fix_node.c | Explore in Territory

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

#include <linux/time.h>
#include <linux/slab.h>
#include <linux/string.h>
#include "reiserfs.h"
#include <linux/buffer_head.h>

/*
 * To make any changes in the tree we find a node that contains item
 * to be changed/deleted or position in the node we insert a new item
 * to. We call this node S. To do balancing we need to decide what we
 * will shift to left/right neighbor, or to a new node, where new item
 * will be etc. To make this analysis simpler we build virtual
 * node. Virtual node is an array of items, that will replace items of
 * node S. (For instance if we are going to delete an item, virtual
 * node does not contain it). Virtual node keeps information about
 * item sizes and types, mergeability of first and last items, sizes
 * of all entries in directory item. We use this array of items when
 * calculating what we can shift to neighbors and how many nodes we
 * have to have if we do not any shiftings, if we shift to left/right
 * neighbor or to both.
 */

/*
 * Takes item number in virtual node, returns number of item
 * that it has in source buffer
 */
static inline int old_item_num(int new_num, int affected_item_num, int mode)
{ … }

static void create_virtual_node(struct tree_balance *tb, int h)
{ … }

/*
 * Using virtual node check, how many items can be
 * shifted to left neighbor
 */
static void check_left(struct tree_balance *tb, int h, int cur_free)
{ … }

/*
 * Using virtual node check, how many items can be
 * shifted to right neighbor
 */
static void check_right(struct tree_balance *tb, int h, int cur_free)
{ … }

/*
 * from - number of items, which are shifted to left neighbor entirely
 * to - number of item, which are shifted to right neighbor entirely
 * from_bytes - number of bytes of boundary item (or directory entries)
 *              which are shifted to left neighbor
 * to_bytes - number of bytes of boundary item (or directory entries)
 *            which are shifted to right neighbor
 */
static int get_num_ver(int mode, struct tree_balance *tb, int h,
		       int from, int from_bytes,
		       int to, int to_bytes, short *snum012, int flow)
{ … }


/*
 * Set parameters for balancing.
 * Performs write of results of analysis of balancing into structure tb,
 * where it will later be used by the functions that actually do the balancing.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	lnum	number of items from S[h] that must be shifted to L[h];
 *	rnum	number of items from S[h] that must be shifted to R[h];
 *	blk_num	number of blocks that S[h] will be splitted into;
 *	s012	number of items that fall into splitted nodes.
 *	lbytes	number of bytes which flow to the left neighbor from the
 *              item that is not shifted entirely
 *	rbytes	number of bytes which flow to the right neighbor from the
 *              item that is not shifted entirely
 *	s1bytes	number of bytes which flow to the first  new node when
 *              S[0] splits (this number is contained in s012 array)
 */

static void set_parameters(struct tree_balance *tb, int h, int lnum,
			   int rnum, int blk_num, short *s012, int lb, int rb)
{ … }

/*
 * check if node disappears if we shift tb->lnum[0] items to left
 * neighbor and tb->rnum[0] to the right one.
 */
static int is_leaf_removable(struct tree_balance *tb)
{ … }

/* check whether L, S, R can be joined in one node */
static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
{ … }

/* when we do not split item, lnum and rnum are numbers of entire items */
#define SET_PAR_SHIFT_LEFT …

#define SET_PAR_SHIFT_RIGHT …

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

/*
 * Get new buffers for storing new nodes that are created while balancing.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 *	        NO_DISK_SPACE - no disk space.
 */
/* The function is NOT SCHEDULE-SAFE! */
static int get_empty_nodes(struct tree_balance *tb, int h)
{ … }

/*
 * Get free space of the left neighbor, which is stored in the parent
 * node of the left neighbor.
 */
static int get_lfree(struct tree_balance *tb, int h)
{ … }

/*
 * Get free space of the right neighbor,
 * which is stored in the parent node of the right neighbor.
 */
static int get_rfree(struct tree_balance *tb, int h)
{ … }

/* Check whether left neighbor is in memory. */
static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
{ … }

#define LEFT_PARENTS …
#define RIGHT_PARENTS …

static void decrement_key(struct cpu_key *key)
{ … }

/*
 * Calculate far left/right parent of the left/right neighbor of the
 * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
 * of the parent F[h].
 * Calculate left/right common parent of the current node and L[h]/R[h].
 * Calculate left/right delimiting key position.
 * Returns:	PATH_INCORRECT    - path in the tree is not correct
 *		SCHEDULE_OCCURRED - schedule occurred while the function worked
 *	        CARRY_ON          - schedule didn't occur while the function
 *				    worked
 */
static int get_far_parent(struct tree_balance *tb,
			  int h,
			  struct buffer_head **pfather,
			  struct buffer_head **pcom_father, char c_lr_par)
{ … }

