src/WINNT/afsd/cm_dnlc.c

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