// if root directory is empty - we set default - Yura's - hash and
// warn about it
// FIXME: we look for only one name in a directory. If tea and yura
// bith have the same value - we ask user to send report to the
// mailing list
__u32 find_hash_out (struct super_block * s)
{
    int retval;
    struct inode * inode;
    struct cpu_key key;
    INITIALIZE_PATH (path);
    struct reiserfs_dir_entry de;
    __u32 hash = DEFAULT_HASH;

    inode = s->s_root->d_inode;

    do { // Some serious "goto"-hater was there ;)
	u32 teahash, r5hash, yurahash;

	make_cpu_key (&key, inode, ~0, TYPE_DIRENTRY, 3);
	retval = search_by_entry_key (s, &key, &path, &de);
	if (retval == IO_ERROR) {
	    pathrelse (&path);
	    return UNSET_HASH ;
	}
	if (retval == NAME_NOT_FOUND)
	    de.de_entry_num --;
	set_de_name_and_namelen (&de);
	if (deh_offset( &(de.de_deh[de.de_entry_num]) ) == DOT_DOT_OFFSET) {
	    /* allow override in this case */
	    if (reiserfs_rupasov_hash(s)) {
		hash = YURA_HASH ;
	    }
	    reiserfs_warning("reiserfs: FS seems to be empty, autodetect "
	                     "is using the default hash\n");
	    break;
	}
	r5hash=GET_HASH_VALUE (r5_hash (de.de_name, de.de_namelen));
	teahash=GET_HASH_VALUE (keyed_hash (de.de_name, de.de_namelen));
	yurahash=GET_HASH_VALUE (yura_hash (de.de_name, de.de_namelen));
	if ( ( (teahash == r5hash) && (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num]))) == r5hash) ) ||
	     ( (teahash == yurahash) && (yurahash == GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])))) ) ||
	     ( (r5hash == yurahash) && (yurahash == GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])))) ) ) {
	    reiserfs_warning("reiserfs: Unable to automatically detect hash"
		"function for device %s\n"
		"please mount with -o hash={tea,rupasov,r5}\n", kdevname (s->s_dev));
	    hash = UNSET_HASH;
	    break;
	}
	if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == yurahash)
	    hash = YURA_HASH;
	else if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == teahash)
	    hash = TEA_HASH;
	else if (GET_HASH_VALUE( deh_offset(&(de.de_deh[de.de_entry_num])) ) == r5hash)
	    hash = R5_HASH;
	else {
	    reiserfs_warning("reiserfs: Unrecognised hash function for "
			     "device %s\n", kdevname (s->s_dev));
	    hash = UNSET_HASH;
	}
    } while (0);

    pathrelse (&path);
    return hash;
}

/*
** looks up the dentry of the parent directory for child.
** taken from ext2_get_parent
*/
struct dentry *reiserfs_get_parent(struct dentry *child)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);
	struct inode *dir = child->d_inode;

	if (dir->i_nlink == 0) {
		return ERR_PTR(-ENOENT);
	}
	de.de_gen_number_bit_string = NULL;

	reiserfs_write_lock(dir->i_sb);
	retval = reiserfs_find_entry(dir, "..", 2, &path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval != NAME_FOUND) {
		reiserfs_write_unlock(dir->i_sb);
		return ERR_PTR(-ENOENT);
	}
	inode = reiserfs_iget(dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
	reiserfs_write_unlock(dir->i_sb);

	return d_obtain_alias(inode);
}

/* 
** looks up the dentry of the parent directory for child.
** taken from ext2_get_parent
*/
struct dentry *reiserfs_get_parent(struct dentry *child)
{
    int retval;
    struct inode * inode = NULL;
    struct reiserfs_dir_entry de;
    INITIALIZE_PATH (path_to_entry);
    struct dentry *parent;
    struct inode *dir = child->d_inode ;


    if (dir->i_nlink == 0) {
	return ERR_PTR(-ENOENT);
    }
    de.de_gen_number_bit_string = NULL;

    reiserfs_write_lock(dir->i_sb);
    retval = reiserfs_find_entry (dir, "..", 2, &path_to_entry, &de);
    pathrelse (&path_to_entry);
    if (retval != NAME_FOUND) {
	reiserfs_write_unlock(dir->i_sb);
	return ERR_PTR(-ENOENT);
    }
    inode = reiserfs_iget (dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
    reiserfs_write_unlock(dir->i_sb);

    if (!inode || IS_ERR(inode)) {
	return ERR_PTR(-EACCES);
    }
    parent = d_alloc_anon(inode);
    if (!parent) {
	iput(inode);
	parent = ERR_PTR(-ENOMEM);
    }
    return parent;
}

/* add new name into a directory. If it exists in a directory - do
   nothing */
int reiserfs_add_entry (reiserfs_filsys_t fs, struct key * dir, char * name,
			 struct key * key, int fsck_need)
{
    struct item_head entry_ih = {{0,}, };
    char * entry;
    int retval;
    INITIALIZE_PATH(path);
    int gen_counter;
    int item_len;
    __u32 hash;

    if (reiserfs_find_entry (fs, dir, name, &gen_counter))
	return 0;

    /* compose entry key to look for its place in the tree */
    entry_ih.ih_key.k_dir_id = cpu_to_le32 (dir->k_dir_id);
    entry_ih.ih_key.k_objectid = cpu_to_le32 (dir->k_objectid);
    hash = hash_value (fs, name) + gen_counter;
    if (!strcmp (name, "."))
	hash = DOT_OFFSET;
    if (!strcmp (name, ".."))
	hash = DOT_DOT_OFFSET;
    set_type_and_offset (KEY_FORMAT_1, &(entry_ih.ih_key),
			 hash, TYPE_DIRENTRY);
    set_ih_key_format (&entry_ih, KEY_FORMAT_1);
    set_entry_count (&entry_ih, 1);
    if (SB_VERSION (fs) == REISERFS_VERSION_2)
	item_len = DEH_SIZE + ROUND_UP (strlen (name));
    else
	item_len = DEH_SIZE + strlen (name);
    set_ih_item_len (&entry_ih, item_len);

