URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [trunk/] [rc203soc/] [sw/] [uClinux/] [fs/] [dcache.c] - Rev 1777
Go to most recent revision | Compare with Previous | Blame | View Log
/* * 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; }
Go to most recent revision | Compare with Previous | Blame | View Log