ReactOS 0.4.15-dev-7842-g558ab78
extent-tree.c File Reference
#include "btrfs_drv.h"
#include "crc32c.h"
Include dependency graph for extent-tree.c:

Go to the source code of this file.

Classes

struct  extent_ref
 

Functions

uint64_t get_extent_data_ref_hash2 (uint64_t root, uint64_t objid, uint64_t offset)
 
static __inline uint64_t get_extent_data_ref_hash (EXTENT_DATA_REF *edr)
 
static uint64_t get_extent_hash (uint8_t type, void *data)
 
static void free_extent_refs (LIST_ENTRY *extent_refs)
 
static NTSTATUS add_shared_data_extent_ref (LIST_ENTRY *extent_refs, uint64_t parent, uint32_t count)
 
static NTSTATUS add_shared_block_extent_ref (LIST_ENTRY *extent_refs, uint64_t parent)
 
static NTSTATUS add_tree_block_extent_ref (LIST_ENTRY *extent_refs, uint64_t root)
 
static void sort_extent_refs (LIST_ENTRY *extent_refs)
 
static NTSTATUS construct_extent_item (device_extension *Vcb, uint64_t address, uint64_t size, uint64_t flags, LIST_ENTRY *extent_refs, KEY *firstitem, uint8_t level, PIRP Irp)
 
static NTSTATUS convert_old_extent (device_extension *Vcb, uint64_t address, bool tree, KEY *firstitem, uint8_t level, PIRP Irp)
 
NTSTATUS increase_extent_refcount (device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, PIRP Irp)
 
NTSTATUS increase_extent_refcount_data (device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t inode, uint64_t offset, uint32_t refcount, PIRP Irp)
 
NTSTATUS decrease_extent_refcount (device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, uint64_t parent, bool superseded, PIRP Irp)
 
NTSTATUS decrease_extent_refcount_data (device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t inode, uint64_t offset, uint32_t refcount, bool superseded, PIRP Irp)
 
NTSTATUS decrease_extent_refcount_tree (device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint8_t level, PIRP Irp)
 
static uint32_t find_extent_data_refcount (device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, PIRP Irp)
 
uint64_t get_extent_refcount (device_extension *Vcb, uint64_t address, uint64_t size, PIRP Irp)
 
bool is_extent_unique (device_extension *Vcb, uint64_t address, uint64_t size, PIRP Irp)
 
uint64_t get_extent_flags (device_extension *Vcb, uint64_t address, PIRP Irp)
 
void update_extent_flags (device_extension *Vcb, uint64_t address, uint64_t flags, PIRP Irp)
 
static changed_extentget_changed_extent_item (chunk *c, uint64_t address, uint64_t size, bool no_csum)
 
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)
 
void add_changed_extent_ref (chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, uint32_t count, bool no_csum)
 
uint64_t find_extent_shared_tree_refcount (device_extension *Vcb, uint64_t address, uint64_t parent, PIRP Irp)
 
uint32_t find_extent_shared_data_refcount (device_extension *Vcb, uint64_t address, uint64_t parent, PIRP Irp)
 

Function Documentation

◆ add_changed_extent_ref()

void add_changed_extent_ref ( chunk c,
uint64_t  address,
uint64_t  size,
uint64_t  root,
uint64_t  objid,
uint64_t  offset,
uint32_t  count,
bool  no_csum 
)

Definition at line 2076 of file extent-tree.c.

2076 {
2077 changed_extent* ce;
2078 changed_extent_ref* cer;
2079 LIST_ENTRY* le;
2080
2081 ce = get_changed_extent_item(c, address, size, no_csum);
2082
2083 if (!ce) {
2084 ERR("get_changed_extent_item failed\n");
2085 return;
2086 }
2087
2088 le = ce->refs.Flink;
2089 while (le != &ce->refs) {
2091
2092 if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == root && cer->edr.objid == objid && cer->edr.offset == offset) {
2093 ce->count += count;
2094 cer->edr.count += count;
2095 return;
2096 }
2097
2098 le = le->Flink;
2099 }
2100
2102
2103 if (!cer) {
2104 ERR("out of memory\n");
2105 return;
2106 }
2107
2109 cer->edr.root = root;
2110 cer->edr.objid = objid;
2111 cer->edr.offset = offset;
2112 cer->edr.count = count;
2113
2114 InsertTailList(&ce->refs, &cer->list_entry);
2115
2116 ce->count += count;
2117}
#define ERR(fmt,...)
Definition: debug.h:110
struct _root root
#define ALLOC_TAG
Definition: btrfs_drv.h:87
#define TYPE_EXTENT_DATA_REF
Definition: btrfs.h:38
#define InsertTailList(ListHead, Entry)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define PagedPool
Definition: env_spec_w32.h:308
static changed_extent * get_changed_extent_item(chunk *c, uint64_t address, uint64_t size, bool no_csum)
Definition: extent-tree.c:1916
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLsizeiptr size
Definition: glext.h:5919
GLuint address
Definition: glext.h:9393
const GLubyte * c
Definition: glext.h:8905
GLintptr offset
Definition: glext.h:5920
uint64_t offset
Definition: btrfs.h:419
uint64_t root
Definition: btrfs.h:417
uint64_t objid
Definition: btrfs.h:418
uint32_t count
Definition: btrfs.h:420
Definition: typedefs.h:120
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
LIST_ENTRY list_entry
Definition: btrfs_drv.h:617
EXTENT_DATA_REF edr
Definition: btrfs_drv.h:613
uint64_t count
Definition: btrfs_drv.h:600
LIST_ENTRY refs
Definition: btrfs_drv.h:604
Definition: list.h:27
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260

Referenced by insert_extent_chunk(), rationalize_extents(), and write_compressed().

◆ add_shared_block_extent_ref()

static NTSTATUS add_shared_block_extent_ref ( LIST_ENTRY extent_refs,
uint64_t  parent 
)
static

Definition at line 110 of file extent-tree.c.

110 {
111 extent_ref* er2;
112 LIST_ENTRY* le;
113
114 if (!IsListEmpty(extent_refs)) {
115 le = extent_refs->Flink;
116
117 while (le != extent_refs) {
119
120 if (er->type == TYPE_SHARED_BLOCK_REF && er->sbr.offset == parent)
121 return STATUS_SUCCESS;
122
123 le = le->Flink;
124 }
125 }
126
128 if (!er2) {
129 ERR("out of memory\n");
131 }
132
134 er2->sbr.offset = parent;
135
136 InsertTailList(extent_refs, &er2->list_entry);
137
138 return STATUS_SUCCESS;
139}
r parent
Definition: btrfs.c:3010
#define TYPE_SHARED_BLOCK_REF
Definition: btrfs.h:40
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
#define STATUS_SUCCESS
Definition: shellext.h:65
uint64_t offset
Definition: btrfs.h:437
LIST_ENTRY list_entry
Definition: extent-tree.c:32
SHARED_BLOCK_REF sbr
Definition: extent-tree.c:28
uint8_t type
Definition: extent-tree.c:22
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158

Referenced by convert_old_extent().

◆ add_shared_data_extent_ref()

static NTSTATUS add_shared_data_extent_ref ( LIST_ENTRY extent_refs,
uint64_t  parent,
uint32_t  count 
)
static

Definition at line 76 of file extent-tree.c.

76 {
77 extent_ref* er2;
78 LIST_ENTRY* le;
79
80 if (!IsListEmpty(extent_refs)) {
81 le = extent_refs->Flink;
82
83 while (le != extent_refs) {
85
86 if (er->type == TYPE_SHARED_DATA_REF && er->sdr.offset == parent) {
87 er->sdr.count += count;
88 return STATUS_SUCCESS;
89 }
90
91 le = le->Flink;
92 }
93 }
94
96 if (!er2) {
97 ERR("out of memory\n");
99 }
100
102 er2->sdr.offset = parent;
103 er2->sdr.count = count;
104
105 InsertTailList(extent_refs, &er2->list_entry);
106
107 return STATUS_SUCCESS;
108}
#define TYPE_SHARED_DATA_REF
Definition: btrfs.h:41
uint32_t count
Definition: btrfs.h:442
uint64_t offset
Definition: btrfs.h:441
SHARED_DATA_REF sdr
Definition: extent-tree.c:26

Referenced by convert_old_extent().

◆ add_tree_block_extent_ref()

static NTSTATUS add_tree_block_extent_ref ( LIST_ENTRY extent_refs,
uint64_t  root 
)
static

Definition at line 141 of file extent-tree.c.

141 {
142 extent_ref* er2;
143 LIST_ENTRY* le;
144
145 if (!IsListEmpty(extent_refs)) {
146 le = extent_refs->Flink;
147
148 while (le != extent_refs) {
150
151 if (er->type == TYPE_TREE_BLOCK_REF && er->tbr.offset == root)
152 return STATUS_SUCCESS;
153
154 le = le->Flink;
155 }
156 }
157
159 if (!er2) {
160 ERR("out of memory\n");
162 }
163
165 er2->tbr.offset = root;
166
167 InsertTailList(extent_refs, &er2->list_entry);
168
169 return STATUS_SUCCESS;
170}
#define TYPE_TREE_BLOCK_REF
Definition: btrfs.h:37
uint64_t offset
Definition: btrfs.h:413
TREE_BLOCK_REF tbr
Definition: extent-tree.c:27

Referenced by convert_old_extent().

◆ construct_extent_item()

static NTSTATUS construct_extent_item ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint64_t  flags,
LIST_ENTRY extent_refs,
KEY firstitem,
uint8_t  level,
PIRP  Irp 
)
static

Definition at line 210 of file extent-tree.c.

