[PATCH 01/04] Adding cipher mode context information to crypto_tfm

[PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

This patch adds the ability for a cipher mode to store cipher mode specific
information in crypto_tfm. This is necessary for LRW's precomputed
GF-multiplication tables.

Signed-off-by: Fruhwirth Clemens <clemens@endorphin.org>
 
--- 0/crypto/api.c	2005-01-20 10:15:22.000000000 +0100
+++ 1/crypto/api.c	2005-01-20 10:15:40.000000000 +0100
@@ -3,6 +3,7 @@
  *
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  * Copyright (c) 2002 David S. Miller (davem@redhat.com)
+ * Copyright (c) 2004 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * Portions derived from Cryptoapi, by Alexander Kjeldaas <astor@fast.no>
  * and Nettle, by Niels M�ller.
@@ -23,6 +24,14 @@
 LIST_HEAD(crypto_alg_list);
 DECLARE_RWSEM(crypto_alg_sem);
 
+static inline int crypto_cmctx_size(u32 flags) 
+{
+	switch(flags & CRYPTO_TFM_MODE_MASK) {
+		default:
+			return 0;
+	}
+}
+
 static inline int crypto_alg_get(struct crypto_alg *alg)
 {
 	return try_module_get(alg->cra_module);
@@ -121,16 +130,18 @@
 {
 	struct crypto_tfm *tfm = NULL;
 	struct crypto_alg *alg;
+	int tfm_size;
 
 	alg = crypto_alg_mod_lookup(name);
 	if (alg == NULL)
 		goto out;
 	
-	tfm = kmalloc(sizeof(*tfm) + alg->cra_ctxsize, GFP_KERNEL);
+	tfm_size = sizeof(*tfm) + alg->cra_ctxsize + crypto_cmctx_size(flags);
+	tfm = kmalloc(tfm_size, GFP_KERNEL);
 	if (tfm == NULL)
 		goto out_put;
 
-	memset(tfm, 0, sizeof(*tfm) + alg->cra_ctxsize);
+	memset(tfm, 0, tfm_size);
 	
 	tfm->__crt_alg = alg;
 	
@@ -156,7 +167,7 @@
 void crypto_free_tfm(struct crypto_tfm *tfm)
 {
 	struct crypto_alg *alg = tfm->__crt_alg;
-	int size = sizeof(*tfm) + alg->cra_ctxsize;
+	int size = sizeof(*tfm) + alg->cra_ctxsize + crypto_cmctx_size(tfm->crt_cipher.cit_mode);
 
 	crypto_exit_ops(tfm);
 	crypto_alg_put(alg);
--- 0/crypto/internal.h	2005-01-20 10:15:22.000000000 +0100
+++ 1/crypto/internal.h	2005-01-20 10:15:40.000000000 +0100
@@ -47,6 +47,11 @@
 	return (void *)&tfm[1];
 }
 
+static inline void *crypto_tfm_cmctx(struct crypto_tfm *tfm)
+{
+	return ((char *)&tfm[1]) + tfm->__crt_alg->cra_ctxsize;
+}
+
 struct crypto_alg *crypto_alg_lookup(const char *name);
 
 /* A far more intelligent version of this is planned.  For now, just

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

I'll review this in detail over the next day or so (still catching up on 
some backlog after vacation).

Just wondering how much testing the generic scatterwalk code has had (I 
gather disk encryption has been tested, but what about ipsec?).


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Andrew Morton]

Fruhwirth Clemens <clemens@endorphin.org> wrote:
>
> This patch adds the ability for a cipher mode to store cipher mode specific
> information in crypto_tfm. This is necessary for LRW's precomputed
> GF-multiplication tables.

These patches clash badly with Michael Ludvig's work:

ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-prepare-for-processing-multiple-buffers-at.patch
ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-update-padlock-to-process-multiple-blocks-at.patch

so someone's going to have to rework things.  Ordinarily Michael would go
first due to test coverage.

James, your call please.  Also, please advise on the suitability of
Michael's patches for a 2.6.11 merge.

Thanks.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 2179 bytes --]

On Mon, 2005-01-24 at 14:31 -0800, Andrew Morton wrote:
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> >
> > This patch adds the ability for a cipher mode to store cipher mode specific
> > information in crypto_tfm. This is necessary for LRW's precomputed
> > GF-multiplication tables.
> 
> These patches clash badly with Michael Ludvig's work:
> 
> ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-prepare-for-processing-multiple-buffers-at.patch
> ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-update-padlock-to-process-multiple-blocks-at.patch
> 
> so someone's going to have to rework things.  Ordinarily Michael would go
> first due to test coverage.

I already pointed that out to Michael. His reply was that he will look
at my tweakable extensions.

Let me bring forward a proposal to the multiblock function lookup of
Michael's patch in crypt(..)

I think this selection should be done much earlier, in
crypto_init_cipher_flags. The tfm's encrypt/decrypt interfaces (there
are three ATM, ECB, IV-based, tweak-based) should be initialized with an
appropriate pointer to a stub multiblock function, if there is one for
the given cipher mode and the given interface type. 

Either this function is a stub like for instance my cbc_process_gw or
it's a stub for a multiblock function, that do the necessary
preprocessing (kmalloc). Both can then call the generic scatterwalker
after that. The different number of arguments are _no_ problem for the
generic scatterwalker, that's what it was designed for.

If the stub is for a software call, then we won't have to do the
somewhat expensive aligned kmalloc call, as this isn't needed for
software anyway. In the software implementation, one can set the .buf
field of the scatterwalker's walk_info to a stack based buffer, and in
the multiblock version, just do the kmalloc. My design allows any
variation. 

That would be a way to deconcentrate the two code paths in crypt(..).

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Mon, 24 Jan 2005, Andrew Morton wrote:

> These patches clash badly with Michael Ludvig's work:
> 
> ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-prepare-for-processing-multiple-buffers-at.patch
> ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-update-padlock-to-process-multiple-blocks-at.patch
> 
> so someone's going to have to rework things.  Ordinarily Michael would go
> first due to test coverage.
> 
> James, your call please.  Also, please advise on the suitability of
> Michael's patches for a 2.6.11 merge.

I think the generic scatterwalk changes are more important and 
fundamental (still to be fully reviewed).

I agree with Fruhwirth that the cipher code is starting to become
ungainly.  I'm not sure these patches are heading in the right direction 
from a design point of view, although we do need the functionality.  

Perhaps temporarily drop the multible block changes above until we get the
generic scatterwalk code in and a cleaned up design to handle cipher mode
offload.

Fruhwirth, do you have any cycles to work on implementing your ideas for 
more cleanly reworking Michal's multiblock code?

Also, I would think this is more 2.6.12 material, at this stage.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1557 bytes --]

On Tue, 2005-01-25 at 10:52 -0500, James Morris wrote:

> I think the generic scatterwalk changes are more important and 
> fundamental (still to be fully reviewed).
> 
> I agree with Fruhwirth that the cipher code is starting to become
> ungainly.  I'm not sure these patches are heading in the right direction 
> from a design point of view, although we do need the functionality.  
> 
> Perhaps temporarily drop the multible block changes above until we get the
> generic scatterwalk code in and a cleaned up design to handle cipher mode
> offload.
> 
> Fruhwirth, do you have any cycles to work on implementing your ideas for 
> more cleanly reworking Michal's multiblock code?

The changes, I purposed, shouldn't be too hard to implement. I will
build a skeleton for Michael, but I can't test the code, as I don't own
a padlock system, further, I'm sorry to say but, my time is somehow
constrained.. I really gotta start to write my diploma thesis, I'm
delaying this for too long for crypto stuff now.

But before I put that into the my queue, I would like to see some kind
of decision on an async crypto framework. acrypto cames with hardware
support. So, are we heading for hardware support in cryptoapi, hardware
support in acrypto, acrypto instead of cryptoapi, OCF instead of
cryptoapi, or put everything into the kernel and export 3 interface? 

And how - when there is more than one interface - are these projects
going to reuse code?

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Tue, 25 Jan 2005, Fruhwirth Clemens wrote:

> The changes, I purposed, shouldn't be too hard to implement. I will
> build a skeleton for Michael, but I can't test the code, as I don't own
> a padlock system, further

I've got one now, and can use it for testing.

> I'm sorry to say but, my time is somehow
> constrained.. I really gotta start to write my diploma thesis, I'm
> delaying this for too long for crypto stuff now.
> 
> But before I put that into the my queue, I would like to see some kind
> of decision on an async crypto framework. acrypto cames with hardware
> support. So, are we heading for hardware support in cryptoapi, hardware
> support in acrypto, acrypto instead of cryptoapi, OCF instead of
> cryptoapi, or put everything into the kernel and export 3 interface? 

Exact details are unknown at this stage.  If we can get permission to use
OCF, then we need to work out what's best.

> And how - when there is more than one interface - are these projects
> going to reuse code?

I would imagine so.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 2581 bytes --]

On Tue, 2005-01-25 at 10:52 -0500, James Morris wrote:
> On Mon, 24 Jan 2005, Andrew Morton wrote:
> 
> > These patches clash badly with Michael Ludvig's work:
> > 
> > ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-prepare-for-processing-multiple-buffers-at.patch
> > ftp://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.11-rc2/2.6.11-rc2-mm1/broken-out/cryptoapi-update-padlock-to-process-multiple-blocks-at.patch
> > 
> > so someone's going to have to rework things.  Ordinarily Michael would go
> > first due to test coverage.
> > 
> > James, your call please.  Also, please advise on the suitability of
> > Michael's patches for a 2.6.11 merge.
>
> Perhaps temporarily drop the multible block changes above until we get the
> generic scatterwalk code in and a cleaned up design to handle cipher mode
> offload.

Andrew, do you agree with James on dropping this patches temporarily?
I'm running into a mess with patches for patches, and I'd be easier for
me to have my scatterwalk code in -mm to build on.

James, anything new on ipsec testing? Is there something else missing
for a "GO" from your side for scatterwalk generic?

I'm almost finished with my port of Michaels multiblock extensions, but
I run into a few single problems.

First, I'd set the bytes, a multiblock call can digest, to 4096, page
size. Why? Because, the scatterwalk code, even James original
implementation, will trigger heavy memcpy because the needscratch check
will always return true for page boundary crossing sections.

ATM max_nbytes isn't set to 4096, but to ((size_t)-1), the maximum value
of size_t. This is algorithm specific and set in padlock implementation.
(My port will drop these changes). But setting it to 4096 causes another
problem: the last fragment of a run might be shorter than 4096, but the
scatterwalk code (James and mine) wasn't designed to
change the stepsize/blocksize dynamically. Therefore, Michaels addition
to crypt(..) will wrongly process the whole last 4096 block, trashing
all data remaining data. That's not likely to break things, but the
behavior is certainly wrong.

So a lot of slippery details here. My advise is, drop Michaels patches
for now, merge scatterwalker and add an ability to change the stepsize
dynamically in the run. Then I will finish my port and post it.

If we can agree on this "agenda", I'll shift my focus to scatterwalker
testing.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Andrew Morton]

Fruhwirth Clemens <clemens@endorphin.org> wrote:
>
> My advise is, drop Michaels patches
>  for now, merge scatterwalker and add an ability to change the stepsize
>  dynamically in the run. Then I will finish my port and post it.
> 
>  If we can agree on this "agenda", I'll shift my focus to scatterwalker
>  testing.

Sure.  Just work against Linus's tree.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Sat, Jan 29, 2005 at 10:23:10AM -0800, Andrew Morton wrote:
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> >
> > My advise is, drop Michaels patches
> >  for now, merge scatterwalker and add an ability to change the stepsize
> >  dynamically in the run. Then I will finish my port and post it.
> > 
> >  If we can agree on this "agenda", I'll shift my focus to scatterwalker
> >  testing.
> 
> Sure.  Just work against Linus's tree.
> 

Ok, here comes a reworked scatterwalk patch. Instead of making
scatterwalk_walk controllable via another additional function or interface,
I decided to make scatterwalk_walk quickly restartable. Therefore, I had to
move an initialization responsibility to the client.

I first planed to this with nice C99 designed structs and compound literals,
but in fact this C99 extension just sucks. It's useless, as compound
literals can't be used as initializers, making this concept at least half
useless. The worst thing of all is, gcc doesn't spill out an error, but just
does random things to your variables. 

GCC C99 ranting aside, this patch also fixes some failing test cases for
chunking across pages.

James, please test it against ipsec. I'm confident, that everything will
work as expected and we can proceed to merge padlock-multiblock against this
scatterwalker, so please Andrew, merge after a successful test of James.

This patch is diffed against 2.6.11-rc2 (Linus) + cipher mode context patch
http://lkml.org/lkml/2005/1/24/54 

 cipher.c      |  267 +++++++++++++++++++++++++++++++++-------------------------
 scatterwalk.c |  137 +++++++++++++++++++++--------
 scatterwalk.h |   37 +++++---
 3 files changed, 277 insertions(+), 164 deletions(-)

Signed-Off-By: Fruhwirth Clemens <clemens@endorphin.org>
--- 1/crypto/cipher.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/cipher.c	2005-01-30 18:45:55.332427200 +0100
@@ -38,94 +38,6 @@
 	((u32 *)a)[3] ^= ((u32 *)b)[3];
 }
 
-
-/* 
- * Generic encrypt/decrypt wrapper for ciphers, handles operations across
- * multiple page boundaries by using temporary blocks.  In user context,
- * the kernel is given a chance to schedule us once per block.
- */
-static int crypt(struct crypto_tfm *tfm,
-		 struct scatterlist *dst,
-		 struct scatterlist *src,
-                 unsigned int nbytes, cryptfn_t crfn,
-                 procfn_t prfn, int enc, void *info)
-{
-	struct scatter_walk walk_in, walk_out;
-	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
-	u8 tmp_src[bsize];
-	u8 tmp_dst[bsize];
-
-	if (!nbytes)
-		return 0;
-
-	if (nbytes % bsize) {
-		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
-		return -EINVAL;
-	}
-
-	scatterwalk_start(&walk_in, src);
-	scatterwalk_start(&walk_out, dst);
-
-	for(;;) {
-		u8 *src_p, *dst_p;
-		int in_place;
-
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
-		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
-		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
-		in_place = scatterwalk_samebuf(&walk_in, &walk_out,
-					       src_p, dst_p);
-
-		nbytes -= bsize;
-
-		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
-
-		prfn(tfm, dst_p, src_p, crfn, enc, info, in_place);
-
-		scatterwalk_done(&walk_in, 0, nbytes);
-
-		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
-		scatterwalk_done(&walk_out, 1, nbytes);
-
-		if (!nbytes)
-			return 0;
-
-		crypto_yield(tfm);
-	}
-}
-
-static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
-{
-	u8 *iv = info;
-	
-	/* Null encryption */
-	if (!iv)
-		return;
-		
-	if (enc) {
-		tfm->crt_u.cipher.cit_xor_block(iv, src);
-		fn(crypto_tfm_ctx(tfm), dst, iv);
-		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
-	} else {
-		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = in_place ? stack : dst;
-
-		fn(crypto_tfm_ctx(tfm), buf, src);
-		tfm->crt_u.cipher.cit_xor_block(buf, iv);
-		memcpy(iv, src, crypto_tfm_alg_blocksize(tfm));
-		if (buf != dst)
-			memcpy(dst, buf, crypto_tfm_alg_blocksize(tfm));
-	}
-}
-
-static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
-{
-	fn(crypto_tfm_ctx(tfm), dst, src);
-}
-
 static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
 {
 	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
@@ -138,43 +50,172 @@
 		                       &tfm->crt_flags);
 }
 
-static int ecb_encrypt(struct crypto_tfm *tfm,
-		       struct scatterlist *dst,
-                       struct scatterlist *src, unsigned int nbytes)
+/* 
+ * Electronic Code Book (ECB) mode implementation 
+ */
+
+struct ecb_process_priv {
+	struct crypto_tfm	*tfm;
+	cryptfn_t		*crfn;
+};
+
+static int ecb_process_gw(void *_priv, int nsg, void **buf) 
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             ecb_process, 1, NULL);
+	struct ecb_process_priv *priv = (struct ecb_process_priv *)_priv;
+	priv->crfn(crypto_tfm_ctx(priv->tfm), buf[0], buf[1]);
+	return 0;
 }
 
-static int ecb_decrypt(struct crypto_tfm *tfm,
+static inline int ecb_template(struct crypto_tfm *tfm,
+	               struct scatterlist *dst,
+                       struct scatterlist *src, unsigned int nbytes, cryptfn_t crfn)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct ecb_process_priv priv = { 
+		.tfm = tfm,
+		.crfn = crfn,
+	};
+
+	struct walk_info ecb_info[3];
+
+	scatterwalk_info_init(ecb_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(ecb_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(ecb_info+2);
+
+	if(!nbytes)
+		return 0;
+	if(nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	return scatterwalk_walk(ecb_process_gw, &priv, nbytes/bsize, ecb_info);
+}
+
+static int ecb_encrypt(struct crypto_tfm *tfm,
                        struct scatterlist *dst,
                        struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             ecb_process, 1, NULL);
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);
 }
 
-static int cbc_encrypt(struct crypto_tfm *tfm,
+static int ecb_decrypt(struct crypto_tfm *tfm,
                        struct scatterlist *dst,
                        struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, tfm->crt_cipher.cit_iv);
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_decrypt);
 }
 