    /* fsck may need to insert item which was not reached yet */
    set_ih_fsck_need( &entry_ih, fsck_need );

    entry = make_entry (0, name, key, get_offset (&(entry_ih.ih_key)));

    retval = _search_by_entry_key (fs, &(entry_ih.ih_key), &path);
    switch (retval) {
    case POSITION_NOT_FOUND:
	reiserfs_paste_into_item (fs, &path, entry, item_len);
	break;

    case DIRECTORY_NOT_FOUND:
        set_deh_location( (struct reiserfs_de_head *)entry, DEH_SIZE );
	reiserfs_insert_item (fs, &path, &entry_ih, entry);
	break;

    default:
	reiserfs_panic ("reiserfs_add_entry: looking for %k (inserting name \"%s\") "
			"search_by_entry_key returned %d",
			&(entry_ih.ih_key), name, retval);
    }

    freemem (entry);
    return item_len;
}

static struct dentry *reiserfs_lookup(struct inode *dir, struct dentry *dentry,
				      struct nameidata *nd)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);

	if (REISERFS_MAX_NAME(dir->i_sb->s_blocksize) < dentry->d_name.len)
		return ERR_PTR(-ENAMETOOLONG);

	reiserfs_write_lock(dir->i_sb);
	de.de_gen_number_bit_string = NULL;
	retval =
	    reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				&path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval == NAME_FOUND) {
		/* Hide the .reiserfs_priv directory */
		if (reiserfs_xattrs(dir->i_sb) &&
		    !old_format_only(dir->i_sb) &&
		    REISERFS_SB(dir->i_sb)->priv_root &&
		    REISERFS_SB(dir->i_sb)->priv_root->d_inode &&
		    de.de_objectid ==
		    le32_to_cpu(INODE_PKEY
				(REISERFS_SB(dir->i_sb)->priv_root->d_inode)->
				k_objectid)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		inode =
		    reiserfs_iget(dir->i_sb, (struct cpu_key *)&(de.de_dir_id));
		if (!inode || IS_ERR(inode)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		/* Propogate the priv_object flag so we know we're in the priv tree */
		if (is_reiserfs_priv_object(dir))
			reiserfs_mark_inode_private(inode);
	}
	reiserfs_write_unlock(dir->i_sb);
	if (retval == IO_ERROR) {
		return ERR_PTR(-EIO);
	}

	return d_splice_alias(inode, dentry);
}

static struct dentry *reiserfs_lookup(struct inode *dir, struct dentry *dentry,
				      unsigned int flags)
{
	int retval;
	struct inode *inode = NULL;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);

	if (REISERFS_MAX_NAME(dir->i_sb->s_blocksize) < dentry->d_name.len)
		return ERR_PTR(-ENAMETOOLONG);

	reiserfs_write_lock(dir->i_sb);

	de.de_gen_number_bit_string = NULL;
	retval =
	    reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				&path_to_entry, &de);
	pathrelse(&path_to_entry);
	if (retval == NAME_FOUND) {
		inode = reiserfs_iget(dir->i_sb,
				      (struct cpu_key *)&de.de_dir_id);
		if (!inode || IS_ERR(inode)) {
			reiserfs_write_unlock(dir->i_sb);
			return ERR_PTR(-EACCES);
		}

		/*
		 * Propagate the private flag so we know we're
		 * in the priv tree
		 */
		if (IS_PRIVATE(dir))
			inode->i_flags |= S_PRIVATE;
	}
	reiserfs_write_unlock(dir->i_sb);
	if (retval == IO_ERROR) {
		return ERR_PTR(-EIO);
	}

	return d_splice_alias(inode, dentry);
}

static int reiserfs_unlink(struct inode *dir, struct dentry *dentry)
{
	int retval, err;
	struct inode *inode;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path);
	struct reiserfs_transaction_handle th;
	int jbegin_count;
	unsigned long savelink;
	int depth;

	dquot_initialize(dir);

	inode = dentry->d_inode;

	/* in this transaction we can be doing at max two balancings and update
	 * two stat datas, we change quotas of the owner of the directory and of
	 * the owner of the parent directory. The quota structure is possibly
	 * deleted only on iput => outside of this transaction */
	jbegin_count =
	    JOURNAL_PER_BALANCE_CNT * 2 + 2 +
	    4 * REISERFS_QUOTA_TRANS_BLOCKS(dir->i_sb);

	depth = reiserfs_write_lock_once(dir->i_sb);
	retval = journal_begin(&th, dir->i_sb, jbegin_count);
	if (retval)
		goto out_unlink;

	de.de_gen_number_bit_string = NULL;
	if ((retval =
	     reiserfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len,
				 &path, &de)) == NAME_NOT_FOUND) {
		retval = -ENOENT;
		goto end_unlink;
	} else if (retval == IO_ERROR) {
		retval = -EIO;
		goto end_unlink;
	}

	reiserfs_update_inode_transaction(inode);
	reiserfs_update_inode_transaction(dir);

	if (de.de_objectid != inode->i_ino) {
		// FIXME: compare key of an object and a key found in the
		// entry
		retval = -EIO;
		goto end_unlink;
	}

	if (!inode->i_nlink) {
		reiserfs_warning(inode->i_sb, "reiserfs-7042",
				 "deleting nonexistent file (%lu), %d",
				 inode->i_ino, inode->i_nlink);
		set_nlink(inode, 1);
	}

	drop_nlink(inode);

	/*
	 * we schedule before doing the add_save_link call, save the link
	 * count so we don't race
	 */
	savelink = inode->i_nlink;

	retval =
	    reiserfs_cut_from_item(&th, &path, &(de.de_entry_key), dir, NULL,
				   0);
	if (retval < 0) {
		inc_nlink(inode);
		goto end_unlink;
	}
	inode->i_ctime = CURRENT_TIME_SEC;
	reiserfs_update_sd(&th, inode);

	dir->i_size -= (de.de_entrylen + DEH_SIZE);
	dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
	reiserfs_update_sd(&th, dir);

	if (!savelink)
		/* prevent file from getting lost */
		add_save_link(&th, inode, 0 /* not truncate */ );

	retval = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_check_path(&path);
	reiserfs_write_unlock_once(dir->i_sb, depth);
	return retval;

      end_unlink:
	pathrelse(&path);
	err = journal_end(&th, dir->i_sb, jbegin_count);
	reiserfs_check_path(&path);
	if (err)
		retval = err;
      out_unlink:
	reiserfs_write_unlock_once(dir->i_sb, depth);
	return retval;
}

