stree.c

linux 内核源代码

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

/*
 *  Written by Anatoly P. Pinchuk [e-mail]
 *  Programm System Institute
 *  Pereslavl-Zalessky Russia
 */

/*
 *  This file contains functions dealing with S+tree
 *
 * B_IS_IN_TREE
 * copy_item_head
 * comp_short_keys
 * comp_keys
 * comp_short_le_keys
 * le_key2cpu_key
 * comp_le_keys
 * bin_search
 * get_lkey
 * get_rkey
 * key_in_buffer
 * decrement_bcount
 * decrement_counters_in_path
 * reiserfs_check_path
 * pathrelse_and_restore
 * pathrelse
 * search_by_key_reada
 * search_by_key
 * search_for_position_by_key
 * comp_items
 * prepare_for_direct_item
 * prepare_for_direntry_item
 * prepare_for_delete_or_cut
 * calc_deleted_bytes_number
 * init_tb_struct
 * padd_item
 * reiserfs_delete_item
 * reiserfs_delete_solid_item
 * reiserfs_delete_object
 * maybe_indirect_to_direct
 * indirect_to_direct_roll_back
 * reiserfs_cut_from_item
 * truncate_directory
 * reiserfs_do_truncate
 * reiserfs_paste_into_item
 * reiserfs_insert_item
 */

#include <linux/time.h>
#include <linux/string.h>
#include <linux/pagemap.h>
#include <linux/reiserfs_fs.h>
#include <linux/buffer_head.h>
#include <linux/quotaops.h>

/* Does the buffer contain a disk block which is in the tree. */
inline int B_IS_IN_TREE(const struct buffer_head *p_s_bh)
{

	RFALSE(B_LEVEL(p_s_bh) > MAX_HEIGHT,
	       "PAP-1010: block (%b) has too big level (%z)", p_s_bh, p_s_bh);

	return (B_LEVEL(p_s_bh) != FREE_LEVEL);
}

