Linux 2.6.28 and AEAD initialization

Linux 2.6.28 and AEAD initialization

[Andreas Steffen]

Hi,

with the Linux 2.6.28 kernel the first time xfrm_user.c:xfrm_add_sa()
is called with either "rfc4106(gcm(aes))" or "rfc4309(ccm(aes))",
an EEXIST error is returned and the installation of the IPsec SA fails.
A detailed analysis of the function calls (see trace added below) shows
that aead.c:crypto_lookup_aead() first loads

name         : rfc4106(gcm(aes))
driver       : rfc4106(gcm_base(ctr(aes-generic)))
module       : kernel
priority     : 100
refcnt       : 1
selftest     : passed
type         : nivaead
async        : yes
blocksize    : 1
ivsize       : 8
maxauthsize  : 16
geniv        : seqiv

Because of type=nivaead

    if (alg->cra_type == &crypto_aead_type)
        return alg;

crypto_lookup_aead() does not return the algorithm and falls through
to the statement

    return ERR_PTR(crypto_nivaead_default(alg, type, mask));

which makes another call to algapi.c;__crypto_register_alg().
Because the driver has already been installed

    ret = -EEXIST;
    ...

	if (crypto_is_larval(q)) {
	    if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
	        goto err;
	    continue;
	}

__crypto_register_alg() exits with the EEXIST error code.

The second time around the type=aead algorithm is additionally loaded

name         : rfc4106(gcm(aes))
driver       : rfc4106(gcm_base(ctr(aes-generic)))
module       : kernel
priority     : 100
refcnt       : 1
selftest     : passed
type         : aead
async        : yes
blocksize    : 1
ivsize       : 8
maxauthsize  : 16
geniv        : seqiv

name         : rfc4106(gcm(aes))
driver       : rfc4106(gcm_base(ctr(aes-generic)))
module       : kernel
priority     : 100
refcnt       : 1
selftest     : passed
type         : nivaead
async        : yes
blocksize    : 1
ivsize       : 8
maxauthsize  : 16
geniv        : seqiv

and the IPsec SAs can be set up successfully.

With the Linux 2.6.27.10 and earlier kernels the aead type is
loaded right at the beginning and no problems occur:

name         : rfc4106(gcm(aes))
driver       : rfc4106(gcm_base(ctr(aes-asm)))
module       : kernel
priority     : 200
refcnt       : 1
type         : aead
async        : yes
blocksize    : 1
ivsize       : 8
maxauthsize  : 16
geniv        : seqiv

name         : rfc4106(gcm(aes))
driver       : rfc4106(gcm_base(ctr(aes-asm)))
module       : kernel
priority     : 200
refcnt       : 1
type         : nivaead
async        : yes
blocksize    : 1
ivsize       : 8
maxauthsize  : 16
geniv        : seqiv

Best regards

Andreas

Trace of function calls returning EEXIST:

-----------------------------------------------------------------------------
net/xfrm/xfrm_user.c:xfrm_add_sa()
{
	x = xfrm_state_construct(p, attrs, &err);
	if (!x)
		return err;
}

-----------------------------------------------------------------------------
net/xfrm/xfrm_user.c:xfrm_state_construct()
{
	err = xfrm_init_state(x);
	if (err)
		goto error;
    ...
error:
	x->km.state = XFRM_STATE_DEAD;
	xfrm_state_put(x);
error_no_put:
	*errp = err;
	return NULL;
}

-----------------------------------------------------------------------------
net/xfrm/xfrm_state.c:xfrm_init_state()
{
	x->type = xfrm_get_type(x->id.proto, family);
	if (x->type == NULL)
		goto error;

	err = x->type->init_state(x);
	if (err)
		goto error;
    ...
error:
	return err;
}

-----------------------------------------------------------------------------
linux/net/xfrm.h:struct xfrm_type
{
	char			*description;
	struct module		*owner;
	__u8			proto;
	__u8			flags;
#define XFRM_TYPE_NON_FRAGMENT	1
#define XFRM_TYPE_REPLAY_PROT	2
#define XFRM_TYPE_LOCAL_COADDR	4
#define XFRM_TYPE_REMOTE_COADDR	8

	int			(*init_state)(struct xfrm_state *x);
	void			(*destructor)(struct xfrm_state *);
	int			(*input)(struct xfrm_state *, struct sk_buff *skb);
	int			(*output)(struct xfrm_state *, struct sk_buff *pskb);
	int			(*reject)(struct xfrm_state *, struct sk_buff *, struct flowi *);
	int			(*hdr_offset)(struct xfrm_state *, struct sk_buff *, u8 **);
	/* Estimate maximal size of result of transformation of a dgram */
	u32			(*get_mtu)(struct xfrm_state *, int size);
};

-----------------------------------------------------------------------------
net/ipv4/esp4.c:esp_init_state()
{
	if (x->aead)
		err = esp_init_aead(x);
	}
	else
		err = esp_init_authenc(x);

	if (err)
		goto error;

}

