Replace the BN_CTX implementation with my current work. I'm leaving the
authorGeoff Thorpe <geoff@openssl.org>
Thu, 25 Mar 2004 04:16:14 +0000 (04:16 +0000)
committerGeoff Thorpe <geoff@openssl.org>
Thu, 25 Mar 2004 04:16:14 +0000 (04:16 +0000)
little TODO list in there as well as the debugging code (only enabled if
BN_CTX_DEBUG is defined).

I'd appreciate as much review and testing as can be spared for this. I'll
commit some changes to other parts of the bignum code shortly to make
better use of this implementation (no more fixed size limitations). Note
also that under identical optimisations, I'm seeing a noticable speed
increase over openssl-0.9.7 - so any feedback to confirm/deny this on other
systems would also be most welcome.

CHANGES
crypto/bn/bn_ctx.c

diff --git a/CHANGES b/CHANGES
index 6eceeba..b65a37a 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,15 @@
 
  Changes between 0.9.7c and 0.9.8  [xx XXX xxxx]
 
+  *) Reimplemented the BN_CTX implementation. There is now no more static
+     limitation on the number of variables it can handle nor the depth of the
+     "stack" handling for BN_CTX_start()/BN_CTX_end() pairs. The stack
+     information can now expand as required, and rather than having a single
+     static array of bignums, BN_CTX now uses a linked-list of such arrays
+     allowing it to expand on demand whilst maintaining the usefulness of
+     BN_CTX's "bundling".
+     [Geoff Thorpe]
+
   *) Add a missing BN_CTX parameter to the 'rsa_mod_exp' callback in RSA_METHOD
      to allow all RSA operations to function using a single BN_CTX.
      [Geoff Thorpe]
index f48055b..5aec0c9 100644 (file)
@@ -1,7 +1,7 @@
 /* crypto/bn/bn_ctx.c */
 /* Written by Ulf Moeller for the OpenSSL project. */
 /* ====================================================================
- * Copyright (c) 1998-2000 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #include "cryptlib.h"
 #include "bn_lcl.h"
 
-/* BN_CTX structure details */
-#define BN_CTX_NUM     32
-#define BN_CTX_NUM_POS 12
+/* TODO list
+ *
+ * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
+ * check they can be safely removed.
+ *  - BN_bin2bn() looks pretty nasty with the miscellaneous +1 and +2 adjustments.
+ *    Needs a full rubber-gloving, me thinks.
+ *  - Check +1 and other ugliness in BN_from_montgomery()
+ *  - Aspects of BN_bn2dec() also look a bit arbitrary
+ *
+ * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
+ * appropriate 'block' size that will be honoured by bn_expand_internal() to
+ * prevent piddly little reallocations. OTOH, profiling bignum expansions in
+ * BN_CTX doesn't show this to be a big issue.
+ */
+
+/* How many bignums are in each "pool item"; */
+#define BN_CTX_POOL_SIZE       16
+/* The stack frame info is resizing, set a first-time expansion size; */
+#define BN_CTX_START_FRAMES    32
+
+/***********/
+/* BN_POOL */
+/***********/
+
+/* A bundle of bignums that can be linked with other bundles */
+typedef struct bignum_pool_item
+       {
+       /* The bignum values */
+       BIGNUM vals[BN_CTX_POOL_SIZE];
+       /* Linked-list admin */
+       struct bignum_pool_item *prev, *next;
+       } BN_POOL_ITEM;
+/* A linked-list of bignums grouped in bundles */
+typedef struct bignum_pool
+       {
+       /* Linked-list admin */
+       BN_POOL_ITEM *head, *current, *tail;
+       /* Stack depth and allocation size */
+       unsigned used, size;
+       } BN_POOL;
+static void            BN_POOL_init(BN_POOL *);
+static void            BN_POOL_finish(BN_POOL *);
+#ifndef OPENSSL_NO_DEPRECATED
+static void            BN_POOL_reset(BN_POOL *);
+#endif
+static BIGNUM *                BN_POOL_get(BN_POOL *);
+static void            BN_POOL_release(BN_POOL *, unsigned int);
+
+/************/
+/* BN_STACK */
+/************/
+
+/* A wrapper to manage the "stack frames" */
+typedef struct bignum_ctx_stack
+       {
+       /* Array of indexes into the bignum stack */
+       unsigned int *indexes;
+       /* Number of stack frames, and the size of the allocated array */
+       unsigned int depth, size;
+       } BN_STACK;
+static void            BN_STACK_init(BN_STACK *);
+static void            BN_STACK_finish(BN_STACK *);
+#ifndef OPENSSL_NO_DEPRECATED
+static void            BN_STACK_reset(BN_STACK *);
+#endif
+static int             BN_STACK_push(BN_STACK *, unsigned int);
+static unsigned int    BN_STACK_pop(BN_STACK *);
+
+/**********/
+/* BN_CTX */
+/**********/
+
+/* The opaque BN_CTX type */
 struct bignum_ctx
        {
-       int tos;
-       BIGNUM bn[BN_CTX_NUM];
-       int flags;
-       int depth;
-       int pos[BN_CTX_NUM_POS];
+       /* The bignum bundles */
+       BN_POOL pool;
+       /* The "stack frames", if you will */
+       BN_STACK stack;
+       /* The number of bignums currently assigned */
+       unsigned int used;
+       /* Depth of stack overflow */
+       int err_stack;
+       /* Block "gets" until an "end" (compatibility behaviour) */
        int too_many;
        };
 
