drivers/filesystems/btrfs/treefuncs.c

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