|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
310c69 |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
310c69 |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
310c69 |
* of the License, or (at your option) any later version.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
310c69 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
310c69 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
310c69 |
* GNU General Public License for more details.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
310c69 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
310c69 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
310c69 |
* 02110-1301, USA.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* $Id: //eng/uds-releases/jasper/src/uds/util/funnelQueue.h#2 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#ifndef FUNNEL_QUEUE_H
|
|
Packit Service |
310c69 |
#define FUNNEL_QUEUE_H
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "atomicDefs.h"
|
|
Packit Service |
310c69 |
#include "compiler.h"
|
|
Packit Service |
310c69 |
#include "cpu.h"
|
|
Packit Service |
310c69 |
#include "typeDefs.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* A FunnelQueue is a simple lock-free (almost) queue that accepts entries
|
|
Packit Service |
310c69 |
* from multiple threads (multi-producer) and delivers them to a single thread
|
|
Packit Service |
310c69 |
* (single-consumer). "Funnel" is an attempt to evoke the image of requests
|
|
Packit Service |
310c69 |
* from more than one producer being "funneled down" to a single consumer.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This is an unsynchronized but thread-safe data structure when used as
|
|
Packit Service |
310c69 |
* intended. There is no mechanism to ensure that only one thread is consuming
|
|
Packit Service |
310c69 |
* from the queue, so if that is done mistakenly, it will not be trapped, and
|
|
Packit Service |
310c69 |
* the resulting behavior is undefined. Clients must not directly access or
|
|
Packit Service |
310c69 |
* manipulate the internals, which are only exposed for the purpose of
|
|
Packit Service |
310c69 |
* allowing the very simple enqueue operation to be in-lined.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The implementation requires that a FunnelQueueEntry structure (a link
|
|
Packit Service |
310c69 |
* pointer) be embedded in the queue entries, and pointers to those structures
|
|
Packit Service |
310c69 |
* are used exclusively by the queue. No macros are defined to template the
|
|
Packit Service |
310c69 |
* queue, so the offset of the FunnelQueueEntry in the records placed in the
|
|
Packit Service |
310c69 |
* queue must all have a fixed offset so the client can derive their structure
|
|
Packit Service |
310c69 |
* pointer from the entry pointer returned by funnelQueuePoll().
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* Callers are wholly responsible for allocating and freeing the entries.
|
|
Packit Service |
310c69 |
* Entries may be freed as soon as they are returned since this queue is not
|
|
Packit Service |
310c69 |
* susceptible to the "ABA problem" present in many lock-free data structures.
|
|
Packit Service |
310c69 |
* The queue is dynamically allocated to ensure cache-line alignment, but no
|
|
Packit Service |
310c69 |
* other dynamic allocation is used.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The algorithm is not actually 100% lock-free. There is a single point in
|
|
Packit Service |
310c69 |
* funnelQueuePut() at which a pre-empted producer will prevent the consumers
|
|
Packit Service |
310c69 |
* from seeing items added to the queue by later producers, and only if the
|
|
Packit Service |
310c69 |
* queue is short enough or the consumer fast enough for it to reach what was
|
|
Packit Service |
310c69 |
* the end of the queue at the time of the pre-empt.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The consumer function, funnelQueuePoll(), will return NULL when the queue
|
|
Packit Service |
310c69 |
* is empty. To wait for data to consume, spin (if safe) or combine the queue
|
|
Packit Service |
310c69 |
* with an EventCount to signal the presence of new entries.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* The queue link structure that must be embedded in client entries.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
typedef struct funnelQueueEntry {
|
|
Packit Service |
310c69 |
// The next (newer) entry in the queue.
|
|
Packit Service |
310c69 |
struct funnelQueueEntry * volatile next;
|
|
Packit Service |
310c69 |
} FunnelQueueEntry;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* The dynamically allocated queue structure, which is aligned to a cache line
|
|
Packit Service |
310c69 |
* boundary when allocated. This should be consider opaque; it is exposed here
|
|
Packit Service |
310c69 |
* so funnelQueuePut() can be in-lined.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) funnelQueue {
|
|
Packit Service |
310c69 |
// The producers' end of the queue--an atomically exchanged pointer that
|
|
Packit Service |
310c69 |
// will never be NULL.
|
|
Packit Service |
310c69 |
FunnelQueueEntry * volatile newest;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// The consumer's end of the queue. Owned by the consumer and never NULL.
|
|
Packit Service |
310c69 |
FunnelQueueEntry *oldest __attribute__((aligned(CACHE_LINE_BYTES)));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// A re-usable dummy entry used to provide the non-NULL invariants above.
|
|
Packit Service |
310c69 |
FunnelQueueEntry stub;
|
|
Packit Service |
310c69 |
} FunnelQueue;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Construct and initialize a new, empty queue.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queuePtr a pointer in which to store the queue
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int makeFunnelQueue(FunnelQueue **queuePtr)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Free a queue.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This will not free any entries in the queue. The caller must ensure that
|
|
Packit Service |
310c69 |
* either the queue will be empty or that any entries in the queue will not be
|
|
Packit Service |
310c69 |
* leaked by dropping the references from queue.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queue the queue to free
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
void freeFunnelQueue(FunnelQueue *queue);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Put an entry on the end of the queue.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The entry pointer must be to the FunnelQueueEntry embedded in the caller's
|
|
Packit Service |
310c69 |
* data structure. The caller must be able to derive the address of the start
|
|
Packit Service |
310c69 |
* of their data structure from the pointer that passed in here, so every
|
|
Packit Service |
310c69 |
* entry in the queue must have the FunnelQueueEntry at the same offset within
|
|
Packit Service |
310c69 |
* the client's structure.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queue the queue on which to place the entry
|
|
Packit Service |
310c69 |
* @param entry the entry to be added to the queue
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE void funnelQueuePut(FunnelQueue *queue, FunnelQueueEntry *entry)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Barrier requirements: All stores relating to the entry ("next" pointer,
|
|
Packit Service |
310c69 |
* containing data structure fields) must happen before the previous->next
|
|
Packit Service |
310c69 |
* store making it visible to the consumer. Also, the entry's "next" field
|
|
Packit Service |
310c69 |
* initialization to NULL must happen before any other producer threads can
|
|
Packit Service |
310c69 |
* see the entry (the xchg) and try to update the "next" field.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* xchg implements a full barrier.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
entry->next = NULL;
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* The xchg macro in the PPC kernel calls a function that takes a void*
|
|
Packit Service |
310c69 |
* argument, triggering a warning about dropping the volatile qualifier.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
#pragma GCC diagnostic push
|
|
Packit Service |
310c69 |
#if __GNUC__ >= 5
|
|
Packit Service |
310c69 |
#pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"
|
|
Packit Service |
310c69 |
#endif
|
|
Packit Service |
310c69 |
FunnelQueueEntry *previous = xchg(&queue->newest, entry);
|
|
Packit Service |
310c69 |
#pragma GCC diagnostic pop
|
|
Packit Service |
310c69 |
// Pre-empts between these two statements hide the rest of the queue from
|
|
Packit Service |
310c69 |
// the consumer, preventing consumption until the following assignment runs.
|
|
Packit Service |
310c69 |
previous->next = entry;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Poll a queue, removing the oldest entry if the queue is not empty. This
|
|
Packit Service |
310c69 |
* function must only be called from a single consumer thread.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queue the queue from which to remove an entry
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the oldest entry in the queue, or NULL if the queue is empty.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
FunnelQueueEntry *funnelQueuePoll(FunnelQueue *queue)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Check whether the funnel queue is empty or not. This function must only be
|
|
Packit Service |
310c69 |
* called from a single consumer thread, as with funnelQueuePoll.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* If the queue is in a transition state with one or more entries being added
|
|
Packit Service |
310c69 |
* such that the list view is incomplete, it may not be possible to retrieve an
|
|
Packit Service |
310c69 |
* entry with the funnelQueuePoll() function. In such states this function will
|
|
Packit Service |
310c69 |
* report an empty indication.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queue the queue which to check for entries.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true iff queue contains no entry which can be retrieved
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
bool isFunnelQueueEmpty(FunnelQueue *queue)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Check whether the funnel queue is idle or not. This function must only be
|
|
Packit Service |
310c69 |
* called from a single consumer thread, as with funnel_queue_poll.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* If the queue has entries available to be retrieved, it is not idle. If the
|
|
Packit Service |
310c69 |
* queue is in a transition state with one or more entries being added such
|
|
Packit Service |
310c69 |
* that the list view is incomplete, it may not be possible to retrieve an
|
|
Packit Service |
310c69 |
* entry with the funnel_queue_poll() function, but the queue will not be
|
|
Packit Service |
310c69 |
* considered idle.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param queue the queue which to check for entries.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true iff queue contains no entry which can be retrieved nor is
|
|
Packit Service |
310c69 |
* known to be having an entry added
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
bool isFunnelQueueIdle(FunnelQueue *queue)
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#endif /* FUNNEL_QUEUE_H */
|