211 {
213 LIST_ENTRY *le, *next_le;
214 uint64_t refcount;
215 uint16_t inline_len;
216 bool all_inline = true;
217 extent_ref* first_noninline = NULL;
218 EXTENT_ITEM* ei;
219 uint8_t* siptr;
220
221 // FIXME - write skinny extents if is tree and incompat flag set
222
223 if (IsListEmpty(extent_refs)) {
224 WARN("no extent refs found\n");
225 return STATUS_SUCCESS;
226 }
227
228 refcount = 0;
229 inline_len = sizeof(EXTENT_ITEM);
230
232 inline_len += sizeof(EXTENT_ITEM2);
233
234 le = extent_refs->Flink;
235 while (le != extent_refs) {
237 uint64_t rc;
238
239 next_le = le->Flink;
240
241 rc = get_extent_data_refcount(er->type, &er->edr);
242
243 if (rc == 0) {
245
246 ExFreePool(er);
247 } else {
248 uint16_t extlen = get_extent_data_len(er->type);
249
250 refcount += rc;
251
252 er->hash = get_extent_hash(er->type, &er->edr);
253
254 if (all_inline) {
255 if ((uint16_t)(inline_len + 1 + extlen) > Vcb->superblock.node_size >> 2) {
256 all_inline = false;
257 first_noninline = er;
258 } else
259 inline_len += extlen + 1;
260 }
261 }
262
263 le = next_le;
264 }
265
266 ei = ExAllocatePoolWithTag(PagedPool, inline_len, ALLOC_TAG);
267 if (!ei) {
268 ERR("out of memory\n");
270 }
271
272 ei->refcount = refcount;
273 ei->generation = Vcb->superblock.generation;
274 ei->flags = flags;
275
277 EXTENT_ITEM2* ei2 = (EXTENT_ITEM2*)&ei[1];
278
279 if (firstitem) {
280 ei2->firstitem.obj_id = firstitem->obj_id;
281 ei2->firstitem.obj_type = firstitem->obj_type;
282 ei2->firstitem.offset = firstitem->offset;
283 } else {
284 ei2->firstitem.obj_id = 0;
285 ei2->firstitem.obj_type = 0;
286 ei2->firstitem.offset = 0;
287 }
288
289 ei2->level = level;
290
291 siptr = (uint8_t*)&ei2[1];
292 } else
293 siptr = (uint8_t*)&ei[1];
294
295 sort_extent_refs(extent_refs);
296
297 le = extent_refs->Flink;
298 while (le != extent_refs) {
300 ULONG extlen = get_extent_data_len(er->type);
301
302 if (!all_inline && er == first_noninline)
303 break;
304
305 *siptr = er->type;
306 siptr++;
307
308 if (extlen > 0) {
309 RtlCopyMemory(siptr, &er->edr, extlen);
310 siptr += extlen;
311 }
312
313 le = le->Flink;
314 }
315
316 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, inline_len, NULL, Irp);
317 if (!NT_SUCCESS(Status)) {
318 ERR("insert_tree_item returned %08lx\n", Status);
319 ExFreePool(ei);
320 return Status;
321 }
322
323 if (!all_inline) {
324 le = &first_noninline->list_entry;
325
326 while (le != extent_refs) {
329 uint8_t* data;
330
331 if (er->type == TYPE_EXTENT_DATA_REF) {
332 len = sizeof(EXTENT_DATA_REF);
333
335
336 if (!data) {
337 ERR("out of memory\n");
339 }
340
341 RtlCopyMemory(data, &er->edr, len);
342 } else if (er->type == TYPE_SHARED_DATA_REF) {
343 len = sizeof(uint32_t);
344
346
347 if (!data) {
348 ERR("out of memory\n");
350 }
351
352 *((uint32_t*)data) = er->sdr.count;
353 } else {
354 len = 0;
355 data = NULL;
356 }
357
358 Status = insert_tree_item(Vcb, Vcb->extent_root, address, er->type, er->hash, data, len, NULL, Irp);
359 if (!NT_SUCCESS(Status)) {
360 ERR("insert_tree_item returned %08lx\n", Status);
361 if (data) ExFreePool(data);
362 return Status;
363 }
364
365 le = le->Flink;
366 }
367 }
368
369 return STATUS_SUCCESS;
370}
unsigned short int uint16_t
Definition: acefiex.h:54
LONG NTSTATUS
Definition: precomp.h:26
#define WARN(fmt,...)
Definition: debug.h:112
static __inline uint32_t get_extent_data_refcount(uint8_t type, void *data)
Definition: btrfs_drv.h:1065
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) __attribute__((nonnull(1
static __inline uint16_t get_extent_data_len(uint8_t type)
Definition: btrfs_drv.h:1043
_In_ PIRP Irp
Definition: csq.h:116
#define NULL
Definition: types.h:112
UINT32 uint32_t
Definition: types.h:75
UINT64 uint64_t
Definition: types.h:77
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define TYPE_EXTENT_ITEM
Definition: btrfs.h:35
#define EXTENT_ITEM_TREE_BLOCK
Definition: btrfs.h:388
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
static void sort_extent_refs(LIST_ENTRY *extent_refs)
Definition: extent-tree.c:172
static uint64_t get_extent_hash(uint8_t type, void *data)
Definition: extent-tree.c:49
Status
Definition: gdiplustypes.h:25
GLint level
Definition: gl.h:1546
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLbitfield flags
Definition: glext.h:7161
GLenum GLsizei len
Definition: glext.h:6722
BYTE uint8_t
Definition: msvideo1.c:66
#define uint32_t
Definition: nsiface.idl:61
#define Vcb
Definition: cdprocs.h:1415
KEY firstitem
Definition: btrfs.h:398
uint8_t level
Definition: btrfs.h:399
uint64_t generation
Definition: btrfs.h:393
uint64_t flags
Definition: btrfs.h:394
uint64_t refcount
Definition: btrfs.h:392
uint8_t obj_type
Definition: btrfs.h:145
uint64_t obj_id
Definition: btrfs.h:144
uint64_t offset
Definition: btrfs.h:146
EXTENT_DATA_REF edr
Definition: extent-tree.c:25
uint64_t hash
Definition: extent-tree.c:31
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
uint32_t ULONG
Definition: typedefs.h:59

Referenced by convert_old_extent().

◆ convert_old_extent()

static NTSTATUS convert_old_extent ( device_extension Vcb,
uint64_t  address,
bool  tree,
KEY firstitem,
uint8_t  level,
PIRP  Irp 
)
static

Definition at line 372 of file extent-tree.c.

372 {
374 KEY searchkey;
375 traverse_ptr tp, next_tp;
376 LIST_ENTRY extent_refs;
378
379 InitializeListHead(&extent_refs);
380
381 searchkey.obj_id = address;
382 searchkey.obj_type = TYPE_EXTENT_ITEM;
383 searchkey.offset = 0xffffffffffffffff;
384
385 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
386 if (!NT_SUCCESS(Status)) {
387 ERR("find_item returned %08lx\n", Status);
388 return Status;
389 }
390
391 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
392 ERR("old-style extent %I64x not found\n", address);
394 }
395
396 size = tp.item->key.offset;
397
399 if (!NT_SUCCESS(Status)) {
400 ERR("delete_tree_item returned %08lx\n", Status);
401 return Status;
402 }
403
404 while (find_next_item(Vcb, &tp, &next_tp, false, Irp)) {
405 tp = next_tp;
406
409
410 if (tree) {
411 if (tp.item->key.offset == tp.item->key.obj_id) { // top of the tree
412 Status = add_tree_block_extent_ref(&extent_refs, erv0->root);
413 if (!NT_SUCCESS(Status)) {
414 ERR("add_tree_block_extent_ref returned %08lx\n", Status);
415 goto end;
416 }
417 } else {
419 if (!NT_SUCCESS(Status)) {
420 ERR("add_shared_block_extent_ref returned %08lx\n", Status);
421 goto end;
422 }
423 }
424 } else {
425 Status = add_shared_data_extent_ref(&extent_refs, tp.item->key.offset, erv0->count);
426 if (!NT_SUCCESS(Status)) {
427 ERR("add_shared_data_extent_ref returned %08lx\n", Status);
428 goto end;
429 }
430 }
431
433 if (!NT_SUCCESS(Status)) {
434 ERR("delete_tree_item returned %08lx\n", Status);
435 goto end;
436 }
437 }
438
440 break;
441 }
442
444 &extent_refs, firstitem, level, Irp);
445 if (!NT_SUCCESS(Status))
446 ERR("construct_extent_item returned %08lx\n", Status);
447
448end:
449 free_extent_refs(&extent_refs);
450
451 return Status;
452}
NTSTATUS NTSTATUS 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) __attribute__((nonnull(1
NTSTATUS NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp) __attribute__((nonnull(1
static LONG find_item(PropertyBag *This, LPCOLESTR name)
Definition: propertybag.c:110
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2996
#define EXTENT_ITEM_DATA
Definition: btrfs.h:387
#define EXTENT_ITEM_SHARED_BACKREFS
Definition: btrfs.h:389
#define TYPE_EXTENT_REF_V0
Definition: btrfs.h:39
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
static void free_extent_refs(LIST_ENTRY *extent_refs)
Definition: extent-tree.c:67
static NTSTATUS construct_extent_item(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t flags, LIST_ENTRY *extent_refs, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:210
static NTSTATUS add_tree_block_extent_ref(LIST_ENTRY *extent_refs, uint64_t root)
Definition: extent-tree.c:141
static NTSTATUS add_shared_block_extent_ref(LIST_ENTRY *extent_refs, uint64_t parent)
Definition: extent-tree.c:110
static NTSTATUS add_shared_data_extent_ref(LIST_ENTRY *extent_refs, uint64_t parent, uint32_t count)
Definition: extent-tree.c:76
GLuint GLuint end
Definition: gl.h:1545
if(dx< 0)
Definition: linetemp.h:194
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:465
uint64_t root
Definition: btrfs.h:430
uint32_t count
Definition: btrfs.h:433
Definition: btrfs.h:143
uint8_t * data
Definition: btrfs_drv.h:415
uint16_t size
Definition: btrfs_drv.h:414
tree_data * item
Definition: btrfs_drv.h:509

Referenced by decrease_extent_refcount(), and increase_extent_refcount().

◆ decrease_extent_refcount()

NTSTATUS decrease_extent_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint8_t  type,
void data,
KEY firstitem,
uint8_t  level,
uint64_t  parent,
bool  superseded,
PIRP  Irp 
)

Definition at line 903 of file extent-tree.c.

904 {
905 KEY searchkey;
907 traverse_ptr tp, tp2;
908 EXTENT_ITEM* ei;
909 ULONG len;
910 uint64_t inline_rc;
911 uint8_t* ptr;
914 bool is_tree = (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF), skinny = false;
915
916 if (is_tree && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
917 searchkey.obj_id = address;
918 searchkey.obj_type = TYPE_METADATA_ITEM;
919 searchkey.offset = 0xffffffffffffffff;
920
921 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
922 if (!NT_SUCCESS(Status)) {
923 ERR("error - find_item returned %08lx\n", Status);
924 return Status;
925 }
926
927 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type)
928 skinny = true;
929 }
930
931 if (!skinny) {
932 searchkey.obj_id = address;
933 searchkey.obj_type = TYPE_EXTENT_ITEM;
934 searchkey.offset = 0xffffffffffffffff;
935
936 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
937 if (!NT_SUCCESS(Status)) {
938 ERR("error - find_item returned %08lx\n", Status);
939 return Status;
940 }
941
942 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
943 ERR("could not find EXTENT_ITEM for address %I64x\n", address);
945 }
946
947 if (tp.item->key.offset != size) {
948 ERR("extent %I64x had length %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
950 }
951
952 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
953 Status = convert_old_extent(Vcb, address, is_tree, firstitem, level, Irp);
954
955 if (!NT_SUCCESS(Status)) {
956 ERR("convert_old_extent returned %08lx\n", Status);
957 return Status;
958 }
959
961 }
962 }
963
964 if (tp.item->size < sizeof(EXTENT_ITEM)) {
965 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));
967 }
968
969 ei = (EXTENT_ITEM*)tp.item->data;
970
971 len = tp.item->size - sizeof(EXTENT_ITEM);
972 ptr = (uint8_t*)&ei[1];
973
974 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
975 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
976 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) + sizeof(EXTENT_ITEM2));
978 }
979
980 len -= sizeof(EXTENT_ITEM2);
981 ptr += sizeof(EXTENT_ITEM2);
982 }
983
984 if (ei->refcount < rc) {
985 ERR("error - extent has refcount %I64x, trying to reduce by %x\n", ei->refcount, rc);
987 }
988
989 inline_rc = 0;
990
991 // Loop through inline extent entries
992
993 while (len > 0) {
994 uint8_t secttype = *ptr;
995 uint16_t sectlen = get_extent_data_len(secttype);
996 uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
997
998 len--;
999
1000 if (sectlen > len) {
1001 ERR("(%I64x,%x,%I64x): %lx bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1002 return STATUS_INTERNAL_ERROR;
1003 }
1004
1005 if (sectlen == 0) {
1006 ERR("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1007 return STATUS_INTERNAL_ERROR;
1008 }
1009
1010 if (secttype == type) {
1011 if (type == TYPE_EXTENT_DATA_REF) {
1012 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(uint8_t));
1014
1015 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
1016 uint16_t neweilen;
1017 EXTENT_ITEM* newei;
1018
1019 if (ei->refcount == edr->count) {
1021 if (!NT_SUCCESS(Status)) {
1022 ERR("delete_tree_item returned %08lx\n", Status);
1023 return Status;
1024 }
1025
1026 if (!superseded)
1027 add_checksum_entry(Vcb, address, (ULONG)(size >> Vcb->sector_shift), NULL, Irp);
1028
1029 return STATUS_SUCCESS;
1030 }
1031
1032 if (sectedr->count < edr->count) {
1033 ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
1034 return STATUS_INTERNAL_ERROR;
1035 }
1036
1037 if (sectedr->count > edr->count) // reduce section refcount
1038 neweilen = tp.item->size;
1039 else // remove section entirely
1040 neweilen = tp.item->size - sizeof(uint8_t) - sectlen;
1041
1042 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1043 if (!newei) {
1044 ERR("out of memory\n");
1046 }
1047
1048 if (sectedr->count > edr->count) {
1049 EXTENT_DATA_REF* newedr = (EXTENT_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectedr - tp.item->data));
1050
1051 RtlCopyMemory(newei, ei, neweilen);
1052
1053 newedr->count -= rc;
1054 } else {
1055 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1056
1057 if (len > sectlen)
1058 RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1059 }
1060
1061 newei->refcount -= rc;
1062
1064 if (!NT_SUCCESS(Status)) {
1065 ERR("delete_tree_item returned %08lx\n", Status);
1066 return Status;
1067 }
1068
1069 Status = insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, neweilen, NULL, Irp);
1070 if (!NT_SUCCESS(Status)) {
1071 ERR("insert_tree_item returned %08lx\n", Status);
1072 return Status;
1073 }
1074
1075 return STATUS_SUCCESS;
1076 }
1077 } else if (type == TYPE_SHARED_DATA_REF) {
1078 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(uint8_t));
1080
1081 if (sectsdr->offset == sdr->offset) {
1082 EXTENT_ITEM* newei;
1083 uint16_t neweilen;
1084
1085 if (ei->refcount == sectsdr->count) {
1087 if (!NT_SUCCESS(Status)) {
1088 ERR("delete_tree_item returned %08lx\n", Status);
1089 return Status;
1090 }
1091
1092 if (!superseded)
1093 add_checksum_entry(Vcb, address, (ULONG)(size >> Vcb->sector_shift), NULL, Irp);
1094
1095 return STATUS_SUCCESS;
1096 }
1097
1098 if (sectsdr->count < sdr->count) {
1099 ERR("error - SHARED_DATA_REF has refcount %x, trying to reduce by %x\n", sectsdr->count, sdr->count);
1100 return STATUS_INTERNAL_ERROR;
1101 }
1102
1103 if (sectsdr->count > sdr->count) // reduce section refcount
1104 neweilen = tp.item->size;
1105 else // remove section entirely
1106 neweilen = tp.item->size - sizeof(uint8_t) - sectlen;
1107
1108 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1109 if (!newei) {
1110 ERR("out of memory\n");
1112 }
1113
1114 if (sectsdr->count > sdr->count) {
1115 SHARED_DATA_REF* newsdr = (SHARED_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectsdr - tp.item->data));
1116
1117 RtlCopyMemory(newei, ei, neweilen);
1118
1119 newsdr->count -= rc;
1120 } else {
1121 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1122
1123 if (len > sectlen)
1124 RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1125 }
1126
1127 newei->refcount -= rc;
1128
1130 if (!NT_SUCCESS(Status)) {
1131 ERR("delete_tree_item returned %08lx\n", Status);
1132 return Status;
1133 }
1134
1135 Status = insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, neweilen, NULL, Irp);
1136 if (!NT_SUCCESS(Status)) {
1137 ERR("insert_tree_item returned %08lx\n", Status);
1138 return Status;
1139 }
1140
1141 return STATUS_SUCCESS;
1142 }
1143 } else if (type == TYPE_TREE_BLOCK_REF) {
1144 TREE_BLOCK_REF* secttbr = (TREE_BLOCK_REF*)(ptr + sizeof(uint8_t));
1146
1147 if (secttbr->offset == tbr->offset) {
1148 EXTENT_ITEM* newei;
1149 uint16_t neweilen;
1150
1151 if (ei->refcount == 1) {
1153 if (!NT_SUCCESS(Status)) {
1154 ERR("delete_tree_item returned %08lx\n", Status);
1155 return Status;
1156 }
1157
1158 return STATUS_SUCCESS;
1159 }
1160
1161 neweilen = tp.item->size - sizeof(uint8_t) - sectlen;
1162
1163 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1164 if (!newei) {
1165 ERR("out of memory\n");
1167 }
1168
1169 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1170
1171 if (len > sectlen)
1172 RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1173
1174 newei->refcount--;
1175
1177 if (!NT_SUCCESS(Status)) {
1178 ERR("delete_tree_item returned %08lx\n", Status);
1179 return Status;
1180 }
1181
1182 Status = insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, neweilen, NULL, Irp);
1183 if (!NT_SUCCESS(Status)) {
1184 ERR("insert_tree_item returned %08lx\n", Status);
1185 return Status;
1186 }
1187
1188 return STATUS_SUCCESS;
1189 }
1190 } else if (type == TYPE_SHARED_BLOCK_REF) {
1191 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(uint8_t));
1193
1194 if (sectsbr->offset == sbr->offset) {
1195 EXTENT_ITEM* newei;
1196 uint16_t neweilen;
1197
1198 if (ei->refcount == 1) {
1200 if (!NT_SUCCESS(Status)) {
1201 ERR("delete_tree_item returned %08lx\n", Status);
1202 return Status;
1203 }
1204
1205 return STATUS_SUCCESS;
1206 }
1207
1208 neweilen = tp.item->size - sizeof(uint8_t) - sectlen;
1209
1210 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1211 if (!newei) {
1212 ERR("out of memory\n");
1214 }
1215
1216 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1217
1218 if (len > sectlen)
1219 RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1220
1221 newei->refcount--;
1222
1224 if (!NT_SUCCESS(Status)) {
1225 ERR("delete_tree_item returned %08lx\n", Status);
1226 return Status;
1227 }
1228
1229 Status = insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, neweilen, NULL, Irp);
1230 if (!NT_SUCCESS(Status)) {
1231 ERR("insert_tree_item returned %08lx\n", Status);
1232 return Status;
1233 }
1234
1235 return STATUS_SUCCESS;
1236 }
1237 } else {
1238 ERR("unhandled extent type %x\n", type);
1239 return STATUS_INTERNAL_ERROR;
1240 }
1241 }
1242
1243 len -= sectlen;
1244 ptr += sizeof(uint8_t) + sectlen;
1245 inline_rc += sectcount;
1246 }
1247
1248 if (inline_rc == ei->refcount) {
1249 ERR("entry not found in inline extent item for address %I64x\n", address);
1250 return STATUS_INTERNAL_ERROR;
1251 }
1252
1254 datalen = sizeof(uint32_t);
1256 datalen = 0;
1257
1258 searchkey.obj_id = address;
1259 searchkey.obj_type = type;
1261
1262 Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, false, Irp);
1263 if (!NT_SUCCESS(Status)) {
1264 ERR("error - find_item returned %08lx\n", Status);
1265 return Status;
1266 }
1267
1268 if (keycmp(tp2.item->key, searchkey)) {
1269 ERR("(%I64x,%x,%I64x) not found\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset);
1270 return STATUS_INTERNAL_ERROR;
1271 }
1272
1273 if (tp2.item->size < datalen) {
1274 ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %lu\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, datalen);
1275 return STATUS_INTERNAL_ERROR;
1276 }
1277
1278 if (type == TYPE_EXTENT_DATA_REF) {
1279 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)tp2.item->data;
1281
1282 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
1283 EXTENT_ITEM* newei;
1284
1285 if (ei->refcount == edr->count) {
1287 if (!NT_SUCCESS(Status)) {
1288 ERR("delete_tree_item returned %08lx\n", Status);
1289 return Status;
1290 }
1291
1292 Status = delete_tree_item(Vcb, &tp2);
1293 if (!NT_SUCCESS(Status)) {
1294 ERR("delete_tree_item returned %08lx\n", Status);
1295 return Status;
1296 }
1297
1298 if (!superseded)
1299 add_checksum_entry(Vcb, address, (ULONG)(size >> Vcb->sector_shift), NULL, Irp);
1300
1301 return STATUS_SUCCESS;
1302 }
1303
1304 if (sectedr->count < edr->count) {
1305 ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
1306 return STATUS_INTERNAL_ERROR;
1307 }
1308
1309 Status = delete_tree_item(Vcb, &tp2);
1310 if (!NT_SUCCESS(Status)) {
1311 ERR("delete_tree_item returned %08lx\n", Status);
1312 return Status;
1313 }
1314
1315 if (sectedr->count > edr->count) {
1317
1318 if (!newedr) {
1319 ERR("out of memory\n");
1321 }
1322
1323 RtlCopyMemory(newedr, sectedr, tp2.item->size);
1324
1325 newedr->count -= edr->count;
1326
1327 Status = insert_tree_item(Vcb, Vcb->extent_root, tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, newedr, tp2.item->size, NULL, Irp);
1328 if (!NT_SUCCESS(Status)) {
1329 ERR("insert_tree_item returned %08lx\n", Status);
1330 return Status;
1331 }
1332 }
1333
1335 if (!newei) {
1336 ERR("out of memory\n");
1338 }
1339
1340 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1341
1342 newei->refcount -= rc;
1343
1345 if (!NT_SUCCESS(Status)) {
1346 ERR("delete_tree_item returned %08lx\n", Status);
1347 return Status;
1348 }
1349
1351 if (!NT_SUCCESS(Status)) {
1352 ERR("insert_tree_item returned %08lx\n", Status);
1353 return Status;
1354 }
1355
1356 return STATUS_SUCCESS;
1357 } else {
1358 ERR("error - hash collision?\n");
1359 return STATUS_INTERNAL_ERROR;
1360 }
1361 } else if (type == TYPE_SHARED_DATA_REF) {
1363
1364 if (tp2.item->key.offset == sdr->offset) {
1365 uint32_t* sectsdrcount = (uint32_t*)tp2.item->data;
1366 EXTENT_ITEM* newei;
1367
1368 if (ei->refcount == sdr->count) {
1370 if (!NT_SUCCESS(Status)) {
1371 ERR("delete_tree_item returned %08lx\n", Status);
1372 return Status;
1373 }
1374
1375 Status = delete_tree_item(Vcb, &tp2);
1376 if (!NT_SUCCESS(Status)) {
1377 ERR("delete_tree_item returned %08lx\n", Status);
1378 return Status;
1379 }
1380
1381 if (!superseded)
1382 add_checksum_entry(Vcb, address, (ULONG)(size >> Vcb->sector_shift), NULL, Irp);
1383
1384 return STATUS_SUCCESS;
1385 }
1386
1387 if (*sectsdrcount < sdr->count) {
1388 ERR("error - extent section has refcount %x, trying to reduce by %x\n", *sectsdrcount, sdr->count);
1389 return STATUS_INTERNAL_ERROR;
1390 }
1391
1392 Status = delete_tree_item(Vcb, &tp2);
1393 if (!NT_SUCCESS(Status)) {
1394 ERR("delete_tree_item returned %08lx\n", Status);
1395 return Status;
1396 }
1397
1398 if (*sectsdrcount > sdr->count) {
1400
1401 if (!newsdr) {
1402 ERR("out of memory\n");
1404 }
1405
1406 *newsdr = *sectsdrcount - sdr->count;
1407
1408 Status = insert_tree_item(Vcb, Vcb->extent_root, tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, newsdr, tp2.item->size, NULL, Irp);
1409 if (!NT_SUCCESS(Status)) {
1410 ERR("insert_tree_item returned %08lx\n", Status);
1411 return Status;
1412 }
1413 }
1414
1416 if (!newei) {
1417 ERR("out of memory\n");
1419 }
1420
1421 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1422
1423 newei->refcount -= rc;
1424
1426 if (!NT_SUCCESS(Status)) {
1427 ERR("delete_tree_item returned %08lx\n", Status);
1428 return Status;
1429 }
1430
1432 if (!NT_SUCCESS(Status)) {
1433 ERR("insert_tree_item returned %08lx\n", Status);
1434 return Status;
1435 }
1436
1437 return STATUS_SUCCESS;
1438 } else {
1439 ERR("error - collision?\n");
1440 return STATUS_INTERNAL_ERROR;
1441 }
1442 } else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF) {
1443 EXTENT_ITEM* newei;
1444
1445 if (ei->refcount == 1) {
1447 if (!NT_SUCCESS(Status)) {
1448 ERR("delete_tree_item returned %08lx\n", Status);
1449 return Status;
1450 }
1451
1452 Status = delete_tree_item(Vcb, &tp2);
1453 if (!NT_SUCCESS(Status)) {
1454 ERR("delete_tree_item returned %08lx\n", Status);
1455 return Status;
1456 }
1457
1458 return STATUS_SUCCESS;
1459 }
1460
1461 Status = delete_tree_item(Vcb, &tp2);
1462 if (!NT_SUCCESS(Status)) {
1463 ERR("delete_tree_item returned %08lx\n", Status);
1464 return Status;
1465 }
1466
1468 if (!newei) {
1469 ERR("out of memory\n");
1471 }
1472
1473 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1474
1475 newei->refcount -= rc;
1476
1478 if (!NT_SUCCESS(Status)) {
1479 ERR("delete_tree_item returned %08lx\n", Status);
1480 return Status;
1481 }
1482
1484 if (!NT_SUCCESS(Status)) {
1485 ERR("insert_tree_item returned %08lx\n", Status);
1486 return Status;
1487 }
1488
1489 return STATUS_SUCCESS;
1490 } else if (type == TYPE_EXTENT_REF_V0) {
1491 EXTENT_REF_V0* erv0 = (EXTENT_REF_V0*)tp2.item->data;
1492 EXTENT_ITEM* newei;
1493
1494 if (ei->refcount == erv0->count) {
1496 if (!NT_SUCCESS(Status)) {
1497 ERR("delete_tree_item returned %08lx\n", Status);
1498 return Status;
1499 }
1500
1501 Status = delete_tree_item(Vcb, &tp2);
1502 if (!NT_SUCCESS(Status)) {
1503 ERR("delete_tree_item returned %08lx\n", Status);
1504 return Status;
1505 }
1506
1507 if (!superseded)
1508 add_checksum_entry(Vcb, address, (ULONG)(size >> Vcb->sector_shift), NULL, Irp);
1509
1510 return STATUS_SUCCESS;
1511 }
1512
1513 Status = delete_tree_item(Vcb, &tp2);
1514 if (!NT_SUCCESS(Status)) {
1515 ERR("delete_tree_item returned %08lx\n", Status);
1516 return Status;
1517 }
1518
1520 if (!newei) {
1521 ERR("out of memory\n");
1523 }
1524
1525 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1526
1527 newei->refcount -= rc;
1528
1530 if (!NT_SUCCESS(Status)) {
1531 ERR("delete_tree_item returned %08lx\n", Status);
1532 return Status;
1533 }
1534
1536 if (!NT_SUCCESS(Status)) {
1537 ERR("insert_tree_item returned %08lx\n", Status);
1538 return Status;
1539 }
1540
1541 return STATUS_SUCCESS;
1542 } else {
1543 ERR("unhandled extent type %x\n", type);
1544 return STATUS_INTERNAL_ERROR;
1545 }
1546}
#define keycmp(key1, key2)
Definition: btrfs_drv.h:1016
void add_checksum_entry(device_extension *Vcb, uint64_t address, ULONG length, void *csum, PIRP Irp)
Definition: flushthread.c:2602
static WCHAR superseded[MAX_STRING_RESOURCE_LEN]
Definition: object.c:1817
#define BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
Definition: btrfs.h:123
#define TYPE_METADATA_ITEM
Definition: btrfs.h:36
static NTSTATUS convert_old_extent(device_extension *Vcb, uint64_t address, bool tree, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:372
NTSTATUS decrease_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, uint64_t parent, bool superseded, PIRP Irp)
Definition: extent-tree.c:903
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
int const JOCTET unsigned int datalen
Definition: jpeglib.h:1031
static PVOID ptr
Definition: dispmode.c:27
#define uint8_t
Definition: nsiface.idl:59

