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 "allocate.h" 18ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1933f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdio.h> 2033f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdlib.h> 2133f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 2206ca811e9297e28f43d65f30493df88862ff09c1Tao Bao#include <sparse/sparse.h> 2306ca811e9297e28f43d65f30493df88862ff09c1Tao Bao 2406ca811e9297e28f43d65f30493df88862ff09c1Tao Bao#include "ext4_utils/ext4_utils.h" 2506ca811e9297e28f43d65f30493df88862ff09c1Tao Bao 264df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct xattr_list_element { 274df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_inode *inode; 284df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *header; 294df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *next; 304df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich}; 314df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 32ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *create_allocation() 33ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 348aef66d2125af8de7672a12895276802fcc1948fColin Cross struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 358aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.first = NULL; 368aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = NULL; 378aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.first = NULL; 388aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.last = NULL; 398aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = NULL; 408aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.partial_iter = 0; 418aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.iter = NULL; 428aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.partial_iter = 0; 43bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker alloc->filename = NULL; 44bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker alloc->next = NULL; 458aef66d2125af8de7672a12895276802fcc1948fColin Cross return alloc; 46ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 47ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 484df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode) 494df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 504df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element; 514df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich for (element = aux_info.xattrs; element != NULL; element = element->next) { 524df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (element->inode == inode) 534df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return element->header; 544df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 554df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 564df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 574df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 584df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header) 594df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 604df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element)); 614df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->inode = inode; 624df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->header = header; 634df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->next = aux_info.xattrs; 644df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich aux_info.xattrs = element; 654df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 664df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void region_list_remove(struct region_list *list, struct region *reg) 68ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->prev) 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev->next = reg->next; 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->next) 73ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next->prev = reg->prev; 74ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 75ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == reg) 76ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg->next; 77ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 78ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->last == reg) 79ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg->prev; 80ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 83ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 84ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 859579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid region_list_append(struct region_list *list, struct region *reg) 86ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 87ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == NULL) { 88ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg; 89ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 90ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->iter = reg; 91ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 92ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 93ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 94ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last->next = reg; 95ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = list->last; 96ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 97ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 98ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 99ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 100ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 101f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyashvoid region_list_merge(struct region_list *list1, struct region_list *list2) 102f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash{ 103f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash if (list1->first == NULL) { 104f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->first = list2->first; 105f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last = list2->last; 106f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->iter = list2->first; 107f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->partial_iter = 0; 108f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->first->prev = NULL; 109f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash } else { 110f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last->next = list2->first; 111f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list2->first->prev = list1->last; 112f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash list1->last = list2->last; 113f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash } 114f7124d6c955c0453361b0ff47c5c94619e68087fMohamad Ayyash} 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#if 0 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_starting_from(struct region *reg) 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("%p: Blocks %d-%d (%d)\n", reg, 120bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker reg->block, reg->block + reg->len - 1, reg->len) 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_region_lists(struct block_allocation *alloc) { 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("Main list:\n"); 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->list.first); 128ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("OOB list:\n"); 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->oob_list.first); 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#endif 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1349579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid print_blocks(FILE* f, struct block_allocation *alloc, char separator) 135bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker{ 136bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker struct region *reg; 1379579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(' ', f); 138bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker for (reg = alloc->list.first; reg; reg = reg->next) { 139bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker if (reg->len == 1) { 1409579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d", reg->block); 141bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } else { 1429579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1); 143bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 1449579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash fputc(separator, f); 145bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker } 146bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker fputc('\n', f); 147bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker} 148bec598e982301bf2714d37b14e312c9845c7cc0cDoug Zongker 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid append_region(struct block_allocation *alloc, 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block, u32 len, int bg_num) 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 1528aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 1538aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 1548aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->block = block; 1558aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->len = len; 1568aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->bg = bg_num; 1578aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->next = NULL; 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1598aef66d2125af8de7672a12895276802fcc1948fColin Cross region_list_append(&alloc->list, reg); 160ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 161ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 162ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void allocate_bg_inode_table(struct block_group_info *bg) 163ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 164ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table != NULL) 165ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 167ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block + 2; 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 17022742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table == NULL) 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 176782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->inode_table, 177f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross aux_info.inode_table_blocks * info.block_size, block); 178107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 17956497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross bg->flags &= ~EXT4_BG_INODE_UNINIT; 180107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall} 181107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 184ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap[bit / 8] & 1 << (bit % 8)) 185ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 1; 186ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 187ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] |= 1 << (bit % 8); 188ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 189ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int ret = bitmap[bit / 8]; 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] = 0xFF; 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ret; 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Marks a the first num_blocks blocks in a block group as used, and accounts 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for them in the block group free block info. */ 200a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyashstatic int reserve_blocks(struct block_group_info *bg, u32 bg_num, u32 start, u32 num) 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i = 0; 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = start; 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num && block % 8 != 0; i++, block++) { 206ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 207a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i + 8 <= (num & ~7); i += 8, block += 8) { 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_8_bits(bg->block_bitmap, block)) { 214a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i < num; i++, block++) { 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 221a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash error("attempted to reserve already reserved block %d in block group %d", block, bg_num); 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks -= num; 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2319579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashstatic void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks) 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 234ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num_blocks; i++, block--) 235ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 236ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks += num_blocks; 237be25a224b45a0c3d1fecd3b09e74aa2741f19b71Mohamad Ayyash for (i = bg->chunk_count; i > 0 ;) { 238be25a224b45a0c3d1fecd3b09e74aa2741f19b71Mohamad Ayyash --i; 23962b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash if (bg->chunks[i].len >= num_blocks && bg->chunks[i].block <= block) { 24062b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash if (bg->chunks[i].block == block) { 24162b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash bg->chunks[i].block += num_blocks; 24262b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash bg->chunks[i].len -= num_blocks; 24362b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash } else if (bg->chunks[i].block + bg->chunks[i].len - 1 == block + num_blocks) { 24462b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash bg->chunks[i].len -= num_blocks; 24562b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash } 24662b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash break; 24762b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash } 24862b5fa4a8b71b99f5a9f33cf4ec1949e30c13060Mohamad Ayyash } 249ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 250ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 251ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reduces an existing allocation by len blocks by return the last blocks 252ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross to the free pool in their block group. Assumes that the blocks being 253ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross returned were the last ones allocated out of the block group */ 254ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid reduce_allocation(struct block_allocation *alloc, u32 len) 255ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 256ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len) { 257ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *last_reg = alloc->list.last; 2589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bg = &aux_info.bgs[last_reg->bg]; 259ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 260ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (last_reg->len > len) { 2619579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len); 262ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross last_reg->len -= len; 263ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = 0; 264ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 265a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross struct region *reg = alloc->list.last->prev; 2669579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len); 267ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= last_reg->len; 268a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross if (reg) { 269ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 270a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } else { 271a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.first = NULL; 272a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.last = NULL; 273a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.iter = NULL; 274a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.partial_iter = 0; 275a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } 276ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(last_reg); 277ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 278ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 279ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 280ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 281ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void init_bg(struct block_group_info *bg, unsigned int i) 282ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 283ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks = 2 + aux_info.inode_table_blocks; 284ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 285ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->has_superblock = ext4_bg_has_super_block(i); 286ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 287ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 28822742ce739a046a079b2e1b03342a25472dfa352Colin Cross header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 289ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 290ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->bitmaps = calloc(info.block_size, 2); 291ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap = bg->bitmaps; 292ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_bitmap = bg->bitmaps + info.block_size; 293ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 294ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->header_blocks = header_blocks; 295ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 296ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 297ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block; 298ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 29922742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 300782879ab61fe825835a9c6a701f91aa7d305acefColin Cross sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 301f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross block); 302ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 303ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->data_blocks_used = 0; 304ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks = info.blocks_per_group; 305ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_inodes = info.inodes_per_group; 306ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_inode = 1; 307dedf8f9705df13e1fd07d3f754216d34725bb269Mohamad Ayyash bg->flags = EXT4_BG_INODE_UNINIT; 308ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 3099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunk_count = 0; 3109579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->max_chunk_count = 1; 3119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region)); 3129579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 313a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(bg, i, 0, bg->header_blocks) < 0) 314ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 3159579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty starting delimiter chunk 3169579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, bg->header_blocks, 0); 317ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 31817de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 31917de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 320a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash reserve_blocks(bg, i, info.blocks_per_group - overrun, overrun); 3219579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Add empty ending delimiter chunk 3229579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - overrun, 0); 3239579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else { 3249579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reserve_bg_chunk(i, info.blocks_per_group - 1, 0); 32517de65420dbc114001896d243fbb27cc3ba6bf61Ken Sumrall } 3269579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 327ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 328ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 329ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_init() 330ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 331ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 332ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 333ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 334ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs == NULL) 335ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 336ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 337ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) 338ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross init_bg(&aux_info.bgs[i], i); 339ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 340ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 341ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_free() 342ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 343ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 344ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 345ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 346ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].bitmaps); 347ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].inode_table); 348ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 349ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs); 350ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 351ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 352ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate a single block and return its block number */ 353ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_block() 354ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 3559579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 block; 3569579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_allocation *blk_alloc = allocate_blocks(1); 3579579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!blk_alloc) { 3589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return EXT4_ALLOCATE_FAILED; 359ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 3609579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash block = blk_alloc->list.first->block; 3619579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash free_alloc(blk_alloc); 3629579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return block; 363ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 364ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 365eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit_partial(u32 len) 366ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 367cd205307320b4da5dd7899f79b83539c620ae1d1Dmitry Shmidt unsigned int i; 368cd205307320b4da5dd7899f79b83539c620ae1d1Dmitry Shmidt int j; 3699579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0; 3709579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 found_allocate_len = 0; 3719579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bool minimize = false; 3729579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 3739579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 37418785a86a30135ac65b88db9886bfc22d6608849Mohamad Ayyash 375ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 3769579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash for (j = 1; j < bgs[i].chunk_count; j++) { 3779579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash u32 hole_start, hole_size; 3789579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len; 3799579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash hole_size = bgs[i].chunks[j].block - hole_start; 3809579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (hole_size == len) { 3819579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // Perfect fit i.e. right between 2 chunks no need to keep searching 3829579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3839579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3849579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3859579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3869579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash goto done; 3879579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) { 3889579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3899579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3909579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3919579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3929579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash minimize = true; 3939579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } else if (!minimize) { 3949579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len < hole_size) { 3959579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_bg = i; 3969579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_prev_chunk = j - 1; 3979579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block = hole_start; 3989579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len = hole_size; 3999579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 4009579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 401eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 402eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross } 403ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 4049579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len == 0) { 405eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross error("failed to allocate %u blocks, out of space?", len); 4069579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 407ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 4089579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (found_allocate_len > len) found_allocate_len = len; 4099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashdone: 4109579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash // reclaim allocated space in chunk 4119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len; 4129579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (reserve_blocks(&bgs[found_bg], 413a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash found_bg, 4149579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_block, 4159579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash found_allocate_len) < 0) { 4169579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg); 4179579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return NULL; 4189579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 4199579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[found_bg].data_blocks_used += found_allocate_len; 4209579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = malloc(sizeof(struct region)); 4219579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->block = found_block + bgs[found_bg].first_block; 4229579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->len = found_allocate_len; 4239579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->next = NULL; 4249579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->prev = NULL; 4259579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg->bg = found_bg; 4269579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return reg; 427ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 428ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 429eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Crossstatic struct region *ext4_allocate_best_fit(u32 len) 430ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 431ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first_reg = NULL; 432ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *prev_reg = NULL; 433ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 434ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 435ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len > 0) { 436eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross reg = ext4_allocate_best_fit_partial(len); 437ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 438ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 439ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 440ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (first_reg == NULL) 441ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross first_reg = reg; 442ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 443ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (prev_reg) { 444ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg->next = reg; 445ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = prev_reg; 446ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 447ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 448ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg = reg; 449ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 450ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 451ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 452ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return first_reg; 453ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 454ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 455ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate len blocks. The blocks may be spread across multiple block groups, 456ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and are returned in a linked list of the blocks in each block group. The 457ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocation algorithm is: 4589579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 1. If the remaining allocation is larger than any available contiguous region, 4599579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash allocate the largest contiguous region and loop 4609579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 2. Otherwise, allocate the smallest contiguous region that it fits in 461ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross*/ 462ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *allocate_blocks(u32 len) 463ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 464eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 465ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 466ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 467ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 468ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 469ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = create_allocation(); 470ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = reg; 4719579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg->next != NULL) 4729579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 4738aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = reg; 474ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 475ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 476ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 477ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 478ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 479ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of discontiguous regions used by an allocation */ 480ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_num_regions(struct block_allocation *alloc) 481ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 482ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 483ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 484ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 485ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 486ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i++; 487ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 488ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 489ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 490ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 491ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_len(struct block_allocation *alloc) 492ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 493ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 4948aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.first; 495ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 496ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 497ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i += reg->len; 498ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 499ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 500ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 501ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 502ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the block number of the block'th block in an allocation */ 503ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_block(struct block_allocation *alloc, u32 block) 504ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5058aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5068aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->list.partial_iter; 507ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5088aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 509ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 510ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 511ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 512ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 513ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 514ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 515ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 516ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_oob_block(struct block_allocation *alloc, u32 block) 517ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5188aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->oob_list.iter; 5198aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->oob_list.partial_iter; 520ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5218aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 522ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 523ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 524ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 525ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 526ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 527ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 528ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 529ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Gets the starting block and length in blocks of the first region 530ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross of an allocation */ 531ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 532ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 533ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *block = alloc->list.iter->block; 534ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *len = alloc->list.iter->len - alloc->list.partial_iter; 535ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 536ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 537ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move to the next region in an allocation */ 538ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_next_region(struct block_allocation *alloc) 539ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 540ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.iter->next; 541ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 542ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 543ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 544ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free blocks in a block group */ 545ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_blocks(u32 bg) 546ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 547ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_blocks; 548ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 549ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 550ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint last_region(struct block_allocation *alloc) 551ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 552ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (alloc->list.iter == NULL); 553ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 554ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 555ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid rewind_alloc(struct block_allocation *alloc) 556ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 557ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 558ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 559ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 560ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 561ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 562ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5638aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5648aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *new; 5658aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *tmp; 566ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5678aef66d2125af8de7672a12895276802fcc1948fColin Cross while (reg && len >= reg->len) { 568ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 569ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 570ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 571ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 572ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL && len > 0) 573ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 574ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 575ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len > 0) { 576ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new = malloc(sizeof(struct region)); 577ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 578ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->bg = reg->bg; 579ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->block = reg->block + len; 580ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->len = reg->len - len; 581ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->next = reg->next; 582ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->prev = reg; 583ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 584ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = new; 585ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 586ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 587ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross tmp = alloc->list.iter; 5888aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = new; 589ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return tmp; 590ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 591ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 592ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 593ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 594ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 595ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Splits an allocation into two allocations. The returned allocation will 596ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross point to the first half, and the original allocation ptr will point to the 597ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross second half. */ 598ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 599ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 600ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* First make sure there is a split at the current ptr */ 601ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross do_split_allocation(alloc, alloc->list.partial_iter); 602ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 603ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Then split off len blocks */ 604ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *middle = do_split_allocation(alloc, len); 605ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 606ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return middle; 607ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 608ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 609ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reserve the next blocks for oob data (indirect or extent blocks) */ 610ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 611ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 612ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *oob = split_allocation(alloc, blocks); 6138aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *next; 614ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 615ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (oob == NULL) 616ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 617ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 618ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (oob && oob != alloc->list.iter) { 619ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross next = oob->next; 620ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_remove(&alloc->list, oob); 621ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, oob); 622ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oob = next; 623ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 624ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 625ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 626ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 627ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 628ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int advance_list_ptr(struct region_list *list, int blocks) 629ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 630ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = list->iter; 631ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 632ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg != NULL && blocks > 0) { 633ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->len > list->partial_iter + blocks) { 634ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter += blocks; 635ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 636ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 637ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 638ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks -= (reg->len - list->partial_iter); 639ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 640ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 641ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 642ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 643ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (blocks > 0) 644ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 645ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 646ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 647ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 648ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 649ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move the allocation pointer forward */ 650ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_blocks(struct block_allocation *alloc, int blocks) 651ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 652ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->list, blocks); 653ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 654ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 655ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_oob_blocks(struct block_allocation *alloc, int blocks) 656ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 657ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->oob_list, blocks); 658ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 659ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 660ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint append_oob_allocation(struct block_allocation *alloc, u32 len) 661ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 662eb3915a5eb76c687fd74773f3896a939d0bf5211Colin Cross struct region *reg = ext4_allocate_best_fit(len); 663ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 664ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) { 665ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks", len); 666ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 667ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 668ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 669ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) 670ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, reg); 671ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 672ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 673ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 674ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 675ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns an ext4_inode structure for an inode number */ 676ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct ext4_inode *get_inode(u32 inode) 677ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 678ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode -= 1; 679ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = inode / info.inodes_per_group; 680ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode %= info.inodes_per_group; 681ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 682ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocate_bg_inode_table(&aux_info.bgs[bg]); 6838aef66d2125af8de7672a12895276802fcc1948fColin Cross return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6848aef66d2125af8de7672a12895276802fcc1948fColin Cross info.inode_size); 685ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 686ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 6874df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 6884df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 6894df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *block = xattr_list_find(inode); 6904df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block != NULL) 6914df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 6924df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 6934df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich u32 block_num = allocate_block(); 6944df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block = calloc(info.block_size, 1); 6954df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block == NULL) { 6964df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: failed to allocate %d", info.block_size); 6974df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 6984df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 6994df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 7004df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 7014df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_refcount = cpu_to_le32(1); 7024df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_blocks = cpu_to_le32(1); 7034df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 7044df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_file_acl_lo = cpu_to_le32(block_num); 7054df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 706782879ab61fe825835a9c6a701f91aa7d305acefColin Cross int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 7074df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (result != 0) { 7084df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: sparse_file_add_data failure %d", result); 7094df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich free(block); 7104df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 7114df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 7124df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich xattr_list_insert(inode, block); 7134df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 7144df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 7154df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 716ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Mark the first len inodes in a block group as used */ 717ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 reserve_inodes(int bg, u32 num) 718ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 719ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 720ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 721ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 722ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_inodes(bg) < num) 723ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 724ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 725ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num; i++) { 726ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode + i - 1; 727ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 728ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 729ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 730ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode; 731ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 732ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].first_free_inode += num; 733ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].free_inodes -= num; 734ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 735ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return inode; 736ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 737ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 738ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the first free inode number 739ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross TODO: Inodes should be allocated in the block group of the data? */ 740ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_inode() 741ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 742ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int bg; 743ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 744ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 745ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (bg = 0; bg < aux_info.groups; bg++) { 746ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = reserve_inodes(bg, 1); 747ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (inode != EXT4_ALLOCATE_FAILED) 748ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg * info.inodes_per_group + inode; 749ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 750ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 751ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 752ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 753ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 754ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free inodes in a block group */ 755ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_inodes(u32 bg) 756ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 757ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_inodes; 758ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 759ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 760ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Increments the directory count of the block group that contains inode */ 761ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid add_directory(u32 inode) 762ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 763ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = (inode - 1) / info.inodes_per_group; 764ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].used_dirs += 1; 765ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 766ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 767ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of inodes in a block group that are directories */ 768ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu16 get_directories(int bg) 769ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 770ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].used_dirs; 771ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 772ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 77356497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross/* Returns the flags for a block group */ 77456497f28bd20001dd5f931208e8d948cf2f81b2fColin Crossu16 get_bg_flags(int bg) 77556497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross{ 77656497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross return aux_info.bgs[bg].flags; 77756497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross} 77856497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross 779ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Frees the memory used by a linked list of allocation regions */ 780ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid free_alloc(struct block_allocation *alloc) 781ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 782ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 783ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 784ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->list.first; 785ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 786ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 787ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 788ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 789ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 790ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 791ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->oob_list.first; 792ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 793ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 794ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 795ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 796ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 797ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 798ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(alloc); 799ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 8009579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 8019579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashvoid reserve_bg_chunk(int bg, u32 start_block, u32 size) { 8029579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 8039579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash int chunk_count; 8049579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) { 8059579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].max_chunk_count *= 2; 8069579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region)); 8079579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!bgs[bg].chunks) 8089579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash critical_error("realloc failed"); 8099579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 8109579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash chunk_count = bgs[bg].chunk_count; 8119579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].block = start_block; 8129579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].len = size; 8139579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunks[chunk_count].bg = bg; 8149579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash bgs[bg].chunk_count++; 8159579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 8169579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 8179579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyashint reserve_blocks_for_allocation(struct block_allocation *alloc) { 8189579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct region *reg; 8199579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash struct block_group_info *bgs = aux_info.bgs; 8209579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 8219579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash if (!alloc) return 0; 8229579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = alloc->list.first; 8239579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash while (reg != NULL) { 824a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash if (reserve_blocks(&bgs[reg->bg], reg->bg, reg->block - bgs[reg->bg].first_block, reg->len) < 0) { 8259579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return -1; 826a6866eb4c6b88403683ac7e00a517820d2e1e810Mohamad Ayyash } 8279579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash reg = reg->next; 8289579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash } 8299579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash return 0; 8309579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash} 8319579198cd7d5b88b3508f1b00ddd77bd8da60682Mohamad Ayyash 832