ext4_utils/allocate.c

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