/*
 * 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 */