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