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