Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[Christophe Gouault]

Dear netdev developers,

The call to xfrm_find_acq_byseq() by the pfkey_getspi() and 
xfrm_alloc_userspi() functions is quite costly and proves to entail 
scalability issues when performing thousands of IKE negotiations with 
racoon (from ipsec-tools distribution) or charon (from strongswan 
distribution).

Removing this call in the kernel drastically accelerates the processing 
and does not seem to entail functional problems.

For now, I don't see the point of this call. I need to understand its 
purpose, because I'm highly tempted to simply remove it.

Regards,
Christophe

> Dear netdev developers,
>
> I would like to understand why the pfkey_getspi and xfrm_alloc_userspi
> functions call xfrm_find_acq_byseq() and try to find an reuse an SA in
> state XFRM_STATE_ACQ with the same sequence number and destination
> address as the GETSPI request.
>
> As far as I understand, SAs in state XFRM_STATE_ACQ can only be created
> as a result of a user call to GETSPI or a kernel ACQUIRE message.
> - GETSPI is invoked by an application in order to create a temporary SA
> with a unique SPI, typically during an IKE negotiation, to create the
> inbound SA of the pair. No later GETSPI will be done on this SA.
> - An acquire message is triggered by the kernel and creates a temporary
> outbound SA whose SPI will be chosen by the remote IKE peer.
> No later GETSPI will be done on this SA.
>
> In which case can GETSPI find and reuse an SA that matches the message
> sequence number and destination address?
> A second lookup is done just after, with xfrm_find_acq (this function
> uses a hash table). Wouldn't this lookup find this SA too?
>
> The call to xfrm_find_acq_byseq is quite costly (the whole SAD is looked
> up every time GETSPI is called), so I'd like to understand what its
> purpose is.
>
> Thanks in advance,
>
> Christophe

Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[David Miller]

From: Christophe Gouault <christophe.gouault@6wind.com>
Date: Thu, 19 Aug 2010 14:55:21 +0200

> The call to xfrm_find_acq_byseq() by the pfkey_getspi() and
> xfrm_alloc_userspi() functions is quite costly and proves to entail
> scalability issues when performing thousands of IKE negotiations with
> racoon (from ipsec-tools distribution) or charon (from strongswan
> distribution).
> 
> Removing this call in the kernel drastically accelerates the
> processing and does not seem to entail functional problems.
> 
> For now, I don't see the point of this call. I need to understand its
> purpose, because I'm highly tempted to simply remove it.

First of all, removing a function because you don't understand
why it's there is rarely a good idea :-)

I think the semantics require that we check for existing ACQUIRE
state entries before we allocate an SPI.

The likelyhood of breaking something if you remove the call is very
high.

Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[Christophe Gouault]

Hi David,

First of all, thank you for your answer.

David Miller wrote:
> From: Christophe Gouault <christophe.gouault@6wind.com>
> Date: Thu, 19 Aug 2010 14:55:21 +0200
>
>> The call to xfrm_find_acq_byseq() by the pfkey_getspi() and
>> xfrm_alloc_userspi() functions is quite costly and proves to entail
>> scalability issues when performing thousands of IKE negotiations with
>> racoon (from ipsec-tools distribution) or charon (from strongswan
>> distribution).
>>
>> Removing this call in the kernel drastically accelerates the
>> processing and does not seem to entail functional problems.
>>
>> For now, I don't see the point of this call. I need to understand its
>> purpose, because I'm highly tempted to simply remove it.
> First of all, removing a function because you don't understand
> why it's there is rarely a good idea :-)
Yes, don't worry, I never act that way. I was deliberately a little 
provocative ;-)
> I think the semantics require that we check for existing ACQUIRE
> state entries before we allocate an SPI.
Well, I still don't see in which case this can happen. The only 
situations in which an ACQUIRE state entry is created is when an acquire 
message is raised by the kernel (this creates a temporary outbound 
state) or when a getspi is issued from the userland (this creates a 
temporary state, as far as I know, this is the future inbound state 
negotiated by IKE).

In my humble opinion, issuing a getspi for the output state does not 
make sense since the SPI is chosen by the destination host.
So the possibly existing ACQUIRE state entry would be the result of a 
former getspi with the same value of the seq field. So this call would 
aim at cancelling a former call to getspi, maybe to cope with an 
application that would retry a failed negotiation before the former 
getspi expired?... I'm not really convinced by this explanation.

But there are maybe other uses of the getspi call than assigning a SPI 
for the inbound state of an IKE negotiation...
> The likelyhood of breaking something if you remove the call is very
> high.
Probably. I'm still interested in a concrete example ;-)

Christophe

Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[Christophe Gouault]

Christophe Gouault wrote:
> Hi David,
>
> First of all, thank you for your answer.
>
> David Miller wrote:
>> From: Christophe Gouault <christophe.gouault@6wind.com>
>> Date: Thu, 19 Aug 2010 14:55:21 +0200
>>
>>> The call to xfrm_find_acq_byseq() by the pfkey_getspi() and
>>> xfrm_alloc_userspi() functions is quite costly and proves to entail
>>> scalability issues when performing thousands of IKE negotiations with
>>> racoon (from ipsec-tools distribution) or charon (from strongswan
>>> distribution).
>>>
>>> Removing this call in the kernel drastically accelerates the
>>> processing and does not seem to entail functional problems.
>>>
>>> For now, I don't see the point of this call. I need to understand its
>>> purpose, because I'm highly tempted to simply remove it.
>> First of all, removing a function because you don't understand
>> why it's there is rarely a good idea :-)
> Yes, don't worry, I never act that way. I was deliberately a little 
> provocative ;-)
>> I think the semantics require that we check for existing ACQUIRE
>> state entries before we allocate an SPI.
> Well, I still don't see in which case this can happen. The only 
> situations in which an ACQUIRE state entry is created is when an 
> acquire message is raised by the kernel (this creates a temporary 
> outbound state) or when a getspi is issued from the userland (this 
> creates a temporary state, as far as I know, this is the future 
> inbound state negotiated by IKE).
>
> In my humble opinion, issuing a getspi for the output state does not 
> make sense since the SPI is chosen by the destination host.
> So the possibly existing ACQUIRE state entry would be the result of a 
> former getspi with the same value of the seq field. So this call would 
> aim at cancelling a former call to getspi,
Correction: it does not cancel the former call but returns the existing 
ACQUIRE state entry.

By the way, is it possible that the first call (to xfrm_find_acq_byseq) 
returns a state that the second call (to xfrm_find_acq) would not find?
> maybe to cope with an application that would retry a failed 
> negotiation before the former getspi expired?... I'm not really 
> convinced by this explanation.
>
> But there are maybe other uses of the getspi call than assigning a SPI 
> for the inbound state of an IKE negotiation...
>> The likelyhood of breaking something if you remove the call is very
>> high.
> Probably. I'm still interested in a concrete example ;-)
>
> Christophe

Re: IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[David Miller]

From: Christophe Gouault <christophe.gouault@6wind.com>
Date: Mon, 23 Aug 2010 16:47:18 +0200

> Christophe Gouault wrote:
>>> The likelyhood of breaking something if you remove the call is very
>>> high.
>> Probably. I'm still interested in a concrete example ;-)

Christophe, digging deep into the tree history I found a
commit that should answer your question:

commit 4d9f62e953567482223b7110c5e8961c4d494c1f
Author: Herbert Xu <herbert@gondor.apana.org.au>
Date:   Fri Sep 10 00:36:11 2004 -0700

    [IPSEC]: Find larval SAs by sequence number
    
    When larval states are generated along with ACQUIRE messages, we should
    use the sequence to find the corresponding larval state when creating
    states with ADD_SA or ALLOC_SPI.
    
    If we don't do that, then it may take down an unrelated larval state
    with the same parameters (think different TCP sessions).  This not only
    leaves behind a larval state that shouldn't be there, it may also cause
    another ACQUIRE message to be sent unnecessarily.
    
    Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
    Signed-off-by: David S. Miller <davem@davemloft.net>

