stree.c

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

      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 path         * 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 illegal path length(%d)",
	  p_s_key, p_s_chk_path->path_length);
  RFALSE( PATH_PLAST_BUFFER(p_s_chk_path)->b_dev == NODEV,
	  "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 path * 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: illegal 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 path *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 path * p_s_search_path
      ) {
  int n_path_offset = p_s_search_path->path_length;

  RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET, 
	  "clm-4000: illegal path offset");
  
  while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )  {
    reiserfs_restore_prepared_buffer(s, PATH_OFFSET_PBUFFER(p_s_search_path, 
                                     n_path_offset));
    brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));
  }
  p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}

/* Release all buffers in the path. */
void  pathrelse (
        struct path * p_s_search_path
      ) {
  int n_path_offset = p_s_search_path->path_length;

  RFALSE( n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	  "PAP-5090: illegal path offset");
  
  while ( n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET )  
    brelse(PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--));

  p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET;
}



static int is_leaf (char * buf, int blocksize, struct buffer_head * bh)
{
    struct block_head * blkh;
    struct item_head * ih;
    int used_space;
    int prev_location;
    int i;
    int nr;

    blkh = (struct block_head *)buf;
    if ( blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) {
	printk ("is_leaf: this should be caught earlier\n");
	return 0;
    }

    nr = blkh_nr_item(blkh);
    if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) {
	/* item number is too big or too small */
	reiserfs_warning ("is_leaf: nr_item seems wrong: %z\n", bh);
	return 0;
    }
    ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1;
    used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location (ih));
    if (used_space != blocksize - blkh_free_space(blkh)) {
	/* free space does not match to calculated amount of use space */
	reiserfs_warning ("is_leaf: free space seems wrong: %z\n", bh);
	return 0;
    }

    // FIXME: it is_leaf will hit performance too much - we may have
    // return 1 here

    /* check tables of item heads */
    ih = (struct item_head *)(buf + BLKH_SIZE);
    prev_location = blocksize;
    for (i = 0; i < nr; i ++, ih ++) {
	if (ih_location (ih) >= blocksize || ih_location (ih) < IH_SIZE * nr) {
	    reiserfs_warning ("is_leaf: item location seems wrong: %h\n", ih);
	    return 0;
	}
	if (ih_item_len (ih) < 1 || ih_item_len (ih) > MAX_ITEM_LEN (blocksize)) {
	    reiserfs_warning ("is_leaf: item length seems wrong: %h\n", ih);
	    return 0;
	}
	if (prev_location - ih_location (ih) != ih_item_len (ih)) {
	    reiserfs_warning ("is_leaf: item location seems wrong (second one): %h\n", ih);
	    return 0;
	}
	prev_location = ih_location (ih);
    }

    // one may imagine much more checks
    return 1;
}


/* returns 1 if buf looks like an internal node, 0 otherwise */
static int is_internal (char * buf, int blocksize, struct buffer_head * bh)
{
    struct block_head * blkh;
    int nr;
    int used_space;

    blkh = (struct block_head *)buf;
    nr = blkh_level(blkh);
    if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) {
	/* this level is not possible for internal nodes */
	printk ("is_internal: this should be caught earlier\n");
	return 0;
    }
    
    nr = blkh_nr_item(blkh);
    if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) {
	/* for internal which is not root we might check min number of keys */
	reiserfs_warning ("is_internal: number of key seems wrong: %z\n", bh);
	return 0;
    }

    used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
    if (used_space != blocksize - blkh_free_space(blkh)) {
	reiserfs_warning ("is_internal: free space seems wrong: %z\n", bh);
	return 0;
    }

    // one may imagine much more checks
    return 1;
}


// make sure that bh contains formatted node of reiserfs tree of
// 'level'-th level
static int is_tree_node (struct buffer_head * bh, int level)
{
    if (B_LEVEL (bh) != level) {
	printk ("is_tree_node: node level %d does not match to the expected one %d\n",
		B_LEVEL (bh), level);
	return 0;
    }
    if (level == DISK_LEAF_NODE_LEVEL)
	return is_leaf (bh->b_data, bh->b_size, bh);

    return is_internal (bh->b_data, bh->b_size, bh);
}



#ifdef SEARCH_BY_KEY_READA

/* The function is NOT SCHEDULE-SAFE! */
static void search_by_key_reada (struct super_block * s, int blocknr)
{
    struct buffer_head * bh;
  
    if (blocknr == 0)
	return;

    bh = getblk (s->s_dev, blocknr, s->s_blocksize);
  
    if (!buffer_uptodate (bh)) {
	ll_rw_block (READA, 1, &bh);
    }
    bh->b_count --;
}

#endif

/**************************************************************************
 * Algorithm   SearchByKey                                                *
 *             look for item in the Disk S+Tree by its key                *
 * Input:  p_s_sb   -  super block                                        *
 *         p_s_key  - pointer to the key to search                        *
 * Output: ITEM_FOUND, ITEM_NOT_FOUND or IO_ERROR                         *
 *         p_s_search_path - path from the root to the needed leaf        *
 **************************************************************************/

