/*

 * Copyright (c) 2020 Red Hat, Inc.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License

 * as published by the Free Software Foundation; either version 2

 * of the License, or (at your option) any later version.

 * 

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

 * 02110-1301, USA. 

 *

 * $Id: //eng/uds-releases/jasper/src/uds/util/funnelQueue.h#2 $

 */

#ifndef FUNNEL_QUEUE_H

#define FUNNEL_QUEUE_H

#include "atomicDefs.h"

#include "compiler.h"

#include "cpu.h"

#include "typeDefs.h"

/**

 * A FunnelQueue is a simple lock-free (almost) queue that accepts entries

 * from multiple threads (multi-producer) and delivers them to a single thread

 * (single-consumer). "Funnel" is an attempt to evoke the image of requests

 * from more than one producer being "funneled down" to a single consumer.

 *

 * This is an unsynchronized but thread-safe data structure when used as

 * intended. There is no mechanism to ensure that only one thread is consuming

 * from the queue, so if that is done mistakenly, it will not be trapped, and

 * the resulting behavior is undefined. Clients must not directly access or

 * manipulate the internals, which are only exposed for the purpose of

 * allowing the very simple enqueue operation to be in-lined.

 *

 * The implementation requires that a FunnelQueueEntry structure (a link

 * pointer) be embedded in the queue entries, and pointers to those structures

 * are used exclusively by the queue. No macros are defined to template the

 * queue, so the offset of the FunnelQueueEntry in the records placed in the

 * queue must all have a fixed offset so the client can derive their structure

 * pointer from the entry pointer returned by funnelQueuePoll().

 *

 * Callers are wholly responsible for allocating and freeing the entries.

 * Entries may be freed as soon as they are returned since this queue is not

 * susceptible to the "ABA problem" present in many lock-free data structures.

 * The queue is dynamically allocated to ensure cache-line alignment, but no

 * other dynamic allocation is used.

 *

 * The algorithm is not actually 100% lock-free. There is a single point in

 * funnelQueuePut() at which a pre-empted producer will prevent the consumers

 * from seeing items added to the queue by later producers, and only if the

 * queue is short enough or the consumer fast enough for it to reach what was

 * the end of the queue at the time of the pre-empt.

 *

 * The consumer function, funnelQueuePoll(), will return NULL when the queue

 * is empty. To wait for data to consume, spin (if safe) or combine the queue

 * with an EventCount to signal the presence of new entries.

 **/

/**

 * The queue link structure that must be embedded in client entries.

 **/

typedef struct funnelQueueEntry {

  // The next (newer) entry in the queue.

  struct funnelQueueEntry * volatile next;

} FunnelQueueEntry;

/**

 * The dynamically allocated queue structure, which is aligned to a cache line

 * boundary when allocated. This should be consider opaque; it is exposed here

 * so funnelQueuePut() can be in-lined.

 **/

typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) funnelQueue {

  // The producers' end of the queue--an atomically exchanged pointer that

  // will never be NULL.

  FunnelQueueEntry * volatile newest;

  // The consumer's end of the queue. Owned by the consumer and never NULL.

  FunnelQueueEntry *oldest __attribute__((aligned(CACHE_LINE_BYTES)));

  // A re-usable dummy entry used to provide the non-NULL invariants above.

  FunnelQueueEntry stub;

} FunnelQueue;

/**

 * Construct and initialize a new, empty queue.

 *

 * @param queuePtr  a pointer in which to store the queue

 *

 * @return UDS_SUCCESS or an error code

 **/

int makeFunnelQueue(FunnelQueue **queuePtr)

  __attribute__((warn_unused_result));

/**

 * Free a queue.

 *

 * This will not free any entries in the queue. The caller must ensure that

 * either the queue will be empty or that any entries in the queue will not be

 * leaked by dropping the references from queue.

 *

 * @param queue  the queue to free

 **/

void freeFunnelQueue(FunnelQueue *queue);

/**

 * Put an entry on the end of the queue.

 *

 * The entry pointer must be to the FunnelQueueEntry embedded in the caller's

 * data structure. The caller must be able to derive the address of the start

 * of their data structure from the pointer that passed in here, so every

 * entry in the queue must have the FunnelQueueEntry at the same offset within

 * the client's structure.

 *

 * @param queue  the queue on which to place the entry

 * @param entry  the entry to be added to the queue

 **/

static INLINE void funnelQueuePut(FunnelQueue *queue, FunnelQueueEntry *entry)

{

  /*

   * Barrier requirements: All stores relating to the entry ("next" pointer,

   * containing data structure fields) must happen before the previous->next

   * store making it visible to the consumer. Also, the entry's "next" field

   * initialization to NULL must happen before any other producer threads can

   * see the entry (the xchg) and try to update the "next" field.

   *

   * xchg implements a full barrier.

   */

  entry->next = NULL;

  /*

   * The xchg macro in the PPC kernel calls a function that takes a void*

   * argument, triggering a warning about dropping the volatile qualifier.

   */

#pragma GCC diagnostic push

#if __GNUC__ >= 5

#pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"

#endif

  FunnelQueueEntry *previous = xchg(&queue->newest, entry);

#pragma GCC diagnostic pop

  // Pre-empts between these two statements hide the rest of the queue from

  // the consumer, preventing consumption until the following assignment runs.

  previous->next = entry;

}

/**

 * Poll a queue, removing the oldest entry if the queue is not empty. This

 * function must only be called from a single consumer thread.

 *

 * @param queue  the queue from which to remove an entry

 *

 * @return the oldest entry in the queue, or NULL if the queue is empty.

 **/

FunnelQueueEntry *funnelQueuePoll(FunnelQueue *queue)

  __attribute__((warn_unused_result));

/**

 * Check whether the funnel queue is empty or not. This function must only be

 * called from a single consumer thread, as with funnelQueuePoll.

 *

 * If the queue is in a transition state with one or more entries being added

 * such that the list view is incomplete, it may not be possible to retrieve an

 * entry with the funnelQueuePoll() function. In such states this function will

 * report an empty indication.

 *

 * @param queue  the queue which to check for entries.

 *

 * @return true iff queue contains no entry which can be retrieved

 **/

bool isFunnelQueueEmpty(FunnelQueue *queue)

  __attribute__((warn_unused_result));

/**

 * Check whether the funnel queue is idle or not. This function must only be

 * called from a single consumer thread, as with funnel_queue_poll.

 *

 * If the queue has entries available to be retrieved, it is not idle. If the

 * queue is in a transition state with one or more entries being added such

 * that the list view is incomplete, it may not be possible to retrieve an

 * entry with the funnel_queue_poll() function, but the queue will not be

 * considered idle.

 *

 * @param queue  the queue which to check for entries.

 *

 * @return true iff queue contains no entry which can be retrieved nor is

 *              known to be having an entry added

 **/

bool isFunnelQueueIdle(FunnelQueue *queue)

  __attribute__((warn_unused_result));

#endif /* FUNNEL_QUEUE_H */