kernel: Add k_queue API
This unifies k_fifo and k_lifo APIs thus making it more flexible regarding
where the data elements are inserted.
Change-Id: Icd6e2f62fc8b374c8273bb763409e9e22c40f9f8
Signed-off-by: Luiz Augusto von Dentz <luiz.von.dentz@intel.com>
diff --git a/include/kernel.h b/include/kernel.h
index 1f79343..611de31 100644
--- a/include/kernel.h
+++ b/include/kernel.h
@@ -113,6 +113,7 @@
struct k_msgq;
struct k_mbox;
struct k_pipe;
+struct k_queue;
struct k_fifo;
struct k_lifo;
struct k_stack;
@@ -1104,6 +1105,183 @@
* @cond INTERNAL_HIDDEN
*/
+struct k_queue {
+ _wait_q_t wait_q;
+ sys_slist_t data_q;
+ _POLL_EVENT;
+
+ _OBJECT_TRACING_NEXT_PTR(k_queue);
+};
+
+#define K_QUEUE_INITIALIZER(obj) \
+ { \
+ .wait_q = SYS_DLIST_STATIC_INIT(&obj.wait_q), \
+ .data_q = SYS_SLIST_STATIC_INIT(&obj.data_q), \
+ _POLL_EVENT_OBJ_INIT \
+ _OBJECT_TRACING_INIT \
+ }
+
+/**
+ * INTERNAL_HIDDEN @endcond
+ */
+
+/**
+ * @defgroup queue_apis Queue APIs
+ * @ingroup kernel_apis
+ * @{
+ */
+
+/**
+ * @brief Initialize a queue.
+ *
+ * This routine initializes a queue object, prior to its first use.
+ *
+ * @param queue Address of the queue.
+ *
+ * @return N/A
+ */
+extern void k_queue_init(struct k_queue *queue);
+
+/**
+ * @brief Append an element to the end of a queue.
+ *
+ * This routine appends a data item to @a queue. A queue data item must be
+ * aligned on a 4-byte boundary, and the first 32 bits of the item are
+ * reserved for the kernel's use.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ * @param data Address of the data item.
+ *
+ * @return N/A
+ */
+extern void k_queue_append(struct k_queue *queue, void *data);
+
+/**
+ * @brief Prepend an element to a queue.
+ *
+ * This routine prepends a data item to @a queue. A queue data item must be
+ * aligned on a 4-byte boundary, and the first 32 bits of the item are
+ * reserved for the kernel's use.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ * @param data Address of the data item.
+ *
+ * @return N/A
+ */
+extern void k_queue_prepend(struct k_queue *queue, void *data);
+
+/**
+ * @brief Inserts an element to a queue.
+ *
+ * This routine inserts a data item to @a queue after previous item. A queue
+ * data item must be aligned on a 4-byte boundary, and the first 32 bits of the
+ * item are reserved for the kernel's use.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ * @param prev Address of the previous data item.
+ * @param data Address of the data item.
+ *
+ * @return N/A
+ */
+extern void k_queue_insert(struct k_queue *queue, void *prev, void *data);
+
+/**
+ * @brief Atomically append a list of elements to a queue.
+ *
+ * This routine adds a list of data items to @a queue in one operation.
+ * The data items must be in a singly-linked list, with the first 32 bits
+ * in each data item pointing to the next data item; the list must be
+ * NULL-terminated.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ * @param head Pointer to first node in singly-linked list.
+ * @param tail Pointer to last node in singly-linked list.
+ *
+ * @return N/A
+ */
+extern void k_queue_append_list(struct k_queue *queue, void *head, void *tail);
+
+/**
+ * @brief Atomically add a list of elements to a queue.
+ *
+ * This routine adds a list of data items to @a queue in one operation.
+ * The data items must be in a singly-linked list implemented using a
+ * sys_slist_t object. Upon completion, the original list is empty.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ * @param list Pointer to sys_slist_t object.
+ *
+ * @return N/A
+ */
+extern void k_queue_merge_slist(struct k_queue *queue, sys_slist_t *list);
+
+/**
+ * @brief Get an element from a queue.
+ *
+ * This routine removes first data item from @a queue. The first 32 bits of the
+ * data item are reserved for the kernel's use.
+ *
+ * @note Can be called by ISRs, but @a timeout must be set to K_NO_WAIT.
+ *
+ * @param queue Address of the queue.
+ * @param timeout Waiting period to obtain a data item (in milliseconds),
+ * or one of the special values K_NO_WAIT and K_FOREVER.
+ *
+ * @return Address of the data item if successful; NULL if returned
+ * without waiting, or waiting period timed out.
+ */
+extern void *k_queue_get(struct k_queue *queue, int32_t timeout);
+
+/**
+ * @brief Query a queue to see if it has data available.
+ *
+ * Note that the data might be already gone by the time this function returns
+ * if other threads are also trying to read from the queue.
+ *
+ * @note Can be called by ISRs.
+ *
+ * @param queue Address of the queue.
+ *
+ * @return Non-zero if the queue is empty.
+ * @return 0 if data is available.
+ */
+static inline int k_queue_is_empty(struct k_queue *queue)
+{
+ return (int)sys_slist_is_empty(&queue->data_q);
+}
+
+/**
+ * @brief Statically define and initialize a queue.
+ *
+ * The queue can be accessed outside the module where it is defined using:
+ *
+ * @code extern struct k_queue <name>; @endcode
+ *
+ * @param name Name of the queue.
+ */
+#define K_QUEUE_DEFINE(name) \
+ struct k_queue name \
+ __in_section(_k_queue, static, name) = \
+ K_QUEUE_INITIALIZER(name)
+
+/**
+ * @} end defgroup queue_apis
+ */
+
+/**
+ * @cond INTERNAL_HIDDEN
+ */
+
struct k_fifo {
_wait_q_t wait_q;
sys_slist_t data_q;
@@ -3129,8 +3307,8 @@
/* semaphore availability */
_POLL_TYPE_SEM_AVAILABLE,
- /* fifo data availability */
- _POLL_TYPE_FIFO_DATA_AVAILABLE,
+ /* queue/fifo/lifo data availability */
+ _POLL_TYPE_DATA_AVAILABLE,
_POLL_NUM_TYPES
};
@@ -3151,8 +3329,8 @@
/* semaphore is available */
_POLL_STATE_SEM_AVAILABLE,
- /* data is available to read on fifo */
- _POLL_STATE_FIFO_DATA_AVAILABLE,
+ /* data is available to read on queue/fifo/lifo */
+ _POLL_STATE_DATA_AVAILABLE,
_POLL_NUM_STATES
};
@@ -3186,8 +3364,8 @@
#define K_POLL_TYPE_IGNORE 0
#define K_POLL_TYPE_SIGNAL _POLL_TYPE_BIT(_POLL_TYPE_SIGNAL)
#define K_POLL_TYPE_SEM_AVAILABLE _POLL_TYPE_BIT(_POLL_TYPE_SEM_AVAILABLE)
-#define K_POLL_TYPE_FIFO_DATA_AVAILABLE \
- _POLL_TYPE_BIT(_POLL_TYPE_FIFO_DATA_AVAILABLE)
+#define K_POLL_TYPE_DATA_AVAILABLE _POLL_TYPE_BIT(_POLL_TYPE_DATA_AVAILABLE)
+#define K_POLL_TYPE_FIFO_DATA_AVAILABLE K_POLL_TYPE_DATA_AVAILABLE
/* public - polling modes */
enum k_poll_modes {
@@ -3202,8 +3380,8 @@
#define K_POLL_STATE_EADDRINUSE _POLL_STATE_BIT(_POLL_STATE_EADDRINUSE)
#define K_POLL_STATE_SIGNALED _POLL_STATE_BIT(_POLL_STATE_SIGNALED)
#define K_POLL_STATE_SEM_AVAILABLE _POLL_STATE_BIT(_POLL_STATE_SEM_AVAILABLE)
-#define K_POLL_STATE_FIFO_DATA_AVAILABLE \
- _POLL_STATE_BIT(_POLL_STATE_FIFO_DATA_AVAILABLE)
+#define K_POLL_STATE_DATA_AVAILABLE _POLL_STATE_BIT(_POLL_STATE_DATA_AVAILABLE)
+#define K_POLL_STATE_FIFO_DATA_AVAILABLE K_POLL_STATE_DATA_AVAILABLE
/* public - poll signal object */
struct k_poll_signal {
diff --git a/include/linker/common-ram.ld b/include/linker/common-ram.ld
index 19cca9e..a2f320b 100644
--- a/include/linker/common-ram.ld
+++ b/include/linker/common-ram.ld
@@ -65,6 +65,13 @@
_k_alert_list_end = .;
} GROUP_DATA_LINK_IN(RAMABLE_REGION, ROMABLE_REGION)
+ SECTION_DATA_PROLOGUE(_k_queue_area, (OPTIONAL),)
+ {
+ _k_queue_list_start = .;
+ KEEP(*(SORT_BY_NAME("._k_queue.static.*")))
+ _k_queue_list_end = .;
+ } GROUP_DATA_LINK_IN(RAMABLE_REGION, ROMABLE_REGION)
+
SECTION_DATA_PROLOGUE(_k_fifo_area, (OPTIONAL),)
{
_k_fifo_list_start = .;
diff --git a/kernel/Makefile b/kernel/Makefile
index 9374b11..4585cac 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -18,6 +18,7 @@
idle.o \
sched.o \
mutex.o \
+ queue.o \
lifo.o \
fifo.o \
stack.o \
diff --git a/kernel/queue.c b/kernel/queue.c
new file mode 100644
index 0000000..7f6e287
--- /dev/null
+++ b/kernel/queue.c
@@ -0,0 +1,185 @@
+/*
+ * Copyright (c) 2010-2016 Wind River Systems, Inc.
+ *
+ * SPDX-License-Identifier: Apache-2.0
+ */
+
+/**
+ * @file
+ *
+ * @brief dynamic-size QUEUE object.
+ */
+
+
+#include <kernel.h>
+#include <kernel_structs.h>
+#include <debug/object_tracing_common.h>
+#include <toolchain.h>
+#include <sections.h>
+#include <wait_q.h>
+#include <ksched.h>
+#include <misc/slist.h>
+#include <init.h>
+
+extern struct k_queue _k_queue_list_start[];
+extern struct k_queue _k_queue_list_end[];
+
+struct k_queue *_trace_list_k_queue;
+
+#ifdef CONFIG_OBJECT_TRACING
+
+/*
+ * Complete initialization of statically defined queues.
+ */
+static int init_queue_module(struct device *dev)
+{
+ ARG_UNUSED(dev);
+
+ struct k_queue *queue;
+
+ for (queue = _k_queue_list_start; queue < _k_queue_list_end; queue++) {
+ SYS_TRACING_OBJ_INIT(k_queue, queue);
+ }
+ return 0;
+}
+
+SYS_INIT(init_queue_module, PRE_KERNEL_1, CONFIG_KERNEL_INIT_PRIORITY_OBJECTS);
+
+#endif /* CONFIG_OBJECT_TRACING */
+
+void k_queue_init(struct k_queue *queue)
+{
+ sys_slist_init(&queue->data_q);
+ sys_dlist_init(&queue->wait_q);
+
+ _INIT_OBJ_POLL_EVENT(queue);
+
+ SYS_TRACING_OBJ_INIT(k_queue, queue);
+}
+
+static void prepare_thread_to_run(struct k_thread *thread, void *data)
+{
+ _abort_thread_timeout(thread);
+ _ready_thread(thread);
+ _set_thread_return_value_with_data(thread, 0, data);
+}
+
+/* returns 1 if a reschedule must take place, 0 otherwise */
+static inline int handle_poll_event(struct k_queue *queue)
+{
+#ifdef CONFIG_POLL
+ uint32_t state = K_POLL_STATE_DATA_AVAILABLE;
+
+ return queue->poll_event ?
+ _handle_obj_poll_event(&queue->poll_event, state) : 0;
+#else
+ return 0;
+#endif
+}
+
+void k_queue_insert(struct k_queue *queue, void *prev, void *data)
+{
+ struct k_thread *first_pending_thread;
+ unsigned int key;
+
+ key = irq_lock();
+
+ first_pending_thread = _unpend_first_thread(&queue->wait_q);
+
+ if (first_pending_thread) {
+ prepare_thread_to_run(first_pending_thread, data);
+ if (!_is_in_isr() && _must_switch_threads()) {
+ (void)_Swap(key);
+ return;
+ }
+ } else {
+ sys_slist_insert(&queue->data_q, prev, data);
+ if (handle_poll_event(queue)) {
+ (void)_Swap(key);
+ return;
+ }
+ }
+
+ irq_unlock(key);
+}
+
+void k_queue_append(struct k_queue *queue, void *data)
+{
+ return k_queue_insert(queue, queue->data_q.tail, data);
+}
+
+void k_queue_prepend(struct k_queue *queue, void *data)
+{
+ return k_queue_insert(queue, NULL, data);
+}
+
+void k_queue_append_list(struct k_queue *queue, void *head, void *tail)
+{
+ __ASSERT(head && tail, "invalid head or tail");
+
+ struct k_thread *first_thread, *thread;
+ unsigned int key;
+
+ key = irq_lock();
+
+ first_thread = _peek_first_pending_thread(&queue->wait_q);
+ while (head && ((thread = _unpend_first_thread(&queue->wait_q)))) {
+ prepare_thread_to_run(thread, head);
+ head = *(void **)head;
+ }
+
+ if (head) {
+ sys_slist_append_list(&queue->data_q, head, tail);
+ }
+
+ if (first_thread) {
+ if (!_is_in_isr() && _must_switch_threads()) {
+ (void)_Swap(key);
+ return;
+ }
+ } else {
+ if (handle_poll_event(queue)) {
+ (void)_Swap(key);
+ return;
+ }
+ }
+
+ irq_unlock(key);
+}
+
+void k_queue_merge_slist(struct k_queue *queue, sys_slist_t *list)
+{
+ __ASSERT(!sys_slist_is_empty(list), "list must not be empty");
+
+ /*
+ * note: this works as long as:
+ * - the slist implementation keeps the next pointer as the first
+ * field of the node object type
+ * - list->tail->next = NULL.
+ */
+ k_queue_append_list(queue, list->head, list->tail);
+ sys_slist_init(list);
+}
+
+void *k_queue_get(struct k_queue *queue, int32_t timeout)
+{
+ unsigned int key;
+ void *data;
+
+ key = irq_lock();
+
+ if (likely(!sys_slist_is_empty(&queue->data_q))) {
+ data = sys_slist_get_not_empty(&queue->data_q);
+ irq_unlock(key);
+ return data;
+ }
+
+ if (timeout == K_NO_WAIT) {
+ irq_unlock(key);
+ return NULL;
+ }
+
+ _pend_current_thread(&queue->wait_q, timeout);
+
+ return _Swap(key) ? NULL : _current->base.swap_data;
+}
