interface: add prefix assignment priority support

In case of prefix delegation prefixes are assigned to one or more
configured downstream interfaces. The delegated prefix length in
combination with the assignment length of the downstream interfaces
determines the number of subnets which can be allocated from the
delegated prefix.
The interface ip6weight parameter allows to prioritize the allocation
of subnets to interfaces in case of multiple configured downstream
interfaces.

The order of interface prefix assignment from a delegated prefix is
based on the following parameters:
- Primary key is prefix assignment based on the configured interface ip6hint
- Secondary key is the requested downstream interface prefix length,
  interfaces configured with the smallest ip6hint will be assigned first
- Third key is the assigned interface ip6weight in case of equal prefix
  assignment length; interfaces having the highest ip6weight will be
  assigned first
- Finally the alphabetical order of the interfaces in case of equal
  ip6weight

Signed-off-by: Hans Dedecker <dedeckeh@gmail.com>
Signed-off-by: Felix Fietkau <nbd@nbd.name> [cleanup]

5 files changed, 52 insertions, 17 deletions

diff --git a/interface-ip.c b/interface-ip.c
index f8dab84..ddca5d2 100644
--- a/interface-ip.c
+++ b/interface-ip.c
@@ -850,6 +850,25 @@ static bool interface_prefix_assign(struct list_head *list,
 	return false;
 }
 
+/*
+ * Sorting of assignment entries:
+ * Primary on assignment length: smallest assignment first
+ * Secondary on assignment weight: highest weight first
+ * Finally alphabetical order of interface names
+ */
+static int prefix_assignment_cmp(const void *k1, const void *k2, void *ptr)
+{
+	const struct device_prefix_assignment *a1 = k1, *a2 = k2;
+
+	if (a1->length != a2->length)
+		return a1->length - a2->length;
+
+	if (a1->weight != a2->weight)
+		return a2->weight - a1->weight;
+
+	return strcmp(a1->name, a2->name);
+}
+
 static void interface_update_prefix_assignments(struct device_prefix *prefix, bool setup)
 {
 	struct device_prefix_assignment *c;
@@ -894,7 +913,13 @@ static void interface_update_prefix_assignments(struct device_prefix *prefix, bo
 	}
 
 	bool assigned_any = false;
-	struct list_head assign_later = LIST_HEAD_INIT(assign_later);
+	struct {
+		struct avl_node node;
+	} *entry, *n_entry;
+	struct avl_tree assign_later;
+
+	avl_init(&assign_later, prefix_assignment_cmp, false, NULL);
+
 	vlist_for_each_element(&interfaces, iface, node) {
 		if (iface->assignment_length < 48 ||
 				iface->assignment_length > 64)
@@ -923,6 +948,7 @@ static void interface_update_prefix_assignments(struct device_prefix *prefix, bo
 
 		c->length = iface->assignment_length;
 		c->assigned = iface->assignment_hint;
+		c->weight = iface->assignment_weight;
 		c->addr = in6addr_any;
 		c->enabled = false;
 		memcpy(c->name, iface->name, namelen);
@@ -935,27 +961,25 @@ static void interface_update_prefix_assignments(struct device_prefix *prefix, bo
 						"of size %hhu for %s, trying other\n", c->length, c->name);
 			}
 
-			struct list_head *next = &assign_later;
-			struct device_prefix_assignment *n;
-			list_for_each_entry(n, &assign_later, head) {
-				if (n->length < c->length) {
-					next = &n->head;
-					break;
-				}
-			}
-			list_add_tail(&c->head, next);
+			entry = calloc(1, sizeof(*entry));
+			if (!entry)
+				continue;
+
+			entry->node.key = c;
+			avl_insert(&assign_later, &entry->node);
 		}
 
 		if (c->assigned != -1)
 			assigned_any = true;
 	}
 
-	// Then try to assign all other + failed custom assignments
-	while (!list_empty(&assign_later)) {
-		c = list_first_entry(&assign_later, struct device_prefix_assignment, head);
-		list_del(&c->head);
-
+	/* Then try to assign all other + failed custom assignments */
+	avl_for_each_element_safe(&assign_later, entry, node, n_entry) {
 		bool assigned = false;
+
+		c = (struct device_prefix_assignment *)entry->node.key;
+		avl_delete(&assign_later, &entry->node);
+
 		do {
 			assigned = interface_prefix_assign(&prefix->assignments, c);
 		} while (!assigned && ++c->length <= 64);
@@ -964,9 +988,10 @@ static void interface_update_prefix_assignments(struct device_prefix *prefix, bo
 			netifd_log_message(L_WARNING, "Failed to assign subprefix "
 					"of size %hhu for %s\n", c->length, c->name);
 			free(c);
-		} else {
+		} else
 			assigned_any = true;
-		}
+
+		free(entry);
 	}
 
 	list_for_each_entry(c, &prefix->assignments, head)
