StateQueue.cpp revision 399930859a75d806ce0ef124ac22025ae4ef0549
1dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten/* 2dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * Copyright (C) 2012 The Android Open Source Project 3dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * 4dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * Licensed under the Apache License, Version 2.0 (the "License"); 5dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * you may not use this file except in compliance with the License. 6dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * You may obtain a copy of the License at 7dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * 8dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * http://www.apache.org/licenses/LICENSE-2.0 9dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * 10dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * Unless required by applicable law or agreed to in writing, software 11dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * distributed under the License is distributed on an "AS IS" BASIS, 12dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * See the License for the specific language governing permissions and 14dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten * limitations under the License. 15dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten */ 16dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 17dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#define LOG_TAG "StateQueue" 18dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten//#define LOG_NDEBUG 0 19dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 20dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <time.h> 21dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <cutils/atomic.h> 22dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <utils/Log.h> 23dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include "StateQueue.h" 24dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 25dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastennamespace android { 26dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 27399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 28399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kastenvoid StateQueueObserverDump::dump(int fd) 29399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten{ 30399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten fdprintf(fd, "State queue observer: stateChanges=%u\n", mStateChanges); 31399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten} 32399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 33399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kastenvoid StateQueueMutatorDump::dump(int fd) 34399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten{ 35399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten fdprintf(fd, "State queue mutator: pushDirty=%u pushAck=%u blockedSequence=%u\n", 36399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mPushDirty, mPushAck, mBlockedSequence); 37399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten} 38399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 39399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 40dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Constructor and destructor 41dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 42dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> StateQueue<T>::StateQueue() : 43dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mNext(NULL), mAck(NULL), mCurrent(NULL), 44dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mMutating(&mStates[0]), mExpecting(NULL), 45dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation(false), mIsDirty(false), mIsInitialized(false) 46399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 47399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten , mObserverDump(&mObserverDummyDump), mMutatorDump(&mMutatorDummyDump) 48399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 49dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 50dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 51dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 52dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> StateQueue<T>::~StateQueue() 53dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 54dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 55dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 56dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Observer APIs 57dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 58dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> const T* StateQueue<T>::poll() 59dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 60dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *next = (const T *) android_atomic_acquire_load((volatile int32_t *) &mNext); 61dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (next != mCurrent) { 62dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mAck = next; // no additional barrier needed 63dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mCurrent = next; 64399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 65399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mObserverDump->mStateChanges++; 66399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 67dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 68dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return next; 69dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 70dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 71dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Mutator APIs 72dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 73dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> T* StateQueue<T>::begin() 74dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 75dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "begin() called when in a mutation"); 76dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = true; 77dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return mMutating; 78dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 79dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 80dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> void StateQueue<T>::end(bool didModify) 81dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 82dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mInMutation, "end() called when not in a mutation"); 83dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mIsInitialized || didModify, "first end() must modify for initialization"); 84dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (didModify) { 85dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = true; 86dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsInitialized = true; 87dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 88dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = false; 89dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 90dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 91dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> bool StateQueue<T>::push(StateQueue<T>::block_t block) 92dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 93dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#define PUSH_BLOCK_ACK_NS 3000000L // 3 ms: time between checks for ack in push() 94dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // FIXME should be configurable 95dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten static const struct timespec req = {0, PUSH_BLOCK_ACK_NS}; 96dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 97dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "push() called when in a mutation"); 98dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 99399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 100399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 101399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushAck++; 102399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 103399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 104399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 105dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mIsDirty) { 106dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 107399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 108399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushDirty++; 109399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 110399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 111dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // wait for prior push to be acknowledged 112dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 113399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 114399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 115399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 116dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 117dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 118dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 119dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // unnecessary as we're about to rewrite 120dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten //mExpecting = NULL; 121dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 122dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 123dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_NEVER) { 124dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return false; 125dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 126399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 127399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 128399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 129399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 130399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 131399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 132dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 133dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 134399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 135399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 136399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 137399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 138399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 139dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 140dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 141dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // publish 142dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten android_atomic_release_store((int32_t) mMutating, (volatile int32_t *) &mNext); 143dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = mMutating; 144dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 145dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // copy with circular wraparound 146dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (++mMutating >= &mStates[kN]) { 147dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mMutating = &mStates[0]; 148dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 149dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten *mMutating = *mExpecting; 150dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = false; 151dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 152dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 153dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 154dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // optionally wait for this push or a prior push to be acknowledged 155dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 156dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 157399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 158399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 159399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 160dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 161dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 162dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 163dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = NULL; 164dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 165dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 166399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 167399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 168399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 169399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 170399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 171399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 172dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 173dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 174399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 175399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 176399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 177399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 178399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 179dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 180dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 181dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 182dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return true; 183dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 184dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 185dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} // namespace android 186dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 187dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// hack for gcc 188dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#ifdef STATE_QUEUE_INSTANTIATIONS 189dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include STATE_QUEUE_INSTANTIATIONS 190dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#endif 191