Skip to contentSkip to conversation

Adding cipher mode context information to crypto_tfm

PATCH In review Fruhwirth Clemens 8 participants 51 messages Jan 24, 2005 – Feb 22, 2005 Crypto API

lore
Share & tools
lore
#0 lore raw

PATCH 1/4 Adding cipher mode context information to crypto_tfm

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.

crypto/api.c +14 -3
@@ -3,6 +3,7 @@
  *
  * Copyright (c) 2002 James Morris <[email protected]>
  * Copyright (c) 2002 David S. Miller ([email protected])
+ * Copyright (c) 2004 Clemens Fruhwirth <[email protected]>
  *
  * Portions derived from Cryptoapi, by Alexander Kjeldaas <[email protected]>
  * 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);
crypto/internal.h +5 -0
@@ -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
#1 lore raw

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

Signature · 2 lines
James Morris
<[email protected]>
#2 lore raw
In reply to Fruhwirth Clemens
Quoted 4 lines · 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.

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.

#3 lore raw
Quoted 6 lines · Andrew Morton
Quoted 4 lines · 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.

Quoted 7 lines

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(..).

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#4 lore raw
In reply to Andrew Morton
Quoted 10 lines · Andrew Morton

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

Signature · 2 lines
James Morris
<[email protected]>
#5 lore raw
Quoted 7 lines · James Morris

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.

Quoted 6 lines

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?

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#6 lore raw
Quoted 3 lines · Fruhwirth Clemens

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.

Quoted 9 lines

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.

Quoted 2 lines

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

I would imagine so.

- James

Signature · 2 lines
James Morris
<[email protected]>
#7 lore raw
In reply to James Morris
Quoted 10 lines · James Morris
Quoted 8 lines · Andrew Morton

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.

Quoted 6 lines
Quoted 2 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#8 lore raw
Quoted 7 lines · Fruhwirth Clemens

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.

#9 lore raw
Quoted 11 lines · Andrew Morton
Quoted 7 lines · Fruhwirth Clemens

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(-)
crypto/cipher.c +152 -115
@@ -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,
crypto/scatterwalk.h +24 -13
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <[email protected]>
  * Copyright (c) 2002 Adam J. Richter <[email protected]>
  * Copyright (c) 2004 Jean-Luc Cooke <[email protected]>
+ * Copyright (c) 2005 Clemens Fruhwirth <[email protected]>
  *
  * 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 */
crypto/scatterwalk.c +101 -36

178 lines not on this page · raw message

#10 lore raw
Quoted 11 lines · Fruhwirth Clemens

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.

Quoted 6 lines

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).

Quoted 1 line

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

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

What does _gw mean?

crypto/cipher.c line 71

Quoted 4 lines
crypto/cipher.c +3 -1
-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).

crypto/cipher.c line 103

Quoted 1 line
crypto/cipher.c +1 -0
+	return ecb_template(tfm,dst,src,nbytes,tfm->__crt_alg->cra_cipher.cia_encrypt);

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

crypto/cipher.c line 122

Quoted 7 lines
crypto/cipher.c +7 -0
+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.

crypto/scatterwalk.h line 44

Quoted 4 lines
crypto/scatterwalk.h +4 -0
+#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.

Quoted 1 line

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

Ditto.

crypto/scatterwalk.c line 157

