stree.c

ARM 嵌入式 系统 设计与实例开发 实验教材 二源码

/*
 *  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_short_key
 * copy_item_head
 * comp_short_keys
 * comp_keys
 * comp_cpu_keys
 * comp_short_le_keys
 * comp_short_cpu_keys
 * cpu_key2cpu_key
 * 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/config.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/locks.h>
#include <linux/pagemap.h>
#include <linux/reiserfs_fs.h>
#include <linux/smp_lock.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 );
}




inline void copy_short_key (void * to, const void * from)
{
    memcpy (to, from, SHORT_KEY_SIZE);
}

//
// 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 key * le_key, 
			     const struct cpu_key * cpu_key)
{
  __u32 * p_s_le_u32, * p_s_cpu_u32;
  int n_key_length = REISERFS_SHORT_KEY_LEN;

  p_s_le_u32 = (__u32 *)le_key;
  p_s_cpu_u32 = (__u32 *)cpu_key;
  for( ; n_key_length--; ++p_s_le_u32, ++p_s_cpu_u32 ) {
    if ( le32_to_cpu (*p_s_le_u32) < *p_s_cpu_u32 )
      return -1;
    if ( le32_to_cpu (*p_s_le_u32) > *p_s_cpu_u32 )
      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 */
inline int  comp_keys (const struct 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;
}


//
// FIXME: not used yet
//
inline int comp_cpu_keys (const struct cpu_key * key1, 
			  const struct cpu_key * key2)
{
    if (key1->on_disk_key.k_dir_id < key2->on_disk_key.k_dir_id)
	return -1;
    if (key1->on_disk_key.k_dir_id > key2->on_disk_key.k_dir_id)
	return 1;

    if (key1->on_disk_key.k_objectid < key2->on_disk_key.k_objectid)
	return -1;
    if (key1->on_disk_key.k_objectid > key2->on_disk_key.k_objectid)
	return 1;

    if (cpu_key_k_offset (key1) < cpu_key_k_offset (key2))
	return -1;
    if (cpu_key_k_offset (key1) > cpu_key_k_offset (key2))
	return 1;

    reiserfs_warning ("comp_cpu_keys: type are compared for %k and %k\n",
		      key1, key2);

    if (cpu_key_k_type (key1) < cpu_key_k_type (key2))
	return -1;
    if (cpu_key_k_type (key1) > cpu_key_k_type (key2))
	return 1;
    return 0;
}

inline int comp_short_le_keys (const struct key * key1, const struct 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 int comp_short_cpu_keys (const struct cpu_key * key1, 
				const struct cpu_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 ( *p_s_1_u32 < *p_s_2_u32 )
      return -1;
    if ( *p_s_1_u32 > *p_s_2_u32 )
      return 1;
  }
  return 0;
}



inline void cpu_key2cpu_key (struct cpu_key * to, const struct cpu_key * from)
{
    memcpy (to, from, sizeof (struct cpu_key));
}


inline void le_key2cpu_key (struct cpu_key * to, const struct key * from)
{
    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
    to->version = le_key_version (from);
    if (to->version == KEY_FORMAT_3_5) {
	to->on_disk_key.u.k_offset_v1.k_offset = le32_to_cpu (from->u.k_offset_v1.k_offset);
	to->on_disk_key.u.k_offset_v1.k_uniqueness = le32_to_cpu (from->u.k_offset_v1.k_uniqueness);
    } else {
	to->on_disk_key.u.k_offset_v2.k_offset = offset_v2_k_offset(&from->u.k_offset_v2);
	to->on_disk_key.u.k_offset_v2.k_type = offset_v2_k_type(&from->u.k_offset_v2);
    } 
}



// 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 key * k1, const struct key * k2)
{
    return memcmp (k1, k2, sizeof (struct 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. */
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 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 key  MIN_KEY = {0, 0, {{0, 0},}};

/* Maximal possible key. It is never in the tree. */
const struct key  MAX_KEY = {0xffffffff, 0xffffffff, {{0xffffffff, 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. */
inline	const struct  key * get_lkey  (
	                const struct path         * 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: illegal 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  key * get_rkey  (
	                const struct path         * 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: illegal 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) )