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