-----------------------------------------------------------------------------
net/ipv4/esp4.c:esp_init_aead()
{
	struct esp_data *esp = x->data;
	struct crypto_aead *aead;
	int err;

	aead = crypto_alloc_aead(x->aead->alg_name, 0, 0);
	err = PTR_ERR(aead);
	if (IS_ERR(aead))
		goto error;

error:
	return err;
}

-----------------------------------------------------------------------------
crypto/aead.c:crypto_alloc_aead()
{
		alg = crypto_lookup_aead(alg_name, type, mask);
		if (IS_ERR(alg)) {
			err = PTR_ERR(alg);
			goto err;
		}

err:
		if (err != -EAGAIN)
			break;
		if (signal_pending(current)) {
			err = -EINTR;
			break;
		}
	}

	return ERR_PTR(err);
}

-----------------------------------------------------------------------------
crypto/aead.c:crypto_lookup_aead()
{
	struct crypto_alg *alg;

	alg = crypto_alg_mod_lookup(name, type, mask);
	if (IS_ERR(alg))
		return alg;

    /* after the first call alg->cra_type is &crypto_nivaead_type */

	if (alg->cra_type == &crypto_aead_type)
		return alg;

	if (!alg->cra_aead.ivsize)
		return alg;

	return ERR_PTR(crypto_nivaead_default(alg, type, mask));
}

-----------------------------------------------------------------------------
crypto/aead.c:crypto_nivaead_default()
{
	if ((err = crypto_register_instance(tmpl, inst))) {
		tmpl->free(inst);
		goto put_tmpl;
	}

	/* Redo the lookup to use the instance we just registered. */
	err = -EAGAIN;

put_tmpl:
	crypto_tmpl_put(tmpl);
kill_larval:
	crypto_larval_kill(larval);
drop_larval:
	crypto_mod_put(larval);
out:
	crypto_mod_put(alg);
	return err;
}

-----------------------------------------------------------------------------
crypto/algapi.c:crypto_register_instance()
{
	larval = __crypto_register_alg(&inst->alg);
	if (IS_ERR(larval))
		goto unlock;

	hlist_add_head(&inst->list, &tmpl->instances);
	inst->tmpl = tmpl;

unlock:
	up_write(&crypto_alg_sem);

	err = PTR_ERR(larval);
	if (IS_ERR(larval))
		goto err;

	crypto_wait_for_test(larval);
	err = 0;

err:
	return err;
}

-----------------------------------------------------------------------------
crypto/algapi.c:__crypto_register_alg()
{
	ret = -EEXIST;
    ...

		if (crypto_is_larval(q)) {
			if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
				goto err;
			continue;
		}
}

Uff!

======================================================================
Andreas Steffen                         andreas.steffen@strongswan.org
strongSwan - the Linux VPN Solution!                www.strongswan.org
              Institute for Internet Technologies and Applications
University of Applied Sciences Rapperswil
CH-8640 Rapperswil (Switzerland)
===========================================================[ITA-HSR]==

Re: Linux 2.6.28 and AEAD initialization

[Herbert Xu]

On Wed, Jan 21, 2009 at 02:29:48AM +0000, Andreas Steffen wrote:
> 
> Because of type=nivaead
> 
>     if (alg->cra_type == &crypto_aead_type)
>         return alg;
> 
> crypto_lookup_aead() does not return the algorithm and falls through
> to the statement
> 
>     return ERR_PTR(crypto_nivaead_default(alg, type, mask));
> 
> which makes another call to algapi.c;__crypto_register_alg().
> Because the driver has already been installed
> 
>     ret = -EEXIST;
>     ...
> 
> 	if (crypto_is_larval(q)) {
> 	    if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
> 	        goto err;
> 	    continue;
> 	}
> 
> __crypto_register_alg() exits with the EEXIST error code.

This can only happen if we find a larval q with a matching driver
name, i.e., there is still an outstanding test on this driver.

Actually I see where the problem is.  When we complete the test
we're notifying everyone of the completion before we take the
test larval off the list.  So if one of the notified parties tries
to register another driver with the same name, then we hit this
error.  This is exactly what aead and givcipher tries to do.

Does this patch help?

crypto: api - Fix algorithm test race that broke aead initialisation

When we complete a test we'll notify everyone waiting on it, drop
the mutex, and then remove the test larval (after reacquiring the
mutex).  If one of the notified parties tries to register another
algorithm with the same driver name prior to the removal of the
test larval, they will fail with EEXIST as only one algorithm of
a given name can be tested at any time.

This broke the initialisation of aead and givcipher algorithms as
they will register two algorithms with the same driver name, in
sequence.

This patch fixes the problem by marking the larval as dead before
we drop the mutex, and also ignoring all dead or dying algorithms
on the registration path.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/crypto/algapi.c b/crypto/algapi.c
index 7c41e74..56c62e2 100644
--- a/crypto/algapi.c
+++ b/crypto/algapi.c
@@ -149,6 +149,9 @@ static struct crypto_larval *__crypto_register_alg(struct crypto_alg *alg)
 		if (q == alg)
 			goto err;
 
