path: root/fs/reiserfs/namei.c

/*
 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
 *
 * Trivial changes by Alan Cox to remove EHASHCOLLISION for compatibility
 *
 * Trivial Changes:
 * Rights granted to Hans Reiser to redistribute under other terms providing
 * he accepts all liability including but not limited to patent, fitness
 * for purpose, and direct or indirect claims arising from failure to perform.
 *
 * NO WARRANTY
 */

#include <linux/time.h>
#include <linux/bitops.h>
#include <linux/slab.h>
#include <linux/reiserfs_fs.h>
#include <linux/reiserfs_acl.h>
#include <linux/reiserfs_xattr.h>
#include <linux/quotaops.h>

#define INC_DIR_INODE_NLINK(i) if (i->i_nlink != 1) { inc_nlink(i); if (i->i_nlink >= REISERFS_LINK_MAX) set_nlink(i, 1); }
#define DEC_DIR_INODE_NLINK(i) if (i->i_nlink != 1) drop_nlink(i);

// directory item contains array of entry headers. This performs
// binary search through that array
static int bin_search_in_dir_item(struct reiserfs_dir_entry *de, loff_t off)
{
	struct item_head *ih = de->de_ih;
	struct reiserfs_de_head *deh = de->de_deh;
	int rbound, lbound, j;

	lbound = 0;
	rbound = I_ENTRY_COUNT(ih) - 1;

	for (j = (rbound + lbound) / 2; lbound <= rbound;
	     j = (rbound + lbound) / 2) {
		if (off < deh_offset(deh + j)) {
			rbound = j - 1;
			continue;
		}
		if (off > deh_offset(deh + j)) {
			lbound = j + 1;
			continue;
		}
		// this is not name found, but matched third key component
		de->de_entry_num = j;
		return NAME_FOUND;
	}

	de->de_entry_num = lbound;
	return NAME_NOT_FOUND;
}

// comment?  maybe something like set de to point to what the path points to?
static inline void set_de_item_location(struct reiserfs_dir_entry *de,
					struct treepath *path)
{
	de->de_bh = get_last_bh(path);
	de->de_ih = get_ih(path);
	de->de_deh = B_I_DEH(de->de_bh, de->de_ih);
	de->de_item_num = PATH_LAST_POSITION(path);
}

// de_bh, de_ih, de_deh (points to first element of array), de_item_num is set
inline void set_de_name_and_namelen(struct reiserfs_dir_entry *de)
{
	struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num;

	BUG_ON(de->de_entry_num >= ih_entry_count(de->de_ih));

	de->de_entrylen = entry_length(de->de_bh, de->de_ih, de->de_entry_num);
	de->de_namelen = de->de_entrylen - (de_with_sd(deh) ? SD_SIZE : 0);
	de->de_name = B_I_PITEM(de->de_bh, de->de_ih) + deh_location(deh);
	if (de->de_name[de->de_namelen - 1] == 0)
		de->de_namelen = strlen(de->de_name);
}

// what entry points to
static inline void set_de_object_key(struct reiserfs_dir_entry *de)
{
	BUG_ON(de->de_entry_num >= ih_entry_count(de->de_ih));
	de->de_dir_id = deh_dir_id(&(de->de_deh[de->de_entry_num]));
	de->de_objectid = deh_objectid(&(de->de_deh[de->de_entry_num]));
}

static inline void store_de_entry_key(struct reiserfs_dir_entry *de)
{
	struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num;

	BUG_ON(de->de_entry_num >= ih_entry_count(de->de_ih));

	/* store key of the found entry */
	de->de_entry_key.version = KEY_FORMAT_3_5;
	de->de_entry_key.on_disk_key.k_dir_id =
	    le32_to_cpu(de->de_ih->ih_key.k_dir_id);
	de->de_entry_key.on_disk_key.k_objectid =
	    le32_to_cpu(de->de_ih->ih_key.k_objectid);
	set_cpu_key_k_offset(&(de->de_entry_key), deh_offset(deh));
	set_cpu_key_k_type(&(de->de_entry_key), TYPE_DIRENTRY);
}

/* We assign a key to each directory item, and place multiple entries
in a single directory item.  A directory item has a key equal to the
key of the first directory entry in it.

This function first calls search_by_key, then, if item whose first
entry matches is not found it looks for the entry inside directory
item found by search_by_key. Fills the path to the entry, and to the
entry position in the item

*/

/* The function is NOT SCHEDULE-SAFE! */
int search_by_entry_key(struct super_block *sb, const struct cpu_key *key,
			struct treepath *path, struct reiserfs_dir_entry *de)
{
	int retval;

	retval = search_item(sb, key, path);
	switch (retval) {
	case ITEM_NOT_FOUND:
		if (!PATH_LAST_POSITION(path)) {
			reiserfs_error(sb, "vs-7000", "search_by_key "
				       "returned item position == 0");
			pathrelse(path);
			return IO_ERROR;
		}
		PATH_LAST_POSITION(path)--;

	case ITEM_FOUND:
		break;

	case IO_ERROR:
		return retval;

	default:
		pathrelse(path);
		reiserfs_error(sb, "vs-7002", "no path to here");
		return IO_ERROR;
	}

	set_de_item_location(de, path);

#ifdef CONFIG_REISERFS_CHECK
	if (!is_direntry_le_ih(de->de_ih) ||
	    COMP_SHORT_KEYS(&(de->de_ih->ih_key), key)) {
		print_block(de->de_bh, 0, -1, -1);
		reiserfs_panic(sb, "vs-7005", "found item %h is not directory "
			       "item or does not belong to the same directory "
			       "as key %K", de->de_ih, key);
	}
#endif				/* CONFIG_REISERFS_CHECK */

	/* binary search in directory item by third componen t of the
	   key. sets de->de_entry_num of de */
	retval = bin_search_in_dir_item(de, cpu_key_k_offset(key));
	path->pos_in_item = de->de_entry_num;
	if (retval != NAME_NOT_FOUND) {
		// ugly, but rename needs de_bh, de_deh, de_name, de_namelen, de_objectid set
		set_de_name_and_namelen(de);
		set_de_object_key(de);
	}
	return retval;
}

/* Keyed 32-bit hash function using TEA in a Davis-Meyer function */

/* The third component is hashed, and you can choose from more than
   one hash function.  Per directory hashes are not yet implemented
   but are thought about. This function should be moved to hashes.c
   Jedi, please do so.  -Hans */

static __u32 get_third_component(struct super_block *s,
				 const char *name, int len)
{
	__u32 res;

	if (!len || (len == 1 && name[0] == '.'))
		return DOT_OFFSET;
	if (len == 2 && name[0] == '.' && name[1] == '.')
		return DOT_DOT_OFFSET;

	res = REISERFS_SB(s)->s_hash_function(name, len);

	// take bits from 7-th to 30-th including both bounds
	res = GET_HASH_VALUE(res);
	if (res == 0)
		// needed to have no names before "." and ".." those have hash
		// value == 0 and generation conters 1 and 2 accordingly
		res = 128;
	return res + MAX_GENERATION_NUMBER;
}

static int reiserfs_match(struct reiserfs_dir_entry *de,
			  const char *name, int namelen)
{
	int retval = NAME_NOT_FO