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