src/afs/afs_cbqueue.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 package is used to actively manage the expiration of callbacks,
  12  * so that the rest of the cache manager doesn't need to compute
  13  * whether a callback has expired or not, but can tell with one simple
  14  * check, that is, whether the CStatd bit is on or off.
  15  *
  16  * The base of the hash table moves periodically (every 128 seconds)
  17  * QueueCallback rarely touches the first 3 slots in the hash table
  18  * (only when called from CheckCallbacks) since MinTimeOut in
  19  * viced/callback.c is currently 7 minutes.
  20  * Therefore, CheckCallbacks should be able to run concurrently with
  21  * QueueCallback, given the proper locking, of course.
  22  *
  23  * Note:
  24  * 1. CheckCallbacks and BumpBase never run simultaneously.  This is because
  25  * they are only called from afs_Daemon.  Therefore, base and basetime will
  26  * always be consistent during CheckCallbacks.
  27  * 2. cbHashT [base] rarely (if ever) gets stuff queued in it.  The only way
  28  * that could happen is CheckCallbacks might fencepost and move something in
  29  * place, or BumpBase might push some stuff up.
  30  * 3. Hash chains aren't particularly sorted.
  31  * 4. The file server keeps its callback state around for 3 minutes
  32  * longer than it promises the cache manager in order to account for
  33  * clock skew, network delay, and other bogeymen.
  34  *
  35  * For now I just use one large lock, which is fine on a uniprocessor,
  36  * since it's not held during any RPCs or low-priority I/O operations.
  37  * To make this code MP-fast, you need no more locks than processors,
  38  * but probably more than one.  In measurements on MP-safe implementations,
  39  * I have never seen any contention over the xcbhash lock.
  40  *
  41  * Incompatible operations:
  42  * Enqueue and "dequeue of first vcache" in same slot
  43  * dequeue and "dequeue of preceding vcache" in same slot
  44  * dequeue and "dequeue of successive vcache" in same slot
  45  * BumpBase pushing a list and enqueue in the new base slot
  46  * Two enqueues in same slot
  47  * more...
  48  *
  49  * Certain invariants exist:
  50  *    1  Callback expiration times granted by a file server will never
  51  *       decrease for a particular vnode UNLESS a CallBack RPC is invoked
  52  *       by the server in the interim.
  53  *    2  A vcache will always expire no sooner than the slot in which it is
  54  *       currently enqueued.  Callback times granted by the server may
  55  *       increase, in which case the vcache will be updated in-place.  As a
  56  *       result, it may expire later than the slot in which it is enqueued.
  57  *       Not to worry, the CheckCallbacks code will move it if neccessary.
  58  *       This approach means that busy vnodes won't be continually moved
  59  *       around within the expiry queue: they are only moved when they
  60  *       finally advance to the lead bucket.
  61  *    3  Anything which has a callback on it must be in the expiry
  62  *       queue.  In AFS 3.3, that means everything but symlinks (which
  63  *       are immutable), including contents of Read-Only volumes
  64  *       (which have callbacks by virtue of the whole-volume callback)
  65  *
  66  * QueueCallback only checks that its vcache is in the list
  67  * somewhere, counting on invariant #1 to guarantee that the vcache
  68  * won't be in a slot later than QueueCallback would otherwise place
  69  * it. Therefore, whenever we turn off the CStatd bit on the vcache, we
  70  * *must* remove the vcache from the expiry queue.  Otherwise, we
  71  * might have missed a CallBack RPC, and a subsequent callback might be
  72  * granted with a shorter expiration time.
  73  */
  74 #include "../afs/param.h"       /*Should be always first*/
  75 #include "../afs/sysincludes.h" /*Standard vendor system headers*/
  76 #include "../afs/afsincludes.h" /*AFS-based standard headers*/
  77 #include "../afs/afs_cbqueue.h"
  78 #include "afs/afs.h"
  79 #include "../afs/lock.h"
  80 #include "../afs/afs_stats.h"
  81
  82 static unsigned int base = 0;
  83 static unsigned int basetime = 0;
  84 static struct vcache *debugvc;  /* used only for post-mortem debugging */
  85 struct bucket {
  86   struct afs_q head;
  87   /*  struct afs_lock lock;  only if you want lots of locks... */
  88 };
  89 struct bucket cbHashT[CBHTSIZE];
  90 struct afs_lock afs_xcbhash;
  91 extern afs_int32 afs_cacheStats;
  92 extern struct volume * afs_FindVolume();
  93 extern unsigned int afs_paniconwarn;
  94 void afs_FlushCBs();
  95
  96 /* afs_QueueCallback
  97  * Takes a write-locked vcache pointer and a callback expiration time
  98  * as returned by the file server (ie, in units of 128 seconds from "now").
  99  *
 100  * Uses the time as an index into a hash table, and inserts the vcache
 101  * structure into the overflow chain.
 102  *
 103  * If the vcache is already on some hash chain, leave it there.
 104  * CheckCallbacks will get to it eventually.  In the meantime, it
 105  * might get flushed, or it might already be on the right hash chain,
 106  * so why bother messing with it now?
 107  *
 108  * NOTE: The caller must hold a write lock on afs_xcbhash
 109  */
 110
 111 void afs_QueueCallback(avc, atime, avp)
 112 struct vcache *avc;
 113 unsigned int atime;
 114 struct volume *avp;
 115 {
 116 struct vcache *list;
 117
 118 if (avp && (avp->expireTime < avc->cbExpires))
 119   avp->expireTime = avc->cbExpires;
 120 if (!(avc->callsort.next)) {
 121   atime = (atime + base) % CBHTSIZE;
 122   QAdd(&(cbHashT[atime].head), &(avc->callsort));
 123 }
 124
 125 return ;
 126 } /* afs_QueueCallback */
 127
 128 /* afs_DequeueCallback
 129  * Takes a write-locked vcache pointer and removes it from the callback
 130  * hash table, without knowing beforehand which slot it was in.
 131  *
 132  * for now, just get a lock on everything when doing the dequeue, don't
 133  * worry about getting a lock on the individual slot.
 134  *
 135  * the only other places that do anything like dequeues are CheckCallbacks
 136  * and BumpBase.
 137  *
 138  * NOTE: The caller must hold a write lock on afs_xcbhash
 139  */
 140 void afs_DequeueCallback(avc)
 141 struct vcache *avc;
 142 {
 143
 144   debugvc=avc;
 145   if (avc->callsort.prev) {
 146     QRemove(&(avc->callsort));
 147     avc->callsort.prev = avc->callsort.next = NULL;
 148   }
 149   else ; /* must have got dequeued in a race */
 150   afs_symhint_inval(avc);
 151
 152   return;
 153 } /* afs_DequeueCallback */
 154
 155 /* afs_CheckCallbacks
 156  * called periodically to determine which callbacks are likely to
 157  * expire in the next n second interval.  Preemptively marks them as
 158  * expired.  Rehashes items which are now in the wrong hash bucket.
 159  * Preemptively renew recently-accessed items.  Only removes things
 160  * from the first and second bucket (as long as secs < 128), and
 161  * inserts things into other, later buckets.  either need to advance
 162  * to the second bucket if secs spans two intervals, or else be
 163  * certain to call afs_CheckCallbacks immediately after calling
 164  * BumpBase (allows a little more slop but it's ok because file server
 165  * keeps 3 minutes of slop time)
 166  *
 167  * There is a little race between CheckCallbacks and any code which
 168  * updates cbExpires, always just prior to calling QueueCallback. We
 169  * don't lock the vcache struct here (can't, or we'd risk deadlock),
 170  * so GetVCache (for example) may update cbExpires before or after #1
 171  * below.  If before, CheckCallbacks moves this entry to its proper
 172  * slot.  If after, GetVCache blocks in the call to QueueCallbacks,
 173  * this code dequeues the vcache, and then QueueCallbacks re-enqueues it.
 174  *
 175  * XXX to avoid the race, make QueueCallback take the "real" time
 176  * and update cbExpires under the xcbhash lock.
 177  *
 178  * NB #1: There's a little optimization here: if I go to invalidate a
 179  * RO vcache or volume, first check to see if the server is down.  If
 180  * it _is_, don't invalidate it, cuz we might just as well keep using
 181  * it.  Possibly, we could do the same thing for items in RW volumes,
 182  * but that bears some drinking about.
 183  *
 184  * Don't really need to invalidate the hints, we could just wait to see if
 185  * the dv has changed after a subsequent FetchStatus, but this is safer.
 186  */
 187
 188 /* Sanity check on the callback queue. Allow for slop in the computation. */
 189 #ifdef AFS_OSF_ENV
 190 extern afs_int32 afs_maxvcount;
 191 #define CBQ_LIMIT (afs_maxvcount + 10)
 192 #else
 193 #define CBQ_LIMIT (afs_cacheStats + afs_stats_cmperf.vcacheXAllocs + 10)
 194 #endif
 195
 196 void afs_CheckCallbacks(secs)
 197 unsigned int secs;
 198 {
 199   struct vcache *tvc;
 200   register struct afs_q *tq;
 201   struct afs_q *uq;
 202   afs_uint32 now;
 203   struct volume *tvp;
 204   register int safety;
 205
 206   ObtainWriteLock(&afs_xcbhash,85);  /* pretty likely I'm going to remove something */
 207   now=osi_Time();
 208   for(safety = 0, tq = cbHashT[base].head.prev;
 209      (safety <= CBQ_LIMIT) && (tq != &(cbHashT[base].head));
 210       tq = uq, safety++) {
 211
 212     uq = QPrev(tq);
 213     tvc = CBQTOV(tq);
 214     if (tvc->cbExpires < now + secs) {  /* race #1 here */
 215       /* Get the volume, and if its callback expiration time is more than secs
 216        * seconds into the future, update this vcache entry and requeue it below
 217        */
 218        if ((tvc->states & CRO) && (tvp=afs_FindVolume(&(tvc->fid), READ_LOCK))) {
 219           if (tvp->expireTime > now + secs) {
 220              tvc->cbExpires = tvp->expireTime;     /* XXX race here */
 221           }
 222           else {
 223              int i;
 224              for (i=0; i < MAXHOSTS && tvp->serverHost[i]; i++) {
 225                 if (!(tvp->serverHost[i]->flags & SRVR_ISDOWN)) {
 226                    /* What about locking xvcache or vrefcount++ or
 227                     * write locking tvc? */
 228                    QRemove(tq);
 229                    tq->prev = tq->next = NULL;
 230                    tvc->states &= ~(CStatd | CMValid | CUnique);
 231                    if ((tvc->fid.Fid.Vnode & 1) || (vType(tvc) == VDIR))
 232                       osi_dnlc_purgedp(tvc);
 233                    tvc->quick.stamp = 0;
 234                    tvc->h1.dchint = NULL;/*invalidate em */
 235                    afs_ResetVolumeInfo(tvp);
 236                    break;
 237                 }
 238              }
 239           }
 240           afs_PutVolume(tvp, READ_LOCK);
 241        }
 242        else {
 243          /* Do I need to worry about things like execsorwriters?
 244           * What about locking xvcache or vrefcount++ or write locking tvc?
 245           */
 246          QRemove(tq);
 247          tq->prev = tq->next = NULL;
 248          tvc->states &= ~(CStatd | CMValid | CUnique);
 249          if ((tvc->fid.Fid.Vnode & 1) || (vType(tvc) == VDIR))
 250             osi_dnlc_purgedp(tvc);
 251        }
 252     }
 253
 254     if ((tvc->cbExpires > basetime) && CBHash(tvc->cbExpires - basetime)) {
 255       /* it's been renewed on us.  Have to be careful not to put it back
 256        * into this slot, or we may never get out of here.
 257        */
 258       int slot;
 259       slot = (CBHash(tvc->cbExpires - basetime)+base)%CBHTSIZE ;
 260       if (slot != base) {
 261         if (QPrev(tq))
 262           QRemove(&(tvc->callsort));
 263         QAdd( &(cbHashT[slot].head), &(tvc->callsort) );
 264         /* XXX remember to update volume expiration time */
 265         /* -- not needed for correctness, though */
 266       }
 267     }
 268   }
 269
 270   if (safety > CBQ_LIMIT) {
 271     afs_stats_cmperf.cbloops++;
 272     if (afs_paniconwarn)
 273       osi_Panic ("CheckCallbacks");
 274
 275     afs_warn("AFS Internal Error (minor): please contact AFS Product Support.\n");
 276     ReleaseWriteLock(&afs_xcbhash);
 277     afs_FlushCBs();
 278     return;
 279   }
 280   else ReleaseWriteLock(&afs_xcbhash);
 281
 282
 283 /* XXX future optimization:
 284    if this item has been recently accessed, queue up a stat for it.
 285    {
 286    struct dcache * adc;
 287
 288    if ((adc = tvc->quick.dc) && (adc->stamp == tvc->quick.stamp)
 289    && (afs_indexTimes[adc->index] > afs_indexCounter - 20)) {
 290    queue up the stat request
 291    }
 292    }
 293    */
 294
 295 return;
 296 } /* afs_CheckCallback */
 297
 298 /* afs_FlushCBs
 299  * to be used only in dire circumstances, this drops all callbacks on
 300  * the floor, without giving them back to the server.  It's ok, the server can
 301  * deal with it, but it is a little bit rude.
 302  */
 303 void afs_FlushCBs()
 304 {
 305   register int i;
 306   register struct vcache *tvc;
 307
 308   ObtainWriteLock(&afs_xcbhash,86);  /* pretty likely I'm going to remove something */
 309
 310     for (i = 0; i < VCSIZE; i++)  /* reset all the vnodes */
 311       for (tvc = afs_vhashT[i]; tvc; tvc = tvc->hnext) {
 312         tvc->callback = 0;
 313         tvc->quick.stamp = 0;
 314         tvc->h1.dchint = NULL; /* invalidate hints */
 315         tvc->states &= ~(CStatd);
 316         if ((tvc->fid.Fid.Vnode & 1) || (vType(tvc) == VDIR))
 317            osi_dnlc_purgedp(tvc);
 318         tvc->callsort.prev = tvc->callsort.next = NULL;
 319       }
 320
 321     afs_InitCBQueue(0);
 322
 323     ReleaseWriteLock(&afs_xcbhash);
 324 }
 325
 326 /* afs_FlushServerCBs
 327  * to be used only in dire circumstances, this drops all callbacks on
 328  * the floor for a specific server, without giving them back to the server.
 329  * It's ok, the server can deal with it, but it is a little bit rude.
 330  */
 331 void afs_FlushServerCBs(srvp)
 332 struct server *srvp;
 333 {
 334   register int i;
 335   register struct vcache *tvc;
 336
 337   ObtainWriteLock(&afs_xcbhash,86);  /* pretty likely I'm going to remove something */
 338
 339   for (i=0; i<VCSIZE; i++) { /* reset all the vnodes */
 340      for (tvc=afs_vhashT[i]; tvc; tvc=tvc->hnext) {
 341         if (tvc->callback == srvp) {
 342            tvc->callback = 0;
 343            tvc->quick.stamp = 0;
 344            tvc->h1.dchint = NULL; /* invalidate hints */
 345            tvc->states &= ~(CStatd);
 346            if ((tvc->fid.Fid.Vnode & 1) || (vType(tvc) == VDIR)) {
 347               osi_dnlc_purgedp(tvc);
 348            }
 349            afs_DequeueCallback(tvc);
 350         }
 351      }
 352   }
 353
 354   ReleaseWriteLock(&afs_xcbhash);
 355 }
 356
 357 /* afs_InitCBQueue
 358  *  called to initialize static and global variables associated with
 359  *  the Callback expiration management mechanism.
 360  */
 361 void afs_InitCBQueue(doLockInit)
 362 int doLockInit;
 363 {
 364 register int i;
 365
 366 bzero((char *)cbHashT, CBHTSIZE*sizeof(struct bucket));
 367 for (i=0;i<CBHTSIZE;i++) {
 368   QInit(&(cbHashT[i].head));
 369   /* Lock_Init(&(cbHashT[i].lock)); only if you want lots of locks, which
 370    * don't seem too useful at present.  */
 371   }
 372 base = 0;
 373 basetime = osi_Time();
 374 if (doLockInit)
 375     Lock_Init(&afs_xcbhash);
 376 }
 377
 378 /* Because there are no real-time guarantees, and especially because a
 379  * thread may wait on a lock indefinitely, this routine has to be
 380  * careful that it doesn't get permanently out-of-date.  Important
 381  * assumption: this routine is only called from afs_Daemon, so there
 382  * can't be more than one instance of this running at any one time.
 383  * Presumes that basetime is never 0, and is always sane.
 384  *
 385  * Before calling this routine, be sure that the first slot is pretty
 386  * empty.  This -20 is because the granularity of the checks in
 387  * afs_Daemon is pretty large, so I'd rather err on the side of safety
 388  * sometimes.  The fact that I only bump basetime by CBHTSLOTLEN-1
 389  * instead of the whole CBHTSLOTLEN is also for "safety".
 390  * Conceptually, it makes this clock run just a little faster than the
 391  * clock governing which slot a callback gets hashed into.  Both of these
 392  * things make CheckCallbacks work a little harder than it would have to
 393  * if I wanted to cut things finer.
 394  * Everything from the old first slot is carried over into the new first
 395  * slot.  Thus, if there were some things that ought to have been invalidated,
 396  * but weren't (say, if the server was down), they will be examined at every
 397  * opportunity thereafter.
 398  */
 399 int afs_BumpBase()
 400 {
 401 afs_uint32 now;
 402 int didbump;
 403 struct vcache *tvca, *tvcb;
 404 afs_int32 ttime;
 405 u_int oldbase;
 406
 407 ObtainWriteLock(&afs_xcbhash,87);
 408 didbump = 0;
 409 now = osi_Time();
 410 while ( basetime + (CBHTSLOTLEN-20) <= now ) {
 411     oldbase=base;
 412     basetime += CBHTSLOTLEN-1;
 413     base = (base+1) % CBHTSIZE;
 414     didbump++;
 415     if (!QEmpty(&(cbHashT[oldbase].head))) {
 416       QCat(&(cbHashT[oldbase].head), &(cbHashT[base].head));
 417     }
 418   }
 419 ReleaseWriteLock(&afs_xcbhash);
 420
 421 return didbump;
 422 }
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436