//
// to gets item head in le form
//
inline void copy_item_head(struct item_head *p_v_to,
			   const struct item_head *p_v_from)
{
	memcpy(p_v_to, p_v_from, IH_SIZE);
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable. For key of items of the same
   object this returns 0.
   Returns: -1 if key1 < key2 
   0 if key1 == key2
   1 if key1 > key2 */
inline int comp_short_keys(const struct reiserfs_key *le_key,
			   const struct cpu_key *cpu_key)
{
	__u32 n;
	n = le32_to_cpu(le_key->k_dir_id);
	if (n < cpu_key->on_disk_key.k_dir_id)
		return -1;
	if (n > cpu_key->on_disk_key.k_dir_id)
		return 1;
	n = le32_to_cpu(le_key->k_objectid);
	if (n < cpu_key->on_disk_key.k_objectid)
		return -1;
	if (n > cpu_key->on_disk_key.k_objectid)
		return 1;
	return 0;
}

/* k1 is pointer to on-disk structure which is stored in little-endian
   form. k2 is pointer to cpu variable.
   Compare keys using all 4 key fields.
   Returns: -1 if key1 < key2 0
   if key1 = key2 1 if key1 > key2 */
static inline int comp_keys(const struct reiserfs_key *le_key,
			    const struct cpu_key *cpu_key)
{
	int retval;

	retval = comp_short_keys(le_key, cpu_key);
	if (retval)
		return retval;
	if (le_key_k_offset(le_key_version(le_key), le_key) <
	    cpu_key_k_offset(cpu_key))
		return -1;
	if (le_key_k_offset(le_key_version(le_key), le_key) >
	    cpu_key_k_offset(cpu_key))
		return 1;

	if (cpu_key->key_length == 3)
		return 0;

	/* this part is needed only when tail conversion is in progress */
	if (le_key_k_type(le_key_version(le_key), le_key) <
	    cpu_key_k_type(cpu_key))
		return -1;

	if (le_key_k_type(le_key_version(le_key), le_key) >
	    cpu_key_k_type(cpu_key))
		return 1;

	return 0;
}

inline int comp_short_le_keys(const struct reiserfs_key *key1,
			      const struct reiserfs_key *key2)
{
	__u32 *p_s_1_u32, *p_s_2_u32;
	int n_key_length = REISERFS_SHORT_KEY_LEN;

	p_s_1_u32 = (__u32 *) key1;
	p_s_2_u32 = (__u32 *) key2;
	for (; n_key_length--; ++p_s_1_u32, ++p_s_2_u32) {
		if (le32_to_cpu(*p_s_1_u32) < le32_to_cpu(*p_s_2_u32))
			return -1;
		if (le32_to_cpu(*p_s_1_u32) > le32_to_cpu(*p_s_2_u32))
			return 1;
	}
	return 0;
}

inline void le_key2cpu_key(struct cpu_key *to, const struct reiserfs_key *from)
{
	int version;
	to->on_disk_key.k_dir_id = le32_to_cpu(from->k_dir_id);
	to->on_disk_key.k_objectid = le32_to_cpu(from->k_objectid);

	// find out version of the key
	version = le_key_version(from);
	to->version = version;
	to->on_disk_key.k_offset = le_key_k_offset(version, from);
	to->on_disk_key.k_type = le_key_k_type(version, from);
}

// this does not say which one is bigger, it only returns 1 if keys
// are not equal, 0 otherwise
inline int comp_le_keys(const struct reiserfs_key *k1,
			const struct reiserfs_key *k2)
{
	return memcmp(k1, k2, sizeof(struct reiserfs_key));
}

/**************************************************************************
 *  Binary search toolkit function                                        *
 *  Search for an item in the array by the item key                       *
 *  Returns:    1 if found,  0 if not found;                              *
 *        *p_n_pos = number of the searched element if found, else the    *
 *        number of the first element that is larger than p_v_key.        *
 **************************************************************************/
/* For those not familiar with binary search: n_lbound is the leftmost item that it
 could be, n_rbound the rightmost item that it could be.  We examine the item
 halfway between n_lbound and n_rbound, and that tells us either that we can increase
 n_lbound, or decrease n_rbound, or that we have found it, or if n_lbound <= n_rbound that
 there are no possible items, and we have not found it. With each examination we
 cut the number of possible items it could be by one more than half rounded down,
 or we find it. */
static inline int bin_search(const void *p_v_key,	/* Key to search for.                   */
			     const void *p_v_base,	/* First item in the array.             */
			     int p_n_num,	/* Number of items in the array.        */
			     int p_n_width,	/* Item size in the array.
						   searched. Lest the reader be
						   confused, note that this is crafted
						   as a general function, and when it
						   is applied specifically to the array
						   of item headers in a node, p_n_width
						   is actually the item header size not
						   the item size.                      */
			     int *p_n_pos	/* Number of the searched for element. */
    )
{
	int n_rbound, n_lbound, n_j;

	for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2;
	     n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2)
		switch (comp_keys
			((struct reiserfs_key *)((char *)p_v_base +
						 n_j * p_n_width),
			 (struct cpu_key *)p_v_key)) {
		case -1:
			n_lbound = n_j + 1;
			continue;
		case 1:
			n_rbound = n_j - 1;
			continue;
		case 0:
			*p_n_pos = n_j;
			return ITEM_FOUND;	/* Key found in the array.  */
		}

	/* bin_search did not find given key, it returns position of key,
	   that is minimal and greater than the given one. */
	*p_n_pos = n_lbound;
	return ITEM_NOT_FOUND;
}

#ifdef CONFIG_REISERFS_CHECK
extern struct tree_balance *cur_tb;
#endif

/* Minimal possible key. It is never in the tree. */
const struct reiserfs_key MIN_KEY = { 0, 0, {{0, 0},} };

/* Maximal possible key. It is never in the tree. */
static const struct reiserfs_key MAX_KEY = {
	__constant_cpu_to_le32(0xffffffff),
	__constant_cpu_to_le32(0xffffffff),
	{{__constant_cpu_to_le32(0xffffffff),
	  __constant_cpu_to_le32(0xffffffff)},}
};

/* Get delimiting key of the buffer by looking for it in the buffers in the path, starting from the bottom
   of the path, and going upwards.  We must check the path's validity at each step.  If the key is not in
   the path, there is no delimiting key in the tree (buffer is first or last buffer in tree), and in this
   case we return a special key, either MIN_KEY or MAX_KEY. */
