iovisor / iovisor/bcc

bpf_log2l helper gives an off by one result

Open
#1,649 7 comments 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
22.7k
Forks
4.1k
Avg merge
10d 4h
Merged PRs (30d)
3

Description

When calculating the binary logarithm of a 64-bit integer `bpf_log2l` helper [adds 1](https://github.com/iovisor/bcc/blob/ddd5dd5ee32226d07c9632a2ff8cf6f1e713dff5/src/cc/export/helpers.h#L454) to the logarithm of a 32-bit half calculated by `bpf_log2`.
```
value | bpf_log2 | bpf_log2l
0 | 0 | 1
1 | 0 | 1
2 | 1 | 2
4 | 2 | 3
4294967296 | | 33
8589934592 | | 34
9223372036854775808 | | 64
```

That doesn't cause errors with code like `dist.increment(bpf_log2l(1ull << 63))`, where `dist` is a log2 histogram of size 64. I suspect that is due to element lookup prior to updating. In real use cases the 0th bucket will always be empty and the 63rd will be lost. Interesting that `bcc.table._print_log2_hist` [works around](https://github.com/iovisor/bcc/blob/ddd5dd5ee32226d07c9632a2ff8cf6f1e713dff5/src/python/bcc/table.py#L80) this by printing buckets 1 through 63, skipping the always empty 0th bucket. Was it done intentionally? I can send a patch that fixes this issue if you would like.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start in src/cc/export/helpers.h at the bpf_log2l implementation and compare its 64-bit behavior with bpf_log2. Then inspect src/python/bcc/table.py and its _print_log2_hist workaround to determine the intended bucket indexing. Done means the helper and histogram output agree on the documented boundary values, with regression coverage added if the repository has a suitable test location.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
observability-sre
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.