alloc_tables.c revision d1154eb460efe588eaed3d439c1caaca149fa362
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 */ 38static 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 / 8)) 51 size = (int) fs->super->s_blocks_per_group / 8; 52 53 /* 54 * Don't do a long search if the previous block 55 * search is still valid. 56 */ 57 if (start_blk && ext2fs_test_block_bitmap_range2(bmap, start_blk, 58 elem_size)) 59 return start_blk; 60 61 start_blk = ext2fs_group_first_block2(fs, flexbg_size * flexbg); 62 last_grp = group | (flexbg_size - 1); 63 if (last_grp > fs->group_desc_count-1) 64 last_grp = fs->group_desc_count-1; 65 last_blk = ext2fs_group_last_block2(fs, last_grp); 66 67 /* Find the first available block */ 68 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, size, 69 bmap, &first_free) == 0) 70 return first_free; 71 72 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, elem_size, 73 bmap, &first_free) == 0) 74 return first_free; 75 76 if (ext2fs_get_free_blocks2(fs, 0, last_blk, elem_size, bmap, 77 &first_free) == 0) 78 return first_free; 79 80 return first_free; 81} 82 83errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group, 84 ext2fs_block_bitmap bmap) 85{ 86 unsigned int j; 87 errcode_t retval; 88 blk64_t group_blk, start_blk, last_blk, new_blk, blk; 89 dgrp_t last_grp = 0; 90 int rem_grps = 0, flexbg_size = 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 (EXT2_HAS_INCOMPAT_FEATURE(fs->super, 99 EXT4_FEATURE_INCOMPAT_FLEX_BG) && 100 fs->super->s_log_groups_per_flex) { 101 flexbg_size = 1 << fs->super->s_log_groups_per_flex; 102 last_grp = group | (flexbg_size - 1); 103 if (last_grp > fs->group_desc_count-1) 104 last_grp = fs->group_desc_count-1; 105 rem_grps = last_grp - group + 1; 106 } 107 108 /* 109 * Allocate the block and inode bitmaps, if necessary 110 */ 111 if (fs->stride) { 112 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk, 113 1, bmap, &start_blk); 114 if (retval) 115 return retval; 116 start_blk += fs->inode_blocks_per_group; 117 start_blk += ((fs->stride * group) % 118 (last_blk - start_blk + 1)); 119 if (start_blk >= last_blk) 120 start_blk = group_blk; 121 } else 122 start_blk = group_blk; 123 124 if (flexbg_size) { 125 blk64_t prev_block = 0; 126 127 if (group % flexbg_size) 128 prev_block = ext2fs_block_bitmap_loc(fs, group - 1) + 1; 129 start_blk = flexbg_offset(fs, group, prev_block, bmap, 130 rem_grps, 1); 131 last_blk = ext2fs_group_last_block2(fs, last_grp); 132 } 133 134 if (!ext2fs_block_bitmap_loc(fs, group)) { 135 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 136 1, bmap, &new_blk); 137 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 138 retval = ext2fs_get_free_blocks2(fs, group_blk, 139 last_blk, 1, bmap, &new_blk); 140 if (retval) 141 return retval; 142 ext2fs_mark_block_bitmap2(bmap, new_blk); 143 ext2fs_block_bitmap_loc_set(fs, group, new_blk); 144 if (flexbg_size) { 145 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 146 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 147 ext2fs_free_blocks_count_add(fs->super, -1); 148 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 149 ext2fs_group_desc_csum_set(fs, gr); 150 } 151 } 152 153 if (flexbg_size) { 154 blk64_t prev_block = 0; 155 if (group % flexbg_size) 156 prev_block = ext2fs_inode_bitmap_loc(fs, group - 1) + 1; 157 else 158 prev_block = ext2fs_block_bitmap_loc(fs, group) + 159 flexbg_size; 160 start_blk = flexbg_offset(fs, group, prev_block, bmap, 161 rem_grps, 1); 162 last_blk = ext2fs_group_last_block2(fs, last_grp); 163 } 164 165 if (!ext2fs_inode_bitmap_loc(fs, group)) { 166 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 167 1, bmap, &new_blk); 168 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 169 retval = ext2fs_get_free_blocks2(fs, group_blk, 170 last_blk, 1, bmap, &new_blk); 171 if (retval) 172 return retval; 173 ext2fs_mark_block_bitmap2(bmap, new_blk); 174 ext2fs_inode_bitmap_loc_set(fs, group, new_blk); 175 if (flexbg_size) { 176 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 177 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 178 ext2fs_free_blocks_count_add(fs->super, -1); 179 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 180 ext2fs_group_desc_csum_set(fs, gr); 181 } 182 } 183 184 /* 185 * Allocate the inode table 186 */ 187 if (flexbg_size) { 188 blk64_t prev_block = 0; 189 190 if (group % flexbg_size) 191 prev_block = ext2fs_inode_table_loc(fs, group - 1) + 192 fs->inode_blocks_per_group; 193 else 194 prev_block = ext2fs_inode_bitmap_loc(fs, group) + 195 flexbg_size; 196 197 group_blk = flexbg_offset(fs, group, prev_block, bmap, 198 rem_grps, fs->inode_blocks_per_group); 199 last_blk = ext2fs_group_last_block2(fs, last_grp); 200 } 201 202 if (!ext2fs_inode_table_loc(fs, group)) { 203 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk, 204 fs->inode_blocks_per_group, 205 bmap, &new_blk); 206 if (retval) 207 return retval; 208 for (j=0, blk = new_blk; 209 j < fs->inode_blocks_per_group; 210 j++, blk++) { 211 ext2fs_mark_block_bitmap2(bmap, blk); 212 if (flexbg_size) { 213 dgrp_t gr = ext2fs_group_of_blk2(fs, blk); 214 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 215 ext2fs_free_blocks_count_add(fs->super, -1); 216 ext2fs_bg_flags_clear(fs, gr, 217 EXT2_BG_BLOCK_UNINIT); 218 ext2fs_group_desc_csum_set(fs, gr); 219 } 220 } 221 ext2fs_inode_table_loc_set(fs, group, new_blk); 222 } 223 ext2fs_group_desc_csum_set(fs, group); 224 return 0; 225} 226 227errcode_t ext2fs_allocate_tables(ext2_filsys fs) 228{ 229 errcode_t retval; 230 dgrp_t i; 231 struct ext2fs_numeric_progress_struct progress; 232 233 ext2fs_numeric_progress_init(fs, &progress, NULL, 234 fs->group_desc_count); 235 236 for (i = 0; i < fs->group_desc_count; i++) { 237 ext2fs_numeric_progress_update(fs, &progress, i); 238 retval = ext2fs_allocate_group_table(fs, i, fs->block_map); 239 if (retval) 240 return retval; 241 } 242 ext2fs_numeric_progress_close(fs, &progress, NULL); 243 return 0; 244} 245 246