Parallel crypto/IPsec v6

This patchset adds the 'pcrypt' parallel crypto template. With this template it is possible to process the crypto requests of a transform in parallel without getting request reorder. This is in particular interesting for IPsec.

The parallel crypto template is based on a generic parallelization/serialization method. This method uses the remote softirq invocation infrastructure for parallelization and serialization. With this method data objects can be processed in parallel, starting at some given point.
After doing some expensive operations in parallel, it is possible to serialize again. The parallelized data objects return after serialization in the order as they were before the parallelization. In the case of IPsec, this makes it possible to run the expensive parts in parallel without getting packet reordering.

Changes from v5:

- rebased to linux-2.6 git current

Changes from v4:

- Use the dynamic percpu allocator

- Drop of the obsolete eseqiv changes (eseqiv is the default IV generator for blockcipher algorithms on smp machines now).

Changes from v3:

- The generic aead wrapper is dropped.

- tcrypt is extended to test algorithms by name. So it is possible to instantiate pcrypt by doing e.g.:
modprobe tcrypt alg="pcrypt(authenc(hmac(sha1),cbc(aes)))" type=3

Changes from v2:

- The xfrm netlink configuration code is dropped,
this will be an extra patchset.

- Add generic aead wrapper interface to be able to wrap an aead algorithm with an arbitrary crypto template.

- Convert pcrypt to use the generic aead wrapper.

- Add support for aead algorithms to eseqiv.

- Add support for the pcrypt aead wrapper to authenc. It's now possible to choose for pcrypt as the default authenc wrapper with a module parameter.

- Patchset applies to linux-2.6 git current.

Changes from v1:

- cpu_chainiv is dropped, pcrypt uses eseqiv as it's IV generator now.

- Add a xfrm netlink message to be able to choose for pcrypt from userspace.

- Use pcrypt just if it is selected from userspace.

Steffen

This patch introduces an interface to process data objects in parallel. On request it is possible to serialize again. The parallelized objects return after serialization in the same order as they were before the parallelization.

---
 include/linux/interrupt.h  |    3 +-
 include/linux/padata.h     |  121 ++++++++++
 include/trace/events/irq.h |    1 +
 kernel/Makefile            |    2 +-
 kernel/padata.c            |  519 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/softirq.c           |    2 +-
 6 files changed, 645 insertions(+), 3 deletions(-)
 create mode 100644 include/linux/padata.h
 create mode 100644 kernel/padata.c

index b78cf81..1af1e4b 100644
@@ -350,7 +350,8 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
-	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
+	PADATA_SOFTIRQ,
+	RCU_SOFTIRQ, 	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
 };

index b89f9db..69584a5 100644
@@ -19,6 +19,7 @@
 			 softirq_name(TASKLET),		\
 			 softirq_name(SCHED),		\
 			 softirq_name(HRTIMER),		\
+			 softirq_name(padata),		\
 			 softirq_name(RCU))
 
 /**

index b8d4cd8..e8e2ecc 100644
@@ -41,7 +41,7 @@ obj-$(CONFIG_RT_MUTEXES) += rtmutex.o
 obj-$(CONFIG_DEBUG_RT_MUTEXES) += rtmutex-debug.o
 obj-$(CONFIG_RT_MUTEX_TESTER) += rtmutex-tester.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-obj-$(CONFIG_USE_GENERIC_SMP_HELPERS) += smp.o
+obj-$(CONFIG_USE_GENERIC_SMP_HELPERS) += smp.o padata.o
 ifneq ($(CONFIG_SMP),y)
 obj-y += up.o
 endif

index f8749e5..4317559 100644
@@ -58,7 +58,7 @@ static DEFINE_PER_CPU(struct task_struct *, ksoftirqd);
 
 char *softirq_to_name[NR_SOFTIRQS] = {
 	"HI", "TIMER", "NET_TX", "NET_RX", "BLOCK", "BLOCK_IOPOLL",
-	"TASKLET", "SCHED", "HRTIMER",	"RCU"
+	"TASKLET", "SCHED", "HRTIMER","PADATA",	"RCU"
 };
 
 /*

1.5.4.2

This patch adds a parallel crypto template that takes a crypto algorithm and converts it to process the crypto transforms in parallel. For the moment only aead is supported.

---
 crypto/Kconfig             |   13 ++
 crypto/Makefile            |    2 +
 crypto/pcrypt.c            |  409 ++++++++++++++++++++++++++++++++++++++++++++
 crypto/pcrypt_core.c       |  106 ++++++++++++
 include/crypto/pcrypt.h    |   51 ++++++
 include/linux/interrupt.h  |    2 +
 include/trace/events/irq.h |    2 +
 kernel/softirq.c           |    3 +-
 8 files changed, 587 insertions(+), 1 deletions(-)
 create mode 100644 crypto/pcrypt.c
 create mode 100644 crypto/pcrypt_core.c
 create mode 100644 include/crypto/pcrypt.h

index 26b5dd0..ce1bc59 100644
@@ -114,6 +114,19 @@ config CRYPTO_NULL
 	help
 	  These are 'Null' algorithms, used by IPsec, which do nothing.
 
+config CRYPTO_PCRYPT_CORE
+	bool
+
+config CRYPTO_PCRYPT
+	tristate "Parallel crypto engine (EXPERIMENTAL)"
+	depends on USE_GENERIC_SMP_HELPERS && EXPERIMENTAL
+	select CRYPTO_MANAGER
+	select CRYPTO_PCRYPT_CORE
+	select CRYPTO_AEAD
+	help
+	  This converts an arbitrary crypto algorithm into a parallel
+	  algorithm that is executed in a softirq.
+
 config CRYPTO_WORKQUEUE
        tristate
 

index 9e8f619..0d0d02d 100644
@@ -56,6 +56,8 @@ obj-$(CONFIG_CRYPTO_XTS) += xts.o
 obj-$(CONFIG_CRYPTO_CTR) += ctr.o
 obj-$(CONFIG_CRYPTO_GCM) += gcm.o
 obj-$(CONFIG_CRYPTO_CCM) += ccm.o
+obj-$(CONFIG_CRYPTO_PCRYPT_CORE) += pcrypt_core.o
+obj-$(CONFIG_CRYPTO_PCRYPT) += pcrypt.o
 obj-$(CONFIG_CRYPTO_CRYPTD) += cryptd.o
 obj-$(CONFIG_CRYPTO_DES) += des_generic.o
 obj-$(CONFIG_CRYPTO_FCRYPT) += fcrypt.o

index 1af1e4b..6bc5dde 100644
@@ -350,6 +350,8 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	AEAD_ENC_SOFTIRQ,
+	AEAD_DEC_SOFTIRQ,
 	PADATA_SOFTIRQ,
 	RCU_SOFTIRQ, 	/* Preferable RCU should always be the last softirq */
 

