flushthread.c

Go to the documentation of this file.

/* Copyright (c) Mark Harmstone 2016-17
 *
 * This file is part of WinBtrfs.
 *
 * WinBtrfs is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public Licence as published by
 * the Free Software Foundation, either version 3 of the Licence, or
 * (at your option) any later version.
 *
 * WinBtrfs is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public Licence for more details.
 *
 * You should have received a copy of the GNU Lesser General Public Licence
 * along with WinBtrfs.  If not, see <http://www.gnu.org/licenses/>. */
 
#include "btrfs_drv.h"
#include "xxhash.h"
#include "crc32c.h"
#include <ata.h>
#include <ntddscsi.h>
#include <ntddstor.h>
 
/* cf. __MAX_CSUM_ITEMS in Linux - it needs sizeof(leaf_node) bytes free
 * so it can do a split. Linux tries to get it so a run will fit in a
 * sector, but the MAX_CSUM_ITEMS logic is wrong... */
#define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - (2 * sizeof(leaf_node)))
 
// #define DEBUG_WRITE_LOOPS
 
#define BATCH_ITEM_LIMIT 1000
 
typedef struct {
    KEVENT Event;
    IO_STATUS_BLOCK iosb;
} write_context;
 
typedef struct {
    EXTENT_ITEM_TREE eit;
    uint8_t type;
    TREE_BLOCK_REF tbr;
} EXTENT_ITEM_TREE2;
 
typedef struct {
    EXTENT_ITEM ei;
    uint8_t type;
    TREE_BLOCK_REF tbr;
} EXTENT_ITEM_SKINNY_METADATA;
 
static NTSTATUS create_chunk(device_extension* Vcb, chunk* c, PIRP Irp);
static NTSTATUS update_tree_extents(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback);
 
static NTSTATUS insert_tree_item_batch(LIST_ENTRY* batchlist, device_extension* Vcb, root* r, uint64_t objid,
                                       uint8_t objtype, uint64_t offset, _In_opt_ _When_(return >= 0, __drv_aliasesMem) void* data,
                                       uint16_t datalen, enum batch_operation operation);
 
_Function_class_(IO_COMPLETION_ROUTINE)
static NTSTATUS __stdcall write_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
    write_context* context = conptr;
 
    UNUSED(DeviceObject);
 
    context->iosb = Irp->IoStatus;
    KeSetEvent(&context->Event, 0, false);
 
    return STATUS_MORE_PROCESSING_REQUIRED;
}
 
NTSTATUS write_data_phys(_In_ PDEVICE_OBJECT device, _In_ PFILE_OBJECT fileobj, _In_ uint64_t address,
                         _In_reads_bytes_(length) void* data, _In_ uint32_t length) {
    NTSTATUS Status;
    LARGE_INTEGER offset;
    PIRP Irp;
    PIO_STACK_LOCATION IrpSp;
    write_context context;
 
    TRACE("(%p, %I64x, %p, %x)\n", device, address, data, length);
 
    RtlZeroMemory(&context, sizeof(write_context));
 
    KeInitializeEvent(&context.Event, NotificationEvent, false);
 
    offset.QuadPart = address;
 
    Irp = IoAllocateIrp(device->StackSize, false);
 
    if (!Irp) {
        ERR("IoAllocateIrp failed\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    IrpSp = IoGetNextIrpStackLocation(Irp);
    IrpSp->MajorFunction = IRP_MJ_WRITE;
    IrpSp->FileObject = fileobj;
 
    if (device->Flags & DO_BUFFERED_IO) {
        Irp->AssociatedIrp.SystemBuffer = data;
 
        Irp->Flags = IRP_BUFFERED_IO;
    } else if (device->Flags & DO_DIRECT_IO) {
        Irp->MdlAddress = IoAllocateMdl(data, length, false, false, NULL);
        if (!Irp->MdlAddress) {
            DbgPrint("IoAllocateMdl failed\n");
            Status = STATUS_INSUFFICIENT_RESOURCES;
            goto exit;
        }
 
        Status = STATUS_SUCCESS;
 
        _SEH2_TRY {
            MmProbeAndLockPages(Irp->MdlAddress, KernelMode, IoReadAccess);
        } _SEH2_EXCEPT (EXCEPTION_EXECUTE_HANDLER) {
            Status = _SEH2_GetExceptionCode();
        } _SEH2_END;
 
        if (!NT_SUCCESS(Status)) {
            ERR("MmProbeAndLockPages threw exception %08lx\n", Status);
            IoFreeMdl(Irp->MdlAddress);
            goto exit;
        }
    } else {
        Irp->UserBuffer = data;
    }
 
    IrpSp->Parameters.Write.Length = length;
    IrpSp->Parameters.Write.ByteOffset = offset;
 
    Irp->UserIosb = &context.iosb;
 
    Irp->UserEvent = &context.Event;
 
    IoSetCompletionRoutine(Irp, write_completion, &context, true, true, true);
 
    Status = IoCallDriver(device, Irp);
 
    if (Status == STATUS_PENDING) {
        KeWaitForSingleObject(&context.Event, Executive, KernelMode, false, NULL);
        Status = context.iosb.Status;
    }
 
    if (!NT_SUCCESS(Status)) {
        ERR("IoCallDriver returned %08lx\n", Status);
    }
 
    if (device->Flags & DO_DIRECT_IO) {
        MmUnlockPages(Irp->MdlAddress);
        IoFreeMdl(Irp->MdlAddress);
    }
 
exit:
    IoFreeIrp(Irp);
 
    return Status;
}
 
static void add_trim_entry(device* dev, uint64_t address, uint64_t size) {
    space* s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG);
    if (!s) {
        ERR("out of memory\n");
        return;
    }
 
    s->address = address;
    s->size = size;
    dev->num_trim_entries++;
 
    InsertTailList(&dev->trim_list, &s->list_entry);
}
 
static void clean_space_cache_chunk(device_extension* Vcb, chunk* c) {
    LIST_ENTRY* le;
    ULONG type;
 
    if (c->chunk_item->type & BLOCK_FLAG_DUPLICATE)
        type = BLOCK_FLAG_DUPLICATE;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID0)
        type = BLOCK_FLAG_RAID0;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID1)
        type = BLOCK_FLAG_DUPLICATE;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID10)
        type = BLOCK_FLAG_RAID10;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID5)
        type = BLOCK_FLAG_RAID5;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID6)
        type = BLOCK_FLAG_RAID6;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID1C3)
        type = BLOCK_FLAG_DUPLICATE;
    else if (c->chunk_item->type & BLOCK_FLAG_RAID1C4)
        type = BLOCK_FLAG_DUPLICATE;
    else // SINGLE
        type = BLOCK_FLAG_DUPLICATE;
 
    le = c->deleting.Flink;
    while (le != &c->deleting) {
        space* s = CONTAINING_RECORD(le, space, list_entry);
 
        if (!Vcb->options.no_barrier || !(c->chunk_item->type & BLOCK_FLAG_METADATA)) {
            CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
 
            if (type == BLOCK_FLAG_DUPLICATE) {
                uint16_t i;
 
                for (i = 0; i < c->chunk_item->num_stripes; i++) {
                    if (c->devices[i] && c->devices[i]->devobj && !c->devices[i]->readonly && c->devices[i]->trim)
                        add_trim_entry(c->devices[i], s->address - c->offset + cis[i].offset, s->size);
                }
            } else if (type == BLOCK_FLAG_RAID0) {
                uint64_t startoff, endoff;
                uint16_t startoffstripe, endoffstripe, i;
 
                get_raid0_offset(s->address - c->offset, c->chunk_item->stripe_length, c->chunk_item->num_stripes, &startoff, &startoffstripe);
                get_raid0_offset(s->address - c->offset + s->size - 1, c->chunk_item->stripe_length, c->chunk_item->num_stripes, &endoff, &endoffstripe);
 
                for (i = 0; i < c->chunk_item->num_stripes; i++) {
                    if (c->devices[i] && c->devices[i]->devobj && !c->devices[i]->readonly && c->devices[i]->trim) {
                        uint64_t stripestart, stripeend;
 
                        if (startoffstripe > i)
                            stripestart = startoff - (startoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
                        else if (startoffstripe == i)
                            stripestart = startoff;
                        else
                            stripestart = startoff - (startoff % c->chunk_item->stripe_length);
 
                        if (endoffstripe > i)
                            stripeend = endoff - (endoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
                        else if (endoffstripe == i)
                            stripeend = endoff + 1;
                        else
                            stripeend = endoff - (endoff % c->chunk_item->stripe_length);
 
                        if (stripestart != stripeend)
                            add_trim_entry(c->devices[i], stripestart + cis[i].offset, stripeend - stripestart);
                    }
                }
            } else if (type == BLOCK_FLAG_RAID10) {
                uint64_t startoff, endoff;
                uint16_t sub_stripes, startoffstripe, endoffstripe, i;
 
                sub_stripes = max(1, c->chunk_item->sub_stripes);
 
                get_raid0_offset(s->address - c->offset, c->chunk_item->stripe_length, c->chunk_item->num_stripes / sub_stripes, &startoff, &startoffstripe);
                get_raid0_offset(s->address - c->offset + s->size - 1, c->chunk_item->stripe_length, c->chunk_item->num_stripes / sub_stripes, &endoff, &endoffstripe);
 
                startoffstripe *= sub_stripes;
                endoffstripe *= sub_stripes;
 
                for (i = 0; i < c->chunk_item->num_stripes; i += sub_stripes) {
                    ULONG j;
                    uint64_t stripestart, stripeend;
 
                    if (startoffstripe > i)
                        stripestart = startoff - (startoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
                    else if (startoffstripe == i)
                        stripestart = startoff;
                    else
                        stripestart = startoff - (startoff % c->chunk_item->stripe_length);
 
                    if (endoffstripe > i)
                        stripeend = endoff - (endoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
                    else if (endoffstripe == i)
                        stripeend = endoff + 1;
                    else
                        stripeend = endoff - (endoff % c->chunk_item->stripe_length);
 
                    if (stripestart != stripeend) {
                        for (j = 0; j < sub_stripes; j++) {
                            if (c->devices[i+j] && c->devices[i+j]->devobj && !c->devices[i+j]->readonly && c->devices[i+j]->trim)
                                add_trim_entry(c->devices[i+j], stripestart + cis[i+j].offset, stripeend - stripestart);
                        }
                    }
                }
            }
            // FIXME - RAID5(?), RAID6(?)
        }
 
        le = le->Flink;
    }
}
 
typedef struct {
    DEVICE_MANAGE_DATA_SET_ATTRIBUTES* dmdsa;
    ATA_PASS_THROUGH_EX apte;
    PIRP Irp;
    IO_STATUS_BLOCK iosb;
#ifdef DEBUG_TRIM_EMULATION
    PMDL mdl;
    void* buf;
#endif
} ioctl_context_stripe;
 
typedef struct {
    KEVENT Event;
    LONG left;
    ioctl_context_stripe* stripes;
} ioctl_context;
 
_Function_class_(IO_COMPLETION_ROUTINE)
static NTSTATUS __stdcall ioctl_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
    ioctl_context* context = (ioctl_context*)conptr;
    LONG left2 = InterlockedDecrement(&context->left);
 
    UNUSED(DeviceObject);
    UNUSED(Irp);
 
    if (left2 == 0)
        KeSetEvent(&context->Event, 0, false);
 
    return STATUS_MORE_PROCESSING_REQUIRED;
}
 
#ifdef DEBUG_TRIM_EMULATION
static void trim_emulation(device* dev) {
    LIST_ENTRY* le;
    ioctl_context context;
    unsigned int i = 0, count = 0;
 
    le = dev->trim_list.Flink;
    while (le != &dev->trim_list) {
        count++;
        le = le->Flink;
    }
 
    context.left = count;
 
    KeInitializeEvent(&context.Event, NotificationEvent, false);
 
    context.stripes = ExAllocatePoolWithTag(NonPagedPool, sizeof(ioctl_context_stripe) * context.left, ALLOC_TAG);
    if (!context.stripes) {
        ERR("out of memory\n");
        return;
    }
 
    RtlZeroMemory(context.stripes, sizeof(ioctl_context_stripe) * context.left);
 
    i = 0;
    le = dev->trim_list.Flink;
    while (le != &dev->trim_list) {
        ioctl_context_stripe* stripe = &context.stripes[i];
        space* s = CONTAINING_RECORD(le, space, list_entry);
 
        WARN("(%I64x, %I64x)\n", s->address, s->size);
 
        stripe->Irp = IoAllocateIrp(dev->devobj->StackSize, false);
 
        if (!stripe->Irp) {
            ERR("IoAllocateIrp failed\n");
        } else {
            PIO_STACK_LOCATION IrpSp = IoGetNextIrpStackLocation(stripe->Irp);
            IrpSp->MajorFunction = IRP_MJ_WRITE;
            IrpSp->FileObject = dev->fileobj;
 
            stripe->buf = ExAllocatePoolWithTag(NonPagedPool, (uint32_t)s->size, ALLOC_TAG);
 
            if (!stripe->buf) {
                ERR("out of memory\n");
            } else {
                RtlZeroMemory(stripe->buf, (uint32_t)s->size); // FIXME - randomize instead?
 
                stripe->mdl = IoAllocateMdl(stripe->buf, (uint32_t)s->size, false, false, NULL);
 
                if (!stripe->mdl) {
                    ERR("IoAllocateMdl failed\n");
                } else {
                    MmBuildMdlForNonPagedPool(stripe->mdl);
 
                    stripe->Irp->MdlAddress = stripe->mdl;
 
                    IrpSp->Parameters.Write.ByteOffset.QuadPart = s->address;
                    IrpSp->Parameters.Write.Length = s->size;
 
                    stripe->Irp->UserIosb = &stripe->iosb;
 
                    IoSetCompletionRoutine(stripe->Irp, ioctl_completion, &context, true, true, true);
 
                    IoCallDriver(dev->devobj, stripe->Irp);
                }
            }
        }
 
        i++;
 
        le = le->Flink;
    }
 
    KeWaitForSingleObject(&context.Event, Executive, KernelMode, false, NULL);
 
    for (i = 0; i < count; i++) {
        ioctl_context_stripe* stripe = &context.stripes[i];
 
        if (stripe->mdl)
            IoFreeMdl(stripe->mdl);
 
        if (stripe->buf)
            ExFreePool(stripe->buf);
    }
 
    ExFreePool(context.stripes);
}
#endif
 
static void clean_space_cache(device_extension* Vcb) {
    LIST_ENTRY* le;
    chunk* c;
#ifndef DEBUG_TRIM_EMULATION
    ULONG num;
#endif
 
    TRACE("(%p)\n", Vcb);
 
    ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
 
    le = Vcb->chunks.Flink;
    while (le != &Vcb->chunks) {
        c = CONTAINING_RECORD(le, chunk, list_entry);
 
        if (c->space_changed) {
            acquire_chunk_lock(c, Vcb);
 
            if (c->space_changed) {
                if (Vcb->trim && !Vcb->options.no_trim)
                    clean_space_cache_chunk(Vcb, c);
 
                space_list_merge(&c->space, &c->space_size, &c->deleting);
 
                while (!IsListEmpty(&c->deleting)) {
                    space* s = CONTAINING_RECORD(RemoveHeadList(&c->deleting), space, list_entry);
 
                    ExFreePool(s);
                }
            }
 
            c->space_changed = false;
 
            release_chunk_lock(c, Vcb);
        }
 
        le = le->Flink;
    }
 
    ExReleaseResourceLite(&Vcb->chunk_lock);
 
    if (Vcb->trim && !Vcb->options.no_trim) {
#ifndef DEBUG_TRIM_EMULATION
        ioctl_context context;
        ULONG total_num;
 
        context.left = 0;
 
        le = Vcb->devices.Flink;
        while (le != &Vcb->devices) {
            device* dev = CONTAINING_RECORD(le, device, list_entry);
 
            if (dev->devobj && !dev->readonly && dev->trim && dev->num_trim_entries > 0)
                context.left++;
 
            le = le->Flink;
        }
 
        if (context.left == 0)
            return;
 
        total_num = context.left;
        num = 0;
 
        KeInitializeEvent(&context.Event, NotificationEvent, false);
 
        context.stripes = ExAllocatePoolWithTag(NonPagedPool, sizeof(ioctl_context_stripe) * context.left, ALLOC_TAG);
        if (!context.stripes) {
            ERR("out of memory\n");
            return;
        }
 
        RtlZeroMemory(context.stripes, sizeof(ioctl_context_stripe) * context.left);
#endif
 
        le = Vcb->devices.Flink;
        while (le != &Vcb->devices) {
            device* dev = CONTAINING_RECORD(le, device, list_entry);
 
            if (dev->devobj && !dev->readonly && dev->trim && dev->num_trim_entries > 0) {
#ifdef DEBUG_TRIM_EMULATION
                trim_emulation(dev);
#else
                LIST_ENTRY* le2;
                ioctl_context_stripe* stripe = &context.stripes[num];
                DEVICE_DATA_SET_RANGE* ranges;
                ULONG datalen = (ULONG)sector_align(sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES), sizeof(uint64_t)) + (dev->num_trim_entries * sizeof(DEVICE_DATA_SET_RANGE)), i;
                PIO_STACK_LOCATION IrpSp;
 
                stripe->dmdsa = ExAllocatePoolWithTag(PagedPool, datalen, ALLOC_TAG);
                if (!stripe->dmdsa) {
                    ERR("out of memory\n");
                    goto nextdev;
                }
 
                stripe->dmdsa->Size = sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES);
                stripe->dmdsa->Action = DeviceDsmAction_Trim;
                stripe->dmdsa->Flags = DEVICE_DSM_FLAG_TRIM_NOT_FS_ALLOCATED;
                stripe->dmdsa->ParameterBlockOffset = 0;
                stripe->dmdsa->ParameterBlockLength = 0;
                stripe->dmdsa->DataSetRangesOffset = (ULONG)sector_align(sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES), sizeof(uint64_t));
                stripe->dmdsa->DataSetRangesLength = dev->num_trim_entries * sizeof(DEVICE_DATA_SET_RANGE);
 
                ranges = (DEVICE_DATA_SET_RANGE*)((uint8_t*)stripe->dmdsa + stripe->dmdsa->DataSetRangesOffset);
 
                i = 0;
 
                le2 = dev->trim_list.Flink;
                while (le2 != &dev->trim_list) {
                    space* s = CONTAINING_RECORD(le2, space, list_entry);
 
                    ranges[i].StartingOffset = s->address;
                    ranges[i].LengthInBytes = s->size;
                    i++;
 
                    le2 = le2->Flink;
                }
 
                stripe->Irp = IoAllocateIrp(dev->devobj->StackSize, false);
 
                if (!stripe->Irp) {
                    ERR("IoAllocateIrp failed\n");
                    goto nextdev;
                }
 
                IrpSp = IoGetNextIrpStackLocation(stripe->Irp);
                IrpSp->MajorFunction = IRP_MJ_DEVICE_CONTROL;
                IrpSp->FileObject = dev->fileobj;
 
                IrpSp->Parameters.DeviceIoControl.IoControlCode = IOCTL_STORAGE_MANAGE_DATA_SET_ATTRIBUTES;
                IrpSp->Parameters.DeviceIoControl.InputBufferLength = datalen;
                IrpSp->Parameters.DeviceIoControl.OutputBufferLength = 0;
 
                stripe->Irp->AssociatedIrp.SystemBuffer = stripe->dmdsa;
                stripe->Irp->Flags |= IRP_BUFFERED_IO;
                stripe->Irp->UserBuffer = NULL;
                stripe->Irp->UserIosb = &stripe->iosb;
 
                IoSetCompletionRoutine(stripe->Irp, ioctl_completion, &context, true, true, true);
 
                IoCallDriver(dev->devobj, stripe->Irp);
 
nextdev:
#endif
                while (!IsListEmpty(&dev->trim_list)) {
                    space* s = CONTAINING_RECORD(RemoveHeadList(&dev->trim_list), space, list_entry);
                    ExFreePool(s);
                }
 
                dev->num_trim_entries = 0;
 
#ifndef DEBUG_TRIM_EMULATION
                num++;
#endif
            }
 
            le = le->Flink;
        }
 
#ifndef DEBUG_TRIM_EMULATION
        KeWaitForSingleObject(&context.Event, Executive, KernelMode, false, NULL);
 
        for (num = 0; num < total_num; num++) {
            if (context.stripes[num].dmdsa)
                ExFreePool(context.stripes[num].dmdsa);
 
            if (context.stripes[num].Irp)
                IoFreeIrp(context.stripes[num].Irp);
        }
 
        ExFreePool(context.stripes);
#endif
    }
}
 
