ReactOS  0.4.15-dev-5606-gf34e425
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_ind)) {
1259 
1260  while (!IsListEmpty(&bii->items)) {
1262 
1263  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
1264  }
1265 
1266  ExFreePool(bii);
1267  }
1268 
1269  ExFreePool(br);
1270  }
1271 }
1272 
1273 __attribute__((nonnull(1,2,3)))
1274 static void add_delete_inode_extref(device_extension* Vcb, batch_item* bi, LIST_ENTRY* listhead) {
1275  batch_item* bi2;
1276  LIST_ENTRY* le;
1277  INODE_REF* delir = (INODE_REF*)bi->data;
1278  INODE_EXTREF* ier;
1279 
1280  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1281 
1282  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1283  if (!bi2) {
1284  ERR("out of memory\n");
1285  return;
1286  }
1287 
1288  ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + delir->n, ALLOC_TAG);
1289  if (!ier) {
1290  ERR("out of memory\n");
1291  ExFreePool(bi2);
1292  return;
1293  }
1294 
1295  ier->dir = bi->key.offset;
1296  ier->index = delir->index;
1297  ier->n = delir->n;
1298  RtlCopyMemory(ier->name, delir->name, delir->n);
1299 
1300  bi2->key.obj_id = bi->key.obj_id;
1302  bi2->key.offset = calc_crc32c((uint32_t)bi->key.offset, (uint8_t*)ier->name, ier->n);
1303  bi2->data = ier;
1304  bi2->datalen = sizeof(INODE_EXTREF) - 1 + ier->n;
1306 
1307  le = bi->list_entry.Flink;
1308  while (le != listhead) {
1310 
1311  if (keycmp(bi3->key, bi2->key) != -1) {
1312  InsertHeadList(le->Blink, &bi2->list_entry);
1313  return;
1314  }
1315 
1316  le = le->Flink;
1317  }
1318 
1319  InsertTailList(listhead, &bi2->list_entry);
1320 }
1321 
1322 __attribute__((nonnull(1,2,3,4,6,7)))
1323 static NTSTATUS handle_batch_collision(device_extension* Vcb, batch_item* bi, tree* t, tree_data* td, tree_data* newtd, LIST_ENTRY* listhead, bool* ignore) {
1324  if (bi->operation == Batch_Delete || bi->operation == Batch_SetXattr || bi->operation == Batch_DirItem || bi->operation == Batch_InodeRef ||
1325  bi->operation == Batch_InodeExtRef || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
1326  bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) {
1327  uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
1328 
1329  switch (bi->operation) {
1330  case Batch_SetXattr: {
1331  if (td->size < sizeof(DIR_ITEM)) {
1332  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));
1333  } else {
1334  uint8_t* newdata;
1335  ULONG size = td->size;
1336  DIR_ITEM* newxa = (DIR_ITEM*)bi->data;
1337  DIR_ITEM* xa = (DIR_ITEM*)td->data;
1338 
1339  while (true) {
1340  ULONG oldxasize;
1341 
1342  if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
1343  ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1344  break;
1345  }
1346 
1347  oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;
1348 
1349  if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) {
1350  uint64_t pos;
1351 
1352  // replace
1353 
1354  if (td->size + bi->datalen - oldxasize > maxlen)
1355  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->size, bi->datalen, oldxasize, maxlen);
1356 
1357  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG);
1358  if (!newdata) {
1359  ERR("out of memory\n");
1361  }
1362 
1363  pos = (uint8_t*)xa - td->data;
1364  if (pos + oldxasize < td->size) // copy after changed xattr
1365  RtlCopyMemory(newdata + pos + bi->datalen, td->data + pos + oldxasize, (ULONG)(td->size - pos - oldxasize));
1366 
1367  if (pos > 0) { // copy before changed xattr
1368  RtlCopyMemory(newdata, td->data, (ULONG)pos);
1369  xa = (DIR_ITEM*)(newdata + pos);
1370  } else
1371  xa = (DIR_ITEM*)newdata;
1372 
1373  RtlCopyMemory(xa, bi->data, bi->datalen);
1374 
1375  bi->datalen = (uint16_t)min(td->size + bi->datalen - oldxasize, maxlen);
1376 
1377  ExFreePool(bi->data);
1378  bi->data = newdata;
1379 
1380  break;
1381  }
1382 
1383  if ((uint8_t*)xa - (uint8_t*)td->data + oldxasize >= size) {
1384  // not found, add to end of data
1385 
1386  if (td->size + bi->datalen > maxlen)
1387  ERR("DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1388 
1389  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1390  if (!newdata) {
1391  ERR("out of memory\n");
1393  }
1394 
1395  RtlCopyMemory(newdata, td->data, td->size);
1396 
1397  xa = (DIR_ITEM*)((uint8_t*)newdata + td->size);
1398  RtlCopyMemory(xa, bi->data, bi->datalen);
1399 
1400  bi->datalen = min(bi->datalen + td->size, maxlen);
1401 
1402  ExFreePool(bi->data);
1403  bi->data = newdata;
1404 
1405  break;
1406  } else {
1407  xa = (DIR_ITEM*)&xa->name[xa->m + xa->n];
1408  size -= oldxasize;
1409  }
1410  }
1411  }
1412  break;
1413  }
1414 
1415  case Batch_DirItem: {
1416  uint8_t* newdata;
1417 
1418  if (td->size + bi->datalen > maxlen) {
1419  ERR("DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1420  return STATUS_INTERNAL_ERROR;
1421  }
1422 
1423  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1424  if (!newdata) {
1425  ERR("out of memory\n");
1427  }
1428 
1429  RtlCopyMemory(newdata, td->data, td->size);
1430 
1431  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1432 
1433  bi->datalen += td->size;
1434 
1435  ExFreePool(bi->data);
1436  bi->data = newdata;
1437 
1438  break;
1439  }
1440 
1441  case Batch_InodeRef: {
1442  uint8_t* newdata;
1443 
1444  if (td->size + bi->datalen > maxlen) {
1445  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1446  INODE_REF* ir = (INODE_REF*)bi->data;
1447  INODE_EXTREF* ier;
1448  uint16_t ierlen;
1449  batch_item* bi2;
1450  LIST_ENTRY* le;
1451  bool inserted = false;
1452 
1453  TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n");
1454 
1455  ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n);
1456 
1457  ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG);
1458  if (!ier) {
1459  ERR("out of memory\n");
1461  }
1462 
1463  ier->dir = bi->key.offset;
1464  ier->index = ir->index;
1465  ier->n = ir->n;
1466  RtlCopyMemory(ier->name, ir->name, ier->n);
1467 
1468  bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1469  if (!bi2) {
1470  ERR("out of memory\n");
1471  ExFreePool(ier);
1473  }
1474 
1475  bi2->key.obj_id = bi->key.obj_id;
1477  bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n);
1478  bi2->data = ier;
1479  bi2->datalen = ierlen;
1481 
1482  le = bi->list_entry.Flink;
1483  while (le != listhead) {
1485 
1486  if (keycmp(bi3->key, bi2->key) != -1) {
1487  InsertHeadList(le->Blink, &bi2->list_entry);
1488  inserted = true;
1489  }
1490 
1491  le = le->Flink;
1492  }
1493 
1494  if (!inserted)
1495  InsertTailList(listhead, &bi2->list_entry);
1496 
1497  *ignore = true;
1498  return STATUS_SUCCESS;
1499  } else {
1500  ERR("INODE_REF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1501  return STATUS_INTERNAL_ERROR;
1502  }
1503  }
1504 
1505  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1506  if (!newdata) {
1507  ERR("out of memory\n");
1509  }
1510 
1511  RtlCopyMemory(newdata, td->data, td->size);
1512 
1513  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1514 
1515  bi->datalen += td->size;
1516 
1517  ExFreePool(bi->data);
1518  bi->data = newdata;
1519 
1520  break;
1521  }
1522 
1523  case Batch_InodeExtRef: {
1524  uint8_t* newdata;
1525 
1526  if (td->size + bi->datalen > maxlen) {
1527  ERR("INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen);
1528  return STATUS_INTERNAL_ERROR;
1529  }
1530 
1531  newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG);
1532  if (!newdata) {
1533  ERR("out of memory\n");
1535  }
1536 
1537  RtlCopyMemory(newdata, td->data, td->size);
1538 
1539  RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1540 
1541  bi->datalen += td->size;
1542 
1543  ExFreePool(bi->data);
1544  bi->data = newdata;
1545 
1546  break;
1547  }
1548 
1549  case Batch_DeleteDirItem: {
1550  if (td->size < sizeof(DIR_ITEM)) {
1551  ERR("DIR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
1552  return STATUS_INTERNAL_ERROR;
1553  } else {
1554  DIR_ITEM *di, *deldi;
1555  LONG len;
1556 
1557  deldi = (DIR_ITEM*)bi->data;
1558  di = (DIR_ITEM*)td->data;
1559  len = td->size;
1560 
1561  do {
1562  if (di->m == deldi->m && di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n + di->m) == di->n + di->m) {
1563  uint16_t newlen = td->size - (sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m);
1564 
1565  if (newlen == 0) {
1566  TRACE("deleting DIR_ITEM\n");
1567  } else {
1568  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1569  tree_data* td2;
1570 
1571  if (!newdi) {
1572  ERR("out of memory\n");
1574  }
1575 
1576  TRACE("modifying DIR_ITEM\n");
1577 
1578  if ((uint8_t*)di > td->data) {
1579  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1580  dioff = newdi + ((uint8_t*)di - td->data);
1581  } else {
1582  dioff = newdi;
1583  }
1584 
1585  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1586  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1587 
1588  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1589  if (!td2) {
1590  ERR("out of memory\n");
1591  ExFreePool(newdi);
1593  }
1594 
1595  td2->key = bi->key;
1596  td2->size = newlen;
1597  td2->data = newdi;
1598  td2->ignore = false;
1599  td2->inserted = true;
1600 
1601  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1602 
1603  t->header.num_items++;
1604  t->size += newlen + sizeof(leaf_node);
1605  t->write = true;
1606  }
1607 
1608  break;
1609  }
1610 
1611  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1612  di = (DIR_ITEM*)&di->name[di->n + di->m];
1613 
1614  if (len == 0) {
1615  TRACE("could not find DIR_ITEM to delete\n");
1616  *ignore = true;
1617  return STATUS_SUCCESS;
1618  }
1619  } while (len > 0);
1620  }
1621  break;
1622  }
1623 
1624  case Batch_DeleteInodeRef: {
1625  if (td->size < sizeof(INODE_REF)) {
1626  ERR("INODE_REF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_REF));
1627  return STATUS_INTERNAL_ERROR;
1628  } else {
1629  INODE_REF *ir, *delir;
1630  ULONG len;
1631  bool changed = false;
1632 
1633  delir = (INODE_REF*)bi->data;
1634  ir = (INODE_REF*)td->data;
1635  len = td->size;
1636 
1637  do {
1638  uint16_t itemlen;
1639 
1640  if (len < sizeof(INODE_REF) || len < offsetof(INODE_REF, name[0]) + ir->n) {
1641  ERR("INODE_REF was truncated\n");
1642  break;
1643  }
1644 
1645  itemlen = (uint16_t)offsetof(INODE_REF, name[0]) + ir->n;
1646 
1647  if (ir->n == delir->n && RtlCompareMemory(ir->name, delir->name, ir->n) == ir->n) {
1648  uint16_t newlen = td->size - itemlen;
1649 
1650  changed = true;
1651 
1652  if (newlen == 0)
1653  TRACE("deleting INODE_REF\n");
1654  else {
1655  uint8_t *newir = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *iroff;
1656  tree_data* td2;
1657 
1658  if (!newir) {
1659  ERR("out of memory\n");
1661  }
1662 
1663  TRACE("modifying INODE_REF\n");
1664 
1665  if ((uint8_t*)ir > td->data) {
1666  RtlCopyMemory(newir, td->data, (uint8_t*)ir - td->data);
1667  iroff = newir + ((uint8_t*)ir - td->data);
1668  } else {
1669  iroff = newir;
1670  }
1671 
1672  if ((uint8_t*)&ir->name[ir->n] < td->data + td->size)
1673  RtlCopyMemory(iroff, &ir->name[ir->n], td->size - ((uint8_t*)&ir->name[ir->n] - td->data));
1674 
1675  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1676  if (!td2) {
1677  ERR("out of memory\n");
1678  ExFreePool(newir);
1680  }
1681 
1682  td2->key = bi->key;
1683  td2->size = newlen;
1684  td2->data = newir;
1685  td2->ignore = false;
1686  td2->inserted = true;
1687 
1688  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1689 
1690  t->header.num_items++;
1691  t->size += newlen + sizeof(leaf_node);
1692  t->write = true;
1693  }
1694 
1695  break;
1696  }
1697 
1698  if (len > itemlen) {
1699  len -= itemlen;
1700  ir = (INODE_REF*)&ir->name[ir->n];
1701  } else
1702  break;
1703  } while (len > 0);
1704 
1705  if (!changed) {
1706  if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1707  TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1708 
1709  add_delete_inode_extref(Vcb, bi, listhead);
1710 
1711  *ignore = true;
1712  return STATUS_SUCCESS;
1713  } else
1714  WARN("entry not found in INODE_REF\n");
1715  }
1716  }
1717 
1718  break;
1719  }
1720 
1721  case Batch_DeleteInodeExtRef: {
1722  if (td->size < sizeof(INODE_EXTREF)) {
1723  ERR("INODE_EXTREF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_EXTREF));
1724  return STATUS_INTERNAL_ERROR;
1725  } else {
1726  INODE_EXTREF *ier, *delier;
1727  ULONG len;
1728 
1729  delier = (INODE_EXTREF*)bi->data;
1730  ier = (INODE_EXTREF*)td->data;
1731  len = td->size;
1732 
1733  do {
1734  uint16_t itemlen;
1735 
1736  if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) {
1737  ERR("INODE_REF was truncated\n");
1738  break;
1739  }
1740 
1741  itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n;
1742 
1743  if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) {
1744  uint16_t newlen = td->size - itemlen;
1745 
1746  if (newlen == 0)
1747  TRACE("deleting INODE_EXTREF\n");
1748  else {
1749  uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff;
1750  tree_data* td2;
1751 
1752  if (!newier) {
1753  ERR("out of memory\n");
1755  }
1756 
1757  TRACE("modifying INODE_EXTREF\n");
1758 
1759  if ((uint8_t*)ier > td->data) {
1760  RtlCopyMemory(newier, td->data, (uint8_t*)ier - td->data);
1761  ieroff = newier + ((uint8_t*)ier - td->data);
1762  } else {
1763  ieroff = newier;
1764  }
1765 
1766  if ((uint8_t*)&ier->name[ier->n] < td->data + td->size)
1767  RtlCopyMemory(ieroff, &ier->name[ier->n], td->size - ((uint8_t*)&ier->name[ier->n] - td->data));
1768 
1769  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1770  if (!td2) {
1771  ERR("out of memory\n");
1772  ExFreePool(newier);
1774  }
1775 
1776  td2->key = bi->key;
1777  td2->size = newlen;
1778  td2->data = newier;
1779  td2->ignore = false;
1780  td2->inserted = true;
1781 
1782  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1783 
1784  t->header.num_items++;
1785  t->size += newlen + sizeof(leaf_node);
1786  t->write = true;
1787  }
1788 
1789  break;
1790  }
1791 
1792  if (len > itemlen) {
1793  len -= itemlen;
1794  ier = (INODE_EXTREF*)&ier->name[ier->n];
1795  } else
1796  break;
1797  } while (len > 0);
1798  }
1799  break;
1800  }
1801 
1802  case Batch_DeleteXattr: {
1803  if (td->size < sizeof(DIR_ITEM)) {
1804  ERR("XATTR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM));
1805  return STATUS_INTERNAL_ERROR;
1806  } else {
1807  DIR_ITEM *di, *deldi;
1808  LONG len;
1809 
1810  deldi = (DIR_ITEM*)bi->data;
1811  di = (DIR_ITEM*)td->data;
1812  len = td->size;
1813 
1814  do {
1815  if (di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n) == di->n) {
1816  uint16_t newlen = td->size - ((uint16_t)offsetof(DIR_ITEM, name[0]) + di->n + di->m);
1817 
1818  if (newlen == 0)
1819  TRACE("deleting XATTR_ITEM\n");
1820  else {
1821  uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff;
1822  tree_data* td2;
1823 
1824  if (!newdi) {
1825  ERR("out of memory\n");
1827  }
1828 
1829  TRACE("modifying XATTR_ITEM\n");
1830 
1831  if ((uint8_t*)di > td->data) {
1832  RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data);
1833  dioff = newdi + ((uint8_t*)di - td->data);
1834  } else
1835  dioff = newdi;
1836 
1837  if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size)
1838  RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data));
1839 
1840  td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
1841  if (!td2) {
1842  ERR("out of memory\n");
1843  ExFreePool(newdi);
1845  }
1846 
1847  td2->key = bi->key;
1848  td2->size = newlen;
1849  td2->data = newdi;
1850  td2->ignore = false;
1851  td2->inserted = true;
1852 
1853  InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1854 
1855  t->header.num_items++;
1856  t->size += newlen + sizeof(leaf_node);
1857  t->write = true;
1858  }
1859 
1860  break;
1861  }
1862 
1863  len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1864  di = (DIR_ITEM*)&di->name[di->n + di->m];
1865 
1866  if (len == 0) {
1867  TRACE("could not find DIR_ITEM to delete\n");
1868  *ignore = true;
1869  return STATUS_SUCCESS;
1870  }
1871  } while (len > 0);
1872  }
1873  break;
1874  }
1875 
1876  case Batch_Delete:
1877  break;
1878 
1879  default:
1880  ERR("unexpected batch operation type\n");
1881  return STATUS_INTERNAL_ERROR;
1882  }
1883 
1884  // delete old item
1885  if (!td->ignore) {
1886  td->ignore = true;
1887 
1888  t->header.num_items--;
1889  t->size -= sizeof(leaf_node) + td->size;
1890  t->write = true;
1891  }
1892 
1893  if (newtd) {
1894  newtd->data = bi->data;
1895  newtd->size = bi->datalen;
1896  InsertHeadList(td->list_entry.Blink, &newtd->list_entry);
1897  }
1898  } else {
1899  ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1900  return STATUS_INTERNAL_ERROR;
1901  }
1902 
1903  *ignore = false;
1904  return STATUS_SUCCESS;
1905 }
1906 
1907 __attribute__((nonnull(1,2)))
1908 static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, batch_root* br, PIRP Irp) {
1909  LIST_ENTRY items;
1910  LIST_ENTRY* le;
1911  NTSTATUS Status;
1912 
1913  TRACE("root: %I64x\n", br->r->id);
1914 
1916 
1917  // move sub-lists into one big list
1918 
1919  while (!IsListEmpty(&br->items_ind)) {
1921 
1922  items.Blink->Flink = bii->items.Flink;
1923  bii->items.Flink->Blink = items.Blink;
1924  items.Blink = bii->items.Blink;
1925  bii->items.Blink->Flink = &items;
1926 
1927  ExFreePool(bii);
1928  }
1929 
1930  le = items.Flink;
1931  while (le != &items) {
1933  LIST_ENTRY* le2;
1934  traverse_ptr tp;
1935  KEY tree_end;
1936  bool no_end;
1937  tree_data *td, *listhead;
1938  int cmp;
1939  tree* t;
1940  bool ignore = false;
1941 
1942  TRACE("(%I64x,%x,%I64x)\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1943 
1944  Status = find_item(Vcb, br->r, &tp, &bi->key, true, Irp);
1945  if (!NT_SUCCESS(Status)) { // FIXME - handle STATUS_NOT_FOUND
1946  ERR("find_item returned %08lx\n", Status);
1947  return Status;
1948  }
1949 
1950  Status = find_tree_end(tp.tree, &tree_end, &no_end);
1951  if (!NT_SUCCESS(Status)) {
1952  ERR("find_tree_end returned %08lx\n", Status);
1953  return Status;
1954  }
1955 
1956  if (bi->operation == Batch_DeleteInode) {
1957  if (tp.item->key.obj_id == bi->key.obj_id) {
1958  bool ended = false;
1959 
1960  td = tp.item;
1961 
1962  if (!tp.item->ignore) {
1963  tp.item->ignore = true;
1964  tp.tree->header.num_items--;
1965  tp.tree->size -= tp.item->size + sizeof(leaf_node);
1966  tp.tree->write = true;
1967  }
1968 
1969  le2 = tp.item->list_entry.Flink;
1970  while (le2 != &tp.tree->itemlist) {
1972 
1973  if (td->key.obj_id == bi->key.obj_id) {
1974  if (!td->ignore) {
1975  td->ignore = true;
1976  tp.tree->header.num_items--;
1977  tp.tree->size -= td->size + sizeof(leaf_node);
1978  tp.tree->write = true;
1979  }
1980  } else {
1981  ended = true;
1982  break;
1983  }
1984 
1985  le2 = le2->Flink;
1986  }
1987 
1988  while (!ended) {
1989  traverse_ptr next_tp;
1990 
1991  tp.item = td;
1992 
1993  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1994  break;
1995 
1996  tp = next_tp;
1997 
1998  le2 = &tp.item->list_entry;
1999  while (le2 != &tp.tree->itemlist) {
2001 
2002  if (td->key.obj_id == bi->key.obj_id) {
2003  if (!td->ignore) {
2004  td->ignore = true;
2005  tp.tree->header.num_items--;
2006  tp.tree->size -= td->size + sizeof(leaf_node);
2007  tp.tree->write = true;
2008  }
2009  } else {
2010  ended = true;
2011  break;
2012  }
2013 
2014  le2 = le2->Flink;
2015  }
2016  }
2017  }
2018  } else if (bi->operation == Batch_DeleteExtentData) {
2019  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)) {
2020  traverse_ptr tp2;
2021 
2022  if (find_next_item(Vcb, &tp, &tp2, false, Irp)) {
2023  if (tp2.item->key.obj_id == bi->key.obj_id && tp2.item->key.obj_type == bi->key.obj_type) {
2024  tp = tp2;
2025  Status = find_tree_end(tp.tree, &tree_end, &no_end);
2026  if (!NT_SUCCESS(Status)) {
2027  ERR("find_tree_end returned %08lx\n", Status);
2028  return Status;
2029  }
2030  }
2031  }
2032  }
2033 
2034  if (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type == bi->key.obj_type) {
2035  bool ended = false;
2036 
2037  td = tp.item;
2038 
2039  if (!tp.item->ignore) {
2040  tp.item->ignore = true;
2041  tp.tree->header.num_items--;
2042  tp.tree->size -= tp.item->size + sizeof(leaf_node);
2043  tp.tree->write = true;
2044  }
2045 
2046  le2 = tp.item->list_entry.Flink;
2047  while (le2 != &tp.tree->itemlist) {
2049 
2050  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2051  if (!td->ignore) {
2052  td->ignore = true;
2053  tp.tree->header.num_items--;
2054  tp.tree->size -= td->size + sizeof(leaf_node);
2055  tp.tree->write = true;
2056  }
2057  } else {
2058  ended = true;
2059  break;
2060  }
2061 
2062  le2 = le2->Flink;
2063  }
2064 
2065  while (!ended) {
2066  traverse_ptr next_tp;
2067 
2068  tp.item = td;
2069 
2070  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2071  break;
2072 
2073  tp = next_tp;
2074 
2075  le2 = &tp.item->list_entry;
2076  while (le2 != &tp.tree->itemlist) {
2078 
2079  if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2080  if (!td->ignore) {
2081  td->ignore = true;
2082  tp.tree->header.num_items--;
2083  tp.tree->size -= td->size + sizeof(leaf_node);
2084  tp.tree->write = true;
2085  }
2086  } else {
2087  ended = true;
2088  break;
2089  }
2090 
2091  le2 = le2->Flink;
2092  }
2093  }
2094  }
2095  } else if (bi->operation == Batch_DeleteFreeSpace) {
2096  if (tp.item->key.obj_id >= bi->key.obj_id && tp.item->key.obj_id < bi->key.obj_id + bi->key.offset) {
2097  bool ended = false;
2098 
2099  td = tp.item;
2100 
2101  if (!tp.item->ignore) {
2102  tp.item->ignore = true;
2103  tp.tree->header.num_items--;
2104  tp.tree->size -= tp.item->size + sizeof(leaf_node);
2105  tp.tree->write = true;
2106  }
2107 
2108  le2 = tp.item->list_entry.Flink;
2109  while (le2 != &tp.tree->itemlist) {
2111 
2112  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2113  if (!td->ignore) {
2114  td->ignore = true;
2115  tp.tree->header.num_items--;
2116  tp.tree->size -= td->size + sizeof(leaf_node);
2117  tp.tree->write = true;
2118  }
2119  } else {
2120  ended = true;
2121  break;
2122  }
2123 
2124  le2 = le2->Flink;
2125  }
2126 
2127  while (!ended) {
2128  traverse_ptr next_tp;
2129 
2130  tp.item = td;
2131 
2132  if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2133  break;
2134 
2135  tp = next_tp;
2136 
2137  le2 = &tp.item->list_entry;
2138  while (le2 != &tp.tree->itemlist) {
2140 
2141  if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2142  if (!td->ignore) {
2143  td->ignore = true;
2144  tp.tree->header.num_items--;
2145  tp.tree->size -= td->size + sizeof(leaf_node);
2146  tp.tree->write = true;
2147  }
2148  } else {
2149  ended = true;
2150  break;
2151  }
2152 
2153  le2 = le2->Flink;
2154  }
2155  }
2156  }
2157  } else {
2160  td = NULL;
2161  else {
2162  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2163  if (!td) {
2164  ERR("out of memory\n");
2166  }
2167 
2168  td->key = bi->key;
2169  td->size = bi->datalen;
2170  td->data = bi->data;
2171  td->ignore = false;
2172  td->inserted = true;
2173  }
2174 
2175  cmp = keycmp(bi->key, tp.item->key);
2176 
2177  if (cmp == -1) { // very first key in root
2178  if (td) {
2179  tree_data* paritem;
2180 
2182 
2183  paritem = tp.tree->paritem;
2184  while (paritem) {
2185  if (!keycmp(paritem->key, tp.item->key)) {
2186  paritem->key = bi->key;
2187  } else
2188  break;
2189 
2190  paritem = paritem->treeholder.tree->paritem;
2191  }
2192  }
2193  } else if (cmp == 0) { // item already exists
2194  if (tp.item->ignore) {
2195  if (td)
2197  } else {
2198  Status = handle_batch_collision(Vcb, bi, tp.tree, tp.item, td, &items, &ignore);
2199  if (!NT_SUCCESS(Status)) {
2200  ERR("handle_batch_collision returned %08lx\n", Status);
2201 #ifdef _DEBUG
2202  int3;
2203 #endif
2204 
2205  if (td)
2206  ExFreeToPagedLookasideList(&Vcb->tree_data_lookaside, td);
2207 
2208  return Status;
2209  }
2210  }
2211  } else if (td) {
2213  }
2214 
2215  if (bi->operation == Batch_DeleteInodeRef && cmp != 0 && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2216  add_delete_inode_extref(Vcb, bi, &items);
2217  }
2218 
2219  if (!ignore && td) {
2220  tp.tree->header.num_items++;
2221  tp.tree->size += bi->datalen + sizeof(leaf_node);
2222  tp.tree->write = true;
2223 
2224  listhead = td;
2225  } else
2226  listhead = tp.item;
2227 
2228  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2230 
2231  if (!keycmp(prevtd->key, listhead->key))
2232  listhead = prevtd;
2233  else
2234  break;
2235  }
2236 
2237  le2 = le->Flink;
2238  while (le2 != &items) {
2240 
2242  break;
2243 
2244  if (no_end || keycmp(bi2->key, tree_end) == -1) {
2245  LIST_ENTRY* le3;
2246  bool inserted = false;
2247 
2248  ignore = false;
2249 
2252  td = NULL;
2253  else {
2254  td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2255  if (!td) {
2256  ERR("out of memory\n");
2258  }
2259 
2260  td->key = bi2->key;
2261  td->size = bi2->datalen;
2262  td->data = bi2->data;
2263  td->ignore = false;
2264  td->inserted = true;
2265  }
2266 
2267  le3 = &listhead->list_entry;
2268  while (le3 != &tp.tree->itemlist) {
2270 
2271  cmp = keycmp(bi2->key, td2->key);
2272 
2273  if (cmp == 0) {
2274  if (td2->ignore) {
2275  if (td) {
2276  InsertHeadList(le3->Blink, &td->list_entry);
2277  inserted = true;
2278  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2279  add_delete_inode_extref(Vcb, bi2, &items);
2280  }
2281  } else {
2282  Status = handle_batch_collision(Vcb, bi2, tp.tree, td2, td, &items, &ignore);
2283  if (!NT_SUCCESS(Status)) {
2284  ERR("handle_batch_collision returned %08lx\n", Status);
2285 #ifdef _DEBUG
2286  int3;
2287 #endif
2288  return Status;
2289  }
2290  }
2291 
2292  inserted = true;
2293  break;
2294  } else if (cmp == -1) {
2295  if (td) {
2296  InsertHeadList(le3->Blink, &td->list_entry);
2297  inserted = true;
2298  } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2299  add_delete_inode_extref(Vcb, bi2, &items);
2300  }
2301  break;
2302  }
2303 
2304  le3 = le3->Flink;
2305  }
2306 
2307  if (td) {
2308  if (!inserted)
2310 
2311  if (!ignore) {
2312  tp.tree->header.num_items++;
2313  tp.tree->size += bi2->datalen + sizeof(leaf_node);
2314 
2315  listhead = td;
2316  }
2317  } else if (!inserted && bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2318  add_delete_inode_extref(Vcb, bi2, &items);
2319  }
2320 
2321  while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2323 
2324  if (!keycmp(prevtd->key, listhead->key))
2325  listhead = prevtd;
2326  else
2327  break;
2328  }
2329 
2330  le = le2;
2331  } else
2332  break;
2333 
2334  le2 = le2->Flink;
2335  }
2336 
2337  t = tp.tree;
2338  while (t) {
2339  if (t->paritem && t->paritem->ignore) {
2340  t->paritem->ignore = false;
2341  t->parent->header.num_items++;
2342  t->parent->size += sizeof(internal_node);
2343  }
2344 
2345  t->header.generation = Vcb->superblock.generation;
2346  t = t->parent;
2347  }
2348  }
2349 
2350  le = le->Flink;
2351  }
2352 
2353  // FIXME - remove as we are going along
2354  while (!IsListEmpty(&items)) {
2356 
2359  ExFreePool(bi->data);
2360 
2361  ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi);
2362  }
2363 
2364  return STATUS_SUCCESS;
2365 }
2366 
2367 __attribute__((nonnull(1,2)))
2369  NTSTATUS Status;
2370 
2371  while (!IsListEmpty(batchlist)) {
2372  LIST_ENTRY* le = RemoveHeadList(batchlist);
2374 
2375  Status = commit_batch_list_root(Vcb, br2, Irp);
2376  if (!NT_SUCCESS(Status)) {
2377  ERR("commit_batch_list_root returned %08lx\n", Status);
2378  return Status;
2379  }
2380 
2381  ExFreePool(br2);
2382  }
2383 
2384  return STATUS_SUCCESS;
2385 }
LIST_ENTRY * list_size
Definition: btrfs_drv.h:1256
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:1275
#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
LIST_ENTRY items_ind
Definition: btrfs_drv.h:503
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:1016
#define WARN(fmt,...)
Definition: debug.h:112
LONG NTSTATUS
Definition: precomp.h:26
void reap_fcbs(device_extension *Vcb)
Definition: btrfs.c:1841
#define int3
Definition: btrfs_drv.h:1745
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:565
#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:1258
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:508
chunk * chunk
Definition: btrfs_drv.h:1259
_In_ PIRP Irp
Definition: csq.h:116
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:1257
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:1140
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:2996
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:1277
#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:1906
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:1267
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:509
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:1264
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:1139
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
LIST_ENTRY items
Definition: btrfs_drv.h:496
#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:1364
__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:1255
#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
static TCHAR * items[]
Definition: page1.c:45
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