src/WINNT/afsd/cm_dnlc.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 /*
  11 **      This implements the directory to name cache lookup.
  12 **      Given a directory scache and a name, the dnlc returns the
  13 **      vcache corresponding to the name. The vcache entries that
  14 **      exist in the dnlc are not refcounted.
  15 **
  16 */
  17
  18 #include <afs/param.h>
  19 #include <afs/stds.h>
  20
  21 #ifndef DJGPP
  22 #include <windows.h>
  23 #include <winsock2.h>
  24 #endif /* !DJGPP */
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <osi.h>
  28 #include "afsd.h"
  29
  30 osi_rwlock_t cm_dnlcLock;
  31
  32 cm_dnlcstats_t dnlcstats;       /* dnlc statistics */
  33 int cm_useDnlc = 1;             /* yes, start using the dnlc */
  34 int cm_debugDnlc = 0;           /* debug dnlc */
  35
  36
  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 struct nc       *ncfreelist = (struct nc *)0;
  42 static struct nc nameCache[NCSIZE];
  43 struct nc*      nameHash[NHSIZE];
  44
  45
  46 #ifndef DJGPP
  47 #define dnlcNotify(x,debug){                    \
  48                         HANDLE  hh;             \
  49                         char *ptbuf[1];         \
  50                         ptbuf[0] = x;           \
  51                         if ( debug ) {          \
  52                             hh = RegisterEventSource(NULL, AFS_DAEMON_EVENT_NAME);   \
  53                             ReportEvent(hh,EVENTLOG_ERROR_TYPE,0,__LINE__,  \
  54                                 NULL, 1, 0, ptbuf, NULL);                   \
  55                             DeregisterEventSource(hh);                  \
  56                         }                                               \
  57                      }
  58 #else
  59 #define dnlcNotify(x,debug)
  60 #endif /* !DJGPP */
  61
  62
  63 static struct nc *
  64 GetMeAnEntry()
  65 {
  66     static unsigned int nameptr = 0; /* next bucket to pull something from */
  67     struct nc *tnc;
  68     int j;
  69
  70     if (ncfreelist)
  71     {
  72         tnc = ncfreelist;
  73         ncfreelist = tnc->next;
  74         return tnc;
  75     }
  76
  77     for (j=0; j<NHSIZE+2; j++, nameptr++)
  78     {
  79         if (nameptr >= NHSIZE)
  80             nameptr =0;
  81         if (nameHash[nameptr])
  82             break;
  83     }
  84
  85     tnc = nameHash[nameptr];
  86     if (!tnc)
  87     {
  88         dnlcNotify("null tnc in GetMeAnEntry",1);
  89         osi_Log0(afsd_logp,"null tnc in GetMeAnEntry");
  90         return 0;
  91     }
  92
  93     if (tnc->prev == tnc)
  94     {                   /* only thing in list, don't screw around */
  95         nameHash[nameptr] = (struct nc *) 0;
  96         return (tnc);
  97     }
  98
  99     tnc = tnc->prev;            /* grab oldest one in this bucket */
 100     tnc->next->prev = tnc->prev;/* remove it from list */
 101     tnc->prev->next = tnc->next;
 102
 103     return (tnc);
 104 }
 105
 106 static void
 107 InsertEntry(tnc)
 108     struct nc *tnc;
 109 {
 110     unsigned int key;
 111     key = tnc->key & (NHSIZE -1);
 112
 113     if(!nameHash[key])
 114     {
 115         nameHash[key] = tnc;
 116         tnc->next = tnc->prev = tnc;
 117     }
 118     else
 119     {
 120         tnc->next = nameHash[key];
 121         tnc->prev = tnc->next->prev;
 122         tnc->next->prev = tnc;
 123         tnc->prev->next = tnc;
 124         nameHash[key] = tnc;
 125     }
 126 }
 127
 128
 129 void
 130 cm_dnlcEnter ( adp, aname, avc )
 131     cm_scache_t *adp;
 132     char        *aname;
 133     cm_scache_t *avc;
 134 {
 135     struct nc *tnc;
 136     unsigned int key, skey, new=0;
 137     char *ts = aname;
 138     int safety;
 139
 140     if (!cm_useDnlc)
 141         return ;
 142
 143     if ( cm_debugDnlc )
 144         osi_Log3(afsd_logp,"cm_dnlcEnter dir %x name %s scache %x",
 145             adp, osi_LogSaveString(afsd_logp,aname), avc);
 146
 147     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 148     if (ts - aname >= CM_AFSNCNAMESIZE)
 149         return ;
 150     skey = key & (NHSIZE -1);
 151
 152     lock_ObtainWrite(&cm_dnlcLock);
 153     dnlcstats.enters++;
 154
 155     for (tnc = nameHash[skey], safety=0; tnc; tnc = tnc->next, safety++ )
 156         if ((tnc->dirp == adp) && (!cm_stricmp(tnc->name, aname)))
 157             break;                              /* preexisting entry */
 158         else if ( tnc->next == nameHash[skey])  /* end of list */
 159         {
 160             tnc = NULL;
 161             break;
 162         }
 163         else if ( safety >NCSIZE)
 164         {
 165             dnlcstats.cycles++;
 166             lock_ReleaseWrite(&cm_dnlcLock);
 167
 168             dnlcNotify("DNLC cycle",1);
 169             if ( cm_debugDnlc )
 170                 osi_Log0(afsd_logp, "DNLC cycle");
 171             cm_dnlcPurge();
 172             return;
 173         }
 174
 175     if ( !tnc )
 176     {
 177         new = 1;        /* entry does not exist, we are creating a new entry*/
 178         tnc = GetMeAnEntry();
 179     }
 180     if ( tnc )
 181     {
 182         tnc->dirp = adp;
 183         tnc->vp = avc;
 184         tnc->key = key;
 185         memcpy (tnc->name, aname, ts-aname+1); /* include the NULL */
 186
 187         if ( new )      /* insert entry only if it is newly created */
 188                 InsertEntry(tnc);
 189
 190     }
 191     lock_ReleaseWrite(&cm_dnlcLock);
 192
 193     if ( !tnc)
 194         cm_dnlcPurge();
 195 }
 196
 197 /*
 198 * if the scache entry is found, return it held
 199 */
 200 cm_scache_t *
 201 cm_dnlcLookup ( adp, sp)
 202   cm_scache_t *adp;
 203   cm_lookupSearch_t*      sp;
 204 {
 205     cm_scache_t * tvc;
 206     unsigned int key, skey;
 207     char* aname = sp->searchNamep;
 208     char *ts = aname;
 209     struct nc * tnc;
 210     int safety, match;
 211
 212     if (!cm_useDnlc)
 213         return 0;
 214     if ( cm_debugDnlc )
 215         osi_Log2(afsd_logp, "cm_dnlcLookup dir %x name %s",
 216                 adp, osi_LogSaveString(afsd_logp,aname));
 217
 218     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 219     if (ts - aname >= CM_AFSNCNAMESIZE)
 220         return 0;
 221
 222     skey = key & (NHSIZE -1);
 223
 224     lock_ObtainRead(&cm_dnlcLock);
 225     dnlcstats.lookups++;             /* Is a dnlcread lock sufficient? */
 226
 227     for ( tvc = (cm_scache_t *) 0, tnc = nameHash[skey], safety=0;
 228        tnc; tnc = tnc->next, safety++ )
 229     {
 230         if (tnc->dirp == adp)
 231         {
 232             if ( sp->caseFold )         /* case insensitive */
 233             {
 234                 match = cm_stricmp(tnc->name, aname);
 235                 if ( !match )   /* something matches */
 236                 {
 237                         /* determine what type of match it is */
 238                         if ( !strcmp(tnc->name, aname))
 239                         {
 240                                 /* exact match, do nothing */
 241                         }
 242                         else if ( cm_NoneUpper(tnc->name))
 243                                 sp->LCfound = 1;
 244                         else if ( cm_NoneLower(tnc->name))
 245                                 sp->UCfound = 1;
 246                         else    sp->NCfound = 1;
 247                         tvc = tnc->vp;
 248                         break;
 249                 }
 250             }
 251             else                        /* case sensitive */
 252             {
 253                 match = strcmp(tnc->name, aname);
 254                 if ( !match ) /* found a match */
 255                 {
 256                         tvc = tnc->vp;
 257                         break;
 258                 }
 259             }
 260         }
 261         if (tnc->next == nameHash[skey])
 262         {                       /* end of list */
 263             break;
 264         }
 265         else if (safety >NCSIZE)
 266         {
 267             dnlcstats.cycles++;
 268             lock_ReleaseRead(&cm_dnlcLock);
 269
 270             dnlcNotify("DNLC cycle",1);
 271             if ( cm_debugDnlc )
 272                 osi_Log0(afsd_logp, "DNLC cycle");
 273             cm_dnlcPurge();
 274             return(0);
 275         }
 276     }
 277
 278     if (!tvc)
 279         dnlcstats.misses++;     /* Is a dnlcread lock sufficient? */
 280     else
 281     {
 282         sp->found = 1;
 283         sp->fid.vnode  = tvc->fid.vnode;
 284         sp->fid.unique = tvc->fid.unique;
 285     }
 286     lock_ReleaseRead(&cm_dnlcLock);
 287
 288     if (tvc) {
 289         lock_ObtainWrite(&cm_scacheLock);
 290         tvc->refCount++;        /* scache entry held */
 291         lock_ReleaseWrite(&cm_scacheLock);
 292     }
 293
 294     if ( cm_debugDnlc && tvc )
 295         osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
 296
 297     return tvc;
 298 }
 299
 300
 301 static int
 302 RemoveEntry (tnc, key)
 303     struct nc    *tnc;
 304     unsigned int key;
 305 {
 306     if (!tnc->prev) /* things on freelist always have null prev ptrs */
 307     {
 308         dnlcNotify("Bogus dnlc freelist", 1);
 309         osi_Log0(afsd_logp,"Bogus dnlc freelist");
 310         return 1;   /* error */
 311     }
 312
 313     if (tnc == tnc->next)  /* only one in list */
 314         nameHash[key] = (struct nc *) 0;
 315     else
 316     {
 317         if (tnc == nameHash[key])
 318             nameHash[key]  = tnc->next;
 319         tnc->prev->next = tnc->next;
 320         tnc->next->prev = tnc->prev;
 321     }
 322
 323     tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
 324     tnc->key = 0; /* just for safety's sake */
 325     return 0;     /* success */
 326 }
 327
 328
 329 void
 330 cm_dnlcRemove ( adp, aname)
 331     cm_scache_t *adp;
 332     char          *aname;
 333 {
 334     unsigned int key, skey, error=0;
 335     int found= 0, safety;
 336     char *ts = aname;
 337     struct nc *tnc, *tmp;
 338
 339     if (!cm_useDnlc)
 340         return ;
 341
 342     if ( cm_debugDnlc )
 343         osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
 344                 adp, osi_LogSaveString(afsd_logp,aname));
 345
 346     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 347     if (ts - aname >= CM_AFSNCNAMESIZE)
 348         return ;
 349
 350     skey = key & (NHSIZE -1);
 351     lock_ObtainWrite(&cm_dnlcLock);
 352     dnlcstats.removes++;
 353
 354     for (tnc = nameHash[skey], safety=0; tnc; safety++)
 355     {
 356         if ( (tnc->dirp == adp) && (tnc->key == key)
 357                         && !cm_stricmp(tnc->name,aname) )
 358         {
 359             tnc->dirp = (cm_scache_t *) 0; /* now it won't match anything */
 360             tmp = tnc->next;
 361             error = RemoveEntry(tnc, skey);
 362             if ( error )
 363                 break;
 364
 365             tnc->next = ncfreelist; /* insert entry into freelist */
 366             ncfreelist = tnc;
 367             found = 1;          /* found atleast one entry */
 368
 369             tnc = tmp;          /* continue down the linked list */
 370         }
 371         else if (tnc->next == nameHash[skey]) /* end of list */
 372             break;
 373         else
 374             tnc = tnc->next;
 375         if ( safety > NCSIZE )
 376         {
 377             dnlcstats.cycles++;
 378             lock_ReleaseWrite(&cm_dnlcLock);
 379
 380             dnlcNotify("DNLC cycle",1);
 381             if ( cm_debugDnlc )
 382                 osi_Log0(afsd_logp, "DNLC cycle");
 383             cm_dnlcPurge();
 384             return;
 385         }
 386     }
 387     lock_ReleaseWrite(&cm_dnlcLock);
 388
 389     if (!found && !error && cm_debugDnlc)
 390         osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
 391
 392     if ( error )
 393         cm_dnlcPurge();
 394 }
 395
 396 /* remove anything pertaining to this directory */
 397 void
 398 cm_dnlcPurgedp (adp)
 399   cm_scache_t *adp;
 400 {
 401     int i;
 402     int err=0;
 403
 404     if (!cm_useDnlc)
 405         return ;
 406
 407     if ( cm_debugDnlc )
 408         osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
 409
 410     lock_ObtainWrite(&cm_dnlcLock);
 411     dnlcstats.purgeds++;
 412
 413     for (i=0; i<NCSIZE && !err; i++)
 414     {
 415         if (nameCache[i].dirp == adp )
 416         {
 417             nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
 418             if (nameCache[i].prev && !err)
 419             {
 420                 err = RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 421                 nameCache[i].next = ncfreelist;
 422                 ncfreelist = &nameCache[i];
 423             }
 424         }
 425     }
 426     lock_ReleaseWrite(&cm_dnlcLock);
 427     if ( err )
 428         cm_dnlcPurge();
 429 }
 430
 431 /* remove anything pertaining to this file */
 432 void
 433 cm_dnlcPurgevp ( avc )
 434   cm_scache_t *avc;
 435 {
 436     int i;
 437     int err=0;
 438
 439     if (!cm_useDnlc)
 440         return ;
 441
 442     if ( cm_debugDnlc )
 443         osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
 444
 445     lock_ObtainWrite(&cm_dnlcLock);
 446     dnlcstats.purgevs++;
 447
 448     for (i=0; i<NCSIZE && !err ; i++)
 449     {
 450         if (nameCache[i].vp == avc)
 451         {
 452             nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
 453             /* can't simply break; because of hard links -- might be two */
 454             /* different entries with same vnode */
 455             if (!err && nameCache[i].prev)
 456             {
 457                 err=RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 458                 nameCache[i].next = ncfreelist;
 459                 ncfreelist = &nameCache[i];
 460             }
 461         }
 462     }
 463     lock_ReleaseWrite(&cm_dnlcLock);
 464     if ( err )
 465         cm_dnlcPurge();
 466 }
 467
 468 /* remove everything */
 469 void cm_dnlcPurge(void)
 470 {
 471     int i;
 472
 473     if (!cm_useDnlc)
 474         return ;
 475
 476     if ( cm_debugDnlc )
 477         osi_Log0(afsd_logp, "cm_dnlcPurge");
 478
 479     lock_ObtainWrite(&cm_dnlcLock);
 480     dnlcstats.purges++;
 481
 482     ncfreelist = (struct nc *) 0;
 483     memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
 484     memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
 485     for (i=0; i<NCSIZE; i++)
 486     {
 487         nameCache[i].next = ncfreelist;
 488         ncfreelist = &nameCache[i];
 489     }
 490     lock_ReleaseWrite(&cm_dnlcLock);
 491
 492 }
 493
 494 /* remove everything referencing a specific volume */
 495 void
 496 cm_dnlcPurgeVol( fidp )
 497   AFSFid *fidp;
 498 {
 499
 500     if (!cm_useDnlc)
 501         return ;
 502
 503     dnlcstats.purgevols++;
 504     cm_dnlcPurge();
 505 }
 506
 507 void
 508 cm_dnlcInit(void)
 509 {
 510     int i;
 511
 512     if (!cm_useDnlc)
 513         return ;
 514     if ( cm_debugDnlc )
 515         osi_Log0(afsd_logp,"cm_dnlcInit");
 516
 517     lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
 518     memset (&dnlcstats, 0, sizeof(dnlcstats));
 519     lock_ObtainWrite(&cm_dnlcLock);
 520     ncfreelist = (struct nc *) 0;
 521     memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
 522     memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
 523     for (i=0; i<NCSIZE; i++)
 524     {
 525         nameCache[i].next = ncfreelist;
 526         ncfreelist = &nameCache[i];
 527     }
 528     lock_ReleaseWrite(&cm_dnlcLock);
 529 }
 530
 531 void
 532 cm_dnlcShutdown(void)
 533 {
 534     if ( cm_debugDnlc )
 535         osi_Log0(afsd_logp,"cm_dnlcShutdown");
 536 }