static bool trees_consistent(device_extension* Vcb) {
    ULONG maxsize = Vcb->superblock.node_size - sizeof(tree_header);
    LIST_ENTRY* le;
 
    le = Vcb->trees.Flink;
    while (le != &Vcb->trees) {
        tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
        if (t->write) {
            if (t->header.num_items == 0 && t->parent) {
#ifdef DEBUG_WRITE_LOOPS
                ERR("empty tree found, looping again\n");
#endif
                return false;
            }
 
            if (t->size > maxsize) {
#ifdef DEBUG_WRITE_LOOPS
                ERR("overlarge tree found (%u > %u), looping again\n", t->size, maxsize);
#endif
                return false;
            }
 
            if (!t->has_new_address) {
#ifdef DEBUG_WRITE_LOOPS
                ERR("tree found without new address, looping again\n");
#endif
                return false;
            }
        }
 
        le = le->Flink;
    }
 
    return true;
}
 
static NTSTATUS add_parents(device_extension* Vcb, PIRP Irp) {
    ULONG level;
    LIST_ENTRY* le;
 
    for (level = 0; level <= 255; level++) {
        bool nothing_found = true;
 
        TRACE("level = %lu\n", level);
 
        le = Vcb->trees.Flink;
        while (le != &Vcb->trees) {
            tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
            if (t->write && t->header.level == level) {
                TRACE("tree %p: root = %I64x, level = %x, parent = %p\n", t, t->header.tree_id, t->header.level, t->parent);
 
                nothing_found = false;
 
                if (t->parent) {
                    if (!t->parent->write)
                        TRACE("adding tree %p (level %x)\n", t->parent, t->header.level);
 
                    t->parent->write = true;
                } else if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
                    KEY searchkey;
                    traverse_ptr tp;
                    NTSTATUS Status;
 
                    searchkey.obj_id = t->root->id;
                    searchkey.obj_type = TYPE_ROOT_ITEM;
                    searchkey.offset = 0xffffffffffffffff;
 
                    Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
                    if (!NT_SUCCESS(Status)) {
                        ERR("error - find_item returned %08lx\n", Status);
                        return Status;
                    }
 
                    if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
                        ERR("could not find ROOT_ITEM for tree %I64x\n", searchkey.obj_id);
                        return STATUS_INTERNAL_ERROR;
                    }
 
                    if (tp.item->size < sizeof(ROOT_ITEM)) { // if not full length, delete and create new entry
                        ROOT_ITEM* ri = ExAllocatePoolWithTag(PagedPool, sizeof(ROOT_ITEM), ALLOC_TAG);
 
                        if (!ri) {
                            ERR("out of memory\n");
                            return STATUS_INSUFFICIENT_RESOURCES;
                        }
 
                        RtlCopyMemory(ri, &t->root->root_item, sizeof(ROOT_ITEM));
 
                        Status = delete_tree_item(Vcb, &tp);
                        if (!NT_SUCCESS(Status)) {
                            ERR("delete_tree_item returned %08lx\n", Status);
                            ExFreePool(ri);
                            return Status;
                        }
 
                        Status = insert_tree_item(Vcb, Vcb->root_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, ri, sizeof(ROOT_ITEM), NULL, Irp);
                        if (!NT_SUCCESS(Status)) {
                            ERR("insert_tree_item returned %08lx\n", Status);
                            ExFreePool(ri);
                            return Status;
                        }
                    }
 
                    tree* t2 = tp.tree;
                    while (t2) {
                        t2->write = true;
 
                        t2 = t2->parent;
                    }
                }
            }
 
            le = le->Flink;
        }
 
        if (nothing_found)
            break;
    }
 
    return STATUS_SUCCESS;
}
 
static void add_parents_to_cache(tree* t) {
    while (t->parent) {
        t = t->parent;
        t->write = true;
    }
}
 
static bool insert_tree_extent_skinny(device_extension* Vcb, uint8_t level, uint64_t root_id, chunk* c, uint64_t address, PIRP Irp, LIST_ENTRY* rollback) {
    NTSTATUS Status;
    EXTENT_ITEM_SKINNY_METADATA* eism;
    traverse_ptr insert_tp;
 
    eism = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_ITEM_SKINNY_METADATA), ALLOC_TAG);
    if (!eism) {
        ERR("out of memory\n");
        return false;
    }
 
    eism->ei.refcount = 1;
    eism->ei.generation = Vcb->superblock.generation;
    eism->ei.flags = EXTENT_ITEM_TREE_BLOCK;
    eism->type = TYPE_TREE_BLOCK_REF;
    eism->tbr.offset = root_id;
 
    Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, eism, sizeof(EXTENT_ITEM_SKINNY_METADATA), &insert_tp, Irp);
    if (!NT_SUCCESS(Status)) {
        ERR("insert_tree_item returned %08lx\n", Status);
        ExFreePool(eism);
        return false;
    }
 
    acquire_chunk_lock(c, Vcb);
 
    space_list_subtract(c, address, Vcb->superblock.node_size, rollback);
 
    release_chunk_lock(c, Vcb);
 
    add_parents_to_cache(insert_tp.tree);
 
    return true;
}
 
bool find_metadata_address_in_chunk(device_extension* Vcb, chunk* c, uint64_t* address) {
    LIST_ENTRY* le;
    space* s;
 
    TRACE("(%p, %I64x, %p)\n", Vcb, c->offset, address);
 
    if (Vcb->superblock.node_size > c->chunk_item->size - c->used)
        return false;
 
    if (!c->cache_loaded) {
        NTSTATUS Status = load_cache_chunk(Vcb, c, NULL);
 
        if (!NT_SUCCESS(Status)) {
            ERR("load_cache_chunk returned %08lx\n", Status);
            return false;
        }
    }
 
    if (IsListEmpty(&c->space_size))
        return false;
 
    if (!c->last_alloc_set) {
        s = CONTAINING_RECORD(c->space.Blink, space, list_entry);
 
        c->last_alloc = s->address;
        c->last_alloc_set = true;
 
        if (s->size >= Vcb->superblock.node_size) {
            *address = s->address;
            c->last_alloc += Vcb->superblock.node_size;
            return true;
        }
    }
 
    le = c->space.Flink;
    while (le != &c->space) {
        s = CONTAINING_RECORD(le, space, list_entry);
 
        if (s->address <= c->last_alloc && s->address + s->size >= c->last_alloc + Vcb->superblock.node_size) {
            *address = c->last_alloc;
            c->last_alloc += Vcb->superblock.node_size;
            return true;
        }
 
        le = le->Flink;
    }
 
    le = c->space_size.Flink;
    while (le != &c->space_size) {
        s = CONTAINING_RECORD(le, space, list_entry_size);
 
        if (s->size == Vcb->superblock.node_size) {
            *address = s->address;
            c->last_alloc = s->address + Vcb->superblock.node_size;
            return true;
        } else if (s->size < Vcb->superblock.node_size) {
            if (le == c->space_size.Flink)
                return false;
 
            s = CONTAINING_RECORD(le->Blink, space, list_entry_size);
 
            *address = s->address;
            c->last_alloc = s->address + Vcb->superblock.node_size;
 
            return true;
        }
 
        le = le->Flink;
    }
 
    s = CONTAINING_RECORD(c->space_size.Blink, space, list_entry_size);
 
    if (s->size > Vcb->superblock.node_size) {
        *address = s->address;
        c->last_alloc = s->address + Vcb->superblock.node_size;
        return true;
    }
 
    return false;
}
 
