ReactOS  0.4.14-dev-337-gf981a68
extent-tree.c
Go to the documentation of this file.
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 {
22 
23  union {
28  };
29 
32 } extent_ref;
33 
35  uint32_t high_crc = 0xffffffff, low_crc = 0xffffffff;
36 
37  high_crc = calc_crc32c(high_crc, (uint8_t*)&root, sizeof(uint64_t));
38  low_crc = calc_crc32c(low_crc, (uint8_t*)&objid, sizeof(uint64_t));
39  low_crc = calc_crc32c(low_crc, (uint8_t*)&offset, sizeof(uint64_t));
40 
41  return ((uint64_t)high_crc << 31) ^ (uint64_t)low_crc;
42 }
43 
45  return get_extent_data_ref_hash2(edr->root, edr->objid, edr->offset);
46 }
47 
49  if (type == TYPE_EXTENT_DATA_REF) {
51  } else if (type == TYPE_SHARED_BLOCK_REF) {
53  return sbr->offset;
54  } else if (type == TYPE_SHARED_DATA_REF) {
56  return sdr->offset;
57  } else if (type == TYPE_TREE_BLOCK_REF) {
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);
70 
71  ExFreePool(er);
72  }
73 }
74 
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) {
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 
95  if (!er2) {
96  ERR("out of memory\n");
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 
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) {
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 
127  if (!er2) {
128  ERR("out of memory\n");
130  }
131 
133  er2->sbr.offset = parent;
134 
135  InsertTailList(extent_refs, &er2->list_entry);
136 
137  return STATUS_SUCCESS;
138 }
139 
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) {
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 
158  if (!er2) {
159  ERR("out of memory\n");
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)) {
183  LIST_ENTRY* le;
184  bool inserted = false;
185 
186  le = newlist.Flink;
187  while (le != &newlist) {
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 
210  KEY* firstitem, uint8_t level, PIRP Irp) {
212  LIST_ENTRY *le, *next_le;
213  uint64_t refcount;
214  uint16_t inline_len;
215  bool all_inline = true;
216  extent_ref* first_noninline = NULL;
217  EXTENT_ITEM* ei;
218  uint8_t* 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 
231  inline_len += sizeof(EXTENT_ITEM2);
232 
233  le = extent_refs->Flink;
234  while (le != extent_refs) {
236  uint64_t rc;
237 
238  next_le = le->Flink;
239 
240  rc = get_extent_data_refcount(er->type, &er->edr);
241 
242  if (rc == 0) {
244 
245  ExFreePool(er);
246  } else {
247  uint16_t 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_t)(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");
269  }
270 
271  ei->refcount = refcount;
272  ei->generation = Vcb->superblock.generation;
273  ei->flags = flags;
274 
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_t*)&ei2[1];
291  } else
292  siptr = (uint8_t*)&ei[1];
293 
294  sort_extent_refs(extent_refs);
295 
296  le = extent_refs->Flink;
297  while (le != extent_refs) {
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) {
327  uint16_t len;
328  uint8_t* data;
329 
330  if (er->type == TYPE_EXTENT_DATA_REF) {
331  len = sizeof(EXTENT_DATA_REF);
332 
334 
335  if (!data) {
336  ERR("out of memory\n");
338  }
339 
340  RtlCopyMemory(data, &er->edr, len);
341  } else if (er->type == TYPE_SHARED_DATA_REF) {
342  len = sizeof(uint32_t);
343 
345 
346  if (!data) {
347  ERR("out of memory\n");
349  }
350 
351  *((uint32_t*)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 
373  KEY searchkey;
374  traverse_ptr tp, next_tp;
375  LIST_ENTRY extent_refs;
376  uint64_t 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 %I64x not found\n", address);
392  return STATUS_INTERNAL_ERROR;
393  }
394 
395  size = tp.item->key.offset;
396 
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 
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 {
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 
432  if (!NT_SUCCESS(Status)) {
433  ERR("delete_tree_item returned %08x\n", Status);
434  goto end;
435  }
436  }
437 
439  break;
440  }
441 
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 
455  KEY searchkey;
457  ULONG len, max_extent_item_size;
459  EXTENT_ITEM* ei;
460  uint8_t* ptr;
461  uint64_t inline_rc, offset;
462  uint8_t* 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 
485  uint16_t 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_t);
490  eisize += datalen;
491 
493  if (!ei) {
494  ERR("out of memory\n");
496  }
497 
499  ei->generation = Vcb->superblock.generation;
501  ptr = (uint8_t*)&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_t*)&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 %I64x exists, but with size %I64x rather than %I64x 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("(%I64x,%x,%I64x) 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_t*)&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("(%I64x,%x,%I64x) 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_t secttype = *ptr;
568  ULONG sectlen = get_extent_data_len(secttype);
569  uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
570 
571  len--;
572 
573  if (sectlen > len) {
574  ERR("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
589 
590  if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
592  EXTENT_DATA_REF* sectedr2;
593 
595  if (!newei) {
596  ERR("out of memory\n");
598  }
599 
600  RtlCopyMemory(newei, tp.item->data, tp.item->size);
601 
602  newei->refcount += rc;
603 
604  sectedr2 = (EXTENT_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectedr - tp.item->data));
605  sectedr2->count += rc;
606 
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_t));
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_t));
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_t));
638 
639  if (sectsdr->offset == sdr->offset) {
641  SHARED_DATA_REF* sectsdr2;
642 
644  if (!newei) {
645  ERR("out of memory\n");
647  }
648 
649  RtlCopyMemory(newei, tp.item->data, tp.item->size);
650 
651  newei->refcount += rc;
652 
653  sectsdr2 = (SHARED_DATA_REF*)((uint8_t*)newei + ((uint8_t*)sectsdr - tp.item->data));
654  sectsdr2->count += rc;
655 
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_t) + sectlen;
678  inline_rc += sectcount;
679  }
680 
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_t) + datalen < max_extent_item_size) {
688  len = tp.item->size - sizeof(EXTENT_ITEM);
689  ptr = (uint8_t*)&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_t secttype = *ptr;
701  ULONG sectlen = get_extent_data_len(secttype);
702 
703  if (secttype > type)
704  break;
705 
706  if (secttype == type) {
707  uint64_t sectoff = get_extent_hash(secttype, ptr + 1);
708 
709  if (sectoff < offset)
710  break;
711  }
712 
713  len -= sectlen + sizeof(uint8_t);
714  ptr += sizeof(uint8_t) + sectlen;
715  }
716 
718  RtlCopyMemory(newei, tp.item->data, ptr - tp.item->data);
719 
721 
722  if (len > 0)
723  RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data) + sizeof(uint8_t) + datalen, ptr, len);
724 
725  ptr = (ptr - tp.item->data) + (uint8_t*)newei;
726 
727  *ptr = type;
728  RtlCopyMemory(ptr + 1, data, datalen);
729 
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_t) + 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_t)) {
762  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, sizeof(uint32_t));
763  return STATUS_INTERNAL_ERROR;
764  } else if (type != TYPE_SHARED_DATA_REF && tp2.item->size < datalen) {
765  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);
766  return STATUS_INTERNAL_ERROR;
767  }
768 
770  if (!data2) {
771  ERR("out of memory\n");
773  }
774 
775  RtlCopyMemory(data2, tp2.item->data, tp2.item->size);
776 
777  if (type == TYPE_EXTENT_DATA_REF) {
779 
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_t* sdr = (uint32_t*)data2;
788 
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 
808  if (!newei) {
809  ERR("out of memory\n");
811  }
812 
813  RtlCopyMemory(newei, tp.item->data, tp.item->size);
814 
816 
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) {
837 
839  if (!data2) {
840  ERR("out of memory\n");
842  }
843 
844  datalen = sizeof(uint32_t);
845 
846  *((uint32_t*)data2) = sdr->count;
847  } else if (type == TYPE_TREE_BLOCK_REF || type == TYPE_SHARED_BLOCK_REF) {
848  data2 = NULL;
849  datalen = 0;
850  } else {
852  if (!data2) {
853  ERR("out of memory\n");
855  }
856 
858  }
859 
861  if (!NT_SUCCESS(Status)) {
862  ERR("insert_tree_item returned %08x\n", Status);
863  return Status;
864  }
865 
867  if (!newei) {
868  ERR("out of memory\n");
870  }
871 
872  RtlCopyMemory(newei, tp.item->data, tp.item->size);
873 
875 
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 
892  EXTENT_DATA_REF edr;
893 
894  edr.root = root;
895  edr.objid = inode;
896  edr.offset = offset;
897  edr.count = refcount;
898 
900 }
901 
904  KEY searchkey;
906  traverse_ptr tp, tp2;
907  EXTENT_ITEM* ei;
908  ULONG len;
909  uint64_t inline_rc;
910  uint8_t* ptr;
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 %I64x\n", address);
943  return STATUS_INTERNAL_ERROR;
944  }
945 
946  if (tp.item->key.offset != size) {
947  ERR("extent %I64x had length %I64x, not %I64x 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 
960  }
961  }
962 
963  if (tp.item->size < sizeof(EXTENT_ITEM)) {
964  ERR("(%I64x,%x,%I64x) 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_t*)&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("(%I64x,%x,%I64x) 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 %I64x, 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_t secttype = *ptr;
994  uint16_t sectlen = get_extent_data_len(secttype);
995  uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
996 
997  len--;
998 
999  if (sectlen > len) {
1000  ERR("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
1013 
1014  if (sectedr->root == edr->root && sectedr->objid == edr->objid && sectedr->offset == edr->offset) {
1015  uint16_t neweilen;
1016  EXTENT_ITEM* newei;
1017 
1018  if (ei->refcount == edr->count) {
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_t) - sectlen;
1040 
1041  newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1042  if (!newei) {
1043  ERR("out of memory\n");
1045  }
1046 
1047  if (sectedr->count > edr->count) {
1048  EXTENT_DATA_REF* newedr = (EXTENT_DATA_REF*)((uint8_t*)newei + ((uint8_t*)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_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1058  }
1059 
1060  newei->refcount -= rc;
1061 
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_t));
1079 
1080  if (sectsdr->offset == sdr->offset) {
1081  EXTENT_ITEM* newei;
1082  uint16_t neweilen;
1083 
1084  if (ei->refcount == sectsdr->count) {
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_t) - sectlen;
1106 
1107  newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1108  if (!newei) {
1109  ERR("out of memory\n");
1111  }
1112 
1113  if (sectsdr->count > sdr->count) {
1114  SHARED_DATA_REF* newsdr = (SHARED_DATA_REF*)((uint8_t*)newei + ((uint8_t*)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_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1124  }
1125 
1126  newei->refcount -= rc;
1127 
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_t));
1145 
1146  if (secttbr->offset == tbr->offset) {
1147  EXTENT_ITEM* newei;
1148  uint16_t neweilen;
1149 
1150  if (ei->refcount == 1) {
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_t) - sectlen;
1161 
1162  newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1163  if (!newei) {
1164  ERR("out of memory\n");
1166  }
1167 
1168  RtlCopyMemory(newei, ei, ptr - tp.item->data);
1169 
1170  if (len > sectlen)
1171  RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1172 
1173  newei->refcount--;
1174 
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_t));
1192 
1193  if (sectsbr->offset == sbr->offset) {
1194  EXTENT_ITEM* newei;
1195  uint16_t neweilen;
1196 
1197  if (ei->refcount == 1) {
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_t) - sectlen;
1208 
1209  newei = ExAllocatePoolWithTag(PagedPool, neweilen, ALLOC_TAG);
1210  if (!newei) {
1211  ERR("out of memory\n");
1213  }
1214 
1215  RtlCopyMemory(newei, ei, ptr - tp.item->data);
1216 
1217  if (len > sectlen)
1218  RtlCopyMemory((uint8_t*)newei + (ptr - tp.item->data), ptr + sectlen + sizeof(uint8_t), len - sectlen);
1219 
1220  newei->refcount--;
1221 
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_t) + sectlen;
1244  inline_rc += sectcount;
1245  }
1246 
1247  if (inline_rc == ei->refcount) {
1248  ERR("entry not found in inline extent item for address %I64x\n", address);
1249  return STATUS_INTERNAL_ERROR;
1250  }
1251 
1252  if (type == TYPE_SHARED_DATA_REF)
1253  datalen = sizeof(uint32_t);
1255  datalen = 0;
1256 
1257  searchkey.obj_id = address;
1258  searchkey.obj_type = type;
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("(%I64x,%x,%I64x) 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("(%I64x,%x,%I64x) 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;
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) {
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) {
1316 
1317  if (!newedr) {
1318  ERR("out of memory\n");
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 
1334  if (!newei) {
1335  ERR("out of memory\n");
1337  }
1338 
1339  RtlCopyMemory(newei, tp.item->data, tp.item->size);
1340 
1341  newei->refcount -= rc;
1342 
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) {
1362 
1363  if (tp2.item->key.offset == sdr->offset) {
1364  uint32_t* sectsdrcount = (uint32_t*)tp2.item->data;
1365  EXTENT_ITEM* newei;
1366 
1367  if (ei->refcount == sdr->count) {
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) {
1399 
1400  if (!newsdr) {
1401  ERR("out of memory\n");
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 
1415  if (!newei) {
1416  ERR("out of memory\n");
1418  }
1419 
1420  RtlCopyMemory(newei, tp.item->data, tp.item->size);
1421 
1422  newei->refcount -= rc;
1423 
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) {
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 
1467  if (!newei) {
1468  ERR("out of memory\n");
1470  }
1471 
1472  RtlCopyMemory(newei, tp.item->data, tp.item->size);
1473 
1474  newei->refcount -= rc;
1475 
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) {
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 
1519  if (!newei) {
1520  ERR("out of memory\n");
1522  }
1523 
1524  RtlCopyMemory(newei, tp.item->data, tp.item->size);
1525 
1526  newei->refcount -= rc;
1527 
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 
1548  uint64_t offset, uint32_t 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 
1557 }
1558 
1560  uint8_t 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 
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 %I64x in extent tree\n", address);
1585  return 0;
1586  }
1587 
1588  if (tp.item->key.offset != size) {
1589  ERR("extent %I64x had size %I64x, not %I64x 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_t len = tp.item->size - sizeof(EXTENT_ITEM);
1596  uint8_t* ptr = (uint8_t*)&ei[1];
1597 
1598  while (len > 0) {
1599  uint8_t secttype = *ptr;
1600  ULONG sectlen = get_extent_data_len(secttype);
1601  uint32_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
1602 
1603  len--;
1604 
1605  if (sectlen > len) {
1606  ERR("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
1617 
1618  if (sectedr->root == root && sectedr->objid == objid && sectedr->offset == offset)
1619  return sectcount;
1620  }
1621 
1622  len -= sectlen;
1623  ptr += sizeof(uint8_t) + 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("(%I64x,%x,%I64x) 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 {
1642 
1643  return edr->count;
1644  }
1645  }
1646 
1647  return 0;
1648 }
1649 
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 
1674  ERR("couldn't find (%I64x,%x,%I64x) in extent tree\n", address, TYPE_EXTENT_ITEM, size);
1675  return 0;
1676  } else if (tp.item->key.offset != size) {
1677  ERR("extent %I64x had size %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
1678  return 0;
1679  }
1680 
1681  if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
1683 
1684  return eiv0->refcount;
1685  } else if (tp.item->size < sizeof(EXTENT_ITEM)) {
1686  ERR("(%I64x,%x,%I64x) 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 
1697  KEY searchkey;
1698  traverse_ptr tp, next_tp;
1699  NTSTATUS Status;
1700  uint64_t rc, rcrun, root = 0, inode = 0, offset = 0;
1701  uint32_t len;
1702  EXTENT_ITEM* ei;
1703  uint8_t* ptr;
1704  bool b;
1705 
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 (%I64x,%x,%I64x)\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("(%I64x,%x,%I64x) 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_t*)&ei[1];
1741 
1742  if (ei->flags & EXTENT_ITEM_TREE_BLOCK) {
1743  if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2)) {
1744  WARN("(%I64x,%x,%I64x) 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_t secttype = *ptr;
1758  ULONG sectlen = get_extent_data_len(secttype);
1759  uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
1760 
1761  len--;
1762 
1763  if (sectlen > len) {
1764  WARN("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
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_t) + 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) {
1800 
1801  if (tp.item->size < sizeof(EXTENT_DATA_REF)) {
1802  WARN("(%I64x,%x,%I64x) 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 
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 
1858  ERR("couldn't find %I64x 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("(%I64x,%x,%I64x) 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 
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 
1899  ERR("couldn't find %I64x 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("(%I64x,%x,%I64x) 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 
1916  LIST_ENTRY* le;
1917  changed_extent* ce;
1918 
1919  le = c->changed_extents.Flink;
1920  while (le != &c->changed_extents) {
1922 
1923  if (ce->address == address && ce->size == size)
1924  return ce;
1925 
1926  le = le->Flink;
1927  }
1928 
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);
1944 
1945  InsertTailList(&c->changed_extents, &ce->list_entry);
1946 
1947  return ce;
1948 }
1949 
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_t 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");
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 %I64x in extent tree\n", address);
1984  goto end;
1985  }
1986 
1987  if (tp.item->key.offset != size) {
1988  ERR("extent %I64x had size %I64x, not %I64x as expected\n", address, tp.item->key.offset, size);
1990  goto end;
1991  }
1992 
1993  if (tp.item->size == sizeof(EXTENT_ITEM_V0)) {
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("(%I64x,%x,%I64x) 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));
2004  goto end;
2005  }
2006  }
2007 
2008  le = ce->refs.Flink;
2009  while (le != &ce->refs) {
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;
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) {
2030 
2031  if (!cer) {
2032  ERR("out of memory\n");
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 
2047 
2048  if (!cer) {
2049  ERR("out of memory\n");
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 
2068 
2069 end:
2070  ExReleaseResourceLite(&c->changed_extents_lock);
2071 
2072  return Status;
2073 }
2074 
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) {
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 
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 
2119  NTSTATUS Status;
2120  KEY searchkey;
2121  traverse_ptr tp;
2122  uint64_t inline_rc;
2123  EXTENT_ITEM* ei;
2124  uint32_t len;
2125  uint8_t* 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 
2138  TRACE("could not find address %I64x 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 %I64x had size %I64x, not %I64x 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("(%I64x,%x,%I64x): 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_t*)&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("(%I64x,%x,%I64x): 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_t secttype = *ptr;
2171  ULONG sectlen = get_extent_data_len(secttype);
2172  uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
2173 
2174  len--;
2175 
2176  if (sectlen > len) {
2177  ERR("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
2188 
2189  if (sectsbr->offset == parent)
2190  return 1;
2191  }
2192 
2193  len -= sectlen;
2194  ptr += sizeof(uint8_t) + 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 
2220  NTSTATUS Status;
2221  KEY searchkey;
2222  traverse_ptr tp;
2223  uint64_t inline_rc;
2224  EXTENT_ITEM* ei;
2225  uint32_t len;
2226  uint8_t* 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 
2239  TRACE("could not find address %I64x in extent tree\n", address);
2240  return 0;
2241  }
2242 
2243  if (tp.item->size < sizeof(EXTENT_ITEM)) {
2244  ERR("(%I64x,%x,%I64x): 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_t*)&ei[1];
2253 
2254  while (len > 0) {
2255  uint8_t secttype = *ptr;
2256  ULONG sectlen = get_extent_data_len(secttype);
2257  uint64_t sectcount = get_extent_data_refcount(secttype, ptr + sizeof(uint8_t));
2258 
2259  len--;
2260 
2261  if (sectlen > len) {
2262  ERR("(%I64x,%x,%I64x): %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("(%I64x,%x,%I64x): 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_t));
2273 
2274  if (sectsdr->offset == parent)
2275  return sectsdr->count;
2276  }
2277 
2278  len -= sectlen;
2279  ptr += sizeof(uint8_t) + 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_t))
2300  ERR("(%I64x,%x,%I64x) 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_t));
2301  else {
2303  return *count;
2304  }
2305  }
2306 
2307  return 0;
2308 }
uint64_t obj_id
Definition: btrfs.h:128
SHARED_DATA_REF sdr
Definition: extent-tree.c:25
GLint level
Definition: gl.h:1546
TREE_BLOCK_REF tbr
Definition: extent-tree.c:26
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
uint64_t root
Definition: btrfs.h:408
uint8_t obj_type
Definition: btrfs.h:129
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
NTSTATUS decrease_extent_refcount_tree(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint8_t level, PIRP Irp)
Definition: extent-tree.c:1559
LIST_ENTRY list_entry
Definition: btrfs_drv.h:599
uint32_t count
Definition: btrfs.h:411
_In_ PIRP Irp
Definition: csq.h:116
uint64_t offset
Definition: btrfs.h:397
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
FORCEINLINE VOID InsertHeadList(_Inout_ PLIST_ENTRY ListHead, _Inout_ __drv_aliasesMem PLIST_ENTRY Entry)
Definition: rtlfuncs.h:201
LIST_ENTRY list_entry
Definition: btrfs_drv.h:610
GLuint GLuint GLsizei count
Definition: gl.h:1545
static uint64_t get_extent_hash(uint8_t type, void *data)
Definition: extent-tree.c:48
struct _root root
#define keycmp(key1, key2)
Definition: btrfs_drv.h:991
#define WARN(fmt,...)
Definition: debug.h:111
LONG NTSTATUS
Definition: precomp.h:26
uint64_t objid
Definition: btrfs.h:396
GLintptr offset
Definition: glext.h:5920
uint16_t size
Definition: btrfs_drv.h:415
#define TYPE_TREE_BLOCK_REF
Definition: btrfs.h:33
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
uint64_t find_extent_shared_tree_refcount(device_extension *Vcb, uint64_t address, uint64_t parent, PIRP Irp)
Definition: extent-tree.c:2118
uint32_t refcount
Definition: btrfs.h:381
#define BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
Definition: btrfs.h:114
static uint32_t find_extent_data_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, PIRP Irp)
Definition: extent-tree.c:1568
GLuint GLuint end
Definition: gl.h:1545
uint64_t old_size
Definition: btrfs_drv.h:592
unsigned short int uint16_t
Definition: acefiex.h:54
#define InsertTailList(ListHead, Entry)
#define TYPE_METADATA_ITEM
Definition: btrfs.h:32
int const JOCTET unsigned int datalen
Definition: jpeglib.h:1027
LIST_ENTRY old_refs
Definition: btrfs_drv.h:598
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
uint64_t offset
Definition: btrfs.h:130
static uint32_t calc_crc32c(uint32_t seed, uint8_t *msg, ULONG msglen)
Definition: recv.cpp:134
uint8_t * data
Definition: btrfs_drv.h:416
static WCHAR superseded[MAX_STRING_RESOURCE_LEN]
Definition: object.c:1817
Definition: fs.h:78
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
LIST_ENTRY list_entry
Definition: extent-tree.c:31
BOOLEAN NTAPI ExAcquireResourceExclusiveLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
Definition: resource.c:770
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:451
#define ALLOC_TAG
Definition: btrfs_drv.h:91
static void free_extent_refs(LIST_ENTRY *extent_refs)
Definition: extent-tree.c:66
uint64_t hash
Definition: extent-tree.c:30
EXTENT_DATA_REF edr
Definition: btrfs_drv.h:606
uint64_t refcount
Definition: btrfs.h:370
static PVOID ptr
Definition: dispmode.c:27
uint32_t count
Definition: btrfs.h:398
NTSTATUS increase_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:453
uint64_t count
Definition: btrfs_drv.h:593
smooth NULL
Definition: ftsmooth.c:416
#define TYPE_EXTENT_ITEM
Definition: btrfs.h:31
NTSTATUS update_changed_extent_ref(device_extension *Vcb, chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, int32_t count, bool no_csum, bool superseded, PIRP Irp)
Definition: extent-tree.c:1950
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
static NTSTATUS convert_old_extent(device_extension *Vcb, uint64_t address, bool tree, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:371
void add_checksum_entry(device_extension *Vcb, uint64_t address, ULONG length, uint32_t *csum, PIRP Irp)
Definition: flushthread.c:2555
uint64_t root
Definition: btrfs.h:395
uint64_t offset
Definition: btrfs.h:391
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
#define b
Definition: ke_i.h:79
#define TYPE_EXTENT_DATA_REF
Definition: btrfs.h:34
void update_extent_flags(device_extension *Vcb, uint64_t address, uint64_t flags, PIRP Irp)
Definition: extent-tree.c:1875
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2855
static LONG find_item(PropertyBag *This, LPCOLESTR name)
Definition: propertybag.c:110
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
static NTSTATUS add_shared_data_extent_ref(LIST_ENTRY *extent_refs, uint64_t parent, uint32_t count)
Definition: extent-tree.c:75
#define TYPE_SHARED_DATA_REF
Definition: btrfs.h:37
NTSTATUS increase_extent_refcount_data(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t inode, uint64_t offset, uint32_t refcount, PIRP Irp)
Definition: extent-tree.c:891
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define TRACE(s)
Definition: solgame.cpp:4
GLsizeiptr size
Definition: glext.h:5919
bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *next_tp, bool ignore, PIRP Irp)
Definition: treefuncs.c:592
r parent
Definition: btrfs.c:2869
if(!(yy_init))
Definition: macro.lex.yy.c:714
uint64_t size
Definition: btrfs_drv.h:591
static __inline uint64_t get_extent_data_ref_hash(EXTENT_DATA_REF *edr)
Definition: extent-tree.c:44
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
static __inline uint16_t get_extent_data_len(uint8_t type)
Definition: btrfs_drv.h:1018
#define Vcb
Definition: cdprocs.h:1425
const GLubyte * c
Definition: glext.h:8905
KEY firstitem
Definition: btrfs.h:376
#define TYPE_EXTENT_REF_V0
Definition: btrfs.h:35
GLuint address
Definition: glext.h:9393
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1817
bool is_extent_unique(device_extension *Vcb, uint64_t address, uint64_t size, PIRP Irp)
Definition: extent-tree.c:1696
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
void add_changed_extent_ref(chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, uint32_t count, bool no_csum)
Definition: extent-tree.c:2075
GLbitfield flags
Definition: glext.h:7161
#define EXTENT_ITEM_DATA
Definition: btrfs.h:365
NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _In_ uint64_t obj_id, _In_ uint8_t obj_type, _In_ uint64_t offset, _In_reads_bytes_opt_(size) _When_(return >=0, __drv_aliasesMem) void *data, _In_ uint16_t size, _Out_opt_ traverse_ptr *ptp, _In_opt_ PIRP Irp)
Definition: treefuncs.c:857
#define TYPE_SHARED_BLOCK_REF
Definition: btrfs.h:36
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
tree_data * item
Definition: btrfs_drv.h:502
uint64_t offset
Definition: btrfs.h:415
static NTSTATUS add_shared_block_extent_ref(LIST_ENTRY *extent_refs, uint64_t parent)
Definition: extent-tree.c:109
uint32_t count
Definition: btrfs.h:420
uint8_t level
Definition: btrfs.h:377
GLenum GLsizei len
Definition: glext.h:6722
static NTSTATUS add_tree_block_extent_ref(LIST_ENTRY *extent_refs, uint64_t root)
Definition: extent-tree.c:140
Definition: typedefs.h:117
BYTE uint8_t
Definition: msvideo1.c:66
uint64_t generation
Definition: btrfs.h:371
#define uint64_t
Definition: nsiface.idl:62
INT32 int32_t
Definition: types.h:71
Status
Definition: gdiplustypes.h:24
static void sort_extent_refs(LIST_ENTRY *extent_refs)
Definition: extent-tree.c:171
NTSTATUS decrease_extent_refcount_data(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t root, uint64_t inode, uint64_t offset, uint32_t refcount, bool superseded, PIRP Irp)
Definition: extent-tree.c:1547
#define ERR(fmt,...)
Definition: debug.h:109
uint64_t get_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, PIRP Irp)
Definition: extent-tree.c:1650
Definition: btrfs.h:127
UINT64 uint64_t
Definition: types.h:77
#define uint8_t
Definition: nsiface.idl:59
#define EXTENT_ITEM_TREE_BLOCK
Definition: btrfs.h:366
static const WCHAR data2[]
Definition: db.c:2971
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
SHARED_BLOCK_REF sbr
Definition: extent-tree.c:27
LIST_ENTRY refs
Definition: btrfs_drv.h:597
NTSTATUS decrease_extent_refcount(device_extension *Vcb, uint64_t address, uint64_t size, uint8_t type, void *data, KEY *firstitem, uint8_t level, uint64_t parent, bool superseded, PIRP Irp)
Definition: extent-tree.c:902
static changed_extent * get_changed_extent_item(chunk *c, uint64_t address, uint64_t size, bool no_csum)
Definition: extent-tree.c:1915
Definition: list.h:27
static __inline uint32_t get_extent_data_refcount(uint8_t type, void *data)
Definition: btrfs_drv.h:1040
UINT32 uint32_t
Definition: types.h:75
uint64_t get_extent_data_ref_hash2(uint64_t root, uint64_t objid, uint64_t offset)
Definition: extent-tree.c:34
uint64_t address
Definition: btrfs_drv.h:590
uint64_t get_extent_flags(device_extension *Vcb, uint64_t address, PIRP Irp)
Definition: extent-tree.c:1834
unsigned int ULONG
Definition: retypes.h:1
static NTSTATUS construct_extent_item(device_extension *Vcb, uint64_t address, uint64_t size, uint64_t flags, LIST_ENTRY *extent_refs, KEY *firstitem, uint8_t level, PIRP Irp)
Definition: extent-tree.c:209
#define EXTENT_ITEM_SHARED_BACKREFS
Definition: btrfs.h:367
uint64_t flags
Definition: btrfs.h:372
#define uint32_t
Definition: nsiface.idl:61
return STATUS_SUCCESS
Definition: btrfs.c:2938
uint64_t offset
Definition: btrfs.h:419
uint64_t old_count
Definition: btrfs_drv.h:594
uint32_t find_extent_shared_data_refcount(device_extension *Vcb, uint64_t address, uint64_t parent, PIRP Irp)
Definition: extent-tree.c:2219
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
EXTENT_DATA_REF edr
Definition: extent-tree.c:24
NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp)
Definition: treefuncs.c:989
uint8_t type
Definition: extent-tree.c:21
Definition: tftpd.h:137