treefuncs.c File Reference

#include "btrfs_drv.h"
#include "crc32c.h"

Include dependency graph for treefuncs.c:

Go to the source code of this file.

Functions
	__attribute__ ((nonnull(1, 3, 4, 5)))
	__attribute__ ((nonnull(1, 2, 3, 4)))
	__attribute__ ((nonnull(1, 2, 3)))
	__attribute__ ((nonnull(1)))
	__attribute__ ((nonnull(1, 2)))
	__attribute__ ((nonnull(1, 2, 3, 4, 5)))
	__attribute__ ((nonnull(1, 3)))
	__attribute__ ((nonnull(1, 2, 3, 4, 6, 7)))

Function Documentation

__attribute__() [1/8]

__attribute__

(

(nonnull(1, 3, 4, 5))

)

Definition at line 21 of file treefuncs.c.

                                                                                           {
    tree_header* th;
    tree* t;
    tree_data* td;
    uint8_t h;
    bool inserted;
    LIST_ENTRY* le;

    th = (tree_header*)buf;

    t = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
    if (!t) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }

    if (th->level > 0) {
        t->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
        if (!t->nonpaged) {
            ERR("out of memory\n");
            ExFreePool(t);
            return STATUS_INSUFFICIENT_RESOURCES;
        }

        ExInitializeFastMutex(&t->nonpaged->mutex);
    } else
        t->nonpaged = NULL;

    RtlCopyMemory(&t->header, th, sizeof(tree_header));
    t->hash = calc_crc32c(0xffffffff, (uint8_t*)&addr, sizeof(uint64_t));
    t->has_address = true;
    t->Vcb = Vcb;
    t->parent = NULL;
    t->root = r;
    t->paritem = NULL;
    t->size = 0;
    t->new_address = 0;
    t->has_new_address = false;
    t->updated_extents = false;
    t->write = false;
    t->uniqueness_determined = false;

    InitializeListHead(&t->itemlist);

    if (t->header.level == 0) { // leaf node
        leaf_node* ln = (leaf_node*)(buf + sizeof(tree_header));
        unsigned int i;

        if ((t->header.num_items * sizeof(leaf_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
            ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
            ExFreePool(t);
            return STATUS_INSUFFICIENT_RESOURCES;
        }

        for (i = 0; i < t->header.num_items; i++) {
            td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
            if (!td) {
                ERR("out of memory\n");
                ExFreePool(t);
                return STATUS_INSUFFICIENT_RESOURCES;
            }

            td->key = ln[i].key;

            if (ln[i].size > 0)
                td->data = buf + sizeof(tree_header) + ln[i].offset;
            else
                td->data = NULL;

            if (ln[i].size + sizeof(tree_header) + sizeof(leaf_node) > Vcb->superblock.node_size) {
                ERR("overlarge item in tree %I64x: %u > %Iu\n", addr, ln[i].size, Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
                ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
                ExFreePool(t);
                return STATUS_INTERNAL_ERROR;
            }

            td->size = (uint16_t)ln[i].size;
            td->ignore = false;
            td->inserted = false;

            InsertTailList(&t->itemlist, &td->list_entry);

            t->size += ln[i].size;
        }

        t->size += t->header.num_items * sizeof(leaf_node);
        t->buf = buf;
    } else {
        internal_node* in = (internal_node*)(buf + sizeof(tree_header));
        unsigned int i;

        if ((t->header.num_items * sizeof(internal_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
            ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
            ExFreePool(t);
            return STATUS_INSUFFICIENT_RESOURCES;
        }

        for (i = 0; i < t->header.num_items; i++) {
            td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
            if (!td) {
                ERR("out of memory\n");
                ExFreePool(t);
                return STATUS_INSUFFICIENT_RESOURCES;
            }

            td->key = in[i].key;

            td->treeholder.address = in[i].address;
            td->treeholder.generation = in[i].generation;
            td->treeholder.tree = NULL;
            td->ignore = false;
            td->inserted = false;

            InsertTailList(&t->itemlist, &td->list_entry);
        }

        t->size = t->header.num_items * sizeof(internal_node);
        t->buf = NULL;
    }

    ExAcquireFastMutex(&Vcb->trees_list_mutex);

    InsertTailList(&Vcb->trees, &t->list_entry);

    h = t->hash >> 24;

    if (!Vcb->trees_ptrs[h]) {
        uint8_t h2 = h;

        le = Vcb->trees_hash.Flink;

        if (h2 > 0) {
            h2--;
            do {
                if (Vcb->trees_ptrs[h2]) {
                    le = Vcb->trees_ptrs[h2];
                    break;
                }

                h2--;
            } while (h2 > 0);
        }
    } else
        le = Vcb->trees_ptrs[h];

    inserted = false;
    while (le != &Vcb->trees_hash) {
        tree* t2 = CONTAINING_RECORD(le, tree, list_entry_hash);

        if (t2->hash >= t->hash) {
            InsertHeadList(le->Blink, &t->list_entry_hash);
            inserted = true;
            break;
        }

        le = le->Flink;
    }

    if (!inserted)
        InsertTailList(&Vcb->trees_hash, &t->list_entry_hash);

    if (!Vcb->trees_ptrs[h] || t->list_entry_hash.Flink == Vcb->trees_ptrs[h])
        Vcb->trees_ptrs[h] = &t->list_entry_hash;

    ExReleaseFastMutex(&Vcb->trees_list_mutex);

    TRACE("returning %p\n", t);

    *pt = t;

    return STATUS_SUCCESS;
}

__attribute__() [2/8]

__attribute__

(

(nonnull(1, 2, 3, 4))

)

Definition at line 195 of file treefuncs.c.

                                                                                                                     {
    if (!th->tree) {
        NTSTATUS Status;
        tree* nt;

        Status = load_tree(Vcb, th->address, buf, r, &nt);
        if (!NT_SUCCESS(Status)) {
            ERR("load_tree returned %08lx\n", Status);
            return Status;
        }

        nt->parent = t;

#ifdef DEBUG_PARANOID
        if (t && t->header.level <= nt->header.level) int3;
#endif

        nt->paritem = td;

        th->tree = nt;
    }

    return STATUS_SUCCESS;
}

__attribute__() [3/8]

__attribute__

(

(nonnull(1, 2, 3))

)

Definition at line 221 of file treefuncs.c.

                                                                                                         {
    NTSTATUS Status;
    uint8_t* buf;
    chunk* c;

    buf = ExAllocatePoolWithTag(PagedPool, Vcb->superblock.node_size, ALLOC_TAG);
    if (!buf) {
        ERR("out of memory\n");
        return STATUS_INSUFFICIENT_RESOURCES;
    }

    Status = read_data(Vcb, th->address, Vcb->superblock.node_size, NULL, true, buf, NULL,
                       &c, Irp, th->generation, false, NormalPagePriority);
    if (!NT_SUCCESS(Status)) {
        ERR("read_data returned 0x%08lx\n", Status);
        ExFreePool(buf);
        return Status;
    }

    if (t)
        ExAcquireFastMutex(&t->nonpaged->mutex);
    else
        ExAcquireResourceExclusiveLite(&r->nonpaged->load_tree_lock, true);

    Status = do_load_tree2(Vcb, th, buf, r, t, td);

    if (t)
        ExReleaseFastMutex(&t->nonpaged->mutex);
    else
        ExReleaseResourceLite(&r->nonpaged->load_tree_lock);

    if (!th->tree || th->tree->buf != buf)
        ExFreePool(buf);

    if (!NT_SUCCESS(Status)) {
        ERR("do_load_tree2 returned %08lx\n", Status);
        return Status;
    }

    return Status;
}

__attribute__() [4/8]

__attribute__

(

(nonnull(1))

)

Definition at line 264 of file treefuncs.c.

                        {
    tree* par;
    root* r = t->root;

    // No need to acquire lock, as this is only ever called while Vcb->tree_lock held exclusively

    par = t->parent;

    if (r && r->treeholder.tree != t)
        r = NULL;

    if (par) {
        if (t->paritem)
            t->paritem->treeholder.tree = NULL;
    }

    while (!IsListEmpty(&t->itemlist)) {
        tree_data* td = CONTAINING_RECORD(RemoveHeadList(&t->itemlist), tree_data, list_entry);

        if (t->header.level == 0 && td->data && td->inserted)
            ExFreePool(td->data);

        ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
    }

    RemoveEntryList(&t->list_entry);

    if (r)
        r->treeholder.tree = NULL;

    if (t->list_entry_hash.Flink) {
        uint8_t h = t->hash >> 24;
        if (t->Vcb->trees_ptrs[h] == &t->list_entry_hash) {
            if (t->list_entry_hash.Flink != &t->Vcb->trees_hash) {
                tree* t2 = CONTAINING_RECORD(t->list_entry_hash.Flink, tree, list_entry_hash);

                if ((t2->hash >> 24) == h)
                    t->Vcb->trees_ptrs[h] = &t2->list_entry_hash;
                else
                    t->Vcb->trees_ptrs[h] = NULL;
            } else
                t->Vcb->trees_ptrs[h] = NULL;
        }

        RemoveEntryList(&t->list_entry_hash);
    }

    if (t->buf)
        ExFreePool(t->buf);

    if (t->nonpaged)
        ExFreePool(t->nonpaged);

    ExFreePool(t);
}

__attribute__() [5/8]

__attribute__

(

(nonnull(1, 2))

)

Definition at line 331 of file treefuncs.c.

                                                             {
    LIST_ENTRY* le = td->list_entry.Blink;

    if (le == &t->itemlist)
        return NULL;

    return CONTAINING_RECORD(le, tree_data, list_entry);
}

__attribute__() [6/8]

__attribute__

(

(nonnull(1, 2, 3, 4, 5))

)

Definition at line 377 of file treefuncs.c.

                                                                                                                    {
    NTSTATUS Status;
    tree *t1, *t2;
    tree_data *td1, *td2;

    t1 = tp->tree;
    t2 = tp2->tree;

    do {
        td1 = t1->paritem;
        td2 = t2->paritem;
        t1 = t1->parent;
        t2 = t2->parent;
    } while (t1 && t2 && t1->header.address == t2->header.address);

    while (true) {
        traverse_ptr tp3, tp4;

        Status = next_item2(Vcb, t1, td1, &tp3);
        if (Status == STATUS_NOT_FOUND)
            *ended1 = true;
        else if (!NT_SUCCESS(Status)) {
            ERR("next_item2 returned %08lx\n", Status);
            return Status;
        }

        Status = next_item2(Vcb, t2, td2, &tp4);
        if (Status == STATUS_NOT_FOUND)
            *ended2 = true;
        else if (!NT_SUCCESS(Status)) {
            ERR("next_item2 returned %08lx\n", Status);
            return Status;
        }

        if (*ended1 || *ended2) {
            if (!*ended1) {
                Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
                if (!NT_SUCCESS(Status)) {
                    ERR("find_item returned %08lx\n", Status);
                    return Status;
                }
            } else if (!*ended2) {
                Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
                if (!NT_SUCCESS(Status)) {
                    ERR("find_item returned %08lx\n", Status);
                    return Status;
                }
            }

            return STATUS_SUCCESS;
        }

        if (tp3.tree->header.address != tp4.tree->header.address) {
            Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
            if (!NT_SUCCESS(Status)) {
                ERR("find_item returned %08lx\n", Status);
                return Status;
            }

            Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
            if (!NT_SUCCESS(Status)) {
                ERR("find_item returned %08lx\n", Status);
                return Status;
            }

            return STATUS_SUCCESS;
        }

        t1 = tp3.tree;
        td1 = tp3.item;
        t2 = tp4.tree;
        td2 = tp4.item;
    }
}

__attribute__() [7/8]

__attribute__

(

(nonnull(1, 3))

)

Definition at line 860 of file treefuncs.c.

                                                                                                            {
    rollback_item* ri;

    ri = ExAllocatePoolWithTag(PagedPool, sizeof(rollback_item), ALLOC_TAG);
    if (!ri) {
        ERR("out of memory\n");
        return;
    }

    ri->type = type;
    ri->ptr = ptr;
    InsertTailList(rollback, &ri->list_entry);
}

__attribute__() [8/8]

__attribute__

(

(nonnull(1, 2, 3, 4, 6, 7))

)

Definition at line 1317 of file treefuncs.c.

                                                                                                                                                            {
    if (bi->operation == Batch_Delete || bi->operation == Batch_SetXattr || bi->operation == Batch_DirItem || bi->operation == Batch_InodeRef ||
        bi->operation == Batch_InodeExtRef || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
        bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) {
        uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));

        switch (bi->operation) {
            case Batch_SetXattr: {
                if (td->size < sizeof(DIR_ITEM)) {
                    ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %Iu\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset, td->size, sizeof(DIR_ITEM));
                } else {
                    uint8_t* newdata;
                    ULONG size = td->size;
                    DIR_ITEM* newxa = (DIR_ITEM*)bi->data;
                    DIR_ITEM* xa = (DIR_ITEM*)td->data;

                    while (true) {
                        ULONG oldxasize;

                        if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
                            ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
                            break;
                        }

                        oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;

                        if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) {
                            uint64_t pos;

                            // replace

                            if (td->size + bi->datalen - oldxasize > maxlen)
                                ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->size, bi->datalen, oldxasize, maxlen);

                            newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG);
                            if (!newdata) {
                                ERR("out of memory\n");
                                return STATUS_INSUFFICIENT_RESOURCES;
                            }

                            pos = (uint8_t*)xa - td->data;
                            if (pos + oldxasize < td->size) // copy after changed xattr
                                RtlCopyMemory(newdata + pos + bi->datalen, td->data + pos + oldxasize, (ULONG)(td->size - pos - oldxasize));

                            if (pos > 0) { // copy before changed xattr
                                RtlCopyMemory(newdata, td->data, (ULONG)pos);
                                xa = (DIR_ITEM*)(newdata + pos);
                            } else
                                xa = (DIR_ITEM*)newdata;

                            RtlCopyMemory(xa, bi->data, bi->datalen);

                            bi->datalen = (uint16_t)min(td->size + bi->datalen - oldxasize, maxlen);

                            ExFreePool(bi->data);
                            bi->data = newdata;

                            break;
                        }

                        if ((uint8_t*)xa - (uint8_t*)td->data + oldxasize >= size) {
                            // not found, add to end of data

                            if (td->size + bi->datalen > maxlen)
                                ERR("DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->size, bi->datalen, maxlen);

                            newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
                            if (!newdata) {
                                ERR("out of memory\n");
                                return STATUS_INSUFFICIENT_RESOURCES;
                            }

                            RtlCopyMemory(newdata, td->data, td->size);

                            xa = (DIR_ITEM*)((uint8_t*)newdata + td->size);
                            RtlCopyMemory(xa, bi->data, bi->datalen);

                            bi->datalen = min(bi->datalen + td->size, maxlen);

                            ExFreePool(bi->data);
                            bi->data = newdata;

                            break;
                        } else {
                            xa = (DIR_ITEM*)&xa->name[xa->m + xa->n];
                            size -= oldxasize;
                        }
                    }
                }
                break;
            }

            case Batch_DirItem: {
                uint8_t* newdata;

                if (td->size + bi->datalen > maxlen) {
                    ERR("DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
                    return STATUS_INTERNAL_ERROR;
                }

                newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
                if (!newdata) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }

                RtlCopyMemory(newdata, td->data, td->size);

                RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);

                bi->datalen += td->size;

                ExFreePool(bi->data);
                bi->data = newdata;

                break;
            }

            case Batch_InodeRef: {
                uint8_t* newdata;

                if (td->size + bi->datalen > maxlen) {
                    if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
                        INODE_REF* ir = (INODE_REF*)bi->data;
                        INODE_EXTREF* ier;
                        uint16_t ierlen;
                        batch_item* bi2;
                        LIST_ENTRY* le;
                        bool inserted = false;

                        TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n");

                        ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n);

                        ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG);
                        if (!ier) {
                            ERR("out of memory\n");
                            return STATUS_INSUFFICIENT_RESOURCES;
                        }

                        ier->dir = bi->key.offset;
                        ier->index = ir->index;
                        ier->n = ir->n;
                        RtlCopyMemory(ier->name, ir->name, ier->n);

                        bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
                        if (!bi2) {
                            ERR("out of memory\n");
                            ExFreePool(ier);
                            return STATUS_INSUFFICIENT_RESOURCES;
                        }

                        bi2->key.obj_id = bi->key.obj_id;
                        bi2->key.obj_type = TYPE_INODE_EXTREF;
                        bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n);
                        bi2->data = ier;
                        bi2->datalen = ierlen;
                        bi2->operation = Batch_InodeExtRef;

                        le = bi->list_entry.Flink;
                        while (le != listhead) {
                            batch_item* bi3 = CONTAINING_RECORD(le, batch_item, list_entry);

                            if (keycmp(bi3->key, bi2->key) != -1) {
                                InsertHeadList(le->Blink, &bi2->list_entry);
                                inserted = true;
                            }

                            le = le->Flink;
                        }

                        if (!inserted)
                            InsertTailList(listhead, &bi2->list_entry);

                        *ignore = true;
                        return STATUS_SUCCESS;
                    } else {
                        ERR("INODE_REF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
                        return STATUS_INTERNAL_ERROR;
                    }
                }

                newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
                if (!newdata) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }

                RtlCopyMemory(newdata, td->data, td->size);

                RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);

                bi->datalen += td->size;

                ExFreePool(bi->data);
                bi->data = newdata;

                break;
            }

            case Batch_InodeExtRef: {
                uint8_t* newdata;

                if (td->size + bi->datalen > maxlen) {
                    ERR("INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
                    return STATUS_INTERNAL_ERROR;
                }

                newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
                if (!newdata) {
                    ERR("out of memory\n");
                    return STATUS_INSUFFICIENT_RESOURCES;
                }

                RtlCopyMemory(newdata, td->data, td->size);

                RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);

                bi->datalen += td->size;

                ExFreePool(bi->data);
                bi->data = newdata;

                break;
            }

            case Batch_DeleteDirItem: {
                if (td->size < sizeof(DIR_ITEM)) {
                    ERR("DIR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
                    return STATUS_INTERNAL_ERROR;
                } else {
                    DIR_ITEM *di, *deldi;
                    LONG len;

                    deldi = (DIR_ITEM*)bi->data;
                    di = (DIR_ITEM*)td->data;
                    len = td->size;

                    do {
                        if (di->m == deldi->m && di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n + di->m) == di->n + di->m) {
                            uint16_t newlen = td->size - (sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m);

                            if (newlen == 0) {
                                TRACE("deleting DIR_ITEM\n");
                            } else {
                                uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
                                tree_data* td2;

                                if (!newdi) {
                                    ERR("out of memory\n");
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                TRACE("modifying DIR_ITEM\n");

                                if ((uint8_t*)di > td->data) {
                                    RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
                                    dioff = newdi + ((uint8_t*)di - td->data);
                                } else {
                                    dioff = newdi;
                                }

                                if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
                                    RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));

                                td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
                                if (!td2) {
                                    ERR("out of memory\n");
                                    ExFreePool(newdi);
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                td2->key = bi->key;
                                td2->size = newlen;
                                td2->data = newdi;
                                td2->ignore = false;
                                td2->inserted = true;

                                InsertHeadList(td->list_entry.Blink, &td2->list_entry);

                                t->header.num_items++;
                                t->size += newlen + sizeof(leaf_node);
                                t->write = true;
                            }

                            break;
                        }

                        len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
                        di = (DIR_ITEM*)&di->name[di->n + di->m];

                        if (len == 0) {
                            TRACE("could not find DIR_ITEM to delete\n");
                            *ignore = true;
                            return STATUS_SUCCESS;
                        }
                    } while (len > 0);
                }
                break;
            }

            case Batch_DeleteInodeRef: {
                if (td->size < sizeof(INODE_REF)) {
                    ERR("INODE_REF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_REF));
                    return STATUS_INTERNAL_ERROR;
                } else {
                    INODE_REF *ir, *delir;
                    ULONG len;
                    bool changed = false;

                    delir = (INODE_REF*)bi->data;
                    ir = (INODE_REF*)td->data;
                    len = td->size;

                    do {
                        uint16_t itemlen;

                        if (len < sizeof(INODE_REF) || len < offsetof(INODE_REF, name[0]) + ir->n) {
                            ERR("INODE_REF was truncated\n");
                            break;
                        }

                        itemlen = (uint16_t)offsetof(INODE_REF, name[0]) + ir->n;

                        if (ir->n == delir->n && RtlCompareMemory(ir->name, delir->name, ir->n) == ir->n) {
                            uint16_t newlen = td->size - itemlen;

                            changed = true;

                            if (newlen == 0)
                                TRACE("deleting INODE_REF\n");
                            else {
                                uint8_t *newir = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *iroff;
                                tree_data* td2;

                                if (!newir) {
                                    ERR("out of memory\n");
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                TRACE("modifying INODE_REF\n");

                                if ((uint8_t*)ir > td->data) {
                                    RtlCopyMemory(newir, td->data, (uint8_t*)ir - td->data);
                                    iroff = newir + ((uint8_t*)ir - td->data);
                                } else {
                                    iroff = newir;
                                }

                                if ((uint8_t*)&ir->name[ir->n] < td->data + td->size)
                                    RtlCopyMemory(iroff, &ir->name[ir->n], td->size - ((uint8_t*)&ir->name[ir->n] - td->data));

                                td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
                                if (!td2) {
                                    ERR("out of memory\n");
                                    ExFreePool(newir);
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                td2->key = bi->key;
                                td2->size = newlen;
                                td2->data = newir;
                                td2->ignore = false;
                                td2->inserted = true;

                                InsertHeadList(td->list_entry.Blink, &td2->list_entry);

                                t->header.num_items++;
                                t->size += newlen + sizeof(leaf_node);
                                t->write = true;
                            }

                            break;
                        }

                        if (len > itemlen) {
                            len -= itemlen;
                            ir = (INODE_REF*)&ir->name[ir->n];
                        } else
                            break;
                    } while (len > 0);

                    if (!changed) {
                        if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
                            TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");

                            add_delete_inode_extref(Vcb, bi, listhead);

                            *ignore = true;
                            return STATUS_SUCCESS;
                        } else
                            WARN("entry not found in INODE_REF\n");
                    }
                }

                break;
            }

            case Batch_DeleteInodeExtRef: {
                if (td->size < sizeof(INODE_EXTREF)) {
                    ERR("INODE_EXTREF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_EXTREF));
                    return STATUS_INTERNAL_ERROR;
                } else {
                    INODE_EXTREF *ier, *delier;
                    ULONG len;

                    delier = (INODE_EXTREF*)bi->data;
                    ier = (INODE_EXTREF*)td->data;
                    len = td->size;

                    do {
                        uint16_t itemlen;

                        if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) {
                            ERR("INODE_REF was truncated\n");
                            break;
                        }

                        itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n;

                        if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) {
                            uint16_t newlen = td->size - itemlen;

                            if (newlen == 0)
                                TRACE("deleting INODE_EXTREF\n");
                            else {
                                uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff;
                                tree_data* td2;

                                if (!newier) {
                                    ERR("out of memory\n");
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                TRACE("modifying INODE_EXTREF\n");

                                if ((uint8_t*)ier > td->data) {
                                    RtlCopyMemory(newier, td->data, (uint8_t*)ier - td->data);
                                    ieroff = newier + ((uint8_t*)ier - td->data);
                                } else {
                                    ieroff = newier;
                                }

                                if ((uint8_t*)&ier->name[ier->n] < td->data + td->size)
                                    RtlCopyMemory(ieroff, &ier->name[ier->n], td->size - ((uint8_t*)&ier->name[ier->n] - td->data));

                                td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
                                if (!td2) {
                                    ERR("out of memory\n");
                                    ExFreePool(newier);
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                td2->key = bi->key;
                                td2->size = newlen;
                                td2->data = newier;
                                td2->ignore = false;
                                td2->inserted = true;

                                InsertHeadList(td->list_entry.Blink, &td2->list_entry);

                                t->header.num_items++;
                                t->size += newlen + sizeof(leaf_node);
                                t->write = true;
                            }

                            break;
                        }

                        if (len > itemlen) {
                            len -= itemlen;
                            ier = (INODE_EXTREF*)&ier->name[ier->n];
                        } else
                            break;
                    } while (len > 0);
                }
                break;
            }

            case Batch_DeleteXattr: {
                if (td->size < sizeof(DIR_ITEM)) {
                    ERR("XATTR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
                    return STATUS_INTERNAL_ERROR;
                } else {
                    DIR_ITEM *di, *deldi;
                    LONG len;

                    deldi = (DIR_ITEM*)bi->data;
                    di = (DIR_ITEM*)td->data;
                    len = td->size;

                    do {
                        if (di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n) == di->n) {
                            uint16_t newlen = td->size - ((uint16_t)offsetof(DIR_ITEM, name[0]) + di->n + di->m);

                            if (newlen == 0)
                                TRACE("deleting XATTR_ITEM\n");
                            else {
                                uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
                                tree_data* td2;

                                if (!newdi) {
                                    ERR("out of memory\n");
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                TRACE("modifying XATTR_ITEM\n");

                                if ((uint8_t*)di > td->data) {
                                    RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
                                    dioff = newdi + ((uint8_t*)di - td->data);
                                } else
                                    dioff = newdi;

                                if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
                                    RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));

                                td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
                                if (!td2) {
                                    ERR("out of memory\n");
                                    ExFreePool(newdi);
                                    return STATUS_INSUFFICIENT_RESOURCES;
                                }

                                td2->key = bi->key;
                                td2->size = newlen;
                                td2->data = newdi;
                                td2->ignore = false;
                                td2->inserted = true;

                                InsertHeadList(td->list_entry.Blink, &td2->list_entry);

                                t->header.num_items++;
                                t->size += newlen + sizeof(leaf_node);
                                t->write = true;
                            }

                            break;
                        }

                        len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
                        di = (DIR_ITEM*)&di->name[di->n + di->m];

                        if (len == 0) {
                            TRACE("could not find DIR_ITEM to delete\n");
                            *ignore = true;
                            return STATUS_SUCCESS;
                        }
                    } while (len > 0);
                }
                break;
            }

            case Batch_Delete:
                break;

            default:
                ERR("unexpected batch operation type\n");
                return STATUS_INTERNAL_ERROR;
        }

        // delete old item
        if (!td->ignore) {
            td->ignore = true;

            t->header.num_items--;
            t->size -= sizeof(leaf_node) + td->size;
            t->write = true;
        }

        if (newtd) {
            newtd->data = bi->data;
            newtd->size = bi->datalen;
            InsertHeadList(td->list_entry.Blink, &newtd->list_entry);
        }
    } else {
        ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
        return STATUS_INTERNAL_ERROR;
    }

    *ignore = false;
    return STATUS_SUCCESS;
}