static bool insert_tree_extent(device_extension* Vcb, uint8_t level, uint64_t root_id, chunk* c, uint64_t* new_address, PIRP Irp, LIST_ENTRY* rollback) {
    NTSTATUS Status;
    uint64_t address;
    EXTENT_ITEM_TREE2* eit2;
    traverse_ptr insert_tp;
 
    TRACE("(%p, %x, %I64x, %p, %p, %p, %p)\n", Vcb, level, root_id, c, new_address, Irp, rollback);
 
    if (!find_metadata_address_in_chunk(Vcb, c, &address))
        return false;
 
    if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
        bool b = insert_tree_extent_skinny(Vcb, level, root_id, c, address, Irp, rollback);
 
        if (b)
            *new_address = address;
 
        return b;
    }
 
    eit2 = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_ITEM_TREE2), ALLOC_TAG);
    if (!eit2) {
        ERR("out of memory\n");
        return false;
    }
 
    eit2->eit.extent_item.refcount = 1;
    eit2->eit.extent_item.generation = Vcb->superblock.generation;
    eit2->eit.extent_item.flags = EXTENT_ITEM_TREE_BLOCK;
    eit2->eit.level = level;
    eit2->type = TYPE_TREE_BLOCK_REF;
    eit2->tbr.offset = root_id;
 
    Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, Vcb->superblock.node_size, eit2, sizeof(EXTENT_ITEM_TREE2), &insert_tp, Irp);
    if (!NT_SUCCESS(Status)) {
        ERR("insert_tree_item returned %08lx\n", Status);
        ExFreePool(eit2);
        return false;
    }
 
    acquire_chunk_lock(c, Vcb);
 
    space_list_subtract(c, address, Vcb->superblock.node_size, rollback);
 
    release_chunk_lock(c, Vcb);
 
    add_parents_to_cache(insert_tp.tree);
 
    *new_address = address;
 
    return true;
}
 
NTSTATUS get_tree_new_address(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
    NTSTATUS Status;
    chunk *origchunk = NULL, *c;
    LIST_ENTRY* le;
    uint64_t flags, addr;
 
    if (t->root->id == BTRFS_ROOT_CHUNK)
        flags = Vcb->system_flags;
    else
        flags = Vcb->metadata_flags;
 
    if (t->has_address) {
        origchunk = get_chunk_from_address(Vcb, t->header.address);
 
        if (origchunk && !origchunk->readonly && !origchunk->reloc && origchunk->chunk_item->type == flags &&
            insert_tree_extent(Vcb, t->header.level, t->root->id, origchunk, &addr, Irp, rollback)) {
            t->new_address = addr;
            t->has_new_address = true;
            return STATUS_SUCCESS;
        }
    }
 
    ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, true);
 
    le = Vcb->chunks.Flink;
    while (le != &Vcb->chunks) {
        c = CONTAINING_RECORD(le, chunk, list_entry);
 
        if (!c->readonly && !c->reloc) {
            acquire_chunk_lock(c, Vcb);
 
            if (c != origchunk && c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
                if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
                    release_chunk_lock(c, Vcb);
                    ExReleaseResourceLite(&Vcb->chunk_lock);
                    t->new_address = addr;
                    t->has_new_address = true;
                    return STATUS_SUCCESS;
                }
            }
 
            release_chunk_lock(c, Vcb);
        }
 
        le = le->Flink;
    }
 
    // allocate new chunk if necessary
 
    Status = alloc_chunk(Vcb, flags, &c, false);
 
    if (!NT_SUCCESS(Status)) {
        ERR("alloc_chunk returned %08lx\n", Status);
        ExReleaseResourceLite(&Vcb->chunk_lock);
        return Status;
    }
 
    acquire_chunk_lock(c, Vcb);
 
    if ((c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
        if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
            release_chunk_lock(c, Vcb);
            ExReleaseResourceLite(&Vcb->chunk_lock);
            t->new_address = addr;
            t->has_new_address = true;
            return STATUS_SUCCESS;
        }
    }
 
    release_chunk_lock(c, Vcb);
 
    ExReleaseResourceLite(&Vcb->chunk_lock);
 
    ERR("couldn't find any metadata chunks with %x bytes free\n", Vcb->superblock.node_size);
 
    return STATUS_DISK_FULL;
}
 
static NTSTATUS reduce_tree_extent(device_extension* Vcb, uint64_t address, tree* t, uint64_t parent_root, uint8_t level, PIRP Irp, LIST_ENTRY* rollback) {
    NTSTATUS Status;
    uint64_t rc, root;
 
    TRACE("(%p, %I64x, %p)\n", Vcb, address, t);
 
    rc = get_extent_refcount(Vcb, address, Vcb->superblock.node_size, Irp);
    if (rc == 0) {
        ERR("error - refcount for extent %I64x was 0\n", address);
        return STATUS_INTERNAL_ERROR;
    }
 
    if (!t || t->parent)
        root = parent_root;
    else
        root = t->header.tree_id;
 
    Status = decrease_extent_refcount_tree(Vcb, address, Vcb->superblock.node_size, root, level, Irp);
    if (!NT_SUCCESS(Status)) {
        ERR("decrease_extent_refcount_tree returned %08lx\n", Status);
        return Status;
    }
 
    if (rc == 1) {
        chunk* c = get_chunk_from_address(Vcb, address);
 
        if (c) {
            acquire_chunk_lock(c, Vcb);
 
            if (!c->cache_loaded) {
                Status = load_cache_chunk(Vcb, c, NULL);
 
                if (!NT_SUCCESS(Status)) {
                    ERR("load_cache_chunk returned %08lx\n", Status);
                    release_chunk_lock(c, Vcb);
                    return Status;
                }
            }
 
            c->used -= Vcb->superblock.node_size;
 
            space_list_add(c, address, Vcb->superblock.node_size, rollback);
 
            release_chunk_lock(c, Vcb);
        } else
            ERR("could not find chunk for address %I64x\n", address);
    }
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS add_changed_extent_ref_edr(changed_extent* ce, EXTENT_DATA_REF* edr, bool old) {
    LIST_ENTRY *le2, *list;
    changed_extent_ref* cer;
 
    list = old ? &ce->old_refs : &ce->refs;
 
    le2 = list->Flink;
    while (le2 != list) {
        cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
        if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == edr->root && cer->edr.objid == edr->objid && cer->edr.offset == edr->offset) {
            cer->edr.count += edr->count;
            goto end;
        }
 
        le2 = le2->Flink;
    }
 
    cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
    if (!cer) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    cer->type = TYPE_EXTENT_DATA_REF;
    RtlCopyMemory(&cer->edr, edr, sizeof(EXTENT_DATA_REF));
    InsertTailList(list, &cer->list_entry);
 
end:
    if (old)
        ce->old_count += edr->count;
    else
        ce->count += edr->count;
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS add_changed_extent_ref_sdr(changed_extent* ce, SHARED_DATA_REF* sdr, bool old) {
    LIST_ENTRY *le2, *list;
    changed_extent_ref* cer;
 
    list = old ? &ce->old_refs : &ce->refs;
 
    le2 = list->Flink;
    while (le2 != list) {
        cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
        if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr->offset) {
            cer->sdr.count += sdr->count;
            goto end;
        }
 
        le2 = le2->Flink;
    }
 
    cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
    if (!cer) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    cer->type = TYPE_SHARED_DATA_REF;
    RtlCopyMemory(&cer->sdr, sdr, sizeof(SHARED_DATA_REF));
    InsertTailList(list, &cer->list_entry);
 
end:
    if (old)
        ce->old_count += sdr->count;
    else
        ce->count += sdr->count;
 
    return STATUS_SUCCESS;
}
 
static bool shared_tree_is_unique(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
    KEY searchkey;
    traverse_ptr tp;
    NTSTATUS Status;
 
    if (!t->updated_extents && t->has_address) {
        Status = update_tree_extents(Vcb, t, Irp, rollback);
        if (!NT_SUCCESS(Status)) {
            ERR("update_tree_extents returned %08lx\n", Status);
            return false;
        }
    }
 
    searchkey.obj_id = t->header.address;
    searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
    searchkey.offset = 0xffffffffffffffff;
 
    Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
    if (!NT_SUCCESS(Status)) {
        ERR("error - find_item returned %08lx\n", Status);
        return false;
    }
 
    if (tp.item->key.obj_id == t->header.address && (tp.item->key.obj_type == TYPE_METADATA_ITEM || tp.item->key.obj_type == TYPE_EXTENT_ITEM))
        return false;
    else
        return true;
}
 
