1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *
16 */
17
18#define LOG_TAG "AAudio"
19//#define LOG_NDEBUG 0
20#include <utils/Log.h>
21
22#include <assert.h>
23#include <new>
24#include <stdint.h>
25#include <utils/Mutex.h>
26
27#include <aaudio/AAudio.h>
28#include "HandleTracker.h"
29
30using android::Mutex;
31
32// Handle format is: tgggiiii
33// where each letter is 4 bits, t=type, g=generation, i=index
34
35#define TYPE_SIZE           4
36#define GENERATION_SIZE    12
37#define INDEX_SIZE         16
38
39#define GENERATION_INVALID  0
40#define GENERATION_SHIFT    INDEX_SIZE
41
42#define TYPE_MASK           ((1 << TYPE_SIZE) - 1)
43#define GENERATION_MASK     ((1 << GENERATION_SIZE) - 1)
44#define INDEX_MASK          ((1 << INDEX_SIZE) - 1)
45
46#define SLOT_UNAVAILABLE    (-1)
47
48// Error if handle is negative so type is limited to bottom half.
49#define HANDLE_INVALID_TYPE TYPE_MASK
50
51static_assert(HANDLE_TRACKER_MAX_TYPES == (1 << (TYPE_SIZE - 1)),
52    "Mismatch between header and cpp.");
53static_assert(HANDLE_TRACKER_MAX_HANDLES == (1 << (INDEX_SIZE)),
54    "Mismatch between header and cpp.");
55
56HandleTracker::HandleTracker(uint32_t maxHandles)
57        : mMaxHandleCount(maxHandles)
58        , mHandleHeaders(nullptr)
59{
60    assert(maxHandles <= HANDLE_TRACKER_MAX_HANDLES);
61    // Allocate arrays to hold addresses and validation info.
62    mHandleAddresses = (handle_tracker_address_t *)
63            new(std::nothrow) handle_tracker_address_t[maxHandles];
64    if (mHandleAddresses != nullptr) {
65        mHandleHeaders = new(std::nothrow) handle_tracker_header_t[maxHandles];
66
67        if (mHandleHeaders != nullptr) {
68            handle_tracker_header_t initialHeader = buildHeader(0, 1);
69            // Initialize linked list of free nodes. nullptr terminated.
70            for (uint32_t i = 0; i < (maxHandles - 1); i++) {
71                mHandleAddresses[i] = &mHandleAddresses[i + 1]; // point to next node
72                mHandleHeaders[i] = initialHeader;
73            }
74            mNextFreeAddress = &mHandleAddresses[0];
75            mHandleAddresses[maxHandles - 1] = nullptr;
76            mHandleHeaders[maxHandles - 1] = 0;
77        } else {
78            delete[] mHandleAddresses; // so the class appears uninitialized
79            mHandleAddresses = nullptr;
80        }
81    }
82}
83
84HandleTracker::~HandleTracker()
85{
86    Mutex::Autolock _l(mLock);
87    delete[] mHandleAddresses;
88    delete[] mHandleHeaders;
89    mHandleAddresses = nullptr;
90}
91
92bool HandleTracker::isInitialized() const {
93    return mHandleAddresses != nullptr;
94}
95
96handle_tracker_slot_t HandleTracker::allocateSlot_l() {
97    void **allocated = mNextFreeAddress;
98    if (allocated == nullptr) {
99        return SLOT_UNAVAILABLE;
100    }
101    // Remove this slot from the head of the linked list.
102    mNextFreeAddress = (void **) *allocated;
103    return (allocated - mHandleAddresses);
104}
105
106handle_tracker_generation_t HandleTracker::nextGeneration_l(handle_tracker_slot_t index) {
107    handle_tracker_generation_t generation = (mHandleHeaders[index] + 1) & GENERATION_MASK;
108    // Avoid generation zero so that 0x0 is not a valid handle.
109    if (generation == GENERATION_INVALID) {
110        generation++;
111    }
112    return generation;
113}
114
115aaudio_handle_t HandleTracker::put(handle_tracker_type_t type, void *address)
116{
117    if (type < 0 || type >= HANDLE_TRACKER_MAX_TYPES) {
118        return static_cast<aaudio_handle_t>(AAUDIO_ERROR_OUT_OF_RANGE);
119    }
120    if (!isInitialized()) {
121        return static_cast<aaudio_handle_t>(AAUDIO_ERROR_NO_MEMORY);
122    }
123
124    Mutex::Autolock _l(mLock);
125
126    // Find an empty slot.
127    handle_tracker_slot_t index = allocateSlot_l();
128    if (index == SLOT_UNAVAILABLE) {
129        ALOGE("HandleTracker::put() no room for more handles");
130        return static_cast<aaudio_handle_t>(AAUDIO_ERROR_NO_FREE_HANDLES);
131    }
132
133    // Cycle the generation counter so stale handles can be detected.
134    handle_tracker_generation_t generation = nextGeneration_l(index); // reads header table
135    handle_tracker_header_t inputHeader = buildHeader(type, generation);
136
137    // These two writes may need to be observed by other threads or cores during get().
138    mHandleHeaders[index] = inputHeader;
139    mHandleAddresses[index] = address;
140    // TODO use store release to enforce memory order with get()
141
142    // Generate a handle.
143    aaudio_handle_t handle = buildHandle(inputHeader, index);
144
145    ALOGV("HandleTracker::put(%p) returns 0x%08x", address, handle);
146    return handle;
147}
148
149handle_tracker_slot_t HandleTracker::handleToIndex(handle_tracker_type_t type,
150                                                   aaudio_handle_t handle) const
151{
152    // Validate the handle.
153    handle_tracker_slot_t index = extractIndex(handle);
154    if (index >= mMaxHandleCount) {
155        ALOGE("HandleTracker::handleToIndex() invalid handle = 0x%08X", handle);
156        return static_cast<aaudio_handle_t>(AAUDIO_ERROR_INVALID_HANDLE);
157    }
158    handle_tracker_generation_t handleGeneration = extractGeneration(handle);
159    handle_tracker_header_t inputHeader = buildHeader(type, handleGeneration);
160    // We do not need to synchronize this access to mHandleHeaders because it is constant for
161    // the lifetime of the handle.
162    if (inputHeader != mHandleHeaders[index]) {
163        ALOGE("HandleTracker::handleToIndex() inputHeader = 0x%08x != mHandleHeaders[%d] = 0x%08x",
164             inputHeader, index, mHandleHeaders[index]);
165        return static_cast<aaudio_handle_t>(AAUDIO_ERROR_INVALID_HANDLE);
166    }
167    return index;
168}
169
170handle_tracker_address_t HandleTracker::get(handle_tracker_type_t type, aaudio_handle_t handle) const
171{
172    if (!isInitialized()) {
173        return nullptr;
174    }
175    handle_tracker_slot_t index = handleToIndex(type, handle);
176    if (index >= 0) {
177        // We do not need to synchronize this access to mHandleHeaders because this slot
178        // is allocated and, therefore, not part of the linked list of free slots.
179        return mHandleAddresses[index];
180    } else {
181        return nullptr;
182    }
183}
184
185handle_tracker_address_t HandleTracker::remove(handle_tracker_type_t type, aaudio_handle_t handle) {
186    if (!isInitialized()) {
187        return nullptr;
188    }
189
190    Mutex::Autolock _l(mLock);
191
192    handle_tracker_slot_t index = handleToIndex(type,handle);
193    if (index >= 0) {
194        handle_tracker_address_t address = mHandleAddresses[index];
195
196        // Invalidate the header type but preserve the generation count.
197        handle_tracker_generation_t generation = mHandleHeaders[index] & GENERATION_MASK;
198        handle_tracker_header_t inputHeader = buildHeader(
199                (handle_tracker_type_t) HANDLE_INVALID_TYPE, generation);
200        mHandleHeaders[index] = inputHeader;
201
202        // Add this slot to the head of the linked list.
203        mHandleAddresses[index] = mNextFreeAddress;
204        mNextFreeAddress = (handle_tracker_address_t *) &mHandleAddresses[index];
205        return address;
206    } else {
207        return nullptr;
208    }
209}
210
211aaudio_handle_t HandleTracker::buildHandle(handle_tracker_header_t typeGeneration,
212                                         handle_tracker_slot_t index) {
213    return (aaudio_handle_t)((typeGeneration << GENERATION_SHIFT) | (index & INDEX_MASK));
214}
215
216handle_tracker_header_t HandleTracker::buildHeader(handle_tracker_type_t type,
217                                    handle_tracker_generation_t generation)
218{
219    return (handle_tracker_header_t) (((type & TYPE_MASK) << GENERATION_SIZE)
220        | (generation & GENERATION_MASK));
221}
222
223handle_tracker_slot_t HandleTracker::extractIndex(aaudio_handle_t handle)
224{
225    return handle & INDEX_MASK;
226}
227
228handle_tracker_generation_t HandleTracker::extractGeneration(aaudio_handle_t handle)
229{
230    return (handle >> GENERATION_SHIFT) & GENERATION_MASK;
231}
232