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

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;