Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Dependencies: FXAS21002 FXOS8700Q
atomic-queue.h File Reference
A linked-list queue based on atomic access. More...
Go to the source code of this file.
Functions | |
| int | aq_push_tail (struct atomic_queue *q, struct atomic_queue_element *e) |
| Add an element to the tail of the queue. | |
| struct atomic_queue_element * | aq_pop_head (struct atomic_queue *q) |
| Get an element from the head of the queue. | |
| int | aq_empty (struct atomic_queue *q) |
| Check if there are any elements in the queue. | |
| unsigned | aq_count (struct atomic_queue *q) |
| Iterates over the queue and counts the elements in the queue. | |
| void | aq_initialize_element (struct atomic_queue_element *e) |
| Initialize an atomic queue element. | |
| int | aq_element_take (struct atomic_queue_element *e, void *ctx) |
| Take an element (this acquires the element lock) | |
| int | aq_element_release (struct atomic_queue_element *e, void **ctx) |
| Release an element (this releases the element lock) | |
| int | aq_atomic_cas_uintptr (uintptr_t *ptr, uintptr_t oldval, uintptr_t newval) |
| Atomic Compare and Set. | |
| int32_t | aq_atomic_inc_int32 (int32_t *ptr, int32_t inc) |
| Atomic increment. | |
Detailed Description
A linked-list queue based on atomic access.
This queue is designed explicitly for use in contexts where atomic access is desirable. Using an atomic queue comes with three major benefits:
1. This allows the queue to be used in contexts where some RTOS primitives (mutexes) cannot be used, such as interrupt context. 2. On many platforms, critical sections are very expensive, while atomics are not. Thus, there is a significant performance benefit to using atomic primitives wherever possible. 3. Atomic operations have the least effect on all other execution contexts on the device. Critical sections have performance and responsiveness side effects. Mutexes can disrupt the execution of other threads. Atomics do not affect the execution of other contexts and are immune to priority inversion.
In short, the atomics are the most cooperative way of building a queue.
Theory of Operation: The queue is intended to be multi-writer/multi-reader. Multi-writer semantics have been fully validated, but multi-reader semantics still require additional validation. It is recommended that the atomic queue be treated as multi-writer/single-reader until this validation is complete.
Assumptions: The queue MUST own all memory currently in the queue. Any modification to a queue element that is already enqueued can result in undefined behaviour. Because of this, the queue expects queue elements to be pool-allocated prior to insertion and freed after extraction.
To mitigate the possibility of a double-insert, the queue elements are populated with a "lock" field. This is used to indicate when the element is in use, to ensure that a parallel thread of execution cannot accidentally reuse an element that has already been inserted.
*NB:* Element locks are unnecessary when the atomic queue is used exclusively with pool allocated queue elements.
Queue Organization: The queue is a singly linked list. The list pointer is the tail pointer of the queue. The tail pointer points to the last element in the queue. To find the head of the queue, the dequeue mechanism traverses the list, starting at the tail of the queue until it finds the last list element, which is the head of the queue. Each queue element contains: * Next pointer * Lock element * Data (void* by default, custom element possible)
Element Insertion: To insert an element: Do: * Read the tail pointer (load exclusive). * Write the tail pointer into the next pointer of the new element. * Write the tail pointer with the address of the new element (store exclusive). Until the store is successful.
If a different thread of higher priority executed between the read and the last write, it will cause the new element to have the wrong next pointer. This is why the load-exclusive and store-exclusive are used. These are ARMv7 instructions that allow a given thread of execution to recognize whether it has been interrupted. If another thread has set the exclusive bit, then the store will fail.
Element Extraction: Extracting an element is much more complex than element insertion due to the need to traverse the queue.
1. Read the tail pointer 2. If the tail pointer is NULL, return NULL. 3. Set the current element to the tail pointer. 4. Read the current element's next pointer (load exclusive). 5. If the next pointer was NULL, start over (go to 1.) 6. Load the next element. 7. Check the value of the next element's next pointer 8. If it is non-NULL, set the current element pointer to the next element and go to 4. 9. Otherwise, set the current element's next pointer to NULL (store exclusive). 10. Return the next element.
There is the potential for another thread of execution to interrupt the search for the head of the queue. This should cause the dequeue mechanism to find a NULL next pointer in the current element. However, this may depend on other circumstances in the system, which might break the behaviour of the queue. Until this is fully analyzed, the queue should be treated as single- reader/multi-writer.
Definition in file atomic-queue.h.
Function Documentation
| int aq_atomic_cas_uintptr | ( | uintptr_t * | ptr, |
| uintptr_t | oldval, | ||
| uintptr_t | newval | ||
| ) |
Atomic Compare and Set.
Take a pointer to a uintptr_t, compare its current value to oldval. If it is as expected, try to write newval to the pointer target. Fail if interrupted.
- Parameters:
-
[in,out] ptr A pointer to the target of the atomic compare and set [in] oldval A value to compare with the target of ptr. [in] newval A new value to store to the target of ptr.
- Return values:
-
1 if newval was stored 0 if oldval did not match *ptr, or if the store was interrupted.
| int32_t aq_atomic_inc_int32 | ( | int32_t * | ptr, |
| int32_t | inc | ||
| ) |
Atomic increment.
Increment the value pointed to by ptr and increment it by inc atomically This is just a passthrough to __sync_add_and_fetch on platforms where it is supported.
- Parameters:
-
[in,out] ptr A pointer to the target of the increment [in] inc A value by which to increment *ptr
- Returns:
- the new value of *ptr
| unsigned aq_count | ( | struct atomic_queue * | q ) |
Iterates over the queue and counts the elements in the queue.
The value returned by this function may be invalid by the time it returns. Do not depend on this value except in a critical section.
- Returns:
- the number of elements in the queue
Definition at line 109 of file atomic-queue.c.
| int aq_element_release | ( | struct atomic_queue_element * | e, |
| void ** | ctx | ||
| ) |
Release an element (this releases the element lock)
- Parameters:
-
[in] element Element to release [out] ctx The element context will be written to this pointer
- Return values:
-
ATOMIC_QUEUE_SUCCESS for success ATOMIC_QUEUE_NULL_ELEMENT if the element is NULL ATOMIC_QUEUE_INVALID_CONTEXT if the pointer to the context is NULL
Definition at line 45 of file atomic-queue.c.
| int aq_element_take | ( | struct atomic_queue_element * | e, |
| void * | ctx | ||
| ) |
Take an element (this acquires the element lock)
- Parameters:
-
[in] element Element to take [in] ctx The element context. If a context is not needed, use ATOMIC_QUEUE_NO_CONTEXT. If a context is needed, pass a non-NULL pointer.
- Return values:
-
ATOMIC_QUEUE_SUCCESS for success ATOMIC_QUEUE_NULL_ELEMENT if the element is NULL ATOMIC_QUEUE_INVALID_CONTEXT if the context is NULL
Definition at line 29 of file atomic-queue.c.
| int aq_empty | ( | struct atomic_queue * | q ) |
Check if there are any elements in the queue.
Note that there is no guarantee that a queue which is not empty when this API is called will not be become empty before aq_pop_head is called
- Return values:
-
non-zero when the queue is empty 0 when the queue is not empty
Definition at line 104 of file atomic-queue.c.
| void aq_initialize_element | ( | struct atomic_queue_element * | e ) |
Initialize an atomic queue element.
WARNING: Only call this function one time per element, or it may result in undefined behaviour.
- Parameters:
-
[in] element Element to initialize
Definition at line 125 of file atomic-queue.c.
| struct atomic_queue_element* aq_pop_head | ( | struct atomic_queue * | q ) | [read] |
Get an element from the head of the queue.
This function iterates over the queue and removes an element from the head when it finds the head. This is slower than maintaining a head pointer, but it is necessary to ensure that a pop is completely atomic.
Element Extraction: Extracting an element is much more complex than element insertion due to the need to traverse the queue.
1. Read the tail pointer 2. If the tail pointer is NULL, return NULL. 3. Set the current element to the tail pointer. 4. Read the current element's next pointer (load exclusive). 5. If the next pointer was NULL, start over (go to 1.) 6. Load the next element. 7. Check the value of the next element's next pointer 8. If it is non-NULL, set the current element pointer to the next element and go to 4. 9. Otherwise, set the current element's next pointer to NULL (store exclusive). 10. Return the next element.
There is the potential for another thread of execution to interrupt the search for the head of the queue. This should cause the dequeue mechanism to find a NULL next pointer in the current element. However, this may depend on other circumstances in the system, which might break the behaviour of the queue. Until this is fully analyzed, the queue should be treated as single- reader/multi-writer.
- Parameters:
-
[in,out] q The queue to pop from
- Returns:
- The popped element or NULL if the queue was empty
Definition at line 69 of file atomic-queue.c.
| int aq_push_tail | ( | struct atomic_queue * | q, |
| struct atomic_queue_element * | e | ||
| ) |
Add an element to the tail of the queue.
Since the queue only maintains a tail pointer, this simply inserts the new element before the tail pointer
Element Insertion: To insert an element: Do: * Read the tail pointer (load exclusive). * Write the tail pointer into the next pointer of the new element. * Write the tail pointer with the address of the new element (store exclusive). Until the store is successful.
If a different thread of higher priority executed between the read and the last write, it will cause the new element to have the wrong next pointer. This is why the load-exclusive and store-exclusive are used. These are ARMv7 instructions that allow a given thread of execution to recognize whether it has been interrupted. If another thread has set the exclusive bit, then the store will fail.
- Parameters:
-
[in,out] q the queue structure to operate on [in] e The element to add to the queue
Definition at line 54 of file atomic-queue.c.
Generated on Tue Jul 12 2022 20:21:04 by
1.7.2