ReactOS 0.4.15-dev-7654-g6bc40d3
free-space.c
Go to the documentation of this file.
1/* Copyright (c) Mark Harmstone 2016-17
2 *
3 * This file is part of WinBtrfs.
4 *
5 * WinBtrfs is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Lesser General Public Licence as published by
7 * the Free Software Foundation, either version 3 of the Licence, or
8 * (at your option) any later version.
9 *
10 * WinBtrfs is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public Licence for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public Licence
16 * along with WinBtrfs. If not, see <http://www.gnu.org/licenses/>. */
17
18#include "btrfs_drv.h"
19#include "crc32c.h"
20
21// Number of increments in the size of each cache inode, in sectors. Should
22// this be a constant number of sectors, a constant 256 KB, or what?
23#define CACHE_INCREMENTS 64
24
27 fcb* fcb;
28
29 Status = open_fcb(Vcb, Vcb->root_root, inode, BTRFS_TYPE_FILE, NULL, false, NULL, &fcb, PagedPool, Irp);
30 if (!NT_SUCCESS(Status)) {
31 ERR("open_fcb returned %08lx\n", Status);
32 return Status;
33 }
34
36
37 if (fcb->inode_item.st_size > 0) {
38 Status = excise_extents(fcb->Vcb, fcb, 0, sector_align(fcb->inode_item.st_size, fcb->Vcb->superblock.sector_size), Irp, rollback);
39 if (!NT_SUCCESS(Status)) {
40 ERR("excise_extents returned %08lx\n", Status);
41 return Status;
42 }
43 }
44
45 fcb->deleted = true;
46
47 Status = flush_fcb(fcb, false, batchlist, Irp);
48 if (!NT_SUCCESS(Status)) {
49 ERR("flush_fcb returned %08lx\n", Status);
51 return Status;
52 }
53
55
56 return STATUS_SUCCESS;
57}
58
60 KEY searchkey;
61 traverse_ptr tp, next_tp;
63 bool b;
65
67
68 searchkey.obj_id = FREE_SPACE_CACHE_ID;
69 searchkey.obj_type = 0;
70 searchkey.offset = 0;
71
72 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
73 if (!NT_SUCCESS(Status)) {
74 ERR("error - find_item returned %08lx\n", Status);
75 return Status;
76 }
77
78 do {
79 if (tp.item->key.obj_id > searchkey.obj_id || (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type > searchkey.obj_type))
80 break;
81
82 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) {
84 if (!NT_SUCCESS(Status)) {
85 ERR("delete_tree_item returned %08lx\n", Status);
86 return Status;
87 }
88
89 if (tp.item->size >= sizeof(FREE_SPACE_ITEM)) {
91
93 WARN("key (%I64x,%x,%I64x) does not point to an INODE_ITEM\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset);
94 else {
95 LIST_ENTRY* le;
96
98
99 if (!NT_SUCCESS(Status))
100 ERR("remove_free_space_inode for (%I64x,%x,%I64x) returned %08lx\n", fsi->key.obj_id, fsi->key.obj_type, fsi->key.offset, Status);
101
102 le = Vcb->chunks.Flink;
103 while (le != &Vcb->chunks) {
105
106 if (c->offset == tp.item->key.offset && c->cache) {
107 reap_fcb(c->cache);
108 c->cache = NULL;
109 }
110
111 le = le->Flink;
112 }
113 }
114 } else
115 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
116 }
117
118 b = find_next_item(Vcb, &tp, &next_tp, false, Irp);
119 if (b)
120 tp = next_tp;
121 } while (b);
122
124
125 if (NT_SUCCESS(Status))
127 else
129
130 if (Vcb->space_root) {
131 searchkey.obj_id = 0;
132 searchkey.obj_type = 0;
133 searchkey.offset = 0;
134
135 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp);
136 if (!NT_SUCCESS(Status)) {
137 ERR("find_item returned %08lx\n", Status);
138 return Status;
139 }
140
141 do {
143 if (!NT_SUCCESS(Status)) {
144 ERR("delete_tree_item returned %08lx\n", Status);
145 return Status;
146 }
147
148 b = find_next_item(Vcb, &tp, &next_tp, false, Irp);
149 if (b)
150 tp = next_tp;
151 } while (b);
152 }
153
154 // regenerate free space tree
155 if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE) {
156 LIST_ENTRY* le;
157
158 ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
159
160 le = Vcb->chunks.Flink;
161 while (le != &Vcb->chunks) {
163
164 if (!c->cache_loaded) {
166
168 if (!NT_SUCCESS(Status)) {
169 ERR("load_cache_chunk(%I64x) returned %08lx\n", c->offset, Status);
171 ExReleaseResourceLite(&Vcb->chunk_lock);
172 return Status;
173 }
174
175 c->changed = true;
176 c->space_changed = true;
177
179 }
180
181 le = le->Flink;
182 }
183
184 ExReleaseResourceLite(&Vcb->chunk_lock);
185 }
186
187 return Status;
188}
189
191 space* s;
192
194
195 if (!s) {
196 ERR("out of memory\n");
198 }
199
200 s->address = offset;
201 s->size = size;
202
203 if (IsListEmpty(list))
204 InsertTailList(list, &s->list_entry);
205 else {
207
208 if (s2->address < offset)
209 InsertTailList(list, &s->list_entry);
210 else {
211 LIST_ENTRY* le;
212
213 le = list->Flink;
214 while (le != list) {
216
217 if (s2->address > offset) {
218 InsertTailList(le, &s->list_entry);
219 goto size;
220 }
221
222 le = le->Flink;
223 }
224 }
225 }
226
227size:
228 if (!list_size)
229 return STATUS_SUCCESS;
230
231 if (IsListEmpty(list_size))
232 InsertTailList(list_size, &s->list_entry_size);
233 else {
234 space* s2 = CONTAINING_RECORD(list_size->Blink, space, list_entry_size);
235
236 if (s2->size >= size)
237 InsertTailList(list_size, &s->list_entry_size);
238 else {
239 LIST_ENTRY* le;
240
241 le = list_size->Flink;
242 while (le != list_size) {
243 s2 = CONTAINING_RECORD(le, space, list_entry_size);
244
245 if (s2->size <= size) {
246 InsertHeadList(le->Blink, &s->list_entry_size);
247 return STATUS_SUCCESS;
248 }
249
250 le = le->Flink;
251 }
252 }
253 }
254
255 return STATUS_SUCCESS;
256}
257
259 RTL_BITMAP bmph;
260 uint32_t i, len, *dwords = data;
261 ULONG runlength, index;
262
263 // flip bits
264 for (i = 0; i < Vcb->superblock.sector_size / sizeof(uint32_t); i++) {
265 dwords[i] = ~dwords[i];
266 }
267
268 len = Vcb->superblock.sector_size * 8;
269
271
272 index = 0;
273 runlength = RtlFindFirstRunClear(&bmph, &index);
274
275 while (runlength != 0) {
277
278 if (index >= len)
279 break;
280
281 if (index + runlength >= len) {
282 runlength = len - index;
283
284 if (runlength == 0)
285 break;
286 }
287
288 addr = offset + (index << Vcb->sector_shift);
289 length = runlength << Vcb->sector_shift;
290
291 add_space_entry(&c->space, &c->space_size, addr, length);
292 index += runlength;
293 *total_space += length;
294
295 runlength = RtlFindNextForwardRunClear(&bmph, index, &index);
296 }
297}
298
299static void order_space_entry(space* s, LIST_ENTRY* list_size) {
300 LIST_ENTRY* le;
301
302 if (IsListEmpty(list_size)) {
303 InsertHeadList(list_size, &s->list_entry_size);
304 return;
305 }
306
307 le = list_size->Flink;
308
309 while (le != list_size) {
310 space* s2 = CONTAINING_RECORD(le, space, list_entry_size);
311
312 if (s2->size <= s->size) {
313 InsertHeadList(le->Blink, &s->list_entry_size);
314 return;
315 }
316
317 le = le->Flink;
318 }
319
320 InsertTailList(list_size, &s->list_entry_size);
321}
322
323typedef struct {
327
329 uint64_t i;
330
331 for (i = 0; i < len; i++) {
332 LIST_ENTRY* le;
334 bool ignore = false;
335
336 le = stripes->Flink;
337 while (le != stripes) {
339
340 if (ss->stripe == off + i) {
341 ignore = true;
342 break;
343 }
344
345 le = le->Flink;
346 }
347
348 if (ignore)
349 continue;
350
352 if (!ss) {
353 ERR("out of memory\n");
355 }
356
357 ss->stripe = off + i;
358 InsertTailList(stripes, &ss->list_entry);
359 }
360
361 return STATUS_SUCCESS;
362}
363
366 CHUNK_ITEM* ci = c->chunk_item;
367 CHUNK_ITEM_STRIPE* cis = (CHUNK_ITEM_STRIPE*)&ci[1];
368 uint64_t off_start, off_end, space = 0;
369 uint16_t i = 0, j;
370 LIST_ENTRY stripes;
371
372 InitializeListHead(&stripes);
373
374 while (superblock_addrs[i] != 0) {
375 if (ci->type & BLOCK_FLAG_RAID0 || ci->type & BLOCK_FLAG_RAID10) {
376 for (j = 0; j < ci->num_stripes; j++) {
377 ULONG sub_stripes = max(ci->sub_stripes, 1);
378
379 if (cis[j].offset + (ci->size * ci->num_stripes / sub_stripes) > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
380 off_start = superblock_addrs[i] - cis[j].offset;
381 off_start -= off_start % ci->stripe_length;
382 off_start *= ci->num_stripes / sub_stripes;
383 off_start += (j / sub_stripes) * ci->stripe_length;
384
385 off_end = off_start + ci->stripe_length;
386
387 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, 1);
388 if (!NT_SUCCESS(Status)) {
389 ERR("add_superblock_stripe returned %08lx\n", Status);
390 goto end;
391 }
392 }
393 }
394 } else if (ci->type & BLOCK_FLAG_RAID5) {
395 for (j = 0; j < ci->num_stripes; j++) {
396 uint64_t stripe_size = ci->size / (ci->num_stripes - 1);
397
398 if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
399 off_start = superblock_addrs[i] - cis[j].offset;
400 off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 1));
401 off_start *= ci->num_stripes - 1;
402
403 off_end = off_start + (ci->stripe_length * (ci->num_stripes - 1));
404
405 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
406 if (!NT_SUCCESS(Status)) {
407 ERR("add_superblock_stripe returned %08lx\n", Status);
408 goto end;
409 }
410 }
411 }
412 } else if (ci->type & BLOCK_FLAG_RAID6) {
413 for (j = 0; j < ci->num_stripes; j++) {
414 uint64_t stripe_size = ci->size / (ci->num_stripes - 2);
415
416 if (cis[j].offset + stripe_size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
417 off_start = superblock_addrs[i] - cis[j].offset;
418 off_start -= off_start % (ci->stripe_length * (ci->num_stripes - 2));
419 off_start *= ci->num_stripes - 2;
420
421 off_end = off_start + (ci->stripe_length * (ci->num_stripes - 2));
422
423 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
424 if (!NT_SUCCESS(Status)) {
425 ERR("add_superblock_stripe returned %08lx\n", Status);
426 goto end;
427 }
428 }
429 }
430 } else { // SINGLE, DUPLICATE, RAID1, RAID1C3, RAID1C4
431 for (j = 0; j < ci->num_stripes; j++) {
432 if (cis[j].offset + ci->size > superblock_addrs[i] && cis[j].offset <= superblock_addrs[i] + sizeof(superblock)) {
433 off_start = ((superblock_addrs[i] - cis[j].offset) / c->chunk_item->stripe_length) * c->chunk_item->stripe_length;
434 off_end = sector_align(superblock_addrs[i] - cis[j].offset + sizeof(superblock), c->chunk_item->stripe_length);
435
436 Status = add_superblock_stripe(&stripes, off_start / ci->stripe_length, (off_end - off_start) / ci->stripe_length);
437 if (!NT_SUCCESS(Status)) {
438 ERR("add_superblock_stripe returned %08lx\n", Status);
439 goto end;
440 }
441 }
442 }
443 }
444
445 i++;
446 }
447
449
450end:
451 while (!IsListEmpty(&stripes)) {
452 LIST_ENTRY* le = RemoveHeadList(&stripes);
454
455 space++;
456
457 ExFreePool(ss);
458 }
459
460 if (NT_SUCCESS(Status))
461 *size = space * ci->stripe_length;
462
463 return Status;
464}
465
467 KEY searchkey;
469 FREE_SPACE_ITEM* fsi;
471 uint8_t* data;
473 uint32_t *checksums, crc32, num_sectors, num_valid_sectors, size;
474 FREE_SPACE_ENTRY* fse;
475 uint64_t num_entries, num_bitmaps, extent_length, bmpnum, off, total_space = 0, superblock_size;
476 LIST_ENTRY *le, rollback;
477
478 // FIXME - does this break if Vcb->superblock.sector_size is not 4096?
479
480 TRACE("(%p, %I64x)\n", Vcb, c->offset);
481
482 searchkey.obj_id = FREE_SPACE_CACHE_ID;
483 searchkey.obj_type = 0;
484 searchkey.offset = c->offset;
485
486 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
487 if (!NT_SUCCESS(Status)) {
488 ERR("error - find_item returned %08lx\n", Status);
489 return Status;
490 }
491
492 if (keycmp(tp.item->key, searchkey)) {
493 TRACE("(%I64x,%x,%I64x) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
494 return STATUS_NOT_FOUND;
495 }
496
497 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
498 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
499 return STATUS_NOT_FOUND;
500 }
501
502 fsi = (FREE_SPACE_ITEM*)tp.item->data;
503
504 if (fsi->key.obj_type != TYPE_INODE_ITEM) {
505 WARN("cache pointed to something other than an INODE_ITEM\n");
506 return STATUS_NOT_FOUND;
507 }
508
509 inode = fsi->key.obj_id;
510 num_entries = fsi->num_entries;
511 num_bitmaps = fsi->num_bitmaps;
512
513 Status = open_fcb(Vcb, Vcb->root_root, inode, BTRFS_TYPE_FILE, NULL, false, NULL, &c->cache, PagedPool, Irp);
514 if (!NT_SUCCESS(Status)) {
515 ERR("open_fcb returned %08lx\n", Status);
516 return STATUS_NOT_FOUND;
517 }
518
519 if (load_only)
520 return STATUS_SUCCESS;
521
522 if (c->cache->inode_item.st_size == 0) {
523 WARN("cache had zero length\n");
524 free_fcb(c->cache);
525 c->cache = NULL;
526 return STATUS_NOT_FOUND;
527 }
528
529 c->cache->inode_item.flags |= BTRFS_INODE_NODATACOW;
530
531 if (num_entries == 0 && num_bitmaps == 0)
532 return STATUS_SUCCESS;
533
534 size = (uint32_t)sector_align(c->cache->inode_item.st_size, Vcb->superblock.sector_size);
535
537
538 if (!data) {
539 ERR("out of memory\n");
540 free_fcb(c->cache);
541 c->cache = NULL;
543 }
544
545 if (c->chunk_item->size < 0x6400000) { // 100 MB
546 WARN("deleting free space cache for chunk smaller than 100MB\n");
547 goto clearcache;
548 }
549
550 Status = read_file(c->cache, data, 0, c->cache->inode_item.st_size, NULL, NULL);
551 if (!NT_SUCCESS(Status)) {
552 ERR("read_file returned %08lx\n", Status);
554
555 c->cache->deleted = true;
556 mark_fcb_dirty(c->cache);
557
558 free_fcb(c->cache);
559 c->cache = NULL;
560 return STATUS_NOT_FOUND;
561 }
562
563 if (size > c->cache->inode_item.st_size)
564 RtlZeroMemory(&data[c->cache->inode_item.st_size], (ULONG)(size - c->cache->inode_item.st_size));
565
566 num_sectors = size >> Vcb->sector_shift;
567
568 generation = (uint64_t*)(data + (num_sectors * sizeof(uint32_t)));
569
570 if (*generation != fsi->generation) {
571 WARN("free space cache generation for %I64x was %I64x, expected %I64x\n", c->offset, *generation, fsi->generation);
572 goto clearcache;
573 }
574
575 extent_length = (num_sectors * sizeof(uint32_t)) + sizeof(uint64_t) + (num_entries * sizeof(FREE_SPACE_ENTRY));
576
577 num_valid_sectors = (ULONG)((sector_align(extent_length, Vcb->superblock.sector_size) >> Vcb->sector_shift) + num_bitmaps);
578
579 if (num_valid_sectors > num_sectors) {
580 ERR("free space cache for %I64x was %u sectors, expected at least %u\n", c->offset, num_sectors, num_valid_sectors);
581 goto clearcache;
582 }
583
584 checksums = (uint32_t*)data;
585
586 for (uint32_t i = 0; i < num_valid_sectors; i++) {
587 if (i << Vcb->sector_shift > sizeof(uint32_t) * num_sectors)
588 crc32 = ~calc_crc32c(0xffffffff, &data[i << Vcb->sector_shift], Vcb->superblock.sector_size);
589 else if ((i + 1) << Vcb->sector_shift < sizeof(uint32_t) * num_sectors)
590 crc32 = 0; // FIXME - test this
591 else
592 crc32 = ~calc_crc32c(0xffffffff, &data[sizeof(uint32_t) * num_sectors], ((i + 1) << Vcb->sector_shift) - (sizeof(uint32_t) * num_sectors));
593
594 if (crc32 != checksums[i]) {
595 WARN("checksum %u was %08x, expected %08x\n", i, crc32, checksums[i]);
596 goto clearcache;
597 }
598 }
599
600 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t);
601
602 bmpnum = 0;
603 for (uint32_t i = 0; i < num_entries; i++) {
604 if ((off + sizeof(FREE_SPACE_ENTRY)) >> Vcb->sector_shift != off >> Vcb->sector_shift)
605 off = sector_align(off, Vcb->superblock.sector_size);
606
607 fse = (FREE_SPACE_ENTRY*)&data[off];
608
609 if (fse->type == FREE_SPACE_EXTENT) {
610 Status = add_space_entry(&c->space, &c->space_size, fse->offset, fse->size);
611 if (!NT_SUCCESS(Status)) {
612 ERR("add_space_entry returned %08lx\n", Status);
614 return Status;
615 }
616
617 total_space += fse->size;
618 } else if (fse->type != FREE_SPACE_BITMAP) {
619 ERR("unknown free-space type %x\n", fse->type);
620 }
621
622 off += sizeof(FREE_SPACE_ENTRY);
623 }
624
625 if (num_bitmaps > 0) {
626 bmpnum = sector_align(off, Vcb->superblock.sector_size) >> Vcb->sector_shift;
627 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t);
628
629 for (uint32_t i = 0; i < num_entries; i++) {
630 if ((off + sizeof(FREE_SPACE_ENTRY)) >> Vcb->sector_shift != off >> Vcb->sector_shift)
631 off = sector_align(off, Vcb->superblock.sector_size);
632
633 fse = (FREE_SPACE_ENTRY*)&data[off];
634
635 if (fse->type == FREE_SPACE_BITMAP) {
636 // FIXME - make sure we don't overflow the buffer here
637 load_free_space_bitmap(Vcb, c, fse->offset, &data[bmpnum << Vcb->sector_shift], &total_space);
638 bmpnum++;
639 }
640
641 off += sizeof(FREE_SPACE_ENTRY);
642 }
643 }
644
645 // do sanity check
646
647 Status = get_superblock_size(c, &superblock_size);
648 if (!NT_SUCCESS(Status)) {
649 ERR("get_superblock_size returned %08lx\n", Status);
651 return Status;
652 }
653
654 if (c->chunk_item->size - c->used != total_space + superblock_size) {
655 WARN("invalidating cache for chunk %I64x: space was %I64x, expected %I64x\n", c->offset, total_space + superblock_size, c->chunk_item->size - c->used);
656 goto clearcache;
657 }
658
659 le = c->space.Flink;
660 while (le != &c->space) {
662 LIST_ENTRY* le2 = le->Flink;
663
664 if (le2 != &c->space) {
666
667 if (s2->address == s->address + s->size) {
668 s->size += s2->size;
669
670 RemoveEntryList(&s2->list_entry);
671 RemoveEntryList(&s2->list_entry_size);
672 ExFreePool(s2);
673
674 RemoveEntryList(&s->list_entry_size);
675 order_space_entry(s, &c->space_size);
676
677 le2 = le;
678 }
679 }
680
681 le = le2;
682 }
683
685
686 return STATUS_SUCCESS;
687
688clearcache:
690
692
694 if (!NT_SUCCESS(Status)) {
695 ERR("delete_tree_item returned %08lx\n", Status);
696 return Status;
697 }
698
699 Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, &rollback);
700 if (!NT_SUCCESS(Status)) {
701 ERR("excise_extents returned %08lx\n", Status);
703 return Status;
704 }
705
707
708 c->cache->deleted = true;
709 mark_fcb_dirty(c->cache);
710
711 c->old_cache = c->cache;
712 c->cache = NULL;
713
714 le = c->space.Flink;
715 while (le != &c->space) {
717 LIST_ENTRY* le2 = le->Flink;
718
719 RemoveEntryList(&s->list_entry);
720 RemoveEntryList(&s->list_entry_size);
721 ExFreePool(s);
722
723 le = le2;
724 }
725
726 return STATUS_NOT_FOUND;
727}
728
730 KEY searchkey;
731 traverse_ptr tp, next_tp;
733 ULONG* bmparr = NULL;
734 ULONG bmplen = 0;
735 LIST_ENTRY* le;
736
737 TRACE("(%p, %I64x)\n", Vcb, c->offset);
738
739 if (!Vcb->space_root)
740 return STATUS_NOT_FOUND;
741
742 searchkey.obj_id = c->offset;
743 searchkey.obj_type = TYPE_FREE_SPACE_INFO;
744 searchkey.offset = c->chunk_item->size;
745
746 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp);
747 if (!NT_SUCCESS(Status)) {
748 ERR("find_item returned %08lx\n", Status);
749 return Status;
750 }
751
752 if (keycmp(tp.item->key, searchkey)) {
753 TRACE("(%I64x,%x,%I64x) not found\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
754 return STATUS_NOT_FOUND;
755 }
756
757 if (tp.item->size < sizeof(FREE_SPACE_INFO)) {
758 WARN("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_INFO));
759 return STATUS_NOT_FOUND;
760 }
761
762 while (find_next_item(Vcb, &tp, &next_tp, false, Irp)) {
763 tp = next_tp;
764
765 if (tp.item->key.obj_id >= c->offset + c->chunk_item->size)
766 break;
767
769 Status = add_space_entry(&c->space, &c->space_size, tp.item->key.obj_id, tp.item->key.offset);
770 if (!NT_SUCCESS(Status)) {
771 ERR("add_space_entry returned %08lx\n", Status);
772 if (bmparr) ExFreePool(bmparr);
773 return Status;
774 }
775 } else if (tp.item->key.obj_type == TYPE_FREE_SPACE_BITMAP) {
776 ULONG explen, index, runlength;
778 uint64_t lastoff;
779 ULONG bmpl;
780
781 explen = (ULONG)(tp.item->key.offset >> Vcb->sector_shift) / 8;
782
783 if (tp.item->size < explen) {
784 WARN("(%I64x,%x,%I64x) was %u bytes, expected %lu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, explen);
785 return STATUS_NOT_FOUND;
786 } else if (tp.item->size == 0) {
787 WARN("(%I64x,%x,%I64x) has size of 0\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
788 return STATUS_NOT_FOUND;
789 }
790
791 if (bmplen < tp.item->size) {
792 if (bmparr)
793 ExFreePool(bmparr);
794
795 bmplen = (ULONG)sector_align(tp.item->size, sizeof(ULONG));
796 bmparr = ExAllocatePoolWithTag(PagedPool, bmplen, ALLOC_TAG);
797 if (!bmparr) {
798 ERR("out of memory\n");
800 }
801 }
802
803 // We copy the bitmap because it supposedly has to be ULONG-aligned
804 RtlCopyMemory(bmparr, tp.item->data, tp.item->size);
805
806 bmpl = (ULONG)tp.item->key.offset >> Vcb->sector_shift;
807
808 RtlInitializeBitMap(&bmp, bmparr, bmpl);
809
810 lastoff = tp.item->key.obj_id;
811
812 runlength = RtlFindFirstRunClear(&bmp, &index);
813
814 while (runlength != 0) {
815 uint64_t runstart, runend;
816
817 if (index >= bmpl)
818 break;
819
820 if (index + runlength >= bmpl) {
821 runlength = bmpl - index;
822
823 if (runlength == 0)
824 break;
825 }
826
827 runstart = tp.item->key.obj_id + (index << Vcb->sector_shift);
828 runend = runstart + (runlength << Vcb->sector_shift);
829
830 if (runstart > lastoff) {
831 Status = add_space_entry(&c->space, &c->space_size, lastoff, runstart - lastoff);
832 if (!NT_SUCCESS(Status)) {
833 ERR("add_space_entry returned %08lx\n", Status);
834 if (bmparr) ExFreePool(bmparr);
835 return Status;
836 }
837 }
838
839 lastoff = runend;
840
841 runlength = RtlFindNextForwardRunClear(&bmp, index + runlength, &index);
842 }
843
844 if (lastoff < tp.item->key.obj_id + tp.item->key.offset) {
845 Status = add_space_entry(&c->space, &c->space_size, lastoff, tp.item->key.obj_id + tp.item->key.offset - lastoff);
846 if (!NT_SUCCESS(Status)) {
847 ERR("add_space_entry returned %08lx\n", Status);
848 if (bmparr) ExFreePool(bmparr);
849 return Status;
850 }
851 }
852 }
853 }
854
855 if (bmparr)
856 ExFreePool(bmparr);
857
858 le = c->space.Flink;
859 while (le != &c->space) {
861 LIST_ENTRY* le2 = le->Flink;
862
863 if (le2 != &c->space) {
865
866 if (s2->address == s->address + s->size) {
867 s->size += s2->size;
868
869 RemoveEntryList(&s2->list_entry);
870 RemoveEntryList(&s2->list_entry_size);
871 ExFreePool(s2);
872
873 RemoveEntryList(&s->list_entry_size);
874 order_space_entry(s, &c->space_size);
875
876 le2 = le;
877 }
878 }
879
880 le = le2;
881 }
882
883 return STATUS_SUCCESS;
884}
885
887 traverse_ptr tp, next_tp;
888 KEY searchkey;
889 uint64_t lastaddr;
890 bool b;
891 space* s;
893
894 if (Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE && Vcb->superblock.compat_ro_flags & BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID) {
896
898 ERR("load_stored_free_space_tree returned %08lx\n", Status);
899 return Status;
900 }
901 } else if (Vcb->superblock.generation - 1 == Vcb->superblock.cache_generation) {
903
905 ERR("load_stored_free_space_cache returned %08lx\n", Status);
906 return Status;
907 }
908 } else
910
911 if (Status == STATUS_NOT_FOUND) {
912 TRACE("generating free space cache for chunk %I64x\n", c->offset);
913
914 searchkey.obj_id = c->offset;
915 searchkey.obj_type = TYPE_EXTENT_ITEM;
916 searchkey.offset = 0;
917
918 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, false, Irp);
919 if (!NT_SUCCESS(Status)) {
920 ERR("error - find_item returned %08lx\n", Status);
921 return Status;
922 }
923
924 lastaddr = c->offset;
925
926 do {
927 if (tp.item->key.obj_id >= c->offset + c->chunk_item->size)
928 break;
929
931 if (tp.item->key.obj_id > lastaddr) {
933
934 if (!s) {
935 ERR("out of memory\n");
937 }
938
939 s->address = lastaddr;
940 s->size = tp.item->key.obj_id - lastaddr;
941 InsertTailList(&c->space, &s->list_entry);
942
943 order_space_entry(s, &c->space_size);
944
945 TRACE("(%I64x,%I64x)\n", s->address, s->size);
946 }
947
949 lastaddr = tp.item->key.obj_id + Vcb->superblock.node_size;
950 else
951 lastaddr = tp.item->key.obj_id + tp.item->key.offset;
952 }
953
954 b = find_next_item(Vcb, &tp, &next_tp, false, Irp);
955 if (b)
956 tp = next_tp;
957 } while (b);
958
959 if (lastaddr < c->offset + c->chunk_item->size) {
961
962 if (!s) {
963 ERR("out of memory\n");
965 }
966
967 s->address = lastaddr;
968 s->size = c->offset + c->chunk_item->size - lastaddr;
969 InsertTailList(&c->space, &s->list_entry);
970
971 order_space_entry(s, &c->space_size);
972
973 TRACE("(%I64x,%I64x)\n", s->address, s->size);
974 }
975 }
976
977 return STATUS_SUCCESS;
978}
979
982
983 if (c->cache_loaded)
984 return STATUS_SUCCESS;
985
987 if (!NT_SUCCESS(Status)) {
988 ERR("load_free_space_cache returned %08lx\n", Status);
989 return Status;
990 }
991
993
994 c->cache_loaded = true;
995
996 return STATUS_SUCCESS;
997}
998
1001 LIST_ENTRY* le = fcb->Vcb->chunks.Flink;
1002 chunk* c;
1004
1005 flags = fcb->Vcb->data_flags;
1006
1007 while (le != &fcb->Vcb->chunks) {
1009
1010 if (!c->readonly && !c->reloc) {
1012
1013 if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) {
1015 return STATUS_SUCCESS;
1016 }
1017
1019 }
1020
1021 le = le->Flink;
1022 }
1023
1024 Status = alloc_chunk(fcb->Vcb, flags, &c, false);
1025
1026 if (!NT_SUCCESS(Status)) {
1027 ERR("alloc_chunk returned %08lx\n", Status);
1028 return Status;
1029 }
1030
1032
1033 if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) {
1035 return STATUS_SUCCESS;
1036 }
1037
1039
1040 return STATUS_DISK_FULL;
1041}
1042
1044 LIST_ENTRY* le;
1046 uint64_t num_entries, new_cache_size, i;
1047 uint32_t num_sectors;
1048 bool realloc_extents = false;
1049
1050 // FIXME - also do bitmaps
1051 // FIXME - make sure this works when sector_size is not 4096
1052
1053 *changed = false;
1054
1055 num_entries = 0;
1056
1057 // num_entries is the number of entries in c->space and c->deleting - it might
1058 // be slightly higher then what we end up writing, but doing it this way is much
1059 // quicker and simpler.
1060 if (!IsListEmpty(&c->space)) {
1061 le = c->space.Flink;
1062 while (le != &c->space) {
1063 num_entries++;
1064
1065 le = le->Flink;
1066 }
1067 }
1068
1069 if (!IsListEmpty(&c->deleting)) {
1070 le = c->deleting.Flink;
1071 while (le != &c->deleting) {
1072 num_entries++;
1073
1074 le = le->Flink;
1075 }
1076 }
1077
1078 new_cache_size = sizeof(uint64_t) + (num_entries * sizeof(FREE_SPACE_ENTRY));
1079
1080 num_sectors = (uint32_t)sector_align(new_cache_size, Vcb->superblock.sector_size) >> Vcb->sector_shift;
1081 num_sectors = (uint32_t)sector_align(num_sectors, CACHE_INCREMENTS);
1082
1083 // adjust for padding
1084 // FIXME - there must be a more efficient way of doing this
1085 new_cache_size = sizeof(uint64_t) + (sizeof(uint32_t) * num_sectors);
1086 for (i = 0; i < num_entries; i++) {
1087 if ((new_cache_size >> Vcb->sector_shift) != ((new_cache_size + sizeof(FREE_SPACE_ENTRY)) >> Vcb->sector_shift))
1088 new_cache_size = sector_align(new_cache_size, Vcb->superblock.sector_size);
1089
1090 new_cache_size += sizeof(FREE_SPACE_ENTRY);
1091 }
1092
1093 new_cache_size = sector_align(new_cache_size, CACHE_INCREMENTS << Vcb->sector_shift);
1094
1095 TRACE("chunk %I64x: cache_size = %I64x, new_cache_size = %I64x\n", c->offset, c->cache ? c->cache->inode_item.st_size : 0, new_cache_size);
1096
1097 if (c->cache) {
1098 if (new_cache_size > c->cache->inode_item.st_size)
1099 realloc_extents = true;
1100 else {
1101 le = c->cache->extents.Flink;
1102
1103 while (le != &c->cache->extents) {
1105
1106 if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) {
1107 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0];
1108
1109 if (ed2->size != 0) {
1111
1112 if (c2 && (c2->readonly || c2->reloc)) {
1113 realloc_extents = true;
1114 break;
1115 }
1116 }
1117 }
1118
1119 le = le->Flink;
1120 }
1121 }
1122 }
1123
1124 if (!c->cache) {
1125 FREE_SPACE_ITEM* fsi;
1126 KEY searchkey;
1128
1129 // create new inode
1130
1131 c->cache = create_fcb(Vcb, PagedPool);
1132 if (!c->cache) {
1133 ERR("out of memory\n");
1135 }
1136
1137 c->cache->Vcb = Vcb;
1138
1139 c->cache->inode_item.st_size = new_cache_size;
1140 c->cache->inode_item.st_blocks = new_cache_size;
1141 c->cache->inode_item.st_nlink = 1;
1142 c->cache->inode_item.st_mode = S_IRUSR | S_IWUSR | __S_IFREG;
1144
1145 c->cache->Header.IsFastIoPossible = fast_io_possible(c->cache);
1146 c->cache->Header.AllocationSize.QuadPart = 0;
1147 c->cache->Header.FileSize.QuadPart = 0;
1148 c->cache->Header.ValidDataLength.QuadPart = 0;
1149
1150 c->cache->subvol = Vcb->root_root;
1151
1152 c->cache->inode = InterlockedIncrement64(&Vcb->root_root->lastinode);
1153 c->cache->hash = calc_crc32c(0xffffffff, (uint8_t*)&c->cache->inode, sizeof(uint64_t));
1154
1155 c->cache->type = BTRFS_TYPE_FILE;
1156 c->cache->created = true;
1157
1158 // create new free space entry
1159
1161 if (!fsi) {
1162 ERR("out of memory\n");
1163 reap_fcb(c->cache);
1164 c->cache = NULL;
1166 }
1167
1168 searchkey.obj_id = FREE_SPACE_CACHE_ID;
1169 searchkey.obj_type = 0;
1170 searchkey.offset = c->offset;
1171
1172 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1173 if (!NT_SUCCESS(Status)) {
1174 ERR("error - find_item returned %08lx\n", Status);
1175 ExFreePool(fsi);
1176 reap_fcb(c->cache);
1177 c->cache = NULL;
1178 return Status;
1179 }
1180
1181 if (!keycmp(searchkey, tp.item->key)) {
1183 if (!NT_SUCCESS(Status)) {
1184 ERR("delete_tree_item returned %08lx\n", Status);
1185 ExFreePool(fsi);
1186 reap_fcb(c->cache);
1187 c->cache = NULL;
1188 return Status;
1189 }
1190 }
1191
1192 fsi->key.obj_id = c->cache->inode;
1194 fsi->key.offset = 0;
1195
1196 Status = insert_tree_item(Vcb, Vcb->root_root, FREE_SPACE_CACHE_ID, 0, c->offset, fsi, sizeof(FREE_SPACE_ITEM), NULL, Irp);
1197 if (!NT_SUCCESS(Status)) {
1198 ERR("insert_tree_item returned %08lx\n", Status);
1199 ExFreePool(fsi);
1200 reap_fcb(c->cache);
1201 c->cache = NULL;
1202 return Status;
1203 }
1204
1205 // allocate space
1206
1207 Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback);
1208 if (!NT_SUCCESS(Status)) {
1209 ERR("insert_cache_extent returned %08lx\n", Status);
1210 reap_fcb(c->cache);
1211 c->cache = NULL;
1212 return Status;
1213 }
1214
1215 c->cache->extents_changed = true;
1216 InsertTailList(&Vcb->all_fcbs, &c->cache->list_entry_all);
1217
1218 add_fcb_to_subvol(c->cache);
1219
1220 Status = flush_fcb(c->cache, true, batchlist, Irp);
1221 if (!NT_SUCCESS(Status)) {
1222 ERR("flush_fcb returned %08lx\n", Status);
1223 free_fcb(c->cache);
1224 c->cache = NULL;
1225 return Status;
1226 }
1227
1228 *changed = true;
1229 } else if (realloc_extents) {
1230 KEY searchkey;
1232
1233 TRACE("reallocating extents\n");
1234
1235 // add free_space entry to tree cache
1236
1237 searchkey.obj_id = FREE_SPACE_CACHE_ID;
1238 searchkey.obj_type = 0;
1239 searchkey.offset = c->offset;
1240
1241 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1242 if (!NT_SUCCESS(Status)) {
1243 ERR("error - find_item returned %08lx\n", Status);
1244 return Status;
1245 }
1246
1247 if (keycmp(searchkey, tp.item->key)) {
1248 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1249 return STATUS_INTERNAL_ERROR;
1250 }
1251
1252 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1253 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1254 return STATUS_INTERNAL_ERROR;
1255 }
1256
1257 tp.tree->write = true;
1258
1259 // remove existing extents
1260
1261 if (c->cache->inode_item.st_size > 0) {
1262 le = c->cache->extents.Flink;
1263
1264 while (le != &c->cache->extents) {
1266
1267 if (!ext->ignore && (ext->extent_data.type == EXTENT_TYPE_REGULAR || ext->extent_data.type == EXTENT_TYPE_PREALLOC)) {
1268 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)&ext->extent_data.data[0];
1269
1270 if (ed2->size != 0) {
1272
1273 if (c2) {
1274 c2->changed = true;
1275 c2->space_changed = true;
1276 }
1277 }
1278 }
1279
1280 le = le->Flink;
1281 }
1282
1283 Status = excise_extents(Vcb, c->cache, 0, c->cache->inode_item.st_size, Irp, rollback);
1284 if (!NT_SUCCESS(Status)) {
1285 ERR("excise_extents returned %08lx\n", Status);
1286 return Status;
1287 }
1288 }
1289
1290 // add new extent
1291
1292 Status = insert_cache_extent(c->cache, 0, new_cache_size, rollback);
1293 if (!NT_SUCCESS(Status)) {
1294 ERR("insert_cache_extent returned %08lx\n", Status);
1295 return Status;
1296 }
1297
1298 // modify INODE_ITEM
1299
1300 c->cache->inode_item.st_size = new_cache_size;
1301 c->cache->inode_item.st_blocks = new_cache_size;
1302
1303 Status = flush_fcb(c->cache, true, batchlist, Irp);
1304 if (!NT_SUCCESS(Status)) {
1305 ERR("flush_fcb returned %08lx\n", Status);
1306 return Status;
1307 }
1308
1309 *changed = true;
1310 } else {
1311 KEY searchkey;
1313
1314 // add INODE_ITEM and free_space entry to tree cache, for writing later
1315
1316 searchkey.obj_id = c->cache->inode;
1317 searchkey.obj_type = TYPE_INODE_ITEM;
1318 searchkey.offset = 0;
1319
1320 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1321 if (!NT_SUCCESS(Status)) {
1322 ERR("error - find_item returned %08lx\n", Status);
1323 return Status;
1324 }
1325
1326 if (keycmp(searchkey, tp.item->key)) {
1327 INODE_ITEM* ii;
1328
1330 if (!ii) {
1331 ERR("out of memory\n");
1333 }
1334
1335 RtlCopyMemory(ii, &c->cache->inode_item, sizeof(INODE_ITEM));
1336
1337 Status = insert_tree_item(Vcb, Vcb->root_root, c->cache->inode, TYPE_INODE_ITEM, 0, ii, sizeof(INODE_ITEM), NULL, Irp);
1338 if (!NT_SUCCESS(Status)) {
1339 ERR("insert_tree_item returned %08lx\n", Status);
1340 ExFreePool(ii);
1341 return Status;
1342 }
1343
1344 *changed = true;
1345 } else {
1346 if (tp.item->size < sizeof(INODE_ITEM)) {
1347 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(INODE_ITEM));
1348 return STATUS_INTERNAL_ERROR;
1349 }
1350
1351 tp.tree->write = true;
1352 }
1353
1354 searchkey.obj_id = FREE_SPACE_CACHE_ID;
1355 searchkey.obj_type = 0;
1356 searchkey.offset = c->offset;
1357
1358 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1359 if (!NT_SUCCESS(Status)) {
1360 ERR("error - find_item returned %08lx\n", Status);
1361 return Status;
1362 }
1363
1364 if (keycmp(searchkey, tp.item->key)) {
1365 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1366 return STATUS_INTERNAL_ERROR;
1367 }
1368
1369 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1370 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1371 return STATUS_INTERNAL_ERROR;
1372 }
1373
1374 tp.tree->write = true;
1375 }
1376
1377 // FIXME - reduce inode allocation if cache is shrinking. Make sure to avoid infinite write loops
1378
1379 return STATUS_SUCCESS;
1380}
1381
1383 LIST_ENTRY *le, batchlist;
1385
1386 *changed = false;
1387
1388 InitializeListHead(&batchlist);
1389
1390 ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, true);
1391
1392 le = Vcb->chunks.Flink;
1393 while (le != &Vcb->chunks) {
1395
1396 if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB
1397 bool b;
1398
1400 Status = allocate_cache_chunk(Vcb, c, &b, &batchlist, Irp, rollback);
1402
1403 if (b)
1404 *changed = true;
1405
1406 if (!NT_SUCCESS(Status)) {
1407 ERR("allocate_cache_chunk(%I64x) returned %08lx\n", c->offset, Status);
1408 ExReleaseResourceLite(&Vcb->chunk_lock);
1409 clear_batch_list(Vcb, &batchlist);
1410 return Status;
1411 }
1412 }
1413
1414 le = le->Flink;
1415 }
1416
1417 ExReleaseResourceLite(&Vcb->chunk_lock);
1418
1419 Status = commit_batch_list(Vcb, &batchlist, Irp);
1420 if (!NT_SUCCESS(Status)) {
1421 ERR("commit_batch_list returned %08lx\n", Status);
1422 return Status;
1423 }
1424
1425 return STATUS_SUCCESS;
1426}
1427
1429 rollback_space* rs;
1430
1432 if (!rs) {
1433 ERR("out of memory\n");
1434 return;
1435 }
1436
1437 rs->list = list;
1438 rs->list_size = list_size;
1439 rs->address = address;
1440 rs->length = length;
1441 rs->chunk = c;
1442
1444}
1445
1447 LIST_ENTRY* le;
1448 space *s, *s2;
1449
1450 if (IsListEmpty(list)) {
1452
1453 if (!s) {
1454 ERR("out of memory\n");
1455 return;
1456 }
1457
1458 s->address = address;
1459 s->size = length;
1460 InsertTailList(list, &s->list_entry);
1461
1462 if (list_size)
1463 InsertTailList(list_size, &s->list_entry_size);
1464
1465 if (rollback)
1466 add_rollback_space(rollback, true, list, list_size, address, length, c);
1467
1468 return;
1469 }
1470
1471 le = list->Flink;
1472 do {
1474
1475 // old entry envelops new one completely
1476 if (s2->address <= address && s2->address + s2->size >= address + length)
1477 return;
1478
1479 // new entry envelops old one completely
1480 if (address <= s2->address && address + length >= s2->address + s2->size) {
1481 if (address < s2->address) {
1482 if (rollback)
1483 add_rollback_space(rollback, true, list, list_size, address, s2->address - address, c);
1484
1485 s2->size += s2->address - address;
1486 s2->address = address;
1487
1488 while (s2->list_entry.Blink != list) {
1489 space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry);
1490
1491 if (s3->address + s3->size == s2->address) {
1492 s2->address = s3->address;
1493 s2->size += s3->size;
1494
1496
1497 if (list_size)
1499
1500 ExFreePool(s3);
1501 } else
1502 break;
1503 }
1504 }
1505
1506 if (length > s2->size) {
1507 if (rollback)
1508 add_rollback_space(rollback, true, list, list_size, s2->address + s2->size, address + length - s2->address - s2->size, c);
1509
1510 s2->size = length;
1511
1512 while (s2->list_entry.Flink != list) {
1513 space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry);
1514
1515 if (s3->address <= s2->address + s2->size) {
1516 s2->size = max(s2->size, s3->address + s3->size - s2->address);
1517
1519
1520 if (list_size)
1522
1523 ExFreePool(s3);
1524 } else
1525 break;
1526 }
1527 }
1528
1529 if (list_size) {
1530 RemoveEntryList(&s2->list_entry_size);
1531 order_space_entry(s2, list_size);
1532 }
1533
1534 return;
1535 }
1536
1537 // new entry overlaps start of old one
1538 if (address < s2->address && address + length >= s2->address) {
1539 if (rollback)
1540 add_rollback_space(rollback, true, list, list_size, address, s2->address - address, c);
1541
1542 s2->size += s2->address - address;
1543 s2->address = address;
1544
1545 while (s2->list_entry.Blink != list) {
1546 space* s3 = CONTAINING_RECORD(s2->list_entry.Blink, space, list_entry);
1547
1548 if (s3->address + s3->size == s2->address) {
1549 s2->address = s3->address;
1550 s2->size += s3->size;
1551
1553
1554 if (list_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 // new entry overlaps end of old one
1571 if (address <= s2->address + s2->size && address + length > s2->address + s2->size) {
1572 if (rollback)
1573 add_rollback_space(rollback, true, list, list_size, address, s2->address + s2->size - address, c);
1574
1575 s2->size = address + length - s2->address;
1576
1577 while (s2->list_entry.Flink != list) {
1578 space* s3 = CONTAINING_RECORD(s2->list_entry.Flink, space, list_entry);
1579
1580 if (s3->address <= s2->address + s2->size) {
1581 s2->size = max(s2->size, s3->address + s3->size - s2->address);
1582
1584
1585 if (list_size)
1587
1588 ExFreePool(s3);
1589 } else
1590 break;
1591 }
1592
1593 if (list_size) {
1594 RemoveEntryList(&s2->list_entry_size);
1595 order_space_entry(s2, list_size);
1596 }
1597
1598 return;
1599 }
1600
1601 // add completely separate entry
1602 if (s2->address > address + length) {
1604
1605 if (!s) {
1606 ERR("out of memory\n");
1607 return;
1608 }
1609
1610 if (rollback)
1611 add_rollback_space(rollback, true, list, list_size, address, length, c);
1612
1613 s->address = address;
1614 s->size = length;
1615 InsertHeadList(s2->list_entry.Blink, &s->list_entry);
1616
1617 if (list_size)
1618 order_space_entry(s, list_size);
1619
1620 return;
1621 }
1622
1623 le = le->Flink;
1624 } while (le != list);
1625
1626 // check if contiguous with last entry
1627 if (s2->address + s2->size == address) {
1628 s2->size += length;
1629
1630 if (list_size) {
1631 RemoveEntryList(&s2->list_entry_size);
1632 order_space_entry(s2, list_size);
1633 }
1634
1635 return;
1636 }
1637
1638 // otherwise, insert at end
1640
1641 if (!s) {
1642 ERR("out of memory\n");
1643 return;
1644 }
1645
1646 s->address = address;
1647 s->size = length;
1648 InsertTailList(list, &s->list_entry);
1649
1650 if (list_size)
1651 order_space_entry(s, list_size);
1652
1653 if (rollback)
1654 add_rollback_space(rollback, true, list, list_size, address, length, c);
1655}
1656
1657void space_list_merge(LIST_ENTRY* spacelist, LIST_ENTRY* spacelist_size, LIST_ENTRY* deleting) {
1658 LIST_ENTRY* le = deleting->Flink;
1659
1660 while (le != deleting) {
1662
1663 space_list_add2(spacelist, spacelist_size, s->address, s->size, NULL, NULL);
1664
1665 le = le->Flink;
1666 }
1667}
1668
1669static NTSTATUS copy_space_list(LIST_ENTRY* old_list, LIST_ENTRY* new_list) {
1670 LIST_ENTRY* le;
1671
1672 le = old_list->Flink;
1673 while (le != old_list) {
1675 space* s2;
1676
1678 if (!s2) {
1679 ERR("out of memory\n");
1681 }
1682
1683 s2->address = s->address;
1684 s2->size = s->size;
1685
1686 InsertTailList(new_list, &s2->list_entry);
1687
1688 le = le->Flink;
1689 }
1690
1691 return STATUS_SUCCESS;
1692}
1693
1696 KEY searchkey;
1698 FREE_SPACE_ITEM* fsi;
1699 void* data;
1700 uint64_t num_entries, *cachegen, off;
1701 uint32_t *checksums, num_sectors;
1702 LIST_ENTRY space_list, deleting;
1703
1704 data = ExAllocatePoolWithTag(NonPagedPool, (ULONG)c->cache->inode_item.st_size, ALLOC_TAG);
1705 if (!data) {
1706 ERR("out of memory\n");
1708 }
1709
1710 RtlZeroMemory(data, (ULONG)c->cache->inode_item.st_size);
1711
1712 InitializeListHead(&space_list);
1713 InitializeListHead(&deleting);
1714
1715 Status = copy_space_list(&c->space, &space_list);
1716 if (!NT_SUCCESS(Status)) {
1717 ERR("copy_space_list returned %08lx\n", Status);
1718 goto end;
1719 }
1720
1721 Status = copy_space_list(&c->deleting, &deleting);
1722 if (!NT_SUCCESS(Status)) {
1723 ERR("copy_space_list returned %08lx\n", Status);
1724
1725 while (!IsListEmpty(&space_list)) {
1727 }
1728
1729 goto end;
1730 }
1731
1732 space_list_merge(&space_list, NULL, &deleting);
1733
1734 num_entries = 0;
1735 num_sectors = (uint32_t)(c->cache->inode_item.st_size >> Vcb->sector_shift);
1736 off = (sizeof(uint32_t) * num_sectors) + sizeof(uint64_t);
1737
1738 while (!IsListEmpty(&space_list)) {
1739 FREE_SPACE_ENTRY* fse;
1740
1742
1743 if ((off + sizeof(FREE_SPACE_ENTRY)) >> Vcb->sector_shift != off >> Vcb->sector_shift)
1744 off = sector_align(off, Vcb->superblock.sector_size);
1745
1746 fse = (FREE_SPACE_ENTRY*)((uint8_t*)data + off);
1747
1748 fse->offset = s->address;
1749 fse->size = s->size;
1750 fse->type = FREE_SPACE_EXTENT;
1751 num_entries++;
1752
1753 off += sizeof(FREE_SPACE_ENTRY);
1754 }
1755
1756 // update INODE_ITEM
1757
1758 c->cache->inode_item.generation = Vcb->superblock.generation;
1759 c->cache->inode_item.transid = Vcb->superblock.generation;
1760 c->cache->inode_item.sequence++;
1761 c->cache->inode_item.st_ctime = *now;
1762
1763 Status = flush_fcb(c->cache, true, batchlist, Irp);
1764 if (!NT_SUCCESS(Status)) {
1765 ERR("flush_fcb returned %08lx\n", Status);
1766 goto end;
1767 }
1768
1769 // update free_space item
1770
1771 searchkey.obj_id = FREE_SPACE_CACHE_ID;
1772 searchkey.obj_type = 0;
1773 searchkey.offset = c->offset;
1774
1775 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, false, Irp);
1776 if (!NT_SUCCESS(Status)) {
1777 ERR("error - find_item returned %08lx\n", Status);
1778 goto end;
1779 }
1780
1781 if (keycmp(searchkey, tp.item->key)) {
1782 ERR("could not find (%I64x,%x,%I64x) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1784 goto end;
1785 }
1786
1787 if (tp.item->size < sizeof(FREE_SPACE_ITEM)) {
1788 ERR("(%I64x,%x,%I64x) was %u bytes, expected %Iu\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(FREE_SPACE_ITEM));
1790 goto end;
1791 }
1792
1793 fsi = (FREE_SPACE_ITEM*)tp.item->data;
1794
1795 fsi->generation = Vcb->superblock.generation;
1796 fsi->num_entries = num_entries;
1797 fsi->num_bitmaps = 0;
1798
1799 // set cache generation
1800
1801 cachegen = (uint64_t*)((uint8_t*)data + (sizeof(uint32_t) * num_sectors));
1802 *cachegen = Vcb->superblock.generation;
1803
1804 // calculate cache checksums
1805
1806 checksums = (uint32_t*)data;
1807
1808 // FIXME - if we know sector is fully zeroed, use cached checksum
1809
1810 for (uint32_t i = 0; i < num_sectors; i++) {
1811 if (i << Vcb->sector_shift > sizeof(uint32_t) * num_sectors)
1812 checksums[i] = ~calc_crc32c(0xffffffff, (uint8_t*)data + (i << Vcb->sector_shift), Vcb->superblock.sector_size);
1813 else if ((i + 1) << Vcb->sector_shift < sizeof(uint32_t) * num_sectors)
1814 checksums[i] = 0; // FIXME - test this
1815 else
1816 checksums[i] = ~calc_crc32c(0xffffffff, (uint8_t*)data + (sizeof(uint32_t) * num_sectors), ((i + 1) << Vcb->sector_shift) - (sizeof(uint32_t) * num_sectors));
1817 }
1818
1819 // write cache
1820
1821 Status = do_write_file(c->cache, 0, c->cache->inode_item.st_size, data, NULL, false, 0, rollback);
1822 if (!NT_SUCCESS(Status)) {
1823 ERR("do_write_file returned %08lx\n", Status);
1824
1825 // Writing the cache isn't critical, so we don't return an error if writing fails. This means
1826 // we can still flush on a degraded mount if metadata is RAID1 but data is RAID0.
1827 }
1828
1830
1831end:
1833
1834 return Status;
1835}
1836
1839 LIST_ENTRY space_list;
1840 FREE_SPACE_INFO* fsi;
1841 KEY searchkey;
1843 uint32_t fsi_count = 0;
1844
1845 InitializeListHead(&space_list);
1846
1847 Status = copy_space_list(&c->space, &space_list);
1848 if (!NT_SUCCESS(Status)) {
1849 ERR("copy_space_list returned %08lx\n", Status);
1850 return Status;
1851 }
1852
1853 space_list_merge(&space_list, NULL, &c->deleting);
1854
1855 searchkey.obj_id = c->offset;
1856 searchkey.obj_type = TYPE_FREE_SPACE_EXTENT;
1857 searchkey.offset = 0xffffffffffffffff;
1858
1859 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp);
1860 if (Status == STATUS_NOT_FOUND)
1861 goto after_tree_walk;
1862 else if (!NT_SUCCESS(Status)) {
1863 ERR("find_item returned %08lx\n", Status);
1864
1865 while (!IsListEmpty(&space_list)) {
1867 }
1868
1869 return Status;
1870 }
1871
1872 while (!IsListEmpty(&space_list) && tp.item->key.obj_id < c->offset + c->chunk_item->size) {
1873 traverse_ptr next_tp;
1874
1876 space* s = CONTAINING_RECORD(space_list.Flink, space, list_entry);
1877
1878 if (s->address < tp.item->key.obj_id || (s->address == tp.item->key.obj_id && s->size < tp.item->key.offset)) {
1879 // add entry
1880
1881 Status = insert_tree_item(Vcb, Vcb->space_root, s->address, TYPE_FREE_SPACE_EXTENT, s->size, NULL, 0,
1882 NULL, Irp);
1883 if (!NT_SUCCESS(Status)) {
1884 ERR("insert_tree_item returned %08lx\n", Status);
1885
1886 while (!IsListEmpty(&space_list)) {
1888 }
1889
1890 return Status;
1891 }
1892
1893 fsi_count++;
1894
1895 RemoveHeadList(&space_list);
1896 ExFreePool(s);
1897 continue;
1898 } else if (s->address == tp.item->key.obj_id && s->size == tp.item->key.offset) {
1899 // unchanged entry
1900
1901 fsi_count++;
1902
1903 RemoveHeadList(&space_list);
1904 ExFreePool(s);
1905 } else {
1906 // remove entry
1907
1909 if (!NT_SUCCESS(Status)) {
1910 ERR("delete_tree_item returned %08lx\n", Status);
1911
1912 while (!IsListEmpty(&space_list)) {
1914 }
1915
1916 return Status;
1917 }
1918 }
1919 } else if (tp.item->key.obj_type == TYPE_FREE_SPACE_BITMAP) {
1921 if (!NT_SUCCESS(Status)) {
1922 ERR("delete_tree_item returned %08lx\n", Status);
1923
1924 while (!IsListEmpty(&space_list)) {
1926 }
1927
1928 return Status;
1929 }
1930 }
1931
1932 if (!find_next_item(Vcb, &tp, &next_tp, false, Irp))
1933 goto after_tree_walk;
1934
1935 tp = next_tp;
1936 }
1937
1938 // after loop, delete remaining tree items for this chunk
1939
1940 while (tp.item->key.obj_id < c->offset + c->chunk_item->size) {
1941 traverse_ptr next_tp;
1942
1945 if (!NT_SUCCESS(Status)) {
1946 ERR("delete_tree_item returned %08lx\n", Status);
1947 return Status;
1948 }
1949 }
1950
1951 if (!find_next_item(Vcb, &tp, &next_tp, false, NULL))
1952 break;
1953
1954 tp = next_tp;
1955 }
1956
1957after_tree_walk:
1958 // after loop, insert remaining space_list entries
1959
1960 while (!IsListEmpty(&space_list)) {
1962
1963 Status = insert_tree_item(Vcb, Vcb->space_root, s->address, TYPE_FREE_SPACE_EXTENT, s->size, NULL, 0,
1964 NULL, Irp);
1965 if (!NT_SUCCESS(Status)) {
1966 ERR("insert_tree_item returned %08lx\n", Status);
1967
1968 while (!IsListEmpty(&space_list)) {
1970 }
1971
1972 return Status;
1973 }
1974
1975 fsi_count++;
1976
1977 ExFreePool(s);
1978 }
1979
1980 // change TYPE_FREE_SPACE_INFO in place if present, and insert otherwise
1981
1982 searchkey.obj_id = c->offset;
1983 searchkey.obj_type = TYPE_FREE_SPACE_INFO;
1984 searchkey.offset = c->chunk_item->size;
1985
1986 Status = find_item(Vcb, Vcb->space_root, &tp, &searchkey, false, Irp);
1988 ERR("find_item returned %08lx\n", Status);
1989 return Status;
1990 }
1991
1992 if (NT_SUCCESS(Status) && !keycmp(tp.item->key, searchkey)) {
1993 if (tp.item->size == sizeof(FREE_SPACE_INFO)) {
1994 tree* t;
1995
1996 // change in place if possible
1997
1998 fsi = (FREE_SPACE_INFO*)tp.item->data;
1999
2000 fsi->count = fsi_count;
2001 fsi->flags = 0;
2002
2003 tp.tree->write = true;
2004
2005 t = tp.tree;
2006 while (t) {
2007 if (t->paritem && t->paritem->ignore) {
2008 t->paritem->ignore = false;
2009 t->parent->header.num_items++;
2010 t->parent->size += sizeof(internal_node);
2011 }
2012
2013 t->header.generation = Vcb->superblock.generation;
2014 t = t->parent;
2015 }
2016
2017 return STATUS_SUCCESS;
2018 } else
2020 }
2021
2022 // insert FREE_SPACE_INFO
2023
2025 if (!fsi) {
2026 ERR("out of memory\n");
2028 }
2029
2030 fsi->count = fsi_count;
2031 fsi->flags = 0;
2032
2033 Status = insert_tree_item(Vcb, Vcb->space_root, c->offset, TYPE_FREE_SPACE_INFO, c->chunk_item->size, fsi, sizeof(fsi),
2034 NULL, Irp);
2035 if (!NT_SUCCESS(Status)) {
2036 ERR("insert_tree_item returned %08lx\n", Status);
2037 return Status;
2038 }
2039
2040 return STATUS_SUCCESS;
2041}
2042
2044 LIST_ENTRY *le, batchlist;
2046 chunk* c;
2049
2052
2053 InitializeListHead(&batchlist);
2054
2055 le = Vcb->chunks.Flink;
2056 while (le != &Vcb->chunks) {
2058
2059 if (c->space_changed && c->chunk_item->size >= 0x6400000) { // 100MB
2061 Status = update_chunk_cache(Vcb, c, &now, &batchlist, Irp, rollback);
2063
2064 if (!NT_SUCCESS(Status)) {
2065 ERR("update_chunk_cache(%I64x) returned %08lx\n", c->offset, Status);
2066 clear_batch_list(Vcb, &batchlist);
2067 return Status;
2068 }
2069 }
2070
2071 le = le->Flink;
2072 }
2073
2074 Status = commit_batch_list(Vcb, &batchlist, Irp);
2075 if (!NT_SUCCESS(Status)) {
2076 ERR("commit_batch_list returned %08lx\n", Status);
2077 return Status;
2078 }
2079
2080 le = Vcb->chunks.Flink;
2081 while (le != &Vcb->chunks) {
2083
2084 if (c->changed && (c->chunk_item->type & BLOCK_FLAG_RAID5 || c->chunk_item->type & BLOCK_FLAG_RAID6)) {
2085 ExAcquireResourceExclusiveLite(&c->partial_stripes_lock, true);
2086
2087 while (!IsListEmpty(&c->partial_stripes)) {
2089
2091
2092 if (ps->bmparr)
2093 ExFreePool(ps->bmparr);
2094
2095 ExFreePool(ps);
2096
2097 if (!NT_SUCCESS(Status)) {
2098 ERR("flush_partial_stripe returned %08lx\n", Status);
2099 ExReleaseResourceLite(&c->partial_stripes_lock);
2100 return Status;
2101 }
2102 }
2103
2104 ExReleaseResourceLite(&c->partial_stripes_lock);
2105 }
2106
2107 le = le->Flink;
2108 }
2109
2110 return STATUS_SUCCESS;
2111}
2112
2114 LIST_ENTRY *le;
2116 chunk* c;
2117
2118 Vcb->superblock.compat_ro_flags |= BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID;
2119
2120 ExAcquireResourceSharedLite(&Vcb->chunk_lock, true);
2121
2122 le = Vcb->chunks.Flink;
2123 while (le != &Vcb->chunks) {
2125
2126 if (c->space_changed) {
2130
2131 if (!NT_SUCCESS(Status)) {
2132 ERR("update_chunk_cache_tree(%I64x) returned %08lx\n", c->offset, Status);
2133 ExReleaseResourceLite(&Vcb->chunk_lock);
2134 return Status;
2135 }
2136 }
2137
2138 le = le->Flink;
2139 }
2140
2141 ExReleaseResourceLite(&Vcb->chunk_lock);
2142
2143 return STATUS_SUCCESS;
2144}
2145
2147 TRACE("(%p, %I64x, %I64x, %p)\n", c, address, length, rollback);
2148
2149 c->changed = true;
2150 c->space_changed = true;
2151
2152 space_list_add2(&c->deleting, NULL, address, length, c, rollback);
2153}
2154
2156 LIST_ENTRY *le, *le2;
2157 space *s, *s2;
2158
2159 if (IsListEmpty(list))
2160 return;
2161
2162 le = list->Flink;
2163 while (le != list) {
2165 le2 = le->Flink;
2166
2167 if (s2->address >= address + length)
2168 return;
2169
2170 if (s2->address >= address && s2->address + s2->size <= address + length) { // remove entry entirely
2171 if (rollback)
2172 add_rollback_space(rollback, false, list, list_size, s2->address, s2->size, c);
2173
2174 RemoveEntryList(&s2->list_entry);
2175
2176 if (list_size)
2177 RemoveEntryList(&s2->list_entry_size);
2178
2179 ExFreePool(s2);
2180 } else if (address + length > s2->address && address + length < s2->address + s2->size) {
2181 if (address > s2->address) { // cut out hole
2182 if (rollback)
2183 add_rollback_space(rollback, false, list, list_size, address, length, c);
2184
2186
2187 if (!s) {
2188 ERR("out of memory\n");
2189 return;
2190 }
2191
2192 s->address = s2->address;
2193 s->size = address - s2->address;
2194 InsertHeadList(s2->list_entry.Blink, &s->list_entry);
2195
2196 s2->size = s2->address + s2->size - address - length;
2197 s2->address = address + length;
2198
2199 if (list_size) {
2200 RemoveEntryList(&s2->list_entry_size);
2201 order_space_entry(s2, list_size);
2202 order_space_entry(s, list_size);
2203 }
2204
2205 return;
2206 } else { // remove start of entry
2207 if (rollback)
2208 add_rollback_space(rollback, false, list, list_size, s2->address, address + length - s2->address, c);
2209
2210 s2->size -= address + length - s2->address;
2211 s2->address = address + length;
2212
2213 if (list_size) {
2214 RemoveEntryList(&s2->list_entry_size);
2215 order_space_entry(s2, list_size);
2216 }
2217 }
2218 } else if (address > s2->address && address < s2->address + s2->size) { // remove end of entry
2219 if (rollback)
2220 add_rollback_space(rollback, false, list, list_size, address, s2->address + s2->size - address, c);
2221
2222 s2->size = address - s2->address;
2223
2224 if (list_size) {
2225 RemoveEntryList(&s2->list_entry_size);
2226 order_space_entry(s2, list_size);
2227 }
2228 }
2229
2230 le = le2;
2231 }
2232}
2233
2235 c->changed = true;
2236 c->space_changed = true;
2237
2238 space_list_subtract2(&c->space, &c->space_size, address, length, c, rollback);
2239
2241}
unsigned short int uint16_t
Definition: acefiex.h:54
LONG NTSTATUS
Definition: precomp.h:26
#define index(s, c)
Definition: various.h:29
#define WARN(fmt,...)
Definition: debug.h:112
#define ERR(fmt,...)
Definition: debug.h:110
NTSTATUS read_file(fcb *fcb, uint8_t *data, uint64_t start, uint64_t length, ULONG *pbr, PIRP Irp) __attribute__((nonnull(1
#define acquire_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1139
#define InterlockedIncrement64(a)
Definition: btrfs_drv.h:143
_In_ fcb _In_ chunk _In_ uint64_t _In_ uint64_t _In_ bool _In_opt_ void _In_opt_ PIRP _In_ LIST_ENTRY * rollback
Definition: btrfs_drv.h:1365
static __inline FAST_IO_POSSIBLE fast_io_possible(fcb *fcb)
Definition: btrfs_drv.h:1684
NTSTATUS flush_fcb(fcb *fcb, bool cache, LIST_ENTRY *batchlist, PIRP Irp)
Definition: flushthread.c:4924
#define keycmp(key1, key2)
Definition: btrfs_drv.h:1016
#define __S_IFREG
Definition: btrfs_drv.h:1757
NTSTATUS alloc_chunk(device_extension *Vcb, uint64_t flags, chunk **pc, bool full_size) __attribute__((nonnull(1
NTSTATUS NTSTATUS NTSTATUS NTSTATUS NTSTATUS excise_extents(device_extension *Vcb, fcb *fcb, uint64_t start_data, uint64_t end_data, PIRP Irp, LIST_ENTRY *rollback) __attribute__((nonnull(1
void void void add_rollback(_In_ LIST_ENTRY *rollback, _In_ enum rollback_type type, _In_ __drv_aliasesMem void *ptr) __attribute__((nonnull(1
void void void NTSTATUS commit_batch_list(_Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp) __attribute__((nonnull(1
static __inline void win_time_to_unix(LARGE_INTEGER t, BTRFS_TIME *out)
Definition: btrfs_drv.h:989
struct _fcb fcb
Definition: btrfs_drv.h:1364
NTSTATUS do_write_file(fcb *fcb, uint64_t start_data, uint64_t end_data, void *data, PIRP Irp, bool file_write, uint32_t irp_offset, LIST_ENTRY *rollback) __attribute__((nonnull(1
#define ALLOC_TAG
Definition: btrfs_drv.h:87
NTSTATUS flush_partial_stripe(device_extension *Vcb, chunk *c, partial_stripe *ps)
Definition: flushthread.c:5958
NTSTATUS NTSTATUS NTSTATUS NTSTATUS NTSTATUS chunk * get_chunk_from_address(device_extension *Vcb, uint64_t address) __attribute__((nonnull(1)))
void do_rollback(device_extension *Vcb, LIST_ENTRY *rollback) __attribute__((nonnull(1
void void void NTSTATUS void clear_batch_list(device_extension *Vcb, LIST_ENTRY *batchlist) __attribute__((nonnull(1
@ ROLLBACK_ADD_SPACE
Definition: btrfs_drv.h:1270
@ ROLLBACK_SUBTRACT_SPACE
Definition: btrfs_drv.h:1271
NTSTATUS open_fcb(_Requires_lock_held_(_Curr_->tree_lock) _Requires_exclusive_lock_held_(_Curr_->fcb_lock) device_extension *Vcb, root *subvol, uint64_t inode, uint8_t type, PANSI_STRING utf8, bool always_add_hl, fcb *parent, fcb **pfcb, POOL_TYPE pooltype, PIRP Irp)
Definition: create.c:706
void add_fcb_to_subvol(_In_ _Requires_exclusive_lock_held_(_Curr_->Vcb->fcb_lock) fcb *fcb)
Definition: fileinfo.c:888
NTSTATUS insert_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _In_ root *r, _In_ uint64_t obj_id, _In_ uint8_t obj_type, _In_ uint64_t offset, _In_reads_bytes_opt_(size) _When_(return >=0, __drv_aliasesMem) void *data, _In_ uint16_t size, _Out_opt_ traverse_ptr *ptp, _In_opt_ PIRP Irp) __attribute__((nonnull(1
NTSTATUS NTSTATUS void clear_rollback(LIST_ENTRY *rollback) __attribute__((nonnull(1)))
fcb * create_fcb(device_extension *Vcb, POOL_TYPE pool_type)
Definition: create.c:91
NTSTATUS NTSTATUS bool find_next_item(_Requires_lock_held_(_Curr_->tree_lock) device_extension *Vcb, const traverse_ptr *tp, traverse_ptr *next_tp, bool ignore, PIRP Irp) __attribute__((nonnull(1
#define release_chunk_lock(c, Vcb)
Definition: btrfs_drv.h:1140
NTSTATUS NTSTATUS delete_tree_item(_In_ _Requires_exclusive_lock_held_(_Curr_->tree_lock) device_extension *Vcb, _Inout_ traverse_ptr *tp) __attribute__((nonnull(1
while(CdLookupNextInitialFileDirent(IrpContext, Fcb, FileContext))
Definition: list.h:37
static uint64_t __inline sector_align(uint64_t n, uint64_t a)
crc_func calc_crc32c
Definition: crc32c.c:23
_In_ PIRP Irp
Definition: csq.h:116
#define NULL
Definition: types.h:112
UINT32 uint32_t
Definition: types.h:75
UINT64 uint64_t
Definition: types.h:77
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
#define crc32(crc, buf, len)
Definition: inflate.c:1081
static const WCHAR *const ext[]
Definition: module.c:53
static LONG find_item(PropertyBag *This, LPCOLESTR name)
Definition: propertybag.c:110
void mark_fcb_dirty(_In_ fcb *fcb)
Definition: btrfs.c:1695
_In_ uint64_t _In_ uint64_t _In_ uint64_t _In_opt_ traverse_ptr * tp
Definition: btrfs.c:2996
void free_fcb(_Inout_ fcb *fcb)
Definition: btrfs.c:1734
void protect_superblocks(_Inout_ chunk *c)
Definition: btrfs.c:3777
_In_ uint64_t _In_ uint64_t _In_ uint64_t generation
Definition: btrfs.c:2996
void reap_fcb(fcb *fcb)
Definition: btrfs.c:1743
#define FREE_SPACE_CACHE_ID
Definition: btrfs.h:90
#define TYPE_FREE_SPACE_EXTENT
Definition: btrfs.h:44
#define EXTENT_TYPE_PREALLOC
Definition: btrfs.h:76
#define BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE
Definition: btrfs.h:111
static const uint64_t superblock_addrs[]
Definition: btrfs.h:16
#define TYPE_FREE_SPACE_BITMAP
Definition: btrfs.h:45
#define BTRFS_COMPAT_RO_FLAGS_FREE_SPACE_CACHE_VALID
Definition: btrfs.h:112
#define FREE_SPACE_EXTENT
Definition: btrfs.h:445
#define TYPE_EXTENT_ITEM
Definition: btrfs.h:35
#define EXTENT_TYPE_REGULAR
Definition: btrfs.h:75
#define BTRFS_COMPRESSION_NONE
Definition: btrfs.h:65
#define TYPE_FREE_SPACE_INFO
Definition: btrfs.h:43
#define TYPE_METADATA_ITEM
Definition: btrfs.h:36
#define TYPE_INODE_ITEM
Definition: btrfs.h:23
#define FREE_SPACE_BITMAP
Definition: btrfs.h:446
bool insert_extent_chunk(_In_ device_extension *Vcb, _In_ fcb *fcb, _In_ chunk *c, _In_ uint64_t start_data, _In_ uint64_t length, _In_ bool prealloc, _In_opt_ void *data, _In_opt_ PIRP Irp, _In_ LIST_ENTRY *rollback, _In_ uint8_t compression, _In_ uint64_t decoded_size, _In_ bool file_write, _In_ uint64_t irp_offset)
Definition: write.c:2824
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define InsertTailList(ListHead, Entry)
#define InsertHeadList(ListHead, Entry)
#define ExAllocatePoolWithTag(hernya, size, tag)
Definition: env_spec_w32.h:350
#define IsListEmpty(ListHead)
Definition: env_spec_w32.h:954
#define KeQuerySystemTime(t)
Definition: env_spec_w32.h:570
#define ExFreePool(addr)
Definition: env_spec_w32.h:352
#define ExAcquireResourceExclusiveLite(res, wait)
Definition: env_spec_w32.h:615
#define RemoveHeadList(ListHead)
Definition: env_spec_w32.h:964
#define NonPagedPool
Definition: env_spec_w32.h:307
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
#define ExAcquireResourceSharedLite(res, wait)
Definition: env_spec_w32.h:621
#define PagedPool
Definition: env_spec_w32.h:308
time_t now
Definition: finger.c:65
NTSTATUS load_stored_free_space_cache(device_extension *Vcb, chunk *c, bool load_only, PIRP Irp)
Definition: free-space.c:466
static NTSTATUS copy_space_list(LIST_ENTRY *old_list, LIST_ENTRY *new_list)
Definition: free-space.c:1669
static NTSTATUS add_superblock_stripe(LIST_ENTRY *stripes, uint64_t off, uint64_t len)
Definition: free-space.c:328
static NTSTATUS get_superblock_size(chunk *c, uint64_t *size)
Definition: free-space.c:364
static void add_rollback_space(LIST_ENTRY *rollback, bool add, LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c)
Definition: free-space.c:1428
static NTSTATUS update_chunk_cache(device_extension *Vcb, chunk *c, BTRFS_TIME *now, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1694
static NTSTATUS load_free_space_cache(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:886
static NTSTATUS allocate_cache_chunk(device_extension *Vcb, chunk *c, bool *changed, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1043
NTSTATUS load_cache_chunk(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:980
void space_list_add2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:1446
NTSTATUS add_space_entry(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t offset, uint64_t size)
Definition: free-space.c:190
static void load_free_space_bitmap(device_extension *Vcb, chunk *c, uint64_t offset, void *data, uint64_t *total_space)
Definition: free-space.c:258
static void order_space_entry(space *s, LIST_ENTRY *list_size)
Definition: free-space.c:299
void space_list_subtract2(LIST_ENTRY *list, LIST_ENTRY *list_size, uint64_t address, uint64_t length, chunk *c, LIST_ENTRY *rollback)
Definition: free-space.c:2155
static NTSTATUS insert_cache_extent(fcb *fcb, uint64_t start, uint64_t length, LIST_ENTRY *rollback)
Definition: free-space.c:999
NTSTATUS update_chunk_caches(device_extension *Vcb, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:2043
static NTSTATUS update_chunk_cache_tree(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:1837
#define CACHE_INCREMENTS
Definition: free-space.c:23
static NTSTATUS remove_free_space_inode(device_extension *Vcb, uint64_t inode, LIST_ENTRY *batchlist, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:25
NTSTATUS clear_free_space_cache(device_extension *Vcb, LIST_ENTRY *batchlist, PIRP Irp)
Definition: free-space.c:59
NTSTATUS update_chunk_caches_tree(device_extension *Vcb, PIRP Irp)
Definition: free-space.c:2113
void space_list_add(chunk *c, uint64_t address, uint64_t length, LIST_ENTRY *rollback)
Definition: free-space.c:2146
static NTSTATUS load_stored_free_space_tree(device_extension *Vcb, chunk *c, PIRP Irp)
Definition: free-space.c:729
void space_list_merge(LIST_ENTRY *spacelist, LIST_ENTRY *spacelist_size, LIST_ENTRY *deleting)
Definition: free-space.c:1657
NTSTATUS allocate_cache(device_extension *Vcb, bool *changed, PIRP Irp, LIST_ENTRY *rollback)
Definition: free-space.c:1382
void space_list_subtract(chunk *c, uint64_t address, uint64_t length, LIST_ENTRY *rollback)
Definition: free-space.c:2234
Status
Definition: gdiplustypes.h:25
GLuint start
Definition: gl.h:1545
GLdouble s
Definition: gl.h:2039
GLuint GLuint end
Definition: gl.h:1545
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLdouble GLdouble t
Definition: gl.h:2047
GLsizeiptr size
Definition: glext.h:5919
GLuint address
Definition: glext.h:9393
const GLubyte * c
Definition: glext.h:8905
GLuint index
Definition: glext.h:6031
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLbitfield flags
Definition: glext.h:7161
GLuint GLsizei GLsizei * length
Definition: glext.h:6040
GLenum const GLvoid * addr
Definition: glext.h:9621
GLenum GLsizei len
Definition: glext.h:6722
GLintptr offset
Definition: glext.h:5920
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define ss
Definition: i386-dis.c:441
NTSYSAPI void WINAPI RtlInitializeBitMap(PRTL_BITMAP, PULONG, ULONG)
NTSYSAPI ULONG WINAPI RtlFindNextForwardRunClear(PCRTL_BITMAP, ULONG, PULONG)
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
if(dx< 0)
Definition: linetemp.h:194
struct S2 s2
__u16 time
Definition: mkdosfs.c:8
BITMAP bmp
Definition: alphablend.c:62
BYTE uint8_t
Definition: msvideo1.c:66
#define uint32_t
Definition: nsiface.idl:61
#define uint64_t
Definition: nsiface.idl:62
VOID FASTCALL ExReleaseResourceLite(IN PERESOURCE Resource)
Definition: resource.c:1822
#define STATUS_INTERNAL_ERROR
Definition: ntstatus.h:465
#define Vcb
Definition: cdprocs.h:1415
#define BTRFS_INODE_PREALLOC
Definition: propsheet.h:80
#define BTRFS_INODE_NOCOMPRESS
Definition: propsheet.h:79
#define BTRFS_INODE_NODATASUM
Definition: propsheet.h:76
#define S_IRUSR
Definition: propsheet.h:29
#define BTRFS_INODE_NODATACOW
Definition: propsheet.h:77
#define S_IWUSR
Definition: propsheet.h:33
#define list
Definition: rosglue.h:35
#define BLOCK_FLAG_RAID5
Definition: shellext.h:82
#define BTRFS_TYPE_FILE
Definition: shellext.h:85
#define STATUS_SUCCESS
Definition: shellext.h:65
#define BLOCK_FLAG_RAID10
Definition: shellext.h:81
#define STATUS_NOT_FOUND
Definition: shellext.h:72
#define BLOCK_FLAG_RAID0
Definition: shellext.h:78
#define BLOCK_FLAG_RAID6
Definition: shellext.h:83
#define TRACE(s)
Definition: solgame.cpp:4
uint64_t offset
Definition: btrfs.h:353
uint16_t num_stripes
Definition: btrfs.h:347
uint64_t stripe_length
Definition: btrfs.h:342
uint16_t sub_stripes
Definition: btrfs.h:348
uint64_t size
Definition: btrfs.h:340
uint64_t type
Definition: btrfs.h:343
uint64_t address
Definition: btrfs.h:368
uint64_t size
Definition: btrfs.h:369
Definition: btrfs.h:448
uint64_t size
Definition: btrfs.h:450
uint64_t offset
Definition: btrfs.h:449
uint8_t type
Definition: btrfs.h:451
uint32_t flags
Definition: btrfs.h:536
uint32_t count
Definition: btrfs.h:535
uint64_t num_entries
Definition: btrfs.h:457
uint64_t generation
Definition: btrfs.h:456
uint64_t num_bitmaps
Definition: btrfs.h:458
uint64_t st_size
Definition: btrfs.h:289
Definition: btrfs.h:143
uint8_t obj_type
Definition: btrfs.h:145
uint64_t obj_id
Definition: btrfs.h:144
uint64_t offset
Definition: btrfs.h:146
Definition: typedefs.h:120
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
bool deleted
Definition: btrfs_drv.h:295
INODE_ITEM inode_item
Definition: btrfs_drv.h:292
struct _device_extension * Vcb
Definition: btrfs_drv.h:287
uint8_t * data
Definition: btrfs_drv.h:415
uint16_t size
Definition: btrfs_drv.h:414
bool write
Definition: btrfs_drv.h:440
bool readonly
Definition: btrfs_drv.h:580
bool reloc
Definition: btrfs_drv.h:581
bool changed
Definition: btrfs_drv.h:584
bool space_changed
Definition: btrfs_drv.h:585
Definition: fs.h:78
Definition: copy.c:22
Definition: list.h:27
ULONG * bmparr
Definition: btrfs_drv.h:554
LIST_ENTRY * list_size
Definition: btrfs_drv.h:1256
uint64_t address
Definition: btrfs_drv.h:1257
chunk * chunk
Definition: btrfs_drv.h:1259
LIST_ENTRY * list
Definition: btrfs_drv.h:1255
uint64_t length
Definition: btrfs_drv.h:1258
LIST_ENTRY list_entry
Definition: btrfs_drv.h:520
LIST_ENTRY list_entry_size
Definition: btrfs_drv.h:521
uint64_t address
Definition: btrfs_drv.h:518
uint64_t size
Definition: btrfs_drv.h:519
LIST_ENTRY list_entry
Definition: free-space.c:325
tree_data * item
Definition: btrfs_drv.h:509
tree * tree
Definition: btrfs_drv.h:508
#define max(a, b)
Definition: svc.c:63
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
#define STATUS_DISK_FULL
Definition: udferr_usr.h:155
#define STATUS_INSUFFICIENT_RESOURCES
Definition: udferr_usr.h:158
NTSYSAPI ULONG NTAPI RtlFindFirstRunClear(_In_ PRTL_BITMAP BitMapHeader, _Out_ PULONG StartingIndex)