diff --git a/include/net/xfrm.h b/include/net/xfrm.h
index 40c65db..b5c9b10 100644
--- a/include/net/xfrm.h
+++ b/include/net/xfrm.h
@@ -896,4 +896,17 @@ typedef void (icv_update_fn_t)(struct crypto_tfm *, struct scatterlist *, unsign
 extern void skb_icv_walk(const struct sk_buff *skb, struct crypto_tfm *tfm,
 			 int offset, int len, icv_update_fn_t icv_update);
 
+static inline int xfrm_addr_cmp(xfrm_address_t *a, xfrm_address_t *b,
+				int family)
+{
+	switch (family) {
+	default:
+	case AF_INET:
+		return a->a4 - b->a4;
+	case AF_INET6:
+		return ipv6_addr_cmp((struct in6_addr *)a,
+				     (struct in6_addr *)b);
+	}
+}
+
 #endif	/* _NET_XFRM_H */
diff --git a/net/key/af_key.c b/net/key/af_key.c
index 8ca25fd..b059fa2 100644
--- a/net/key/af_key.c
+++ b/net/key/af_key.c
@@ -1156,7 +1156,16 @@ static int pfkey_getspi(struct sock *sk, struct sk_buff *skb, struct sadb_msg *h
 		break;
 #endif
 	}
-	if (xdaddr)
+
+	if (hdr->sadb_msg_seq) {
+		x = xfrm_find_acq_byseq(hdr->sadb_msg_seq);
+		if (x && xfrm_addr_cmp(&x->id.daddr, xdaddr, family)) {
+			xfrm_state_put(x);
+			x = NULL;
+		}
+	}
+
+	if (!x)
 		x = xfrm_find_acq(mode, reqid, proto, xdaddr, xsaddr, 1, family);
 
 	if (x == NULL)
diff --git a/net/xfrm/xfrm_state.c b/net/xfrm/xfrm_state.c
index f45fa55..835c92a 100644
--- a/net/xfrm/xfrm_state.c
+++ b/net/xfrm/xfrm_state.c
@@ -387,13 +387,17 @@ void xfrm_state_insert(struct xfrm_state *x)
 	spin_unlock_bh(&xfrm_state_lock);
 }
 
+static struct xfrm_state *__xfrm_find_acq_byseq(u32 seq);
+
 int xfrm_state_add(struct xfrm_state *x)
 {
 	struct xfrm_state_afinfo *afinfo;
 	struct xfrm_state *x1;
+	int family;
 	int err;
 
-	afinfo = xfrm_state_get_afinfo(x->props.family);
+	family = x->props.family;
+	afinfo = xfrm_state_get_afinfo(family);
 	if (unlikely(afinfo == NULL))
 		return -EAFNOSUPPORT;
 
@@ -407,9 +411,18 @@ int xfrm_state_add(struct xfrm_state *x)
 		goto out;
 	}
 
-	x1 = afinfo->find_acq(
-		x->props.mode, x->props.reqid, x->id.proto,
-		&x->id.daddr, &x->props.saddr, 0);
+	if (x->km.seq) {
+		x1 = __xfrm_find_acq_byseq(x->km.seq);
+		if (x1 && xfrm_addr_cmp(&x1->id.daddr, &x->id.daddr, family)) {
+			xfrm_state_put(x1);
+			x1 = NULL;
+		}
+	}
+
+	if (!x1)
+		x1 = afinfo->find_acq(
+			x->props.mode, x->props.reqid, x->id.proto,
+			&x->id.daddr, &x->props.saddr, 0);
 
 	__xfrm_state_insert(x);
 	err = 0;
