Complete removal of DUX client code
[openafs.git] / 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 <afsconfig.h>
75 #include "afs/param.h"
76
77
78 #include "afs/sysincludes.h"    /*Standard vendor system headers */
79 #include "afsincludes.h"        /*AFS-based standard headers */
80 #include "afs/afs_cbqueue.h"
81 #include "afs/afs.h"
82 #include "afs/lock.h"
83 #include "afs/afs_stats.h"
84
85 static unsigned int base = 0;
86 static unsigned int basetime = 0;
87 static struct vcache *debugvc;  /* used only for post-mortem debugging */
88 struct bucket {
89     struct afs_q head;
90     /*  struct afs_lock lock;  only if you want lots of locks... */
91 };
92 static struct bucket cbHashT[CBHTSIZE];
93 struct afs_lock afs_xcbhash;
94
95 /* afs_QueueCallback
96  * Takes a write-locked vcache pointer and a callback expiration time
97  * as returned by the file server (ie, in units of 128 seconds from "now").
98  * 
99  * Uses the time as an index into a hash table, and inserts the vcache
100  * structure into the overflow chain.
101  * 
102  * If the vcache is already on some hash chain, leave it there.
103  * CheckCallbacks will get to it eventually.  In the meantime, it
104  * might get flushed, or it might already be on the right hash chain, 
105  * so why bother messing with it now?
106  *
107  * NOTE: The caller must hold a write lock on afs_xcbhash
108  */
109
110 void
111 afs_QueueCallback(struct vcache *avc, unsigned int atime, struct volume *avp)
112 {
113     if (avp && (avp->expireTime < avc->cbExpires))
114         avp->expireTime = avc->cbExpires;
115     if (!(avc->callsort.next)) {
116         atime = (atime + base) % CBHTSIZE;
117         QAdd(&(cbHashT[atime].head), &(avc->callsort));
118     }
119
120     return;
121 }                               /* afs_QueueCallback */
122
123 /* afs_DequeueCallback
124  * Takes a write-locked vcache pointer and removes it from the callback
125  * hash table, without knowing beforehand which slot it was in.
126  *
127  * for now, just get a lock on everything when doing the dequeue, don't
128  * worry about getting a lock on the individual slot.
129  * 
130  * the only other places that do anything like dequeues are CheckCallbacks
131  * and BumpBase.
132  *
133  * NOTE: The caller must hold a write lock on afs_xcbhash
134  */
135 void
136 afs_DequeueCallback(struct vcache *avc)
137 {
138
139     debugvc = avc;
140     if (avc->callsort.prev) {
141         QRemove(&(avc->callsort));
142     } else;                     /* must have got dequeued in a race */
143
144     return;
145 }                               /* afs_DequeueCallback */
146
147 /* afs_CheckCallbacks
148  * called periodically to determine which callbacks are likely to
149  * expire in the next n second interval.  Preemptively marks them as
150  * expired.  Rehashes items which are now in the wrong hash bucket.
151  * Preemptively renew recently-accessed items.  Only removes things
152  * from the first and second bucket (as long as secs < 128), and
153  * inserts things into other, later buckets.  either need to advance
154  * to the second bucket if secs spans two intervals, or else be
155  * certain to call afs_CheckCallbacks immediately after calling
156  * BumpBase (allows a little more slop but it's ok because file server
157  * keeps 3 minutes of slop time)
158  *
159  * There is a little race between CheckCallbacks and any code which
160  * updates cbExpires, always just prior to calling QueueCallback. We
161  * don't lock the vcache struct here (can't, or we'd risk deadlock),
162  * so GetVCache (for example) may update cbExpires before or after #1
163  * below.  If before, CheckCallbacks moves this entry to its proper
164  * slot.  If after, GetVCache blocks in the call to QueueCallbacks,
165  * this code dequeues the vcache, and then QueueCallbacks re-enqueues it. 
166  *
167  * XXX to avoid the race, make QueueCallback take the "real" time
168  * and update cbExpires under the xcbhash lock. 
169  *
170  * NB #1: There's a little optimization here: if I go to invalidate a
171  * RO vcache or volume, first check to see if the server is down.  If
172  * it _is_, don't invalidate it, cuz we might just as well keep using
173  * it.  Possibly, we could do the same thing for items in RW volumes,
174  * but that bears some drinking about.
175  *
176  * Don't really need to invalidate the hints, we could just wait to see if
177  * the dv has changed after a subsequent FetchStatus, but this is safer.
178  */
179
180 /* Sanity check on the callback queue. Allow for slop in the computation. */
181 #if defined(AFS_LINUX22_ENV)
182 #define CBQ_LIMIT (afs_maxvcount + 10)
183 #else
184 #define CBQ_LIMIT (afs_cacheStats + afs_stats_cmperf.vcacheXAllocs + 10)
185 #endif
186
187 void
188 afs_CheckCallbacks(unsigned int secs)
189 {
190     struct vcache *tvc;
191     register struct afs_q *tq;
192     struct afs_q *uq;
193     afs_uint32 now;
194     struct volume *tvp;
195     register int safety;
196
197     ObtainWriteLock(&afs_xcbhash, 85);  /* pretty likely I'm going to remove something */
198     now = osi_Time();
199     for (safety = 0, tq = cbHashT[base].head.prev;
200          (safety <= CBQ_LIMIT) && (tq != &(cbHashT[base].head));
201          tq = uq, safety++) {
202
203         uq = QPrev(tq);
204         tvc = CBQTOV(tq);
205         if (tvc->cbExpires < now + secs) {      /* race #1 here */
206             /* Get the volume, and if its callback expiration time is more than secs
207              * seconds into the future, update this vcache entry and requeue it below
208              */
209             if ((tvc->f.states & CRO)
210                 && (tvp = afs_FindVolume(&(tvc->f.fid), READ_LOCK))) {
211                 if (tvp->expireTime > now + secs) {
212                     tvc->cbExpires = tvp->expireTime;   /* XXX race here */
213                 } else {
214                     int i;
215                     for (i = 0; i < MAXHOSTS && tvp->serverHost[i]; i++) {
216                         if (!(tvp->serverHost[i]->flags & SRVR_ISDOWN)) {
217                             /* What about locking xvcache or vrefcount++ or
218                              * write locking tvc? */
219                             QRemove(tq);
220                             tvc->f.states &= ~(CStatd | CMValid | CUnique);
221                             if (!(tvc->f.states & (CVInit|CVFlushed)) &&
222                                 (tvc->f.fid.Fid.Vnode & 1 ||
223                                  (vType(tvc) == VDIR)))
224                                 osi_dnlc_purgedp(tvc);
225                             tvc->dchint = NULL; /*invalidate em */
226                             afs_ResetVolumeInfo(tvp);
227                             break;
228                         }
229                     }
230                 }
231                 afs_PutVolume(tvp, READ_LOCK);
232             } else {
233                 /* Do I need to worry about things like execsorwriters?
234                  * What about locking xvcache or vrefcount++ or write locking tvc?
235                  */
236                 QRemove(tq);
237                 tvc->f.states &= ~(CStatd | CMValid | CUnique);
238                 if (!(tvc->f.states & (CVInit|CVFlushed)) &&
239                     (tvc->f.fid.Fid.Vnode & 1 || (vType(tvc) == VDIR)))
240                     osi_dnlc_purgedp(tvc);
241             }
242         }
243
244         if ((tvc->cbExpires > basetime) && CBHash(tvc->cbExpires - basetime)) {
245             /* it's been renewed on us.  Have to be careful not to put it back
246              * into this slot, or we may never get out of here.
247              */
248             int slot;
249             slot = (CBHash(tvc->cbExpires - basetime) + base) % CBHTSIZE;
250             if (slot != base) {
251                 if (QPrev(tq))
252                     QRemove(&(tvc->callsort));
253                 QAdd(&(cbHashT[slot].head), &(tvc->callsort));
254                 /* XXX remember to update volume expiration time */
255                 /* -- not needed for correctness, though */
256             }
257         }
258     }
259
260     if (safety > CBQ_LIMIT) {
261         afs_stats_cmperf.cbloops++;
262         if (afs_paniconwarn)
263             osi_Panic("CheckCallbacks");
264
265         afs_warn
266             ("AFS Internal Error (minor): please contact AFS Product Support.\n");
267         ReleaseWriteLock(&afs_xcbhash);
268         afs_FlushCBs();
269         return;
270     } else
271         ReleaseWriteLock(&afs_xcbhash);
272
273
274 /* XXX future optimization:
275    if this item has been recently accessed, queue up a stat for it.
276    {
277    struct dcache * adc;
278
279    ObtainReadLock(&afs_xdcache);
280    if ((adc = tvc->quick.dc) && (adc->stamp == tvc->quick.stamp)
281    && (afs_indexTimes[adc->index] > afs_indexCounter - 20)) {
282    queue up the stat request
283    }
284    ReleaseReadLock(&afs_xdcache);
285    }
286    */
287
288     return;
289 }                               /* afs_CheckCallback */
290
291 /* afs_FlushCBs 
292  * to be used only in dire circumstances, this drops all callbacks on
293  * the floor, without giving them back to the server.  It's ok, the server can 
294  * deal with it, but it is a little bit rude.
295  */
296 void
297 afs_FlushCBs(void)
298 {
299     register int i;
300     register struct vcache *tvc;
301
302     ObtainWriteLock(&afs_xcbhash, 86);  /* pretty likely I'm going to remove something */
303
304     for (i = 0; i < VCSIZE; i++)        /* reset all the vnodes */
305         for (tvc = afs_vhashT[i]; tvc; tvc = tvc->hnext) {
306             tvc->callback = 0;
307             tvc->dchint = NULL; /* invalidate hints */
308             tvc->f.states &= ~(CStatd);
309             if (QPrev(&(tvc->callsort)))
310                 QRemove(&(tvc->callsort));
311             if (!(tvc->f.states & (CVInit|CVFlushed)) &&
312                 ((tvc->f.fid.Fid.Vnode & 1) || (vType(tvc) == VDIR)))
313                 osi_dnlc_purgedp(tvc);
314         }
315
316     afs_InitCBQueue(0);
317
318     ReleaseWriteLock(&afs_xcbhash);
319 }
320
321 /* afs_FlushServerCBs
322  * to be used only in dire circumstances, this drops all callbacks on
323  * the floor for a specific server, without giving them back to the server.
324  * It's ok, the server can deal with it, but it is a little bit rude.
325  */
326 void
327 afs_FlushServerCBs(struct server *srvp)
328 {
329     register int i;
330     register struct vcache *tvc;
331
332     ObtainWriteLock(&afs_xcbhash, 86);  /* pretty likely I'm going to remove something */
333
334     for (i = 0; i < VCSIZE; i++) {      /* reset all the vnodes */
335         for (tvc = afs_vhashT[i]; tvc; tvc = tvc->hnext) {
336             if (tvc->callback == srvp) {
337                 tvc->callback = 0;
338                 tvc->dchint = NULL;     /* invalidate hints */
339                 tvc->f.states &= ~(CStatd);
340                 if (!(tvc->f.states & (CVInit|CVFlushed)) &&
341                     ((tvc->f.fid.Fid.Vnode & 1) || (vType(tvc) == VDIR))) {
342                     osi_dnlc_purgedp(tvc);
343                 }
344                 afs_DequeueCallback(tvc);
345             }
346         }
347     }
348
349     ReleaseWriteLock(&afs_xcbhash);
350 }
351
352 /* afs_InitCBQueue
353  *  called to initialize static and global variables associated with
354  *  the Callback expiration management mechanism.
355  */
356 void
357 afs_InitCBQueue(int doLockInit)
358 {
359     register int i;
360
361     memset(cbHashT, 0, CBHTSIZE * sizeof(struct bucket));
362     for (i = 0; i < CBHTSIZE; i++) {
363         QInit(&(cbHashT[i].head));
364         /* Lock_Init(&(cbHashT[i].lock)); only if you want lots of locks, which 
365          * don't seem too useful at present.  */
366     }
367     base = 0;
368     basetime = osi_Time();
369     if (doLockInit)
370         Lock_Init(&afs_xcbhash);
371 }
372
373 /* Because there are no real-time guarantees, and especially because a
374  * thread may wait on a lock indefinitely, this routine has to be
375  * careful that it doesn't get permanently out-of-date.  Important
376  * assumption: this routine is only called from afs_Daemon, so there
377  * can't be more than one instance of this running at any one time.
378  * Presumes that basetime is never 0, and is always sane. 
379  *
380  * Before calling this routine, be sure that the first slot is pretty
381  * empty.  This -20 is because the granularity of the checks in
382  * afs_Daemon is pretty large, so I'd rather err on the side of safety
383  * sometimes.  The fact that I only bump basetime by CBHTSLOTLEN-1
384  * instead of the whole CBHTSLOTLEN is also for "safety".
385  * Conceptually, it makes this clock run just a little faster than the
386  * clock governing which slot a callback gets hashed into.  Both of these 
387  * things make CheckCallbacks work a little harder than it would have to 
388  * if I wanted to cut things finer.
389  * Everything from the old first slot is carried over into the new first
390  * slot.  Thus, if there were some things that ought to have been invalidated,
391  * but weren't (say, if the server was down), they will be examined at every
392  * opportunity thereafter.
393  */
394 int
395 afs_BumpBase(void)
396 {
397     afs_uint32 now;
398     int didbump;
399     u_int oldbase;
400
401     ObtainWriteLock(&afs_xcbhash, 87);
402     didbump = 0;
403     now = osi_Time();
404     while (basetime + (CBHTSLOTLEN - 20) <= now) {
405         oldbase = base;
406         basetime += CBHTSLOTLEN - 1;
407         base = (base + 1) % CBHTSIZE;
408         didbump++;
409         if (!QEmpty(&(cbHashT[oldbase].head))) {
410             QCat(&(cbHashT[oldbase].head), &(cbHashT[base].head));
411         }
412     }
413     ReleaseWriteLock(&afs_xcbhash);
414
415     return didbump;
416 }