/*
 * process, that is going to call fix_nodes/do_balance must hold only
 * one path. If it holds 2 or more, it can get into endless waiting in
 * get_empty_nodes or its clones
 */
static int reiserfs_rename(struct inode *old_dir, struct dentry *old_dentry,
			   struct inode *new_dir, struct dentry *new_dentry)
{
	int retval;
	INITIALIZE_PATH(old_entry_path);
	INITIALIZE_PATH(new_entry_path);
	INITIALIZE_PATH(dot_dot_entry_path);
	struct item_head new_entry_ih, old_entry_ih, dot_dot_ih;
	struct reiserfs_dir_entry old_de, new_de, dot_dot_de;
	struct inode *old_inode, *new_dentry_inode;
	struct reiserfs_transaction_handle th;
	int jbegin_count;
	umode_t old_inode_mode;
	unsigned long savelink = 1;
	struct timespec ctime;

	/* three balancings: (1) old name removal, (2) new name insertion
	   and (3) maybe "save" link insertion
	   stat data updates: (1) old directory,
	   (2) new directory and (3) maybe old object stat data (when it is
	   directory) and (4) maybe stat data of object to which new entry
	   pointed initially and (5) maybe block containing ".." of
	   renamed directory
	   quota updates: two parent directories */
	jbegin_count =
	    JOURNAL_PER_BALANCE_CNT * 3 + 5 +
	    4 * REISERFS_QUOTA_TRANS_BLOCKS(old_dir->i_sb);

	dquot_initialize(old_dir);
	dquot_initialize(new_dir);

	old_inode = old_dentry->d_inode;
	new_dentry_inode = new_dentry->d_inode;

	// make sure, that oldname still exists and points to an object we
	// are going to rename
	old_de.de_gen_number_bit_string = NULL;
	reiserfs_write_lock(old_dir->i_sb);
	retval =
	    reiserfs_find_entry(old_dir, old_dentry->d_name.name,
				old_dentry->d_name.len, &old_entry_path,
				&old_de);
	pathrelse(&old_entry_path);
	if (retval == IO_ERROR) {
		reiserfs_write_unlock(old_dir->i_sb);
		return -EIO;
	}

	if (retval != NAME_FOUND || old_de.de_objectid != old_inode->i_ino) {
		reiserfs_write_unlock(old_dir->i_sb);
		return -ENOENT;
	}

	old_inode_mode = old_inode->i_mode;
	if (S_ISDIR(old_inode_mode)) {
		// make sure, that directory being renamed has correct ".."
		// and that its new parent directory has not too many links
		// already

		if (new_dentry_inode) {
			if (!reiserfs_empty_dir(new_dentry_inode)) {
				reiserfs_write_unlock(old_dir->i_sb);
				return -ENOTEMPTY;
			}
		}

		/* directory is renamed, its parent directory will be changed,
		 ** so find ".." entry
		 */
		dot_dot_de.de_gen_number_bit_string = NULL;
		retval =
		    reiserfs_find_entry(old_inode, "..", 2, &dot_dot_entry_path,
					&dot_dot_de);
		pathrelse(&dot_dot_entry_path);
		if (retval != NAME_FOUND) {
			reiserfs_write_unlock(old_dir->i_sb);
			return -EIO;
		}

		/* inode number of .. must equal old_dir->i_ino */
		if (dot_dot_de.de_objectid != old_dir->i_ino) {
			reiserfs_write_unlock(old_dir->i_sb);
			return -EIO;
		}
	}

	retval = journal_begin(&th, old_dir->i_sb, jbegin_count);
	if (retval) {
		reiserfs_write_unlock(old_dir->i_sb);
		return retval;
	}

	/* add new entry (or find the existing one) */
	retval =
	    reiserfs_add_entry(&th, new_dir, new_dentry->d_name.name,
//.........这里部分代码省略.........

int
reiserfs_lookup(struct vop_cachedlookup_args *ap)
{
	int error, retval;
	struct vnode *vdp         = ap->a_dvp;
	struct vnode **vpp        = ap->a_vpp;
	struct componentname *cnp = ap->a_cnp;

	int flags         = cnp->cn_flags;
	struct thread *td = cnp->cn_thread;
	struct cpu_key *saved_ino;

	struct vnode *vp;
	struct vnode *pdp;  /* Saved dp during symlink work */
	struct reiserfs_node *dp;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);

	char c = cnp->cn_nameptr[cnp->cn_namelen];
	cnp->cn_nameptr[cnp->cn_namelen] = '\0';
	reiserfs_log(LOG_DEBUG, "looking for `%s', %ld (%s)\n",
	    cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_pnbuf);
	cnp->cn_nameptr[cnp->cn_namelen] = c;

	vp = NULL;
	dp = VTOI(vdp);

	if (REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize) < cnp->cn_namelen)
		return (ENAMETOOLONG);

