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