[hcoop/debian/openafs.git] / src / afs / afs_osidnlc.c

/*
 * Copyright 2000, International Business Machines Corporation and others.
 * All Rights Reserved.
 *
 * This software has been released under the terms of the IBM Public
 * License.  For details, see the LICENSE file in the top-level source
 * directory or online at http://www.openafs.org/dl/license10.html
 */

/*-
 * OSI Directory Name Lookup Cache
 *
 * Keep a local cache of lookup results to avoid needing to examine the disk
 * cache, for frequently accessed names.
 */

#include <afsconfig.h>
#include "afs/param.h"


#include "afs/sysincludes.h"	/*Standard vendor system headers */
#include "afsincludes.h"	/*AFS-based standard headers */
#include "afs/afs.h"
#include "afs/lock.h"
#include "afs/afs_stats.h"
#include "afs/afs_osidnlc.h"

/* Things to do:
 *    also cache failed lookups.
 *    look into interactions of dnlc and readdir.
 *    cache larger names, perhaps by using a better,longer key (SHA) and discarding
 *    the actual name itself.
 *    precompute a key and stuff for \sys, and combine the HandleAtName function with
 *    this, since we're looking at the name anyway.
 */

struct afs_lock afs_xdnlc;
extern struct afs_lock afs_xvcache;

dnlcstats_t dnlcstats;

#define NCSIZE 4096
#define NHSIZE 256		/* must be power of 2. == NHASHENT in dir package */
struct nc *ncfreelist = NULL;
static struct nc nameCache[NCSIZE];
struct nc *nameHash[NHSIZE];
/* Hash table invariants:
 *     1.  If nameHash[i] is NULL, list is empty
 *     2.  A single element in a hash bucket has itself as prev and next.
 */

typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
    ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
    osi_dnlc_purgevpT, osi_dnlc_purgeT
} traceevt;

int afs_usednlc = 1;

struct dt {
    traceevt event;
    unsigned char slot;
};

struct dt dnlctracetable[256];
int dnlct;

#define TRACE(e,s)		/* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */

#define dnlcHash(ts, hval) for (hval=0; *ts; ts++) { hval *= 173;  hval  += *ts;   }

static struct nc *
GetMeAnEntry(void)
{
    static unsigned int nameptr = 0;	/* next bucket to pull something from */
    struct nc *tnc;
    int j;

    if (ncfreelist) {
	tnc = ncfreelist;
	ncfreelist = tnc->next;
	return tnc;
    }

    for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
	if (nameptr >= NHSIZE)
	    nameptr = 0;
	if (nameHash[nameptr])
	    break;
    }

    if (nameptr >= NHSIZE)
	nameptr = 0;

    TRACE(ScavengeEntryT, nameptr);
    tnc = nameHash[nameptr];
    if (!tnc)			/* May want to consider changing this to return 0 */
	osi_Panic("null tnc in GetMeAnEntry");

    if (tnc->prev == tnc) {	/* only thing in list, don't screw around */
	nameHash[nameptr] = NULL;
	return (tnc);
    }

    tnc = tnc->prev;		/* grab oldest one in this bucket */
    /* remove it from list */
    tnc->next->prev = tnc->prev;
    tnc->prev->next = tnc->next;

    return (tnc);
}

static void
InsertEntry(struct nc *tnc)
{
    unsigned int key;
    key = tnc->key & (NHSIZE - 1);

    TRACE(InsertEntryT, key);
    if (!nameHash[key]) {
	nameHash[key] = tnc;
	tnc->next = tnc->prev = tnc;
    } else {
	tnc->next = nameHash[key];
	tnc->prev = tnc->next->prev;
	tnc->next->prev = tnc;
	tnc->prev->next = tnc;
	nameHash[key] = tnc;
    }
}


