Run util/openssl-format-source -v -c .
[openssl.git] / crypto / bn / bn_ctx.c
1 /* crypto/bn/bn_ctx.c */
2 /* Written by Ulf Moeller for the OpenSSL project. */
3 /* ====================================================================
4  * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  *
18  * 3. All advertising materials mentioning features or use of this
19  *    software must display the following acknowledgment:
20  *    "This product includes software developed by the OpenSSL Project
21  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22  *
23  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24  *    endorse or promote products derived from this software without
25  *    prior written permission. For written permission, please contact
26  *    openssl-core@openssl.org.
27  *
28  * 5. Products derived from this software may not be called "OpenSSL"
29  *    nor may "OpenSSL" appear in their names without prior written
30  *    permission of the OpenSSL Project.
31  *
32  * 6. Redistributions of any form whatsoever must retain the following
33  *    acknowledgment:
34  *    "This product includes software developed by the OpenSSL Project
35  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36  *
37  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48  * OF THE POSSIBILITY OF SUCH DAMAGE.
49  * ====================================================================
50  *
51  * This product includes cryptographic software written by Eric Young
52  * (eay@cryptsoft.com).  This product includes software written by Tim
53  * Hudson (tjh@cryptsoft.com).
54  *
55  */
56
57 #if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
58 # ifndef NDEBUG
59 #  define NDEBUG
60 # endif
61 #endif
62
63 #include <assert.h>
64
65 #include "cryptlib.h"
66 #include "bn_lcl.h"
67
68 /*-
69  * TODO list
70  *
71  * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
72  * check they can be safely removed.
73  *  - Check +1 and other ugliness in BN_from_montgomery()
74  *
75  * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
76  * appropriate 'block' size that will be honoured by bn_expand_internal() to
77  * prevent piddly little reallocations. OTOH, profiling bignum expansions in
78  * BN_CTX doesn't show this to be a big issue.
79  */
80
81 /* How many bignums are in each "pool item"; */
82 #define BN_CTX_POOL_SIZE        16
83 /* The stack frame info is resizing, set a first-time expansion size; */
84 #define BN_CTX_START_FRAMES     32
85
86 /***********/
87 /* BN_POOL */
88 /***********/
89
90 /* A bundle of bignums that can be linked with other bundles */
91 typedef struct bignum_pool_item {
92     /* The bignum values */
93     BIGNUM vals[BN_CTX_POOL_SIZE];
94     /* Linked-list admin */
95     struct bignum_pool_item *prev, *next;
96 } BN_POOL_ITEM;
97 /* A linked-list of bignums grouped in bundles */
98 typedef struct bignum_pool {
99     /* Linked-list admin */
100     BN_POOL_ITEM *head, *current, *tail;
101     /* Stack depth and allocation size */
102     unsigned used, size;
103 } BN_POOL;
104 static void BN_POOL_init(BN_POOL *);
105 static void BN_POOL_finish(BN_POOL *);
106 #ifndef OPENSSL_NO_DEPRECATED
107 static void BN_POOL_reset(BN_POOL *);
108 #endif
109 static BIGNUM *BN_POOL_get(BN_POOL *);
110 static void BN_POOL_release(BN_POOL *, unsigned int);
111
112 /************/
113 /* BN_STACK */
114 /************/
115
116 /* A wrapper to manage the "stack frames" */
117 typedef struct bignum_ctx_stack {
118     /* Array of indexes into the bignum stack */
119     unsigned int *indexes;
120     /* Number of stack frames, and the size of the allocated array */
121     unsigned int depth, size;
122 } BN_STACK;
123 static void BN_STACK_init(BN_STACK *);
124 static void BN_STACK_finish(BN_STACK *);
125 #ifndef OPENSSL_NO_DEPRECATED
126 static void BN_STACK_reset(BN_STACK *);
127 #endif
128 static int BN_STACK_push(BN_STACK *, unsigned int);
129 static unsigned int BN_STACK_pop(BN_STACK *);
130
131 /**********/
132 /* BN_CTX */
133 /**********/
134
135 /* The opaque BN_CTX type */
136 struct bignum_ctx {
137     /* The bignum bundles */
138     BN_POOL pool;
139     /* The "stack frames", if you will */
140     BN_STACK stack;
141     /* The number of bignums currently assigned */
142     unsigned int used;
143     /* Depth of stack overflow */
144     int err_stack;
145     /* Block "gets" until an "end" (compatibility behaviour) */
146     int too_many;
147 };
148
149 /* Enable this to find BN_CTX bugs */
150 #ifdef BN_CTX_DEBUG
151 static const char *ctxdbg_cur = NULL;
152 static void ctxdbg(BN_CTX *ctx)
153 {
154     unsigned int bnidx = 0, fpidx = 0;
155     BN_POOL_ITEM *item = ctx->pool.head;
156     BN_STACK *stack = &ctx->stack;
157     fprintf(stderr, "(%16p): ", ctx);
158     while (bnidx < ctx->used) {
159         fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
160         if (!(bnidx % BN_CTX_POOL_SIZE))
161             item = item->next;
162     }
163     fprintf(stderr, "\n");
164     bnidx = 0;
165     fprintf(stderr, "          : ");
166     while (fpidx < stack->depth) {
167         while (bnidx++ < stack->indexes[fpidx])
168             fprintf(stderr, "    ");
169         fprintf(stderr, "^^^ ");
170         bnidx++;
171         fpidx++;
172     }
173     fprintf(stderr, "\n");
174 }
175
176 # define CTXDBG_ENTRY(str, ctx)  do { \
177                                 ctxdbg_cur = (str); \
178                                 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
179                                 ctxdbg(ctx); \
180                                 } while(0)
181 # define CTXDBG_EXIT(ctx)        do { \
182                                 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
183                                 ctxdbg(ctx); \
184                                 } while(0)
185 # define CTXDBG_RET(ctx,ret)
186 #else
187 # define CTXDBG_ENTRY(str, ctx)
188 # define CTXDBG_EXIT(ctx)
189 # define CTXDBG_RET(ctx,ret)
190 #endif
191
192 /*
193  * This function is an evil legacy and should not be used. This
194  * implementation is WYSIWYG, though I've done my best.
195  */
196 #ifndef OPENSSL_NO_DEPRECATED
197 void BN_CTX_init(BN_CTX *ctx)
198 {
199     /*
200      * Assume the caller obtained the context via BN_CTX_new() and so is
201      * trying to reset it for use. Nothing else makes sense, least of all
202      * binary compatibility from a time when they could declare a static
203      * variable.
204      */
205     BN_POOL_reset(&ctx->pool);
206     BN_STACK_reset(&ctx->stack);
207     ctx->used = 0;
208     ctx->err_stack = 0;
209     ctx->too_many = 0;
210 }
211 #endif
212
213 BN_CTX *BN_CTX_new(void)
214 {
215     BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
216     if (!ret) {
217         BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
218         return NULL;
219     }
220     /* Initialise the structure */
221     BN_POOL_init(&ret->pool);
222     BN_STACK_init(&ret->stack);
223     ret->used = 0;
224     ret->err_stack = 0;
225     ret->too_many = 0;
226     return ret;
227 }
228
229 void BN_CTX_free(BN_CTX *ctx)
230 {
231     if (ctx == NULL)
232         return;
233 #ifdef BN_CTX_DEBUG
234     {
235         BN_POOL_ITEM *pool = ctx->pool.head;
236         fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
237                 ctx->stack.size, ctx->pool.size);
238         fprintf(stderr, "dmaxs: ");
239         while (pool) {
240             unsigned loop = 0;
241             while (loop < BN_CTX_POOL_SIZE)
242                 fprintf(stderr, "%02x ", pool->vals[loop++].dmax);
243             pool = pool->next;
244         }
245         fprintf(stderr, "\n");
246     }
247 #endif
248     BN_STACK_finish(&ctx->stack);
249     BN_POOL_finish(&ctx->pool);
250     OPENSSL_free(ctx);
251 }
252
253 void BN_CTX_start(BN_CTX *ctx)
254 {
255     CTXDBG_ENTRY("BN_CTX_start", ctx);
256     /* If we're already overflowing ... */
257     if (ctx->err_stack || ctx->too_many)
258         ctx->err_stack++;
259     /* (Try to) get a new frame pointer */
260     else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
261         BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
262         ctx->err_stack++;
263     }
264     CTXDBG_EXIT(ctx);
265 }
266
267 void BN_CTX_end(BN_CTX *ctx)
268 {
269     CTXDBG_ENTRY("BN_CTX_end", ctx);
270     if (ctx->err_stack)
271         ctx->err_stack--;
272     else {
273         unsigned int fp = BN_STACK_pop(&ctx->stack);
274         /* Does this stack frame have anything to release? */
275         if (fp < ctx->used)
276             BN_POOL_release(&ctx->pool, ctx->used - fp);
277         ctx->used = fp;
278         /* Unjam "too_many" in case "get" had failed */
279         ctx->too_many = 0;
280     }
281     CTXDBG_EXIT(ctx);
282 }
283
284 BIGNUM *BN_CTX_get(BN_CTX *ctx)
285 {
286     BIGNUM *ret;
287     CTXDBG_ENTRY("BN_CTX_get", ctx);
288     if (ctx->err_stack || ctx->too_many)
289         return NULL;
290     if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
291         /*
292          * Setting too_many prevents repeated "get" attempts from cluttering
293          * the error stack.
294          */
295         ctx->too_many = 1;
296         BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
297         return NULL;
298     }
299     /* OK, make sure the returned bignum is "zero" */
300     BN_zero(ret);
301     ctx->used++;
302     CTXDBG_RET(ctx, ret);
303     return ret;
304 }
305
306 /************/
307 /* BN_STACK */
308 /************/
309
310 static void BN_STACK_init(BN_STACK *st)
311 {
312     st->indexes = NULL;
313     st->depth = st->size = 0;
314 }
315
316 static void BN_STACK_finish(BN_STACK *st)
317 {
318     if (st->size)
319         OPENSSL_free(st->indexes);
320 }
321
322 #ifndef OPENSSL_NO_DEPRECATED
323 static void BN_STACK_reset(BN_STACK *st)
324 {
325     st->depth = 0;
326 }
327 #endif
328
329 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
330 {
331     if (st->depth == st->size)
332         /* Need to expand */
333     {
334         unsigned int newsize = (st->size ?
335                                 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
336         unsigned int *newitems = OPENSSL_malloc(newsize *
337                                                 sizeof(unsigned int));
338         if (!newitems)
339             return 0;
340         if (st->depth)
341             memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
342         if (st->size)
343             OPENSSL_free(st->indexes);
344         st->indexes = newitems;
345         st->size = newsize;
346     }
347     st->indexes[(st->depth)++] = idx;
348     return 1;
349 }
350
351 static unsigned int BN_STACK_pop(BN_STACK *st)
352 {
353     return st->indexes[--(st->depth)];
354 }
355
356 /***********/
357 /* BN_POOL */
358 /***********/
359
360 static void BN_POOL_init(BN_POOL *p)
361 {
362     p->head = p->current = p->tail = NULL;
363     p->used = p->size = 0;
364 }
365
366 static void BN_POOL_finish(BN_POOL *p)
367 {
368     while (p->head) {
369         unsigned int loop = 0;
370         BIGNUM *bn = p->head->vals;
371         while (loop++ < BN_CTX_POOL_SIZE) {
372             if (bn->d)
373                 BN_clear_free(bn);
374             bn++;
375         }
376         p->current = p->head->next;
377         OPENSSL_free(p->head);
378         p->head = p->current;
379     }
380 }
381
382 #ifndef OPENSSL_NO_DEPRECATED
383 static void BN_POOL_reset(BN_POOL *p)
384 {
385     BN_POOL_ITEM *item = p->head;
386     while (item) {
387         unsigned int loop = 0;
388         BIGNUM *bn = item->vals;
389         while (loop++ < BN_CTX_POOL_SIZE) {
390             if (bn->d)
391                 BN_clear(bn);
392             bn++;
393         }
394         item = item->next;
395     }
396     p->current = p->head;
397     p->used = 0;
398 }
399 #endif
400
401 static BIGNUM *BN_POOL_get(BN_POOL *p)
402 {
403     if (p->used == p->size) {
404         BIGNUM *bn;
405         unsigned int loop = 0;
406         BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
407         if (!item)
408             return NULL;
409         /* Initialise the structure */
410         bn = item->vals;
411         while (loop++ < BN_CTX_POOL_SIZE)
412             BN_init(bn++);
413         item->prev = p->tail;
414         item->next = NULL;
415         /* Link it in */
416         if (!p->head)
417             p->head = p->current = p->tail = item;
418         else {
419             p->tail->next = item;
420             p->tail = item;
421             p->current = item;
422         }
423         p->size += BN_CTX_POOL_SIZE;
424         p->used++;
425         /* Return the first bignum from the new pool */
426         return item->vals;
427     }
428     if (!p->used)
429         p->current = p->head;
430     else if ((p->used % BN_CTX_POOL_SIZE) == 0)
431         p->current = p->current->next;
432     return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
433 }
434
435 static void BN_POOL_release(BN_POOL *p, unsigned int num)
436 {
437     unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
438     p->used -= num;
439     while (num--) {
440         bn_check_top(p->current->vals + offset);
441         if (!offset) {
442             offset = BN_CTX_POOL_SIZE - 1;
443             p->current = p->current->prev;
444         } else
445             offset--;
446     }
447 }