namei.c

嵌入式系统设计与实例开发实验教材二源码 多线程应用程序设计 串行端口程序设计 AD接口实验 CAN总线通信实验 GPS通信实验 Linux内核移植与编译实验 IC卡读写实验 SD驱动使

/*
 * 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/config.h>
#include <linux/sched.h>
#include <linux/bitops.h>
#include <linux/reiserfs_fs.h>
#include <linux/smp_lock.h>

#define INC_DIR_INODE_NLINK(i) if (i->i_nlink != 1) { i->i_nlink++; if (i->i_nlink >= REISERFS_LINK_MAX) i->i_nlink=1; }
#define DEC_DIR_INODE_NLINK(i) if (i->i_nlink != 1) i->i_nlink--;

// 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 path * 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;

    if (de->de_entry_num >= ih_entry_count (de->de_ih))
	BUG ();

    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)
{
    if (de->de_entry_num >= ih_entry_count (de->de_ih))
	BUG ();
    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;

    if (de->de_entry_num >= ih_entry_count (de->de_ih))
	BUG ();

    /* 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 path * 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_warning ("vs-7000: search_by_entry_key: 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_warning ("vs-7002: search_by_entry_key: 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: search_by_entry_key: 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 = s->u.reiserfs_sb.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;
}


//
// a portion of this function, particularly the VFS interface portion,
// was derived from minix or ext2's analog and evolved as the
// prototype did. You should be able to tell which portion by looking
// at the ext2 code and comparing. It's subfunctions contain no code
// used as a template unless they are so labeled.
//
static int reiserfs_match (struct reiserfs_dir_entry * de, 
			   const char * name, int namelen)
{
    int retval = NAME_NOT_FOUND;

    if ((namelen == de->de_namelen) &&
	!memcmp(de->de_name, name, de->de_namelen))
	retval = (de_visible (de->de_deh + de->de_entry_num) ? NAME_FOUND : NAME_FOUND_INVISIBLE);

    return retval;
}


/* de's de_bh, de_ih, de_deh, de_item_num, de_entry_num are set already */

				/* used when hash collisions exist */


static int linear_search_in_dir_item (struct cpu_key * key, struct reiserfs_dir_entry * de,
				      const char * name, int namelen)
{
    struct reiserfs_de_head * deh = de->de_deh;
    int retval;
    int i;

    i = de->de_entry_num;

    if (i == I_ENTRY_COUNT (de->de_ih) ||
	GET_HASH_VALUE (deh_offset (deh + i)) != GET_HASH_VALUE (cpu_key_k_offset (key))) {
	i --;
    }

    RFALSE( de->de_deh != B_I_DEH (de->de_bh, de->de_ih),
	    "vs-7010: array of entry headers not found");

    deh += i;

    for (; i >= 0; i --, deh --) {
	if (GET_HASH_VALUE (deh_offset (deh)) !=
	    GET_HASH_VALUE (cpu_key_k_offset (key))) {
	    // hash value does not match, no need to check whole name
	    return NAME_NOT_FOUND;
	}
   
	/* mark, that this generation number is used */
	if (de->de_gen_number_bit_string)
	    set_bit (GET_GENERATION_NUMBER (deh_offset (deh)), de->de_gen_number_bit_string);

	// calculate pointer to name and namelen
	de->de_entry_num = i;
	set_de_name_and_namelen (de);

	if ((retval = reiserfs_match (de, name, namelen)) != NAME_NOT_FOUND) {
	    // de's de_name, de_namelen, de_recordlen are set. Fill the rest:

	    // key of pointed object
	    set_de_object_key (de);

	    store_de_entry_key (de);

	    // retval can be NAME_FOUND or NAME_FOUND_INVISIBLE
	    return retval;
	}
    }

    if (GET_GENERATION_NUMBER (le_ih_k_offset (de->de_ih)) == 0)
	/* we have reached left most entry in the node. In common we
           have to go to the left neighbor, but if generation counter
           is 0 already, we know for sure, that there is no name with
           the same hash value */
	// FIXME: this work correctly only because hash value can not
	// be 0. Btw, in case of Yura's hash it is probably possible,
	// so, this is a bug
	return NAME_NOT_FOUND;

    RFALSE( de->de_item_num,
	    "vs-7015: two diritems of the same directory in one node?");

    return GOTO_PREVIOUS_ITEM;
}


//
// a portion of this function, particularly the VFS interface portion,
// was derived from minix or ext2's analog and evolved as the
// prototype did. You should be able to tell which portion by looking
// at the ext2 code and comparing. It's subfunctions contain no code
// used as a template unless they are so labeled.
//
// may return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND
// FIXME: should add something like IOERROR
static int reiserfs_find_entry (struct inode * dir, const char * name, int namelen, 
				struct path * path_to_entry, struct reiserfs_dir_entry * de)
{
    struct cpu_key key_to_search;
    int retval;


    if (namelen > REISERFS_MAX_NAME_LEN (dir->i_sb->s_blocksize))
	return NAME_NOT_FOUND;

    /* we will search for this key in the tree */
    make_cpu_key (&key_to_search, dir, 
		  get_third_component (dir->i_sb, name, namelen), TYPE_DIRENTRY, 3);

    while (1) {
	retval = search_by_entry_key (dir->i_sb, &key_to_search, path_to_entry, de);
	if (retval == IO_ERROR) {
	    reiserfs_warning ("zam-7001: io error in " __FUNCTION__ "\n");
	    return IO_ERROR;
	}

	/* compare names for all entries having given hash value */
	retval = linear_search_in_dir_item (&key_to_search, de, name, namelen);
	if (retval != GOTO_PREVIOUS_ITEM) {
	    /* there is no need to scan directory anymore. Given entry found or does not exist */
	    path_to_entry->pos_in_item = de->de_entry_num;
	    return retval;
	}

	/* there is left neighboring item of this directory and given entry can be there */
	set_cpu_key_k_offset (&key_to_search, le_ih_k_offset (de->de_ih) - 1);
	pathrelse (path_to_entry);

    } /* while (1) */
}


//
// a portion of this function, particularly the VFS interface portion,
// was derived from minix or ext2's analog and evolved as the
// prototype did. You should be able to tell which portion by looking
// at the ext2 code and comparing. It's subfunctions contain no code
// used as a template unless they are so labeled.
//
static struct dentry * reiserfs_lookup (struct inode * dir, struct dentry * dentry)
{
    int retval;
    struct inode * inode = 0;
    struct reiserfs_dir_entry de;
    INITIALIZE_PATH (path_to_entry);

    reiserfs_check_lock_depth("lookup") ;

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

    de.de_gen_number_bit_string = 0;
    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)) {
	    return ERR_PTR(-EACCES);
        }
    }

    d_add(dentry, inode);
    return NULL;
}

//
// a portion of this function, particularly the VFS interface portion,
// was derived from minix or ext2's analog and evolved as the
// prototype did. You should be able to tell which portion by looking
// at the ext2 code and comparing. It's subfunctions contain no code
// used as a template unless they are so labeled.
//

/* add entry to the directory (entry can be hidden). 

insert definition of when hidden directories are used here -Hans

 Does not mark dir   inode dirty, do it after successesfull call to it */

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;
    int bit_string [MAX_GENERATION_NUMBER / (sizeof(int) * 8) + 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;


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

    if (namelen > REISERFS_MAX_NAME_LEN (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 = reiserfs_kmalloc (buflen, GFP_NOFS, dir->i_sb);
	if (buffer == 0)
	    return -ENOMEM;
    } else
	buffer = small_buf;

    paste_size = (old_format_only (dir->i_sb)) ? (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 */