	reiserfs_log(LOG_DEBUG, "searching entry\n");
	de.de_gen_number_bit_string = 0;
	retval = reiserfs_find_entry(dp, cnp->cn_nameptr, cnp->cn_namelen,
	    &path_to_entry, &de);
	pathrelse(&path_to_entry);

	if (retval == NAME_FOUND) {
		reiserfs_log(LOG_DEBUG, "found\n");
	} else {
		reiserfs_log(LOG_DEBUG, "not found\n");
	}

	if (retval == NAME_FOUND) {
#if 0
		/* Hide the .reiserfs_priv directory */
		if (reiserfs_xattrs(dp->i_reiserfs) &&
		    !old_format_only(dp->i_reiserfs) &&
		    REISERFS_SB(dp->i_reiserfs)->priv_root &&
		    REISERFS_SB(dp->i_reiserfs)->priv_root->d_inode &&
		    de.de_objectid == le32toh(INODE_PKEY(REISERFS_SB(
		    dp->i_reiserfs)->priv_root->d_inode)->k_objectid)) {
			return (EACCES);
		}
#endif

		reiserfs_log(LOG_DEBUG, "reading vnode\n");
		pdp = vdp;
		if (flags & ISDOTDOT) {
			saved_ino = (struct cpu_key *)&(de.de_dir_id);
			VOP_UNLOCK(pdp, 0);
			error = reiserfs_iget(vdp->v_mount,
			    saved_ino, &vp, td);
			vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY);
			if (error != 0)
				return (error);
			*vpp = vp;
		} else if (de.de_objectid == dp->i_number &&
		    de.de_dir_id == dp->i_ino) {
			VREF(vdp); /* We want ourself, ie "." */
			*vpp = vdp;
		} else {
			if ((error = reiserfs_iget(vdp->v_mount,
			    (struct cpu_key *)&(de.de_dir_id), &vp, td)) != 0)
				return (error);
			*vpp = vp;
		}

		/*
		 * Propogate the priv_object flag so we know we're in the
		 * priv tree
		 */
		/*if (is_reiserfs_priv_object(dir))
			REISERFS_I(inode)->i_flags |= i_priv_object;*/
	} else {
		if (retval == IO_ERROR) {
			reiserfs_log(LOG_DEBUG, "IO error\n");
			return (EIO);
		}

		return (ENOENT);
	}

	/* Insert name into cache if appropriate. */
	if (cnp->cn_flags & MAKEENTRY)
		cache_enter(vdp, *vpp, cnp);

	reiserfs_log(LOG_DEBUG, "done\n");
	return (0);
}

/* Allocates blocks for a file to fulfil write request.
   Maps all unmapped but prepared pages from the list.
   Updates metadata with newly allocated blocknumbers as needed */
