Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

file 397 lines (348 sloc) 10.892 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 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 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, int in_size,
int (*fill)(void *dest, unsigned int size),
int (*flush)(void *src, unsigned int size),
unsigned char *out, int *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) != (int)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
Something went wrong with that request. Please try again.