src/vnet/bier/bier_fmask.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
[gerrit]
host=gerrit.fd.io
port=29418
project=csit.git
/*
 * Copyright (c) 2016 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
#include <vnet/fib/fib_walk.h>
#include <vnet/fib/fib_path_list.h>

#include <vnet/bier/bier_table.h>
#include <vnet/bier/bier_fmask.h>
#include <vnet/bier/bier_bit_string.h>
#include <vnet/bier/bier_disp_table.h>

#include <vnet/mpls/mpls.h>
#include <vnet/dpo/drop_dpo.h>
#include <vnet/dpo/load_balance.h>

/*
 * attributes names for formatting
 */
static const char *const bier_fmask_attr_names[] = BIER_FMASK_ATTR_NAMES;

/*
 * pool of BIER fmask objects
 */
bier_fmask_t *bier_fmask_pool;

/**
 * Stats for each BIER fmask object
 */
vlib_combined_counter_main_t bier_fmask_counters;

static inline index_t
bier_fmask_get_index (const bier_fmask_t *bfm)
{
    return (bfm - bier_fmask_pool);
}

static void
bier_fmask_bits_init (bier_fmask_bits_t *bits,
                      bier_hdr_len_id_t hlid)
{
    bits->bfmb_refs = clib_mem_alloc(sizeof(bits->bfmb_refs[0]) *
                                     bier_hdr_len_id_to_num_bits(hlid));
    clib_memset(bits->bfmb_refs,
           0,
           (sizeof(bits->bfmb_refs[0]) *
            bier_hdr_len_id_to_num_bits(hlid)));

    bits->bfmb_input_reset_string.bbs_len =
        bier_hdr_len_id_to_num_buckets(hlid);

    /*
     * The buckets are accessed in the switch path
     */
    bits->bfmb_input_reset_string.bbs_buckets =
        clib_mem_alloc_aligned(
            sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
            bier_hdr_len_id_to_num_buckets(hlid),
            CLIB_CACHE_LINE_BYTES);
    clib_memset(bits->bfmb_input_reset_string.bbs_buckets,
           0,
           sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
           bier_hdr_len_id_to_num_buckets(hlid));
}

static void
bier_fmask_stack (bier_fmask_t *bfm)
{
    dpo_id_t via_dpo = DPO_INVALID;
    fib_forward_chain_type_t fct;

    if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
    {
        fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
    }
    else
    {
        fct = FIB_FORW_CHAIN_TYPE_BIER;
    }

    fib_path_list_contribute_forwarding(bfm->bfm_pl, fct,
                                        FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
                                        &via_dpo);

    /*
     * If the via PL entry provides no forwarding (i.e. a drop)
     * then neither does this fmask. That way children consider this fmask
     * unresolved and other ECMP options are used instead.
     */
    if (dpo_is_drop(&via_dpo))
    {
        bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING;
    }
    else
    {
        bfm->bfm_flags |= BIER_FMASK_FLAG_FORWARDING;
    }

    dpo_stack(DPO_BIER_FMASK,
              DPO_PROTO_BIER,
              &bfm->bfm_dpo,
              &via_dpo);
    dpo_reset(&via_dpo);
}

void
bier_fmask_contribute_forwarding (index_t bfmi,
                                  dpo_id_t *dpo)
{
    bier_fmask_t *bfm;

    bfm = bier_fmask_get(bfmi);

    if (bfm->bfm_flags & BIER_FMASK_FLAG_FORWARDING)
    {
        dpo_set(dpo,
                DPO_BIER_FMASK,
                DPO_PROTO_BIER,
                bfmi);
    }
    else
    {
        dpo_copy(dpo, drop_dpo_get(DPO_PROTO_BIER));
    }
}

u32
bier_fmask_child_add (fib_node_index_t bfmi,
                     fib_node_type_t child_type,
                     fib_node_index_t child_index)
{
    return (fib_node_child_add(FIB_NODE_TYPE_BIER_FMASK,
                               bfmi,
                               child_type,
                               child_index));
};

