worker: Do not use poll_block() in worker_send_iovec().
[sliver-openvswitch.git] / tests / test-util.c
1 /*
2  * Copyright (c) 2011, 2012 Nicira, Inc.
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 <config.h>
18
19 #include <inttypes.h>
20 #include <limits.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23
24 #include "byte-order.h"
25 #include "command-line.h"
26 #include "random.h"
27 #include "util.h"
28
29 #undef NDEBUG
30 #include <assert.h>
31
32 static void
33 check_log_2_floor(uint32_t x, int n)
34 {
35     if (log_2_floor(x) != n) {
36         fprintf(stderr, "log_2_floor(%"PRIu32") is %d but should be %d\n",
37                 x, log_2_floor(x), n);
38         abort();
39     }
40 }
41
42 static void
43 test_log_2_floor(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
44 {
45     int n;
46
47     for (n = 0; n < 32; n++) {
48         /* Check minimum x such that f(x) == n. */
49         check_log_2_floor(1 << n, n);
50
51         /* Check maximum x such that f(x) == n. */
52         check_log_2_floor((1 << n) | ((1 << n) - 1), n);
53
54         /* Check a random value in the middle. */
55         check_log_2_floor((random_uint32() & ((1 << n) - 1)) | (1 << n), n);
56     }
57
58     /* log_2_floor(0) is undefined, so don't check it. */
59 }
60
61 static void
62 check_ctz(uint32_t x, int n)
63 {
64     if (ctz(x) != n) {
65         fprintf(stderr, "ctz(%"PRIu32") is %d but should be %d\n",
66                 x, ctz(x), n);
67         abort();
68     }
69 }
70
71 static void
72 test_ctz(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
73 {
74     int n;
75
76     for (n = 0; n < 32; n++) {
77         /* Check minimum x such that f(x) == n. */
78         check_ctz(1 << n, n);
79
80         /* Check maximum x such that f(x) == n. */
81         check_ctz(UINT32_MAX << n, n);
82
83         /* Check a random value in the middle. */
84         check_ctz((random_uint32() | 1) << n, n);
85     }
86
87     /* Check ctz(0). */
88     check_ctz(0, 32);
89 }
90
91 static void
92 shuffle(unsigned int *p, size_t n)
93 {
94     for (; n > 1; n--, p++) {
95         unsigned int *q = &p[rand() % n];
96         unsigned int tmp = *p;
97         *p = *q;
98         *q = tmp;
99     }
100 }
101
102 static void
103 check_popcount(uint32_t x, int n)
104 {
105     if (popcount(x) != n) {
106         fprintf(stderr, "popcount(%#"PRIx32") is %d but should be %d\n",
107                 x, popcount(x), n);
108         abort();
109     }
110 }
111
112 static void
113 test_popcount(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
114 {
115     unsigned int bits[32];
116     int i;
117
118     for (i = 0; i < ARRAY_SIZE(bits); i++) {
119         bits[i] = 1u << i;
120     }
121
122     check_popcount(0, 0);
123
124     for (i = 0; i < 1000; i++) {
125         uint32_t x = 0;
126         int j;
127
128         shuffle(bits, ARRAY_SIZE(bits));
129         for (j = 0; j < 32; j++) {
130             x |= bits[j];
131             check_popcount(x, j + 1);
132         }
133         assert(x == UINT32_MAX);
134
135         shuffle(bits, ARRAY_SIZE(bits));
136         for (j = 31; j >= 0; j--) {
137             x &= ~bits[j];
138             check_popcount(x, j);
139         }
140         assert(x == 0);
141     }
142 }
143
144 /* Returns the sum of the squares of the first 'n' positive integers. */
145 static unsigned int
146 sum_of_squares(int n)
147 {
148     return n * (n + 1) * (2 * n + 1) / 6;
149 }
150
151 static void
152 test_bitwise_copy(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
153 {
154     unsigned int n_loops;
155     int src_ofs;
156     int dst_ofs;
157     int n_bits;
158
159     n_loops = 0;
160     for (n_bits = 0; n_bits <= 64; n_bits++) {
161         for (src_ofs = 0; src_ofs < 64 - n_bits; src_ofs++) {
162             for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
163                 ovs_be64 src = htonll(random_uint64());
164                 ovs_be64 dst = htonll(random_uint64());
165                 ovs_be64 orig_dst = dst;
166                 ovs_be64 expect;
167
168                 if (n_bits == 64) {
169                     expect = dst;
170                 } else {
171                     uint64_t mask = (UINT64_C(1) << n_bits) - 1;
172                     expect = orig_dst & ~htonll(mask << dst_ofs);
173                     expect |= htonll(((ntohll(src) >> src_ofs) & mask)
174                                      << dst_ofs);
175                 }
176
177                 bitwise_copy(&src, sizeof src, src_ofs,
178                              &dst, sizeof dst, dst_ofs,
179                              n_bits);
180                 if (expect != dst) {
181                     fprintf(stderr,"copy_bits(0x%016"PRIx64",8,%d, "
182                             "0x%016"PRIx64",8,%d, %d) yielded 0x%016"PRIx64" "
183                             "instead of the expected 0x%016"PRIx64"\n",
184                             ntohll(src), src_ofs,
185                             ntohll(orig_dst), dst_ofs,
186                             n_bits,
187                             ntohll(dst), ntohll(expect));
188                     abort();
189                 }
190
191                 n_loops++;
192             }
193         }
194     }
195
196     if (n_loops != sum_of_squares(64)) {
197         abort();
198     }
199 }
200
201 static void
202 test_bitwise_zero(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
203 {
204     unsigned int n_loops;
205     int dst_ofs;
206     int n_bits;
207
208     n_loops = 0;
209     for (n_bits = 0; n_bits <= 64; n_bits++) {
210         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
211             ovs_be64 dst = htonll(random_uint64());
212             ovs_be64 orig_dst = dst;
213             ovs_be64 expect;
214
215             if (n_bits == 64) {
216                 expect = htonll(0);
217             } else {
218                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
219                 expect = orig_dst & ~htonll(mask << dst_ofs);
220             }
221
222             bitwise_zero(&dst, sizeof dst, dst_ofs, n_bits);
223             if (expect != dst) {
224                 fprintf(stderr,"bitwise_zero(0x%016"PRIx64",8,%d, %d) "
225                         "yielded 0x%016"PRIx64" "
226                         "instead of the expected 0x%016"PRIx64"\n",
227                         ntohll(orig_dst), dst_ofs,
228                         n_bits,
229                         ntohll(dst), ntohll(expect));
230                 abort();
231             }
232
233             n_loops++;
234         }
235     }
236
237     if (n_loops != 64 * (64 + 1) / 2) {
238         abort();
239     }
240 }
241
242 static void
243 test_bitwise_one(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
244 {
245     unsigned int n_loops;
246     int dst_ofs;
247     int n_bits;
248
249     n_loops = 0;
250     for (n_bits = 0; n_bits <= 64; n_bits++) {
251         for (dst_ofs = 0; dst_ofs < 64 - n_bits; dst_ofs++) {
252             ovs_be64 dst = htonll(random_uint64());
253             ovs_be64 orig_dst = dst;
254             ovs_be64 expect;
255
256             if (n_bits == 64) {
257                 expect = htonll(UINT64_MAX);
258             } else {
259                 uint64_t mask = (UINT64_C(1) << n_bits) - 1;
260                 expect = orig_dst | htonll(mask << dst_ofs);
261             }
262
263             bitwise_one(&dst, sizeof dst, dst_ofs, n_bits);
264             if (expect != dst) {
265                 fprintf(stderr,"bitwise_one(0x%016"PRIx64",8,%d, %d) "
266                         "yielded 0x%016"PRIx64" "
267                         "instead of the expected 0x%016"PRIx64"\n",
268                         ntohll(orig_dst), dst_ofs,
269                         n_bits,
270                         ntohll(dst), ntohll(expect));
271                 abort();
272             }
273
274             n_loops++;
275         }
276     }
277
278     if (n_loops != 64 * (64 + 1) / 2) {
279         abort();
280     }
281 }
282
283 static void
284 test_bitwise_is_all_zeros(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
285 {
286     int n_loops;
287
288     for (n_loops = 0; n_loops < 100; n_loops++) {
289         ovs_be64 x = htonll(0);
290         int i;
291
292         for (i = 0; i < 64; i++) {
293             ovs_be64 bit;
294             int ofs, n;
295
296             /* Change a random 0-bit into a 1-bit. */
297             do {
298                 bit = htonll(UINT64_C(1) << (random_uint32() % 64));
299             } while (x & bit);
300             x |= bit;
301
302             for (ofs = 0; ofs < 64; ofs++) {
303                 for (n = 0; n <= 64 - ofs; n++) {
304                     bool expect;
305                     bool answer;
306
307                     expect = (n == 64
308                               ? x == 0
309                               : !(x & htonll(((UINT64_C(1) << n) - 1)
310                                              << ofs)));
311                     answer = bitwise_is_all_zeros(&x, sizeof x, ofs, n);
312                     if (expect != answer) {
313                         fprintf(stderr,
314                                 "bitwise_is_all_zeros(0x%016"PRIx64",8,%d,%d "
315                                 "returned %s instead of %s\n",
316                                 ntohll(x), ofs, n,
317                                 answer ? "true" : "false",
318                                 expect ? "true" : "false");
319                         abort();
320                     }
321                 }
322             }
323         }
324     }
325 }
326
327 static void
328 test_follow_symlinks(int argc, char *argv[])
329 {
330     int i;
331
332     for (i = 1; i < argc; i++) {
333         char *target = follow_symlinks(argv[i]);
334         puts(target);
335         free(target);
336     }
337 }
338 \f
339 static const struct command commands[] = {
340     {"ctz", 0, 0, test_ctz},
341     {"popcount", 0, 0, test_popcount},
342     {"log_2_floor", 0, 0, test_log_2_floor},
343     {"bitwise_copy", 0, 0, test_bitwise_copy},
344     {"bitwise_zero", 0, 0, test_bitwise_zero},
345     {"bitwise_one", 0, 0, test_bitwise_one},
346     {"bitwise_is_all_zeros", 0, 0, test_bitwise_is_all_zeros},
347     {"follow-symlinks", 1, INT_MAX, test_follow_symlinks},
348     {NULL, 0, 0, NULL},
349 };
350
351 int
352 main(int argc, char *argv[])
353 {
354     set_program_name(argv[0]);
355     run_command(argc - 1, argv + 1, commands);
356     return 0;
357 }