2 * Copyright 2000-2021 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include <openssl/trace.h>
11 #include "internal/cryptlib.h"
14 /* How many bignums are in each "pool item"; */
15 #define BN_CTX_POOL_SIZE 16
16 /* The stack frame info is resizing, set a first-time expansion size; */
17 #define BN_CTX_START_FRAMES 32
23 /* A bundle of bignums that can be linked with other bundles */
24 typedef struct bignum_pool_item
{
25 /* The bignum values */
26 BIGNUM vals
[BN_CTX_POOL_SIZE
];
27 /* Linked-list admin */
28 struct bignum_pool_item
*prev
, *next
;
30 /* A linked-list of bignums grouped in bundles */
31 typedef struct bignum_pool
{
32 /* Linked-list admin */
33 BN_POOL_ITEM
*head
, *current
, *tail
;
34 /* Stack depth and allocation size */
37 static void BN_POOL_init(BN_POOL
*);
38 static void BN_POOL_finish(BN_POOL
*);
39 static BIGNUM
*BN_POOL_get(BN_POOL
*, int);
40 static void BN_POOL_release(BN_POOL
*, unsigned int);
46 /* A wrapper to manage the "stack frames" */
47 typedef struct bignum_ctx_stack
{
48 /* Array of indexes into the bignum stack */
49 unsigned int *indexes
;
50 /* Number of stack frames, and the size of the allocated array */
51 unsigned int depth
, size
;
53 static void BN_STACK_init(BN_STACK
*);
54 static void BN_STACK_finish(BN_STACK
*);
55 static int BN_STACK_push(BN_STACK
*, unsigned int);
56 static unsigned int BN_STACK_pop(BN_STACK
*);
62 /* The opaque BN_CTX type */
64 /* The bignum bundles */
66 /* The "stack frames", if you will */
68 /* The number of bignums currently assigned */
70 /* Depth of stack overflow */
72 /* Block "gets" until an "end" (compatibility behaviour) */
76 /* The library context */
81 /* Debugging functionality */
82 static void ctxdbg(BIO
*channel
, const char *text
, BN_CTX
*ctx
)
84 unsigned int bnidx
= 0, fpidx
= 0;
85 BN_POOL_ITEM
*item
= ctx
->pool
.head
;
86 BN_STACK
*stack
= &ctx
->stack
;
88 BIO_printf(channel
, "%s\n", text
);
89 BIO_printf(channel
, " (%16p): ", (void*)ctx
);
90 while (bnidx
< ctx
->used
) {
91 BIO_printf(channel
, "%03x ",
92 item
->vals
[bnidx
++ % BN_CTX_POOL_SIZE
].dmax
);
93 if (!(bnidx
% BN_CTX_POOL_SIZE
))
96 BIO_printf(channel
, "\n");
98 BIO_printf(channel
, " %16s : ", "");
99 while (fpidx
< stack
->depth
) {
100 while (bnidx
++ < stack
->indexes
[fpidx
])
101 BIO_printf(channel
, " ");
102 BIO_printf(channel
, "^^^ ");
106 BIO_printf(channel
, "\n");
109 # define CTXDBG(str, ctx) \
110 OSSL_TRACE_BEGIN(BN_CTX) { \
111 ctxdbg(trc_out, str, ctx); \
112 } OSSL_TRACE_END(BN_CTX)
114 /* We do not want tracing in FIPS module */
115 # define CTXDBG(str, ctx) do {} while(0)
116 #endif /* FIPS_MODULE */
118 BN_CTX
*BN_CTX_new_ex(OSSL_LIB_CTX
*ctx
)
122 if ((ret
= OPENSSL_zalloc(sizeof(*ret
))) == NULL
)
124 /* Initialise the structure */
125 BN_POOL_init(&ret
->pool
);
126 BN_STACK_init(&ret
->stack
);
132 BN_CTX
*BN_CTX_new(void)
134 return BN_CTX_new_ex(NULL
);
138 BN_CTX
*BN_CTX_secure_new_ex(OSSL_LIB_CTX
*ctx
)
140 BN_CTX
*ret
= BN_CTX_new_ex(ctx
);
143 ret
->flags
= BN_FLG_SECURE
;
148 BN_CTX
*BN_CTX_secure_new(void)
150 return BN_CTX_secure_new_ex(NULL
);
154 void BN_CTX_free(BN_CTX
*ctx
)
159 OSSL_TRACE_BEGIN(BN_CTX
) {
160 BN_POOL_ITEM
*pool
= ctx
->pool
.head
;
162 "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n",
163 ctx
->stack
.size
, ctx
->pool
.size
);
164 BIO_printf(trc_out
, " dmaxs: ");
167 while (loop
< BN_CTX_POOL_SIZE
)
168 BIO_printf(trc_out
, "%02x ", pool
->vals
[loop
++].dmax
);
171 BIO_printf(trc_out
, "\n");
172 } OSSL_TRACE_END(BN_CTX
);
174 BN_STACK_finish(&ctx
->stack
);
175 BN_POOL_finish(&ctx
->pool
);
179 void BN_CTX_start(BN_CTX
*ctx
)
181 CTXDBG("ENTER BN_CTX_start()", ctx
);
182 /* If we're already overflowing ... */
183 if (ctx
->err_stack
|| ctx
->too_many
)
185 /* (Try to) get a new frame pointer */
186 else if (!BN_STACK_push(&ctx
->stack
, ctx
->used
)) {
187 ERR_raise(ERR_LIB_BN
, BN_R_TOO_MANY_TEMPORARY_VARIABLES
);
190 CTXDBG("LEAVE BN_CTX_start()", ctx
);
193 void BN_CTX_end(BN_CTX
*ctx
)
197 CTXDBG("ENTER BN_CTX_end()", ctx
);
201 unsigned int fp
= BN_STACK_pop(&ctx
->stack
);
202 /* Does this stack frame have anything to release? */
204 BN_POOL_release(&ctx
->pool
, ctx
->used
- fp
);
206 /* Unjam "too_many" in case "get" had failed */
209 CTXDBG("LEAVE BN_CTX_end()", ctx
);
212 BIGNUM
*BN_CTX_get(BN_CTX
*ctx
)
216 CTXDBG("ENTER BN_CTX_get()", ctx
);
217 if (ctx
->err_stack
|| ctx
->too_many
)
219 if ((ret
= BN_POOL_get(&ctx
->pool
, ctx
->flags
)) == NULL
) {
221 * Setting too_many prevents repeated "get" attempts from cluttering
225 ERR_raise(ERR_LIB_BN
, BN_R_TOO_MANY_TEMPORARY_VARIABLES
);
228 /* OK, make sure the returned bignum is "zero" */
230 /* clear BN_FLG_CONSTTIME if leaked from previous frames */
231 ret
->flags
&= (~BN_FLG_CONSTTIME
);
233 CTXDBG("LEAVE BN_CTX_get()", ctx
);
237 OSSL_LIB_CTX
*ossl_bn_get_libctx(BN_CTX
*ctx
)
248 static void BN_STACK_init(BN_STACK
*st
)
251 st
->depth
= st
->size
= 0;
254 static void BN_STACK_finish(BN_STACK
*st
)
256 OPENSSL_free(st
->indexes
);
261 static int BN_STACK_push(BN_STACK
*st
, unsigned int idx
)
263 if (st
->depth
== st
->size
) {
265 unsigned int newsize
=
266 st
->size
? (st
->size
* 3 / 2) : BN_CTX_START_FRAMES
;
267 unsigned int *newitems
;
269 if ((newitems
= OPENSSL_malloc(sizeof(*newitems
) * newsize
)) == NULL
)
272 memcpy(newitems
, st
->indexes
, sizeof(*newitems
) * st
->depth
);
273 OPENSSL_free(st
->indexes
);
274 st
->indexes
= newitems
;
277 st
->indexes
[(st
->depth
)++] = idx
;
281 static unsigned int BN_STACK_pop(BN_STACK
*st
)
283 return st
->indexes
[--(st
->depth
)];
290 static void BN_POOL_init(BN_POOL
*p
)
292 p
->head
= p
->current
= p
->tail
= NULL
;
293 p
->used
= p
->size
= 0;
296 static void BN_POOL_finish(BN_POOL
*p
)
302 for (loop
= 0, bn
= p
->head
->vals
; loop
++ < BN_CTX_POOL_SIZE
; bn
++)
305 p
->current
= p
->head
->next
;
306 OPENSSL_free(p
->head
);
307 p
->head
= p
->current
;
312 static BIGNUM
*BN_POOL_get(BN_POOL
*p
, int flag
)
317 /* Full; allocate a new pool item and link it in. */
318 if (p
->used
== p
->size
) {
321 if ((item
= OPENSSL_malloc(sizeof(*item
))) == NULL
)
323 for (loop
= 0, bn
= item
->vals
; loop
++ < BN_CTX_POOL_SIZE
; bn
++) {
325 if ((flag
& BN_FLG_SECURE
) != 0)
326 BN_set_flags(bn
, BN_FLG_SECURE
);
328 item
->prev
= p
->tail
;
332 p
->head
= p
->current
= p
->tail
= item
;
334 p
->tail
->next
= item
;
338 p
->size
+= BN_CTX_POOL_SIZE
;
340 /* Return the first bignum from the new pool */
345 p
->current
= p
->head
;
346 else if ((p
->used
% BN_CTX_POOL_SIZE
) == 0)
347 p
->current
= p
->current
->next
;
348 return p
->current
->vals
+ ((p
->used
++) % BN_CTX_POOL_SIZE
);
351 static void BN_POOL_release(BN_POOL
*p
, unsigned int num
)
353 unsigned int offset
= (p
->used
- 1) % BN_CTX_POOL_SIZE
;
357 bn_check_top(p
->current
->vals
+ offset
);
359 offset
= BN_CTX_POOL_SIZE
- 1;
360 p
->current
= p
->current
->prev
;