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 20153b9fe667e6e78e0218ff0159353097428c7657Glenn Kasten#include "Configuration.h" 21dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <time.h> 22dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <cutils/atomic.h> 23dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include <utils/Log.h> 24dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include "StateQueue.h" 25dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 26dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastennamespace android { 27dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 28399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 29399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kastenvoid StateQueueObserverDump::dump(int fd) 30399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten{ 31399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten fdprintf(fd, "State queue observer: stateChanges=%u\n", mStateChanges); 32399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten} 33399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 34399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kastenvoid StateQueueMutatorDump::dump(int fd) 35399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten{ 36399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten fdprintf(fd, "State queue mutator: pushDirty=%u pushAck=%u blockedSequence=%u\n", 37399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mPushDirty, mPushAck, mBlockedSequence); 38399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten} 39399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 40399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 41dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Constructor and destructor 42dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 43dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> StateQueue<T>::StateQueue() : 44dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mNext(NULL), mAck(NULL), mCurrent(NULL), 45dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mMutating(&mStates[0]), mExpecting(NULL), 46dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation(false), mIsDirty(false), mIsInitialized(false) 47399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 48399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten , mObserverDump(&mObserverDummyDump), mMutatorDump(&mMutatorDummyDump) 49399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 50dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 51dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 52dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 53dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> StateQueue<T>::~StateQueue() 54dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 55dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 56dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 57dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Observer APIs 58dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 59dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> const T* StateQueue<T>::poll() 60dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 61dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *next = (const T *) android_atomic_acquire_load((volatile int32_t *) &mNext); 62dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (next != mCurrent) { 63dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mAck = next; // no additional barrier needed 64dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mCurrent = next; 65399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 66399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mObserverDump->mStateChanges++; 67399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 68dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 69dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return next; 70dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 71dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 72dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Mutator APIs 73dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 74dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> T* StateQueue<T>::begin() 75dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 76dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "begin() called when in a mutation"); 77dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = true; 78dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return mMutating; 79dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 80dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 81dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> void StateQueue<T>::end(bool didModify) 82dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 83dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mInMutation, "end() called when not in a mutation"); 84dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mIsInitialized || didModify, "first end() must modify for initialization"); 85dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (didModify) { 86dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = true; 87dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsInitialized = true; 88dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 89dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = false; 90dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 91dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 92dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> bool StateQueue<T>::push(StateQueue<T>::block_t block) 93dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 94dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#define PUSH_BLOCK_ACK_NS 3000000L // 3 ms: time between checks for ack in push() 95dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // FIXME should be configurable 96dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten static const struct timespec req = {0, PUSH_BLOCK_ACK_NS}; 97dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 98dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "push() called when in a mutation"); 99dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 100399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 101399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 102399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushAck++; 103399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 104399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 105399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 106dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mIsDirty) { 107dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 108399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 109399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushDirty++; 110399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 111399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 112dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // wait for prior push to be acknowledged 113dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 114399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 115399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 116399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 117dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 118dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 119dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 120dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // unnecessary as we're about to rewrite 121dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten //mExpecting = NULL; 122dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 123dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 124dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_NEVER) { 125dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return false; 126dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 127399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 128399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 129399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 130399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 131399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 132399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 133dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 134dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 135399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 136399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 137399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 138399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 139399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 140dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 141dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 142dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // publish 143dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten android_atomic_release_store((int32_t) mMutating, (volatile int32_t *) &mNext); 144dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = mMutating; 145dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 146dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // copy with circular wraparound 147dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (++mMutating >= &mStates[kN]) { 148dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mMutating = &mStates[0]; 149dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 150dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten *mMutating = *mExpecting; 151dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = false; 152dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 153dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 154dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 155dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // optionally wait for this push or a prior push to be acknowledged 156dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 157dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 158399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 159399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 160399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 161dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 162dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 163dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 164dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = NULL; 165dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 166dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 167399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 168399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 169399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 170399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 171399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 172399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 173dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 174dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 175399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 176399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 177399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 178399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 179399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 180dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 181dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 182dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 183dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return true; 184dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 185dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 186dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} // namespace android 187dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 188dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// hack for gcc 189dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#ifdef STATE_QUEUE_INSTANTIATIONS 190dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include STATE_QUEUE_INSTANTIATIONS 191dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#endif 192