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