Referenced by add_metadata_reloc_extent_item(), decrease_extent_refcount(), decrease_extent_refcount_data(), decrease_extent_refcount_tree(), and update_tree_extents().

◆ decrease_extent_refcount_data()

NTSTATUS decrease_extent_refcount_data ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint64_t  root,
uint64_t  inode,
uint64_t  offset,
uint32_t  refcount,
bool  superseded,
PIRP  Irp 
)

Definition at line 1548 of file extent-tree.c.

1549 {
1550 EXTENT_DATA_REF edr;
1551
1552 edr.root = root;
1553 edr.objid = inode;
1554 edr.offset = offset;
1555 edr.count = refcount;
1556
1558}
Definition: fs.h:78

Referenced by flush_changed_extent().

◆ decrease_extent_refcount_tree()

NTSTATUS decrease_extent_refcount_tree ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint64_t  root,
uint8_t  level,
PIRP  Irp 
)

Definition at line 1560 of file extent-tree.c.

1561 {
1562 TREE_BLOCK_REF tbr;
1563
1564 tbr.offset = root;
1565
1566 return decrease_extent_refcount(Vcb, address, size, TYPE_TREE_BLOCK_REF, &tbr, NULL/*FIXME*/, level, 0, false, Irp);
1567}

Referenced by reduce_tree_extent().

