Markus F.X.J. Oberhumer (3):
lib/lzo: Rename lzo1x_decompress.c to lzo1x_decompress_safe.c lib/lzo: Update LZO compression to current upstream version lib/lzo: Optimize code for CPUs with inefficient unaligned access

 include/linux/lzo.h             |   15 +-
 lib/lzo/Makefile                |    2 +-
 lib/lzo/lzo1x_compress.c        |  309 +++++++++++++++++++++------------------
 lib/lzo/lzo1x_decompress.c      |  255 --------------------------------
 lib/lzo/lzo1x_decompress_safe.c |  237 ++++++++++++++++++++++++++++++
 lib/lzo/lzodefs.h               |   34 ++++-
 6 files changed, 441 insertions(+), 411 deletions(-)
 delete mode 100644 lib/lzo/lzo1x_decompress.c
 create mode 100644 lib/lzo/lzo1x_decompress_safe.c

Markus F.X.J. Oberhumer

author

2012-10-07 15:08 UTC #1 lore raw

PATCH 1/3 lib/lzo: Rename lzo1x_decompress.c to lzo1x_decompress_safe.c

Rename the source file to match the function name and thereby also make room for a possible future even slightly faster "non-safe" decompressor version.

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

---
 lib/lzo/Makefile                                   |    2 +-
 ...{lzo1x_decompress.c => lzo1x_decompress_safe.c} |    0
 2 files changed, 1 insertions(+), 1 deletions(-)
 rename lib/lzo/{lzo1x_decompress.c => lzo1x_decompress_safe.c} (100%)

lib/lzo/Makefile +1 -1

index e764116..f0f7d7c 100644
@@ -1,5 +1,5 @@
 lzo_compress-objs := lzo1x_compress.o
-lzo_decompress-objs := lzo1x_decompress.o
+lzo_decompress-objs := lzo1x_decompress_safe.o
 
 obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
 obj-$(CONFIG_LZO_DECOMPRESS) += lzo_decompress.o

lib/lzo/lzo1x_decompress_safe.c renamed from lib/lzo/lzo1x_decompress.c +0 -0

similarity index 100%
rename from lib/lzo/lzo1x_decompress.c
rename to lib/lzo/lzo1x_decompress_safe.c

Signature · 1 line

1.7.1

Markus F.X.J. Oberhumer

author

2012-10-07 15:09 UTC #2 lore raw

PATCH 2/3 lib/lzo: Update LZO compression to current upstream version

In reply to Markus F.X.J. Oberhumer

This commit updates the kernel LZO code to the current upsteam version which features a significant speed improvement - benchmarking the Calgary and Silesia test corpora typically shows a doubled performance in both compression and decompression on modern i386/x86_64/powerpc machines.

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

---
 include/linux/lzo.h             |   15 +-
 lib/lzo/lzo1x_compress.c        |  309 +++++++++++++++++++----------------
 lib/lzo/lzo1x_decompress_safe.c |  341 ++++++++++++++++++---------------------
 lib/lzo/lzodefs.h               |   34 +++-
 4 files changed, 360 insertions(+), 339 deletions(-)

include/linux/lzo.h +8 -7

index d793497..a0848d9 100644
@@ -4,28 +4,28 @@
  *  LZO Public Kernel Interface
  *  A mini subset of the LZO real-time data compression library
  *
- *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <[email protected]>
+ *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <[email protected]>
  *
  *  The full LZO package can be found at:
  *  http://www.oberhumer.com/opensource/lzo/
  *
- *  Changed for kernel use by:
+ *  Changed for Linux kernel use by:
  *  Nitin Gupta <[email protected]>
  *  Richard Purdie <[email protected]>
  */
 
-#define LZO1X_MEM_COMPRESS	(16384 * sizeof(unsigned char *))
-#define LZO1X_1_MEM_COMPRESS	LZO1X_MEM_COMPRESS
+#define LZO1X_1_MEM_COMPRESS	(8192 * sizeof(unsigned short))
+#define LZO1X_MEM_COMPRESS	LZO1X_1_MEM_COMPRESS
 
 #define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3)
 
-/* This requires 'workmem' of size LZO1X_1_MEM_COMPRESS */
+/* This requires 'wrkmem' of size LZO1X_1_MEM_COMPRESS */
 int lzo1x_1_compress(const unsigned char *src, size_t src_len,
-			unsigned char *dst, size_t *dst_len, void *wrkmem);
+		     unsigned char *dst, size_t *dst_len, void *wrkmem);
 
 /* safe decompression with overrun testing */
 int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
