Home | History | Annotate | Download | only in ext2fs
      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 Public
      9  * License.
     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 
     30 /*
     31  * This routine searches for free blocks that can allocate a full
     32  * group of bitmaps or inode tables for a flexbg group.  Returns the
     33  * block number with a correct offset were the bitmaps and inode
     34  * tables can be allocated continously and in order.
     35  */
     36 static blk_t flexbg_offset(ext2_filsys fs, dgrp_t group, blk_t start_blk,
     37 			   ext2fs_block_bitmap bmap, int offset, int size,
     38 			   int elem_size)
     39 {
     40 	int		flexbg, flexbg_size;
     41 	blk_t		last_blk, first_free = 0;
     42 	dgrp_t	       	last_grp;
     43 
     44 	flexbg_size = 1 << fs->super->s_log_groups_per_flex;
     45 	flexbg = group / flexbg_size;
     46 
     47 	if (size > (int) (fs->super->s_blocks_per_group / 8))
     48 		size = (int) fs->super->s_blocks_per_group / 8;
     49 
     50 	if (offset)
     51 		offset -= 1;
     52 
     53 	/*
     54 	 * Don't do a long search if the previous block
     55 	 * search is still valid.
     56 	 */
     57 	if (start_blk && group % flexbg_size) {
     58 		if (ext2fs_test_block_bitmap_range(bmap, start_blk + elem_size,
     59 						   size))
     60 			return start_blk + elem_size;
     61 	}
     62 
     63 	start_blk = ext2fs_group_first_block(fs, flexbg_size * flexbg);
     64 	last_grp = group | (flexbg_size - 1);
     65 	if (last_grp > fs->group_desc_count)
     66 		last_grp = fs->group_desc_count;
     67 	last_blk = ext2fs_group_last_block(fs, last_grp);
     68 
     69 	/* Find the first available block */
     70 	if (ext2fs_get_free_blocks(fs, start_blk, last_blk, 1, bmap,
     71 				   &first_free))
     72 		return first_free;
     73 
     74 	if (ext2fs_get_free_blocks(fs, first_free + offset, last_blk, size,
     75 				   bmap, &first_free))
     76 		return first_free;
     77 
     78 	return first_free;
     79 }
     80 
     81 errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group,
     82 				      ext2fs_block_bitmap bmap)
     83 {
     84 	errcode_t	retval;
     85 	blk_t		group_blk, start_blk, last_blk, new_blk, blk;
     86 	dgrp_t		last_grp = 0;
     87 	int		j, rem_grps = 0, flexbg_size = 0;
     88 
     89 	group_blk = ext2fs_group_first_block(fs, group);
     90 	last_blk = ext2fs_group_last_block(fs, group);
     91 
     92 	if (!bmap)
     93 		bmap = fs->block_map;
     94 
     95 	if (EXT2_HAS_INCOMPAT_FEATURE(fs->super,
     96 				      EXT4_FEATURE_INCOMPAT_FLEX_BG) &&
     97 	    fs->super->s_log_groups_per_flex) {
     98 		flexbg_size = 1 << fs->super->s_log_groups_per_flex;
     99 		last_grp = group | (flexbg_size - 1);
    100 		rem_grps = last_grp - group;
    101 		if (last_grp > fs->group_desc_count)
    102 			last_grp = fs->group_desc_count;
    103 	}
    104 
    105 	/*
    106 	 * Allocate the block and inode bitmaps, if necessary
    107 	 */
    108 	if (fs->stride) {
    109 		retval = ext2fs_get_free_blocks(fs, group_blk, last_blk,
    110 						1, bmap, &start_blk);
    111 		if (retval)
    112 			return retval;
    113 		start_blk += fs->inode_blocks_per_group;
    114 		start_blk += ((fs->stride * group) %
    115 			      (last_blk - start_blk + 1));
    116 		if (start_blk >= last_blk)
    117 			start_blk = group_blk;
    118 	} else
    119 		start_blk = group_blk;
    120 
    121 	if (flexbg_size) {
    122 		blk_t prev_block = 0;
    123 		if (group && fs->group_desc[group-1].bg_block_bitmap)
    124 			prev_block = fs->group_desc[group-1].bg_block_bitmap;
    125 		start_blk = flexbg_offset(fs, group, prev_block, bmap,
    126 						 0, rem_grps, 1);
    127 		last_blk = ext2fs_group_last_block(fs, last_grp);
    128 	}
    129 
    130 	if (!fs->group_desc[group].bg_block_bitmap) {
    131 		retval = ext2fs_get_free_blocks(fs, start_blk, last_blk,
    132 						1, bmap, &new_blk);
    133 		if (retval == EXT2_ET_BLOCK_ALLOC_FAIL)
    134 			retval = ext2fs_get_free_blocks(fs, group_blk,
    135 					last_blk, 1, bmap, &new_blk);
    136 		if (retval)
    137 			return retval;
    138 		ext2fs_mark_block_bitmap(bmap, new_blk);
    139 		fs->group_desc[group].bg_block_bitmap = new_blk;
    140 		if (flexbg_size) {
    141 			dgrp_t gr = ext2fs_group_of_blk(fs, new_blk);
    142 			fs->group_desc[gr].bg_free_blocks_count--;
    143 			fs->super->s_free_blocks_count--;
    144 			fs->group_desc[gr].bg_flags &= ~EXT2_BG_BLOCK_UNINIT;
    145 			ext2fs_group_desc_csum_set(fs, gr);
    146 		}
    147 	}
    148 
    149 	if (flexbg_size) {
    150 		blk_t prev_block = 0;
    151 		if (group && fs->group_desc[group-1].bg_inode_bitmap)
    152 			prev_block = fs->group_desc[group-1].bg_inode_bitmap;
    153 		start_blk = flexbg_offset(fs, group, prev_block, bmap,
    154 						 flexbg_size, rem_grps, 1);
    155 		last_blk = ext2fs_group_last_block(fs, last_grp);
    156 	}
    157 
    158 	if (!fs->group_desc[group].bg_inode_bitmap) {
    159 		retval = ext2fs_get_free_blocks(fs, start_blk, last_blk,
    160 						1, bmap, &new_blk);
    161 		if (retval == EXT2_ET_BLOCK_ALLOC_FAIL)
    162 			retval = ext2fs_get_free_blocks(fs, group_blk,
    163 					last_blk, 1, bmap, &new_blk);
    164 		if (retval)
    165 			return retval;
    166 		ext2fs_mark_block_bitmap(bmap, new_blk);
    167 		fs->group_desc[group].bg_inode_bitmap = new_blk;
    168 		if (flexbg_size) {
    169 			dgrp_t gr = ext2fs_group_of_blk(fs, new_blk);
    170 			fs->group_desc[gr].bg_free_blocks_count--;
    171 			fs->super->s_free_blocks_count--;
    172 			fs->group_desc[gr].bg_flags &= ~EXT2_BG_BLOCK_UNINIT;
    173 			ext2fs_group_desc_csum_set(fs, gr);
    174 		}
    175 	}
    176 
    177 	/*
    178 	 * Allocate the inode table
    179 	 */
    180 	if (flexbg_size) {
    181 		blk_t prev_block = 0;
    182 		if (group && fs->group_desc[group-1].bg_inode_table)
    183 			prev_block = fs->group_desc[group-1].bg_inode_table;
    184 		if (last_grp == fs->group_desc_count)
    185 			rem_grps = last_grp - group;
    186 		group_blk = flexbg_offset(fs, group, prev_block, bmap,
    187 						 flexbg_size * 2,
    188 						 fs->inode_blocks_per_group *
    189 						 rem_grps,
    190 						 fs->inode_blocks_per_group);
    191 		last_blk = ext2fs_group_last_block(fs, last_grp);
    192 	}
    193 
    194 	if (!fs->group_desc[group].bg_inode_table) {
    195 		retval = ext2fs_get_free_blocks(fs, group_blk, last_blk,
    196 						fs->inode_blocks_per_group,
    197 						bmap, &new_blk);
    198 		if (retval)
    199 			return retval;
    200 		for (j=0, blk = new_blk;
    201 		     j < fs->inode_blocks_per_group;
    202 		     j++, blk++) {
    203 			ext2fs_mark_block_bitmap(bmap, blk);
    204 			if (flexbg_size) {
    205 				dgrp_t gr = ext2fs_group_of_blk(fs, blk);
    206 				fs->group_desc[gr].bg_free_blocks_count--;
    207 				fs->super->s_free_blocks_count--;
    208 				fs->group_desc[gr].bg_flags &= ~EXT2_BG_BLOCK_UNINIT;
    209 				ext2fs_group_desc_csum_set(fs, gr);
    210 			}
    211 		}
    212 		fs->group_desc[group].bg_inode_table = new_blk;
    213 	}
    214 	ext2fs_group_desc_csum_set(fs, group);
    215 	return 0;
    216 }
    217 
    218 errcode_t ext2fs_allocate_tables(ext2_filsys fs)
    219 {
    220 	errcode_t	retval;
    221 	dgrp_t		i;
    222 
    223 	for (i = 0; i < fs->group_desc_count; i++) {
    224 		retval = ext2fs_allocate_group_table(fs, i, fs->block_map);
    225 		if (retval)
    226 			return retval;
    227 	}
    228 	return 0;
    229 }
    230 
    231