[patch 40/40] reiserfs: reorganize do_balan.c comments

[jeffm@suse.com]

[-- Attachment #1: reiserfs-balance_leaf_comment.diff --]
[-- Type: text/plain, Size: 13687 bytes --]

 This patch just shuffles some comments around to make them more useful,
 as well as formatted in a more readable manner.

Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
 fs/reiserfs/do_balan.c |  233 ++++++++++++++++++++++---------------------------
 1 file changed, 108 insertions(+), 125 deletions(-)

--- a/fs/reiserfs/do_balan.c	2007-05-30 17:54:46.000000000 -0400
+++ b/fs/reiserfs/do_balan.c	2007-05-30 17:54:47.000000000 -0400
@@ -1,20 +1,47 @@
 /*
  * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
+ *
+ * Big rule: Nothing performed during balance_leaf() may schedule. This
+ * is to ensure that the tree will be stable during the entire balancing
+ * run. This is clearly suboptimal for multithreaded use, but making
+ * the tree locking more scalable is a huge project that nobody has
+ * decided to take on yet.
+ *
+ * Summary:
+ *  if deleting/cutting something ( tb->insert_size[0] < 0 )
+ *    return(bl_when_delete());
+ *  else
+ *    if lnum is larger than 0 we put items into the left node
+ *    if rnum is larger than 0 we put items into the right node
+ *    if tb->snum[0] is larger than 0 we put items into the new node s1
+ *    if tb->snum[1] is larger than 0 we put items into the new node s2
+ * Note that all *num* count new items being created.
+ *
+ * Some interesting rules of balancing:
+ *
+ * we delete a maximum of two nodes per level per balancing: we never
+ * delete R, when we delete two of three nodes L, S, R then we move
+ * them into R.
+ *
+ * we only delete L if we are deleting two nodes, if we delete only
+ * one node we delete S
+ *
+ * if we shift leaves then we shift as much as we can: this is a
+ * deliberate policy of extremism in node packing which results in
+ * higher average utilization after repeated random balance operations
+ * at the cost of more memory copies and more balancing as a result of
+ * small insertions to full nodes.
+ *
+ * if we shift internal nodes we try to evenly balance the node
+ * utilization, with consequent less balancing at the cost of lower
+ * utilization.
+ *
+ * one could argue that the policy for directories in leaves should be
+ * that of internal nodes, but we will wait until another day to
+ * evaluate this....  It would be nice to someday measure and prove
+ * these assumptions as to what is optimal....
  */
 
-/* Now we have all buffers that must be used in balancing of the tree 	*/
-/* Further calculations can not cause schedule(), and thus the buffer 	*/
-/* tree will be stable until the balancing will be finished 		*/
-/* balance the tree according to the analysis made before,		*/
-/* and using buffers obtained after all above.				*/
-
-/**
- ** bl_when_delete
- ** balance_leaf
- ** do_balance
- **
- **/
-
 #include <asm/uaccess.h>
 #include <linux/time.h>
 #include <linux/reiserfs_fs.h>
@@ -76,29 +103,6 @@ inline void do_balance_mark_leaf_dirty(s
 #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
 #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
 
-/* summary:
- if deleting something ( tb->insert_size[0] < 0 )
-   return(bl_when_delete()); (flag d handled here)
- else
-   if lnum is larger than 0 we put items into the left node
-   if rnum is larger than 0 we put items into the right node
-   if tb->snum[0] is larger than 0 we put items into the new node s1
-   if tb->snum[1] is larger than 0 we put items into the new node s2
-Note that all *num* count new items being created.
-
-It would be easier to read balance_leaf() if each of these summary
-lines was a separate procedure rather than being inlined.  I think
-that there are many passages here and in bl_when_delete() in
-which two calls to one procedure can replace two passages, and it
-might save cache space and improve software maintenance costs to do so.
-
-Vladimir made the perceptive comment that we should offload most of
-the decision making in this function into fix_nodes/check_balance, and
-then create some sort of structure in tb that says what actions should
-be performed by do_balance.
-
--Hans */
-
 /* L[0] must be joined with S[0] */
 static int bl_delete_merge_left(struct tree_balance *tb)
 {
@@ -1352,20 +1356,30 @@ bl_current_node(struct tree_ba
 }
 
 
-static int balance_leaf(struct tree_balance *tb, struct item_head *ih,	/* item header of inserted item (this is on little endian) */
-			const char *body,	/* body  of inserted item or bytes to paste */
-			int flag,	/* i - insert, d - delete, c - cut, p - paste
-					   (see comment to do_balance) */
-			struct item_head *insert_key,	/* in our processing of one level we sometimes determine what
-							   must be inserted into the next higher level.  This insertion
-							   consists of a key or two keys and their corresponding
-							   pointers */
-			struct buffer_head **insert_ptr	/* inserted node-ptrs for the next level */
-    )
+/*
+ * balance_leaf(): The core driver for balancing the leaf level of reiserfs
+ *                 s-trees. This function completes successfully or panics.
+ *                 Upon successful completion, the leaf level is balanced.
+ *
+ * @tb:         tree balance struct containing state of this balance
+ * @ih:         item header of inserted item (this is on little endian)
+ * @body:       body of inserted item or bytes to paste
+ * @flag:	One of M_INSERT, M_PASTE, M_DELETE, or M_CUT
+ * @insert_key:	In our processing of one level we sometimes determine what
+ *              must be inserted into the next higher level.  This insertion
+ *              consists of a key or two keys and their corresponding
+ *              pointers
+ * @insert_ptr:	inserted node-ptrs for the next level
+ */
+static int balance_leaf(struct tree_balance *tb, struct item_head *ih,
+                        const char *body, int flag,
+                        struct item_head *insert_key,
+                        struct buffer_head **insert_ptr)
 {
 	struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
-	int item_pos = PATH_LAST_POSITION(tb->tb_path);	/*  index into the array of item headers in S[0]
-							   of the affected item */
+	/* index into the array of item headers in S[0]
+         * of the affected item */
+	int item_pos = PATH_LAST_POSITION(tb->tb_path);
 	int pos_in_item;
 	int zeros_num;
 
@@ -1435,7 +1449,7 @@ static int balance_leaf(struct tree_bala
 		          pos_in_item);
 
 	return 0;
-}				/* Leaf level of the tree is balanced (end of balance_leaf) */
+}	/* Leaf level of the tree is balanced (end of balance_leaf) */
 
 /* Make empty node */
 void make_empty_node(struct buffer_info *bi)
@@ -1449,7 +1463,7 @@ void make_empty_node(struct buffer_info 
 	set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
 
 	if (bi->bi_parent)
-		B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0;	/* Endian safe if 0 */
+		B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0;
 }
 
 /* Get first empty buffer */
@@ -1490,7 +1504,8 @@ static void store_thrown(struct tree_bal
 			get_bh(bh);	/* free_thrown puts this */
 			return;
 		}
-	reiserfs_warning(tb->tb_sb, "reiserfs-12321", "too many thrown buffers");
+	reiserfs_warning(tb->tb_sb, "reiserfs-12321",
+	                 "too many thrown buffers");
 }
 
 static void free_thrown(struct tree_balance *tb)
@@ -1504,7 +1519,8 @@ static void free_thrown(struct tree_bala
 				reiserfs_warning(tb->tb_sb, "reiserfs-12322",
 				                 "called with dirty buffer %d",
 				                 blocknr);
-			brelse(tb->thrown[i]);	/* incremented in store_thrown */
+			/* incremented in store_thrown */
+			brelse(tb->thrown[i]);
 			reiserfs_free_block(tb->transaction_handle, NULL,
 					    blocknr, 0);
 		}
@@ -1530,9 +1546,8 @@ void replace_key(struct tree_balance *tb
 	RFALSE(dest == NULL || src == NULL,
 	       "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
 	       src, dest);
-	RFALSE(!B_IS_KEYS_LEVEL(dest),
-	       "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
-	       dest);
+	RFALSE(!B_IS_KEYS_LEVEL(dest), "vs-12310: invalid level (%z) "
+	       "for destination buffer. dest must be leaf", dest);
 	RFALSE(n_dest < 0 || n_src < 0,
 	       "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
 	RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
@@ -1723,39 +1738,6 @@ static void check_internal_levels(struct
 
 #endif
 
-/* Now we have all of the buffers that must be used in balancing of
-   the tree.  We rely on the assumption that schedule() will not occur
-   while do_balance works. ( Only interrupt handlers are acceptable.)
-   We balance the tree according to the analysis made before this,
-   using buffers already obtained.  For SMP support it will someday be
-   necessary to add ordered locking of tb. */
-
-/* Some interesting rules of balancing:
-
-   we delete a maximum of two nodes per level per balancing: we never
-   delete R, when we delete two of three nodes L, S, R then we move
-   them into R.
-
-   we only delete L if we are deleting two nodes, if we delete only
-   one node we delete S
-
-   if we shift leaves then we shift as much as we can: this is a
-   deliberate policy of extremism in node packing which results in
-   higher average utilization after repeated random balance operations
-   at the cost of more memory copies and more balancing as a result of
-   small insertions to full nodes.
-
-   if we shift internal nodes we try to evenly balance the node
-   utilization, with consequent less balancing at the cost of lower
-   utilization.
-
-   one could argue that the policy for directories in leaves should be
-   that of internal nodes, but we will wait until another day to
-   evaluate this....  It would be nice to someday measure and prove
-   these assumptions as to what is optimal....
-
-*/
-
 static inline void do_balance_starts(struct tree_balance *tb)
 {
 	/* use print_cur_tb() to see initial state of struct
@@ -1794,43 +1776,45 @@ static inline void do_balance_completed(
 	free_thrown(tb);
 }
 
-void do_balance(struct tree_balance *tb,	/* tree_balance structure */
-		struct item_head *ih,	/* item header of inserted item */
-		const char *body,	/* body  of inserted item or bytes to paste */
-		int flag)
-{				/* i - insert, d - delete
-				   c - cut, p - paste
-
-				   Cut means delete part of an item
-				   (includes removing an entry from a
-				   directory).
-
-				   Delete means delete whole item.
-
-				   Insert means add a new item into the
-				   tree.
-
-				   Paste means to append to the end of an
-				   existing file or to insert a directory
-				   entry.  */
-	int child_pos,		/* position of a child node in its parent */
-	 h;			/* level of the tree being processed */
-	struct item_head insert_key[2];	/* in our processing of one level
-					   we sometimes determine what
-					   must be inserted into the next
-					   higher level.  This insertion
-					   consists of a key or two keys
-					   and their corresponding
-					   pointers */
-	struct buffer_head *insert_ptr[2];	/* inserted node-ptrs for the next
-						   level */
+/*
+ * do_balance(): The driver function for tree balancing. We balance the leaf
+ *               level first, and then update the internal tree to match.
+ *
+ * @tb: struct tree_balance containing state of balancing
+ * @ih: item header of inserted item
+ * @body: body of inserted item or bytes to paste
+ * @flag: One of M_INSERT, M_PASTE, M_DELETE, or M_CUT:
+ *        M_INSERT: Add a new item to the tree
+ *        M_PASTE:  Extend an existing item, e.g. appending a file or
+ *                  adding a new directory entry
+ *        M_DELETE: Delete the entire item
+ *        M_CUT:    Delete part of an item, e.g. removing a directory entry
+ */
+void do_balance(struct tree_balance *tb, struct item_head *ih,
+                const char *body, int flag)
+{
+	/* position of a child node in its parent */
+	int child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
+
+	/* level of the tree being processed */
+	int h;
+
+	/* in our processing of one level we sometimes determine what
+         * must be inserted into the next higher level.  This insertion
+         * consists of a key or two keys and their corresponding pointers */
+	struct item_head insert_key[2];
+
+	/* Buffers added to the leaf level that must be tracked for
+	 * balancing the internal levels. */
+	struct buffer_head *insert_ptr[2];
 
 	tb->tb_mode = flag;
 	tb->need_balance_dirty = 0;
 
-	if (FILESYSTEM_CHANGED_TB(tb)) {
-		reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has changed");
-	}
+	if (FILESYSTEM_CHANGED_TB(tb))
+		reiserfs_panic(tb->tb_sb, "clm-6000",
+		               "fs generation has changed");
+
 	/* if we have no real work to do  */
 	if (!tb->insert_size[0]) {
 		reiserfs_warning(tb->tb_sb, "PAP-12350",
@@ -1845,8 +1829,7 @@ void do_balance(struct tree_balance *tb,
 	/* balance leaf returns 0 except if combining L R and S into
 	   one node.  see balance_internal() for explanation of this
 	   line of code. */
-	child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
-	    balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
+	child_pos += balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
 
 #ifdef CONFIG_REISERFS_CHECK
 	check_after_balance_leaf(tb);
@@ -1854,8 +1837,8 @@ void do_balance(struct tree_balance *tb,
 
 	/* Balance internal level of the tree. */
 	for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
-		child_pos =
-		    balance_internal(tb, h, child_pos, insert_key, insert_ptr);
+		child_pos = balance_internal(tb, h, child_pos,
+		                             insert_key, insert_ptr);
 
 	do_balance_completed(tb);
 

-- 
Jeff Mahoney
SUSE Labs