-			unsigned char *dst, size_t *dst_len);
+			  unsigned char *dst, size_t *dst_len);
 
 /*
  * Return values (< 0 = Error)

@@ -40,5 +40,6 @@ int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
 #define LZO_E_EOF_NOT_FOUND		(-7)
 #define LZO_E_INPUT_NOT_CONSUMED	(-8)
 #define LZO_E_NOT_YET_IMPLEMENTED	(-9)
+#define LZO_E_INVALID_ARGUMENT		(-10)
 
 #endif

lib/lzo/lzo1x_compress.c +168 ~~-141~~

382 lines not on this page · raw message

lib/lzo/lzo1x_decompress_safe.c +157 ~~-184~~

394 lines not on this page · raw message

lib/lzo/lzodefs.h +27 -7

index b6d482c..ddc8db5 100644
@@ -1,19 +1,37 @@
 /*
  *  lzodefs.h -- architecture, OS and compiler specific defines
  *
- *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <[email protected]>
+ *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <[email protected]>
  *
  *  The full LZO package can be found at:
  *  http://www.oberhumer.com/opensource/lzo/
  *
- *  Changed for kernel use by:
+ *  Changed for Linux kernel use by:
  *  Nitin Gupta <[email protected]>
  *  Richard Purdie <[email protected]>
  */
 
-#define LZO_VERSION		0x2020
-#define LZO_VERSION_STRING	"2.02"
-#define LZO_VERSION_DATE	"Oct 17 2005"
+
+#define COPY4(dst, src)	\
+		put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
+#if defined(__x86_64__)
+#define COPY8(dst, src)	\
+		put_unaligned(get_unaligned((const u64 *)(src)), (u64 *)(dst))
+#else
+#define COPY8(dst, src)	\
+		COPY4(dst, src); COPY4((dst) + 4, (src) + 4)
+#endif
+
+#if defined(__BIG_ENDIAN) && defined(__LITTLE_ENDIAN)
+#error "conflicting endian definitions"
+#elif defined(__x86_64__)
+#define LZO_USE_CTZ64	1
+#define LZO_USE_CTZ32	1
+#elif defined(__i386__) || defined(__powerpc__)
+#define LZO_USE_CTZ32	1
+#else
+#define LZO_USE_CTZ32	1
+#endif
 
 #define M1_MAX_OFFSET	0x0400
 #define M2_MAX_OFFSET	0x0800

@@ -34,8 +52,10 @@
 #define M3_MARKER	32
 #define M4_MARKER	16
 
-#define D_BITS		14
-#define D_MASK		((1u << D_BITS) - 1)
+#define lzo_dict_t      unsigned short
+#define D_BITS		13
+#define D_SIZE		(1u << D_BITS)
+#define D_MASK		(D_SIZE - 1)
 #define D_HIGH		((D_MASK >> 1) + 1)
 
 #define DX2(p, s1, s2)	(((((size_t)((p)[2]) << (s2)) ^ (p)[1]) \

Signature · 1 line

1.7.1

Markus F.X.J. Oberhumer

author

2012-10-07 15:09 UTC #3 lore raw

PATCH 3/3 lib/lzo: Optimize code for CPUs with inefficient unaligned access

In reply to Markus F.X.J. Oberhumer

Some code paths are only benefical on machines with fast unaligned loads, so only use these if CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS defined.

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

---
 lib/lzo/lzo1x_compress.c        |    4 ++--
 lib/lzo/lzo1x_decompress_safe.c |   15 ++++++++++++---
 lib/lzo/lzodefs.h               |    2 +-
 3 files changed, 15 insertions(+), 6 deletions(-)

lib/lzo/lzo1x_compress.c +2 -2

index d42efe5..1593dba 100644
@@ -90,7 +90,7 @@ next:
 
 		m_len = 4;
 		{
-#if defined(LZO_USE_CTZ64)
+#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ64)
 		u64 v;
 		v = get_unaligned((const u64 *) (ip + m_len)) ^
 		    get_unaligned((const u64 *) (m_pos + m_len));

@@ -110,7 +110,7 @@ next:
 #  else
 #    error "missing endian definition"
 #  endif
-#elif defined(LZO_USE_CTZ32)
+#elif defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ32)
 		u32 v;
 		v = get_unaligned((const u32 *) (ip + m_len)) ^
 		    get_unaligned((const u32 *) (m_pos + m_len));

lib/lzo/lzo1x_decompress_safe.c +12 -3

index 0dba30c..569985d 100644
@@ -64,6 +64,7 @@ int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
 				}
 				t += 3;
 copy_literal_run:
