// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_
#define CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_

#include <stddef.h>

#include "base/atomicops.h"
#include "base/macros.h"
#include "base/memory/aligned_memory.h"

#define CACHELINE_ALIGNED ALIGNAS(64)

namespace content {

MSVC_PUSH_DISABLE_WARNING(4324)  // structure was padded due to align

// Lock-free cache-friendly sampling circular queue for large
// records. Intended for fast transfer of large records between a
// single producer and a single consumer. If the queue is full,
// StartEnqueue will return nullptr. The queue is designed with
// a goal in mind to evade cache lines thrashing by preventing
// simultaneous reads and writes to adjanced memory locations.
template <typename T, unsigned Length>
class LockFreeCircularQueue {
 public:
  // Executed on the application thread.
  LockFreeCircularQueue();
  ~LockFreeCircularQueue();

  // StartEnqueue returns a pointer to a memory location for storing the next
  // record or nullptr if all entries are full at the moment.
  T* StartEnqueue();
  // Notifies the queue that the producer has complete writing data into the
  // memory returned by StartEnqueue and it can be passed to the consumer.
  void FinishEnqueue();

  // Executed on the consumer (analyzer) thread.
  // Retrieves, but does not remove, the head of this queue, returning nullptr
  // if this queue is empty. After the record had been read by a consumer,
  // Remove must be called.
  T* Peek();
  void Remove();

  // The class fields have stricter alignment requirements than a normal new
  // can fulfil, so we need to provide our own new/delete here.
  void* operator new(size_t size);
  void operator delete(void* ptr);

 private:
  // Reserved values for the entry marker.
  enum {
    kEmpty,  // Marks clean (processed) entries.
    kFull    // Marks entries already filled by the producer but not yet
             // completely processed by the consumer.
  };

  struct CACHELINE_ALIGNED Entry {
    Entry() : marker(kEmpty) {}
    T record;
    base::subtle::Atomic32 marker;
  };

  Entry* Next(Entry* entry);

  Entry buffer_[Length];
  CACHELINE_ALIGNED Entry* enqueue_pos_;
  CACHELINE_ALIGNED Entry* dequeue_pos_;

  DISALLOW_COPY_AND_ASSIGN(LockFreeCircularQueue);
};

MSVC_POP_WARNING()

template <typename T, unsigned L>
LockFreeCircularQueue<T, L>::LockFreeCircularQueue()
    : enqueue_pos_(buffer_), dequeue_pos_(buffer_) {
}

template <typename T, unsigned L>
LockFreeCircularQueue<T, L>::~LockFreeCircularQueue() {
}

template <typename T, unsigned L>
T* LockFreeCircularQueue<T, L>::Peek() {
  base::subtle::MemoryBarrier();
  if (base::subtle::Acquire_Load(&dequeue_pos_->marker) == kFull) {
    return &dequeue_pos_->record;
  }
  return nullptr;
}

template <typename T, unsigned L>
void LockFreeCircularQueue<T, L>::Remove() {
  base::subtle::Release_Store(&dequeue_pos_->marker, kEmpty);
  dequeue_pos_ = Next(dequeue_pos_);
}

template <typename T, unsigned L>
T* LockFreeCircularQueue<T, L>::StartEnqueue() {
  base::subtle::MemoryBarrier();
  if (base::subtle::Acquire_Load(&enqueue_pos_->marker) == kEmpty) {
    return &enqueue_pos_->record;
  }
  return nullptr;
}

template <typename T, unsigned L>
void LockFreeCircularQueue<T, L>::FinishEnqueue() {
  base::subtle::Release_Store(&enqueue_pos_->marker, kFull);
  enqueue_pos_ = Next(enqueue_pos_);
}

template <typename T, unsigned L>
typename LockFreeCircularQueue<T, L>::Entry* LockFreeCircularQueue<T, L>::Next(
    Entry* entry) {
  Entry* next = entry + 1;
  if (next == &buffer_[L])
    return buffer_;
  return next;
}

template <typename T, unsigned L>
void* LockFreeCircularQueue<T, L>::operator new(size_t size) {
  typedef LockFreeCircularQueue<T, L> QueueTypeAlias;
  return base::AlignedAlloc(size, ALIGNOF(QueueTypeAlias));
}

template <typename T, unsigned L>
void LockFreeCircularQueue<T, L>::operator delete(void* ptr) {
  base::AlignedFree(ptr);
}

}  // namespace content

#endif  // CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_