Quoted 2 lines
crypto/scatterwalk.c +2 -0
+        for(csg = walk_infos; csg->sw.sg; csg++) {
+		scatterwalk_map(&csg->sw, csg->ioflag);

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

crypto/scatterwalk.c line 163

Quoted 1 line
crypto/scatterwalk.c +1 -0
+	while(steps--) {

while ()

crypto/scatterwalk.c line 174

Quoted 4 lines
crypto/scatterwalk.c +4 -0
+		
+		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.

crypto/scatterwalk.c line 177

Quoted 2 lines
crypto/scatterwalk.c +2 -0
+		for(csg = walk_infos, cbuf = dispatch_list; csg->sw.sg; csg++, cbuf++) {	
+			if(csg->ioflag == 1) 

for ()
if ()

Review

Quoted 1 line
(quoted diff) +1 -0
+	for(csg = walk_infos; csg->sw.sg; csg++) {

Ditto.

- James

Signature · 2 lines
James Morris
<[email protected]>
#11 lore raw
Quoted 9 lines · James Morris
Quoted 3 lines · Fruhwirth Clemens

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!

Quoted 7 lines

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).

Quoted 1 line

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

What does _gw mean?

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

Quoted 9 lines

crypto/cipher.c line 122

Quoted 7 lines
crypto/cipher.c +7 -0
+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.

Quoted 6 lines

crypto/scatterwalk.c line 174

Quoted 3 lines
crypto/scatterwalk.c +3 -0
+		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?

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
maintainer
#12 lore raw
Quoted 2 lines · On Thu, 03 Feb 2005 00:28:29 +0100 Fruhwirth Clemens <[email protected]>…

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 :-)

#13 lore raw
Quoted 3 lines · David S. Miller

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
maintainer
#14 lore raw
Quoted 2 lines · On Thu, 03 Feb 2005 01:21:35 +0100 Fruhwirth Clemens <[email protected]>…

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.

#15 lore raw
In reply to Fruhwirth Clemens
Quoted 2 lines · Fruhwirth Clemens

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

#16 lore raw
Quoted 7 lines · Michal Ludvig
Quoted 2 lines · Fruhwirth Clemens

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 :)

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#17 lore raw
In reply to Fruhwirth Clemens
Quoted 5 lines · Fruhwirth Clemens
Quoted 3 lines
Quoted 1 line

+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.

Quoted 9 lines
Quoted 6 lines

crypto/scatterwalk.c line 174

Quoted 3 lines
crypto/scatterwalk.c +3 -0
+		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

Signature · 2 lines
James Morris
<[email protected]>
#18 lore raw
Quoted 2 lines · James Morris

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

Signature · 2 lines
James Morris
<[email protected]>
#19 lore raw
In reply to James Morris
Quoted 8 lines · James Morris

crypto/scatterwalk.h line 44

Quoted 4 lines · Fruhwirth Clemens
crypto/scatterwalk.h +4 -0
+#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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#20 lore raw
Quoted 16 lines · Fruhwirth Clemens

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:

Quoted 7 lines

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.

Quoted 5 lines

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

Signature · 2 lines
James Morris
<[email protected]>
#21 lore raw
In reply to James Morris
Quoted 8 lines · James Morris

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.

crypto/cipher.c +187 -145
@@ -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;
 	}
crypto/scatterwalk.h +19 -13
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <[email protected]>
  * Copyright (c) 2002 Adam J. Richter <[email protected]>
  * Copyright (c) 2004 Jean-Luc Cooke <[email protected]>
+ * Copyright (c) 2005 Clemens Fruhwirth <[email protected]>
  *
  * 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 */
crypto/scatterwalk.c +106 -36

184 lines not on this page · raw message

#22 lore raw
Quoted 4 lines · Fruhwirth Clemens

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.

Quoted 5 lines

+ * 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.

crypto/scatterwalk.c line 154

Quoted 7 lines
crypto/scatterwalk.c +7 -0
+
+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.

crypto/scatterwalk.c line 183

Quoted 1 line
crypto/scatterwalk.c +1 -0
+				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.

crypto/scatterwalk.c line 43

Quoted 4 lines
crypto/scatterwalk.c +4 -0
+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

Signature · 2 lines
James Morris
<[email protected]>
#23 lore raw
Quoted 8 lines · James Morris
Quoted 5 lines · Fruhwirth Clemens

+ * 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.

Quoted 6 lines

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.

Quoted 1 line

[cutted]

Unquoted stuff changed according to your suggestions.

Quoted 10 lines

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);
}
Quoted 2 lines

rest_of_page should be just PAGE_SIZE - sg->offset (sg->offset should never extend beyond the page).

Changed.

Quoted 1 line

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

crypto/cipher.c +187 -145
@@ -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;
 	}
crypto/scatterwalk.h +22 -13
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <[email protected]>
  * Copyright (c) 2002 Adam J. Richter <[email protected]>
  * Copyright (c) 2004 Jean-Luc Cooke <[email protected]>
+ * Copyright (c) 2005 Clemens Fruhwirth <[email protected]>
  *
  * 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, -- [email protected] */
+
+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 */
crypto/scatterwalk.c +129 -40

219 lines not on this page · raw message

crypto/internal.h +19 -7
@@ -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)
crypto/digest.c +6 -4
@@ -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);
Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#24 lore raw
Quoted 16 lines · Fruhwirth Clemens
Quoted 8 lines · James Morris
Quoted 5 lines · Fruhwirth Clemens

+ * 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.

Quoted 6 lines

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.

Quoted 3 lines

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.

crypto/cipher.c +187 -145
@@ -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;
 	}
crypto/scatterwalk.h +23 -13
@@ -4,6 +4,7 @@
  * Copyright (c) 2002 James Morris <[email protected]>
  * Copyright (c) 2002 Adam J. Richter <[email protected]>
  * Copyright (c) 2004 Jean-Luc Cooke <[email protected]>
+ * Copyright (c) 2005 Clemens Fruhwirth <[email protected]>
  *
  * 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, -- [email protected] */
+
+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 */
crypto/scatterwalk.c +133 -44

