Assignment 2: Scheduler CPU bidding

Announcement date: 31.03.2026

Due date: 28.04.2026 (final due date 12.05.2026)

Additional materials

Introduction

With the recent introduction of BPF scheduling, we can control program execution at a far greater scale. However, if we would want to allow users to indicate the tasks priority or CPU needs, we would had to manually change BPF schedulers, to allow for such a possibility. To solve this problem we propose a new interface, that aims to decouple process of deciding importance of the task from the scheduler itself. In our approach, the scheduler manages auctions for the processor time, and tasks create bids with an abstract "task currency".

This interface is designed in a way that enables a central identity to control the currency allocation. It can be used in scenarios where to obtain task currency, you would need to buy it from the system owner. This could be then used to create a service where you rent CPU time at finer granularity levels than solutions like EC2 Spot Instances allow, since there is no need to create a new VM for each task you want to run.

Assignment

Your task is to implement the interface that would allow for the process of auctioning, bidding, and obtain new task currency. Your solution should adhere to the provided specification.

Task struct

task_struct must have the following new fields:

// Information about current bid
// If there is no active bid, it's set to null
struct *bid_info current_bid;
// Current accumulated currency
size_t currency;

where bid_info is the following structure:

struct bid_info {
    // How much currency the process wants to pay
    size_t bid_amount;
    // For what amount of time
    size_t time_fraction;
};

The bid amount represent how much currency (which the process need to hold) we want to spend on the current bid. Time fraction represents abstract unit of time, we are bidding for. This value can be interpreted by the BPF scheduler in any way it deems fit.

You may add any additional fields you deem necessary.

Earning currency

In a production-ready version, task currency could be provided on the scheduler's discretion: for instance, based on the time a runnable task is waiting for execution. For this Assignment scope, however, the currency can only be obtained by a user having superuser's authorization (ensured by a message signing procedure). This can be done by the new syscall, that you have to implement:

int pay_signed(size_t sequence_number, int payee, size_t amount, char *signature)

Where:

  • This syscall has a number that is 1 greater than the file_setattr syscall

  • sequence number - is the number of times this syscall was called from the calling process (including calls that ended with an error). The first sequence number used by the process should be 1. (This is required to avoid double spending - each call will have a unique sequence number and, as a result, unique signature.)

  • payee - is the PID of a process that should receive the payment. If set to zero, the calling process will receive the payment.

  • amount - how much currency to add to the payee process.

  • signature - is an address to 256 bytes of memory, containing a sha256 signature of the following structure:

// The "packed" attribute is to ensure we do not get some padding
// that would break the signatures
struct __attribute__((packed)){
    int caller_pid; // PID of the calling process
    size_t sequence_number;
    int payee;
    size_t amount;
    char key[]; // Key set in the set_payments_hmac_key, see below
}

This syscall should ensure the following:

  • The sequence number is correct

  • The payee process exists

  • The signature is valid

If one of the errors occur, it should return errno value. On success it should return 0.

The key can be set through set_payments_hmac_key syscall, which you have to add:

int set_payments_hmac_key(char *key, unsigned char len)

This syscall sets the key (with the provided length), that will be used to verify calls to pay_signed. This syscall can be called only by the root user. This syscall has a number that is 1 greater than the pay_signed syscall

On success, it should return 0. Otherwise, it should return errno value. Remember that both of those syscall should be resistant against known most common attack vectors, especially timing attacks.

Bidding mechanism

The bidding will be done by a BPF program on behalf of a process. To accommodated this mechanism, you have to add a new BPF program type BPF_PROG_TYPE_BIDDER (having a number 1 greater than BPF_PROG_TYPE_NETFILTER), with the following attachment types: BPF_CREATE_BID and BPF_UPDATE_BID (having numbers 1 and 2 greater than BPF_TRACE_UPROBE_SESSION respectively).

You have to add the following attachment points:

  • int bpf_create_new_bid(struct task_struct *task) for the BPF_CREATE_BID attachment type.

  • int bpf_update_bid(struct task_struct *task) for the BPF_UPDATE_BID attachment type.

The added BPF program should attach to them with BPF_RAW_TRACEPOINT_OPEN.

The bpf_create_new_bid function shall be called after the program receives new currency through a payment, and it should set the current_bid field in the task_struct, if it decides to create a bid. Both functions can only return 0.

The bpf_update_bid shall be called for processes with the field current_bid set, once the task becomes runnable.

Both of those operations on the task struct will be performed through BPF helper functions you need to implement:

  • bpf_create_bid_helper(struct task_struct *task, size_t bid_amount, size_t time_fraction),

  • bpf_update_bid_helper(struct task_struct *task, size_t bid_amount, size_t time_fraction).

Those helpers should have 213 and 214 codes respectively.

Those helpers should be accessible only to BPF_CREATE_BID and BPF_UPDATE_BID BPF programs respectively. On top of those two functions, BPF_PROG_TYPE_BIDDER programs should only have access to the base helpers set.

If you submit a solution, that does not support attaching BPF_PROG_TYPE_BIDDER BPF programs, you should create bids that consume all of the budget for a single unit of time.

Auction process

The BPF scheduler, when deciding which process to schedule, can look at the current process bids. If it decides to take one of the bids from the task, it will call bpf_sched_bid_for(task).

The bool bpf_sched_bid_for(struct task_struct *task, size_t bid_amount, size_t time_fraction) is a helper function you need to implement. Only BPF_PROG_TYPE_STRUCT_OPS programs should be able to access this helper function. This function should:

  • have a 212 code,

  • ensure values inside the current bid are the same as function arguments (compare and exchange semantic),

  • check the validity of the current bid (and return false if it's invalid),

  • take the payment for the current bid,

  • clear the current bid,

    • If the process has remaining currency, this means setting bid amount and time fraction to 0,

    • otherwise it means deallocating the bid information structure.

  • return true when the bid was taken successfully, and false otherwise.

Solution compilation

Compiling the tests requires the vmlinux.h file, which was not included with the tests. It can be generated e.g. using the bpftool program. No additional modifications to the provided libbpf library are required.

Compilation of the kernel requires installation of the pahole package. During testing, solution will be compiled with the config file included in the tests package.

Hints

A fix for infinite loops that was implemented in the BPF subsystem (https://lore.kernel.org/bpf/20241015150207.70264-2-leon.hwang@linux.dev/T/) unelegantly introduces an assumption that bpf_tramp_prog_type == BPF_TRAMP_REPLACE implies tgt_prog != NULL. The solution must take this into account, otherwise the kernel will panic due to NULL dereferences.

Solution format

As the solution submit a package containing:

  • a patch for the Linux kernel version 6.18.5 generated using git format-patch

  • a short description of the solution