reactos/dll/win32/ubtrfs/ubtrfs.c

   1 /* Copyright (c) Mark Harmstone 2016
   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 <ata.h>
  36 #include <mountmgr.h>
  37 #ifdef __REACTOS__
  38 #include "../../drivers/filesystems/btrfs/btrfs.h"
  39 #include "../../drivers/filesystems/btrfs/btrfsioctl.h"
  40 #else
  41 #include "../btrfs.h"
  42 #include "../btrfsioctl.h"
  43 #endif
  44
  45 #ifndef __REACTOS__
  46 #define FSCTL_LOCK_VOLUME               CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  6, METHOD_BUFFERED, FILE_ANY_ACCESS)
  47 #define FSCTL_UNLOCK_VOLUME             CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  7, METHOD_BUFFERED, FILE_ANY_ACCESS)
  48 #define FSCTL_DISMOUNT_VOLUME           CTL_CODE(FILE_DEVICE_FILE_SYSTEM,  8, METHOD_BUFFERED, FILE_ANY_ACCESS)
  49 #endif
  50
  51 #ifndef __REACTOS__
  52 #ifdef __cplusplus
  53 extern "C" {
  54 #endif
  55 NTSYSCALLAPI NTSTATUS NTAPI NtFsControlFile(HANDLE FileHandle, HANDLE Event, PIO_APC_ROUTINE ApcRoutine, PVOID ApcContext, PIO_STATUS_BLOCK IoStatusBlock, ULONG FsControlCode, PVOID InputBuffer, ULONG InputBufferLength, PVOID OutputBuffer, ULONG OutputBufferLength);
  56
  57 NTSTATUS NTAPI NtWriteFile(HANDLE FileHandle, HANDLE Event, PIO_APC_ROUTINE ApcRoutine, PVOID ApcContext, PIO_STATUS_BLOCK IoStatusBlock, PVOID Buffer,
  58                            ULONG Length, PLARGE_INTEGER ByteOffset, PULONG Key);
  59
  60 NTSTATUS NTAPI NtReadFile(HANDLE FileHandle, HANDLE Event, PIO_APC_ROUTINE ApcRoutine, PVOID ApcContext, PIO_STATUS_BLOCK IoStatusBlock, PVOID Buffer,
  61                           ULONG Length, PLARGE_INTEGER ByteOffset, PULONG Key);
  62
  63 NTSYSAPI NTSTATUS NTAPI RtlUnicodeToUTF8N(PCHAR UTF8StringDestination, ULONG UTF8StringMaxByteCount, PULONG UTF8StringActualByteCount,
  64                                           PCWCH UnicodeStringSource, ULONG  UnicodeStringByteCount);
  65 #ifdef __cplusplus
  66 }
  67 #endif
  68
  69 FORCEINLINE VOID InitializeListHead(PLIST_ENTRY ListHead) {
  70     ListHead->Flink = ListHead->Blink = ListHead;
  71 }
  72
  73 FORCEINLINE VOID InsertTailList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry) {
  74     PLIST_ENTRY Blink;
  75
  76     Blink = ListHead->Blink;
  77     Entry->Flink = ListHead;
  78     Entry->Blink = Blink;
  79     Blink->Flink = Entry;
  80     ListHead->Blink = Entry;
  81 }
  82 #endif
  83
  84 #if defined(__REACTOS__) && (NTDDI_VERSION < NTDDI_WIN7)
  85 NTSTATUS WINAPI RtlUnicodeToUTF8N(CHAR *utf8_dest, ULONG utf8_bytes_max,
  86                                   ULONG *utf8_bytes_written,
  87                                   const WCHAR *uni_src, ULONG uni_bytes);
  88 #endif /* defined(__REACTOS__) && (NTDDI_VERSION < NTDDI_WIN7) */
  89
  90 #ifdef __REACTOS__
  91 ULONG WINAPI NtGetTickCount(VOID);
  92 #endif
  93
  94 typedef struct {
  95     KEY key;
  96     UINT16 size;
  97     void* data;
  98     LIST_ENTRY list_entry;
  99 } btrfs_item;
 100
 101 typedef struct {
 102     UINT64 offset;
 103     CHUNK_ITEM* chunk_item;
 104     UINT64 lastoff;
 105     UINT64 used;
 106     LIST_ENTRY list_entry;
 107 } btrfs_chunk;
 108
 109 typedef struct {
 110     UINT64 id;
 111     tree_header header;
 112     btrfs_chunk* c;
 113     LIST_ENTRY items;
 114     LIST_ENTRY list_entry;
 115 } btrfs_root;
 116
 117 typedef struct {
 118     DEV_ITEM dev_item;
 119     UINT64 last_alloc;
 120 } btrfs_dev;
 121
 122 #define keycmp(key1, key2)\
 123     ((key1.obj_id < key2.obj_id) ? -1 :\
 124     ((key1.obj_id > key2.obj_id) ? 1 :\
 125     ((key1.obj_type < key2.obj_type) ? -1 :\
 126     ((key1.obj_type > key2.obj_type) ? 1 :\
 127     ((key1.offset < key2.offset) ? -1 :\
 128     ((key1.offset > key2.offset) ? 1 :\
 129     0))))))
 130
 131 HMODULE module;
 132
 133 // the following definitions come from fmifs.h in ReactOS
 134
 135 typedef struct {
 136     ULONG Lines;
 137     PCHAR Output;
 138 } TEXTOUTPUT, *PTEXTOUTPUT;
 139
 140 typedef enum {
 141     FMIFS_UNKNOWN0,
 142     FMIFS_UNKNOWN1,
 143     FMIFS_UNKNOWN2,
 144     FMIFS_UNKNOWN3,
 145     FMIFS_UNKNOWN4,
 146     FMIFS_UNKNOWN5,
 147     FMIFS_UNKNOWN6,
 148     FMIFS_UNKNOWN7,
 149     FMIFS_FLOPPY,
 150     FMIFS_UNKNOWN9,
 151     FMIFS_UNKNOWN10,
 152     FMIFS_REMOVABLE,
 153     FMIFS_HARDDISK,
 154     FMIFS_UNKNOWN13,
 155     FMIFS_UNKNOWN14,
 156     FMIFS_UNKNOWN15,
 157     FMIFS_UNKNOWN16,
 158     FMIFS_UNKNOWN17,
 159     FMIFS_UNKNOWN18,
 160     FMIFS_UNKNOWN19,
 161     FMIFS_UNKNOWN20,
 162     FMIFS_UNKNOWN21,
 163     FMIFS_UNKNOWN22,
 164     FMIFS_UNKNOWN23,
 165 } FMIFS_MEDIA_FLAG;
 166
 167 typedef enum {
 168     PROGRESS,
 169     DONEWITHSTRUCTURE,
 170     UNKNOWN2,
 171     UNKNOWN3,
 172     UNKNOWN4,
 173     UNKNOWN5,
 174     INSUFFICIENTRIGHTS,
 175     FSNOTSUPPORTED,
 176     VOLUMEINUSE,
 177     UNKNOWN9,
 178     UNKNOWNA,
 179     DONE,
 180     UNKNOWNC,
 181     UNKNOWND,
 182     OUTPUT,
 183     STRUCTUREPROGRESS,
 184     CLUSTERSIZETOOSMALL,
 185 } CALLBACKCOMMAND;
 186
 187 typedef BOOLEAN (NTAPI* PFMIFSCALLBACK)(CALLBACKCOMMAND Command, ULONG SubAction, PVOID ActionInfo);
 188
 189 static const UINT32 crctable[] = {
 190     0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, 0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
 191     0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b, 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
 192     0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b, 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
 193     0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, 0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
 194     0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a, 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
 195     0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5, 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
 196     0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, 0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
 197     0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a, 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
 198     0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48, 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
 199     0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, 0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
 200     0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927, 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
 201     0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8, 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
 202     0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, 0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
 203     0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859, 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
 204     0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9, 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
 205     0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, 0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
 206     0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c, 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
 207     0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043, 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
 208     0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, 0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
 209     0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c, 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
 210     0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652, 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
 211     0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, 0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
 212     0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d, 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
 213     0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2, 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
 214     0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, 0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
 215     0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff, 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
 216     0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f, 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
 217     0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, 0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
 218     0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee, 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
 219     0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321, 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
 220     0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, 0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
 221     0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e, 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351,
 222 };
 223
 224 static UINT32 calc_crc32c(UINT32 seed, UINT8* msg, ULONG msglen) {
 225     UINT32 rem;
 226     ULONG i;
 227
 228     rem = seed;
 229
 230     for (i = 0; i < msglen; i++) {
 231         rem = crctable[(rem ^ msg[i]) & 0xff] ^ (rem >> 8);
 232     }
 233
 234     return rem;
 235 }
 236
 237 NTSTATUS WINAPI ChkdskEx(PUNICODE_STRING DriveRoot, BOOLEAN FixErrors, BOOLEAN Verbose, BOOLEAN CheckOnlyIfDirty,
 238                          BOOLEAN ScanDrive, PFMIFSCALLBACK Callback) {
 239     // STUB
 240
 241     if (Callback) {
 242         TEXTOUTPUT TextOut;
 243
 244         TextOut.Lines = 1;
 245         TextOut.Output = "stub, not implemented";
 246
 247         Callback(OUTPUT, 0, &TextOut);
 248     }
 249
 250     return STATUS_SUCCESS;
 251 }
 252
 253 static btrfs_root* add_root(LIST_ENTRY* roots, UINT64 id) {
 254     btrfs_root* root;
 255
 256 #ifdef __REACTOS__
 257     root = RtlAllocateHeap(RtlGetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(btrfs_root));
 258 #else
 259     root = malloc(sizeof(btrfs_root));
 260 #endif
 261
 262     root->id = id;
 263 #ifndef __REACTOS__
 264     RtlZeroMemory(&root->header, sizeof(tree_header));
 265 #endif
 266     InitializeListHead(&root->items);
 267     InsertTailList(roots, &root->list_entry);
 268
 269     return root;
 270 }
 271
 272 static void free_roots(LIST_ENTRY* roots) {
 273     LIST_ENTRY* le;
 274
 275     le = roots->Flink;
 276     while (le != roots) {
 277         LIST_ENTRY *le2 = le->Flink, *le3;
 278         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 279
 280         le3 = r->items.Flink;
 281         while (le3 != &r->items) {
 282             LIST_ENTRY* le4 = le3->Flink;
 283             btrfs_item* item = CONTAINING_RECORD(le3, btrfs_item, list_entry);
 284
 285             if (item->data)
 286 #ifdef __REACTOS__
 287                 RtlFreeHeap(RtlGetProcessHeap(), 0, item->data);
 288
 289             RtlFreeHeap(RtlGetProcessHeap(), 0, item);
 290 #else
 291                 free(item->data);
 292
 293             free(item);
 294 #endif
 295
 296             le3 = le4;
 297         }
 298
 299 #ifdef __REACTOS__
 300         RtlFreeHeap(RtlGetProcessHeap(), 0, r);
 301 #else
 302         free(r);
 303 #endif
 304
 305         le = le2;
 306     }
 307 }
 308
 309 static void free_chunks(LIST_ENTRY* chunks) {
 310     LIST_ENTRY* le;
 311
 312     le = chunks->Flink;
 313     while (le != chunks) {
 314         LIST_ENTRY *le2 = le->Flink;
 315         btrfs_chunk* c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
 316
 317 #ifndef __REACTOS__
 318         free(c->chunk_item);
 319         free(c);
 320 #else
 321         RtlFreeHeap(RtlGetProcessHeap(), 0, c->chunk_item);
 322         RtlFreeHeap(RtlGetProcessHeap(), 0, c);
 323 #endif
 324
 325         le = le2;
 326     }
 327 }
 328
 329 static void add_item(btrfs_root* r, UINT64 obj_id, UINT8 obj_type, UINT64 offset, void* data, UINT16 size) {
 330     LIST_ENTRY* le;
 331     btrfs_item* item;
 332
 333 #ifndef __REACTOS__
 334     item = malloc(sizeof(btrfs_item));
 335 #else
 336     item = RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(btrfs_item));
 337 #endif
 338
 339     item->key.obj_id = obj_id;
 340     item->key.obj_type = obj_type;
 341     item->key.offset = offset;
 342     item->size = size;
 343
 344     if (size == 0)
 345         item->data = NULL;
 346     else {
 347 #ifndef __REACTOS__
 348         item->data = malloc(size);
 349 #else
 350         item->data = RtlAllocateHeap(RtlGetProcessHeap(), 0, size);
 351 #endif
 352         memcpy(item->data, data, size);
 353     }
 354
 355     le = r->items.Flink;
 356     while (le != &r->items) {
 357         btrfs_item* i2 = CONTAINING_RECORD(le, btrfs_item, list_entry);
 358
 359         if (keycmp(item->key, i2->key) != 1) {
 360             InsertTailList(le, &item->list_entry);
 361             return;
 362         }
 363
 364         le = le->Flink;
 365     }
 366
 367     InsertTailList(&r->items, &item->list_entry);
 368 }
 369
 370 static UINT64 find_chunk_offset(UINT64 size, UINT64 offset, btrfs_dev* dev, btrfs_root* dev_root, BTRFS_UUID* chunkuuid) {
 371     UINT64 off;
 372     DEV_EXTENT de;
 373
 374     off = dev->last_alloc;
 375     dev->last_alloc += size;
 376
 377     dev->dev_item.bytes_used += size;
 378
 379     de.chunktree = BTRFS_ROOT_CHUNK;
 380     de.objid = 0x100;
 381     de.address = offset;
 382     de.length = size;
 383     de.chunktree_uuid = *chunkuuid;
 384
 385     add_item(dev_root, dev->dev_item.dev_id, TYPE_DEV_EXTENT, off, &de, sizeof(DEV_EXTENT));
 386
 387     return off;
 388 }
 389
 390 static btrfs_chunk* add_chunk(LIST_ENTRY* chunks, UINT64 flags, btrfs_root* chunk_root, btrfs_dev* dev, btrfs_root* dev_root, BTRFS_UUID* chunkuuid, UINT32 sector_size) {
 391     UINT64 off, size;
 392     UINT16 stripes, i;
 393     btrfs_chunk* c;
 394     LIST_ENTRY* le;
 395     CHUNK_ITEM_STRIPE* cis;
 396
 397     off = 0xc00000;
 398     le = chunks->Flink;
 399     while (le != chunks) {
 400         c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
 401
 402         if (c->offset + c->chunk_item->size > off)
 403             off = c->offset + c->chunk_item->size;
 404
 405         le = le->Flink;
 406     }
 407
 408     if (flags & BLOCK_FLAG_METADATA) {
 409         if (dev->dev_item.num_bytes > 0xC80000000) // 50 GB
 410             size = 0x40000000; // 1 GB
 411         else
 412             size = 0x10000000; // 256 MB
 413     } else if (flags & BLOCK_FLAG_SYSTEM)
 414         size = 0x800000;
 415
 416     size = min(size, dev->dev_item.num_bytes / 10); // cap at 10%
 417     size &= ~(sector_size - 1);
 418
 419     stripes = flags & BLOCK_FLAG_DUPLICATE ? 2 : 1;
 420
 421     if (dev->dev_item.num_bytes - dev->dev_item.bytes_used < stripes * size) // not enough space
 422         return NULL;
 423
 424 #ifndef __REACTOS__
 425     c = malloc(sizeof(btrfs_chunk));
 426 #else
 427     c = RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(btrfs_chunk));
 428 #endif
 429     c->offset = off;
 430     c->lastoff = off;
 431     c->used = 0;
 432
 433 #ifndef __REACTOS__
 434     c->chunk_item = malloc(sizeof(CHUNK_ITEM) + (stripes * sizeof(CHUNK_ITEM_STRIPE)));
 435 #else
 436     c->chunk_item = RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(CHUNK_ITEM) + (stripes * sizeof(CHUNK_ITEM_STRIPE)));
 437 #endif
 438
 439     c->chunk_item->size = size;
 440     c->chunk_item->root_id = BTRFS_ROOT_EXTENT;
 441     c->chunk_item->stripe_length = 0x10000;
 442     c->chunk_item->type = flags;
 443     c->chunk_item->opt_io_alignment = 0x10000;
 444     c->chunk_item->opt_io_width = 0x10000;
 445     c->chunk_item->sector_size = sector_size;
 446     c->chunk_item->num_stripes = stripes;
 447     c->chunk_item->sub_stripes = 0;
 448
 449     cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 450
 451     for (i = 0; i < stripes; i++) {
 452         cis[i].dev_id = dev->dev_item.dev_id;
 453         cis[i].offset = find_chunk_offset(size, c->offset, dev, dev_root, chunkuuid);
 454         cis[i].dev_uuid = dev->dev_item.device_uuid;
 455     }
 456
 457     add_item(chunk_root, 0x100, TYPE_CHUNK_ITEM, c->offset, c->chunk_item, sizeof(CHUNK_ITEM) + (stripes * sizeof(CHUNK_ITEM_STRIPE)));
 458
 459     InsertTailList(chunks, &c->list_entry);
 460
 461     return c;
 462 }
 463
 464 static BOOL superblock_collision(btrfs_chunk* c, UINT64 address) {
 465     CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 466     UINT64 stripe = (address - c->offset) / c->chunk_item->stripe_length;
 467     UINT16 i, j;
 468
 469     for (i = 0; i < c->chunk_item->num_stripes; i++) {
 470         j = 0;
 471         while (superblock_addrs[j] != 0) {
 472             if (superblock_addrs[j] >= cis[i].offset) {
 473                 UINT64 stripe2 = (superblock_addrs[j] - cis[i].offset) / c->chunk_item->stripe_length;
 474
 475                 if (stripe2 == stripe)
 476                     return TRUE;
 477             }
 478             j++;
 479         }
 480     }
 481
 482     return FALSE;
 483 }
 484
 485 static UINT64 get_next_address(btrfs_chunk* c) {
 486     UINT64 addr;
 487
 488     addr = c->lastoff;
 489
 490     while (superblock_collision(c, addr)) {
 491         addr = addr - ((addr - c->offset) % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
 492
 493         if (addr >= c->offset + c->chunk_item->size) // chunk has been exhausted
 494             return 0;
 495     }
 496
 497     return addr;
 498 }
 499
 500 typedef struct {
 501     EXTENT_ITEM ei;
 502     UINT8 type;
 503     TREE_BLOCK_REF tbr;
 504 } EXTENT_ITEM_METADATA;
 505
 506 static void assign_addresses(LIST_ENTRY* roots, btrfs_chunk* sys_chunk, btrfs_chunk* metadata_chunk, UINT32 node_size,
 507                              btrfs_root* root_root, btrfs_root* extent_root) {
 508     LIST_ENTRY* le;
 509
 510     le = roots->Flink;
 511     while (le != roots) {
 512         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 513         btrfs_chunk* c = r->id == BTRFS_ROOT_CHUNK ? sys_chunk : metadata_chunk;
 514         EXTENT_ITEM_METADATA eim;
 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         eim.ei.refcount = 1;
 522         eim.ei.generation = 1;
 523         eim.ei.flags = EXTENT_ITEM_TREE_BLOCK;
 524         eim.type = TYPE_TREE_BLOCK_REF;
 525         eim.tbr.offset = r->id;
 526
 527         // FIXME - support non-skinny EXTENT_ITEM
 528         add_item(extent_root, r->header.address, TYPE_METADATA_ITEM, 0, &eim, sizeof(EXTENT_ITEM_METADATA));
 529
 530         if (r->id != BTRFS_ROOT_ROOT && r->id != BTRFS_ROOT_CHUNK) {
 531             ROOT_ITEM ri;
 532
 533             memset(&ri, 0, sizeof(ROOT_ITEM));
 534
 535             ri.inode.generation = 1;
 536             ri.inode.st_size = 3;
 537             ri.inode.st_blocks = node_size;
 538             ri.inode.st_nlink = 1;
 539             ri.inode.st_mode = 040755;
 540             ri.generation = 1;
 541             ri.objid = r->id == 5 || r->id >= 0x100 ? SUBVOL_ROOT_INODE : 0;
 542             ri.block_number = r->header.address;
 543             ri.bytes_used = node_size;
 544             ri.num_references = 1;
 545             ri.generation2 = ri.generation;
 546
 547             add_item(root_root, r->id, TYPE_ROOT_ITEM, 0, &ri, sizeof(ROOT_ITEM));
 548         }
 549
 550         le = le->Flink;
 551     }
 552 }
 553
 554 static NTSTATUS write_data(HANDLE h, UINT64 address, btrfs_chunk* c, void* data, ULONG size) {
 555     NTSTATUS Status;
 556     UINT16 i;
 557     IO_STATUS_BLOCK iosb;
 558     LARGE_INTEGER off;
 559     CHUNK_ITEM_STRIPE* cis;
 560
 561     cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 562
 563     for (i = 0; i < c->chunk_item->num_stripes; i++) {
 564         off.QuadPart = cis[i].offset + address - c->offset;
 565
 566         Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, data, size, &off, NULL);
 567         if (!NT_SUCCESS(Status))
 568             return Status;
 569     }
 570
 571     return STATUS_SUCCESS;
 572 }
 573
 574 static NTSTATUS write_roots(HANDLE h, LIST_ENTRY* roots, UINT32 node_size, BTRFS_UUID* fsuuid, BTRFS_UUID* chunkuuid) {
 575     LIST_ENTRY *le, *le2;
 576     NTSTATUS Status;
 577     UINT8* tree;
 578
 579 #ifndef __REACTOS__
 580     tree = malloc(node_size);
 581 #else
 582     tree = RtlAllocateHeap(RtlGetProcessHeap(), 0, node_size);
 583 #endif
 584
 585     le = roots->Flink;
 586     while (le != roots) {
 587         btrfs_root* r = CONTAINING_RECORD(le, btrfs_root, list_entry);
 588         UINT8* dp;
 589         leaf_node* ln;
 590         UINT32 crc32;
 591
 592         memset(tree, 0, node_size);
 593
 594         r->header.num_items = 0;
 595         r->header.fs_uuid = *fsuuid;
 596         r->header.flags = HEADER_FLAG_MIXED_BACKREF | HEADER_FLAG_WRITTEN;
 597         r->header.chunk_tree_uuid = *chunkuuid;
 598         r->header.generation = 1;
 599         r->header.tree_id = r->id;
 600
 601         ln = (leaf_node*)(tree + sizeof(tree_header));
 602
 603         dp = tree + node_size;
 604
 605         le2 = r->items.Flink;
 606         while (le2 != &r->items) {
 607             btrfs_item* item = CONTAINING_RECORD(le2, btrfs_item, list_entry);
 608
 609             ln->key = item->key;
 610             ln->size = item->size;
 611
 612             if (item->size > 0) {
 613                 dp -= item->size;
 614                 memcpy(dp, item->data, item->size);
 615
 616                 ln->offset = dp - tree - sizeof(tree_header);
 617             } else
 618                 ln->offset = 0;
 619
 620             ln = &ln[1];
 621
 622             r->header.num_items++;
 623
 624             le2 = le2->Flink;
 625         }
 626
 627         memcpy(tree, &r->header, sizeof(tree_header));
 628
 629         crc32 = ~calc_crc32c(0xffffffff, (UINT8*)&((tree_header*)tree)->fs_uuid, node_size - sizeof(((tree_header*)tree)->csum));
 630         memcpy(tree, &crc32, sizeof(UINT32));
 631
 632         Status = write_data(h, r->header.address, r->c, tree, node_size);
 633         if (!NT_SUCCESS(Status)) {
 634 #ifndef __REACTOS__
 635             free(tree);
 636 #else
 637             RtlFreeHeap(RtlGetProcessHeap(), 0, tree);
 638 #endif
 639             return Status;
 640         }
 641
 642         le = le->Flink;
 643     }
 644
 645 #ifndef __REACTOS__
 646     free(tree);
 647 #else
 648     RtlFreeHeap(RtlGetProcessHeap(), 0, tree);
 649 #endif
 650
 651     return STATUS_SUCCESS;
 652 }
 653
 654 #ifndef __REACTOS__
 655 static void get_uuid(BTRFS_UUID* uuid) {
 656 #else
 657 static void get_uuid(BTRFS_UUID* uuid, ULONG* seed) {
 658 #endif
 659     UINT8 i;
 660
 661     for (i = 0; i < 16; i+=2) {
 662 #ifndef __REACTOS__
 663         ULONG r = rand();
 664 #else
 665         ULONG r = RtlRandom(seed);
 666 #endif
 667
 668         uuid->uuid[i] = (r & 0xff00) >> 8;
 669         uuid->uuid[i+1] = r & 0xff;
 670     }
 671 }
 672
 673 #ifndef __REACTOS__
 674 static void init_device(btrfs_dev* dev, UINT64 id, UINT64 size, BTRFS_UUID* fsuuid, UINT32 sector_size) {
 675 #else
 676 static void init_device(btrfs_dev* dev, UINT64 id, UINT64 size, BTRFS_UUID* fsuuid, UINT32 sector_size, ULONG* seed) {
 677 #endif
 678     dev->dev_item.dev_id = id;
 679     dev->dev_item.num_bytes = size;
 680     dev->dev_item.bytes_used = 0;
 681     dev->dev_item.optimal_io_align = sector_size;
 682     dev->dev_item.optimal_io_width = sector_size;
 683     dev->dev_item.minimal_io_size = sector_size;
 684     dev->dev_item.type = 0;
 685     dev->dev_item.generation = 0;
 686     dev->dev_item.start_offset = 0;
 687     dev->dev_item.dev_group = 0;
 688     dev->dev_item.seek_speed = 0;
 689     dev->dev_item.bandwidth = 0;
 690 #ifndef __REACTOS__
 691     get_uuid(&dev->dev_item.device_uuid);
 692 #else
 693     get_uuid(&dev->dev_item.device_uuid, seed);
 694 #endif
 695     dev->dev_item.fs_uuid = *fsuuid;
 696
 697     dev->last_alloc = 0x100000; // skip first megabyte
 698 }
 699
 700 #ifdef __REACTOS__
 701 NTSTATUS NTAPI RtlUnicodeToUTF8N(CHAR *utf8_dest, ULONG utf8_bytes_max,
 702                                  ULONG *utf8_bytes_written,
 703                                  const WCHAR *uni_src, ULONG uni_bytes)
 704 {
 705     NTSTATUS status;
 706     ULONG i;
 707     ULONG written;
 708     ULONG ch;
 709     BYTE utf8_ch[4];
 710     ULONG utf8_ch_len;
 711
 712     if (!uni_src)
 713         return STATUS_INVALID_PARAMETER_4;
 714     if (!utf8_bytes_written)
 715         return STATUS_INVALID_PARAMETER;
 716     if (utf8_dest && uni_bytes % sizeof(WCHAR))
 717         return STATUS_INVALID_PARAMETER_5;
 718
 719     written = 0;
 720     status = STATUS_SUCCESS;
 721
 722     for (i = 0; i < uni_bytes / sizeof(WCHAR); i++)
 723     {
 724         /* decode UTF-16 into ch */
 725         ch = uni_src[i];
 726         if (ch >= 0xdc00 && ch <= 0xdfff)
 727         {
 728             ch = 0xfffd;
 729             status = STATUS_SOME_NOT_MAPPED;
 730         }
 731         else if (ch >= 0xd800 && ch <= 0xdbff)
 732         {
 733             if (i + 1 < uni_bytes / sizeof(WCHAR))
 734             {
 735                 ch -= 0xd800;
 736                 ch <<= 10;
 737                 if (uni_src[i + 1] >= 0xdc00 && uni_src[i + 1] <= 0xdfff)
 738                 {
 739                     ch |= uni_src[i + 1] - 0xdc00;
 740                     ch += 0x010000;
 741                     i++;
 742                 }
 743                 else
 744                 {
 745                     ch = 0xfffd;
 746                     status = STATUS_SOME_NOT_MAPPED;
 747                 }
 748             }
 749             else
 750             {
 751                 ch = 0xfffd;
 752                 status = STATUS_SOME_NOT_MAPPED;
 753             }
 754         }
 755
 756         /* encode ch as UTF-8 */
 757         ASSERT(ch <= 0x10ffff);
 758         if (ch < 0x80)
 759         {
 760             utf8_ch[0] = ch & 0x7f;
 761             utf8_ch_len = 1;
 762         }
 763         else if (ch < 0x800)
 764         {
 765             utf8_ch[0] = 0xc0 | (ch >>  6 & 0x1f);
 766             utf8_ch[1] = 0x80 | (ch >>  0 & 0x3f);
 767             utf8_ch_len = 2;
 768         }
 769         else if (ch < 0x10000)
 770         {
 771             utf8_ch[0] = 0xe0 | (ch >> 12 & 0x0f);
 772             utf8_ch[1] = 0x80 | (ch >>  6 & 0x3f);
 773             utf8_ch[2] = 0x80 | (ch >>  0 & 0x3f);
 774             utf8_ch_len = 3;
 775         }
 776         else if (ch < 0x200000)
 777         {
 778             utf8_ch[0] = 0xf0 | (ch >> 18 & 0x07);
 779             utf8_ch[1] = 0x80 | (ch >> 12 & 0x3f);
 780             utf8_ch[2] = 0x80 | (ch >>  6 & 0x3f);
 781             utf8_ch[3] = 0x80 | (ch >>  0 & 0x3f);
 782             utf8_ch_len = 4;
 783         }
 784
 785         if (!utf8_dest)
 786         {
 787             written += utf8_ch_len;
 788             continue;
 789         }
 790
 791         if (utf8_bytes_max >= utf8_ch_len)
 792         {
 793             memcpy(utf8_dest, utf8_ch, utf8_ch_len);
 794             utf8_dest += utf8_ch_len;
 795             utf8_bytes_max -= utf8_ch_len;
 796             written += utf8_ch_len;
 797         }
 798         else
 799         {
 800             utf8_bytes_max = 0;
 801             status = STATUS_BUFFER_TOO_SMALL;
 802         }
 803     }
 804
 805     *utf8_bytes_written = written;
 806     return status;
 807 }
 808 #endif
 809
 810 static NTSTATUS write_superblocks(HANDLE h, btrfs_dev* dev, btrfs_root* chunk_root, btrfs_root* root_root, btrfs_root* extent_root,
 811                                   btrfs_chunk* sys_chunk, UINT32 node_size, BTRFS_UUID* fsuuid, UINT32 sector_size, PUNICODE_STRING label) {
 812     NTSTATUS Status;
 813     IO_STATUS_BLOCK iosb;
 814     ULONG sblen;
 815     int i;
 816     UINT32 crc32;
 817     superblock* sb;
 818     KEY* key;
 819     UINT64 bytes_used;
 820     LIST_ENTRY* le;
 821
 822     sblen = sizeof(sb);
 823     if (sblen & (sector_size - 1))
 824         sblen = (sblen & sector_size) + sector_size;
 825
 826     bytes_used = 0;
 827
 828     le = extent_root->items.Flink;
 829     while (le != &extent_root->items) {
 830         btrfs_item* item = CONTAINING_RECORD(le, btrfs_item, list_entry);
 831
 832         if (item->key.obj_type == TYPE_EXTENT_ITEM)
 833             bytes_used += item->key.offset;
 834         else if (item->key.obj_type == TYPE_METADATA_ITEM)
 835             bytes_used += node_size;
 836
 837         le = le->Flink;
 838     }
 839
 840 #ifndef __REACTOS__
 841     sb = malloc(sblen);
 842     memset(sb, 0, sblen);
 843 #else
 844     sb = RtlAllocateHeap(RtlGetProcessHeap(), HEAP_ZERO_MEMORY, sblen);
 845 #endif
 846
 847     sb->uuid = *fsuuid;
 848     sb->flags = 1;
 849     sb->magic = BTRFS_MAGIC;
 850     sb->generation = 1;
 851     sb->root_tree_addr = root_root->header.address;
 852     sb->chunk_tree_addr = chunk_root->header.address;
 853     sb->total_bytes = dev->dev_item.num_bytes;
 854     sb->bytes_used = bytes_used;
 855     sb->root_dir_objectid = 6;
 856     sb->num_devices = 1;
 857     sb->sector_size = sector_size;
 858     sb->node_size = node_size;
 859     sb->leaf_size = node_size;
 860     sb->stripe_size = sector_size;
 861     sb->n = sizeof(KEY) + sizeof(CHUNK_ITEM) + (sys_chunk->chunk_item->num_stripes * sizeof(CHUNK_ITEM_STRIPE));
 862     sb->chunk_root_generation = 1;
 863     sb->incompat_flags = BTRFS_INCOMPAT_FLAGS_MIXED_BACKREF | BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF | BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA;
 864     memcpy(&sb->dev_item, &dev->dev_item, sizeof(DEV_ITEM));
 865
 866     if (label->Length > 0) {
 867         int i;
 868         ULONG utf8len;
 869
 870         for (i = 0; i < label->Length / sizeof(WCHAR); i++) {
 871             if (label->Buffer[i] == '/' || label->Buffer[i] == '\\') {
 872 #ifndef __REACTOS__
 873                 free(sb);
 874 #else
 875                 RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 876 #endif
 877                 return STATUS_INVALID_VOLUME_LABEL;
 878             }
 879         }
 880
 881         Status = RtlUnicodeToUTF8N(NULL, 0, &utf8len, label->Buffer, label->Length);
 882         if (!NT_SUCCESS(Status)) {
 883 #ifndef __REACTOS__
 884             free(sb);
 885 #else
 886             RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 887 #endif
 888             return Status;
 889         }
 890
 891         if (utf8len > MAX_LABEL_SIZE) {
 892 #ifndef __REACTOS__
 893             free(sb);
 894 #else
 895             RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 896 #endif
 897             return STATUS_INVALID_VOLUME_LABEL;
 898         }
 899
 900         Status = RtlUnicodeToUTF8N((PCHAR)&sb->label, MAX_LABEL_SIZE, &utf8len, label->Buffer, label->Length);
 901         if (!NT_SUCCESS(Status)) {
 902 #ifndef __REACTOS__
 903             free(sb);
 904 #else
 905             RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 906 #endif
 907             return Status;
 908         }
 909     }
 910     sb->cache_generation = 0xffffffffffffffff;
 911
 912     key = (KEY*)sb->sys_chunk_array;
 913     key->obj_id = 0x100;
 914     key->obj_type = TYPE_CHUNK_ITEM;
 915     key->offset = sys_chunk->offset;
 916     memcpy(&key[1], sys_chunk->chunk_item, sizeof(CHUNK_ITEM) + (sys_chunk->chunk_item->num_stripes * sizeof(CHUNK_ITEM_STRIPE)));
 917
 918     i = 0;
 919     while (superblock_addrs[i] != 0) {
 920         LARGE_INTEGER off;
 921
 922         if (superblock_addrs[i] > dev->dev_item.num_bytes)
 923             break;
 924
 925         sb->sb_phys_addr = superblock_addrs[i];
 926
 927         crc32 = ~calc_crc32c(0xffffffff, (UINT8*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
 928         memcpy(&sb->checksum, &crc32, sizeof(UINT32));
 929
 930         off.QuadPart = superblock_addrs[i];
 931
 932         Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, sb, sblen, &off, NULL);
 933         if (!NT_SUCCESS(Status)) {
 934 #ifndef __REACTOS__
 935             free(sb);
 936 #else
 937             RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 938 #endif
 939             return Status;
 940         }
 941
 942         i++;
 943     }
 944
 945 #ifndef __REACTOS__
 946     free(sb);
 947 #else
 948     RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
 949 #endif
 950
 951     return STATUS_SUCCESS;
 952 }
 953
 954 static __inline void win_time_to_unix(LARGE_INTEGER t, BTRFS_TIME* out) {
 955     ULONGLONG l = t.QuadPart - 116444736000000000;
 956
 957     out->seconds = l / 10000000;
 958     out->nanoseconds = (l % 10000000) * 100;
 959 }
 960
 961 #ifdef __REACTOS__
 962 VOID
 963 WINAPI
 964 GetSystemTimeAsFileTime(OUT PFILETIME lpFileTime)
 965 {
 966     LARGE_INTEGER SystemTime;
 967
 968     do
 969     {
 970         SystemTime.HighPart = SharedUserData->SystemTime.High1Time;
 971         SystemTime.LowPart = SharedUserData->SystemTime.LowPart;
 972     }
 973     while (SystemTime.HighPart != SharedUserData->SystemTime.High2Time);
 974
 975     lpFileTime->dwLowDateTime = SystemTime.LowPart;
 976     lpFileTime->dwHighDateTime = SystemTime.HighPart;
 977 }
 978 #endif
 979
 980 static void init_fs_tree(btrfs_root* r, UINT32 node_size) {
 981     INODE_ITEM ii;
 982     INODE_REF* ir;
 983 #ifndef __REACTOS__
 984     SYSTEMTIME systime;
 985 #endif
 986     FILETIME filetime;
 987     LARGE_INTEGER time;
 988
 989     memset(&ii, 0, sizeof(INODE_ITEM));
 990
 991     ii.generation = 1;
 992     ii.st_blocks = node_size;
 993     ii.st_nlink = 1;
 994     ii.st_mode = 040755;
 995
 996 #ifndef __REACTOS__
 997     GetSystemTime(&systime);
 998     SystemTimeToFileTime(&systime, &filetime);
 999 #else
1000     GetSystemTimeAsFileTime(&filetime);
1001 #endif
1002     time.LowPart = filetime.dwLowDateTime;
1003     time.HighPart = filetime.dwHighDateTime;
1004
1005     win_time_to_unix(time, &ii.st_atime);
1006     ii.st_ctime = ii.st_mtime = ii.st_atime;
1007
1008     add_item(r, SUBVOL_ROOT_INODE, TYPE_INODE_ITEM, 0, &ii, sizeof(INODE_ITEM));
1009
1010 #ifndef __REACTOS__
1011     ir = malloc(sizeof(INODE_REF) - 1 + 2);
1012 #else
1013     ir = RtlAllocateHeap(RtlGetProcessHeap(), 0, sizeof(INODE_REF) - 1 + 2);
1014 #endif
1015
1016     ir->index = 0;
1017     ir->n = 2;
1018     ir->name[0] = '.';
1019     ir->name[1] = '.';
1020
1021     add_item(r, SUBVOL_ROOT_INODE, TYPE_INODE_REF, SUBVOL_ROOT_INODE, ir, sizeof(INODE_REF) - 1 + ir->n);
1022
1023 #ifndef __REACTOS__
1024     free(ir);
1025 #else
1026     RtlFreeHeap(RtlGetProcessHeap(), 0, ir);
1027 #endif
1028 }
1029
1030 static void add_block_group_items(LIST_ENTRY* chunks, btrfs_root* extent_root) {
1031     LIST_ENTRY* le;
1032
1033     le = chunks->Flink;
1034     while (le != chunks) {
1035         btrfs_chunk* c = CONTAINING_RECORD(le, btrfs_chunk, list_entry);
1036         BLOCK_GROUP_ITEM bgi;
1037
1038         bgi.used = c->used;
1039         bgi.chunk_tree = 0x100;
1040         bgi.flags = c->chunk_item->type;
1041         add_item(extent_root, c->offset, TYPE_BLOCK_GROUP_ITEM, c->chunk_item->size, &bgi, sizeof(BLOCK_GROUP_ITEM));
1042
1043         le = le->Flink;
1044     }
1045 }
1046
1047 static NTSTATUS clear_first_megabyte(HANDLE h) {
1048     NTSTATUS Status;
1049     IO_STATUS_BLOCK iosb;
1050     LARGE_INTEGER zero;
1051     UINT8* mb;
1052
1053 #ifndef __REACTOS__
1054     mb = malloc(0x100000);
1055 #else
1056     mb = RtlAllocateHeap(RtlGetProcessHeap(), 0, 0x100000);
1057 #endif
1058     memset(mb, 0, 0x100000);
1059
1060     zero.QuadPart = 0;
1061
1062     Status = NtWriteFile(h, NULL, NULL, NULL, &iosb, mb, 0x100000, &zero, NULL);
1063
1064 #ifndef __REACTOS__
1065     free(mb);
1066 #else
1067     RtlFreeHeap(RtlGetProcessHeap(), 0, mb);
1068 #endif
1069
1070     return Status;
1071 }
1072
1073 static BOOL is_ssd(HANDLE h) {
1074     ULONG aptelen;
1075     ATA_PASS_THROUGH_EX* apte;
1076     IO_STATUS_BLOCK iosb;
1077     NTSTATUS Status;
1078     IDENTIFY_DEVICE_DATA* idd;
1079
1080     aptelen = sizeof(ATA_PASS_THROUGH_EX) + 512;
1081 #ifndef __REACTOS__
1082     apte = malloc(aptelen);
1083
1084     RtlZeroMemory(apte, aptelen);
1085 #else
1086     apte = RtlAllocateHeap(RtlGetProcessHeap(), HEAP_ZERO_MEMORY, aptelen);
1087 #endif
1088
1089     apte->Length = sizeof(ATA_PASS_THROUGH_EX);
1090     apte->AtaFlags = ATA_FLAGS_DATA_IN;
1091     apte->DataTransferLength = aptelen - sizeof(ATA_PASS_THROUGH_EX);
1092     apte->TimeOutValue = 3;
1093     apte->DataBufferOffset = apte->Length;
1094     apte->CurrentTaskFile[6] = IDE_COMMAND_IDENTIFY;
1095
1096     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_ATA_PASS_THROUGH, apte, aptelen, apte, aptelen);
1097
1098     if (NT_SUCCESS(Status)) {
1099         idd = (IDENTIFY_DEVICE_DATA*)((UINT8*)apte + sizeof(ATA_PASS_THROUGH_EX));
1100
1101         if (idd->NominalMediaRotationRate == 1)
1102             return TRUE;
1103     }
1104
1105     return FALSE;
1106 }
1107
1108 static NTSTATUS write_btrfs(HANDLE h, UINT64 size, PUNICODE_STRING label, UINT32 sector_size) {
1109     NTSTATUS Status;
1110     UINT32 node_size;
1111     LIST_ENTRY roots, chunks;
1112     btrfs_root *root_root, *chunk_root, *extent_root, *dev_root, *fs_root, *reloc_root;
1113     btrfs_chunk *sys_chunk, *metadata_chunk;
1114     btrfs_dev dev;
1115     BTRFS_UUID fsuuid, chunkuuid;
1116     BOOL ssd;
1117 #ifdef __REACTOS__
1118     ULONG seed;
1119 #endif
1120
1121 #ifndef __REACTOS__
1122     srand(time(0));
1123     get_uuid(&fsuuid);
1124     get_uuid(&chunkuuid);
1125 #else
1126     seed = NtGetTickCount();
1127     get_uuid(&fsuuid, &seed);
1128     get_uuid(&chunkuuid, &seed);
1129 #endif
1130
1131     InitializeListHead(&roots);
1132     InitializeListHead(&chunks);
1133
1134     root_root = add_root(&roots, BTRFS_ROOT_ROOT);
1135     chunk_root = add_root(&roots, BTRFS_ROOT_CHUNK);
1136     extent_root = add_root(&roots, BTRFS_ROOT_EXTENT);
1137     dev_root = add_root(&roots, BTRFS_ROOT_DEVTREE);
1138     add_root(&roots, BTRFS_ROOT_CHECKSUM);
1139     fs_root = add_root(&roots, BTRFS_ROOT_FSTREE);
1140     reloc_root = add_root(&roots, BTRFS_ROOT_DATA_RELOC);
1141
1142 #ifndef __REACTOS__
1143     init_device(&dev, 1, size, &fsuuid, sector_size);
1144 #else
1145     init_device(&dev, 1, size, &fsuuid, sector_size, &seed);
1146 #endif
1147
1148     ssd = is_ssd(h);
1149
1150     sys_chunk = add_chunk(&chunks, BLOCK_FLAG_SYSTEM | (ssd ? 0 : BLOCK_FLAG_DUPLICATE), chunk_root, &dev, dev_root, &chunkuuid, sector_size);
1151     if (!sys_chunk)
1152         return STATUS_INTERNAL_ERROR;
1153
1154     metadata_chunk = add_chunk(&chunks, BLOCK_FLAG_METADATA | (ssd ? 0 : BLOCK_FLAG_DUPLICATE), chunk_root, &dev, dev_root, &chunkuuid, sector_size);
1155     if (!metadata_chunk)
1156         return STATUS_INTERNAL_ERROR;
1157
1158     node_size = 0x4000;
1159     assign_addresses(&roots, sys_chunk, metadata_chunk, node_size, root_root, extent_root);
1160
1161     add_item(chunk_root, 1, TYPE_DEV_ITEM, dev.dev_item.dev_id, &dev.dev_item, sizeof(DEV_ITEM));
1162
1163     init_fs_tree(fs_root, node_size);
1164     init_fs_tree(reloc_root, node_size);
1165
1166     add_block_group_items(&chunks, extent_root);
1167
1168     Status = write_roots(h, &roots, node_size, &fsuuid, &chunkuuid);
1169     if (!NT_SUCCESS(Status))
1170         return Status;
1171
1172     Status = clear_first_megabyte(h);
1173     if (!NT_SUCCESS(Status))
1174         return Status;
1175
1176     Status = write_superblocks(h, &dev, chunk_root, root_root, extent_root, sys_chunk, node_size, &fsuuid, sector_size, label);
1177     if (!NT_SUCCESS(Status))
1178         return Status;
1179
1180     free_roots(&roots);
1181     free_chunks(&chunks);
1182
1183     return STATUS_SUCCESS;
1184 }
1185
1186 static BOOL look_for_device(btrfs_filesystem* bfs, BTRFS_UUID* devuuid) {
1187     UINT32 i;
1188     btrfs_filesystem_device* dev;
1189
1190     for (i = 0; i < bfs->num_devices; i++) {
1191         if (i == 0)
1192             dev = &bfs->device;
1193         else
1194             dev = (btrfs_filesystem_device*)((UINT8*)dev + offsetof(btrfs_filesystem_device, name[0]) + dev->name_length);
1195
1196         if (RtlCompareMemory(&dev->uuid, devuuid, sizeof(BTRFS_UUID)) == sizeof(BTRFS_UUID))
1197             return TRUE;
1198     }
1199
1200     return FALSE;
1201 }
1202
1203 static BOOL is_mounted_multi_device(HANDLE h, UINT32 sector_size) {
1204     NTSTATUS Status;
1205     superblock* sb;
1206     ULONG sblen;
1207     IO_STATUS_BLOCK iosb;
1208     LARGE_INTEGER off;
1209     BTRFS_UUID fsuuid, devuuid;
1210     UINT32 crc32;
1211     UNICODE_STRING us;
1212     OBJECT_ATTRIBUTES atts;
1213     HANDLE h2;
1214     btrfs_filesystem *bfs = NULL, *bfs2;
1215     ULONG bfssize;
1216     BOOL ret = FALSE;
1217
1218     static WCHAR btrfs[] = L"\\Btrfs";
1219
1220     sblen = sizeof(sb);
1221     if (sblen & (sector_size - 1))
1222         sblen = (sblen & sector_size) + sector_size;
1223
1224 #ifndef __REACTOS__
1225     sb = malloc(sblen);
1226 #else
1227     sb = RtlAllocateHeap(RtlGetProcessHeap(), 0, sblen);
1228 #endif
1229
1230     off.QuadPart = superblock_addrs[0];
1231
1232     Status = NtReadFile(h, NULL, NULL, NULL, &iosb, sb, sblen, &off, NULL);
1233     if (!NT_SUCCESS(Status)) {
1234 #ifndef __REACTOS__
1235         free(sb);
1236 #else
1237         RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
1238 #endif
1239         return FALSE;
1240     }
1241
1242     if (sb->magic != BTRFS_MAGIC) {
1243 #ifndef __REACTOS__
1244         free(sb);
1245 #else
1246         RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
1247 #endif
1248         return FALSE;
1249     }
1250
1251     crc32 = ~calc_crc32c(0xffffffff, (UINT8*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
1252     if (crc32 != *((UINT32*)sb)) {
1253 #ifndef __REACTOS__
1254         free(sb);
1255 #else
1256         RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
1257 #endif
1258         return FALSE;
1259     }
1260
1261     fsuuid = sb->uuid;
1262     devuuid = sb->dev_item.device_uuid;
1263
1264 #ifndef __REACTOS__
1265     free(sb);
1266 #else
1267     RtlFreeHeap(RtlGetProcessHeap(), 0, sb);
1268 #endif
1269
1270     us.Length = us.MaximumLength = wcslen(btrfs) * sizeof(WCHAR);
1271     us.Buffer = btrfs;
1272
1273     InitializeObjectAttributes(&atts, &us, 0, NULL, NULL);
1274
1275     Status = NtOpenFile(&h2, SYNCHRONIZE | FILE_READ_ATTRIBUTES, &atts, &iosb,
1276                         FILE_SHARE_READ | FILE_SHARE_WRITE, FILE_SYNCHRONOUS_IO_ALERT);
1277     if (!NT_SUCCESS(Status)) // not a problem, it usually just means the driver isn't loaded
1278         return FALSE;
1279
1280     bfssize = 0;
1281
1282     do {
1283         bfssize += 1024;
1284
1285 #ifndef __REACTOS__
1286         if (bfs) free(bfs);
1287         bfs = malloc(bfssize);
1288 #else
1289         if (bfs) RtlFreeHeap(RtlGetProcessHeap(), 0, bfs);
1290         bfs = RtlAllocateHeap(RtlGetProcessHeap(), 0, bfssize);
1291 #endif
1292
1293         Status = NtDeviceIoControlFile(h2, NULL, NULL, NULL, &iosb, IOCTL_BTRFS_QUERY_FILESYSTEMS, NULL, 0, bfs, bfssize);
1294         if (!NT_SUCCESS(Status) && Status != STATUS_BUFFER_OVERFLOW) {
1295             NtClose(h2);
1296             return FALSE;
1297         }
1298     } while (Status == STATUS_BUFFER_OVERFLOW);
1299
1300     if (!NT_SUCCESS(Status))
1301         goto end;
1302
1303     if (bfs->num_devices != 0) {
1304         bfs2 = bfs;
1305         while (TRUE) {
1306             if (RtlCompareMemory(&bfs2->uuid, &fsuuid, sizeof(BTRFS_UUID)) == sizeof(BTRFS_UUID)) {
1307                 if (bfs2->num_devices == 1)
1308                     ret = FALSE;
1309                 else
1310                     ret = look_for_device(bfs2, &devuuid);
1311
1312                 goto end;
1313             }
1314
1315             if (bfs2->next_entry == 0)
1316                 break;
1317             else
1318                 bfs2 = (btrfs_filesystem*)((UINT8*)bfs2 + bfs2->next_entry);
1319         }
1320     }
1321
1322 end:
1323     NtClose(h2);
1324
1325     if (bfs)
1326 #ifndef __REACTOS__
1327         free(bfs);
1328 #else
1329         RtlFreeHeap(RtlGetProcessHeap(), 0, bfs);
1330 #endif
1331
1332     return ret;
1333 }
1334
1335 static void add_drive_letter(HANDLE h) {
1336     NTSTATUS Status;
1337     IO_STATUS_BLOCK iosb;
1338     MOUNTDEV_NAME mdn, *mdn2;
1339     UNICODE_STRING us;
1340     OBJECT_ATTRIBUTES attr;
1341     HANDLE mountmgr;
1342     MOUNTMGR_DRIVE_LETTER_INFORMATION mdli;
1343
1344     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_MOUNTDEV_QUERY_DEVICE_NAME, NULL, 0, &mdn, sizeof(mdn));
1345     if (!NT_SUCCESS(Status) && Status != STATUS_BUFFER_OVERFLOW)
1346         return;
1347
1348 #ifndef __REACTOS__
1349     mdn2 = malloc(offsetof(MOUNTDEV_NAME, Name[0]) + mdn.NameLength);
1350 #else
1351     mdn2 = RtlAllocateHeap(RtlGetProcessHeap(), 0, offsetof(MOUNTDEV_NAME, Name[0]) + mdn.NameLength);
1352 #endif
1353
1354     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_MOUNTDEV_QUERY_DEVICE_NAME, NULL, 0, mdn2, offsetof(MOUNTDEV_NAME, Name[0]) + mdn.NameLength);
1355     if (!NT_SUCCESS(Status))
1356         goto end;
1357
1358     RtlInitUnicodeString(&us, MOUNTMGR_DEVICE_NAME);
1359     InitializeObjectAttributes(&attr, &us, 0, NULL, NULL);
1360
1361     Status = NtOpenFile(&mountmgr, FILE_GENERIC_READ | FILE_GENERIC_WRITE, &attr, &iosb,
1362                         FILE_SHARE_READ, FILE_SYNCHRONOUS_IO_ALERT);
1363
1364     if (!NT_SUCCESS(Status))
1365         goto end;
1366
1367     // MOUNTDEV_NAME is identical to MOUNTMGR_TARGET_NAME
1368     Status = NtDeviceIoControlFile(mountmgr, NULL, NULL, NULL, &iosb, IOCTL_MOUNTMGR_VOLUME_ARRIVAL_NOTIFICATION,
1369                                    mdn2, offsetof(MOUNTDEV_NAME, Name[0]) + mdn.NameLength, NULL, 0);
1370     if (!NT_SUCCESS(Status))
1371         goto end2;
1372
1373     // MOUNTDEV_NAME is identical to MOUNTMGR_DRIVE_LETTER_TARGET
1374     Status = NtDeviceIoControlFile(mountmgr, NULL, NULL, NULL, &iosb, IOCTL_MOUNTMGR_NEXT_DRIVE_LETTER,
1375                                    mdn2, offsetof(MOUNTDEV_NAME, Name[0]) + mdn.NameLength, &mdli, sizeof(mdli));
1376     if (!NT_SUCCESS(Status))
1377         goto end2;
1378
1379 end2:
1380     NtClose(mountmgr);
1381
1382 end:
1383 #ifndef __REACTOS__
1384     free(mdn2);
1385 #else
1386     RtlFreeHeap(RtlGetProcessHeap(), 0, mdn2);
1387 #endif
1388 }
1389
1390 NTSTATUS NTAPI FormatEx(PUNICODE_STRING DriveRoot, FMIFS_MEDIA_FLAG MediaFlag, PUNICODE_STRING Label,
1391                         BOOLEAN QuickFormat, ULONG ClusterSize, PFMIFSCALLBACK Callback)
1392 {
1393     NTSTATUS Status;
1394     HANDLE h;
1395     OBJECT_ATTRIBUTES attr;
1396     IO_STATUS_BLOCK iosb;
1397     GET_LENGTH_INFORMATION gli;
1398     DISK_GEOMETRY_EX dgex;
1399     UINT32 sector_size;
1400
1401     InitializeObjectAttributes(&attr, DriveRoot, 0, NULL, NULL);
1402
1403     Status = NtOpenFile(&h, FILE_GENERIC_READ | FILE_GENERIC_WRITE, &attr, &iosb,
1404                         FILE_SHARE_READ, FILE_SYNCHRONOUS_IO_ALERT);
1405
1406     if (!NT_SUCCESS(Status))
1407         return Status;
1408
1409     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_DISK_GET_LENGTH_INFO, NULL, 0, &gli, sizeof(gli));
1410     if (!NT_SUCCESS(Status)) {
1411         NtClose(h);
1412         return Status;
1413     }
1414
1415     Status = NtDeviceIoControlFile(h, NULL, NULL, NULL, &iosb, IOCTL_DISK_GET_DRIVE_GEOMETRY_EX, NULL, 0, &dgex, sizeof(dgex));
1416     if (!NT_SUCCESS(Status)) {
1417         NtClose(h);
1418         return Status;
1419     }
1420
1421     sector_size = dgex.Geometry.BytesPerSector;
1422
1423     if (sector_size == 0x200 || sector_size == 0)
1424         sector_size = 0x1000;
1425
1426     if (Callback) {
1427         ULONG pc = 0;
1428         Callback(PROGRESS, 0, (PVOID)&pc);
1429     }
1430
1431     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_LOCK_VOLUME, NULL, 0, NULL, 0);
1432
1433     if (is_mounted_multi_device(h, sector_size)) {
1434         Status = STATUS_ACCESS_DENIED;
1435         goto end;
1436     }
1437
1438     Status = write_btrfs(h, gli.Length.QuadPart, Label, sector_size);
1439
1440     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_DISMOUNT_VOLUME, NULL, 0, NULL, 0);
1441
1442 end:
1443     NtFsControlFile(h, NULL, NULL, NULL, &iosb, FSCTL_UNLOCK_VOLUME, NULL, 0, NULL, 0);
1444
1445     if (NT_SUCCESS(Status))
1446         add_drive_letter(h);
1447
1448     NtClose(h);
1449
1450     if (Callback) {
1451         BOOL success = NT_SUCCESS(Status);
1452         Callback(DONE, 0, (PVOID)&success);
1453     }
1454
1455     return Status;
1456 }
1457
1458 BOOL APIENTRY DllMain(HANDLE hModule, DWORD dwReason, void* lpReserved) {
1459     if (dwReason == DLL_PROCESS_ATTACH)
1460         module = (HMODULE)hModule;
1461
1462     return TRUE;
1463 }