229 lines not on this page · raw message

crypto/internal.h +19 -7
@@ -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)
crypto/digest.c +6 -4
@@ -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);
#25 lore raw
Quoted 6 lines · Fruhwirth Clemens

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

Signature · 2 lines
James Morris
<[email protected]>
#26 lore raw
Quoted 10 lines · James Morris
Quoted 6 lines · Fruhwirth Clemens

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?

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#27 lore raw
Quoted 3 lines · Fruhwirth Clemens
Quoted 1 line

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

Signature · 2 lines
James Morris
<[email protected]>
#28 lore raw
Quoted 4 lines · James Morris
Quoted 2 lines · Fruhwirth Clemens
Quoted 1 line

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

Quoted 8 lines
Quoted 1 line

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#29 lore raw
Quoted 3 lines · Fruhwirth Clemens

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

Signature · 2 lines
James Morris
<[email protected]>
#30 lore raw
Quoted 7 lines · James Morris
Quoted 3 lines · Fruhwirth Clemens

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.

Quoted 2 lines

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.

Quoted 3 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#31 lore raw
Quoted 3 lines · Fruhwirth Clemens

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.

#32 lore raw

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

Quoted 7 lines
Quoted 2 lines

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. :(

#33 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Fruhwirth Clemens

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?

Quoted 5 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#34 lore raw
Quoted 11 lines · Fruhwirth Clemens
Quoted 7 lines · Andrew Morton
Quoted 3 lines · Fruhwirth Clemens

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.

Quoted 9 lines
Quoted 5 lines

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.

Quoted 6 lines

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.

Quoted 5 lines

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.

Quoted 2 lines

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.

#35 lore raw
Quoted 10 lines · Andrew Morton
Quoted 7 lines · Fruhwirth Clemens
Quoted 3 lines · Andrew Morton

Fruhwirth Clemens <[email protected]> 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?

Quoted 5 lines
Quoted 3 lines

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.

Quoted 4 lines
Quoted 2 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#36 lore raw
Quoted 4 lines · Fruhwirth Clemens

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.

Quoted 3 lines

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

Signature · 2 lines
James Morris
<[email protected]>
#37 lore raw
Quoted 11 lines · James Morris
Quoted 4 lines · Fruhwirth Clemens

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?

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#38 lore raw
Quoted 8 lines · Fruhwirth Clemens

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.

Quoted 4 lines

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

Signature · 2 lines
James Morris
<[email protected]>
#39 lore raw
Quoted 3 lines · James Morris

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
maintainer
#40 lore raw
Quoted 4 lines · On Mon, 14 Feb 2005 14:20:34 +0100 Fruhwirth Clemens <[email protected]>…

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.

#41 lore raw
Quoted 8 lines · David S. Miller
Quoted 4 lines · On Mon, 14 Feb 2005 14:20:34 +0100 Fruhwirth Clemens <[email protected]>…

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.

Quoted 4 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
maintainer
#42 lore raw
Quoted 4 lines · On Mon, 14 Feb 2005 18:06:39 +0100 Fruhwirth Clemens <[email protected]>…

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.

#43 lore raw
Quoted 8 lines · David S. Miller
Quoted 4 lines · On Mon, 14 Feb 2005 18:06:39 +0100 Fruhwirth Clemens <[email protected]>…

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.

Quoted 4 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#44 lore raw
Quoted 2 lines · Fruhwirth Clemens

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.

#45 lore raw
Quoted 7 lines · Andrew Morton
Quoted 2 lines · Fruhwirth Clemens

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#46 lore raw
In reply to Fruhwirth Clemens
Quoted 8 lines · Fruhwirth Clemens
Quoted 7 lines · Andrew Morton
Quoted 6 lines · Fruhwirth Clemens
Quoted 3 lines · Andrew Morton

Fruhwirth Clemens <[email protected]> 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.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

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.
*

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#47 lore raw
In reply to Andrew Morton
Quoted 5 lines · On Thu, 10 Feb 2005 02:33:44 -0800 Andrew Morton <[email protected]> wrote:
Quoted 3 lines

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.

#48 lore raw
In reply to Fruhwirth Clemens
Quoted 6 lines · Fruhwirth Clemens

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

Signature · 2 lines
James Morris
<[email protected]>
#49 lore raw
Quoted 9 lines · James Morris
Quoted 6 lines · Fruhwirth Clemens

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.

Quoted 6 lines

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.

Quoted 2 lines

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.

Signature · 1 line
Fruhwirth Clemens <[email protected]>  http://clemens.endorphin.org
#50 lore raw
In reply to Fruhwirth Clemens
Quoted 3 lines · 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.

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

- James

Signature · 2 lines
James Morris
<[email protected]>