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