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

diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index f4e9700bb8d1563454d1e87e0e13a8702168687c..f59fe0e4483ea43262ad8c867b9876a7b81fe8ef 100644 (file)
--- 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 */;
 
        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;
 
 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;
 
        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 */
 
        /* 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.
  * (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 5e3fb5c20b8dec6c13fe5ef616c39caf959cdfe9..c00875cd73e9483ea3b0fc9cd2b827fdbdb502b0 100644 (file)
--- 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->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);
 
        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);
 
        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);
 
        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);
 
        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);
 
        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)
        {
 
 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);
        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;
        
        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)
                }
 
        if (src->generator != NULL)


@@ -475,67 +471,148 @@ int EC_GROUP_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
 
 
 /* this has 'package' visibility */
 
 
 /* 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;
                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;
        }
 
        return 1;
        }
 

-

 /* this has 'package' visibility */
 /* 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;
                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 */
 
 /* 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 = NULL;

-       group->extra_data_dup_func = 0;
-       group->extra_data_free_func = 0;
-       group->extra_data_clear_free_func = 0;

        }
 
        }
 

-

 /* this has 'package' visibility */
 /* 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 = 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 f4e5f90847114ee511f35cb457544608e5ae35ce..c71a69ac0d45676304cb3b0b2ce0e4ee557c4a8e 100644 (file)
--- 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) */
        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 */
 } 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->w = 4; /* default */
        ret->points = NULL;
        ret->num = 0;

+       ret->references = 1;

        return ret;
        }
 
 static void *ec_pre_comp_dup(void *src_)
        {
        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_)
        {
        }
 
 static void ec_pre_comp_free(void *pre_)
        {

+       int i;

        EC_PRE_COMP *pre = pre_;
 
        if (!pre)
                return;
        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)
                {
        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);
                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_)
        {
 
 static void ec_pre_comp_clear_free(void *pre_)
        {

+       int i;

        EC_PRE_COMP *pre = pre_;
 
        if (!pre)
                return;
        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;
        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_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;
        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;
        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;
 
        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)
 
        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;
        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;
 
        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);
 
        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;
        if (points)
                {
                EC_POINT **p;