Skip to contentSkip to conversation

Add LZO1X compression support to the kernel

PATCH In review Richard Purdie 8 participants 12 messages May 2, 2007 – May 13, 2007 Library code

lore
Share & tools
lore

Richard Purdie

author
#0 lore raw

PATCH 1/1 Add LZO1X compression support to the kernel

Current thinking is that lzo should get merged directly followed by the subsystem parts through their specific trees. It appears this should make it onto LKML despite the size so here goes.

Please keep in mind I haven't reformatted the LZO code itself as if I do so, it will make maintenance of it against any changes in LZO itself near impossible. In its current form, it should be possible to diff against upstream. All the bad formatting is confined to a handful of files in lib/lzo/ and the kernel interface should be clean.

I realise a maze of ifdefs still remain. I've already spent a lot of time removing a ton of them and going much further might start to affect diffability of the code - I hoping whats there is a good compromise.

I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

Add LZO1X compression/decompression support to the kernel.

This is based on the standard userspace lzo library, particularly minilzo with the headers much trimmed down and simplified for kernel use. Its structured so that it should still diff with the userspace version for ease of future updating.

Signed-off-by Richard Purdie <[email protected]>
---
 include/linux/lzo.h |   63 ++
 lib/Kconfig         |    5 +
 lib/Makefile        |    1 +
 lib/lzo/Makefile    |    3 +
 lib/lzo/lzoconf.h   |  186 ++++++
 lib/lzo/lzodefs.h   |  463 ++++++++++++++
 lib/lzo/lzointf.c   |   37 ++
 lib/lzo/minilzo.c   | 1771 +++++++++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 2529 insertions(+), 0 deletions(-)
include/linux/lzo.h new file +63 -0
new file mode 100644
index 0000000..ef72438
@@ -0,0 +1,63 @@
+/*
+ * LZO Public Kernel Interface
+ * A mini subset of the LZO real-time data compression library
+ *
+ * Copyright (C) 2007 Nokia Corporation. All rights reserved.
+ *
+ * Author: Richard Purdie <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA
+ *
+ */
+
+#ifndef __LZO_H
+#define __LZO_H
+
+#define LZO1X_MEM_COMPRESS	(16384 * sizeof(unsigned char *))
+#define LZO1X_MEM_DECOMPRESS    (0)
+#define LZO1X_1_MEM_COMPRESS	LZO1X_MEM_COMPRESS
+
+#define lzo1x_worst_compress(x) (x + (x / 64) + 16 + 3)
+
+const unsigned char * lzo_copyright(void);
+
+int lzo1x_1_compress(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem);
+
+int lzo1x_decompress(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem /* NOT USED */);
+
+/* safe decompression with overrun testing */
+int lzo1x_decompress_safe(const unsigned char *src, unsigned long src_len,
+			unsigned char *dst, unsigned long *dst_len,
+			void *wrkmem /* NOT USED */);
+
+/*
+ * Return values (< 0 = Error)
+ */
+#define LZO_E_OK                    0
+#define LZO_E_ERROR                 (-1)
+#define LZO_E_OUT_OF_MEMORY         (-2)
+#define LZO_E_NOT_COMPRESSIBLE      (-3)
+#define LZO_E_INPUT_OVERRUN         (-4)
+#define LZO_E_OUTPUT_OVERRUN        (-5)
+#define LZO_E_LOOKBEHIND_OVERRUN    (-6)
+#define LZO_E_EOF_NOT_FOUND         (-7)
+#define LZO_E_INPUT_NOT_CONSUMED    (-8)
+#define LZO_E_NOT_YET_IMPLEMENTED   (-9)
+
+#endif
lib/Kconfig +5 -0
index 3842499..b39d4e5 100644
@@ -47,6 +47,11 @@ config AUDIT_GENERIC
 	depends on AUDIT && !AUDIT_ARCH
 	default y
 
+config LZO
+	tristate "LZO compressor/decompressor"
+	help
+	  minilzo implementation in kernelspace.
+
 #
 # compression support is select'ed if needed
 #
lib/Makefile +1 -0
index ae57f35..442c63f 100644
@@ -48,6 +48,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
 obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
 obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
 obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
+obj-$(CONFIG_LZO)          += lzo/
 
 obj-$(CONFIG_TEXTSEARCH) += textsearch.o
 obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
lib/lzo/Makefile new file +3 -0
new file mode 100644
index 0000000..cdb4809
@@ -0,0 +1,3 @@
+lzo-objs := minilzo.o lzointf.o
+
+obj-$(CONFIG_LZO) += lzo.o
lib/lzo/lzoconf.h new file +186 -0

186 lines not on this page · raw message

lib/lzo/lzodefs.h new file +463 -0

463 lines not on this page · raw message

