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{ 318b5f642eb2364ea7fe46a5b3af51b48b58f12183Elliott Hughes dprintf(fd, "State queue observer: stateChanges=%u\n", mStateChanges); 32399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten} 33399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 34399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kastenvoid StateQueueMutatorDump::dump(int fd) 35399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten{ 368b5f642eb2364ea7fe46a5b3af51b48b58f12183Elliott Hughes dprintf(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() : 44f39b560952d3706a7ff47ef0d82c1a836daeea42Hans Boehm 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{ 5136802bd18b7b4e8c87fa019c7e3068bee330d174Dan Albert atomic_init(&mNext, static_cast<uintptr_t>(0)); 52dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 53dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 54dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> StateQueue<T>::~StateQueue() 55dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 56dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 57dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 58dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Observer APIs 59dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 60dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> const T* StateQueue<T>::poll() 61dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 62f39b560952d3706a7ff47ef0d82c1a836daeea42Hans Boehm const T *next = (const T *) atomic_load_explicit(&mNext, memory_order_acquire); 63f39b560952d3706a7ff47ef0d82c1a836daeea42Hans Boehm 64dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (next != mCurrent) { 65dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mAck = next; // no additional barrier needed 66dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mCurrent = next; 67399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 68399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mObserverDump->mStateChanges++; 69399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 70dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 71dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return next; 72dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 73dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 74dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// Mutator APIs 75dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 76dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> T* StateQueue<T>::begin() 77dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 78dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "begin() called when in a mutation"); 79dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = true; 80dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return mMutating; 81dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 82dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 83dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> void StateQueue<T>::end(bool didModify) 84dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 85dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mInMutation, "end() called when not in a mutation"); 86dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(mIsInitialized || didModify, "first end() must modify for initialization"); 87dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (didModify) { 88dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = true; 89dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsInitialized = true; 90dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 91dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mInMutation = false; 92dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 93dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 94dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kastentemplate<typename T> bool StateQueue<T>::push(StateQueue<T>::block_t block) 95dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten{ 96dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#define PUSH_BLOCK_ACK_NS 3000000L // 3 ms: time between checks for ack in push() 97dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // FIXME should be configurable 98dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten static const struct timespec req = {0, PUSH_BLOCK_ACK_NS}; 99dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 100dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten ALOG_ASSERT(!mInMutation, "push() called when in a mutation"); 101dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 102399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 103399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 104399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushAck++; 105399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 106399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 107399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 108dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mIsDirty) { 109dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 110399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 111399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mPushDirty++; 112399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 113399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten 114dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // wait for prior push to be acknowledged 115dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 116399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 117399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 118399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 119dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 120dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 121dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 122dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // unnecessary as we're about to rewrite 123dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten //mExpecting = NULL; 124dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 125dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 126dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_NEVER) { 127dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return false; 128dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 129399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 130399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 131399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 132399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 133399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 134399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 135dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 136dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 137399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 138399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 139399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 140399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 141399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 142dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 143dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 144dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // publish 145f39b560952d3706a7ff47ef0d82c1a836daeea42Hans Boehm atomic_store_explicit(&mNext, (uintptr_t)mMutating, memory_order_release); 146dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = mMutating; 147dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 148dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // copy with circular wraparound 149dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (++mMutating >= &mStates[kN]) { 150dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mMutating = &mStates[0]; 151dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 152dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten *mMutating = *mExpecting; 153dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mIsDirty = false; 154dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 155dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 156dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 157dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten // optionally wait for this push or a prior push to be acknowledged 158dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (block == BLOCK_UNTIL_ACKED) { 159dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (mExpecting != NULL) { 160399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 161399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten unsigned count = 0; 162399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 163dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten for (;;) { 164dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten const T *ack = (const T *) mAck; // no additional barrier needed 165dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten if (ack == mExpecting) { 166dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten mExpecting = NULL; 167dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten break; 168dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 169399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 170399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count == 1) { 171399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 172399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 173399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten ++count; 174399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 175dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten nanosleep(&req, NULL); 176dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 177399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#ifdef STATE_QUEUE_DUMP 178399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten if (count > 1) { 179399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten mMutatorDump->mBlockedSequence++; 180399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten } 181399930859a75d806ce0ef124ac22025ae4ef0549Glenn Kasten#endif 182dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 183dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten } 184dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 185dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten return true; 186dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} 187dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 188dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten} // namespace android 189dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten 190dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten// hack for gcc 191dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#ifdef STATE_QUEUE_INSTANTIATIONS 192dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#include STATE_QUEUE_INSTANTIATIONS 193dc998c809e084b617990b281e2ed5271830cc2e0Glenn Kasten#endif 194