bgpd: Cleanup multipath figuring out in bgp

Currently bgp multipath has these properties:

a) mp_info may or may not be on a single path, based
upon path perturbations in the past.
b) mp_info->count started counting at 0( meaning 1 ).  As that the
bestpath path_info was never included in the count
c) The first mp_info in the list held the multipath data associated
with the multipath.  As such if you were at any other node that data
was not filled in.
d) As such the mp_info's that are not first on the list basically
were just pointers to the corresponding bgp_path_info that was in
the multipath.
e) On bestpath calculation, a linklist(struct linklist *) of bgp_path_info's was
created.
f) This linklist was passed in to a comparison function that took the
old mpinfo list and compared it item by item to the linklist and
doing magic to figure out how to create a new mp_info list.
g) the old mp_info and the link list had to be memory managed and
freed up.
h) BGP_PATH_MULTIPATH is only set on non bestpath nodes in the
multipath.

This is really complicated.  Let's change the algorithm to this:

a) When running bestpath, mark a bgp_path_info node that could be in the ecmp path as
BGP_PATH_MULTIPATH_NEW.
b) When running multipath, just walk the list of bgp_path_info's and if
it has BGP_PATH_MULTIPATH_NEW on it, decide if it is in BGP_MULTIPATH.
If we run out of space to put in the ecmp, clear the flag on the rest.
c) Clean up the counting of sometimes adding 1 to the mpath count.
d) Only allocate a mpath_info node for the bestpath.  Clean it up
when done with it.
e) remove the unneeded list management associated with the linklist and
the mp_list.

This greatly simplifies multipath computation for bgp and reduces memory
load for large scale deployments.

2 full feeds in work_queue_run prior:

    0      56367.471      1123    50193    493695    50362    493791         0         0          0    TE   work_queue_run

BGP multipath info            :  1941844     48   110780992  1941844 110780992

2 full feeds in work_queue_run after change:

    1      52924.931      1296    40837    465968    41025    487390         0         0          1    TE   work_queue_run

BGP multipath info            :   970860     32    38836880   970866  38837120

Aproximately 4 seconds of saved cpu time for convergence and ~75 mb
smaller run time.

Signed-off-by: Donald Sharp <sharpd@nvidia.com>

3 files changed, 0 insertions, 503 deletions

diff --git a/tests/bgpd/subdir.am b/tests/bgpd/subdir.am
index 5148e7e440..97845ec1aa 100644
--- a/tests/bgpd/subdir.am
+++ b/tests/bgpd/subdir.am
@@ -52,17 +52,6 @@ tests_bgpd_test_mp_attr_LDADD = $(BGP_TEST_LDADD)
 tests_bgpd_test_mp_attr_SOURCES = tests/bgpd/test_mp_attr.c
 EXTRA_DIST += tests/bgpd/test_mp_attr.py
 
-
-if BGPD
-check_PROGRAMS += tests/bgpd/test_mpath
-endif
-tests_bgpd_test_mpath_CFLAGS = $(TESTS_CFLAGS)
-tests_bgpd_test_mpath_CPPFLAGS = $(TESTS_CPPFLAGS)
-tests_bgpd_test_mpath_LDADD = $(BGP_TEST_LDADD)
-tests_bgpd_test_mpath_SOURCES = tests/bgpd/test_mpath.c
-EXTRA_DIST += tests/bgpd/test_mpath.py
-
-
 if BGPD
 check_PROGRAMS += tests/bgpd/test_packet
 endif
