ext2 reservations

Val's cross-port of the ext3 reservations code into ext2.

[mbligh@mbligh.org: Small type error for printk
[akpm@linux-foundation.org: fix types, sync with ext3]
[mbligh@mbligh.org: Bring ext2 reservations code in line with latest ext3]
[akpm@linux-foundation.org: kill noisy printk]
[akpm@linux-foundation.org: remember to dirty the gdp's block]
[akpm@linux-foundation.org: cross-port the missed 5dea5176e5c32ef9f0d1a41d28427b3bf6881b3a]
[akpm@linux-foundation.org: cross-port e6022603b9aa7d61d20b392e69edcdbbc1789969]
[akpm@linux-foundation.org: Port the omitted 08fb306fe63d98eb86e3b16f4cc21816fa47f18e]
[akpm@linux-foundation.org: Backport the missed 20acaa18d0c002fec180956f87adeb3f11f635a6]
[akpm@linux-foundation.org: fixes]
[cmm@us.ibm.com: fix reservation extension]
[bunk@stusta.de: make ext2_get_blocks() static]
[hugh@veritas.com: fix hang]
[hugh@veritas.com: ext2_new_blocks should reset the reservation window size]
[hugh@veritas.com: ext2 balloc: fix off-by-one against rsv_end]
[hugh@veritas.com: grp_goal 0 is a genuine goal (unlike -1), so ext2_try_to_allocate_with_rsv should treat it as such]
[hugh@veritas.com: rbtree usage cleanup]
[pbadari@us.ibm.com: Fix for ext2 reservation]
[bunk@kernel.org: remove fs/ext2/balloc.c:reserve_blocks()]
[hugh@veritas.com: ext2 balloc: use io_error label]
Cc: "Martin J. Bligh" <mbligh@mbligh.org>
Cc: Valerie Henson <val_henson@linux.intel.com>
Cc: Mingming Cao <cmm@us.ibm.com>
Cc: Mel Gorman <mel@csn.ul.ie>
Cc: Hugh Dickins <hugh@veritas.com>
Signed-off-by: Adrian Bunk <bunk@stusta.de>
Signed-off-by: Hugh Dickins <hugh@veritas.com>
Signed-off-by: Badari Pulavarty <pbadari@us.ibm.com>
Signed-off-by: Adrian Bunk <bunk@kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

10 files changed, 1554 insertions, 485 deletions

diff --git a/fs/ext2/balloc.c b/fs/ext2/balloc.c
index ffaa6d845442..18a42de25b55 100644
--- a/fs/ext2/balloc.c
+++ b/fs/ext2/balloc.c
@@ -133,41 +133,6 @@ error_out:
         return NULL;
 }
 
-/*
- * Set sb->s_dirt here because the superblock was "logically" altered.  We
- * need to recalculate its free blocks count and flush it out.
- */
-static int reserve_blocks(struct super_block *sb, int count)
-{
-        struct ext2_sb_info *sbi = EXT2_SB(sb);
-        struct ext2_super_block *es = sbi->s_es;
-        unsigned free_blocks;
-        unsigned root_blocks;
-
-        free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
-        root_blocks = le32_to_cpu(es->s_r_blocks_count);
-
-        if (free_blocks < count)
-                count = free_blocks;
-
-        if (free_blocks < root_blocks + count && !capable(CAP_SYS_RESOURCE) &&
-            sbi->s_resuid != current->fsuid &&
-            (sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
-                /*
-                 * We are too close to reserve and we are not privileged.
-                 * Can we allocate anything at all?
-                 */
-                if (free_blocks > root_blocks)
-                        count = free_blocks - root_blocks;
-                else
-                        return 0;
-        }
-
-        percpu_counter_sub(&sbi->s_freeblocks_counter, count);
-        sb->s_dirt = 1;
-        return count;
-}
-
 static void release_blocks(struct super_block *sb, int count)
 {
         if (count) {
@@ -178,25 +143,7 @@ static void release_blocks(struct super_block *sb, int count)
         }
 }
 
-static int group_reserve_blocks(struct ext2_sb_info *sbi, int group_no,
-        struct ext2_group_desc *desc, struct buffer_head *bh, int count)
-{
-        unsigned free_blocks;
-
-        if (!desc->bg_free_blocks_count)
-                return 0;
-
-        spin_lock(sb_bgl_lock(sbi, group_no));
-        free_blocks = le16_to_cpu(desc->bg_free_blocks_count);
-        if (free_blocks < count)
-                count = free_blocks;
-        desc->bg_free_blocks_count = cpu_to_le16(free_blocks - count);
-        spin_unlock(sb_bgl_lock(sbi, group_no));
-        mark_buffer_dirty(bh);
-        return count;
-}
-
-static void group_release_blocks(struct super_block *sb, int group_no,
+static void group_adjust_blocks(struct super_block *sb, int group_no,
         struct ext2_group_desc *desc, struct buffer_head *bh, int count)
 {
         if (count) {
@@ -212,7 +159,306 @@ static void group_release_blocks(struct super_block *sb, int group_no,
         }
 }
 
-/* Free given blocks, update quota and i_blocks field */
+/*
+ * The reservation window structure operations
+ * --------------------------------------------
+ * Operations include:
+ * dump, find, add, remove, is_empty, find_next_reservable_window, etc.
+ *
+ * We use a red-black tree to represent per-filesystem reservation
+ * windows.
+ *
+ */
+
+/**
+ * __rsv_window_dump() -- Dump the filesystem block allocation reservation map
+ * @rb_root:            root of per-filesystem reservation rb tree
+ * @verbose:            verbose mode
+ * @fn:                 function which wishes to dump the reservation map
+ *
+ * If verbose is turned on, it will print the whole block reservation
+ * windows(start, end). Otherwise, it will only print out the "bad" windows,
+ * those windows that overlap with their immediate neighbors.
+ */
+#if 1
+static void __rsv_window_dump(struct rb_root *root, int verbose,
+                              const char *fn)
+{
+        struct rb_node *n;
+        struct ext2_reserve_window_node *rsv, *prev;
+        int bad;
+
+restart:
+        n = rb_first(root);
+        bad = 0;
+        prev = NULL;
+
+        printk("Block Allocation Reservation Windows Map (%s):\n", fn);
+        while (n) {
+                rsv = rb_entry(n, struct ext2_reserve_window_node, rsv_node);
+                if (verbose)
+                        printk("reservation window 0x%p "
+                                "start: %lu, end: %lu\n",
+                                rsv, rsv->rsv_start, rsv->rsv_end);
+                if (rsv->rsv_start && rsv->rsv_start >= rsv->rsv_end) {
+                        printk("Bad reservation %p (start >= end)\n",
+                               rsv);
+                        bad = 1;
+                }
+                if (prev && prev->rsv_end >= rsv->rsv_start) {
+                        printk("Bad reservation %p (prev->end >= start)\n",
+                               rsv);
+                        bad = 1;
+                }
+                if (bad) {
+                        if (!verbose) {
+                                printk("Restarting reservation walk in verbose mode\n");
+                                verbose = 1;
+                                goto restart;
+                        }
+                }
+                n = rb_next(n);
+                prev = rsv;
+        }
+        printk("Window map complete.\n");
+        if (bad)
+                BUG();
+}
+#define rsv_window_dump(root, verbose) \
+        __rsv_window_dump((root), (verbose), __FUNCTION__)
+#else
+#define rsv_window_dump(root, verbose) do {} while (0)
+#endif
+
+/**
+ * goal_in_my_reservation()
+ * @rsv:                inode's reservation window
+ * @grp_goal:           given goal block relative to the allocation block group
+ * @group:              the current allocation block group
+ * @sb:                 filesystem super block
+ *
+ * Test if the given goal block (group relative) is within the file's
+ * own block reservation window range.
+ *
+ * If the reservation window is outside the goal allocation group, return 0;
+ * grp_goal (given goal block) could be -1, which means no specific
+ * goal block. In this case, always return 1.
+ * If the goal block is within the reservation window, return 1;
+ * otherwise, return 0;
+ */
+static int
+goal_in_my_reservation(struct ext2_reserve_window *rsv, ext2_grpblk_t grp_goal,
+                        unsigned int group, struct super_block * sb)
+{
+        ext2_fsblk_t group_first_block, group_last_block;
+
+        group_first_block = ext2_group_first_block_no(sb, group);
+        group_last_block = group_first_block + EXT2_BLOCKS_PER_GROUP(sb) - 1;
+
+        if ((rsv->_rsv_start > group_last_block) ||
+            (rsv->_rsv_end < group_first_block))
+                return 0;
+        if ((grp_goal >= 0) && ((grp_goal + group_first_block < rsv->_rsv_start)