9  *  Enhanced block allocation by Stephen Tweedie (sct@redhat.com), 1993
27  * blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
28  * block for inodes, N blocks for the inode table and data blocks.
31  * super block.  Each descriptor contains the number of the bitmap block and
32  * the free blocks count in the block.  The descriptors are loaded in memory
85 	/* check whether block bitmap block number is set */  in ext2_valid_block_bitmap()
89 		/* bad block bitmap */  in ext2_valid_block_bitmap()
92 	/* check whether the inode bitmap block number is set */  in ext2_valid_block_bitmap()
96 		/* bad block bitmap */  in ext2_valid_block_bitmap()
99 	/* check whether the inode table block number is set */  in ext2_valid_block_bitmap()
111 			"Invalid block bitmap - "  in ext2_valid_block_bitmap()
112 			"block_group = %d, block = %lu",  in ext2_valid_block_bitmap()
119  * bits for block/inode/inode tables are set in the bitmaps
137 			    "Cannot read block bitmap - "  in read_block_bitmap()
148 			    "Cannot read block bitmap - "  in read_block_bitmap()
200  * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
205  * If verbose is turned on, it will print the whole block reservation
222 	printk("Block Allocation Reservation Windows Map (%s):\n", fn);  in __rsv_window_dump()
261  * @grp_goal:		given goal block relative to the allocation block group
262  * @group:		the current allocation block group
263  * @sb:			filesystem super block
265  * Test if the given goal block (group relative) is within the file's
266  * own block reservation window range.
269  * grp_goal (given goal block) could be -1, which means no specific
270  * goal block. In this case, always return 1.
271  * If the goal block is within the reservation window, return 1;
295  * @goal:		target allocation block
334  * ext2_rsv_window_add() -- Insert a window to the block reservation rb tree.
335  * @sb:			super block
372  * @sb:			super block
375  * Mark the block reservation window as not allocated, and unlink it
392  * returns 1 if the end block is EXT2_RESERVE_WINDOW_NOT_ALLOCATED.
396 	/* a valid reservation end block could not be 0 */  in rsv_is_empty()
409  * needs a new block. So, before every ext2_new_block(s) call, for
412  * Fail to do so will result in block reservation being turned off for that
417  * is open for write (needs block allocation).
437 		 * block reservation is off  in ext2_init_block_alloc_info()
454  * Discard(free) block reservation window on last file close, or truncate
460  * 	ext2_truncate(): when the block indirect map is about to change.
484  * @block:		start physcial block to free
487 void ext2_free_blocks (struct inode * inode, unsigned long block,  in ext2_free_blocks()  argument
502 	if (block < le32_to_cpu(es->s_first_data_block) ||  in ext2_free_blocks()
503 	    block + count < block ||  in ext2_free_blocks()
504 	    block + count > le32_to_cpu(es->s_blocks_count)) {  in ext2_free_blocks()
507 			    "block = %lu, count = %lu", block, count);  in ext2_free_blocks()
511 	ext2_debug ("freeing block(s) %lu-%lu\n", block, block + count - 1);  in ext2_free_blocks()
515 	block_group = (block - le32_to_cpu(es->s_first_data_block)) /  in ext2_free_blocks()
517 	bit = (block - le32_to_cpu(es->s_first_data_block)) %  in ext2_free_blocks()
536 	if (in_range (le32_to_cpu(desc->bg_block_bitmap), block, count) ||  in ext2_free_blocks()
537 	    in_range (le32_to_cpu(desc->bg_inode_bitmap), block, count) ||  in ext2_free_blocks()
538 	    in_range (block, le32_to_cpu(desc->bg_inode_table),  in ext2_free_blocks()
540 	    in_range (block + count - 1, le32_to_cpu(desc->bg_inode_table),  in ext2_free_blocks()
544 			    "Block = %lu, count = %lu",  in ext2_free_blocks()
545 			    block, count);  in ext2_free_blocks()
553 				"bit already cleared for block %lu", block + i);  in ext2_free_blocks()
567 		block += count;  in ext2_free_blocks()
579  * @start:		the starting block (group relative) of the search
580  * @bh:			bufferhead contains the block group bitmap
581  * @maxblocks:		the ending block (group relative) of the reservation
600  * @start:		the starting block (group relative) to find next
601  * 			allocatable block in bitmap.
602  * @bh:			bufferhead contains the block group bitmap
603  * @maxblocks:		the ending block (group relative) for the search
605  * Find an allocatable block in a bitmap.  We perform the "most
606  * appropriate allocation" algorithm of looking for a free block near
619 		 * block within the next XX blocks.  in find_next_usable_block()
652  * @group:		given allocation block group
653  * @bitmap_bh:		bufferhead holds the block bitmap
654  * @grp_goal:		given target block within the group
663  * 	if there is a reservation window, only try to allocate block(s)
665  * 	Otherwise, the allocation range starts from the give goal block,
666  * 	ends at the block group's last block.
668  * If we failed to allocate the desired block then we may end up crossing to a
727 		 * The block was allocated by another thread, or it was  in ext2_try_to_allocate()
767  * 	@group_first_block: the first block we consider to start
771  *		the maximum block number that our goal reservable space
772  *		could start from. This is normally the last block in this
878  *		there, we check the bitmap for the first free block after
879  *		it. If there is no free block until the end of group, then the
881  *		block is inside the expected reservable space, if so, we
883  *		If the first free block is outside the reservable space, then
884  *		start from the first free block, we search for next available
888  *	It contains at least one free block, and it does not overlap with other
898  *		no goal(goal = -1), we start from the first block
901  *	@sb: the super block
903  *	@bitmap_bh: the block group block bitmap
939 		 * Maybe we could shift the start block of the reservation  in alloc_new_reservation()
940 		 * window to the first block of next group.  in alloc_new_reservation()
965 	 * shift the search start to the window near the goal block  in alloc_new_reservation()
991 	 * to make sure there is at least a free block inside this region.  in alloc_new_reservation()
993 	 * Search the first free bit on the block bitmap.  Search starts from  in alloc_new_reservation()
994 	 * the start block of the reservable space we just found.  in alloc_new_reservation()
1003 		 * no free block left on the bitmap, no point  in alloc_new_reservation()
1015 	 * check if the first free block is within the  in alloc_new_reservation()
1023 	 * start from where the free block is,  in alloc_new_reservation()
1034  * @sb:			super block
1076  * @group:		given allocation block group
1077  * @bitmap_bh:		bufferhead holds the block bitmap
1078  * @grp_goal:		given target block within the group
1082  * This is the main function used to allocate a new block and its reservation
1085  * Each time when a new block allocation is need, first try to allocate from
1089  * reservation window for it starting from the goal first. Then do the block
1093  * again when somebody is looking for a free block (without
1113 	 * or last attempt to allocate a block with reservation turned on failed  in ext2_try_to_allocate_with_rsv()
1120 	 * grp_goal is a group relative block number (if there is a goal)  in ext2_try_to_allocate_with_rsv()
1122 	 * first block is a filesystem wide block number  in ext2_try_to_allocate_with_rsv()
1123 	 * first block is the block number of the first block in this group  in ext2_try_to_allocate_with_rsv()
1129 	 * Basically we will allocate a new block from inode's reservation  in ext2_try_to_allocate_with_rsv()
1134 	 * b) last attempt to allocate a block from existing reservation  in ext2_try_to_allocate_with_rsv()
1185  * @sbi:		in-core super block structure.
1187  * Check if filesystem has at least 1 free block available for allocation.
1204  * ext2_new_blocks() -- core block(s) allocation function
1206  * @goal:		given target block(filesystem wide)
1210  * ext2_new_blocks uses a goal block to assist allocation.  If the goal is
1211  * free, or there is a free block within 32 blocks of the goal, that block
1212  * is allocated.  Otherwise a forward search is made for a free block; within 
1213  * each block group the search first looks for an entire free byte in the block
1224 	ext2_grpblk_t grp_target_blk;	/* blockgroup relative goal block */  in ext2_new_blocks()
1225 	ext2_grpblk_t grp_alloc_blk;	/* blockgroup-relative allocated block*/  in ext2_new_blocks()
1226 	ext2_fsblk_t ret_block;		/* filesyetem-wide allocated block */  in ext2_new_blocks()
1249 	 * Check quota for allocation of this block.  in ext2_new_blocks()
1261 	 * Allocate a block from reservation only when  in ext2_new_blocks()
1281 	 * First, test whether the goal block is free.  in ext2_new_blocks()
1352 		 * try to allocate block(s) from this group, without a goal(-1).  in ext2_new_blocks()
1364 	 * just do block allocation as without reservations.  in ext2_new_blocks()
1378 	ext2_debug("using block group %d(%d)\n",  in ext2_new_blocks()
1390 			    "Allocating block in system zone - "  in ext2_new_blocks()
1405 			    "block("E2FSBLK") >= blocks count(%d) - "  in ext2_new_blocks()
1429 	 * Undo the block allocation  in ext2_new_blocks()