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