1 /* Copyright (c) Mark Harmstone 2016-17
2 *
3 * This file is part of WinBtrfs.
4 *
5 * WinBtrfs is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Lesser General Public Licence as published by
7 * the Free Software Foundation, either version 3 of the Licence, or
8 * (at your option) any later version.
9 *
10 * WinBtrfs is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public Licence for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public Licence
16 * along with WinBtrfs. If not, see <http://www.gnu.org/licenses/>. */
17
18 #include "btrfs_drv.h"
19 #include "crc32c.h"
20
21 typedef struct {
22 uint8_t type;
23
24 union {
25 EXTENT_DATA_REF edr;
26 SHARED_DATA_REF sdr;
27 TREE_BLOCK_REF tbr;
28 SHARED_BLOCK_REF sbr;
29 };
30
31 uint64_t hash;
32 LIST_ENTRY list_entry;
33 } extent_ref;
34
get_extent_data_ref_hash2(uint64_t root,uint64_t objid,uint64_t offset)35 uint64_t get_extent_data_ref_hash2(uint64_t root, uint64_t objid, uint64_t offset) {
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 }
44
get_extent_data_ref_hash(EXTENT_DATA_REF * edr)45 static __inline uint64_t get_extent_data_ref_hash(EXTENT_DATA_REF* edr) {
46 return get_extent_data_ref_hash2(edr->root, edr->objid, edr->offset);
47 }
48
get_extent_hash(uint8_t type,void * data)49 static uint64_t get_extent_hash(uint8_t type, void* data) {
50 if (type == TYPE_EXTENT_DATA_REF) {
51 return get_extent_data_ref_hash((EXTENT_DATA_REF*)data);
52 } else if (type == TYPE_SHARED_BLOCK_REF) {
53 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
54 return sbr->offset;
55 } else if (type == TYPE_SHARED_DATA_REF) {
56 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
57 return sdr->offset;
58 } else if (type == TYPE_TREE_BLOCK_REF) {
59 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
60 return tbr->offset;
61 } else {
62 ERR("unhandled extent type %x\n", type);
63 return 0;
64 }
65 }
66
free_extent_refs(LIST_ENTRY * extent_refs)67 static void free_extent_refs(LIST_ENTRY* extent_refs) {
68 while (!IsListEmpty(extent_refs)) {
69 LIST_ENTRY* le = RemoveHeadList(extent_refs);
70 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
71
72 ExFreePool(er);
73 }
74 }
75
add_shared_data_extent_ref(LIST_ENTRY * extent_refs,uint64_t parent,uint32_t count)76 static NTSTATUS add_shared_data_extent_ref(LIST_ENTRY* extent_refs, uint64_t parent, uint32_t count) {
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) {
84 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
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
95 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
96 if (!er2) {
97 ERR("out of memory\n");
98 return STATUS_INSUFFICIENT_RESOURCES;
99 }
100
101 er2->type = TYPE_SHARED_DATA_REF;
102 er2->sdr.offset = parent;
103 er2->sdr.count = count;
104
105 InsertTailList(extent_refs, &er2->list_entry);
106
107 return STATUS_SUCCESS;
108 }
109
add_shared_block_extent_ref(LIST_ENTRY * extent_refs,uint64_t parent)110 static NTSTATUS add_shared_block_extent_ref(LIST_ENTRY* extent_refs, uint64_t parent) {
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) {
118 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
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
127 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
128 if (!er2) {
129 ERR("out of memory\n");
130 return STATUS_INSUFFICIENT_RESOURCES;
131 }
132
133 er2->type = TYPE_SHARED_BLOCK_REF;
134 er2->sbr.offset = parent;
135
136 InsertTailList(extent_refs, &er2->list_entry);
137
138 return STATUS_SUCCESS;
139 }
140
add_tree_block_extent_ref(LIST_ENTRY * extent_refs,uint64_t root)141 static NTSTATUS add_tree_block_extent_ref(LIST_ENTRY* extent_refs, uint64_t root) {
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) {
149 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
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
158 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
159 if (!er2) {
160 ERR("out of memory\n");
161 return STATUS_INSUFFICIENT_RESOURCES;
162 }
163
164 er2->type = TYPE_TREE_BLOCK_REF;
165 er2->tbr.offset = root;
166
167 InsertTailList(extent_refs, &er2->list_entry);
168
169 return STATUS_SUCCESS;
170 }
171
sort_extent_refs(LIST_ENTRY * extent_refs)172 static void sort_extent_refs(LIST_ENTRY* extent_refs) {
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)) {
183 extent_ref* er = CONTAINING_RECORD(RemoveHeadList(extent_refs), extent_ref, list_entry);
184 LIST_ENTRY* le;
185 bool inserted = false;
186
187 le = newlist.Flink;
188 while (le != &newlist) {
189 extent_ref* er2 = CONTAINING_RECORD(le, extent_ref, list_entry);
190
191 if (er->type < er2->type || (er->type == er2->type && er->hash > er2->hash)) {
192 InsertHeadList(le->Blink, &er->list_entry);
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 }
209
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)210 static NTSTATUS construct_extent_item(device_extension* Vcb, uint64_t address, uint64_t size, uint64_t flags, LIST_ENTRY* extent_refs,
211 KEY* firstitem, uint8_t level, PIRP Irp) {
212 NTSTATUS Status;
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
231 if (flags & EXTENT_ITEM_TREE_BLOCK)
232 inline_len += sizeof(EXTENT_ITEM2);
233
234 le = extent_refs->Flink;
235 while (le != extent_refs) {
236 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
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) {
244 RemoveEntryList(&er->list_entry);
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");
269 return STATUS_INSUFFICIENT_RESOURCES;
270 }
271
272 ei->refcount = refcount;
273 ei->generation = Vcb->superblock.generation;
274 ei->flags = flags;
275
276 if (flags & EXTENT_ITEM_TREE_BLOCK) {
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) {
299 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
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) {
327 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
328 uint16_t len;
329 uint8_t* data;
330
331 if (er->type == TYPE_EXTENT_DATA_REF) {
332 len = sizeof(EXTENT_DATA_REF);
333
334 data = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
335
336 if (!data) {
337 ERR("out of memory\n");
338 return STATUS_INSUFFICIENT_RESOURCES;
339 }
340
341 RtlCopyMemory(data, &er->edr, len);
342 } else if (er->type == TYPE_SHARED_DATA_REF) {
343 len = sizeof(uint32_t);
344
345 data = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
346
347 if (!data) {
348 ERR("out of memory\n");
349 return STATUS_INSUFFICIENT_RESOURCES;
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 }
371
convert_old_extent(device_extension * Vcb,uint64_t address,bool tree,KEY * firstitem,uint8_t level,PIRP Irp)372 static NTSTATUS convert_old_extent(device_extension* Vcb, uint64_t address, bool tree, KEY* firstitem, uint8_t level, PIRP Irp) {
373 NTSTATUS Status;
374 KEY searchkey;
375 traverse_ptr tp, next_tp;
376 LIST_ENTRY extent_refs;
377 uint64_t size;
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);
393 return STATUS_INTERNAL_ERROR;
394 }
395
396 size = tp.item->key.offset;
397
398 Status = delete_tree_item(Vcb, &tp);
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
407 if (tp.item->key.obj_id == address && tp.item->key.obj_type == TYPE_EXTENT_REF_V0 && tp.item->size >= sizeof(EXTENT_REF_V0)) {
408 EXTENT_REF_V0* erv0 = (EXTENT_REF_V0*)tp.item->data;
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 {
418 Status = add_shared_block_extent_ref(&extent_refs, tp.item->key.offset);
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
432 Status = delete_tree_item(Vcb, &tp);
433 if (!NT_SUCCESS(Status)) {
434 ERR("delete_tree_item returned %08lx\n", Status);
435 goto end;
436 }
437 }
438
439 if (tp.item->key.obj_id > address || tp.item->key.obj_type > TYPE_EXTENT_REF_V0)
440 break;
441 }
442
443 Status = construct_extent_item(Vcb, address, size, tree ? (EXTENT_ITEM_TREE_BLOCK | EXTENT_ITEM_SHARED_BACKREFS) : EXTENT_ITEM_DATA,
444 &extent_refs, firstitem, level, Irp);
445 if (!NT_SUCCESS(Status))
446 ERR("construct_extent_item returned %08lx\n", Status);
447
448 end:
449 free_extent_refs(&extent_refs);
450
451 return Status;
452 }
453
increase_extent_refcount(device_extension * Vcb,uint64_t address,uint64_t size,uint8_t type,void * data,KEY * firstitem,uint8_t level,PIRP Irp)454 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) {
455 NTSTATUS Status;
456 KEY searchkey;
457 traverse_ptr tp;
458 ULONG len, max_extent_item_size;
459 uint16_t datalen = get_extent_data_len(type);
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);
470 return STATUS_INTERNAL_ERROR;
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
485 if (tp.item->key.obj_id != searchkey.obj_id || (tp.item->key.obj_type != TYPE_EXTENT_ITEM && tp.item->key.obj_type != TYPE_METADATA_ITEM)) {
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
493 ei = ExAllocatePoolWithTag(PagedPool, eisize, ALLOC_TAG);
494 if (!ei) {
495 ERR("out of memory\n");
496 return STATUS_INSUFFICIENT_RESOURCES;
497 }
498
499 ei->refcount = get_extent_data_refcount(type, data);
500 ei->generation = Vcb->superblock.generation;
501 ei->flags = is_tree ? EXTENT_ITEM_TREE_BLOCK : EXTENT_ITEM_DATA;
502 ptr = (uint8_t*)&ei[1];
503
504 if (is_tree && !(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
505 EXTENT_ITEM2* ei2 = (EXTENT_ITEM2*)ptr;
506 ei2->firstitem = *firstitem;
507 ei2->level = level;
508 ptr = (uint8_t*)&ei2[1];
509 }
510
511 *ptr = type;
512 RtlCopyMemory(ptr + 1, data, datalen);
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);
527 return STATUS_INTERNAL_ERROR;
528 }
529
530 skinny = tp.item->key.obj_type == TYPE_METADATA_ITEM;
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));
545 return STATUS_INTERNAL_ERROR;
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));
556 return STATUS_INTERNAL_ERROR;
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);
576 return STATUS_INTERNAL_ERROR;
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);
581 return STATUS_INTERNAL_ERROR;
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));
589 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
590
591 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
592 uint32_t rc = get_extent_data_refcount(type, data);
593 EXTENT_DATA_REF* sectedr2;
594
595 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
596 if (!newei) {
597 ERR("out of memory\n");
598 return STATUS_INSUFFICIENT_RESOURCES;
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
608 Status = delete_tree_item(Vcb, &tp);
609 if (!NT_SUCCESS(Status)) {
610 ERR("delete_tree_item returned %08lx\n", Status);
611 return Status;
612 }
613
614 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, NULL, Irp);
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));
624 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
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));
632 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
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));
638 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
639
640 if (sectsdr->offset == sdr->offset) {
641 uint32_t rc = get_extent_data_refcount(type, data);
642 SHARED_DATA_REF* sectsdr2;
643
644 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
645 if (!newei) {
646 ERR("out of memory\n");
647 return STATUS_INSUFFICIENT_RESOURCES;
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
657 Status = delete_tree_item(Vcb, &tp);
658 if (!NT_SUCCESS(Status)) {
659 ERR("delete_tree_item returned %08lx\n", Status);
660 return Status;
661 }
662
663 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, NULL, Irp);
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);
673 return STATUS_INTERNAL_ERROR;
674 }
675 }
676
677 len -= sectlen;
678 ptr += sizeof(uint8_t) + sectlen;
679 inline_rc += sectcount;
680 }
681
682 offset = get_extent_hash(type, data);
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
718 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size + sizeof(uint8_t) + datalen, ALLOC_TAG);
719 RtlCopyMemory(newei, tp.item->data, ptr - tp.item->data);
720
721 newei->refcount += get_extent_data_refcount(type, data);
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;
729 RtlCopyMemory(ptr + 1, data, datalen);
730
731 Status = delete_tree_item(Vcb, &tp);
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));
764 return STATUS_INTERNAL_ERROR;
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);
767 return STATUS_INTERNAL_ERROR;
768 }
769
770 data2 = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
771 if (!data2) {
772 ERR("out of memory\n");
773 return STATUS_INSUFFICIENT_RESOURCES;
774 }
775
776 RtlCopyMemory(data2, tp2.item->data, tp2.item->size);
777
778 if (type == TYPE_EXTENT_DATA_REF) {
779 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data2;
780
781 edr->count += get_extent_data_refcount(type, data);
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
790 *sdr += get_extent_data_refcount(type, data);
791 } else {
792 ERR("unhandled extent type %x\n", type);
793 return STATUS_INTERNAL_ERROR;
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
808 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
809 if (!newei) {
810 ERR("out of memory\n");
811 return STATUS_INSUFFICIENT_RESOURCES;
812 }
813
814 RtlCopyMemory(newei, tp.item->data, tp.item->size);
815
816 newei->refcount += get_extent_data_refcount(type, data);
817
818 Status = delete_tree_item(Vcb, &tp);
819 if (!NT_SUCCESS(Status)) {
820 ERR("delete_tree_item returned %08lx\n", Status);
821 return Status;
822 }
823
824 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, NULL, Irp);
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) {
837 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
838
839 data2 = ExAllocatePoolWithTag(PagedPool, sizeof(uint32_t), ALLOC_TAG);
840 if (!data2) {
841 ERR("out of memory\n");
842 return STATUS_INSUFFICIENT_RESOURCES;
843 }
844
845 datalen = sizeof(uint32_t);
846
847 *((uint32_t*)data2) = sdr->count;
848 } else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF) {
849 data2 = NULL;
850 datalen = 0;
851 } else {
852 data2 = ExAllocatePoolWithTag(PagedPool, datalen, ALLOC_TAG);
853 if (!data2) {
854 ERR("out of memory\n");
855 return STATUS_INSUFFICIENT_RESOURCES;
856 }
857
858 RtlCopyMemory(data2, data, datalen);
859 }
860
861 Status = insert_tree_item(Vcb, Vcb->extent_root, address, type, offset, data2, datalen, NULL, Irp);
862 if (!NT_SUCCESS(Status)) {
863 ERR("insert_tree_item returned %08lx\n", Status);
864 return Status;
865 }
866
867 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
868 if (!newei) {
869 ERR("out of memory\n");
870 return STATUS_INSUFFICIENT_RESOURCES;
871 }
872
873 RtlCopyMemory(newei, tp.item->data, tp.item->size);
874
875 newei->refcount += get_extent_data_refcount(type, data);
876
877 Status = delete_tree_item(Vcb, &tp);
878 if (!NT_SUCCESS(Status)) {
879 ERR("delete_tree_item returned %08lx\n", Status);
880 return Status;
881 }
882
883 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, NULL, Irp);
884 if (!NT_SUCCESS(Status)) {
885 ERR("insert_tree_item returned %08lx\n", Status);
886 return Status;
887 }
888
889 return STATUS_SUCCESS;
890 }
891
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)892 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) {
893 EXTENT_DATA_REF edr;
894
895 edr.root = root;
896 edr.objid = inode;
897 edr.offset = offset;
898 edr.count = refcount;
899
900 return increase_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp);
901 }
902
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)903 NTSTATUS decrease_extent_refcount(device_extension* Vcb, uint64_t address, uint64_t size, uint8_t type, void* data, KEY* firstitem,
904 uint8_t level, uint64_t parent, bool superseded, PIRP Irp) {
905 KEY searchkey;
906 NTSTATUS Status;
907 traverse_ptr tp, tp2;
908 EXTENT_ITEM* ei;
909 ULONG len;
910 uint64_t inline_rc;
911 uint8_t* ptr;
912 uint32_t rc = data ? get_extent_data_refcount(type, data) : 1;
913 ULONG datalen = get_extent_data_len(type);
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);
944 return STATUS_INTERNAL_ERROR;
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);
949 return STATUS_INTERNAL_ERROR;
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
960 return decrease_extent_refcount(Vcb, address, size, type, data, firstitem, level, parent, superseded, Irp);
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));
966 return STATUS_INTERNAL_ERROR;
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));
977 return STATUS_INTERNAL_ERROR;
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);
986 return STATUS_INTERNAL_ERROR;
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));
1013 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
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) {
1020 Status = delete_tree_item(Vcb, &tp);
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");
1045 return STATUS_INSUFFICIENT_RESOURCES;
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
1063 Status = delete_tree_item(Vcb, &tp);
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));
1079 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
1080
1081 if (sectsdr->offset == sdr->offset) {
1082 EXTENT_ITEM* newei;
1083 uint16_t neweilen;
1084
1085 if (ei->refcount == sectsdr->count) {
1086 Status = delete_tree_item(Vcb, &tp);
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");
1111 return STATUS_INSUFFICIENT_RESOURCES;
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
1129 Status = delete_tree_item(Vcb, &tp);
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));
1145 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
1146
1147 if (secttbr->offset == tbr->offset) {
1148 EXTENT_ITEM* newei;
1149 uint16_t neweilen;
1150
1151 if (ei->refcount == 1) {
1152 Status = delete_tree_item(Vcb, &tp);
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");
1166 return STATUS_INSUFFICIENT_RESOURCES;
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
1176 Status = delete_tree_item(Vcb, &tp);
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));
1192 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
1193
1194 if (sectsbr->offset == sbr->offset) {
1195 EXTENT_ITEM* newei;
1196 uint16_t neweilen;
1197
1198 if (ei->refcount == 1) {
1199 Status = delete_tree_item(Vcb, &tp);
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");
1213 return STATUS_INSUFFICIENT_RESOURCES;
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
1223 Status = delete_tree_item(Vcb, &tp);
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
1253 if (type == TYPE_SHARED_DATA_REF)
1254 datalen = sizeof(uint32_t);
1255 else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF)
1256 datalen = 0;
1257
1258 searchkey.obj_id = address;
1259 searchkey.obj_type = type;
1260 searchkey.offset = (type == TYPE_SHARED_DATA_REF || type == TYPE_EXTENT_REF_V0) ? parent : get_extent_hash(type, data);
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;
1280 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)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) {
1286 Status = delete_tree_item(Vcb, &tp);
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) {
1316 EXTENT_DATA_REF* newedr = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
1317
1318 if (!newedr) {
1319 ERR("out of memory\n");
1320 return STATUS_INSUFFICIENT_RESOURCES;
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
1334 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1335 if (!newei) {
1336 ERR("out of memory\n");
1337 return STATUS_INSUFFICIENT_RESOURCES;
1338 }
1339
1340 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1341
1342 newei->refcount -= rc;
1343
1344 Status = delete_tree_item(Vcb, &tp);
1345 if (!NT_SUCCESS(Status)) {
1346 ERR("delete_tree_item returned %08lx\n", Status);
1347 return Status;
1348 }
1349
1350 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, NULL, Irp);
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) {
1362 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
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) {
1369 Status = delete_tree_item(Vcb, &tp);
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) {
1399 uint32_t* newsdr = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
1400
1401 if (!newsdr) {
1402 ERR("out of memory\n");
1403 return STATUS_INSUFFICIENT_RESOURCES;
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
1415 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1416 if (!newei) {
1417 ERR("out of memory\n");
1418 return STATUS_INSUFFICIENT_RESOURCES;
1419 }
1420
1421 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1422
1423 newei->refcount -= rc;
1424
1425 Status = delete_tree_item(Vcb, &tp);
1426 if (!NT_SUCCESS(Status)) {
1427 ERR("delete_tree_item returned %08lx\n", Status);
1428 return Status;
1429 }
1430
1431 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, NULL, Irp);
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) {
1446 Status = delete_tree_item(Vcb, &tp);
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
1467 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1468 if (!newei) {
1469 ERR("out of memory\n");
1470 return STATUS_INSUFFICIENT_RESOURCES;
1471 }
1472
1473 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1474
1475 newei->refcount -= rc;
1476
1477 Status = delete_tree_item(Vcb, &tp);
1478 if (!NT_SUCCESS(Status)) {
1479 ERR("delete_tree_item returned %08lx\n", Status);
1480 return Status;
1481 }
1482
1483 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, NULL, Irp);
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) {
1495 Status = delete_tree_item(Vcb, &tp);
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
1519 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1520 if (!newei) {
1521 ERR("out of memory\n");
1522 return STATUS_INSUFFICIENT_RESOURCES;
1523 }
1524
1525 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1526
1527 newei->refcount -= rc;
1528
1529 Status = delete_tree_item(Vcb, &tp);
1530 if (!NT_SUCCESS(Status)) {
1531 ERR("delete_tree_item returned %08lx\n", Status);
1532 return Status;
1533 }
1534
1535 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, NULL, Irp);
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 }
1547
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)1548 NTSTATUS decrease_extent_refcount_data(device_extension* Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t inode,
1549 uint64_t offset, uint32_t refcount, bool superseded, PIRP Irp) {
1550 EXTENT_DATA_REF edr;
1551
1552 edr.root = root;
1553 edr.objid = inode;
1554 edr.offset = offset;
1555 edr.count = refcount;
1556
1557 return decrease_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, 0, superseded, Irp);
1558 }
1559
decrease_extent_refcount_tree(device_extension * Vcb,uint64_t address,uint64_t size,uint64_t root,uint8_t level,PIRP Irp)1560 NTSTATUS decrease_extent_refcount_tree(device_extension* Vcb, uint64_t address, uint64_t size, uint64_t root,
1561 uint8_t level, PIRP Irp) {
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 }
1568
find_extent_data_refcount(device_extension * Vcb,uint64_t address,uint64_t size,uint64_t root,uint64_t objid,uint64_t offset,PIRP Irp)1569 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) {
1570 NTSTATUS Status;
1571 KEY searchkey;
1572 traverse_ptr tp;
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)) {
1595 EXTENT_ITEM* ei = (EXTENT_ITEM*)tp.item->data;
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 {
1642 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)tp.item->data;
1643
1644 return edr->count;
1645 }
1646 }
1647
1648 return 0;
1649 }
1650
get_extent_refcount(device_extension * Vcb,uint64_t address,uint64_t size,PIRP Irp)1651 uint64_t get_extent_refcount(device_extension* Vcb, uint64_t address, uint64_t size, PIRP Irp) {
1652 KEY searchkey;
1653 traverse_ptr tp;
1654 NTSTATUS Status;
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 &&
1668 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1669 ei = (EXTENT_ITEM*)tp.item->data;
1670
1671 return ei->refcount;
1672 }
1673
1674 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
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)) {
1683 EXTENT_ITEM_V0* eiv0 = (EXTENT_ITEM_V0*)tp.item->data;
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 }
1696
is_extent_unique(device_extension * Vcb,uint64_t address,uint64_t size,PIRP Irp)1697 bool is_extent_unique(device_extension* Vcb, uint64_t address, uint64_t size, PIRP Irp) {
1698 KEY searchkey;
1699 traverse_ptr tp, next_tp;
1700 NTSTATUS Status;
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
1707 rc = get_extent_refcount(Vcb, address, size, Irp);
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) {
1800 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)tp.item->data;
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 }
1834
get_extent_flags(device_extension * Vcb,uint64_t address,PIRP Irp)1835 uint64_t get_extent_flags(device_extension* Vcb, uint64_t address, PIRP Irp) {
1836 KEY searchkey;
1837 traverse_ptr tp;
1838 NTSTATUS Status;
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 &&
1852 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1853 ei = (EXTENT_ITEM*)tp.item->data;
1854
1855 return ei->flags;
1856 }
1857
1858 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
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 }
1875
update_extent_flags(device_extension * Vcb,uint64_t address,uint64_t flags,PIRP Irp)1876 void update_extent_flags(device_extension* Vcb, uint64_t address, uint64_t flags, PIRP Irp) {
1877 KEY searchkey;
1878 traverse_ptr tp;
1879 NTSTATUS Status;
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 &&
1893 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1894 ei = (EXTENT_ITEM*)tp.item->data;
1895 ei->flags = flags;
1896 return;
1897 }
1898
1899 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
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 }
1915
get_changed_extent_item(chunk * c,uint64_t address,uint64_t size,bool no_csum)1916 static changed_extent* get_changed_extent_item(chunk* c, uint64_t address, uint64_t size, bool no_csum) {
1917 LIST_ENTRY* le;
1918 changed_extent* ce;
1919
1920 le = c->changed_extents.Flink;
1921 while (le != &c->changed_extents) {
1922 ce = CONTAINING_RECORD(le, changed_extent, list_entry);
1923
1924 if (ce->address == address && ce->size == size)
1925 return ce;
1926
1927 le = le->Flink;
1928 }
1929
1930 ce = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent), ALLOC_TAG);
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;
1943 InitializeListHead(&ce->refs);
1944 InitializeListHead(&ce->old_refs);
1945
1946 InsertTailList(&c->changed_extents, &ce->list_entry);
1947
1948 return ce;
1949 }
1950
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)1951 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,
1952 bool no_csum, bool superseded, PIRP Irp) {
1953 LIST_ENTRY* le;
1954 changed_extent* ce;
1955 changed_extent_ref* cer;
1956 NTSTATUS Status;
1957 KEY searchkey;
1958 traverse_ptr tp;
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");
1967 Status = STATUS_INTERNAL_ERROR;
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);
1984 Status = STATUS_INTERNAL_ERROR;
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);
1990 Status = STATUS_INTERNAL_ERROR;
1991 goto end;
1992 }
1993
1994 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1995 EXTENT_ITEM_V0* eiv0 = (EXTENT_ITEM_V0*)tp.item->data;
1996
1997 ce->count = ce->old_count = eiv0->refcount;
1998 } else if (tp.item->size >= sizeof(EXTENT_ITEM)) {
1999 EXTENT_ITEM* ei = (EXTENT_ITEM*)tp.item->data;
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));
2004 Status = STATUS_INTERNAL_ERROR;
2005 goto end;
2006 }
2007 }
2008
2009 le = ce->refs.Flink;
2010 while (le != &ce->refs) {
2011 cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
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;
2016 Status = STATUS_SUCCESS;
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) {
2030 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2031
2032 if (!cer) {
2033 ERR("out of memory\n");
2034 Status = STATUS_INSUFFICIENT_RESOURCES;
2035 goto end;
2036 }
2037
2038 cer->type = TYPE_EXTENT_DATA_REF;
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
2047 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2048
2049 if (!cer) {
2050 ERR("out of memory\n");
2051 Status = STATUS_INSUFFICIENT_RESOURCES;
2052 goto end;
2053 }
2054
2055 cer->type = TYPE_EXTENT_DATA_REF;
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
2068 Status = STATUS_SUCCESS;
2069
2070 end:
2071 ExReleaseResourceLite(&c->changed_extents_lock);
2072
2073 return Status;
2074 }
2075
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)2076 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) {
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) {
2090 cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
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
2101 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2102
2103 if (!cer) {
2104 ERR("out of memory\n");
2105 return;
2106 }
2107
2108 cer->type = TYPE_EXTENT_DATA_REF;
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 }
2118
find_extent_shared_tree_refcount(device_extension * Vcb,uint64_t address,uint64_t parent,PIRP Irp)2119 uint64_t find_extent_shared_tree_refcount(device_extension* Vcb, uint64_t address, uint64_t parent, PIRP Irp) {
2120 NTSTATUS Status;
2121 KEY searchkey;
2122 traverse_ptr tp;
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
2138 if (tp.item->key.obj_id != searchkey.obj_id || (tp.item->key.obj_type != TYPE_EXTENT_ITEM && tp.item->key.obj_type != TYPE_METADATA_ITEM)) {
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 }
2219
find_extent_shared_data_refcount(device_extension * Vcb,uint64_t address,uint64_t parent,PIRP Irp)2220 uint32_t find_extent_shared_data_refcount(device_extension* Vcb, uint64_t address, uint64_t parent, PIRP Irp) {
2221 NTSTATUS Status;
2222 KEY searchkey;
2223 traverse_ptr tp;
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
2239 if (tp.item->key.obj_id != searchkey.obj_id || (tp.item->key.obj_type != TYPE_EXTENT_ITEM && tp.item->key.obj_type != TYPE_METADATA_ITEM)) {
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 {
2303 uint32_t* count = (uint32_t*)tp.item->data;
2304 return *count;
2305 }
2306 }
2307
2308 return 0;
2309 }
2310