2 * alloc_tables.c --- Allocate tables for a newly initialized
3 * filesystem. Used by mke2fs when initializing a filesystem
5 * Copyright (C) 1996 Theodore Ts'o.
8 * This file may be redistributed under the terms of the GNU Public
24 #include <sys/types.h>
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.
37 static blk_t
flexbg_offset(ext2_filsys fs
, dgrp_t group
, blk64_t start_blk
,
38 ext2fs_block_bitmap bmap
, int offset
, int size
,
41 int flexbg
, flexbg_size
;
42 blk_t last_blk
, first_free
= 0;
45 flexbg_size
= 1 << fs
->super
->s_log_groups_per_flex
;
46 flexbg
= group
/ flexbg_size
;
48 if (size
> (int) (fs
->super
->s_blocks_per_group
/ 8))
49 size
= (int) fs
->super
->s_blocks_per_group
/ 8;
55 * Don't do a long search if the previous block
56 * search is still valid.
58 if (start_blk
&& group
% flexbg_size
) {
59 if (ext2fs_test_block_bitmap_range2(bmap
, start_blk
+ elem_size
,
61 return start_blk
+ elem_size
;
64 start_blk
= ext2fs_group_first_block(fs
, flexbg_size
* flexbg
);
65 last_grp
= group
| (flexbg_size
- 1);
66 if (last_grp
> fs
->group_desc_count
)
67 last_grp
= fs
->group_desc_count
;
68 last_blk
= ext2fs_group_last_block(fs
, last_grp
);
70 /* Find the first available block */
71 if (ext2fs_get_free_blocks(fs
, start_blk
, last_blk
, 1, bmap
,
75 if (ext2fs_get_free_blocks(fs
, first_free
+ offset
, last_blk
, size
,
82 errcode_t
ext2fs_allocate_group_table(ext2_filsys fs
, dgrp_t group
,
83 ext2fs_block_bitmap bmap
)
86 blk_t group_blk
, start_blk
, last_blk
, new_blk
, blk
;
88 int j
, rem_grps
= 0, flexbg_size
= 0;
90 group_blk
= ext2fs_group_first_block(fs
, group
);
91 last_blk
= ext2fs_group_last_block(fs
, group
);
96 if (EXT2_HAS_INCOMPAT_FEATURE(fs
->super
,
97 EXT4_FEATURE_INCOMPAT_FLEX_BG
) &&
98 fs
->super
->s_log_groups_per_flex
) {
99 flexbg_size
= 1 << fs
->super
->s_log_groups_per_flex
;
100 last_grp
= group
| (flexbg_size
- 1);
101 rem_grps
= last_grp
- group
;
102 if (last_grp
> fs
->group_desc_count
)
103 last_grp
= fs
->group_desc_count
;
107 * Allocate the block and inode bitmaps, if necessary
110 retval
= ext2fs_get_free_blocks(fs
, group_blk
, last_blk
,
111 1, bmap
, &start_blk
);
114 start_blk
+= fs
->inode_blocks_per_group
;
115 start_blk
+= ((fs
->stride
* group
) %
116 (last_blk
- start_blk
+ 1));
117 if (start_blk
>= last_blk
)
118 start_blk
= group_blk
;
120 start_blk
= group_blk
;
123 blk64_t prev_block
= 0;
125 if (group
&& fs
->group_desc
[group
-1].bg_block_bitmap
)
126 prev_block
= fs
->group_desc
[group
-1].bg_block_bitmap
;
127 start_blk
= flexbg_offset(fs
, group
, prev_block
, bmap
,
129 last_blk
= ext2fs_group_last_block(fs
, last_grp
);
132 if (!fs
->group_desc
[group
].bg_block_bitmap
) {
133 retval
= ext2fs_get_free_blocks(fs
, start_blk
, last_blk
,
135 if (retval
== EXT2_ET_BLOCK_ALLOC_FAIL
)
136 retval
= ext2fs_get_free_blocks(fs
, group_blk
,
137 last_blk
, 1, bmap
, &new_blk
);
140 ext2fs_mark_block_bitmap2(bmap
, new_blk
);
141 fs
->group_desc
[group
].bg_block_bitmap
= new_blk
;
143 dgrp_t gr
= ext2fs_group_of_blk(fs
, new_blk
);
144 fs
->group_desc
[gr
].bg_free_blocks_count
--;
145 ext2fs_free_blocks_count_add(fs
->super
, -1);
146 ext2fs_bg_flag_clear(fs
, gr
, EXT2_BG_BLOCK_UNINIT
);
147 ext2fs_group_desc_csum_set(fs
, gr
);
152 blk_t prev_block
= 0;
153 if (group
&& fs
->group_desc
[group
-1].bg_inode_bitmap
)
154 prev_block
= fs
->group_desc
[group
-1].bg_inode_bitmap
;
155 start_blk
= flexbg_offset(fs
, group
, prev_block
, bmap
,
156 flexbg_size
, rem_grps
, 1);
157 last_blk
= ext2fs_group_last_block(fs
, last_grp
);
160 if (!fs
->group_desc
[group
].bg_inode_bitmap
) {
161 retval
= ext2fs_get_free_blocks(fs
, start_blk
, last_blk
,
163 if (retval
== EXT2_ET_BLOCK_ALLOC_FAIL
)
164 retval
= ext2fs_get_free_blocks(fs
, group_blk
,
165 last_blk
, 1, bmap
, &new_blk
);
168 ext2fs_mark_block_bitmap2(bmap
, new_blk
);
169 fs
->group_desc
[group
].bg_inode_bitmap
= new_blk
;
171 dgrp_t gr
= ext2fs_group_of_blk(fs
, new_blk
);
172 fs
->group_desc
[gr
].bg_free_blocks_count
--;
173 ext2fs_free_blocks_count_add(fs
->super
, -1);
174 ext2fs_bg_flag_clear(fs
, gr
, EXT2_BG_BLOCK_UNINIT
);
175 ext2fs_group_desc_csum_set(fs
, gr
);
180 * Allocate the inode table
183 blk_t prev_block
= 0;
184 if (group
&& fs
->group_desc
[group
-1].bg_inode_table
)
185 prev_block
= fs
->group_desc
[group
-1].bg_inode_table
;
186 group_blk
= flexbg_offset(fs
, group
, prev_block
, bmap
,
188 fs
->inode_blocks_per_group
*
190 fs
->inode_blocks_per_group
);
191 last_blk
= ext2fs_group_last_block(fs
, last_grp
);
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
,
200 for (j
=0, blk
= new_blk
;
201 j
< fs
->inode_blocks_per_group
;
203 ext2fs_mark_block_bitmap2(bmap
, blk
);
205 dgrp_t gr
= ext2fs_group_of_blk(fs
, blk
);
206 fs
->group_desc
[gr
].bg_free_blocks_count
--;
207 ext2fs_free_blocks_count_add(fs
->super
, -1);
208 ext2fs_bg_flag_clear(fs
, gr
,
209 EXT2_BG_BLOCK_UNINIT
);
210 ext2fs_group_desc_csum_set(fs
, gr
);
213 fs
->group_desc
[group
].bg_inode_table
= new_blk
;
215 ext2fs_group_desc_csum_set(fs
, group
);
219 errcode_t
ext2fs_allocate_tables(ext2_filsys fs
)
223 struct ext2fs_numeric_progress_struct progress
;
225 ext2fs_numeric_progress_init(fs
, &progress
, NULL
,
226 fs
->group_desc_count
);
228 for (i
= 0; i
< fs
->group_desc_count
; i
++) {
229 ext2fs_numeric_progress_update(fs
, &progress
, i
);
230 retval
= ext2fs_allocate_group_table(fs
, i
, fs
->block_map
);
234 ext2fs_numeric_progress_close(fs
, &progress
, NULL
);