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 26struct xattr_list_element { 27 struct ext4_inode *inode; 28 struct ext4_xattr_header *header; 29 struct xattr_list_element *next; 30}; 31 32struct 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 48static 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 58static 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 67static 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 85void 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 101void 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 116static 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 124static 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 134void 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 149void 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 162static 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 182static 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 191static 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. */ 200static 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 231static void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks) 232{ 233 unsigned int i; 234 for (i = 0; i < num_blocks; i++, block--) 235 bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 236 bg->free_blocks += num_blocks; 237 for (i = bg->chunk_count; i > 0 ;) { 238 --i; 239 if (bg->chunks[i].len >= num_blocks && bg->chunks[i].block <= block) { 240 if (bg->chunks[i].block == block) { 241 bg->chunks[i].block += num_blocks; 242 bg->chunks[i].len -= num_blocks; 243 } else if (bg->chunks[i].block + bg->chunks[i].len - 1 == block + num_blocks) { 244 bg->chunks[i].len -= num_blocks; 245 } 246 break; 247 } 248 } 249} 250 251/* Reduces an existing allocation by len blocks by return the last blocks 252 to the free pool in their block group. Assumes that the blocks being 253 returned were the last ones allocated out of the block group */ 254void reduce_allocation(struct block_allocation *alloc, u32 len) 255{ 256 while (len) { 257 struct region *last_reg = alloc->list.last; 258 struct block_group_info *bg = &aux_info.bgs[last_reg->bg]; 259 260 if (last_reg->len > len) { 261 free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len); 262 last_reg->len -= len; 263 len = 0; 264 } else { 265 struct region *reg = alloc->list.last->prev; 266 free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len); 267 len -= last_reg->len; 268 if (reg) { 269 reg->next = NULL; 270 } else { 271 alloc->list.first = NULL; 272 alloc->list.last = NULL; 273 alloc->list.iter = NULL; 274 alloc->list.partial_iter = 0; 275 } 276 free(last_reg); 277 } 278 } 279} 280 281static void init_bg(struct block_group_info *bg, unsigned int i) 282{ 283 int header_blocks = 2 + aux_info.inode_table_blocks; 284 285 bg->has_superblock = ext4_bg_has_super_block(i); 286 287 if (bg->has_superblock) 288 header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 289 290 bg->bitmaps = calloc(info.block_size, 2); 291 bg->block_bitmap = bg->bitmaps; 292 bg->inode_bitmap = bg->bitmaps + info.block_size; 293 294 bg->header_blocks = header_blocks; 295 bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 296 297 u32 block = bg->first_block; 298 if (bg->has_superblock) 299 block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 300 sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 301 block); 302 303 bg->data_blocks_used = 0; 304 bg->free_blocks = info.blocks_per_group; 305 bg->free_inodes = info.inodes_per_group; 306 bg->first_free_inode = 1; 307 bg->flags = EXT4_BG_INODE_UNINIT; 308 309 bg->chunk_count = 0; 310 bg->max_chunk_count = 1; 311 bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region)); 312 313 if (reserve_blocks(bg, i, 0, bg->header_blocks) < 0) 314 error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 315 // Add empty starting delimiter chunk 316 reserve_bg_chunk(i, bg->header_blocks, 0); 317 318 if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 319 u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 320 reserve_blocks(bg, i, info.blocks_per_group - overrun, overrun); 321 // Add empty ending delimiter chunk 322 reserve_bg_chunk(i, info.blocks_per_group - overrun, 0); 323 } else { 324 reserve_bg_chunk(i, info.blocks_per_group - 1, 0); 325 } 326 327} 328 329void block_allocator_init() 330{ 331 unsigned int i; 332 333 aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 334 if (aux_info.bgs == NULL) 335 critical_error_errno("calloc"); 336 337 for (i = 0; i < aux_info.groups; i++) 338 init_bg(&aux_info.bgs[i], i); 339} 340 341void block_allocator_free() 342{ 343 unsigned int i; 344 345 for (i = 0; i < aux_info.groups; i++) { 346 free(aux_info.bgs[i].bitmaps); 347 free(aux_info.bgs[i].inode_table); 348 } 349 free(aux_info.bgs); 350} 351 352/* Allocate a single block and return its block number */ 353u32 allocate_block() 354{ 355 u32 block; 356 struct block_allocation *blk_alloc = allocate_blocks(1); 357 if (!blk_alloc) { 358 return EXT4_ALLOCATE_FAILED; 359 } 360 block = blk_alloc->list.first->block; 361 free_alloc(blk_alloc); 362 return block; 363} 364 365static struct region *ext4_allocate_best_fit_partial(u32 len) 366{ 367 unsigned int i; 368 int j; 369 unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0; 370 u32 found_allocate_len = 0; 371 bool minimize = false; 372 struct block_group_info *bgs = aux_info.bgs; 373 struct region *reg; 374 375 for (i = 0; i < aux_info.groups; i++) { 376 for (j = 1; j < bgs[i].chunk_count; j++) { 377 u32 hole_start, hole_size; 378 hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len; 379 hole_size = bgs[i].chunks[j].block - hole_start; 380 if (hole_size == len) { 381 // Perfect fit i.e. right between 2 chunks no need to keep searching 382 found_bg = i; 383 found_prev_chunk = j - 1; 384 found_block = hole_start; 385 found_allocate_len = hole_size; 386 goto done; 387 } else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) { 388 found_bg = i; 389 found_prev_chunk = j - 1; 390 found_block = hole_start; 391 found_allocate_len = hole_size; 392 minimize = true; 393 } else if (!minimize) { 394 if (found_allocate_len < hole_size) { 395 found_bg = i; 396 found_prev_chunk = j - 1; 397 found_block = hole_start; 398 found_allocate_len = hole_size; 399 } 400 } 401 } 402 } 403 404 if (found_allocate_len == 0) { 405 error("failed to allocate %u blocks, out of space?", len); 406 return NULL; 407 } 408 if (found_allocate_len > len) found_allocate_len = len; 409done: 410 // reclaim allocated space in chunk 411 bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len; 412 if (reserve_blocks(&bgs[found_bg], 413 found_bg, 414 found_block, 415 found_allocate_len) < 0) { 416 error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg); 417 return NULL; 418 } 419 bgs[found_bg].data_blocks_used += found_allocate_len; 420 reg = malloc(sizeof(struct region)); 421 reg->block = found_block + bgs[found_bg].first_block; 422 reg->len = found_allocate_len; 423 reg->next = NULL; 424 reg->prev = NULL; 425 reg->bg = found_bg; 426 return reg; 427} 428 429static struct region *ext4_allocate_best_fit(u32 len) 430{ 431 struct region *first_reg = NULL; 432 struct region *prev_reg = NULL; 433 struct region *reg; 434 435 while (len > 0) { 436 reg = ext4_allocate_best_fit_partial(len); 437 if (reg == NULL) 438 return NULL; 439 440 if (first_reg == NULL) 441 first_reg = reg; 442 443 if (prev_reg) { 444 prev_reg->next = reg; 445 reg->prev = prev_reg; 446 } 447 448 prev_reg = reg; 449 len -= reg->len; 450 } 451 452 return first_reg; 453} 454 455/* Allocate len blocks. The blocks may be spread across multiple block groups, 456 and are returned in a linked list of the blocks in each block group. The 457 allocation algorithm is: 458 1. If the remaining allocation is larger than any available contiguous region, 459 allocate the largest contiguous region and loop 460 2. Otherwise, allocate the smallest contiguous region that it fits in 461*/ 462struct block_allocation *allocate_blocks(u32 len) 463{ 464 struct region *reg = ext4_allocate_best_fit(len); 465 466 if (reg == NULL) 467 return NULL; 468 469 struct block_allocation *alloc = create_allocation(); 470 alloc->list.first = reg; 471 while (reg->next != NULL) 472 reg = reg->next; 473 alloc->list.last = reg; 474 alloc->list.iter = alloc->list.first; 475 alloc->list.partial_iter = 0; 476 return alloc; 477} 478 479/* Returns the number of discontiguous regions used by an allocation */ 480int block_allocation_num_regions(struct block_allocation *alloc) 481{ 482 unsigned int i; 483 struct region *reg = alloc->list.first; 484 485 for (i = 0; reg != NULL; reg = reg->next) 486 i++; 487 488 return i; 489} 490 491int block_allocation_len(struct block_allocation *alloc) 492{ 493 unsigned int i; 494 struct region *reg = alloc->list.first; 495 496 for (i = 0; reg != NULL; reg = reg->next) 497 i += reg->len; 498 499 return i; 500} 501 502/* Returns the block number of the block'th block in an allocation */ 503u32 get_block(struct block_allocation *alloc, u32 block) 504{ 505 struct region *reg = alloc->list.iter; 506 block += alloc->list.partial_iter; 507 508 for (; reg; reg = reg->next) { 509 if (block < reg->len) 510 return reg->block + block; 511 block -= reg->len; 512 } 513 return EXT4_ALLOCATE_FAILED; 514} 515 516u32 get_oob_block(struct block_allocation *alloc, u32 block) 517{ 518 struct region *reg = alloc->oob_list.iter; 519 block += alloc->oob_list.partial_iter; 520 521 for (; reg; reg = reg->next) { 522 if (block < reg->len) 523 return reg->block + block; 524 block -= reg->len; 525 } 526 return EXT4_ALLOCATE_FAILED; 527} 528 529/* Gets the starting block and length in blocks of the first region 530 of an allocation */ 531void get_region(struct block_allocation *alloc, u32 *block, u32 *len) 532{ 533 *block = alloc->list.iter->block; 534 *len = alloc->list.iter->len - alloc->list.partial_iter; 535} 536 537/* Move to the next region in an allocation */ 538void get_next_region(struct block_allocation *alloc) 539{ 540 alloc->list.iter = alloc->list.iter->next; 541 alloc->list.partial_iter = 0; 542} 543 544/* Returns the number of free blocks in a block group */ 545u32 get_free_blocks(u32 bg) 546{ 547 return aux_info.bgs[bg].free_blocks; 548} 549 550int last_region(struct block_allocation *alloc) 551{ 552 return (alloc->list.iter == NULL); 553} 554 555void rewind_alloc(struct block_allocation *alloc) 556{ 557 alloc->list.iter = alloc->list.first; 558 alloc->list.partial_iter = 0; 559} 560 561static struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 562{ 563 struct region *reg = alloc->list.iter; 564 struct region *new; 565 struct region *tmp; 566 567 while (reg && len >= reg->len) { 568 len -= reg->len; 569 reg = reg->next; 570 } 571 572 if (reg == NULL && len > 0) 573 return NULL; 574 575 if (len > 0) { 576 new = malloc(sizeof(struct region)); 577 578 new->bg = reg->bg; 579 new->block = reg->block + len; 580 new->len = reg->len - len; 581 new->next = reg->next; 582 new->prev = reg; 583 584 reg->next = new; 585 reg->len = len; 586 587 tmp = alloc->list.iter; 588 alloc->list.iter = new; 589 return tmp; 590 } else { 591 return reg; 592 } 593} 594 595/* Splits an allocation into two allocations. The returned allocation will 596 point to the first half, and the original allocation ptr will point to the 597 second half. */ 598static struct region *split_allocation(struct block_allocation *alloc, u32 len) 599{ 600 /* First make sure there is a split at the current ptr */ 601 do_split_allocation(alloc, alloc->list.partial_iter); 602 603 /* Then split off len blocks */ 604 struct region *middle = do_split_allocation(alloc, len); 605 alloc->list.partial_iter = 0; 606 return middle; 607} 608 609/* Reserve the next blocks for oob data (indirect or extent blocks) */ 610int reserve_oob_blocks(struct block_allocation *alloc, int blocks) 611{ 612 struct region *oob = split_allocation(alloc, blocks); 613 struct region *next; 614 615 if (oob == NULL) 616 return -1; 617 618 while (oob && oob != alloc->list.iter) { 619 next = oob->next; 620 region_list_remove(&alloc->list, oob); 621 region_list_append(&alloc->oob_list, oob); 622 oob = next; 623 } 624 625 return 0; 626} 627 628static int advance_list_ptr(struct region_list *list, int blocks) 629{ 630 struct region *reg = list->iter; 631 632 while (reg != NULL && blocks > 0) { 633 if (reg->len > list->partial_iter + blocks) { 634 list->partial_iter += blocks; 635 return 0; 636 } 637 638 blocks -= (reg->len - list->partial_iter); 639 list->partial_iter = 0; 640 reg = reg->next; 641 } 642 643 if (blocks > 0) 644 return -1; 645 646 return 0; 647} 648 649/* Move the allocation pointer forward */ 650int advance_blocks(struct block_allocation *alloc, int blocks) 651{ 652 return advance_list_ptr(&alloc->list, blocks); 653} 654 655int advance_oob_blocks(struct block_allocation *alloc, int blocks) 656{ 657 return advance_list_ptr(&alloc->oob_list, blocks); 658} 659 660int append_oob_allocation(struct block_allocation *alloc, u32 len) 661{ 662 struct region *reg = ext4_allocate_best_fit(len); 663 664 if (reg == NULL) { 665 error("failed to allocate %d blocks", len); 666 return -1; 667 } 668 669 for (; reg; reg = reg->next) 670 region_list_append(&alloc->oob_list, reg); 671 672 return 0; 673} 674 675/* Returns an ext4_inode structure for an inode number */ 676struct ext4_inode *get_inode(u32 inode) 677{ 678 inode -= 1; 679 int bg = inode / info.inodes_per_group; 680 inode %= info.inodes_per_group; 681 682 allocate_bg_inode_table(&aux_info.bgs[bg]); 683 return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 684 info.inode_size); 685} 686 687struct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 688{ 689 struct ext4_xattr_header *block = xattr_list_find(inode); 690 if (block != NULL) 691 return block; 692 693 u32 block_num = allocate_block(); 694 block = calloc(info.block_size, 1); 695 if (block == NULL) { 696 error("get_xattr: failed to allocate %d", info.block_size); 697 return NULL; 698 } 699 700 block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 701 block->h_refcount = cpu_to_le32(1); 702 block->h_blocks = cpu_to_le32(1); 703 inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 704 inode->i_file_acl_lo = cpu_to_le32(block_num); 705 706 int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 707 if (result != 0) { 708 error("get_xattr: sparse_file_add_data failure %d", result); 709 free(block); 710 return NULL; 711 } 712 xattr_list_insert(inode, block); 713 return block; 714} 715 716/* Mark the first len inodes in a block group as used */ 717u32 reserve_inodes(int bg, u32 num) 718{ 719 unsigned int i; 720 u32 inode; 721 722 if (get_free_inodes(bg) < num) 723 return EXT4_ALLOCATE_FAILED; 724 725 for (i = 0; i < num; i++) { 726 inode = aux_info.bgs[bg].first_free_inode + i - 1; 727 aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 728 } 729 730 inode = aux_info.bgs[bg].first_free_inode; 731 732 aux_info.bgs[bg].first_free_inode += num; 733 aux_info.bgs[bg].free_inodes -= num; 734 735 return inode; 736} 737 738/* Returns the first free inode number 739 TODO: Inodes should be allocated in the block group of the data? */ 740u32 allocate_inode() 741{ 742 unsigned int bg; 743 u32 inode; 744 745 for (bg = 0; bg < aux_info.groups; bg++) { 746 inode = reserve_inodes(bg, 1); 747 if (inode != EXT4_ALLOCATE_FAILED) 748 return bg * info.inodes_per_group + inode; 749 } 750 751 return EXT4_ALLOCATE_FAILED; 752} 753 754/* Returns the number of free inodes in a block group */ 755u32 get_free_inodes(u32 bg) 756{ 757 return aux_info.bgs[bg].free_inodes; 758} 759 760/* Increments the directory count of the block group that contains inode */ 761void add_directory(u32 inode) 762{ 763 int bg = (inode - 1) / info.inodes_per_group; 764 aux_info.bgs[bg].used_dirs += 1; 765} 766 767/* Returns the number of inodes in a block group that are directories */ 768u16 get_directories(int bg) 769{ 770 return aux_info.bgs[bg].used_dirs; 771} 772 773/* Returns the flags for a block group */ 774u16 get_bg_flags(int bg) 775{ 776 return aux_info.bgs[bg].flags; 777} 778 779/* Frees the memory used by a linked list of allocation regions */ 780void free_alloc(struct block_allocation *alloc) 781{ 782 struct region *reg; 783 784 reg = alloc->list.first; 785 while (reg) { 786 struct region *next = reg->next; 787 free(reg); 788 reg = next; 789 } 790 791 reg = alloc->oob_list.first; 792 while (reg) { 793 struct region *next = reg->next; 794 free(reg); 795 reg = next; 796 } 797 798 free(alloc); 799} 800 801void reserve_bg_chunk(int bg, u32 start_block, u32 size) { 802 struct block_group_info *bgs = aux_info.bgs; 803 int chunk_count; 804 if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) { 805 bgs[bg].max_chunk_count *= 2; 806 bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region)); 807 if (!bgs[bg].chunks) 808 critical_error("realloc failed"); 809 } 810 chunk_count = bgs[bg].chunk_count; 811 bgs[bg].chunks[chunk_count].block = start_block; 812 bgs[bg].chunks[chunk_count].len = size; 813 bgs[bg].chunks[chunk_count].bg = bg; 814 bgs[bg].chunk_count++; 815} 816 817int reserve_blocks_for_allocation(struct block_allocation *alloc) { 818 struct region *reg; 819 struct block_group_info *bgs = aux_info.bgs; 820 821 if (!alloc) return 0; 822 reg = alloc->list.first; 823 while (reg != NULL) { 824 if (reserve_blocks(&bgs[reg->bg], reg->bg, reg->block - bgs[reg->bg].first_block, reg->len) < 0) { 825 return -1; 826 } 827 reg = reg->next; 828 } 829 return 0; 830} 831 832