ReactOS  0.4.14-dev-606-g14ebc0b
flushthread.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 <ata.h>
20 #include <ntddscsi.h>
21 #include <ntddstor.h>
22 
23 #define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - sizeof(leaf_node))
24 
25 // #define DEBUG_WRITE_LOOPS
26 
27 typedef struct {
31 
32 typedef struct {
37 
38 typedef struct {
43 
46 
47 #ifndef _MSC_VER // not in mingw yet
48 #define DEVICE_DSM_FLAG_TRIM_NOT_FS_ALLOCATED 0x80000000
49 #endif
50 
51 _Function_class_(IO_COMPLETION_ROUTINE)
52 static NTSTATUS __stdcall write_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
53  write_context* context = conptr;
54 
56 
57  context->iosb = Irp->IoStatus;
58  KeSetEvent(&context->Event, 0, false);
59 
61 }
62 
67  PIRP Irp;
70 
71  TRACE("(%p, %I64x, %p, %x)\n", device, address, data, length);
72 
74 
76 
77  offset.QuadPart = address;
78 
79  Irp = IoAllocateIrp(device->StackSize, false);
80 
81  if (!Irp) {
82  ERR("IoAllocateIrp failed\n");
84  }
85 
88  IrpSp->FileObject = fileobj;
89 
90  if (device->Flags & DO_BUFFERED_IO) {
91  Irp->AssociatedIrp.SystemBuffer = data;
92 
93  Irp->Flags = IRP_BUFFERED_IO;
94  } else if (device->Flags & DO_DIRECT_IO) {
95  Irp->MdlAddress = IoAllocateMdl(data, length, false, false, NULL);
96  if (!Irp->MdlAddress) {
97  DbgPrint("IoAllocateMdl failed\n");
99  goto exit;
100  }
101 
103 
104  _SEH2_TRY {
108  } _SEH2_END;
109 
110  if (!NT_SUCCESS(Status)) {
111  ERR("MmProbeAndLockPages threw exception %08x\n", Status);
112  IoFreeMdl(Irp->MdlAddress);
113  goto exit;
114  }
115  } else {
116  Irp->UserBuffer = data;
117  }
118 
119  IrpSp->Parameters.Write.Length = length;
120  IrpSp->Parameters.Write.ByteOffset = offset;
121 
122  Irp->UserIosb = &context.iosb;
123 
124  Irp->UserEvent = &context.Event;
125 
126  IoSetCompletionRoutine(Irp, write_completion, &context, true, true, true);
127 
129 
130  if (Status == STATUS_PENDING) {
132  Status = context.iosb.Status;
133  }
134 
135  if (!NT_SUCCESS(Status)) {
136  ERR("IoCallDriver returned %08x\n", Status);
137  }
138 
139  if (device->Flags & DO_DIRECT_IO) {
140  MmUnlockPages(Irp->MdlAddress);
141  IoFreeMdl(Irp->MdlAddress);
142  }
143 
144 exit:
145  IoFreeIrp(Irp);
146 
147  return Status;
148 }
149 
152  if (!s) {
153  ERR("out of memory\n");
154  return;
155  }
156 
157  s->address = address;
158  s->size = size;
159  dev->num_trim_entries++;
160 
161  InsertTailList(&dev->trim_list, &s->list_entry);
162 }
163 
165  ULONG type;
166 
167  if (Vcb->trim && !Vcb->options.no_trim) {
168  if (c->chunk_item->type & BLOCK_FLAG_DUPLICATE)
170  else if (c->chunk_item->type & BLOCK_FLAG_RAID0)
172  else if (c->chunk_item->type & BLOCK_FLAG_RAID1)
174  else if (c->chunk_item->type & BLOCK_FLAG_RAID10)
176  else if (c->chunk_item->type & BLOCK_FLAG_RAID5)
178  else if (c->chunk_item->type & BLOCK_FLAG_RAID6)
180  else // SINGLE
182  }
183 
184  while (!IsListEmpty(&c->deleting)) {
185  space* s = CONTAINING_RECORD(c->deleting.Flink, space, list_entry);
186 
187  if (Vcb->trim && !Vcb->options.no_trim && (!Vcb->options.no_barrier || !(c->chunk_item->type & BLOCK_FLAG_METADATA))) {
188  CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
189 
191  uint16_t i;
192 
193  for (i = 0; i < c->chunk_item->num_stripes; i++) {
194  if (c->devices[i] && c->devices[i]->devobj && !c->devices[i]->readonly && c->devices[i]->trim)
195  add_trim_entry(c->devices[i], s->address - c->offset + cis[i].offset, s->size);
196  }
197  } else if (type == BLOCK_FLAG_RAID0) {
198  uint64_t startoff, endoff;
199  uint16_t startoffstripe, endoffstripe, i;
200 
201  get_raid0_offset(s->address - c->offset, c->chunk_item->stripe_length, c->chunk_item->num_stripes, &startoff, &startoffstripe);
202  get_raid0_offset(s->address - c->offset + s->size - 1, c->chunk_item->stripe_length, c->chunk_item->num_stripes, &endoff, &endoffstripe);
203 
204  for (i = 0; i < c->chunk_item->num_stripes; i++) {
205  if (c->devices[i] && c->devices[i]->devobj && !c->devices[i]->readonly && c->devices[i]->trim) {
206  uint64_t stripestart, stripeend;
207 
208  if (startoffstripe > i)
209  stripestart = startoff - (startoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
210  else if (startoffstripe == i)
211  stripestart = startoff;
212  else
213  stripestart = startoff - (startoff % c->chunk_item->stripe_length);
214 
215  if (endoffstripe > i)
216  stripeend = endoff - (endoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
217  else if (endoffstripe == i)
218  stripeend = endoff + 1;
219  else
220  stripeend = endoff - (endoff % c->chunk_item->stripe_length);
221 
222  if (stripestart != stripeend)
223  add_trim_entry(c->devices[i], stripestart + cis[i].offset, stripeend - stripestart);
224  }
225  }
226  } else if (type == BLOCK_FLAG_RAID10) {
227  uint64_t startoff, endoff;
228  uint16_t sub_stripes, startoffstripe, endoffstripe, i;
229 
230  sub_stripes = max(1, c->chunk_item->sub_stripes);
231 
232  get_raid0_offset(s->address - c->offset, c->chunk_item->stripe_length, c->chunk_item->num_stripes / sub_stripes, &startoff, &startoffstripe);
233  get_raid0_offset(s->address - c->offset + s->size - 1, c->chunk_item->stripe_length, c->chunk_item->num_stripes / sub_stripes, &endoff, &endoffstripe);
234 
235  startoffstripe *= sub_stripes;
236  endoffstripe *= sub_stripes;
237 
238  for (i = 0; i < c->chunk_item->num_stripes; i += sub_stripes) {
239  ULONG j;
240  uint64_t stripestart, stripeend;
241 
242  if (startoffstripe > i)
243  stripestart = startoff - (startoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
244  else if (startoffstripe == i)
245  stripestart = startoff;
246  else
247  stripestart = startoff - (startoff % c->chunk_item->stripe_length);
248 
249  if (endoffstripe > i)
250  stripeend = endoff - (endoff % c->chunk_item->stripe_length) + c->chunk_item->stripe_length;
251  else if (endoffstripe == i)
252  stripeend = endoff + 1;
253  else
254  stripeend = endoff - (endoff % c->chunk_item->stripe_length);
255 
256  if (stripestart != stripeend) {
257  for (j = 0; j < sub_stripes; j++) {
258  if (c->devices[i+j] && c->devices[i+j]->devobj && !c->devices[i+j]->readonly && c->devices[i+j]->trim)
259  add_trim_entry(c->devices[i+j], stripestart + cis[i+j].offset, stripeend - stripestart);
260  }
261  }
262  }
263  }
264  // FIXME - RAID5(?), RAID6(?)
265  }
266 
267  RemoveEntryList(&s->list_entry);
268  ExFreePool(s);
269  }
270 }
271 
272 typedef struct {
277 #ifdef DEBUG_TRIM_EMULATION
278  PMDL mdl;
279  void* buf;
280 #endif
282 
283 typedef struct {
287 } ioctl_context;
288 
289 _Function_class_(IO_COMPLETION_ROUTINE)
290 static NTSTATUS __stdcall ioctl_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
291  ioctl_context* context = (ioctl_context*)conptr;
292  LONG left2 = InterlockedDecrement(&context->left);
293 
295  UNUSED(Irp);
296 
297  if (left2 == 0)
298  KeSetEvent(&context->Event, 0, false);
299 
301 }
302 
303 #ifdef DEBUG_TRIM_EMULATION
304 static void trim_emulation(device* dev) {
305  LIST_ENTRY* le;
307  unsigned int i = 0, count = 0;
308 
309  le = dev->trim_list.Flink;
310  while (le != &dev->trim_list) {
311  count++;
312  le = le->Flink;
313  }
314 
315  context.left = count;
316 
318 
320  if (!context.stripes) {
321  ERR("out of memory\n");
322  return;
323  }
324 
325  RtlZeroMemory(context.stripes, sizeof(ioctl_context_stripe) * context.left);
326 
327  i = 0;
328  le = dev->trim_list.Flink;
329  while (le != &dev->trim_list) {
330  ioctl_context_stripe* stripe = &context.stripes[i];
332 
333  WARN("(%I64x, %I64x)\n", s->address, s->size);
334 
335  stripe->Irp = IoAllocateIrp(dev->devobj->StackSize, false);
336 
337  if (!stripe->Irp) {
338  ERR("IoAllocateIrp failed\n");
339  } else {
342  IrpSp->FileObject = dev->fileobj;
343 
345 
346  if (!stripe->buf) {
347  ERR("out of memory\n");
348  } else {
349  RtlZeroMemory(stripe->buf, (uint32_t)s->size); // FIXME - randomize instead?
350 
351  stripe->mdl = IoAllocateMdl(stripe->buf, (uint32_t)s->size, false, false, NULL);
352 
353  if (!stripe->mdl) {
354  ERR("IoAllocateMdl failed\n");
355  } else {
357 
358  stripe->Irp->MdlAddress = stripe->mdl;
359 
360  IrpSp->Parameters.Write.ByteOffset.QuadPart = s->address;
361  IrpSp->Parameters.Write.Length = s->size;
362 
363  stripe->Irp->UserIosb = &stripe->iosb;
364 
365  IoSetCompletionRoutine(stripe->Irp, ioctl_completion, &context, true, true, true);
366 
367  IoCallDriver(dev->devobj, stripe->Irp);
368  }
369  }
370  }
371 
372  i++;
373 
374  le = le->Flink;
375  }
376 
378 
379  for (i = 0; i < count; i++) {
380  ioctl_context_stripe* stripe = &context.stripes[i];
381 
382  if (stripe->mdl)
383  IoFreeMdl(stripe->mdl);
384 
385  if (stripe->buf)
386  ExFreePool(stripe->buf);
387  }
388 
389  ExFreePool(context.stripes);
390 }
391 #endif
392 
394  LIST_ENTRY* le;
395  chunk* c;
396 #ifndef DEBUG_TRIM_EMULATION
397  ULONG num;
398 #endif
399 
400  TRACE("(%p)\n", Vcb);
401 
402  ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
403 
404  le = Vcb->chunks.Flink;
405  while (le != &Vcb->chunks) {
407 
408  if (c->space_changed) {
410 
411  if (c->space_changed)
413 
414  c->space_changed = false;
415 
417  }
418 
419  le = le->Flink;
420  }
421 
422  ExReleaseResourceLite(&Vcb->chunk_lock);
423 
424  if (Vcb->trim && !Vcb->options.no_trim) {
425 #ifndef DEBUG_TRIM_EMULATION
427  ULONG total_num;
428 
429  context.left = 0;
430 
431  le = Vcb->devices.Flink;
432  while (le != &Vcb->devices) {
434 
435  if (dev->devobj && !dev->readonly && dev->trim && dev->num_trim_entries > 0)
436  context.left++;
437 
438  le = le->Flink;
439  }
440 
441  if (context.left == 0)
442  return;
443 
444  total_num = context.left;
445  num = 0;
446 
448 
450  if (!context.stripes) {
451  ERR("out of memory\n");
452  return;
453  }
454 
455  RtlZeroMemory(context.stripes, sizeof(ioctl_context_stripe) * context.left);
456 #endif
457 
458  le = Vcb->devices.Flink;
459  while (le != &Vcb->devices) {
461 
462  if (dev->devobj && !dev->readonly && dev->trim && dev->num_trim_entries > 0) {
463 #ifdef DEBUG_TRIM_EMULATION
464  trim_emulation(dev);
465 #else
466  LIST_ENTRY* le2;
467  ioctl_context_stripe* stripe = &context.stripes[num];
468  DEVICE_DATA_SET_RANGE* ranges;
469  ULONG datalen = (ULONG)sector_align(sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES), sizeof(uint64_t)) + (dev->num_trim_entries * sizeof(DEVICE_DATA_SET_RANGE)), i;
471 
473  if (!stripe->dmdsa) {
474  ERR("out of memory\n");
475  goto nextdev;
476  }
477 
478  stripe->dmdsa->Size = sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES);
479  stripe->dmdsa->Action = DeviceDsmAction_Trim;
481  stripe->dmdsa->ParameterBlockOffset = 0;
482  stripe->dmdsa->ParameterBlockLength = 0;
483  stripe->dmdsa->DataSetRangesOffset = (ULONG)sector_align(sizeof(DEVICE_MANAGE_DATA_SET_ATTRIBUTES), sizeof(uint64_t));
484  stripe->dmdsa->DataSetRangesLength = dev->num_trim_entries * sizeof(DEVICE_DATA_SET_RANGE);
485 
486  ranges = (DEVICE_DATA_SET_RANGE*)((uint8_t*)stripe->dmdsa + stripe->dmdsa->DataSetRangesOffset);
487 
488  i = 0;
489 
490  le2 = dev->trim_list.Flink;
491  while (le2 != &dev->trim_list) {
493 
494  ranges[i].StartingOffset = s->address;
495  ranges[i].LengthInBytes = s->size;
496  i++;
497 
498  le2 = le2->Flink;
499  }
500 
501  stripe->Irp = IoAllocateIrp(dev->devobj->StackSize, false);
502 
503  if (!stripe->Irp) {
504  ERR("IoAllocateIrp failed\n");
505  goto nextdev;
506  }
507 
510  IrpSp->FileObject = dev->fileobj;
511 
512  IrpSp->Parameters.DeviceIoControl.IoControlCode = IOCTL_STORAGE_MANAGE_DATA_SET_ATTRIBUTES;
513  IrpSp->Parameters.DeviceIoControl.InputBufferLength = datalen;
514  IrpSp->Parameters.DeviceIoControl.OutputBufferLength = 0;
515 
516  stripe->Irp->AssociatedIrp.SystemBuffer = stripe->dmdsa;
517  stripe->Irp->Flags |= IRP_BUFFERED_IO;
518  stripe->Irp->UserBuffer = NULL;
519  stripe->Irp->UserIosb = &stripe->iosb;
520 
521  IoSetCompletionRoutine(stripe->Irp, ioctl_completion, &context, true, true, true);
522 
523  IoCallDriver(dev->devobj, stripe->Irp);
524 
525 nextdev:
526 #endif
527  while (!IsListEmpty(&dev->trim_list)) {
529  ExFreePool(s);
530  }
531 
532  dev->num_trim_entries = 0;
533 
534 #ifndef DEBUG_TRIM_EMULATION
535  num++;
536 #endif
537  }
538 
539  le = le->Flink;
540  }
541 
542 #ifndef DEBUG_TRIM_EMULATION
544 
545  for (num = 0; num < total_num; num++) {
546  if (context.stripes[num].dmdsa)
547  ExFreePool(context.stripes[num].dmdsa);
548 
549  if (context.stripes[num].Irp)
550  IoFreeIrp(context.stripes[num].Irp);
551  }
552 
553  ExFreePool(context.stripes);
554 #endif
555  }
556 }
557 
559  ULONG maxsize = Vcb->superblock.node_size - sizeof(tree_header);
560  LIST_ENTRY* le;
561 
562  le = Vcb->trees.Flink;
563  while (le != &Vcb->trees) {
565 
566  if (t->write) {
567  if (t->header.num_items == 0 && t->parent) {
568 #ifdef DEBUG_WRITE_LOOPS
569  ERR("empty tree found, looping again\n");
570 #endif
571  return false;
572  }
573 
574  if (t->size > maxsize) {
575 #ifdef DEBUG_WRITE_LOOPS
576  ERR("overlarge tree found (%u > %u), looping again\n", t->size, maxsize);
577 #endif
578  return false;
579  }
580 
581  if (!t->has_new_address) {
582 #ifdef DEBUG_WRITE_LOOPS
583  ERR("tree found without new address, looping again\n");
584 #endif
585  return false;
586  }
587  }
588 
589  le = le->Flink;
590  }
591 
592  return true;
593 }
594 
596  ULONG level;
597  LIST_ENTRY* le;
598 
599  for (level = 0; level <= 255; level++) {
600  bool nothing_found = true;
601 
602  TRACE("level = %u\n", level);
603 
604  le = Vcb->trees.Flink;
605  while (le != &Vcb->trees) {
607 
608  if (t->write && t->header.level == level) {
609  TRACE("tree %p: root = %I64x, level = %x, parent = %p\n", t, t->header.tree_id, t->header.level, t->parent);
610 
611  nothing_found = false;
612 
613  if (t->parent) {
614  if (!t->parent->write)
615  TRACE("adding tree %p (level %x)\n", t->parent, t->header.level);
616 
617  t->parent->write = true;
618  } else if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
619  KEY searchkey;
622 #ifdef __REACTOS__
623  tree* t2;
624 #endif
625 
626  searchkey.obj_id = t->root->id;
627  searchkey.obj_type = TYPE_ROOT_ITEM;
628  searchkey.offset = 0xffffffffffffffff;
629 
630  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
631  if (!NT_SUCCESS(Status)) {
632  ERR("error - find_item returned %08x\n", Status);
633  return Status;
634  }
635 
636  if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
637  ERR("could not find ROOT_ITEM for tree %I64x\n", searchkey.obj_id);
638  return STATUS_INTERNAL_ERROR;
639  }
640 
641  if (tp.item->size < sizeof(ROOT_ITEM)) { // if not full length, delete and create new entry
643 
644  if (!ri) {
645  ERR("out of memory\n");
647  }
648 
649  RtlCopyMemory(ri, &t->root->root_item, sizeof(ROOT_ITEM));
650 
652  if (!NT_SUCCESS(Status)) {
653  ERR("delete_tree_item returned %08x\n", Status);
654  ExFreePool(ri);
655  return Status;
656  }
657 
658  Status = insert_tree_item(Vcb, Vcb->root_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, ri, sizeof(ROOT_ITEM), NULL, Irp);
659  if (!NT_SUCCESS(Status)) {
660  ERR("insert_tree_item returned %08x\n", Status);
661  ExFreePool(ri);
662  return Status;
663  }
664  }
665 
666 #ifndef __REACTOS__
667  tree* t2 = tp.tree;
668 #else
669  t2 = tp.tree;
670 #endif
671  while (t2) {
672  t2->write = true;
673 
674  t2 = t2->parent;
675  }
676  }
677  }
678 
679  le = le->Flink;
680  }
681 
682  if (nothing_found)
683  break;
684  }
685 
686  return STATUS_SUCCESS;
687 }
688 
689 static void add_parents_to_cache(tree* t) {
690  while (t->parent) {
691  t = t->parent;
692  t->write = true;
693  }
694 }
695 
699  traverse_ptr insert_tp;
700 
702  if (!eism) {
703  ERR("out of memory\n");
704  return false;
705  }
706 
707  eism->ei.refcount = 1;
708  eism->ei.generation = Vcb->superblock.generation;
710  eism->type = TYPE_TREE_BLOCK_REF;
711  eism->tbr.offset = root_id;
712 
713  Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, eism, sizeof(EXTENT_ITEM_SKINNY_METADATA), &insert_tp, Irp);
714  if (!NT_SUCCESS(Status)) {
715  ERR("insert_tree_item returned %08x\n", Status);
716  ExFreePool(eism);
717  return false;
718  }
719 
721 
722  space_list_subtract(c, false, address, Vcb->superblock.node_size, rollback);
723 
725 
726  add_parents_to_cache(insert_tp.tree);
727 
728  return true;
729 }
730 
732  LIST_ENTRY* le;
733  space* s;
734 
735  TRACE("(%p, %I64x, %p)\n", Vcb, c->offset, address);
736 
737  if (Vcb->superblock.node_size > c->chunk_item->size - c->used)
738  return false;
739 
740  if (!c->cache_loaded) {
742 
743  if (!NT_SUCCESS(Status)) {
744  ERR("load_cache_chunk returned %08x\n", Status);
745  return false;
746  }
747  }
748 
749  if (IsListEmpty(&c->space_size))
750  return false;
751 
752  if (!c->last_alloc_set) {
753  s = CONTAINING_RECORD(c->space.Blink, space, list_entry);
754 
755  c->last_alloc = s->address;
756  c->last_alloc_set = true;
757 
758  if (s->size >= Vcb->superblock.node_size) {
759  *address = s->address;
760  c->last_alloc += Vcb->superblock.node_size;
761  return true;
762  }
763  }
764 
765  le = c->space.Flink;
766  while (le != &c->space) {
768 
769  if (s->address <= c->last_alloc && s->address + s->size >= c->last_alloc + Vcb->superblock.node_size) {
770  *address = c->last_alloc;
771  c->last_alloc += Vcb->superblock.node_size;
772  return true;
773  }
774 
775  le = le->Flink;
776  }
777 
778  le = c->space_size.Flink;
779  while (le != &c->space_size) {
780  s = CONTAINING_RECORD(le, space, list_entry_size);
781 
782  if (s->size == Vcb->superblock.node_size) {
783  *address = s->address;
784  c->last_alloc = s->address + Vcb->superblock.node_size;
785  return true;
786  } else if (s->size < Vcb->superblock.node_size) {
787  if (le == c->space_size.Flink)
788  return false;
789 
790  s = CONTAINING_RECORD(le->Blink, space, list_entry_size);
791 
792  *address = s->address;
793  c->last_alloc = s->address + Vcb->superblock.node_size;
794 
795  return true;
796  }
797 
798  le = le->Flink;
799  }
800 
801  s = CONTAINING_RECORD(c->space_size.Blink, space, list_entry_size);
802 
803  if (s->size > Vcb->superblock.node_size) {
804  *address = s->address;
805  c->last_alloc = s->address + Vcb->superblock.node_size;
806  return true;
807  }
808 
809  return false;
810 }
811 
815  EXTENT_ITEM_TREE2* eit2;
816  traverse_ptr insert_tp;
817 
818  TRACE("(%p, %x, %I64x, %p, %p, %p, %p)\n", Vcb, level, root_id, c, new_address, rollback);
819 
821  return false;
822 
823  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
824  bool b = insert_tree_extent_skinny(Vcb, level, root_id, c, address, Irp, rollback);
825 
826  if (b)
827  *new_address = address;
828 
829  return b;
830  }
831 
833  if (!eit2) {
834  ERR("out of memory\n");
835  return false;
836  }
837 
838  eit2->eit.extent_item.refcount = 1;
839  eit2->eit.extent_item.generation = Vcb->superblock.generation;
841  eit2->eit.level = level;
842  eit2->type = TYPE_TREE_BLOCK_REF;
843  eit2->tbr.offset = root_id;
844 
845  Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, Vcb->superblock.node_size, eit2, sizeof(EXTENT_ITEM_TREE2), &insert_tp, Irp);
846  if (!NT_SUCCESS(Status)) {
847  ERR("insert_tree_item returned %08x\n", Status);
848  ExFreePool(eit2);
849  return false;
850  }
851 
853 
854  space_list_subtract(c, false, address, Vcb->superblock.node_size, rollback);
855 
857 
858  add_parents_to_cache(insert_tp.tree);
859 
860  *new_address = address;
861 
862  return true;
863 }
864 
867  chunk *origchunk = NULL, *c;
868  LIST_ENTRY* le;
870 
871  if (t->root->id == BTRFS_ROOT_CHUNK)
872  flags = Vcb->system_flags;
873  else
874  flags = Vcb->metadata_flags;
875 
876  if (t->has_address) {
877  origchunk = get_chunk_from_address(Vcb, t->header.address);
878 
879  if (origchunk && !origchunk->readonly && !origchunk->reloc && origchunk->chunk_item->type == flags &&
880  insert_tree_extent(Vcb, t->header.level, t->root->id, origchunk, &addr, Irp, rollback)) {
881  t->new_address = addr;
882  t->has_new_address = true;
883  return STATUS_SUCCESS;
884  }
885  }
886 
887  ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, true);
888 
889  le = Vcb->chunks.Flink;
890  while (le != &Vcb->chunks) {
892 
893  if (!c->readonly && !c->reloc) {
895 
896  if (c != origchunk && c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
897  if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
899  ExReleaseResourceLite(&Vcb->chunk_lock);
900  t->new_address = addr;
901  t->has_new_address = true;
902  return STATUS_SUCCESS;
903  }
904  }
905 
907  }
908 
909  le = le->Flink;
910  }
911 
912  // allocate new chunk if necessary
913 
914  Status = alloc_chunk(Vcb, flags, &c, false);
915 
916  if (!NT_SUCCESS(Status)) {
917  ERR("alloc_chunk returned %08x\n", Status);
918  ExReleaseResourceLite(&Vcb->chunk_lock);
919  return Status;
920  }
921 
923 
924  if ((c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
925  if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
927  ExReleaseResourceLite(&Vcb->chunk_lock);
928  t->new_address = addr;
929  t->has_new_address = true;
930  return STATUS_SUCCESS;
931  }
932  }
933 
935 
936  ExReleaseResourceLite(&Vcb->chunk_lock);
937 
938  ERR("couldn't find any metadata chunks with %x bytes free\n", Vcb->superblock.node_size);
939 
940  return STATUS_DISK_FULL;
941 }
942 
945  uint64_t rc, root;
946 
947  TRACE("(%p, %I64x, %p)\n", Vcb, address, t);
948 
949  rc = get_extent_refcount(Vcb, address, Vcb->superblock.node_size, Irp);
950  if (rc == 0) {
951  ERR("error - refcount for extent %I64x was 0\n", address);
952  return STATUS_INTERNAL_ERROR;
953  }
954 
955  if (!t || t->parent)
956  root = parent_root;
957  else
958  root = t->header.tree_id;
959 
960  Status = decrease_extent_refcount_tree(Vcb, address, Vcb->superblock.node_size, root, level, Irp);
961  if (!NT_SUCCESS(Status)) {
962  ERR("decrease_extent_refcount_tree returned %08x\n", Status);
963  return Status;
964  }
965 
966  if (rc == 1) {
968 
969  if (c) {
971 
972  if (!c->cache_loaded) {
974 
975  if (!NT_SUCCESS(Status)) {
976  ERR("load_cache_chunk returned %08x\n", Status);
978  return Status;
979  }
980  }
981 
982  c->used -= Vcb->superblock.node_size;
983 
984  space_list_add(c, address, Vcb->superblock.node_size, rollback);
985 
987  } else
988  ERR("could not find chunk for address %I64x\n", address);
989  }
990 
991  return STATUS_SUCCESS;
992 }
993 
995  LIST_ENTRY *le2, *list;
996  changed_extent_ref* cer;
997 
998  list = old ? &ce->old_refs : &ce->refs;
999 
1000  le2 = list->Flink;
1001  while (le2 != list) {
1003 
1004  if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == edr->root && cer->edr.objid == edr->objid && cer->edr.offset == edr->offset) {
1005  cer->edr.count += edr->count;
1006  goto end;
1007  }
1008 
1009  le2 = le2->Flink;
1010  }
1011 
1013  if (!cer) {
1014  ERR("out of memory\n");
1016  }
1017 
1018  cer->type = TYPE_EXTENT_DATA_REF;
1019  RtlCopyMemory(&cer->edr, edr, sizeof(EXTENT_DATA_REF));
1020  InsertTailList(list, &cer->list_entry);
1021 
1022 end:
1023  if (old)
1024  ce->old_count += edr->count;
1025  else
1026  ce->count += edr->count;
1027 
1028  return STATUS_SUCCESS;
1029 }
1030 
1032  LIST_ENTRY *le2, *list;
1033  changed_extent_ref* cer;
1034 
1035  list = old ? &ce->old_refs : &ce->refs;
1036 
1037  le2 = list->Flink;
1038  while (le2 != list) {
1040 
1041  if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr->offset) {
1042  cer->sdr.count += sdr->count;
1043  goto end;
1044  }
1045 
1046  le2 = le2->Flink;
1047  }
1048 
1050  if (!cer) {
1051  ERR("out of memory\n");
1053  }
1054 
1055  cer->type = TYPE_SHARED_DATA_REF;
1056  RtlCopyMemory(&cer->sdr, sdr, sizeof(SHARED_DATA_REF));
1057  InsertTailList(list, &cer->list_entry);
1058 
1059 end:
1060  if (old)
1061  ce->old_count += sdr->count;
1062  else
1063  ce->count += sdr->count;
1064 
1065  return STATUS_SUCCESS;
1066 }
1067 
1069  KEY searchkey;
1070  traverse_ptr tp;
1071  NTSTATUS Status;
1072 
1073  if (!t->updated_extents && t->has_address) {
1075  if (!NT_SUCCESS(Status)) {
1076  ERR("update_tree_extents returned %08x\n", Status);
1077  return false;
1078  }
1079  }
1080 
1081  searchkey.obj_id = t->header.address;
1082  searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
1083  searchkey.offset = 0xffffffffffffffff;
1084 
1085  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1086  if (!NT_SUCCESS(Status)) {
1087  ERR("error - find_item returned %08x\n", Status);
1088  return false;
1089  }
1090 
1091  if (tp.item->key.obj_id == t->header.address && (tp.item->key.obj_type == TYPE_METADATA_ITEM || tp.item->key.obj_type == TYPE_EXTENT_ITEM))
1092  return false;
1093  else
1094  return true;
1095 }
1096 
1098  NTSTATUS Status;
1099  uint64_t rc = get_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, Irp);
1100  uint64_t flags = get_extent_flags(Vcb, t->header.address, Irp);
1101 
1102  if (rc == 0) {
1103  ERR("refcount for extent %I64x was 0\n", t->header.address);
1104  return STATUS_INTERNAL_ERROR;
1105  }
1106 
1107  if (flags & EXTENT_ITEM_SHARED_BACKREFS || t->header.flags & HEADER_FLAG_SHARED_BACKREF || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
1108  TREE_BLOCK_REF tbr;
1109  bool unique = rc > 1 ? false : (t->parent ? shared_tree_is_unique(Vcb, t->parent, Irp, rollback) : false);
1110 
1111  if (t->header.level == 0) {
1112  LIST_ENTRY* le;
1113 
1114  le = t->itemlist.Flink;
1115  while (le != &t->itemlist) {
1117 
1118  if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
1119  EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
1120 
1123 
1124  if (ed2->size > 0) {
1125  EXTENT_DATA_REF edr;
1126  changed_extent* ce = NULL;
1128 
1129  if (c) {
1130  LIST_ENTRY* le2;
1131 
1132  le2 = c->changed_extents.Flink;
1133  while (le2 != &c->changed_extents) {
1135 
1136  if (ce2->address == ed2->address) {
1137  ce = ce2;
1138  break;
1139  }
1140 
1141  le2 = le2->Flink;
1142  }
1143  }
1144 
1145  edr.root = t->root->id;
1146  edr.objid = td->key.obj_id;
1147  edr.offset = td->key.offset - ed2->offset;
1148  edr.count = 1;
1149 
1150  if (ce) {
1151  Status = add_changed_extent_ref_edr(ce, &edr, true);
1152  if (!NT_SUCCESS(Status)) {
1153  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1154  return Status;
1155  }
1156 
1157  Status = add_changed_extent_ref_edr(ce, &edr, false);
1158  if (!NT_SUCCESS(Status)) {
1159  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1160  return Status;
1161  }
1162  }
1163 
1165  if (!NT_SUCCESS(Status)) {
1166  ERR("increase_extent_refcount returned %08x\n", Status);
1167  return Status;
1168  }
1169 
1170  if ((flags & EXTENT_ITEM_SHARED_BACKREFS && unique) || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
1171  uint64_t sdrrc = find_extent_shared_data_refcount(Vcb, ed2->address, t->header.address, Irp);
1172 
1173  if (sdrrc > 0) {
1174  SHARED_DATA_REF sdr;
1175 
1176  sdr.offset = t->header.address;
1177  sdr.count = 1;
1178 
1180  t->header.address, ce ? ce->superseded : false, Irp);
1181  if (!NT_SUCCESS(Status)) {
1182  ERR("decrease_extent_refcount returned %08x\n", Status);
1183  return Status;
1184  }
1185 
1186  if (ce) {
1187  LIST_ENTRY* le2;
1188 
1189  le2 = ce->refs.Flink;
1190  while (le2 != &ce->refs) {
1192 
1193  if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr.offset) {
1194  ce->count--;
1195  cer->sdr.count--;
1196  break;
1197  }
1198 
1199  le2 = le2->Flink;
1200  }
1201 
1202  le2 = ce->old_refs.Flink;
1203  while (le2 != &ce->old_refs) {
1205 
1206  if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr.offset) {
1207  ce->old_count--;
1208 
1209  if (cer->sdr.count > 1)
1210  cer->sdr.count--;
1211  else {
1212  RemoveEntryList(&cer->list_entry);
1213  ExFreePool(cer);
1214  }
1215 
1216  break;
1217  }
1218 
1219  le2 = le2->Flink;
1220  }
1221  }
1222  }
1223  }
1224 
1225  // FIXME - clear shared flag if unique?
1226  }
1227  }
1228  }
1229 
1230  le = le->Flink;
1231  }
1232  } else {
1233  LIST_ENTRY* le;
1234 
1235  le = t->itemlist.Flink;
1236  while (le != &t->itemlist) {
1238 
1239  if (!td->inserted) {
1240  tbr.offset = t->root->id;
1241 
1243  &tbr, &td->key, t->header.level - 1, Irp);
1244  if (!NT_SUCCESS(Status)) {
1245  ERR("increase_extent_refcount returned %08x\n", Status);
1246  return Status;
1247  }
1248 
1249  if (unique || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
1250  uint64_t sbrrc = find_extent_shared_tree_refcount(Vcb, td->treeholder.address, t->header.address, Irp);
1251 
1252  if (sbrrc > 0) {
1253  SHARED_BLOCK_REF sbr;
1254 
1255  sbr.offset = t->header.address;
1256 
1257  Status = decrease_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
1258  t->header.address, false, Irp);
1259  if (!NT_SUCCESS(Status)) {
1260  ERR("decrease_extent_refcount returned %08x\n", Status);
1261  return Status;
1262  }
1263  }
1264  }
1265 
1266  // FIXME - clear shared flag if unique?
1267  }
1268 
1269  le = le->Flink;
1270  }
1271  }
1272 
1273  if (unique) {
1274  uint64_t sbrrc = find_extent_shared_tree_refcount(Vcb, t->header.address, t->parent->header.address, Irp);
1275 
1276  if (sbrrc == 1) {
1277  SHARED_BLOCK_REF sbr;
1278 
1279  sbr.offset = t->parent->header.address;
1280 
1281  Status = decrease_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
1282  t->parent->header.address, false, Irp);
1283  if (!NT_SUCCESS(Status)) {
1284  ERR("decrease_extent_refcount returned %08x\n", Status);
1285  return Status;
1286  }
1287  }
1288  }
1289 
1290  if (t->parent)
1291  tbr.offset = t->parent->header.tree_id;
1292  else
1293  tbr.offset = t->header.tree_id;
1294 
1295  Status = increase_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr,
1296  t->parent ? &t->paritem->key : NULL, t->header.level, Irp);
1297  if (!NT_SUCCESS(Status)) {
1298  ERR("increase_extent_refcount returned %08x\n", Status);
1299  return Status;
1300  }
1301 
1302  // FIXME - clear shared flag if unique?
1303 
1304  t->header.flags &= ~HEADER_FLAG_SHARED_BACKREF;
1305  }
1306 
1307  if (rc > 1 || t->header.tree_id == t->root->id) {
1308  Status = reduce_tree_extent(Vcb, t->header.address, t, t->parent ? t->parent->header.tree_id : t->header.tree_id, t->header.level, Irp, rollback);
1309 
1310  if (!NT_SUCCESS(Status)) {
1311  ERR("reduce_tree_extent returned %08x\n", Status);
1312  return Status;
1313  }
1314  }
1315 
1316  t->has_address = false;
1317 
1318  if ((rc > 1 || t->header.tree_id != t->root->id) && !(flags & EXTENT_ITEM_SHARED_BACKREFS)) {
1319  if (t->header.tree_id == t->root->id) {
1321  update_extent_flags(Vcb, t->header.address, flags, Irp);
1322  }
1323 
1324  if (t->header.level > 0) {
1325  LIST_ENTRY* le;
1326 
1327  le = t->itemlist.Flink;
1328  while (le != &t->itemlist) {
1330 
1331  if (!td->inserted) {
1332  if (t->header.tree_id == t->root->id) {
1333  SHARED_BLOCK_REF sbr;
1334 
1335  sbr.offset = t->header.address;
1336 
1337  Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, &td->key, t->header.level - 1, Irp);
1338  } else {
1339  TREE_BLOCK_REF tbr;
1340 
1341  tbr.offset = t->root->id;
1342 
1343  Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr, &td->key, t->header.level - 1, Irp);
1344  }
1345 
1346  if (!NT_SUCCESS(Status)) {
1347  ERR("increase_extent_refcount returned %08x\n", Status);
1348  return Status;
1349  }
1350  }
1351 
1352  le = le->Flink;
1353  }
1354  } else {
1355  LIST_ENTRY* le;
1356 
1357  le = t->itemlist.Flink;
1358  while (le != &t->itemlist) {
1360 
1361  if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
1362  EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
1363 
1366 
1367  if (ed2->size > 0) {
1368  changed_extent* ce = NULL;
1370 
1371  if (c) {
1372  LIST_ENTRY* le2;
1373 
1374  le2 = c->changed_extents.Flink;
1375  while (le2 != &c->changed_extents) {
1377 
1378  if (ce2->address == ed2->address) {
1379  ce = ce2;
1380  break;
1381  }
1382 
1383  le2 = le2->Flink;
1384  }
1385  }
1386 
1387  if (t->header.tree_id == t->root->id) {
1388  SHARED_DATA_REF sdr;
1389 
1390  sdr.offset = t->header.address;
1391  sdr.count = 1;
1392 
1393  if (ce) {
1394  Status = add_changed_extent_ref_sdr(ce, &sdr, true);
1395  if (!NT_SUCCESS(Status)) {
1396  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1397  return Status;
1398  }
1399 
1400  Status = add_changed_extent_ref_sdr(ce, &sdr, false);
1401  if (!NT_SUCCESS(Status)) {
1402  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1403  return Status;
1404  }
1405  }
1406 
1408  } else {
1409  EXTENT_DATA_REF edr;
1410 
1411  edr.root = t->root->id;
1412  edr.objid = td->key.obj_id;
1413  edr.offset = td->key.offset - ed2->offset;
1414  edr.count = 1;
1415 
1416  if (ce) {
1417  Status = add_changed_extent_ref_edr(ce, &edr, true);
1418  if (!NT_SUCCESS(Status)) {
1419  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1420  return Status;
1421  }
1422 
1423  Status = add_changed_extent_ref_edr(ce, &edr, false);
1424  if (!NT_SUCCESS(Status)) {
1425  ERR("add_changed_extent_ref_edr returned %08x\n", Status);
1426  return Status;
1427  }
1428  }
1429 
1431  }
1432 
1433  if (!NT_SUCCESS(Status)) {
1434  ERR("increase_extent_refcount returned %08x\n", Status);
1435  return Status;
1436  }
1437  }
1438  }
1439  }
1440 
1441  le = le->Flink;
1442  }
1443  }
1444  }
1445 
1446  t->updated_extents = true;
1447  t->header.tree_id = t->root->id;
1448 
1449  return STATUS_SUCCESS;
1450 }
1451 
1453  LIST_ENTRY* le;
1454  NTSTATUS Status;
1455  bool changed = false;
1456  uint8_t max_level = 0, level;
1457 
1458  TRACE("(%p)\n", Vcb);
1459 
1460  le = Vcb->trees.Flink;
1461  while (le != &Vcb->trees) {
1463 
1464  if (t->write && !t->has_new_address) {
1465  chunk* c;
1466 
1467  if (t->has_address) {
1468  c = get_chunk_from_address(Vcb, t->header.address);
1469 
1470  if (c) {
1471  if (!c->cache_loaded) {
1473 
1474  if (!c->cache_loaded) {
1476 
1477  if (!NT_SUCCESS(Status)) {
1478  ERR("load_cache_chunk returned %08x\n", Status);
1480  return Status;
1481  }
1482  }
1483 
1485  }
1486  }
1487  }
1488 
1490  if (!NT_SUCCESS(Status)) {
1491  ERR("get_tree_new_address returned %08x\n", Status);
1492  return Status;
1493  }
1494 
1495  TRACE("allocated extent %I64x\n", t->new_address);
1496 
1497  c = get_chunk_from_address(Vcb, t->new_address);
1498 
1499  if (c)
1500  c->used += Vcb->superblock.node_size;
1501  else {
1502  ERR("could not find chunk for address %I64x\n", t->new_address);
1503  return STATUS_INTERNAL_ERROR;
1504  }
1505 
1506  changed = true;
1507 
1508  if (t->header.level > max_level)
1509  max_level = t->header.level;
1510  }
1511 
1512  le = le->Flink;
1513  }
1514 
1515  if (!changed)
1516  return STATUS_SUCCESS;
1517 
1518  level = max_level;
1519  do {
1520  le = Vcb->trees.Flink;
1521  while (le != &Vcb->trees) {
1523 
1524  if (t->write && !t->updated_extents && t->has_address && t->header.level == level) {
1526  if (!NT_SUCCESS(Status)) {
1527  ERR("update_tree_extents returned %08x\n", Status);
1528  return Status;
1529  }
1530  }
1531 
1532  le = le->Flink;
1533  }
1534 
1535  if (level == 0)
1536  break;
1537 
1538  level--;
1539  } while (true);
1540 
1541  return STATUS_SUCCESS;
1542 }
1543 
1545  LIST_ENTRY* le;
1546  NTSTATUS Status;
1547 
1548  TRACE("(%p)\n", Vcb);
1549 
1550  le = Vcb->trees.Flink;
1551  while (le != &Vcb->trees) {
1553 
1554  if (t->write && !t->parent) {
1555  if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
1556  KEY searchkey;
1557  traverse_ptr tp;
1558 
1559  searchkey.obj_id = t->root->id;
1560  searchkey.obj_type = TYPE_ROOT_ITEM;
1561  searchkey.offset = 0xffffffffffffffff;
1562 
1563  Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1564  if (!NT_SUCCESS(Status)) {
1565  ERR("error - find_item returned %08x\n", Status);
1566  return Status;
1567  }
1568 
1569  if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1570  ERR("could not find ROOT_ITEM for tree %I64x\n", searchkey.obj_id);
1571  return STATUS_INTERNAL_ERROR;
1572  }
1573 
1574  TRACE("updating the address for root %I64x to %I64x\n", searchkey.obj_id, t->new_address);
1575 
1576  t->root->root_item.block_number = t->new_address;
1577  t->root->root_item.root_level = t->header.level;
1578  t->root->root_item.generation = Vcb->superblock.generation;
1579  t->root->root_item.generation2 = Vcb->superblock.generation;
1580 
1581  // item is guaranteed to be at least sizeof(ROOT_ITEM), due to add_parents
1582 
1583  RtlCopyMemory(tp.item->data, &t->root->root_item, sizeof(ROOT_ITEM));
1584  }
1585 
1586  t->root->treeholder.address = t->new_address;
1587  t->root->treeholder.generation = Vcb->superblock.generation;
1588  }
1589 
1590  le = le->Flink;
1591  }
1592 
1593  if (!no_cache && !(Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE)) {
1594  ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
1596  ExReleaseResourceLite(&Vcb->chunk_lock);
1597 
1598  if (!NT_SUCCESS(Status)) {
1599  ERR("update_chunk_caches returned %08x\n", Status);
1600  return Status;
1601  }
1602  }
1603 
1604  return STATUS_SUCCESS;
1605 }
1606 
1607 NTSTATUS do_tree_writes(device_extension* Vcb, LIST_ENTRY* tree_writes, bool no_free) {
1608  chunk* c;
1609  LIST_ENTRY* le;
1610  tree_write* tw;
1611  NTSTATUS Status;
1612  ULONG i, num_bits;
1613  write_data_context* wtc;
1614  ULONG bit_num = 0;
1615  bool raid56 = false;
1616 
1617  // merge together runs
1618  c = NULL;
1619  le = tree_writes->Flink;
1620  while (le != tree_writes) {
1622 
1623  if (!c || tw->address < c->offset || tw->address >= c->offset + c->chunk_item->size)
1625  else {
1627 
1628  if (tw->address == tw2->address + tw2->length) {
1630 
1631  if (!data) {
1632  ERR("out of memory\n");
1634  }
1635 
1636  RtlCopyMemory(data, tw2->data, tw2->length);
1637  RtlCopyMemory(&data[tw2->length], tw->data, tw->length);
1638 
1639  if (!no_free || tw2->allocated)
1640  ExFreePool(tw2->data);
1641 
1642  tw2->data = data;
1643  tw2->length += tw->length;
1644  tw2->allocated = true;
1645 
1646  if (!no_free || tw->allocated)
1647  ExFreePool(tw->data);
1648 
1650  ExFreePool(tw);
1651 
1652  le = tw2->list_entry.Flink;
1653  continue;
1654  }
1655  }
1656 
1657  tw->c = c;
1658 
1659  if (c->chunk_item->type & (BLOCK_FLAG_RAID5 | BLOCK_FLAG_RAID6))
1660  raid56 = true;
1661 
1662  le = le->Flink;
1663  }
1664 
1665  num_bits = 0;
1666 
1667  le = tree_writes->Flink;
1668  while (le != tree_writes) {
1670 
1671  num_bits++;
1672 
1673  le = le->Flink;
1674  }
1675 
1676  wtc = ExAllocatePoolWithTag(NonPagedPool, sizeof(write_data_context) * num_bits, ALLOC_TAG);
1677  if (!wtc) {
1678  ERR("out of memory\n");
1680  }
1681 
1682  le = tree_writes->Flink;
1683 
1684  while (le != tree_writes) {
1686 
1687  TRACE("address: %I64x, size: %x\n", tw->address, tw->length);
1688 
1689  KeInitializeEvent(&wtc[bit_num].Event, NotificationEvent, false);
1690  InitializeListHead(&wtc[bit_num].stripes);
1691  wtc[bit_num].need_wait = false;
1692  wtc[bit_num].stripes_left = 0;
1693  wtc[bit_num].parity1 = wtc[bit_num].parity2 = wtc[bit_num].scratch = NULL;
1694  wtc[bit_num].mdl = wtc[bit_num].parity1_mdl = wtc[bit_num].parity2_mdl = NULL;
1695 
1696  Status = write_data(Vcb, tw->address, tw->data, tw->length, &wtc[bit_num], NULL, NULL, false, 0, HighPagePriority);
1697  if (!NT_SUCCESS(Status)) {
1698  ERR("write_data returned %08x\n", Status);
1699 
1700  for (i = 0; i < num_bits; i++) {
1701  free_write_data_stripes(&wtc[i]);
1702  }
1703  ExFreePool(wtc);
1704 
1705  return Status;
1706  }
1707 
1708  bit_num++;
1709 
1710  le = le->Flink;
1711  }
1712 
1713  for (i = 0; i < num_bits; i++) {
1714  if (wtc[i].stripes.Flink != &wtc[i].stripes) {
1715  // launch writes and wait
1716  le = wtc[i].stripes.Flink;
1717  while (le != &wtc[i].stripes) {
1719 
1720  if (stripe->status != WriteDataStatus_Ignore) {
1721  wtc[i].need_wait = true;
1723  }
1724 
1725  le = le->Flink;
1726  }
1727  }
1728  }
1729 
1730  for (i = 0; i < num_bits; i++) {
1731  if (wtc[i].need_wait)
1733  }
1734 
1735  for (i = 0; i < num_bits; i++) {
1736  le = wtc[i].stripes.Flink;
1737  while (le != &wtc[i].stripes) {
1739 
1740  if (stripe->status != WriteDataStatus_Ignore && !NT_SUCCESS(stripe->iosb.Status)) {
1741  Status = stripe->iosb.Status;
1743  break;
1744  }
1745 
1746  le = le->Flink;
1747  }
1748 
1749  free_write_data_stripes(&wtc[i]);
1750  }
1751 
1752  ExFreePool(wtc);
1753 
1754  if (raid56) {
1755  c = NULL;
1756 
1757  le = tree_writes->Flink;
1758  while (le != tree_writes) {
1760 
1761  if (tw->c != c) {
1762  c = tw->c;
1763 
1764  ExAcquireResourceExclusiveLite(&c->partial_stripes_lock, true);
1765 
1766  while (!IsListEmpty(&c->partial_stripes)) {
1768 
1769  Status = flush_partial_stripe(Vcb, c, ps);
1770 
1771  if (ps->bmparr)
1772  ExFreePool(ps->bmparr);
1773 
1774  ExFreePool(ps);
1775 
1776  if (!NT_SUCCESS(Status)) {
1777  ERR("flush_partial_stripe returned %08x\n", Status);
1778  ExReleaseResourceLite(&c->partial_stripes_lock);
1779  return Status;
1780  }
1781  }
1782 
1783  ExReleaseResourceLite(&c->partial_stripes_lock);
1784  }
1785 
1786  le = le->Flink;
1787  }
1788  }
1789 
1790  return STATUS_SUCCESS;
1791 }
1792 
1794  ULONG level;
1795  uint8_t *data, *body;
1796  uint32_t crc32;
1797  NTSTATUS Status;
1798  LIST_ENTRY* le;
1799  LIST_ENTRY tree_writes;
1800  tree_write* tw;
1801 
1802  TRACE("(%p)\n", Vcb);
1803 
1804  InitializeListHead(&tree_writes);
1805 
1806  for (level = 0; level <= 255; level++) {
1807  bool nothing_found = true;
1808 
1809  TRACE("level = %u\n", level);
1810 
1811  le = Vcb->trees.Flink;
1812  while (le != &Vcb->trees) {
1814 
1815  if (t->write && t->header.level == level) {
1816  KEY firstitem, searchkey;
1817  LIST_ENTRY* le2;
1818  traverse_ptr tp;
1819 
1820  if (!t->has_new_address) {
1821  ERR("error - tried to write tree with no new address\n");
1822  return STATUS_INTERNAL_ERROR;
1823  }
1824 
1825  le2 = t->itemlist.Flink;
1826  while (le2 != &t->itemlist) {
1828  if (!td->ignore) {
1829  firstitem = td->key;
1830  break;
1831  }
1832  le2 = le2->Flink;
1833  }
1834 
1835  if (t->parent) {
1836  t->paritem->key = firstitem;
1837  t->paritem->treeholder.address = t->new_address;
1838  t->paritem->treeholder.generation = Vcb->superblock.generation;
1839  }
1840 
1841  if (!(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
1842  EXTENT_ITEM_TREE* eit;
1843 
1844  searchkey.obj_id = t->new_address;
1845  searchkey.obj_type = TYPE_EXTENT_ITEM;
1846  searchkey.offset = Vcb->superblock.node_size;
1847 
1848  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
1849  if (!NT_SUCCESS(Status)) {
1850  ERR("error - find_item returned %08x\n", Status);
1851  return Status;
1852  }
1853 
1854  if (keycmp(searchkey, tp.item->key)) {
1855  ERR("could not find %I64x,%x,%I64x in extent_root (found %I64x,%x,%I64x instead)\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
1856  return STATUS_INTERNAL_ERROR;
1857  }
1858 
1859  if (tp.item->size < sizeof(EXTENT_ITEM_TREE)) {
1860  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_TREE));
1861  return STATUS_INTERNAL_ERROR;
1862  }
1863 
1864  eit = (EXTENT_ITEM_TREE*)tp.item->data;
1865  eit->firstitem = firstitem;
1866  }
1867 
1868  nothing_found = false;
1869  }
1870 
1871  le = le->Flink;
1872  }
1873 
1874  if (nothing_found)
1875  break;
1876  }
1877 
1878  TRACE("allocated tree extents\n");
1879 
1880  le = Vcb->trees.Flink;
1881  while (le != &Vcb->trees) {
1883  LIST_ENTRY* le2;
1884 #ifdef DEBUG_PARANOID
1885  uint32_t num_items = 0, size = 0;
1886  bool crash = false;
1887 #endif
1888 
1889  if (t->write) {
1890 #ifdef DEBUG_PARANOID
1891  bool first = true;
1892  KEY lastkey;
1893 
1894  le2 = t->itemlist.Flink;
1895  while (le2 != &t->itemlist) {
1897  if (!td->ignore) {
1898  num_items++;
1899 
1900  if (!first) {
1901  if (keycmp(td->key, lastkey) == 0) {
1902  ERR("(%I64x,%x,%I64x): duplicate key\n", td->key.obj_id, td->key.obj_type, td->key.offset);
1903  crash = true;
1904  } else if (keycmp(td->key, lastkey) == -1) {
1905  ERR("(%I64x,%x,%I64x): key out of order\n", td->key.obj_id, td->key.obj_type, td->key.offset);
1906  crash = true;
1907  }
1908  } else
1909  first = false;
1910 
1911  lastkey = td->key;
1912 
1913  if (t->header.level == 0)
1914  size += td->size;
1915  }
1916  le2 = le2->Flink;
1917  }
1918 
1919  if (t->header.level == 0)
1920  size += num_items * sizeof(leaf_node);
1921  else
1922  size += num_items * sizeof(internal_node);
1923 
1924  if (num_items != t->header.num_items) {
1925  ERR("tree %I64x, level %x: num_items was %x, expected %x\n", t->root->id, t->header.level, num_items, t->header.num_items);
1926  crash = true;
1927  }
1928 
1929  if (size != t->size) {
1930  ERR("tree %I64x, level %x: size was %x, expected %x\n", t->root->id, t->header.level, size, t->size);
1931  crash = true;
1932  }
1933 
1934  if (t->header.num_items == 0 && t->parent) {
1935  ERR("tree %I64x, level %x: tried to write empty tree with parent\n", t->root->id, t->header.level);
1936  crash = true;
1937  }
1938 
1939  if (t->size > Vcb->superblock.node_size - sizeof(tree_header)) {
1940  ERR("tree %I64x, level %x: tried to write overlarge tree (%x > %x)\n", t->root->id, t->header.level, t->size, Vcb->superblock.node_size - sizeof(tree_header));
1941  crash = true;
1942  }
1943 
1944  if (crash) {
1945  ERR("tree %p\n", t);
1946  le2 = t->itemlist.Flink;
1947  while (le2 != &t->itemlist) {
1949  if (!td->ignore) {
1950  ERR("%I64x,%x,%I64x inserted=%u\n", td->key.obj_id, td->key.obj_type, td->key.offset, td->inserted);
1951  }
1952  le2 = le2->Flink;
1953  }
1954  int3;
1955  }
1956 #endif
1957  t->header.address = t->new_address;
1958  t->header.generation = Vcb->superblock.generation;
1959  t->header.tree_id = t->root->id;
1960  t->header.flags |= HEADER_FLAG_MIXED_BACKREF;
1961  t->header.fs_uuid = Vcb->superblock.uuid;
1962  t->has_address = true;
1963 
1964  data = ExAllocatePoolWithTag(NonPagedPool, Vcb->superblock.node_size, ALLOC_TAG);
1965  if (!data) {
1966  ERR("out of memory\n");
1968  goto end;
1969  }
1970 
1971  body = data + sizeof(tree_header);
1972 
1973  RtlCopyMemory(data, &t->header, sizeof(tree_header));
1974  RtlZeroMemory(body, Vcb->superblock.node_size - sizeof(tree_header));
1975 
1976  if (t->header.level == 0) {
1977  leaf_node* itemptr = (leaf_node*)body;
1978  int i = 0;
1979  uint8_t* dataptr = data + Vcb->superblock.node_size;
1980 
1981  le2 = t->itemlist.Flink;
1982  while (le2 != &t->itemlist) {
1984  if (!td->ignore) {
1985  dataptr = dataptr - td->size;
1986 
1987  itemptr[i].key = td->key;
1988  itemptr[i].offset = (uint32_t)((uint8_t*)dataptr - (uint8_t*)body);
1989  itemptr[i].size = td->size;
1990  i++;
1991 
1992  if (td->size > 0)
1993  RtlCopyMemory(dataptr, td->data, td->size);
1994  }
1995 
1996  le2 = le2->Flink;
1997  }
1998  } else {
1999  internal_node* itemptr = (internal_node*)body;
2000  int i = 0;
2001 
2002  le2 = t->itemlist.Flink;
2003  while (le2 != &t->itemlist) {
2005  if (!td->ignore) {
2006  itemptr[i].key = td->key;
2007  itemptr[i].address = td->treeholder.address;
2008  itemptr[i].generation = td->treeholder.generation;
2009  i++;
2010  }
2011 
2012  le2 = le2->Flink;
2013  }
2014  }
2015 
2016  crc32 = calc_crc32c(0xffffffff, (uint8_t*)&((tree_header*)data)->fs_uuid, Vcb->superblock.node_size - sizeof(((tree_header*)data)->csum));
2017  crc32 = ~crc32;
2018  *((uint32_t*)data) = crc32;
2019  TRACE("setting crc32 to %08x\n", crc32);
2020 
2022  if (!tw) {
2023  ERR("out of memory\n");
2024  ExFreePool(data);
2026  goto end;
2027  }
2028 
2029  tw->address = t->new_address;
2030  tw->length = Vcb->superblock.node_size;
2031  tw->data = data;
2032  tw->allocated = false;
2033 
2034  if (IsListEmpty(&tree_writes))
2035  InsertTailList(&tree_writes, &tw->list_entry);
2036  else {
2037  bool inserted = false;
2038 
2039  le2 = tree_writes.Flink;
2040  while (le2 != &tree_writes) {
2042 
2043  if (tw2->address > tw->address) {
2044  InsertHeadList(le2->Blink, &tw->list_entry);
2045  inserted = true;
2046  break;
2047  }
2048 
2049  le2 = le2->Flink;
2050  }
2051 
2052  if (!inserted)
2053  InsertTailList(&tree_writes, &tw->list_entry);
2054  }
2055  }
2056 
2057  le = le->Flink;
2058  }
2059 
2060  Status = do_tree_writes(Vcb, &tree_writes, false);
2061  if (!NT_SUCCESS(Status)) {
2062  ERR("do_tree_writes returned %08x\n", Status);
2063  goto end;
2064  }
2065 
2067 
2068 end:
2069  while (!IsListEmpty(&tree_writes)) {
2070  le = RemoveHeadList(&tree_writes);
2072 
2073  if (tw->data)
2074  ExFreePool(tw->data);
2075 
2076  ExFreePool(tw);
2077  }
2078 
2079  return Status;
2080 }
2081 
2083  KEY searchkey;
2084  traverse_ptr tp;
2085 
2087 
2088  sb->root_tree_addr = Vcb->superblock.root_tree_addr;
2089  sb->root_tree_generation = Vcb->superblock.generation;
2090  sb->root_level = Vcb->superblock.root_level;
2091 
2092  sb->chunk_tree_addr = Vcb->superblock.chunk_tree_addr;
2093  sb->chunk_tree_generation = Vcb->superblock.chunk_root_generation;
2094  sb->chunk_root_level = Vcb->superblock.chunk_root_level;
2095 
2096  searchkey.obj_id = BTRFS_ROOT_EXTENT;
2097  searchkey.obj_type = TYPE_ROOT_ITEM;
2098  searchkey.offset = 0xffffffffffffffff;
2099 
2100  if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
2101  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
2102  ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
2103 
2104  sb->extent_tree_addr = ri->block_number;
2105  sb->extent_tree_generation = ri->generation;
2106  sb->extent_root_level = ri->root_level;
2107  }
2108  }
2109 
2110  searchkey.obj_id = BTRFS_ROOT_FSTREE;
2111 
2112  if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
2113  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
2114  ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
2115 
2116  sb->fs_tree_addr = ri->block_number;
2117  sb->fs_tree_generation = ri->generation;
2118  sb->fs_root_level = ri->root_level;
2119  }
2120  }
2121 
2122  searchkey.obj_id = BTRFS_ROOT_DEVTREE;
2123 
2124  if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
2125  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
2126  ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
2127 
2128  sb->dev_root_addr = ri->block_number;
2129  sb->dev_root_generation = ri->generation;
2130  sb->dev_root_level = ri->root_level;
2131  }
2132  }
2133 
2134  searchkey.obj_id = BTRFS_ROOT_CHECKSUM;
2135 
2136  if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp))) {
2137  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
2138  ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
2139 
2140  sb->csum_root_addr = ri->block_number;
2141  sb->csum_root_generation = ri->generation;
2142  sb->csum_root_level = ri->root_level;
2143  }
2144  }
2145 
2146  sb->total_bytes = Vcb->superblock.total_bytes;
2147  sb->bytes_used = Vcb->superblock.bytes_used;
2148  sb->num_devices = Vcb->superblock.num_devices;
2149 }
2150 
2151 typedef struct {
2152  void* context;
2160 
2166 
2167 _Function_class_(IO_COMPLETION_ROUTINE)
2168 static NTSTATUS __stdcall write_superblock_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
2169  write_superblocks_stripe* stripe = conptr;
2171 
2173 
2174  stripe->Status = Irp->IoStatus.Status;
2175 
2176  if (InterlockedDecrement(&context->left) == 0)
2177  KeSetEvent(&context->Event, 0, false);
2178 
2180 }
2181 
2183  unsigned int i = 0;
2184 
2185  // All the documentation says that the Linux driver only writes one superblock
2186  // if it thinks a disk is an SSD, but this doesn't seem to be the case!
2187 
2188  while (superblock_addrs[i] > 0 && device->devitem.num_bytes >= superblock_addrs[i] + sizeof(superblock)) {
2189  ULONG sblen = (ULONG)sector_align(sizeof(superblock), Vcb->superblock.sector_size);
2190  superblock* sb;
2191  uint32_t crc32;
2194 
2196  if (!sb) {
2197  ERR("out of memory\n");
2199  }
2200 
2201  RtlCopyMemory(sb, &Vcb->superblock, sizeof(superblock));
2202 
2203  if (sblen > sizeof(superblock))
2204  RtlZeroMemory((uint8_t*)sb + sizeof(superblock), sblen - sizeof(superblock));
2205 
2208 
2209  crc32 = ~calc_crc32c(0xffffffff, (uint8_t*)&sb->uuid, (ULONG)sizeof(superblock) - sizeof(sb->checksum));
2210  RtlCopyMemory(&sb->checksum, &crc32, sizeof(uint32_t));
2211 
2213  if (!stripe) {
2214  ERR("out of memory\n");
2215  ExFreePool(sb);
2217  }
2218 
2219  stripe->buf = (uint8_t*)sb;
2220 
2221  stripe->Irp = IoAllocateIrp(device->devobj->StackSize, false);
2222  if (!stripe->Irp) {
2223  ERR("IoAllocateIrp failed\n");
2224  ExFreePool(stripe);
2225  ExFreePool(sb);
2227  }
2228 
2232 
2233  if (i == 0)
2235 
2236  if (device->devobj->Flags & DO_BUFFERED_IO) {
2237  stripe->Irp->AssociatedIrp.SystemBuffer = sb;
2238  stripe->mdl = NULL;
2239 
2240  stripe->Irp->Flags = IRP_BUFFERED_IO;
2241  } else if (device->devobj->Flags & DO_DIRECT_IO) {
2242  stripe->mdl = IoAllocateMdl(sb, sblen, false, false, NULL);
2243  if (!stripe->mdl) {
2244  ERR("IoAllocateMdl failed\n");
2245  IoFreeIrp(stripe->Irp);
2246  ExFreePool(stripe);
2247  ExFreePool(sb);
2249  }
2250 
2251  stripe->Irp->MdlAddress = stripe->mdl;
2252 
2254  } else {
2255  stripe->Irp->UserBuffer = sb;
2256  stripe->mdl = NULL;
2257  }
2258 
2259  IrpSp->Parameters.Write.Length = sblen;
2260  IrpSp->Parameters.Write.ByteOffset.QuadPart = superblock_addrs[i];
2261 
2262  IoSetCompletionRoutine(stripe->Irp, write_superblock_completion, stripe, true, true, true);
2263 
2264  stripe->context = context;
2265  stripe->device = device;
2266  InsertTailList(&context->stripes, &stripe->list_entry);
2267 
2268  context->left++;
2269 
2270  i++;
2271  }
2272 
2273  if (i == 0)
2274  ERR("no superblocks written!\n");
2275 
2276  return STATUS_SUCCESS;
2277 }
2278 
2280  uint64_t i;
2281  NTSTATUS Status;
2282  LIST_ENTRY* le;
2284 
2285  TRACE("(%p)\n", Vcb);
2286 
2287  le = Vcb->trees.Flink;
2288  while (le != &Vcb->trees) {
2290 
2291  if (t->write && !t->parent) {
2292  if (t->root == Vcb->root_root) {
2293  Vcb->superblock.root_tree_addr = t->new_address;
2294  Vcb->superblock.root_level = t->header.level;
2295  } else if (t->root == Vcb->chunk_root) {
2296  Vcb->superblock.chunk_tree_addr = t->new_address;
2297  Vcb->superblock.chunk_root_generation = t->header.generation;
2298  Vcb->superblock.chunk_root_level = t->header.level;
2299  }
2300  }
2301 
2302  le = le->Flink;
2303  }
2304 
2305  for (i = 0; i < BTRFS_NUM_BACKUP_ROOTS - 1; i++) {
2306  RtlCopyMemory(&Vcb->superblock.backup[i], &Vcb->superblock.backup[i+1], sizeof(superblock_backup));
2307  }
2308 
2309  update_backup_superblock(Vcb, &Vcb->superblock.backup[BTRFS_NUM_BACKUP_ROOTS - 1], Irp);
2310 
2312  InitializeListHead(&context.stripes);
2313  context.left = 0;
2314 
2315  le = Vcb->devices.Flink;
2316  while (le != &Vcb->devices) {
2318 
2319  if (dev->devobj && !dev->readonly) {
2321  if (!NT_SUCCESS(Status)) {
2322  ERR("write_superblock returned %08x\n", Status);
2323  goto end;
2324  }
2325  }
2326 
2327  le = le->Flink;
2328  }
2329 
2330  if (IsListEmpty(&context.stripes)) {
2331  ERR("error - not writing any superblocks\n");
2333  goto end;
2334  }
2335 
2336  le = context.stripes.Flink;
2337  while (le != &context.stripes) {
2339 
2341 
2342  le = le->Flink;
2343  }
2344 
2346 
2347  le = context.stripes.Flink;
2348  while (le != &context.stripes) {
2350 
2351  if (!NT_SUCCESS(stripe->Status)) {
2352  ERR("device %I64x returned %08x\n", stripe->device->devitem.dev_id, stripe->Status);
2354  Status = stripe->Status;
2355  goto end;
2356  }
2357 
2358  le = le->Flink;
2359  }
2360 
2362 
2363 end:
2364  while (!IsListEmpty(&context.stripes)) {
2366 
2367  if (stripe->mdl) {
2368  if (stripe->mdl->MdlFlags & MDL_PAGES_LOCKED)
2369  MmUnlockPages(stripe->mdl);
2370 
2371  IoFreeMdl(stripe->mdl);
2372  }
2373 
2374  if (stripe->Irp)
2375  IoFreeIrp(stripe->Irp);
2376 
2377  if (stripe->buf)
2378  ExFreePool(stripe->buf);
2379 
2380  ExFreePool(stripe);
2381  }
2382 
2383  return Status;
2384 }
2385 
2387  LIST_ENTRY *le, *le2;
2388  NTSTATUS Status;
2389  uint64_t old_size;
2390 
2391  if (ce->count == 0 && ce->old_count == 0) {
2392  while (!IsListEmpty(&ce->refs)) {
2394  ExFreePool(cer);
2395  }
2396 
2397  while (!IsListEmpty(&ce->old_refs)) {
2399  ExFreePool(cer);
2400  }
2401 
2402  goto end;
2403  }
2404 
2405  le = ce->refs.Flink;
2406  while (le != &ce->refs) {
2408  uint32_t old_count = 0;
2409 
2410  if (cer->type == TYPE_EXTENT_DATA_REF) {
2411  le2 = ce->old_refs.Flink;
2412  while (le2 != &ce->old_refs) {
2414 
2415  if (cer2->type == TYPE_EXTENT_DATA_REF && cer2->edr.root == cer->edr.root && cer2->edr.objid == cer->edr.objid && cer2->edr.offset == cer->edr.offset) {
2416  old_count = cer2->edr.count;
2417  break;
2418  }
2419 
2420  le2 = le2->Flink;
2421  }
2422 
2423  old_size = ce->old_count > 0 ? ce->old_size : ce->size;
2424 
2425  if (cer->edr.count > old_count) {
2426  Status = increase_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset, cer->edr.count - old_count, Irp);
2427 
2428  if (!NT_SUCCESS(Status)) {
2429  ERR("increase_extent_refcount_data returned %08x\n", Status);
2430  return Status;
2431  }
2432  }
2433  } else if (cer->type == TYPE_SHARED_DATA_REF) {
2434  le2 = ce->old_refs.Flink;
2435  while (le2 != &ce->old_refs) {
2437 
2438  if (cer2->type == TYPE_SHARED_DATA_REF && cer2->sdr.offset == cer->sdr.offset) {
2439  RemoveEntryList(&cer2->list_entry);
2440  ExFreePool(cer2);
2441  break;
2442  }
2443 
2444  le2 = le2->Flink;
2445  }
2446  }
2447 
2448  le = le->Flink;
2449  }
2450 
2451  le = ce->refs.Flink;
2452  while (le != &ce->refs) {
2454  LIST_ENTRY* le3 = le->Flink;
2455  uint32_t old_count = 0;
2456 
2457  if (cer->type == TYPE_EXTENT_DATA_REF) {
2458  le2 = ce->old_refs.Flink;
2459  while (le2 != &ce->old_refs) {
2461 
2462  if (cer2->type == TYPE_EXTENT_DATA_REF && cer2->edr.root == cer->edr.root && cer2->edr.objid == cer->edr.objid && cer2->edr.offset == cer->edr.offset) {
2463  old_count = cer2->edr.count;
2464 
2465  RemoveEntryList(&cer2->list_entry);
2466  ExFreePool(cer2);
2467  break;
2468  }
2469 
2470  le2 = le2->Flink;
2471  }
2472 
2473  old_size = ce->old_count > 0 ? ce->old_size : ce->size;
2474 
2475  if (cer->edr.count < old_count) {
2476  Status = decrease_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset,
2477  old_count - cer->edr.count, ce->superseded, Irp);
2478 
2479  if (!NT_SUCCESS(Status)) {
2480  ERR("decrease_extent_refcount_data returned %08x\n", Status);
2481  return Status;
2482  }
2483  }
2484 
2485  if (ce->size != ce->old_size && ce->old_count > 0) {
2486  KEY searchkey;
2487  traverse_ptr tp;
2488  void* data;
2489 
2490  searchkey.obj_id = ce->address;
2491  searchkey.obj_type = TYPE_EXTENT_ITEM;
2492  searchkey.offset = ce->old_size;
2493 
2494  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2495  if (!NT_SUCCESS(Status)) {
2496  ERR("error - find_item returned %08x\n", Status);
2497  return Status;
2498  }
2499 
2500  if (keycmp(searchkey, tp.item->key)) {
2501  ERR("could not find (%I64x,%x,%I64x) in extent tree\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
2502  return STATUS_INTERNAL_ERROR;
2503  }
2504 
2505  if (tp.item->size > 0) {
2507 
2508  if (!data) {
2509  ERR("out of memory\n");
2511  }
2512 
2514  } else
2515  data = NULL;
2516 
2517  Status = insert_tree_item(Vcb, Vcb->extent_root, ce->address, TYPE_EXTENT_ITEM, ce->size, data, tp.item->size, NULL, Irp);
2518  if (!NT_SUCCESS(Status)) {
2519  ERR("insert_tree_item returned %08x\n", Status);
2520  if (data) ExFreePool(data);
2521  return Status;
2522  }
2523 
2525  if (!NT_SUCCESS(Status)) {
2526  ERR("delete_tree_item returned %08x\n", Status);
2527  return Status;
2528  }
2529  }
2530  }
2531 
2532  RemoveEntryList(&cer->list_entry);
2533  ExFreePool(cer);
2534 
2535  le = le3;
2536  }
2537 
2538 #ifdef DEBUG_PARANOID
2539  if (!IsListEmpty(&ce->old_refs))
2540  WARN("old_refs not empty\n");
2541 #endif
2542 
2543 end:
2544  if (ce->count == 0 && !ce->superseded) {
2545  c->used -= ce->size;
2546  space_list_add(c, ce->address, ce->size, rollback);
2547  }
2548 
2550  ExFreePool(ce);
2551 
2552  return STATUS_SUCCESS;
2553 }
2554 
2556  KEY searchkey;
2557  traverse_ptr tp, next_tp;
2558  NTSTATUS Status;
2559  uint64_t startaddr, endaddr;
2560  ULONG len;
2561  uint32_t* checksums;
2562  RTL_BITMAP bmp;
2563  ULONG* bmparr;
2564  ULONG runlength, index;
2565 
2566  TRACE("(%p, %I64x, %x, %p, %p)\n", Vcb, address, length, csum, Irp);
2567 
2568  searchkey.obj_id = EXTENT_CSUM_ID;
2569  searchkey.obj_type = TYPE_EXTENT_CSUM;
2570  searchkey.offset = address;
2571 
2572  // FIXME - create checksum_root if it doesn't exist at all
2573 
2574  Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
2575  if (Status == STATUS_NOT_FOUND) { // tree is completely empty
2576  if (csum) { // not deleted
2577  ULONG length2 = length;
2578  uint64_t off = address;
2579  uint32_t* data = csum;
2580 
2581  do {
2582  uint16_t il = (uint16_t)min(length2, MAX_CSUM_SIZE / sizeof(uint32_t));
2583 
2584  checksums = ExAllocatePoolWithTag(PagedPool, il * sizeof(uint32_t), ALLOC_TAG);
2585  if (!checksums) {
2586  ERR("out of memory\n");
2587  return;
2588  }
2589 
2590  RtlCopyMemory(checksums, data, il * sizeof(uint32_t));
2591 
2592  Status = insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, off, checksums,
2593  il * sizeof(uint32_t), NULL, Irp);
2594  if (!NT_SUCCESS(Status)) {
2595  ERR("insert_tree_item returned %08x\n", Status);
2596  ExFreePool(checksums);
2597  return;
2598  }
2599 
2600  length2 -= il;
2601 
2602  if (length2 > 0) {
2603  off += il * Vcb->superblock.sector_size;
2604  data += il;
2605  }
2606  } while (length2 > 0);
2607  }
2608  } else if (!NT_SUCCESS(Status)) {
2609  ERR("find_item returned %08x\n", Status);
2610  return;
2611  } else {
2612  uint32_t tplen;
2613 
2614  // FIXME - check entry is TYPE_EXTENT_CSUM?
2615 
2616  if (tp.item->key.offset < address && tp.item->key.offset + (tp.item->size * Vcb->superblock.sector_size / sizeof(uint32_t)) >= address)
2617  startaddr = tp.item->key.offset;
2618  else
2619  startaddr = address;
2620 
2621  searchkey.obj_id = EXTENT_CSUM_ID;
2622  searchkey.obj_type = TYPE_EXTENT_CSUM;
2623  searchkey.offset = address + (length * Vcb->superblock.sector_size);
2624 
2625  Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
2626  if (!NT_SUCCESS(Status)) {
2627  ERR("find_item returned %08x\n", Status);
2628  return;
2629  }
2630 
2631  tplen = tp.item->size / sizeof(uint32_t);
2632 
2633  if (tp.item->key.offset + (tplen * Vcb->superblock.sector_size) >= address + (length * Vcb->superblock.sector_size))
2634  endaddr = tp.item->key.offset + (tplen * Vcb->superblock.sector_size);
2635  else
2636  endaddr = address + (length * Vcb->superblock.sector_size);
2637 
2638  TRACE("cs starts at %I64x (%x sectors)\n", address, length);
2639  TRACE("startaddr = %I64x\n", startaddr);
2640  TRACE("endaddr = %I64x\n", endaddr);
2641 
2642  len = (ULONG)((endaddr - startaddr) / Vcb->superblock.sector_size);
2643 
2644  checksums = ExAllocatePoolWithTag(PagedPool, sizeof(uint32_t) * len, ALLOC_TAG);
2645  if (!checksums) {
2646  ERR("out of memory\n");
2647  return;
2648  }
2649 
2650  bmparr = ExAllocatePoolWithTag(PagedPool, sizeof(ULONG) * ((len/8)+1), ALLOC_TAG);
2651  if (!bmparr) {
2652  ERR("out of memory\n");
2653  ExFreePool(checksums);
2654  return;
2655  }
2656 
2657  RtlInitializeBitMap(&bmp, bmparr, len);
2658  RtlSetAllBits(&bmp);
2659 
2660  searchkey.obj_id = EXTENT_CSUM_ID;
2661  searchkey.obj_type = TYPE_EXTENT_CSUM;
2662  searchkey.offset = address;
2663 
2664  Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, false, Irp);
2665  if (!NT_SUCCESS(Status)) {
2666  ERR("find_item returned %08x\n", Status);
2667  ExFreePool(checksums);
2668  ExFreePool(bmparr);
2669  return;
2670  }
2671 
2672  // set bit = free space, cleared bit = allocated sector
2673 
2674  while (tp.item->key.offset < endaddr) {
2675  if (tp.item->key.offset >= startaddr) {
2676  if (tp.item->size > 0) {
2677  ULONG itemlen = (ULONG)min((len - (tp.item->key.offset - startaddr) / Vcb->superblock.sector_size) * sizeof(uint32_t), tp.item->size);
2678 
2679  RtlCopyMemory(&checksums[(tp.item->key.offset - startaddr) / Vcb->superblock.sector_size], tp.item->data, itemlen);
2680  RtlClearBits(&bmp, (ULONG)((tp.item->key.offset - startaddr) / Vcb->superblock.sector_size), itemlen / sizeof(uint32_t));
2681  }
2682 
2684  if (!NT_SUCCESS(Status)) {
2685  ERR("delete_tree_item returned %08x\n", Status);
2686  ExFreePool(checksums);
2687  ExFreePool(bmparr);
2688  return;
2689  }
2690  }
2691 
2692  if (find_next_item(Vcb, &tp, &next_tp, false, Irp)) {
2693  tp = next_tp;
2694  } else
2695  break;
2696  }
2697 
2698  if (!csum) { // deleted
2699  RtlSetBits(&bmp, (ULONG)((address - startaddr) / Vcb->superblock.sector_size), length);
2700  } else {
2701  RtlCopyMemory(&checksums[(address - startaddr) / Vcb->superblock.sector_size], csum, length * sizeof(uint32_t));
2702  RtlClearBits(&bmp, (ULONG)((address - startaddr) / Vcb->superblock.sector_size), length);
2703  }
2704 
2705  runlength = RtlFindFirstRunClear(&bmp, &index);
2706 
2707  while (runlength != 0) {
2708  if (index >= len)
2709  break;
2710 
2711  if (index + runlength >= len) {
2712  runlength = len - index;
2713 
2714  if (runlength == 0)
2715  break;
2716  }
2717 
2718  do {
2719  uint16_t rl;
2720  uint64_t off;
2721  uint32_t* data;
2722 
2723  if (runlength * sizeof(uint32_t) > MAX_CSUM_SIZE)
2724  rl = MAX_CSUM_SIZE / sizeof(uint32_t);
2725  else
2726  rl = (uint16_t)runlength;
2727 
2729  if (!data) {
2730  ERR("out of memory\n");
2731  ExFreePool(bmparr);
2732  ExFreePool(checksums);
2733  return;
2734  }
2735 
2736  RtlCopyMemory(data, &checksums[index], sizeof(uint32_t) * rl);
2737 
2738  off = startaddr + UInt32x32To64(index, Vcb->superblock.sector_size);
2739 
2740  Status = insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, off, data, sizeof(uint32_t) * rl, NULL, Irp);
2741  if (!NT_SUCCESS(Status)) {
2742  ERR("insert_tree_item returned %08x\n", Status);
2743  ExFreePool(data);
2744  ExFreePool(bmparr);
2745  ExFreePool(checksums);
2746  return;
2747  }
2748 
2749  runlength -= rl;
2750  index += rl;
2751  } while (runlength > 0);
2752 
2753  runlength = RtlFindNextForwardRunClear(&bmp, index, &index);
2754  }
2755 
2756  ExFreePool(bmparr);
2757  ExFreePool(checksums);
2758  }
2759 }
2760 
2762  LIST_ENTRY *le = Vcb->chunks.Flink, *le2;
2763  chunk* c;
2764  KEY searchkey;
2765  traverse_ptr tp;
2766  BLOCK_GROUP_ITEM* bgi;
2767  NTSTATUS Status;
2768 
2769  TRACE("(%p)\n", Vcb);
2770 
2771  ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
2772 
2773  while (le != &Vcb->chunks) {
2775 
2777 
2778  if (!c->cache_loaded && (!IsListEmpty(&c->changed_extents) || c->used != c->oldused)) {
2780 
2781  if (!NT_SUCCESS(Status)) {
2782  ERR("load_cache_chunk returned %08x\n", Status);
2784  goto end;
2785  }
2786  }
2787 
2788  le2 = c->changed_extents.Flink;
2789  while (le2 != &c->changed_extents) {
2790  LIST_ENTRY* le3 = le2->Flink;
2792 
2794  if (!NT_SUCCESS(Status)) {
2795  ERR("flush_changed_extent returned %08x\n", Status);
2797  goto end;
2798  }
2799 
2800  le2 = le3;
2801  }
2802 
2803  // This is usually done by update_chunks, but we have to check again in case any new chunks
2804  // have been allocated since.
2805  if (c->created) {
2806  Status = create_chunk(Vcb, c, Irp);
2807  if (!NT_SUCCESS(Status)) {
2808  ERR("create_chunk returned %08x\n", Status);
2810  goto end;
2811  }
2812  }
2813 
2814  if (c->old_cache) {
2815  if (c->old_cache->dirty) {
2816  LIST_ENTRY batchlist;
2817 
2818  InitializeListHead(&batchlist);
2819 
2820  Status = flush_fcb(c->old_cache, false, &batchlist, Irp);
2821  if (!NT_SUCCESS(Status)) {
2822  ERR("flush_fcb returned %08x\n", Status);
2824  clear_batch_list(Vcb, &batchlist);
2825  goto end;
2826  }
2827 
2828  Status = commit_batch_list(Vcb, &batchlist, Irp);
2829  if (!NT_SUCCESS(Status)) {
2830  ERR("commit_batch_list returned %08x\n", Status);
2832  goto end;
2833  }
2834  }
2835 
2836  free_fcb(c->old_cache);
2837 
2838  if (c->old_cache->refcount == 0)
2839  reap_fcb(c->old_cache);
2840 
2841  c->old_cache = NULL;
2842  }
2843 
2844  if (c->used != c->oldused) {
2845 #ifdef __REACTOS__
2846  uint64_t old_phys_used, phys_used;
2847 #endif
2848  searchkey.obj_id = c->offset;
2849  searchkey.obj_type = TYPE_BLOCK_GROUP_ITEM;
2850  searchkey.offset = c->chunk_item->size;
2851 
2852  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
2853  if (!NT_SUCCESS(Status)) {
2854  ERR("error - find_item returned %08x\n", Status);
2856  goto end;
2857  }
2858 
2859  if (keycmp(searchkey, tp.item->key)) {
2860  ERR("could not find (%I64x,%x,%I64x) in extent_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
2863  goto end;
2864  }
2865 
2866  if (tp.item->size < sizeof(BLOCK_GROUP_ITEM)) {
2867  ERR("(%I64x,%x,%I64x) was %u bytes, expected %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(BLOCK_GROUP_ITEM));
2870  goto end;
2871  }
2872 
2874  if (!bgi) {
2875  ERR("out of memory\n");
2878  goto end;
2879  }
2880 
2881  RtlCopyMemory(bgi, tp.item->data, tp.item->size);
2882  bgi->used = c->used;
2883 
2884 #ifdef DEBUG_PARANOID
2885  if (bgi->used & 0x8000000000000000) {
2886  ERR("refusing to write BLOCK_GROUP_ITEM with negative usage value (%I64x)", bgi->used);
2887  int3;
2888  }
2889 #endif
2890 
2891  TRACE("adjusting usage of chunk %I64x to %I64x\n", c->offset, c->used);
2892 
2894  if (!NT_SUCCESS(Status)) {
2895  ERR("delete_tree_item returned %08x\n", Status);
2896  ExFreePool(bgi);
2898  goto end;
2899  }
2900 
2901  Status = insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, bgi, tp.item->size, NULL, Irp);
2902  if (!NT_SUCCESS(Status)) {
2903  ERR("insert_tree_item returned %08x\n", Status);
2904  ExFreePool(bgi);
2906  goto end;
2907  }
2908 
2909 #ifndef __REACTOS__
2910  uint64_t old_phys_used = chunk_estimate_phys_size(Vcb, c, c->oldused);
2911  uint64_t phys_used = chunk_estimate_phys_size(Vcb, c, c->used);
2912 #else
2913  old_phys_used = chunk_estimate_phys_size(Vcb, c, c->oldused);
2914  phys_used = chunk_estimate_phys_size(Vcb, c, c->used);
2915 #endif
2916 
2917  if (Vcb->superblock.bytes_used + phys_used > old_phys_used)
2918  Vcb->superblock.bytes_used += phys_used - old_phys_used;
2919  else
2920  Vcb->superblock.bytes_used = 0;
2921 
2922  c->oldused = c->used;
2923  }
2924 
2926 
2927  le = le->Flink;
2928  }
2929 
2931 
2932 end:
2933  ExReleaseResourceLite(&Vcb->chunk_lock);
2934 
2935  return Status;
2936 }
2937 
2938 static void get_first_item(tree* t, KEY* key) {
2939  LIST_ENTRY* le;
2940 
2941  le = t->itemlist.Flink;
2942  while (le != &t->itemlist) {
2944 
2945  *key = td->key;
2946  return;
2947  }
2948 }
2949 
2951  tree *nt, *pt;
2952  tree_data* td;
2953  tree_data* oldlastitem;
2954 
2955  TRACE("splitting tree in %I64x at (%I64x,%x,%I64x)\n", t->root->id, newfirstitem->key.obj_id, newfirstitem->key.obj_type, newfirstitem->key.offset);
2956 
2958  if (!nt) {
2959  ERR("out of memory\n");
2961  }
2962 
2963  if (t->header.level > 0) {
2965  if (!nt->nonpaged) {
2966  ERR("out of memory\n");
2967  ExFreePool(nt);
2969  }
2970 
2971  ExInitializeFastMutex(&nt->nonpaged->mutex);
2972  } else
2973  nt->nonpaged = NULL;
2974 
2975  RtlCopyMemory(&nt->header, &t->header, sizeof(tree_header));
2976  nt->header.address = 0;
2977  nt->header.generation = Vcb->superblock.generation;
2978  nt->header.num_items = t->header.num_items - numitems;
2980 
2981  nt->has_address = false;
2982  nt->Vcb = Vcb;
2983  nt->parent = t->parent;
2984 
2985 #ifdef DEBUG_PARANOID
2986  if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
2987 #endif
2988 
2989  nt->root = t->root;
2990  nt->new_address = 0;
2991  nt->has_new_address = false;
2992  nt->updated_extents = false;
2993  nt->uniqueness_determined = true;
2994  nt->is_unique = true;
2995  nt->list_entry_hash.Flink = NULL;
2996  nt->buf = NULL;
2997  InitializeListHead(&nt->itemlist);
2998 
2999  oldlastitem = CONTAINING_RECORD(newfirstitem->list_entry.Blink, tree_data, list_entry);
3000 
3001  nt->itemlist.Flink = &newfirstitem->list_entry;
3002  nt->itemlist.Blink = t->itemlist.Blink;
3003  nt->itemlist.Flink->Blink = &nt->itemlist;
3004  nt->itemlist.Blink->Flink = &nt->itemlist;
3005 
3006  t->itemlist.Blink = &oldlastitem->list_entry;
3007  t->itemlist.Blink->Flink = &t->itemlist;
3008 
3009  nt->size = t->size - size;
3010  t->size = size;
3011  t->header.num_items = numitems;
3012  nt->write = true;
3013 
3014  InsertTailList(&Vcb->trees, &nt->list_entry);
3015 
3016  if (nt->header.level > 0) {
3017  LIST_ENTRY* le = nt->itemlist.Flink;
3018 
3019  while (le != &nt->itemlist) {
3021 
3022  if (td2->treeholder.tree) {
3023  td2->treeholder.tree->parent = nt;
3024 #ifdef DEBUG_PARANOID
3025  if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
3026 #endif
3027  }
3028 
3029  le = le->Flink;
3030  }
3031  } else {
3032  LIST_ENTRY* le = nt->itemlist.Flink;
3033 
3034  while (le != &nt->itemlist) {
3036 
3037  if (!td2->inserted && td2->data) {
3039 
3040  if (!data) {
3041  ERR("out of memory\n");
3043  }
3044 
3045  RtlCopyMemory(data, td2->data, td2->size);
3046  td2->data = data;
3047  td2->inserted = true;
3048  }
3049 
3050  le = le->Flink;
3051  }
3052  }
3053 
3054  if (nt->parent) {
3055  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
3056  if (!td) {
3057  ERR("out of memory\n");
3059  }
3060 
3061  td->key = newfirstitem->key;
3062 
3063  InsertHeadList(&t->paritem->list_entry, &td->list_entry);
3064 
3065  td->ignore = false;
3066  td->inserted = true;
3067  td->treeholder.tree = nt;
3068  nt->paritem = td;
3069 
3070  nt->parent->header.num_items++;
3071  nt->parent->size += sizeof(internal_node);
3072 
3073  goto end;
3074  }
3075 
3076  TRACE("adding new tree parent\n");
3077 
3078  if (nt->header.level == 255) {
3079  ERR("cannot add parent to tree at level 255\n");
3080  return STATUS_INTERNAL_ERROR;
3081  }
3082 
3084  if (!pt) {
3085  ERR("out of memory\n");
3087  }
3088 
3090  if (!pt->nonpaged) {
3091  ERR("out of memory\n");
3092  ExFreePool(pt);
3094  }
3095 
3096  ExInitializeFastMutex(&pt->nonpaged->mutex);
3097 
3098  RtlCopyMemory(&pt->header, &nt->header, sizeof(tree_header));
3099  pt->header.address = 0;
3100  pt->header.num_items = 2;
3101  pt->header.level = nt->header.level + 1;
3103 
3104  pt->has_address = false;
3105  pt->Vcb = Vcb;
3106  pt->parent = NULL;
3107  pt->paritem = NULL;
3108  pt->root = t->root;
3109  pt->new_address = 0;
3110  pt->has_new_address = false;
3111  pt->updated_extents = false;
3112  pt->size = pt->header.num_items * sizeof(internal_node);
3113  pt->uniqueness_determined = true;
3114  pt->is_unique = true;
3115  pt->list_entry_hash.Flink = NULL;
3116  pt->buf = NULL;
3117  InitializeListHead(&pt->itemlist);
3118 
3119  InsertTailList(&Vcb->trees, &pt->list_entry);
3120 
3121  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
3122  if (!td) {
3123  ERR("out of memory\n");
3125  }
3126 
3127  get_first_item(t, &td->key);
3128  td->ignore = false;
3129  td->inserted = false;
3130  td->treeholder.address = 0;
3131  td->treeholder.generation = Vcb->superblock.generation;
3132  td->treeholder.tree = t;
3133  InsertTailList(&pt->itemlist, &td->list_entry);
3134  t->paritem = td;
3135 
3136  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
3137  if (!td) {
3138  ERR("out of memory\n");
3140  }
3141 
3142  td->key = newfirstitem->key;
3143  td->ignore = false;
3144  td->inserted = false;
3145  td->treeholder.address = 0;
3146  td->treeholder.generation = Vcb->superblock.generation;
3147  td->treeholder.tree = nt;
3148  InsertTailList(&pt->itemlist, &td->list_entry);
3149  nt->paritem = td;
3150 
3151  pt->write = true;
3152 
3153  t->root->treeholder.tree = pt;
3154 
3155  t->parent = pt;
3156  nt->parent = pt;
3157 
3158 #ifdef DEBUG_PARANOID
3159  if (t->parent && t->parent->header.level <= t->header.level) int3;
3160  if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
3161 #endif
3162 
3163 end:
3164  t->root->root_item.bytes_used += Vcb->superblock.node_size;
3165 
3166  return STATUS_SUCCESS;
3167 }
3168 
3170  LIST_ENTRY* le;
3171  uint32_t size, ds, numitems;
3172 
3173  size = 0;
3174  numitems = 0;
3175 
3176  // FIXME - na├»ve implementation: maximizes number of filled trees
3177 
3178  le = t->itemlist.Flink;
3179  while (le != &t->itemlist) {
3181 
3182  if (!td->ignore) {
3183  if (t->header.level == 0)
3184  ds = sizeof(leaf_node) + td->size;
3185  else
3186  ds = sizeof(internal_node);
3187 
3188  if (numitems == 0 && ds > Vcb->superblock.node_size - sizeof(tree_header)) {
3189  ERR("(%I64x,%x,%I64x) in tree %I64x is too large (%x > %x)\n",
3190  td->key.obj_id, td->key.obj_type, td->key.offset, t->root->id,
3191  ds, Vcb->superblock.node_size - sizeof(tree_header));
3192  return STATUS_INTERNAL_ERROR;
3193  }
3194 
3195  // FIXME - move back if previous item was deleted item with same key
3196  if (size + ds > Vcb->superblock.node_size - sizeof(tree_header))
3197  return split_tree_at(Vcb, t, td, numitems, size);
3198 
3199  size += ds;
3200  numitems++;
3201  }
3202 
3203  le = le->Flink;
3204  }
3205 
3206  return STATUS_SUCCESS;
3207 }
3208 
3210  KEY searchkey;
3211  traverse_ptr tp;
3212  NTSTATUS Status;
3213  bool ret = false;
3214  EXTENT_ITEM* ei;
3215  uint8_t* type;
3216 
3217  if (t->uniqueness_determined)
3218  return t->is_unique;
3219 
3220  if (t->parent && !is_tree_unique(Vcb, t->parent, Irp))
3221  goto end;
3222 
3223  if (t->has_address) {
3224  searchkey.obj_id = t->header.address;
3225  searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
3226  searchkey.offset = 0xffffffffffffffff;
3227 
3228  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
3229  if (!NT_SUCCESS(Status)) {
3230  ERR("error - find_item returned %08x\n", Status);
3231  goto end;
3232  }
3233 
3234  if (tp.item->key.obj_id != t->header.address || (tp.item->key.obj_type != TYPE_METADATA_ITEM && tp.item->key.obj_type != TYPE_EXTENT_ITEM))
3235  goto end;
3236 
3237  if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->size == sizeof(EXTENT_ITEM_V0))
3238  goto end;
3239 
3240  if (tp.item->size < sizeof(EXTENT_ITEM))
3241  goto end;
3242 
3243  ei = (EXTENT_ITEM*)tp.item->data;
3244 
3245  if (ei->refcount > 1)
3246  goto end;
3247 
3249  EXTENT_ITEM2* ei2;
3250 
3251  if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2))
3252  goto end;
3253 
3254  ei2 = (EXTENT_ITEM2*)&ei[1];
3255  type = (uint8_t*)&ei2[1];
3256  } else
3257  type = (uint8_t*)&ei[1];
3258 
3259  if (type >= tp.item->data + tp.item->size || *type != TYPE_TREE_BLOCK_REF)
3260  goto end;
3261  }
3262 
3263  ret = true;
3264 
3265 end:
3266  t->is_unique = ret;
3267  t->uniqueness_determined = true;
3268 
3269  return ret;
3270 }
3271 
3272 static NTSTATUS try_tree_amalgamate(device_extension* Vcb, tree* t, bool* done, bool* done_deletions, PIRP Irp, LIST_ENTRY* rollback) {
3273  LIST_ENTRY* le;
3274  tree_data* nextparitem = NULL;
3275  NTSTATUS Status;
3276  tree *next_tree, *par;
3277 
3278  *done = false;
3279 
3280  TRACE("trying to amalgamate tree in root %I64x, level %x (size %u)\n", t->root->id, t->header.level, t->size);
3281 
3282  // FIXME - doesn't capture everything, as it doesn't ascend
3283  le = t->paritem->list_entry.Flink;
3284  while (le != &t->parent->itemlist) {
3286 
3287  if (!td->ignore) {
3288  nextparitem = td;
3289  break;
3290  }
3291 
3292  le = le->Flink;
3293  }
3294 
3295  if (!nextparitem)
3296  return STATUS_SUCCESS;
3297 
3298  TRACE("nextparitem: key = %I64x,%x,%I64x\n", nextparitem->key.obj_id, nextparitem->key.obj_type, nextparitem->key.offset);
3299 
3300  if (!nextparitem->treeholder.tree) {
3301  Status = do_load_tree(Vcb, &nextparitem->treeholder, t->root, t->parent, nextparitem, NULL);
3302  if (!NT_SUCCESS(Status)) {
3303  ERR("do_load_tree returned %08x\n", Status);
3304  return Status;
3305  }
3306  }
3307 
3308  if (!is_tree_unique(Vcb, nextparitem->treeholder.tree, Irp))
3309  return STATUS_SUCCESS;
3310 
3311  next_tree = nextparitem->treeholder.tree;
3312 
3313  if (!next_tree->updated_extents && next_tree->has_address) {
3314  Status = update_tree_extents(Vcb, next_tree, Irp, rollback);
3315  if (!NT_SUCCESS(Status)) {
3316  ERR("update_tree_extents returned %08x\n", Status);
3317  return Status;
3318  }
3319  }
3320 
3321  if (t->size + next_tree->size <= Vcb->superblock.node_size - sizeof(tree_header)) {
3322  // merge two trees into one
3323 
3324  t->header.num_items += next_tree->header.num_items;
3325  t->size += next_tree->size;
3326 
3327  if (next_tree->header.level > 0) {
3328  le = next_tree->itemlist.Flink;
3329 
3330  while (le != &next_tree->itemlist) {
3332 
3333  if (td2->treeholder.tree) {
3334  td2->treeholder.tree->parent = t;
3335 #ifdef DEBUG_PARANOID
3336  if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
3337 #endif
3338  }
3339 
3340  td2->inserted = true;
3341  le = le->Flink;
3342  }
3343  } else {
3344  le = next_tree->itemlist.Flink;
3345 
3346  while (le != &next_tree->itemlist) {
3348 
3349  if (!td2->inserted && td2->data) {
3351 
3352  if (!data) {
3353  ERR("out of memory\n");
3355  }
3356 
3357  RtlCopyMemory(data, td2->data, td2->size);
3358  td2->data = data;
3359  td2->inserted = true;
3360  }
3361 
3362  le = le->Flink;
3363  }
3364  }
3365 
3366  t->itemlist.Blink->Flink = next_tree->itemlist.Flink;
3367  t->itemlist.Blink->Flink->Blink = t->itemlist.Blink;
3368  t->itemlist.Blink = next_tree->itemlist.Blink;
3369  t->itemlist.Blink->Flink = &t->itemlist;
3370 
3371  next_tree->itemlist.Flink = next_tree->itemlist.Blink = &next_tree->itemlist;
3372 
3373  next_tree->header.num_items = 0;
3374  next_tree->size = 0;
3375 
3376  if (next_tree->has_new_address) { // delete associated EXTENT_ITEM
3377  Status = reduce_tree_extent(Vcb, next_tree->new_address, next_tree, next_tree->parent->header.tree_id, next_tree->header.level, Irp, rollback);
3378 
3379  if (!NT_SUCCESS(Status)) {
3380  ERR("reduce_tree_extent returned %08x\n", Status);
3381  return Status;
3382  }
3383  } else if (next_tree->has_address) {
3384  Status = reduce_tree_extent(Vcb, next_tree->header.address, next_tree, next_tree->parent->header.tree_id, next_tree->header.level, Irp, rollback);
3385 
3386  if (!NT_SUCCESS(Status)) {
3387  ERR("reduce_tree_extent returned %08x\n", Status);
3388  return Status;
3389  }
3390  }
3391 
3392  if (!nextparitem->ignore) {
3393  nextparitem->ignore = true;
3394  next_tree->parent->header.num_items--;
3395  next_tree->parent->size -= sizeof(internal_node);
3396 
3397  *done_deletions = true;
3398  }
3399 
3400  par = next_tree->parent;
3401  while (par) {
3402  par->write = true;
3403  par = par->parent;
3404  }
3405 
3406  RemoveEntryList(&nextparitem->list_entry);
3407  ExFreePool(next_tree->paritem);
3408  next_tree->paritem = NULL;
3409 
3410  next_tree->root->root_item.bytes_used -= Vcb->superblock.node_size;
3411 
3412  free_tree(next_tree);
3413 
3414  *done = true;
3415  } else {
3416  // rebalance by moving items from second tree into first
3417  ULONG avg_size = (t->size + next_tree->size) / 2;
3418  KEY firstitem = {0, 0, 0};
3419  bool changed = false;
3420 
3421  TRACE("attempting rebalance\n");
3422 
3423  le = next_tree->itemlist.Flink;
3424  while (le != &next_tree->itemlist && t->size < avg_size && next_tree->header.num_items > 1) {
3426  ULONG size;
3427 
3428  if (!td->ignore) {
3429  if (next_tree->header.level == 0)
3430  size = sizeof(leaf_node) + td->size;
3431  else
3432  size = sizeof(internal_node);
3433  } else
3434  size = 0;
3435 
3436  if (t->size + size < Vcb->superblock.node_size - sizeof(tree_header)) {
3438  InsertTailList(&t->itemlist, &td->list_entry);
3439 
3440  if (next_tree->header.level > 0 && td->treeholder.tree) {
3441  td->treeholder.tree->parent = t;
3442 #ifdef DEBUG_PARANOID
3443  if (td->treeholder.tree->parent && td->treeholder.tree->parent->header.level <= td->treeholder.tree->header.level) int3;
3444 #endif
3445  } else if (next_tree->header.level == 0 && !td->inserted && td->size > 0) {
3447 
3448  if (!data) {
3449  ERR("out of memory\n");
3451  }
3452 
3453  RtlCopyMemory(data, td->data, td->size);
3454  td->data = data;
3455  }
3456 
3457  td->inserted = true;
3458 
3459  if (!td->ignore) {
3460  next_tree->size -= size;
3461  t->size += size;
3462  next_tree->header.num_items--;
3463  t->header.num_items++;
3464  }
3465 
3466  changed = true;
3467  } else
3468  break;
3469 
3470  le = next_tree->itemlist.Flink;
3471  }
3472 
3473  le = next_tree->itemlist.Flink;
3474  while (le != &next_tree->itemlist) {
3476 
3477  if (!td->ignore) {
3478  firstitem = td->key;
3479  break;
3480  }
3481 
3482  le = le->Flink;
3483  }
3484 
3485  // FIXME - once ascension is working, make this work with parent's parent, etc.
3486  if (next_tree->paritem)
3487  next_tree->paritem->key = firstitem;
3488 
3489  par = next_tree;
3490  while (par) {
3491  par->write = true;
3492  par = par->parent;
3493  }
3494 
3495  if (changed)
3496  *done = true;
3497  }
3498 
3499  return STATUS_SUCCESS;
3500 }
3501 
3503  KEY searchkey;
3504  traverse_ptr tp;
3505  NTSTATUS Status;
3506 
3507  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
3508  searchkey.obj_id = address;
3509  searchkey.obj_type = TYPE_METADATA_ITEM;
3510  searchkey.offset = t->header.level;
3511 
3512  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
3513  if (!NT_SUCCESS(Status)) {
3514  ERR("error - find_item returned %08x\n", Status);
3515  return Status;
3516  }
3517 
3518  if (!keycmp(tp.item->key, searchkey)) {
3520 
3521  if (tp.item->size > 0) {
3523 
3524  if (!eism) {
3525  ERR("out of memory\n");
3527  }
3528 
3529  RtlCopyMemory(eism, tp.item->data, tp.item->size);
3530  } else
3531  eism = NULL;
3532 
3534  if (!NT_SUCCESS(Status)) {
3535  ERR("delete_tree_item returned %08x\n", Status);
3536  if (eism) ExFreePool(eism);
3537  return Status;
3538  }
3539 
3540  Status = insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, eism, tp.item->size, NULL, Irp);
3541  if (!NT_SUCCESS(Status)) {
3542  ERR("insert_tree_item returned %08x\n", Status);
3543  if (eism) ExFreePool(eism);
3544  return Status;
3545  }
3546 
3547  return STATUS_SUCCESS;
3548  }
3549  }
3550 
3551  searchkey.obj_id = address;
3552  searchkey.obj_type = TYPE_EXTENT_ITEM;
3553  searchkey.offset = 0xffffffffffffffff;
3554 
3555  Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
3556  if (!NT_SUCCESS(Status)) {
3557  ERR("error - find_item returned %08x\n", Status);
3558  return Status;
3559  }
3560 
3561  if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) {
3562  EXTENT_ITEM_TREE* eit;
3563 
3564  if (tp.item->size < sizeof(EXTENT_ITEM_TREE)) {
3565  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_TREE));
3566  return STATUS_INTERNAL_ERROR;
3567  }
3568 
3570 
3571  if (!eit) {
3572  ERR("out of memory\n");
3574  }
3575 
3576  RtlCopyMemory(eit, tp.item->data, tp.item->size);
3577 
3579  if (!NT_SUCCESS(Status)) {
3580  ERR("delete_tree_item returned %08x\n", Status);
3581  ExFreePool(eit);
3582  return Status;
3583  }
3584 
3585  eit->level = level;
3586 
3588  if (!NT_SUCCESS(Status)) {
3589  ERR("insert_tree_item returned %08x\n", Status);
3590  ExFreePool(eit);
3591  return Status;
3592  }
3593 
3594  return STATUS_SUCCESS;
3595  }
3596 
3597  ERR("could not find EXTENT_ITEM for address %I64x\n", address);
3598 
3599  return STATUS_INTERNAL_ERROR;
3600 }
3601 
3603  NTSTATUS Status;
3604 
3605  if (t->parent && !t->parent->updated_extents && t->parent->has_address) {
3607  if (!NT_SUCCESS(Status))
3608  return Status;
3609  }
3610 
3612  if (!NT_SUCCESS(Status)) {
3613  ERR("update_tree_extents returned %08x\n", Status);
3614  return Status;
3615  }
3616 
3617  return STATUS_SUCCESS;
3618 }
3619 
3621  ULONG level, max_level;
3622  uint32_t min_size;
3623  bool empty, done_deletions = false;
3624  NTSTATUS Status;
3625  tree* t;
3626 
3627  TRACE("(%p)\n", Vcb);
3628 
3629  max_level = 0;
3630 
3631  for (level = 0; level <= 255; level++) {
3632  LIST_ENTRY *le, *nextle;
3633 
3634  empty = true;
3635 
3636  TRACE("doing level %u\n", level);
3637 
3638  le = Vcb->trees.Flink;
3639 
3640  while (le != &Vcb->trees) {
3642 
3643  nextle = le->Flink;
3644 
3645  if (t->write && t->header.level == level) {
3646  empty = false;
3647 
3648  if (t->header.num_items == 0) {
3649  if (t->parent) {
3650  done_deletions = true;
3651 
3652  TRACE("deleting tree in root %I64x\n", t->root->id);
3653 
3654  t->root->root_item.bytes_used -= Vcb->superblock.node_size;
3655 
3656  if (t->has_new_address) { // delete associated EXTENT_ITEM
3657  Status = reduce_tree_extent(Vcb, t->new_address, t, t->parent->header.tree_id, t->header.level, Irp, rollback);
3658 
3659  if (!NT_SUCCESS(Status)) {
3660  ERR("reduce_tree_extent returned %08x\n", Status);
3661  return Status;
3662  }
3663 
3664  t->has_new_address = false;
3665  } else if (t->has_address) {
3666  Status = reduce_tree_extent(Vcb,t->header.address, t, t->parent->header.tree_id, t->header.level, Irp, rollback);
3667 
3668  if (!NT_SUCCESS(Status)) {
3669  ERR("reduce_tree_extent returned %08x\n", Status);
3670  return Status;
3671  }
3672 
3673  t->has_address = false;
3674  }
3675 
3676  if (!t->paritem->ignore) {
3677  t->paritem->ignore = true;
3678  t->parent->header.num_items--;
3679  t->parent->size -= sizeof(internal_node);
3680  }
3681 
3682  RemoveEntryList(&t->paritem->list_entry);
3683  ExFreePool(t->paritem);
3684  t->paritem = NULL;
3685 
3686  free_tree(t);
3687  } else if (t->header.level != 0) {
3688  if (t->has_new_address) {
3689  Status = update_extent_level(Vcb, t->new_address, t, 0, Irp);
3690 
3691  if (!NT_SUCCESS(Status)) {
3692  ERR("update_extent_level returned %08x\n", Status);
3693  return Status;
3694  }
3695  }
3696 
3697  t->header.level = 0;
3698  }
3699  } else if (t->size > Vcb->superblock.node_size - sizeof(tree_header)) {
3700  TRACE("splitting overlarge tree (%x > %x)\n", t->size, Vcb->superblock.node_size - sizeof(tree_header));
3701 
3702  if (!t->updated_extents && t->has_address) {
3704  if (!NT_SUCCESS(Status)) {
3705  ERR("update_tree_extents_recursive returned %08x\n", Status);
3706  return Status;
3707  }
3708  }
3709 
3710  Status = split_tree(Vcb, t);
3711 
3712  if (!NT_SUCCESS(Status)) {
3713  ERR("split_tree returned %08x\n", Status);
3714  return Status;
3715  }
3716  }
3717  }
3718 
3719  le = nextle;
3720  }
3721 
3722  if (!empty) {
3723  max_level = level;
3724  } else {
3725  TRACE("nothing found for level %u\n", level);
3726  break;
3727  }
3728  }
3729 
3730  min_size = (Vcb->superblock.node_size - sizeof(tree_header)) / 2;
3731 
3732  for (level = 0; level <= max_level; level++) {
3733  LIST_ENTRY* le;
3734 
3735  le = Vcb->trees.Flink;
3736 
3737  while (le != &Vcb->trees) {
3739 
3740  if (t->write && t->header.level == level && t->header.num_items > 0 && t->parent && t->size < min_size &&
3741  t->root->id != BTRFS_ROOT_FREE_SPACE && is_tree_unique(Vcb, t, Irp)) {
3742  bool done;
3743 
3744  do {
3745  Status = try_tree_amalgamate(Vcb, t, &done, &done_deletions, Irp, rollback);
3746  if (!NT_SUCCESS(Status)) {
3747  ERR("try_tree_amalgamate returned %08x\n", Status);
3748  return Status;
3749  }
3750  } while (done && t->size < min_size);
3751  }
3752 
3753  le = le->Flink;
3754  }
3755  }
3756 
3757  // simplify trees if top tree only has one entry
3758 
3759  if (done_deletions) {
3760  for (level = max_level; level > 0; level--) {
3761  LIST_ENTRY *le, *nextle;
3762 
3763  le = Vcb->trees.Flink;
3764  while (le != &Vcb->trees) {
3765  nextle = le->Flink;
3767 
3768  if (t->write && t->header.level == level) {
3769  if (!t->parent && t->header.num_items == 1) {
3770  LIST_ENTRY* le2 = t->itemlist.Flink;
3771  tree_data* td = NULL;
3772  tree* child_tree = NULL;
3773 
3774  while (le2 != &t->itemlist) {
3776  if (!td->ignore)
3777  break;
3778  le2 = le2->Flink;
3779  }
3780 
3781  TRACE("deleting top-level tree in root %I64x with one item\n", t->root->id);
3782 
3783  if (t->has_new_address) { // delete associated EXTENT_ITEM
3784  Status = reduce_tree_extent(Vcb, t->new_address, t, t->header.tree_id, t->header.level, Irp, rollback);
3785 
3786  if (!NT_SUCCESS(Status)) {
3787  ERR("reduce_tree_extent returned %08x\n", Status);
3788  return Status;
3789  }
3790 
3791  t->has_new_address = false;
3792  } else if (t->has_address) {
3793  Status = reduce_tree_extent(Vcb,t->header.address, t, t->header.tree_id, t->header.level, Irp, rollback);
3794 
3795  if (!NT_SUCCESS(Status)) {
3796  ERR("reduce_tree_extent returned %08x\n", Status);
3797  return Status;
3798  }
3799 
3800  t->has_address = false;
3801  }
3802 
3803  if (!td->treeholder.tree) { // load first item if not already loaded
3804  KEY searchkey = {0,0,0};
3805  traverse_ptr tp;
3806 
3807  Status = find_item(Vcb, t->root, &tp, &searchkey, false, Irp);
3808  if (!NT_SUCCESS(Status)) {
3809  ERR("error - find_item returned %08x\n", Status);
3810  return Status;
3811  }
3812  }
3813 
3814  child_tree = td->treeholder.tree;
3815 
3816  if (child_tree) {
3817  child_tree->parent = NULL;
3818  child_tree->paritem = NULL;
3819  }
3820 
3821  t->root->root_item.bytes_used -= Vcb->superblock.node_size;
3822 
3823  free_tree(t);
3824 
3825  if (child_tree)
3826  child_tree->root->treeholder.tree = child_tree;
3827  }
3828  }
3829 
3830  le = nextle;
3831  }
3832  }
3833  }
3834 
3835  return STATUS_SUCCESS;
3836 }
3837 
3839  NTSTATUS Status;
3840 
3841  if (!th->tree) {
3842  uint8_t* buf;
3843  chunk* c;
3844 
3845  buf = ExAllocatePoolWithTag(PagedPool, Vcb->superblock.node_size, ALLOC_TAG);
3846  if (!buf) {
3847  ERR("out of memory\n");
3849  }
3850 
3851  Status = read_data(Vcb, th->address, Vcb->superblock.node_size, NULL, true, buf, NULL,
3852  &c, Irp, th->generation, false, NormalPagePriority);
3853  if (!NT_SUCCESS(Status)) {
3854  ERR("read_data returned 0x%08x\n", Status);
3855  ExFreePool(buf);
3856  return Status;
3857  }
3858 
3859  Status = load_tree(Vcb, th->address, buf, r, &th->tree);
3860 
3861  if (!th->tree || th->tree->buf != buf)
3862  ExFreePool(buf);
3863 
3864  if (!NT_SUCCESS(Status)) {
3865