int
osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
	       afs_hyper_t * avno)
{
    struct nc *tnc;
    unsigned int key, skey;
    char *ts = aname;
    int safety;

    if (!afs_usednlc)
	return 0;

    TRACE(osi_dnlc_enterT, 0);
    dnlcHash(ts, key);		/* leaves ts pointing at the NULL */
    if (ts - aname >= AFSNCNAMESIZE) {
	return 0;
    }
    skey = key & (NHSIZE - 1);
    dnlcstats.enters++;

  retry:
    ObtainWriteLock(&afs_xdnlc, 222);

    /* Only cache entries from the latest version of the directory */
    if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
	ReleaseWriteLock(&afs_xdnlc);
	return 0;
    }

    /*
     * Make sure each directory entry gets cached no more than once.
     */
    for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
	if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
	    /* duplicate entry */
	    break;
	} else if (tnc->next == nameHash[skey]) {	/* end of list */
	    tnc = NULL;
	    break;
	} else if (safety > NCSIZE) {
	    afs_warn("DNLC cycle");
	    dnlcstats.cycles++;
	    ReleaseWriteLock(&afs_xdnlc);
	    osi_dnlc_purge();
	    goto retry;
	}
    }

    if (tnc == NULL) {
	tnc = GetMeAnEntry();

	tnc->dirp = adp;
	tnc->vp = avc;
	tnc->key = key;
	memcpy((char *)tnc->name, aname, ts - aname + 1);	/* include the NULL */

	InsertEntry(tnc);
    } else {
	/* duplicate */
	tnc->vp = avc;
    }
    ReleaseWriteLock(&afs_xdnlc);

    return 0;
}


struct vcache *
osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
{
    struct vcache *tvc;
    unsigned int key, skey;
    char *ts = aname;
    struct nc *tnc;
    int safety;
#ifdef AFS_DARWIN80_ENV
    vnode_t tvp;
#endif

    if (!afs_usednlc)
      return 0;

    dnlcHash(ts, key);		/* leaves ts pointing at the NULL */
    if (ts - aname >= AFSNCNAMESIZE)
      return 0;
    skey = key & (NHSIZE - 1);

    TRACE(osi_dnlc_lookupT, skey);
    dnlcstats.lookups++;

    ObtainReadLock(&afs_xvcache);
    ObtainReadLock(&afs_xdnlc);

    for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
	 tnc = tnc->next, safety++) {
	if ( /* (tnc->key == key)  && */ (tnc->dirp == adp)
	    && (!strcmp((char *)tnc->name, aname))) {
	    tvc = tnc->vp;
	    break;
	} else if (tnc->next == nameHash[skey]) {	/* end of list */
	    break;
	} else if (safety > NCSIZE) {
	    afs_warn("DNLC cycle");
	    dnlcstats.cycles++;
	    ReleaseReadLock(&afs_xdnlc);
	    ReleaseReadLock(&afs_xvcache);
	    osi_dnlc_purge();
	    return (0);
	}
    }

    ReleaseReadLock(&afs_xdnlc);

    if (!tvc) {
	ReleaseReadLock(&afs_xvcache);
	dnlcstats.misses++;
    } else {
	if ((tvc->f.states & CVInit)
#ifdef  AFS_DARWIN80_ENV
	    ||(tvc->f.states & CDeadVnode)
#endif
	    )
	{
	    ReleaseReadLock(&afs_xvcache);
	    dnlcstats.misses++;
	    osi_dnlc_remove(adp, aname, tvc);
	    return 0;
	}
#if defined(AFS_DARWIN80_ENV)
	tvp = AFSTOV(tvc);
	if (vnode_get(tvp)) {
	    ReleaseReadLock(&afs_xvcache);
	    dnlcstats.misses++;
	    osi_dnlc_remove(adp, aname, tvc);
	    return 0;
	}
	if (vnode_ref(tvp)) {
	    ReleaseReadLock(&afs_xvcache);
	    AFS_GUNLOCK();
	    vnode_put(tvp);
	    AFS_GLOCK();
	    dnlcstats.misses++;
	    osi_dnlc_remove(adp, aname, tvc);
	    return 0;
	}
#else
	osi_vnhold(tvc, 0);
#endif
	ReleaseReadLock(&afs_xvcache);

    }

    return tvc;
}


static void
RemoveEntry(struct nc *tnc, unsigned int key)
{
    if (!tnc->prev)		/* things on freelist always have null prev ptrs */
	osi_Panic("bogus free list");

    TRACE(RemoveEntryT, key);
    if (tnc == tnc->next) {	/* only one in list */
	nameHash[key] = NULL;
    } else {
	if (tnc == nameHash[key])
	    nameHash[key] = tnc->next;
	tnc->prev->next = tnc->next;
	tnc->next->prev = tnc->prev;
    }

    tnc->prev = NULL;		/* everything not in hash table has 0 prev */
    tnc->key = 0;		/* just for safety's sake */
}


