do_balan.c | Explore in Territory

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 */

/*
 * 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.
 */

#include <linux/uaccess.h>
#include <linux/time.h>
#include "reiserfs.h"
#include <linux/buffer_head.h>
#include <linux/kernel.h>

static inline void buffer_info_init_left(struct tree_balance *tb,
                                         struct buffer_info *bi)
{ … }

static inline void buffer_info_init_right(struct tree_balance *tb,
                                          struct buffer_info *bi)
{ … }

static inline void buffer_info_init_tbS0(struct tree_balance *tb,
                                         struct buffer_info *bi)
{ … }

static inline void buffer_info_init_bh(struct tree_balance *tb,
                                       struct buffer_info *bi,
                                       struct buffer_head *bh)
{ … }

inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
				       struct buffer_head *bh, int flag)
{ … }

#define do_balance_mark_internal_dirty …
#define do_balance_mark_sb_dirty …

/*
 * summary:
 *  if deleting something ( tb->insert_size[0] < 0 )
 *    return(balance_leaf_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 snum1 is larger than 0 we put items into the new node s1
 *    if snum2 is larger than 0 we put items into the new node s2
 * Note that all *num* count new items being created.
 */

static void balance_leaf_when_delete_del(struct tree_balance *tb)
{ … }

/* cut item in S[0] */
static void balance_leaf_when_delete_cut(struct tree_balance *tb)
{ … }

static int balance_leaf_when_delete_left(struct tree_balance *tb)
{ … }

/*
 * Balance leaf node in case of delete or cut: insert_size[0] < 0
 *
 * lnum, rnum can have values >= -1
 *	-1 means that the neighbor must be joined with S
 *	 0 means that nothing should be done with the neighbor
 *	>0 means to shift entirely or partly the specified number of items
 *         to the neighbor
 */
static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
{ … }

static unsigned int balance_leaf_insert_left(struct tree_balance *tb,
					     struct item_head *const ih,
					     const char * const body)
{ … }

static void balance_leaf_paste_left_shift_dirent(struct tree_balance *tb,
						 struct item_head * const ih,
						 const char * const body)
{ … }

static unsigned int balance_leaf_paste_left_shift(struct tree_balance *tb,
						  struct item_head * const ih,
						  const char * const body)
{ … }


/* appended item will be in L[0] in whole */
static void balance_leaf_paste_left_whole(struct tree_balance *tb,
					  struct item_head * const ih,
					  const char * const body)
{ … }

static unsigned int balance_leaf_paste_left(struct tree_balance *tb,
					    struct item_head * const ih,
					    const char * const body)
{ … }

/* Shift lnum[0] items from S[0] to the left neighbor L[0] */
static unsigned int balance_leaf_left(struct tree_balance *tb,
				      struct item_head * const ih,
				      const char * const body, int flag)
{ … }


static void balance_leaf_insert_right(struct tree_balance *tb,
				      struct item_head * const ih,
				      const char * const body)
{ … }


static void balance_leaf_paste_right_shift_dirent(struct tree_balance *tb,
				     struct item_head * const ih,
				     const char * const body)
{ … }

static void balance_leaf_paste_right_shift(struct tree_balance *tb,
				     struct item_head * const ih,
				     const char * const body)
{ … }

static void balance_leaf_paste_right_whole(struct tree_balance *tb,
				     struct item_head * const ih,
				     const char * const body)
{ … }

static void balance_leaf_paste_right(struct tree_balance *tb,
				     struct item_head * const ih,
				     const char * const body)
{ … }

/* shift rnum[0] items from S[0] to the right neighbor R[0] */
static void balance_leaf_right(struct tree_balance *tb,
			       struct item_head * const ih,
			       const char * const body, int flag)
{ … }

static void balance_leaf_new_nodes_insert(struct tree_balance *tb,
					  struct item_head * const ih,
					  const char * const body,
					  struct item_head *insert_key,
					  struct buffer_head **insert_ptr,
					  int i)
{ … }