◆ find_extent_data_refcount()

static uint32_t find_extent_data_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint64_t  root,
uint64_t  objid,
uint64_t  offset,
PIRP  Irp 
)
static

Definition at line 1569 of file extent-tree.c.

1569 {
1571 KEY searchkey;
1573
1574 searchkey.obj_id = address;
1575 searchkey.obj_type = TYPE_EXTENT_ITEM;
1576 searchkey.offset = 0xffffffffffffffff;
1577
1578 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1579 if (!NT_SUCCESS(Status)) {
1580 ERR("error - find_item returned %08lx\n", Status);
1581 return 0;
1582 }
1583
1584 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1585 TRACE("could not find address %I64x in extent tree\n", address);
1586 return 0;
1587 }
1588
1589 if (tp.item->key.offset != size) {
1590 ERR("extent %I64x had size %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
1591 return 0;
1592 }
1593
1594 if (tp.item->size >= sizeof(EXTENT_ITEM)) {
1596 uint32_t len = tp.item->size - sizeof(EXTENT_ITEM);
1597 uint8_t* ptr = (uint8_t*)&ei[1];
1598
1599 while (len > 0) {
1600 uint8_t secttype = *ptr;
1601 ULONG sectlen = get_extent_data_len(secttype);
1602 uint32_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
1603
1604 len--;
1605
1606 if (sectlen > len) {
1607 ERR("(%I64x,%x,%I64x): %x bytes left, expecting at least %lx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1608 return 0;
1609 }
1610
1611 if (sectlen == 0) {
1612 ERR("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1613 return 0;
1614 }
1615
1616 if (secttype == TYPE_EXTENT_DATA_REF) {
1617 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(uint8_t));
1618
1619 if (sectedr->root == root && sectedr->objid == objid && sectedr->offset == offset)
1620 return sectcount;
1621 }
1622
1623 len -= sectlen;
1624 ptr += sizeof(uint8_t) + sectlen;
1625 }
1626 }
1627
1628 searchkey.obj_id = address;
1629 searchkey.obj_type = TYPE_EXTENT_DATA_REF;
1630 searchkey.offset = get_extent_data_ref_hash2(root, objid, offset);
1631
1632 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1633 if (!NT_SUCCESS(Status)) {
1634 ERR("error - find_item returned %08lx\n", Status);
1635 return 0;
1636 }
1637
1638 if (!keycmp(searchkey, tp.item->key)) {
1639 if (tp.item->size < sizeof(EXTENT_DATA_REF))
1640 ERR("(%I64x,%x,%I64x) has size %u, not %Iu as expected\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_DATA_REF));
1641 else {
1643
1644 return edr->count;
1645 }
1646 }
1647
1648 return 0;
1649}
uint64_t get_extent_data_ref_hash2(uint64_t root, uint64_t objid, uint64_t offset)
Definition: extent-tree.c:35
#define TRACE(s)
Definition: solgame.cpp:4

Referenced by update_changed_extent_ref().

◆ find_extent_shared_data_refcount()

uint32_t find_extent_shared_data_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  parent,
PIRP  Irp 
)

Definition at line 2220 of file extent-tree.c.

2220 {
2222 KEY searchkey;
2224 uint64_t inline_rc;
2225 EXTENT_ITEM* ei;
2226 uint32_t len;
2227 uint8_t* ptr;
2228
2229 searchkey.obj_id = address;
2230 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
2231 searchkey.offset = 0xffffffffffffffff;
2232
2233 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2234 if (!NT_SUCCESS(Status)) {
2235 ERR("error - find_item returned %08lx\n", Status);
2236 return 0;
2237 }
2238
2240 TRACE("could not find address %I64x in extent tree\n", address);
2241 return 0;
2242 }
2243
2244 if (tp.item->size < sizeof(EXTENT_ITEM)) {
2245 ERR("(%I64x,%x,%I64x): size was %u, 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));
2246 return 0;
2247 }
2248
2249 ei = (EXTENT_ITEM*)tp.item->data;
2250 inline_rc = 0;
2251
2252 len = tp.item->size - sizeof(EXTENT_ITEM);
2253 ptr = (uint8_t*)&ei[1];
2254
2255 while (len > 0) {
2256 uint8_t secttype = *ptr;
2257 ULONG sectlen = get_extent_data_len(secttype);
2258 uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
2259
2260 len--;
2261
2262 if (sectlen > len) {
2263 ERR("(%I64x,%x,%I64x): %x bytes left, expecting at least %lx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
2264 return 0;
2265 }
2266
2267 if (sectlen == 0) {
2268 ERR("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
2269 return 0;
2270 }
2271
2272 if (secttype == TYPE_SHARED_DATA_REF) {
2273 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(uint8_t));
2274
2275 if (sectsdr->offset == parent)
2276 return sectsdr->count;
2277 }
2278
2279 len -= sectlen;
2280 ptr += sizeof(uint8_t) + sectlen;
2281 inline_rc += sectcount;
2282 }
2283
2284 // FIXME - what if old?
2285
2286 if (inline_rc == ei->refcount)
2287 return 0;
2288
2289 searchkey.obj_id = address;
2290 searchkey.obj_type = TYPE_SHARED_DATA_REF;
2291 searchkey.offset = parent;
2292
2293 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2294 if (!NT_SUCCESS(Status)) {
2295 ERR("error - find_item returned %08lx\n", Status);
2296 return 0;
2297 }
2298
2299 if (!keycmp(searchkey, tp.item->key)) {
2300 if (tp.item->size < sizeof(uint32_t))
2301 ERR("(%I64x,%x,%I64x) has size %u, not %Iu as expected\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(uint32_t));
2302 else {
2304 return *count;
2305 }
2306 }
2307
2308 return 0;
2309}

Referenced by add_metadata_reloc_extent_item(), and update_tree_extents().

◆ find_extent_shared_tree_refcount()

uint64_t find_extent_shared_tree_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  parent,
PIRP  Irp 
)

Definition at line 2119 of file extent-tree.c.

2119 {
2121 KEY searchkey;
2123 uint64_t inline_rc;
2124 EXTENT_ITEM* ei;
2125 uint32_t len;
2126 uint8_t* ptr;
2127
2128 searchkey.obj_id = address;
2129 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
2130 searchkey.offset = 0xffffffffffffffff;
2131
2132 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2133 if (!NT_SUCCESS(Status)) {
2134 ERR("error - find_item returned %08lx\n", Status);
2135 return 0;
2136 }
2137
2139 TRACE("could not find address %I64x in extent tree\n", address);
2140 return 0;
2141 }
2142
2143 if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->key.offset != Vcb->superblock.node_size) {
2144 ERR("extent %I64x had size %I64x, not %x as expected\n", address, tp.item->key.offset, Vcb->superblock.node_size);
2145 return 0;
2146 }
2147
2148 if (tp.item->size < sizeof(EXTENT_ITEM)) {
2149 ERR("(%I64x,%x,%I64x): size was %u, 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));
2150 return 0;
2151 }
2152
2153 ei = (EXTENT_ITEM*)tp.item->data;
2154 inline_rc = 0;
2155
2156 len = tp.item->size - sizeof(EXTENT_ITEM);
2157 ptr = (uint8_t*)&ei[1];
2158
2159 if (searchkey.obj_type == TYPE_EXTENT_ITEM && ei->flags & EXTENT_ITEM_TREE_BLOCK) {
2160 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
2161 ERR("(%I64x,%x,%I64x): size was %u, expected at least %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset,
2162 tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
2163 return 0;
2164 }
2165
2166 len -= sizeof(EXTENT_ITEM2);
2167 ptr += sizeof(EXTENT_ITEM2);
2168 }
2169
2170 while (len > 0) {
2171 uint8_t secttype = *ptr;
2172 ULONG sectlen = get_extent_data_len(secttype);
2173 uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
2174
2175 len--;
2176
2177 if (sectlen > len) {
2178 ERR("(%I64x,%x,%I64x): %x bytes left, expecting at least %lx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
2179 return 0;
2180 }
2181
2182 if (sectlen == 0) {
2183 ERR("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
2184 return 0;
2185 }
2186
2187 if (secttype == TYPE_SHARED_BLOCK_REF) {
2188 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(uint8_t));
2189
2190 if (sectsbr->offset == parent)
2191 return 1;
2192 }
2193
2194 len -= sectlen;
2195 ptr += sizeof(uint8_t) + sectlen;
2196 inline_rc += sectcount;
2197 }
2198
2199 // FIXME - what if old?
2200
2201 if (inline_rc == ei->refcount)
2202 return 0;
2203
2204 searchkey.obj_id = address;
2205 searchkey.obj_type = TYPE_SHARED_BLOCK_REF;
2206 searchkey.offset = parent;
2207
2208 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2209 if (!NT_SUCCESS(Status)) {
2210 ERR("error - find_item returned %08lx\n", Status);
2211 return 0;
2212 }
2213
2214 if (!keycmp(searchkey, tp.item->key))
2215 return 1;
2216
2217 return 0;
2218}

Referenced by add_metadata_reloc_extent_item(), and update_tree_extents().

◆ free_extent_refs()

static void free_extent_refs ( LIST_ENTRY extent_refs)
static

Definition at line 67 of file extent-tree.c.

67 {
68 while (!IsListEmpty(extent_refs)) {
69 LIST_ENTRY* le = RemoveHeadList(extent_refs);
71
72 ExFreePool(er);
73 }
74}
#define RemoveHeadList(ListHead)
Definition: env_spec_w32.h:964

Referenced by convert_old_extent().

◆ get_changed_extent_item()

static changed_extent * get_changed_extent_item ( chunk c,
uint64_t  address,
uint64_t  size,
bool  no_csum 
)
static

Definition at line 1916 of file extent-tree.c.

1916 {
1917 LIST_ENTRY* le;
1918 changed_extent* ce;
1919
1920 le = c->changed_extents.Flink;
1921 while (le != &c->changed_extents) {
1923
1924 if (ce->address == address && ce->size == size)
1925 return ce;
1926
1927 le = le->Flink;
1928 }
1929
1931 if (!ce) {
1932 ERR("out of memory\n");
1933 return NULL;
1934 }
1935
1936 ce->address = address;
1937 ce->size = size;
1938 ce->old_size = size;
1939 ce->count = 0;
1940 ce->old_count = 0;
1941 ce->no_csum = no_csum;
1942 ce->superseded = false;
1945
1946 InsertTailList(&c->changed_extents, &ce->list_entry);
1947
1948 return ce;
1949}
uint64_t address
Definition: btrfs_drv.h:597
uint64_t old_count
Definition: btrfs_drv.h:601
uint64_t old_size
Definition: btrfs_drv.h:599
LIST_ENTRY old_refs
Definition: btrfs_drv.h:605
LIST_ENTRY list_entry
Definition: btrfs_drv.h:606
uint64_t size
Definition: btrfs_drv.h:598

Referenced by add_changed_extent_ref(), and update_changed_extent_ref().

◆ get_extent_data_ref_hash()

static __inline uint64_t get_extent_data_ref_hash ( EXTENT_DATA_REF edr)
static

Definition at line 45 of file extent-tree.c.

45 {
46 return get_extent_data_ref_hash2(edr->root, edr->objid, edr->offset);
47}

Referenced by get_extent_hash().

◆ get_extent_data_ref_hash2()

uint64_t get_extent_data_ref_hash2 ( uint64_t  root,
uint64_t  objid,
uint64_t  offset 
)

Definition at line 35 of file extent-tree.c.

35 {
36 uint32_t high_crc = 0xffffffff, low_crc = 0xffffffff;
37
38 high_crc = calc_crc32c(high_crc, (uint8_t*)&root, sizeof(uint64_t));
39 low_crc = calc_crc32c(low_crc, (uint8_t*)&objid, sizeof(uint64_t));
40 low_crc = calc_crc32c(low_crc, (uint8_t*)&offset, sizeof(uint64_t));
41
42 return ((uint64_t)high_crc << 31) ^ (uint64_t)low_crc;
43}
crc_func calc_crc32c
Definition: crc32c.c:23
#define uint64_t
Definition: nsiface.idl:62

Referenced by find_extent_data_refcount(), get_extent_data_ref_hash(), and sort_data_reloc_refs().

◆ get_extent_flags()

uint64_t get_extent_flags ( device_extension Vcb,
uint64_t  address,
PIRP  Irp 
)

Definition at line 1835 of file extent-tree.c.

1835 {
1836 KEY searchkey;
1839 EXTENT_ITEM* ei;
1840
1841 searchkey.obj_id = address;
1842 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1843 searchkey.offset = 0xffffffffffffffff;
1844
1845 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1846 if (!NT_SUCCESS(Status)) {
1847 ERR("error - find_item returned %08lx\n", Status);
1848 return 0;
1849 }
1850
1851 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1853 ei = (EXTENT_ITEM*)tp.item->data;
1854
1855 return ei->flags;
1856 }
1857
1859 ERR("couldn't find %I64x in extent tree\n", address);
1860 return 0;
1861 }
1862
1863 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1864 return 0;
1865 else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1866 ERR("(%I64x,%x,%I64x) was %x bytes, expected at least %Ix\n", tp.item->key.obj_id, tp.item->key.obj_type,
1867 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1868 return 0;
1869 }
1870
1871 ei = (EXTENT_ITEM*)tp.item->data;
1872
1873 return ei->flags;
1874}

