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 <stdio.h> 14#include <string.h> 15#if HAVE_UNISTD_H 16#include <unistd.h> 17#endif 18#include <fcntl.h> 19#include <time.h> 20#if HAVE_SYS_STAT_H 21#include <sys/stat.h> 22#endif 23#if HAVE_SYS_TYPES_H 24#include <sys/types.h> 25#endif 26 27#include "ext2_fs.h" 28#include "ext2fs.h" 29#include "ext2fsP.h" 30 31/* 32 * This routine searches for free blocks that can allocate a full 33 * group of bitmaps or inode tables for a flexbg group. Returns the 34 * block number with a correct offset were the bitmaps and inode 35 * tables can be allocated continously and in order. 36 */ 37static blk64_t flexbg_offset(ext2_filsys fs, dgrp_t group, blk64_t start_blk, 38 ext2fs_block_bitmap bmap, int rem_grp, 39 int elem_size) 40{ 41 int flexbg, flexbg_size, size; 42 blk64_t last_blk, first_free = 0; 43 dgrp_t last_grp; 44 45 flexbg_size = 1 << fs->super->s_log_groups_per_flex; 46 flexbg = group / flexbg_size; 47 size = rem_grp * elem_size; 48 49 if (size > (int) (fs->super->s_blocks_per_group / 8)) 50 size = (int) fs->super->s_blocks_per_group / 8; 51 52 /* 53 * Don't do a long search if the previous block 54 * search is still valid. 55 */ 56 if (start_blk && ext2fs_test_block_bitmap_range2(bmap, start_blk, 57 elem_size)) 58 return start_blk; 59 60 start_blk = ext2fs_group_first_block2(fs, flexbg_size * flexbg); 61 last_grp = group | (flexbg_size - 1); 62 if (last_grp > fs->group_desc_count-1) 63 last_grp = fs->group_desc_count-1; 64 last_blk = ext2fs_group_last_block2(fs, last_grp); 65 66 /* Find the first available block */ 67 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, size, 68 bmap, &first_free) == 0) 69 return first_free; 70 71 if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, elem_size, 72 bmap, &first_free) == 0) 73 return first_free; 74 75 if (ext2fs_get_free_blocks2(fs, 0, last_blk, elem_size, bmap, 76 &first_free) == 0) 77 return first_free; 78 79 return first_free; 80} 81 82errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group, 83 ext2fs_block_bitmap bmap) 84{ 85 unsigned int j; 86 errcode_t retval; 87 blk64_t group_blk, start_blk, last_blk, new_blk, blk; 88 dgrp_t last_grp = 0; 89 int rem_grps = 0, flexbg_size = 0; 90 91 group_blk = ext2fs_group_first_block2(fs, group); 92 last_blk = ext2fs_group_last_block2(fs, group); 93 94 if (!bmap) 95 bmap = fs->block_map; 96 97 if (EXT2_HAS_INCOMPAT_FEATURE(fs->super, 98 EXT4_FEATURE_INCOMPAT_FLEX_BG) && 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 if (group % flexbg_size) 127 prev_block = ext2fs_block_bitmap_loc(fs, group - 1) + 1; 128 start_blk = flexbg_offset(fs, group, prev_block, bmap, 129 rem_grps, 1); 130 last_blk = ext2fs_group_last_block2(fs, last_grp); 131 } 132 133 if (!ext2fs_block_bitmap_loc(fs, group)) { 134 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 135 1, bmap, &new_blk); 136 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 137 retval = ext2fs_get_free_blocks2(fs, group_blk, 138 last_blk, 1, bmap, &new_blk); 139 if (retval) 140 return retval; 141 ext2fs_mark_block_bitmap2(bmap, new_blk); 142 ext2fs_block_bitmap_loc_set(fs, group, new_blk); 143 if (flexbg_size) { 144 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 145 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 146 ext2fs_free_blocks_count_add(fs->super, -1); 147 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 148 ext2fs_group_desc_csum_set(fs, gr); 149 } 150 } 151 152 if (flexbg_size) { 153 blk64_t prev_block = 0; 154 if (group % flexbg_size) 155 prev_block = ext2fs_inode_bitmap_loc(fs, group - 1) + 1; 156 else 157 prev_block = ext2fs_block_bitmap_loc(fs, group) + 158 flexbg_size; 159 start_blk = flexbg_offset(fs, group, prev_block, bmap, 160 rem_grps, 1); 161 last_blk = ext2fs_group_last_block2(fs, last_grp); 162 } 163 164 if (!ext2fs_inode_bitmap_loc(fs, group)) { 165 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk, 166 1, bmap, &new_blk); 167 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL) 168 retval = ext2fs_get_free_blocks2(fs, group_blk, 169 last_blk, 1, bmap, &new_blk); 170 if (retval) 171 return retval; 172 ext2fs_mark_block_bitmap2(bmap, new_blk); 173 ext2fs_inode_bitmap_loc_set(fs, group, new_blk); 174 if (flexbg_size) { 175 dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk); 176 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 177 ext2fs_free_blocks_count_add(fs->super, -1); 178 ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT); 179 ext2fs_group_desc_csum_set(fs, gr); 180 } 181 } 182 183 /* 184 * Allocate the inode table 185 */ 186 if (flexbg_size) { 187 blk64_t prev_block = 0; 188 189 if (group % flexbg_size) 190 prev_block = ext2fs_inode_table_loc(fs, group - 1) + 191 fs->inode_blocks_per_group; 192 else 193 prev_block = ext2fs_inode_bitmap_loc(fs, group) + 194 flexbg_size; 195 196 group_blk = flexbg_offset(fs, group, prev_block, bmap, 197 rem_grps, fs->inode_blocks_per_group); 198 last_blk = ext2fs_group_last_block2(fs, last_grp); 199 } 200 201 if (!ext2fs_inode_table_loc(fs, group)) { 202 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk, 203 fs->inode_blocks_per_group, 204 bmap, &new_blk); 205 if (retval) 206 return retval; 207 for (j=0, blk = new_blk; 208 j < fs->inode_blocks_per_group; 209 j++, blk++) { 210 ext2fs_mark_block_bitmap2(bmap, blk); 211 if (flexbg_size) { 212 dgrp_t gr = ext2fs_group_of_blk2(fs, blk); 213 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1); 214 ext2fs_free_blocks_count_add(fs->super, -1); 215 ext2fs_bg_flags_clear(fs, gr, 216 EXT2_BG_BLOCK_UNINIT); 217 ext2fs_group_desc_csum_set(fs, gr); 218 } 219 } 220 ext2fs_inode_table_loc_set(fs, group, new_blk); 221 } 222 ext2fs_group_desc_csum_set(fs, group); 223 return 0; 224} 225 226errcode_t ext2fs_allocate_tables(ext2_filsys fs) 227{ 228 errcode_t retval; 229 dgrp_t i; 230 struct ext2fs_numeric_progress_struct progress; 231 232 ext2fs_numeric_progress_init(fs, &progress, NULL, 233 fs->group_desc_count); 234 235 for (i = 0; i < fs->group_desc_count; i++) { 236 ext2fs_numeric_progress_update(fs, &progress, i); 237 retval = ext2fs_allocate_group_table(fs, i, fs->block_map); 238 if (retval) 239 return retval; 240 } 241 ext2fs_numeric_progress_close(fs, &progress, NULL); 242 return 0; 243} 244 245