@@ -570,12 +583,11 @@ xfrm_find_acq(u8 mode, u32 reqid, u8 proto,
 
 /* Silly enough, but I'm lazy to build resolution list */
 
-struct xfrm_state * xfrm_find_acq_byseq(u32 seq)
+static struct xfrm_state *__xfrm_find_acq_byseq(u32 seq)
 {
 	int i;
 	struct xfrm_state *x;
 
-	spin_lock_bh(&xfrm_state_lock);
 	for (i = 0; i < XFRM_DST_HSIZE; i++) {
 		list_for_each_entry(x, xfrm_state_bydst+i, bydst) {
 			if (x->km.seq == seq) {
@@ -585,9 +597,18 @@ struct xfrm_state * xfrm_find_acq_byseq(u32 seq)
 			}
 		}
 	}
-	spin_unlock_bh(&xfrm_state_lock);
 	return NULL;
 }
+
+struct xfrm_state *xfrm_find_acq_byseq(u32 seq)
+{
+	struct xfrm_state *x;
+
+	spin_lock_bh(&xfrm_state_lock);
+	x = __xfrm_find_acq_byseq(seq);
+	spin_unlock_bh(&xfrm_state_lock);
+	return x;
+}
  
 u32 xfrm_get_acqseq(void)
 {
diff --git a/net/xfrm/xfrm_user.c b/net/xfrm/xfrm_user.c
index be298cd..db2087c 100644
--- a/net/xfrm/xfrm_user.c
+++ b/net/xfrm/xfrm_user.c
@@ -470,16 +470,32 @@ static int xfrm_alloc_userspi(struct sk_buff *skb, struct nlmsghdr *nlh, void **
 	struct xfrm_state *x;
 	struct xfrm_userspi_info *p;
 	struct sk_buff *resp_skb;
+	xfrm_address_t *daddr;
+	int family;
 	int err;
 
 	p = NLMSG_DATA(nlh);
 	err = verify_userspi_info(p);
 	if (err)
 		goto out_noput;
-	x = xfrm_find_acq(p->info.mode, p->info.reqid, p->info.id.proto,
-			  &p->info.id.daddr,
-			  &p->info.saddr, 1,
-			  p->info.family);
+
+	family = p->info.family;
+	daddr = &p->info.id.daddr;
+
+	x = NULL;
+	if (p->info.seq) {
+		x = xfrm_find_acq_byseq(p->info.seq);
+		if (x && xfrm_addr_cmp(&x->id.daddr, daddr, family)) {
+			xfrm_state_put(x);
+			x = NULL;
+		}
+	}
+
+	if (!x)
+		x = xfrm_find_acq(p->info.mode, p->info.reqid,
+				  p->info.id.proto, daddr,
+				  &p->info.saddr, 1,
+				  family);
 	err = -ENOENT;
 	if (x == NULL)
 		goto out_noput;

IPsec: Why do pfkey_getspi and xfrm_alloc_userspi call xfrm_find_acq_byseq?

[Christophe Gouault]

Dear netdev developers,

I would like to understand why the pfkey_getspi and xfrm_alloc_userspi
functions call xfrm_find_acq_byseq() and try to find an reuse an SA in
state XFRM_STATE_ACQ with the same sequence number and destination
address as the GETSPI request.

As far as I understand, SAs in state XFRM_STATE_ACQ can only be created
as a result of a user call to GETSPI or a kernel ACQUIRE message.
- GETSPI is invoked by an application in order to create a temporary SA
with a unique SPI, typically during an IKE negotiation, to create the
inbound SA of the pair. No later GETSPI will be done on this SA.
- An acquire message is triggered by the kernel and creates a temporary
outbound SA whose SPI will be chosen by the remote IKE peer.
No later GETSPI will be done on this SA.

In which case can GETSPI find and reuse an SA that matches the message
sequence number and destination address?
A second lookup is done just after, with xfrm_find_acq (this function
uses a hash table). Wouldn't this lookup find this SA too?

The call to xfrm_find_acq_byseq is quite costly (the whole SAD is looked
up every time GETSPI is called), so I'd like to understand what its
purpose is.

Thanks in advance,

Christophe