Referenced by update_tree_extents().

◆ get_extent_hash()

static uint64_t get_extent_hash ( uint8_t  type,
void data 
)
static

Definition at line 49 of file extent-tree.c.

49 {
52 } else if (type == TYPE_SHARED_BLOCK_REF) {
54 return sbr->offset;
55 } else if (type == TYPE_SHARED_DATA_REF) {
57 return sdr->offset;
58 } else if (type == TYPE_TREE_BLOCK_REF) {
60 return tbr->offset;
61 } else {
62 ERR("unhandled extent type %x\n", type);
63 return 0;
64 }
65}
static __inline uint64_t get_extent_data_ref_hash(EXTENT_DATA_REF *edr)
Definition: extent-tree.c:45

Referenced by construct_extent_item(), decrease_extent_refcount(), and increase_extent_refcount().

◆ get_extent_refcount()

uint64_t get_extent_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
PIRP  Irp 
)

Definition at line 1651 of file extent-tree.c.

1651 {
1652 KEY searchkey;
1655 EXTENT_ITEM* ei;
1656
1657 searchkey.obj_id = address;
1658 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1659 searchkey.offset = 0xffffffffffffffff;
1660
1661 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1662 if (!NT_SUCCESS(Status)) {
1663 ERR("error - find_item returned %08lx\n", Status);
1664 return 0;
1665 }
1666
1667 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1669 ei = (EXTENT_ITEM*)tp.item->data;
1670
1671 return ei->refcount;
1672 }
1673
1675 ERR("couldn't find (%I64x,%x,%I64x) in extent tree\n", address, TYPE_EXTENT_ITEM, size);
1676 return 0;
1677 } else if (tp.item->key.offset != size) {
1678 ERR("extent %I64x had size %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
1679 return 0;
1680 }
1681
1682 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1684
1685 return eiv0->refcount;
1686 } else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1687 ERR("(%I64x,%x,%I64x) was %x bytes, expected at least %Ix\n", tp.item->key.obj_id, tp.item->key.obj_type,
1688 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1689 return 0;
1690 }
1691
1692 ei = (EXTENT_ITEM*)tp.item->data;
1693
1694 return ei->refcount;
1695}
uint32_t refcount
Definition: btrfs.h:403