/*
 * Get parents of neighbors of node in the path(S[path_offset]) and
 * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
 * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
 * CFR[path_offset].
 * Calculate numbers of left and right delimiting keys position:
 * lkey[path_offset], rkey[path_offset].
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked
 *	        CARRY_ON - schedule didn't occur while the function worked
 */
static int get_parents(struct tree_balance *tb, int h)
{ … }

/*
 * it is possible to remove node as result of shiftings to
 * neighbors even when we insert or paste item.
 */
static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
				      struct tree_balance *tb, int h)
{ … }

/*
 * Check whether current node S[h] is balanced when increasing its size by
 * Inserting or Pasting.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occurred;
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
/* ip means Inserting or Pasting */
static int ip_check_balance(struct tree_balance *tb, int h)
{ … }

/*
 * Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting for INTERNAL node of S+tree.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occurred;
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 *
 * Note: Items of internal nodes have fixed size, so the balance condition for
 * the internal part of S+tree is as for the B-trees.
 */
static int dc_check_balance_internal(struct tree_balance *tb, int h)
{ … }

/*
 * Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Truncating for LEAF node of S+tree.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste;
 * Returns:	1 - schedule occurred;
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance_leaf(struct tree_balance *tb, int h)
{ … }

/*
 * Check whether current node S[h] is balanced when Decreasing its size by
 * Deleting or Cutting.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *	tb	tree_balance structure;
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	d - delete, c - cut.
 * Returns:	1 - schedule occurred;
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int dc_check_balance(struct tree_balance *tb, int h)
{ … }

/*
 * Check whether current node S[h] is balanced.
 * Calculate parameters for balancing for current level h.
 * Parameters:
 *
 *	tb	tree_balance structure:
 *
 *              tb is a large structure that must be read about in the header
 *		file at the same time as this procedure if the reader is
 *		to successfully understand this procedure
 *
 *	h	current level of the node;
 *	inum	item number in S[h];
 *	mode	i - insert, p - paste, d - delete, c - cut.
 * Returns:	1 - schedule occurred;
 *	        0 - balancing for higher levels needed;
 *	       -1 - no balancing for higher levels needed;
 *	       -2 - no disk space.
 */
static int check_balance(int mode,
			 struct tree_balance *tb,
			 int h,
			 int inum,
			 int pos_in_item,
			 struct item_head *ins_ih, const void *data)
{ … }

/* Check whether parent at the path is the really parent of the current node.*/
static int get_direct_parent(struct tree_balance *tb, int h)
{ … }

/*
 * Using lnum[h] and rnum[h] we should determine what neighbors
 * of S[h] we
 * need in order to balance S[h], and get them if necessary.
 * Returns:	SCHEDULE_OCCURRED - schedule occurred while the function worked;
 *	        CARRY_ON - schedule didn't occur while the function worked;
 */
static int get_neighbors(struct tree_balance *tb, int h)
{ … }

static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
{ … }

/*
 * maybe we should fail balancing we are going to perform when kmalloc
 * fails several times. But now it will loop until kmalloc gets
 * required memory
 */
static int get_mem_for_virtual_node(struct tree_balance *tb)
{ … }

#ifdef CONFIG_REISERFS_CHECK
static void tb_buffer_sanity_check(struct super_block *sb,
				   struct buffer_head *bh,
				   const char *descr, int level)
{ … }
#else
static void tb_buffer_sanity_check(struct super_block *sb,
				   struct buffer_head *bh,
				   const char *descr, int level)
{;
}
#endif

static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
{ … }

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

/*
 * Prepare for balancing, that is
 *	get all necessary parents, and neighbors;
 *	analyze what and where should be moved;
 *	get sufficient number of new nodes;
 * Balancing will start only after all resources will be collected at a time.
 *
 * When ported to SMP kernels, only at the last moment after all needed nodes
 * are collected in cache, will the resources be locked using the usual
 * textbook ordered lock acquisition algorithms.  Note that ensuring that
 * this code neither write locks what it does not need to write lock nor locks
 * out of order will be a pain in the butt that could have been avoided.
 * Grumble grumble. -Hans
 *
 * fix is meant in the sense of render unchanging
 *
 * Latency might be improved by first gathering a list of what buffers
 * are needed and then getting as many of them in parallel as possible? -Hans
 *
 * Parameters:
 *	op_mode	i - insert, d - delete, c - cut (truncate), p - paste (append)
 *	tb	tree_balance structure;
 *	inum	item number in S[h];
 *      pos_in_item - comment this if you can
 *      ins_ih	item head of item being inserted
 *	data	inserted item or data to be pasted
 * Returns:	1 - schedule occurred while the function worked;
 *	        0 - schedule didn't occur while the function worked;
 *             -1 - if no_disk_space
 */

int fix_nodes(int op_mode, struct tree_balance *tb,
	      struct item_head *ins_ih, const void *data)
{ … }

void unfix_nodes(struct tree_balance *tb)
{ … }
linux/fs/reiserfs/fix_node.c
