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