atomic_queue.h File Reference

Thread-safe queues. More...

#include <freeradius-devel/util/stdatomic.h>
#include <freeradius-devel/util/talloc.h>

Include dependency graph for atomic_queue.h:

Go to the source code of this file.

Typedefs
typedef struct fr_atomic_queue_s	fr_atomic_queue_t
typedef struct fr_atomic_ring_s	fr_atomic_ring_t
	Unbounded segmented single-producer / single-consumer queue.

Functions
void	fr_atomic_queue_debug (FILE *fp, fr_atomic_queue_t *aq)
	Dump an atomic queue.
void	fr_atomic_queue_free (fr_atomic_queue_t **aq)
	Free an atomic queue if it's not freed by ctx.
fr_atomic_queue_t *	fr_atomic_queue_malloc (TALLOC_CTX *ctx, size_t num, size_t elem_len)
	Create fixed-size atomic queue outside the talloc hierarchy, owned by a talloc context.
fr_atomic_queue_t *	fr_atomic_queue_mmap (TALLOC_CTX *ctx, int *fd, size_t num, size_t elem_len))
	Create or attach to a fixed-size atomic queue in shared memory, owned by a talloc context.
bool	fr_atomic_queue_mpmc_pop (fr_atomic_queue_t *aq, void *data)
	Copy an element out of the atomic queue, any number of consumers.
bool	fr_atomic_queue_mpmc_push (fr_atomic_queue_t *aq, void const *data)
	Copy an element into the atomic queue, any number of producers.
size_t	fr_atomic_queue_size (fr_atomic_queue_t *aq)
bool	fr_atomic_queue_spsc_pop (fr_atomic_queue_t *aq, void *data)
	Copy an element out of the atomic queue, one consumer only.
bool	fr_atomic_queue_spsc_push (fr_atomic_queue_t *aq, void const *data)
	Copy an element into the atomic queue, one producer only.
fr_atomic_queue_t *	fr_atomic_queue_talloc (TALLOC_CTX *ctx, size_t num, size_t elem_len)
	Create a fixed-size atomic queue.
fr_atomic_ring_t *	fr_atomic_ring_alloc (TALLOC_CTX *ctx, size_t seg_size)
	Allocate an empty SPSC ring.
void	fr_atomic_ring_free (fr_atomic_ring_t **ring)
	Free the ring and all remaining segments.
bool	fr_atomic_ring_pop (fr_atomic_ring_t *ring, void **p_data)
	Pop a pointer from the ring, advancing past drained segments.
bool	fr_atomic_ring_push (fr_atomic_ring_t *ring, void *data)
	Push a pointer into the ring; allocate a new segment on overflow.

Detailed Description

Thread-safe queues.

Id

bd00b1f00a94ca7a476aa84c001b28a19c8a90fe

Copyright

2016 Alan DeKok (aland.nosp@m.@fre.nosp@m.eradi.nosp@m.us.o.nosp@m.rg)

Definition in file atomic_queue.h.

Typedef Documentation

fr_atomic_queue_t

typedef struct fr_atomic_queue_s fr_atomic_queue_t

Definition at line 40 of file atomic_queue.h.

fr_atomic_ring_t

typedef struct fr_atomic_ring_s fr_atomic_ring_t

Unbounded segmented single-producer / single-consumer queue.

Internally a linked list of fixed-size fr_atomic_queue_t segments. When the producer's current segment fills, a new segment is malloc'd and linked in; the consumer drains segments in order and frees them as it advances. Allocation on the producer side uses raw malloc (not talloc), so the producer thread is free to be one that cannot safely use talloc (e.g. a library-owned callback thread).

Exactly one producer and one consumer. Not safe for MPMC use.

Definition at line 66 of file atomic_queue.h.

Function Documentation

fr_atomic_queue_debug()

void fr_atomic_queue_debug	(	FILE *	fp,
		fr_atomic_queue_t *	aq
	)

Dump an atomic queue.

Absolutely NOT thread-safe.

Parameters

[in]	aq	The atomic queue to debug.
[in]	fp	where the debugging information will be printed.

Definition at line 1061 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_free()

void fr_atomic_queue_free

(

fr_atomic_queue_t **

aq

)

Free an atomic queue if it's not freed by ctx.

The queue memory must be cache line aligned, so it lives in one of three places: a talloc aligned array (chunk is the array), a raw allocation owned by a talloc handle (chunk is the handle, whose destructor frees the queue), or a raw allocation with no owner (chunk is NULL).

Definition at line 557 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_malloc()

fr_atomic_queue_t * fr_atomic_queue_malloc	(	TALLOC_CTX *	ctx,
		size_t	num,
		size_t	elem_len
	)

Create fixed-size atomic queue outside the talloc hierarchy, owned by a talloc context.

The queue itself is a raw posix_memalign allocation, so it can be pushed to and popped from by threads where talloc is not safe, and can later be placed in memory talloc does not manage. A small owner handle allocated in ctx frees the queue when ctx is freed, or when the caller calls fr_atomic_queue_free.

Parameters

[in]	ctx	The talloc ctx which owns the queue.
[in]	num	The number of entries in the queue.
[in]	elem_len	The size of one element.

Returns

• NULL on error.
• fr_atomic_queue_t *, a pointer to the allocated and initialized queue.

Definition at line 416 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_mmap()

fr_atomic_queue_t * fr_atomic_queue_mmap	(	TALLOC_CTX *	ctx,
		int *	fd,
		size_t	num,
		size_t	elem_len
	)

