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