+/* Cipher Block Chaining (CBC) mode implementation */
+
+struct cbc_process_priv {
+	struct crypto_tfm *tfm;
+	int enc;
+	cryptfn_t *crfn;
+	u8 *curIV;
+	u8 *nextIV;
+};
+
+static int cbc_process_gw(void *_priv, int nsg, void **buf) 
+{
+	struct cbc_process_priv *priv = (struct cbc_process_priv *)_priv;
+	u8 *iv = priv->curIV;
+	struct crypto_tfm *tfm = priv->tfm;
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	u8 *dst = buf[0];
+	u8 *src = buf[1];
+	
+	/* Null encryption */
+	if (!iv)
+		return 0;
+
+	if (priv->enc == CRYPTO_DIR_ENCRYPT) {
+		tfm->crt_u.cipher.cit_xor_block(iv, src);
+		priv->crfn(crypto_tfm_ctx(tfm), dst, iv);
+		memcpy(iv, dst, bsize);
+	} else {
+		memcpy(priv->nextIV,src,bsize);
+		priv->crfn(crypto_tfm_ctx(tfm), dst, src);
+		tfm->crt_u.cipher.cit_xor_block(dst, iv);
+		priv->curIV = priv->nextIV;
+		priv->nextIV = iv;
+	}
+	return 0;
+}
+
+
 static int cbc_encrypt_iv(struct crypto_tfm *tfm,
                           struct scatterlist *dst,
                           struct scatterlist *src,
                           unsigned int nbytes, u8 *iv)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, iv);
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_ENCRYPT,
+		.curIV = iv,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_encrypt
+	};
+
+	struct walk_info cbc_info[3];
+
+	if(!nbytes)
+		return 0;
+	if(nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT); 
+	scatterwalk_info_endtag(cbc_info+2);
+
+ 	return scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
+}
+
+static int cbc_decrypt_iv(struct crypto_tfm *tfm,
+                          struct scatterlist *dst,
+                          struct scatterlist *src,
+                          unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	int r = -EINVAL;
+
+	char scratch1[bsize]; 
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_DECRYPT,
+		.curIV = iv,
+		.nextIV = scratch1,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_decrypt,
+	};
+	struct walk_info cbc_info[3];
+
+	if(!nbytes)
+		return 0;
+	if(nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(cbc_info+2);
+
+	r = scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
+
+	if(priv.curIV != iv) 
+		memcpy(iv,priv.curIV,bsize);
+	return r;
 }
 
 static int cbc_decrypt(struct crypto_tfm *tfm,
@@ -182,19 +223,15 @@
                        struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, tfm->crt_cipher.cit_iv);
+	return cbc_decrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
-static int cbc_decrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
+static int cbc_encrypt(struct crypto_tfm *tfm,
+                       struct scatterlist *dst,
+                       struct scatterlist *src,
+		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, iv);
+	return cbc_encrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
 static int nocrypt(struct crypto_tfm *tfm,
--- 1/crypto/scatterwalk.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.h	2005-01-30 18:40:42.820936168 +0100
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  * Copyright (c) 2002 Adam J. Richter <adam@yggdrasil.com>
  * Copyright (c) 2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ * Copyright (c) 2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -16,6 +17,7 @@
 #define _CRYPTO_SCATTERWALK_H
 #include <linux/mm.h>
 #include <asm/scatterlist.h>
+#include <linux/pagemap.h>
 
 struct scatter_walk {
 	struct scatterlist	*sg;
@@ -26,6 +28,21 @@
 	unsigned int		offset;
 };
 
+struct walk_info {
+	struct scatter_walk   sw;
+	int                   stepsize;
+	int                   ioflag;
+	char                  *buf;
+};
+
+#define SCATTERWALK_IO_OUTPUT  1
+#define SCATTERWALK_IO_INPUT   0
+
+#define scatterwalk_needscratch(walk, nbytes) 						\
+	((nbytes) <= (walk)->len_this_page &&						\
+	    (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) + (nbytes) <=	\
+	    PAGE_CACHE_SIZE)								\
+
 /* Define sg_next is an inline routine now in case we want to change
    scatterlist to a linked list later. */
 static inline struct scatterlist *sg_next(struct scatterlist *sg)
@@ -33,19 +50,13 @@
 	return sg + 1;
 }
 
-static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
-				      struct scatter_walk *walk_out,
-				      void *src_p, void *dst_p)
-{
-	return walk_in->page == walk_out->page &&
-	       walk_in->offset == walk_out->offset &&
-	       walk_in->data == src_p && walk_out->data == dst_p;
-}
+typedef int (*sw_proc_func_t)(void *priv, int length, void **buflist);
+
+int scatterwalk_walk(sw_proc_func_t function, void *priv, int steps, struct walk_info *walk_info_l);
+
+#define scatterwalk_info_endtag(winfo) (winfo)->sw.sg = NULL;
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, int stepsize, void *buf, int io);
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
-void scatterwalk_map(struct scatter_walk *walk, int out);
-void scatterwalk_done(struct scatter_walk *walk, int out, int more);
 
 #endif  /* _CRYPTO_SCATTERWALK_H */
--- 1/crypto/scatterwalk.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.c	2005-01-30 18:45:15.489484248 +0100
@@ -6,6 +6,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  *               2002 Adam J. Richter <adam@yggdrasil.com>
  *               2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *               2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -28,17 +29,7 @@
 	KM_SOFTIRQ1,
 };
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
-{
-	if (nbytes <= walk->len_this_page &&
-	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
-	    PAGE_CACHE_SIZE)
-		return walk->data;
-	else
-		return scratch;
-}
-
-static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
+static inline void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
 {
 	if (out)
 		memcpy(sgdata, buf, nbytes);
@@ -46,7 +37,7 @@
 		memcpy(buf, sgdata, nbytes);
 }
 
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
+static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
 {
 	unsigned int rest_of_page;
 
@@ -60,11 +51,17 @@
 	walk->offset = sg->offset;
 }
 
-void scatterwalk_map(struct scatter_walk *walk, int out)
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, int stepsize, void *buf, int io)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	scatterwalk_start(&winfo->sw, sg);
+	winfo->stepsize = stepsize;
+	winfo->ioflag = io;
+	winfo->buf = buf;
 }
 
+#define scatterwalk_map(walk,out) \
+	(walk)->data = crypto_kmap((walk)->page, (out)) + (walk)->offset; 
+
 static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
 				 unsigned int more)
 {
@@ -89,36 +86,104 @@
 	}
 }
 
-void scatterwalk_done(struct scatter_walk *walk, int out, int more)
-{
-	crypto_kunmap(walk->data, out);
-	if (walk->len_this_page == 0 || !more)
-		scatterwalk_pagedone(walk, out, more);
-}
-
-/*
- * Do not call this unless the total length of all of the fragments
- * has been verified as multiple of the block size.
- */
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
+void scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
 			   size_t nbytes, int out)
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
-			memcpy_dir(buf, walk->data, walk->len_this_page, out);
-			buf += walk->len_this_page;
-			nbytes -= walk->len_this_page;
-
+			if(walk->len_this_page) {
+				memcpy_dir(buf, walk->data, walk->len_this_page, out);
+				buf += walk->len_this_page;
+				nbytes -= walk->len_this_page;
+                        }
 			crypto_kunmap(walk->data, out);
-			scatterwalk_pagedone(walk, out, 1);
+			scatterwalk_pagedone(walk, 
+					     out, 
+					     1); /* more processing steps */
 			scatterwalk_map(walk, out);
-		}
-
-		memcpy_dir(buf, walk->data, nbytes, out);
+		}			       
+		memcpy_dir(buf, walk->data, nbytes, out);			
 	}
-
+        walk->data += nbytes;
 	walk->offset += nbytes;
 	walk->len_this_page -= nbytes;
 	walk->len_this_segment -= nbytes;
-	return 0;
+}
+
+/*  
+ * The generic scatterwalker can manipulate data associated with one
+ * or more scatterlist with a processing function, pf. It's purpose is
+ * to hide the mapping, unalignment and page switching logic.
+ * 
+ * The generic scatterwalker applies a certain function, pf, utilising
+ * an arbitrary number of scatterlist data as it's arguments. These
+ * arguments are supplied as an array of pointers to buffers. These
+ * buffers are prepared and processed block-wise by the function
+ * (stepsize) and might be input or output buffers.
+ *
+ * All this informations and the underlaying scatterlist is handed to
+ * the generic walker as an array of descriptors of type
+ * walk_info. The sg, stepsize, ioflag and buf field of this struct
+ * must be initialised.
+ *
+ * The sg field points to the scatterlist the function should work on,
+ * the stepsize is the number of successive bytes that should be
+ * handed to the function, ioflag denotes input or output scatterlist
+ * and the buf field is either null, or points to a stepsize-width
+ * byte block, which can be used as copy buffer, when the stepsize
+ * does not align with page or scatterlist boundaries.
+ *
+ * A list of buffers are compiled and handed to the function, as char
+ * **buf, with buf[0] corresponds to the first walk_info descriptor,
+ * buf[1] to the second, and so on. The function is also handed a priv
+ * object, which does not change. Think of it as a "this" object, to
+ * collect/store processing information.
+ */
+
+int scatterwalk_walk(sw_proc_func_t pf, void *priv, int steps,
+			       struct walk_info *walk_infos) 
+{
+	int r = -EINVAL;
+	
+	int i;
+
+	struct walk_info *csg;
+	int nsl = 0;
+
+	void **cbuf;
+	void **dispatch_list;
+
+        for(csg = walk_infos; csg->sw.sg; csg++) {
+		scatterwalk_map(&csg->sw, csg->ioflag);
+		nsl++;
+	}
+
+	dispatch_list = (void *[nsl]){}; /* This alien thing is a C99 compound literal */
+
+	while(steps--) {
+		for(csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; i--, csg++, cbuf++) {
+			/* If a scratch is needed, do a lazy kmallocation */
+			*cbuf =	scatterwalk_needscratch(&csg->sw,csg->stepsize)?csg->sw.data:csg->buf;
+
+			if(csg->ioflag == 0)
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize,0);
+		}
+		
+		r = pf(priv, nsl, dispatch_list);
+		if(unlikely(r < 0))
+			goto out;
+
+		for(csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
+			if(csg->ioflag == 1) 
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize,1);
+		}
+	}
+
+	r = 0;
+ out:
+	for(csg = walk_infos; csg->sw.sg; csg++) {
+		crypto_kunmap(csg->sw.data, csg->ioflag);
+		scatterwalk_pagedone(&csg->sw, csg->ioflag, 0);
+	}
+	return r;
 }

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Sun, 30 Jan 2005, Fruhwirth Clemens wrote:

> Ok, here comes a reworked scatterwalk patch. Instead of making
> scatterwalk_walk controllable via another additional function or interface,
> I decided to make scatterwalk_walk quickly restartable. Therefore, I had to
> move an initialization responsibility to the client.
> 
> I first planed to this with nice C99 designed structs and compound literals,
> but in fact this C99 extension just sucks. It's useless, as compound
> literals can't be used as initializers, making this concept at least half
> useless. The worst thing of all is, gcc doesn't spill out an error, but just
> does random things to your variables. 
> 
> GCC C99 ranting aside, this patch also fixes some failing test cases for
> chunking across pages.
> 
> James, please test it against ipsec. I'm confident, that everything will
> work as expected and we can proceed to merge padlock-multiblock against this
> scatterwalker, so please Andrew, merge after a successful test of James.

This code tests ok with IPSec, and delivers some good performance
improvements.  e.g. FTP transfers over transport mode AES over GigE sped
up with this patch applied on one side of the connection by 20% for send
and 15% for receive.

There are quite a few coding style and minor issues to be fixed (per 
below), and the code should probably then be tested in the -mm tree for a 
while (2.6.11 is too soon for mainline merge).

> +static int ecb_process_gw(void *_priv, int nsg, void **buf) 

Please just use 'priv', the underscore is not neccessary.

What does _gw mean?

> -static int ecb_decrypt(struct crypto_tfm *tfm,
> +static inline int ecb_template(struct crypto_tfm *tfm,
> +	               struct scatterlist *dst,
> +                       struct scatterlist *src, unsigned int nbytes, cryptfn_t crfn)

Please fix alignment (elsewhere too).

> +	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);


Missing spaces, should be ecb_template(tfm, dst, src...) 

> +struct cbc_process_priv {
> +	struct crypto_tfm *tfm;
> +	int enc;
> +	cryptfn_t *crfn;
> +	u8 *curIV;
> +	u8 *nextIV;
> +};

No caps please, I suggest curr_iv and next_iv.

> +#define scatterwalk_needscratch(walk, nbytes) 						\
> +	((nbytes) <= (walk)->len_this_page &&						\
> +	    (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) + (nbytes) <=	\
> +	    PAGE_CACHE_SIZE)								\

This should be a static inline.

> +#define scatterwalk_info_endtag(winfo) (winfo)->sw.sg = NULL;

Ditto.

> +        for(csg = walk_infos; csg->sw.sg; csg++) {
> +		scatterwalk_map(&csg->sw, csg->ioflag);

Indending + coding style: should be for (...).

> +	while(steps--) {

while ()

> +		
> +		r = pf(priv, nsl, dispatch_list);
> +		if(unlikely(r < 0))
> +			goto out;

Not sure if the unlikely() is justified here, given that this is not a 
fast path.  I guess it doesn't do any harm.

> +		for(csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
> +			if(csg->ioflag == 1) 

for ()
if ()

> +	for(csg = walk_infos; csg->sw.sg; csg++) {

Ditto.



- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1781 bytes --]

On Wed, 2005-02-02 at 17:46 -0500, James Morris wrote:
> On Sun, 30 Jan 2005, Fruhwirth Clemens wrote:
> > James, please test it against ipsec. I'm confident, that everything will
> > work as expected and we can proceed to merge padlock-multiblock against this
> > scatterwalker, so please Andrew, merge after a successful test of James.
> 
> This code tests ok with IPSec, and delivers some good performance
> improvements.  e.g. FTP transfers over transport mode AES over GigE sped
> up with this patch applied on one side of the connection by 20% for send
> and 15% for receive.

Fine, nice to hear that!

> There are quite a few coding style and minor issues to be fixed (per 
> below), and the code should probably then be tested in the -mm tree for a 
> while (2.6.11 is too soon for mainline merge).
> 
> > +static int ecb_process_gw(void *_priv, int nsg, void **buf) 

> What does _gw mean?

generic walker.. can be removed, if you like.

> > +struct cbc_process_priv {
> > +	struct crypto_tfm *tfm;
> > +	int enc;
> > +	cryptfn_t *crfn;
> > +	u8 *curIV;
> > +	u8 *nextIV;
> > +};
> 
> No caps please, I suggest curr_iv and next_iv.

Ack, cipher.c is underscore style. But my LRW private helper lib
gfmulseq.c is going to stay lowerCamelCase. I hope that's ok for
everyone. If not, the one concerned should post a reformat patch.

> > +		r = pf(priv, nsl, dispatch_list);
> > +		if(unlikely(r < 0))
> > +			goto out;
> 
> Not sure if the unlikely() is justified here, given that this is not a 
> fast path.  I guess it doesn't do any harm.

I suspected unlikely to be a hint for the compiler to do better jump
prediction and speculations. Remove?

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[David S. Miller]

On Thu, 03 Feb 2005 00:28:29 +0100
Fruhwirth Clemens <clemens@endorphin.org> wrote:

> I suspected unlikely to be a hint for the compiler to do better jump
> prediction and speculations. Remove?

I don't think it hurts, keep it in there.

When the final patch is made with James's requested fixups, I'll stick
this into the 2.6.12 pending tree.

Also, I think there will be objections to that studlyCaps naming you
said your other code has.  Keep garbage like that in the x11 sources,
if you don't mind :-)

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 840 bytes --]

On Wed, 2005-02-02 at 15:34 -0800, David S. Miller wrote:

> Also, I think there will be objections to that studlyCaps naming you
> said your other code has.  Keep garbage like that in the x11 sources,
> if you don't mind :-)

I'm afraid, I'm not going to change it. I already lost too much time
pushing LRW into the kernel. 

Coding time: 3 days. Pushing time: 78 days and counting. 

I'm willing to cancel my work, as I've taken this to matter to an
extend, where my time sacrifice can hardly be justified. Especially, if
James ask me to redo Michal's conflicting patches (done btw), which are
totally off-topic for me. Then, I'm certainly not going to redo all my
code, just because someone thinks different about the naming of my
variables.
-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[David S. Miller]

On Thu, 03 Feb 2005 01:21:35 +0100
Fruhwirth Clemens <clemens@endorphin.org> wrote:

> I'm afraid, I'm not going to change it. I already lost too much time
> pushing LRW into the kernel.

The work has to be done by somebody.  Linus would certainly reject any
attempt I would make to push code with that kind of variable naming
in it.  So instead of blindly going:

1) dave try push to linus
2) linus says fix horrible variable studlyCaps names
3) dave asks patch submitter to fix
4) submitter submits new patch
5) dave retries pushing to linus

