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