void
bier_fmask_child_remove (fib_node_index_t bfmi,
                         u32 sibling_index)
{
    if (INDEX_INVALID == bfmi)
    {
        return;
    }

    fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK,
                          bfmi,
                          sibling_index);
}

static void
bier_fmask_init (bier_fmask_t *bfm,
                 const bier_fmask_id_t *fmid,
                 const fib_route_path_t *rpath)
{
    const bier_table_id_t *btid;
    fib_route_path_t *rpaths;
    mpls_label_t olabel;

    clib_memset(bfm, 0, sizeof(*bfm));
    
    bfm->bfm_id = clib_mem_alloc(sizeof(*bfm->bfm_id));

    fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK);
    *bfm->bfm_id = *fmid;
    dpo_reset(&bfm->bfm_dpo);
    btid = bier_table_get_id(bfm->bfm_id->bfmi_bti);
    bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len);

    if (rpath->frp_flags & FIB_ROUTE_PATH_UDP_ENCAP)
    {
        bfm->bfm_id->bfmi_nh_type = BIER_NH_UDP;
    }
    else if (ip46_address_is_zero(&(bfm->bfm_id->bfmi_nh)))
    {
        bfm->bfm_flags |= BIER_FMASK_FLAG_DISP;
    }

    if (!(bfm->bfm_flags & BIER_FMASK_FLAG_DISP))
    {
        if (NULL != rpath->frp_label_stack)
        {
            olabel = rpath->frp_label_stack[0].fml_value;
            vnet_mpls_uc_set_label(&bfm->bfm_label, olabel);
            vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
            vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
            vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
            bfm->bfm_flags |= BIER_FMASK_FLAG_MPLS;
        }
        else
        {
            bier_bift_id_t id;

            /*
             * not an MPLS label
             */
            bfm->bfm_flags &= ~BIER_FMASK_FLAG_MPLS;

            /*
             * use a label as encoded for BIFT value
             */
            id = bier_bift_id_encode(btid->bti_set,
                                     btid->bti_sub_domain,
                                     btid->bti_hdr_len);
            vnet_mpls_uc_set_label(&bfm->bfm_label, id);
            vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
            vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
            vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
        }
        bfm->bfm_label = clib_host_to_net_u32(bfm->bfm_label);
    }

    rpaths = NULL;
    vec_add1(rpaths, *rpath);
    bfm->bfm_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
                                        FIB_PATH_LIST_FLAG_NO_URPF),
                                       rpaths);
    bfm->bfm_sibling = fib_path_list_child_add(bfm->bfm_pl,
                                               FIB_NODE_TYPE_BIER_FMASK,
                                               bier_fmask_get_index(bfm));
    vec_free(rpaths);
    bier_fmask_stack(bfm);
}

static void
bier_fmask_destroy (bier_fmask_t *bfm)
{
    clib_mem_free(bfm->bfm_bits.bfmb_refs);
    clib_mem_free(bfm->bfm_bits.bfmb_input_reset_string.bbs_buckets);

    bier_fmask_db_remove(bfm->bfm_id);
    fib_path_list_child_remove(bfm->bfm_pl,
                               bfm->bfm_sibling);
    dpo_reset(&bfm->bfm_dpo);
    clib_mem_free(bfm->bfm_id);
    pool_put(bier_fmask_pool, bfm);
}

void
bier_fmask_unlock (index_t bfmi)
{
    bier_fmask_t *bfm;

    if (INDEX_INVALID == bfmi)
    {
        return;
    }

    bfm = bier_fmask_get(bfmi);

    fib_node_unlock(&bfm->bfm_node);
}

void
bier_fmask_lock (index_t bfmi)
{
    bier_fmask_t *bfm;

    if (INDEX_INVALID == bfmi)
    {
        return;
    }

    bfm = bier_fmask_get(bfmi);

    fib_node_lock(&bfm->bfm_node);
}