lib/lzo/lzointf.c new file +37 -0
new file mode 100644
index 0000000..182354b
@@ -0,0 +1,37 @@
+/*
+ * LZO Public Kernel Interface
+ *
+ * Copyright (C) 2007 Nokia Corporation. All rights reserved.
+ *
+ * Author: Richard Purdie <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/init.h>
+#include <linux/lzo.h>
+#include "lzoconf.h"
+
+EXPORT_SYMBOL_GPL(lzo_copyright);
+EXPORT_SYMBOL_GPL(lzo1x_1_compress);
+EXPORT_SYMBOL_GPL(lzo1x_decompress);
+EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
+
+MODULE_LICENSE("GPL")
+MODULE_DESCRIPTION("LZO compression library")
+
lib/lzo/minilzo.c new file +1771 -0

1,771 lines not on this page · raw message

#1 lore raw
Quoted 3 lines · Richard Purdie

I realise a maze of ifdefs still remain. I've already spent a lot of time removing a ton of them and going much further might start to affect diffability of the code - I hoping whats there is a good compromise.

I really don't think this is suitable for inclusion in the kernel. Any reason why you don't just fork the code and clean it up properly? Sure it will take some more work to track the original but how hard can it be for ~1700 lines of code?

#2 lore raw

Hi Richard, Pekka,

Quoted 9 lines · Pekka Enberg
Quoted 3 lines · Richard Purdie

I realise a maze of ifdefs still remain. I've already spent a lot of time removing a ton of them and going much further might start to affect diffability of the code - I hoping whats there is a good compromise.

I really don't think this is suitable for inclusion in the kernel. Any reason why you don't just fork the code and clean it up properly? Sure it will take some more work to track the original but how hard can it be for ~1700 lines of code?

I'd have to agree with that. When something gets ported to the kernel (from some userspace library, or from any other piece of software), then it _must_ be ported completely and follow the usual kernel style. In fact I bet you can knock off a cool couple of hundred lines of gunk from the patch just by doing a proper port and getting rid of those pointless typedefs, for example.

(On an unrelated note/rant, this was one of the reasons why I absolutely hate those MODSIGN patches being maintained by Red Hat/Fedora/etc that port the GNU MPI library to the kernel but don't do so properly, so that it can be diffed with future GNU MP releases for easy maintainability -- with the result that the patch ends up containing arch-specific assembly for platforms that Linux doesn't even run on! Good to see that at least you've taken the pains to avoid that kind of brain damage, but a full port would be better)

Thanks,
Satyam

maintainer
#3 lore raw
In reply to Richard Purdie
Quoted 20 lines · On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <[email protected]>…

Current thinking is that lzo should get merged directly followed by the subsystem parts through their specific trees. It appears this should make it onto LKML despite the size so here goes.

Please keep in mind I haven't reformatted the LZO code itself as if I do so, it will make maintenance of it against any changes in LZO itself near impossible. In its current form, it should be possible to diff against upstream. All the bad formatting is confined to a handful of files in lib/lzo/ and the kernel interface should be clean.

I realise a maze of ifdefs still remain. I've already spent a lot of time removing a ton of them and going much further might start to affect diffability of the code - I hoping whats there is a good compromise.

I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

Quoted 6 lines

Add LZO1X compression/decompression support to the kernel.

This is based on the standard userspace lzo library, particularly minilzo with the headers much trimmed down and simplified for kernel use. Its structured so that it should still diff with the userspace version for ease of future updating.

Well that's attractive-looking code.

Why is this needed? What code plans to use it?

How many buffer overruns are there in it?

#4 lore raw
Quoted 1 line · Andrew Morton

Well that's attractive-looking code.

It's compression code. I've never seen compression code look nice :)

Quoted 1 line

Why is this needed? What code plans to use it?

I'm itching to use it in JFFS2. Richard claims a 10% boot time speedup and 40% improvement on file read speed, with only a slight drop in the file compression ratio (when compared to zlib).

Quoted 1 line

How many buffer overruns are there in it?

That I'm afraid I cannot tell you.

Signature · 1 line
dwmw2
author
#5 lore raw
Quoted 10 lines · David Woodhouse
Quoted 1 line · Andrew Morton

Well that's attractive-looking code.

It's compression code. I've never seen compression code look nice :)

Quoted 1 line

Why is this needed? What code plans to use it?

I'm itching to use it in JFFS2. Richard claims a 10% boot time speedup and 40% improvement on file read speed, with only a slight drop in the file compression ratio (when compared to zlib).

Right, the speed improvement is noticeable and useful. JFFS2 is the primary use case, I've also implemented a crypto interface for it.

Quoted 3 lines
Quoted 1 line

How many buffer overruns are there in it?

That I'm afraid I cannot tell you.

There is a "safe" decompression function which does bounds checking so its at least been thought about by the author. The code has been around in userspace for a while so hopefully any issues have been ironed out before now.

Richard

#6 lore raw
In reply to Andrew Morton
Quoted 11 lines · Andrew Morton
Quoted 6 lines · On Wed, 02 May 2007 09:56:23 +0100 Richard Purdie <[email protected]>…

Add LZO1X compression/decompression support to the kernel.

This is based on the standard userspace lzo library, particularly minilzo with the headers much trimmed down and simplified for kernel use. Its structured so that it should still diff with the userspace version for ease of future updating.

Well that's attractive-looking code.
Why is this needed? What code plans to use it?

Perhaps squashfs [not included] could use it as an alternative to zlib or LZMA* [not included either].

* That's floating patches not in the official squashfs AFAICT.

Jan

#7 lore raw
In reply to Richard Purdie
Quoted 4 lines · Richard Purdie

...
I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

This sounds as if LZO is GPL incompatible similar to code under the 4 clause BSD licence.

Quoted 8 lines

...

lib/lzo/minilzo.c new file +7 -0
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */
+
+const char __lzo_copyright[] =
+#if !defined(__LZO_IN_MINLZO)
+    LZO_VERSION_STRING;

