Line 0
Link Here
|
|
|
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 |
* |
19 |
* The structure of the .zst file in case of a compresed kernel is as follows. |
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. |
59 |
* zstd's only source dependeny is xxhash, which has no source |
60 |
* dependencies. |
61 |
* |
62 |
* zstd and xxhash avoid declaring themselves as modules |
63 |
* when ZSTD_PREBOOT and XXH_PREBOOT are defined. |
64 |
*/ |
65 |
#ifdef STATIC |
66 |
# define ZSTD_PREBOOT |
67 |
# define XXH_PREBOOT |
68 |
# include "xxhash.c" |
69 |
# include "zstd/entropy_common.c" |
70 |
# include "zstd/fse_decompress.c" |
71 |
# include "zstd/huf_decompress.c" |
72 |
# include "zstd/zstd_common.c" |
73 |
# include "zstd/decompress.c" |
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 |
/* Size of the input and output buffers in multi-call mode. |
83 |
* Pick a larger size because it isn't used during kernel decompression, |
84 |
* since that is single pass, and we have to allocate a large buffer for |
85 |
* zstd's window anyways. The larger size speeds up initramfs decompression. |
86 |
*/ |
87 |
#define ZSTD_IOBUF_SIZE (1 << 17) |
88 |
|
89 |
static int INIT handle_zstd_error(size_t ret, void (*error)(char *x)) |
90 |
{ |
91 |
const int err = ZSTD_getErrorCode(ret); |
92 |
|
93 |
if (!ZSTD_isError(ret)) |
94 |
return 0; |
95 |
|
96 |
switch (err) { |
97 |
case ZSTD_error_memory_allocation: |
98 |
error("ZSTD decompressor ran out of memory"); |
99 |
break; |
100 |
case ZSTD_error_prefix_unknown: |
101 |
error("Input is not in the ZSTD format (wrong magic bytes)"); |
102 |
break; |
103 |
case ZSTD_error_dstSize_tooSmall: |
104 |
case ZSTD_error_corruption_detected: |
105 |
case ZSTD_error_checksum_wrong: |
106 |
error("ZSTD-compressed data is corrupt"); |
107 |
break; |
108 |
default: |
109 |
error("ZSTD-compressed data is probably corrupt"); |
110 |
break; |
111 |
} |
112 |
return -1; |
113 |
} |
114 |
|
115 |
/* |
116 |
* Handle the case where we have the entire input and output in one segment. |
117 |
* We can allocate less memory (no circular buffer for the sliding window), |
118 |
* and avoid some memcpy() calls. |
119 |
*/ |
120 |
static int INIT decompress_single(const u8 *in_buf, long in_len, u8 *out_buf, |
121 |
long out_len, long *in_pos, |
122 |
void (*error)(char *x)) |
123 |
{ |
124 |
const size_t wksp_size = ZSTD_DCtxWorkspaceBound(); |
125 |
void *wksp = large_malloc(wksp_size); |
126 |
ZSTD_DCtx *dctx = ZSTD_initDCtx(wksp, wksp_size); |
127 |
int err; |
128 |
size_t ret; |
129 |
|
130 |
if (dctx == NULL) { |
131 |
error("Out of memory while allocating ZSTD_DCtx"); |
132 |
err = -1; |
133 |
goto out; |
134 |
} |
135 |
/* |
136 |
* Find out how large the frame actually is, there may be junk at |
137 |
* the end of the frame that ZSTD_decompressDCtx() can't handle. |
138 |
*/ |
139 |
ret = ZSTD_findFrameCompressedSize(in_buf, in_len); |
140 |
err = handle_zstd_error(ret, error); |
141 |
if (err) |
142 |
goto out; |
143 |
in_len = (long)ret; |
144 |
|
145 |
ret = ZSTD_decompressDCtx(dctx, out_buf, out_len, in_buf, in_len); |
146 |
err = handle_zstd_error(ret, error); |
147 |
if (err) |
148 |
goto out; |
149 |
|
150 |
if (in_pos != NULL) |
151 |
*in_pos = in_len; |
152 |
|
153 |
err = 0; |
154 |
out: |
155 |
if (wksp != NULL) |
156 |
large_free(wksp); |
157 |
return err; |
158 |
} |
159 |
|
160 |
static int INIT __unzstd(unsigned char *in_buf, long in_len, |
161 |
long (*fill)(void*, unsigned long), |
162 |
long (*flush)(void*, unsigned long), |
163 |
unsigned char *out_buf, long out_len, |
164 |
long *in_pos, |
165 |
void (*error)(char *x)) |
166 |
{ |
167 |
ZSTD_inBuffer in; |
168 |
ZSTD_outBuffer out; |
169 |
ZSTD_frameParams params; |
170 |
void *in_allocated = NULL; |
171 |
void *out_allocated = NULL; |
172 |
void *wksp = NULL; |
173 |
size_t wksp_size; |
174 |
ZSTD_DStream *dstream; |
175 |
int err; |
176 |
size_t ret; |
177 |
|
178 |
if (out_len == 0) |
179 |
out_len = LONG_MAX; /* no limit */ |
180 |
|
181 |
if (fill == NULL && flush == NULL) |
182 |
/* |
183 |
* We can decompress faster and with less memory when we have a |
184 |
* single chunk. |
185 |
*/ |
186 |
return decompress_single(in_buf, in_len, out_buf, out_len, |
187 |
in_pos, error); |
188 |
|
189 |
/* |
190 |
* If in_buf is not provided, we must be using fill(), so allocate |
191 |
* a large enough buffer. If it is provided, it must be at least |
192 |
* ZSTD_IOBUF_SIZE large. |
193 |
*/ |
194 |
if (in_buf == NULL) { |
195 |
in_allocated = large_malloc(ZSTD_IOBUF_SIZE); |
196 |
if (in_allocated == NULL) { |
197 |
error("Out of memory while allocating input buffer"); |
198 |
err = -1; |
199 |
goto out; |
200 |
} |
201 |
in_buf = in_allocated; |
202 |
in_len = 0; |
203 |
} |
204 |
/* Read the first chunk, since we need to decode the frame header. */ |
205 |
if (fill != NULL) |
206 |
in_len = fill(in_buf, ZSTD_IOBUF_SIZE); |
207 |
if (in_len < 0) { |
208 |
error("ZSTD-compressed data is truncated"); |
209 |
err = -1; |
210 |
goto out; |
211 |
} |
212 |
/* Set the first non-empty input buffer. */ |
213 |
in.src = in_buf; |
214 |
in.pos = 0; |
215 |
in.size = in_len; |
216 |
/* Allocate the output buffer if we are using flush(). */ |
217 |
if (flush != NULL) { |
218 |
out_allocated = large_malloc(ZSTD_IOBUF_SIZE); |
219 |
if (out_allocated == NULL) { |
220 |
error("Out of memory while allocating output buffer"); |
221 |
err = -1; |
222 |
goto out; |
223 |
} |
224 |
out_buf = out_allocated; |
225 |
out_len = ZSTD_IOBUF_SIZE; |
226 |
} |
227 |
/* Set the output buffer. */ |
228 |
out.dst = out_buf; |
229 |
out.pos = 0; |
230 |
out.size = out_len; |
231 |
|
232 |
/* |
233 |
* We need to know the window size to allocate the ZSTD_DStream. |
234 |
* Since we are streaming, we need to allocate a buffer for the sliding |
235 |
* window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX |
236 |
* (8 MB), so it is important to use the actual value so as not to |
237 |
* waste memory when it is smaller. |
238 |
*/ |
239 |
ret = ZSTD_getFrameParams(¶ms, in.src, in.size); |
240 |
err = handle_zstd_error(ret, error); |
241 |
if (err) |
242 |
goto out; |
243 |
if (ret != 0) { |
244 |
error("ZSTD-compressed data has an incomplete frame header"); |
245 |
err = -1; |
246 |
goto out; |
247 |
} |
248 |
if (params.windowSize > ZSTD_WINDOWSIZE_MAX) { |
249 |
error("ZSTD-compressed data has too large a window size"); |
250 |
err = -1; |
251 |
goto out; |
252 |
} |
253 |
|
254 |
/* |
255 |
* Allocate the ZSTD_DStream now that we know how much memory is |
256 |
* required. |
257 |
*/ |
258 |
wksp_size = ZSTD_DStreamWorkspaceBound(params.windowSize); |
259 |
wksp = large_malloc(wksp_size); |
260 |
dstream = ZSTD_initDStream(params.windowSize, wksp, wksp_size); |
261 |
if (dstream == NULL) { |
262 |
error("Out of memory while allocating ZSTD_DStream"); |
263 |
err = -1; |
264 |
goto out; |
265 |
} |
266 |
|
267 |
/* |
268 |
* Decompression loop: |
269 |
* Read more data if necessary (error if no more data can be read). |
270 |
* Call the decompression function, which returns 0 when finished. |
271 |
* Flush any data produced if using flush(). |
272 |
*/ |
273 |
if (in_pos != NULL) |
274 |
*in_pos = 0; |
275 |
do { |
276 |
/* |
277 |
* If we need to reload data, either we have fill() and can |
278 |
* try to get more data, or we don't and the input is truncated. |
279 |
*/ |
280 |
if (in.pos == in.size) { |
281 |
if (in_pos != NULL) |
282 |
*in_pos += in.pos; |
283 |
in_len = fill ? fill(in_buf, ZSTD_IOBUF_SIZE) : -1; |
284 |
if (in_len < 0) { |
285 |
error("ZSTD-compressed data is truncated"); |
286 |
err = -1; |
287 |
goto out; |
288 |
} |
289 |
in.pos = 0; |
290 |
in.size = in_len; |
291 |
} |
292 |
/* Returns zero when the frame is complete. */ |
293 |
ret = ZSTD_decompressStream(dstream, &out, &in); |
294 |
err = handle_zstd_error(ret, error); |
295 |
if (err) |
296 |
goto out; |
297 |
/* Flush all of the data produced if using flush(). */ |
298 |
if (flush != NULL && out.pos > 0) { |
299 |
if (out.pos != flush(out.dst, out.pos)) { |
300 |
error("Failed to flush()"); |
301 |
err = -1; |
302 |
goto out; |
303 |
} |
304 |
out.pos = 0; |
305 |
} |
306 |
} while (ret != 0); |
307 |
|
308 |
if (in_pos != NULL) |
309 |
*in_pos += in.pos; |
310 |
|
311 |
err = 0; |
312 |
out: |
313 |
if (in_allocated != NULL) |
314 |
large_free(in_allocated); |
315 |
if (out_allocated != NULL) |
316 |
large_free(out_allocated); |
317 |
if (wksp != NULL) |
318 |
large_free(wksp); |
319 |
return err; |
320 |
} |
321 |
|
322 |
#ifndef ZSTD_PREBOOT |
323 |
STATIC int INIT unzstd(unsigned char *buf, long len, |
324 |
long (*fill)(void*, unsigned long), |
325 |
long (*flush)(void*, unsigned long), |
326 |
unsigned char *out_buf, |
327 |
long *pos, |
328 |
void (*error)(char *x)) |
329 |
{ |
330 |
return __unzstd(buf, len, fill, flush, out_buf, 0, pos, error); |
331 |
} |
332 |
#else |
333 |
STATIC int INIT __decompress(unsigned char *buf, long len, |
334 |
long (*fill)(void*, unsigned long), |
335 |
long (*flush)(void*, unsigned long), |
336 |
unsigned char *out_buf, long out_len, |
337 |
long *pos, |
338 |
void (*error)(char *x)) |
339 |
{ |
340 |
return __unzstd(buf, len, fill, flush, out_buf, out_len, pos, error); |
341 |
} |
342 |
#endif |