Commit | Line | Data |
---|---|---|
4963bb2b NT |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | ||
3 | /* | |
4 | * Important notes about in-place decompression | |
5 | * | |
6 | * At least on x86, the kernel is decompressed in place: the compressed data | |
7 | * is placed to the end of the output buffer, and the decompressor overwrites | |
8 | * most of the compressed data. There must be enough safety margin to | |
9 | * guarantee that the write position is always behind the read position. | |
10 | * | |
11 | * The safety margin for ZSTD with a 128 KB block size is calculated below. | |
12 | * Note that the margin with ZSTD is bigger than with GZIP or XZ! | |
13 | * | |
14 | * The worst case for in-place decompression is that the beginning of | |
15 | * the file is compressed extremely well, and the rest of the file is | |
16 | * uncompressible. Thus, we must look for worst-case expansion when the | |
17 | * compressor is encoding uncompressible data. | |
18 | * | |
05911c5d | 19 | * The structure of the .zst file in case of a compressed kernel is as follows. |
4963bb2b NT |
20 | * Maximum sizes (as bytes) of the fields are in parenthesis. |
21 | * | |
22 | * Frame Header: (18) | |
23 | * Blocks: (N) | |
24 | * Checksum: (4) | |
25 | * | |
26 | * The frame header and checksum overhead is at most 22 bytes. | |
27 | * | |
28 | * ZSTD stores the data in blocks. Each block has a header whose size is | |
29 | * a 3 bytes. After the block header, there is up to 128 KB of payload. | |
30 | * The maximum uncompressed size of the payload is 128 KB. The minimum | |
31 | * uncompressed size of the payload is never less than the payload size | |
32 | * (excluding the block header). | |
33 | * | |
34 | * The assumption, that the uncompressed size of the payload is never | |
35 | * smaller than the payload itself, is valid only when talking about | |
36 | * the payload as a whole. It is possible that the payload has parts where | |
37 | * the decompressor consumes more input than it produces output. Calculating | |
38 | * the worst case for this would be tricky. Instead of trying to do that, | |
39 | * let's simply make sure that the decompressor never overwrites any bytes | |
40 | * of the payload which it is currently reading. | |
41 | * | |
42 | * Now we have enough information to calculate the safety margin. We need | |
43 | * - 22 bytes for the .zst file format headers; | |
44 | * - 3 bytes per every 128 KiB of uncompressed size (one block header per | |
45 | * block); and | |
46 | * - 128 KiB (biggest possible zstd block size) to make sure that the | |
47 | * decompressor never overwrites anything from the block it is currently | |
48 | * reading. | |
49 | * | |
50 | * We get the following formula: | |
51 | * | |
52 | * safety_margin = 22 + uncompressed_size * 3 / 131072 + 131072 | |
53 | * <= 22 + (uncompressed_size >> 15) + 131072 | |
54 | */ | |
55 | ||
56 | /* | |
57 | * Preboot environments #include "path/to/decompress_unzstd.c". | |
58 | * All of the source files we depend on must be #included. | |
05911c5d | 59 | * zstd's only source dependency is xxhash, which has no source |
4963bb2b NT |
60 | * dependencies. |
61 | * | |
62 | * When UNZSTD_PREBOOT is defined we declare __decompress(), which is | |
63 | * used for kernel decompression, instead of unzstd(). | |
64 | * | |
65 | * Define __DISABLE_EXPORTS in preboot environments to prevent symbols | |
66 | * from xxhash and zstd from being exported by the EXPORT_SYMBOL macro. | |
67 | */ | |
68 | #ifdef STATIC | |
69 | # define UNZSTD_PREBOOT | |
70 | # include "xxhash.c" | |
2479b523 | 71 | # include "zstd/decompress_sources.h" |
00444448 AB |
72 | #else |
73 | #include <linux/decompress/unzstd.h> | |
4963bb2b NT |
74 | #endif |
75 | ||
76 | #include <linux/decompress/mm.h> | |
77 | #include <linux/kernel.h> | |
78 | #include <linux/zstd.h> | |
79 | ||
80 | /* 128MB is the maximum window size supported by zstd. */ | |
81 | #define ZSTD_WINDOWSIZE_MAX (1 << ZSTD_WINDOWLOG_MAX) | |
82 | /* | |
83 | * Size of the input and output buffers in multi-call mode. | |
84 | * Pick a larger size because it isn't used during kernel decompression, | |
85 | * since that is single pass, and we have to allocate a large buffer for | |
86 | * zstd's window anyway. The larger size speeds up initramfs decompression. | |
87 | */ | |
88 | #define ZSTD_IOBUF_SIZE (1 << 17) | |
89 | ||
90 | static int INIT handle_zstd_error(size_t ret, void (*error)(char *x)) | |
91 | { | |
cf30f6a5 | 92 | const zstd_error_code err = zstd_get_error_code(ret); |
4963bb2b | 93 | |
cf30f6a5 | 94 | if (!zstd_is_error(ret)) |
4963bb2b NT |
95 | return 0; |
96 | ||
cf30f6a5 NT |
97 | /* |
98 | * zstd_get_error_name() cannot be used because error takes a char * | |
99 | * not a const char * | |
100 | */ | |
4963bb2b NT |
101 | switch (err) { |
102 | case ZSTD_error_memory_allocation: | |
103 | error("ZSTD decompressor ran out of memory"); | |
104 | break; | |
105 | case ZSTD_error_prefix_unknown: | |
106 | error("Input is not in the ZSTD format (wrong magic bytes)"); | |
107 | break; | |
108 | case ZSTD_error_dstSize_tooSmall: | |
109 | case ZSTD_error_corruption_detected: | |
110 | case ZSTD_error_checksum_wrong: | |
111 | error("ZSTD-compressed data is corrupt"); | |
112 | break; | |
113 | default: | |
114 | error("ZSTD-compressed data is probably corrupt"); | |
115 | break; | |
116 | } | |
117 | return -1; | |
118 | } | |
119 | ||
120 | /* | |
121 | * Handle the case where we have the entire input and output in one segment. | |
122 | * We can allocate less memory (no circular buffer for the sliding window), | |
123 | * and avoid some memcpy() calls. | |
124 | */ | |
125 | static int INIT decompress_single(const u8 *in_buf, long in_len, u8 *out_buf, | |
126 | long out_len, long *in_pos, | |
127 | void (*error)(char *x)) | |
128 | { | |
cf30f6a5 | 129 | const size_t wksp_size = zstd_dctx_workspace_bound(); |
4963bb2b | 130 | void *wksp = large_malloc(wksp_size); |
cf30f6a5 | 131 | zstd_dctx *dctx = zstd_init_dctx(wksp, wksp_size); |
4963bb2b NT |
132 | int err; |
133 | size_t ret; | |
134 | ||
135 | if (dctx == NULL) { | |
cf30f6a5 | 136 | error("Out of memory while allocating zstd_dctx"); |
4963bb2b NT |
137 | err = -1; |
138 | goto out; | |
139 | } | |
140 | /* | |
141 | * Find out how large the frame actually is, there may be junk at | |
cf30f6a5 | 142 | * the end of the frame that zstd_decompress_dctx() can't handle. |
4963bb2b | 143 | */ |
cf30f6a5 | 144 | ret = zstd_find_frame_compressed_size(in_buf, in_len); |
4963bb2b NT |
145 | err = handle_zstd_error(ret, error); |
146 | if (err) | |
147 | goto out; | |
148 | in_len = (long)ret; | |
149 | ||
cf30f6a5 | 150 | ret = zstd_decompress_dctx(dctx, out_buf, out_len, in_buf, in_len); |
4963bb2b NT |
151 | err = handle_zstd_error(ret, error); |
152 | if (err) | |
153 | goto out; | |
154 | ||
155 | if (in_pos != NULL) | |
156 | *in_pos = in_len; | |
157 | ||
158 | err = 0; | |
159 | out: | |
160 | if (wksp != NULL) | |
161 | large_free(wksp); | |
162 | return err; | |
163 | } | |
164 | ||
165 | static int INIT __unzstd(unsigned char *in_buf, long in_len, | |
166 | long (*fill)(void*, unsigned long), | |
167 | long (*flush)(void*, unsigned long), | |
168 | unsigned char *out_buf, long out_len, | |
169 | long *in_pos, | |
170 | void (*error)(char *x)) | |
171 | { | |
cf30f6a5 NT |
172 | zstd_in_buffer in; |
173 | zstd_out_buffer out; | |
174 | zstd_frame_header header; | |
4963bb2b NT |
175 | void *in_allocated = NULL; |
176 | void *out_allocated = NULL; | |
177 | void *wksp = NULL; | |
178 | size_t wksp_size; | |
cf30f6a5 | 179 | zstd_dstream *dstream; |
4963bb2b NT |
180 | int err; |
181 | size_t ret; | |
182 | ||
1c4dd334 PC |
183 | /* |
184 | * ZSTD decompression code won't be happy if the buffer size is so big | |
185 | * that its end address overflows. When the size is not provided, make | |
186 | * it as big as possible without having the end address overflow. | |
187 | */ | |
4963bb2b | 188 | if (out_len == 0) |
1c4dd334 | 189 | out_len = UINTPTR_MAX - (uintptr_t)out_buf; |
4963bb2b NT |
190 | |
191 | if (fill == NULL && flush == NULL) | |
192 | /* | |
193 | * We can decompress faster and with less memory when we have a | |
194 | * single chunk. | |
195 | */ | |
196 | return decompress_single(in_buf, in_len, out_buf, out_len, | |
197 | in_pos, error); | |
198 | ||
199 | /* | |
200 | * If in_buf is not provided, we must be using fill(), so allocate | |
201 | * a large enough buffer. If it is provided, it must be at least | |
202 | * ZSTD_IOBUF_SIZE large. | |
203 | */ | |
204 | if (in_buf == NULL) { | |
205 | in_allocated = large_malloc(ZSTD_IOBUF_SIZE); | |
206 | if (in_allocated == NULL) { | |
207 | error("Out of memory while allocating input buffer"); | |
208 | err = -1; | |
209 | goto out; | |
210 | } | |
211 | in_buf = in_allocated; | |
212 | in_len = 0; | |
213 | } | |
214 | /* Read the first chunk, since we need to decode the frame header. */ | |
215 | if (fill != NULL) | |
216 | in_len = fill(in_buf, ZSTD_IOBUF_SIZE); | |
217 | if (in_len < 0) { | |
218 | error("ZSTD-compressed data is truncated"); | |
219 | err = -1; | |
220 | goto out; | |
221 | } | |
222 | /* Set the first non-empty input buffer. */ | |
223 | in.src = in_buf; | |
224 | in.pos = 0; | |
225 | in.size = in_len; | |
226 | /* Allocate the output buffer if we are using flush(). */ | |
227 | if (flush != NULL) { | |
228 | out_allocated = large_malloc(ZSTD_IOBUF_SIZE); | |
229 | if (out_allocated == NULL) { | |
230 | error("Out of memory while allocating output buffer"); | |
231 | err = -1; | |
232 | goto out; | |
233 | } | |
234 | out_buf = out_allocated; | |
235 | out_len = ZSTD_IOBUF_SIZE; | |
236 | } | |
237 | /* Set the output buffer. */ | |
238 | out.dst = out_buf; | |
239 | out.pos = 0; | |
240 | out.size = out_len; | |
241 | ||
242 | /* | |
cf30f6a5 | 243 | * We need to know the window size to allocate the zstd_dstream. |
4963bb2b NT |
244 | * Since we are streaming, we need to allocate a buffer for the sliding |
245 | * window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX | |
246 | * (8 MB), so it is important to use the actual value so as not to | |
247 | * waste memory when it is smaller. | |
248 | */ | |
cf30f6a5 | 249 | ret = zstd_get_frame_header(&header, in.src, in.size); |
4963bb2b NT |
250 | err = handle_zstd_error(ret, error); |
251 | if (err) | |
252 | goto out; | |
253 | if (ret != 0) { | |
254 | error("ZSTD-compressed data has an incomplete frame header"); | |
255 | err = -1; | |
256 | goto out; | |
257 | } | |
cf30f6a5 | 258 | if (header.windowSize > ZSTD_WINDOWSIZE_MAX) { |
4963bb2b NT |
259 | error("ZSTD-compressed data has too large a window size"); |
260 | err = -1; | |
261 | goto out; | |
262 | } | |
263 | ||
264 | /* | |
cf30f6a5 | 265 | * Allocate the zstd_dstream now that we know how much memory is |
4963bb2b NT |
266 | * required. |
267 | */ | |
cf30f6a5 | 268 | wksp_size = zstd_dstream_workspace_bound(header.windowSize); |
4963bb2b | 269 | wksp = large_malloc(wksp_size); |
cf30f6a5 | 270 | dstream = zstd_init_dstream(header.windowSize, wksp, wksp_size); |
4963bb2b NT |
271 | if (dstream == NULL) { |
272 | error("Out of memory while allocating ZSTD_DStream"); | |
273 | err = -1; | |
274 | goto out; | |
275 | } | |
276 | ||
277 | /* | |
278 | * Decompression loop: | |
279 | * Read more data if necessary (error if no more data can be read). | |
280 | * Call the decompression function, which returns 0 when finished. | |
281 | * Flush any data produced if using flush(). | |
282 | */ | |
283 | if (in_pos != NULL) | |
284 | *in_pos = 0; | |
285 | do { | |
286 | /* | |
287 | * If we need to reload data, either we have fill() and can | |
288 | * try to get more data, or we don't and the input is truncated. | |
289 | */ | |
290 | if (in.pos == in.size) { | |
291 | if (in_pos != NULL) | |
292 | *in_pos += in.pos; | |
293 | in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1; | |
294 | if (in_len < 0) { | |
295 | error("ZSTD-compressed data is truncated"); | |
296 | err = -1; | |
297 | goto out; | |
298 | } | |
299 | in.pos = 0; | |
300 | in.size = in_len; | |
301 | } | |
302 | /* Returns zero when the frame is complete. */ | |
cf30f6a5 | 303 | ret = zstd_decompress_stream(dstream, &out, &in); |
4963bb2b NT |
304 | err = handle_zstd_error(ret, error); |
305 | if (err) | |
306 | goto out; | |
307 | /* Flush all of the data produced if using flush(). */ | |
308 | if (flush != NULL && out.pos > 0) { | |
309 | if (out.pos != flush(out.dst, out.pos)) { | |
310 | error("Failed to flush()"); | |
311 | err = -1; | |
312 | goto out; | |
313 | } | |
314 | out.pos = 0; | |
315 | } | |
316 | } while (ret != 0); | |
317 | ||
318 | if (in_pos != NULL) | |
319 | *in_pos += in.pos; | |
320 | ||
321 | err = 0; | |
322 | out: | |
323 | if (in_allocated != NULL) | |
324 | large_free(in_allocated); | |
325 | if (out_allocated != NULL) | |
326 | large_free(out_allocated); | |
327 | if (wksp != NULL) | |
328 | large_free(wksp); | |
329 | return err; | |
330 | } | |
331 | ||
332 | #ifndef UNZSTD_PREBOOT | |
333 | STATIC int INIT unzstd(unsigned char *buf, long len, | |
334 | long (*fill)(void*, unsigned long), | |
335 | long (*flush)(void*, unsigned long), | |
336 | unsigned char *out_buf, | |
337 | long *pos, | |
338 | void (*error)(char *x)) | |
339 | { | |
340 | return __unzstd(buf, len, fill, flush, out_buf, 0, pos, error); | |
341 | } | |
342 | #else | |
343 | STATIC int INIT __decompress(unsigned char *buf, long len, | |
344 | long (*fill)(void*, unsigned long), | |
345 | long (*flush)(void*, unsigned long), | |
346 | unsigned char *out_buf, long out_len, | |
347 | long *pos, | |
348 | void (*error)(char *x)) | |
349 | { | |
350 | return __unzstd(buf, len, fill, flush, out_buf, out_len, pos, error); | |
351 | } | |
352 | #endif |