allocate.c revision ec0a2e83dc66d67addeb90e83144187691852a3e
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 { 27ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first; 28ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *last; 29ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *iter; 30ec0a2e83dc66d67addeb90e83144187691852a3eColin 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 { 39ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block; 40ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 len; 41ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg; 42ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next; 43ec0a2e83dc66d67addeb90e83144187691852a3eColin 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{ 64ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 65ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = NULL; 66ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.last = NULL; 67ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->oob_list.first = NULL; 68ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->oob_list.last = NULL; 69ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = NULL; 70ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 71ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->oob_list.iter = NULL; 72ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->oob_list.partial_iter = 0; 73ec0a2e83dc66d67addeb90e83144187691852a3eColin 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{ 134ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 135ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = malloc(sizeof(struct region)); 136ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->block = block; 137ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 138ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg = bg_num; 139ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 140ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 141ec0a2e83dc66d67addeb90e83144187691852a3eColin 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 159ec0a2e83dc66d67addeb90e83144187691852a3eColin 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 { 239ec0a2e83dc66d67addeb90e83144187691852a3eColin 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; 242ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg) 243ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 244ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(last_reg); 245ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 246ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 247ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 248ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 249ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic void init_bg(struct block_group_info *bg, unsigned int i) 250ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 251ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int header_blocks = 2 + aux_info.inode_table_blocks; 252ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 253ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->has_superblock = ext4_bg_has_super_block(i); 254ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 255ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 256ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross header_blocks += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; 257ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 258ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->bitmaps = calloc(info.block_size, 2); 259ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->block_bitmap = bg->bitmaps; 260ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->inode_bitmap = bg->bitmaps + info.block_size; 261ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 262ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->header_blocks = header_blocks; 263ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 264ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 265ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = bg->first_block; 266ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (bg->has_superblock) 267ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; 268ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross queue_data_block(bg->bitmaps, 2 * info.block_size, block); 269ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 270ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->data_blocks_used = 0; 271ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_blocks = info.blocks_per_group; 272ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_block = 0; 273ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->free_inodes = info.inodes_per_group; 274ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg->first_free_inode = 1; 275ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 276ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) 277ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 278ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 279ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 280ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (overrun > 0) 281ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reserve_blocks(bg, info.blocks_per_group - overrun, overrun); 282ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 283ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 284ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_init() 285ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 286ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 287ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 288ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 289ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs == NULL) 290ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross critical_error_errno("calloc"); 291ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 292ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) 293ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross init_bg(&aux_info.bgs[i], i); 294ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 295ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 296ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid block_allocator_free() 297ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 298ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 299ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 300ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 301ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].bitmaps); 302ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs[i].inode_table); 303ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 304ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(aux_info.bgs); 305ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 306ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 307ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) 308ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 309ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_blocks(bg_num) < len) 310ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 311ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 312ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = aux_info.bgs[bg_num].first_free_block; 313ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_group_info *bg = &aux_info.bgs[bg_num]; 314ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reserve_blocks(bg, bg->first_free_block, len) < 0) { 315ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to reserve %u blocks in block group %u\n", len, bg_num); 316ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 317ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 318ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 319ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg_num].data_blocks_used += len; 320ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 321ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg->first_block + block; 322ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 323ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 324ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_contiguous_blocks(u32 len) 325ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 326ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 327ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 328ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 329ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 330ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = ext4_allocate_blocks_from_block_group(len, i); 331ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 332ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block != EXT4_ALLOCATE_FAILED) { 333ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = malloc(sizeof(struct region)); 334ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->block = block; 335ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 336ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 337ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 338ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg = i; 339ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 340ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 341ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 342ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 343ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 344ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 345ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 346ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate a single block and return its block number */ 347ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_block() 348ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 349ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 350ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 351ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block = ext4_allocate_blocks_from_block_group(1, i); 352ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 353ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block != EXT4_ALLOCATE_FAILED) 354ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return block; 355ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 356ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 357ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 358ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 359ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 360ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_partial(u32 len) 361ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 362ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 363ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 364ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 365ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < aux_info.groups; i++) { 366ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (aux_info.bgs[i].data_blocks_used == 0) { 367ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 bg_len = aux_info.bgs[i].free_blocks; 368ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 block; 369ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 370ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len <= bg_len) { 371ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* If the requested length would fit in a block group, 372ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross use the regular allocator to try to fit it in a partially 373ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross used block group */ 374ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross bg_len = len; 375ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_contiguous_blocks(len); 376ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 377ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block = ext4_allocate_blocks_from_block_group(bg_len, i); 378ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 379ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block == EXT4_ALLOCATE_FAILED) { 380ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks in block group %d", bg_len, i); 381ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 382ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 383ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 384ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = malloc(sizeof(struct region)); 385ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->block = block; 386ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = bg_len; 387ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = NULL; 388ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = NULL; 389ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->bg = i; 390ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 391ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 392ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 393ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 394ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 395ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 396ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 397ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 398ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *ext4_allocate_multiple_contiguous_blocks(u32 len) 399ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 400ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *first_reg = NULL; 401ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *prev_reg = NULL; 402ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 403ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 404ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (len > 0) { 405ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_partial(len); 406ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 407ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 408ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 409ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (first_reg == NULL) 410ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross first_reg = reg; 411ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 412ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (prev_reg) { 413ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg->next = reg; 414ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->prev = prev_reg; 415ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 416ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 417ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross prev_reg = reg; 418ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 419ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 420ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 421ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return first_reg; 422ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 423ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 424ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct region *do_allocate(u32 len) 425ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 426ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = ext4_allocate_contiguous_blocks(len); 427ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 428ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 429ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = ext4_allocate_multiple_contiguous_blocks(len); 430ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 431ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 432ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 433ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 434ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Allocate len blocks. The blocks may be spread across multiple block groups, 435ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross and are returned in a linked list of the blocks in each block group. The 436ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocation algorithm is: 437ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 1. Try to allocate the entire block len in each block group 438ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 2. If the request doesn't fit in any block group, allocate as many 439ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks as possible into each block group that is completely empty 440ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 3. Put the last set of blocks in the first block group they fit in 441ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross*/ 442ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct block_allocation *allocate_blocks(u32 len) 443ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 444ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = do_allocate(len); 445ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 446ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) 447ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 448ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 449ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct block_allocation *alloc = create_allocation(); 450ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.first = reg; 451ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.last = reg; 452ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 453ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 454ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return alloc; 455ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 456ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 457ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of discontiguous regions used by an allocation */ 458ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_num_regions(struct block_allocation *alloc) 459ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 460ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 461ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 462ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 463ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 464ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i++; 465ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 466ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 467ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 468ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 469ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint block_allocation_len(struct block_allocation *alloc) 470ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 471ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 472ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.first; 473ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 474ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; reg != NULL; reg = reg->next) 475ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross i += reg->len; 476ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 477ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return i; 478ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 479ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 480ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the block number of the block'th block in an allocation */ 481ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_block(struct block_allocation *alloc, u32 block) 482ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 483ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.iter; 484ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block += alloc->list.partial_iter; 485ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 486ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 487ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 488ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 489ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 490ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 491ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 492ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 493ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 494ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_oob_block(struct block_allocation *alloc, u32 block) 495ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 496ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->oob_list.iter; 497ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block += alloc->oob_list.partial_iter; 498ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 499ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) { 500ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (block < reg->len) 501ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg->block + block; 502ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross block -= reg->len; 503ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 504ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 505ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 506ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 507ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Gets the starting block and length in blocks of the first region 508ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross of an allocation */ 509ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 510ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 511ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *block = alloc->list.iter->block; 512ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross *len = alloc->list.iter->len - alloc->list.partial_iter; 513ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 514ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 515ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move to the next region in an allocation */ 516ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid get_next_region(struct block_allocation *alloc) 517ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 518ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.iter->next; 519ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 520ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 521ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 522ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free blocks in a block group */ 523ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_blocks(u32 bg) 524ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 525ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_blocks; 526ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 527ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 528ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint last_region(struct block_allocation *alloc) 529ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 530ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (alloc->list.iter == NULL); 531ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 532ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 533ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid rewind_alloc(struct block_allocation *alloc) 534ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 535ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = alloc->list.first; 536ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 537ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 538ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 539ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 540ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 541ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = alloc->list.iter; 542ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *new; 543ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *tmp; 544ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 545ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg && len >= reg->len) { 546ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross len -= reg->len; 547ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 548ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 549ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 550ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL && len > 0) 551ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return NULL; 552ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 553ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (len > 0) { 554ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new = malloc(sizeof(struct region)); 555ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 556ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->bg = reg->bg; 557ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->block = reg->block + len; 558ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->len = reg->len - len; 559ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->next = reg->next; 560ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross new->prev = reg; 561ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 562ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->next = new; 563ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg->len = len; 564ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 565ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross tmp = alloc->list.iter; 566ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.iter = new; 567ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return tmp; 568ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } else { 569ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return reg; 570ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 571ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 572ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 573ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Splits an allocation into two allocations. The returned allocation will 574ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross point to the first half, and the original allocation ptr will point to the 575ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross second half. */ 576ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 577ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 578ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* First make sure there is a split at the current ptr */ 579ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross do_split_allocation(alloc, alloc->list.partial_iter); 580ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 581ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross /* Then split off len blocks */ 582ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *middle = do_split_allocation(alloc, len); 583ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross alloc->list.partial_iter = 0; 584ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return middle; 585ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 586ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 587ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Reserve the next blocks for oob data (indirect or extent blocks) */ 588ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 589ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 590ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *oob = split_allocation(alloc, blocks); 591ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next; 592ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 593ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (oob == NULL) 594ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 595ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 596ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (oob && oob != alloc->list.iter) { 597ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross next = oob->next; 598ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_remove(&alloc->list, oob); 599ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, oob); 600ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross oob = next; 601ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 602ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 603ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 604ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 605ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 606ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstatic int advance_list_ptr(struct region_list *list, int blocks) 607ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 608ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = list->iter; 609ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 610ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg != NULL && blocks > 0) { 611ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg->len > list->partial_iter + blocks) { 612ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter += blocks; 613ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 614ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 615ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 616ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross blocks -= (reg->len - list->partial_iter); 617ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross list->partial_iter = 0; 618ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = reg->next; 619ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 620ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 621ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (blocks > 0) 622ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 623ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 624ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 625ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 626ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 627ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Move the allocation pointer forward */ 628ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_blocks(struct block_allocation *alloc, int blocks) 629ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 630ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->list, blocks); 631ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 632ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 633ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint advance_oob_blocks(struct block_allocation *alloc, int blocks) 634ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 635ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return advance_list_ptr(&alloc->oob_list, blocks); 636ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 637ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 638ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossint append_oob_allocation(struct block_allocation *alloc, u32 len) 639ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 640ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg = do_allocate(len); 641ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 642ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (reg == NULL) { 643ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross error("failed to allocate %d blocks", len); 644ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return -1; 645ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 646ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 647ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (; reg; reg = reg->next) 648ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross region_list_append(&alloc->oob_list, reg); 649ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 650ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return 0; 651ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 652ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 653ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns an ext4_inode structure for an inode number */ 654ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossstruct ext4_inode *get_inode(u32 inode) 655ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 656ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode -= 1; 657ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = inode / info.inodes_per_group; 658ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode %= info.inodes_per_group; 659ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 660ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross allocate_bg_inode_table(&aux_info.bgs[bg]); 661ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode 662ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross * info.inode_size); 663ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 664ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 665ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Mark the first len inodes in a block group as used */ 666ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 reserve_inodes(int bg, u32 num) 667ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 668ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int i; 669ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 670ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 671ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (get_free_inodes(bg) < num) 672ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 673ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 674ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (i = 0; i < num; i++) { 675ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode + i - 1; 676ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 677ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 678ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 679ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = aux_info.bgs[bg].first_free_inode; 680ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 681ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].first_free_inode += num; 682ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].free_inodes -= num; 683ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 684ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return inode; 685ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 686ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 687ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the first free inode number 688ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross TODO: Inodes should be allocated in the block group of the data? */ 689ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 allocate_inode() 690ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 691ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross unsigned int bg; 692ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross u32 inode; 693ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 694ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross for (bg = 0; bg < aux_info.groups; bg++) { 695ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross inode = reserve_inodes(bg, 1); 696ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross if (inode != EXT4_ALLOCATE_FAILED) 697ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return bg * info.inodes_per_group + inode; 698ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 699ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 700ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return EXT4_ALLOCATE_FAILED; 701ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 702ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 703ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of free inodes in a block group */ 704ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu32 get_free_inodes(u32 bg) 705ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 706ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].free_inodes; 707ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 708ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 709ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Increments the directory count of the block group that contains inode */ 710ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid add_directory(u32 inode) 711ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 712ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross int bg = (inode - 1) / info.inodes_per_group; 713ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross aux_info.bgs[bg].used_dirs += 1; 714ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 715ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 716ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Returns the number of inodes in a block group that are directories */ 717ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossu16 get_directories(int bg) 718ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 719ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross return aux_info.bgs[bg].used_dirs; 720ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 721ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 722ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross/* Frees the memory used by a linked list of allocation regions */ 723ec0a2e83dc66d67addeb90e83144187691852a3eColin Crossvoid free_alloc(struct block_allocation *alloc) 724ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross{ 725ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *reg; 726ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 727ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->list.first; 728ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 729ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 730ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 731ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 732ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 733ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 734ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = alloc->oob_list.first; 735ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross while (reg) { 736ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross struct region *next = reg->next; 737ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(reg); 738ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross reg = next; 739ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross } 740ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross 741ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross free(alloc); 742ec0a2e83dc66d67addeb90e83144187691852a3eColin Cross} 743