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