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