Referenced by is_extent_unique(), reduce_tree_extent(), and update_tree_extents().

◆ increase_extent_refcount()

NTSTATUS increase_extent_refcount ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint8_t  type,
void data,
KEY firstitem,
uint8_t  level,
PIRP  Irp 
)

Definition at line 454 of file extent-tree.c.

454 {
456 KEY searchkey;
458 ULONG len, max_extent_item_size;
460 EXTENT_ITEM* ei;
461 uint8_t* ptr;
462 uint64_t inline_rc, offset;
463 uint8_t* data2;
464 EXTENT_ITEM* newei;
465 bool skinny;
466 bool is_tree = type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF;
467
468 if (datalen == 0) {
469 ERR("unrecognized extent type %x\n", type);
471 }
472
473 searchkey.obj_id = address;
474 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
475 searchkey.offset = 0xffffffffffffffff;
476
477 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
478 if (!NT_SUCCESS(Status)) {
479 ERR("error - find_item returned %08lx\n", Status);
480 return Status;
481 }
482
483 // If entry doesn't exist yet, create new inline extent item
484
486 uint16_t eisize;
487
488 eisize = sizeof(EXTENT_ITEM);
489 if (is_tree && !(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) eisize += sizeof(EXTENT_ITEM2);
490 eisize += sizeof(uint8_t);
491 eisize += datalen;
492
494 if (!ei) {
495 ERR("out of memory\n");
497 }
498
500 ei->generation = Vcb->superblock.generation;
502 ptr = (uint8_t*)&ei[1];
503
504 if (is_tree && !(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
506 ei2->firstitem = *firstitem;
507 ei2->level = level;
508 ptr = (uint8_t*)&ei2[1];
509 }
510
511 *ptr = type;
513
514 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && is_tree)
515 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, ei, eisize, NULL, Irp);
516 else
517 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, eisize, NULL, Irp);
518
519 if (!NT_SUCCESS(Status)) {
520 ERR("insert_tree_item returned %08lx\n", Status);
521 return Status;
522 }
523
524 return STATUS_SUCCESS;
525 } else if (tp.item->key.obj_id == address && tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->key.offset != size) {
526 ERR("extent %I64x exists, but with size %I64x rather than %I64x expected\n", tp.item->key.obj_id, tp.item->key.offset, size);
528 }
529
531
532 if (tp.item->size == sizeof(EXTENT_ITEM_V0) && !skinny) {
533 Status = convert_old_extent(Vcb, address, is_tree, firstitem, level, Irp);
534
535 if (!NT_SUCCESS(Status)) {
536 ERR("convert_old_extent returned %08lx\n", Status);
537 return Status;
538 }
539
540 return increase_extent_refcount(Vcb, address, size, type, data, firstitem, level, Irp);
541 }
542
543 if (tp.item->size < sizeof(EXTENT_ITEM)) {
544 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));
546 }
547
548 ei = (EXTENT_ITEM*)tp.item->data;
549
550 len = tp.item->size - sizeof(EXTENT_ITEM);
551 ptr = (uint8_t*)&ei[1];
552
553 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
554 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
555 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) + sizeof(EXTENT_ITEM2));
557 }
558
559 len -= sizeof(EXTENT_ITEM2);
560 ptr += sizeof(EXTENT_ITEM2);
561 }
562
563 inline_rc = 0;
564
565 // Loop through existing inline extent entries
566
567 while (len > 0) {
568 uint8_t secttype = *ptr;
569 ULONG sectlen = get_extent_data_len(secttype);
570 uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
571
572 len--;
573
574 if (sectlen > len) {
575 ERR("(%I64x,%x,%I64x): %lx bytes left, expecting at least %lx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
577 }
578
579 if (sectlen == 0) {
580 ERR("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
582 }
583
584 // If inline extent already present, increase refcount and return
585
586 if (secttype == type) {
587 if (type == TYPE_EXTENT_DATA_REF) {
588 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(uint8_t));
590
591 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
593 EXTENT_DATA_REF* sectedr2;
594
596 if (!newei) {
597 ERR("out of memory\n");
599 }
600
601 RtlCopyMemory(newei, tp.item->data, tp.item->size);
602
603 newei->refcount += rc;
604
605 sectedr2 = (EXTENT_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectedr - tp.item->data));
606 sectedr2->count += rc;
607
609 if (!NT_SUCCESS(Status)) {
610 ERR("delete_tree_item returned %08lx\n", Status);
611 return Status;
612 }
613
615 if (!NT_SUCCESS(Status)) {
616 ERR("insert_tree_item returned %08lx\n", Status);
617 return Status;
618 }
619
620 return STATUS_SUCCESS;
621 }
622 } else if (type == TYPE_TREE_BLOCK_REF) {
623 TREE_BLOCK_REF* secttbr = (TREE_BLOCK_REF*)(ptr + sizeof(uint8_t));
625
626 if (secttbr->offset == tbr->offset) {
627 TRACE("trying to increase refcount of non-shared tree extent\n");
628 return STATUS_SUCCESS;
629 }
630 } else if (type == TYPE_SHARED_BLOCK_REF) {
631 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(uint8_t));
633
634 if (sectsbr->offset == sbr->offset)
635 return STATUS_SUCCESS;
636 } else if (type == TYPE_SHARED_DATA_REF) {
637 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(uint8_t));
639
640 if (sectsdr->offset == sdr->offset) {
642 SHARED_DATA_REF* sectsdr2;
643
645 if (!newei) {
646 ERR("out of memory\n");
648 }
649
650 RtlCopyMemory(newei, tp.item->data, tp.item->size);
651
652 newei->refcount += rc;
653
654 sectsdr2 = (SHARED_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectsdr - tp.item->data));
655 sectsdr2->count += rc;
656
658 if (!NT_SUCCESS(Status)) {
659 ERR("delete_tree_item returned %08lx\n", Status);
660 return Status;
661 }
662
664 if (!NT_SUCCESS(Status)) {
665 ERR("insert_tree_item returned %08lx\n", Status);
666 return Status;
667 }
668
669 return STATUS_SUCCESS;
670 }
671 } else {
672 ERR("unhandled extent type %x\n", type);
674 }
675 }
676
677 len -= sectlen;
678 ptr += sizeof(uint8_t) + sectlen;
679 inline_rc += sectcount;
680 }
681
683
684 max_extent_item_size = (Vcb->superblock.node_size >> 4) - sizeof(leaf_node);
685
686 // If we can, add entry as inline extent item
687
688 if (inline_rc == ei->refcount && tp.item->size + sizeof(uint8_t) + datalen < max_extent_item_size) {
689 len = tp.item->size - sizeof(EXTENT_ITEM);
690 ptr = (uint8_t*)&ei[1];
691
692 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
693 len -= sizeof(EXTENT_ITEM2);
694 ptr += sizeof(EXTENT_ITEM2);
695 }
696
697 // Confusingly, it appears that references are sorted forward by type (i.e. EXTENT_DATA_REFs before
698 // SHARED_DATA_REFs), but then backwards by hash...
699
700 while (len > 0) {
701 uint8_t secttype = *ptr;
702 ULONG sectlen = get_extent_data_len(secttype);
703
704 if (secttype > type)
705 break;
706
707 if (secttype == type) {
708 uint64_t sectoff = get_extent_hash(secttype, ptr + 1);
709
710 if (sectoff < offset)
711 break;
712 }
713
714 len -= sectlen + sizeof(uint8_t);
715 ptr += sizeof(uint8_t) + sectlen;
716 }
717
719 RtlCopyMemory(newei, tp.item->data, ptr - tp.item->data);
720
722
723 if (len > 0)
724 RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data) + sizeof(uint8_t) + datalen, ptr, len);
725
726 ptr = (ptr - tp.item->data) + (uint8_t*)newei;
727
728 *ptr = type;
730
732 if (!NT_SUCCESS(Status)) {
733 ERR("delete_tree_item returned %08lx\n", Status);
734 return Status;
735 }
736
737 Status = insert_tree_item(Vcb, Vcb->extent_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newei, tp.item->size + sizeof(uint8_t) + datalen, NULL, Irp);
738 if (!NT_SUCCESS(Status)) {
739 ERR("insert_tree_item returned %08lx\n", Status);
740 return Status;
741 }
742
743 return STATUS_SUCCESS;
744 }
745
746 // Look for existing non-inline entry, and increase refcount if found
747
748 if (inline_rc != ei->refcount) {
749 traverse_ptr tp2;
750
751 searchkey.obj_id = address;
752 searchkey.obj_type = type;
753 searchkey.offset = offset;
754
755 Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, false, Irp);
756 if (!NT_SUCCESS(Status)) {
757 ERR("error - find_item returned %08lx\n", Status);
758 return Status;
759 }
760
761 if (!keycmp(tp2.item->key, searchkey)) {
762 if (type == TYPE_SHARED_DATA_REF && tp2.item->size < sizeof(uint32_t)) {
763 ERR("(%I64x,%x,%I64x) was %x bytes, expecting %Ix\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, sizeof(uint32_t));
765 } else if (type != TYPE_SHARED_DATA_REF && tp2.item->size < datalen) {
766 ERR("(%I64x,%x,%I64x) was %x bytes, expecting %x\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, datalen);
768 }
769
771 if (!data2) {
772 ERR("out of memory\n");
774 }
775
776 RtlCopyMemory(data2, tp2.item->data, tp2.item->size);
777
778 if (type == TYPE_EXTENT_DATA_REF) {
780
782 } else if (type == TYPE_TREE_BLOCK_REF) {
783 TRACE("trying to increase refcount of non-shared tree extent\n");
784 return STATUS_SUCCESS;
785 } else if (type == TYPE_SHARED_BLOCK_REF)
786 return STATUS_SUCCESS;
787 else if (type == TYPE_SHARED_DATA_REF) {
788 uint32_t* sdr = (uint32_t*)data2;
789
791 } else {
792 ERR("unhandled extent type %x\n", type);
794 }
795
796 Status = delete_tree_item(Vcb, &tp2);
797 if (!NT_SUCCESS(Status)) {
798 ERR("delete_tree_item returned %08lx\n", Status);
799 return Status;
800 }
801
802 Status = insert_tree_item(Vcb, Vcb->extent_root, tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, data2, tp2.item->size, NULL, Irp);
803 if (!NT_SUCCESS(Status)) {
804 ERR("insert_tree_item returned %08lx\n", Status);
805 return Status;
806 }
807
809 if (!newei) {
810 ERR("out of memory\n");
812 }
813
814 RtlCopyMemory(newei, tp.item->data, tp.item->size);
815
817
819 if (!NT_SUCCESS(Status)) {
820 ERR("delete_tree_item returned %08lx\n", Status);
821 return Status;
822 }
823
825 if (!NT_SUCCESS(Status)) {
826 ERR("insert_tree_item returned %08lx\n", Status);
827 return Status;
828 }
829
830 return STATUS_SUCCESS;
831 }
832 }
833
834 // Otherwise, add new non-inline entry
835
836 if (type == TYPE_SHARED_DATA_REF) {
838
840 if (!data2) {
841 ERR("out of memory\n");
843 }
844
845 datalen = sizeof(uint32_t);
846
847 *((uint32_t*)data2) = sdr->count;
849 data2 = NULL;
850 datalen = 0;
851 } else {
853 if (!data2) {
854 ERR("out of memory\n");
856 }
857
859 }
860
862 if (!NT_SUCCESS(Status)) {
863 ERR("insert_tree_item returned %08lx\n", Status);
864 return Status;
865 }
866
868 if (!newei) {
869 ERR("out of memory\n");
871 }
872
873 RtlCopyMemory(newei, tp.item->data, tp.item->size);
874
876
878 if (!NT_SUCCESS(Status)) {
879 ERR("delete_tree_item returned %08lx\n", Status);
880 return Status;
881 }
882
884 if (!NT_SUCCESS(Status)) {
885 ERR("insert_tree_item returned %08lx\n", Status);
886 return Status;
887 }
888
889 return STATUS_SUCCESS;
890}
NTSTATUS increase_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:454
Definition: tftpd.h:138

