lib: rework management of user pointers in the northbound layer

Introduce a hash table to keep track of user pointers associated
to configuration entries. The previous strategy was to embed
the user pointers inside libyang data nodes, but this solution
incurred a substantial performance overhead. The user pointers
embedded in candidate configurations could be lost while the
configuration was being edited, so they needed to be regenerated
before the candidate could be committed.  This was done by the
nb_candidate_restore_priv_pointers() function, which was extremely
expensive for large configurations. The new hash table solves this
performance problem.

The yang_dnode_[gs]et_entry() functions were renamed and moved from
yang.[ch] to northbound.[ch], which is a more appropriate place
for them. This patch also introduces the nb_running_unset_entry()
function, the counterpart of nb_running_set_entry() (unsetting
user pointers was done automatically before, now it needs to be
done manually).

As a consequence of these changes, we shouldn't need support for
libyang private pointers anymore (-DENABLE_LYD_PRIV=ON). But it's
probably a good idea to keep requiring this feature as we might
need it in the future for other things (e.g. disable configuration
settings without removing them).

Fixes #4136.

Signed-off-by: Renato Westphal <renato@opensourcerouting.org>

5 files changed, 194 insertions, 125 deletions

diff --git a/lib/if.c b/lib/if.c
index a31b44c7d5..2eb8a448f2 100644
--- a/lib/if.c
+++ b/lib/if.c
@@ -1303,7 +1303,7 @@ static int lib_interface_create(enum nb_event event,
 #else
 		ifp = if_get_by_name(ifname, vrf->vrf_id);
 #endif /* SUNOS_5 */
-		yang_dnode_set_entry(dnode, ifp);
+		nb_running_set_entry(dnode, ifp);
 		break;
 	}
 