diff --git a/tests/bgpd/test_mpath.c b/tests/bgpd/test_mpath.c
deleted file mode 100644
index ebbe3ac3e2..0000000000
--- a/tests/bgpd/test_mpath.c
+++ /dev/null
@@ -1,482 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0-or-later
-/*
- * BGP Multipath Unit Test
- * Copyright (C) 2010 Google Inc.
- *
- * This file is part of Quagga
- */
-
-#include <zebra.h>
-
-#include "qobj.h"
-#include "vty.h"
-#include "stream.h"
-#include "privs.h"
-#include "linklist.h"
-#include "memory.h"
-#include "zclient.h"
-#include "queue.h"
-#include "filter.h"
-
-#include "bgpd/bgpd.h"
-#include "bgpd/bgp_table.h"
-#include "bgpd/bgp_route.h"
-#include "bgpd/bgp_attr.h"
-#include "bgpd/bgp_nexthop.h"
-#include "bgpd/bgp_mpath.h"
-#include "bgpd/bgp_evpn.h"
-#include "bgpd/bgp_network.h"
-
-#define VT100_RESET "\x1b[0m"
-#define VT100_RED "\x1b[31m"
-#define VT100_GREEN "\x1b[32m"
-#define VT100_YELLOW "\x1b[33m"
-#define OK VT100_GREEN "OK" VT100_RESET
-#define FAILED VT100_RED "failed" VT100_RESET
-
-#define TEST_PASSED 0
-#define TEST_FAILED -1
-
-#define EXPECT_TRUE(expr, res)                                                 \
-	if (!(expr)) {                                                         \
-		printf("Test failure in %s line %u: %s\n", __func__, __LINE__, \
-		       #expr);                                                 \
-		(res) = TEST_FAILED;                                           \
-	}
-
-typedef struct testcase_t__ testcase_t;
-
-typedef int (*test_setup_func)(testcase_t *);
-typedef int (*test_run_func)(testcase_t *);
-typedef int (*test_cleanup_func)(testcase_t *);
-
-struct testcase_t__ {
-	const char *desc;
-	void *test_data;
-	void *verify_data;
-	void *tmp_data;
-	test_setup_func setup;
-	test_run_func run;
-	test_cleanup_func cleanup;
-};
-
-/* need these to link in libbgp */
-struct event_loop *master = NULL;
-extern struct zclient *zclient;
-struct zebra_privs_t bgpd_privs = {
-	.user = NULL,
-	.group = NULL,
-	.vty_group = NULL,
-};
-
-static int tty = 0;
-
-/* Create fake bgp instance */
-static struct bgp *bgp_create_fake(as_t *as, const char *name)
-{
-	struct bgp *bgp;
-	afi_t afi;
-	safi_t safi;
-
-	if ((bgp = XCALLOC(MTYPE_BGP, sizeof(struct bgp))) == NULL)
-		return NULL;
-
-	bgp_lock(bgp);
-	// bgp->peer_self = peer_new (bgp);
-	// bgp->peer_self->host = XSTRDUP (MTYPE_BGP_PEER_HOST, "Static
-	// announcement");
-
-	bgp->peer = list_new();
-	// bgp->peer->cmp = (int (*)(void *, void *)) peer_cmp;
-
-	bgp->group = list_new();
-	// bgp->group->cmp = (int (*)(void *, void *)) peer_group_cmp;
-
-	bgp_evpn_init(bgp);
-	FOREACH_AFI_SAFI (afi, safi) {
-		bgp->route[afi][safi] = bgp_table_init(bgp, afi, safi);
-		bgp->aggregate[afi][safi] = bgp_table_init(bgp, afi, safi);
-		bgp->rib[afi][safi] = bgp_table_init(bgp, afi, safi);
-		bgp->maxpaths[afi][safi].maxpaths_ebgp = MULTIPATH_NUM;
-		bgp->maxpaths[afi][safi].maxpaths_ibgp = MULTIPATH_NUM;
-	}
-
-	bgp_scan_init(bgp);
-	bgp->default_local_pref = BGP_DEFAULT_LOCAL_PREF;
-	bgp->default_holdtime = BGP_DEFAULT_HOLDTIME;
-	bgp->default_keepalive = BGP_DEFAULT_KEEPALIVE;
-	bgp->restart_time = BGP_DEFAULT_RESTART_TIME;
-	bgp->stalepath_time = BGP_DEFAULT_STALEPATH_TIME;
-
-	bgp->as = *as;
-
-	if (name)
-		bgp->name = strdup(name);
-
-	return bgp;
-}
-
-/*=========================================================
- * Testcase for maximum-paths configuration
- */
-static int setup_bgp_cfg_maximum_paths(testcase_t *t)
-{
-	as_t asn = 1;
-	t->tmp_data = bgp_create_fake(&asn, NULL);
-	if (!t->tmp_data)
-		return -1;
-	return 0;
-}
-
-static int run_bgp_cfg_maximum_paths(testcase_t *t)
-{
-	afi_t afi;
-	safi_t safi;
-	struct bgp *bgp;
-	int api_result;
-	int test_result = TEST_PASSED;
-
-	bgp = t->tmp_data;
-	FOREACH_AFI_SAFI (afi, safi) {
-		/* test bgp_maximum_paths_set */
-		api_result = bgp_maximum_paths_set(bgp, afi, safi,
-						   BGP_PEER_EBGP, 10, 0);
-		EXPECT_TRUE(api_result == 0, test_result);
-		api_result = bgp_maximum_paths_set(bgp, afi, safi,
-						   BGP_PEER_IBGP, 10, 0);
-		EXPECT_TRUE(api_result == 0, test_result);
-		EXPECT_TRUE(bgp->maxpaths[afi][safi].maxpaths_ebgp == 10,
-			    test_result);
-		EXPECT_TRUE(bgp->maxpaths[afi][safi].maxpaths_ibgp == 10,
-			    test_result);
-
-		/* test bgp_maximum_paths_unset */
-		api_result =
-			bgp_maximum_paths_unset(bgp, afi, safi, BGP_PEER_EBGP);
-		EXPECT_TRUE(api_result == 0, test_result);
-		api_result =
-			bgp_maximum_paths_unset(bgp, afi, safi, BGP_PEER_IBGP);
-		EXPECT_TRUE(api_result == 0, test_result);
-		EXPECT_TRUE((bgp->maxpaths[afi][safi].maxpaths_ebgp
-			     == MULTIPATH_NUM),
-			    test_result);
-		EXPECT_TRUE((bgp->maxpaths[afi][safi].maxpaths_ibgp
-			     == MULTIPATH_NUM),
-			    test_result);
-	}
-
-	return test_result;
-}
-
-static int cleanup_bgp_cfg_maximum_paths(testcase_t *t)
-{
-	return bgp_delete((struct bgp *)t->tmp_data);
-}
-
-testcase_t test_bgp_cfg_maximum_paths = {
-	.desc = "Test bgp maximum-paths config",
-	.setup = setup_bgp_cfg_maximum_paths,
-	.run = run_bgp_cfg_maximum_paths,
-	.cleanup = cleanup_bgp_cfg_maximum_paths,
-};
-
-/*=========================================================
- * Testcase for bgp_mp_list
- */
-struct peer test_mp_list_peer[] = {
-	{.local_as = 1, .as = 2}, {.local_as = 1, .as = 2},
-	{.local_as = 1, .as = 2}, {.local_as = 1, .as = 2},
-	{.local_as = 1, .as = 2},
-};
-int test_mp_list_peer_count = array_size(test_mp_list_peer);
-struct attr test_mp_list_attr[4];
-struct bgp_path_info test_mp_list_info[] = {
-	{.peer = &test_mp_list_peer[0], .attr = &test_mp_list_attr[0]},
-	{.peer = &test_mp_list_peer[1], .attr = &test_mp_list_attr[1]},
-	{.peer = &test_mp_list_peer[2], .attr = &test_mp_list_attr[1]},
-	{.peer = &test_mp_list_peer[3], .attr = &test_mp_list_attr[2]},
-	{.peer = &test_mp_list_peer[4], .attr = &test_mp_list_attr[3]},
-};
-int test_mp_list_info_count = array_size(test_mp_list_info);
-
-static int setup_bgp_mp_list(testcase_t *t)
-{
-	test_mp_list_attr[0].nexthop.s_addr = 0x01010101;
-	test_mp_list_attr[1].nexthop.s_addr = 0x02020202;
-	test_mp_list_attr[2].nexthop.s_addr = 0x03030303;
-	test_mp_list_attr[3].nexthop.s_addr = 0x04040404;
-
-	if ((test_mp_list_peer[0].su_remote = sockunion_str2su("1.1.1.1"))
-	    == NULL)
-		return -1;
-	if ((test_mp_list_peer[1].su_remote = sockunion_str2su("2.2.2.2"))
-	    == NULL)
-		return -1;
-	if ((test_mp_list_peer[2].su_remote = sockunion_str2su("3.3.3.3"))
-	    == NULL)
-		return -1;
-	if ((test_mp_list_peer[3].su_remote = sockunion_str2su("4.4.4.4"))
-	    == NULL)
-		return -1;
-	if ((test_mp_list_peer[4].su_remote = sockunion_str2su("5.5.5.5"))
-	    == NULL)
-		return -1;
-
-	return 0;
-}
-
-static int run_bgp_mp_list(testcase_t *t)
-{
-	struct list mp_list;
-	struct listnode *mp_node;
-	struct bgp_path_info *info;
-	int i;
-	int test_result = TEST_PASSED;
-	bgp_mp_list_init(&mp_list);
-	EXPECT_TRUE(listcount(&mp_list) == 0, test_result);
-
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[1]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[4]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[2]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[3]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[0]);
-
-	for (i = 0, mp_node = mp_list.head; i < test_mp_list_info_count;
-	     i++, mp_node = listnextnode(mp_node)) {
-		info = listgetdata(mp_node);
-		info->lock++;
-		EXPECT_TRUE(info == &test_mp_list_info[i], test_result);
-	}
-
-	bgp_mp_list_clear(&mp_list);
-	EXPECT_TRUE(listcount(&mp_list) == 0, test_result);
-
-	return test_result;
-}
-
-static int cleanup_bgp_mp_list(testcase_t *t)
-{
-	int i;
-
-	for (i = 0; i < test_mp_list_peer_count; i++)
-		sockunion_free(test_mp_list_peer[i].su_remote);
-
-	return 0;
-}
-
-testcase_t test_bgp_mp_list = {
-	.desc = "Test bgp_mp_list",
-	.setup = setup_bgp_mp_list,
-	.run = run_bgp_mp_list,
-	.cleanup = cleanup_bgp_mp_list,
-};
-
-/*=========================================================
- * Testcase for bgp_path_info_mpath_update
- */
-
-static struct bgp_dest *dest;
-
-static int setup_bgp_path_info_mpath_update(testcase_t *t)
-{
-	int i;
-	struct bgp *bgp;
-	struct bgp_table *rt;
-	struct prefix p;
-	as_t asn = 1;
-
-	t->tmp_data = bgp_create_fake(&asn, NULL);
-	if (!t->tmp_data)
-		return -1;
-
-	bgp = t->tmp_data;
-	rt = bgp->rib[AFI_IP][SAFI_UNICAST];
-
-	if (!rt)
-		return -1;
-
-	str2prefix("42.1.1.0/24", &p);
-	dest = bgp_node_get(rt, &p);
-
-	setup_bgp_mp_list(t);
-	for (i = 0; i < test_mp_list_info_count; i++)
-		bgp_path_info_add(dest, &test_mp_list_info[i]);
-	return 0;
-}
-
-static int run_bgp_path_info_mpath_update(testcase_t *t)
-{
-	struct bgp_path_info *new_best, *old_best, *mpath;
-	struct list mp_list;
-	struct bgp_maxpaths_cfg mp_cfg = {3, 3};
-
-	int test_result = TEST_PASSED;
-	bgp_mp_list_init(&mp_list);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[4]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[3]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[0]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[1]);
-	new_best = &test_mp_list_info[3];
-	old_best = NULL;
-	bgp_path_info_mpath_update(NULL, dest, new_best, old_best, &mp_list,
-				   &mp_cfg);
-	bgp_mp_list_clear(&mp_list);
-	EXPECT_TRUE(bgp_path_info_mpath_count(new_best) == 2, test_result);
-	mpath = bgp_path_info_mpath_first(new_best);
-	EXPECT_TRUE(mpath == &test_mp_list_info[0], test_result);
-	EXPECT_TRUE(CHECK_FLAG(mpath->flags, BGP_PATH_MULTIPATH), test_result);
-	mpath = bgp_path_info_mpath_next(mpath);
-	EXPECT_TRUE(mpath == &test_mp_list_info[1], test_result);
-	EXPECT_TRUE(CHECK_FLAG(mpath->flags, BGP_PATH_MULTIPATH), test_result);
-
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[0]);
-	bgp_mp_list_add(&mp_list, &test_mp_list_info[1]);
-	new_best = &test_mp_list_info[0];
-	old_best = &test_mp_list_info[3];
-	bgp_path_info_mpath_update(NULL, dest, new_best, old_best, &mp_list,
-				   &mp_cfg);
-	bgp_mp_list_clear(&mp_list);
-	EXPECT_TRUE(bgp_path_info_mpath_count(new_best) == 1, test_result);
-	mpath = bgp_path_info_mpath_first(new_best);
-	EXPECT_TRUE(mpath == &test_mp_list_info[1], test_result);
-	EXPECT_TRUE(CHECK_FLAG(mpath->flags, BGP_PATH_MULTIPATH), test_result);
-	EXPECT_TRUE(!CHECK_FLAG(test_mp_list_info[0].flags, BGP_PATH_MULTIPATH),
-		    test_result);
-
-	return test_result;
-}
-
-static int cleanup_bgp_path_info_mpath_update(testcase_t *t)
-{
-	int i;
-
-	for (i = 0; i < test_mp_list_peer_count; i++)
-		sockunion_free(test_mp_list_peer[i].su_remote);
-
-	return bgp_delete((struct bgp *)t->tmp_data);
-}
-
-testcase_t test_bgp_path_info_mpath_update = {
-	.desc = "Test bgp_path_info_mpath_update",
-	.setup = setup_bgp_path_info_mpath_update,
-	.run = run_bgp_path_info_mpath_update,
-	.cleanup = cleanup_bgp_path_info_mpath_update,
-};
-
-/*=========================================================
- * Set up testcase vector
- */
-testcase_t *all_tests[] = {
-	&test_bgp_cfg_maximum_paths, &test_bgp_mp_list,
-	&test_bgp_path_info_mpath_update,
-};
-
-int all_tests_count = array_size(all_tests);
-
-/*=========================================================
- * Test Driver Functions
- */
-static int global_test_init(void)
-{
-	qobj_init();
-	master = event_master_create(NULL);
-	zclient = zclient_new(master, &zclient_options_default, NULL, 0);
-	bgp_master_init(master, BGP_SOCKET_SNDBUF_SIZE, list_new());
-	vrf_init(NULL, NULL, NULL, NULL);
-	bgp_option_set(BGP_OPT_NO_LISTEN);
-
-	if (fileno(stdout) >= 0)
-		tty = isatty(fileno(stdout));
-	return 0;
-}
-
-static int global_test_cleanup(void)
-{
-	if (zclient != NULL)
-		zclient_free(zclient);
-	event_master_free(master);
-	return 0;
-}
-
-static void display_result(testcase_t *test, int result)
-{
-	if (tty)
-		printf("%s: %s\n", test->desc,
-		       result == TEST_PASSED ? OK : FAILED);
-	else
-		printf("%s: %s\n", test->desc,
-		       result == TEST_PASSED ? "OK" : "FAILED");
-}
-
-static int setup_test(testcase_t *t)
-{
-	int res = 0;
-	if (t->setup)
-		res = t->setup(t);
-	return res;
-}
-
-static int cleanup_test(testcase_t *t)
-{
-	int res = 0;
-	if (t->cleanup)
-		res = t->cleanup(t);
-	return res;
-}
-
-static void run_tests(testcase_t *tests[], int num_tests, int *pass_count,
-		      int *fail_count)
-{
-	int test_index, result;
-	testcase_t *cur_test;
-
-	*pass_count = *fail_count = 0;
-
-	for (test_index = 0; test_index < num_tests; test_index++) {
-		cur_test = tests[test_index];
-		if (!cur_test->desc) {
-			printf("error: test %d has no description!\n",
-			       test_index);
-			continue;
-		}
-		if (!cur_test->run) {
-			printf("error: test %s has no run function!\n",
-			       cur_test->desc);
-			continue;
-		}
-		if (setup_test(cur_test) != 0) {
-			printf("error: setup failed for test %s\n",
-			       cur_test->desc);
-			continue;
-		}
-		result = cur_test->run(cur_test);
-		if (result == TEST_PASSED)
-			*pass_count += 1;
-		else
-			*fail_count += 1;
-		display_result(cur_test, result);
-		if (cleanup_test(cur_test) != 0) {
-			printf("error: cleanup failed for test %s\n",
-			       cur_test->desc);
-			continue;
-		}
-	}
-}
-
-int main(void)
-{
-	int pass_count, fail_count;
-	time_t cur_time;
-	char buf[32];
-
-	time(&cur_time);
-	printf("BGP Multipath Tests Run at %s", ctime_r(&cur_time, buf));
-	if (global_test_init() != 0) {
-		printf("Global init failed. Terminating.\n");
-		exit(1);
-	}
-	run_tests(all_tests, all_tests_count, &pass_count, &fail_count);
-	global_test_cleanup();
-	printf("Total pass/fail: %d/%d\n", pass_count, fail_count);
-	return fail_count;
-}
diff --git a/tests/bgpd/test_mpath.py b/tests/bgpd/test_mpath.py
deleted file mode 100644
index 582fd25c20..0000000000
--- a/tests/bgpd/test_mpath.py
+++ /dev/null
@@ -1,10 +0,0 @@
-import frrtest
-
-
-class TestMpath(frrtest.TestMultiOut):
-    program = "./test_mpath"
-
-
-TestMpath.okfail("bgp maximum-paths config")
-TestMpath.okfail("bgp_mp_list")
-TestMpath.okfail("bgp_path_info_mpath_update")