Layer 3 routing program & IN keyword should support longest-prefix match

[adferguson]

As Rodrigo pointed out, our Layer 3 routing program:

ON ip_packet(pkt):
  DO forward(new) WHERE
    subnets(addr, mask, ANY, new.dlSrc, pkt.locSw, new.locPt, ANY)
    and pkt.nwDst IN addr/mask;

does not currently do longest-prefix matching, as a real router would do.

@tnelson -- probably we should make the semantics of IN match the longest prefix in the table. so this would be a change in how FIn is transformed, correct? currently it is just transformed to in_ipv4_range.

note that this is a change from how we currently handle multiple values coming from the table. in this case, multiple values returned by in_ipv4_range would then be further refined so that only the longest prefix matches.

[tnelson]

The trouble with changing the semantics of IN is that it'd mean explicitly saying which relation we were computing "longest" with respect to. Maybe it's better to add enough to Flowlog that the programmer can say "longest" on their own. Let's assume we have a "max" predicate. Then we can isolate the longest-prefix with something like:

max(mask, subnets(inaddr, mask,...) and pkt.nwDst IN inaddr/mask )

but then we need to write something kind of ugly to re-extract the addr we already found, if the max predicate is limited to one variable (it can maximize mask, but not carry the corresponding inaddr with it):

max(mask, subnets(inaddr, mask,...) and pkt.nwDst IN inaddr/mask ) and subnets(addr, mask, ...) and pkt.nwDst IN addr/mask

Something like that is likely good enough for now, though.

[adferguson]

I really like your idea to keep things separate! that gives the programmer flexibility to find overlapping subnets if they want that later. good call.

so, maybe something like IN (as we have now) and LONGEST IN which is syntactic sugar for what you wrote above? would that be easy to do? if so, that would be the best solution, I think!