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