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