IP addresses unreachable due to split/merge processing in (former implementation of) flow-filter

[qmonnet]

Let's consider the following peering (simplified syntax):

peerings:
  vpc1-to-vpc2:
    vpc1:
      ips: 10.0.2.0/24
    vpc2:
      ips: 20.0.0.0/24
  vpc1-to-vpc3:
    vpc1:
      ips:
        - 10.0.2.2/32
        - 10.0.2.3/32  # <- contiguous with 10.0.2.2/32, covered by 10.0.2.0/24
    vpc3:
      ips: 30.0.0.0/24

In the old flow-filter table we would end up with rules for both 10.0.2.2/31, and 10.0.2.2/32+10.0.2.3/32. Why? The bug is in the function that processes these prefixes for building the flow-filter context for vpc1. We call add_peering(), which in turns calls get_prefixes_for_processing(), which contains something like this:

    // Determine overlapping prefixes accross peerings
    let (local_manifests_overlap, remote_manifests_overlap) =
        get_manifests_overlap(overlay, vpc, peering, dst_vpcd, skip_ports);

    // Merge overlapping prefixes, when possible
    let overlap_trie = consolidate_overlap_list(local_manifests_overlap);

    // Now generate list of non-overlapping prefixes
    let local_prefixes = get_split_prefixes_for_manifest(
        &peering.local,
        &dst_vpcd,
        |expose| &expose.ips,
        overlap_trie,
        skip_ports,
    );

In other words:

1. Get the list of all overlapping prefixes exposed to vpc1. In our example, overlapping prefixes are 10.0.2.2/32 and 10.0.2.3/32.
2. Merge these prefixes together if possible, as an optimisation for the follow-up step: the overlap_trie list becomes 10.0.2.2/31, which makes sense.
3. We compute the list of prefixes to add to the context table: for every exposed prefix.

Step 3 compares to entries in the set of overlapping prefixes, and split if necessary; then add split prefixes to the list. This is relevant when building the context for vpc2, because 10.0.2.0/24 needs to be split into smaller subprefixes, but not for the context in vpc1.

What matters, however, is that function get_split_prefixes_for_manifest() does not do any merging of the exposed prefixes. So 10.0.2.2/32 and 10.0.2.3/32 are compared with the entries in overlap_trie, 10.0.2.2/31, and this leads to the creation of the entries for destination vpc3; but 10.0.2.2/32 and 10.0.2.3/32 are never merged together before creating this entry (only overlap_trie entries were merged, and they don't get added straight away to the list of processed prefixes), they're added directly to the list of processed prefixes.

By contrast, vpc3's prefix 10.0.2.0/24 gets split against 10.0.2.2/31, and this produces 10.0.2.2/31 (with multiple matches), and 10.0.2.0/31, 10.0.2.4/30, 10.0.2.8/29, ..., 10.0.2.128/25 (all single match) in the list of processed prefixes. That's where the 10.0.2.2/31 rule get added.

Workarounds:

1. Instead of writing 10.0.2.2/32 and 10.0.2.3/32 in the config, use 10.0.2.2/31. This works because then the prefixes are merged and there's no discrepancy.
2. Remove the merge step: overlap_trie gets bigger, resulting in more prefixes in the end (here, context for vpc3 will contain 10.0.2.2/32 and 10.0.2.3/32 as well instead of just 10.0.2.2/31).
3. Make sure everything is merged: this is the opposite way as 2). Merge prefixes when possible, either when validating the configuration (preferably) or when building the configuration.

In the end we didn't fix, and moved to a new implementation with
#1638

---

Note that we can also reproduce with the following setup:

peerings:
  vpc1-to-vpc2:
    vpc1:
      ips: 10.0.2.0/24
    vpc2:
      ips: 20.0.0.0/24
  vpc1-to-vpc3:
    vpc1:
      ips:
        - 10.0.2.4/31
        - 10.0.2.6/31
    vpc3:
      ips: 30.0.0.0/24

