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