9  *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
32  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
33  * block for inodes, N blocks for the inode table and data blocks.
36  * super block.  Each descriptor contains the number of the bitmap block and
37  * the free blocks count in the block.  The descriptors are loaded in memory
45  * Calculate the block group number and offset, given a block number
61  * @sb:			super block
62  * @block_group:	given block group
63  * @bh:			pointer to the buffer head to store the block
113 	/* check whether block bitmap block number is set */  in ext3_valid_block_bitmap()
117 		/* bad block bitmap */  in ext3_valid_block_bitmap()
120 	/* check whether the inode bitmap block number is set */  in ext3_valid_block_bitmap()
124 		/* bad block bitmap */  in ext3_valid_block_bitmap()
127 	/* check whether the inode table block number is set */  in ext3_valid_block_bitmap()
139 			"Invalid block bitmap - "  in ext3_valid_block_bitmap()
140 			"block_group = %d, block = %lu",  in ext3_valid_block_bitmap()
147  * @sb:			super block
148  * @block_group:	given block group
151  * bits for block/inode/inode tables are set in the bitmaps
170 			    "Cannot read block bitmap - "  in read_block_bitmap()
181 			    "Cannot read block bitmap - "  in read_block_bitmap()
205  * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
210  * If verbose is turned on, it will print the whole block reservation
227 	printk("Block Allocation Reservation Windows Map (%s):\n", fn);  in __rsv_window_dump()
266  * @grp_goal:		given goal block relative to the allocation block group
267  * @group:		the current allocation block group
268  * @sb:			filesystem super block
270  * Test if the given goal block (group relative) is within the file's
271  * own block reservation window range.
274  * grp_goal (given goal block) could be -1, which means no specific
275  * goal block. In this case, always return 1.
276  * If the goal block is within the reservation window, return 1;
300  * @goal:		target allocation block
339  * ext3_rsv_window_add() -- Insert a window to the block reservation rb tree.
340  * @sb:			super block
378  * @sb:			super block
381  * Mark the block reservation window as not allocated, and unlink it
398  * returns 1 if the end block is EXT3_RESERVE_WINDOW_NOT_ALLOCATED.
402 	/* a valid reservation end block could not be 0 */  in rsv_is_empty()
415  * needs a new block. So, before every ext3_new_block(s) call, for
418  * Fail to do so will result in block reservation being turned off for that
423  * is open for write (needs block allocation).
443 		 * block reservation is off  in ext3_init_block_alloc_info()
460  * Discard(free) block reservation window on last file close, or truncate
466  *	ext3_truncate(): when the block indirect map is about to change.
493  * @sb:				super block
494  * @block:			start physcial block to free
499 			 ext3_fsblk_t block, unsigned long count,  in ext3_free_blocks_sb()  argument
517 	if (block < le32_to_cpu(es->s_first_data_block) ||  in ext3_free_blocks_sb()
518 	    block + count < block ||  in ext3_free_blocks_sb()
519 	    block + count > le32_to_cpu(es->s_blocks_count)) {  in ext3_free_blocks_sb()
522 			    "block = "E3FSBLK", count = %lu", block, count);  in ext3_free_blocks_sb()
526 	ext3_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);  in ext3_free_blocks_sb()
530 	block_group = (block - le32_to_cpu(es->s_first_data_block)) /  in ext3_free_blocks_sb()
532 	bit = (block - le32_to_cpu(es->s_first_data_block)) %  in ext3_free_blocks_sb()
550 	if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||  in ext3_free_blocks_sb()
551 	    in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||  in ext3_free_blocks_sb()
552 	    in_range (block, le32_to_cpu(desc->bg_inode_table),  in ext3_free_blocks_sb()
554 	    in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),  in ext3_free_blocks_sb()
558 			    "Block = "E3FSBLK", count = %lu",  in ext3_free_blocks_sb()
559 			    block, count);  in ext3_free_blocks_sb()
593 			debug_bh = sb_find_get_block(sb, block + i);  in ext3_free_blocks_sb()
616 		 * revoking the queued write of a data block, which  in ext3_free_blocks_sb()
618 		 * cannot block due to truncate races.  in ext3_free_blocks_sb()
644 				"bit already cleared for block "E3FSBLK,  in ext3_free_blocks_sb()
645 				 block + i);  in ext3_free_blocks_sb()
659 	/* We dirtied the bitmap block */  in ext3_free_blocks_sb()
660 	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");  in ext3_free_blocks_sb()
663 	/* And the group descriptor block */  in ext3_free_blocks_sb()
664 	BUFFER_TRACE(gd_bh, "dirtied group descriptor block");  in ext3_free_blocks_sb()
670 		block += count;  in ext3_free_blocks_sb()
685  * @block:		start physical block to free
689 			ext3_fsblk_t block, unsigned long count)  in ext3_free_blocks()  argument
694 	trace_ext3_free_blocks(inode, block, count);  in ext3_free_blocks()
695 	ext3_free_blocks_sb(handle, sb, block, count, &dquot_freed_blocks);  in ext3_free_blocks()
703  * @nr:			given allocation block group
704  * @bh:			bufferhead contains the bitmap of the given block group
712  * data would allow the old block to be overwritten before the
740  * @start:		the starting block (group relative) of the search
741  * @bh:			bufferhead contains the block group bitmap
742  * @maxblocks:		the ending block (group relative) of the reservation
772  * @start:		the starting block (group relative) to find next
773  *			allocatable block in bitmap.
774  * @bh:			bufferhead contains the block group bitmap
775  * @maxblocks:		the ending block (group relative) for the search
777  * Find an allocatable block in a bitmap.  We honor both the bitmap and
779  * appropriate allocation" algorithm of looking for a free block near
793 		 * block within the next XX blocks.  in find_next_usable_block()
830  * @lock:		the spin lock for this block group
831  * @block:		the free block (group relative) to allocate
832  * @bh:			the buffer_head contains the block group bitmap
834  * We think we can allocate this block in this bitmap.  Try to set the bit.
836  * block since we saw that is was not marked in b_committed_data.  If it _was_
841 claim_block(spinlock_t *lock, ext3_grpblk_t block, struct buffer_head *bh)  in claim_block()  argument
846 	if (ext3_set_bit_atomic(lock, block, bh->b_data))  in claim_block()
849 	if (jh->b_committed_data && ext3_test_bit(block,jh->b_committed_data)) {  in claim_block()
850 		ext3_clear_bit_atomic(lock, block, bh->b_data);  in claim_block()
863  * @group:		given allocation block group
864  * @bitmap_bh:		bufferhead holds the block bitmap
865  * @grp_goal:		given target block within the group
874  *	if there is a reservation window, only try to allocate block(s) from the
876  *	Otherwise, the allocation range starts from the give goal block, ends at
877  *	the block group's last block.
879  * If we failed to allocate the desired block then we may end up crossing to a
938 		 * The block was allocated by another thread, or it was  in ext3_try_to_allocate()
979  *	@sb: the super block
981  *	@start_block: the first block we consider to start
985  *		the maximum block number that our goal reservable space
986  *		could start from. This is normally the last block in this
1092  *		there, we check the bitmap for the first free block after
1093  *		it. If there is no free block until the end of group, then the
1095  *		block is inside the expected reservable space, if so, we
1097  *		If the first free block is outside the reservable space, then
1098  *		start from the first free block, we search for next available
1102  *	It contains at least one free block, and it does not overlap with other
1112  *		no grp_goal(grp_goal = -1), we start from the first block
1115  *	@sb: the super block
1117  *	@bitmap_bh: the block group block bitmap
1154 		 * Maybe we could shift the start block of the reservation  in alloc_new_reservation()
1155 		 * window to the first block of next group.  in alloc_new_reservation()
1180 	 * shift the search start to the window near the goal block  in alloc_new_reservation()
1206 	 * to make sure there is at least a free block inside this region.  in alloc_new_reservation()
1208 	 * searching the first free bit on the block bitmap and copy of  in alloc_new_reservation()
1210 	 * block. Search start from the start block of the reservable space  in alloc_new_reservation()
1220 		 * no free block left on the bitmap, no point  in alloc_new_reservation()
1232 	 * check if the first free block is within the  in alloc_new_reservation()
1243 	 * start from where the free block is,  in alloc_new_reservation()
1254  * @sb:			super block
1297  * @group:		given allocation block group
1298  * @bitmap_bh:		bufferhead holds the block bitmap
1299  * @grp_goal:		given target block within the group
1304  * This is the main function used to allocate a new block and its reservation
1307  * Each time when a new block allocation is need, first try to allocate from
1311  * reservation window for it starting from the goal first. Then do the block
1315  * again when somebody is looking for a free block (without
1341 	BUFFER_TRACE(bitmap_bh, "get undo access for new block");  in ext3_try_to_allocate_with_rsv()
1352 	 * or last attempt to allocate a block with reservation turned on failed  in ext3_try_to_allocate_with_rsv()
1360 	 * grp_goal is a group relative block number (if there is a goal)  in ext3_try_to_allocate_with_rsv()
1362 	 * first block is a filesystem wide block number  in ext3_try_to_allocate_with_rsv()
1363 	 * first block is the block number of the first block in this group  in ext3_try_to_allocate_with_rsv()
1369 	 * Basically we will allocate a new block from inode's reservation  in ext3_try_to_allocate_with_rsv()
1374 	 * b) last attempt to allocate a block from existing reservation  in ext3_try_to_allocate_with_rsv()
1423 					"bitmap block");  in ext3_try_to_allocate_with_rsv()
1439  * @sbi:		in-core super block structure.
1441  * Check if filesystem has at least 1 free block available for allocation.
1459  * @sb:			super block
1480  * ext3_new_blocks() -- core block(s) allocation function
1483  * @goal:		given target block(filesystem wide)
1487  * ext3_new_blocks uses a goal block to assist allocation.  It tries to
1488  * allocate block(s) from the block group contains the goal block first. If that
1489  * fails, it will try to allocate block(s) from other block groups without
1490  * any specific goal block.
1500 	ext3_grpblk_t grp_target_blk;	/* blockgroup relative goal block */  in ext3_new_blocks()
1501 	ext3_grpblk_t grp_alloc_blk;	/* blockgroup-relative allocated block*/  in ext3_new_blocks()
1502 	ext3_fsblk_t ret_block;		/* filesyetem-wide allocated block */  in ext3_new_blocks()
1524 	 * Check quota for allocation of this block.  in ext3_new_blocks()
1538 	 * Allocate a block from reservation only when  in ext3_new_blocks()
1555 	 * First, test whether the goal block is free.  in ext3_new_blocks()
1627 		 * try to allocate block(s) from this group, without a goal(-1).  in ext3_new_blocks()
1642 	 * just do block allocation as without reservations.  in ext3_new_blocks()
1656 	ext3_debug("using block group %d(%d)\n",  in ext3_new_blocks()
1673 			    "Allocating block in system zone - "  in ext3_new_blocks()
1689 		/* Record bitmap buffer state in the newly allocated block */  in ext3_new_blocks()
1705 				printk("%s: block was unexpectedly set in "  in ext3_new_blocks()
1717 			    "block("E3FSBLK") >= blocks count(%d) - "  in ext3_new_blocks()
1728 	ext3_debug("allocating block %lu. Goal hits %d of %d.\n",  in ext3_new_blocks()
1762 	 * Undo the block allocation  in ext3_new_blocks()
1782  * Adds up the number of free blocks from each block group.
1914  * @sb:			super block for file system
1916  * @start:		first group block to examine
1917  * @max:		last group block to examine
1919  * @minblocks:		minimum extent block count
1921  * ext3_trim_all_free walks through group's block bitmap searching for free
1922  * blocks. When the free block is found, it tries to allocate this block and
1923  * consequent free block to get the biggest free extent possible, until it
1924  * reaches any used block. Then issue a TRIM command on this extent and free
1925  * the extent in the block bitmap. This is done until whole group is scanned.
1941 	 * We will update one block bitmap, and one group descriptor  in ext3_trim_all_free()
1981 		 * block bitmap  in ext3_trim_all_free()
2023 					"bit already cleared for block "E3FSBLK,  in ext3_trim_all_free()
2057 	/* We dirtied the bitmap block */  in ext3_trim_all_free()
2058 	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");  in ext3_trim_all_free()
2063 	/* And the group descriptor block */  in ext3_trim_all_free()
2064 	BUFFER_TRACE(gdp_bh, "dirtied group descriptor block");  in ext3_trim_all_free()
2140 		 * For all the groups except the last one, last block will  in ext3_trim_fs()