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