/* we append to directory item */
static void balance_leaf_new_nodes_paste_dirent(struct tree_balance *tb,
					 struct item_head * const ih,
					 const char * const body,
					 struct item_head *insert_key,
					 struct buffer_head **insert_ptr,
					 int i)
{ … }

static void balance_leaf_new_nodes_paste_shift(struct tree_balance *tb,
					 struct item_head * const ih,
					 const char * const body,
					 struct item_head *insert_key,
					 struct buffer_head **insert_ptr,
					 int i)
{ … }

static void balance_leaf_new_nodes_paste_whole(struct tree_balance *tb,
					       struct item_head * const ih,
					       const char * const body,
					       struct item_head *insert_key,
					       struct buffer_head **insert_ptr,
					       int i)

{ … }
static void balance_leaf_new_nodes_paste(struct tree_balance *tb,
					 struct item_head * const ih,
					 const char * const body,
					 struct item_head *insert_key,
					 struct buffer_head **insert_ptr,
					 int i)
{ … }

/* Fill new nodes that appear in place of S[0] */
static void balance_leaf_new_nodes(struct tree_balance *tb,
				   struct item_head * const ih,
				   const char * const body,
				   struct item_head *insert_key,
				   struct buffer_head **insert_ptr,
				   int flag)
{ … }

static void balance_leaf_finish_node_insert(struct tree_balance *tb,
					    struct item_head * const ih,
					    const char * const body)
{ … }

static void balance_leaf_finish_node_paste_dirent(struct tree_balance *tb,
						  struct item_head * const ih,
						  const char * const body)
{ … }

static void balance_leaf_finish_node_paste(struct tree_balance *tb,
					   struct item_head * const ih,
					   const char * const body)
{ … }

/*
 * if the affected item was not wholly shifted then we
 * perform all necessary operations on that part or whole
 * of the affected item which remains in S
 */
static void balance_leaf_finish_node(struct tree_balance *tb,
				      struct item_head * const ih,
				      const char * const body, int flag)
{ … }

/**
 * balance_leaf - reiserfs tree balancing algorithm
 * @tb: tree balance state
 * @ih: item header of inserted item (little endian)
 * @body: body of inserted item or bytes to paste
 * @flag: i - insert, d - delete, c - cut, p - paste (see do_balance)
 * passed back:
 * @insert_key: key to insert new nodes
 * @insert_ptr: array of nodes to insert at the next level
 *
 * 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.
 */
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)
{ … }

/* Make empty node */
void make_empty_node(struct buffer_info *bi)
{ … }

/* Get first empty buffer */
struct buffer_head *get_FEB(struct tree_balance *tb)
{ … }

/* This is now used because reiserfs_free_block has to be able to schedule. */
static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
{ … }

static void free_thrown(struct tree_balance *tb)
{ … }

void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
{ … }

/* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
		 struct buffer_head *src, int n_src)
{ … }

int get_left_neighbor_position(struct tree_balance *tb, int h)
{ … }

int get_right_neighbor_position(struct tree_balance *tb, int h)
{ … }

#ifdef CONFIG_REISERFS_CHECK

int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
static void check_internal_node(struct super_block *s, struct buffer_head *bh,
				char *mes)
{ … }

static int locked_or_not_in_tree(struct tree_balance *tb,
				  struct buffer_head *bh, char *which)
{ … }

static int check_before_balancing(struct tree_balance *tb)
{ … }

static void check_after_balance_leaf(struct tree_balance *tb)
{ … }

static void check_leaf_level(struct tree_balance *tb)
{ … }

static void check_internal_levels(struct tree_balance *tb)
{ … }

#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)
{ … }

static inline void do_balance_completed(struct tree_balance *tb)
{ … }

/*
 * do_balance - balance the tree
 *
 * @tb: tree_balance structure
 * @ih: item header of inserted item
 * @body: body of inserted item or bytes to paste
 * @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.
 */
void do_balance(struct tree_balance *tb, struct item_head *ih,
		const char *body, int flag)
{ … }
linux/fs/reiserfs/do_balan.c