+		if (crypto_is_moribund(q))
+			continue;
+
 		if (crypto_is_larval(q)) {
 			if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
 				goto err;
@@ -197,7 +200,7 @@ void crypto_alg_tested(const char *name, int err)
 
 	down_write(&crypto_alg_sem);
 	list_for_each_entry(q, &crypto_alg_list, cra_list) {
-		if (!crypto_is_larval(q))
+		if (crypto_is_moribund(q) || !crypto_is_larval(q))
 			continue;
 
 		test = (struct crypto_larval *)q;
@@ -210,6 +213,7 @@ void crypto_alg_tested(const char *name, int err)
 	goto unlock;
 
 found:
+	q->cra_flags |= CRYPTO_ALG_DEAD;
 	alg = test->adult;
 	if (err || list_empty(&alg->cra_list))
 		goto complete;

Thanks,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: Linux 2.6.28 and AEAD initialization

[Andreas Steffen]

Hi Herbert,

your patch fixes the initialization problem!

Thanks

Andreas

Herbert Xu wrote:
> On Wed, Jan 21, 2009 at 02:29:48AM +0000, Andreas Steffen wrote:
>> Because of type=nivaead
>>
>>     if (alg->cra_type == &crypto_aead_type)
>>         return alg;
>>
>> crypto_lookup_aead() does not return the algorithm and falls through
>> to the statement
>>
>>     return ERR_PTR(crypto_nivaead_default(alg, type, mask));
>>
>> which makes another call to algapi.c;__crypto_register_alg().
>> Because the driver has already been installed
>>
>>     ret = -EEXIST;
>>     ...
>>
>> 	if (crypto_is_larval(q)) {
>> 	    if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
>> 	        goto err;
>> 	    continue;
>> 	}
>>
>> __crypto_register_alg() exits with the EEXIST error code.
> 
> This can only happen if we find a larval q with a matching driver
> name, i.e., there is still an outstanding test on this driver.
> 
> Actually I see where the problem is.  When we complete the test
> we're notifying everyone of the completion before we take the
> test larval off the list.  So if one of the notified parties tries
> to register another driver with the same name, then we hit this
> error.  This is exactly what aead and givcipher tries to do.
> 
> Does this patch help?
> 
> crypto: api - Fix algorithm test race that broke aead initialisation
> 
> When we complete a test we'll notify everyone waiting on it, drop
> the mutex, and then remove the test larval (after reacquiring the
> mutex).  If one of the notified parties tries to register another
> algorithm with the same driver name prior to the removal of the
> test larval, they will fail with EEXIST as only one algorithm of
> a given name can be tested at any time.
> 
> This broke the initialisation of aead and givcipher algorithms as
> they will register two algorithms with the same driver name, in
> sequence.
> 
> This patch fixes the problem by marking the larval as dead before
> we drop the mutex, and also ignoring all dead or dying algorithms
> on the registration path.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> diff --git a/crypto/algapi.c b/crypto/algapi.c
> index 7c41e74..56c62e2 100644
> --- a/crypto/algapi.c
> +++ b/crypto/algapi.c
> @@ -149,6 +149,9 @@ static struct crypto_larval *__crypto_register_alg(struct crypto_alg *alg)
>  		if (q == alg)
>  			goto err;
>  
> +		if (crypto_is_moribund(q))
> +			continue;
> +
>  		if (crypto_is_larval(q)) {
>  			if (!strcmp(alg->cra_driver_name, q->cra_driver_name))
>  				goto err;
> @@ -197,7 +200,7 @@ void crypto_alg_tested(const char *name, int err)
>  
>  	down_write(&crypto_alg_sem);
>  	list_for_each_entry(q, &crypto_alg_list, cra_list) {
> -		if (!crypto_is_larval(q))
> +		if (crypto_is_moribund(q) || !crypto_is_larval(q))
>  			continue;
>  
>  		test = (struct crypto_larval *)q;
> @@ -210,6 +213,7 @@ void crypto_alg_tested(const char *name, int err)
>  	goto unlock;
>  
>  found:
> +	q->cra_flags |= CRYPTO_ALG_DEAD;
>  	alg = test->adult;
>  	if (err || list_empty(&alg->cra_list))
>  		goto complete;
> 
> Thanks,

======================================================================
Andreas Steffen                         andreas.steffen@strongswan.org
strongSwan - the Linux VPN Solution!                www.strongswan.org

Institute for Internet Technologies and Applications
University of Applied Sciences Rapperswil
CH-8640 Rapperswil (Switzerland)
===========================================================[ITA-HSR]==

Re: Linux 2.6.28 and AEAD initialization

[Herbert Xu]

On Wed, Jan 28, 2009 at 01:18:57AM +0100, Andreas Steffen wrote:
> Hi Herbert,
> 
> your patch fixes the initialization problem!

Thanks for testing! I'll push this fix out.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt