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