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