147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org/* 247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * Copyright 2011 The WebRTC Project Authors. All rights reserved. 347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * 447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * Use of this source code is governed by a BSD-style license 547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * that can be found in the LICENSE file in the root of the source 647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * tree. An additional intellectual property rights grant can be found 747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * in the file PATENTS. All contributing project authors may 847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org * be found in the AUTHORS file in the root of the source tree. 947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org */ 1047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 1147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#ifndef WEBRTC_BASE_ATOMICOPS_H_ 1247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#define WEBRTC_BASE_ATOMICOPS_H_ 1347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 1447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include <string> 1547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 1647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "webrtc/base/basictypes.h" 1747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "webrtc/base/common.h" 1847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "webrtc/base/logging.h" 1947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#include "webrtc/base/scoped_ptr.h" 2047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 2147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.orgnamespace rtc { 2247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 2347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// A single-producer, single-consumer, fixed-size queue. 2447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// All methods not ending in Unsafe can be safely called without locking, 2547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// provided that calls to consumer methods (Peek/Pop) or producer methods (Push) 2647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// only happen on a single thread per method type. If multiple threads need to 2747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// read simultaneously or write simultaneously, other synchronization is 2847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// necessary. Synchronization is also required if a call into any Unsafe method 2947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// could happen at the same time as a call to any other method. 3047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.orgtemplate <typename T> 3147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.orgclass FixedSizeLockFreeQueue { 3247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org private: 3347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org// Atomic primitives and memory barrier 3447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#if defined(__arm__) 3547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org typedef uint32 Atomic32; 3647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 3747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Copied from google3/base/atomicops-internals-arm-v6plus.h 3847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org static inline void MemoryBarrier() { 3947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org asm volatile("dmb":::"memory"); 4047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 4147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 4247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Adapted from google3/base/atomicops-internals-arm-v6plus.h 4347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org static inline void AtomicIncrement(volatile Atomic32* ptr) { 4447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org Atomic32 str_success, value; 4547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org asm volatile ( 4647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "1:\n" 4747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "ldrex %1, [%2]\n" 4847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "add %1, %1, #1\n" 4947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "strex %0, %1, [%2]\n" 5047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "teq %0, #0\n" 5147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org "bne 1b" 5247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org : "=&r"(str_success), "=&r"(value) 5347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org : "r" (ptr) 5447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org : "cc", "memory"); 5547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 5647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#elif !defined(SKIP_ATOMIC_CHECK) 5747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#error "No atomic operations defined for the given architecture." 5847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#endif 5947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 6047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org public: 6147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Constructs an empty queue, with capacity 0. 6247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FixedSizeLockFreeQueue() : pushed_count_(0), 6347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org popped_count_(0), 6447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org capacity_(0), 6547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org data_() {} 6647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Constructs an empty queue with the given capacity. 6747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org FixedSizeLockFreeQueue(size_t capacity) : pushed_count_(0), 6847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org popped_count_(0), 6947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org capacity_(capacity), 7047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org data_(new T[capacity]) {} 7147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 7247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Pushes a value onto the queue. Returns true if the value was successfully 7347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // pushed (there was space in the queue). This method can be safely called at 7447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // the same time as PeekFront/PopFront. 7547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org bool PushBack(T value) { 7647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (capacity_ == 0) { 7747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org LOG(LS_WARNING) << "Queue capacity is 0."; 7847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 7947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 8047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (IsFull()) { 8147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 8247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 8347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 8447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org data_[pushed_count_ % capacity_] = value; 8547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Make sure the data is written before the count is incremented, so other 8647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // threads can't see the value exists before being able to read it. 8747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org MemoryBarrier(); 8847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org AtomicIncrement(&pushed_count_); 8947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 9047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 9147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 9247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Retrieves the oldest value pushed onto the queue. Returns true if there was 9347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // an item to peek (the queue was non-empty). This method can be safely called 9447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // at the same time as PushBack. 9547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org bool PeekFront(T* value_out) { 9647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (capacity_ == 0) { 9747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org LOG(LS_WARNING) << "Queue capacity is 0."; 9847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 9947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 10047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (IsEmpty()) { 10147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 10247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 10347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 10447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org *value_out = data_[popped_count_ % capacity_]; 10547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 10647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 10747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 10847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Retrieves the oldest value pushed onto the queue and removes it from the 10947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // queue. Returns true if there was an item to pop (the queue was non-empty). 11047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // This method can be safely called at the same time as PushBack. 11147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org bool PopFront(T* value_out) { 11247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org if (PeekFront(value_out)) { 11347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org AtomicIncrement(&popped_count_); 11447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return true; 11547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 11647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org return false; 11747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 11847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 11947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Clears the current items in the queue and sets the new (fixed) size. This 12047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // method cannot be called at the same time as any other method. 12147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org void ClearAndResizeUnsafe(int new_capacity) { 12247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org capacity_ = new_capacity; 12347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org data_.reset(new T[new_capacity]); 12447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org pushed_count_ = 0; 12547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org popped_count_ = 0; 12647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org } 12747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 12847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Returns true if there is no space left in the queue for new elements. 12947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org int IsFull() const { return pushed_count_ == popped_count_ + capacity_; } 13047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Returns true if there are no elements in the queue. 13147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org int IsEmpty() const { return pushed_count_ == popped_count_; } 13247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Returns the current number of elements in the queue. This is always in the 13347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // range [0, capacity] 13447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org size_t Size() const { return pushed_count_ - popped_count_; } 13547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 13647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org // Returns the capacity of the queue (max size). 13747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org size_t capacity() const { return capacity_; } 13847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 13947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org private: 14047be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org volatile Atomic32 pushed_count_; 14147be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org volatile Atomic32 popped_count_; 14247be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org size_t capacity_; 14347be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org rtc::scoped_ptr<T[]> data_; 14447be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org DISALLOW_COPY_AND_ASSIGN(FixedSizeLockFreeQueue); 14547be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org}; 14647be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 14747be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org} 14847be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org 14947be73b8629244d6bb63a28198f97f040ce53d21henrike@webrtc.org#endif // WEBRTC_BASE_ATOMICOPS_H_ 150