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 "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 = NULL;
  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(void)
  63 {
  64   static unsigned int nameptr = 0; /* next bucket to pull something from */
  65   struct nc *tnc;
  66   int j;
  67
  68   if (ncfreelist) {
  69     tnc = ncfreelist;
  70     ncfreelist = tnc->next;
  71     return tnc;
  72   }
  73
  74   for (j=0; j<NHSIZE+2; j++, nameptr++) {
  75     if (nameptr >= NHSIZE)
  76       nameptr =0;
  77     if (nameHash[nameptr])
  78       break;
  79   }
  80
  81   TRACE(ScavengeEntryT, nameptr);
  82   tnc = nameHash[nameptr];
  83   if (!tnc)   /* May want to consider changing this to return 0 */
  84     osi_Panic("null tnc in GetMeAnEntry");
  85
  86   if (tnc->prev == tnc) { /* only thing in list, don't screw around */
  87     nameHash[nameptr] = NULL;
  88     return (tnc);
  89   }
  90
  91   tnc = tnc->prev;      /* grab oldest one in this bucket */
  92   /* remove it from list */
  93   tnc->next->prev = tnc->prev;
  94   tnc->prev->next = tnc->next;
  95
  96   return (tnc);
  97 }
  98
  99 static void InsertEntry(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 (struct vcache *adp, char *aname, struct vcache *avc, 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     memcpy((char *)tnc->name, aname, 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 *osi_dnlc_lookup (struct vcache *adp, char *aname, int locktype )
 187 {
 188   struct vcache * tvc;
 189   int LRUme;
 190   unsigned int key, skey;
 191   char *ts = aname;
 192   struct nc * tnc, *tnc1=0;
 193   int safety;
 194
 195   if (!afs_usednlc)
 196     return 0;
 197
 198   dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 199   if (ts - aname >= AFSNCNAMESIZE) {
 200     return 0;
 201   }
 202   skey = key & (NHSIZE -1);
 203
 204   TRACE(osi_dnlc_lookupT, skey);
 205   dnlcstats.lookups++;
 206
 207   ObtainReadLock(&afs_xvcache);
 208   ObtainReadLock(&afs_xdnlc);
 209
 210   for ( tvc = NULL, tnc = nameHash[skey], safety=0;
 211        tnc; tnc = tnc->next, safety++ ) {
 212     if ( /* (tnc->key == key)  && */ (tnc->dirp == adp)
 213         && (!strcmp((char *)tnc->name, aname))) {
 214       tvc = tnc->vp;
 215       tnc1 = tnc;
 216       break;
 217     }
 218     else if (tnc->next == nameHash[skey]) { /* end of list */
 219       break;
 220     }
 221     else if (safety >NCSIZE) {
 222       afs_warn("DNLC cycle");
 223       dnlcstats.cycles++;
 224       ReleaseReadLock(&afs_xdnlc);
 225       ReleaseReadLock(&afs_xvcache);
 226       osi_dnlc_purge();
 227       return(0);
 228     }
 229   }
 230
 231   LRUme = 0; /* (tnc != nameHash[skey]); */
 232   ReleaseReadLock(&afs_xdnlc);
 233
 234   if (!tvc) {
 235      ReleaseReadLock(&afs_xvcache);
 236      dnlcstats.misses++;
 237   }
 238   else {
 239 #ifdef  AFS_OSF_ENV
 240      VN_HOLD((vnode_t *)tvc);
 241 #else
 242       osi_vnhold(tvc, 0);
 243 #endif
 244       ReleaseReadLock(&afs_xvcache);
 245
 246 #ifdef  notdef
 247     /*
 248      * XX If LRUme ever is non-zero change the if statement around because
 249      * aix's cc with optimizer on won't necessarily check things in order XX
 250      */
 251     if (LRUme && (0 == NBObtainWriteLock(&afs_xdnlc))) {
 252       /* don't block to do this */
 253       /* tnc might have been moved during race condition, */
 254       /* but it's always in a legit hash chain when a lock is granted,
 255        * or else it's on the freelist so prev == NULL,
 256        * so at worst this is redundant */
 257       /* Now that we've got it held, and a lock on the dnlc, we
 258        * should check to be sure that there was no race, and
 259        * bail out if there was. */
 260       if (tnc->prev) {
 261         /* special case for only two elements on list - relative ordering
 262          * doesn't change */
 263         if (tnc->prev != tnc->next) {
 264           /* remove from old location */
 265           tnc->prev->next = tnc->next;
 266           tnc->next->prev = tnc->prev;
 267           /* insert into new location */
 268           tnc->next = nameHash[skey];
 269           tnc->prev = tnc->next->prev;
 270           tnc->next->prev = tnc;
 271           tnc->prev->next = tnc;
 272         }
 273         nameHash[skey] = tnc;
 274       }
 275       ReleaseWriteLock(&afs_xdnlc);
 276   }
 277 #endif
 278   }
 279
 280 return tvc;
 281 }
 282
 283
 284 static void RemoveEntry (struct nc *tnc, unsigned int key)
 285 {
 286   if (!tnc->prev) /* things on freelist always have null prev ptrs */
 287     osi_Panic("bogus free list");
 288
 289   TRACE(RemoveEntryT, key);
 290   if (tnc == tnc->next) { /* only one in list */
 291     nameHash[key] = NULL;
 292   }
 293   else {
 294     if (tnc == nameHash[key])
 295       nameHash[key]  = tnc->next;
 296     tnc->prev->next = tnc->next;
 297     tnc->next->prev = tnc->prev;
 298   }
 299
 300   tnc->prev = NULL; /* everything not in hash table has 0 prev */
 301   tnc->key = 0; /* just for safety's sake */
 302 }
 303
 304
 305 int osi_dnlc_remove (struct vcache *adp, char *aname, struct vcache *avc )
 306 {
 307   unsigned int key, skey;
 308   char *ts = aname;
 309   struct nc *tnc;
 310
 311   if (!afs_usednlc)
 312     return 0;
 313
 314   TRACE( osi_dnlc_removeT, skey);
 315   dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 316   if (ts - aname >= AFSNCNAMESIZE) {
 317     return 0;
 318   }
 319   skey = key & (NHSIZE -1);
 320   TRACE( osi_dnlc_removeT, skey);
 321   dnlcstats.removes++;
 322   ObtainReadLock(&afs_xdnlc);
 323
 324   for (tnc = nameHash[skey]; tnc; tnc = tnc->next) {
 325     if ((tnc->dirp == adp) && (tnc->key == key)
 326         && (!strcmp((char *)tnc->name, aname))) {
 327       tnc->dirp = NULL; /* now it won't match anything */
 328       break;
 329     }
 330     else if (tnc->next == nameHash[skey]) { /* end of list */
 331       tnc = NULL;
 332       break;
 333     }
 334   }
 335   ReleaseReadLock(&afs_xdnlc);
 336
 337   if (!tnc)
 338     return 0;
 339
 340   /* there is a little race condition here, but it's relatively
 341    * harmless.  At worst, I wind up removing a mapping that I just
 342    * created. */
 343   if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,1)) {
 344     return 0; /* no big deal, tnc will get recycled eventually */
 345   }
 346   RemoveEntry(tnc, skey);
 347   tnc->next = ncfreelist;
 348   ncfreelist = tnc;
 349   ReleaseWriteLock(&afs_xdnlc);
 350
 351 return 0;
 352 }
 353
 354 /* remove anything pertaining to this directory.  I can invalidate
 355  * things without the lock, since I am just looking through the array,
 356  * but to move things off the lists or into the freelist, I need the
 357  * write lock */
 358 int osi_dnlc_purgedp (struct vcache *adp)
 359 {
 360   int i;
 361   int writelocked;
 362
 363   if (!afs_usednlc)
 364     return 0;
 365
 366   dnlcstats.purgeds++;
 367   TRACE( osi_dnlc_purgedpT, 0);
 368   writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,2));
 369
 370   for (i=0; i<NCSIZE; i++) {
 371     if ((nameCache[i].dirp == adp) || (nameCache[i].vp == adp)) {
 372       nameCache[i].dirp = nameCache[i].vp = NULL;
 373       if (writelocked && nameCache[i].prev) {
 374         RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 375         nameCache[i].next = ncfreelist;
 376         ncfreelist = &nameCache[i];
 377       }
 378     }
 379   }
 380   if (writelocked)
 381     ReleaseWriteLock(&afs_xdnlc);
 382
 383 return 0;
 384 }
 385
 386 /* remove anything pertaining to this file */
 387 int osi_dnlc_purgevp (struct vcache *avc)
 388 {
 389   int i;
 390   int writelocked;
 391
 392   if (!afs_usednlc)
 393     return 0;
 394
 395   dnlcstats.purgevs++;
 396   TRACE( osi_dnlc_purgevpT, 0);
 397   writelocked = (0 == NBObtainWriteLock(&afs_xdnlc,3));
 398
 399   for (i=0; i<NCSIZE; i++) {
 400     if ((nameCache[i].vp == avc)) {
 401       nameCache[i].dirp = nameCache[i].vp = NULL;
 402       /* can't simply break; because of hard links -- might be two */
 403       /* different entries with same vnode */
 404       if (writelocked && nameCache[i].prev) {
 405         RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 406         nameCache[i].next = ncfreelist;
 407         ncfreelist = &nameCache[i];
 408       }
 409     }
 410   }
 411   if (writelocked)
 412     ReleaseWriteLock(&afs_xdnlc);
 413
 414 return 0;
 415 }
 416
 417 /* remove everything */
 418 int osi_dnlc_purge(void)
 419 {
 420   int i;
 421
 422   dnlcstats.purges++;
 423   TRACE( osi_dnlc_purgeT, 0);
 424   if (EWOULDBLOCK == NBObtainWriteLock(&afs_xdnlc,4)) { /* couldn't get lock */
 425     for (i=0; i<NCSIZE; i++)
 426       nameCache[i].dirp = nameCache[i].vp = NULL;
 427   }
 428   else {  /* did get the lock */
 429     ncfreelist = NULL;
 430     memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
 431     memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
 432     for (i=0; i<NCSIZE; i++) {
 433       nameCache[i].next = ncfreelist;
 434       ncfreelist = &nameCache[i];
 435     }
 436     ReleaseWriteLock(&afs_xdnlc);
 437   }
 438
 439 return 0;
 440 }
 441
 442 /* remove everything referencing a specific volume */
 443 int osi_dnlc_purgevol(struct VenusFid *fidp)
 444 {
 445
 446   dnlcstats.purgevols++;
 447   osi_dnlc_purge();
 448
 449 return 0;
 450 }
 451
 452 int osi_dnlc_init(void)
 453 {
 454 int i;
 455
 456   Lock_Init(&afs_xdnlc);
 457   memset((char *)&dnlcstats, 0, sizeof(dnlcstats));
 458   memset((char *)dnlctracetable, 0, sizeof(dnlctracetable));
 459   dnlct=0;
 460   ObtainWriteLock(&afs_xdnlc,223);
 461   ncfreelist = NULL;
 462   memset((char *)nameCache, 0, sizeof(struct nc) * NCSIZE);
 463   memset((char *)nameHash, 0, sizeof(struct nc *) * NHSIZE);
 464   for (i=0; i<NCSIZE; i++) {
 465     nameCache[i].next = ncfreelist;
 466     ncfreelist = &nameCache[i];
 467   }
 468   ReleaseWriteLock(&afs_xdnlc);
 469
 470 return 0;
 471 }
 472
 473 int osi_dnlc_shutdown(void)
 474 {
 475   return 0;
 476 }
 477
 478
 479
 480