Create or attach to a fixed-size atomic queue in shared memory, owned by a talloc context.

With *fd negative, a new anonymous shared memory object is created, the queue initialised in it, and its descriptor written back for the caller to pass to another process. With a descriptor, that object is mapped and must already hold a queue of this size; the mapping is not reinitialised. Either way the handle owns the descriptor and closes it with the mapping. Pages are aligned well beyond a cache line.

Parameters

[in]	ctx	The talloc ctx which owns the queue.
[in,out]	fd	A shared memory object holding a queue to attach to, or -1 to create one, in which case the new descriptor is written here.
[in]	num	The number of entries in the queue.
[in]	elem_len	The size of one element.

Returns

• NULL on error, with the error in fr_strerror.
• fr_atomic_queue_t *, a pointer to the mapped queue.

Definition at line 482 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_mpmc_pop()

bool fr_atomic_queue_mpmc_pop	(	fr_atomic_queue_t *	aq,
		void *	data
	)

Copy an element out of the atomic queue, any number of consumers.

For a queue of pointers, data is the address of a pointer to fill.

Parameters

[in]	aq	the atomic queue to retrieve data from.
[out]	data	where to write the element, elem_len long.

Returns

• true on successful pop
• false on queue empty

Definition at line 701 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_mpmc_push()

bool fr_atomic_queue_mpmc_push	(	fr_atomic_queue_t *	aq,
		void const *	data
	)

Copy an element into the atomic queue, any number of producers.

For a queue of pointers, data is the address of the pointer.

Parameters

[in]	aq	The atomic queue to add data to.
[in]	data	the element, elem_len long.

Returns

• true on successful push
• false on queue full

Definition at line 579 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_size()

size_t fr_atomic_queue_size

(

fr_atomic_queue_t *

aq

)

Definition at line 813 of file atomic_queue.c.

Here is the caller graph for this function:

fr_atomic_queue_spsc_pop()

bool fr_atomic_queue_spsc_pop	(	fr_atomic_queue_t *	aq,
		void *	data
	)

Copy an element out of the atomic queue, one consumer only.

With one consumer nobody else advances tail, so no compare-and-swap: the slot is full when its sequence number is one past tail.

Parameters

[in]	aq	the atomic queue to retrieve data from.
[out]	data	where to write the element, elem_len long.

Returns

• true on successful pop
• false on queue empty

Definition at line 799 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_spsc_push()

bool fr_atomic_queue_spsc_push	(	fr_atomic_queue_t *	aq,
		void const *	data
	)

Copy an element into the atomic queue, one producer only.

The same slots and sequence numbers as the mpmc functions, so the consumer may be either flavour. With one producer nobody else advances head, so there is nothing to race and no compare-and-swap: the slot is free when its sequence number equals head.

Parameters

[in]	aq	The atomic queue to add data to.
[in]	data	the element, elem_len long.

Returns

• true on successful push
• false on queue full

Definition at line 774 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_queue_talloc()

fr_atomic_queue_t * fr_atomic_queue_talloc	(	TALLOC_CTX *	ctx,
		size_t	num,
		size_t	elem_len
	)

Create a fixed-size atomic queue.

Push and pop copy elem_len bytes in and out, so a queue of pointers is a queue of sizeof(uintptr_t) elements whose callers pass the address of the pointer. Nothing is allocated per element, and nothing has to be freed by the consumer.

Note

the queue must be freed explicitly by the ctx being freed, or by using the fr_atomic_queue_free function.

Parameters

[in]	ctx	The talloc ctx to allocate the queue in.
[in]	num	The number of entries in the queue.
[in]	elem_len	The size of one element. Elements are 8 byte aligned.

Returns

• NULL on error, including an element which does not fit in a cache line.
• fr_atomic_queue_t *, a pointer to the allocated and initialized queue.

Definition at line 310 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_ring_alloc()

fr_atomic_ring_t * fr_atomic_ring_alloc	(	TALLOC_CTX *	ctx,
		size_t	seg_size
	)

Allocate an empty SPSC ring.

Parameters

[in]	ctx	talloc ctx that owns the ring handle (segments live outside talloc; they are freed by the ring's destructor).
[in]	seg_size	Per-segment capacity. Rounded up to a power of 2.

Returns

• NULL on error.
• A ring containing one initial (empty) segment.

Definition at line 900 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_ring_free()

void fr_atomic_ring_free

(

fr_atomic_ring_t **

ring_p

)

Free the ring and all remaining segments.

Equivalent to talloc_free() on the ring, but nulls the caller's handle in the style of fr_atomic_queue_free.

Definition at line 929 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_ring_pop()

bool fr_atomic_ring_pop	(	fr_atomic_ring_t *	ring,
		void **	p_data
	)

Pop a pointer from the ring, advancing past drained segments.

Single-consumer only. Must not be called concurrently with itself.

Parameters

[in]	ring	Ring to pop from.
[out]	p_data	Where to write the popped value on success.

Returns

• true if a value was popped.
• false if the ring is currently empty.

Definition at line 995 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_atomic_ring_push()

bool fr_atomic_ring_push	(	fr_atomic_ring_t *	ring,
		void *	data
	)

Push a pointer into the ring; allocate a new segment on overflow.

Single-producer only. Must not be called concurrently with itself.

Parameters

[in]	ring	Ring to push into.
[in]	data	Value to push (must be non-NULL).

Returns

• true on success.
• false if both the current segment is full and a new segment could not be allocated.

Definition at line 968 of file atomic_queue.c.

Here is the call graph for this function:

Here is the caller graph for this function: