Make maps implementation be cross-platform

[dthaler]

This is to track making the core maps implementation in src/ebpf/libs/maps/ebpf_maps.c not be Windows specific, so the same code can be used on Windows, Linux, etc. This might entail upstreaming it to the generic-ebpf project for example.

[dthaler]

In PR #15, @Alan-Jowett states:

Long term goal would be to switch to using generic-ebpf library, but due to generic-ebpf dependency on concurrency kit (which only builds with GCC), we can't use generic-ebpf yet.

[Alan-Jowett]

Goal of this project is to only support Windows. Any code that could be generic should be moved to a more generic project and pulled in via a sub-module.

[YutaroHayakawa]

Hi, here's the author of generic-ebpf. Let me left some comments based on my implementation experience. I’m appreciate if it can help you.

[YutaroHayakawa]

Seems like current map implementation is using in-place spinlock to get map element.

https://github.com/microsoft/ebpf-for-windows/blame/2b2ea62deee534ecee1bcf2a72bdc6b5964f681f/libs/execution_context/ebpf_maps.c#L251-L255

Is there any plan to move this on to RCU or EBR/QSBR implementation? Otherwide I think it will cause the use-after-free with some scenario like this.

// In eBPF program
elem = bpf_map_lookup_elem(&k);  // hash map
// User space program or other eBPF program deletes the element in here
elem->counter++;  // use after free

Actually, I did exactly the same thing before. Linux eBPF program is basically assumed to be run inside the RCU critical section, so they can delay the reclamation of the memory to after all of the eBPF program finish using it. This is why the generic-ebpf kernel implementations depend on the Epoch or RCU.

[Alan-Jowett]

We had planned on using generic-ebpf, but the issue is that concurrency kit depends on a lot of GCC specific compiler features that aren't present in the MSVC compiler. Porting concurrencykit seems too risky.

Our map implementation relies on our own version of epoch tracking:

ebpf-for-windows/libs/execution_context/ebpf_maps.c

Line 210 in 656e7be

retval = ebpf_hash_table_create(

Which then uses:

ebpf-for-windows/libs/platform/ebpf_epoch.c

Line 263 in c476179

ebpf_epoch_free(void* memory)

Our epoch tracker works like this:

1. Every thread and/or CPU captures the epoch it's executing in.
2. On free, memory is tagged with the epoch it was freed in.
3. Memory is released back to the system when there are no more threads or CPU's on that epoch.

[Alan-Jowett]

Description of how the epoch tracker works is here:

ebpf-for-windows/libs/platform/ebpf_epoch.c

Line 7 in 656e7be

// Brief summary of how epoch tracking works.

[YutaroHayakawa]

Ah, sorry I was missing that code. Thanks for your explanation!

[YutaroHayakawa]

Do you have any plan to implement per-cpu variants of the maps? If yes, I'm interested in how you guys trying to implement it in user space (I couldn't come up with the way to implement it in preemptable environment).

[Alan-Jowett]

Yes, we are planning to add per-cpu variants. Our goal is to maintain parity with the libbpf API's, so we are planning to match the behavior of bpf_map_lookup_elem.

Do you happen to know what bpf_map_lookup_elem does for per-CPU maps?

[YutaroHayakawa]

Yes, in Linux, from bpf(2), it fetches all elements for each CPUs at once.

What I was mentioning here is the case the eBPF program running on userspace calls the bpf_map_lookup_elem helper. Maybe it is out of the scope of this project?

[Alan-Jowett]

I think the current plan would be to have our API return the value for each CPU as well then.

[Alan-Jowett]

@YutaroHayakawa do you happen to have any contact with the ConcurrencyKit team? If we could get a port of CK to Windows/Visual Studio, then I think we can get closer to adopting generic-ebpf map implementation.

[YutaroHayakawa]

Unfortunately, I don't have...

[dthaler]

Closing for now due to no progress or immediate way to make progress on this.
Fine to reopen if/when a possible way forward is known.