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