Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

398 lines (348 sloc) 10.899 kb
/*
* 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 comparison, 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
#ifdef CONFIG_PPC
# define XZ_DEC_POWERPC
#endif
#ifdef CONFIG_ARM
# define XZ_DEC_ARM
#endif
#ifdef CONFIG_IA64
# define XZ_DEC_IA64
#endif
#ifdef CONFIG_SPARC
# define XZ_DEC_SPARC
#endif
/*
* This will get the basic headers so that memeq() and others
* can be defined.
*/
#include "xz/xz_private.h"
/*
* Replace the normal allocation functions with the versions from
* <linux/decompress/mm.h>. vfree() needs to support vfree(NULL)
* when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it.
* Workaround it here because the other decompressors don't need it.
*/
#undef kmalloc
#undef kfree
#undef vmalloc
#undef vfree
#define kmalloc(size, flags) malloc(size)
#define kfree(ptr) free(ptr)
#define vmalloc(size) malloc(size)
#define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0)
/*
* FIXME: Not all basic memory functions are provided in architecture-specific
* files (yet). We define our own versions here for now, but this should be
* only a temporary solution.
*
* memeq and memzero are not used much and any remotely sane implementation
* is fast enough. memcpy/memmove speed matters in multi-call mode, but
* the kernel image is decompressed in single-call mode, in which only
* memcpy speed can matter and only if there is a lot of uncompressible data
* (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
* functions below should just be kept small; it's probably not worth
* optimizing for speed.
*/
#ifndef memeq
static bool memeq(const void *a, const void *b, size_t size)
{
const uint8_t *x = a;
const uint8_t *y = b;
size_t i;
for (i = 0; i < size; ++i)
if (x[i] != y[i])
return false;
return true;
}
#endif
#ifndef memzero
static void memzero(void *buf, size_t size)
{
uint8_t *b = buf;
uint8_t *e = b + size;
while (b != e)
*b++ = '\0';
}
#endif
#ifndef memmove
/* Not static to avoid a conflict with the prototype in the Linux headers. */
void *memmove(void *dest, const void *src, size_t size)
{
uint8_t *d = dest;
const uint8_t *s = src;
size_t i;
if (d < s) {
for (i = 0; i < size; ++i)
d[i] = s[i];
} else if (d > s) {
i = size;
while (i-- > 0)
d[i] = s[i];
}
return dest;
}
#endif
/*
* Since we need memmove anyway, would use it as memcpy too.
* Commented out for now to avoid breaking things.
*/
/*
#ifndef memcpy
# define memcpy memmove
#endif
*/
#include "xz/xz_crc32.c"
#include "xz/xz_dec_stream.c"
#include "xz/xz_dec_lzma2.c"
#include "xz/xz_dec_bcj.c"
#endif /* XZ_PREBOOT */
/* Size of the input and output buffers in multi-call mode */
#define XZ_IOBUF_SIZE 4096
/*
* This function implements the API defined in <linux/decompress/generic.h>.
*
* This wrapper will automatically choose single-call or multi-call mode
* of the native XZ decoder API. The single-call mode can be used only when
* both input and output buffers are available as a single chunk, i.e. when
* fill() and flush() won't be used.
*/
STATIC int INIT unxz(unsigned char *in, long in_size,
long (*fill)(void *dest, unsigned long size),
long (*flush)(void *src, unsigned long size),
unsigned char *out, long *in_used,
void (*error)(char *x))
{
struct xz_buf b;
struct xz_dec *s;
enum xz_ret ret;
bool must_free_in = false;
#if XZ_INTERNAL_CRC32
xz_crc32_init();
#endif
if (in_used != NULL)
*in_used = 0;
if (fill == NULL && flush == NULL)
s = xz_dec_init(XZ_SINGLE, 0);
else
s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1);
if (s == NULL)
goto error_alloc_state;
if (flush == NULL) {
b.out = out;
b.out_size = (size_t)-1;
} else {
b.out_size = XZ_IOBUF_SIZE;
b.out = malloc(XZ_IOBUF_SIZE);
if (b.out == NULL)
goto error_alloc_out;
}
if (in == NULL) {
must_free_in = true;
in = malloc(XZ_IOBUF_SIZE);
if (in == NULL)
goto error_alloc_in;
}
b.in = in;
b.in_pos = 0;
b.in_size = in_size;
b.out_pos = 0;
if (fill == NULL && flush == NULL) {
ret = xz_dec_run(s, &b);
} else {
do {
if (b.in_pos == b.in_size && fill != NULL) {
if (in_used != NULL)
*in_used += b.in_pos;
b.in_pos = 0;
in_size = fill(in, XZ_IOBUF_SIZE);
if (in_size < 0) {
/*
* This isn't an optimal error code
* but it probably isn't worth making
* a new one either.
*/
ret = XZ_BUF_ERROR;
break;
}
b.in_size = in_size;
}
ret = xz_dec_run(s, &b);
if (flush != NULL && (b.out_pos == b.out_size
|| (ret != XZ_OK && b.out_pos > 0))) {
/*
* Setting ret here may hide an error
* returned by xz_dec_run(), but probably
* it's not too bad.
*/
if (flush(b.out, b.out_pos) != (long)b.out_pos)
ret = XZ_BUF_ERROR;
b.out_pos = 0;
}
} while (ret == XZ_OK);
if (must_free_in)
free(in);
if (flush != NULL)
free(b.out);
}
if (in_used != NULL)
*in_used += b.in_pos;
xz_dec_end(s);
switch (ret) {
case XZ_STREAM_END:
return 0;
case XZ_MEM_ERROR:
/* This can occur only in multi-call mode. */
error("XZ decompressor ran out of memory");
break;
case XZ_FORMAT_ERROR:
error("Input is not in the XZ format (wrong magic bytes)");
break;
case XZ_OPTIONS_ERROR:
error("Input was encoded with settings that are not "
"supported by this XZ decoder");
break;
case XZ_DATA_ERROR:
case XZ_BUF_ERROR:
error("XZ-compressed data is corrupt");
break;
default:
error("Bug in the XZ decompressor");
break;
}
return -1;
error_alloc_in:
if (flush != NULL)
free(b.out);
error_alloc_out:
xz_dec_end(s);
error_alloc_state:
error("XZ decompressor ran out of memory");
return -1;
}
/*
* This macro is used by architecture-specific files to decompress
* the kernel image.
*/
#define decompress unxz
Jump to Line
Something went wrong with that request. Please try again.