Adding upstream version 2:4.20.0+dfsg.upstream/2%4.20.0+dfsg

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 525 insertions, 0 deletions

diff --git a/ctdb/server/ipalloc_lcp2.c b/ctdb/server/ipalloc_lcp2.c
new file mode 100644
index 0000000..996adcf
--- /dev/null
+++ b/ctdb/server/ipalloc_lcp2.c
@@ -0,0 +1,525 @@
+/*
+   ctdb ip takeover code
+
+   Copyright (C) Ronnie Sahlberg  2007
+   Copyright (C) Andrew Tridgell  2007
+   Copyright (C) Martin Schwenke  2011
+
+   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 3 of the License, or
+   (at your option) any later version.
+
+   This program 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 program; if not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "replace.h"
+#include "system/network.h"
+
+#include "lib/util/debug.h"
+#include "common/logging.h"
+
+#include "protocol/protocol_util.h"
+
+#include "server/ipalloc_private.h"
+
+/*
+ * This is the length of the longtest common prefix between the IPs.
+ * It is calculated by XOR-ing the 2 IPs together and counting the
+ * number of leading zeroes.  The implementation means that all
+ * addresses end up being 128 bits long.
+ *
+ * FIXME? Should we consider IPv4 and IPv6 separately given that the
+ * 12 bytes of 0 prefix padding will hurt the algorithm if there are
+ * lots of nodes and IP addresses?
+ */
+static uint32_t ip_distance(ctdb_sock_addr *ip1, ctdb_sock_addr *ip2)
+{
+	uint32_t ip1_k[IP_KEYLEN];
+	uint32_t *t;
+	int i;
+	uint32_t x;
+
+	uint32_t distance = 0;
+
+	memcpy(ip1_k, ip_key(ip1), sizeof(ip1_k));
+	t = ip_key(ip2);
+	for (i=0; i<IP_KEYLEN; i++) {
+		x = ip1_k[i] ^ t[i];
+		if (x == 0) {
+			distance += 32;
+		} else {
+			/* Count number of leading zeroes.
+			 * FIXME? This could be optimised...
+			 */
+			while ((x & ((uint32_t)1 << 31)) == 0) {
+				x <<= 1;
+				distance += 1;
+			}
+		}
+	}
+
+	return distance;
+}
+
+/* Calculate the IP distance for the given IP relative to IPs on the
+   given node.  The ips argument is generally the all_ips variable
+   used in the main part of the algorithm.
+ */
+static uint32_t ip_distance_2_sum(ctdb_sock_addr *ip,
+				  struct public_ip_list *ips,
+				  unsigned int pnn)
+{
+	struct public_ip_list *t;
+	uint32_t d;
+
+	uint32_t sum = 0;
+
+	for (t = ips; t != NULL; t = t->next) {
+		if (t->pnn != pnn) {
+			continue;
+		}
+
+		/* Optimisation: We never calculate the distance
+		 * between an address and itself.  This allows us to
+		 * calculate the effect of removing an address from a
+		 * node by simply calculating the distance between
+		 * that address and all of the existing addresses.
+		 * Moreover, we assume that we're only ever dealing
+		 * with addresses from all_ips so we can identify an
+		 * address via a pointer rather than doing a more
+		 * expensive address comparison. */
+		if (&(t->addr) == ip) {
+			continue;
+		}
+
+		d = ip_distance(ip, &(t->addr));
+		sum += d * d;  /* Cheaper than pulling in math.h :-) */
+	}
+
+	return sum;
+}
+
+/* Return the LCP2 imbalance metric for addresses currently assigned
+   to the given node.
+ */
+static uint32_t lcp2_imbalance(struct public_ip_list * all_ips,
+			       unsigned int pnn)
+{
+	struct public_ip_list *t;
+
+	uint32_t imbalance = 0;
+
+	for (t = all_ips; t != NULL; t = t->next) {
+		if (t->pnn != pnn) {
+			continue;
+		}
+		/* Pass the rest of the IPs rather than the whole
+		   all_ips input list.
+		*/
+		imbalance += ip_distance_2_sum(&(t->addr), t->next, pnn);
+	}
+
+	return imbalance;
+}
+
+static bool lcp2_init(struct ipalloc_state *ipalloc_state,
+		      uint32_t **lcp2_imbalances,
+		      bool **rebalance_candidates)
+{
+	unsigned int i, numnodes;
+	struct public_ip_list *t;
+
+	numnodes = ipalloc_state->num;
+
+	*rebalance_candidates = talloc_array(ipalloc_state, bool, numnodes);
+	if (*rebalance_candidates == NULL) {
+		DEBUG(DEBUG_ERR, (__location__ " out of memory\n"));
+		return false;
+	}
+	*lcp2_imbalances = talloc_array(ipalloc_state, uint32_t, numnodes);
+	if (*lcp2_imbalances == NULL) {
+		DEBUG(DEBUG_ERR, (__location__ " out of memory\n"));
+		return false;
+	}
+
+	for (i=0; i<numnodes; i++) {
+		(*lcp2_imbalances)[i] =
+			lcp2_imbalance(ipalloc_state->all_ips, i);
+		/* First step: assume all nodes are candidates */
+		(*rebalance_candidates)[i] = true;
+	}
+
+	/* 2nd step: if a node has IPs assigned then it must have been
+	 * healthy before, so we remove it from consideration.  This
+	 * is overkill but is all we have because we don't maintain
+	 * state between takeover runs.  An alternative would be to
+	 * keep state and invalidate it every time the recovery master
+	 * changes.
+	 */
+	for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
+		if (t->pnn != CTDB_UNKNOWN_PNN) {
+			(*rebalance_candidates)[t->pnn] = false;
+		}
+	}
+
+	/* 3rd step: if a node is forced to re-balance then
+	   we allow failback onto the node */
+	if (ipalloc_state->force_rebalance_nodes == NULL) {
+		return true;
+	}
+	for (i = 0;
+	     i < talloc_array_length(ipalloc_state->force_rebalance_nodes);
+	     i++) {
+		uint32_t pnn = ipalloc_state->force_rebalance_nodes[i];
+		if (pnn >= numnodes) {
+			DEBUG(DEBUG_ERR,
+			      (__location__ "unknown node %u\n", pnn));
+			continue;
+		}
+
+		DEBUG(DEBUG_NOTICE,
+		      ("Forcing rebalancing of IPs to node %u\n", pnn));
+		(*rebalance_candidates)[pnn] = true;
+	}
+
+	return true;
+}
+
+/* Allocate any unassigned addresses using the LCP2 algorithm to find
+ * the IP/node combination that will cost the least.
+ */
+static void lcp2_allocate_unassigned(struct ipalloc_state *ipalloc_state,
+				     uint32_t *lcp2_imbalances)
+{
+	struct public_ip_list *t;
+	unsigned int dstnode, numnodes;
+
+	unsigned int minnode;
+	uint32_t mindsum, dstdsum, dstimbl;
+	uint32_t minimbl = 0;
+	struct public_ip_list *minip;
+
+	bool should_loop = true;
+	bool have_unassigned = true;
+
+	numnodes = ipalloc_state->num;
+
+	while (have_unassigned && should_loop) {
+		should_loop = false;
+
+		DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
+		DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES (UNASSIGNED)\n"));
+
+		minnode = CTDB_UNKNOWN_PNN;
+		mindsum = 0;
+		minip = NULL;
+
+		/* loop over each unassigned ip. */
+		for (t = ipalloc_state->all_ips; t != NULL ; t = t->next) {
+			if (t->pnn != CTDB_UNKNOWN_PNN) {
+				continue;
+			}
+
+			for (dstnode = 0; dstnode < numnodes; dstnode++) {
+				/* only check nodes that can actually takeover this ip */
+				if (!can_node_takeover_ip(ipalloc_state,
+							  dstnode,
+							  t)) {
+					/* no it couldn't   so skip to the next node */
+					continue;
+				}
+
+				dstdsum = ip_distance_2_sum(&(t->addr),
+							    ipalloc_state->all_ips,
+							    dstnode);
+				dstimbl = lcp2_imbalances[dstnode] + dstdsum;
+				DEBUG(DEBUG_DEBUG,
+				      (" %s -> %d [+%d]\n",
+				       ctdb_sock_addr_to_string(ipalloc_state,
+								&(t->addr),
+								false),
+				       dstnode,
+				       dstimbl - lcp2_imbalances[dstnode]));
+
+
+				if (minnode == CTDB_UNKNOWN_PNN ||
+				    dstdsum < mindsum) {
+					minnode = dstnode;
+					minimbl = dstimbl;
+					mindsum = dstdsum;
+					minip = t;
+					should_loop = true;
+				}
+			}
+		}
+
+		DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
+
+		/* If we found one then assign it to the given node. */
+		if (minnode != CTDB_UNKNOWN_PNN) {
+			minip->pnn = minnode;
+			lcp2_imbalances[minnode] = minimbl;
+			DEBUG(DEBUG_INFO,(" %s -> %d [+%d]\n",
+					  ctdb_sock_addr_to_string(
+						  ipalloc_state,
+						  &(minip->addr), false),
+					  minnode,
+					  mindsum));
+		}
+
+		/* There might be a better way but at least this is clear. */
+		have_unassigned = false;
+		for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
+			if (t->pnn == CTDB_UNKNOWN_PNN) {
+				have_unassigned = true;
+			}
+		}
+	}
+
+	/* We know if we have an unassigned addresses so we might as
+	 * well optimise.
+	 */
+	if (have_unassigned) {
+		for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
+			if (t->pnn == CTDB_UNKNOWN_PNN) {
+				DEBUG(DEBUG_WARNING,
+				      ("Failed to find node to cover ip %s\n",
+				       ctdb_sock_addr_to_string(ipalloc_state,
+								&t->addr,
+								false)));
+			}
+		}
+	}
+}
+
+/* LCP2 algorithm for rebalancing the cluster.  Given a candidate node
+ * to move IPs from, determines the best IP/destination node
+ * combination to move from the source node.
+ */
+static bool lcp2_failback_candidate(struct ipalloc_state *ipalloc_state,
+				    unsigned int srcnode,
+				    uint32_t *lcp2_imbalances,
+				    bool *rebalance_candidates)
+{
+	unsigned int dstnode, mindstnode, numnodes;
+	uint32_t srcdsum, dstimbl, dstdsum;
+	uint32_t minsrcimbl, mindstimbl;
+	struct public_ip_list *minip;
+	struct public_ip_list *t;
+
+	/* Find an IP and destination node that best reduces imbalance. */
+	minip = NULL;
+	minsrcimbl = 0;
+	mindstnode = CTDB_UNKNOWN_PNN;
+	mindstimbl = 0;
+
+	numnodes = ipalloc_state->num;
+
+	DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
+	DEBUG(DEBUG_DEBUG,(" CONSIDERING MOVES FROM %d [%d]\n",
+			   srcnode, lcp2_imbalances[srcnode]));
+
+	for (t = ipalloc_state->all_ips; t != NULL; t = t->next) {
+		uint32_t srcimbl;
+
+		/* Only consider addresses on srcnode. */
+		if (t->pnn != srcnode) {
+			continue;
+		}
+
+		/* What is this IP address costing the source node? */
+		srcdsum = ip_distance_2_sum(&(t->addr),
+					    ipalloc_state->all_ips,
+					    srcnode);
+		srcimbl = lcp2_imbalances[srcnode] - srcdsum;
+
+		/* Consider this IP address would cost each potential
+		 * destination node.  Destination nodes are limited to
+		 * those that are newly healthy, since we don't want
+		 * to do gratuitous failover of IPs just to make minor
+		 * balance improvements.
+		 */
+		for (dstnode = 0; dstnode < numnodes; dstnode++) {
+			if (!rebalance_candidates[dstnode]) {
+				continue;
+			}
+
+			/* only check nodes that can actually takeover this ip */
+			if (!can_node_takeover_ip(ipalloc_state, dstnode,
+						  t)) {
+				/* no it couldn't   so skip to the next node */
+				continue;
+			}
+
+			dstdsum = ip_distance_2_sum(&(t->addr),
+						    ipalloc_state->all_ips,
+						    dstnode);
+			dstimbl = lcp2_imbalances[dstnode] + dstdsum;
+			DEBUG(DEBUG_DEBUG,(" %d [%d] -> %s -> %d [+%d]\n",
+					   srcnode, -srcdsum,
+					   ctdb_sock_addr_to_string(
+						   ipalloc_state,
+						   &(t->addr), false),
+					   dstnode, dstdsum));
+
+			if ((dstimbl < lcp2_imbalances[srcnode]) &&
+			    (dstdsum < srcdsum) &&			\
+			    ((mindstnode == CTDB_UNKNOWN_PNN) ||				\
+			     ((srcimbl + dstimbl) < (minsrcimbl + mindstimbl)))) {
+
+				minip = t;
+				minsrcimbl = srcimbl;
+				mindstnode = dstnode;
+				mindstimbl = dstimbl;
+			}
+		}
+	}
+	DEBUG(DEBUG_DEBUG,(" ----------------------------------------\n"));
+
+        if (mindstnode != CTDB_UNKNOWN_PNN) {
+		/* We found a move that makes things better... */
+		DEBUG(DEBUG_INFO,
+		      ("%d [%d] -> %s -> %d [+%d]\n",
+		       srcnode, minsrcimbl - lcp2_imbalances[srcnode],
+		       ctdb_sock_addr_to_string(ipalloc_state,
+						&(minip->addr), false),
+		       mindstnode, mindstimbl - lcp2_imbalances[mindstnode]));
+
+
+		lcp2_imbalances[srcnode] = minsrcimbl;
+		lcp2_imbalances[mindstnode] = mindstimbl;
+		minip->pnn = mindstnode;
+
+		return true;
+	}
+
+        return false;
+}
+
+struct lcp2_imbalance_pnn {
+	uint32_t imbalance;
+	unsigned int pnn;
+};
+
+static int lcp2_cmp_imbalance_pnn(const void * a, const void * b)
+{
+	const struct lcp2_imbalance_pnn * lipa = (const struct lcp2_imbalance_pnn *) a;
+	const struct lcp2_imbalance_pnn * lipb = (const struct lcp2_imbalance_pnn *) b;
+
+	if (lipa->imbalance > lipb->imbalance) {
+		return -1;
+	} else if (lipa->imbalance == lipb->imbalance) {
+		return 0;
+	} else {
+		return 1;
+	}
+}
+
+/* LCP2 algorithm for rebalancing the cluster.  This finds the source
+ * node with the highest LCP2 imbalance, and then determines the best
+ * IP/destination node combination to move from the source node.
+ */
+static void lcp2_failback(struct ipalloc_state *ipalloc_state,
+			  uint32_t *lcp2_imbalances,
+			  bool *rebalance_candidates)
+{
+	int i, numnodes;
+	struct lcp2_imbalance_pnn * lips;
+	bool again;
+
+	numnodes = ipalloc_state->num;
+
+try_again:
+	/* Put the imbalances and nodes into an array, sort them and
+	 * iterate through candidates.  Usually the 1st one will be
+	 * used, so this doesn't cost much...
+	 */
+	DEBUG(DEBUG_DEBUG,("+++++++++++++++++++++++++++++++++++++++++\n"));
+	DEBUG(DEBUG_DEBUG,("Selecting most imbalanced node from:\n"));
+	lips = talloc_array(ipalloc_state, struct lcp2_imbalance_pnn, numnodes);
+	for (i = 0; i < numnodes; i++) {
+		lips[i].imbalance = lcp2_imbalances[i];
+		lips[i].pnn = i;
+		DEBUG(DEBUG_DEBUG,(" %d [%d]\n", i, lcp2_imbalances[i]));
+	}
+	qsort(lips, numnodes, sizeof(struct lcp2_imbalance_pnn),
+	      lcp2_cmp_imbalance_pnn);
+
+	again = false;
+	for (i = 0; i < numnodes; i++) {
+		/* This means that all nodes had 0 or 1 addresses, so
+		 * can't be imbalanced.
+		 */
+		if (lips[i].imbalance == 0) {
+			break;
+		}
+
+		if (lcp2_failback_candidate(ipalloc_state,
+					    lips[i].pnn,
+					    lcp2_imbalances,
+					    rebalance_candidates)) {
+			again = true;
+			break;
+		}
+	}
+
+	talloc_free(lips);
+	if (again) {
+		goto try_again;
+	}
+}
+
+bool ipalloc_lcp2(struct ipalloc_state *ipalloc_state)
+{
+	uint32_t *lcp2_imbalances;
+	bool *rebalance_candidates;
+	int numnodes, i;
+	bool have_rebalance_candidates;
+	bool ret = true;
+
+	unassign_unsuitable_ips(ipalloc_state);
+
+	if (!lcp2_init(ipalloc_state,
+		       &lcp2_imbalances, &rebalance_candidates)) {
+		ret = false;
+		goto finished;
+	}
+
+	lcp2_allocate_unassigned(ipalloc_state, lcp2_imbalances);
+
+	/* If we don't want IPs to fail back then don't rebalance IPs. */
+	if (ipalloc_state->no_ip_failback) {
+		goto finished;
+	}
+
+	/* It is only worth continuing if we have suitable target
+	 * nodes to transfer IPs to.  This check is much cheaper than
+	 * continuing on...
+	 */
+	numnodes = ipalloc_state->num;
+	have_rebalance_candidates = false;
+	for (i=0; i<numnodes; i++) {
+		if (rebalance_candidates[i]) {
+			have_rebalance_candidates = true;
+			break;
+		}
+	}
+	if (!have_rebalance_candidates) {
+		goto finished;
+	}
+
+	/* Now, try to make sure the ip addresses are evenly distributed
+	   across the nodes.
+	*/
+	lcp2_failback(ipalloc_state, lcp2_imbalances, rebalance_candidates);
+
+finished:
+	return ret;
+}