Commit | Line | Data |
---|---|---|
3ebe1243 LC |
1 | /* |
2 | * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd | |
3 | * | |
4 | * Author: Lasse Collin <lasse.collin@tukaani.org> | |
5 | * | |
6 | * This file has been put into the public domain. | |
7 | * You can do whatever you want with this file. | |
8 | */ | |
9 | ||
10 | /* | |
11 | * Important notes about in-place decompression | |
12 | * | |
13 | * At least on x86, the kernel is decompressed in place: the compressed data | |
14 | * is placed to the end of the output buffer, and the decompressor overwrites | |
15 | * most of the compressed data. There must be enough safety margin to | |
16 | * guarantee that the write position is always behind the read position. | |
17 | * | |
18 | * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below. | |
19 | * Note that the margin with XZ is bigger than with Deflate (gzip)! | |
20 | * | |
21 | * The worst case for in-place decompression is that the beginning of | |
22 | * the file is compressed extremely well, and the rest of the file is | |
0a434e0a LC |
23 | * incompressible. Thus, we must look for worst-case expansion when the |
24 | * compressor is encoding incompressible data. | |
3ebe1243 | 25 | * |
05911c5d | 26 | * The structure of the .xz file in case of a compressed kernel is as follows. |
3ebe1243 LC |
27 | * Sizes (as bytes) of the fields are in parenthesis. |
28 | * | |
29 | * Stream Header (12) | |
30 | * Block Header: | |
31 | * Block Header (8-12) | |
32 | * Compressed Data (N) | |
33 | * Block Padding (0-3) | |
34 | * CRC32 (4) | |
35 | * Index (8-20) | |
36 | * Stream Footer (12) | |
37 | * | |
38 | * Normally there is exactly one Block, but let's assume that there are | |
39 | * 2-4 Blocks just in case. Because Stream Header and also Block Header | |
40 | * of the first Block don't make the decompressor produce any uncompressed | |
41 | * data, we can ignore them from our calculations. Block Headers of possible | |
42 | * additional Blocks have to be taken into account still. With these | |
43 | * assumptions, it is safe to assume that the total header overhead is | |
44 | * less than 128 bytes. | |
45 | * | |
46 | * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ | |
47 | * doesn't change the size of the data, it is enough to calculate the | |
48 | * safety margin for LZMA2. | |
49 | * | |
50 | * LZMA2 stores the data in chunks. Each chunk has a header whose size is | |
51 | * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that | |
52 | * the maximum chunk header size is 8 bytes. After the chunk header, there | |
53 | * may be up to 64 KiB of actual payload in the chunk. Often the payload is | |
54 | * quite a bit smaller though; to be safe, let's assume that an average | |
55 | * chunk has only 32 KiB of payload. | |
56 | * | |
57 | * The maximum uncompressed size of the payload is 2 MiB. The minimum | |
58 | * uncompressed size of the payload is in practice never less than the | |
59 | * payload size itself. The LZMA2 format would allow uncompressed size | |
60 | * to be less than the payload size, but no sane compressor creates such | |
0a434e0a | 61 | * files. LZMA2 supports storing incompressible data in uncompressed form, |
3ebe1243 LC |
62 | * so there's never a need to create payloads whose uncompressed size is |
63 | * smaller than the compressed size. | |
64 | * | |
65 | * The assumption, that the uncompressed size of the payload is never | |
66 | * smaller than the payload itself, is valid only when talking about | |
67 | * the payload as a whole. It is possible that the payload has parts where | |
68 | * the decompressor consumes more input than it produces output. Calculating | |
69 | * the worst case for this would be tricky. Instead of trying to do that, | |
70 | * let's simply make sure that the decompressor never overwrites any bytes | |
71 | * of the payload which it is currently reading. | |
72 | * | |
73 | * Now we have enough information to calculate the safety margin. We need | |
74 | * - 128 bytes for the .xz file format headers; | |
75 | * - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header | |
76 | * per chunk, each chunk having average payload size of 32 KiB); and | |
77 | * - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that | |
78 | * the decompressor never overwrites anything from the LZMA2 chunk | |
79 | * payload it is currently reading. | |
80 | * | |
81 | * We get the following formula: | |
82 | * | |
83 | * safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536 | |
84 | * = 128 + (uncompressed_size >> 12) + 65536 | |
85 | * | |
25985edc | 86 | * For comparison, according to arch/x86/boot/compressed/misc.c, the |
3ebe1243 LC |
87 | * equivalent formula for Deflate is this: |
88 | * | |
89 | * safety_margin = 18 + (uncompressed_size >> 12) + 32768 | |
90 | * | |
91 | * Thus, when updating Deflate-only in-place kernel decompressor to | |
92 | * support XZ, the fixed overhead has to be increased from 18+32768 bytes | |
93 | * to 128+65536 bytes. | |
94 | */ | |
95 | ||
96 | /* | |
97 | * STATIC is defined to "static" if we are being built for kernel | |
98 | * decompression (pre-boot code). <linux/decompress/mm.h> will define | |
99 | * STATIC to empty if it wasn't already defined. Since we will need to | |
100 | * know later if we are being used for kernel decompression, we define | |
101 | * XZ_PREBOOT here. | |
102 | */ | |
103 | #ifdef STATIC | |
104 | # define XZ_PREBOOT | |
00444448 AB |
105 | #else |
106 | #include <linux/decompress/unxz.h> | |
3ebe1243 LC |
107 | #endif |
108 | #ifdef __KERNEL__ | |
109 | # include <linux/decompress/mm.h> | |
110 | #endif | |
111 | #define XZ_EXTERN STATIC | |
112 | ||
113 | #ifndef XZ_PREBOOT | |
114 | # include <linux/slab.h> | |
115 | # include <linux/xz.h> | |
116 | #else | |
117 | /* | |
118 | * Use the internal CRC32 code instead of kernel's CRC32 module, which | |
119 | * is not available in early phase of booting. | |
120 | */ | |
121 | #define XZ_INTERNAL_CRC32 1 | |
122 | ||
123 | /* | |
124 | * For boot time use, we enable only the BCJ filter of the current | |
125 | * architecture or none if no BCJ filter is available for the architecture. | |
126 | */ | |
127 | #ifdef CONFIG_X86 | |
128 | # define XZ_DEC_X86 | |
129 | #endif | |
130 | #ifdef CONFIG_PPC | |
131 | # define XZ_DEC_POWERPC | |
132 | #endif | |
133 | #ifdef CONFIG_ARM | |
134 | # define XZ_DEC_ARM | |
135 | #endif | |
136 | #ifdef CONFIG_IA64 | |
137 | # define XZ_DEC_IA64 | |
138 | #endif | |
139 | #ifdef CONFIG_SPARC | |
140 | # define XZ_DEC_SPARC | |
141 | #endif | |
142 | ||
143 | /* | |
144 | * This will get the basic headers so that memeq() and others | |
145 | * can be defined. | |
146 | */ | |
147 | #include "xz/xz_private.h" | |
148 | ||
149 | /* | |
150 | * Replace the normal allocation functions with the versions from | |
151 | * <linux/decompress/mm.h>. vfree() needs to support vfree(NULL) | |
152 | * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it. | |
153 | * Workaround it here because the other decompressors don't need it. | |
154 | */ | |
155 | #undef kmalloc | |
156 | #undef kfree | |
157 | #undef vmalloc | |
158 | #undef vfree | |
159 | #define kmalloc(size, flags) malloc(size) | |
160 | #define kfree(ptr) free(ptr) | |
161 | #define vmalloc(size) malloc(size) | |
162 | #define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0) | |
163 | ||
164 | /* | |
165 | * FIXME: Not all basic memory functions are provided in architecture-specific | |
166 | * files (yet). We define our own versions here for now, but this should be | |
167 | * only a temporary solution. | |
168 | * | |
169 | * memeq and memzero are not used much and any remotely sane implementation | |
170 | * is fast enough. memcpy/memmove speed matters in multi-call mode, but | |
171 | * the kernel image is decompressed in single-call mode, in which only | |
0a434e0a LC |
172 | * memmove speed can matter and only if there is a lot of incompressible data |
173 | * (LZMA2 stores incompressible chunks in uncompressed form). Thus, the | |
3ebe1243 LC |
174 | * functions below should just be kept small; it's probably not worth |
175 | * optimizing for speed. | |
176 | */ | |
177 | ||
178 | #ifndef memeq | |
179 | static bool memeq(const void *a, const void *b, size_t size) | |
180 | { | |
181 | const uint8_t *x = a; | |
182 | const uint8_t *y = b; | |
183 | size_t i; | |
184 | ||
185 | for (i = 0; i < size; ++i) | |
186 | if (x[i] != y[i]) | |
187 | return false; | |
188 | ||
189 | return true; | |
190 | } | |
191 | #endif | |
192 | ||
193 | #ifndef memzero | |
194 | static void memzero(void *buf, size_t size) | |
195 | { | |
196 | uint8_t *b = buf; | |
197 | uint8_t *e = b + size; | |
198 | ||
199 | while (b != e) | |
200 | *b++ = '\0'; | |
201 | } | |
202 | #endif | |
203 | ||
204 | #ifndef memmove | |
205 | /* Not static to avoid a conflict with the prototype in the Linux headers. */ | |
206 | void *memmove(void *dest, const void *src, size_t size) | |
207 | { | |
208 | uint8_t *d = dest; | |
209 | const uint8_t *s = src; | |
210 | size_t i; | |
211 | ||
212 | if (d < s) { | |
213 | for (i = 0; i < size; ++i) | |
214 | d[i] = s[i]; | |
215 | } else if (d > s) { | |
216 | i = size; | |
217 | while (i-- > 0) | |
218 | d[i] = s[i]; | |
219 | } | |
220 | ||
221 | return dest; | |
222 | } | |
223 | #endif | |
224 | ||
225 | /* | |
226 | * Since we need memmove anyway, would use it as memcpy too. | |
227 | * Commented out for now to avoid breaking things. | |
228 | */ | |
229 | /* | |
230 | #ifndef memcpy | |
231 | # define memcpy memmove | |
232 | #endif | |
233 | */ | |
234 | ||
235 | #include "xz/xz_crc32.c" | |
236 | #include "xz/xz_dec_stream.c" | |
237 | #include "xz/xz_dec_lzma2.c" | |
238 | #include "xz/xz_dec_bcj.c" | |
239 | ||
240 | #endif /* XZ_PREBOOT */ | |
241 | ||
242 | /* Size of the input and output buffers in multi-call mode */ | |
243 | #define XZ_IOBUF_SIZE 4096 | |
244 | ||
245 | /* | |
246 | * This function implements the API defined in <linux/decompress/generic.h>. | |
247 | * | |
248 | * This wrapper will automatically choose single-call or multi-call mode | |
249 | * of the native XZ decoder API. The single-call mode can be used only when | |
250 | * both input and output buffers are available as a single chunk, i.e. when | |
251 | * fill() and flush() won't be used. | |
252 | */ | |
d97b07c5 YL |
253 | STATIC int INIT unxz(unsigned char *in, long in_size, |
254 | long (*fill)(void *dest, unsigned long size), | |
255 | long (*flush)(void *src, unsigned long size), | |
256 | unsigned char *out, long *in_used, | |
3ebe1243 LC |
257 | void (*error)(char *x)) |
258 | { | |
259 | struct xz_buf b; | |
260 | struct xz_dec *s; | |
261 | enum xz_ret ret; | |
262 | bool must_free_in = false; | |
263 | ||
264 | #if XZ_INTERNAL_CRC32 | |
265 | xz_crc32_init(); | |
266 | #endif | |
267 | ||
268 | if (in_used != NULL) | |
269 | *in_used = 0; | |
270 | ||
271 | if (fill == NULL && flush == NULL) | |
272 | s = xz_dec_init(XZ_SINGLE, 0); | |
273 | else | |
274 | s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1); | |
275 | ||
276 | if (s == NULL) | |
277 | goto error_alloc_state; | |
278 | ||
279 | if (flush == NULL) { | |
280 | b.out = out; | |
281 | b.out_size = (size_t)-1; | |
282 | } else { | |
283 | b.out_size = XZ_IOBUF_SIZE; | |
284 | b.out = malloc(XZ_IOBUF_SIZE); | |
285 | if (b.out == NULL) | |
286 | goto error_alloc_out; | |
287 | } | |
288 | ||
289 | if (in == NULL) { | |
290 | must_free_in = true; | |
291 | in = malloc(XZ_IOBUF_SIZE); | |
292 | if (in == NULL) | |
293 | goto error_alloc_in; | |
294 | } | |
295 | ||
296 | b.in = in; | |
297 | b.in_pos = 0; | |
298 | b.in_size = in_size; | |
299 | b.out_pos = 0; | |
300 | ||
301 | if (fill == NULL && flush == NULL) { | |
302 | ret = xz_dec_run(s, &b); | |
303 | } else { | |
304 | do { | |
305 | if (b.in_pos == b.in_size && fill != NULL) { | |
306 | if (in_used != NULL) | |
307 | *in_used += b.in_pos; | |
308 | ||
309 | b.in_pos = 0; | |
310 | ||
311 | in_size = fill(in, XZ_IOBUF_SIZE); | |
312 | if (in_size < 0) { | |
313 | /* | |
314 | * This isn't an optimal error code | |
315 | * but it probably isn't worth making | |
316 | * a new one either. | |
317 | */ | |
318 | ret = XZ_BUF_ERROR; | |
319 | break; | |
320 | } | |
321 | ||
322 | b.in_size = in_size; | |
323 | } | |
324 | ||
325 | ret = xz_dec_run(s, &b); | |
326 | ||
327 | if (flush != NULL && (b.out_pos == b.out_size | |
328 | || (ret != XZ_OK && b.out_pos > 0))) { | |
329 | /* | |
330 | * Setting ret here may hide an error | |
331 | * returned by xz_dec_run(), but probably | |
332 | * it's not too bad. | |
333 | */ | |
d97b07c5 | 334 | if (flush(b.out, b.out_pos) != (long)b.out_pos) |
3ebe1243 LC |
335 | ret = XZ_BUF_ERROR; |
336 | ||
337 | b.out_pos = 0; | |
338 | } | |
339 | } while (ret == XZ_OK); | |
340 | ||
341 | if (must_free_in) | |
342 | free(in); | |
343 | ||
344 | if (flush != NULL) | |
345 | free(b.out); | |
346 | } | |
347 | ||
348 | if (in_used != NULL) | |
349 | *in_used += b.in_pos; | |
350 | ||
351 | xz_dec_end(s); | |
352 | ||
353 | switch (ret) { | |
354 | case XZ_STREAM_END: | |
355 | return 0; | |
356 | ||
357 | case XZ_MEM_ERROR: | |
358 | /* This can occur only in multi-call mode. */ | |
359 | error("XZ decompressor ran out of memory"); | |
360 | break; | |
361 | ||
362 | case XZ_FORMAT_ERROR: | |
363 | error("Input is not in the XZ format (wrong magic bytes)"); | |
364 | break; | |
365 | ||
366 | case XZ_OPTIONS_ERROR: | |
367 | error("Input was encoded with settings that are not " | |
368 | "supported by this XZ decoder"); | |
369 | break; | |
370 | ||
371 | case XZ_DATA_ERROR: | |
372 | case XZ_BUF_ERROR: | |
373 | error("XZ-compressed data is corrupt"); | |
374 | break; | |
375 | ||
376 | default: | |
377 | error("Bug in the XZ decompressor"); | |
378 | break; | |
379 | } | |
380 | ||
381 | return -1; | |
382 | ||
383 | error_alloc_in: | |
384 | if (flush != NULL) | |
385 | free(b.out); | |
386 | ||
387 | error_alloc_out: | |
388 | xz_dec_end(s); | |
389 | ||
390 | error_alloc_state: | |
391 | error("XZ decompressor ran out of memory"); | |
392 | return -1; | |
393 | } | |
394 | ||
395 | /* | |
396 | * This macro is used by architecture-specific files to decompress | |
397 | * the kernel image. | |
398 | */ | |
2d3862d2 YL |
399 | #ifdef XZ_PREBOOT |
400 | STATIC int INIT __decompress(unsigned char *buf, long len, | |
401 | long (*fill)(void*, unsigned long), | |
402 | long (*flush)(void*, unsigned long), | |
403 | unsigned char *out_buf, long olen, | |
404 | long *pos, | |
405 | void (*error)(char *x)) | |
406 | { | |
407 | return unxz(buf, len, fill, flush, out_buf, pos, error); | |
408 | } | |
409 | #endif |