//
// $Header: D:/ext2-os2/vfs/RCS/dcache.c,v 1.3 1995/08/16 17:30:16 Willm Exp Willm $
//
// Linux ext2 file system driver for OS/2 2.x and WARP - Allows OS/2 to
// access your Linux ext2fs partitions as normal drive letters.
// OS/2 implementation : Copyright (C) 1995 Matthieu WILLM
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
/*
* 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.
*/
#ifdef OS2
#define INCL_DOS
#define INCL_DOSERRORS
#include <os2.h> // From the "Developer Connection Device Driver Kit" version 2.0
#include <fsh.h>
#include <os2/types.h>
#endif
#include <stddef.h>
#include <linux/fs.h>
#ifndef OS2
#include <linux/string.h>
#endif
#ifdef OS2
#define inline _inline
#endif
/*
* 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;
unsigned long 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 COPYDATA(de, newde) \
memcpy((void *) &newde->dev, (void *) &de->dev, \
4*sizeof(unsigned long) + 1 + DCACHE_NAME_LEN)
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 19
#define hash_fn(dev,dir,namehash) (((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)
{
de->next_lru->prev_lru = de->prev_lru;
de->prev_lru->next_lru = de->next_lru;
}
static inline void add_lru(struct dir_cache_entry * de, struct dir_cache_entry *head)
{
de->next_lru = head;
de->prev_lru = head->prev_lru;
de->prev_lru->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 * *(unsigned char *) name;
}
/*
* Hash queue manipulation. Look out for the casts..
*/
static inline void remove_hash(struct dir_cache_entry * de)
{
if (de->h.next) {
de->h.next->h.prev = de->h.prev;
de->h.prev->h.next = de->h.next;
de->h.next = NULL;
}
}
static inline void add_hash(struct dir_cache_entry * de, struct hash_list * hash)
{
de->h.next = hash->next;
de->h.prev = (struct dir_cache_entry *) hash;
hash->next->h.prev = de;
hash->next = de;
}
/*
* Find a directory cache entry given all the necessary info.
*/
static 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->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->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;
}
