15c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten/* 25c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * Copyright (C) 2012 The Android Open Source Project 35c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * 45c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * Licensed under the Apache License, Version 2.0 (the "License"); 55c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * you may not use this file except in compliance with the License. 65c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * You may obtain a copy of the License at 75c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * 85c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * http://www.apache.org/licenses/LICENSE-2.0 95c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * 105c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * Unless required by applicable law or agreed to in writing, software 115c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * distributed under the License is distributed on an "AS IS" BASIS, 125c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 135c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * See the License for the specific language governing permissions and 145c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten * limitations under the License. 155c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten */ 165c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 175c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#ifndef SINGLE_STATE_QUEUE_H 185c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#define SINGLE_STATE_QUEUE_H 195c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 205c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten// Non-blocking single element state queue, or 215c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten// Non-blocking single-reader / single-writer multi-word atomic load / store 225c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 235c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#include <stdint.h> 249b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung#include <cutils/atomic.h> 255c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 265c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kastennamespace android { 275c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 285c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kastentemplate<typename T> class SingleStateQueue { 295c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 305c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kastenpublic: 315c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 325c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten class Mutator; 335c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten class Observer; 345c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 35774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung enum SSQ_STATUS { 36774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung SSQ_PENDING, /* = 0 */ 37774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung SSQ_READ, 38774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung SSQ_DONE, 39774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung }; 40774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung 415c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten struct Shared { 425c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten // needs to be part of a union so don't define constructor or destructor 435c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 445c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten friend class Mutator; 455c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten friend class Observer; 465c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 475c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kastenprivate: 485c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten void init() { mAck = 0; mSequence = 0; } 495c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 505c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten volatile int32_t mAck; 515c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten volatile int32_t mSequence; 525c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten T mValue; 535c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten }; 545c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 555c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten class Mutator { 565c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten public: 579b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung Mutator(Shared *shared) 589b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung : mSequence(0), mShared(shared) 599b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 609b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung // exactly one of Mutator and Observer must initialize, currently it is Observer 619b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung // shared->init(); 629b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 635c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 645c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten // push new value onto state queue, overwriting previous value; 655c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten // returns a sequence number which can be used with ack() 669b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung int32_t push(const T& value) 679b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 689b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung Shared *shared = mShared; 699b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung int32_t sequence = mSequence; 709b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung sequence++; 719b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung android_atomic_acquire_store(sequence, &shared->mSequence); 729b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung shared->mValue = value; 739b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung sequence++; 749b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung android_atomic_release_store(sequence, &shared->mSequence); 759b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung mSequence = sequence; 769b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung // consider signalling a futex here, if we know that observer is waiting 779b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return sequence; 789b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 795c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 80774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // returns the status of the last state push. This may be a stale value. 81774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // 82774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // SSQ_PENDING, or 0, means it has not been observed 83774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // SSQ_READ means it has been read 84774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // SSQ_DONE means it has been acted upon, after Observer::done() is called 85774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung enum SSQ_STATUS ack() const 869b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 87774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // in the case of SSQ_DONE, prevent any subtle data-races of subsequent reads 88774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // being performed (out-of-order) before the ack read, should the caller be 89774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // depending on sequentiality of reads. 90774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung const int32_t ack = android_atomic_acquire_load(&mShared->mAck); 91774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung return ack - mSequence & ~1 ? SSQ_PENDING /* seq differ */ : 92774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung ack & 1 ? SSQ_DONE : SSQ_READ; 939b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 945c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 955c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten // return true if a push with specified sequence number or later has been observed 969b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung bool ack(int32_t sequence) const 979b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 989b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung // this relies on 2's complement rollover to detect an ancient sequence number 999b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return mShared->mAck - sequence >= 0; 1009b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1015c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1025c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten private: 1035c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten int32_t mSequence; 1045c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten Shared * const mShared; 1055c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten }; 1065c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1075c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten class Observer { 1085c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten public: 1099b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung Observer(Shared *shared) 1109b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung : mSequence(0), mSeed(1), mShared(shared) 1119b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 1129b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung // exactly one of Mutator and Observer must initialize, currently it is Observer 1139b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung shared->init(); 1149b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1155c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1165c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten // return true if value has changed 1179b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung bool poll(T& value) 1189b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung { 1199b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung Shared *shared = mShared; 1209b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung int32_t before = shared->mSequence; 1219b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung if (before == mSequence) { 1229b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return false; 1239b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1249b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung for (int tries = 0; ; ) { 1259b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung const int MAX_TRIES = 5; 1269b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung if (before & 1) { 1279b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung if (++tries >= MAX_TRIES) { 1289b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return false; 1299b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1309b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung before = shared->mSequence; 1319b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } else { 1329b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung android_memory_barrier(); 1339b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung T temp = shared->mValue; 1349b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung int32_t after = android_atomic_release_load(&shared->mSequence); 1359b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung if (after == before) { 1369b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung value = temp; 1379b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung shared->mAck = before; 138774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung mSequence = before; // mSequence is even after poll success 1399b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return true; 1409b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1419b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung if (++tries >= MAX_TRIES) { 1429b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung return false; 1439b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1449b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung before = after; 1459b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1469b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1479b82924cbd203f1678c2f78aa73b15909efa3e81Andy Hung } 1485c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 149774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // (optional) used to indicate to the Mutator that the state that has been polled 150774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // has also been acted upon. 151774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung void done() 152774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung { 153774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung const int32_t ack = mShared->mAck + 1; 154774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung // ensure all previous writes have been performed. 155774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung android_atomic_release_store(ack, &mShared->mAck); // mSequence is odd after "done" 156774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung } 157774acea9bdaa1a8b2fac89a5bba9db4124f20192Andy Hung 1585c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten private: 1595c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten int32_t mSequence; 1605c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten int mSeed; // for PRNG 1615c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten Shared * const mShared; 1625c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten }; 1635c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1645c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#if 0 1655c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten SingleStateQueue(void /*Shared*/ *shared); 1665c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten /*virtual*/ ~SingleStateQueue() { } 1675c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1685c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten static size_t size() { return sizeof(Shared); } 1695c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#endif 1705c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1715c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten}; 1725c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1735c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten} // namespace android 1745c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten 1755c4cc0d99d3b1cb35c5d7c237272ee53142745fbGlenn Kasten#endif // SINGLE_STATE_QUEUE_H 176