1 /* Written by Ulf Moeller for the OpenSSL project. */ 2 /* ==================================================================== 3 * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * openssl-core (at) openssl.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay (at) cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh (at) cryptsoft.com). */ 53 54 55 #include <openssl/bn.h> 56 57 #include <openssl/err.h> 58 #include <openssl/mem.h> 59 60 61 /* How many bignums are in each "pool item"; */ 62 #define BN_CTX_POOL_SIZE 16 63 /* The stack frame info is resizing, set a first-time expansion size; */ 64 #define BN_CTX_START_FRAMES 32 65 66 /* A bundle of bignums that can be linked with other bundles */ 67 typedef struct bignum_pool_item { 68 /* The bignum values */ 69 BIGNUM vals[BN_CTX_POOL_SIZE]; 70 /* Linked-list admin */ 71 struct bignum_pool_item *prev, *next; 72 } BN_POOL_ITEM; 73 74 75 typedef struct bignum_pool { 76 /* Linked-list admin */ 77 BN_POOL_ITEM *head, *current, *tail; 78 /* Stack depth and allocation size */ 79 unsigned used, size; 80 } BN_POOL; 81 82 static void BN_POOL_init(BN_POOL *); 83 static void BN_POOL_finish(BN_POOL *); 84 static BIGNUM *BN_POOL_get(BN_POOL *); 85 static void BN_POOL_release(BN_POOL *, unsigned int); 86 87 /************/ 88 /* BN_STACK */ 89 /************/ 90 91 /* A wrapper to manage the "stack frames" */ 92 typedef struct bignum_ctx_stack { 93 /* Array of indexes into the bignum stack */ 94 unsigned int *indexes; 95 /* Number of stack frames, and the size of the allocated array */ 96 unsigned int depth, size; 97 } BN_STACK; 98 99 static void BN_STACK_init(BN_STACK *); 100 static void BN_STACK_finish(BN_STACK *); 101 static int BN_STACK_push(BN_STACK *, unsigned int); 102 static unsigned int BN_STACK_pop(BN_STACK *); 103 104 /**********/ 105 /* BN_CTX */ 106 /**********/ 107 108 /* The opaque BN_CTX type */ 109 struct bignum_ctx { 110 /* The bignum bundles */ 111 BN_POOL pool; 112 /* The "stack frames", if you will */ 113 BN_STACK stack; 114 /* The number of bignums currently assigned */ 115 unsigned int used; 116 /* Depth of stack overflow */ 117 int err_stack; 118 /* Block "gets" until an "end" (compatibility behaviour) */ 119 int too_many; 120 }; 121 122 BN_CTX *BN_CTX_new(void) { 123 BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 124 if (!ret) { 125 OPENSSL_PUT_ERROR(BN, BN_CTX_new, ERR_R_MALLOC_FAILURE); 126 return NULL; 127 } 128 129 /* Initialise the structure */ 130 BN_POOL_init(&ret->pool); 131 BN_STACK_init(&ret->stack); 132 ret->used = 0; 133 ret->err_stack = 0; 134 ret->too_many = 0; 135 return ret; 136 } 137 138 void BN_CTX_free(BN_CTX *ctx) { 139 if (ctx == NULL) { 140 return; 141 } 142 143 BN_STACK_finish(&ctx->stack); 144 BN_POOL_finish(&ctx->pool); 145 OPENSSL_free(ctx); 146 } 147 148 void BN_CTX_start(BN_CTX *ctx) { 149 /* If we're already overflowing ... */ 150 if (ctx->err_stack || ctx->too_many) { 151 ctx->err_stack++; 152 } else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 153 /* (Try to) get a new frame pointer */ 154 OPENSSL_PUT_ERROR(BN, BN_CTX_start, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 155 ctx->err_stack++; 156 } 157 } 158 159 BIGNUM *BN_CTX_get(BN_CTX *ctx) { 160 BIGNUM *ret; 161 if (ctx->err_stack || ctx->too_many) { 162 return NULL; 163 } 164 165 ret = BN_POOL_get(&ctx->pool); 166 if (ret == NULL) { 167 /* Setting too_many prevents repeated "get" attempts from 168 * cluttering the error stack. */ 169 ctx->too_many = 1; 170 OPENSSL_PUT_ERROR(BN, BN_CTX_get, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 171 return NULL; 172 } 173 174 /* OK, make sure the returned bignum is "zero" */ 175 BN_zero(ret); 176 ctx->used++; 177 return ret; 178 } 179 180 void BN_CTX_end(BN_CTX *ctx) { 181 if (ctx->err_stack) { 182 ctx->err_stack--; 183 } else { 184 unsigned int fp = BN_STACK_pop(&ctx->stack); 185 /* Does this stack frame have anything to release? */ 186 if (fp < ctx->used) { 187 BN_POOL_release(&ctx->pool, ctx->used - fp); 188 } 189 190 ctx->used = fp; 191 /* Unjam "too_many" in case "get" had failed */ 192 ctx->too_many = 0; 193 } 194 } 195 196 /************/ 197 /* BN_STACK */ 198 /************/ 199 200 static void BN_STACK_init(BN_STACK *st) { 201 st->indexes = NULL; 202 st->depth = st->size = 0; 203 } 204 205 static void BN_STACK_finish(BN_STACK *st) { 206 if (st->size) 207 OPENSSL_free(st->indexes); 208 } 209 210 static int BN_STACK_push(BN_STACK *st, unsigned int idx) { 211 if (st->depth == st->size) 212 /* Need to expand */ 213 { 214 unsigned int newsize = 215 (st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES); 216 unsigned int *newitems = OPENSSL_malloc(newsize * sizeof(unsigned int)); 217 if (!newitems) { 218 return 0; 219 } 220 if (st->depth) { 221 memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int)); 222 } 223 if (st->size) { 224 OPENSSL_free(st->indexes); 225 } 226 st->indexes = newitems; 227 st->size = newsize; 228 } 229 230 st->indexes[(st->depth)++] = idx; 231 return 1; 232 } 233 234 static unsigned int BN_STACK_pop(BN_STACK *st) { 235 return st->indexes[--(st->depth)]; 236 } 237 238 static void BN_POOL_init(BN_POOL *p) { 239 p->head = p->current = p->tail = NULL; 240 p->used = p->size = 0; 241 } 242 243 static void BN_POOL_finish(BN_POOL *p) { 244 while (p->head) { 245 unsigned int loop = 0; 246 BIGNUM *bn = p->head->vals; 247 while (loop++ < BN_CTX_POOL_SIZE) { 248 if (bn->d) { 249 BN_clear_free(bn); 250 } 251 bn++; 252 } 253 254 p->current = p->head->next; 255 OPENSSL_free(p->head); 256 p->head = p->current; 257 } 258 } 259 260 static BIGNUM *BN_POOL_get(BN_POOL *p) { 261 if (p->used == p->size) { 262 BIGNUM *bn; 263 unsigned int loop = 0; 264 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 265 if (!item) { 266 return NULL; 267 } 268 269 /* Initialise the structure */ 270 bn = item->vals; 271 while (loop++ < BN_CTX_POOL_SIZE) { 272 BN_init(bn++); 273 } 274 275 item->prev = p->tail; 276 item->next = NULL; 277 /* Link it in */ 278 if (!p->head) { 279 p->head = p->current = p->tail = item; 280 } else { 281 p->tail->next = item; 282 p->tail = item; 283 p->current = item; 284 } 285 286 p->size += BN_CTX_POOL_SIZE; 287 p->used++; 288 /* Return the first bignum from the new pool */ 289 return item->vals; 290 } 291 292 if (!p->used) { 293 p->current = p->head; 294 } else if ((p->used % BN_CTX_POOL_SIZE) == 0) { 295 p->current = p->current->next; 296 } 297 298 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 299 } 300 301 static void BN_POOL_release(BN_POOL *p, unsigned int num) { 302 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 303 p->used -= num; 304 305 while (num--) { 306 if (!offset) { 307 offset = BN_CTX_POOL_SIZE - 1; 308 p->current = p->current->prev; 309 } else { 310 offset--; 311 } 312 } 313 } 314
