This article provides an overview without technical details or usage instructions.
The Zephyr kernel uses a generic data structure library, which can also be utilized in applications. The data structures include:
-
Linked List -
Packet Buffer -
Red-Black Tree -
Circular Buffer
It is important to note that the APIs for accessing these data structures are not thread-safe.
Linked List
The linked list consists of singly linked lists and doubly linked lists:
Singly Linked List: In Zephyr, the singly linked list allows constant time O(1) access to the head and tail elements, insertion at the head and tail, and removal of the head element. However, deleting a node from the linked list requires traversing the list for the search, which takes linear time O(n). Each node in a singly linked list only stores a pointer to the next node. The singly linked list is implemented in the following files:
zephyr/include/zephyr/sys/slist.h
zephyr/include/zephyr/sys/sflist.h
Doubly Linked List: The doubly linked list in Zephyr supports the same operations as the singly linked list and additionally provides the ability to insert and delete nodes at any position (head, tail, or internal nodes) in constant time O(1). To achieve these functionalities, each node in the doubly linked list needs to store two pointers, resulting in some additional overhead in runtime code and memory space compared to singly linked lists. The doubly linked list is implemented in the following files:
zephyr/include/zephyr/sys/dlist.h
Packet Buffer
The packet buffer includes MPSC and SPSC:
MPSC Buffer (Multi-Producer Single-Consumer): The Multi-Producer Single-Consumer Packet Buffer (MPSC) is a circular buffer used to store packets, processed in a first-in-first-out manner. There is only one context (consumer) that consumes the data. There may be multiple contexts (producers) writing data. The production and consumption of packets are divided into two steps. The producer first allocates a certain amount of space, fills in the data, and submits it. The consumer first declares the packet to consume, retrieves a pointer and length to the packet, and releases the packet after use. This method reduces the number of memory copies, improving efficiency. MPSC is implemented in the following files:
zephyr/include/zephyr/sys/mpsc_pbuf.h
zephyr/lib/os/mpsc_pbuf.c
SPSC Buffer (Single-Producer Single-Consumer): The Single-Producer Single-Consumer Packet Buffer (SPSC) is a circular buffer used to store packets, processed in a first-in-first-out manner. There is only one context (consumer) that consumes data, and only one context (producer) that produces data. The SPSC consumer needs to copy to obtain the data. SPSC is implemented in the following files:
zephyr/include/zephyr/sys/spsc_pbuf.h
zephyr/lib/os/spsc_pbuf.c
Red-Black Tree
The size of sorted nodes can become very large at runtime, making the efficiency of search operations using linked lists very low O(n). To solve this problem, Zephyr provides a balanced tree implementation. The time complexity for search and delete operations in a balanced tree is O(log2(n)). The balanced tree in Zephyr uses the red-black tree algorithm. The red-black tree is implemented in the following files:
zephyr/include/zephyr/sys/rb.h
zephyr/lib/os/rb.c
Circular Buffer
The circular buffer is a circular buffer that stores its contents in a first-in-first-out manner and can operate in the following two modes:
-
Byte Mode: Raw bytes can be enqueued and dequeued -
Data Item Mode: Multiple 32-bit word data items with metadata can be enqueued and dequeued from the circular buffer in blocks of up to 1020 bytes
The circular buffer is implemented in the following files:
zephyr/include/zephyr/sys/ring_buffer.h
zephyr/lib/os/ring_buffer.c
References
https://docs.zephyrproject.org/latest/kernel/data_structures/index.html