1e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman/* 2e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * Copyright (C) 2012 The Android Open Source Project 3e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * 4e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * Licensed under the Apache License, Version 2.0 (the "License"); 5e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * you may not use this file except in compliance with the License. 6e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * You may obtain a copy of the License at 7e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * 8e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * http://www.apache.org/licenses/LICENSE-2.0 9e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * 10e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * Unless required by applicable law or agreed to in writing, software 11e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * distributed under the License is distributed on an "AS IS" BASIS, 12e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * See the License for the specific language governing permissions and 14e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman * limitations under the License. 15e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman */ 16e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 17e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#ifndef SINGLE_STATE_QUEUE_H 18e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#define SINGLE_STATE_QUEUE_H 19e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 20e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman// Non-blocking single element state queue, or 21e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman// Non-blocking single-reader / single-writer multi-word atomic load / store 22e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 23e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#include <stdint.h> 24e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#include <cutils/atomic.h> 25e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 26e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatramannamespace android { 27e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 28e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatramantemplate<typename T> class SingleStateQueue { 29e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 30e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatramanpublic: 31e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 32e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman class Mutator; 33e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman class Observer; 34e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 35e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman enum SSQ_STATUS { 36e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman SSQ_PENDING, /* = 0 */ 37e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman SSQ_READ, 38e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman SSQ_DONE, 39e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman }; 40e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 41e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman struct Shared { 42e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // needs to be part of a union so don't define constructor or destructor 43e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 44e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman friend class Mutator; 45e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman friend class Observer; 46e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 47e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatramanprivate: 48e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman void init() { mAck = 0; mSequence = 0; } 49e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 50e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman volatile int32_t mAck; 51e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman volatile int32_t mSequence; 52e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman T mValue; 53e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman }; 54e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 55e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman class Mutator { 56e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman public: 57e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Mutator(Shared *shared) 58e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman : mSequence(0), mShared(shared) 59e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 60e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // exactly one of Mutator and Observer must initialize, currently it is Observer 61e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // shared->init(); 62e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 63e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 64e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // push new value onto state queue, overwriting previous value; 65e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // returns a sequence number which can be used with ack() 66e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t push(const T& value) 67e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 68e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Shared *shared = mShared; 69e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t sequence = mSequence; 70e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman sequence++; 71e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman android_atomic_acquire_store(sequence, &shared->mSequence); 72e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman shared->mValue = value; 73e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman sequence++; 74e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman android_atomic_release_store(sequence, &shared->mSequence); 75e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman mSequence = sequence; 76e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // consider signalling a futex here, if we know that observer is waiting 77e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return sequence; 78e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 79e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 80e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // returns the status of the last state push. This may be a stale value. 81e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // 82e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // SSQ_PENDING, or 0, means it has not been observed 83e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // SSQ_READ means it has been read 84e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // SSQ_DONE means it has been acted upon, after Observer::done() is called 85e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman enum SSQ_STATUS ack() const 86e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 87e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // in the case of SSQ_DONE, prevent any subtle data-races of subsequent reads 88e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // being performed (out-of-order) before the ack read, should the caller be 89e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // depending on sequentiality of reads. 90e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman const int32_t ack = android_atomic_acquire_load(&mShared->mAck); 91e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return ack - mSequence & ~1 ? SSQ_PENDING /* seq differ */ : 92e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman ack & 1 ? SSQ_DONE : SSQ_READ; 93e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 94e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 95e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // return true if a push with specified sequence number or later has been observed 96e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman bool ack(int32_t sequence) const 97e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 98e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // this relies on 2's complement rollover to detect an ancient sequence number 99e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return mShared->mAck - sequence >= 0; 100e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 101e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 102e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman private: 103e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t mSequence; 104e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Shared * const mShared; 105e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman }; 106e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 107e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman class Observer { 108e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman public: 109e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Observer(Shared *shared) 110e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman : mSequence(0), mSeed(1), mShared(shared) 111e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 112e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // exactly one of Mutator and Observer must initialize, currently it is Observer 113e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman shared->init(); 114e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 115e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 116e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // return true if value has changed 117e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman bool poll(T& value) 118e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 119e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Shared *shared = mShared; 120e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t before = shared->mSequence; 121e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman if (before == mSequence) { 122e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return false; 123e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 124e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman for (int tries = 0; ; ) { 125e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman const int MAX_TRIES = 5; 126e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman if (before & 1) { 127e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman if (++tries >= MAX_TRIES) { 128e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return false; 129e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 130e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman before = shared->mSequence; 131e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } else { 132e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman android_memory_barrier(); 133e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman T temp = shared->mValue; 134e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t after = android_atomic_release_load(&shared->mSequence); 135e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman if (after == before) { 136e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman value = temp; 137e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman shared->mAck = before; 138e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman mSequence = before; // mSequence is even after poll success 139e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return true; 140e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 141e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman if (++tries >= MAX_TRIES) { 142e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman return false; 143e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 144e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman before = after; 145e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 146e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 147e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 148e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 149e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // (optional) used to indicate to the Mutator that the state that has been polled 150e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // has also been acted upon. 151e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman void done() 152e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman { 153e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman const int32_t ack = mShared->mAck + 1; 154e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman // ensure all previous writes have been performed. 155e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman android_atomic_release_store(ack, &mShared->mAck); // mSequence is odd after "done" 156e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman } 157e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 158e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman private: 159e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int32_t mSequence; 160e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman int mSeed; // for PRNG 161e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman Shared * const mShared; 162e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman }; 163e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 164e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#if 0 165e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman SingleStateQueue(void /*Shared*/ *shared); 166e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman /*virtual*/ ~SingleStateQueue() { } 167e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 168e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman static size_t size() { return sizeof(Shared); } 169e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#endif 170e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 171e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman}; 172e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 173e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman} // namespace android 174e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman 175e2b43843fd12783188edd2c54188ea8d26864788Vijay Venkatraman#endif // SINGLE_STATE_QUEUE_H 176