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