-#ifndef OPENSSL_NO_DEPRECATED
-void BN_CTX_init(BN_CTX *ctx)
+/* Enable this to find BN_CTX bugs */
+#ifdef BN_CTX_DEBUG
+static const char *ctxdbg_cur = NULL;
+static void ctxdbg(BN_CTX *ctx)
+       {
+       unsigned int bnidx = 0, fpidx = 0;
+       BN_POOL_ITEM *item = ctx->pool.head;
+       BN_STACK *stack = &ctx->stack;
+       printf("(%08x): ", (unsigned int)ctx);
+       while(bnidx < ctx->used)
+               {
+               printf("%02x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
+               if(!(bnidx % BN_CTX_POOL_SIZE))
+                       item = item->next;
+               }
+       printf("\n");
+       bnidx = 0;
+       printf("          : ");
+       while(fpidx < stack->depth)
+               {
+               while(bnidx++ < stack->indexes[fpidx])
+                       printf("   ");
+               printf("^^ ");
+               bnidx++;
+               fpidx++;
+               }
+       printf("\n");
+       }
+#define CTXDBG_ENTRY(str, ctx) do { \
+                               ctxdbg_cur = (str); \
+                               printf("Starting %s\n", ctxdbg_cur); \
+                               ctxdbg(ctx); \
+                               } while(0)
+#define CTXDBG_EXIT(ctx)       do { \
+                               printf("Ending %s\n", ctxdbg_cur); \
+                               ctxdbg(ctx); \
+                               } while(0)
+#define CTXDBG_RET(ctx,ret)
 #else
-static void BN_CTX_init(BN_CTX *ctx)
+#define CTXDBG_ENTRY(str, ctx)
+#define CTXDBG_EXIT(ctx)
+#define CTXDBG_RET(ctx,ret)
 #endif
+
+/* This function is an evil legacy and should not be used. This implementation
+ * is WYSIWYG, though I've done my best. */
+#ifndef OPENSSL_NO_DEPRECATED
+void BN_CTX_init(BN_CTX *ctx)
        {
-#if 0 /* explicit version */
-       int i;
-       ctx->tos = 0;
-       ctx->flags = 0;
-       ctx->depth = 0;
+       /* Assume the caller obtained the context via BN_CTX_new() and so is
+        * trying to reset it for use. Nothing else makes sense, least of all
+        * binary compatibility from a time when they could declare a static
+        * variable. */
+       BN_POOL_reset(&ctx->pool);
+       BN_STACK_reset(&ctx->stack);
+       ctx->used = 0;
+       ctx->err_stack = 0;
        ctx->too_many = 0;
-       for (i = 0; i < BN_CTX_NUM; i++)
-               BN_init(&(ctx->bn[i]));
-#else
-       memset(ctx, 0, sizeof *ctx);
-#endif
        }
