+ size = atomic_read(&my_rsv->rsv_goal_size);
+ if (!rsv_is_empty(&my_rsv->rsv_window)) {
+ /*
+ * if the old reservation is cross group boundary
+ * and if the goal is inside the old reservation window,
+ * we will come here when we just failed to allocate from
+ * the first part of the window. We still have another part
+ * that belongs to the next group. In this case, there is no
+ * point to discard our window and try to allocate a new one
+ * in this group(which will fail). we should
+ * keep the reservation window, just simply move on.
+ *
+ * Maybe we could shift the start block of the reservation
+ * window to the first block of next group.
+ */
+
+ if ((my_rsv->rsv_start <= group_end_block) &&
+ (my_rsv->rsv_end > group_end_block) &&
+ (start_block >= my_rsv->rsv_start))
+ return -1;
+
+ if ((atomic_read(&my_rsv->rsv_alloc_hit) >
+ (my_rsv->rsv_end - my_rsv->rsv_start + 1) / 2)) {
+ /*
+ * if we previously allocation hit ration is greater than half
+ * we double the size of reservation window next time
+ * otherwise keep the same
+ */
+ size = size * 2;
+ if (size > EXT3_MAX_RESERVE_BLOCKS)
+ size = EXT3_MAX_RESERVE_BLOCKS;
+ atomic_set(&my_rsv->rsv_goal_size, size);
+ }
+ }
+ /*
+ * shift the search start to the window near the goal block
+ */
+ search_head = search_reserve_window(fs_rsv_root, start_block);
+
+ /*
+ * find_next_reservable_window() simply finds a reservable window
+ * inside the given range(start_block, group_end_block).
+ *
+ * To make sure the reservation window has a free bit inside it, we
+ * need to check the bitmap after we found a reservable window.
+ */
+retry:
+ prev_rsv = find_next_reservable_window(search_head, size,
+ &start_block, group_end_block);
+ if (prev_rsv == NULL)
+ goto failed;
+ reservable_space_start = start_block;
+ /*
+ * On success, find_next_reservable_window() returns the
+ * reservation window where there is a reservable space after it.
+ * Before we reserve this reservable space, we need
+ * to make sure there is at least a free block inside this region.
+ *
+ * searching the first free bit on the block bitmap and copy of
+ * last committed bitmap alternatively, until we found a allocatable
+ * block. Search start from the start block of the reservable space
+ * we just found.
+ */
+ first_free_block = bitmap_search_next_usable_block(
+ reservable_space_start - group_first_block,
+ bitmap_bh, group_end_block - group_first_block + 1);
+
+ if (first_free_block < 0) {
+ /*
+ * no free block left on the bitmap, no point
+ * to reserve the space. return failed.
+ */
+ goto failed;
+ }
+ start_block = first_free_block + group_first_block;
+ /*
+ * check if the first free block is within the
+ * free space we just found
+ */
+ if ((start_block >= reservable_space_start) &&
+ (start_block < reservable_space_start + size))
+ goto found_rsv_window;
+ /*
+ * if the first free bit we found is out of the reservable space
+ * this means there is no free block on the reservable space
+ * we should continue search for next reservable space,
+ * start from where the free block is,
+ * we also shift the list head to where we stopped last time
+ */
+ search_head = prev_rsv;
+ goto retry;
+
+found_rsv_window:
+ /*
+ * great! the reservable space contains some free blocks.
+ * if the search returns that we should add the new
+ * window just next to where the old window, we don't
+ * need to remove the old window first then add it to the
+ * same place, just update the new start and new end.
+ */
+ if (my_rsv != prev_rsv) {
+ if (!rsv_is_empty(&my_rsv->rsv_window))
+ rsv_window_remove(sb, my_rsv);
+ }
+ my_rsv->rsv_start = reservable_space_start;
+ my_rsv->rsv_end = my_rsv->rsv_start + size - 1;
+ atomic_set(&my_rsv->rsv_alloc_hit, 0);
+ if (my_rsv != prev_rsv) {
+ ext3_rsv_window_add(sb, my_rsv);
+ }
+ return 0; /* succeed */
+failed:
+ /*
+ * failed to find a new reservation window in the current
+ * group, remove the current(stale) reservation window
+ * if there is any
+ */
+ if (!rsv_is_empty(&my_rsv->rsv_window))
+ rsv_window_remove(sb, my_rsv);
+ return -1; /* failed */
+}
+
+/*
+ * This is the main function used to allocate a new block and its reservation
+ * window.
+ *
+ * Each time when a new block allocation is need, first try to allocate from
+ * its own reservation. If it does not have a reservation window, instead of
+ * looking for a free bit on bitmap first, then look up the reservation list to
+ * see if it is inside somebody else's reservation window, we try to allocate a
+ * reservation window for it starting from the goal first. Then do the block
+ * allocation within the reservation window.
+ *
+ * This will avoid keeping on searching the reservation list again and
+ * again when someboday is looking for a free block (without
+ * reservation), and there are lots of free blocks, but they are all
+ * being reserved.
+ *
+ * We use a sorted double linked list for the per-filesystem reservation list.
+ * The insert, remove and find a free space(non-reserved) operations for the
+ * sorted double linked list should be fast.
+ *
+ */
+static int
+ext3_try_to_allocate_with_rsv(struct super_block *sb, handle_t *handle,
+ unsigned int group, struct buffer_head *bitmap_bh,
+ int goal, struct ext3_reserve_window_node * my_rsv,
+ int *errp)
+{
+ spinlock_t *rsv_lock;
+ unsigned long group_first_block;
+ int ret = 0;
+ int fatal;
+ int credits = 0;
+
+ *errp = 0;
+
+ /*
+ * Make sure we use undo access for the bitmap, because it is critical
+ * that we do the frozen_data COW on bitmap buffers in all cases even
+ * if the buffer is in BJ_Forget state in the committing transaction.
+ */
+ BUFFER_TRACE(bitmap_bh, "get undo access for new block");
+ fatal = ext3_journal_get_undo_access(handle, bitmap_bh, &credits);