stree.c

linux 内核源代码

{
	struct item_head *p_le_ih;	/* pointer to on-disk structure */
	int n_blk_size;
	loff_t item_offset, offset;
	struct reiserfs_dir_entry de;
	int retval;

	/* If searching for directory entry. */
	if (is_direntry_cpu_key(p_cpu_key))
		return search_by_entry_key(p_s_sb, p_cpu_key, p_s_search_path,
					   &de);

	/* If not searching for directory entry. */

	/* If item is found. */
	retval = search_item(p_s_sb, p_cpu_key, p_s_search_path);
	if (retval == IO_ERROR)
		return retval;
	if (retval == ITEM_FOUND) {

		RFALSE(!ih_item_len
		       (B_N_PITEM_HEAD
			(PATH_PLAST_BUFFER(p_s_search_path),
			 PATH_LAST_POSITION(p_s_search_path))),
		       "PAP-5165: item length equals zero");

		pos_in_item(p_s_search_path) = 0;
		return POSITION_FOUND;
	}

	RFALSE(!PATH_LAST_POSITION(p_s_search_path),
	       "PAP-5170: position equals zero");

	/* Item is not found. Set path to the previous item. */
	p_le_ih =
	    B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path),
			   --PATH_LAST_POSITION(p_s_search_path));
	n_blk_size = p_s_sb->s_blocksize;

	if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) {
		return FILE_NOT_FOUND;
	}
	// FIXME: quite ugly this far

	item_offset = le_ih_k_offset(p_le_ih);
	offset = cpu_key_k_offset(p_cpu_key);

	/* Needed byte is contained in the item pointed to by the path. */
	if (item_offset <= offset &&
	    item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) {
		pos_in_item(p_s_search_path) = offset - item_offset;
		if (is_indirect_le_ih(p_le_ih)) {
			pos_in_item(p_s_search_path) /= n_blk_size;
		}
		return POSITION_FOUND;
	}

	/* Needed byte is not contained in the item pointed to by the
	   path. Set pos_in_item out of the item. */
	if (is_indirect_le_ih(p_le_ih))
		pos_in_item(p_s_search_path) =
		    ih_item_len(p_le_ih) / UNFM_P_SIZE;
	else
		pos_in_item(p_s_search_path) = ih_item_len(p_le_ih);

	return POSITION_NOT_FOUND;
}

/* Compare given item and item pointed to by the path. */
int comp_items(const struct item_head *stored_ih, const struct treepath *p_s_path)
{
	struct buffer_head *p_s_bh;
	struct item_head *ih;

	/* Last buffer at the path is not in the tree. */
	if (!B_IS_IN_TREE(p_s_bh = PATH_PLAST_BUFFER(p_s_path)))
		return 1;

	/* Last path position is invalid. */
	if (PATH_LAST_POSITION(p_s_path) >= B_NR_ITEMS(p_s_bh))
		return 1;

	/* we need only to know, whether it is the same item */
	ih = get_ih(p_s_path);
	return memcmp(stored_ih, ih, IH_SIZE);
}

/* unformatted nodes are not logged anymore, ever.  This is safe
** now
*/
#define held_by_others(bh) (atomic_read(&(bh)->b_count) > 1)

// block can not be forgotten as it is in I/O or held by someone
#define block_in_use(bh) (buffer_locked(bh) || (held_by_others(bh)))

// prepare for delete or cut of direct item
static inline int prepare_for_direct_item(struct treepath *path,
					  struct item_head *le_ih,
					  struct inode *inode,
					  loff_t new_file_length, int *cut_size)
{
	loff_t round_len;

	if (new_file_length == max_reiserfs_offset(inode)) {
		/* item has to be deleted */
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;
	}
	// new file gets truncated
	if (get_inode_item_key_version(inode) == KEY_FORMAT_3_6) {
		// 
		round_len = ROUND_UP(new_file_length);
		/* this was n_new_file_length < le_ih ... */
		if (round_len < le_ih_k_offset(le_ih)) {
			*cut_size = -(IH_SIZE + ih_item_len(le_ih));
			return M_DELETE;	/* Delete this item. */
		}
		/* Calculate first position and size for cutting from item. */
		pos_in_item(path) = round_len - (le_ih_k_offset(le_ih) - 1);
		*cut_size = -(ih_item_len(le_ih) - pos_in_item(path));

		return M_CUT;	/* Cut from this item. */
	}

	// old file: items may have any length

	if (new_file_length < le_ih_k_offset(le_ih)) {
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;	/* Delete this item. */
	}
	/* Calculate first position and size for cutting from item. */
	*cut_size = -(ih_item_len(le_ih) -
		      (pos_in_item(path) =
		       new_file_length + 1 - le_ih_k_offset(le_ih)));
	return M_CUT;		/* Cut from this item. */
}

