ctdb-ipalloc: Optimise check to see if IP is available on a node

Use a "bitmap" of available IPs for each IP address instead of walking
the list of available IP addresses.

For ctdb/tests/takeover/lcp2.030.sh, this improves the time taken on
my laptop from:

  real	0m11.997s
  user	0m11.960s
  sys	0m0.000s

to

  real	0m8.571s
  user	0m8.544s
  sys	0m0.000s

So, when assigning all 900 IP addresses the improvement is about 25%.

For the no-op case (where all IPs are already assigned to nodes), the
extra setup adds a small fraction of a second for 900 IPs.
Intermediate cases result in intermediate improvements.

Signed-off-by: Martin Schwenke <martin@meltin.net>
Reviewed-by: Amitay Isaacs <amitay@gmail.com>

1 files changed, 37 insertions, 0 deletions

diff --git a/ctdb/server/ipalloc.c b/ctdb/server/ipalloc.c
index 37804ea029e..819add164b0 100644
--- a/ctdb/server/ipalloc.c
+++ b/ctdb/server/ipalloc.c
@@ -29,6 +29,8 @@
 #include "common/logging.h"
 #include "common/rb_tree.h"
 
+#include "protocol/protocol_api.h"
+
 #include "server/ipalloc_private.h"
 
 /* Initialise main ipalloc state and sub-structures */
@@ -160,6 +162,37 @@ create_merged_ip_list(struct ipalloc_state *ipalloc_state)
 	return ip_list;
 }
 
+static bool populate_bitmap(struct ipalloc_state *ipalloc_state)
+{
+	struct public_ip_list *ip = NULL;
+	int i, j;
+
+	for (ip = ipalloc_state->all_ips; ip != NULL; ip = ip->next) {
+
+		ip->available_on = talloc_zero_array(ip, bool,
+						     ipalloc_state->num);
+		if (ip->available_on == NULL) {
+			return false;
+		}
+
+		for (i = 0; i < ipalloc_state->num; i++) {
+			struct ctdb_public_ip_list *avail =
+				&ipalloc_state->available_public_ips[i];
+
+			/* Check to see if "ip" is available on node "i" */
+			for (j = 0; j < avail->num; j++) {
+				if (ctdb_sock_addr_same_ip(
+					    &ip->addr, &avail->ip[j].addr)) {
+					ip->available_on[i] = true;
+					break;
+				}
+			}
+		}
+	}
+
+	return true;
+}
+
 static bool all_nodes_are_disabled(struct ctdb_node_map *nodemap)
 {
 	int i;
@@ -283,6 +316,10 @@ struct public_ip_list *ipalloc(struct ipalloc_state *ipalloc_state)
 		return NULL;
 	}
 
+	if (!populate_bitmap(ipalloc_state)) {
+		return NULL;
+	}
+
 	switch (ipalloc_state->algorithm) {
 	case IPALLOC_LCP2:
 		ret = ipalloc_lcp2(ipalloc_state);