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