diff --git a/src/config.h b/src/config.h index 41be454..bb95e48 100644 --- a/src/config.h +++ b/src/config.h @@ -1,226 +1,233 @@ /* * Copyright (C) 2011 Jiaju Zhang * Copyright (C) 2013-2014 Philipp Marek * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef _CONFIG_H #define _CONFIG_H #include #include "booth.h" #include "raft.h" #include "transport.h" /** @{ */ /** Definitions for in-RAM data. */ #define MAX_NODES 16 #define TICKET_ALLOC 16 struct ticket_config { /** \name Configuration items. * @{ */ /** Name of ticket. */ boothc_ticket name; /** How many seconds a term lasts (if not refreshed). */ int term_duration; /** Network related timeouts. */ int timeout; /** Retries before giving up. */ int retries; /** If >0, time to wait for a site to get fenced. * The ticket may be acquired after that timespan by * another site. */ int acquire_after; /* TODO: needed? */ /* Program to ask whether it makes sense to * acquire the ticket */ char *ext_verifier; /** Node weights. */ int weight[MAX_NODES]; /** @} */ /** \name Runtime values. * @{ */ /** Current state. */ server_state_e state; /** Next state. Used at startup. */ server_state_e next_state; /** When something has to be done */ struct timeval next_cron; /** Current leader. This is effectively the log[] in Raft. */ struct booth_site *leader; + /** Leader that got lost. */ + struct booth_site *lost_leader; + /** Is the ticket granted? */ int is_granted; /** Timestamp of leadership expiration */ time_t term_expires; /** End of election period */ time_t election_end; struct booth_site *voted_for; /** Who the various sites vote for. * NO_OWNER = no vote yet. */ struct booth_site *votes_for[MAX_NODES]; /* bitmap */ uint64_t votes_received; /** Last voting round that was seen. */ uint32_t current_term; /** Do ticket updates whenever we get enough heartbeats. * But do that only once. * This is reset to 0 whenever we broadcast heartbeat and set * to 1 once enough acks are received. * Increased to 2 when the ticket is commited to the CIB (see * delay_commit). */ uint32_t ticket_updated; /** @} */ /** */ uint32_t commit_index; /** */ uint32_t last_applied; uint32_t next_index[MAX_NODES]; uint32_t match_index[MAX_NODES]; + /* Why did we start the elections? + */ + cmd_reason_t election_reason; + /* if it is potentially dangerous to grant the ticket * immediately, then this is set to some point in time, * usually (now + term_duration + acquire_after) */ time_t delay_commit; /* if we expect some acks, then set this to the id of * the RPC which others will send us; it is cleared once all * replies were received */ uint32_t acks_expected; /* bitmask of servers which sent acks */ uint64_t acks_received; /* timestamp of the request, currently unused */ time_t req_sent_at; /* we need to wait for MY_INDEX from other servers, * hold the ticket processing for a while until they reply */ int start_postpone; /* Do we need to update the copy in the CIB? * Normally, the ticket is written only when it changes via * the UPDATE RPC (for followers) and on expiration update * (for leaders) */ int update_cib; /* don't log warnings unnecessarily */ int expect_more_rejects; /** \name Needed while proposals are being done. * @{ */ /** Whom to vote for the next time. * Needed to push a ticket to someone else. */ #if 0 /** Bitmap of sites that acknowledge that state. */ uint64_t proposal_acknowledges; /** When an incompletely acknowledged proposal gets done. * If all peers agree, that happens sooner. * See switch_state_to(). */ struct timeval proposal_switch; /** Timestamp of proposal expiration. */ time_t proposal_expires; #endif /** Number of send retries left. * Used on the new owner. * Starts at 0, counts up. */ int retry_number; /** @} */ }; struct booth_config { char name[BOOTH_NAME_LEN]; transport_layer_t proto; uint16_t port; /** Stores the OR of sites bitmasks. */ uint64_t sites_bits; /** Stores the OR of all members' bitmasks. */ uint64_t all_bits; char site_user[BOOTH_NAME_LEN]; char site_group[BOOTH_NAME_LEN]; char arb_user[BOOTH_NAME_LEN]; char arb_group[BOOTH_NAME_LEN]; uid_t uid; gid_t gid; int site_count; struct booth_site site[MAX_NODES]; int ticket_count; int ticket_allocated; struct ticket_config *ticket; }; extern struct booth_config *booth_conf; int read_config(const char *path, int type); int check_config(int type); int find_site_by_name(unsigned char *site, struct booth_site **node, int any_type); int find_site_by_id(uint32_t site_id, struct booth_site **node); const char *type_to_string(int type); #include #define R(tk_) do { if (ANYDEBUG) printf("## %12s:%3d state %s, %d:%d, " \ "leader %s, exp %s", __FILE__, __LINE__, \ state_to_string(tk_->state), tk_->current_term, \ tk_->commit_index, site_string(tk_->leader), ctime(&tk_->term_expires)); } while(0) #endif /* _CONFIG_H */ diff --git a/src/raft.c b/src/raft.c index f9f2da7..56312f6 100644 --- a/src/raft.c +++ b/src/raft.c @@ -1,921 +1,931 @@ /* * Copyright (C) 2014 Philipp Marek * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include #include #include #include #include #include #include "booth.h" #include "transport.h" #include "inline-fn.h" #include "config.h" #include "raft.h" #include "ticket.h" #include "log.h" inline static void clear_election(struct ticket_config *tk) { int i; struct booth_site *site; tk_log_debug("clear election"); tk->votes_received = 0; foreach_node(i, site) tk->votes_for[site->index] = NULL; } inline static void record_vote(struct ticket_config *tk, struct booth_site *who, struct booth_site *vote) { tk_log_debug("site %s votes for %s", site_string(who), site_string(vote)); if (!tk->votes_for[who->index]) { tk->votes_for[who->index] = vote; tk->votes_received |= who->bitmask; } else { if (tk->votes_for[who->index] != vote) tk_log_warn("%s voted previously " "for %s and now wants to vote for %s (ignored)", site_string(who), site_string(tk->votes_for[who->index]), site_string(vote)); } } static int cmp_msg_ticket(struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg) { if (tk->current_term != ntohl(msg->ticket.term)) { return tk->current_term - ntohl(msg->ticket.term); } /* compare commit_index only from the leader */ if (sender == leader) { return tk->commit_index - ntohl(msg->ticket.leader_commit); } return 0; } static void update_term_from_msg(struct ticket_config *tk, struct boothc_ticket_msg *msg) { uint32_t i; i = ntohl(msg->ticket.term); /* if we failed to start the election, then accept the term * from the leader * */ if (tk->state == ST_CANDIDATE) { tk->current_term = i; } else { tk->current_term = max(i, tk->current_term); } /* § 5.3 */ i = ntohl(msg->ticket.leader_commit); tk->commit_index = max(i, tk->commit_index); } static void update_ticket_from_msg(struct ticket_config *tk, struct boothc_ticket_msg *msg) { int duration; duration = tk->term_duration; if (msg) duration = min(duration, ntohl(msg->ticket.term_valid_for)); tk->term_expires = time(NULL) + duration; if (msg) { update_term_from_msg(tk, msg); } } static void copy_ticket_from_msg(struct ticket_config *tk, struct boothc_ticket_msg *msg) { tk->term_expires = time(NULL) + ntohl(msg->ticket.term_valid_for); tk->current_term = ntohl(msg->ticket.term); tk->commit_index = ntohl(msg->ticket.leader_commit); } static void become_follower(struct ticket_config *tk, struct boothc_ticket_msg *msg) { copy_ticket_from_msg(tk, msg); tk->state = ST_FOLLOWER; tk->delay_commit = 0; /* if we're following and the ticket was granted here * then commit to CIB right away (we're probably restarting) */ if (tk->is_granted) { disown_ticket(tk); ticket_write(tk); } } static void won_elections(struct ticket_config *tk) { tk->leader = local; tk->state = ST_LEADER; tk->term_expires = time(NULL) + tk->term_duration; tk->election_end = 0; tk->voted_for = NULL; tk->commit_index++; send_heartbeat(tk); ticket_activate_timeout(tk); } static int is_tie(struct ticket_config *tk) { int i; struct booth_site *v; int count[MAX_NODES] = { 0, }; int max_votes = 0, max_cnt = 0; for(i=0; isite_count; i++) { v = tk->votes_for[i]; if (!v) continue; count[v->index]++; max_votes = max(max_votes, count[v->index]); } for(i=0; isite_count; i++) { if (count[i] == max_votes) max_cnt++; } return max_cnt > 1; } static struct booth_site *majority_votes(struct ticket_config *tk) { int i, n; struct booth_site *v; int count[MAX_NODES] = { 0, }; for(i=0; isite_count; i++) { v = tk->votes_for[i]; if (!v) continue; n = v->index; count[n]++; tk_log_debug("Majority: %d %s wants %d %s => %d", i, site_string(&booth_conf->site[i]), n, site_string(v), count[n]); if (count[n]*2 <= booth_conf->site_count) continue; tk_log_debug("Majority reached: %d of %d for %s", count[n], booth_conf->site_count, site_string(v)); return v; } return NULL; } void elections_end(struct ticket_config *tk) { time_t now; struct booth_site *new_leader; now = time(NULL); if (now > tk->election_end) { /* This is previous election timed out */ tk_log_info("election timed out"); } new_leader = majority_votes(tk); if (new_leader == local) { tk_log_info("granted successfully here"); won_elections(tk); } else if (new_leader) { tk_log_info("ticket granted at %s", site_string(new_leader)); become_follower(tk, NULL); set_ticket_wakeup(tk); } else { tk_log_info("nobody won elections, new elections"); new_election(tk, NULL, is_tie(tk), OR_AGAIN); } } static int newer_term(struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg, int in_election) { uint32_t term; /* it may happen that we hear about our newer term */ if (leader == local) return 0; term = ntohl(msg->ticket.term); /* §5.1 */ if (term > tk->current_term) { tk->state = ST_FOLLOWER; if (!in_election) { tk->leader = leader; tk_log_info("from %s: higher term %d vs. %d, following %s", site_string(sender), term, tk->current_term, ticket_leader_string(tk)); } else { tk->leader = no_leader; tk_log_debug("from %s: higher term %d vs. %d (election)", site_string(sender), term, tk->current_term); } tk->current_term = term; return 1; } return 0; } static int term_too_low(struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg) { uint32_t term; term = ntohl(msg->ticket.term); /* §5.1 */ if (term < tk->current_term) { tk_log_info("sending reject to %s, its term too low " "(%d vs. %d)", site_string(sender), term, tk->current_term ); send_reject(sender, tk, RLT_TERM_OUTDATED); return 1; } return 0; } /* For follower. */ static int answer_HEARTBEAT ( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t term; struct boothc_ticket_msg omsg; term = ntohl(msg->ticket.term); tk_log_debug("leader: %s, have %s; term %d vs %d", site_string(leader), ticket_leader_string(tk), term, tk->current_term); /* got heartbeat, no rejects expected anymore */ tk->expect_more_rejects = 0; /* if we're candidate, it may be that we got a heartbeat from * a legitimate leader, so don't ignore a lower term */ if (tk->state != ST_CANDIDATE && term < tk->current_term) { tk_log_info("ignoring lower term %d vs. %d, from %s", term, tk->current_term, ticket_leader_string(tk)); return 0; } /* Needed? */ newer_term(tk, sender, leader, msg, 0); become_follower(tk, msg); /* Racy??? */ assert(sender == leader || !leader); tk->leader = leader; /* Ack the heartbeat (we comply). */ init_ticket_msg(&omsg, OP_HEARTBEAT, RLT_SUCCESS, 0, tk); return booth_udp_send(sender, &omsg, sizeof(omsg)); } static int process_UPDATE ( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t term; term = ntohl(msg->ticket.term); tk_log_debug("leader: %s, have %s; term %d vs %d", site_string(leader), ticket_leader_string(tk), term, tk->current_term); /* No reject. (?) */ if (term < tk->current_term) { tk_log_info("ignoring lower term %d vs. %d, from %s", term, tk->current_term, ticket_leader_string(tk)); return 0; } update_ticket_from_msg(tk, msg); ticket_write(tk); /* run ticket_cron if the ticket expires */ set_ticket_wakeup(tk); return 0; } static int process_REVOKE ( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { if (tk->leader != sender) { tk_log_error("%s wants to revoke ticket, " "but it is not granted there (ignoring)", site_string(sender)); return 1; } else if (tk->state != ST_FOLLOWER) { tk_log_error("unexpected ticket revoke from %s " "(in state %s) (ignoring)", site_string(sender), state_to_string(tk->state)); return 1; } else { tk_log_info("%s revokes ticket", site_string(tk->leader)); reset_ticket(tk); tk->leader = no_leader; ticket_write(tk); } return 0; } /* For leader. */ static int process_HEARTBEAT( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t term; term = ntohl(msg->ticket.term); if (newer_term(tk, sender, leader, msg, 0)) { /* unexpected higher term */ tk_log_warn("got higher term from %s (%d vs. %d)", site_string(sender), term, tk->current_term); return 0; } /* Don't send a reject. */ if (term < tk->current_term) { /* Doesn't know what he's talking about - perhaps * doesn't receive our packets? */ tk_log_warn("unexpected term " "from %s (%d vs. %d) (ignoring)", site_string(sender), term, tk->current_term); return 0; } if (term == tk->current_term && leader == tk->leader) { if (majority_of_bits(tk, tk->acks_received)) { /* OK, at least half of the nodes are reachable; * Update the ticket and send update messages out */ return leader_update_ticket(tk); } } return 0; } static int process_VOTE_FOR( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { if (term_too_low(tk, sender, leader, msg)) return 0; if (newer_term(tk, sender, leader, msg, 0)) { clear_election(tk); } /* leader wants to step down? */ if (leader == no_leader && sender == tk->leader && (tk->state == ST_FOLLOWER || tk->state == ST_CANDIDATE)) { tk_log_info("%s wants to give the ticket away", site_string(tk->leader)); return new_round(tk, OR_STEPDOWN); } record_vote(tk, sender, leader); if (tk->state != ST_CANDIDATE) { /* lost candidate status, somebody rejected our proposal */ return 0; } /* only if all voted can we take the ticket now, otherwise * wait for timeout in ticket_cron */ if (!tk->acks_expected) { /* §5.2 */ elections_end(tk); } return 0; } static int process_REJECTED( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t rv; rv = ntohl(msg->header.result); if (tk->state == ST_CANDIDATE && leader == local) { /* the sender has us as the leader (!) * the elections will time out, then we can try again */ tk_log_warn("ticket was granted to us " "(and we didn't know)"); tk->expect_more_rejects = 1; return 0; } if (tk->state == ST_CANDIDATE && rv == RLT_TERM_OUTDATED) { tk_log_warn("ticket outdated (term %d), granted to %s", ntohl(msg->ticket.term), site_string(leader) ); tk->leader = leader; tk->expect_more_rejects = 1; become_follower(tk, msg); return 0; } if (tk->state == ST_CANDIDATE && rv == RLT_TERM_STILL_VALID) { - tk_log_warn("ticket was granted to %s " - "(and we didn't know)", - site_string(leader)); + if (tk->lost_leader == leader) { + if (tk->election_reason == OR_TKT_LOST) { + tk_log_warn("%s still has the ticket valid, " + "we'll backup a bit", + site_string(sender)); + } else { + tk_log_warn("%s unexpecetedly rejects elections", + site_string(sender)); + } + } else { + tk_log_warn("ticket was granted to %s " + "(and we didn't know)", + site_string(leader)); + } tk->leader = leader; become_follower(tk, msg); tk->expect_more_rejects = 1; return 0; } if (tk->state == ST_CANDIDATE && rv == RLT_YOU_OUTDATED) { tk->leader = leader; tk->expect_more_rejects = 1; if (leader && leader != no_leader) { tk_log_warn("our ticket is outdated, granted to %s", site_string(leader)); become_follower(tk, msg); } else { tk_log_warn("our ticket is outdated and revoked"); update_ticket_from_msg(tk, msg); tk->state = ST_INIT; } return 0; } if (!tk->expect_more_rejects) { tk_log_warn("from %s: in state %s, got %s (unexpected reject)", site_string(sender), state_to_string(tk->state), state_to_string(rv)); } return 0; } static int ticket_seems_ok(struct ticket_config *tk) { int time_left; time_left = term_time_left(tk); if (!time_left) return 0; /* quite sure */ if (tk->state == ST_CANDIDATE) return 0; /* in state of flux */ if (tk->state == ST_LEADER) return 1; /* quite sure */ if (tk->state == ST_FOLLOWER && time_left >= tk->term_duration/3) return 1; /* almost quite sure */ return 0; } static int test_reason( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { int reason; reason = ntohl(msg->header.reason); if (reason == OR_TKT_LOST) { if (tk->state == ST_INIT && tk->leader == no_leader) { tk_log_warn("%s claims that the ticket is lost, " "but it's in %s state (reject sent)", site_string(sender), state_to_string(tk->state) ); return RLT_YOU_OUTDATED; } if (ticket_seems_ok(tk)) { tk_log_warn("%s claims that the ticket is lost, " "but it is ok here (reject sent)", site_string(sender)); return RLT_TERM_STILL_VALID; } } return 0; } /* §5.2 */ static int answer_REQ_VOTE( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t term; int valid; struct boothc_ticket_msg omsg; cmd_result_t inappr_reason; inappr_reason = test_reason(tk, sender, leader, msg); if (inappr_reason) return send_reject(sender, tk, inappr_reason); term = ntohl(msg->ticket.term); /* Important: Ignore duplicated packets! */ valid = term_time_left(tk); if (valid && term == tk->current_term && sender == tk->leader) { tk_log_debug("Duplicate OP_VOTE_FOR ignored."); return 0; } /* allow the leader to start new elections on valid tickets */ if (sender != tk->leader && valid) { tk_log_warn("election rejected, term still valid for %ds", valid); return send_reject(sender, tk, RLT_TERM_STILL_VALID); } if (term_too_low(tk, sender, leader, msg)) return 0; /* if it's a newer term or ... */ if (newer_term(tk, sender, leader, msg, 1)) { clear_election(tk); goto vote_for_sender; } /* ... we didn't vote yet, then vote for the sender */ /* §5.2, §5.4 */ if (!tk->voted_for) { vote_for_sender: tk->voted_for = sender; record_vote(tk, sender, leader); } init_ticket_msg(&omsg, OP_VOTE_FOR, RLT_SUCCESS, 0, tk); omsg.ticket.leader = htonl(get_node_id(tk->voted_for)); return booth_udp_send(sender, &omsg, sizeof(omsg)); } int new_election(struct ticket_config *tk, struct booth_site *preference, int update_term, cmd_reason_t reason) { struct booth_site *new_leader; time_t now; - static cmd_reason_t last_reason; time(&now); tk_log_debug("start new election?, now=%" PRIi64 ", end %" PRIi64, (int64_t)now, (int64_t)(tk->election_end)); if (now <= tk->election_end) return 0; /* §5.2 */ /* If there was _no_ answer, don't keep incrementing the term number * indefinitely. If there was no peer, there'll probably be no one * listening now either. However, we don't know if we were * invoked due to a timeout (caller does). */ if (update_term) tk->current_term++; tk->term_expires = 0; tk->election_end = now + tk->timeout; tk_log_info("starting new election (term=%d)", tk->current_term); clear_election(tk); if(preference) new_leader = preference; else new_leader = (local->type == SITE) ? local : NULL; record_vote(tk, local, new_leader); tk->voted_for = new_leader; tk->state = ST_CANDIDATE; /* some callers may want just to repeat on timeout */ if (reason == OR_AGAIN) { - reason = last_reason; + reason = tk->election_reason; } else { - last_reason = reason; + tk->election_reason = reason; } expect_replies(tk, OP_VOTE_FOR); ticket_broadcast(tk, OP_REQ_VOTE, RLT_SUCCESS, reason); ticket_activate_timeout(tk); return 0; } int new_round(struct ticket_config *tk, cmd_reason_t reason) { int rv = 0; struct timespec delay; if (local->type == ARBITRATOR) { /* we cannot really do anything, but keep the copy for * somebody else who perhaps can */ return 0; } disown_ticket(tk); ticket_write(tk); /* New vote round; §5.2 */ /* delay the next election start for up to 200ms */ delay.tv_sec = 0; delay.tv_nsec = 1000000L * (long)cl_rand_from_interval(0, 200); nanosleep(&delay, NULL); rv = new_election(tk, NULL, 1, reason); return rv; } /* we were a leader and somebody says that they have a more up * to date ticket * there was probably connectivity loss * tricky */ static int leader_handle_newer_ticket( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { update_term_from_msg(tk, msg); if (leader != no_leader && leader && leader != local) { /* eek, two leaders, split brain */ /* normally shouldn't happen; run election */ tk_log_error("from %s: ticket granted to %s! (revoking locally)", site_string(sender), site_string(leader) ); } else if (term_time_left(tk)) { /* eek, two leaders, split brain */ /* normally shouldn't happen; run election */ tk_log_error("from %s: ticket granted to %s! (revoking locally)", site_string(sender), site_string(leader) ); } tk->next_state = ST_LEADER; return 0; } /* reply to STATUS */ static int process_MY_INDEX ( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { int i; int expired; expired = !msg->ticket.term_valid_for; i = cmp_msg_ticket(tk, sender, leader, msg); if (i > 0) { /* let them know about our newer ticket */ send_msg(OP_MY_INDEX, tk, sender); if (tk->state == ST_LEADER) { tk_log_info("sending ticket update to %s", site_string(sender)); return send_msg(OP_UPDATE, tk, sender); } } /* we have a newer or equal ticket and theirs is expired, * nothing more to do here */ if (i >= 0 && expired) { return 0; } if (tk->state == ST_LEADER) { /* we're the leader, thread carefully */ if (expired) { /* if their ticket is expired, * nothing more to do */ return 0; } if (i < 0) { /* they have a newer ticket, trouble if we're already leader * for it */ tk_log_warn("from %s: more up to date ticket at %s", site_string(sender), site_string(leader) ); return leader_handle_newer_ticket(tk, sender, leader, msg); } else { /* we have the ticket and we don't care */ return 0; } } /* their ticket is either newer or not expired, don't * ignore it */ update_ticket_from_msg(tk, msg); tk->leader = leader; update_ticket_state(tk, sender); set_ticket_wakeup(tk); return 0; } int raft_answer( struct ticket_config *tk, struct booth_site *from, struct booth_site *leader, struct boothc_ticket_msg *msg ) { int cmd; int rv; rv = 0; cmd = ntohl(msg->header.cmd); tk_log_debug("got message %s from %s", state_to_string(cmd), site_string(from)); switch (cmd) { case OP_REQ_VOTE: rv = answer_REQ_VOTE(tk, from, leader, msg); break; case OP_VOTE_FOR: rv = process_VOTE_FOR(tk, from, leader, msg); break; case OP_HEARTBEAT: if (tk->leader == local && tk->state == ST_LEADER) rv = process_HEARTBEAT(tk, from, leader, msg); else if (tk->leader != local && (tk->state == ST_INIT ||tk->state == ST_FOLLOWER || tk->state == ST_CANDIDATE)) rv = answer_HEARTBEAT(tk, from, leader, msg); else { tk_log_warn("unexpected message %s, from %s", state_to_string(cmd), site_string(from)); rv = -EINVAL; } break; case OP_UPDATE: if (tk->leader != local && tk->state == ST_FOLLOWER) { rv = process_UPDATE(tk, from, leader, msg); } else { tk_log_warn("unexpected message %s, from %s", state_to_string(cmd), site_string(from)); rv = -EINVAL; } break; case OP_REJECTED: rv = process_REJECTED(tk, from, leader, msg); break; case OP_REVOKE: rv = process_REVOKE(tk, from, leader, msg); break; case OP_MY_INDEX: rv = process_MY_INDEX(tk, from, leader, msg); break; case OP_STATUS: rv = send_msg(OP_MY_INDEX, tk, from); break; default: tk_log_error("unknown message %s, from %s", state_to_string(cmd), site_string(from)); rv = -EINVAL; } return rv; } diff --git a/src/ticket.c b/src/ticket.c index 7f483e1..4fc0f68 100644 --- a/src/ticket.c +++ b/src/ticket.c @@ -1,933 +1,934 @@ /* * Copyright (C) 2011 Jiaju Zhang * Copyright (C) 2013-2014 Philipp Marek * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This software is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #include #include #include #include #include #include #include #include #include "ticket.h" #include "config.h" #include "pacemaker.h" #include "inline-fn.h" #include "log.h" #include "booth.h" #include "raft.h" #include "handler.h" #define TK_LINE 256 /* Untrusted input, must fit (incl. \0) in a buffer of max chars. */ int check_max_len_valid(const char *s, int max) { int i; for(i=0; iticket_count; i++) { if (!strcmp(booth_conf->ticket[i].name, ticket)) { if (found) *found = booth_conf->ticket + i; return 1; } } return 0; } int check_ticket(char *ticket, struct ticket_config **found) { if (found) *found = NULL; if (!booth_conf) return 0; if (!check_max_len_valid(ticket, sizeof(booth_conf->ticket[0].name))) return 0; return find_ticket_by_name(ticket, found); } int check_site(char *site, int *is_local) { struct booth_site *node; if (!check_max_len_valid(site, sizeof(node->addr_string))) return 0; if (find_site_by_name(site, &node, 0)) { *is_local = node->local; return 1; } return 0; } int ticket_write(struct ticket_config *tk) { if (local->type != SITE) return -EINVAL; if (tk->leader == local) { pcmk_handler.grant_ticket(tk); } else { pcmk_handler.revoke_ticket(tk); } tk->update_cib = 0; return 0; } /* Ask an external program whether getting the ticket * makes sense. * Eg. if the services have a failcount of INFINITY, * we can't serve here anyway. */ int test_external_prog(struct ticket_config *tk, int start_election) { int rv; rv = run_handler(tk, tk->ext_verifier, 1); if (rv) { tk_log_warn("we are not allowed to acquire ticket"); /* Give it to somebody else. * Just send a VOTE_FOR message, so the * others can start elections. */ if (leader_and_valid(tk)) { disown_ticket(tk); if (start_election) { ticket_broadcast(tk, OP_VOTE_FOR, RLT_SUCCESS, OR_LOCAL_FAIL); } } } return rv; } /* Try to acquire a ticket * Could be manual grant or after ticket loss */ int acquire_ticket(struct ticket_config *tk, cmd_reason_t reason) { if (test_external_prog(tk, 0)) return RLT_EXT_FAILED; return new_election(tk, local, 1, reason); } /** Try to get the ticket for the local site. * */ int do_grant_ticket(struct ticket_config *tk, int options) { int rv; tk_log_info("granting ticket"); if (tk->leader == local) return RLT_SUCCESS; if (is_owned(tk)) return RLT_OVERGRANT; tk->delay_commit = time(NULL) + tk->term_duration + tk->acquire_after; if (options & OPT_IMMEDIATE) { tk_log_warn("granting ticket immediately! If there are " "unreachable sites, _hope_ you are sure that they don't " "have the ticket!"); tk->delay_commit = 0; } rv = acquire_ticket(tk, OR_ADMIN); if (rv) tk->delay_commit = 0; return rv; } /** Ticket revoke. * Only to be started from the leader. */ int do_revoke_ticket(struct ticket_config *tk) { tk_log_info("revoking ticket"); reset_ticket(tk); tk->leader = no_leader; ticket_write(tk); return ticket_broadcast(tk, OP_REVOKE, RLT_SUCCESS, OR_ADMIN); } int list_ticket(char **pdata, unsigned int *len) { struct ticket_config *tk; char timeout_str[64]; char pending_str[64]; char *data, *cp; int i, alloc; *pdata = NULL; *len = 0; alloc = 256 + booth_conf->ticket_count * (BOOTH_NAME_LEN * 2 + 128); data = malloc(alloc); if (!data) return -ENOMEM; cp = data; foreach_ticket(i, tk) { if (tk->term_expires != 0) strftime(timeout_str, sizeof(timeout_str), "%F %T", localtime(&tk->term_expires)); else strcpy(timeout_str, "INF"); if (tk->leader == local && tk->delay_commit > time(NULL)) { strcpy(pending_str, " (commit pending until "); strftime(pending_str + strlen(" (commit pending until "), sizeof(pending_str) - strlen(" (commit pending until ") - 1, "%F %T", localtime(&tk->delay_commit)); strcat(pending_str, ")"); } else *pending_str = '\0'; cp += snprintf(cp, alloc - (cp - data), "ticket: %s, leader: %s", tk->name, ticket_leader_string(tk)); if (is_owned(tk)) { cp += snprintf(cp, alloc - (cp - data), ", expires: %s, commit: %d%s\n", timeout_str, tk->commit_index, pending_str); } else { cp += snprintf(cp, alloc - (cp - data), "\n"); } if (alloc - (cp - data) <= 0) return -ENOMEM; } *pdata = data; *len = cp - data; return 0; } void reset_ticket(struct ticket_config *tk) { disown_ticket(tk); tk->state = ST_INIT; tk->voted_for = NULL; } static void reacquire_ticket(struct ticket_config *tk) { int valid; const char *where_granted = "\0"; char buff[64]; valid = (tk->term_expires >= time(NULL)); if (tk->is_granted || tk->leader == local) { where_granted = "granted here"; } else { snprintf(buff, sizeof(buff), "granted to %s", site_string(tk->leader)); where_granted = buff; } if (!valid) { tk_log_warn("%s, but not valid " "anymore (will try to reacquire)", where_granted); } if (tk->is_granted && tk->leader != local) { if (tk->leader && tk->leader != no_leader) { tk_log_error("granted here, but also %s, " "that's really too bad (will try to reacquire)", where_granted); } else { tk_log_warn("granted here, but we're " "not recorded as the grantee (will try to reacquire)"); } } /* try to acquire the * ticket through new elections */ acquire_ticket(tk, OR_REACQUIRE); } void update_ticket_state(struct ticket_config *tk, struct booth_site *sender) { if (tk->leader == local || tk->is_granted) { /* message from a live leader with valid ticket? */ if (sender == tk->leader && term_time_left(tk)) { tk_log_info("ticket was granted here, " "but it's live at %s (revoking here)", site_string(sender)); ticket_write(tk); tk->state = ST_FOLLOWER; tk->next_state = ST_FOLLOWER; } else { tk->next_state = ST_LEADER; } } else { if (!tk->leader || tk->leader == no_leader) { if (sender) tk_log_info("ticket is not granted"); else tk_log_info("ticket is not granted (from CIB)"); tk->state = ST_INIT; } else { if (sender) tk_log_info("ticket granted to %s (says %s)", site_string(tk->leader), site_string(sender)); else tk_log_info("ticket granted to %s (from CIB)", site_string(tk->leader)); tk->state = ST_FOLLOWER; /* just make sure that we check the ticket soon */ tk->next_state = ST_FOLLOWER; } } } int setup_ticket(void) { struct ticket_config *tk; int i; foreach_ticket(i, tk) { reset_ticket(tk); if (local->type == SITE) { if (!pcmk_handler.load_ticket(tk)) { update_ticket_state(tk, NULL); } tk->update_cib = 1; } tk_log_info("broadcasting state query"); /* wait until all send their status (or the first * timeout) */ tk->start_postpone = 1; expect_replies(tk, OP_MY_INDEX); ticket_broadcast(tk, OP_STATUS, RLT_SUCCESS, 0); } return 0; } int ticket_answer_list(int fd, struct boothc_ticket_msg *msg) { char *data; int olen, rv; struct boothc_header hdr; rv = list_ticket(&data, &olen); if (rv < 0) return rv; init_header(&hdr, CMR_LIST, 0, RLT_SUCCESS, 0, sizeof(hdr) + olen); return send_header_plus(fd, &hdr, data, olen); } int ticket_answer_grant(int fd, struct boothc_ticket_msg *msg) { int rv; struct ticket_config *tk; if (!check_ticket(msg->ticket.id, &tk)) { log_warn("client asked to grant unknown ticket %s", msg->ticket.id); rv = RLT_INVALID_ARG; goto reply; } if (is_owned(tk)) { log_warn("client wants to grant an (already granted!) ticket %s", msg->ticket.id); rv = RLT_OVERGRANT; goto reply; } rv = do_grant_ticket(tk, ntohl(msg->header.options)); reply: init_header(&msg->header, CMR_GRANT, 0, rv ?: RLT_ASYNC, 0, sizeof(*msg)); return send_ticket_msg(fd, msg); } int ticket_answer_revoke(int fd, struct boothc_ticket_msg *msg) { int rv; struct ticket_config *tk; if (!check_ticket(msg->ticket.id, &tk)) { log_warn("client wants to revoke an unknown ticket %s", msg->ticket.id); rv = RLT_INVALID_ARG; goto reply; } if (!is_owned(tk)) { log_info("client wants to revoke a free ticket %s", msg->ticket.id); rv = RLT_TICKET_IDLE; goto reply; } if (tk->leader != local) { log_info("the ticket %s is not granted here, " "redirect to %s", msg->ticket.id, ticket_leader_string(tk)); rv = RLT_REDIRECT; goto reply; } rv = do_revoke_ticket(tk); if (rv == 0) rv = RLT_ASYNC; reply: init_ticket_msg(msg, CMR_REVOKE, rv, 0, tk); return send_ticket_msg(fd, msg); } int ticket_broadcast(struct ticket_config *tk, cmd_request_t cmd, cmd_result_t res, cmd_reason_t reason) { struct boothc_ticket_msg msg; init_ticket_msg(&msg, cmd, res, reason, tk); tk_log_debug("broadcasting '%s' (term=%d, valid=%d)", state_to_string(cmd), ntohl(msg.ticket.term), ntohl(msg.ticket.term_valid_for)); return transport()->broadcast(&msg, sizeof(msg)); } /* is it safe to commit the grant? * if we didn't hear from all sites on the initial grant, we may * need to delay the commit * * TODO: investigate possibility to devise from history whether a * missing site could be holding a ticket or not */ static int ticket_dangerous(struct ticket_config *tk) { if (!tk->delay_commit) return 0; if (tk->delay_commit <= time(NULL) || all_sites_replied(tk)) { tk_log_debug("ticket delay commit expired"); tk->delay_commit = 0; return 0; } else { tk_log_debug("delay ticket commit for %ds", (int)(tk->delay_commit - time(NULL))); } return 1; } /* update the ticket on the leader, write it to the CIB, and send out the update message to others with the new expiry time */ int leader_update_ticket(struct ticket_config *tk) { struct boothc_ticket_msg msg; int rv = 0; if (tk->ticket_updated >= 2) return 0; if (tk->ticket_updated < 1) { tk->ticket_updated = 1; tk->term_expires = time(NULL) + tk->term_duration; tk_log_debug("broadcasting ticket update"); init_ticket_msg(&msg, OP_UPDATE, RLT_SUCCESS, 0, tk); rv = transport()->broadcast(&msg, sizeof(msg)); } if (tk->ticket_updated < 2) { if (!ticket_dangerous(tk)) { tk->ticket_updated = 2; ticket_write(tk); } else { /* log just once, on the first retry */ if (tk->retry_number == 1) tk_log_info("delaying ticket commit to CIB for %ds " "(or all sites are reached)", (int)(tk->delay_commit - time(NULL))); } } return rv; } static void log_lost_servers(struct ticket_config *tk) { struct booth_site *n; int i; if (tk->retry_number > 1) /* log those that we couldn't reach, but do * that only on the first retry */ return; for (i = 0; i < booth_conf->site_count; i++) { n = booth_conf->site + i; if (!(tk->acks_received & n->bitmask)) { tk_log_warn("%s %s didn't acknowledge our request, " "will retry %d times", (n->type == ARBITRATOR ? "arbitrator" : "site"), site_string(n), tk->retries); } } } static void resend_msg(struct ticket_config *tk) { struct booth_site *n; int i; if (!(tk->acks_received ^ local->bitmask)) { ticket_broadcast(tk, tk->acks_expected, RLT_SUCCESS, 0); } else { for (i = 0; i < booth_conf->site_count; i++) { n = booth_conf->site + i; if (!(tk->acks_received & n->bitmask)) { tk_log_debug("resending %s to %s", state_to_string(tk->acks_expected), site_string(n) ); send_msg(tk->acks_expected, tk, n); } } } } static void handle_resends(struct ticket_config *tk) { int ack_cnt; if (++tk->retry_number > tk->retries) { tk_log_debug("giving up on sending retries"); no_resends(tk); set_ticket_wakeup(tk); return; } if (!majority_of_bits(tk, tk->acks_received)) { ack_cnt = count_bits(tk->acks_received) - 1; if (!ack_cnt) { tk_log_warn("no answers to heartbeat (try #%d), " "we are alone", tk->retry_number); } else { tk_log_warn("not enough answers to heartbeat (try #%d): " "only got %d answers", tk->retry_number, ack_cnt); } } else { log_lost_servers(tk); /* we have the majority, update the ticket, at * least the local copy if we're still not * allowed to commit */ leader_update_ticket(tk); } resend_msg(tk); ticket_activate_timeout(tk); } int postpone_ticket_processing(struct ticket_config *tk) { extern time_t start_time; return tk->start_postpone && ((time(NULL) - start_time) < tk->timeout); } static void ticket_cron(struct ticket_config *tk) { time_t now; now = time(NULL); /* don't process the tickets too early */ if (postpone_ticket_processing(tk)) { tk_log_debug("ticket processing postponed (start_postpone=%d)", tk->start_postpone); /* but run again soon */ ticket_activate_timeout(tk); return; } if (tk->acks_expected == OP_MY_INDEX) { no_resends(tk); } if (tk->next_state) { if (tk->next_state == ST_LEADER) { if (tk->state == ST_LEADER) { new_round(tk, OR_SPLIT); } else { reacquire_ticket(tk); } } tk->next_state = 0; tk->start_postpone = 0; goto out; } /* Has an owner, has an expiry date, and expiry date in the past? * Losing the ticket must happen in _every_ state. */ if (tk->term_expires && is_owned(tk) && now >= tk->term_expires) { if (tk->leader != local) { tk_log_warn("lost at %s", site_string(tk->leader)); } else { tk_log_warn("lost majority (revoking locally)"); } + tk->lost_leader = tk->leader; tk->next_state = 0; /* Couldn't renew in time - ticket lost. */ new_round(tk, OR_TKT_LOST); return; } switch(tk->state) { case ST_INIT: /* init state, nothing to do */ break; case ST_FOLLOWER: /* nothing here either, ticket loss is caught earlier * */ break; case ST_CANDIDATE: /* §5.2 */ elections_end(tk); break; case ST_LEADER: /* timeout or ticket renewal? */ if (tk->acks_expected) { handle_resends(tk); } else { /* this is ticket renewal, run local test */ if (!test_external_prog(tk, 1)) { send_heartbeat(tk); ticket_activate_timeout(tk); } } break; default: break; } out: if (tk->update_cib) ticket_write(tk); } void process_tickets(void) { struct ticket_config *tk; int i; struct timeval now, last_cron; float sec_until; gettimeofday(&now, NULL); foreach_ticket(i, tk) { sec_until = timeval_to_float(tk->next_cron) - timeval_to_float(now); if (0) tk_log_debug("next cron %" PRIx64 ".%03d, " "now %" PRIx64 "%03d, in %f", (uint64_t)tk->next_cron.tv_sec, timeval_msec(tk->next_cron), (uint64_t)now.tv_sec, timeval_msec(now), sec_until); if (sec_until > 0.0) continue; tk_log_debug("ticket cron"); last_cron = tk->next_cron; ticket_cron(tk); if (!timercmp(&last_cron, &tk->next_cron, !=)) { tk_log_debug("nobody set ticket wakeup"); set_ticket_wakeup(tk); } } } void tickets_log_info(void) { struct ticket_config *tk; int i; foreach_ticket(i, tk) { tk_log_info("state '%s' " "term %d " "commit index %d " "leader %s " "expires %-24.24s", state_to_string(tk->state), tk->current_term, tk->commit_index, ticket_leader_string(tk), ctime(&tk->term_expires)); } } static void update_acks( struct ticket_config *tk, struct booth_site *sender, struct booth_site *leader, struct boothc_ticket_msg *msg ) { uint32_t cmd; cmd = ntohl(msg->header.cmd); if (tk->acks_expected != cmd && tk->acks_expected != OP_REJECTED) return; /* got an ack! */ tk->acks_received |= sender->bitmask; tk_log_debug("got ACK from %s, %d/%d agree.", site_string(sender), count_bits(tk->acks_received), booth_conf->site_count); if (tk->delay_commit && all_sites_replied(tk)) { tk->delay_commit = 0; } if (all_replied(tk)) { no_resends(tk); tk->start_postpone = 0; set_ticket_wakeup(tk); } } /* UDP message receiver. */ int message_recv(struct boothc_ticket_msg *msg, int msglen) { uint32_t from; struct booth_site *source; struct ticket_config *tk; struct booth_site *leader; uint32_t leader_u; if (check_boothc_header(&msg->header, sizeof(*msg)) < 0 || msglen != sizeof(*msg)) { log_error("message receive error"); return -1; } from = ntohl(msg->header.from); if (!find_site_by_id(from, &source) || !source) { log_error("unknown sender: %08x", from); return -1; } if (!check_ticket(msg->ticket.id, &tk)) { log_warn("got invalid ticket name %s from %s", msg->ticket.id, site_string(source)); return -EINVAL; } leader_u = ntohl(msg->ticket.leader); if (!find_site_by_id(leader_u, &leader)) { tk_log_error("message with unknown leader %u received", leader_u); return -EINVAL; } update_acks(tk, source, leader, msg); return raft_answer(tk, source, leader, msg); } void set_ticket_wakeup(struct ticket_config *tk) { struct timeval tv, now; /* At least every hour, perhaps sooner. */ ticket_next_cron_in(tk, 3600); gettimeofday(&now, NULL); switch (tk->state) { case ST_LEADER: assert(tk->leader == local); tv = now; tv.tv_sec = next_vote_starts_at(tk); /* If timestamp is in the past, wakeup at the expiry * time. */ if (timeval_compare(tv, now) <= 0) { tk_log_debug("next ts in the past (%f)", timeval_to_float(tv) - timeval_to_float(now)); tv.tv_sec = tk->term_expires; } ticket_next_cron_at(tk, tv); break; case ST_CANDIDATE: assert(tk->election_end); ticket_next_cron_at_coarse(tk, tk->election_end); break; case ST_INIT: case ST_FOLLOWER: /* If there is (or should be) some owner, check on it later on. * If no one is interested - don't care. */ if (is_owned(tk) && (local->type == SITE)) ticket_next_cron_at_coarse(tk, tk->term_expires + tk->acquire_after); break; default: tk_log_error("unknown ticket state: %d", tk->state); } if (tk->next_state) { /* we need to do something soon here */ ticket_activate_timeout(tk); } if (ANYDEBUG) { float sec_until; gettimeofday(&now, NULL); sec_until = timeval_to_float(tk->next_cron) - timeval_to_float(now); tk_log_debug("set ticket wakeup in %f", sec_until); } } /* Given a state (in host byte order), return a human-readable (char*). * An array is used so that multiple states can be printed in a single printf(). */ char *state_to_string(uint32_t state_ho) { union mu { cmd_request_t s; char c[5]; }; static union mu cache[6] = { { 0 } }, *cur; static int current = 0; current ++; if (current >= sizeof(cache)/sizeof(cache[0])) current = 0; cur = cache + current; cur->s = htonl(state_ho); /* Shouldn't be necessary, union array is initialized with zeroes, and * these bytes never get written. */ cur->c[4] = 0; return cur->c; } int send_reject(struct booth_site *dest, struct ticket_config *tk, cmd_result_t code) { struct boothc_ticket_msg msg; init_ticket_msg(&msg, OP_REJECTED, code, 0, tk); return booth_udp_send(dest, &msg, sizeof(msg)); } int send_msg ( int cmd, struct ticket_config *tk, struct booth_site *dest ) { struct boothc_ticket_msg msg; if (cmd == OP_MY_INDEX) { tk_log_info("sending status to %s", site_string(dest)); } init_ticket_msg(&msg, cmd, RLT_SUCCESS, 0, tk); return booth_udp_send(dest, &msg, sizeof(msg)); }