index_t
bier_fmask_create_and_lock (const bier_fmask_id_t *fmid,
                            const fib_route_path_t *rpath)
{
    bier_fmask_t *bfm;
    index_t bfmi;

    pool_get_aligned(bier_fmask_pool, bfm, CLIB_CACHE_LINE_BYTES);
    bfmi = bier_fmask_get_index(bfm);

    vlib_validate_combined_counter (&(bier_fmask_counters), bfmi);
    vlib_zero_combined_counter (&(bier_fmask_counters), bfmi);

    bier_fmask_init(bfm, fmid, rpath);

    bier_fmask_lock(bfmi);

    return (bfmi);
}

void
bier_fmask_link (index_t bfmi,
                 bier_bp_t bp)
{
    bier_fmask_t *bfm;

    bfm = bier_fmask_get(bfmi);

    if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
    {
        /*
         * 0 -> 1 transition - set the bit in the string
         */
        bier_bit_string_set_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
    }

    ++bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
    ++bfm->bfm_bits.bfmb_count;
}

void
bier_fmask_unlink (index_t bfmi,
                   bier_bp_t bp)
{
    bier_fmask_t *bfm;

    bfm = bier_fmask_get(bfmi);

    --bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
    --bfm->bfm_bits.bfmb_count;

    if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
    {
        /*
         * 1 -> 0 transition - clear the bit in the string
         */
        bier_bit_string_clear_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
    }
}

u8*
format_bier_fmask (u8 *s, va_list *ap)
{
    index_t bfmi = va_arg(*ap, index_t);
    u32 indent = va_arg(*ap, u32);
    bier_fmask_attributes_t attr;
    bier_fmask_t *bfm;
    vlib_counter_t to;

    if (pool_is_free_index(bier_fmask_pool, bfmi))
    {
        return (format(s, "No BIER f-mask %d", bfmi));
    }

    bfm = bier_fmask_get(bfmi);

    s = format(s, "fmask: nh:%U bs:%U locks:%d ",
               format_ip46_address, &bfm->bfm_id->bfmi_nh, IP46_TYPE_ANY,
               format_bier_bit_string, &bfm->bfm_bits.bfmb_input_reset_string,
               bfm->bfm_node.fn_locks);
    s = format(s, "flags:");
    FOR_EACH_BIER_FMASK_ATTR(attr) {
        if ((1<<attr) & bfm->bfm_flags) {
            s = format (s, "%s,", bier_fmask_attr_names[attr]);
        }
    }
    vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);
    s = format (s, " to:[%Ld:%Ld]]", to.packets, to.bytes);
    s = format(s, "\n");
    s = fib_path_list_format(bfm->bfm_pl, s);

    if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
    {
        s = format(s, "  output-label:%U",
                   format_mpls_unicast_label,
                   vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
    }
    else
    {
        s = format(s, "  output-bfit:[%U]",
                   format_bier_bift_id,
                   vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
    }
    s = format(s, "\n %U%U",
               format_white_space, indent,
               format_dpo_id, &bfm->bfm_dpo, indent+2);

    return (s);
}

void
bier_fmask_get_stats (index_t bfmi, u64 * packets, u64 * bytes)
{
  vlib_counter_t to;

  vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);

  *packets = to.packets;
  *bytes = to.bytes;
}

void
bier_fmask_encode (index_t bfmi,
                   bier_table_id_t *btid,
                   fib_route_path_t *rpath)
{
    bier_fmask_t *bfm;

    bfm = bier_fmask_get(bfmi);
    *btid = *bier_table_get_id(bfm->bfm_id->bfmi_bti);

    clib_memset(rpath, 0, sizeof(*rpath));

    rpath->frp_sw_if_index = ~0;

    switch (bfm->bfm_id->bfmi_nh_type)
    {
    case BIER_NH_UDP:
        rpath->frp_flags = FIB_ROUTE_PATH_UDP_ENCAP;
        rpath->frp_udp_encap_id = bfm->bfm_id->bfmi_id;
        break;
    case BIER_NH_IP:
        memcpy(&rpath->frp_addr, &bfm->bfm_id->bfmi_nh,
               sizeof(rpath->frp_addr));
        break;
    }
}

static fib_node_t *
bier_fmask_get_node (fib_node_index_t index)
{
    bier_fmask_t *bfm = bier_fmask_get(index);
    return (&(bfm->bfm_node));
}

