| OLD | NEW |
|---|
| (Empty) |
| 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 /* 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 { | |
| 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 */ | |
| 99 typedef struct bignum_pool | |
| 100 { | |
| 101 /* Linked-list admin */ | |
| 102 BN_POOL_ITEM *head, *current, *tail; | |
| 103 /* Stack depth and allocation size */ | |
| 104 unsigned used, size; | |
| 105 } BN_POOL; | |
| 106 static void BN_POOL_init(BN_POOL *); | |
| 107 static void BN_POOL_finish(BN_POOL *); | |
| 108 #ifndef OPENSSL_NO_DEPRECATED | |
| 109 static void BN_POOL_reset(BN_POOL *); | |
| 110 #endif | |
| 111 static BIGNUM * BN_POOL_get(BN_POOL *); | |
| 112 static void BN_POOL_release(BN_POOL *, unsigned int); | |
| 113 | |
| 114 /************/ | |
| 115 /* BN_STACK */ | |
| 116 /************/ | |
| 117 | |
| 118 /* A wrapper to manage the "stack frames" */ | |
| 119 typedef struct bignum_ctx_stack | |
| 120 { | |
| 121 /* Array of indexes into the bignum stack */ | |
| 122 unsigned int *indexes; | |
| 123 /* Number of stack frames, and the size of the allocated array */ | |
| 124 unsigned int depth, size; | |
| 125 } BN_STACK; | |
| 126 static void BN_STACK_init(BN_STACK *); | |
| 127 static void BN_STACK_finish(BN_STACK *); | |
| 128 #ifndef OPENSSL_NO_DEPRECATED | |
| 129 static void BN_STACK_reset(BN_STACK *); | |
| 130 #endif | |
| 131 static int BN_STACK_push(BN_STACK *, unsigned int); | |
| 132 static unsigned int BN_STACK_pop(BN_STACK *); | |
| 133 | |
| 134 /**********/ | |
| 135 /* BN_CTX */ | |
| 136 /**********/ | |
| 137 | |
| 138 /* The opaque BN_CTX type */ | |
| 139 struct bignum_ctx | |
| 140 { | |
| 141 /* The bignum bundles */ | |
| 142 BN_POOL pool; | |
| 143 /* The "stack frames", if you will */ | |
| 144 BN_STACK stack; | |
| 145 /* The number of bignums currently assigned */ | |
| 146 unsigned int used; | |
| 147 /* Depth of stack overflow */ | |
| 148 int err_stack; | |
| 149 /* Block "gets" until an "end" (compatibility behaviour) */ | |
| 150 int too_many; | |
| 151 }; | |
| 152 | |
| 153 /* Enable this to find BN_CTX bugs */ | |
| 154 #ifdef BN_CTX_DEBUG | |
| 155 static const char *ctxdbg_cur = NULL; | |
| 156 static void ctxdbg(BN_CTX *ctx) | |
| 157 { | |
| 158 unsigned int bnidx = 0, fpidx = 0; | |
| 159 BN_POOL_ITEM *item = ctx->pool.head; | |
| 160 BN_STACK *stack = &ctx->stack; | |
| 161 fprintf(stderr,"(%08x): ", (unsigned int)ctx); | |
| 162 while(bnidx < ctx->used) | |
| 163 { | |
| 164 fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].d
max); | |
| 165 if(!(bnidx % BN_CTX_POOL_SIZE)) | |
| 166 item = item->next; | |
| 167 } | |
| 168 fprintf(stderr,"\n"); | |
| 169 bnidx = 0; | |
| 170 fprintf(stderr," : "); | |
| 171 while(fpidx < stack->depth) | |
| 172 { | |
| 173 while(bnidx++ < stack->indexes[fpidx]) | |
| 174 fprintf(stderr," "); | |
| 175 fprintf(stderr,"^^^ "); | |
| 176 bnidx++; | |
| 177 fpidx++; | |
| 178 } | |
| 179 fprintf(stderr,"\n"); | |
| 180 } | |
| 181 #define CTXDBG_ENTRY(str, ctx) do { \ | |
| 182 ctxdbg_cur = (str); \ | |
| 183 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ | |
| 184 ctxdbg(ctx); \ | |
| 185 } while(0) | |
| 186 #define CTXDBG_EXIT(ctx) do { \ | |
| 187 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ | |
| 188 ctxdbg(ctx); \ | |
| 189 } while(0) | |
| 190 #define CTXDBG_RET(ctx,ret) | |
| 191 #else | |
| 192 #define CTXDBG_ENTRY(str, ctx) | |
| 193 #define CTXDBG_EXIT(ctx) | |
| 194 #define CTXDBG_RET(ctx,ret) | |
| 195 #endif | |
| 196 | |
| 197 /* This function is an evil legacy and should not be used. This implementation | |
| 198 * is WYSIWYG, though I've done my best. */ | |
| 199 #ifndef OPENSSL_NO_DEPRECATED | |
| 200 void BN_CTX_init(BN_CTX *ctx) | |
| 201 { | |
| 202 /* Assume the caller obtained the context via BN_CTX_new() and so is | |
| 203 * trying to reset it for use. Nothing else makes sense, least of all | |
| 204 * binary compatibility from a time when they could declare a static | |
| 205 * variable. */ | |
| 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 | |
| 214 BN_CTX *BN_CTX_new(void) | |
| 215 { | |
| 216 BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); | |
| 217 if(!ret) | |
| 218 { | |
| 219 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); | |
| 220 return NULL; | |
| 221 } | |
| 222 /* Initialise the structure */ | |
| 223 BN_POOL_init(&ret->pool); | |
| 224 BN_STACK_init(&ret->stack); | |
| 225 ret->used = 0; | |
| 226 ret->err_stack = 0; | |
| 227 ret->too_many = 0; | |
| 228 return ret; | |
| 229 } | |
| 230 | |
| 231 void BN_CTX_free(BN_CTX *ctx) | |
| 232 { | |
| 233 if (ctx == NULL) | |
| 234 return; | |
| 235 #ifdef BN_CTX_DEBUG | |
| 236 { | |
| 237 BN_POOL_ITEM *pool = ctx->pool.head; | |
| 238 fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n", | |
| 239 ctx->stack.size, ctx->pool.size); | |
| 240 fprintf(stderr,"dmaxs: "); | |
| 241 while(pool) { | |
| 242 unsigned loop = 0; | |
| 243 while(loop < BN_CTX_POOL_SIZE) | |
| 244 fprintf(stderr,"%02x ", pool->vals[loop++].dmax); | |
| 245 pool = pool->next; | |
| 246 } | |
| 247 fprintf(stderr,"\n"); | |
| 248 } | |
| 249 #endif | |
| 250 BN_STACK_finish(&ctx->stack); | |
| 251 BN_POOL_finish(&ctx->pool); | |
| 252 OPENSSL_free(ctx); | |
| 253 } | |
| 254 | |
| 255 void BN_CTX_start(BN_CTX *ctx) | |
| 256 { | |
| 257 CTXDBG_ENTRY("BN_CTX_start", ctx); | |
| 258 /* If we're already overflowing ... */ | |
| 259 if(ctx->err_stack || ctx->too_many) | |
| 260 ctx->err_stack++; | |
| 261 /* (Try to) get a new frame pointer */ | |
| 262 else if(!BN_STACK_push(&ctx->stack, ctx->used)) | |
| 263 { | |
| 264 BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES); | |
| 265 ctx->err_stack++; | |
| 266 } | |
| 267 CTXDBG_EXIT(ctx); | |
| 268 } | |
| 269 | |
| 270 void BN_CTX_end(BN_CTX *ctx) | |
| 271 { | |
| 272 CTXDBG_ENTRY("BN_CTX_end", ctx); | |
| 273 if(ctx->err_stack) | |
| 274 ctx->err_stack--; | |
| 275 else | |
| 276 { | |
| 277 unsigned int fp = BN_STACK_pop(&ctx->stack); | |
| 278 /* Does this stack frame have anything to release? */ | |
| 279 if(fp < ctx->used) | |
| 280 BN_POOL_release(&ctx->pool, ctx->used - fp); | |
| 281 ctx->used = fp; | |
| 282 /* Unjam "too_many" in case "get" had failed */ | |
| 283 ctx->too_many = 0; | |
| 284 } | |
| 285 CTXDBG_EXIT(ctx); | |
| 286 } | |
| 287 | |
| 288 BIGNUM *BN_CTX_get(BN_CTX *ctx) | |
| 289 { | |
| 290 BIGNUM *ret; | |
| 291 CTXDBG_ENTRY("BN_CTX_get", ctx); | |
| 292 if(ctx->err_stack || ctx->too_many) return NULL; | |
| 293 if((ret = BN_POOL_get(&ctx->pool)) == NULL) | |
| 294 { | |
| 295 /* Setting too_many prevents repeated "get" attempts from | |
| 296 * cluttering the error stack. */ | |
| 297 ctx->too_many = 1; | |
| 298 BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); | |
| 299 return NULL; | |
| 300 } | |
| 301 /* OK, make sure the returned bignum is "zero" */ | |
| 302 BN_zero(ret); | |
| 303 ctx->used++; | |
| 304 CTXDBG_RET(ctx, ret); | |
| 305 return ret; | |
| 306 } | |
| 307 | |
| 308 /************/ | |
| 309 /* BN_STACK */ | |
| 310 /************/ | |
| 311 | |
| 312 static void BN_STACK_init(BN_STACK *st) | |
| 313 { | |
| 314 st->indexes = NULL; | |
| 315 st->depth = st->size = 0; | |
| 316 } | |
| 317 | |
| 318 static void BN_STACK_finish(BN_STACK *st) | |
| 319 { | |
| 320 if(st->size) OPENSSL_free(st->indexes); | |
| 321 } | |
| 322 | |
| 323 #ifndef OPENSSL_NO_DEPRECATED | |
| 324 static void BN_STACK_reset(BN_STACK *st) | |
| 325 { | |
| 326 st->depth = 0; | |
| 327 } | |
| 328 #endif | |
| 329 | |
| 330 static 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) return 0; | |
| 340 if(st->depth) | |
| 341 memcpy(newitems, st->indexes, st->depth * | |
| 342 sizeof(unsigned int)); | |
| 343 if(st->size) 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 { | |
| 370 unsigned int loop = 0; | |
| 371 BIGNUM *bn = p->head->vals; | |
| 372 while(loop++ < BN_CTX_POOL_SIZE) | |
| 373 { | |
| 374 if(bn->d) 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 | |
| 384 static void BN_POOL_reset(BN_POOL *p) | |
| 385 { | |
| 386 BN_POOL_ITEM *item = p->head; | |
| 387 while(item) | |
| 388 { | |
| 389 unsigned int loop = 0; | |
| 390 BIGNUM *bn = item->vals; | |
| 391 while(loop++ < BN_CTX_POOL_SIZE) | |
| 392 { | |
| 393 if(bn->d) BN_clear(bn); | |
| 394 bn++; | |
| 395 } | |
| 396 item = item->next; | |
| 397 } | |
| 398 p->current = p->head; | |
| 399 p->used = 0; | |
| 400 } | |
| 401 #endif | |
| 402 | |
| 403 static BIGNUM *BN_POOL_get(BN_POOL *p) | |
| 404 { | |
| 405 if(p->used == p->size) | |
| 406 { | |
| 407 BIGNUM *bn; | |
| 408 unsigned int loop = 0; | |
| 409 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); | |
| 410 if(!item) return NULL; | |
| 411 /* Initialise the structure */ | |
| 412 bn = item->vals; | |
| 413 while(loop++ < BN_CTX_POOL_SIZE) | |
| 414 BN_init(bn++); | |
| 415 item->prev = p->tail; | |
| 416 item->next = NULL; | |
| 417 /* Link it in */ | |
| 418 if(!p->head) | |
| 419 p->head = p->current = p->tail = item; | |
| 420 else | |
| 421 { | |
| 422 p->tail->next = item; | |
| 423 p->tail = item; | |
| 424 p->current = item; | |
| 425 } | |
| 426 p->size += BN_CTX_POOL_SIZE; | |
| 427 p->used++; | |
| 428 /* Return the first bignum from the new pool */ | |
| 429 return item->vals; | |
| 430 } | |
| 431 if(!p->used) | |
| 432 p->current = p->head; | |
| 433 else if((p->used % BN_CTX_POOL_SIZE) == 0) | |
| 434 p->current = p->current->next; | |
| 435 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); | |
| 436 } | |
| 437 | |
| 438 static void BN_POOL_release(BN_POOL *p, unsigned int num) | |
| 439 { | |
| 440 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; | |
| 441 p->used -= num; | |
| 442 while(num--) | |
| 443 { | |
| 444 bn_check_top(p->current->vals + offset); | |
| 445 if(!offset) | |
| 446 { | |
| 447 offset = BN_CTX_POOL_SIZE - 1; | |
| 448 p->current = p->current->prev; | |
| 449 } | |
| 450 else | |
| 451 offset--; | |
| 452 } | |
| 453 } | |
| 454 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2072073002:
Delete bundled copy of OpenSSL and replace with README. (Closed)
Base URL: https://chromium.googlesource.com/chromium/deps/openssl@master