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, * tnc_begin;
 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     tnc_begin = nameHash[skey];
 228     for ( tvc = (cm_scache_t *) 0, tnc = tnc_begin, safety=0;
 229        tnc; tnc = tnc->next, safety++ )
 230     {
 231         if (tnc->dirp == adp)
 232         {
 233             if ( sp->caseFold )         /* case insensitive */
 234             {
 235                 match = cm_stricmp(tnc->name, aname);
 236                 if ( !match )   /* something matches */
 237                 {
 238                         /* determine what type of match it is */
 239                         if ( !strcmp(tnc->name, aname))
 240                         {
 241                                 /* exact match, do nothing */
 242                         }
 243                         else if ( cm_NoneUpper(tnc->name))
 244                                 sp->LCfound = 1;
 245                         else if ( cm_NoneLower(tnc->name))
 246                                 sp->UCfound = 1;
 247                         else    sp->NCfound = 1;
 248                         tvc = tnc->vp;
 249                         break;
 250                 }
 251             }
 252             else                        /* case sensitive */
 253             {
 254                 match = strcmp(tnc->name, aname);
 255                 if ( !match ) /* found a match */
 256                 {
 257                         tvc = tnc->vp;
 258                         break;
 259                 }
 260             }
 261         }
 262         if (tnc->next == nameHash[skey])
 263     {                   /* end of list */
 264             break;
 265         }
 266         else if (tnc->next == tnc_begin || safety >NCSIZE)
 267         {
 268             dnlcstats.cycles++;
 269             lock_ReleaseRead(&cm_dnlcLock);
 270
 271             dnlcNotify("DNLC cycle",1);
 272             if ( cm_debugDnlc )
 273                 osi_Log0(afsd_logp, "DNLC cycle");
 274             cm_dnlcPurge();
 275             return(0);
 276         }
 277     }
 278
 279     if (!tvc)
 280         dnlcstats.misses++;     /* Is a dnlcread lock sufficient? */
 281     else
 282     {
 283         sp->found = 1;
 284         sp->fid.vnode  = tvc->fid.vnode;
 285         sp->fid.unique = tvc->fid.unique;
 286     }
 287     lock_ReleaseRead(&cm_dnlcLock);
 288
 289     if (tvc) {
 290         lock_ObtainWrite(&cm_scacheLock);
 291         tvc->refCount++;        /* scache entry held */
 292         lock_ReleaseWrite(&cm_scacheLock);
 293     }
 294
 295     if ( cm_debugDnlc && tvc )
 296         osi_Log1(afsd_logp, "cm_dnlcLookup found %x", tvc);
 297
 298     return tvc;
 299 }
 300
 301
 302 static int
 303 RemoveEntry (tnc, key)
 304     struct nc    *tnc;
 305     unsigned int key;
 306 {
 307     if (!tnc->prev) /* things on freelist always have null prev ptrs */
 308     {
 309         dnlcNotify("Bogus dnlc freelist", 1);
 310         osi_Log0(afsd_logp,"Bogus dnlc freelist");
 311         return 1;   /* error */
 312     }
 313
 314     if (tnc == tnc->next)  /* only one in list */
 315         nameHash[key] = (struct nc *) 0;
 316     else
 317     {
 318         if (tnc == nameHash[key])
 319             nameHash[key]  = tnc->next;
 320         tnc->prev->next = tnc->next;
 321         tnc->next->prev = tnc->prev;
 322     }
 323
 324     tnc->prev = (struct nc *) 0; /* everything not in hash table has 0 prev */
 325     tnc->key = 0; /* just for safety's sake */
 326     return 0;     /* success */
 327 }
 328
 329
 330 void
 331 cm_dnlcRemove ( adp, aname)
 332     cm_scache_t *adp;
 333     char          *aname;
 334 {
 335     unsigned int key, skey, error=0;
 336     int found= 0, safety;
 337     char *ts = aname;
 338     struct nc *tnc, *tmp;
 339
 340     if (!cm_useDnlc)
 341         return ;
 342
 343     if ( cm_debugDnlc )
 344         osi_Log2(afsd_logp, "cm_dnlcRemove dir %x name %s",
 345                 adp, osi_LogSaveString(afsd_logp,aname));
 346
 347     dnlcHash( ts, key );  /* leaves ts pointing at the NULL */
 348     if (ts - aname >= CM_AFSNCNAMESIZE)
 349         return ;
 350
 351     skey = key & (NHSIZE -1);
 352     lock_ObtainWrite(&cm_dnlcLock);
 353     dnlcstats.removes++;
 354
 355     for (tnc = nameHash[skey], safety=0; tnc; safety++)
 356     {
 357         if ( (tnc->dirp == adp) && (tnc->key == key)
 358                         && !cm_stricmp(tnc->name,aname) )
 359         {
 360             tnc->dirp = (cm_scache_t *) 0; /* now it won't match anything */
 361             tmp = tnc->next;
 362             error = RemoveEntry(tnc, skey);
 363             if ( error )
 364                 break;
 365
 366             tnc->next = ncfreelist; /* insert entry into freelist */
 367             ncfreelist = tnc;
 368             found = 1;          /* found atleast one entry */
 369
 370             tnc = tmp;          /* continue down the linked list */
 371         }
 372         else if (tnc->next == nameHash[skey]) /* end of list */
 373             break;
 374         else
 375             tnc = tnc->next;
 376         if ( safety > NCSIZE )
 377         {
 378             dnlcstats.cycles++;
 379             lock_ReleaseWrite(&cm_dnlcLock);
 380
 381             dnlcNotify("DNLC cycle",1);
 382             if ( cm_debugDnlc )
 383                 osi_Log0(afsd_logp, "DNLC cycle");
 384             cm_dnlcPurge();
 385             return;
 386         }
 387     }
 388     lock_ReleaseWrite(&cm_dnlcLock);
 389
 390     if (!found && !error && cm_debugDnlc)
 391         osi_Log0(afsd_logp, "cm_dnlcRemove name not found");
 392
 393     if ( error )
 394         cm_dnlcPurge();
 395 }
 396
 397 /* remove anything pertaining to this directory */
 398 void
 399 cm_dnlcPurgedp (adp)
 400   cm_scache_t *adp;
 401 {
 402     int i;
 403     int err=0;
 404
 405     if (!cm_useDnlc)
 406         return ;
 407
 408     if ( cm_debugDnlc )
 409         osi_Log1(afsd_logp, "cm_dnlcPurgedp dir %x", adp);
 410
 411     lock_ObtainWrite(&cm_dnlcLock);
 412     dnlcstats.purgeds++;
 413
 414     for (i=0; i<NCSIZE && !err; i++)
 415     {
 416         if (nameCache[i].dirp == adp )
 417         {
 418             nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
 419             if (nameCache[i].prev && !err)
 420             {
 421                 err = RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 422                 nameCache[i].next = ncfreelist;
 423                 ncfreelist = &nameCache[i];
 424             }
 425         }
 426     }
 427     lock_ReleaseWrite(&cm_dnlcLock);
 428     if ( err )
 429         cm_dnlcPurge();
 430 }
 431
 432 /* remove anything pertaining to this file */
 433 void
 434 cm_dnlcPurgevp ( avc )
 435   cm_scache_t *avc;
 436 {
 437     int i;
 438     int err=0;
 439
 440     if (!cm_useDnlc)
 441         return ;
 442
 443     if ( cm_debugDnlc )
 444         osi_Log1(afsd_logp, "cm_dnlcPurgevp scache %x", avc);
 445
 446     lock_ObtainWrite(&cm_dnlcLock);
 447     dnlcstats.purgevs++;
 448
 449     for (i=0; i<NCSIZE && !err ; i++)
 450     {
 451         if (nameCache[i].vp == avc)
 452         {
 453             nameCache[i].dirp = nameCache[i].vp = (cm_scache_t *) 0;
 454             /* can't simply break; because of hard links -- might be two */
 455             /* different entries with same vnode */
 456             if (!err && nameCache[i].prev)
 457             {
 458                 err=RemoveEntry(&nameCache[i], nameCache[i].key & (NHSIZE-1));
 459                 nameCache[i].next = ncfreelist;
 460                 ncfreelist = &nameCache[i];
 461             }
 462         }
 463     }
 464     lock_ReleaseWrite(&cm_dnlcLock);
 465     if ( err )
 466         cm_dnlcPurge();
 467 }
 468
 469 /* remove everything */
 470 void cm_dnlcPurge(void)
 471 {
 472     int i;
 473
 474     if (!cm_useDnlc)
 475         return ;
 476
 477     if ( cm_debugDnlc )
 478         osi_Log0(afsd_logp, "cm_dnlcPurge");
 479
 480     lock_ObtainWrite(&cm_dnlcLock);
 481     dnlcstats.purges++;
 482
 483     ncfreelist = (struct nc *) 0;
 484     memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
 485     memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
 486     for (i=0; i<NCSIZE; i++)
 487     {
 488         nameCache[i].next = ncfreelist;
 489         ncfreelist = &nameCache[i];
 490     }
 491     lock_ReleaseWrite(&cm_dnlcLock);
 492
 493 }
 494
 495 /* remove everything referencing a specific volume */
 496 void
 497 cm_dnlcPurgeVol( fidp )
 498   AFSFid *fidp;
 499 {
 500
 501     if (!cm_useDnlc)
 502         return ;
 503
 504     dnlcstats.purgevols++;
 505     cm_dnlcPurge();
 506 }
 507
 508 void
 509 cm_dnlcInit(void)
 510 {
 511     int i;
 512
 513     if (!cm_useDnlc)
 514         return ;
 515     if ( cm_debugDnlc )
 516         osi_Log0(afsd_logp,"cm_dnlcInit");
 517
 518     lock_InitializeRWLock(&cm_dnlcLock, "cm_dnlcLock");
 519     memset (&dnlcstats, 0, sizeof(dnlcstats));
 520     lock_ObtainWrite(&cm_dnlcLock);
 521     ncfreelist = (struct nc *) 0;
 522     memset (nameCache, 0, sizeof(struct nc) * NCSIZE);
 523     memset (nameHash, 0, sizeof(struct nc *) * NHSIZE);
 524     for (i=0; i<NCSIZE; i++)
 525     {
 526         nameCache[i].next = ncfreelist;
 527         ncfreelist = &nameCache[i];
 528     }
 529     lock_ReleaseWrite(&cm_dnlcLock);
 530 }
 531
 532 void
 533 cm_dnlcShutdown(void)
 534 {
 535     if ( cm_debugDnlc )
 536         osi_Log0(afsd_logp,"cm_dnlcShutdown");
 537 }