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     if (nameptr >= NHSIZE)
  85         nameptr = 0;
  86
  87     TRACE(ScavengeEntryT, nameptr);
  88     tnc = nameHash[nameptr];
  89     if (!tnc)                   /* May want to consider changing this to return 0 */
  90         osi_Panic("null tnc in GetMeAnEntry");
  91
  92     if (tnc->prev == tnc) {     /* only thing in list, don't screw around */
  93         nameHash[nameptr] = NULL;
  94         return (tnc);
  95     }
  96
  97     tnc = tnc->prev;            /* grab oldest one in this bucket */
  98     /* remove it from list */
  99     tnc->next->prev = tnc->prev;
 100     tnc->prev->next = tnc->next;
 101
 102     return (tnc);
 103 }
 104
 105 static void
 106 InsertEntry(struct nc *tnc)
 107 {
 108     unsigned int key;
 109     key = tnc->key & (NHSIZE - 1);
 110
 111     TRACE(InsertEntryT, key);
 112     if (!nameHash[key]) {
 113         nameHash[key] = tnc;
 114         tnc->next = tnc->prev = tnc;
 115     } else {
 116         tnc->next = nameHash[key];
 117         tnc->prev = tnc->next->prev;
 118         tnc->next->prev = tnc;
 119         tnc->prev->next = tnc;
 120         nameHash[key] = tnc;
 121     }
 122 }
 123
 124
 125 int
 126 osi_dnlc_enter(struct vcache *adp, char *aname, struct vcache *avc,
 127                afs_hyper_t * avno)
 128 {
 129     struct nc *tnc;
 130     unsigned int key, skey;
 131     char *ts = aname;
 132     int safety;
 133
 134     if (!afs_usednlc)
 135         return 0;
 136
 137     TRACE(osi_dnlc_enterT, 0);
 138     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
 139     if (ts - aname >= AFSNCNAMESIZE) {
 140         return 0;
 141     }
 142     skey = key & (NHSIZE - 1);
 143     dnlcstats.enters++;
 144
 145   retry:
 146     ObtainWriteLock(&afs_xdnlc, 222);
 147
 148     /* Only cache entries from the latest version of the directory */
 149     if (!(adp->f.states & CStatd) || !hsame(*avno, adp->f.m.DataVersion)) {
 150         ReleaseWriteLock(&afs_xdnlc);
 151         return 0;
 152     }
 153
 154     /*
 155      * Make sure each directory entry gets cached no more than once.
 156      */
 157     for (tnc = nameHash[skey], safety = 0; tnc; tnc = tnc->next, safety++) {
 158         if ((tnc->dirp == adp) && (!strcmp((char *)tnc->name, aname))) {
 159             /* duplicate entry */
 160             break;
 161         } else if (tnc->next == nameHash[skey]) {       /* end of list */
 162             tnc = NULL;
 163             break;
 164         } else if (safety > NCSIZE) {
 165             afs_warn("DNLC cycle");
 166             dnlcstats.cycles++;
 167             ReleaseWriteLock(&afs_xdnlc);
 168             osi_dnlc_purge();
 169             goto retry;
 170         }
 171     }
 172
 173     if (tnc == NULL) {
 174         tnc = GetMeAnEntry();
 175
 176         tnc->dirp = adp;
 177         tnc->vp = avc;
 178         tnc->key = key;
 179         memcpy((char *)tnc->name, aname, ts - aname + 1);       /* include the NULL */
 180
 181         InsertEntry(tnc);
 182     } else {
 183         /* duplicate */
 184         tnc->vp = avc;
 185     }
 186     ReleaseWriteLock(&afs_xdnlc);
 187
 188     return 0;
 189 }
 190
 191
 192 struct vcache *
 193 osi_dnlc_lookup(struct vcache *adp, char *aname, int locktype)
 194 {
 195     struct vcache *tvc;
 196     unsigned int key, skey;
 197     char *ts = aname;
 198     struct nc *tnc;
 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     skey = key & (NHSIZE - 1);
 211
 212     TRACE(osi_dnlc_lookupT, skey);
 213     dnlcstats.lookups++;
 214
 215     ObtainReadLock(&afs_xvcache);
 216     ObtainReadLock(&afs_xdnlc);
 217
 218     for (tvc = NULL, tnc = nameHash[skey], safety = 0; tnc;
 219          tnc = tnc->next, safety++) {
 220         if ( /* (tnc->key == key)  && */ (tnc->dirp == adp)
 221             && (!strcmp((char *)tnc->name, aname))) {
 222             tvc = tnc->vp;
 223             break;
 224         } else if (tnc->next == nameHash[skey]) {       /* end of list */
 225             break;
 226         } else if (safety > NCSIZE) {
 227             afs_warn("DNLC cycle");
 228             dnlcstats.cycles++;
 229             ReleaseReadLock(&afs_xdnlc);
 230             ReleaseReadLock(&afs_xvcache);
 231             osi_dnlc_purge();
 232             return (0);
 233         }
 234     }
 235
 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     }
 276
 277     return tvc;
 278 }
 279
 280
 281 static void
 282 RemoveEntry(struct nc *tnc, unsigned int key)
 283 {
 284     if (!tnc->prev)             /* things on freelist always have null prev ptrs */
 285         osi_Panic("bogus free list");
 286
 287     TRACE(RemoveEntryT, key);
 288     if (tnc == tnc->next) {     /* only one in list */
 289         nameHash[key] = NULL;
 290     } else {
 291         if (tnc == nameHash[key])
 292             nameHash[key] = tnc->next;
 293         tnc->prev->next = tnc->next;
 294         tnc->next->prev = tnc->prev;
 295     }
 296
 297     tnc->prev = NULL;           /* everything not in hash table has 0 prev */
 298     tnc->key = 0;               /* just for safety's sake */
 299 }
 300
 301
 302 int
 303 osi_dnlc_remove(struct vcache *adp, char *aname, struct vcache *avc)
 304 {
 305     unsigned int key, skey;
 306     char *ts = aname;
 307     struct nc *tnc;
 308
 309     if (!afs_usednlc)
 310         return 0;
 311
 312     TRACE(osi_dnlc_removeT, skey);
 313     dnlcHash(ts, key);          /* leaves ts pointing at the NULL */
 314     if (ts - aname >= AFSNCNAMESIZE) {
 315         return 0;
 316     }
 317     skey = key & (NHSIZE - 1);
 318     TRACE(osi_dnlc_removeT, skey);
 319     dnlcstats.removes++;
 320     ObtainReadLock(&afs_xdnlc);
 321
 322     for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
 323         if ((tnc->dirp == adp) && (tnc->key == key)
 324             && (!strcmp((char *)tnc->name, aname))) {
 325             tnc->dirp = NULL;   /* now it won't match anything */
 326             break;
 327         } else if (tnc->next == nameHash[skey]) {       /* end of list */
 328             tnc = NULL;
 329             break;
 330         }
 331     }
 332     ReleaseReadLock(&afs_xdnlc);
 333
 334     if (!tnc)
 335         return 0;
 336
 337     /* there is a little race condition here, but it's relatively
 338      * harmless.  At worst, I wind up removing a mapping that I just
 339      * created. */
 340     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 1)) {
 341         return 0;               /* no big deal, tnc will get recycled eventually */
 342     }
 343     RemoveEntry(tnc, skey);
 344     tnc->next = ncfreelist;
 345     ncfreelist = tnc;
 346     ReleaseWriteLock(&afs_xdnlc);
 347
 348     return 0;
 349 }
 350
 351 /*!
 352  * Remove anything pertaining to this directory.  I can invalidate
 353  * things without the lock, since I am just looking through the array,
 354  * but to move things off the lists or into the freelist, I need the
 355  * write lock
 356  *
 357  * \param adp vcache entry for the directory to be purged.
 358  * \return 0
 359  */
 360 int
 361 osi_dnlc_purgedp(struct vcache *adp)
 362 {
 363     int i;
 364     int writelocked;
 365
 366 #ifdef AFS_DARWIN_ENV
 367     if (!(adp->f.states & (CVInit | CVFlushed
 368 #ifdef AFS_DARWIN80_ENV
 369                         | CDeadVnode
 370 #endif
 371         )) && AFSTOV(adp))
 372     cache_purge(AFSTOV(adp));
 373 #endif
 374
 375     if (!afs_usednlc)
 376         return 0;
 377
 378     dnlcstats.purgeds++;
 379     TRACE(osi_dnlc_purgedpT, 0);
 380     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 2));
 381
 382     for (i = 0; i < NCSIZE; i++) {
 383         if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
 384             nameCache[i].dirp = nameCache[i].vp = NULL;
 385             if (writelocked && nameCache[i].prev) {
 386                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
 387                 nameCache[i].next = ncfreelist;
 388                 ncfreelist = &nameCache[i];
 389             }
 390         }
 391     }
 392     if (writelocked)
 393         ReleaseWriteLock(&afs_xdnlc);
 394
 395     return 0;
 396 }
 397
 398 /*!
 399  * Remove anything pertaining to this file
 400  *
 401  * \param File vcache entry.
 402  * \return 0
 403  */
 404 int
 405 osi_dnlc_purgevp(struct vcache *avc)
 406 {
 407     int i;
 408     int writelocked;
 409
 410 #ifdef AFS_DARWIN_ENV
 411     if (!(avc->f.states & (CVInit | CVFlushed
 412 #ifdef AFS_DARWIN80_ENV
 413                         | CDeadVnode
 414 #endif
 415         )) && AFSTOV(avc))
 416     cache_purge(AFSTOV(avc));
 417 #endif
 418
 419     if (!afs_usednlc)
 420         return 0;
 421
 422     dnlcstats.purgevs++;
 423     TRACE(osi_dnlc_purgevpT, 0);
 424     writelocked = (0 == NBObtainWriteLock(&afs_xdnlc, 3));
 425
 426     for (i = 0; i < NCSIZE; i++) {
 427         if (nameCache[i].vp == avc) {
 428             nameCache[i].dirp = nameCache[i].vp = NULL;
 429             /* can't simply break; because of hard links -- might be two */
 430             /* different entries with same vnode */
 431             if (writelocked && nameCache[i].prev) {
 432                 RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE - 1));
 433                 nameCache[i].next = ncfreelist;
 434                 ncfreelist = &nameCache[i];
 435             }
 436         }
 437     }
 438     if (writelocked)
 439         ReleaseWriteLock(&afs_xdnlc);
 440
 441     return 0;
 442 }
 443
 444 /* remove everything */
 445 int
 446 osi_dnlc_purge(void)
 447 {
 448     int i;
 449
 450     dnlcstats.purges++;
 451     TRACE(osi_dnlc_purgeT, 0);
 452     if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc, 4)) {      /* couldn't get lock */
 453         for (i = 0; i < NCSIZE; i++)
 454             nameCache[i].dirp = nameCache[i].vp = NULL;
 455     } else {                    /* did get the lock */
 456         ncfreelist = NULL;
 457         memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
 458         memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
 459         for (i = 0; i < NCSIZE; i++) {
 460             nameCache[i].next = ncfreelist;
 461             ncfreelist = &nameCache[i];
 462         }
 463         ReleaseWriteLock(&afs_xdnlc);
 464     }
 465
 466     return 0;
 467 }
 468
 469 /* remove everything referencing a specific volume */
 470 int
 471 osi_dnlc_purgevol(struct VenusFid *fidp)
 472 {
 473
 474     dnlcstats.purgevols++;
 475     osi_dnlc_purge();
 476
 477     return 0;
 478 }
 479
 480 int
 481 osi_dnlc_init(void)
 482 {
 483     int i;
 484
 485     Lock_Init(&afs_xdnlc);
 486     memset(&dnlcstats, 0, sizeof(dnlcstats));
 487     memset(dnlctracetable, 0, sizeof(dnlctracetable));
 488     dnlct = 0;
 489     ObtainWriteLock(&afs_xdnlc, 223);
 490     ncfreelist = NULL;
 491     memset(nameCache, 0, sizeof(struct nc) * NCSIZE);
 492     memset(nameHash, 0, sizeof(struct nc *) * NHSIZE);
 493     for (i = 0; i < NCSIZE; i++) {
 494         nameCache[i].next = ncfreelist;
 495         ncfreelist = &nameCache[i];
 496     }
 497     ReleaseWriteLock(&afs_xdnlc);
 498
 499     return 0;
 500 }
 501
 502 int
 503 osi_dnlc_shutdown(void)
 504 {
 505     return 0;
 506 }