1// Copyright 2016 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <bitmap/raw-bitmap.h>
6#include <bitmap/storage.h>
7
8#include <fbl/algorithm.h>
9#include <fbl/alloc_checker.h>
10#include <unittest/unittest.h>
11
12namespace bitmap {
13namespace tests {
14
15template <typename RawBitmap> static bool InitializedEmpty(void) {
16    BEGIN_TEST;
17
18    RawBitmap bitmap;
19    EXPECT_EQ(bitmap.Reset(0), ZX_OK);
20    EXPECT_EQ(bitmap.size(), 0U, "get size");
21
22    EXPECT_TRUE(bitmap.GetOne(0), "get one bit");
23    EXPECT_EQ(bitmap.SetOne(0), ZX_ERR_INVALID_ARGS, "set one bit");
24    EXPECT_EQ(bitmap.ClearOne(0), ZX_ERR_INVALID_ARGS, "clear one bit");
25
26    EXPECT_EQ(bitmap.Reset(1), ZX_OK);
27    EXPECT_FALSE(bitmap.GetOne(0), "get one bit");
28    EXPECT_EQ(bitmap.SetOne(0), ZX_OK, "set one bit");
29    EXPECT_EQ(bitmap.ClearOne(0), ZX_OK, "clear one bit");
30
31    END_TEST;
32}
33
34template <typename RawBitmap> static bool SingleBit(void) {
35    BEGIN_TEST;
36
37    RawBitmap bitmap;
38    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
39    EXPECT_EQ(bitmap.size(), 128U, "get size");
40
41    EXPECT_FALSE(bitmap.GetOne(2), "get bit before setting");
42
43    EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
44    EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting");
45
46    EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit");
47    EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing");
48
49    END_TEST;
50}
51
52template <typename RawBitmap> static bool SetTwice(void) {
53    BEGIN_TEST;
54
55    RawBitmap bitmap;
56    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
57    EXPECT_EQ(bitmap.size(), 128U, "get size");
58
59    EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
60    EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting");
61
62    EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit again");
63    EXPECT_TRUE(bitmap.GetOne(2), "get bit after setting again");
64
65    END_TEST;
66}
67
68template <typename RawBitmap> static bool ClearTwice(void) {
69    BEGIN_TEST;
70
71    RawBitmap bitmap;
72    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
73    EXPECT_EQ(bitmap.size(), 128U, "get size");
74
75    EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
76
77    EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit");
78    EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing");
79
80    EXPECT_EQ(bitmap.ClearOne(2), ZX_OK, "clear bit again");
81    EXPECT_FALSE(bitmap.GetOne(2), "get bit after clearing again");
82
83    END_TEST;
84}
85
86template <typename RawBitmap> static bool GetReturnArg(void) {
87    BEGIN_TEST;
88
89    RawBitmap bitmap;
90    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
91    EXPECT_EQ(bitmap.size(), 128U, "get size");
92
93    size_t first_unset = 0;
94    EXPECT_FALSE(bitmap.Get(2, 3, nullptr), "get bit with null");
95    EXPECT_FALSE(bitmap.Get(2, 3, &first_unset), "get bit with nonnull");
96    EXPECT_EQ(first_unset, 2U, "check returned arg");
97
98    EXPECT_EQ(bitmap.SetOne(2), ZX_OK, "set bit");
99    EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get bit after setting");
100    EXPECT_EQ(first_unset, 3U, "check returned arg");
101
102    first_unset = 0;
103    EXPECT_FALSE(bitmap.Get(2, 4, &first_unset), "get larger range after setting");
104    EXPECT_EQ(first_unset, 3U, "check returned arg");
105
106    EXPECT_EQ(bitmap.SetOne(3), ZX_OK, "set another bit");
107    EXPECT_FALSE(bitmap.Get(2, 5, &first_unset), "get larger range after setting another");
108    EXPECT_EQ(first_unset, 4U, "check returned arg");
109
110    END_TEST;
111}
112
113template <typename RawBitmap> static bool SetRange(void) {
114    BEGIN_TEST;
115
116    RawBitmap bitmap;
117    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
118    EXPECT_EQ(bitmap.size(), 128U, "get size");
119
120    EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
121
122    size_t first_unset = 0;
123    EXPECT_TRUE(bitmap.Get(2, 3, &first_unset), "get first bit in range");
124    EXPECT_EQ(first_unset, 3U, "check returned arg");
125
126    EXPECT_TRUE(bitmap.Get(99, 100, &first_unset), "get last bit in range");
127    EXPECT_EQ(first_unset, 100U, "check returned arg");
128
129    EXPECT_FALSE(bitmap.Get(1, 2, &first_unset), "get bit before first in range");
130    EXPECT_EQ(first_unset, 1U, "check returned arg");
131
132    EXPECT_FALSE(bitmap.Get(100, 101, &first_unset), "get bit after last in range");
133    EXPECT_EQ(first_unset, 100U, "check returned arg");
134
135    EXPECT_TRUE(bitmap.Get(2, 100, &first_unset), "get entire range");
136    EXPECT_EQ(first_unset, 100U, "check returned arg");
137
138    EXPECT_TRUE(bitmap.Get(50, 80, &first_unset), "get part of range");
139    EXPECT_EQ(first_unset, 80U, "check returned arg");
140
141    size_t result;
142    EXPECT_FALSE(bitmap.Scan(0, 100, true, &result), "scan set bits");
143    EXPECT_EQ(result, 0U, "scan set bits");
144    EXPECT_FALSE(bitmap.ReverseScan(0, 100, true, &result), "reverse scan set bits");
145    EXPECT_EQ(result, 1U, "reverse scan set bits");
146
147    EXPECT_FALSE(bitmap.Scan(0, 100, false, &result), "scan cleared bits");
148    EXPECT_EQ(result, 2U, "scan cleared bits to start");
149    EXPECT_FALSE(bitmap.ReverseScan(0, 100, false, &result), "reverse scan cleared bits");
150    EXPECT_EQ(result, 99U, "reverse scan cleared bits");
151
152    EXPECT_TRUE(bitmap.Scan(2, 100, true), "scan set bits in set range");
153    EXPECT_TRUE(bitmap.ReverseScan(2, 100, true), "reverse scan set bits in set range");
154
155    EXPECT_FALSE(bitmap.Scan(2, 100, false, &result), "scan cleared bits in set range");
156    EXPECT_EQ(result, 2U, "scan cleared bits in set range");
157    EXPECT_FALSE(bitmap.ReverseScan(2, 100, false, &result),
158                 "reverse scan cleared bits in set range");
159    EXPECT_EQ(result, 99U, "reverse scan cleared bits in set range");
160
161    EXPECT_TRUE(bitmap.Scan(50, 80, true), "scan set bits in subrange");
162    EXPECT_TRUE(bitmap.ReverseScan(50, 80, true), "reverse scan set bits in subrange");
163
164    EXPECT_TRUE(bitmap.Scan(100, 200, false), "scan past end of bitmap");
165    EXPECT_TRUE(bitmap.ReverseScan(100, 200, false), "reverse scan past end of bitmap");
166
167    END_TEST;
168}
169
170template <typename RawBitmap> static bool FindSimple(void) {
171    BEGIN_TEST;
172
173    RawBitmap bitmap;
174    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
175    EXPECT_EQ(bitmap.size(), 128U, "get size");
176
177    size_t bitoff_start;
178
179    // Invalid finds
180    EXPECT_EQ(bitmap.Find(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
181    EXPECT_EQ(bitmap.ReverseFind(false, 0, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
182    EXPECT_EQ(bitmap.Find(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
183    EXPECT_EQ(bitmap.ReverseFind(false, 1, 0, 1, &bitoff_start), ZX_ERR_INVALID_ARGS, "bad range");
184    EXPECT_EQ(bitmap.Find(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
185    EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, nullptr), ZX_ERR_INVALID_ARGS, "bad output");
186
187    // Finds from offset zero
188    EXPECT_EQ(bitmap.Find(false, 0, 100, 1, &bitoff_start), ZX_OK, "find unset");
189    EXPECT_EQ(bitoff_start, 0, "check returned arg");
190    EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 1, &bitoff_start), ZX_OK, "reverse find unset");
191    EXPECT_EQ(bitoff_start, 99, "check returned arg");
192
193    EXPECT_EQ(bitmap.Find(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES, "find set");
194    EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
195              "reverse find set");
196
197    EXPECT_EQ(bitmap.Find(false, 0, 100, 5, &bitoff_start), ZX_OK, "find more unset");
198    EXPECT_EQ(bitoff_start, 0, "check returned arg");
199    EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 5, &bitoff_start), ZX_OK,
200              "reverse find more unset");
201    EXPECT_EQ(bitoff_start, 95, "check returned arg");
202
203    EXPECT_EQ(bitmap.Find(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES, "find more set");
204    EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 5, &bitoff_start), ZX_ERR_NO_RESOURCES,
205              "reverse find more set");
206
207    EXPECT_EQ(bitmap.Find(false, 0, 100, 100, &bitoff_start), ZX_OK, "find all unset");
208    EXPECT_EQ(bitoff_start, 0, "check returned arg");
209    EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 100, &bitoff_start), ZX_OK,
210              "reverse find all unset");
211    EXPECT_EQ(bitoff_start, 0, "check returned arg");
212
213    EXPECT_EQ(bitmap.Find(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES, "find all set");
214    EXPECT_EQ(bitmap.ReverseFind(true, 0, 100, 100, &bitoff_start), ZX_ERR_NO_RESOURCES,
215              "reverse find all set");
216
217    // Finds at an offset
218    EXPECT_EQ(bitmap.Find(false, 50, 100, 3, &bitoff_start), ZX_OK, "find at offset");
219    EXPECT_EQ(bitoff_start, 50, "check returned arg");
220    EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 3, &bitoff_start), ZX_OK,
221              "reverse find at offset");
222    EXPECT_EQ(bitoff_start, 97, "check returned arg");
223
224    EXPECT_EQ(bitmap.Find(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail at offset");
225    EXPECT_EQ(bitmap.ReverseFind(true, 50, 100, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
226              "reverse fail at offset");
227
228    EXPECT_EQ(bitmap.Find(false, 90, 100, 10, &bitoff_start), ZX_OK, "find at offset end");
229    EXPECT_EQ(bitoff_start, 90, "check returned arg");
230    EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 10, &bitoff_start), ZX_OK,
231              "reverse find at offset end");
232    EXPECT_EQ(bitoff_start, 90, "check returned arg");
233
234    // Invalid scans
235    EXPECT_EQ(bitmap.Find(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
236    EXPECT_EQ(bitmap.ReverseFind(false, 0, 100, 101, &bitoff_start), ZX_ERR_NO_RESOURCES,
237              "no space");
238    EXPECT_EQ(bitmap.Find(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
239    EXPECT_EQ(bitmap.ReverseFind(false, 91, 100, 10, &bitoff_start), ZX_ERR_NO_RESOURCES,
240              "no space");
241    EXPECT_EQ(bitmap.Find(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
242    EXPECT_EQ(bitmap.ReverseFind(false, 90, 100, 11, &bitoff_start), ZX_ERR_NO_RESOURCES,
243              "no space");
244    EXPECT_EQ(bitmap.Find(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
245    EXPECT_EQ(bitmap.ReverseFind(false, 90, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES, "no space");
246
247    // Fill the bitmap
248    EXPECT_EQ(bitmap.Set(5, 10), ZX_OK, "set range");
249    EXPECT_EQ(bitmap.Set(20, 30), ZX_OK, "set range");
250    EXPECT_EQ(bitmap.Set(32, 35), ZX_OK, "set range");
251    EXPECT_EQ(bitmap.Set(90, 95), ZX_OK, "set range");
252    EXPECT_EQ(bitmap.Set(70, 80), ZX_OK, "set range");
253    EXPECT_EQ(bitmap.Set(65, 68), ZX_OK, "set range");
254
255    EXPECT_EQ(bitmap.Find(false, 0, 50, 5, &bitoff_start), ZX_OK, "find in first group");
256    EXPECT_EQ(bitoff_start, 0, "check returned arg");
257    EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 5, &bitoff_start), ZX_OK,
258              "reverse find in first group");
259    EXPECT_EQ(bitoff_start, 95, "check returned arg");
260
261    EXPECT_EQ(bitmap.Find(false, 0, 50, 10, &bitoff_start), ZX_OK, "find in second group");
262    EXPECT_EQ(bitoff_start, 10, "check returned arg");
263    EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 10, &bitoff_start), ZX_OK,
264              "reverse find in second group");
265    EXPECT_EQ(bitoff_start, 80, "check returned arg");
266
267    EXPECT_EQ(bitmap.Find(false, 0, 50, 15, &bitoff_start), ZX_OK, "find in third group");
268    EXPECT_EQ(bitoff_start, 35, "check returned arg");
269    EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 15, &bitoff_start), ZX_OK,
270              "reverse find in third group");
271    EXPECT_EQ(bitoff_start, 50, "check returned arg");
272
273    EXPECT_EQ(bitmap.Find(false, 0, 50, 16, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
274    EXPECT_EQ(bitmap.ReverseFind(false, 50, 100, 16, &bitoff_start), ZX_ERR_NO_RESOURCES,
275              "reverse fail to find");
276
277    EXPECT_EQ(bitmap.Find(false, 5, 20, 10, &bitoff_start), ZX_OK, "find space (offset)");
278    EXPECT_EQ(bitoff_start, 10, "check returned arg");
279    EXPECT_EQ(bitmap.ReverseFind(false, 80, 95, 10, &bitoff_start), ZX_OK,
280              "reverse find space (offset)");
281    EXPECT_EQ(bitoff_start, 80, "check returned arg");
282
283    EXPECT_EQ(bitmap.Find(false, 5, 25, 10, &bitoff_start), ZX_OK, "find space (offset)");
284    EXPECT_EQ(bitoff_start, 10, "check returned arg");
285    EXPECT_EQ(bitmap.ReverseFind(false, 75, 95, 10, &bitoff_start), ZX_OK,
286              "reverse find space (offset)");
287    EXPECT_EQ(bitoff_start, 80, "check returned arg");
288
289    EXPECT_EQ(bitmap.Find(false, 5, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
290              "fail to find (offset)");
291    EXPECT_EQ(bitmap.ReverseFind(false, 85, 95, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
292              "reverse fail to find (offset)");
293
294    EXPECT_EQ(bitmap.Find(true, 0, 15, 2, &bitoff_start), ZX_OK, "find set bits");
295    EXPECT_EQ(bitoff_start, 5, "check returned arg");
296    EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 2, &bitoff_start), ZX_OK, "reverse find set bits");
297    EXPECT_EQ(bitoff_start, 93, "check returned arg");
298
299    EXPECT_EQ(bitmap.Find(true, 0, 15, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
300              "find set bits (fail)");
301    EXPECT_EQ(bitmap.ReverseFind(true, 85, 100, 6, &bitoff_start), ZX_ERR_NO_RESOURCES,
302              "reverse find set bits (fail)");
303
304    EXPECT_EQ(bitmap.Find(false, 32, 35, 3, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
305    EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 3, &bitoff_start), ZX_ERR_NO_RESOURCES,
306              "reverse fail to find");
307
308    EXPECT_EQ(bitmap.Find(false, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES, "fail to find");
309    EXPECT_EQ(bitmap.ReverseFind(false, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
310              "reverse fail to find");
311
312    EXPECT_EQ(bitmap.Find(true, 32, 35, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
313              "fail to find (set)");
314    EXPECT_EQ(bitmap.ReverseFind(true, 65, 68, 4, &bitoff_start), ZX_ERR_NO_RESOURCES,
315              "reverse fail to find (set)");
316
317    // Fill the whole bitmap
318    EXPECT_EQ(bitmap.Set(0, 128), ZX_OK, "set range");
319
320    EXPECT_EQ(bitmap.Find(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
321              "fail to find (small)");
322    EXPECT_EQ(bitmap.ReverseFind(false, 0, 1, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
323              "reverse fail to find (small)");
324
325    EXPECT_EQ(bitmap.Find(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
326              "fail to find (large)");
327    EXPECT_EQ(bitmap.ReverseFind(false, 0, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
328              "reverse fail to find (large)");
329
330    END_TEST;
331}
332
333template <typename RawBitmap> static bool ClearAll(void) {
334    BEGIN_TEST;
335
336    RawBitmap bitmap;
337    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
338    EXPECT_EQ(bitmap.size(), 128U, "get size");
339
340    EXPECT_EQ(bitmap.Set(0, 100), ZX_OK, "set range");
341
342    bitmap.ClearAll();
343
344    size_t first = 0;
345    EXPECT_FALSE(bitmap.Get(2, 100, &first), "get range");
346    EXPECT_EQ(first, 2U, "all clear");
347
348    EXPECT_EQ(bitmap.Set(0, 99), ZX_OK, "set range");
349    EXPECT_FALSE(bitmap.Get(0, 100, &first), "get range");
350    EXPECT_EQ(first, 99U, "all clear");
351
352    END_TEST;
353}
354
355template <typename RawBitmap> static bool ClearSubrange(void) {
356    BEGIN_TEST;
357
358    RawBitmap bitmap;
359    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
360    EXPECT_EQ(bitmap.size(), 128U, "get size");
361
362    EXPECT_EQ(bitmap.Set(2, 100), ZX_OK, "set range");
363    EXPECT_EQ(bitmap.Clear(50, 80), ZX_OK, "clear range");
364
365    size_t first_unset = 0;
366    EXPECT_FALSE(bitmap.Get(2, 100, &first_unset), "get whole original range");
367    EXPECT_EQ(first_unset, 50U, "check returned arg");
368
369    first_unset = 0;
370    EXPECT_TRUE(bitmap.Get(2, 50, &first_unset), "get first half range");
371    EXPECT_EQ(first_unset, 50U, "check returned arg");
372
373    EXPECT_TRUE(bitmap.Get(80, 100, &first_unset), "get second half range");
374    EXPECT_EQ(first_unset, 100U, "check returned arg");
375
376    EXPECT_FALSE(bitmap.Get(50, 80, &first_unset), "get cleared range");
377    EXPECT_EQ(first_unset, 50U, "check returned arg");
378
379    END_TEST;
380}
381
382template <typename RawBitmap> static bool BoundaryArguments(void) {
383    BEGIN_TEST;
384
385    RawBitmap bitmap;
386    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
387    EXPECT_EQ(bitmap.size(), 128U, "get size");
388
389    EXPECT_EQ(bitmap.Set(0, 0), ZX_OK, "range contains no bits");
390    EXPECT_EQ(bitmap.Set(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
391    EXPECT_EQ(bitmap.Set(5, 5), ZX_OK, "range contains no bits");
392
393    EXPECT_EQ(bitmap.Clear(0, 0), ZX_OK, "range contains no bits");
394    EXPECT_EQ(bitmap.Clear(5, 4), ZX_ERR_INVALID_ARGS, "max is less than off");
395    EXPECT_EQ(bitmap.Clear(5, 5), ZX_OK, "range contains no bits");
396
397    EXPECT_TRUE(bitmap.Get(0, 0), "range contains no bits, so all are true");
398    EXPECT_TRUE(bitmap.Get(5, 4), "range contains no bits, so all are true");
399    EXPECT_TRUE(bitmap.Get(5, 5), "range contains no bits, so all are true");
400
401    END_TEST;
402}
403
404template <typename RawBitmap> static bool SetOutOfOrder(void) {
405    BEGIN_TEST;
406
407    RawBitmap bitmap;
408    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
409    EXPECT_EQ(bitmap.size(), 128U, "get size");
410
411    EXPECT_EQ(bitmap.SetOne(0x64), ZX_OK, "setting later");
412    EXPECT_EQ(bitmap.SetOne(0x60), ZX_OK, "setting earlier");
413
414    EXPECT_TRUE(bitmap.GetOne(0x64), "getting first set");
415    EXPECT_TRUE(bitmap.GetOne(0x60), "getting second set");
416    END_TEST;
417}
418
419template <typename RawBitmap> static bool GrowAcrossPage(void) {
420    BEGIN_TEST;
421
422    RawBitmap bitmap;
423    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
424    EXPECT_EQ(bitmap.size(), 128u);
425
426    EXPECT_FALSE(bitmap.GetOne(100));
427    EXPECT_EQ(bitmap.SetOne(100), ZX_OK);
428    EXPECT_TRUE(bitmap.GetOne(100));
429
430    size_t bitoff_start;
431    EXPECT_EQ(bitmap.Find(true, 101, 128, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
432              "Expected tail end of bitmap to be unset");
433
434    // We can't set bits out of range
435    EXPECT_NE(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK);
436
437    EXPECT_EQ(bitmap.Grow(16 * PAGE_SIZE), ZX_OK);
438    EXPECT_EQ(bitmap.Find(true, 101, 16 * PAGE_SIZE, 1, &bitoff_start), ZX_ERR_NO_RESOURCES,
439              "Expected tail end of bitmap to be unset");
440
441    // Now we can set the previously inaccessible bits
442    EXPECT_FALSE(bitmap.GetOne(16 * PAGE_SIZE - 1));
443    EXPECT_EQ(bitmap.SetOne(16 * PAGE_SIZE - 1), ZX_OK);
444    EXPECT_TRUE(bitmap.GetOne(16 * PAGE_SIZE - 1));
445
446    // But our orignal 'set bit' is still set
447    EXPECT_TRUE(bitmap.GetOne(100), "Growing should not unset bits");
448
449    // If we shrink and re-expand the bitmap, it should
450    // have cleared the underlying bits
451    EXPECT_EQ(bitmap.Shrink(99), ZX_OK);
452    EXPECT_EQ(bitmap.Grow(16 * PAGE_SIZE), ZX_OK);
453    EXPECT_FALSE(bitmap.GetOne(100));
454    EXPECT_FALSE(bitmap.GetOne(16 * PAGE_SIZE - 1));
455
456    END_TEST;
457}
458
459template <typename RawBitmap> static bool GrowShrink(void) {
460    BEGIN_TEST;
461
462    RawBitmap bitmap;
463    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
464    EXPECT_EQ(bitmap.size(), 128u);
465
466    EXPECT_FALSE(bitmap.GetOne(100));
467    EXPECT_EQ(bitmap.SetOne(100), ZX_OK);
468    EXPECT_TRUE(bitmap.GetOne(100));
469
470    for (size_t i = 8; i < 16; i++) {
471        for (int j = -16; j <= 16; j++) {
472            size_t bitmap_size = (1 << i) + j;
473
474            for (size_t shrink_len = 1; shrink_len < 32; shrink_len++) {
475                EXPECT_EQ(bitmap.Reset(bitmap_size), ZX_OK);
476                EXPECT_EQ(bitmap.size(), bitmap_size);
477
478                // This bit will be eliminated by shrink / grow
479                EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len));
480                EXPECT_EQ(bitmap.SetOne(bitmap_size - shrink_len), ZX_OK);
481                EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len));
482
483                // This bit will stay
484                EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len - 1));
485                EXPECT_EQ(bitmap.SetOne(bitmap_size - shrink_len - 1), ZX_OK);
486                EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len - 1));
487
488                EXPECT_EQ(bitmap.Shrink(bitmap_size - shrink_len), ZX_OK);
489                EXPECT_EQ(bitmap.Grow(bitmap_size), ZX_OK);
490
491                EXPECT_FALSE(bitmap.GetOne(bitmap_size - shrink_len),
492                             "Expected 'shrunk' bit to be unset");
493                EXPECT_TRUE(bitmap.GetOne(bitmap_size - shrink_len - 1),
494                            "Expected bit outside shrink range to be set");
495
496                size_t bitoff_start;
497                EXPECT_EQ(
498                    bitmap.Find(true, bitmap_size - shrink_len, bitmap_size, 1, &bitoff_start),
499                    ZX_ERR_NO_RESOURCES, "Expected tail end of bitmap to be unset");
500            }
501        }
502    }
503
504    END_TEST;
505}
506
507template <typename RawBitmap> static bool GrowFailure(void) {
508    BEGIN_TEST;
509
510    RawBitmap bitmap;
511    EXPECT_EQ(bitmap.Reset(128), ZX_OK);
512    EXPECT_EQ(bitmap.size(), 128u);
513
514    EXPECT_EQ(bitmap.Grow(64), ZX_ERR_NO_RESOURCES);
515    EXPECT_EQ(bitmap.Grow(128), ZX_ERR_NO_RESOURCES);
516    EXPECT_EQ(bitmap.Grow(128 + 1), ZX_ERR_NO_RESOURCES);
517    EXPECT_EQ(bitmap.Grow(8 * PAGE_SIZE), ZX_ERR_NO_RESOURCES);
518    END_TEST;
519}
520
521#define RUN_TEMPLATIZED_TEST(test, specialization) RUN_TEST(test<specialization>)
522#define ALL_TESTS(specialization)                                                                  \
523    RUN_TEMPLATIZED_TEST(InitializedEmpty, specialization)                                         \
524    RUN_TEMPLATIZED_TEST(SingleBit, specialization)                                                \
525    RUN_TEMPLATIZED_TEST(SetTwice, specialization)                                                 \
526    RUN_TEMPLATIZED_TEST(ClearTwice, specialization)                                               \
527    RUN_TEMPLATIZED_TEST(GetReturnArg, specialization)                                             \
528    RUN_TEMPLATIZED_TEST(SetRange, specialization)                                                 \
529    RUN_TEMPLATIZED_TEST(FindSimple, specialization)                                               \
530    RUN_TEMPLATIZED_TEST(ClearSubrange, specialization)                                            \
531    RUN_TEMPLATIZED_TEST(BoundaryArguments, specialization)                                        \
532    RUN_TEMPLATIZED_TEST(ClearAll, specialization)                                                 \
533    RUN_TEMPLATIZED_TEST(SetOutOfOrder, specialization)
534
535BEGIN_TEST_CASE(raw_bitmap_tests)
536ALL_TESTS(RawBitmapGeneric<DefaultStorage>)
537ALL_TESTS(RawBitmapGeneric<VmoStorage>)
538RUN_TEST(GrowAcrossPage<RawBitmapGeneric<VmoStorage>>)
539RUN_TEST(GrowShrink<RawBitmapGeneric<VmoStorage>>)
540RUN_TEST(GrowFailure<RawBitmapGeneric<DefaultStorage>>)
541END_TEST_CASE(raw_bitmap_tests);
542
543} // namespace tests
544} // namespace bitmap
545