src/afs/afs_osidnlc.c

   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         if (osi_vnhold(tvc) != 0) {
 279             dnlcstats.misses++;
 280             osi_dnlc_remove(adp, aname, tvc);
 281             tvc = NULL;
 282         }
 283 #endif
 284         ReleaseReadLock(&afs_xvcache);
 285
 286     }
 287
 288     return tvc;
 289 }
 290
 291
 292 static void
 293 RemoveEntry(struct nc *tnc, unsigned int key)
 294 {
 295     if (!tnc->prev)             /* things on freelist always have null prev ptrs */
 296         osi_Panic("bogus free list");
 297
 298     TRACE(RemoveEntryT, key);
 299     if (tnc == tnc->next) {     /* only one in list */
 300         nameHash[key] = NULL;
 301     } else {
 302         if (tnc == nameHash[key])
 303             nameHash[key] = tnc->next;
 304         tnc->prev->next = tnc->next;
 305         tnc->next->prev = tnc->prev;
 306     }
 307
 308     tnc->prev = NULL;           /* everything not in hash table has 0 prev */
 309     tnc->key = 0;               /* just for safety's sake */
 310 }
 311
 312
 313 int
 314 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
 315 {
 316     unsigned int key, skey;
 317     char *ts = aname;
 318     struct nc *tnc;
 319
 320     if (!afs_usednlc)
 321         return 0;
 322
 323     TRACE(osi_dnlc_removeT, skey);
 324     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
 325     if (ts - aname >= AFSNCNAMESIZE) {
 326         return 0;
 327     }
 328     skey = key & (NHSIZE - 1);
 329     TRACE(osi_dnlc_removeT, skey);
 330     dnlcstats.removes++;
 331     ObtainReadLock(&afs_xdnlc);
 332
 333     for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
 334         if ((tnc->dirp == adp) && (tnc->key == key)
 335             && (!strcmp((char *)tnc->name, aname))) {
 336             tnc->dirp = NULL;   /* now it won't match anything */
 337             break;
 338         } else if (tnc->next == nameHash[skey]) {       /* end of list */
 339             tnc = NULL;
 340             break;
 341         }
 342     }
 343     ReleaseReadLock(&afs_xdnlc);
 344
 345     if (!tnc)
 346         return 0;
 347
 348     /* there is a little race condition here, but it's relatively
 349      * harmless.  At worst, I wind up removing a mapping that I just
 350      * created. */
 351     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
 352         return 0;               /* no big deal, tnc will get recycled eventually */
 353     }
 354     RemoveEntry(tnc, skey);
 355     tnc->next = ncfreelist;
 356     ncfreelist = tnc;
 357     ReleaseWriteLock(&afs_xdnlc);
 358
 359     return 0;
 360 }
 361
 362 /*!
 363  * Remove anything pertaining to this directory.  I can invalidate
 364  * things without the lock, since I am just looking through the array,
 365  * but to move things off the lists or into the freelist, I need the
 366  * write lock
 367  *
 368  * \param adp vcache entry for the directory to be purged.
 369  * \return 0
 370  */
 371 int
 372 osi_dnlc_purgedp(struct vcache *adp)
 373 {
 374     int i;
 375     int writelocked;
 376
 377 #ifdef AFS_DARWIN_ENV
 378     if (!(adp->f.states & (CVInit | CVFlushed
 379 #ifdef AFS_DARWIN80_ENV
 380                         | CDeadVnode
 381 #endif
 382         )) && AFSTOV(adp))
 383     cache_purge(AFSTOV(adp));
 384 #endif
 385
 386     if (!afs_usednlc)
 387         return 0;
 388
 389     dnlcstats.purgeds++;
 390     TRACE(osi_dnlc_purgedpT, 0);
 391     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
 392
 393     for (i = 0; i < NCSIZE; i++) {
 394         if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
 395             nameCache[i].dirp = nameCache[i].vp = NULL;
 396             if (writelocked && nameCache[i].prev) {
 397                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
 398                 nameCache[i].next = ncfreelist;
 399                 ncfreelist = &nameCache[i];
 400             }
 401         }
 402     }
 403     if (writelocked)
 404         ReleaseWriteLock(&afs_xdnlc);
 405
 406     return 0;
 407 }
 408
 409 /*!
 410  * Remove anything pertaining to this file
 411  *
 412  * \param File vcache entry.
 413  * \return 0
 414  */
 415 int
 416 osi_dnlc_purgevp(struct vcache *avc)
 417 {
 418     int i;
 419     int writelocked;
 420
 421 #ifdef AFS_DARWIN_ENV
 422     if (!(avc->f.states & (CVInit | CVFlushed
 423 #ifdef AFS_DARWIN80_ENV
 424                         | CDeadVnode
 425 #endif
 426         )) && AFSTOV(avc))
 427     cache_purge(AFSTOV(avc));
 428 #endif
 429
 430     if (!afs_usednlc)
 431         return 0;
 432
 433     dnlcstats.purgevs++;
 434     TRACE(osi_dnlc_purgevpT, 0);
 435     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
 436
 437     for (i = 0; i < NCSIZE; i++) {
 438         if (nameCache[i].vp == avc) {
 439             nameCache[i].dirp = nameCache[i].vp = NULL;
 440             /* can't simply break; because of hard links -- might be two */
 441             /* different entries with same vnode */
 442             if (writelocked && nameCache[i].prev) {
 443                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
 444                 nameCache[i].next = ncfreelist;
 445                 ncfreelist = &nameCache[i];
 446             }
 447         }
 448     }
 449     if (writelocked)
 450         ReleaseWriteLock(&afs_xdnlc);
 451
 452     return 0;
 453 }
 454
 455 /* remove everything */
 456 int
 457 osi_dnlc_purge(void)
 458 {
 459     int i;
 460
 461     dnlcstats.purges++;
 462     TRACE(osi_dnlc_purgeT, 0);
 463     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) {      /* couldn't get lock */
 464         for (i = 0; i < NCSIZE; i++)
 465             nameCache[i].dirp = nameCache[i].vp = NULL;
 466     } else {                    /* did get the lock */
 467         ncfreelist = NULL;
 468         memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
 469         memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
 470         for (i = 0; i < NCSIZE; i++) {
 471             nameCache[i].next = ncfreelist;
 472             ncfreelist = &nameCache[i];
 473         }
 474         ReleaseWriteLock(&afs_xdnlc);
 475     }
 476
 477     return 0;
 478 }
 479
 480 /* remove everything referencing a specific volume */
 481 int
 482 osi_dnlc_purgevol(struct VenusFid *fidp)
 483 {
 484
 485     dnlcstats.purgevols++;
 486     osi_dnlc_purge();
 487
 488     return 0;
 489 }
 490
 491 int
 492 osi_dnlc_init(void)
 493 {
 494     int i;
 495
 496     Lock_Init(&afs_xdnlc);
 497     memset(&dnlcstats, 0, sizeof(dnlcstats));
 498     memset(dnlctracetable, 0, sizeof(dnlctracetable));
 499     dnlct = 0;
 500     ObtainWriteLock(&afs_xdnlc, 223);
 501     ncfreelist = NULL;
 502     memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
 503     memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
 504     for (i = 0; i < NCSIZE; i++) {
 505         nameCache[i].next = ncfreelist;
 506         ncfreelist = &nameCache[i];
 507     }
 508     ReleaseWriteLock(&afs_xdnlc);
 509
 510     return 0;
 511 }
 512
 513 int
 514 osi_dnlc_shutdown(void)
 515 {
 516     return 0;
 517 }