/*

   * Copyright (C) 2007,2008 Oracle.  All rights reserved.

   *
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public
   * License v2 as published by the Free Software Foundation.
   *
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * General Public License for more details.
   *
   * You should have received a copy of the GNU General Public
   * License along with this program; if not, write to the
   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   * Boston, MA 021110-1307, USA.
   */

  #include <linux/sched.h>

  #include <linux/slab.h>

  #include "ctree.h"
  #include "disk-io.h"

  #include "transaction.h"

  #include "print-tree.h"

  #include "locking.h"

  static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  		      *root, struct btrfs_path *path, int level);
  static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root

  		      *root, struct btrfs_key *ins_key,

  		      struct btrfs_path *path, int data_size, int extend);

  static int push_node_left(struct btrfs_trans_handle *trans,
  			  struct btrfs_root *root, struct extent_buffer *dst,

  			  struct extent_buffer *src, int empty);

  static int balance_node_right(struct btrfs_trans_handle *trans,
  			      struct btrfs_root *root,
  			      struct extent_buffer *dst_buf,
  			      struct extent_buffer *src_buf);

  static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  		   struct btrfs_path *path, int level, int slot);

  struct btrfs_path *btrfs_alloc_path(void)

  {

  	struct btrfs_path *path;

  	path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);

  	return path;

  }

  /*
   * set all locked nodes in the path to blocking locks.  This should
   * be done before scheduling
   */
  noinline void btrfs_set_path_blocking(struct btrfs_path *p)
  {
  	int i;
  	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {

  		if (!p->nodes[i] || !p->locks[i])
  			continue;
  		btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]);
  		if (p->locks[i] == BTRFS_READ_LOCK)
  			p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
  		else if (p->locks[i] == BTRFS_WRITE_LOCK)
  			p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;

  	}
  }
  
  /*
   * reset all the locked nodes in the patch to spinning locks.

   *
   * held is used to keep lockdep happy, when lockdep is enabled
   * we set held to a blocking lock before we go around and
   * retake all the spinlocks in the path.  You can safely use NULL
   * for held

   */

  noinline void btrfs_clear_path_blocking(struct btrfs_path *p,

  					struct extent_buffer *held, int held_rw)

  {
  	int i;

  
  #ifdef CONFIG_DEBUG_LOCK_ALLOC
  	/* lockdep really cares that we take all of these spinlocks
  	 * in the right order.  If any of the locks in the path are not
  	 * currently blocking, it is going to complain.  So, make really
  	 * really sure by forcing the path to blocking before we clear
  	 * the path blocking.
  	 */

  	if (held) {
  		btrfs_set_lock_blocking_rw(held, held_rw);
  		if (held_rw == BTRFS_WRITE_LOCK)
  			held_rw = BTRFS_WRITE_LOCK_BLOCKING;
  		else if (held_rw == BTRFS_READ_LOCK)
  			held_rw = BTRFS_READ_LOCK_BLOCKING;
  	}

  	btrfs_set_path_blocking(p);
  #endif
  
  	for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {

  		if (p->nodes[i] && p->locks[i]) {
  			btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]);
  			if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING)
  				p->locks[i] = BTRFS_WRITE_LOCK;
  			else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING)
  				p->locks[i] = BTRFS_READ_LOCK;
  		}

  	}

  
  #ifdef CONFIG_DEBUG_LOCK_ALLOC
  	if (held)

  		btrfs_clear_lock_blocking_rw(held, held_rw);

  #endif

  }

  /* this also releases the path */

  void btrfs_free_path(struct btrfs_path *p)

  {

  	if (!p)
  		return;

  	btrfs_release_path(p);

  	kmem_cache_free(btrfs_path_cachep, p);

  }

  /*
   * path release drops references on the extent buffers in the path
   * and it drops any locks held by this path
   *
   * It is safe to call this on paths that no locks or extent buffers held.
   */

  noinline void btrfs_release_path(struct btrfs_path *p)

  {
  	int i;

  	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {

  		p->slots[i] = 0;

  		if (!p->nodes[i])

  			continue;
  		if (p->locks[i]) {

  			btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);

  			p->locks[i] = 0;
  		}

  		free_extent_buffer(p->nodes[i]);

  		p->nodes[i] = NULL;

  	}
  }

  /*
   * safely gets a reference on the root node of a tree.  A lock
   * is not taken, so a concurrent writer may put a different node
   * at the root of the tree.  See btrfs_lock_root_node for the
   * looping required.
   *
   * The extent buffer returned by this has a reference taken, so
   * it won't disappear.  It may stop being the root of the tree
   * at any time because there are no locks held.
   */

  struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
  {
  	struct extent_buffer *eb;

  
  	rcu_read_lock();
  	eb = rcu_dereference(root->node);

  	extent_buffer_get(eb);

  	rcu_read_unlock();

  	return eb;
  }

  /* loop around taking references on and locking the root node of the
   * tree until you end up with a lock on the root.  A locked buffer
   * is returned, with a reference held.
   */

  struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
  {
  	struct extent_buffer *eb;

  	while (1) {

  		eb = btrfs_root_node(root);
  		btrfs_tree_lock(eb);

  		if (eb == root->node)

  			break;

  		btrfs_tree_unlock(eb);
  		free_extent_buffer(eb);
  	}
  	return eb;
  }

  /* loop around taking references on and locking the root node of the
   * tree until you end up with a lock on the root.  A locked buffer
   * is returned, with a reference held.
   */
  struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root)
  {
  	struct extent_buffer *eb;
  
  	while (1) {
  		eb = btrfs_root_node(root);
  		btrfs_tree_read_lock(eb);
  		if (eb == root->node)
  			break;
  		btrfs_tree_read_unlock(eb);
  		free_extent_buffer(eb);
  	}
  	return eb;
  }

  /* cowonly root (everything not a reference counted cow subvolume), just get
   * put onto a simple dirty list.  transaction.c walks this to make sure they
   * get properly updated on disk.
   */

  static void add_root_to_dirty_list(struct btrfs_root *root)
  {
  	if (root->track_dirty && list_empty(&root->dirty_list)) {
  		list_add(&root->dirty_list,
  			 &root->fs_info->dirty_cowonly_roots);
  	}
  }

  /*
   * used by snapshot creation to make a copy of a root for a tree with
   * a given objectid.  The buffer with the new root node is returned in
   * cow_ret, and this func returns zero on success or a negative error code.
   */

  int btrfs_copy_root(struct btrfs_trans_handle *trans,
  		      struct btrfs_root *root,
  		      struct extent_buffer *buf,
  		      struct extent_buffer **cow_ret, u64 new_root_objectid)
  {
  	struct extent_buffer *cow;

  	int ret = 0;
  	int level;

  	struct btrfs_disk_key disk_key;

  
  	WARN_ON(root->ref_cows && trans->transid !=
  		root->fs_info->running_transaction->transid);
  	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
  
  	level = btrfs_header_level(buf);

  	if (level == 0)
  		btrfs_item_key(buf, &disk_key, 0);
  	else
  		btrfs_node_key(buf, &disk_key, 0);

  	cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
  				     new_root_objectid, &disk_key, level,
  				     buf->start, 0);
  	if (IS_ERR(cow))

  		return PTR_ERR(cow);
  
  	copy_extent_buffer(cow, buf, 0, 0, cow->len);
  	btrfs_set_header_bytenr(cow, cow->start);
  	btrfs_set_header_generation(cow, trans->transid);

  	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
  	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
  				     BTRFS_HEADER_FLAG_RELOC);
  	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
  		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
  	else
  		btrfs_set_header_owner(cow, new_root_objectid);

  	write_extent_buffer(cow, root->fs_info->fsid,
  			    (unsigned long)btrfs_header_fsid(cow),
  			    BTRFS_FSID_SIZE);

  	WARN_ON(btrfs_header_generation(buf) > trans->transid);

  	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
  		ret = btrfs_inc_ref(trans, root, cow, 1);
  	else
  		ret = btrfs_inc_ref(trans, root, cow, 0);

  	if (ret)
  		return ret;
  
  	btrfs_mark_buffer_dirty(cow);
  	*cow_ret = cow;
  	return 0;
  }

  /*

   * check if the tree block can be shared by multiple trees
   */
  int btrfs_block_can_be_shared(struct btrfs_root *root,
  			      struct extent_buffer *buf)
  {
  	/*
  	 * Tree blocks not in refernece counted trees and tree roots
  	 * are never shared. If a block was allocated after the last
  	 * snapshot and the block was not allocated by tree relocation,
  	 * we know the block is not shared.
  	 */
  	if (root->ref_cows &&
  	    buf != root->node && buf != root->commit_root &&
  	    (btrfs_header_generation(buf) <=
  	     btrfs_root_last_snapshot(&root->root_item) ||
  	     btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
  		return 1;
  #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
  	if (root->ref_cows &&
  	    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
  		return 1;
  #endif
  	return 0;
  }
  
  static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
  				       struct btrfs_root *root,
  				       struct extent_buffer *buf,

  				       struct extent_buffer *cow,
  				       int *last_ref)

  {
  	u64 refs;
  	u64 owner;
  	u64 flags;
  	u64 new_flags = 0;
  	int ret;
  
  	/*
  	 * Backrefs update rules:
  	 *
  	 * Always use full backrefs for extent pointers in tree block
  	 * allocated by tree relocation.
  	 *
  	 * If a shared tree block is no longer referenced by its owner
  	 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
  	 * use full backrefs for extent pointers in tree block.
  	 *
  	 * If a tree block is been relocating
  	 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
  	 * use full backrefs for extent pointers in tree block.
  	 * The reason for this is some operations (such as drop tree)
  	 * are only allowed for blocks use full backrefs.
  	 */
  
  	if (btrfs_block_can_be_shared(root, buf)) {
  		ret = btrfs_lookup_extent_info(trans, root, buf->start,
  					       buf->len, &refs, &flags);
  		BUG_ON(ret);
  		BUG_ON(refs == 0);
  	} else {
  		refs = 1;
  		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
  		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
  			flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
  		else
  			flags = 0;
  	}
  
  	owner = btrfs_header_owner(buf);
  	BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
  	       !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
  
  	if (refs > 1) {
  		if ((owner == root->root_key.objectid ||
  		     root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
  		    !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
  			ret = btrfs_inc_ref(trans, root, buf, 1);
  			BUG_ON(ret);
  
  			if (root->root_key.objectid ==
  			    BTRFS_TREE_RELOC_OBJECTID) {
  				ret = btrfs_dec_ref(trans, root, buf, 0);
  				BUG_ON(ret);
  				ret = btrfs_inc_ref(trans, root, cow, 1);
  				BUG_ON(ret);
  			}
  			new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
  		} else {
  
  			if (root->root_key.objectid ==
  			    BTRFS_TREE_RELOC_OBJECTID)
  				ret = btrfs_inc_ref(trans, root, cow, 1);
  			else
  				ret = btrfs_inc_ref(trans, root, cow, 0);
  			BUG_ON(ret);
  		}
  		if (new_flags != 0) {
  			ret = btrfs_set_disk_extent_flags(trans, root,
  							  buf->start,
  							  buf->len,
  							  new_flags, 0);
  			BUG_ON(ret);
  		}
  	} else {
  		if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
  			if (root->root_key.objectid ==
  			    BTRFS_TREE_RELOC_OBJECTID)
  				ret = btrfs_inc_ref(trans, root, cow, 1);
  			else
  				ret = btrfs_inc_ref(trans, root, cow, 0);
  			BUG_ON(ret);
  			ret = btrfs_dec_ref(trans, root, buf, 1);
  			BUG_ON(ret);
  		}
  		clean_tree_block(trans, root, buf);

  		*last_ref = 1;

  	}
  	return 0;
  }
  
  /*

   * does the dirty work in cow of a single block.  The parent block (if
   * supplied) is updated to point to the new cow copy.  The new buffer is marked
   * dirty and returned locked.  If you modify the block it needs to be marked
   * dirty again.

   *
   * search_start -- an allocation hint for the new block
   *

   * empty_size -- a hint that you plan on doing more cow.  This is the size in
   * bytes the allocator should try to find free next to the block it returns.
   * This is just a hint and may be ignored by the allocator.

   */

  static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,

  			     struct btrfs_root *root,
  			     struct extent_buffer *buf,
  			     struct extent_buffer *parent, int parent_slot,
  			     struct extent_buffer **cow_ret,

  			     u64 search_start, u64 empty_size)

  {

  	struct btrfs_disk_key disk_key;

  	struct extent_buffer *cow;

  	int level;

  	int last_ref = 0;

  	int unlock_orig = 0;

  	u64 parent_start;

  	if (*cow_ret == buf)
  		unlock_orig = 1;

  	btrfs_assert_tree_locked(buf);

  	WARN_ON(root->ref_cows && trans->transid !=
  		root->fs_info->running_transaction->transid);

  	WARN_ON(root->ref_cows && trans->transid != root->last_trans);

  	level = btrfs_header_level(buf);

  	if (level == 0)
  		btrfs_item_key(buf, &disk_key, 0);
  	else
  		btrfs_node_key(buf, &disk_key, 0);
  
  	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
  		if (parent)
  			parent_start = parent->start;
  		else
  			parent_start = 0;
  	} else
  		parent_start = 0;
  
  	cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
  				     root->root_key.objectid, &disk_key,
  				     level, search_start, empty_size);

  	if (IS_ERR(cow))
  		return PTR_ERR(cow);

  	/* cow is set to blocking by btrfs_init_new_buffer */

  	copy_extent_buffer(cow, buf, 0, 0, cow->len);

  	btrfs_set_header_bytenr(cow, cow->start);

  	btrfs_set_header_generation(cow, trans->transid);

  	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
  	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
  				     BTRFS_HEADER_FLAG_RELOC);
  	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
  		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
  	else
  		btrfs_set_header_owner(cow, root->root_key.objectid);

  	write_extent_buffer(cow, root->fs_info->fsid,
  			    (unsigned long)btrfs_header_fsid(cow),
  			    BTRFS_FSID_SIZE);

  	update_ref_for_cow(trans, root, buf, cow, &last_ref);

  	if (root->ref_cows)
  		btrfs_reloc_cow_block(trans, root, buf, cow);

  	if (buf == root->node) {

  		WARN_ON(parent && parent != buf);

  		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
  		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
  			parent_start = buf->start;
  		else
  			parent_start = 0;

  		extent_buffer_get(cow);

  		rcu_assign_pointer(root->node, cow);

  		btrfs_free_tree_block(trans, root, buf, parent_start,
  				      last_ref);

  		free_extent_buffer(buf);

  		add_root_to_dirty_list(root);

  	} else {

  		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
  			parent_start = parent->start;
  		else
  			parent_start = 0;
  
  		WARN_ON(trans->transid != btrfs_header_generation(parent));

  		btrfs_set_node_blockptr(parent, parent_slot,

  					cow->start);

  		btrfs_set_node_ptr_generation(parent, parent_slot,
  					      trans->transid);

  		btrfs_mark_buffer_dirty(parent);

  		btrfs_free_tree_block(trans, root, buf, parent_start,
  				      last_ref);

  	}

  	if (unlock_orig)
  		btrfs_tree_unlock(buf);

  	free_extent_buffer(buf);

  	btrfs_mark_buffer_dirty(cow);

  	*cow_ret = cow;

  	return 0;
  }

  static inline int should_cow_block(struct btrfs_trans_handle *trans,
  				   struct btrfs_root *root,
  				   struct extent_buffer *buf)
  {

  	/* ensure we can see the force_cow */
  	smp_rmb();
  
  	/*
  	 * We do not need to cow a block if
  	 * 1) this block is not created or changed in this transaction;
  	 * 2) this block does not belong to TREE_RELOC tree;
  	 * 3) the root is not forced COW.
  	 *
  	 * What is forced COW:
  	 *    when we create snapshot during commiting the transaction,
  	 *    after we've finished coping src root, we must COW the shared
  	 *    block to ensure the metadata consistency.
  	 */

  	if (btrfs_header_generation(buf) == trans->transid &&
  	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
  	    !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&

  	      btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
  	    !root->force_cow)

  		return 0;
  	return 1;
  }

  /*
   * cows a single block, see __btrfs_cow_block for the real work.
   * This version of it has extra checks so that a block isn't cow'd more than
   * once per transaction, as long as it hasn't been written yet
   */

  noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,

  		    struct btrfs_root *root, struct extent_buffer *buf,
  		    struct extent_buffer *parent, int parent_slot,

  		    struct extent_buffer **cow_ret)

  {
  	u64 search_start;

  	int ret;

  	if (trans->transaction != root->fs_info->running_transaction) {

  		printk(KERN_CRIT "trans %llu running %llu
  ",
  		       (unsigned long long)trans->transid,
  		       (unsigned long long)

  		       root->fs_info->running_transaction->transid);
  		WARN_ON(1);
  	}
  	if (trans->transid != root->fs_info->generation) {

  		printk(KERN_CRIT "trans %llu running %llu
  ",
  		       (unsigned long long)trans->transid,
  		       (unsigned long long)root->fs_info->generation);

  		WARN_ON(1);
  	}

  	if (!should_cow_block(trans, root, buf)) {

  		*cow_ret = buf;
  		return 0;
  	}

  	search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);

  
  	if (parent)
  		btrfs_set_lock_blocking(parent);
  	btrfs_set_lock_blocking(buf);

  	ret = __btrfs_cow_block(trans, root, buf, parent,

  				 parent_slot, cow_ret, search_start, 0);

  
  	trace_btrfs_cow_block(root, buf, *cow_ret);

  	return ret;

  }

  /*
   * helper function for defrag to decide if two blocks pointed to by a
   * node are actually close by
   */

  static int close_blocks(u64 blocknr, u64 other, u32 blocksize)

  {

  	if (blocknr < other && other - (blocknr + blocksize) < 32768)

  		return 1;

  	if (blocknr > other && blocknr - (other + blocksize) < 32768)

  		return 1;
  	return 0;
  }

  /*
   * compare two keys in a memcmp fashion
   */
  static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
  {
  	struct btrfs_key k1;
  
  	btrfs_disk_key_to_cpu(&k1, disk);

  	return btrfs_comp_cpu_keys(&k1, k2);

  }

  /*
   * same as comp_keys only with two btrfs_key's
   */

  int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)

  {
  	if (k1->objectid > k2->objectid)
  		return 1;
  	if (k1->objectid < k2->objectid)
  		return -1;
  	if (k1->type > k2->type)
  		return 1;
  	if (k1->type < k2->type)
  		return -1;
  	if (k1->offset > k2->offset)
  		return 1;
  	if (k1->offset < k2->offset)
  		return -1;
  	return 0;
  }

  /*
   * this is used by the defrag code to go through all the
   * leaves pointed to by a node and reallocate them so that
   * disk order is close to key order
   */

  int btrfs_realloc_node(struct btrfs_trans_handle *trans,

  		       struct btrfs_root *root, struct extent_buffer *parent,

  		       int start_slot, int cache_only, u64 *last_ret,
  		       struct btrfs_key *progress)

  {

  	struct extent_buffer *cur;

  	u64 blocknr;

  	u64 gen;

  	u64 search_start = *last_ret;
  	u64 last_block = 0;

  	u64 other;
  	u32 parent_nritems;

  	int end_slot;
  	int i;
  	int err = 0;

  	int parent_level;

  	int uptodate;
  	u32 blocksize;

  	int progress_passed = 0;
  	struct btrfs_disk_key disk_key;

  	parent_level = btrfs_header_level(parent);
  	if (cache_only && parent_level != 1)
  		return 0;

  	if (trans->transaction != root->fs_info->running_transaction)

  		WARN_ON(1);

  	if (trans->transid != root->fs_info->generation)

  		WARN_ON(1);

  	parent_nritems = btrfs_header_nritems(parent);

  	blocksize = btrfs_level_size(root, parent_level - 1);

  	end_slot = parent_nritems;
  
  	if (parent_nritems == 1)
  		return 0;

  	btrfs_set_lock_blocking(parent);

  	for (i = start_slot; i < end_slot; i++) {
  		int close = 1;

  		btrfs_node_key(parent, &disk_key, i);
  		if (!progress_passed && comp_keys(&disk_key, progress) < 0)
  			continue;
  
  		progress_passed = 1;

  		blocknr = btrfs_node_blockptr(parent, i);

  		gen = btrfs_node_ptr_generation(parent, i);

  		if (last_block == 0)
  			last_block = blocknr;

  		if (i > 0) {

  			other = btrfs_node_blockptr(parent, i - 1);
  			close = close_blocks(blocknr, other, blocksize);

  		}

  		if (!close && i < end_slot - 2) {

  			other = btrfs_node_blockptr(parent, i + 1);
  			close = close_blocks(blocknr, other, blocksize);

  		}

  		if (close) {
  			last_block = blocknr;

  			continue;

  		}

  		cur = btrfs_find_tree_block(root, blocknr, blocksize);
  		if (cur)

  			uptodate = btrfs_buffer_uptodate(cur, gen);

  		else
  			uptodate = 0;

  		if (!cur || !uptodate) {

  			if (cache_only) {

  				free_extent_buffer(cur);

  				continue;
  			}

  			if (!cur) {
  				cur = read_tree_block(root, blocknr,

  							 blocksize, gen);

  				if (!cur)
  					return -EIO;

  			} else if (!uptodate) {

  				btrfs_read_buffer(cur, gen);

  			}

  		}

  		if (search_start == 0)

  			search_start = last_block;

  		btrfs_tree_lock(cur);

  		btrfs_set_lock_blocking(cur);

  		err = __btrfs_cow_block(trans, root, cur, parent, i,

  					&cur, search_start,

  					min(16 * blocksize,

  					    (end_slot - i) * blocksize));

  		if (err) {

  			btrfs_tree_unlock(cur);

  			free_extent_buffer(cur);

  			break;

  		}

  		search_start = cur->start;
  		last_block = cur->start;

  		*last_ret = search_start;

  		btrfs_tree_unlock(cur);
  		free_extent_buffer(cur);

  	}
  	return err;
  }

  /*
   * The leaf data grows from end-to-front in the node.
   * this returns the address of the start of the last item,
   * which is the stop of the leaf data stack
   */

  static inline unsigned int leaf_data_end(struct btrfs_root *root,

  					 struct extent_buffer *leaf)

  {

  	u32 nr = btrfs_header_nritems(leaf);

  	if (nr == 0)

  		return BTRFS_LEAF_DATA_SIZE(root);

  	return btrfs_item_offset_nr(leaf, nr - 1);

  }

  /*

   * search for key in the extent_buffer.  The items start at offset p,
   * and they are item_size apart.  There are 'max' items in p.
   *

   * the slot in the array is returned via slot, and it points to
   * the place where you would insert key if it is not found in
   * the array.
   *
   * slot may point to max if the key is bigger than all of the keys
   */

  static noinline int generic_bin_search(struct extent_buffer *eb,
  				       unsigned long p,
  				       int item_size, struct btrfs_key *key,
  				       int max, int *slot)

  {
  	int low = 0;
  	int high = max;
  	int mid;
  	int ret;

  	struct btrfs_disk_key *tmp = NULL;

  	struct btrfs_disk_key unaligned;
  	unsigned long offset;

  	char *kaddr = NULL;
  	unsigned long map_start = 0;
  	unsigned long map_len = 0;

  	int err;

  	while (low < high) {

  		mid = (low + high) / 2;

  		offset = p + mid * item_size;

  		if (!kaddr || offset < map_start ||

  		    (offset + sizeof(struct btrfs_disk_key)) >
  		    map_start + map_len) {

  
  			err = map_private_extent_buffer(eb, offset,

  						sizeof(struct btrfs_disk_key),

  						&kaddr, &map_start, &map_len);

  
  			if (!err) {
  				tmp = (struct btrfs_disk_key *)(kaddr + offset -
  							map_start);
  			} else {
  				read_extent_buffer(eb, &unaligned,
  						   offset, sizeof(unaligned));
  				tmp = &unaligned;
  			}

  		} else {
  			tmp = (struct btrfs_disk_key *)(kaddr + offset -
  							map_start);
  		}

  		ret = comp_keys(tmp, key);
  
  		if (ret < 0)
  			low = mid + 1;
  		else if (ret > 0)
  			high = mid;
  		else {
  			*slot = mid;
  			return 0;
  		}
  	}
  	*slot = low;
  	return 1;
  }

  /*
   * simple bin_search frontend that does the right thing for
   * leaves vs nodes
   */

  static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
  		      int level, int *slot)

  {

  	if (level == 0) {
  		return generic_bin_search(eb,
  					  offsetof(struct btrfs_leaf, items),

  					  sizeof(struct btrfs_item),

  					  key, btrfs_header_nritems(eb),

  					  slot);

  	} else {

  		return generic_bin_search(eb,
  					  offsetof(struct btrfs_node, ptrs),

  					  sizeof(struct btrfs_key_ptr),

  					  key, btrfs_header_nritems(eb),

  					  slot);

  	}
  	return -1;
  }

  int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
  		     int level, int *slot)
  {
  	return bin_search(eb, key, level, slot);
  }

  static void root_add_used(struct btrfs_root *root, u32 size)
  {
  	spin_lock(&root->accounting_lock);
  	btrfs_set_root_used(&root->root_item,
  			    btrfs_root_used(&root->root_item) + size);
  	spin_unlock(&root->accounting_lock);
  }
  
  static void root_sub_used(struct btrfs_root *root, u32 size)
  {
  	spin_lock(&root->accounting_lock);
  	btrfs_set_root_used(&root->root_item,
  			    btrfs_root_used(&root->root_item) - size);
  	spin_unlock(&root->accounting_lock);
  }

  /* given a node and slot number, this reads the blocks it points to.  The
   * extent buffer is returned with a reference taken (but unlocked).
   * NULL is returned on error.
   */

  static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,

  				   struct extent_buffer *parent, int slot)

  {

  	int level = btrfs_header_level(parent);

  	if (slot < 0)
  		return NULL;

  	if (slot >= btrfs_header_nritems(parent))

  		return NULL;

  
  	BUG_ON(level == 0);

  	return read_tree_block(root, btrfs_node_blockptr(parent, slot),

  		       btrfs_level_size(root, level - 1),
  		       btrfs_node_ptr_generation(parent, slot));

  }

  /*
   * node level balancing, used to make sure nodes are in proper order for
   * item deletion.  We balance from the top down, so we have to make sure
   * that a deletion won't leave an node completely empty later on.
   */

  static noinline int balance_level(struct btrfs_trans_handle *trans,

  			 struct btrfs_root *root,
  			 struct btrfs_path *path, int level)

  {

  	struct extent_buffer *right = NULL;
  	struct extent_buffer *mid;
  	struct extent_buffer *left = NULL;
  	struct extent_buffer *parent = NULL;

  	int ret = 0;
  	int wret;
  	int pslot;

  	int orig_slot = path->slots[level];

  	u64 orig_ptr;

  
  	if (level == 0)
  		return 0;

  	mid = path->nodes[level];

  	WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
  		path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);

  	WARN_ON(btrfs_header_generation(mid) != trans->transid);

  	orig_ptr = btrfs_node_blockptr(mid, orig_slot);

  	if (level < BTRFS_MAX_LEVEL - 1) {

  		parent = path->nodes[level + 1];

  		pslot = path->slots[level + 1];
  	}

  	/*
  	 * deal with the case where there is only one pointer in the root
  	 * by promoting the node below to a root
  	 */

  	if (!parent) {
  		struct extent_buffer *child;

  		if (btrfs_header_nritems(mid) != 1)

  			return 0;
  
  		/* promote the child to a root */

  		child = read_node_slot(root, mid, 0);

  		BUG_ON(!child);

  		btrfs_tree_lock(child);

  		btrfs_set_lock_blocking(child);

  		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);

  		if (ret) {
  			btrfs_tree_unlock(child);
  			free_extent_buffer(child);
  			goto enospc;
  		}

  		rcu_assign_pointer(root->node, child);

  		add_root_to_dirty_list(root);

  		btrfs_tree_unlock(child);

  		path->locks[level] = 0;

  		path->nodes[level] = NULL;

  		clean_tree_block(trans, root, mid);

  		btrfs_tree_unlock(mid);

  		/* once for the path */

  		free_extent_buffer(mid);

  
  		root_sub_used(root, mid->len);
  		btrfs_free_tree_block(trans, root, mid, 0, 1);

  		/* once for the root ptr */

  		free_extent_buffer(mid);

  		return 0;

  	}

  	if (btrfs_header_nritems(mid) >

  	    BTRFS_NODEPTRS_PER_BLOCK(root) / 4)

  		return 0;

  	btrfs_header_nritems(mid);

  	left = read_node_slot(root, parent, pslot - 1);
  	if (left) {

  		btrfs_tree_lock(left);

  		btrfs_set_lock_blocking(left);

  		wret = btrfs_cow_block(trans, root, left,

  				       parent, pslot - 1, &left);

  		if (wret) {
  			ret = wret;
  			goto enospc;
  		}

  	}

  	right = read_node_slot(root, parent, pslot + 1);
  	if (right) {

  		btrfs_tree_lock(right);

  		btrfs_set_lock_blocking(right);

  		wret = btrfs_cow_block(trans, root, right,

  				       parent, pslot + 1, &right);

  		if (wret) {
  			ret = wret;
  			goto enospc;
  		}
  	}
  
  	/* first, try to make some room in the middle buffer */

  	if (left) {
  		orig_slot += btrfs_header_nritems(left);

  		wret = push_node_left(trans, root, left, mid, 1);

  		if (wret < 0)
  			ret = wret;

  		btrfs_header_nritems(mid);

  	}

  
  	/*
  	 * then try to empty the right most buffer into the middle
  	 */

  	if (right) {

  		wret = push_node_left(trans, root, mid, right, 1);

  		if (wret < 0 && wret != -ENOSPC)

  			ret = wret;

  		if (btrfs_header_nritems(right) == 0) {

  			clean_tree_block(trans, root, right);

  			btrfs_tree_unlock(right);

  			wret = del_ptr(trans, root, path, level + 1, pslot +
  				       1);

  			if (wret)
  				ret = wret;

  			root_sub_used(root, right->len);
  			btrfs_free_tree_block(trans, root, right, 0, 1);
  			free_extent_buffer(right);
  			right = NULL;

  		} else {

  			struct btrfs_disk_key right_key;
  			btrfs_node_key(right, &right_key, 0);
  			btrfs_set_node_key(parent, &right_key, pslot + 1);
  			btrfs_mark_buffer_dirty(parent);

  		}
  	}

  	if (btrfs_header_nritems(mid) == 1) {

  		/*
  		 * we're not allowed to leave a node with one item in the
  		 * tree during a delete.  A deletion from lower in the tree
  		 * could try to delete the only pointer in this node.
  		 * So, pull some keys from the left.
  		 * There has to be a left pointer at this point because
  		 * otherwise we would have pulled some pointers from the
  		 * right
  		 */

  		BUG_ON(!left);
  		wret = balance_node_right(trans, root, mid, left);

  		if (wret < 0) {

  			ret = wret;

  			goto enospc;
  		}

  		if (wret == 1) {
  			wret = push_node_left(trans, root, left, mid, 1);
  			if (wret < 0)
  				ret = wret;
  		}

  		BUG_ON(wret == 1);
  	}

  	if (btrfs_header_nritems(mid) == 0) {

  		clean_tree_block(trans, root, mid);

  		btrfs_tree_unlock(mid);

  		wret = del_ptr(trans, root, path, level + 1, pslot);

  		if (wret)
  			ret = wret;

  		root_sub_used(root, mid->len);
  		btrfs_free_tree_block(trans, root, mid, 0, 1);
  		free_extent_buffer(mid);
  		mid = NULL;

  	} else {
  		/* update the parent key to reflect our changes */

  		struct btrfs_disk_key mid_key;
  		btrfs_node_key(mid, &mid_key, 0);
  		btrfs_set_node_key(parent, &mid_key, pslot);
  		btrfs_mark_buffer_dirty(parent);

  	}

  	/* update the path */

  	if (left) {
  		if (btrfs_header_nritems(left) > orig_slot) {
  			extent_buffer_get(left);

  			/* left was locked after cow */

  			path->nodes[level] = left;

  			path->slots[level + 1] -= 1;
  			path->slots[level] = orig_slot;

  			if (mid) {
  				btrfs_tree_unlock(mid);

  				free_extent_buffer(mid);

  			}

  		} else {

  			orig_slot -= btrfs_header_nritems(left);

  			path->slots[level] = orig_slot;
  		}
  	}

  	/* double check we haven't messed things up */

  	if (orig_ptr !=

  	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))

  		BUG();

  enospc:

  	if (right) {
  		btrfs_tree_unlock(right);

  		free_extent_buffer(right);

  	}
  	if (left) {
  		if (path->nodes[level] != left)
  			btrfs_tree_unlock(left);

  		free_extent_buffer(left);

  	}

  	return ret;
  }

  /* Node balancing for insertion.  Here we only split or push nodes around
   * when they are completely full.  This is also done top down, so we
   * have to be pessimistic.
   */

  static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,

  					  struct btrfs_root *root,
  					  struct btrfs_path *path, int level)

  {

  	struct extent_buffer *right = NULL;
  	struct extent_buffer *mid;
  	struct extent_buffer *left = NULL;
  	struct extent_buffer *parent = NULL;

  	int ret = 0;
  	int wret;
  	int pslot;
  	int orig_slot = path->slots[level];

  
  	if (level == 0)
  		return 1;

  	mid = path->nodes[level];

  	WARN_ON(btrfs_header_generation(mid) != trans->transid);

  	if (level < BTRFS_MAX_LEVEL - 1) {

  		parent = path->nodes[level + 1];

  		pslot = path->slots[level + 1];
  	}

  	if (!parent)

  		return 1;

  	left = read_node_slot(root, parent, pslot - 1);

  
  	/* first, try to make some room in the middle buffer */

  	if (left) {

  		u32 left_nr;

  
  		btrfs_tree_lock(left);

  		btrfs_set_lock_blocking(left);

  		left_nr = btrfs_header_nritems(left);

  		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
  			wret = 1;
  		} else {

  			ret = btrfs_cow_block(trans, root, left, parent,

  					      pslot - 1, &left);

  			if (ret)
  				wret = 1;
  			else {

  				wret = push_node_left(trans, root,

  						      left, mid, 0);

  			}

  		}

  		if (wret < 0)
  			ret = wret;
  		if (wret == 0) {

  			struct btrfs_disk_key disk_key;

  			orig_slot += left_nr;

  			btrfs_node_key(mid, &disk_key, 0);
  			btrfs_set_node_key(parent, &disk_key, pslot);
  			btrfs_mark_buffer_dirty(parent);
  			if (btrfs_header_nritems(left) > orig_slot) {
  				path->nodes[level] = left;

  				path->slots[level + 1] -= 1;
  				path->slots[level] = orig_slot;

  				btrfs_tree_unlock(mid);

  				free_extent_buffer(mid);

  			} else {
  				orig_slot -=

  					btrfs_header_nritems(left);

  				path->slots[level] = orig_slot;

  				btrfs_tree_unlock(left);

  				free_extent_buffer(left);

  			}

  			return 0;
  		}

  		btrfs_tree_unlock(left);

  		free_extent_buffer(left);

  	}

  	right = read_node_slot(root, parent, pslot + 1);

  
  	/*
  	 * then try to empty the right most buffer into the middle
  	 */

  	if (right) {

  		u32 right_nr;

  		btrfs_tree_lock(right);

  		btrfs_set_lock_blocking(right);

  		right_nr = btrfs_header_nritems(right);

  		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
  			wret = 1;
  		} else {

  			ret = btrfs_cow_block(trans, root, right,
  					      parent, pslot + 1,

  					      &right);

  			if (ret)
  				wret = 1;
  			else {

  				wret = balance_node_right(trans, root,

  							  right, mid);

  			}

  		}

  		if (wret < 0)
  			ret = wret;
  		if (wret == 0) {

  			struct btrfs_disk_key disk_key;
  
  			btrfs_node_key(right, &disk_key, 0);
  			btrfs_set_node_key(parent, &disk_key, pslot + 1);
  			btrfs_mark_buffer_dirty(parent);
  
  			if (btrfs_header_nritems(mid) <= orig_slot) {
  				path->nodes[level] = right;

  				path->slots[level + 1] += 1;
  				path->slots[level] = orig_slot -

  					btrfs_header_nritems(mid);

  				btrfs_tree_unlock(mid);

  				free_extent_buffer(mid);

  			} else {

  				btrfs_tree_unlock(right);

  				free_extent_buffer(right);

  			}

  			return 0;
  		}

  		btrfs_tree_unlock(right);

  		free_extent_buffer(right);

  	}

  	return 1;
  }

  /*

   * readahead one full node of leaves, finding things that are close
   * to the block in 'slot', and triggering ra on them.

   */

  static void reada_for_search(struct btrfs_root *root,
  			     struct btrfs_path *path,
  			     int level, int slot, u64 objectid)

  {

  	struct extent_buffer *node;

  	struct btrfs_disk_key disk_key;

  	u32 nritems;

  	u64 search;

  	u64 target;

  	u64 nread = 0;

  	u64 gen;

  	int direction = path->reada;

  	struct extent_buffer *eb;

  	u32 nr;
  	u32 blocksize;
  	u32 nscan = 0;

  	if (level != 1)

  		return;
  
  	if (!path->nodes[level])

  		return;

  	node = path->nodes[level];

  	search = btrfs_node_blockptr(node, slot);

  	blocksize = btrfs_level_size(root, level - 1);
  	eb = btrfs_find_tree_block(root, search, blocksize);

  	if (eb) {
  		free_extent_buffer(eb);

  		return;
  	}

  	target = search;

  	nritems = btrfs_header_nritems(node);

  	nr = slot;

  	while (1) {

  		if (direction < 0) {
  			if (nr == 0)
  				break;
  			nr--;
  		} else if (direction > 0) {
  			nr++;
  			if (nr >= nritems)
  				break;

  		}

  		if (path->reada < 0 && objectid) {
  			btrfs_node_key(node, &disk_key, nr);
  			if (btrfs_disk_key_objectid(&disk_key) != objectid)
  				break;
  		}

  		search = btrfs_node_blockptr(node, nr);

  		if ((search <= target && target - search <= 65536) ||
  		    (search > target && search - target <= 65536)) {

  			gen = btrfs_node_ptr_generation(node, nr);

  			readahead_tree_block(root, search, blocksize, gen);

  			nread += blocksize;
  		}
  		nscan++;

  		if ((nread > 65536 || nscan > 32))

  			break;

  	}
  }

  /*

   * returns -EAGAIN if it had to drop the path, or zero if everything was in
   * cache
   */
  static noinline int reada_for_balance(struct btrfs_root *root,
  				      struct btrfs_path *path, int level)
  {
  	int slot;
  	int nritems;
  	struct extent_buffer *parent;
  	struct extent_buffer *eb;
  	u64 gen;
  	u64 block1 = 0;
  	u64 block2 = 0;
  	int ret = 0;
  	int blocksize;

  	parent = path->nodes[level + 1];

  	if (!parent)
  		return 0;
  
  	nritems = btrfs_header_nritems(parent);

  	slot = path->slots[level + 1];

  	blocksize = btrfs_level_size(root, level);
  
  	if (slot > 0) {
  		block1 = btrfs_node_blockptr(parent, slot - 1);
  		gen = btrfs_node_ptr_generation(parent, slot - 1);
  		eb = btrfs_find_tree_block(root, block1, blocksize);
  		if (eb && btrfs_buffer_uptodate(eb, gen))
  			block1 = 0;
  		free_extent_buffer(eb);
  	}

  	if (slot + 1 < nritems) {

  		block2 = btrfs_node_blockptr(parent, slot + 1);
  		gen = btrfs_node_ptr_generation(parent, slot + 1);
  		eb = btrfs_find_tree_block(root, block2, blocksize);
  		if (eb && btrfs_buffer_uptodate(eb, gen))
  			block2 = 0;
  		free_extent_buffer(eb);
  	}
  	if (block1 || block2) {
  		ret = -EAGAIN;

  
  		/* release the whole path */

  		btrfs_release_path(path);

  
  		/* read the blocks */

  		if (block1)
  			readahead_tree_block(root, block1, blocksize, 0);
  		if (block2)
  			readahead_tree_block(root, block2, blocksize, 0);
  
  		if (block1) {
  			eb = read_tree_block(root, block1, blocksize, 0);
  			free_extent_buffer(eb);
  		}

  		if (block2) {

  			eb = read_tree_block(root, block2, blocksize, 0);
  			free_extent_buffer(eb);
  		}
  	}
  	return ret;
  }
  
  
  /*

   * when we walk down the tree, it is usually safe to unlock the higher layers
   * in the tree.  The exceptions are when our path goes through slot 0, because
   * operations on the tree might require changing key pointers higher up in the
   * tree.

   *

   * callers might also have set path->keep_locks, which tells this code to keep
   * the lock if the path points to the last slot in the block.  This is part of
   * walking through the tree, and selecting the next slot in the higher block.

   *

   * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
   * if lowest_unlock is 1, level 0 won't be unlocked

   */

  static noinline void unlock_up(struct btrfs_path *path, int level,
  			       int lowest_unlock)

  {
  	int i;
  	int skip_level = level;

  	int no_skips = 0;

  	struct extent_buffer *t;
  
  	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  		if (!path->nodes[i])
  			break;
  		if (!path->locks[i])
  			break;

  		if (!no_skips && path->slots[i] == 0) {

  			skip_level = i + 1;
  			continue;
  		}

  		if (!no_skips && path->keep_locks) {

  			u32 nritems;
  			t = path->nodes[i];
  			nritems = btrfs_header_nritems(t);

  			if (nritems < 1 || path->slots[i] >= nritems - 1) {

  				skip_level = i + 1;
  				continue;
  			}
  		}

  		if (skip_level < i && i >= lowest_unlock)
  			no_skips = 1;

  		t = path->nodes[i];
  		if (i >= lowest_unlock && i > skip_level && path->locks[i]) {

  			btrfs_tree_unlock_rw(t, path->locks[i]);

  			path->locks[i] = 0;
  		}
  	}
  }

  /*

   * This releases any locks held in the path starting at level and
   * going all the way up to the root.
   *
   * btrfs_search_slot will keep the lock held on higher nodes in a few
   * corner cases, such as COW of the block at slot zero in the node.  This
   * ignores those rules, and it should only be called when there are no
   * more updates to be done higher up in the tree.
   */
  noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
  {
  	int i;

  	if (path->keep_locks)

  		return;
  
  	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  		if (!path->nodes[i])

  			continue;

  		if (!path->locks[i])

  			continue;

  		btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);

  		path->locks[i] = 0;
  	}
  }
  
  /*

   * helper function for btrfs_search_slot.  The goal is to find a block
   * in cache without setting the path to blocking.  If we find the block
   * we return zero and the path is unchanged.
   *
   * If we can't find the block, we set the path blocking and do some
   * reada.  -EAGAIN is returned and the search must be repeated.
   */
  static int
  read_block_for_search(struct btrfs_trans_handle *trans,
  		       struct btrfs_root *root, struct btrfs_path *p,
  		       struct extent_buffer **eb_ret, int level, int slot,
  		       struct btrfs_key *key)
  {
  	u64 blocknr;
  	u64 gen;
  	u32 blocksize;
  	struct extent_buffer *b = *eb_ret;
  	struct extent_buffer *tmp;

  	int ret;

  
  	blocknr = btrfs_node_blockptr(b, slot);
  	gen = btrfs_node_ptr_generation(b, slot);
  	blocksize = btrfs_level_size(root, level - 1);
  
  	tmp = btrfs_find_tree_block(root, blocknr, blocksize);

  	if (tmp) {
  		if (btrfs_buffer_uptodate(tmp, 0)) {
  			if (btrfs_buffer_uptodate(tmp, gen)) {
  				/*
  				 * we found an up to date block without
  				 * sleeping, return
  				 * right away
  				 */
  				*eb_ret = tmp;
  				return 0;
  			}
  			/* the pages were up to date, but we failed
  			 * the generation number check.  Do a full
  			 * read for the generation number that is correct.
  			 * We must do this without dropping locks so
  			 * we can trust our generation number
  			 */
  			free_extent_buffer(tmp);

  			btrfs_set_path_blocking(p);

  			tmp = read_tree_block(root, blocknr, blocksize, gen);
  			if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
  				*eb_ret = tmp;
  				return 0;
  			}
  			free_extent_buffer(tmp);

  			btrfs_release_path(p);

  			return -EIO;
  		}

  	}
  
  	/*
  	 * reduce lock contention at high levels
  	 * of the btree by dropping locks before

  	 * we read.  Don't release the lock on the current
  	 * level because we need to walk this node to figure
  	 * out which blocks to read.

  	 */

  	btrfs_unlock_up_safe(p, level + 1);
  	btrfs_set_path_blocking(p);

  	free_extent_buffer(tmp);

  	if (p->reada)
  		reada_for_search(root, p, level, slot, key->objectid);

  	btrfs_release_path(p);

  
  	ret = -EAGAIN;

  	tmp = read_tree_block(root, blocknr, blocksize, 0);

  	if (tmp) {
  		/*
  		 * If the read above didn't mark this buffer up to date,
  		 * it will never end up being up to date.  Set ret to EIO now
  		 * and give up so that our caller doesn't loop forever
  		 * on our EAGAINs.
  		 */
  		if (!btrfs_buffer_uptodate(tmp, 0))
  			ret = -EIO;

  		free_extent_buffer(tmp);

  	}
  	return ret;

  }
  
  /*
   * helper function for btrfs_search_slot.  This does all of the checks
   * for node-level blocks and does any balancing required based on
   * the ins_len.
   *
   * If no extra work was required, zero is returned.  If we had to
   * drop the path, -EAGAIN is returned and btrfs_search_slot must
   * start over
   */
  static int
  setup_nodes_for_search(struct btrfs_trans_handle *trans,
  		       struct btrfs_root *root, struct btrfs_path *p,

  		       struct extent_buffer *b, int level, int ins_len,
  		       int *write_lock_level)

  {
  	int ret;
  	if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
  	    BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
  		int sret;

  		if (*write_lock_level < level + 1) {
  			*write_lock_level = level + 1;
  			btrfs_release_path(p);
  			goto again;
  		}

  		sret = reada_for_balance(root, p, level);
  		if (sret)
  			goto again;
  
  		btrfs_set_path_blocking(p);
  		sret = split_node(trans, root, p, level);

  		btrfs_clear_path_blocking(p, NULL, 0);

  
  		BUG_ON(sret > 0);
  		if (sret) {
  			ret = sret;
  			goto done;
  		}
  		b = p->nodes[level];
  	} else if (ins_len < 0 && btrfs_header_nritems(b) <

  		   BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {

  		int sret;

  		if (*write_lock_level < level + 1) {
  			*write_lock_level = level + 1;
  			btrfs_release_path(p);
  			goto again;
  		}

  		sret = reada_for_balance(root, p, level);
  		if (sret)
  			goto again;
  
  		btrfs_set_path_blocking(p);
  		sret = balance_level(trans, root, p, level);

  		btrfs_clear_path_blocking(p, NULL, 0);

  
  		if (sret) {
  			ret = sret;
  			goto done;
  		}
  		b = p->nodes[level];
  		if (!b) {

  			btrfs_release_path(p);

  			goto again;
  		}
  		BUG_ON(btrfs_header_nritems(b) == 1);
  	}
  	return 0;
  
  again:
  	ret = -EAGAIN;
  done:
  	return ret;
  }
  
  /*

   * look for key in the tree.  path is filled in with nodes along the way
   * if key is found, we return zero and you can find the item in the leaf
   * level of the path (level 0)
   *
   * If the key isn't found, the path points to the slot where it should

   * be inserted, and 1 is returned.  If there are other errors during the
   * search a negative error number is returned.

   *
   * if ins_len > 0, nodes and leaves will be split as we walk down the
   * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
   * possible)

   */

  int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
  		      *root, struct btrfs_key *key, struct btrfs_path *p, int
  		      ins_len, int cow)