Hi,
This contains LZO1X-1 compressor and LZO1X decompressor (safe and
standard version).
This includes changes suggested by various people - Thanks to all who
reviewed previous patches for this LZO port.
Changelog vs original LZO 2.02 code:
- Chopped down huge parts of original code that were irrelevant fot this port
- Use of standard data types
- Use memcpy() instead of COPY4 macros used in orig. code
- Various macros -> static inline functions
- Code matches general kernel style
- Various other cleanups suggested in reviews
For now, tested on x86 only.
Signed-off-by: Nitin Gupta <[email protected]>
---
diff --git a/Makefile b/Makefile
index 34210af..88053ba 100644
--- a/Makefile
+++ b/Makefile
@@ -826,11 +826,18 @@ include/config/kernel.release:
include/config/auto.conf FORCE
# Listed in dependency order
PHONY += prepare archprepare prepare0 prepare1 prepare2 prepare3
+# prepare4 does module specific things prior to compilation
+prepare4:
+ifneq ($(CONFIG_LZO1X),n)
+ $(Q)ln -sf $(srctree)/lib/lzo1x/lzo1x_decompress.c \
+ $(srctree)/lib/lzo1x/lzo1x_decompress_safe.c
+endif
+
# prepare3 is used to check if we are building in a separate output directory,
# and if so do:
# 1) Check that make has not been executed in the kernel src $(srctree)
# 2) Create the include2 directory, used for the second asm symlink
-prepare3: include/config/kernel.release
+prepare3: prepare4 include/config/kernel.release
ifneq ($(KBUILD_SRC),)
@echo ' Using $(srctree) as source for kernel'
$(Q)if [ -f $(srctree)/.config -o -d $(srctree)/include/config ]; then \
diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
new file mode 100755
index 0000000..7c2f633
--- /dev/null
+++ b/include/linux/lzo1x.h
@@ -0,0 +1,80 @@
+/* lzo1x.h -- public interface of the LZO1X compression algorithm
+
+ This file is part of the LZO real-time data compression library.
+
+ Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+ All Rights Reserved.
+
+ The LZO library 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.
+
+ The LZO library 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 the LZO library; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+
+
+ This file is modified version of lzo1x.h found in original LZO 2.02
+ code. Some additional changes have also been made to make it work
+ in kernel space.
+
+ Nitin Gupta
+ <[email protected]>
+ */
+
+#ifndef __LZO1X_H
+#define __LZO1X_H
+
+/* LZO return codes */
+#define LZO_E_OK 0
+#define LZO_E_ERROR (-1)
+#define LZO_E_OUT_OF_MEMORY (-2) /* [not used right now] */
+#define LZO_E_NOT_COMPRESSIBLE (-3) /* [not used right now] */
+#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) /* [not used right now] */
+
+/* Size of temp buffer (workmem) required by lzo1x_compress */
+#define LZO1X_WORKMEM_SIZE ((size_t) (16384L * sizeof(unsigned char *)))
+
+/*
+ * This required 'workmem' of size LZO1X_WORKMEM_SIZE
+ */
+int lzo1x_compress(const unsigned char *src, size_t src_len,
+ unsigned char *dst, size_t *dst_len,
+ void *workmem);
+
+
+/*
+ * This decompressor expects valid compressed data.
+ *
+ * If the compressed data gets corrupted somehow (e.g. transmission
+ * via an erroneous channel, disk errors, ...) it will probably crash
+ * your application because absolutely no additional checks are done.
+ */
+int lzo1x_decompress(const unsigned char *src, size_t src_len,
+ unsigned char *dst, size_t *dst_len);
+
+
+/*
+ * The `safe' decompressor. Somewhat slower.
+ *
+ * This decompressor will catch all compressed data violations and
+ * return an error code in this case.
+ */
+int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
+ unsigned char *dst, size_t *dst_len);
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b..9d30b1f 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -64,6 +64,12 @@ config ZLIB_INFLATE
config ZLIB_DEFLATE
tristate
+config LZO1X
+ tristate "LZO1X Compression/Decompression"
+ help
+ Compression: LZO1X-1
+ Decompression: LZO1X
+
#
# Generic allocator support is selected if needed
#
diff --git a/lib/Makefile b/lib/Makefile
index c8c8e20..4dad99d 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -49,6 +49,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_LZO1X) += lzo1x/
obj-$(CONFIG_TEXTSEARCH) += textsearch.o
obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
new file mode 100644
index 0000000..e036b42
--- /dev/null
+++ b/lib/lzo1x/Makefile
@@ -0,0 +1,11 @@
+#
+# When compiling this module out of tree, do 'make prepare_lzo'
+# before compiling as usual
+#
+obj-$(CONFIG_LZO1X) += lzo1x.o
+CFLAGS_lzo1x_decompress_safe.o += -DLZO1X_DECOMPRESS_SAFE
+lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o lzo1x_decompress_safe.o
+
+prepare_lzo:
+ @ln -sf lzo1x_decompress.c lzo1x_decompress_safe.c
+
diff --git a/lib/lzo1x/lzo1x_compress.c b/lib/lzo1x/lzo1x_compress.c
new file mode 100755
index 0000000..690c082
--- /dev/null
+++ b/lib/lzo1x/lzo1x_compress.c
@@ -0,0 +1,256 @@
+/* lzo1x_compress.c -- LZO1X-1 compression
+
+ This file is part of the LZO real-time data compression library.
+
+ Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+ All Rights Reserved.
+
+ The LZO library 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.
+
+ The LZO library 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 the LZO library; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+
+
+ This file is derived from lzo1x_1.c and lzo1x_c.ch found in original
+ LZO 2.02 code. Some additional changes have also been made to make
+ it work in kernel space.
+
+ Nitin Gupta
+ <[email protected]>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <linux/compiler.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Compression");
+
+/* compress a block of data. */
+static unsigned int
+lzo1x_compress_worker(const unsigned char *in, size_t in_len,
+ unsigned char *out, size_t *out_len,
+ void *workmem)
+{
+ const unsigned char *ip;
+ unsigned char *op;
+ const unsigned char * const in_end = in + in_len;
+ const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
+ const unsigned char *ii;
+ const unsigned char ** const dict = (const unsigned char **)workmem;
+
+ op = out;
+ ip = in;
+ ii = ip;
+
+ ip += 4;
+ for (;;) {
+ const unsigned char *m_pos;
+ size_t m_off;
+ size_t m_len;
+ size_t dindex;
+
+ dindex = DINDEX1(ip);
+ m_pos = dict[dindex];
+
+ if ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
+ || m_off > M4_MAX_OFFSET)
+ goto literal;
+
+ if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
+ goto try_match;
+
+ dindex = DINDEX2(dindex);
+ m_pos = dict[dindex];
+
+ if ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
+ || m_off > M4_MAX_OFFSET)
+ goto literal;
+
+ if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
+ goto try_match;
+
+ goto literal;
+
+try_match:
+ if (*(const unsigned short *)m_pos ==
+ *(const unsigned short *)ip) {
+ if (likely(m_pos[2] == ip[2]))
+ goto match;
+ }
+
+ /* a literal */
+literal:
+ dict[dindex] = ip;
+ ++ip;
+ if (unlikely(ip >= ip_end))
+ break;
+ continue;
+
+ /* a match */
+match:
+ dict[dindex] = ip;
+ /* store current literal run */
+ if ((size_t)(ip - ii) > 0) {
+ size_t t = (size_t)(ip - ii);
+ if (t <= 3)
+ op[-2] |= (unsigned char)(t);
+ else if (t <= 18)
+ *op++ = (unsigned char)(t - 3);
+ else {
+ size_t tt = t - 18;
+ *op++ = 0;
+ while (tt > 255) {
+ tt -= 255;
+ *op++ = 0;
+ }
+ *op++ = (unsigned char)tt;
+ }
+ do *op++ = *ii++; while (--t > 0);
+ }
+
+ /* code the match */
+ ip += 3;
+ if (m_pos[3] != *ip++ || m_pos[4] != *ip++ ||
+ m_pos[5] != *ip++ || m_pos[6] != *ip++ ||
+ m_pos[7] != *ip++ || m_pos[8] != *ip++) {
+ --ip;
+ m_len = (size_t)(ip - ii);
+
+ if (m_off <= M2_MAX_OFFSET) {
+ m_off -= 1;
+ *op++ = (unsigned char)(((m_len - 1) << 5) |
+ ((m_off & 7) << 2));
+ *op++ = (unsigned char)(m_off >> 3);
+ }
+ else if (m_off <= M3_MAX_OFFSET) {
+ m_off -= 1;
+ *op++ = (unsigned char)(M3_MARKER |
+ (m_len - 2));
+ goto m3_m4_offset;
+ } else {
+ m_off -= 0x4000;
+ *op++ = (unsigned char)(M4_MARKER |
+ ((m_off & 0x4000) >> 11) |
+ (m_len - 2));
+ goto m3_m4_offset;
+ }
+ } else {
+ const unsigned char *end = in_end;
+ const unsigned char *m = m_pos + M2_MAX_LEN + 1;
+ while (ip < end && *m == *ip)
+ m++, ip++;
+ m_len = (size_t)(ip - ii);
+
+ if (m_off <= M3_MAX_OFFSET) {
+ m_off -= 1;
+ if (m_len <= 33)
+ *op++ = (unsigned char)(M3_MARKER |
+ (m_len - 2));
+ else {
+ m_len -= 33;
+ *op++ = M3_MARKER | 0;
+ goto m3_m4_len;
+ }
+ } else {
+ m_off -= 0x4000;
+ if (m_len <= M4_MAX_LEN)
+ *op++ = (unsigned char)(M4_MARKER |
+ ((m_off & 0x4000) >> 11) |
+ (m_len - 2));
+ else {
+ m_len -= M4_MAX_LEN;
+ *op++ = (unsigned char)(M4_MARKER |
+ ((m_off & 0x4000) >> 11));
+m3_m4_len:
+ while (m_len > 255) {
+ m_len -= 255;
+ *op++ = 0;
+ }
+ *op++ = (unsigned char)(m_len);
+ }
+ }
+
+m3_m4_offset:
+ *op++ = (unsigned char)((m_off & 63) << 2);
+ *op++ = (unsigned char)(m_off >> 6);
+ }
+
+ ii = ip;
+ if (unlikely(ip >= ip_end))
+ break;
+ }
+
+ *out_len = (size_t)(op - out);
+ return (size_t)(in_end - ii);
+}
+
+
+/*
+ * This requires buffer (workmem) of size LZO1X_WORKMEM_SIZE
+ * (exported by lzo1x.h).
+ */
+int
+lzo1x_compress(const unsigned char *in, size_t in_len,
+ unsigned char *out, size_t *out_len,
+ void *workmem)
+{
+ unsigned char *op = out;
+ size_t t;
+
+ if (!workmem)
+ return -EINVAL;
+
+ if (unlikely(in_len <= M2_MAX_LEN + 5))
+ t = in_len;
+ else {
+ t = lzo1x_compress_worker(in, in_len, op, out_len, workmem);
+ op += *out_len;
+ }
+
+ if (t > 0) {
+ const unsigned char *ii = in + in_len - t;
+
+ if (op == out && t <= 238)
+ *op++ = (unsigned char)(17 + t);
+ else if (t <= 3)
+ op[-2] |= (unsigned char)(t);
+ else if (t <= 18)
+ *op++ = (unsigned char)(t - 3);
+ else {
+ size_t tt = t - 18;
+ *op++ = 0;
+ while (tt > 255) {
+ tt -= 255;
+ *op++ = 0;
+ }
+ *op++ = (unsigned char)tt;
+ }
+ memcpy(op, ii, t);
+ op += t;
+ ii += t;
+ }
+ *op++ = M4_MARKER | 1;
+ *op++ = 0;
+ *op++ = 0;
+
+ *out_len = (size_t)(op - out);
+ return 0;
+}
+
+EXPORT_SYMBOL(lzo1x_compress);
diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
new file mode 100755
index 0000000..09fa1ca
--- /dev/null
+++ b/lib/lzo1x/lzo1x_decompress.c
@@ -0,0 +1,224 @@
+/* lzo1x_decompress.c -- LZO1X decompression
+
+ This file is part of the LZO real-time data compression library.
+
+ Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+ All Rights Reserved.
+
+ The LZO library 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.
+
+ The LZO library 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 the LZO library; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+
+
+ This file is derived from lzo1x_d1.c and lzo1x_d.ch found in original
+ LZO 2.02 code. Some additional changes have also been made to make
+ it work in kernel space.
+
+ Nitin Gupta
+ <[email protected]>
+ */
+
+#include <linux/kernel.h>
+#include <linux/module.h>
+#include <asm/byteorder.h>
+#include <linux/lzo1x.h>
+
+#include "lzo1x_int.h"
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("LZO1X Decompression");
+
+int
+lzo1x_decompress(const unsigned char *in, size_t in_len,
+ unsigned char *out, size_t *out_len)
+{
+ size_t t;
+ unsigned char *op = out;
+ const unsigned char *ip = in, *m_pos;
+ const unsigned char * const ip_end = in + in_len;
+#if defined(HAVE_ANY_OP)
+ unsigned char * const op_end = out + *out_len;
+#endif
+ *out_len = 0;
+
+ if (*ip > 17) {
+ t = *ip++ - 17;
+ if (t < 4)
+ goto match_next;
+ NEED_OP(t);
+ NEED_IP(t + 1);
+ memcpy(op, ip, t);
+ op += t;
+ ip += t;
+ goto first_literal_run;
+ }
+
+ while (TEST_IP) {
+ t = *ip++;
+ if (t >= 16)
+ goto match;
+ /* a literal run */
+ if (t == 0) {
+ NEED_IP(1);
+ while (*ip == 0) {
+ t += 255;
+ ip++;
+ NEED_IP(1);
+ }
+ t += 15 + *ip++;
+ }
+ /* copy literals */
+ NEED_OP(t + 3);
+ NEED_IP(t + 4);
+ memcpy(op, ip, t + 3);
+ op += t + 3;
+ ip += t + 3;
+
+first_literal_run:
+ t = *ip++;
+ if (t >= 16)
+ goto match;
+ m_pos = op - (1 + M2_MAX_OFFSET);
+ m_pos -= t >> 2;
+ m_pos -= *ip++ << 2;
+ TEST_LB(m_pos);
+ NEED_OP(3);
+ *op++ = *m_pos++;
+ *op++ = *m_pos++;
+ *op++ = *m_pos;
+ goto match_done;
+
+ /* handle matches */
+ do {
+match:
+ if (t >= 64) { /* a M2 match */
+ m_pos = op - 1;
+ m_pos -= (t >> 2) & 7;
+ m_pos -= *ip++ << 3;
+ t = (t >> 5) - 1;
+ TEST_LB(m_pos);
+ NEED_OP(t + 3 - 1);
+ goto copy_match;
+ } else if (t >= 32) { /* a M3 match */
+ t &= 31;
+ if (t == 0) {
+ NEED_IP(1);
+ while (*ip == 0) {
+ t += 255;
+ ip++;
+ NEED_IP(1);
+ }
+ t += 31 + *ip++;
+ }
+ m_pos = op - 1 - (cpu_to_le16(
+ *(const unsigned short *)ip) >> 2);
+ ip += 2;
+ } else if (t >= 16) { /* a M4 match */
+ m_pos = op;
+ m_pos -= (t & 8) << 11;
+ t &= 7;
+ if (t == 0) {
+ NEED_IP(1);
+ while (*ip == 0) {
+ t += 255;
+ ip++;
+ NEED_IP(1);
+ }
+ t += 7 + *ip++;
+ }
+ m_pos -= cpu_to_le16(
+ *(const unsigned short *)ip) >> 2;
+ ip += 2;
+ if (m_pos == op)
+ goto eof_found;
+ m_pos -= 0x4000;
+ } else { /* a M1 match */
+ m_pos = op - 1;
+ m_pos -= t >> 2;
+ m_pos -= *ip++ << 2;
+ TEST_LB(m_pos);
+ NEED_OP(2);
+ *op++ = *m_pos++;
+ *op++ = *m_pos;
+ goto match_done;
+ }
+
+ /* copy match */
+ TEST_LB(m_pos);
+ NEED_OP(t + 3 - 1);
+
+copy_match:
+ if (op - m_pos >= BITS_PER_LONG / BITS_PER_BYTE) {
+ memcpy(op, m_pos, t + 2);
+ op += t + 2;
+ m_pos += t + 2;
+ } else {
+ *op = *m_pos;
+ *++op = *++m_pos;
+ do
+ *++op = *++m_pos;
+ while (--t > 0);
+ op++;
+ m_pos++;
+ }
+
+match_done:
+ t = ip[-2] & 3;
+ if (t == 0)
+ break;
+
+ /* copy literals */
+match_next:
+ NEED_OP(t);
+ NEED_IP(t+1);
+ *op++ = *ip++;
+ if (t > 1) {
+ *op++ = *ip++;
+ if (t > 2)
+ *op++ = *ip++;
+ }
+ t = *ip++;
+ } while (TEST_IP);
+ }
+
+#if defined(HAVE_TEST_IP)
+ /* no EOF code was found */
+ *out_len = (size_t)(op - out);
+ return LZO_E_EOF_NOT_FOUND;
+#endif
+
+eof_found:
+ *out_len = (size_t)(op - out);
+ return (ip == ip_end ? LZO_E_OK :
+ (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
+
+#if defined(LZO1X_DECOMPRESS_SAFE)
+input_overrun:
+ *out_len = (size_t)(op - out);
+ return LZO_E_INPUT_OVERRUN;
+
+output_overrun:
+ *out_len = (size_t)(op - out);
+ return LZO_E_OUTPUT_OVERRUN;
+
+lookbehind_overrun:
+ *out_len = (size_t)(op - out);
+ return LZO_E_LOOKBEHIND_OVERRUN;
+#endif
+}
+
+EXPORT_SYMBOL(lzo1x_decompress);
diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
new file mode 100755
index 0000000..69e6d9b
--- /dev/null
+++ b/lib/lzo1x/lzo1x_int.h
@@ -0,0 +1,122 @@
+/* lzo1x_int.h -- to be used internally by LZO de/compression algorithms
+
+ This file is part of the LZO real-time data compression library.
+
+ Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
+ All Rights Reserved.
+
+ The LZO library 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.
+
+ The LZO library 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 the LZO library; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+ Markus F.X.J. Oberhumer
+ <[email protected]>
+ http://www.oberhumer.com/opensource/lzo/
+
+
+ This file was derived from several header files found in original
+ LZO 2.02 code. Some additional changes have also been made to make
+ it work in kernel space.
+
+ Nitin Gupta
+ <[email protected]>
+ */
+
+#ifndef __LZO1X_INT_H
+#define __LZO1X_INT_H
+
+#include <linux/types.h>
+
+#define D_BITS 14
+#define D_SIZE (1u << D_BITS)
+#define D_MASK (D_SIZE - 1)
+#define D_HIGH ((D_MASK >> 1) + 1)
+
+static inline size_t DX2(const unsigned char *p, size_t s1, size_t s2)
+{
+ return (((((size_t)(p[2]) << s2) ^ p[1]) << s1) ^ p[0]);
+}
+
+static inline size_t DX3(const unsigned char *p, size_t s1, size_t
s2, size_t s3)
+{
+ return (DX2(p + 1, s2, s3) << s1) ^ p[0];
+}
+
+static inline size_t DINDEX1(const unsigned char *p)
+{
+ return ((size_t)(0x21 * DX3(p, 5, 5, 6)) >> 5) & D_MASK;
+}
+
+static inline size_t DINDEX2(size_t d)
+{
+ return (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
+}
+
+/* LZO1X Specific constants */
+#define M1_MAX_OFFSET 0x0400
+#define M2_MAX_OFFSET 0x0800
+#define M3_MAX_OFFSET 0x4000
+#define M4_MAX_OFFSET 0xbfff
+
+#define M1_MIN_LEN 2
+#define M1_MAX_LEN 2
+#define M2_MIN_LEN 3
+#define M2_MAX_LEN 8
+#define M3_MIN_LEN 3
+#define M3_MAX_LEN 33
+#define M4_MIN_LEN 3
+#define M4_MAX_LEN 9
+
+#define M1_MARKER 0
+#define M2_MARKER 64
+#define M3_MARKER 32
+#define M4_MARKER 16
+
+/* LZO return codes */
+#define LZO_E_OK 0
+#define LZO_E_ERROR (-1)
+#define LZO_E_OUT_OF_MEMORY (-2) /* [not used right now] */
+#define LZO_E_NOT_COMPRESSIBLE (-3) /* [not used right now] */
+#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) /* [not used right now] */
+
+/* Macros for 'safe' decompression */
+#ifdef LZO1X_DECOMPRESS_SAFE
+
+#define lzo1x_decompress lzo1x_decompress_safe
+#define TEST_IP (ip < ip_end)
+#define NEED_IP(x) \
+ if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
+#define NEED_OP(x) \
+ if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
+#define TEST_LB(m_pos) \
+ if (m_pos < out || m_pos >= op) goto lookbehind_overrun
+#define HAVE_TEST_IP
+#define HAVE_ANY_OP
+
+#else /* !LZO1X_DECOMPRESS_SAFE */
+
+#define TEST_IP 1
+#define TEST_LB(x) ((void) 0)
+#define NEED_IP(x) ((void) 0)
+#define NEED_OP(x) ((void) 0)
+#undef HAVE_TEST_IP
+#undef HAVE_ANY_OP
+
+#endif /* LZO1X_DECOMPRESS_SAFE */
+
+#endif
On 23 May 2007, at 09:27, Nitin Gupta wrote:
> This contains LZO1X-1 compressor and LZO1X decompressor (safe and
> standard version).
I understand that the 'safe' decompression code is 'somewhat slower'
and that decompressor performance is a key feature of this algorithm.
However, I am concerned about the safety implications of including
the 'unsafe' standard version in-kernel when likely uses include
compression of network data, memory objects and so-on, all of which
could in theory be maliciously modified.
I'm no kernel or programming expert, so I may be off the mark with
this one. To me, at least, even if the answer is 'no, there isn't a
problem' that's still a valuable clarification :)
Thanks,
Michael-Luke Jones
[please cc me on replies as I am not subscribed to lkml]
Hi Michael,
On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
> On 23 May 2007, at 09:27, Nitin Gupta wrote:
>
> > This contains LZO1X-1 compressor and LZO1X decompressor (safe and
> > standard version).
>
> I understand that the 'safe' decompression code is 'somewhat slower'
> and that decompressor performance is a key feature of this algorithm.
> However, I am concerned about the safety implications of including
> the 'unsafe' standard version in-kernel when likely uses include
> compression of network data, memory objects and so-on, all of which
> could in theory be maliciously modified.
>
The 'unsafe' version is still included since in some scenarios we have
guarantee that compressed data has not been modified (for e.g. where
we keep compressed data in memory only). So, in those cases there is
no need to go for slower 'safe' version. So, the version of
decompressor selected should be left to the user (kernel dev) only -
he should make sure that he is using the right version.
Cheers,
Nitin
On 23 May 2007, at 12:39, Nitin Gupta wrote:
> Hi Michael,
>
> On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
>> I understand that the 'safe' decompression code is 'somewhat slower'
>> and that decompressor performance is a key feature of this algorithm.
>> However, I am concerned about the safety implications of including
>> the 'unsafe' standard version in-kernel when likely uses include
>> compression of network data, memory objects and so-on, all of which
>> could in theory be maliciously modified.
>>
>
> The 'unsafe' version is still included since in some scenarios we have
> guarantee that compressed data has not been modified (for e.g. where
> we keep compressed data in memory only). So, in those cases there is
> no need to go for slower 'safe' version. So, the version of
> decompressor selected should be left to the user (kernel dev) only -
> he should make sure that he is using the right version.
Fair enough. However, this rather important issue is pretty much
undocumented (source code comments don't count) and Reiser4 is
already using the lzo1x_decompress() function rather than the
seemingly more appropriate lzo1x_decompress_safe() function...
http://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-
rc2/2.6.22-rc2-mm1/broken-out/reiser4-use-lzo-library-functions.patch
Perhaps a rename is in order:
lzo1x_decompress() => lzo1x_decompress_unsafe()
lzo1x_decompress_safe => lzo1x_decompress()
M-L
On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
>
> Fair enough. However, this rather important issue is pretty much
> undocumented (source code comments don't count)
If header file for public interface (<linux/lzo1x.h> documents about
'unsafe' vs. 'safe' then it should be enough.
> and Reiser4 is
> already using the lzo1x_decompress() function rather than the
> seemingly more appropriate lzo1x_decompress_safe() function...
>
> http://ftp.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.22-
> rc2/2.6.22-rc2-mm1/broken-out/reiser4-use-lzo-library-functions.patch
>
> Perhaps a rename is in order:
> lzo1x_decompress() => lzo1x_decompress_unsafe()
> lzo1x_decompress_safe => lzo1x_decompress()
>
Or perhaps make reiserfs use _safe() instead - I think Richard has
already submitted patch for same.
- Nitin
On 23 May 2007, at 15:03, Nitin Gupta wrote:
>> Perhaps a rename is in order:
>> lzo1x_decompress() => lzo1x_decompress_unsafe()
>> lzo1x_decompress_safe => lzo1x_decompress()
>
> Or perhaps make reiserfs use _safe() instead - I think Richard has
> already submitted patch for same.
If someone's already made this mistake once, then it'll happen again.
In-kernel memory corruption is no fun.
Safe/Secure == Default
Michael-Luke
On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
> On 23 May 2007, at 15:03, Nitin Gupta wrote:
>
> >> Perhaps a rename is in order:
> >> lzo1x_decompress() => lzo1x_decompress_unsafe()
> >> lzo1x_decompress_safe => lzo1x_decompress()
> >
> > Or perhaps make reiserfs use _safe() instead - I think Richard has
> > already submitted patch for same.
>
> If someone's already made this mistake once, then it'll happen again.
> In-kernel memory corruption is no fun.
>
> Safe/Secure == Default
If I rename 'nonsafe' version as such then it will seem like its a
'broken' implementation which is not the case. If somebody is upto
including compression he must be having head to use the right
decompress version depending on this scenario :-)
- Nitin
>
> Michael-Luke
>
>
On 23 May 2007, at 15:21, Nitin Gupta wrote:
> If somebody is up to including compression he must be having head
> to use the right
> decompress version depending on this scenario :-)
By that logic, experienced kernel dev Richard Purdie is not up to
using compression (?!)
To me, it looks like an easy trap to fall into. And one that an
experienced dev *has* just fallen in to.
M-L
On 5/23/07, Nitin Gupta <[email protected]> wrote:
> Hi,
>
> This contains LZO1X-1 compressor and LZO1X decompressor (safe and
> standard version).
> This includes changes suggested by various people - Thanks to all who
> reviewed previous patches for this LZO port.
>
> Changelog vs original LZO 2.02 code:
> - Chopped down huge parts of original code that were irrelevant fot this port
> - Use of standard data types
> - Use memcpy() instead of COPY4 macros used in orig. code
> - Various macros -> static inline functions
> - Code matches general kernel style
> - Various other cleanups suggested in reviews
>
> For now, tested on x86 only.
If you have a program to test this I can run it on an amd64 and a g4 ppc
> Signed-off-by: Nitin Gupta <[email protected]>
> ---
>
> diff --git a/Makefile b/Makefile
> index 34210af..88053ba 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -826,11 +826,18 @@ include/config/kernel.release:
> include/config/auto.conf FORCE
> # Listed in dependency order
> PHONY += prepare archprepare prepare0 prepare1 prepare2 prepare3
>
> +# prepare4 does module specific things prior to compilation
> +prepare4:
> +ifneq ($(CONFIG_LZO1X),n)
> + $(Q)ln -sf $(srctree)/lib/lzo1x/lzo1x_decompress.c \
> + $(srctree)/lib/lzo1x/lzo1x_decompress_safe.c
> +endif
> +
> # prepare3 is used to check if we are building in a separate output directory,
> # and if so do:
> # 1) Check that make has not been executed in the kernel src $(srctree)
> # 2) Create the include2 directory, used for the second asm symlink
> -prepare3: include/config/kernel.release
> +prepare3: prepare4 include/config/kernel.release
> ifneq ($(KBUILD_SRC),)
> @echo ' Using $(srctree) as source for kernel'
> $(Q)if [ -f $(srctree)/.config -o -d $(srctree)/include/config ]; then \
> diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
> new file mode 100755
> index 0000000..7c2f633
> --- /dev/null
> +++ b/include/linux/lzo1x.h
> @@ -0,0 +1,80 @@
> +/* lzo1x.h -- public interface of the LZO1X compression algorithm
> +
> + This file is part of the LZO real-time data compression library.
> +
> + Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
> + All Rights Reserved.
> +
> + The LZO library 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.
> +
> + The LZO library 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 the LZO library; see the file COPYING.
> + If not, write to the Free Software Foundation, Inc.,
> + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
> +
> + Markus F.X.J. Oberhumer
> + <[email protected]>
> + http://www.oberhumer.com/opensource/lzo/
> +
> +
> + This file is modified version of lzo1x.h found in original LZO 2.02
> + code. Some additional changes have also been made to make it work
> + in kernel space.
> +
> + Nitin Gupta
> + <[email protected]>
> + */
> +
> +#ifndef __LZO1X_H
> +#define __LZO1X_H
> +
> +/* LZO return codes */
> +#define LZO_E_OK 0
> +#define LZO_E_ERROR (-1)
> +#define LZO_E_OUT_OF_MEMORY (-2) /* [not used right now] */
> +#define LZO_E_NOT_COMPRESSIBLE (-3) /* [not used right now] */
> +#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) /* [not used right now] */
> +
> +/* Size of temp buffer (workmem) required by lzo1x_compress */
> +#define LZO1X_WORKMEM_SIZE ((size_t) (16384L * sizeof(unsigned char *)))
> +
> +/*
> + * This required 'workmem' of size LZO1X_WORKMEM_SIZE
> + */
> +int lzo1x_compress(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len,
> + void *workmem);
> +
> +
> +/*
> + * This decompressor expects valid compressed data.
> + *
> + * If the compressed data gets corrupted somehow (e.g. transmission
> + * via an erroneous channel, disk errors, ...) it will probably crash
> + * your application because absolutely no additional checks are done.
> + */
> +int lzo1x_decompress(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len);
> +
> +
> +/*
> + * The `safe' decompressor. Somewhat slower.
> + *
> + * This decompressor will catch all compressed data violations and
> + * return an error code in this case.
> + */
> +int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len);
> +#endif
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 2e7ae6b..9d30b1f 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -64,6 +64,12 @@ config ZLIB_INFLATE
> config ZLIB_DEFLATE
> tristate
>
> +config LZO1X
> + tristate "LZO1X Compression/Decompression"
> + help
> + Compression: LZO1X-1
> + Decompression: LZO1X
> +
> #
> # Generic allocator support is selected if needed
> #
> diff --git a/lib/Makefile b/lib/Makefile
> index c8c8e20..4dad99d 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -49,6 +49,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_LZO1X) += lzo1x/
>
> obj-$(CONFIG_TEXTSEARCH) += textsearch.o
> obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
> diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
> new file mode 100644
> index 0000000..e036b42
> --- /dev/null
> +++ b/lib/lzo1x/Makefile
> @@ -0,0 +1,11 @@
> +#
> +# When compiling this module out of tree, do 'make prepare_lzo'
> +# before compiling as usual
> +#
> +obj-$(CONFIG_LZO1X) += lzo1x.o
> +CFLAGS_lzo1x_decompress_safe.o += -DLZO1X_DECOMPRESS_SAFE
> +lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o lzo1x_decompress_safe.o
> +
> +prepare_lzo:
> + @ln -sf lzo1x_decompress.c lzo1x_decompress_safe.c
> +
> diff --git a/lib/lzo1x/lzo1x_compress.c b/lib/lzo1x/lzo1x_compress.c
> new file mode 100755
> index 0000000..690c082
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_compress.c
> @@ -0,0 +1,256 @@
> +/* lzo1x_compress.c -- LZO1X-1 compression
> +
> + This file is part of the LZO real-time data compression library.
> +
> + Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
> + All Rights Reserved.
> +
> + The LZO library 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.
> +
> + The LZO library 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 the LZO library; see the file COPYING.
> + If not, write to the Free Software Foundation, Inc.,
> + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
> +
> + Markus F.X.J. Oberhumer
> + <[email protected]>
> + http://www.oberhumer.com/opensource/lzo/
> +
> +
> + This file is derived from lzo1x_1.c and lzo1x_c.ch found in original
> + LZO 2.02 code. Some additional changes have also been made to make
> + it work in kernel space.
> +
> + Nitin Gupta
> + <[email protected]>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <linux/compiler.h>
> +
> +#include "lzo1x_int.h"
> +
> +MODULE_LICENSE("GPL");
> +MODULE_DESCRIPTION("LZO1X Compression");
> +
> +/* compress a block of data. */
> +static unsigned int
> +lzo1x_compress_worker(const unsigned char *in, size_t in_len,
> + unsigned char *out, size_t *out_len,
> + void *workmem)
> +{
> + const unsigned char *ip;
> + unsigned char *op;
> + const unsigned char * const in_end = in + in_len;
> + const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
> + const unsigned char *ii;
> + const unsigned char ** const dict = (const unsigned char **)workmem;
> +
> + op = out;
> + ip = in;
> + ii = ip;
> +
> + ip += 4;
> + for (;;) {
> + const unsigned char *m_pos;
> + size_t m_off;
> + size_t m_len;
> + size_t dindex;
> +
> + dindex = DINDEX1(ip);
> + m_pos = dict[dindex];
> +
> + if ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
> + || m_off > M4_MAX_OFFSET)
> + goto literal;
> +
> + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
> + goto try_match;
> +
> + dindex = DINDEX2(dindex);
> + m_pos = dict[dindex];
> +
> + if ((m_pos < in) || (m_off = (size_t)(ip - m_pos)) <= 0
> + || m_off > M4_MAX_OFFSET)
> + goto literal;
> +
> + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
> + goto try_match;
> +
> + goto literal;
> +
> +try_match:
> + if (*(const unsigned short *)m_pos ==
> + *(const unsigned short *)ip) {
> + if (likely(m_pos[2] == ip[2]))
> + goto match;
> + }
> +
> + /* a literal */
> +literal:
> + dict[dindex] = ip;
> + ++ip;
> + if (unlikely(ip >= ip_end))
> + break;
> + continue;
> +
> + /* a match */
> +match:
> + dict[dindex] = ip;
> + /* store current literal run */
> + if ((size_t)(ip - ii) > 0) {
> + size_t t = (size_t)(ip - ii);
> + if (t <= 3)
> + op[-2] |= (unsigned char)(t);
> + else if (t <= 18)
> + *op++ = (unsigned char)(t - 3);
> + else {
> + size_t tt = t - 18;
> + *op++ = 0;
> + while (tt > 255) {
> + tt -= 255;
> + *op++ = 0;
> + }
> + *op++ = (unsigned char)tt;
> + }
> + do *op++ = *ii++; while (--t > 0);
> + }
> +
> + /* code the match */
> + ip += 3;
> + if (m_pos[3] != *ip++ || m_pos[4] != *ip++ ||
> + m_pos[5] != *ip++ || m_pos[6] != *ip++ ||
> + m_pos[7] != *ip++ || m_pos[8] != *ip++) {
> + --ip;
> + m_len = (size_t)(ip - ii);
> +
> + if (m_off <= M2_MAX_OFFSET) {
> + m_off -= 1;
> + *op++ = (unsigned char)(((m_len - 1) << 5) |
> + ((m_off & 7) << 2));
> + *op++ = (unsigned char)(m_off >> 3);
> + }
> + else if (m_off <= M3_MAX_OFFSET) {
> + m_off -= 1;
> + *op++ = (unsigned char)(M3_MARKER |
> + (m_len - 2));
> + goto m3_m4_offset;
> + } else {
> + m_off -= 0x4000;
> + *op++ = (unsigned char)(M4_MARKER |
> + ((m_off & 0x4000) >> 11) |
> + (m_len - 2));
> + goto m3_m4_offset;
> + }
> + } else {
> + const unsigned char *end = in_end;
> + const unsigned char *m = m_pos + M2_MAX_LEN + 1;
> + while (ip < end && *m == *ip)
> + m++, ip++;
> + m_len = (size_t)(ip - ii);
> +
> + if (m_off <= M3_MAX_OFFSET) {
> + m_off -= 1;
> + if (m_len <= 33)
> + *op++ = (unsigned char)(M3_MARKER |
> + (m_len - 2));
> + else {
> + m_len -= 33;
> + *op++ = M3_MARKER | 0;
> + goto m3_m4_len;
> + }
> + } else {
> + m_off -= 0x4000;
> + if (m_len <= M4_MAX_LEN)
> + *op++ = (unsigned char)(M4_MARKER |
> + ((m_off & 0x4000) >> 11) |
> + (m_len - 2));
> + else {
> + m_len -= M4_MAX_LEN;
> + *op++ = (unsigned char)(M4_MARKER |
> + ((m_off & 0x4000) >> 11));
> +m3_m4_len:
> + while (m_len > 255) {
> + m_len -= 255;
> + *op++ = 0;
> + }
> + *op++ = (unsigned char)(m_len);
> + }
> + }
> +
> +m3_m4_offset:
> + *op++ = (unsigned char)((m_off & 63) << 2);
> + *op++ = (unsigned char)(m_off >> 6);
> + }
> +
> + ii = ip;
> + if (unlikely(ip >= ip_end))
> + break;
> + }
> +
> + *out_len = (size_t)(op - out);
> + return (size_t)(in_end - ii);
> +}
> +
> +
> +/*
> + * This requires buffer (workmem) of size LZO1X_WORKMEM_SIZE
> + * (exported by lzo1x.h).
> + */
> +int
> +lzo1x_compress(const unsigned char *in, size_t in_len,
> + unsigned char *out, size_t *out_len,
> + void *workmem)
> +{
> + unsigned char *op = out;
> + size_t t;
> +
> + if (!workmem)
> + return -EINVAL;
> +
> + if (unlikely(in_len <= M2_MAX_LEN + 5))
> + t = in_len;
> + else {
> + t = lzo1x_compress_worker(in, in_len, op, out_len, workmem);
> + op += *out_len;
> + }
> +
> + if (t > 0) {
> + const unsigned char *ii = in + in_len - t;
> +
> + if (op == out && t <= 238)
> + *op++ = (unsigned char)(17 + t);
> + else if (t <= 3)
> + op[-2] |= (unsigned char)(t);
> + else if (t <= 18)
> + *op++ = (unsigned char)(t - 3);
> + else {
> + size_t tt = t - 18;
> + *op++ = 0;
> + while (tt > 255) {
> + tt -= 255;
> + *op++ = 0;
> + }
> + *op++ = (unsigned char)tt;
> + }
> + memcpy(op, ii, t);
> + op += t;
> + ii += t;
> + }
> + *op++ = M4_MARKER | 1;
> + *op++ = 0;
> + *op++ = 0;
> +
> + *out_len = (size_t)(op - out);
> + return 0;
> +}
> +
> +EXPORT_SYMBOL(lzo1x_compress);
> diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> new file mode 100755
> index 0000000..09fa1ca
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_decompress.c
> @@ -0,0 +1,224 @@
> +/* lzo1x_decompress.c -- LZO1X decompression
> +
> + This file is part of the LZO real-time data compression library.
> +
> + Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
> + All Rights Reserved.
> +
> + The LZO library 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.
> +
> + The LZO library 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 the LZO library; see the file COPYING.
> + If not, write to the Free Software Foundation, Inc.,
> + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
> +
> + Markus F.X.J. Oberhumer
> + <[email protected]>
> + http://www.oberhumer.com/opensource/lzo/
> +
> +
> + This file is derived from lzo1x_d1.c and lzo1x_d.ch found in original
> + LZO 2.02 code. Some additional changes have also been made to make
> + it work in kernel space.
> +
> + Nitin Gupta
> + <[email protected]>
> + */
> +
> +#include <linux/kernel.h>
> +#include <linux/module.h>
> +#include <asm/byteorder.h>
> +#include <linux/lzo1x.h>
> +
> +#include "lzo1x_int.h"
> +
> +MODULE_LICENSE("GPL");
> +MODULE_DESCRIPTION("LZO1X Decompression");
> +
> +int
> +lzo1x_decompress(const unsigned char *in, size_t in_len,
> + unsigned char *out, size_t *out_len)
> +{
> + size_t t;
> + unsigned char *op = out;
> + const unsigned char *ip = in, *m_pos;
> + const unsigned char * const ip_end = in + in_len;
> +#if defined(HAVE_ANY_OP)
> + unsigned char * const op_end = out + *out_len;
> +#endif
> + *out_len = 0;
> +
> + if (*ip > 17) {
> + t = *ip++ - 17;
> + if (t < 4)
> + goto match_next;
> + NEED_OP(t);
> + NEED_IP(t + 1);
> + memcpy(op, ip, t);
> + op += t;
> + ip += t;
> + goto first_literal_run;
> + }
> +
> + while (TEST_IP) {
> + t = *ip++;
> + if (t >= 16)
> + goto match;
> + /* a literal run */
> + if (t == 0) {
> + NEED_IP(1);
> + while (*ip == 0) {
> + t += 255;
> + ip++;
> + NEED_IP(1);
> + }
> + t += 15 + *ip++;
> + }
> + /* copy literals */
> + NEED_OP(t + 3);
> + NEED_IP(t + 4);
> + memcpy(op, ip, t + 3);
> + op += t + 3;
> + ip += t + 3;
> +
> +first_literal_run:
> + t = *ip++;
> + if (t >= 16)
> + goto match;
> + m_pos = op - (1 + M2_MAX_OFFSET);
> + m_pos -= t >> 2;
> + m_pos -= *ip++ << 2;
> + TEST_LB(m_pos);
> + NEED_OP(3);
> + *op++ = *m_pos++;
> + *op++ = *m_pos++;
> + *op++ = *m_pos;
> + goto match_done;
> +
> + /* handle matches */
> + do {
> +match:
> + if (t >= 64) { /* a M2 match */
> + m_pos = op - 1;
> + m_pos -= (t >> 2) & 7;
> + m_pos -= *ip++ << 3;
> + t = (t >> 5) - 1;
> + TEST_LB(m_pos);
> + NEED_OP(t + 3 - 1);
> + goto copy_match;
> + } else if (t >= 32) { /* a M3 match */
> + t &= 31;
> + if (t == 0) {
> + NEED_IP(1);
> + while (*ip == 0) {
> + t += 255;
> + ip++;
> + NEED_IP(1);
> + }
> + t += 31 + *ip++;
> + }
> + m_pos = op - 1 - (cpu_to_le16(
> + *(const unsigned short *)ip) >> 2);
> + ip += 2;
> + } else if (t >= 16) { /* a M4 match */
> + m_pos = op;
> + m_pos -= (t & 8) << 11;
> + t &= 7;
> + if (t == 0) {
> + NEED_IP(1);
> + while (*ip == 0) {
> + t += 255;
> + ip++;
> + NEED_IP(1);
> + }
> + t += 7 + *ip++;
> + }
> + m_pos -= cpu_to_le16(
> + *(const unsigned short *)ip) >> 2;
> + ip += 2;
> + if (m_pos == op)
> + goto eof_found;
> + m_pos -= 0x4000;
> + } else { /* a M1 match */
> + m_pos = op - 1;
> + m_pos -= t >> 2;
> + m_pos -= *ip++ << 2;
> + TEST_LB(m_pos);
> + NEED_OP(2);
> + *op++ = *m_pos++;
> + *op++ = *m_pos;
> + goto match_done;
> + }
> +
> + /* copy match */
> + TEST_LB(m_pos);
> + NEED_OP(t + 3 - 1);
> +
> +copy_match:
> + if (op - m_pos >= BITS_PER_LONG / BITS_PER_BYTE) {
> + memcpy(op, m_pos, t + 2);
> + op += t + 2;
> + m_pos += t + 2;
> + } else {
> + *op = *m_pos;
> + *++op = *++m_pos;
> + do
> + *++op = *++m_pos;
> + while (--t > 0);
> + op++;
> + m_pos++;
> + }
> +
> +match_done:
> + t = ip[-2] & 3;
> + if (t == 0)
> + break;
> +
> + /* copy literals */
> +match_next:
> + NEED_OP(t);
> + NEED_IP(t+1);
> + *op++ = *ip++;
> + if (t > 1) {
> + *op++ = *ip++;
> + if (t > 2)
> + *op++ = *ip++;
> + }
> + t = *ip++;
> + } while (TEST_IP);
> + }
> +
> +#if defined(HAVE_TEST_IP)
> + /* no EOF code was found */
> + *out_len = (size_t)(op - out);
> + return LZO_E_EOF_NOT_FOUND;
> +#endif
> +
> +eof_found:
> + *out_len = (size_t)(op - out);
> + return (ip == ip_end ? LZO_E_OK :
> + (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
> +
> +#if defined(LZO1X_DECOMPRESS_SAFE)
> +input_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_INPUT_OVERRUN;
> +
> +output_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_OUTPUT_OVERRUN;
> +
> +lookbehind_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_LOOKBEHIND_OVERRUN;
> +#endif
> +}
> +
> +EXPORT_SYMBOL(lzo1x_decompress);
> diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> new file mode 100755
> index 0000000..69e6d9b
> --- /dev/null
> +++ b/lib/lzo1x/lzo1x_int.h
> @@ -0,0 +1,122 @@
> +/* lzo1x_int.h -- to be used internally by LZO de/compression algorithms
> +
> + This file is part of the LZO real-time data compression library.
> +
> + Copyright (C) 1996-2005 Markus Franz Xaver Johannes Oberhumer
> + All Rights Reserved.
> +
> + The LZO library 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.
> +
> + The LZO library 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 the LZO library; see the file COPYING.
> + If not, write to the Free Software Foundation, Inc.,
> + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
> +
> + Markus F.X.J. Oberhumer
> + <[email protected]>
> + http://www.oberhumer.com/opensource/lzo/
> +
> +
> + This file was derived from several header files found in original
> + LZO 2.02 code. Some additional changes have also been made to make
> + it work in kernel space.
> +
> + Nitin Gupta
> + <[email protected]>
> + */
> +
> +#ifndef __LZO1X_INT_H
> +#define __LZO1X_INT_H
> +
> +#include <linux/types.h>
> +
> +#define D_BITS 14
> +#define D_SIZE (1u << D_BITS)
> +#define D_MASK (D_SIZE - 1)
> +#define D_HIGH ((D_MASK >> 1) + 1)
> +
> +static inline size_t DX2(const unsigned char *p, size_t s1, size_t s2)
> +{
> + return (((((size_t)(p[2]) << s2) ^ p[1]) << s1) ^ p[0]);
> +}
> +
> +static inline size_t DX3(const unsigned char *p, size_t s1, size_t
> s2, size_t s3)
> +{
> + return (DX2(p + 1, s2, s3) << s1) ^ p[0];
> +}
> +
> +static inline size_t DINDEX1(const unsigned char *p)
> +{
> + return ((size_t)(0x21 * DX3(p, 5, 5, 6)) >> 5) & D_MASK;
> +}
> +
> +static inline size_t DINDEX2(size_t d)
> +{
> + return (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
> +}
> +
> +/* LZO1X Specific constants */
> +#define M1_MAX_OFFSET 0x0400
> +#define M2_MAX_OFFSET 0x0800
> +#define M3_MAX_OFFSET 0x4000
> +#define M4_MAX_OFFSET 0xbfff
> +
> +#define M1_MIN_LEN 2
> +#define M1_MAX_LEN 2
> +#define M2_MIN_LEN 3
> +#define M2_MAX_LEN 8
> +#define M3_MIN_LEN 3
> +#define M3_MAX_LEN 33
> +#define M4_MIN_LEN 3
> +#define M4_MAX_LEN 9
> +
> +#define M1_MARKER 0
> +#define M2_MARKER 64
> +#define M3_MARKER 32
> +#define M4_MARKER 16
> +
> +/* LZO return codes */
> +#define LZO_E_OK 0
> +#define LZO_E_ERROR (-1)
> +#define LZO_E_OUT_OF_MEMORY (-2) /* [not used right now] */
> +#define LZO_E_NOT_COMPRESSIBLE (-3) /* [not used right now] */
> +#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) /* [not used right now] */
> +
> +/* Macros for 'safe' decompression */
> +#ifdef LZO1X_DECOMPRESS_SAFE
> +
> +#define lzo1x_decompress lzo1x_decompress_safe
> +#define TEST_IP (ip < ip_end)
> +#define NEED_IP(x) \
> + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> +#define NEED_OP(x) \
> + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> +#define TEST_LB(m_pos) \
> + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> +#define HAVE_TEST_IP
> +#define HAVE_ANY_OP
> +
> +#else /* !LZO1X_DECOMPRESS_SAFE */
> +
> +#define TEST_IP 1
> +#define TEST_LB(x) ((void) 0)
> +#define NEED_IP(x) ((void) 0)
> +#define NEED_OP(x) ((void) 0)
> +#undef HAVE_TEST_IP
> +#undef HAVE_ANY_OP
> +
> +#endif /* LZO1X_DECOMPRESS_SAFE */
> +
> +#endif
>
>
On Wed, 23 May 2007 19:51:44 +0530 "Nitin Gupta" <[email protected]> wrote:
> On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
> > On 23 May 2007, at 15:03, Nitin Gupta wrote:
> >
> > >> Perhaps a rename is in order:
> > >> lzo1x_decompress() => lzo1x_decompress_unsafe()
> > >> lzo1x_decompress_safe => lzo1x_decompress()
> > >
> > > Or perhaps make reiserfs use _safe() instead - I think Richard has
> > > already submitted patch for same.
> >
> > If someone's already made this mistake once, then it'll happen again.
> > In-kernel memory corruption is no fun.
> >
> > Safe/Secure == Default
>
> If I rename 'nonsafe' version as such then it will seem like its a
> 'broken' implementation which is not the case. If somebody is upto
> including compression he must be having head to use the right
> decompress version depending on this scenario :-)
>
<wakes up>
What's "unsafe" here? If you fed it bad data, the decompressor will
scribble on memory or crash the kernel or hang up?
If so, it was quite inappropriate that a filesystem be using the unsafe
version.
I'd agree with the proposed renaming. In fact I'd suggest that the unsafe
APIs just be removed - it's hard to imagine a situation in which they're OK
to be used in the kernel.
On Wed, 2007-05-23 at 09:16 -0700, Andrew Morton wrote:
> On Wed, 23 May 2007 19:51:44 +0530 "Nitin Gupta" <[email protected]> wrote:
> > On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
> > If I rename 'nonsafe' version as such then it will seem like its a
> > 'broken' implementation which is not the case. If somebody is upto
> > including compression he must be having head to use the right
> > decompress version depending on this scenario :-)
> >
>
> <wakes up>
>
> What's "unsafe" here? If you fed it bad data, the decompressor will
> scribble on memory or crash the kernel or hang up?
It can scribble on memory it shouldn't.
> If so, it was quite inappropriate that a filesystem be using the unsafe
> version.
Yes, I'll give you a patch to change the resier4 code in -mm then (if
its not already been changed).
> I'd agree with the proposed renaming. In fact I'd suggest that the unsafe
> APIs just be removed - it's hard to imagine a situation in which they're OK
> to be used in the kernel.
The compressed cache code might be one exception since it does the
compression itself and shouldn't get corrupted. If it does get
corrupted, you have bigger problems.
I'll provide a patch to update the LZO code in -mm to add unsafe to the
name.
Cheers,
Richard
Hi Nitin,
On 5/23/07, Nitin Gupta <[email protected]> wrote:
> [...]
> diff --git a/Makefile b/Makefile
> index 34210af..88053ba 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -826,11 +826,18 @@ include/config/kernel.release:
> include/config/auto.conf FORCE
> # Listed in dependency order
> PHONY += prepare archprepare prepare0 prepare1 prepare2 prepare3
>
> +# prepare4 does module specific things prior to compilation
> +prepare4:
> +ifneq ($(CONFIG_LZO1X),n)
> + $(Q)ln -sf $(srctree)/lib/lzo1x/lzo1x_decompress.c \
> + $(srctree)/lib/lzo1x/lzo1x_decompress_safe.c
> +endif
> +
Is this addition to the master Makefile really necessary? We're just
setting up a source file link here ... is this something temporary that
you're proposing that'll last only till this gets tested or do you want
this kind of special-casing for lzo1x here permanently?
> diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
> [...]
> +/* Size of temp buffer (workmem) required by lzo1x_compress */
> +#define LZO1X_WORKMEM_SIZE ((size_t) (16384L * sizeof(unsigned char *)))
> +
> +/*
> + * This required 'workmem' of size LZO1X_WORKMEM_SIZE
> + */
> +int lzo1x_compress(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len,
> + void *workmem);
Just defining and exporting LZO1X_WORKMEM_SIZE may not be enough
to guarantee that users _will_ pass in workmem of size exactly that much.
If this workmem is really merely a temp buffer required by lzo1x_compress(),
I'd suggest you rename lzo1x_compress() in lzo1x_compress.c to
__lzo1x_compress(), and implement a lzo1x_compress() wrapper for the
user that handles the allocation (and subsequent free'ing) of this temp
buffer itself.
[ I vaguely remember discussing something of this sort with Richard
when he had submitted his patchset too, perhaps you can look into
his implementation to see how he's managing this ... ]
> +/*
> + * This decompressor expects valid compressed data.
> + *
> + * If the compressed data gets corrupted somehow (e.g. transmission
> + * via an erroneous channel, disk errors, ...) it will probably crash
> + * your application because absolutely no additional checks are done.
^^^^^^^^^^^
Whoa! "your application" here is _kernel code_ and not a userspace
program ... "crashing" it is something we could do without :-)
> + */
> +int lzo1x_decompress(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len);
> +
> +
> +/*
> + * The `safe' decompressor. Somewhat slower.
> + *
> + * This decompressor will catch all compressed data violations and
> + * return an error code in this case.
> + */
> +int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
> + unsigned char *dst, size_t *dst_len);
> +#endif
I just read the follow-ups to this, so perhaps we /can/ use the unsafe
versions in certain situations. But I agree with Michael's suggestion
to rename _safe to decompress and decompress to _unsafe ...
> diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
> [...]
> +#
> +# When compiling this module out of tree, do 'make prepare_lzo'
> +# before compiling as usual
> +#
> +obj-$(CONFIG_LZO1X) += lzo1x.o
> +CFLAGS_lzo1x_decompress_safe.o += -DLZO1X_DECOMPRESS_SAFE
> +lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o lzo1x_decompress_safe.o
> +
> +prepare_lzo:
> + @ln -sf lzo1x_decompress.c lzo1x_decompress_safe.c
> +
... ah, so that's why the master Makefile changes.
Hmmm, perhaps you could extract the common stuff between the
_safe and _unsafe versions out into a separate function and then
reuse it from _safe and _unsafe wrappers? In any case, this kind
of Makefile jugglery (even in the master Makefile) just to avoid the
above doesn't seem quite right ...
> diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> [...]
> +#if defined(LZO1X_DECOMPRESS_SAFE)
> +input_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_INPUT_OVERRUN;
> +
> +output_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_OUTPUT_OVERRUN;
> +
> +lookbehind_overrun:
> + *out_len = (size_t)(op - out);
> + return LZO_E_LOOKBEHIND_OVERRUN;
> +#endif
> +}
> +
> +EXPORT_SYMBOL(lzo1x_decompress);
Ok, so this is all there is between _safe and _unsafe, it seems ...
> diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> [...]
> +/* Macros for 'safe' decompression */
> +#ifdef LZO1X_DECOMPRESS_SAFE
> +
> +#define lzo1x_decompress lzo1x_decompress_safe
> +#define TEST_IP (ip < ip_end)
> +#define NEED_IP(x) \
> + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> +#define NEED_OP(x) \
> + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> +#define TEST_LB(m_pos) \
> + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> +#define HAVE_TEST_IP
> +#define HAVE_ANY_OP
> +
> +#else /* !LZO1X_DECOMPRESS_SAFE */
> +
> +#define TEST_IP 1
> +#define TEST_LB(x) ((void) 0)
> +#define NEED_IP(x) ((void) 0)
> +#define NEED_OP(x) ((void) 0)
> +#undef HAVE_TEST_IP
> +#undef HAVE_ANY_OP
> +
> +#endif /* LZO1X_DECOMPRESS_SAFE */
... ugh. Yes, extracting the common stuff between the _safe and _unsafe
variants in a common low-level __lzo1x_decompress kind of function
definitely looks doable. The low-level function could simply take an extra
argument (say, set by the _safe and _unsafe wrappers) that tells it
whether it is being called as safe or unsafe ... helps us get rid of the
disruptions to all the Makefiles above and these #ifdef's ugliness ...
BTW, it'd be really cool if Richard and yourself could get together and
pool your energies / efforts to develop a common / same patchset for this.
(I wonder how different your implementations are, actually, and if there
are any significant performance disparities, especially.) I really like your
work, as it clears up the major gripe I had with Richard's patchset -- the
ugliness (and monstrosity) of it. But he's also worked up the glue code for
cryptoapi / jffs2 etc for this, so no point duplicating his efforts.
Satyam
On 5/23/07, Richard Purdie <[email protected]> wrote:
> On Wed, 2007-05-23 at 09:16 -0700, Andrew Morton wrote:
> > On Wed, 23 May 2007 19:51:44 +0530 "Nitin Gupta" <[email protected]> wrote:
> > > On 5/23/07, Michael-Luke Jones <[email protected]> wrote:
>
> > If so, it was quite inappropriate that a filesystem be using the unsafe
> > version.
>
> Yes, I'll give you a patch to change the resier4 code in -mm then (if
> its not already been changed).
Richard, are you planning to use this patch for LZO or your own port?
Can we decide on a Final Unified(tm) version of LZO port and then
patch up reiser4 or whatever to use that Ultimate LZO instead?
Can you please look into this (take 3) version on LZO patch posted and
we can edit/add/remove things from this to unify our effort - there is
no point in this duplication.
Perhaps you have opinion of maintaining diffability with original LZO
code which differs from mine. Since the code is now just ~500 lines it
should be fair enough to have major overhauls for sake of clean
KernelStyle(tm) code. It shouldn't be that hard to verify this small
code for bugs that might have crept in during porting work. As regard
to keeping up with future LZO versions, hm.... that will be hard - but
I don't think algorithm itself will change and optimizations can
always be done separately in this fork.
>
> > I'd agree with the proposed renaming. In fact I'd suggest that the unsafe
> > APIs just be removed - it's hard to imagine a situation in which they're OK
> > to be used in the kernel.
>
> The compressed cache code might be one exception since it does the
> compression itself and shouldn't get corrupted. If it does get
> corrupted, you have bigger problems.
>
Yes. Compressed Caching is one of cases where compressed data cannot
get magically corrupted. Hence, there is no need to go for the 'safe'
version. There might be other such cases too, so removing 'unsafe'
version is not good.
Ok, I will rename 'unsafe' version as such (as suggested by Michael).
Cheers,
Nitin
Hi Satyam,
Thanks for you comments.
On 5/24/07, Satyam Sharma <[email protected]> wrote:
> On 5/23/07, Nitin Gupta <[email protected]> wrote:
> > diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
> > [...]
> > +/* Size of temp buffer (workmem) required by lzo1x_compress */
> > +#define LZO1X_WORKMEM_SIZE ((size_t) (16384L * sizeof(unsigned char *)))
> > +
> > +/*
> > + * This required 'workmem' of size LZO1X_WORKMEM_SIZE
> > + */
> > +int lzo1x_compress(const unsigned char *src, size_t src_len,
> > + unsigned char *dst, size_t *dst_len,
> > + void *workmem);
>
> Just defining and exporting LZO1X_WORKMEM_SIZE may not be enough
> to guarantee that users _will_ pass in workmem of size exactly that much.
>
> If this workmem is really merely a temp buffer required by lzo1x_compress(),
> I'd suggest you rename lzo1x_compress() in lzo1x_compress.c to
> __lzo1x_compress(), and implement a lzo1x_compress() wrapper for the
> user that handles the allocation (and subsequent free'ing) of this temp
> buffer itself.
>
I did not include such wrapper since allocation method will depend on
particular scenario (like kmalloc vs. vmalloc and flags GFP_KERNEL vs
GFP_ATOMIC etc...). But still maybe we can have "default" wrapper that
does, say vmalloc(GFP_KERNEL)/vfree and let others with specific
requirement have their own wrappers.
> [ I vaguely remember discussing something of this sort with Richard
> when he had submitted his patchset too, perhaps you can look into
> his implementation to see how he's managing this ... ]
>
ok.
> > +/*
> > + * This decompressor expects valid compressed data.
> > + *
> > + * If the compressed data gets corrupted somehow (e.g. transmission
> > + * via an erroneous channel, disk errors, ...) it will probably crash
> > + * your application because absolutely no additional checks are done.
> ^^^^^^^^^^^
>
> Whoa! "your application" here is _kernel code_ and not a userspace
> program ... "crashing" it is something we could do without :-)
>
Firstly, will change s/your application/kernel. "crash" also seems a
bit vague in this sense...
> > + */
> > +int lzo1x_decompress(const unsigned char *src, size_t src_len,
> > + unsigned char *dst, size_t *dst_len);
> > +
> > +
> > +/*
> > + * The `safe' decompressor. Somewhat slower.
> > + *
> > + * This decompressor will catch all compressed data violations and
> > + * return an error code in this case.
> > + */
> > +int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
> > + unsigned char *dst, size_t *dst_len);
> > +#endif
>
> I just read the follow-ups to this, so perhaps we /can/ use the unsafe
> versions in certain situations. But I agree with Michael's suggestion
> to rename _safe to decompress and decompress to _unsafe ...
Ok. I will do this.
>
> > diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
> > [...]
> > +#
> > +# When compiling this module out of tree, do 'make prepare_lzo'
> > +# before compiling as usual
> > +#
> > +obj-$(CONFIG_LZO1X) += lzo1x.o
> > +CFLAGS_lzo1x_decompress_safe.o += -DLZO1X_DECOMPRESS_SAFE
> > +lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o lzo1x_decompress_safe.o
> > +
> > +prepare_lzo:
> > + @ln -sf lzo1x_decompress.c lzo1x_decompress_safe.c
> > +
>
> ... ah, so that's why the master Makefile changes.
>
> Hmmm, perhaps you could extract the common stuff between the
> _safe and _unsafe versions out into a separate function and then
> reuse it from _safe and _unsafe wrappers? In any case, this kind
> of Makefile jugglery (even in the master Makefile) just to avoid the
> above doesn't seem quite right ...
Ok. I will look into this.
>
> > diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> > [...]
> > +#if defined(LZO1X_DECOMPRESS_SAFE)
> > +input_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_INPUT_OVERRUN;
> > +
> > +output_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_OUTPUT_OVERRUN;
> > +
> > +lookbehind_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_LOOKBEHIND_OVERRUN;
> > +#endif
> > +}
> > +
> > +EXPORT_SYMBOL(lzo1x_decompress);
>
> Ok, so this is all there is between _safe and _unsafe, it seems ...
>
No. The code has macros like NEED_IP, NEED_OP etc. at many places
which are no-op for 'unsafe' version.
> > diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> > [...]
> > +/* Macros for 'safe' decompression */
> > +#ifdef LZO1X_DECOMPRESS_SAFE
> > +
> > +#define lzo1x_decompress lzo1x_decompress_safe
> > +#define TEST_IP (ip < ip_end)
> > +#define NEED_IP(x) \
> > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > +#define NEED_OP(x) \
> > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > +#define TEST_LB(m_pos) \
> > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > +#define HAVE_TEST_IP
> > +#define HAVE_ANY_OP
> > +
> > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > +
> > +#define TEST_IP 1
> > +#define TEST_LB(x) ((void) 0)
> > +#define NEED_IP(x) ((void) 0)
> > +#define NEED_OP(x) ((void) 0)
> > +#undef HAVE_TEST_IP
> > +#undef HAVE_ANY_OP
> > +
> > +#endif /* LZO1X_DECOMPRESS_SAFE */
>
> ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> variants in a common low-level __lzo1x_decompress kind of function
> definitely looks doable. The low-level function could simply take an extra
> argument (say, set by the _safe and _unsafe wrappers) that tells it
> whether it is being called as safe or unsafe ... helps us get rid of the
> disruptions to all the Makefiles above and these #ifdef's ugliness ..
Hmm..I will try to get this done.
>
> BTW, it'd be really cool if Richard and yourself could get together and
> pool your energies / efforts to develop a common / same patchset for this.
> (I wonder how different your implementations are, actually, and if there
> are any significant performance disparities, especially.) I really like your
> work, as it clears up the major gripe I had with Richard's patchset -- the
> ugliness (and monstrosity) of it.
I am really looking forward to co-operating with Richard regarding
this - although our approach for this porting is quite different but I
hope we can get around this. Duplication sucks! :)
> But he's also worked up the glue code for
> cryptoapi / jffs2 etc for this, so no point duplicating his efforts.
>
> Satyam
>
Sure. I am not going to duplicate these.
Cheers,
Nitin
On Thu, 2007-05-24 at 01:04 +0530, Satyam Sharma wrote:
> On 5/23/07, Nitin Gupta <[email protected]> wrote:
> > diff --git a/include/linux/lzo1x.h b/include/linux/lzo1x.h
> > [...]
> > +/* Size of temp buffer (workmem) required by lzo1x_compress */
> > +#define LZO1X_WORKMEM_SIZE ((size_t) (16384L * sizeof(unsigned char *)))
> > +
> > +/*
> > + * This required 'workmem' of size LZO1X_WORKMEM_SIZE
> > + */
> > +int lzo1x_compress(const unsigned char *src, size_t src_len,
> > + unsigned char *dst, size_t *dst_len,
> > + void *workmem);
>
> Just defining and exporting LZO1X_WORKMEM_SIZE may not be enough
> to guarantee that users _will_ pass in workmem of size exactly that much.
>
> If this workmem is really merely a temp buffer required by lzo1x_compress(),
> I'd suggest you rename lzo1x_compress() in lzo1x_compress.c to
> __lzo1x_compress(), and implement a lzo1x_compress() wrapper for the
> user that handles the allocation (and subsequent free'ing) of this temp
> buffer itself.
>
> [ I vaguely remember discussing something of this sort with Richard
> when he had submitted his patchset too, perhaps you can look into
> his implementation to see how he's managing this ... ]
I remember this being mentioned. My answer was that this is the same
behaviour as the zlib library and you do not want to alloc/free this
memory every time you have a piece of data to compress as it will
totally cripple performance. This allocation of buffers is a standard
part of the crypto and jffs2 compression APIs too.
> I just read the follow-ups to this, so perhaps we /can/ use the unsafe
> versions in certain situations. But I agree with Michael's suggestion
> to rename _safe to decompress and decompress to _unsafe ...
Lets just add the _unsafe postfix and leave "safe" alone, then it
remains the same name as userspace and will be less confusing for anyone
used to the userspace library ;-).
> > diff --git a/lib/lzo1x/Makefile b/lib/lzo1x/Makefile
> > [...]
> > +#
> > +# When compiling this module out of tree, do 'make prepare_lzo'
> > +# before compiling as usual
> > +#
> > +obj-$(CONFIG_LZO1X) += lzo1x.o
> > +CFLAGS_lzo1x_decompress_safe.o += -DLZO1X_DECOMPRESS_SAFE
> > +lzo1x-objs := lzo1x_compress.o lzo1x_decompress.o lzo1x_decompress_safe.o
> > +
> > +prepare_lzo:
> > + @ln -sf lzo1x_decompress.c lzo1x_decompress_safe.c
> > +
>
> ... ah, so that's why the master Makefile changes.
>
> Hmmm, perhaps you could extract the common stuff between the
> _safe and _unsafe versions out into a separate function and then
> reuse it from _safe and _unsafe wrappers? In any case, this kind
> of Makefile jugglery (even in the master Makefile) just to avoid the
> above doesn't seem quite right ...
FWIW, I don't like the symlink much either. My version of the patch
doesn't do things that way.
> > diff --git a/lib/lzo1x/lzo1x_decompress.c b/lib/lzo1x/lzo1x_decompress.c
> > [...]
> > +#if defined(LZO1X_DECOMPRESS_SAFE)
> > +input_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_INPUT_OVERRUN;
> > +
> > +output_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_OUTPUT_OVERRUN;
> > +
> > +lookbehind_overrun:
> > + *out_len = (size_t)(op - out);
> > + return LZO_E_LOOKBEHIND_OVERRUN;
> > +#endif
> > +}
> > +
> > +EXPORT_SYMBOL(lzo1x_decompress);
>
> Ok, so this is all there is between _safe and _unsafe, it seems ...
No, since there is some ifdefs in the header file.
> > diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> > [...]
> > +/* Macros for 'safe' decompression */
> > +#ifdef LZO1X_DECOMPRESS_SAFE
> > +
> > +#define lzo1x_decompress lzo1x_decompress_safe
> > +#define TEST_IP (ip < ip_end)
> > +#define NEED_IP(x) \
> > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > +#define NEED_OP(x) \
> > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > +#define TEST_LB(m_pos) \
> > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > +#define HAVE_TEST_IP
> > +#define HAVE_ANY_OP
> > +
> > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > +
> > +#define TEST_IP 1
> > +#define TEST_LB(x) ((void) 0)
> > +#define NEED_IP(x) ((void) 0)
> > +#define NEED_OP(x) ((void) 0)
> > +#undef HAVE_TEST_IP
> > +#undef HAVE_ANY_OP
> > +
> > +#endif /* LZO1X_DECOMPRESS_SAFE */
>
> ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> variants in a common low-level __lzo1x_decompress kind of function
> definitely looks doable. The low-level function could simply take an extra
> argument (say, set by the _safe and _unsafe wrappers) that tells it
> whether it is being called as safe or unsafe ... helps us get rid of the
> disruptions to all the Makefiles above and these #ifdef's ugliness ...
I suspect it will probably damage performance unless the compiler is
very clever and I don't trust compilers that much...
> BTW, it'd be really cool if Richard and yourself could get together and
> pool your energies / efforts to develop a common / same patchset for this.
> (I wonder how different your implementations are, actually, and if there
> are any significant performance disparities, especially.) I really like your
> work, as it clears up the major gripe I had with Richard's patchset -- the
> ugliness (and monstrosity) of it. But he's also worked up the glue code for
> cryptoapi / jffs2 etc for this, so no point duplicating his efforts.
All I will add is that after the amendment I made, the ugliness in my
patchset is confined to one file now and I still think its the better
approach to take.
My main concerns with this patch are that:
* from the security point of view its not tried and tested code
* I'm not 100% confident in what Nitin has done with the code from a
buffer overflow/security PoV
* its not tested on many architectures
* the performance implications of the rewrite are unknown
In theory both sets of code should result in the output bytecode if the
compiler does its job properly. Ideally I'd like to compare the
performance of them as well as have a look at the code. I'm not quite
sure when I'm going to have time for this though :/.
Also, I did notice you had the error defines in two header files. They
should only exist in one place and the LZO implementation should be
including the copy in linux/.
Cheers,
Richard
On 5/24/07, Nitin Gupta <[email protected]> wrote:
> On 5/24/07, Satyam Sharma <[email protected]> wrote:
> > [...]
> > Just defining and exporting LZO1X_WORKMEM_SIZE may not be enough
> > to guarantee that users _will_ pass in workmem of size exactly that much.
> >
> > If this workmem is really merely a temp buffer required by lzo1x_compress(),
> > I'd suggest you rename lzo1x_compress() in lzo1x_compress.c to
> > __lzo1x_compress(), and implement a lzo1x_compress() wrapper for the
> > user that handles the allocation (and subsequent free'ing) of this temp
> > buffer itself.
> >
>
> I did not include such wrapper since allocation method will depend on
> particular scenario (like kmalloc vs. vmalloc and flags GFP_KERNEL vs
> GFP_ATOMIC etc...). But still maybe we can have "default" wrapper that
> does, say vmalloc(GFP_KERNEL)/vfree and let others with specific
> requirement have their own wrappers.
Actually, the problem with my recommendation (see Richard's response
on this thread too) is performance degradation, because we're
allocating / freeing memory on every compress() call -- so just ignore this
recommendation. But we can do better (see below) ...
> > [ I vaguely remember discussing something of this sort with Richard
> > when he had submitted his patchset too, perhaps you can look into
> > his implementation to see how he's managing this ... ]
> >
>
> ok.
Ok, I remember that discussion with Richard now. It was regarding the
JFFS2 glue code, actually. To avoid repeated allocation and free() of
the workspace memory, allocate a static global workspace of required
size for ourselves at module init time itself, and introduce a simple
spinlock to protect tht buffer and synchronize between concurrent calls
to lzo1x_compress(). There'd be no slowdown for single users of
lzo1x_compress(), but concurrent users (wonder how many there'd be)
would need to wait on the spinlock. You can consider a similar approach
for the /lib/lzo code too, if you want.
> > > diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> > > [...]
> > > +/* Macros for 'safe' decompression */
> > > +#ifdef LZO1X_DECOMPRESS_SAFE
> > > +
> > > +#define lzo1x_decompress lzo1x_decompress_safe
> > > +#define TEST_IP (ip < ip_end)
> > > +#define NEED_IP(x) \
> > > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > > +#define NEED_OP(x) \
> > > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > > +#define TEST_LB(m_pos) \
> > > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > > +#define HAVE_TEST_IP
> > > +#define HAVE_ANY_OP
> > > +
> > > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > > +
> > > +#define TEST_IP 1
> > > +#define TEST_LB(x) ((void) 0)
> > > +#define NEED_IP(x) ((void) 0)
> > > +#define NEED_OP(x) ((void) 0)
> > > +#undef HAVE_TEST_IP
> > > +#undef HAVE_ANY_OP
> > > +
> > > +#endif /* LZO1X_DECOMPRESS_SAFE */
> >
> > ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> > variants in a common low-level __lzo1x_decompress kind of function
> > definitely looks doable. The low-level function could simply take an extra
> > argument (say, set by the _safe and _unsafe wrappers) that tells it
> > whether it is being called as safe or unsafe ... helps us get rid of the
> > disruptions to all the Makefiles above and these #ifdef's ugliness ..
>
> Hmm..I will try to get this done.
Yes, like you said, both the versions have common macro's (defined
differently for the safe and unsafe cases) sprinkled in them. We can
take care of that by the following common definitions:
#define TEST_IP (!safe || (ip < ip_end))
#define NEED_IP(x) \
if (safe && ((size_t)(ip_end - ip) < (size_t)(x))) goto input_overrun
#define NEED_OP(x) \
if (safe && ((size_t)(op_end - op) < (size_t)(x))) goto output_overrun
#define TEST_LB(m_pos) \
if (safe && (m_pos < out || m_pos >= op)) goto lookbehind_overrun
In fact this makes the macros independent of SAFE or !SAFE compile
options, so you may simply even get rid of them altogether if you want ...
However, as Richard mentioned in his follow-up, this introduces a
condition test for even the _unsafe versions where there was previously
none because of the macros simply getting compiled away. Keeping
the safe test (the argument passed to the low-level function by the
_safe and _unsafe wrappers as 1 or 0) first in the condition would
definitely help, but if we're really bothered with even that performance
compromise (can do tests to find out how much), why not just go ahead
and duplicate those few lines of common code! Still beats the symlink
and Makefile "prepare" things.
> > BTW, it'd be really cool if Richard and yourself could get together and
> > pool your energies / efforts to develop a common / same patchset for this.
> > (I wonder how different your implementations are, actually, and if there
> > are any significant performance disparities, especially.) I really like your
> > work, as it clears up the major gripe I had with Richard's patchset -- the
> > ugliness (and monstrosity) of it.
>
> I am really looking forward to co-operating with Richard regarding
> this - although our approach for this porting is quite different but I
> hope we can get around this. Duplication sucks! :)
Yeah, hope you guys can come up with a single best version.
Satyam
Hi Richard,
On 5/24/07, Richard Purdie <[email protected]> wrote:
> On Thu, 2007-05-24 at 01:04 +0530, Satyam Sharma wrote:
> > On 5/23/07, Nitin Gupta <[email protected]> wrote:
> > > [...]
> > > +/* Macros for 'safe' decompression */
> > > +#ifdef LZO1X_DECOMPRESS_SAFE
> > > +
> > > +#define lzo1x_decompress lzo1x_decompress_safe
> > > +#define TEST_IP (ip < ip_end)
> > > +#define NEED_IP(x) \
> > > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > > +#define NEED_OP(x) \
> > > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > > +#define TEST_LB(m_pos) \
> > > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > > +#define HAVE_TEST_IP
> > > +#define HAVE_ANY_OP
> > > +
> > > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > > +
> > > +#define TEST_IP 1
> > > +#define TEST_LB(x) ((void) 0)
> > > +#define NEED_IP(x) ((void) 0)
> > > +#define NEED_OP(x) ((void) 0)
> > > +#undef HAVE_TEST_IP
> > > +#undef HAVE_ANY_OP
> > > +
> > > +#endif /* LZO1X_DECOMPRESS_SAFE */
> >
> > ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> > variants in a common low-level __lzo1x_decompress kind of function
> > definitely looks doable. The low-level function could simply take an extra
> > argument (say, set by the _safe and _unsafe wrappers) that tells it
> > whether it is being called as safe or unsafe ... helps us get rid of the
> > disruptions to all the Makefiles above and these #ifdef's ugliness ...
>
> I suspect it will probably damage performance unless the compiler is
> very clever and I don't trust compilers that much...
Hmm. The wrappers would clearly be inline, but if we want a common
low-level decompress function, we'd also need to introduce the "if (safe &&)"
kind of tests for those differently-defined macros which could impact
performance (for the _unsafe variant only, isn't it). By how much is the
question, and whether we really care to avoid duplicating 50 lines of code
to take that hit on the unsafe function (or vice versa).
> > BTW, it'd be really cool if Richard and yourself could get together and
> > pool your energies / efforts to develop a common / same patchset for this.
> > (I wonder how different your implementations are, actually, and if there
> > are any significant performance disparities, especially.) I really like your
> > work, as it clears up the major gripe I had with Richard's patchset -- the
> > ugliness (and monstrosity) of it. But he's also worked up the glue code for
> > cryptoapi / jffs2 etc for this, so no point duplicating his efforts.
>
> All I will add is that after the amendment I made, the ugliness in my
> patchset is confined to one file now and I still think its the better
> approach to take.
>
> My main concerns with this patch are that:
> * from the security point of view its not tried and tested code
> * I'm not 100% confident in what Nitin has done with the code from a
> buffer overflow/security PoV
> * its not tested on many architectures
Right, it needs testing (for correctness and robustness). But that
shouldn't be too difficult -- Nitin, you could just write up a simple test
module that others can use with your patch to do testing on their
arch's ... the more this gets tested, the better chances it's got.
> * the performance implications of the rewrite are unknown
>
> In theory both sets of code should result in the output bytecode if the
> compiler does its job properly. Ideally I'd like to compare the
> performance of them as well as have a look at the code. I'm not quite
> sure when I'm going to have time for this though :/.
Yes, performance disparities (if any) would be most important, IMO.
> Also, I did notice you had the error defines in two header files. They
> should only exist in one place and the LZO implementation should be
> including the copy in linux/.
Satyam
On 5/23/07, Bret Towe <[email protected]> wrote:
> On 5/23/07, Nitin Gupta <[email protected]> wrote:
> > For now, tested on x86 only.
>
> If you have a program to test this I can run it on an amd64 and a g4 ppc
>
Attached is the kernel module (compress-test) to test this LZO code.
Just compile this module against 2.6.22-rc2 with this LZO patch. Then
testing can be done as:
1- Mount DebugFS somewhere e.g:
mkdir /debug; mount -t debugfs debugfs /debug
2- Load the module and do:
cat /path/to/some_file > /debug/compress_test/compress
(/var/log/messages should show that compression was successful)
3- Then decompress this file as:
cat /debug/compress_test/decompress > /tmp/t
(/var/log/messages should show that decompression was successful)
4- For extra verification do:
diff /tmp/t /path/to/some_file -- O/P must be empty
Thanks!
Nitin
On 5/24/07, Richard Purdie <[email protected]> wrote:
> On Thu, 2007-05-24 at 01:04 +0530, Satyam Sharma wrote:
> > On 5/23/07, Nitin Gupta <[email protected]> wrote:
>
<snip>
> I remember this being mentioned. My answer was that this is the same
> behaviour as the zlib library and you do not want to alloc/free this
> memory every time you have a piece of data to compress as it will
> totally cripple performance. This allocation of buffers is a standard
> part of the crypto and jffs2 compression APIs too.
>
This is why there are no wrappers for this LZO -- in compressed
caching also we have wrappers that take care of this. I don't think
anyone will want to alloc/free for every compression they do. So I
am just going to leave code without wrappers.
> > I just read the follow-ups to this, so perhaps we /can/ use the unsafe
> > versions in certain situations. But I agree with Michael's suggestion
> > to rename _safe to decompress and decompress to _unsafe ...
>
> Lets just add the _unsafe postfix and leave "safe" alone, then it
> remains the same name as userspace and will be less confusing for anyone
> used to the userspace library ;-).
Ok - will do this :)
>
> > Hmmm, perhaps you could extract the common stuff between the
> > _safe and _unsafe versions out into a separate function and then
> > reuse it from _safe and _unsafe wrappers? In any case, this kind
> > of Makefile jugglery (even in the master Makefile) just to avoid the
> > above doesn't seem quite right ...
>
> FWIW, I don't like the symlink much either. My version of the patch
> doesn't do things that way.
You have duplicated decompress code twice! Although this will do away
with symlink but I was wondering if a symlink is really that bad!
> > > diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> > > [...]
> > > +/* Macros for 'safe' decompression */
> > > +#ifdef LZO1X_DECOMPRESS_SAFE
> > > +
> > > +#define lzo1x_decompress lzo1x_decompress_safe
> > > +#define TEST_IP (ip < ip_end)
> > > +#define NEED_IP(x) \
> > > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > > +#define NEED_OP(x) \
> > > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > > +#define TEST_LB(m_pos) \
> > > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > > +#define HAVE_TEST_IP
> > > +#define HAVE_ANY_OP
> > > +
> > > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > > +
> > > +#define TEST_IP 1
> > > +#define TEST_LB(x) ((void) 0)
> > > +#define NEED_IP(x) ((void) 0)
> > > +#define NEED_OP(x) ((void) 0)
> > > +#undef HAVE_TEST_IP
> > > +#undef HAVE_ANY_OP
> > > +
> > > +#endif /* LZO1X_DECOMPRESS_SAFE */
> >
> > ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> > variants in a common low-level __lzo1x_decompress kind of function
> > definitely looks doable. The low-level function could simply take an extra
> > argument (say, set by the _safe and _unsafe wrappers) that tells it
> > whether it is being called as safe or unsafe ... helps us get rid of the
> > disruptions to all the Makefiles above and these #ifdef's ugliness ...
>
> I suspect it will probably damage performance unless the compiler is
> very clever and I don't trust compilers that much...
>
+1. I looked into Satyam suggestion as above but ...yes, we should not
leave everything to compiler. And since all this was suggested just
to do away with that symlink, I don't think this splitting work is
worth the effort.
> > BTW, it'd be really cool if Richard and yourself could get together and
> > pool your energies / efforts to develop a common / same patchset for this.
> > (I wonder how different your implementations are, actually, and if there
> > are any significant performance disparities, especially.) I really like your
> > work, as it clears up the major gripe I had with Richard's patchset -- the
> > ugliness (and monstrosity) of it. But he's also worked up the glue code for
> > cryptoapi / jffs2 etc for this, so no point duplicating his efforts.
>
> All I will add is that after the amendment I made, the ugliness in my
> patchset is confined to one file now and I still think its the better
> approach to take.
>
> My main concerns with this patch are that:
> * from the security point of view its not tried and tested code
> * I'm not 100% confident in what Nitin has done with the code from a
> buffer overflow/security PoV
> * its not tested on many architectures
> * the performance implications of the rewrite are unknown
>
I agree with your points - there can surely be bugs in my porting work
since it involves too many chages. But considering that the port is
just ~500 lines, if we can fix it and optimize to get
comparable/better perf. results than original one, we will end up with
much cleaner and smaller code.
For rigous testing, I have sent 'compress-test' module (with usage) to
Bret Towe who has 64-bit machines available for testing.
> In theory both sets of code should result in the output bytecode if the
> compiler does its job properly. Ideally I'd like to compare the
> performance of them as well as have a look at the code. I'm not quite
> sure when I'm going to have time for this though :/.
>
> Also, I did notice you had the error defines in two header files. They
> should only exist in one place and the LZO implementation should be
> including the copy in linux/.
>
Ah! I now notice them -- will keep the copy in linux/lzo1x.h only.
Thanks for your comments.
- Nitin
On 5/24/07, Satyam Sharma <[email protected]> wrote:
> Hmm. The wrappers would clearly be inline, but if we want a common
> low-level decompress function, we'd also need to introduce the "if (safe &&)"
> kind of tests for those differently-defined macros which could impact
> performance (for the _unsafe variant only, isn't it). By how much is the
> question, and whether we really care to avoid duplicating 50 lines of code
> to take that hit on the unsafe function (or vice versa).
All this just to avoid that symlink? What is so wrong with that? Yes,
the ugliest thing is some additions to top-level Makefile but I think
this the reason those prepare{1,2,3....} targets were meant for.
> > All I will add is that after the amendment I made, the ugliness in my
> > patchset is confined to one file now and I still think its the better
> > approach to take.
> >
> > My main concerns with this patch are that:
> > * from the security point of view its not tried and tested code
> > * I'm not 100% confident in what Nitin has done with the code from a
> > buffer overflow/security PoV
> > * its not tested on many architectures
> > * the performance implications of the rewrite are unknown
>
> Right, it needs testing (for correctness and robustness). But that
> shouldn't be too difficult -- Nitin, you could just write up a simple test
> module that others can use with your patch to do testing on their
> arch's ... the more this gets tested, the better chances it's got.
>
Mailed 'compressed-test' module along with usage to Bret (CC'ed to
you, Richard, linux-kernel). This makes it very easy to test this LZO
code.
Thanks for comments.
- Nitin
On 5/24/07, Nitin Gupta <[email protected]> wrote:
> On 5/24/07, Satyam Sharma <[email protected]> wrote:
> > Hmm. The wrappers would clearly be inline, but if we want a common
> > low-level decompress function, we'd also need to introduce the "if (safe &&)"
> > kind of tests for those differently-defined macros which could impact
> > performance (for the _unsafe variant only, isn't it). By how much is the
> > question, and whether we really care to avoid duplicating 50 lines of code
> > to take that hit on the unsafe function (or vice versa).
>
> All this just to avoid that symlink?
Oh, yes. And also to avoid the changes to the master Makefile,
and the extra stuff in the other Makefile. And you'd even rid
yourself of some #ifdef's in the actual code. Too many upsides!
> What is so wrong with that?
We never required this kind of thing before, why now? Also note
that it requires all the extra stuff mentioned above ... why not do
away with all that too.
On 5/24/07, Nitin Gupta <[email protected]> wrote:
> [...]
> > > > diff --git a/lib/lzo1x/lzo1x_int.h b/lib/lzo1x/lzo1x_int.h
> > > > [...]
> > > > +/* Macros for 'safe' decompression */
> > > > +#ifdef LZO1X_DECOMPRESS_SAFE
> > > > +
> > > > +#define lzo1x_decompress lzo1x_decompress_safe
> > > > +#define TEST_IP (ip < ip_end)
> > > > +#define NEED_IP(x) \
> > > > + if ((size_t)(ip_end - ip) < (size_t)(x)) goto input_overrun
> > > > +#define NEED_OP(x) \
> > > > + if ((size_t)(op_end - op) < (size_t)(x)) goto output_overrun
> > > > +#define TEST_LB(m_pos) \
> > > > + if (m_pos < out || m_pos >= op) goto lookbehind_overrun
> > > > +#define HAVE_TEST_IP
> > > > +#define HAVE_ANY_OP
> > > > +
> > > > +#else /* !LZO1X_DECOMPRESS_SAFE */
> > > > +
> > > > +#define TEST_IP 1
> > > > +#define TEST_LB(x) ((void) 0)
> > > > +#define NEED_IP(x) ((void) 0)
> > > > +#define NEED_OP(x) ((void) 0)
> > > > +#undef HAVE_TEST_IP
> > > > +#undef HAVE_ANY_OP
> > > > +
> > > > +#endif /* LZO1X_DECOMPRESS_SAFE */
> > >
> > > ... ugh. Yes, extracting the common stuff between the _safe and _unsafe
> > > variants in a common low-level __lzo1x_decompress kind of function
> > > definitely looks doable. The low-level function could simply take an extra
> > > argument (say, set by the _safe and _unsafe wrappers) that tells it
> > > whether it is being called as safe or unsafe ... helps us get rid of the
> > > disruptions to all the Makefiles above and these #ifdef's ugliness ...
> >
> > I suspect it will probably damage performance unless the compiler is
> > very clever and I don't trust compilers that much...
>
> +1. I looked into Satyam suggestion as above but ...yes, we should not
> leave everything to compiler. And since all this was suggested just
> to do away with that symlink, I don't think this splitting work is
> worth the effort.
Not just the symlink ... we get rid of the changes in the two Makefiles,
the -D...SAFE stuff, some #ifdef's _and_ the macros listed above. Code
becomes even smaller and simpler. But yes, as I said, there'd be an
extra condition tested by the _unsafe variant (and *only* the _unsafe
variant, I must add) at the locations of these macros that was compiled
away previously. As for performance hit, I'd be interested in actually
measuring it first ... I definitely wouldn't mind trading off a couple of %
for a simpler and smaller patch.
But if you don't want even _that_ performance hit, you could also
simply duplicate the decompress() like Richard has done.
> For rigous testing, I have sent 'compress-test' module (with usage) to
> Bret Towe who has 64-bit machines available for testing.
This test module isn't so performance benchmarking friendly, good
enough for checking correctness of the algorithm implementation and
robustness of the code. But I think Richard's cryptoapi glue code patch
would work for your version too, as both your interfaces are the same,
so that'd be a better way to benchmark the relative performance of
your patch vs his. If you can test/benchmark both your versions and
produce results that beat his code, you've made it :-)
On Wed, 2007-05-23 at 15:33 +0100, Michael-Luke Jones wrote:
> On 23 May 2007, at 15:21, Nitin Gupta wrote:
>
> > If somebody is up to including compression he must be having head
> > to use the right
> > decompress version depending on this scenario :-)
>
> By that logic, experienced kernel dev Richard Purdie is not up to
> using compression (?!)
>
> To me, it looks like an easy trap to fall into. And one that an
> experienced dev *has* just fallen in to.
To be fair, I just altered resier4 to use the library functions and it
was someone else who chose to use the "unsafe" version. I did flag this
up on LKML when I saw it and the resier4 people are considering
changing.
I've since promised to send a patch changing it to use the safe version.
I'll not send a "rename to unsafe" patch for the LZO core until Andrew
decides whether to drop the unsafe version entirely or not as per your
patch. If he doesn't due to the potential use by the compressed cache
people, I will send that patch.
Cheers,
Richard
On Thu, 24 May 2007 23:41:22 +0100
Richard Purdie <[email protected]> wrote:
> I'll not send a "rename to unsafe" patch for the LZO core until Andrew
> decides whether to drop the unsafe version entirely or not as per your
> patch. If he doesn't due to the potential use by the compressed cache
> people, I will send that patch.
I'd have thought that a 3% performance difference isn't worth worrying
about. Especially when reclaiming that 3% costs an additional 500 lines
of pretty yukky code.
On Thu, 2007-05-24 at 15:54 -0700, Andrew Morton wrote:
> On Thu, 24 May 2007 23:41:22 +0100
> Richard Purdie <[email protected]> wrote:
>
> > I'll not send a "rename to unsafe" patch for the LZO core until Andrew
> > decides whether to drop the unsafe version entirely or not as per your
> > patch. If he doesn't due to the potential use by the compressed cache
> > people, I will send that patch.
>
> I'd have thought that a 3% performance difference isn't worth worrying
> about. Especially when reclaiming that 3% costs an additional 500 lines
> of pretty yukky code.
7% since the 3% applied to code that was over twice as slow in the first
place!
Richard
On 5/24/07, Nitin Gupta <[email protected]> wrote:
> On 5/23/07, Bret Towe <[email protected]> wrote:
> > On 5/23/07, Nitin Gupta <[email protected]> wrote:
>
> > > For now, tested on x86 only.
> >
> > If you have a program to test this I can run it on an amd64 and a g4 ppc
> >
>
> Attached is the kernel module (compress-test) to test this LZO code.
> Just compile this module against 2.6.22-rc2 with this LZO patch. Then
> testing can be done as:
> 1- Mount DebugFS somewhere e.g:
> mkdir /debug; mount -t debugfs debugfs /debug
> 2- Load the module and do:
> cat /path/to/some_file > /debug/compress_test/compress
> (/var/log/messages should show that compression was successful)
> 3- Then decompress this file as:
> cat /debug/compress_test/decompress > /tmp/t
> (/var/log/messages should show that decompression was successful)
> 4- For extra verification do:
> diff /tmp/t /path/to/some_file -- O/P must be empty
>
>
> Thanks!
> Nitin
>
>
the test worked fine on amd64
from dmesg:
LZO compress successful: orig_size=17448, comp_size=8183
LZO decompress successful: decomp_size=17448
and input and output files I gave it:
sha1sum test-input output
2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
2221c586e3eb869af7f4333d4f56b441b9aa8414 output
(will be giving the ppc box the same file to test btw when I get to it)
and I don't know if it matters much but I tried feeding it a 260k file
and it didn't like it
cat /usr/bin/yelp > /debug/compress_test/compress
cat: write error: No space left on device
On 5/25/07, Bret Towe <[email protected]> wrote:
> On 5/24/07, Nitin Gupta <[email protected]> wrote:
> > On 5/23/07, Bret Towe <[email protected]> wrote:
> > > On 5/23/07, Nitin Gupta <[email protected]> wrote:
> >
> > > > For now, tested on x86 only.
> > >
> > > If you have a program to test this I can run it on an amd64 and a g4 ppc
> > >
> >
> > Attached is the kernel module (compress-test) to test this LZO code.
> > Just compile this module against 2.6.22-rc2 with this LZO patch. Then
> > testing can be done as:
> > 1- Mount DebugFS somewhere e.g:
> > mkdir /debug; mount -t debugfs debugfs /debug
> > 2- Load the module and do:
> > cat /path/to/some_file > /debug/compress_test/compress
> > (/var/log/messages should show that compression was successful)
> > 3- Then decompress this file as:
> > cat /debug/compress_test/decompress > /tmp/t
> > (/var/log/messages should show that decompression was successful)
> > 4- For extra verification do:
> > diff /tmp/t /path/to/some_file -- O/P must be empty
> >
> >
>
> the test worked fine on amd64
> from dmesg:
> LZO compress successful: orig_size=17448, comp_size=8183
> LZO decompress successful: decomp_size=17448
>
> and input and output files I gave it:
> sha1sum test-input output
> 2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
> 2221c586e3eb869af7f4333d4f56b441b9aa8414 output
>
Good to know it worked correctly on 64-bit system too. I will also
add exporting benchmarking figures soon.
> (will be giving the ppc box the same file to test btw when I get to it)
>
> and I don't know if it matters much but I tried feeding it a 260k file
> and it didn't like it
>
> cat /usr/bin/yelp > /debug/compress_test/compress
> cat: write error: No space left on device
>
Ah! I forgot to mention that max file size to feed is 256K (this was
just for simplicity of compress-test module implementation).
Thanks for your testing.
- Nitin
On 5/24/07, Nitin Gupta <[email protected]> wrote:
> On 5/25/07, Bret Towe <[email protected]> wrote:
> > On 5/24/07, Nitin Gupta <[email protected]> wrote:
> > > On 5/23/07, Bret Towe <[email protected]> wrote:
> > > > On 5/23/07, Nitin Gupta <[email protected]> wrote:
> > >
> > > > > For now, tested on x86 only.
> > > >
> > > > If you have a program to test this I can run it on an amd64 and a g4 ppc
> > > >
> > >
> > > Attached is the kernel module (compress-test) to test this LZO code.
> > > Just compile this module against 2.6.22-rc2 with this LZO patch. Then
> > > testing can be done as:
> > > 1- Mount DebugFS somewhere e.g:
> > > mkdir /debug; mount -t debugfs debugfs /debug
> > > 2- Load the module and do:
> > > cat /path/to/some_file > /debug/compress_test/compress
> > > (/var/log/messages should show that compression was successful)
> > > 3- Then decompress this file as:
> > > cat /debug/compress_test/decompress > /tmp/t
> > > (/var/log/messages should show that decompression was successful)
> > > 4- For extra verification do:
> > > diff /tmp/t /path/to/some_file -- O/P must be empty
> > >
> > >
> >
> > the test worked fine on amd64
> > from dmesg:
> > LZO compress successful: orig_size=17448, comp_size=8183
> > LZO decompress successful: decomp_size=17448
> >
> > and input and output files I gave it:
> > sha1sum test-input output
> > 2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
> > 2221c586e3eb869af7f4333d4f56b441b9aa8414 output
> >
>
> Good to know it worked correctly on 64-bit system too. I will also
> add exporting benchmarking figures soon.
>
> > (will be giving the ppc box the same file to test btw when I get to it)
[ 237.556167] LZO compress successful: orig_size=17448, comp_size=8183
[ 253.320760] LZO decompress successful: decomp_size=17448
2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
2e6c96b687274b629308b29835cebd3af989e0c7 output
ppc however seems bust
the computer is a g4 mini
> > and I don't know if it matters much but I tried feeding it a 260k file
> > and it didn't like it
> >
> > cat /usr/bin/yelp > /debug/compress_test/compress
> > cat: write error: No space left on device
> >
>
> Ah! I forgot to mention that max file size to feed is 256K (this was
> just for simplicity of compress-test module implementation).
figured it might be something like that
> Thanks for your testing.
no problem
> - Nitin
>
On 5/25/07, Bret Towe <[email protected]> wrote:
> On 5/24/07, Nitin Gupta <[email protected]> wrote:
> > On 5/25/07, Bret Towe <[email protected]> wrote:
> > > On 5/24/07, Nitin Gupta <[email protected]> wrote:
> > > > On 5/23/07, Bret Towe <[email protected]> wrote:
> > > > > On 5/23/07, Nitin Gupta <[email protected]> wrote:
>
> [ 237.556167] LZO compress successful: orig_size=17448, comp_size=8183
> [ 253.320760] LZO decompress successful: decomp_size=17448
>
> 2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
> 2e6c96b687274b629308b29835cebd3af989e0c7 output
>
> ppc however seems bust
> the computer is a g4 mini
Since lzo1x_decompress() itself is saying that decompression was
successful, it is really strange to have different sha-sums. It seems
that it's the fault with compress-test module itself. I will look more
closely into this and reply back.
Thanks,
Nitin
Hi!
> Perhaps you have opinion of maintaining diffability with
> original LZO
> code which differs from mine. Since the code is now just
> ~500 lines it
> should be fair enough to have major overhauls for sake
> of clean
> KernelStyle(tm) code. It shouldn't be that hard to
> verify this small
> code for bugs that might have crept in during porting
> work. As regard
> to keeping up with future LZO versions, hm.... that will
> be hard - but
> I don't think algorithm itself will change and
> optimizations can
> always be done separately in this fork.
>
> >
> >> I'd agree with the proposed renaming. In fact I'd
> >suggest that the unsafe
> >> APIs just be removed - it's hard to imagine a
> >situation in which they're OK
> >> to be used in the kernel.
> >
> >The compressed cache code might be one exception since
> >it does the
> >compression itself and shouldn't get corrupted. If it
> >does get
> >corrupted, you have bigger problems.
> >
>
> Yes. Compressed Caching is one of cases where compressed
> data cannot
> get magically corrupted. Hence, there is no need to go
> for the 'safe'
> version. There might be other such cases too, so
> removing 'unsafe'
> version is not good.
What is the performance difference between safe and unsafe version?
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
On 25 May 2007, at 11:42, Pavel Machek wrote:
> What is the performance difference between safe and unsafe version?
On 24 May 2007, at 23:26, Richard Purdie wrote:
> For my minilzo kernel patch, the safe version showed a 7.2%
> performance
> hit.
The conclusion seemed to be that we should drop the 'unsafe' version
on this basis.
Michael-Luke
Hi Pavel,
Just did some benchmarking; results below.
On 5/25/07, Pavel Machek <[email protected]> wrote:
>
> What is the performance difference between safe and unsafe version?
>
File size: 256K
- Following as tests for original test code - not any kernel port of this.
- Test with each block size repeated 5 times - taken avg. of these 5 runs.
- Same file used for each test.
- Used lzotest utility (included with LZO 2.02) for testing.
Blocksize Comp* DU* DS* Speed%
4 59.356 211.526 195.260 7.689
8 54.623 202.712 188.369 7.075
16 50.342 196.482 183.988 6.358
32 47.499 189.800 177.455 6.504
64 44.148 178.724 167.201 6.447
128 42.125 170.229 159.257 6.445
256 41.830 155.035 146.115 5.753
* All speeds in MB/sec
Comp = LZO1X-1
DU = Decompress (unsafe)
DS = Decompress (safe)
Speed% = ((DU-DS)/DU)*100
I have yet to see how the kernel ports compare against this original version.
Cheers,
Nitin
Hi Bret,
On 5/25/07, Bret Towe <[email protected]> wrote:
>
> [ 237.556167] LZO compress successful: orig_size=17448, comp_size=8183
> [ 253.320760] LZO decompress successful: decomp_size=17448
>
> 2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
> 2e6c96b687274b629308b29835cebd3af989e0c7 output
>
> ppc however seems bust
> the computer is a g4 mini
>
Can you please test the 'take 4' version on ppc?
Just one line change: Please replace call to lzo1x_decompress_safe()
to lzo1x_decompress() in compress-test module.
Thanks,
Nitin
On 5/26/07, Nitin Gupta <[email protected]> wrote:
> Hi Bret,
>
> On 5/25/07, Bret Towe <[email protected]> wrote:
> >
> > [ 237.556167] LZO compress successful: orig_size=17448, comp_size=8183
> > [ 253.320760] LZO decompress successful: decomp_size=17448
> >
> > 2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
> > 2e6c96b687274b629308b29835cebd3af989e0c7 output
> >
> > ppc however seems bust
> > the computer is a g4 mini
> >
>
> Can you please test the 'take 4' version on ppc?
> Just one line change: Please replace call to lzo1x_decompress_safe()
> to lzo1x_decompress() in compress-test module.
>
> Thanks,
> Nitin
results from take 4
dmesg:
[ 1944.508280] LZO compress successful: orig_size=17448, comp_size=8183
[ 1952.098677] LZO decompress successful: decomp_size=17448
root@mini:~# sha1sum /home/bret/test-input output
2221c586e3eb869af7f4333d4f56b441b9aa8414 test-input
2221c586e3eb869af7f4333d4f56b441b9aa8414 output
If you need more testing let me know