static inline int prepare_for_direntry_item(struct treepath *path,
					    struct item_head *le_ih,
					    struct inode *inode,
					    loff_t new_file_length,
					    int *cut_size)
{
	if (le_ih_k_offset(le_ih) == DOT_OFFSET &&
	    new_file_length == max_reiserfs_offset(inode)) {
		RFALSE(ih_entry_count(le_ih) != 2,
		       "PAP-5220: incorrect empty directory item (%h)", le_ih);
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;	/* Delete the directory item containing "." and ".." entry. */
	}

	if (ih_entry_count(le_ih) == 1) {
		/* Delete the directory item such as there is one record only
		   in this item */
		*cut_size = -(IH_SIZE + ih_item_len(le_ih));
		return M_DELETE;
	}

	/* Cut one record from the directory item. */
	*cut_size =
	    -(DEH_SIZE +
	      entry_length(get_last_bh(path), le_ih, pos_in_item(path)));
	return M_CUT;
}

#define JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD (2 * JOURNAL_PER_BALANCE_CNT + 1)

/*  If the path points to a directory or direct item, calculate mode and the size cut, for balance.
    If the path points to an indirect item, remove some number of its unformatted nodes.
    In case of file truncate calculate whether this item must be deleted/truncated or last
    unformatted node of this item will be converted to a direct item.
    This function returns a determination of what balance mode the calling function should employ. */
static char prepare_for_delete_or_cut(struct reiserfs_transaction_handle *th, struct inode *inode, struct treepath *p_s_path, const struct cpu_key *p_s_item_key, int *p_n_removed,	/* Number of unformatted nodes which were removed
																						   from end of the file. */
				      int *p_n_cut_size, unsigned long long n_new_file_length	/* MAX_KEY_OFFSET in case of delete. */
    )
{
	struct super_block *p_s_sb = inode->i_sb;
	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_path);
	struct buffer_head *p_s_bh = PATH_PLAST_BUFFER(p_s_path);

	BUG_ON(!th->t_trans_id);

	/* Stat_data item. */
	if (is_statdata_le_ih(p_le_ih)) {

		RFALSE(n_new_file_length != max_reiserfs_offset(inode),
		       "PAP-5210: mode must be M_DELETE");

		*p_n_cut_size = -(IH_SIZE + ih_item_len(p_le_ih));
		return M_DELETE;
	}

	/* Directory item. */
	if (is_direntry_le_ih(p_le_ih))
		return prepare_for_direntry_item(p_s_path, p_le_ih, inode,
						 n_new_file_length,
						 p_n_cut_size);

	/* Direct item. */
	if (is_direct_le_ih(p_le_ih))
		return prepare_for_direct_item(p_s_path, p_le_ih, inode,
					       n_new_file_length, p_n_cut_size);

	/* Case of an indirect item. */
	{
	    int blk_size = p_s_sb->s_blocksize;
	    struct item_head s_ih;
	    int need_re_search;
	    int delete = 0;
	    int result = M_CUT;
	    int pos = 0;

	    if ( n_new_file_length == max_reiserfs_offset (inode) ) {
		/* prepare_for_delete_or_cut() is called by
		 * reiserfs_delete_item() */
		n_new_file_length = 0;
		delete = 1;
	    }

	    do {
		need_re_search = 0;
		*p_n_cut_size = 0;
		p_s_bh = PATH_PLAST_BUFFER(p_s_path);
		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
		pos = I_UNFM_NUM(&s_ih);

		while (le_ih_k_offset (&s_ih) + (pos - 1) * blk_size > n_new_file_length) {
		    __le32 *unfm;
		    __u32 block;

		    /* Each unformatted block deletion may involve one additional
		     * bitmap block into the transaction, thereby the initial
		     * journal space reservation might not be enough. */
		    if (!delete && (*p_n_cut_size) != 0 &&
			reiserfs_transaction_free_space(th) < JOURNAL_FOR_FREE_BLOCK_AND_UPDATE_SD) {
			break;
		    }

		    unfm = (__le32 *)B_I_PITEM(p_s_bh, &s_ih) + pos - 1;
		    block = get_block_num(unfm, 0);

		    if (block != 0) {
			reiserfs_prepare_for_journal(p_s_sb, p_s_bh, 1);
			put_block_num(unfm, 0, 0);
			journal_mark_dirty (th, p_s_sb, p_s_bh);
			reiserfs_free_block(th, inode, block, 1);
		    }

		    cond_resched();

		    if (item_moved (&s_ih, p_s_path))  {
			need_re_search = 1;
			break;
		    }

		    pos --;
		    (*p_n_removed) ++;
		    (*p_n_cut_size) -= UNFM_P_SIZE;

		    if (pos == 0) {
			(*p_n_cut_size) -= IH_SIZE;
			result = M_DELETE;
			break;
		    }
		}
		/* a trick.  If the buffer has been logged, this will do nothing.  If
		** we've broken the loop without logging it, it will restore the
		** buffer */
		reiserfs_restore_prepared_buffer(p_s_sb, p_s_bh);
	    } while (need_re_search &&
		     search_for_position_by_key(p_s_sb, p_s_item_key, p_s_path) == POSITION_FOUND);
	    pos_in_item(p_s_path) = pos * UNFM_P_SIZE;

	    if (*p_n_cut_size == 0) {
		/* Nothing were cut. maybe convert last unformatted node to the
		 * direct item? */
		result = M_CONVERT;
	    }
	    return result;
	}
}

