blob: 21d3e5ef646afc436ec0a1fd364e4213f3fed654 [file] [log] [blame]
Theodore Ts'o3839e651997-04-26 13:21:57 +00001/*
2 * alloc.c --- allocate new inodes, blocks for ext2fs
3 *
Theodore Ts'o21c84b71997-04-29 16:15:03 +00004 * Copyright (C) 1993, 1994, 1995, 1996 Theodore Ts'o.
5 *
6 * %Begin-Header%
Theodore Ts'o543547a2010-05-17 21:31:56 -04007 * This file may be redistributed under the terms of the GNU Library
8 * General Public License, version 2.
Theodore Ts'o21c84b71997-04-29 16:15:03 +00009 * %End-Header%
Theodore Ts'o3839e651997-04-26 13:21:57 +000010 */
11
12#include <stdio.h>
Theodore Ts'o4cbe8af1997-08-10 23:07:40 +000013#if HAVE_UNISTD_H
Theodore Ts'o3839e651997-04-26 13:21:57 +000014#include <unistd.h>
Theodore Ts'o4cbe8af1997-08-10 23:07:40 +000015#endif
Theodore Ts'o3839e651997-04-26 13:21:57 +000016#include <time.h>
Theodore Ts'o30fab291997-10-25 22:37:42 +000017#include <string.h>
Theodore Ts'o1d2ff461997-10-19 23:00:21 +000018#if HAVE_SYS_STAT_H
Theodore Ts'o3839e651997-04-26 13:21:57 +000019#include <sys/stat.h>
Theodore Ts'o1d2ff461997-10-19 23:00:21 +000020#endif
21#if HAVE_SYS_TYPES_H
Theodore Ts'o3839e651997-04-26 13:21:57 +000022#include <sys/types.h>
Theodore Ts'o1d2ff461997-10-19 23:00:21 +000023#endif
Theodore Ts'o3839e651997-04-26 13:21:57 +000024
Theodore Ts'ob5abe6f1998-01-19 14:47:53 +000025#include "ext2_fs.h"
Theodore Ts'o3839e651997-04-26 13:21:57 +000026#include "ext2fs.h"
27
28/*
Theodore Ts'oc71d7812008-08-22 02:52:12 -040029 * Check for uninit block bitmaps and deal with them appropriately
30 */
Theodore Ts'o03fa6f82008-11-16 10:03:00 -050031static void check_block_uninit(ext2_filsys fs, ext2fs_block_bitmap map,
JP Abgralle0ed7402014-03-19 19:08:39 -070032 dgrp_t group)
Theodore Ts'oc71d7812008-08-22 02:52:12 -040033{
Theodore Ts'o03fa6f82008-11-16 10:03:00 -050034 blk_t i;
JP Abgralle0ed7402014-03-19 19:08:39 -070035 blk64_t blk, super_blk, old_desc_blk, new_desc_blk;
Theodore Ts'oc71d7812008-08-22 02:52:12 -040036 int old_desc_blocks;
37
38 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
39 EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) ||
JP Abgralle0ed7402014-03-19 19:08:39 -070040 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT)))
Theodore Ts'oc71d7812008-08-22 02:52:12 -040041 return;
42
JP Abgralle0ed7402014-03-19 19:08:39 -070043 blk = ext2fs_group_first_block2(fs, group);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040044
JP Abgralle0ed7402014-03-19 19:08:39 -070045 ext2fs_super_and_bgd_loc2(fs, group, &super_blk,
46 &old_desc_blk, &new_desc_blk, 0);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040047
48 if (fs->super->s_feature_incompat &
49 EXT2_FEATURE_INCOMPAT_META_BG)
50 old_desc_blocks = fs->super->s_first_meta_bg;
51 else
52 old_desc_blocks = fs->desc_blocks + fs->super->s_reserved_gdt_blocks;
53
JP Abgralle0ed7402014-03-19 19:08:39 -070054 for (i=0; i < fs->super->s_blocks_per_group; i++, blk++)
55 ext2fs_fast_unmark_block_bitmap2(map, blk);
56
57 blk = ext2fs_group_first_block2(fs, group);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040058 for (i=0; i < fs->super->s_blocks_per_group; i++, blk++) {
59 if ((blk == super_blk) ||
60 (old_desc_blk && old_desc_blocks &&
61 (blk >= old_desc_blk) &&
62 (blk < old_desc_blk + old_desc_blocks)) ||
63 (new_desc_blk && (blk == new_desc_blk)) ||
JP Abgralle0ed7402014-03-19 19:08:39 -070064 (blk == ext2fs_block_bitmap_loc(fs, group)) ||
65 (blk == ext2fs_inode_bitmap_loc(fs, group)) ||
66 (blk >= ext2fs_inode_table_loc(fs, group) &&
67 (blk < ext2fs_inode_table_loc(fs, group)
Theodore Ts'oc71d7812008-08-22 02:52:12 -040068 + fs->inode_blocks_per_group)))
JP Abgralle0ed7402014-03-19 19:08:39 -070069 ext2fs_fast_mark_block_bitmap2(map, blk);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040070 }
JP Abgralle0ed7402014-03-19 19:08:39 -070071 ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040072 ext2fs_group_desc_csum_set(fs, group);
JP Abgralle0ed7402014-03-19 19:08:39 -070073 ext2fs_mark_super_dirty(fs);
74 ext2fs_mark_bb_dirty(fs);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040075}
76
77/*
78 * Check for uninit inode bitmaps and deal with them appropriately
79 */
Theodore Ts'o03fa6f82008-11-16 10:03:00 -050080static void check_inode_uninit(ext2_filsys fs, ext2fs_inode_bitmap map,
Theodore Ts'oc71d7812008-08-22 02:52:12 -040081 dgrp_t group)
82{
Theodore Ts'o03fa6f82008-11-16 10:03:00 -050083 ext2_ino_t i, ino;
Theodore Ts'oc71d7812008-08-22 02:52:12 -040084
85 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
86 EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) ||
JP Abgralle0ed7402014-03-19 19:08:39 -070087 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)))
Theodore Ts'oc71d7812008-08-22 02:52:12 -040088 return;
89
90 ino = (group * fs->super->s_inodes_per_group) + 1;
91 for (i=0; i < fs->super->s_inodes_per_group; i++, ino++)
JP Abgralle0ed7402014-03-19 19:08:39 -070092 ext2fs_fast_unmark_inode_bitmap2(map, ino);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040093
JP Abgralle0ed7402014-03-19 19:08:39 -070094 ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT);
95 ext2fs_group_desc_csum_set(fs, group);
96 ext2fs_mark_ib_dirty(fs);
97 ext2fs_mark_super_dirty(fs);
Theodore Ts'oc71d7812008-08-22 02:52:12 -040098 check_block_uninit(fs, fs->block_map, group);
99}
100
101/*
Theodore Ts'o3839e651997-04-26 13:21:57 +0000102 * Right now, just search forward from the parent directory's block
103 * group to find the next free inode.
104 *
105 * Should have a special policy for directories.
106 */
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400107errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
Theodore Ts'o54434922003-12-07 01:28:50 -0500108 int mode EXT2FS_ATTR((unused)),
Theodore Ts'o31dbecd2001-01-11 04:54:39 +0000109 ext2fs_inode_bitmap map, ext2_ino_t *ret)
Theodore Ts'o3839e651997-04-26 13:21:57 +0000110{
JP Abgralle0ed7402014-03-19 19:08:39 -0700111 ext2_ino_t start_inode = 0;
112 ext2_ino_t i, ino_in_group, upto, first_zero;
113 errcode_t retval;
114 dgrp_t group;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000115
Theodore Ts'of3db3561997-04-26 13:34:30 +0000116 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400117
Theodore Ts'o3839e651997-04-26 13:21:57 +0000118 if (!map)
119 map = fs->inode_map;
120 if (!map)
121 return EXT2_ET_NO_INODE_BITMAP;
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400122
JP Abgralle0ed7402014-03-19 19:08:39 -0700123 if (dir > 0) {
124 group = (dir - 1) / EXT2_INODES_PER_GROUP(fs->super);
125 start_inode = (group * EXT2_INODES_PER_GROUP(fs->super)) + 1;
126 }
Theodore Ts'o7f88b041997-04-26 14:48:50 +0000127 if (start_inode < EXT2_FIRST_INODE(fs->super))
128 start_inode = EXT2_FIRST_INODE(fs->super);
Theodore Ts'oa93d4062009-01-22 15:55:49 -0500129 if (start_inode > fs->super->s_inodes_count)
130 return EXT2_ET_INODE_ALLOC_FAIL;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000131 i = start_inode;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000132 do {
JP Abgralle0ed7402014-03-19 19:08:39 -0700133 ino_in_group = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
134 group = (i - 1) / EXT2_INODES_PER_GROUP(fs->super);
Theodore Ts'oc71d7812008-08-22 02:52:12 -0400135
JP Abgralle0ed7402014-03-19 19:08:39 -0700136 check_inode_uninit(fs, map, group);
137 upto = i + (EXT2_INODES_PER_GROUP(fs->super) - ino_in_group);
138 if (i < start_inode && upto >= start_inode)
139 upto = start_inode - 1;
140 if (upto > fs->super->s_inodes_count)
141 upto = fs->super->s_inodes_count;
142
143 retval = ext2fs_find_first_zero_inode_bitmap2(map, i, upto,
144 &first_zero);
145 if (retval == 0) {
146 i = first_zero;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000147 break;
JP Abgralle0ed7402014-03-19 19:08:39 -0700148 }
149 if (retval != ENOENT)
150 return EXT2_ET_INODE_ALLOC_FAIL;
151 i = upto + 1;
Sami Liedesc1a1e7f2012-03-10 22:36:12 +0200152 if (i > fs->super->s_inodes_count)
153 i = EXT2_FIRST_INODE(fs->super);
Theodore Ts'o3839e651997-04-26 13:21:57 +0000154 } while (i != start_inode);
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400155
JP Abgralle0ed7402014-03-19 19:08:39 -0700156 if (ext2fs_test_inode_bitmap2(map, i))
Theodore Ts'o1f0b6c11997-10-31 06:07:47 +0000157 return EXT2_ET_INODE_ALLOC_FAIL;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000158 *ret = i;
159 return 0;
160}
161
162/*
163 * Stupid algorithm --- we now just search forward starting from the
164 * goal. Should put in a smarter one someday....
165 */
JP Abgralle0ed7402014-03-19 19:08:39 -0700166errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal,
167 ext2fs_block_bitmap map, blk64_t *ret)
Theodore Ts'o3839e651997-04-26 13:21:57 +0000168{
JP Abgralle0ed7402014-03-19 19:08:39 -0700169 blk64_t i;
170 int c_ratio;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000171
Theodore Ts'of3db3561997-04-26 13:34:30 +0000172 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
173
Theodore Ts'o3839e651997-04-26 13:21:57 +0000174 if (!map)
175 map = fs->block_map;
176 if (!map)
177 return EXT2_ET_NO_BLOCK_BITMAP;
JP Abgralle0ed7402014-03-19 19:08:39 -0700178 if (!goal || (goal >= ext2fs_blocks_count(fs->super)))
Theodore Ts'oa29f4d31997-04-29 21:26:48 +0000179 goal = fs->super->s_first_data_block;
180 i = goal;
JP Abgralle0ed7402014-03-19 19:08:39 -0700181 c_ratio = 1 << ext2fs_get_bitmap_granularity(map);
182 if (c_ratio > 1)
183 goal &= ~EXT2FS_CLUSTER_MASK(fs);
Theodore Ts'oc71d7812008-08-22 02:52:12 -0400184 check_block_uninit(fs, map,
185 (i - fs->super->s_first_data_block) /
186 EXT2_BLOCKS_PER_GROUP(fs->super));
Theodore Ts'o3839e651997-04-26 13:21:57 +0000187 do {
Theodore Ts'oc71d7812008-08-22 02:52:12 -0400188 if (((i - fs->super->s_first_data_block) %
189 EXT2_BLOCKS_PER_GROUP(fs->super)) == 0)
190 check_block_uninit(fs, map,
191 (i - fs->super->s_first_data_block) /
192 EXT2_BLOCKS_PER_GROUP(fs->super));
193
JP Abgralle0ed7402014-03-19 19:08:39 -0700194 if (!ext2fs_fast_test_block_bitmap2(map, i)) {
Theodore Ts'o3839e651997-04-26 13:21:57 +0000195 *ret = i;
196 return 0;
197 }
JP Abgralle0ed7402014-03-19 19:08:39 -0700198 i = (i + c_ratio) & ~(c_ratio - 1);
199 if (i >= ext2fs_blocks_count(fs->super))
Theodore Ts'o3839e651997-04-26 13:21:57 +0000200 i = fs->super->s_first_data_block;
201 } while (i != goal);
Theodore Ts'o1f0b6c11997-10-31 06:07:47 +0000202 return EXT2_ET_BLOCK_ALLOC_FAIL;
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000203}
204
JP Abgralle0ed7402014-03-19 19:08:39 -0700205errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal,
206 ext2fs_block_bitmap map, blk_t *ret)
207{
208 errcode_t retval;
209 blk64_t val;
210 retval = ext2fs_new_block2(fs, goal, map, &val);
211 if (!retval)
212 *ret = (blk_t) val;
213 return retval;
214}
215
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000216/*
Theodore Ts'o30fab291997-10-25 22:37:42 +0000217 * This function zeros out the allocated block, and updates all of the
218 * appropriate filesystem records.
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000219 */
JP Abgralle0ed7402014-03-19 19:08:39 -0700220errcode_t ext2fs_alloc_block2(ext2_filsys fs, blk64_t goal,
221 char *block_buf, blk64_t *ret)
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000222{
223 errcode_t retval;
JP Abgralle0ed7402014-03-19 19:08:39 -0700224 blk64_t block;
Theodore Ts'o30fab291997-10-25 22:37:42 +0000225 char *buf = 0;
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000226
Theodore Ts'o30fab291997-10-25 22:37:42 +0000227 if (!block_buf) {
Theodore Ts'oc4e3d3f2003-08-01 09:41:07 -0400228 retval = ext2fs_get_mem(fs->blocksize, &buf);
Theodore Ts'o7b4e4531997-10-26 03:41:24 +0000229 if (retval)
230 return retval;
Theodore Ts'o30fab291997-10-25 22:37:42 +0000231 block_buf = buf;
232 }
233 memset(block_buf, 0, fs->blocksize);
Theodore Ts'oc555aeb1997-10-25 04:16:53 +0000234
Theodore Ts'of5c562e2008-06-02 17:21:37 -0400235 if (fs->get_alloc_block) {
JP Abgralle0ed7402014-03-19 19:08:39 -0700236 retval = (fs->get_alloc_block)(fs, goal, &block);
Theodore Ts'of5c562e2008-06-02 17:21:37 -0400237 if (retval)
238 goto fail;
Theodore Ts'of5c562e2008-06-02 17:21:37 -0400239 } else {
240 if (!fs->block_map) {
241 retval = ext2fs_read_block_bitmap(fs);
242 if (retval)
243 goto fail;
244 }
245
JP Abgralle0ed7402014-03-19 19:08:39 -0700246 retval = ext2fs_new_block2(fs, goal, 0, &block);
Theodore Ts'o30fab291997-10-25 22:37:42 +0000247 if (retval)
248 goto fail;
249 }
250
JP Abgralle0ed7402014-03-19 19:08:39 -0700251 retval = io_channel_write_blk64(fs->io, block, 1, block_buf);
Theodore Ts'o30fab291997-10-25 22:37:42 +0000252 if (retval)
253 goto fail;
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400254
JP Abgralle0ed7402014-03-19 19:08:39 -0700255 ext2fs_block_alloc_stats2(fs, block, +1);
Theodore Ts'o30fab291997-10-25 22:37:42 +0000256 *ret = block;
Theodore Ts'o30fab291997-10-25 22:37:42 +0000257
258fail:
259 if (buf)
Theodore Ts'oc4e3d3f2003-08-01 09:41:07 -0400260 ext2fs_free_mem(&buf);
Theodore Ts'o30fab291997-10-25 22:37:42 +0000261 return retval;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000262}
263
JP Abgralle0ed7402014-03-19 19:08:39 -0700264errcode_t ext2fs_alloc_block(ext2_filsys fs, blk_t goal,
265 char *block_buf, blk_t *ret)
Theodore Ts'o3839e651997-04-26 13:21:57 +0000266{
JP Abgralle0ed7402014-03-19 19:08:39 -0700267 errcode_t retval;
268 blk64_t val;
269 retval = ext2fs_alloc_block2(fs, goal, block_buf, &val);
270 if (!retval)
271 *ret = (blk_t) val;
272 return retval;
273}
274
275errcode_t ext2fs_get_free_blocks2(ext2_filsys fs, blk64_t start, blk64_t finish,
276 int num, ext2fs_block_bitmap map, blk64_t *ret)
277{
278 blk64_t b = start;
279 int c_ratio;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000280
Theodore Ts'of3db3561997-04-26 13:34:30 +0000281 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
282
Theodore Ts'o3839e651997-04-26 13:21:57 +0000283 if (!map)
284 map = fs->block_map;
285 if (!map)
286 return EXT2_ET_NO_BLOCK_BITMAP;
287 if (!b)
288 b = fs->super->s_first_data_block;
289 if (!finish)
290 finish = start;
291 if (!num)
292 num = 1;
JP Abgralle0ed7402014-03-19 19:08:39 -0700293 c_ratio = 1 << ext2fs_get_bitmap_granularity(map);
294 b &= ~(c_ratio - 1);
295 finish &= ~(c_ratio -1);
Theodore Ts'o3839e651997-04-26 13:21:57 +0000296 do {
JP Abgralle0ed7402014-03-19 19:08:39 -0700297 if (b+num-1 > ext2fs_blocks_count(fs->super))
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000298 b = fs->super->s_first_data_block;
JP Abgralle0ed7402014-03-19 19:08:39 -0700299 if (ext2fs_fast_test_block_bitmap_range2(map, b, num)) {
Theodore Ts'o3839e651997-04-26 13:21:57 +0000300 *ret = b;
301 return 0;
302 }
JP Abgralle0ed7402014-03-19 19:08:39 -0700303 b += c_ratio;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000304 } while (b != finish);
Theodore Ts'o1f0b6c11997-10-31 06:07:47 +0000305 return EXT2_ET_BLOCK_ALLOC_FAIL;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000306}
307
JP Abgralle0ed7402014-03-19 19:08:39 -0700308errcode_t ext2fs_get_free_blocks(ext2_filsys fs, blk_t start, blk_t finish,
309 int num, ext2fs_block_bitmap map, blk_t *ret)
310{
311 errcode_t retval;
312 blk64_t val;
313 retval = ext2fs_get_free_blocks2(fs, start, finish, num, map, &val);
314 if(!retval)
315 *ret = (blk_t) val;
316 return retval;
317}
318
Theodore Ts'oefc6f622008-08-27 23:07:54 -0400319void ext2fs_set_alloc_block_callback(ext2_filsys fs,
Theodore Ts'of5c562e2008-06-02 17:21:37 -0400320 errcode_t (*func)(ext2_filsys fs,
321 blk64_t goal,
322 blk64_t *ret),
323 errcode_t (**old)(ext2_filsys fs,
324 blk64_t goal,
325 blk64_t *ret))
326{
327 if (!fs || fs->magic != EXT2_ET_MAGIC_EXT2FS_FILSYS)
328 return;
329
330 if (old)
331 *old = fs->get_alloc_block;
332
333 fs->get_alloc_block = func;
334}