1 /* Copyright (c) Mark Harmstone 2016-17
2  * Copyright (c) Reimar Doeffinger 2006
3  * Copyright (c) Markus Oberhumer 1996
4  *
5  * This file is part of WinBtrfs.
6  *
7  * WinBtrfs is free software: you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public Licence as published by
9  * the Free Software Foundation, either version 3 of the Licence, or
10  * (at your option) any later version.
11  *
12  * WinBtrfs is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public Licence for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public Licence
18  * along with WinBtrfs.  If not, see <http://www.gnu.org/licenses/>. */
19 
20 // Portions of the LZO decompression code here were cribbed from code in
21 // libavcodec, also under the LGPL. Thank you, Reimar Doeffinger.
22 
23 // The LZO compression code comes from v0.22 of lzo, written way back in
24 // 1996, and available here:
25 // https://www.ibiblio.org/pub/historic-linux/ftp-archives/sunsite.unc.edu/Sep-29-1996/libs/lzo-0.22.tar.gz
26 // Modern versions of lzo are licensed under the GPL, but the very oldest
27 // versions are under the LGPL and hence okay to use here.
28 
29 #include "btrfs_drv.h"
30 
31 #define Z_SOLO
32 #define ZLIB_INTERNAL
33 
34 #ifndef __REACTOS__
35 #include "zlib/zlib.h"
36 #include "zlib/inftrees.h"
37 #include "zlib/inflate.h"
38 #else
39 #include <zlib.h>
40 #endif // __REACTOS__
41 
42 #define ZSTD_STATIC_LINKING_ONLY
43 
44 #include "zstd/zstd.h"
45 
46 #define LZO_PAGE_SIZE 4096
47 
48 typedef struct {
49     uint8_t* in;
50     uint32_t inlen;
51     uint32_t inpos;
52     uint8_t* out;
53     uint32_t outlen;
54     uint32_t outpos;
55     bool error;
56     void* wrkmem;
57 } lzo_stream;
58 
59 #define LZO1X_MEM_COMPRESS ((uint32_t) (16384L * sizeof(uint8_t*)))
60 
61 #define M1_MAX_OFFSET 0x0400
62 #define M2_MAX_OFFSET 0x0800
63 #define M3_MAX_OFFSET 0x4000
64 #define M4_MAX_OFFSET 0xbfff
65 
66 #define MX_MAX_OFFSET (M1_MAX_OFFSET + M2_MAX_OFFSET)
67 
68 #define M1_MARKER 0
69 #define M2_MARKER 64
70 #define M3_MARKER 32
71 #define M4_MARKER 16
72 
73 #define _DV2(p, shift1, shift2) (((( (uint32_t)(p[2]) << shift1) ^ p[1]) << shift2) ^ p[0])
74 #define DVAL_NEXT(dv, p) dv ^= p[-1]; dv = (((dv) >> 5) ^ ((uint32_t)(p[2]) << (2*5)))
75 #define _DV(p, shift) _DV2(p, shift, shift)
76 #define DVAL_FIRST(dv, p) dv = _DV((p), 5)
77 #define _DINDEX(dv, p) ((40799u * (dv)) >> 5)
78 #define DINDEX(dv, p) (((_DINDEX(dv, p)) & 0x3fff) << 0)
79 #define UPDATE_D(dict, cycle, dv, p) dict[DINDEX(dv, p)] = (p)
80 #define UPDATE_I(dict, cycle, index, p) dict[index] = (p)
81 
82 #define LZO_CHECK_MPOS_NON_DET(m_pos, m_off, in, ip, max_offset) \
83     ((void*) m_pos < (void*) in || \
84     (m_off = (uint8_t*) ip - (uint8_t*) m_pos) <= 0 || \
85     m_off > max_offset)
86 
87 #define LZO_BYTE(x) ((unsigned char) (x))
88 
89 #define ZSTD_ALLOC_TAG 0x6474737a // "zstd"
90 
91 // needs to be the same as Linux (fs/btrfs/zstd.c)
92 #define ZSTD_BTRFS_MAX_WINDOWLOG 17
93 
94 static void* zstd_malloc(void* opaque, size_t size);
95 static void zstd_free(void* opaque, void* address);
96 
97 #ifndef __REACTOS__
98 ZSTD_customMem zstd_mem = { .customAlloc = zstd_malloc, .customFree = zstd_free, .opaque = NULL };
99 #else
100 ZSTD_customMem zstd_mem = { zstd_malloc, zstd_free, NULL };
101 #endif
102 
lzo_nextbyte(lzo_stream * stream)103 static uint8_t lzo_nextbyte(lzo_stream* stream) {
104     uint8_t c;
105 
106     if (stream->inpos >= stream->inlen) {
107         stream->error = true;
108         return 0;
109     }
110 
111     c = stream->in[stream->inpos];
112     stream->inpos++;
113 
114     return c;
115 }
116 
lzo_len(lzo_stream * stream,int byte,int mask)117 static int lzo_len(lzo_stream* stream, int byte, int mask) {
118     int len = byte & mask;
119 
120     if (len == 0) {
121         while (!(byte = lzo_nextbyte(stream))) {
122             if (stream->error) return 0;
123 
124             len += 255;
125         }
126 
127         len += mask + byte;
128     }
129 
130     return len;
131 }
132 
lzo_copy(lzo_stream * stream,int len)133 static void lzo_copy(lzo_stream* stream, int len) {
134     if (stream->inpos + len > stream->inlen) {
135         stream->error = true;
136         return;
137     }
138 
139     if (stream->outpos + len > stream->outlen) {
140         stream->error = true;
141         return;
142     }
143 
144     do {
145         stream->out[stream->outpos] = stream->in[stream->inpos];
146         stream->inpos++;
147         stream->outpos++;
148         len--;
149     } while (len > 0);
150 }
151 
lzo_copyback(lzo_stream * stream,uint32_t back,int len)152 static void lzo_copyback(lzo_stream* stream, uint32_t back, int len) {
153     if (stream->outpos < back) {
154         stream->error = true;
155         return;
156     }
157 
158     if (stream->outpos + len > stream->outlen) {
159         stream->error = true;
160         return;
161     }
162 
163     do {
164         stream->out[stream->outpos] = stream->out[stream->outpos - back];
165         stream->outpos++;
166         len--;
167     } while (len > 0);
168 }
169 
do_lzo_decompress(lzo_stream * stream)170 static NTSTATUS do_lzo_decompress(lzo_stream* stream) {
171     uint8_t byte;
172     uint32_t len, back;
173     bool backcopy = false;
174 
175     stream->error = false;
176 
177     byte = lzo_nextbyte(stream);
178     if (stream->error) return STATUS_INTERNAL_ERROR;
179 
180     if (byte > 17) {
181         lzo_copy(stream, min((uint8_t)(byte - 17), (uint32_t)(stream->outlen - stream->outpos)));
182         if (stream->error) return STATUS_INTERNAL_ERROR;
183 
184         if (stream->outlen == stream->outpos)
185             return STATUS_SUCCESS;
186 
187         byte = lzo_nextbyte(stream);
188         if (stream->error) return STATUS_INTERNAL_ERROR;
189 
190         if (byte < 16) return STATUS_INTERNAL_ERROR;
191     }
192 
193     while (1) {
194         if (byte >> 4) {
195             backcopy = true;
196             if (byte >> 6) {
197                 len = (byte >> 5) - 1;
198                 back = (lzo_nextbyte(stream) << 3) + ((byte >> 2) & 7) + 1;
199                 if (stream->error) return STATUS_INTERNAL_ERROR;
200             } else if (byte >> 5) {
201                 len = lzo_len(stream, byte, 31);
202                 if (stream->error) return STATUS_INTERNAL_ERROR;
203 
204                 byte = lzo_nextbyte(stream);
205                 if (stream->error) return STATUS_INTERNAL_ERROR;
206 
207                 back = (lzo_nextbyte(stream) << 6) + (byte >> 2) + 1;
208                 if (stream->error) return STATUS_INTERNAL_ERROR;
209             } else {
210                 len = lzo_len(stream, byte, 7);
211                 if (stream->error) return STATUS_INTERNAL_ERROR;
212 
213                 back = (1 << 14) + ((byte & 8) << 11);
214 
215                 byte = lzo_nextbyte(stream);
216                 if (stream->error) return STATUS_INTERNAL_ERROR;
217 
218                 back += (lzo_nextbyte(stream) << 6) + (byte >> 2);
219                 if (stream->error) return STATUS_INTERNAL_ERROR;
220 
221                 if (back == (1 << 14)) {
222                     if (len != 1)
223                         return STATUS_INTERNAL_ERROR;
224                     break;
225                 }
226             }
227         } else if (backcopy) {
228             len = 0;
229             back = (lzo_nextbyte(stream) << 2) + (byte >> 2) + 1;
230             if (stream->error) return STATUS_INTERNAL_ERROR;
231         } else {
232             len = lzo_len(stream, byte, 15);
233             if (stream->error) return STATUS_INTERNAL_ERROR;
234 
235             lzo_copy(stream, min(len + 3, stream->outlen - stream->outpos));
236             if (stream->error) return STATUS_INTERNAL_ERROR;
237 
238             if (stream->outlen == stream->outpos)
239                 return STATUS_SUCCESS;
240 
241             byte = lzo_nextbyte(stream);
242             if (stream->error) return STATUS_INTERNAL_ERROR;
243 
244             if (byte >> 4)
245                 continue;
246 
247             len = 1;
248             back = (1 << 11) + (lzo_nextbyte(stream) << 2) + (byte >> 2) + 1;
249             if (stream->error) return STATUS_INTERNAL_ERROR;
250 
251             break;
252         }
253 
254         lzo_copyback(stream, back, min(len + 2, stream->outlen - stream->outpos));
255         if (stream->error) return STATUS_INTERNAL_ERROR;
256 
257         if (stream->outlen == stream->outpos)
258             return STATUS_SUCCESS;
259 
260         len = byte & 3;
261 
262         if (len) {
263             lzo_copy(stream, min(len, stream->outlen - stream->outpos));
264             if (stream->error) return STATUS_INTERNAL_ERROR;
265 
266             if (stream->outlen == stream->outpos)
267                 return STATUS_SUCCESS;
268         } else
269             backcopy = !backcopy;
270 
271         byte = lzo_nextbyte(stream);
272         if (stream->error) return STATUS_INTERNAL_ERROR;
273     }
274 
275     return STATUS_SUCCESS;
276 }
277 
lzo_decompress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen,uint32_t inpageoff)278 NTSTATUS lzo_decompress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen, uint32_t inpageoff) {
279     NTSTATUS Status;
280     uint32_t partlen, inoff, outoff;
281     lzo_stream stream;
282 
283     inoff = 0;
284     outoff = 0;
285 
286     do {
287         partlen = *(uint32_t*)&inbuf[inoff];
288 
289         if (partlen + inoff > inlen) {
290             ERR("overflow: %x + %x > %x\n", partlen, inoff, inlen);
291             return STATUS_INTERNAL_ERROR;
292         }
293 
294         inoff += sizeof(uint32_t);
295 
296         stream.in = &inbuf[inoff];
297         stream.inlen = partlen;
298         stream.inpos = 0;
299         stream.out = &outbuf[outoff];
300         stream.outlen = min(outlen, LZO_PAGE_SIZE);
301         stream.outpos = 0;
302 
303         Status = do_lzo_decompress(&stream);
304         if (!NT_SUCCESS(Status)) {
305             ERR("do_lzo_decompress returned %08lx\n", Status);
306             return Status;
307         }
308 
309         if (stream.outpos < stream.outlen)
310             RtlZeroMemory(&stream.out[stream.outpos], stream.outlen - stream.outpos);
311 
312         inoff += partlen;
313         outoff += stream.outlen;
314 
315         if (LZO_PAGE_SIZE - ((inpageoff + inoff) % LZO_PAGE_SIZE) < sizeof(uint32_t))
316             inoff = ((((inpageoff + inoff) / LZO_PAGE_SIZE) + 1) * LZO_PAGE_SIZE) - inpageoff;
317 
318         outlen -= stream.outlen;
319     } while (inoff < inlen && outlen > 0);
320 
321     return STATUS_SUCCESS;
322 }
323 
zlib_alloc(void * opaque,unsigned int items,unsigned int size)324 static void* zlib_alloc(void* opaque, unsigned int items, unsigned int size) {
325     UNUSED(opaque);
326 
327     return ExAllocatePoolWithTag(PagedPool, items * size, ALLOC_TAG_ZLIB);
328 }
329 
zlib_free(void * opaque,void * ptr)330 static void zlib_free(void* opaque, void* ptr) {
331     UNUSED(opaque);
332 
333     ExFreePool(ptr);
334 }
335 
zlib_compress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen,unsigned int level,unsigned int * space_left)336 NTSTATUS zlib_compress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen, unsigned int level, unsigned int* space_left) {
337     z_stream c_stream;
338     int ret;
339 
340     c_stream.zalloc = zlib_alloc;
341     c_stream.zfree = zlib_free;
342     c_stream.opaque = (voidpf)0;
343 
344     ret = deflateInit(&c_stream, level);
345 
346     if (ret != Z_OK) {
347         ERR("deflateInit returned %i\n", ret);
348         return STATUS_INTERNAL_ERROR;
349     }
350 
351     c_stream.next_in = inbuf;
352     c_stream.avail_in = inlen;
353 
354     c_stream.next_out = outbuf;
355     c_stream.avail_out = outlen;
356 
357     do {
358         ret = deflate(&c_stream, Z_FINISH);
359 
360         if (ret != Z_OK && ret != Z_STREAM_END) {
361             ERR("deflate returned %i\n", ret);
362             deflateEnd(&c_stream);
363             return STATUS_INTERNAL_ERROR;
364         }
365 
366         if (c_stream.avail_in == 0 || c_stream.avail_out == 0)
367             break;
368     } while (ret != Z_STREAM_END);
369 
370     deflateEnd(&c_stream);
371 
372     *space_left = c_stream.avail_in > 0 ? 0 : c_stream.avail_out;
373 
374     return STATUS_SUCCESS;
375 }
376 
zlib_decompress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen)377 NTSTATUS zlib_decompress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen) {
378     z_stream c_stream;
379     int ret;
380 
381     c_stream.zalloc = zlib_alloc;
382     c_stream.zfree = zlib_free;
383     c_stream.opaque = (voidpf)0;
384 
385     ret = inflateInit(&c_stream);
386 
387     if (ret != Z_OK) {
388         ERR("inflateInit returned %i\n", ret);
389         return STATUS_INTERNAL_ERROR;
390     }
391 
392     c_stream.next_in = inbuf;
393     c_stream.avail_in = inlen;
394 
395     c_stream.next_out = outbuf;
396     c_stream.avail_out = outlen;
397 
398     do {
399         ret = inflate(&c_stream, Z_NO_FLUSH);
400 
401         if (ret != Z_OK && ret != Z_STREAM_END) {
402             ERR("inflate returned %i\n", ret);
403             inflateEnd(&c_stream);
404             return STATUS_INTERNAL_ERROR;
405         }
406 
407         if (c_stream.avail_out == 0)
408             break;
409     } while (ret != Z_STREAM_END);
410 
411     ret = inflateEnd(&c_stream);
412 
413     if (ret != Z_OK) {
414         ERR("inflateEnd returned %i\n", ret);
415         return STATUS_INTERNAL_ERROR;
416     }
417 
418     // FIXME - if we're short, should we zero the end of outbuf so we don't leak information into userspace?
419 
420     return STATUS_SUCCESS;
421 }
422 
lzo_do_compress(const uint8_t * in,uint32_t in_len,uint8_t * out,uint32_t * out_len,void * wrkmem)423 static NTSTATUS lzo_do_compress(const uint8_t* in, uint32_t in_len, uint8_t* out, uint32_t* out_len, void* wrkmem) {
424     const uint8_t* ip;
425     uint32_t dv;
426     uint8_t* op;
427     const uint8_t* in_end = in + in_len;
428     const uint8_t* ip_end = in + in_len - 9 - 4;
429     const uint8_t* ii;
430     const uint8_t** dict = (const uint8_t**)wrkmem;
431 
432     op = out;
433     ip = in;
434     ii = ip;
435 
436     DVAL_FIRST(dv, ip); UPDATE_D(dict, cycle, dv, ip); ip++;
437     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
438     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
439     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
440 
441     while (1) {
442         const uint8_t* m_pos;
443         uint32_t m_len;
444         ptrdiff_t m_off;
445         uint32_t lit, dindex;
446 
447         dindex = DINDEX(dv, ip);
448         m_pos = dict[dindex];
449         UPDATE_I(dict, cycle, dindex, ip);
450 
451         if (!LZO_CHECK_MPOS_NON_DET(m_pos, m_off, in, ip, M4_MAX_OFFSET) && m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2]) {
452             lit = (uint32_t)(ip - ii);
453             m_pos += 3;
454             if (m_off <= M2_MAX_OFFSET)
455                 goto match;
456 
457             if (lit == 3) { /* better compression, but slower */
458                 if (op - 2 <= out)
459                     return STATUS_INTERNAL_ERROR;
460 
461                 op[-2] |= LZO_BYTE(3);
462                 *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
463                 goto code_match;
464             }
465 
466             if (*m_pos == ip[3])
467                 goto match;
468         }
469 
470         /* a literal */
471         ++ip;
472         if (ip >= ip_end)
473             break;
474         DVAL_NEXT(dv, ip);
475         continue;
476 
477         /* a match */
478 match:
479         /* store current literal run */
480         if (lit > 0) {
481             uint32_t t = lit;
482 
483             if (t <= 3) {
484                 if (op - 2 <= out)
485                     return STATUS_INTERNAL_ERROR;
486 
487                 op[-2] |= LZO_BYTE(t);
488             } else if (t <= 18)
489                 *op++ = LZO_BYTE(t - 3);
490             else {
491                 uint32_t tt = t - 18;
492 
493                 *op++ = 0;
494                 while (tt > 255) {
495                     tt -= 255;
496                     *op++ = 0;
497                 }
498 
499                 if (tt <= 0)
500                     return STATUS_INTERNAL_ERROR;
501 
502                 *op++ = LZO_BYTE(tt);
503             }
504 
505             do {
506                 *op++ = *ii++;
507             } while (--t > 0);
508         }
509 
510 
511         /* code the match */
512 code_match:
513         if (ii != ip)
514             return STATUS_INTERNAL_ERROR;
515 
516         ip += 3;
517         if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ ||
518             *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++) {
519             --ip;
520             m_len = (uint32_t)(ip - ii);
521 
522             if (m_len < 3 || m_len > 8)
523                 return STATUS_INTERNAL_ERROR;
524 
525             if (m_off <= M2_MAX_OFFSET) {
526                 m_off -= 1;
527                 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
528                 *op++ = LZO_BYTE(m_off >> 3);
529             } else if (m_off <= M3_MAX_OFFSET) {
530                 m_off -= 1;
531                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
532                 goto m3_m4_offset;
533             } else {
534                 m_off -= 0x4000;
535 
536                 if (m_off <= 0 || m_off > 0x7fff)
537                     return STATUS_INTERNAL_ERROR;
538 
539                 *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
540                 goto m3_m4_offset;
541             }
542         } else {
543             const uint8_t* end;
544             end = in_end;
545             while (ip < end && *m_pos == *ip)
546                 m_pos++, ip++;
547             m_len = (uint32_t)(ip - ii);
548 
549             if (m_len < 3)
550                 return STATUS_INTERNAL_ERROR;
551 
552             if (m_off <= M3_MAX_OFFSET) {
553                 m_off -= 1;
554                 if (m_len <= 33)
555                     *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
556                 else {
557                     m_len -= 33;
558                     *op++ = M3_MARKER | 0;
559                     goto m3_m4_len;
560                 }
561             } else {
562                 m_off -= 0x4000;
563 
564                 if (m_off <= 0 || m_off > 0x7fff)
565                     return STATUS_INTERNAL_ERROR;
566 
567                 if (m_len <= 9)
568                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
569                 else {
570                     m_len -= 9;
571                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
572 m3_m4_len:
573                     while (m_len > 255) {
574                         m_len -= 255;
575                         *op++ = 0;
576                     }
577 
578                     if (m_len <= 0)
579                         return STATUS_INTERNAL_ERROR;
580 
581                     *op++ = LZO_BYTE(m_len);
582                 }
583             }
584 
585 m3_m4_offset:
586             *op++ = LZO_BYTE((m_off & 63) << 2);
587             *op++ = LZO_BYTE(m_off >> 6);
588         }
589 
590         ii = ip;
591         if (ip >= ip_end)
592             break;
593         DVAL_FIRST(dv, ip);
594     }
595 
596     /* store final literal run */
597     if (in_end - ii > 0) {
598         uint32_t t = (uint32_t)(in_end - ii);
599 
600         if (op == out && t <= 238)
601             *op++ = LZO_BYTE(17 + t);
602         else if (t <= 3)
603             op[-2] |= LZO_BYTE(t);
604         else if (t <= 18)
605             *op++ = LZO_BYTE(t - 3);
606         else {
607             uint32_t tt = t - 18;
608 
609             *op++ = 0;
610             while (tt > 255) {
611                 tt -= 255;
612                 *op++ = 0;
613             }
614 
615             if (tt <= 0)
616                 return STATUS_INTERNAL_ERROR;
617 
618             *op++ = LZO_BYTE(tt);
619         }
620 
621         do {
622             *op++ = *ii++;
623         } while (--t > 0);
624     }
625 
626     *out_len = (uint32_t)(op - out);
627 
628     return STATUS_SUCCESS;
629 }
630 
lzo1x_1_compress(lzo_stream * stream)631 static NTSTATUS lzo1x_1_compress(lzo_stream* stream) {
632     uint8_t *op = stream->out;
633     NTSTATUS Status = STATUS_SUCCESS;
634 
635     if (stream->inlen <= 0)
636         stream->outlen = 0;
637     else if (stream->inlen <= 9 + 4) {
638         *op++ = LZO_BYTE(17 + stream->inlen);
639 
640         stream->inpos = 0;
641         do {
642             *op++ = stream->in[stream->inpos];
643             stream->inpos++;
644         } while (stream->inlen < stream->inpos);
645         stream->outlen = (uint32_t)(op - stream->out);
646     } else
647         Status = lzo_do_compress(stream->in, stream->inlen, stream->out, &stream->outlen, stream->wrkmem);
648 
649     if (Status == STATUS_SUCCESS) {
650         op = stream->out + stream->outlen;
651         *op++ = M4_MARKER | 1;
652         *op++ = 0;
653         *op++ = 0;
654         stream->outlen += 3;
655     }
656 
657     return Status;
658 }
659 
lzo_max_outlen(uint32_t inlen)660 static __inline uint32_t lzo_max_outlen(uint32_t inlen) {
661     return inlen + (inlen / 16) + 64 + 3; // formula comes from LZO.FAQ
662 }
663 
zstd_malloc(void * opaque,size_t size)664 static void* zstd_malloc(void* opaque, size_t size) {
665     UNUSED(opaque);
666 
667     return ExAllocatePoolWithTag(PagedPool, size, ZSTD_ALLOC_TAG);
668 }
669 
zstd_free(void * opaque,void * address)670 static void zstd_free(void* opaque, void* address) {
671     UNUSED(opaque);
672 
673     ExFreePool(address);
674 }
675 
zstd_decompress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen)676 NTSTATUS zstd_decompress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen) {
677     NTSTATUS Status;
678     ZSTD_DStream* stream;
679     size_t init_res, read;
680     ZSTD_inBuffer input;
681     ZSTD_outBuffer output;
682 
683     stream = ZSTD_createDStream_advanced(zstd_mem);
684 
685     if (!stream) {
686         ERR("ZSTD_createDStream failed.\n");
687         return STATUS_INTERNAL_ERROR;
688     }
689 
690     init_res = ZSTD_initDStream(stream);
691 
692     if (ZSTD_isError(init_res)) {
693         ERR("ZSTD_initDStream failed: %s\n", ZSTD_getErrorName(init_res));
694         Status = STATUS_INTERNAL_ERROR;
695         goto end;
696     }
697 
698     input.src = inbuf;
699     input.size = inlen;
700     input.pos = 0;
701 
702     output.dst = outbuf;
703     output.size = outlen;
704     output.pos = 0;
705 
706     do {
707         read = ZSTD_decompressStream(stream, &output, &input);
708 
709         if (ZSTD_isError(read)) {
710             ERR("ZSTD_decompressStream failed: %s\n", ZSTD_getErrorName(read));
711             Status = STATUS_INTERNAL_ERROR;
712             goto end;
713         }
714 
715         if (output.pos == output.size)
716             break;
717     } while (read != 0);
718 
719     Status = STATUS_SUCCESS;
720 
721 end:
722     ZSTD_freeDStream(stream);
723 
724     return Status;
725 }
726 
lzo_compress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen,unsigned int * space_left)727 NTSTATUS lzo_compress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen, unsigned int* space_left) {
728     NTSTATUS Status;
729     unsigned int num_pages;
730     unsigned int comp_data_len;
731     uint8_t* comp_data;
732     lzo_stream stream;
733     uint32_t* out_size;
734 
735     num_pages = (unsigned int)sector_align(inlen, LZO_PAGE_SIZE) / LZO_PAGE_SIZE;
736 
737     // Four-byte overall header
738     // Another four-byte header page
739     // Each page has a maximum size of lzo_max_outlen(LZO_PAGE_SIZE)
740     // Plus another four bytes for possible padding
741     comp_data_len = sizeof(uint32_t) + ((lzo_max_outlen(LZO_PAGE_SIZE) + (2 * sizeof(uint32_t))) * num_pages);
742 
743     // FIXME - can we write this so comp_data isn't necessary?
744 
745     comp_data = ExAllocatePoolWithTag(PagedPool, comp_data_len, ALLOC_TAG);
746     if (!comp_data) {
747         ERR("out of memory\n");
748         return STATUS_INSUFFICIENT_RESOURCES;
749     }
750 
751     stream.wrkmem = ExAllocatePoolWithTag(PagedPool, LZO1X_MEM_COMPRESS, ALLOC_TAG);
752     if (!stream.wrkmem) {
753         ERR("out of memory\n");
754         ExFreePool(comp_data);
755         return STATUS_INSUFFICIENT_RESOURCES;
756     }
757 
758     out_size = (uint32_t*)comp_data;
759     *out_size = sizeof(uint32_t);
760 
761     stream.in = inbuf;
762     stream.out = comp_data + (2 * sizeof(uint32_t));
763 
764     for (unsigned int i = 0; i < num_pages; i++) {
765         uint32_t* pagelen = (uint32_t*)(stream.out - sizeof(uint32_t));
766 
767         stream.inlen = (uint32_t)min(LZO_PAGE_SIZE, outlen - (i * LZO_PAGE_SIZE));
768 
769         Status = lzo1x_1_compress(&stream);
770         if (!NT_SUCCESS(Status)) {
771             ERR("lzo1x_1_compress returned %08lx\n", Status);
772             ExFreePool(comp_data);
773             return Status;
774         }
775 
776         *pagelen = stream.outlen;
777         *out_size += stream.outlen + sizeof(uint32_t);
778 
779         stream.in += LZO_PAGE_SIZE;
780         stream.out += stream.outlen + sizeof(uint32_t);
781 
782         // new page needs to start at a 32-bit boundary
783         if (LZO_PAGE_SIZE - (*out_size % LZO_PAGE_SIZE) < sizeof(uint32_t)) {
784             RtlZeroMemory(stream.out, LZO_PAGE_SIZE - (*out_size % LZO_PAGE_SIZE));
785             stream.out += LZO_PAGE_SIZE - (*out_size % LZO_PAGE_SIZE);
786             *out_size += LZO_PAGE_SIZE - (*out_size % LZO_PAGE_SIZE);
787         }
788     }
789 
790     ExFreePool(stream.wrkmem);
791 
792     if (*out_size >= outlen)
793         *space_left = 0;
794     else {
795         *space_left = outlen - *out_size;
796 
797         RtlCopyMemory(outbuf, comp_data, *out_size);
798     }
799 
800     ExFreePool(comp_data);
801 
802     return STATUS_SUCCESS;
803 }
804 
zstd_compress(uint8_t * inbuf,uint32_t inlen,uint8_t * outbuf,uint32_t outlen,uint32_t level,unsigned int * space_left)805 NTSTATUS zstd_compress(uint8_t* inbuf, uint32_t inlen, uint8_t* outbuf, uint32_t outlen, uint32_t level, unsigned int* space_left) {
806     ZSTD_CStream* stream;
807     size_t init_res, written;
808     ZSTD_inBuffer input;
809     ZSTD_outBuffer output;
810     ZSTD_parameters params;
811 
812     stream = ZSTD_createCStream_advanced(zstd_mem);
813 
814     if (!stream) {
815         ERR("ZSTD_createCStream failed.\n");
816         return STATUS_INTERNAL_ERROR;
817     }
818 
819     params = ZSTD_getParams(level, inlen, 0);
820 
821     if (params.cParams.windowLog > ZSTD_BTRFS_MAX_WINDOWLOG)
822         params.cParams.windowLog = ZSTD_BTRFS_MAX_WINDOWLOG;
823 
824     init_res = ZSTD_initCStream_advanced(stream, NULL, 0, params, inlen);
825 
826     if (ZSTD_isError(init_res)) {
827         ERR("ZSTD_initCStream_advanced failed: %s\n", ZSTD_getErrorName(init_res));
828         ZSTD_freeCStream(stream);
829         return STATUS_INTERNAL_ERROR;
830     }
831 
832     input.src = inbuf;
833     input.size = inlen;
834     input.pos = 0;
835 
836     output.dst = outbuf;
837     output.size = outlen;
838     output.pos = 0;
839 
840     while (input.pos < input.size && output.pos < output.size) {
841         written = ZSTD_compressStream(stream, &output, &input);
842 
843         if (ZSTD_isError(written)) {
844             ERR("ZSTD_compressStream failed: %s\n", ZSTD_getErrorName(written));
845             ZSTD_freeCStream(stream);
846             return STATUS_INTERNAL_ERROR;
847         }
848     }
849 
850     written = ZSTD_endStream(stream, &output);
851     if (ZSTD_isError(written)) {
852         ERR("ZSTD_endStream failed: %s\n", ZSTD_getErrorName(written));
853         ZSTD_freeCStream(stream);
854         return STATUS_INTERNAL_ERROR;
855     }
856 
857     ZSTD_freeCStream(stream);
858 
859     if (input.pos < input.size) // output would be larger than input
860         *space_left = 0;
861     else
862         *space_left = output.size - output.pos;
863 
864     return STATUS_SUCCESS;
865 }
866 
867 typedef struct {
868     uint8_t buf[COMPRESSED_EXTENT_SIZE];
869     uint8_t compression_type;
870     unsigned int inlen;
871     unsigned int outlen;
872     calc_job* cj;
873 } comp_part;
874 
write_compressed(fcb * fcb,uint64_t start_data,uint64_t end_data,void * data,PIRP Irp,LIST_ENTRY * rollback)875 NTSTATUS write_compressed(fcb* fcb, uint64_t start_data, uint64_t end_data, void* data, PIRP Irp, LIST_ENTRY* rollback) {
876     NTSTATUS Status;
877     uint64_t i;
878     unsigned int num_parts = (unsigned int)sector_align(end_data - start_data, COMPRESSED_EXTENT_SIZE) / COMPRESSED_EXTENT_SIZE;
879     uint8_t type;
880     comp_part* parts;
881     unsigned int buflen = 0;
882     uint8_t* buf;
883     chunk* c = NULL;
884     LIST_ENTRY* le;
885     uint64_t address, extaddr;
886     void* csum = NULL;
887 
888     if (fcb->Vcb->options.compress_type != 0 && fcb->prop_compression == PropCompression_None)
889         type = fcb->Vcb->options.compress_type;
890     else {
891         if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_ZSTD) && fcb->prop_compression == PropCompression_ZSTD)
892             type = BTRFS_COMPRESSION_ZSTD;
893         else if (fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_ZSTD && fcb->prop_compression != PropCompression_Zlib && fcb->prop_compression != PropCompression_LZO)
894             type = BTRFS_COMPRESSION_ZSTD;
895         else if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO) && fcb->prop_compression == PropCompression_LZO)
896             type = BTRFS_COMPRESSION_LZO;
897         else if (fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO && fcb->prop_compression != PropCompression_Zlib)
898             type = BTRFS_COMPRESSION_LZO;
899         else
900             type = BTRFS_COMPRESSION_ZLIB;
901     }
902 
903     Status = excise_extents(fcb->Vcb, fcb, start_data, end_data, Irp, rollback);
904     if (!NT_SUCCESS(Status)) {
905         ERR("excise_extents returned %08lx\n", Status);
906         return Status;
907     }
908 
909     parts = ExAllocatePoolWithTag(PagedPool, sizeof(comp_part) * num_parts, ALLOC_TAG);
910     if (!parts) {
911         ERR("out of memory\n");
912         return STATUS_INSUFFICIENT_RESOURCES;
913     }
914 
915     for (i = 0; i < num_parts; i++) {
916         if (i == num_parts - 1)
917             parts[i].inlen = ((unsigned int)(end_data - start_data) - ((num_parts - 1) * COMPRESSED_EXTENT_SIZE));
918         else
919             parts[i].inlen = COMPRESSED_EXTENT_SIZE;
920 
921         Status = add_calc_job_comp(fcb->Vcb, type, (uint8_t*)data + (i * COMPRESSED_EXTENT_SIZE), parts[i].inlen,
922                                    parts[i].buf, parts[i].inlen, &parts[i].cj);
923         if (!NT_SUCCESS(Status)) {
924             ERR("add_calc_job_comp returned %08lx\n", Status);
925 
926             for (unsigned int j = 0; j < i; j++) {
927                 KeWaitForSingleObject(&parts[j].cj->event, Executive, KernelMode, false, NULL);
928                 ExFreePool(parts[j].cj);
929             }
930 
931             ExFreePool(parts);
932             return Status;
933         }
934     }
935 
936     Status = STATUS_SUCCESS;
937 
938     for (int i = num_parts - 1; i >= 0; i--) {
939         calc_thread_main(fcb->Vcb, parts[i].cj);
940 
941         KeWaitForSingleObject(&parts[i].cj->event, Executive, KernelMode, false, NULL);
942 
943         if (!NT_SUCCESS(parts[i].cj->Status))
944             Status = parts[i].cj->Status;
945     }
946 
947     if (!NT_SUCCESS(Status)) {
948         ERR("calc job returned %08lx\n", Status);
949 
950         for (unsigned int i = 0; i < num_parts; i++) {
951             ExFreePool(parts[i].cj);
952         }
953 
954         ExFreePool(parts);
955         return Status;
956     }
957 
958     for (unsigned int i = 0; i < num_parts; i++) {
959         if (parts[i].cj->space_left >= fcb->Vcb->superblock.sector_size) {
960             parts[i].compression_type = type;
961             parts[i].outlen = parts[i].inlen - parts[i].cj->space_left;
962 
963             if (type == BTRFS_COMPRESSION_LZO)
964                 fcb->Vcb->superblock.incompat_flags |= BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO;
965             else if (type == BTRFS_COMPRESSION_ZSTD)
966                 fcb->Vcb->superblock.incompat_flags |= BTRFS_INCOMPAT_FLAGS_COMPRESS_ZSTD;
967 
968             if ((parts[i].outlen & (fcb->Vcb->superblock.sector_size - 1)) != 0) {
969                 unsigned int newlen = (unsigned int)sector_align(parts[i].outlen, fcb->Vcb->superblock.sector_size);
970 
971                 RtlZeroMemory(parts[i].buf + parts[i].outlen, newlen - parts[i].outlen);
972 
973                 parts[i].outlen = newlen;
974             }
975         } else {
976             parts[i].compression_type = BTRFS_COMPRESSION_NONE;
977             parts[i].outlen = (unsigned int)sector_align(parts[i].inlen, fcb->Vcb->superblock.sector_size);
978         }
979 
980         buflen += parts[i].outlen;
981         ExFreePool(parts[i].cj);
982     }
983 
984     // check if first 128 KB of file is incompressible
985 
986     if (start_data == 0 && parts[0].compression_type == BTRFS_COMPRESSION_NONE && !fcb->Vcb->options.compress_force) {
987         TRACE("adding nocompress flag to subvol %I64x, inode %I64x\n", fcb->subvol->id, fcb->inode);
988 
989         fcb->inode_item.flags |= BTRFS_INODE_NOCOMPRESS;
990         fcb->inode_item_changed = true;
991         mark_fcb_dirty(fcb);
992     }
993 
994     // join together into continuous buffer
995 
996     buf = ExAllocatePoolWithTag(PagedPool, buflen, ALLOC_TAG);
997     if (!buf) {
998         ERR("out of memory\n");
999         ExFreePool(parts);
1000         return STATUS_INSUFFICIENT_RESOURCES;
1001     }
1002 
1003     {
1004         uint8_t* buf2 = buf;
1005 
1006         for (i = 0; i < num_parts; i++) {
1007             if (parts[i].compression_type == BTRFS_COMPRESSION_NONE)
1008                 RtlCopyMemory(buf2, (uint8_t*)data + (i * COMPRESSED_EXTENT_SIZE), parts[i].outlen);
1009             else
1010                 RtlCopyMemory(buf2, parts[i].buf, parts[i].outlen);
1011 
1012             buf2 += parts[i].outlen;
1013         }
1014     }
1015 
1016     // find an address
1017 
1018     ExAcquireResourceSharedLite(&fcb->Vcb->chunk_lock, true);
1019 
1020     le = fcb->Vcb->chunks.Flink;
1021     while (le != &fcb->Vcb->chunks) {
1022         chunk* c2 = CONTAINING_RECORD(le, chunk, list_entry);
1023 
1024         if (!c2->readonly && !c2->reloc) {
1025             acquire_chunk_lock(c2, fcb->Vcb);
1026 
1027             if (c2->chunk_item->type == fcb->Vcb->data_flags && (c2->chunk_item->size - c2->used) >= buflen) {
1028                 if (find_data_address_in_chunk(fcb->Vcb, c2, buflen, &address)) {
1029                     c = c2;
1030                     c->used += buflen;
1031                     space_list_subtract(c, address, buflen, rollback);
1032                     release_chunk_lock(c2, fcb->Vcb);
1033                     break;
1034                 }
1035             }
1036 
1037             release_chunk_lock(c2, fcb->Vcb);
1038         }
1039 
1040         le = le->Flink;
1041     }
1042 
1043     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
1044 
1045     if (!c) {
1046         chunk* c2;
1047 
1048         ExAcquireResourceExclusiveLite(&fcb->Vcb->chunk_lock, true);
1049 
1050         Status = alloc_chunk(fcb->Vcb, fcb->Vcb->data_flags, &c2, false);
1051 
1052         ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
1053 
1054         if (!NT_SUCCESS(Status)) {
1055             ERR("alloc_chunk returned %08lx\n", Status);
1056             ExFreePool(buf);
1057             ExFreePool(parts);
1058             return Status;
1059         }
1060 
1061         acquire_chunk_lock(c2, fcb->Vcb);
1062 
1063         if (find_data_address_in_chunk(fcb->Vcb, c2, buflen, &address)) {
1064             c = c2;
1065             c->used += buflen;
1066             space_list_subtract(c, address, buflen, rollback);
1067         }
1068 
1069         release_chunk_lock(c2, fcb->Vcb);
1070     }
1071 
1072     if (!c) {
1073         WARN("couldn't find any data chunks with %x bytes free\n", buflen);
1074         ExFreePool(buf);
1075         ExFreePool(parts);
1076         return STATUS_DISK_FULL;
1077     }
1078 
1079     // write to disk
1080 
1081     TRACE("writing %x bytes to %I64x\n", buflen, address);
1082 
1083     Status = write_data_complete(fcb->Vcb, address, buf, buflen, Irp, NULL, false, 0,
1084                                  fcb->Header.Flags2 & FSRTL_FLAG2_IS_PAGING_FILE ? HighPagePriority : NormalPagePriority);
1085     if (!NT_SUCCESS(Status)) {
1086         ERR("write_data_complete returned %08lx\n", Status);
1087         ExFreePool(buf);
1088         ExFreePool(parts);
1089         return Status;
1090     }
1091 
1092     // FIXME - do rest of the function while we're waiting for I/O to finish?
1093 
1094     // calculate csums if necessary
1095 
1096     if (!(fcb->inode_item.flags & BTRFS_INODE_NODATASUM)) {
1097         unsigned int sl = buflen >> fcb->Vcb->sector_shift;
1098 
1099         csum = ExAllocatePoolWithTag(PagedPool, sl * fcb->Vcb->csum_size, ALLOC_TAG);
1100         if (!csum) {
1101             ERR("out of memory\n");
1102             ExFreePool(buf);
1103             ExFreePool(parts);
1104             return STATUS_INSUFFICIENT_RESOURCES;
1105         }
1106 
1107         do_calc_job(fcb->Vcb, buf, sl, csum);
1108     }
1109 
1110     ExFreePool(buf);
1111 
1112     // add extents to fcb
1113 
1114     extaddr = address;
1115 
1116     for (i = 0; i < num_parts; i++) {
1117         EXTENT_DATA* ed;
1118         EXTENT_DATA2* ed2;
1119         void* csum2;
1120 
1121         ed = ExAllocatePoolWithTag(PagedPool, offsetof(EXTENT_DATA, data[0]) + sizeof(EXTENT_DATA2), ALLOC_TAG);
1122         if (!ed) {
1123             ERR("out of memory\n");
1124             ExFreePool(parts);
1125 
1126             if (csum)
1127                 ExFreePool(csum);
1128 
1129             return STATUS_INSUFFICIENT_RESOURCES;
1130         }
1131 
1132         ed->generation = fcb->Vcb->superblock.generation;
1133         ed->decoded_size = parts[i].inlen;
1134         ed->compression = parts[i].compression_type;
1135         ed->encryption = BTRFS_ENCRYPTION_NONE;
1136         ed->encoding = BTRFS_ENCODING_NONE;
1137         ed->type = EXTENT_TYPE_REGULAR;
1138 
1139         ed2 = (EXTENT_DATA2*)ed->data;
1140         ed2->address = extaddr;
1141         ed2->size = parts[i].outlen;
1142         ed2->offset = 0;
1143         ed2->num_bytes = parts[i].inlen;
1144 
1145         if (csum) {
1146             csum2 = ExAllocatePoolWithTag(PagedPool, (parts[i].outlen * fcb->Vcb->csum_size) >> fcb->Vcb->sector_shift, ALLOC_TAG);
1147             if (!csum2) {
1148                 ERR("out of memory\n");
1149                 ExFreePool(ed);
1150                 ExFreePool(parts);
1151                 ExFreePool(csum);
1152                 return STATUS_INSUFFICIENT_RESOURCES;
1153             }
1154 
1155             RtlCopyMemory(csum2, (uint8_t*)csum + (((extaddr - address) * fcb->Vcb->csum_size) >> fcb->Vcb->sector_shift),
1156                           (parts[i].outlen * fcb->Vcb->csum_size) >> fcb->Vcb->sector_shift);
1157         } else
1158             csum2 = NULL;
1159 
1160         Status = add_extent_to_fcb(fcb, start_data + (i * COMPRESSED_EXTENT_SIZE), ed, offsetof(EXTENT_DATA, data[0]) + sizeof(EXTENT_DATA2),
1161                                    true, csum2, rollback);
1162         if (!NT_SUCCESS(Status)) {
1163             ERR("add_extent_to_fcb returned %08lx\n", Status);
1164             ExFreePool(ed);
1165             ExFreePool(parts);
1166 
1167             if (csum)
1168                 ExFreePool(csum);
1169 
1170             return Status;
1171         }
1172 
1173         ExFreePool(ed);
1174 
1175         fcb->inode_item.st_blocks += parts[i].inlen;
1176 
1177         extaddr += parts[i].outlen;
1178     }
1179 
1180     if (csum)
1181         ExFreePool(csum);
1182 
1183     // update extent refcounts
1184 
1185     ExAcquireResourceExclusiveLite(&c->changed_extents_lock, true);
1186 
1187     extaddr = address;
1188 
1189     for (i = 0; i < num_parts; i++) {
1190         add_changed_extent_ref(c, extaddr, parts[i].outlen, fcb->subvol->id, fcb->inode,
1191                                start_data + (i * COMPRESSED_EXTENT_SIZE), 1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM);
1192 
1193         extaddr += parts[i].outlen;
1194     }
1195 
1196     ExReleaseResourceLite(&c->changed_extents_lock);
1197 
1198     fcb->extents_changed = true;
1199     fcb->inode_item_changed = true;
1200     mark_fcb_dirty(fcb);
1201 
1202     ExFreePool(parts);
1203 
1204     return STATUS_SUCCESS;
1205 }
1206