1 /* 2 * Copyright (C) 2010 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 #include "ext4_utils.h" 18 #include "allocate.h" 19 20 #include <sparse/sparse.h> 21 22 #include <stdio.h> 23 #include <stdlib.h> 24 25 struct region { 26 u32 block; 27 u32 len; 28 int bg; 29 struct region *next; 30 struct region *prev; 31 }; 32 33 struct block_group_info { 34 u32 first_block; 35 int header_blocks; 36 int data_blocks_used; 37 int has_superblock; 38 u8 *bitmaps; 39 u8 *block_bitmap; 40 u8 *inode_bitmap; 41 u8 *inode_table; 42 u32 free_blocks; 43 u32 first_free_block; 44 u32 free_inodes; 45 u32 first_free_inode; 46 u16 flags; 47 u16 used_dirs; 48 }; 49 50 struct xattr_list_element { 51 struct ext4_inode *inode; 52 struct ext4_xattr_header *header; 53 struct xattr_list_element *next; 54 }; 55 56 struct block_allocation *create_allocation() 57 { 58 struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 59 alloc->list.first = NULL; 60 alloc->list.last = NULL; 61 alloc->oob_list.first = NULL; 62 alloc->oob_list.last = NULL; 63 alloc->list.iter = NULL; 64 alloc->list.partial_iter = 0; 65 alloc->oob_list.iter = NULL; 66 alloc->oob_list.partial_iter = 0; 67 alloc->filename = NULL; 68 alloc->next = NULL; 69 return alloc; 70 } 71 72 static struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode) 73 { 74 struct xattr_list_element *element; 75 for (element = aux_info.xattrs; element != NULL; element = element->next) { 76 if (element->inode == inode) 77 return element->header; 78 } 79 return NULL; 80 } 81 82 static void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header) 83 { 84 struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element)); 85 element->inode = inode; 86 element->header = header; 87 element->next = aux_info.xattrs; 88 aux_info.xattrs = element; 89 } 90 91 static void region_list_remove(struct region_list *list, struct region *reg) 92 { 93 if (reg->prev) 94 reg->prev->next = reg->next; 95 96 if (reg->next) 97 reg->next->prev = reg->prev; 98 99 if (list->first == reg) 100 list->first = reg->next; 101 102 if (list->last == reg) 103 list->last = reg->prev; 104 105 reg->next = NULL; 106 reg->prev = NULL; 107 } 108 109 static void region_list_append(struct region_list *list, struct region *reg) 110 { 111 if (list->first == NULL) { 112 list->first = reg; 113 list->last = reg; 114 list->iter = reg; 115 list->partial_iter = 0; 116 reg->prev = NULL; 117 } else { 118 list->last->next = reg; 119 reg->prev = list->last; 120 list->last = reg; 121 } 122 reg->next = NULL; 123 } 124 125 #if 0 126 static void dump_starting_from(struct region *reg) 127 { 128 for (; reg; reg = reg->next) { 129 printf("%p: Blocks %d-%d (%d)\n", reg, 130 reg->block, reg->block + reg->len - 1, reg->len) 131 } 132 } 133 134 static void dump_region_lists(struct block_allocation *alloc) { 135 136 printf("Main list:\n"); 137 dump_starting_from(alloc->list.first); 138 139 printf("OOB list:\n"); 140 dump_starting_from(alloc->oob_list.first); 141 } 142 #endif 143 144 void print_blocks(FILE* f, struct block_allocation *alloc) 145 { 146 struct region *reg; 147 for (reg = alloc->list.first; reg; reg = reg->next) { 148 if (reg->len == 1) { 149 fprintf(f, " %d", reg->block); 150 } else { 151 fprintf(f, " %d-%d", reg->block, reg->block + reg->len - 1); 152 } 153 } 154 fputc('\n', f); 155 } 156 157 void append_region(struct block_allocation *alloc, 158 u32 block, u32 len, int bg_num) 159 { 160 struct region *reg; 161 reg = malloc(sizeof(struct region)); 162 reg->block = block; 163 reg->len = len; 164 reg->bg = bg_num; 165 reg->next = NULL; 166 167 region_list_append(&alloc->list, reg); 168 } 169 170 static void allocate_bg_inode_table(struct block_group_info *bg) 171 { 172 if (bg->inode_table != NULL) 173 return; 174 175 u32 block = bg->first_block + 2; 176 177 if (bg->has_superblock) 178 block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 179 180 bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 181 if (bg->inode_table == NULL) 182 critical_error_errno("calloc"); 183 184 sparse_file_add_data(ext4_sparse_file, bg->inode_table, 185 aux_info.inode_table_blocks * info.block_size, block); 186 187 bg->flags &= ~EXT4_BG_INODE_UNINIT; 188 } 189 190 static int bitmap_set_bit(u8 *bitmap, u32 bit) 191 { 192 if (bitmap[bit / 8] & 1 << (bit % 8)) 193 return 1; 194 195 bitmap[bit / 8] |= 1 << (bit % 8); 196 return 0; 197 } 198 199 static int bitmap_set_8_bits(u8 *bitmap, u32 bit) 200 { 201 int ret = bitmap[bit / 8]; 202 bitmap[bit / 8] = 0xFF; 203 return ret; 204 } 205 206 /* Marks a the first num_blocks blocks in a block group as used, and accounts 207 for them in the block group free block info. */ 208 static int reserve_blocks(struct block_group_info *bg, u32 start, u32 num) 209 { 210 unsigned int i = 0; 211 212 u32 block = start; 213 if (num > bg->free_blocks) 214 return -1; 215 216 for (i = 0; i < num && block % 8 != 0; i++, block++) { 217 if (bitmap_set_bit(bg->block_bitmap, block)) { 218 error("attempted to reserve already reserved block"); 219 return -1; 220 } 221 } 222 223 for (; i + 8 <= (num & ~7); i += 8, block += 8) { 224 if (bitmap_set_8_bits(bg->block_bitmap, block)) { 225 error("attempted to reserve already reserved block"); 226 return -1; 227 } 228 } 229 230 for (; i < num; i++, block++) { 231 if (bitmap_set_bit(bg->block_bitmap, block)) { 232 error("attempted to reserve already reserved block"); 233 return -1; 234 } 235 } 236 237 bg->free_blocks -= num; 238 if (start == bg->first_free_block) 239 bg->first_free_block = start + num; 240 241 return 0; 242 } 243 244 static void free_blocks(struct block_group_info *bg, u32 num_blocks) 245 { 246 unsigned int i; 247 u32 block = bg->first_free_block - 1; 248 for (i = 0; i < num_blocks; i++, block--) 249 bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 250 bg->free_blocks += num_blocks; 251 bg->first_free_block -= num_blocks; 252 } 253 254 /* Reduces an existing allocation by len blocks by return the last blocks 255 to the free pool in their block group. Assumes that the blocks being 256 returned were the last ones allocated out of the block group */ 257 void reduce_allocation(struct block_allocation *alloc, u32 len) 258 { 259 while (len) { 260 struct region *last_reg = alloc->list.last; 261 262 if (last_reg->len > len) { 263 free_blocks(&aux_info.bgs[last_reg->bg], len); 264 last_reg->len -= len; 265 len = 0; 266 } else { 267 struct region *reg = alloc->list.last->prev; 268 free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len); 269 len -= last_reg->len; 270 if (reg) { 271 reg->next = NULL; 272 } else { 273 alloc->list.first = NULL; 274 alloc->list.last = NULL; 275 alloc->list.iter = NULL; 276 alloc->list.partial_iter = 0; 277 } 278 free(last_reg); 279 } 280 } 281 } 282 283 static void init_bg(struct block_group_info *bg, unsigned int i) 284 { 285 int header_blocks = 2 + aux_info.inode_table_blocks; 286 287 bg->has_superblock = ext4_bg_has_super_block(i); 288 289 if (bg->has_superblock) 290 header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 291 292 bg->bitmaps = calloc(info.block_size, 2); 293 bg->block_bitmap = bg->bitmaps; 294 bg->inode_bitmap = bg->bitmaps + info.block_size; 295 296 bg->header_blocks = header_blocks; 297 bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 298 299 u32 block = bg->first_block; 300 if (bg->has_superblock) 301 block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 302 sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 303 block); 304 305 bg->data_blocks_used = 0; 306 bg->free_blocks = info.blocks_per_group; 307 bg->first_free_block = 0; 308 bg->free_inodes = info.inodes_per_group; 309 bg->first_free_inode = 1; 310 bg->flags = EXT4_BG_INODE_UNINIT; 311 312 if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) 313 error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 314 315 if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 316 u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 317 reserve_blocks(bg, info.blocks_per_group - overrun, overrun); 318 } 319 } 320 321 void block_allocator_init() 322 { 323 unsigned int i; 324 325 aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 326 if (aux_info.bgs == NULL) 327 critical_error_errno("calloc"); 328 329 for (i = 0; i < aux_info.groups; i++) 330 init_bg(&aux_info.bgs[i], i); 331 } 332 333 void block_allocator_free() 334 { 335 unsigned int i; 336 337 for (i = 0; i < aux_info.groups; i++) { 338 free(aux_info.bgs[i].bitmaps); 339 free(aux_info.bgs[i].inode_table); 340 } 341 free(aux_info.bgs); 342 } 343 344 static u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) 345 { 346 if (get_free_blocks(bg_num) < len) 347 return EXT4_ALLOCATE_FAILED; 348 349 u32 block = aux_info.bgs[bg_num].first_free_block; 350 struct block_group_info *bg = &aux_info.bgs[bg_num]; 351 if (reserve_blocks(bg, bg->first_free_block, len) < 0) { 352 error("failed to reserve %u blocks in block group %u\n", len, bg_num); 353 return EXT4_ALLOCATE_FAILED; 354 } 355 356 aux_info.bgs[bg_num].data_blocks_used += len; 357 358 return bg->first_block + block; 359 } 360 361 /* Allocate a single block and return its block number */ 362 u32 allocate_block() 363 { 364 unsigned int i; 365 for (i = 0; i < aux_info.groups; i++) { 366 u32 block = ext4_allocate_blocks_from_block_group(1, i); 367 368 if (block != EXT4_ALLOCATE_FAILED) 369 return block; 370 } 371 372 return EXT4_ALLOCATE_FAILED; 373 } 374 375 static struct region *ext4_allocate_best_fit_partial(u32 len) 376 { 377 unsigned int i; 378 unsigned int found_bg = 0; 379 u32 found_bg_len = 0; 380 381 for (i = 0; i < aux_info.groups; i++) { 382 u32 bg_len = aux_info.bgs[i].free_blocks; 383 384 if ((len <= bg_len && (found_bg_len == 0 || bg_len < found_bg_len)) || 385 (len > found_bg_len && bg_len > found_bg_len)) { 386 found_bg = i; 387 found_bg_len = bg_len; 388 } 389 } 390 391 if (found_bg_len) { 392 u32 allocate_len = min(len, found_bg_len); 393 struct region *reg; 394 u32 block = ext4_allocate_blocks_from_block_group(allocate_len, found_bg); 395 if (block == EXT4_ALLOCATE_FAILED) { 396 error("failed to allocate %d blocks in block group %d", allocate_len, found_bg); 397 return NULL; 398 } 399 reg = malloc(sizeof(struct region)); 400 reg->block = block; 401 reg->len = allocate_len; 402 reg->next = NULL; 403 reg->prev = NULL; 404 reg->bg = found_bg; 405 return reg; 406 } else { 407 error("failed to allocate %u blocks, out of space?", len); 408 } 409 410 return NULL; 411 } 412 413 static struct region *ext4_allocate_best_fit(u32 len) 414 { 415 struct region *first_reg = NULL; 416 struct region *prev_reg = NULL; 417 struct region *reg; 418 419 while (len > 0) { 420 reg = ext4_allocate_best_fit_partial(len); 421 if (reg == NULL) 422 return NULL; 423 424 if (first_reg == NULL) 425 first_reg = reg; 426 427 if (prev_reg) { 428 prev_reg->next = reg; 429 reg->prev = prev_reg; 430 } 431 432 prev_reg = reg; 433 len -= reg->len; 434 } 435 436 return first_reg; 437 } 438 439 /* Allocate len blocks. The blocks may be spread across multiple block groups, 440 and are returned in a linked list of the blocks in each block group. The 441 allocation algorithm is: 442 1. If the remaining allocation is larger than any available contiguous region, 443 allocate the largest contiguous region and loop 444 2. Otherwise, allocate the smallest contiguous region that it fits in 445 */ 446 struct block_allocation *allocate_blocks(u32 len) 447 { 448 struct region *reg = ext4_allocate_best_fit(len); 449 450 if (reg == NULL) 451 return NULL; 452 453 struct block_allocation *alloc = create_allocation(); 454 alloc->list.first = reg; 455 alloc->list.last = reg; 456 alloc->list.iter = alloc->list.first; 457 alloc->list.partial_iter = 0; 458 return alloc; 459 } 460 461 /* Returns the number of discontiguous regions used by an allocation */ 462 int block_allocation_num_regions(struct block_allocation *alloc) 463 { 464 unsigned int i; 465 struct region *reg = alloc->list.first; 466 467 for (i = 0; reg != NULL; reg = reg->next) 468 i++; 469 470 return i; 471 } 472 473 int block_allocation_len(struct block_allocation *alloc) 474 { 475 unsigned int i; 476 struct region *reg = alloc->list.first; 477 478 for (i = 0; reg != NULL; reg = reg->next) 479 i += reg->len; 480 481 return i; 482 } 483 484 /* Returns the block number of the block'th block in an allocation */ 485 u32 get_block(struct block_allocation *alloc, u32 block) 486 { 487 struct region *reg = alloc->list.iter; 488 block += alloc->list.partial_iter; 489 490 for (; reg; reg = reg->next) { 491 if (block < reg->len) 492 return reg->block + block; 493 block -= reg->len; 494 } 495 return EXT4_ALLOCATE_FAILED; 496 } 497 498 u32 get_oob_block(struct block_allocation *alloc, u32 block) 499 { 500 struct region *reg = alloc->oob_list.iter; 501 block += alloc->oob_list.partial_iter; 502 503 for (; reg; reg = reg->next) { 504 if (block < reg->len) 505 return reg->block + block; 506 block -= reg->len; 507 } 508 return EXT4_ALLOCATE_FAILED; 509 } 510 511 /* Gets the starting block and length in blocks of the first region 512 of an allocation */ 513 void get_region(struct block_allocation *alloc, u32 *block, u32 *len) 514 { 515 *block = alloc->list.iter->block; 516 *len = alloc->list.iter->len - alloc->list.partial_iter; 517 } 518 519 /* Move to the next region in an allocation */ 520 void get_next_region(struct block_allocation *alloc) 521 { 522 alloc->list.iter = alloc->list.iter->next; 523 alloc->list.partial_iter = 0; 524 } 525 526 /* Returns the number of free blocks in a block group */ 527 u32 get_free_blocks(u32 bg) 528 { 529 return aux_info.bgs[bg].free_blocks; 530 } 531 532 int last_region(struct block_allocation *alloc) 533 { 534 return (alloc->list.iter == NULL); 535 } 536 537 void rewind_alloc(struct block_allocation *alloc) 538 { 539 alloc->list.iter = alloc->list.first; 540 alloc->list.partial_iter = 0; 541 } 542 543 static struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 544 { 545 struct region *reg = alloc->list.iter; 546 struct region *new; 547 struct region *tmp; 548 549 while (reg && len >= reg->len) { 550 len -= reg->len; 551 reg = reg->next; 552 } 553 554 if (reg == NULL && len > 0) 555 return NULL; 556 557 if (len > 0) { 558 new = malloc(sizeof(struct region)); 559 560 new->bg = reg->bg; 561 new->block = reg->block + len; 562 new->len = reg->len - len; 563 new->next = reg->next; 564 new->prev = reg; 565 566 reg->next = new; 567 reg->len = len; 568 569 tmp = alloc->list.iter; 570 alloc->list.iter = new; 571 return tmp; 572 } else { 573 return reg; 574 } 575 } 576 577 /* Splits an allocation into two allocations. The returned allocation will 578 point to the first half, and the original allocation ptr will point to the 579 second half. */ 580 static struct region *split_allocation(struct block_allocation *alloc, u32 len) 581 { 582 /* First make sure there is a split at the current ptr */ 583 do_split_allocation(alloc, alloc->list.partial_iter); 584 585 /* Then split off len blocks */ 586 struct region *middle = do_split_allocation(alloc, len); 587 alloc->list.partial_iter = 0; 588 return middle; 589 } 590 591 /* Reserve the next blocks for oob data (indirect or extent blocks) */ 592 int reserve_oob_blocks(struct block_allocation *alloc, int blocks) 593 { 594 struct region *oob = split_allocation(alloc, blocks); 595 struct region *next; 596 597 if (oob == NULL) 598 return -1; 599 600 while (oob && oob != alloc->list.iter) { 601 next = oob->next; 602 region_list_remove(&alloc->list, oob); 603 region_list_append(&alloc->oob_list, oob); 604 oob = next; 605 } 606 607 return 0; 608 } 609 610 static int advance_list_ptr(struct region_list *list, int blocks) 611 { 612 struct region *reg = list->iter; 613 614 while (reg != NULL && blocks > 0) { 615 if (reg->len > list->partial_iter + blocks) { 616 list->partial_iter += blocks; 617 return 0; 618 } 619 620 blocks -= (reg->len - list->partial_iter); 621 list->partial_iter = 0; 622 reg = reg->next; 623 } 624 625 if (blocks > 0) 626 return -1; 627 628 return 0; 629 } 630 631 /* Move the allocation pointer forward */ 632 int advance_blocks(struct block_allocation *alloc, int blocks) 633 { 634 return advance_list_ptr(&alloc->list, blocks); 635 } 636 637 int advance_oob_blocks(struct block_allocation *alloc, int blocks) 638 { 639 return advance_list_ptr(&alloc->oob_list, blocks); 640 } 641 642 int append_oob_allocation(struct block_allocation *alloc, u32 len) 643 { 644 struct region *reg = ext4_allocate_best_fit(len); 645 646 if (reg == NULL) { 647 error("failed to allocate %d blocks", len); 648 return -1; 649 } 650 651 for (; reg; reg = reg->next) 652 region_list_append(&alloc->oob_list, reg); 653 654 return 0; 655 } 656 657 /* Returns an ext4_inode structure for an inode number */ 658 struct ext4_inode *get_inode(u32 inode) 659 { 660 inode -= 1; 661 int bg = inode / info.inodes_per_group; 662 inode %= info.inodes_per_group; 663 664 allocate_bg_inode_table(&aux_info.bgs[bg]); 665 return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 666 info.inode_size); 667 } 668 669 struct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 670 { 671 struct ext4_xattr_header *block = xattr_list_find(inode); 672 if (block != NULL) 673 return block; 674 675 u32 block_num = allocate_block(); 676 block = calloc(info.block_size, 1); 677 if (block == NULL) { 678 error("get_xattr: failed to allocate %d", info.block_size); 679 return NULL; 680 } 681 682 block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 683 block->h_refcount = cpu_to_le32(1); 684 block->h_blocks = cpu_to_le32(1); 685 inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 686 inode->i_file_acl_lo = cpu_to_le32(block_num); 687 688 int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 689 if (result != 0) { 690 error("get_xattr: sparse_file_add_data failure %d", result); 691 free(block); 692 return NULL; 693 } 694 xattr_list_insert(inode, block); 695 return block; 696 } 697 698 /* Mark the first len inodes in a block group as used */ 699 u32 reserve_inodes(int bg, u32 num) 700 { 701 unsigned int i; 702 u32 inode; 703 704 if (get_free_inodes(bg) < num) 705 return EXT4_ALLOCATE_FAILED; 706 707 for (i = 0; i < num; i++) { 708 inode = aux_info.bgs[bg].first_free_inode + i - 1; 709 aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 710 } 711 712 inode = aux_info.bgs[bg].first_free_inode; 713 714 aux_info.bgs[bg].first_free_inode += num; 715 aux_info.bgs[bg].free_inodes -= num; 716 717 return inode; 718 } 719 720 /* Returns the first free inode number 721 TODO: Inodes should be allocated in the block group of the data? */ 722 u32 allocate_inode() 723 { 724 unsigned int bg; 725 u32 inode; 726 727 for (bg = 0; bg < aux_info.groups; bg++) { 728 inode = reserve_inodes(bg, 1); 729 if (inode != EXT4_ALLOCATE_FAILED) 730 return bg * info.inodes_per_group + inode; 731 } 732 733 return EXT4_ALLOCATE_FAILED; 734 } 735 736 /* Returns the number of free inodes in a block group */ 737 u32 get_free_inodes(u32 bg) 738 { 739 return aux_info.bgs[bg].free_inodes; 740 } 741 742 /* Increments the directory count of the block group that contains inode */ 743 void add_directory(u32 inode) 744 { 745 int bg = (inode - 1) / info.inodes_per_group; 746 aux_info.bgs[bg].used_dirs += 1; 747 } 748 749 /* Returns the number of inodes in a block group that are directories */ 750 u16 get_directories(int bg) 751 { 752 return aux_info.bgs[bg].used_dirs; 753 } 754 755 /* Returns the flags for a block group */ 756 u16 get_bg_flags(int bg) 757 { 758 return aux_info.bgs[bg].flags; 759 } 760 761 /* Frees the memory used by a linked list of allocation regions */ 762 void free_alloc(struct block_allocation *alloc) 763 { 764 struct region *reg; 765 766 reg = alloc->list.first; 767 while (reg) { 768 struct region *next = reg->next; 769 free(reg); 770 reg = next; 771 } 772 773 reg = alloc->oob_list.first; 774 while (reg) { 775 struct region *next = reg->next; 776 free(reg); 777 reg = next; 778 } 779 780 free(alloc); 781 } 782
