From ac64b71b2893341b2e342865c209ee63c2dc3138 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Mon, 8 Oct 2018 14:51:11 +0000 Subject: Sticky Load-balance keep the number of buckets in the load-balanced fixed. If a path goes dwon fill its buckets with those from the next available up path. Change-Id: I15603ccb899fa9b77556b898c99136379cf32eae Signed-off-by: Neale Ranns --- src/vnet/fib/fib_path.c | 17 ++- src/vnet/fib/fib_path_list.c | 29 +++- src/vnet/fib/fib_path_list.h | 1 + src/vnet/fib/fib_test.c | 336 ++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 367 insertions(+), 16 deletions(-) (limited to 'src/vnet/fib') diff --git a/src/vnet/fib/fib_path.c b/src/vnet/fib/fib_path.c index 4c93f732b72..4ec04f5b950 100644 --- a/src/vnet/fib/fib_path.c +++ b/src/vnet/fib/fib_path.c @@ -2521,15 +2521,20 @@ fib_path_append_nh_for_multipath_hash (fib_node_index_t path_index, ASSERT(path); + vec_add2(hash_key, mnh, 1); + + mnh->path_weight = path->fp_weight; + mnh->path_index = path_index; + if (fib_path_is_resolved(path_index)) { - vec_add2(hash_key, mnh, 1); - - mnh->path_weight = path->fp_weight; - mnh->path_index = path_index; - fib_path_contribute_forwarding(path_index, fct, &mnh->path_dpo); + fib_path_contribute_forwarding(path_index, fct, &mnh->path_dpo); + } + else + { + dpo_copy(&mnh->path_dpo, + drop_dpo_get(fib_forw_chain_type_to_dpo_proto(fct))); } - return (hash_key); } diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c index 8aee5aaa18a..d830eaa3667 100644 --- a/src/vnet/fib/fib_path_list.c +++ b/src/vnet/fib/fib_path_list.c @@ -340,6 +340,18 @@ fib_path_list_last_lock_gone (fib_node_t *node) fib_path_list_destroy(path_list); } +static load_balance_flags_t +fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags) +{ + load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE; + + if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY) + { + lb_flags |= LOAD_BALANCE_ATTR_STICKY; + } + return (lb_flags); +} + /* * fib_path_mk_lb * @@ -349,7 +361,8 @@ fib_path_list_last_lock_gone (fib_node_t *node) static void fib_path_list_mk_lb (fib_path_list_t *path_list, fib_forward_chain_type_t fct, - dpo_id_t *dpo) + dpo_id_t *dpo, + fib_path_list_fwd_flags_t flags) { load_balance_path_t *nhs; fib_node_index_t *path_index; @@ -361,9 +374,12 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, */ vec_foreach (path_index, path_list->fpl_paths) { - nhs = fib_path_append_nh_for_multipath_hash(*path_index, - fct, - nhs); + if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) || + fib_path_is_resolved(*path_index)) + { + nhs = fib_path_append_nh_for_multipath_hash(*path_index, + fct, nhs); + } } /* @@ -376,7 +392,8 @@ fib_path_list_mk_lb (fib_path_list_t *path_list, load_balance_create(vec_len(nhs), fib_forw_chain_type_to_dpo_proto(fct), 0 /* FIXME FLOW HASH */)); - load_balance_multipath_update(dpo, nhs, LOAD_BALANCE_FLAG_NONE); + load_balance_multipath_update(dpo, nhs, + fib_path_list_fwd_flags_2_load_balance(flags)); FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index); @@ -1144,7 +1161,7 @@ fib_path_list_contribute_forwarding (fib_node_index_t path_list_index, path_list = fib_path_list_get(path_list_index); - fib_path_list_mk_lb(path_list, fct, dpo); + fib_path_list_mk_lb(path_list, fct, dpo, flags); ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type); diff --git a/src/vnet/fib/fib_path_list.h b/src/vnet/fib/fib_path_list.h index 76870dc6c78..18835a60282 100644 --- a/src/vnet/fib/fib_path_list.h +++ b/src/vnet/fib/fib_path_list.h @@ -134,6 +134,7 @@ typedef enum fib_path_list_fwd_flags_t_ { FIB_PATH_LIST_FWD_FLAG_NONE = 0, FIB_PATH_LIST_FWD_FLAG_COLLAPSE = (1 << 0), + FIB_PATH_LIST_FWD_FLAG_STICKY = (1 << 1), } fib_path_list_fwd_flags_t; extern void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, diff --git a/src/vnet/fib/fib_test.c b/src/vnet/fib/fib_test.c index 112709e7cfe..492369c3540 100644 --- a/src/vnet/fib/fib_test.c +++ b/src/vnet/fib/fib_test.c @@ -640,9 +640,9 @@ fib_test_validate_lb (const dpo_id_t *dpo, res = 0; va_start(ap, n_buckets); - if (FIB_TEST_I((DPO_LOAD_BALANCE == dpo->dpoi_type), - "Entry links to %U", - format_dpo_type, dpo->dpoi_type)) + if (!FIB_TEST_I((DPO_LOAD_BALANCE == dpo->dpoi_type), + "Entry links to %U", + format_dpo_type, dpo->dpoi_type)) { lb = load_balance_get(dpo->dpoi_index); @@ -650,7 +650,7 @@ fib_test_validate_lb (const dpo_id_t *dpo, } else { - res = 0; + res = 1; } va_end(ap); @@ -10118,6 +10118,330 @@ fib_test_inherit (void) return (res); } +static int +fib_test_sticky (void) +{ + fib_route_path_t *r_paths = NULL; + test_main_t *tm = &test_main; + u32 ii, lb_count, pl_count; + dpo_id_t dpo = DPO_INVALID; + fib_node_index_t pl_index; + int res = 0; +#define N_PATHS 16 + + fib_test_lb_bucket_t buckets[N_PATHS]; + bfd_session_t bfds[N_PATHS] = {{0}}; + + lb_count = pool_elts(load_balance_pool); + pl_count = fib_path_list_pool_size(); + + for (ii = 0; ii < N_PATHS; ii++) + { + ip46_address_t nh = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a02 + ii), + }; + adj_index_t ai; + + ai = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4, + VNET_LINK_IP4, + &nh, tm->hw[0]->sw_if_index); + + buckets[ii].type = FT_LB_ADJ; + buckets[ii].adj.adj = ai; + + bfds[ii].udp.key.peer_addr = nh; + bfds[ii].udp.key.sw_if_index = tm->hw[0]->sw_if_index; + bfds[ii].hop_type = BFD_HOP_TYPE_SINGLE; + bfds[ii].local_state = BFD_STATE_init; + adj_bfd_notify(BFD_LISTEN_EVENT_CREATE, &bfds[ii]); + bfds[ii].local_state = BFD_STATE_up; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[ii]); + } + + for (ii = 0; ii < N_PATHS; ii++) + { + fib_route_path_t r_path = { + .frp_proto = DPO_PROTO_IP4, + .frp_addr = { + .ip4.as_u32 = clib_host_to_net_u32(0x0a0a0a02 + ii), + }, + .frp_sw_if_index = tm->hw[0]->sw_if_index, + .frp_weight = 1, + .frp_fib_index = ~0, + }; + vec_add1(r_paths, r_path); + }; + + pl_index = fib_path_list_create(FIB_PATH_LIST_FLAG_SHARED, r_paths); + fib_path_list_lock(pl_index); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[0], + &buckets[1], + &buckets[2], + &buckets[3], + &buckets[4], + &buckets[5], + &buckets[6], + &buckets[7], + &buckets[8], + &buckets[9], + &buckets[10], + &buckets[11], + &buckets[12], + &buckets[13], + &buckets[14], + &buckets[15]), + "Setup OK"); + + /* take down paths */ + bfds[0].local_state = BFD_STATE_down; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[0]); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[1], + &buckets[1], + &buckets[2], + &buckets[3], + &buckets[4], + &buckets[5], + &buckets[6], + &buckets[7], + &buckets[8], + &buckets[9], + &buckets[10], + &buckets[11], + &buckets[12], + &buckets[13], + &buckets[14], + &buckets[15]), + "Failed at shut-down path 0"); + + bfds[7].local_state = BFD_STATE_down; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[7]); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[1], + &buckets[1], + &buckets[2], + &buckets[3], + &buckets[4], + &buckets[5], + &buckets[6], + &buckets[2], + &buckets[8], + &buckets[9], + &buckets[10], + &buckets[11], + &buckets[12], + &buckets[13], + &buckets[14], + &buckets[15]), + "Failed at shut-down path 7"); + + /* paths back up */ + bfds[0].local_state = BFD_STATE_up; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[0]); + bfds[7].local_state = BFD_STATE_up; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[7]); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[0], + &buckets[1], + &buckets[2], + &buckets[3], + &buckets[4], + &buckets[5], + &buckets[6], + &buckets[7], + &buckets[8], + &buckets[9], + &buckets[10], + &buckets[11], + &buckets[12], + &buckets[13], + &buckets[14], + &buckets[15]), + "recovery OK"); + + fib_path_list_unlock(pl_index); + + /* + * non-power of 2 number of buckets + */ + fib_route_path_t *r_paths2 = NULL; + + r_paths2 = vec_dup(r_paths); + _vec_len(r_paths2) = 3; + + pl_index = fib_path_list_create(FIB_PATH_LIST_FLAG_SHARED, r_paths2); + fib_path_list_lock(pl_index); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[1], + &buckets[1], + &buckets[1], + &buckets[1], + &buckets[1], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[2]), + "non-power of 2"); + + bfds[1].local_state = BFD_STATE_down; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[1]); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + /* + * path 1's buckets alternate between path 0 and 2 + */ + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[2], + &buckets[0], + &buckets[2], + &buckets[0], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[2]), + "non-power of 2"); + bfds[1].local_state = BFD_STATE_up; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[1]); + + fib_path_list_unlock(pl_index); + + /* + * unequal cost + */ + fib_route_path_t *r_paths3 = NULL; + + r_paths3 = vec_dup(r_paths); + _vec_len(r_paths3) = 3; + + r_paths3[0].frp_weight = 3; + + pl_index = fib_path_list_create(FIB_PATH_LIST_FLAG_SHARED, r_paths3); + fib_path_list_lock(pl_index); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[1], + &buckets[1], + &buckets[1], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0]), + "UCMP"); + + bfds[1].local_state = BFD_STATE_down; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[1]); + + fib_path_list_contribute_forwarding(pl_index, + FIB_FORW_CHAIN_TYPE_UNICAST_IP4, + FIB_PATH_LIST_FWD_FLAG_STICKY, + &dpo); + /* No attempt to Un-equal distribute the down path's buckets */ + FIB_TEST(!fib_test_validate_lb(&dpo, + 16, + &buckets[2], + &buckets[0], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[2], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0], + &buckets[0]), + "UCMP"); + bfds[1].local_state = BFD_STATE_up; + adj_bfd_notify(BFD_LISTEN_EVENT_UPDATE, &bfds[1]); + + dpo_reset(&dpo); + fib_path_list_unlock(pl_index); + + vec_free(r_paths); + vec_free(r_paths2); + vec_free(r_paths3); + + FIB_TEST(lb_count == pool_elts(load_balance_pool), "no leaked LBs"); + FIB_TEST(pl_count == fib_path_list_pool_size(), "no leaked PLs"); + + return 0; +} + static clib_error_t * fib_test (vlib_main_t * vm, unformat_input_t * input, @@ -10175,6 +10499,10 @@ fib_test (vlib_main_t * vm, { res += fib_test_inherit(); } + else if (unformat (input, "sticky")) + { + res += fib_test_sticky(); + } else { res += fib_test_v4(); -- cgit 1.2.3-korg