1 /* 2 * alloc_tables.c --- Allocate tables for a newly initialized 3 * filesystem. Used by mke2fs when initializing a filesystem 4 * 5 * Copyright (C) 1996 Theodore Ts'o. 6 * 7 * %Begin-Header% 8 * This file may be redistributed under the terms of the GNU Library 9 * General Public License, version 2. 10 * %End-Header% 11 */ 12 13 #include "config.h" 14 #include <stdio.h> 15 #include <string.h> 16 #if HAVE_UNISTD_H 17 #include <unistd.h> 18 #endif 19 #include <fcntl.h> 20 #include <time.h> 21 #if HAVE_SYS_STAT_H 22 #include <sys/stat.h> 23 #endif 24 #if HAVE_SYS_TYPES_H 25 #include <sys/types.h> 26 #endif 27 28 #include "ext2_fs.h" 29 #include "ext2fs.h" 30 #include "ext2fsP.h" 31 32 /* 33 * This routine searches for free blocks that can allocate a full 34 * group of bitmaps or inode tables for a flexbg group. Returns the 35 * block number with a correct offset were the bitmaps and inode 36 * tables can be allocated continously and in order. 37 */ 38 static blk64_t flexbg_offset(ext2_filsys fs, dgrp_t group, blk64_t start_blk, 39 ext2fs_block_bitmap bmap, int rem_grp, 40 int elem_size) 41 { 42 int flexbg, flexbg_size, size; 43 blk64_t last_blk, first_free = 0; 44 dgrp_t last_grp; 45 46 flexbg_size = 1 << fs->super->s_log_groups_per_flex; 47 flexbg = group / flexbg_size; 48 size = rem_grp * elem_size; 49 50 if (size > (int) (fs->super->s_blocks_per_group / 4)) 51 size = (int) fs->super->s_blocks_per_group / 4; 52 53 /* 54 * Don't do a long search if the previous block search is still valid, 55 * but skip minor obstructions such as group descriptor backups. 56 */ 57 if (start_blk && start_blk < ext2fs_blocks_count(fs->super) && 58 ext2fs_get_free_blocks2(fs, start_blk, start_blk + size, elem_size, 59 bmap, &first_free) == 0) 60 return first_free; 61 62 start_blk = ext2fs_group_first_block2(fs, flexbg_size * flexbg); 63 last_grp = group | (flexbg_size - 1); 64 if (last_grp > fs->group_desc_count-1) 65 last_grp = fs->group_desc_count-1; 66 last_blk = ext2fs_group_last_block2(fs, last_grp); 67 68 /* Find the first available block */ 69 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, size, 70 bmap, &first_free) == 0) 71 return first_free; 72 73 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, elem_size, 74 bmap, &first_free) == 0) 75 return first_free; 76 77 if (ext2fs_get_free_blocks2(fs, 0, last_blk, elem_size, bmap, 78 &first_free) == 0) 79 return first_free; 80 81 return first_free; 82 } 83 84 errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group, 85 ext2fs_block_bitmap bmap) 86 { 87 errcode_t retval; 88 blk64_t group_blk, start_blk, last_blk, new_blk; 89 dgrp_t last_grp = 0; 90 int rem_grps = 0, flexbg_size = 0, table_offset = 0; 91 92 group_blk = ext2fs_group_first_block2(fs, group); 93 last_blk = ext2fs_group_last_block2(fs, group); 94 95 if (!bmap) 96 bmap = fs->block_map; 97 98 if (ext2fs_has_feature_flex_bg(fs->super) && 99 fs->super->s_log_groups_per_flex) { 100 flexbg_size = 1 << fs->super->s_log_groups_per_flex; 101 last_grp = group | (flexbg_size - 1); 102 if (last_grp > fs->group_desc_count-1) 103 last_grp = fs->group_desc_count-1; 104 rem_grps = last_grp - group + 1; 105 } 106 107 /* 108 * Allocate the block and inode bitmaps, if necessary 109 */ 110 if (fs->stride) { 111 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk, 112 1, bmap, &start_blk); 113 if (retval) 114 return retval; 115 start_blk += fs->inode_blocks_per_group; 116 start_blk += ((fs->stride * group) % 117 (last_blk - start_blk + 1)); 118 if (start_blk >= last_blk) 119 start_blk = group_blk; 120 } else 121 start_blk = group_blk; 122 123 if (flexbg_size) { 124 blk64_t prev_block = 0; 125 126 table_offset = flexbg_size; 127 if (group % flexbg_size) 128 prev_block = ext2fs_block_bitmap_loc(fs, group - 1) + 1; 129 else if (last_grp == fs->group_desc_count-1) { 130 /* 131 * If we are allocating for the last flex_bg 132 * keep the metadata tables contiguous 133 */ 134 table_offset = last_grp & (flexbg_size - 1); 135 if (table_offset == 0) 136 table_offset = flexbg_size; 137 else 138 table_offset++; 139 } 140 /* FIXME: Take backup group descriptor blocks into account 141 * if the flexbg allocations will grow to overlap them... */ 142 start_blk = flexbg_offset(fs, group, prev_block, bmap, 143 rem_grps, 1); 144 last_blk = ext2fs_group_last_block2(fs, last_grp); 145 } 146 147 if (!ext2fs_block_bitmap_loc(fs, group)) { 148 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 149 1, bmap, &new_blk); 150 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 151 retval = ext2fs_get_free_blocks2(fs, group_blk, 152 last_blk, 1, bmap, &new_blk); 153 if (retval) 154 return retval; 155 ext2fs_mark_block_bitmap2(bmap, new_blk); 156 ext2fs_block_bitmap_loc_set(fs, group, new_blk); 157 if (flexbg_size) { 158 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 159 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 160 ext2fs_free_blocks_count_add(fs->super, -1); 161 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 162 ext2fs_group_desc_csum_set(fs, gr); 163 } 164 } 165 166 if (flexbg_size) { 167 blk64_t prev_block = 0; 168 if (group % flexbg_size) 169 prev_block = ext2fs_inode_bitmap_loc(fs, group - 1) + 1; 170 else 171 prev_block = ext2fs_block_bitmap_loc(fs, group) + 172 table_offset; 173 /* FIXME: Take backup group descriptor blocks into account 174 * if the flexbg allocations will grow to overlap them... */ 175 start_blk = flexbg_offset(fs, group, prev_block, bmap, 176 rem_grps, 1); 177 last_blk = ext2fs_group_last_block2(fs, last_grp); 178 } 179 180 if (!ext2fs_inode_bitmap_loc(fs, group)) { 181 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 182 1, bmap, &new_blk); 183 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 184 retval = ext2fs_get_free_blocks2(fs, group_blk, 185 last_blk, 1, bmap, &new_blk); 186 if (retval) 187 return retval; 188 ext2fs_mark_block_bitmap2(bmap, new_blk); 189 ext2fs_inode_bitmap_loc_set(fs, group, new_blk); 190 if (flexbg_size) { 191 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 192 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 193 ext2fs_free_blocks_count_add(fs->super, -1); 194 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 195 ext2fs_group_desc_csum_set(fs, gr); 196 } 197 } 198 199 /* 200 * Allocate the inode table 201 */ 202 if (flexbg_size) { 203 blk64_t prev_block = 0; 204 205 if (group % flexbg_size) 206 prev_block = ext2fs_inode_table_loc(fs, group - 1) + 207 fs->inode_blocks_per_group; 208 else 209 prev_block = ext2fs_inode_bitmap_loc(fs, group) + 210 table_offset; 211 212 /* FIXME: Take backup group descriptor blocks into account 213 * if the flexbg allocations will grow to overlap them... */ 214 group_blk = flexbg_offset(fs, group, prev_block, bmap, 215 rem_grps, fs->inode_blocks_per_group); 216 last_blk = ext2fs_group_last_block2(fs, last_grp); 217 } 218 219 if (!ext2fs_inode_table_loc(fs, group)) { 220 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk, 221 fs->inode_blocks_per_group, 222 bmap, &new_blk); 223 if (retval) 224 return retval; 225 if (flexbg_size) 226 ext2fs_block_alloc_stats_range(fs, new_blk, 227 fs->inode_blocks_per_group, +1); 228 else 229 ext2fs_mark_block_bitmap_range2(fs->block_map, 230 new_blk, fs->inode_blocks_per_group); 231 ext2fs_inode_table_loc_set(fs, group, new_blk); 232 } 233 ext2fs_group_desc_csum_set(fs, group); 234 return 0; 235 } 236 237 errcode_t ext2fs_allocate_tables(ext2_filsys fs) 238 { 239 errcode_t retval; 240 dgrp_t i; 241 struct ext2fs_numeric_progress_struct progress; 242 243 if (fs->progress_ops && fs->progress_ops->init) 244 (fs->progress_ops->init)(fs, &progress, NULL, 245 fs->group_desc_count); 246 247 for (i = 0; i < fs->group_desc_count; i++) { 248 if (fs->progress_ops && fs->progress_ops->update) 249 (fs->progress_ops->update)(fs, &progress, i); 250 retval = ext2fs_allocate_group_table(fs, i, fs->block_map); 251 if (retval) 252 return retval; 253 } 254 if (fs->progress_ops && fs->progress_ops->close) 255 (fs->progress_ops->close)(fs, &progress, NULL); 256 return 0; 257 } 258 259
