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