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