aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig9
-rw-r--r--lib/Kconfig.debug3
-rw-r--r--lib/Makefile10
-rw-r--r--lib/average.c61
-rw-r--r--lib/decompress.c5
-rw-r--r--lib/decompress_bunzip2.c8
-rw-r--r--lib/decompress_inflate.c23
-rw-r--r--lib/decompress_unlzma.c85
-rw-r--r--lib/decompress_unlzo.c105
-rw-r--r--lib/decompress_unxz.c397
-rw-r--r--lib/dynamic_debug.c9
-rw-r--r--lib/flex_array.c10
-rw-r--r--lib/hexdump.c18
-rw-r--r--lib/kref.c30
-rw-r--r--lib/nlattr.c22
-rw-r--r--lib/percpu_counter.c8
-rw-r--r--lib/timerqueue.c107
-rw-r--r--lib/vsprintf.c38
-rw-r--r--lib/xz/Kconfig59
-rw-r--r--lib/xz/Makefile5
-rw-r--r--lib/xz/xz_crc32.c59
-rw-r--r--lib/xz/xz_dec_bcj.c561
-rw-r--r--lib/xz/xz_dec_lzma2.c1171
-rw-r--r--lib/xz/xz_dec_stream.c821
-rw-r--r--lib/xz/xz_dec_syms.c26
-rw-r--r--lib/xz/xz_dec_test.c220
-rw-r--r--lib/xz/xz_lzma2.h204
-rw-r--r--lib/xz/xz_private.h156
-rw-r--r--lib/xz/xz_stream.h62
29 files changed, 4194 insertions, 98 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index fa9bf2c0619..0ee67e08ad3 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -106,6 +106,8 @@ config LZO_COMPRESS
config LZO_DECOMPRESS
tristate
+source "lib/xz/Kconfig"
+
#
# These all provide a common interface (hence the apparent duplication with
# ZLIB_INFLATE; DECOMPRESS_GZIP is just a wrapper.)
@@ -120,6 +122,10 @@ config DECOMPRESS_BZIP2
config DECOMPRESS_LZMA
tristate
+config DECOMPRESS_XZ
+ select XZ_DEC
+ tristate
+
config DECOMPRESS_LZO
select LZO_DECOMPRESS
tristate
@@ -210,4 +216,7 @@ config GENERIC_ATOMIC64
config LRU_CACHE
tristate
+config AVERAGE
+ bool
+
endmenu
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 28b42b9274d..2d05adb9840 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -173,7 +173,8 @@ config LOCKUP_DETECTOR
An NMI is generated every 60 seconds or so to check for hardlockups.
config HARDLOCKUP_DETECTOR
- def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI
+ def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \
+ !ARCH_HAS_NMI_WATCHDOG
config BOOTPARAM_SOFTLOCKUP_PANIC
bool "Panic (Reboot) On Soft Lockups"
diff --git a/lib/Makefile b/lib/Makefile
index e6a3763b821..cbb774f7d41 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -8,11 +8,11 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS))
endif
lib-y := ctype.o string.o vsprintf.o cmdline.o \
- rbtree.o radix-tree.o dump_stack.o \
+ rbtree.o radix-tree.o dump_stack.o timerqueue.o\
idr.o int_sqrt.o extable.o prio_tree.o \
sha1.o irq_regs.o reciprocal_div.o argv_split.o \
proportions.o prio_heap.o ratelimit.o show_mem.o \
- is_single_threaded.o plist.o decompress.o flex_array.o
+ is_single_threaded.o plist.o decompress.o
lib-$(CONFIG_MMU) += ioremap.o
lib-$(CONFIG_SMP) += cpumask.o
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- string_helpers.o gcd.o lcm.o list_sort.o uuid.o
+ string_helpers.o gcd.o lcm.o list_sort.o uuid.o flex_array.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
@@ -69,11 +69,13 @@ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
obj-$(CONFIG_LZO_COMPRESS) += lzo/
obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
+obj-$(CONFIG_XZ_DEC) += xz/
obj-$(CONFIG_RAID6_PQ) += raid6/
lib-$(CONFIG_DECOMPRESS_GZIP) += decompress_inflate.o
lib-$(CONFIG_DECOMPRESS_BZIP2) += decompress_bunzip2.o
lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o
+lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o
lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o
obj-$(CONFIG_TEXTSEARCH) += textsearch.o
@@ -106,6 +108,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o
obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o
+obj-$(CONFIG_AVERAGE) += average.o
+
hostprogs-y := gen_crc32table
clean-files := crc32table.h
diff --git a/lib/average.c b/lib/average.c
new file mode 100644
index 00000000000..5576c284149
--- /dev/null
+++ b/lib/average.c
@@ -0,0 +1,61 @@
+/*
+ * lib/average.c
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2. See the file COPYING for more details.
+ */
+
+#include <linux/module.h>
+#include <linux/average.h>
+#include <linux/bug.h>
+#include <linux/log2.h>
+
+/**
+ * DOC: Exponentially Weighted Moving Average (EWMA)
+ *
+ * These are generic functions for calculating Exponentially Weighted Moving
+ * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled
+ * up internal representation of the average value to prevent rounding errors.
+ * The factor for scaling up and the exponential weight (or decay rate) have to
+ * be specified thru the init fuction. The structure should not be accessed
+ * directly but only thru the helper functions.
+ */
+
+/**
+ * ewma_init() - Initialize EWMA parameters
+ * @avg: Average structure
+ * @factor: Factor to use for the scaled up internal value. The maximum value
+ * of averages can be ULONG_MAX/(factor*weight). For performance reasons
+ * factor has to be a power of 2.
+ * @weight: Exponential weight, or decay rate. This defines how fast the
+ * influence of older values decreases. For performance reasons weight has
+ * to be a power of 2.
+ *
+ * Initialize the EWMA parameters for a given struct ewma @avg.
+ */
+void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
+{
+ WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor));
+
+ avg->weight = ilog2(weight);
+ avg->factor = ilog2(factor);
+ avg->internal = 0;
+}
+EXPORT_SYMBOL(ewma_init);
+
+/**
+ * ewma_add() - Exponentially weighted moving average (EWMA)
+ * @avg: Average structure
+ * @val: Current value
+ *
+ * Add a sample to the average.
+ */
+struct ewma *ewma_add(struct ewma *avg, unsigned long val)
+{
+ avg->internal = avg->internal ?
+ (((avg->internal << avg->weight) - avg->internal) +
+ (val << avg->factor)) >> avg->weight :
+ (val << avg->factor);
+ return avg;
+}
+EXPORT_SYMBOL(ewma_add);
diff --git a/lib/decompress.c b/lib/decompress.c
index a7606815541..3d766b7f60a 100644
--- a/lib/decompress.c
+++ b/lib/decompress.c
@@ -8,6 +8,7 @@
#include <linux/decompress/bunzip2.h>
#include <linux/decompress/unlzma.h>
+#include <linux/decompress/unxz.h>
#include <linux/decompress/inflate.h>
#include <linux/decompress/unlzo.h>
@@ -23,6 +24,9 @@
#ifndef CONFIG_DECOMPRESS_LZMA
# define unlzma NULL
#endif
+#ifndef CONFIG_DECOMPRESS_XZ
+# define unxz NULL
+#endif
#ifndef CONFIG_DECOMPRESS_LZO
# define unlzo NULL
#endif
@@ -36,6 +40,7 @@ static const struct compress_format {
{ {037, 0236}, "gzip", gunzip },
{ {0x42, 0x5a}, "bzip2", bunzip2 },
{ {0x5d, 0x00}, "lzma", unlzma },
+ { {0xfd, 0x37}, "xz", unxz },
{ {0x89, 0x4c}, "lzo", unlzo },
{ {0, 0}, NULL, NULL }
};
diff --git a/lib/decompress_bunzip2.c b/lib/decompress_bunzip2.c
index 81c8bb1cc6a..a7b80c1d6a0 100644
--- a/lib/decompress_bunzip2.c
+++ b/lib/decompress_bunzip2.c
@@ -49,7 +49,6 @@
#define PREBOOT
#else
#include <linux/decompress/bunzip2.h>
-#include <linux/slab.h>
#endif /* STATIC */
#include <linux/decompress/mm.h>
@@ -682,13 +681,12 @@ STATIC int INIT bunzip2(unsigned char *buf, int len,
int(*flush)(void*, unsigned int),
unsigned char *outbuf,
int *pos,
- void(*error_fn)(char *x))
+ void(*error)(char *x))
{
struct bunzip_data *bd;
int i = -1;
unsigned char *inbuf;
- set_error_fn(error_fn);
if (flush)
outbuf = malloc(BZIP2_IOBUF_SIZE);
@@ -751,8 +749,8 @@ STATIC int INIT decompress(unsigned char *buf, int len,
int(*flush)(void*, unsigned int),
unsigned char *outbuf,
int *pos,
- void(*error_fn)(char *x))
+ void(*error)(char *x))
{
- return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error_fn);
+ return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error);
}
#endif
diff --git a/lib/decompress_inflate.c b/lib/decompress_inflate.c
index fc686c7a0a0..19ff89e34ee 100644
--- a/lib/decompress_inflate.c
+++ b/lib/decompress_inflate.c
@@ -19,7 +19,6 @@
#include "zlib_inflate/inflate.h"
#include "zlib_inflate/infutil.h"
-#include <linux/slab.h>
#endif /* STATIC */
@@ -27,7 +26,7 @@
#define GZIP_IOBUF_SIZE (16*1024)
-static int nofill(void *buffer, unsigned int len)
+static int INIT nofill(void *buffer, unsigned int len)
{
return -1;
}
@@ -38,13 +37,12 @@ STATIC int INIT gunzip(unsigned char *buf, int len,
int(*flush)(void*, unsigned int),
unsigned char *out_buf,
int *pos,
- void(*error_fn)(char *x)) {
+ void(*error)(char *x)) {
u8 *zbuf;
struct z_stream_s *strm;
int rc;
size_t out_len;
- set_error_fn(error_fn);
rc = -1;
if (flush) {
out_len = 0x8000; /* 32 K */
@@ -100,13 +98,22 @@ STATIC int INIT gunzip(unsigned char *buf, int len,
* possible asciz filename)
*/
strm->next_in = zbuf + 10;
+ strm->avail_in = len - 10;
/* skip over asciz filename */
if (zbuf[3] & 0x8) {
- while (strm->next_in[0])
- strm->next_in++;
- strm->next_in++;
+ do {
+ /*
+ * If the filename doesn't fit into the buffer,
+ * the file is very probably corrupt. Don't try
+ * to read more data.
+ */
+ if (strm->avail_in == 0) {
+ error("header error");
+ goto gunzip_5;
+ }
+ --strm->avail_in;
+ } while (*strm->next_in++);
}
- strm->avail_in = len - (strm->next_in - zbuf);
strm->next_out = out_buf;
strm->avail_out = out_len;
diff --git a/lib/decompress_unlzma.c b/lib/decompress_unlzma.c
index ca82fde81c8..476c65af970 100644
--- a/lib/decompress_unlzma.c
+++ b/lib/decompress_unlzma.c
@@ -33,7 +33,6 @@
#define PREBOOT
#else
#include <linux/decompress/unlzma.h>
-#include <linux/slab.h>
#endif /* STATIC */
#include <linux/decompress/mm.h>
@@ -74,6 +73,7 @@ struct rc {
uint32_t code;
uint32_t range;
uint32_t bound;
+ void (*error)(char *);
};
@@ -82,7 +82,7 @@ struct rc {
#define RC_MODEL_TOTAL_BITS 11
-static int nofill(void *buffer, unsigned int len)
+static int INIT nofill(void *buffer, unsigned int len)
{
return -1;
}
@@ -92,7 +92,7 @@ static void INIT rc_read(struct rc *rc)
{
rc->buffer_size = rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);
if (rc->buffer_size <= 0)
- error("unexpected EOF");
+ rc->error("unexpected EOF");
rc->ptr = rc->buffer;
rc->buffer_end = rc->buffer + rc->buffer_size;
}
@@ -127,12 +127,6 @@ static inline void INIT rc_init_code(struct rc *rc)
}
-/* Called once. TODO: bb_maybe_free() */
-static inline void INIT rc_free(struct rc *rc)
-{
- free(rc->buffer);
-}
-
/* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */
static void INIT rc_do_normalize(struct rc *rc)
{
@@ -169,7 +163,7 @@ static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p)
rc->range = rc->bound;
*p += ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;
}
-static inline void rc_update_bit_1(struct rc *rc, uint16_t *p)
+static inline void INIT rc_update_bit_1(struct rc *rc, uint16_t *p)
{
rc->range -= rc->bound;
rc->code -= rc->bound;
@@ -319,32 +313,38 @@ static inline uint8_t INIT peek_old_byte(struct writer *wr,
}
-static inline void INIT write_byte(struct writer *wr, uint8_t byte)
+static inline int INIT write_byte(struct writer *wr, uint8_t byte)
{
wr->buffer[wr->buffer_pos++] = wr->previous_byte = byte;
if (wr->flush && wr->buffer_pos == wr->header->dict_size) {
wr->buffer_pos = 0;
wr->global_pos += wr->header->dict_size;
- wr->flush((char *)wr->buffer, wr->header->dict_size);
+ if (wr->flush((char *)wr->buffer, wr->header->dict_size)
+ != wr->header->dict_size)
+ return -1;
}
+ return 0;
}
-static inline void INIT copy_byte(struct writer *wr, uint32_t offs)
+static inline int INIT copy_byte(struct writer *wr, uint32_t offs)
{
- write_byte(wr, peek_old_byte(wr, offs));
+ return write_byte(wr, peek_old_byte(wr, offs));
}
-static inline void INIT copy_bytes(struct writer *wr,
+static inline int INIT copy_bytes(struct writer *wr,
uint32_t rep0, int len)
{
do {
- copy_byte(wr, rep0);
+ if (copy_byte(wr, rep0))
+ return -1;
len--;
} while (len != 0 && wr->buffer_pos < wr->header->dst_size);
+
+ return len;
}
-static inline void INIT process_bit0(struct writer *wr, struct rc *rc,
+static inline int INIT process_bit0(struct writer *wr, struct rc *rc,
struct cstate *cst, uint16_t *p,
int pos_state, uint16_t *prob,
int lc, uint32_t literal_pos_mask) {
@@ -378,16 +378,17 @@ static inline void INIT process_bit0(struct writer *wr, struct rc *rc,
uint16_t *prob_lit = prob + mi;
rc_get_bit(rc, prob_lit, &mi);
}
- write_byte(wr, mi);
if (cst->state < 4)
cst->state = 0;
else if (cst->state < 10)
cst->state -= 3;
else
cst->state -= 6;
+
+ return write_byte(wr, mi);
}
-static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
+static inline int INIT process_bit1(struct writer *wr, struct rc *rc,
struct cstate *cst, uint16_t *p,
int pos_state, uint16_t *prob) {
int offset;
@@ -418,8 +419,7 @@ static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
cst->state = cst->state < LZMA_NUM_LIT_STATES ?
9 : 11;
- copy_byte(wr, cst->rep0);
- return;
+ return copy_byte(wr, cst->rep0);
} else {
rc_update_bit_1(rc, prob);
}
@@ -521,12 +521,15 @@ static inline void INIT process_bit1(struct writer *wr, struct rc *rc,
} else
cst->rep0 = pos_slot;
if (++(cst->rep0) == 0)
- return;
+ return 0;
+ if (cst->rep0 > wr->header->dict_size
+ || cst->rep0 > get_pos(wr))
+ return -1;
}
len += LZMA_MATCH_MIN_LEN;
- copy_bytes(wr, cst->rep0, len);
+ return copy_bytes(wr, cst->rep0, len);
}
@@ -536,7 +539,7 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
int(*flush)(void*, unsigned int),
unsigned char *output,
int *posp,
- void(*error_fn)(char *x)
+ void(*error)(char *x)
)
{
struct lzma_header header;
@@ -552,7 +555,7 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
unsigned char *inbuf;
int ret = -1;
- set_error_fn(error_fn);
+ rc.error = error;
if (buf)
inbuf = buf;
@@ -580,8 +583,10 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
((unsigned char *)&header)[i] = *rc.ptr++;
}
- if (header.pos >= (9 * 5 * 5))
+ if (header.pos >= (9 * 5 * 5)) {
error("bad header");
+ goto exit_1;
+ }
mi = 0;
lc = header.pos;
@@ -627,21 +632,29 @@ STATIC inline int INIT unlzma(unsigned char *buf, int in_len,
int pos_state = get_pos(&wr) & pos_state_mask;
uint16_t *prob = p + LZMA_IS_MATCH +
(cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;
- if (rc_is_bit_0(&rc, prob))
- process_bit0(&wr, &rc, &cst, p, pos_state, prob,
- lc, literal_pos_mask);
- else {
- process_bit1(&wr, &rc, &cst, p, pos_state, prob);
+ if (rc_is_bit_0(&rc, prob)) {
+ if (process_bit0(&wr, &rc, &cst, p, pos_state, prob,
+ lc, literal_pos_mask)) {
+ error("LZMA data is corrupt");
+ goto exit_3;
+ }
+ } else {
+ if (process_bit1(&wr, &rc, &cst, p, pos_state, prob)) {
+ error("LZMA data is corrupt");
+ goto exit_3;
+ }
if (cst.rep0 == 0)
break;
}
+ if (rc.buffer_size <= 0)
+ goto exit_3;
}
if (posp)
*posp = rc.ptr-rc.buffer;
- if (wr.flush)
- wr.flush(wr.buffer, wr.buffer_pos);
- ret = 0;
+ if (!wr.flush || wr.flush(wr.buffer, wr.buffer_pos) == wr.buffer_pos)
+ ret = 0;
+exit_3:
large_free(p);
exit_2:
if (!output)
@@ -659,9 +672,9 @@ STATIC int INIT decompress(unsigned char *buf, int in_len,
int(*flush)(void*, unsigned int),
unsigned char *output,
int *posp,
- void(*error_fn)(char *x)
+ void(*error)(char *x)
)
{
- return unlzma(buf, in_len - 4, fill, flush, output, posp, error_fn);
+ return unlzma(buf, in_len - 4, fill, flush, output, posp, error);
}
#endif
diff --git a/lib/decompress_unlzo.c b/lib/decompress_unlzo.c
index bcb3a4bd68f..5a7a2adf4c4 100644
--- a/lib/decompress_unlzo.c
+++ b/lib/decompress_unlzo.c
@@ -33,7 +33,6 @@
#ifdef STATIC
#include "lzo/lzo1x_decompress.c"
#else
-#include <linux/slab.h>
#include <linux/decompress/unlzo.h>
#endif
@@ -49,14 +48,25 @@ static const unsigned char lzop_magic[] = {
#define LZO_BLOCK_SIZE (256*1024l)
#define HEADER_HAS_FILTER 0x00000800L
+#define HEADER_SIZE_MIN (9 + 7 + 4 + 8 + 1 + 4)
+#define HEADER_SIZE_MAX (9 + 7 + 1 + 8 + 8 + 4 + 1 + 255 + 4)
-STATIC inline int INIT parse_header(u8 *input, u8 *skip)
+STATIC inline int INIT parse_header(u8 *input, int *skip, int in_len)
{
int l;
u8 *parse = input;
+ u8 *end = input + in_len;
u8 level = 0;
u16 version;
+ /*
+ * Check that there's enough input to possibly have a valid header.
+ * Then it is possible to parse several fields until the minimum
+ * size may have been used.
+ */
+ if (in_len < HEADER_SIZE_MIN)
+ return 0;
+
/* read magic: 9 first bits */
for (l = 0; l < 9; l++) {
if (*parse++ != lzop_magic[l])
@@ -74,6 +84,15 @@ STATIC inline int INIT parse_header(u8 *input, u8 *skip)
else
parse += 4; /* flags */
+ /*
+ * At least mode, mtime_low, filename length, and checksum must
+ * be left to be parsed. If also mtime_high is present, it's OK
+ * because the next input buffer check is after reading the
+ * filename length.
+ */
+ if (end - parse < 8 + 1 + 4)
+ return 0;
+
/* skip mode and mtime_low */
parse += 8;
if (version >= 0x0940)
@@ -81,6 +100,8 @@ STATIC inline int INIT parse_header(u8 *input, u8 *skip)
l = *parse++;
/* don't care about the file name, and skip checksum */
+ if (end - parse < l + 4)
+ return 0;
parse += l + 4;
*skip = parse - input;
@@ -91,16 +112,15 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
int (*fill) (void *, unsigned int),
int (*flush) (void *, unsigned int),
u8 *output, int *posp,
- void (*error_fn) (char *x))
+ void (*error) (char *x))
{
- u8 skip = 0, r = 0;
+ u8 r = 0;
+ int skip = 0;
u32 src_len, dst_len;
size_t tmp;
u8 *in_buf, *in_buf_save, *out_buf;
int ret = -1;
- set_error_fn(error_fn);
-
if (output) {
out_buf = output;
} else if (!flush) {
@@ -119,8 +139,8 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
goto exit_1;
} else if (input) {
in_buf = input;
- } else if (!fill || !posp) {
- error("NULL input pointer and missing position pointer or fill function");
+ } else if (!fill) {
+ error("NULL input pointer and missing fill function");
goto exit_1;
} else {
in_buf = malloc(lzo1x_worst_compress(LZO_BLOCK_SIZE));
@@ -134,22 +154,47 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
if (posp)
*posp = 0;
- if (fill)
- fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE));
+ if (fill) {
+ /*
+ * Start from in_buf + HEADER_SIZE_MAX to make it possible
+ * to use memcpy() to copy the unused data to the beginning
+ * of the buffer. This way memmove() isn't needed which
+ * is missing from pre-boot environments of most archs.
+ */
+ in_buf += HEADER_SIZE_MAX;
+ in_len = fill(in_buf, HEADER_SIZE_MAX);
+ }
- if (!parse_header(input, &skip)) {
+ if (!parse_header(in_buf, &skip, in_len)) {
error("invalid header");
goto exit_2;
}
in_buf += skip;
+ in_len -= skip;
+
+ if (fill) {
+ /* Move the unused data to the beginning of the buffer. */
+ memcpy(in_buf_save, in_buf, in_len);
+ in_buf = in_buf_save;
+ }
if (posp)
*posp = skip;
for (;;) {
/* read uncompressed block size */
+ if (fill && in_len < 4) {
+ skip = fill(in_buf + in_len, 4 - in_len);
+ if (skip > 0)
+ in_len += skip;
+ }
+ if (in_len < 4) {
+ error("file corrupted");
+ goto exit_2;
+ }
dst_len = get_unaligned_be32(in_buf);
in_buf += 4;
+ in_len -= 4;
/* exit if last block */
if (dst_len == 0) {
@@ -164,8 +209,18 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
}
/* read compressed block size, and skip block checksum info */
+ if (fill && in_len < 8) {
+ skip = fill(in_buf + in_len, 8 - in_len);
+ if (skip > 0)
+ in_len += skip;
+ }
+ if (in_len < 8) {
+ error("file corrupted");
+ goto exit_2;
+ }
src_len = get_unaligned_be32(in_buf);
in_buf += 8;
+ in_len -= 8;
if (src_len <= 0 || src_len > dst_len) {
error("file corrupted");
@@ -173,6 +228,15 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
}
/* decompress */
+ if (fill && in_len < src_len) {
+ skip = fill(in_buf + in_len, src_len - in_len);
+ if (skip > 0)
+ in_len += skip;
+ }
+ if (in_len < src_len) {
+ error("file corrupted");
+ goto exit_2;
+ }
tmp = dst_len;
/* When the input data is not compressed at all,
@@ -190,17 +254,26 @@ STATIC inline int INIT unlzo(u8 *input, int in_len,
}
}
- if (flush)
- flush(out_buf, dst_len);
+ if (flush && flush(out_buf, dst_len) != dst_len)
+ goto exit_2;
if (output)
out_buf += dst_len;
if (posp)
*posp += src_len + 12;
+
+ in_buf += src_len;
+ in_len -= src_len;
if (fill) {
+ /*
+ * If there happens to still be unused data left in
+ * in_buf, move it to the beginning of the buffer.
+ * Use a loop to avoid memmove() dependency.
+ */
+ if (in_len > 0)
+ for (skip = 0; skip < in_len; ++skip)
+ in_buf_save[skip] = in_buf[skip];
in_buf = in_buf_save;
- fill(in_buf, lzo1x_worst_compress(LZO_BLOCK_SIZE));
- } else
- in_buf += src_len;
+ }
}
ret = 0;
diff --git a/lib/decompress_unxz.c b/lib/decompress_unxz.c
new file mode 100644
index 00000000000..cecd23df2b9
--- /dev/null
+++ b/lib/decompress_unxz.c
@@ -0,0 +1,397 @@
+/*
+ * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd
+ *
+ * Author: Lasse Collin <lasse.collin@tukaani.org>
+ *
+ * This file has been put into the public domain.
+ * You can do whatever you want with this file.
+ */
+
+/*
+ * Important notes about in-place decompression
+ *
+ * At least on x86, the kernel is decompressed in place: the compressed data
+ * is placed to the end of the output buffer, and the decompressor overwrites
+ * most of the compressed data. There must be enough safety margin to
+ * guarantee that the write position is always behind the read position.
+ *
+ * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below.
+ * Note that the margin with XZ is bigger than with Deflate (gzip)!
+ *
+ * The worst case for in-place decompression is that the beginning of
+ * the file is compressed extremely well, and the rest of the file is
+ * uncompressible. Thus, we must look for worst-case expansion when the
+ * compressor is encoding uncompressible data.
+ *
+ * The structure of the .xz file in case of a compresed kernel is as follows.
+ * Sizes (as bytes) of the fields are in parenthesis.
+ *
+ * Stream Header (12)
+ * Block Header:
+ * Block Header (8-12)
+ * Compressed Data (N)
+ * Block Padding (0-3)
+ * CRC32 (4)
+ * Index (8-20)
+ * Stream Footer (12)
+ *
+ * Normally there is exactly one Block, but let's assume that there are
+ * 2-4 Blocks just in case. Because Stream Header and also Block Header
+ * of the first Block don't make the decompressor produce any uncompressed
+ * data, we can ignore them from our calculations. Block Headers of possible
+ * additional Blocks have to be taken into account still. With these
+ * assumptions, it is safe to assume that the total header overhead is
+ * less than 128 bytes.
+ *
+ * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ
+ * doesn't change the size of the data, it is enough to calculate the
+ * safety margin for LZMA2.
+ *
+ * LZMA2 stores the data in chunks. Each chunk has a header whose size is
+ * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that
+ * the maximum chunk header size is 8 bytes. After the chunk header, there
+ * may be up to 64 KiB of actual payload in the chunk. Often the payload is
+ * quite a bit smaller though; to be safe, let's assume that an average
+ * chunk has only 32 KiB of payload.
+ *
+ * The maximum uncompressed size of the payload is 2 MiB. The minimum
+ * uncompressed size of the payload is in practice never less than the
+ * payload size itself. The LZMA2 format would allow uncompressed size
+ * to be less than the payload size, but no sane compressor creates such
+ * files. LZMA2 supports storing uncompressible data in uncompressed form,
+ * so there's never a need to create payloads whose uncompressed size is
+ * smaller than the compressed size.
+ *
+ * The assumption, that the uncompressed size of the payload is never
+ * smaller than the payload itself, is valid only when talking about
+ * the payload as a whole. It is possible that the payload has parts where
+ * the decompressor consumes more input than it produces output. Calculating
+ * the worst case for this would be tricky. Instead of trying to do that,
+ * let's simply make sure that the decompressor never overwrites any bytes
+ * of the payload which it is currently reading.
+ *
+ * Now we have enough information to calculate the safety margin. We need
+ * - 128 bytes for the .xz file format headers;
+ * - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header
+ * per chunk, each chunk having average payload size of 32 KiB); and
+ * - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that
+ * the decompressor never overwrites anything from the LZMA2 chunk
+ * payload it is currently reading.
+ *
+ * We get the following formula:
+ *
+ * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
+ * = 128 + (uncompressed_size >> 12) + 65536
+ *
+ * For comparision, according to arch/x86/boot/compressed/misc.c, the
+ * equivalent formula for Deflate is this:
+ *
+ * safety_margin = 18 + (uncompressed_size >> 12) + 32768
+ *
+ * Thus, when updating Deflate-only in-place kernel decompressor to
+ * support XZ, the fixed overhead has to be increased from 18+32768 bytes
+ * to 128+65536 bytes.
+ */
+
+/*
+ * STATIC is defined to "static" if we are being built for kernel
+ * decompression (pre-boot code). <linux/decompress/mm.h> will define
+ * STATIC to empty if it wasn't already defined. Since we will need to
+ * know later if we are being used for kernel decompression, we define
+ * XZ_PREBOOT here.
+ */
+#ifdef STATIC
+# define XZ_PREBOOT
+#endif
+#ifdef __KERNEL__
+# include <linux/decompress/mm.h>
+#endif
+#define XZ_EXTERN STATIC
+
+#ifndef XZ_PREBOOT
+# include <linux/slab.h>
+# include <linux/xz.h>
+#else
+/*
+ * Use the internal CRC32 code instead of kernel's CRC32 module, which
+ * is not available in early phase of booting.
+ */
+#define XZ_INTERNAL_CRC32 1
+
+/*
+ * For boot time use, we enable only the BCJ filter of the current
+ * architecture or none if no BCJ filter is available for the architecture.
+ */
+#ifdef CONFIG_X86
+# define XZ_DEC_X86
+#endif