diff --git a/qdevices/qnetd-algo-lms.c b/qdevices/qnetd-algo-lms.c index 55a1bb29..cdd86c4d 100644 --- a/qdevices/qnetd-algo-lms.c +++ b/qdevices/qnetd-algo-lms.c @@ -1,381 +1,393 @@ /* * Copyright (c) 2015-2016 Red Hat, Inc. * * All rights reserved. * * Author: Christine Caulfield (ccaulfie@redhat.com) * * This software licensed under BSD license, the text of which follows: * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * - Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * - Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * - Neither the name of the Red Hat, Inc. nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF * THE POSSIBILITY OF SUCH DAMAGE. */ /* * This is a 'last man standing' algorithm for 2+ node clusters * * If the node is the only one left in the cluster that can see the * qdevice server then we return a vote. * * If more than one node can see the qdevice server but some nodes can't * see each other then we divide the cluster up into 'partitions' based on * their ring_id and return a vote to nodes in the partition that contains * a nominated nodeid. (lowest, highest, etc) * */ #include #include #include #include #include "qnetd-algo-lms.h" #include "qnetd-log.h" #include "qnetd-cluster-list.h" #include "qnetd-algo-utils.h" #include "qnetd-client-algo-timer.h" #include "utils.h" struct qnetd_algo_lms_info { int num_config_nodes; enum tlv_vote last_result; partitions_list_t partition_list; }; static enum tlv_reply_error_code do_lms_algorithm(struct qnetd_client *client, const struct tlv_ring_id *cur_ring_id, enum tlv_vote *result_vote) { struct qnetd_client *other_client; struct qnetd_algo_lms_info *info = client->algorithm_data; struct qnetd_algo_partition *cur_partition; struct qnetd_algo_partition *largest_partition; const struct tlv_ring_id *ring_id = cur_ring_id; int num_partitions; int joint_leader; /* We are running the algorithm, don't do it again unless we say so */ qnetd_client_algo_timer_abort(client); if (qnetd_algo_all_ring_ids_match(client, ring_id) == -1) { qnetd_log(LOG_DEBUG, "algo-lms: nodeid %d: ring ID %d/%ld not unique in this membership, waiting", client->node_id, ring_id->node_id, ring_id->seq); qnetd_client_algo_timer_schedule(client); *result_vote = info->last_result = TLV_VOTE_WAIT_FOR_REPLY; return (TLV_REPLY_ERROR_CODE_NO_ERROR); } /* Create and count the number of separate partitions */ if ( (num_partitions = qnetd_algo_create_partitions(client, &info->partition_list, ring_id)) == -1) { qnetd_log(LOG_DEBUG, "algo-lms: Error creating partition list"); return (TLV_REPLY_ERROR_CODE_INTERNAL_ERROR); } /* This can happen if we are first on the block */ if (num_partitions == 0) { qnetd_log(LOG_DEBUG, "algo-lms: No partitions found"); qnetd_client_algo_timer_schedule(client); *result_vote = info->last_result = TLV_VOTE_WAIT_FOR_REPLY; return (TLV_REPLY_ERROR_CODE_NO_ERROR); } qnetd_algo_dump_partitions(&info->partition_list); /* Only 1 partition - let votequorum sort it out */ if (num_partitions == 1) { qnetd_log(LOG_DEBUG, "algo-lms: Only 1 partition. This is votequorum's problem, not ours"); qnetd_algo_free_partitions(&info->partition_list); *result_vote = info->last_result = TLV_VOTE_ACK; return (TLV_REPLY_ERROR_CODE_NO_ERROR); } /* If we're a newcomer and there is another active partition, then we must NACK * to avoid quorum moving to us from already active nodes. */ if (info->last_result == 0) { TAILQ_FOREACH(other_client, &client->cluster->client_list, cluster_entries) { struct qnetd_algo_lms_info *other_info = other_client->algorithm_data; if (!tlv_ring_id_eq(ring_id, &other_client->last_ring_id) && other_info->last_result == TLV_VOTE_ACK) { qnetd_algo_free_partitions(&info->partition_list); /* Don't save NACK, we need to know subsequently if we haven't been voting */ *result_vote = TLV_VOTE_NACK; qnetd_log(LOG_DEBUG, "algo-lms: we are a new partition and another active partition exists. NACK"); return (TLV_REPLY_ERROR_CODE_NO_ERROR); } } } /* Find the largest partition */ largest_partition = NULL; TAILQ_FOREACH(cur_partition, &info->partition_list, entries) { if (!largest_partition || largest_partition->num_nodes < cur_partition->num_nodes) { largest_partition = cur_partition; } } qnetd_log(LOG_DEBUG, "algo-lms: largest partition is %d/%ld with %d nodes", largest_partition->ring_id.node_id, largest_partition->ring_id.seq, largest_partition->num_nodes); /* Now check if it's really the largest, and not just the joint-largest */ joint_leader = 0; TAILQ_FOREACH(cur_partition, &info->partition_list, entries) { if (largest_partition != cur_partition && largest_partition->num_nodes == cur_partition->num_nodes) { joint_leader = 1; } } if (!joint_leader) { /* Largest partition is unique, allow us to run if we're in that partition. */ if (tlv_ring_id_eq(&largest_partition->ring_id, ring_id)) { qnetd_log(LOG_DEBUG, "algo-lms: We are in the largest partition. ACK"); *result_vote = info->last_result = TLV_VOTE_ACK; } else { qnetd_log(LOG_DEBUG, "algo-lms: We are NOT in the largest partition. NACK"); *result_vote = info->last_result = TLV_VOTE_NACK; } } else { int tb_node_id; struct tlv_ring_id tb_node_ring_id = {0LL, 0}; /* Look for the tie-breaker node */ if (client->tie_breaker.mode == TLV_TIE_BREAKER_MODE_LOWEST) { tb_node_id = INT_MAX; } else if (client->tie_breaker.mode == TLV_TIE_BREAKER_MODE_HIGHEST) { tb_node_id = 0; } else if (client->tie_breaker.mode == TLV_TIE_BREAKER_MODE_NODE_ID) { tb_node_id = client->tie_breaker.node_id; } else { qnetd_log(LOG_DEBUG, "algo-lms: denied vote because tie-breaker option is invalid: %d", client->tie_breaker.mode); tb_node_id = -1; } /* Find the tie_breaker node */ TAILQ_FOREACH(other_client, &client->cluster->client_list, cluster_entries) { switch (client->tie_breaker.mode) { case TLV_TIE_BREAKER_MODE_LOWEST: if (other_client->node_id < tb_node_id) { tb_node_id = other_client->node_id; memcpy(&tb_node_ring_id, &other_client->last_ring_id, sizeof(struct tlv_ring_id)); qnetd_log(LOG_DEBUG, "algo-lms: Looking for low node ID. found %d (%d/%ld)", tb_node_id, tb_node_ring_id.node_id, tb_node_ring_id.seq); } break; case TLV_TIE_BREAKER_MODE_HIGHEST: if (other_client->node_id > tb_node_id) { tb_node_id = other_client->node_id; memcpy(&tb_node_ring_id, &other_client->last_ring_id, sizeof(struct tlv_ring_id)); qnetd_log(LOG_DEBUG, "algo-lms: Looking for high node ID. found %d (%d/%ld)", tb_node_id, tb_node_ring_id.node_id, tb_node_ring_id.seq); } break; case TLV_TIE_BREAKER_MODE_NODE_ID: if (client->tie_breaker.node_id == client->node_id) { memcpy(&tb_node_ring_id, &other_client->last_ring_id, sizeof(struct tlv_ring_id)); qnetd_log(LOG_DEBUG, "algo-lms: Looking for nominated node ID. found %d (%d/%ld)", tb_node_id, tb_node_ring_id.node_id, tb_node_ring_id.seq); } break; default: qnetd_log(LOG_DEBUG, "algo-lms: denied vote because tie-breaker option is invalid: %d", client->tie_breaker.mode); memset(&tb_node_ring_id, 0, sizeof(struct tlv_ring_id)); } } if (client->node_id == tb_node_id || tlv_ring_id_eq(&tb_node_ring_id, ring_id)) { qnetd_log(LOG_DEBUG, "algo-lms: We are in the same partition (%d/%ld) as tie-breaker node id %d. ACK", tb_node_ring_id.node_id, tb_node_ring_id.seq, tb_node_id); *result_vote = info->last_result = TLV_VOTE_ACK; } else { qnetd_log(LOG_DEBUG, "algo-lms: We are NOT in the same partition (%d/%ld) as tie-breaker node id %d. NACK", tb_node_ring_id.node_id, tb_node_ring_id.seq, tb_node_id); *result_vote = info->last_result = TLV_VOTE_NACK; } } qnetd_algo_free_partitions(&info->partition_list); return (TLV_REPLY_ERROR_CODE_NO_ERROR); } enum tlv_reply_error_code qnetd_algo_lms_client_init(struct qnetd_client *client) { struct qnetd_algo_lms_info *info; info = malloc(sizeof(struct qnetd_algo_lms_info)); if (!info) { return (TLV_REPLY_ERROR_CODE_INTERNAL_ERROR); } memset(info, 0, sizeof(*info)); client->algorithm_data = info; info->last_result = 0; /* status unknown, or NEW */ TAILQ_INIT(&info->partition_list); return (TLV_REPLY_ERROR_CODE_NO_ERROR); } /* * We got the config node list. Simply count the number of available nodes * and wait for the quorum list. */ enum tlv_reply_error_code qnetd_algo_lms_config_node_list_received(struct qnetd_client *client, uint32_t msg_seq_num, int config_version_set, uint64_t config_version, const struct node_list *nodes, int initial, enum tlv_vote *result_vote) { struct node_list_entry *node_info; struct qnetd_algo_lms_info *info = client->algorithm_data; int node_count = 0; TAILQ_FOREACH(node_info, nodes, entries) { node_count++; } info->num_config_nodes = node_count; qnetd_log(LOG_DEBUG, "algo-lms: cluster %s config_list has %d nodes", client->cluster_name, node_count); *result_vote = TLV_VOTE_NO_CHANGE; return (TLV_REPLY_ERROR_CODE_NO_ERROR); } /* * membership node list. This is where we get to work. */ enum tlv_reply_error_code qnetd_algo_lms_membership_node_list_received(struct qnetd_client *client, uint32_t msg_seq_num, const struct tlv_ring_id *ring_id, const struct node_list *nodes, enum tlv_vote *result_vote) { qnetd_log(LOG_DEBUG, " "); qnetd_log(LOG_DEBUG, "algo-lms: membership list from node %d partition %d/%ld", client->node_id, ring_id->node_id, ring_id->seq); return do_lms_algorithm(client, ring_id, result_vote); } /* * The quorum node list is received after corosync has decided which nodes are in the cluster. * We run our algorithm again to be sure that things still match. By this time we will (or should) * all know the current ring_id (not guaranteed when the membership list is received). So this * might be the most reliable return. */ enum tlv_reply_error_code qnetd_algo_lms_quorum_node_list_received(struct qnetd_client *client, uint32_t msg_seq_num, enum tlv_quorate quorate, const struct node_list *nodes, enum tlv_vote *result_vote) { qnetd_log(LOG_DEBUG, " "); qnetd_log(LOG_DEBUG, "algo-lms: quorum node list from node %d partition %d/%ld", client->node_id, client->last_ring_id.node_id, client->last_ring_id.seq); return do_lms_algorithm(client, &client->last_ring_id, result_vote); } /* * Called after client disconnect. Client structure is still existing (and it's part * of a client->cluster), but it is destroyed (and removed from cluster) right after * this callback finishes. Callback is used mainly for destroing client->algorithm_data. */ void qnetd_algo_lms_client_disconnect(struct qnetd_client *client, int server_going_down) { qnetd_log(LOG_DEBUG, "algo-lms: Client %p (cluster %s, node_id "UTILS_PRI_NODE_ID") " "disconnect", client, client->cluster_name, client->node_id); qnetd_log(LOG_INFO, "algo-lms: server going down %u", server_going_down); free(client->algorithm_data); } /* * Called after client sent ask for vote message. This is usually happening after server * replied TLV_VOTE_WAIT_FOR_REPLY. */ enum tlv_reply_error_code qnetd_algo_lms_ask_for_vote_received(struct qnetd_client *client, uint32_t msg_seq_num, enum tlv_vote *result_vote) { qnetd_log(LOG_DEBUG, " "); qnetd_log(LOG_DEBUG, "algo-lms: Client %p (cluster %s, node_id "UTILS_PRI_NODE_ID") " "asked for a vote", client, client->cluster_name, client->node_id); return do_lms_algorithm(client, &client->last_ring_id, result_vote); } enum tlv_reply_error_code qnetd_algo_lms_vote_info_reply_received(struct qnetd_client *client, uint32_t msg_seq_num) { qnetd_log(LOG_DEBUG, "algo-lms: Client %p (cluster %s, node_id "UTILS_PRI_NODE_ID") " "replied back to vote info message", client, client->cluster_name, client->node_id); return (TLV_REPLY_ERROR_CODE_NO_ERROR); } enum tlv_reply_error_code qnetd_algo_lms_timer_callback(struct qnetd_client *client, int *reschedule_timer, int *send_vote, enum tlv_vote *result_vote) { enum tlv_reply_error_code ret; qnetd_log(LOG_DEBUG, "algo-lms: Client %p (cluster %s, node_id "UTILS_PRI_NODE_ID") " "Timer callback", client, client->cluster_name, client->node_id); ret = do_lms_algorithm(client, &client->last_ring_id, result_vote); if (ret == TLV_REPLY_ERROR_CODE_NO_ERROR && (*result_vote == TLV_VOTE_ACK || *result_vote == TLV_VOTE_NACK)) { *send_vote = 1; } + + if (ret == TLV_REPLY_ERROR_CODE_NO_ERROR && + *result_vote == TLV_VOTE_WAIT_FOR_REPLY) { + /* + * Reschedule was called in the do_lms_algorithm but algo_timer is + * not stack based so there can only be one. So if do_lms aborted + * the active timer, and scheduled it again the timer would be aborted + * if reschedule_timer was not set. + */ + *reschedule_timer = 1; + } + return ret; } static struct qnetd_algorithm qnetd_algo_lms = { .init = qnetd_algo_lms_client_init, .config_node_list_received = qnetd_algo_lms_config_node_list_received, .membership_node_list_received = qnetd_algo_lms_membership_node_list_received, .quorum_node_list_received = qnetd_algo_lms_quorum_node_list_received, .client_disconnect = qnetd_algo_lms_client_disconnect, .ask_for_vote_received = qnetd_algo_lms_ask_for_vote_received, .vote_info_reply_received = qnetd_algo_lms_vote_info_reply_received, .timer_callback = qnetd_algo_lms_timer_callback, }; enum tlv_reply_error_code qnetd_algo_lms_register() { return qnetd_algorithm_register(TLV_DECISION_ALGORITHM_TYPE_LMS, &qnetd_algo_lms); } diff --git a/qdevices/qnetd-algo-utils.c b/qdevices/qnetd-algo-utils.c index 440f81f6..e26b40ae 100644 --- a/qdevices/qnetd-algo-utils.c +++ b/qdevices/qnetd-algo-utils.c @@ -1,153 +1,167 @@ /* * Copyright (c) 2016 Red Hat, Inc. * * All rights reserved. * * Author: Christine Caulfield (ccaulfie@redhat.com) * * This software licensed under BSD license, the text of which follows: * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * - Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * - Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * - Neither the name of the Red Hat, Inc. nor the names of its * contributors may be used to endorse or promote products derived from this * software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF * THE POSSIBILITY OF SUCH DAMAGE. */ #include #include #include "qnetd-log.h" #include "qnetd-cluster-list.h" #include "qnetd-algo-utils.h" /* * Returns -1 if any node that is supposedly in the same cluster partition * as us has a different ring_id. * If this happens it simply means that qnetd does not yet have the full current view * of the cluster and should wait until all of the ring_ids in this membership list match up */ int qnetd_algo_all_ring_ids_match(struct qnetd_client *client, const struct tlv_ring_id *ring_id) { struct node_list_entry *node_info; struct qnetd_client *other_client; TAILQ_FOREACH(other_client, &client->cluster->client_list, cluster_entries) { int in_our_partition = 0; if (other_client == client) { continue; /* We've seen our membership list */ } qnetd_log(LOG_DEBUG, "algo-util: all_ring_ids_match: seen nodeid %d (client %p) ring_id (%d/%ld)", other_client->node_id, other_client, other_client->last_ring_id.node_id, other_client->last_ring_id.seq); /* Look down our node list and see if this client is known to us */ TAILQ_FOREACH(node_info, &client->last_membership_node_list, entries) { if (node_info->node_id == other_client->node_id) { in_our_partition = 1; } } + if (in_our_partition == 0) { + /* + * Also try to look from the other side to see if we are + * not in the other node's membership list. + * Because if so it may mean the membership lists are not equal + */ + TAILQ_FOREACH(node_info, &other_client->last_membership_node_list, entries) { + if (node_info->node_id == client->node_id) { + in_our_partition = 1; + } + } + } + /* * If the other nodes on our side of a partition have a different ring ID then * we need to wait until they have all caught up before making a decision */ if (in_our_partition && !tlv_ring_id_eq(ring_id, &other_client->last_ring_id)) { qnetd_log(LOG_DEBUG, "algo-util: nodeid %d in our partition has different ring_id (%d/%ld) to us (%d/%ld)", other_client->node_id, other_client->last_ring_id.node_id, other_client->last_ring_id.seq, ring_id->node_id, ring_id->seq); return (-1); /* ring IDs don't match */ } } + return (0); } struct qnetd_algo_partition * qnetd_algo_find_partition(partitions_list_t *partitions_list, const struct tlv_ring_id *ring_id) { struct qnetd_algo_partition *cur_partition; TAILQ_FOREACH(cur_partition, partitions_list, entries) { if (tlv_ring_id_eq(&cur_partition->ring_id, ring_id)) { return (cur_partition); } } return (NULL); } int qnetd_algo_create_partitions(struct qnetd_client *client, partitions_list_t *partitions_list, const struct tlv_ring_id *ring_id) { struct qnetd_client *other_client; int num_partitions = 0; TAILQ_FOREACH(other_client, &client->cluster->client_list, cluster_entries) { struct qnetd_algo_partition *partition; if (other_client->last_ring_id.seq == 0){ continue; /* not initialised yet */ } partition = qnetd_algo_find_partition(partitions_list, &other_client->last_ring_id); if (!partition) { partition = malloc(sizeof(struct qnetd_algo_partition)); if (!partition) { return (-1); } partition->num_nodes = 0; memcpy(&partition->ring_id, &other_client->last_ring_id, sizeof(*ring_id)); num_partitions++; TAILQ_INSERT_TAIL(partitions_list, partition, entries); } partition->num_nodes++; } return (num_partitions); } void qnetd_algo_free_partitions(partitions_list_t *partitions_list) { struct qnetd_algo_partition *cur_partition; struct qnetd_algo_partition *partition_next; cur_partition = TAILQ_FIRST(partitions_list); while (cur_partition != NULL) { partition_next = TAILQ_NEXT(cur_partition, entries); free(cur_partition); cur_partition = partition_next; } TAILQ_INIT(partitions_list); } void qnetd_algo_dump_partitions(partitions_list_t *partitions_list) { struct qnetd_algo_partition *partition; TAILQ_FOREACH(partition, partitions_list, entries) { qnetd_log(LOG_DEBUG, "algo-util: partition %d/%ld (%p) has %d nodes", partition->ring_id.node_id, partition->ring_id.seq, partition, partition->num_nodes); } }