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 <string.h> 58 59 #include <openssl/err.h> 60 #include <openssl/mem.h> 61 62 #include "../../internal.h" 63 64 65 // How many bignums are in each "pool item"; 66 #define BN_CTX_POOL_SIZE 16 67 // The stack frame info is resizing, set a first-time expansion size; 68 #define BN_CTX_START_FRAMES 32 69 70 // A bundle of bignums that can be linked with other bundles 71 typedef struct bignum_pool_item { 72 // The bignum values 73 BIGNUM vals[BN_CTX_POOL_SIZE]; 74 // Linked-list admin 75 struct bignum_pool_item *prev, *next; 76 } BN_POOL_ITEM; 77 78 79 typedef struct bignum_pool { 80 // Linked-list admin 81 BN_POOL_ITEM *head, *current, *tail; 82 // Stack depth and allocation size 83 unsigned used, size; 84 } BN_POOL; 85 86 static void BN_POOL_init(BN_POOL *); 87 static void BN_POOL_finish(BN_POOL *); 88 static BIGNUM *BN_POOL_get(BN_POOL *); 89 static void BN_POOL_release(BN_POOL *, unsigned int); 90 91 92 // BN_STACK 93 94 // A wrapper to manage the "stack frames" 95 typedef struct bignum_ctx_stack { 96 // Array of indexes into the bignum stack 97 unsigned int *indexes; 98 // Number of stack frames, and the size of the allocated array 99 unsigned int depth, size; 100 } BN_STACK; 101 102 static void BN_STACK_init(BN_STACK *); 103 static void BN_STACK_finish(BN_STACK *); 104 static int BN_STACK_push(BN_STACK *, unsigned int); 105 static unsigned int BN_STACK_pop(BN_STACK *); 106 107 108 // BN_CTX 109 110 // The opaque BN_CTX type 111 struct bignum_ctx { 112 // The bignum bundles 113 BN_POOL pool; 114 // The "stack frames", if you will 115 BN_STACK stack; 116 // The number of bignums currently assigned 117 unsigned int used; 118 // Depth of stack overflow 119 int err_stack; 120 // Block "gets" until an "end" (compatibility behaviour) 121 int too_many; 122 }; 123 124 BN_CTX *BN_CTX_new(void) { 125 BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 126 if (!ret) { 127 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 128 return NULL; 129 } 130 131 // Initialise the structure 132 BN_POOL_init(&ret->pool); 133 BN_STACK_init(&ret->stack); 134 ret->used = 0; 135 ret->err_stack = 0; 136 ret->too_many = 0; 137 return ret; 138 } 139 140 void BN_CTX_free(BN_CTX *ctx) { 141 if (ctx == NULL) { 142 return; 143 } 144 145 BN_STACK_finish(&ctx->stack); 146 BN_POOL_finish(&ctx->pool); 147 OPENSSL_free(ctx); 148 } 149 150 void BN_CTX_start(BN_CTX *ctx) { 151 // If we're already overflowing ... 152 if (ctx->err_stack || ctx->too_many) { 153 ctx->err_stack++; 154 } else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 155 // (Try to) get a new frame pointer 156 OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 157 ctx->err_stack++; 158 } 159 } 160 161 BIGNUM *BN_CTX_get(BN_CTX *ctx) { 162 BIGNUM *ret; 163 if (ctx->err_stack || ctx->too_many) { 164 return NULL; 165 } 166 167 ret = BN_POOL_get(&ctx->pool); 168 if (ret == NULL) { 169 // Setting too_many prevents repeated "get" attempts from 170 // cluttering the error stack. 171 ctx->too_many = 1; 172 OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 173 return NULL; 174 } 175 176 // OK, make sure the returned bignum is "zero" 177 BN_zero(ret); 178 ctx->used++; 179 return ret; 180 } 181 182 void BN_CTX_end(BN_CTX *ctx) { 183 if (ctx->err_stack) { 184 ctx->err_stack--; 185 } else { 186 unsigned int fp = BN_STACK_pop(&ctx->stack); 187 // Does this stack frame have anything to release? 188 if (fp < ctx->used) { 189 BN_POOL_release(&ctx->pool, ctx->used - fp); 190 } 191 192 ctx->used = fp; 193 // Unjam "too_many" in case "get" had failed 194 ctx->too_many = 0; 195 } 196 } 197 198 199 // BN_STACK 200 201 static void BN_STACK_init(BN_STACK *st) { 202 st->indexes = NULL; 203 st->depth = st->size = 0; 204 } 205 206 static void BN_STACK_finish(BN_STACK *st) { 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 unsigned int newsize = 214 (st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES); 215 unsigned int *newitems = OPENSSL_malloc(newsize * sizeof(unsigned int)); 216 if (!newitems) { 217 return 0; 218 } 219 if (st->depth) { 220 OPENSSL_memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int)); 221 } 222 OPENSSL_free(st->indexes); 223 st->indexes = newitems; 224 st->size = newsize; 225 } 226 227 st->indexes[(st->depth)++] = idx; 228 return 1; 229 } 230 231 static unsigned int BN_STACK_pop(BN_STACK *st) { 232 return st->indexes[--(st->depth)]; 233 } 234 235 236 static void BN_POOL_init(BN_POOL *p) { 237 p->head = p->current = p->tail = NULL; 238 p->used = p->size = 0; 239 } 240 241 static void BN_POOL_finish(BN_POOL *p) { 242 while (p->head) { 243 for (size_t i = 0; i < BN_CTX_POOL_SIZE; i++) { 244 BN_clear_free(&p->head->vals[i]); 245 } 246 247 p->current = p->head->next; 248 OPENSSL_free(p->head); 249 p->head = p->current; 250 } 251 } 252 253 static BIGNUM *BN_POOL_get(BN_POOL *p) { 254 if (p->used == p->size) { 255 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 256 if (!item) { 257 return NULL; 258 } 259 260 // Initialise the structure 261 for (size_t i = 0; i < BN_CTX_POOL_SIZE; i++) { 262 BN_init(&item->vals[i]); 263 } 264 265 item->prev = p->tail; 266 item->next = NULL; 267 // Link it in 268 if (!p->head) { 269 p->head = p->current = p->tail = item; 270 } else { 271 p->tail->next = item; 272 p->tail = item; 273 p->current = item; 274 } 275 276 p->size += BN_CTX_POOL_SIZE; 277 p->used++; 278 // Return the first bignum from the new pool 279 return item->vals; 280 } 281 282 if (!p->used) { 283 p->current = p->head; 284 } else if ((p->used % BN_CTX_POOL_SIZE) == 0) { 285 p->current = p->current->next; 286 } 287 288 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 289 } 290 291 static void BN_POOL_release(BN_POOL *p, unsigned int num) { 292 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 293 p->used -= num; 294 295 while (num--) { 296 if (!offset) { 297 offset = BN_CTX_POOL_SIZE - 1; 298 p->current = p->current->prev; 299 } else { 300 offset--; 301 } 302 } 303 } 304
