Subversion Repositories or1k

/*

 *  linux/fs/dcache.c

 *

 *  (C) Copyright 1994 Linus Torvalds

 */

/*

 * The directory cache is a "two-level" cache, each level doing LRU on

 * its entries.  Adding new entries puts them at the end of the LRU

 * queue on the first-level cache, while the second-level cache is

 * fed by any cache hits.

 *

 * The idea is that new additions (from readdir(), for example) will not

 * flush the cache of entries that have really been used.

 *

 * There is a global hash-table over both caches that hashes the entries

 * based on the directory inode number and device as well as on a

 * string-hash computed over the name.

 */

#include <linux/fs.h>

#include <linux/string.h>

/*

 * Don't bother caching long names.. They just take up space in the cache, and

 * for a name cache you just want to cache the "normal" names anyway which tend

 * to be short.

 */

#define DCACHE_NAME_LEN 15

#ifdef CONFIG_REDUCED_MEMORY

#define DCACHE_SIZE 128

#else /* !CONFIG_REDUCED_MEMORY */

#define DCACHE_SIZE 32

#endif /* !CONFIG_REDUCED_MEMORY */

struct hash_list {

        struct dir_cache_entry * next;

        struct dir_cache_entry * prev;

};

/*

 * The dir_cache_entry must be in this order: we do ugly things with the pointers

 */

struct dir_cache_entry {

        struct hash_list h;

        kdev_t dc_dev;

        unsigned long dir;

        unsigned long version;

        unsigned long ino;

        unsigned char name_len;

        char name[DCACHE_NAME_LEN];

        struct dir_cache_entry ** lru_head;

        struct dir_cache_entry * next_lru,  * prev_lru;

};

#define dcache_offset(x) ((unsigned long)&((struct dir_cache_entry*)0)->x)

#define dcache_datalen (dcache_offset(lru_head) - dcache_offset(dc_dev))

#define COPYDATA(de, newde) \

memcpy((void *) &newde->dc_dev, (void *) &de->dc_dev, dcache_datalen)

static struct dir_cache_entry level1_cache[DCACHE_SIZE];

static struct dir_cache_entry level2_cache[DCACHE_SIZE];

/*

 * The LRU-lists are doubly-linked circular lists, and do not change in size

 * so these pointers always have something to point to (after _init)

 */

static struct dir_cache_entry * level1_head;

static struct dir_cache_entry * level2_head;

/*

 * The hash-queues are also doubly-linked circular lists, but the head is

 * itself on the doubly-linked list, not just a pointer to the first entry.

 */

#define DCACHE_HASH_QUEUES 32

#define hash_fn(dev,dir,namehash) ((HASHDEV(dev) ^ (dir) ^ (namehash)) % DCACHE_HASH_QUEUES)

static struct hash_list hash_table[DCACHE_HASH_QUEUES];

static inline void remove_lru(struct dir_cache_entry * de)

{

        struct dir_cache_entry * next = de->next_lru;

        struct dir_cache_entry * prev = de->prev_lru;

        next->prev_lru = prev;

        prev->next_lru = next;

}

static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)

{

        struct dir_cache_entry * prev = head->prev_lru;

        de->next_lru = head;

        de->prev_lru = prev;

        prev->next_lru = de;

        head->prev_lru = de;

}

static inline void update_lru(struct dir_cache_entry * de)

{

        if (de == *de->lru_head)

                *de->lru_head = de->next_lru;

        else {

                remove_lru(de);

                add_lru(de,*de->lru_head);

        }

}

/*

 * Stupid name"hash" algorithm. Write something better if you want to,

 * but I doubt it matters that much

 */

static inline unsigned long namehash(const char * name, int len)

{

        return len +

                ((const unsigned char *) name)[0]+

                ((const unsigned char *) name)[len-1];

}

/*

 * Hash queue manipulation. Look out for the casts..

 */

static inline void remove_hash(struct dir_cache_entry * de)

