#include <sys/param.h>
#include <sys/systm.h>
#include <sys/time.h>
#include <sys/mount.h>
#include <sys/vnode.h>
#include <sys/namei.h>
#include <sys/errno.h>
#include <sys/malloc.h>
#define NCHHASH(dvp, hash_val) \
(&nchashtbl[((u_long)(dvp) ^ ((dvp)->v_id ^ (hash_val))) & nchash])
LIST_HEAD(nchashhead, namecache) *nchashtbl;
u_long nchash;
long numcache;
TAILQ_HEAD(, namecache) nclruhead;
struct nchstats nchstats;
u_long nextvnodeid = 0;
int doingcache = 1;
#if DIAGNOSTIC
#define PURGE(ncp) { \
if (ncp->nc_hash.le_prev == 0) \
panic("namecache purge le_prev"); \
if (ncp->nc_hash.le_next == ncp) \
panic("namecache purge le_next"); \
LIST_REMOVE(ncp, nc_hash); \
ncp->nc_hash.le_prev = 0; \
TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
\
remove_name(ncp->nc_name); \
ncp->nc_name = NULL; \
}
#else
#define PURGE(ncp) { \
LIST_REMOVE(ncp, nc_hash); \
ncp->nc_hash.le_prev = 0; \
TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
TAILQ_INSERT_HEAD(&nclruhead, ncp, nc_lru); \
\
remove_name(ncp->nc_name); \
ncp->nc_name = NULL; \
}
#endif
#define TOUCH(ncp) { \
if (ncp->nc_lru.tqe_next != 0) { \
TAILQ_REMOVE(&nclruhead, ncp, nc_lru); \
TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru); \
} \
}
static unsigned int
hash_string(const char *str, int len)
{
unsigned int i, hashval = 0;
if (len == 0) {
for(i=1; *str != 0; i++, str++) {
hashval += (unsigned char)*str * i;
}
} else {
for(i=len; i > 0; i--, str++) {
hashval += (unsigned char)*str * (len - i + 1);
}
}
return hashval;
}
int
cache_lookup(dvp, vpp, cnp)
struct vnode *dvp;
struct vnode **vpp;
struct componentname *cnp;
{
register struct namecache *ncp, *nnp;
register struct nchashhead *ncpp;
register long namelen = cnp->cn_namelen;
char *nameptr = cnp->cn_nameptr;
if (!doingcache) {
cnp->cn_flags &= ~MAKEENTRY;
return (0);
}
ncpp = NCHHASH(dvp, cnp->cn_hash);
for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
nnp = ncp->nc_hash.le_next;
if (ncp->nc_dvp == dvp &&
strncmp(ncp->nc_name, nameptr, namelen) == 0 &&
ncp->nc_name[namelen] == 0) {
if ((ncp->nc_dvpid != dvp->v_id) ||
(ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id)) {
nchstats.ncs_falsehits++;
PURGE(ncp);
continue;
}
break;
}
}
if (ncp == 0) {
nchstats.ncs_miss++;
return (0);
}
if ((cnp->cn_flags & MAKEENTRY) == 0) {
nchstats.ncs_badhits++;
PURGE(ncp);
return (0);
}
if (ncp->nc_vp) {
if (ncp->nc_vp->v_flag & (VUINIT|VXLOCK|VTERMINATE|VORECLAIM)) {
PURGE(ncp);
return (0);
}
nchstats.ncs_goodhits++;
TOUCH(ncp);
*vpp = ncp->nc_vp;
return (-1);
}
if (cnp->cn_nameiop == CREATE) {
nchstats.ncs_badhits++;
PURGE(ncp);
return (0);
}
nchstats.ncs_neghits++;
TOUCH(ncp);
cnp->cn_flags |= ncp->nc_vpid;
return (ENOENT);
}
void
cache_enter(dvp, vp, cnp)
struct vnode *dvp;
struct vnode *vp;
struct componentname *cnp;
{
register struct namecache *ncp;
register struct nchashhead *ncpp;
if (!doingcache)
return;
if (numcache < desiredvnodes &&
((ncp = nclruhead.tqh_first) == NULL ||
ncp->nc_hash.le_prev != 0)) {
ncp = (struct namecache *)
_MALLOC_ZONE((u_long)sizeof *ncp, M_CACHE, M_WAITOK);
numcache++;
} else if (ncp = nclruhead.tqh_first) {
TAILQ_REMOVE(&nclruhead, ncp, nc_lru);
if (ncp->nc_hash.le_prev != 0) {
#if DIAGNOSTIC
if (ncp->nc_hash.le_next == ncp)
panic("cache_enter: le_next");
#endif
LIST_REMOVE(ncp, nc_hash);
remove_name(ncp->nc_name);
ncp->nc_name = NULL;
ncp->nc_hash.le_prev = 0;
}
} else {
return;
}
ncp->nc_vp = vp;
if (vp)
ncp->nc_vpid = vp->v_id;
else
ncp->nc_vpid = cnp->cn_flags & ISWHITEOUT;
ncp->nc_dvp = dvp;
ncp->nc_dvpid = dvp->v_id;
ncp->nc_name = add_name(cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_hash, 0);
TAILQ_INSERT_TAIL(&nclruhead, ncp, nc_lru);
ncpp = NCHHASH(dvp, cnp->cn_hash);
#if DIAGNOSTIC
{
register struct namecache *p;
for (p = ncpp->lh_first; p != 0; p = p->nc_hash.le_next)
if (p == ncp)
panic("cache_enter: duplicate");
}
#endif
LIST_INSERT_HEAD(ncpp, ncp, nc_hash);
}
void
nchinit()
{
static void init_string_table(void);
TAILQ_INIT(&nclruhead);
nchashtbl = hashinit(MAX(4096, desiredvnodes), M_CACHE, &nchash);
init_string_table();
}
int
resize_namecache(u_int newsize)
{
struct nchashhead *new_table;
struct nchashhead *old_table;
struct nchashhead *old_head, *head;
struct namecache *entry, *next;
uint32_t i;
u_long new_mask, old_mask;
if (newsize < nchash) {
return 0;
}
new_table = hashinit(newsize, M_CACHE, &new_mask);
if (new_table == NULL) {
return ENOMEM;
}
old_table = nchashtbl;
nchashtbl = new_table;
old_mask = nchash;
nchash = new_mask;
for(i=0; i <= old_mask; i++) {
old_head = &old_table[i];
for (entry=old_head->lh_first; entry != NULL; entry=next) {
head = NCHHASH(entry->nc_dvp, hash_string(entry->nc_name, 0));
next = entry->nc_hash.le_next;
LIST_INSERT_HEAD(head, entry, nc_hash);
}
}
FREE(old_table, M_CACHE);
return 0;
}
void
cache_purge(vp)
struct vnode *vp;
{
struct namecache *ncp;
struct nchashhead *ncpp;
vp->v_id = ++nextvnodeid;
if (nextvnodeid != 0)
return;
for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
while (ncp = ncpp->lh_first)
PURGE(ncp);
}
vp->v_id = ++nextvnodeid;
}
void
cache_purgevfs(mp)
struct mount *mp;
{
struct nchashhead *ncpp;
struct namecache *ncp, *nnp;
for (ncpp = &nchashtbl[nchash]; ncpp >= nchashtbl; ncpp--) {
for (ncp = ncpp->lh_first; ncp != 0; ncp = nnp) {
nnp = ncp->nc_hash.le_next;
if (ncp->nc_dvpid != ncp->nc_dvp->v_id ||
(ncp->nc_vp && ncp->nc_vpid != ncp->nc_vp->v_id) ||
ncp->nc_dvp->v_mount == mp) {
PURGE(ncp);
}
}
}
}
static LIST_HEAD(stringhead, string_t) *string_ref_table;
static u_long string_table_mask;
static uint32_t max_chain_len=0;
static struct stringhead *long_chain_head=NULL;
static uint32_t filled_buckets=0;
static uint32_t num_dups=0;
static uint32_t nstrings=0;
typedef struct string_t {
LIST_ENTRY(string_t) hash_chain;
unsigned char *str;
uint32_t refcount;
} string_t;
static int
resize_string_ref_table()
{
struct stringhead *new_table;
struct stringhead *old_table;
struct stringhead *old_head, *head;
string_t *entry, *next;
uint32_t i, hashval;
u_long new_mask, old_mask;
new_table = hashinit((string_table_mask + 1) * 2, M_CACHE, &new_mask);
if (new_table == NULL) {
return ENOMEM;
}
old_table = string_ref_table;
string_ref_table = new_table;
old_mask = string_table_mask;
string_table_mask = new_mask;
printf("resize: max chain len %d, new table size %d\n",
max_chain_len, new_mask + 1);
max_chain_len = 0;
long_chain_head = NULL;
filled_buckets = 0;
for(i=0; i <= old_mask; i++) {
old_head = &old_table[i];
for (entry=old_head->lh_first; entry != NULL; entry=next) {
hashval = hash_string(entry->str, 0);
head = &string_ref_table[hashval & string_table_mask];
if (head->lh_first == NULL) {
filled_buckets++;
}
next = entry->hash_chain.le_next;
LIST_INSERT_HEAD(head, entry, hash_chain);
}
}
FREE(old_table, M_CACHE);
return 0;
}
static void
init_string_table(void)
{
string_ref_table = hashinit(4096, M_CACHE, &string_table_mask);
}
char *
add_name(const char *name, size_t len, u_int hashval, u_int flags)
{
struct stringhead *head;
string_t *entry;
int chain_len = 0;
if (4*filled_buckets >= ((string_table_mask + 1) * 3)) {
if (resize_string_ref_table() != 0) {
printf("failed to resize the hash table.\n");
}
}
if (hashval == 0) {
hashval = hash_string(name, len);
}
head = &string_ref_table[hashval & string_table_mask];
for (entry=head->lh_first; entry != NULL; chain_len++, entry=entry->hash_chain.le_next) {
if (strncmp(entry->str, name, len) == 0 && entry->str[len] == '\0') {
entry->refcount++;
num_dups++;
break;
}
}
if (entry == NULL) {
MALLOC(entry, string_t *, sizeof(string_t) + len + 1, M_TEMP, M_WAITOK);
head = &string_ref_table[hashval & string_table_mask];
if (head->lh_first == NULL) {
filled_buckets++;
}
LIST_INSERT_HEAD(head, entry, hash_chain);
entry->str = (char *)((char *)entry + sizeof(string_t));
strncpy(entry->str, name, len);
entry->str[len] = '\0';
entry->refcount = 1;
if (chain_len > max_chain_len) {
max_chain_len = chain_len;
long_chain_head = head;
}
nstrings++;
}
return entry->str;
}
int
remove_name(const char *nameref)
{
struct stringhead *head;
string_t *entry;
uint32_t hashval;
hashval = hash_string(nameref, 0);
head = &string_ref_table[hashval & string_table_mask];
for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
if (entry->str == (unsigned char *)nameref) {
entry->refcount--;
if (entry->refcount == 0) {
LIST_REMOVE(entry, hash_chain);
if (head->lh_first == NULL) {
filled_buckets--;
}
entry->str = NULL;
nstrings--;
FREE(entry, M_TEMP);
} else {
num_dups--;
}
return 0;
}
}
return ENOENT;
}
void
dump_string_table(void)
{
struct stringhead *head;
string_t *entry;
int i;
for(i=0; i <= string_table_mask; i++) {
head = &string_ref_table[i];
for (entry=head->lh_first; entry != NULL; entry=entry->hash_chain.le_next) {
printf("%6d - %s\n", entry->refcount, entry->str);
}
}
}