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)))
load_tree(device_extension * Vcb,uint64_t addr,uint8_t * buf,root * r,tree ** pt)22 NTSTATUS load_tree(device_extension* Vcb, uint64_t addr, uint8_t* buf, root* r, tree** pt) {
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
32 t = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
33 if (!t) {
34 ERR("out of memory\n");
35 return STATUS_INSUFFICIENT_RESOURCES;
36 }
37
38 if (th->level > 0) {
39 t->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
40 if (!t->nonpaged) {
41 ERR("out of memory\n");
42 ExFreePool(t);
43 return STATUS_INSUFFICIENT_RESOURCES;
44 }
45
46 ExInitializeFastMutex(&t->nonpaged->mutex);
47 } else
48 t->nonpaged = NULL;
49
50 RtlCopyMemory(&t->header, th, sizeof(tree_header));
51 t->hash = calc_crc32c(0xffffffff, (uint8_t*)&addr, sizeof(uint64_t));
52 t->has_address = true;
53 t->Vcb = Vcb;
54 t->parent = NULL;
55 t->root = r;
56 t->paritem = NULL;
57 t->size = 0;
58 t->new_address = 0;
59 t->has_new_address = false;
60 t->updated_extents = false;
61 t->write = false;
62 t->uniqueness_determined = false;
63
64 InitializeListHead(&t->itemlist);
65
66 if (t->header.level == 0) { // leaf node
67 leaf_node* ln = (leaf_node*)(buf + sizeof(tree_header));
68 unsigned int i;
69
70 if ((t->header.num_items * sizeof(leaf_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
71 ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
72 ExFreePool(t);
73 return STATUS_INSUFFICIENT_RESOURCES;
74 }
75
76 for (i = 0; i < t->header.num_items; i++) {
77 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
78 if (!td) {
79 ERR("out of memory\n");
80 ExFreePool(t);
81 return STATUS_INSUFFICIENT_RESOURCES;
82 }
83
84 td->key = ln[i].key;
85
86 if (ln[i].size > 0)
87 td->data = buf + sizeof(tree_header) + ln[i].offset;
88 else
89 td->data = NULL;
90
91 if (ln[i].size + sizeof(tree_header) + sizeof(leaf_node) > Vcb->superblock.node_size) {
92 ERR("overlarge item in tree %I64x: %u > %Iu\n", addr, ln[i].size, Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
93 ExFreeToPagedLookasideList(&t->Vcb->tree_data_lookaside, td);
94 ExFreePool(t);
95 return STATUS_INTERNAL_ERROR;
96 }
97
98 td->size = (uint16_t)ln[i].size;
99 td->ignore = false;
100 td->inserted = false;
101
102 InsertTailList(&t->itemlist, &td->list_entry);
103
104 t->size += ln[i].size;
105 }
106
107 t->size += t->header.num_items * sizeof(leaf_node);
108 t->buf = buf;
109 } else {
110 internal_node* in = (internal_node*)(buf + sizeof(tree_header));
111 unsigned int i;
112
113 if ((t->header.num_items * sizeof(internal_node)) + sizeof(tree_header) > Vcb->superblock.node_size) {
114 ERR("tree at %I64x has more items than expected (%x)\n", addr, t->header.num_items);
115 ExFreePool(t);
116 return STATUS_INSUFFICIENT_RESOURCES;
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);
124 return STATUS_INSUFFICIENT_RESOURCES;
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)))
do_load_tree2(device_extension * Vcb,tree_holder * th,uint8_t * buf,root * r,tree * t,tree_data * td)196 static NTSTATUS do_load_tree2(device_extension* Vcb, tree_holder* th, uint8_t* buf, root* r, tree* t, tree_data* td) {
197 if (!th->tree) {
198 NTSTATUS Status;
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)))
do_load_tree(device_extension * Vcb,tree_holder * th,root * r,tree * t,tree_data * td,PIRP Irp)222 NTSTATUS do_load_tree(device_extension* Vcb, tree_holder* th, root* r, tree* t, tree_data* td, PIRP Irp) {
223 NTSTATUS Status;
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");
230 return STATUS_INSUFFICIENT_RESOURCES;
231 }
232
233 Status = read_data(Vcb, th->address, Vcb->superblock.node_size, NULL, true, buf, NULL,
234 &c, Irp, th->generation, false, NormalPagePriority);
235 if (!NT_SUCCESS(Status)) {
236 ERR("read_data returned 0x%08lx\n", Status);
237 ExFreePool(buf);
238 return Status;
239 }
240
241 if (t)
242 ExAcquireFastMutex(&t->nonpaged->mutex);
243 else
244 ExAcquireResourceExclusiveLite(&r->nonpaged->load_tree_lock, true);
245
246 Status = do_load_tree2(Vcb, th, buf, r, t, td);
247
248 if (t)
249 ExReleaseFastMutex(&t->nonpaged->mutex);
250 else
251 ExReleaseResourceLite(&r->nonpaged->load_tree_lock);
252
253 if (!th->tree || th->tree->buf != buf)
254 ExFreePool(buf);
255
256 if (!NT_SUCCESS(Status)) {
257 ERR("do_load_tree2 returned %08lx\n", Status);
258 return Status;
259 }
260
261 return Status;
262 }
263
264 __attribute__((nonnull(1)))
free_tree(tree * t)265 void free_tree(tree* t) {
266 tree* par;
267 root* r = t->root;
268
269 // No need to acquire lock, as this is only ever called while Vcb->tree_lock held exclusively
270
271 par = t->parent;
272
273 if (r && r->treeholder.tree != t)
274 r = NULL;
275
276 if (par) {
277 if (t->paritem)
278 t->paritem->treeholder.tree = NULL;
279 }
280
281 while (!IsListEmpty(&t->itemlist)) {
282 tree_data* td = CONTAINING_RECORD(RemoveHeadList(&t->itemlist), tree_data, list_entry);
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)))
first_item(tree * t)322 static __inline tree_data* first_item(tree* t) {
323 LIST_ENTRY* le = t->itemlist.Flink;
324
325 if (le == &t->itemlist)
326 return NULL;
327
328 return CONTAINING_RECORD(le, tree_data, list_entry);
329 }
330
331 __attribute__((nonnull(1,2)))
prev_item(tree * t,tree_data * td)332 static __inline tree_data* prev_item(tree* t, tree_data* td) {
333 LIST_ENTRY* le = td->list_entry.Blink;
334
335 if (le == &t->itemlist)
336 return NULL;
337
338 return CONTAINING_RECORD(le, tree_data, list_entry);
339 }
340
341 __attribute__((nonnull(1,2)))
next_item(tree * t,tree_data * td)342 static __inline tree_data* next_item(tree* t, tree_data* td) {
343 LIST_ENTRY* le = td->list_entry.Flink;
344
345 if (le == &t->itemlist)
346 return NULL;
347
348 return CONTAINING_RECORD(le, tree_data, list_entry);
349 }
350
351 __attribute__((nonnull(1,2,3,4)))
next_item2(device_extension * Vcb,tree * t,tree_data * td,traverse_ptr * tp)352 static NTSTATUS next_item2(device_extension* Vcb, tree* t, tree_data* td, traverse_ptr* tp) {
353 tree_data* td2 = next_item(t, td);
354 tree* t2;
355
356 if (td2) {
357 tp->tree = t;
358 tp->item = td2;
359 return STATUS_SUCCESS;
360 }
361
362 t2 = t;
363
364 do {
365 td2 = t2->paritem;
366 t2 = t2->parent;
367 } while (td2 && !next_item(t2, td2));
368
369 if (!td2)
370 return STATUS_NOT_FOUND;
371
372 td2 = next_item(t2, td2);
373
374 return find_item_to_level(Vcb, t2->root, tp, &td2->key, false, t->header.level, NULL);
375 }
376
377 __attribute__((nonnull(1,2,3,4,5)))
skip_to_difference(device_extension * Vcb,traverse_ptr * tp,traverse_ptr * tp2,bool * ended1,bool * ended2)378 NTSTATUS skip_to_difference(device_extension* Vcb, traverse_ptr* tp, traverse_ptr* tp2, bool* ended1, bool* ended2) {
379 NTSTATUS Status;
380 tree *t1, *t2;
381 tree_data *td1, *td2;
382
383 t1 = tp->tree;
384 t2 = tp2->tree;
385
386 do {
387 td1 = t1->paritem;
388 td2 = t2->paritem;
389 t1 = t1->parent;
390 t2 = t2->parent;
391 } while (t1 && t2 && t1->header.address == t2->header.address);
392
393 while (true) {
394 traverse_ptr tp3, tp4;
395
396 Status = next_item2(Vcb, t1, td1, &tp3);
397 if (Status == STATUS_NOT_FOUND)
398 *ended1 = true;
399 else if (!NT_SUCCESS(Status)) {
400 ERR("next_item2 returned %08lx\n", Status);
401 return Status;
402 }
403
404 Status = next_item2(Vcb, t2, td2, &tp4);
405 if (Status == STATUS_NOT_FOUND)
406 *ended2 = true;
407 else if (!NT_SUCCESS(Status)) {
408 ERR("next_item2 returned %08lx\n", Status);
409 return Status;
410 }
411
412 if (*ended1 || *ended2) {
413 if (!*ended1) {
414 Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
415 if (!NT_SUCCESS(Status)) {
416 ERR("find_item returned %08lx\n", Status);
417 return Status;
418 }
419 } else if (!*ended2) {
420 Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
421 if (!NT_SUCCESS(Status)) {
422 ERR("find_item returned %08lx\n", Status);
423 return Status;
424 }
425 }
426
427 return STATUS_SUCCESS;
428 }
429
430 if (tp3.tree->header.address != tp4.tree->header.address) {
431 Status = find_item(Vcb, t1->root, tp, &tp3.item->key, false, NULL);
432 if (!NT_SUCCESS(Status)) {
433 ERR("find_item returned %08lx\n", Status);
434 return Status;
435 }
436
437 Status = find_item(Vcb, t2->root, tp2, &tp4.item->key, false, NULL);
438 if (!NT_SUCCESS(Status)) {
439 ERR("find_item returned %08lx\n", Status);
440 return Status;
441 }
442
443 return STATUS_SUCCESS;
444 }
445
446 t1 = tp3.tree;
447 td1 = tp3.item;
448 t2 = tp4.tree;
449 td2 = tp4.item;
450 }
451 }
452
453 __attribute__((nonnull(1,2,3,4)))
find_item_in_tree(device_extension * Vcb,tree * t,traverse_ptr * tp,const KEY * searchkey,bool ignore,uint8_t level,PIRP Irp)454 static NTSTATUS find_item_in_tree(device_extension* Vcb, tree* t, traverse_ptr* tp, const KEY* searchkey, bool ignore, uint8_t level, PIRP Irp) {
455 int cmp;
456 tree_data *td, *lasttd;
457 KEY key2;
458
459 cmp = 1;
460 td = first_item(t);
461 lasttd = NULL;
462
463 if (!td) return STATUS_NOT_FOUND;
464
465 key2 = *searchkey;
466
467 do {
468 cmp = keycmp(key2, td->key);
469
470 if (cmp == 1) {
471 lasttd = td;
472 td = next_item(t, td);
473 }
474
475 if (t->header.level == 0 && cmp == 0 && !ignore && td && td->ignore) {
476 tree_data* origtd = td;
477
478 while (td && td->ignore)
479 td = next_item(t, td);
480
481 if (td) {
482 cmp = keycmp(key2, td->key);
483
484 if (cmp != 0) {
485 td = origtd;
486 cmp = 0;
487 }
488 } else
489 td = origtd;
490 }
491 } while (td && cmp == 1);
492
493 if ((cmp == -1 || !td) && lasttd)
494 td = lasttd;
495
496 if (t->header.level == 0) {
497 if (td->ignore && !ignore) {
498 traverse_ptr oldtp;
499
500 oldtp.tree = t;
501 oldtp.item = td;
502
503 while (find_prev_item(Vcb, &oldtp, tp, Irp)) {
504 if (!tp->item->ignore)
505 return STATUS_SUCCESS;
506
507 oldtp = *tp;
508 }
509
510 // if no valid entries before where item should be, look afterwards instead
511
512 oldtp.tree = t;
513 oldtp.item = td;
514
515 while (find_next_item(Vcb, &oldtp, tp, true, Irp)) {
516 if (!tp->item->ignore)
517 return STATUS_SUCCESS;
518
519 oldtp = *tp;
520 }
521
522 return STATUS_NOT_FOUND;
523 } else {
524 tp->tree = t;
525 tp->item = td;
526 }
527
528 return STATUS_SUCCESS;
529 } else {
530 NTSTATUS Status;
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)))
560 NTSTATUS find_item(_In_ _Requires_lock_held_(_Curr_->tree_lock) device_extension* Vcb, _In_ root* r, _Out_ traverse_ptr* tp,
561 _In_ const KEY* searchkey, _In_ bool ignore, _In_opt_ PIRP Irp) {
562 NTSTATUS Status;
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);
573 if (!NT_SUCCESS(Status) && Status != STATUS_NOT_FOUND) {
574 ERR("find_item_in_tree returned %08lx\n", Status);
575 }
576
577 return Status;
578 }
579
580 __attribute__((nonnull(1,2,3,4)))
find_item_to_level(device_extension * Vcb,root * r,traverse_ptr * tp,const KEY * searchkey,bool ignore,uint8_t level,PIRP Irp)581 NTSTATUS find_item_to_level(device_extension* Vcb, root* r, traverse_ptr* tp, const KEY* searchkey, bool ignore, uint8_t level, PIRP Irp) {
582 NTSTATUS Status;
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);
593 if (!NT_SUCCESS(Status) && Status != STATUS_NOT_FOUND) {
594 ERR("find_item_in_tree returned %08lx\n", Status);
595 }
596
597 if (Status == STATUS_NOT_FOUND) {
598 tp->tree = r->treeholder.tree;
599 tp->item = NULL;
600 }
601
602 return Status;
603 }
604
605 __attribute__((nonnull(1,2,3)))
606 bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension* Vcb, const traverse_ptr* tp, traverse_ptr* next_tp, bool ignore, PIRP Irp) {
607 tree* t;
608 tree_data *td = NULL, *next;
609 NTSTATUS Status;
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)))
last_item(tree * t)710 static __inline tree_data* last_item(tree* t) {
711 LIST_ENTRY* le = t->itemlist.Blink;
712
713 if (le == &t->itemlist)
714 return NULL;
715
716 return CONTAINING_RECORD(le, tree_data, list_entry);
717 }
718
719 __attribute__((nonnull(1,2,3)))
720 bool find_prev_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension* Vcb, const traverse_ptr* tp, traverse_ptr* prev_tp, PIRP Irp) {
721 tree* t;
722 tree_data* td;
723 NTSTATUS Status;
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)))
free_trees_root(device_extension * Vcb,root * r)779 void free_trees_root(device_extension* Vcb, root* r) {
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;
790 tree* t = CONTAINING_RECORD(le, tree, list_entry);
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)))
free_trees(device_extension * Vcb)817 void free_trees(device_extension* Vcb) {
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;
828 tree* t = CONTAINING_RECORD(le, tree, list_entry);
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)))
add_rollback(_In_ LIST_ENTRY * rollback,_In_ enum rollback_type type,_In_ __drv_aliasesMem void * ptr)861 void add_rollback(_In_ LIST_ENTRY* rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void* ptr) {
862 rollback_item* ri;
863
864 ri = ExAllocatePoolWithTag(PagedPool, sizeof(rollback_item), ALLOC_TAG);
865 if (!ri) {
866 ERR("out of memory\n");
867 return;
868 }
869
870 ri->type = type;
871 ri->ptr = ptr;
872 InsertTailList(rollback, &ri->list_entry);
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)))
883 NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, _In_ root* r, _In_ uint64_t obj_id,
884 _In_ uint8_t obj_type, _In_ uint64_t offset, _In_reads_bytes_opt_(size) _When_(return >= 0, __drv_aliasesMem) void* data,
885 _In_ uint16_t size, _Out_opt_ traverse_ptr* ptp, _In_opt_ PIRP Irp) {
886 traverse_ptr tp;
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
895 NTSTATUS Status;
896
897 TRACE("(%p, %p, %I64x, %x, %I64x, %p, %x, %p)\n", Vcb, r, obj_id, obj_type, offset, data, size, ptp);
898
899 searchkey.obj_id = obj_id;
900 searchkey.obj_type = obj_type;
901 searchkey.offset = offset;
902
903 Status = find_item(Vcb, r, &tp, &searchkey, true, Irp);
904 if (Status == STATUS_NOT_FOUND) {
905 if (!r->treeholder.tree) {
906 Status = do_load_tree(Vcb, &r->treeholder, r, NULL, NULL, Irp);
907 if (!NT_SUCCESS(Status)) {
908 ERR("do_load_tree returned %08lx\n", Status);
909 return Status;
910 }
911 }
912
913 if (r->treeholder.tree && r->treeholder.tree->header.num_items == 0) {
914 tp.tree = r->treeholder.tree;
915 tp.item = NULL;
916 } else {
917 ERR("error: unable to load tree for root %I64x\n", r->id);
918 return STATUS_INTERNAL_ERROR;
919 }
920 } else if (!NT_SUCCESS(Status)) {
921 ERR("find_item returned %08lx\n", Status);
922 return Status;
923 }
924
925 TRACE("tp.item = %p\n", tp.item);
926
927 if (tp.item) {
928 TRACE("tp.item->key = %p\n", &tp.item->key);
929 cmp = keycmp(searchkey, tp.item->key);
930
931 if (cmp == 0 && !tp.item->ignore) {
932 ERR("error: key (%I64x,%x,%I64x) already present\n", obj_id, obj_type, offset);
933 #ifdef DEBUG_PARANOID
934 int3;
935 #endif
936 return STATUS_INTERNAL_ERROR;
937 }
938 } else
939 cmp = -1;
940
941 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
942 if (!td) {
943 ERR("out of memory\n");
944 return STATUS_INSUFFICIENT_RESOURCES;
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) {
956 tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
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
965 InsertHeadList(&tp.tree->itemlist, &td->list_entry);
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
979 InsertHeadList(&tp.item->list_entry, &td->list_entry);
980
981 tp.tree->header.num_items++;
982 tp.tree->size += size + sizeof(leaf_node);
983
984 if (!tp.tree->write) {
985 tp.tree->write = true;
986 Vcb->need_write = true;
987 }
988
989 if (ptp)
990 *ptp = tp;
991
992 t = tp.tree;
993 while (t) {
994 if (t->paritem && t->paritem->ignore) {
995 t->paritem->ignore = false;
996 t->parent->header.num_items++;
997 t->parent->size += sizeof(internal_node);
998 }
999
1000 t->header.generation = Vcb->superblock.generation;
1001 t = t->parent;
1002 }
1003
1004 return STATUS_SUCCESS;
1005 }
1006 #ifdef _MSC_VER
1007 #pragma warning(pop)
1008 #endif
1009
1010 __attribute__((nonnull(1,2)))
1011 NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, _Inout_ traverse_ptr* tp) {
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)))
clear_rollback(LIST_ENTRY * rollback)1051 void clear_rollback(LIST_ENTRY* rollback) {
1052 while (!IsListEmpty(rollback)) {
1053 LIST_ENTRY* le = RemoveHeadList(rollback);
1054 rollback_item* ri = CONTAINING_RECORD(le, rollback_item, list_entry);
1055
1056 switch (ri->type) {
1057 case ROLLBACK_ADD_SPACE:
1058 case ROLLBACK_SUBTRACT_SPACE:
1059 case ROLLBACK_INSERT_EXTENT:
1060 case ROLLBACK_DELETE_EXTENT:
1061 ExFreePool(ri->ptr);
1062 break;
1063
1064 default:
1065 break;
1066 }
1067
1068 ExFreePool(ri);
1069 }
1070 }
1071
1072 __attribute__((nonnull(1,2)))
do_rollback(device_extension * Vcb,LIST_ENTRY * rollback)1073 void do_rollback(device_extension* Vcb, LIST_ENTRY* rollback) {
1074 NTSTATUS Status;
1075 rollback_item* ri;
1076
1077 while (!IsListEmpty(rollback)) {
1078 LIST_ENTRY* le = RemoveTailList(rollback);
1079 ri = CONTAINING_RECORD(le, rollback_item, list_entry);
1080
1081 switch (ri->type) {
1082 case ROLLBACK_INSERT_EXTENT:
1083 {
1084 rollback_extent* re = ri->ptr;
1085
1086 re->ext->ignore = true;
1087
1088 switch (re->ext->extent_data.type) {
1089 case EXTENT_TYPE_REGULAR:
1090 case EXTENT_TYPE_PREALLOC: {
1091 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)re->ext->extent_data.data;
1092
1093 if (ed2->size != 0) {
1094 chunk* c = get_chunk_from_address(Vcb, ed2->address);
1095
1096 if (c) {
1097 Status = update_changed_extent_ref(Vcb, c, ed2->address, ed2->size, re->fcb->subvol->id,
1098 re->fcb->inode, re->ext->offset - ed2->offset, -1,
1099 re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1100
1101 if (!NT_SUCCESS(Status))
1102 ERR("update_changed_extent_ref returned %08lx\n", Status);
1103 }
1104
1105 re->fcb->inode_item.st_blocks -= ed2->num_bytes;
1106 }
1107
1108 break;
1109 }
1110
1111 case EXTENT_TYPE_INLINE:
1112 re->fcb->inode_item.st_blocks -= re->ext->extent_data.decoded_size;
1113 break;
1114 }
1115
1116 ExFreePool(re);
1117 break;
1118 }
1119
1120 case ROLLBACK_DELETE_EXTENT:
1121 {
1122 rollback_extent* re = ri->ptr;
1123
1124 re->ext->ignore = false;
1125
1126 switch (re->ext->extent_data.type) {
1127 case EXTENT_TYPE_REGULAR:
1128 case EXTENT_TYPE_PREALLOC: {
1129 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)re->ext->extent_data.data;
1130
1131 if (ed2->size != 0) {
1132 chunk* c = get_chunk_from_address(Vcb, ed2->address);
1133
1134 if (c) {
1135 Status = update_changed_extent_ref(Vcb, c, ed2->address, ed2->size, re->fcb->subvol->id,
1136 re->fcb->inode, re->ext->offset - ed2->offset, 1,
1137 re->fcb->inode_item.flags & BTRFS_INODE_NODATASUM, false, NULL);
1138
1139 if (!NT_SUCCESS(Status))
1140 ERR("update_changed_extent_ref returned %08lx\n", Status);
1141 }
1142
1143 re->fcb->inode_item.st_blocks += ed2->num_bytes;
1144 }
1145
1146 break;
1147 }
1148
1149 case EXTENT_TYPE_INLINE:
1150 re->fcb->inode_item.st_blocks += re->ext->extent_data.decoded_size;
1151 break;
1152 }
1153
1154 ExFreePool(re);
1155 break;
1156 }
1157
1158 case ROLLBACK_ADD_SPACE:
1159 case ROLLBACK_SUBTRACT_SPACE:
1160 {
1161 rollback_space* rs = ri->ptr;
1162
1163 if (rs->chunk)
1164 acquire_chunk_lock(rs->chunk, Vcb);
1165
1166 if (ri->type == ROLLBACK_ADD_SPACE)
1167 space_list_subtract2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1168 else
1169 space_list_add2(rs->list, rs->list_size, rs->address, rs->length, NULL, NULL);
1170
1171 if (rs->chunk) {
1172 if (ri->type == ROLLBACK_ADD_SPACE)
1173 rs->chunk->used += rs->length;
1174 else
1175 rs->chunk->used -= rs->length;
1176 }
1177
1178 if (rs->chunk) {
1179 LIST_ENTRY* le2 = le->Blink;
1180
1181 while (le2 != rollback) {
1182 LIST_ENTRY* le3 = le2->Blink;
1183 rollback_item* ri2 = CONTAINING_RECORD(le2, rollback_item, list_entry);
1184
1185 if (ri2->type == ROLLBACK_ADD_SPACE || ri2->type == ROLLBACK_SUBTRACT_SPACE) {
1186 rollback_space* rs2 = ri2->ptr;
1187
1188 if (rs2->chunk == rs->chunk) {
1189 if (ri2->type == ROLLBACK_ADD_SPACE) {
1190 space_list_subtract2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1191 rs->chunk->used += rs2->length;
1192 } else {
1193 space_list_add2(rs2->list, rs2->list_size, rs2->address, rs2->length, NULL, NULL);
1194 rs->chunk->used -= rs2->length;
1195 }
1196
1197 ExFreePool(rs2);
1198 RemoveEntryList(&ri2->list_entry);
1199 ExFreePool(ri2);
1200 }
1201 }
1202
1203 le2 = le3;
1204 }
1205
1206 release_chunk_lock(rs->chunk, Vcb);
1207 }
1208
1209 ExFreePool(rs);
1210
1211 break;
1212 }
1213 }
1214
1215 ExFreePool(ri);
1216 }
1217 }
1218
1219 __attribute__((nonnull(1,2,3)))
find_tree_end(tree * t,KEY * tree_end,bool * no_end)1220 static NTSTATUS find_tree_end(tree* t, KEY* tree_end, bool* no_end) {
1221 tree* p;
1222
1223 p = t;
1224 do {
1225 tree_data* pi;
1226
1227 if (!p->parent) {
1228 tree_end->obj_id = 0xffffffffffffffff;
1229 tree_end->obj_type = 0xff;
1230 tree_end->offset = 0xffffffffffffffff;
1231 *no_end = true;
1232 return STATUS_SUCCESS;
1233 }
1234
1235 pi = p->paritem;
1236
1237 if (pi->list_entry.Flink != &p->parent->itemlist) {
1238 tree_data* td = CONTAINING_RECORD(pi->list_entry.Flink, tree_data, list_entry);
1239
1240 *tree_end = td->key;
1241 *no_end = false;
1242 return STATUS_SUCCESS;
1243 }
1244
1245 p = p->parent;
1246 } while (p);
1247
1248 return STATUS_INTERNAL_ERROR;
1249 }
1250
1251 __attribute__((nonnull(1,2)))
clear_batch_list(device_extension * Vcb,LIST_ENTRY * batchlist)1252 void clear_batch_list(device_extension* Vcb, LIST_ENTRY* batchlist) {
1253 while (!IsListEmpty(batchlist)) {
1254 LIST_ENTRY* le = RemoveHeadList(batchlist);
1255 batch_root* br = CONTAINING_RECORD(le, batch_root, list_entry);
1256
1257 while (!IsListEmpty(&br->items_ind)) {
1258 batch_item_ind* bii = CONTAINING_RECORD(RemoveHeadList(&br->items_ind), batch_item_ind, list_entry);
1259
1260 while (!IsListEmpty(&bii->items)) {
1261 batch_item* bi = CONTAINING_RECORD(RemoveHeadList(&bii->items), batch_item, list_entry);
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)))
add_delete_inode_extref(device_extension * Vcb,batch_item * bi,LIST_ENTRY * listhead)1274 static void add_delete_inode_extref(device_extension* Vcb, batch_item* bi, LIST_ENTRY* listhead) {
1275 batch_item* bi2;
1276 LIST_ENTRY* le;
1277 INODE_REF* delir = (INODE_REF*)bi->data;
1278 INODE_EXTREF* ier;
1279
1280 TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1281
1282 bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
1283 if (!bi2) {
1284 ERR("out of memory\n");
1285 return;
1286 }
1287
1288 ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + delir->n, ALLOC_TAG);
1289 if (!ier) {
1290 ERR("out of memory\n");
1291 ExFreePool(bi2);
1292 return;
1293 }
1294
1295 ier->dir = bi->key.offset;
1296 ier->index = delir->index;
1297 ier->n = delir->n;
1298 RtlCopyMemory(ier->name, delir->name, delir->n);
1299
1300 bi2->key.obj_id = bi->key.obj_id;
1301 bi2->key.obj_type = TYPE_INODE_EXTREF;
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;
1305 bi2->operation = Batch_DeleteInodeExtRef;
1306
1307 le = bi->list_entry.Flink;
1308 while (le != listhead) {
1309 batch_item* bi3 = CONTAINING_RECORD(le, batch_item, list_entry);
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)))
handle_batch_collision(device_extension * Vcb,batch_item * bi,tree * t,tree_data * td,tree_data * newtd,LIST_ENTRY * listhead,bool * ignore)1323 static NTSTATUS handle_batch_collision(device_extension* Vcb, batch_item* bi, tree* t, tree_data* td, tree_data* newtd, LIST_ENTRY* listhead, bool* ignore) {
1324 if (bi->operation == Batch_Delete || bi->operation == Batch_SetXattr || bi->operation == Batch_DirItem || bi->operation == Batch_InodeRef ||
1325 bi->operation == Batch_InodeExtRef || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
1326 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) {
1327 uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node));
1328
1329 switch (bi->operation) {
1330 case Batch_SetXattr: {
1331 if (td->size < sizeof(DIR_ITEM)) {
1332 ERR("(%I64x,%x,%I64x) was %u bytes, expected at least %Iu\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset, td->size, sizeof(DIR_ITEM));
1333 } else {
1334 uint8_t* newdata;
1335 ULONG size = td->size;
1336 DIR_ITEM* newxa = (DIR_ITEM*)bi->data;
1337 DIR_ITEM* xa = (DIR_ITEM*)td->data;
1338
1339 while (true) {
1340 ULONG oldxasize;
1341
1342 if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
1343 ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1344 break;
1345 }
1346
1347 oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;
1348
1349 if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) {
1350 uint64_t pos;
1351
1352 // replace
1353
1354 if (td->size + bi->datalen - oldxasize > maxlen)
1355 ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->size, bi->datalen, oldxasize, maxlen);
1356
1357 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG);
1358 if (!newdata) {
1359 ERR("out of memory\n");
1360 return STATUS_INSUFFICIENT_RESOURCES;
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");
1392 return STATUS_INSUFFICIENT_RESOURCES;
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");
1426 return STATUS_INSUFFICIENT_RESOURCES;
1427 }
1428
1429 RtlCopyMemory(newdata, td->data, td->size);
1430
1431 RtlCopyMemory(newdata + td->size, bi->data, bi->datalen);
1432
1433 bi->datalen += td->size;
1434
1435 ExFreePool(bi->data);
1436 bi->data = newdata;
1437
1438 break;
1439 }
1440
1441 case Batch_InodeRef: {
1442 uint8_t* newdata;
1443
1444 if (td->size + bi->datalen > maxlen) {
1445 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1446 INODE_REF* ir = (INODE_REF*)bi->data;
1447 INODE_EXTREF* ier;
1448 uint16_t ierlen;
1449 batch_item* bi2;
1450 LIST_ENTRY* le;
1451 bool inserted = false;
1452
1453 TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n");
1454
1455 ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n);
1456
1457 ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG);
1458 if (!ier) {
1459 ERR("out of memory\n");
1460 return STATUS_INSUFFICIENT_RESOURCES;
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);
1472 return STATUS_INSUFFICIENT_RESOURCES;
1473 }
1474
1475 bi2->key.obj_id = bi->key.obj_id;
1476 bi2->key.obj_type = TYPE_INODE_EXTREF;
1477 bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n);
1478 bi2->data = ier;
1479 bi2->datalen = ierlen;
1480 bi2->operation = Batch_InodeExtRef;
1481
1482 le = bi->list_entry.Flink;
1483 while (le != listhead) {
1484 batch_item* bi3 = CONTAINING_RECORD(le, batch_item, list_entry);
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");
1508 return STATUS_INSUFFICIENT_RESOURCES;
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");
1534 return STATUS_INSUFFICIENT_RESOURCES;
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");
1573 return STATUS_INSUFFICIENT_RESOURCES;
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);
1592 return STATUS_INSUFFICIENT_RESOURCES;
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");
1660 return STATUS_INSUFFICIENT_RESOURCES;
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);
1679 return STATUS_INSUFFICIENT_RESOURCES;
1680 }
1681
1682 td2->key = bi->key;
1683 td2->size = newlen;
1684 td2->data = newir;
1685 td2->ignore = false;
1686 td2->inserted = true;
1687
1688 InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1689
1690 t->header.num_items++;
1691 t->size += newlen + sizeof(leaf_node);
1692 t->write = true;
1693 }
1694
1695 break;
1696 }
1697
1698 if (len > itemlen) {
1699 len -= itemlen;
1700 ir = (INODE_REF*)&ir->name[ir->n];
1701 } else
1702 break;
1703 } while (len > 0);
1704
1705 if (!changed) {
1706 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
1707 TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n");
1708
1709 add_delete_inode_extref(Vcb, bi, listhead);
1710
1711 *ignore = true;
1712 return STATUS_SUCCESS;
1713 } else
1714 WARN("entry not found in INODE_REF\n");
1715 }
1716 }
1717
1718 break;
1719 }
1720
1721 case Batch_DeleteInodeExtRef: {
1722 if (td->size < sizeof(INODE_EXTREF)) {
1723 ERR("INODE_EXTREF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_EXTREF));
1724 return STATUS_INTERNAL_ERROR;
1725 } else {
1726 INODE_EXTREF *ier, *delier;
1727 ULONG len;
1728
1729 delier = (INODE_EXTREF*)bi->data;
1730 ier = (INODE_EXTREF*)td->data;
1731 len = td->size;
1732
1733 do {
1734 uint16_t itemlen;
1735
1736 if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) {
1737 ERR("INODE_REF was truncated\n");
1738 break;
1739 }
1740
1741 itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n;
1742
1743 if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) {
1744 uint16_t newlen = td->size - itemlen;
1745
1746 if (newlen == 0)
1747 TRACE("deleting INODE_EXTREF\n");
1748 else {
1749 uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff;
1750 tree_data* td2;
1751
1752 if (!newier) {
1753 ERR("out of memory\n");
1754 return STATUS_INSUFFICIENT_RESOURCES;
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);
1773 return STATUS_INSUFFICIENT_RESOURCES;
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");
1826 return STATUS_INSUFFICIENT_RESOURCES;
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);
1844 return STATUS_INSUFFICIENT_RESOURCES;
1845 }
1846
1847 td2->key = bi->key;
1848 td2->size = newlen;
1849 td2->data = newdi;
1850 td2->ignore = false;
1851 td2->inserted = true;
1852
1853 InsertHeadList(td->list_entry.Blink, &td2->list_entry);
1854
1855 t->header.num_items++;
1856 t->size += newlen + sizeof(leaf_node);
1857 t->write = true;
1858 }
1859
1860 break;
1861 }
1862
1863 len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m;
1864 di = (DIR_ITEM*)&di->name[di->n + di->m];
1865
1866 if (len == 0) {
1867 TRACE("could not find DIR_ITEM to delete\n");
1868 *ignore = true;
1869 return STATUS_SUCCESS;
1870 }
1871 } while (len > 0);
1872 }
1873 break;
1874 }
1875
1876 case Batch_Delete:
1877 break;
1878
1879 default:
1880 ERR("unexpected batch operation type\n");
1881 return STATUS_INTERNAL_ERROR;
1882 }
1883
1884 // delete old item
1885 if (!td->ignore) {
1886 td->ignore = true;
1887
1888 t->header.num_items--;
1889 t->size -= sizeof(leaf_node) + td->size;
1890 t->write = true;
1891 }
1892
1893 if (newtd) {
1894 newtd->data = bi->data;
1895 newtd->size = bi->datalen;
1896 InsertHeadList(td->list_entry.Blink, &newtd->list_entry);
1897 }
1898 } else {
1899 ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1900 return STATUS_INTERNAL_ERROR;
1901 }
1902
1903 *ignore = false;
1904 return STATUS_SUCCESS;
1905 }
1906
1907 __attribute__((nonnull(1,2)))
1908 static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, batch_root* br, PIRP Irp) {
1909 LIST_ENTRY items;
1910 LIST_ENTRY* le;
1911 NTSTATUS Status;
1912
1913 TRACE("root: %I64x\n", br->r->id);
1914
1915 InitializeListHead(&items);
1916
1917 // move sub-lists into one big list
1918
1919 while (!IsListEmpty(&br->items_ind)) {
1920 batch_item_ind* bii = CONTAINING_RECORD(RemoveHeadList(&br->items_ind), batch_item_ind, list_entry);
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) {
1932 batch_item* bi = CONTAINING_RECORD(le, batch_item, list_entry);
1933 LIST_ENTRY* le2;
1934 traverse_ptr tp;
1935 KEY tree_end;
1936 bool no_end;
1937 tree_data *td, *listhead;
1938 int cmp;
1939 tree* t;
1940 bool ignore = false;
1941
1942 TRACE("(%I64x,%x,%I64x)\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset);
1943
1944 Status = find_item(Vcb, br->r, &tp, &bi->key, true, Irp);
1945 if (!NT_SUCCESS(Status)) { // FIXME - handle STATUS_NOT_FOUND
1946 ERR("find_item returned %08lx\n", Status);
1947 return Status;
1948 }
1949
1950 Status = find_tree_end(tp.tree, &tree_end, &no_end);
1951 if (!NT_SUCCESS(Status)) {
1952 ERR("find_tree_end returned %08lx\n", Status);
1953 return Status;
1954 }
1955
1956 if (bi->operation == Batch_DeleteInode) {
1957 if (tp.item->key.obj_id == bi->key.obj_id) {
1958 bool ended = false;
1959
1960 td = tp.item;
1961
1962 if (!tp.item->ignore) {
1963 tp.item->ignore = true;
1964 tp.tree->header.num_items--;
1965 tp.tree->size -= tp.item->size + sizeof(leaf_node);
1966 tp.tree->write = true;
1967 }
1968
1969 le2 = tp.item->list_entry.Flink;
1970 while (le2 != &tp.tree->itemlist) {
1971 td = CONTAINING_RECORD(le2, tree_data, list_entry);
1972
1973 if (td->key.obj_id == bi->key.obj_id) {
1974 if (!td->ignore) {
1975 td->ignore = true;
1976 tp.tree->header.num_items--;
1977 tp.tree->size -= td->size + sizeof(leaf_node);
1978 tp.tree->write = true;
1979 }
1980 } else {
1981 ended = true;
1982 break;
1983 }
1984
1985 le2 = le2->Flink;
1986 }
1987
1988 while (!ended) {
1989 traverse_ptr next_tp;
1990
1991 tp.item = td;
1992
1993 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1994 break;
1995
1996 tp = next_tp;
1997
1998 le2 = &tp.item->list_entry;
1999 while (le2 != &tp.tree->itemlist) {
2000 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2001
2002 if (td->key.obj_id == bi->key.obj_id) {
2003 if (!td->ignore) {
2004 td->ignore = true;
2005 tp.tree->header.num_items--;
2006 tp.tree->size -= td->size + sizeof(leaf_node);
2007 tp.tree->write = true;
2008 }
2009 } else {
2010 ended = true;
2011 break;
2012 }
2013
2014 le2 = le2->Flink;
2015 }
2016 }
2017 }
2018 } else if (bi->operation == Batch_DeleteExtentData) {
2019 if (tp.item->key.obj_id < bi->key.obj_id || (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type < bi->key.obj_type)) {
2020 traverse_ptr tp2;
2021
2022 if (find_next_item(Vcb, &tp, &tp2, false, Irp)) {
2023 if (tp2.item->key.obj_id == bi->key.obj_id && tp2.item->key.obj_type == bi->key.obj_type) {
2024 tp = tp2;
2025 Status = find_tree_end(tp.tree, &tree_end, &no_end);
2026 if (!NT_SUCCESS(Status)) {
2027 ERR("find_tree_end returned %08lx\n", Status);
2028 return Status;
2029 }
2030 }
2031 }
2032 }
2033
2034 if (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type == bi->key.obj_type) {
2035 bool ended = false;
2036
2037 td = tp.item;
2038
2039 if (!tp.item->ignore) {
2040 tp.item->ignore = true;
2041 tp.tree->header.num_items--;
2042 tp.tree->size -= tp.item->size + sizeof(leaf_node);
2043 tp.tree->write = true;
2044 }
2045
2046 le2 = tp.item->list_entry.Flink;
2047 while (le2 != &tp.tree->itemlist) {
2048 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2049
2050 if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2051 if (!td->ignore) {
2052 td->ignore = true;
2053 tp.tree->header.num_items--;
2054 tp.tree->size -= td->size + sizeof(leaf_node);
2055 tp.tree->write = true;
2056 }
2057 } else {
2058 ended = true;
2059 break;
2060 }
2061
2062 le2 = le2->Flink;
2063 }
2064
2065 while (!ended) {
2066 traverse_ptr next_tp;
2067
2068 tp.item = td;
2069
2070 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2071 break;
2072
2073 tp = next_tp;
2074
2075 le2 = &tp.item->list_entry;
2076 while (le2 != &tp.tree->itemlist) {
2077 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2078
2079 if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) {
2080 if (!td->ignore) {
2081 td->ignore = true;
2082 tp.tree->header.num_items--;
2083 tp.tree->size -= td->size + sizeof(leaf_node);
2084 tp.tree->write = true;
2085 }
2086 } else {
2087 ended = true;
2088 break;
2089 }
2090
2091 le2 = le2->Flink;
2092 }
2093 }
2094 }
2095 } else if (bi->operation == Batch_DeleteFreeSpace) {
2096 if (tp.item->key.obj_id >= bi->key.obj_id && tp.item->key.obj_id < bi->key.obj_id + bi->key.offset) {
2097 bool ended = false;
2098
2099 td = tp.item;
2100
2101 if (!tp.item->ignore) {
2102 tp.item->ignore = true;
2103 tp.tree->header.num_items--;
2104 tp.tree->size -= tp.item->size + sizeof(leaf_node);
2105 tp.tree->write = true;
2106 }
2107
2108 le2 = tp.item->list_entry.Flink;
2109 while (le2 != &tp.tree->itemlist) {
2110 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2111
2112 if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2113 if (!td->ignore) {
2114 td->ignore = true;
2115 tp.tree->header.num_items--;
2116 tp.tree->size -= td->size + sizeof(leaf_node);
2117 tp.tree->write = true;
2118 }
2119 } else {
2120 ended = true;
2121 break;
2122 }
2123
2124 le2 = le2->Flink;
2125 }
2126
2127 while (!ended) {
2128 traverse_ptr next_tp;
2129
2130 tp.item = td;
2131
2132 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
2133 break;
2134
2135 tp = next_tp;
2136
2137 le2 = &tp.item->list_entry;
2138 while (le2 != &tp.tree->itemlist) {
2139 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2140
2141 if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) {
2142 if (!td->ignore) {
2143 td->ignore = true;
2144 tp.tree->header.num_items--;
2145 tp.tree->size -= td->size + sizeof(leaf_node);
2146 tp.tree->write = true;
2147 }
2148 } else {
2149 ended = true;
2150 break;
2151 }
2152
2153 le2 = le2->Flink;
2154 }
2155 }
2156 }
2157 } else {
2158 if (bi->operation == Batch_Delete || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
2159 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr)
2160 td = NULL;
2161 else {
2162 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2163 if (!td) {
2164 ERR("out of memory\n");
2165 return STATUS_INSUFFICIENT_RESOURCES;
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
2181 InsertHeadList(&tp.tree->itemlist, &td->list_entry);
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)
2196 InsertHeadList(tp.item->list_entry.Blink, &td->list_entry);
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) {
2212 InsertHeadList(&tp.item->list_entry, &td->list_entry);
2213 }
2214
2215 if (bi->operation == Batch_DeleteInodeRef && cmp != 0 && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2216 add_delete_inode_extref(Vcb, bi, &items);
2217 }
2218
2219 if (!ignore && td) {
2220 tp.tree->header.num_items++;
2221 tp.tree->size += bi->datalen + sizeof(leaf_node);
2222 tp.tree->write = true;
2223
2224 listhead = td;
2225 } else
2226 listhead = tp.item;
2227
2228 while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2229 tree_data* prevtd = CONTAINING_RECORD(listhead->list_entry.Blink, tree_data, list_entry);
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) {
2239 batch_item* bi2 = CONTAINING_RECORD(le2, batch_item, list_entry);
2240
2241 if (bi2->operation == Batch_DeleteInode || bi2->operation == Batch_DeleteExtentData || bi2->operation == Batch_DeleteFreeSpace)
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
2250 if (bi2->operation == Batch_Delete || bi2->operation == Batch_DeleteDirItem || bi2->operation == Batch_DeleteInodeRef ||
2251 bi2->operation == Batch_DeleteInodeExtRef || bi2->operation == Batch_DeleteXattr)
2252 td = NULL;
2253 else {
2254 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2255 if (!td) {
2256 ERR("out of memory\n");
2257 return STATUS_INSUFFICIENT_RESOURCES;
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) {
2269 tree_data* td2 = CONTAINING_RECORD(le3, tree_data, list_entry);
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)
2309 InsertTailList(&tp.tree->itemlist, &td->list_entry);
2310
2311 if (!ignore) {
2312 tp.tree->header.num_items++;
2313 tp.tree->size += bi2->datalen + sizeof(leaf_node);
2314
2315 listhead = td;
2316 }
2317 } else if (!inserted && bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
2318 add_delete_inode_extref(Vcb, bi2, &items);
2319 }
2320
2321 while (listhead->list_entry.Blink != &tp.tree->itemlist) {
2322 tree_data* prevtd = CONTAINING_RECORD(listhead->list_entry.Blink, tree_data, list_entry);
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)) {
2355 batch_item* bi = CONTAINING_RECORD(RemoveHeadList(&items), batch_item, list_entry);
2356
2357 if ((bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef ||
2358 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) && bi->data)
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)))
2368 NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, LIST_ENTRY* batchlist, PIRP Irp) {
2369 NTSTATUS Status;
2370
2371 while (!IsListEmpty(batchlist)) {
2372 LIST_ENTRY* le = RemoveHeadList(batchlist);
2373 batch_root* br2 = CONTAINING_RECORD(le, batch_root, list_entry);
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 }
2386