Module edq 

The eligible deadline queue, from the source the BPF program is built from: the loader reads the queues in the arena through the same code. Eligible Deadline Queue: an intrusive red-black tree, a port of scx_eevdf’s lib/edq.bpf.c.

The tree is ordered by deadline, ties broken by insertion order, and every node caches the minimum eligibility and the shortest slice of its subtree. The first eligible task in deadline order, which is what pick_eevdf() searches for, is then one descent from the root, and the shortest queued request is read off the root.

Nodes and queues are addressed by plain u64 addresses, 0 for none, and every access goes through Memory. In BPF that is the arena, cast at each access, with loops bounded by may_goto, which the verifier does not unroll. The host tests run the same code on ordinary memory.

A queued task is its node followed by a hold count and its membership, the address of its queue, 0, or DEAD. The queue has a lock of its own. Its owner CID takes it in its callbacks, which already hold the rq lock, so the only other holders are remote CIDs peeking or stealing, and those only try it. Lockless snapshots of the first deadline and the shortest slice serve decisions that tolerate a stale value.

The snapshots need only View, the loads of Memory. An observer outside the scheduler, such as the loader reading the arena it mapped, implements that alone: it can read a queue’s words and can neither change them nor take the lock.

Structs

Cursor

A resumable position in deadline order, which survives the nodes it passed leaving the tree.

Constants

BLACK 🔒

COLOR 🔒

CURSOR_AFTER

A cursor that resumes after its key.

CURSOR_AT

A cursor that resumes at its key, the task it names included.

CURSOR_START

A cursor that starts at the first task.

DEAD

Membership of a task that may never be queued again.

DEADLINE 🔒

E2BIG

EALREADY

EBUSY

ECANCELED

EINVAL

ELIGIBILITY 🔒

ENOENT

ETIMEDOUT

FIRST 🔒

FIRST_DEADLINE 🔒

HOLD 🔒

LEFT 🔒

LOCK 🔒

LOCK_SPINS 🔒

MAX_DEPTH 🔒

Bound on a walk from the root to a leaf. A red-black tree of 2^31 nodes is no deeper than this.

MAX_SPINS 🔒

Spinning for a queue lock, or for holders to drop a task, is bounded by can_loop alone, as lib/edq’s is. On JITs with timed may_goto, x86 and arm64 among them, that is a quarter of a second per program run, not BPF_MAX_LOOPS iterations. A holder can be held up for milliseconds, by an interrupt or, on a virtual machine, by the host descheduling its vCPU.

MEMBER 🔒

MIN_ELIGIBILITY 🔒

MIN_SLICE 🔒

NR 🔒

PARENT 🔒

QUEUE_BYTES

Bytes a queue takes in a table of them, a cache line each.

QUEUE_MIN_SLICE 🔒

QUEUE_SEQ 🔒

QUEUE_WORDS

Words in a queue.

RED 🔒

RIGHT 🔒

ROOT 🔒

SEQ 🔒

SLICE 🔒

TASK_WORDS

Words in a queued task.

Traits

Memory

Word access to queues and tasks.

View

Read-only word access to queues and tasks.

Functions

clear_links 🔒

drop_task

eligible 🔒

erase_fixup 🔒

Restore the red-black properties after a black node left the child slot of parent that is now empty: that side is one black node short.

erase_step 🔒

One step of erase_fixup with the short side, SIDE, known at compile time, as the verifier explores far fewer states through two fixed-side copies than through one that picks the side at run time. Returns the result once the properties hold, or None to go on one level up.

first_deadline

Lockless snapshot of the first deadline, or None when empty.

first_eligible 🔒

The first node in deadline order whose eligibility is at or before cutoff, or 0: one descent guided by the subtree minima.

get 🔒

held

Is task held by a pop or a peek that has not dropped it yet?

hold_count

How many pops and peeks hold task, for debugging dumps.

hold_task

insert

Queue task on queue. Fails with EALREADY if it is queued anywhere, and ECANCELED once it is dead.

insert_fixup 🔒

Restore the red-black properties after linking the red leaf node.

key

The deadline, eligibility and insertion order a queued task was keyed with.

leftmost 🔒

The leftmost node under node, or 0 if the walk ran out.

less 🔒

lock

Take queue’s lock, spinning a bounded time.

lock_slow 🔒

The spin of lock, in a function of its own: see LOCK_SPINS.

locked

Lockless snapshot of whether queue’s lock is held.

membership

The queue task is a member of: its address, 0, or DEAD.

min_slice

Lockless snapshot of the shortest queued slice, 0 when empty.

nr_inserted

Lockless snapshot of how many tasks were ever queued on queue.

nr_queued

opposite 🔒

pop_first

Remove and return the first task by deadline, or 0 if the queue is empty. With hold, the task is held for the caller.

pop_first_eligible_or_first

Remove and return the first task whose eligibility is at or before cutoff, or else the first task, or 0 if the queue is empty. With hold, the task is held for the caller.

pop_locked 🔒

propagate 🔒

Recompute the cached minima from node up to the root. The walk stops at the first node whose minima did not change, since nothing above it can change either, unless resume is further up the path: then it goes on from resume, whose cached minima are not ones the nodes above saw.

put 🔒

queue_init

Initialize an empty queue.

red 🔒

refresh_min_slice 🔒

remove

Take task out of queue. EINVAL if it is not queued there.

remove_locked 🔒

replace_child 🔒

rotate 🔒

Rotate node down to the side down, raising its child on the other side, and return that child. The child takes over the node’s subtree, and with it its minima.

task_detach

Take task out of whatever queue it is in for good, then wait for the holders to drop it, so that its memory can be reused.

task_fini

Take task out of the queue it is in, if any. Returns 1 if it was queued, 0 if not, or an error.

task_init

Bring a fresh task to the state of one queued nowhere and held by nobody, word by word.

time_before 🔒

try_first_eligible_deadline

The deadline of the first eligible task and the shortest queued slice, without removing anything. ENOENT when nothing queued is eligible, EBUSY when the queue is contended.

try_peek_next_hold

Hold the next task in deadline order after cursor and advance it, so that a bounded scan can resume even after the tasks it passed have left. Returns 0 with no task at the end, EBUSY when contended.

try_remove

As remove, but EBUSY if the queue is contended.

trylock

Take queue’s lock if it is free.

unlock

update 🔒

Refresh the cached subtree minima of node.