static NTSTATUS update_tree_extents(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
    NTSTATUS Status;
    uint64_t rc = get_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, Irp);
    uint64_t flags = get_extent_flags(Vcb, t->header.address, Irp);
 
    if (rc == 0) {
        ERR("refcount for extent %I64x was 0\n", t->header.address);
        return STATUS_INTERNAL_ERROR;
    }
 
    if (flags & EXTENT_ITEM_SHARED_BACKREFS || t->header.flags & HEADER_FLAG_SHARED_BACKREF || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
        TREE_BLOCK_REF tbr;
        bool unique = rc > 1 ? false : (t->parent ? shared_tree_is_unique(Vcb, t->parent, Irp, rollback) : false);
 
        if (t->header.level == 0) {
            LIST_ENTRY* le;
 
            le = t->itemlist.Flink;
            while (le != &t->itemlist) {
                tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
                    EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
 
                    if (ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) {
                        EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
 
                        if (ed2->size > 0) {
                            EXTENT_DATA_REF edr;
                            changed_extent* ce = NULL;
                            chunk* c = get_chunk_from_address(Vcb, ed2->address);
 
                            if (c) {
                                LIST_ENTRY* le2;
 
                                le2 = c->changed_extents.Flink;
                                while (le2 != &c->changed_extents) {
                                    changed_extent* ce2 = CONTAINING_RECORD(le2, changed_extent, list_entry);
 
                                    if (ce2->address == ed2->address) {
                                        ce = ce2;
                                        break;
                                    }
 
                                    le2 = le2->Flink;
                                }
                            }
 
                            edr.root = t->root->id;
                            edr.objid = td->key.obj_id;
                            edr.offset = td->key.offset - ed2->offset;
                            edr.count = 1;
 
                            if (ce) {
                                Status = add_changed_extent_ref_edr(ce, &edr, true);
                                if (!NT_SUCCESS(Status)) {
                                    ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                    return Status;
                                }
 
                                Status = add_changed_extent_ref_edr(ce, &edr, false);
                                if (!NT_SUCCESS(Status)) {
                                    ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                    return Status;
                                }
                            }
 
                            Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp);
                            if (!NT_SUCCESS(Status)) {
                                ERR("increase_extent_refcount returned %08lx\n", Status);
                                return Status;
                            }
 
                            if ((flags & EXTENT_ITEM_SHARED_BACKREFS && unique) || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
                                uint64_t sdrrc = find_extent_shared_data_refcount(Vcb, ed2->address, t->header.address, Irp);
 
                                if (sdrrc > 0) {
                                    SHARED_DATA_REF sdr;
 
                                    sdr.offset = t->header.address;
                                    sdr.count = 1;
 
                                    Status = decrease_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_SHARED_DATA_REF, &sdr, NULL, 0,
                                                                      t->header.address, ce ? ce->superseded : false, Irp);
                                    if (!NT_SUCCESS(Status)) {
                                        ERR("decrease_extent_refcount returned %08lx\n", Status);
                                        return Status;
                                    }
 
                                    if (ce) {
                                        LIST_ENTRY* le2;
 
                                        le2 = ce->refs.Flink;
                                        while (le2 != &ce->refs) {
                                            changed_extent_ref* cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
                                            if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr.offset) {
                                                ce->count--;
                                                cer->sdr.count--;
                                                break;
                                            }
 
                                            le2 = le2->Flink;
                                        }
 
                                        le2 = ce->old_refs.Flink;
                                        while (le2 != &ce->old_refs) {
                                            changed_extent_ref* cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
                                            if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr.offset) {
                                                ce->old_count--;
 
                                                if (cer->sdr.count > 1)
                                                    cer->sdr.count--;
                                                else {
                                                    RemoveEntryList(&cer->list_entry);
                                                    ExFreePool(cer);
                                                }
 
                                                break;
                                            }
 
                                            le2 = le2->Flink;
                                        }
                                    }
                                }
                            }
 
                            // FIXME - clear shared flag if unique?
                        }
                    }
                }
 
                le = le->Flink;
            }
        } else {
            LIST_ENTRY* le;
 
            le = t->itemlist.Flink;
            while (le != &t->itemlist) {
                tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (!td->inserted) {
                    tbr.offset = t->root->id;
 
                    Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF,
                                                      &tbr, &td->key, t->header.level - 1, Irp);
                    if (!NT_SUCCESS(Status)) {
                        ERR("increase_extent_refcount returned %08lx\n", Status);
                        return Status;
                    }
 
                    if (unique || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
                        uint64_t sbrrc = find_extent_shared_tree_refcount(Vcb, td->treeholder.address, t->header.address, Irp);
 
                        if (sbrrc > 0) {
                            SHARED_BLOCK_REF sbr;
 
                            sbr.offset = t->header.address;
 
                            Status = decrease_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
                                                              t->header.address, false, Irp);
                            if (!NT_SUCCESS(Status)) {
                                ERR("decrease_extent_refcount returned %08lx\n", Status);
                                return Status;
                            }
                        }
                    }
 
                    // FIXME - clear shared flag if unique?
                }
 
                le = le->Flink;
            }
        }
 
        if (unique) {
            uint64_t sbrrc = find_extent_shared_tree_refcount(Vcb, t->header.address, t->parent->header.address, Irp);
 
            if (sbrrc == 1) {
                SHARED_BLOCK_REF sbr;
 
                sbr.offset = t->parent->header.address;
 
                Status = decrease_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
                                                  t->parent->header.address, false, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("decrease_extent_refcount returned %08lx\n", Status);
                    return Status;
                }
            }
        }
 
        if (t->parent)
            tbr.offset = t->parent->header.tree_id;
        else
            tbr.offset = t->header.tree_id;
 
        Status = increase_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr,
                                          t->parent ? &t->paritem->key : NULL, t->header.level, Irp);
        if (!NT_SUCCESS(Status)) {
            ERR("increase_extent_refcount returned %08lx\n", Status);
            return Status;
        }
 
        // FIXME - clear shared flag if unique?
 
        t->header.flags &= ~HEADER_FLAG_SHARED_BACKREF;
    }
 
    if (rc > 1 || t->header.tree_id == t->root->id) {
        Status = reduce_tree_extent(Vcb, t->header.address, t, t->parent ? t->parent->header.tree_id : t->header.tree_id, t->header.level, Irp, rollback);
 
        if (!NT_SUCCESS(Status)) {
            ERR("reduce_tree_extent returned %08lx\n", Status);
            return Status;
        }
    }
 
    t->has_address = false;
 
    if ((rc > 1 || t->header.tree_id != t->root->id) && !(flags & EXTENT_ITEM_SHARED_BACKREFS)) {
        if (t->header.tree_id == t->root->id) {
            flags |= EXTENT_ITEM_SHARED_BACKREFS;
            update_extent_flags(Vcb, t->header.address, flags, Irp);
        }
 
        if (t->header.level > 0) {
            LIST_ENTRY* le;
 
            le = t->itemlist.Flink;
            while (le != &t->itemlist) {
                tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (!td->inserted) {
                    if (t->header.tree_id == t->root->id) {
                        SHARED_BLOCK_REF sbr;
 
                        sbr.offset = t->header.address;
 
                        Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, &td->key, t->header.level - 1, Irp);
                    } else {
                        TREE_BLOCK_REF tbr;
 
                        tbr.offset = t->root->id;
 
                        Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr, &td->key, t->header.level - 1, Irp);
                    }
 
                    if (!NT_SUCCESS(Status)) {
                        ERR("increase_extent_refcount returned %08lx\n", Status);
                        return Status;
                    }
                }
 
                le = le->Flink;
            }
        } else {
            LIST_ENTRY* le;
 
            le = t->itemlist.Flink;
            while (le != &t->itemlist) {
                tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
                    EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
 
                    if (ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) {
                        EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
 
                        if (ed2->size > 0) {
                            changed_extent* ce = NULL;
                            chunk* c = get_chunk_from_address(Vcb, ed2->address);
 
                            if (c) {
                                LIST_ENTRY* le2;
 
                                le2 = c->changed_extents.Flink;
                                while (le2 != &c->changed_extents) {
                                    changed_extent* ce2 = CONTAINING_RECORD(le2, changed_extent, list_entry);
 
                                    if (ce2->address == ed2->address) {
                                        ce = ce2;
                                        break;
                                    }
 
                                    le2 = le2->Flink;
                                }
                            }
 
                            if (t->header.tree_id == t->root->id) {
                                SHARED_DATA_REF sdr;
 
                                sdr.offset = t->header.address;
                                sdr.count = 1;
 
                                if (ce) {
                                    Status = add_changed_extent_ref_sdr(ce, &sdr, true);
                                    if (!NT_SUCCESS(Status)) {
                                        ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                        return Status;
                                    }
 
                                    Status = add_changed_extent_ref_sdr(ce, &sdr, false);
                                    if (!NT_SUCCESS(Status)) {
                                        ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                        return Status;
                                    }
                                }
 
                                Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_SHARED_DATA_REF, &sdr, NULL, 0, Irp);
                            } else {
                                EXTENT_DATA_REF edr;
 
                                edr.root = t->root->id;
                                edr.objid = td->key.obj_id;
                                edr.offset = td->key.offset - ed2->offset;
                                edr.count = 1;
 
                                if (ce) {
                                    Status = add_changed_extent_ref_edr(ce, &edr, true);
                                    if (!NT_SUCCESS(Status)) {
                                        ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                        return Status;
                                    }
 
                                    Status = add_changed_extent_ref_edr(ce, &edr, false);
                                    if (!NT_SUCCESS(Status)) {
                                        ERR("add_changed_extent_ref_edr returned %08lx\n", Status);
                                        return Status;
                                    }
                                }
 
                                Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp);
                            }
 
                            if (!NT_SUCCESS(Status)) {
                                ERR("increase_extent_refcount returned %08lx\n", Status);
                                return Status;
                            }
                        }
                    }
                }
 
                le = le->Flink;
            }
        }
    }
 
    t->updated_extents = true;
    t->header.tree_id = t->root->id;
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS allocate_tree_extents(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
    LIST_ENTRY* le;
    NTSTATUS Status;
    bool changed = false;
    uint8_t max_level = 0, level;
 
    TRACE("(%p)\n", Vcb);
 
    le = Vcb->trees.Flink;
    while (le != &Vcb->trees) {
        tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
        if (t->write && !t->has_new_address) {
            chunk* c;
 
            if (t->has_address) {
                c = get_chunk_from_address(Vcb, t->header.address);
 
                if (c) {
                    if (!c->cache_loaded) {
                        acquire_chunk_lock(c, Vcb);
 
                        if (!c->cache_loaded) {
                            Status = load_cache_chunk(Vcb, c, NULL);
 
                            if (!NT_SUCCESS(Status)) {
                                ERR("load_cache_chunk returned %08lx\n", Status);
                                release_chunk_lock(c, Vcb);
                                return Status;
                            }
                        }
 
                        release_chunk_lock(c, Vcb);
                    }
                }
            }
 
            Status = get_tree_new_address(Vcb, t, Irp, rollback);
            if (!NT_SUCCESS(Status)) {
                ERR("get_tree_new_address returned %08lx\n", Status);
                return Status;
            }
 
            TRACE("allocated extent %I64x\n", t->new_address);
 
            c = get_chunk_from_address(Vcb, t->new_address);
 
            if (c)
                c->used += Vcb->superblock.node_size;
            else {
                ERR("could not find chunk for address %I64x\n", t->new_address);
                return STATUS_INTERNAL_ERROR;
            }
 
            changed = true;
 
            if (t->header.level > max_level)
                max_level = t->header.level;
        }
 
        le = le->Flink;
    }
 
    if (!changed)
        return STATUS_SUCCESS;
 
    level = max_level;
    do {
        le = Vcb->trees.Flink;
        while (le != &Vcb->trees) {
            tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
            if (t->write && !t->updated_extents && t->has_address && t->header.level == level) {
                Status = update_tree_extents(Vcb, t, Irp, rollback);
                if (!NT_SUCCESS(Status)) {
                    ERR("update_tree_extents returned %08lx\n", Status);
                    return Status;
                }
            }
 
            le = le->Flink;
        }
 
        if (level == 0)
            break;
 
        level--;
    } while (true);
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS update_root_root(device_extension* Vcb, bool no_cache, PIRP Irp, LIST_ENTRY* rollback) {
    LIST_ENTRY* le;
    NTSTATUS Status;
 
    TRACE("(%p)\n", Vcb);
 
    le = Vcb->trees.Flink;
    while (le != &Vcb->trees) {
        tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
        if (t->write && !t->parent) {
            if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
                KEY searchkey;
                traverse_ptr tp;
 
                searchkey.obj_id = t->root->id;
                searchkey.obj_type = TYPE_ROOT_ITEM;
                searchkey.offset = 0xffffffffffffffff;
 
                Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("error - find_item returned %08lx\n", Status);
                    return Status;
                }
 
                if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
                    ERR("could not find ROOT_ITEM for tree %I64x\n", searchkey.obj_id);
                    return STATUS_INTERNAL_ERROR;
                }
 
                TRACE("updating the address for root %I64x to %I64x\n", searchkey.obj_id, t->new_address);
 
                t->root->root_item.block_number = t->new_address;
                t->root->root_item.root_level = t->header.level;
                t->root->root_item.generation = Vcb->superblock.generation;
                t->root->root_item.generation2 = Vcb->superblock.generation;
 
                // item is guaranteed to be at least sizeof(ROOT_ITEM), due to add_parents
 
                RtlCopyMemory(tp.item->data, &t->root->root_item, sizeof(ROOT_ITEM));
            }
 
            t->root->treeholder.address = t->new_address;
            t->root->treeholder.generation = Vcb->superblock.generation;
        }
 
        le = le->Flink;
    }
 
    if (!no_cache && !(Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE)) {
        ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
        Status = update_chunk_caches(Vcb, Irp, rollback);
        ExReleaseResourceLite(&Vcb->chunk_lock);
 
        if (!NT_SUCCESS(Status)) {
            ERR("update_chunk_caches returned %08lx\n", Status);
            return Status;
        }
    }
 
    return STATUS_SUCCESS;
}
 
NTSTATUS do_tree_writes(device_extension* Vcb, LIST_ENTRY* tree_writes, bool no_free) {
    chunk* c;
    LIST_ENTRY* le;
    tree_write* tw;
    NTSTATUS Status;
    ULONG i, num_bits;
    write_data_context* wtc;
    ULONG bit_num = 0;
    bool raid56 = false;
 
    // merge together runs
    c = NULL;
    le = tree_writes->Flink;
    while (le != tree_writes) {
        tw = CONTAINING_RECORD(le, tree_write, list_entry);
 
        if (!c || tw->address < c->offset || tw->address >= c->offset + c->chunk_item->size)
            c = get_chunk_from_address(Vcb, tw->address);
        else {
            tree_write* tw2 = CONTAINING_RECORD(le->Blink, tree_write, list_entry);
 
            if (tw->address == tw2->address + tw2->length) {
                uint8_t* data = ExAllocatePoolWithTag(NonPagedPool, tw2->length + tw->length, ALLOC_TAG);
 
                if (!data) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }
 
                RtlCopyMemory(data, tw2->data, tw2->length);
                RtlCopyMemory(&data[tw2->length], tw->data, tw->length);
 
                if (!no_free || tw2->allocated)
                    ExFreePool(tw2->data);
 
                tw2->data = data;
                tw2->length += tw->length;
                tw2->allocated = true;
 
                if (!no_free || tw->allocated)
                    ExFreePool(tw->data);
 
                RemoveEntryList(&tw->list_entry);
                ExFreePool(tw);
 
                le = tw2->list_entry.Flink;
                continue;
            }
        }
 
        tw->c = c;
 
        if (c->chunk_item->type & (BLOCK_FLAG_RAID5 | BLOCK_FLAG_RAID6))
            raid56 = true;
 
        le = le->Flink;
    }
 
    num_bits = 0;
 
    le = tree_writes->Flink;
    while (le != tree_writes) {
        tw = CONTAINING_RECORD(le, tree_write, list_entry);
 
        num_bits++;
 
        le = le->Flink;
    }
 
    wtc = ExAllocatePoolWithTag(NonPagedPool, sizeof(write_data_context) * num_bits, ALLOC_TAG);
    if (!wtc) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    le = tree_writes->Flink;
 
    while (le != tree_writes) {
        tw = CONTAINING_RECORD(le, tree_write, list_entry);
 
        TRACE("address: %I64x, size: %x\n", tw->address, tw->length);
 
        KeInitializeEvent(&wtc[bit_num].Event, NotificationEvent, false);
        InitializeListHead(&wtc[bit_num].stripes);
        wtc[bit_num].need_wait = false;
        wtc[bit_num].stripes_left = 0;
        wtc[bit_num].parity1 = wtc[bit_num].parity2 = wtc[bit_num].scratch = NULL;
        wtc[bit_num].mdl = wtc[bit_num].parity1_mdl = wtc[bit_num].parity2_mdl = NULL;
 
        Status = write_data(Vcb, tw->address, tw->data, tw->length, &wtc[bit_num], NULL, NULL, false, 0, HighPagePriority);
        if (!NT_SUCCESS(Status)) {
            ERR("write_data returned %08lx\n", Status);
 
            for (i = 0; i < num_bits; i++) {
                free_write_data_stripes(&wtc[i]);
            }
            ExFreePool(wtc);
 
            return Status;
        }
 
        bit_num++;
 
        le = le->Flink;
    }
 
    for (i = 0; i < num_bits; i++) {
        if (wtc[i].stripes.Flink != &wtc[i].stripes) {
            // launch writes and wait
            le = wtc[i].stripes.Flink;
            while (le != &wtc[i].stripes) {
                write_data_stripe* stripe = CONTAINING_RECORD(le, write_data_stripe, list_entry);
 
                if (stripe->status != WriteDataStatus_Ignore) {
                    wtc[i].need_wait = true;
                    IoCallDriver(stripe->device->devobj, stripe->Irp);
                }
 
                le = le->Flink;
            }
        }
    }
 
    for (i = 0; i < num_bits; i++) {
        if (wtc[i].need_wait)
            KeWaitForSingleObject(&wtc[i].Event, Executive, KernelMode, false, NULL);
    }
 
    for (i = 0; i < num_bits; i++) {
        le = wtc[i].stripes.Flink;
        while (le != &wtc[i].stripes) {
            write_data_stripe* stripe = CONTAINING_RECORD(le, write_data_stripe, list_entry);
 
            if (stripe->status != WriteDataStatus_Ignore && !NT_SUCCESS(stripe->iosb.Status)) {
                Status = stripe->iosb.Status;
                log_device_error(Vcb, stripe->device, BTRFS_DEV_STAT_WRITE_ERRORS);
                break;
            }
 
            le = le->Flink;
        }
 
        free_write_data_stripes(&wtc[i]);
    }
 
    ExFreePool(wtc);
 
    if (raid56) {
        c = NULL;
 
        le = tree_writes->Flink;
        while (le != tree_writes) {
            tw = CONTAINING_RECORD(le, tree_write, list_entry);
 
            if (tw->c != c) {
                c = tw->c;
 
                ExAcquireResourceExclusiveLite(&c->partial_stripes_lock, true);
 
                while (!IsListEmpty(&c->partial_stripes)) {
                    partial_stripe* ps = CONTAINING_RECORD(RemoveHeadList(&c->partial_stripes), partial_stripe, list_entry);
 
                    Status = flush_partial_stripe(Vcb, c, ps);
 
                    if (ps->bmparr)
                        ExFreePool(ps->bmparr);
 
                    ExFreePool(ps);
 
                    if (!NT_SUCCESS(Status)) {
                        ERR("flush_partial_stripe returned %08lx\n", Status);
                        ExReleaseResourceLite(&c->partial_stripes_lock);
                        return Status;
                    }
                }
 
                ExReleaseResourceLite(&c->partial_stripes_lock);
            }
 
            le = le->Flink;
        }
    }
 
    return STATUS_SUCCESS;
}
 
