stree.c

linux 内核源代码

	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "clm-4000: invalid 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 treepath *p_s_search_path)
{
	int n_path_offset = p_s_search_path->path_length;

	RFALSE(n_path_offset < ILLEGAL_PATH_ELEMENT_OFFSET,
	       "PAP-5090: invalid 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) {
		reiserfs_warning(NULL,
				 "is_leaf: this should be caught earlier");
		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(NULL, "is_leaf: nr_item seems wrong: %z", 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(NULL, "is_leaf: free space seems wrong: %z",
				 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 (le_ih_k_type(ih) == TYPE_ANY) {
			reiserfs_warning(NULL,
					 "is_leaf: wrong item type for item %h",
					 ih);
			return 0;
		}
		if (ih_location(ih) >= blocksize
		    || ih_location(ih) < IH_SIZE * nr) {
			reiserfs_warning(NULL,
					 "is_leaf: item location seems wrong: %h",
					 ih);
			return 0;
		}
		if (ih_item_len(ih) < 1
		    || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) {
			reiserfs_warning(NULL,
					 "is_leaf: item length seems wrong: %h",
					 ih);
			return 0;
		}
		if (prev_location - ih_location(ih) != ih_item_len(ih)) {
			reiserfs_warning(NULL,
					 "is_leaf: item location seems wrong (second one): %h",
					 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 */
		reiserfs_warning(NULL,
				 "is_internal: this should be caught earlier");
		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(NULL,
				 "is_internal: number of key seems wrong: %z",
				 bh);
		return 0;
	}

	used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1);
	if (used_space != blocksize - blkh_free_space(blkh)) {
		reiserfs_warning(NULL,
				 "is_internal: free space seems wrong: %z", 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) {
		reiserfs_warning(NULL,
				 "is_tree_node: node level %d does not match to the expected one %d",
				 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);
}

#define SEARCH_BY_KEY_READA 16

/* The function is NOT SCHEDULE-SAFE! */
static void search_by_key_reada(struct super_block *s,
				struct buffer_head **bh,
				b_blocknr_t *b, int num)
{
	int i, j;

	for (i = 0; i < num; i++) {
		bh[i] = sb_getblk(s, b[i]);
	}
	for (j = 0; j < i; j++) {
		/*
		 * note, this needs attention if we are getting rid of the BKL
		 * you have to make sure the prepared bit isn't set on this buffer
		 */
		if (!buffer_uptodate(bh[j]))
			ll_rw_block(READA, 1, bh + j);
		brelse(bh[j]);
	}
}

/**************************************************************************
 * 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 treepath *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 */
    )
{
	b_blocknr_t n_block_number;
	int expected_level;
	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;
	struct buffer_head *reada_bh[SEARCH_BY_KEY_READA];
	b_blocknr_t reada_blocks[SEARCH_BY_KEY_READA];
	int reada_count = 0;

#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.. */
	n_block_number = SB_ROOT_BLOCK(p_s_sb);
	expected_level = -1;
	while (1) {

#ifdef CONFIG_REISERFS_CHECK
		if (!(++n_repeat_counter % 50000))
			reiserfs_warning(p_s_sb, "PAP-5100: search_by_key: %s:"
					 "there were %d iterations of while loop "
					 "looking for key %K",
					 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);

		/* 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 =
		     sb_getblk(p_s_sb, n_block_number))) {
			if (!buffer_uptodate(p_s_bh) && reada_count > 1) {
				search_by_key_reada(p_s_sb, reada_bh,
						    reada_blocks, reada_count);
			}
			ll_rw_block(READ, 1, &p_s_bh);
			wait_on_buffer(p_s_bh);
			if (!buffer_uptodate(p_s_bh))
				goto io_error;
		} else {
		      io_error:
			p_s_search_path->path_length--;
			pathrelse(p_s_search_path);
			return IO_ERROR;
		}
		reada_count = 0;
		if (expected_level == -1)
			expected_level = SB_TREE_HEIGHT(p_s_sb);
		expected_level--;

		/* 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) ||
		     B_LEVEL(p_s_bh) != expected_level ||
		     !key_in_buffer(p_s_search_path, p_s_key, p_s_sb))) {
			PROC_INFO_INC(p_s_sb, search_by_key_fs_changed);
			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 = -1;
			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
		if (!is_tree_node(p_s_bh, expected_level)) {
			reiserfs_warning(p_s_sb, "vs-5150: search_by_key: "
					 "invalid format found in block %ld. Fsck?",
					 p_s_bh->b_blocknr);
			pathrelse(p_s_search_path);
			return IO_ERROR;
		}

		/* ok, we have acquired next formatted node in the tree */
		n_node_level = B_LEVEL(p_s_bh);

		PROC_INFO_BH_STAT(p_s_sb, p_s_bh, n_node_level - 1);

		RFALSE(n_node_level < n_stop_level,
		       "vs-5152: tree level (%d) is less than stop level (%d)",
		       n_node_level, n_stop_level);

		n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bh, 0),
				      B_NR_ITEMS(p_s_bh),
				      (n_node_level ==
				       DISK_LEAF_NODE_LEVEL) ? IH_SIZE :
				      KEY_SIZE,
				      &(p_s_last_element->pe_position));
		if (n_node_level == n_stop_level) {
			return n_retval;
		}

		/* we are not in the stop level */
		if (n_retval == ITEM_FOUND)
			/* item has been found, so we choose the pointer which is to the right of the found one */
			p_s_last_element->pe_position++;

		/* if item was not found we choose the position which is to
		   the left of the found item. This requires no code,
		   bin_search did it already. */

		/* So we have chosen a position in the current node which is
		   an internal node.  Now we calculate child block number by
		   position in the node. */
		n_block_number =
		    B_N_CHILD_NUM(p_s_bh, p_s_last_element->pe_position);

		/* if we are going to read leaf nodes, try for read ahead as well */
		if ((p_s_search_path->reada & PATH_READA) &&
		    n_node_level == DISK_LEAF_NODE_LEVEL + 1) {
			int pos = p_s_last_element->pe_position;
			int limit = B_NR_ITEMS(p_s_bh);
			struct reiserfs_key *le_key;

			if (p_s_search_path->reada & PATH_READA_BACK)
				limit = 0;
			while (reada_count < SEARCH_BY_KEY_READA) {
				if (pos == limit)
					break;
				reada_blocks[reada_count++] =
				    B_N_CHILD_NUM(p_s_bh, pos);
				if (p_s_search_path->reada & PATH_READA_BACK)
					pos--;
				else
					pos++;

				/*
				 * check to make sure we're in the same object
				 */
				le_key = B_N_PDELIM_KEY(p_s_bh, pos);
				if (le32_to_cpu(le_key->k_objectid) !=
				    p_s_key->on_disk_key.k_objectid) {
					break;
				}
			}
		}
	}
}

/* Form the path to an item and position in this item which contains
   file byte defined by p_s_key. If there is no such item
   corresponding to the key, we point the path to the item with
   maximal key less than p_s_key, and *p_n_pos_in_item is set to one
   past the last entry/byte in the item.  If searching for entry in a
   directory item, and it is not found, *p_n_pos_in_item is set to one
   entry more than the entry with maximal key which is less than the
   sought key.

   Note that if there is no entry in this same node which is one more,
   then we point to an imaginary entry.  for direct items, the
   position is in units of bytes, for indirect items the position is
   in units of blocknr entries, for directory items the position is in
   units of directory entries.  */

/* The function is NOT SCHEDULE-SAFE! */
int search_for_position_by_key(struct super_block *p_s_sb,	/* Pointer to the super block.          */
			       const struct cpu_key *p_cpu_key,	/* Key to search (cpu variable)         */
			       struct treepath *p_s_search_path	/* Filled up by this function.          */
    )