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