void calc_tree_checksum(device_extension* Vcb, tree_header* th) {
    switch (Vcb->superblock.csum_type) {
        case CSUM_TYPE_CRC32C:
            *((uint32_t*)th) = ~calc_crc32c(0xffffffff, (uint8_t*)&th->fs_uuid, Vcb->superblock.node_size - sizeof(th->csum));
        break;
 
        case CSUM_TYPE_XXHASH:
            *((uint64_t*)th) = XXH64((uint8_t*)&th->fs_uuid, Vcb->superblock.node_size - sizeof(th->csum), 0);
        break;
 
        case CSUM_TYPE_SHA256:
            calc_sha256((uint8_t*)th, &th->fs_uuid, Vcb->superblock.node_size - sizeof(th->csum));
        break;
 
        case CSUM_TYPE_BLAKE2:
            blake2b((uint8_t*)th, BLAKE2_HASH_SIZE, &th->fs_uuid, Vcb->superblock.node_size - sizeof(th->csum));
        break;
    }
}
 
static NTSTATUS write_trees(device_extension* Vcb, PIRP Irp) {
    ULONG level;
    uint8_t *data, *body;
    NTSTATUS Status;
    LIST_ENTRY* le;
    LIST_ENTRY tree_writes;
    tree_write* tw;
 
    TRACE("(%p)\n", Vcb);
 
    InitializeListHead(&tree_writes);
 
    for (level = 0; level <= 255; level++) {
        bool nothing_found = true;
 
        TRACE("level = %lu\n", level);
 
        le = Vcb->trees.Flink;
        while (le != &Vcb->trees) {
            tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
            if (t->write && t->header.level == level) {
                KEY firstitem, searchkey;
                LIST_ENTRY* le2;
                traverse_ptr tp;
 
                if (!t->has_new_address) {
                    ERR("error - tried to write tree with no new address\n");
                    return STATUS_INTERNAL_ERROR;
                }
 
                le2 = t->itemlist.Flink;
                while (le2 != &t->itemlist) {
                    tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
                    if (!td->ignore) {
                        firstitem = td->key;
                        break;
                    }
                    le2 = le2->Flink;
                }
 
                if (t->parent) {
                    t->paritem->key = firstitem;
                    t->paritem->treeholder.address = t->new_address;
                    t->paritem->treeholder.generation = Vcb->superblock.generation;
                }
 
                if (!(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
                    EXTENT_ITEM_TREE* eit;
 
                    searchkey.obj_id = t->new_address;
                    searchkey.obj_type = TYPE_EXTENT_ITEM;
                    searchkey.offset = Vcb->superblock.node_size;
 
                    Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
                    if (!NT_SUCCESS(Status)) {
                        ERR("error - find_item returned %08lx\n", Status);
                        return Status;
                    }
 
                    if (keycmp(searchkey, tp.item->key)) {
                        ERR("could not find %I64x,%x,%I64x in extent_root (found %I64x,%x,%I64x instead)\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
                        return STATUS_INTERNAL_ERROR;
                    }
 
                    if (tp.item->size < sizeof(EXTENT_ITEM_TREE)) {
                        ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM_TREE));
                        return STATUS_INTERNAL_ERROR;
                    }
 
                    eit = (EXTENT_ITEM_TREE*)tp.item->data;
                    eit->firstitem = firstitem;
                }
 
                nothing_found = false;
            }
 
            le = le->Flink;
        }
 
        if (nothing_found)
            break;
    }
 
    TRACE("allocated tree extents\n");
 
    le = Vcb->trees.Flink;
    while (le != &Vcb->trees) {
        tree* t = CONTAINING_RECORD(le, tree, list_entry);
        LIST_ENTRY* le2;
#ifdef DEBUG_PARANOID
        uint32_t num_items = 0, size = 0;
        bool crash = false;
#endif
 
        if (t->write) {
#ifdef DEBUG_PARANOID
            bool first = true;
            KEY lastkey;
 
            le2 = t->itemlist.Flink;
            while (le2 != &t->itemlist) {
                tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
                if (!td->ignore) {
                    num_items++;
 
                    if (!first) {
                        if (keycmp(td->key, lastkey) == 0) {
                            ERR("(%I64x,%x,%I64x): duplicate key\n", td->key.obj_id, td->key.obj_type, td->key.offset);
                            crash = true;
                        } else if (keycmp(td->key, lastkey) == -1) {
                            ERR("(%I64x,%x,%I64x): key out of order\n", td->key.obj_id, td->key.obj_type, td->key.offset);
                            crash = true;
                        }
                    } else
                        first = false;
 
                    lastkey = td->key;
 
                    if (t->header.level == 0)
                        size += td->size;
                }
                le2 = le2->Flink;
            }
 
            if (t->header.level == 0)
                size += num_items * sizeof(leaf_node);
            else
                size += num_items * sizeof(internal_node);
 
            if (num_items != t->header.num_items) {
                ERR("tree %I64x, level %x: num_items was %x, expected %x\n", t->root->id, t->header.level, num_items, t->header.num_items);
                crash = true;
            }
 
            if (size != t->size) {
                ERR("tree %I64x, level %x: size was %x, expected %x\n", t->root->id, t->header.level, size, t->size);
                crash = true;
            }
 
            if (t->header.num_items == 0 && t->parent) {
                ERR("tree %I64x, level %x: tried to write empty tree with parent\n", t->root->id, t->header.level);
                crash = true;
            }
 
            if (t->size > Vcb->superblock.node_size - sizeof(tree_header)) {
                ERR("tree %I64x, level %x: tried to write overlarge tree (%x > %Ix)\n", t->root->id, t->header.level, t->size, Vcb->superblock.node_size - sizeof(tree_header));
                crash = true;
            }
 
            if (crash) {
                ERR("tree %p\n", t);
                le2 = t->itemlist.Flink;
                while (le2 != &t->itemlist) {
                    tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
                    if (!td->ignore) {
                        ERR("%I64x,%x,%I64x inserted=%u\n", td->key.obj_id, td->key.obj_type, td->key.offset, td->inserted);
                    }
                    le2 = le2->Flink;
                }
                int3;
            }
#endif
            t->header.address = t->new_address;
            t->header.generation = Vcb->superblock.generation;
            t->header.tree_id = t->root->id;
            t->header.flags |= HEADER_FLAG_MIXED_BACKREF;
            t->header.fs_uuid = Vcb->superblock.metadata_uuid;
            t->has_address = true;
 
            data = ExAllocatePoolWithTag(NonPagedPool, Vcb->superblock.node_size, ALLOC_TAG);
            if (!data) {
                ERR("out of memory\n");
                Status = STATUS_INSUFFICIENT_RESOURCES;
                goto end;
            }
 
            body = data + sizeof(tree_header);
 
            RtlCopyMemory(data, &t->header, sizeof(tree_header));
            RtlZeroMemory(body, Vcb->superblock.node_size - sizeof(tree_header));
 
            if (t->header.level == 0) {
                leaf_node* itemptr = (leaf_node*)body;
                int i = 0;
                uint8_t* dataptr = data + Vcb->superblock.node_size;
 
                le2 = t->itemlist.Flink;
                while (le2 != &t->itemlist) {
                    tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
                    if (!td->ignore) {
                        dataptr = dataptr - td->size;
 
                        itemptr[i].key = td->key;
                        itemptr[i].offset = (uint32_t)((uint8_t*)dataptr - (uint8_t*)body);
                        itemptr[i].size = td->size;
                        i++;
 
                        if (td->size > 0)
                            RtlCopyMemory(dataptr, td->data, td->size);
                    }
 
                    le2 = le2->Flink;
                }
            } else {
                internal_node* itemptr = (internal_node*)body;
                int i = 0;
 
                le2 = t->itemlist.Flink;
                while (le2 != &t->itemlist) {
                    tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
                    if (!td->ignore) {
                        itemptr[i].key = td->key;
                        itemptr[i].address = td->treeholder.address;
                        itemptr[i].generation = td->treeholder.generation;
                        i++;
                    }
 
                    le2 = le2->Flink;
                }
            }
 
            calc_tree_checksum(Vcb, (tree_header*)data);
 
            tw = ExAllocatePoolWithTag(PagedPool, sizeof(tree_write), ALLOC_TAG);
            if (!tw) {
                ERR("out of memory\n");
                ExFreePool(data);
                Status = STATUS_INSUFFICIENT_RESOURCES;
                goto end;
            }
 
            tw->address = t->new_address;
            tw->length = Vcb->superblock.node_size;
            tw->data = data;
            tw->allocated = false;
 
            if (IsListEmpty(&tree_writes))
                InsertTailList(&tree_writes, &tw->list_entry);
            else {
                bool inserted = false;
 
                le2 = tree_writes.Flink;
                while (le2 != &tree_writes) {
                    tree_write* tw2 = CONTAINING_RECORD(le2, tree_write, list_entry);
 
                    if (tw2->address > tw->address) {
                        InsertHeadList(le2->Blink, &tw->list_entry);
                        inserted = true;
                        break;
                    }
 
                    le2 = le2->Flink;
                }
 
                if (!inserted)
                    InsertTailList(&tree_writes, &tw->list_entry);
            }
        }
 
        le = le->Flink;
    }
 
    Status = do_tree_writes(Vcb, &tree_writes, false);
    if (!NT_SUCCESS(Status)) {
        ERR("do_tree_writes returned %08lx\n", Status);
        goto end;
    }
 
    Status = STATUS_SUCCESS;
 
end:
    while (!IsListEmpty(&tree_writes)) {
        le = RemoveHeadList(&tree_writes);
        tw = CONTAINING_RECORD(le, tree_write, list_entry);
 
        if (tw->data)
            ExFreePool(tw->data);
 
        ExFreePool(tw);
    }
 
    return Status;
}
 
static void update_backup_superblock(device_extension* Vcb, superblock_backup* sb, PIRP Irp) {
    KEY searchkey;
    traverse_ptr tp;
 
    RtlZeroMemory(sb, sizeof(superblock_backup));
 
    sb->root_tree_addr = Vcb->superblock.root_tree_addr;
    sb->root_tree_generation = Vcb->superblock.generation;
    sb->root_level = Vcb->superblock.root_level;
 
    sb->chunk_tree_addr = Vcb->superblock.chunk_tree_addr;
    sb->chunk_tree_generation = Vcb->superblock.chunk_root_generation;
    sb->chunk_root_level = Vcb->superblock.chunk_root_level;
 
    searchkey.obj_id = BTRFS_ROOT_EXTENT;
    searchkey.obj_type = TYPE_ROOT_ITEM;
    searchkey.offset = 0xffffffffffffffff;
 
    if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
        if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
            ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
 
            sb->extent_tree_addr = ri->block_number;
            sb->extent_tree_generation = ri->generation;
            sb->extent_root_level = ri->root_level;
        }
    }
 
    searchkey.obj_id = BTRFS_ROOT_FSTREE;
 
    if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
        if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
            ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
 
            sb->fs_tree_addr = ri->block_number;
            sb->fs_tree_generation = ri->generation;
            sb->fs_root_level = ri->root_level;
        }
    }
 
    searchkey.obj_id = BTRFS_ROOT_DEVTREE;
 
    if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
        if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
            ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
 
            sb->dev_root_addr = ri->block_number;
            sb->dev_root_generation = ri->generation;
            sb->dev_root_level = ri->root_level;
        }
    }
 
    searchkey.obj_id = BTRFS_ROOT_CHECKSUM;
 
    if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
        if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
            ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
 
            sb->csum_root_addr = ri->block_number;
            sb->csum_root_generation = ri->generation;
            sb->csum_root_level = ri->root_level;
        }
    }
 
    sb->total_bytes = Vcb->superblock.total_bytes;
    sb->bytes_used = Vcb->superblock.bytes_used;
    sb->num_devices = Vcb->superblock.num_devices;
}
 
typedef struct {
    void* context;
    uint8_t* buf;
    PMDL mdl;
    device* device;
    NTSTATUS Status;
    PIRP Irp;
    LIST_ENTRY list_entry;
} write_superblocks_stripe;
 
typedef struct _write_superblocks_context {
    KEVENT Event;
    LIST_ENTRY stripes;
    LONG left;
} write_superblocks_context;
 
_Function_class_(IO_COMPLETION_ROUTINE)
static NTSTATUS __stdcall write_superblock_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
    write_superblocks_stripe* stripe = conptr;
    write_superblocks_context* context = stripe->context;
 
    UNUSED(DeviceObject);
 
    stripe->Status = Irp->IoStatus.Status;
 
    if (InterlockedDecrement(&context->left) == 0)
        KeSetEvent(&context->Event, 0, false);
 
    return STATUS_MORE_PROCESSING_REQUIRED;
}
 
