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