1 /*
2 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include <stdio.h>
11 #include <string.h>
12
13 #include <openssl/opensslconf.h>
14 #include <internal/priority_queue.h>
15 #include <openssl/err.h>
16 #include <openssl/crypto.h>
17
18 #include "internal/nelem.h"
19 #include "testutil.h"
20
21 #define MAX_SAMPLES 500000
22
23 DEFINE_PRIORITY_QUEUE_OF(size_t);
24
25 static size_t num_rec_freed;
26
size_t_compare(const size_t * a,const size_t * b)27 static int size_t_compare(const size_t *a, const size_t *b)
28 {
29 if (*a < *b)
30 return -1;
31 if (*a > *b)
32 return 1;
33 return 0;
34 }
35
qsort_size_t_compare(const void * a,const void * b)36 static int qsort_size_t_compare(const void *a, const void *b)
37 {
38 return size_t_compare((size_t *)a, (size_t *)b);
39 }
40
qsort_size_t_compare_rev(const void * a,const void * b)41 static int qsort_size_t_compare_rev(const void *a, const void *b)
42 {
43 return size_t_compare((size_t *)b, (size_t *)a);
44 }
45
free_checker(ossl_unused size_t * p)46 static void free_checker(ossl_unused size_t *p)
47 {
48 num_rec_freed++;
49 }
50
test_size_t_priority_queue_int(int reserve,int order,int count,int remove,int random,int popfree)51 static int test_size_t_priority_queue_int(int reserve, int order, int count,
52 int remove, int random, int popfree)
53 {
54 PRIORITY_QUEUE_OF(size_t) *pq = NULL;
55 static size_t values[MAX_SAMPLES], sorted[MAX_SAMPLES], ref[MAX_SAMPLES];
56 size_t n;
57 int i, res = 0;
58 static const char *orders[3] = { "unordered", "ascending", "descending" };
59
60 TEST_info("testing count %d, %s, %s, values %s, remove %d, %sfree",
61 count, orders[order], reserve ? "reserve" : "grow",
62 random ? "random" : "deterministic", remove,
63 popfree ? "pop " : "");
64
65 if (!TEST_size_t_le(count, MAX_SAMPLES))
66 return 0;
67
68 memset(values, 0, sizeof(values));
69 memset(sorted, 0, sizeof(sorted));
70 memset(ref, 0, sizeof(ref));
71
72 for (i = 0; i < count; i++)
73 values[i] = random ? test_random() : (size_t)(count - i);
74 memcpy(sorted, values, sizeof(*sorted) * count);
75 qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
76
77 if (order == 1)
78 memcpy(values, sorted, sizeof(*values) * count);
79 else if (order == 2)
80 qsort(values, count, sizeof(*values), &qsort_size_t_compare_rev);
81
82 if (!TEST_ptr(pq = ossl_pqueue_size_t_new(&size_t_compare))
83 || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), 0))
84 goto err;
85
86 if (reserve && !TEST_true(ossl_pqueue_size_t_reserve(pq, count)))
87 goto err;
88
89 for (i = 0; i < count; i++)
90 if (!TEST_true(ossl_pqueue_size_t_push(pq, values + i, ref + i)))
91 goto err;
92
93 if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), *sorted)
94 || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), count))
95 goto err;
96
97 if (remove) {
98 while (remove-- > 0) {
99 i = test_random() % count;
100 if (values[i] != SIZE_MAX) {
101 if (!TEST_ptr_eq(ossl_pqueue_size_t_remove(pq, ref[i]),
102 values + i))
103 goto err;
104 values[i] = SIZE_MAX;
105 }
106 }
107 memcpy(sorted, values, sizeof(*sorted) * count);
108 qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
109 }
110 for (i = 0; ossl_pqueue_size_t_peek(pq) != NULL; i++)
111 if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), sorted[i])
112 || !TEST_size_t_eq(*ossl_pqueue_size_t_pop(pq), sorted[i]))
113 goto err;
114
115 if (popfree) {
116 num_rec_freed = 0;
117 n = ossl_pqueue_size_t_num(pq);
118 ossl_pqueue_size_t_pop_free(pq, &free_checker);
119 pq = NULL;
120 if (!TEST_size_t_eq(num_rec_freed, n))
121 goto err;
122 }
123 res = 1;
124 err:
125 ossl_pqueue_size_t_free(pq);
126 return res;
127 }
128
129 static const int test_size_t_priority_counts[] = {
130 10, 11, 6, 5, 3, 1, 2, 7500
131 };
132
test_size_t_priority_queue(int n)133 static int test_size_t_priority_queue(int n)
134 {
135 int reserve, order, count, remove, random, popfree;
136
137 count = n % OSSL_NELEM(test_size_t_priority_counts);
138 n /= OSSL_NELEM(test_size_t_priority_counts);
139 order = n % 3;
140 n /= 3;
141 random = n % 2;
142 n /= 2;
143 reserve = n % 2;
144 n /= 2;
145 remove = n % 6;
146 n /= 6;
147 popfree = n % 2;
148
149 count = test_size_t_priority_counts[count];
150 return test_size_t_priority_queue_int(reserve, order, count, remove,
151 random, popfree);
152 }
153
test_large_priority_queue(void)154 static int test_large_priority_queue(void)
155 {
156 return test_size_t_priority_queue_int(0, 0, MAX_SAMPLES, MAX_SAMPLES / 100,
157 1, 1);
158 }
159
160 typedef struct info_st {
161 uint64_t seq_num, sub_seq;
162 size_t idx;
163 } INFO;
164
165 DEFINE_PRIORITY_QUEUE_OF(INFO);
166
cmp(const INFO * a,const INFO * b)167 static int cmp(const INFO *a, const INFO *b)
168 {
169 if (a->seq_num < b->seq_num)
170 return -1;
171 if (a->seq_num > b->seq_num)
172 return 1;
173 if (a->sub_seq < b->sub_seq)
174 return -1;
175 if (a->sub_seq > b->sub_seq)
176 return 1;
177 return 0;
178 }
179
test_22644(void)180 static int test_22644(void)
181 {
182 size_t i;
183 INFO infos[32];
184 int res = 0;
185 PRIORITY_QUEUE_OF(INFO) *pq = ossl_pqueue_INFO_new(cmp);
186
187 memset(infos, 0, sizeof(infos));
188 for (i = 0; i < 32; ++i)
189 infos[i].sub_seq = i;
190
191 infos[0].seq_num = 70650219160667140;
192 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[0], &infos[0].idx))
193 || !TEST_size_t_eq(infos[0].idx, 7)
194 || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[0].idx)))
195 goto err;
196
197 infos[1].seq_num = 289360691352306692;
198 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[1], &infos[1].idx))
199 || !TEST_size_t_eq(infos[1].idx, 7)
200 || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[1].idx)))
201 goto err;
202
203 infos[2].seq_num = 289360691352306692;
204 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[2], &infos[2].idx))
205 || !TEST_size_t_eq(infos[2].idx, 7))
206 goto err;
207
208 infos[3].seq_num = 289360691352306692;
209 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[3], &infos[3].idx))
210 || !TEST_size_t_eq(infos[3].idx, 6))
211 goto err;
212
213 infos[4].seq_num = 289360691352306692;
214 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[4], &infos[4].idx))
215 || !TEST_size_t_eq(infos[4].idx, 5))
216 goto err;
217
218 infos[5].seq_num = 289360691352306692;
219 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[5], &infos[5].idx))
220 || !TEST_size_t_eq(infos[5].idx, 4))
221 goto err;
222
223 infos[6].seq_num = 289360691352306692;
224 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[6], &infos[6].idx))
225 || !TEST_size_t_eq(infos[6].idx, 3))
226 goto err;
227
228 infos[7].seq_num = 289360691352306692;
229 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[7], &infos[7].idx))
230 || !TEST_size_t_eq(infos[7].idx, 2))
231 goto err;
232
233 infos[8].seq_num = 289360691352306692;
234 if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[8], &infos[8].idx))
235 || !TEST_size_t_eq(infos[8].idx, 1))
236 goto err;
237
238 if (!TEST_ptr(ossl_pqueue_INFO_pop(pq))
239 || !TEST_ptr(ossl_pqueue_INFO_pop(pq))) /* crash if bug present */
240 goto err;
241 res = 1;
242
243 err:
244 ossl_pqueue_INFO_free(pq);
245 return res;
246 }
247
setup_tests(void)248 int setup_tests(void)
249 {
250 ADD_ALL_TESTS(test_size_t_priority_queue,
251 OSSL_NELEM(test_size_t_priority_counts) /* count */
252 * 3 /* order */
253 * 2 /* random */
254 * 2 /* reserve */
255 * 6 /* remove */
256 * 2); /* pop & free */
257 ADD_TEST(test_large_priority_queue);
258 ADD_TEST(test_22644);
259 return 1;
260 }
261
