1 /*
2 * Copyright (C) 2018 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 #include <iostream>
18
19 #include <gtest/gtest.h>
20 #include <stdlib.h>
21
22 #include "fifo/FifoBuffer.h"
23 #include "fifo/FifoController.h"
24
25 using android::fifo_frames_t;
26 using android::fifo_counter_t;
27 using android::FifoController;
28 using android::FifoBuffer;
29 using android::WrappingBuffer;
30
TEST(test_fifo_controller,fifo_indices)31 TEST(test_fifo_controller, fifo_indices) {
32 // Values are arbitrary primes designed to trigger edge cases.
33 constexpr int capacity = 83;
34 constexpr int threshold = 47;
35 FifoController fifoController(capacity, threshold);
36 ASSERT_EQ(capacity, fifoController.getCapacity());
37 ASSERT_EQ(threshold, fifoController.getThreshold());
38
39 ASSERT_EQ(0, fifoController.getReadCounter());
40 ASSERT_EQ(0, fifoController.getWriteCounter());
41 ASSERT_EQ(0, fifoController.getFullFramesAvailable());
42 ASSERT_EQ(threshold, fifoController.getEmptyFramesAvailable());
43
44 // Pretend to write some data.
45 constexpr int advance1 = 23;
46 fifoController.advanceWriteIndex(advance1);
47 int advanced = advance1;
48 ASSERT_EQ(0, fifoController.getReadCounter());
49 ASSERT_EQ(0, fifoController.getReadIndex());
50 ASSERT_EQ(advanced, fifoController.getWriteCounter());
51 ASSERT_EQ(advanced, fifoController.getWriteIndex());
52 ASSERT_EQ(advanced, fifoController.getFullFramesAvailable());
53 ASSERT_EQ(threshold - advanced, fifoController.getEmptyFramesAvailable());
54
55 // Pretend to read the data.
56 fifoController.advanceReadIndex(advance1);
57 ASSERT_EQ(advanced, fifoController.getReadCounter());
58 ASSERT_EQ(advanced, fifoController.getReadIndex());
59 ASSERT_EQ(advanced, fifoController.getWriteCounter());
60 ASSERT_EQ(advanced, fifoController.getWriteIndex());
61 ASSERT_EQ(0, fifoController.getFullFramesAvailable());
62 ASSERT_EQ(threshold, fifoController.getEmptyFramesAvailable());
63
64 // Write past end of buffer.
65 constexpr int advance2 = 13 + capacity - advance1;
66 fifoController.advanceWriteIndex(advance2);
67 advanced += advance2;
68 ASSERT_EQ(advance1, fifoController.getReadCounter());
69 ASSERT_EQ(advance1, fifoController.getReadIndex());
70 ASSERT_EQ(advanced, fifoController.getWriteCounter());
71 ASSERT_EQ(advanced - capacity, fifoController.getWriteIndex());
72 ASSERT_EQ(advance2, fifoController.getFullFramesAvailable());
73 ASSERT_EQ(threshold - advance2, fifoController.getEmptyFramesAvailable());
74 }
75
TEST(test_fifo_controller,fifo_wrap_around_zero)76 TEST(test_fifo_controller, fifo_wrap_around_zero) {
77 constexpr int capacity = 7; // arbitrary prime
78 constexpr int threshold = capacity;
79 FifoController fifoController(capacity, threshold);
80 ASSERT_EQ(capacity, fifoController.getCapacity());
81 ASSERT_EQ(threshold, fifoController.getThreshold());
82
83 fifoController.setReadCounter(-10); // a bit less than negative capacity
84 for (int i = 0; i < 20; i++) {
85 EXPECT_EQ(i - 10, fifoController.getReadCounter());
86 EXPECT_GE(fifoController.getReadIndex(), 0);
87 EXPECT_LT(fifoController.getReadIndex(), capacity);
88 fifoController.advanceReadIndex(1);
89 }
90
91 fifoController.setWriteCounter(-10);
92 for (int i = 0; i < 20; i++) {
93 EXPECT_EQ(i - 10, fifoController.getWriteCounter());
94 EXPECT_GE(fifoController.getWriteIndex(), 0);
95 EXPECT_LT(fifoController.getWriteIndex(), capacity);
96 fifoController.advanceWriteIndex(1);
97 }
98 }
99
100
101 // TODO consider using a template for other data types.
102
103 // Create a big array and then use a region in the middle for the unit tests.
104 // Then we can scan the rest of the array to see if it got clobbered.
105 static constexpr fifo_frames_t kBigArraySize = 1024;
106 static constexpr fifo_frames_t kFifoDataOffset = 128; // starting index of FIFO data
107 static constexpr int16_t kSafeDataValue = 0x7654; // original value of BigArray
108
109 class TestFifoBuffer {
110 public:
TestFifoBuffer(fifo_frames_t capacity,fifo_frames_t threshold=0)111 explicit TestFifoBuffer(fifo_frames_t capacity, fifo_frames_t threshold = 0)
112 : mFifoBuffer(sizeof(int16_t), capacity,
113 &mReadIndex,
114 &mWriteIndex,
115 &mVeryBigArray[kFifoDataOffset]) // address of start of FIFO data
116 {
117
118 // Assume a frame is one int16_t.
119 // For reading and writing.
120 if (threshold <= 0) {
121 threshold = capacity;
122 }
123 mFifoBuffer.setThreshold(threshold);
124 mThreshold = threshold;
125
126 for (fifo_frames_t i = 0; i < kBigArraySize; i++) {
127 mVeryBigArray[i] = kSafeDataValue;
128 }
129 }
130
checkMisc()131 void checkMisc() {
132 ASSERT_EQ((int32_t)(2 * sizeof(int16_t)), mFifoBuffer.convertFramesToBytes(2));
133 ASSERT_EQ(mThreshold, mFifoBuffer.getThreshold());
134 }
135
verifyAddressInRange(void * p,void * valid,size_t numBytes)136 void verifyAddressInRange(void *p, void *valid, size_t numBytes) {
137 uintptr_t p_int = (uintptr_t) p;
138 uintptr_t valid_int = (uintptr_t) valid;
139 EXPECT_GE(p_int, valid_int);
140 EXPECT_LT(p_int, (valid_int + numBytes));
141 }
142
verifyStorageIntegrity()143 void verifyStorageIntegrity() {
144 for (fifo_frames_t i = 0; i < kFifoDataOffset; i++) {
145 EXPECT_EQ(mVeryBigArray[i], kSafeDataValue);
146 }
147 fifo_frames_t firstFrameAfter = kFifoDataOffset + mFifoBuffer.getBufferCapacityInFrames();
148 for (fifo_frames_t i = firstFrameAfter; i < kBigArraySize; i++) {
149 EXPECT_EQ(mVeryBigArray[i], kSafeDataValue);
150 }
151 }
152
153 // Verify that the available frames in each part add up correctly.
verifyWrappingBuffer()154 void verifyWrappingBuffer() {
155 WrappingBuffer wrappingBuffer;
156
157
158 // Does the sum of the two parts match the available value returned?
159 // For EmptyRoom
160 fifo_frames_t framesAvailable =
161 mFifoBuffer.getEmptyFramesAvailable();
162 fifo_frames_t wrapAvailable = mFifoBuffer.getEmptyRoomAvailable(&wrappingBuffer);
163 EXPECT_EQ(framesAvailable, wrapAvailable);
164 fifo_frames_t bothAvailable = wrappingBuffer.numFrames[0] + wrappingBuffer.numFrames[1];
165 EXPECT_EQ(framesAvailable, bothAvailable);
166 // For FullData
167 framesAvailable =
168 mFifoBuffer.getFullFramesAvailable();
169 wrapAvailable = mFifoBuffer.getFullDataAvailable(&wrappingBuffer);
170 EXPECT_EQ(framesAvailable, wrapAvailable);
171 bothAvailable = wrappingBuffer.numFrames[0] + wrappingBuffer.numFrames[1];
172 EXPECT_EQ(framesAvailable, bothAvailable);
173
174 // Are frame counts in legal range?
175 fifo_frames_t capacity = mFifoBuffer.getBufferCapacityInFrames();
176 EXPECT_GE(wrappingBuffer.numFrames[0], 0);
177 EXPECT_LE(wrappingBuffer.numFrames[0], capacity);
178 EXPECT_GE(wrappingBuffer.numFrames[1], 0);
179 EXPECT_LE(wrappingBuffer.numFrames[1], capacity);
180
181 // Are addresses within the FIFO data area?
182 size_t validBytes = capacity * sizeof(int16_t);
183 if (wrappingBuffer.numFrames[0]) {
184 verifyAddressInRange(wrappingBuffer.data[0], mFifoStorage, validBytes);
185 uint8_t *last = ((uint8_t *)wrappingBuffer.data[0])
186 + mFifoBuffer.convertFramesToBytes(wrappingBuffer.numFrames[0]) - 1;
187 verifyAddressInRange(last, mFifoStorage, validBytes);
188 }
189 if (wrappingBuffer.numFrames[1]) {
190 verifyAddressInRange(wrappingBuffer.data[1], mFifoStorage, validBytes);
191 uint8_t *last = ((uint8_t *)wrappingBuffer.data[1])
192 + mFifoBuffer.convertFramesToBytes(wrappingBuffer.numFrames[1]) - 1;
193 verifyAddressInRange(last, mFifoStorage, validBytes);
194 }
195
196 }
197
198 // Write data but do not overflow.
writeMultipleDataFrames(fifo_frames_t numFrames)199 void writeMultipleDataFrames(fifo_frames_t numFrames) {
200 fifo_frames_t framesAvailable =
201 mFifoBuffer.getEmptyFramesAvailable();
202 fifo_frames_t framesToWrite = std::min(framesAvailable, numFrames);
203 for (int i = 0; i < framesToWrite; i++) {
204 mData[i] = mNextWriteIndex++;
205 }
206 fifo_frames_t actual = mFifoBuffer.write(mData, framesToWrite);
207 ASSERT_EQ(framesToWrite, actual);
208 }
209
210 // Read whatever data is available, Do not underflow.
verifyMultipleDataFrames(fifo_frames_t numFrames)211 void verifyMultipleDataFrames(fifo_frames_t numFrames) {
212 fifo_frames_t framesAvailable =
213 mFifoBuffer.getFullFramesAvailable();
214 fifo_frames_t framesToRead = std::min(framesAvailable, numFrames);
215 fifo_frames_t actual = mFifoBuffer.read(mData, framesToRead);
216 ASSERT_EQ(framesToRead, actual);
217 for (int i = 0; i < framesToRead; i++) {
218 ASSERT_EQ(mNextVerifyIndex++, mData[i]);
219 }
220 }
221
222 // Read specified number of frames
verifyRequestedData(fifo_frames_t numFrames)223 void verifyRequestedData(fifo_frames_t numFrames) {
224 fifo_frames_t framesAvailable =
225 mFifoBuffer.getFullFramesAvailable();
226 ASSERT_LE(numFrames, framesAvailable);
227 fifo_frames_t framesToRead = std::min(framesAvailable, numFrames);
228 fifo_frames_t actual = mFifoBuffer.read(mData, framesToRead);
229 ASSERT_EQ(actual, numFrames);
230 for (int i = 0; i < actual; i++) {
231 ASSERT_EQ(mNextVerifyIndex++, mData[i]);
232 }
233 }
234
235 // Wrap around the end of the buffer.
checkWrappingWriteRead()236 void checkWrappingWriteRead() {
237 constexpr int frames1 = 43;
238 constexpr int frames2 = 15;
239
240 writeMultipleDataFrames(frames1);
241 verifyWrappingBuffer();
242 verifyRequestedData(frames1);
243 verifyWrappingBuffer();
244
245 writeMultipleDataFrames(frames2);
246 verifyWrappingBuffer();
247 verifyRequestedData(frames2);
248 verifyWrappingBuffer();
249
250 verifyStorageIntegrity();
251 }
252
253 // Write and Read a specific amount of data.
checkWriteRead()254 void checkWriteRead() {
255 const fifo_frames_t capacity = mFifoBuffer.getBufferCapacityInFrames();
256 // Wrap around with the smaller region in the second half.
257 const int frames1 = capacity - 4;
258 const int frames2 = 7; // arbitrary, small
259 writeMultipleDataFrames(frames1);
260 verifyRequestedData(frames1);
261 writeMultipleDataFrames(frames2);
262 verifyRequestedData(frames2);
263
264 verifyStorageIntegrity();
265 }
266
267 // Write and Read a specific amount of data.
checkWriteReadSmallLarge()268 void checkWriteReadSmallLarge() {
269 const fifo_frames_t capacity = mFifoBuffer.getBufferCapacityInFrames();
270 // Wrap around with the larger region in the second half.
271 const int frames1 = capacity - 4;
272 const int frames2 = capacity - 9; // arbitrary, large
273 writeMultipleDataFrames(frames1);
274 verifyRequestedData(frames1);
275 writeMultipleDataFrames(frames2);
276 verifyRequestedData(frames2);
277
278 verifyStorageIntegrity();
279 }
280
281 // Randomly read or write up to the maximum amount of data.
checkRandomWriteRead()282 void checkRandomWriteRead() {
283 for (int i = 0; i < 20; i++) {
284 fifo_frames_t framesEmpty =
285 mFifoBuffer.getEmptyFramesAvailable();
286 fifo_frames_t numFrames = (fifo_frames_t)(drand48() * framesEmpty);
287 writeMultipleDataFrames(numFrames);
288
289 fifo_frames_t framesFull =
290 mFifoBuffer.getFullFramesAvailable();
291 numFrames = (fifo_frames_t)(drand48() * framesFull);
292 verifyMultipleDataFrames(numFrames);
293 }
294
295 verifyStorageIntegrity();
296 }
297
298 // Write and Read a specific amount of data.
checkNegativeCounters()299 void checkNegativeCounters() {
300 fifo_counter_t counter = -9876;
301 mFifoBuffer.setWriteCounter(counter);
302 mFifoBuffer.setReadCounter(counter);
303 checkWrappingWriteRead();
304 }
305
306 // Wrap over the boundary at 0x7FFFFFFFFFFFFFFF
307 // Note that the behavior of a signed overflow is technically undefined.
checkHalfWrap()308 void checkHalfWrap() {
309 fifo_counter_t counter = INT64_MAX - 10;
310 mFifoBuffer.setWriteCounter(counter);
311 mFifoBuffer.setReadCounter(counter);
312 ASSERT_GT(mFifoBuffer.getWriteCounter(), 0);
313 checkWrappingWriteRead();
314 ASSERT_LT(mFifoBuffer.getWriteCounter(), 0); // did we wrap past INT64_MAX?
315 }
316
317 // Wrap over the boundary at 0xFFFFFFFFFFFFFFFF
checkFullWrap()318 void checkFullWrap() {
319 fifo_counter_t counter = -10;
320 mFifoBuffer.setWriteCounter(counter);
321 mFifoBuffer.setReadCounter(counter);
322 ASSERT_LT(mFifoBuffer.getWriteCounter(), 0);
323 writeMultipleDataFrames(20);
324 ASSERT_GT(mFifoBuffer.getWriteCounter(), 0); // did we wrap past zero?
325 verifyStorageIntegrity();
326 }
327
328 FifoBuffer mFifoBuffer;
329 fifo_frames_t mNextWriteIndex = 0;
330 fifo_frames_t mNextVerifyIndex = 0;
331 fifo_frames_t mThreshold;
332
333 fifo_counter_t mReadIndex = 0;
334 fifo_counter_t mWriteIndex = 0;
335 int16_t mVeryBigArray[kBigArraySize]; // Use the middle of this array for the FIFO.
336 int16_t *mFifoStorage = &mVeryBigArray[kFifoDataOffset]; // Start here for storage.
337 int16_t mData[kBigArraySize]{};
338 };
339
TEST(test_fifo_buffer,fifo_write_read)340 TEST(test_fifo_buffer, fifo_write_read) {
341 constexpr int capacity = 51; // arbitrary
342 TestFifoBuffer tester(capacity);
343 tester.checkMisc();
344 tester.checkWriteRead();
345 }
346
TEST(test_fifo_buffer,fifo_wrapping_write_read)347 TEST(test_fifo_buffer, fifo_wrapping_write_read) {
348 constexpr int capacity = 59; // arbitrary, a little bigger this time
349 TestFifoBuffer tester(capacity);
350 tester.checkWrappingWriteRead();
351 }
352
TEST(test_fifo_buffer,fifo_read_write_small_large)353 TEST(test_fifo_buffer, fifo_read_write_small_large) {
354 constexpr int capacity = 51; // arbitrary
355 TestFifoBuffer tester(capacity);
356 tester.checkWriteReadSmallLarge();
357 }
358
TEST(test_fifo_buffer,fifo_random_read_write)359 TEST(test_fifo_buffer, fifo_random_read_write) {
360 constexpr int capacity = 51; // arbitrary
361 TestFifoBuffer tester(capacity);
362 tester.checkRandomWriteRead();
363 }
364
TEST(test_fifo_buffer,fifo_random_threshold)365 TEST(test_fifo_buffer, fifo_random_threshold) {
366 constexpr int capacity = 67; // arbitrary
367 constexpr int threshold = 37; // arbitrary
368 TestFifoBuffer tester(capacity, threshold);
369 tester.checkRandomWriteRead();
370 }
371
TEST(test_fifo_buffer,fifo_negative_counters)372 TEST(test_fifo_buffer, fifo_negative_counters) {
373 constexpr int capacity = 49; // arbitrary
374 TestFifoBuffer tester(capacity);
375 tester.checkNegativeCounters();
376 }
377
TEST(test_fifo_buffer,fifo_half_wrap)378 TEST(test_fifo_buffer, fifo_half_wrap) {
379 constexpr int capacity = 57; // arbitrary
380 TestFifoBuffer tester(capacity);
381 tester.checkHalfWrap();
382 }
383
TEST(test_fifo_buffer,fifo_full_wrap)384 TEST(test_fifo_buffer, fifo_full_wrap) {
385 constexpr int capacity = 57; // arbitrary
386 TestFifoBuffer tester(capacity);
387 tester.checkFullWrap();
388 }
389