I'm reducing it to one step, by asking that it be done now, thus
saving a lot of wasted time on everyone's part.

Submitting your first major patch or set of changes can be incredibly
frustrating.  It took more than a year before people like Linus would
regularly and smoothly integrate my work, most of it would come right
back to me for fixups.

Don't worry though, if the work is truly variable, someone will pick
up the ball and do the necessary coding style fixups et al. to get it
integrated.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Michal Ludvig]

Fruhwirth Clemens wrote:

 > Especially, if James ask me to redo Michal's conflicting patches
 > (done btw), which are totally off-topic for me.

Great, thanks! Has the interface for multiblock modules changed or 
should my old modules work with it with no more effort?

Unfortulately I don't have a PadLock system running at the moment (it is 
still somewhere down in a wooden box after my moving), but if you send 
me the patch I could at least try to compile with my parts.

Thanks for that!

Michal Ludvig

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 879 bytes --]

On Thu, 2005-02-03 at 13:40 +1300, Michal Ludvig wrote:
> Fruhwirth Clemens wrote:
> 
>  > Especially, if James ask me to redo Michal's conflicting patches
>  > (done btw), which are totally off-topic for me.
> 
> Great, thanks! Has the interface for multiblock modules changed or 
> should my old modules work with it with no more effort?

Yes, changes are required. I fixed up padlock-aes.c along the way. So
don't worry if it's just padlock. 

The changes to the CryptoAPI core minimal, in fact, 10 lines, retaining
all the functionally of you original patch. I'll finalize/clean/post the
patch when the scatterwalk stuff is merged. Please have a look at the
scatterwalk code, because, as I don't have a padlock, you'll have the
joy of running my code for the very first time :)

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Thu, 3 Feb 2005, Fruhwirth Clemens wrote:

> > > +static int ecb_process_gw(void *_priv, int nsg, void **buf) 
> 
> > What does _gw mean?
> 
> generic walker.. can be removed, if you like.

That's fine, was just wondering.

> > > +		r = pf(priv, nsl, dispatch_list);
> > > +		if(unlikely(r < 0))
> > > +			goto out;
> > 
> > Not sure if the unlikely() is justified here, given that this is not a 
> > fast path.  I guess it doesn't do any harm.
> 
> I suspected unlikely to be a hint for the compiler to do better jump
> prediction and speculations. Remove?

Correct, although I think this will get lost in the noise given that it's 
sitting in the middle of crypto processing.  I'd remove it.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Wed, 2 Feb 2005, James Morris wrote:

> Correct, although I think this will get lost in the noise given that it's 
> sitting in the middle of crypto processing.  I'd remove it.

Dave just ok'd it, so take his advice over mine :-)


- james
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1833 bytes --]

On Wed, 2005-02-02 at 17:46 -0500, James Morris wrote:
> On Sun, 30 Jan 2005, Fruhwirth Clemens wrote:

> > +#define scatterwalk_needscratch(walk, nbytes) 						\
> > +	((nbytes) <= (walk)->len_this_page &&						\
> > +	    (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) + (nbytes) <=	\
> > +	    PAGE_CACHE_SIZE)								\
> 
> This should be a static inline.

First attempt:

static inline int scatterwalk_needscratch(struct scatter_walk *walk, int
nbytes) {
       return ((nbytes) <= (walk)->len_this_page &&
               (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) +
(nbytes) <= PAGE_CACHE_SIZE);
}

While trying to improve this unreadable monster I noticed, that 
(((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) is always equal
to walk->offset. walk->data and walk->offset always grows together (see
scatterwalk_copychunks), and when the bitwise AND-ing of walk->data with
PAGE_CACHE_SIZE-1 would result walk->offset to be zero, in just that
moment, walk->offset is set zero (see scatterwalk_pagedone). So, better:

static inline int scatterwalk_needscratch(struct scatter_walk *walk, int
nbytes) 
{
	return (nbytes <= walk->len_this_page &&
		(nbytes + walk->offset) <= PAGE_CACHE_SIZE);
}

Looks nicer, right? But in fact, it's redundant. walk->offset is never
intended to grow bigger than PAGE_CACHE_SIZE, and further it's illegal
to hand cryptoapi a scatterlist, where sg->offset is greater than
PAGE_CACHE_SIZE (I presume this from the calculations in
scatterwalk_start). Are these two conclusions correct, James? 

If so, I can drop the redundant expression, and probably drop the entire
function, as it becomes trivial then. Dropping the check shows no
regressions btw.
-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Thu, 3 Feb 2005, Fruhwirth Clemens wrote:

> First attempt:
> 
> static inline int scatterwalk_needscratch(struct scatter_walk *walk, int
> nbytes) {
>        return ((nbytes) <= (walk)->len_this_page &&
>                (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) +
> (nbytes) <= PAGE_CACHE_SIZE);
> }
> 
> While trying to improve this unreadable monster I noticed, that 
> (((unsigned long)(walk)->data) & (PAGE_CACHE_SIZE - 1)) is always equal
> to walk->offset. walk->data and walk->offset always grows together (see
> scatterwalk_copychunks), and when the bitwise AND-ing of walk->data with
> PAGE_CACHE_SIZE-1 would result walk->offset to be zero, in just that
> moment, walk->offset is set zero (see scatterwalk_pagedone). So, better:
> 
> static inline int scatterwalk_needscratch(struct scatter_walk *walk, int
> nbytes) 
> {
> 	return (nbytes <= walk->len_this_page &&
> 		(nbytes + walk->offset) <= PAGE_CACHE_SIZE);
> }
> 

This appears to be correct.  Adam (cc'd) did some work on this code, and
may have some further observations.

> Looks nicer, right? But in fact, it's redundant. walk->offset is never
> intended to grow bigger than PAGE_CACHE_SIZE, and further it's illegal
> to hand cryptoapi a scatterlist, where sg->offset is greater than
> PAGE_CACHE_SIZE (I presume this from the calculations in
> scatterwalk_start). Are these two conclusions correct, James? 

Yes, passing in an offset beyond the page size is wrong.

Also, I don't know why PAGE_CACHE_SIZE is being used here instead of
PAGE_SIZE.  Even though they're always the same now, I would suggest
changing all occurrences to PAGE_SIZE.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Wed, 2005-02-02 at 17:46 -0500, James Morris wrote:

> This code tests ok with IPSec, and delivers some good performance
> improvements.  e.g. FTP transfers over transport mode AES over GigE sped
> up with this patch applied on one side of the connection by 20% for send
> and 15% for receive.
>
> There are quite a few coding style and minor issues to be fixed (per
> below), and the code should probably then be tested in the -mm tree for a
> while (2.6.11 is too soon for mainline merge).

Fixed formating and white-spaces. The biggest change is, that I stripped
a redundant check from scatterwalk.c. This omission seems justified and
shows no regression on my system. ( http://lkml.org/lkml/2005/2/3/87 )
Can you give it a quick test with ipsec anyhow? Just to make sure.

http://clemens.endorphin.org/interdiff-sw.diff is an interdiff to last patch
posted, to ease the work of any reviewers. Mostly whitespace changes..

Outlook for the next patches: tweakable cipher modes interface, LRW
core, Michal's multiblock rewrite. Fortunately, none of them is as
intruding as the scatterwalk change.

Signed-off-by: Fruhwirth Clemens <clemens@endorphin.org>

--- 1/crypto/cipher.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/cipher.c	2005-02-05 09:52:30.000000000 +0100
@@ -22,7 +22,7 @@
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
-                        u8*, cryptfn_t, int enc, void *, int);
+			u8*, cryptfn_t, int enc, void *, int);
 
 static inline void xor_64(u8 *a, const u8 *b)
 {
@@ -38,177 +38,219 @@
 	((u32 *)a)[3] ^= ((u32 *)b)[3];
 }
 
+static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
+{
+	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
+	
+	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+		return -EINVAL;
+	} else
+		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
+				       &tfm->crt_flags);
+}
 
 /* 
- * Generic encrypt/decrypt wrapper for ciphers, handles operations across
- * multiple page boundaries by using temporary blocks.  In user context,
- * the kernel is given a chance to schedule us once per block.
+ * Electronic Code Book (ECB) mode implementation 
  */
-static int crypt(struct crypto_tfm *tfm,
-		 struct scatterlist *dst,
-		 struct scatterlist *src,
-                 unsigned int nbytes, cryptfn_t crfn,
-                 procfn_t prfn, int enc, void *info)
-{
-	struct scatter_walk walk_in, walk_out;
-	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
-	u8 tmp_src[bsize];
-	u8 tmp_dst[bsize];
+
+struct ecb_process_priv {
+	struct crypto_tfm	*tfm;
+	cryptfn_t		*crfn;
+};
+
+static int ecb_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct ecb_process_priv *ecb_priv = priv;
+	ecb_priv->crfn(crypto_tfm_ctx(ecb_priv->tfm), buf[0], buf[1]);
+	return 0;
+}
+
+static inline int ecb_template(struct crypto_tfm *tfm,
+			       struct scatterlist *dst,
+			       struct scatterlist *src, unsigned int nbytes, cryptfn_t crfn)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct ecb_process_priv priv = { 
+		.tfm = tfm,
+		.crfn = crfn,
+	};
+
+	struct walk_info ecb_info[3];
+
+	scatterwalk_info_init(ecb_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(ecb_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(ecb_info+2);
 
 	if (!nbytes)
 		return 0;
-
 	if (nbytes % bsize) {
 		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
 	}
 
-	scatterwalk_start(&walk_in, src);
-	scatterwalk_start(&walk_out, dst);
-
-	for(;;) {
-		u8 *src_p, *dst_p;
-		int in_place;
-
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
-		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
-		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
-		in_place = scatterwalk_samebuf(&walk_in, &walk_out,
-					       src_p, dst_p);
-
-		nbytes -= bsize;
-
-		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
-
-		prfn(tfm, dst_p, src_p, crfn, enc, info, in_place);
-
-		scatterwalk_done(&walk_in, 0, nbytes);
-
-		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
-		scatterwalk_done(&walk_out, 1, nbytes);
-
-		if (!nbytes)
-			return 0;
+	return scatterwalk_walk(ecb_process_gw, &priv, nbytes/bsize, ecb_info);
+}
 
-		crypto_yield(tfm);
-	}
+static int ecb_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);
 }
 
-static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
+static int ecb_decrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
 {
-	u8 *iv = info;
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_decrypt);
+}
+
+/* Cipher Block Chaining (CBC) mode implementation */
+
+struct cbc_process_priv {
+	struct crypto_tfm *tfm;
+	int enc;
+	cryptfn_t *crfn;
+	u8 *curr_iv;
+	u8 *next_iv;
+};
+
+static int cbc_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct cbc_process_priv *cbc_priv = priv;
+	u8 *iv = cbc_priv->curr_iv;
+	struct crypto_tfm *tfm = cbc_priv->tfm;
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	u8 *dst = buf[0];
+	u8 *src = buf[1];
 	
 	/* Null encryption */
 	if (!iv)
-		return;
-		
-	if (enc) {
+		return 0;
+
+	if (cbc_priv->enc == CRYPTO_DIR_ENCRYPT) {
+		/* Encryption can be done in place */
 		tfm->crt_u.cipher.cit_xor_block(iv, src);
-		fn(crypto_tfm_ctx(tfm), dst, iv);
-		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, iv);
+		memcpy(iv, dst, bsize);
 	} else {
-		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = in_place ? stack : dst;
-
-		fn(crypto_tfm_ctx(tfm), buf, src);
-		tfm->crt_u.cipher.cit_xor_block(buf, iv);
-		memcpy(iv, src, crypto_tfm_alg_blocksize(tfm));
-		if (buf != dst)
-			memcpy(dst, buf, crypto_tfm_alg_blocksize(tfm));
+		/* Current cipher text in "src" needs to be saved, as
+		 * it's going to be the next iv, exchange IV buffers
+		 * after processing
+		 */
+		memcpy(cbc_priv->next_iv,src,bsize);
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, src);
+		tfm->crt_u.cipher.cit_xor_block(dst, iv);
+		cbc_priv->curr_iv = cbc_priv->next_iv;
+		cbc_priv->next_iv = iv;
 	}
+	return 0;
 }
 
-static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
-{
-	fn(crypto_tfm_ctx(tfm), dst, src);
-}
 
-static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
-{
-	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
-	
-	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
-		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+static int cbc_encrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_ENCRYPT,
+		.curr_iv = iv,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_encrypt
+	};
+
+	struct walk_info cbc_info[3];
+
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
-	} else
-		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
-		                       &tfm->crt_flags);
-}
+	}
 
-static int ecb_encrypt(struct crypto_tfm *tfm,
-		       struct scatterlist *dst,
-                       struct scatterlist *src, unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             ecb_process, 1, NULL);
-}
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT); 
+	scatterwalk_info_endtag(cbc_info+2);
 
-static int ecb_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             ecb_process, 1, NULL);
+	return scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
 }
 
-static int cbc_encrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, tfm->crt_cipher.cit_iv);
-}
+static int cbc_decrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	int r = -EINVAL;
+
+	char scratch1[bsize]; 
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_DECRYPT,
+		.curr_iv = iv,
+		.next_iv = scratch1,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_decrypt,
+	};
+	struct walk_info cbc_info[3];
 
-static int cbc_encrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, iv);
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(cbc_info+2);
+
+	r = scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
+
+	if (priv.curr_iv != iv) 
+		memcpy(iv,priv.curr_iv,bsize);
+	return r;
 }
 
 static int cbc_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, tfm->crt_cipher.cit_iv);
+	return cbc_decrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
-static int cbc_decrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, iv);
+static int cbc_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return cbc_encrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
 static int nocrypt(struct crypto_tfm *tfm,
-                   struct scatterlist *dst,
-                   struct scatterlist *src,
+		   struct scatterlist *dst,
+		   struct scatterlist *src,
 		   unsigned int nbytes)
 {
 	return -ENOSYS;
 }
 
 static int nocrypt_iv(struct crypto_tfm *tfm,
-                      struct scatterlist *dst,
-                      struct scatterlist *src,
-                      unsigned int nbytes, u8 *iv)
+		      struct scatterlist *dst,
+		      struct scatterlist *src,
+		      unsigned int nbytes, u8 *iv)
 {
 	return -ENOSYS;
 }
@@ -263,26 +305,26 @@
 	}
 	
 	if (ops->cit_mode == CRYPTO_TFM_MODE_CBC) {
-	    	
-	    	switch (crypto_tfm_alg_blocksize(tfm)) {
-	    	case 8:
-	    		ops->cit_xor_block = xor_64;
-	    		break;
-	    		
-	    	case 16:
-	    		ops->cit_xor_block = xor_128;
-	    		break;
-	    		
-	    	default:
-	    		printk(KERN_WARNING "%s: block size %u not supported\n",
-	    		       crypto_tfm_alg_name(tfm),
-	    		       crypto_tfm_alg_blocksize(tfm));
-	    		ret = -EINVAL;
-	    		goto out;
-	    	}
-	    	
+		
+		switch (crypto_tfm_alg_blocksize(tfm)) {
+		case 8:
+			ops->cit_xor_block = xor_64;
+			break;
+			
+		case 16:
+			ops->cit_xor_block = xor_128;
+			break;
+			
+		default:
+			printk(KERN_WARNING "%s: block size %u not supported\n",
+			       crypto_tfm_alg_name(tfm),
+			       crypto_tfm_alg_blocksize(tfm));
+			ret = -EINVAL;
+			goto out;
+		}
+		
 		ops->cit_ivsize = crypto_tfm_alg_blocksize(tfm);
-	    	ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
+		ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
 		if (ops->cit_iv == NULL)
 			ret = -ENOMEM;
 	}
--- 1/crypto/scatterwalk.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.h	2005-02-03 10:07:57.000000000 +0100
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  * Copyright (c) 2002 Adam J. Richter <adam@yggdrasil.com>
  * Copyright (c) 2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ * Copyright (c) 2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -16,6 +17,7 @@
 #define _CRYPTO_SCATTERWALK_H
 #include <linux/mm.h>
 #include <asm/scatterlist.h>
