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 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 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 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 46 static void free_checker(ossl_unused size_t *p) 47 { 48 num_rec_freed++; 49 } 50 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 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 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 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 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 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