diff --git a/interface-ip.h b/interface-ip.h
index 01727c9..197bd9a 100644
--- a/interface-ip.h
+++ b/interface-ip.h
@@ -59,6 +59,7 @@ struct device_prefix_assignment {
 	struct list_head head;
 	int32_t assigned;
 	uint8_t length;
+	int weight;
 	struct in6_addr addr;
 	bool enabled;
 	char name[];
diff --git a/interface.c b/interface.c
index 522e7fe..f150f7d 100644
--- a/interface.c
+++ b/interface.c
@@ -46,6 +46,7 @@ enum {
 	IFACE_ATTR_DELEGATE,
 	IFACE_ATTR_IP6IFACEID,
 	IFACE_ATTR_FORCE_LINK,
+	IFACE_ATTR_IP6WEIGHT,
 	IFACE_ATTR_MAX
 };
 
@@ -68,6 +69,7 @@ static const struct blobmsg_policy iface_attrs[IFACE_ATTR_MAX] = {
 	[IFACE_ATTR_DELEGATE] = { .name = "delegate", .type = BLOBMSG_TYPE_BOOL },
 	[IFACE_ATTR_IP6IFACEID] = { .name = "ip6ifaceid", .type = BLOBMSG_TYPE_STRING },
 	[IFACE_ATTR_FORCE_LINK] = { .name = "force_link", .type = BLOBMSG_TYPE_BOOL },
+	[IFACE_ATTR_IP6WEIGHT] = { .name = "ip6weight", .type = BLOBMSG_TYPE_INT32 },
 };
 
 const struct uci_blob_param_list interface_attr_list = {
@@ -497,6 +499,7 @@ interface_merge_assignment_data(struct interface *old, struct interface *new)
 	bool changed = (old->assignment_hint != new->assignment_hint ||
 			old->assignment_length != new->assignment_length ||
 			old->assignment_iface_id_selection != new->assignment_iface_id_selection ||
+			old->assignment_weight != new->assignment_weight ||
 			(old->assignment_iface_id_selection == IFID_FIXED &&
 			 memcmp(&old->assignment_fixed_iface_id, &new->assignment_fixed_iface_id,
 				sizeof(old->assignment_fixed_iface_id))) ||
@@ -534,6 +537,7 @@ interface_merge_assignment_data(struct interface *old, struct interface *new)
 		old->assignment_length = new->assignment_length;
 		old->assignment_iface_id_selection = new->assignment_iface_id_selection;
 		old->assignment_fixed_iface_id = new->assignment_fixed_iface_id;
+		old->assignment_weight = new->assignment_weight;
 		interface_refresh_assignments(true);
 	}
 }
@@ -842,6 +846,8 @@ interface_alloc(const char *name, struct blob_attr *config)
 	if ((cur = tb[IFACE_ATTR_IP6CLASS]))
 		interface_add_assignment_classes(iface, cur);
 
+	if ((cur = tb[IFACE_ATTR_IP6WEIGHT]))
+		iface->assignment_weight = blobmsg_get_u32(cur);
 
 	if ((cur = tb[IFACE_ATTR_IP4TABLE])) {
 		if (!system_resolve_rt_table(blobmsg_data(cur), &iface->ip4table))
diff --git a/interface.h b/interface.h
index 7d5b309..1472324 100644
--- a/interface.h
+++ b/interface.h
@@ -155,6 +155,7 @@ struct interface {
 	uint8_t assignment_length;
 	int32_t assignment_hint;
 	struct list_head assignment_classes;
+	int assignment_weight;
 
 	/* errors/warnings while trying to bring up the interface */
 	struct list_head errors;
diff --git a/ubus.c b/ubus.c
index 66f714a..1b1a4cd 100644
--- a/ubus.c
+++ b/ubus.c
@@ -698,6 +698,8 @@ netifd_dump_status(struct interface *iface)
 		blobmsg_add_u32(&b, "metric", iface->metric);
 		blobmsg_add_u32(&b, "dns_metric", iface->dns_metric);
 		blobmsg_add_u8(&b, "delegation", !iface->proto_ip.no_delegation);
+		if (iface->assignment_weight)
+			blobmsg_add_u32(&b, "ip6weight", iface->assignment_weight);
 		a = blobmsg_open_array(&b, "ipv4-address");
 		interface_ip_dump_address_list(&iface->config_ip, false, true);
 		interface_ip_dump_address_list(&iface->proto_ip, false, true);