2 * alloc.c --- allocate new inodes, blocks for ext2fs
4 * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
23 #include <sys/types.h>
30 * Check for uninit block bitmaps and deal with them appropriately
32 static void check_block_uninit(ext2_filsys fs
, ext2fs_block_bitmap map
,
36 blk64_t blk
, super_blk
, old_desc_blk
, new_desc_blk
;
39 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs
->super
,
40 EXT4_FEATURE_RO_COMPAT_GDT_CSUM
)) ||
41 !(ext2fs_bg_flags_test(fs
, group
, EXT2_BG_BLOCK_UNINIT
)))
44 blk
= (group
* fs
->super
->s_blocks_per_group
) +
45 fs
->super
->s_first_data_block
;
47 ext2fs_super_and_bgd_loc2(fs
, group
, &super_blk
,
48 &old_desc_blk
, &new_desc_blk
, 0);
50 if (fs
->super
->s_feature_incompat
&
51 EXT2_FEATURE_INCOMPAT_META_BG
)
52 old_desc_blocks
= fs
->super
->s_first_meta_bg
;
54 old_desc_blocks
= fs
->desc_blocks
+ fs
->super
->s_reserved_gdt_blocks
;
56 for (i
=0; i
< fs
->super
->s_blocks_per_group
; i
++, blk
++)
57 ext2fs_fast_unmark_block_bitmap2(map
, blk
);
59 blk
= (group
* fs
->super
->s_blocks_per_group
) +
60 fs
->super
->s_first_data_block
;
61 for (i
=0; i
< fs
->super
->s_blocks_per_group
; i
++, blk
++) {
62 if ((blk
== super_blk
) ||
63 (old_desc_blk
&& old_desc_blocks
&&
64 (blk
>= old_desc_blk
) &&
65 (blk
< old_desc_blk
+ old_desc_blocks
)) ||
66 (new_desc_blk
&& (blk
== new_desc_blk
)) ||
67 (blk
== ext2fs_block_bitmap_loc(fs
, group
)) ||
68 (blk
== ext2fs_inode_bitmap_loc(fs
, group
)) ||
69 (blk
>= ext2fs_inode_table_loc(fs
, group
) &&
70 (blk
< ext2fs_inode_table_loc(fs
, group
)
71 + fs
->inode_blocks_per_group
)))
72 ext2fs_fast_mark_block_bitmap2(map
, blk
);
74 ext2fs_bg_flags_clear(fs
, group
, EXT2_BG_BLOCK_UNINIT
);
75 ext2fs_group_desc_csum_set(fs
, group
);
79 * Check for uninit inode bitmaps and deal with them appropriately
81 static void check_inode_uninit(ext2_filsys fs
, ext2fs_inode_bitmap map
,
86 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs
->super
,
87 EXT4_FEATURE_RO_COMPAT_GDT_CSUM
)) ||
88 !(ext2fs_bg_flags_test(fs
, group
, EXT2_BG_INODE_UNINIT
)))
91 ino
= (group
* fs
->super
->s_inodes_per_group
) + 1;
92 for (i
=0; i
< fs
->super
->s_inodes_per_group
; i
++, ino
++)
93 ext2fs_fast_unmark_inode_bitmap2(map
, ino
);
95 ext2fs_bg_flags_clear(fs
, group
, EXT2_BG_INODE_UNINIT
);
96 check_block_uninit(fs
, fs
->block_map
, group
);
100 * Right now, just search forward from the parent directory's block
101 * group to find the next free inode.
103 * Should have a special policy for directories.
105 errcode_t
ext2fs_new_inode(ext2_filsys fs
, ext2_ino_t dir
,
106 int mode
EXT2FS_ATTR((unused
)),
107 ext2fs_inode_bitmap map
, ext2_ino_t
*ret
)
109 ext2_ino_t dir_group
= 0;
111 ext2_ino_t start_inode
;
113 EXT2_CHECK_MAGIC(fs
, EXT2_ET_MAGIC_EXT2FS_FILSYS
);
118 return EXT2_ET_NO_INODE_BITMAP
;
121 dir_group
= (dir
- 1) / EXT2_INODES_PER_GROUP(fs
->super
);
123 start_inode
= (dir_group
* EXT2_INODES_PER_GROUP(fs
->super
)) + 1;
124 if (start_inode
< EXT2_FIRST_INODE(fs
->super
))
125 start_inode
= EXT2_FIRST_INODE(fs
->super
);
126 if (start_inode
> fs
->super
->s_inodes_count
)
127 return EXT2_ET_INODE_ALLOC_FAIL
;
131 if (((i
- 1) % EXT2_INODES_PER_GROUP(fs
->super
)) == 0)
132 check_inode_uninit(fs
, map
, (i
- 1) /
133 EXT2_INODES_PER_GROUP(fs
->super
));
135 if (!ext2fs_fast_test_inode_bitmap2(map
, i
))
138 if (i
> fs
->super
->s_inodes_count
)
139 i
= EXT2_FIRST_INODE(fs
->super
);
140 } while (i
!= start_inode
);
142 if (ext2fs_test_inode_bitmap2(map
, i
))
143 return EXT2_ET_INODE_ALLOC_FAIL
;
149 * Stupid algorithm --- we now just search forward starting from the
150 * goal. Should put in a smarter one someday....
152 errcode_t
ext2fs_new_block2(ext2_filsys fs
, blk64_t goal
,
153 ext2fs_block_bitmap map
, blk64_t
*ret
)
158 EXT2_CHECK_MAGIC(fs
, EXT2_ET_MAGIC_EXT2FS_FILSYS
);
163 return EXT2_ET_NO_BLOCK_BITMAP
;
164 if (!goal
|| (goal
>= ext2fs_blocks_count(fs
->super
)))
165 goal
= fs
->super
->s_first_data_block
;
167 c_ratio
= 1 << ext2fs_get_bitmap_granularity(map
);
169 goal
&= ~EXT2FS_CLUSTER_MASK(fs
);
170 check_block_uninit(fs
, map
,
171 (i
- fs
->super
->s_first_data_block
) /
172 EXT2_BLOCKS_PER_GROUP(fs
->super
));
174 if (((i
- fs
->super
->s_first_data_block
) %
175 EXT2_BLOCKS_PER_GROUP(fs
->super
)) == 0)
176 check_block_uninit(fs
, map
,
177 (i
- fs
->super
->s_first_data_block
) /
178 EXT2_BLOCKS_PER_GROUP(fs
->super
));
180 if (!ext2fs_fast_test_block_bitmap2(map
, i
)) {
184 i
= (i
+ c_ratio
) & ~(c_ratio
- 1);
185 if (i
>= ext2fs_blocks_count(fs
->super
))
186 i
= fs
->super
->s_first_data_block
;
188 return EXT2_ET_BLOCK_ALLOC_FAIL
;
191 errcode_t
ext2fs_new_block(ext2_filsys fs
, blk_t goal
,
192 ext2fs_block_bitmap map
, blk_t
*ret
)
196 retval
= ext2fs_new_block2(fs
, goal
, map
, &val
);
203 * This function zeros out the allocated block, and updates all of the
204 * appropriate filesystem records.
206 errcode_t
ext2fs_alloc_block2(ext2_filsys fs
, blk64_t goal
,
207 char *block_buf
, blk64_t
*ret
)
214 retval
= ext2fs_get_mem(fs
->blocksize
, &buf
);
219 memset(block_buf
, 0, fs
->blocksize
);
221 if (fs
->get_alloc_block
) {
222 retval
= (fs
->get_alloc_block
)(fs
, goal
, &block
);
226 if (!fs
->block_map
) {
227 retval
= ext2fs_read_block_bitmap(fs
);
232 retval
= ext2fs_new_block2(fs
, goal
, 0, &block
);
237 retval
= io_channel_write_blk64(fs
->io
, block
, 1, block_buf
);
241 ext2fs_block_alloc_stats2(fs
, block
, +1);
246 ext2fs_free_mem(&buf
);
250 errcode_t
ext2fs_alloc_block(ext2_filsys fs
, blk_t goal
,
251 char *block_buf
, blk_t
*ret
)
255 retval
= ext2fs_alloc_block2(fs
, goal
, block_buf
, &val
);
261 errcode_t
ext2fs_get_free_blocks2(ext2_filsys fs
, blk64_t start
, blk64_t finish
,
262 int num
, ext2fs_block_bitmap map
, blk64_t
*ret
)
267 EXT2_CHECK_MAGIC(fs
, EXT2_ET_MAGIC_EXT2FS_FILSYS
);
272 return EXT2_ET_NO_BLOCK_BITMAP
;
274 b
= fs
->super
->s_first_data_block
;
279 c_ratio
= 1 << ext2fs_get_bitmap_granularity(map
);
281 finish
&= ~(c_ratio
-1);
283 if (b
+num
-1 > ext2fs_blocks_count(fs
->super
))
284 b
= fs
->super
->s_first_data_block
;
285 if (ext2fs_fast_test_block_bitmap_range2(map
, b
, num
)) {
290 } while (b
!= finish
);
291 return EXT2_ET_BLOCK_ALLOC_FAIL
;
294 errcode_t
ext2fs_get_free_blocks(ext2_filsys fs
, blk_t start
, blk_t finish
,
295 int num
, ext2fs_block_bitmap map
, blk_t
*ret
)
299 retval
= ext2fs_get_free_blocks2(fs
, start
, finish
, num
, map
, &val
);
305 void ext2fs_set_alloc_block_callback(ext2_filsys fs
,
306 errcode_t (*func
)(ext2_filsys fs
,
309 errcode_t (**old
)(ext2_filsys fs
,
313 if (!fs
|| fs
->magic
!= EXT2_ET_MAGIC_EXT2FS_FILSYS
)
317 *old
= fs
->get_alloc_block
;
319 fs
->get_alloc_block
= func
;