/* This function fills up the path from the root to the leaf as it
   descends the tree looking for the key.  It uses reiserfs_bread to
   try to find buffers in the cache given their block number.  If it
   does not find them in the cache it reads them from disk.  For each
   node search_by_key finds using reiserfs_bread it then uses
   bin_search to look through that node.  bin_search will find the
   position of the block_number of the next node if it is looking
   through an internal node.  If it is looking through a leaf node
   bin_search will find the position of the item which has key either
   equal to given key, or which is the maximal key less than the given
   key.  search_by_key returns a path that must be checked for the
   correctness of the top of the path but need not be checked for the
   correctness of the bottom of the path */
/* The function is NOT SCHEDULE-SAFE! */
int search_by_key (struct super_block * p_s_sb,
		   const struct cpu_key * p_s_key, /* Key to search. */
		   struct path * p_s_search_path, /* This structure was
						     allocated and initialized
						     by the calling
						     function. It is filled up
						     by this function.  */
		   int n_stop_level /* How far down the tree to search. To
                                       stop at leaf level - set to
                                       DISK_LEAF_NODE_LEVEL */
    ) {
    int  n_block_number = SB_ROOT_BLOCK (p_s_sb),
      expected_level = SB_TREE_HEIGHT (p_s_sb),
      n_block_size    = p_s_sb->s_blocksize;
    struct buffer_head  *       p_s_bh;
    struct path_element *       p_s_last_element;
    int				n_node_level, n_retval;
    int 			right_neighbor_of_leaf_node;
    int				fs_gen;

#ifdef CONFIG_REISERFS_CHECK
    int n_repeat_counter = 0;
#endif
    
    PROC_INFO_INC( p_s_sb, search_by_key );
    
    /* As we add each node to a path we increase its count.  This means that
       we must be careful to release all nodes in a path before we either
       discard the path struct or re-use the path struct, as we do here. */

    decrement_counters_in_path(p_s_search_path);

    right_neighbor_of_leaf_node = 0;

    /* With each iteration of this loop we search through the items in the
       current node, and calculate the next current node(next path element)
       for the next iteration of this loop.. */
    while ( 1 ) {

#ifdef CONFIG_REISERFS_CHECK
	if ( !(++n_repeat_counter % 50000) )
	    reiserfs_warning ("PAP-5100: search_by_key: %s:"
			      "there were %d iterations of while loop "
			      "looking for key %K\n",
			      current->comm, n_repeat_counter, p_s_key);
#endif

	/* prep path to have another element added to it. */
	p_s_last_element = PATH_OFFSET_PELEMENT(p_s_search_path, ++p_s_search_path->path_length);
	fs_gen = get_generation (p_s_sb);
	expected_level --;

#ifdef SEARCH_BY_KEY_READA
	/* schedule read of right neighbor */
	search_by_key_reada (p_s_sb, right_neighbor_of_leaf_node);
#endif

	/* Read the next tree node, and set the last element in the path to
           have a pointer to it. */
	if ( ! (p_s_bh = p_s_last_element->pe_buffer =
		reiserfs_bread(p_s_sb, n_block_number, n_block_size)) ) {
	    p_s_search_path->path_length --;
	    pathrelse(p_s_search_path);
	    return IO_ERROR;
	}

 	if( fs_changed (fs_gen, p_s_sb) ) {
 		PROC_INFO_INC( p_s_sb, search_by_key_fs_changed );
 		PROC_INFO_INC( p_s_sb, sbk_fs_changed[ expected_level - 1 ] );
 	}

	/* It is possible that schedule occurred. We must check whether the key
	   to search is still in the tree rooted from the current buffer. If
	   not then repeat search from the root. */
	if ( fs_changed (fs_gen, p_s_sb) && 
	     (!B_IS_IN_TREE (p_s_bh) || !key_in_buffer(p_s_search_path, p_s_key, p_s_sb)) ) {
 	    PROC_INFO_INC( p_s_sb, search_by_key_restarted );
	    PROC_INFO_INC( p_s_sb, sbk_restarted[ expected_level - 1 ] );
	    decrement_counters_in_path(p_s_search_path);
	    
	    /* Get the root block number so that we can repeat the search
               starting from the root. */
	    n_block_number = SB_ROOT_BLOCK (p_s_sb);
	    expected_level = SB_TREE_HEIGHT (p_s_sb);
	    right_neighbor_of_leaf_node = 0;
	    
	    /* repeat search from the root */
	    continue;
	}

        /* only check that the key is in the buffer if p_s_key is not
           equal to the MAX_KEY. Latter case is only possible in
           "finish_unfinished()" processing during mount. */
        RFALSE( COMP_KEYS( &MAX_KEY, p_s_key ) && 
                ! key_in_buffer(p_s_search_path, p_s_key, p_s_sb),
		"PAP-5130: key is not in the buffer");
#ifdef CONFIG_REISERFS_CHECK
	if ( cur_tb ) {
	    print_cur_tb ("5140");
	    reiserfs_panic(p_s_sb, "PAP-5140: search_by_key: schedule occurred in do_balance!");
	}
#endif

	// make sure, that the node contents look like a node of
	// certain level