+#include <linux/pagemap.h>
 
 struct scatter_walk {
 	struct scatterlist	*sg;
@@ -26,6 +28,16 @@
 	unsigned int		offset;
 };
 
+struct walk_info {
+	struct scatter_walk   sw;
+	int                   stepsize;
+	int                   ioflag;
+	char                  *buf;
+};
+
+#define SCATTERWALK_IO_OUTPUT  1
+#define SCATTERWALK_IO_INPUT   0
+
 /* Define sg_next is an inline routine now in case we want to change
    scatterlist to a linked list later. */
 static inline struct scatterlist *sg_next(struct scatterlist *sg)
@@ -33,19 +45,13 @@
 	return sg + 1;
 }
 
-static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
-				      struct scatter_walk *walk_out,
-				      void *src_p, void *dst_p)
-{
-	return walk_in->page == walk_out->page &&
-	       walk_in->offset == walk_out->offset &&
-	       walk_in->data == src_p && walk_out->data == dst_p;
-}
+typedef int (*sw_proc_func_t)(void *priv, int length, void **buflist);
+
+int scatterwalk_walk(sw_proc_func_t function, void *priv, int steps, struct walk_info *walk_info_l);
+
+#define scatterwalk_info_endtag(winfo) (winfo)->sw.sg = NULL;
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, int stepsize, void *buf, int io);
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
-void scatterwalk_map(struct scatter_walk *walk, int out);
-void scatterwalk_done(struct scatter_walk *walk, int out, int more);
 
 #endif  /* _CRYPTO_SCATTERWALK_H */
--- 1/crypto/scatterwalk.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.c	2005-02-05 00:14:28.000000000 +0100
@@ -6,6 +6,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  *               2002 Adam J. Richter <adam@yggdrasil.com>
  *               2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *               2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -28,17 +29,7 @@
 	KM_SOFTIRQ1,
 };
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
-{
-	if (nbytes <= walk->len_this_page &&
-	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
-	    PAGE_CACHE_SIZE)
-		return walk->data;
-	else
-		return scratch;
-}
-
-static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
+static inline void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
 {
 	if (out)
 		memcpy(sgdata, buf, nbytes);
@@ -46,7 +37,12 @@
 		memcpy(buf, sgdata, nbytes);
 }
 
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
+static inline int scatterwalk_needscratch(struct scatter_walk *walk, int nbytes) 
+{
+	return (nbytes <= walk->len_this_page);
+}
+
+static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
 {
 	unsigned int rest_of_page;
 
@@ -60,12 +56,19 @@
 	walk->offset = sg->offset;
 }
 
-void scatterwalk_map(struct scatter_walk *walk, int out)
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, 
+			   int stepsize, void *buf, int io)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	scatterwalk_start(&winfo->sw, sg);
+	winfo->stepsize = stepsize;
+	winfo->ioflag = io;
+	winfo->buf = buf;
 }
 
-static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
+#define scatterwalk_map(walk,out) \
+	(walk)->data = crypto_kmap((walk)->page, (out)) + (walk)->offset; 
+
+static inline void scatterwalk_pagedone(struct scatter_walk *walk, int out,
 				 unsigned int more)
 {
 	/* walk->data may be pointing the first byte of the next page;
@@ -89,36 +92,103 @@
 	}
 }
 
-void scatterwalk_done(struct scatter_walk *walk, int out, int more)
-{
-	crypto_kunmap(walk->data, out);
-	if (walk->len_this_page == 0 || !more)
-		scatterwalk_pagedone(walk, out, more);
-}
-
-/*
- * Do not call this unless the total length of all of the fragments
- * has been verified as multiple of the block size.
- */
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
-			   size_t nbytes, int out)
+static inline void scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
+			    size_t nbytes, int out)
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
-			memcpy_dir(buf, walk->data, walk->len_this_page, out);
-			buf += walk->len_this_page;
-			nbytes -= walk->len_this_page;
-
+			if (walk->len_this_page) {
+				memcpy_dir(buf, walk->data, walk->len_this_page, out);
+				buf += walk->len_this_page;
+				nbytes -= walk->len_this_page;
+			}
 			crypto_kunmap(walk->data, out);
-			scatterwalk_pagedone(walk, out, 1);
+			scatterwalk_pagedone(walk, 
+					     out, 
+					     1); /* more processing steps */
 			scatterwalk_map(walk, out);
 		}
-
 		memcpy_dir(buf, walk->data, nbytes, out);
 	}
-
+	walk->data += nbytes;
 	walk->offset += nbytes;
 	walk->len_this_page -= nbytes;
 	walk->len_this_segment -= nbytes;
-	return 0;
+}
+
+/*  
+ * The generic scatterwalker can manipulate data associated with one
+ * or more scatterlist with a processing function, pf. It's purpose is
+ * to hide the mapping, unalignment and page switching logic.
+ * 
+ * The generic scatterwalker applies a certain function, pf, utilising
+ * an arbitrary number of scatterlist data as it's arguments. These
+ * arguments are supplied as an array of pointers to buffers. These
+ * buffers are prepared and processed block-wise by the function
+ * (stepsize) and might be input or output buffers.
+ *
+ * All this informations and the underlaying scatterlist is handed to
+ * the generic walker as an array of descriptors of type
+ * walk_info. The sg, stepsize, ioflag and buf field of this struct
+ * must be initialised.
+ *
+ * The sg field points to the scatterlist the function should work on,
+ * the stepsize is the number of successive bytes that should be
+ * handed to the function, ioflag denotes input or output scatterlist
+ * and the buf field is either null, or points to a stepsize-width
+ * byte block, which can be used as copy buffer, when the stepsize
+ * does not align with page or scatterlist boundaries.
+ *
+ * A list of buffers are compiled and handed to the function, as char
+ * **buf, with buf[0] corresponds to the first walk_info descriptor,
+ * buf[1] to the second, and so on. The function is also handed a priv
+ * object, which does not change. Think of it as a "this" object, to
+ * collect/store processing information.
+ */
+
+int scatterwalk_walk(sw_proc_func_t pf, void *priv, int steps,
+		     struct walk_info *walk_infos) 
+{
+	int r = -EINVAL;
+	
+	int i;
+
+	struct walk_info *csg;
+	int nsl = 0;
+
+	void **cbuf;
+	void **dispatch_list;
+
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		scatterwalk_map(&csg->sw, csg->ioflag);
+		nsl++;
+	}
+
+	dispatch_list = (void *[nsl]){}; /* This alien thing is a C99 compound literal */
+
+	while (steps--) {
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; i--, csg++, cbuf++) {
+			*cbuf = scatterwalk_needscratch(&csg->sw,csg->stepsize)?csg->sw.data:csg->buf;
+
+			if (csg->ioflag == 0)
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize,0);
+		}
+
+		r = pf(priv, nsl, dispatch_list);
+		if (unlikely(r < 0))
+			goto out;
+
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
+			if (csg->ioflag == 1) 
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize,1);
+		}
+	}
+
+	r = 0;
+out:
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		crypto_kunmap(csg->sw.data, csg->ioflag);
+		scatterwalk_pagedone(&csg->sw, csg->ioflag, 0);
+	}
+	return r;
 }

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Sat, 5 Feb 2005, Fruhwirth Clemens wrote:

> Fixed formating and white-spaces. The biggest change is, that I stripped
> a redundant check from scatterwalk.c. This omission seems justified and
> shows no regression on my system. ( http://lkml.org/lkml/2005/2/3/87 )
> Can you give it a quick test with ipsec anyhow? Just to make sure.

Not tested yet, still reviewing the code.

> + * The generic scatterwalker applies a certain function, pf, utilising
> + * an arbitrary number of scatterlist data as it's arguments. These
> + * arguments are supplied as an array of pointers to buffers. These
> + * buffers are prepared and processed block-wise by the function
> + * (stepsize) and might be input or output buffers.

This is not going to work generically, as there number of atomic kmaps
available is limited.  You have four: one for input and one for output,
each in user in softirq context (hence the list in crypto_km_types).  A
thread of execution can only use two at once (input & output).  The crypto
code is written around this: processing a cleartext and ciphertext block
simultaneously.

> +
> +int scatterwalk_walk(sw_proc_func_t pf, void *priv, int steps,
> +		     struct walk_info *walk_infos) 
> +{
> +	int r = -EINVAL;
> +	
> +	int i;

Looks like this i is left over from something no longer use.

> +				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize,1);

There are several places such as this where you use literal 1 & 0 instead 
of the new macros, SCATTERWALK_IO_OUTPUT & INPUT.

> +static inline int scatterwalk_needscratch(struct scatter_walk *walk, int nbytes) 
> +{
> +       return (nbytes <= walk->len_this_page);
> +}

The logic of this is inverted given the function name.  While the calling 
code is using it correctly, it's going to cause confusion.

Also confusing is the remaining clamping of the page offset:

static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
{
	...

	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
        walk->len_this_page = min(sg->length, rest_of_page);
}

rest_of_page should be just PAGE_SIZE - sg->offset (sg->offset should
never extend beyond the page).
  
And then how would walk->len_this_page be greater than rest_of_page?


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Tue, 2005-02-08 at 09:48 -0500, James Morris wrote:
> On Sat, 5 Feb 2005, Fruhwirth Clemens wrote:
>
> > + * The generic scatterwalker applies a certain function, pf, utilising
> > + * an arbitrary number of scatterlist data as it's arguments. These
> > + * arguments are supplied as an array of pointers to buffers. These
> > + * buffers are prepared and processed block-wise by the function
> > + * (stepsize) and might be input or output buffers.
> 
> This is not going to work generically, as there number of atomic kmaps
> available is limited.  You have four: one for input and one for output,
> each in user in softirq context (hence the list in crypto_km_types).  A
> thread of execution can only use two at once (input & output).  The crypto
> code is written around this: processing a cleartext and ciphertext block
> simultaneously.

I added a usemap, keeping track of what slots are used, so we do have
the speed gain of kmap_atomic, if possible, and the option to fall-back
to kmap (regular) when the slots are exhausted.

> [cutted]

Unquoted stuff changed according to your suggestions.

> Also confusing is the remaining clamping of the page offset:
> 
> static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
> {
> 	...
> 
> 	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
>         walk->len_this_page = min(sg->length, rest_of_page);
> }
> 
> rest_of_page should be just PAGE_SIZE - sg->offset (sg->offset should
> never extend beyond the page).

Changed.
  
> And then how would walk->len_this_page be greater than rest_of_page?

Of course, it can't be greater than rest_of_page because of the min.

What about that? Search for kmap_usage || usemap, to get to the new code
quickly

--- 1/crypto/cipher.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/cipher.c	2005-02-05 09:52:30.000000000 +0100
@@ -22,7 +22,7 @@
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
-                        u8*, cryptfn_t, int enc, void *, int);
+			u8*, cryptfn_t, int enc, void *, int);
 
 static inline void xor_64(u8 *a, const u8 *b)
 {
@@ -38,177 +38,219 @@
 	((u32 *)a)[3] ^= ((u32 *)b)[3];
 }
 
+static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
+{
+	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
+	
+	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+		return -EINVAL;
+	} else
+		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
+				       &tfm->crt_flags);
+}
 
 /* 
- * Generic encrypt/decrypt wrapper for ciphers, handles operations across
- * multiple page boundaries by using temporary blocks.  In user context,
- * the kernel is given a chance to schedule us once per block.
+ * Electronic Code Book (ECB) mode implementation 
  */
-static int crypt(struct crypto_tfm *tfm,
-		 struct scatterlist *dst,
-		 struct scatterlist *src,
-                 unsigned int nbytes, cryptfn_t crfn,
-                 procfn_t prfn, int enc, void *info)
-{
-	struct scatter_walk walk_in, walk_out;
-	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
-	u8 tmp_src[bsize];
-	u8 tmp_dst[bsize];
+
+struct ecb_process_priv {
+	struct crypto_tfm	*tfm;
+	cryptfn_t		*crfn;
+};
+
+static int ecb_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct ecb_process_priv *ecb_priv = priv;
+	ecb_priv->crfn(crypto_tfm_ctx(ecb_priv->tfm), buf[0], buf[1]);
+	return 0;
+}
+
+static inline int ecb_template(struct crypto_tfm *tfm,
+			       struct scatterlist *dst,
+			       struct scatterlist *src, unsigned int nbytes, cryptfn_t crfn)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct ecb_process_priv priv = { 
+		.tfm = tfm,
+		.crfn = crfn,
+	};
+
+	struct walk_info ecb_info[3];
+
+	scatterwalk_info_init(ecb_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(ecb_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(ecb_info+2);
 
 	if (!nbytes)
 		return 0;
-
 	if (nbytes % bsize) {
 		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
 	}
 
-	scatterwalk_start(&walk_in, src);
-	scatterwalk_start(&walk_out, dst);
-
-	for(;;) {
-		u8 *src_p, *dst_p;
-		int in_place;
-
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
-		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
-		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
-		in_place = scatterwalk_samebuf(&walk_in, &walk_out,
-					       src_p, dst_p);
-
-		nbytes -= bsize;
-
-		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
-
-		prfn(tfm, dst_p, src_p, crfn, enc, info, in_place);
-
-		scatterwalk_done(&walk_in, 0, nbytes);
-
-		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
-		scatterwalk_done(&walk_out, 1, nbytes);
-
-		if (!nbytes)
-			return 0;
+	return scatterwalk_walk(ecb_process_gw, &priv, nbytes/bsize, ecb_info);
+}
 
-		crypto_yield(tfm);
-	}
+static int ecb_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);
 }
 
-static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
+static int ecb_decrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
 {
-	u8 *iv = info;
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_decrypt);
+}
+
+/* Cipher Block Chaining (CBC) mode implementation */
+
+struct cbc_process_priv {
+	struct crypto_tfm *tfm;
+	int enc;
+	cryptfn_t *crfn;
+	u8 *curr_iv;
+	u8 *next_iv;
+};
+
+static int cbc_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct cbc_process_priv *cbc_priv = priv;
+	u8 *iv = cbc_priv->curr_iv;
+	struct crypto_tfm *tfm = cbc_priv->tfm;
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	u8 *dst = buf[0];
+	u8 *src = buf[1];
 	
 	/* Null encryption */
 	if (!iv)
-		return;
-		
-	if (enc) {
+		return 0;
+
+	if (cbc_priv->enc == CRYPTO_DIR_ENCRYPT) {
+		/* Encryption can be done in place */
 		tfm->crt_u.cipher.cit_xor_block(iv, src);
-		fn(crypto_tfm_ctx(tfm), dst, iv);
-		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, iv);
+		memcpy(iv, dst, bsize);
 	} else {
-		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = in_place ? stack : dst;
-
-		fn(crypto_tfm_ctx(tfm), buf, src);
-		tfm->crt_u.cipher.cit_xor_block(buf, iv);
-		memcpy(iv, src, crypto_tfm_alg_blocksize(tfm));
-		if (buf != dst)
-			memcpy(dst, buf, crypto_tfm_alg_blocksize(tfm));
+		/* Current cipher text in "src" needs to be saved, as
+		 * it's going to be the next iv, exchange IV buffers
+		 * after processing
+		 */
+		memcpy(cbc_priv->next_iv,src,bsize);
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, src);
+		tfm->crt_u.cipher.cit_xor_block(dst, iv);
+		cbc_priv->curr_iv = cbc_priv->next_iv;
+		cbc_priv->next_iv = iv;
 	}
+	return 0;
 }
 
-static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
-{
-	fn(crypto_tfm_ctx(tfm), dst, src);
-}
 
-static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
-{
-	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
-	
-	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
-		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+static int cbc_encrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_ENCRYPT,
+		.curr_iv = iv,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_encrypt
+	};
+
+	struct walk_info cbc_info[3];
+
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
-	} else
-		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
-		                       &tfm->crt_flags);
-}
+	}
 
-static int ecb_encrypt(struct crypto_tfm *tfm,
-		       struct scatterlist *dst,
-                       struct scatterlist *src, unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             ecb_process, 1, NULL);
-}
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT); 
+	scatterwalk_info_endtag(cbc_info+2);
 
-static int ecb_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             ecb_process, 1, NULL);
+	return scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
 }
 
-static int cbc_encrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, tfm->crt_cipher.cit_iv);
-}
+static int cbc_decrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	int r = -EINVAL;
+
+	char scratch1[bsize]; 
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_DECRYPT,
+		.curr_iv = iv,
+		.next_iv = scratch1,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_decrypt,
+	};
+	struct walk_info cbc_info[3];
 
-static int cbc_encrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, iv);
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(cbc_info+2);
+
+	r = scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
+
+	if (priv.curr_iv != iv) 
+		memcpy(iv,priv.curr_iv,bsize);
+	return r;
 }
 
 static int cbc_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, tfm->crt_cipher.cit_iv);
