/*
* 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
#define DCACHE_SIZE 128
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;
}
