[Suspend2][ 0/2] Cryptoapi deflate fix.

[Suspend2][ 0/2] Cryptoapi deflate fix.

[Nigel Cunningham]

The deflate module doesn't properly complete the handling of PAGE_SIZE
chunks of data. This patch corrects that so that it can be used with
Suspend2.

[Suspend2][ 1/2] [Suspend2] Add cryptoapi LZF support.

[Nigel Cunningham]

Add a cryptoapi LZF module. Performance in suspending to disk can be
greatly improved by a fast compression algorithm. LZF provides this. It was
donated by Marc Alexander Lehmann under a dual BSD/GPL license.

Signed-off-by: Nigel Cunningham <nigel@suspend2.net>

 crypto/Kconfig  |    7 +
 crypto/Makefile |    1 
 crypto/lzf.c    |  335 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 343 insertions(+), 0 deletions(-)

diff --git a/crypto/Kconfig b/crypto/Kconfig
index c442f2e..36e0b71 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -316,6 +316,13 @@ config CRYPTO_DEFLATE
 	  
 	  You will most probably want this if using IPSec.
 
+config CRYPTO_LZF
+	tristate "LZF compression algorithm"
+	depends on CRYPTO
+	help
+	  This is the LZF algorithm. It is especially useful for Suspend2,
+	  because it achieves good compression quickly.
+
 config CRYPTO_MICHAEL_MIC
 	tristate "Michael MIC keyed digest algorithm"
 	depends on CRYPTO
diff --git a/crypto/Makefile b/crypto/Makefile
index d287b9e..9845a6d 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -30,5 +30,6 @@ obj-$(CONFIG_CRYPTO_ANUBIS) += anubis.o
 obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o
 obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o
 obj-$(CONFIG_CRYPTO_CRC32C) += crc32c.o
+obj-$(CONFIG_CRYPTO_LZF) += lzf.o
 
 obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