Referenced by add_metadata_reloc_extent_item(), increase_extent_refcount(), increase_extent_refcount_data(), snapshot_tree_copy(), and update_tree_extents().

◆ increase_extent_refcount_data()

NTSTATUS increase_extent_refcount_data ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
uint64_t  root,
uint64_t  inode,
uint64_t  offset,
uint32_t  refcount,
PIRP  Irp 
)

Definition at line 892 of file extent-tree.c.

892 {
893 EXTENT_DATA_REF edr;
894
895 edr.root = root;
896 edr.objid = inode;
897 edr.offset = offset;
898 edr.count = refcount;
899
901}

Referenced by flush_changed_extent(), and snapshot_tree_copy().

◆ is_extent_unique()

bool is_extent_unique ( device_extension Vcb,
uint64_t  address,
uint64_t  size,
PIRP  Irp 
)

Definition at line 1697 of file extent-tree.c.

1697 {
1698 KEY searchkey;
1699 traverse_ptr tp, next_tp;
1701 uint64_t rc, rcrun, root = 0, inode = 0, offset = 0;
1702 uint32_t len;
1703 EXTENT_ITEM* ei;
1704 uint8_t* ptr;
1705 bool b;
1706
1708
1709 if (rc == 1)
1710 return true;
1711
1712 if (rc == 0)
1713 return false;
1714
1715 searchkey.obj_id = address;
1716 searchkey.obj_type = TYPE_EXTENT_ITEM;
1717 searchkey.offset = size;
1718
1719 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1720 if (!NT_SUCCESS(Status)) {
1721 WARN("error - find_item returned %08lx\n", Status);
1722 return false;
1723 }
1724
1725 if (keycmp(tp.item->key, searchkey)) {
1726 WARN("could not find (%I64x,%x,%I64x)\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1727 return false;
1728 }
1729
1730 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1731 return false;
1732
1733 if (tp.item->size < sizeof(EXTENT_ITEM)) {
1734 WARN("(%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));
1735 return false;
1736 }
1737
1738 ei = (EXTENT_ITEM*)tp.item->data;
1739
1740 len = tp.item->size - sizeof(EXTENT_ITEM);
1741 ptr = (uint8_t*)&ei[1];
1742
1743 if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
1744 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
1745 WARN("(%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) + sizeof(EXTENT_ITEM2));
1746 return false;
1747 }
1748
1749 len -= sizeof(EXTENT_ITEM2);
1750 ptr += sizeof(EXTENT_ITEM2);
1751 }
1752
1753 rcrun = 0;
1754
1755 // Loop through inline extent entries
1756
1757 while (len > 0) {
1758 uint8_t secttype = *ptr;
1759 ULONG sectlen = get_extent_data_len(secttype);
1760 uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
1761
1762 len--;
1763
1764 if (sectlen > len) {
1765 WARN("(%I64x,%x,%I64x): %x bytes left, expecting at least %lx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1766 return false;
1767 }
1768
1769 if (sectlen == 0) {
1770 WARN("(%I64x,%x,%I64x): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1771 return false;
1772 }
1773
1774 if (secttype == TYPE_EXTENT_DATA_REF) {
1775 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(uint8_t));
1776
1777 if (root == 0 && inode == 0) {
1778 root = sectedr->root;
1779 inode = sectedr->objid;
1780 offset = sectedr->offset;
1781 } else if (root != sectedr->root || inode != sectedr->objid || offset != sectedr->offset)
1782 return false;
1783 } else
1784 return false;
1785
1786 len -= sectlen;
1787 ptr += sizeof(uint8_t) + sectlen;
1788 rcrun += sectcount;
1789 }
1790
1791 if (rcrun == rc)
1792 return true;
1793
1794 // Loop through non-inlines if some refs still unaccounted for
1795
1796 do {
1797 b = find_next_item(Vcb, &tp, &next_tp, false, Irp);
1798
1799 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == TYPE_EXTENT_DATA_REF) {
1801
1802 if (tp.item->size < sizeof(EXTENT_DATA_REF)) {
1803 WARN("(%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,
1804 tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
1805 return false;
1806 }
1807
1808 if (root == 0 && inode == 0) {
1809 root = edr->root;
1810 inode = edr->objid;
1811 offset = edr->offset;
1812 } else if (root != edr->root || inode != edr->objid || offset != edr->offset)
1813 return false;
1814
1815 rcrun += edr->count;
1816 }
1817
1818 if (rcrun == rc)
1819 return true;
1820
1821 if (b) {
1822 tp = next_tp;
1823
1824 if (tp.item->key.obj_id > searchkey.obj_id)
1825 break;
1826 }
1827 } while (b);
1828
1829 // If we reach this point, there's still some refs unaccounted for somewhere.
1830 // Return false in case we mess things up elsewhere.
1831
1832 return false;
1833}
uint64_t get_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, PIRP Irp)
Definition: extent-tree.c:1651
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define b
Definition: ke_i.h:79

◆ sort_extent_refs()

static void sort_extent_refs ( LIST_ENTRY extent_refs)
static

Definition at line 172 of file extent-tree.c.

172 {
173 LIST_ENTRY newlist;
174
175 if (IsListEmpty(extent_refs))
176 return;
177
178 // insertion sort
179
180 InitializeListHead(&newlist);
181
182 while (!IsListEmpty(extent_refs)) {
184 LIST_ENTRY* le;
185 bool inserted = false;
186
187 le = newlist.Flink;
188 while (le != &newlist) {
190
191 if (er->type < er2->type || (er->type == er2->type && er->hash > er2->hash)) {
193 inserted = true;
194 break;
195 }
196
197 le = le->Flink;
198 }
199
200 if (!inserted)
201 InsertTailList(&newlist, &er->list_entry);
202 }
203
204 newlist.Flink->Blink = extent_refs;
205 newlist.Blink->Flink = extent_refs;
206 extent_refs->Flink = newlist.Flink;
207 extent_refs->Blink = newlist.Blink;
208}
#define InsertHeadList(ListHead, Entry)
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122

Referenced by construct_extent_item().

◆ update_changed_extent_ref()

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 
)