No /32, but consecutive /31s in the config. In the flow-filter context table:

        source: 10.0.2.4/30
          destination: 20.0.1.0/24, data:
            destination VPC: VNI(200), source NAT: -, destination NAT: -
          no remote default
        source: 10.0.2.4/31
          destination: 40.0.1.0/24, data:
            destination VPC: VNI(400), source NAT: -, destination NAT: -
          no remote default
        source: 10.0.2.6/31
          destination: 40.0.1.0/24, data:
            destination VPC: VNI(400), source NAT: -, destination NAT: -
          no remote default

So the issue happens when

• Two VPCs b and c expose overlapping prefixes to one given VPC a
• VPC b exposes mergeable (same-length, consecutive, and aligned) prefixes (10.0.2.2/32 and 10.0.2.3/32 work; 10.0.2.3/32 and 10.0.2.4/32 aren't in the same parent CIDR)
• VPC c's exposed prefix completely overlaps both consecutive prefixes exposed from b

[qmonnet]

Related test, on dataplane v0.20.2:

Details

#[test]
    fn test_issue_1693() {
        // Create a simple overlay with two VPCs and a peering
        let mut vpc_table = VpcTable::new();

        let vni1 = Vni::new_checked(100).unwrap();
        let vni2 = Vni::new_checked(200).unwrap();
        let vni3 = Vni::new_checked(300).unwrap();
        let vni4 = Vni::new_checked(400).unwrap();

        let mut vpc1 = Vpc::new("vpc1", "VPC01", vni1.as_u32()).unwrap();
        let vpc2 = Vpc::new("vpc2", "VPC02", vni2.as_u32()).unwrap();
        let vpc3 = Vpc::new("vpc3", "VPC03", vni3.as_u32()).unwrap();
        let vpc4 = Vpc::new("vpc4", "VPC04", vni4.as_u32()).unwrap();

        vpc1.peerings.push(Peering {
            name: "vpc1-to-vpc2".to_string(),
            local: VpcManifest::with_exposes(
                "vpc1-local",
                vec![VpcExpose::empty().ip("10.0.2.0/24".into())],
            ),
            remote: VpcManifest::with_exposes(
                "vpc2-remote",
                vec![VpcExpose::empty().ip("20.0.1.0/24".into())],
            ),
            remote_id: "VPC02".try_into().unwrap(),
            gwgroup: None,
        });

        vpc1.peerings.push(Peering {
            name: "vpc1-to-vpc3".to_string(),
            local: VpcManifest::with_exposes(
                "vpc1-local",
                vec![VpcExpose::empty().ip("10.0.2.0/24".into())],
            ),
            remote: VpcManifest::with_exposes(
                "vpc3-remote",
                vec![VpcExpose::empty().ip("30.0.1.0/24".into())],
            ),
            remote_id: "VPC03".try_into().unwrap(),
            gwgroup: None,
        });

        vpc1.peerings.push(Peering {
            name: "vpc1-to-vpc4".to_string(),
            local: VpcManifest::with_exposes(
                "vpc1-local",
                vec![
                    VpcExpose::empty()
                        .ip("10.0.2.2/32".into())
                        .ip("10.0.2.3/32".into())
                        .ip("10.0.2.4/32".into())
                        .ip("10.0.2.5/32".into())
                        .ip("10.0.2.6/32".into())
                        .ip("10.0.2.8/32".into()),
                ],
            ),
            remote: VpcManifest::with_exposes(
                "vpc4-remote",
                vec![VpcExpose::empty().ip("40.0.1.0/24".into())],
            ),
            remote_id: "VPC04".try_into().unwrap(),
            gwgroup: None,
        });

        vpc_table.add(vpc1).unwrap();
        vpc_table.add(vpc2).unwrap();
        vpc_table.add(vpc3).unwrap();
        vpc_table.add(vpc4).unwrap();

        let overlay = Overlay {
            vpc_table,
            peering_table: VpcPeeringTable::new(),
        };

        let result = FlowFilterTable::build_from_overlay(&overlay);
        assert!(result.is_ok());

        let table = result.unwrap();
        println!("{table}");
        panic!()
    }

[qmonnet]

As mentioned above, it's no longer present in main since we switched to the new flow-filter implementation with #1638.

We also added a regression test with #1680.