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