static bier_fmask_t*
bier_fmask_get_from_node (fib_node_t *node)
{
    return ((bier_fmask_t*)(((char*)node) -
                            STRUCT_OFFSET_OF(bier_fmask_t,
                                             bfm_node)));
}

/*
 * bier_fmask_last_lock_gone
 */
static void
bier_fmask_last_lock_gone (fib_node_t *node)
{
    bier_fmask_destroy(bier_fmask_get_from_node(node));
}

/*
 * bier_fmask_back_walk_notify
 *
 * A back walk has reached this BIER fmask
 */
static fib_node_back_walk_rc_t
bier_fmask_back_walk_notify (fib_node_t *node,
                             fib_node_back_walk_ctx_t *ctx)
{
    /*
     * re-stack the fmask on the n-eos of the via
     */
    bier_fmask_t *bfm = bier_fmask_get_from_node(node);

    bier_fmask_stack(bfm);

    /*
     * propagate further up the graph.
     * we can do this synchronously since the fan out is small.
     */
    fib_walk_sync(FIB_NODE_TYPE_BIER_FMASK, bier_fmask_get_index(bfm), ctx);

    return (FIB_NODE_BACK_WALK_CONTINUE);
}

/*
 * The BIER fmask's graph node virtual function table
 */
static const fib_node_vft_t bier_fmask_vft = {
    .fnv_get = bier_fmask_get_node,
    .fnv_last_lock = bier_fmask_last_lock_gone,
    .fnv_back_walk = bier_fmask_back_walk_notify,
};

static void
bier_fmask_dpo_lock (dpo_id_t *dpo)
{
}

static void
bier_fmask_dpo_unlock (dpo_id_t *dpo)
{
}

static void
bier_fmask_dpo_mem_show (void)
{
    fib_show_memory_usage("BIER-fmask",
                          pool_elts(bier_fmask_pool),
                          pool_len(bier_fmask_pool),
                          sizeof(bier_fmask_t));
}

const static dpo_vft_t bier_fmask_dpo_vft = {
    .dv_lock = bier_fmask_dpo_lock,
    .dv_unlock = bier_fmask_dpo_unlock,
    .dv_mem_show = bier_fmask_dpo_mem_show,
    .dv_format = format_bier_fmask,
};

const static char *const bier_fmask_mpls_nodes[] =
{
    "bier-output",
    NULL
};
const static char * const * const bier_fmask_nodes[DPO_PROTO_NUM] =
{
    [DPO_PROTO_BIER] = bier_fmask_mpls_nodes,
    [DPO_PROTO_MPLS] = bier_fmask_mpls_nodes,
};

clib_error_t *
bier_fmask_module_init (vlib_main_t * vm)
{
    fib_node_register_type (FIB_NODE_TYPE_BIER_FMASK, &bier_fmask_vft);
    dpo_register(DPO_BIER_FMASK, &bier_fmask_dpo_vft, bier_fmask_nodes);

    return (NULL);
}

VLIB_INIT_FUNCTION (bier_fmask_module_init);

static clib_error_t *
bier_fmask_show (vlib_main_t * vm,
                 unformat_input_t * input,
                 vlib_cli_command_t * cmd)
{
    bier_fmask_t *bfm;
    index_t bfmi;

    bfmi = INDEX_INVALID;

    while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
        if (unformat (input, "%d", &bfmi))
        {
            ;
        } else
        {
            break;
        }
    }

    if (INDEX_INVALID == bfmi)
    {
        pool_foreach (bfm, bier_fmask_pool)
         {
            vlib_cli_output (vm, "[@%d] %U",
                             bier_fmask_get_index(bfm),
                             format_bier_fmask, bier_fmask_get_index(bfm), 0);
        }
    }
    else
    {
        vlib_cli_output (vm, "%U", format_bier_fmask, bfmi, 0);
    }

    return (NULL);
}

VLIB_CLI_COMMAND (show_bier_fmask, static) = {
    .path = "show bier fmask",
    .short_help = "show bier fmask",
    .function = bier_fmask_show,
};