static inline const struct reiserfs_key *get_lkey(const struct treepath
						  *p_s_chk_path,
						  const struct super_block
						  *p_s_sb)
{
	int n_position, n_path_offset = p_s_chk_path->path_length;
	struct buffer_head *p_s_parent;

	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5010: invalid offset in the path");

	/* While not higher in path than first element. */
	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
		       "PAP-5020: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (p_s_parent =
		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
			return &MAX_KEY;
		/* Check whether position in the parent is correct. */
		if ((n_position =
		     PATH_OFFSET_POSITION(p_s_chk_path,
					  n_path_offset)) >
		    B_NR_ITEMS(p_s_parent))
			return &MAX_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
		    PATH_OFFSET_PBUFFER(p_s_chk_path,
					n_path_offset + 1)->b_blocknr)
			return &MAX_KEY;
		/* Return delimiting key if position in the parent is not equal to zero. */
		if (n_position)
			return B_N_PDELIM_KEY(p_s_parent, n_position - 1);
	}
	/* Return MIN_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
		return &MIN_KEY;
	return &MAX_KEY;
}

/* Get delimiting key of the buffer at the path and its right neighbor. */
inline const struct reiserfs_key *get_rkey(const struct treepath *p_s_chk_path,
					   const struct super_block *p_s_sb)
{
	int n_position, n_path_offset = p_s_chk_path->path_length;
	struct buffer_head *p_s_parent;

	RFALSE(n_path_offset < FIRST_PATH_ELEMENT_OFFSET,
	       "PAP-5030: invalid offset in the path");

	while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) {

		RFALSE(!buffer_uptodate
		       (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)),
		       "PAP-5040: parent is not uptodate");

		/* Parent at the path is not in the tree now. */
		if (!B_IS_IN_TREE
		    (p_s_parent =
		     PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset)))
			return &MIN_KEY;
		/* Check whether position in the parent is correct. */
		if ((n_position =
		     PATH_OFFSET_POSITION(p_s_chk_path,
					  n_path_offset)) >
		    B_NR_ITEMS(p_s_parent))
			return &MIN_KEY;
		/* Check whether parent at the path really points to the child. */
		if (B_N_CHILD_NUM(p_s_parent, n_position) !=
		    PATH_OFFSET_PBUFFER(p_s_chk_path,
					n_path_offset + 1)->b_blocknr)
			return &MIN_KEY;
		/* Return delimiting key if position in the parent is not the last one. */
		if (n_position != B_NR_ITEMS(p_s_parent))
			return B_N_PDELIM_KEY(p_s_parent, n_position);
	}
	/* Return MAX_KEY if we are in the root of the buffer tree. */
	if (PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->
	    b_blocknr == SB_ROOT_BLOCK(p_s_sb))
		return &MAX_KEY;
	return &MIN_KEY;
}

/* Check whether a key is contained in the tree rooted from a buffer at a path. */
/* This works by looking at the left and right delimiting keys for the buffer in the last path_element in
   the path.  These delimiting keys are stored at least one level above that buffer in the tree. If the
   buffer is the first or last node in the tree order then one of the delimiting keys may be absent, and in
   this case get_lkey and get_rkey return a special key which is MIN_KEY or MAX_KEY. */
static inline int key_in_buffer(struct treepath *p_s_chk_path,	/* Path which should be checked.  */
				const struct cpu_key *p_s_key,	/* Key which should be checked.   */
				struct super_block *p_s_sb	/* Super block pointer.           */
    )
{

	RFALSE(!p_s_key || p_s_chk_path->path_length < FIRST_PATH_ELEMENT_OFFSET
	       || p_s_chk_path->path_length > MAX_HEIGHT,
	       "PAP-5050: pointer to the key(%p) is NULL or invalid path length(%d)",
	       p_s_key, p_s_chk_path->path_length);
	RFALSE(!PATH_PLAST_BUFFER(p_s_chk_path)->b_bdev,
	       "PAP-5060: device must not be NODEV");

	if (comp_keys(get_lkey(p_s_chk_path, p_s_sb), p_s_key) == 1)
		/* left delimiting key is bigger, that the key we look for */
		return 0;
	//  if ( comp_keys(p_s_key, get_rkey(p_s_chk_path, p_s_sb)) != -1 )
	if (comp_keys(get_rkey(p_s_chk_path, p_s_sb), p_s_key) != 1)
		/* p_s_key must be less than right delimitiing key */
		return 0;
	return 1;
}

inline void decrement_bcount(struct buffer_head *p_s_bh)
{
	if (p_s_bh) {
		if (atomic_read(&(p_s_bh->b_count))) {
			put_bh(p_s_bh);
			return;
		}
		reiserfs_panic(NULL,
			       "PAP-5070: decrement_bcount: trying to free free buffer %b",
			       p_s_bh);
	}
}

/* Decrement b_count field of the all buffers in the path. */
void decrement_counters_in_path(struct treepath *p_s_search_path)
{
	int n_path_offset = p_s_search_path->path_length;

	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET ||
	       n_path_offset > EXTENDED_MAX_HEIGHT - 1,
	       "PAP-5080: invalid path offset of %d", n_path_offset);

	while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) {
		struct buffer_head *bh;

		bh = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--);
		decrement_bcount(bh);
	}
	p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

int reiserfs_check_path(struct treepath *p)
{
	RFALSE(p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET,
	       "path not properly relsed");
	return 0;
}

/* Release all buffers in the path. Restore dirty bits clean
** when preparing the buffer for the log
**
** only called from fix_nodes()
*/
void pathrelse_and_restore(struct super_block *s, struct treepath *p_s_search_path)
{
	int n_path_offset = p_s_search_path->path_length;