Queues are a central data structure used throughout the Tripos environment. Packets are queued onto work queues for both tasks and for device drivers.
In classical Tripos, queues are maintained as singly linked lists. This works, from a functional point of view. However, on contemporary processor architectures, linked lists offers greatly reduced performance thanks in large part to the cache hierarchy. Experiments on my personal computer shows that it's actually cheaper to copy entire 80 byte-long structures into and out of queues than it is to maintain linked list structures.
Therefore, we opt instead to use a ring buffer for queue management.
A queue has the following layout in memory:
+---------+ | q_ring | +---------+ | q_size | +---------+ | q_head | +---------+ | q_tail | +---------+ | q_flags | +---------+
The q_ring field points to the ring buffer itself.
The ring buffer is always a power of two in size.
The q_size field controls several things at once.
First, it directly indicates how big the ring buffer actually is,
in elements, not in bytes.
It is recorded as the log2 of the linear size;
e.g., 2 would indicate 4 elements, 4 indicates 16, 8 256, and so on.
Because of this, it also controls the modulus used to constrain
the q_head and q_tail fields as well.
The q_head and q_tail fields
keep track of how many pushes (q_tail)
and how many pops (q_head)
have occurred since the queue was created.
When properly constrained via a modulus operation,
they are also used to index into the ring buffer
for both the head and the tail of the queue.
The q_flags field is needed to record whether or not
this queue is dynamic or static.
A dynamic queue is one whose ring buffer is managed via getmem and freemem,
while a static queue is one whose ring buffer is statically sized and never changes.
The type of element stored in the queue is a pointer to a structure. Such pointers will have at least half-word alignment, leaving bit 0 (at a minimum) free to use as a tombstone flag.
Note: It is possible to still use queues to store pointers to byte-aligned data. The precondition to this working, however, is that you never have to tombstone an element in the queue.
Why? I realize that this is a bit of a leaky abstraction; however, storage and run-time efficiency forces my hand.
Tombstones are required
in order to properly support
the dqpkt system call,
which can remove a packet from a queue
regardless of where in the queue it sits.
A queue is considered empty when
q_head == q_tail.
Note that we don't consider moduli here;
rather, we use the full integer width of these fields
as unsigned integers.
A queue is considered full when
q_tail - q_head == (1 << q_size).
An element is pushed onto the queue via the following behavior:
TO push element (e) onto queue (q) DO IF queue not full THEN Copy pointer (e) into next open slot. Bump q_tail. RETURN results for success. END RETURN results for queue full. END
Pushing onto a dynamically managed queue is just like pushing onto a static queue. However, the behavior changes somewhat:
PREDICATE queue is statically managed DO RETURN bit 0 of q_flags is set. END PREDICATE ring buffer is dynamically allocated DO RETURN bit 1 of q_flags is set. END TO push element (e) onto queue (q) DO Assume first try. DO WHILE we haven't reached 3 tries yet -- prevent infinite recursion IF queue not full THEN Copy pointer (e) into next open slot. Bump q_tail. RETURN results for success. END IF queue is statically managed THEN RETURN results for queue full. END Try to allocate ring buffer twice the current size. IF memory not available THEN RETURN results for queue full. END Copy current ring buffer contents to new buffer, \ initializing new elements to NULL. IF current ring buffer is dynamically allocated THEN Free current ring buffer. END Set new ring buffer pointer. Denote that it is dynamically allocated. Try again. END -- If we're here, we tried and failed to grow the buffer *twice*. RETURN results for queue full. END
An element may be retrieved from the head of the queue via the following set of behaviors. Please note that popping the queue does not return a value, so make sure to query the queue first!
TO query the queue (q) DO IF queue not empty THEN Retrieve pointer to next available element. RETURN pointer. END RETURN results for queue empty. END TO pop queue (q) DO IF queue not empty THEN Bump q_head. RETURN results for success. END RETURN results for failure. END
Note: before you use a value from the queue, double-check it is not a tombstone. A more conventional "get head of queue" function might be implemented with a behavior such as this:
PREDICATE element (e) is a tombstone DO RETURN bit 0 of e is set --> TRUE ; FALSE. END TO get next head of queue (q) DO DO FOREVER Query the queue. IF head is not a tombstone THEN Pop the queue. RETURN the head. ELSEIF head is a tombstone THEN Pop the queue. CYCLE ELSE RETURN results. -- it's an error END END END