/* Calculate number of bytes which will be deleted or cut during balance */
static int calc_deleted_bytes_number(struct tree_balance *p_s_tb, char c_mode)
{
	int n_del_size;
	struct item_head *p_le_ih = PATH_PITEM_HEAD(p_s_tb->tb_path);

	if (is_statdata_le_ih(p_le_ih))
		return 0;

	n_del_size =
	    (c_mode ==
	     M_DELETE) ? ih_item_len(p_le_ih) : -p_s_tb->insert_size[0];
	if (is_direntry_le_ih(p_le_ih)) {
		// return EMPTY_DIR_SIZE; /* We delete emty directoris only. */
		// we can't use EMPTY_DIR_SIZE, as old format dirs have a different
		// empty size.  ick. FIXME, is this right?
		//
		return n_del_size;
	}

	if (is_indirect_le_ih(p_le_ih))
		n_del_size = (n_del_size / UNFM_P_SIZE) * (PATH_PLAST_BUFFER(p_s_tb->tb_path)->b_size);	// - get_ih_free_space (p_le_ih);
	return n_del_size;
}

static void init_tb_struct(struct reiserfs_transaction_handle *th,
			   struct tree_balance *p_s_tb,
			   struct super_block *p_s_sb,
			   struct treepath *p_s_path, int n_size)
{

	BUG_ON(!th->t_trans_id);

	memset(p_s_tb, '\0', sizeof(struct tree_balance));
	p_s_tb->transaction_handle = th;
	p_s_tb->tb_sb = p_s_sb;
	p_s_tb->tb_path = p_s_path;
	PATH_OFFSET_PBUFFER(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = NULL;
	PATH_OFFSET_POSITION(p_s_path, ILLEGAL_PATH_ELEMENT_OFFSET) = 0;
	p_s_tb->insert_size[0] = n_size;
}

void padd_item(char *item, int total_length, int length)
{
	int i;

	for (i = total_length; i > length;)
		item[--i] = 0;
}

#ifdef REISERQUOTA_DEBUG
char key2type(struct reiserfs_key *ih)
{
	if (is_direntry_le_key(2, ih))
		return 'd';
	if (is_direct_le_key(2, ih))
		return 'D';
	if (is_indirect_le_key(2, ih))
		return 'i';
	if (is_statdata_le_key(2, ih))
		return 's';
	return 'u';
}

char head2type(struct item_head *ih)
{
	if (is_direntry_le_ih(ih))
		return 'd';
	if (is_direct_le_ih(ih))
		return 'D';
	if (is_indirect_le_ih(ih))
		return 'i';
	if (is_statdata_le_ih(ih))
		return 's';
	return 'u';
}
#endif

/* Delete object item. */
int reiserfs_delete_item(struct reiserfs_transaction_handle *th, struct treepath *p_s_path,	/* Path to the deleted item. */
			 const struct cpu_key *p_s_item_key,	/* Key to search for the deleted item.  */
			 struct inode *p_s_inode,	/* inode is here just to update i_blocks and quotas */
			 struct buffer_head *p_s_un_bh)
{				/* NULL or unformatted node pointer.    */
	struct super_block *p_s_sb = p_s_inode->i_sb;
	struct tree_balance s_del_balance;
	struct item_head s_ih;
	struct item_head *q_ih;
	int quota_cut_bytes;
	int n_ret_value, n_del_size, n_removed;

#ifdef CONFIG_REISERFS_CHECK
	char c_mode;
	int n_iter = 0;
#endif

	BUG_ON(!th->t_trans_id);

	init_tb_struct(th, &s_del_balance, p_s_sb, p_s_path,
		       0 /*size is unknown */ );

	while (1) {
		n_removed = 0;

#ifdef CONFIG_REISERFS_CHECK
		n_iter++;
		c_mode =
#endif
		    prepare_for_delete_or_cut(th, p_s_inode, p_s_path,
					      p_s_item_key, &n_removed,
					      &n_del_size,
					      max_reiserfs_offset(p_s_inode));

		RFALSE(c_mode != M_DELETE, "PAP-5320: mode must be M_DELETE");

		copy_item_head(&s_ih, PATH_PITEM_HEAD(p_s_path));
		s_del_balance.insert_size[0] = n_del_size;

		n_ret_value = fix_nodes(M_DELETE, &s_del_balance, NULL, NULL);
		if (n_ret_value != REPEAT_SEARCH)
			break;

		PROC_INFO_INC(p_s_sb, delete_item_restarted);

		// file system changed, repeat search