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