@@ -1315,10 +1315,10 @@ static int lib_interface_destroy(enum nb_event event,
 {
 	struct interface *ifp;
 
-	ifp = yang_dnode_get_entry(dnode, true);
 
 	switch (event) {
 	case NB_EV_VALIDATE:
+		ifp = nb_running_get_entry(dnode, NULL, true);
 		if (CHECK_FLAG(ifp->status, ZEBRA_INTERFACE_ACTIVE)) {
 			zlog_warn("%s: only inactive interfaces can be deleted",
 				  __func__);
@@ -1329,6 +1329,7 @@ static int lib_interface_destroy(enum nb_event event,
 	case NB_EV_ABORT:
 		break;
 	case NB_EV_APPLY:
+		ifp = nb_running_unset_entry(dnode);
 		if_delete(ifp);
 		break;
 	}
@@ -1349,7 +1350,7 @@ static int lib_interface_description_modify(enum nb_event event,
 	if (event != NB_EV_APPLY)
 		return NB_OK;
 
-	ifp = yang_dnode_get_entry(dnode, true);
+	ifp = nb_running_get_entry(dnode, NULL, true);
 	XFREE(MTYPE_TMP, ifp->desc);
 	description = yang_dnode_get_string(dnode, NULL);
 	ifp->desc = XSTRDUP(MTYPE_TMP, description);
@@ -1365,7 +1366,7 @@ static int lib_interface_description_destroy(enum nb_event event,
 	if (event != NB_EV_APPLY)
 		return NB_OK;
 
-	ifp = yang_dnode_get_entry(dnode, true);
+	ifp = nb_running_get_entry(dnode, NULL, true);
 	XFREE(MTYPE_TMP, ifp->desc);
 
 	return NB_OK;
diff --git a/lib/northbound.c b/lib/northbound.c
index 9deb9c6cce..fb782bf1bd 100644
--- a/lib/northbound.c
+++ b/lib/northbound.c
@@ -22,6 +22,7 @@
 #include "libfrr.h"
 #include "log.h"
 #include "lib_errors.h"
+#include "hash.h"
 #include "command.h"
 #include "debug.h"
 #include "db.h"
@@ -31,10 +32,14 @@
 
 DEFINE_MTYPE_STATIC(LIB, NB_NODE, "Northbound Node")
 DEFINE_MTYPE_STATIC(LIB, NB_CONFIG, "Northbound Configuration")
+DEFINE_MTYPE_STATIC(LIB, NB_CONFIG_ENTRY, "Northbound Configuration Entry")
 
 /* Running configuration - shouldn't be modified directly. */
 struct nb_config *running_config;
 
+/* Hash table of user pointers associated with configuration entries. */
+static struct hash *running_config_entries;
+
 /*
  * Global lock used to prevent multiple configuration transactions from
  * happening concurrently.
@@ -535,38 +540,6 @@ int nb_candidate_update(struct nb_config *candidate)
 }
 
 /*
- * The northbound configuration callbacks use the 'priv' pointer present in the
- * libyang lyd_node structure to store pointers to FRR internal variables
- * associated to YANG lists and presence containers. Before commiting a
- * candidate configuration, we must restore the 'priv' pointers stored in the
- * running configuration since they might be lost while editing the candidate.
- */
-static void nb_candidate_restore_priv_pointers(struct nb_config *candidate)
-{
-	struct lyd_node *root, *next, *dnode_iter;
-
-	LY_TREE_FOR (running_config->dnode, root) {
-		LY_TREE_DFS_BEGIN (root, next, dnode_iter) {
-			struct lyd_node *dnode_candidate;
-			char xpath[XPATH_MAXLEN];
-
-			if (!dnode_iter->priv)
-				goto next;
-
-			yang_dnode_get_path(dnode_iter, xpath, sizeof(xpath));
-			dnode_candidate =
-				yang_dnode_get(candidate->dnode, xpath);
-			if (dnode_candidate)
-				yang_dnode_set_entry(dnode_candidate,
-						     dnode_iter->priv);
-
-		next:
-			LY_TREE_DFS_END(root, next, dnode_iter);
-		}
-	}
-}
-
-/*
  * Perform YANG syntactic and semantic validation.
  *
  * WARNING: lyd_validate() can change the configuration as part of the
@@ -588,7 +561,6 @@ static int nb_candidate_validate_changes(struct nb_config *candidate,
 {
 	struct nb_config_cb *cb;
 
-	nb_candidate_restore_priv_pointers(candidate);
 	RB_FOREACH (cb, nb_config_cbs, changes) {
 		struct nb_config_change *change = (struct nb_config_change *)cb;
 		int ret;
@@ -1548,6 +1520,116 @@ int nb_notification_send(const char *xpath, struct list *arguments)
 	return ret;
 }
 
+/* Running configuration user pointers management. */
+struct nb_config_entry {
+	char xpath[XPATH_MAXLEN];
+	void *entry;
+};
+
+static bool running_config_entry_cmp(const void *value1, const void *value2)
+{
+	const struct nb_config_entry *c1 = value1;
+	const struct nb_config_entry *c2 = value2;
+
+	return strmatch(c1->xpath, c2->xpath);
+}
+
+static unsigned int running_config_entry_key_make(void *value)
+{
+	return string_hash_make(value);
+}
+
+static void *running_config_entry_alloc(void *p)
+{
+	struct nb_config_entry *new, *key = p;
+
+	new = XCALLOC(MTYPE_NB_CONFIG_ENTRY, sizeof(*new));
+	strlcpy(new->xpath, key->xpath, sizeof(new->xpath));
+
+	return new;
+}
+
+static void running_config_entry_free(void *arg)
+{
+	XFREE(MTYPE_NB_CONFIG_ENTRY, arg);
+}
+
+void nb_running_set_entry(const struct lyd_node *dnode, void *entry)
+{
+	struct nb_config_entry *config, s;
+
+	yang_dnode_get_path(dnode, s.xpath, sizeof(s.xpath));
+	config = hash_get(running_config_entries, &s,
+			  running_config_entry_alloc);
+	config->entry = entry;
+}
+
+static void *nb_running_unset_entry_helper(const struct lyd_node *dnode)
+{
+	struct nb_config_entry *config, s;
+	struct lyd_node *child;
+	void *entry = NULL;
+
+	yang_dnode_get_path(dnode, s.xpath, sizeof(s.xpath));
+	config = hash_release(running_config_entries, &s);
+	if (config) {
+		entry = config->entry;
+		running_config_entry_free(config);
+	}
+
+	/* Unset user pointers from the child nodes. */
+	if (CHECK_FLAG(dnode->schema->nodetype, LYS_LIST | LYS_CONTAINER)) {
+		LY_TREE_FOR (dnode->child, child) {
+			(void)nb_running_unset_entry_helper(child);
+		}
+	}
+
+	return entry;
+}
+
+void *nb_running_unset_entry(const struct lyd_node *dnode)
+{
+	void *entry;
+
+	entry = nb_running_unset_entry_helper(dnode);
+	assert(entry);
+
+	return entry;
+}
+
+void *nb_running_get_entry(const struct lyd_node *dnode, const char *xpath,
+			   bool abort_if_not_found)
+{
+	const struct lyd_node *orig_dnode = dnode;
+	char xpath_buf[XPATH_MAXLEN];
+
+	assert(dnode || xpath);
+
+	if (!dnode)
+		dnode = yang_dnode_get(running_config->dnode, xpath);
+
+	while (dnode) {
+		struct nb_config_entry *config, s;
+
+		yang_dnode_get_path(dnode, s.xpath, sizeof(s.xpath));
+		config = hash_lookup(running_config_entries, &s);
+		if (config)
+			return config->entry;
+
+		dnode = dnode->parent;
+	}
+
+	if (!abort_if_not_found)
+		return NULL;
+
+	yang_dnode_get_path(orig_dnode, xpath_buf, sizeof(xpath_buf));
+	flog_err(EC_LIB_YANG_DNODE_NOT_FOUND,
+		 "%s: failed to find entry [xpath %s]", __func__, xpath_buf);
+	zlog_backtrace(LOG_ERR);
+	abort();
+}
+
+/* Logging functions. */
 const char *nb_event_name(enum nb_event event)
 {
 	switch (event) {
@@ -1685,6 +1767,9 @@ void nb_init(struct thread_master *tm,
 
 	/* Create an empty running configuration. */
 	running_config = nb_config_new(NULL);
+	running_config_entries = hash_create(running_config_entry_key_make,
+					     running_config_entry_cmp,
+					     "Running Configuration Entries");
 
 	/* Initialize the northbound CLI. */
 	nb_cli_init(tm);
@@ -1699,5 +1784,7 @@ void nb_terminate(void)
 	nb_nodes_delete();
 
 	/* Delete the running configuration. */
+	hash_clean(running_config_entries, running_config_entry_free);
+	hash_free(running_config_entries);
 	nb_config_free(running_config);
 }
diff --git a/lib/northbound.h b/lib/northbound.h
index bfa28b3f65..14f27c1d41 100644
--- a/lib/northbound.h
+++ b/lib/northbound.h
@@ -808,6 +808,75 @@ extern bool nb_operation_is_valid(enum nb_operation operation,
 extern int nb_notification_send(const char *xpath, struct list *arguments);
 
 /*
+ * Associate a user pointer to a configuration node.
+ *
+ * This should be called by northbound 'create' callbacks in the NB_EV_APPLY
+ * phase only.
+ *
+ * dnode
+ *    libyang data node - only its XPath is used.
+ *
+ * entry
+ *    Arbitrary user-specified pointer.
+ */
+extern void nb_running_set_entry(const struct lyd_node *dnode, void *entry);
+
+/*
+ * Unset the user pointer associated to a configuration node.
+ *
+ * This should be called by northbound 'destroy' callbacks in the NB_EV_APPLY
+ * phase only.
+ *
+ * dnode
+ *    libyang data node - only its XPath is used.
+ *
+ * Returns:
+ *    The user pointer that was unset.
+ */
+extern void *nb_running_unset_entry(const struct lyd_node *dnode);
+
+/*
+ * Find the user pointer (if any) associated to a configuration node.
+ *
+ * The XPath associated to the configuration node can be provided directly or
+ * indirectly through a libyang data node.
+ *
+ * If an user point is not found, this function follows the parent nodes in the
+ * running configuration until an user pointer is found or until the root node
+ * is reached.
+ *
+ * dnode
+ *    libyang data node - only its XPath is used (can be NULL if 'xpath' is
+ *    provided).
+ *
+ * xpath
+ *    XPath of the configuration node (can be NULL if 'dnode' is provided).
+ *
+ * abort_if_not_found
+ *    When set to true, abort the program if no user pointer is found.
+ *
+ *    As a rule of thumb, this parameter should be set to true in the following
+ *    scenarios:
+ *    - Calling this function from any northbound configuration callback during
+ *      the NB_EV_APPLY phase.
+ *    - Calling this function from a 'delete' northbound configuration callback
+ *      during any phase.
+ *
+ *    In both the above cases, the given configuration node should contain an
+ *    user pointer except when there's a bug in the code, in which case it's
+ *    better to abort the program right away and eliminate the need for
+ *    unnecessary NULL checks.
+ *
+ *    In all other cases, this parameter should be set to false and the caller
+ *    should check if the function returned NULL or not.
+ *
+ * Returns:
+ *    User pointer if found, NULL otherwise.
+ */
+extern void *nb_running_get_entry(const struct lyd_node *dnode, const char *xpath,
+				  bool abort_if_not_found);
+
+/*
  * Return a human-readable string representing a northbound event.
  *
  * event
diff --git a/lib/yang.c b/lib/yang.c
index 7982d14fdd..b7b001b7c3 100644
--- a/lib/yang.c
+++ b/lib/yang.c
@@ -513,42 +513,6 @@ void yang_dnode_change_leaf(struct lyd_node *dnode, const char *value)
 	lyd_change_leaf((struct lyd_node_leaf_list *)dnode, value);
 }
 
-void yang_dnode_set_entry(const struct lyd_node *dnode, void *entry)
-{
-	assert(CHECK_FLAG(dnode->schema->nodetype, LYS_LIST | LYS_CONTAINER));
-	lyd_set_private(dnode, entry);
-}
-
-void *yang_dnode_get_entry(const struct lyd_node *dnode,
-			   bool abort_if_not_found)
-{
-	const struct lyd_node *orig_dnode = dnode;
-	char xpath[XPATH_MAXLEN];
-
-	while (dnode) {
-		switch (dnode->schema->nodetype) {
-		case LYS_CONTAINER:
-		case LYS_LIST:
-			if (dnode->priv)
-				return dnode->priv;
-			break;
-		default:
-			break;
-		}
-
-		dnode = dnode->parent;
-	}
-
-	if (!abort_if_not_found)
-		return NULL;
-
-	yang_dnode_get_path(orig_dnode, xpath, sizeof(xpath));
-	flog_err(EC_LIB_YANG_DNODE_NOT_FOUND,
-		 "%s: failed to find entry [xpath %s]", __func__, xpath);
-	zlog_backtrace(LOG_ERR);
-	abort();
-}
-
 struct lyd_node *yang_dnode_new(struct ly_ctx *ly_ctx, bool config_only)
 {
 	struct lyd_node *dnode;
@@ -629,12 +593,6 @@ struct yang_data *yang_data_list_find(const struct list *list,
 	return NULL;
 }
 
-static void *ly_dup_cb(const void *priv)
-{
-	/* Make a shallow copy of the priv pointer. */
-	return (void *)priv;
-}
-
 /* Make libyang log its errors using FRR logging infrastructure. */
 static void ly_log_cb(LY_LOG_LEVEL level, const char *msg, const char *path)
 {
@@ -724,7 +682,6 @@ CPP_NOTICE("lib/yang: deprecated libyang <0.16.74 extension loading in use!")
 		flog_err(EC_LIB_LIBYANG, "%s: ly_ctx_new() failed", __func__);
 		exit(1);
 	}
-	ly_ctx_set_priv_dup_clb(ly_native_ctx, ly_dup_cb);
 
 #ifndef LIBYANG_EXT_BUILTIN
 	/* Detect if the required libyang plugin(s) were loaded successfully. */
diff --git a/lib/yang.h b/lib/yang.h
index 15f0ec7ae6..6f8c84ab64 100644
--- a/lib/yang.h
+++ b/lib/yang.h
@@ -403,51 +403,6 @@ extern bool yang_dnode_is_default_recursive(const struct lyd_node *dnode);
 extern void yang_dnode_change_leaf(struct lyd_node *dnode, const char *value);
 
 /*
- * Set the libyang private pointer to a user pointer. Can only be used on YANG
- * lists and containers.
- *
- * dnode
- *    libyang data node to operate on.
- *
- * entry
- *    Arbitrary user-specified pointer.
- */
-extern void yang_dnode_set_entry(const struct lyd_node *dnode, void *entry);
-
-/*
- * Find the user pointer associated to the given libyang data node.
- *
- * The data node is traversed by following the parent pointers until an user
- * pointer is found or until the root node is reached.
- *
- * dnode
- *    libyang data node to operate on.
- *
- * abort_if_not_found
- *    When set to true, abort the program if no user pointer is found.
- *
- *    As a rule of thumb, this parameter should be set to true in the following
- *    scenarios:
- *    - Calling this function from any northbound configuration callback during
- *      the NB_EV_APPLY phase.
- *    - Calling this function from a 'delete' northbound configuration callback
- *      during any phase.
- *
- *    In both the above cases, the libyang data node should contain an user
- *    pointer except when there's a bug in the code, in which case it's better
- *    to abort the program right away and eliminate the need for unnecessary
- *    NULL checks.
- *
- *    In all other cases, this parameter should be set to false and the caller
- *    should check if the function returned NULL or not.
- *
- * Returns:
- *    User pointer if found, NULL otherwise.
- */
-extern void *yang_dnode_get_entry(const struct lyd_node *dnode,
-				  bool abort_if_not_found);
-
-/*
  * Create a new libyang data node.
  *
  * ly_ctx