sdk/lib/fslib/btrfslib/btrfslib.c

   1 /* Copyright (c) Mark Harmstone 2016-17
   2  *
   3  * This file is part of WinBtrfs.
   4  *
   5  * WinBtrfs is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU Lesser General Public Licence as published by
   7  * the Free Software Foundation, either version 3 of the Licence, or
   8  * (at your option) any later version.
   9  *
  10  * WinBtrfs is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU Lesser General Public Licence for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public Licence
  16  * along with WinBtrfs.  If not, see <http://www.gnu.org/licenses/>. */
  17
  18 #include <stdlib.h>
  19 #include <stddef.h>
  20 #include <time.h>
  21 #include <ntstatus.h>
  22 #define WIN32_NO_STATUS
  23 #include <windef.h>
  24 #include <winbase.h>
  25 #ifndef __REACTOS__
  26 #include <winternl.h>
  27 #include <devioctl.h>
  28 #include <ntdddisk.h>
  29 #else
  30 #include <ndk/iofuncs.h>
  31 #include <ndk/obfuncs.h>
  32 #include <ndk/rtlfuncs.h>
  33 #endif
  34 #include <ntddscsi.h>
  35 #include <ntddstor.h>
  36 #include <ata.h>
  37 #include <mountmgr.h>
  38 #ifdef __REACTOS__
  39 #include <winnls.h>
  40 #include <stdbool.h>
  41 #include "btrfs.h"
  42 #include "btrfsioctl.h"
  43 #include "crc32c.h"
  44 #include "xxhash.h"
  45 #else
  46 #include <stringapiset.h>
  47 #include <stdbool.h>
  48 #include "../btrfs.h"
  49 #include "../btrfsioctl.h"
  50 #include "../crc32c.h"
  51 #include "../xxhash.h"
  52
  53 #if defined(_X86_) || defined(_AMD64_)
  54 #ifndef _MSC_VER
  55 #include <cpuid.h>
  56 #else
  57 #include <intrin.h>
  58 #endif
  59 #endif
  60 #endif // __REACTOS__
  61
  62 #ifdef __REACTOS__
  63 #define malloc(size)    RtlAllocateHeap(RtlGetProcessHeap(), 0, (size))
  64 #define free(ptr)       RtlFreeHeap(RtlGetProcessHeap(), 0, (ptr))
  65 #endif
  66
  67 #define SHA256_HASH_SIZE 32
  68 void calc_sha256(uint8_t* hash, const void* input, size_t len);
  69
  70 #define BLAKE2_HASH_SIZE 32
  71 void blake2b(void *out, size_t outlen, const void* in, size_t inlen);
  72
  73 #ifndef __REACTOS__
  74 #define FSCTL_LOCK_VOLUME               CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  6, METHOD_BUFFERED, FILE_ANY_ACCESS)
  75 #define FSCTL_UNLOCK_VOLUME             CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  7, METHOD_BUFFERED, FILE_ANY_ACCESS)
  76 #define FSCTL_DISMOUNT_VOLUME           CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  8, METHOD_BUFFERED, FILE_ANY_ACCESS)
  77
  78 #ifndef _MSC_VER // not in mingw yet
  79 #define DEVICE_DSM_FLAG_TRIM_NOT_FS_ALLOCATED 0x80000000
  80 #endif
  81
  82 #ifdef __cplusplus
  83 extern "C" {
  84 #endif
  85 NTSTATUS NTAPI NtWriteFile(HANDLE FileHandle, HANDLE Event, PIO_APC_ROUTINE ApcRoutine, PVOID ApcContext, PIO_STATUS_BLOCK IoStatusBlock, PVOID Buffer,
  86                            ULONG Length, PLARGE_INTEGER ByteOffset, PULONG Key);
  87
  88 NTSTATUS NTAPI NtReadFile(HANDLE FileHandle, HANDLE Event, PIO_APC_ROUTINE ApcRoutine, PVOID ApcContext, PIO_STATUS_BLOCK IoStatusBlock, PVOID Buffer,
  89                           ULONG Length, PLARGE_INTEGER ByteOffset, PULONG Key);
  90 #ifdef __cplusplus
  91 }
  92 #endif
  93 #endif // __REACTOS__
  94
  95 // These are undocumented, and what comes from format.exe
  96 typedef struct {
  97     void* table;
  98     void* unk1;
  99     WCHAR* string;
 100 } DSTRING;
 101
 102 typedef struct {
 103     void* table;
 104 } STREAM_MESSAGE;
 105
 106 #define FORMAT_FLAG_QUICK_FORMAT        0x00000001
 107 #define FORMAT_FLAG_UNKNOWN1            0x00000002
 108 #define FORMAT_FLAG_DISMOUNT_FIRST      0x00000004
 109 #define FORMAT_FLAG_UNKNOWN2            0x00000040
 110 #define FORMAT_FLAG_LARGE_RECORDS       0x00000100
 111 #define FORMAT_FLAG_INTEGRITY_DISABLE   0x00000100
 112
 113 typedef struct {
 114     uint16_t unk1;
 115     uint16_t unk2;
 116     uint32_t flags;
 117     DSTRING* label;
 118 } options;
 119
 120 #ifndef __REACTOS__
 121 FORCEINLINE VOID InitializeListHead(PLIST_ENTRY ListHead) {
 122     ListHead->Flink = ListHead->Blink = ListHead;
 123 }
 124
 125 FORCEINLINE VOID InsertTailList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry) {
 126     PLIST_ENTRY Blink;
 127
 128     Blink = ListHead->Blink;
 129     Entry->Flink = ListHead;
 130     Entry->Blink = Blink;
 131     Blink->Flink = Entry;
 132     ListHead->Blink = Entry;
 133 }
 134 #endif
 135
 136 #ifdef __REACTOS__
 137 ULONG NTAPI NtGetTickCount(VOID);
 138 #endif
 139
 140 typedef struct {
 141     KEY key;
 142     uint16_t size;
 143     void* data;
 144     LIST_ENTRY list_entry;
 145 } btrfs_item;
 146
 147 typedef struct {
 148     uint64_t offset;
 149     CHUNK_ITEM* chunk_item;
 150     uint64_t lastoff;
 151     uint64_t used;
 152     LIST_ENTRY list_entry;
 153 } btrfs_chunk;
 154
 155 typedef struct {
 156     uint64_t id;
 157     tree_header header;
 158     btrfs_chunk* c;
 159     LIST_ENTRY items;
 160     LIST_ENTRY list_entry;
 161 } btrfs_root;
 162
 163 typedef struct {
 164     DEV_ITEM dev_item;
 165     uint64_t last_alloc;
 166 } btrfs_dev;
 167
 168 #define keycmp(key1, key2)\
 169     ((key1.obj_id < key2.obj_id) ? -1 :\
 170     ((key1.obj_id > key2.obj_id) ? 1 :\
 171     ((key1.obj_type < key2.obj_type) ? -1 :\
 172     ((key1.obj_type > key2.obj_type) ? 1 :\
 173     ((key1.offset < key2.offset) ? -1 :\
 174     ((key1.offset > key2.offset) ? 1 :\
 175     0))))))
 176
 177 HMODULE module;
 178 ULONG def_sector_size = 0, def_node_size = 0;
 179 uint64_t def_incompat_flags = BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF | BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA;
 180 uint16_t def_csum_type = CSUM_TYPE_CRC32C;
 181
 182 #ifndef __REACTOS__
 183 // the following definitions come from fmifs.h in ReactOS
 184
 185 typedef struct {
 186     ULONG Lines;
 187     PCHAR Output;
 188 } TEXTOUTPUT, *PTEXTOUTPUT;
 189
 190 typedef enum {
 191     FMIFS_UNKNOWN0,
 192     FMIFS_UNKNOWN1,
 193     FMIFS_UNKNOWN2,
 194     FMIFS_UNKNOWN3,
 195     FMIFS_UNKNOWN4,
 196     FMIFS_UNKNOWN5,
 197     FMIFS_UNKNOWN6,
 198     FMIFS_UNKNOWN7,
 199     FMIFS_FLOPPY,
 200     FMIFS_UNKNOWN9,
 201     FMIFS_UNKNOWN10,
 202     FMIFS_REMOVABLE,
 203     FMIFS_HARDDISK,
 204     FMIFS_UNKNOWN13,
 205     FMIFS_UNKNOWN14,
 206     FMIFS_UNKNOWN15,
 207     FMIFS_UNKNOWN16,
 208     FMIFS_UNKNOWN17,
 209     FMIFS_UNKNOWN18,
 210     FMIFS_UNKNOWN19,
 211     FMIFS_UNKNOWN20,
 212     FMIFS_UNKNOWN21,
 213     FMIFS_UNKNOWN22,
 214     FMIFS_UNKNOWN23,
 215 } FMIFS_MEDIA_FLAG;
 216
 217 typedef enum {
 218     PROGRESS,
 219     DONEWITHSTRUCTURE,
 220     UNKNOWN2,
 221     UNKNOWN3,
 222     UNKNOWN4,
 223     UNKNOWN5,
 224     INSUFFICIENTRIGHTS,
 225     FSNOTSUPPORTED,
 226     VOLUMEINUSE,
 227     UNKNOWN9,
 228     UNKNOWNA,
 229     DONE,
 230     UNKNOWNC,
 231     UNKNOWND,
 232     OUTPUT,
 233     STRUCTUREPROGRESS,
 234     CLUSTERSIZETOOSMALL,
 235 } CALLBACKCOMMAND;
 236
 237 typedef BOOLEAN (NTAPI* PFMIFSCALLBACK)(CALLBACKCOMMAND Command, ULONG SubAction, PVOID ActionInfo);
 238
 239 #else
 240
 241 #include <fmifs/fmifs.h>
 242
 243 #endif // __REACTOS__
 244
 245 #ifndef __REACTOS__
 246 NTSTATUS WINAPI ChkdskEx(PUNICODE_STRING DriveRoot, BOOLEAN FixErrors, BOOLEAN Verbose, BOOLEAN CheckOnlyIfDirty,
 247                          BOOLEAN ScanDrive, PFMIFSCALLBACK Callback) {
 248 #else
 249 BOOLEAN
 250 NTAPI
 251 BtrfsChkdsk(
 252     IN PUNICODE_STRING DriveRoot,
 253     IN PFMIFSCALLBACK Callback,
 254     IN BOOLEAN FixErrors,
 255     IN BOOLEAN Verbose,
 256     IN BOOLEAN CheckOnlyIfDirty,
 257     IN BOOLEAN ScanDrive,
 258     IN PVOID pUnknown1,
 259     IN PVOID pUnknown2,
 260     IN PVOID pUnknown3,
 261     IN PVOID pUnknown4,
 262     IN PULONG ExitStatus)
 263 {
 264 #endif
 265     // STUB
 266
 267     if (Callback) {
 268         TEXTOUTPUT TextOut;
 269
 270         TextOut.Lines = 1;
 271         TextOut.Output = "stub, not implemented";
 272
 273         Callback(OUTPUT, 0, &TextOut);
 274     }
 275
 276 #ifndef __REACTOS__
 277     return STATUS_SUCCESS;
 278 #else
 279     *ExitStatus = (ULONG)STATUS_SUCCESS;
 280     return TRUE;
 281 #endif
 282 }
 283
 284 static btrfs_root* add_root(LIST_ENTRY* roots, uint64_t id) {
 285     btrfs_root* root;
 286
 287     root = malloc(sizeof(btrfs_root));
 288
 289     root->id = id;
 290     RtlZeroMemory(&root->header, sizeof(tree_header));
 291     InitializeListHead(&root->items);
 292     InsertTailList(roots, &root->list_entry);
 293
 294     return root;
 295 }
 296
 297 static void free_roots(LIST_ENTRY* roots) {
 298     LIST_ENTRY* le;
 299
 300     le = roots->Flink;
 301     while (le != roots) {
 302         LIST_ENTRY *le2 = le->Flink, *le3;
 303         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 304
 305         le3 = r->items.Flink;
 306         while (le3 != &r->items) {
 307             LIST_ENTRY* le4 = le3->Flink;
 308             btrfs_item* item = CONTAINING_RECORD(le3, btrfs_item, list_entry);
 309
 310             if (item->data)
 311                 free(item->data);
 312
 313             free(item);
 314
 315             le3 = le4;
 316         }
 317
 318         free(r);
 319
 320         le = le2;
 321     }
 322 }
 323
 324 static void free_chunks(LIST_ENTRY* chunks) {
 325     LIST_ENTRY* le;
 326
 327     le = chunks->Flink;
 328     while (le != chunks) {
 329         LIST_ENTRY *le2 = le->Flink;
 330         btrfs_chunk* c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
 331
 332         free(c->chunk_item);
 333         free(c);
 334
 335         le = le2;
 336     }
 337 }
 338
 339 static void add_item(btrfs_root* r, uint64_t obj_id, uint8_t obj_type, uint64_t offset, void* data, uint16_t size) {
 340     LIST_ENTRY* le;
 341     btrfs_item* item;
 342
 343     item = malloc(sizeof(btrfs_item));
 344
 345     item->key.obj_id = obj_id;
 346     item->key.obj_type = obj_type;
 347     item->key.offset = offset;
 348     item->size = size;
 349
 350     if (size == 0)
 351         item->data = NULL;
 352     else {
 353         item->data = malloc(size);
 354         memcpy(item->data, data, size);
 355     }
 356
 357     le = r->items.Flink;
 358     while (le != &r->items) {
 359         btrfs_item* i2 = CONTAINING_RECORD(le, btrfs_item, list_entry);
 360
 361         if (keycmp(item->key, i2->key) != 1) {
 362             InsertTailList(le, &item->list_entry);
 363             return;
 364         }
 365
 366         le = le->Flink;
 367     }
 368
 369     InsertTailList(&r->items, &item->list_entry);
 370 }
 371
 372 static uint64_t find_chunk_offset(uint64_t size, uint64_t offset, btrfs_dev* dev, btrfs_root* dev_root, BTRFS_UUID* chunkuuid) {
 373     uint64_t off;
 374     DEV_EXTENT de;
 375
 376     off = dev->last_alloc;
 377     dev->last_alloc += size;
 378
 379     dev->dev_item.bytes_used += size;
 380
 381     de.chunktree = BTRFS_ROOT_CHUNK;
 382     de.objid = 0x100;
 383     de.address = offset;
 384     de.length = size;
 385     de.chunktree_uuid = *chunkuuid;
 386
 387     add_item(dev_root, dev->dev_item.dev_id, TYPE_DEV_EXTENT, off, &de, sizeof(DEV_EXTENT));
 388
 389     return off;
 390 }
 391
 392 static btrfs_chunk* add_chunk(LIST_ENTRY* chunks, uint64_t flags, btrfs_root* chunk_root, btrfs_dev* dev, btrfs_root* dev_root, BTRFS_UUID* chunkuuid, uint32_t sector_size) {
 393     uint64_t off, size;
 394     uint16_t stripes, i;
 395     btrfs_chunk* c;
 396     LIST_ENTRY* le;
 397     CHUNK_ITEM_STRIPE* cis;
 398
 399     off = 0xc00000;
 400     le = chunks->Flink;
 401     while (le != chunks) {
 402         c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
 403
 404         if (c->offset + c->chunk_item->size > off)
 405             off = c->offset + c->chunk_item->size;
 406
 407         le = le->Flink;
 408     }
 409
 410     if (flags & BLOCK_FLAG_METADATA) {
 411         if (dev->dev_item.num_bytes > 0xC80000000) // 50 GB
 412             size = 0x40000000; // 1 GB
 413         else
 414             size = 0x10000000; // 256 MB
 415     } else if (flags & BLOCK_FLAG_SYSTEM)
 416         size = 0x800000;
 417
 418     size = min(size, dev->dev_item.num_bytes / 10); // cap at 10%
 419     size &= ~(sector_size - 1);
 420
 421     stripes = flags & BLOCK_FLAG_DUPLICATE ? 2 : 1;
 422
 423     if (dev->dev_item.num_bytes - dev->dev_item.bytes_used < stripes * size) // not enough space
 424         return NULL;
 425
 426     c = malloc(sizeof(btrfs_chunk));
 427     c->offset = off;
 428     c->lastoff = off;
 429     c->used = 0;
 430
 431     c->chunk_item = malloc(sizeof(CHUNK_ITEM) + (stripes * sizeof(CHUNK_ITEM_STRIPE)));
 432
 433     c->chunk_item->size = size;
 434     c->chunk_item->root_id = BTRFS_ROOT_EXTENT;
 435     c->chunk_item->stripe_length = max(sector_size, 0x10000);
 436     c->chunk_item->type = flags;
 437     c->chunk_item->opt_io_alignment = max(sector_size, 0x10000);
 438     c->chunk_item->opt_io_width = max(sector_size, 0x10000);
 439     c->chunk_item->sector_size = sector_size;
 440     c->chunk_item->num_stripes = stripes;
 441     c->chunk_item->sub_stripes = 0;
 442
 443     cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 444
 445     for (i = 0; i < stripes; i++) {
 446         cis[i].dev_id = dev->dev_item.dev_id;
 447         cis[i].offset = find_chunk_offset(size, c->offset, dev, dev_root, chunkuuid);
 448         cis[i].dev_uuid = dev->dev_item.device_uuid;
 449     }
 450
 451     add_item(chunk_root, 0x100, TYPE_CHUNK_ITEM, c->offset, c->chunk_item, sizeof(CHUNK_ITEM) + (stripes * sizeof(CHUNK_ITEM_STRIPE)));
 452
 453     InsertTailList(chunks, &c->list_entry);
 454
 455     return c;
 456 }
 457
 458 static bool superblock_collision(btrfs_chunk* c, uint64_t address) {
 459     CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 460     uint64_t stripe = (address - c->offset) / c->chunk_item->stripe_length;
 461     uint16_t i, j;
 462
 463     for (i = 0; i < c->chunk_item->num_stripes; i++) {
 464         j = 0;
 465         while (superblock_addrs[j] != 0) {
 466             if (superblock_addrs[j] >= cis[i].offset) {
 467                 uint64_t stripe2 = (superblock_addrs[j] - cis[i].offset) / c->chunk_item->stripe_length;
 468
 469                 if (stripe2 == stripe)
 470                     return true;
 471             }
 472             j++;
 473         }
 474     }
 475
 476     return false;
 477 }
 478
 479 static uint64_t get_next_address(btrfs_chunk* c) {
 480     uint64_t addr;
 481
 482     addr = c->lastoff;
 483
 484     while (superblock_collision(c, addr)) {
 485         addr = addr - ((addr - c->offset) % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
 486
 487         if (addr >= c->offset + c->chunk_item->size) // chunk has been exhausted
 488             return 0;
 489     }
 490
 491     return addr;
 492 }
 493
 494 typedef struct {
 495     EXTENT_ITEM ei;
 496     uint8_t type;
 497     TREE_BLOCK_REF tbr;
 498 } EXTENT_ITEM_METADATA;
 499
 500 typedef struct {
 501     EXTENT_ITEM ei;
 502     EXTENT_ITEM2 ei2;
 503     uint8_t type;
 504     TREE_BLOCK_REF tbr;
 505 } EXTENT_ITEM_METADATA2;
 506
 507 static void assign_addresses(LIST_ENTRY* roots, btrfs_chunk* sys_chunk, btrfs_chunk* metadata_chunk, uint32_t node_size,
 508                              btrfs_root* root_root, btrfs_root* extent_root, bool skinny) {
 509     LIST_ENTRY* le;
 510
 511     le = roots->Flink;
 512     while (le != roots) {
 513         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 514         btrfs_chunk* c = r->id == BTRFS_ROOT_CHUNK ? sys_chunk : metadata_chunk;
 515
 516         r->header.address = get_next_address(c);
 517         r->c = c;
 518         c->lastoff = r->header.address + node_size;
 519         c->used += node_size;
 520
 521         if (skinny) {
 522             EXTENT_ITEM_METADATA eim;
 523
 524             eim.ei.refcount = 1;
 525             eim.ei.generation = 1;
 526             eim.ei.flags = EXTENT_ITEM_TREE_BLOCK;
 527             eim.type = TYPE_TREE_BLOCK_REF;
 528             eim.tbr.offset = r->id;
 529
 530             add_item(extent_root, r->header.address, TYPE_METADATA_ITEM, 0, &eim, sizeof(EXTENT_ITEM_METADATA));
 531         } else {
 532             EXTENT_ITEM_METADATA2 eim2;
 533             KEY firstitem;
 534
 535             if (r->items.Flink == &r->items) {
 536                 firstitem.obj_id = 0;
 537                 firstitem.obj_type = 0;
 538                 firstitem.offset = 0;
 539             } else {
 540                 btrfs_item* bi = CONTAINING_RECORD(r->items.Flink, btrfs_item, list_entry);
 541
 542                 firstitem = bi->key;
 543             }
 544
 545             eim2.ei.refcount = 1;
 546             eim2.ei.generation = 1;
 547             eim2.ei.flags = EXTENT_ITEM_TREE_BLOCK;
 548             eim2.ei2.firstitem = firstitem;
 549             eim2.ei2.level = 0;
 550             eim2.type = TYPE_TREE_BLOCK_REF;
 551             eim2.tbr.offset = r->id;
 552
 553             add_item(extent_root, r->header.address, TYPE_EXTENT_ITEM, node_size, &eim2, sizeof(EXTENT_ITEM_METADATA2));
 554         }
 555
 556         if (r->id != BTRFS_ROOT_ROOT && r->id != BTRFS_ROOT_CHUNK) {
 557             ROOT_ITEM ri;
 558
 559             memset(&ri, 0, sizeof(ROOT_ITEM));
 560
 561             ri.inode.generation = 1;
 562             ri.inode.st_size = 3;
 563             ri.inode.st_blocks = node_size;
 564             ri.inode.st_nlink = 1;
 565             ri.inode.st_mode = 040755;
 566             ri.generation = 1;
 567             ri.objid = r->id == 5 || r->id >= 0x100 ? SUBVOL_ROOT_INODE : 0;
 568             ri.block_number = r->header.address;
 569             ri.bytes_used = node_size;
 570             ri.num_references = 1;
 571             ri.generation2 = ri.generation;
 572
 573             add_item(root_root, r->id, TYPE_ROOT_ITEM, 0, &ri, sizeof(ROOT_ITEM));
 574         }
 575
 576         le = le->Flink;
 577     }
 578 }
 579
 580 static NTSTATUS write_data(HANDLE h, uint64_t address, btrfs_chunk* c, void* data, ULONG size) {
 581     NTSTATUS Status;
 582     uint16_t i;
 583     IO_STATUS_BLOCK iosb;
 584     LARGE_INTEGER off;
 585     CHUNK_ITEM_STRIPE* cis;
 586
 587     cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 588
 589     for (i = 0; i < c->chunk_item->num_stripes; i++) {
 590         off.QuadPart = cis[i].offset + address - c->offset;
 591
 592         Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, data, size, &off, NULL);
 593         if (!NT_SUCCESS(Status))
 594             return Status;
 595     }
 596
 597     return STATUS_SUCCESS;
 598 }
 599
 600 static void calc_tree_checksum(tree_header* th, uint32_t node_size) {
 601     switch (def_csum_type) {
 602         case CSUM_TYPE_CRC32C:
 603             *(uint32_t*)th = ~calc_crc32c(0xffffffff, (uint8_t*)&th->fs_uuid, node_size - sizeof(th->csum));
 604         break;
 605
 606         case CSUM_TYPE_XXHASH:
 607             *(uint64_t*)th = XXH64((uint8_t*)&th->fs_uuid, node_size - sizeof(th->csum), 0);
 608         break;
 609
 610         case CSUM_TYPE_SHA256:
 611             calc_sha256((uint8_t*)th, &th->fs_uuid, node_size - sizeof(th->csum));
 612         break;
 613
 614         case CSUM_TYPE_BLAKE2:
 615             blake2b((uint8_t*)th, BLAKE2_HASH_SIZE, &th->fs_uuid, node_size - sizeof(th->csum));
 616         break;
 617     }
 618 }
 619
 620 static NTSTATUS write_roots(HANDLE h, LIST_ENTRY* roots, uint32_t node_size, BTRFS_UUID* fsuuid, BTRFS_UUID* chunkuuid) {
 621     LIST_ENTRY *le, *le2;
 622     NTSTATUS Status;
 623     uint8_t* tree;
 624
 625     tree = malloc(node_size);
 626
 627     le = roots->Flink;
 628     while (le != roots) {
 629         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 630         uint8_t* dp;
 631         leaf_node* ln;
 632
 633         memset(tree, 0, node_size);
 634
 635         r->header.num_items = 0;
 636         r->header.fs_uuid = *fsuuid;
 637         r->header.flags = HEADER_FLAG_MIXED_BACKREF | HEADER_FLAG_WRITTEN;
 638         r->header.chunk_tree_uuid = *chunkuuid;
 639         r->header.generation = 1;
 640         r->header.tree_id = r->id;
 641
 642         ln = (leaf_node*)(tree + sizeof(tree_header));
 643
 644         dp = tree + node_size;
 645
 646         le2 = r->items.Flink;
 647         while (le2 != &r->items) {
 648             btrfs_item* item = CONTAINING_RECORD(le2, btrfs_item, list_entry);
 649
 650             ln->key = item->key;
 651             ln->size = item->size;
 652
 653             if (item->size > 0) {
 654                 dp -= item->size;
 655                 memcpy(dp, item->data, item->size);
 656
 657                 ln->offset = (uint32_t)(dp - tree - sizeof(tree_header));
 658             } else
 659                 ln->offset = 0;
 660
 661             ln = &ln[1];
 662
 663             r->header.num_items++;
 664
 665             le2 = le2->Flink;
 666         }
 667
 668         memcpy(tree, &r->header, sizeof(tree_header));
 669
 670         calc_tree_checksum((tree_header*)tree, node_size);
 671
 672         Status = write_data(h, r->header.address, r->c, tree, node_size);
 673         if (!NT_SUCCESS(Status)) {
 674             free(tree);
 675             return Status;
 676         }
 677
 678         le = le->Flink;
 679     }
 680
 681     free(tree);
 682
 683     return STATUS_SUCCESS;
 684 }
 685
 686 #ifndef __REACTOS__
 687 static void get_uuid(BTRFS_UUID* uuid) {
 688 #else
 689 static void get_uuid(BTRFS_UUID* uuid, ULONG* seed) {
 690 #endif
 691     uint8_t i;
 692
 693     for (i = 0; i < 16; i+=2) {
 694 #ifndef __REACTOS__
 695         ULONG r = rand();
 696 #else
 697         ULONG r = RtlRandom(seed);
 698 #endif
 699
 700         uuid->uuid[i] = (r & 0xff00) >> 8;
 701         uuid->uuid[i+1] = r & 0xff;
 702     }
 703 }
 704
 705 #ifndef __REACTOS__
 706 static void init_device(btrfs_dev* dev, uint64_t id, uint64_t size, BTRFS_UUID* fsuuid, uint32_t sector_size) {
 707 #else
 708 static void init_device(btrfs_dev* dev, uint64_t id, uint64_t size, BTRFS_UUID* fsuuid, uint32_t sector_size, ULONG* seed) {
 709 #endif
 710     dev->dev_item.dev_id = id;
 711     dev->dev_item.num_bytes = size;
 712     dev->dev_item.bytes_used = 0;
 713     dev->dev_item.optimal_io_align = sector_size;
 714     dev->dev_item.optimal_io_width = sector_size;
 715     dev->dev_item.minimal_io_size = sector_size;
 716     dev->dev_item.type = 0;
 717     dev->dev_item.generation = 0;
 718     dev->dev_item.start_offset = 0;
 719     dev->dev_item.dev_group = 0;
 720     dev->dev_item.seek_speed = 0;
 721     dev->dev_item.bandwidth = 0;
 722 #ifndef __REACTOS__
 723     get_uuid(&dev->dev_item.device_uuid);
 724 #else
 725     get_uuid(&dev->dev_item.device_uuid, seed);
 726 #endif
 727     dev->dev_item.fs_uuid = *fsuuid;
 728
 729     dev->last_alloc = 0x100000; // skip first megabyte
 730 }
 731
 732 static void calc_superblock_checksum(superblock* sb) {
 733     switch (def_csum_type) {
 734         case CSUM_TYPE_CRC32C:
 735             *(uint32_t*)sb = ~calc_crc32c(0xffffffff, (uint8_t*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
 736         break;
 737
 738         case CSUM_TYPE_XXHASH:
 739             *(uint64_t*)sb = XXH64(&sb->uuid, sizeof(superblock) - sizeof(sb->checksum), 0);
 740         break;
 741
 742         case CSUM_TYPE_SHA256:
 743             calc_sha256((uint8_t*)sb, &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
 744         break;
 745
 746         case CSUM_TYPE_BLAKE2:
 747             blake2b((uint8_t*)sb, BLAKE2_HASH_SIZE, &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
 748         break;
 749     }
 750 }
 751
 752 static NTSTATUS write_superblocks(HANDLE h, btrfs_dev* dev, btrfs_root* chunk_root, btrfs_root* root_root, btrfs_root* extent_root,
 753                                   btrfs_chunk* sys_chunk, uint32_t node_size, BTRFS_UUID* fsuuid, uint32_t sector_size, PUNICODE_STRING label, uint64_t incompat_flags) {
 754     NTSTATUS Status;
 755     IO_STATUS_BLOCK iosb;
 756     ULONG sblen;
 757     int i;
 758     superblock* sb;
 759     KEY* key;
 760     uint64_t bytes_used;
 761     LIST_ENTRY* le;
 762
 763     sblen = sizeof(*sb);
 764     if (sblen & (sector_size - 1))
 765         sblen = (sblen & sector_size) + sector_size;
 766
 767     bytes_used = 0;
 768
 769     le = extent_root->items.Flink;
 770     while (le != &extent_root->items) {
 771         btrfs_item* item = CONTAINING_RECORD(le, btrfs_item, list_entry);
 772
 773         if (item->key.obj_type == TYPE_EXTENT_ITEM)
 774             bytes_used += item->key.offset;
 775         else if (item->key.obj_type == TYPE_METADATA_ITEM)
 776             bytes_used += node_size;
 777
 778         le = le->Flink;
 779     }
 780
 781     sb = malloc(sblen);
 782     memset(sb, 0, sblen);
 783
 784     sb->uuid = *fsuuid;
 785     sb->flags = 1;
 786     sb->magic = BTRFS_MAGIC;
 787     sb->generation = 1;
 788     sb->root_tree_addr = root_root->header.address;
 789     sb->chunk_tree_addr = chunk_root->header.address;
 790     sb->total_bytes = dev->dev_item.num_bytes;
 791     sb->bytes_used = bytes_used;
 792     sb->root_dir_objectid = BTRFS_ROOT_TREEDIR;
 793     sb->num_devices = 1;
 794     sb->sector_size = sector_size;
 795     sb->node_size = node_size;
 796     sb->leaf_size = node_size;
 797     sb->stripe_size = sector_size;
 798     sb->n = sizeof(KEY) + sizeof(CHUNK_ITEM) + (sys_chunk->chunk_item->num_stripes * sizeof(CHUNK_ITEM_STRIPE));
 799     sb->chunk_root_generation = 1;
 800     sb->incompat_flags = incompat_flags;
 801     sb->csum_type = def_csum_type;
 802     memcpy(&sb->dev_item, &dev->dev_item, sizeof(DEV_ITEM));
 803
 804     if (label->Length > 0) {
 805 #ifdef __REACTOS__
 806         ANSI_STRING as;
 807         unsigned int i;
 808
 809         for (i = 0; i < label->Length / sizeof(WCHAR); i++) {
 810 #else
 811         ULONG utf8len;
 812
 813         for (unsigned int i = 0; i < label->Length / sizeof(WCHAR); i++) {
 814 #endif
 815             if (label->Buffer[i] == '/' || label->Buffer[i] == '\\') {
 816                 free(sb);
 817                 return STATUS_INVALID_VOLUME_LABEL;
 818             }
 819         }
 820
 821 #ifndef __REACTOS__
 822         utf8len = WideCharToMultiByte(CP_UTF8, 0, label->Buffer, label->Length / sizeof(WCHAR), NULL, 0, NULL, NULL);
 823
 824         if (utf8len == 0 || utf8len > MAX_LABEL_SIZE) {
 825             free(sb);
 826             return STATUS_INVALID_VOLUME_LABEL;
 827         }
 828
 829         if (WideCharToMultiByte(CP_UTF8, 0, label->Buffer, label->Length / sizeof(WCHAR), sb->label, utf8len, NULL, NULL) == 0) {
 830 #else
 831         as.Buffer = sb->label;
 832         as.Length = 0;
 833         as.MaximumLength = MAX_LABEL_SIZE;
 834
 835         if (!NT_SUCCESS(RtlUnicodeStringToAnsiString(&as, label, FALSE)))
 836         {
 837 #endif
 838             free(sb);
 839             return STATUS_INVALID_VOLUME_LABEL;
 840         }
 841     }
 842     sb->cache_generation = 0xffffffffffffffff;
 843
 844     key = (KEY*)sb->sys_chunk_array;
 845     key->obj_id = 0x100;
 846     key->obj_type = TYPE_CHUNK_ITEM;
 847     key->offset = sys_chunk->offset;
 848     memcpy(&key[1], sys_chunk->chunk_item, sizeof(CHUNK_ITEM) + (sys_chunk->chunk_item->num_stripes * sizeof(CHUNK_ITEM_STRIPE)));
 849
 850     i = 0;
 851     while (superblock_addrs[i] != 0) {
 852         LARGE_INTEGER off;
 853
 854         if (superblock_addrs[i] > dev->dev_item.num_bytes)
 855             break;
 856
 857         sb->sb_phys_addr = superblock_addrs[i];
 858
 859         calc_superblock_checksum(sb);
 860
 861         off.QuadPart = superblock_addrs[i];
 862
 863         Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, sb, sblen, &off, NULL);
 864         if (!NT_SUCCESS(Status)) {
 865             free(sb);
 866             return Status;
 867         }
 868
 869         i++;
 870     }
 871
 872     free(sb);
 873
 874     return STATUS_SUCCESS;
 875 }
 876
 877 static __inline void win_time_to_unix(LARGE_INTEGER t, BTRFS_TIME* out) {
 878     ULONGLONG l = t.QuadPart - 116444736000000000;
 879
 880     out->seconds = l / 10000000;
 881     out->nanoseconds = (l % 10000000) * 100;
 882 }
 883
 884 #ifdef __REACTOS__
 885 VOID
 886 WINAPI
 887 GetSystemTimeAsFileTime(OUT PFILETIME lpFileTime)
 888 {
 889     LARGE_INTEGER SystemTime;
 890
 891     do
 892     {
 893         SystemTime.HighPart = SharedUserData->SystemTime.High1Time;
 894         SystemTime.LowPart = SharedUserData->SystemTime.LowPart;
 895     }
 896     while (SystemTime.HighPart != SharedUserData->SystemTime.High2Time);
 897
 898     lpFileTime->dwLowDateTime = SystemTime.LowPart;
 899     lpFileTime->dwHighDateTime = SystemTime.HighPart;
 900 }
 901 #endif
 902
 903 static void add_inode_ref(btrfs_root* r, uint64_t inode, uint64_t parent, uint64_t index, const char* name) {
 904     uint16_t name_len = (uint16_t)strlen(name);
 905     INODE_REF* ir = malloc(offsetof(INODE_REF, name[0]) + name_len);
 906
 907     ir->index = 0;
 908     ir->n = name_len;
 909     memcpy(ir->name, name, name_len);
 910
 911     add_item(r, inode, TYPE_INODE_REF, parent, ir, (uint16_t)offsetof(INODE_REF, name[0]) + ir->n);
 912
 913     free(ir);
 914 }
 915
 916 static void init_fs_tree(btrfs_root* r, uint32_t node_size) {
 917     INODE_ITEM ii;
 918     FILETIME filetime;
 919     LARGE_INTEGER time;
 920
 921     memset(&ii, 0, sizeof(INODE_ITEM));
 922
 923     ii.generation = 1;
 924     ii.st_blocks = node_size;
 925     ii.st_nlink = 1;
 926     ii.st_mode = 040755;
 927
 928     GetSystemTimeAsFileTime(&filetime);
 929     time.LowPart = filetime.dwLowDateTime;
 930     time.HighPart = filetime.dwHighDateTime;
 931
 932     win_time_to_unix(time, &ii.st_atime);
 933     ii.st_ctime = ii.st_mtime = ii.st_atime;
 934
 935     add_item(r, SUBVOL_ROOT_INODE, TYPE_INODE_ITEM, 0, &ii, sizeof(INODE_ITEM));
 936
 937     add_inode_ref(r, SUBVOL_ROOT_INODE, SUBVOL_ROOT_INODE, 0, "..");
 938 }
 939
 940 static void add_block_group_items(LIST_ENTRY* chunks, btrfs_root* extent_root) {
 941     LIST_ENTRY* le;
 942
 943     le = chunks->Flink;
 944     while (le != chunks) {
 945         btrfs_chunk* c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
 946         BLOCK_GROUP_ITEM bgi;
 947
 948         bgi.used = c->used;
 949         bgi.chunk_tree = 0x100;
 950         bgi.flags = c->chunk_item->type;
 951         add_item(extent_root, c->offset, TYPE_BLOCK_GROUP_ITEM, c->chunk_item->size, &bgi, sizeof(BLOCK_GROUP_ITEM));
 952
 953         le = le->Flink;
 954     }
 955 }
 956
 957 static NTSTATUS clear_first_megabyte(HANDLE h) {
 958     NTSTATUS Status;
 959     IO_STATUS_BLOCK iosb;
 960     LARGE_INTEGER zero;
 961     uint8_t* mb;
 962
 963     mb = malloc(0x100000);
 964     memset(mb, 0, 0x100000);
 965
 966     zero.QuadPart = 0;
 967
 968     Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, mb, 0x100000, &zero, NULL);
 969
 970     free(mb);
 971
 972     return Status;
 973 }
 974
 975 static bool is_ssd(HANDLE h) {
 976     ULONG aptelen;
 977     ATA_PASS_THROUGH_EX* apte;
 978     IO_STATUS_BLOCK iosb;
 979     NTSTATUS Status;
 980     IDENTIFY_DEVICE_DATA* idd;
 981
 982     aptelen = sizeof(ATA_PASS_THROUGH_EX) + 512;
 983     apte = malloc(aptelen);
 984
 985     RtlZeroMemory(apte, aptelen);
 986
 987     apte->Length = sizeof(ATA_PASS_THROUGH_EX);
 988     apte->AtaFlags = ATA_FLAGS_DATA_IN;
 989     apte->DataTransferLength = aptelen - sizeof(ATA_PASS_THROUGH_EX);
 990     apte->TimeOutValue = 3;
 991     apte->DataBufferOffset = apte->Length;
 992     apte->CurrentTaskFile[6] = IDE_COMMAND_IDENTIFY;
 993
 994     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_ATA_PASS_THROUGH, apte, aptelen, apte, aptelen);
 995
 996     if (NT_SUCCESS(Status)) {
 997         idd = (IDENTIFY_DEVICE_DATA*)((uint8_t*)apte + sizeof(ATA_PASS_THROUGH_EX));
 998
 999         if (idd->NominalMediaRotationRate == 1) {
1000             free(apte);
1001             return true;
1002         }
1003     }
1004
1005     free(apte);
1006
1007     return false;
1008 }
1009
1010 static void add_dir_item(btrfs_root* root, uint64_t inode, uint32_t hash, uint64_t key_objid, uint8_t key_type,
1011                          uint64_t key_offset, uint64_t transid, uint8_t type, const char* name) {
1012     uint16_t name_len = (uint16_t)strlen(name);
1013     DIR_ITEM* di = malloc(offsetof(DIR_ITEM, name[0]) + name_len);
1014
1015     di->key.obj_id = key_objid;
1016     di->key.obj_type = key_type;
1017     di->key.offset = key_offset;
1018     di->transid = transid;
1019     di->m = 0;
1020     di->n = name_len;
1021     di->type = type;
1022     memcpy(di->name, name, name_len);
1023
1024     add_item(root, inode, TYPE_DIR_ITEM, hash, di, (uint16_t)(offsetof(DIR_ITEM, name[0]) + di->m + di->n));
1025
1026     free(di);
1027 }
1028
1029 static void set_default_subvol(btrfs_root* root_root, uint32_t node_size) {
1030     INODE_ITEM ii;
1031     FILETIME filetime;
1032     LARGE_INTEGER time;
1033
1034     static const char default_subvol[] = "default";
1035     static const uint32_t default_hash = 0x8dbfc2d2;
1036
1037     add_inode_ref(root_root, BTRFS_ROOT_FSTREE, BTRFS_ROOT_TREEDIR, 0, default_subvol);
1038
1039     memset(&ii, 0, sizeof(INODE_ITEM));
1040
1041     ii.generation = 1;
1042     ii.st_blocks = node_size;
1043     ii.st_nlink = 1;
1044     ii.st_mode = 040755;
1045
1046     GetSystemTimeAsFileTime(&filetime);
1047     time.LowPart = filetime.dwLowDateTime;
1048     time.HighPart = filetime.dwHighDateTime;
1049
1050     win_time_to_unix(time, &ii.st_atime);
1051     ii.st_ctime = ii.st_mtime = ii.otime = ii.st_atime;
1052
1053     add_item(root_root, BTRFS_ROOT_TREEDIR, TYPE_INODE_ITEM, 0, &ii, sizeof(INODE_ITEM));
1054
1055     add_inode_ref(root_root, BTRFS_ROOT_TREEDIR, BTRFS_ROOT_TREEDIR, 0, "..");
1056
1057     add_dir_item(root_root, BTRFS_ROOT_TREEDIR, default_hash, BTRFS_ROOT_FSTREE, TYPE_ROOT_ITEM,
1058                  0xffffffffffffffff, 0, BTRFS_TYPE_DIRECTORY, default_subvol);
1059 }
1060
1061 static NTSTATUS write_btrfs(HANDLE h, uint64_t size, PUNICODE_STRING label, uint32_t sector_size, uint32_t node_size, uint64_t incompat_flags) {
1062     NTSTATUS Status;
1063     LIST_ENTRY roots, chunks;
1064     btrfs_root *root_root, *chunk_root, *extent_root, *dev_root, *fs_root, *reloc_root;
1065     btrfs_chunk *sys_chunk, *metadata_chunk;
1066     btrfs_dev dev;
1067     BTRFS_UUID fsuuid, chunkuuid;
1068     bool ssd;
1069     uint64_t metadata_flags;
1070 #ifdef __REACTOS__
1071     ULONG seed;
1072 #endif
1073
1074 #ifndef __REACTOS__
1075     srand((unsigned int)time(0));
1076     get_uuid(&fsuuid);
1077     get_uuid(&chunkuuid);
1078 #else
1079     seed = NtGetTickCount();
1080     get_uuid(&fsuuid, &seed);
1081     get_uuid(&chunkuuid, &seed);
1082 #endif
1083
1084     InitializeListHead(&roots);
1085     InitializeListHead(&chunks);
1086
1087     root_root = add_root(&roots, BTRFS_ROOT_ROOT);
1088     chunk_root = add_root(&roots, BTRFS_ROOT_CHUNK);
1089     extent_root = add_root(&roots, BTRFS_ROOT_EXTENT);
1090     dev_root = add_root(&roots, BTRFS_ROOT_DEVTREE);
1091     add_root(&roots, BTRFS_ROOT_CHECKSUM);
1092     fs_root = add_root(&roots, BTRFS_ROOT_FSTREE);
1093     reloc_root = add_root(&roots, BTRFS_ROOT_DATA_RELOC);
1094
1095 #ifndef __REACTOS__
1096     init_device(&dev, 1, size, &fsuuid, sector_size);
1097 #else
1098     init_device(&dev, 1, size, &fsuuid, sector_size, &seed);
1099 #endif
1100
1101     ssd = is_ssd(h);
1102
1103     sys_chunk = add_chunk(&chunks, BLOCK_FLAG_SYSTEM | (ssd ? 0 : BLOCK_FLAG_DUPLICATE), chunk_root, &dev, dev_root, &chunkuuid, sector_size);
1104     if (!sys_chunk)
1105         return STATUS_INTERNAL_ERROR;
1106
1107     metadata_flags = BLOCK_FLAG_METADATA;
1108
1109     if (!ssd && !(incompat_flags & BTRFS_INCOMPAT_FLAGS_MIXED_GROUPS))
1110         metadata_flags |= BLOCK_FLAG_DUPLICATE;
1111
1112     if (incompat_flags & BTRFS_INCOMPAT_FLAGS_MIXED_GROUPS)
1113         metadata_flags |= BLOCK_FLAG_DATA;
1114
1115     metadata_chunk = add_chunk(&chunks, metadata_flags, chunk_root, &dev, dev_root, &chunkuuid, sector_size);
1116     if (!metadata_chunk)
1117         return STATUS_INTERNAL_ERROR;
1118
1119     add_item(chunk_root, 1, TYPE_DEV_ITEM, dev.dev_item.dev_id, &dev.dev_item, sizeof(DEV_ITEM));
1120
1121     set_default_subvol(root_root, node_size);
1122
1123     init_fs_tree(fs_root, node_size);
1124     init_fs_tree(reloc_root, node_size);
1125
1126     assign_addresses(&roots, sys_chunk, metadata_chunk, node_size, root_root, extent_root, incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA);
1127
1128     add_block_group_items(&chunks, extent_root);
1129
1130     Status = write_roots(h, &roots, node_size, &fsuuid, &chunkuuid);
1131     if (!NT_SUCCESS(Status))
1132         return Status;
1133
1134     Status = clear_first_megabyte(h);
1135     if (!NT_SUCCESS(Status))
1136         return Status;
1137
1138     Status = write_superblocks(h, &dev, chunk_root, root_root, extent_root, sys_chunk, node_size, &fsuuid, sector_size, label, incompat_flags);
1139     if (!NT_SUCCESS(Status))
1140         return Status;
1141
1142     free_roots(&roots);
1143     free_chunks(&chunks);
1144
1145     return STATUS_SUCCESS;
1146 }
1147
1148 static bool look_for_device(btrfs_filesystem* bfs, BTRFS_UUID* devuuid) {
1149     uint32_t i;
1150     btrfs_filesystem_device* dev;
1151
1152     for (i = 0; i < bfs->num_devices; i++) {
1153         if (i == 0)
1154             dev = &bfs->device;
1155         else
1156             dev = (btrfs_filesystem_device*)((uint8_t*)dev + offsetof(btrfs_filesystem_device, name[0]) + dev->name_length);
1157
1158         if (RtlCompareMemory(&dev->uuid, devuuid, sizeof(BTRFS_UUID)) == sizeof(BTRFS_UUID))
1159             return true;
1160     }
1161
1162     return false;
1163 }
1164
1165 static bool check_superblock_checksum(superblock* sb) {
1166     switch (sb->csum_type) {
1167         case CSUM_TYPE_CRC32C: {
1168             uint32_t crc32 = ~calc_crc32c(0xffffffff, (uint8_t*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
1169
1170             return crc32 == *(uint32_t*)sb;
1171         }
1172
1173         case CSUM_TYPE_XXHASH: {
1174             uint64_t hash = XXH64(&sb->uuid, sizeof(superblock) - sizeof(sb->checksum), 0);
1175
1176             return hash == *(uint64_t*)sb;
1177         }
1178
1179         case CSUM_TYPE_SHA256: {
1180             uint8_t hash[SHA256_HASH_SIZE];
1181
1182             calc_sha256(hash, &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
1183
1184             return !memcmp(hash, sb, SHA256_HASH_SIZE);
1185         }
1186
1187         case CSUM_TYPE_BLAKE2: {
1188             uint8_t hash[BLAKE2_HASH_SIZE];
1189
1190             blake2b(hash, sizeof(hash), &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
1191
1192             return !memcmp(hash, sb, BLAKE2_HASH_SIZE);
1193         }
1194
1195         default:
1196             return false;
1197     }
1198 }
1199
1200 static bool is_mounted_multi_device(HANDLE h, uint32_t sector_size) {
1201     NTSTATUS Status;
1202     superblock* sb;
1203     ULONG sblen;
1204     IO_STATUS_BLOCK iosb;
1205     LARGE_INTEGER off;
1206     BTRFS_UUID fsuuid, devuuid;
1207     UNICODE_STRING us;
1208     OBJECT_ATTRIBUTES atts;
1209     HANDLE h2;
1210     btrfs_filesystem *bfs = NULL, *bfs2;
1211     ULONG bfssize;
1212     bool ret = false;
1213
1214     static WCHAR btrfs[] = L"\\Btrfs";
1215
1216     sblen = sizeof(*sb);
1217     if (sblen & (sector_size - 1))
1218         sblen = (sblen & sector_size) + sector_size;
1219
1220     sb = malloc(sblen);
1221
1222     off.QuadPart = superblock_addrs[0];
1223
1224     Status = NtReadFile(h, NULL, NULL, NULL, &iosb, sb, sblen, &off, NULL);
1225     if (!NT_SUCCESS(Status)) {
1226         free(sb);
1227         return false;
1228     }
1229
1230     if (sb->magic != BTRFS_MAGIC) {
1231         free(sb);
1232         return false;
1233     }
1234
1235     if (!check_superblock_checksum(sb)) {
1236         free(sb);
1237         return false;
1238     }
1239
1240     fsuuid = sb->uuid;
1241     devuuid = sb->dev_item.device_uuid;
1242
1243     free(sb);
1244
1245     us.Length = us.MaximumLength = (USHORT)(wcslen(btrfs) * sizeof(WCHAR));
1246     us.Buffer = btrfs;
1247
1248     InitializeObjectAttributes(&atts, &us, 0, NULL, NULL);
1249
1250     Status = NtOpenFile(&h2, SYNCHRONIZE | FILE_READ_ATTRIBUTES, &atts, &iosb,
1251                         FILE_SHARE_READ | FILE_SHARE_WRITE, FILE_SYNCHRONOUS_IO_ALERT);
1252     if (!NT_SUCCESS(Status)) // not a problem, it usually just means the driver isn't loaded
1253         return false;
1254
1255     bfssize = 0;
1256
1257     do {
1258         bfssize += 1024;
1259
1260         if (bfs) free(bfs);
1261         bfs = malloc(bfssize);
1262
1263         Status = NtDeviceIoControlFile(h2, NULL, NULL, NULL, &iosb, IOCTL_BTRFS_QUERY_FILESYSTEMS, NULL, 0, bfs, bfssize);
1264     } while (Status == STATUS_BUFFER_OVERFLOW);
1265
1266     if (!NT_SUCCESS(Status))
1267         goto end;
1268
1269     if (bfs->num_devices != 0) {
1270         bfs2 = bfs;
1271         while (true) {
1272             if (RtlCompareMemory(&bfs2->uuid, &fsuuid, sizeof(BTRFS_UUID)) == sizeof(BTRFS_UUID)) {
1273                 if (bfs2->num_devices == 1)
1274                     ret = false;
1275                 else
1276                     ret = look_for_device(bfs2, &devuuid);
1277
1278                 goto end;
1279             }
1280
1281             if (bfs2->next_entry == 0)
1282                 break;
1283             else
1284                 bfs2 = (btrfs_filesystem*)((uint8_t*)bfs2 + bfs2->next_entry);
1285         }
1286     }
1287
1288 end:
1289     NtClose(h2);
1290
1291     if (bfs)
1292         free(bfs);
1293
1294     return ret;
1295 }
1296
1297 static void do_full_trim(HANDLE h) {
1298     IO_STATUS_BLOCK iosb;
1299     DEVICE_MANAGE_DATA_SET_ATTRIBUTES dmdsa;
1300
1301     RtlZeroMemory(&dmdsa, sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES));
1302
1303     dmdsa.Size = sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES);
1304     dmdsa.Action = DeviceDsmAction_Trim;
1305     dmdsa.Flags = DEVICE_DSM_FLAG_ENTIRE_DATA_SET_RANGE | DEVICE_DSM_FLAG_TRIM_NOT_FS_ALLOCATED;
1306     dmdsa.ParameterBlockOffset = 0;
1307     dmdsa.ParameterBlockLength = 0;
1308     dmdsa.DataSetRangesOffset = 0;
1309     dmdsa.DataSetRangesLength = 0;
1310
1311     NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_STORAGE_MANAGE_DATA_SET_ATTRIBUTES, &dmdsa, sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES), NULL, 0);
1312 }
1313
1314 static bool is_power_of_two(ULONG i) {
1315     return ((i != 0) && !(i & (i - 1)));
1316 }
1317
1318 #if !defined(__REACTOS__) && (defined(_X86_) || defined(_AMD64_))
1319 static void check_cpu() {
1320     unsigned int cpuInfo[4];
1321     bool have_sse42;
1322
1323 #ifndef _MSC_VER
1324     __get_cpuid(1, &cpuInfo[0], &cpuInfo[1], &cpuInfo[2], &cpuInfo[3]);
1325     have_sse42 = cpuInfo[2] & bit_SSE4_2;
1326 #else
1327     __cpuid(cpuInfo, 1);
1328     have_sse42 = cpuInfo[2] & (1 << 20);
1329 #endif
1330
1331     if (have_sse42)
1332         calc_crc32c = calc_crc32c_hw;
1333 }
1334 #endif
1335
1336 static NTSTATUS NTAPI FormatEx2(PUNICODE_STRING DriveRoot, FMIFS_MEDIA_FLAG MediaFlag, PUNICODE_STRING Label,
1337                                 BOOLEAN QuickFormat, ULONG ClusterSize, PFMIFSCALLBACK Callback)
1338 {
1339     NTSTATUS Status;
1340     HANDLE h, btrfsh;
1341     OBJECT_ATTRIBUTES attr;
1342     IO_STATUS_BLOCK iosb;
1343     GET_LENGTH_INFORMATION gli;
1344     DISK_GEOMETRY dg;
1345     uint32_t sector_size, node_size;
1346     UNICODE_STRING btrfsus;
1347 #ifndef __REACTOS__
1348     HANDLE token;
1349     TOKEN_PRIVILEGES tp;
1350     LUID luid;
1351 #endif
1352     uint64_t incompat_flags;
1353     UNICODE_STRING empty_label;
1354
1355     static WCHAR btrfs[] = L"\\Btrfs";
1356
1357 #ifndef __REACTOS__
1358     if (!OpenProcessToken(GetCurrentProcess(), TOKEN_ADJUST_PRIVILEGES | TOKEN_QUERY, &token))
1359         return STATUS_PRIVILEGE_NOT_HELD;
1360
1361     if (!LookupPrivilegeValueW(NULL, L"SeManageVolumePrivilege", &luid)) {
1362         CloseHandle(token);
1363         return STATUS_PRIVILEGE_NOT_HELD;
1364     }
1365
1366     tp.PrivilegeCount = 1;
1367     tp.Privileges[0].Luid = luid;
1368     tp.Privileges[0].Attributes = SE_PRIVILEGE_ENABLED;
1369
1370     if (!AdjustTokenPrivileges(token, false, &tp, sizeof(TOKEN_PRIVILEGES), NULL, NULL)) {
1371         CloseHandle(token);
1372         return STATUS_PRIVILEGE_NOT_HELD;
1373     }
1374
1375     CloseHandle(token);
1376
1377 #if defined(_X86_) || defined(_AMD64_)
1378     check_cpu();
1379 #endif
1380 #endif
1381
1382     if (def_csum_type != CSUM_TYPE_CRC32C && def_csum_type != CSUM_TYPE_XXHASH && def_csum_type != CSUM_TYPE_SHA256 &&
1383         def_csum_type != CSUM_TYPE_BLAKE2)
1384         return STATUS_INVALID_PARAMETER;
1385
1386     InitializeObjectAttributes(&attr, DriveRoot, OBJ_CASE_INSENSITIVE, NULL, NULL);
1387
1388     Status = NtOpenFile(&h, FILE_GENERIC_READ | FILE_GENERIC_WRITE, &attr, &iosb,
1389                         FILE_SHARE_READ, FILE_SYNCHRONOUS_IO_ALERT);
1390
1391     if (!NT_SUCCESS(Status))
1392         return Status;
1393
1394     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_DISK_GET_LENGTH_INFO, NULL, 0, &gli, sizeof(gli));
1395     if (!NT_SUCCESS(Status)) {
1396         NtClose(h);
1397         return Status;
1398     }
1399
1400     // MSDN tells us to use IOCTL_DISK_GET_DRIVE_GEOMETRY_EX, but there are
1401     // some instances where it fails and IOCTL_DISK_GET_DRIVE_GEOMETRY succeeds -
1402     // such as with spanned volumes.
1403     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_DISK_GET_DRIVE_GEOMETRY, NULL, 0, &dg, sizeof(dg));
1404     if (!NT_SUCCESS(Status)) {
1405         NtClose(h);
1406         return Status;
1407     }
1408
1409     if (def_sector_size == 0) {
1410         sector_size = dg.BytesPerSector;
1411
1412         if (sector_size == 0x200 || sector_size == 0)
1413             sector_size = 0x1000;
1414     } else {
1415         if (dg.BytesPerSector != 0 && (def_sector_size < dg.BytesPerSector || def_sector_size % dg.BytesPerSector != 0 || !is_power_of_two(def_sector_size / dg.BytesPerSector))) {
1416             NtClose(h);
1417             return STATUS_INVALID_PARAMETER;
1418         }
1419
1420         sector_size = def_sector_size;
1421     }
1422
1423     if (def_node_size == 0)
1424         node_size = 0x4000;
1425     else {
1426         if (def_node_size < sector_size || def_node_size % sector_size != 0 || !is_power_of_two(def_node_size / sector_size)) {
1427             NtClose(h);
1428             return STATUS_INVALID_PARAMETER;
1429         }
1430
1431         node_size = def_node_size;
1432     }
1433
1434     if (Callback) {
1435         ULONG pc = 0;
1436         Callback(PROGRESS, 0, (PVOID)&pc);
1437     }
1438
1439     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_LOCK_VOLUME, NULL, 0, NULL, 0);
1440
1441     if (is_mounted_multi_device(h, sector_size)) {
1442         Status = STATUS_ACCESS_DENIED;
1443         goto end;
1444     }
1445
1446     do_full_trim(h);
1447
1448     incompat_flags = def_incompat_flags;
1449     incompat_flags |= BTRFS_INCOMPAT_FLAGS_MIXED_BACKREF | BTRFS_INCOMPAT_FLAGS_BIG_METADATA;
1450
1451     if (!Label) {
1452         empty_label.Buffer = NULL;
1453         empty_label.Length = empty_label.MaximumLength = 0;
1454         Label = &empty_label;
1455     }
1456
1457     Status = write_btrfs(h, gli.Length.QuadPart, Label, sector_size, node_size, incompat_flags);
1458
1459     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_DISMOUNT_VOLUME, NULL, 0, NULL, 0);
1460
1461 end:
1462     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_UNLOCK_VOLUME, NULL, 0, NULL, 0);
1463
1464     NtClose(h);
1465
1466     if (NT_SUCCESS(Status)) {
1467         btrfsus.Buffer = btrfs;
1468         btrfsus.Length = btrfsus.MaximumLength = (USHORT)(wcslen(btrfs) * sizeof(WCHAR));
1469
1470         InitializeObjectAttributes(&attr, &btrfsus, 0, NULL, NULL);
1471
1472         Status = NtOpenFile(&btrfsh, FILE_GENERIC_READ | FILE_GENERIC_WRITE, &attr, &iosb,
1473                             FILE_SHARE_READ, FILE_SYNCHRONOUS_IO_ALERT);
1474
1475         if (NT_SUCCESS(Status)) {
1476             MOUNTDEV_NAME* mdn;
1477             ULONG mdnsize;
1478
1479             mdnsize = (ULONG)(offsetof(MOUNTDEV_NAME, Name[0]) + DriveRoot->Length);
1480             mdn = malloc(mdnsize);
1481
1482             mdn->NameLength = DriveRoot->Length;
1483             memcpy(mdn->Name, DriveRoot->Buffer, DriveRoot->Length);
1484
1485             NtDeviceIoControlFile(btrfsh, NULL, NULL, NULL, &iosb, IOCTL_BTRFS_PROBE_VOLUME, mdn, mdnsize, NULL, 0);
1486
1487             free(mdn);
1488
1489             NtClose(btrfsh);
1490         }
1491
1492         Status = STATUS_SUCCESS;
1493     }
1494
1495 #ifndef __REACTOS__
1496     if (Callback) {
1497         bool success = NT_SUCCESS(Status);
1498         Callback(DONE, 0, (PVOID)&success);
1499     }
1500 #endif
1501
1502     return Status;
1503 }
1504
1505 #ifdef __REACTOS__
1506
1507 BOOLEAN
1508 NTAPI
1509 BtrfsFormat(
1510     IN PUNICODE_STRING DriveRoot,
1511     IN PFMIFSCALLBACK Callback,
1512     IN BOOLEAN QuickFormat,
1513     IN BOOLEAN BackwardCompatible,
1514     IN MEDIA_TYPE MediaType,
1515     IN PUNICODE_STRING Label,
1516     IN ULONG ClusterSize)
1517 {
1518     NTSTATUS Status;
1519
1520     if (BackwardCompatible)
1521     {
1522         // DPRINT1("BackwardCompatible == TRUE is unsupported!\n");
1523         return FALSE;
1524     }
1525
1526     Status = FormatEx2(DriveRoot, (FMIFS_MEDIA_FLAG)MediaType, Label, QuickFormat, ClusterSize, Callback);
1527
1528     return NT_SUCCESS(Status);
1529 }
1530
1531 #else
1532
1533 BOOL __stdcall FormatEx(DSTRING* root, STREAM_MESSAGE* message, options* opts, uint32_t unk1) {
1534     UNICODE_STRING DriveRoot, Label;
1535     NTSTATUS Status;
1536
1537     if (!root || !root->string)
1538         return false;
1539
1540     DriveRoot.Length = DriveRoot.MaximumLength = (USHORT)(wcslen(root->string) * sizeof(WCHAR));
1541     DriveRoot.Buffer = root->string;
1542
1543     if (opts && opts->label && opts->label->string) {
1544         Label.Length = Label.MaximumLength = (USHORT)(wcslen(opts->label->string) * sizeof(WCHAR));
1545         Label.Buffer = opts->label->string;
1546     } else {
1547         Label.Length = Label.MaximumLength = 0;
1548         Label.Buffer = NULL;
1549     }
1550
1551     Status = FormatEx2(&DriveRoot, FMIFS_HARDDISK, &Label, opts && opts->flags & FORMAT_FLAG_QUICK_FORMAT, 0, NULL);
1552
1553     return NT_SUCCESS(Status);
1554 }
1555
1556 #endif // __REACTOS__
1557
1558 void __stdcall SetSizes(ULONG sector, ULONG node) {
1559     if (sector != 0)
1560         def_sector_size = sector;
1561
1562     if (node != 0)
1563         def_node_size = node;
1564 }
1565
1566 void __stdcall SetIncompatFlags(uint64_t incompat_flags) {
1567     def_incompat_flags = incompat_flags;
1568 }
1569
1570 void __stdcall SetCsumType(uint16_t csum_type) {
1571     def_csum_type = csum_type;
1572 }
1573
1574 BOOL __stdcall GetFilesystemInformation(uint32_t unk1, uint32_t unk2, void* unk3) {
1575     // STUB - undocumented
1576
1577     return true;
1578 }
1579
1580 #ifndef __REACTOS__
1581 BOOL APIENTRY DllMain(HANDLE hModule, DWORD dwReason, void* lpReserved) {
1582     if (dwReason == DLL_PROCESS_ATTACH)
1583         module = (HMODULE)hModule;
1584
1585     return true;
1586 }
1587 #endif