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