33 ERR(
"out of memory\n");
40 ERR(
"out of memory\n");
51 t->has_address =
true;
58 t->has_new_address =
false;
59 t->updated_extents =
false;
61 t->uniqueness_determined =
false;
65 if (
t->header.level == 0) {
70 ERR(
"tree at %I64x has more items than expected (%x)\n",
addr,
t->header.num_items);
75 for (
i = 0;
i <
t->header.num_items;
i++) {
76 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
78 ERR(
"out of memory\n");
92 ExFreeToPagedLookasideList(&
t->Vcb->tree_data_lookaside, td);
106 t->size +=
t->header.num_items *
sizeof(
leaf_node);
113 ERR(
"tree at %I64x has more items than expected (%x)\n",
addr,
t->header.num_items);
118 for (
i = 0;
i <
t->header.num_items;
i++) {
119 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
121 ERR(
"out of memory\n");
147 if (!
Vcb->trees_ptrs[
h]) {
150 le =
Vcb->trees_hash.Flink;
155 if (
Vcb->trees_ptrs[h2]) {
156 le =
Vcb->trees_ptrs[h2];
164 le =
Vcb->trees_ptrs[
h];
167 while (le != &
Vcb->trees_hash) {
170 if (t2->
hash >=
t->hash) {
182 if (!
Vcb->trees_ptrs[
h] ||
t->list_entry_hash.Flink ==
Vcb->trees_ptrs[
h])
183 Vcb->trees_ptrs[
h] = &
t->list_entry_hash;
187 TRACE(
"returning %p\n",
t);
201 ERR(
"load_tree returned %08lx\n",
Status);
207 #ifdef DEBUG_PARANOID 208 if (
t &&
t->header.level <=
nt->header.level)
int3;
226 ERR(
"out of memory\n");
233 ERR(
"read_data returned 0x%08lx\n",
Status);
254 ERR(
"do_load_tree2 returned %08lx\n",
Status);
269 if (
r &&
r->treeholder.tree !=
t)
274 t->paritem->treeholder.tree =
NULL;
283 ExFreeToPagedLookasideList(&
t->Vcb->tree_data_lookaside, td);
289 r->treeholder.tree =
NULL;
291 if (
t->list_entry_hash.Flink) {
293 if (
t->Vcb->trees_ptrs[
h] == &
t->list_entry_hash) {
294 if (
t->list_entry_hash.Flink != &
t->Vcb->trees_hash) {
297 if ((t2->
hash >> 24) ==
h)
300 t->Vcb->trees_ptrs[
h] =
NULL;
302 t->Vcb->trees_ptrs[
h] =
NULL;
320 if (le == &
t->itemlist)
329 if (le == &
t->itemlist)
338 if (le == &
t->itemlist)
391 ERR(
"next_item2 returned %08lx\n",
Status);
399 ERR(
"next_item2 returned %08lx\n",
Status);
403 if (*ended1 || *ended2) {
407 ERR(
"find_item returned %08lx\n",
Status);
410 }
else if (!*ended2) {
413 ERR(
"find_item returned %08lx\n",
Status);
424 ERR(
"find_item returned %08lx\n",
Status);
430 ERR(
"find_item returned %08lx\n",
Status);
481 }
while (td &&
cmp == 1);
483 if ((
cmp == -1 || !td) && lasttd)
486 if (
t->header.level == 0) {
529 if (
t->header.level <=
level) {
538 ERR(
"do_load_tree returned %08lx\n",
Status);
553 if (!
r->treeholder.tree) {
556 ERR(
"do_load_tree returned %08lx\n",
Status);
563 ERR(
"find_item_in_tree returned %08lx\n",
Status);
572 if (!
r->treeholder.tree) {
575 ERR(
"do_load_tree returned %08lx\n",
Status);
582 ERR(
"find_item_in_tree returned %08lx\n",
Status);
609 #ifdef DEBUG_PARANOID 611 ERR(
"error - returning ignored item\n");
639 ERR(
"do_load_tree returned %08lx\n",
Status);
646 while (
t->header.level != 0) {
654 ERR(
"do_load_tree returned %08lx\n",
Status);
680 #ifdef DEBUG_PARANOID 682 ERR(
"error - returning ignored item\n");
693 if (le == &
t->itemlist)
716 while (
t && (!
t->parent || !
prev_item(
t->parent,
t->paritem))) {
728 ERR(
"do_load_tree returned %08lx\n",
Status);
735 while (
t->header.level != 0) {
740 if (!
li->treeholder.tree) {
743 ERR(
"do_load_tree returned %08lx\n",
Status);
748 t =
li->treeholder.tree;
764 le =
Vcb->trees.Flink;
766 while (le != &
Vcb->trees) {
771 if (
t->header.level ==
level) {
772 bool top = !
t->paritem;
777 if (
top &&
r->treeholder.tree ==
t)
778 r->treeholder.tree =
NULL;
782 }
else if (
t->header.level >
level)
801 le =
Vcb->trees.Flink;
803 while (le != &
Vcb->trees) {
808 if (
t->header.level ==
level) {
809 bool top = !
t->paritem;
814 if (
top &&
r->treeholder.tree ==
t)
815 r->treeholder.tree =
NULL;
819 }
else if (
t->header.level >
level)
834 #pragma warning(push) 835 #pragma warning(suppress: 28194) 842 ERR(
"out of memory\n");
855 #pragma warning(push) 856 #pragma warning(suppress: 28194) 868 KEY firstitem = {0xcccccccccccccccc,0xcc,0xcccccccccccccccc};
872 TRACE(
"(%p, %p, %I64x, %x, %I64x, %p, %x, %p)\n",
Vcb,
r, obj_id, obj_type,
offset,
data,
size, ptp);
874 searchkey.
obj_id = obj_id;
881 if (!
r->treeholder.tree) {
884 ERR(
"do_load_tree returned %08lx\n",
Status);
889 if (
r->treeholder.tree &&
r->treeholder.tree->header.num_items == 0) {
893 ERR(
"error: unable to load tree for root %I64x\n",
r->id);
897 ERR(
"error: find_item returned %08lx\n",
Status);
901 ERR(
"find_item returned %08lx\n",
Status);
912 ERR(
"error: key (%I64x,%x,%I64x) already present\n", obj_id, obj_type,
offset);
913 #ifdef DEBUG_PARANOID 921 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
923 ERR(
"out of memory\n");
937 firstitem = td2->
key;
941 TRACE(
"inserting %I64x,%x,%I64x into tree beginning %I64x,%x,%I64x (num_items %x)\n", obj_id, obj_type,
offset, firstitem.
obj_id, firstitem.
obj_type, firstitem.
offset,
tp.
tree->
header.
num_items);
950 paritem->
key = searchkey;
966 Vcb->need_write =
true;
974 if (
t->paritem &&
t->paritem->ignore) {
976 t->parent->header.num_items++;
980 t->header.generation =
Vcb->superblock.generation;
996 #ifdef DEBUG_PARANOID 1008 Vcb->need_write =
true;
1018 gen =
tp->
tree->
Vcb->superblock.generation;
1077 ERR(
"update_changed_extent_ref returned %08lx\n",
Status);
1106 ERR(
"update_changed_extent_ref returned %08lx\n",
Status);
1192 if (
pi->list_entry.Flink != &
p->parent->itemlist) {
1195 *tree_end = td->
key;
1213 ExFreeToPagedLookasideList(&
Vcb->batch_item_lookaside, bi);
1226 TRACE(
"entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1228 bi2 = ExAllocateFromPagedLookasideList(&
Vcb->batch_item_lookaside);
1230 ERR(
"out of memory\n");
1236 ERR(
"out of memory\n");
1242 ier->index = delir->
index;
1254 while (le != listhead) {
1292 oldxasize =
sizeof(
DIR_ITEM) - 1 + xa->m + xa->n;
1300 ERR(
"DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->
size, bi->
datalen, oldxasize, maxlen);
1304 ERR(
"out of memory\n");
1332 ERR(
"DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->
size, bi->
datalen, maxlen);
1336 ERR(
"out of memory\n");
1352 xa = (
DIR_ITEM*)&xa->name[xa->m + xa->n];
1364 ERR(
"DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->
size, bi->
datalen, maxlen);
1370 ERR(
"out of memory\n");
1396 bool inserted =
false;
1398 TRACE(
"INODE_REF would be too long, adding INODE_EXTREF instead\n");
1404 ERR(
"out of memory\n");
1409 ier->index = ir->
index;
1413 bi2 = ExAllocateFromPagedLookasideList(&
Vcb->batch_item_lookaside);
1415 ERR(
"out of memory\n");
1424 bi2->datalen = ierlen;
1428 while (le != listhead) {
1445 ERR(
"INODE_REF would be over maximum size (%u + %u > %u)\n", td->
size, bi->
datalen, maxlen);
1452 ERR(
"out of memory\n");
1472 ERR(
"INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->
size, bi->
datalen, maxlen);
1478 ERR(
"out of memory\n");
1496 ERR(
"DIR_ITEM was %u bytes, expected at least %Iu\n", td->
size,
sizeof(
DIR_ITEM));
1511 TRACE(
"deleting DIR_ITEM\n");
1517 ERR(
"out of memory\n");
1521 TRACE(
"modifying DIR_ITEM\n");
1533 td2 = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
1535 ERR(
"out of memory\n");
1548 t->header.num_items++;
1560 TRACE(
"could not find DIR_ITEM to delete\n");
1571 ERR(
"INODE_REF was %u bytes, expected at least %Iu\n", td->
size,
sizeof(
INODE_REF));
1576 bool changed =
false;
1586 ERR(
"INODE_REF was truncated\n");
1598 TRACE(
"deleting INODE_REF\n");
1604 ERR(
"out of memory\n");
1608 TRACE(
"modifying INODE_REF\n");
1620 td2 = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
1622 ERR(
"out of memory\n");
1635 t->header.num_items++;
1643 if (
len > itemlen) {
1652 TRACE(
"entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1659 WARN(
"entry not found in INODE_REF\n");
1668 ERR(
"INODE_EXTREF was %u bytes, expected at least %Iu\n", td->
size,
sizeof(
INODE_EXTREF));
1682 ERR(
"INODE_REF was truncated\n");
1692 TRACE(
"deleting INODE_EXTREF\n");
1698 ERR(
"out of memory\n");
1702 TRACE(
"modifying INODE_EXTREF\n");
1714 td2 = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
1716 ERR(
"out of memory\n");
1729 t->header.num_items++;
1737 if (
len > itemlen) {
1749 ERR(
"XATTR_ITEM was %u bytes, expected at least %Iu\n", td->
size,
sizeof(
DIR_ITEM));
1764 TRACE(
"deleting XATTR_ITEM\n");
1770 ERR(
"out of memory\n");
1774 TRACE(
"modifying XATTR_ITEM\n");
1785 td2 = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
1787 ERR(
"out of memory\n");
1800 t->header.num_items++;
1812 TRACE(
"could not find DIR_ITEM to delete\n");
1825 ERR(
"unexpected batch operation type\n");
1833 t->header.num_items--;
1859 while (le != &br->
items) {
1874 ERR(
"find_item returned %08lx\n",
Status);
2082 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
2084 ERR(
"out of memory\n");
2113 }
else if (
cmp == 0) {
2120 ERR(
"handle_batch_collision returned %08lx\n",
Status);
2123 ExFreeToPagedLookasideList(&
Vcb->tree_data_lookaside, td);
2155 while (le2 != &br->
items) {
2161 if (no_end ||
keycmp(bi2->
key, tree_end) == -1) {
2163 bool inserted =
false;
2171 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
2173 ERR(
"out of memory\n");
2201 ERR(
"handle_batch_collision returned %08lx\n",
Status);
2208 }
else if (
cmp == -1) {
2253 if (
t->paritem &&
t->paritem->ignore) {
2255 t->parent->header.num_items++;
2259 t->header.generation =
Vcb->superblock.generation;
2275 ExFreeToPagedLookasideList(&
Vcb->batch_item_lookaside, bi);
2290 ERR(
"commit_batch_list_root returned %08lx\n",
Status);
#define STATUS_INSUFFICIENT_RESOURCES
NTSTATUS update_changed_extent_ref(device_extension *Vcb, chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, int32_t count, bool no_csum, bool superseded, PIRP Irp)
static NTSTATUS do_load_tree2(device_extension *Vcb, tree_holder *th, uint8_t *buf, root *r, tree *t, tree_data *td)
NTSTATUS load_tree(device_extension *Vcb, uint64_t addr, uint8_t *buf, root *r, tree **pt)
GLdouble GLdouble GLdouble r
struct _LIST_ENTRY * Blink
FORCEINLINE VOID InsertHeadList(_Inout_ PLIST_ENTRY ListHead, _Inout_ __drv_aliasesMem PLIST_ENTRY Entry)
static NTSTATUS next_item2(device_extension *Vcb, tree *t, tree_data *td, traverse_ptr *tp)
int ignore(int trapCode, ppc_trap_frame_t *trap)
#define BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF
FORCEINLINE PLIST_ENTRY RemoveTailList(_Inout_ PLIST_ENTRY ListHead)
bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *next_tp, bool ignore, PIRP Irp)
static NTSTATUS find_item_in_tree(device_extension *Vcb, tree *t, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
#define keycmp(key1, key2)
void reap_fcbs(device_extension *Vcb)
LIST_ENTRY list_entry_hash
enum batch_operation operation
NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp)
release_chunk_lock(c, Vcb)
unsigned short int uint16_t
static void add_delete_inode_extref(device_extension *Vcb, batch_item *bi, LIST_ENTRY *listhead)
#define cmp(status, error)
#define InsertTailList(ListHead, Entry)
NTSTATUS skip_to_difference(device_extension *Vcb, traverse_ptr *tp, traverse_ptr *tp2, bool *ended1, bool *ended2)
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
VOID FASTCALL ExReleaseFastMutex(IN PFAST_MUTEX FastMutex)
GLfloat GLfloat GLfloat GLfloat h
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
BOOLEAN NTAPI ExAcquireResourceExclusiveLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
#define STATUS_INTERNAL_ERROR
GLenum GLuint GLenum GLsizei const GLchar * buf
NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp)
struct _device_extension * Vcb
void free_trees(device_extension *Vcb)
static __inline tree_data * last_item(tree *t)
#define offsetof(TYPE, MEMBER)
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
void clear_rollback(LIST_ENTRY *rollback)
_Requires_exclusive_lock_held_(Vcb->tree_lock) static NTSTATUS add_root(_Inout_ device_extension *Vcb
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
struct _LIST_ENTRY * Flink
GLboolean GLboolean GLboolean b
void add_rollback(_In_ LIST_ENTRY *rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void *ptr)
static __inline tree_data * prev_item(tree *t, tree_data *td)
void reap_filerefs(device_extension *Vcb, file_ref *fr)
static NTSTATUS handle_batch_collision(device_extension *Vcb, batch_item *bi, tree *t, tree_data *td, tree_data *newtd, LIST_ENTRY *listhead, bool *ignore)
#define NT_SUCCESS(StatCode)
static __inline tree_data * next_item(tree *t, tree_data *td)
#define BTRFS_INODE_NODATASUM
FORCEINLINE VOID ExInitializeFastMutex(_Out_ PFAST_MUTEX FastMutex)
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
#define ExAllocatePoolWithTag(hernya, size, tag)
GLenum const GLvoid * addr
#define TYPE_INODE_EXTREF
static void find_tree_end(tree *t, KEY *tree_end, bool *no_end)
NTSTATUS find_item_to_level(device_extension *Vcb, root *r, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp)
void clear_batch_list(device_extension *Vcb, LIST_ENTRY *batchlist)
#define EXTENT_TYPE_PREALLOC
void do_rollback(device_extension *Vcb, LIST_ENTRY *rollback)
#define EXTENT_TYPE_REGULAR
chunk * get_chunk_from_address(device_extension *Vcb, uint64_t address)
static unsigned __int64 next
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, batch_root *br, PIRP Irp)
VOID FASTCALL ExAcquireFastMutex(IN PFAST_MUTEX FastMutex)
void space_list_subtract2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
#define acquire_chunk_lock(c, Vcb)
#define InitializeListHead(ListHead)
void free_trees_root(device_extension *Vcb, root *r)
NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp)
_In_ fcb _In_ chunk _In_ uint64_t _In_ uint64_t _In_ bool _In_opt_ void _In_opt_ PIRP _In_ LIST_ENTRY * rollback
#define _In_reads_bytes_opt_(s)
NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp)
static BOOL read_data(struct request *request, void *buffer, DWORD size, DWORD *read, BOOL async)
NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _In_ uint64_t obj_id, _In_ uint8_t obj_type, _In_ uint64_t offset, _In_reads_bytes_opt_(size) _When_(return >=0, __drv_aliasesMem) void *data, _In_ uint16_t size, _Out_opt_ traverse_ptr *ptp, _In_opt_ PIRP Irp)
#define RtlCopyMemory(Destination, Source, Length)
GLdouble GLdouble GLdouble GLdouble top
GLuint GLuint GLsizei GLenum type
static __inline tree_data * first_item(tree *t)
void space_list_add2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
#define _Requires_lock_held_(a)
#define RtlCompareMemory(s1, s2, l)
bool find_prev_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *prev_tp, PIRP Irp)