Hypothesis: _ebpf_hash_table_replace_bucket bloats epoch free list

[Alan-Jowett]

Hypothesis: Under very high rates of hash bucket collision, _ebpf_hash_table_replace_bucket adds large numbers of entries to the eBPF epoch free list when they could be directly freed (because they have not been seen by anyone outside this thread context).

This shows up as the eBPF epoch flush timer getting backlogged with a very long list of items to be freed. If the collisions continue, the system will eventually run out of memory.

Option 1:
Add API to epoch code to directly free (as opposed to delay-free) memory.
If ebpf_interlocked_compare_exchange_pointer returns failure, the directly free bucket (don't insert in delay-free list).

Option 2:
Add a look-aside list for hashtable buckets.
Pull from look-aside list first (allocate if empty).
If ebpf_interlocked_compare_exchange_pointer returns failure, insert bucket into look-aside list (don't insert in delay-free list).

[Alan-Jowett]

I ran an experiment to test this hypothesis.

Test parameters

1. Modified hash_table_stress_test to set bucket_count == CPU count * keys per thread (which would give a hash table load of 100%) and increased iterations to 10K.
2. Created free_bucket_list (a InterlockedSList ) that stores that stores buckets that ebpf_interlocked_compare_exchange_pointer rejected during _ebpf_hash_table_replace_bucket.
3. Applied change to partition the epoch thread lock (ebpf_epoch's _ebpf_epoch_thread_table_lock causes significant contention #417)
4. Measure:
   a) Total number of buckets allocated - free_bucket_list_alloc
   b) Number of buckets allocated from free_bucket_list - free_bucket_list_hit
   c) Number of buckets that are larger than cache size - free_bucket_list_too_small
   d) Number of times ebpf_interlocked_compare_exchange_pointer rejected the update - compare_exchange_miss

Results

	Name	Value	Type
◢	table	0x0000029dbc406ab0 {free_bucket_list={Alignment=3420979200 Region=0 HeaderX64={Depth=0 Sequence=52200 ...} } ...}	_ebpf_hash_table *
	▶ free_bucket_list	{Alignment=3420979200 Region=0 HeaderX64={Depth=0 Sequence=52200 Reserved=0 ...} }	_SLIST_HEADER
	free_bucket_list_alloc	996130	__int64
	free_bucket_list_hit	52200	__int64
	free_bucket_list_too_small	0	__int64
	compare_exchange_miss	52200	__int64
	bucket_count	64	unsigned int
	entry_count	0	volatile int
	seed	1818999625	unsigned int
	key_size	4	unsigned __int64
	value_size	8	unsigned __int64
	allocate	0x00007ff65d7386e0 {unit_tests.exe!ebpf_epoch_allocate(unsigned __int64)}	void ()(unsigned __int64)
	free	0x00007ff65d738730 {unit_tests.exe!ebpf_epoch_free(void *)}	void(*)(void *)
	extract	0x0000000000000000	void(*)(const unsigned char *, const unsigned char * *, unsigned __int64 *)
	▶ buckets	0x0000029dbc406b18 {0x0000000000000000 }	_ebpf_hash_bucket_header * volatile[1]

This shows that the hit rate for the proposed cache is around 5%, which would suggest that this is probably not worth implementing.

[Alan-Jowett]

Additional data points. Hit rate vs table load.

Hash table load	Hit rate
100%	6.8%
200%	5.3%
400%	4.3%
800%	4.0%

Note:
BPF_MAP_TYPE_HASH has a load of 100% (buckets == max_entries)

[Alan-Jowett]

Branch used for this test:
https://github.com/Alan-Jowett/ebpf-for-windows/tree/discussion434

[Alan-Jowett]

This appears to solve the bloat issue and the lock contention on thread entry / exit.
#436