index 69584a5..ded7178 100644
@@ -19,6 +19,8 @@
 			 softirq_name(TASKLET),		\
 			 softirq_name(SCHED),		\
 			 softirq_name(HRTIMER),		\
+			 softirq_name(AEAD_ENC_SOFTIRQ),\
+			 softirq_name(AEAD_DEC_SOFTIRQ),\
 			 softirq_name(padata),		\
 			 softirq_name(RCU))
 

index 4317559..5f20baa 100644
@@ -58,7 +58,8 @@ static DEFINE_PER_CPU(struct task_struct *, ksoftirqd);
 
 char *softirq_to_name[NR_SOFTIRQS] = {
 	"HI", "TIMER", "NET_TX", "NET_RX", "BLOCK", "BLOCK_IOPOLL",
-	"TASKLET", "SCHED", "HRTIMER","PADATA",	"RCU"
+	"TASKLET", "SCHED", "HRTIMER", "AEAD_ENC_SOFTIRQ", "AEAD_DEC_SOFTIRQ",
+	"PADATA", "RCU"
 };
 
 /*

1.5.4.2

From: Steffen Klassert <[email protected]>
Date: Thu, 8 Oct 2009 09:28:18 +0200

I tried already to reduce the softirqs by using the same softirq for encryption and decryption. But in case of IPsec this had a negative performance impact. So if we stay with softirqs we would probaply need at least two for the whole crypto layer.

Best would be if we would not need softirqs at all. In fact I started with a thread based version but the thread based version had never that performance like the softirq version has.

Anyway, in between the workqueue interface changed so perhaps it is worth to try again with workqueues.

Tasklets are not sufficient because I can't control on which cpu the tasklet will run on. Also we can run just one tasklet of the same type the time, so tasklets don't parallelize.

I changed padata to use workqueues instead of softirqs to do the parallelization/serialization. The performance for IPsec is similar to the softirq version, so probaply we don't need to use softirqs at all.

While thinking about using workqueues for padata/pcrypt, I noticed two problems if we return asynchronous in thread context from the crypto-layer to xfrm. Returning in thread context is not new with pcrypt, we also can return in thread context if we use the cryptd.

If we use tunnel mode, xfrm_input() calls netif_rx() which is certainly wrong if we are in thread context, we need to call netif_rx_ni() instead. Also xfrm_input() uses bare spinlocks to protect the xfrm_state, this is not appropriate in this case. We probaply need to switch off the bottom halves, if we allow to return from the cypto-layer in softirq and thread context.

Any thoughts on how to handle this?

Since this is all happening through a crypto completion call, it needs to be done with BH off since that's a requirement for crypto completion functions. So netif_rx will work correctly as when BH is reenabled it'll pick up the packets.

This too should be fine with BH off.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Ok, if it's required that BHs are off then everything is fine. In fact I solved this problem for pcrypt by switching off the BHs. I just was not sure whether this is the right way to do.

Thanks for clarification!

I'm going to send a workqueue based version of padata/pcrypt within the next week.

Yeah having random contexts for completion functions would only create chaos :)

Awesome!

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

From: Herbert Xu <[email protected]>
Date: Fri, 30 Oct 2009 09:30:55 -0400

Thanks a lot for continuing this work Steffen.