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         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 }