int
osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
{
    unsigned int key, skey;
    char *ts = aname;
    struct nc *tnc;

    if (!afs_usednlc)
	return 0;

    TRACE(osi_dnlc_removeT, skey);
    dnlcHash(ts, key);		/* leaves ts pointing at the NULL */
    if (ts - aname >= AFSNCNAMESIZE) {
	return 0;
    }
    skey = key & (NHSIZE - 1);
    TRACE(osi_dnlc_removeT, skey);
    dnlcstats.removes++;
    ObtainReadLock(&afs_xdnlc);

    for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
	if ((tnc->dirp == adp) && (tnc->key == key)
	    && (!strcmp((char *)tnc->name, aname))) {
	    tnc->dirp = NULL;	/* now it won't match anything */
	    break;
	} else if (tnc->next == nameHash[skey]) {	/* end of list */
	    tnc = NULL;
	    break;
	}
    }
    ReleaseReadLock(&afs_xdnlc);

    if (!tnc)
	return 0;

    /* there is a little race condition here, but it's relatively
     * harmless.  At worst, I wind up removing a mapping that I just
     * created. */
    if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
	return 0;		/* no big deal, tnc will get recycled eventually */
    }
    RemoveEntry(tnc, skey);
    tnc->next = ncfreelist;
    ncfreelist = tnc;
    ReleaseWriteLock(&afs_xdnlc);

    return 0;
}

/*!
 * Remove anything pertaining to this directory.  I can invalidate
 * things without the lock, since I am just looking through the array,
 * but to move things off the lists or into the freelist, I need the
 * write lock
 *
 * \param adp vcache entry for the directory to be purged.
 * \return 0
 */
int
osi_dnlc_purgedp(struct vcache *adp)
{
    int i;
    int writelocked;

#ifdef AFS_DARWIN_ENV
    if (!(adp->f.states & (CVInit | CVFlushed
#ifdef AFS_DARWIN80_ENV
                        | CDeadVnode
#endif
        )) && AFSTOV(adp))
    cache_purge(AFSTOV(adp));
#endif

    if (!afs_usednlc)
	return 0;

    dnlcstats.purgeds++;
    TRACE(osi_dnlc_purgedpT, 0);
    writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));

    for (i = 0; i < NCSIZE; i++) {
	if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
	    nameCache[i].dirp = nameCache[i].vp = NULL;
	    if (writelocked && nameCache[i].prev) {
		RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
		nameCache[i].next = ncfreelist;
		ncfreelist = &nameCache[i];
	    }
	}
    }
    if (writelocked)
	ReleaseWriteLock(&afs_xdnlc);

    return 0;
}

/*!
 * Remove anything pertaining to this file
 *
 * \param File vcache entry.
 * \return 0
 */
int
osi_dnlc_purgevp(struct vcache *avc)
{
    int i;
    int writelocked;

#ifdef AFS_DARWIN_ENV
    if (!(avc->f.states & (CVInit | CVFlushed
#ifdef AFS_DARWIN80_ENV
                        | CDeadVnode
#endif
        )) && AFSTOV(avc))
    cache_purge(AFSTOV(avc));
#endif

    if (!afs_usednlc)
	return 0;

    dnlcstats.purgevs++;
    TRACE(osi_dnlc_purgevpT, 0);
    writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));

    for (i = 0; i < NCSIZE; i++) {
	if (nameCache[i].vp == avc) {
	    nameCache[i].dirp = nameCache[i].vp = NULL;
	    /* can't simply break; because of hard links -- might be two */
	    /* different entries with same vnode */
	    if (writelocked && nameCache[i].prev) {
		RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
		nameCache[i].next = ncfreelist;
		ncfreelist = &nameCache[i];
	    }
	}
    }
    if (writelocked)
	ReleaseWriteLock(&afs_xdnlc);

    return 0;
}

/* remove everything */
int
osi_dnlc_purge(void)
{
    int i;

    dnlcstats.purges++;
    TRACE(osi_dnlc_purgeT, 0);
    if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) {	/* couldn't get lock */
	for (i = 0; i < NCSIZE; i++)
	    nameCache[i].dirp = nameCache[i].vp = NULL;
    } else {			/* did get the lock */
	ncfreelist = NULL;
	memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
	memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
	for (i = 0; i < NCSIZE; i++) {
	    nameCache[i].next = ncfreelist;
	    ncfreelist = &nameCache[i];
	}
	ReleaseWriteLock(&afs_xdnlc);
    }

    return 0;
}

