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 // Number of increments in the size of each cache inode, in sectors. Should 22 // this be a constant number of sectors, a constant 256 KB, or what? 23 #define CACHE_INCREMENTS 64 24 25 static NTSTATUS remove_free_space_inode(device_extension* Vcb, uint64_t inode, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) { 26 NTSTATUS Status; 27 fcb* fcb; 28 29 Status = open_fcb(Vcb, Vcb->root_root, inode, BTRFS_TYPE_FILE, NULL, false, NULL, &fcb, PagedPool, Irp); 30 if (!NT_SUCCESS(Status)) { 31 ERR("open_fcb returned %08lx\n", Status); 32 return Status; 33 } 34 35 mark_fcb_dirty(fcb); 36 37 if (fcb->inode_item.st_size > 0) { 38 Status = excise_extents(fcb->Vcb, fcb, 0, sector_align(fcb->inode_item.st_size, fcb->Vcb->superblock.sector_size), Irp, rollback); 39 if (!NT_SUCCESS(Status)) { 40 ERR("excise_extents returned %08lx\n", Status); 41 return Status; 42 } 43 } 44 45 fcb->deleted = true; 46 47 Status = flush_fcb(fcb, false, batchlist, Irp); 48 if (!NT_SUCCESS(Status)) { 49 ERR("flush_fcb returned %08lx\n", Status); 50 free_fcb(fcb); 51 return Status; 52 } 53 54 free_fcb(fcb); 55 56 return STATUS_SUCCESS; 57 } 58 59 NTSTATUS clear_free_space_cache(device_extension* Vcb, LIST_ENTRY* batchlist, PIRP Irp) { 60 KEY searchkey; 61 traverse_ptr tp, next_tp; 62 NTSTATUS Status; 63 bool b; 64 LIST_ENTRY rollback; 65 66 InitializeListHead(&rollback); 67 68 searchkey.obj_id = FREE_SPACE_CACHE_ID; 69 searchkey.obj_type = 0; 70 searchkey.offset = 0; 71 72 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 73 if (!NT_SUCCESS(Status)) { 74 ERR("error - find_item returned %08lx\n", Status); 75 return Status; 76 } 77 78 do { 79 if (tp.item->key.obj_id > searchkey.obj_id || (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type > searchkey.obj_type)) 80 break; 81 82 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) { 83 Status = delete_tree_item(Vcb, &tp); 84 if (!NT_SUCCESS(Status)) { 85 ERR("delete_tree_item returned %08lx\n", Status); 86 return Status; 87 } 88 89 if (tp.item->size >= sizeof(FREE_SPACE_ITEM)) { 90 FREE_SPACE_ITEM* fsi = (FREE_SPACE_ITEM*)tp.item->data; 91 92 if (fsi->key.obj_type != TYPE_INODE_ITEM) 93 WARN("key (%I64x,%x,%I64x) does not point to an INODE_ITEM\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset); 94 else { 95 LIST_ENTRY* le; 96 97 Status = remove_free_space_inode(Vcb, fsi->key.obj_id, batchlist, Irp, &rollback); 98 99 if (!NT_SUCCESS(Status)) 100 ERR("remove_free_space_inode for (%I64x,%x,%I64x) returned %08lx\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset, Status); 101 102 le = Vcb->chunks.Flink; 103 while (le != &Vcb->chunks) { 104 chunk* c = CONTAINING_RECORD(le, chunk, list_entry); 105 106 if (c->offset == tp.item->key.offset && c->cache) { 107 reap_fcb(c->cache); 108 c->cache = NULL; 109 } 110 111 le = le->Flink; 112 } 113 } 114 } else 115 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM)); 116 } 117 118 b = find_next_item(Vcb, &tp, &next_tp, false, Irp); 119 if (b) 120 tp = next_tp; 121 } while (b); 122 123 Status = STATUS_SUCCESS; 124 125 if (NT_SUCCESS(Status)) 126 clear_rollback(&rollback); 127 else 128 do_rollback(Vcb, &rollback); 129 130 if (Vcb->space_root) { 131 searchkey.obj_id = 0; 132 searchkey.obj_type = 0; 133 searchkey.offset = 0; 134 135 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp); 136 if (!NT_SUCCESS(Status)) { 137 ERR("find_item returned %08lx\n", Status); 138 return Status; 139 } 140 141 do { 142 Status = delete_tree_item(Vcb, &tp); 143 if (!NT_SUCCESS(Status)) { 144 ERR("delete_tree_item returned %08lx\n", Status); 145 return Status; 146 } 147 148 b = find_next_item(Vcb, &tp, &next_tp, false, Irp); 149 if (b) 150 tp = next_tp; 151 } while (b); 152 } 153 154 // regenerate free space tree 155 if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE) { 156 LIST_ENTRY* le; 157 158 ExAcquireResourceSharedLite(&Vcb->chunk_lock, true); 159 160 le = Vcb->chunks.Flink; 161 while (le != &Vcb->chunks) { 162 chunk* c = CONTAINING_RECORD(le, chunk, list_entry); 163 164 if (!c->cache_loaded) { 165 acquire_chunk_lock(c, Vcb); 166 167 Status = load_cache_chunk(Vcb, c, NULL); 168 if (!NT_SUCCESS(Status)) { 169 ERR("load_cache_chunk(%I64x) returned %08lx\n", c->offset, Status); 170 release_chunk_lock(c, Vcb); 171 ExReleaseResourceLite(&Vcb->chunk_lock); 172 return Status; 173 } 174 175 c->changed = true; 176 c->space_changed = true; 177 178 release_chunk_lock(c, Vcb); 179 } 180 181 le = le->Flink; 182 } 183 184 ExReleaseResourceLite(&Vcb->chunk_lock); 185 } 186 187 return Status; 188 } 189 190 NTSTATUS add_space_entry(LIST_ENTRY* list, LIST_ENTRY* list_size, uint64_t offset, uint64_t size) { 191 space* s; 192 193 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 194 195 if (!s) { 196 ERR("out of memory\n"); 197 return STATUS_INSUFFICIENT_RESOURCES; 198 } 199 200 s->address = offset; 201 s->size = size; 202 203 if (IsListEmpty(list)) 204 InsertTailList(list, &s->list_entry); 205 else { 206 space* s2 = CONTAINING_RECORD(list->Blink, space, list_entry); 207 208 if (s2->address < offset) 209 InsertTailList(list, &s->list_entry); 210 else { 211 LIST_ENTRY* le; 212 213 le = list->Flink; 214 while (le != list) { 215 s2 = CONTAINING_RECORD(le, space, list_entry); 216 217 if (s2->address > offset) { 218 InsertTailList(le, &s->list_entry); 219 goto size; 220 } 221 222 le = le->Flink; 223 } 224 } 225 } 226 227 size: 228 if (!list_size) 229 return STATUS_SUCCESS; 230 231 if (IsListEmpty(list_size)) 232 InsertTailList(list_size, &s->list_entry_size); 233 else { 234 space* s2 = CONTAINING_RECORD(list_size->Blink, space, list_entry_size); 235 236 if (s2->size >= size) 237 InsertTailList(list_size, &s->list_entry_size); 238 else { 239 LIST_ENTRY* le; 240 241 le = list_size->Flink; 242 while (le != list_size) { 243 s2 = CONTAINING_RECORD(le, space, list_entry_size); 244 245 if (s2->size <= size) { 246 InsertHeadList(le->Blink, &s->list_entry_size); 247 return STATUS_SUCCESS; 248 } 249 250 le = le->Flink; 251 } 252 } 253 } 254 255 return STATUS_SUCCESS; 256 } 257 258 static void load_free_space_bitmap(device_extension* Vcb, chunk* c, uint64_t offset, void* data, uint64_t* total_space) { 259 RTL_BITMAP bmph; 260 uint32_t i, len, *dwords = data; 261 ULONG runlength, index; 262 263 // flip bits 264 for (i = 0; i < Vcb->superblock.sector_size / sizeof(uint32_t); i++) { 265 dwords[i] = ~dwords[i]; 266 } 267 268 len = Vcb->superblock.sector_size * 8; 269 270 RtlInitializeBitMap(&bmph, data, len); 271 272 index = 0; 273 runlength = RtlFindFirstRunClear(&bmph, &index); 274 275 while (runlength != 0) { 276 uint64_t addr, length; 277 278 if (index >= len) 279 break; 280 281 if (index + runlength >= len) { 282 runlength = len - index; 283 284 if (runlength == 0) 285 break; 286 } 287 288 addr = offset + (index * Vcb->superblock.sector_size); 289 length = Vcb->superblock.sector_size * runlength; 290 291 add_space_entry(&c->space, &c->space_size, addr, length); 292 index += runlength; 293 *total_space += length; 294 295 runlength = RtlFindNextForwardRunClear(&bmph, index, &index); 296 } 297 } 298 299 static void order_space_entry(space* s, LIST_ENTRY* list_size) { 300 LIST_ENTRY* le; 301 302 if (IsListEmpty(list_size)) { 303 InsertHeadList(list_size, &s->list_entry_size); 304 return; 305 } 306 307 le = list_size->Flink; 308 309 while (le != list_size) { 310 space* s2 = CONTAINING_RECORD(le, space, list_entry_size); 311 312 if (s2->size <= s->size) { 313 InsertHeadList(le->Blink, &s->list_entry_size); 314 return; 315 } 316 317 le = le->Flink; 318 } 319 320 InsertTailList(list_size, &s->list_entry_size); 321 } 322 323 typedef struct { 324 uint64_t stripe; 325 LIST_ENTRY list_entry; 326 } superblock_stripe; 327 328 static NTSTATUS add_superblock_stripe(LIST_ENTRY* stripes, uint64_t off, uint64_t len) { 329 uint64_t i; 330 331 for (i = 0; i < len; i++) { 332 LIST_ENTRY* le; 333 superblock_stripe* ss; 334 bool ignore = false; 335 336 le = stripes->Flink; 337 while (le != stripes) { 338 ss = CONTAINING_RECORD(le, superblock_stripe, list_entry); 339 340 if (ss->stripe == off + i) { 341 ignore = true; 342 break; 343 } 344 345 le = le->Flink; 346 } 347 348 if (ignore) 349 continue; 350 351 ss = ExAllocatePoolWithTag(PagedPool, sizeof(superblock_stripe), ALLOC_TAG); 352 if (!ss) { 353 ERR("out of memory\n"); 354 return STATUS_INSUFFICIENT_RESOURCES; 355 } 356 357 ss->stripe = off + i; 358 InsertTailList(stripes, &ss->list_entry); 359 } 360 361 return STATUS_SUCCESS; 362 } 363 364 static NTSTATUS get_superblock_size(chunk* c, uint64_t* size) { 365 NTSTATUS Status; 366 CHUNK_ITEM* ci = c->chunk_item; 367 CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&ci[1]; 368 uint64_t off_start, off_end, space = 0; 369 uint16_t i = 0, j; 370 LIST_ENTRY stripes; 371 372 InitializeListHead(&stripes); 373 374 while (superblock_addrs[i] != 0) { 375 if (ci->type & BLOCK_FLAG_RAID0 || ci->type & BLOCK_FLAG_RAID10) { 376 for (j = 0; j < ci->num_stripes; j++) { 377 ULONG sub_stripes = max(ci->sub_stripes, 1); 378 379 if (cis[j].offset + (ci->size * ci->num_stripes / sub_stripes) > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) { 380 off_start = superblock_addrs[i] - cis[j].offset; 381 off_start -= off_start % ci->stripe_length; 382 off_start *= ci->num_stripes / sub_stripes; 383 off_start += (j / sub_stripes) * ci->stripe_length; 384 385 off_end = off_start + ci->stripe_length; 386 387 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, 1); 388 if (!NT_SUCCESS(Status)) { 389 ERR("add_superblock_stripe returned %08lx\n", Status); 390 goto end; 391 } 392 } 393 } 394 } else if (ci->type & BLOCK_FLAG_RAID5) { 395 for (j = 0; j < ci->num_stripes; j++) { 396 uint64_t stripe_size = ci->size / (ci->num_stripes - 1); 397 398 if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) { 399 off_start = superblock_addrs[i] - cis[j].offset; 400 off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 1)); 401 off_start *= ci->num_stripes - 1; 402 403 off_end = off_start + (ci->stripe_length * (ci->num_stripes - 1)); 404 405 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length); 406 if (!NT_SUCCESS(Status)) { 407 ERR("add_superblock_stripe returned %08lx\n", Status); 408 goto end; 409 } 410 } 411 } 412 } else if (ci->type & BLOCK_FLAG_RAID6) { 413 for (j = 0; j < ci->num_stripes; j++) { 414 uint64_t stripe_size = ci->size / (ci->num_stripes - 2); 415 416 if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) { 417 off_start = superblock_addrs[i] - cis[j].offset; 418 off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 2)); 419 off_start *= ci->num_stripes - 2; 420 421 off_end = off_start + (ci->stripe_length * (ci->num_stripes - 2)); 422 423 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length); 424 if (!NT_SUCCESS(Status)) { 425 ERR("add_superblock_stripe returned %08lx\n", Status); 426 goto end; 427 } 428 } 429 } 430 } else { // SINGLE, DUPLICATE, RAID1, RAID1C3, RAID1C4 431 for (j = 0; j < ci->num_stripes; j++) { 432 if (cis[j].offset + ci->size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) { 433 off_start = ((superblock_addrs[i] - cis[j].offset) / c->chunk_item->stripe_length) * c->chunk_item->stripe_length; 434 off_end = sector_align(superblock_addrs[i] - cis[j].offset + sizeof(superblock), c->chunk_item->stripe_length); 435 436 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length); 437 if (!NT_SUCCESS(Status)) { 438 ERR("add_superblock_stripe returned %08lx\n", Status); 439 goto end; 440 } 441 } 442 } 443 } 444 445 i++; 446 } 447 448 Status = STATUS_SUCCESS; 449 450 end: 451 while (!IsListEmpty(&stripes)) { 452 LIST_ENTRY* le = RemoveHeadList(&stripes); 453 superblock_stripe* ss = CONTAINING_RECORD(le, superblock_stripe, list_entry); 454 455 space++; 456 457 ExFreePool(ss); 458 } 459 460 if (NT_SUCCESS(Status)) 461 *size = space * ci->stripe_length; 462 463 return Status; 464 } 465 466 NTSTATUS load_stored_free_space_cache(device_extension* Vcb, chunk* c, bool load_only, PIRP Irp) { 467 KEY searchkey; 468 traverse_ptr tp; 469 FREE_SPACE_ITEM* fsi; 470 uint64_t inode, *generation; 471 uint8_t* data; 472 NTSTATUS Status; 473 uint32_t *checksums, crc32, i, num_sectors, num_valid_sectors, size; 474 FREE_SPACE_ENTRY* fse; 475 uint64_t num_entries, num_bitmaps, extent_length, bmpnum, off, total_space = 0, superblock_size; 476 LIST_ENTRY *le, rollback; 477 478 // FIXME - does this break if Vcb->superblock.sector_size is not 4096? 479 480 TRACE("(%p, %I64x)\n", Vcb, c->offset); 481 482 searchkey.obj_id = FREE_SPACE_CACHE_ID; 483 searchkey.obj_type = 0; 484 searchkey.offset = c->offset; 485 486 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 487 if (!NT_SUCCESS(Status)) { 488 ERR("error - find_item returned %08lx\n", Status); 489 return Status; 490 } 491 492 if (keycmp(tp.item->key, searchkey)) { 493 TRACE("(%I64x,%x,%I64x) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset); 494 return STATUS_NOT_FOUND; 495 } 496 497 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) { 498 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM)); 499 return STATUS_NOT_FOUND; 500 } 501 502 fsi = (FREE_SPACE_ITEM*)tp.item->data; 503 504 if (fsi->key.obj_type != TYPE_INODE_ITEM) { 505 WARN("cache pointed to something other than an INODE_ITEM\n"); 506 return STATUS_NOT_FOUND; 507 } 508 509 inode = fsi->key.obj_id; 510 num_entries = fsi->num_entries; 511 num_bitmaps = fsi->num_bitmaps; 512 513 Status = open_fcb(Vcb, Vcb->root_root, inode, BTRFS_TYPE_FILE, NULL, false, NULL, &c->cache, PagedPool, Irp); 514 if (!NT_SUCCESS(Status)) { 515 ERR("open_fcb returned %08lx\n", Status); 516 return STATUS_NOT_FOUND; 517 } 518 519 if (load_only) 520 return STATUS_SUCCESS; 521 522 if (c->cache->inode_item.st_size == 0) { 523 WARN("cache had zero length\n"); 524 free_fcb(c->cache); 525 c->cache = NULL; 526 return STATUS_NOT_FOUND; 527 } 528 529 c->cache->inode_item.flags |= BTRFS_INODE_NODATACOW; 530 531 if (num_entries == 0 && num_bitmaps == 0) 532 return STATUS_SUCCESS; 533 534 size = (uint32_t)sector_align(c->cache->inode_item.st_size, Vcb->superblock.sector_size); 535 536 data = ExAllocatePoolWithTag(PagedPool, size, ALLOC_TAG); 537 538 if (!data) { 539 ERR("out of memory\n"); 540 free_fcb(c->cache); 541 c->cache = NULL; 542 return STATUS_INSUFFICIENT_RESOURCES; 543 } 544 545 if (c->chunk_item->size < 0x6400000) { // 100 MB 546 WARN("deleting free space cache for chunk smaller than 100MB\n"); 547 goto clearcache; 548 } 549 550 Status = read_file(c->cache, data, 0, c->cache->inode_item.st_size, NULL, NULL); 551 if (!NT_SUCCESS(Status)) { 552 ERR("read_file returned %08lx\n", Status); 553 ExFreePool(data); 554 555 c->cache->deleted = true; 556 mark_fcb_dirty(c->cache); 557 558 free_fcb(c->cache); 559 c->cache = NULL; 560 return STATUS_NOT_FOUND; 561 } 562 563 if (size > c->cache->inode_item.st_size) 564 RtlZeroMemory(&data[c->cache->inode_item.st_size], (ULONG)(size - c->cache->inode_item.st_size)); 565 566 num_sectors = size / Vcb->superblock.sector_size; 567 568 generation = (uint64_t*)(data + (num_sectors * sizeof(uint32_t))); 569 570 if (*generation != fsi->generation) { 571 WARN("free space cache generation for %I64x was %I64x, expected %I64x\n", c->offset, *generation, fsi->generation); 572 goto clearcache; 573 } 574 575 extent_length = (num_sectors * sizeof(uint32_t)) + sizeof(uint64_t) + (num_entries * sizeof(FREE_SPACE_ENTRY)); 576 577 num_valid_sectors = (ULONG)((sector_align(extent_length, Vcb->superblock.sector_size) / Vcb->superblock.sector_size) + num_bitmaps); 578 579 if (num_valid_sectors > num_sectors) { 580 ERR("free space cache for %I64x was %u sectors, expected at least %u\n", c->offset, num_sectors, num_valid_sectors); 581 goto clearcache; 582 } 583 584 checksums = (uint32_t*)data; 585 586 for (i = 0; i < num_valid_sectors; i++) { 587 if (i * Vcb->superblock.sector_size > sizeof(uint32_t) * num_sectors) 588 crc32 = ~calc_crc32c(0xffffffff, &data[i * Vcb->superblock.sector_size], Vcb->superblock.sector_size); 589 else if ((i + 1) * Vcb->superblock.sector_size < sizeof(uint32_t) * num_sectors) 590 crc32 = 0; // FIXME - test this 591 else 592 crc32 = ~calc_crc32c(0xffffffff, &data[sizeof(uint32_t) * num_sectors], ((i + 1) * Vcb->superblock.sector_size) - (sizeof(uint32_t) * num_sectors)); 593 594 if (crc32 != checksums[i]) { 595 WARN("checksum %u was %08x, expected %08x\n", i, crc32, checksums[i]); 596 goto clearcache; 597 } 598 } 599 600 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t); 601 602 bmpnum = 0; 603 for (i = 0; i < num_entries; i++) { 604 if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size) 605 off = sector_align(off, Vcb->superblock.sector_size); 606 607 fse = (FREE_SPACE_ENTRY*)&data[off]; 608 609 if (fse->type == FREE_SPACE_EXTENT) { 610 Status = add_space_entry(&c->space, &c->space_size, fse->offset, fse->size); 611 if (!NT_SUCCESS(Status)) { 612 ERR("add_space_entry returned %08lx\n", Status); 613 ExFreePool(data); 614 return Status; 615 } 616 617 total_space += fse->size; 618 } else if (fse->type != FREE_SPACE_BITMAP) { 619 ERR("unknown free-space type %x\n", fse->type); 620 } 621 622 off += sizeof(FREE_SPACE_ENTRY); 623 } 624 625 if (num_bitmaps > 0) { 626 bmpnum = sector_align(off, Vcb->superblock.sector_size) / Vcb->superblock.sector_size; 627 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t); 628 629 for (i = 0; i < num_entries; i++) { 630 if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size) 631 off = sector_align(off, Vcb->superblock.sector_size); 632 633 fse = (FREE_SPACE_ENTRY*)&data[off]; 634 635 if (fse->type == FREE_SPACE_BITMAP) { 636 // FIXME - make sure we don't overflow the buffer here 637 load_free_space_bitmap(Vcb, c, fse->offset, &data[bmpnum * Vcb->superblock.sector_size], &total_space); 638 bmpnum++; 639 } 640 641 off += sizeof(FREE_SPACE_ENTRY); 642 } 643 } 644 645 // do sanity check 646 647 Status = get_superblock_size(c, &superblock_size); 648 if (!NT_SUCCESS(Status)) { 649 ERR("get_superblock_size returned %08lx\n", Status); 650 ExFreePool(data); 651 return Status; 652 } 653 654 if (c->chunk_item->size - c->used != total_space + superblock_size) { 655 WARN("invalidating cache for chunk %I64x: space was %I64x, expected %I64x\n", c->offset, total_space + superblock_size, c->chunk_item->size - c->used); 656 goto clearcache; 657 } 658 659 le = c->space.Flink; 660 while (le != &c->space) { 661 space* s = CONTAINING_RECORD(le, space, list_entry); 662 LIST_ENTRY* le2 = le->Flink; 663 664 if (le2 != &c->space) { 665 space* s2 = CONTAINING_RECORD(le2, space, list_entry); 666 667 if (s2->address == s->address + s->size) { 668 s->size += s2->size; 669 670 RemoveEntryList(&s2->list_entry); 671 RemoveEntryList(&s2->list_entry_size); 672 ExFreePool(s2); 673 674 RemoveEntryList(&s->list_entry_size); 675 order_space_entry(s, &c->space_size); 676 677 le2 = le; 678 } 679 } 680 681 le = le2; 682 } 683 684 ExFreePool(data); 685 686 return STATUS_SUCCESS; 687 688 clearcache: 689 ExFreePool(data); 690 691 InitializeListHead(&rollback); 692 693 Status = delete_tree_item(Vcb, &tp); 694 if (!NT_SUCCESS(Status)) { 695 ERR("delete_tree_item returned %08lx\n", Status); 696 return Status; 697 } 698 699 Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, &rollback); 700 if (!NT_SUCCESS(Status)) { 701 ERR("excise_extents returned %08lx\n", Status); 702 do_rollback(Vcb, &rollback); 703 return Status; 704 } 705 706 clear_rollback(&rollback); 707 708 c->cache->deleted = true; 709 mark_fcb_dirty(c->cache); 710 711 c->old_cache = c->cache; 712 c->cache = NULL; 713 714 le = c->space.Flink; 715 while (le != &c->space) { 716 space* s = CONTAINING_RECORD(le, space, list_entry); 717 LIST_ENTRY* le2 = le->Flink; 718 719 RemoveEntryList(&s->list_entry); 720 RemoveEntryList(&s->list_entry_size); 721 ExFreePool(s); 722 723 le = le2; 724 } 725 726 return STATUS_NOT_FOUND; 727 } 728 729 static NTSTATUS load_stored_free_space_tree(device_extension* Vcb, chunk* c, PIRP Irp) { 730 KEY searchkey; 731 traverse_ptr tp, next_tp; 732 NTSTATUS Status; 733 ULONG* bmparr = NULL; 734 ULONG bmplen = 0; 735 LIST_ENTRY* le; 736 737 TRACE("(%p, %I64x)\n", Vcb, c->offset); 738 739 if (!Vcb->space_root) 740 return STATUS_NOT_FOUND; 741 742 searchkey.obj_id = c->offset; 743 searchkey.obj_type = TYPE_FREE_SPACE_INFO; 744 searchkey.offset = c->chunk_item->size; 745 746 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp); 747 if (!NT_SUCCESS(Status)) { 748 ERR("find_item returned %08lx\n", Status); 749 return Status; 750 } 751 752 if (keycmp(tp.item->key, searchkey)) { 753 TRACE("(%I64x,%x,%I64x) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset); 754 return STATUS_NOT_FOUND; 755 } 756 757 if (tp.item->size < sizeof(FREE_SPACE_INFO)) { 758 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_INFO)); 759 return STATUS_NOT_FOUND; 760 } 761 762 while (find_next_item(Vcb, &tp, &next_tp, false, Irp)) { 763 tp = next_tp; 764 765 if (tp.item->key.obj_id >= c->offset + c->chunk_item->size) 766 break; 767 768 if (tp.item->key.obj_type == TYPE_FREE_SPACE_EXTENT) { 769 Status = add_space_entry(&c->space, &c->space_size, tp.item->key.obj_id, tp.item->key.offset); 770 if (!NT_SUCCESS(Status)) { 771 ERR("add_space_entry returned %08lx\n", Status); 772 if (bmparr) ExFreePool(bmparr); 773 return Status; 774 } 775 } else if (tp.item->key.obj_type == TYPE_FREE_SPACE_BITMAP) { 776 ULONG explen, index, runlength; 777 RTL_BITMAP bmp; 778 uint64_t lastoff; 779 ULONG bmpl; 780 781 explen = (ULONG)(tp.item->key.offset / (Vcb->superblock.sector_size * 8)); 782 783 if (tp.item->size < explen) { 784 WARN("(%I64x,%x,%I64x) was %u bytes, expected %lu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, explen); 785 return STATUS_NOT_FOUND; 786 } else if (tp.item->size == 0) { 787 WARN("(%I64x,%x,%I64x) has size of 0\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset); 788 return STATUS_NOT_FOUND; 789 } 790 791 if (bmplen < tp.item->size) { 792 if (bmparr) 793 ExFreePool(bmparr); 794 795 bmplen = (ULONG)sector_align(tp.item->size, sizeof(ULONG)); 796 bmparr = ExAllocatePoolWithTag(PagedPool, bmplen, ALLOC_TAG); 797 if (!bmparr) { 798 ERR("out of memory\n"); 799 return STATUS_INSUFFICIENT_RESOURCES; 800 } 801 } 802 803 // We copy the bitmap because it supposedly has to be ULONG-aligned 804 RtlCopyMemory(bmparr, tp.item->data, tp.item->size); 805 806 bmpl = (ULONG)tp.item->key.offset / Vcb->superblock.sector_size; 807 808 RtlInitializeBitMap(&bmp, bmparr, bmpl); 809 810 lastoff = tp.item->key.obj_id; 811 812 runlength = RtlFindFirstRunClear(&bmp, &index); 813 814 while (runlength != 0) { 815 uint64_t runstart, runend; 816 817 if (index >= bmpl) 818 break; 819 820 if (index + runlength >= bmpl) { 821 runlength = bmpl - index; 822 823 if (runlength == 0) 824 break; 825 } 826 827 runstart = tp.item->key.obj_id + (index * Vcb->superblock.sector_size); 828 runend = runstart + (runlength * Vcb->superblock.sector_size); 829 830 if (runstart > lastoff) { 831 Status = add_space_entry(&c->space, &c->space_size, lastoff, runstart - lastoff); 832 if (!NT_SUCCESS(Status)) { 833 ERR("add_space_entry returned %08lx\n", Status); 834 if (bmparr) ExFreePool(bmparr); 835 return Status; 836 } 837 } 838 839 lastoff = runend; 840 841 runlength = RtlFindNextForwardRunClear(&bmp, index + runlength, &index); 842 } 843 844 if (lastoff < tp.item->key.obj_id + tp.item->key.offset) { 845 Status = add_space_entry(&c->space, &c->space_size, lastoff, tp.item->key.obj_id + tp.item->key.offset - lastoff); 846 if (!NT_SUCCESS(Status)) { 847 ERR("add_space_entry returned %08lx\n", Status); 848 if (bmparr) ExFreePool(bmparr); 849 return Status; 850 } 851 } 852 } 853 } 854 855 if (bmparr) 856 ExFreePool(bmparr); 857 858 le = c->space.Flink; 859 while (le != &c->space) { 860 space* s = CONTAINING_RECORD(le, space, list_entry); 861 LIST_ENTRY* le2 = le->Flink; 862 863 if (le2 != &c->space) { 864 space* s2 = CONTAINING_RECORD(le2, space, list_entry); 865 866 if (s2->address == s->address + s->size) { 867 s->size += s2->size; 868 869 RemoveEntryList(&s2->list_entry); 870 RemoveEntryList(&s2->list_entry_size); 871 ExFreePool(s2); 872 873 RemoveEntryList(&s->list_entry_size); 874 order_space_entry(s, &c->space_size); 875 876 le2 = le; 877 } 878 } 879 880 le = le2; 881 } 882 883 return STATUS_SUCCESS; 884 } 885 886 static NTSTATUS load_free_space_cache(device_extension* Vcb, chunk* c, PIRP Irp) { 887 traverse_ptr tp, next_tp; 888 KEY searchkey; 889 uint64_t lastaddr; 890 bool b; 891 space* s; 892 NTSTATUS Status; 893 894 if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE && Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID) { 895 Status = load_stored_free_space_tree(Vcb, c, Irp); 896 897 if (!NT_SUCCESS(Status) && Status != STATUS_NOT_FOUND) { 898 ERR("load_stored_free_space_tree returned %08lx\n", Status); 899 return Status; 900 } 901 } else if (Vcb->superblock.generation - 1 == Vcb->superblock.cache_generation) { 902 Status = load_stored_free_space_cache(Vcb, c, false, Irp); 903 904 if (!NT_SUCCESS(Status) && Status != STATUS_NOT_FOUND) { 905 ERR("load_stored_free_space_cache returned %08lx\n", Status); 906 return Status; 907 } 908 } else 909 Status = STATUS_NOT_FOUND; 910 911 if (Status == STATUS_NOT_FOUND) { 912 TRACE("generating free space cache for chunk %I64x\n", c->offset); 913 914 searchkey.obj_id = c->offset; 915 searchkey.obj_type = TYPE_EXTENT_ITEM; 916 searchkey.offset = 0; 917 918 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp); 919 if (!NT_SUCCESS(Status)) { 920 ERR("error - find_item returned %08lx\n", Status); 921 return Status; 922 } 923 924 lastaddr = c->offset; 925 926 do { 927 if (tp.item->key.obj_id >= c->offset + c->chunk_item->size) 928 break; 929 930 if (tp.item->key.obj_id >= c->offset && (tp.item->key.obj_type == TYPE_EXTENT_ITEM || tp.item->key.obj_type == TYPE_METADATA_ITEM)) { 931 if (tp.item->key.obj_id > lastaddr) { 932 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 933 934 if (!s) { 935 ERR("out of memory\n"); 936 return STATUS_INSUFFICIENT_RESOURCES; 937 } 938 939 s->address = lastaddr; 940 s->size = tp.item->key.obj_id - lastaddr; 941 InsertTailList(&c->space, &s->list_entry); 942 943 order_space_entry(s, &c->space_size); 944 945 TRACE("(%I64x,%I64x)\n", s->address, s->size); 946 } 947 948 if (tp.item->key.obj_type == TYPE_METADATA_ITEM) 949 lastaddr = tp.item->key.obj_id + Vcb->superblock.node_size; 950 else 951 lastaddr = tp.item->key.obj_id + tp.item->key.offset; 952 } 953 954 b = find_next_item(Vcb, &tp, &next_tp, false, Irp); 955 if (b) 956 tp = next_tp; 957 } while (b); 958 959 if (lastaddr < c->offset + c->chunk_item->size) { 960 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 961 962 if (!s) { 963 ERR("out of memory\n"); 964 return STATUS_INSUFFICIENT_RESOURCES; 965 } 966 967 s->address = lastaddr; 968 s->size = c->offset + c->chunk_item->size - lastaddr; 969 InsertTailList(&c->space, &s->list_entry); 970 971 order_space_entry(s, &c->space_size); 972 973 TRACE("(%I64x,%I64x)\n", s->address, s->size); 974 } 975 } 976 977 return STATUS_SUCCESS; 978 } 979 980 NTSTATUS load_cache_chunk(device_extension* Vcb, chunk* c, PIRP Irp) { 981 NTSTATUS Status; 982 983 if (c->cache_loaded) 984 return STATUS_SUCCESS; 985 986 Status = load_free_space_cache(Vcb, c, Irp); 987 if (!NT_SUCCESS(Status)) { 988 ERR("load_free_space_cache returned %08lx\n", Status); 989 return Status; 990 } 991 992 protect_superblocks(c); 993 994 c->cache_loaded = true; 995 996 return STATUS_SUCCESS; 997 } 998 999 static NTSTATUS insert_cache_extent(fcb* fcb, uint64_t start, uint64_t length, LIST_ENTRY* rollback) { 1000 NTSTATUS Status; 1001 LIST_ENTRY* le = fcb->Vcb->chunks.Flink; 1002 chunk* c; 1003 uint64_t flags; 1004 1005 flags = fcb->Vcb->data_flags; 1006 1007 while (le != &fcb->Vcb->chunks) { 1008 c = CONTAINING_RECORD(le, chunk, list_entry); 1009 1010 if (!c->readonly && !c->reloc) { 1011 acquire_chunk_lock(c, fcb->Vcb); 1012 1013 if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) { 1014 if (insert_extent_chunk(fcb->Vcb, fcb, c, start, length, false, NULL, NULL, rollback, BTRFS_COMPRESSION_NONE, length, false, 0)) 1015 return STATUS_SUCCESS; 1016 } 1017 1018 release_chunk_lock(c, fcb->Vcb); 1019 } 1020 1021 le = le->Flink; 1022 } 1023 1024 Status = alloc_chunk(fcb->Vcb, flags, &c, false); 1025 1026 if (!NT_SUCCESS(Status)) { 1027 ERR("alloc_chunk returned %08lx\n", Status); 1028 return Status; 1029 } 1030 1031 acquire_chunk_lock(c, fcb->Vcb); 1032 1033 if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) { 1034 if (insert_extent_chunk(fcb->Vcb, fcb, c, start, length, false, NULL, NULL, rollback, BTRFS_COMPRESSION_NONE, length, false, 0)) 1035 return STATUS_SUCCESS; 1036 } 1037 1038 release_chunk_lock(c, fcb->Vcb); 1039 1040 return STATUS_DISK_FULL; 1041 } 1042 1043 static NTSTATUS allocate_cache_chunk(device_extension* Vcb, chunk* c, bool* changed, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) { 1044 LIST_ENTRY* le; 1045 NTSTATUS Status; 1046 uint64_t num_entries, new_cache_size, i; 1047 uint32_t num_sectors; 1048 bool realloc_extents = false; 1049 1050 // FIXME - also do bitmaps 1051 // FIXME - make sure this works when sector_size is not 4096 1052 1053 *changed = false; 1054 1055 num_entries = 0; 1056 1057 // num_entries is the number of entries in c->space and c->deleting - it might 1058 // be slightly higher then what we end up writing, but doing it this way is much 1059 // quicker and simpler. 1060 if (!IsListEmpty(&c->space)) { 1061 le = c->space.Flink; 1062 while (le != &c->space) { 1063 num_entries++; 1064 1065 le = le->Flink; 1066 } 1067 } 1068 1069 if (!IsListEmpty(&c->deleting)) { 1070 le = c->deleting.Flink; 1071 while (le != &c->deleting) { 1072 num_entries++; 1073 1074 le = le->Flink; 1075 } 1076 } 1077 1078 new_cache_size = sizeof(uint64_t) + (num_entries * sizeof(FREE_SPACE_ENTRY)); 1079 1080 num_sectors = (uint32_t)sector_align(new_cache_size, Vcb->superblock.sector_size) / Vcb->superblock.sector_size; 1081 num_sectors = (uint32_t)sector_align(num_sectors, CACHE_INCREMENTS); 1082 1083 // adjust for padding 1084 // FIXME - there must be a more efficient way of doing this 1085 new_cache_size = sizeof(uint64_t) + (sizeof(uint32_t) * num_sectors); 1086 for (i = 0; i < num_entries; i++) { 1087 if ((new_cache_size / Vcb->superblock.sector_size) != ((new_cache_size + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size)) 1088 new_cache_size = sector_align(new_cache_size, Vcb->superblock.sector_size); 1089 1090 new_cache_size += sizeof(FREE_SPACE_ENTRY); 1091 } 1092 1093 new_cache_size = sector_align(new_cache_size, CACHE_INCREMENTS * Vcb->superblock.sector_size); 1094 1095 TRACE("chunk %I64x: cache_size = %I64x, new_cache_size = %I64x\n", c->offset, c->cache ? c->cache->inode_item.st_size : 0, new_cache_size); 1096 1097 if (c->cache) { 1098 if (new_cache_size > c->cache->inode_item.st_size) 1099 realloc_extents = true; 1100 else { 1101 le = c->cache->extents.Flink; 1102 1103 while (le != &c->cache->extents) { 1104 extent* ext = CONTAINING_RECORD(le, extent, list_entry); 1105 1106 if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) { 1107 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0]; 1108 1109 if (ed2->size != 0) { 1110 chunk* c2 = get_chunk_from_address(Vcb, ed2->address); 1111 1112 if (c2 && (c2->readonly || c2->reloc)) { 1113 realloc_extents = true; 1114 break; 1115 } 1116 } 1117 } 1118 1119 le = le->Flink; 1120 } 1121 } 1122 } 1123 1124 if (!c->cache) { 1125 FREE_SPACE_ITEM* fsi; 1126 KEY searchkey; 1127 traverse_ptr tp; 1128 1129 // create new inode 1130 1131 c->cache = create_fcb(Vcb, PagedPool); 1132 if (!c->cache) { 1133 ERR("out of memory\n"); 1134 return STATUS_INSUFFICIENT_RESOURCES; 1135 } 1136 1137 c->cache->Vcb = Vcb; 1138 1139 c->cache->inode_item.st_size = new_cache_size; 1140 c->cache->inode_item.st_blocks = new_cache_size; 1141 c->cache->inode_item.st_nlink = 1; 1142 c->cache->inode_item.st_mode = S_IRUSR | S_IWUSR | __S_IFREG; 1143 c->cache->inode_item.flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW | BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC; 1144 1145 c->cache->Header.IsFastIoPossible = fast_io_possible(c->cache); 1146 c->cache->Header.AllocationSize.QuadPart = 0; 1147 c->cache->Header.FileSize.QuadPart = 0; 1148 c->cache->Header.ValidDataLength.QuadPart = 0; 1149 1150 c->cache->subvol = Vcb->root_root; 1151 1152 c->cache->inode = InterlockedIncrement64(&Vcb->root_root->lastinode); 1153 1154 c->cache->type = BTRFS_TYPE_FILE; 1155 c->cache->created = true; 1156 1157 // create new free space entry 1158 1159 fsi = ExAllocatePoolWithTag(PagedPool, sizeof(FREE_SPACE_ITEM), ALLOC_TAG); 1160 if (!fsi) { 1161 ERR("out of memory\n"); 1162 reap_fcb(c->cache); 1163 c->cache = NULL; 1164 return STATUS_INSUFFICIENT_RESOURCES; 1165 } 1166 1167 searchkey.obj_id = FREE_SPACE_CACHE_ID; 1168 searchkey.obj_type = 0; 1169 searchkey.offset = c->offset; 1170 1171 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 1172 if (!NT_SUCCESS(Status)) { 1173 ERR("error - find_item returned %08lx\n", Status); 1174 ExFreePool(fsi); 1175 reap_fcb(c->cache); 1176 c->cache = NULL; 1177 return Status; 1178 } 1179 1180 if (!keycmp(searchkey, tp.item->key)) { 1181 Status = delete_tree_item(Vcb, &tp); 1182 if (!NT_SUCCESS(Status)) { 1183 ERR("delete_tree_item returned %08lx\n", Status); 1184 ExFreePool(fsi); 1185 reap_fcb(c->cache); 1186 c->cache = NULL; 1187 return Status; 1188 } 1189 } 1190 1191 fsi->key.obj_id = c->cache->inode; 1192 fsi->key.obj_type = TYPE_INODE_ITEM; 1193 fsi->key.offset = 0; 1194 1195 Status = insert_tree_item(Vcb, Vcb->root_root, FREE_SPACE_CACHE_ID, 0, c->offset, fsi, sizeof(FREE_SPACE_ITEM), NULL, Irp); 1196 if (!NT_SUCCESS(Status)) { 1197 ERR("insert_tree_item returned %08lx\n", Status); 1198 ExFreePool(fsi); 1199 reap_fcb(c->cache); 1200 c->cache = NULL; 1201 return Status; 1202 } 1203 1204 // allocate space 1205 1206 Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback); 1207 if (!NT_SUCCESS(Status)) { 1208 ERR("insert_cache_extent returned %08lx\n", Status); 1209 reap_fcb(c->cache); 1210 c->cache = NULL; 1211 return Status; 1212 } 1213 1214 c->cache->extents_changed = true; 1215 InsertTailList(&Vcb->all_fcbs, &c->cache->list_entry_all); 1216 1217 Status = flush_fcb(c->cache, true, batchlist, Irp); 1218 if (!NT_SUCCESS(Status)) { 1219 ERR("flush_fcb returned %08lx\n", Status); 1220 free_fcb(c->cache); 1221 c->cache = NULL; 1222 return Status; 1223 } 1224 1225 *changed = true; 1226 } else if (realloc_extents) { 1227 KEY searchkey; 1228 traverse_ptr tp; 1229 1230 TRACE("reallocating extents\n"); 1231 1232 // add free_space entry to tree cache 1233 1234 searchkey.obj_id = FREE_SPACE_CACHE_ID; 1235 searchkey.obj_type = 0; 1236 searchkey.offset = c->offset; 1237 1238 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 1239 if (!NT_SUCCESS(Status)) { 1240 ERR("error - find_item returned %08lx\n", Status); 1241 return Status; 1242 } 1243 1244 if (keycmp(searchkey, tp.item->key)) { 1245 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset); 1246 return STATUS_INTERNAL_ERROR; 1247 } 1248 1249 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) { 1250 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM)); 1251 return STATUS_INTERNAL_ERROR; 1252 } 1253 1254 tp.tree->write = true; 1255 1256 // remove existing extents 1257 1258 if (c->cache->inode_item.st_size > 0) { 1259 le = c->cache->extents.Flink; 1260 1261 while (le != &c->cache->extents) { 1262 extent* ext = CONTAINING_RECORD(le, extent, list_entry); 1263 1264 if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) { 1265 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0]; 1266 1267 if (ed2->size != 0) { 1268 chunk* c2 = get_chunk_from_address(Vcb, ed2->address); 1269 1270 if (c2) { 1271 c2->changed = true; 1272 c2->space_changed = true; 1273 } 1274 } 1275 } 1276 1277 le = le->Flink; 1278 } 1279 1280 Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, rollback); 1281 if (!NT_SUCCESS(Status)) { 1282 ERR("excise_extents returned %08lx\n", Status); 1283 return Status; 1284 } 1285 } 1286 1287 // add new extent 1288 1289 Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback); 1290 if (!NT_SUCCESS(Status)) { 1291 ERR("insert_cache_extent returned %08lx\n", Status); 1292 return Status; 1293 } 1294 1295 // modify INODE_ITEM 1296 1297 c->cache->inode_item.st_size = new_cache_size; 1298 c->cache->inode_item.st_blocks = new_cache_size; 1299 1300 Status = flush_fcb(c->cache, true, batchlist, Irp); 1301 if (!NT_SUCCESS(Status)) { 1302 ERR("flush_fcb returned %08lx\n", Status); 1303 return Status; 1304 } 1305 1306 *changed = true; 1307 } else { 1308 KEY searchkey; 1309 traverse_ptr tp; 1310 1311 // add INODE_ITEM and free_space entry to tree cache, for writing later 1312 1313 searchkey.obj_id = c->cache->inode; 1314 searchkey.obj_type = TYPE_INODE_ITEM; 1315 searchkey.offset = 0; 1316 1317 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 1318 if (!NT_SUCCESS(Status)) { 1319 ERR("error - find_item returned %08lx\n", Status); 1320 return Status; 1321 } 1322 1323 if (keycmp(searchkey, tp.item->key)) { 1324 INODE_ITEM* ii; 1325 1326 ii = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_ITEM), ALLOC_TAG); 1327 if (!ii) { 1328 ERR("out of memory\n"); 1329 return STATUS_INSUFFICIENT_RESOURCES; 1330 } 1331 1332 RtlCopyMemory(ii, &c->cache->inode_item, sizeof(INODE_ITEM)); 1333 1334 Status = insert_tree_item(Vcb, Vcb->root_root, c->cache->inode, TYPE_INODE_ITEM, 0, ii, sizeof(INODE_ITEM), NULL, Irp); 1335 if (!NT_SUCCESS(Status)) { 1336 ERR("insert_tree_item returned %08lx\n", Status); 1337 ExFreePool(ii); 1338 return Status; 1339 } 1340 1341 *changed = true; 1342 } else { 1343 if (tp.item->size < sizeof(INODE_ITEM)) { 1344 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(INODE_ITEM)); 1345 return STATUS_INTERNAL_ERROR; 1346 } 1347 1348 tp.tree->write = true; 1349 } 1350 1351 searchkey.obj_id = FREE_SPACE_CACHE_ID; 1352 searchkey.obj_type = 0; 1353 searchkey.offset = c->offset; 1354 1355 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 1356 if (!NT_SUCCESS(Status)) { 1357 ERR("error - find_item returned %08lx\n", Status); 1358 return Status; 1359 } 1360 1361 if (keycmp(searchkey, tp.item->key)) { 1362 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset); 1363 return STATUS_INTERNAL_ERROR; 1364 } 1365 1366 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) { 1367 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM)); 1368 return STATUS_INTERNAL_ERROR; 1369 } 1370 1371 tp.tree->write = true; 1372 } 1373 1374 // FIXME - reduce inode allocation if cache is shrinking. Make sure to avoid infinite write loops 1375 1376 return STATUS_SUCCESS; 1377 } 1378 1379 NTSTATUS allocate_cache(device_extension* Vcb, bool* changed, PIRP Irp, LIST_ENTRY* rollback) { 1380 LIST_ENTRY *le, batchlist; 1381 NTSTATUS Status; 1382 1383 *changed = false; 1384 1385 InitializeListHead(&batchlist); 1386 1387 ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, true); 1388 1389 le = Vcb->chunks.Flink; 1390 while (le != &Vcb->chunks) { 1391 chunk* c = CONTAINING_RECORD(le, chunk, list_entry); 1392 1393 if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB 1394 bool b; 1395 1396 acquire_chunk_lock(c, Vcb); 1397 Status = allocate_cache_chunk(Vcb, c, &b, &batchlist, Irp, rollback); 1398 release_chunk_lock(c, Vcb); 1399 1400 if (b) 1401 *changed = true; 1402 1403 if (!NT_SUCCESS(Status)) { 1404 ERR("allocate_cache_chunk(%I64x) returned %08lx\n", c->offset, Status); 1405 ExReleaseResourceLite(&Vcb->chunk_lock); 1406 clear_batch_list(Vcb, &batchlist); 1407 return Status; 1408 } 1409 } 1410 1411 le = le->Flink; 1412 } 1413 1414 ExReleaseResourceLite(&Vcb->chunk_lock); 1415 1416 Status = commit_batch_list(Vcb, &batchlist, Irp); 1417 if (!NT_SUCCESS(Status)) { 1418 ERR("commit_batch_list returned %08lx\n", Status); 1419 return Status; 1420 } 1421 1422 return STATUS_SUCCESS; 1423 } 1424 1425 static void add_rollback_space(LIST_ENTRY* rollback, bool add, LIST_ENTRY* list, LIST_ENTRY* list_size, uint64_t address, uint64_t length, chunk* c) { 1426 rollback_space* rs; 1427 1428 rs = ExAllocatePoolWithTag(PagedPool, sizeof(rollback_space), ALLOC_TAG); 1429 if (!rs) { 1430 ERR("out of memory\n"); 1431 return; 1432 } 1433 1434 rs->list = list; 1435 rs->list_size = list_size; 1436 rs->address = address; 1437 rs->length = length; 1438 rs->chunk = c; 1439 1440 add_rollback(rollback, add ? ROLLBACK_ADD_SPACE : ROLLBACK_SUBTRACT_SPACE, rs); 1441 } 1442 1443 void space_list_add2(LIST_ENTRY* list, LIST_ENTRY* list_size, uint64_t address, uint64_t length, chunk* c, LIST_ENTRY* rollback) { 1444 LIST_ENTRY* le; 1445 space *s, *s2; 1446 1447 if (IsListEmpty(list)) { 1448 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 1449 1450 if (!s) { 1451 ERR("out of memory\n"); 1452 return; 1453 } 1454 1455 s->address = address; 1456 s->size = length; 1457 InsertTailList(list, &s->list_entry); 1458 1459 if (list_size) 1460 InsertTailList(list_size, &s->list_entry_size); 1461 1462 if (rollback) 1463 add_rollback_space(rollback, true, list, list_size, address, length, c); 1464 1465 return; 1466 } 1467 1468 le = list->Flink; 1469 do { 1470 s2 = CONTAINING_RECORD(le, space, list_entry); 1471 1472 // old entry envelops new one completely 1473 if (s2->address <= address && s2->address + s2->size >= address + length) 1474 return; 1475 1476 // new entry envelops old one completely 1477 if (address <= s2->address && address + length >= s2->address + s2->size) { 1478 if (address < s2->address) { 1479 if (rollback) 1480 add_rollback_space(rollback, true, list, list_size, address, s2->address - address, c); 1481 1482 s2->size += s2->address - address; 1483 s2->address = address; 1484 1485 while (s2->list_entry.Blink != list) { 1486 space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry); 1487 1488 if (s3->address + s3->size == s2->address) { 1489 s2->address = s3->address; 1490 s2->size += s3->size; 1491 1492 RemoveEntryList(&s3->list_entry); 1493 1494 if (list_size) 1495 RemoveEntryList(&s3->list_entry_size); 1496 1497 ExFreePool(s3); 1498 } else 1499 break; 1500 } 1501 } 1502 1503 if (length > s2->size) { 1504 if (rollback) 1505 add_rollback_space(rollback, true, list, list_size, s2->address + s2->size, address + length - s2->address - s2->size, c); 1506 1507 s2->size = length; 1508 1509 while (s2->list_entry.Flink != list) { 1510 space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry); 1511 1512 if (s3->address <= s2->address + s2->size) { 1513 s2->size = max(s2->size, s3->address + s3->size - s2->address); 1514 1515 RemoveEntryList(&s3->list_entry); 1516 1517 if (list_size) 1518 RemoveEntryList(&s3->list_entry_size); 1519 1520 ExFreePool(s3); 1521 } else 1522 break; 1523 } 1524 } 1525 1526 if (list_size) { 1527 RemoveEntryList(&s2->list_entry_size); 1528 order_space_entry(s2, list_size); 1529 } 1530 1531 return; 1532 } 1533 1534 // new entry overlaps start of old one 1535 if (address < s2->address && address + length >= s2->address) { 1536 if (rollback) 1537 add_rollback_space(rollback, true, list, list_size, address, s2->address - address, c); 1538 1539 s2->size += s2->address - address; 1540 s2->address = address; 1541 1542 while (s2->list_entry.Blink != list) { 1543 space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry); 1544 1545 if (s3->address + s3->size == s2->address) { 1546 s2->address = s3->address; 1547 s2->size += s3->size; 1548 1549 RemoveEntryList(&s3->list_entry); 1550 1551 if (list_size) 1552 RemoveEntryList(&s3->list_entry_size); 1553 1554 ExFreePool(s3); 1555 } else 1556 break; 1557 } 1558 1559 if (list_size) { 1560 RemoveEntryList(&s2->list_entry_size); 1561 order_space_entry(s2, list_size); 1562 } 1563 1564 return; 1565 } 1566 1567 // new entry overlaps end of old one 1568 if (address <= s2->address + s2->size && address + length > s2->address + s2->size) { 1569 if (rollback) 1570 add_rollback_space(rollback, true, list, list_size, address, s2->address + s2->size - address, c); 1571 1572 s2->size = address + length - s2->address; 1573 1574 while (s2->list_entry.Flink != list) { 1575 space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry); 1576 1577 if (s3->address <= s2->address + s2->size) { 1578 s2->size = max(s2->size, s3->address + s3->size - s2->address); 1579 1580 RemoveEntryList(&s3->list_entry); 1581 1582 if (list_size) 1583 RemoveEntryList(&s3->list_entry_size); 1584 1585 ExFreePool(s3); 1586 } else 1587 break; 1588 } 1589 1590 if (list_size) { 1591 RemoveEntryList(&s2->list_entry_size); 1592 order_space_entry(s2, list_size); 1593 } 1594 1595 return; 1596 } 1597 1598 // add completely separate entry 1599 if (s2->address > address + length) { 1600 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 1601 1602 if (!s) { 1603 ERR("out of memory\n"); 1604 return; 1605 } 1606 1607 if (rollback) 1608 add_rollback_space(rollback, true, list, list_size, address, length, c); 1609 1610 s->address = address; 1611 s->size = length; 1612 InsertHeadList(s2->list_entry.Blink, &s->list_entry); 1613 1614 if (list_size) 1615 order_space_entry(s, list_size); 1616 1617 return; 1618 } 1619 1620 le = le->Flink; 1621 } while (le != list); 1622 1623 // check if contiguous with last entry 1624 if (s2->address + s2->size == address) { 1625 s2->size += length; 1626 1627 if (list_size) { 1628 RemoveEntryList(&s2->list_entry_size); 1629 order_space_entry(s2, list_size); 1630 } 1631 1632 return; 1633 } 1634 1635 // otherwise, insert at end 1636 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 1637 1638 if (!s) { 1639 ERR("out of memory\n"); 1640 return; 1641 } 1642 1643 s->address = address; 1644 s->size = length; 1645 InsertTailList(list, &s->list_entry); 1646 1647 if (list_size) 1648 order_space_entry(s, list_size); 1649 1650 if (rollback) 1651 add_rollback_space(rollback, true, list, list_size, address, length, c); 1652 } 1653 1654 static void space_list_merge(LIST_ENTRY* spacelist, LIST_ENTRY* spacelist_size, LIST_ENTRY* deleting) { 1655 LIST_ENTRY* le; 1656 1657 if (!IsListEmpty(deleting)) { 1658 le = deleting->Flink; 1659 while (le != deleting) { 1660 space* s = CONTAINING_RECORD(le, space, list_entry); 1661 1662 space_list_add2(spacelist, spacelist_size, s->address, s->size, NULL, NULL); 1663 1664 le = le->Flink; 1665 } 1666 } 1667 } 1668 1669 static NTSTATUS update_chunk_cache(device_extension* Vcb, chunk* c, BTRFS_TIME* now, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) { 1670 NTSTATUS Status; 1671 KEY searchkey; 1672 traverse_ptr tp; 1673 FREE_SPACE_ITEM* fsi; 1674 void* data; 1675 uint64_t num_entries, *cachegen, off; 1676 uint32_t *checksums, num_sectors, i; 1677 LIST_ENTRY* le; 1678 1679 space_list_merge(&c->space, &c->space_size, &c->deleting); 1680 1681 data = ExAllocatePoolWithTag(NonPagedPool, (ULONG)c->cache->inode_item.st_size, ALLOC_TAG); 1682 if (!data) { 1683 ERR("out of memory\n"); 1684 return STATUS_INSUFFICIENT_RESOURCES; 1685 } 1686 1687 RtlZeroMemory(data, (ULONG)c->cache->inode_item.st_size); 1688 1689 num_entries = 0; 1690 num_sectors = (uint32_t)(c->cache->inode_item.st_size / Vcb->superblock.sector_size); 1691 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t); 1692 1693 le = c->space.Flink; 1694 while (le != &c->space) { 1695 FREE_SPACE_ENTRY* fse; 1696 1697 space* s = CONTAINING_RECORD(le, space, list_entry); 1698 1699 if ((off + sizeof(FREE_SPACE_ENTRY)) / Vcb->superblock.sector_size != off / Vcb->superblock.sector_size) 1700 off = sector_align(off, Vcb->superblock.sector_size); 1701 1702 fse = (FREE_SPACE_ENTRY*)((uint8_t*)data + off); 1703 1704 fse->offset = s->address; 1705 fse->size = s->size; 1706 fse->type = FREE_SPACE_EXTENT; 1707 num_entries++; 1708 1709 off += sizeof(FREE_SPACE_ENTRY); 1710 1711 le = le->Flink; 1712 } 1713 1714 // update INODE_ITEM 1715 1716 c->cache->inode_item.generation = Vcb->superblock.generation; 1717 c->cache->inode_item.transid = Vcb->superblock.generation; 1718 c->cache->inode_item.sequence++; 1719 c->cache->inode_item.st_ctime = *now; 1720 1721 Status = flush_fcb(c->cache, true, batchlist, Irp); 1722 if (!NT_SUCCESS(Status)) { 1723 ERR("flush_fcb returned %08lx\n", Status); 1724 goto end; 1725 } 1726 1727 // update free_space item 1728 1729 searchkey.obj_id = FREE_SPACE_CACHE_ID; 1730 searchkey.obj_type = 0; 1731 searchkey.offset = c->offset; 1732 1733 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp); 1734 if (!NT_SUCCESS(Status)) { 1735 ERR("error - find_item returned %08lx\n", Status); 1736 goto end; 1737 } 1738 1739 if (keycmp(searchkey, tp.item->key)) { 1740 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset); 1741 Status = STATUS_INTERNAL_ERROR; 1742 goto end; 1743 } 1744 1745 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) { 1746 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM)); 1747 Status = STATUS_INTERNAL_ERROR; 1748 goto end; 1749 } 1750 1751 fsi = (FREE_SPACE_ITEM*)tp.item->data; 1752 1753 fsi->generation = Vcb->superblock.generation; 1754 fsi->num_entries = num_entries; 1755 fsi->num_bitmaps = 0; 1756 1757 // set cache generation 1758 1759 cachegen = (uint64_t*)((uint8_t*)data + (sizeof(uint32_t) * num_sectors)); 1760 *cachegen = Vcb->superblock.generation; 1761 1762 // calculate cache checksums 1763 1764 checksums = (uint32_t*)data; 1765 1766 // FIXME - if we know sector is fully zeroed, use cached checksum 1767 1768 for (i = 0; i < num_sectors; i++) { 1769 if (i * Vcb->superblock.sector_size > sizeof(uint32_t) * num_sectors) 1770 checksums[i] = ~calc_crc32c(0xffffffff, (uint8_t*)data + (i * Vcb->superblock.sector_size), Vcb->superblock.sector_size); 1771 else if ((i + 1) * Vcb->superblock.sector_size < sizeof(uint32_t) * num_sectors) 1772 checksums[i] = 0; // FIXME - test this 1773 else 1774 checksums[i] = ~calc_crc32c(0xffffffff, (uint8_t*)data + (sizeof(uint32_t) * num_sectors), ((i + 1) * Vcb->superblock.sector_size) - (sizeof(uint32_t) * num_sectors)); 1775 } 1776 1777 // write cache 1778 1779 Status = do_write_file(c->cache, 0, c->cache->inode_item.st_size, data, NULL, false, 0, rollback); 1780 if (!NT_SUCCESS(Status)) { 1781 ERR("do_write_file returned %08lx\n", Status); 1782 1783 // Writing the cache isn't critical, so we don't return an error if writing fails. This means 1784 // we can still flush on a degraded mount if metadata is RAID1 but data is RAID0. 1785 } 1786 1787 Status = STATUS_SUCCESS; 1788 1789 end: 1790 ExFreePool(data); 1791 1792 return Status; 1793 } 1794 1795 static NTSTATUS update_chunk_cache_tree(device_extension* Vcb, chunk* c, LIST_ENTRY* batchlist) { 1796 NTSTATUS Status; 1797 LIST_ENTRY* le; 1798 FREE_SPACE_INFO* fsi; 1799 1800 fsi = ExAllocatePoolWithTag(PagedPool, sizeof(FREE_SPACE_INFO), ALLOC_TAG); 1801 if (!fsi) { 1802 ERR("out of memory\n"); 1803 return STATUS_INSUFFICIENT_RESOURCES; 1804 } 1805 1806 space_list_merge(&c->space, &c->space_size, &c->deleting); 1807 1808 fsi->count = 0; 1809 fsi->flags = 0; 1810 1811 le = c->space.Flink; 1812 while (le != &c->space) { 1813 space* s = CONTAINING_RECORD(le, space, list_entry); 1814 1815 fsi->count++; 1816 1817 Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, s->address, TYPE_FREE_SPACE_EXTENT, s->size, 1818 NULL, 0, Batch_Insert); 1819 if (!NT_SUCCESS(Status)) { 1820 ERR("insert_tree_item_batch returned %08lx\n", Status); 1821 ExFreePool(fsi); 1822 return Status; 1823 } 1824 1825 le = le->Flink; 1826 } 1827 1828 Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, c->offset, TYPE_FREE_SPACE_INFO, c->chunk_item->size, 1829 NULL, 0, Batch_DeleteFreeSpace); 1830 if (!NT_SUCCESS(Status)) { 1831 ERR("insert_tree_item_batch returned %08lx\n", Status); 1832 ExFreePool(fsi); 1833 return Status; 1834 } 1835 1836 Status = insert_tree_item_batch(batchlist, Vcb, Vcb->space_root, c->offset, TYPE_FREE_SPACE_INFO, c->chunk_item->size, 1837 fsi, sizeof(FREE_SPACE_INFO), Batch_Insert); 1838 if (!NT_SUCCESS(Status)) { 1839 ERR("insert_tree_item_batch returned %08lx\n", Status); 1840 ExFreePool(fsi); 1841 return Status; 1842 } 1843 1844 return STATUS_SUCCESS; 1845 } 1846 1847 NTSTATUS update_chunk_caches(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) { 1848 LIST_ENTRY *le, batchlist; 1849 NTSTATUS Status; 1850 chunk* c; 1851 LARGE_INTEGER time; 1852 BTRFS_TIME now; 1853 1854 KeQuerySystemTime(&time); 1855 win_time_to_unix(time, &now); 1856 1857 InitializeListHead(&batchlist); 1858 1859 le = Vcb->chunks.Flink; 1860 while (le != &Vcb->chunks) { 1861 c = CONTAINING_RECORD(le, chunk, list_entry); 1862 1863 if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB 1864 acquire_chunk_lock(c, Vcb); 1865 Status = update_chunk_cache(Vcb, c, &now, &batchlist, Irp, rollback); 1866 release_chunk_lock(c, Vcb); 1867 1868 if (!NT_SUCCESS(Status)) { 1869 ERR("update_chunk_cache(%I64x) returned %08lx\n", c->offset, Status); 1870 clear_batch_list(Vcb, &batchlist); 1871 return Status; 1872 } 1873 } 1874 1875 le = le->Flink; 1876 } 1877 1878 Status = commit_batch_list(Vcb, &batchlist, Irp); 1879 if (!NT_SUCCESS(Status)) { 1880 ERR("commit_batch_list returned %08lx\n", Status); 1881 return Status; 1882 } 1883 1884 le = Vcb->chunks.Flink; 1885 while (le != &Vcb->chunks) { 1886 c = CONTAINING_RECORD(le, chunk, list_entry); 1887 1888 if (c->changed && (c->chunk_item->type & BLOCK_FLAG_RAID5 || c->chunk_item->type & BLOCK_FLAG_RAID6)) { 1889 ExAcquireResourceExclusiveLite(&c->partial_stripes_lock, true); 1890 1891 while (!IsListEmpty(&c->partial_stripes)) { 1892 partial_stripe* ps = CONTAINING_RECORD(RemoveHeadList(&c->partial_stripes), partial_stripe, list_entry); 1893 1894 Status = flush_partial_stripe(Vcb, c, ps); 1895 1896 if (ps->bmparr) 1897 ExFreePool(ps->bmparr); 1898 1899 ExFreePool(ps); 1900 1901 if (!NT_SUCCESS(Status)) { 1902 ERR("flush_partial_stripe returned %08lx\n", Status); 1903 ExReleaseResourceLite(&c->partial_stripes_lock); 1904 return Status; 1905 } 1906 } 1907 1908 ExReleaseResourceLite(&c->partial_stripes_lock); 1909 } 1910 1911 le = le->Flink; 1912 } 1913 1914 return STATUS_SUCCESS; 1915 } 1916 1917 NTSTATUS update_chunk_caches_tree(device_extension* Vcb, PIRP Irp) { 1918 LIST_ENTRY *le, batchlist; 1919 NTSTATUS Status; 1920 chunk* c; 1921 1922 Vcb->superblock.compat_ro_flags |= BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID; 1923 1924 InitializeListHead(&batchlist); 1925 1926 ExAcquireResourceSharedLite(&Vcb->chunk_lock, true); 1927 1928 le = Vcb->chunks.Flink; 1929 while (le != &Vcb->chunks) { 1930 c = CONTAINING_RECORD(le, chunk, list_entry); 1931 1932 if (c->space_changed) { 1933 acquire_chunk_lock(c, Vcb); 1934 Status = update_chunk_cache_tree(Vcb, c, &batchlist); 1935 release_chunk_lock(c, Vcb); 1936 1937 if (!NT_SUCCESS(Status)) { 1938 ERR("update_chunk_cache_tree(%I64x) returned %08lx\n", c->offset, Status); 1939 ExReleaseResourceLite(&Vcb->chunk_lock); 1940 clear_batch_list(Vcb, &batchlist); 1941 return Status; 1942 } 1943 } 1944 1945 le = le->Flink; 1946 } 1947 1948 ExReleaseResourceLite(&Vcb->chunk_lock); 1949 1950 Status = commit_batch_list(Vcb, &batchlist, Irp); 1951 if (!NT_SUCCESS(Status)) { 1952 ERR("commit_batch_list returned %08lx\n", Status); 1953 return Status; 1954 } 1955 1956 return STATUS_SUCCESS; 1957 } 1958 1959 void space_list_add(chunk* c, uint64_t address, uint64_t length, LIST_ENTRY* rollback) { 1960 TRACE("(%p, %I64x, %I64x, %p)\n", c, address, length, rollback); 1961 1962 c->changed = true; 1963 c->space_changed = true; 1964 1965 space_list_add2(&c->deleting, NULL, address, length, c, rollback); 1966 } 1967 1968 void space_list_subtract2(LIST_ENTRY* list, LIST_ENTRY* list_size, uint64_t address, uint64_t length, chunk* c, LIST_ENTRY* rollback) { 1969 LIST_ENTRY *le, *le2; 1970 space *s, *s2; 1971 1972 if (IsListEmpty(list)) 1973 return; 1974 1975 le = list->Flink; 1976 while (le != list) { 1977 s2 = CONTAINING_RECORD(le, space, list_entry); 1978 le2 = le->Flink; 1979 1980 if (s2->address >= address + length) 1981 return; 1982 1983 if (s2->address >= address && s2->address + s2->size <= address + length) { // remove entry entirely 1984 if (rollback) 1985 add_rollback_space(rollback, false, list, list_size, s2->address, s2->size, c); 1986 1987 RemoveEntryList(&s2->list_entry); 1988 1989 if (list_size) 1990 RemoveEntryList(&s2->list_entry_size); 1991 1992 ExFreePool(s2); 1993 } else if (address + length > s2->address && address + length < s2->address + s2->size) { 1994 if (address > s2->address) { // cut out hole 1995 if (rollback) 1996 add_rollback_space(rollback, false, list, list_size, address, length, c); 1997 1998 s = ExAllocatePoolWithTag(PagedPool, sizeof(space), ALLOC_TAG); 1999 2000 if (!s) { 2001 ERR("out of memory\n"); 2002 return; 2003 } 2004 2005 s->address = s2->address; 2006 s->size = address - s2->address; 2007 InsertHeadList(s2->list_entry.Blink, &s->list_entry); 2008 2009 s2->size = s2->address + s2->size - address - length; 2010 s2->address = address + length; 2011 2012 if (list_size) { 2013 RemoveEntryList(&s2->list_entry_size); 2014 order_space_entry(s2, list_size); 2015 order_space_entry(s, list_size); 2016 } 2017 2018 return; 2019 } else { // remove start of entry 2020 if (rollback) 2021 add_rollback_space(rollback, false, list, list_size, s2->address, address + length - s2->address, c); 2022 2023 s2->size -= address + length - s2->address; 2024 s2->address = address + length; 2025 2026 if (list_size) { 2027 RemoveEntryList(&s2->list_entry_size); 2028 order_space_entry(s2, list_size); 2029 } 2030 } 2031 } else if (address > s2->address && address < s2->address + s2->size) { // remove end of entry 2032 if (rollback) 2033 add_rollback_space(rollback, false, list, list_size, address, s2->address + s2->size - address, c); 2034 2035 s2->size = address - s2->address; 2036 2037 if (list_size) { 2038 RemoveEntryList(&s2->list_entry_size); 2039 order_space_entry(s2, list_size); 2040 } 2041 } 2042 2043 le = le2; 2044 } 2045 } 2046 2047 void space_list_subtract(chunk* c, bool deleting, uint64_t address, uint64_t length, LIST_ENTRY* rollback) { 2048 LIST_ENTRY* list; 2049 2050 list = deleting ? &c->deleting : &c->space; 2051 2052 c->changed = true; 2053 c->space_changed = true; 2054 2055 space_list_subtract2(list, deleting ? NULL : &c->space_size, address, length, c, rollback); 2056 } 2057