1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.tools.build.apkzlib.zip; 18 19 import com.google.common.base.Preconditions; 20 import com.google.common.base.Verify; 21 import com.google.common.collect.Lists; 22 import com.google.common.collect.Sets; 23 import com.google.common.primitives.Ints; 24 import java.util.List; 25 import java.util.Set; 26 import java.util.SortedSet; 27 import java.util.StringJoiner; 28 import java.util.TreeSet; 29 import javax.annotation.Nonnull; 30 import javax.annotation.Nullable; 31 32 /** 33 * The file use map keeps track of which parts of the zip file are used which parts are not. 34 * It essentially maintains an ordered set of entries ({@link FileUseMapEntry}). Each entry either has 35 * some data (an entry, the Central Directory, the EOCD) or is a free entry. 36 * 37 * <p>For example: [0-95, "foo/"][95-260, "xpto"][260-310, free][310-360, Central Directory] 38 * [360-390,EOCD] 39 * 40 * <p>There are a few invariants in this structure: 41 * <ul> 42 * <li>there are no gaps between map entries; 43 * <li>the map is fully covered up to its size; 44 * <li>there are no two free entries next to each other; this is guaranteed by coalescing the 45 * entries upon removal (see {@link #coalesce(FileUseMapEntry)}); 46 * <li>all free entries have a minimum size defined in the constructor, with the possible exception 47 * of the last one 48 * </ul> 49 */ 50 class FileUseMap { 51 /** 52 * Size of the file according to the map. This should always match the last entry in 53 * {@code #map}. 54 */ 55 private long size; 56 57 /** 58 * Tree with all intervals ordered by position. Contains coverage from 0 up to {@link #size}. 59 * If {@link #size} is zero then this set is empty. This is the only situation in which the map 60 * will be empty. 61 */ 62 @Nonnull 63 private TreeSet<FileUseMapEntry<?>> map; 64 65 /** 66 * Tree with all free blocks ordered by size. This is essentially a view over {@link #map} 67 * containing only the free blocks, but in a different order. 68 */ 69 @Nonnull 70 private TreeSet<FileUseMapEntry<?>> free; 71 72 /** 73 * If defined, defines the minimum size for a free entry. 74 */ 75 private int mMinFreeSize; 76 77 /** 78 * Creates a new, empty file map. 79 * 80 * @param size the size of the file 81 * @param minFreeSize minimum size of a free entry 82 */ FileUseMap(long size, int minFreeSize)83 FileUseMap(long size, int minFreeSize) { 84 Preconditions.checkArgument(size >= 0, "size < 0"); 85 Preconditions.checkArgument(minFreeSize >= 0, "minFreeSize < 0"); 86 87 this.size = size; 88 map = new TreeSet<>(FileUseMapEntry.COMPARE_BY_START); 89 free = new TreeSet<>(FileUseMapEntry.COMPARE_BY_SIZE); 90 mMinFreeSize = minFreeSize; 91 92 if (size > 0) { 93 internalAdd(FileUseMapEntry.makeFree(0, size)); 94 } 95 } 96 97 /** 98 * Adds an entry to the internal structures. 99 * 100 * @param entry the entry to add 101 */ internalAdd(@onnull FileUseMapEntry<?> entry)102 private void internalAdd(@Nonnull FileUseMapEntry<?> entry) { 103 map.add(entry); 104 105 if (entry.isFree()) { 106 free.add(entry); 107 } 108 } 109 110 /** 111 * Removes an entry from the internal structures. 112 * 113 * @param entry the entry to remove 114 */ internalRemove(@onnull FileUseMapEntry<?> entry)115 private void internalRemove(@Nonnull FileUseMapEntry<?> entry) { 116 boolean wasRemoved = map.remove(entry); 117 Preconditions.checkState(wasRemoved, "entry not in map"); 118 119 if (entry.isFree()) { 120 free.remove(entry); 121 } 122 } 123 124 /** 125 * Adds a new file to the map. The interval specified by {@code entry} must fit inside an 126 * empty entry in the map. That entry will be replaced by entry and additional free entries 127 * will be added before and after if needed to make sure no spaces exist on the map. 128 * 129 * @param entry the entry to add 130 */ add(@onnull FileUseMapEntry<?> entry)131 private void add(@Nonnull FileUseMapEntry<?> entry) { 132 Preconditions.checkArgument(entry.getStart() < size, "entry.getStart() >= size"); 133 Preconditions.checkArgument(entry.getEnd() <= size, "entry.getEnd() > size"); 134 Preconditions.checkArgument(!entry.isFree(), "entry.isFree()"); 135 136 FileUseMapEntry<?> container = findContainer(entry); 137 Verify.verify(container.isFree(), "!container.isFree()"); 138 139 Set<FileUseMapEntry<?>> replacements = split(container, entry); 140 internalRemove(container); 141 for (FileUseMapEntry<?> r : replacements) { 142 internalAdd(r); 143 } 144 } 145 146 /** 147 * Removes a file from the map, replacing it with an empty one that is then coalesced with 148 * neighbors (if the neighbors are free). 149 * 150 * @param entry the entry 151 */ 152 void remove(@Nonnull FileUseMapEntry<?> entry) { 153 Preconditions.checkState(map.contains(entry), "!map.contains(entry)"); 154 Preconditions.checkArgument(!entry.isFree(), "entry.isFree()"); 155 156 internalRemove(entry); 157 158 FileUseMapEntry<?> replacement = FileUseMapEntry.makeFree(entry.getStart(), entry.getEnd()); 159 internalAdd(replacement); 160 coalesce(replacement); 161 } 162 163 /** 164 * Adds a new file to the map. The interval specified by ({@code start}, {@code end}) must fit 165 * inside an empty entry in the map. That entry will be replaced by entry and additional free 166 * entries will be added before and after if needed to make sure no spaces exist on the map. 167 * 168 * <p>The entry cannot extend beyong the end of the map. If necessary, extend the map using 169 * {@link #extend(long)}. 170 * 171 * @param start the start of this entry 172 * @param end the end of the entry 173 * @param store extra data to store with the entry 174 * @param <T> the type of data to store in the entry 175 * @return the new entry 176 */ 177 <T> FileUseMapEntry<T> add(long start, long end, @Nonnull T store) { 178 Preconditions.checkArgument(start >= 0, "start < 0"); 179 Preconditions.checkArgument(end > start, "end < start"); 180 181 FileUseMapEntry<T> entry = FileUseMapEntry.makeUsed(start, end, store); 182 add(entry); 183 return entry; 184 } 185 186 /** 187 * Finds the entry that fully contains the given one. It is assumed that one exists. 188 * 189 * @param entry the entry whose container we're looking for 190 * @return the container 191 */ 192 @Nonnull findContainer(@onnull FileUseMapEntry<?> entry)193 private FileUseMapEntry<?> findContainer(@Nonnull FileUseMapEntry<?> entry) { 194 FileUseMapEntry container = map.floor(entry); 195 Verify.verifyNotNull(container); 196 Verify.verify(container.getStart() <= entry.getStart()); 197 Verify.verify(container.getEnd() >= entry.getEnd()); 198 199 return container; 200 } 201 202 /** 203 * Splits a container to add an entry, adding new free entries before and after the provided 204 * entry if needed. 205 * 206 * @param container the container entry, a free entry that is in {@link #map} that that 207 * encloses {@code entry} 208 * @param entry the entry that will be used to split {@code container} 209 * @return a set of non-overlapping entries that completely covers {@code container} and that 210 * includes {@code entry} 211 */ 212 @Nonnull split(@onnull FileUseMapEntry<?> container, @Nonnull FileUseMapEntry<?> entry)213 private static Set<FileUseMapEntry<?>> split(@Nonnull FileUseMapEntry<?> container, 214 @Nonnull FileUseMapEntry<?> entry) { 215 Preconditions.checkArgument(container.isFree(), "!container.isFree()"); 216 217 long farStart = container.getStart(); 218 long start = entry.getStart(); 219 long end = entry.getEnd(); 220 long farEnd = container.getEnd(); 221 222 Verify.verify(farStart <= start, "farStart > start"); 223 Verify.verify(start < end, "start >= end"); 224 Verify.verify(farEnd >= end, "farEnd < end"); 225 226 Set<FileUseMapEntry<?>> result = Sets.newHashSet(); 227 if (farStart < start) { 228 result.add(FileUseMapEntry.makeFree(farStart, start)); 229 } 230 231 result.add(entry); 232 233 if (end < farEnd) { 234 result.add(FileUseMapEntry.makeFree(end, farEnd)); 235 } 236 237 return result; 238 } 239 240 /** 241 * Coalesces a free entry replacing it and neighboring free entries with a single, larger 242 * entry. This method does nothing if {@code entry} does not have free neighbors. 243 * 244 * @param entry the free entry to coalesce with neighbors 245 */ coalesce(@onnull FileUseMapEntry<?> entry)246 private void coalesce(@Nonnull FileUseMapEntry<?> entry) { 247 Preconditions.checkArgument(entry.isFree(), "!entry.isFree()"); 248 249 FileUseMapEntry<?> prevToMerge = null; 250 long start = entry.getStart(); 251 if (start > 0) { 252 /* 253 * See if we have a previous entry to merge with this one. 254 */ 255 prevToMerge = map.floor(FileUseMapEntry.makeFree(start - 1, start)); 256 Verify.verifyNotNull(prevToMerge); 257 if (!prevToMerge.isFree()) { 258 prevToMerge = null; 259 } 260 } 261 262 FileUseMapEntry<?> nextToMerge = null; 263 long end = entry.getEnd(); 264 if (end < size) { 265 /* 266 * See if we have a next entry to merge with this one. 267 */ 268 nextToMerge = map.ceiling(FileUseMapEntry.makeFree(end, end + 1)); 269 Verify.verifyNotNull(nextToMerge); 270 if (!nextToMerge.isFree()) { 271 nextToMerge = null; 272 } 273 } 274 275 if (prevToMerge == null && nextToMerge == null) { 276 return; 277 } 278 279 long newStart = start; 280 if (prevToMerge != null) { 281 newStart = prevToMerge.getStart(); 282 internalRemove(prevToMerge); 283 } 284 285 long newEnd = end; 286 if (nextToMerge != null) { 287 newEnd = nextToMerge.getEnd(); 288 internalRemove(nextToMerge); 289 } 290 291 internalRemove(entry); 292 internalAdd(FileUseMapEntry.makeFree(newStart, newEnd)); 293 } 294 295 /** 296 * Truncates map removing the top entry if it is free and reducing the map's size. 297 */ truncate()298 void truncate() { 299 if (size == 0) { 300 return; 301 } 302 303 /* 304 * Find the last entry. 305 */ 306 FileUseMapEntry<?> last = map.last(); 307 Verify.verifyNotNull(last, "last == null"); 308 if (last.isFree()) { 309 internalRemove(last); 310 size = last.getStart(); 311 } 312 } 313 314 /** 315 * Obtains the size of the map. 316 * 317 * @return the size 318 */ size()319 long size() { 320 return size; 321 } 322 323 /** 324 * Obtains the largest used offset in the map. This will be size of the map after truncation. 325 * 326 * @return the size of the file discounting the last block if it is empty 327 */ usedSize()328 long usedSize() { 329 if (size == 0) { 330 return 0; 331 } 332 333 /* 334 * Find the last entry to see if it is an empty entry. If it is, we need to remove its size 335 * from the returned value. 336 */ 337 FileUseMapEntry<?> last = map.last(); 338 Verify.verifyNotNull(last, "last == null"); 339 if (last.isFree()) { 340 return last.getStart(); 341 } else { 342 Verify.verify(last.getEnd() == size); 343 return size; 344 } 345 } 346 347 /** 348 * Extends the map to guarantee it has at least {@code size} bytes. If the current size is 349 * as large as {@code size}, this method does nothing. 350 * 351 * @param size the new size of the map that cannot be smaller that the current size 352 */ extend(long size)353 void extend(long size) { 354 Preconditions.checkArgument(size >= this.size, "size < size"); 355 356 if (this.size == size) { 357 return; 358 } 359 360 FileUseMapEntry<?> newBlock = FileUseMapEntry.makeFree(this.size, size); 361 internalAdd(newBlock); 362 363 this.size = size; 364 365 coalesce(newBlock); 366 } 367 368 /** 369 * Locates a free area in the map with at least {@code size} bytes such that 370 * {@code ((start + alignOffset) % align == 0} and such that the free space before {@code start} 371 * is not smaller than the minimum free entry size. This method will follow the algorithm 372 * specified by {@code alg}. 373 * 374 * <p>If no free contiguous block exists in the map that can hold the provided 375 * size then the first free index at the end of the map is provided. This means that the map 376 * may need to be extended before data can be added. 377 * 378 * @param size the size of the contiguous area requested 379 * @param alignOffset an offset to which alignment needs to be computed (see method description) 380 * @param align alignment at the offset (see method description) 381 * @param alg which algorithm to use 382 * @return the location of the contiguous area; this may be located at the end of the map 383 */ locateFree(long size, long alignOffset, long align, @Nonnull PositionAlgorithm alg)384 long locateFree(long size, long alignOffset, long align, @Nonnull PositionAlgorithm alg) { 385 Preconditions.checkArgument(size > 0, "size <= 0"); 386 387 FileUseMapEntry<?> minimumSizedEntry = FileUseMapEntry.makeFree(0, size); 388 SortedSet<FileUseMapEntry<?>> matches; 389 390 switch (alg) { 391 case BEST_FIT: 392 matches = free.tailSet(minimumSizedEntry); 393 break; 394 case FIRST_FIT: 395 matches = map; 396 break; 397 default: 398 throw new AssertionError(); 399 } 400 401 FileUseMapEntry<?> best = null; 402 long bestExtraSize = 0; 403 for (FileUseMapEntry<?> curr : matches) { 404 /* 405 * We don't care about blocks that aren't free. 406 */ 407 if (!curr.isFree()) { 408 continue; 409 } 410 411 /* 412 * Compute any extra size we need in this block to make sure we verify the alignment. 413 * There must be a better to do this... 414 */ 415 long extraSize; 416 if (align == 0) { 417 extraSize = 0; 418 } else { 419 extraSize = (align - ((curr.getStart() + alignOffset) % align)) % align; 420 } 421 422 /* 423 * We can't leave than mMinFreeSize before. So if the extraSize is less than 424 * mMinFreeSize, we have to increase it by 'align' as many times as needed. For 425 * example, if mMinFreeSize is 20, align 4 and extraSize is 5. We need to increase it 426 * to 21 (5 + 4 * 4) 427 */ 428 if (extraSize > 0 && extraSize < mMinFreeSize) { 429 int addAlignBlocks = 430 Ints.checkedCast((mMinFreeSize - extraSize + align - 1) / align); 431 extraSize += addAlignBlocks * align; 432 } 433 434 /* 435 * We don't care about blocks where we don't fit in. 436 */ 437 if (curr.getSize() < (size + extraSize)) { 438 continue; 439 } 440 441 /* 442 * We don't care about blocks that leave less than the minimum size after. There are 443 * two exceptions: (1) this is the last block and (2) the next block is free in which 444 * case, after coalescing, the free block with have at least the minimum size. 445 */ 446 long emptySpaceLeft = curr.getSize() - (size + extraSize); 447 if (emptySpaceLeft > 0 && emptySpaceLeft < mMinFreeSize) { 448 FileUseMapEntry<?> next = map.higher(curr); 449 if (next != null && !next.isFree()) { 450 continue; 451 } 452 } 453 454 /* 455 * We don't care about blocks that are bigger than the best so far (otherwise this 456 * wouldn't be a best-fit algorithm). 457 */ 458 if (best != null && best.getSize() < curr.getSize()) { 459 continue; 460 } 461 462 best = curr; 463 bestExtraSize = extraSize; 464 465 /* 466 * If we're doing first fit, we don't want to search for a better one :) 467 */ 468 if (alg == PositionAlgorithm.FIRST_FIT) { 469 break; 470 } 471 } 472 473 /* 474 * If no entry that could hold size is found, get the first free byte. 475 */ 476 long firstFree = this.size; 477 if (best == null && !map.isEmpty()) { 478 FileUseMapEntry<?> last = map.last(); 479 if (last.isFree()) { 480 firstFree = last.getStart(); 481 } 482 } 483 484 /* 485 * We're done: either we found something or we didn't, in which the new entry needs to 486 * be added to the end of the map. 487 */ 488 if (best == null) { 489 long extra = (align - ((firstFree + alignOffset) % align)) % align; 490 491 /* 492 * If adding this entry at the end would create a space smaller than the minimum, 493 * push it for 'align' bytes forward. 494 */ 495 if (extra > 0) { 496 if (extra < mMinFreeSize) { 497 extra += align * (((mMinFreeSize - extra) + (align - 1)) / align); 498 } 499 } 500 501 return firstFree + extra; 502 } else { 503 return best.getStart() + bestExtraSize; 504 } 505 } 506 507 /** 508 * Obtains all free areas of the map, excluding any trailing free area. 509 * 510 * @return all free areas, an empty set if there are no free areas; the areas are returned 511 * in file order, that is, if area {@code x} starts before area {@code y}, then area {@code x} 512 * will be stored before area {@code y} in the list 513 */ 514 @Nonnull getFreeAreas()515 List<FileUseMapEntry<?>> getFreeAreas() { 516 List<FileUseMapEntry<?>> freeAreas = Lists.newArrayList(); 517 518 for (FileUseMapEntry<?> area : map) { 519 if (area.isFree() && area.getEnd() != size) { 520 freeAreas.add(area); 521 } 522 } 523 524 return freeAreas; 525 } 526 527 /** 528 * Obtains the entry that is located before the one provided. 529 * 530 * @param entry the map entry to get the previous one for; must belong to the map 531 * @return the entry before the provided one, {@code null} if {@code entry} is the first entry 532 * in the map 533 */ 534 @Nullable before(@onnull FileUseMapEntry<?> entry)535 FileUseMapEntry<?> before(@Nonnull FileUseMapEntry<?> entry) { 536 Preconditions.checkNotNull(entry, "entry == null"); 537 538 return map.lower(entry); 539 } 540 541 /** 542 * Obtains the entry that is located after the one provided. 543 * 544 * @param entry the map entry to get the next one for; must belong to the map 545 * @return the entry after the provided one, {@code null} if {@code entry} is the last entry in 546 * the map 547 */ 548 @Nullable after(@onnull FileUseMapEntry<?> entry)549 FileUseMapEntry<?> after(@Nonnull FileUseMapEntry<?> entry) { 550 Preconditions.checkNotNull(entry, "entry == null"); 551 552 return map.higher(entry); 553 } 554 555 /** 556 * Obtains the entry at the given offset. 557 * 558 * @param offset the offset to look for 559 * @return the entry found or {@code null} if there is no entry (not even a free one) at the 560 * given offset 561 */ 562 @Nullable at(long offset)563 FileUseMapEntry<?> at(long offset) { 564 Preconditions.checkArgument(offset >= 0, "offset < 0"); 565 Preconditions.checkArgument(offset < size, "offset >= size"); 566 567 FileUseMapEntry<?> entry = map.floor(FileUseMapEntry.makeFree(offset, offset + 1)); 568 if (entry == null) { 569 return null; 570 } 571 572 Verify.verify(entry.getStart() <= offset); 573 Verify.verify(entry.getEnd() > offset); 574 575 return entry; 576 } 577 578 @Override 579 public String toString() { 580 StringJoiner j = new StringJoiner(", "); 581 map.stream() 582 .map(e -> e.getStart() + " - " + e.getEnd() + ": " + e.getStore()) 583 .forEach(j::add); 584 return "FileUseMap[" + j.toString() + "]"; 585 } 586 587 /** 588 * Algorithms used to position entries in blocks. 589 */ 590 public enum PositionAlgorithm { 591 /** 592 * Best fit: finds the smallest free block that can receive the entry. 593 */ 594 BEST_FIT, 595 596 /** 597 * First fit: finds the first free block that can receive the entry. 598 */ 599 FIRST_FIT 600 } 601 } 602