/* remove everything referencing a specific volume */
int
osi_dnlc_purgevol(struct VenusFid *fidp)
{

    dnlcstats.purgevols++;
    osi_dnlc_purge();

    return 0;
}

int
osi_dnlc_init(void)
{
    int i;

    Lock_Init(&afs_xdnlc);
    memset(&dnlcstats, 0, sizeof(dnlcstats));
    memset(dnlctracetable, 0, sizeof(dnlctracetable));
    dnlct = 0;
    ObtainWriteLock(&afs_xdnlc, 223);
    ncfreelist = NULL;
    memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
    memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
    for (i = 0; i < NCSIZE; i++) {
	nameCache[i].next = ncfreelist;
	ncfreelist = &nameCache[i];
    }
    ReleaseWriteLock(&afs_xdnlc);

    return 0;
}

int
osi_dnlc_shutdown(void)
{
    return 0;
}
Commit	Line	Data
805e021f CE	1	/*
	2	* Copyright 2000, International Business Machines Corporation and others.
	3	* All Rights Reserved.
	4	*
	5	* This software has been released under the terms of the IBM Public
	6	* License. For details, see the LICENSE file in the top-level source
	7	* directory or online at http://www.openafs.org/dl/license10.html
	8	*/
	9
	10	/*-
	11	* OSI Directory Name Lookup Cache
	12	*
	13	* Keep a local cache of lookup results to avoid needing to examine the disk
	14	* cache, for frequently accessed names.
	15	*/
	16
	17	#include <afsconfig.h>
	18	#include "afs/param.h"
	19
	20
	21	#include "afs/sysincludes.h" /Standard vendor system headers /
	22	#include "afsincludes.h" /AFS-based standard headers /
	23	#include "afs/afs.h"
	24	#include "afs/lock.h"
	25	#include "afs/afs_stats.h"
	26	#include "afs/afs_osidnlc.h"
	27
	28	/* Things to do:
	29	* also cache failed lookups.
	30	* look into interactions of dnlc and readdir.
	31	* cache larger names, perhaps by using a better,longer key (SHA) and discarding
	32	* the actual name itself.
	33	* precompute a key and stuff for \sys, and combine the HandleAtName function with
	34	* this, since we're looking at the name anyway.
	35	*/
	36
	37	struct afs_lock afs_xdnlc;
	38	extern struct afs_lock afs_xvcache;
	39
	40	dnlcstats_t dnlcstats;
	41
	42	#define NCSIZE 4096
	43	#define NHSIZE 256 /* must be power of 2. == NHASHENT in dir package */
	44	struct nc *ncfreelist = NULL;
	45	static struct nc nameCache[NCSIZE];
	46	struct nc *nameHash[NHSIZE];
	47	/* Hash table invariants:
	48	* 1. If nameHash[i] is NULL, list is empty
	49	* 2. A single element in a hash bucket has itself as prev and next.
	50	*/
	51
	52	typedef enum { osi_dnlc_enterT, InsertEntryT, osi_dnlc_lookupT,
	53	ScavengeEntryT, osi_dnlc_removeT, RemoveEntryT, osi_dnlc_purgedpT,
	54	osi_dnlc_purgevpT, osi_dnlc_purgeT
	55	} traceevt;
	56
	57	int afs_usednlc = 1;
	58
	59	struct dt {
	60	traceevt event;
	61	unsigned char slot;
	62	};
	63
	64	struct dt dnlctracetable[256];