lib/lzo/minilzo.c line 195

Quoted 10 lines
lib/lzo/minilzo.c new file +9 -0
+#else
+    "\r\n\n"
+    "LZO data compression library.\n"
+    "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 Markus Franz Xaver Johannes Oberhumer\n"
+    "<[email protected]>\n"
+    "http://www.oberhumer.com $\n\n"
+    "$Id: LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE " $\n"
+    "$Built: " __DATE__ " " __TIME__ " $\n"
+#endif
...

cu
Adrian

Signature · 4 lines
       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed
author
#8 lore raw
Quoted 13 lines · Adrian Bunk
Quoted 4 lines · Richard Purdie

...
I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

This sounds as if LZO is GPL incompatible similar to code under the 4 clause BSD licence.

Quoted 4 lines

...
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */

I've had a reply from the copyright holder/author saying he's going to change this wording in the next LZO release and that the code *is* GPLv2 licensed as per the headers on the files.

Regards,

Richard

maintainer
#9 lore raw
Quoted 10 lines · On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <[email protected]>…
Quoted 9 lines · Adrian Bunk
Quoted 4 lines · Richard Purdie

...
I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

This sounds as if LZO is GPL incompatible similar to code under the 4 clause BSD licence.

Quoted 9 lines
Quoted 4 lines
Quoted 4 lines

...
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */

I've had a reply from the copyright holder/author saying he's going to change this wording in the next LZO release and that the code *is* GPLv2 licensed as per the headers on the files.

It would be ideal if the author of that code could send us a
signed-off-by: as per secton 11 of Documentation/SubmittingPatches.

author
#10 lore raw
Quoted 17 lines · Andrew Morton
Quoted 15 lines · On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <[email protected]>…
Quoted 13 lines · Adrian Bunk
Quoted 4 lines · Richard Purdie

...
I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

This sounds as if LZO is GPL incompatible similar to code under the 4 clause BSD licence.

Quoted 4 lines

...
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */

Quoted 7 lines
Quoted 4 lines

I've had a reply from the copyright holder/author saying he's going to change this wording in the next LZO release and that the code *is* GPLv2 licensed as per the headers on the files.

It would be ideal if the author of that code could send us a
signed-off-by: as per secton 11 of Documentation/SubmittingPatches.

Section 11b says I can submit it but I've asked the author about a signed off by line (he's cc'd) for the alleviation of any doubt.

Cheers,

Richard

#11 lore raw
Quoted 20 lines · Richard Purdie
Quoted 19 lines · Andrew Morton
Quoted 17 lines · On Sat, 12 May 2007 16:17:35 +0100 Richard Purdie <[email protected]>…
Quoted 12 lines · Adrian Bunk
Quoted 4 lines · Richard Purdie

...
I've asked the LZO author about the comments on lzo_copyright function but the code is GPLv2 licensed so is suitable for inclusion in the kernel.

This sounds as if LZO is GPL incompatible similar to code under the 4 clause BSD licence.

Quoted 4 lines

...
+/* If you use the LZO library in a product, you *must* keep this
+ * copyright string in the executable of your product.
+ */

I've had a reply from the copyright holder/author saying he's going to change this wording in the next LZO release and that the code *is* GPLv2 licensed as per the headers on the files.

Quoted 5 lines
Quoted 2 lines

It would be ideal if the author of that code could send us a
signed-off-by: as per secton 11 of Documentation/SubmittingPatches.

Section 11b says I can submit it but I've asked the author about a signed off by line (he's cc'd) for the alleviation of any doubt.

I agree that the comment does conflict with the GPL. Just to avoid any doubts, LZO _is_ GPL v2, and I will fix that comment for the next version. Please accept my signed-off-by for Richard's kernel patch in the meantime.

Signed-off-by Markus F.X.J. Oberhumer <[email protected]>

~Markus

Quoted 6 lines

Cheers,

Richard

Signature · 1 line
Markus Oberhumer, <[email protected]>, http://www.oberhumer.com/