1 /*
2 * Copyright (c) 2015 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29
30 #if DEVELOPMENT || DEBUG
31
32 #include <tests/xnupost.h>
33 #include <kern/kalloc.h>
34 #include <kern/bits.h>
35 #include <pexpert/pexpert.h>
36
37 extern void dump_bitmap_next(bitmap_t *map, uint nbits);
38 extern void dump_bitmap_lsb(bitmap_t *map, uint nbits);
39 extern void test_bitmap(void);
40 extern void test_bits(void);
41 extern kern_return_t bitmap_post_test(void);
42
43 void
dump_bitmap_next(bitmap_t * map,uint nbits)44 dump_bitmap_next(bitmap_t *map, uint nbits)
45 {
46 for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
47 printf(" %d", i);
48 }
49 printf("\n");
50 }
51
52 void
dump_bitmap_lsb(bitmap_t * map,uint nbits)53 dump_bitmap_lsb(bitmap_t *map, uint nbits)
54 {
55 for (int i = bitmap_lsb_first(map, nbits); i >= 0; i = bitmap_lsb_next(map, nbits, i)) {
56 printf(" %d", i);
57 }
58 printf("\n");
59 }
60
61 #ifdef NOTDEF
62 #ifdef assert
63 #undef assert
64 #endif
65 #define assert(x) T_ASSERT(x, NULL)
66 #endif
67
68 void
test_bitmap(void)69 test_bitmap(void)
70 {
71 uint start = 60;
72 for (uint nbits = start; nbits <= 192; nbits++) {
73 bitmap_t *map = bitmap_alloc(nbits);
74
75 for (uint i = 0; i < nbits; i++) {
76 bitmap_set(map, i);
77 }
78 assert(bitmap_is_full(map, nbits));
79
80 int expected_result = nbits - 1;
81 for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
82 assert(i == expected_result);
83 expected_result--;
84 }
85 assert(expected_result == -1);
86
87 bitmap_zero(map, nbits);
88
89 assert(bitmap_first(map, nbits) == -1);
90 assert(bitmap_lsb_first(map, nbits) == -1);
91
92 bitmap_full(map, nbits);
93 assert(bitmap_is_full(map, nbits));
94
95 expected_result = nbits - 1;
96 for (int i = bitmap_first(map, nbits); i >= 0; i = bitmap_next(map, i)) {
97 assert(i == expected_result);
98 expected_result--;
99 }
100 assert(expected_result == -1);
101
102 expected_result = 0;
103 for (int i = bitmap_lsb_first(map, nbits); i >= 0; i = bitmap_lsb_next(map, nbits, i)) {
104 assert(i == expected_result);
105 expected_result++;
106 }
107 assert(expected_result == (int)nbits);
108
109 for (uint i = 0; i < nbits; i++) {
110 bitmap_clear(map, i);
111 assert(!bitmap_is_full(map, nbits));
112 bitmap_set(map, i);
113 assert(bitmap_is_full(map, nbits));
114 }
115
116 for (uint i = 0; i < nbits; i++) {
117 bitmap_clear(map, i);
118 }
119 assert(bitmap_first(map, nbits) == -1);
120 assert(bitmap_lsb_first(map, nbits) == -1);
121
122 /* bitmap_not */
123 bitmap_not(map, map, nbits);
124 assert(bitmap_is_full(map, nbits));
125
126 bitmap_not(map, map, nbits);
127 assert(bitmap_first(map, nbits) == -1);
128 assert(bitmap_lsb_first(map, nbits) == -1);
129
130 /* bitmap_and */
131 bitmap_t *map0 = bitmap_alloc(nbits);
132 assert(bitmap_first(map0, nbits) == -1);
133
134 bitmap_t *map1 = bitmap_alloc(nbits);
135 bitmap_full(map1, nbits);
136 assert(bitmap_is_full(map1, nbits));
137
138 bitmap_and(map, map0, map1, nbits);
139 assert(bitmap_first(map, nbits) == -1);
140
141 bitmap_and(map, map1, map1, nbits);
142 assert(bitmap_is_full(map, nbits));
143
144 /* bitmap_or */
145 bitmap_or(map, map1, map0, nbits);
146 assert(bitmap_is_full(map, nbits));
147
148 bitmap_or(map, map0, map0, nbits);
149 assert(bitmap_first(map, nbits) == -1);
150
151 /* bitmap_and_not */
152 bitmap_and_not(map, map0, map1, nbits);
153 assert(bitmap_first(map, nbits) == -1);
154
155 bitmap_and_not(map, map1, map0, nbits);
156 assert(bitmap_is_full(map, nbits));
157
158 /* bitmap_equal */
159 for (uint i = 0; i < nbits; i++) {
160 bitmap_clear(map, i);
161 assert(!bitmap_equal(map, map1, nbits));
162 bitmap_set(map, i);
163 assert(bitmap_equal(map, map1, nbits));
164 }
165
166 /* bitmap_and_not_mask_first */
167 for (uint i = 0; i < nbits; i++) {
168 bitmap_clear(map, i);
169 expected_result = i;
170 int result = bitmap_and_not_mask_first(map1, map, nbits);
171 assert(result == expected_result);
172 bitmap_set(map, i);
173 result = bitmap_and_not_mask_first(map1, map, nbits);
174 assert(result == -1);
175 }
176
177 bitmap_free(map, nbits);
178 bitmap_free(map0, nbits);
179 bitmap_free(map1, nbits);
180 }
181 }
182
183 void
test_bits(void)184 test_bits(void)
185 {
186 bitmap_t map = 0;
187
188 for (int i = 0; i < 64; i++) {
189 __assert_only bool changed = bit_set_if_clear(map, i);
190 assert(changed);
191 }
192 assert(map == ~0);
193 for (int i = 0; i < 64; i++) {
194 __assert_only bool changed = bit_set_if_clear(map, i);
195 assert(!changed);
196 }
197
198 for (int i = 0; i < 64; i++) {
199 __assert_only bool changed = bit_clear_if_set(map, i);
200 assert(changed);
201 }
202 assert(map == 0);
203 for (int i = 0; i < 64; i++) {
204 __assert_only bool changed = bit_clear_if_set(map, i);
205 assert(!changed);
206 }
207 }
208
209 kern_return_t
bitmap_post_test(void)210 bitmap_post_test(void)
211 {
212 test_bits();
213
214 test_bitmap();
215
216 kern_return_t ret = KERN_SUCCESS;
217
218 T_ASSERT(ret == KERN_SUCCESS, NULL);
219
220 return ret;
221 }
222 #endif
223