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