+	return cbc_decrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
-static int cbc_decrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, iv);
+static int cbc_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return cbc_encrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
 static int nocrypt(struct crypto_tfm *tfm,
-                   struct scatterlist *dst,
-                   struct scatterlist *src,
+		   struct scatterlist *dst,
+		   struct scatterlist *src,
 		   unsigned int nbytes)
 {
 	return -ENOSYS;
 }
 
 static int nocrypt_iv(struct crypto_tfm *tfm,
-                      struct scatterlist *dst,
-                      struct scatterlist *src,
-                      unsigned int nbytes, u8 *iv)
+		      struct scatterlist *dst,
+		      struct scatterlist *src,
+		      unsigned int nbytes, u8 *iv)
 {
 	return -ENOSYS;
 }
@@ -263,26 +305,26 @@
 	}
 	
 	if (ops->cit_mode == CRYPTO_TFM_MODE_CBC) {
-	    	
-	    	switch (crypto_tfm_alg_blocksize(tfm)) {
-	    	case 8:
-	    		ops->cit_xor_block = xor_64;
-	    		break;
-	    		
-	    	case 16:
-	    		ops->cit_xor_block = xor_128;
-	    		break;
-	    		
-	    	default:
-	    		printk(KERN_WARNING "%s: block size %u not supported\n",
-	    		       crypto_tfm_alg_name(tfm),
-	    		       crypto_tfm_alg_blocksize(tfm));
-	    		ret = -EINVAL;
-	    		goto out;
-	    	}
-	    	
+		
+		switch (crypto_tfm_alg_blocksize(tfm)) {
+		case 8:
+			ops->cit_xor_block = xor_64;
+			break;
+			
+		case 16:
+			ops->cit_xor_block = xor_128;
+			break;
+			
+		default:
+			printk(KERN_WARNING "%s: block size %u not supported\n",
+			       crypto_tfm_alg_name(tfm),
+			       crypto_tfm_alg_blocksize(tfm));
+			ret = -EINVAL;
+			goto out;
+		}
+		
 		ops->cit_ivsize = crypto_tfm_alg_blocksize(tfm);
-	    	ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
+		ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
 		if (ops->cit_iv == NULL)
 			ret = -ENOMEM;
 	}
--- 1/crypto/scatterwalk.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.h	2005-02-07 22:13:02.000000000 +0100
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  * Copyright (c) 2002 Adam J. Richter <adam@yggdrasil.com>
  * Copyright (c) 2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ * Copyright (c) 2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -16,6 +17,7 @@
 #define _CRYPTO_SCATTERWALK_H
 #include <linux/mm.h>
 #include <asm/scatterlist.h>
+#include <linux/pagemap.h>
 
 struct scatter_walk {
 	struct scatterlist	*sg;
@@ -26,6 +28,16 @@
 	unsigned int		offset;
 };
 
+struct walk_info {
+	struct scatter_walk   sw;
+	int                   stepsize;
+	int                   ioflag;
+	char                  *buf;
+};
+
+#define SCATTERWALK_IO_OUTPUT  1
+#define SCATTERWALK_IO_INPUT   0
+
 /* Define sg_next is an inline routine now in case we want to change
    scatterlist to a linked list later. */
 static inline struct scatterlist *sg_next(struct scatterlist *sg)
@@ -33,19 +45,16 @@
 	return sg + 1;
 }
 
-static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
-				      struct scatter_walk *walk_out,
-				      void *src_p, void *dst_p)
-{
-	return walk_in->page == walk_out->page &&
-	       walk_in->offset == walk_out->offset &&
-	       walk_in->data == src_p && walk_out->data == dst_p;
-}
+typedef int (*sw_proc_func_t)(void *priv, int length, void **buflist);
+
+/* If the following functions are ever going to be exported symbols, I 
+ * request them to be GPL-only symbols. Thanks, -- clemens@endorphin.org */
+
+int scatterwalk_walk(sw_proc_func_t function, void *priv, int steps, struct walk_info *walk_info_l);
+
+void scatterwalk_info_endtag(struct walk_info *);
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, int stepsize, void *buf, int io);
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
-void scatterwalk_map(struct scatter_walk *walk, int out);
-void scatterwalk_done(struct scatter_walk *walk, int out, int more);
 
 #endif  /* _CRYPTO_SCATTERWALK_H */
--- 1/crypto/scatterwalk.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.c	2005-02-08 17:06:38.000000000 +0100
@@ -6,6 +6,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  *               2002 Adam J. Richter <adam@yggdrasil.com>
  *               2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *               2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -28,17 +29,7 @@
 	KM_SOFTIRQ1,
 };
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
-{
-	if (nbytes <= walk->len_this_page &&
-	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
-	    PAGE_CACHE_SIZE)
-		return walk->data;
-	else
-		return scratch;
-}
-
-static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
+static inline void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
 {
 	if (out)
 		memcpy(sgdata, buf, nbytes);
@@ -46,7 +37,12 @@
 		memcpy(buf, sgdata, nbytes);
 }
 
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
+static inline int scatterwalk_noscratch(struct scatter_walk *walk, int nbytes) 
+{
+	return (nbytes <= walk->len_this_page);
+}
+
+static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
 {
 	unsigned int rest_of_page;
 
@@ -55,17 +51,37 @@
 	walk->page = sg->page;
 	walk->len_this_segment = sg->length;
 
-	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
+	rest_of_page = PAGE_SIZE - sg->offset;
 	walk->len_this_page = min(sg->length, rest_of_page);
 	walk->offset = sg->offset;
 }
 
-void scatterwalk_map(struct scatter_walk *walk, int out)
+/*
+ * The scatterwalk_info_init function initialzes a walk_info struct 
+ * sg       .. pointer to the scatterlist to be processed 
+ * stepsize .. size of the data processed by one step of scatterwalk_walk
+ * buf      .. scratch buffer at least as stepsize-wide.
+ * io       .. set to SCATTERWALK_IO_INPUT or SCATTERWALK_IO_OUTPUT
+ */
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, 
+			   int stepsize, void *buf, int io)
+{
+	scatterwalk_start(&winfo->sw, sg);
+	winfo->stepsize = stepsize;
+	winfo->ioflag = io;
+	winfo->buf = buf;
+}
+
+void scatterwalk_info_endtag(struct walk_info *winfo)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	winfo->sw.sg = NULL;
 }
 
-static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
+#define scatterwalk_map(walk,out,usemap) \
+	(walk)->data = crypto_kmap((walk)->page, (out),(usemap)) + (walk)->offset; 
+
+static inline void scatterwalk_pagedone(struct scatter_walk *walk, int out,
 				 unsigned int more)
 {
 	/* walk->data may be pointing the first byte of the next page;
@@ -81,7 +97,7 @@
 		if (walk->len_this_segment) {
 			walk->page++;
 			walk->len_this_page = min(walk->len_this_segment,
-						  (unsigned)PAGE_CACHE_SIZE);
+						  (unsigned)PAGE_SIZE);
 			walk->offset = 0;
 		}
 		else
@@ -89,36 +105,109 @@
 	}
 }
 
-void scatterwalk_done(struct scatter_walk *walk, int out, int more)
-{
-	crypto_kunmap(walk->data, out);
-	if (walk->len_this_page == 0 || !more)
-		scatterwalk_pagedone(walk, out, more);
-}
-
-/*
- * Do not call this unless the total length of all of the fragments
- * has been verified as multiple of the block size.
- */
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
-			   size_t nbytes, int out)
+static inline void scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
+			    size_t nbytes, int out, void *usemap[])
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
-			memcpy_dir(buf, walk->data, walk->len_this_page, out);
-			buf += walk->len_this_page;
-			nbytes -= walk->len_this_page;
-
-			crypto_kunmap(walk->data, out);
-			scatterwalk_pagedone(walk, out, 1);
-			scatterwalk_map(walk, out);
+			if (walk->len_this_page) {
+				memcpy_dir(buf, walk->data, walk->len_this_page, out);
+				buf += walk->len_this_page;
+				nbytes -= walk->len_this_page;
+			}
+			crypto_kunmap(walk->data, walk->page, out, usemap);
+			scatterwalk_pagedone(walk, 
+					     out, 
+					     1); /* more processing steps */
+			scatterwalk_map(walk, out, usemap);
 		}
-
 		memcpy_dir(buf, walk->data, nbytes, out);
 	}
-
+	walk->data += nbytes;
 	walk->offset += nbytes;
 	walk->len_this_page -= nbytes;
 	walk->len_this_segment -= nbytes;
-	return 0;
+}
+
+/*  
+ * The generic scatterwalker can manipulate data associated with one
+ * or more scatterlist with a processing function, pf. It's purpose is
+ * to hide the mapping, unalignment and page switching logic.
+ * 
+ * The generic scatterwalker applies a certain function, pf, utilising
+ * an arbitrary number of scatterlist data as it's arguments. The scatterlist data 
+ * is handed to the pf function as an array of pointers, **buf. The pointers
+ * of buf point either directly into the kmapping of a scatterlist, or
+ * to a scratch buffer, if the scatterlist data is fragmented over a 
+ * more scatterlist vectors. All this logic is hidden in the scatterwalk_walk
+ * function, and the user of this function does not have to worry about
+ * unaligned scatterlists.
+ *
+ * Every scatterlist to be processed has to be supplied to scatterwalk_walk
+ * in a walk_info struct. There are also other information attached to
+ * this walk_info struct, such as step size or if the scatterlist is used as 
+ * input or output.
+ *
+ * The information about all scatterlists and their auxillary
+ * information is handed to scatterwalk_walk as a walk_info
+ * array. Every element of this array is initialized with
+ * scatterwalk_init_walk(..). The last element must be a terminator
+ * element and must be supplied to scatterwalk_info_endtag(..).
+ *
+ * See scatterwalk_info_init how the walk_info struct is initialized.
+ * scatterwalk_walk can be called multiple times after an initialization, 
+ * then the processing will pick up, where the previous one quitted.
+ *
+ * A list of buffers are compiled and handed to the function, as char
+ * **buf, with buf[0] corresponds to the first walk_info descriptor,
+ * buf[1] to the second, and so on. The function is also handed a priv
+ * object, which does not change. Think of it as a "this" object, to
+ * collect/store processing information.
+ */
+
+int scatterwalk_walk(sw_proc_func_t pf, void *priv, int steps,
+		     struct walk_info *walk_infos) 
+{
+	int r = -EINVAL;
+	
+	void *kmap_usage[4];
+
+	struct walk_info *csg;
+	int nsl = 0;
+
+	void **cbuf;
+	void **dispatch_list;
+
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		scatterwalk_map(&csg->sw, csg->ioflag, kmap_usage);
+		nsl++;
+	}
+
+	dispatch_list = (void *[nsl]){}; /* This alien thing is a C99 compound literal */
+
+	while (steps--) {
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {
+			*cbuf = scatterwalk_noscratch(&csg->sw,csg->stepsize)?csg->sw.data:csg->buf;
+
+			if (csg->ioflag == 0)
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize, SCATTERWALK_IO_INPUT, kmap_usage);
+		}
+
+		r = pf(priv, nsl, dispatch_list);
+		if (unlikely(r < 0))
+			goto out;
+
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
+			if (csg->ioflag == 1) 
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize, SCATTERWALK_IO_OUTPUT, kmap_usage);
+		}
+	}
+
+	r = 0;
+out:
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		crypto_kunmap(csg->sw.data, csg->sw.page, csg->ioflag, kmap_usage);
+		scatterwalk_pagedone(&csg->sw, csg->ioflag, 0);
+	}
+	return r;
 }
--- 1/crypto/internal.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/internal.h	2005-02-08 16:44:31.000000000 +0100
@@ -26,14 +26,26 @@
 	return crypto_km_types[(in_softirq() ? 2 : 0) + out];
 }
 
-static inline void *crypto_kmap(struct page *page, int out)
+static inline void *crypto_kmap(struct page *page, int out, void *usemap[])
 {
-	return kmap_atomic(page, crypto_kmap_type(out));
-}
-
-static inline void crypto_kunmap(void *vaddr, int out)
-{
-	kunmap_atomic(vaddr, crypto_kmap_type(out));
+	enum km_type type = crypto_kmap_type(out);
+	if(usemap[type] == NULL) {
+		void *mapping = kmap_atomic(page, type);
+		usemap[type] = mapping;
+		return mapping;
+	}
+	return kmap(page);
+}
+
+static inline void crypto_kunmap(void *vaddr, struct page *page, int out, void *usemap[])
+{
+	enum km_type type = crypto_kmap_type(out);
+	if(usemap[type] == vaddr) {
+		kunmap_atomic(vaddr, type);
+		usemap[type] = NULL;
+		return;
+	}
+	kunmap(page);
 }
 
 static inline void crypto_yield(struct crypto_tfm *tfm)
--- 1/crypto/digest.c	2005-02-08 17:04:33.000000000 +0100
+++ 2/crypto/digest.c	2005-02-08 17:04:50.000000000 +0100
@@ -27,6 +27,7 @@
                    struct scatterlist *sg, unsigned int nsg)
 {
 	unsigned int i;
+	void *kmap_usage[4];
 
 	for (i = 0; i < nsg; i++) {
 
@@ -38,12 +39,12 @@
 			unsigned int bytes_from_page = min(l, ((unsigned int)
 							   (PAGE_SIZE)) - 
 							   offset);
-			char *p = crypto_kmap(pg, 0) + offset;
+			char *p = crypto_kmap(pg, 0, kmap_usage) + offset;
 
 			tfm->__crt_alg->cra_digest.dia_update
 					(crypto_tfm_ctx(tfm), p,
 					 bytes_from_page);
-			crypto_kunmap(p, 0);
+			crypto_kunmap(p, pg, 0, kmap_usage);
 			crypto_yield(tfm);
 			offset = 0;
 			pg++;
@@ -69,15 +70,16 @@
 static void digest(struct crypto_tfm *tfm,
                    struct scatterlist *sg, unsigned int nsg, u8 *out)
 {
+	void *kmap_usage[4];
 	unsigned int i;
 
 	tfm->crt_digest.dit_init(tfm);
 		
 	for (i = 0; i < nsg; i++) {
-		char *p = crypto_kmap(sg[i].page, 0) + sg[i].offset;
+		char *p = crypto_kmap(sg[i].page, 0, kmap_usage) + sg[i].offset;
 		tfm->__crt_alg->cra_digest.dia_update(crypto_tfm_ctx(tfm),
 		                                      p, sg[i].length);
-		crypto_kunmap(p, 0);
+		crypto_kunmap(p, sg[i].page, 0, kmap_usage);
 		crypto_yield(tfm);
 	}
 	crypto_digest_final(tfm, out);

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Tue, 2005-02-08 at 17:08 +0100, Fruhwirth Clemens wrote:
> On Tue, 2005-02-08 at 09:48 -0500, James Morris wrote:
> > On Sat, 5 Feb 2005, Fruhwirth Clemens wrote:
> >
> > > + * The generic scatterwalker applies a certain function, pf, utilising
> > > + * an arbitrary number of scatterlist data as it's arguments. These
> > > + * arguments are supplied as an array of pointers to buffers. These
> > > + * buffers are prepared and processed block-wise by the function
> > > + * (stepsize) and might be input or output buffers.
> > 
> > This is not going to work generically, as there number of atomic kmaps
> > available is limited.  You have four: one for input and one for output,
> > each in user in softirq context (hence the list in crypto_km_types).  A
> > thread of execution can only use two at once (input & output).  The crypto
> > code is written around this: processing a cleartext and ciphertext block
> > simultaneously.
> 
> I added a usemap, keeping track of what slots are used, so we do have
> the speed gain of kmap_atomic, if possible, and the option to fall-back
> to kmap (regular) when the slots are exhausted.

I shot out the last patch too quickly. Having reviewed the mapping one
more time I noticed, that there as the possibility of "off-by-one"
unmapping, and instead of doing doubtful guesses, if that's the case, I
added a base pointer to scatter_walk, which is the pointer returned by
kmap. Exactly this pointer will be unmapped again, so the vaddr
comparison in crypto_kunmap doesn't have to do any masking.

--- 1/crypto/cipher.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/cipher.c	2005-02-05 09:52:30.000000000 +0100
@@ -22,7 +22,7 @@
 
 typedef void (cryptfn_t)(void *, u8 *, const u8 *);
 typedef void (procfn_t)(struct crypto_tfm *, u8 *,
-                        u8*, cryptfn_t, int enc, void *, int);
+			u8*, cryptfn_t, int enc, void *, int);
 
 static inline void xor_64(u8 *a, const u8 *b)
 {
@@ -38,177 +38,219 @@
 	((u32 *)a)[3] ^= ((u32 *)b)[3];
 }
 
+static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
+{
+	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
+	
+	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+		return -EINVAL;
+	} else
+		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
+				       &tfm->crt_flags);
+}
 
 /* 
- * Generic encrypt/decrypt wrapper for ciphers, handles operations across
- * multiple page boundaries by using temporary blocks.  In user context,
- * the kernel is given a chance to schedule us once per block.
+ * Electronic Code Book (ECB) mode implementation 
  */