diff --git a/crypto/lzf.c b/crypto/lzf.c
new file mode 100644
index 0000000..fce1621
--- /dev/null
+++ b/crypto/lzf.c
@@ -0,0 +1,335 @@
+/* 
+ * Cryptoapi LZF compression module.
+ *
+ * Copyright (c) 2004-2005 Nigel Cunningham <nigel@suspend2.net>
+ *
+ * based on the deflate.c file:
+ * 
+ * Copyright (c) 2003 James Morris <jmorris@intercode.com.au>
+ * 
+ * and upon the LZF compression module donated to the Suspend2 project with
+ * the following copyright:
+ *
+ * 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
+ * Software Foundation; either version 2 of the License, or (at your option) 
+ * any later version.
+ * Copyright (c) 2000-2003 Marc Alexander Lehmann <pcg@goof.com>
+ * 
+ * Redistribution and use in source and binary forms, with or without modifica-
+ * tion, are permitted provided that the following conditions are met:
+ * 
+ *   1.  Redistributions of source code must retain the above copyright notice,
+ *       this list of conditions and the following disclaimer.
+ * 
+ *   2.  Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ * 
+ *   3.  The name of the author may not be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
+ * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
+ * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
+ * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
+ * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
+ * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * the GNU General Public License version 2 (the "GPL"), in which case the
+ * provisions of the GPL are applicable instead of the above. If you wish to
+ * allow the use of your version of this file only under the terms of the
+ * GPL and not to allow others to use your version of this file under the
+ * BSD license, indicate your decision by deleting the provisions above and
+ * replace them with the notice and other provisions required by the GPL. If
+ * you do not delete the provisions above, a recipient may use your version
+ * of this file under either the BSD or the GPL.
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/crypto.h>
+#include <linux/err.h>
+#include <linux/vmalloc.h>
+#include <asm/string.h>
+
+struct lzf_ctx {
+	void *hbuf;
+	unsigned int bufofs;
+};
+
+/*
+ * size of hashtable is (1 << hlog) * sizeof (char *)
+ * decompression is independent of the hash table size
+ * the difference between 15 and 14 is very small
+ * for small blocks (and 14 is also faster).
+ * For a low-memory configuration, use hlog == 13;
+ * For best compression, use 15 or 16.
+ */
+static const int hlog = 14;
+
+/*
+ * don't play with this unless you benchmark!
+ * decompression is not dependent on the hash function
+ * the hashing function might seem strange, just believe me
+ * it works ;)
+ */
+static inline u16 first(const u8 *p)
+{
+	return ((p[0]) << 8) + p[1];
+}
+
+static inline u16 next(u8 v, const u8 *p)
+{
+	return ((v) << 8) + p[2];
+}
+
+static inline u32 idx(unsigned int h)
+{
+	return (((h ^ (h << 5)) >> (3*8 - hlog)) + h*3) & ((1 << hlog) - 1);
+}
+
+/*
+ * IDX works because it is very similar to a multiplicative hash, e.g.
+ * (h * 57321 >> (3*8 - hlog))
+ * the next one is also quite good, albeit slow ;)
+ * (int)(cos(h & 0xffffff) * 1e6)
+ */
+
+static const int max_lit = (1 <<  5);
+static const int max_off = (1 << 13);
+static const int max_ref = ((1 <<  8) + (1 << 3));
+
+/*
+ * compressed format
+ *
+ * 000LLLLL <L+1>    ; literal
+ * LLLOOOOO oooooooo ; backref L
+ * 111OOOOO LLLLLLLL oooooooo ; backref L+7
+ *
+ */
+
+static void lzf_compress_exit(void *context)
+{
+	struct lzf_ctx *ctx = (struct lzf_ctx *)context;
+
+	if (ctx->hbuf) {
+		vfree(ctx->hbuf);
+		ctx->hbuf = NULL;
+	}
+}
+
+static int lzf_compress_init(void *context)
+{
+	struct lzf_ctx *ctx = (struct lzf_ctx *)context;
+
+	/* Get LZF ready to go */
+	ctx->hbuf = vmalloc_32((1 << hlog) * sizeof(char *));
+	if (!ctx->hbuf) {
+		printk(KERN_WARNING
+		       "Failed to allocate %ld bytes for lzf workspace\n",
+		       (long) ((1 << hlog) * sizeof(char *)));
+		return -ENOMEM;
+	}
+	return 0;
+}
+
+static int lzf_compress(void *context, const u8 *in_data, unsigned int in_len,
+			u8 *out_data, unsigned int *out_len)
+{
+	struct lzf_ctx *ctx = (struct lzf_ctx *)context;
+	const u8 **htab = ctx->hbuf;
+	const u8 **hslot;
+	const u8 *ip = in_data;
+	u8 *op = out_data;
+	const u8 *in_end = ip + in_len;
+	u8 *out_end = op + *out_len - 3;
+	const u8 *ref;
+
+	unsigned int hval = first(ip);
+	unsigned long off;
+	int lit = 0;
+
+	memset(htab, 0, sizeof(htab));
+
+	for (;;) {
+		if (ip < in_end - 2) {
+			hval = next(hval, ip);
+			hslot = htab + idx(hval);
+			ref = *hslot;
+			*hslot = ip;
+
+			if ((off = ip - ref - 1) < max_off
+			    && ip + 4 < in_end && ref > in_data
+			    && *(u16 *) ref == *(u16 *) ip && ref[2] == ip[2]
+			    ) {
+				/* match found at *ref++ */
+				unsigned int len = 2;
+				unsigned int maxlen = in_end - ip - len;
+				maxlen = maxlen > max_ref ? max_ref : maxlen;
+
+				do
+					len++;
+				while (len < maxlen && ref[len] == ip[len]);
+
+				if (op + lit + 1 + 3 >= out_end) {
+					*out_len = PAGE_SIZE;
+					return 0;
+				}
+
+				if (lit) {
+					*op++ = lit - 1;
+					lit = -lit;
+					do
+						*op++ = ip[lit];
+					while (++lit);
+				}
+
+				len -= 2;
+				ip++;
+
+				if (len < 7) {
+					*op++ = (off >> 8) + (len << 5);
+				} else {
+					*op++ = (off >> 8) + (7 << 5);
+					*op++ = len - 7;
+				}
+
+				*op++ = off;
+
+				ip += len;
+				hval = first(ip);
+				hval = next(hval, ip);
+				htab[idx(hval)] = ip;
+				ip++;
+				continue;
+			}
+		} else if (ip == in_end)
+			break;
+
+		/* one more literal byte we must copy */
+		lit++;
+		ip++;
+
+		if (lit == max_lit) {
+			if (op + 1 + max_lit >= out_end) {
+				*out_len = PAGE_SIZE;
+				return 0;
+			}
+
+			*op++ = max_lit - 1;
+			memcpy(op, ip - max_lit, max_lit);
+			op += max_lit;
+			lit = 0;
+		}
+	}
+
+	if (lit) {
+		if (op + lit + 1 >= out_end) {
+			*out_len = PAGE_SIZE;
+			return 0;
+		}
+
+		*op++ = lit - 1;
+		lit = -lit;
+		do
+			*op++ = ip[lit];
+		while (++lit);
+	}
+
+	*out_len = op - out_data;
+	return 0;
+}
+
+static int lzf_decompress(void *context, const u8 *src, unsigned int slen,
+			  u8 *dst, unsigned int *dlen)
+{
+	u8 const *ip = src;
+	u8 *op = dst;
+	u8 const *const in_end = ip + slen;
+	u8 *const out_end = op + *dlen;
+
+	do {
+		unsigned int ctrl = *ip++;
+
+		if (ctrl < (1 << 5)) {	/* literal run */
+			ctrl++;
+
+			if (op + ctrl > out_end) {
+				*dlen = PAGE_SIZE;
+				return 0;
+			}
+			memcpy(op, ip, ctrl);
+			op += ctrl;
+			ip += ctrl;
+		} else {	/* back reference */
+
+			unsigned int len = ctrl >> 5;
+
+			u8 *ref = op - ((ctrl & 0x1f) << 8) - 1;
+
+			if (len == 7)
+				len += *ip++;
+
+			ref -= *ip++;
+
+			if (op + len + 2 > out_end) {
+				*dlen = PAGE_SIZE;
+				return 0;
+			}
+
+			if (ref < (u8 *) dst) {
+				*dlen = PAGE_SIZE;
+				return 0;
+			}
+
+			*op++ = *ref++;
+			*op++ = *ref++;
+
+			do
+				*op++ = *ref++;
+			while (--len);
+		}
+	}
+	while (op < out_end && ip < in_end);
+
+	*dlen = op - (u8 *) dst;
+	return 0;
+}
+
+static struct crypto_alg alg = {
+	.cra_name = "lzf",
+	.cra_flags = CRYPTO_ALG_TYPE_COMPRESS,
+	.cra_ctxsize = 0,
+	.cra_module = THIS_MODULE,
+	.cra_list = LIST_HEAD_INIT(alg.cra_list),
+	.cra_u = {.compress = {
+			       .coa_init = lzf_compress_init,
+			       .coa_exit = lzf_compress_exit,
+			       .coa_compress = lzf_compress,
+			       .coa_decompress = lzf_decompress}}
+};
+
+static int __init init(void)
+{
+	return crypto_register_alg(&alg);
+}
+
+static void __exit fini(void)
+{
+	crypto_unregister_alg(&alg);
+}
+
+module_init(init);
+module_exit(fini);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZF Compression Algorithm");
+MODULE_AUTHOR("Marc Alexander Lehmann & Nigel Cunningham");

