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