Definition at line 1951 of file extent-tree.c.

1952 {
1953 LIST_ENTRY* le;
1954 changed_extent* ce;
1955 changed_extent_ref* cer;
1957 KEY searchkey;
1959 uint32_t old_count;
1960
1961 ExAcquireResourceExclusiveLite(&c->changed_extents_lock, true);
1962
1963 ce = get_changed_extent_item(c, address, size, no_csum);
1964
1965 if (!ce) {
1966 ERR("get_changed_extent_item failed\n");
1968 goto end;
1969 }
1970
1971 if (IsListEmpty(&ce->refs) && IsListEmpty(&ce->old_refs)) { // new entry
1972 searchkey.obj_id = address;
1973 searchkey.obj_type = TYPE_EXTENT_ITEM;
1974 searchkey.offset = 0xffffffffffffffff;
1975
1976 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1977 if (!NT_SUCCESS(Status)) {
1978 ERR("error - find_item returned %08lx\n", Status);
1979 goto end;
1980 }
1981
1982 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1983 ERR("could not find address %I64x in extent tree\n", address);
1985 goto end;
1986 }
1987
1988 if (tp.item->key.offset != size) {
1989 ERR("extent %I64x had size %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
1991 goto end;
1992 }
1993
1994 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1996
1997 ce->count = ce->old_count = eiv0->refcount;
1998 } else if (tp.item->size >= sizeof(EXTENT_ITEM)) {
2000
2001 ce->count = ce->old_count = ei->refcount;
2002 } else {
2003 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));
2005 goto end;
2006 }
2007 }
2008
2009 le = ce->refs.Flink;
2010 while (le != &ce->refs) {
2012
2013 if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == root && cer->edr.objid == objid && cer->edr.offset == offset) {
2014 ce->count += count;
2015 cer->edr.count += count;
2017
2018 if (superseded)
2019 ce->superseded = true;
2020
2021 goto end;
2022 }
2023
2024 le = le->Flink;
2025 }
2026
2027 old_count = find_extent_data_refcount(Vcb, address, size, root, objid, offset, Irp);
2028
2029 if (old_count > 0) {
2031
2032 if (!cer) {
2033 ERR("out of memory\n");
2035 goto end;
2036 }
2037
2039 cer->edr.root = root;
2040 cer->edr.objid = objid;
2041 cer->edr.offset = offset;
2042 cer->edr.count = old_count;
2043
2044 InsertTailList(&ce->old_refs, &cer->list_entry);
2045 }
2046
2048
2049 if (!cer) {
2050 ERR("out of memory\n");
2052 goto end;
2053 }
2054
2056 cer->edr.root = root;
2057 cer->edr.objid = objid;
2058 cer->edr.offset = offset;
2059 cer->edr.count = old_count + count;
2060
2061 InsertTailList(&ce->refs, &cer->list_entry);
2062
2063 ce->count += count;
2064
2065 if (superseded)
2066 ce->superseded = true;
2067
2069
2070end:
2071 ExReleaseResourceLite(&c->changed_extents_lock);
2072
2073 return Status;
2074}
#define ExAcquireResourceExclusiveLite(res, wait)
Definition: env_spec_w32.h:615
static uint32_t find_extent_data_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, PIRP Irp)
Definition: extent-tree.c:1569
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1822

Referenced by __attribute__(), duplicate_extents(), flush_fcb(), move_across_subvols(), and rationalize_extents().

◆ update_extent_flags()

void update_extent_flags ( device_extension Vcb,
uint64_t  address,
uint64_t  flags,
PIRP  Irp 
)

Definition at line 1876 of file extent-tree.c.

1876 {
1877 KEY searchkey;
1880 EXTENT_ITEM* ei;
1881
1882 searchkey.obj_id = address;
1883 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1884 searchkey.offset = 0xffffffffffffffff;
1885
1886 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1887 if (!NT_SUCCESS(Status)) {
1888 ERR("error - find_item returned %08lx\n", Status);
1889 return;
1890 }
1891
1892 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1894 ei = (EXTENT_ITEM*)tp.item->data;
1895 ei->flags = flags;
1896 return;
1897 }
1898
1900 ERR("couldn't find %I64x in extent tree\n", address);
1901 return;
1902 }
1903
1904 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1905 return;
1906 else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1907 ERR("(%I64x,%x,%I64x) was %x bytes, expected at least %Ix\n", tp.item->key.obj_id, tp.item->key.obj_type,
1908 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1909 return;
1910 }
1911
1912 ei = (EXTENT_ITEM*)tp.item->data;
1913 ei->flags = flags;
1914}

Referenced by update_tree_extents().