allocate.c revision a6866eb4c6b88403683ac7e00a517820d2e1e810
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 * 89579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash * 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 20dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross#include <sparse/sparse.h> 21dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross 2233f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdio.h> 2333f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdlib.h> 2433f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 254df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct xattr_list_element { 264df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_inode *inode; 274df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *header; 284df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *next; 294df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich}; 304df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 31ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *create_allocation() 32ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 338aef66d2125af8de7672a12895276802fcc1948fColin Cross struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 348aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.first = NULL; 358aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = NULL; 368aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.first = NULL; 378aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.last = NULL; 388aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = NULL; 398aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.partial_iter = 0; 408aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.iter = NULL; 418aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.partial_iter = 0; 42bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker alloc->filename = NULL; 43bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker alloc->next = NULL; 448aef66d2125af8de7672a12895276802fcc1948fColin Cross return alloc; 45ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 46ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 474df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode) 484df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 494df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element; 504df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich for (element = aux_info.xattrs; element != NULL; element = element->next) { 514df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (element->inode == inode) 524df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return element->header; 534df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 544df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 554df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 564df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 574df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header) 584df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 594df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element)); 604df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->inode = inode; 614df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->header = header; 624df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->next = aux_info.xattrs; 634df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich aux_info.xattrs = element; 644df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 654df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 66ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void region_list_remove(struct region_list *list, struct region *reg) 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 68ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->prev) 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev->next = reg->next; 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->next) 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next->prev = reg->prev; 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 74ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == reg) 75ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg->next; 76ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->last == reg) 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg->prev; 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid region_list_append(struct region_list *list, struct region *reg) 85ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == NULL) { 87ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg; 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->iter = reg; 90ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 91ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last->next = reg; 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = list->last; 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 98ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 99ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 100ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#if 0 101ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_starting_from(struct region *reg) 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("%p: Blocks %d-%d (%d)\n", reg, 105bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker reg->block, reg->block + reg->len - 1, reg->len) 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 108ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 109ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_region_lists(struct block_allocation *alloc) { 110ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("Main list:\n"); 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->list.first); 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("OOB list:\n"); 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->oob_list.first); 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#endif 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1199579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid print_blocks(FILE* f, struct block_allocation *alloc, char separator) 120bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker{ 121bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker struct region *reg; 1229579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(' ', f); 123bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker for (reg = alloc->list.first; reg; reg = reg->next) { 124bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker if (reg->len == 1) { 1259579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d", reg->block); 126bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } else { 1279579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1); 128bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 1299579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(separator, f); 130bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 131bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker fputc('\n', f); 132bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker} 133bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid append_region(struct block_allocation *alloc, 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block, u32 len, int bg_num) 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 1378aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 1388aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 1398aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->block = block; 1408aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->len = len; 1418aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->bg = bg_num; 1428aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->next = NULL; 143ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1448aef66d2125af8de7672a12895276802fcc1948fColin Cross region_list_append(&alloc->list, reg); 145ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 146ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 147ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void allocate_bg_inode_table(struct block_group_info *bg) 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table != NULL) 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block + 2; 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 15522742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table == NULL) 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 161782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->inode_table, 162f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross aux_info.inode_table_blocks * info.block_size, block); 163107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 16456497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross bg->flags &= ~EXT4_BG_INODE_UNINIT; 165107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall} 166107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap[bit / 8] & 1 << (bit % 8)) 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 1; 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] |= 1 << (bit % 8); 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 178ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int ret = bitmap[bit / 8]; 179ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] = 0xFF; 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ret; 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Marks a the first num_blocks blocks in a block group as used, and accounts 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for them in the block group free block info. */ 185a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyashstatic int reserve_blocks(struct block_group_info *bg, u32 bg_num, u32 start, u32 num) 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i = 0; 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = start; 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num && block % 8 != 0; i++, block++) { 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 192a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i + 8 <= (num & ~7); i += 8, block += 8) { 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_8_bits(bg->block_bitmap, block)) { 199a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i < num; i++, block++) { 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 206a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 207ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks -= num; 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2169579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashstatic void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks) 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num_blocks; i++, block--) 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks += num_blocks; 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reduces an existing allocation by len blocks by return the last blocks 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross to the free pool in their block group. Assumes that the blocks being 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross returned were the last ones allocated out of the block group */ 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid reduce_allocation(struct block_allocation *alloc, u32 len) 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len) { 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *last_reg = alloc->list.last; 2319579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bg = &aux_info.bgs[last_reg->bg]; 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (last_reg->len > len) { 2349579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len); 235ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross last_reg->len -= len; 236ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = 0; 237ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 238a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross struct region *reg = alloc->list.last->prev; 2399579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len); 240ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= last_reg->len; 241a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross if (reg) { 242ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 243a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } else { 244a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.first = NULL; 245a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.last = NULL; 246a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.iter = NULL; 247a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.partial_iter = 0; 248a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } 249ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(last_reg); 250ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 251ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 252ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 253ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 254ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void init_bg(struct block_group_info *bg, unsigned int i) 255ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 256ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks = 2 + aux_info.inode_table_blocks; 257ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 258ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->has_superblock = ext4_bg_has_super_block(i); 259ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 260ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 26122742ce739a046a079b2e1b03342a25472dfa352Colin Cross header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 262ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 263ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->bitmaps = calloc(info.block_size, 2); 264ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap = bg->bitmaps; 265ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_bitmap = bg->bitmaps + info.block_size; 266ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 267ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->header_blocks = header_blocks; 268ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 269ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 270ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block; 271ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 27222742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 273782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 274f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross block); 275ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 276ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->data_blocks_used = 0; 277ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks = info.blocks_per_group; 278ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_inodes = info.inodes_per_group; 279ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_inode = 1; 280468e7007b1151915a14800cf9d55a5f6f3644de3Theodore Ts'o bg->flags = 0; 281ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2829579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunk_count = 0; 2839579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->max_chunk_count = 1; 2849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region)); 2859579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 286a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(bg, i, 0, bg->header_blocks) < 0) 287ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 2889579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty starting delimiter chunk 2899579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, bg->header_blocks, 0); 290ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 29117de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 29217de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 293a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash reserve_blocks(bg, i, info.blocks_per_group - overrun, overrun); 2949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty ending delimiter chunk 2959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - overrun, 0); 2969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else { 2979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - 1, 0); 29817de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall } 2999579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 300ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 301ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 302ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_init() 303ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 304ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 305ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 306ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 307ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs == NULL) 308ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 309ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 310ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) 311ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross init_bg(&aux_info.bgs[i], i); 312ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 313ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 314ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_free() 315ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 316ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 317ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 318ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 319ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].bitmaps); 320ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].inode_table); 321ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 322ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs); 323ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 324ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 325ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate a single block and return its block number */ 326ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_block() 327ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 3289579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 block; 3299579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_allocation *blk_alloc = allocate_blocks(1); 3309579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!blk_alloc) { 3319579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return EXT4_ALLOCATE_FAILED; 332ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 3339579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash block = blk_alloc->list.first->block; 3349579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_alloc(blk_alloc); 3359579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return block; 336ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 337ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 338eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit_partial(u32 len) 339ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 3409579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash unsigned int i, j; 3419579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0; 3429579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 found_allocate_len = 0; 3439579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bool minimize = false; 3449579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 3459579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 34618785a86a30135ac65b88db9886bfc22d6608849Mohamad Ayyash 347ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 3489579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash for (j = 1; j < bgs[i].chunk_count; j++) { 3499579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 hole_start, hole_size; 3509579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len; 3519579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_size = bgs[i].chunks[j].block - hole_start; 3529579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (hole_size == len) { 3539579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Perfect fit i.e. right between 2 chunks no need to keep searching 3549579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3559579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3569579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3579579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash goto done; 3599579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) { 3609579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3619579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3629579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3639579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3649579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash minimize = true; 3659579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (!minimize) { 3669579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len < hole_size) { 3679579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3689579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3699579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3709579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3719579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 3729579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 373eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 374eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 375ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 3769579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len == 0) { 377eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross error("failed to allocate %u blocks, out of space?", len); 3789579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 379ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 3809579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len > len) found_allocate_len = len; 3819579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashdone: 3829579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // reclaim allocated space in chunk 3839579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len; 3849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (reserve_blocks(&bgs[found_bg], 385a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash found_bg, 3869579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block, 3879579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len) < 0) { 3889579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg); 3899579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 3909579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 3919579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].data_blocks_used += found_allocate_len; 3929579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = malloc(sizeof(struct region)); 3939579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->block = found_block + bgs[found_bg].first_block; 3949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->len = found_allocate_len; 3959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->next = NULL; 3969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->prev = NULL; 3979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->bg = found_bg; 3989579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return reg; 399ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 400ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 401eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit(u32 len) 402ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 403ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first_reg = NULL; 404ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *prev_reg = NULL; 405ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 406ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 407ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len > 0) { 408eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross reg = ext4_allocate_best_fit_partial(len); 409ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 410ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 411ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 412ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (first_reg == NULL) 413ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross first_reg = reg; 414ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 415ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (prev_reg) { 416ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg->next = reg; 417ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = prev_reg; 418ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 419ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 420ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg = reg; 421ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 422ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 423ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 424ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return first_reg; 425ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 426ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 427ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate len blocks. The blocks may be spread across multiple block groups, 428ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and are returned in a linked list of the blocks in each block group. The 429ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocation algorithm is: 4309579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 1. If the remaining allocation is larger than any available contiguous region, 4319579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash allocate the largest contiguous region and loop 4329579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 2. Otherwise, allocate the smallest contiguous region that it fits in 433ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross*/ 434ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *allocate_blocks(u32 len) 435ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 436eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 437ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 438ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 439ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 440ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 441ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = create_allocation(); 442ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = reg; 4439579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg->next != NULL) 4449579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 4458aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = reg; 446ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 447ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 448ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 449ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 450ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 451ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of discontiguous regions used by an allocation */ 452ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_num_regions(struct block_allocation *alloc) 453ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 454ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 455ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 456ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 457ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 458ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i++; 459ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 460ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 461ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 462ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 463ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_len(struct block_allocation *alloc) 464ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 465ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 4668aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.first; 467ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 468ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 469ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i += reg->len; 470ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 471ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 472ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 473ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 474ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the block number of the block'th block in an allocation */ 475ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_block(struct block_allocation *alloc, u32 block) 476ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 4778aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 4788aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->list.partial_iter; 479ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 4808aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 481ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 482ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 483ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 484ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 485ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 486ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 487ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 488ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_oob_block(struct block_allocation *alloc, u32 block) 489ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 4908aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->oob_list.iter; 4918aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->oob_list.partial_iter; 492ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 4938aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 494ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 495ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 496ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 497ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 498ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 499ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 500ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 501ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Gets the starting block and length in blocks of the first region 502ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross of an allocation */ 503ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 504ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 505ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *block = alloc->list.iter->block; 506ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *len = alloc->list.iter->len - alloc->list.partial_iter; 507ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 508ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 509ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move to the next region in an allocation */ 510ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_next_region(struct block_allocation *alloc) 511ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 512ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.iter->next; 513ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 514ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 515ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 516ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free blocks in a block group */ 517ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_blocks(u32 bg) 518ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 519ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_blocks; 520ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 521ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 522ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint last_region(struct block_allocation *alloc) 523ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 524ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (alloc->list.iter == NULL); 525ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 526ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 527ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid rewind_alloc(struct block_allocation *alloc) 528ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 529ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 530ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 531ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 532ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 533ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 534ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5358aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5368aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *new; 5378aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *tmp; 538ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5398aef66d2125af8de7672a12895276802fcc1948fColin Cross while (reg && len >= reg->len) { 540ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 541ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 542ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 543ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 544ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL && len > 0) 545ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 546ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 547ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len > 0) { 548ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new = malloc(sizeof(struct region)); 549ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 550ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->bg = reg->bg; 551ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->block = reg->block + len; 552ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->len = reg->len - len; 553ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->next = reg->next; 554ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->prev = reg; 555ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 556ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = new; 557ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 558ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 559ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross tmp = alloc->list.iter; 5608aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = new; 561ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return tmp; 562ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 563ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 564ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 565ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 566ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 567ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Splits an allocation into two allocations. The returned allocation will 568ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross point to the first half, and the original allocation ptr will point to the 569ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross second half. */ 570ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 571ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 572ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* First make sure there is a split at the current ptr */ 573ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross do_split_allocation(alloc, alloc->list.partial_iter); 574ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 575ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Then split off len blocks */ 576ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *middle = do_split_allocation(alloc, len); 577ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 578ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return middle; 579ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 580ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 581ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reserve the next blocks for oob data (indirect or extent blocks) */ 582ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 583ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 584ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *oob = split_allocation(alloc, blocks); 5858aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *next; 586ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 587ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (oob == NULL) 588ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 589ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 590ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (oob && oob != alloc->list.iter) { 591ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross next = oob->next; 592ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_remove(&alloc->list, oob); 593ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, oob); 594ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oob = next; 595ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 596ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 597ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 598ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 599ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 600ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int advance_list_ptr(struct region_list *list, int blocks) 601ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 602ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = list->iter; 603ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 604ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg != NULL && blocks > 0) { 605ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->len > list->partial_iter + blocks) { 606ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter += blocks; 607ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 608ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 609ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 610ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks -= (reg->len - list->partial_iter); 611ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 612ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 613ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 614ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 615ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (blocks > 0) 616ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 617ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 618ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 619ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 620ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 621ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move the allocation pointer forward */ 622ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_blocks(struct block_allocation *alloc, int blocks) 623ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 624ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->list, blocks); 625ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 626ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 627ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_oob_blocks(struct block_allocation *alloc, int blocks) 628ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 629ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->oob_list, blocks); 630ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 631ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 632ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint append_oob_allocation(struct block_allocation *alloc, u32 len) 633ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 634eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 635ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 636ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) { 637ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks", len); 638ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 639ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 640ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 641ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) 642ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, reg); 643ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 644ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 645ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 646ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 647ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns an ext4_inode structure for an inode number */ 648ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct ext4_inode *get_inode(u32 inode) 649ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 650ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode -= 1; 651ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = inode / info.inodes_per_group; 652ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode %= info.inodes_per_group; 653ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 654ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocate_bg_inode_table(&aux_info.bgs[bg]); 6558aef66d2125af8de7672a12895276802fcc1948fColin Cross return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6568aef66d2125af8de7672a12895276802fcc1948fColin Cross info.inode_size); 657ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 658ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 6594df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 6604df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 6614df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *block = xattr_list_find(inode); 6624df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block != NULL) 6634df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 6644df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 6654df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich u32 block_num = allocate_block(); 6664df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block = calloc(info.block_size, 1); 6674df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block == NULL) { 6684df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: failed to allocate %d", info.block_size); 6694df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 6704df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 6714df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 6724df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 6734df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_refcount = cpu_to_le32(1); 6744df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_blocks = cpu_to_le32(1); 6754df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 6764df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_file_acl_lo = cpu_to_le32(block_num); 6774df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 678782879ab61fe825835a9c6a701f91aa7d305acefColin Cross int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 6794df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (result != 0) { 6804df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: sparse_file_add_data failure %d", result); 6814df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich free(block); 6824df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 6834df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 6844df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich xattr_list_insert(inode, block); 6854df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 6864df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 6874df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 688ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Mark the first len inodes in a block group as used */ 689ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 reserve_inodes(int bg, u32 num) 690ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 691ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 692ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 693ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 694ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_inodes(bg) < num) 695ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 696ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 697ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num; i++) { 698ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode + i - 1; 699ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 700ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 701ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 702ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode; 703ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 704ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].first_free_inode += num; 705ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].free_inodes -= num; 706ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 707ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return inode; 708ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 709ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 710ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the first free inode number 711ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross TODO: Inodes should be allocated in the block group of the data? */ 712ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_inode() 713ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 714ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int bg; 715ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 716ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 717ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (bg = 0; bg < aux_info.groups; bg++) { 718ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = reserve_inodes(bg, 1); 719ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (inode != EXT4_ALLOCATE_FAILED) 720ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg * info.inodes_per_group + inode; 721ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 722ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 723ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 724ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 725ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 726ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free inodes in a block group */ 727ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_inodes(u32 bg) 728ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 729ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_inodes; 730ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 731ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 732ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Increments the directory count of the block group that contains inode */ 733ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid add_directory(u32 inode) 734ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 735ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = (inode - 1) / info.inodes_per_group; 736ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].used_dirs += 1; 737ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 738ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 739ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of inodes in a block group that are directories */ 740ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu16 get_directories(int bg) 741ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 742ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].used_dirs; 743ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 744ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 74556497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross/* Returns the flags for a block group */ 74656497f28bd20001dd5f931208e8d948cf2f81b2fColin Crossu16 get_bg_flags(int bg) 74756497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross{ 74856497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross return aux_info.bgs[bg].flags; 74956497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross} 75056497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross 751ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Frees the memory used by a linked list of allocation regions */ 752ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid free_alloc(struct block_allocation *alloc) 753ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 754ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 755ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 756ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->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 reg = alloc->oob_list.first; 764ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 765ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 766ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 767ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 768ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 769ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 770ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(alloc); 771ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 7729579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 7739579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid reserve_bg_chunk(int bg, u32 start_block, u32 size) { 7749579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 7759579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash int chunk_count; 7769579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) { 7779579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].max_chunk_count *= 2; 7789579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region)); 7799579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!bgs[bg].chunks) 7809579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash critical_error("realloc failed"); 7819579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 7829579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash chunk_count = bgs[bg].chunk_count; 7839579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].block = start_block; 7849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].len = size; 7859579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].bg = bg; 7869579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunk_count++; 7879579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 7889579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 7899579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashint reserve_blocks_for_allocation(struct block_allocation *alloc) { 7909579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 7919579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 7929579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 7939579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!alloc) return 0; 7949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = alloc->list.first; 7959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg != NULL) { 796a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(&bgs[reg->bg], reg->bg, reg->block - bgs[reg->bg].first_block, reg->len) < 0) { 7979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return -1; 798a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash } 7999579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 8009579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 8019579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return 0; 8029579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 8039579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 804