+#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
 				if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
 					const unsigned char *ie = ip + t;
 					unsigned char *oe = op + t;

@@ -77,7 +78,9 @@ copy_literal_run:
 					} while (ip < ie);
 					ip = ie;
 					op = oe;
-				} else {
+				} else
+#endif
+				{
 					NEED_OP(t);
 					NEED_IP(t + 3);
 					do {

@@ -148,6 +151,7 @@ copy_literal_run:
 			m_pos -= 0x4000;
 		}
 		TEST_LB(m_pos);
+#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
 		if (op - m_pos >= 8) {
 			unsigned char *oe = op + t;
 			if (likely(HAVE_OP(t + 15))) {

@@ -173,7 +177,9 @@ copy_literal_run:
 					*op++ = *m_pos++;
 				} while (op < oe);
 			}
-		} else {
+		} else
+#endif
+		{
 			unsigned char *oe = op + t;
 			NEED_OP(t);
 			op[0] = m_pos[0];

@@ -187,11 +193,14 @@ copy_literal_run:
 match_next:
 		state = next;
 		t = next;
+#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
 		if (likely(HAVE_IP(6) && HAVE_OP(4))) {
 			COPY4(op, ip);
 			op += t;
 			ip += t;
-		} else {
+		} else
+#endif
+		{
 			NEED_IP(t + 3);
 			NEED_OP(t);
 			while (t > 0) {

lib/lzo/lzodefs.h +1 -1

index ddc8db5..5a4beb2 100644
@@ -29,7 +29,7 @@
 #define LZO_USE_CTZ32	1
 #elif defined(__i386__) || defined(__powerpc__)
 #define LZO_USE_CTZ32	1
-#else
+#elif defined(__arm__) && (__LINUX_ARM_ARCH__ >= 5)
 #define LZO_USE_CTZ32	1
 #endif

Signature · 1 line

1.7.1

Andrew Morton

maintainer

2012-10-09 19:26 UTC #4 lore raw

In reply to Markus F.X.J. Oberhumer

Quoted 8 lines · On Sun, 7 Oct 2012 17:07:55 +0200 "Markus F.X.J. Oberhumer"…

As requested by akpm I am sending my "lzo-update" branch at
git://github.com/markus-oberhumer/linux.git lzo-update
to lkml as a patch series created by "git format-patch -M v3.5..lzo-update".
You can also browse the branch at

Quoted 7 lines

https://github.com/markus-oberhumer/linux/compare/lzo-update
and review the three patches at
https://github.com/markus-oberhumer/linux/commit/7c979cebc0f93dc692b734c12665a6824d219c20
https://github.com/markus-oberhumer/linux/commit/10f6781c8591fe5fe4c8c733131915e5ae057826
https://github.com/markus-oberhumer/linux/commit/5f702781f158cb59075cfa97e5c21f52275057f1

The changes look OK to me. Please ask Stephen to include the tree in linux-next, for a 3.7 merge.

The changelog for patch 2/3 says:

: This commit updates the kernel LZO code to the current upsteam version : which features a significant speed improvement - benchmarking the Calgary : and Silesia test corpora typically shows a doubled performance in : both compression and decompression on modern i386/x86_64/powerpc machines.

There are significant clients of the LZO library - crypto, btrfs, jffs2, ubifs, squashfs and zcache. So let's give all those people a cc and ask that they test the LZO changes once they land in linux-next. For correctness and performance, please.

Markus F.X.J. Oberhumer

author

2012-10-09 19:54 UTC #5 lore raw

Hi Stephen,

Quoted 13 lines · Andrew Morton

Quoted 10 lines · On Sun, 7 Oct 2012 17:07:55 +0200 "Markus F.X.J. Oberhumer"…
As requested by akpm I am sending my "lzo-update" branch at
git://github.com/markus-oberhumer/linux.git lzo-update
to lkml as a patch series created by "git format-patch -M v3.5..lzo-update".
You can also browse the branch at
https://github.com/markus-oberhumer/linux/compare/lzo-update

Quoted 8 lines

Quoted 5 lines
and review the three patches at
https://github.com/markus-oberhumer/linux/commit/7c979cebc0f93dc692b734c12665a6824d219c20
https://github.com/markus-oberhumer/linux/commit/10f6781c8591fe5fe4c8c733131915e5ae057826
https://github.com/markus-oberhumer/linux/commit/5f702781f158cb59075cfa97e5c21f52275057f1
The changes look OK to me. Please ask Stephen to include the tree in linux-next, for a 3.7 merge.

I'd ask you to include my "lzo-update" branch in linux-next:

git://github.com/markus-oberhumer/linux.git lzo-update

Quoted 11 lines

The changelog for patch 2/3 says:
: This commit updates the kernel LZO code to the current upsteam version : which features a significant speed improvement - benchmarking the Calgary : and Silesia test corpora typically shows a doubled performance in : both compression and decompression on modern i386/x86_64/powerpc machines.
There are significant clients of the LZO library - crypto, btrfs, jffs2, ubifs, squashfs and zcache. So let's give all those people a cc and ask that they test the LZO changes once they land in linux-next. For correctness and performance, please.

The core compression and decompression code has been thoroughly tested, so I do not expect major problems.

Good testing after the merge and feedback about build or performance issues (and improvements!) is highly appreciated.

Many thanks,
Markus

Signature · 1 line

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

Stephen Rothwell

2012-10-09 22:43 UTC #6 lore raw

Hi Markus,

Quoted 21 lines · On Tue, 09 Oct 2012 21:54:59 +0200 "Markus F.X.J. Oberhumer"…

Quoted 19 lines · Andrew Morton
Quoted 15 lines · On Sun, 7 Oct 2012 17:07:55 +0200 "Markus F.X.J. Oberhumer"…
As requested by akpm I am sending my "lzo-update" branch at
git://github.com/markus-oberhumer/linux.git lzo-update
to lkml as a patch series created by "git format-patch -M v3.5..lzo-update".
You can also browse the branch at
https://github.com/markus-oberhumer/linux/compare/lzo-update
and review the three patches at
https://github.com/markus-oberhumer/linux/commit/7c979cebc0f93dc692b734c12665a6824d219c20
https://github.com/markus-oberhumer/linux/commit/10f6781c8591fe5fe4c8c733131915e5ae057826
https://github.com/markus-oberhumer/linux/commit/5f702781f158cb59075cfa97e5c21f52275057f1

Quoted 6 lines

Quoted 2 lines
The changes look OK to me. Please ask Stephen to include the tree in linux-next, for a 3.7 merge.
I'd ask you to include my "lzo-update" branch in linux-next:
git://github.com/markus-oberhumer/linux.git lzo-update

I have added this from today.

Thanks for adding your subsystem tree as a participant of linux-next. As you may know, this is not a judgment of your code. The purpose of linux-next is for integration testing and to lower the impact of conflicts between subsystems in the next merge window.

You will need to ensure that the patches/commits in your tree/series have been:
* submitted under GPL v2 (or later) and include the Contributor's Signed-off-by,
* posted to the relevant mailing list,
* reviewed by you (or another maintainer of your subsystem tree),
* successfully unit tested, and
* destined for the current or next Linux merge window.

Basically, this should be just what you would send to Linus (or ask him to fetch). It is allowed to be rebased if you deem it necessary.

Signature · 15 lines

Cheers,
Stephen Rothwell 
[email protected]

Legal Stuff:
By participating in linux-next, your subsystem tree contributions are
public and will be included in the linux-next trees.  You may be sent
e-mail messages indicating errors or other issues when the
patches/commits from your subsystem tree are merged and tested in
linux-next.  These messages may also be cross-posted to the linux-next
mailing list, the linux-kernel mailing list, etc.  The linux-next tree
project and IBM (my employer) make no warranties regarding the linux-next
project, the testing procedures, the results, the e-mails, etc.  If you
don't agree to these ground rules, let me know and I'll remove your tree
from participation in linux-next.

Arnd Bergmann

2012-10-11 11:41 UTC #7 lore raw

In reply to Markus F.X.J. Oberhumer

Quoted 11 lines · Markus F.X.J. Oberhumer

Quoted 10 lines
: This commit updates the kernel LZO code to the current upsteam version : which features a significant speed improvement - benchmarking the Calgary : and Silesia test corpora typically shows a doubled performance in : both compression and decompression on modern i386/x86_64/powerpc machines.
There are significant clients of the LZO library - crypto, btrfs, jffs2, ubifs, squashfs and zcache. So let's give all those people a cc and ask that they test the LZO changes once they land in linux-next. For correctness and performance, please.

Quoted 5 lines

The core compression and decompression code has been thoroughly tested, so I do not expect major problems.
Good testing after the merge and feedback about build or performance issues (and improvements!) is highly appreciated.

The addition of the lzo tree to linux-next caused this problem for ARM imx_v6_v7_defconfig:

In file included from /home/arnd/linux-arm/arch/arm/boot/compressed/decompress.c:40:0:
/home/arnd/linux-arm/arch/arm/boot/compressed/../../../../lib/decompress_unlzo.c:34:34: fatal error: lzo/lzo1x_decompress.c: No such file or directory

Since the file was renamed, anything including it needs to be updated to the new file name.

Signed-off-by Arnd Bergmann <[email protected]>

lib/decompress_unlzo.c +1 -1

index 4531294..960183d 100644
@@ -31,7 +31,7 @@
  */
 
 #ifdef STATIC
-#include "lzo/lzo1x_decompress.c"
+#include "lzo/lzo1x_decompress_safe.c"
 #else
 #include <linux/decompress/unlzo.h>
 #endif

Markus F.X.J. Oberhumer

author

2012-10-11 16:29 UTC #8 lore raw

Thanks Arnd,

Quoted 18 lines · Arnd Bergmann

Quoted 11 lines · Markus F.X.J. Oberhumer
Quoted 10 lines
: This commit updates the kernel LZO code to the current upsteam version : which features a significant speed improvement - benchmarking the Calgary : and Silesia test corpora typically shows a doubled performance in : both compression and decompression on modern i386/x86_64/powerpc machines.
There are significant clients of the LZO library - crypto, btrfs, jffs2, ubifs, squashfs and zcache. So let's give all those people a cc and ask that they test the LZO changes once they land in linux-next. For correctness and performance, please.
Quoted 5 lines
The core compression and decompression code has been thoroughly tested, so I do not expect major problems.
Good testing after the merge and feedback about build or performance issues (and improvements!) is highly appreciated.

Quoted 8 lines

The addition of the lzo tree to linux-next caused this problem for ARM imx_v6_v7_defconfig:
In file included from /home/arnd/linux-arm/arch/arm/boot/compressed/decompress.c:40:0:
/home/arnd/linux-arm/arch/arm/boot/compressed/../../../../lib/decompress_unlzo.c:34:34: fatal error: lzo/lzo1x_decompress.c: No such file or directory
Since the file was renamed, anything including it needs to be updated to the new file name.

I will add that patch to my tree.

Cheers,
Markus

Quoted 16 lines

Signed-off-by Arnd Bergmann <[email protected]>

lib/decompress_unlzo.c +1 -1

index 4531294..960183d 100644
@@ -31,7 +31,7 @@
  */
 
 #ifdef STATIC
-#include "lzo/lzo1x_decompress.c"
+#include "lzo/lzo1x_decompress_safe.c"
 #else
 #include <linux/decompress/unlzo.h>
 #endif

Signature · 1 line

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

Dan Magenheimer

2012-12-21 02:04 UTC #9 lore raw

Quoted 31 lines

From: Markus F.X.J. Oberhumer [mailto:[email protected]]
Subject: Re: [PATCH 0/3] Update LZO compression
Thanks Arnd,
Quoted 15 lines · Arnd Bergmann
Quoted 14 lines · Markus F.X.J. Oberhumer
Quoted 10 lines
: This commit updates the kernel LZO code to the current upsteam version : which features a significant speed improvement - benchmarking the Calgary : and Silesia test corpora typically shows a doubled performance in : both compression and decompression on modern i386/x86_64/powerpc machines.
There are significant clients of the LZO library - crypto, btrfs, jffs2, ubifs, squashfs and zcache. So let's give all those people a cc and ask that they test the LZO changes once they land in linux-next. For correctness and performance, please.
The core compression and decompression code has been thoroughly tested, so I do not expect major problems.
Quoted 8 lines
Quoted 2 lines
Good testing after the merge and feedback about build or performance issues (and improvements!) is highly appreciated.
The addition of the lzo tree to linux-next caused this problem for ARM imx_v6_v7_defconfig:
In file included from /home/arnd/linux-arm/arch/arm/boot/compressed/decompress.c:40:0:
/home/arnd/linux-arm/arch/arm/boot/compressed/../../../../lib/decompress_unlzo.c:34:34: fatal error:
lzo/lzo1x_decompress.c: No such file or directory
Quoted 1 line

Quoted 7 lines

Quoted 2 lines
Since the file was renamed, anything including it needs to be updated to the new file name.
I will add that patch to my tree.
Cheers,
Markus

Sorry if I missed it (bad connectivity this week), but is someone going to send a pull request to get this LZO update from linux-next into Linus's tree? The window is closing soon isn't it?

Dan