--
Nigel Cunningham		nigel at suspend2 dot net

[Suspend2][ 2/2] [Suspend2] Make cryptoapi deflate module handle full pages.

[Nigel Cunningham]

The cryptoapi deflate module currently returns an error when it
successfully handles a full page of data at the end of a compressed stream.
This patch addresses that behaviour.

Signed-off-by: Nigel Cunningham <nigel@suspend2.net>

 crypto/deflate.c |   11 +++++++++--
 1 files changed, 9 insertions(+), 2 deletions(-)

diff --git a/crypto/deflate.c b/crypto/deflate.c
index f209368..2a38593 100644
--- a/crypto/deflate.c
+++ b/crypto/deflate.c
@@ -142,8 +142,15 @@ static int deflate_compress(void *ctx, c
 
 	ret = zlib_deflate(stream, Z_FINISH);
 	if (ret != Z_STREAM_END) {
-		ret = -EINVAL;
-		goto out;
+	    	if (!(ret == Z_OK && !stream->avail_in && !stream->avail_out)) {
+			ret = -EINVAL;
+			goto out;
+		} else {
+			u8 zerostuff = 0;
+			stream->next_out = &zerostuff;
+			stream->avail_out = 1; 
+			ret = zlib_deflate(stream, Z_FINISH);
+		}
 	}
 	ret = 0;
 	*dlen = stream->total_out;

--
Nigel Cunningham		nigel at suspend2 dot net

Re: [Suspend2][ 0/2] Cryptoapi deflate fix.

[Rafael J. Wysocki]

On Monday 26 June 2006 18:51, Nigel Cunningham wrote:
> 
> The deflate module doesn't properly complete the handling of PAGE_SIZE
> chunks of data. This patch corrects that so that it can be used with
> Suspend2.

Well, it also adds the LZF support to the cryptoapi.  These are two different
things.

If you think the deflate modules needs to be fixed, you should post the patch
for it separately, I think.

Rafael

Re: [Suspend2][ 0/2] Cryptoapi deflate fix.

[Nigel Cunningham]

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

Hi.

On Tuesday 27 June 2006 06:09, Rafael J. Wysocki wrote:
> On Monday 26 June 2006 18:51, Nigel Cunningham wrote:
> > The deflate module doesn't properly complete the handling of PAGE_SIZE
> > chunks of data. This patch corrects that so that it can be used with
> > Suspend2.
>
> Well, it also adds the LZF support to the cryptoapi.  These are two
> different things.
>
> If you think the deflate modules needs to be fixed, you should post the
> patch for it separately, I think.
>
> Rafael

Sorry for the bad choice of heading. I have posted this before and emailed it 
direct to Herbert, but he (rightly) doesn't see the need while suspend2 isn't 
merged.

Regards,

Nigel
-- 
See http://www.suspend2.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [Suspend2][ 0/2] Cryptoapi deflate fix.

[Herbert Xu]

Nigel Cunningham <nigel@suspend2.net> wrote:
> 
> Sorry for the bad choice of heading. I have posted this before and emailed it 
> direct to Herbert, but he (rightly) doesn't see the need while suspend2 isn't 
> merged.

Hmm, I don't recall ever telling you that.

I searched through my mail archive here is what I said to you last year
on these two patches.  As far as I can see I don't have a reply from you
on either subject.  So if you could reply to my questions below then I
can consider your patches again.

1. Deflate fix:

> > Hi Nigel, I need a bit more information about this patch.
> > Do you have a specific input stream that requires a fix like
> > this?
> 
> Yes, Suspend2 if the user selects deflate as their compressor. The
> output data will be PAGE_SIZE chunks, but deflate sometimes thinks it
> has an extra byte to give us back.

Are you saying that you're feeding it PAGE_SIZE chunks and it's
giving you back something bigger than a page? That is expected
since the nature of compression in general is that not everything
is compressible.  Data streams which are not compressible will
end up bigger than what you start with.

What would be a bug is if you feed it something that's
deflateBound^-1(PAGE_SIZE) bytes long and it spits back
something that's longer than a page.

> I agree that it's ugly and don't recall using it when I had gzip support
> in an earlier version of Suspend2. Are you thinking there might be a
> better way? If so, I can dig out the old (non crypto api) code.

Well if you could give me a snippet of code that actually uses this
stuff to compress pages then I might have a better idea of what it's
trying to do.

2. LZF:

> +static int lzf_compress_init(void *context)
> +{
> +     struct lzf_ctx *ctx = (struct lzf_ctx *)context;
> +
> +     /* Get LZF ready to go */
> +     ctx->hbuf = vmalloc_32((1 << hlog) * sizeof(char *));

Any reason why vmalloc can't be used?

> +     /* Allocate local buffer */
> +     ctx->local_buffer = (char *)get_zeroed_page(GFP_ATOMIC);

> +     /* Allocate page buffer */
> +     ctx->page_buffer = (char *)get_zeroed_page(GFP_ATOMIC);

Where are these two buffers used anyway?

> +     if (!ctx->page_buffer) {
> +             free_page((unsigned long)ctx->local_buffer);
> +             lzf_compress_exit(ctx);

This is a double-free of local_buffer.

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

Re: [Suspend2][ 0/2] Cryptoapi deflate fix.

[Nigel Cunningham]

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

Hi.

On Tuesday 27 June 2006 16:00, Herbert Xu wrote:
> Nigel Cunningham <nigel@suspend2.net> wrote:
> > Sorry for the bad choice of heading. I have posted this before and
> > emailed it direct to Herbert, but he (rightly) doesn't see the need while
> > suspend2 isn't merged.
>
> Hmm, I don't recall ever telling you that.

Ok. Sorry for my wonky memory then :)

> I searched through my mail archive here is what I said to you last year
> on these two patches.  As far as I can see I don't have a reply from you
> on either subject.  So if you could reply to my questions below then I
> can consider your patches again.
>
> 1. Deflate fix:
> > > Hi Nigel, I need a bit more information about this patch.
> > > Do you have a specific input stream that requires a fix like
> > > this?
> >
> > Yes, Suspend2 if the user selects deflate as their compressor. The
> > output data will be PAGE_SIZE chunks, but deflate sometimes thinks it
> > has an extra byte to give us back.
>
> Are you saying that you're feeding it PAGE_SIZE chunks and it's
> giving you back something bigger than a page? That is expected
> since the nature of compression in general is that not everything
> is compressible.  Data streams which are not compressible will
> end up bigger than what you start with.
>
> What would be a bug is if you feed it something that's
> deflateBound^-1(PAGE_SIZE) bytes long and it spits back
> something that's longer than a page.

Yes, I'm always feeding it PAGE_SIZE chunks and compressing each page 
separately. It's a long time since I looked at or thought about this, so I'll 
spend some more time getting it fresh in my head if you like.

> > I agree that it's ugly and don't recall using it when I had gzip support
> > in an earlier version of Suspend2. Are you thinking there might be a
> > better way? If so, I can dig out the old (non crypto api) code.
>
> Well if you could give me a snippet of code that actually uses this
> stuff to compress pages then I might have a better idea of what it's
> trying to do.
>
> 2. LZF:
> > +static int lzf_compress_init(void *context)
> > +{
> > +     struct lzf_ctx *ctx = (struct lzf_ctx *)context;
> > +
> > +     /* Get LZF ready to go */
> > +     ctx->hbuf = vmalloc_32((1 << hlog) * sizeof(char *));
>
> Any reason why vmalloc can't be used?

I just left Marc's original code as it was, so I'm not completely sure, but I 
guess it's because we want lowmem.

> > +     /* Allocate local buffer */
> > +     ctx->local_buffer = (char *)get_zeroed_page(GFP_ATOMIC);
> >
> > +     /* Allocate page buffer */
> > +     ctx->page_buffer = (char *)get_zeroed_page(GFP_ATOMIC);
>
> Where are these two buffers used anyway?

Page_buffer is the destination buffer passed to the compressor. Local buffer 
is used to buffer the output for writing (and vv).

> > +     if (!ctx->page_buffer) {
> > +             free_page((unsigned long)ctx->local_buffer);
> > +             lzf_compress_exit(ctx);
>
> This is a double-free of local_buffer.

Is that from our previous correspondence? I can't find anything like it now.

Regards,

Nigel

> Cheers,

-- 
See http://www.suspend2.net for Howtos, FAQs, mailing
lists, wiki and bugzilla info.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [Suspend2][ 0/2] Cryptoapi deflate fix.

[Herbert Xu]

On Tue, Jun 27, 2006 at 05:02:46PM +1000, Nigel Cunningham wrote:
> 
> Ok. Sorry for my wonky memory then :)

No problems.

> Yes, I'm always feeding it PAGE_SIZE chunks and compressing each page 
> separately. It's a long time since I looked at or thought about this, so I'll 
> spend some more time getting it fresh in my head if you like.

If you could give me a minimal test case to work with that'd be great.

> I just left Marc's original code as it was, so I'm not completely sure, but I 
> guess it's because we want lowmem.

The question is why do you need lowmem? It doesn't appear to be obvious
by looking at the code.

> > This is a double-free of local_buffer.
> 
> Is that from our previous correspondence? I can't find anything like it now.

Yes, that was from a year ago before you fixed the code :) Feel free to
resubmit this once you've addressed the vmalloc question.

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