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