# bpf-tcp-congestion-control-algorithm

**Repository Path**: wangcichen/bpf-tcp-congestion-control-algorithm

## Basic Information

- **Project Name**: bpf-tcp-congestion-control-algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-01-18
- **Last Updated**: 2025-01-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# bpf-tcp-congestion-control-algorithm
This repository is intended to be a simple guide for utilizing the eBPF tool in order to write and load a custom TCP congestion control algorithm into the Linux kernel.

## General guide
- Make sure you have all the [requirements](#requirements) installed.
- Follow the steps according the [compile_and_load.sh](src/compile_and_load.sh) file (Run the commands in the **`src`** directory).
- In case of any problems and issues, refer to [this](#common-issues-and-possible-fixes) section.
>
- If you want to know more about what actually happens under the hood, when going through these steps, refer to [this](https://lwn.net/Articles/811631/) page.

## Requirements
- bpftool
> This should be already installed on your linux machine.
- clang-13
> Instructions to install clang-13 on Ubuntu 20.04: 
> 
> https://ubuntu.pkgs.org/20.04/ubuntu-proposed-universe-amd64/clang-13_13.0.1-2ubuntu2~20.04.1_amd64.deb.html
- BPF headers
> Bpf headers don’t come with the kernel distro headers.
> 
> Run `sudo apt install libbpf-dev` to install them.
- bcc
> Github repository link: https://github.com/iovisor/bcc/tree/master
> 
> Installation guide: https://github.com/iovisor/bcc/tree/master

## Important Note
> This work has been done and tested on Ubuntu 20.04 with kernel version `5.15`.

## Common issues and possible fixes
The following problem would most probably occur if you are using a clang version older than clang-13.

### Main Problem 1
You have original bpf_cubic.c (the one in this repository is slightly changed which will be discussed later in this file) and bpf_tcp_helpers.h from kernel examples.
The can be found from the following addresses:
`tools/testing/selftests/bpf/progs/bpf_cubic.c`
`tools/testing/selftests/bpf/bpf_tcp_helpers.h`

The code will be compiled using `clang -target bpf -I/usr/include/$(uname -m)-linux-gnu -g -O2 -o bpf_cubic.o -c bpf_cubic.c`.
Then it will be loaded using  `sudo bpftool struct_ops register bpf_cubic.o`.

The ensuing error will be something like this:
`libbpf: failed to find BTF for extern 'tcp_cong_avoid_ai' [41] section: -2`

This shows that bpftool has problem finding the [BTF](https://www.kernel.org/doc/html/next/bpf/btf.html) mapping for the extern function types used in bpf_cubic.c.

Below cites a note from the README.rst file in the linux source tree located at `tools/testing/selftests/bpf/README.rst`:

```
Kernel function call test and Clang version
===========================================

Some selftests (e.g. kfunc_call and bpf_tcp_ca) require a LLVM support
to generate extern function in BTF.  It was introduced in `Clang 13`__.

Without it, the error from compiling bpf selftests looks like:

.. code-block:: console

  libbpf: failed to find BTF for extern 'tcp_slow_start' [25] section: -2

__ https://reviews.llvm.org/D93563
```

According to the above statement, you will have to install clang-13 using the link provided in the [requirements](#requirements) section.

### Main Problem 2
Compiling the original code with clang-13 and then loading solves the previous issue of not finding BTF for extern functions ([Main Problem 1](#main-problem-1)). Although, a new one will most probably emerge when trying to load the object file into the kernel using bpftool.

In the error logs, the output of the `sudo bpftool struct_ops register bpf_cubic.o` command ends as follows:
```
libbpf: -- END LOG --
libbpf: failed to load program 'bpf_cubic_cong_avoid'
libbpf: failed to load object 'bpf_cubic.o'
```

The following lines can also be seen:
```
; x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;
202: (18) r1 = 0xffffb5740035c000
204: (0f) r1 += r2
205: (71) r1 = *(u8 *)(r1 +0)
R1 invalid mem access 'inv'
```

By commenting and uncommenting different sections of the code in the `bpf_cubic_cong_avoid` function, the problem seems to be in the `cubic_root` function where the following line is being verified by the bpf verifier:
```
x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;
```
This was indicated in the error logs above. 
More trial and error suggests that the problem is with the `shift` variable assignment:
```
shift = (a >> (b * 3));
```
Variable `a` is of type __u64 and `b` and `shift` are of type `__u32`. 
Changing the code like this for casting helps to solve the problem.
```
shift = ((__u32)a >> (b * 3));
```

**The change is not necessary for the code to be compiled, but it seems to cause an error when the code is being verified by the bpf verifier.**