+#endif
 
 BN_CTX *BN_CTX_new(void)
        {
-       BN_CTX *ret;
-
-       ret=(BN_CTX *)OPENSSL_malloc(sizeof(BN_CTX));
-       if (ret == NULL)
+       BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
+       if(!ret)
                {
                BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
-               return(NULL);
+               return NULL;
                }
-
-       BN_CTX_init(ret);
-       ret->flags=BN_FLG_MALLOCED;
-       return(ret);
+       /* Initialise the structure */
+       BN_POOL_init(&ret->pool);
+       BN_STACK_init(&ret->stack);
+       ret->used = 0;
+       ret->err_stack = 0;
+       ret->too_many = 0;
+       return ret;
        }
 
 void BN_CTX_free(BN_CTX *ctx)
        {
-       int i;
-
-       if (ctx == NULL) return;
-       assert(ctx->depth == 0);
-
-       for (i=0; i < BN_CTX_NUM; i++) {
-               bn_check_top(&(ctx->bn[i]));
-               if (ctx->bn[i].d)
-                       BN_clear_free(&(ctx->bn[i]));
+#ifdef BN_CTX_DEBUG
+       BN_POOL_ITEM *pool = ctx->pool.head;
+       printf("BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
+               ctx->stack.size, ctx->pool.size);
+       printf("dmaxs: ");
+       while(pool) {
+               unsigned loop = 0;
+               while(loop < BN_CTX_POOL_SIZE)
+                       printf("%02x ", pool->vals[loop++].dmax);
+               pool = pool->next;
        }
-       if (ctx->flags & BN_FLG_MALLOCED)
-               OPENSSL_free(ctx);
+       printf("\n");
+#endif
+       BN_STACK_finish(&ctx->stack);
+       BN_POOL_finish(&ctx->pool);
+       OPENSSL_free(ctx);
        }
 
 void BN_CTX_start(BN_CTX *ctx)
        {
-       if (ctx->depth < BN_CTX_NUM_POS)
-               ctx->pos[ctx->depth] = ctx->tos;
-       ctx->depth++;
+       CTXDBG_ENTRY("BN_CTX_start", ctx);
+       /* If we're already overflowing ... */
+       if(ctx->err_stack || ctx->too_many)
+               ctx->err_stack++;
+       /* (Try to) get a new frame pointer */
+       else if(!BN_STACK_push(&ctx->stack, ctx->used))
+               {
+               /* I know this isn't BN_CTX_get, but ... */
+               BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
+               ctx->err_stack++;
+               }
+       CTXDBG_EXIT(ctx);
        }
 
+void BN_CTX_end(BN_CTX *ctx)
+       {
+       CTXDBG_ENTRY("BN_CTX_end", ctx);
+       if(ctx->err_stack)
+               ctx->err_stack--;
+       else
+               {
+               unsigned int fp = BN_STACK_pop(&ctx->stack);
+               /* Does this stack frame have anything to release? */
+               if(fp < ctx->used)
+                       BN_POOL_release(&ctx->pool, ctx->used - fp);
+               ctx->used = fp;
+               /* Unjam "too_many" in case "get" had failed */
+               ctx->too_many = 0;
+               }
+       CTXDBG_EXIT(ctx);
+       }
 
 BIGNUM *BN_CTX_get(BN_CTX *ctx)
        {
        BIGNUM *ret;
-       /* Note: If BN_CTX_get is ever changed to allocate BIGNUMs dynamically,
-        * make sure that if BN_CTX_get fails once it will return NULL again
-        * until BN_CTX_end is called.  (This is so that callers have to check
-        * only the last return value.)
-        */
-       if (ctx->depth > BN_CTX_NUM_POS || ctx->tos >= BN_CTX_NUM)
+       CTXDBG_ENTRY("BN_CTX_get", ctx);
+       if(ctx->err_stack || ctx->too_many) return NULL;
+       if((ret = BN_POOL_get(&ctx->pool)) == NULL)
                {
-               if (!ctx->too_many)
-                       {
-                       BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
-                       /* disable error code until BN_CTX_end is called: */
-                       ctx->too_many = 1;
-                       }
+               /* Setting too_many prevents repeated "get" attempts from
+                * cluttering the error stack. */
+               ctx->too_many = 1;
+               BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
                return NULL;
                }
-       ret = ctx->bn + (ctx->tos++);
-       /* always return a 'zeroed' bignum */
+       /* OK, make sure the returned bignum is "zero" */
        BN_zero(ret);
+       ctx->used++;
+       CTXDBG_RET(ctx, ret);
        return ret;
        }
 
-void BN_CTX_end(BN_CTX *ctx)
+/************/
+/* BN_STACK */
+/************/
+
+static void BN_STACK_init(BN_STACK *st)
+       {
+       st->indexes = NULL;
+       st->depth = st->size = 0;
+       }
+
+static void BN_STACK_finish(BN_STACK *st)
        {
-       if (ctx == NULL) return;
-       assert(ctx->depth > 0);
-       if (ctx->depth == 0)
-               /* should never happen, but we can tolerate it if not in
-                * debug mode (could be a 'goto err' in the calling function
-                * before BN_CTX_start was reached) */
-               BN_CTX_start(ctx);
+       if(st->size) OPENSSL_free(st->indexes);
+       }
 
-       ctx->too_many = 0;
-       ctx->depth--;
-       if (ctx->depth < BN_CTX_NUM_POS)
-#ifndef BN_DEBUG
-               ctx->tos = ctx->pos[ctx->depth];
-#else
-               while(ctx->tos > ctx->pos[ctx->depth])
-                       bn_check_top(&ctx->bn[--(ctx->tos)]);
+#ifndef OPENSSL_NO_DEPRECATED
+static void BN_STACK_reset(BN_STACK *st)
+       {
+       st->depth = 0;
+       }
+#endif
+
+static int BN_STACK_push(BN_STACK *st, unsigned int idx)
+       {
+       if(st->depth == st->size)
+               /* Need to expand */
+               {
+               unsigned int newsize = (st->size ?
+                               (st->size * 3 / 2) : BN_CTX_START_FRAMES);
+               unsigned int *newitems = OPENSSL_malloc(newsize *
+                                               sizeof(unsigned int));
+               if(!newitems) return 0;
+               if(st->depth)
+                       memcpy(newitems, st->indexes, st->depth *
+                                               sizeof(unsigned int));
+               if(st->size) OPENSSL_free(st->indexes);
+               st->indexes = newitems;
+               st->size = newsize;
+               }
+       st->indexes[(st->depth)++] = idx;
+       return 1;
+       }
+
+static unsigned int BN_STACK_pop(BN_STACK *st)
+       {
+       return st->indexes[--(st->depth)];
+       }
+
+/***********/
+/* BN_POOL */
+/***********/
+
+static void BN_POOL_init(BN_POOL *p)
+       {
+       p->head = p->current = p->tail = NULL;
+       p->used = p->size = 0;
+       }
+
+static void BN_POOL_finish(BN_POOL *p)
+       {
+       while(p->head)
+               {
+               unsigned int loop = 0;
+               BIGNUM *bn = p->head->vals;
+               while(loop++ < BN_CTX_POOL_SIZE)
+                       {
+                       if(bn->d) BN_clear_free(bn);
+                       bn++;
+                       }
+               p->current = p->head->next;
+               OPENSSL_free(p->head);
+               p->head = p->current;
+               }
+       }
+
+#ifndef OPENSSL_NO_DEPRECATED
+static void BN_POOL_reset(BN_POOL *p)
+       {
+       BN_POOL_ITEM *item = p->head;
+       while(item)
+               {
+               unsigned int loop = 0;
+               BIGNUM *bn = item->vals;
+               while(loop++ < BN_CTX_POOL_SIZE)
+                       {
+                       if(bn->d) BN_clear(bn);
+                       bn++;
+                       }
+               item = item->next;
+               }
+       p->current = p->head;
+       p->used = 0;
+       }
 #endif
+
+static BIGNUM *BN_POOL_get(BN_POOL *p)
+       {
+       if(p->used == p->size)
+               {
+               BIGNUM *bn;
+               unsigned int loop = 0;
+               BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
+               if(!item) return NULL;
+               /* Initialise the structure */
+               bn = item->vals;
+               while(loop++ < BN_CTX_POOL_SIZE)
+                       BN_init(bn++);
+               item->prev = p->tail;
+               item->next = NULL;
+               /* Link it in */
+               if(!p->head)
+                       p->head = p->current = p->tail = item;
+               else
+                       {
+                       p->tail->next = item;
+                       p->tail = item;
+                       p->current = item;
+                       }
+               p->size += BN_CTX_POOL_SIZE;
+               p->used++;
+               /* Return the first bignum from the new pool */
+               return item->vals;
+               }
+       if(!p->used)
+               p->current = p->head;
+       else if((p->used % BN_CTX_POOL_SIZE) == 0)
+               p->current = p->current->next;
+       return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
+       }
+
+static void BN_POOL_release(BN_POOL *p, unsigned int num)
+       {
+       unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
+       p->used -= num;
+       while(num--)
+               {
+               bn_check_top(p->current->vals + offset);
+               if(!offset)
+                       {
+                       offset = BN_CTX_POOL_SIZE - 1;
+                       p->current = p->current->prev;
+                       }
+               else
+                       offset--;
+               }
        }
+