int reiserfs_allocate_blocks_for_region(
				struct reiserfs_transaction_handle *th,
				struct inode *inode, /* Inode we work with */
				loff_t pos, /* Writing position */
				int num_pages, /* number of pages write going
						  to touch */
				int write_bytes, /* amount of bytes to write */
				struct page **prepared_pages, /* array of
							         prepared pages
							       */
				int blocks_to_allocate /* Amount of blocks we
							  need to allocate to
							  fit the data into file
							 */
				)
{
    struct cpu_key key; // cpu key of item that we are going to deal with
    struct item_head *ih; // pointer to item head that we are going to deal with
    struct buffer_head *bh; // Buffer head that contains items that we are going to deal with
    __u32 * item; // pointer to item we are going to deal with
    INITIALIZE_PATH(path); // path to item, that we are going to deal with.
    b_blocknr_t *allocated_blocks; // Pointer to a place where allocated blocknumbers would be stored.
    reiserfs_blocknr_hint_t hint; // hint structure for block allocator.
    size_t res; // return value of various functions that we call.
    int curr_block; // current block used to keep track of unmapped blocks.
    int i; // loop counter
    int itempos; // position in item
    unsigned int from = (pos & (PAGE_CACHE_SIZE - 1)); // writing position in
						       // first page
    unsigned int to = ((pos + write_bytes - 1) & (PAGE_CACHE_SIZE - 1)) + 1; /* last modified byte offset in last page */
    __u64 hole_size ; // amount of blocks for a file hole, if it needed to be created.
    int modifying_this_item = 0; // Flag for items traversal code to keep track
				 // of the fact that we already prepared
				 // current block for journal
    int will_prealloc = 0;

    RFALSE(!blocks_to_allocate, "green-9004: tried to allocate zero blocks?");

    /* only preallocate if this is a small write */
    if (REISERFS_I(inode)->i_prealloc_count ||
       (!(write_bytes & (inode->i_sb->s_blocksize -1)) &&
        blocks_to_allocate <
        REISERFS_SB(inode->i_sb)->s_alloc_options.preallocsize))
        will_prealloc = REISERFS_SB(inode->i_sb)->s_alloc_options.preallocsize;

    allocated_blocks = kmalloc((blocks_to_allocate + will_prealloc) *
    					sizeof(b_blocknr_t), GFP_NOFS);

    /* First we compose a key to point at the writing position, we want to do
       that outside of any locking region. */
    make_cpu_key (&key, inode, pos+1, TYPE_ANY, 3/*key length*/);

    /* If we came here, it means we absolutely need to open a transaction,
       since we need to allocate some blocks */
    reiserfs_write_lock(inode->i_sb); // Journaling stuff and we need that.
    journal_begin(th, inode->i_sb, JOURNAL_PER_BALANCE_CNT * 3 + 1); // Wish I know if this number enough
    reiserfs_update_inode_transaction(inode) ;

    /* Look for the in-tree position of our write, need path for block allocator */
    res = search_for_position_by_key(inode->i_sb, &key, &path);
    if ( res == IO_ERROR ) {
	res = -EIO;
	goto error_exit;
    }
   
    /* Allocate blocks */
    /* First fill in "hint" structure for block allocator */
    hint.th = th; // transaction handle.
    hint.path = &path; // Path, so that block allocator can determine packing locality or whatever it needs to determine.
    hint.inode = inode; // Inode is needed by block allocator too.
    hint.search_start = 0; // We have no hint on where to search free blocks for block allocator.
    hint.key = key.on_disk_key; // on disk key of file.
    hint.block = inode->i_blocks>>(inode->i_sb->s_blocksize_bits-9); // Number of disk blocks this file occupies already.
    hint.formatted_node = 0; // We are allocating blocks for unformatted node.
    hint.preallocate = will_prealloc;

    /* Call block allocator to allocate blocks */
    res = reiserfs_allocate_blocknrs(&hint, allocated_blocks, blocks_to_allocate, blocks_to_allocate);
    if ( res != CARRY_ON ) {
	if ( res == NO_DISK_SPACE ) {
	    /* We flush the transaction in case of no space. This way some
	       blocks might become free */
	    SB_JOURNAL(inode->i_sb)->j_must_wait = 1;
	    restart_transaction(th, inode, &path);

	    /* We might have scheduled, so search again */
	    res = search_for_position_by_key(inode->i_sb, &key, &path);
	    if ( res == IO_ERROR ) {
		res = -EIO;
		goto error_exit;
	    }

	    /* update changed info for hint structure. */
	    res = reiserfs_allocate_blocknrs(&hint, allocated_blocks, blocks_to_allocate, blocks_to_allocate);
	    if ( res != CARRY_ON ) {
		res = -ENOSPC; 
		pathrelse(&path);
//.........这里部分代码省略.........

int
reiserfs_readdir(struct vop_readdir_args  /* {
		struct vnode *a_vp;
		struct uio *a_uio;
		struct ucred *a_cred;
		int *a_eofflag;
		int *a_ncookies;
		u_long **a_cookies;
	} */*ap)
{
	int error = 0;
	struct dirent dstdp;
	struct uio *uio = ap->a_uio;

	off_t next_pos;
	struct buf *bp;
	struct item_head *ih;
	struct cpu_key pos_key;
	const struct key *rkey;
	struct reiserfs_node *ip;
	struct reiserfs_dir_entry de;
	INITIALIZE_PATH(path_to_entry);
	int entry_num, item_num, search_res;

	/* The NFS part */
	int ncookies = 0;
	u_long *cookies = NULL;

	/*
	 * Form key for search the next directory entry using f_pos field of
	 * file structure
	 */
	ip = VTOI(ap->a_vp);
	make_cpu_key(&pos_key,
	    ip, uio->uio_offset ? uio->uio_offset : DOT_OFFSET,
	    TYPE_DIRENTRY, 3);
	next_pos = cpu_key_k_offset(&pos_key);

	reiserfs_log(LOG_DEBUG, "listing entries for "
	    "(objectid=%d, dirid=%d)\n",
	    pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id);
	reiserfs_log(LOG_DEBUG, "uio_offset = %jd, uio_resid = %d\n",
	    (intmax_t)uio->uio_offset, uio->uio_resid);

	if (ap->a_ncookies && ap->a_cookies) {
		cookies = (u_long *)malloc(
		    uio->uio_resid / 16 * sizeof(u_long),
		    M_REISERFSCOOKIES, M_WAITOK);
	}

	while (1) {
		//research:
		/*
		 * Search the directory item, containing entry with
		 * specified key
		 */
		reiserfs_log(LOG_DEBUG, "search directory to read\n");
		search_res = search_by_entry_key(ip->i_reiserfs, &pos_key,
		    &path_to_entry, &de);
		if (search_res == IO_ERROR) {
			error = EIO;
			goto out;
		}

		entry_num = de.de_entry_num;
		item_num  = de.de_item_num;
		bp = de.de_bp;
		ih = de.de_ih;

		if (search_res == POSITION_FOUND ||
		    entry_num < I_ENTRY_COUNT(ih)) {
			/*
			 * Go through all entries in the directory item
			 * beginning from the entry, that has been found.
			 */
			struct reiserfs_de_head *deh = B_I_DEH(bp, ih) +
			    entry_num;

			if (ap->a_ncookies == NULL) {
				cookies = NULL;
			} else {
				//ncookies = 
			}

			reiserfs_log(LOG_DEBUG,
			    "walking through directory entries\n");
			for (; entry_num < I_ENTRY_COUNT(ih);
			    entry_num++, deh++) {
				int d_namlen;
				char *d_name;
				off_t d_off;
				ino_t d_ino;

				if (!de_visible(deh)) {
					/* It is hidden entry */
					continue;
				}

				d_namlen = entry_length(bp, ih, entry_num);
				d_name   = B_I_DEH_ENTRY_FILE_NAME(bp, ih, deh);
//.........这里部分代码省略.........

static int reiserfs_rmdir (struct inode * dir, struct dentry *dentry)
{
    int retval;
    struct inode * inode;
    struct reiserfs_transaction_handle th ;
    int jbegin_count; 
    INITIALIZE_PATH (path);
    struct reiserfs_dir_entry de;


    /* we will be doing 2 balancings and update 2 stat data */
    jbegin_count = JOURNAL_PER_BALANCE_CNT * 2 + 2;

    reiserfs_write_lock(dir->i_sb);
    journal_begin(&th, dir->i_sb, jbegin_count) ;

    de.de_gen_number_bit_string = 0;
    if ( (retval = reiserfs_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &path, &de)) == NAME_NOT_FOUND) {
	retval = -ENOENT;
	goto end_rmdir;
    } else if ( retval == IO_ERROR) {
	retval = -EIO;
	goto end_rmdir;
    }

    inode = dentry->d_inode;

    reiserfs_update_inode_transaction(inode) ;
    reiserfs_update_inode_transaction(dir) ;

    if (de.de_objectid != inode->i_ino) {
	// FIXME: compare key of an object and a key found in the
	// entry
	retval = -EIO;
	goto end_rmdir;
    }
    if (!reiserfs_empty_dir(inode)) {
	retval = -ENOTEMPTY;
	goto end_rmdir;
    }

    /* cut entry from dir directory */
    retval = reiserfs_cut_from_item (&th, &path, &(de.de_entry_key), dir, 
                                     NULL, /* page */ 
				     0/*new file size - not used here*/);
    if (retval < 0)
	goto end_rmdir;

    if ( inode->i_nlink != 2 && inode->i_nlink != 1 )
	reiserfs_warning (inode->i_sb, "%s: empty directory has nlink "
			  "!= 2 (%d)", __FUNCTION__, inode->i_nlink);

    inode->i_nlink = 0;
    inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME;
    reiserfs_update_sd (&th, inode);

    DEC_DIR_INODE_NLINK(dir)
    dir->i_size -= (DEH_SIZE + de.de_entrylen);
    reiserfs_update_sd (&th, dir);

    /* prevent empty directory from getting lost */
    add_save_link (&th, inode, 0/* not truncate */);

    journal_end(&th, dir->i_sb, jbegin_count) ;
    reiserfs_check_path(&path) ;
    reiserfs_write_unlock(dir->i_sb);
    return 0;
	
 end_rmdir:
    /* we must release path, because we did not call
       reiserfs_cut_from_item, or reiserfs_cut_from_item does not
       release path if operation was not complete */
    pathrelse (&path);
    journal_end(&th, dir->i_sb, jbegin_count) ;
    reiserfs_write_unlock(dir->i_sb);
    return retval;	
}

static int reiserfs_unlink (struct inode * dir, struct dentry *dentry)
{
    int retval;
    struct inode * inode;
    struct reiserfs_dir_entry de;
    INITIALIZE_PATH (path);
    struct reiserfs_transaction_handle th ;
    int jbegin_count;
    unsigned long savelink;

    inode = dentry->d_inode;

    /* in this transaction we can be doing at max two balancings and update
       two stat datas */
    jbegin_count = JOURNAL_PER_BALANCE_CNT * 2 + 2;

    reiserfs_write_lock(dir->i_sb);
    journal_begin(&th, dir->i_sb, jbegin_count) ;
	
    de.de_gen_number_bit_string = 0;
    if ( (retval = reiserfs_find_entry (dir, dentry->d_name.name, dentry->d_name.len, &path, &de)) == NAME_NOT_FOUND) {
	retval = -ENOENT;
	goto end_unlink;
    } else if (retval == IO_ERROR) {
	retval = -EIO;
	goto end_unlink;
    }

    reiserfs_update_inode_transaction(inode) ;
    reiserfs_update_inode_transaction(dir) ;

    if (de.de_objectid != inode->i_ino) {
	// FIXME: compare key of an object and a key found in the
	// entry
	retval = -EIO;
	goto end_unlink;
    }
  
    if (!inode->i_nlink) {
	reiserfs_warning (inode->i_sb, "%s: deleting nonexistent file "
			  "(%s:%lu), %d", __FUNCTION__,
			  reiserfs_bdevname (inode->i_sb), inode->i_ino,
			  inode->i_nlink);
	inode->i_nlink = 1;
    }

    inode->i_nlink--;

    /*
     * we schedule before doing the add_save_link call, save the link
     * count so we don't race
     */
    savelink = inode->i_nlink;


    retval = reiserfs_cut_from_item (&th, &path, &(de.de_entry_key), dir, NULL, 0);
    if (retval < 0) {
	inode->i_nlink++;
	goto end_unlink;
    }
    inode->i_ctime = CURRENT_TIME;
    reiserfs_update_sd (&th, inode);

    dir->i_size -= (de.de_entrylen + DEH_SIZE);
    dir->i_ctime = dir->i_mtime = CURRENT_TIME;
    reiserfs_update_sd (&th, dir);

    if (!savelink)
       /* prevent file from getting lost */
       add_save_link (&th, inode, 0/* not truncate */);

    journal_end(&th, dir->i_sb, jbegin_count) ;
    reiserfs_check_path(&path) ;
    reiserfs_write_unlock(dir->i_sb);
    return 0;

 end_unlink:
    pathrelse (&path);
    journal_end(&th, dir->i_sb, jbegin_count) ;
    reiserfs_check_path(&path) ;
    reiserfs_write_unlock(dir->i_sb);
    return retval;
}

static int reiserfs_add_entry(struct reiserfs_transaction_handle *th,
			      struct inode *dir, const char *name, int namelen,
			      struct inode *inode, int visible)
{
	struct cpu_key entry_key;
	struct reiserfs_de_head *deh;
	INITIALIZE_PATH(path);
	struct reiserfs_dir_entry de;
	DECLARE_BITMAP(bit_string, MAX_GENERATION_NUMBER + 1);
	int gen_number;
	char small_buf[32 + DEH_SIZE];	/* 48 bytes now and we avoid kmalloc
					   if we create file with short name */
	char *buffer;
	int buflen, paste_size;
	int retval;

	BUG_ON(!th->t_trans_id);

	/* cannot allow items to be added into a busy deleted directory */
	if (!namelen)
		return -EINVAL;

	if (namelen > REISERFS_MAX_NAME(dir->i_sb->s_blocksize))
		return -ENAMETOOLONG;

	/* each entry has unique key. compose it */
	make_cpu_key(&entry_key, dir,
		     get_third_component(dir->i_sb, name, namelen),
		     TYPE_DIRENTRY, 3);

	/* get memory for composing the entry */
	buflen = DEH_SIZE + ROUND_UP(namelen);
	if (buflen > sizeof(small_buf)) {
		buffer = kmalloc(buflen, GFP_NOFS);
		if (!buffer)
			return -ENOMEM;
	} else
		buffer = small_buf;

	paste_size =
	    (get_inode_sd_version(dir) ==
	     STAT_DATA_V1) ? (DEH_SIZE + namelen) : buflen;

	/* fill buffer : directory entry head, name[, dir objectid | , stat data | ,stat data, dir objectid ] */
	deh = (struct reiserfs_de_head *)buffer;
	deh->deh_location = 0;	/* JDM Endian safe if 0 */
	put_deh_offset(deh, cpu_key_k_offset(&entry_key));
	deh->deh_state = 0;	/* JDM Endian safe if 0 */
	/* put key (ino analog) to de */
	deh->deh_dir_id = INODE_PKEY(inode)->k_dir_id;	/* safe: k_dir_id is le */
	deh->deh_objectid = INODE_PKEY(inode)->k_objectid;	/* safe: k_objectid is le */

	/* copy name */
	memcpy((char *)(deh + 1), name, namelen);
	/* padd by 0s to the 4 byte boundary */
	padd_item((char *)(deh + 1), ROUND_UP(namelen), namelen);

	/* entry is ready to be pasted into tree, set 'visibility' and 'stat data in entry' attributes */
	mark_de_without_sd(deh);
	visible ? mark_de_visible(deh) : mark_de_hidden(deh);

	/* find the proper place for the new entry */
	memset(bit_string, 0, sizeof(bit_string));
	de.de_gen_number_bit_string = bit_string;
	retval = reiserfs_find_entry(dir, name, namelen, &path, &de);
	if (retval != NAME_NOT_FOUND) {
		if (buffer != small_buf)
			kfree(buffer);
		pathrelse(&path);

		if (retval == IO_ERROR) {
			return -EIO;
		}

		if (retval != NAME_FOUND) {
			reiserfs_error(dir->i_sb, "zam-7002",
				       "reiserfs_find_entry() returned "
				       "unexpected value (%d)", retval);
		}

		return -EEXIST;
	}

	gen_number =
	    find_first_zero_bit(bit_string,
				MAX_GENERATION_NUMBER + 1);
	if (gen_number > MAX_GENERATION_NUMBER) {
		/* there is no free generation number */
		reiserfs_warning(dir->i_sb, "reiserfs-7010",
				 "Congratulations! we have got hash function "
				 "screwed up");
		if (buffer != small_buf)
			kfree(buffer);
		pathrelse(&path);
		return -EBUSY;
	}
	/* adjust offset of directory enrty */
	put_deh_offset(deh, SET_GENERATION_NUMBER(deh_offset(deh), gen_number));
	set_cpu_key_k_offset(&entry_key, deh_offset(deh));

//.........这里部分代码省略.........

/* to protect file being unlinked from getting lost we "safe" link files
   being unlinked. This link will be deleted in the same transaction with last
   item of file. mounting the filesytem we scan all these links and remove
   files which almost got lost */
void add_save_link (struct reiserfs_transaction_handle * th,
		    struct inode * inode, int truncate)
{
    INITIALIZE_PATH (path);
    int retval;
    struct cpu_key key;
    struct item_head ih;
    __u32 link;

    /* file can only get one "save link" of each kind */
    RFALSE( truncate && 
	    ( inode -> u.reiserfs_i.i_flags & i_link_saved_truncate_mask ),
	    "saved link already exists for truncated inode %lx",
	    ( long ) inode -> i_ino );
    RFALSE( !truncate && 
	    ( inode -> u.reiserfs_i.i_flags & i_link_saved_unlink_mask ),
	    "saved link already exists for unlinked inode %lx",
	    ( long ) inode -> i_ino );

    /* setup key of "save" link */
    key.version = KEY_FORMAT_3_5;
    key.on_disk_key.k_dir_id = MAX_KEY_OBJECTID;
    key.on_disk_key.k_objectid = inode->i_ino;
    if (!truncate) {
	/* unlink, rmdir, rename */
	set_cpu_key_k_offset (&key, 1 + inode->i_sb->s_blocksize);
	set_cpu_key_k_type (&key, TYPE_DIRECT);

	/* item head of "safe" link */
	make_le_item_head (&ih, &key, key.version, 1 + inode->i_sb->s_blocksize, TYPE_DIRECT,
			   4/*length*/, 0xffff/*free space*/);
    } else {
	/* truncate */
	if (S_ISDIR (inode->i_mode))
	    reiserfs_warning("green-2102: Adding a truncate savelink for a directory %k! Please report\n", INODE_PKEY(inode));
	set_cpu_key_k_offset (&key, 1);
	set_cpu_key_k_type (&key, TYPE_INDIRECT);

	/* item head of "safe" link */
	make_le_item_head (&ih, &key, key.version, 1, TYPE_INDIRECT,
			   4/*length*/, 0/*free space*/);
    }
    key.key_length = 3;

    /* look for its place in the tree */
    retval = search_item (inode->i_sb, &key, &path);
    if (retval != ITEM_NOT_FOUND) {
	if ( retval != -ENOSPC )
	    reiserfs_warning ("vs-2100: add_save_link:"
			  "search_by_key (%K) returned %d\n", &key, retval);
	pathrelse (&path);
	return;
    }

    /* body of "save" link */
    link = cpu_to_le32 (INODE_PKEY (inode)->k_dir_id);

    /* put "save" link inot tree */
    retval = reiserfs_insert_item (th, &path, &key, &ih, (char *)&link);
    if (retval) {
	if (retval != -ENOSPC)
	    reiserfs_warning ("vs-2120: add_save_link: insert_item returned %d\n",
			  retval);
    } else {
	if( truncate )
	    inode -> u.reiserfs_i.i_flags |= i_link_saved_truncate_mask;
	else
	    inode -> u.reiserfs_i.i_flags |= i_link_saved_unlink_mask;
    }
}

/* look for uncompleted unlinks and truncates and complete them */
static void finish_unfinished (struct super_block * s)
{
    INITIALIZE_PATH (path);
    struct cpu_key max_cpu_key, obj_key;
    struct key save_link_key;
    int retval;
    struct item_head * ih;
    struct buffer_head * bh;
    int item_pos;
    char * item;
    int done;
    struct inode * inode;
    int truncate;
 
 
    /* compose key to look for "save" links */
    max_cpu_key.version = KEY_FORMAT_3_5;
    max_cpu_key.on_disk_key = MAX_KEY;
    max_cpu_key.key_length = 3;
 
    done = 0;
    s -> u.reiserfs_sb.s_is_unlinked_ok = 1;
    while (1) {
        retval = search_item (s, &max_cpu_key, &path);
        if (retval != ITEM_NOT_FOUND) {
            reiserfs_warning ("vs-2140: finish_unfinished: search_by_key returned %d\n",
                              retval);
            break;
        }
        
        bh = get_last_bh (&path);
        item_pos = get_item_pos (&path);
        if (item_pos != B_NR_ITEMS (bh)) {
            reiserfs_warning ("vs-2060: finish_unfinished: wrong position found\n");
            break;
        }
        item_pos --;
        ih = B_N_PITEM_HEAD (bh, item_pos);
 
        if (le32_to_cpu (ih->ih_key.k_dir_id) != MAX_KEY_OBJECTID)
            /* there are no "save" links anymore */
            break;
 
        save_link_key = ih->ih_key;
        if (is_indirect_le_ih (ih))
            truncate = 1;
        else
            truncate = 0;
 
        /* reiserfs_iget needs k_dirid and k_objectid only */
        item = B_I_PITEM (bh, ih);
        obj_key.on_disk_key.k_dir_id = le32_to_cpu (*(__u32 *)item);
        obj_key.on_disk_key.k_objectid = le32_to_cpu (ih->ih_key.k_objectid);
	obj_key.on_disk_key.u.k_offset_v1.k_offset = 0;
	obj_key.on_disk_key.u.k_offset_v1.k_uniqueness = 0;
	
        pathrelse (&path);
 
        inode = reiserfs_iget (s, &obj_key);
        if (!inode) {
            /* the unlink almost completed, it just did not manage to remove
	       "save" link and release objectid */
            reiserfs_warning ("vs-2180: finish_unfinished: iget failed for %K\n",
                              &obj_key);
            remove_save_link_only (s, &save_link_key, 1);
            continue;
        }

	if (!truncate && inode->i_nlink) {
	    /* file is not unlinked */
            reiserfs_warning ("vs-2185: finish_unfinished: file %K is not unlinked\n",
                              &obj_key);
            remove_save_link_only (s, &save_link_key, 0);
            continue;
	}

	if (truncate && S_ISDIR (inode->i_mode) ) {
	    /* We got a truncate request for a dir which is impossible.
	       The only imaginable way is to execute unfinished truncate request
	       then boot into old kernel, remove the file and create dir with
	       the same key. */
	    reiserfs_warning("green-2101: impossible truncate on a directory %k. Please report\n", INODE_PKEY (inode));
	    remove_save_link_only (s, &save_link_key, 0);
	    truncate = 0;
	    iput (inode); 
	    continue;
	}
 
        if (truncate) {
            inode -> u.reiserfs_i.i_flags |= i_link_saved_truncate_mask;
            /* not completed truncate found. New size was committed together
	       with "save" link */
            reiserfs_warning ("Truncating %k to %Ld ..",
                              INODE_PKEY (inode), inode->i_size);
            reiserfs_truncate_file (inode, 0/*don't update modification time*/);
            remove_save_link (inode, truncate);
        } else {
            inode -> u.reiserfs_i.i_flags |= i_link_saved_unlink_mask;
            /* not completed unlink (rmdir) found */
//.........这里部分代码省略.........

/* returns 0 if name is not found in a directory and objectid of
   pointed object otherwise and returns minimal not used generation
   counter.  dies if found object is not a directory. */
int reiserfs_find_entry (reiserfs_filsys_t fs, struct key * dir, char * name, 
			 int * min_gen_counter)
{
    struct key entry_key;
    int retval;
    int i;
    INITIALIZE_PATH (path);
    struct item_head * ih;
    struct reiserfs_de_head * deh;
    struct key * rdkey;
    __u32 hash;

    entry_key.k_dir_id = cpu_to_le32(dir->k_dir_id);
    entry_key.k_objectid =