-static int crypt(struct crypto_tfm *tfm,
-		 struct scatterlist *dst,
-		 struct scatterlist *src,
-                 unsigned int nbytes, cryptfn_t crfn,
-                 procfn_t prfn, int enc, void *info)
-{
-	struct scatter_walk walk_in, walk_out;
-	const unsigned int bsize = crypto_tfm_alg_blocksize(tfm);
-	u8 tmp_src[bsize];
-	u8 tmp_dst[bsize];
+
+struct ecb_process_priv {
+	struct crypto_tfm	*tfm;
+	cryptfn_t		*crfn;
+};
+
+static int ecb_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct ecb_process_priv *ecb_priv = priv;
+	ecb_priv->crfn(crypto_tfm_ctx(ecb_priv->tfm), buf[0], buf[1]);
+	return 0;
+}
+
+static inline int ecb_template(struct crypto_tfm *tfm,
+			       struct scatterlist *dst,
+			       struct scatterlist *src, unsigned int nbytes, cryptfn_t crfn)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct ecb_process_priv priv = { 
+		.tfm = tfm,
+		.crfn = crfn,
+	};
+
+	struct walk_info ecb_info[3];
+
+	scatterwalk_info_init(ecb_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(ecb_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(ecb_info+2);
 
 	if (!nbytes)
 		return 0;
-
 	if (nbytes % bsize) {
 		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
 	}
 
-	scatterwalk_start(&walk_in, src);
-	scatterwalk_start(&walk_out, dst);
-
-	for(;;) {
-		u8 *src_p, *dst_p;
-		int in_place;
-
-		scatterwalk_map(&walk_in, 0);
-		scatterwalk_map(&walk_out, 1);
-		src_p = scatterwalk_whichbuf(&walk_in, bsize, tmp_src);
-		dst_p = scatterwalk_whichbuf(&walk_out, bsize, tmp_dst);
-		in_place = scatterwalk_samebuf(&walk_in, &walk_out,
-					       src_p, dst_p);
-
-		nbytes -= bsize;
-
-		scatterwalk_copychunks(src_p, &walk_in, bsize, 0);
-
-		prfn(tfm, dst_p, src_p, crfn, enc, info, in_place);
-
-		scatterwalk_done(&walk_in, 0, nbytes);
-
-		scatterwalk_copychunks(dst_p, &walk_out, bsize, 1);
-		scatterwalk_done(&walk_out, 1, nbytes);
-
-		if (!nbytes)
-			return 0;
+	return scatterwalk_walk(ecb_process_gw, &priv, nbytes/bsize, ecb_info);
+}
 
-		crypto_yield(tfm);
-	}
+static int ecb_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);
 }
 
-static void cbc_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
+static int ecb_decrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
 {
-	u8 *iv = info;
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_decrypt);
+}
+
+/* Cipher Block Chaining (CBC) mode implementation */
+
+struct cbc_process_priv {
+	struct crypto_tfm *tfm;
+	int enc;
+	cryptfn_t *crfn;
+	u8 *curr_iv;
+	u8 *next_iv;
+};
+
+static int cbc_process_gw(void *priv, int nsg, void **buf) 
+{
+	struct cbc_process_priv *cbc_priv = priv;
+	u8 *iv = cbc_priv->curr_iv;
+	struct crypto_tfm *tfm = cbc_priv->tfm;
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	u8 *dst = buf[0];
+	u8 *src = buf[1];
 	
 	/* Null encryption */
 	if (!iv)
-		return;
-		
-	if (enc) {
+		return 0;
+
+	if (cbc_priv->enc == CRYPTO_DIR_ENCRYPT) {
+		/* Encryption can be done in place */
 		tfm->crt_u.cipher.cit_xor_block(iv, src);
-		fn(crypto_tfm_ctx(tfm), dst, iv);
-		memcpy(iv, dst, crypto_tfm_alg_blocksize(tfm));
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, iv);
+		memcpy(iv, dst, bsize);
 	} else {
-		u8 stack[in_place ? crypto_tfm_alg_blocksize(tfm) : 0];
-		u8 *buf = in_place ? stack : dst;
-
-		fn(crypto_tfm_ctx(tfm), buf, src);
-		tfm->crt_u.cipher.cit_xor_block(buf, iv);
-		memcpy(iv, src, crypto_tfm_alg_blocksize(tfm));
-		if (buf != dst)
-			memcpy(dst, buf, crypto_tfm_alg_blocksize(tfm));
+		/* Current cipher text in "src" needs to be saved, as
+		 * it's going to be the next iv, exchange IV buffers
+		 * after processing
+		 */
+		memcpy(cbc_priv->next_iv,src,bsize);
+		cbc_priv->crfn(crypto_tfm_ctx(tfm), dst, src);
+		tfm->crt_u.cipher.cit_xor_block(dst, iv);
+		cbc_priv->curr_iv = cbc_priv->next_iv;
+		cbc_priv->next_iv = iv;
 	}
+	return 0;
 }
 
-static void ecb_process(struct crypto_tfm *tfm, u8 *dst, u8 *src,
-			cryptfn_t fn, int enc, void *info, int in_place)
-{
-	fn(crypto_tfm_ctx(tfm), dst, src);
-}
 
-static int setkey(struct crypto_tfm *tfm, const u8 *key, unsigned int keylen)
-{
-	struct cipher_alg *cia = &tfm->__crt_alg->cra_cipher;
-	
-	if (keylen < cia->cia_min_keysize || keylen > cia->cia_max_keysize) {
-		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_KEY_LEN;
+static int cbc_encrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_ENCRYPT,
+		.curr_iv = iv,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_encrypt
+	};
+
+	struct walk_info cbc_info[3];
+
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
 		return -EINVAL;
-	} else
-		return cia->cia_setkey(crypto_tfm_ctx(tfm), key, keylen,
-		                       &tfm->crt_flags);
-}
+	}
 
-static int ecb_encrypt(struct crypto_tfm *tfm,
-		       struct scatterlist *dst,
-                       struct scatterlist *src, unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             ecb_process, 1, NULL);
-}
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, 
+			      SCATTERWALK_IO_INPUT); 
+	scatterwalk_info_endtag(cbc_info+2);
 
-static int ecb_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             ecb_process, 1, NULL);
+	return scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
 }
 
-static int cbc_encrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
-		       unsigned int nbytes)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, tfm->crt_cipher.cit_iv);
-}
+static int cbc_decrypt_iv(struct crypto_tfm *tfm,
+			  struct scatterlist *dst,
+			  struct scatterlist *src,
+			  unsigned int nbytes, u8 *iv)
+{
+	int bsize = crypto_tfm_alg_blocksize(tfm);
+	int r = -EINVAL;
+
+	char scratch1[bsize]; 
+
+	struct cbc_process_priv priv = {
+		.tfm = tfm,
+		.enc = CRYPTO_DIR_DECRYPT,
+		.curr_iv = iv,
+		.next_iv = scratch1,
+		.crfn = tfm->__crt_alg->cra_cipher.cia_decrypt,
+	};
+	struct walk_info cbc_info[3];
 
-static int cbc_encrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_encrypt,
-	             cbc_process, 1, iv);
+	if (!nbytes)
+		return 0;
+	if (nbytes % bsize) {
+		tfm->crt_flags |= CRYPTO_TFM_RES_BAD_BLOCK_LEN;
+		return -EINVAL;
+	}
+
+	scatterwalk_info_init(cbc_info+0, dst, bsize, (char[bsize]){}, SCATTERWALK_IO_OUTPUT);
+	scatterwalk_info_init(cbc_info+1, src, bsize, (char[bsize]){}, SCATTERWALK_IO_INPUT);
+	scatterwalk_info_endtag(cbc_info+2);
+
+	r = scatterwalk_walk(cbc_process_gw, &priv, nbytes/bsize, cbc_info);
+
+	if (priv.curr_iv != iv) 
+		memcpy(iv,priv.curr_iv,bsize);
+	return r;
 }
 
 static int cbc_decrypt(struct crypto_tfm *tfm,
-                       struct scatterlist *dst,
-                       struct scatterlist *src,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
 		       unsigned int nbytes)
 {
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, tfm->crt_cipher.cit_iv);
+	return cbc_decrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
-static int cbc_decrypt_iv(struct crypto_tfm *tfm,
-                          struct scatterlist *dst,
-                          struct scatterlist *src,
-                          unsigned int nbytes, u8 *iv)
-{
-	return crypt(tfm, dst, src, nbytes,
-	             tfm->__crt_alg->cra_cipher.cia_decrypt,
-	             cbc_process, 0, iv);
+static int cbc_encrypt(struct crypto_tfm *tfm,
+		       struct scatterlist *dst,
+		       struct scatterlist *src,
+		       unsigned int nbytes)
+{
+	return cbc_encrypt_iv(tfm, dst, src, nbytes, tfm->crt_cipher.cit_iv);
 }
 
 static int nocrypt(struct crypto_tfm *tfm,
-                   struct scatterlist *dst,
-                   struct scatterlist *src,
+		   struct scatterlist *dst,
+		   struct scatterlist *src,
 		   unsigned int nbytes)
 {
 	return -ENOSYS;
 }
 
 static int nocrypt_iv(struct crypto_tfm *tfm,
-                      struct scatterlist *dst,
-                      struct scatterlist *src,
-                      unsigned int nbytes, u8 *iv)
+		      struct scatterlist *dst,
+		      struct scatterlist *src,
+		      unsigned int nbytes, u8 *iv)
 {
 	return -ENOSYS;
 }
@@ -263,26 +305,26 @@
 	}
 	
 	if (ops->cit_mode == CRYPTO_TFM_MODE_CBC) {
-	    	
-	    	switch (crypto_tfm_alg_blocksize(tfm)) {
-	    	case 8:
-	    		ops->cit_xor_block = xor_64;
-	    		break;
-	    		
-	    	case 16:
-	    		ops->cit_xor_block = xor_128;
-	    		break;
-	    		
-	    	default:
-	    		printk(KERN_WARNING "%s: block size %u not supported\n",
-	    		       crypto_tfm_alg_name(tfm),
-	    		       crypto_tfm_alg_blocksize(tfm));
-	    		ret = -EINVAL;
-	    		goto out;
-	    	}
-	    	
+		
+		switch (crypto_tfm_alg_blocksize(tfm)) {
+		case 8:
+			ops->cit_xor_block = xor_64;
+			break;
+			
+		case 16:
+			ops->cit_xor_block = xor_128;
+			break;
+			
+		default:
+			printk(KERN_WARNING "%s: block size %u not supported\n",
+			       crypto_tfm_alg_name(tfm),
+			       crypto_tfm_alg_blocksize(tfm));
+			ret = -EINVAL;
+			goto out;
+		}
+		
 		ops->cit_ivsize = crypto_tfm_alg_blocksize(tfm);
-	    	ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
+		ops->cit_iv = kmalloc(ops->cit_ivsize, GFP_KERNEL);
 		if (ops->cit_iv == NULL)
 			ret = -ENOMEM;
 	}
--- 1/crypto/scatterwalk.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.h	2005-02-08 17:29:58.000000000 +0100
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  * Copyright (c) 2002 Adam J. Richter <adam@yggdrasil.com>
  * Copyright (c) 2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ * Copyright (c) 2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -16,16 +17,28 @@
 #define _CRYPTO_SCATTERWALK_H
 #include <linux/mm.h>
 #include <asm/scatterlist.h>
+#include <linux/pagemap.h>
 
 struct scatter_walk {
 	struct scatterlist	*sg;
 	struct page		*page;
 	void			*data;
+	void                    *base;
 	unsigned int		len_this_page;
 	unsigned int		len_this_segment;
 	unsigned int		offset;
 };
 
+struct walk_info {
+	struct scatter_walk   sw;
+	int                   stepsize;
+	int                   ioflag;
+	char                  *buf;
+};
+
+#define SCATTERWALK_IO_OUTPUT  1
+#define SCATTERWALK_IO_INPUT   0
+
 /* Define sg_next is an inline routine now in case we want to change
    scatterlist to a linked list later. */
 static inline struct scatterlist *sg_next(struct scatterlist *sg)
@@ -33,19 +46,16 @@
 	return sg + 1;
 }
 
-static inline int scatterwalk_samebuf(struct scatter_walk *walk_in,
-				      struct scatter_walk *walk_out,
-				      void *src_p, void *dst_p)
-{
-	return walk_in->page == walk_out->page &&
-	       walk_in->offset == walk_out->offset &&
-	       walk_in->data == src_p && walk_out->data == dst_p;
-}
+typedef int (*sw_proc_func_t)(void *priv, int length, void **buflist);
+
+/* If the following functions are ever going to be exported symbols, I 
+ * request them to be GPL-only symbols. Thanks, -- clemens@endorphin.org */
+
+int scatterwalk_walk(sw_proc_func_t function, void *priv, int steps, struct walk_info *walk_info_l);
+
+void scatterwalk_info_endtag(struct walk_info *);
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, int stepsize, void *buf, int io);
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch);
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg);
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk, size_t nbytes, int out);
-void scatterwalk_map(struct scatter_walk *walk, int out);
-void scatterwalk_done(struct scatter_walk *walk, int out, int more);
 
 #endif  /* _CRYPTO_SCATTERWALK_H */
--- 1/crypto/scatterwalk.c	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/scatterwalk.c	2005-02-08 17:35:00.000000000 +0100
@@ -6,6 +6,7 @@
  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
  *               2002 Adam J. Richter <adam@yggdrasil.com>
  *               2004 Jean-Luc Cooke <jlcooke@certainkey.com>
+ *               2005 Clemens Fruhwirth <clemens@endorphin.org>
  *
  * This program is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License as published by the Free
@@ -28,17 +29,7 @@
 	KM_SOFTIRQ1,
 };
 
-void *scatterwalk_whichbuf(struct scatter_walk *walk, unsigned int nbytes, void *scratch)
-{
-	if (nbytes <= walk->len_this_page &&
-	    (((unsigned long)walk->data) & (PAGE_CACHE_SIZE - 1)) + nbytes <=
-	    PAGE_CACHE_SIZE)
-		return walk->data;
-	else
-		return scratch;
-}
-
-static void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
+static inline void memcpy_dir(void *buf, void *sgdata, size_t nbytes, int out)
 {
 	if (out)
 		memcpy(sgdata, buf, nbytes);
@@ -46,7 +37,12 @@
 		memcpy(buf, sgdata, nbytes);
 }
 
-void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
+static inline int scatterwalk_noscratch(struct scatter_walk *walk, int nbytes) 
+{
+	return (nbytes <= walk->len_this_page);
+}
+
+static inline void scatterwalk_start(struct scatter_walk *walk, struct scatterlist *sg)
 {
 	unsigned int rest_of_page;
 
@@ -55,23 +51,43 @@
 	walk->page = sg->page;
 	walk->len_this_segment = sg->length;
 
-	rest_of_page = PAGE_CACHE_SIZE - (sg->offset & (PAGE_CACHE_SIZE - 1));
+	rest_of_page = PAGE_SIZE - sg->offset;
 	walk->len_this_page = min(sg->length, rest_of_page);
 	walk->offset = sg->offset;
 }
 
-void scatterwalk_map(struct scatter_walk *walk, int out)
+/*
+ * The scatterwalk_info_init function initialzes a walk_info struct 
+ * sg       .. pointer to the scatterlist to be processed 
+ * stepsize .. size of the data processed by one step of scatterwalk_walk
+ * buf      .. scratch buffer at least as stepsize-wide.
+ * io       .. set to SCATTERWALK_IO_INPUT or SCATTERWALK_IO_OUTPUT
+ */
+
+void scatterwalk_info_init(struct walk_info *winfo, struct scatterlist *sg, 
+			   int stepsize, void *buf, int io)
 {
-	walk->data = crypto_kmap(walk->page, out) + walk->offset;
+	scatterwalk_start(&winfo->sw, sg);
+	winfo->stepsize = stepsize;
+	winfo->ioflag = io;
+	winfo->buf = buf;
 }
 
-static void scatterwalk_pagedone(struct scatter_walk *walk, int out,
-				 unsigned int more)
+void scatterwalk_info_endtag(struct walk_info *winfo)
 {
-	/* walk->data may be pointing the first byte of the next page;
-	   however, we know we transfered at least one byte.  So,
-	   walk->data - 1 will be a virtual address in the mapped page. */
+	winfo->sw.sg = NULL;
+}
+
+
+static void scatterwalk_map(struct scatter_walk *walk, int out, void *usemap[]) 
+{
+	walk->base = crypto_kmap(walk->page, out, usemap);
+	walk->data = walk->base + walk->offset; 
+}
 
