drivers/filesystems/btrfs/compress.c

   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
  41
  42 #define LINUX_PAGE_SIZE 4096
  43
  44 typedef struct {
  45     UINT8* in;
  46     UINT32 inlen;
  47     UINT32 inpos;
  48     UINT8* out;
  49     UINT32 outlen;
  50     UINT32 outpos;
  51     BOOL error;
  52     void* wrkmem;
  53 } lzo_stream;
  54
  55 #define LZO1X_MEM_COMPRESS ((UINT32) (16384L * sizeof(UINT8*)))
  56
  57 #define M1_MAX_OFFSET 0x0400
  58 #define M2_MAX_OFFSET 0x0800
  59 #define M3_MAX_OFFSET 0x4000
  60 #define M4_MAX_OFFSET 0xbfff
  61
  62 #define MX_MAX_OFFSET (M1_MAX_OFFSET + M2_MAX_OFFSET)
  63
  64 #define M1_MARKER 0
  65 #define M2_MARKER 64
  66 #define M3_MARKER 32
  67 #define M4_MARKER 16
  68
  69 #define _DV2(p, shift1, shift2) (((( (UINT32)(p[2]) << shift1) ^ p[1]) << shift2) ^ p[0])
  70 #define DVAL_NEXT(dv, p) dv ^= p[-1]; dv = (((dv) >> 5) ^ ((UINT32)(p[2]) << (2*5)))
  71 #define _DV(p, shift) _DV2(p, shift, shift)
  72 #define DVAL_FIRST(dv, p) dv = _DV((p), 5)
  73 #define _DINDEX(dv, p) ((40799u * (dv)) >> 5)
  74 #define DINDEX(dv, p) (((_DINDEX(dv, p)) & 0x3fff) << 0)
  75 #define UPDATE_D(dict, cycle, dv, p) dict[DINDEX(dv, p)] = (p)
  76 #define UPDATE_I(dict, cycle, index, p) dict[index] = (p)
  77
  78 #define LZO_CHECK_MPOS_NON_DET(m_pos, m_off, in, ip, max_offset) \
  79     ((void*) m_pos < (void*) in || \
  80     (m_off = (UINT8*) ip - (UINT8*) m_pos) <= 0 || \
  81     m_off > max_offset)
  82
  83 #define LZO_BYTE(x) ((unsigned char) (x))
  84
  85 static UINT8 lzo_nextbyte(lzo_stream* stream) {
  86     UINT8 c;
  87
  88     if (stream->inpos >= stream->inlen) {
  89         stream->error = TRUE;
  90         return 0;
  91     }
  92
  93     c = stream->in[stream->inpos];
  94     stream->inpos++;
  95
  96     return c;
  97 }
  98
  99 static int lzo_len(lzo_stream* stream, int byte, int mask) {
 100     int len = byte & mask;
 101
 102     if (len == 0) {
 103         while (!(byte = lzo_nextbyte(stream))) {
 104             if (stream->error) return 0;
 105
 106             len += 255;
 107         }
 108
 109         len += mask + byte;
 110     }
 111
 112     return len;
 113 }
 114
 115 static void lzo_copy(lzo_stream* stream, int len) {
 116     if (stream->inpos + len > stream->inlen) {
 117         stream->error = TRUE;
 118         return;
 119     }
 120
 121     if (stream->outpos + len > stream->outlen) {
 122         stream->error = TRUE;
 123         return;
 124     }
 125
 126     do {
 127         stream->out[stream->outpos] = stream->in[stream->inpos];
 128         stream->inpos++;
 129         stream->outpos++;
 130         len--;
 131     } while (len > 0);
 132 }
 133
 134 static void lzo_copyback(lzo_stream* stream, UINT32 back, int len) {
 135     if (stream->outpos < back) {
 136         stream->error = TRUE;
 137         return;
 138     }
 139
 140     if (stream->outpos + len > stream->outlen) {
 141         stream->error = TRUE;
 142         return;
 143     }
 144
 145     do {
 146         stream->out[stream->outpos] = stream->out[stream->outpos - back];
 147         stream->outpos++;
 148         len--;
 149     } while (len > 0);
 150 }
 151
 152 static NTSTATUS do_lzo_decompress(lzo_stream* stream) {
 153     UINT8 byte;
 154     UINT32 len, back;
 155     BOOL backcopy = FALSE;
 156
 157     stream->error = FALSE;
 158
 159     byte = lzo_nextbyte(stream);
 160     if (stream->error) return STATUS_INTERNAL_ERROR;
 161
 162     if (byte > 17) {
 163         lzo_copy(stream, min((UINT8)(byte - 17), (UINT32)(stream->outlen - stream->outpos)));
 164         if (stream->error) return STATUS_INTERNAL_ERROR;
 165
 166         if (stream->outlen == stream->outpos)
 167             return STATUS_SUCCESS;
 168
 169         byte = lzo_nextbyte(stream);
 170         if (stream->error) return STATUS_INTERNAL_ERROR;
 171
 172         if (byte < 16) return STATUS_INTERNAL_ERROR;
 173     }
 174
 175     while (1) {
 176         if (byte >> 4) {
 177             backcopy = TRUE;
 178             if (byte >> 6) {
 179                 len = (byte >> 5) - 1;
 180                 back = (lzo_nextbyte(stream) << 3) + ((byte >> 2) & 7) + 1;
 181                 if (stream->error) return STATUS_INTERNAL_ERROR;
 182             } else if (byte >> 5) {
 183                 len = lzo_len(stream, byte, 31);
 184                 if (stream->error) return STATUS_INTERNAL_ERROR;
 185
 186                 byte = lzo_nextbyte(stream);
 187                 if (stream->error) return STATUS_INTERNAL_ERROR;
 188
 189                 back = (lzo_nextbyte(stream) << 6) + (byte >> 2) + 1;
 190                 if (stream->error) return STATUS_INTERNAL_ERROR;
 191             } else {
 192                 len = lzo_len(stream, byte, 7);
 193                 if (stream->error) return STATUS_INTERNAL_ERROR;
 194
 195                 back = (1 << 14) + ((byte & 8) << 11);
 196
 197                 byte = lzo_nextbyte(stream);
 198                 if (stream->error) return STATUS_INTERNAL_ERROR;
 199
 200                 back += (lzo_nextbyte(stream) << 6) + (byte >> 2);
 201                 if (stream->error) return STATUS_INTERNAL_ERROR;
 202
 203                 if (back == (1 << 14)) {
 204                     if (len != 1)
 205                         return STATUS_INTERNAL_ERROR;
 206                     break;
 207                 }
 208             }
 209         } else if (backcopy) {
 210             len = 0;
 211             back = (lzo_nextbyte(stream) << 2) + (byte >> 2) + 1;
 212             if (stream->error) return STATUS_INTERNAL_ERROR;
 213         } else {
 214             len = lzo_len(stream, byte, 15);
 215             if (stream->error) return STATUS_INTERNAL_ERROR;
 216
 217             lzo_copy(stream, min(len + 3, stream->outlen - stream->outpos));
 218             if (stream->error) return STATUS_INTERNAL_ERROR;
 219
 220             if (stream->outlen == stream->outpos)
 221                 return STATUS_SUCCESS;
 222
 223             byte = lzo_nextbyte(stream);
 224             if (stream->error) return STATUS_INTERNAL_ERROR;
 225
 226             if (byte >> 4)
 227                 continue;
 228
 229             len = 1;
 230             back = (1 << 11) + (lzo_nextbyte(stream) << 2) + (byte >> 2) + 1;
 231             if (stream->error) return STATUS_INTERNAL_ERROR;
 232
 233             break;
 234         }
 235
 236         lzo_copyback(stream, back, min(len + 2, stream->outlen - stream->outpos));
 237         if (stream->error) return STATUS_INTERNAL_ERROR;
 238
 239         if (stream->outlen == stream->outpos)
 240             return STATUS_SUCCESS;
 241
 242         len = byte & 3;
 243
 244         if (len) {
 245             lzo_copy(stream, min(len, stream->outlen - stream->outpos));
 246             if (stream->error) return STATUS_INTERNAL_ERROR;
 247
 248             if (stream->outlen == stream->outpos)
 249                 return STATUS_SUCCESS;
 250         } else
 251             backcopy = !backcopy;
 252
 253         byte = lzo_nextbyte(stream);
 254         if (stream->error) return STATUS_INTERNAL_ERROR;
 255     }
 256
 257     return STATUS_SUCCESS;
 258 }
 259
 260 NTSTATUS lzo_decompress(UINT8* inbuf, UINT32 inlen, UINT8* outbuf, UINT32 outlen, UINT32 inpageoff) {
 261     NTSTATUS Status;
 262     UINT32 partlen, inoff, outoff;
 263     lzo_stream stream;
 264
 265     inoff = 0;
 266     outoff = 0;
 267
 268     do {
 269         partlen = *(UINT32*)&inbuf[inoff];
 270
 271         if (partlen + inoff > inlen) {
 272             ERR("overflow: %x + %x > %llx\n", partlen, inoff, inlen);
 273             return STATUS_INTERNAL_ERROR;
 274         }
 275
 276         inoff += sizeof(UINT32);
 277
 278         stream.in = &inbuf[inoff];
 279         stream.inlen = partlen;
 280         stream.inpos = 0;
 281         stream.out = &outbuf[outoff];
 282         stream.outlen = min(outlen, LINUX_PAGE_SIZE);
 283         stream.outpos = 0;
 284
 285         Status = do_lzo_decompress(&stream);
 286         if (!NT_SUCCESS(Status)) {
 287             ERR("do_lzo_decompress returned %08x\n", Status);
 288             return Status;
 289         }
 290
 291         if (stream.outpos < stream.outlen)
 292             RtlZeroMemory(&stream.out[stream.outpos], stream.outlen - stream.outpos);
 293
 294         inoff += partlen;
 295         outoff += stream.outlen;
 296
 297         if (LINUX_PAGE_SIZE - ((inpageoff + inoff) % LINUX_PAGE_SIZE) < sizeof(UINT32))
 298             inoff = ((((inpageoff + inoff) / LINUX_PAGE_SIZE) + 1) * LINUX_PAGE_SIZE) - inpageoff;
 299
 300         outlen -= stream.outlen;
 301     } while (inoff < inlen && outlen > 0);
 302
 303     return STATUS_SUCCESS;
 304 }
 305
 306 static void* zlib_alloc(void* opaque, unsigned int items, unsigned int size) {
 307     UNUSED(opaque);
 308
 309     return ExAllocatePoolWithTag(PagedPool, items * size, ALLOC_TAG_ZLIB);
 310 }
 311
 312 static void zlib_free(void* opaque, void* ptr) {
 313     UNUSED(opaque);
 314
 315     ExFreePool(ptr);
 316 }
 317
 318 NTSTATUS zlib_decompress(UINT8* inbuf, UINT32 inlen, UINT8* outbuf, UINT32 outlen) {
 319     z_stream c_stream;
 320     int ret;
 321
 322     c_stream.zalloc = zlib_alloc;
 323     c_stream.zfree = zlib_free;
 324     c_stream.opaque = (voidpf)0;
 325
 326     ret = inflateInit(&c_stream);
 327
 328     if (ret != Z_OK) {
 329         ERR("inflateInit returned %08x\n", ret);
 330         return STATUS_INTERNAL_ERROR;
 331     }
 332
 333     c_stream.next_in = inbuf;
 334     c_stream.avail_in = inlen;
 335
 336     c_stream.next_out = outbuf;
 337     c_stream.avail_out = outlen;
 338
 339     do {
 340         ret = inflate(&c_stream, Z_NO_FLUSH);
 341
 342         if (ret != Z_OK && ret != Z_STREAM_END) {
 343             ERR("inflate returned %08x\n", ret);
 344             inflateEnd(&c_stream);
 345             return STATUS_INTERNAL_ERROR;
 346         }
 347
 348         if (c_stream.avail_out == 0)
 349             break;
 350     } while (ret != Z_STREAM_END);
 351
 352     ret = inflateEnd(&c_stream);
 353
 354     if (ret != Z_OK) {
 355         ERR("inflateEnd returned %08x\n", ret);
 356         return STATUS_INTERNAL_ERROR;
 357     }
 358
 359     // FIXME - if we're short, should we zero the end of outbuf so we don't leak information into userspace?
 360
 361     return STATUS_SUCCESS;
 362 }
 363
 364 static NTSTATUS zlib_write_compressed_bit(fcb* fcb, UINT64 start_data, UINT64 end_data, void* data, BOOL* compressed, PIRP Irp, LIST_ENTRY* rollback) {
 365     NTSTATUS Status;
 366     UINT8 compression;
 367     UINT32 comp_length;
 368     UINT8* comp_data;
 369     UINT32 out_left;
 370     LIST_ENTRY* le;
 371     chunk* c;
 372     z_stream c_stream;
 373     int ret;
 374
 375     comp_data = ExAllocatePoolWithTag(PagedPool, (UINT32)(end_data - start_data), ALLOC_TAG);
 376     if (!comp_data) {
 377         ERR("out of memory\n");
 378         return STATUS_INSUFFICIENT_RESOURCES;
 379     }
 380
 381     Status = excise_extents(fcb->Vcb, fcb, start_data, end_data, Irp, rollback);
 382     if (!NT_SUCCESS(Status)) {
 383         ERR("excise_extents returned %08x\n", Status);
 384         ExFreePool(comp_data);
 385         return Status;
 386     }
 387
 388     c_stream.zalloc = zlib_alloc;
 389     c_stream.zfree = zlib_free;
 390     c_stream.opaque = (voidpf)0;
 391
 392     ret = deflateInit(&c_stream, fcb->Vcb->options.zlib_level);
 393
 394     if (ret != Z_OK) {
 395         ERR("deflateInit returned %08x\n", ret);
 396         ExFreePool(comp_data);
 397         return STATUS_INTERNAL_ERROR;
 398     }
 399
 400     c_stream.avail_in = (UINT32)(end_data - start_data);
 401     c_stream.next_in = data;
 402     c_stream.avail_out = (UINT32)(end_data - start_data);
 403     c_stream.next_out = comp_data;
 404
 405     do {
 406         ret = deflate(&c_stream, Z_FINISH);
 407
 408         if (ret == Z_STREAM_ERROR) {
 409             ERR("deflate returned %x\n", ret);
 410             ExFreePool(comp_data);
 411             return STATUS_INTERNAL_ERROR;
 412         }
 413     } while (c_stream.avail_in > 0 && c_stream.avail_out > 0);
 414
 415     out_left = c_stream.avail_out;
 416
 417     ret = deflateEnd(&c_stream);
 418
 419     if (ret != Z_OK) {
 420         ERR("deflateEnd returned %08x\n", ret);
 421         ExFreePool(comp_data);
 422         return STATUS_INTERNAL_ERROR;
 423     }
 424
 425     if (out_left < fcb->Vcb->superblock.sector_size) { // compressed extent would be larger than or same size as uncompressed extent
 426         ExFreePool(comp_data);
 427
 428         comp_length = (UINT32)(end_data - start_data);
 429         comp_data = data;
 430         compression = BTRFS_COMPRESSION_NONE;
 431
 432         *compressed = FALSE;
 433     } else {
 434         UINT32 cl;
 435
 436         compression = BTRFS_COMPRESSION_ZLIB;
 437         cl = (UINT32)(end_data - start_data - out_left);
 438         comp_length = (UINT32)sector_align(cl, fcb->Vcb->superblock.sector_size);
 439
 440         RtlZeroMemory(comp_data + cl, comp_length - cl);
 441
 442         *compressed = TRUE;
 443     }
 444
 445     ExAcquireResourceSharedLite(&fcb->Vcb->chunk_lock, TRUE);
 446
 447     le = fcb->Vcb->chunks.Flink;
 448     while (le != &fcb->Vcb->chunks) {
 449         c = CONTAINING_RECORD(le, chunk, list_entry);
 450
 451         if (!c->readonly && !c->reloc) {
 452             ExAcquireResourceExclusiveLite(&c->lock, TRUE);
 453
 454             if (c->chunk_item->type == fcb->Vcb->data_flags && (c->chunk_item->size - c->used) >= comp_length) {
 455                 if (insert_extent_chunk(fcb->Vcb, fcb, c, start_data, comp_length, FALSE, comp_data, Irp, rollback, compression, end_data - start_data, FALSE, 0)) {
 456                     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 457
 458                     if (compression != BTRFS_COMPRESSION_NONE)
 459                         ExFreePool(comp_data);
 460
 461                     return STATUS_SUCCESS;
 462                 }
 463             }
 464
 465             ExReleaseResourceLite(&c->lock);
 466         }
 467
 468         le = le->Flink;
 469     }
 470
 471     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 472
 473     ExAcquireResourceExclusiveLite(&fcb->Vcb->chunk_lock, TRUE);
 474
 475     Status = alloc_chunk(fcb->Vcb, fcb->Vcb->data_flags, &c, FALSE);
 476
 477     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 478
 479     if (!NT_SUCCESS(Status)) {
 480         ERR("alloc_chunk returned %08x\n", Status);
 481
 482         if (compression != BTRFS_COMPRESSION_NONE)
 483             ExFreePool(comp_data);
 484
 485         return Status;
 486     }
 487
 488     if (c) {
 489         ExAcquireResourceExclusiveLite(&c->lock, TRUE);
 490
 491         if (c->chunk_item->type == fcb->Vcb->data_flags && (c->chunk_item->size - c->used) >= comp_length) {
 492             if (insert_extent_chunk(fcb->Vcb, fcb, c, start_data, comp_length, FALSE, comp_data, Irp, rollback, compression, end_data - start_data, FALSE, 0)) {
 493                 if (compression != BTRFS_COMPRESSION_NONE)
 494                     ExFreePool(comp_data);
 495
 496                 return STATUS_SUCCESS;
 497             }
 498         }
 499
 500         ExReleaseResourceLite(&c->lock);
 501     }
 502
 503     WARN("couldn't find any data chunks with %llx bytes free\n", comp_length);
 504
 505     if (compression != BTRFS_COMPRESSION_NONE)
 506         ExFreePool(comp_data);
 507
 508     return STATUS_DISK_FULL;
 509 }
 510
 511 static NTSTATUS lzo_do_compress(const UINT8* in, UINT32 in_len, UINT8* out, UINT32* out_len, void* wrkmem) {
 512     const UINT8* ip;
 513     UINT32 dv;
 514     UINT8* op;
 515     const UINT8* in_end = in + in_len;
 516     const UINT8* ip_end = in + in_len - 9 - 4;
 517     const UINT8* ii;
 518     const UINT8** dict = (const UINT8**)wrkmem;
 519
 520     op = out;
 521     ip = in;
 522     ii = ip;
 523
 524     DVAL_FIRST(dv, ip); UPDATE_D(dict, cycle, dv, ip); ip++;
 525     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
 526     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
 527     DVAL_NEXT(dv, ip);  UPDATE_D(dict, cycle, dv, ip); ip++;
 528
 529     while (1) {
 530         const UINT8* m_pos;
 531         UINT32 m_len;
 532         ptrdiff_t m_off;
 533         UINT32 lit, dindex;
 534
 535         dindex = DINDEX(dv, ip);
 536         m_pos = dict[dindex];
 537         UPDATE_I(dict, cycle, dindex, ip);
 538
 539         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]) {
 540             lit = (UINT32)(ip - ii);
 541             m_pos += 3;
 542             if (m_off <= M2_MAX_OFFSET)
 543                 goto match;
 544
 545             if (lit == 3) { /* better compression, but slower */
 546                 if (op - 2 <= out)
 547                     return STATUS_INTERNAL_ERROR;
 548
 549                 op[-2] |= LZO_BYTE(3);
 550                 *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
 551                 goto code_match;
 552             }
 553
 554             if (*m_pos == ip[3])
 555                 goto match;
 556         }
 557
 558         /* a literal */
 559         ++ip;
 560         if (ip >= ip_end)
 561             break;
 562         DVAL_NEXT(dv, ip);
 563         continue;
 564
 565         /* a match */
 566 match:
 567         /* store current literal run */
 568         if (lit > 0) {
 569             UINT32 t = lit;
 570
 571             if (t <= 3) {
 572                 if (op - 2 <= out)
 573                     return STATUS_INTERNAL_ERROR;
 574
 575                 op[-2] |= LZO_BYTE(t);
 576             } else if (t <= 18)
 577                 *op++ = LZO_BYTE(t - 3);
 578             else {
 579                 UINT32 tt = t - 18;
 580
 581                 *op++ = 0;
 582                 while (tt > 255) {
 583                     tt -= 255;
 584                     *op++ = 0;
 585                 }
 586
 587                 if (tt <= 0)
 588                     return STATUS_INTERNAL_ERROR;
 589
 590                 *op++ = LZO_BYTE(tt);
 591             }
 592
 593             do {
 594                 *op++ = *ii++;
 595             } while (--t > 0);
 596         }
 597
 598
 599         /* code the match */
 600 code_match:
 601         if (ii != ip)
 602             return STATUS_INTERNAL_ERROR;
 603
 604         ip += 3;
 605         if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ ||
 606             *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++) {
 607             --ip;
 608             m_len = (UINT32)(ip - ii);
 609
 610             if (m_len < 3 || m_len > 8)
 611                 return STATUS_INTERNAL_ERROR;
 612
 613             if (m_off <= M2_MAX_OFFSET) {
 614                 m_off -= 1;
 615                 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
 616                 *op++ = LZO_BYTE(m_off >> 3);
 617             } else if (m_off <= M3_MAX_OFFSET) {
 618                 m_off -= 1;
 619                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 620                 goto m3_m4_offset;
 621             } else {
 622                 m_off -= 0x4000;
 623
 624                 if (m_off <= 0 || m_off > 0x7fff)
 625                     return STATUS_INTERNAL_ERROR;
 626
 627                 *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
 628                 goto m3_m4_offset;
 629             }
 630         } else {
 631             const UINT8* end;
 632             end = in_end;
 633             while (ip < end && *m_pos == *ip)
 634                 m_pos++, ip++;
 635             m_len = (UINT32)(ip - ii);
 636
 637             if (m_len < 3)
 638                 return STATUS_INTERNAL_ERROR;
 639
 640             if (m_off <= M3_MAX_OFFSET) {
 641                 m_off -= 1;
 642                 if (m_len <= 33)
 643                     *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 644                 else {
 645                     m_len -= 33;
 646                     *op++ = M3_MARKER | 0;
 647                     goto m3_m4_len;
 648                 }
 649             } else {
 650                 m_off -= 0x4000;
 651
 652                 if (m_off <= 0 || m_off > 0x7fff)
 653                     return STATUS_INTERNAL_ERROR;
 654
 655                 if (m_len <= 9)
 656                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
 657                 else {
 658                     m_len -= 9;
 659                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
 660 m3_m4_len:
 661                     while (m_len > 255) {
 662                         m_len -= 255;
 663                         *op++ = 0;
 664                     }
 665
 666                     if (m_len <= 0)
 667                         return STATUS_INTERNAL_ERROR;
 668
 669                     *op++ = LZO_BYTE(m_len);
 670                 }
 671             }
 672
 673 m3_m4_offset:
 674             *op++ = LZO_BYTE((m_off & 63) << 2);
 675             *op++ = LZO_BYTE(m_off >> 6);
 676         }
 677
 678         ii = ip;
 679         if (ip >= ip_end)
 680             break;
 681         DVAL_FIRST(dv, ip);
 682     }
 683
 684     /* store final literal run */
 685     if (in_end - ii > 0) {
 686         UINT32 t = (UINT32)(in_end - ii);
 687
 688         if (op == out && t <= 238)
 689             *op++ = LZO_BYTE(17 + t);
 690         else if (t <= 3)
 691             op[-2] |= LZO_BYTE(t);
 692         else if (t <= 18)
 693             *op++ = LZO_BYTE(t - 3);
 694         else {
 695             UINT32 tt = t - 18;
 696
 697             *op++ = 0;
 698             while (tt > 255) {
 699                 tt -= 255;
 700                 *op++ = 0;
 701             }
 702
 703             if (tt <= 0)
 704                 return STATUS_INTERNAL_ERROR;
 705
 706             *op++ = LZO_BYTE(tt);
 707         }
 708
 709         do {
 710             *op++ = *ii++;
 711         } while (--t > 0);
 712     }
 713
 714     *out_len = (UINT32)(op - out);
 715
 716     return STATUS_SUCCESS;
 717 }
 718
 719 static NTSTATUS lzo1x_1_compress(lzo_stream* stream) {
 720     UINT8 *op = stream->out;
 721     NTSTATUS Status = STATUS_SUCCESS;
 722
 723     if (stream->inlen <= 0)
 724         stream->outlen = 0;
 725     else if (stream->inlen <= 9 + 4) {
 726         *op++ = LZO_BYTE(17 + stream->inlen);
 727
 728         stream->inpos = 0;
 729         do {
 730             *op++ = stream->in[stream->inpos];
 731             stream->inpos++;
 732         } while (stream->inlen < stream->inpos);
 733         stream->outlen = (UINT32)(op - stream->out);
 734     } else
 735         Status = lzo_do_compress(stream->in, stream->inlen, stream->out, &stream->outlen, stream->wrkmem);
 736
 737     if (Status == STATUS_SUCCESS) {
 738         op = stream->out + stream->outlen;
 739         *op++ = M4_MARKER | 1;
 740         *op++ = 0;
 741         *op++ = 0;
 742         stream->outlen += 3;
 743     }
 744
 745     return Status;
 746 }
 747
 748 static __inline UINT32 lzo_max_outlen(UINT32 inlen) {
 749     return inlen + (inlen / 16) + 64 + 3; // formula comes from LZO.FAQ
 750 }
 751
 752 static NTSTATUS lzo_write_compressed_bit(fcb* fcb, UINT64 start_data, UINT64 end_data, void* data, BOOL* compressed, PIRP Irp, LIST_ENTRY* rollback) {
 753     NTSTATUS Status;
 754     UINT8 compression;
 755     UINT64 comp_length;
 756     ULONG comp_data_len, num_pages, i;
 757     UINT8* comp_data;
 758     BOOL skip_compression = FALSE;
 759     lzo_stream stream;
 760     UINT32* out_size;
 761     LIST_ENTRY* le;
 762     chunk* c;
 763
 764     num_pages = (ULONG)((sector_align(end_data - start_data, LINUX_PAGE_SIZE)) / LINUX_PAGE_SIZE);
 765
 766     // Four-byte overall header
 767     // Another four-byte header page
 768     // Each page has a maximum size of lzo_max_outlen(LINUX_PAGE_SIZE)
 769     // Plus another four bytes for possible padding
 770     comp_data_len = sizeof(UINT32) + ((lzo_max_outlen(LINUX_PAGE_SIZE) + (2 * sizeof(UINT32))) * num_pages);
 771
 772     comp_data = ExAllocatePoolWithTag(PagedPool, comp_data_len, ALLOC_TAG);
 773     if (!comp_data) {
 774         ERR("out of memory\n");
 775         return STATUS_INSUFFICIENT_RESOURCES;
 776     }
 777
 778     stream.wrkmem = ExAllocatePoolWithTag(PagedPool, LZO1X_MEM_COMPRESS, ALLOC_TAG);
 779     if (!stream.wrkmem) {
 780         ERR("out of memory\n");
 781         ExFreePool(comp_data);
 782         return STATUS_INSUFFICIENT_RESOURCES;
 783     }
 784
 785     Status = excise_extents(fcb->Vcb, fcb, start_data, end_data, Irp, rollback);
 786     if (!NT_SUCCESS(Status)) {
 787         ERR("excise_extents returned %08x\n", Status);
 788         ExFreePool(comp_data);
 789         ExFreePool(stream.wrkmem);
 790         return Status;
 791     }
 792
 793     out_size = (UINT32*)comp_data;
 794     *out_size = sizeof(UINT32);
 795
 796     stream.in = data;
 797     stream.out = comp_data + (2 * sizeof(UINT32));
 798
 799     for (i = 0; i < num_pages; i++) {
 800         UINT32* pagelen = (UINT32*)(stream.out - sizeof(UINT32));
 801
 802         stream.inlen = (UINT32)min(LINUX_PAGE_SIZE, end_data - start_data - (i * LINUX_PAGE_SIZE));
 803
 804         Status = lzo1x_1_compress(&stream);
 805         if (!NT_SUCCESS(Status)) {
 806             ERR("lzo1x_1_compress returned %08x\n", Status);
 807             skip_compression = TRUE;
 808             break;
 809         }
 810
 811         *pagelen = stream.outlen;
 812         *out_size += stream.outlen + sizeof(UINT32);
 813
 814         stream.in += LINUX_PAGE_SIZE;
 815         stream.out += stream.outlen + sizeof(UINT32);
 816
 817         if (LINUX_PAGE_SIZE - (*out_size % LINUX_PAGE_SIZE) < sizeof(UINT32)) {
 818             RtlZeroMemory(stream.out, LINUX_PAGE_SIZE - (*out_size % LINUX_PAGE_SIZE));
 819             stream.out += LINUX_PAGE_SIZE - (*out_size % LINUX_PAGE_SIZE);
 820             *out_size += LINUX_PAGE_SIZE - (*out_size % LINUX_PAGE_SIZE);
 821         }
 822     }
 823
 824     ExFreePool(stream.wrkmem);
 825
 826     if (skip_compression || *out_size >= end_data - start_data - fcb->Vcb->superblock.sector_size) { // compressed extent would be larger than or same size as uncompressed extent
 827         ExFreePool(comp_data);
 828
 829         comp_length = end_data - start_data;
 830         comp_data = data;
 831         compression = BTRFS_COMPRESSION_NONE;
 832
 833         *compressed = FALSE;
 834     } else {
 835         compression = BTRFS_COMPRESSION_LZO;
 836         comp_length = sector_align(*out_size, fcb->Vcb->superblock.sector_size);
 837
 838         RtlZeroMemory(comp_data + *out_size, (ULONG)(comp_length - *out_size));
 839
 840         *compressed = TRUE;
 841     }
 842
 843     ExAcquireResourceSharedLite(&fcb->Vcb->chunk_lock, TRUE);
 844
 845     le = fcb->Vcb->chunks.Flink;
 846     while (le != &fcb->Vcb->chunks) {
 847         c = CONTAINING_RECORD(le, chunk, list_entry);
 848
 849         if (!c->readonly && !c->reloc) {
 850             ExAcquireResourceExclusiveLite(&c->lock, TRUE);
 851
 852             if (c->chunk_item->type == fcb->Vcb->data_flags && (c->chunk_item->size - c->used) >= comp_length) {
 853                 if (insert_extent_chunk(fcb->Vcb, fcb, c, start_data, comp_length, FALSE, comp_data, Irp, rollback, compression, end_data - start_data, FALSE, 0)) {
 854                     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 855
 856                     if (compression != BTRFS_COMPRESSION_NONE)
 857                         ExFreePool(comp_data);
 858
 859                     return STATUS_SUCCESS;
 860                 }
 861             }
 862
 863             ExReleaseResourceLite(&c->lock);
 864         }
 865
 866         le = le->Flink;
 867     }
 868
 869     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 870
 871     ExAcquireResourceExclusiveLite(&fcb->Vcb->chunk_lock, TRUE);
 872
 873     Status = alloc_chunk(fcb->Vcb, fcb->Vcb->data_flags, &c, FALSE);
 874
 875     ExReleaseResourceLite(&fcb->Vcb->chunk_lock);
 876
 877     if (!NT_SUCCESS(Status)) {
 878         ERR("alloc_chunk returned %08x\n", Status);
 879
 880         if (compression != BTRFS_COMPRESSION_NONE)
 881             ExFreePool(comp_data);
 882
 883         return Status;
 884     }
 885
 886     if (c) {
 887         ExAcquireResourceExclusiveLite(&c->lock, TRUE);
 888
 889         if (c->chunk_item->type == fcb->Vcb->data_flags && (c->chunk_item->size - c->used) >= comp_length) {
 890             if (insert_extent_chunk(fcb->Vcb, fcb, c, start_data, comp_length, FALSE, comp_data, Irp, rollback, compression, end_data - start_data, FALSE, 0)) {
 891                 if (compression != BTRFS_COMPRESSION_NONE)
 892                     ExFreePool(comp_data);
 893
 894                 return STATUS_SUCCESS;
 895             }
 896         }
 897
 898         ExReleaseResourceLite(&c->lock);
 899     }
 900
 901     WARN("couldn't find any data chunks with %llx bytes free\n", comp_length);
 902
 903     if (compression != BTRFS_COMPRESSION_NONE)
 904         ExFreePool(comp_data);
 905
 906     return STATUS_DISK_FULL;
 907 }
 908
 909 NTSTATUS write_compressed_bit(fcb* fcb, UINT64 start_data, UINT64 end_data, void* data, BOOL* compressed, PIRP Irp, LIST_ENTRY* rollback) {
 910     UINT8 type;
 911
 912     if (fcb->Vcb->options.compress_type != 0 && fcb->prop_compression == PropCompression_None)
 913         type = fcb->Vcb->options.compress_type;
 914     else {
 915         if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO) && fcb->prop_compression == PropCompression_LZO) {
 916             fcb->Vcb->superblock.incompat_flags |= BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO;
 917             type = BTRFS_COMPRESSION_LZO;
 918         } else if (fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO && fcb->prop_compression != PropCompression_Zlib)
 919             type = BTRFS_COMPRESSION_LZO;
 920         else
 921             type = BTRFS_COMPRESSION_ZLIB;
 922     }
 923
 924     if (type == BTRFS_COMPRESSION_LZO) {
 925         fcb->Vcb->superblock.incompat_flags |= BTRFS_INCOMPAT_FLAGS_COMPRESS_LZO;
 926         return lzo_write_compressed_bit(fcb, start_data, end_data, data, compressed, Irp, rollback);
 927     } else
 928         return zlib_write_compressed_bit(fcb, start_data, end_data, data, compressed, Irp, rollback);
 929 }