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