{

        struct dir_cache_entry * next = de->h.next;

        if (next) {

                struct dir_cache_entry * prev = de->h.prev;

                next->h.prev = prev;

                prev->h.next = next;

                de->h.next = NULL;

        }

}

static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)

{

        struct dir_cache_entry * next = hash->next;

        de->h.next = next;

        de->h.prev = (struct dir_cache_entry *) hash;

        next->h.prev = de;

        hash->next = de;

}

/*

 * Find a directory cache entry given all the necessary info.

 */

static inline struct dir_cache_entry * find_entry(struct inode * dir, const char * name, int len, struct hash_list * hash)

{

        struct dir_cache_entry * de = hash->next;

        for (de = hash->next ; de != (struct dir_cache_entry *) hash ; de = de->h.next) {

                if (de->dc_dev != dir->i_dev)

                        continue;

                if (de->dir != dir->i_ino)

                        continue;

                if (de->version != dir->i_version)

                        continue;

                if (de->name_len != len)

                        continue;

                if (memcmp(de->name, name, len))

                        continue;

                return de;

        }

        return NULL;

}

/*

 * Move a successfully used entry to level2. If already at level2,

 * move it to the end of the LRU queue..

 */

static inline void move_to_level2(struct dir_cache_entry * old_de, struct hash_list * hash)

{

        struct dir_cache_entry * de;

        if (old_de->lru_head == &level2_head) {

                update_lru(old_de);

                return;

        }

        de = level2_head;

        level2_head = de->next_lru;

        remove_hash(de);

        COPYDATA(old_de, de);

        add_hash(de, hash);

}

int dcache_lookup(struct inode * dir, const char * name, int len, unsigned long * ino)

{

        struct hash_list * hash;

        struct dir_cache_entry *de;

        if (len > DCACHE_NAME_LEN)

                return 0;

        hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));

        de = find_entry(dir, name, len, hash);

        if (!de)

                return 0;

        *ino = de->ino;

        move_to_level2(de, hash);

        return 1;

}

void dcache_add(struct inode * dir, const char * name, int len, unsigned long ino)

{

        struct hash_list * hash;

        struct dir_cache_entry *de;

        if (len > DCACHE_NAME_LEN)

                return;

        hash = hash_table + hash_fn(dir->i_dev, dir->i_ino, namehash(name,len));

        if ((de = find_entry(dir, name, len, hash)) != NULL) {

                de->ino = ino;

                update_lru(de);

                return;

        }

        de = level1_head;

        level1_head = de->next_lru;

        remove_hash(de);

        de->dc_dev = dir->i_dev;

        de->dir = dir->i_ino;

        de->version = dir->i_version;

        de->ino = ino;

        de->name_len = len;

        memcpy(de->name, name, len);

        add_hash(de, hash);

}

unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)

{

        int i;

        struct dir_cache_entry * p;

        /*

         * Init level1 LRU lists..

         */

        p = level1_cache;

        do {

                p[1].prev_lru = p;

                p[0].next_lru = p+1;

                p[0].lru_head = &level1_head;

        } while (++p < level1_cache + DCACHE_SIZE-1);

        level1_cache[0].prev_lru = p;

        p[0].next_lru = &level1_cache[0];

        p[0].lru_head = &level1_head;

        level1_head = level1_cache;

        /*

         * Init level2 LRU lists..

         */

        p = level2_cache;

        do {

                p[1].prev_lru = p;

                p[0].next_lru = p+1;

                p[0].lru_head = &level2_head;

        } while (++p < level2_cache + DCACHE_SIZE-1);

        level2_cache[0].prev_lru = p;

        p[0].next_lru = &level2_cache[0];

        p[0].lru_head = &level2_head;

        level2_head = level2_cache;

        /*

         * Empty hash queues..

         */

        for (i = 0 ; i < DCACHE_HASH_QUEUES ; i++)

                hash_table[i].next = hash_table[i].next =

                        (struct dir_cache_entry *) &hash_table[i];

        return mem_start;

}