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