bn_ctx.c revision 296465 
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 <stdio.h>
64#include <assert.h>
65
66#include "cryptlib.h"
67#include "bn_lcl.h"
68
69/*-
70 * TODO list
71 *
72 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
73 * check they can be safely removed.
74 *  - Check +1 and other ugliness in BN_from_montgomery()
75 *
76 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
77 * appropriate 'block' size that will be honoured by bn_expand_internal() to
78 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
79 * BN_CTX doesn't show this to be a big issue.
80 */
81
82/* How many bignums are in each "pool item"; */
83#define BN_CTX_POOL_SIZE        16
84/* The stack frame info is resizing, set a first-time expansion size; */
85#define BN_CTX_START_FRAMES     32
86
87/***********/
88/* BN_POOL */
89/***********/
90
91/* A bundle of bignums that can be linked with other bundles */
92typedef struct bignum_pool_item {
93    /* The bignum values */
94    BIGNUM vals[BN_CTX_POOL_SIZE];
95    /* Linked-list admin */
96    struct bignum_pool_item *prev, *next;
97} BN_POOL_ITEM;
98/* A linked-list of bignums grouped in bundles */
99typedef struct bignum_pool {
100    /* Linked-list admin */
101    BN_POOL_ITEM *head, *current, *tail;
102    /* Stack depth and allocation size */
103    unsigned used, size;
104} BN_POOL;
105static void BN_POOL_init(BN_POOL *);
106static void BN_POOL_finish(BN_POOL *);
107#ifndef OPENSSL_NO_DEPRECATED
108static void BN_POOL_reset(BN_POOL *);
109#endif
110static BIGNUM *BN_POOL_get(BN_POOL *);
111static void BN_POOL_release(BN_POOL *, unsigned int);
112
113/************/
114/* BN_STACK */
115/************/
116
117/* A wrapper to manage the "stack frames" */
118typedef struct bignum_ctx_stack {
119    /* Array of indexes into the bignum stack */
120    unsigned int *indexes;
121    /* Number of stack frames, and the size of the allocated array */
122    unsigned int depth, size;
123} BN_STACK;
124static void BN_STACK_init(BN_STACK *);
125static void BN_STACK_finish(BN_STACK *);
126#ifndef OPENSSL_NO_DEPRECATED
127static void BN_STACK_reset(BN_STACK *);
128#endif
129static int BN_STACK_push(BN_STACK *, unsigned int);
130static unsigned int BN_STACK_pop(BN_STACK *);
131
132/**********/
133/* BN_CTX */
134/**********/
135
136/* The opaque BN_CTX type */
137struct bignum_ctx {
138    /* The bignum bundles */
139    BN_POOL pool;
140    /* The "stack frames", if you will */
141    BN_STACK stack;
142    /* The number of bignums currently assigned */
143    unsigned int used;
144    /* Depth of stack overflow */
145    int err_stack;
146    /* Block "gets" until an "end" (compatibility behaviour) */
147    int too_many;
148};
149
150/* Enable this to find BN_CTX bugs */
151#ifdef BN_CTX_DEBUG
152static const char *ctxdbg_cur = NULL;
153static void ctxdbg(BN_CTX *ctx)
154{
155    unsigned int bnidx = 0, fpidx = 0;
156    BN_POOL_ITEM *item = ctx->pool.head;
157    BN_STACK *stack = &ctx->stack;
158    fprintf(stderr, "(%08x): ", (unsigned int)ctx);
159    while (bnidx < ctx->used) {
160        fprintf(stderr, "%02x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
161        if (!(bnidx % BN_CTX_POOL_SIZE))
162            item = item->next;
163    }
164    fprintf(stderr, "\n");
165    bnidx = 0;
166    fprintf(stderr, "          : ");
167    while (fpidx < stack->depth) {
168        while (bnidx++ < stack->indexes[fpidx])
169            fprintf(stderr, "   ");
170        fprintf(stderr, "^^ ");
171        bnidx++;
172        fpidx++;
173    }
174    fprintf(stderr, "\n");
175}
176
177# define CTXDBG_ENTRY(str, ctx)  do { \
178                                ctxdbg_cur = (str); \
179                                fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
180                                ctxdbg(ctx); \
181                                } while(0)
182# define CTXDBG_EXIT(ctx)        do { \
183                                fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
184                                ctxdbg(ctx); \
185                                } while(0)
186# define CTXDBG_RET(ctx,ret)
187#else
188# define CTXDBG_ENTRY(str, ctx)
189# define CTXDBG_EXIT(ctx)
190# define CTXDBG_RET(ctx,ret)
191#endif
192
193/*
194 * This function is an evil legacy and should not be used. This
195 * implementation is WYSIWYG, though I've done my best.
196 */
197#ifndef OPENSSL_NO_DEPRECATED
198void BN_CTX_init(BN_CTX *ctx)
199{
200    /*
201     * Assume the caller obtained the context via BN_CTX_new() and so is
202     * trying to reset it for use. Nothing else makes sense, least of all
203     * binary compatibility from a time when they could declare a static
204     * variable.
205     */
206    BN_POOL_reset(&ctx->pool);
207    BN_STACK_reset(&ctx->stack);
208    ctx->used = 0;
209    ctx->err_stack = 0;
210    ctx->too_many = 0;
211}
212#endif
213
214BN_CTX *BN_CTX_new(void)
215{
216    BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
217    if (!ret) {
218        BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
219        return NULL;
220    }
221    /* Initialise the structure */
222    BN_POOL_init(&ret->pool);
223    BN_STACK_init(&ret->stack);
224    ret->used = 0;
225    ret->err_stack = 0;
226    ret->too_many = 0;
227    return ret;
228}
229
230void BN_CTX_free(BN_CTX *ctx)
231{
232    if (ctx == NULL)
233        return;
234#ifdef BN_CTX_DEBUG
235    {
236        BN_POOL_ITEM *pool = ctx->pool.head;
237        fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
238                ctx->stack.size, ctx->pool.size);
239        fprintf(stderr, "dmaxs: ");
240        while (pool) {
241            unsigned loop = 0;
242            while (loop < BN_CTX_POOL_SIZE)
243                fprintf(stderr, "%02x ", pool->vals[loop++].dmax);
244            pool = pool->next;
245        }
246        fprintf(stderr, "\n");
247    }
248#endif
249    BN_STACK_finish(&ctx->stack);
250    BN_POOL_finish(&ctx->pool);
251    OPENSSL_free(ctx);
252}
253
254void BN_CTX_start(BN_CTX *ctx)
255{
256    CTXDBG_ENTRY("BN_CTX_start", ctx);
257    /* If we're already overflowing ... */
258    if (ctx->err_stack || ctx->too_many)
259        ctx->err_stack++;
260    /* (Try to) get a new frame pointer */
261    else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
262        BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
263        ctx->err_stack++;
264    }
265    CTXDBG_EXIT(ctx);
266}
267
268void BN_CTX_end(BN_CTX *ctx)
269{
270    CTXDBG_ENTRY("BN_CTX_end", ctx);
271    if (ctx->err_stack)
272        ctx->err_stack--;
273    else {
274        unsigned int fp = BN_STACK_pop(&ctx->stack);
275        /* Does this stack frame have anything to release? */
276        if (fp < ctx->used)
277            BN_POOL_release(&ctx->pool, ctx->used - fp);
278        ctx->used = fp;
279        /* Unjam "too_many" in case "get" had failed */
280        ctx->too_many = 0;
281    }
282    CTXDBG_EXIT(ctx);
283}
284
285BIGNUM *BN_CTX_get(BN_CTX *ctx)
286{
287    BIGNUM *ret;
288    CTXDBG_ENTRY("BN_CTX_get", ctx);
289    if (ctx->err_stack || ctx->too_many)
290        return NULL;
291    if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
292        /*
293         * Setting too_many prevents repeated "get" attempts from cluttering
294         * the error stack.
295         */
296        ctx->too_many = 1;
297        BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
298        return NULL;
299    }
300    /* OK, make sure the returned bignum is "zero" */
301    BN_zero(ret);
302    ctx->used++;
303    CTXDBG_RET(ctx, ret);
304    return ret;
305}
306
307/************/
308/* BN_STACK */
309/************/
310
311static void BN_STACK_init(BN_STACK *st)
312{
313    st->indexes = NULL;
314    st->depth = st->size = 0;
315}
316
317static void BN_STACK_finish(BN_STACK *st)
318{
319    if (st->size)
320        OPENSSL_free(st->indexes);
321}
322
323#ifndef OPENSSL_NO_DEPRECATED
324static void BN_STACK_reset(BN_STACK *st)
325{
326    st->depth = 0;
327}
328#endif
329
330static int BN_STACK_push(BN_STACK *st, unsigned int idx)
331{
332    if (st->depth == st->size)
333        /* Need to expand */
334    {
335        unsigned int newsize = (st->size ?
336                                (st->size * 3 / 2) : BN_CTX_START_FRAMES);
337        unsigned int *newitems = OPENSSL_malloc(newsize *
338                                                sizeof(unsigned int));
339        if (!newitems)
340            return 0;
341        if (st->depth)
342            memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
343        if (st->size)
344            OPENSSL_free(st->indexes);
345        st->indexes = newitems;
346        st->size = newsize;
347    }
348    st->indexes[(st->depth)++] = idx;
349    return 1;
350}
351
352static unsigned int BN_STACK_pop(BN_STACK *st)
353{
354    return st->indexes[--(st->depth)];
355}
356
357/***********/
358/* BN_POOL */
359/***********/
360
361static void BN_POOL_init(BN_POOL *p)
362{
363    p->head = p->current = p->tail = NULL;
364    p->used = p->size = 0;
365}
366
367static void BN_POOL_finish(BN_POOL *p)
368{
369    while (p->head) {
370        unsigned int loop = 0;
371        BIGNUM *bn = p->head->vals;
372        while (loop++ < BN_CTX_POOL_SIZE) {
373            if (bn->d)
374                BN_clear_free(bn);
375            bn++;
376        }
377        p->current = p->head->next;
378        OPENSSL_free(p->head);
379        p->head = p->current;
380    }
381}
382
383#ifndef OPENSSL_NO_DEPRECATED
384static void BN_POOL_reset(BN_POOL *p)
385{
386    BN_POOL_ITEM *item = p->head;
387    while (item) {
388        unsigned int loop = 0;
389        BIGNUM *bn = item->vals;
390        while (loop++ < BN_CTX_POOL_SIZE) {
391            if (bn->d)
392                BN_clear(bn);
393            bn++;
394        }
395        item = item->next;
396    }
397    p->current = p->head;
398    p->used = 0;
399}
400#endif
401
402static BIGNUM *BN_POOL_get(BN_POOL *p)
403{
404    if (p->used == p->size) {
405        BIGNUM *bn;
406        unsigned int loop = 0;
407        BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
408        if (!item)
409            return NULL;
410        /* Initialise the structure */
411        bn = item->vals;
412        while (loop++ < BN_CTX_POOL_SIZE)
413            BN_init(bn++);
414        item->prev = p->tail;
415        item->next = NULL;
416        /* Link it in */
417        if (!p->head)
418            p->head = p->current = p->tail = item;
419        else {
420            p->tail->next = item;
421            p->tail = item;
422            p->current = item;
423        }
424        p->size += BN_CTX_POOL_SIZE;
425        p->used++;
426        /* Return the first bignum from the new pool */
427        return item->vals;
428    }
429    if (!p->used)
430        p->current = p->head;
431    else if ((p->used % BN_CTX_POOL_SIZE) == 0)
432        p->current = p->current->next;
433    return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
434}
435
436static void BN_POOL_release(BN_POOL *p, unsigned int num)
437{
438    unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
439    p->used -= num;
440    while (num--) {
441        bn_check_top(p->current->vals + offset);
442        if (!offset) {
443            offset = BN_CTX_POOL_SIZE - 1;
444            p->current = p->current->prev;
445        } else
446            offset--;
447    }
448}
449