1ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* 2ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Copyright (C) 2010 The Android Open Source Project 3ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 4ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Licensed under the Apache License, Version 2.0 (the "License"); 5ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * you may not use this file except in compliance with the License. 6ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * You may obtain a copy of the License at 7ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 8ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * http://www.apache.org/licenses/LICENSE-2.0 9ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * 10ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * Unless required by applicable law or agreed to in writing, software 11ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * distributed under the License is distributed on an "AS IS" BASIS, 12ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * See the License for the specific language governing permissions and 14ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * limitations under the License. 15ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross */ 16ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 17ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4_utils.h" 18ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "allocate.h" 19ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#include "ext4.h" 20ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 21dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross#include <sparse/sparse.h> 22dc5abeee1e6fc4827ee0d5ece12aaed2dd56f4c7Colin Cross 2333f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdio.h> 2433f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross#include <stdlib.h> 2533f96c66e9a1f2e266a75e5e84c091dffa6ef118Colin Cross 26ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct region_list { 278aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *first; 288aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *last; 298aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *iter; 308aef66d2125af8de7672a12895276802fcc1948fColin Cross u32 partial_iter; 31ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 32ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 33ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation { 34ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region_list list; 35ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region_list oob_list; 36ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 37ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 38ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct region { 398aef66d2125af8de7672a12895276802fcc1948fColin Cross u32 block; 408aef66d2125af8de7672a12895276802fcc1948fColin Cross u32 len; 418aef66d2125af8de7672a12895276802fcc1948fColin Cross int bg; 428aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *next; 438aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *prev; 44ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 45ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 46ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_group_info { 47ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 first_block; 48ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks; 49ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int data_blocks_used; 50ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int has_superblock; 51ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *bitmaps; 52ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *block_bitmap; 53ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *inode_bitmap; 54ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u8 *inode_table; 55ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 free_blocks; 56ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 first_free_block; 57ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 free_inodes; 58ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 first_free_inode; 5956497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross u16 flags; 60ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u16 used_dirs; 61ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross}; 62ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 634df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct xattr_list_element { 644df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_inode *inode; 654df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *header; 664df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *next; 674df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich}; 684df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *create_allocation() 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 718aef66d2125af8de7672a12895276802fcc1948fColin Cross struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 728aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.first = NULL; 738aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = NULL; 748aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.first = NULL; 758aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.last = NULL; 768aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = NULL; 778aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.partial_iter = 0; 788aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.iter = NULL; 798aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->oob_list.partial_iter = 0; 808aef66d2125af8de7672a12895276802fcc1948fColin Cross return alloc; 81ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 82ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 834df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode) 844df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 854df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element; 864df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich for (element = aux_info.xattrs; element != NULL; element = element->next) { 874df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (element->inode == inode) 884df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return element->header; 894df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 904df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 914df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 924df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 934df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstatic void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header) 944df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 954df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element)); 964df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->inode = inode; 974df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->header = header; 984df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich element->next = aux_info.xattrs; 994df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich aux_info.xattrs = element; 1004df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 1014df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 102ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void region_list_remove(struct region_list *list, struct region *reg) 103ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 104ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->prev) 105ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev->next = reg->next; 106ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 107ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->next) 108ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next->prev = reg->prev; 109ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 110ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == reg) 111ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg->next; 112ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 113ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->last == reg) 114ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg->prev; 115ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 116ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 117ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 118ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 119ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 120ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void region_list_append(struct region_list *list, struct region *reg) 121ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 122ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (list->first == NULL) { 123ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->first = reg; 124ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 125ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->iter = reg; 126ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 127ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 128ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 129ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last->next = reg; 130ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = list->last; 131ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->last = reg; 132ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 133ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#if 0 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_starting_from(struct region *reg) 138ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 139ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 140ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("%p: Blocks %d-%d (%d)\n", reg, 141ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg * info.blocks_per_group + reg->block, 142ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg * info.blocks_per_group + reg->block + reg->len - 1, 143ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len); 144ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 145ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 146ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 147ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void dump_region_lists(struct block_allocation *alloc) { 148ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 149ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("Main list:\n"); 150ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->list.first); 151ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 152ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross printf("OOB list:\n"); 153ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross dump_starting_from(alloc->oob_list.first); 154ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 155ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross#endif 156ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 157ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid append_region(struct block_allocation *alloc, 158ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block, u32 len, int bg_num) 159ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 1608aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 1618aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 1628aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->block = block; 1638aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->len = len; 1648aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->bg = bg_num; 1658aef66d2125af8de7672a12895276802fcc1948fColin Cross reg->next = NULL; 166ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1678aef66d2125af8de7672a12895276802fcc1948fColin Cross region_list_append(&alloc->list, reg); 168ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 169ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 170ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void allocate_bg_inode_table(struct block_group_info *bg) 171ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 172ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table != NULL) 173ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return; 174ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 175ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block + 2; 176ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 177ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 17822742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 179ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 180ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 181ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->inode_table == NULL) 182ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 183ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 184f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross sparse_file_add_data(info.sparse_file, bg->inode_table, 185f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross aux_info.inode_table_blocks * info.block_size, block); 186107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 18756497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross bg->flags &= ~EXT4_BG_INODE_UNINIT; 188107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall} 189107a9f161babc20daf915311146b0e864d3b4157Ken Sumrall 190ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 191ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 192ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap[bit / 8] & 1 << (bit % 8)) 193ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 1; 194ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 195ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] |= 1 << (bit % 8); 196ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 197ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 198ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 199ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 200ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 201ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int ret = bitmap[bit / 8]; 202ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bitmap[bit / 8] = 0xFF; 203ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return ret; 204ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 205ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 206ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Marks a the first num_blocks blocks in a block group as used, and accounts 207ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for them in the block group free block info. */ 208ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int reserve_blocks(struct block_group_info *bg, u32 start, u32 num) 209ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 210ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i = 0; 211ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 212ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = start; 213ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (num > bg->free_blocks) 214ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 215ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 216ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num && block % 8 != 0; i++, block++) { 217ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 218ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("attempted to reserve already reserved block"); 219ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 220ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 221ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 222ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 223ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i + 8 <= (num & ~7); i += 8, block += 8) { 224ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_8_bits(bg->block_bitmap, block)) { 225ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("attempted to reserve already reserved block"); 226ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 227ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 228ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 229ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 230ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; i < num; i++, block++) { 231ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bitmap_set_bit(bg->block_bitmap, block)) { 232ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("attempted to reserve already reserved block"); 233ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 234ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 235ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 236ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 237ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks -= num; 238ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (start == bg->first_free_block) 239ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_block = start + num; 240ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 241ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 242ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 243ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 244ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void free_blocks(struct block_group_info *bg, u32 num_blocks) 245ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 246ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 247ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_free_block - 1; 248ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num_blocks; i++, block--) 249ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 250ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks += num_blocks; 251ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_block -= num_blocks; 252ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 253ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 254ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reduces an existing allocation by len blocks by return the last blocks 255ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross to the free pool in their block group. Assumes that the blocks being 256ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross returned were the last ones allocated out of the block group */ 257ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid reduce_allocation(struct block_allocation *alloc, u32 len) 258ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 259ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len) { 260ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *last_reg = alloc->list.last; 261ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 262ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (last_reg->len > len) { 263ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_blocks(&aux_info.bgs[last_reg->bg], len); 264ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross last_reg->len -= len; 265ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len = 0; 266ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 267a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross struct region *reg = alloc->list.last->prev; 268ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len); 269ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= last_reg->len; 270a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross if (reg) { 271ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 272a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } else { 273a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.first = NULL; 274a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.last = NULL; 275a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.iter = NULL; 276a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross alloc->list.partial_iter = 0; 277a1a175aef60677ed877bcb52db553705a8e8c20fColin Cross } 278ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(last_reg); 279ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 280ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 281ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 282ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 283ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void init_bg(struct block_group_info *bg, unsigned int i) 284ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 285ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks = 2 + aux_info.inode_table_blocks; 286ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 287ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->has_superblock = ext4_bg_has_super_block(i); 288ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 289ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 29022742ce739a046a079b2e1b03342a25472dfa352Colin Cross header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 291ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 292ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->bitmaps = calloc(info.block_size, 2); 293ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap = bg->bitmaps; 294ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_bitmap = bg->bitmaps + info.block_size; 295ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 296ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->header_blocks = header_blocks; 297ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 298ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 299ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block; 300ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 30122742ce739a046a079b2e1b03342a25472dfa352Colin Cross block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 302f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross sparse_file_add_data(info.sparse_file, bg->bitmaps, 2 * info.block_size, 303f0ee37ffded79afdb03e15ae3a69969d2b7e6079Colin Cross block); 304ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 305ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->data_blocks_used = 0; 306ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks = info.blocks_per_group; 307ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_block = 0; 308ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_inodes = info.inodes_per_group; 309ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_inode = 1; 31056497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross bg->flags = EXT4_BG_INODE_UNINIT; 311ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 312ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) 313ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 314ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 315ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 316ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (overrun > 0) 317ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reserve_blocks(bg, info.blocks_per_group - overrun, overrun); 318ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 319ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 320ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_init() 321ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 322ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 323ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 324ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 325ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs == NULL) 326ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 327ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 328ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) 329ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross init_bg(&aux_info.bgs[i], i); 330ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 331ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 332ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_free() 333ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 334ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 335ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 336ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 337ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].bitmaps); 338ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].inode_table); 339ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 340ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs); 341ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 342ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 343ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) 344ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 345ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_blocks(bg_num) < len) 346ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 347ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 348ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = aux_info.bgs[bg_num].first_free_block; 349ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_group_info *bg = &aux_info.bgs[bg_num]; 350ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reserve_blocks(bg, bg->first_free_block, len) < 0) { 351ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", len, bg_num); 352ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 353ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 354ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 355ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg_num].data_blocks_used += len; 356ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 357ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg->first_block + block; 358ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 359ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 360ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_contiguous_blocks(u32 len) 361ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 362ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 3638aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 364ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 365ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 366ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = ext4_allocate_blocks_from_block_group(len, i); 367ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 368ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block != EXT4_ALLOCATE_FAILED) { 3698aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 370ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->block = block; 371ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 372ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 373ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 374ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg = i; 375ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 376ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 377ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 378ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 379ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 380ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 381ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 382ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate a single block and return its block number */ 383ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_block() 384ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 385ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 386ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 387ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = ext4_allocate_blocks_from_block_group(1, i); 388ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 389ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block != EXT4_ALLOCATE_FAILED) 390ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return block; 391ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 392ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 393ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 394ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 395ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 396ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_partial(u32 len) 397ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 398ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 3998aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg; 400ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 401ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 402ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs[i].data_blocks_used == 0) { 403ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 bg_len = aux_info.bgs[i].free_blocks; 404ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block; 405ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 406ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len <= bg_len) { 407ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* If the requested length would fit in a block group, 408ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross use the regular allocator to try to fit it in a partially 409ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross used block group */ 410ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg_len = len; 411ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_contiguous_blocks(len); 412ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 413ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block = ext4_allocate_blocks_from_block_group(bg_len, i); 414ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 415ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block == EXT4_ALLOCATE_FAILED) { 416ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks in block group %d", bg_len, i); 417ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 418ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 419ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 4208aef66d2125af8de7672a12895276802fcc1948fColin Cross reg = malloc(sizeof(struct region)); 421ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->block = block; 422ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = bg_len; 423ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 424ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 425ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg = i; 426ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 427ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 428ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 429ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 430ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 431ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 432ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 433ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 434ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_multiple_contiguous_blocks(u32 len) 435ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 436ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first_reg = NULL; 437ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *prev_reg = NULL; 438ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 439ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 440ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len > 0) { 441ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_partial(len); 442ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 443ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 444ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 445ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (first_reg == NULL) 446ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross first_reg = reg; 447ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 448ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (prev_reg) { 449ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg->next = reg; 450ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = prev_reg; 451ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 452ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 453ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg = reg; 454ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 455ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 456ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 457ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return first_reg; 458ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 459ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 460ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct region *do_allocate(u32 len) 461ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 462ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = ext4_allocate_contiguous_blocks(len); 463ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 464ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 465ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_multiple_contiguous_blocks(len); 466ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 467ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 468ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 469ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 470ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate len blocks. The blocks may be spread across multiple block groups, 471ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and are returned in a linked list of the blocks in each block group. The 472ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocation algorithm is: 473ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1. Try to allocate the entire block len in each block group 474ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2. If the request doesn't fit in any block group, allocate as many 475ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks as possible into each block group that is completely empty 476ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 3. Put the last set of blocks in the first block group they fit in 477ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross*/ 478ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *allocate_blocks(u32 len) 479ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 480ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = do_allocate(len); 481ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 482ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 483ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 484ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 485ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = create_allocation(); 486ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = reg; 4878aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.last = reg; 488ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 489ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 490ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 491ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 492ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 493ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of discontiguous regions used by an allocation */ 494ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_num_regions(struct block_allocation *alloc) 495ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 496ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 497ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 498ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 499ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 500ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i++; 501ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 502ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 503ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 504ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 505ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_len(struct block_allocation *alloc) 506ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 507ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 5088aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.first; 509ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 510ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 511ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i += reg->len; 512ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 513ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 514ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 515ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 516ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the block number of the block'th block in an allocation */ 517ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_block(struct block_allocation *alloc, u32 block) 518ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5198aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5208aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->list.partial_iter; 521ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5228aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 523ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 524ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 525ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 526ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 527ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 528ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 529ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 530ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_oob_block(struct block_allocation *alloc, u32 block) 531ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5328aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->oob_list.iter; 5338aef66d2125af8de7672a12895276802fcc1948fColin Cross block += alloc->oob_list.partial_iter; 534ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5358aef66d2125af8de7672a12895276802fcc1948fColin Cross for (; reg; reg = reg->next) { 536ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 537ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 538ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 539ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 540ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 541ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 542ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 543ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Gets the starting block and length in blocks of the first region 544ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross of an allocation */ 545ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 546ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 547ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *block = alloc->list.iter->block; 548ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *len = alloc->list.iter->len - alloc->list.partial_iter; 549ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 550ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 551ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move to the next region in an allocation */ 552ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_next_region(struct block_allocation *alloc) 553ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 554ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.iter->next; 555ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 556ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 557ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 558ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free blocks in a block group */ 559ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_blocks(u32 bg) 560ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 561ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_blocks; 562ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 563ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 564ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint last_region(struct block_allocation *alloc) 565ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 566ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (alloc->list.iter == NULL); 567ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 568ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 569ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid rewind_alloc(struct block_allocation *alloc) 570ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 571ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 572ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 573ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 574ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 575ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 576ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 5778aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *reg = alloc->list.iter; 5788aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *new; 5798aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *tmp; 580ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 5818aef66d2125af8de7672a12895276802fcc1948fColin Cross while (reg && len >= reg->len) { 582ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 583ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 584ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 585ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 586ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL && len > 0) 587ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 588ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 589ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len > 0) { 590ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new = malloc(sizeof(struct region)); 591ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 592ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->bg = reg->bg; 593ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->block = reg->block + len; 594ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->len = reg->len - len; 595ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->next = reg->next; 596ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->prev = reg; 597ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 598ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = new; 599ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 600ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 601ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross tmp = alloc->list.iter; 6028aef66d2125af8de7672a12895276802fcc1948fColin Cross alloc->list.iter = new; 603ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return tmp; 604ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 605ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 606ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 607ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 608ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 609ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Splits an allocation into two allocations. The returned allocation will 610ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross point to the first half, and the original allocation ptr will point to the 611ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross second half. */ 612ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 613ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 614ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* First make sure there is a split at the current ptr */ 615ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross do_split_allocation(alloc, alloc->list.partial_iter); 616ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 617ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Then split off len blocks */ 618ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *middle = do_split_allocation(alloc, len); 619ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 620ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return middle; 621ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 622ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 623ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reserve the next blocks for oob data (indirect or extent blocks) */ 624ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 625ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 626ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *oob = split_allocation(alloc, blocks); 6278aef66d2125af8de7672a12895276802fcc1948fColin Cross struct region *next; 628ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 629ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (oob == NULL) 630ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 631ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 632ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (oob && oob != alloc->list.iter) { 633ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross next = oob->next; 634ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_remove(&alloc->list, oob); 635ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, oob); 636ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oob = next; 637ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 638ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 639ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 640ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 641ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 642ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int advance_list_ptr(struct region_list *list, int blocks) 643ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 644ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = list->iter; 645ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 646ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg != NULL && blocks > 0) { 647ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->len > list->partial_iter + blocks) { 648ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter += blocks; 649ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 650ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 651ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 652ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks -= (reg->len - list->partial_iter); 653ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 654ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 655ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 656ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 657ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (blocks > 0) 658ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 659ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 660ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 661ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 662ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 663ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move the allocation pointer forward */ 664ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_blocks(struct block_allocation *alloc, int blocks) 665ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 666ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->list, blocks); 667ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 668ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 669ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_oob_blocks(struct block_allocation *alloc, int blocks) 670ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 671ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->oob_list, blocks); 672ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 673ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 674ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint append_oob_allocation(struct block_allocation *alloc, u32 len) 675ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 676ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = do_allocate(len); 677ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 678ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) { 679ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks", len); 680ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 681ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 682ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 683ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) 684ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, reg); 685ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 686ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 687ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 688ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 689ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns an ext4_inode structure for an inode number */ 690ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct ext4_inode *get_inode(u32 inode) 691ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 692ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode -= 1; 693ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = inode / info.inodes_per_group; 694ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode %= info.inodes_per_group; 695ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 696ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocate_bg_inode_table(&aux_info.bgs[bg]); 6978aef66d2125af8de7672a12895276802fcc1948fColin Cross return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6988aef66d2125af8de7672a12895276802fcc1948fColin Cross info.inode_size); 699ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 700ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 7014df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevichstruct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 7024df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich{ 7034df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich struct ext4_xattr_header *block = xattr_list_find(inode); 7044df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block != NULL) 7054df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 7064df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 7074df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich u32 block_num = allocate_block(); 7084df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block = calloc(info.block_size, 1); 7094df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (block == NULL) { 7104df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: failed to allocate %d", info.block_size); 7114df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 7124df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 7134df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 7144df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 7154df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_refcount = cpu_to_le32(1); 7164df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich block->h_blocks = cpu_to_le32(1); 7174df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 7184df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich inode->i_file_acl_lo = cpu_to_le32(block_num); 7194df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 7204df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich int result = sparse_file_add_data(info.sparse_file, block, info.block_size, block_num); 7214df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich if (result != 0) { 7224df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich error("get_xattr: sparse_file_add_data failure %d", result); 7234df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich free(block); 7244df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return NULL; 7254df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich } 7264df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich xattr_list_insert(inode, block); 7274df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich return block; 7284df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich} 7294df62f342dbbe2f5cca831ce789dc0426d32ec03Nick Kralevich 730ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Mark the first len inodes in a block group as used */ 731ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 reserve_inodes(int bg, u32 num) 732ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 733ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 734ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 735ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 736ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_inodes(bg) < num) 737ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 738ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 739ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num; i++) { 740ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode + i - 1; 741ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 742ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 743ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 744ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode; 745ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 746ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].first_free_inode += num; 747ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].free_inodes -= num; 748ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 749ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return inode; 750ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 751ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 752ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the first free inode number 753ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross TODO: Inodes should be allocated in the block group of the data? */ 754ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_inode() 755ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 756ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int bg; 757ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 758ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 759ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (bg = 0; bg < aux_info.groups; bg++) { 760ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = reserve_inodes(bg, 1); 761ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (inode != EXT4_ALLOCATE_FAILED) 762ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg * info.inodes_per_group + inode; 763ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 764ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 765ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 766ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 767ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 768ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free inodes in a block group */ 769ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_inodes(u32 bg) 770ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 771ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_inodes; 772ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 773ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 774ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Increments the directory count of the block group that contains inode */ 775ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid add_directory(u32 inode) 776ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 777ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = (inode - 1) / info.inodes_per_group; 778ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].used_dirs += 1; 779ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 780ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 781ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of inodes in a block group that are directories */ 782ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu16 get_directories(int bg) 783ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 784ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].used_dirs; 785ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 786ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 78756497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross/* Returns the flags for a block group */ 78856497f28bd20001dd5f931208e8d948cf2f81b2fColin Crossu16 get_bg_flags(int bg) 78956497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross{ 79056497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross return aux_info.bgs[bg].flags; 79156497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross} 79256497f28bd20001dd5f931208e8d948cf2f81b2fColin Cross 793ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Frees the memory used by a linked list of allocation regions */ 794ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid free_alloc(struct block_allocation *alloc) 795ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 796ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 797ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 798ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->list.first; 799ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 800ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 801ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 802ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 803ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 804ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 805ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->oob_list.first; 806ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 807ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 808ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 809ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 810ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 811ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 812ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(alloc); 813ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 814