Zephyr Project API 3.7.0
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
mpsc_lockfree.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2010-2011 Dmitry Vyukov
3 * Copyright (c) 2023 Intel Corporation
4 *
5 * SPDX-License-Identifier: Apache-2.0
6 */
7
8#ifndef ZEPHYR_SYS_MPSC_LOCKFREE_H_
9#define ZEPHYR_SYS_MPSC_LOCKFREE_H_
10
11#include <stdint.h>
12#include <stdbool.h>
13#include <zephyr/sys/atomic.h>
14#include <zephyr/kernel.h>
15
16#ifdef __cplusplus
17extern "C" {
18#endif
19
43/*
44 * On single core systems atomics are unnecessary
45 * and cause a lot of unnecessary cache invalidation
46 *
47 * Using volatile to at least ensure memory is read/written
48 * by the compiler generated op codes is enough.
49 *
50 * On SMP atomics *must* be used to ensure the pointers
51 * are updated in the correct order.
52 */
53#if defined(CONFIG_SMP)
54
56
57#define mpsc_ptr_get(ptr) atomic_ptr_get(&(ptr))
58#define mpsc_ptr_set(ptr, val) atomic_ptr_set(&(ptr), val)
59#define mpsc_ptr_set_get(ptr, val) atomic_ptr_set(&(ptr), val)
60
61#else /* defined(CONFIG_SMP) */
62
63typedef struct mpsc_node *mpsc_ptr_t;
64
65#define mpsc_ptr_get(ptr) ptr
66#define mpsc_ptr_set(ptr, val) ptr = val
67#define mpsc_ptr_set_get(ptr, val) \
68 ({ \
69 mpsc_ptr_t tmp = ptr; \
70 ptr = val; \
71 tmp; \
72 })
73
74#endif /* defined(CONFIG_SMP) */
75
82
86struct mpsc {
88 struct mpsc_node *tail;
90};
91
99#define MPSC_INIT(symbol) \
100 { \
101 .head = (struct mpsc_node *)&symbol.stub, \
102 .tail = (struct mpsc_node *)&symbol.stub, \
103 .stub = { \
104 .next = NULL, \
105 }, \
106 }
107
113static inline void mpsc_init(struct mpsc *q)
114{
115 mpsc_ptr_set(q->head, &q->stub);
116 q->tail = &q->stub;
117 mpsc_ptr_set(q->stub.next, NULL);
118}
119
126static ALWAYS_INLINE void mpsc_push(struct mpsc *q, struct mpsc_node *n)
127{
128 struct mpsc_node *prev;
129 int key;
130
131 mpsc_ptr_set(n->next, NULL);
132
133 key = arch_irq_lock();
134 prev = (struct mpsc_node *)mpsc_ptr_set_get(q->head, n);
135 mpsc_ptr_set(prev->next, n);
137}
138
145static inline struct mpsc_node *mpsc_pop(struct mpsc *q)
146{
147 struct mpsc_node *head;
148 struct mpsc_node *tail = q->tail;
149 struct mpsc_node *next = (struct mpsc_node *)mpsc_ptr_get(tail->next);
150
151 /* Skip over the stub/sentinel */
152 if (tail == &q->stub) {
153 if (next == NULL) {
154 return NULL;
155 }
156
157 q->tail = next;
158 tail = next;
159 next = (struct mpsc_node *)mpsc_ptr_get(next->next);
160 }
161
162 /* If next is non-NULL then a valid node is found, return it */
163 if (next != NULL) {
164 q->tail = next;
165 return tail;
166 }
167
168 head = (struct mpsc_node *)mpsc_ptr_get(q->head);
169
170 /* If next is NULL, and the tail != HEAD then the queue has pending
171 * updates that can't yet be accessed.
172 */
173 if (tail != head) {
174 return NULL;
175 }
176
177 mpsc_push(q, &q->stub);
178
179 next = (struct mpsc_node *)mpsc_ptr_get(tail->next);
180
181 if (next != NULL) {
182 q->tail = next;
183 return tail;
184 }
185
186 return NULL;
187}
188
193#ifdef __cplusplus
194}
195#endif
196
197#endif /* ZEPHYR_SYS_MPSC_LOCKFREE_H_ */
static ALWAYS_INLINE unsigned int arch_irq_lock(void)
Disable all interrupts on the local CPU.
Definition irq.h:168
static ALWAYS_INLINE void arch_irq_unlock(unsigned int key)
Definition irq.h:176
void * atomic_ptr_t
Definition atomic_types.h:17
#define ALWAYS_INLINE
Definition common.h:129
atomic_ptr_t mpsc_ptr_t
Definition mpsc_lockfree.h:55
static ALWAYS_INLINE void mpsc_push(struct mpsc *q, struct mpsc_node *n)
Push a node.
Definition mpsc_lockfree.h:126
static struct mpsc_node * mpsc_pop(struct mpsc *q)
Pop a node off of the list.
Definition mpsc_lockfree.h:145
#define mpsc_ptr_set(ptr, val)
Definition mpsc_lockfree.h:58
#define mpsc_ptr_get(ptr)
Definition mpsc_lockfree.h:57
#define mpsc_ptr_set_get(ptr, val)
Definition mpsc_lockfree.h:59
static void mpsc_init(struct mpsc *q)
Initialize queue.
Definition mpsc_lockfree.h:113
Public kernel APIs.
struct k_queue q
Definition kobject.c:1320
static k_spinlock_key_t key
Definition spinlock_error_case.c:15
Queue member.
Definition mpsc_lockfree.h:79
mpsc_ptr_t next
Definition mpsc_lockfree.h:80
MPSC Queue.
Definition mpsc_lockfree.h:86
struct mpsc_node stub
Definition mpsc_lockfree.h:89
mpsc_ptr_t head
Definition mpsc_lockfree.h:87
struct mpsc_node * tail
Definition mpsc_lockfree.h:88