+static inline void scatterwalk_pagedone(struct scatter_walk *walk, int out,
+				 unsigned int more)
+{
 	if (out)
 		flush_dcache_page(walk->page);
 
@@ -81,7 +97,7 @@
 		if (walk->len_this_segment) {
 			walk->page++;
 			walk->len_this_page = min(walk->len_this_segment,
-						  (unsigned)PAGE_CACHE_SIZE);
+						  (unsigned)PAGE_SIZE);
 			walk->offset = 0;
 		}
 		else
@@ -89,36 +105,109 @@
 	}
 }
 
-void scatterwalk_done(struct scatter_walk *walk, int out, int more)
-{
-	crypto_kunmap(walk->data, out);
-	if (walk->len_this_page == 0 || !more)
-		scatterwalk_pagedone(walk, out, more);
-}
-
-/*
- * Do not call this unless the total length of all of the fragments
- * has been verified as multiple of the block size.
- */
-int scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
-			   size_t nbytes, int out)
+static inline void scatterwalk_copychunks(void *buf, struct scatter_walk *walk,
+			    size_t nbytes, int out, void *usemap[])
 {
 	if (buf != walk->data) {
 		while (nbytes > walk->len_this_page) {
-			memcpy_dir(buf, walk->data, walk->len_this_page, out);
-			buf += walk->len_this_page;
-			nbytes -= walk->len_this_page;
-
-			crypto_kunmap(walk->data, out);
-			scatterwalk_pagedone(walk, out, 1);
-			scatterwalk_map(walk, out);
+			if (walk->len_this_page) {
+				memcpy_dir(buf, walk->data, walk->len_this_page, out);
+				buf += walk->len_this_page;
+				nbytes -= walk->len_this_page;
+			}
+			crypto_kunmap(walk->base, walk->page, out, usemap);
+			scatterwalk_pagedone(walk, 
+					     out, 
+					     1); /* more processing steps */
+			scatterwalk_map(walk, out, usemap);
 		}
-
 		memcpy_dir(buf, walk->data, nbytes, out);
 	}
-
+	walk->data += nbytes;
 	walk->offset += nbytes;
 	walk->len_this_page -= nbytes;
 	walk->len_this_segment -= nbytes;
-	return 0;
+}
+
+/*  
+ * The generic scatterwalker can manipulate data associated with one
+ * or more scatterlist with a processing function, pf. It's purpose is
+ * to hide the mapping, unalignment and page switching logic.
+ * 
+ * The generic scatterwalker applies a certain function, pf, utilising
+ * an arbitrary number of scatterlist data as it's arguments. The scatterlist data 
+ * is handed to the pf function as an array of pointers, **buf. The pointers
+ * of buf point either directly into the kmapping of a scatterlist, or
+ * to a scratch buffer, if the scatterlist data is fragmented over a 
+ * more scatterlist vectors. All this logic is hidden in the scatterwalk_walk
+ * function, and the user of this function does not have to worry about
+ * unaligned scatterlists.
+ *
+ * Every scatterlist to be processed has to be supplied to scatterwalk_walk
+ * in a walk_info struct. There are also other information attached to
+ * this walk_info struct, such as step size or if the scatterlist is used as 
+ * input or output.
+ *
+ * The information about all scatterlists and their auxillary
+ * information is handed to scatterwalk_walk as a walk_info
+ * array. Every element of this array is initialized with
+ * scatterwalk_init_walk(..). The last element must be a terminator
+ * element and must be supplied to scatterwalk_info_endtag(..).
+ *
+ * See scatterwalk_info_init how the walk_info struct is initialized.
+ * scatterwalk_walk can be called multiple times after an initialization, 
+ * then the processing will pick up, where the previous one quitted.
+ *
+ * A list of buffers are compiled and handed to the function, as char
+ * **buf, with buf[0] corresponds to the first walk_info descriptor,
+ * buf[1] to the second, and so on. The function is also handed a priv
+ * object, which does not change. Think of it as a "this" object, to
+ * collect/store processing information.
+ */
+
+int scatterwalk_walk(sw_proc_func_t pf, void *priv, int steps,
+		     struct walk_info *walk_infos) 
+{
+	int r = -EINVAL;
+	
+	void *kmap_usage[4];
+
+	struct walk_info *csg;
+	int nsl = 0;
+
+	void **cbuf;
+	void **dispatch_list;
+
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		scatterwalk_map(&csg->sw, csg->ioflag, kmap_usage);
+		nsl++;
+	}
+
+	dispatch_list = (void *[nsl]){}; /* This alien thing is a C99 compound literal */
+
+	while (steps--) {
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {
+			*cbuf = scatterwalk_noscratch(&csg->sw,csg->stepsize)?csg->sw.data:csg->buf;
+
+			if (csg->ioflag == 0)
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize, SCATTERWALK_IO_INPUT, kmap_usage);
+		}
+
+		r = pf(priv, nsl, dispatch_list);
+		if (unlikely(r < 0))
+			goto out;
+
+		for (csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
+			if (csg->ioflag == 1) 
+				scatterwalk_copychunks(*cbuf,&csg->sw,csg->stepsize, SCATTERWALK_IO_OUTPUT, kmap_usage);
+		}
+	}
+
+	r = 0;
+out:
+	for (csg = walk_infos; csg->sw.sg; csg++) {
+		crypto_kunmap(csg->sw.base, csg->sw.page, csg->ioflag, kmap_usage);
+		scatterwalk_pagedone(&csg->sw, csg->ioflag, 0);
+	}
+	return r;
 }
--- 1/crypto/internal.h	2005-01-20 10:15:40.000000000 +0100
+++ 2/crypto/internal.h	2005-02-08 17:32:09.000000000 +0100
@@ -26,14 +26,26 @@
 	return crypto_km_types[(in_softirq() ? 2 : 0) + out];
 }
 
-static inline void *crypto_kmap(struct page *page, int out)
+static inline void *crypto_kmap(struct page *page, int out, void *usemap[])
 {
-	return kmap_atomic(page, crypto_kmap_type(out));
-}
-
-static inline void crypto_kunmap(void *vaddr, int out)
-{
-	kunmap_atomic(vaddr, crypto_kmap_type(out));
+	enum km_type type = crypto_kmap_type(out);
+	if(usemap[type] == NULL) {
+		void *mapping = kmap_atomic(page, type);
+		usemap[type] = mapping;
+		return mapping;
+	}
+	return kmap(page);
+}
+
+static inline void crypto_kunmap(void *vaddr, struct page *page, int out, void *usemap[])
+{
+	enum km_type type = crypto_kmap_type(out);
+	if(usemap[type] == vaddr) {
+		kunmap_atomic(vaddr, type);
+		usemap[type] = NULL;
+		return;
+	}
+	kunmap(page);
 }
 
 static inline void crypto_yield(struct crypto_tfm *tfm)
--- 1/crypto/digest.c	2005-02-08 17:04:33.000000000 +0100
+++ 2/crypto/digest.c	2005-02-08 17:04:50.000000000 +0100
@@ -27,6 +27,7 @@
                    struct scatterlist *sg, unsigned int nsg)
 {
 	unsigned int i;
+	void *kmap_usage[4];
 
 	for (i = 0; i < nsg; i++) {
 
@@ -38,12 +39,12 @@
 			unsigned int bytes_from_page = min(l, ((unsigned int)
 							   (PAGE_SIZE)) - 
 							   offset);
-			char *p = crypto_kmap(pg, 0) + offset;
+			char *p = crypto_kmap(pg, 0, kmap_usage) + offset;
 
 			tfm->__crt_alg->cra_digest.dia_update
 					(crypto_tfm_ctx(tfm), p,
 					 bytes_from_page);
-			crypto_kunmap(p, 0);
+			crypto_kunmap(p, pg, 0, kmap_usage);
 			crypto_yield(tfm);
 			offset = 0;
 			pg++;
@@ -69,15 +70,16 @@
 static void digest(struct crypto_tfm *tfm,
                    struct scatterlist *sg, unsigned int nsg, u8 *out)
 {
+	void *kmap_usage[4];
 	unsigned int i;
 
 	tfm->crt_digest.dit_init(tfm);
 		
 	for (i = 0; i < nsg; i++) {
-		char *p = crypto_kmap(sg[i].page, 0) + sg[i].offset;
+		char *p = crypto_kmap(sg[i].page, 0, kmap_usage) + sg[i].offset;
 		tfm->__crt_alg->cra_digest.dia_update(crypto_tfm_ctx(tfm),
 		                                      p, sg[i].length);
-		crypto_kunmap(p, 0);
+		crypto_kunmap(p, sg[i].page, 0, kmap_usage);
 		crypto_yield(tfm);
 	}
 	crypto_digest_final(tfm, out);

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Tue, 8 Feb 2005, Fruhwirth Clemens wrote:

> I shot out the last patch too quickly. Having reviewed the mapping one
> more time I noticed, that there as the possibility of "off-by-one"
> unmapping, and instead of doing doubtful guesses, if that's the case, I
> added a base pointer to scatter_walk, which is the pointer returned by
> kmap. Exactly this pointer will be unmapped again, so the vaddr
> comparison in crypto_kunmap doesn't have to do any masking.

You can't call kmap() in softirq context (why was it even trying?):

Debug: sleeping function called from invalid context at arch/i386/mm/highmem.c:5
in_atomic():1, irqs_disabled():0
 [<c0103385>] dump_stack+0x17/0x19
 [<c01165b5>] __might_sleep+0xc4/0xd7
 [<c0112665>] kmap+0x15/0x2e
 [<c0223027>] scatterwalk_map+0x5a/0x68
 [<c0223063>] scatterwalk_walk+0x2e/0x45b
 [<c02239ba>] cbc_decrypt_iv+0x11a/0x15f
 [<c0223a18>] cbc_decrypt+0x19/0x1f
 [<f88ad587>] esp_input+0x17d/0x409 [esp4]
 [<c031b7c4>] xfrm4_rcv_encap+0x102/0x512
 [<c02e5b6f>] ip_local_deliver+0x9d/0x28c
 [<c02e61bf>] ip_rcv+0x251/0x508
 [<c02d177b>] netif_receive_skb+0x1f6/0x223
 [<c02d1824>] process_backlog+0x7c/0x10f
 [<c02d1930>] net_rx_action+0x79/0xfb
 [<c011dfc2>] __do_softirq+0x62/0xcc
 [<c01047b6>] do_softirq+0x57/0x5b



- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Tue, 2005-02-08 at 18:30 -0500, James Morris wrote:
> On Tue, 8 Feb 2005, Fruhwirth Clemens wrote:
> 
> > I shot out the last patch too quickly. Having reviewed the mapping one
> > more time I noticed, that there as the possibility of "off-by-one"
> > unmapping, and instead of doing doubtful guesses, if that's the case, I
> > added a base pointer to scatter_walk, which is the pointer returned by
> > kmap. Exactly this pointer will be unmapped again, so the vaddr
> > comparison in crypto_kunmap doesn't have to do any masking.
> 
> You can't call kmap() in softirq context (why was it even trying?):

Why not? What's the alternative, then?

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Wed, 9 Feb 2005, Fruhwirth Clemens wrote:

> > You can't call kmap() in softirq context (why was it even trying?):
> 
> Why not? What's the alternative, then?

It can sleep in map_new_virtual().

The alternative is to use atomic kmaps.  For this code, unless you can 
point to something concrete in the existing kernel which would benefit 
from passing an arbitrary number of scatterlists in, just code for the 
case of processing two at once (input & output).


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

On Tue, 2005-02-08 at 19:09 -0500, James Morris wrote:
> On Wed, 9 Feb 2005, Fruhwirth Clemens wrote:
> 
> > > You can't call kmap() in softirq context (why was it even trying?):
> > 
> > Why not? What's the alternative, then?
> 
> It can sleep in map_new_virtual().
> 
> The alternative is to use atomic kmaps.  For this code, unless you can 
> point to something concrete in the existing kernel which would benefit 
> from passing an arbitrary number of scatterlists in, just code for the 
> case of processing two at once (input & output).

kmap_atomic doesn't qualify as alternative. It's limited to two free
mappings. There must be something else to kmap in softirq. I really
can't imagine such a limitation.

Where is the documentation for the highmem stuff anyway? It's stunning
that there is not a single useful hit in ./Documentation for kmap_atomic
or kmap. The web is also close-lipped about that issue.

I can't code for the case of two. Because, first, that's the idea of
generic in the name "generic scatterwalk", second, I need at least 3
scatterlists in parallel for LRW.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Wed, 9 Feb 2005, Fruhwirth Clemens wrote:

> I can't code for the case of two. Because, first, that's the idea of
> generic in the name "generic scatterwalk", second, I need at least 3
> scatterlists in parallel for LRW.

Can you explain why you need a third scatterlist for the LRW tweak?

My understanding is that the tweak value is calculated from the disk
position of the plaintext block and and the secondary key.

It would be useful to see the original patch (which seems to be
unavailable now), with dm-crypt integration, to see how the entire
mechanism works beyond the test vectors.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1997 bytes --]

On Wed, 2005-02-09 at 19:30 -0500, James Morris wrote:
> On Wed, 9 Feb 2005, Fruhwirth Clemens wrote:
> 
> > I can't code for the case of two. Because, first, that's the idea of
> > generic in the name "generic scatterwalk", second, I need at least 3
> > scatterlists in parallel for LRW.
> 
> Can you explain why you need a third scatterlist for the LRW tweak?

Because a tweak is different from an IV. There can be an arbitrary
number of tweaks. For instance, EME takes 1 tweak per 512 bytes. If you
have a 4k page to encrypt, you have to process 8 tweaks of whatever
size. 
 Therefore, you need 3 scatterlists: src, dst and the running along
tweak.

However, I don't want to limit the discussion to the specific needs of
LRW or EME. I wanted to write something nice and generic for other
people to use, thus scatterwalk_walk. 

There must be a solution to get an arbitrary number of kmappings in
softirq problem. If it's possible for 2 pages, I can't see a reason why
this ain't possible for more. The use of scratch buffers and constant
switching of kmap_atomic mapping is just ridiculously stupid.

> My understanding is that the tweak value is calculated from the disk
> position of the plaintext block and and the secondary key.

That's only partially correct. The tweak value _is_ the location on
disk. The value which is XORed twice is computed from the tweak and the
secondary key. In LRW, you need a tweak value per block. So, if you
encode 256 blocks, you need 256 tweaks. That's what the additional
scatterlist is for.

> It would be useful to see the original patch (which seems to be
> unavailable now), with dm-crypt integration, to see how the entire
> mechanism works beyond the test vectors.

Frankly, I don't see a point escalating this discussion. It must be
possible to process more than 2 mappings in softirq context. If not, I
feel emotionally offended.
-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Andrew Morton]

Fruhwirth Clemens <clemens@endorphin.org> wrote:
>
> It must be
>  possible to process more than 2 mappings in softirq context.

Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
arbitrarily large number of them then no, we cannot do that.

Taking more than one sleeping kmap at a time within the same process is
deadlocky, btw.  You can end up with N such tasks all holding one kmap and
waiting for someone else to release one.

Possibly one could arrange for the pages to not be in highmem at all.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Christophe Saout]

