prefer-ubik-print-to-printf-20010403
[openafs.git] / src / ubik / vote.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 #include <afs/param.h>
11 #include <sys/types.h>
12 #ifdef AFS_NT40_ENV
13 #include <winsock2.h>
14 #else
15 #include <sys/file.h>
16 #include <netinet/in.h>
17 #endif
18 #include <afs/afsutil.h>
19 #include <lock.h>
20 #include <rx/xdr.h>
21 #include <rx/rx.h>
22 #include <afs/afsutil.h>
23 #include <time.h>
24
25 #define UBIK_INTERNALS
26 #include "ubik.h"
27 #include "ubik_int.h"
28
29 /*
30     General Ubik Goal:
31     The goal is to provide reliable operation among N servers, such that any
32     server can crash with the remaining servers continuing operation within a
33     short period of time.  While a *short* outage is acceptable, this time
34     should be order of 3 minutes or less.
35     
36     Theory of operation:
37     
38     Note: SMALLTIME and BIGTIME are essentially the same time value, separated
39     only by the clock skew, MAXSKEW.  In general, if you are making guarantees
40     for someone else, promise them no more than SMALLTIME seconds of whatever
41     invariant you provide.  If you are waiting to be sure some invariant is now
42     *false*, wait at least BIGTIME seconds to be sure that SMALLTIME seconds
43     has passed at the other site.
44
45     Now, back to the design:
46     One site in the collection is a special site, designated the *sync* site.
47     The sync site sends periodic messages, which can be thought of as
48     keep-alive messages.  When a non-sync site hears from the sync site, it
49     knows that it is getting updates for the next SMALLTIME seconds from that
50     sync site.
51     
52     If a server does not hear from the sync site in SMALLTIME seconds, it
53     determines that it no longer is getting updates, and thus refuses to give
54     out potentially out-of-date data.  If a sync site can not muster a majority
55     of servers to agree that it is the sync site, then there is a possibility
56     that a network partition has occurred, allowing another server to claim to
57     be the sync site.  Thus, any time that the sync site has not heard from a
58     majority of the servers in the last SMALLTIME seconds, it voluntarily
59     relinquishes its role as sync site.
60     
61     While attempting to nominate a new sync site, certain rules apply.  First,
62     a server can not reply "ok" (return 1 from ServBeacon) to two different
63     hosts in less than BIGTIME seconds; this allows a server that has heard
64     affirmative replies from a majority of the servers to know that no other
65     server in the network has heard enough affirmative replies in the last
66     BIGTIME seconds to become sync site, too.  The variables ubik_lastYesTime
67     and lastYesHost are used by all servers to keep track of which host they
68     have last replied affirmatively to, when queried by a potential new sync
69     site.
70     
71     Once a sync site has become a sync site, it periodically sends beacon
72     messages with a parameter of 1, indicating that it already has determined
73     it is supposed to be the sync site.  The servers treat such a message as a
74     guarantee that no other site will become sync site for the next SMALLTIME
75     seconds.  In the interim, these servers can answer a query concerning which
76     site is the sync site without any communication with any server.  The
77     variables lastBeaconArrival and lastBeaconHost are used by all servers to
78     keep track of which sync site has last contacted them.
79     
80     One complication occurs while nominating a new sync site: each site may be
81     trying to nominate a different site (based on the value of lastYesHost),
82     yet we must nominate the smallest host (under some order), to prevent this
83     process from looping.  The process could loop by having each server give
84     one vote to another server, but with no server getting a majority of the
85     votes.  To avoid this, we try to withhold our votes for the server with the
86     lowest internet address (an easy-to-generate order).  To this effect, we
87     keep track (in lowestTime and lowestHost) of the lowest server trying to
88     become a sync site.  We wait for this server unless there is already a sync
89     site (indicated by ServBeacon's parameter being 1).
90 */
91
92 afs_int32 ubik_debugFlag        = 0;            /* print out debugging messages? */
93
94 /* these statics are used by all sites in nominating new sync sites */
95 afs_int32 ubik_lastYesTime = 0; /* time we sent the last *yes* vote */
96 static afs_uint32 lastYesHost = 0xffffffff; /* host to which we sent *yes* vote */
97 /* Next is time sync site began this vote: guarantees sync site until this + SMALLTIME */
98 static afs_int32 lastYesClaim = 0;
99 static int lastYesState = 0;    /* did last site we voted for claim to be sync site? */
100
101 /* used to guarantee that nomination process doesn't loop */
102 static afs_int32 lowestTime = 0;
103 static afs_uint32 lowestHost = 0xffffffff;
104 static afs_int32 syncTime = 0;
105 static afs_int32 syncHost = 0;
106
107 /* used to remember which dbase version is the one at the sync site (for non-sync sites */
108 struct ubik_version ubik_dbVersion;     /* sync site's dbase version */
109 struct ubik_tid ubik_dbTid;             /* sync site's tid, or 0 if none */
110
111 /* decide if we should try to become sync site.  The basic rule is that we
112  * don't run if there is a valid sync site and it ain't us (we have to run if
113  * it is us, in order to keep our votes).  If there is no sync site, then we
114  * want to run if we're the lowest numbered host running, otherwise we defer to
115  * the lowest host.  However, if the lowest host hasn't been heard from for a
116  * while, then we start running again, in case he crashed.
117  *
118  * This function returns true if we should run, and false otherwise.
119  */
120 int uvote_ShouldIRun() {
121     register afs_int32 now;
122     
123     now = FT_ApproxTime();
124     if (BIGTIME + ubik_lastYesTime < now) return 1;    /* no valid guy even trying */
125     if (lastYesState && lastYerHost != ubik_host[0]) return 0; /* other guy is sync site, leave him alone */
126     if (ntohl((afs_uint32) lastYesHost) < ntohl((afs_uint32) ubik_host[0]))
127         return 0;    /* if someone is valid and better than us, don't run */
128     /* otherwise we should run */
129     return 1;
130 }
131
132 /* Return the current synchronization site, if any.  Simple approach: if the
133  * last guy we voted yes for claims to be the sync site, then we we're happy to
134  * use that guy for a sync site until the time his mandate expires.  If the guy
135  * does not claim to be sync site, then, of course, there's none.
136  *
137  * In addition, if we lost the sync, we set urecovery_syncSite to an invalid
138  * value, indicating that we no longer know which version of the dbase is the
139  * one we should have.  We'll get a new one when we next hear from the sync
140  * site.
141  *
142  * This function returns 0 or currently valid sync site.  It can return our own
143  * address, if we're the sync site.
144  */
145 afs_int32 uvote_GetSyncSite() {
146     register afs_int32 now;
147     register afs_int32 code;
148
149     if (!lastYesState) code = 0;
150     else {
151         now = FT_ApproxTime();
152         if (SMALLTIME + lastYesClaim < now) code = 0;    /* last guy timed out */
153         else code = lastYesHost;
154     }
155     return code;
156 }
157
158 /* called by the sync site to handle vote beacons; if aconn is null, this is a
159  * local call; returns 0 or time whe the vote was sent.  It returns 0 if we are
160  * not voting for this sync site, or the time we actually voted yes, if
161  * non-zero.
162  */
163 SVOTE_Beacon(rxcall, astate, astart, avers, atid)
164     register struct rx_call *rxcall;
165     afs_int32 astate;
166     struct ubik_version *avers;
167     struct ubik_tid *atid;
168     afs_int32 astart; 
169 {
170     register afs_int32 otherHost;
171     register afs_int32 now;
172     afs_int32 vote;
173     struct rx_connection *aconn;
174     struct rx_peer *rxp;
175     struct ubik_server *ts;
176     int isClone = 0;
177
178     now = FT_ApproxTime();                      /* close to current time */
179     if (rxcall) {                               /* caller's host */
180         aconn = rx_ConnectionOf(rxcall);
181         rxp = rx_PeerOf(aconn);
182         otherHost = rx_HostOf(rxp);
183
184                 /* get the primary interface address for this host.  */
185                 /* This is the identifier that ubik uses. */
186         otherHost = ubikGetPrimaryInterfaceAddr(otherHost);
187         if ( !otherHost )
188         {
189                 ubik_dprint("Received beacon from unknown host %s\n",
190                                         afs_inet_ntoa(rx_HostOf(rxp)));
191                 return 0; /* I don't know about you: vote no */
192         }
193         for (ts = ubik_servers; ts; ts = ts->next) {
194             if (ts->addr[0] == otherHost) break;
195         }
196         if (!ts) ubik_dprint("Unknown host %x has sent a beacon\n", otherHost);
197         if (ts && ts->isClone) isClone = 1;
198     } else {
199         otherHost = ubik_host[0];                       /* this host */
200         isClone = amIClone;
201     }
202
203     ubik_dprint("Received beacon type %d from host %s\n", astate, 
204                                 afs_inet_ntoa(otherHost));
205
206     /* compute the lowest server we've heard from.  We'll try to only vote for
207        this dude if we don't already have a synchronization site.  Also, don't
208        let a very old lowestHost confusing things forever.  We pick a new
209        lowestHost after BIGTIME seconds to limit the damage if this host
210        actually crashes.  Finally, we also count in this computation: don't
211        pick someone else if we're even better!
212
213        Note that the test below must be <=, not <, so that we keep refreshing
214        lowestTime.  Otherwise it will look like we haven't heard from
215        lowestHost in a while and another host could slip in.  */
216
217
218     /* First compute the lowest host we've heard from, whether we want them
219        for a sync site or not.  If we haven't heard from a site in BIGTIME
220        seconds, we ignore its presence in lowestHost: it may have crashed.
221        Note that we don't ever let anyone appear in our lowestHost if we're
222        lower than them, 'cause we know we're up. */
223     /* But do not consider clones for lowesHost since they never may become
224        sync site */
225     if (!isClone &&
226         (ntohl((afs_uint32) otherHost) <= ntohl((afs_uint32) lowestHost)
227         || lowestTime + BIGTIME < now)) {
228         lowestTime = now;
229         lowestHost = otherHost;
230     }
231     /* why do we need this next check?  Consider the case where each of two
232        servers decides the other is lowestHost.  Each stops sending beacons
233        'cause the other is there.  Not obvious that this process terminates:
234        i.e. each guy could restart procedure and again think other side is
235        lowest.  Need to prove: if one guy in the system is lowest and knows
236        he's lowest, these loops don't occur.  because if someone knows he's
237        lowest, he will send out beacons telling others to vote for him. */
238     if (!amIClone &&
239         (ntohl((afs_uint32) ubik_host) <= ntohl((afs_uint32) lowestHost)
240         || lowestTime + BIGTIME < now)) {
241         lowestTime = now;
242         lowestHost = ubik_host[0];
243     }
244     
245     /* tell if we've heard from a sync site recently (even if we're not voting
246        for this dude yet).  After a while, time the guy out. */
247     if (astate) {   /* this guy is a sync site */
248         syncHost = otherHost;
249         syncTime = now;
250     }
251     else if (syncTime + BIGTIME < now) {
252        if (syncHost) {
253           ubik_dprint("Ubik: Lost contact with sync-site %d.%d.%d.%d (NOT in quorum)\n",
254                       ((syncHost>>24)&0xff), ((syncHost>>16)&0xff),
255                       ((syncHost>> 8)&0xff), (syncHost      &0xff));
256        }
257        syncHost = 0;
258     }
259
260     /* decide how to vote */
261     vote = 0;               /* start off voting no */
262
263     /* if we this guy isn't a sync site, we don't really have to vote for him.
264        We get to apply some heuristics to try to avoid weird oscillation sates
265        in the voting procedure. */
266     if (astate == 0) {
267         /* in here only if this guy doesn't claim to be a sync site */
268
269         /* lowestHost is also trying for our votes, then just say no. */
270         if (ntohl(lowestHost) != ntohl(otherHost)) {
271             return 0;
272         }
273
274         /* someone else *is* a sync site, just say no */
275         if (syncHost && syncHost != otherHost)
276             return 0;
277     } else  /* fast startup if this is the only non-clone */
278     if (lastYesHost == 0xffffffff && otherHost == ubik_host[0]) {
279         int i = 0;
280         for (ts = ubik_servers; ts; ts = ts->next) {
281             if (ts->addr[0] == otherHost) continue;
282             if (!ts->isClone) i++;
283         }
284         if (!i) lastYesHost = otherHost;
285     }
286         
287
288     if (isClone) return 0; /* clone never can become sync site */
289
290     /* Don't promise sync site support to more than one host every BIGTIME
291        seconds.  This is the heart of our invariants in this system. */
292     if (ubik_lastYesTime + BIGTIME < now || otherHost == lastYesHost) {
293         if ((ubik_lastYesTime+BIGTIME < now) || 
294             (otherHost != lastYesHost) ||
295             (lastYesState != astate)) {
296            /* A new vote or a change in the vote or changed quorum */
297            ubik_dprint("Ubik: vote 'yes' for %d.%d.%d.%d %s\n",
298                        ((otherHost>>24)&0xff), ((otherHost>>16)&0xff),
299                        ((otherHost>> 8)&0xff), (otherHost      &0xff),
300                        (astate?"(in quorum)":"(NOT in quorum)"));
301         }
302
303         vote = now;                 /* vote yes */
304         ubik_lastYesTime = now;     /* remember when we voted yes */
305         lastYesClaim = astart;      /* remember for computing when sync site expires */
306         lastYesHost = otherHost;    /* and who for */
307         lastYesState = astate;      /* remember if site is a sync site */
308         ubik_dbVersion = *avers;    /* resync value */
309         ubik_dbTid = *atid;         /* transaction id, if any, of active trans */
310         urecovery_CheckTid(atid);   /* check if current write trans needs aborted */
311     }
312     return vote;
313 }
314
315 /* handle per-server debug command, where 0 is the first server.  Basic network
316    debugging hooks. */
317 SVOTE_SDebug(rxcall, awhich, aparm)
318     struct rx_call *rxcall;
319     afs_int32 awhich;
320     register struct ubik_sdebug *aparm;
321 {
322     afs_int32 code, isClone;
323     code = SVOTE_XSDebug(rxcall, awhich, aparm, &isClone);
324     return code;
325 }
326
327 SVOTE_XSDebug(rxcall, awhich, aparm, isclone)
328     afs_int32 *isclone;
329     struct rx_call *rxcall;
330     afs_int32 awhich;
331     register struct ubik_sdebug *aparm; 
332 {
333     register struct ubik_server *ts;
334     register int i;
335     for(ts=ubik_servers; ts; ts=ts->next) {
336         if (awhich-- == 0) {
337             /* we're done */
338             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
339             for ( i=0; i < UBIK_MAX_INTERFACE_ADDR-1; i++)
340                 aparm->altAddr[i] = ntohl(ts->addr[i+1]);
341             aparm->lastVoteTime = ts->lastVoteTime;
342             aparm->lastBeaconSent = ts->lastBeaconSent;
343             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
344             aparm->lastVote = ts->lastVote;
345             aparm->up = ts->up;
346             aparm->beaconSinceDown = ts->beaconSinceDown;
347             aparm->currentDB = ts->currentDB;
348             *isclone = ts->isClone;
349             return 0;
350         }
351     }
352     return 2;
353 }
354
355 SVOTE_XDebug(rxcall, aparm, isclone)
356     struct rx_call *rxcall;
357     register struct ubik_debug *aparm;
358     afs_int32 *isclone;
359 {
360     afs_int32 code;
361
362     code = SVOTE_Debug(rxcall, aparm);
363     *isclone = amIClone;
364     return code;
365 }
366
367 /* handle basic network debug command.  This is the global state dumper */
368 SVOTE_Debug(rxcall, aparm)
369     struct rx_call *rxcall;
370     register struct ubik_debug *aparm; {
371     int  i;
372     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
373      * integers in host order. */
374     
375     aparm->now = FT_ApproxTime();
376     aparm->lastYesTime = ubik_lastYesTime;
377     aparm->lastYesHost = ntohl(lastYesHost);
378     aparm->lastYesState = lastYesState;
379     aparm->lastYesClaim = lastYesClaim;
380     aparm->lowestHost = ntohl(lowestHost);
381     aparm->lowestTime = lowestTime;
382     aparm->syncHost = ntohl(syncHost);
383     aparm->syncTime = syncTime;
384
385     /* fill in all interface addresses of myself in hostbyte order */
386     for ( i=0; i < UBIK_MAX_INTERFACE_ADDR; i++)
387         aparm->interfaceAddr[i] = ntohl(ubik_host[i]);   
388
389     aparm->amSyncSite = ubik_amSyncSite;
390     ubeacon_Debug(aparm);
391     
392     udisk_Debug(aparm);
393     
394     ulock_Debug(aparm);
395
396     /* Get the recovery state. The label of the database may not have 
397      * been written yet but set the flag so udebug behavior remains.
398      * Defect 9477.
399      */
400     aparm->recoveryState = urecovery_state;
401     if ((urecovery_state & UBIK_RECSYNCSITE) && 
402         (urecovery_state & UBIK_RECFOUNDDB ) &&
403         (urecovery_state & UBIK_RECHAVEDB  ) ) {
404        aparm->recoveryState |= UBIK_RECLABELDB;
405     }
406     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
407     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
408     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
409     aparm->tidCounter = ubik_dbase->tidCounter;
410     
411     if (ubik_currentTrans) {
412         aparm->currentTrans = 1;
413         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
414         else aparm->writeTrans = 0;
415     }
416     else {
417         aparm->currentTrans = 0;
418     }
419
420     aparm->epochTime = ubik_epochTime;
421
422     return 0;
423 }
424
425 SVOTE_SDebugOld(rxcall, awhich, aparm)
426     struct rx_call *rxcall;
427     afs_int32 awhich;
428     register struct ubik_sdebug_old *aparm; {
429     register struct ubik_server *ts;
430     register int i;
431     for(ts=ubik_servers; ts; ts=ts->next) {
432         if (awhich-- == 0) {
433             /* we're done */
434             aparm->addr = ntohl(ts->addr[0]); /* primary interface */
435             aparm->lastVoteTime = ts->lastVoteTime;
436             aparm->lastBeaconSent = ts->lastBeaconSent;
437             bcopy(&ts->version, &aparm->remoteVersion, sizeof(struct ubik_version));
438             aparm->lastVote = ts->lastVote;
439             aparm->up = ts->up;
440             aparm->beaconSinceDown = ts->beaconSinceDown;
441             aparm->currentDB = ts->currentDB;
442             return 0;
443         }
444     }
445     return 2;
446 }
447
448
449 /* handle basic network debug command.  This is the global state dumper */
450 SVOTE_DebugOld(rxcall, aparm)
451     struct rx_call *rxcall;
452     register struct ubik_debug_old *aparm; {
453     int  i;
454     /* fill in the basic debug structure.  Note the the RPC protocol transfers,
455      * integers in host order. */
456     
457     aparm->now = FT_ApproxTime();
458     aparm->lastYesTime = ubik_lastYesTime;
459     aparm->lastYesHost = ntohl(lastYesHost);
460     aparm->lastYesState = lastYesState;
461     aparm->lastYesClaim = lastYesClaim;
462     aparm->lowestHost = ntohl(lowestHost);
463     aparm->lowestTime = lowestTime;
464     aparm->syncHost = ntohl(syncHost);
465     aparm->syncTime = syncTime;
466
467     aparm->amSyncSite = ubik_amSyncSite;
468     ubeacon_Debug(aparm);
469     
470     udisk_Debug(aparm);
471     
472     ulock_Debug(aparm);
473
474     /* Get the recovery state. The label of the database may not have 
475      * been written yet but set the flag so udebug behavior remains.
476      * Defect 9477.
477      */
478     aparm->recoveryState = urecovery_state;
479     if ((urecovery_state & UBIK_RECSYNCSITE) && 
480         (urecovery_state & UBIK_RECFOUNDDB ) &&
481         (urecovery_state & UBIK_RECHAVEDB  ) ) {
482        aparm->recoveryState |= UBIK_RECLABELDB;
483     }
484     bcopy(&ubik_dbVersion, &aparm->syncVersion, sizeof(struct ubik_version));
485     bcopy(&ubik_dbTid, &aparm->syncTid, sizeof(struct ubik_tid));
486     aparm->activeWrite = (ubik_dbase->flags & DBWRITING);
487     aparm->tidCounter = ubik_dbase->tidCounter;
488     
489     if (ubik_currentTrans) {
490         aparm->currentTrans = 1;
491         if (ubik_currentTrans->type == UBIK_WRITETRANS) aparm->writeTrans = 1;
492         else aparm->writeTrans = 0;
493     }
494     else {
495         aparm->currentTrans = 0;
496     }
497
498     aparm->epochTime = ubik_epochTime;
499
500     return 0;
501 }
502
503
504 /* get the sync site; called by remote servers to find where they should go */
505 SVOTE_GetSyncSite(rxcall, ahost)
506     register struct rx_call *rxcall;
507     register afs_int32 *ahost; {
508     register afs_int32 temp;
509
510     temp = uvote_GetSyncSite();
511     *ahost = ntohl(temp);
512     return 0;
513 }
514
515 ubik_dprint(a,b,c,d,e,f,g,h)
516     char *a, *b, *c, *d, *e, *f, *g, *h; {
517     ViceLog(5, (a,b,c,d,e,f,g,h));
518 }
519
520 ubik_print(a,b,c,d,e,f,g,h)
521   char *a, *b, *c, *d, *e, *f, *g, *h;
522 {
523   ViceLog(0, (a,b,c,d,e,f,g,h));
524 }
525
526 /* called once/run to init the vote module */
527 uvote_Init() {
528     /* pretend we just voted for someone else, since we just restarted */
529     ubik_lastYesTime = FT_ApproxTime();
530     return 0;
531 }