1229159Sadrian/* 2229159Sadrian * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd 3229159Sadrian * 4229159Sadrian * Author: Lasse Collin <lasse.collin@tukaani.org> 5229159Sadrian * 6229159Sadrian * This file has been put into the public domain. 7229159Sadrian * You can do whatever you want with this file. 8229159Sadrian */ 9229159Sadrian 10229159Sadrian/* 11229159Sadrian * Important notes about in-place decompression 12229159Sadrian * 13229159Sadrian * At least on x86, the kernel is decompressed in place: the compressed data 14229159Sadrian * is placed to the end of the output buffer, and the decompressor overwrites 15229159Sadrian * most of the compressed data. There must be enough safety margin to 16229159Sadrian * guarantee that the write position is always behind the read position. 17229159Sadrian * 18229159Sadrian * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below. 19229159Sadrian * Note that the margin with XZ is bigger than with Deflate (gzip)! 20229159Sadrian * 21229159Sadrian * The worst case for in-place decompression is that the beginning of 22229159Sadrian * the file is compressed extremely well, and the rest of the file is 23229159Sadrian * uncompressible. Thus, we must look for worst-case expansion when the 24229159Sadrian * compressor is encoding uncompressible data. 25229159Sadrian * 26229159Sadrian * The structure of the .xz file in case of a compresed kernel is as follows. 27229159Sadrian * Sizes (as bytes) of the fields are in parenthesis. 28229159Sadrian * 29229159Sadrian * Stream Header (12) 30229159Sadrian * Block Header: 31229159Sadrian * Block Header (8-12) 32229159Sadrian * Compressed Data (N) 33229159Sadrian * Block Padding (0-3) 34229159Sadrian * CRC32 (4) 35229159Sadrian * Index (8-20) 36229159Sadrian * Stream Footer (12) 37229159Sadrian * 38229159Sadrian * Normally there is exactly one Block, but let's assume that there are 39229159Sadrian * 2-4 Blocks just in case. Because Stream Header and also Block Header 40229159Sadrian * of the first Block don't make the decompressor produce any uncompressed 41229159Sadrian * data, we can ignore them from our calculations. Block Headers of possible 42229159Sadrian * additional Blocks have to be taken into account still. With these 43229159Sadrian * assumptions, it is safe to assume that the total header overhead is 44229159Sadrian * less than 128 bytes. 45229159Sadrian * 46229159Sadrian * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ 47229159Sadrian * doesn't change the size of the data, it is enough to calculate the 48229159Sadrian * safety margin for LZMA2. 49229159Sadrian * 50229159Sadrian * LZMA2 stores the data in chunks. Each chunk has a header whose size is 51229159Sadrian * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that 52229159Sadrian * the maximum chunk header size is 8 bytes. After the chunk header, there 53229159Sadrian * may be up to 64 KiB of actual payload in the chunk. Often the payload is 54229159Sadrian * quite a bit smaller though; to be safe, let's assume that an average 55229159Sadrian * chunk has only 32 KiB of payload. 56229159Sadrian * 57229159Sadrian * The maximum uncompressed size of the payload is 2 MiB. The minimum 58229159Sadrian * uncompressed size of the payload is in practice never less than the 59229159Sadrian * payload size itself. The LZMA2 format would allow uncompressed size 60229159Sadrian * to be less than the payload size, but no sane compressor creates such 61229159Sadrian * files. LZMA2 supports storing uncompressible data in uncompressed form, 62229159Sadrian * so there's never a need to create payloads whose uncompressed size is 63229159Sadrian * smaller than the compressed size. 64229159Sadrian * 65229159Sadrian * The assumption, that the uncompressed size of the payload is never 66229159Sadrian * smaller than the payload itself, is valid only when talking about 67229159Sadrian * the payload as a whole. It is possible that the payload has parts where 68229159Sadrian * the decompressor consumes more input than it produces output. Calculating 69229159Sadrian * the worst case for this would be tricky. Instead of trying to do that, 70229159Sadrian * let's simply make sure that the decompressor never overwrites any bytes 71229159Sadrian * of the payload which it is currently reading. 72229159Sadrian * 73229159Sadrian * Now we have enough information to calculate the safety margin. We need 74229159Sadrian * - 128 bytes for the .xz file format headers; 75229159Sadrian * - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header 76229159Sadrian * per chunk, each chunk having average payload size of 32 KiB); and 77229159Sadrian * - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that 78229159Sadrian * the decompressor never overwrites anything from the LZMA2 chunk 79229159Sadrian * payload it is currently reading. 80229159Sadrian * 81229159Sadrian * We get the following formula: 82229159Sadrian * 83229159Sadrian * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536 84229159Sadrian * = 128 + (uncompressed_size >> 12) + 65536 85229159Sadrian * 86229159Sadrian * For comparision, according to arch/x86/boot/compressed/misc.c, the 87229159Sadrian * equivalent formula for Deflate is this: 88229159Sadrian * 89229159Sadrian * safety_margin = 18 + (uncompressed_size >> 12) + 32768 90229159Sadrian * 91229159Sadrian * Thus, when updating Deflate-only in-place kernel decompressor to 92229159Sadrian * support XZ, the fixed overhead has to be increased from 18+32768 bytes 93229159Sadrian * to 128+65536 bytes. 94229159Sadrian */ 95229159Sadrian 96229159Sadrian/* 97229159Sadrian * STATIC is defined to "static" if we are being built for kernel 98229159Sadrian * decompression (pre-boot code). <linux/decompress/mm.h> will define 99229159Sadrian * STATIC to empty if it wasn't already defined. Since we will need to 100229159Sadrian * know later if we are being used for kernel decompression, we define 101229159Sadrian * XZ_PREBOOT here. 102229159Sadrian */ 103229159Sadrian#ifdef STATIC 104229159Sadrian# define XZ_PREBOOT 105229159Sadrian#endif 106229159Sadrian#ifdef __KERNEL__ 107229159Sadrian# include <linux/decompress/mm.h> 108229159Sadrian#endif 109229159Sadrian#define XZ_EXTERN STATIC 110229159Sadrian 111229159Sadrian#ifndef XZ_PREBOOT 112229159Sadrian# include <linux/slab.h> 113229159Sadrian# include <linux/xz.h> 114229159Sadrian#else 115229159Sadrian/* 116229159Sadrian * Use the internal CRC32 code instead of kernel's CRC32 module, which 117229159Sadrian * is not available in early phase of booting. 118229159Sadrian */ 119229159Sadrian#define XZ_INTERNAL_CRC32 1 120229159Sadrian 121229159Sadrian/* 122229159Sadrian * For boot time use, we enable only the BCJ filter of the current 123229159Sadrian * architecture or none if no BCJ filter is available for the architecture. 124229159Sadrian */ 125229159Sadrian#ifdef CONFIG_X86 126229159Sadrian# define XZ_DEC_X86 127229159Sadrian#endif 128229159Sadrian#ifdef CONFIG_PPC 129229159Sadrian# define XZ_DEC_POWERPC 130229159Sadrian#endif 131229159Sadrian#ifdef CONFIG_ARM 132229159Sadrian# define XZ_DEC_ARM 133229159Sadrian#endif 134229159Sadrian#ifdef CONFIG_IA64 135229159Sadrian# define XZ_DEC_IA64 136229159Sadrian#endif 137229159Sadrian#ifdef CONFIG_SPARC 138229159Sadrian# define XZ_DEC_SPARC 139229159Sadrian#endif 140229159Sadrian 141229159Sadrian/* 142229159Sadrian * This will get the basic headers so that memeq() and others 143229159Sadrian * can be defined. 144229159Sadrian */ 145229159Sadrian#include "xz/xz_private.h" 146229159Sadrian 147229159Sadrian/* 148229159Sadrian * Replace the normal allocation functions with the versions from 149229159Sadrian * <linux/decompress/mm.h>. vfree() needs to support vfree(NULL) 150229159Sadrian * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it. 151229159Sadrian * Workaround it here because the other decompressors don't need it. 152229159Sadrian */ 153229159Sadrian#undef kmalloc 154229159Sadrian#undef kfree 155229159Sadrian#undef vmalloc 156229159Sadrian#undef vfree 157229159Sadrian#define kmalloc(size, flags) malloc(size) 158229159Sadrian#define kfree(ptr) free(ptr) 159229159Sadrian#define vmalloc(size) malloc(size) 160229159Sadrian#define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0) 161229159Sadrian 162229159Sadrian/* 163229159Sadrian * FIXME: Not all basic memory functions are provided in architecture-specific 164229159Sadrian * files (yet). We define our own versions here for now, but this should be 165229159Sadrian * only a temporary solution. 166229159Sadrian * 167229159Sadrian * memeq and memzero are not used much and any remotely sane implementation 168229159Sadrian * is fast enough. memcpy/memmove speed matters in multi-call mode, but 169229159Sadrian * the kernel image is decompressed in single-call mode, in which only 170229159Sadrian * memcpy speed can matter and only if there is a lot of uncompressible data 171229159Sadrian * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the 172229159Sadrian * functions below should just be kept small; it's probably not worth 173229159Sadrian * optimizing for speed. 174229159Sadrian */ 175229159Sadrian 176229159Sadrian#ifndef memeq 177229159Sadrianstatic bool memeq(const void *a, const void *b, size_t size) 178229159Sadrian{ 179229159Sadrian const uint8_t *x = a; 180229159Sadrian const uint8_t *y = b; 181229159Sadrian size_t i; 182229159Sadrian 183229159Sadrian for (i = 0; i < size; ++i) 184229159Sadrian if (x[i] != y[i]) 185229159Sadrian return false; 186229159Sadrian 187229159Sadrian return true; 188229159Sadrian} 189229159Sadrian#endif 190229159Sadrian 191229159Sadrian#ifndef memzero 192229159Sadrianstatic void memzero(void *buf, size_t size) 193229159Sadrian{ 194229159Sadrian uint8_t *b = buf; 195229159Sadrian uint8_t *e = b + size; 196229159Sadrian 197229159Sadrian while (b != e) 198229159Sadrian *b++ = '\0'; 199229159Sadrian} 200229159Sadrian#endif 201229159Sadrian 202229159Sadrian#ifndef memmove 203229159Sadrian/* Not static to avoid a conflict with the prototype in the Linux headers. */ 204229159Sadrianvoid *memmove(void *dest, const void *src, size_t size) 205229159Sadrian{ 206229159Sadrian uint8_t *d = dest; 207229159Sadrian const uint8_t *s = src; 208229159Sadrian size_t i; 209229159Sadrian 210229159Sadrian if (d < s) { 211229159Sadrian for (i = 0; i < size; ++i) 212229159Sadrian d[i] = s[i]; 213229159Sadrian } else if (d > s) { 214229159Sadrian i = size; 215229159Sadrian while (i-- > 0) 216229159Sadrian d[i] = s[i]; 217229159Sadrian } 218229159Sadrian 219229159Sadrian return dest; 220229159Sadrian} 221229159Sadrian#endif 222229159Sadrian 223229159Sadrian/* 224229159Sadrian * Since we need memmove anyway, would use it as memcpy too. 225229159Sadrian * Commented out for now to avoid breaking things. 226229159Sadrian */ 227229159Sadrian/* 228229159Sadrian#ifndef memcpy 229229159Sadrian# define memcpy memmove 230229159Sadrian#endif 231229159Sadrian*/ 232229159Sadrian 233229159Sadrian#include "xz/xz_crc32.c" 234229159Sadrian#include "xz/xz_dec_stream.c" 235229159Sadrian#include "xz/xz_dec_lzma2.c" 236229159Sadrian#include "xz/xz_dec_bcj.c" 237229159Sadrian 238229159Sadrian#endif /* XZ_PREBOOT */ 239229159Sadrian 240229159Sadrian/* Size of the input and output buffers in multi-call mode */ 241229159Sadrian#define XZ_IOBUF_SIZE 4096 242229159Sadrian 243229159Sadrian/* 244229159Sadrian * This function implements the API defined in <linux/decompress/generic.h>. 245229159Sadrian * 246229159Sadrian * This wrapper will automatically choose single-call or multi-call mode 247229159Sadrian * of the native XZ decoder API. The single-call mode can be used only when 248229159Sadrian * both input and output buffers are available as a single chunk, i.e. when 249229159Sadrian * fill() and flush() won't be used. 250229159Sadrian */ 251229159SadrianSTATIC int INIT unxz(unsigned char *in, int in_size, 252229159Sadrian int (*fill)(void *dest, unsigned int size), 253229159Sadrian int (*flush)(void *src, unsigned int size), 254229159Sadrian unsigned char *out, int *in_used, 255229159Sadrian void (*error)(char *x)) 256229159Sadrian{ 257229159Sadrian struct xz_buf b; 258229159Sadrian struct xz_dec *s; 259229159Sadrian enum xz_ret ret; 260229159Sadrian bool must_free_in = false; 261229159Sadrian 262229159Sadrian#if XZ_INTERNAL_CRC32 263229159Sadrian xz_crc32_init(); 264229159Sadrian#endif 265229159Sadrian 266229159Sadrian if (in_used != NULL) 267229159Sadrian *in_used = 0; 268229159Sadrian 269229159Sadrian if (fill == NULL && flush == NULL) 270229159Sadrian s = xz_dec_init(XZ_SINGLE, 0); 271229159Sadrian else 272229159Sadrian s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1); 273229159Sadrian 274229159Sadrian if (s == NULL) 275229159Sadrian goto error_alloc_state; 276229159Sadrian 277229159Sadrian if (flush == NULL) { 278229159Sadrian b.out = out; 279229159Sadrian b.out_size = (size_t)-1; 280229159Sadrian } else { 281229159Sadrian b.out_size = XZ_IOBUF_SIZE; 282229159Sadrian b.out = malloc(XZ_IOBUF_SIZE); 283229159Sadrian if (b.out == NULL) 284229159Sadrian goto error_alloc_out; 285229159Sadrian } 286229159Sadrian 287229159Sadrian if (in == NULL) { 288229159Sadrian must_free_in = true; 289229159Sadrian in = malloc(XZ_IOBUF_SIZE); 290229159Sadrian if (in == NULL) 291229159Sadrian goto error_alloc_in; 292229159Sadrian } 293229159Sadrian 294229159Sadrian b.in = in; 295229159Sadrian b.in_pos = 0; 296229159Sadrian b.in_size = in_size; 297229159Sadrian b.out_pos = 0; 298229159Sadrian 299229159Sadrian if (fill == NULL && flush == NULL) { 300229159Sadrian ret = xz_dec_run(s, &b); 301229159Sadrian } else { 302229159Sadrian do { 303229159Sadrian if (b.in_pos == b.in_size && fill != NULL) { 304229159Sadrian if (in_used != NULL) 305229159Sadrian *in_used += b.in_pos; 306229159Sadrian 307229159Sadrian b.in_pos = 0; 308229159Sadrian 309229159Sadrian in_size = fill(in, XZ_IOBUF_SIZE); 310229159Sadrian if (in_size < 0) { 311229159Sadrian /* 312229159Sadrian * This isn't an optimal error code 313229159Sadrian * but it probably isn't worth making 314229159Sadrian * a new one either. 315229159Sadrian */ 316229159Sadrian ret = XZ_BUF_ERROR; 317229159Sadrian break; 318229159Sadrian } 319229159Sadrian 320229159Sadrian b.in_size = in_size; 321229159Sadrian } 322229159Sadrian 323229159Sadrian ret = xz_dec_run(s, &b); 324229159Sadrian 325229159Sadrian if (flush != NULL && (b.out_pos == b.out_size 326229159Sadrian || (ret != XZ_OK && b.out_pos > 0))) { 327229159Sadrian /* 328229159Sadrian * Setting ret here may hide an error 329229159Sadrian * returned by xz_dec_run(), but probably 330229159Sadrian * it's not too bad. 331229159Sadrian */ 332229159Sadrian if (flush(b.out, b.out_pos) != (int)b.out_pos) 333229159Sadrian ret = XZ_BUF_ERROR; 334229159Sadrian 335229159Sadrian b.out_pos = 0; 336229159Sadrian } 337229159Sadrian } while (ret == XZ_OK); 338229159Sadrian 339229159Sadrian if (must_free_in) 340229159Sadrian free(in); 341229159Sadrian 342229159Sadrian if (flush != NULL) 343229159Sadrian free(b.out); 344229159Sadrian } 345229159Sadrian 346229159Sadrian if (in_used != NULL) 347229159Sadrian *in_used += b.in_pos; 348229159Sadrian 349229159Sadrian xz_dec_end(s); 350229159Sadrian 351229159Sadrian switch (ret) { 352229159Sadrian case XZ_STREAM_END: 353229159Sadrian return 0; 354229159Sadrian 355229159Sadrian case XZ_MEM_ERROR: 356229159Sadrian /* This can occur only in multi-call mode. */ 357229159Sadrian error("XZ decompressor ran out of memory"); 358229159Sadrian break; 359229159Sadrian 360229159Sadrian case XZ_FORMAT_ERROR: 361229159Sadrian error("Input is not in the XZ format (wrong magic bytes)"); 362229159Sadrian break; 363229159Sadrian 364229159Sadrian case XZ_OPTIONS_ERROR: 365229159Sadrian error("Input was encoded with settings that are not " 366229159Sadrian "supported by this XZ decoder"); 367229159Sadrian break; 368229159Sadrian 369229159Sadrian case XZ_DATA_ERROR: 370229159Sadrian case XZ_BUF_ERROR: 371229159Sadrian error("XZ-compressed data is corrupt"); 372229159Sadrian break; 373229159Sadrian 374229159Sadrian default: 375229159Sadrian error("Bug in the XZ decompressor"); 376229159Sadrian break; 377229159Sadrian } 378229159Sadrian 379229159Sadrian return -1; 380229159Sadrian 381229159Sadrianerror_alloc_in: 382229159Sadrian if (flush != NULL) 383229159Sadrian free(b.out); 384229159Sadrian 385229159Sadrianerror_alloc_out: 386229159Sadrian xz_dec_end(s); 387229159Sadrian 388229159Sadrianerror_alloc_state: 389229159Sadrian error("XZ decompressor ran out of memory"); 390229159Sadrian return -1; 391229159Sadrian} 392229159Sadrian 393229159Sadrian/* 394229159Sadrian * This macro is used by architecture-specific files to decompress 395229159Sadrian * the kernel image. 396229159Sadrian */ 397229159Sadrian#define decompress unxz 398