ReactOS  0.4.15-dev-5112-g22d8c0f
treefuncs.c
Go to the documentation of this file.
1 /* Copyright (c) Mark Harmstone 2016-17
2  *
3  * This file is part of WinBtrfs.
4  *
5  * WinBtrfs is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU Lesser General Public Licence as published by
7  * the Free Software Foundation, either version 3 of the Licence, or
8  * (at your option) any later version.
9  *
10  * WinBtrfs is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU Lesser General Public Licence for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public Licence
16  * along with WinBtrfs. If not, see <http://www.gnu.org/licenses/>. */
17 
18 #include "btrfs_drv.h"
19 #include "crc32c.h"
20 
21 __attribute__((nonnull(1,3,4,5)))
23  tree_header* th;
24  tree* t;
25  tree_data* td;
26  uint8_t h;
27  bool inserted;
28  LIST_ENTRY* le;
29 
30  th = (tree_header*)buf;
31 
33  if (!t) {
34  ERR("out of memory\n");
36  }
37 
38  if (th->level > 0) {
40  if (!t->nonpaged) {
41  ERR("out of memory\n");
42  ExFreePool(t);
44  }
45 
46  ExInitializeFastMutex(&t->nonpaged->mutex);
47  } else
48  t->nonpaged = NULL;
49 
50  RtlCopyMemory(&t->header, th, sizeof(tree_header));
51  t->hash = calc_crc32c(0xffffffff, (uint8_t*)&addr, sizeof(uint64_t));
52  t->has_address = true;
53  t->Vcb = Vcb;
54  t->parent = NULL;
55  t->root = r;
56  t->paritem = NULL;
57  t->size = 0;
58  t->new_address = 0;
59  t->has_new_address = false;
60  t->updated_extents = false;
61  t->write = false;
62  t->uniqueness_determined = false;
63 
64  InitializeListHead(&t->itemlist);
65 
66  if (t->header.level == 0) { // leaf node
67  leaf_node* ln = (leaf_node*)(buf + sizeof(tree_header));
68  unsigned int i;
69 
70  if ((t->header.num_items * sizeof(leaf_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
71  ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
72  ExFreePool(t);
74  }
75 
76  for (i = 0; i < t->header.num_items; i++) {
77  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
78  if (!td) {
79  ERR("out of memory\n");
80  ExFreePool(t);
82  }
83 
84  td->key = ln[i].key;
85 
86  if (ln[i].size > 0)
87  td->data = buf + sizeof(tree_header) + ln[i].offset;
88  else
89  td->data = NULL;
90 
91  if (ln[i].size + sizeof(tree_header) + sizeof(leaf_node) > Vcb->superblock.node_size) {
92  ERR("overlarge item in tree %I64x: %u > %Iu\n", addr, ln[i].size, Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
93  ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
94  ExFreePool(t);
95  return STATUS_INTERNAL_ERROR;
96  }
97 
98  td->size = (uint16_t)ln[i].size;
99  td->ignore = false;
100  td->inserted = false;
101 
102  InsertTailList(&t->itemlist, &td->list_entry);
103 
104  t->size += ln[i].size;
105  }
106 
107  t->size += t->header.num_items * sizeof(leaf_node);
108  t->buf = buf;
109  } else {
110  internal_node* in = (internal_node*)(buf + sizeof(tree_header));
111  unsigned int i;
112 
113  if ((t->header.num_items * sizeof(internal_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
114  ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
115  ExFreePool(t);
117  }
118 
119  for (i = 0; i < t->header.num_items; i++) {
120  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
121  if (!td) {
122  ERR("out of memory\n");
123  ExFreePool(t);
125  }
126 
127  td->key = in[i].key;
128 
129  td->treeholder.address = in[i].address;
130  td->treeholder.generation = in[i].generation;
131  td->treeholder.tree = NULL;
132  td->ignore = false;
133  td->inserted = false;
134 
135  InsertTailList(&t->itemlist, &td->list_entry);
136  }
137 
138  t->size = t->header.num_items * sizeof(internal_node);
139  t->buf = NULL;
140  }
141 
142  ExAcquireFastMutex(&Vcb->trees_list_mutex);
143 
144  InsertTailList(&Vcb->trees, &t->list_entry);
145 
146  h = t->hash >> 24;
147 
148  if (!Vcb->trees_ptrs[h]) {
149  uint8_t h2 = h;
150 
151  le = Vcb->trees_hash.Flink;
152 
153  if (h2 > 0) {
154  h2--;
155  do {
156  if (Vcb->trees_ptrs[h2]) {
157  le = Vcb->trees_ptrs[h2];
158  break;
159  }
160 
161  h2--;
162  } while (h2 > 0);
163  }
164  } else
165  le = Vcb->trees_ptrs[h];
166 
167  inserted = false;
168  while (le != &Vcb->trees_hash) {
169  tree* t2 = CONTAINING_RECORD(le, tree, list_entry_hash);
170 
171  if (t2->hash >= t->hash) {
172  InsertHeadList(le->Blink, &t->list_entry_hash);
173  inserted = true;
174  break;
175  }
176 
177  le = le->Flink;
178  }
179 
180  if (!inserted)
181  InsertTailList(&Vcb->trees_hash, &t->list_entry_hash);
182 
183  if (!Vcb->trees_ptrs[h] || t->list_entry_hash.Flink == Vcb->trees_ptrs[h])
184  Vcb->trees_ptrs[h] = &t->list_entry_hash;
185 
186  ExReleaseFastMutex(&Vcb->trees_list_mutex);
187 
188  TRACE("returning %p\n", t);
189 
190  *pt = t;
191 
192  return STATUS_SUCCESS;
193 }
194 
195 __attribute__((nonnull(1,2,3,4)))
196 static NTSTATUS do_load_tree2(device_extension* Vcb, tree_holder* th, uint8_t* buf, root* r, tree* t, tree_data* td) {
197  if (!th->tree) {
199  tree* nt;
200 
201  Status = load_tree(Vcb, th->address, buf, r, &nt);
202  if (!NT_SUCCESS(Status)) {
203  ERR("load_tree returned %08lx\n", Status);
204  return Status;
205  }
206 
207  nt->parent = t;
208 
209 #ifdef DEBUG_PARANOID
210  if (t && t->header.level <= nt->header.level) int3;
211 #endif
212 
213  nt->paritem = td;
214 
215  th->tree = nt;
216  }
217 
218  return STATUS_SUCCESS;
219 }
220 
221 __attribute__((nonnull(1,2,3)))
224  uint8_t* buf;
225  chunk* c;
226 
227  buf = ExAllocatePoolWithTag(PagedPool, Vcb->superblock.node_size, ALLOC_TAG);
228  if (!buf) {
229  ERR("out of memory\n");
231  }
232 
233  Status = read_data(Vcb, th->address, Vcb->superblock.node_size, NULL, true, buf, NULL,
234  &c, Irp, th->generation, false, NormalPagePriority);
235  if (!NT_SUCCESS(Status)) {
236  ERR("read_data returned 0x%08lx\n", Status);
237  ExFreePool(buf);
238  return Status;
239  }
240 
241  if (t)
242  ExAcquireFastMutex(&t->nonpaged->mutex);
243  else
244  ExAcquireResourceExclusiveLite(&r->nonpaged->load_tree_lock, true);
245 
246  Status = do_load_tree2(Vcb, th, buf, r, t, td);
247 
248  if (t)
249  ExReleaseFastMutex(&t->nonpaged->mutex);
250  else
251  ExReleaseResourceLite(&r->nonpaged->load_tree_lock);
252 
253  if (!th->tree || th->tree->buf != buf)
254  ExFreePool(buf);
255 
256  if (!NT_SUCCESS(Status)) {
257  ERR("do_load_tree2 returned %08lx\n", Status);
258  return Status;
259  }
260 
261  return Status;
262 }
263 
264 __attribute__((nonnull(1)))
265 void free_tree(tree* t) {
266  tree* par;
267  root* r = t->root;
268 
269  // No need to acquire lock, as this is only ever called while Vcb->tree_lock held exclusively
270 
271  par = t->parent;
272 
273  if (r && r->treeholder.tree != t)
274  r = NULL;
275 
276  if (par) {
277  if (t->paritem)
278  t->paritem->treeholder.tree = NULL;
279  }
280 
281  while (!IsListEmpty(&t->itemlist)) {
283 
284  if (t->header.level == 0 && td->data && td->inserted)
285  ExFreePool(td->data);
286 
287  ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
288  }
289 
290  RemoveEntryList(&t->list_entry);
291 
292  if (r)
293  r->treeholder.tree = NULL;
294 
295  if (t->list_entry_hash.Flink) {
296  uint8_t h = t->hash >> 24;
297  if (t->Vcb->trees_ptrs[h] == &t->list_entry_hash) {
298  if (t->list_entry_hash.Flink != &t->Vcb->trees_hash) {
299  tree* t2 = CONTAINING_RECORD(t->list_entry_hash.Flink, tree, list_entry_hash);
300 
301  if ((t2->hash >> 24) == h)
302  t->Vcb->trees_ptrs[h] = &t2->list_entry_hash;
303  else
304  t->Vcb->trees_ptrs[h] = NULL;
305  } else
306  t->Vcb->trees_ptrs[h] = NULL;
307  }
308 
309  RemoveEntryList(&t->list_entry_hash);
310  }
311 
312  if (t->buf)
313  ExFreePool(t->buf);
314 
315  if (t->nonpaged)
316  ExFreePool(t->nonpaged);
317 
318  ExFreePool(t);
319 }
320 
321 __attribute__((nonnull(1)))
322 static __inline tree_data* first_item(tree* t) {
323  LIST_ENTRY* le = t->itemlist.Flink;
324 
325  if (le == &t->itemlist)
326  return NULL;
327 
329 }
330 
331 __attribute__((nonnull(1,2)))
332 static __inline tree_data* prev_item(tree* t, tree_data* td) {
333  LIST_ENTRY* le = td->list_entry.Blink;
334 
335  if (le == &t->itemlist)
336  return NULL;
337 
339 }
340 
341 __attribute__((nonnull(1,2)))
342 static __inline tree_data* next_item(tree* t, tree_data* td) {
343  LIST_ENTRY* le = td->list_entry.Flink;
344 
345  if (le == &t->itemlist)
346  return NULL;
347 
349 }
350 
351 __attribute__((nonnull(1,2,3,4)))
352 static NTSTATUS next_item2(device_extension* Vcb, tree* t, tree_data* td, traverse_ptr* tp) {
353  tree_data* td2 = next_item(t, td);
354  tree* t2;
355 
356  if (td2) {
357  tp->tree = t;
358  tp->item = td2;
359  return STATUS_SUCCESS;
360  }
361 
362  t2 = t;
363 
364  do {
365  td2 = t2->paritem;
366  t2 = t2->parent;
367  } while (td2 && !next_item(t2, td2));
368 
369  if (!td2)
370  return STATUS_NOT_FOUND;
371 
372  td2 = next_item(t2, td2);
373 
374  return find_item_to_level(Vcb, t2->root, tp, &td2->key, false, t->header.level, NULL);
375 }
376 
377 __attribute__((nonnull(1,2,3,4,5)))
378 NTSTATUS skip_to_difference(device_extension* Vcb, traverse_ptr* tp, traverse_ptr* tp2, bool* ended1, bool* ended2) {
380  tree *t1, *t2;
381  tree_data *td1, *td2;
382 
383  t1 = tp->tree;
384  t2 = tp2->tree;
385 
386  do {
387  td1 = t1->paritem;
388  td2 = t2->paritem;
389  t1 = t1->parent;
390  t2 = t2->parent;
391  } while (t1 && t2 && t1->header.address == t2->header.address);
392 
393  while (true) {
394  traverse_ptr tp3, tp4;
395 
396  Status = next_item2(Vcb, t1, td1, &tp3);
397  if (Status == STATUS_NOT_FOUND)
398  *ended1 = true;
399  else if (!NT_SUCCESS(Status)) {
400  ERR("next_item2 returned %08lx\n", Status);
401  return Status;
402  }
403 
404  Status = next_item2(Vcb, t2, td2, &tp4);
405  if (Status == STATUS_NOT_FOUND)
406  *ended2 = true;
407  else if (!NT_SUCCESS(Status)) {
408  ERR("next_item2 returned %08lx\n", Status);
409  return Status;
410  }
411 
412  if (*ended1 || *ended2) {
413  if (!*ended1) {
414  Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
415  if (!NT_SUCCESS(Status)) {
416  ERR("find_item returned %08lx\n", Status);
417  return Status;
418  }
419  } else if (!*ended2) {
420  Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
421  if (!NT_SUCCESS(Status)) {
422  ERR("find_item returned %08lx\n", Status);
423  return Status;
424  }
425  }
426 
427  return STATUS_SUCCESS;
428  }
429 
430  if (tp3.tree->header.address != tp4.tree->header.address) {
431  Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
432  if (!NT_SUCCESS(Status)) {
433  ERR("find_item returned %08lx\n", Status);
434  return Status;
435  }
436 
437  Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
438  if (!NT_SUCCESS(Status)) {
439  ERR("find_item returned %08lx\n", Status);
440  return Status;
441  }
442 
443  return STATUS_SUCCESS;
444  }
445 
446  t1 = tp3.tree;
447  td1 = tp3.item;
448  t2 = tp4.tree;
449  td2 = tp4.item;
450  }
451 }
452 
453 __attribute__((nonnull(1,2,3,4)))
454 static NTSTATUS find_item_in_tree(device_extension* Vcb, tree* t, traverse_ptr* tp, const KEY* searchkey, bool ignore, uint8_t level, PIRP Irp) {
455  int cmp;
456  tree_data *td, *lasttd;
457  KEY key2;
458 
459  cmp = 1;
460  td = first_item(t);
461  lasttd = NULL;
462 
463  if (!td) return STATUS_NOT_FOUND;
464 
465  key2 = *searchkey;
466 
467  do {
468  cmp = keycmp(key2, td->key);
469 
470  if (cmp == 1) {
471  lasttd = td;
472  td = next_item(t, td);
473  }
474 
475  if (t->header.level == 0 && cmp == 0 && !ignore && td && td->ignore) {
476  tree_data* origtd = td;
477 
478  while (td && td->ignore)
479  td = next_item(t, td);
480 
481  if (td) {
482  cmp = keycmp(key2, td->key);
483 
484  if (cmp != 0) {
485  td = origtd;
486  cmp = 0;
487  }
488  } else
489  td = origtd;
490  }
491  } while (td && cmp == 1);
492 
493  if ((cmp == -1 || !td) && lasttd)
494  td = lasttd;
495 
496  if (t->header.level == 0) {
497  if (td->ignore && !ignore) {
498  traverse_ptr oldtp;
499 
500  oldtp.tree = t;
501  oldtp.item = td;
502 
503  while (find_prev_item(Vcb, &oldtp, tp, Irp)) {
504  if (!tp->item->ignore)
505  return STATUS_SUCCESS;
506 
507  oldtp = *tp;
508  }
509 
510  // if no valid entries before where item should be, look afterwards instead
511 
512  oldtp.tree = t;
513  oldtp.item = td;
514 
515  while (find_next_item(Vcb, &oldtp, tp, true, Irp)) {
516  if (!tp->item->ignore)
517  return STATUS_SUCCESS;
518 
519  oldtp = *tp;
520  }
521 
522  return STATUS_NOT_FOUND;
523  } else {
524  tp->tree = t;
525  tp->item = td;
526  }
527 
528  return STATUS_SUCCESS;
529  } else {
531 
532  while (td && td->treeholder.tree && IsListEmpty(&td->treeholder.tree->itemlist)) {
533  td = prev_item(t, td);
534  }
535 
536  if (!td)
537  return STATUS_NOT_FOUND;
538 
539  if (t->header.level <= level) {
540  tp->tree = t;
541  tp->item = td;
542  return STATUS_SUCCESS;
543  }
544 
545  if (!td->treeholder.tree) {
546  Status = do_load_tree(Vcb, &td->treeholder, t->root, t, td, Irp);
547  if (!NT_SUCCESS(Status)) {
548  ERR("do_load_tree returned %08lx\n", Status);
549  return Status;
550  }
551  }
552 
553  Status = find_item_in_tree(Vcb, td->treeholder.tree, tp, searchkey, ignore, level, Irp);
554 
555  return Status;
556  }
557 }
558 
559 __attribute__((nonnull(1,2,3,4)))
561  _In_ const KEY* searchkey, _In_ bool ignore, _In_opt_ PIRP Irp) {
563 
564  if (!r->treeholder.tree) {
565  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
566  if (!NT_SUCCESS(Status)) {
567  ERR("do_load_tree returned %08lx\n", Status);
568  return Status;
569  }
570  }
571 
572  Status = find_item_in_tree(Vcb, r->treeholder.tree, tp, searchkey, ignore, 0, Irp);
574  ERR("find_item_in_tree returned %08lx\n", Status);
575  }
576 
577  return Status;
578 }
579 
580 __attribute__((nonnull(1,2,3,4)))
583 
584  if (!r->treeholder.tree) {
585  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
586  if (!NT_SUCCESS(Status)) {
587  ERR("do_load_tree returned %08lx\n", Status);
588  return Status;
589  }
590  }
591 
592  Status = find_item_in_tree(Vcb, r->treeholder.tree, tp, searchkey, ignore, level, Irp);
594  ERR("find_item_in_tree returned %08lx\n", Status);
595  }
596 
597  if (Status == STATUS_NOT_FOUND) {
598  tp->tree = r->treeholder.tree;
599  tp->item = NULL;
600  }
601 
602  return Status;
603 }
604 
605 __attribute__((nonnull(1,2,3)))
606 bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension* Vcb, const traverse_ptr* tp, traverse_ptr* next_tp, bool ignore, PIRP Irp) {
607  tree* t;
608  tree_data *td = NULL, *next;
610 
611  next = next_item(tp->tree, tp->item);
612 
613  if (!ignore) {
614  while (next && next->ignore)
615  next = next_item(tp->tree, next);
616  }
617 
618  if (next) {
619  next_tp->tree = tp->tree;
620  next_tp->item = next;
621 
622 #ifdef DEBUG_PARANOID
623  if (!ignore && next_tp->item->ignore) {
624  ERR("error - returning ignored item\n");
625  int3;
626  }
627 #endif
628 
629  return true;
630  }
631 
632  if (!tp->tree->parent)
633  return false;
634 
635  t = tp->tree;
636  do {
637  if (t->parent) {
638  td = next_item(t->parent, t->paritem);
639 
640  if (td) break;
641  }
642 
643  t = t->parent;
644  } while (t);
645 
646  if (!t)
647  return false;
648 
649  if (!td->treeholder.tree) {
650  Status = do_load_tree(Vcb, &td->treeholder, t->parent->root, t->parent, td, Irp);
651  if (!NT_SUCCESS(Status)) {
652  ERR("do_load_tree returned %08lx\n", Status);
653  return false;
654  }
655  }
656 
657  t = td->treeholder.tree;
658 
659  while (t->header.level != 0) {
660  tree_data* fi;
661 
662  fi = first_item(t);
663 
664  if (!fi)
665  return false;
666 
667  if (!fi->treeholder.tree) {
668  Status = do_load_tree(Vcb, &fi->treeholder, t->parent->root, t, fi, Irp);
669  if (!NT_SUCCESS(Status)) {
670  ERR("do_load_tree returned %08lx\n", Status);
671  return false;
672  }
673  }
674 
675  t = fi->treeholder.tree;
676  }
677 
678  next_tp->tree = t;
679  next_tp->item = first_item(t);
680 
681  if (!next_tp->item)
682  return false;
683 
684  if (!ignore && next_tp->item->ignore) {
685  traverse_ptr ntp2;
686  bool b;
687 
688  while ((b = find_next_item(Vcb, next_tp, &ntp2, true, Irp))) {
689  *next_tp = ntp2;
690 
691  if (!next_tp->item->ignore)
692  break;
693  }
694 
695  if (!b)
696  return false;
697  }
698 
699 #ifdef DEBUG_PARANOID
700  if (!ignore && next_tp->item->ignore) {
701  ERR("error - returning ignored item\n");
702  int3;
703  }
704 #endif
705 
706  return true;
707 }
708 
709 __attribute__((nonnull(1)))
710 static __inline tree_data* last_item(tree* t) {
711  LIST_ENTRY* le = t->itemlist.Blink;
712 
713  if (le == &t->itemlist)
714  return NULL;
715 
717 }
718 
719 __attribute__((nonnull(1,2,3)))
721  tree* t;
722  tree_data* td;
724 
725  // FIXME - support ignore flag
726  if (prev_item(tp->tree, tp->item)) {
727  prev_tp->tree = tp->tree;
728  prev_tp->item = prev_item(tp->tree, tp->item);
729 
730  return true;
731  }
732 
733  if (!tp->tree->parent)
734  return false;
735 
736  t = tp->tree;
737  while (t && (!t->parent || !prev_item(t->parent, t->paritem))) {
738  t = t->parent;
739  }
740 
741  if (!t)
742  return false;
743 
744  td = prev_item(t->parent, t->paritem);
745 
746  if (!td->treeholder.tree) {
747  Status = do_load_tree(Vcb, &td->treeholder, t->parent->root, t->parent, td, Irp);
748  if (!NT_SUCCESS(Status)) {
749  ERR("do_load_tree returned %08lx\n", Status);
750  return false;
751  }
752  }
753 
754  t = td->treeholder.tree;
755 
756  while (t->header.level != 0) {
757  tree_data* li;
758 
759  li = last_item(t);
760 
761  if (!li->treeholder.tree) {
762  Status = do_load_tree(Vcb, &li->treeholder, t->parent->root, t, li, Irp);
763  if (!NT_SUCCESS(Status)) {
764  ERR("do_load_tree returned %08lx\n", Status);
765  return false;
766  }
767  }
768 
769  t = li->treeholder.tree;
770  }
771 
772  prev_tp->tree = t;
773  prev_tp->item = last_item(t);
774 
775  return true;
776 }
777 
778 __attribute__((nonnull(1,2)))
780  LIST_ENTRY* le;
781  ULONG level;
782 
783  for (level = 0; level <= 255; level++) {
784  bool empty = true;
785 
786  le = Vcb->trees.Flink;
787 
788  while (le != &Vcb->trees) {
789  LIST_ENTRY* nextle = le->Flink;
791 
792  if (t->root == r) {
793  if (t->header.level == level) {
794  bool top = !t->paritem;
795 
796  empty = false;
797 
798  free_tree(t);
799  if (top && r->treeholder.tree == t)
800  r->treeholder.tree = NULL;
801 
802  if (IsListEmpty(&Vcb->trees))
803  return;
804  } else if (t->header.level > level)
805  empty = false;
806  }
807 
808  le = nextle;
809  }
810 
811  if (empty)
812  break;
813  }
814 }
815 
816 __attribute__((nonnull(1)))
818  LIST_ENTRY* le;
819  ULONG level;
820 
821  for (level = 0; level <= 255; level++) {
822  bool empty = true;
823 
824  le = Vcb->trees.Flink;
825 
826  while (le != &Vcb->trees) {
827  LIST_ENTRY* nextle = le->Flink;
829  root* r = t->root;
830 
831  if (t->header.level == level) {
832  bool top = !t->paritem;
833 
834  empty = false;
835 
836  free_tree(t);
837  if (top && r->treeholder.tree == t)
838  r->treeholder.tree = NULL;
839 
840  if (IsListEmpty(&Vcb->trees))
841  break;
842  } else if (t->header.level > level)
843  empty = false;
844 
845  le = nextle;
846  }
847 
848  if (empty)
849  break;
850  }
851 
852  reap_filerefs(Vcb, Vcb->root_fileref);
853  reap_fcbs(Vcb);
854 }
855 
856 #ifdef _MSC_VER
857 #pragma warning(push)
858 #pragma warning(suppress: 28194)
859 #endif
860 __attribute__((nonnull(1,3)))
862  rollback_item* ri;
863 
865  if (!ri) {
866  ERR("out of memory\n");
867  return;
868  }
869 
870  ri->type = type;
871  ri->ptr = ptr;
873 }
874 #ifdef _MSC_VER
875 #pragma warning(pop)
876 #endif
877 
878 #ifdef _MSC_VER
879 #pragma warning(push)
880 #pragma warning(suppress: 28194)
881 #endif
882 __attribute__((nonnull(1,2)))
887  KEY searchkey;
888  int cmp;
889  tree_data *td, *paritem;
890  tree* t;
891 #ifdef _DEBUG
892  LIST_ENTRY* le;
893  KEY firstitem = {0xcccccccccccccccc,0xcc,0xcccccccccccccccc};
894 #endif
896 
897  TRACE("(%p, %p, %I64x, %x, %I64x, %p, %x, %p)\n", Vcb, r, obj_id, obj_type, offset, data, size, ptp);
898 
899  searchkey.obj_id = obj_id;
900  searchkey.obj_type = obj_type;
901  searchkey.offset = offset;
902 
903  Status = find_item(Vcb, r, &tp, &searchkey, true, Irp);
904  if (Status == STATUS_NOT_FOUND) {
905  if (!r->treeholder.tree) {
906  Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
907  if (!NT_SUCCESS(Status)) {
908  ERR("do_load_tree returned %08lx\n", Status);
909  return Status;
910  }
911  }
912 
913  if (r->treeholder.tree && r->treeholder.tree->header.num_items == 0) {
914  tp.tree = r->treeholder.tree;
915  tp.item = NULL;
916  } else {
917  ERR("error: unable to load tree for root %I64x\n", r->id);
918  return STATUS_INTERNAL_ERROR;
919  }
920  } else if (!NT_SUCCESS(Status)) {
921  ERR("find_item returned %08lx\n", Status);
922  return Status;
923  }
924 
925  TRACE("tp.item = %p\n", tp.item);
926 
927  if (tp.item) {
928  TRACE("tp.item->key = %p\n", &tp.item->key);
929  cmp = keycmp(searchkey, tp.item->key);
930 
931  if (cmp == 0 && !tp.item->ignore) {
932  ERR("error: key (%I64x,%x,%I64x) already present\n", obj_id, obj_type, offset);
933 #ifdef DEBUG_PARANOID
934  int3;
935 #endif
936  return STATUS_INTERNAL_ERROR;
937  }
938  } else
939  cmp = -1;
940 
941  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
942  if (!td) {
943  ERR("out of memory\n");
945  }
946 
947  td->key = searchkey;
948  td->size = size;
949  td->data = data;
950  td->ignore = false;
951  td->inserted = true;
952 
953 #ifdef _DEBUG
954  le = tp.tree->itemlist.Flink;
955  while (le != &tp.tree->itemlist) {
957  firstitem = td2->key;
958  break;
959  }
960 
961  TRACE("inserting %I64x,%x,%I64x into tree beginning %I64x,%x,%I64x (num_items %x)\n", obj_id, obj_type, offset, firstitem.obj_id, firstitem.obj_type, firstitem.offset, tp.tree->header.num_items);
962 #endif
963 
964  if (cmp == -1) { // very first key in root
966 
967  paritem = tp.tree->paritem;
968  while (paritem) {
969  if (!keycmp(paritem->key, tp.item->key)) {
970  paritem->key = searchkey;
971  } else
972  break;
973 
974  paritem = paritem->treeholder.tree->paritem;
975  }
976  } else if (cmp == 0)
977  InsertHeadList(tp.item->list_entry.Blink, &td->list_entry); // make sure non-deleted item is before deleted ones
978  else
980 
981  tp.tree->header.num_items++;
982  tp.tree->size += size + sizeof(leaf_node);
983 
984  if (!tp.tree->write) {
985  tp.tree->write = true;
986  Vcb->need_write = true;
987  }
988 
989  if (ptp)
990  *ptp = tp;
991 
992  t = tp.tree;
993  while (t) {
994  if (t->paritem && t->paritem->ignore) {
995  t->paritem->ignore = false;
996  t->parent->header.num_items++;
997  t->parent->size += sizeof(internal_node);
998  }
999 
1000  t->header.generation = Vcb->superblock.generation;
1001  t = t->parent;
1002  }
1003 
1004  return STATUS_SUCCESS;
1005 }
1006 #ifdef _MSC_VER
1007 #pragma warning(pop)
1008 #endif
1009 
1010 __attribute__((nonnull(1,2)))
1012  tree* t;
1013  uint64_t gen;
1014 
1015  TRACE("deleting item %I64x,%x,%I64x (ignore = %s)\n", tp->item->key.obj_id, tp->item->key.obj_type, tp->item->key.offset, tp->item->ignore ? "true" : "false");
1016 
1017 #ifdef DEBUG_PARANOID
1018  if (tp->item->ignore) {
1019  ERR("trying to delete already-deleted item %I64x,%x,%I64x\n", tp->item->key.obj_id, tp->item->key.obj_type, tp->item->key.offset);
1020  int3;
1021  return STATUS_INTERNAL_ERROR;
1022  }
1023 #endif
1024 
1025  tp->item->ignore = true;
1026 
1027  if (!tp->tree->write) {
1028  tp->tree->write = true;
1029  Vcb->need_write = true;
1030  }
1031 
1032  tp->tree->header.num_items--;
1033 
1034  if (tp->tree->header.level == 0)
1035  tp->tree->size -= sizeof(leaf_node) + tp->item->size;
1036  else
1037  tp->tree->size -= sizeof(internal_node);
1038 
1039  gen = tp->tree->Vcb->superblock.generation;
1040 
1041  t = tp->tree;
1042  while (t) {
1043  t->header.generation = gen;
1044  t = t->parent;
1045  }
1046 
1047  return STATUS_SUCCESS;
1048 }
1049 
1050 __attribute__((nonnull(1)))
1052  while (!IsListEmpty(rollback)) {
1055 
1056  switch (ri->type) {
1057  case ROLLBACK_ADD_SPACE:
1061  ExFreePool(ri->ptr);
1062  break;
1063 
1064  default:
1065  break;
1066  }
1067 
1068  ExFreePool(ri);
1069  }
1070 }
1071 
1072 __attribute__((nonnull(1,2)))
1074  NTSTATUS Status;
1075  rollback_item* ri;
1076 
1077  while (!IsListEmpty(rollback)) {
1080 
1081  switch (ri->type) {
1083  {
1084  rollback_extent* re = ri->ptr;
1085 
1086  re->ext->ignore = true;
1087 
1088  switch (re->ext->extent_data.type) {
1089  case EXTENT_TYPE_REGULAR:
1090  case EXTENT_TYPE_PREALLOC: {
1092 
1093  if (ed2->size != 0) {
1095 
1096  if (c) {
1097  Status = update_changed_extent_ref(Vcb, c, ed2->address, ed2->size, re->fcb->subvol->id,
1098  re->fcb->inode, re->ext->offset - ed2->offset, -1,
1099  re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1100 
1101  if (!NT_SUCCESS(Status))
1102  ERR("update_changed_extent_ref returned %08lx\n", Status);
1103  }
1104 
1105  re->fcb->inode_item.st_blocks -= ed2->num_bytes;
1106  }
1107 
1108  break;
1109  }
1110 
1111  case EXTENT_TYPE_INLINE:
1113  break;
1114  }
1115 
1116  ExFreePool(re);
1117  break;
1118  }
1119 
1121  {
1122  rollback_extent* re = ri->ptr;
1123 
1124  re->ext->ignore = false;
1125 
1126  switch (re->ext->extent_data.type) {
1127  case EXTENT_TYPE_REGULAR:
1128  case EXTENT_TYPE_PREALLOC: {
1130 
1131  if (ed2->size != 0) {
1133 
1134  if (c) {
1135  Status = update_changed_extent_ref(Vcb, c, ed2->address, ed2->size, re->fcb->subvol->id,
1136  re->fcb->inode, re->ext->offset - ed2->offset, 1,
1137  re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1138 
1139  if (!NT_SUCCESS(Status))
1140  ERR("update_changed_extent_ref returned %08lx\n", Status);
1141  }
1142 
1143  re->fcb->inode_item.st_blocks += ed2->num_bytes;
1144  }
1145 
1146  break;
1147  }
1148 
1149  case EXTENT_TYPE_INLINE:
1151  break;
1152  }
1153 
1154  ExFreePool(re);
1155  break;
1156  }
1157 
1158  case ROLLBACK_ADD_SPACE:
1160  {
1161  rollback_space* rs = ri->ptr;
1162 
1163  if (rs->chunk)
1165 
1166  if (ri->type == ROLLBACK_ADD_SPACE)
1167  space_list_subtract2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1168  else
1169  space_list_add2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1170 
1171  if (rs->chunk) {
1172  if (ri->type == ROLLBACK_ADD_SPACE)
1173  rs->chunk->used += rs->length;
1174  else
1175  rs->chunk->used -= rs->length;
1176  }
1177 
1178  if (rs->chunk) {
1179  LIST_ENTRY* le2 = le->Blink;
1180 
1181  while (le2 != rollback) {
1182  LIST_ENTRY* le3 = le2->Blink;
1184 
1185  if (ri2->type == ROLLBACK_ADD_SPACE || ri2->type == ROLLBACK_SUBTRACT_SPACE) {
1186  rollback_space* rs2 = ri2->ptr;
1187 
1188  if (rs2->chunk == rs->chunk) {
1189  if (ri2->type == ROLLBACK_ADD_SPACE) {
1190  space_list_subtract2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1191  rs->chunk->used += rs2->length;
1192  } else {
1193  space_list_add2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1194  rs->chunk->used -= rs2->length;
1195  }
1196 
1197  ExFreePool(rs2);
1198  RemoveEntryList(&ri2->list_entry);
1199  ExFreePool(ri2);
1200  }
1201  }
1202 
1203  le2 = le3;
1204  }
1205 
1207  }
1208 
1209  ExFreePool(rs);
1210 
1211  break;
1212  }
1213  }
1214 
1215  ExFreePool(ri);
1216  }
1217 }
1218 
1219 __attribute__((nonnull(1,2,3)))
1220 static NTSTATUS find_tree_end(tree* t, KEY* tree_end, bool* no_end) {
1221  tree* p;
1222 
1223  p = t;
1224  do {
1225  tree_data* pi;
1226 
1227  if (!p->parent) {
1228  tree_end->obj_id = 0xffffffffffffffff;
1229  tree_end->obj_type = 0xff;
1230  tree_end->offset = 0xffffffffffffffff;
1231  *no_end = true;
1232  return STATUS_SUCCESS;
1233  }
1234 
1235  pi = p->paritem;
1236 
1237  if (pi->list_entry.Flink != &p->parent->itemlist) {
1238  tree_data* td = CONTAINING_RECORD(pi->list_entry.Flink, tree_data, list_entry);
1239 
1240  *tree_end = td->key;
1241  *no_end = false;
1242  return STATUS_SUCCESS;
1243  }
1244 
1245  p = p->parent;
1246  } while (p);
1247 
1248  return STATUS_INTERNAL_ERROR;
1249 }
1250 
1251 __attribute__((nonnull(1,2)))
1253  while (!IsListEmpty(batchlist)) {
1254  LIST_ENTRY* le = RemoveHeadList(batchlist);
1256 
1257  while (!IsListEmpty(&br->items)) {
1258  LIST_ENTRY* le2 = RemoveHeadList(&br->items);
1260 
1261  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
1262  }
1263 
1264  ExFreePool(br);
1265  }
1266 }
1267 
1268 __attribute__((nonnull(1,2,3)))
1269 static void add_delete_inode_extref(device_extension* Vcb, batch_item* bi, LIST_ENTRY* listhead) {
1270  batch_item* bi2;
1271  LIST_ENTRY* le;
1272  INODE_REF* delir = (INODE_REF*)bi->data;
1273  INODE_EXTREF* ier;
1274 
1275  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1276 
1277  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1278  if (!bi2) {
1279  ERR("out of memory\n");
1280  return;
1281  }
1282 
1283  ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + delir->n, ALLOC_TAG);
1284  if (!ier) {
1285  ERR("out of memory\n");
1286  ExFreePool(bi2);
1287  return;
1288  }
1289 
1290  ier->dir = bi->key.offset;
1291  ier->index = delir->index;
1292  ier->n = delir->n;
1293  RtlCopyMemory(ier->name, delir->name, delir->n);
1294 
1295  bi2->key.obj_id = bi->key.obj_id;
1297  bi2->key.offset = calc_crc32c((uint32_t)bi->key.offset, (uint8_t*)ier->name, ier->n);
1298  bi2->data = ier;
1299  bi2->datalen = sizeof(INODE_EXTREF) - 1 + ier->n;
1301 
1302  le = bi->list_entry.Flink;
1303  while (le != listhead) {
1305 
1306  if (keycmp(bi3->key, bi2->key) != -1) {
1307  InsertHeadList(le->Blink, &bi2->list_entry);
1308  return;
1309  }
1310 
1311  le = le->Flink;
1312  }
1313 
1314  InsertTailList(listhead, &bi2->list_entry);
1315 }
1316 
1317 __attribute__((nonnull(1,2,3,4,6,7)))
1318 static NTSTATUS handle_batch_collision(device_extension* Vcb, batch_item* bi, tree* t, tree_data* td, tree_data* newtd, LIST_ENTRY* listhead, bool* ignore) {
1319  if (bi->operation == Batch_Delete || bi->operation == Batch_SetXattr || bi->operation == Batch_DirItem || bi->operation == Batch_InodeRef ||
1320  bi->operation == Batch_InodeExtRef || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
1321  bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) {
1322  uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
1323 
1324  switch (bi->operation) {
1325  case Batch_SetXattr: {
1326  if (td->size < sizeof(DIR_ITEM)) {
1327  ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %Iu\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset, td->size, sizeof(DIR_ITEM));
1328  } else {
1329  uint8_t* newdata;
1330  ULONG size = td->size;
1331  DIR_ITEM* newxa = (DIR_ITEM*)bi->data;
1332  DIR_ITEM* xa = (DIR_ITEM*)td->data;
1333 
1334  while (true) {
1335  ULONG oldxasize;
1336 
1337  if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
1338  ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1339  break;
1340  }
1341 
1342  oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;
1343 
1344  if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) {
1345  uint64_t pos;
1346 
1347  // replace
1348 
1349  if (td->size + bi->datalen - oldxasize > maxlen)
1350  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->size, bi->datalen, oldxasize, maxlen);
1351 
1352  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG);
1353  if (!newdata) {
1354  ERR("out of memory\n");
1356  }
1357 
1358  pos = (uint8_t*)xa - td->data;
1359  if (pos + oldxasize < td->size) // copy after changed xattr
1360  RtlCopyMemory(newdata + pos + bi->datalen, td->data + pos + oldxasize, (ULONG)(td->size - pos - oldxasize));
1361 
1362  if (pos > 0) { // copy before changed xattr
1363  RtlCopyMemory(newdata, td->data, (ULONG)pos);
1364  xa = (DIR_ITEM*)(newdata + pos);
1365  } else
1366  xa = (DIR_ITEM*)newdata;
1367 
1368  RtlCopyMemory(xa, bi->data, bi->datalen);
1369 
1370  bi->datalen = (uint16_t)min(td->size + bi->datalen - oldxasize, maxlen);
1371 
1372  ExFreePool(bi->data);
1373  bi->data = newdata;
1374 
1375  break;
1376  }
1377 
1378  if ((uint8_t*)xa - (uint8_t*)td->data + oldxasize >= size) {
1379  // not found, add to end of data
1380 
1381  if (td->size + bi->datalen > maxlen)
1382  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1383 
1384  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1385  if (!newdata) {
1386  ERR("out of memory\n");
1388  }
1389 
1390  RtlCopyMemory(newdata, td->data, td->size);
1391 
1392  xa = (DIR_ITEM*)((uint8_t*)newdata + td->size);
1393  RtlCopyMemory(xa, bi->data, bi->datalen);
1394 
1395  bi->datalen = min(bi->datalen + td->size, maxlen);
1396 
1397  ExFreePool(bi->data);
1398  bi->data = newdata;
1399 
1400  break;
1401  } else {
1402  xa = (DIR_ITEM*)&xa->name[xa->m + xa->n];
1403  size -= oldxasize;
1404  }
1405  }
1406  }
1407  break;
1408  }
1409 
1410  case Batch_DirItem: {
1411  uint8_t* newdata;
1412 
1413  if (td->size + bi->datalen > maxlen) {
1414  ERR("DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1415  return STATUS_INTERNAL_ERROR;
1416  }
1417 
1418  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1419  if (!newdata) {
1420  ERR("out of memory\n");
1422  }
1423 
1424  RtlCopyMemory(newdata, td->data, td->size);
1425 
1426  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1427 
1428  bi->datalen += td->size;
1429 
1430  ExFreePool(bi->data);
1431  bi->data = newdata;
1432 
1433  break;
1434  }
1435 
1436  case Batch_InodeRef: {
1437  uint8_t* newdata;
1438 
1439  if (td->size + bi->datalen > maxlen) {
1440  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1441  INODE_REF* ir = (INODE_REF*)bi->data;
1442  INODE_EXTREF* ier;
1443  uint16_t ierlen;
1444  batch_item* bi2;
1445  LIST_ENTRY* le;
1446  bool inserted = false;
1447 
1448  TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n");
1449 
1450  ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n);
1451 
1452  ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG);
1453  if (!ier) {
1454  ERR("out of memory\n");
1456  }
1457 
1458  ier->dir = bi->key.offset;
1459  ier->index = ir->index;
1460  ier->n = ir->n;
1461  RtlCopyMemory(ier->name, ir->name, ier->n);
1462 
1463  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1464  if (!bi2) {
1465  ERR("out of memory\n");
1466  ExFreePool(ier);
1468  }
1469 
1470  bi2->key.obj_id = bi->key.obj_id;
1472  bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n);
1473  bi2->data = ier;
1474  bi2->datalen = ierlen;
1476 
1477  le = bi->list_entry.Flink;
1478  while (le != listhead) {
1480 
1481  if (keycmp(bi3->key, bi2->key) != -1) {
1482  InsertHeadList(le->Blink, &bi2->list_entry);
1483  inserted = true;
1484  }
1485 
1486  le = le->Flink;
1487  }
1488 
1489  if (!inserted)
1490  InsertTailList(listhead, &bi2->list_entry);
1491 
1492  *ignore = true;
1493  return STATUS_SUCCESS;
1494  } else {
1495  ERR("INODE_REF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1496  return STATUS_INTERNAL_ERROR;
1497  }
1498  }
1499 
1500  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1501  if (!newdata) {
1502  ERR("out of memory\n");
1504  }
1505 
1506  RtlCopyMemory(newdata, td->data, td->size);
1507 
1508  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1509 
1510  bi->datalen += td->size;
1511 
1512  ExFreePool(bi->data);
1513  bi->data = newdata;
1514 
1515  break;
1516  }
1517 
1518  case Batch_InodeExtRef: {
1519  uint8_t* newdata;
1520 
1521  if (td->size + bi->datalen > maxlen) {
1522  ERR("INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1523  return STATUS_INTERNAL_ERROR;
1524  }
1525 
1526  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1527  if (!newdata) {
1528  ERR("out of memory\n");
1530  }
1531 
1532  RtlCopyMemory(newdata, td->data, td->size);
1533 
1534  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1535 
1536  bi->datalen += td->size;
1537 
1538  ExFreePool(bi->data);
1539  bi->data = newdata;
1540 
1541  break;
1542  }
1543 
1544  case Batch_DeleteDirItem: {
1545  if (td->size < sizeof(DIR_ITEM)) {
1546  ERR("DIR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
1547  return STATUS_INTERNAL_ERROR;
1548  } else {
1549  DIR_ITEM *di, *deldi;
1550  LONG len;
1551 
1552  deldi = (DIR_ITEM*)bi->data;
1553  di = (DIR_ITEM*)td->data;
1554  len = td->size;
1555 
1556  do {
1557  if (di->m == deldi->m && di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n + di->m) == di->n + di->m) {
1558  uint16_t newlen = td->size - (sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m);
1559 
1560  if (newlen == 0) {
1561  TRACE("deleting DIR_ITEM\n");
1562  } else {
1563  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1564  tree_data* td2;
1565 
1566  if (!newdi) {
1567  ERR("out of memory\n");
1569  }
1570 
1571  TRACE("modifying DIR_ITEM\n");
1572 
1573  if ((uint8_t*)di > td->data) {
1574  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1575  dioff = newdi + ((uint8_t*)di - td->data);
1576  } else {
1577  dioff = newdi;
1578  }
1579 
1580  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1581  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1582 
1583  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1584  if (!td2) {
1585  ERR("out of memory\n");
1586  ExFreePool(newdi);
1588  }
1589 
1590  td2->key = bi->key;
1591  td2->size = newlen;
1592  td2->data = newdi;
1593  td2->ignore = false;
1594  td2->inserted = true;
1595 
1596  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1597 
1598  t->header.num_items++;
1599  t->size += newlen + sizeof(leaf_node);
1600  t->write = true;
1601  }
1602 
1603  break;
1604  }
1605 
1606  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1607  di = (DIR_ITEM*)&di->name[di->n + di->m];
1608 
1609  if (len == 0) {
1610  TRACE("could not find DIR_ITEM to delete\n");
1611  *ignore = true;
1612  return STATUS_SUCCESS;
1613  }
1614  } while (len > 0);
1615  }
1616  break;
1617  }
1618 
1619  case Batch_DeleteInodeRef: {
1620  if (td->size < sizeof(INODE_REF)) {
1621  ERR("INODE_REF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_REF));
1622  return STATUS_INTERNAL_ERROR;
1623  } else {
1624  INODE_REF *ir, *delir;
1625  ULONG len;
1626  bool changed = false;
1627 
1628  delir = (INODE_REF*)bi->data;
1629  ir = (INODE_REF*)td->data;
1630  len = td->size;
1631 
1632  do {
1633  uint16_t itemlen;
1634 
1635  if (len < sizeof(INODE_REF) || len < offsetof(INODE_REF, name[0]) + ir->n) {
1636  ERR("INODE_REF was truncated\n");
1637  break;
1638  }
1639 
1640  itemlen = (uint16_t)offsetof(INODE_REF, name[0]) + ir->n;
1641 
1642  if (ir->n == delir->n && RtlCompareMemory(ir->name, delir->name, ir->n) == ir->n) {
1643  uint16_t newlen = td->size - itemlen;
1644 
1645  changed = true;
1646 
1647  if (newlen == 0)
1648  TRACE("deleting INODE_REF\n");
1649  else {
1650  uint8_t *newir = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *iroff;
1651  tree_data* td2;
1652 
1653  if (!newir) {
1654  ERR("out of memory\n");
1656  }
1657 
1658  TRACE("modifying INODE_REF\n");
1659 
1660  if ((uint8_t*)ir > td->data) {
1661  RtlCopyMemory(newir, td->data, (uint8_t*)ir - td->data);
1662  iroff = newir + ((uint8_t*)ir - td->data);
1663  } else {
1664  iroff = newir;
1665  }
1666 
1667  if ((uint8_t*)&ir->name[ir->n] < td->data + td->size)
1668  RtlCopyMemory(iroff, &ir->name[ir->n], td->size - ((uint8_t*)&ir->name[ir->n] - td->data));
1669 
1670  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1671  if (!td2) {
1672  ERR("out of memory\n");
1673  ExFreePool(newir);
1675  }
1676 
1677  td2->key = bi->key;
1678  td2->size = newlen;
1679  td2->data = newir;
1680  td2->ignore = false;
1681  td2->inserted = true;
1682 
1683  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1684 
1685  t->header.num_items++;
1686  t->size += newlen + sizeof(leaf_node);
1687  t->write = true;
1688  }
1689 
1690  break;
1691  }
1692 
1693  if (len > itemlen) {
1694  len -= itemlen;
1695  ir = (INODE_REF*)&ir->name[ir->n];
1696  } else
1697  break;
1698  } while (len > 0);
1699 
1700  if (!changed) {
1701  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1702  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1703 
1704  add_delete_inode_extref(Vcb, bi, listhead);
1705 
1706  *ignore = true;
1707  return STATUS_SUCCESS;
1708  } else
1709  WARN("entry not found in INODE_REF\n");
1710  }
1711  }
1712 
1713  break;
1714  }
1715 
1716  case Batch_DeleteInodeExtRef: {
1717  if (td->size < sizeof(INODE_EXTREF)) {
1718  ERR("INODE_EXTREF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_EXTREF));
1719  return STATUS_INTERNAL_ERROR;
1720  } else {
1721  INODE_EXTREF *ier, *delier;
1722  ULONG len;
1723 
1724  delier = (INODE_EXTREF*)bi->data;
1725  ier = (INODE_EXTREF*)td->data;
1726  len = td->size;
1727 
1728  do {
1729  uint16_t itemlen;
1730 
1731  if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) {
1732  ERR("INODE_REF was truncated\n");
1733  break;
1734  }
1735 
1736  itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n;
1737 
1738  if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) {
1739  uint16_t newlen = td->size - itemlen;
1740 
1741  if (newlen == 0)
1742  TRACE("deleting INODE_EXTREF\n");
1743  else {
1744  uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff;
1745  tree_data* td2;
1746 
1747  if (!newier) {
1748  ERR("out of memory\n");
1750  }
1751 
1752  TRACE("modifying INODE_EXTREF\n");
1753 
1754  if ((uint8_t*)ier > td->data) {
1755  RtlCopyMemory(newier, td->data, (uint8_t*)ier - td->data);
1756  ieroff = newier + ((uint8_t*)ier - td->data);
1757  } else {
1758  ieroff = newier;
1759  }
1760 
1761  if ((uint8_t*)&ier->name[ier->n] < td->data + td->size)
1762  RtlCopyMemory(ieroff, &ier->name[ier->n], td->size - ((uint8_t*)&ier->name[ier->n] - td->data));
1763 
1764  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1765  if (!td2) {
1766  ERR("out of memory\n");
1767  ExFreePool(newier);
1769  }
1770 
1771  td2->key = bi->key;
1772  td2->size = newlen;
1773  td2->data = newier;
1774  td2->ignore = false;
1775  td2->inserted = true;
1776 
1777  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1778 
1779  t->header.num_items++;
1780  t->size += newlen + sizeof(leaf_node);
1781  t->write = true;
1782  }
1783 
1784  break;
1785  }
1786 
1787  if (len > itemlen) {
1788  len -= itemlen;
1789  ier = (INODE_EXTREF*)&ier->name[ier->n];
1790  } else
1791  break;
1792  } while (len > 0);
1793  }
1794  break;
1795  }
1796 
1797  case Batch_DeleteXattr: {
1798  if (td->size < sizeof(DIR_ITEM)) {
1799  ERR("XATTR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
1800  return STATUS_INTERNAL_ERROR;
1801  } else {
1802  DIR_ITEM *di, *deldi;
1803  LONG len;
1804 
1805  deldi = (DIR_ITEM*)bi->data;
1806  di = (DIR_ITEM*)td->data;
1807  len = td->size;
1808 
1809  do {
1810  if (di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n) == di->n) {
1811  uint16_t newlen = td->size - ((uint16_t)offsetof(DIR_ITEM, name[0]) + di->n + di->m);
1812 
1813  if (newlen == 0)
1814  TRACE("deleting XATTR_ITEM\n");
1815  else {
1816  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1817  tree_data* td2;
1818 
1819  if (!newdi) {
1820  ERR("out of memory\n");
1822  }
1823 
1824  TRACE("modifying XATTR_ITEM\n");
1825 
1826  if ((uint8_t*)di > td->data) {
1827  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1828  dioff = newdi + ((uint8_t*)di - td->data);
1829  } else
1830  dioff = newdi;
1831 
1832  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1833  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1834 
1835  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1836  if (!td2) {
1837  ERR("out of memory\n");
1838  ExFreePool(newdi);
1840  }
1841 
1842  td2->key = bi->key;
1843  td2->size = newlen;
1844  td2->data = newdi;
1845  td2->ignore = false;
1846  td2->inserted = true;
1847 
1848  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1849 
1850  t->header.num_items++;
1851  t->size += newlen + sizeof(leaf_node);
1852  t->write = true;
1853  }
1854 
1855  break;
1856  }
1857 
1858  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1859  di = (DIR_ITEM*)&di->name[di->n + di->m];
1860 
1861  if (len == 0) {
1862  TRACE("could not find DIR_ITEM to delete\n");
1863  *ignore = true;
1864  return STATUS_SUCCESS;
1865  }
1866  } while (len > 0);
1867  }
1868  break;
1869  }
1870 
1871  case Batch_Delete:
1872  break;
1873 
1874  default:
1875  ERR("unexpected batch operation type\n");
1876  return STATUS_INTERNAL_ERROR;
1877  }
1878 
1879  // delete old item
1880  if (!td->ignore) {
1881  td->ignore = true;
1882 
1883  t->header.num_items--;
1884  t->size -= sizeof(leaf_node) + td->size;
1885  t->write = true;
1886  }
1887 
1888  if (newtd) {
1889  newtd->data = bi->data;
1890  newtd->size = bi->datalen;
1891  InsertHeadList(td->list_entry.Blink, &newtd->list_entry);
1892  }
1893  } else {
1894  ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1895  return STATUS_INTERNAL_ERROR;
1896  }
1897 
1898  *ignore = false;
1899  return STATUS_SUCCESS;
1900 }
1901 
1902 __attribute__((nonnull(1,2)))
1903 static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, batch_root* br, PIRP Irp) {
1904  LIST_ENTRY* le;
1905  NTSTATUS Status;
1906 
1907  TRACE("root: %I64x\n", br->r->id);
1908 
1909  le = br->items.Flink;
1910  while (le != &br->items) {
1912  LIST_ENTRY *le2;
1913  traverse_ptr tp;
1914  KEY tree_end;
1915  bool no_end;
1916  tree_data *td, *listhead;
1917  int cmp;
1918  tree* t;
1919  bool ignore = false;
1920 
1921  TRACE("(%I64x,%x,%I64x)\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1922 
1923  Status = find_item(Vcb, br->r, &tp, &bi->key, true, Irp);
1924  if (!NT_SUCCESS(Status)) { // FIXME - handle STATUS_NOT_FOUND
1925  ERR("find_item returned %08lx\n", Status);
1926  return Status;
1927  }
1928 
1929  Status = find_tree_end(tp.tree, &tree_end, &no_end);
1930  if (!NT_SUCCESS(Status)) {
1931  ERR("find_tree_end returned %08lx\n", Status);
1932  return Status;
1933  }
1934 
1935  if (bi->operation == Batch_DeleteInode) {
1936  if (tp.item->key.obj_id == bi->key.obj_id) {
1937  bool ended = false;
1938 
1939  td = tp.item;
1940 
1941  if (!tp.item->ignore) {
1942  tp.item->ignore = true;
1943  tp.tree->header.num_items--;
1944  tp.tree->size -= tp.item->size + sizeof(leaf_node);
1945  tp.tree->write = true;
1946  }
1947 
1948  le2 = tp.item->list_entry.Flink;
1949  while (le2 != &tp.tree->itemlist) {
1951 
1952  if (td->key.obj_id == bi->key.obj_id) {
1953  if (!td->ignore) {
1954  td->ignore = true;
1955  tp.tree->header.num_items--;
1956  tp.tree->size -= td->size + sizeof(leaf_node);
1957  tp.tree->write = true;
1958  }
1959  } else {
1960  ended = true;
1961  break;
1962  }
1963 
1964  le2 = le2->Flink;
1965  }
1966 
1967  while (!ended) {
1968  traverse_ptr next_tp;
1969 
1970  tp.item = td;
1971 
1972  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1973  break;
1974 
1975  tp = next_tp;
1976 
1977  le2 = &tp.item->list_entry;
1978  while (le2 != &tp.tree->itemlist) {
1980 
1981  if (td->key.obj_id == bi->key.obj_id) {
1982  if (!td->ignore) {
1983  td->ignore = true;
1984  tp.tree->header.num_items--;
1985  tp.tree->size -= td->size + sizeof(leaf_node);
1986  tp.tree->write = true;
1987  }
1988  } else {
1989  ended = true;
1990  break;
1991  }
1992 
1993  le2 = le2->Flink;
1994  }
1995  }
1996  }
1997  } else if (bi->operation == Batch_DeleteExtentData) {
1998  if (tp.item->key.obj_id < bi->key.obj_id || (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type < bi->key.obj_type)) {
1999  traverse_ptr tp2;
2000 
2001  if (find_next_item(Vcb, &tp, &tp2, false, Irp)) {
2002  if (tp2.item->key.obj_id == bi->key.obj_id && tp2.item->key.obj_type == bi->key.obj_type) {
2003  tp = tp2;
2004  Status = find_tree_end(tp.tree, &tree_end, &no_end);
2005  if (!NT_SUCCESS(Status)) {
2006  ERR("find_tree_end returned %08lx\n", Status);
2007  return Status;
2008  }
2009  }
2010  }
2011  }
2012 
2013  if (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type == bi->key.obj_type) {
2014  bool ended = false;
2015 
2016  td = tp.item;
2017 
2018  if (!tp.item->ignore) {
2019  tp.item->ignore = true;
2020  tp.tree->header.num_items--;
2021  tp.tree->size -= tp.item->size + sizeof(leaf_node);
2022  tp.tree->write = true;
2023  }
2024 
2025  le2 = tp.item->list_entry.Flink;
2026  while (le2 != &tp.tree->itemlist) {
2028 
2029  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2030  if (!td->ignore) {
2031  td->ignore = true;
2032  tp.tree->header.num_items--;
2033  tp.tree->size -= td->size + sizeof(leaf_node);
2034  tp.tree->write = true;
2035  }
2036  } else {
2037  ended = true;
2038  break;
2039  }
2040 
2041  le2 = le2->Flink;
2042  }
2043 
2044  while (!ended) {
2045  traverse_ptr next_tp;
2046 
2047  tp.item = td;
2048 
2049  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2050  break;
2051 
2052  tp = next_tp;
2053 
2054  le2 = &tp.item->list_entry;
2055  while (le2 != &tp.tree->itemlist) {
2057 
2058  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2059  if (!td->ignore) {
2060  td->ignore = true;
2061  tp.tree->header.num_items--;
2062  tp.tree->size -= td->size + sizeof(leaf_node);
2063  tp.tree->write = true;
2064  }
2065  } else {
2066  ended = true;
2067  break;
2068  }
2069 
2070  le2 = le2->Flink;
2071  }
2072  }
2073  }
2074  } else if (bi->operation == Batch_DeleteFreeSpace) {
2075  if (tp.item->key.obj_id >= bi->key.obj_id && tp.item->key.obj_id < bi->key.obj_id + bi->key.offset) {
2076  bool ended = false;
2077 
2078  td = tp.item;
2079 
2080  if (!tp.item->ignore) {
2081  tp.item->ignore = true;
2082  tp.tree->header.num_items--;
2083  tp.tree->size -= tp.item->size + sizeof(leaf_node);
2084  tp.tree->write = true;
2085  }
2086 
2087  le2 = tp.item->list_entry.Flink;
2088  while (le2 != &tp.tree->itemlist) {
2090 
2091  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2092  if (!td->ignore) {
2093  td->ignore = true;
2094  tp.tree->header.num_items--;
2095  tp.tree->size -= td->size + sizeof(leaf_node);
2096  tp.tree->write = true;
2097  }
2098  } else {
2099  ended = true;
2100  break;
2101  }
2102 
2103  le2 = le2->Flink;
2104  }
2105 
2106  while (!ended) {
2107  traverse_ptr next_tp;
2108 
2109  tp.item = td;
2110 
2111  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2112  break;
2113 
2114  tp = next_tp;
2115 
2116  le2 = &tp.item->list_entry;
2117  while (le2 != &tp.tree->itemlist) {
2119 
2120  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2121  if (!td->ignore) {
2122  td->ignore = true;
2123  tp.tree->header.num_items--;
2124  tp.tree->size -= td->size + sizeof(leaf_node);
2125  tp.tree->write = true;
2126  }
2127  } else {
2128  ended = true;
2129  break;
2130  }
2131 
2132  le2 = le2->Flink;
2133  }
2134  }
2135  }
2136  } else {
2139  td = NULL;
2140  else {
2141  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2142  if (!td) {
2143  ERR("out of memory\n");
2145  }
2146 
2147  td->key = bi->key;
2148  td->size = bi->datalen;
2149  td->data = bi->data;
2150  td->ignore = false;
2151  td->inserted = true;
2152  }
2153 
2154  cmp = keycmp(bi->key, tp.item->key);
2155 
2156  if (cmp == -1) { // very first key in root
2157  if (td) {
2158  tree_data* paritem;
2159 
2161 
2162  paritem = tp.tree->paritem;
2163  while (paritem) {
2164  if (!keycmp(paritem->key, tp.item->key)) {
2165  paritem->key = bi->key;
2166  } else
2167  break;
2168 
2169  paritem = paritem->treeholder.tree->paritem;
2170  }
2171  }
2172  } else if (cmp == 0) { // item already exists
2173  if (tp.item->ignore) {
2174  if (td)
2176  } else {
2177  Status = handle_batch_collision(Vcb, bi, tp.tree, tp.item, td, &br->items, &ignore);
2178  if (!NT_SUCCESS(Status)) {
2179  ERR("handle_batch_collision returned %08lx\n", Status);
2180 #ifdef _DEBUG
2181  int3;
2182 #endif
2183 
2184  if (td)
2185  ExFreeToPagedLookasideList(&Vcb->tree_data_lookaside, td);
2186 
2187  return Status;
2188  }
2189  }
2190  } else if (td) {
2192  }
2193 
2194  if (bi->operation == Batch_DeleteInodeRef && cmp != 0 && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2195  add_delete_inode_extref(Vcb, bi, &br->items);
2196  }
2197 
2198  if (!ignore && td) {
2199  tp.tree->header.num_items++;
2200  tp.tree->size += bi->datalen + sizeof(leaf_node);
2201  tp.tree->write = true;
2202 
2203  listhead = td;
2204  } else
2205  listhead = tp.item;
2206 
2207  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2209 
2210  if (!keycmp(prevtd->key, listhead->key))
2211  listhead = prevtd;
2212  else
2213  break;
2214  }
2215 
2216  le2 = le->Flink;
2217  while (le2 != &br->items) {
2219 
2221  break;
2222 
2223  if (no_end || keycmp(bi2->key, tree_end) == -1) {
2224  LIST_ENTRY* le3;
2225  bool inserted = false;
2226 
2227  ignore = false;
2228 
2231  td = NULL;
2232  else {
2233  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2234  if (!td) {
2235  ERR("out of memory\n");
2237  }
2238 
2239  td->key = bi2->key;
2240  td->size = bi2->datalen;
2241  td->data = bi2->data;
2242  td->ignore = false;
2243  td->inserted = true;
2244  }
2245 
2246  le3 = &listhead->list_entry;
2247  while (le3 != &tp.tree->itemlist) {
2249 
2250  cmp = keycmp(bi2->key, td2->key);
2251 
2252  if (cmp == 0) {
2253  if (td2->ignore) {
2254  if (td) {
2255  InsertHeadList(le3->Blink, &td->list_entry);
2256  inserted = true;
2257  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2258  add_delete_inode_extref(Vcb, bi2, &br->items);
2259  }
2260  } else {
2261  Status = handle_batch_collision(Vcb, bi2, tp.tree, td2, td, &br->items, &ignore);
2262  if (!NT_SUCCESS(Status)) {
2263  ERR("handle_batch_collision returned %08lx\n", Status);
2264 #ifdef _DEBUG
2265  int3;
2266 #endif
2267  return Status;
2268  }
2269  }
2270 
2271  inserted = true;
2272  break;
2273  } else if (cmp == -1) {
2274  if (td) {
2275  InsertHeadList(le3->Blink, &td->list_entry);
2276  inserted = true;
2277  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2278  add_delete_inode_extref(Vcb, bi2, &br->items);
2279  }
2280  break;
2281  }
2282 
2283  le3 = le3->Flink;
2284  }
2285 
2286  if (td) {
2287  if (!inserted)
2289 
2290  if (!ignore) {
2291  tp.tree->header.num_items++;
2292  tp.tree->size += bi2->datalen + sizeof(leaf_node);
2293 
2294  listhead = td;
2295  }
2296  } else if (!inserted && bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2297  add_delete_inode_extref(Vcb, bi2, &br->items);
2298  }
2299 
2300  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2302 
2303  if (!keycmp(prevtd->key, listhead->key))
2304  listhead = prevtd;
2305  else
2306  break;
2307  }
2308 
2309  le = le2;
2310  } else
2311  break;
2312 
2313  le2 = le2->Flink;
2314  }
2315 
2316  t = tp.tree;
2317  while (t) {
2318  if (t->paritem && t->paritem->ignore) {
2319  t->paritem->ignore = false;
2320  t->parent->header.num_items++;
2321  t->parent->size += sizeof(internal_node);
2322  }
2323 
2324  t->header.generation = Vcb->superblock.generation;
2325  t = t->parent;
2326  }
2327  }
2328 
2329  le = le->Flink;
2330  }
2331 
2332  // FIXME - remove as we are going along
2333  while (!IsListEmpty(&br->items)) {
2335 
2338  ExFreePool(bi->data);
2339 
2340  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
2341  }
2342 
2343  return STATUS_SUCCESS;
2344 }
2345 
2346 __attribute__((nonnull(1,2)))
2348  NTSTATUS Status;
2349 
2350  while (!IsListEmpty(batchlist)) {
2351  LIST_ENTRY* le = RemoveHeadList(batchlist);
2353 
2354  Status = commit_batch_list_root(Vcb, br2, Irp);
2355  if (!NT_SUCCESS(Status)) {
2356  ERR("commit_batch_list_root returned %08lx\n", Status);
2357  return Status;
2358  }
2359 
2360  ExFreePool(br2);
2361  }
2362 
2363  return STATUS_SUCCESS;
2364 }
LIST_ENTRY * list_size
Definition: btrfs_drv.h:1247
LIST_ENTRY list_entry
Definition: btrfs_drv.h:491
while(CdLookupNextInitialFileDirent(IrpContext, Fcb, FileContext))
uint64_t obj_id
Definition: btrfs.h:144
GLint level
Definition: gl.h:1546
struct _root * root
Definition: btrfs_drv.h:433
return
Definition: dirsup.c:529
uint8_t type
Definition: btrfs.h:363
uint8_t obj_type
Definition: btrfs.h:145
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
NTSTATUS update_changed_extent_ref(device_extension *Vcb, chunk *c, uint64_t address, uint64_t size, uint64_t root, uint64_t objid, uint64_t offset, int32_t count, bool no_csum, bool superseded, PIRP Irp)
Definition: extent-tree.c:1951
#define _In_opt_
Definition: ms_sal.h:309
uint16_t n
Definition: btrfs.h:383
#define _Inout_
Definition: ms_sal.h:378
#define _Out_
Definition: ms_sal.h:345
enum rollback_type type
Definition: btrfs_drv.h:1266
#define pt(x, y)
Definition: drawing.c:79
bool inserted
Definition: btrfs_drv.h:408
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
FORCEINLINE VOID InsertHeadList(_Inout_ PLIST_ENTRY ListHead, _Inout_ __drv_aliasesMem PLIST_ENTRY Entry)
Definition: rtlfuncs.h:201
uint64_t decoded_size
Definition: btrfs.h:359
#define BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF
Definition: btrfs.h:121
FORCEINLINE PLIST_ENTRY RemoveTailList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:154
#define keycmp(key1, key2)
Definition: btrfs_drv.h:1008
#define WARN(fmt,...)
Definition: debug.h:112
LONG NTSTATUS
Definition: precomp.h:26
void reap_fcbs(device_extension *Vcb)
Definition: btrfs.c:1810
#define int3
Definition: btrfs_drv.h:1735
tree_holder treeholder
Definition: btrfs_drv.h:411
uint16_t size
Definition: btrfs_drv.h:414
LIST_ENTRY list_entry_hash
Definition: btrfs_drv.h:436
enum batch_operation operation
Definition: btrfs_drv.h:490
GLdouble GLdouble t
Definition: gl.h:2047
uint64_t used
Definition: btrfs_drv.h:558
#define _When_(expr, annos)
Definition: ms_sal.h:254
unsigned short int uint16_t
Definition: acefiex.h:54
#define uint16_t
Definition: nsiface.idl:60
#define cmp(status, error)
Definition: error.c:114
#define InsertTailList(ListHead, Entry)
uint32_t flags
Definition: btrfs.h:297
NTSTATUS NTSTATUS bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *next_tp, bool ignore, PIRP Irp) __attribute__((nonnull(1
#define _Requires_exclusive_lock_held_(lock)
if(dx==0 &&dy==0)
Definition: linetemp.h:174
_Must_inspect_result_ FORCEINLINE BOOLEAN IsListEmpty(_In_ const LIST_ENTRY *ListHead)
Definition: rtlfuncs.h:57
uint64_t offset
Definition: btrfs.h:146
VOID FASTCALL ExReleaseFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:31
uint8_t * data
Definition: btrfs_drv.h:415
IMAGE_NT_HEADERS nt
Definition: module.c:50
bool ignore
Definition: btrfs_drv.h:231
NTSTATUS NTSTATUS void free_tree(tree *t) __attribute__((nonnull(1)))
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
void * data
Definition: btrfs_drv.h:488
uint64_t length
Definition: btrfs_drv.h:1249
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
BOOLEAN NTAPI ExAcquireResourceExclusiveLite(IN PERESOURCE Resource, IN BOOLEAN Wait)
Definition: resource.c:770
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:465
#define ALLOC_TAG
Definition: btrfs_drv.h:87
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
LIST_ENTRY list_entry
Definition: btrfs_drv.h:406
#define EXTENT_TYPE_INLINE
Definition: btrfs.h:74
struct _device_extension * Vcb
Definition: btrfs_drv.h:430
uint64_t address
Definition: btrfs.h:156
uint16_t m
Definition: btrfs.h:275
tree * tree
Definition: btrfs_drv.h:501
chunk * chunk
Definition: btrfs_drv.h:1250
_In_ PIRP Irp
Definition: csq.h:116
LIST_ENTRY items
Definition: btrfs_drv.h:496
uint64_t address
Definition: btrfs.h:368
struct _tree * tree
Definition: btrfs_drv.h:401
long LONG
Definition: pedump.c:60
uint64_t address
Definition: btrfs_drv.h:1248
uint64_t offset
Definition: btrfs_drv.h:228
void void void NTSTATUS void NTSTATUS skip_to_difference(device_extension *Vcb, traverse_ptr *tp, traverse_ptr *tp2, bool *ended1, bool *ended2) __attribute__((nonnull(1
NTSTATUS NTSTATUS bool bool find_prev_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *prev_tp, PIRP Irp) __attribute__((nonnull(1
static PVOID ptr
Definition: dispmode.c:27
#define __drv_aliasesMem
Definition: btrfs_drv.h:203
uint64_t generation
Definition: btrfs.h:159
tree_data * paritem
Definition: btrfs_drv.h:432
char name[1]
Definition: btrfs.h:377
char name[1]
Definition: btrfs.h:278
#define offsetof(TYPE, MEMBER)
#define _In_
Definition: ms_sal.h:308
FORCEINLINE PLIST_ENTRY RemoveHeadList(_Inout_ PLIST_ENTRY ListHead)
Definition: rtlfuncs.h:128
#define release_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1132
struct _tree * parent
Definition: btrfs_drv.h:431
uint64_t size
Definition: btrfs.h:369
uint32_t size
Definition: btrfs.h:168
NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _In_ uint64_t obj_id, _In_ uint8_t obj_type, _In_ uint64_t offset, _In_reads_bytes_opt_(size) _When_(return >=0, __drv_aliasesMem) void *data, _In_ uint16_t size, _Out_opt_ traverse_ptr *ptp, _In_opt_ PIRP Irp) __attribute__((nonnull(1
uint16_t n
Definition: btrfs.h:376
uint32_t hash
Definition: btrfs_drv.h:427
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
#define b
Definition: ke_i.h:79
typedef bool(CARDLIBPROC *pCanDragProc)(CardRegion &stackobj
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2965
Status
Definition: gdiplustypes.h:24
void void void NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp) __attribute__((nonnull(1
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
#define STATUS_NOT_FOUND
Definition: shellext.h:72
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
LIST_ENTRY list_entry
Definition: btrfs_drv.h:1268
#define TRACE(s)
Definition: solgame.cpp:4
GLsizeiptr size
Definition: glext.h:5919
void reap_filerefs(device_extension *Vcb, file_ref *fr)
Definition: btrfs.c:1875
NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _Out_ traverse_ptr *tp, _In_ const KEY *searchkey, _In_ bool ignore, _In_opt_ PIRP Irp) __attribute__((nonnull(1
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
static refpint_t pi[]
Definition: server.c:96
uint64_t inode
Definition: btrfs_drv.h:289
GLintptr offset
Definition: glext.h:5920
LIST_ENTRY itemlist
Definition: btrfs_drv.h:434
#define BTRFS_INODE_NODATASUM
Definition: propsheet.h:76
FORCEINLINE VOID ExInitializeFastMutex(_Out_ PFAST_MUTEX FastMutex)
Definition: exfuncs.h:274
#define Vcb
Definition: cdprocs.h:1415
rollback_type
Definition: btrfs_drv.h:1258
const GLubyte * c
Definition: glext.h:8905
NTSTATUS NTSTATUS void clear_rollback(LIST_ENTRY *rollback) __attribute__((nonnull(1)))
uint8_t level
Definition: btrfs.h:162
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1817
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
tree_data * item
Definition: btrfs_drv.h:502
NTSTATUS NTSTATUS find_item_to_level(device_extension *Vcb, root *r, traverse_ptr *tp, const KEY *searchkey, bool ignore, uint8_t level, PIRP Irp) __attribute__((nonnull(1
NTSTATUS NTSTATUS do_load_tree(device_extension *Vcb, tree_holder *th, root *r, tree *t, tree_data *td, PIRP Irp) __attribute__((nonnull(1
GLenum const GLvoid * addr
Definition: glext.h:9621
tree_header header
Definition: btrfs_drv.h:426
#define TYPE_INODE_EXTREF
Definition: btrfs.h:25
GLenum GLsizei len
Definition: glext.h:6722
crc_func calc_crc32c
Definition: crc32c.c:23
Definition: typedefs.h:119
void do_rollback(device_extension *Vcb, LIST_ENTRY *rollback) __attribute__((nonnull(1
#define EXTENT_TYPE_PREALLOC
Definition: btrfs.h:76
INODE_ITEM inode_item
Definition: btrfs_drv.h:292
BYTE uint8_t
Definition: msvideo1.c:66
uint64_t num_bytes
Definition: btrfs.h:371
uint64_t dir
Definition: btrfs.h:381
uint64_t st_blocks
Definition: btrfs.h:290
#define EXTENT_TYPE_REGULAR
Definition: btrfs.h:75
char name[1]
Definition: btrfs.h:384
NTSTATUS NTSTATUS bool bool void free_trees(device_extension *Vcb) __attribute__((nonnull(1)))
#define ERR(fmt,...)
Definition: debug.h:110
uint8_t data[1]
Definition: btrfs.h:364
bool ignore
Definition: btrfs_drv.h:407
uint32_t size
Definition: btrfs_drv.h:429
extent * ext
Definition: btrfs_drv.h:1255
Definition: btrfs.h:143
void void void add_rollback(_In_ LIST_ENTRY *rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void *ptr) __attribute__((nonnull(1
#define _Requires_lock_held_(lock)
static unsigned __int64 next
Definition: rand_nt.c:6
NTSTATUS load_tree(device_extension *Vcb, uint64_t addr, uint8_t *buf, root *r, tree **pt) __attribute__((nonnull(1
UINT64 uint64_t
Definition: types.h:77
GLuint in
Definition: glext.h:9616
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
VOID FASTCALL ExAcquireFastMutex(IN PFAST_MUTEX FastMutex)
Definition: fmutex.c:23
void space_list_subtract2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:2155
#define acquire_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1131
KEY key
Definition: btrfs.h:166
uint64_t index
Definition: btrfs.h:375
NTSTATUS NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp) __attribute__((nonnull(1
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
#define _Out_opt_
Definition: ms_sal.h:346
struct _root * subvol
Definition: btrfs_drv.h:288
#define min(a, b)
Definition: monoChain.cc:55
Definition: list.h:27
#define NULL
Definition: types.h:112
_In_ fcb _In_ chunk _In_ uint64_t _In_ uint64_t _In_ bool _In_opt_ void _In_opt_ PIRP _In_ LIST_ENTRY * rollback
Definition: btrfs_drv.h:1355
__attribute__((nonnull(1, 3, 4, 5)))
Definition: treefuncs.c:21
BOOL empty
Definition: button.c:170
uint64_t address
Definition: btrfs_drv.h:399
UINT32 uint32_t
Definition: types.h:75
void void free_trees_root(device_extension *Vcb, root *r) __attribute__((nonnull(1
void void void NTSTATUS void clear_batch_list(device_extension *Vcb, LIST_ENTRY *batchlist) __attribute__((nonnull(1
EXTENT_DATA extent_data
Definition: btrfs_drv.h:237
#define _In_reads_bytes_opt_(size)
Definition: ms_sal.h:322
Definition: name.c:38
static BOOL read_data(struct request *request, void *buffer, DWORD size, DWORD *read, BOOL async)
Definition: request.c:2018
#define c
Definition: ke_i.h:80
unsigned int ULONG
Definition: retypes.h:1
#define const
Definition: zconf.h:230
uint32_t num_items
Definition: btrfs.h:161
uint16_t datalen
Definition: btrfs_drv.h:489
LIST_ENTRY * list
Definition: btrfs_drv.h:1246
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
uint64_t offset
Definition: btrfs.h:370
#define STATUS_SUCCESS
Definition: shellext.h:65
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
GLfloat GLfloat p
Definition: glext.h:8902
uint16_t n
Definition: btrfs.h:276
bool write
Definition: btrfs_drv.h:440
void space_list_add2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:1446
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
#define RtlCompareMemory(s1, s2, l)
Definition: env_spec_w32.h:465
NTSTATUS NTSTATUS NTSTATUS NTSTATUS NTSTATUS chunk * get_chunk_from_address(device_extension *Vcb, uint64_t address) __attribute__((nonnull(1)))
LARGE_INTEGER li
Definition: fxtimerapi.cpp:235
uint64_t generation
Definition: btrfs_drv.h:400