From ba729265a819d4c36df730449aeb301927ca74f2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bodo=20M=C3=B6ller?= Date: Wed, 12 Feb 2003 18:30:16 +0000 Subject: [PATCH] Allow EC_GROUP objects to share precomputation for improved memory efficiency (EC_PRE_COMP objects are now constant once completed). Extend 'extra_data' API to support arbitrarily many slots (although we need only one at the moment). Modify EC internal 'extra_data' API: EC_GROUP_[clear_]free_extra_data now frees only a single slot (the previous functions are available as EC_GROUP_[clear_]free_all_extra_data). Submitted by: Nils Larsch Reviewed by: Bodo Moeller --- crypto/ec/ec_lcl.h | 31 +++++--- crypto/ec/ec_lib.c | 187 +++++++++++++++++++++++++++++++------------- crypto/ec/ec_mult.c | 99 ++++++++--------------- 3 files changed, 185 insertions(+), 132 deletions(-) diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index f4e9700bb8..f59fe0e448 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -167,6 +167,13 @@ struct ec_method_st { int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *); } /* EC_METHOD */; +typedef struct ec_extra_data_st { + struct ec_extra_data_st *next; + void *data; + void *(*dup_func)(void *); + void (*free_func)(void *); + void (*clear_free_func)(void *); +} EC_EXTRA_DATA; /* used in EC_GROUP */ struct ec_group_st { const EC_METHOD *meth; @@ -181,10 +188,7 @@ struct ec_group_st { unsigned char *seed; /* optional seed for parameters (appears in ASN1) */ size_t seed_len; - void *extra_data; - void *(*extra_data_dup_func)(void *); - void (*extra_data_free_func)(void *); - void (*extra_data_clear_free_func)(void *); + EC_EXTRA_DATA *extra_data; /* linked list */ /* The following members are handled by the method functions, * even if they appear generic */ @@ -224,14 +228,17 @@ struct ec_group_st { * (with visibility limited to 'package' level for now). * We use the function pointers as index for retrieval; this obviates * global ex_data-style index tables. - * (Currently, we have one slot only, but is is possible to extend this - * if necessary.) */ -int EC_GROUP_set_extra_data(EC_GROUP *, void *extra_data, void *(*extra_data_dup_func)(void *), - void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)); -void *EC_GROUP_get_extra_data(const EC_GROUP *, void *(*extra_data_dup_func)(void *), - void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)); -void EC_GROUP_free_extra_data(EC_GROUP *); -void EC_GROUP_clear_free_extra_data(EC_GROUP *); + */ +int EC_GROUP_set_extra_data(EC_GROUP *, void *data, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)); +void *EC_GROUP_get_extra_data(const EC_GROUP *, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)); +void EC_GROUP_free_extra_data(EC_GROUP*, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)); +void EC_GROUP_clear_free_extra_data(EC_GROUP*, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)); +void EC_GROUP_free_all_extra_data(EC_GROUP *); +void EC_GROUP_clear_free_all_extra_data(EC_GROUP *); diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c index 5e3fb5c20b..c00875cd73 100644 --- a/crypto/ec/ec_lib.c +++ b/crypto/ec/ec_lib.c @@ -98,9 +98,6 @@ EC_GROUP *EC_GROUP_new(const EC_METHOD *meth) ret->meth = meth; ret->extra_data = NULL; - ret->extra_data_dup_func = 0; - ret->extra_data_free_func = 0; - ret->extra_data_clear_free_func = 0; ret->generator = NULL; BN_init(&ret->order); @@ -130,7 +127,7 @@ void EC_GROUP_free(EC_GROUP *group) if (group->meth->group_finish != 0) group->meth->group_finish(group); - EC_GROUP_free_extra_data(group); + EC_GROUP_free_all_extra_data(group); if (group->generator != NULL) EC_POINT_free(group->generator); @@ -153,7 +150,7 @@ void EC_GROUP_clear_free(EC_GROUP *group) else if (group->meth != NULL && group->meth->group_finish != 0) group->meth->group_finish(group); - EC_GROUP_clear_free_extra_data(group); + EC_GROUP_clear_free_all_extra_data(group); if (group->generator != NULL) EC_POINT_clear_free(group->generator); @@ -173,6 +170,8 @@ void EC_GROUP_clear_free(EC_GROUP *group) int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) { + EC_EXTRA_DATA *d; + if (dest->meth->group_copy == 0) { ECerr(EC_F_EC_GROUP_COPY, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); @@ -186,19 +185,16 @@ int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) if (dest == src) return 1; - EC_GROUP_clear_free_extra_data(dest); - if (src->extra_data_dup_func) - { - if (src->extra_data != NULL) - { - dest->extra_data = src->extra_data_dup_func(src->extra_data); - if (dest->extra_data == NULL) - return 0; - } + EC_GROUP_free_all_extra_data(dest); - dest->extra_data_dup_func = src->extra_data_dup_func; - dest->extra_data_free_func = src->extra_data_free_func; - dest->extra_data_clear_free_func = src->extra_data_clear_free_func; + for (d = src->extra_data; d != NULL; d = d->next) + { + void *t = d->dup_func(d->data); + + if (t == NULL) + return 0; + if (!EC_GROUP_set_extra_data(dest, t, d->dup_func, d->free_func, d->clear_free_func)) + return 0; } if (src->generator != NULL) @@ -475,67 +471,148 @@ int EC_GROUP_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) /* this has 'package' visibility */ -int EC_GROUP_set_extra_data(EC_GROUP *group, void *extra_data, void *(*extra_data_dup_func)(void *), - void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)) +int EC_GROUP_set_extra_data(EC_GROUP *group, void *data, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)) { - if ((group->extra_data != NULL) - || (group->extra_data_dup_func != 0) - || (group->extra_data_free_func != 0) - || (group->extra_data_clear_free_func != 0)) - { - ECerr(EC_F_EC_GROUP_SET_EXTRA_DATA, EC_R_SLOT_FULL); + EC_EXTRA_DATA *d; + + if (group == NULL) return 0; + + for (d = group->extra_data; d != NULL; d = d->next) + { + if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func) + { + ECerr(EC_F_EC_GROUP_SET_EXTRA_DATA, EC_R_SLOT_FULL); + return 0; + } } - group->extra_data = extra_data; - group->extra_data_dup_func = extra_data_dup_func; - group->extra_data_free_func = extra_data_free_func; - group->extra_data_clear_free_func = extra_data_clear_free_func; + if (data == NULL) + /* no explicit entry needed */ + return 1; + + d = OPENSSL_malloc(sizeof *d); + if (d == NULL) + return 0; + + d->data = data; + d->dup_func = dup_func; + d->free_func = free_func; + d->clear_free_func = clear_free_func; + + d->next = group->extra_data; + group->extra_data = d; + return 1; } - /* this has 'package' visibility */ -void *EC_GROUP_get_extra_data(const EC_GROUP *group, void *(*extra_data_dup_func)(void *), - void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *)) +void *EC_GROUP_get_extra_data(const EC_GROUP *group, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)) { - if ((group->extra_data_dup_func != extra_data_dup_func) - || (group->extra_data_free_func != extra_data_free_func) - || (group->extra_data_clear_free_func != extra_data_clear_free_func)) - { -#if 0 /* this was an error in 0.9.7, but that does not make a lot of sense */ - ECerr(EC_F_EC_GROUP_GET_EXTRA_DATA, EC_R_NO_SUCH_EXTRA_DATA); -#endif + EC_EXTRA_DATA *d; + + if (group == NULL) return NULL; + + for (d = group->extra_data; d != NULL; d = d->next) + { + if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func) + return d->data; } + + return NULL; + } - return group->extra_data; +/* this has 'package' visibility */ +void EC_GROUP_free_extra_data(EC_GROUP *group, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)) + { + EC_EXTRA_DATA **p; + + if (group == NULL) + return; + + for (p = &group->extra_data; *p != NULL; p = &((*p)->next)) + { + if ((*p)->dup_func == dup_func && (*p)->free_func == free_func && (*p)->clear_free_func == clear_free_func) + { + EC_EXTRA_DATA *next = (*p)->next; + + (*p)->free_func((*p)->data); + OPENSSL_free(*p); + + *p = next; + return; + } + } } +/* this has 'package' visibility */ +void EC_GROUP_clear_free_extra_data(EC_GROUP *group, + void *(*dup_func)(void *), void (*free_func)(void *), void (*clear_free_func)(void *)) + { + EC_EXTRA_DATA **p; + + if (group == NULL) + return; + + for (p = &group->extra_data; *p != NULL; p = &((*p)->next)) + { + if ((*p)->dup_func == dup_func && (*p)->free_func == free_func && (*p)->clear_free_func == clear_free_func) + { + EC_EXTRA_DATA *next = (*p)->next; + + (*p)->clear_free_func((*p)->data); + OPENSSL_free(*p); + + *p = next; + return; + } + } + } /* this has 'package' visibility */ -void EC_GROUP_free_extra_data(EC_GROUP *group) +void EC_GROUP_free_all_extra_data(EC_GROUP *group) { - if (group->extra_data_free_func) - group->extra_data_free_func(group->extra_data); + EC_EXTRA_DATA *d; + + if (group == NULL) + return; + + d = group->extra_data; + while (d) + { + EC_EXTRA_DATA *next = d->next; + + d->free_func(d->data); + OPENSSL_free(d); + + d = next; + } group->extra_data = NULL; - group->extra_data_dup_func = 0; - group->extra_data_free_func = 0; - group->extra_data_clear_free_func = 0; } - /* this has 'package' visibility */ -void EC_GROUP_clear_free_extra_data(EC_GROUP *group) +void EC_GROUP_clear_free_all_extra_data(EC_GROUP *group) { - if (group->extra_data_clear_free_func) - group->extra_data_clear_free_func(group->extra_data); - else if (group->extra_data_free_func) - group->extra_data_free_func(group->extra_data); + EC_EXTRA_DATA *d; + + if (group == NULL) + return; + + d = group->extra_data; + while (d) + { + EC_EXTRA_DATA *next = d->next; + + d->clear_free_func(d->data); + OPENSSL_free(d); + + d = next; + } group->extra_data = NULL; - group->extra_data_dup_func = 0; - group->extra_data_free_func = 0; - group->extra_data_clear_free_func = 0; } diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index f4e5f90847..c71a69ac0d 100644 --- a/crypto/ec/ec_mult.c +++ b/crypto/ec/ec_mult.c @@ -87,6 +87,7 @@ typedef struct ec_pre_comp_st { EC_POINT **points; /* array with pre-calculated multiples of generator: * 'num' pointers to EC_POINT objects followed by a NULL */ size_t num; /* numblocks * 2^(w-1) */ + int references; } EC_PRE_COMP; /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ @@ -110,68 +111,39 @@ static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) ret->w = 4; /* default */ ret->points = NULL; ret->num = 0; + ret->references = 1; return ret; } static void *ec_pre_comp_dup(void *src_) { - const EC_PRE_COMP *src = src_; - EC_PRE_COMP *ret = NULL; - - ret = ec_pre_comp_new(src->group); - if (!ret) - return ret; - ret->blocksize = src->blocksize; - ret->numblocks = src->numblocks; - ret->w = src->w; - ret->num = 0; - - if (src->points) - { - EC_POINT **src_var, **dest_var; - - ret->points = (EC_POINT **)OPENSSL_malloc((src->num + 1) * sizeof(EC_POINT *)); - if (!ret->points) - { - ec_pre_comp_free(ret); - return NULL; - } + EC_PRE_COMP *src = src_; - for (dest_var = ret->points, src_var = src->points; *src_var != NULL; src_var++, dest_var++) - { - *dest_var = EC_POINT_dup(*src_var, src->group); - if (*dest_var == NULL) - { - ec_pre_comp_free(ret); - return NULL; - } - ret->num++; - } + /* no need to actually copy, these objects never change! */ - ret->points[ret->num] = NULL; - if (ret->num != src->num) - { - ec_pre_comp_free(ret); - ECerr(EC_F_EC_PRE_COMP_DUP, ERR_R_INTERNAL_ERROR); - return NULL; - } - } + CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); - return ret; + return src_; } static void ec_pre_comp_free(void *pre_) { + int i; EC_PRE_COMP *pre = pre_; if (!pre) return; + + i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); + if (i > 0) + return; + if (pre->points) { - EC_POINT **var; + EC_POINT **p; - for (var = pre->points; *var != NULL; var++) - EC_POINT_free(*var); + for (p = pre->points; *p != NULL; p++) + EC_POINT_free(*p); OPENSSL_free(pre->points); } OPENSSL_free(pre); @@ -179,10 +151,16 @@ static void ec_pre_comp_free(void *pre_) static void ec_pre_comp_clear_free(void *pre_) { + int i; EC_PRE_COMP *pre = pre_; if (!pre) return; + + i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); + if (i > 0) + return; + if (pre->points) { EC_POINT **p; @@ -363,7 +341,7 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, EC_POINT **val = NULL; /* precomputation */ EC_POINT **v; EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */ - EC_PRE_COMP *pre_comp = NULL; + const EC_PRE_COMP *pre_comp = NULL; int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like other scalars, * i.e. precomputation is not available */ int ret = 0; @@ -761,13 +739,14 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) BIGNUM *order; size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; EC_POINT **points = NULL; - EC_PRE_COMP *pre_comp, *new_pre_comp = NULL; + EC_PRE_COMP *pre_comp; int ret = 0; - pre_comp = EC_GROUP_get_extra_data(group, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); - if (pre_comp == NULL) - if ((pre_comp = new_pre_comp = ec_pre_comp_new(group)) == NULL) - return 0; + /* if there is an old EC_PRE_COMP object, throw it away */ + EC_GROUP_free_extra_data(group, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); + + if ((pre_comp = ec_pre_comp_new(group)) == NULL) + return 0; generator = EC_GROUP_get0_generator(group); if (generator == NULL) @@ -888,32 +867,22 @@ int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) pre_comp->blocksize = blocksize; pre_comp->numblocks = numblocks; pre_comp->w = w; - if (pre_comp->points) - { - EC_POINT **p; - - for (p = pre_comp->points; *p != NULL; p++) - EC_POINT_free(*p); - OPENSSL_free(pre_comp->points); - } pre_comp->points = points; points = NULL; pre_comp->num = num; - if (new_pre_comp) - { - if (!EC_GROUP_set_extra_data(group, new_pre_comp, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) - goto err; - new_pre_comp = NULL; - } + if (!EC_GROUP_set_extra_data(group, pre_comp, + ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) + goto err; + pre_comp = NULL; ret = 1; err: BN_CTX_end(ctx); if (new_ctx != NULL) BN_CTX_free(new_ctx); - if (new_pre_comp) - ec_pre_comp_free(new_pre_comp); + if (pre_comp) + ec_pre_comp_free(pre_comp); if (points) { EC_POINT **p; -- 2.34.1