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