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