5e48e9193b5d42f2b52ae567b8df450871272eee
[vpp.git] / src / vnet / mfib / ip6_mfib.c
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15
16 #include <vnet/mfib/ip6_mfib.h>
17
18 #include <vnet/mfib/mfib_table.h>
19 #include <vnet/mfib/mfib_entry.h>
20 #include <vnet/fib/ip6_fib.h>
21
22 /**
23  * The number of bytes in an address/ask key in the radix tree
24  * First byte is the length in bytes.
25  */
26 #define IP6_MFIB_KEY_LEN 33
27
28 /**
29  * Key and mask for radix
30  */
31 typedef struct ip6_mfib_key_t_
32 {
33     u8 key[IP6_MFIB_KEY_LEN];
34     u8 mask[IP6_MFIB_KEY_LEN];
35 } ip6_mfib_key_t;
36
37 /**
38  * An object that is inserted into the radix tree.
39  * Since it's in the tree and has pointers, it cannot realloc and so cannot
40  * come from a vlib pool.
41  */
42 typedef struct ip6_mfib_node_t_
43 {
44     struct radix_node i6mn_nodes[2];
45     ip6_mfib_key_t i6mn_key;
46     index_t i6mn_entry;
47 } ip6_mfib_node_t;
48
49 static const mfib_prefix_t all_zeros = {
50     /* (*,*) */
51     .fp_src_addr = {
52         .ip6.as_u64 = {0, 0},
53     },
54     .fp_grp_addr = {
55         .ip6.as_u64 = {0, 0},
56     },
57     .fp_len  = 0,
58     .fp_proto = FIB_PROTOCOL_IP6,
59 };
60
61 typedef enum ip6_mfib_special_type_t_ {
62     IP6_MFIB_SPECIAL_TYPE_NONE,
63     IP6_MFIB_SPECIAL_TYPE_SOLICITED,
64 } ip6_mfib_special_type_t;
65
66 typedef struct ip6_mfib_special_t_ {
67     /**
68      * @brief solicited or not
69      */
70     ip6_mfib_special_type_t ims_type;
71
72     /**
73      * @brief the Prefix length
74      */
75     u8 ims_len;
76
77     /**
78      * @brief The last byte of the mcast address
79      */
80     u8 ims_byte;
81     /**
82      * @brief The scope of the address
83      */
84     u8 ims_scope;
85 } ip6_mfib_special_t;
86
87 static const ip6_mfib_special_t ip6_mfib_specials[] =
88 {
89     {
90         /*
91          * Add ff02::1:ff00:0/104 via local route for all tables.
92          *  This is required for neighbor discovery to work.
93          */
94         .ims_type = IP6_MFIB_SPECIAL_TYPE_SOLICITED,
95         .ims_len = 104,
96     },
97     {
98         /*
99          * all-routers multicast address
100          */
101         .ims_type = IP6_MFIB_SPECIAL_TYPE_NONE,
102         .ims_scope = IP6_MULTICAST_SCOPE_link_local,
103         .ims_byte = IP6_MULTICAST_GROUP_ID_all_routers,
104         .ims_len = 128,
105     },
106     {
107         /*
108          * all-nodes multicast address
109          */
110         .ims_type = IP6_MFIB_SPECIAL_TYPE_NONE,
111         .ims_scope = IP6_MULTICAST_SCOPE_link_local,
112         .ims_byte = IP6_MULTICAST_GROUP_ID_all_hosts,
113         .ims_len = 128,
114     },
115     {
116         /*
117          *  Add all-mldv2  multicast address via local route for all tables
118          */
119         .ims_type = IP6_MFIB_SPECIAL_TYPE_NONE,
120         .ims_len = 128,
121         .ims_scope = IP6_MULTICAST_SCOPE_link_local,
122         .ims_byte = IP6_MULTICAST_GROUP_ID_mldv2_routers,
123     }
124 };
125
126 #define FOR_EACH_IP6_SPECIAL(_pfx, _body)                               \
127 {                                                                       \
128     const ip6_mfib_special_t *_spec;                                    \
129     u8 _ii;                                                             \
130     for (_ii = 0;                                                       \
131          _ii < ARRAY_LEN(ip6_mfib_specials);                            \
132          _ii++)                                                         \
133     {                                                                   \
134         _spec = &ip6_mfib_specials[_ii];                                \
135         if (IP6_MFIB_SPECIAL_TYPE_SOLICITED == _spec->ims_type)         \
136         {                                                               \
137             ip6_set_solicited_node_multicast_address(                   \
138                 &(_pfx)->fp_grp_addr.ip6, 0);                           \
139         }                                                               \
140         else                                                            \
141         {                                                               \
142             ip6_set_reserved_multicast_address (                        \
143                 &(_pfx)->fp_grp_addr.ip6,                               \
144                 _spec->ims_scope,                                       \
145                 _spec->ims_byte);                                       \
146         }                                                               \
147         (_pfx)->fp_len = _spec->ims_len;                                \
148         do { _body; } while (0);                                        \
149     }                                                                   \
150 }
151
152
153 static u32
154 ip6_create_mfib_with_table_id (u32 table_id)
155 {
156     mfib_table_t *mfib_table;
157     mfib_prefix_t pfx = {
158         .fp_proto = FIB_PROTOCOL_IP6,
159     };
160     const fib_route_path_t path_for_us = {
161         .frp_proto = DPO_PROTO_IP6,
162         .frp_addr = zero_addr,
163         .frp_sw_if_index = 0xffffffff,
164         .frp_fib_index = ~0,
165         .frp_weight = 0,
166         .frp_flags = FIB_ROUTE_PATH_LOCAL,
167     };
168
169     pool_get_aligned(ip6_main.mfibs, mfib_table, CLIB_CACHE_LINE_BYTES);
170     memset(mfib_table, 0, sizeof(*mfib_table));
171
172     mfib_table->mft_proto = FIB_PROTOCOL_IP6;
173     mfib_table->mft_index =
174         mfib_table->v6.index =
175             (mfib_table - ip6_main.mfibs);
176
177     hash_set (ip6_main.mfib_index_by_table_id,
178               table_id,
179               mfib_table->mft_index);
180
181     mfib_table->mft_table_id =
182         mfib_table->v6.table_id =
183             table_id;
184
185     mfib_table_lock(mfib_table->mft_index, FIB_PROTOCOL_IP6);
186
187     mfib_table->v6.rhead =
188         clib_mem_alloc_aligned (sizeof(*mfib_table->v6.rhead),
189                                 CLIB_CACHE_LINE_BYTES);
190     rn_inithead0(mfib_table->v6.rhead, 8);
191
192     /*
193      * add the special entries into the new FIB
194      */
195     mfib_table_entry_update(mfib_table->mft_index,
196                             &all_zeros,
197                             MFIB_SOURCE_DEFAULT_ROUTE,
198                             MFIB_RPF_ID_NONE,
199                             MFIB_ENTRY_FLAG_DROP);
200
201     /*
202      * Add each of the specials
203      */
204     FOR_EACH_IP6_SPECIAL(&pfx,
205     ({
206         mfib_table_entry_path_update(mfib_table->mft_index,
207                                      &pfx,
208                                      MFIB_SOURCE_SPECIAL,
209                                      &path_for_us,
210                                      MFIB_ITF_FLAG_FORWARD);
211     }));
212
213     return (mfib_table->mft_index);
214 }
215
216 void
217 ip6_mfib_table_destroy (ip6_mfib_t *mfib)
218 {
219     mfib_table_t *mfib_table = (mfib_table_t*)mfib;
220     fib_node_index_t mfei;
221     mfib_prefix_t pfx = {
222         .fp_proto = FIB_PROTOCOL_IP6,
223     };
224     const fib_route_path_t path_for_us = {
225         .frp_proto = DPO_PROTO_IP6,
226         .frp_addr = zero_addr,
227         .frp_sw_if_index = 0xffffffff,
228         .frp_fib_index = ~0,
229         .frp_weight = 0,
230         .frp_flags = FIB_ROUTE_PATH_LOCAL,
231     };
232
233     /*
234      * remove all the specials we added when the table was created.
235      */
236     FOR_EACH_IP6_SPECIAL(&pfx,
237     {
238         mfib_table_entry_path_remove(mfib_table->mft_index,
239                                      &pfx,
240                                      MFIB_SOURCE_SPECIAL,
241                                      &path_for_us);
242     });
243
244     mfei = mfib_table_lookup_exact_match(mfib_table->mft_index, &all_zeros);
245     mfib_table_entry_delete_index(mfei, MFIB_SOURCE_DEFAULT_ROUTE);
246
247     /*
248      * validate no more routes.
249      */
250     ASSERT(0 == mfib_table->mft_total_route_counts);
251     ASSERT(~0 != mfib_table->mft_table_id);
252
253     hash_unset (ip6_main.mfib_index_by_table_id, mfib_table->mft_table_id);
254     clib_mem_free(mfib_table->v6.rhead);
255     pool_put(ip6_main.mfibs, mfib_table);
256 }
257
258 void
259 ip6_mfib_interface_enable_disable (u32 sw_if_index, int is_enable)
260 {
261     const fib_route_path_t path = {
262         .frp_proto = DPO_PROTO_IP6,
263         .frp_addr = zero_addr,
264         .frp_sw_if_index = sw_if_index,
265         .frp_fib_index = ~0,
266         .frp_weight = 0,
267     };
268     mfib_prefix_t pfx = {
269         .fp_proto = FIB_PROTOCOL_IP6,
270     };
271     u32 mfib_index;
272
273     vec_validate (ip6_main.mfib_index_by_sw_if_index, sw_if_index);
274     mfib_index = ip6_mfib_table_get_index_for_sw_if_index(sw_if_index);
275
276     if (is_enable)
277     {
278         FOR_EACH_IP6_SPECIAL(&pfx,
279         {
280             mfib_table_entry_path_update(mfib_index,
281                                          &pfx,
282                                          MFIB_SOURCE_SPECIAL,
283                                          &path,
284                                          MFIB_ITF_FLAG_ACCEPT);
285         });
286     }
287     else
288     {
289         FOR_EACH_IP6_SPECIAL(&pfx,
290         {
291             mfib_table_entry_path_remove(mfib_index,
292                                          &pfx,
293                                          MFIB_SOURCE_SPECIAL,
294                                          &path);
295         });
296     }
297 }
298
299 u32
300 ip6_mfib_table_find_or_create_and_lock (u32 table_id)
301 {
302     u32 index;
303
304     index = ip6_mfib_index_from_table_id(table_id);
305     if (~0 == index)
306         return ip6_create_mfib_with_table_id(table_id);
307     mfib_table_lock(index, FIB_PROTOCOL_IP6);
308
309     return (index);
310 }
311
312 u32
313 ip6_mfib_table_get_index_for_sw_if_index (u32 sw_if_index)
314 {
315     if (sw_if_index >= vec_len(ip6_main.mfib_index_by_sw_if_index))
316     {
317         /*
318          * This is the case for interfaces that are not yet mapped to
319          * a IP table
320          */
321         return (~0);
322     }
323     return (ip6_main.mfib_index_by_sw_if_index[sw_if_index]);
324 }
325
326 #define IP6_MFIB_MK_KEY(_grp, _src, _key)                           \
327 {                                                                   \
328     (_key)->key[0] = 33;                                            \
329     memcpy((_key)->key+1, _grp, 16);                                \
330     memcpy((_key)->key+17, _src, 16);                               \
331 }
332
333 #define IP6_MFIB_MK_KEY_MASK(_grp, _src, _len, _key)                \
334 {                                                                   \
335     IP6_MFIB_MK_KEY(_grp, _src, _key);                              \
336                                                                     \
337     (_key)->mask[0] = 33;                                           \
338     if (_len <= 128)                                                \
339     {                                                               \
340         memcpy((_key)->mask+1, &ip6_main.fib_masks[_len], 16);      \
341         memset((_key)->mask+17, 0, 16);                             \
342     }                                                               \
343     else                                                            \
344     {                                                               \
345         ASSERT(_len == 256);                                        \
346         memcpy((_key)->mask+1, &ip6_main.fib_masks[128], 16);       \
347         memcpy((_key)->mask+17, &ip6_main.fib_masks[128], 16);      \
348     }                                                               \
349 }
350
351 /*
352  * ip6_fib_table_lookup_exact_match
353  *
354  * Exact match prefix lookup
355  */
356 fib_node_index_t
357 ip6_mfib_table_lookup_exact_match (const ip6_mfib_t *mfib,
358                                    const ip6_address_t *grp,
359                                    const ip6_address_t *src,
360                                    u32 len)
361 {
362     ip6_mfib_node_t *i6mn;
363     ip6_mfib_key_t key;
364
365     IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
366
367     i6mn = (ip6_mfib_node_t*) rn_lookup(key.key, key.mask,
368                                         (struct radix_node_head *)mfib->rhead);
369
370     if (NULL == i6mn)
371     {
372         return (INDEX_INVALID);
373     }
374
375     return (i6mn->i6mn_entry);
376 }
377
378 /*
379  * ip6_fib_table_lookup
380  *
381  * Longest prefix match
382  */
383 fib_node_index_t
384 ip6_mfib_table_lookup (const ip6_mfib_t *mfib,
385                        const ip6_address_t *src,
386                        const ip6_address_t *grp,
387                        u32 len)
388 {
389     ip6_mfib_node_t *i6mn;
390     ip6_mfib_key_t key;
391
392     IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
393
394     i6mn = (ip6_mfib_node_t*) rn_search_m(key.key,
395                                           mfib->rhead->rnh_treetop,
396                                           key.mask);
397
398     ASSERT(NULL != i6mn);
399
400     return (i6mn->i6mn_entry);
401 }
402
403 /*
404  * ip6_fib_table_lookup
405  *
406  * Longest prefix match no mask
407  */
408 fib_node_index_t
409 ip6_mfib_table_lookup2 (const ip6_mfib_t *mfib,
410                         const ip6_address_t *src,
411                         const ip6_address_t *grp)
412 {
413     ip6_mfib_node_t *i6mn;
414     ip6_mfib_key_t key;
415
416     IP6_MFIB_MK_KEY(grp, src, &key);
417
418     i6mn = (ip6_mfib_node_t*) rn_match(key.key,
419                                        (struct radix_node_head *)mfib->rhead); // const cast
420
421     ASSERT(NULL != i6mn);
422
423     return (i6mn->i6mn_entry);
424 }
425
426 void
427 ip6_mfib_table_entry_insert (ip6_mfib_t *mfib,
428                              const ip6_address_t *grp,
429                              const ip6_address_t *src,
430                              u32 len,
431                              fib_node_index_t mfib_entry_index)
432 {
433     ip6_mfib_node_t *i6mn = clib_mem_alloc(sizeof(*i6mn));
434
435     memset(i6mn->i6mn_nodes, 0, sizeof(i6mn->i6mn_nodes));
436
437     IP6_MFIB_MK_KEY_MASK(grp, src, len, &i6mn->i6mn_key);
438     i6mn->i6mn_entry = mfib_entry_index;
439
440     if (NULL == rn_addroute(i6mn->i6mn_key.key,
441                             i6mn->i6mn_key.mask,
442                             mfib->rhead,
443                             i6mn->i6mn_nodes))
444     {
445         ASSERT(0);
446     }
447 }
448
449 void
450 ip6_mfib_table_entry_remove (ip6_mfib_t *mfib,
451                              const ip6_address_t *grp,
452                              const ip6_address_t *src,
453                              u32 len)
454 {
455     ip6_mfib_node_t *i6mn;
456     ip6_mfib_key_t key;
457
458     IP6_MFIB_MK_KEY_MASK(grp, src, len, &key);
459
460     i6mn = (ip6_mfib_node_t*) rn_delete(key.key, key.mask, mfib->rhead);
461
462     clib_mem_free(i6mn);
463 }
464
465 static clib_error_t *
466 ip6_mfib_module_init (vlib_main_t * vm)
467 {
468     return (NULL);
469 }
470
471 VLIB_INIT_FUNCTION(ip6_mfib_module_init);
472
473 static void
474 ip6_mfib_table_show_one (ip6_mfib_t *mfib,
475                          vlib_main_t * vm,
476                          ip6_address_t *src,
477                          ip6_address_t *grp,
478                          u32 mask_len)
479 {
480     vlib_cli_output(vm, "%U",
481                     format_mfib_entry,
482                     ip6_mfib_table_lookup(mfib, src, grp, mask_len),
483                     MFIB_ENTRY_FORMAT_DETAIL);
484 }
485
486 typedef struct ip6_mfib_show_ctx_t_ {
487     fib_node_index_t *entries;
488 } ip6_mfib_show_ctx_t;
489
490
491 static int
492 ip6_mfib_table_collect_entries (fib_node_index_t mfei, void *arg)
493 {
494     ip6_mfib_show_ctx_t *ctx = arg;
495
496     vec_add1(ctx->entries, mfei);
497
498     return (0);
499 }
500
501 static void
502 ip6_mfib_table_show_all (ip6_mfib_t *mfib,
503                          vlib_main_t * vm)
504 {
505     fib_node_index_t *mfib_entry_index;
506     ip6_mfib_show_ctx_t ctx = {
507         .entries = NULL,
508     };
509
510     ip6_mfib_table_walk(mfib,
511                         ip6_mfib_table_collect_entries,
512                         &ctx);
513
514     vec_sort_with_function(ctx.entries, mfib_entry_cmp_for_sort);
515
516     vec_foreach(mfib_entry_index, ctx.entries)
517     {
518         vlib_cli_output(vm, "%U",
519                         format_mfib_entry,
520                         *mfib_entry_index,
521                         MFIB_ENTRY_FORMAT_BRIEF);
522     }
523
524     vec_free(ctx.entries);
525 }
526
527 typedef struct ip6_mfib_radix_walk_ctx_t_
528 {
529     mfib_table_walk_fn_t user_fn;
530     void *user_ctx;
531 } ip6_mfib_radix_walk_ctx_t;
532
533 static int
534 ip6_mfib_table_radix_walk (struct radix_node *rn,
535                            void *arg)
536 {
537     ip6_mfib_radix_walk_ctx_t *ctx = arg;
538     ip6_mfib_node_t *i6mn;
539
540     i6mn = (ip6_mfib_node_t*) rn;
541
542     ctx->user_fn(i6mn->i6mn_entry, ctx->user_ctx);
543
544     return (0);
545 }
546
547 void
548 ip6_mfib_table_walk (ip6_mfib_t *mfib,
549                      mfib_table_walk_fn_t fn,
550                      void *ctx)
551 {
552     ip6_mfib_radix_walk_ctx_t rn_ctx = {
553         .user_fn = fn,
554         .user_ctx = ctx,
555     };
556
557     rn_walktree(mfib->rhead,
558                 ip6_mfib_table_radix_walk,
559                 &rn_ctx);
560 }
561
562 static clib_error_t *
563 ip6_show_mfib (vlib_main_t * vm,
564                unformat_input_t * input,
565                vlib_cli_command_t * cmd)
566 {
567     ip6_main_t * im4 = &ip6_main;
568     mfib_table_t *mfib_table;
569     int verbose, matching;
570     ip6_address_t grp, src = {{0}};
571     u32 mask = 32;
572     int table_id = -1, fib_index = ~0;
573
574     verbose = 1;
575     matching = 0;
576
577     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
578     {
579         if (unformat (input, "brief") || unformat (input, "summary")
580             || unformat (input, "sum"))
581             verbose = 0;
582
583         else if (unformat (input, "%U %U",
584                            unformat_ip6_address, &src,
585                            unformat_ip6_address, &grp))
586         {
587             matching = 1;
588             mask = 256;
589         }
590         else if (unformat (input, "%U/%d", unformat_ip6_address, &grp, &mask))
591         {
592             memset(&src, 0, sizeof(src));
593             matching = 1;
594         }
595         else if (unformat (input, "%U", unformat_ip6_address, &grp))
596         {
597             memset(&src, 0, sizeof(src));
598             matching = 1;
599             mask = 128;
600         }
601         else if (unformat (input, "table %d", &table_id))
602             ;
603         else if (unformat (input, "index %d", &fib_index))
604             ;
605         else
606             break;
607     }
608
609     pool_foreach (mfib_table, im4->mfibs,
610     ({
611         ip6_mfib_t *mfib = &mfib_table->v6;
612
613         if (table_id >= 0 && table_id != (int)mfib->table_id)
614             continue;
615         if (fib_index != ~0 && fib_index != (int)mfib->index)
616             continue;
617
618         vlib_cli_output (vm, "%U, fib_index %d",
619                          format_mfib_table_name, mfib->index, FIB_PROTOCOL_IP6,
620                          mfib->index);
621
622         /* Show summary? */
623         if (! verbose)
624         {
625             /* vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count"); */
626             /* for (i = 0; i < ARRAY_LEN (mfib->fib_entry_by_dst_address); i++) */
627             /* { */
628             /*     uword * hash = mfib->fib_entry_by_dst_address[i]; */
629             /*     uword n_elts = hash_elts (hash); */
630             /*     if (n_elts > 0) */
631             /*         vlib_cli_output (vm, "%20d%16d", i, n_elts); */
632             /* } */
633             continue;
634         }
635
636         if (!matching)
637         {
638             ip6_mfib_table_show_all(mfib, vm);
639         }
640         else
641         {
642             ip6_mfib_table_show_one(mfib, vm, &src, &grp, mask);
643         }
644     }));
645
646     return 0;
647 }
648
649 /*
650  * This command displays the IPv4 MulticasrFIB Tables (VRF Tables) and
651  * the route entries for each table.
652  *
653  * @note This command will run for a long time when the FIB tables are
654  * comprised of millions of entries. For those senarios, consider displaying
655  * a single table or summary mode.
656  *
657  * @cliexpar
658  * Example of how to display all the IPv4 Multicast FIB tables:
659  * @cliexstart{show ip fib}
660  * ipv4-VRF:0, fib_index 0
661  * (*, 0.0.0.0/0):  flags:D,
662  *  Interfaces:
663  *  multicast-ip6-chain
664  *   [@1]: dpo-drop ip6
665  * (*, 232.1.1.1/32):
666  * Interfaces:
667  *  test-eth1: Forward,
668  *  test-eth2: Forward,
669  *  test-eth0: Accept,
670  * multicast-ip6-chain
671  * [@2]: dpo-replicate: [index:1 buckets:2 to:[0:0]]
672  *   [0] [@1]: ipv4-mcast: test-eth1: IP6: d0:d1:d2:d3:d4:01 -> 01:00:05:00:00:00
673  *   [1] [@1]: ipv4-mcast: test-eth2: IP6: d0:d1:d2:d3:d4:02 -> 01:00:05:00:00:00
674  *
675  * @cliexend
676  * Example of how to display a summary of all IPv4 FIB tables:
677  * @cliexstart{show ip fib summary}
678  * ipv4-VRF:0, fib_index 0, flow hash: src dst sport dport proto
679  *     Prefix length         Count
680  *                    0               1
681  *                    8               2
682  *                   32               4
683  * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto
684  *     Prefix length         Count
685  *                    0               1
686  *                    8               2
687  *                   24               2
688  *                   32               4
689  * @cliexend
690  */
691 /* *INDENT-OFF* */
692 VLIB_CLI_COMMAND (ip6_show_fib_command, static) = {
693     .path = "show ip6 mfib",
694     .short_help = "show ip mfib [summary] [table <table-id>] [index <fib-id>] [<grp-addr>[/<mask>]] [<grp-addr>] [<src-addr> <grp-addr>]",
695     .function = ip6_show_mfib,
696 };
697 /* *INDENT-ON* */