sparse_array.c 6.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220
  1. /*
  2. * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
  3. * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
  4. *
  5. * Licensed under the Apache License 2.0 (the "License"). You may not use
  6. * this file except in compliance with the License. You can obtain a copy
  7. * in the file LICENSE in the source distribution or at
  8. * https://www.openssl.org/source/license.html
  9. */
  10. #include <openssl/crypto.h>
  11. #include <openssl/bn.h>
  12. #include "crypto/sparse_array.h"
  13. /*
  14. * How many bits are used to index each level in the tree structure?
  15. * This setting determines the number of pointers stored in each node of the
  16. * tree used to represent the sparse array. Having more pointers reduces the
  17. * depth of the tree but potentially wastes more memory. That is, this is a
  18. * direct space versus time tradeoff.
  19. *
  20. * The large memory model uses twelve bits which means that the are 4096
  21. * pointers in each tree node. This is more than sufficient to hold the
  22. * largest defined NID (as of Feb 2019). This means that using a NID to
  23. * index a sparse array becomes a constant time single array look up.
  24. *
  25. * The small memory model uses four bits which means the tree nodes contain
  26. * sixteen pointers. This reduces the amount of unused space significantly
  27. * at a cost in time.
  28. *
  29. * The library builder is also permitted to define other sizes in the closed
  30. * interval [2, sizeof(ossl_uintmax_t) * 8].
  31. */
  32. #ifndef OPENSSL_SA_BLOCK_BITS
  33. # ifdef OPENSSL_SMALL_FOOTPRINT
  34. # define OPENSSL_SA_BLOCK_BITS 4
  35. # else
  36. # define OPENSSL_SA_BLOCK_BITS 12
  37. # endif
  38. #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
  39. # error OPENSSL_SA_BLOCK_BITS is out of range
  40. #endif
  41. /*
  42. * From the number of bits, work out:
  43. * the number of pointers in a tree node;
  44. * a bit mask to quickly extract an index and
  45. * the maximum depth of the tree structure.
  46. */
  47. #define SA_BLOCK_MAX (1 << OPENSSL_SA_BLOCK_BITS)
  48. #define SA_BLOCK_MASK (SA_BLOCK_MAX - 1)
  49. #define SA_BLOCK_MAX_LEVELS (((int)sizeof(ossl_uintmax_t) * 8 \
  50. + OPENSSL_SA_BLOCK_BITS - 1) \
  51. / OPENSSL_SA_BLOCK_BITS)
  52. struct sparse_array_st {
  53. int levels;
  54. ossl_uintmax_t top;
  55. size_t nelem;
  56. void **nodes;
  57. };
  58. OPENSSL_SA *OPENSSL_SA_new(void)
  59. {
  60. OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
  61. return res;
  62. }
  63. static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
  64. void (*leaf)(ossl_uintmax_t, void *, void *), void *arg)
  65. {
  66. int i[SA_BLOCK_MAX_LEVELS];
  67. void *nodes[SA_BLOCK_MAX_LEVELS];
  68. ossl_uintmax_t idx = 0;
  69. int l = 0;
  70. i[0] = 0;
  71. nodes[0] = sa->nodes;
  72. while (l >= 0) {
  73. const int n = i[l];
  74. void ** const p = nodes[l];
  75. if (n >= SA_BLOCK_MAX) {
  76. if (p != NULL && node != NULL)
  77. (*node)(p);
  78. l--;
  79. idx >>= OPENSSL_SA_BLOCK_BITS;
  80. } else {
  81. i[l] = n + 1;
  82. if (p != NULL && p[n] != NULL) {
  83. idx = (idx & ~SA_BLOCK_MASK) | n;
  84. if (l < sa->levels - 1) {
  85. i[++l] = 0;
  86. nodes[l] = p[n];
  87. idx <<= OPENSSL_SA_BLOCK_BITS;
  88. } else if (leaf != NULL) {
  89. (*leaf)(idx, p[n], arg);
  90. }
  91. }
  92. }
  93. }
  94. }
  95. static void sa_free_node(void **p)
  96. {
  97. OPENSSL_free(p);
  98. }
  99. static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
  100. {
  101. OPENSSL_free(p);
  102. }
  103. void OPENSSL_SA_free(OPENSSL_SA *sa)
  104. {
  105. sa_doall(sa, &sa_free_node, NULL, NULL);
  106. OPENSSL_free(sa);
  107. }
  108. void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
  109. {
  110. sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
  111. OPENSSL_free(sa);
  112. }
  113. /* Wrap this in a structure to avoid compiler warnings */
  114. struct trampoline_st {
  115. void (*func)(ossl_uintmax_t, void *);
  116. };
  117. static void trampoline(ossl_uintmax_t n, void *l, void *arg)
  118. {
  119. ((const struct trampoline_st *)arg)->func(n, l);
  120. }
  121. void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t,
  122. void *))
  123. {
  124. struct trampoline_st tramp;
  125. tramp.func = leaf;
  126. if (sa != NULL)
  127. sa_doall(sa, NULL, &trampoline, &tramp);
  128. }
  129. void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
  130. void (*leaf)(ossl_uintmax_t, void *, void *),
  131. void *arg)
  132. {
  133. if (sa != NULL)
  134. sa_doall(sa, NULL, leaf, arg);
  135. }
  136. size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
  137. {
  138. return sa == NULL ? 0 : sa->nelem;
  139. }
  140. void *OPENSSL_SA_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
  141. {
  142. int level;
  143. void **p, *r = NULL;
  144. if (sa == NULL)
  145. return NULL;
  146. if (n <= sa->top) {
  147. p = sa->nodes;
  148. for (level = sa->levels - 1; p != NULL && level > 0; level--)
  149. p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
  150. & SA_BLOCK_MASK];
  151. r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
  152. }
  153. return r;
  154. }
  155. static ossl_inline void **alloc_node(void)
  156. {
  157. return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
  158. }
  159. int OPENSSL_SA_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
  160. {
  161. int i, level = 1;
  162. ossl_uintmax_t n = posn;
  163. void **p;
  164. if (sa == NULL)
  165. return 0;
  166. for (level = 1; level < SA_BLOCK_MAX_LEVELS; level++)
  167. if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
  168. break;
  169. for (;sa->levels < level; sa->levels++) {
  170. p = alloc_node();
  171. if (p == NULL)
  172. return 0;
  173. p[0] = sa->nodes;
  174. sa->nodes = p;
  175. }
  176. if (sa->top < posn)
  177. sa->top = posn;
  178. p = sa->nodes;
  179. for (level = sa->levels - 1; level > 0; level--) {
  180. i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
  181. if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
  182. return 0;
  183. p = p[i];
  184. }
  185. p += posn & SA_BLOCK_MASK;
  186. if (val == NULL && *p != NULL)
  187. sa->nelem--;
  188. else if (val != NULL && *p == NULL)
  189. sa->nelem++;
  190. *p = val;
  191. return 1;
  192. }