| Message ID | 20181125180919.13996-2-aconole@bytheb.org |
|---|---|
| State | RFC |
| Delegated to: | Pablo Neira |
| Headers | show |
| Series | netfilter: expose flow offload tables as an ebpf map | expand |
On Sun, Nov 25, 2018 at 01:09:17PM -0500, Aaron Conole wrote: > This commit allows for map operations to be loaded by an lkm, rather than > needing to be baked into the kernel at compile time. Nack. Please see Documentation/bpf/bpf_design_QA.rst
Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > On Sun, Nov 25, 2018 at 01:09:17PM -0500, Aaron Conole wrote: >> This commit allows for map operations to be loaded by an lkm, rather than >> needing to be baked into the kernel at compile time. > > Nack. > Please see Documentation/bpf/bpf_design_QA.rst Thanks for the review, Alexei! I hadn't been aware of this doc, so it's good to read through it. I see that the following is there: Q: New functionality via kernel modules? ---------------------------------------- Q: Can BPF functionality such as new program or map types, new helpers, etc be added out of kernel module code? A: NO. So, I think that means that even changing the helpers would be of no value (since it would only be useful in the event that the kernel were compiled with netfilter linked in, rather than as a module - and I doubt there's any place where that would be true). BUT, as I wrote in my cover I have some alternative approaches that I've thought about, and I'm listing here. Can you let me know if any would be acceptable? If none are, is there an alternative approach you would support? 1. Introduce flowmap again, this time, basically having it close to a copy of the hashmap. Introduce a few function calls that allow an external module to easily manipulate all maps of that type to insert / remove / update entries. This makes it similar to, for example, devmap. 2. Introduce a way to share maps between modules. IE: something like bpf_helper_expose_map(map_id, module_name). Then have netfilter and eBPF share access to the hashmap. Netfilter and the ebpf program will need to agree on the key and value size, and will push data in/out. 3. Introduce an xdp/ebpf hook in the flowmap. IE: nft add flowmap xx { .program=foo.o } Then that will be called with a context, and can update a shared map with userspace. I haven't though out all the logistics on how to do this, but it would put the onus of sharing the information on the bpf program writer. What do you think?
On Tue, Nov 27, 2018 at 09:24:05AM -0500, Aaron Conole wrote: > > 1. Introduce flowmap again, this time, basically having it close to a > copy of the hashmap. Introduce a few function calls that allow an > external module to easily manipulate all maps of that type to insert > / remove / update entries. This makes it similar to, for example, > devmap. what is a flowmap? How is this flowmap different from existing hash, lpm and lru maps? 'close to a copy of hashmap'... why hashmap is not enough for your purpose?
Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > On Tue, Nov 27, 2018 at 09:24:05AM -0500, Aaron Conole wrote: >> >> 1. Introduce flowmap again, this time, basically having it close to a >> copy of the hashmap. Introduce a few function calls that allow an >> external module to easily manipulate all maps of that type to insert >> / remove / update entries. This makes it similar to, for example, >> devmap. > > what is a flowmap? > How is this flowmap different from existing hash, lpm and lru maps? The biggest difference is how relationship works. Normal map would have single key and single value. Flow map needs to have two keys "single-value," because there are two sets of flow tuples to track (forward and reverse direction). That means that when updating the k-v pairs, we need to ensure that the data is always consistent and up to date. Probably we could do that with the existing maps if we had some kind of allocation mechanism, too (so, keep a pointer to data from two keys - not sure if there's a way to do that in ebpf)? Still I need a way to get the conntrack information from netfilter (or really any other entity that will provide it) into the bpf map, whatever map type it takes. > 'close to a copy of hashmap'... why hashmap is not enough for your purpose? It might be (see the item 2. in that list). I'm trying to allow netfilter conntrack to update the bpf map so that the flow offload data is available, and make sure that when I look up a 5-tuple from the bpf program in the map, I get the appropriate flow-offload data (ie: forward direction addresses could be different from reverse direction so just swapping addresses / ports will not match). Like I wrote in the cover letter (but probably poorly, sorry for that), I want to forward packets into the stack until a connection is added to the table, and then push the packets directly to the places they need to go, doing the nat etc. That lets us use xdp as a fast forwarding path for connections, getting all of the advantage of helper modules to do the control / parsing, and all the advantage of xdp for packet movement. Maybe I don't see a better solution, though - or possibly there's a more generic approach that works better.
On Wed, Nov 28, 2018 at 01:51:42PM -0500, Aaron Conole wrote: > Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > > > On Tue, Nov 27, 2018 at 09:24:05AM -0500, Aaron Conole wrote: > >> > >> 1. Introduce flowmap again, this time, basically having it close to a > >> copy of the hashmap. Introduce a few function calls that allow an > >> external module to easily manipulate all maps of that type to insert > >> / remove / update entries. This makes it similar to, for example, > >> devmap. > > > > what is a flowmap? > > How is this flowmap different from existing hash, lpm and lru maps? > > The biggest difference is how relationship works. Normal map would > have single key and single value. Flow map needs to have two keys > "single-value," because there are two sets of flow tuples to track > (forward and reverse direction). That means that when updating the k-v > pairs, we need to ensure that the data is always consistent and up to > date. Probably we could do that with the existing maps if we had some > kind of allocation mechanism, too (so, keep a pointer to data from two > keys - not sure if there's a way to do that in ebpf)? just swap the src/dst ips inside bpf program depending on direction and use the same hash map. That's what xdp/bpf users already do pretty successfully. bpf hash map is already offloaded into hw too. > forward direction addresses could be different from reverse direction so > just swapping addresses / ports will not match). That makes no sense to me. What would be an example of such flow? Certainly not a tcp flow. > That lets us use xdp as a fast forwarding path for > connections, getting all of the advantage of helper modules to do the > control / parsing, and all the advantage of xdp for packet movement. From 10k feet view it sounds correct, but details make no sense. You're saying doing nat in the stack, but that _is_ the packet movement where you wanted to use xdp.
Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > On Wed, Nov 28, 2018 at 01:51:42PM -0500, Aaron Conole wrote: >> Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: >> >> > On Tue, Nov 27, 2018 at 09:24:05AM -0500, Aaron Conole wrote: >> >> >> >> 1. Introduce flowmap again, this time, basically having it close to a >> >> copy of the hashmap. Introduce a few function calls that allow an >> >> external module to easily manipulate all maps of that type to insert >> >> / remove / update entries. This makes it similar to, for example, >> >> devmap. >> > >> > what is a flowmap? >> > How is this flowmap different from existing hash, lpm and lru maps? >> >> The biggest difference is how relationship works. Normal map would >> have single key and single value. Flow map needs to have two keys >> "single-value," because there are two sets of flow tuples to track >> (forward and reverse direction). That means that when updating the k-v >> pairs, we need to ensure that the data is always consistent and up to >> date. Probably we could do that with the existing maps if we had some >> kind of allocation mechanism, too (so, keep a pointer to data from two >> keys - not sure if there's a way to do that in ebpf)? > > just swap the src/dst ips inside bpf program depending on direction > and use the same hash map. That won't work. I'll explain below. > That's what xdp/bpf users already do pretty successfully. > bpf hash map is already offloaded into hw too. While this is one reason to use hash map, I don't think we should use this as a reason to exclude development of a data type that may work better. After all, if we can do better then we should. >> forward direction addresses could be different from reverse direction so >> just swapping addresses / ports will not match). > > That makes no sense to me. What would be an example of such flow? > Certainly not a tcp flow. Maybe it's poorly worded on my part. Think about this scenario (ipv4, tcp): Interfaces A(internet), B(lan) When XDP program receives a packet from B, it will have a tuple like: source=B-subnet:B-port dest=inet-addr:inet-port When XDP program receives a packet from A, it will have a tuple like: source=inet-addr:inet-port dest=gw-addr:gw-port The only data in common there is inet-addr:inet-port, and that will likely be shared among too many connections to be a valid key. I don't know how to figure out from A the same connetion that corresponds to B. A really simple static map works, *except*, when something causes either side of the connection to become invalid, I can't mark the other side. For instance, even if I have some static mapping, I might not be able to infer the correct B-side tuple from the A-side tuple to do the teardown. I might too naive to see the right approach though - maybe I'm over-complicating something? >> That lets us use xdp as a fast forwarding path for >> connections, getting all of the advantage of helper modules to do the >> control / parsing, and all the advantage of xdp for packet movement. > > From 10k feet view it sounds correct, but details make no sense. > You're saying doing nat in the stack, but that _is_ the packet movement > where you wanted to use xdp. The thing I want to use the stack for are things that will always be slow anyway, or require massive system input to do correctly. Here are some examples: 1. Port / address reservation. If I want to do NAT, I need to reserve ports and addresses correctly. That requires knowing the interface addresses, and which addresses are currently allocated. The stack knows this already, let it do these allocations then. Then when packets arrive for the connection that the stack set up, just forward via XDP. 2. Helpers. Parsing an in-flight stream is always going to be slow. Let the stack do that. But when it sets up an expectation, then use that information to forward that via XDP. So I would use the stack for the initial handshakes. Once the handshake is complete, and we know where the packet is destined to go, all that data is shoved into a map that the XDP program can access, and we do the data forwarding. Hope it helps.
On Fri, Nov 30, 2018 at 08:49:17AM -0500, Aaron Conole wrote: > > While this is one reason to use hash map, I don't think we should use > this as a reason to exclude development of a data type that may work > better. After all, if we can do better then we should. I'm all for improving existing hash map or implementing new data types. Like classifier map == same as wild-card match map == ACL map. The one that OVS folks could use and other folks wanted for long time. But I don't want bpf to become a collection of single purpose solutions. Like mega-flow style OVS map. That one does linear number of lookups applying mask at a time. It sounds to me that you're proposing "NAT-as-bpf-helper" or "NAT-as-bpf-map" type of solution. That falls into single purpose solution category. I'd rather see generic connection tracking building block. The one that works out of skb and out of XDP layer. Existing stack-queue-map can already be used to allocate integers out of specified range. It can be used to implement port allocation for NAT. If generic stack-queue-map is not enough, let's improve it. > >> forward direction addresses could be different from reverse direction so > >> just swapping addresses / ports will not match). > > > > That makes no sense to me. What would be an example of such flow? > > Certainly not a tcp flow. > > Maybe it's poorly worded on my part. Think about this scenario (ipv4, tcp): > > Interfaces A(internet), B(lan) > > When XDP program receives a packet from B, it will have a tuple like: > > source=B-subnet:B-port dest=inet-addr:inet-port > > When XDP program receives a packet from A, it will have a tuple like: > > source=inet-addr:inet-port dest=gw-addr:gw-port first of all there are two netdevs. one XDP program can attach to multiple netdevs, but in this case we're dealing with two indepedent tcp flows. > The only data in common there is inet-addr:inet-port, and that will > likely be shared among too many connections to be a valid key. two independent tcp flows don't make a 'connection'. That definition of connection is only meaningful in the context of the particular problem you're trying to solve and confuses me quite a bit. > I don't know how to figure out from A the same connetion that > corresponds to B. A really simple static map works, *except*, when > something causes either side of the connection to become invalid, I > can't mark the other side. For instance, even if I have some static > mapping, I might not be able to infer the correct B-side tuple from the > A-side tuple to do the teardown. I don't think I got enough information from the above description to understand why two tcp flows (same as two tcp connections) will form single 'connection' in your definition of connection. > 1. Port / address reservation. If I want to do NAT, I need to reserve > ports and addresses correctly. That requires knowing the interface > addresses, and which addresses are currently allocated. The stack > knows this already, let it do these allocations then. Then when > packets arrive for the connection that the stack set up, just forward > via XDP. I beg to disagree. For NAT use case the stack has nothing to do with port allocation for NATing. It's all within NAT framework (whichever way it's implemented). The stack cares about sockets and ports that are open on the host to be consumed by the host. NAT function is independent of that. > 2. Helpers. Parsing an in-flight stream is always going to be slow. > Let the stack do that. But when it sets up an expectation, then use > that information to forward that via XDP. XDP parses packets way faster than the stack, since XDP deals with linear buffers whereas stack has to do pskb_may_pull at every step. The stack can be optimized further, but assuming that packet parsing by the stack is faster than XDP and making techincal decisions based on that just doesn't seem like the right approach to take.
Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > On Fri, Nov 30, 2018 at 08:49:17AM -0500, Aaron Conole wrote: >> >> While this is one reason to use hash map, I don't think we should use >> this as a reason to exclude development of a data type that may work >> better. After all, if we can do better then we should. > > I'm all for improving existing hash map or implementing new data types. > Like classifier map == same as wild-card match map == ACL map. > The one that OVS folks could use and other folks wanted for long time. > > But I don't want bpf to become a collection of single purpose solutions. > Like mega-flow style OVS map. > That one does linear number of lookups applying mask at a time. > > It sounds to me that you're proposing "NAT-as-bpf-helper" > or "NAT-as-bpf-map" type of solution. Maybe that's what this particular iteration is. But I'm open to a different implementation. My requirements aren't fixed to a specific map type. > That falls into single purpose solution category. > I'd rather see generic connection tracking building block. > The one that works out of skb and out of XDP layer. > Existing stack-queue-map can already be used to allocate integers > out of specified range. It can be used to implement port allocation for NAT. > If generic stack-queue-map is not enough, let's improve it. I don't understand this. You say you want something out of skb and out of xdp layer, but then advocate an ebpf approach (that would only be useful from xdp). Plus already some specialized mechanism exists for FIB. Not sure why this conntrack assist would be rejected as too specialized? I was thinking to re-use existing conntrack framework, and make the metadata available from ebpf context. That can be used even out of xdp layer (for instance, maybe some tracing program, or other accounting / auditing tool like a HIDS). Anyway, as I wrote, there are other approaches. But maybe instead of a flowmap, an mkmap would make sense (this is a multi-key map, that allows a single value to be reached via multiple keys). I also wrote some other approaches I was thinking in an earlier mail. Maybe one of those is better direction? >> >> forward direction addresses could be different from reverse direction so >> >> just swapping addresses / ports will not match). >> > >> > That makes no sense to me. What would be an example of such flow? >> > Certainly not a tcp flow. >> >> Maybe it's poorly worded on my part. Think about this scenario (ipv4, tcp): >> >> Interfaces A(internet), B(lan) >> >> When XDP program receives a packet from B, it will have a tuple like: >> >> source=B-subnet:B-port dest=inet-addr:inet-port >> >> When XDP program receives a packet from A, it will have a tuple like: >> >> source=inet-addr:inet-port dest=gw-addr:gw-port > > first of all there are two netdevs. > one XDP program can attach to multiple netdevs, but in this > case we're dealing with two indepedent tcp flows. > >> The only data in common there is inet-addr:inet-port, and that will >> likely be shared among too many connections to be a valid key. > > two independent tcp flows don't make a 'connection'. > That definition of connection is only meaningful in the context > of the particular problem you're trying to solve and > confuses me quite a bit. I don't understand this. They aren't independent. We need to properly account the packets, and need to apply policy decisions to either side. Just because the tuples are asymmetric, the connection *is* the same. If you treat them separately, then you lose the ability for accounting them properly. Something needs to make the association. >> I don't know how to figure out from A the same connetion that >> corresponds to B. A really simple static map works, *except*, when >> something causes either side of the connection to become invalid, I >> can't mark the other side. For instance, even if I have some static >> mapping, I might not be able to infer the correct B-side tuple from the >> A-side tuple to do the teardown. > > I don't think I got enough information from the above description to > understand why two tcp flows (same as two tcp connections) will > form single 'connection' in your definition of connection. They aren't two connections. Maybe there's something I'm missing. >> 1. Port / address reservation. If I want to do NAT, I need to reserve >> ports and addresses correctly. That requires knowing the interface >> addresses, and which addresses are currently allocated. The stack >> knows this already, let it do these allocations then. Then when >> packets arrive for the connection that the stack set up, just forward >> via XDP. > > I beg to disagree. For NAT use case the stack has nothing to do with > port allocation for NATing. It's all within NAT framework > (whichever way it's implemented). > The stack cares about sockets and ports that are open on the host > to be consumed by the host. > NAT function is independent of that. It's related. If host has a particular port open, NAT can't reuse it if NATing from a host IP. So the NAT port allocation *must* take into account host ports. >> 2. Helpers. Parsing an in-flight stream is always going to be slow. >> Let the stack do that. But when it sets up an expectation, then use >> that information to forward that via XDP. > > XDP parses packets way faster than the stack, since XDP deals with linear > buffers whereas stack has to do pskb_may_pull at every step. Sure. > The stack can be optimized further, but assuming that packet parsing > by the stack is faster than XDP and making techincal decisions based > on that just doesn't seem like the right approach to take. Agreed that packet parsing can be faster in XDP. But my point is, packet parsing is *slow* no matter what. And the DPI required to implement helpers is complex and slow. The instant you need to parse H.323 or some kind of SIP logic to implement conntrack helper you will run out of instructions and tailcall iterations in eBPF. Even simple FTP parsing might not be 'good enough' from a throughput standpoint. The idea here is for control kinds of connections to traverse the stack (since throughput isn't gating factor there), and the data connections (which need maximum throughput) can just be switched via the xdp mechanism.
diff --git a/include/linux/bpf.h b/include/linux/bpf.h index 33014ae73103..bf4531f076ca 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -553,6 +553,7 @@ static inline int bpf_map_attr_numa_node(const union bpf_attr *attr) struct bpf_prog *bpf_prog_get_type_path(const char *name, enum bpf_prog_type type); int array_map_alloc_check(union bpf_attr *attr); +void bpf_map_insert_ops(size_t id, const struct bpf_map_ops *ops); #else /* !CONFIG_BPF_SYSCALL */ static inline struct bpf_prog *bpf_prog_get(u32 ufd) @@ -665,6 +666,11 @@ static inline struct bpf_prog *bpf_prog_get_type_path(const char *name, { return ERR_PTR(-EOPNOTSUPP); } + +static inline void bpf_map_insert_ops(size_t id, + const struct bpf_map_ops *ops) +{ +} #endif /* CONFIG_BPF_SYSCALL */ static inline struct bpf_prog *bpf_prog_get_type(u32 ufd, diff --git a/init/Kconfig b/init/Kconfig index a4112e95724a..aa4eb98af656 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1489,6 +1489,14 @@ config BPF_JIT_ALWAYS_ON Enables BPF JIT and removes BPF interpreter to avoid speculative execution of BPF instructions by the interpreter +config BPF_LOADABLE_MAPS + bool "Allow map types to be loaded with modules" + depends on BPF_SYSCALL && MODULES + help + Enables BPF map types to be provided by loadable modules + instead of always compiled in. Maps provided dynamically + may only be used by super users. + config USERFAULTFD bool "Enable userfaultfd() system call" select ANON_INODES diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index cf5040fd5434..fa1db9ab81e1 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -49,6 +49,8 @@ static DEFINE_SPINLOCK(map_idr_lock); int sysctl_unprivileged_bpf_disabled __read_mostly; +const struct bpf_map_ops loadable_map = {}; + static const struct bpf_map_ops * const bpf_map_types[] = { #define BPF_PROG_TYPE(_id, _ops) #define BPF_MAP_TYPE(_id, _ops) \ @@ -58,6 +60,15 @@ static const struct bpf_map_ops * const bpf_map_types[] = { #undef BPF_MAP_TYPE }; +static const struct bpf_map_ops * bpf_loadable_map_types[] = { +#define BPF_PROG_TYPE(_id, _ops) +#define BPF_MAP_TYPE(_id, _ops) \ + [_id] = NULL, +#include <linux/bpf_types.h> +#undef BPF_PROG_TYPE +#undef BPF_MAP_TYPE +}; + /* * If we're handed a bigger struct than we know of, ensure all the unknown bits * are 0 - i.e. new user-space does not rely on any kernel feature extensions @@ -105,6 +116,48 @@ const struct bpf_map_ops bpf_map_offload_ops = { .map_check_btf = map_check_no_btf, }; +/* + * Fills in the modular ops map, provided that the entry is not already + * filled, and that the caller has CAP_SYS_ADMIN. */ +void bpf_map_insert_ops(size_t id, const struct bpf_map_ops *ops) +{ +#ifdef CONFIG_BPF_LOADABLE_MAPS + if (!capable(CAP_SYS_ADMIN)) + return; + + if (id >= ARRAY_SIZE(bpf_loadable_map_types)) + return; + + id = array_index_nospec(id, ARRAY_SIZE(bpf_loadable_map_types)); + if (bpf_loadable_map_types[id] == NULL) + bpf_loadable_map_types[id] = ops; +#endif +} +EXPORT_SYMBOL_GPL(bpf_map_insert_ops); + +static const struct bpf_map_ops *find_loadable_ops(u32 type) +{ + struct user_struct *user = get_current_user(); + const struct bpf_map_ops *ops = NULL; + + if (user->uid.val) + goto done; + +#ifdef CONFIG_BPF_LOADABLE_MAPS + if (!capable(CAP_SYS_ADMIN)) + goto done; + + if (type >= ARRAY_SIZE(bpf_loadable_map_types)) + goto done; + type = array_index_nospec(type, ARRAY_SIZE(bpf_loadable_map_types)); + ops = bpf_loadable_map_types[type]; +#endif + +done: + free_uid(user); + return ops; +} + static struct bpf_map *find_and_alloc_map(union bpf_attr *attr) { const struct bpf_map_ops *ops; @@ -115,7 +168,8 @@ static struct bpf_map *find_and_alloc_map(union bpf_attr *attr) if (type >= ARRAY_SIZE(bpf_map_types)) return ERR_PTR(-EINVAL); type = array_index_nospec(type, ARRAY_SIZE(bpf_map_types)); - ops = bpf_map_types[type]; + ops = (bpf_map_types[type] != &loadable_map) ? bpf_map_types[type] : + find_loadable_ops(type); if (!ops) return ERR_PTR(-EINVAL); @@ -180,6 +234,7 @@ int bpf_map_precharge_memlock(u32 pages) return -EPERM; return 0; } +EXPORT_SYMBOL_GPL(bpf_map_precharge_memlock); static int bpf_charge_memlock(struct user_struct *user, u32 pages) {
This commit allows for map operations to be loaded by an lkm, rather than needing to be baked into the kernel at compile time. Signed-off-by: Aaron Conole <aconole@bytheb.org> --- include/linux/bpf.h | 6 +++++ init/Kconfig | 8 +++++++ kernel/bpf/syscall.c | 57 +++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 70 insertions(+), 1 deletion(-)