projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
[SETUP] Remove FSDs which have broken dismount implementation.
[reactos.git] / drivers / filesystems / btrfs / extent-tree.c
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
20 typedef struct {
21 UINT8 type;
22
23 union {
24 EXTENT_DATA_REF edr;
25 SHARED_DATA_REF sdr;
26 TREE_BLOCK_REF tbr;
27 SHARED_BLOCK_REF sbr;
28 };
29
30 UINT64 hash;
31 LIST_ENTRY list_entry;
32 } extent_ref;
33
34 UINT64 get_extent_data_ref_hash2(UINT64 root, UINT64 objid, UINT64 offset) {
35 UINT32 high_crc = 0xffffffff, low_crc = 0xffffffff;
36
37 high_crc = calc_crc32c(high_crc, (UINT8*)&root, sizeof(UINT64));
38 low_crc = calc_crc32c(low_crc, (UINT8*)&objid, sizeof(UINT64));
39 low_crc = calc_crc32c(low_crc, (UINT8*)&offset, sizeof(UINT64));
40
41 return ((UINT64)high_crc << 31) ^ (UINT64)low_crc;
42 }
43
44 static __inline UINT64 get_extent_data_ref_hash(EXTENT_DATA_REF* edr) {
45 return get_extent_data_ref_hash2(edr->root, edr->objid, edr->offset);
46 }
47
48 static UINT64 get_extent_hash(UINT8 type, void* data) {
49 if (type == TYPE_EXTENT_DATA_REF) {
50 return get_extent_data_ref_hash((EXTENT_DATA_REF*)data);
51 } else if (type == TYPE_SHARED_BLOCK_REF) {
52 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
53 return sbr->offset;
54 } else if (type == TYPE_SHARED_DATA_REF) {
55 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
56 return sdr->offset;
57 } else if (type == TYPE_TREE_BLOCK_REF) {
58 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
59 return tbr->offset;
60 } else {
61 ERR("unhandled extent type %x\n", type);
62 return 0;
63 }
64 }
65
66 static void free_extent_refs(LIST_ENTRY* extent_refs) {
67 while (!IsListEmpty(extent_refs)) {
68 LIST_ENTRY* le = RemoveHeadList(extent_refs);
69 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
70
71 ExFreePool(er);
72 }
73 }
74
75 static NTSTATUS add_shared_data_extent_ref(LIST_ENTRY* extent_refs, UINT64 parent, UINT32 count) {
76 extent_ref* er2;
77 LIST_ENTRY* le;
78
79 if (!IsListEmpty(extent_refs)) {
80 le = extent_refs->Flink;
81
82 while (le != extent_refs) {
83 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
84
85 if (er->type == TYPE_SHARED_DATA_REF && er->sdr.offset == parent) {
86 er->sdr.count += count;
87 return STATUS_SUCCESS;
88 }
89
90 le = le->Flink;
91 }
92 }
93
94 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
95 if (!er2) {
96 ERR("out of memory\n");
97 return STATUS_INSUFFICIENT_RESOURCES;
98 }
99
100 er2->type = TYPE_SHARED_DATA_REF;
101 er2->sdr.offset = parent;
102 er2->sdr.count = count;
103
104 InsertTailList(extent_refs, &er2->list_entry);
105
106 return STATUS_SUCCESS;
107 }
108
109 static NTSTATUS add_shared_block_extent_ref(LIST_ENTRY* extent_refs, UINT64 parent) {
110 extent_ref* er2;
111 LIST_ENTRY* le;
112
113 if (!IsListEmpty(extent_refs)) {
114 le = extent_refs->Flink;
115
116 while (le != extent_refs) {
117 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
118
119 if (er->type == TYPE_SHARED_BLOCK_REF && er->sbr.offset == parent)
120 return STATUS_SUCCESS;
121
122 le = le->Flink;
123 }
124 }
125
126 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
127 if (!er2) {
128 ERR("out of memory\n");
129 return STATUS_INSUFFICIENT_RESOURCES;
130 }
131
132 er2->type = TYPE_SHARED_BLOCK_REF;
133 er2->sbr.offset = parent;
134
135 InsertTailList(extent_refs, &er2->list_entry);
136
137 return STATUS_SUCCESS;
138 }
139
140 static NTSTATUS add_tree_block_extent_ref(LIST_ENTRY* extent_refs, UINT64 root) {
141 extent_ref* er2;
142 LIST_ENTRY* le;
143
144 if (!IsListEmpty(extent_refs)) {
145 le = extent_refs->Flink;
146
147 while (le != extent_refs) {
148 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
149
150 if (er->type == TYPE_TREE_BLOCK_REF && er->tbr.offset == root)
151 return STATUS_SUCCESS;
152
153 le = le->Flink;
154 }
155 }
156
157 er2 = ExAllocatePoolWithTag(PagedPool, sizeof(extent_ref), ALLOC_TAG);
158 if (!er2) {
159 ERR("out of memory\n");
160 return STATUS_INSUFFICIENT_RESOURCES;
161 }
162
163 er2->type = TYPE_TREE_BLOCK_REF;
164 er2->tbr.offset = root;
165
166 InsertTailList(extent_refs, &er2->list_entry);
167
168 return STATUS_SUCCESS;
169 }
170
171 static void sort_extent_refs(LIST_ENTRY* extent_refs) {
172 LIST_ENTRY newlist;
173
174 if (IsListEmpty(extent_refs))
175 return;
176
177 // insertion sort
178
179 InitializeListHead(&newlist);
180
181 while (!IsListEmpty(extent_refs)) {
182 extent_ref* er = CONTAINING_RECORD(RemoveHeadList(extent_refs), extent_ref, list_entry);
183 LIST_ENTRY* le;
184 BOOL inserted = FALSE;
185
186 le = newlist.Flink;
187 while (le != &newlist) {
188 extent_ref* er2 = CONTAINING_RECORD(le, extent_ref, list_entry);
189
190 if (er->type < er2->type || (er->type == er2->type && er->hash > er2->hash)) {
191 InsertHeadList(le->Blink, &er->list_entry);
192 inserted = TRUE;
193 break;
194 }
195
196 le = le->Flink;
197 }
198
199 if (!inserted)
200 InsertTailList(&newlist, &er->list_entry);
201 }
202
203 newlist.Flink->Blink = extent_refs;
204 newlist.Blink->Flink = extent_refs;
205 extent_refs->Flink = newlist.Flink;
206 extent_refs->Blink = newlist.Blink;
207 }
208
209 static NTSTATUS construct_extent_item(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 flags, LIST_ENTRY* extent_refs,
210 KEY* firstitem, UINT8 level, PIRP Irp) {
211 NTSTATUS Status;
212 LIST_ENTRY *le, *next_le;
213 UINT64 refcount;
214 UINT16 inline_len;
215 BOOL all_inline = TRUE;
216 extent_ref* first_noninline = NULL;
217 EXTENT_ITEM* ei;
218 UINT8* siptr;
219
220 // FIXME - write skinny extents if is tree and incompat flag set
221
222 if (IsListEmpty(extent_refs)) {
223 WARN("no extent refs found\n");
224 return STATUS_SUCCESS;
225 }
226
227 refcount = 0;
228 inline_len = sizeof(EXTENT_ITEM);
229
230 if (flags & EXTENT_ITEM_TREE_BLOCK)
231 inline_len += sizeof(EXTENT_ITEM2);
232
233 le = extent_refs->Flink;
234 while (le != extent_refs) {
235 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
236 UINT64 rc;
237
238 next_le = le->Flink;
239
240 rc = get_extent_data_refcount(er->type, &er->edr);
241
242 if (rc == 0) {
243 RemoveEntryList(&er->list_entry);
244
245 ExFreePool(er);
246 } else {
247 UINT16 extlen = get_extent_data_len(er->type);
248
249 refcount += rc;
250
251 er->hash = get_extent_hash(er->type, &er->edr);
252
253 if (all_inline) {
254 if ((UINT16)(inline_len + 1 + extlen) > Vcb->superblock.node_size >> 2) {
255 all_inline = FALSE;
256 first_noninline = er;
257 } else
258 inline_len += extlen + 1;
259 }
260 }
261
262 le = next_le;
263 }
264
265 ei = ExAllocatePoolWithTag(PagedPool, inline_len, ALLOC_TAG);
266 if (!ei) {
267 ERR("out of memory\n");
268 return STATUS_INSUFFICIENT_RESOURCES;
269 }
270
271 ei->refcount = refcount;
272 ei->generation = Vcb->superblock.generation;
273 ei->flags = flags;
274
275 if (flags & EXTENT_ITEM_TREE_BLOCK) {
276 EXTENT_ITEM2* ei2 = (EXTENT_ITEM2*)&ei[1];
277
278 if (firstitem) {
279 ei2->firstitem.obj_id = firstitem->obj_id;
280 ei2->firstitem.obj_type = firstitem->obj_type;
281 ei2->firstitem.offset = firstitem->offset;
282 } else {
283 ei2->firstitem.obj_id = 0;
284 ei2->firstitem.obj_type = 0;
285 ei2->firstitem.offset = 0;
286 }
287
288 ei2->level = level;
289
290 siptr = (UINT8*)&ei2[1];
291 } else
292 siptr = (UINT8*)&ei[1];
293
294 sort_extent_refs(extent_refs);
295
296 le = extent_refs->Flink;
297 while (le != extent_refs) {
298 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
299 ULONG extlen = get_extent_data_len(er->type);
300
301 if (!all_inline && er == first_noninline)
302 break;
303
304 *siptr = er->type;
305 siptr++;
306
307 if (extlen > 0) {
308 RtlCopyMemory(siptr, &er->edr, extlen);
309 siptr += extlen;
310 }
311
312 le = le->Flink;
313 }
314
315 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, inline_len, NULL, Irp);
316 if (!NT_SUCCESS(Status)) {
317 ERR("insert_tree_item returned %08x\n", Status);
318 ExFreePool(ei);
319 return Status;
320 }
321
322 if (!all_inline) {
323 le = &first_noninline->list_entry;
324
325 while (le != extent_refs) {
326 extent_ref* er = CONTAINING_RECORD(le, extent_ref, list_entry);
327 UINT16 len;
328 UINT8* data;
329
330 if (er->type == TYPE_EXTENT_DATA_REF) {
331 len = sizeof(EXTENT_DATA_REF);
332
333 data = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
334
335 if (!data) {
336 ERR("out of memory\n");
337 return STATUS_INSUFFICIENT_RESOURCES;
338 }
339
340 RtlCopyMemory(data, &er->edr, len);
341 } else if (er->type == TYPE_SHARED_DATA_REF) {
342 len = sizeof(UINT32);
343
344 data = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
345
346 if (!data) {
347 ERR("out of memory\n");
348 return STATUS_INSUFFICIENT_RESOURCES;
349 }
350
351 *((UINT32*)data) = er->sdr.count;
352 } else {
353 len = 0;
354 data = NULL;
355 }
356
357 Status = insert_tree_item(Vcb, Vcb->extent_root, address, er->type, er->hash, data, len, NULL, Irp);
358 if (!NT_SUCCESS(Status)) {
359 ERR("insert_tree_item returned %08x\n", Status);
360 if (data) ExFreePool(data);
361 return Status;
362 }
363
364 le = le->Flink;
365 }
366 }
367
368 return STATUS_SUCCESS;
369 }
370
371 static NTSTATUS convert_old_extent(device_extension* Vcb, UINT64 address, BOOL tree, KEY* firstitem, UINT8 level, PIRP Irp) {
372 NTSTATUS Status;
373 KEY searchkey;
374 traverse_ptr tp, next_tp;
375 LIST_ENTRY extent_refs;
376 UINT64 size;
377
378 InitializeListHead(&extent_refs);
379
380 searchkey.obj_id = address;
381 searchkey.obj_type = TYPE_EXTENT_ITEM;
382 searchkey.offset = 0xffffffffffffffff;
383
384 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
385 if (!NT_SUCCESS(Status)) {
386 ERR("find_item returned %08x\n", Status);
387 return Status;
388 }
389
390 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
391 ERR("old-style extent %llx not found\n", address);
392 return STATUS_INTERNAL_ERROR;
393 }
394
395 size = tp.item->key.offset;
396
397 Status = delete_tree_item(Vcb, &tp);
398 if (!NT_SUCCESS(Status)) {
399 ERR("delete_tree_item returned %08x\n", Status);
400 return Status;
401 }
402
403 while (find_next_item(Vcb, &tp, &next_tp, FALSE, Irp)) {
404 tp = next_tp;
405
406 if (tp.item->key.obj_id == address && tp.item->key.obj_type == TYPE_EXTENT_REF_V0 && tp.item->size >= sizeof(EXTENT_REF_V0)) {
407 EXTENT_REF_V0* erv0 = (EXTENT_REF_V0*)tp.item->data;
408
409 if (tree) {
410 if (tp.item->key.offset == tp.item->key.obj_id) { // top of the tree
411 Status = add_tree_block_extent_ref(&extent_refs, erv0->root);
412 if (!NT_SUCCESS(Status)) {
413 ERR("add_tree_block_extent_ref returned %08x\n", Status);
414 goto end;
415 }
416 } else {
417 Status = add_shared_block_extent_ref(&extent_refs, tp.item->key.offset);
418 if (!NT_SUCCESS(Status)) {
419 ERR("add_shared_block_extent_ref returned %08x\n", Status);
420 goto end;
421 }
422 }
423 } else {
424 Status = add_shared_data_extent_ref(&extent_refs, tp.item->key.offset, erv0->count);
425 if (!NT_SUCCESS(Status)) {
426 ERR("add_shared_data_extent_ref returned %08x\n", Status);
427 goto end;
428 }
429 }
430
431 Status = delete_tree_item(Vcb, &tp);
432 if (!NT_SUCCESS(Status)) {
433 ERR("delete_tree_item returned %08x\n", Status);
434 goto end;
435 }
436 }
437
438 if (tp.item->key.obj_id > address || tp.item->key.obj_type > TYPE_EXTENT_REF_V0)
439 break;
440 }
441
442 Status = construct_extent_item(Vcb, address, size, tree ? (EXTENT_ITEM_TREE_BLOCK | EXTENT_ITEM_SHARED_BACKREFS) : EXTENT_ITEM_DATA,
443 &extent_refs, firstitem, level, Irp);
444 if (!NT_SUCCESS(Status))
445 ERR("construct_extent_item returned %08x\n", Status);
446
447 end:
448 free_extent_refs(&extent_refs);
449
450 return Status;
451 }
452
453 NTSTATUS increase_extent_refcount(device_extension* Vcb, UINT64 address, UINT64 size, UINT8 type, void* data, KEY* firstitem, UINT8 level, PIRP Irp) {
454 NTSTATUS Status;
455 KEY searchkey;
456 traverse_ptr tp;
457 ULONG len, max_extent_item_size;
458 UINT16 datalen = get_extent_data_len(type);
459 EXTENT_ITEM* ei;
460 UINT8* ptr;
461 UINT64 inline_rc, offset;
462 UINT8* data2;
463 EXTENT_ITEM* newei;
464 BOOL skinny;
465 BOOL is_tree = type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF;
466
467 if (datalen == 0) {
468 ERR("unrecognized extent type %x\n", type);
469 return STATUS_INTERNAL_ERROR;
470 }
471
472 searchkey.obj_id = address;
473 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
474 searchkey.offset = 0xffffffffffffffff;
475
476 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
477 if (!NT_SUCCESS(Status)) {
478 ERR("error - find_item returned %08x\n", Status);
479 return Status;
480 }
481
482 // If entry doesn't exist yet, create new inline extent item
483
484 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)) {
485 UINT16 eisize;
486
487 eisize = sizeof(EXTENT_ITEM);
488 if (is_tree && !(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) eisize += sizeof(EXTENT_ITEM2);
489 eisize += sizeof(UINT8);
490 eisize += datalen;
491
492 ei = ExAllocatePoolWithTag(PagedPool, eisize, ALLOC_TAG);
493 if (!ei) {
494 ERR("out of memory\n");
495 return STATUS_INSUFFICIENT_RESOURCES;
496 }
497
498 ei->refcount = get_extent_data_refcount(type, data);
499 ei->generation = Vcb->superblock.generation;
500 ei->flags = is_tree ? EXTENT_ITEM_TREE_BLOCK : EXTENT_ITEM_DATA;
501 ptr = (UINT8*)&ei[1];
502
503 if (is_tree && !(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
504 EXTENT_ITEM2* ei2 = (EXTENT_ITEM2*)ptr;
505 ei2->firstitem = *firstitem;
506 ei2->level = level;
507 ptr = (UINT8*)&ei2[1];
508 }
509
510 *ptr = type;
511 RtlCopyMemory(ptr + 1, data, datalen);
512
513 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && is_tree)
514 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, ei, eisize, NULL, Irp);
515 else
516 Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, size, ei, eisize, NULL, Irp);
517
518 if (!NT_SUCCESS(Status)) {
519 ERR("insert_tree_item returned %08x\n", Status);
520 return Status;
521 }
522
523 return STATUS_SUCCESS;
524 } else if (tp.item->key.obj_id == address && tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->key.offset != size) {
525 ERR("extent %llx exists, but with size %llx rather than %llx expected\n", tp.item->key.obj_id, tp.item->key.offset, size);
526 return STATUS_INTERNAL_ERROR;
527 }
528
529 skinny = tp.item->key.obj_type == TYPE_METADATA_ITEM;
530
531 if (tp.item->size == sizeof(EXTENT_ITEM_V0) && !skinny) {
532 Status = convert_old_extent(Vcb, address, is_tree, firstitem, level, Irp);
533
534 if (!NT_SUCCESS(Status)) {
535 ERR("convert_old_extent returned %08x\n", Status);
536 return Status;
537 }
538
539 return increase_extent_refcount(Vcb, address, size, type, data, firstitem, level, Irp);
540 }
541
542 if (tp.item->size < sizeof(EXTENT_ITEM)) {
543 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
544 return STATUS_INTERNAL_ERROR;
545 }
546
547 ei = (EXTENT_ITEM*)tp.item->data;
548
549 len = tp.item->size - sizeof(EXTENT_ITEM);
550 ptr = (UINT8*)&ei[1];
551
552 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
553 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
554 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
555 return STATUS_INTERNAL_ERROR;
556 }
557
558 len -= sizeof(EXTENT_ITEM2);
559 ptr += sizeof(EXTENT_ITEM2);
560 }
561
562 inline_rc = 0;
563
564 // Loop through existing inline extent entries
565
566 while (len > 0) {
567 UINT8 secttype = *ptr;
568 ULONG sectlen = get_extent_data_len(secttype);
569 UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
570
571 len--;
572
573 if (sectlen > len) {
574 ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
575 return STATUS_INTERNAL_ERROR;
576 }
577
578 if (sectlen == 0) {
579 ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
580 return STATUS_INTERNAL_ERROR;
581 }
582
583 // If inline extent already present, increase refcount and return
584
585 if (secttype == type) {
586 if (type == TYPE_EXTENT_DATA_REF) {
587 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
588 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
589
590 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
591 UINT32 rc = get_extent_data_refcount(type, data);
592 EXTENT_DATA_REF* sectedr2;
593
594 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
595 if (!newei) {
596 ERR("out of memory\n");
597 return STATUS_INSUFFICIENT_RESOURCES;
598 }
599
600 RtlCopyMemory(newei, tp.item->data, tp.item->size);
601
602 newei->refcount += rc;
603
604 sectedr2 = (EXTENT_DATA_REF*)((UINT8*)newei + ((UINT8*)sectedr - tp.item->data));
605 sectedr2->count += rc;
606
607 Status = delete_tree_item(Vcb, &tp);
608 if (!NT_SUCCESS(Status)) {
609 ERR("delete_tree_item returned %08x\n", Status);
610 return Status;
611 }
612
613 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);
614 if (!NT_SUCCESS(Status)) {
615 ERR("insert_tree_item returned %08x\n", Status);
616 return Status;
617 }
618
619 return STATUS_SUCCESS;
620 }
621 } else if (type == TYPE_TREE_BLOCK_REF) {
622 TREE_BLOCK_REF* secttbr = (TREE_BLOCK_REF*)(ptr + sizeof(UINT8));
623 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
624
625 if (secttbr->offset == tbr->offset) {
626 TRACE("trying to increase refcount of non-shared tree extent\n");
627 return STATUS_SUCCESS;
628 }
629 } else if (type == TYPE_SHARED_BLOCK_REF) {
630 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(UINT8));
631 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
632
633 if (sectsbr->offset == sbr->offset)
634 return STATUS_SUCCESS;
635 } else if (type == TYPE_SHARED_DATA_REF) {
636 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(UINT8));
637 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
638
639 if (sectsdr->offset == sdr->offset) {
640 UINT32 rc = get_extent_data_refcount(type, data);
641 SHARED_DATA_REF* sectsdr2;
642
643 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
644 if (!newei) {
645 ERR("out of memory\n");
646 return STATUS_INSUFFICIENT_RESOURCES;
647 }
648
649 RtlCopyMemory(newei, tp.item->data, tp.item->size);
650
651 newei->refcount += rc;
652
653 sectsdr2 = (SHARED_DATA_REF*)((UINT8*)newei + ((UINT8*)sectsdr - tp.item->data));
654 sectsdr2->count += rc;
655
656 Status = delete_tree_item(Vcb, &tp);
657 if (!NT_SUCCESS(Status)) {
658 ERR("delete_tree_item returned %08x\n", Status);
659 return Status;
660 }
661
662 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);
663 if (!NT_SUCCESS(Status)) {
664 ERR("insert_tree_item returned %08x\n", Status);
665 return Status;
666 }
667
668 return STATUS_SUCCESS;
669 }
670 } else {
671 ERR("unhandled extent type %x\n", type);
672 return STATUS_INTERNAL_ERROR;
673 }
674 }
675
676 len -= sectlen;
677 ptr += sizeof(UINT8) + sectlen;
678 inline_rc += sectcount;
679 }
680
681 offset = get_extent_hash(type, data);
682
683 max_extent_item_size = (Vcb->superblock.node_size >> 4) - sizeof(leaf_node);
684
685 // If we can, add entry as inline extent item
686
687 if (inline_rc == ei->refcount && tp.item->size + sizeof(UINT8) + datalen < max_extent_item_size) {
688 len = tp.item->size - sizeof(EXTENT_ITEM);
689 ptr = (UINT8*)&ei[1];
690
691 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
692 len -= sizeof(EXTENT_ITEM2);
693 ptr += sizeof(EXTENT_ITEM2);
694 }
695
696 // Confusingly, it appears that references are sorted forward by type (i.e. EXTENT_DATA_REFs before
697 // SHARED_DATA_REFs), but then backwards by hash...
698
699 while (len > 0) {
700 UINT8 secttype = *ptr;
701 ULONG sectlen = get_extent_data_len(secttype);
702
703 if (secttype > type)
704 break;
705
706 if (secttype == type) {
707 UINT64 sectoff = get_extent_hash(secttype, ptr + 1);
708
709 if (sectoff < offset)
710 break;
711 }
712
713 len -= sectlen + sizeof(UINT8);
714 ptr += sizeof(UINT8) + sectlen;
715 }
716
717 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size + sizeof(UINT8) + datalen, ALLOC_TAG);
718 RtlCopyMemory(newei, tp.item->data, ptr - tp.item->data);
719
720 newei->refcount += get_extent_data_refcount(type, data);
721
722 if (len > 0)
723 RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data) + sizeof(UINT8) + datalen, ptr, len);
724
725 ptr = (ptr - tp.item->data) + (UINT8*)newei;
726
727 *ptr = type;
728 RtlCopyMemory(ptr + 1, data, datalen);
729
730 Status = delete_tree_item(Vcb, &tp);
731 if (!NT_SUCCESS(Status)) {
732 ERR("delete_tree_item returned %08x\n", Status);
733 return Status;
734 }
735
736 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) + datalen, NULL, Irp);
737 if (!NT_SUCCESS(Status)) {
738 ERR("insert_tree_item returned %08x\n", Status);
739 return Status;
740 }
741
742 return STATUS_SUCCESS;
743 }
744
745 // Look for existing non-inline entry, and increase refcount if found
746
747 if (inline_rc != ei->refcount) {
748 traverse_ptr tp2;
749
750 searchkey.obj_id = address;
751 searchkey.obj_type = type;
752 searchkey.offset = offset;
753
754 Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, FALSE, Irp);
755 if (!NT_SUCCESS(Status)) {
756 ERR("error - find_item returned %08x\n", Status);
757 return Status;
758 }
759
760 if (!keycmp(tp2.item->key, searchkey)) {
761 if (type == TYPE_SHARED_DATA_REF && tp2.item->size < sizeof(UINT32)) {
762 ERR("(%llx,%x,%llx) was %x bytes, expecting %x\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, sizeof(UINT32));
763 return STATUS_INTERNAL_ERROR;
764 } else if (type != TYPE_SHARED_DATA_REF && tp2.item->size < datalen) {
765 ERR("(%llx,%x,%llx) was %x bytes, expecting %x\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, datalen);
766 return STATUS_INTERNAL_ERROR;
767 }
768
769 data2 = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
770 if (!data2) {
771 ERR("out of memory\n");
772 return STATUS_INSUFFICIENT_RESOURCES;
773 }
774
775 RtlCopyMemory(data2, tp2.item->data, tp2.item->size);
776
777 if (type == TYPE_EXTENT_DATA_REF) {
778 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data2;
779
780 edr->count += get_extent_data_refcount(type, data);
781 } else if (type == TYPE_TREE_BLOCK_REF) {
782 TRACE("trying to increase refcount of non-shared tree extent\n");
783 return STATUS_SUCCESS;
784 } else if (type == TYPE_SHARED_BLOCK_REF)
785 return STATUS_SUCCESS;
786 else if (type == TYPE_SHARED_DATA_REF) {
787 UINT32* sdr = (UINT32*)data2;
788
789 *sdr += get_extent_data_refcount(type, data);
790 } else {
791 ERR("unhandled extent type %x\n", type);
792 return STATUS_INTERNAL_ERROR;
793 }
794
795 Status = delete_tree_item(Vcb, &tp2);
796 if (!NT_SUCCESS(Status)) {
797 ERR("delete_tree_item returned %08x\n", Status);
798 return Status;
799 }
800
801 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);
802 if (!NT_SUCCESS(Status)) {
803 ERR("insert_tree_item returned %08x\n", Status);
804 return Status;
805 }
806
807 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
808 if (!newei) {
809 ERR("out of memory\n");
810 return STATUS_INSUFFICIENT_RESOURCES;
811 }
812
813 RtlCopyMemory(newei, tp.item->data, tp.item->size);
814
815 newei->refcount += get_extent_data_refcount(type, data);
816
817 Status = delete_tree_item(Vcb, &tp);
818 if (!NT_SUCCESS(Status)) {
819 ERR("delete_tree_item returned %08x\n", Status);
820 return Status;
821 }
822
823 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);
824 if (!NT_SUCCESS(Status)) {
825 ERR("insert_tree_item returned %08x\n", Status);
826 return Status;
827 }
828
829 return STATUS_SUCCESS;
830 }
831 }
832
833 // Otherwise, add new non-inline entry
834
835 if (type == TYPE_SHARED_DATA_REF) {
836 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
837
838 data2 = ExAllocatePoolWithTag(PagedPool, sizeof(UINT32), ALLOC_TAG);
839 if (!data2) {
840 ERR("out of memory\n");
841 return STATUS_INSUFFICIENT_RESOURCES;
842 }
843
844 datalen = sizeof(UINT32);
845
846 *((UINT32*)data2) = sdr->count;
847 } else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF) {
848 data2 = NULL;
849 datalen = 0;
850 } else {
851 data2 = ExAllocatePoolWithTag(PagedPool, datalen, ALLOC_TAG);
852 if (!data2) {
853 ERR("out of memory\n");
854 return STATUS_INSUFFICIENT_RESOURCES;
855 }
856
857 RtlCopyMemory(data2, data, datalen);
858 }
859
860 Status = insert_tree_item(Vcb, Vcb->extent_root, address, type, offset, data2, datalen, NULL, Irp);
861 if (!NT_SUCCESS(Status)) {
862 ERR("insert_tree_item returned %08x\n", Status);
863 return Status;
864 }
865
866 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
867 if (!newei) {
868 ERR("out of memory\n");
869 return STATUS_INSUFFICIENT_RESOURCES;
870 }
871
872 RtlCopyMemory(newei, tp.item->data, tp.item->size);
873
874 newei->refcount += get_extent_data_refcount(type, data);
875
876 Status = delete_tree_item(Vcb, &tp);
877 if (!NT_SUCCESS(Status)) {
878 ERR("delete_tree_item returned %08x\n", Status);
879 return Status;
880 }
881
882 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);
883 if (!NT_SUCCESS(Status)) {
884 ERR("insert_tree_item returned %08x\n", Status);
885 return Status;
886 }
887
888 return STATUS_SUCCESS;
889 }
890
891 NTSTATUS increase_extent_refcount_data(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 root, UINT64 inode, UINT64 offset, UINT32 refcount, PIRP Irp) {
892 EXTENT_DATA_REF edr;
893
894 edr.root = root;
895 edr.objid = inode;
896 edr.offset = offset;
897 edr.count = refcount;
898
899 return increase_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp);
900 }
901
902 NTSTATUS decrease_extent_refcount(device_extension* Vcb, UINT64 address, UINT64 size, UINT8 type, void* data, KEY* firstitem,
903 UINT8 level, UINT64 parent, BOOL superseded, PIRP Irp) {
904 KEY searchkey;
905 NTSTATUS Status;
906 traverse_ptr tp, tp2;
907 EXTENT_ITEM* ei;
908 ULONG len;
909 UINT64 inline_rc;
910 UINT8* ptr;
911 UINT32 rc = data ? get_extent_data_refcount(type, data) : 1;
912 ULONG datalen = get_extent_data_len(type);
913 BOOL is_tree = (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF), skinny = FALSE;
914
915 if (is_tree && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
916 searchkey.obj_id = address;
917 searchkey.obj_type = TYPE_METADATA_ITEM;
918 searchkey.offset = 0xffffffffffffffff;
919
920 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
921 if (!NT_SUCCESS(Status)) {
922 ERR("error - find_item returned %08x\n", Status);
923 return Status;
924 }
925
926 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type)
927 skinny = TRUE;
928 }
929
930 if (!skinny) {
931 searchkey.obj_id = address;
932 searchkey.obj_type = TYPE_EXTENT_ITEM;
933 searchkey.offset = 0xffffffffffffffff;
934
935 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
936 if (!NT_SUCCESS(Status)) {
937 ERR("error - find_item returned %08x\n", Status);
938 return Status;
939 }
940
941 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
942 ERR("could not find EXTENT_ITEM for address %llx\n", address);
943 return STATUS_INTERNAL_ERROR;
944 }
945
946 if (tp.item->key.offset != size) {
947 ERR("extent %llx had length %llx, not %llx as expected\n", address, tp.item->key.offset, size);
948 return STATUS_INTERNAL_ERROR;
949 }
950
951 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
952 Status = convert_old_extent(Vcb, address, is_tree, firstitem, level, Irp);
953
954 if (!NT_SUCCESS(Status)) {
955 ERR("convert_old_extent returned %08x\n", Status);
956 return Status;
957 }
958
959 return decrease_extent_refcount(Vcb, address, size, type, data, firstitem, level, parent, superseded, Irp);
960 }
961 }
962
963 if (tp.item->size < sizeof(EXTENT_ITEM)) {
964 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
965 return STATUS_INTERNAL_ERROR;
966 }
967
968 ei = (EXTENT_ITEM*)tp.item->data;
969
970 len = tp.item->size - sizeof(EXTENT_ITEM);
971 ptr = (UINT8*)&ei[1];
972
973 if (ei->flags & EXTENT_ITEM_TREE_BLOCK && !skinny) {
974 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
975 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
976 return STATUS_INTERNAL_ERROR;
977 }
978
979 len -= sizeof(EXTENT_ITEM2);
980 ptr += sizeof(EXTENT_ITEM2);
981 }
982
983 if (ei->refcount < rc) {
984 ERR("error - extent has refcount %llx, trying to reduce by %x\n", ei->refcount, rc);
985 return STATUS_INTERNAL_ERROR;
986 }
987
988 inline_rc = 0;
989
990 // Loop through inline extent entries
991
992 while (len > 0) {
993 UINT8 secttype = *ptr;
994 UINT16 sectlen = get_extent_data_len(secttype);
995 UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
996
997 len--;
998
999 if (sectlen > len) {
1000 ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1001 return STATUS_INTERNAL_ERROR;
1002 }
1003
1004 if (sectlen == 0) {
1005 ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1006 return STATUS_INTERNAL_ERROR;
1007 }
1008
1009 if (secttype == type) {
1010 if (type == TYPE_EXTENT_DATA_REF) {
1011 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
1012 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
1013
1014 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
1015 UINT16 neweilen;
1016 EXTENT_ITEM* newei;
1017
1018 if (ei->refcount == edr->count) {
1019 Status = delete_tree_item(Vcb, &tp);
1020 if (!NT_SUCCESS(Status)) {
1021 ERR("delete_tree_item returned %08x\n", Status);
1022 return Status;
1023 }
1024
1025 if (!superseded)
1026 add_checksum_entry(Vcb, address, (ULONG)(size / Vcb->superblock.sector_size), NULL, Irp);
1027
1028 return STATUS_SUCCESS;
1029 }
1030
1031 if (sectedr->count < edr->count) {
1032 ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
1033 return STATUS_INTERNAL_ERROR;
1034 }
1035
1036 if (sectedr->count > edr->count) // reduce section refcount
1037 neweilen = tp.item->size;
1038 else // remove section entirely
1039 neweilen = tp.item->size - sizeof(UINT8) - sectlen;
1040
1041 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1042 if (!newei) {
1043 ERR("out of memory\n");
1044 return STATUS_INSUFFICIENT_RESOURCES;
1045 }
1046
1047 if (sectedr->count > edr->count) {
1048 EXTENT_DATA_REF* newedr = (EXTENT_DATA_REF*)((UINT8*)newei + ((UINT8*)sectedr - tp.item->data));
1049
1050 RtlCopyMemory(newei, ei, neweilen);
1051
1052 newedr->count -= rc;
1053 } else {
1054 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1055
1056 if (len > sectlen)
1057 RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(UINT8), len - sectlen);
1058 }
1059
1060 newei->refcount -= rc;
1061
1062 Status = delete_tree_item(Vcb, &tp);
1063 if (!NT_SUCCESS(Status)) {
1064 ERR("delete_tree_item returned %08x\n", Status);
1065 return Status;
1066 }
1067
1068 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);
1069 if (!NT_SUCCESS(Status)) {
1070 ERR("insert_tree_item returned %08x\n", Status);
1071 return Status;
1072 }
1073
1074 return STATUS_SUCCESS;
1075 }
1076 } else if (type == TYPE_SHARED_DATA_REF) {
1077 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(UINT8));
1078 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
1079
1080 if (sectsdr->offset == sdr->offset) {
1081 EXTENT_ITEM* newei;
1082 UINT16 neweilen;
1083
1084 if (ei->refcount == sectsdr->count) {
1085 Status = delete_tree_item(Vcb, &tp);
1086 if (!NT_SUCCESS(Status)) {
1087 ERR("delete_tree_item returned %08x\n", Status);
1088 return Status;
1089 }
1090
1091 if (!superseded)
1092 add_checksum_entry(Vcb, address, (ULONG)(size / Vcb->superblock.sector_size), NULL, Irp);
1093
1094 return STATUS_SUCCESS;
1095 }
1096
1097 if (sectsdr->count < sdr->count) {
1098 ERR("error - SHARED_DATA_REF has refcount %x, trying to reduce by %x\n", sectsdr->count, sdr->count);
1099 return STATUS_INTERNAL_ERROR;
1100 }
1101
1102 if (sectsdr->count > sdr->count) // reduce section refcount
1103 neweilen = tp.item->size;
1104 else // remove section entirely
1105 neweilen = tp.item->size - sizeof(UINT8) - sectlen;
1106
1107 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1108 if (!newei) {
1109 ERR("out of memory\n");
1110 return STATUS_INSUFFICIENT_RESOURCES;
1111 }
1112
1113 if (sectsdr->count > sdr->count) {
1114 SHARED_DATA_REF* newsdr = (SHARED_DATA_REF*)((UINT8*)newei + ((UINT8*)sectsdr - tp.item->data));
1115
1116 RtlCopyMemory(newei, ei, neweilen);
1117
1118 newsdr->count -= rc;
1119 } else {
1120 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1121
1122 if (len > sectlen)
1123 RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(UINT8), len - sectlen);
1124 }
1125
1126 newei->refcount -= rc;
1127
1128 Status = delete_tree_item(Vcb, &tp);
1129 if (!NT_SUCCESS(Status)) {
1130 ERR("delete_tree_item returned %08x\n", Status);
1131 return Status;
1132 }
1133
1134 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);
1135 if (!NT_SUCCESS(Status)) {
1136 ERR("insert_tree_item returned %08x\n", Status);
1137 return Status;
1138 }
1139
1140 return STATUS_SUCCESS;
1141 }
1142 } else if (type == TYPE_TREE_BLOCK_REF) {
1143 TREE_BLOCK_REF* secttbr = (TREE_BLOCK_REF*)(ptr + sizeof(UINT8));
1144 TREE_BLOCK_REF* tbr = (TREE_BLOCK_REF*)data;
1145
1146 if (secttbr->offset == tbr->offset) {
1147 EXTENT_ITEM* newei;
1148 UINT16 neweilen;
1149
1150 if (ei->refcount == 1) {
1151 Status = delete_tree_item(Vcb, &tp);
1152 if (!NT_SUCCESS(Status)) {
1153 ERR("delete_tree_item returned %08x\n", Status);
1154 return Status;
1155 }
1156
1157 return STATUS_SUCCESS;
1158 }
1159
1160 neweilen = tp.item->size - sizeof(UINT8) - sectlen;
1161
1162 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1163 if (!newei) {
1164 ERR("out of memory\n");
1165 return STATUS_INSUFFICIENT_RESOURCES;
1166 }
1167
1168 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1169
1170 if (len > sectlen)
1171 RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(UINT8), len - sectlen);
1172
1173 newei->refcount--;
1174
1175 Status = delete_tree_item(Vcb, &tp);
1176 if (!NT_SUCCESS(Status)) {
1177 ERR("delete_tree_item returned %08x\n", Status);
1178 return Status;
1179 }
1180
1181 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);
1182 if (!NT_SUCCESS(Status)) {
1183 ERR("insert_tree_item returned %08x\n", Status);
1184 return Status;
1185 }
1186
1187 return STATUS_SUCCESS;
1188 }
1189 } else if (type == TYPE_SHARED_BLOCK_REF) {
1190 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(UINT8));
1191 SHARED_BLOCK_REF* sbr = (SHARED_BLOCK_REF*)data;
1192
1193 if (sectsbr->offset == sbr->offset) {
1194 EXTENT_ITEM* newei;
1195 UINT16 neweilen;
1196
1197 if (ei->refcount == 1) {
1198 Status = delete_tree_item(Vcb, &tp);
1199 if (!NT_SUCCESS(Status)) {
1200 ERR("delete_tree_item returned %08x\n", Status);
1201 return Status;
1202 }
1203
1204 return STATUS_SUCCESS;
1205 }
1206
1207 neweilen = tp.item->size - sizeof(UINT8) - sectlen;
1208
1209 newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1210 if (!newei) {
1211 ERR("out of memory\n");
1212 return STATUS_INSUFFICIENT_RESOURCES;
1213 }
1214
1215 RtlCopyMemory(newei, ei, ptr - tp.item->data);
1216
1217 if (len > sectlen)
1218 RtlCopyMemory((UINT8*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(UINT8), len - sectlen);
1219
1220 newei->refcount--;
1221
1222 Status = delete_tree_item(Vcb, &tp);
1223 if (!NT_SUCCESS(Status)) {
1224 ERR("delete_tree_item returned %08x\n", Status);
1225 return Status;
1226 }
1227
1228 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);
1229 if (!NT_SUCCESS(Status)) {
1230 ERR("insert_tree_item returned %08x\n", Status);
1231 return Status;
1232 }
1233
1234 return STATUS_SUCCESS;
1235 }
1236 } else {
1237 ERR("unhandled extent type %x\n", type);
1238 return STATUS_INTERNAL_ERROR;
1239 }
1240 }
1241
1242 len -= sectlen;
1243 ptr += sizeof(UINT8) + sectlen;
1244 inline_rc += sectcount;
1245 }
1246
1247 if (inline_rc == ei->refcount) {
1248 ERR("entry not found in inline extent item for address %llx\n", address);
1249 return STATUS_INTERNAL_ERROR;
1250 }
1251
1252 if (type == TYPE_SHARED_DATA_REF)
1253 datalen = sizeof(UINT32);
1254 else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF)
1255 datalen = 0;
1256
1257 searchkey.obj_id = address;
1258 searchkey.obj_type = type;
1259 searchkey.offset = (type == TYPE_SHARED_DATA_REF || type == TYPE_EXTENT_REF_V0) ? parent : get_extent_hash(type, data);
1260
1261 Status = find_item(Vcb, Vcb->extent_root, &tp2, &searchkey, FALSE, Irp);
1262 if (!NT_SUCCESS(Status)) {
1263 ERR("error - find_item returned %08x\n", Status);
1264 return Status;
1265 }
1266
1267 if (keycmp(tp2.item->key, searchkey)) {
1268 ERR("(%llx,%x,%llx) not found\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset);
1269 return STATUS_INTERNAL_ERROR;
1270 }
1271
1272 if (tp2.item->size < datalen) {
1273 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp2.item->key.obj_id, tp2.item->key.obj_type, tp2.item->key.offset, tp2.item->size, datalen);
1274 return STATUS_INTERNAL_ERROR;
1275 }
1276
1277 if (type == TYPE_EXTENT_DATA_REF) {
1278 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)tp2.item->data;
1279 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)data;
1280
1281 if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
1282 EXTENT_ITEM* newei;
1283
1284 if (ei->refcount == edr->count) {
1285 Status = delete_tree_item(Vcb, &tp);
1286 if (!NT_SUCCESS(Status)) {
1287 ERR("delete_tree_item returned %08x\n", Status);
1288 return Status;
1289 }
1290
1291 Status = delete_tree_item(Vcb, &tp2);
1292 if (!NT_SUCCESS(Status)) {
1293 ERR("delete_tree_item returned %08x\n", Status);
1294 return Status;
1295 }
1296
1297 if (!superseded)
1298 add_checksum_entry(Vcb, address, (ULONG)(size / Vcb->superblock.sector_size), NULL, Irp);
1299
1300 return STATUS_SUCCESS;
1301 }
1302
1303 if (sectedr->count < edr->count) {
1304 ERR("error - extent section has refcount %x, trying to reduce by %x\n", sectedr->count, edr->count);
1305 return STATUS_INTERNAL_ERROR;
1306 }
1307
1308 Status = delete_tree_item(Vcb, &tp2);
1309 if (!NT_SUCCESS(Status)) {
1310 ERR("delete_tree_item returned %08x\n", Status);
1311 return Status;
1312 }
1313
1314 if (sectedr->count > edr->count) {
1315 EXTENT_DATA_REF* newedr = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
1316
1317 if (!newedr) {
1318 ERR("out of memory\n");
1319 return STATUS_INSUFFICIENT_RESOURCES;
1320 }
1321
1322 RtlCopyMemory(newedr, sectedr, tp2.item->size);
1323
1324 newedr->count -= edr->count;
1325
1326 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);
1327 if (!NT_SUCCESS(Status)) {
1328 ERR("insert_tree_item returned %08x\n", Status);
1329 return Status;
1330 }
1331 }
1332
1333 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1334 if (!newei) {
1335 ERR("out of memory\n");
1336 return STATUS_INSUFFICIENT_RESOURCES;
1337 }
1338
1339 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1340
1341 newei->refcount -= rc;
1342
1343 Status = delete_tree_item(Vcb, &tp);
1344 if (!NT_SUCCESS(Status)) {
1345 ERR("delete_tree_item returned %08x\n", Status);
1346 return Status;
1347 }
1348
1349 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);
1350 if (!NT_SUCCESS(Status)) {
1351 ERR("insert_tree_item returned %08x\n", Status);
1352 return Status;
1353 }
1354
1355 return STATUS_SUCCESS;
1356 } else {
1357 ERR("error - hash collision?\n");
1358 return STATUS_INTERNAL_ERROR;
1359 }
1360 } else if (type == TYPE_SHARED_DATA_REF) {
1361 SHARED_DATA_REF* sdr = (SHARED_DATA_REF*)data;
1362
1363 if (tp2.item->key.offset == sdr->offset) {
1364 UINT32* sectsdrcount = (UINT32*)tp2.item->data;
1365 EXTENT_ITEM* newei;
1366
1367 if (ei->refcount == sdr->count) {
1368 Status = delete_tree_item(Vcb, &tp);
1369 if (!NT_SUCCESS(Status)) {
1370 ERR("delete_tree_item returned %08x\n", Status);
1371 return Status;
1372 }
1373
1374 Status = delete_tree_item(Vcb, &tp2);
1375 if (!NT_SUCCESS(Status)) {
1376 ERR("delete_tree_item returned %08x\n", Status);
1377 return Status;
1378 }
1379
1380 if (!superseded)
1381 add_checksum_entry(Vcb, address, (ULONG)(size / Vcb->superblock.sector_size), NULL, Irp);
1382
1383 return STATUS_SUCCESS;
1384 }
1385
1386 if (*sectsdrcount < sdr->count) {
1387 ERR("error - extent section has refcount %x, trying to reduce by %x\n", *sectsdrcount, sdr->count);
1388 return STATUS_INTERNAL_ERROR;
1389 }
1390
1391 Status = delete_tree_item(Vcb, &tp2);
1392 if (!NT_SUCCESS(Status)) {
1393 ERR("delete_tree_item returned %08x\n", Status);
1394 return Status;
1395 }
1396
1397 if (*sectsdrcount > sdr->count) {
1398 UINT32* newsdr = ExAllocatePoolWithTag(PagedPool, tp2.item->size, ALLOC_TAG);
1399
1400 if (!newsdr) {
1401 ERR("out of memory\n");
1402 return STATUS_INSUFFICIENT_RESOURCES;
1403 }
1404
1405 *newsdr = *sectsdrcount - sdr->count;
1406
1407 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);
1408 if (!NT_SUCCESS(Status)) {
1409 ERR("insert_tree_item returned %08x\n", Status);
1410 return Status;
1411 }
1412 }
1413
1414 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1415 if (!newei) {
1416 ERR("out of memory\n");
1417 return STATUS_INSUFFICIENT_RESOURCES;
1418 }
1419
1420 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1421
1422 newei->refcount -= rc;
1423
1424 Status = delete_tree_item(Vcb, &tp);
1425 if (!NT_SUCCESS(Status)) {
1426 ERR("delete_tree_item returned %08x\n", Status);
1427 return Status;
1428 }
1429
1430 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);
1431 if (!NT_SUCCESS(Status)) {
1432 ERR("insert_tree_item returned %08x\n", Status);
1433 return Status;
1434 }
1435
1436 return STATUS_SUCCESS;
1437 } else {
1438 ERR("error - collision?\n");
1439 return STATUS_INTERNAL_ERROR;
1440 }
1441 } else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF) {
1442 EXTENT_ITEM* newei;
1443
1444 if (ei->refcount == 1) {
1445 Status = delete_tree_item(Vcb, &tp);
1446 if (!NT_SUCCESS(Status)) {
1447 ERR("delete_tree_item returned %08x\n", Status);
1448 return Status;
1449 }
1450
1451 Status = delete_tree_item(Vcb, &tp2);
1452 if (!NT_SUCCESS(Status)) {
1453 ERR("delete_tree_item returned %08x\n", Status);
1454 return Status;
1455 }
1456
1457 return STATUS_SUCCESS;
1458 }
1459
1460 Status = delete_tree_item(Vcb, &tp2);
1461 if (!NT_SUCCESS(Status)) {
1462 ERR("delete_tree_item returned %08x\n", Status);
1463 return Status;
1464 }
1465
1466 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1467 if (!newei) {
1468 ERR("out of memory\n");
1469 return STATUS_INSUFFICIENT_RESOURCES;
1470 }
1471
1472 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1473
1474 newei->refcount -= rc;
1475
1476 Status = delete_tree_item(Vcb, &tp);
1477 if (!NT_SUCCESS(Status)) {
1478 ERR("delete_tree_item returned %08x\n", Status);
1479 return Status;
1480 }
1481
1482 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);
1483 if (!NT_SUCCESS(Status)) {
1484 ERR("insert_tree_item returned %08x\n", Status);
1485 return Status;
1486 }
1487
1488 return STATUS_SUCCESS;
1489 } else if (type == TYPE_EXTENT_REF_V0) {
1490 EXTENT_REF_V0* erv0 = (EXTENT_REF_V0*)tp2.item->data;
1491 EXTENT_ITEM* newei;
1492
1493 if (ei->refcount == erv0->count) {
1494 Status = delete_tree_item(Vcb, &tp);
1495 if (!NT_SUCCESS(Status)) {
1496 ERR("delete_tree_item returned %08x\n", Status);
1497 return Status;
1498 }
1499
1500 Status = delete_tree_item(Vcb, &tp2);
1501 if (!NT_SUCCESS(Status)) {
1502 ERR("delete_tree_item returned %08x\n", Status);
1503 return Status;
1504 }
1505
1506 if (!superseded)
1507 add_checksum_entry(Vcb, address, (ULONG)(size / Vcb->superblock.sector_size), NULL, Irp);
1508
1509 return STATUS_SUCCESS;
1510 }
1511
1512 Status = delete_tree_item(Vcb, &tp2);
1513 if (!NT_SUCCESS(Status)) {
1514 ERR("delete_tree_item returned %08x\n", Status);
1515 return Status;
1516 }
1517
1518 newei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1519 if (!newei) {
1520 ERR("out of memory\n");
1521 return STATUS_INSUFFICIENT_RESOURCES;
1522 }
1523
1524 RtlCopyMemory(newei, tp.item->data, tp.item->size);
1525
1526 newei->refcount -= rc;
1527
1528 Status = delete_tree_item(Vcb, &tp);
1529 if (!NT_SUCCESS(Status)) {
1530 ERR("delete_tree_item returned %08x\n", Status);
1531 return Status;
1532 }
1533
1534 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);
1535 if (!NT_SUCCESS(Status)) {
1536 ERR("insert_tree_item returned %08x\n", Status);
1537 return Status;
1538 }
1539
1540 return STATUS_SUCCESS;
1541 } else {
1542 ERR("unhandled extent type %x\n", type);
1543 return STATUS_INTERNAL_ERROR;
1544 }
1545 }
1546
1547 NTSTATUS decrease_extent_refcount_data(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 root, UINT64 inode,
1548 UINT64 offset, UINT32 refcount, BOOL superseded, PIRP Irp) {
1549 EXTENT_DATA_REF edr;
1550
1551 edr.root = root;
1552 edr.objid = inode;
1553 edr.offset = offset;
1554 edr.count = refcount;
1555
1556 return decrease_extent_refcount(Vcb, address, size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, 0, superseded, Irp);
1557 }
1558
1559 NTSTATUS decrease_extent_refcount_tree(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 root,
1560 UINT8 level, PIRP Irp) {
1561 TREE_BLOCK_REF tbr;
1562
1563 tbr.offset = root;
1564
1565 return decrease_extent_refcount(Vcb, address, size, TYPE_TREE_BLOCK_REF, &tbr, NULL/*FIXME*/, level, 0, FALSE, Irp);
1566 }
1567
1568 static UINT32 find_extent_data_refcount(device_extension* Vcb, UINT64 address, UINT64 size, UINT64 root, UINT64 objid, UINT64 offset, PIRP Irp) {
1569 NTSTATUS Status;
1570 KEY searchkey;
1571 traverse_ptr tp;
1572
1573 searchkey.obj_id = address;
1574 searchkey.obj_type = TYPE_EXTENT_ITEM;
1575 searchkey.offset = 0xffffffffffffffff;
1576
1577 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1578 if (!NT_SUCCESS(Status)) {
1579 ERR("error - find_item returned %08x\n", Status);
1580 return 0;
1581 }
1582
1583 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1584 TRACE("could not find address %llx in extent tree\n", address);
1585 return 0;
1586 }
1587
1588 if (tp.item->key.offset != size) {
1589 ERR("extent %llx had size %llx, not %llx as expected\n", address, tp.item->key.offset, size);
1590 return 0;
1591 }
1592
1593 if (tp.item->size >= sizeof(EXTENT_ITEM)) {
1594 EXTENT_ITEM* ei = (EXTENT_ITEM*)tp.item->data;
1595 UINT32 len = tp.item->size - sizeof(EXTENT_ITEM);
1596 UINT8* ptr = (UINT8*)&ei[1];
1597
1598 while (len > 0) {
1599 UINT8 secttype = *ptr;
1600 ULONG sectlen = get_extent_data_len(secttype);
1601 UINT32 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
1602
1603 len--;
1604
1605 if (sectlen > len) {
1606 ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1607 return 0;
1608 }
1609
1610 if (sectlen == 0) {
1611 ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1612 return 0;
1613 }
1614
1615 if (secttype == TYPE_EXTENT_DATA_REF) {
1616 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
1617
1618 if (sectedr->root == root && sectedr->objid == objid && sectedr->offset == offset)
1619 return sectcount;
1620 }
1621
1622 len -= sectlen;
1623 ptr += sizeof(UINT8) + sectlen;
1624 }
1625 }
1626
1627 searchkey.obj_id = address;
1628 searchkey.obj_type = TYPE_EXTENT_DATA_REF;
1629 searchkey.offset = get_extent_data_ref_hash2(root, objid, offset);
1630
1631 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1632 if (!NT_SUCCESS(Status)) {
1633 ERR("error - find_item returned %08x\n", Status);
1634 return 0;
1635 }
1636
1637 if (!keycmp(searchkey, tp.item->key)) {
1638 if (tp.item->size < sizeof(EXTENT_DATA_REF))
1639 ERR("(%llx,%x,%llx) has size %u, not %u as expected\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_DATA_REF));
1640 else {
1641 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)tp.item->data;
1642
1643 return edr->count;
1644 }
1645 }
1646
1647 return 0;
1648 }
1649
1650 UINT64 get_extent_refcount(device_extension* Vcb, UINT64 address, UINT64 size, PIRP Irp) {
1651 KEY searchkey;
1652 traverse_ptr tp;
1653 NTSTATUS Status;
1654 EXTENT_ITEM* ei;
1655
1656 searchkey.obj_id = address;
1657 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1658 searchkey.offset = 0xffffffffffffffff;
1659
1660 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1661 if (!NT_SUCCESS(Status)) {
1662 ERR("error - find_item returned %08x\n", Status);
1663 return 0;
1664 }
1665
1666 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1667 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1668 ei = (EXTENT_ITEM*)tp.item->data;
1669
1670 return ei->refcount;
1671 }
1672
1673 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
1674 ERR("couldn't find (%llx,%x,%llx) in extent tree\n", address, TYPE_EXTENT_ITEM, size);
1675 return 0;
1676 } else if (tp.item->key.offset != size) {
1677 ERR("extent %llx had size %llx, not %llx as expected\n", address, tp.item->key.offset, size);
1678 return 0;
1679 }
1680
1681 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1682 EXTENT_ITEM_V0* eiv0 = (EXTENT_ITEM_V0*)tp.item->data;
1683
1684 return eiv0->refcount;
1685 } else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1686 ERR("(%llx,%x,%llx) was %x bytes, expected at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type,
1687 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1688 return 0;
1689 }
1690
1691 ei = (EXTENT_ITEM*)tp.item->data;
1692
1693 return ei->refcount;
1694 }
1695
1696 BOOL is_extent_unique(device_extension* Vcb, UINT64 address, UINT64 size, PIRP Irp) {
1697 KEY searchkey;
1698 traverse_ptr tp, next_tp;
1699 NTSTATUS Status;
1700 UINT64 rc, rcrun, root = 0, inode = 0, offset = 0;
1701 UINT32 len;
1702 EXTENT_ITEM* ei;
1703 UINT8* ptr;
1704 BOOL b;
1705
1706 rc = get_extent_refcount(Vcb, address, size, Irp);
1707
1708 if (rc == 1)
1709 return TRUE;
1710
1711 if (rc == 0)
1712 return FALSE;
1713
1714 searchkey.obj_id = address;
1715 searchkey.obj_type = TYPE_EXTENT_ITEM;
1716 searchkey.offset = size;
1717
1718 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1719 if (!NT_SUCCESS(Status)) {
1720 WARN("error - find_item returned %08x\n", Status);
1721 return FALSE;
1722 }
1723
1724 if (keycmp(tp.item->key, searchkey)) {
1725 WARN("could not find (%llx,%x,%llx)\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1726 return FALSE;
1727 }
1728
1729 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1730 return FALSE;
1731
1732 if (tp.item->size < sizeof(EXTENT_ITEM)) {
1733 WARN("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1734 return FALSE;
1735 }
1736
1737 ei = (EXTENT_ITEM*)tp.item->data;
1738
1739 len = tp.item->size - sizeof(EXTENT_ITEM);
1740 ptr = (UINT8*)&ei[1];
1741
1742 if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
1743 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
1744 WARN("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
1745 return FALSE;
1746 }
1747
1748 len -= sizeof(EXTENT_ITEM2);
1749 ptr += sizeof(EXTENT_ITEM2);
1750 }
1751
1752 rcrun = 0;
1753
1754 // Loop through inline extent entries
1755
1756 while (len > 0) {
1757 UINT8 secttype = *ptr;
1758 ULONG sectlen = get_extent_data_len(secttype);
1759 UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
1760
1761 len--;
1762
1763 if (sectlen > len) {
1764 WARN("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
1765 return FALSE;
1766 }
1767
1768 if (sectlen == 0) {
1769 WARN("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
1770 return FALSE;
1771 }
1772
1773 if (secttype == TYPE_EXTENT_DATA_REF) {
1774 EXTENT_DATA_REF* sectedr = (EXTENT_DATA_REF*)(ptr + sizeof(UINT8));
1775
1776 if (root == 0 && inode == 0) {
1777 root = sectedr->root;
1778 inode = sectedr->objid;
1779 offset = sectedr->offset;
1780 } else if (root != sectedr->root || inode != sectedr->objid || offset != sectedr->offset)
1781 return FALSE;
1782 } else
1783 return FALSE;
1784
1785 len -= sectlen;
1786 ptr += sizeof(UINT8) + sectlen;
1787 rcrun += sectcount;
1788 }
1789
1790 if (rcrun == rc)
1791 return TRUE;
1792
1793 // Loop through non-inlines if some refs still unaccounted for
1794
1795 do {
1796 b = find_next_item(Vcb, &tp, &next_tp, FALSE, Irp);
1797
1798 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == TYPE_EXTENT_DATA_REF) {
1799 EXTENT_DATA_REF* edr = (EXTENT_DATA_REF*)tp.item->data;
1800
1801 if (tp.item->size < sizeof(EXTENT_DATA_REF)) {
1802 WARN("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset,
1803 tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
1804 return FALSE;
1805 }
1806
1807 if (root == 0 && inode == 0) {
1808 root = edr->root;
1809 inode = edr->objid;
1810 offset = edr->offset;
1811 } else if (root != edr->root || inode != edr->objid || offset != edr->offset)
1812 return FALSE;
1813
1814 rcrun += edr->count;
1815 }
1816
1817 if (rcrun == rc)
1818 return TRUE;
1819
1820 if (b) {
1821 tp = next_tp;
1822
1823 if (tp.item->key.obj_id > searchkey.obj_id)
1824 break;
1825 }
1826 } while (b);
1827
1828 // If we reach this point, there's still some refs unaccounted for somewhere.
1829 // Return FALSE in case we mess things up elsewhere.
1830
1831 return FALSE;
1832 }
1833
1834 UINT64 get_extent_flags(device_extension* Vcb, UINT64 address, PIRP Irp) {
1835 KEY searchkey;
1836 traverse_ptr tp;
1837 NTSTATUS Status;
1838 EXTENT_ITEM* ei;
1839
1840 searchkey.obj_id = address;
1841 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1842 searchkey.offset = 0xffffffffffffffff;
1843
1844 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1845 if (!NT_SUCCESS(Status)) {
1846 ERR("error - find_item returned %08x\n", Status);
1847 return 0;
1848 }
1849
1850 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1851 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1852 ei = (EXTENT_ITEM*)tp.item->data;
1853
1854 return ei->flags;
1855 }
1856
1857 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
1858 ERR("couldn't find %llx in extent tree\n", address);
1859 return 0;
1860 }
1861
1862 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1863 return 0;
1864 else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1865 ERR("(%llx,%x,%llx) was %x bytes, expected at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type,
1866 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1867 return 0;
1868 }
1869
1870 ei = (EXTENT_ITEM*)tp.item->data;
1871
1872 return ei->flags;
1873 }
1874
1875 void update_extent_flags(device_extension* Vcb, UINT64 address, UINT64 flags, PIRP Irp) {
1876 KEY searchkey;
1877 traverse_ptr tp;
1878 NTSTATUS Status;
1879 EXTENT_ITEM* ei;
1880
1881 searchkey.obj_id = address;
1882 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1883 searchkey.offset = 0xffffffffffffffff;
1884
1885 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1886 if (!NT_SUCCESS(Status)) {
1887 ERR("error - find_item returned %08x\n", Status);
1888 return;
1889 }
1890
1891 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA && tp.item->key.obj_id == address &&
1892 tp.item->key.obj_type == TYPE_METADATA_ITEM && tp.item->size >= sizeof(EXTENT_ITEM)) {
1893 ei = (EXTENT_ITEM*)tp.item->data;
1894 ei->flags = flags;
1895 return;
1896 }
1897
1898 if (tp.item->key.obj_id != address || tp.item->key.obj_type != TYPE_EXTENT_ITEM) {
1899 ERR("couldn't find %llx in extent tree\n", address);
1900 return;
1901 }
1902
1903 if (tp.item->size == sizeof(EXTENT_ITEM_V0))
1904 return;
1905 else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1906 ERR("(%llx,%x,%llx) was %x bytes, expected at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type,
1907 tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
1908 return;
1909 }
1910
1911 ei = (EXTENT_ITEM*)tp.item->data;
1912 ei->flags = flags;
1913 }
1914
1915 static changed_extent* get_changed_extent_item(chunk* c, UINT64 address, UINT64 size, BOOL no_csum) {
1916 LIST_ENTRY* le;
1917 changed_extent* ce;
1918
1919 le = c->changed_extents.Flink;
1920 while (le != &c->changed_extents) {
1921 ce = CONTAINING_RECORD(le, changed_extent, list_entry);
1922
1923 if (ce->address == address && ce->size == size)
1924 return ce;
1925
1926 le = le->Flink;
1927 }
1928
1929 ce = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent), ALLOC_TAG);
1930 if (!ce) {
1931 ERR("out of memory\n");
1932 return NULL;
1933 }
1934
1935 ce->address = address;
1936 ce->size = size;
1937 ce->old_size = size;
1938 ce->count = 0;
1939 ce->old_count = 0;
1940 ce->no_csum = no_csum;
1941 ce->superseded = FALSE;
1942 InitializeListHead(&ce->refs);
1943 InitializeListHead(&ce->old_refs);
1944
1945 InsertTailList(&c->changed_extents, &ce->list_entry);
1946
1947 return ce;
1948 }
1949
1950 NTSTATUS update_changed_extent_ref(device_extension* Vcb, chunk* c, UINT64 address, UINT64 size, UINT64 root, UINT64 objid, UINT64 offset, INT32 count,
1951 BOOL no_csum, BOOL superseded, PIRP Irp) {
1952 LIST_ENTRY* le;
1953 changed_extent* ce;
1954 changed_extent_ref* cer;
1955 NTSTATUS Status;
1956 KEY searchkey;
1957 traverse_ptr tp;
1958 UINT32 old_count;
1959
1960 ExAcquireResourceExclusiveLite(&c->changed_extents_lock, TRUE);
1961
1962 ce = get_changed_extent_item(c, address, size, no_csum);
1963
1964 if (!ce) {
1965 ERR("get_changed_extent_item failed\n");
1966 Status = STATUS_INTERNAL_ERROR;
1967 goto end;
1968 }
1969
1970 if (IsListEmpty(&ce->refs) && IsListEmpty(&ce->old_refs)) { // new entry
1971 searchkey.obj_id = address;
1972 searchkey.obj_type = TYPE_EXTENT_ITEM;
1973 searchkey.offset = 0xffffffffffffffff;
1974
1975 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1976 if (!NT_SUCCESS(Status)) {
1977 ERR("error - find_item returned %08x\n", Status);
1978 goto end;
1979 }
1980
1981 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1982 ERR("could not find address %llx in extent tree\n", address);
1983 Status = STATUS_INTERNAL_ERROR;
1984 goto end;
1985 }
1986
1987 if (tp.item->key.offset != size) {
1988 ERR("extent %llx had size %llx, not %llx as expected\n", address, tp.item->key.offset, size);
1989 Status = STATUS_INTERNAL_ERROR;
1990 goto end;
1991 }
1992
1993 if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1994 EXTENT_ITEM_V0* eiv0 = (EXTENT_ITEM_V0*)tp.item->data;
1995
1996 ce->count = ce->old_count = eiv0->refcount;
1997 } else if (tp.item->size >= sizeof(EXTENT_ITEM)) {
1998 EXTENT_ITEM* ei = (EXTENT_ITEM*)tp.item->data;
1999
2000 ce->count = ce->old_count = ei->refcount;
2001 } else {
2002 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
2003 Status = STATUS_INTERNAL_ERROR;
2004 goto end;
2005 }
2006 }
2007
2008 le = ce->refs.Flink;
2009 while (le != &ce->refs) {
2010 cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
2011
2012 if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == root && cer->edr.objid == objid && cer->edr.offset == offset) {
2013 ce->count += count;
2014 cer->edr.count += count;
2015 Status = STATUS_SUCCESS;
2016
2017 if (superseded)
2018 ce->superseded = TRUE;
2019
2020 goto end;
2021 }
2022
2023 le = le->Flink;
2024 }
2025
2026 old_count = find_extent_data_refcount(Vcb, address, size, root, objid, offset, Irp);
2027
2028 if (old_count > 0) {
2029 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2030
2031 if (!cer) {
2032 ERR("out of memory\n");
2033 Status = STATUS_INSUFFICIENT_RESOURCES;
2034 goto end;
2035 }
2036
2037 cer->type = TYPE_EXTENT_DATA_REF;
2038 cer->edr.root = root;
2039 cer->edr.objid = objid;
2040 cer->edr.offset = offset;
2041 cer->edr.count = old_count;
2042
2043 InsertTailList(&ce->old_refs, &cer->list_entry);
2044 }
2045
2046 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2047
2048 if (!cer) {
2049 ERR("out of memory\n");
2050 Status = STATUS_INSUFFICIENT_RESOURCES;
2051 goto end;
2052 }
2053
2054 cer->type = TYPE_EXTENT_DATA_REF;
2055 cer->edr.root = root;
2056 cer->edr.objid = objid;
2057 cer->edr.offset = offset;
2058 cer->edr.count = old_count + count;
2059
2060 InsertTailList(&ce->refs, &cer->list_entry);
2061
2062 ce->count += count;
2063
2064 if (superseded)
2065 ce->superseded = TRUE;
2066
2067 Status = STATUS_SUCCESS;
2068
2069 end:
2070 ExReleaseResourceLite(&c->changed_extents_lock);
2071
2072 return Status;
2073 }
2074
2075 void add_changed_extent_ref(chunk* c, UINT64 address, UINT64 size, UINT64 root, UINT64 objid, UINT64 offset, UINT32 count, BOOL no_csum) {
2076 changed_extent* ce;
2077 changed_extent_ref* cer;
2078 LIST_ENTRY* le;
2079
2080 ce = get_changed_extent_item(c, address, size, no_csum);
2081
2082 if (!ce) {
2083 ERR("get_changed_extent_item failed\n");
2084 return;
2085 }
2086
2087 le = ce->refs.Flink;
2088 while (le != &ce->refs) {
2089 cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
2090
2091 if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == root && cer->edr.objid == objid && cer->edr.offset == offset) {
2092 ce->count += count;
2093 cer->edr.count += count;
2094 return;
2095 }
2096
2097 le = le->Flink;
2098 }
2099
2100 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
2101
2102 if (!cer) {
2103 ERR("out of memory\n");
2104 return;
2105 }
2106
2107 cer->type = TYPE_EXTENT_DATA_REF;
2108 cer->edr.root = root;
2109 cer->edr.objid = objid;
2110 cer->edr.offset = offset;
2111 cer->edr.count = count;
2112
2113 InsertTailList(&ce->refs, &cer->list_entry);
2114
2115 ce->count += count;
2116 }
2117
2118 UINT64 find_extent_shared_tree_refcount(device_extension* Vcb, UINT64 address, UINT64 parent, PIRP Irp) {
2119 NTSTATUS Status;
2120 KEY searchkey;
2121 traverse_ptr tp;
2122 UINT64 inline_rc;
2123 EXTENT_ITEM* ei;
2124 UINT32 len;
2125 UINT8* ptr;
2126
2127 searchkey.obj_id = address;
2128 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
2129 searchkey.offset = 0xffffffffffffffff;
2130
2131 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2132 if (!NT_SUCCESS(Status)) {
2133 ERR("error - find_item returned %08x\n", Status);
2134 return 0;
2135 }
2136
2137 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)) {
2138 TRACE("could not find address %llx in extent tree\n", address);
2139 return 0;
2140 }
2141
2142 if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->key.offset != Vcb->superblock.node_size) {
2143 ERR("extent %llx had size %llx, not %llx as expected\n", address, tp.item->key.offset, Vcb->superblock.node_size);
2144 return 0;
2145 }
2146
2147 if (tp.item->size < sizeof(EXTENT_ITEM)) {
2148 ERR("(%llx,%x,%llx): size was %u, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
2149 return 0;
2150 }
2151
2152 ei = (EXTENT_ITEM*)tp.item->data;
2153 inline_rc = 0;
2154
2155 len = tp.item->size - sizeof(EXTENT_ITEM);
2156 ptr = (UINT8*)&ei[1];
2157
2158 if (searchkey.obj_type == TYPE_EXTENT_ITEM && ei->flags & EXTENT_ITEM_TREE_BLOCK) {
2159 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
2160 ERR("(%llx,%x,%llx): size was %u, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset,
2161 tp.item->size, sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2));
2162 return 0;
2163 }
2164
2165 len -= sizeof(EXTENT_ITEM2);
2166 ptr += sizeof(EXTENT_ITEM2);
2167 }
2168
2169 while (len > 0) {
2170 UINT8 secttype = *ptr;
2171 ULONG sectlen = get_extent_data_len(secttype);
2172 UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
2173
2174 len--;
2175
2176 if (sectlen > len) {
2177 ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
2178 return 0;
2179 }
2180
2181 if (sectlen == 0) {
2182 ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
2183 return 0;
2184 }
2185
2186 if (secttype == TYPE_SHARED_BLOCK_REF) {
2187 SHARED_BLOCK_REF* sectsbr = (SHARED_BLOCK_REF*)(ptr + sizeof(UINT8));
2188
2189 if (sectsbr->offset == parent)
2190 return 1;
2191 }
2192
2193 len -= sectlen;
2194 ptr += sizeof(UINT8) + sectlen;
2195 inline_rc += sectcount;
2196 }
2197
2198 // FIXME - what if old?
2199
2200 if (inline_rc == ei->refcount)
2201 return 0;
2202
2203 searchkey.obj_id = address;
2204 searchkey.obj_type = TYPE_SHARED_BLOCK_REF;
2205 searchkey.offset = parent;
2206
2207 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2208 if (!NT_SUCCESS(Status)) {
2209 ERR("error - find_item returned %08x\n", Status);
2210 return 0;
2211 }
2212
2213 if (!keycmp(searchkey, tp.item->key))
2214 return 1;
2215
2216 return 0;
2217 }
2218
2219 UINT32 find_extent_shared_data_refcount(device_extension* Vcb, UINT64 address, UINT64 parent, PIRP Irp) {
2220 NTSTATUS Status;
2221 KEY searchkey;
2222 traverse_ptr tp;
2223 UINT64 inline_rc;
2224 EXTENT_ITEM* ei;
2225 UINT32 len;
2226 UINT8* ptr;
2227
2228 searchkey.obj_id = address;
2229 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
2230 searchkey.offset = 0xffffffffffffffff;
2231
2232 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2233 if (!NT_SUCCESS(Status)) {
2234 ERR("error - find_item returned %08x\n", Status);
2235 return 0;
2236 }
2237
2238 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)) {
2239 TRACE("could not find address %llx in extent tree\n", address);
2240 return 0;
2241 }
2242
2243 if (tp.item->size < sizeof(EXTENT_ITEM)) {
2244 ERR("(%llx,%x,%llx): size was %u, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
2245 return 0;
2246 }
2247
2248 ei = (EXTENT_ITEM*)tp.item->data;
2249 inline_rc = 0;
2250
2251 len = tp.item->size - sizeof(EXTENT_ITEM);
2252 ptr = (UINT8*)&ei[1];
2253
2254 while (len > 0) {
2255 UINT8 secttype = *ptr;
2256 ULONG sectlen = get_extent_data_len(secttype);
2257 UINT64 sectcount = get_extent_data_refcount(secttype, ptr + sizeof(UINT8));
2258
2259 len--;
2260
2261 if (sectlen > len) {
2262 ERR("(%llx,%x,%llx): %x bytes left, expecting at least %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, len, sectlen);
2263 return 0;
2264 }
2265
2266 if (sectlen == 0) {
2267 ERR("(%llx,%x,%llx): unrecognized extent type %x\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, secttype);
2268 return 0;
2269 }
2270
2271 if (secttype == TYPE_SHARED_DATA_REF) {
2272 SHARED_DATA_REF* sectsdr = (SHARED_DATA_REF*)(ptr + sizeof(UINT8));
2273
2274 if (sectsdr->offset == parent)
2275 return sectsdr->count;
2276 }
2277
2278 len -= sectlen;
2279 ptr += sizeof(UINT8) + sectlen;
2280 inline_rc += sectcount;
2281 }
2282
2283 // FIXME - what if old?
2284
2285 if (inline_rc == ei->refcount)
2286 return 0;
2287
2288 searchkey.obj_id = address;
2289 searchkey.obj_type = TYPE_SHARED_DATA_REF;
2290 searchkey.offset = parent;
2291
2292 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2293 if (!NT_SUCCESS(Status)) {
2294 ERR("error - find_item returned %08x\n", Status);
2295 return 0;
2296 }
2297
2298 if (!keycmp(searchkey, tp.item->key)) {
2299 if (tp.item->size < sizeof(UINT32))
2300 ERR("(%llx,%x,%llx) has size %u, not %u as expected\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(UINT32));
2301 else {
2302 UINT32* count = (UINT32*)tp.item->data;
2303 return *count;
2304 }
2305 }
2306
2307 return 0;
2308 }
A free Windows-compatible Operating System