static void calc_superblock_checksum(superblock* sb) {
    switch (sb->csum_type) {
        case CSUM_TYPE_CRC32C:
            *(uint32_t*)sb = ~calc_crc32c(0xffffffff, (uint8_t*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
        break;
 
        case CSUM_TYPE_XXHASH:
            *(uint64_t*)sb = XXH64(&sb->uuid, sizeof(superblock) - sizeof(sb->checksum), 0);
        break;
 
        case CSUM_TYPE_SHA256:
            calc_sha256((uint8_t*)sb, &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
        break;
 
        case CSUM_TYPE_BLAKE2:
            blake2b((uint8_t*)sb, BLAKE2_HASH_SIZE, &sb->uuid, sizeof(superblock) - sizeof(sb->checksum));
        break;
    }
}
 
static NTSTATUS write_superblock(device_extension* Vcb, device* device, write_superblocks_context* context) {
    unsigned int i = 0;
 
    // All the documentation says that the Linux driver only writes one superblock
    // if it thinks a disk is an SSD, but this doesn't seem to be the case!
 
    while (superblock_addrs[i] > 0 && device->devitem.num_bytes >= superblock_addrs[i] + sizeof(superblock)) {
        ULONG sblen = (ULONG)sector_align(sizeof(superblock), Vcb->superblock.sector_size);
        superblock* sb;
        write_superblocks_stripe* stripe;
        PIO_STACK_LOCATION IrpSp;
 
        sb = ExAllocatePoolWithTag(NonPagedPool, sblen, ALLOC_TAG);
        if (!sb) {
            ERR("out of memory\n");
            return STATUS_INSUFFICIENT_RESOURCES;
        }
 
        RtlCopyMemory(sb, &Vcb->superblock, sizeof(superblock));
 
        if (sblen > sizeof(superblock))
            RtlZeroMemory((uint8_t*)sb + sizeof(superblock), sblen - sizeof(superblock));
 
        RtlCopyMemory(&sb->dev_item, &device->devitem, sizeof(DEV_ITEM));
        sb->sb_phys_addr = superblock_addrs[i];
 
        calc_superblock_checksum(sb);
 
        stripe = ExAllocatePoolWithTag(NonPagedPool, sizeof(write_superblocks_stripe), ALLOC_TAG);
        if (!stripe) {
            ERR("out of memory\n");
            ExFreePool(sb);
            return STATUS_INSUFFICIENT_RESOURCES;
        }
 
        stripe->buf = (uint8_t*)sb;
 
        stripe->Irp = IoAllocateIrp(device->devobj->StackSize, false);
        if (!stripe->Irp) {
            ERR("IoAllocateIrp failed\n");
            ExFreePool(stripe);
            ExFreePool(sb);
            return STATUS_INSUFFICIENT_RESOURCES;
        }
 
        IrpSp = IoGetNextIrpStackLocation(stripe->Irp);
        IrpSp->MajorFunction = IRP_MJ_WRITE;
        IrpSp->FileObject = device->fileobj;
 
        if (i == 0)
            IrpSp->Flags |= SL_WRITE_THROUGH;
 
        if (device->devobj->Flags & DO_BUFFERED_IO) {
            stripe->Irp->AssociatedIrp.SystemBuffer = sb;
            stripe->mdl = NULL;
 
            stripe->Irp->Flags = IRP_BUFFERED_IO;
        } else if (device->devobj->Flags & DO_DIRECT_IO) {
            stripe->mdl = IoAllocateMdl(sb, sblen, false, false, NULL);
            if (!stripe->mdl) {
                ERR("IoAllocateMdl failed\n");
                IoFreeIrp(stripe->Irp);
                ExFreePool(stripe);
                ExFreePool(sb);
                return STATUS_INSUFFICIENT_RESOURCES;
            }
 
            stripe->Irp->MdlAddress = stripe->mdl;
 
            MmBuildMdlForNonPagedPool(stripe->mdl);
        } else {
            stripe->Irp->UserBuffer = sb;
            stripe->mdl = NULL;
        }
 
        IrpSp->Parameters.Write.Length = sblen;
        IrpSp->Parameters.Write.ByteOffset.QuadPart = superblock_addrs[i];
 
        IoSetCompletionRoutine(stripe->Irp, write_superblock_completion, stripe, true, true, true);
 
        stripe->context = context;
        stripe->device = device;
        InsertTailList(&context->stripes, &stripe->list_entry);
 
        context->left++;
 
        i++;
    }
 
    if (i == 0)
        ERR("no superblocks written!\n");
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS write_superblocks(device_extension* Vcb, PIRP Irp) {
    uint64_t i;
    NTSTATUS Status;
    LIST_ENTRY* le;
    write_superblocks_context context;
 
    TRACE("(%p)\n", Vcb);
 
    le = Vcb->trees.Flink;
    while (le != &Vcb->trees) {
        tree* t = CONTAINING_RECORD(le, tree, list_entry);
 
        if (t->write && !t->parent) {
            if (t->root == Vcb->root_root) {
                Vcb->superblock.root_tree_addr = t->new_address;
                Vcb->superblock.root_level = t->header.level;
            } else if (t->root == Vcb->chunk_root) {
                Vcb->superblock.chunk_tree_addr = t->new_address;
                Vcb->superblock.chunk_root_generation = t->header.generation;
                Vcb->superblock.chunk_root_level = t->header.level;
            }
        }
 
        le = le->Flink;
    }
 
    for (i = 0; i < BTRFS_NUM_BACKUP_ROOTS - 1; i++) {
        RtlCopyMemory(&Vcb->superblock.backup[i], &Vcb->superblock.backup[i+1], sizeof(superblock_backup));
    }
 
    update_backup_superblock(Vcb, &Vcb->superblock.backup[BTRFS_NUM_BACKUP_ROOTS - 1], Irp);
 
    KeInitializeEvent(&context.Event, NotificationEvent, false);
    InitializeListHead(&context.stripes);
    context.left = 0;
 
    le = Vcb->devices.Flink;
    while (le != &Vcb->devices) {
        device* dev = CONTAINING_RECORD(le, device, list_entry);
 
        if (dev->devobj && !dev->readonly) {
            Status = write_superblock(Vcb, dev, &context);
            if (!NT_SUCCESS(Status)) {
                ERR("write_superblock returned %08lx\n", Status);
                goto end;
            }
        }
 
        le = le->Flink;
    }
 
    if (IsListEmpty(&context.stripes)) {
        ERR("error - not writing any superblocks\n");
        Status = STATUS_INTERNAL_ERROR;
        goto end;
    }
 
    le = context.stripes.Flink;
    while (le != &context.stripes) {
        write_superblocks_stripe* stripe = CONTAINING_RECORD(le, write_superblocks_stripe, list_entry);
 
        IoCallDriver(stripe->device->devobj, stripe->Irp);
 
        le = le->Flink;
    }
 
    KeWaitForSingleObject(&context.Event, Executive, KernelMode, false, NULL);
 
    le = context.stripes.Flink;
    while (le != &context.stripes) {
        write_superblocks_stripe* stripe = CONTAINING_RECORD(le, write_superblocks_stripe, list_entry);
 
        if (!NT_SUCCESS(stripe->Status)) {
            ERR("device %I64x returned %08lx\n", stripe->device->devitem.dev_id, stripe->Status);
            log_device_error(Vcb, stripe->device, BTRFS_DEV_STAT_WRITE_ERRORS);
            Status = stripe->Status;
            goto end;
        }
 
        le = le->Flink;
    }
 
    Status = STATUS_SUCCESS;
 
end:
    while (!IsListEmpty(&context.stripes)) {
        write_superblocks_stripe* stripe = CONTAINING_RECORD(RemoveHeadList(&context.stripes), write_superblocks_stripe, list_entry);
 
        if (stripe->mdl) {
            if (stripe->mdl->MdlFlags & MDL_PAGES_LOCKED)
                MmUnlockPages(stripe->mdl);
 
            IoFreeMdl(stripe->mdl);
        }
 
        if (stripe->Irp)
            IoFreeIrp(stripe->Irp);
 
        if (stripe->buf)
            ExFreePool(stripe->buf);
 
        ExFreePool(stripe);
    }
 
    return Status;
}
 
static NTSTATUS flush_changed_extent(device_extension* Vcb, chunk* c, changed_extent* ce, PIRP Irp, LIST_ENTRY* rollback) {
    LIST_ENTRY *le, *le2;
    NTSTATUS Status;
    uint64_t old_size;
 
    if (ce->count == 0 && ce->old_count == 0) {
        while (!IsListEmpty(&ce->refs)) {
            changed_extent_ref* cer = CONTAINING_RECORD(RemoveHeadList(&ce->refs), changed_extent_ref, list_entry);
            ExFreePool(cer);
        }
 
        while (!IsListEmpty(&ce->old_refs)) {
            changed_extent_ref* cer = CONTAINING_RECORD(RemoveHeadList(&ce->old_refs), changed_extent_ref, list_entry);
            ExFreePool(cer);
        }
 
        goto end;
    }
 
    le = ce->refs.Flink;
    while (le != &ce->refs) {
        changed_extent_ref* cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
        uint32_t old_count = 0;
 
        if (cer->type == TYPE_EXTENT_DATA_REF) {
            le2 = ce->old_refs.Flink;
            while (le2 != &ce->old_refs) {
                changed_extent_ref* cer2 = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
                if (cer2->type == TYPE_EXTENT_DATA_REF && cer2->edr.root == cer->edr.root && cer2->edr.objid == cer->edr.objid && cer2->edr.offset == cer->edr.offset) {
                    old_count = cer2->edr.count;
                    break;
                }
 
                le2 = le2->Flink;
            }
 
            old_size = ce->old_count > 0 ? ce->old_size : ce->size;
 
            if (cer->edr.count > old_count) {
                Status = increase_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset, cer->edr.count - old_count, Irp);
 
                if (!NT_SUCCESS(Status)) {
                    ERR("increase_extent_refcount_data returned %08lx\n", Status);
                    return Status;
                }
            }
        } else if (cer->type == TYPE_SHARED_DATA_REF) {
            le2 = ce->old_refs.Flink;
            while (le2 != &ce->old_refs) {
                changed_extent_ref* cer2 = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
                if (cer2->type == TYPE_SHARED_DATA_REF && cer2->sdr.offset == cer->sdr.offset) {
                    RemoveEntryList(&cer2->list_entry);
                    ExFreePool(cer2);
                    break;
                }
 
                le2 = le2->Flink;
            }
        }
 
        le = le->Flink;
    }
 
    le = ce->refs.Flink;
    while (le != &ce->refs) {
        changed_extent_ref* cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
        LIST_ENTRY* le3 = le->Flink;
        uint32_t old_count = 0;
 
        if (cer->type == TYPE_EXTENT_DATA_REF) {
            le2 = ce->old_refs.Flink;
            while (le2 != &ce->old_refs) {
                changed_extent_ref* cer2 = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
 
                if (cer2->type == TYPE_EXTENT_DATA_REF && cer2->edr.root == cer->edr.root && cer2->edr.objid == cer->edr.objid && cer2->edr.offset == cer->edr.offset) {
                    old_count = cer2->edr.count;
 
                    RemoveEntryList(&cer2->list_entry);
                    ExFreePool(cer2);
                    break;
                }
 
                le2 = le2->Flink;
            }
 
            old_size = ce->old_count > 0 ? ce->old_size : ce->size;
 
            if (cer->edr.count < old_count) {
                Status = decrease_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset,
                                                       old_count - cer->edr.count, ce->superseded, Irp);
 
                if (!NT_SUCCESS(Status)) {
                    ERR("decrease_extent_refcount_data returned %08lx\n", Status);
                    return Status;
                }
            }
 
            if (ce->size != ce->old_size && ce->old_count > 0) {
                KEY searchkey;
                traverse_ptr tp;
                void* data;
 
                searchkey.obj_id = ce->address;
                searchkey.obj_type = TYPE_EXTENT_ITEM;
                searchkey.offset = ce->old_size;
 
                Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("error - find_item returned %08lx\n", Status);
                    return Status;
                }
 
                if (keycmp(searchkey, tp.item->key)) {
                    ERR("could not find (%I64x,%x,%I64x) in extent tree\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
                    return STATUS_INTERNAL_ERROR;
                }
 
                if (tp.item->size > 0) {
                    data = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 
                    if (!data) {
                        ERR("out of memory\n");
                        return STATUS_INSUFFICIENT_RESOURCES;
                    }
 
                    RtlCopyMemory(data, tp.item->data, tp.item->size);
                } else
                    data = NULL;
 
                Status = insert_tree_item(Vcb, Vcb->extent_root, ce->address, TYPE_EXTENT_ITEM, ce->size, data, tp.item->size, NULL, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("insert_tree_item returned %08lx\n", Status);
                    if (data) ExFreePool(data);
                    return Status;
                }
 
                Status = delete_tree_item(Vcb, &tp);
                if (!NT_SUCCESS(Status)) {
                    ERR("delete_tree_item returned %08lx\n", Status);
                    return Status;
                }
            }
        }
 
        RemoveEntryList(&cer->list_entry);
        ExFreePool(cer);
 
        le = le3;
    }
 
#ifdef DEBUG_PARANOID
    if (!IsListEmpty(&ce->old_refs))
        WARN("old_refs not empty\n");
#endif
 
end:
    if (ce->count == 0 && !ce->superseded) {
        c->used -= ce->size;
        space_list_add(c, ce->address, ce->size, rollback);
    }
 
    RemoveEntryList(&ce->list_entry);
    ExFreePool(ce);
 
    return STATUS_SUCCESS;
}
 
void add_checksum_entry(device_extension* Vcb, uint64_t address, ULONG length, void* csum, PIRP Irp) {
    KEY searchkey;
    traverse_ptr tp, next_tp;
    NTSTATUS Status;
    uint64_t startaddr, endaddr;
    ULONG len;
    RTL_BITMAP bmp;
    ULONG* bmparr;
    ULONG runlength, index;
 
    TRACE("(%p, %I64x, %lx, %p, %p)\n", Vcb, address, length, csum, Irp);
 
    searchkey.obj_id = EXTENT_CSUM_ID;
    searchkey.obj_type = TYPE_EXTENT_CSUM;
    searchkey.offset = address;
 
    // FIXME - create checksum_root if it doesn't exist at all
 
    Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
    if (Status == STATUS_NOT_FOUND) { // tree is completely empty
        if (csum) { // not deleted
            ULONG length2 = length;
            uint64_t off = address;
            void* data = csum;
 
            do {
                uint16_t il = (uint16_t)min(length2, MAX_CSUM_SIZE / Vcb->csum_size);
 
                void* checksums = ExAllocatePoolWithTag(PagedPool, il * Vcb->csum_size, ALLOC_TAG);
                if (!checksums) {
                    ERR("out of memory\n");
                    return;
                }
 
                RtlCopyMemory(checksums, data, il * Vcb->csum_size);
 
                Status = insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, off, checksums,
                                          il * Vcb->csum_size, NULL, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("insert_tree_item returned %08lx\n", Status);
                    ExFreePool(checksums);
                    return;
                }
 
                length2 -= il;
 
                if (length2 > 0) {
                    off += (uint64_t)il << Vcb->sector_shift;
                    data = (uint8_t*)data + (il * Vcb->csum_size);
                }
            } while (length2 > 0);
        }
    } else if (!NT_SUCCESS(Status)) {
        ERR("find_item returned %08lx\n", Status);
        return;
    } else {
        uint32_t tplen;
        void* checksums;
 
        // FIXME - check entry is TYPE_EXTENT_CSUM?
 
        if (tp.item->key.offset < address && tp.item->key.offset + (((uint64_t)tp.item->size << Vcb->sector_shift) / Vcb->csum_size) >= address)
            startaddr = tp.item->key.offset;
        else
            startaddr = address;
 
        searchkey.obj_id = EXTENT_CSUM_ID;
        searchkey.obj_type = TYPE_EXTENT_CSUM;
        searchkey.offset = address + (length << Vcb->sector_shift);
 
        Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
        if (!NT_SUCCESS(Status)) {
            ERR("find_item returned %08lx\n", Status);
            return;
        }
 
        tplen = tp.item->size / Vcb->csum_size;
 
        if (tp.item->key.offset + (tplen << Vcb->sector_shift) >= address + (length << Vcb->sector_shift))
            endaddr = tp.item->key.offset + (tplen << Vcb->sector_shift);
        else
            endaddr = address + (length << Vcb->sector_shift);
 
        TRACE("cs starts at %I64x (%lx sectors)\n", address, length);
        TRACE("startaddr = %I64x\n", startaddr);
        TRACE("endaddr = %I64x\n", endaddr);
 
        len = (ULONG)((endaddr - startaddr) >> Vcb->sector_shift);
 
        checksums = ExAllocatePoolWithTag(PagedPool, Vcb->csum_size * len, ALLOC_TAG);
        if (!checksums) {
            ERR("out of memory\n");
            return;
        }
 
        bmparr = ExAllocatePoolWithTag(PagedPool, sizeof(ULONG) * ((len/8)+1), ALLOC_TAG);
        if (!bmparr) {
            ERR("out of memory\n");
            ExFreePool(checksums);
            return;
        }
 
        RtlInitializeBitMap(&bmp, bmparr, len);
        RtlSetAllBits(&bmp);
 
        searchkey.obj_id = EXTENT_CSUM_ID;
        searchkey.obj_type = TYPE_EXTENT_CSUM;
        searchkey.offset = address;
 
        Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
        if (!NT_SUCCESS(Status)) {
            ERR("find_item returned %08lx\n", Status);
            ExFreePool(checksums);
            ExFreePool(bmparr);
            return;
        }
 
        // set bit = free space, cleared bit = allocated sector
 
        while (tp.item->key.offset < endaddr) {
            if (tp.item->key.offset >= startaddr) {
                if (tp.item->size > 0) {
                    ULONG itemlen = (ULONG)min((len - ((tp.item->key.offset - startaddr) >> Vcb->sector_shift)) * Vcb->csum_size, tp.item->size);
 
                    RtlCopyMemory((uint8_t*)checksums + (((tp.item->key.offset - startaddr) * Vcb->csum_size) >> Vcb->sector_shift),
                                  tp.item->data, itemlen);
                    RtlClearBits(&bmp, (ULONG)((tp.item->key.offset - startaddr) >> Vcb->sector_shift), itemlen / Vcb->csum_size);
                }
 
                Status = delete_tree_item(Vcb, &tp);
                if (!NT_SUCCESS(Status)) {
                    ERR("delete_tree_item returned %08lx\n", Status);
                    ExFreePool(checksums);
                    ExFreePool(bmparr);
                    return;
                }
            }
 
            if (find_next_item(Vcb, &tp, &next_tp, false, Irp)) {
                tp = next_tp;
            } else
                break;
        }
 
        if (!csum) { // deleted
            RtlSetBits(&bmp, (ULONG)((address - startaddr) >> Vcb->sector_shift), length);
        } else {
            RtlCopyMemory((uint8_t*)checksums + (((address - startaddr) * Vcb->csum_size) >> Vcb->sector_shift),
                          csum, length * Vcb->csum_size);
            RtlClearBits(&bmp, (ULONG)((address - startaddr) >> Vcb->sector_shift), length);
        }
 
        runlength = RtlFindFirstRunClear(&bmp, &index);
 
        while (runlength != 0) {
            if (index >= len)
                break;
 
            if (index + runlength >= len) {
                runlength = len - index;
 
                if (runlength == 0)
                    break;
            }
 
            do {
                uint16_t rl;
                uint64_t off;
                void* data;
 
                if (runlength * Vcb->csum_size > MAX_CSUM_SIZE)
                    rl = (uint16_t)(MAX_CSUM_SIZE / Vcb->csum_size);
                else
                    rl = (uint16_t)runlength;
 
                data = ExAllocatePoolWithTag(PagedPool, Vcb->csum_size * rl, ALLOC_TAG);
                if (!data) {
                    ERR("out of memory\n");
                    ExFreePool(bmparr);
                    ExFreePool(checksums);
                    return;
                }
 
                RtlCopyMemory(data, (uint8_t*)checksums + (Vcb->csum_size * index), Vcb->csum_size * rl);
 
                off = startaddr + ((uint64_t)index << Vcb->sector_shift);
 
                Status = insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, off, data, Vcb->csum_size * rl, NULL, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("insert_tree_item returned %08lx\n", Status);
                    ExFreePool(data);
                    ExFreePool(bmparr);
                    ExFreePool(checksums);
                    return;
                }
 
                runlength -= rl;
                index += rl;
            } while (runlength > 0);
 
            runlength = RtlFindNextForwardRunClear(&bmp, index, &index);
        }
 
        ExFreePool(bmparr);
        ExFreePool(checksums);
    }
}
 
