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