65	int dnlct;
66
67	#define TRACE(e,s) /* if (dnlct == 256) dnlct = 0; dnlctracetable[dnlct].event = e; dnlctracetable[dnlct++].slot = s; */
68
69	#define dnlcHash(ts, hval) for (hval=0; ts; ts++) { hval = 173; hval += *ts; }
70
71	static struct nc *
72	GetMeAnEntry(void)
73	{
74	static unsigned int nameptr = 0; /* next bucket to pull something from */
75	struct nc *tnc;
76	int j;
77
78	if (ncfreelist) {
79	tnc = ncfreelist;
80	ncfreelist = tnc->next;
81	return tnc;
82	}
83
84	for (j = 0; j < NHSIZE + 2; j++, nameptr++) {
85	if (nameptr >= NHSIZE)
86	nameptr = 0;
87	if (nameHash[nameptr])
88	break;
89	}
90
91	if (nameptr >= NHSIZE)
92	nameptr = 0;
93
94	TRACE(ScavengeEntryT, nameptr);
95	tnc = nameHash[nameptr];
96	if (!tnc) /* May want to consider changing this to return 0 */
97	osi_Panic("null tnc in GetMeAnEntry");
98
99	if (tnc->prev == tnc) { /* only thing in list, don't screw around */
100	nameHash[nameptr] = NULL;
101	return (tnc);
102	}
103
104	tnc = tnc->prev; /* grab oldest one in this bucket */
105	/* remove it from list */
106	tnc->next->prev = tnc->prev;
107	tnc->prev->next = tnc->next;
108
109	return (tnc);
110	}
111
112	static void
113	InsertEntry(struct nc *tnc)
114	{
115	unsigned int key;
116	key = tnc->key & (NHSIZE - 1);
117
118	TRACE(InsertEntryT, key);
119	if (!nameHash[key]) {
120	nameHash[key] = tnc;
121	tnc->next = tnc->prev = tnc;
122	} else {
123	tnc->next = nameHash[key];
124	tnc->prev = tnc->next->prev;
125	tnc->next->prev = tnc;
126	tnc->prev->next = tnc;
127	nameHash[key] = tnc;
128	}
129	}
130
131
132	int
133	osi_dnlc_enter(struct vcache adp, char aname, struct vcache *avc,
134	afs_hyper_t * avno)
135	{
136	struct nc *tnc;
137	unsigned int key, skey;
138	char *ts = aname;
139	int safety;
140
141	if (!afs_usednlc)
142	return 0;
143
144	TRACE(osi_dnlc_enterT, 0);
145	dnlcHash(ts, key); /* leaves ts pointing at the NULL */
146	if (ts - aname >= AFSNCNAMESIZE) {
147	return 0;
148	}
149	skey = key & (NHSIZE - 1);
150	dnlcstats.enters++;
151
152	retry:
153	ObtainWriteLock(&afs_xdnlc, 222);
154
155	/* Only cache entries from the latest version of the directory */
156	if (!(adp->f.states & CStatd) \|\| !hsame(*avno, adp->f.m.DataVersion)) {
157	ReleaseWriteLock(&afs_xdnlc);
158	return 0;
159	}
160
161	/*
162	* Make sure each directory entry gets cached no more than once.
163	*/
164	for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
165	if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
166	/* duplicate entry */
167	break;
168	} else if (tnc->next == nameHash[skey]) { /* end of list */
169	tnc = NULL;
170	break;
171	} else if (safety > NCSIZE) {
172	afs_warn("DNLC cycle");
173	dnlcstats.cycles++;
174	ReleaseWriteLock(&afs_xdnlc);
175	osi_dnlc_purge();
176	goto retry;
177	}
178	}
179
180	if (tnc == NULL) {
181	tnc = GetMeAnEntry();
182
183	tnc->dirp = adp;
184	tnc->vp = avc;
185	tnc->key = key;
186	memcpy((char )tnc->name, aname, ts - aname + 1); / include the NULL */
187
188	InsertEntry(tnc);
189	} else {
190	/* duplicate */
191	tnc->vp = avc;
192	}
193	ReleaseWriteLock(&afs_xdnlc);
194
195	return 0;
196	}
197
198
199	struct vcache *
200	osi_dnlc_lookup(struct vcache adp, char aname, int locktype)
201	{
202	struct vcache *tvc;
203	unsigned int key, skey;
204	char *ts = aname;
205	struct nc *tnc;
206	int safety;
207	#ifdef AFS_DARWIN80_ENV
208	vnode_t tvp;
209	#endif
210
211	if (!afs_usednlc)
212	return 0;
213
214	dnlcHash(ts, key); /* leaves ts pointing at the NULL */
215	if (ts - aname >= AFSNCNAMESIZE)
216	return 0;
217	skey = key & (NHSIZE - 1);
218
219	TRACE(osi_dnlc_lookupT, skey);
220	dnlcstats.lookups++;
221
222	ObtainReadLock(&afs_xvcache);
223	ObtainReadLock(&afs_xdnlc);
224
225	for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
226	tnc = tnc->next, safety++) {
227	if ( /* (tnc->key == key) && */ (tnc->dirp == adp)
228	&& (!strcmp((char *)tnc->name, aname))) {
229	tvc = tnc->vp;
230	break;
231	} else if (tnc->next == nameHash[skey]) { /* end of list */
232	break;
233	} else if (safety > NCSIZE) {
234	afs_warn("DNLC cycle");
235	dnlcstats.cycles++;
236	ReleaseReadLock(&afs_xdnlc);
237	ReleaseReadLock(&afs_xvcache);
238	osi_dnlc_purge();
239	return (0);
240	}
241	}
242
243	ReleaseReadLock(&afs_xdnlc);
244
245	if (!tvc) {
246	ReleaseReadLock(&afs_xvcache);
247	dnlcstats.misses++;
248	} else {
249	if ((tvc->f.states & CVInit)
250	#ifdef AFS_DARWIN80_ENV
251	\|\|(tvc->f.states & CDeadVnode)
252	#endif
253	)
254	{
255	ReleaseReadLock(&afs_xvcache);
256	dnlcstats.misses++;
257	osi_dnlc_remove(adp, aname, tvc);
258	return 0;
259	}
260	#if defined(AFS_DARWIN80_ENV)
261	tvp = AFSTOV(tvc);
262	if (vnode_get(tvp)) {
263	ReleaseReadLock(&afs_xvcache);
264	dnlcstats.misses++;
265	osi_dnlc_remove(adp, aname, tvc);
266	return 0;
267	}
268	if (vnode_ref(tvp)) {
269	ReleaseReadLock(&afs_xvcache);
270	AFS_GUNLOCK();
271	vnode_put(tvp);
272	AFS_GLOCK();
273	dnlcstats.misses++;
274	osi_dnlc_remove(adp, aname, tvc);
275	return 0;
276	}
277	#else
278	osi_vnhold(tvc, 0);
279	#endif
280	ReleaseReadLock(&afs_xvcache);
281
282	}
283
284	return tvc;
285	}
286
287
288	static void
289	RemoveEntry(struct nc *tnc, unsigned int key)
290	{
291	if (!tnc->prev) /* things on freelist always have null prev ptrs */
292	osi_Panic("bogus free list");
293
294	TRACE(RemoveEntryT, key);
295	if (tnc == tnc->next) { /* only one in list */
296	nameHash[key] = NULL;
297	} else {
298	if (tnc == nameHash[key])
299	nameHash[key] = tnc->next;
300	tnc->prev->next = tnc->next;
301	tnc->next->prev = tnc->prev;
302	}
303
304	tnc->prev = NULL; /* everything not in hash table has 0 prev */
305	tnc->key = 0; /* just for safety's sake */
306	}
307
308
309	int
310	osi_dnlc_remove(struct vcache adp, char aname, struct vcache *avc)
311	{
312	unsigned int key, skey;
313	char *ts = aname;
314	struct nc *tnc;
315
316	if (!afs_usednlc)
317	return 0;
318
319	TRACE(osi_dnlc_removeT, skey);
320	dnlcHash(ts, key); /* leaves ts pointing at the NULL */
321	if (ts - aname >= AFSNCNAMESIZE) {
322	return 0;
323	}
324	skey = key & (NHSIZE - 1);
325	TRACE(osi_dnlc_removeT, skey);
326	dnlcstats.removes++;
327	ObtainReadLock(&afs_xdnlc);
328
329	for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
330	if ((tnc->dirp == adp) && (tnc->key == key)
331	&& (!strcmp((char *)tnc->name, aname))) {
332	tnc->dirp = NULL; /* now it won't match anything */
333	break;
334	} else if (tnc->next == nameHash[skey]) { /* end of list */
335	tnc = NULL;
336	break;
337	}
338	}
339	ReleaseReadLock(&afs_xdnlc);
340
341	if (!tnc)
342	return 0;
343
344	/* there is a little race condition here, but it's relatively
345	* harmless. At worst, I wind up removing a mapping that I just
346	* created. */
347	if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
348	return 0; /* no big deal, tnc will get recycled eventually */
349	}
350	RemoveEntry(tnc, skey);
351	tnc->next = ncfreelist;
352	ncfreelist = tnc;
353	ReleaseWriteLock(&afs_xdnlc);
354
355	return 0;
356	}
357
358	/*!
359	* Remove anything pertaining to this directory. I can invalidate
360	* things without the lock, since I am just looking through the array,
361	* but to move things off the lists or into the freelist, I need the
362	* write lock
363	*
364	* \param adp vcache entry for the directory to be purged.
365	* \return 0
366	*/
367	int
368	osi_dnlc_purgedp(struct vcache *adp)
369	{
370	int i;
371	int writelocked;
372
373	#ifdef AFS_DARWIN_ENV
374	if (!(adp->f.states & (CVInit \| CVFlushed
375	#ifdef AFS_DARWIN80_ENV
376	\| CDeadVnode
377	#endif
378	)) && AFSTOV(adp))
379	cache_purge(AFSTOV(adp));
380	#endif
381
382	if (!afs_usednlc)
383	return 0;
384
385	dnlcstats.purgeds++;
386	TRACE(osi_dnlc_purgedpT, 0);
387	writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
388
389	for (i = 0; i < NCSIZE; i++) {
390	if ((nameCache[i].dirp == adp) \|\| (nameCache[i].vp == adp)) {
391	nameCache[i].dirp = nameCache[i].vp = NULL;
392	if (writelocked && nameCache[i].prev) {
393	RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
394	nameCache[i].next = ncfreelist;
395	ncfreelist = &nameCache[i];
396	}
397	}
398	}
399	if (writelocked)
400	ReleaseWriteLock(&afs_xdnlc);
401
402	return 0;
403	}
404
405	/*!
406	* Remove anything pertaining to this file
407	*
408	* \param File vcache entry.
409	* \return 0
410	*/
411	int
412	osi_dnlc_purgevp(struct vcache *avc)
413	{
414	int i;
415	int writelocked;
416
417	#ifdef AFS_DARWIN_ENV
418	if (!(avc->f.states & (CVInit \| CVFlushed
419	#ifdef AFS_DARWIN80_ENV
420	\| CDeadVnode
421	#endif
422	)) && AFSTOV(avc))
423	cache_purge(AFSTOV(avc));
424	#endif
425
426	if (!afs_usednlc)
427	return 0;
428
429	dnlcstats.purgevs++;
430	TRACE(osi_dnlc_purgevpT, 0);
431	writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
432
433	for (i = 0; i < NCSIZE; i++) {
434	if (nameCache[i].vp == avc) {
435	nameCache[i].dirp = nameCache[i].vp = NULL;
436	/* can't simply break; because of hard links -- might be two */
437	/* different entries with same vnode */
438	if (writelocked && nameCache[i].prev) {
439	RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
440	nameCache[i].next = ncfreelist;
441	ncfreelist = &nameCache[i];
442	}
443	}
444	}
445	if (writelocked)
446	ReleaseWriteLock(&afs_xdnlc);
447
448	return 0;
449	}
450
451	/* remove everything */
452	int
453	osi_dnlc_purge(void)
454	{
455	int i;
456
457	dnlcstats.purges++;
458	TRACE(osi_dnlc_purgeT, 0);
459	if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) { /* couldn't get lock */
460	for (i = 0; i < NCSIZE; i++)
461	nameCache[i].dirp = nameCache[i].vp = NULL;
462	} else { /* did get the lock */
463	ncfreelist = NULL;
464	memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
465	memset(nameHash, 0, sizeof(struct nc ) NHSIZE);
466	for (i = 0; i < NCSIZE; i++) {
467	nameCache[i].next = ncfreelist;
468	ncfreelist = &nameCache[i];
469	}
470	ReleaseWriteLock(&afs_xdnlc);
471	}
472
473	return 0;
474	}
475
476	/* remove everything referencing a specific volume */
477	int
478	osi_dnlc_purgevol(struct VenusFid *fidp)
479	{
480
481	dnlcstats.purgevols++;
482	osi_dnlc_purge();
483
484	return 0;
485	}
486
487	int
488	osi_dnlc_init(void)
489	{
490	int i;
491
492	Lock_Init(&afs_xdnlc);
493	memset(&dnlcstats, 0, sizeof(dnlcstats));
494	memset(dnlctracetable, 0, sizeof(dnlctracetable));
495	dnlct = 0;
496	ObtainWriteLock(&afs_xdnlc, 223);
497	ncfreelist = NULL;
498	memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
499	memset(nameHash, 0, sizeof(struct nc ) NHSIZE);
500	for (i = 0; i < NCSIZE; i++) {
501	nameCache[i].next = ncfreelist;
502	ncfreelist = &nameCache[i];
503	}
504	ReleaseWriteLock(&afs_xdnlc);
505
506	return 0;
507	}
508
509	int
510	osi_dnlc_shutdown(void)
511	{
512	return 0;
513	}