lib: fix ordering issues in the northbound

When a configuration transaction is being performed, the northbound
uses a red-black tree to store the configuration changes that need to
be processed. The problem is that we were sorting the configuration
changes based on their XPaths (and callback priorities). This means
the original order of the changes wasn't being respected, which is
a problem for lists that use the "ordered-by user" statement. To
fix this, add a new "seq" member to the "nb_config_cb" structure
so that we can preserve the order of the configuration changes as
told by libyang.

Since none of the FRR modules use "ordered-by user" lists so far,
no daemon was affected by this problem.

Reported-by: Martin Winter <mwinter@opensourcerouting.org>
Signed-off-by: Renato Westphal <renato@opensourcerouting.org>

2 files changed, 19 insertions, 13 deletions

diff --git a/lib/northbound.c b/lib/northbound.c
index 75f1e07b7f..42fd1fba50 100644
--- a/lib/northbound.c
+++ b/lib/northbound.c
@@ -337,21 +337,23 @@ static inline int nb_config_cb_compare(const struct nb_config_cb *a,
 		return 1;
 
 	/*
-	 * Use XPath as a tie-breaker. This will naturally sort parent nodes
-	 * before their children.
+	 * Preserve the order of the configuration changes as told by libyang.
 	 */
-	return strcmp(a->xpath, b->xpath);
+	return a->seq - b->seq;
 }
 RB_GENERATE(nb_config_cbs, nb_config_cb, entry, nb_config_cb_compare);
 
 static void nb_config_diff_add_change(struct nb_config_cbs *changes,
 				      enum nb_operation operation,
+				      uint32_t *seq,
 				      const struct lyd_node *dnode)
 {
 	struct nb_config_change *change;
 
 	change = XCALLOC(MTYPE_TMP, sizeof(*change));
 	change->cb.operation = operation;
+	change->cb.seq = *seq;
+	*seq = *seq + 1;
 	change->cb.nb_node = dnode->schema->priv;
 	yang_dnode_get_path(dnode, change->cb.xpath, sizeof(change->cb.xpath));
 	change->cb.dnode = dnode;
@@ -376,7 +378,7 @@ static void nb_config_diff_del_changes(struct nb_config_cbs *changes)
  * configurations. Given a new subtree, calculate all new YANG data nodes,
  * excluding default leafs and leaf-lists. This is a recursive function.
  */
-static void nb_config_diff_created(const struct lyd_node *dnode,
+static void nb_config_diff_created(const struct lyd_node *dnode, uint32_t *seq,
 				   struct nb_config_cbs *changes)
 {
 	enum nb_operation operation;
@@ -395,16 +397,17 @@ static void nb_config_diff_created(const struct lyd_node *dnode,
 		else
 			return;
 
-		nb_config_diff_add_change(changes, operation, dnode);
+		nb_config_diff_add_change(changes, operation, seq, dnode);
 		break;
 	case LYS_CONTAINER:
 	case LYS_LIST:
 		if (nb_operation_is_valid(NB_OP_CREATE, dnode->schema))
-			nb_config_diff_add_change(changes, NB_OP_CREATE, dnode);
+			nb_config_diff_add_change(changes, NB_OP_CREATE, seq,
+						  dnode);
 
 		/* Process child nodes recursively. */
 		LY_TREE_FOR (dnode->child, child) {
-			nb_config_diff_created(child, changes);
+			nb_config_diff_created(child, seq, changes);
 		}
 		break;
 	default:
@@ -412,11 +415,11 @@ static void nb_config_diff_created(const struct lyd_node *dnode,
 	}
 }
 
-static void nb_config_diff_deleted(const struct lyd_node *dnode,
+static void nb_config_diff_deleted(const struct lyd_node *dnode, uint32_t *seq,
 				   struct nb_config_cbs *changes)
 {
 	if (nb_operation_is_valid(NB_OP_DESTROY, dnode->schema))
-		nb_config_diff_add_change(changes, NB_OP_DESTROY, dnode);
+		nb_config_diff_add_change(changes, NB_OP_DESTROY, seq, dnode);
 	else if (CHECK_FLAG(dnode->schema->nodetype, LYS_CONTAINER)) {
 		struct lyd_node *child;
 
@@ -427,7 +430,7 @@ static void nb_config_diff_deleted(const struct lyd_node *dnode,
 		 * when applicable (i.e. optional nodes).
 		 */
 		LY_TREE_FOR (dnode->child, child) {
-			nb_config_diff_deleted(child, changes);
+			nb_config_diff_deleted(child, seq, changes);
 		}
 	}
 }
@@ -438,6 +441,7 @@ static void nb_config_diff(const struct nb_config *config1,
 			   struct nb_config_cbs *changes)
 {
 	struct lyd_difflist *diff;
+	uint32_t seq = 0;
 
 	diff = lyd_diff(config1->dnode, config2->dnode,
 			LYD_DIFFOPT_WITHDEFAULTS);
@@ -452,15 +456,16 @@ static void nb_config_diff(const struct nb_config *config1,
 		switch (type) {
 		case LYD_DIFF_CREATED:
 			dnode = diff->second[i];
-			nb_config_diff_created(dnode, changes);
+			nb_config_diff_created(dnode, &seq, changes);
 			break;
 		case LYD_DIFF_DELETED:
 			dnode = diff->first[i];
-			nb_config_diff_deleted(dnode, changes);
+			nb_config_diff_deleted(dnode, &seq, changes);
 			break;
 		case LYD_DIFF_CHANGED:
 			dnode = diff->second[i];
-			nb_config_diff_add_change(changes, NB_OP_MODIFY, dnode);
+			nb_config_diff_add_change(changes, NB_OP_MODIFY, &seq,
+						  dnode);
 			break;
 		case LYD_DIFF_MOVEDAFTER1:
 		case LYD_DIFF_MOVEDAFTER2:
diff --git a/lib/northbound.h b/lib/northbound.h
index 50bddd157f..fbd7771db7 100644
--- a/lib/northbound.h
+++ b/lib/northbound.h
@@ -457,6 +457,7 @@ struct nb_config {
 struct nb_config_cb {
 	RB_ENTRY(nb_config_cb) entry;
 	enum nb_operation operation;
+	uint32_t seq;
 	char xpath[XPATH_MAXLEN];
 	const struct nb_node *nb_node;
 	const struct lyd_node *dnode;