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