static NTSTATUS update_chunk_usage(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
    LIST_ENTRY *le = Vcb->chunks.Flink, *le2;
    chunk* c;
    KEY searchkey;
    traverse_ptr tp;
    BLOCK_GROUP_ITEM* bgi;
    NTSTATUS Status;
 
    TRACE("(%p)\n", Vcb);
 
    ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
 
    while (le != &Vcb->chunks) {
        c = CONTAINING_RECORD(le, chunk, list_entry);
 
        acquire_chunk_lock(c, Vcb);
 
        if (!c->cache_loaded && (!IsListEmpty(&c->changed_extents) || c->used != c->oldused)) {
            Status = load_cache_chunk(Vcb, c, NULL);
 
            if (!NT_SUCCESS(Status)) {
                ERR("load_cache_chunk returned %08lx\n", Status);
                release_chunk_lock(c, Vcb);
                goto end;
            }
        }
 
        le2 = c->changed_extents.Flink;
        while (le2 != &c->changed_extents) {
            LIST_ENTRY* le3 = le2->Flink;
            changed_extent* ce = CONTAINING_RECORD(le2, changed_extent, list_entry);
 
            Status = flush_changed_extent(Vcb, c, ce, Irp, rollback);
            if (!NT_SUCCESS(Status)) {
                ERR("flush_changed_extent returned %08lx\n", Status);
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            le2 = le3;
        }
 
        // This is usually done by update_chunks, but we have to check again in case any new chunks
        // have been allocated since.
        if (c->created) {
            Status = create_chunk(Vcb, c, Irp);
            if (!NT_SUCCESS(Status)) {
                ERR("create_chunk returned %08lx\n", Status);
                release_chunk_lock(c, Vcb);
                goto end;
            }
        }
 
        if (c->old_cache) {
            if (c->old_cache->dirty) {
                LIST_ENTRY batchlist;
 
                InitializeListHead(&batchlist);
 
                Status = flush_fcb(c->old_cache, false, &batchlist, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("flush_fcb returned %08lx\n", Status);
                    release_chunk_lock(c, Vcb);
                    clear_batch_list(Vcb, &batchlist);
                    goto end;
                }
 
                Status = commit_batch_list(Vcb, &batchlist, Irp);
                if (!NT_SUCCESS(Status)) {
                    ERR("commit_batch_list returned %08lx\n", Status);
                    release_chunk_lock(c, Vcb);
                    goto end;
                }
            }
 
            free_fcb(c->old_cache);
 
            if (c->old_cache->refcount == 0)
                reap_fcb(c->old_cache);
 
            c->old_cache = NULL;
        }
 
        if (c->used != c->oldused) {
            searchkey.obj_id = c->offset;
            searchkey.obj_type = TYPE_BLOCK_GROUP_ITEM;
            searchkey.offset = c->chunk_item->size;
 
            Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
            if (!NT_SUCCESS(Status)) {
                ERR("error - find_item returned %08lx\n", Status);
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            if (keycmp(searchkey, tp.item->key)) {
                ERR("could not find (%I64x,%x,%I64x) in extent_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
                Status = STATUS_INTERNAL_ERROR;
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            if (tp.item->size < sizeof(BLOCK_GROUP_ITEM)) {
                ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(BLOCK_GROUP_ITEM));
                Status = STATUS_INTERNAL_ERROR;
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            bgi = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
            if (!bgi) {
                ERR("out of memory\n");
                Status = STATUS_INSUFFICIENT_RESOURCES;
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            RtlCopyMemory(bgi, tp.item->data, tp.item->size);
            bgi->used = c->used;
 
#ifdef DEBUG_PARANOID
            if (bgi->used & 0x8000000000000000) {
                ERR("refusing to write BLOCK_GROUP_ITEM with negative usage value (%I64x)\n", bgi->used);
                int3;
            }
#endif
 
            TRACE("adjusting usage of chunk %I64x to %I64x\n", c->offset, c->used);
 
            Status = delete_tree_item(Vcb, &tp);
            if (!NT_SUCCESS(Status)) {
                ERR("delete_tree_item returned %08lx\n", Status);
                ExFreePool(bgi);
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            Status = insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, bgi, tp.item->size, NULL, Irp);
            if (!NT_SUCCESS(Status)) {
                ERR("insert_tree_item returned %08lx\n", Status);
                ExFreePool(bgi);
                release_chunk_lock(c, Vcb);
                goto end;
            }
 
            Vcb->superblock.bytes_used += c->used - c->oldused;
            c->oldused = c->used;
        }
 
        release_chunk_lock(c, Vcb);
 
        le = le->Flink;
    }
 
    Status = STATUS_SUCCESS;
 
end:
    ExReleaseResourceLite(&Vcb->chunk_lock);
 
    return Status;
}
 
static void get_first_item(tree* t, KEY* key) {
    LIST_ENTRY* le;
 
    le = t->itemlist.Flink;
    while (le != &t->itemlist) {
        tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
        *key = td->key;
        return;
    }
}
 
static NTSTATUS split_tree_at(device_extension* Vcb, tree* t, tree_data* newfirstitem, uint32_t numitems, uint32_t size) {
    tree *nt, *pt;
    tree_data* td;
    tree_data* oldlastitem;
 
    TRACE("splitting tree in %I64x at (%I64x,%x,%I64x)\n", t->root->id, newfirstitem->key.obj_id, newfirstitem->key.obj_type, newfirstitem->key.offset);
 
    nt = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
    if (!nt) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    if (t->header.level > 0) {
        nt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
        if (!nt->nonpaged) {
            ERR("out of memory\n");
            ExFreePool(nt);
            return STATUS_INSUFFICIENT_RESOURCES;
        }
 
        ExInitializeFastMutex(&nt->nonpaged->mutex);
    } else
        nt->nonpaged = NULL;
 
    RtlCopyMemory(&nt->header, &t->header, sizeof(tree_header));
    nt->header.address = 0;
    nt->header.generation = Vcb->superblock.generation;
    nt->header.num_items = t->header.num_items - numitems;
    nt->header.flags = HEADER_FLAG_MIXED_BACKREF | HEADER_FLAG_WRITTEN;
 
    nt->has_address = false;
    nt->Vcb = Vcb;
    nt->parent = t->parent;
 
#ifdef DEBUG_PARANOID
    if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
#endif
 
    nt->root = t->root;
    nt->new_address = 0;
    nt->has_new_address = false;
    nt->updated_extents = false;
    nt->uniqueness_determined = true;
    nt->is_unique = true;
    nt->list_entry_hash.Flink = NULL;
    nt->buf = NULL;
    InitializeListHead(&nt->itemlist);
 
    oldlastitem = CONTAINING_RECORD(newfirstitem->list_entry.Blink, tree_data, list_entry);
 
    nt->itemlist.Flink = &newfirstitem->list_entry;
    nt->itemlist.Blink = t->itemlist.Blink;
    nt->itemlist.Flink->Blink = &nt->itemlist;
    nt->itemlist.Blink->Flink = &nt->itemlist;
 
    t->itemlist.Blink = &oldlastitem->list_entry;
    t->itemlist.Blink->Flink = &t->itemlist;
 
    nt->size = t->size - size;
    t->size = size;
    t->header.num_items = numitems;
    nt->write = true;
 
    InsertTailList(&Vcb->trees, &nt->list_entry);
 
    if (nt->header.level > 0) {
        LIST_ENTRY* le = nt->itemlist.Flink;
 
        while (le != &nt->itemlist) {
            tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
 
            if (td2->treeholder.tree) {
                td2->treeholder.tree->parent = nt;
#ifdef DEBUG_PARANOID
                if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
#endif
            }
 
            le = le->Flink;
        }
    } else {
        LIST_ENTRY* le = nt->itemlist.Flink;
 
        while (le != &nt->itemlist) {
            tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
 
            if (!td2->inserted && td2->data) {
                uint8_t* data = ExAllocatePoolWithTag(PagedPool, td2->size, ALLOC_TAG);
 
                if (!data) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }
 
                RtlCopyMemory(data, td2->data, td2->size);
                td2->data = data;
                td2->inserted = true;
            }
 
            le = le->Flink;
        }
    }
 
    if (nt->parent) {
        td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
        if (!td) {
            ERR("out of memory\n");
            return STATUS_INSUFFICIENT_RESOURCES;
        }
 
        td->key = newfirstitem->key;
 
        InsertHeadList(&t->paritem->list_entry, &td->list_entry);
 
        td->ignore = false;
        td->inserted = true;
        td->treeholder.tree = nt;
        nt->paritem = td;
 
        nt->parent->header.num_items++;
        nt->parent->size += sizeof(internal_node);
 
        goto end;
    }
 
    TRACE("adding new tree parent\n");
 
    if (nt->header.level == 255) {
        ERR("cannot add parent to tree at level 255\n");
        return STATUS_INTERNAL_ERROR;
    }
 
    pt = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
    if (!pt) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    pt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
    if (!pt->nonpaged) {
        ERR("out of memory\n");
        ExFreePool(pt);
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    ExInitializeFastMutex(&pt->nonpaged->mutex);
 
    RtlCopyMemory(&pt->header, &nt->header, sizeof(tree_header));
    pt->header.address = 0;
    pt->header.num_items = 2;
    pt->header.level = nt->header.level + 1;
    pt->header.flags = HEADER_FLAG_MIXED_BACKREF | HEADER_FLAG_WRITTEN;
 
    pt->has_address = false;
    pt->Vcb = Vcb;
    pt->parent = NULL;
    pt->paritem = NULL;
    pt->root = t->root;
    pt->new_address = 0;
    pt->has_new_address = false;
    pt->updated_extents = false;
    pt->size = pt->header.num_items * sizeof(internal_node);
    pt->uniqueness_determined = true;
    pt->is_unique = true;
    pt->list_entry_hash.Flink = NULL;
    pt->buf = NULL;
    InitializeListHead(&pt->itemlist);
 
    InsertTailList(&Vcb->trees, &pt->list_entry);
 
    td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
    if (!td) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    get_first_item(t, &td->key);
    td->ignore = false;
    td->inserted = false;
    td->treeholder.address = 0;
    td->treeholder.generation = Vcb->superblock.generation;
    td->treeholder.tree = t;
    InsertTailList(&pt->itemlist, &td->list_entry);
    t->paritem = td;
 
    td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
    if (!td) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }
 
    td->key = newfirstitem->key;
    td->ignore = false;
    td->inserted = false;
    td->treeholder.address = 0;
    td->treeholder.generation = Vcb->superblock.generation;
    td->treeholder.tree = nt;
    InsertTailList(&pt->itemlist, &td->list_entry);
    nt->paritem = td;
 
    pt->write = true;
 
    t->root->treeholder.tree = pt;
 
    t->parent = pt;
    nt->parent = pt;
 
#ifdef DEBUG_PARANOID
    if (t->parent && t->parent->header.level <= t->header.level) int3;
    if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
#endif
 
end:
    t->root->root_item.bytes_used += Vcb->superblock.node_size;
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS split_tree(device_extension* Vcb, tree* t) {
    LIST_ENTRY* le;
    uint32_t size, ds, numitems;
 
    size = 0;
    numitems = 0;
 
    // FIXME - naïve implementation: maximizes number of filled trees
 
    le = t->itemlist.Flink;
    while (le != &t->itemlist) {
        tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
        if (!td->ignore) {
            if (t->header.level == 0)
                ds = sizeof(leaf_node) + td->size;
            else
                ds = sizeof(internal_node);
 
            if (numitems == 0 && ds > Vcb->superblock.node_size - sizeof(tree_header)) {
                ERR("(%I64x,%x,%I64x) in tree %I64x is too large (%x > %Ix)\n",
                    td->key.obj_id, td->key.obj_type, td->key.offset, t->root->id,
                    ds, Vcb->superblock.node_size - sizeof(tree_header));
                return STATUS_INTERNAL_ERROR;
            }
 
            // FIXME - move back if previous item was deleted item with same key
            if (size + ds > Vcb->superblock.node_size - sizeof(tree_header))
                return split_tree_at(Vcb, t, td, numitems, size);
 
            size += ds;
            numitems++;
        }
 
        le = le->Flink;
    }
 
    return STATUS_SUCCESS;
}
 
bool is_tree_unique(device_extension* Vcb, tree* t, PIRP Irp) {
    KEY searchkey;
    traverse_ptr tp;
    NTSTATUS Status;
    bool ret = false;
    EXTENT_ITEM* ei;
    uint8_t* type;
 
    if (t->uniqueness_determined)
        return t->is_unique;
 
    if (t->parent && !is_tree_unique(Vcb, t->parent, Irp))
        goto end;
 
    if (t->has_address) {
        searchkey.obj_id = t->header.address;
        searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
        searchkey.offset = 0xffffffffffffffff;
 
        Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
        if (!NT_SUCCESS(Status)) {
            ERR("error - find_item returned %08lx\n", Status);
            goto end;
        }
 
        if (tp.item->key.obj_id != t->header.address || (tp.item->key.obj_type != TYPE_METADATA_ITEM && tp.item->key.obj_type != TYPE_EXTENT_ITEM))
            goto end;
 
        if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->size == sizeof(EXTENT_ITEM_V0))
            goto end;
 
        if (tp.item->size < sizeof(EXTENT_ITEM))
            goto end;
 
        ei = (EXTENT_ITEM*)tp.item->data;
 
        if (ei->refcount > 1)
            goto end;
 
        if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && ei->flags & EXTENT_ITEM_TREE_BLOCK) {
            EXTENT_ITEM2* ei2;
 
            if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2))
                goto end;
 
            ei2 = (EXTENT_ITEM2*)&ei[1];
            type = (uint8_t*)&ei2[1];
        } else
            type = (uint8_t*)&ei[1];
 
        if (type >= tp.item->data + tp.item->size || *type != TYPE_TREE_BLOCK_REF)
            goto end;
    }
 
    ret = true;
 
end:
    t->is_unique = ret;
    t->uniqueness_determined = true;
 
    return ret;
}
 
static NTSTATUS try_tree_amalgamate(device_extension* Vcb, tree* t, bool* done, bool* done_deletions, PIRP Irp, LIST_ENTRY* rollback) {
    LIST_ENTRY* le;
    tree_data* nextparitem = NULL;
    NTSTATUS Status;
    tree *next_tree, *par;
 
    *done = false;
 
    TRACE("trying to amalgamate tree in root %I64x, level %x (size %u)\n", t->root->id, t->header.level, t->size);
 
    // FIXME - doesn't capture everything, as it doesn't ascend
    le = t->paritem->list_entry.Flink;
    while (le != &t->parent->itemlist) {
        tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
        if (!td->ignore) {
            nextparitem = td;
            break;
        }
 
        le = le->Flink;
    }
 
    if (!nextparitem)
        return STATUS_SUCCESS;
 
    TRACE("nextparitem: key = %I64x,%x,%I64x\n", nextparitem->key.obj_id, nextparitem->key.obj_type, nextparitem->key.offset);
 
    if (!nextparitem->treeholder.tree) {
        Status = do_load_tree(Vcb, &nextparitem->treeholder, t->root, t->parent, nextparitem, NULL);
        if (!NT_SUCCESS(Status)) {
            ERR("do_load_tree returned %08lx\n", Status);
            return Status;
        }
    }
 
    if (!is_tree_unique(Vcb, nextparitem->treeholder.tree, Irp))
        return STATUS_SUCCESS;
 
    next_tree = nextparitem->treeholder.tree;
 
    if (!next_tree->updated_extents && next_tree->has_address) {
        Status = update_tree_extents(Vcb, next_tree, Irp, rollback);
        if (!NT_SUCCESS(Status)) {
            ERR("update_tree_extents returned %08lx\n", Status);
            return Status;
        }
    }
 
    if (t->size + next_tree->size <= Vcb->superblock.node_size - sizeof(tree_header)) {
        // merge two trees into one
 
        t->header.num_items += next_tree->header.num_items;
        t->size += next_tree->size;
 
        if (next_tree->header.level > 0) {
            le = next_tree->itemlist.Flink;
 
            while (le != &next_tree->itemlist) {
                tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (td2->treeholder.tree) {
                    td2->treeholder.tree->parent = t;
#ifdef DEBUG_PARANOID
                    if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
#endif
                }
 
                td2->inserted = true;
                le = le->Flink;
            }
        } else {
            le = next_tree->itemlist.Flink;
 
            while (le != &next_tree->itemlist) {
                tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
 
                if (!td2->inserted && td2->data) {
                    uint8_t* data = ExAllocatePoolWithTag(PagedPool, td2->size, ALLOC_TAG);
 
                    if (!data) {
                        ERR("out of memory\n");
                        return STATUS_INSUFFICIENT_RESOURCES;
                    }
 
                    RtlCopyMemory(data, td2->data, td2->size);
                    td2->data = data;
                    td2->inserted = true;
                }
 
                le = le->Flink;
            }
        }
 
        t->itemlist.Blink->Flink = next_tree->itemlist.Flink;
        t->itemlist.Blink->Flink->Blink = t->itemlist.Blink;
        t->itemlist.Blink = next_tree->itemlist.Blink;
        t->itemlist.Blink->Flink = &t->itemlist;
 
        next_tree->itemlist.Flink = next_tree->itemlist.Blink = &next_tree->itemlist;
 
        next_tree->header.num_items = 0;
        next_tree->size = 0;
 
        if (next_tree->has_new_address) { // delete associated EXTENT_ITEM
            Status = reduce_tree_extent(Vcb, next_tree->new_address, next_tree, next_tree->parent->header.tree_id, next_tree->header.level, Irp, rollback);
 
            if (!NT_SUCCESS(Status)) {
                ERR("reduce_tree_extent returned %08lx\n", Status);
                return Status;
            }
        } else if (next_tree->has_address) {
            Status = reduce_tree_extent(Vcb, next_tree->header.address, next_tree, next_tree->parent->header.tree_id, next_tree->header.level, Irp, rollback);
 
            if (!NT_SUCCESS(Status)) {
                ERR("reduce_tree_extent returned %08lx\n", Status);
                return Status;
            }
        }
 
        if (!nextparitem->ignore) {
            nextparitem->ignore = true;
            next_tree->parent->header.num_items--;
            next_tree->parent->size -= sizeof(internal_node);
 
            *done_deletions = true;
        }
 
        par = next_tree->parent;
        while (par) {
            par->write = true;
            par = par->parent;
        }
 
        RemoveEntryList(&nextparitem->list_entry);
        ExFreePool(next_tree->paritem);
        next_tree->paritem = NULL;
 
        next_tree->root->root_item.bytes_used -= Vcb->superblock.node_size;
 
        free_tree(next_tree);
 
        *done = true;
    } else {
        // rebalance by moving items from second tree into first
        ULONG avg_size = (t->size + next_tree->size) / 2;
        KEY firstitem = {0, 0, 0};
        bool changed = false;
 
        TRACE("attempting rebalance\n");
 
        le = next_tree->itemlist.Flink;
        while (le != &next_tree->itemlist && t->size < avg_size && next_tree->header.num_items > 1) {
            tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
            ULONG size;
 
            if (!td->ignore) {
                if (next_tree->header.level == 0)
                    size = sizeof(leaf_node) + td->size;
                else
                    size = sizeof(internal_node);
            } else
                size = 0;
 
            if (t->size + size < Vcb->superblock.node_size - sizeof(tree_header)) {
                RemoveEntryList(&td->list_entry);
                InsertTailList(&t->itemlist, &td->list_entry);
 
                if (next_tree->header.level > 0 && td->treeholder.tree) {
                    td->treeholder.tree->parent = t;
#ifdef DEBUG_PARANOID
                    if (td->treeholder.tree->parent && td->treeholder.tree->parent->header.level <= td->treeholder.tree->header.level) int3;
#endif
                } else if (next_tree->header.level == 0 && !td->inserted && td->size > 0) {
                    uint8_t* data = ExAllocatePoolWithTag(PagedPool, td->size, ALLOC_TAG);
 
                    if (!data) {
                        ERR("out of memory\n");
                        return STATUS_INSUFFICIENT_RESOURCES;
                    }
 
                    RtlCopyMemory(data, td->data, td->size);
                    td->data = data;
                }
 
                td->inserted = true;
 
                if (!td->ignore) {
                    next_tree->size -= size;
                    t->size += size;
                    next_tree->header.num_items--;
                    t->header.num_items++;
                }
 
                changed = true;
            } else
                break;
 
            le = next_tree->itemlist.Flink;
        }
 
        le = next_tree->itemlist.Flink;
        while (le != &next_tree->itemlist) {
            tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
 
            if (!td->ignore) {
                firstitem = td->key;
                break;
            }
 
            le = le->Flink;
        }
 
        // FIXME - once ascension is working, make this work with parent's parent, etc.
        if (next_tree->paritem)
            next_tree->paritem->key = firstitem;
 
        par = next_tree;
        while (par) {
            par->write = true;
            par = par->parent;
        }
 
        if (changed)
            *done = true;
    }
 
    return STATUS_SUCCESS;
}
 
static NTSTATUS update_extent_level(device_extension* Vcb, uint64_t address, tree* t, uint8_t level, PIRP Irp) {
    KEY searchkey;
    traverse_ptr tp;
    NTSTATUS Status;
 
    if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
        searchkey.obj_id = address;
        searchkey.obj_type = TYPE_METADATA_ITEM;
        searchkey.offset = t->header.level;
 
        Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
        if (!NT_SUCCESS(Status)) {
            ERR("error - find_item returned %08lx\n", Status);
            return Status;
        }
 
        if (!keycmp(tp.item->key, searchkey)) {
            EXTENT_ITEM_SKINNY_METADATA* eism;
 
            if (tp.item->size > 0) {
                eism = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
 
                if (!eism) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }
 
                RtlCopyMemory(eism, tp.item->data, tp.item->size);
            } else
                eism = NULL;
 
            Status = delete_tree_item(Vcb, &tp);
            if (!NT_SUCCESS(Status)) {
                ERR("delete_tree_item returned %08lx\n", Status);
                if (eism) ExFreePool(eism);
                return Status;
            }