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