[-- Attachment #1: Type: text/plain, Size: 752 bytes --]

Am Mittwoch, den 09.02.2005, 17:19 -0800 schrieb Andrew Morton:

> > It must be
> >  possible to process more than 2 mappings in softirq context.
> 
> Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
> arbitrarily large number of them then no, we cannot do that.
> 
> Possibly one could arrange for the pages to not be in highmem at all.

In the case of the LRW use in dm-crypt only plain- and ciphertext need
to be accessible through struct page (both are addressed through BIO
vectors). The LRW tweaks could simply be kmalloced. So instead of
passing "struct scatterlist *tweaksg" we could just pass a "void
*tweaksg".

Some of the hard work on the generic scatterlist walker would be for
nothing then. :(


[-- Attachment #2: Dies ist ein digital signierter Nachrichtenteil --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1590 bytes --]

On Wed, 2005-02-09 at 17:19 -0800, Andrew Morton wrote:
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> >
> > It must be
> >  possible to process more than 2 mappings in softirq context.
> 
> Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
> arbitrarily large number of them then no, we cannot do that.

What magnitude is "few more"? 2, 10, 100?

> Taking more than one sleeping kmap at a time within the same process is
> deadlocky, btw.  You can end up with N such tasks all holding one kmap and
> waiting for someone else to release one.
> 
> Possibly one could arrange for the pages to not be in highmem at all.

Is there an easy way to bring pages to lowmem? The cryptoapi is called
from the backlog of the networking stack, which is assigned in irq
context first and processed softirq context. There is little opportunity
to bringt stuff to low mem. And we can't bringt stuff to lowmem on our
own as well, because (as I guess) this involves a page allocation, which
would have to be GFP_ATOMIC, which can fail. So we would need fallback
for the fallback mechanism, and that's still the tiny set of scratch
buffers.. hairy business..

Ok, what about the following plan:

If context == softirq, use kmap_atomic until they all used, fall-back to
scratch buffers, and printk in some DEBUG mode:"Warning slow, redesign
your client or raise the number of fixmaps".

If context == user, use kmap_atomic until they all used, and fall-back
to kmap.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Andrew Morton]

Fruhwirth Clemens <clemens@endorphin.org> wrote:
>
> On Wed, 2005-02-09 at 17:19 -0800, Andrew Morton wrote:
> > Fruhwirth Clemens <clemens@endorphin.org> wrote:
> > >
> > > It must be
> > >  possible to process more than 2 mappings in softirq context.
> > 
> > Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
> > arbitrarily large number of them then no, we cannot do that.
> 
> What magnitude is "few more"? 2, 10, 100?

Not 100.  10 would seem excessive.

> > Taking more than one sleeping kmap at a time within the same process is
> > deadlocky, btw.  You can end up with N such tasks all holding one kmap and
> > waiting for someone else to release one.
> > 
> > Possibly one could arrange for the pages to not be in highmem at all.
> 
> Is there an easy way to bring pages to lowmem? The cryptoapi is called
> from the backlog of the networking stack, which is assigned in irq
> context first and processed softirq context.

Are networking frames ever allocated from highmem?  Don't think so.

> There is little opportunity
> to bringt stuff to low mem. And we can't bringt stuff to lowmem on our
> own as well, because (as I guess) this involves a page allocation, which
> would have to be GFP_ATOMIC, which can fail. So we would need fallback
> for the fallback mechanism, and that's still the tiny set of scratch
> buffers.. hairy business..

yup.

> Ok, what about the following plan:
> 
> If context == softirq, use kmap_atomic until they all used, fall-back to
> scratch buffers, and printk in some DEBUG mode:"Warning slow, redesign
> your client or raise the number of fixmaps".

Sounds painful.

> If context == user, use kmap_atomic until they all used, and fall-back
> to kmap.

Taking multiple kmaps can deadlock due to kmap exhaustion though.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1642 bytes --]

On Thu, 2005-02-10 at 02:33 -0800, Andrew Morton wrote:
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> >
> > On Wed, 2005-02-09 at 17:19 -0800, Andrew Morton wrote:
> > > Fruhwirth Clemens <clemens@endorphin.org> wrote:
> > > Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
> > > arbitrarily large number of them then no, we cannot do that.
> > 
> > What magnitude is "few more"? 2, 10, 100?
> 
> Not 100.  10 would seem excessive.

Out of curiosity: Where does this limitation even come from? What
prevents kmap_atomic from adding slots dynamically?

> > Is there an easy way to bring pages to lowmem? The cryptoapi is called
> > from the backlog of the networking stack, which is assigned in irq
> > context first and processed softirq context.
> 
> Are networking frames ever allocated from highmem?  Don't think so.

Hm, alright. So I'm going take the internal of kmap_atomic into
scatterwalk.c. to test if the page is in highmem, with PageHighMem. If
it is, I'm going to kmap_atomic and mark the fixmap as used. If it's
not, I do the "mapping" on my own with page_address.

Btw folks: why are there UpperCamelCase functions in linux/page-flags.h
and you're whining about my camelcase style in gfmulseq.c? My file isn't
even intended to be included by other files, unlike this include file.

> > If context == user, use kmap_atomic until they all used, and fall-back
> > to kmap.
> 
> Taking multiple kmaps can deadlock due to kmap exhaustion though.

Ok, then relay on kmap_atomic, solely.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Thu, 10 Feb 2005, Fruhwirth Clemens wrote:

> Hm, alright. So I'm going take the internal of kmap_atomic into
> scatterwalk.c. to test if the page is in highmem, with PageHighMem. If
> it is, I'm going to kmap_atomic and mark the fixmap as used. If it's
> not, I do the "mapping" on my own with page_address.

No, you do not need to do any of this.

Per previous email, all you need is the existing two kmaps, pass the tweak 
in as a linear buffer.

> Btw folks: why are there UpperCamelCase functions in linux/page-flags.h
> and you're whining about my camelcase style in gfmulseq.c? My file isn't
> even intended to be included by other files, unlike this include file.

I don't know why the code is like that, but it is not an excuse to put 
more like it into the kernel.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1270 bytes --]

On Thu, 2005-02-10 at 12:02 -0500, James Morris wrote:
> On Thu, 10 Feb 2005, Fruhwirth Clemens wrote:
> 
> > Hm, alright. So I'm going take the internal of kmap_atomic into
> > scatterwalk.c. to test if the page is in highmem, with PageHighMem. If
> > it is, I'm going to kmap_atomic and mark the fixmap as used. If it's
> > not, I do the "mapping" on my own with page_address.
> 
> No, you do not need to do any of this.
> 
> Per previous email, all you need is the existing two kmaps, pass the tweak 
> in as a linear buffer.

Why should I pass the first thing of size X as scatterlist, and the
second thing of size X as linear buffer? 

I could do that. It would be reasonable, because tweaks are more likely
to be generated than transmitted, read or whatever. But what for shall I
narrow the interface? I could also pass a linear mapped buffer as
scatterlist. This doesn't cause any overhead.

And switching to a more specific interface would just delay a solution
of the inherent limitations of kmap's. I guess it will take another half
year until the next guy stumbles across this (totally undocumented!)
problem. Why are you pushing to ignore this problem?

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Thu, 10 Feb 2005, Fruhwirth Clemens wrote:

> Why should I pass the first thing of size X as scatterlist, and the
> second thing of size X as linear buffer? 
> 
> I could do that. It would be reasonable, because tweaks are more likely
> to be generated than transmitted, read or whatever. But what for shall I
> narrow the interface? I could also pass a linear mapped buffer as
> scatterlist. This doesn't cause any overhead.
> 
> And switching to a more specific interface would just delay a solution
> of the inherent limitations of kmap's. I guess it will take another half
> year until the next guy stumbles across this (totally undocumented!)
> problem. Why are you pushing to ignore this problem?

What problem?

All you need is the two existing kmaps, for simultaneous processing of 
input & output data at the page level.

The tweak is linearly generated data fed into this process.  It does not 
need to be kmapped.  It is not discontiguous.  There is no need for a 
third or Nth scatterlist.

Making a generic N-way scatterlist processor is pointless overengineering,
causing new problems with non-trivial solutions, for no benefit
whatsoever.


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1822 bytes --]

On Thu, 2005-02-10 at 12:54 -0500, James Morris wrote:

> Making a generic N-way scatterlist processor is pointless
> overengineering, causing new problems with non-trivial solutions, for
> no benefit whatsoever.

I respectfully disagree. I spend the last few days thinking about a
solution about optimally scheduling the constrained number of kmaps. The
number of kmap/kunmaps can easily be reduced by allocating on a
first-come-first-serve base, and keeping a shared kmap for all other.
This is optimal in terms of kmap/kunmaps, but it's not in terms of
memcpy bouncing for fragmented scatterlists.

Now, I found a solution for optimal mapping/remapping to minimize the
bouncing, but in fact it doesn't make sense anymore, because, even
though my algorithm does not enforce any single unnecessary pass over
the scatterlist set, it needs to book-keep too much queues, that their
maintenance causes more work than the memcpy work it tries to prevent.
It only safes work, when the stepsize is irregularly large, like >200
byte. I would have to introduce an artificial threshold level to decide
between memcpy-preventing behavior and the behavior outlined in the last
paragraph.

This is all getting more ugly than the ugliness I'm trying to escape. 

Conclusion: The idea of high-mem and low-mem seperation is fundamentally
broken. The limitation of page table entries to a fixed set is causing
more complications than it solves. Laziness to do things right at memory
management shifts the burden to the users of the interface. 

Being disgusted by the highmem interface and the "ungenericness" of my
generic workaround, there is not going to be any update to my LRW work
from my side. This patch set is dead.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[David S. Miller]

On Mon, 14 Feb 2005 14:20:34 +0100
Fruhwirth Clemens <clemens@endorphin.org> wrote:

> Conclusion: The idea of high-mem and low-mem seperation is fundamentally
> broken. The limitation of page table entries to a fixed set is causing
> more complications than it solves. Laziness to do things right at memory
> management shifts the burden to the users of the interface. 

Doing it "at memory management" is what many other OS's do and
is incredibly costly especially on SMP systems.  Please ponder
those issues for some time before you blast Linux's MM design
decisions.  They were not made in a vacuum.

I used to be heavily against this scheme long ago, but over time
I've seen more and more how it's the right thing to do.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1015 bytes --]

On Mon, 2005-02-14 at 07:56 -0800, David S. Miller wrote:
> On Mon, 14 Feb 2005 14:20:34 +0100
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> 
> > Conclusion: The idea of high-mem and low-mem seperation is fundamentally
> > broken. The limitation of page table entries to a fixed set is causing
> > more complications than it solves. Laziness to do things right at memory
> > management shifts the burden to the users of the interface. 
> 
> Doing it "at memory management" is what many other OS's do and
> is incredibly costly especially on SMP systems.  Please ponder
> those issues for some time before you blast Linux's MM design
> decisions.  They were not made in a vacuum.

There is nothing wrong with having special methods, that lack generality
but are superior in performance. There is something wrong, when there
are no other. And there are no other for holding three kmappings or more
concurrently.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[David S. Miller]

On Mon, 14 Feb 2005 18:06:39 +0100
Fruhwirth Clemens <clemens@endorphin.org> wrote:

> There is nothing wrong with having special methods, that lack generality
> but are superior in performance. There is something wrong, when there
> are no other. And there are no other for holding three kmappings or more
> concurrently.

You want more resources in a context where no such thing exists,
in interrupt processing context.  There the stack is limited, allocatable
memory is limited, etc. etc. etc.  And all of this is because you cannot
sleep in interrupt context.

Resources are fixed in this environment exactly becuase one cannot
sleep or wait on events.  It's supposed to be fast processing, deferring
more involved work to process context.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 1164 bytes --]

On Mon, 2005-02-14 at 09:07 -0800, David S. Miller wrote:
> On Mon, 14 Feb 2005 18:06:39 +0100
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> 
> > There is nothing wrong with having special methods, that lack generality
> > but are superior in performance. There is something wrong, when there
> > are no other. And there are no other for holding three kmappings or more
> > concurrently.
> 
> You want more resources in a context where no such thing exists,
> in interrupt processing context.  There the stack is limited, allocatable
> memory is limited, etc. etc. etc.  And all of this is because you cannot
> sleep in interrupt context.

I have said nothing about sleeping in interrupt or softirq context.

First, one has to make kmap fallible. Second, ensure that it does not
fail often. This can be done by creating a page table pool, where kmap
can allocate page tables from, when all of the remaining page tables are
full. The mempool is of course refilled at the next occasion.

For stuff, that cannot be allowed to fail, kmap_atomic is still there.
-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Andrew Morton]

Fruhwirth Clemens <clemens@endorphin.org> wrote:
>
> First, one has to make kmap fallible.

I think it would be relatively simple and sane to modify the existing
kmap() implementations to add a new try_kmap() which is atomic and returns
failure if it would have needed to sleep.

That being said, kmap() is a sort of old and deprecated thing which scales
badly on SMP.  We've put considerable work into moving over to
kmap_atomic() and using nice tight short code regions where atomic
kmappings are held.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 583 bytes --]

On Mon, 2005-02-14 at 10:16 -0800, Andrew Morton wrote:
> Fruhwirth Clemens <clemens@endorphin.org> wrote:
> >
> > First, one has to make kmap fallible.
> 
> I think it would be relatively simple and sane to modify the existing
> kmap() implementations to add a new try_kmap() which is atomic and returns
> failure if it would have needed to sleep.

Is anyone going to implement that? I would be willing to rework my
scatterwalk code one more time, but I'm not going to touch the kernel
vm.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Matt Mackall]

On Thu, Feb 10, 2005 at 12:17:24PM +0100, Fruhwirth Clemens wrote:
> On Thu, 2005-02-10 at 02:33 -0800, Andrew Morton wrote:
> > Fruhwirth Clemens <clemens@endorphin.org> wrote:
> > >
> > > On Wed, 2005-02-09 at 17:19 -0800, Andrew Morton wrote:
> > > > Fruhwirth Clemens <clemens@endorphin.org> wrote:
> > > > Adding a few more fixmap slots wouldn't hurt anyone.  But if you want an
> > > > arbitrarily large number of them then no, we cannot do that.
> > > 
> > > What magnitude is "few more"? 2, 10, 100?
> > 
> > Not 100.  10 would seem excessive.
> 
> Out of curiosity: Where does this limitation even come from? What
> prevents kmap_atomic from adding slots dynamically?

There's a single page of PTEs for mapping high memory and the atomic
slots are a small subset of that. They're fixed in number for
complexity reasons - we don't want to have an allocator here:

/*
 * kmap_atomic/kunmap_atomic is significantly faster than kmap/kunmap because
 * no global lock is needed and because the kmap code must perform a global TLB
 * invalidation when the kmap pool wraps.
 *

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[David S. Miller]

On Thu, 10 Feb 2005 02:33:44 -0800
Andrew Morton <akpm@osdl.org> wrote:

> > Is there an easy way to bring pages to lowmem? The cryptoapi is called
> > from the backlog of the networking stack, which is assigned in irq
> > context first and processed softirq context.
> 
> Are networking frames ever allocated from highmem?  Don't think so.

It is absolutely possible, especially over loopback.

It can happen on the send side for any device which indicates
the NETIF_F_HIGHDMA capability, and because loopback indicates
this feature this means we'll see such highmem pages in packets
on receive too.

There is thus also nothing preventing a real hardware device
from feeding highmem packets into the networking stack.

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Thu, 10 Feb 2005, Fruhwirth Clemens wrote:

> Because a tweak is different from an IV. There can be an arbitrary
> number of tweaks. For instance, EME takes 1 tweak per 512 bytes. If you
> have a 4k page to encrypt, you have to process 8 tweaks of whatever
> size. 
>  Therefore, you need 3 scatterlists: src, dst and the running along
> tweak.

The purpose of the scatterlists is to be able to process discontigous data 
at the page level.

The tweak, as I understand it, is something which you generate, and it is 
not inherently likely to be page-level clumps of data.  It does not ever 
need to be kmapped.

What you really need to do is use an array for the tweak (or possibly a
structure which maintains state about it if needed).


- James
-- 
James Morris
<jmorris@redhat.com>

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[Fruhwirth Clemens]

[-- Attachment #1: Type: text/plain, Size: 2054 bytes --]

On Wed, 2005-02-09 at 20:42 -0500, James Morris wrote:
> On Thu, 10 Feb 2005, Fruhwirth Clemens wrote:
> 
> > Because a tweak is different from an IV. There can be an arbitrary
> > number of tweaks. For instance, EME takes 1 tweak per 512 bytes. If you
> > have a 4k page to encrypt, you have to process 8 tweaks of whatever
> > size. 
> >  Therefore, you need 3 scatterlists: src, dst and the running along
> > tweak.
> 
> The purpose of the scatterlists is to be able to process discontigous data 
> at the page level.
> 
> The tweak, as I understand it, is something which you generate, and it is 
> not inherently likely to be page-level clumps of data.  It does not ever 
> need to be kmapped.

For LRW, the tweak is exactly as large as the bulk data itself, so
tweaksize = blocksize. Yes, it is usually generated and sequential, but
that may not be the case. I like to put the generation of the tweaks at
the client side, because it knows best where the tweaks come from and if
it likes fragmented tweaks or not.

Further, this interface is more naturally to any other tweakable cipher
mode. In contrast to a regular cipher:

E: {0,1}^k  x  {0,1}^n -> {0,1}^n

a tweakable cipher is:

E: {0,1}^k  x  {0,1}^t  x  {0,1}^n -> {0,1}^n

where k is key size, n block size and t is tweak size.
( http://www.cs.berkeley.edu/%7Edaw/papers/tweak-crypto02.ps )

In the special case of LRW, it would be possible to squeeze it into an
IV styled interface, which does auto-incrementation. But that's flawed.
It would put functionality, where it does not belong. Witha  tweakable
mode, the blocks are independent and are not linked in any way. The
interface should reflect this.

> What you really need to do is use an array for the tweak (or possibly a
> structure which maintains state about it if needed).

The LRW cipher mode is stateless. There is context information, but this
only a cache. Same applies for EME, and it's fellows.

-- 
Fruhwirth Clemens <clemens@endorphin.org>  http://clemens.endorphin.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH 01/04] Adding cipher mode context information to crypto_tfm

[James Morris]

On Mon, 24 Jan 2005, Fruhwirth Clemens wrote:

> This patch adds the ability for a cipher mode to store cipher mode specific
> information in crypto_tfm. This is necessary for LRW's precomputed
> GF-multiplication tables.

This one looks fine as part of the LRW patchset (i.e. not needed for 
generic scatterwalk).


- James
-- 
James Morris
<jmorris@redhat.com>