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)) { 1258 LIST_ENTRY* le2 = RemoveHeadList(&br->items); 1259 batch_item* bi = CONTAINING_RECORD(le2, batch_item, list_entry); 1260 1261 ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi); 1262 } 1263 1264 ExFreePool(br); 1265 } 1266 } 1267 1268 __attribute__((nonnull(1,2,3))) 1269 static void add_delete_inode_extref(device_extension* Vcb, batch_item* bi, LIST_ENTRY* listhead) { 1270 batch_item* bi2; 1271 LIST_ENTRY* le; 1272 INODE_REF* delir = (INODE_REF*)bi->data; 1273 INODE_EXTREF* ier; 1274 1275 TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n"); 1276 1277 bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside); 1278 if (!bi2) { 1279 ERR("out of memory\n"); 1280 return; 1281 } 1282 1283 ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + delir->n, ALLOC_TAG); 1284 if (!ier) { 1285 ERR("out of memory\n"); 1286 ExFreePool(bi2); 1287 return; 1288 } 1289 1290 ier->dir = bi->key.offset; 1291 ier->index = delir->index; 1292 ier->n = delir->n; 1293 RtlCopyMemory(ier->name, delir->name, delir->n); 1294 1295 bi2->key.obj_id = bi->key.obj_id; 1296 bi2->key.obj_type = TYPE_INODE_EXTREF; 1297 bi2->key.offset = calc_crc32c((uint32_t)bi->key.offset, (uint8_t*)ier->name, ier->n); 1298 bi2->data = ier; 1299 bi2->datalen = sizeof(INODE_EXTREF) - 1 + ier->n; 1300 bi2->operation = Batch_DeleteInodeExtRef; 1301 1302 le = bi->list_entry.Flink; 1303 while (le != listhead) { 1304 batch_item* bi3 = CONTAINING_RECORD(le, batch_item, list_entry); 1305 1306 if (keycmp(bi3->key, bi2->key) != -1) { 1307 InsertHeadList(le->Blink, &bi2->list_entry); 1308 return; 1309 } 1310 1311 le = le->Flink; 1312 } 1313 1314 InsertTailList(listhead, &bi2->list_entry); 1315 } 1316 1317 __attribute__((nonnull(1,2,3,4,6,7))) 1318 static NTSTATUS handle_batch_collision(device_extension* Vcb, batch_item* bi, tree* t, tree_data* td, tree_data* newtd, LIST_ENTRY* listhead, bool* ignore) { 1319 if (bi->operation == Batch_Delete || bi->operation == Batch_SetXattr || bi->operation == Batch_DirItem || bi->operation == Batch_InodeRef || 1320 bi->operation == Batch_InodeExtRef || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef || 1321 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) { 1322 uint16_t maxlen = (uint16_t)(Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node)); 1323 1324 switch (bi->operation) { 1325 case Batch_SetXattr: { 1326 if (td->size < sizeof(DIR_ITEM)) { 1327 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)); 1328 } else { 1329 uint8_t* newdata; 1330 ULONG size = td->size; 1331 DIR_ITEM* newxa = (DIR_ITEM*)bi->data; 1332 DIR_ITEM* xa = (DIR_ITEM*)td->data; 1333 1334 while (true) { 1335 ULONG oldxasize; 1336 1337 if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) { 1338 ERR("(%I64x,%x,%I64x) was truncated\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset); 1339 break; 1340 } 1341 1342 oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n; 1343 1344 if (xa->n == newxa->n && RtlCompareMemory(newxa->name, xa->name, xa->n) == xa->n) { 1345 uint64_t pos; 1346 1347 // replace 1348 1349 if (td->size + bi->datalen - oldxasize > maxlen) 1350 ERR("DIR_ITEM would be over maximum size, truncating (%u + %u - %lu > %u)\n", td->size, bi->datalen, oldxasize, maxlen); 1351 1352 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen - oldxasize, ALLOC_TAG); 1353 if (!newdata) { 1354 ERR("out of memory\n"); 1355 return STATUS_INSUFFICIENT_RESOURCES; 1356 } 1357 1358 pos = (uint8_t*)xa - td->data; 1359 if (pos + oldxasize < td->size) // copy after changed xattr 1360 RtlCopyMemory(newdata + pos + bi->datalen, td->data + pos + oldxasize, (ULONG)(td->size - pos - oldxasize)); 1361 1362 if (pos > 0) { // copy before changed xattr 1363 RtlCopyMemory(newdata, td->data, (ULONG)pos); 1364 xa = (DIR_ITEM*)(newdata + pos); 1365 } else 1366 xa = (DIR_ITEM*)newdata; 1367 1368 RtlCopyMemory(xa, bi->data, bi->datalen); 1369 1370 bi->datalen = (uint16_t)min(td->size + bi->datalen - oldxasize, maxlen); 1371 1372 ExFreePool(bi->data); 1373 bi->data = newdata; 1374 1375 break; 1376 } 1377 1378 if ((uint8_t*)xa - (uint8_t*)td->data + oldxasize >= size) { 1379 // not found, add to end of data 1380 1381 if (td->size + bi->datalen > maxlen) 1382 ERR("DIR_ITEM would be over maximum size, truncating (%u + %u > %u)\n", td->size, bi->datalen, maxlen); 1383 1384 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG); 1385 if (!newdata) { 1386 ERR("out of memory\n"); 1387 return STATUS_INSUFFICIENT_RESOURCES; 1388 } 1389 1390 RtlCopyMemory(newdata, td->data, td->size); 1391 1392 xa = (DIR_ITEM*)((uint8_t*)newdata + td->size); 1393 RtlCopyMemory(xa, bi->data, bi->datalen); 1394 1395 bi->datalen = min(bi->datalen + td->size, maxlen); 1396 1397 ExFreePool(bi->data); 1398 bi->data = newdata; 1399 1400 break; 1401 } else { 1402 xa = (DIR_ITEM*)&xa->name[xa->m + xa->n]; 1403 size -= oldxasize; 1404 } 1405 } 1406 } 1407 break; 1408 } 1409 1410 case Batch_DirItem: { 1411 uint8_t* newdata; 1412 1413 if (td->size + bi->datalen > maxlen) { 1414 ERR("DIR_ITEM would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen); 1415 return STATUS_INTERNAL_ERROR; 1416 } 1417 1418 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG); 1419 if (!newdata) { 1420 ERR("out of memory\n"); 1421 return STATUS_INSUFFICIENT_RESOURCES; 1422 } 1423 1424 RtlCopyMemory(newdata, td->data, td->size); 1425 1426 RtlCopyMemory(newdata + td->size, bi->data, bi->datalen); 1427 1428 bi->datalen += td->size; 1429 1430 ExFreePool(bi->data); 1431 bi->data = newdata; 1432 1433 break; 1434 } 1435 1436 case Batch_InodeRef: { 1437 uint8_t* newdata; 1438 1439 if (td->size + bi->datalen > maxlen) { 1440 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 1441 INODE_REF* ir = (INODE_REF*)bi->data; 1442 INODE_EXTREF* ier; 1443 uint16_t ierlen; 1444 batch_item* bi2; 1445 LIST_ENTRY* le; 1446 bool inserted = false; 1447 1448 TRACE("INODE_REF would be too long, adding INODE_EXTREF instead\n"); 1449 1450 ierlen = (uint16_t)(offsetof(INODE_EXTREF, name[0]) + ir->n); 1451 1452 ier = ExAllocatePoolWithTag(PagedPool, ierlen, ALLOC_TAG); 1453 if (!ier) { 1454 ERR("out of memory\n"); 1455 return STATUS_INSUFFICIENT_RESOURCES; 1456 } 1457 1458 ier->dir = bi->key.offset; 1459 ier->index = ir->index; 1460 ier->n = ir->n; 1461 RtlCopyMemory(ier->name, ir->name, ier->n); 1462 1463 bi2 = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside); 1464 if (!bi2) { 1465 ERR("out of memory\n"); 1466 ExFreePool(ier); 1467 return STATUS_INSUFFICIENT_RESOURCES; 1468 } 1469 1470 bi2->key.obj_id = bi->key.obj_id; 1471 bi2->key.obj_type = TYPE_INODE_EXTREF; 1472 bi2->key.offset = calc_crc32c((uint32_t)ier->dir, (uint8_t*)ier->name, ier->n); 1473 bi2->data = ier; 1474 bi2->datalen = ierlen; 1475 bi2->operation = Batch_InodeExtRef; 1476 1477 le = bi->list_entry.Flink; 1478 while (le != listhead) { 1479 batch_item* bi3 = CONTAINING_RECORD(le, batch_item, list_entry); 1480 1481 if (keycmp(bi3->key, bi2->key) != -1) { 1482 InsertHeadList(le->Blink, &bi2->list_entry); 1483 inserted = true; 1484 } 1485 1486 le = le->Flink; 1487 } 1488 1489 if (!inserted) 1490 InsertTailList(listhead, &bi2->list_entry); 1491 1492 *ignore = true; 1493 return STATUS_SUCCESS; 1494 } else { 1495 ERR("INODE_REF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen); 1496 return STATUS_INTERNAL_ERROR; 1497 } 1498 } 1499 1500 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG); 1501 if (!newdata) { 1502 ERR("out of memory\n"); 1503 return STATUS_INSUFFICIENT_RESOURCES; 1504 } 1505 1506 RtlCopyMemory(newdata, td->data, td->size); 1507 1508 RtlCopyMemory(newdata + td->size, bi->data, bi->datalen); 1509 1510 bi->datalen += td->size; 1511 1512 ExFreePool(bi->data); 1513 bi->data = newdata; 1514 1515 break; 1516 } 1517 1518 case Batch_InodeExtRef: { 1519 uint8_t* newdata; 1520 1521 if (td->size + bi->datalen > maxlen) { 1522 ERR("INODE_EXTREF would be over maximum size (%u + %u > %u)\n", td->size, bi->datalen, maxlen); 1523 return STATUS_INTERNAL_ERROR; 1524 } 1525 1526 newdata = ExAllocatePoolWithTag(PagedPool, td->size + bi->datalen, ALLOC_TAG); 1527 if (!newdata) { 1528 ERR("out of memory\n"); 1529 return STATUS_INSUFFICIENT_RESOURCES; 1530 } 1531 1532 RtlCopyMemory(newdata, td->data, td->size); 1533 1534 RtlCopyMemory(newdata + td->size, bi->data, bi->datalen); 1535 1536 bi->datalen += td->size; 1537 1538 ExFreePool(bi->data); 1539 bi->data = newdata; 1540 1541 break; 1542 } 1543 1544 case Batch_DeleteDirItem: { 1545 if (td->size < sizeof(DIR_ITEM)) { 1546 ERR("DIR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM)); 1547 return STATUS_INTERNAL_ERROR; 1548 } else { 1549 DIR_ITEM *di, *deldi; 1550 LONG len; 1551 1552 deldi = (DIR_ITEM*)bi->data; 1553 di = (DIR_ITEM*)td->data; 1554 len = td->size; 1555 1556 do { 1557 if (di->m == deldi->m && di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n + di->m) == di->n + di->m) { 1558 uint16_t newlen = td->size - (sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m); 1559 1560 if (newlen == 0) { 1561 TRACE("deleting DIR_ITEM\n"); 1562 } else { 1563 uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff; 1564 tree_data* td2; 1565 1566 if (!newdi) { 1567 ERR("out of memory\n"); 1568 return STATUS_INSUFFICIENT_RESOURCES; 1569 } 1570 1571 TRACE("modifying DIR_ITEM\n"); 1572 1573 if ((uint8_t*)di > td->data) { 1574 RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data); 1575 dioff = newdi + ((uint8_t*)di - td->data); 1576 } else { 1577 dioff = newdi; 1578 } 1579 1580 if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size) 1581 RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data)); 1582 1583 td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 1584 if (!td2) { 1585 ERR("out of memory\n"); 1586 ExFreePool(newdi); 1587 return STATUS_INSUFFICIENT_RESOURCES; 1588 } 1589 1590 td2->key = bi->key; 1591 td2->size = newlen; 1592 td2->data = newdi; 1593 td2->ignore = false; 1594 td2->inserted = true; 1595 1596 InsertHeadList(td->list_entry.Blink, &td2->list_entry); 1597 1598 t->header.num_items++; 1599 t->size += newlen + sizeof(leaf_node); 1600 t->write = true; 1601 } 1602 1603 break; 1604 } 1605 1606 len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m; 1607 di = (DIR_ITEM*)&di->name[di->n + di->m]; 1608 1609 if (len == 0) { 1610 TRACE("could not find DIR_ITEM to delete\n"); 1611 *ignore = true; 1612 return STATUS_SUCCESS; 1613 } 1614 } while (len > 0); 1615 } 1616 break; 1617 } 1618 1619 case Batch_DeleteInodeRef: { 1620 if (td->size < sizeof(INODE_REF)) { 1621 ERR("INODE_REF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_REF)); 1622 return STATUS_INTERNAL_ERROR; 1623 } else { 1624 INODE_REF *ir, *delir; 1625 ULONG len; 1626 bool changed = false; 1627 1628 delir = (INODE_REF*)bi->data; 1629 ir = (INODE_REF*)td->data; 1630 len = td->size; 1631 1632 do { 1633 uint16_t itemlen; 1634 1635 if (len < sizeof(INODE_REF) || len < offsetof(INODE_REF, name[0]) + ir->n) { 1636 ERR("INODE_REF was truncated\n"); 1637 break; 1638 } 1639 1640 itemlen = (uint16_t)offsetof(INODE_REF, name[0]) + ir->n; 1641 1642 if (ir->n == delir->n && RtlCompareMemory(ir->name, delir->name, ir->n) == ir->n) { 1643 uint16_t newlen = td->size - itemlen; 1644 1645 changed = true; 1646 1647 if (newlen == 0) 1648 TRACE("deleting INODE_REF\n"); 1649 else { 1650 uint8_t *newir = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *iroff; 1651 tree_data* td2; 1652 1653 if (!newir) { 1654 ERR("out of memory\n"); 1655 return STATUS_INSUFFICIENT_RESOURCES; 1656 } 1657 1658 TRACE("modifying INODE_REF\n"); 1659 1660 if ((uint8_t*)ir > td->data) { 1661 RtlCopyMemory(newir, td->data, (uint8_t*)ir - td->data); 1662 iroff = newir + ((uint8_t*)ir - td->data); 1663 } else { 1664 iroff = newir; 1665 } 1666 1667 if ((uint8_t*)&ir->name[ir->n] < td->data + td->size) 1668 RtlCopyMemory(iroff, &ir->name[ir->n], td->size - ((uint8_t*)&ir->name[ir->n] - td->data)); 1669 1670 td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 1671 if (!td2) { 1672 ERR("out of memory\n"); 1673 ExFreePool(newir); 1674 return STATUS_INSUFFICIENT_RESOURCES; 1675 } 1676 1677 td2->key = bi->key; 1678 td2->size = newlen; 1679 td2->data = newir; 1680 td2->ignore = false; 1681 td2->inserted = true; 1682 1683 InsertHeadList(td->list_entry.Blink, &td2->list_entry); 1684 1685 t->header.num_items++; 1686 t->size += newlen + sizeof(leaf_node); 1687 t->write = true; 1688 } 1689 1690 break; 1691 } 1692 1693 if (len > itemlen) { 1694 len -= itemlen; 1695 ir = (INODE_REF*)&ir->name[ir->n]; 1696 } else 1697 break; 1698 } while (len > 0); 1699 1700 if (!changed) { 1701 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 1702 TRACE("entry in INODE_REF not found, adding Batch_DeleteInodeExtRef entry\n"); 1703 1704 add_delete_inode_extref(Vcb, bi, listhead); 1705 1706 *ignore = true; 1707 return STATUS_SUCCESS; 1708 } else 1709 WARN("entry not found in INODE_REF\n"); 1710 } 1711 } 1712 1713 break; 1714 } 1715 1716 case Batch_DeleteInodeExtRef: { 1717 if (td->size < sizeof(INODE_EXTREF)) { 1718 ERR("INODE_EXTREF was %u bytes, expected at least %Iu\n", td->size, sizeof(INODE_EXTREF)); 1719 return STATUS_INTERNAL_ERROR; 1720 } else { 1721 INODE_EXTREF *ier, *delier; 1722 ULONG len; 1723 1724 delier = (INODE_EXTREF*)bi->data; 1725 ier = (INODE_EXTREF*)td->data; 1726 len = td->size; 1727 1728 do { 1729 uint16_t itemlen; 1730 1731 if (len < sizeof(INODE_EXTREF) || len < offsetof(INODE_EXTREF, name[0]) + ier->n) { 1732 ERR("INODE_REF was truncated\n"); 1733 break; 1734 } 1735 1736 itemlen = (uint16_t)offsetof(INODE_EXTREF, name[0]) + ier->n; 1737 1738 if (ier->dir == delier->dir && ier->n == delier->n && RtlCompareMemory(ier->name, delier->name, ier->n) == ier->n) { 1739 uint16_t newlen = td->size - itemlen; 1740 1741 if (newlen == 0) 1742 TRACE("deleting INODE_EXTREF\n"); 1743 else { 1744 uint8_t *newier = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *ieroff; 1745 tree_data* td2; 1746 1747 if (!newier) { 1748 ERR("out of memory\n"); 1749 return STATUS_INSUFFICIENT_RESOURCES; 1750 } 1751 1752 TRACE("modifying INODE_EXTREF\n"); 1753 1754 if ((uint8_t*)ier > td->data) { 1755 RtlCopyMemory(newier, td->data, (uint8_t*)ier - td->data); 1756 ieroff = newier + ((uint8_t*)ier - td->data); 1757 } else { 1758 ieroff = newier; 1759 } 1760 1761 if ((uint8_t*)&ier->name[ier->n] < td->data + td->size) 1762 RtlCopyMemory(ieroff, &ier->name[ier->n], td->size - ((uint8_t*)&ier->name[ier->n] - td->data)); 1763 1764 td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 1765 if (!td2) { 1766 ERR("out of memory\n"); 1767 ExFreePool(newier); 1768 return STATUS_INSUFFICIENT_RESOURCES; 1769 } 1770 1771 td2->key = bi->key; 1772 td2->size = newlen; 1773 td2->data = newier; 1774 td2->ignore = false; 1775 td2->inserted = true; 1776 1777 InsertHeadList(td->list_entry.Blink, &td2->list_entry); 1778 1779 t->header.num_items++; 1780 t->size += newlen + sizeof(leaf_node); 1781 t->write = true; 1782 } 1783 1784 break; 1785 } 1786 1787 if (len > itemlen) { 1788 len -= itemlen; 1789 ier = (INODE_EXTREF*)&ier->name[ier->n]; 1790 } else 1791 break; 1792 } while (len > 0); 1793 } 1794 break; 1795 } 1796 1797 case Batch_DeleteXattr: { 1798 if (td->size < sizeof(DIR_ITEM)) { 1799 ERR("XATTR_ITEM was %u bytes, expected at least %Iu\n", td->size, sizeof(DIR_ITEM)); 1800 return STATUS_INTERNAL_ERROR; 1801 } else { 1802 DIR_ITEM *di, *deldi; 1803 LONG len; 1804 1805 deldi = (DIR_ITEM*)bi->data; 1806 di = (DIR_ITEM*)td->data; 1807 len = td->size; 1808 1809 do { 1810 if (di->n == deldi->n && RtlCompareMemory(di->name, deldi->name, di->n) == di->n) { 1811 uint16_t newlen = td->size - ((uint16_t)offsetof(DIR_ITEM, name[0]) + di->n + di->m); 1812 1813 if (newlen == 0) 1814 TRACE("deleting XATTR_ITEM\n"); 1815 else { 1816 uint8_t *newdi = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *dioff; 1817 tree_data* td2; 1818 1819 if (!newdi) { 1820 ERR("out of memory\n"); 1821 return STATUS_INSUFFICIENT_RESOURCES; 1822 } 1823 1824 TRACE("modifying XATTR_ITEM\n"); 1825 1826 if ((uint8_t*)di > td->data) { 1827 RtlCopyMemory(newdi, td->data, (uint8_t*)di - td->data); 1828 dioff = newdi + ((uint8_t*)di - td->data); 1829 } else 1830 dioff = newdi; 1831 1832 if ((uint8_t*)&di->name[di->n + di->m] < td->data + td->size) 1833 RtlCopyMemory(dioff, &di->name[di->n + di->m], td->size - ((uint8_t*)&di->name[di->n + di->m] - td->data)); 1834 1835 td2 = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 1836 if (!td2) { 1837 ERR("out of memory\n"); 1838 ExFreePool(newdi); 1839 return STATUS_INSUFFICIENT_RESOURCES; 1840 } 1841 1842 td2->key = bi->key; 1843 td2->size = newlen; 1844 td2->data = newdi; 1845 td2->ignore = false; 1846 td2->inserted = true; 1847 1848 InsertHeadList(td->list_entry.Blink, &td2->list_entry); 1849 1850 t->header.num_items++; 1851 t->size += newlen + sizeof(leaf_node); 1852 t->write = true; 1853 } 1854 1855 break; 1856 } 1857 1858 len -= sizeof(DIR_ITEM) - sizeof(char) + di->n + di->m; 1859 di = (DIR_ITEM*)&di->name[di->n + di->m]; 1860 1861 if (len == 0) { 1862 TRACE("could not find DIR_ITEM to delete\n"); 1863 *ignore = true; 1864 return STATUS_SUCCESS; 1865 } 1866 } while (len > 0); 1867 } 1868 break; 1869 } 1870 1871 case Batch_Delete: 1872 break; 1873 1874 default: 1875 ERR("unexpected batch operation type\n"); 1876 return STATUS_INTERNAL_ERROR; 1877 } 1878 1879 // delete old item 1880 if (!td->ignore) { 1881 td->ignore = true; 1882 1883 t->header.num_items--; 1884 t->size -= sizeof(leaf_node) + td->size; 1885 t->write = true; 1886 } 1887 1888 if (newtd) { 1889 newtd->data = bi->data; 1890 newtd->size = bi->datalen; 1891 InsertHeadList(td->list_entry.Blink, &newtd->list_entry); 1892 } 1893 } else { 1894 ERR("(%I64x,%x,%I64x) already exists\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset); 1895 return STATUS_INTERNAL_ERROR; 1896 } 1897 1898 *ignore = false; 1899 return STATUS_SUCCESS; 1900 } 1901 1902 __attribute__((nonnull(1,2))) 1903 static NTSTATUS commit_batch_list_root(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, batch_root* br, PIRP Irp) { 1904 LIST_ENTRY* le; 1905 NTSTATUS Status; 1906 1907 TRACE("root: %I64x\n", br->r->id); 1908 1909 le = br->items.Flink; 1910 while (le != &br->items) { 1911 batch_item* bi = CONTAINING_RECORD(le, batch_item, list_entry); 1912 LIST_ENTRY *le2; 1913 traverse_ptr tp; 1914 KEY tree_end; 1915 bool no_end; 1916 tree_data *td, *listhead; 1917 int cmp; 1918 tree* t; 1919 bool ignore = false; 1920 1921 TRACE("(%I64x,%x,%I64x)\n", bi->key.obj_id, bi->key.obj_type, bi->key.offset); 1922 1923 Status = find_item(Vcb, br->r, &tp, &bi->key, true, Irp); 1924 if (!NT_SUCCESS(Status)) { // FIXME - handle STATUS_NOT_FOUND 1925 ERR("find_item returned %08lx\n", Status); 1926 return Status; 1927 } 1928 1929 Status = find_tree_end(tp.tree, &tree_end, &no_end); 1930 if (!NT_SUCCESS(Status)) { 1931 ERR("find_tree_end returned %08lx\n", Status); 1932 return Status; 1933 } 1934 1935 if (bi->operation == Batch_DeleteInode) { 1936 if (tp.item->key.obj_id == bi->key.obj_id) { 1937 bool ended = false; 1938 1939 td = tp.item; 1940 1941 if (!tp.item->ignore) { 1942 tp.item->ignore = true; 1943 tp.tree->header.num_items--; 1944 tp.tree->size -= tp.item->size + sizeof(leaf_node); 1945 tp.tree->write = true; 1946 } 1947 1948 le2 = tp.item->list_entry.Flink; 1949 while (le2 != &tp.tree->itemlist) { 1950 td = CONTAINING_RECORD(le2, tree_data, list_entry); 1951 1952 if (td->key.obj_id == bi->key.obj_id) { 1953 if (!td->ignore) { 1954 td->ignore = true; 1955 tp.tree->header.num_items--; 1956 tp.tree->size -= td->size + sizeof(leaf_node); 1957 tp.tree->write = true; 1958 } 1959 } else { 1960 ended = true; 1961 break; 1962 } 1963 1964 le2 = le2->Flink; 1965 } 1966 1967 while (!ended) { 1968 traverse_ptr next_tp; 1969 1970 tp.item = td; 1971 1972 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp)) 1973 break; 1974 1975 tp = next_tp; 1976 1977 le2 = &tp.item->list_entry; 1978 while (le2 != &tp.tree->itemlist) { 1979 td = CONTAINING_RECORD(le2, tree_data, list_entry); 1980 1981 if (td->key.obj_id == bi->key.obj_id) { 1982 if (!td->ignore) { 1983 td->ignore = true; 1984 tp.tree->header.num_items--; 1985 tp.tree->size -= td->size + sizeof(leaf_node); 1986 tp.tree->write = true; 1987 } 1988 } else { 1989 ended = true; 1990 break; 1991 } 1992 1993 le2 = le2->Flink; 1994 } 1995 } 1996 } 1997 } else if (bi->operation == Batch_DeleteExtentData) { 1998 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)) { 1999 traverse_ptr tp2; 2000 2001 if (find_next_item(Vcb, &tp, &tp2, false, Irp)) { 2002 if (tp2.item->key.obj_id == bi->key.obj_id && tp2.item->key.obj_type == bi->key.obj_type) { 2003 tp = tp2; 2004 Status = find_tree_end(tp.tree, &tree_end, &no_end); 2005 if (!NT_SUCCESS(Status)) { 2006 ERR("find_tree_end returned %08lx\n", Status); 2007 return Status; 2008 } 2009 } 2010 } 2011 } 2012 2013 if (tp.item->key.obj_id == bi->key.obj_id && tp.item->key.obj_type == bi->key.obj_type) { 2014 bool ended = false; 2015 2016 td = tp.item; 2017 2018 if (!tp.item->ignore) { 2019 tp.item->ignore = true; 2020 tp.tree->header.num_items--; 2021 tp.tree->size -= tp.item->size + sizeof(leaf_node); 2022 tp.tree->write = true; 2023 } 2024 2025 le2 = tp.item->list_entry.Flink; 2026 while (le2 != &tp.tree->itemlist) { 2027 td = CONTAINING_RECORD(le2, tree_data, list_entry); 2028 2029 if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) { 2030 if (!td->ignore) { 2031 td->ignore = true; 2032 tp.tree->header.num_items--; 2033 tp.tree->size -= td->size + sizeof(leaf_node); 2034 tp.tree->write = true; 2035 } 2036 } else { 2037 ended = true; 2038 break; 2039 } 2040 2041 le2 = le2->Flink; 2042 } 2043 2044 while (!ended) { 2045 traverse_ptr next_tp; 2046 2047 tp.item = td; 2048 2049 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp)) 2050 break; 2051 2052 tp = next_tp; 2053 2054 le2 = &tp.item->list_entry; 2055 while (le2 != &tp.tree->itemlist) { 2056 td = CONTAINING_RECORD(le2, tree_data, list_entry); 2057 2058 if (td->key.obj_id == bi->key.obj_id && td->key.obj_type == bi->key.obj_type) { 2059 if (!td->ignore) { 2060 td->ignore = true; 2061 tp.tree->header.num_items--; 2062 tp.tree->size -= td->size + sizeof(leaf_node); 2063 tp.tree->write = true; 2064 } 2065 } else { 2066 ended = true; 2067 break; 2068 } 2069 2070 le2 = le2->Flink; 2071 } 2072 } 2073 } 2074 } else if (bi->operation == Batch_DeleteFreeSpace) { 2075 if (tp.item->key.obj_id >= bi->key.obj_id && tp.item->key.obj_id < bi->key.obj_id + bi->key.offset) { 2076 bool ended = false; 2077 2078 td = tp.item; 2079 2080 if (!tp.item->ignore) { 2081 tp.item->ignore = true; 2082 tp.tree->header.num_items--; 2083 tp.tree->size -= tp.item->size + sizeof(leaf_node); 2084 tp.tree->write = true; 2085 } 2086 2087 le2 = tp.item->list_entry.Flink; 2088 while (le2 != &tp.tree->itemlist) { 2089 td = CONTAINING_RECORD(le2, tree_data, list_entry); 2090 2091 if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) { 2092 if (!td->ignore) { 2093 td->ignore = true; 2094 tp.tree->header.num_items--; 2095 tp.tree->size -= td->size + sizeof(leaf_node); 2096 tp.tree->write = true; 2097 } 2098 } else { 2099 ended = true; 2100 break; 2101 } 2102 2103 le2 = le2->Flink; 2104 } 2105 2106 while (!ended) { 2107 traverse_ptr next_tp; 2108 2109 tp.item = td; 2110 2111 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp)) 2112 break; 2113 2114 tp = next_tp; 2115 2116 le2 = &tp.item->list_entry; 2117 while (le2 != &tp.tree->itemlist) { 2118 td = CONTAINING_RECORD(le2, tree_data, list_entry); 2119 2120 if (td->key.obj_id >= bi->key.obj_id && td->key.obj_id < bi->key.obj_id + bi->key.offset) { 2121 if (!td->ignore) { 2122 td->ignore = true; 2123 tp.tree->header.num_items--; 2124 tp.tree->size -= td->size + sizeof(leaf_node); 2125 tp.tree->write = true; 2126 } 2127 } else { 2128 ended = true; 2129 break; 2130 } 2131 2132 le2 = le2->Flink; 2133 } 2134 } 2135 } 2136 } else { 2137 if (bi->operation == Batch_Delete || bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef || 2138 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) 2139 td = NULL; 2140 else { 2141 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 2142 if (!td) { 2143 ERR("out of memory\n"); 2144 return STATUS_INSUFFICIENT_RESOURCES; 2145 } 2146 2147 td->key = bi->key; 2148 td->size = bi->datalen; 2149 td->data = bi->data; 2150 td->ignore = false; 2151 td->inserted = true; 2152 } 2153 2154 cmp = keycmp(bi->key, tp.item->key); 2155 2156 if (cmp == -1) { // very first key in root 2157 if (td) { 2158 tree_data* paritem; 2159 2160 InsertHeadList(&tp.tree->itemlist, &td->list_entry); 2161 2162 paritem = tp.tree->paritem; 2163 while (paritem) { 2164 if (!keycmp(paritem->key, tp.item->key)) { 2165 paritem->key = bi->key; 2166 } else 2167 break; 2168 2169 paritem = paritem->treeholder.tree->paritem; 2170 } 2171 } 2172 } else if (cmp == 0) { // item already exists 2173 if (tp.item->ignore) { 2174 if (td) 2175 InsertHeadList(tp.item->list_entry.Blink, &td->list_entry); 2176 } else { 2177 Status = handle_batch_collision(Vcb, bi, tp.tree, tp.item, td, &br->items, &ignore); 2178 if (!NT_SUCCESS(Status)) { 2179 ERR("handle_batch_collision returned %08lx\n", Status); 2180 #ifdef _DEBUG 2181 int3; 2182 #endif 2183 2184 if (td) 2185 ExFreeToPagedLookasideList(&Vcb->tree_data_lookaside, td); 2186 2187 return Status; 2188 } 2189 } 2190 } else if (td) { 2191 InsertHeadList(&tp.item->list_entry, &td->list_entry); 2192 } 2193 2194 if (bi->operation == Batch_DeleteInodeRef && cmp != 0 && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 2195 add_delete_inode_extref(Vcb, bi, &br->items); 2196 } 2197 2198 if (!ignore && td) { 2199 tp.tree->header.num_items++; 2200 tp.tree->size += bi->datalen + sizeof(leaf_node); 2201 tp.tree->write = true; 2202 2203 listhead = td; 2204 } else 2205 listhead = tp.item; 2206 2207 while (listhead->list_entry.Blink != &tp.tree->itemlist) { 2208 tree_data* prevtd = CONTAINING_RECORD(listhead->list_entry.Blink, tree_data, list_entry); 2209 2210 if (!keycmp(prevtd->key, listhead->key)) 2211 listhead = prevtd; 2212 else 2213 break; 2214 } 2215 2216 le2 = le->Flink; 2217 while (le2 != &br->items) { 2218 batch_item* bi2 = CONTAINING_RECORD(le2, batch_item, list_entry); 2219 2220 if (bi2->operation == Batch_DeleteInode || bi2->operation == Batch_DeleteExtentData || bi2->operation == Batch_DeleteFreeSpace) 2221 break; 2222 2223 if (no_end || keycmp(bi2->key, tree_end) == -1) { 2224 LIST_ENTRY* le3; 2225 bool inserted = false; 2226 2227 ignore = false; 2228 2229 if (bi2->operation == Batch_Delete || bi2->operation == Batch_DeleteDirItem || bi2->operation == Batch_DeleteInodeRef || 2230 bi2->operation == Batch_DeleteInodeExtRef || bi2->operation == Batch_DeleteXattr) 2231 td = NULL; 2232 else { 2233 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside); 2234 if (!td) { 2235 ERR("out of memory\n"); 2236 return STATUS_INSUFFICIENT_RESOURCES; 2237 } 2238 2239 td->key = bi2->key; 2240 td->size = bi2->datalen; 2241 td->data = bi2->data; 2242 td->ignore = false; 2243 td->inserted = true; 2244 } 2245 2246 le3 = &listhead->list_entry; 2247 while (le3 != &tp.tree->itemlist) { 2248 tree_data* td2 = CONTAINING_RECORD(le3, tree_data, list_entry); 2249 2250 cmp = keycmp(bi2->key, td2->key); 2251 2252 if (cmp == 0) { 2253 if (td2->ignore) { 2254 if (td) { 2255 InsertHeadList(le3->Blink, &td->list_entry); 2256 inserted = true; 2257 } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 2258 add_delete_inode_extref(Vcb, bi2, &br->items); 2259 } 2260 } else { 2261 Status = handle_batch_collision(Vcb, bi2, tp.tree, td2, td, &br->items, &ignore); 2262 if (!NT_SUCCESS(Status)) { 2263 ERR("handle_batch_collision returned %08lx\n", Status); 2264 #ifdef _DEBUG 2265 int3; 2266 #endif 2267 return Status; 2268 } 2269 } 2270 2271 inserted = true; 2272 break; 2273 } else if (cmp == -1) { 2274 if (td) { 2275 InsertHeadList(le3->Blink, &td->list_entry); 2276 inserted = true; 2277 } else if (bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 2278 add_delete_inode_extref(Vcb, bi2, &br->items); 2279 } 2280 break; 2281 } 2282 2283 le3 = le3->Flink; 2284 } 2285 2286 if (td) { 2287 if (!inserted) 2288 InsertTailList(&tp.tree->itemlist, &td->list_entry); 2289 2290 if (!ignore) { 2291 tp.tree->header.num_items++; 2292 tp.tree->size += bi2->datalen + sizeof(leaf_node); 2293 2294 listhead = td; 2295 } 2296 } else if (!inserted && bi2->operation == Batch_DeleteInodeRef && Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) { 2297 add_delete_inode_extref(Vcb, bi2, &br->items); 2298 } 2299 2300 while (listhead->list_entry.Blink != &tp.tree->itemlist) { 2301 tree_data* prevtd = CONTAINING_RECORD(listhead->list_entry.Blink, tree_data, list_entry); 2302 2303 if (!keycmp(prevtd->key, listhead->key)) 2304 listhead = prevtd; 2305 else 2306 break; 2307 } 2308 2309 le = le2; 2310 } else 2311 break; 2312 2313 le2 = le2->Flink; 2314 } 2315 2316 t = tp.tree; 2317 while (t) { 2318 if (t->paritem && t->paritem->ignore) { 2319 t->paritem->ignore = false; 2320 t->parent->header.num_items++; 2321 t->parent->size += sizeof(internal_node); 2322 } 2323 2324 t->header.generation = Vcb->superblock.generation; 2325 t = t->parent; 2326 } 2327 } 2328 2329 le = le->Flink; 2330 } 2331 2332 // FIXME - remove as we are going along 2333 while (!IsListEmpty(&br->items)) { 2334 batch_item* bi = CONTAINING_RECORD(RemoveHeadList(&br->items), batch_item, list_entry); 2335 2336 if ((bi->operation == Batch_DeleteDirItem || bi->operation == Batch_DeleteInodeRef || 2337 bi->operation == Batch_DeleteInodeExtRef || bi->operation == Batch_DeleteXattr) && bi->data) 2338 ExFreePool(bi->data); 2339 2340 ExFreeToPagedLookasideList(&Vcb->batch_item_lookaside, bi); 2341 } 2342 2343 return STATUS_SUCCESS; 2344 } 2345 2346 __attribute__((nonnull(1,2))) 2347 NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension* Vcb, LIST_ENTRY* batchlist, PIRP Irp) { 2348 NTSTATUS Status; 2349 2350 while (!IsListEmpty(batchlist)) { 2351 LIST_ENTRY* le = RemoveHeadList(batchlist); 2352 batch_root* br2 = CONTAINING_RECORD(le, batch_root, list_entry); 2353 2354 Status = commit_batch_list_root(Vcb, br2, Irp); 2355 if (!NT_SUCCESS(Status)) { 2356 ERR("commit_batch_list_root returned %08lx\n", Status); 2357 return Status; 2358 } 2359 2360 ExFreePool(br2); 2361 } 2362 2363 return STATUS_SUCCESS; 2364 } 2365