1 // SPDX-License-Identifier: GPL-2.0
7  * Laboratoire MASI - Institut Blaise Pascal
10  *  BSD ufs-inspired inode and directory allocation by 
12  *  Big-endian to little-endian byte-swapping/bitmaps by
18 #include <linux/backing-dev.h>
31  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
34  * The file system contains group descriptors which are located after the
56 	bh = sb_bread(sb, le32_to_cpu(desc->bg_inode_bitmap));  in read_inode_bitmap()
59 			    "Cannot read inode bitmap - "  in read_inode_bitmap()
61 			    block_group, le32_to_cpu(desc->bg_inode_bitmap));  in read_inode_bitmap()
66 static void ext2_release_inode(struct super_block *sb, int group, int dir)  in ext2_release_inode()  argument
71 	desc = ext2_get_group_desc(sb, group, &bh);  in ext2_release_inode()
74 			"can't get descriptor for group %d", group);  in ext2_release_inode()
78 	spin_lock(sb_bgl_lock(EXT2_SB(sb), group));  in ext2_release_inode()
79 	le16_add_cpu(&desc->bg_free_inodes_count, 1);  in ext2_release_inode()
81 		le16_add_cpu(&desc->bg_used_dirs_count, -1);  in ext2_release_inode()
82 	spin_unlock(sb_bgl_lock(EXT2_SB(sb), group));  in ext2_release_inode()
83 	percpu_counter_inc(&EXT2_SB(sb)->s_freeinodes_counter);  in ext2_release_inode()
85 		percpu_counter_dec(&EXT2_SB(sb)->s_dirs_counter);  in ext2_release_inode()
93  * is not on the hash-lists, and it cannot be reached
107 	struct super_block * sb = inode->i_sb;  in ext2_free_inode()
115 	ino = inode->i_ino;  in ext2_free_inode()
126 	es = EXT2_SB(sb)->s_es;  in ext2_free_inode()
127 	is_directory = S_ISDIR(inode->i_mode);  in ext2_free_inode()
130 	    ino > le32_to_cpu(es->s_inodes_count)) {  in ext2_free_inode()
135 	block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);  in ext2_free_inode()
136 	bit = (ino - 1) % EXT2_INODES_PER_GROUP(sb);  in ext2_free_inode()
143 				bit, (void *) bitmap_bh->b_data))  in ext2_free_inode()
149 	if (sb->s_flags & SB_SYNCHRONOUS)  in ext2_free_inode()
160  * - When creating a large number of files, the async prereads will be
162  * - When writing out a large number of inodes, we don't need to keep on
174 	block_group = (inode->i_ino - 1) / EXT2_INODES_PER_GROUP(inode->i_sb);  in ext2_preread_inode()
175 	gdp = ext2_get_group_desc(inode->i_sb, block_group, NULL);  in ext2_preread_inode()
180 	 * Figure out the offset within the block group inode table  in ext2_preread_inode()
182 	offset = ((inode->i_ino - 1) % EXT2_INODES_PER_GROUP(inode->i_sb)) *  in ext2_preread_inode()
183 				EXT2_INODE_SIZE(inode->i_sb);  in ext2_preread_inode()
184 	block = le32_to_cpu(gdp->bg_inode_table) +  in ext2_preread_inode()
185 				(offset >> EXT2_BLOCK_SIZE_BITS(inode->i_sb));  in ext2_preread_inode()
186 	sb_breadahead(inode->i_sb, block);  in ext2_preread_inode()
191  * a directory, then a forward search is made for a block group with both
192  * free space and a low directory-to-inode ratio; if that fails, then of
193  * the groups with above-average free space, that group with the fewest
197  * group to find a free inode.
201 	int ngroups = EXT2_SB(sb)->s_groups_count;  in find_group_dir()
204 	int group, best_group = -1;  in find_group_dir()  local
206 	for (group = 0; group < ngroups; group++) {  in find_group_dir()
207 		desc = ext2_get_group_desc (sb, group, NULL);  in find_group_dir()
208 		if (!desc || !desc->bg_free_inodes_count)  in find_group_dir()
210 		if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)  in find_group_dir()
213 		    (le16_to_cpu(desc->bg_free_blocks_count) >  in find_group_dir()
214 		     le16_to_cpu(best_desc->bg_free_blocks_count))) {  in find_group_dir()
215 			best_group = group;  in find_group_dir()
226  * We always try to spread first-level directories.
230  * Otherwise we simply return a random group. 
234  * It's OK to put directory into a group unless 
239  * Parent's group is preferred, if it doesn't satisfy these 
241  * of the groups look good we just look for a group with more 
242  * free inodes than average (starting at parent's group). 
245  * when we allocate an inode, within 0--255. 
253 	int parent_group = EXT2_I(parent)->i_block_group;  in find_group_orlov()
255 	struct ext2_super_block *es = sbi->s_es;  in find_group_orlov()
256 	int ngroups = sbi->s_groups_count;  in find_group_orlov()
265 	int group = -1, i;  in find_group_orlov()  local
268 	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);  in find_group_orlov()
270 	free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);  in find_group_orlov()
272 	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);  in find_group_orlov()
274 	if ((parent == d_inode(sb->s_root)) ||  in find_group_orlov()
275 	    (EXT2_I(parent)->i_flags & EXT2_TOPDIR_FL)) {  in find_group_orlov()
277 		int best_group = -1;  in find_group_orlov()
281 			group = (parent_group + i) % ngroups;  in find_group_orlov()
282 			desc = ext2_get_group_desc (sb, group, NULL);  in find_group_orlov()
283 			if (!desc || !desc->bg_free_inodes_count)  in find_group_orlov()
285 			if (le16_to_cpu(desc->bg_used_dirs_count) >= best_ndir)  in find_group_orlov()
287 			if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)  in find_group_orlov()
289 			if (le16_to_cpu(desc->bg_free_blocks_count) < avefreeb)  in find_group_orlov()
291 			best_group = group;  in find_group_orlov()
292 			best_ndir = le16_to_cpu(desc->bg_used_dirs_count);  in find_group_orlov()
295 			group = best_group;  in find_group_orlov()
304 	blocks_per_dir = (le32_to_cpu(es->s_blocks_count)-free_blocks) / ndirs;  in find_group_orlov()
307 	min_inodes = avefreei - inodes_per_group / 4;  in find_group_orlov()
308 	min_blocks = avefreeb - EXT2_BLOCKS_PER_GROUP(sb) / 4;  in find_group_orlov()
319 		group = (parent_group + i) % ngroups;  in find_group_orlov()
320 		desc = ext2_get_group_desc (sb, group, NULL);  in find_group_orlov()
321 		if (!desc || !desc->bg_free_inodes_count)  in find_group_orlov()
323 		if (sbi->s_debts[group] >= max_debt)  in find_group_orlov()
325 		if (le16_to_cpu(desc->bg_used_dirs_count) >= max_dirs)  in find_group_orlov()
327 		if (le16_to_cpu(desc->bg_free_inodes_count) < min_inodes)  in find_group_orlov()
329 		if (le16_to_cpu(desc->bg_free_blocks_count) < min_blocks)  in find_group_orlov()
336 		group = (parent_group + i) % ngroups;  in find_group_orlov()
337 		desc = ext2_get_group_desc (sb, group, NULL);  in find_group_orlov()
338 		if (!desc || !desc->bg_free_inodes_count)  in find_group_orlov()
340 		if (le16_to_cpu(desc->bg_free_inodes_count) >= avefreei)  in find_group_orlov()
346 		 * The free-inodes counter is approximate, and for really small  in find_group_orlov()
353 	return -1;  in find_group_orlov()
356 	return group;  in find_group_orlov()
361 	int parent_group = EXT2_I(parent)->i_block_group;  in find_group_other()
362 	int ngroups = EXT2_SB(sb)->s_groups_count;  in find_group_other()
364 	int group, i;  in find_group_other()  local
369 	group = parent_group;  in find_group_other()
370 	desc = ext2_get_group_desc (sb, group, NULL);  in find_group_other()
371 	if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&  in find_group_other()
372 			le16_to_cpu(desc->bg_free_blocks_count))  in find_group_other()
384 	group = (group + parent->i_ino) % ngroups;  in find_group_other()
387 	 * Use a quadratic hash to find a group with a free inode and some  in find_group_other()
391 		group += i;  in find_group_other()
392 		if (group >= ngroups)  in find_group_other()
393 			group -= ngroups;  in find_group_other()
394 		desc = ext2_get_group_desc (sb, group, NULL);  in find_group_other()
395 		if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&  in find_group_other()
396 				le16_to_cpu(desc->bg_free_blocks_count))  in find_group_other()
401 	 * That failed: try linear search for a free inode, even if that group  in find_group_other()
404 	group = parent_group;  in find_group_other()
406 		if (++group >= ngroups)  in find_group_other()
407 			group = 0;  in find_group_other()
408 		desc = ext2_get_group_desc (sb, group, NULL);  in find_group_other()
409 		if (desc && le16_to_cpu(desc->bg_free_inodes_count))  in find_group_other()
413 	return -1;  in find_group_other()
416 	return group;  in find_group_other()
425 	int group, i;  in ext2_new_inode()  local
434 	sb = dir->i_sb;  in ext2_new_inode()
437 		return ERR_PTR(-ENOMEM);  in ext2_new_inode()
441 	es = sbi->s_es;  in ext2_new_inode()
444 			group = find_group_dir(sb, dir);  in ext2_new_inode()
446 			group = find_group_orlov(sb, dir);  in ext2_new_inode()
448 		group = find_group_other(sb, dir);  in ext2_new_inode()
450 	if (group == -1) {  in ext2_new_inode()
451 		err = -ENOSPC;  in ext2_new_inode()
455 	for (i = 0; i < sbi->s_groups_count; i++) {  in ext2_new_inode()
456 		gdp = ext2_get_group_desc(sb, group, &bh2);  in ext2_new_inode()
458 			if (++group == sbi->s_groups_count)  in ext2_new_inode()
459 				group = 0;  in ext2_new_inode()
463 		bitmap_bh = read_inode_bitmap(sb, group);  in ext2_new_inode()
465 			err = -EIO;  in ext2_new_inode()
471 		ino = ext2_find_next_zero_bit((unsigned long *)bitmap_bh->b_data,  in ext2_new_inode()
476 			 * free inodes in this group, but by the time we tried  in ext2_new_inode()
480 			 * next block group.  in ext2_new_inode()
482 			if (++group == sbi->s_groups_count)  in ext2_new_inode()
483 				group = 0;  in ext2_new_inode()
486 		if (ext2_set_bit_atomic(sb_bgl_lock(sbi, group),  in ext2_new_inode()
487 						ino, bitmap_bh->b_data)) {  in ext2_new_inode()
490 				/* this group is exhausted, try next group */  in ext2_new_inode()
491 				if (++group == sbi->s_groups_count)  in ext2_new_inode()
492 					group = 0;  in ext2_new_inode()
495 			/* try to find free inode in the same group */  in ext2_new_inode()
505 	err = -ENOSPC;  in ext2_new_inode()
509 	if (sb->s_flags & SB_SYNCHRONOUS)  in ext2_new_inode()
513 	ino += group * EXT2_INODES_PER_GROUP(sb) + 1;  in ext2_new_inode()
514 	if (ino < EXT2_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {  in ext2_new_inode()
516 			    "reserved inode or inode > inodes count - "  in ext2_new_inode()
517 			    "block_group = %d,inode=%lu", group,  in ext2_new_inode()
519 		err = -EIO;  in ext2_new_inode()
523 	percpu_counter_dec(&sbi->s_freeinodes_counter);  in ext2_new_inode()
525 		percpu_counter_inc(&sbi->s_dirs_counter);  in ext2_new_inode()
527 	spin_lock(sb_bgl_lock(sbi, group));  in ext2_new_inode()
528 	le16_add_cpu(&gdp->bg_free_inodes_count, -1);  in ext2_new_inode()
530 		if (sbi->s_debts[group] < 255)  in ext2_new_inode()
531 			sbi->s_debts[group]++;  in ext2_new_inode()
532 		le16_add_cpu(&gdp->bg_used_dirs_count, 1);  in ext2_new_inode()
534 		if (sbi->s_debts[group])  in ext2_new_inode()
535 			sbi->s_debts[group]--;  in ext2_new_inode()
537 	spin_unlock(sb_bgl_lock(sbi, group));  in ext2_new_inode()
541 		inode->i_mode = mode;  in ext2_new_inode()
542 		inode->i_uid = current_fsuid();  in ext2_new_inode()
543 		inode->i_gid = dir->i_gid;  in ext2_new_inode()
547 	inode->i_ino = ino;  in ext2_new_inode()
548 	inode->i_blocks = 0;  in ext2_new_inode()
550 	memset(ei->i_data, 0, sizeof(ei->i_data));  in ext2_new_inode()
551 	ei->i_flags =  in ext2_new_inode()
552 		ext2_mask_flags(mode, EXT2_I(dir)->i_flags & EXT2_FL_INHERITED);  in ext2_new_inode()
553 	ei->i_faddr = 0;  in ext2_new_inode()
554 	ei->i_frag_no = 0;  in ext2_new_inode()
555 	ei->i_frag_size = 0;  in ext2_new_inode()
556 	ei->i_file_acl = 0;  in ext2_new_inode()
557 	ei->i_dir_acl = 0;  in ext2_new_inode()
558 	ei->i_dtime = 0;  in ext2_new_inode()
559 	ei->i_block_alloc_info = NULL;  in ext2_new_inode()
560 	ei->i_block_group = group;  in ext2_new_inode()
561 	ei->i_dir_start_lookup = 0;  in ext2_new_inode()
562 	ei->i_state = EXT2_STATE_NEW;  in ext2_new_inode()
564 	spin_lock(&sbi->s_next_gen_lock);  in ext2_new_inode()
565 	inode->i_generation = sbi->s_next_generation++;  in ext2_new_inode()
566 	spin_unlock(&sbi->s_next_gen_lock);  in ext2_new_inode()
569 			   "inode number already in use - inode=%lu",  in ext2_new_inode()
571 		err = -EIO;  in ext2_new_inode()
592 	ext2_debug("allocating inode %lu\n", inode->i_ino);  in ext2_new_inode()
601 	inode->i_flags |= S_NOQUOTA;  in ext2_new_inode()
623 	es = EXT2_SB(sb)->s_es;  in ext2_count_free_inodes()
624 	for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {  in ext2_count_free_inodes()
630 		desc_count += le16_to_cpu(desc->bg_free_inodes_count);  in ext2_count_free_inodes()
637 		printk("group %d: stored = %d, counted = %u\n",  in ext2_count_free_inodes()
638 			i, le16_to_cpu(desc->bg_free_inodes_count), x);  in ext2_count_free_inodes()
644 		percpu_counter_read(&EXT2_SB(sb)->s_freeinodes_counter),  in ext2_count_free_inodes()
648 	for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {  in ext2_count_free_inodes()
652 		desc_count += le16_to_cpu(desc->bg_free_inodes_count);  in ext2_count_free_inodes()
658 /* Called at mount-time, super-block is locked */
664 	for (i = 0; i < EXT2_SB(sb)->s_groups_count; i++) {  in ext2_count_dirs()
668 		count += le16_to_cpu(gdp->bg_used_dirs_count);  in ext2_count_dirs()