18642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* 28642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * Copyright (C) 2010 The Android Open Source Project 38642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * 48642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * Licensed under the Apache License, Version 2.0 (the "License"); 58642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * you may not use this file except in compliance with the License. 68642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * You may obtain a copy of the License at 78642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * 88642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * http://www.apache.org/licenses/LICENSE-2.0 98642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * 108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * Unless required by applicable law or agreed to in writing, software 118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * distributed under the License is distributed on an "AS IS" BASIS, 128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * See the License for the specific language governing permissions and 148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * limitations under the License. 158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland */ 168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include <stdio.h> 188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include <stdlib.h> 198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include "ext4_utils.h" 218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include "allocate.h" 228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include "backed_block.h" 238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#include "ext4.h" 248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct region_list { 268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *first; 278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *last; 288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *iter; 298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 partial_iter; 308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland}; 318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct block_allocation { 338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region_list list; 348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region_list oob_list; 358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland}; 368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct region { 388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block; 398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 len; 408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int bg; 418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *next; 428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *prev; 438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland}; 448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct block_group_info { 468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 first_block; 478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int header_blocks; 488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int data_blocks_used; 498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int has_superblock; 508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u8 *bitmaps; 518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u8 *block_bitmap; 528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u8 *inode_bitmap; 538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u8 *inode_table; 548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 free_blocks; 558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 first_free_block; 568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 free_inodes; 578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 first_free_inode; 588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u16 used_dirs; 598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland}; 608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct block_allocation *create_allocation() 628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.first = NULL; 658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.last = NULL; 668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->oob_list.first = NULL; 678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->oob_list.last = NULL; 688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = NULL; 698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->oob_list.iter = NULL; 718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->oob_list.partial_iter = 0; 728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return alloc; 738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void region_list_remove(struct region_list *list, struct region *reg) 768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg->prev) 788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev->next = reg->next; 798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg->next) 818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next->prev = reg->prev; 828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (list->first == reg) 848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->first = reg->next; 858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (list->last == reg) 878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->last = reg->prev; 888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = NULL; 918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void region_list_append(struct region_list *list, struct region *reg) 948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (list->first == NULL) { 968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->first = reg; 978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->last = reg; 988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->iter = reg; 998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->partial_iter = 0; 1008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = NULL; 1018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } else { 1028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->last->next = reg; 1038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = list->last; 1048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->last = reg; 1058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 1068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 1078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#if 0 1108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void dump_starting_from(struct region *reg) 1118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; reg; reg = reg->next) { 1138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland printf("%p: Blocks %d-%d (%d)\n", reg, 1148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->bg * info.blocks_per_group + reg->block, 1158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->bg * info.blocks_per_group + reg->block + reg->len - 1, 1168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->len); 1178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 1188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void dump_region_lists(struct block_allocation *alloc) { 1218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland printf("Main list:\n"); 1238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland dump_starting_from(alloc->list.first); 1248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland printf("OOB list:\n"); 1268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland dump_starting_from(alloc->oob_list.first); 1278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland#endif 1298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid append_region(struct block_allocation *alloc, 1318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block, u32 len, int bg_num) 1328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg; 1348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = malloc(sizeof(struct region)); 1358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->block = block; 1368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->len = len; 1378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->bg = bg_num; 1388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 1398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland region_list_append(&alloc->list, reg); 1418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void allocate_bg_inode_table(struct block_group_info *bg) 1448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bg->inode_table != NULL) 1468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return; 1478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = bg->first_block + 2; 1498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bg->has_superblock) 1518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block += aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks + 1; 1528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 1548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bg->inode_table == NULL) 1558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland critical_error_errno("calloc"); 1568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland queue_data_block(bg->inode_table, aux_info.inode_table_blocks 1588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland * info.block_size, block); 1598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 1628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bitmap[bit / 8] & 1 << (bit % 8)) 1648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 1; 1658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bitmap[bit / 8] |= 1 << (bit % 8); 1678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 1688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 1718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int ret = bitmap[bit / 8]; 1738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bitmap[bit / 8] = 0xFF; 1748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return ret; 1758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 1768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Marks a the first num_blocks blocks in a block group as used, and accounts 1788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for them in the block group free block info. */ 1798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic int reserve_blocks(struct block_group_info *bg, u32 start, u32 num) 1808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 1818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i = 0; 1828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = start; 1848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (num > bg->free_blocks) 1858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 1868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < num && block % 8 != 0; i++, block++) { 1888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bitmap_set_bit(bg->block_bitmap, block)) { 1898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("attempted to reserve already reserved block"); 1908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 1918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 1928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 1938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; i + 8 <= (num & ~7); i += 8, block += 8) { 1958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bitmap_set_8_bits(bg->block_bitmap, block)) { 1968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("attempted to reserve already reserved block"); 1978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 1988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 1998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; i < num; i++, block++) { 2028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bitmap_set_bit(bg->block_bitmap, block)) { 2038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("attempted to reserve already reserved block"); 2048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 2058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->free_blocks -= num; 2098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (start == bg->first_free_block) 2108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->first_free_block = start + num; 2118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 2138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 2148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void free_blocks(struct block_group_info *bg, u32 num_blocks) 2168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 2178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 2188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = bg->first_free_block - 1; 2198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < num_blocks; i++, block--) 2208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 2218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->free_blocks += num_blocks; 2228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->first_free_block -= num_blocks; 2238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 2248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Reduces an existing allocation by len blocks by return the last blocks 2268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland to the free pool in their block group. Assumes that the blocks being 2278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland returned were the last ones allocated out of the block group */ 2288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid reduce_allocation(struct block_allocation *alloc, u32 len) 2298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 2308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (len) { 2318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *last_reg = alloc->list.last; 2328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (last_reg->len > len) { 2348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free_blocks(&aux_info.bgs[last_reg->bg], len); 2358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland last_reg->len -= len; 2368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland len = 0; 2378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } else { 2388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->list.last->prev; 2398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len); 2408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland len -= last_reg->len; 2418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg) { 2428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 2438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } else { 2448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.first = NULL; 2458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.last = NULL; 2468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = NULL; 2478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 2488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(last_reg); 2508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 2528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 2538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic void init_bg(struct block_group_info *bg, unsigned int i) 2558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 2568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int header_blocks = 2 + aux_info.inode_table_blocks; 2578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->has_superblock = ext4_bg_has_super_block(i); 2598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bg->has_superblock) 2618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland header_blocks += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; 2628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->bitmaps = calloc(info.block_size, 2); 2648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->block_bitmap = bg->bitmaps; 2658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->inode_bitmap = bg->bitmaps + info.block_size; 2668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->header_blocks = header_blocks; 2688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 2698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = bg->first_block; 2718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (bg->has_superblock) 2728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks; 2738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland queue_data_block(bg->bitmaps, 2 * info.block_size, block); 2748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->data_blocks_used = 0; 2768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->free_blocks = info.blocks_per_group; 2778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->first_free_block = 0; 2788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->free_inodes = info.inodes_per_group; 2798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg->first_free_inode = 1; 2808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) 2828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 2838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 2858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (overrun > 0) 2868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reserve_blocks(bg, info.blocks_per_group - overrun, overrun); 2878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 2888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid block_allocator_init() 2908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 2918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 2928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 2948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (aux_info.bgs == NULL) 2958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland critical_error_errno("calloc"); 2968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < aux_info.groups; i++) 2988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland init_bg(&aux_info.bgs[i], i); 2998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 3008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid block_allocator_free() 3028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 3038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 3048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < aux_info.groups; i++) { 3068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(aux_info.bgs[i].bitmaps); 3078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(aux_info.bgs[i].inode_table); 3088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(aux_info.bgs); 3108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 3118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) 3138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 3148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (get_free_blocks(bg_num) < len) 3158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 3168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = aux_info.bgs[bg_num].first_free_block; 3188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct block_group_info *bg = &aux_info.bgs[bg_num]; 3198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reserve_blocks(bg, bg->first_free_block, len) < 0) { 3208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("failed to reserve %u blocks in block group %u\n", len, bg_num); 3218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 3228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs[bg_num].data_blocks_used += len; 3258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return bg->first_block + block; 3278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 3288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic struct region *ext4_allocate_contiguous_blocks(u32 len) 3308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 3318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 3328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg; 3338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < aux_info.groups; i++) { 3358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = ext4_allocate_blocks_from_block_group(len, i); 3368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (block != EXT4_ALLOCATE_FAILED) { 3388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = malloc(sizeof(struct region)); 3398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->block = block; 3408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->len = len; 3418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 3428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = NULL; 3438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->bg = i; 3448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg; 3458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 3498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 3508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Allocate a single block and return its block number */ 3528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 allocate_block() 3538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 3548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 3558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < aux_info.groups; i++) { 3568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block = ext4_allocate_blocks_from_block_group(1, i); 3578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (block != EXT4_ALLOCATE_FAILED) 3598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return block; 3608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 3638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 3648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic struct region *ext4_allocate_partial(u32 len) 3668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 3678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 3688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg; 3698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < aux_info.groups; i++) { 3718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (aux_info.bgs[i].data_blocks_used == 0) { 3728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 bg_len = aux_info.bgs[i].free_blocks; 3738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 block; 3748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (len <= bg_len) { 3768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland /* If the requested length would fit in a block group, 3778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland use the regular allocator to try to fit it in a partially 3788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland used block group */ 3798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland bg_len = len; 3808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = ext4_allocate_contiguous_blocks(len); 3818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } else { 3828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block = ext4_allocate_blocks_from_block_group(bg_len, i); 3838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (block == EXT4_ALLOCATE_FAILED) { 3858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("failed to allocate %d blocks in block group %d", bg_len, i); 3868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 3878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = malloc(sizeof(struct region)); 3908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->block = block; 3918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->len = bg_len; 3928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = NULL; 3938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = NULL; 3948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->bg = i; 3958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg; 3988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 3998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 4008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 4018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic struct region *ext4_allocate_multiple_contiguous_blocks(u32 len) 4048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *first_reg = NULL; 4068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *prev_reg = NULL; 4078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg; 4088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (len > 0) { 4108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = ext4_allocate_partial(len); 4118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg == NULL) 4128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 4138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (first_reg == NULL) 4158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland first_reg = reg; 4168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (prev_reg) { 4188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland prev_reg->next = reg; 4198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->prev = prev_reg; 4208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 4218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland prev_reg = reg; 4238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland len -= reg->len; 4248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 4258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return first_reg; 4278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct region *do_allocate(u32 len) 4308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = ext4_allocate_contiguous_blocks(len); 4328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg == NULL) 4348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = ext4_allocate_multiple_contiguous_blocks(len); 4358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg; 4378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Allocate len blocks. The blocks may be spread across multiple block groups, 4408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland and are returned in a linked list of the blocks in each block group. The 4418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland allocation algorithm is: 4428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 1. Try to allocate the entire block len in each block group 4438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 2. If the request doesn't fit in any block group, allocate as many 4448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland blocks as possible into each block group that is completely empty 4458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 3. Put the last set of blocks in the first block group they fit in 4468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland*/ 4478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct block_allocation *allocate_blocks(u32 len) 4488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = do_allocate(len); 4508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg == NULL) 4528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 4538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct block_allocation *alloc = create_allocation(); 4558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.first = reg; 4568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.last = reg; 4578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = alloc->list.first; 4588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 4598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return alloc; 4608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the number of discontiguous regions used by an allocation */ 4638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint block_allocation_num_regions(struct block_allocation *alloc) 4648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 4668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->list.first; 4678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; reg != NULL; reg = reg->next) 4698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland i++; 4708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return i; 4728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint block_allocation_len(struct block_allocation *alloc) 4758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 4778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->list.first; 4788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; reg != NULL; reg = reg->next) 4808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland i += reg->len; 4818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return i; 4838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the block number of the block'th block in an allocation */ 4868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 get_block(struct block_allocation *alloc, u32 block) 4878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 4888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->list.iter; 4898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block += alloc->list.partial_iter; 4908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; reg; reg = reg->next) { 4928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (block < reg->len) 4938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg->block + block; 4948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block -= reg->len; 4958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 4968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 4978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 4988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 4998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 get_oob_block(struct block_allocation *alloc, u32 block) 5008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->oob_list.iter; 5028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block += alloc->oob_list.partial_iter; 5038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; reg; reg = reg->next) { 5058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (block < reg->len) 5068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg->block + block; 5078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland block -= reg->len; 5088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 5098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 5108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Gets the starting block and length in blocks of the first region 5138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland of an allocation */ 5148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 5158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland *block = alloc->list.iter->block; 5178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland *len = alloc->list.iter->len - alloc->list.partial_iter; 5188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Move to the next region in an allocation */ 5218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid get_next_region(struct block_allocation *alloc) 5228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = alloc->list.iter->next; 5248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 5258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the number of free blocks in a block group */ 5288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 get_free_blocks(u32 bg) 5298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return aux_info.bgs[bg].free_blocks; 5318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint last_region(struct block_allocation *alloc) 5348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return (alloc->list.iter == NULL); 5368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid rewind_alloc(struct block_allocation *alloc) 5398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = alloc->list.first; 5418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 5428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 5458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = alloc->list.iter; 5478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *new; 5488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *tmp; 5498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (reg && len >= reg->len) { 5518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland len -= reg->len; 5528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = reg->next; 5538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 5548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg == NULL && len > 0) 5568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return NULL; 5578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (len > 0) { 5598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new = malloc(sizeof(struct region)); 5608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new->bg = reg->bg; 5628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new->block = reg->block + len; 5638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new->len = reg->len - len; 5648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new->next = reg->next; 5658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland new->prev = reg; 5668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->next = new; 5688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg->len = len; 5698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland tmp = alloc->list.iter; 5718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.iter = new; 5728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return tmp; 5738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } else { 5748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return reg; 5758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 5768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Splits an allocation into two allocations. The returned allocation will 5798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland point to the first half, and the original allocation ptr will point to the 5808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland second half. */ 5818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 5828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland /* First make sure there is a split at the current ptr */ 5848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland do_split_allocation(alloc, alloc->list.partial_iter); 5858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland /* Then split off len blocks */ 5878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *middle = do_split_allocation(alloc, len); 5888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland alloc->list.partial_iter = 0; 5898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return middle; 5908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 5918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Reserve the next blocks for oob data (indirect or extent blocks) */ 5938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 5948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 5958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *oob = split_allocation(alloc, blocks); 5968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *next; 5978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 5988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (oob == NULL) 5998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 6008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (oob && oob != alloc->list.iter) { 6028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland next = oob->next; 6038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland region_list_remove(&alloc->list, oob); 6048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland region_list_append(&alloc->oob_list, oob); 6058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland oob = next; 6068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 6078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 6098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstatic int advance_list_ptr(struct region_list *list, int blocks) 6128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = list->iter; 6148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (reg != NULL && blocks > 0) { 6168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg->len > list->partial_iter + blocks) { 6178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->partial_iter += blocks; 6188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 6198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 6208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland blocks -= (reg->len - list->partial_iter); 6228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland list->partial_iter = 0; 6238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = reg->next; 6248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 6258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (blocks > 0) 6278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 6288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 6308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Move the allocation pointer forward */ 6338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint advance_blocks(struct block_allocation *alloc, int blocks) 6348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return advance_list_ptr(&alloc->list, blocks); 6368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint advance_oob_blocks(struct block_allocation *alloc, int blocks) 6398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return advance_list_ptr(&alloc->oob_list, blocks); 6418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandint append_oob_allocation(struct block_allocation *alloc, u32 len) 6448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg = do_allocate(len); 6468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (reg == NULL) { 6488642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland error("failed to allocate %d blocks", len); 6498642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return -1; 6508642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 6518642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6528642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (; reg; reg = reg->next) 6538642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland region_list_append(&alloc->oob_list, reg); 6548642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6558642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return 0; 6568642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6578642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6588642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns an ext4_inode structure for an inode number */ 6598642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandstruct ext4_inode *get_inode(u32 inode) 6608642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6618642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland inode -= 1; 6628642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int bg = inode / info.inodes_per_group; 6638642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland inode %= info.inodes_per_group; 6648642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6658642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland allocate_bg_inode_table(&aux_info.bgs[bg]); 6668642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6678642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland info.inode_size); 6688642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6698642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6708642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Mark the first len inodes in a block group as used */ 6718642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 reserve_inodes(int bg, u32 num) 6728642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6738642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int i; 6748642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 inode; 6758642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6768642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (get_free_inodes(bg) < num) 6778642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 6788642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6798642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (i = 0; i < num; i++) { 6808642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland inode = aux_info.bgs[bg].first_free_inode + i - 1; 6818642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 6828642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 6838642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6848642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland inode = aux_info.bgs[bg].first_free_inode; 6858642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6868642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs[bg].first_free_inode += num; 6878642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs[bg].free_inodes -= num; 6888642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6898642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return inode; 6908642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 6918642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6928642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the first free inode number 6938642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland TODO: Inodes should be allocated in the block group of the data? */ 6948642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 allocate_inode() 6958642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 6968642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland unsigned int bg; 6978642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland u32 inode; 6988642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 6998642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland for (bg = 0; bg < aux_info.groups; bg++) { 7008642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland inode = reserve_inodes(bg, 1); 7018642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland if (inode != EXT4_ALLOCATE_FAILED) 7028642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return bg * info.inodes_per_group + inode; 7038642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 7048642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7058642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return EXT4_ALLOCATE_FAILED; 7068642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 7078642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7088642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the number of free inodes in a block group */ 7098642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu32 get_free_inodes(u32 bg) 7108642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 7118642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return aux_info.bgs[bg].free_inodes; 7128642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 7138642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7148642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Increments the directory count of the block group that contains inode */ 7158642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid add_directory(u32 inode) 7168642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 7178642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland int bg = (inode - 1) / info.inodes_per_group; 7188642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland aux_info.bgs[bg].used_dirs += 1; 7198642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 7208642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7218642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Returns the number of inodes in a block group that are directories */ 7228642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandu16 get_directories(int bg) 7238642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 7248642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland return aux_info.bgs[bg].used_dirs; 7258642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 7268642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7278642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland/* Frees the memory used by a linked list of allocation regions */ 7288642b7fba54727a38f751516bcdc452fb09ef610Brian Swetlandvoid free_alloc(struct block_allocation *alloc) 7298642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland{ 7308642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *reg; 7318642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7328642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = alloc->list.first; 7338642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (reg) { 7348642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *next = reg->next; 7358642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(reg); 7368642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = next; 7378642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 7388642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7398642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = alloc->oob_list.first; 7408642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland while (reg) { 7418642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland struct region *next = reg->next; 7428642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(reg); 7438642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland reg = next; 7448642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland } 7458642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland 7468642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland free(alloc); 7478642b7fba54727a38f751516bcdc452fb09ef610Brian Swetland} 748