Re: stap/eBPF language features brainstorm

[Serhei Makarov <serhei at fastmail dot com>]

On Wed, Jul 11, 2018, at 4:13 PM, Serhei Makarov wrote:
> (1) A BPF_MAP_TYPE_PERCPU would be a contiguously indexed, preallocated 
> array of aggregates, so a BPF_MAP_TYPE_HASH would be needed to map from 
> sparse keys to indices into the BPF_MAP_TYPE_PERCPU. However, without 
> synchronization, there is no way to allocate slots in the 
> BPF_MAP_TYPE_PERCPU.

Note that eBPF does have an atomic increment operation in the form of BPF_XADD.
If it returned the value at the memory location (either before or after the increment)
like a compare-and-swap operation, then it could be used to allocate array slots
in a thread-safe fashion.

Alas, I can't find any indication in the docs that a value is returned. Rather, the in-kernel
testsuite (https://github.com/torvalds/linux/blob/4e33d7d47943aaa84a5904472cf2f9c6d6b0a6ca/lib/test_bpf.c#L4306)
specifies that there should be no side-effects (as far as I can decipher the testcases).
The purpose of BPF_XADD seems to be to make sure that two increment operations
don't 'cancel each other out' by racing to read the same memory location.

For example, see the sample eBPF program in
 http://www.man7.org/linux/man-pages/man2/bpf.2.html
-- which contains the following atomic increment of a counter:

BPF_XADD(BPF_DW, BPF_REG_0, BPF_REG_1, 0, 0), /* lock *(u64 *) r0 += r1 */
 
> (2) /usr/include/linux/bpf.h mentions BPF_MAP_TYPE_HASH_OF_MAPS, but 
> it's currently undocumented. Still need to read the code and investigate 
> if it works for our purposes.

This might still be an option.

> # Global variable locking semantics
> 
> Apparently not possible due to upstream eBPF limitations. I could not 
> find any compare-and-swap-type operation for map elements. (bcc's 
> lookup_or_init() compiles to code with potential to data-race. The only 
> map modification helpers are lookup_elem, update_elem, and delete_elem, 
> and any compare-and-swap code constructed from them will be subject to 
> data races.)

As suggested by Frank, we could implement probe exclusion with a sequence
such as the following:

BPF_XADD(&lock_counter, 1);
value = read(lock_counter);
if (value <= 1) { ... execute probe ... } else skip probe
BPF_XADD(&lock_counter, -1);

In this case, it is possible for two probes to *both* cancel each other's execution,
but it should not be possible for two probes to execute simultaneously.
Will need to test how well this works in practice (i.e. how likely are two probes
to mutually cancel?)