allocate.c revision f7124d6c955c0453361b0ff47c5c94619e68087f
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 100f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyashvoid region_list_merge(struct region_list *list1, struct region_list *list2) 101f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash{ 102f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash if (list1->first == NULL) { 103f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->first = list2->first; 104f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last = list2->last; 105f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->iter = list2->first; 106f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->partial_iter = 0; 107f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->first->prev = NULL; 108f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash } else { 109f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last->next = list2->first; 110f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list2->first->prev = list1->last; 111f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last = list2->last; 112f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash } 113f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash} 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#if 0 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_starting_from(struct region *reg) 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("%p: Blocks %d-%d (%d)\n", reg, 119bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker reg->block, reg->block + reg->len - 1, reg->len) 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_region_lists(struct block_allocation *alloc) { 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("Main list:\n"); 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->list.first); 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 128ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("OOB list:\n"); 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->oob_list.first); 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#endif 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1339579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid print_blocks(FILE* f, struct block_allocation *alloc, char separator) 134bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker{ 135bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker struct region *reg; 1369579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(' ', f); 137bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker for (reg = alloc->list.first; reg; reg = reg->next) { 138bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker if (reg->len == 1) { 1399579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d", reg->block); 140bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } else { 1419579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1); 142bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 1439579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(separator, f); 144bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 145bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker fputc('\n', f); 146bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker} 147bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid append_region(struct block_allocation *alloc, 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block, u32 len, int bg_num) 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 1518aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 1528aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 1538aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->block = block; 1548aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->len = len; 1558aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->bg = bg_num; 1568aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->next = NULL; 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1588aef66d2125af8de7672a12895276802fcc1948fColin Cross region_list_append(&alloc->list, reg); 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void allocate_bg_inode_table(struct block_group_info *bg) 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table != NULL) 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block + 2; 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 16922742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table == NULL) 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 175782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->inode_table, 176f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross aux_info.inode_table_blocks * info.block_size, block); 177107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 17856497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross bg->flags &= ~EXT4_BG_INODE_UNINIT; 179107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall} 180107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap[bit / 8] & 1 << (bit % 8)) 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 1; 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] |= 1 << (bit % 8); 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int ret = bitmap[bit / 8]; 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] = 0xFF; 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ret; 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Marks a the first num_blocks blocks in a block group as used, and accounts 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for them in the block group free block info. */ 199a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyashstatic int reserve_blocks(struct block_group_info *bg, u32 bg_num, u32 start, u32 num) 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i = 0; 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = start; 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num && block % 8 != 0; 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 for (; i + 8 <= (num & ~7); i += 8, block += 8) { 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_8_bits(bg->block_bitmap, block)) { 213a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i < num; i++, block++) { 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 220a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks -= num; 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2309579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashstatic void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks) 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num_blocks; i++, block--) 234ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 235ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks += num_blocks; 236ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 237ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 238ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reduces an existing allocation by len blocks by return the last blocks 239ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross to the free pool in their block group. Assumes that the blocks being 240ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross returned were the last ones allocated out of the block group */ 241ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid reduce_allocation(struct block_allocation *alloc, u32 len) 242ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 243ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len) { 244ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *last_reg = alloc->list.last; 2459579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bg = &aux_info.bgs[last_reg->bg]; 246ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 247ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (last_reg->len > len) { 2489579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len); 249ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross last_reg->len -= len; 250ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = 0; 251ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 252a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross struct region *reg = alloc->list.last->prev; 2539579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len); 254ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= last_reg->len; 255a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross if (reg) { 256ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 257a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } else { 258a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.first = NULL; 259a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.last = NULL; 260a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.iter = NULL; 261a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.partial_iter = 0; 262a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } 263ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(last_reg); 264ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 265ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 266ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 267ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 268ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void init_bg(struct block_group_info *bg, unsigned int i) 269ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 270ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks = 2 + aux_info.inode_table_blocks; 271ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 272ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->has_superblock = ext4_bg_has_super_block(i); 273ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 274ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 27522742ce739a046a079b2e1b03342a25472dfa352Colin Cross header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 276ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 277ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->bitmaps = calloc(info.block_size, 2); 278ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap = bg->bitmaps; 279ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_bitmap = bg->bitmaps + info.block_size; 280ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 281ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->header_blocks = header_blocks; 282ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 283ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 284ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block; 285ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 28622742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 287782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 288f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross block); 289ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 290ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->data_blocks_used = 0; 291ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks = info.blocks_per_group; 292ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_inodes = info.inodes_per_group; 293ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_inode = 1; 294dedf8f9705df13e1fd07d3f754216d34725bb269Mohamad Ayyash bg->flags = EXT4_BG_INODE_UNINIT; 295ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunk_count = 0; 2979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->max_chunk_count = 1; 2989579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region)); 2999579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 300a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(bg, i, 0, bg->header_blocks) < 0) 301ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 3029579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty starting delimiter chunk 3039579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, bg->header_blocks, 0); 304ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 30517de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 30617de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 307a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash reserve_blocks(bg, i, info.blocks_per_group - overrun, overrun); 3089579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty ending delimiter chunk 3099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - overrun, 0); 3109579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else { 3119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - 1, 0); 31217de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall } 3139579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 314ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 315ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 316ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_init() 317ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 318ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 319ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 320ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 321ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs == NULL) 322ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 323ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 324ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) 325ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross init_bg(&aux_info.bgs[i], i); 326ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 327ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 328ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_free() 329ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 330ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 331ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 332ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 333ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].bitmaps); 334ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].inode_table); 335ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 336ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs); 337ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 338ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 339ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate a single block and return its block number */ 340ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_block() 341ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 3429579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 block; 3439579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_allocation *blk_alloc = allocate_blocks(1); 3449579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!blk_alloc) { 3459579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return EXT4_ALLOCATE_FAILED; 346ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 3479579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash block = blk_alloc->list.first->block; 3489579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_alloc(blk_alloc); 3499579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return block; 350ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 351ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 352eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit_partial(u32 len) 353ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 3549579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash unsigned int i, j; 3559579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0; 3569579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 found_allocate_len = 0; 3579579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bool minimize = false; 3589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 3599579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 36018785a86a30135ac65b88db9886bfc22d6608849Mohamad Ayyash 361ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 3629579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash for (j = 1; j < bgs[i].chunk_count; j++) { 3639579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 hole_start, hole_size; 3649579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len; 3659579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_size = bgs[i].chunks[j].block - hole_start; 3669579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (hole_size == len) { 3679579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Perfect fit i.e. right between 2 chunks no need to keep searching 3689579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3699579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3709579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3719579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3729579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash goto done; 3739579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) { 3749579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3759579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3769579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3779579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3789579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash minimize = true; 3799579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (!minimize) { 3809579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len < hole_size) { 3819579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3829579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3839579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3859579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 3869579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 387eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 388eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 389ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 3909579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len == 0) { 391eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross error("failed to allocate %u blocks, out of space?", len); 3929579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 393ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 3949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len > len) found_allocate_len = len; 3959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashdone: 3969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // reclaim allocated space in chunk 3979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len; 3989579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (reserve_blocks(&bgs[found_bg], 399a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash found_bg, 4009579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block, 4019579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len) < 0) { 4029579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg); 4039579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 4049579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 4059579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].data_blocks_used += found_allocate_len; 4069579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = malloc(sizeof(struct region)); 4079579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->block = found_block + bgs[found_bg].first_block; 4089579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->len = found_allocate_len; 4099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->next = NULL; 4109579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->prev = NULL; 4119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->bg = found_bg; 4129579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return reg; 413ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 414ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 415eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit(u32 len) 416ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 417ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first_reg = NULL; 418ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *prev_reg = NULL; 419ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 420ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 421ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len > 0) { 422eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross reg = ext4_allocate_best_fit_partial(len); 423ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 424ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 425ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 426ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (first_reg == NULL) 427ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross first_reg = reg; 428ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 429ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (prev_reg) { 430ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg->next = reg; 431ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = prev_reg; 432ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 433ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 434ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg = reg; 435ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 436ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 437ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 438ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return first_reg; 439ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 440ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 441ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate len blocks. The blocks may be spread across multiple block groups, 442ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and are returned in a linked list of the blocks in each block group. The 443ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocation algorithm is: 4449579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 1. If the remaining allocation is larger than any available contiguous region, 4459579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash allocate the largest contiguous region and loop 4469579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 2. Otherwise, allocate the smallest contiguous region that it fits in 447ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross*/ 448ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *allocate_blocks(u32 len) 449ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 450eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 451ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 452ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 453ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 454ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 455ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = create_allocation(); 456ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = reg; 4579579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg->next != NULL) 4589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 4598aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = reg; 460ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 461ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 462ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 463ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 464ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 465ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of discontiguous regions used by an allocation */ 466ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_num_regions(struct block_allocation *alloc) 467ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 468ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 469ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 470ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 471ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 472ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i++; 473ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 474ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 475ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 476ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 477ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_len(struct block_allocation *alloc) 478ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 479ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 4808aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.first; 481ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 482ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 483ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i += reg->len; 484ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 485ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 486ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 487ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 488ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the block number of the block'th block in an allocation */ 489ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_block(struct block_allocation *alloc, u32 block) 490ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 4918aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 4928aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->list.partial_iter; 493ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 4948aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 495ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 496ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 497ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 498ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 499ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 500ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 501ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 502ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_oob_block(struct block_allocation *alloc, u32 block) 503ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5048aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->oob_list.iter; 5058aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->oob_list.partial_iter; 506ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5078aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 508ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 509ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 510ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 511ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 512ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 513ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 514ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 515ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Gets the starting block and length in blocks of the first region 516ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross of an allocation */ 517ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 518ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 519ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *block = alloc->list.iter->block; 520ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *len = alloc->list.iter->len - alloc->list.partial_iter; 521ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 522ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 523ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move to the next region in an allocation */ 524ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_next_region(struct block_allocation *alloc) 525ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 526ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.iter->next; 527ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 528ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 529ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 530ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free blocks in a block group */ 531ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_blocks(u32 bg) 532ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 533ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_blocks; 534ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 535ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 536ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint last_region(struct block_allocation *alloc) 537ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 538ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (alloc->list.iter == NULL); 539ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 540ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 541ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid rewind_alloc(struct block_allocation *alloc) 542ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 543ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 544ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 545ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 546ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 547ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 548ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5498aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5508aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *new; 5518aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *tmp; 552ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5538aef66d2125af8de7672a12895276802fcc1948fColin Cross while (reg && len >= reg->len) { 554ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 555ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 556ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 557ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 558ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL && len > 0) 559ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 560ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 561ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len > 0) { 562ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new = malloc(sizeof(struct region)); 563ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 564ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->bg = reg->bg; 565ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->block = reg->block + len; 566ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->len = reg->len - len; 567ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->next = reg->next; 568ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->prev = reg; 569ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 570ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = new; 571ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 572ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 573ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross tmp = alloc->list.iter; 5748aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = new; 575ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return tmp; 576ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 577ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 578ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 579ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 580ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 581ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Splits an allocation into two allocations. The returned allocation will 582ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross point to the first half, and the original allocation ptr will point to the 583ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross second half. */ 584ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 585ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 586ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* First make sure there is a split at the current ptr */ 587ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross do_split_allocation(alloc, alloc->list.partial_iter); 588ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 589ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Then split off len blocks */ 590ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *middle = do_split_allocation(alloc, len); 591ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 592ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return middle; 593ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 594ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 595ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reserve the next blocks for oob data (indirect or extent blocks) */ 596ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 597ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 598ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *oob = split_allocation(alloc, blocks); 5998aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *next; 600ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 601ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (oob == NULL) 602ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 603ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 604ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (oob && oob != alloc->list.iter) { 605ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross next = oob->next; 606ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_remove(&alloc->list, oob); 607ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, oob); 608ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oob = next; 609ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 610ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 611ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 612ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 613ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 614ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int advance_list_ptr(struct region_list *list, int blocks) 615ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 616ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = list->iter; 617ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 618ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg != NULL && blocks > 0) { 619ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->len > list->partial_iter + blocks) { 620ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter += blocks; 621ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 622ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 623ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 624ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks -= (reg->len - list->partial_iter); 625ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 626ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 627ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 628ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 629ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (blocks > 0) 630ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 631ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 632ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 633ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 634ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 635ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move the allocation pointer forward */ 636ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_blocks(struct block_allocation *alloc, int blocks) 637ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 638ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->list, blocks); 639ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 640ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 641ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_oob_blocks(struct block_allocation *alloc, int blocks) 642ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 643ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->oob_list, blocks); 644ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 645ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 646ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint append_oob_allocation(struct block_allocation *alloc, u32 len) 647ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 648eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 649ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 650ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) { 651ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks", len); 652ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 653ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 654ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 655ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) 656ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, reg); 657ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 658ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 659ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 660ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 661ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns an ext4_inode structure for an inode number */ 662ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct ext4_inode *get_inode(u32 inode) 663ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 664ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode -= 1; 665ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = inode / info.inodes_per_group; 666ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode %= info.inodes_per_group; 667ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 668ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocate_bg_inode_table(&aux_info.bgs[bg]); 6698aef66d2125af8de7672a12895276802fcc1948fColin Cross return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6708aef66d2125af8de7672a12895276802fcc1948fColin Cross info.inode_size); 671ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 672ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 6734df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 6744df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 6754df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *block = xattr_list_find(inode); 6764df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block != NULL) 6774df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 6784df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 6794df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich u32 block_num = allocate_block(); 6804df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block = calloc(info.block_size, 1); 6814df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block == NULL) { 6824df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: failed to allocate %d", info.block_size); 6834df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 6844df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 6854df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 6864df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 6874df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_refcount = cpu_to_le32(1); 6884df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_blocks = cpu_to_le32(1); 6894df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 6904df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_file_acl_lo = cpu_to_le32(block_num); 6914df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 692782879ab61fe825835a9c6a701f91aa7d305acefColin Cross int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 6934df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (result != 0) { 6944df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: sparse_file_add_data failure %d", result); 6954df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich free(block); 6964df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 6974df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 6984df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich xattr_list_insert(inode, block); 6994df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 7004df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 7014df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 702ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Mark the first len inodes in a block group as used */ 703ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 reserve_inodes(int bg, u32 num) 704ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 705ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 706ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 707ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 708ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_inodes(bg) < num) 709ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 710ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 711ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num; i++) { 712ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode + i - 1; 713ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 714ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 715ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 716ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode; 717ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 718ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].first_free_inode += num; 719ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].free_inodes -= num; 720ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 721ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return inode; 722ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 723ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 724ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the first free inode number 725ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross TODO: Inodes should be allocated in the block group of the data? */ 726ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_inode() 727ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 728ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int bg; 729ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 730ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 731ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (bg = 0; bg < aux_info.groups; bg++) { 732ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = reserve_inodes(bg, 1); 733ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (inode != EXT4_ALLOCATE_FAILED) 734ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg * info.inodes_per_group + inode; 735ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 736ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 737ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 738ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 739ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 740ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free inodes in a block group */ 741ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_inodes(u32 bg) 742ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 743ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_inodes; 744ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 745ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 746ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Increments the directory count of the block group that contains inode */ 747ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid add_directory(u32 inode) 748ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 749ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = (inode - 1) / info.inodes_per_group; 750ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].used_dirs += 1; 751ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 752ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 753ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of inodes in a block group that are directories */ 754ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu16 get_directories(int bg) 755ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 756ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].used_dirs; 757ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 758ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 75956497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross/* Returns the flags for a block group */ 76056497f28bd20001dd5f931208e8d948cf2f81b2fColin Crossu16 get_bg_flags(int bg) 76156497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross{ 76256497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross return aux_info.bgs[bg].flags; 76356497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross} 76456497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross 765ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Frees the memory used by a linked list of allocation regions */ 766ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid free_alloc(struct block_allocation *alloc) 767ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 768ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 769ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 770ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->list.first; 771ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 772ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 773ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 774ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 775ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 776ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 777ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->oob_list.first; 778ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 779ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 780ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 781ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 782ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 783ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 784ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(alloc); 785ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 7869579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 7879579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid reserve_bg_chunk(int bg, u32 start_block, u32 size) { 7889579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 7899579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash int chunk_count; 7909579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) { 7919579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].max_chunk_count *= 2; 7929579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region)); 7939579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!bgs[bg].chunks) 7949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash critical_error("realloc failed"); 7959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 7969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash chunk_count = bgs[bg].chunk_count; 7979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].block = start_block; 7989579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].len = size; 7999579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].bg = bg; 8009579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunk_count++; 8019579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 8029579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 8039579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashint reserve_blocks_for_allocation(struct block_allocation *alloc) { 8049579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 8059579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 8069579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 8079579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!alloc) return 0; 8089579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = alloc->list.first; 8099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg != NULL) { 810a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(&bgs[reg->bg], reg->bg, reg->block - bgs[reg->bg].first_block, reg->len) < 0) { 8119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return -1; 812a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash } 8139579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 8149579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 8159579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return 0; 8169579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 8179579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 818