Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0
2 : : /*
3 : : * linux/fs/ext4/ialloc.c
4 : : *
5 : : * Copyright (C) 1992, 1993, 1994, 1995
6 : : * Remy Card (card@masi.ibp.fr)
7 : : * Laboratoire MASI - Institut Blaise Pascal
8 : : * Universite Pierre et Marie Curie (Paris VI)
9 : : *
10 : : * BSD ufs-inspired inode and directory allocation by
11 : : * Stephen Tweedie (sct@redhat.com), 1993
12 : : * Big-endian to little-endian byte-swapping/bitmaps by
13 : : * David S. Miller (davem@caip.rutgers.edu), 1995
14 : : */
15 : :
16 : : #include <linux/time.h>
17 : : #include <linux/fs.h>
18 : : #include <linux/stat.h>
19 : : #include <linux/string.h>
20 : : #include <linux/quotaops.h>
21 : : #include <linux/buffer_head.h>
22 : : #include <linux/random.h>
23 : : #include <linux/bitops.h>
24 : : #include <linux/blkdev.h>
25 : : #include <linux/cred.h>
26 : :
27 : : #include <asm/byteorder.h>
28 : :
29 : : #include "ext4.h"
30 : : #include "ext4_jbd2.h"
31 : : #include "xattr.h"
32 : : #include "acl.h"
33 : :
34 : : #include <trace/events/ext4.h>
35 : :
36 : : /*
37 : : * ialloc.c contains the inodes allocation and deallocation routines
38 : : */
39 : :
40 : : /*
41 : : * The free inodes are managed by bitmaps. A file system contains several
42 : : * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
43 : : * block for inodes, N blocks for the inode table and data blocks.
44 : : *
45 : : * The file system contains group descriptors which are located after the
46 : : * super block. Each descriptor contains the number of the bitmap block and
47 : : * the free blocks count in the block.
48 : : */
49 : :
50 : : /*
51 : : * To avoid calling the atomic setbit hundreds or thousands of times, we only
52 : : * need to use it within a single byte (to ensure we get endianness right).
53 : : * We can use memset for the rest of the bitmap as there are no other users.
54 : : */
55 : 0 : void ext4_mark_bitmap_end(int start_bit, int end_bit, char *bitmap)
56 : : {
57 : 0 : int i;
58 : :
59 [ # # ]: 0 : if (start_bit >= end_bit)
60 : : return;
61 : :
62 : : ext4_debug("mark end bits +%d through +%d used\n", start_bit, end_bit);
63 [ # # ]: 0 : for (i = start_bit; i < ((start_bit + 7) & ~7UL); i++)
64 : 0 : ext4_set_bit(i, bitmap);
65 [ # # ]: 0 : if (i < end_bit)
66 : 0 : memset(bitmap + (i >> 3), 0xff, (end_bit - i) >> 3);
67 : : }
68 : :
69 : 120 : void ext4_end_bitmap_read(struct buffer_head *bh, int uptodate)
70 : : {
71 [ + - ]: 120 : if (uptodate) {
72 : 120 : set_buffer_uptodate(bh);
73 : 120 : set_bitmap_uptodate(bh);
74 : : }
75 : 120 : unlock_buffer(bh);
76 : 120 : put_bh(bh);
77 : 120 : }
78 : :
79 : 20982 : static int ext4_validate_inode_bitmap(struct super_block *sb,
80 : : struct ext4_group_desc *desc,
81 : : ext4_group_t block_group,
82 : : struct buffer_head *bh)
83 : : {
84 : 20982 : ext4_fsblk_t blk;
85 : 20982 : struct ext4_group_info *grp = ext4_get_group_info(sb, block_group);
86 : :
87 [ + + ]: 20982 : if (buffer_verified(bh))
88 : : return 0;
89 [ + - ]: 30 : if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp))
90 : : return -EFSCORRUPTED;
91 : :
92 : 30 : ext4_lock_group(sb, block_group);
93 [ - + ]: 30 : if (buffer_verified(bh))
94 : 0 : goto verified;
95 : 30 : blk = ext4_inode_bitmap(sb, desc);
96 [ - + ]: 30 : if (!ext4_inode_bitmap_csum_verify(sb, block_group, desc, bh,
97 : 30 : EXT4_INODES_PER_GROUP(sb) / 8) ||
98 : : ext4_simulate_fail(sb, EXT4_SIM_IBITMAP_CRC)) {
99 : 0 : ext4_unlock_group(sb, block_group);
100 : 0 : ext4_error(sb, "Corrupt inode bitmap - block_group = %u, "
101 : : "inode_bitmap = %llu", block_group, blk);
102 : 0 : ext4_mark_group_bitmap_corrupted(sb, block_group,
103 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
104 : 0 : return -EFSBADCRC;
105 : : }
106 : 30 : set_buffer_verified(bh);
107 : 30 : verified:
108 : 30 : ext4_unlock_group(sb, block_group);
109 : 30 : return 0;
110 : : }
111 : :
112 : : /*
113 : : * Read the inode allocation bitmap for a given block_group, reading
114 : : * into the specified slot in the superblock's bitmap cache.
115 : : *
116 : : * Return buffer_head of bitmap on success or NULL.
117 : : */
118 : : static struct buffer_head *
119 : 20982 : ext4_read_inode_bitmap(struct super_block *sb, ext4_group_t block_group)
120 : : {
121 : 20982 : struct ext4_group_desc *desc;
122 : 20982 : struct ext4_sb_info *sbi = EXT4_SB(sb);
123 : 20982 : struct buffer_head *bh = NULL;
124 : 20982 : ext4_fsblk_t bitmap_blk;
125 : 20982 : int err;
126 : :
127 : 20982 : desc = ext4_get_group_desc(sb, block_group, NULL);
128 [ + - ]: 20982 : if (!desc)
129 : : return ERR_PTR(-EFSCORRUPTED);
130 : :
131 : 20982 : bitmap_blk = ext4_inode_bitmap(sb, desc);
132 [ + - - + ]: 20982 : if ((bitmap_blk <= le32_to_cpu(sbi->s_es->s_first_data_block)) ||
133 [ - + ]: 20982 : (bitmap_blk >= ext4_blocks_count(sbi->s_es))) {
134 : 0 : ext4_error(sb, "Invalid inode bitmap blk %llu in "
135 : : "block_group %u", bitmap_blk, block_group);
136 : 0 : ext4_mark_group_bitmap_corrupted(sb, block_group,
137 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
138 : 0 : return ERR_PTR(-EFSCORRUPTED);
139 : : }
140 : 20982 : bh = sb_getblk(sb, bitmap_blk);
141 [ - + ]: 20982 : if (unlikely(!bh)) {
142 : 0 : ext4_warning(sb, "Cannot read inode bitmap - "
143 : : "block_group = %u, inode_bitmap = %llu",
144 : : block_group, bitmap_blk);
145 : 0 : return ERR_PTR(-ENOMEM);
146 : : }
147 [ + + ]: 20982 : if (bitmap_uptodate(bh))
148 : 20951 : goto verify;
149 : :
150 : 31 : lock_buffer(bh);
151 [ + + ]: 31 : if (bitmap_uptodate(bh)) {
152 : 1 : unlock_buffer(bh);
153 : 1 : goto verify;
154 : : }
155 : :
156 : 30 : ext4_lock_group(sb, block_group);
157 [ + - ]: 30 : if (ext4_has_group_desc_csum(sb) &&
158 [ - + ]: 30 : (desc->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT))) {
159 [ # # ]: 0 : if (block_group == 0) {
160 : 0 : ext4_unlock_group(sb, block_group);
161 : 0 : unlock_buffer(bh);
162 : 0 : ext4_error(sb, "Inode bitmap for bg 0 marked "
163 : : "uninitialized");
164 : 0 : err = -EFSCORRUPTED;
165 : 0 : goto out;
166 : : }
167 : 0 : memset(bh->b_data, 0, (EXT4_INODES_PER_GROUP(sb) + 7) / 8);
168 : 0 : ext4_mark_bitmap_end(EXT4_INODES_PER_GROUP(sb),
169 : 0 : sb->s_blocksize * 8, bh->b_data);
170 : 0 : set_bitmap_uptodate(bh);
171 : 0 : set_buffer_uptodate(bh);
172 : 0 : set_buffer_verified(bh);
173 : 0 : ext4_unlock_group(sb, block_group);
174 : 0 : unlock_buffer(bh);
175 : 0 : return bh;
176 : : }
177 : 30 : ext4_unlock_group(sb, block_group);
178 : :
179 [ - + ]: 30 : if (buffer_uptodate(bh)) {
180 : : /*
181 : : * if not uninit if bh is uptodate,
182 : : * bitmap is also uptodate
183 : : */
184 : 0 : set_bitmap_uptodate(bh);
185 : 0 : unlock_buffer(bh);
186 : 0 : goto verify;
187 : : }
188 : : /*
189 : : * submit the buffer_head for reading
190 : : */
191 : 30 : trace_ext4_load_inode_bitmap(sb, block_group);
192 : 30 : bh->b_end_io = ext4_end_bitmap_read;
193 : 30 : get_bh(bh);
194 : 30 : submit_bh(REQ_OP_READ, REQ_META | REQ_PRIO, bh);
195 : 30 : wait_on_buffer(bh);
196 : 30 : ext4_simulate_fail_bh(sb, bh, EXT4_SIM_IBITMAP_EIO);
197 [ - + ]: 30 : if (!buffer_uptodate(bh)) {
198 : 0 : put_bh(bh);
199 : 0 : ext4_set_errno(sb, EIO);
200 : 0 : ext4_error(sb, "Cannot read inode bitmap - "
201 : : "block_group = %u, inode_bitmap = %llu",
202 : : block_group, bitmap_blk);
203 : 0 : ext4_mark_group_bitmap_corrupted(sb, block_group,
204 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
205 : 0 : return ERR_PTR(-EIO);
206 : : }
207 : :
208 : 30 : verify:
209 : 20982 : err = ext4_validate_inode_bitmap(sb, desc, block_group, bh);
210 [ - + ]: 20982 : if (err)
211 : 0 : goto out;
212 : : return bh;
213 : 0 : out:
214 : 0 : put_bh(bh);
215 : 0 : return ERR_PTR(err);
216 : : }
217 : :
218 : : /*
219 : : * NOTE! When we get the inode, we're the only people
220 : : * that have access to it, and as such there are no
221 : : * race conditions we have to worry about. The inode
222 : : * is not on the hash-lists, and it cannot be reached
223 : : * through the filesystem because the directory entry
224 : : * has been deleted earlier.
225 : : *
226 : : * HOWEVER: we must make sure that we get no aliases,
227 : : * which means that we have to call "clear_inode()"
228 : : * _before_ we mark the inode not in use in the inode
229 : : * bitmaps. Otherwise a newly created file might use
230 : : * the same inode number (not actually the same pointer
231 : : * though), and then we'd have two inodes sharing the
232 : : * same inode number and space on the harddisk.
233 : : */
234 : 300 : void ext4_free_inode(handle_t *handle, struct inode *inode)
235 : : {
236 : 300 : struct super_block *sb = inode->i_sb;
237 : 300 : int is_directory;
238 : 300 : unsigned long ino;
239 : 300 : struct buffer_head *bitmap_bh = NULL;
240 : 300 : struct buffer_head *bh2;
241 : 300 : ext4_group_t block_group;
242 : 300 : unsigned long bit;
243 : 300 : struct ext4_group_desc *gdp;
244 : 300 : struct ext4_super_block *es;
245 : 300 : struct ext4_sb_info *sbi;
246 : 300 : int fatal = 0, err, count, cleared;
247 : 300 : struct ext4_group_info *grp;
248 : :
249 [ - + ]: 300 : if (!sb) {
250 : 0 : printk(KERN_ERR "EXT4-fs: %s:%d: inode on "
251 : : "nonexistent device\n", __func__, __LINE__);
252 : 0 : return;
253 : : }
254 [ - + ]: 300 : if (atomic_read(&inode->i_count) > 1) {
255 : 0 : ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: count=%d",
256 : : __func__, __LINE__, inode->i_ino,
257 : : atomic_read(&inode->i_count));
258 : 0 : return;
259 : : }
260 [ - + ]: 300 : if (inode->i_nlink) {
261 : 0 : ext4_msg(sb, KERN_ERR, "%s:%d: inode #%lu: nlink=%d\n",
262 : : __func__, __LINE__, inode->i_ino, inode->i_nlink);
263 : 0 : return;
264 : : }
265 : 300 : sbi = EXT4_SB(sb);
266 : :
267 : 300 : ino = inode->i_ino;
268 : 300 : ext4_debug("freeing inode %lu\n", ino);
269 : 300 : trace_ext4_free_inode(inode);
270 : :
271 : 300 : dquot_initialize(inode);
272 : 300 : dquot_free_inode(inode);
273 : :
274 : 300 : is_directory = S_ISDIR(inode->i_mode);
275 : :
276 : : /* Do this BEFORE marking the inode not in use or returning an error */
277 : 300 : ext4_clear_inode(inode);
278 : :
279 : 300 : es = sbi->s_es;
280 [ + - - + ]: 300 : if (ino < EXT4_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
281 : 0 : ext4_error(sb, "reserved or nonexistent inode %lu", ino);
282 : 0 : goto error_return;
283 : : }
284 : 300 : block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
285 : 300 : bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
286 : 300 : bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
287 : : /* Don't bother if the inode bitmap is corrupt. */
288 : 300 : grp = ext4_get_group_info(sb, block_group);
289 [ - + ]: 300 : if (IS_ERR(bitmap_bh)) {
290 : 0 : fatal = PTR_ERR(bitmap_bh);
291 : 0 : bitmap_bh = NULL;
292 : 0 : goto error_return;
293 : : }
294 [ - + ]: 300 : if (unlikely(EXT4_MB_GRP_IBITMAP_CORRUPT(grp))) {
295 : 0 : fatal = -EFSCORRUPTED;
296 : 0 : goto error_return;
297 : : }
298 : :
299 : 300 : BUFFER_TRACE(bitmap_bh, "get_write_access");
300 : 300 : fatal = ext4_journal_get_write_access(handle, bitmap_bh);
301 [ - + ]: 300 : if (fatal)
302 : 0 : goto error_return;
303 : :
304 : 300 : fatal = -ESRCH;
305 : 300 : gdp = ext4_get_group_desc(sb, block_group, &bh2);
306 [ + - ]: 300 : if (gdp) {
307 : 300 : BUFFER_TRACE(bh2, "get_write_access");
308 : 300 : fatal = ext4_journal_get_write_access(handle, bh2);
309 : : }
310 : 300 : ext4_lock_group(sb, block_group);
311 : 300 : cleared = ext4_test_and_clear_bit(bit, bitmap_bh->b_data);
312 [ - + ]: 300 : if (fatal || !cleared) {
313 : 0 : ext4_unlock_group(sb, block_group);
314 : 0 : goto out;
315 : : }
316 : :
317 : 300 : count = ext4_free_inodes_count(sb, gdp) + 1;
318 : 300 : ext4_free_inodes_set(sb, gdp, count);
319 [ + + ]: 300 : if (is_directory) {
320 : 60 : count = ext4_used_dirs_count(sb, gdp) - 1;
321 : 60 : ext4_used_dirs_set(sb, gdp, count);
322 : 60 : percpu_counter_dec(&sbi->s_dirs_counter);
323 : : }
324 : 300 : ext4_inode_bitmap_csum_set(sb, block_group, gdp, bitmap_bh,
325 : 300 : EXT4_INODES_PER_GROUP(sb) / 8);
326 : 300 : ext4_group_desc_csum_set(sb, block_group, gdp);
327 : 300 : ext4_unlock_group(sb, block_group);
328 : :
329 : 300 : percpu_counter_inc(&sbi->s_freeinodes_counter);
330 [ + - ]: 300 : if (sbi->s_log_groups_per_flex) {
331 : 300 : struct flex_groups *fg;
332 : :
333 : 300 : fg = sbi_array_rcu_deref(sbi, s_flex_groups,
334 : : ext4_flex_group(sbi, block_group));
335 : 300 : atomic_inc(&fg->free_inodes);
336 [ + + ]: 300 : if (is_directory)
337 : 60 : atomic_dec(&fg->used_dirs);
338 : : }
339 : 300 : BUFFER_TRACE(bh2, "call ext4_handle_dirty_metadata");
340 : 300 : fatal = ext4_handle_dirty_metadata(handle, NULL, bh2);
341 : 300 : out:
342 [ + - ]: 300 : if (cleared) {
343 : 300 : BUFFER_TRACE(bitmap_bh, "call ext4_handle_dirty_metadata");
344 : 300 : err = ext4_handle_dirty_metadata(handle, NULL, bitmap_bh);
345 [ + - ]: 300 : if (!fatal)
346 : 300 : fatal = err;
347 : : } else {
348 : 0 : ext4_error(sb, "bit already cleared for inode %lu", ino);
349 : 0 : ext4_mark_group_bitmap_corrupted(sb, block_group,
350 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
351 : : }
352 : :
353 : 300 : error_return:
354 [ + - ]: 300 : brelse(bitmap_bh);
355 [ - + ]: 300 : ext4_std_error(sb, fatal);
356 : : }
357 : :
358 : : struct orlov_stats {
359 : : __u64 free_clusters;
360 : : __u32 free_inodes;
361 : : __u32 used_dirs;
362 : : };
363 : :
364 : : /*
365 : : * Helper function for Orlov's allocator; returns critical information
366 : : * for a particular block group or flex_bg. If flex_size is 1, then g
367 : : * is a block group number; otherwise it is flex_bg number.
368 : : */
369 : 7506 : static void get_orlov_stats(struct super_block *sb, ext4_group_t g,
370 : : int flex_size, struct orlov_stats *stats)
371 : : {
372 : 7506 : struct ext4_group_desc *desc;
373 : :
374 [ + - ]: 7506 : if (flex_size > 1) {
375 : 7506 : struct flex_groups *fg = sbi_array_rcu_deref(EXT4_SB(sb),
376 : : s_flex_groups, g);
377 : 7506 : stats->free_inodes = atomic_read(&fg->free_inodes);
378 : 7506 : stats->free_clusters = atomic64_read(&fg->free_clusters);
379 : 7506 : stats->used_dirs = atomic_read(&fg->used_dirs);
380 : 7506 : return;
381 : : }
382 : :
383 : 0 : desc = ext4_get_group_desc(sb, g, NULL);
384 [ # # ]: 0 : if (desc) {
385 : 0 : stats->free_inodes = ext4_free_inodes_count(sb, desc);
386 : 0 : stats->free_clusters = ext4_free_group_clusters(sb, desc);
387 : 0 : stats->used_dirs = ext4_used_dirs_count(sb, desc);
388 : : } else {
389 : 0 : stats->free_inodes = 0;
390 : 0 : stats->free_clusters = 0;
391 : 0 : stats->used_dirs = 0;
392 : : }
393 : : }
394 : :
395 : : /*
396 : : * Orlov's allocator for directories.
397 : : *
398 : : * We always try to spread first-level directories.
399 : : *
400 : : * If there are blockgroups with both free inodes and free blocks counts
401 : : * not worse than average we return one with smallest directory count.
402 : : * Otherwise we simply return a random group.
403 : : *
404 : : * For the rest rules look so:
405 : : *
406 : : * It's OK to put directory into a group unless
407 : : * it has too many directories already (max_dirs) or
408 : : * it has too few free inodes left (min_inodes) or
409 : : * it has too few free blocks left (min_blocks) or
410 : : * Parent's group is preferred, if it doesn't satisfy these
411 : : * conditions we search cyclically through the rest. If none
412 : : * of the groups look good we just look for a group with more
413 : : * free inodes than average (starting at parent's group).
414 : : */
415 : :
416 : 7506 : static int find_group_orlov(struct super_block *sb, struct inode *parent,
417 : : ext4_group_t *group, umode_t mode,
418 : : const struct qstr *qstr)
419 : : {
420 : 7506 : ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
421 : 7506 : struct ext4_sb_info *sbi = EXT4_SB(sb);
422 : 7506 : ext4_group_t real_ngroups = ext4_get_groups_count(sb);
423 [ + - ]: 7506 : int inodes_per_group = EXT4_INODES_PER_GROUP(sb);
424 : 7506 : unsigned int freei, avefreei, grp_free;
425 : 7506 : ext4_fsblk_t freeb, avefreec;
426 : 7506 : unsigned int ndirs;
427 : 7506 : int max_dirs, min_inodes;
428 : 7506 : ext4_grpblk_t min_clusters;
429 : 7506 : ext4_group_t i, grp, g, ngroups;
430 : 7506 : struct ext4_group_desc *desc;
431 : 7506 : struct orlov_stats stats;
432 [ + - ]: 7506 : int flex_size = ext4_flex_bg_size(sbi);
433 : 7506 : struct dx_hash_info hinfo;
434 : :
435 : 7506 : ngroups = real_ngroups;
436 [ + - ]: 7506 : if (flex_size > 1) {
437 : 7506 : ngroups = (real_ngroups + flex_size - 1) >>
438 : : sbi->s_log_groups_per_flex;
439 : 7506 : parent_group >>= sbi->s_log_groups_per_flex;
440 : : }
441 : :
442 : 7506 : freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
443 : 7506 : avefreei = freei / ngroups;
444 : 7506 : freeb = EXT4_C2B(sbi,
445 : : percpu_counter_read_positive(&sbi->s_freeclusters_counter));
446 : 7506 : avefreec = freeb;
447 : 7506 : do_div(avefreec, ngroups);
448 : 7506 : ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
449 : :
450 [ + - + - ]: 7506 : if (S_ISDIR(mode) &&
451 [ + - - + ]: 15012 : ((parent == d_inode(sb->s_root)) ||
452 : : (ext4_test_inode_flag(parent, EXT4_INODE_TOPDIR)))) {
453 : 0 : int best_ndir = inodes_per_group;
454 : 0 : int ret = -1;
455 : :
456 [ # # ]: 0 : if (qstr) {
457 : 0 : hinfo.hash_version = DX_HASH_HALF_MD4;
458 : 0 : hinfo.seed = sbi->s_hash_seed;
459 : 0 : ext4fs_dirhash(parent, qstr->name, qstr->len, &hinfo);
460 : 0 : grp = hinfo.hash;
461 : : } else
462 : 0 : grp = prandom_u32();
463 : 0 : parent_group = (unsigned)grp % ngroups;
464 [ # # ]: 0 : for (i = 0; i < ngroups; i++) {
465 : 0 : g = (parent_group + i) % ngroups;
466 : 0 : get_orlov_stats(sb, g, flex_size, &stats);
467 [ # # ]: 0 : if (!stats.free_inodes)
468 : 0 : continue;
469 [ # # ]: 0 : if (stats.used_dirs >= best_ndir)
470 : 0 : continue;
471 [ # # ]: 0 : if (stats.free_inodes < avefreei)
472 : 0 : continue;
473 [ # # ]: 0 : if (stats.free_clusters < avefreec)
474 : 0 : continue;
475 : 0 : grp = g;
476 : 0 : ret = 0;
477 : 0 : best_ndir = stats.used_dirs;
478 : : }
479 [ # # ]: 0 : if (ret)
480 : 0 : goto fallback;
481 : 0 : found_flex_bg:
482 [ - + ]: 7506 : if (flex_size == 1) {
483 : 0 : *group = grp;
484 : 0 : return 0;
485 : : }
486 : :
487 : : /*
488 : : * We pack inodes at the beginning of the flexgroup's
489 : : * inode tables. Block allocation decisions will do
490 : : * something similar, although regular files will
491 : : * start at 2nd block group of the flexgroup. See
492 : : * ext4_ext_find_goal() and ext4_find_near().
493 : : */
494 : 7506 : grp *= flex_size;
495 [ + - ]: 15012 : for (i = 0; i < flex_size; i++) {
496 [ + - ]: 15012 : if (grp+i >= real_ngroups)
497 : : break;
498 : 15012 : desc = ext4_get_group_desc(sb, grp+i, NULL);
499 [ + - + + ]: 15012 : if (desc && ext4_free_inodes_count(sb, desc)) {
500 : 7506 : *group = grp+i;
501 : 7506 : return 0;
502 : : }
503 : : }
504 : 0 : goto fallback;
505 : : }
506 : :
507 : 7506 : max_dirs = ndirs / ngroups + inodes_per_group / 16;
508 : 7506 : min_inodes = avefreei - inodes_per_group*flex_size / 4;
509 : 7506 : if (min_inodes < 1)
510 : : min_inodes = 1;
511 [ + + ]: 7506 : min_clusters = avefreec - EXT4_CLUSTERS_PER_GROUP(sb)*flex_size / 4;
512 : :
513 : : /*
514 : : * Start looking in the flex group where we last allocated an
515 : : * inode for this parent directory
516 : : */
517 [ + + ]: 7506 : if (EXT4_I(parent)->i_last_alloc_group != ~0) {
518 : 5465 : parent_group = EXT4_I(parent)->i_last_alloc_group;
519 [ + - ]: 5465 : if (flex_size > 1)
520 : 5465 : parent_group >>= sbi->s_log_groups_per_flex;
521 : : }
522 : :
523 [ + - ]: 7506 : for (i = 0; i < ngroups; i++) {
524 : 7506 : grp = (parent_group + i) % ngroups;
525 : 7506 : get_orlov_stats(sb, grp, flex_size, &stats);
526 [ - + ]: 7506 : if (stats.used_dirs >= max_dirs)
527 : 0 : continue;
528 [ - + ]: 7506 : if (stats.free_inodes < min_inodes)
529 : 0 : continue;
530 [ - + ]: 7506 : if (stats.free_clusters < min_clusters)
531 : 0 : continue;
532 : 7506 : goto found_flex_bg;
533 : : }
534 : :
535 : 0 : fallback:
536 : 0 : ngroups = real_ngroups;
537 : 0 : avefreei = freei / ngroups;
538 : 0 : fallback_retry:
539 : 0 : parent_group = EXT4_I(parent)->i_block_group;
540 [ # # ]: 0 : for (i = 0; i < ngroups; i++) {
541 : 0 : grp = (parent_group + i) % ngroups;
542 : 0 : desc = ext4_get_group_desc(sb, grp, NULL);
543 [ # # ]: 0 : if (desc) {
544 : 0 : grp_free = ext4_free_inodes_count(sb, desc);
545 [ # # ]: 0 : if (grp_free && grp_free >= avefreei) {
546 : 0 : *group = grp;
547 : 0 : return 0;
548 : : }
549 : : }
550 : : }
551 : :
552 [ # # ]: 0 : if (avefreei) {
553 : : /*
554 : : * The free-inodes counter is approximate, and for really small
555 : : * filesystems the above test can fail to find any blockgroups
556 : : */
557 : 0 : avefreei = 0;
558 : 0 : goto fallback_retry;
559 : : }
560 : :
561 : : return -1;
562 : : }
563 : :
564 : 13176 : static int find_group_other(struct super_block *sb, struct inode *parent,
565 : : ext4_group_t *group, umode_t mode)
566 : : {
567 : 13176 : ext4_group_t parent_group = EXT4_I(parent)->i_block_group;
568 : 13176 : ext4_group_t i, last, ngroups = ext4_get_groups_count(sb);
569 : 13176 : struct ext4_group_desc *desc;
570 [ + - ]: 13176 : int flex_size = ext4_flex_bg_size(EXT4_SB(sb));
571 : :
572 : : /*
573 : : * Try to place the inode is the same flex group as its
574 : : * parent. If we can't find space, use the Orlov algorithm to
575 : : * find another flex group, and store that information in the
576 : : * parent directory's inode information so that use that flex
577 : : * group for future allocations.
578 : : */
579 [ + - ]: 13176 : if (flex_size > 1) {
580 : : int retry = 0;
581 : :
582 : 13176 : try_again:
583 : 13176 : parent_group &= ~(flex_size-1);
584 : 13176 : last = parent_group + flex_size;
585 : 13176 : if (last > ngroups)
586 : : last = ngroups;
587 [ + - ]: 26352 : for (i = parent_group; i < last; i++) {
588 : 26352 : desc = ext4_get_group_desc(sb, i, NULL);
589 [ + - + + ]: 26352 : if (desc && ext4_free_inodes_count(sb, desc)) {
590 : 13176 : *group = i;
591 : 13176 : return 0;
592 : : }
593 : : }
594 [ # # # # ]: 0 : if (!retry && EXT4_I(parent)->i_last_alloc_group != ~0) {
595 : 0 : retry = 1;
596 : 0 : parent_group = EXT4_I(parent)->i_last_alloc_group;
597 : 0 : goto try_again;
598 : : }
599 : : /*
600 : : * If this didn't work, use the Orlov search algorithm
601 : : * to find a new flex group; we pass in the mode to
602 : : * avoid the topdir algorithms.
603 : : */
604 : 0 : *group = parent_group + flex_size;
605 [ # # ]: 0 : if (*group > ngroups)
606 : 0 : *group = 0;
607 : 0 : return find_group_orlov(sb, parent, group, mode, NULL);
608 : : }
609 : :
610 : : /*
611 : : * Try to place the inode in its parent directory
612 : : */
613 : 0 : *group = parent_group;
614 : 0 : desc = ext4_get_group_desc(sb, *group, NULL);
615 [ # # # # : 0 : if (desc && ext4_free_inodes_count(sb, desc) &&
# # ]
616 : 0 : ext4_free_group_clusters(sb, desc))
617 : : return 0;
618 : :
619 : : /*
620 : : * We're going to place this inode in a different blockgroup from its
621 : : * parent. We want to cause files in a common directory to all land in
622 : : * the same blockgroup. But we want files which are in a different
623 : : * directory which shares a blockgroup with our parent to land in a
624 : : * different blockgroup.
625 : : *
626 : : * So add our directory's i_ino into the starting point for the hash.
627 : : */
628 : 0 : *group = (*group + parent->i_ino) % ngroups;
629 : :
630 : : /*
631 : : * Use a quadratic hash to find a group with a free inode and some free
632 : : * blocks.
633 : : */
634 [ # # ]: 0 : for (i = 1; i < ngroups; i <<= 1) {
635 : 0 : *group += i;
636 [ # # ]: 0 : if (*group >= ngroups)
637 : 0 : *group -= ngroups;
638 : 0 : desc = ext4_get_group_desc(sb, *group, NULL);
639 [ # # # # : 0 : if (desc && ext4_free_inodes_count(sb, desc) &&
# # ]
640 : 0 : ext4_free_group_clusters(sb, desc))
641 : : return 0;
642 : : }
643 : :
644 : : /*
645 : : * That failed: try linear search for a free inode, even if that group
646 : : * has no free blocks.
647 : : */
648 : 0 : *group = parent_group;
649 [ # # ]: 0 : for (i = 0; i < ngroups; i++) {
650 [ # # ]: 0 : if (++*group >= ngroups)
651 : 0 : *group = 0;
652 : 0 : desc = ext4_get_group_desc(sb, *group, NULL);
653 [ # # # # ]: 0 : if (desc && ext4_free_inodes_count(sb, desc))
654 : : return 0;
655 : : }
656 : :
657 : : return -1;
658 : : }
659 : :
660 : : /*
661 : : * In no journal mode, if an inode has recently been deleted, we want
662 : : * to avoid reusing it until we're reasonably sure the inode table
663 : : * block has been written back to disk. (Yes, these values are
664 : : * somewhat arbitrary...)
665 : : */
666 : : #define RECENTCY_MIN 5
667 : : #define RECENTCY_DIRTY 300
668 : :
669 : 0 : static int recently_deleted(struct super_block *sb, ext4_group_t group, int ino)
670 : : {
671 : 0 : struct ext4_group_desc *gdp;
672 : 0 : struct ext4_inode *raw_inode;
673 : 0 : struct buffer_head *bh;
674 : 0 : int inodes_per_block = EXT4_SB(sb)->s_inodes_per_block;
675 : 0 : int offset, ret = 0;
676 : 0 : int recentcy = RECENTCY_MIN;
677 : 0 : u32 dtime, now;
678 : :
679 : 0 : gdp = ext4_get_group_desc(sb, group, NULL);
680 [ # # ]: 0 : if (unlikely(!gdp))
681 : : return 0;
682 : :
683 : 0 : bh = sb_find_get_block(sb, ext4_inode_table(sb, gdp) +
684 : 0 : (ino / inodes_per_block));
685 [ # # # # ]: 0 : if (!bh || !buffer_uptodate(bh))
686 : : /*
687 : : * If the block is not in the buffer cache, then it
688 : : * must have been written out.
689 : : */
690 : 0 : goto out;
691 : :
692 : 0 : offset = (ino % inodes_per_block) * EXT4_INODE_SIZE(sb);
693 : 0 : raw_inode = (struct ext4_inode *) (bh->b_data + offset);
694 : :
695 : : /* i_dtime is only 32 bits on disk, but we only care about relative
696 : : * times in the range of a few minutes (i.e. long enough to sync a
697 : : * recently-deleted inode to disk), so using the low 32 bits of the
698 : : * clock (a 68 year range) is enough, see time_before32() */
699 : 0 : dtime = le32_to_cpu(raw_inode->i_dtime);
700 : 0 : now = ktime_get_real_seconds();
701 [ # # ]: 0 : if (buffer_dirty(bh))
702 : 0 : recentcy += RECENTCY_DIRTY;
703 : :
704 [ # # # # ]: 0 : if (dtime && time_before32(dtime, now) &&
705 [ # # ]: 0 : time_before32(now, dtime + recentcy))
706 : 0 : ret = 1;
707 : 0 : out:
708 [ # # ]: 0 : brelse(bh);
709 : : return ret;
710 : : }
711 : :
712 : : static int find_inode_bit(struct super_block *sb, ext4_group_t group,
713 : : struct buffer_head *bitmap, unsigned long *ino)
714 : : {
715 : : next:
716 : : *ino = ext4_find_next_zero_bit((unsigned long *)
717 : : bitmap->b_data,
718 : : EXT4_INODES_PER_GROUP(sb), *ino);
719 : : if (*ino >= EXT4_INODES_PER_GROUP(sb))
720 : : return 0;
721 : :
722 : : if ((EXT4_SB(sb)->s_journal == NULL) &&
723 : : recently_deleted(sb, group, *ino)) {
724 : : *ino = *ino + 1;
725 : : if (*ino < EXT4_INODES_PER_GROUP(sb))
726 : : goto next;
727 : : return 0;
728 : : }
729 : :
730 : : return 1;
731 : : }
732 : :
733 : : /*
734 : : * There are two policies for allocating an inode. If the new inode is
735 : : * a directory, then a forward search is made for a block group with both
736 : : * free space and a low directory-to-inode ratio; if that fails, then of
737 : : * the groups with above-average free space, that group with the fewest
738 : : * directories already is chosen.
739 : : *
740 : : * For other inodes, search forward from the parent directory's block
741 : : * group to find a free inode.
742 : : */
743 : 20682 : struct inode *__ext4_new_inode(handle_t *handle, struct inode *dir,
744 : : umode_t mode, const struct qstr *qstr,
745 : : __u32 goal, uid_t *owner, __u32 i_flags,
746 : : int handle_type, unsigned int line_no,
747 : : int nblocks)
748 : : {
749 : 20682 : struct super_block *sb;
750 : 20682 : struct buffer_head *inode_bitmap_bh = NULL;
751 : 20682 : struct buffer_head *group_desc_bh;
752 : 20682 : ext4_group_t ngroups, group = 0;
753 : 20682 : unsigned long ino = 0;
754 : 20682 : struct inode *inode;
755 : 20682 : struct ext4_group_desc *gdp = NULL;
756 : 20682 : struct ext4_inode_info *ei;
757 : 20682 : struct ext4_sb_info *sbi;
758 : 20682 : int ret2, err;
759 : 20682 : struct inode *ret;
760 : 20682 : ext4_group_t i;
761 : 20682 : ext4_group_t flex_group;
762 : 20682 : struct ext4_group_info *grp;
763 : 20682 : int encrypt = 0;
764 : :
765 : : /* Cannot create files in a deleted directory */
766 [ + - + - ]: 20682 : if (!dir || !dir->i_nlink)
767 : : return ERR_PTR(-EPERM);
768 : :
769 : 20682 : sb = dir->i_sb;
770 : 20682 : sbi = EXT4_SB(sb);
771 : :
772 [ + - ]: 20682 : if (unlikely(ext4_forced_shutdown(sbi)))
773 : : return ERR_PTR(-EIO);
774 : :
775 [ - + ]: 20682 : if ((IS_ENCRYPTED(dir) || DUMMY_ENCRYPTION_ENABLED(sbi)) &&
776 [ # # # # ]: 0 : (S_ISREG(mode) || S_ISDIR(mode) || S_ISLNK(mode)) &&
777 [ # # ]: 0 : !(i_flags & EXT4_EA_INODE_FL)) {
778 : : err = fscrypt_get_encryption_info(dir);
779 : : if (err)
780 : : return ERR_PTR(err);
781 : : if (!fscrypt_has_encryption_key(dir))
782 : : return ERR_PTR(-ENOKEY);
783 : : encrypt = 1;
784 : : }
785 : :
786 [ + - + - : 20682 : if (!handle && sbi->s_journal && !(i_flags & EXT4_EA_INODE_FL)) {
+ - ]
787 : : #ifdef CONFIG_EXT4_FS_POSIX_ACL
788 : 20682 : struct posix_acl *p = get_acl(dir, ACL_TYPE_DEFAULT);
789 : :
790 [ + - ]: 20682 : if (IS_ERR(p))
791 : : return ERR_CAST(p);
792 [ - + ]: 20682 : if (p) {
793 : 0 : int acl_size = p->a_count * sizeof(ext4_acl_entry);
794 : :
795 [ # # ]: 0 : nblocks += (S_ISDIR(mode) ? 2 : 1) *
796 : 0 : __ext4_xattr_set_credits(sb, NULL /* inode */,
797 : : NULL /* block_bh */, acl_size,
798 : : true /* is_create */);
799 : 0 : posix_acl_release(p);
800 : : }
801 : : #endif
802 : :
803 : : #ifdef CONFIG_SECURITY
804 : : {
805 : 20682 : int num_security_xattrs = 1;
806 : :
807 : : #ifdef CONFIG_INTEGRITY
808 : 20682 : num_security_xattrs++;
809 : : #endif
810 : : /*
811 : : * We assume that security xattrs are never
812 : : * more than 1k. In practice they are under
813 : : * 128 bytes.
814 : : */
815 : 41364 : nblocks += num_security_xattrs *
816 : 20682 : __ext4_xattr_set_credits(sb, NULL /* inode */,
817 : : NULL /* block_bh */, 1024,
818 : : true /* is_create */);
819 : : }
820 : : #endif
821 : 20682 : if (encrypt)
822 : : nblocks += __ext4_xattr_set_credits(sb,
823 : : NULL /* inode */, NULL /* block_bh */,
824 : : FSCRYPT_SET_CONTEXT_MAX_SIZE,
825 : : true /* is_create */);
826 : : }
827 : :
828 : 20682 : ngroups = ext4_get_groups_count(sb);
829 : 20682 : trace_ext4_request_inode(dir, mode);
830 : 20682 : inode = new_inode(sb);
831 [ + - ]: 20682 : if (!inode)
832 : : return ERR_PTR(-ENOMEM);
833 : 20682 : ei = EXT4_I(inode);
834 : :
835 : : /*
836 : : * Initialize owners and quota early so that we don't have to account
837 : : * for quota initialization worst case in standard inode creating
838 : : * transaction
839 : : */
840 [ - + ]: 20682 : if (owner) {
841 : 0 : inode->i_mode = mode;
842 : 0 : i_uid_write(inode, owner[0]);
843 : 0 : i_gid_write(inode, owner[1]);
844 [ - + ]: 20682 : } else if (test_opt(sb, GRPID)) {
845 : 0 : inode->i_mode = mode;
846 : 0 : inode->i_uid = current_fsuid();
847 : 0 : inode->i_gid = dir->i_gid;
848 : : } else
849 : 20682 : inode_init_owner(inode, dir, mode);
850 : :
851 [ - + - - ]: 20682 : if (ext4_has_feature_project(sb) &&
852 : : ext4_test_inode_flag(dir, EXT4_INODE_PROJINHERIT))
853 : 0 : ei->i_projid = EXT4_I(dir)->i_projid;
854 : : else
855 : 20682 : ei->i_projid = make_kprojid(&init_user_ns, EXT4_DEF_PROJID);
856 : :
857 : 20682 : err = dquot_initialize(inode);
858 [ - + ]: 20682 : if (err)
859 : 0 : goto out;
860 : :
861 [ + - ]: 20682 : if (!goal)
862 : 20682 : goal = sbi->s_inode_goal;
863 : :
864 [ - + - - ]: 20682 : if (goal && goal <= le32_to_cpu(sbi->s_es->s_inodes_count)) {
865 : 0 : group = (goal - 1) / EXT4_INODES_PER_GROUP(sb);
866 : 0 : ino = (goal - 1) % EXT4_INODES_PER_GROUP(sb);
867 : 0 : ret2 = 0;
868 : 0 : goto got_group;
869 : : }
870 : :
871 [ + + ]: 20682 : if (S_ISDIR(mode))
872 : 7506 : ret2 = find_group_orlov(sb, dir, &group, mode, qstr);
873 : : else
874 : 13176 : ret2 = find_group_other(sb, dir, &group, mode);
875 : :
876 : 20682 : got_group:
877 : 20682 : EXT4_I(dir)->i_last_alloc_group = group;
878 : 20682 : err = -ENOSPC;
879 [ - + ]: 20682 : if (ret2 == -1)
880 : 0 : goto out;
881 : :
882 : : /*
883 : : * Normally we will only go through one pass of this loop,
884 : : * unless we get unlucky and it turns out the group we selected
885 : : * had its last inode grabbed by someone else.
886 : : */
887 [ + - ]: 20682 : for (i = 0; i < ngroups; i++, ino = 0) {
888 : 20682 : err = -EIO;
889 : :
890 : 20682 : gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
891 [ - + ]: 20682 : if (!gdp)
892 : 0 : goto out;
893 : :
894 : : /*
895 : : * Check free inodes count before loading bitmap.
896 : : */
897 [ - + ]: 20682 : if (ext4_free_inodes_count(sb, gdp) == 0)
898 : 0 : goto next_group;
899 : :
900 : 20682 : grp = ext4_get_group_info(sb, group);
901 : : /* Skip groups with already-known suspicious inode tables */
902 [ - + ]: 20682 : if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp))
903 : 0 : goto next_group;
904 : :
905 [ - + ]: 20682 : brelse(inode_bitmap_bh);
906 : 20682 : inode_bitmap_bh = ext4_read_inode_bitmap(sb, group);
907 : : /* Skip groups with suspicious inode tables */
908 [ + - - + ]: 20682 : if (EXT4_MB_GRP_IBITMAP_CORRUPT(grp) ||
909 : : IS_ERR(inode_bitmap_bh)) {
910 : 0 : inode_bitmap_bh = NULL;
911 : 0 : goto next_group;
912 : : }
913 : :
914 : 20682 : repeat_in_this_group:
915 : 20682 : ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino);
916 [ - + ]: 20682 : if (!ret2)
917 : 0 : goto next_group;
918 : :
919 [ - + - - ]: 20682 : if (group == 0 && (ino + 1) < EXT4_FIRST_INO(sb)) {
920 : 0 : ext4_error(sb, "reserved inode found cleared - "
921 : : "inode=%lu", ino + 1);
922 : 0 : ext4_mark_group_bitmap_corrupted(sb, group,
923 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
924 : 0 : goto next_group;
925 : : }
926 : :
927 [ + - ]: 20682 : if (!handle) {
928 [ - + ]: 20682 : BUG_ON(nblocks <= 0);
929 : 20682 : handle = __ext4_journal_start_sb(dir->i_sb, line_no,
930 : : handle_type, nblocks, 0,
931 : : ext4_trans_default_revoke_credits(sb));
932 [ - + ]: 20682 : if (IS_ERR(handle)) {
933 [ # # ]: 0 : err = PTR_ERR(handle);
934 [ # # ]: 0 : ext4_std_error(sb, err);
935 : 0 : goto out;
936 : : }
937 : : }
938 : 20682 : BUFFER_TRACE(inode_bitmap_bh, "get_write_access");
939 : 20682 : err = ext4_journal_get_write_access(handle, inode_bitmap_bh);
940 [ - + ]: 20682 : if (err) {
941 : 0 : ext4_std_error(sb, err);
942 : 0 : goto out;
943 : : }
944 : 20682 : ext4_lock_group(sb, group);
945 : 20682 : ret2 = ext4_test_and_set_bit(ino, inode_bitmap_bh->b_data);
946 [ - + ]: 20682 : if (ret2) {
947 : : /* Someone already took the bit. Repeat the search
948 : : * with lock held.
949 : : */
950 : 0 : ret2 = find_inode_bit(sb, group, inode_bitmap_bh, &ino);
951 [ # # ]: 0 : if (ret2) {
952 : 0 : ext4_set_bit(ino, inode_bitmap_bh->b_data);
953 : 0 : ret2 = 0;
954 : : } else {
955 : : ret2 = 1; /* we didn't grab the inode */
956 : : }
957 : : }
958 : 20682 : ext4_unlock_group(sb, group);
959 : 20682 : ino++; /* the inode bitmap is zero-based */
960 [ + - ]: 20682 : if (!ret2)
961 : 20682 : goto got; /* we grabbed the inode! */
962 : :
963 [ # # ]: 0 : if (ino < EXT4_INODES_PER_GROUP(sb))
964 : 0 : goto repeat_in_this_group;
965 : 0 : next_group:
966 [ # # ]: 0 : if (++group == ngroups)
967 : 0 : group = 0;
968 : : }
969 : 0 : err = -ENOSPC;
970 : 0 : goto out;
971 : :
972 : : got:
973 : 20682 : BUFFER_TRACE(inode_bitmap_bh, "call ext4_handle_dirty_metadata");
974 : 20682 : err = ext4_handle_dirty_metadata(handle, NULL, inode_bitmap_bh);
975 [ - + ]: 20682 : if (err) {
976 : 0 : ext4_std_error(sb, err);
977 : 0 : goto out;
978 : : }
979 : :
980 : 20682 : BUFFER_TRACE(group_desc_bh, "get_write_access");
981 : 20682 : err = ext4_journal_get_write_access(handle, group_desc_bh);
982 [ - + ]: 20682 : if (err) {
983 : 0 : ext4_std_error(sb, err);
984 : 0 : goto out;
985 : : }
986 : :
987 : : /* We may have to initialize the block bitmap if it isn't already */
988 [ + - ]: 20682 : if (ext4_has_group_desc_csum(sb) &&
989 [ - + ]: 20682 : gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT)) {
990 : 0 : struct buffer_head *block_bitmap_bh;
991 : :
992 : 0 : block_bitmap_bh = ext4_read_block_bitmap(sb, group);
993 [ # # ]: 0 : if (IS_ERR(block_bitmap_bh)) {
994 : 0 : err = PTR_ERR(block_bitmap_bh);
995 : 0 : goto out;
996 : : }
997 : 0 : BUFFER_TRACE(block_bitmap_bh, "get block bitmap access");
998 : 0 : err = ext4_journal_get_write_access(handle, block_bitmap_bh);
999 [ # # ]: 0 : if (err) {
1000 [ # # ]: 0 : brelse(block_bitmap_bh);
1001 : 0 : ext4_std_error(sb, err);
1002 : 0 : goto out;
1003 : : }
1004 : :
1005 : 0 : BUFFER_TRACE(block_bitmap_bh, "dirty block bitmap");
1006 : 0 : err = ext4_handle_dirty_metadata(handle, NULL, block_bitmap_bh);
1007 : :
1008 : : /* recheck and clear flag under lock if we still need to */
1009 : 0 : ext4_lock_group(sb, group);
1010 [ # # ]: 0 : if (ext4_has_group_desc_csum(sb) &&
1011 [ # # ]: 0 : (gdp->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))) {
1012 : 0 : gdp->bg_flags &= cpu_to_le16(~EXT4_BG_BLOCK_UNINIT);
1013 : 0 : ext4_free_group_clusters_set(sb, gdp,
1014 : : ext4_free_clusters_after_init(sb, group, gdp));
1015 : 0 : ext4_block_bitmap_csum_set(sb, group, gdp,
1016 : : block_bitmap_bh);
1017 : 0 : ext4_group_desc_csum_set(sb, group, gdp);
1018 : : }
1019 : 0 : ext4_unlock_group(sb, group);
1020 [ # # ]: 0 : brelse(block_bitmap_bh);
1021 : :
1022 [ # # ]: 0 : if (err) {
1023 : 0 : ext4_std_error(sb, err);
1024 : 0 : goto out;
1025 : : }
1026 : : }
1027 : :
1028 : : /* Update the relevant bg descriptor fields */
1029 [ + - ]: 20682 : if (ext4_has_group_desc_csum(sb)) {
1030 : 20682 : int free;
1031 : 20682 : struct ext4_group_info *grp = ext4_get_group_info(sb, group);
1032 : :
1033 : 20682 : down_read(&grp->alloc_sem); /* protect vs itable lazyinit */
1034 : 20682 : ext4_lock_group(sb, group); /* while we modify the bg desc */
1035 : 20682 : free = EXT4_INODES_PER_GROUP(sb) -
1036 : 20682 : ext4_itable_unused_count(sb, gdp);
1037 [ - + ]: 20682 : if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)) {
1038 : 0 : gdp->bg_flags &= cpu_to_le16(~EXT4_BG_INODE_UNINIT);
1039 : 0 : free = 0;
1040 : : }
1041 : : /*
1042 : : * Check the relative inode number against the last used
1043 : : * relative inode number in this group. if it is greater
1044 : : * we need to update the bg_itable_unused count
1045 : : */
1046 [ + + ]: 20682 : if (ino > free)
1047 : 20382 : ext4_itable_unused_set(sb, gdp,
1048 : 20382 : (EXT4_INODES_PER_GROUP(sb) - ino));
1049 : 20682 : up_read(&grp->alloc_sem);
1050 : : } else {
1051 : 0 : ext4_lock_group(sb, group);
1052 : : }
1053 : :
1054 : 20682 : ext4_free_inodes_set(sb, gdp, ext4_free_inodes_count(sb, gdp) - 1);
1055 [ + + ]: 20682 : if (S_ISDIR(mode)) {
1056 : 7506 : ext4_used_dirs_set(sb, gdp, ext4_used_dirs_count(sb, gdp) + 1);
1057 [ + - ]: 7506 : if (sbi->s_log_groups_per_flex) {
1058 : 7506 : ext4_group_t f = ext4_flex_group(sbi, group);
1059 : :
1060 : 7506 : atomic_inc(&sbi_array_rcu_deref(sbi, s_flex_groups,
1061 : : f)->used_dirs);
1062 : : }
1063 : : }
1064 [ + - ]: 20682 : if (ext4_has_group_desc_csum(sb)) {
1065 : 20682 : ext4_inode_bitmap_csum_set(sb, group, gdp, inode_bitmap_bh,
1066 : 20682 : EXT4_INODES_PER_GROUP(sb) / 8);
1067 : 20682 : ext4_group_desc_csum_set(sb, group, gdp);
1068 : : }
1069 : 20682 : ext4_unlock_group(sb, group);
1070 : :
1071 : 20682 : BUFFER_TRACE(group_desc_bh, "call ext4_handle_dirty_metadata");
1072 : 20682 : err = ext4_handle_dirty_metadata(handle, NULL, group_desc_bh);
1073 [ - + ]: 20682 : if (err) {
1074 : 0 : ext4_std_error(sb, err);
1075 : 0 : goto out;
1076 : : }
1077 : :
1078 : 20682 : percpu_counter_dec(&sbi->s_freeinodes_counter);
1079 [ + + ]: 20682 : if (S_ISDIR(mode))
1080 : 7506 : percpu_counter_inc(&sbi->s_dirs_counter);
1081 : :
1082 [ + - ]: 20682 : if (sbi->s_log_groups_per_flex) {
1083 : 20682 : flex_group = ext4_flex_group(sbi, group);
1084 : 20682 : atomic_dec(&sbi_array_rcu_deref(sbi, s_flex_groups,
1085 : : flex_group)->free_inodes);
1086 : : }
1087 : :
1088 : 20682 : inode->i_ino = ino + group * EXT4_INODES_PER_GROUP(sb);
1089 : : /* This is the optimal IO size (for stat), not the fs block size */
1090 : 20682 : inode->i_blocks = 0;
1091 : 20682 : inode->i_mtime = inode->i_atime = inode->i_ctime = current_time(inode);
1092 : 20682 : ei->i_crtime = inode->i_mtime;
1093 : :
1094 : 20682 : memset(ei->i_data, 0, sizeof(ei->i_data));
1095 : 20682 : ei->i_dir_start_lookup = 0;
1096 : 20682 : ei->i_disksize = 0;
1097 : :
1098 : : /* Don't inherit extent flag from directory, amongst others. */
1099 : 20682 : ei->i_flags =
1100 [ + + ]: 20682 : ext4_mask_flags(mode, EXT4_I(dir)->i_flags & EXT4_FL_INHERITED);
1101 : 20682 : ei->i_flags |= i_flags;
1102 : 20682 : ei->i_file_acl = 0;
1103 : 20682 : ei->i_dtime = 0;
1104 : 20682 : ei->i_block_group = group;
1105 : 20682 : ei->i_last_alloc_group = ~0;
1106 : :
1107 : 20682 : ext4_set_inode_flags(inode);
1108 [ + - - + ]: 20682 : if (IS_DIRSYNC(inode))
1109 [ # # ]: 0 : ext4_handle_sync(handle);
1110 [ - + ]: 20682 : if (insert_inode_locked(inode) < 0) {
1111 : : /*
1112 : : * Likely a bitmap corruption causing inode to be allocated
1113 : : * twice.
1114 : : */
1115 : 0 : err = -EIO;
1116 : 0 : ext4_error(sb, "failed to insert inode %lu: doubly allocated?",
1117 : : inode->i_ino);
1118 : 0 : ext4_mark_group_bitmap_corrupted(sb, group,
1119 : : EXT4_GROUP_INFO_IBITMAP_CORRUPT);
1120 : 0 : goto out;
1121 : : }
1122 : 20682 : inode->i_generation = prandom_u32();
1123 : :
1124 : : /* Precompute checksum seed for inode metadata */
1125 [ + - ]: 20682 : if (ext4_has_metadata_csum(sb)) {
1126 : 20682 : __u32 csum;
1127 : 20682 : __le32 inum = cpu_to_le32(inode->i_ino);
1128 : 20682 : __le32 gen = cpu_to_le32(inode->i_generation);
1129 : 20682 : csum = ext4_chksum(sbi, sbi->s_csum_seed, (__u8 *)&inum,
1130 : : sizeof(inum));
1131 : 20682 : ei->i_csum_seed = ext4_chksum(sbi, csum, (__u8 *)&gen,
1132 : : sizeof(gen));
1133 : : }
1134 : :
1135 : 20682 : ext4_clear_state_flags(ei); /* Only relevant on 32-bit archs */
1136 : 20682 : ext4_set_inode_state(inode, EXT4_STATE_NEW);
1137 : :
1138 : 20682 : ei->i_extra_isize = sbi->s_want_extra_isize;
1139 : 20682 : ei->i_inline_off = 0;
1140 [ - + ]: 20682 : if (ext4_has_feature_inline_data(sb))
1141 : 0 : ext4_set_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA);
1142 : 20682 : ret = inode;
1143 : 20682 : err = dquot_alloc_inode(inode);
1144 [ - + ]: 20682 : if (err)
1145 : 0 : goto fail_drop;
1146 : :
1147 : : /*
1148 : : * Since the encryption xattr will always be unique, create it first so
1149 : : * that it's less likely to end up in an external xattr block and
1150 : : * prevent its deduplication.
1151 : : */
1152 : 20682 : if (encrypt) {
1153 : : err = fscrypt_inherit_context(dir, inode, handle, true);
1154 : : if (err)
1155 : : goto fail_free_drop;
1156 : : }
1157 : :
1158 [ + - ]: 20682 : if (!(ei->i_flags & EXT4_EA_INODE_FL)) {
1159 : 20682 : err = ext4_init_acl(handle, inode, dir);
1160 [ - + ]: 20682 : if (err)
1161 : 0 : goto fail_free_drop;
1162 : :
1163 : 20682 : err = ext4_init_security(handle, inode, dir, qstr);
1164 [ - + ]: 20682 : if (err)
1165 : 0 : goto fail_free_drop;
1166 : : }
1167 : :
1168 [ + - ]: 20682 : if (ext4_has_feature_extents(sb)) {
1169 : : /* set extent flag only for directory, file and normal symlink*/
1170 [ + + + - ]: 20682 : if (S_ISDIR(mode) || S_ISREG(mode) || S_ISLNK(mode)) {
1171 : 20682 : ext4_set_inode_flag(inode, EXT4_INODE_EXTENTS);
1172 : 20682 : ext4_ext_tree_init(handle, inode);
1173 : : }
1174 : : }
1175 : :
1176 [ + - ]: 20682 : if (ext4_handle_valid(handle)) {
1177 : 20682 : ei->i_sync_tid = handle->h_transaction->t_tid;
1178 : 20682 : ei->i_datasync_tid = handle->h_transaction->t_tid;
1179 : : }
1180 : :
1181 : 20682 : err = ext4_mark_inode_dirty(handle, inode);
1182 [ - + ]: 20682 : if (err) {
1183 : 0 : ext4_std_error(sb, err);
1184 : 0 : goto fail_free_drop;
1185 : : }
1186 : :
1187 : 20682 : ext4_debug("allocating inode %lu\n", inode->i_ino);
1188 : 20682 : trace_ext4_allocate_inode(inode, dir, mode);
1189 [ + - ]: 20682 : brelse(inode_bitmap_bh);
1190 : : return ret;
1191 : :
1192 : 0 : fail_free_drop:
1193 : 0 : dquot_free_inode(inode);
1194 : 0 : fail_drop:
1195 : 0 : clear_nlink(inode);
1196 : 0 : unlock_new_inode(inode);
1197 : 0 : out:
1198 : 0 : dquot_drop(inode);
1199 : 0 : inode->i_flags |= S_NOQUOTA;
1200 : 0 : iput(inode);
1201 [ # # ]: 0 : brelse(inode_bitmap_bh);
1202 : 0 : return ERR_PTR(err);
1203 : : }
1204 : :
1205 : : /* Verify that we are loading a valid orphan from disk */
1206 : 0 : struct inode *ext4_orphan_get(struct super_block *sb, unsigned long ino)
1207 : : {
1208 [ # # ]: 0 : unsigned long max_ino = le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count);
1209 : 0 : ext4_group_t block_group;
1210 : 0 : int bit;
1211 : 0 : struct buffer_head *bitmap_bh = NULL;
1212 : 0 : struct inode *inode = NULL;
1213 : 0 : int err = -EFSCORRUPTED;
1214 : :
1215 [ # # # # ]: 0 : if (ino < EXT4_FIRST_INO(sb) || ino > max_ino)
1216 : 0 : goto bad_orphan;
1217 : :
1218 : 0 : block_group = (ino - 1) / EXT4_INODES_PER_GROUP(sb);
1219 : 0 : bit = (ino - 1) % EXT4_INODES_PER_GROUP(sb);
1220 : 0 : bitmap_bh = ext4_read_inode_bitmap(sb, block_group);
1221 [ # # ]: 0 : if (IS_ERR(bitmap_bh))
1222 : : return ERR_CAST(bitmap_bh);
1223 : :
1224 : : /* Having the inode bit set should be a 100% indicator that this
1225 : : * is a valid orphan (no e2fsck run on fs). Orphans also include
1226 : : * inodes that were being truncated, so we can't check i_nlink==0.
1227 : : */
1228 [ # # ]: 0 : if (!ext4_test_bit(bit, bitmap_bh->b_data))
1229 : 0 : goto bad_orphan;
1230 : :
1231 : 0 : inode = ext4_iget(sb, ino, EXT4_IGET_NORMAL);
1232 [ # # ]: 0 : if (IS_ERR(inode)) {
1233 : 0 : err = PTR_ERR(inode);
1234 : 0 : ext4_set_errno(sb, -err);
1235 : 0 : ext4_error(sb, "couldn't read orphan inode %lu (err %d)",
1236 : : ino, err);
1237 : 0 : return inode;
1238 : : }
1239 : :
1240 : : /*
1241 : : * If the orphans has i_nlinks > 0 then it should be able to
1242 : : * be truncated, otherwise it won't be removed from the orphan
1243 : : * list during processing and an infinite loop will result.
1244 : : * Similarly, it must not be a bad inode.
1245 : : */
1246 [ # # # # : 0 : if ((inode->i_nlink && !ext4_can_truncate(inode)) ||
# # ]
1247 : 0 : is_bad_inode(inode))
1248 : 0 : goto bad_orphan;
1249 : :
1250 [ # # ]: 0 : if (NEXT_ORPHAN(inode) > max_ino)
1251 : 0 : goto bad_orphan;
1252 [ # # ]: 0 : brelse(bitmap_bh);
1253 : : return inode;
1254 : :
1255 : 0 : bad_orphan:
1256 : 0 : ext4_error(sb, "bad orphan inode %lu", ino);
1257 [ # # ]: 0 : if (bitmap_bh)
1258 : 0 : printk(KERN_ERR "ext4_test_bit(bit=%d, block=%llu) = %d\n",
1259 : 0 : bit, (unsigned long long)bitmap_bh->b_blocknr,
1260 : 0 : ext4_test_bit(bit, bitmap_bh->b_data));
1261 [ # # ]: 0 : if (inode) {
1262 : 0 : printk(KERN_ERR "is_bad_inode(inode)=%d\n",
1263 : 0 : is_bad_inode(inode));
1264 : 0 : printk(KERN_ERR "NEXT_ORPHAN(inode)=%u\n",
1265 : 0 : NEXT_ORPHAN(inode));
1266 : 0 : printk(KERN_ERR "max_ino=%lu\n", max_ino);
1267 : 0 : printk(KERN_ERR "i_nlink=%u\n", inode->i_nlink);
1268 : : /* Avoid freeing blocks if we got a bad deleted inode */
1269 [ # # ]: 0 : if (inode->i_nlink == 0)
1270 : 0 : inode->i_blocks = 0;
1271 : 0 : iput(inode);
1272 : : }
1273 [ # # ]: 0 : brelse(bitmap_bh);
1274 : : return ERR_PTR(err);
1275 : : }
1276 : :
1277 : 60 : unsigned long ext4_count_free_inodes(struct super_block *sb)
1278 : : {
1279 : 60 : unsigned long desc_count;
1280 : 60 : struct ext4_group_desc *gdp;
1281 : 60 : ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1282 : : #ifdef EXT4FS_DEBUG
1283 : : struct ext4_super_block *es;
1284 : : unsigned long bitmap_count, x;
1285 : : struct buffer_head *bitmap_bh = NULL;
1286 : :
1287 : : es = EXT4_SB(sb)->s_es;
1288 : : desc_count = 0;
1289 : : bitmap_count = 0;
1290 : : gdp = NULL;
1291 : : for (i = 0; i < ngroups; i++) {
1292 : : gdp = ext4_get_group_desc(sb, i, NULL);
1293 : : if (!gdp)
1294 : : continue;
1295 : : desc_count += ext4_free_inodes_count(sb, gdp);
1296 : : brelse(bitmap_bh);
1297 : : bitmap_bh = ext4_read_inode_bitmap(sb, i);
1298 : : if (IS_ERR(bitmap_bh)) {
1299 : : bitmap_bh = NULL;
1300 : : continue;
1301 : : }
1302 : :
1303 : : x = ext4_count_free(bitmap_bh->b_data,
1304 : : EXT4_INODES_PER_GROUP(sb) / 8);
1305 : : printk(KERN_DEBUG "group %lu: stored = %d, counted = %lu\n",
1306 : : (unsigned long) i, ext4_free_inodes_count(sb, gdp), x);
1307 : : bitmap_count += x;
1308 : : }
1309 : : brelse(bitmap_bh);
1310 : : printk(KERN_DEBUG "ext4_count_free_inodes: "
1311 : : "stored = %u, computed = %lu, %lu\n",
1312 : : le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
1313 : : return desc_count;
1314 : : #else
1315 : 60 : desc_count = 0;
1316 [ + + ]: 3000 : for (i = 0; i < ngroups; i++) {
1317 : 2880 : gdp = ext4_get_group_desc(sb, i, NULL);
1318 [ - + ]: 2880 : if (!gdp)
1319 : 0 : continue;
1320 : 2880 : desc_count += ext4_free_inodes_count(sb, gdp);
1321 : 2880 : cond_resched();
1322 : : }
1323 : 60 : return desc_count;
1324 : : #endif
1325 : : }
1326 : :
1327 : : /* Called at mount-time, super-block is locked */
1328 : 60 : unsigned long ext4_count_dirs(struct super_block * sb)
1329 : : {
1330 : 60 : unsigned long count = 0;
1331 : 60 : ext4_group_t i, ngroups = ext4_get_groups_count(sb);
1332 : :
1333 [ + + ]: 3000 : for (i = 0; i < ngroups; i++) {
1334 : 2880 : struct ext4_group_desc *gdp = ext4_get_group_desc(sb, i, NULL);
1335 [ - + ]: 2880 : if (!gdp)
1336 : 0 : continue;
1337 : 2880 : count += ext4_used_dirs_count(sb, gdp);
1338 : : }
1339 : 60 : return count;
1340 : : }
1341 : :
1342 : : /*
1343 : : * Zeroes not yet zeroed inode table - just write zeroes through the whole
1344 : : * inode table. Must be called without any spinlock held. The only place
1345 : : * where it is called from on active part of filesystem is ext4lazyinit
1346 : : * thread, so we do not need any special locks, however we have to prevent
1347 : : * inode allocation from the current group, so we take alloc_sem lock, to
1348 : : * block ext4_new_inode() until we are finished.
1349 : : */
1350 : 0 : int ext4_init_inode_table(struct super_block *sb, ext4_group_t group,
1351 : : int barrier)
1352 : : {
1353 : 0 : struct ext4_group_info *grp = ext4_get_group_info(sb, group);
1354 [ # # ]: 0 : struct ext4_sb_info *sbi = EXT4_SB(sb);
1355 : 0 : struct ext4_group_desc *gdp = NULL;
1356 : 0 : struct buffer_head *group_desc_bh;
1357 : 0 : handle_t *handle;
1358 : 0 : ext4_fsblk_t blk;
1359 : 0 : int num, ret = 0, used_blks = 0;
1360 : :
1361 : : /* This should not happen, but just to be sure check this */
1362 [ # # ]: 0 : if (sb_rdonly(sb)) {
1363 : 0 : ret = 1;
1364 : 0 : goto out;
1365 : : }
1366 : :
1367 : 0 : gdp = ext4_get_group_desc(sb, group, &group_desc_bh);
1368 [ # # ]: 0 : if (!gdp)
1369 : 0 : goto out;
1370 : :
1371 : : /*
1372 : : * We do not need to lock this, because we are the only one
1373 : : * handling this flag.
1374 : : */
1375 [ # # ]: 0 : if (gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_ZEROED))
1376 : 0 : goto out;
1377 : :
1378 : 0 : handle = ext4_journal_start_sb(sb, EXT4_HT_MISC, 1);
1379 [ # # ]: 0 : if (IS_ERR(handle)) {
1380 : 0 : ret = PTR_ERR(handle);
1381 : 0 : goto out;
1382 : : }
1383 : :
1384 : 0 : down_write(&grp->alloc_sem);
1385 : : /*
1386 : : * If inode bitmap was already initialized there may be some
1387 : : * used inodes so we need to skip blocks with used inodes in
1388 : : * inode table.
1389 : : */
1390 [ # # ]: 0 : if (!(gdp->bg_flags & cpu_to_le16(EXT4_BG_INODE_UNINIT)))
1391 : 0 : used_blks = DIV_ROUND_UP((EXT4_INODES_PER_GROUP(sb) -
1392 : : ext4_itable_unused_count(sb, gdp)),
1393 : : sbi->s_inodes_per_block);
1394 : :
1395 [ # # # # : 0 : if ((used_blks < 0) || (used_blks > sbi->s_itb_per_group) ||
# # ]
1396 : 0 : ((group == 0) && ((EXT4_INODES_PER_GROUP(sb) -
1397 : 0 : ext4_itable_unused_count(sb, gdp)) <
1398 [ # # ]: 0 : EXT4_FIRST_INO(sb)))) {
1399 : 0 : ext4_error(sb, "Something is wrong with group %u: "
1400 : : "used itable blocks: %d; "
1401 : : "itable unused count: %u",
1402 : : group, used_blks,
1403 : : ext4_itable_unused_count(sb, gdp));
1404 : 0 : ret = 1;
1405 : 0 : goto err_out;
1406 : : }
1407 : :
1408 : 0 : blk = ext4_inode_table(sb, gdp) + used_blks;
1409 : 0 : num = sbi->s_itb_per_group - used_blks;
1410 : :
1411 : 0 : BUFFER_TRACE(group_desc_bh, "get_write_access");
1412 : 0 : ret = ext4_journal_get_write_access(handle,
1413 : : group_desc_bh);
1414 [ # # ]: 0 : if (ret)
1415 : 0 : goto err_out;
1416 : :
1417 : : /*
1418 : : * Skip zeroout if the inode table is full. But we set the ZEROED
1419 : : * flag anyway, because obviously, when it is full it does not need
1420 : : * further zeroing.
1421 : : */
1422 [ # # ]: 0 : if (unlikely(num == 0))
1423 : 0 : goto skip_zeroout;
1424 : :
1425 : 0 : ext4_debug("going to zero out inode table in group %d\n",
1426 : : group);
1427 : 0 : ret = sb_issue_zeroout(sb, blk, num, GFP_NOFS);
1428 [ # # ]: 0 : if (ret < 0)
1429 : 0 : goto err_out;
1430 [ # # ]: 0 : if (barrier)
1431 : 0 : blkdev_issue_flush(sb->s_bdev, GFP_NOFS, NULL);
1432 : :
1433 : 0 : skip_zeroout:
1434 : 0 : ext4_lock_group(sb, group);
1435 : 0 : gdp->bg_flags |= cpu_to_le16(EXT4_BG_INODE_ZEROED);
1436 : 0 : ext4_group_desc_csum_set(sb, group, gdp);
1437 : 0 : ext4_unlock_group(sb, group);
1438 : :
1439 : 0 : BUFFER_TRACE(group_desc_bh,
1440 : : "call ext4_handle_dirty_metadata");
1441 : 0 : ret = ext4_handle_dirty_metadata(handle, NULL,
1442 : : group_desc_bh);
1443 : :
1444 : 0 : err_out:
1445 : 0 : up_write(&grp->alloc_sem);
1446 : 0 : ext4_journal_stop(handle);
1447 : 0 : out:
1448 : 0 : return ret;
1449 : : }
|
