lib: Optimizing route-maps - Part-1

* This commit introduces the building blocks.
    A per-route-map prefix tree is introduced.
    This tree will consist of the prefixes defined within the prefix-lists
    that are added to the match clause of that route-map.

Signed-off-by: NaveenThanikachalam <nthanikachal@vmware.com>

3 files changed, 835 insertions, 5 deletions

diff --git a/lib/plist.c b/lib/plist.c
index 662221bee..a3b89f5ab 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -303,6 +303,9 @@ static void prefix_list_delete(struct prefix_list *plist)
 
 	/* If prefix-list contain prefix_list_entry free all of it. */
 	for (pentry = plist->head; pentry; pentry = next) {
+		route_map_notify_pentry_dependencies(plist->name,
+						     pentry,
+						     RMAP_EVENT_PLIST_DELETED);
 		next = pentry->next;
 		prefix_list_trie_del(plist, pentry);
 		prefix_list_entry_free(pentry);
@@ -518,6 +521,9 @@ static void prefix_list_entry_delete(struct prefix_list *plist,
 	else
 		plist->tail = pentry->prev;
 
+	route_map_notify_pentry_dependencies(plist->name,
+					     pentry,
+					     RMAP_EVENT_PLIST_DELETED);
 	prefix_list_entry_free(pentry);
 
 	plist->count--;
@@ -631,6 +637,9 @@ static void prefix_list_entry_add(struct prefix_list *plist,
 	/* Increment count. */
 	plist->count++;
 
+	route_map_notify_pentry_dependencies(plist->name, pentry,
+					     RMAP_EVENT_PLIST_ADDED);
+
 	/* Run hook function. */
 	if (plist->master->add_hook)
 		(*plist->master->add_hook)(plist);
diff --git a/lib/routemap.c b/lib/routemap.c
index 0d5621d90..e3d5c9168 100644
--- a/lib/routemap.c
+++ b/lib/routemap.c
@@ -31,6 +31,7 @@
 #include "hash.h"
 #include "libfrr.h"
 #include "lib_errors.h"
+#include "table.h"
 
 DEFINE_MTYPE_STATIC(LIB, ROUTE_MAP, "Route map")
 DEFINE_MTYPE(LIB, ROUTE_MAP_NAME, "Route map name")
@@ -44,12 +45,52 @@ DEFINE_MTYPE_STATIC(LIB, ROUTE_MAP_DEP_DATA, "Route map dependency data")
 DEFINE_QOBJ_TYPE(route_map_index)
 DEFINE_QOBJ_TYPE(route_map)
 
+#define IPv4_PREFIX_LIST "ip address prefix-list"
+#define IPv6_PREFIX_LIST "ipv6 address prefix-list"
+#define IPv4_MATCH_RULE "ip "
+#define IPv6_MATCH_RULE "ipv6 "
+
+struct route_map_pentry_dep {
+	struct prefix_list_entry *pentry;
+	const char *plist_name;
+	route_map_event_t event;
+};
+
 /* Vector for route match rules. */
 static vector route_match_vec;
 
 /* Vector for route set rules. */
 static vector route_set_vec;
 
+static void
+route_map_pfx_tbl_update(route_map_event_t event,
+			 struct route_map_index *index,
+			 afi_t afi,
+			 const char *plist_name);
+static void
+route_map_pfx_table_add_default(afi_t afi,
+				struct route_map_index *index);
+static void
+route_map_pfx_table_del_default(afi_t afi,
+				struct route_map_index *index);
+static void
+route_map_add_plist_entries(afi_t afi,
+			    struct route_map_index *index,
+			    const char *plist_name,
+			    struct prefix_list_entry *entry);
+static void
+route_map_del_plist_entries(afi_t afi,
+			    struct route_map_index *index,
+			    const char *plist_name,
+			    struct prefix_list_entry *entry);
+static bool
+route_map_is_ip_rule_present(struct route_map_index *index);
+static bool
+route_map_is_ipv6_rule_present(struct route_map_index *index);
+
+static struct hash *
+route_map_get_dep_hash(route_map_event_t event);
+
 struct route_map_match_set_hooks rmap_match_set_hook;
 
 /* match interface */
@@ -566,6 +607,12 @@ static struct route_map *route_map_add(const char *name)
 		route_map_notify_dependencies(name, RMAP_EVENT_CALL_ADDED);
 	}
 
+	if (!map->ipv4_prefix_table)
+		map->ipv4_prefix_table = route_table_init();
+
+	if (!map->ipv6_prefix_table)
+		map->ipv6_prefix_table = route_table_init();
+
 	if (rmap_debug)
 		zlog_debug("Add route-map %s", name);
 	return map;
@@ -786,8 +833,9 @@ static void vty_show_route_map_entry(struct vty *vty, struct route_map *map)
 	struct route_map_index *index;
 	struct route_map_rule *rule;
 
-	vty_out(vty, "route-map: %s Invoked: %" PRIu64 "\n",
-		map->name, map->applied - map->applied_clear);
+	vty_out(vty, "route-map: %s Invoked: %" PRIu64 " Optimization: %s\n",
+		map->name, map->applied - map->applied_clear,
+		map->optimization_disabled ? "disabled" : "enabled");
 
 	for (index = map->head; index; index = index->next) {
 		vty_out(vty, " %s, sequence %d Invoked %" PRIu64 "\n",
@@ -927,8 +975,22 @@ void route_map_index_delete(struct route_map_index *index, int notify)
 		routemap_hook_context_free(TAILQ_FIRST(&index->rhclist));
 
 	/* Free route match. */
-	while ((rule = index->match_list.head) != NULL)
+	while ((rule = index->match_list.head) != NULL) {
+		if (strncmp(rule->cmd->str, IPv4_PREFIX_LIST,
+			    strlen(IPv4_PREFIX_LIST)) == 0)
+			route_map_pfx_tbl_update(
+					RMAP_EVENT_PLIST_DELETED,
+					index, AFI_IP,
+					rule->rule_str);
+		else if (strncmp(rule->cmd->str, IPv6_PREFIX_LIST,
+				 strlen(IPv6_PREFIX_LIST)) == 0)
+			route_map_pfx_tbl_update(
+					RMAP_EVENT_PLIST_DELETED,
+					index, AFI_IP6,
+					rule->rule_str);
+
 		route_map_rule_delete(&index->match_list, rule);
+	}
 
 	/* Free route set. */
 	while ((rule = index->set_list.head) != NULL)
@@ -948,6 +1010,9 @@ void route_map_index_delete(struct route_map_index *index, int notify)
 	/* Free 'char *nextrm' if not NULL */
 	XFREE(MTYPE_ROUTE_MAP_NAME, index->nextrm);
 
+	route_map_pfx_tbl_update(RMAP_EVENT_INDEX_DELETED,
+				 index, 0, NULL);
+
 	/* Execute event hook. */
 	if (route_map_master.event_hook && notify) {
 		(*route_map_master.event_hook)(index->map->name);
@@ -1007,6 +1072,9 @@ route_map_index_add(struct route_map *map, enum route_map_type type, int pref)
 		point->prev = index;
 	}
 
+	route_map_pfx_tbl_update(RMAP_EVENT_INDEX_ADDED,
+				 index, 0, NULL);
+
 	/* Execute event hook. */
 	if (route_map_master.event_hook) {
 		(*route_map_master.event_hook)(map->name);
@@ -1254,6 +1322,23 @@ enum rmap_compile_rets route_map_add_match(struct route_map_index *index,
 				return RMAP_COMPILE_SUCCESS;
 			}
 
+			/* If IPv4 or IPv6 prefix-list match criteria
+			 * has been delete to the route-map index, update
+			 * the route-map's prefix table.
+			 */
+			if (strncmp(match_name, IPv4_PREFIX_LIST,
+				    strlen(IPv4_PREFIX_LIST)) == 0)
+				route_map_pfx_tbl_update(
+						RMAP_EVENT_PLIST_DELETED,
+						index, AFI_IP,
+						rule->rule_str);
+			else if (strncmp(match_name, IPv6_PREFIX_LIST,
+					 strlen(IPv6_PREFIX_LIST)) == 0)
+				route_map_pfx_tbl_update(
+						RMAP_EVENT_PLIST_DELETED,
+						index, AFI_IP6,
+						rule->rule_str);
+
 			/* Remove the dependency of the route-map on the rule
 			 * that is being replaced.
 			 */
@@ -1282,6 +1367,46 @@ enum rmap_compile_rets route_map_add_match(struct route_map_index *index,
 	/* Add new route match rule to linked list. */
 	route_map_rule_add(&index->match_list, rule);
 
+	/* If IPv4 or IPv6 prefix-list match criteria
+	 * has been added to the route-map index, update
+	 * the route-map's prefix table.
+	 */
+	if (strncmp(match_name, IPv4_PREFIX_LIST,
+		    strlen(IPv4_PREFIX_LIST)) == 0) {
+		route_map_pfx_tbl_update(RMAP_EVENT_PLIST_ADDED,
+					 index, AFI_IP,
+					 match_arg);
+	} else if (strncmp(match_name, IPv6_PREFIX_LIST,
+			   strlen(IPv6_PREFIX_LIST)) == 0) {
+		route_map_pfx_tbl_update(RMAP_EVENT_PLIST_ADDED,
+					 index, AFI_IP6,
+					 match_arg);
+	} else {
+		/* If IPv4 match criteria has been added to the route-map
+		 * index, check for IPv6 prefix-list match rule presence and
+		 * remove this index from the trie node created for each of the
+		 * prefix-entry within the prefix-list. If no IPv6 prefix-list
+		 * match rule is present, remove this index from the IPv6
+		 * default route's trie node.
+		 */
+		if (strncmp(match_name, IPv4_MATCH_RULE,
+			    strlen(IPv4_MATCH_RULE)) == 0)
+			route_map_del_plist_entries(AFI_IP6, index,
+						    NULL, NULL);
+
+		/* If IPv6 match criteria has been added to the route-map
+		 * index, check for IPv4 prefix-list match rule presence and
+		 * remove this index from the trie node created for each of the
+		 * prefix-entry within the prefix-list. If no IPv4 prefix-list
+		 * match rule is present, remove this index from the IPv4
+		 * default route's trie node.
+		 */
+		else if (strncmp(match_name, IPv6_MATCH_RULE,
+				 strlen(IPv6_MATCH_RULE)) == 0)
+			route_map_del_plist_entries(AFI_IP, index,
+						    NULL, NULL);
+	}
+
 	/* Execute event hook. */
 	if (route_map_master.event_hook) {
 		(*route_map_master.event_hook)(index->map->name);
@@ -1329,6 +1454,51 @@ enum rmap_compile_rets route_map_delete_match(struct route_map_index *index,
 						index->map->name);
 
 			route_map_rule_delete(&index->match_list, rule);
+
+			/* If IPv4 or IPv6 prefix-list match criteria
+			 * has been delete to the route-map index, update
+			 * the route-map's prefix table.
+			 */
+			if (strncmp(match_name, IPv4_PREFIX_LIST,
+				    strlen(IPv4_PREFIX_LIST)) == 0) {
+				route_map_pfx_tbl_update(
+						RMAP_EVENT_PLIST_DELETED,
+						index, AFI_IP,
+						match_arg);
+			} else if (strncmp(match_name, IPv6_PREFIX_LIST,
+					   strlen(IPv6_PREFIX_LIST)) == 0) {
+				route_map_pfx_tbl_update(
+						RMAP_EVENT_PLIST_DELETED,
+						index, AFI_IP6,
+						match_arg);
+			} else {
+				/* If no more IPv4 match rules are present in
+				 * this index, check for IPv6 prefix-list match
+				 * rule presence and add this index to trie node
+				 * created for each of the prefix-entry within
+				 * the prefix-list. If no IPv6 prefix-list match
+				 * rule is present, add this index to the IPv6
+				 * default route's trie node.
+				 */
+				if (!route_map_is_ip_rule_present(index))
+					route_map_add_plist_entries(AFI_IP6,
+								    index, NULL,
+								    NULL);
+
+				/* If no more IPv6 match rules are present in
+				 * this index, check for IPv4 prefix-list match
+				 * rule presence and add this index to trie node
+				 * created for each of the prefix-entry within
+				 * the prefix-list. If no IPv6 prefix-list match
+				 * rule is present, add this index to the IPv4
+				 * default route's trie node.
+				 */
+				if (!route_map_is_ipv6_rule_present(index))
+					route_map_add_plist_entries(AFI_IP,
+								    index, NULL,
+								    NULL);
+			}
+
 			return RMAP_COMPILE_SUCCESS;
 		}
 	/* Can't find matched rule. */
@@ -1494,6 +1664,619 @@ route_map_apply_match(struct route_map_rule_list *match_list,
 	return ret;
 }
 
+static int
+route_map_candidate_list_cmp(struct route_map_index *idx1,
+			     struct route_map_index *idx2)
+{
+	if (!idx1)
+		return -1;
+	if (!idx2)
+		return 1;
+
+	return (idx1->pref - idx2->pref);
+}
+
+/*
+ * This function adds the route-map index into the default route's
+ * route-node in the route-map's IPv4/IPv6 prefix-table.
+ */
+static void
+route_map_pfx_table_add_default(afi_t afi,
+				struct route_map_index *index)
+{
+	struct route_node *rn = NULL;
+	struct list *rmap_candidate_list = NULL;
+	struct prefix p;
+	bool updated_rn = false;
+	struct route_table *table = NULL;
+
+	memset(&p, 0, sizeof(p));
+	p.family = afi2family(afi);
+	p.prefixlen = 0;
+
+	if (p.family == AF_INET) {
+		table = index->map->ipv4_prefix_table;
+		if (!table)
+			index->map->ipv4_prefix_table = route_table_init();
+
+		table = index->map->ipv4_prefix_table;
+	} else {
+		table = index->map->ipv6_prefix_table;
+		if (!table)
+			index->map->ipv6_prefix_table = route_table_init();
+
+		table = index->map->ipv6_prefix_table;
+	}
+
+	/* Add default route to table */
+	rn = route_node_get(table, &p);
+
+	if (!rn)
+		return;
+
+	if (!rn->info) {
+		rmap_candidate_list = list_new();
+		rmap_candidate_list->cmp =
+			(int (*)(void *, void *))route_map_candidate_list_cmp;
+		rn->info = rmap_candidate_list;
+	} else {
+		rmap_candidate_list = (struct list *)rn->info;
+		updated_rn = true;
+	}
+
+	listnode_add_sort_nodup(rmap_candidate_list, index);
+	if (updated_rn)
+		route_unlock_node(rn);
+}
+
+/*
+ * This function removes the route-map index from the default route's
+ * route-node in the route-map's IPv4/IPv6 prefix-table.
+ */
+static void
+route_map_pfx_table_del_default(afi_t afi,
+				struct route_map_index *index)
+{
+	struct route_node *rn = NULL;
+	struct list *rmap_candidate_list = NULL;
+	struct prefix p;
+	struct route_table *table = NULL;
+
+	memset(&p, 0, sizeof(p));
+	p.family = afi2family(afi);
+	p.prefixlen = 0;
+
+	if (p.family == AF_INET)
+		table = index->map->ipv4_prefix_table;
+	else
+		table = index->map->ipv6_prefix_table;
+
+	/* Remove RMAP index from default route in table */
+	rn = route_node_lookup(table, &p);
+	if (!rn || !rn->info)
+		return;
+
+	rmap_candidate_list = (struct list *)rn->info;
+
+	listnode_delete(rmap_candidate_list, index);
+
+	if (listcount(rmap_candidate_list) == 0) {
+		list_delete(&rmap_candidate_list);
+		rn->info = NULL;
+		route_unlock_node(rn);
+	}
+	route_unlock_node(rn);
+}
+
+/*
+ * This function adds the route-map index to the route-node for
+ * the prefix-entry in the route-map's IPv4/IPv6 prefix-table.
+ */
+static void
+route_map_pfx_table_add(struct route_table *table,
+			struct route_map_index *index,
+			struct prefix_list_entry *pentry)
+{
+	struct route_node *rn = NULL;
+	struct list *rmap_candidate_list = NULL;
+	bool updated_rn = false;
+
+	rn = route_node_get(table, &pentry->prefix);
+	if (!rn)
+		return;
+
+	if (!rn->info) {
+		rmap_candidate_list = list_new();
+		rmap_candidate_list->cmp =
+			(int (*)(void *, void *))route_map_candidate_list_cmp;
+		rn->info = rmap_candidate_list;
+	} else {
+		rmap_candidate_list = (struct list *)rn->info;
+		updated_rn = true;
+	}
+
+	listnode_add_sort_nodup(rmap_candidate_list, index);
+	if (updated_rn)
+		route_unlock_node(rn);
+}
+
+/*
+ * This function removes the route-map index from the route-node for
+ * the prefix-entry in the route-map's IPv4/IPv6 prefix-table.
+ */
+static void
+route_map_pfx_table_del(struct route_table *table,
+			struct route_map_index *index,
+			struct prefix_list_entry *pentry)
+{
+	struct route_node *rn = NULL;
+	struct list *rmap_candidate_list = NULL;
+
+	rn = route_node_lookup(table, &pentry->prefix);
+	if (!rn || !rn->info)
+		return;
+
+	rmap_candidate_list = (struct list *)rn->info;
+
+	listnode_delete(rmap_candidate_list, index);
+
+	if (listcount(rmap_candidate_list) == 0) {
+		list_delete(&rmap_candidate_list);
+		rn->info = NULL;
+		route_unlock_node(rn);
+	}
+	route_unlock_node(rn);
+}
+
+/* This function checks for the presence of an IPv4 match rule
+ * in the given route-map index.
+ */
+static bool
+route_map_is_ip_rule_present(struct route_map_index *index)
+{
+	struct route_map_rule_list *match_list = NULL;
+	struct route_map_rule *rule = NULL;
+
+	match_list = &index->match_list;
+	for (rule = match_list->head; rule; rule = rule->next)
+		if (strncmp(rule->cmd->str, IPv4_MATCH_RULE,
+			    strlen(IPv4_MATCH_RULE)) == 0)
+			return true;
+
+	return false;
+}
+
+/* This function checks for the presence of an IPv6 match rule
+ * in the given route-map index.
+ */
+static bool
+route_map_is_ipv6_rule_present(struct route_map_index *index)
+{
+	struct route_map_rule_list *match_list = NULL;
+	struct route_map_rule *rule = NULL;
+
+	match_list = &index->match_list;
+	for (rule = match_list->head; rule; rule = rule->next)
+		if (strncmp(rule->cmd->str, IPv6_MATCH_RULE,
+			    strlen(IPv6_MATCH_RULE)) == 0)
+			return true;
+
+	return false;
+}
+
+/* This function does the following:
+ * 1) If plist_name is not present, search for a IPv4 or IPv6 prefix-list
+ *    match clause (based on the afi passed to this foo) and get the
+ *    prefix-list name.
+ * 2) Look up the prefix-list using the name.
+ * 3) If the prefix-list is not found then, add the index to the IPv4/IPv6
+ *    default-route's node in the trie (based on the afi passed to this foo).
+ * 4) If the prefix-list is found then, remove the index from the IPv4/IPv6
+ *    default-route's node in the trie (based on the afi passed to this foo).
+ * 5) If a prefix-entry is passed then, create a route-node for this entry and
+ *    add this index to the route-node.
+ * 6) If prefix-entry is not passed then, for every prefix-entry in the
+ *    prefix-list, create a route-node for this entry and
+ *    add this index to the route-node.
+ */
+static void
+route_map_add_plist_entries(afi_t afi,
+			    struct route_map_index *index,
+			    const char *plist_name,
+			    struct prefix_list_entry *entry)
+{
+	struct route_map_rule_list *match_list = NULL;
+	struct route_map_rule *match = NULL;
+	struct prefix_list *plist = NULL;
+	struct prefix_list_entry *pentry = NULL;
+	bool plist_rule_is_present = false;
+
+	if (!plist_name) {
+		match_list = &index->match_list;
+
+		for (match = match_list->head; match; match = match->next) {
+			if (strncmp(
+				match->cmd->str,
+				(afi == AFI_IP) ? IPv4_PREFIX_LIST :
+						  IPv6_PREFIX_LIST,
+				strlen((afi == AFI_IP) ?
+					IPv4_PREFIX_LIST : IPv6_PREFIX_LIST))
+					== 0) {
+				plist_rule_is_present = true;
+				break;
+			}
+		}
+
+		if (plist_rule_is_present)
+			plist = prefix_list_lookup(afi, match->rule_str);
+	} else {
+		plist = prefix_list_lookup(afi, plist_name);
+	}
+
+	if (!plist) {
+		route_map_pfx_table_add_default(afi, index);
+		return;
+	}
+
+	route_map_pfx_table_del_default(afi, index);
+
+	if (entry) {
+		if (afi == AFI_IP) {
+			route_map_pfx_table_add(
+					index->map->ipv4_prefix_table,
+					index, entry);
+		} else {
+			route_map_pfx_table_add(
+					index->map->ipv6_prefix_table,
+					index, entry);
+		}
+	} else {
+		for (pentry = plist->head; pentry; pentry = pentry->next) {
+			if (afi == AFI_IP) {
+				route_map_pfx_table_add(
+						index->map->ipv4_prefix_table,
+						index, pentry);
+			} else {
+				route_map_pfx_table_add(
+						index->map->ipv6_prefix_table,
+						index, pentry);
+			}
+		}
+	}
+}
+
+/* This function does the following:
+ * 1) If plist_name is not present, search for a IPv4 or IPv6 prefix-list
+ *    match clause (based on the afi passed to this foo) and get the
+ *    prefix-list name.
+ * 2) Look up the prefix-list using the name.
+ * 3) If the prefix-list is not found then, delete the index from the IPv4/IPv6
+ *    default-route's node in the trie (based on the afi passed to this foo).
+ * 4) If a prefix-entry is passed then, remove this index from the route-node
+ *    for the prefix in this prefix-entry.
+ * 5) If prefix-entry is not passed then, for every prefix-entry in the
+ *    prefix-list, remove this index from the route-node
+ *    for the prefix in this prefix-entry.
+ */
+static void
+route_map_del_plist_entries(afi_t afi,
+			    struct route_map_index *index,
+			    const char *plist_name,
+			    struct prefix_list_entry *entry)
+{
+	struct route_map_rule_list *match_list = NULL;
+	struct route_map_rule *match = NULL;
+	struct prefix_list *plist = NULL;
+	struct prefix_list_entry *pentry = NULL;
+	bool plist_rule_is_present = false;
+
+	if (!plist_name) {
+		match_list = &index->match_list;
+
+		for (match = match_list->head; match; match = match->next) {
+			if (strncmp(
+				match->cmd->str,
+				(afi == AFI_IP) ? IPv4_PREFIX_LIST :
+						  IPv6_PREFIX_LIST,
+				strlen((afi == AFI_IP) ?
+					IPv4_PREFIX_LIST : IPv6_PREFIX_LIST))
+					== 0) {
+				plist_rule_is_present = true;
+				break;
+			}
+		}
+
+		if (plist_rule_is_present)
+			plist = prefix_list_lookup(afi, match->rule_str);
+	} else {
+		plist = prefix_list_lookup(afi, plist_name);
+	}
+
+	if (!plist) {
+		route_map_pfx_table_del_default(afi, index);
+		return;
+	}
+
+	if (entry) {
+		if (afi == AFI_IP) {
+			route_map_pfx_table_del(
+					index->map->ipv4_prefix_table,
+					index, entry);
+		} else {
+			route_map_pfx_table_del(
+					index->map->ipv6_prefix_table,
+					index, entry);
+		}
+	} else {
+		for (pentry = plist->head; pentry; pentry = pentry->next) {
+			if (afi == AFI_IP) {
+				route_map_pfx_table_del(
+						index->map->ipv4_prefix_table,
+						index, pentry);
+			} else {
+				route_map_pfx_table_del(
+						index->map->ipv6_prefix_table,
+						index, pentry);
+			}
+		}
+	}
+}
+
+/*
+ * This function handles the cases where a prefix-list is added/removed
+ * as a match command from a particular route-map index.
+ * It updates the prefix-table of the route-map accordingly.
+ */
+static void
+route_map_trie_update(afi_t afi,
+		      route_map_event_t event,
+		      struct route_map_index *index,
+		      const char *plist_name)
+{
+	if (event == RMAP_EVENT_PLIST_ADDED) {
+		if (afi == AFI_IP) {
+			if (!route_map_is_ipv6_rule_present(index)) {
+				route_map_pfx_table_del_default(AFI_IP6,
+								index);
+				route_map_add_plist_entries(afi, index,
+							    plist_name, NULL);
+			} else {
+				route_map_del_plist_entries(AFI_IP6, index,
+							    NULL, NULL);
+			}
+		} else {
+			if (!route_map_is_ip_rule_present(index)) {
+				route_map_pfx_table_del_default(AFI_IP,
+								index);
+				route_map_add_plist_entries(afi, index,
+							    plist_name, NULL);
+			} else {
+				route_map_del_plist_entries(AFI_IP, index,
+							    NULL, NULL);
+			}
+		}
+	} else if (event == RMAP_EVENT_PLIST_DELETED) {
+		if (afi == AFI_IP) {
+			route_map_del_plist_entries(afi, index,
+						    plist_name, NULL);
+
+			if (!route_map_is_ipv6_rule_present(index))
+				route_map_pfx_table_add_default(afi, index);
+
+			if (!route_map_is_ip_rule_present(index))
+				route_map_add_plist_entries(AFI_IP6,
+							    index,
+							    NULL, NULL);
+		} else {
+			route_map_del_plist_entries(afi, index,
+						    plist_name, NULL);
+
+			if (!route_map_is_ip_rule_present(index))
+				route_map_pfx_table_add_default(afi, index);
+
+			if (!route_map_is_ipv6_rule_present(index))
+				route_map_add_plist_entries(AFI_IP,
+							    index,
+							    NULL, NULL);
+		}
+	}
+}
+
+/*
+ * This function handles the cases where a route-map index and
+ * prefix-list is added/removed.
+ * It updates the prefix-table of the route-map accordingly.
+ */
+static void
+route_map_pfx_tbl_update(route_map_event_t event,
+			 struct route_map_index *index,
+			 afi_t afi,
+			 const char *plist_name)
+{
+	struct route_map *rmap = NULL;
+
+	if (!index)
+		return;
+
+	if (event == RMAP_EVENT_INDEX_ADDED) {
+		route_map_pfx_table_add_default(AFI_IP, index);
+		route_map_pfx_table_add_default(AFI_IP6, index);
+		return;
+	}
+
+	if (event == RMAP_EVENT_INDEX_DELETED) {
+		route_map_pfx_table_del_default(AFI_IP, index);
+		route_map_pfx_table_del_default(AFI_IP6, index);
+
+		if ((index->map->head == NULL) &&
+		    (index->map->tail == NULL)) {
+			rmap = index->map;
+
+			if (rmap->ipv4_prefix_table) {
+				route_table_finish(rmap->ipv4_prefix_table);
+				rmap->ipv4_prefix_table = NULL;
+			}
+
+			if (rmap->ipv6_prefix_table) {
+				route_table_finish(rmap->ipv6_prefix_table);
+				rmap->ipv6_prefix_table = NULL;
+			}
+		}
+		return;
+	}
+
+	/* Handle prefix-list match rule addition/deletion.
+	 */
+	route_map_trie_update(afi, event,
+			      index, plist_name);
+}
+
+/*
+ * This function handles the cases where a new prefix-entry is added to
+ * a prefix-list or, an existing prefix-entry is removed from the prefix-list.
+ * It updates the prefix-table of the route-map accordingly.
+ */
+static void
+route_map_pentry_update(route_map_event_t event,
+			const char *plist_name,
+			struct route_map_index *index,
+			struct prefix_list_entry *pentry)
+{
+	struct prefix_list *plist = NULL;
+	afi_t afi;
+	unsigned char family = pentry->prefix.family;
+
+	if (family == AF_INET) {
+		afi = AFI_IP;
+		plist = prefix_list_lookup(AFI_IP, plist_name);
+	} else {
+		afi = AFI_IP6;
+		plist = prefix_list_lookup(AFI_IP6, plist_name);
+	}
+
+	if (event == RMAP_EVENT_PLIST_ADDED) {
+		if (plist->count == 1) {
+			if (afi == AFI_IP) {
+				if (!route_map_is_ipv6_rule_present(index))
+					route_map_add_plist_entries(afi, index,
+								    plist_name,
+								    pentry);
+			} else {
+				if (!route_map_is_ip_rule_present(index))
+					route_map_add_plist_entries(afi, index,
+								    plist_name,
+								    pentry);
+			}
+		} else {
+			route_map_add_plist_entries(afi, index,
+						    plist_name, pentry);
+		}
+	} else if (event == RMAP_EVENT_PLIST_DELETED) {
+		route_map_del_plist_entries(afi, index, plist_name, pentry);
+
+		if (plist->count == 1) {
+			if (afi == AFI_IP) {
+				if (!route_map_is_ipv6_rule_present(index))
+					route_map_pfx_table_add_default(afi,
+									index);
+			} else {
+				if (!route_map_is_ip_rule_present(index))
+					route_map_pfx_table_add_default(afi,
+									index);
+			}
+		}
+	}
+}
+
+static void
+route_map_pentry_process_dependency(struct hash_backet *backet,
+				    void *data)
+{
+	char *rmap_name = NULL;
+	struct route_map *rmap = NULL;
+	struct route_map_index *index = NULL;
+	struct route_map_rule_list *match_list = NULL;
+	struct route_map_rule *match = NULL;
+	struct route_map_dep_data *dep_data = NULL;
+	struct route_map_pentry_dep *pentry_dep =
+				(struct route_map_pentry_dep *)data;
+	unsigned char family = pentry_dep->pentry->prefix.family;
+
+	dep_data = (struct route_map_dep_data *)backet->data;
+	if (!dep_data)
+		return;
+
+	rmap_name = dep_data->rname;
+	rmap = route_map_lookup_by_name(rmap_name);
+	if (!rmap || !rmap->head)
+		return;
+
+	for (index = rmap->head; index; index = index->next) {
+		match_list = &index->match_list;
+
+		if (!match_list)
+			continue;
+
+		for (match = match_list->head; match; match = match->next) {
+			if (strcmp(match->rule_str, pentry_dep->plist_name)
+									== 0) {
+				if ((strncmp(match->cmd->str, IPv4_PREFIX_LIST,
+					     strlen(IPv4_PREFIX_LIST)) == 0) &&
+				    family == AF_INET) {
+					route_map_pentry_update(
+							pentry_dep->event,
+							pentry_dep->plist_name,
+							index,
+							pentry_dep->pentry);
+				} else if ((strncmp(match->cmd->str,
+						    IPv6_PREFIX_LIST,
+						    strlen(IPv6_PREFIX_LIST))
+					   == 0) &&
+					   family == AF_INET6) {
+					route_map_pentry_update(
+							pentry_dep->event,
+							pentry_dep->plist_name,
+							index,
+							pentry_dep->pentry);
+				}
+			}
+		}
+	}
+}
+
+void
+route_map_notify_pentry_dependencies(const char *affected_name,
+				     struct prefix_list_entry *pentry,
+				     route_map_event_t event)
+{
+	struct route_map_dep *dep = NULL;
+	struct hash *upd8_hash = NULL;
+	struct route_map_pentry_dep pentry_dep;
+
+	if (!affected_name || !pentry)
+		return;
+
+	upd8_hash = route_map_get_dep_hash(event);
+	if (!upd8_hash)
+		return;
+
+	dep = (struct route_map_dep *)hash_get(upd8_hash, (void *)affected_name,
+					       NULL);
+	if (dep) {
+		if (!dep->this_hash)
+			dep->this_hash = upd8_hash;
+
+		memset(&pentry_dep, 0, sizeof(struct route_map_pentry_dep));
+		pentry_dep.pentry = pentry;
+		pentry_dep.plist_name = affected_name;
+		pentry_dep.event = event;
+
+		hash_iterate(dep->dep_rmap_hash,
+			     route_map_pentry_process_dependency,
+			     (void *)&pentry_dep);
+	}
+}
+
 /* Apply route map's each index to the object.
 
    The matrix for a route-map looks like this:
@@ -2025,8 +2808,31 @@ void route_map_notify_dependencies(const char *affected_name,
 	XFREE(MTYPE_ROUTE_MAP_NAME, name);
 }
 
+DEFUN (no_routemap_optimization,
+       no_routemap_optimization_cmd,
+       "no route-map optimization",
+       NO_STR
+       "route-map\n"
+       "optimization\n")
+{
+	VTY_DECLVAR_CONTEXT(route_map_index, index);
+
+	index->map->optimization_disabled = true;
+	return CMD_SUCCESS;
+}
+
+DEFUN (routemap_optimization,
+       routemap_optimization_cmd,
+       "route-map optimization",
+       "route-map\n"
+       "optimization\n")
+{
+	VTY_DECLVAR_CONTEXT(route_map_index, index);
+
+	index->map->optimization_disabled = false;
+	return CMD_SUCCESS;
+}
 
-/* VTY related functions. */
 static void clear_route_map_helper(struct route_map *map)
 {
 	struct route_map_index *index;
@@ -2237,4 +3043,7 @@ void route_map_init(void)
 
 	install_element(ENABLE_NODE, &debug_rmap_cmd);
 	install_element(ENABLE_NODE, &no_debug_rmap_cmd);
+
+	install_element(RMAP_NODE, &routemap_optimization_cmd);
+	install_element(RMAP_NODE, &no_routemap_optimization_cmd);
 }
diff --git a/lib/routemap.h b/lib/routemap.h
index 05c958967..c9adfb420 100644
--- a/lib/routemap.h
+++ b/lib/routemap.h
@@ -25,6 +25,8 @@
 #include "memory.h"
 #include "qobj.h"
 #include "vty.h"
+#include "lib/plist.h"
+#include "lib/plist_int.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -220,6 +222,7 @@ struct route_map {
 	/* Maintain update info */
 	bool to_be_processed; /* True if modification isn't acted on yet */
 	bool deleted;         /* If 1, then this node will be deleted */
+	bool optimization_disabled;
 
 	/* How many times have we applied this route-map */
 	uint64_t applied;
@@ -228,6 +231,12 @@ struct route_map {
 	/* Counter to track active usage of this route-map */
 	uint16_t use_count;
 
+	/* Tables to maintain IPv4 and IPv6 prefixes from
+	 * the prefix-list match clause.
+	 */
+	struct route_table *ipv4_prefix_table;
+	struct route_table *ipv6_prefix_table;
+
 	QOBJ_FIELDS
 };
 DECLARE_QOBJ_TYPE(route_map)
@@ -310,7 +319,10 @@ extern void route_map_upd8_dependency(route_map_event_t type, const char *arg,
 				      const char *rmap_name);
 extern void route_map_notify_dependencies(const char *affected_name,
 					  route_map_event_t event);
-
+extern void route_map_notify_pentry_dependencies(
+					const char *affected_name,
+					struct prefix_list_entry *pentry,
+					route_map_event_t event);
 extern int generic_match_add(struct vty *vty, struct route_map_index *index,
 			     const char *command, const char *arg,
 			     route_map_event_t type);