aboutsummaryrefslogtreecommitdiffstats
path: root/src/vnet/fib/ip4_fib.c
blob: d8d983dd9c1a093df4f0a44bcf4e7ea5e0d2c19c (plain)
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

@media only all and (prefers-color-scheme: dark) {
.highlight .hll { background-color: #49483e }
.highlight .c { color: #75715e } /* Comment */
.highlight .err { color: #960050; background-color: #1e0010 } /* Error */
.highlight .k { color: #66d9ef } /* Keyword */
.highlight .l { color: #ae81ff } /* Literal */
.highlight .n { color: #f8f8f2 } /* Name */
.highlight .o { color: #f92672 } /* Operator */
.highlight .p { color: #f8f8f2 } /* Punctuation */
.highlight .ch { color: #75715e } /* Comment.Hashbang */
.highlight .cm { color: #75715e } /* Comment.Multiline */
.highlight .cp { color: #75715e } /* Comment.Preproc */
.highlight .cpf { color: #75715e } /* Comment.PreprocFile */
.highlight .c1 { color: #75715e } /* Comment.Single */
.highlight .cs { color: #75715e } /* Comment.Special */
.highlight .gd { color: #f92672 } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gi { color: #a6e22e } /* Generic.Inserted */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #75715e } /* Generic.Subheading */
.highlight .kc { color: #66d9ef } /* Keyword.Constant */
.highlight .kd { color: #66d9ef } /* Keyword.Declaration */
.highlight .kn { color: #f92672 } /* Keyword.Namespace */
.highlight .kp { color: #66d9ef } /* Keyword.Pseudo */
.highlight .kr { color: #66d9ef } /* Keyword.Reserved */
.highlight .kt { color: #66d9ef } /* Keyword.Type */
.highlight .ld { color: #e6db74 } /* Literal.Date */
.highlight .m { color: #ae81ff } /* Literal.Number */
.highlight .s { color: #e6db74 } /* Literal.String */
.highlight .na { color: #a6e22e } /* Name.Attribute */
.highlight .nb { color: #f8f8f2 } /* Name.Builtin */
.highlight .nc { color: #a6e22e } /* Name.Class */
.highlight .no { color: #66d9ef } /* Name.Constant */
.highlight .nd { color: #a6e22e } /* Name.Decorator */
.highlight .ni { color: #f8f8f2 } /* Name.Entity */
.highlight .ne { color: #a6e22e } /* Name.Exception */
.highlight .nf { color: #a6e22e } /* Name.Function */
.highlight .nl { color: #f8f8f2 } /* Name.Label */
.highlight .nn { color: #f8f8f2 } /* Name.Namespace */
.highlight .nx { color: #a6e22e } /* Name.Other */
.highlight .py { color: #f8f8f2 } /* Name.Property */
.highlight .nt { color: #f92672 } /* Name.Tag */
.highlight .nv { color: #f8f8f2 } /* Name.Variable */
.highlight .ow { color: #f92672 } /* Operator.Word */
.highlight .w { color: #f8f8f2 } /* Text.Whitespace */
.highlight .mb { color: #ae81ff } /* Literal.Number.Bin */
.highlight .mf { color: #ae81ff } /* Literal.Number.Float */
.highlight .mh { color: #ae81ff } /* Literal.Number.Hex */
.highlight .mi { color: #ae81ff } /* Literal.Number.Integer */
.highlight .mo { color: #ae81ff } /* Literal.Number.Oct */
.highlight .sa { color: #e6db74 } /* Literal.String.Affix */
.highlight .sb { color: #e6db74 } /* Literal.String.Backtick */
.highlight .sc { color: #e6db74 } /* Literal.String.Char */
.highlight .dl { color: #e6db74 } /* Literal.String.Delimiter */
.highlight .sd { color: #e6db74 } /* Literal.String.Doc */
.highlight .s2 { color: #e6db74 } /* Literal.String.Double */
.highlight .se { color: #ae81ff } /* Literal.String.Escape */
.highlight .sh { color: #e6db74 } /* Literal.String.Heredoc */
.highlight .si { color: #e6db74 } /* Literal.String.Interpol */
.highlight .sx { color: #e6db74 } /* Literal.String.Other */
.highlight .sr { color: #e6db74 } /* Literal.String.Regex */
.highlight .s1 { color: #e6db74 } /* Literal.String.Single */
.highlight .ss { color: #e6db74 } /* Literal.String.Symbol */
.highlight .bp { color: #f8f8f2 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #a6e22e } /* Name.Function.Magic */
.highlight .vc { color: #f8f8f2 } /* Name.Variable.Class */
.highlight .vg { color: #f8f8f2 } /* Name.Variable.Global */
.highlight .vi { color: #f8f8f2 } /* Name.Variable.Instance */
.highlight .vm { color: #f8f8f2 } /* Name.Variable.Magic */
.highlight .il { color: #ae81ff } /* Literal.Number.Integer.Long */
}
@media (prefers-color-scheme: light) {
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
}
#!/bin/bash

# Make sure that we get the hugepages we need on provision boot
# Note: The package install should take care of this at the end
#       But sometimes after all the work of provisioning, we can't
#       get the requested number of hugepages without rebooting.
#       So do it here just in case
sysctl -w vm.nr_hugepages=1024
HUGEPAGES=`sysctl -n  vm.nr_hugepages`
if [ $HUGEPAGES != 1024 ]; then
    echo "ERROR: Unable to get 1024 hugepages, only got $HUGEPAGES.  Cannot finish."
    exit
fi

if [ "$(uname)" <> "Darwin" ]; then
    OS_ID=$(grep '^ID=' /etc/os-release | cut -f2- -d= | sed -e 's/\"//g')
    OS_VERSION_ID=$(grep '^VERSION_ID=' /etc/os-release | cut -f2- -d= | sed -e 's/\"//g')
fi

# Do initial setup for the system
if [ "$OS_ID" == "ubuntu" ]; then

    export DEBIAN_PRIORITY=critical
    export DEBIAN_FRONTEND=noninteractive
    export DEBCONF_NONINTERACTIVE_SEEN=true
    APT_OPTS="--assume-yes --no-install-suggests --no-install-recommends -o Dpkg::Options::=\"--force-confdef\" -o Dpkg::Options::=\"--force-confold\""

    # Standard update + upgrade dance
    apt-get update ${APT_OPTS} >/dev/null
    apt-get upgrade ${APT_OPTS} >/dev/null

    # Fix the silly notion that /bin/sh should point to dash by pointing it to bash

    update-alternatives --install /bin/sh sh /bin/bash 100

    # Install useful but non-mandatory tools
    apt-get install -y emacs x11-utils git-review gdb gdbserver xfce4-terminal iperf3
elif [ "$OS_ID" == "centos" ]; then
    if [ "$(echo $DISTRIB_RELEASE | cut -d'.' -f1)" == "7" ]; then
        rpm -ivh https://dl.fedoraproject.org/pub/epel/epel-release-latest-7.noarch.rpm
        yum groupinstall "X Window system" -y
        yum groupinstall xfce -y
    fi
    # Standard update + upgrade dance
    yum check-update
    yum update -y
fi
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878
/*
 * 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_table.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/ip4_fib.h>

/*
 * A table of pefixes to be added to tables and the sources for them
 */
typedef struct ip4_fib_table_special_prefix_t_ {
    fib_prefix_t ift_prefix;
    fib_source_t ift_source;
    fib_entry_flag_t ift_flag;
} ip4_fib_table_special_prefix_t;

static const ip4_fib_table_special_prefix_t ip4_specials[] = {
    {
	/* 0.0.0.0/0*/
	.ift_prefix = {
	    .fp_addr = {
		.ip4.data_u32 = 0,
	    },
	    .fp_len  = 0,
	    .fp_proto = FIB_PROTOCOL_IP4,
	},
	.ift_source = FIB_SOURCE_DEFAULT_ROUTE,
	.ift_flag   = FIB_ENTRY_FLAG_DROP,
    },
    {
	/* 0.0.0.0/32*/
	.ift_prefix = {
	    .fp_addr = {
		.ip4.data_u32 = 0,
	    },
	    .fp_len  = 32,
	    .fp_proto = FIB_PROTOCOL_IP4,
	},
	.ift_source = FIB_SOURCE_DEFAULT_ROUTE,
	.ift_flag   = FIB_ENTRY_FLAG_DROP,
    },
    {
	/*
	 * 240.0.0.0/4
	 * drop class E
	 */
	.ift_prefix = {
	    .fp_addr = {
		.ip4.data_u32 = 0xf0000000,
	    },
	    .fp_len   = 4,
	    .fp_proto = FIB_PROTOCOL_IP4,
	},
	.ift_source = FIB_SOURCE_SPECIAL,
	.ift_flag   = FIB_ENTRY_FLAG_DROP,

    },
    {
	/*
	 * 224.0.0.0/4
	 * drop all mcast
	 */
	.ift_prefix = {
	    .fp_addr = {
		.ip4.data_u32 = 0xe0000000,
	    },
	    .fp_len   = 4,
	    .fp_proto = FIB_PROTOCOL_IP4,
	},
	.ift_source = FIB_SOURCE_SPECIAL,
	.ift_flag    = FIB_ENTRY_FLAG_DROP,
    },
    {
	/*
	 * 255.255.255.255/32
	 * drop, but we'll allow it to be usurped by the likes of DHCP
	 */
	.ift_prefix = {
	    .fp_addr = {
		.ip4.data_u32 = 0xffffffff,
	    },
	    .fp_len   = 32,
	    .fp_proto = FIB_PROTOCOL_IP4,
	},
	.ift_source = FIB_SOURCE_DEFAULT_ROUTE,
	.ift_flag   = FIB_ENTRY_FLAG_DROP,
    }
};


static u32
ip4_create_fib_with_table_id (u32 table_id,
                              fib_source_t src)
{
    fib_table_t *fib_table;
    ip4_fib_t *v4_fib;
    void *old_heap;

    pool_get(ip4_main.fibs, fib_table);
    memset(fib_table, 0, sizeof(*fib_table));

    old_heap = clib_mem_set_heap (ip4_main.mtrie_mheap);
    pool_get_aligned(ip4_main.v4_fibs, v4_fib, CLIB_CACHE_LINE_BYTES);
    clib_mem_set_heap (old_heap);

    ASSERT((fib_table - ip4_main.fibs) ==
           (v4_fib - ip4_main.v4_fibs));

    fib_table->ft_proto = FIB_PROTOCOL_IP4;
    fib_table->ft_index =
	v4_fib->index =
	    (fib_table - ip4_main.fibs);

    hash_set (ip4_main.fib_index_by_table_id, table_id, fib_table->ft_index);

    fib_table->ft_table_id =
	v4_fib->table_id =
	    table_id;
    fib_table->ft_flow_hash_config = IP_FLOW_HASH_DEFAULT;
    
    fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP4, src);

    ip4_mtrie_init(&v4_fib->mtrie);

    /*
     * add the special entries into the new FIB
     */
    int ii;

    for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
    {
	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;

	prefix.fp_addr.ip4.data_u32 =
	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);

	fib_table_entry_special_add(fib_table->ft_index,
				    &prefix,
				    ip4_specials[ii].ift_source,
				    ip4_specials[ii].ift_flag);
    }

    return (fib_table->ft_index);
}

void
ip4_fib_table_destroy (u32 fib_index)
{
    fib_table_t *fib_table = pool_elt_at_index(ip4_main.fibs, fib_index);
    ip4_fib_t *v4_fib = pool_elt_at_index(ip4_main.v4_fibs, fib_index);
    int ii;

    /*
     * remove all the specials we added when the table was created.
     * In reverse order so the default route is last.
     */
    for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--)
    {
	fib_prefix_t prefix = ip4_specials[ii].ift_prefix;

	prefix.fp_addr.ip4.data_u32 =
	    clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32);

	fib_table_entry_special_remove(fib_table->ft_index,
				       &prefix,
				       ip4_specials[ii].ift_source);
    }

    /*
     * validate no more routes.
     */
    ASSERT(0 == fib_table->ft_total_route_counts);
    FOR_EACH_FIB_SOURCE(ii)
    {
	ASSERT(0 == fib_table->ft_src_route_counts[ii]);
    }

    if (~0 != fib_table->ft_table_id)
    {
	hash_unset (ip4_main.fib_index_by_table_id, fib_table->ft_table_id);
    }

    ip4_mtrie_free(&v4_fib->mtrie);

    pool_put(ip4_main.v4_fibs, v4_fib);
    pool_put(ip4_main.fibs, fib_table);
}


u32
ip4_fib_table_find_or_create_and_lock (u32 table_id,
                                       fib_source_t src)
{
    u32 index;

    index = ip4_fib_index_from_table_id(table_id);
    if (~0 == index)
	return ip4_create_fib_with_table_id(table_id, src);

    fib_table_lock(index, FIB_PROTOCOL_IP4, src);

    return (index);
}

u32
ip4_fib_table_create_and_lock (fib_source_t src)
{
    return (ip4_create_fib_with_table_id(~0, src));
}

u32
ip4_fib_table_get_index_for_sw_if_index (u32 sw_if_index)
{
    if (sw_if_index >= vec_len(ip4_main.fib_index_by_sw_if_index))
    {
	/*
	 * This is the case for interfaces that are not yet mapped to
	 * a IP table
	 */
	return (~0);
    }
    return (ip4_main.fib_index_by_sw_if_index[sw_if_index]);
}

/*
 * ip4_fib_table_lookup_exact_match
 *
 * Exact match prefix lookup
 */
fib_node_index_t
ip4_fib_table_lookup_exact_match (const ip4_fib_t *fib,
				  const ip4_address_t *addr,
				  u32 len)
{
    uword * hash, * result;
    u32 key;

    hash = fib->fib_entry_by_dst_address[len];
    key  = (addr->data_u32 & ip4_main.fib_masks[len]);

    result = hash_get(hash, key);

    if (NULL != result) {
	return (result[0]);
    }
    return (FIB_NODE_INDEX_INVALID);
}

/*
 * ip4_fib_table_lookup_adj
 *
 * Longest prefix match
 */
index_t
ip4_fib_table_lookup_lb (ip4_fib_t *fib,
			 const ip4_address_t *addr)
{
    fib_node_index_t fei;

    fei = ip4_fib_table_lookup(fib, addr, 32);

    if (FIB_NODE_INDEX_INVALID != fei)
    {
	const dpo_id_t *dpo;

	dpo = fib_entry_contribute_ip_forwarding(fei);

	return (dpo->dpoi_index);
    }
    return (INDEX_INVALID);
}

/*
 * ip4_fib_table_lookup
 *
 * Longest prefix match
 */
fib_node_index_t
ip4_fib_table_lookup (const ip4_fib_t *fib,
		      const ip4_address_t *addr,
		      u32 len)
{
    uword * hash, * result;
    i32 mask_len;
    u32 key;

    for (mask_len = len; mask_len >= 0; mask_len--)
    {
	hash = fib->fib_entry_by_dst_address[mask_len];
	key = (addr->data_u32 & ip4_main.fib_masks[mask_len]);

	result = hash_get (hash, key);

	if (NULL != result) {
	    return (result[0]);
	}
    }
    return (FIB_NODE_INDEX_INVALID);
}

void
ip4_fib_table_entry_insert (ip4_fib_t *fib,
			    const ip4_address_t *addr,
			    u32 len,
			    fib_node_index_t fib_entry_index)
{
    uword * hash, * result;
    u32 key;

    key = (addr->data_u32 & ip4_main.fib_masks[len]);
    hash = fib->fib_entry_by_dst_address[len];
    result = hash_get (hash, key);

    if (NULL == result) {
	/*
	 * adding a new entry
	 */
        uword *old_heap;
        old_heap = clib_mem_set_heap (ip4_main.mtrie_mheap);

	if (NULL == hash) {
	    hash = hash_create (32 /* elts */, sizeof (uword));
	    hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK);

	}
	hash = hash_set(hash, key, fib_entry_index);
	fib->fib_entry_by_dst_address[len] = hash;
        clib_mem_set_heap (old_heap);
    }
    else
    {
	ASSERT(0);
    }
}

void
ip4_fib_table_entry_remove (ip4_fib_t *fib,
			    const ip4_address_t *addr,
			    u32 len)
{
    uword * hash, * result;
    u32 key;

    key = (addr->data_u32 & ip4_main.fib_masks[len]);
    hash = fib->fib_entry_by_dst_address[len];
    result = hash_get (hash, key);

    if (NULL == result)
    {
	/*
	 * removing a non-existant entry. i'll allow it.
	 */
    }
    else 
    {
        uword *old_heap;

        old_heap = clib_mem_set_heap (ip4_main.mtrie_mheap);
	hash_unset(hash, key);
        clib_mem_set_heap (old_heap);
    }

    fib->fib_entry_by_dst_address[len] = hash;
}

void
ip4_fib_table_fwding_dpo_update (ip4_fib_t *fib,
				 const ip4_address_t *addr,
				 u32 len,
				 const dpo_id_t *dpo)
{
    ip4_fib_mtrie_route_add(&fib->mtrie, addr, len, dpo->dpoi_index);
}

void
ip4_fib_table_fwding_dpo_remove (ip4_fib_t *fib,
				 const ip4_address_t *addr,
				 u32 len,
				 const dpo_id_t *dpo,
                                 u32 cover_index)
{
    const fib_prefix_t *cover_prefix;
    const dpo_id_t *cover_dpo;

    /*
     * We need to pass the MTRIE the LB index and address length of the
     * covering prefix, so it can fill the plys with the correct replacement
     * for the entry being removed
     */
    cover_prefix = fib_entry_get_prefix(cover_index);
    cover_dpo = fib_entry_contribute_ip_forwarding(cover_index);

    ip4_fib_mtrie_route_del(&fib->mtrie,
                            addr, len, dpo->dpoi_index,
                            cover_prefix->fp_len,
                            cover_dpo->dpoi_index);
}

void
ip4_fib_table_walk (ip4_fib_t *fib,
                    fib_table_walk_fn_t fn,
                    void *ctx)
{
    fib_prefix_t root = {
        .fp_proto = FIB_PROTOCOL_IP4,
        // address and length default to all 0
    };

    /*
     * A full tree walk is the dengenerate case of a sub-tree from
     * the very root
     */
    return (ip4_fib_table_sub_tree_walk(fib, &root, fn, ctx));
}

void
ip4_fib_table_sub_tree_walk (ip4_fib_t *fib,
                             const fib_prefix_t *root,
                             fib_table_walk_fn_t fn,
                             void *ctx)
{
    fib_prefix_t *sub_trees = NULL;
    int i;

    /*
     * There is no efficent way to walk this array of hash tables.
     * so we walk each table with a mask length greater than and equal to
     * the required root and check it is covered by the root.
     */
    for (i = root->fp_len;
         i < ARRAY_LEN (fib->fib_entry_by_dst_address);
         i++)
    {
	uword * hash = fib->fib_entry_by_dst_address[i];

	if (NULL != hash)
	{
            ip4_address_t key;
	    hash_pair_t * p;

	    hash_foreach_pair (p, hash,
	    ({
                key.as_u32 = p->key;
                if (ip4_destination_matches_route(&ip4_main,
                                                  &key,
                                                  &root->fp_addr.ip4,
                                                  root->fp_len))
                {
                    const fib_prefix_t *sub_tree;
                    int skip = 0;

                    /*
                     * exclude sub-trees the walk does not want to explore
                     */
                    vec_foreach(sub_tree, sub_trees)
                    {
                        if (ip4_destination_matches_route(&ip4_main,
                                                          &key,
                                                          &sub_tree->fp_addr.ip4,
                                                          sub_tree->fp_len))
                        {
                            skip = 1;
                            break;
                        }
                    }

                    if (!skip)
                    {
                        switch (fn(p->value[0], ctx))
                        {
                        case FIB_TABLE_WALK_CONTINUE:
                            break;
                        case FIB_TABLE_WALK_SUB_TREE_STOP: {
                            fib_prefix_t pfx = {
                                .fp_proto = FIB_PROTOCOL_IP4,
                                .fp_len = i,
                                .fp_addr.ip4 = key,
                            };
                            vec_add1(sub_trees, pfx);
                            break;
                        }
                        case FIB_TABLE_WALK_STOP:
                            goto done;
                        }
                    }
                }
	    }));
	}
    }
done:
    vec_free(sub_trees);
    return;
}

/**
 * Walk show context
 */
typedef struct ip4_fib_show_walk_ctx_t_
{
    fib_node_index_t *ifsw_indicies;
} ip4_fib_show_walk_ctx_t;

static fib_table_walk_rc_t
ip4_fib_show_walk_cb (fib_node_index_t fib_entry_index,
                      void *arg)
{
    ip4_fib_show_walk_ctx_t *ctx = arg;

    vec_add1(ctx->ifsw_indicies, fib_entry_index);

    return (FIB_TABLE_WALK_CONTINUE);
}

static void
ip4_fib_table_show_all (ip4_fib_t *fib,
			vlib_main_t * vm)
{
    ip4_fib_show_walk_ctx_t ctx = {
        .ifsw_indicies = NULL,
    };
    fib_node_index_t *fib_entry_index;

    ip4_fib_table_walk(fib, ip4_fib_show_walk_cb, &ctx);
    vec_sort_with_function(ctx.ifsw_indicies,
                           fib_entry_cmp_for_sort);

    vec_foreach(fib_entry_index, ctx.ifsw_indicies)
    {
	vlib_cli_output(vm, "%U",
                        format_fib_entry,
                        *fib_entry_index,
                        FIB_ENTRY_FORMAT_BRIEF);
    }

    vec_free(ctx.ifsw_indicies);
}

static void
ip4_fib_table_show_one (ip4_fib_t *fib,
			vlib_main_t * vm,
			ip4_address_t *address,
			u32 mask_len,
                        int detail)
{    
    vlib_cli_output(vm, "%U",
                    format_fib_entry,
                    ip4_fib_table_lookup(fib, address, mask_len),
                    (detail ?
                     FIB_ENTRY_FORMAT_DETAIL2 :
                     FIB_ENTRY_FORMAT_DETAIL));
}

u8 *
format_ip4_fib_table_memory (u8 * s, va_list * args)
{
#if USE_DLMALLOC == 0
    s = format(s, "%=30s %=6d %=8ld\n",
               "IPv4 unicast",
               pool_elts(ip4_main.fibs),
               mheap_bytes(ip4_main.mtrie_mheap));
#else
    s = format(s, "%=30s %=6d %=8ld\n",
               "IPv4 unicast",
               pool_elts(ip4_main.fibs),
               mspace_footprint(ip4_main.mtrie_mheap));
#endif
    

    return (s);
}

static clib_error_t *
ip4_show_fib (vlib_main_t * vm,
	      unformat_input_t * input,
	      vlib_cli_command_t * cmd)
{
    ip4_main_t * im4 = &ip4_main;
    fib_table_t * fib_table;
    u64 total_mtrie_memory, total_hash_memory;
    int verbose, matching, mtrie, memory;
    ip4_address_t matching_address;
    u32 matching_mask = 32;
    int i, table_id = -1, fib_index = ~0;
    int detail = 0;

    verbose = 1;
    matching = mtrie = memory = 0;
    total_hash_memory = total_mtrie_memory = 0;

    while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
    {
	if (unformat (input, "brief") || unformat (input, "summary")
	    || unformat (input, "sum"))
	    verbose = 0;

	else if (unformat (input, "detail") || unformat (input, "det"))
	    detail = 1;

	else if (unformat (input, "mtrie"))
	    mtrie = 1;

        else if (unformat (input, "mem") ||
                 unformat (input, "memory"))
	    memory = 1;

	else if (unformat (input, "%U/%d",
			   unformat_ip4_address, &matching_address, &matching_mask))
	    matching = 1;

	else if (unformat (input, "%U", unformat_ip4_address, &matching_address))
	    matching = 1;

	else if (unformat (input, "table %d", &table_id))
	    ;
	else if (unformat (input, "index %d", &fib_index))
	    ;
	else
	    break;
    }

    pool_foreach (fib_table, im4->fibs,
    ({
	ip4_fib_t *fib = pool_elt_at_index(im4->v4_fibs, fib_table->ft_index);
        fib_source_t source;
        u8 *s = NULL;

	if (table_id >= 0 && table_id != (int)fib->table_id)
	    continue;
	if (fib_index != ~0 && fib_index != (int)fib->index)
	    continue;

        if (memory)
        {
            uword mtrie_size, hash_size;

            mtrie_size = ip4_fib_mtrie_memory_usage(&fib->mtrie);
            hash_size = 0;

	    for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++)
	    {
		uword * hash = fib->fib_entry_by_dst_address[i];
                if (NULL != hash)
                {
                    hash_size += hash_bytes(hash);
                }
            }
            if (verbose)
                vlib_cli_output (vm, "%U mtrie:%d hash:%d",
                                 format_fib_table_name, fib->index,
                                 FIB_PROTOCOL_IP4,
                                 mtrie_size,
                                 hash_size);
            total_mtrie_memory += mtrie_size;
            total_hash_memory += hash_size;
            continue;
        }

	s = format(s, "%U, fib_index:%d, flow hash:[%U] locks:[",
                   format_fib_table_name, fib->index,
                   FIB_PROTOCOL_IP4,
                   fib->index,
                   format_ip_flow_hash_config,
                   fib_table->ft_flow_hash_config);
	FOR_EACH_FIB_SOURCE(source)
        {
            if (0 != fib_table->ft_locks[source])
            {
                s = format(s, "%U:%d, ",
                           format_fib_source, source,
                           fib_table->ft_locks[source]);
            }
        }
        s = format (s, "]");
        vlib_cli_output (vm, "%v", s);
        vec_free(s);

	/* Show summary? */
	if (mtrie)
        {
	    vlib_cli_output (vm, "%U", format_ip4_fib_mtrie, &fib->mtrie, verbose);
            continue;
        }
	if (! verbose)
	{
	    vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count");
	    for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++)
	    {
		uword * hash = fib->fib_entry_by_dst_address[i];
		uword n_elts = hash_elts (hash);
		if (n_elts > 0)
		    vlib_cli_output (vm, "%20d%16d", i, n_elts);
	    }
	    continue;
	}

	if (!matching)
	{
	    ip4_fib_table_show_all(fib, vm);
	}
	else
	{
	    ip4_fib_table_show_one(fib, vm, &matching_address,
                                   matching_mask, detail);
	}
    }));

    if (memory)
        vlib_cli_output (vm, "totals: mtrie:%ld hash:%ld all:%ld",
                         total_mtrie_memory,
                         total_hash_memory,
                         total_mtrie_memory + total_hash_memory);

    return 0;
}

/*?
 * This command displays the IPv4 FIB Tables (VRF Tables) and the route
 * entries for each table.
 *
 * @note This command will run for a long time when the FIB tables are
 * comprised of millions of entries. For those senarios, consider displaying
 * a single table or summary mode.
 *
 * @cliexpar
 * Example of how to display all the IPv4 FIB tables:
 * @cliexstart{show ip fib}
 * ipv4-VRF:0, fib_index 0, flow hash: src dst sport dport proto
 * 0.0.0.0/0
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:0 buckets:1 uRPF:0 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 0.0.0.0/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:1 buckets:1 uRPF:1 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 6.0.1.2/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:30 buckets:1 uRPF:29 to:[0:0]]
 *     [0] [@3]: arp-ipv4: via 6.0.0.1 af_packet0
 * 7.0.0.1/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:31 buckets:4 uRPF:30 to:[0:0]]
 *     [0] [@3]: arp-ipv4: via 6.0.0.2 af_packet0
 *     [1] [@3]: arp-ipv4: via 6.0.0.2 af_packet0
 *     [2] [@3]: arp-ipv4: via 6.0.0.2 af_packet0
 *     [3] [@3]: arp-ipv4: via 6.0.0.1 af_packet0
 * 224.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:3 buckets:1 uRPF:3 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 240.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:2 buckets:1 uRPF:2 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 255.255.255.255/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:4 buckets:1 uRPF:4 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto
 * 0.0.0.0/0
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:12 buckets:1 uRPF:11 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 0.0.0.0/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:13 buckets:1 uRPF:12 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 172.16.1.0/24
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:17 buckets:1 uRPF:16 to:[0:0]]
 *     [0] [@4]: ipv4-glean: af_packet0
 * 172.16.1.1/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:18 buckets:1 uRPF:17 to:[1:84]]
 *     [0] [@2]: dpo-receive: 172.16.1.1 on af_packet0
 * 172.16.1.2/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:21 buckets:1 uRPF:20 to:[0:0]]
 *     [0] [@5]: ipv4 via 172.16.1.2 af_packet0: IP4: 02:fe:9e:70:7a:2b -> 26:a5:f6:9c:3a:36
 * 172.16.2.0/24
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:19 buckets:1 uRPF:18 to:[0:0]]
 *     [0] [@4]: ipv4-glean: af_packet1
 * 172.16.2.1/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:20 buckets:1 uRPF:19 to:[0:0]]
 *     [0] [@2]: dpo-receive: 172.16.2.1 on af_packet1
 * 224.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:15 buckets:1 uRPF:14 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 240.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:14 buckets:1 uRPF:13 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 255.255.255.255/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:16 buckets:1 uRPF:15 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * @cliexend
 * Example of how to display a single IPv4 FIB table:
 * @cliexstart{show ip fib table 7}
 * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto
 * 0.0.0.0/0
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:12 buckets:1 uRPF:11 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 0.0.0.0/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:13 buckets:1 uRPF:12 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 172.16.1.0/24
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:17 buckets:1 uRPF:16 to:[0:0]]
 *     [0] [@4]: ipv4-glean: af_packet0
 * 172.16.1.1/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:18 buckets:1 uRPF:17 to:[1:84]]
 *     [0] [@2]: dpo-receive: 172.16.1.1 on af_packet0
 * 172.16.1.2/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:21 buckets:1 uRPF:20 to:[0:0]]
 *     [0] [@5]: ipv4 via 172.16.1.2 af_packet0: IP4: 02:fe:9e:70:7a:2b -> 26:a5:f6:9c:3a:36
 * 172.16.2.0/24
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:19 buckets:1 uRPF:18 to:[0:0]]
 *     [0] [@4]: ipv4-glean: af_packet1
 * 172.16.2.1/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:20 buckets:1 uRPF:19 to:[0:0]]
 *     [0] [@2]: dpo-receive: 172.16.2.1 on af_packet1
 * 224.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:15 buckets:1 uRPF:14 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 240.0.0.0/8
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:14 buckets:1 uRPF:13 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * 255.255.255.255/32
 *   unicast-ip4-chain
 *   [@0]: dpo-load-balance: [index:16 buckets:1 uRPF:15 to:[0:0]]
 *     [0] [@0]: dpo-drop ip6
 * @cliexend
 * Example of how to display a summary of all IPv4 FIB tables:
 * @cliexstart{show ip fib summary}
 * ipv4-VRF:0, fib_index 0, flow hash: src dst sport dport proto
 *     Prefix length         Count
 *                    0               1
 *                    8               2
 *                   32               4
 * ipv4-VRF:7, fib_index 1, flow hash: src dst sport dport proto
 *     Prefix length         Count
 *                    0               1
 *                    8               2
 *                   24               2
 *                   32               4
 * @cliexend
 ?*/
/* *INDENT-OFF* */
VLIB_CLI_COMMAND (ip4_show_fib_command, static) = {
    .path = "show ip fib",
    .short_help = "show ip fib [summary] [table <table-id>] [index <fib-id>] [<ip4-addr>[/<mask>]] [mtrie] [detail]",
    .function = ip4_show_fib,
};
/* *INDENT-ON* */