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