1 /* Copyright (c) Mark Harmstone 2016
3 * This file is part of WinBtrfs.
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.
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.
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/>. */
18 #include "btrfs_drv.h"
20 #define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - sizeof(leaf_node))
23 BOOL chunk_test
= FALSE
;
34 } EXTENT_ITEM_DATA_REF
;
46 } EXTENT_ITEM_SKINNY_METADATA
;
50 CHUNK_ITEM_STRIPE stripes
[1];
53 static BOOL
extent_item_is_shared(EXTENT_ITEM
* ei
, ULONG len
);
54 static BOOL
is_file_prealloc(fcb
* fcb
, UINT64 start_data
, UINT64 end_data
);
56 static NTSTATUS STDCALL
write_completion(PDEVICE_OBJECT DeviceObject
, PIRP Irp
, PVOID conptr
) {
57 write_context
* context
= conptr
;
59 context
->iosb
= Irp
->IoStatus
;
60 KeSetEvent(&context
->Event
, 0, FALSE
);
62 // return STATUS_SUCCESS;
63 return STATUS_MORE_PROCESSING_REQUIRED
;
66 static NTSTATUS STDCALL
write_data_phys(PDEVICE_OBJECT device
, UINT64 address
, void* data
, UINT32 length
) {
70 PIO_STACK_LOCATION IrpSp
;
71 write_context
* context
= NULL
;
73 TRACE("(%p, %llx, %p, %x)\n", device
, address
, data
, length
);
75 context
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(write_context
), ALLOC_TAG
);
77 ERR("out of memory\n");
78 return STATUS_INSUFFICIENT_RESOURCES
;
81 RtlZeroMemory(context
, sizeof(write_context
));
83 KeInitializeEvent(&context
->Event
, NotificationEvent
, FALSE
);
85 offset
.QuadPart
= address
;
87 // Irp = IoBuildSynchronousFsdRequest(IRP_MJ_WRITE, Vcb->device, data, length, &offset, NULL, &context->iosb);
89 Irp
= IoAllocateIrp(device
->StackSize
, FALSE
);
92 ERR("IoAllocateIrp failed\n");
93 Status
= STATUS_INTERNAL_ERROR
;
97 IrpSp
= IoGetNextIrpStackLocation(Irp
);
98 IrpSp
->MajorFunction
= IRP_MJ_WRITE
;
100 if (device
->Flags
& DO_BUFFERED_IO
) {
101 Irp
->AssociatedIrp
.SystemBuffer
= data
;
103 Irp
->Flags
= IRP_BUFFERED_IO
;
104 } else if (device
->Flags
& DO_DIRECT_IO
) {
105 Irp
->MdlAddress
= IoAllocateMdl(data
, length
, FALSE
, FALSE
, NULL
);
106 if (!Irp
->MdlAddress
) {
107 DbgPrint("IoAllocateMdl failed\n");
111 MmProbeAndLockPages(Irp
->MdlAddress
, KernelMode
, IoWriteAccess
);
113 Irp
->UserBuffer
= data
;
116 IrpSp
->Parameters
.Write
.Length
= length
;
117 IrpSp
->Parameters
.Write
.ByteOffset
= offset
;
119 Irp
->UserIosb
= &context
->iosb
;
121 Irp
->UserEvent
= &context
->Event
;
123 IoSetCompletionRoutine(Irp
, write_completion
, context
, TRUE
, TRUE
, TRUE
);
125 // FIXME - support multiple devices
126 Status
= IoCallDriver(device
, Irp
);
128 if (Status
== STATUS_PENDING
) {
129 KeWaitForSingleObject(&context
->Event
, Executive
, KernelMode
, FALSE
, NULL
);
130 Status
= context
->iosb
.Status
;
133 if (!NT_SUCCESS(Status
)) {
134 ERR("IoCallDriver returned %08x\n", Status
);
137 if (device
->Flags
& DO_DIRECT_IO
) {
138 MmUnlockPages(Irp
->MdlAddress
);
139 IoFreeMdl(Irp
->MdlAddress
);
152 static NTSTATUS STDCALL
write_superblock(device_extension
* Vcb
, device
* device
) {
158 Status
= STATUS_INTERNAL_ERROR
;
161 // FIXME - work with RAID
163 // FIXME - only write one superblock if on SSD (?)
164 while (superblock_addrs
[i
] > 0 && Vcb
->length
>= superblock_addrs
[i
] + sizeof(superblock
)) {
165 TRACE("writing superblock %u\n", i
);
167 Vcb
->superblock
.sb_phys_addr
= superblock_addrs
[i
];
168 RtlCopyMemory(&Vcb
->superblock
.dev_item
, &device
->devitem
, sizeof(DEV_ITEM
));
170 crc32
= calc_crc32c(0xffffffff, (UINT8
*)&Vcb
->superblock
.uuid
, (ULONG
)sizeof(superblock
) - sizeof(Vcb
->superblock
.checksum
));
172 TRACE("crc32 is %08x\n", crc32
);
173 RtlCopyMemory(&Vcb
->superblock
.checksum
, &crc32
, sizeof(UINT32
));
175 Status
= write_data_phys(device
->devobj
, superblock_addrs
[i
], &Vcb
->superblock
, sizeof(superblock
));
177 if (!NT_SUCCESS(Status
))
186 static BOOL
find_address_in_chunk(device_extension
* Vcb
, chunk
* c
, UINT64 length
, UINT64
* address
) {
188 space
*s
, *bestfit
= NULL
;
190 TRACE("(%p, %llx, %llx, %p)\n", Vcb
, c
->offset
, length
, address
);
193 while (le
!= &c
->space
) {
194 s
= CONTAINING_RECORD(le
, space
, list_entry
);
196 if (s
->type
== SPACE_TYPE_FREE
) {
197 if (s
->size
== length
) {
198 *address
= s
->offset
;
199 TRACE("returning exact fit at %llx\n", s
->offset
);
201 } else if (s
->size
> length
&& (!bestfit
|| bestfit
->size
> s
->size
)) {
210 TRACE("returning best fit at %llx\n", bestfit
->offset
);
211 *address
= bestfit
->offset
;
218 void add_to_space_list(chunk
* c
, UINT64 offset
, UINT64 size
, UINT8 type
) {
219 LIST_ENTRY
*le
= c
->space
.Flink
, *nextle
, *insbef
;
221 #ifdef DEBUG_PARANOID
225 TRACE("(%p, %llx, %llx, %x)\n", c
, offset
, size
, type
);
227 #ifdef DEBUG_PARANOID
230 while (le
!= &c
->space
) {
231 s
= CONTAINING_RECORD(le
, space
, list_entry
);
233 TRACE("%llx,%llx,%x\n", s
->offset
, s
->size
, s
->type
);
239 c
->space_changed
= TRUE
;
243 while (le
!= &c
->space
) {
244 s
= CONTAINING_RECORD(le
, space
, list_entry
);
247 if (s
->offset
>= offset
+ size
) {
252 if (s
->offset
>= offset
&& s
->offset
+ s
->size
<= offset
+ size
) { // delete entirely
253 if (s
->offset
+ s
->size
== offset
+ size
) {
254 insbef
= s
->list_entry
.Flink
;
255 RemoveEntryList(&s
->list_entry
);
260 RemoveEntryList(&s
->list_entry
);
262 } else if (s
->offset
< offset
&& s
->offset
+ s
->size
> offset
+ size
) { // split in two
263 s3
= ExAllocatePoolWithTag(PagedPool
, sizeof(space
), ALLOC_TAG
);
265 ERR("out of memory\n");
269 s3
->offset
= offset
+ size
;
270 s3
->size
= s
->size
- size
- offset
+ s
->offset
;
272 InsertHeadList(&s
->list_entry
, &s3
->list_entry
);
273 insbef
= &s3
->list_entry
;
275 s
->size
= offset
- s
->offset
;
277 } else if (s
->offset
+ s
->size
> offset
&& s
->offset
+ s
->size
<= offset
+ size
) { // truncate before
278 s
->size
= offset
- s
->offset
;
279 } else if (s
->offset
< offset
+ size
&& s
->offset
+ s
->size
> offset
+ size
) { // truncate after
280 s
->size
-= offset
+ size
- s
->offset
;
281 s
->offset
= offset
+ size
;
290 s2
= ExAllocatePoolWithTag(PagedPool
, sizeof(space
), ALLOC_TAG
);
292 ERR("out of memory\n");
299 InsertTailList(insbef
, &s2
->list_entry
);
301 // merge entries if same type
303 if (s2
->list_entry
.Blink
!= &c
->space
) {
304 s
= CONTAINING_RECORD(s2
->list_entry
.Blink
, space
, list_entry
);
306 if (s
->type
== type
) {
309 RemoveEntryList(&s2
->list_entry
);
316 if (s2
->list_entry
.Flink
!= &c
->space
) {
317 s
= CONTAINING_RECORD(s2
->list_entry
.Flink
, space
, list_entry
);
319 if (s
->type
== type
) {
322 RemoveEntryList(&s
->list_entry
);
328 while (le
!= &c
->space
) {
329 s
= CONTAINING_RECORD(le
, space
, list_entry
);
331 TRACE("%llx,%llx,%x\n", s
->offset
, s
->size
, s
->type
);
336 #ifdef DEBUG_PARANOID
338 lastaddr
= c
->offset
;
340 while (le
!= &c
->space
) {
341 s
= CONTAINING_RECORD(le
, space
, list_entry
);
343 if (s
->offset
!= lastaddr
) {
344 ERR("inconsistency detected!\n");
348 lastaddr
= s
->offset
+ s
->size
;
353 if (lastaddr
!= c
->offset
+ c
->chunk_item
->size
) {
354 ERR("inconsistency detected - space doesn't run all the way to end of chunk\n");
360 chunk
* get_chunk_from_address(device_extension
* Vcb
, UINT64 address
) {
364 le2
= Vcb
->chunks
.Flink
;
365 while (le2
!= &Vcb
->chunks
) {
366 c
= CONTAINING_RECORD(le2
, chunk
, list_entry
);
368 // TRACE("chunk: %llx, %llx\n", c->offset, c->chunk_item->size);
370 if (address
>= c
->offset
&& address
< c
->offset
+ c
->chunk_item
->size
)
384 static void add_provisional_disk_hole(device_extension
* Vcb
, stripe
* s
, UINT64 max_stripe_size
) {
385 // LIST_ENTRY* le = s->device->disk_holes.Flink;
388 // ERR("old holes:\n");
389 // while (le != &s->device->disk_holes) {
390 // dh = CONTAINING_RECORD(le, disk_hole, listentry);
392 // ERR("address %llx, size %llx, provisional %u\n", dh->address, dh->size, dh->provisional);
397 if (s
->dh
->size
<= max_stripe_size
) {
398 s
->dh
->provisional
= TRUE
;
400 disk_hole
* newdh
= ExAllocatePoolWithTag(PagedPool
, sizeof(disk_hole
), ALLOC_TAG
);
402 ERR("out of memory\n");
406 newdh
->address
= s
->dh
->address
+ max_stripe_size
;
407 newdh
->size
= s
->dh
->size
- max_stripe_size
;
408 newdh
->provisional
= FALSE
;
409 InsertTailList(&s
->device
->disk_holes
, &newdh
->listentry
);
411 s
->dh
->size
= max_stripe_size
;
412 s
->dh
->provisional
= TRUE
;
415 // ERR("new holes:\n");
416 // le = s->device->disk_holes.Flink;
417 // while (le != &s->device->disk_holes) {
418 // dh = CONTAINING_RECORD(le, disk_hole, listentry);
420 // ERR("address %llx, size %llx, provisional %u\n", dh->address, dh->size, dh->provisional);
426 static UINT64
find_new_chunk_address(device_extension
* Vcb
, UINT64 size
) {
428 traverse_ptr tp
, next_tp
;
433 searchkey
.obj_id
= 0x100;
434 searchkey
.obj_type
= TYPE_CHUNK_ITEM
;
435 searchkey
.offset
= 0;
437 Status
= find_item(Vcb
, Vcb
->chunk_root
, &tp
, &searchkey
, FALSE
);
438 if (!NT_SUCCESS(Status
)) {
439 ERR("error - find_item returned %08x\n", Status
);
440 return 0xffffffffffffffff;
446 if (tp
.item
->key
.obj_type
== TYPE_CHUNK_ITEM
) {
447 if (tp
.item
->size
< sizeof(CHUNK_ITEM
)) {
448 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(CHUNK_ITEM
));
450 CHUNK_ITEM
* ci
= (CHUNK_ITEM
*)tp
.item
->data
;
452 if (tp
.item
->key
.offset
>= lastaddr
+ size
)
455 lastaddr
= tp
.item
->key
.offset
+ ci
->size
;
459 b
= find_next_item(Vcb
, &tp
, &next_tp
, FALSE
);
463 if (tp
.item
->key
.obj_id
> searchkey
.obj_id
|| tp
.item
->key
.obj_type
> searchkey
.obj_type
)
471 static BOOL
increase_dev_item_used(device_extension
* Vcb
, device
* device
, UINT64 size
, LIST_ENTRY
* rollback
) {
477 searchkey
.obj_id
= 1;
478 searchkey
.obj_type
= TYPE_DEV_ITEM
;
479 searchkey
.offset
= device
->devitem
.dev_id
;
481 Status
= find_item(Vcb
, Vcb
->chunk_root
, &tp
, &searchkey
, FALSE
);
482 if (!NT_SUCCESS(Status
)) {
483 ERR("error - find_item returned %08x\n", Status
);
487 if (keycmp(&tp
.item
->key
, &searchkey
)) {
488 ERR("error - could not find DEV_ITEM for device %llx\n", device
->devitem
.dev_id
);
492 delete_tree_item(Vcb
, &tp
, rollback
);
494 device
->devitem
.bytes_used
+= size
;
496 di
= ExAllocatePoolWithTag(PagedPool
, sizeof(DEV_ITEM
), ALLOC_TAG
);
498 ERR("out of memory\n");
502 RtlCopyMemory(di
, &device
->devitem
, sizeof(DEV_ITEM
));
504 if (!insert_tree_item(Vcb
, Vcb
->chunk_root
, 1, TYPE_DEV_ITEM
, device
->devitem
.dev_id
, di
, sizeof(DEV_ITEM
), NULL
, rollback
)) {
505 ERR("insert_tree_item failed\n");
512 static void reset_disk_holes(device
* device
, BOOL commit
) {
513 LIST_ENTRY
* le
= device
->disk_holes
.Flink
;
516 // ERR("old holes:\n");
517 // while (le != &device->disk_holes) {
518 // dh = CONTAINING_RECORD(le, disk_hole, listentry);
520 // ERR("address %llx, size %llx, provisional %u\n", dh->address, dh->size, dh->provisional);
525 le
= device
->disk_holes
.Flink
;
526 while (le
!= &device
->disk_holes
) {
527 LIST_ENTRY
* le2
= le
->Flink
;
529 dh
= CONTAINING_RECORD(le
, disk_hole
, listentry
);
531 if (dh
->provisional
) {
536 dh
->provisional
= FALSE
;
544 le
= device
->disk_holes
.Flink
;
545 while (le
!= &device
->disk_holes
) {
546 LIST_ENTRY
* le2
= le
->Flink
;
548 dh
= CONTAINING_RECORD(le
, disk_hole
, listentry
);
550 while (le2
!= &device
->disk_holes
) {
551 disk_hole
* dh2
= CONTAINING_RECORD(le2
, disk_hole
, listentry
);
553 if (dh2
->address
== dh
->address
+ dh
->size
) {
554 LIST_ENTRY
* le3
= le2
->Flink
;
555 dh
->size
+= dh2
->size
;
557 RemoveEntryList(le2
);
569 // ERR("new holes:\n");
570 // le = device->disk_holes.Flink;
571 // while (le != &device->disk_holes) {
572 // dh = CONTAINING_RECORD(le, disk_hole, listentry);
574 // ERR("address %llx, size %llx, provisional %u\n", dh->address, dh->size, dh->provisional);
580 static NTSTATUS
add_to_bootstrap(device_extension
* Vcb
, UINT64 obj_id
, UINT8 obj_type
, UINT64 offset
, void* data
, ULONG size
) {
585 if (Vcb
->superblock
.n
+ sizeof(KEY
) + size
> SYS_CHUNK_ARRAY_SIZE
) {
586 ERR("error - bootstrap is full\n");
587 return STATUS_INTERNAL_ERROR
;
590 sc
= ExAllocatePoolWithTag(PagedPool
, sizeof(sys_chunk
), ALLOC_TAG
);
592 ERR("out of memory\n");
593 return STATUS_INSUFFICIENT_RESOURCES
;
596 sc
->key
.obj_id
= obj_id
;
597 sc
->key
.obj_type
= obj_type
;
598 sc
->key
.offset
= offset
;
600 sc
->data
= ExAllocatePoolWithTag(PagedPool
, sc
->size
, ALLOC_TAG
);
602 ERR("out of memory\n");
604 return STATUS_INSUFFICIENT_RESOURCES
;
607 RtlCopyMemory(sc
->data
, data
, sc
->size
);
609 le
= Vcb
->sys_chunks
.Flink
;
610 while (le
!= &Vcb
->sys_chunks
) {
611 sc2
= CONTAINING_RECORD(le
, sys_chunk
, list_entry
);
613 if (keycmp(&sc2
->key
, &sc
->key
) == 1)
618 InsertTailList(le
, &sc
->list_entry
);
620 Vcb
->superblock
.n
+= sizeof(KEY
) + size
;
623 le
= Vcb
->sys_chunks
.Flink
;
624 while (le
!= &Vcb
->sys_chunks
) {
625 sc2
= CONTAINING_RECORD(le
, sys_chunk
, list_entry
);
627 TRACE("%llx,%x,%llx\n", sc2
->key
.obj_id
, sc2
->key
.obj_type
, sc2
->key
.offset
);
629 RtlCopyMemory(&Vcb
->superblock
.sys_chunk_array
[i
], &sc2
->key
, sizeof(KEY
));
632 RtlCopyMemory(&Vcb
->superblock
.sys_chunk_array
[i
], sc2
->data
, sc2
->size
);
638 return STATUS_SUCCESS
;
641 chunk
* alloc_chunk(device_extension
* Vcb
, UINT64 flags
, LIST_ENTRY
* rollback
) {
642 UINT64 max_stripe_size
, max_chunk_size
, stripe_size
;
643 UINT64 total_size
= 0, i
, j
, logaddr
;
649 CHUNK_ITEM_STRIPE
* cis
;
652 BOOL success
= FALSE
;
653 BLOCK_GROUP_ITEM
* bgi
;
655 for (i
= 0; i
< Vcb
->superblock
.num_devices
; i
++) {
656 total_size
+= Vcb
->devices
[i
].devitem
.num_bytes
;
658 TRACE("total_size = %llx\n", total_size
);
660 if (flags
& BLOCK_FLAG_DATA
) {
661 max_stripe_size
= 0x40000000; // 1 GB
662 max_chunk_size
= 10 * max_stripe_size
;
663 } else if (flags
& BLOCK_FLAG_METADATA
) {
664 if (total_size
> 0xC80000000) // 50 GB
665 max_stripe_size
= 0x40000000; // 1 GB
667 max_stripe_size
= 0x10000000; // 256 MB
669 max_chunk_size
= max_stripe_size
;
670 } else if (flags
& BLOCK_FLAG_SYSTEM
) {
671 max_stripe_size
= 0x2000000; // 32 MB
672 max_chunk_size
= 2 * max_stripe_size
;
675 // FIXME - make sure whole number of sectors?
676 max_chunk_size
= min(max_chunk_size
, total_size
/ 10); // cap at 10%
678 TRACE("would allocate a new chunk of %llx bytes and stripe %llx\n", max_chunk_size
, max_stripe_size
);
680 if (flags
& BLOCK_FLAG_DUPLICATE
) {
682 } else if (flags
& BLOCK_FLAG_RAID0
) {
683 FIXME("RAID0 not yet supported\n");
685 } else if (flags
& BLOCK_FLAG_RAID1
) {
686 FIXME("RAID1 not yet supported\n");
688 } else if (flags
& BLOCK_FLAG_RAID10
) {
689 FIXME("RAID10 not yet supported\n");
691 } else if (flags
& BLOCK_FLAG_RAID5
) {
692 FIXME("RAID5 not yet supported\n");
694 } else if (flags
& BLOCK_FLAG_RAID6
) {
695 FIXME("RAID6 not yet supported\n");
701 stripes
= ExAllocatePoolWithTag(PagedPool
, sizeof(stripe
) * num_stripes
, ALLOC_TAG
);
703 ERR("out of memory\n");
707 for (i
= 0; i
< num_stripes
; i
++) {
708 stripes
[i
].dh
= NULL
;
710 for (j
= 0; j
< Vcb
->superblock
.num_devices
; j
++) {
711 LIST_ENTRY
* le
= Vcb
->devices
[j
].disk_holes
.Flink
;
713 while (le
!= &Vcb
->devices
[j
].disk_holes
) {
714 dh
= CONTAINING_RECORD(le
, disk_hole
, listentry
);
716 if (!dh
->provisional
) {
717 if (!stripes
[i
].dh
|| dh
->size
> stripes
[i
].dh
->size
) {
719 stripes
[i
].device
= &Vcb
->devices
[j
];
721 if (stripes
[i
].dh
->size
>= max_stripe_size
)
729 if (stripes
[i
].dh
&& stripes
[i
].dh
->size
>= max_stripe_size
)
734 TRACE("good DH: device %llx, address %llx, size %llx\n", stripes
[i
].device
->devitem
.dev_id
, stripes
[i
].dh
->address
, stripes
[i
].dh
->size
);
736 TRACE("good DH not found\n");
740 add_provisional_disk_hole(Vcb
, &stripes
[i
], max_stripe_size
);
743 stripe_size
= min(stripes
[0].dh
->size
, max_stripe_size
);
744 for (i
= 1; i
< num_stripes
; i
++) {
745 stripe_size
= min(stripe_size
, stripes
[1].dh
->size
);
747 // FIXME - make sure stripe_size aligned properly
748 // FIXME - obey max_chunk_size
750 c
= ExAllocatePoolWithTag(PagedPool
, sizeof(chunk
), ALLOC_TAG
);
752 ERR("out of memory\n");
756 // add CHUNK_ITEM to tree 3
758 cisize
= sizeof(CHUNK_ITEM
) + (num_stripes
* sizeof(CHUNK_ITEM_STRIPE
));
759 ci
= ExAllocatePoolWithTag(PagedPool
, cisize
, ALLOC_TAG
);
761 ERR("out of memory\n");
765 ci
->size
= stripe_size
; // FIXME for RAID
766 ci
->root_id
= Vcb
->extent_root
->id
;
767 ci
->stripe_length
= 0x10000; // FIXME? BTRFS_STRIPE_LEN in kernel
769 ci
->opt_io_alignment
= ci
->stripe_length
;
770 ci
->opt_io_width
= ci
->stripe_length
;
771 ci
->sector_size
= stripes
[0].device
->devitem
.minimal_io_size
;
772 ci
->num_stripes
= num_stripes
;
775 c
->devices
= ExAllocatePoolWithTag(PagedPool
, sizeof(device
*) * num_stripes
, ALLOC_TAG
);
777 ERR("out of memory\n");
782 for (i
= 0; i
< num_stripes
; i
++) {
784 cis
= (CHUNK_ITEM_STRIPE
*)&ci
[1];
788 cis
->dev_id
= stripes
[i
].device
->devitem
.dev_id
;
789 cis
->offset
= stripes
[i
].dh
->address
;
790 cis
->dev_uuid
= stripes
[i
].device
->devitem
.device_uuid
;
792 c
->devices
[i
] = stripes
[i
].device
;
795 logaddr
= find_new_chunk_address(Vcb
, ci
->size
);
796 if (logaddr
== 0xffffffffffffffff) {
797 ERR("find_new_chunk_address failed\n");
802 if (!insert_tree_item(Vcb
, Vcb
->chunk_root
, 0x100, TYPE_CHUNK_ITEM
, logaddr
, ci
, cisize
, NULL
, rollback
)) {
803 ERR("insert_tree_item failed\n");
808 if (flags
& BLOCK_FLAG_SYSTEM
) {
809 NTSTATUS Status
= add_to_bootstrap(Vcb
, 0x100, TYPE_CHUNK_ITEM
, logaddr
, ci
, cisize
);
810 if (!NT_SUCCESS(Status
)) {
811 ERR("add_to_bootstrap returned %08x\n", Status
);
816 Vcb
->superblock
.chunk_root_generation
= Vcb
->superblock
.generation
;
818 c
->chunk_item
= ExAllocatePoolWithTag(PagedPool
, cisize
, ALLOC_TAG
);
819 if (!c
->chunk_item
) {
820 ERR("out of memory\n");
824 RtlCopyMemory(c
->chunk_item
, ci
, cisize
);
827 c
->used
= c
->oldused
= 0;
828 c
->space_changed
= FALSE
;
831 InitializeListHead(&c
->space
);
833 s
= ExAllocatePoolWithTag(PagedPool
, sizeof(space
), ALLOC_TAG
);
835 ERR("out of memory\n");
839 s
->offset
= c
->offset
;
840 s
->size
= c
->chunk_item
->size
;
841 s
->type
= SPACE_TYPE_FREE
;
842 InsertTailList(&c
->space
, &s
->list_entry
);
844 protect_superblocks(Vcb
, c
);
846 // add BLOCK_GROUP_ITEM to tree 2
848 bgi
= ExAllocatePoolWithTag(PagedPool
, sizeof(BLOCK_GROUP_ITEM
), ALLOC_TAG
);
850 ERR("out of memory\n");
855 bgi
->chunk_tree
= 0x100;
858 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, logaddr
, TYPE_BLOCK_GROUP_ITEM
, ci
->size
, bgi
, sizeof(BLOCK_GROUP_ITEM
), NULL
, rollback
)) {
859 ERR("insert_tree_item failed\n");
864 // add DEV_EXTENTs to tree 4
866 for (i
= 0; i
< num_stripes
; i
++) {
869 de
= ExAllocatePoolWithTag(PagedPool
, sizeof(DEV_EXTENT
), ALLOC_TAG
);
871 ERR("out of memory\n");
875 de
->chunktree
= Vcb
->chunk_root
->id
;
877 de
->address
= logaddr
;
878 de
->length
= ci
->size
;
879 de
->chunktree_uuid
= Vcb
->chunk_root
->treeholder
.tree
->header
.chunk_tree_uuid
;
881 if (!insert_tree_item(Vcb
, Vcb
->dev_root
, stripes
[i
].device
->devitem
.dev_id
, TYPE_DEV_EXTENT
, stripes
[i
].dh
->address
, de
, sizeof(DEV_EXTENT
), NULL
, rollback
)) {
882 ERR("insert_tree_item failed\n");
887 if (!increase_dev_item_used(Vcb
, stripes
[i
].device
, ci
->size
, rollback
)) {
888 ERR("increase_dev_item_used failed\n");
893 for (i
= 0; i
< num_stripes
; i
++) {
895 for (j
= 0; j
< i
; j
++) {
896 if (stripes
[j
].device
== stripes
[i
].device
)
901 reset_disk_holes(stripes
[i
].device
, TRUE
);
910 for (i
= 0; i
< num_stripes
; i
++) {
912 for (j
= 0; j
< i
; j
++) {
913 if (stripes
[j
].device
== stripes
[i
].device
)
918 reset_disk_holes(stripes
[i
].device
, FALSE
);
921 if (c
) ExFreePool(c
);
922 if (s
) ExFreePool(s
);
924 InsertTailList(&Vcb
->chunks
, &c
->list_entry
);
926 return success
? c
: NULL
;
929 NTSTATUS STDCALL
write_data(device_extension
* Vcb
, UINT64 address
, void* data
, UINT32 length
) {
936 TRACE("(%p, %llx, %p, %x)\n", Vcb
, address
, data
, length
);
938 // FIXME - use version cached in Vcb
940 searchkey
.obj_id
= 0x100; // fixed?
941 searchkey
.obj_type
= TYPE_CHUNK_ITEM
;
942 searchkey
.offset
= address
;
944 Status
= find_item(Vcb
, Vcb
->chunk_root
, &tp
, &searchkey
, FALSE
);
945 if (!NT_SUCCESS(Status
)) {
946 ERR("error - find_item returned %08x\n", Status
);
950 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
951 ERR("error - unexpected item in chunk tree\n");
952 Status
= STATUS_INTERNAL_ERROR
;
956 if (tp
.item
->size
< sizeof(CHUNK_ITEM2
)) {
957 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(CHUNK_ITEM2
));
958 Status
= STATUS_INTERNAL_ERROR
;
962 ci
= (CHUNK_ITEM2
*)tp
.item
->data
;
964 if (tp
.item
->key
.offset
> address
|| tp
.item
->key
.offset
+ ci
->ci
.size
< address
) {
965 ERR("error - address %llx was out of chunk bounds\n", address
);
966 Status
= STATUS_INTERNAL_ERROR
;
970 // FIXME - only do this for chunks marked DUPLICATE?
971 // FIXME - for multiple writes, if PENDING do waits at the end
972 // FIXME - work with RAID
973 for (i
= 0; i
< ci
->ci
.num_stripes
; i
++) {
974 Status
= write_data_phys(Vcb
->devices
[0].devobj
, address
- tp
.item
->key
.offset
+ ci
->stripes
[i
].offset
, data
, length
);
975 if (!NT_SUCCESS(Status
)) {
976 ERR("error - write_data_phys failed\n");
986 static void clean_space_cache_chunk(device_extension
* Vcb
, chunk
* c
) {
987 LIST_ENTRY
*le
, *nextle
;
991 // le = c->space.Flink;
992 // while (le != &c->space) {
993 // s = CONTAINING_RECORD(le, space, list_entry);
995 // TRACE("%x,%x,%x\n", (UINT32)s->offset, (UINT32)s->size, s->type);
1000 le
= c
->space
.Flink
;
1001 while (le
!= &c
->space
) {
1002 s
= CONTAINING_RECORD(le
, space
, list_entry
);
1005 if (s
->type
== SPACE_TYPE_DELETING
)
1006 s
->type
= SPACE_TYPE_FREE
;
1007 else if (s
->type
== SPACE_TYPE_WRITING
)
1008 s
->type
= SPACE_TYPE_USED
;
1010 if (le
->Blink
!= &c
->space
) {
1011 s2
= CONTAINING_RECORD(le
->Blink
, space
, list_entry
);
1013 if (s2
->type
== s
->type
) { // do merge
1014 s2
->size
+= s
->size
;
1016 RemoveEntryList(&s
->list_entry
);
1024 // le = c->space.Flink;
1025 // while (le != &c->space) {
1026 // s = CONTAINING_RECORD(le, space, list_entry);
1028 // TRACE("%x,%x,%x\n", (UINT32)s->offset, (UINT32)s->size, s->type);
1034 static void clean_space_cache(device_extension
* Vcb
) {
1038 TRACE("(%p)\n", Vcb
);
1040 le
= Vcb
->chunks
.Flink
;
1041 while (le
!= &Vcb
->chunks
) {
1042 c
= CONTAINING_RECORD(le
, chunk
, list_entry
);
1044 if (c
->space_changed
) {
1045 clean_space_cache_chunk(Vcb
, c
);
1046 c
->space_changed
= FALSE
;
1053 static BOOL
trees_consistent(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
1054 ULONG maxsize
= Vcb
->superblock
.node_size
- sizeof(tree_header
);
1057 le
= Vcb
->trees
.Flink
;
1058 while (le
!= &Vcb
->trees
) {
1059 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
1062 if (t
->header
.num_items
== 0 && t
->parent
)
1065 if (t
->size
> maxsize
)
1068 if (!t
->has_new_address
)
1078 static NTSTATUS
add_parents(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
1082 le
= Vcb
->trees
.Flink
;
1083 while (le
!= &Vcb
->trees
) {
1084 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
1088 if (!t
->parent
->write
) {
1089 t
->parent
->write
= TRUE
;
1092 } else if (t
->root
!= Vcb
->chunk_root
&& t
->root
!= Vcb
->root_root
) {
1096 searchkey
.obj_id
= t
->root
->id
;
1097 searchkey
.obj_type
= TYPE_ROOT_ITEM
;
1098 searchkey
.offset
= 0xffffffffffffffff;
1100 Status
= find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
);
1101 if (!NT_SUCCESS(Status
)) {
1102 ERR("error - find_item returned %08x\n", Status
);
1106 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
1107 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey
.obj_id
);
1108 return STATUS_INTERNAL_ERROR
;
1111 if (tp
.item
->size
< sizeof(ROOT_ITEM
)) { // if not full length, create new entry with new bits zeroed
1112 ROOT_ITEM
* ri
= ExAllocatePoolWithTag(PagedPool
, sizeof(ROOT_ITEM
), ALLOC_TAG
);
1114 ERR("out of memory\n");
1115 return STATUS_INSUFFICIENT_RESOURCES
;
1118 if (tp
.item
->size
> 0)
1119 RtlCopyMemory(ri
, tp
.item
->data
, tp
.item
->size
);
1121 RtlZeroMemory(((UINT8
*)ri
) + tp
.item
->size
, sizeof(ROOT_ITEM
) - tp
.item
->size
);
1123 delete_tree_item(Vcb
, &tp
, rollback
);
1125 if (!insert_tree_item(Vcb
, Vcb
->root_root
, searchkey
.obj_id
, searchkey
.obj_type
, tp
.item
->key
.offset
, ri
, sizeof(ROOT_ITEM
), NULL
, rollback
)) {
1126 ERR("insert_tree_item failed\n");
1127 return STATUS_INTERNAL_ERROR
;
1130 if (!tp
.tree
->write
) {
1131 tp
.tree
->write
= TRUE
;
1141 return STATUS_SUCCESS
;
1144 static void add_parents_to_cache(device_extension
* Vcb
, tree
* t
) {
1158 if (t
->root
== Vcb
->root_root
|| t
->root
== Vcb
->chunk_root
)
1161 searchkey
.obj_id
= t
->root
->id
;
1162 searchkey
.obj_type
= TYPE_ROOT_ITEM
;
1163 searchkey
.offset
= 0xffffffffffffffff;
1165 Status
= find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
);
1166 if (!NT_SUCCESS(Status
)) {
1167 ERR("error - find_item returned %08x\n", Status
);
1171 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
1172 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey
.obj_id
);
1176 if (!tp
.tree
->write
) {
1177 tp
.tree
->write
= TRUE
;
1182 static BOOL
insert_tree_extent_skinny(device_extension
* Vcb
, UINT8 level
, UINT64 root_id
, chunk
* c
, UINT64 address
, LIST_ENTRY
* rollback
) {
1183 EXTENT_ITEM_SKINNY_METADATA
* eism
;
1184 traverse_ptr insert_tp
;
1186 eism
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_ITEM_SKINNY_METADATA
), ALLOC_TAG
);
1188 ERR("out of memory\n");
1192 eism
->ei
.refcount
= 1;
1193 eism
->ei
.generation
= Vcb
->superblock
.generation
;
1194 eism
->ei
.flags
= EXTENT_ITEM_TREE_BLOCK
;
1195 eism
->type
= TYPE_TREE_BLOCK_REF
;
1196 eism
->tbr
.offset
= root_id
;
1198 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, address
, TYPE_METADATA_ITEM
, level
, eism
, sizeof(EXTENT_ITEM_SKINNY_METADATA
), &insert_tp
, rollback
)) {
1199 ERR("insert_tree_item failed\n");
1204 add_to_space_list(c
, address
, Vcb
->superblock
.node_size
, SPACE_TYPE_WRITING
);
1206 add_parents_to_cache(Vcb
, insert_tp
.tree
);
1211 static BOOL
insert_tree_extent(device_extension
* Vcb
, UINT8 level
, UINT64 root_id
, chunk
* c
, UINT64
* new_address
, LIST_ENTRY
* rollback
) {
1213 EXTENT_ITEM_TREE2
* eit2
;
1214 traverse_ptr insert_tp
;
1216 TRACE("(%p, %x, %llx, %p, %p, %p, %p)\n", Vcb
, level
, root_id
, c
, new_address
, rollback
);
1218 if (!find_address_in_chunk(Vcb
, c
, Vcb
->superblock
.node_size
, &address
))
1221 if (Vcb
->superblock
.incompat_flags
& BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
) {
1222 BOOL b
= insert_tree_extent_skinny(Vcb
, level
, root_id
, c
, address
, rollback
);
1225 *new_address
= address
;
1230 eit2
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_ITEM_TREE2
), ALLOC_TAG
);
1232 ERR("out of memory\n");
1236 eit2
->eit
.extent_item
.refcount
= 1;
1237 eit2
->eit
.extent_item
.generation
= Vcb
->superblock
.generation
;
1238 eit2
->eit
.extent_item
.flags
= EXTENT_ITEM_TREE_BLOCK
;
1239 // eit2->eit.firstitem = wt->firstitem;
1240 eit2
->eit
.level
= level
;
1241 eit2
->type
= TYPE_TREE_BLOCK_REF
;
1242 eit2
->tbr
.offset
= root_id
;
1244 // #ifdef DEBUG_PARANOID
1245 // if (wt->firstitem.obj_type == 0xcc) { // TESTING
1246 // ERR("error - firstitem not set (wt = %p, tree = %p, address = %x)\n", wt, wt->tree, (UINT32)address);
1247 // ERR("num_items = %u, level = %u, root = %x, delete = %u\n", wt->tree->header.num_items, wt->tree->header.level, (UINT32)wt->tree->root->id, wt->delete);
1252 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, address
, TYPE_EXTENT_ITEM
, Vcb
->superblock
.node_size
, eit2
, sizeof(EXTENT_ITEM_TREE2
), &insert_tp
, rollback
)) {
1253 ERR("insert_tree_item failed\n");
1258 add_to_space_list(c
, address
, Vcb
->superblock
.node_size
, SPACE_TYPE_WRITING
);
1260 add_parents_to_cache(Vcb
, insert_tp
.tree
);
1262 *new_address
= address
;
1267 NTSTATUS
get_tree_new_address(device_extension
* Vcb
, tree
* t
, LIST_ENTRY
* rollback
) {
1268 chunk
*origchunk
= NULL
, *c
;
1270 UINT64 flags
= t
->flags
, addr
;
1273 flags
= (t
->root
->id
== BTRFS_ROOT_CHUNK
? BLOCK_FLAG_SYSTEM
: BLOCK_FLAG_METADATA
) | BLOCK_FLAG_DUPLICATE
;
1275 // TRACE("flags = %x\n", (UINT32)wt->flags);
1277 // if (!chunk_test) { // TESTING
1278 // if ((c = alloc_chunk(Vcb, flags))) {
1279 // if ((c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
1280 // if (insert_tree_extent(Vcb, t, c)) {
1281 // chunk_test = TRUE;
1282 // return STATUS_SUCCESS;
1288 if (t
->has_address
) {
1289 origchunk
= get_chunk_from_address(Vcb
, t
->header
.address
);
1291 if (insert_tree_extent(Vcb
, t
->header
.level
, t
->header
.tree_id
, origchunk
, &addr
, rollback
)) {
1292 t
->new_address
= addr
;
1293 t
->has_new_address
= TRUE
;
1294 return STATUS_SUCCESS
;
1298 le
= Vcb
->chunks
.Flink
;
1299 while (le
!= &Vcb
->chunks
) {
1300 c
= CONTAINING_RECORD(le
, chunk
, list_entry
);
1302 if (c
!= origchunk
&& c
->chunk_item
->type
== flags
&& (c
->chunk_item
->size
- c
->used
) >= Vcb
->superblock
.node_size
) {
1303 if (insert_tree_extent(Vcb
, t
->header
.level
, t
->header
.tree_id
, c
, &addr
, rollback
)) {
1304 t
->new_address
= addr
;
1305 t
->has_new_address
= TRUE
;
1306 return STATUS_SUCCESS
;
1313 // allocate new chunk if necessary
1314 if ((c
= alloc_chunk(Vcb
, flags
, rollback
))) {
1315 if ((c
->chunk_item
->size
- c
->used
) >= Vcb
->superblock
.node_size
) {
1316 if (insert_tree_extent(Vcb
, t
->header
.level
, t
->header
.tree_id
, c
, &addr
, rollback
)) {
1317 t
->new_address
= addr
;
1318 t
->has_new_address
= TRUE
;
1319 return STATUS_SUCCESS
;
1324 ERR("couldn't find any metadata chunks with %x bytes free\n", Vcb
->superblock
.node_size
);
1326 return STATUS_DISK_FULL
;
1329 static BOOL
reduce_tree_extent_skinny(device_extension
* Vcb
, UINT64 address
, tree
* t
, LIST_ENTRY
* rollback
) {
1333 EXTENT_ITEM_SKINNY_METADATA
* eism
;
1336 searchkey
.obj_id
= address
;
1337 searchkey
.obj_type
= TYPE_METADATA_ITEM
;
1338 searchkey
.offset
= 0xffffffffffffffff;
1340 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
1341 if (!NT_SUCCESS(Status
)) {
1342 ERR("error - find_item returned %08x\n", Status
);
1346 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
1347 TRACE("could not find %llx,%x,%llx in extent_root\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
1351 if (tp
.item
->size
< sizeof(EXTENT_ITEM_SKINNY_METADATA
)) {
1352 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM_SKINNY_METADATA
));
1356 delete_tree_item(Vcb
, &tp
, rollback
);
1358 eism
= (EXTENT_ITEM_SKINNY_METADATA
*)tp
.item
->data
;
1359 if (t
&& t
->header
.level
== 0 && eism
->ei
.flags
& EXTENT_ITEM_SHARED_BACKREFS
&& eism
->type
== TYPE_TREE_BLOCK_REF
) {
1360 // convert shared data extents
1362 LIST_ENTRY
* le
= t
->itemlist
.Flink
;
1363 while (le
!= &t
->itemlist
) {
1364 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
1366 TRACE("%llx,%x,%llx\n", td
->key
.obj_id
, td
->key
.obj_type
, td
->key
.offset
);
1368 if (!td
->ignore
&& !td
->inserted
) {
1369 if (td
->key
.obj_type
== TYPE_EXTENT_DATA
) {
1370 EXTENT_DATA
* ed
= (EXTENT_DATA
*)td
->data
;
1372 if (ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) {
1373 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
1375 if (ed2
->address
!= 0) {
1376 TRACE("trying to convert shared data extent %llx,%llx\n", ed2
->address
, ed2
->size
);
1377 convert_shared_data_extent(Vcb
, ed2
->address
, ed2
->size
, rollback
);
1386 t
->header
.flags
&= ~HEADER_FLAG_SHARED_BACKREF
;
1389 c
= get_chunk_from_address(Vcb
, address
);
1392 decrease_chunk_usage(c
, Vcb
->superblock
.node_size
);
1394 add_to_space_list(c
, address
, Vcb
->superblock
.node_size
, SPACE_TYPE_DELETING
);
1396 ERR("could not find chunk for address %llx\n", address
);
1402 // static void check_tree_num_items(tree* t) {
1406 // le2 = t->itemlist.Flink;
1408 // while (le2 != &t->itemlist) {
1409 // tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1412 // le2 = le2->Flink;
1415 // if (t->header.num_items != ni) {
1416 // ERR("tree %p not okay: num_items was %x, expecting %x\n", t, ni, t->header.num_items);
1419 // ERR("tree %p okay\n", t);
1423 // static void check_trees_num_items(LIST_ENTRY* tc) {
1424 // LIST_ENTRY* le = tc->Flink;
1425 // while (le != tc) {
1426 // tree_cache* tc2 = CONTAINING_RECORD(le, tree_cache, list_entry);
1428 // check_tree_num_items(tc2->tree);
1434 static void convert_old_tree_extent(device_extension
* Vcb
, tree_data
* td
, tree
* t
, LIST_ENTRY
* rollback
) {
1436 traverse_ptr tp
, tp2
, insert_tp
;
1437 EXTENT_REF_V0
* erv0
;
1440 TRACE("(%p, %p, %p)\n", Vcb
, td
, t
);
1442 searchkey
.obj_id
= td
->treeholder
.address
;
1443 searchkey
.obj_type
= TYPE_EXTENT_REF_V0
;
1444 searchkey
.offset
= 0xffffffffffffffff;
1446 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
1447 if (!NT_SUCCESS(Status
)) {
1448 ERR("error - find_item returned %08x\n", Status
);
1452 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
1453 TRACE("could not find EXTENT_REF_V0 for %llx\n", searchkey
.obj_id
);
1457 searchkey
.obj_id
= td
->treeholder
.address
;
1458 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
1459 searchkey
.offset
= Vcb
->superblock
.node_size
;
1461 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp2
, &searchkey
, FALSE
);
1462 if (!NT_SUCCESS(Status
)) {
1463 ERR("error - find_item returned %08x\n", Status
);
1467 if (keycmp(&searchkey
, &tp2
.item
->key
)) {
1468 ERR("could not find %llx,%x,%llx\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
1472 if (tp
.item
->size
< sizeof(EXTENT_REF_V0
)) {
1473 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_REF_V0
));
1477 erv0
= (EXTENT_REF_V0
*)tp
.item
->data
;
1479 delete_tree_item(Vcb
, &tp
, rollback
);
1480 delete_tree_item(Vcb
, &tp2
, rollback
);
1482 if (Vcb
->superblock
.incompat_flags
& BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
) {
1483 EXTENT_ITEM_SKINNY_METADATA
* eism
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_ITEM_SKINNY_METADATA
), ALLOC_TAG
);
1486 ERR("out of memory\n");
1490 eism
->ei
.refcount
= 1;
1491 eism
->ei
.generation
= erv0
->gen
;
1492 eism
->ei
.flags
= EXTENT_ITEM_TREE_BLOCK
;
1493 eism
->type
= TYPE_TREE_BLOCK_REF
;
1494 eism
->tbr
.offset
= t
->header
.tree_id
;
1496 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, td
->treeholder
.address
, TYPE_METADATA_ITEM
, t
->header
.level
-1, eism
, sizeof(EXTENT_ITEM_SKINNY_METADATA
), &insert_tp
, rollback
)) {
1497 ERR("insert_tree_item failed\n");
1501 EXTENT_ITEM_TREE2
* eit2
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_ITEM_TREE2
), ALLOC_TAG
);
1504 ERR("out of memory\n");
1508 eit2
->eit
.extent_item
.refcount
= 1;
1509 eit2
->eit
.extent_item
.generation
= erv0
->gen
;
1510 eit2
->eit
.extent_item
.flags
= EXTENT_ITEM_TREE_BLOCK
;
1511 eit2
->eit
.firstitem
= td
->key
;
1512 eit2
->eit
.level
= t
->header
.level
- 1;
1513 eit2
->type
= TYPE_TREE_BLOCK_REF
;
1514 eit2
->tbr
.offset
= t
->header
.tree_id
;
1516 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, td
->treeholder
.address
, TYPE_EXTENT_ITEM
, Vcb
->superblock
.node_size
, eit2
, sizeof(EXTENT_ITEM_TREE2
), &insert_tp
, rollback
)) {
1517 ERR("insert_tree_item failed\n");
1522 add_parents_to_cache(Vcb
, insert_tp
.tree
);
1523 add_parents_to_cache(Vcb
, tp
.tree
);
1524 add_parents_to_cache(Vcb
, tp2
.tree
);
1527 static NTSTATUS
reduce_tree_extent(device_extension
* Vcb
, UINT64 address
, tree
* t
, LIST_ENTRY
* rollback
) {
1531 EXTENT_ITEM_V0
* eiv0
;
1535 // FIXME - deal with refcounts > 1
1537 TRACE("(%p, %llx, %p)\n", Vcb
, address
, t
);
1539 if (Vcb
->superblock
.incompat_flags
& BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
) {
1540 if (reduce_tree_extent_skinny(Vcb
, address
, t
, rollback
)) {
1541 return STATUS_SUCCESS
;
1545 searchkey
.obj_id
= address
;
1546 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
1547 searchkey
.offset
= Vcb
->superblock
.node_size
;
1549 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
1550 if (!NT_SUCCESS(Status
)) {
1551 ERR("error - find_item returned %08x\n", Status
);
1555 if (keycmp(&tp
.item
->key
, &searchkey
)) {
1556 ERR("could not find %llx,%x,%llx in extent_root\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
1558 return STATUS_INTERNAL_ERROR
;
1561 if (tp
.item
->size
== sizeof(EXTENT_ITEM_V0
)) {
1562 eiv0
= (EXTENT_ITEM_V0
*)tp
.item
->data
;
1564 if (eiv0
->refcount
> 1) {
1565 FIXME("FIXME - cannot deal with refcounts larger than 1 at present (eiv0->refcount == %llx)\n", eiv0
->refcount
);
1566 return STATUS_INTERNAL_ERROR
;
1569 if (tp
.item
->size
< sizeof(EXTENT_ITEM
)) {
1570 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM
));
1571 return STATUS_INTERNAL_ERROR
;
1574 ei
= (EXTENT_ITEM
*)tp
.item
->data
;
1576 if (ei
->refcount
> 1) {
1577 FIXME("FIXME - cannot deal with refcounts larger than 1 at present (ei->refcount == %llx)\n", ei
->refcount
);
1578 return STATUS_INTERNAL_ERROR
;
1581 if (t
&& t
->header
.level
== 0 && ei
->flags
& EXTENT_ITEM_SHARED_BACKREFS
) {
1582 // convert shared data extents
1584 LIST_ENTRY
* le
= t
->itemlist
.Flink
;
1585 while (le
!= &t
->itemlist
) {
1586 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
1588 TRACE("%llx,%x,%llx\n", td
->key
.obj_id
, td
->key
.obj_type
, td
->key
.offset
);
1590 if (!td
->ignore
&& !td
->inserted
) {
1591 if (td
->key
.obj_type
== TYPE_EXTENT_DATA
) {
1592 EXTENT_DATA
* ed
= (EXTENT_DATA
*)td
->data
;
1594 if (ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) {
1595 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
1597 if (ed2
->address
!= 0) {
1598 TRACE("trying to convert shared data extent %llx,%llx\n", ed2
->address
, ed2
->size
);
1599 convert_shared_data_extent(Vcb
, ed2
->address
, ed2
->size
, rollback
);
1608 t
->header
.flags
&= ~HEADER_FLAG_SHARED_BACKREF
;
1612 delete_tree_item(Vcb
, &tp
, rollback
);
1614 // if EXTENT_ITEM_V0, delete corresponding B4 item
1615 if (tp
.item
->size
== sizeof(EXTENT_ITEM_V0
)) {
1618 searchkey
.obj_id
= address
;
1619 searchkey
.obj_type
= TYPE_EXTENT_REF_V0
;
1620 searchkey
.offset
= 0xffffffffffffffff;
1622 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp2
, &searchkey
, FALSE
);
1623 if (!NT_SUCCESS(Status
)) {
1624 ERR("error - find_item returned %08x\n", Status
);
1628 if (tp2
.item
->key
.obj_id
== searchkey
.obj_id
&& tp2
.item
->key
.obj_type
== searchkey
.obj_type
) {
1629 delete_tree_item(Vcb
, &tp2
, rollback
);
1633 if (t
&& !(t
->header
.flags
& HEADER_FLAG_MIXED_BACKREF
)) {
1636 // when writing old internal trees, convert related extents
1638 le
= t
->itemlist
.Flink
;
1639 while (le
!= &t
->itemlist
) {
1640 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
1642 // ERR("%llx,%x,%llx\n", td->key.obj_id, td->key.obj_type, td->key.offset);
1644 if (!td
->ignore
&& !td
->inserted
) {
1645 if (t
->header
.level
> 0) {
1646 convert_old_tree_extent(Vcb
, td
, t
, rollback
);
1647 } else if (td
->key
.obj_type
== TYPE_EXTENT_DATA
&& td
->size
>= sizeof(EXTENT_DATA
)) {
1648 EXTENT_DATA
* ed
= (EXTENT_DATA
*)td
->data
;
1650 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && td
->size
>= sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
1651 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
1653 if (ed2
->address
!= 0) {
1654 TRACE("trying to convert old data extent %llx,%llx\n", ed2
->address
, ed2
->size
);
1655 convert_old_data_extent(Vcb
, ed2
->address
, ed2
->size
, rollback
);
1665 c
= get_chunk_from_address(Vcb
, address
);
1668 decrease_chunk_usage(c
, tp
.item
->key
.offset
);
1670 add_to_space_list(c
, address
, tp
.item
->key
.offset
, SPACE_TYPE_DELETING
);
1672 ERR("could not find chunk for address %llx\n", address
);
1674 return STATUS_SUCCESS
;
1677 static NTSTATUS
allocate_tree_extents(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
1681 TRACE("(%p)\n", Vcb
);
1683 le
= Vcb
->trees
.Flink
;
1684 while (le
!= &Vcb
->trees
) {
1685 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
1687 if (t
->write
&& !t
->has_new_address
) {
1690 Status
= get_tree_new_address(Vcb
, t
, rollback
);
1691 if (!NT_SUCCESS(Status
)) {
1692 ERR("get_tree_new_address returned %08x\n", Status
);
1696 TRACE("allocated extent %llx\n", t
->new_address
);
1698 if (t
->has_address
) {
1699 Status
= reduce_tree_extent(Vcb
, t
->header
.address
, t
, rollback
);
1701 if (!NT_SUCCESS(Status
)) {
1702 ERR("reduce_tree_extent returned %08x\n", Status
);
1707 c
= get_chunk_from_address(Vcb
, t
->new_address
);
1710 increase_chunk_usage(c
, Vcb
->superblock
.node_size
);
1712 ERR("could not find chunk for address %llx\n", t
->new_address
);
1713 return STATUS_INTERNAL_ERROR
;
1720 return STATUS_SUCCESS
;
1723 static NTSTATUS
update_root_root(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
1727 TRACE("(%p)\n", Vcb
);
1729 le
= Vcb
->trees
.Flink
;
1730 while (le
!= &Vcb
->trees
) {
1731 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
1733 if (t
->write
&& !t
->parent
) {
1734 if (t
->root
!= Vcb
->root_root
&& t
->root
!= Vcb
->chunk_root
) {
1738 searchkey
.obj_id
= t
->root
->id
;
1739 searchkey
.obj_type
= TYPE_ROOT_ITEM
;
1740 searchkey
.offset
= 0xffffffffffffffff;
1742 Status
= find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
);
1743 if (!NT_SUCCESS(Status
)) {
1744 ERR("error - find_item returned %08x\n", Status
);
1748 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
1749 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey
.obj_id
);
1750 return STATUS_INTERNAL_ERROR
;
1753 TRACE("updating the address for root %llx to %llx\n", searchkey
.obj_id
, t
->new_address
);
1755 t
->root
->root_item
.block_number
= t
->new_address
;
1756 t
->root
->root_item
.root_level
= t
->header
.level
;
1757 t
->root
->root_item
.generation
= Vcb
->superblock
.generation
;
1758 t
->root
->root_item
.generation2
= Vcb
->superblock
.generation
;
1760 if (tp
.item
->size
< sizeof(ROOT_ITEM
)) { // if not full length, delete and create new entry
1761 ROOT_ITEM
* ri
= ExAllocatePoolWithTag(PagedPool
, sizeof(ROOT_ITEM
), ALLOC_TAG
);
1764 ERR("out of memory\n");
1765 return STATUS_INSUFFICIENT_RESOURCES
;
1768 RtlCopyMemory(ri
, &t
->root
->root_item
, sizeof(ROOT_ITEM
));
1770 delete_tree_item(Vcb
, &tp
, rollback
);
1772 if (!insert_tree_item(Vcb
, Vcb
->root_root
, searchkey
.obj_id
, searchkey
.obj_type
, 0, ri
, sizeof(ROOT_ITEM
), NULL
, rollback
)) {
1773 ERR("insert_tree_item failed\n");
1774 return STATUS_INTERNAL_ERROR
;
1777 RtlCopyMemory(tp
.item
->data
, &t
->root
->root_item
, sizeof(ROOT_ITEM
));
1780 t
->root
->treeholder
.address
= t
->new_address
;
1786 Status
= update_chunk_caches(Vcb
, rollback
);
1787 if (!NT_SUCCESS(Status
)) {
1788 ERR("update_chunk_caches returned %08x\n", Status
);
1792 return STATUS_SUCCESS
;
1795 static NTSTATUS STDCALL
write_tree_completion(PDEVICE_OBJECT DeviceObject
, PIRP Irp
, PVOID conptr
) {
1796 write_tree_stripe
* stripe
= conptr
;
1797 write_tree_context
* context
= (write_tree_context
*)stripe
->context
;
1801 if (stripe
->status
== WriteTreeStatus_Cancelling
) {
1802 stripe
->status
= WriteTreeStatus_Cancelled
;
1806 stripe
->iosb
= Irp
->IoStatus
;
1808 if (NT_SUCCESS(Irp
->IoStatus
.Status
)) {
1809 stripe
->status
= WriteTreeStatus_Success
;
1811 le
= context
->stripes
.Flink
;
1813 stripe
->status
= WriteTreeStatus_Error
;
1815 while (le
!= &context
->stripes
) {
1816 write_tree_stripe
* s2
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
1818 if (s2
->status
== WriteTreeStatus_Pending
) {
1819 s2
->status
= WriteTreeStatus_Cancelling
;
1820 IoCancelIrp(s2
->Irp
);
1828 le
= context
->stripes
.Flink
;
1831 while (le
!= &context
->stripes
) {
1832 write_tree_stripe
* s2
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
1834 if (s2
->status
== WriteTreeStatus_Pending
|| s2
->status
== WriteTreeStatus_Cancelling
) {
1843 KeSetEvent(&context
->Event
, 0, FALSE
);
1845 return STATUS_MORE_PROCESSING_REQUIRED
;
1848 NTSTATUS
write_tree(device_extension
* Vcb
, UINT64 addr
, UINT8
* data
, write_tree_context
* wtc
) {
1850 CHUNK_ITEM_STRIPE
* cis
;
1851 write_tree_stripe
* stripe
;
1854 c
= get_chunk_from_address(Vcb
, addr
);
1857 ERR("get_chunk_from_address failed\n");
1858 return STATUS_INTERNAL_ERROR
;
1861 cis
= (CHUNK_ITEM_STRIPE
*)&c
->chunk_item
[1];
1863 // FIXME - make this work with RAID
1865 for (i
= 0; i
< c
->chunk_item
->num_stripes
; i
++) {
1866 PIO_STACK_LOCATION IrpSp
;
1868 // FIXME - handle missing devices
1870 stripe
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(write_tree_stripe
), ALLOC_TAG
);
1872 ERR("out of memory\n");
1873 return STATUS_INSUFFICIENT_RESOURCES
;
1876 stripe
->context
= (struct write_tree_context
*)wtc
;
1878 stripe
->device
= c
->devices
[i
];
1879 RtlZeroMemory(&stripe
->iosb
, sizeof(IO_STATUS_BLOCK
));
1880 stripe
->status
= WriteTreeStatus_Pending
;
1882 stripe
->Irp
= IoAllocateIrp(stripe
->device
->devobj
->StackSize
, FALSE
);
1885 ERR("IoAllocateIrp failed\n");
1886 return STATUS_INTERNAL_ERROR
;
1889 IrpSp
= IoGetNextIrpStackLocation(stripe
->Irp
);
1890 IrpSp
->MajorFunction
= IRP_MJ_WRITE
;
1892 if (stripe
->device
->devobj
->Flags
& DO_BUFFERED_IO
) {
1893 stripe
->Irp
->AssociatedIrp
.SystemBuffer
= data
;
1895 stripe
->Irp
->Flags
= IRP_BUFFERED_IO
;
1896 } else if (stripe
->device
->devobj
->Flags
& DO_DIRECT_IO
) {
1897 stripe
->Irp
->MdlAddress
= IoAllocateMdl(data
, Vcb
->superblock
.node_size
, FALSE
, FALSE
, NULL
);
1898 if (!stripe
->Irp
->MdlAddress
) {
1899 ERR("IoAllocateMdl failed\n");
1900 return STATUS_INTERNAL_ERROR
;
1903 MmProbeAndLockPages(stripe
->Irp
->MdlAddress
, KernelMode
, IoWriteAccess
);
1905 stripe
->Irp
->UserBuffer
= data
;
1908 IrpSp
->Parameters
.Write
.Length
= Vcb
->superblock
.node_size
;
1909 IrpSp
->Parameters
.Write
.ByteOffset
.QuadPart
= addr
- c
->offset
+ cis
[i
].offset
;
1911 stripe
->Irp
->UserIosb
= &stripe
->iosb
;
1913 IoSetCompletionRoutine(stripe
->Irp
, write_tree_completion
, stripe
, TRUE
, TRUE
, TRUE
);
1915 InsertTailList(&wtc
->stripes
, &stripe
->list_entry
);
1918 return STATUS_SUCCESS
;
1921 void free_write_tree_stripes(write_tree_context
* wtc
) {
1922 LIST_ENTRY
*le
, *le2
, *nextle
;
1924 le
= wtc
->stripes
.Flink
;
1925 while (le
!= &wtc
->stripes
) {
1926 write_tree_stripe
* stripe
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
1928 if (stripe
->device
->devobj
->Flags
& DO_DIRECT_IO
) {
1929 MmUnlockPages(stripe
->Irp
->MdlAddress
);
1930 IoFreeMdl(stripe
->Irp
->MdlAddress
);
1936 le
= wtc
->stripes
.Flink
;
1937 while (le
!= &wtc
->stripes
) {
1938 write_tree_stripe
* stripe
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
1943 ExFreePool(stripe
->buf
);
1946 while (le2
!= &wtc
->stripes
) {
1947 write_tree_stripe
* s2
= CONTAINING_RECORD(le2
, write_tree_stripe
, list_entry
);
1949 if (s2
->buf
== stripe
->buf
)
1963 static NTSTATUS
write_trees(device_extension
* Vcb
) {
1969 write_tree_context
* wtc
;
1971 TRACE("(%p)\n", Vcb
);
1973 for (level
= 0; level
<= 255; level
++) {
1974 BOOL nothing_found
= TRUE
;
1976 TRACE("level = %u\n", level
);
1978 le
= Vcb
->trees
.Flink
;
1979 while (le
!= &Vcb
->trees
) {
1980 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
1982 if (t
->write
&& t
->header
.level
== level
) {
1983 KEY firstitem
, searchkey
;
1986 EXTENT_ITEM_TREE
* eit
;
1988 if (!t
->has_new_address
) {
1989 ERR("error - tried to write tree with no new address\n");
1993 le2
= t
->itemlist
.Flink
;
1994 while (le2
!= &t
->itemlist
) {
1995 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
1997 firstitem
= td
->key
;
2004 t
->paritem
->key
= firstitem
;
2005 t
->paritem
->treeholder
.address
= t
->new_address
;
2006 t
->paritem
->treeholder
.generation
= Vcb
->superblock
.generation
;
2009 if (!(Vcb
->superblock
.incompat_flags
& BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
)) {
2010 searchkey
.obj_id
= t
->new_address
;
2011 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
2012 searchkey
.offset
= Vcb
->superblock
.node_size
;
2014 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
2015 if (!NT_SUCCESS(Status
)) {
2016 ERR("error - find_item returned %08x\n", Status
);
2020 if (keycmp(&searchkey
, &tp
.item
->key
)) {
2021 // traverse_ptr next_tp;
2023 // tree_data* paritem;
2025 ERR("could not find %llx,%x,%llx in extent_root (found %llx,%x,%llx instead)\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
, tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
);
2027 // searchkey.obj_id = 0;
2028 // searchkey.obj_type = 0;
2029 // searchkey.offset = 0;
2031 // find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
2035 // if (tp.tree->paritem != paritem) {
2036 // paritem = tp.tree->paritem;
2037 // ERR("paritem: %llx,%x,%llx\n", paritem->key.obj_id, paritem->key.obj_type, paritem->key.offset);
2040 // ERR("%llx,%x,%llx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
2042 // b = find_next_item(Vcb, &tp, &next_tp, NULL, FALSE);
2044 // free_traverse_ptr(&tp);
2049 // free_traverse_ptr(&tp);
2051 return STATUS_INTERNAL_ERROR
;
2054 if (tp
.item
->size
< sizeof(EXTENT_ITEM_TREE
)) {
2055 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM_TREE
));
2056 return STATUS_INTERNAL_ERROR
;
2059 eit
= (EXTENT_ITEM_TREE
*)tp
.item
->data
;
2060 eit
->firstitem
= firstitem
;
2063 nothing_found
= FALSE
;
2073 TRACE("allocated tree extents\n");
2075 wtc
= ExAllocatePoolWithTag(NonPagedPool
, sizeof(write_tree_context
), ALLOC_TAG
);
2077 ERR("out of memory\n");
2078 return STATUS_INSUFFICIENT_RESOURCES
;
2081 KeInitializeEvent(&wtc
->Event
, NotificationEvent
, FALSE
);
2082 InitializeListHead(&wtc
->stripes
);
2084 le
= Vcb
->trees
.Flink
;
2085 while (le
!= &Vcb
->trees
) {
2086 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
2087 #ifdef DEBUG_PARANOID
2088 UINT32 num_items
= 0, size
= 0;
2094 #ifdef DEBUG_PARANOID
2095 le2
= t
->itemlist
.Flink
;
2096 while (le2
!= &t
->itemlist
) {
2097 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
2101 if (t
->header
.level
== 0)
2107 if (t
->header
.level
== 0)
2108 size
+= num_items
* sizeof(leaf_node
);
2110 size
+= num_items
* sizeof(internal_node
);
2112 if (num_items
!= t
->header
.num_items
) {
2113 ERR("tree %llx, level %x: num_items was %x, expected %x\n", t
->root
->id
, t
->header
.level
, num_items
, t
->header
.num_items
);
2117 if (size
!= t
->size
) {
2118 ERR("tree %llx, level %x: size was %x, expected %x\n", t
->root
->id
, t
->header
.level
, size
, t
->size
);
2122 if (t
->header
.num_items
== 0 && t
->parent
) {
2123 ERR("tree %llx, level %x: tried to write empty tree with parent\n", t
->root
->id
, t
->header
.level
);
2127 if (t
->size
> Vcb
->superblock
.node_size
- sizeof(tree_header
)) {
2128 ERR("tree %llx, level %x: tried to write overlarge tree (%x > %x)\n", t
->root
->id
, t
->header
.level
, t
->size
, Vcb
->superblock
.node_size
- sizeof(tree_header
));
2133 ERR("tree %p\n", t
);
2134 le2
= t
->itemlist
.Flink
;
2135 while (le2
!= &t
->itemlist
) {
2136 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
2138 ERR("%llx,%x,%llx inserted=%u\n", td
->key
.obj_id
, td
->key
.obj_type
, td
->key
.offset
, td
->inserted
);
2145 t
->header
.address
= t
->new_address
;
2146 t
->header
.generation
= Vcb
->superblock
.generation
;
2147 t
->header
.flags
|= HEADER_FLAG_MIXED_BACKREF
;
2148 t
->has_address
= TRUE
;
2150 data
= ExAllocatePoolWithTag(NonPagedPool
, Vcb
->superblock
.node_size
, ALLOC_TAG
);
2152 ERR("out of memory\n");
2153 Status
= STATUS_INSUFFICIENT_RESOURCES
;
2157 body
= data
+ sizeof(tree_header
);
2159 RtlCopyMemory(data
, &t
->header
, sizeof(tree_header
));
2160 RtlZeroMemory(body
, Vcb
->superblock
.node_size
- sizeof(tree_header
));
2162 if (t
->header
.level
== 0) {
2163 leaf_node
* itemptr
= (leaf_node
*)body
;
2166 UINT8
* dataptr
= data
+ Vcb
->superblock
.node_size
;
2168 le2
= t
->itemlist
.Flink
;
2169 while (le2
!= &t
->itemlist
) {
2170 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
2172 dataptr
= dataptr
- td
->size
;
2174 itemptr
[i
].key
= td
->key
;
2175 itemptr
[i
].offset
= (UINT8
*)dataptr
- (UINT8
*)body
;
2176 itemptr
[i
].size
= td
->size
;
2180 RtlCopyMemory(dataptr
, td
->data
, td
->size
);
2186 internal_node
* itemptr
= (internal_node
*)body
;
2190 le2
= t
->itemlist
.Flink
;
2191 while (le2
!= &t
->itemlist
) {
2192 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
2194 itemptr
[i
].key
= td
->key
;
2195 itemptr
[i
].address
= td
->treeholder
.address
;
2196 itemptr
[i
].generation
= td
->treeholder
.generation
;
2204 crc32
= calc_crc32c(0xffffffff, (UINT8
*)&((tree_header
*)data
)->fs_uuid
, Vcb
->superblock
.node_size
- sizeof(((tree_header
*)data
)->csum
));
2206 *((UINT32
*)data
) = crc32
;
2207 TRACE("setting crc32 to %08x\n", crc32
);
2209 Status
= write_tree(Vcb
, t
->new_address
, data
, wtc
);
2210 if (!NT_SUCCESS(Status
)) {
2211 ERR("write_tree returned %08x\n", Status
);
2219 Status
= STATUS_SUCCESS
;
2221 if (wtc
->stripes
.Flink
!= &wtc
->stripes
) {
2222 // launch writes and wait
2223 le
= wtc
->stripes
.Flink
;
2224 while (le
!= &wtc
->stripes
) {
2225 write_tree_stripe
* stripe
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
2227 IoCallDriver(stripe
->device
->devobj
, stripe
->Irp
);
2232 KeWaitForSingleObject(&wtc
->Event
, Executive
, KernelMode
, FALSE
, NULL
);
2234 le
= wtc
->stripes
.Flink
;
2235 while (le
!= &wtc
->stripes
) {
2236 write_tree_stripe
* stripe
= CONTAINING_RECORD(le
, write_tree_stripe
, list_entry
);
2238 if (!NT_SUCCESS(stripe
->iosb
.Status
)) {
2239 Status
= stripe
->iosb
.Status
;
2246 free_write_tree_stripes(wtc
);
2255 static void update_backup_superblock(device_extension
* Vcb
, superblock_backup
* sb
) {
2259 RtlZeroMemory(sb
, sizeof(superblock_backup
));
2261 sb
->root_tree_addr
= Vcb
->superblock
.root_tree_addr
;
2262 sb
->root_tree_generation
= Vcb
->superblock
.generation
;
2263 sb
->root_level
= Vcb
->superblock
.root_level
;
2265 sb
->chunk_tree_addr
= Vcb
->superblock
.chunk_tree_addr
;
2266 sb
->chunk_tree_generation
= Vcb
->superblock
.chunk_root_generation
;
2267 sb
->chunk_root_level
= Vcb
->superblock
.chunk_root_level
;
2269 searchkey
.obj_id
= BTRFS_ROOT_EXTENT
;
2270 searchkey
.obj_type
= TYPE_ROOT_ITEM
;
2271 searchkey
.offset
= 0xffffffffffffffff;
2273 if (NT_SUCCESS(find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
))) {
2274 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
&& tp
.item
->size
>= sizeof(ROOT_ITEM
)) {
2275 ROOT_ITEM
* ri
= (ROOT_ITEM
*)tp
.item
->data
;
2277 sb
->extent_tree_addr
= ri
->block_number
;
2278 sb
->extent_tree_generation
= ri
->generation
;
2279 sb
->extent_root_level
= ri
->root_level
;
2283 searchkey
.obj_id
= BTRFS_ROOT_FSTREE
;
2285 if (NT_SUCCESS(find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
))) {
2286 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
&& tp
.item
->size
>= sizeof(ROOT_ITEM
)) {
2287 ROOT_ITEM
* ri
= (ROOT_ITEM
*)tp
.item
->data
;
2289 sb
->fs_tree_addr
= ri
->block_number
;
2290 sb
->fs_tree_generation
= ri
->generation
;
2291 sb
->fs_root_level
= ri
->root_level
;
2295 searchkey
.obj_id
= BTRFS_ROOT_DEVTREE
;
2297 if (NT_SUCCESS(find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
))) {
2298 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
&& tp
.item
->size
>= sizeof(ROOT_ITEM
)) {
2299 ROOT_ITEM
* ri
= (ROOT_ITEM
*)tp
.item
->data
;
2301 sb
->dev_root_addr
= ri
->block_number
;
2302 sb
->dev_root_generation
= ri
->generation
;
2303 sb
->dev_root_level
= ri
->root_level
;
2307 searchkey
.obj_id
= BTRFS_ROOT_CHECKSUM
;
2309 if (NT_SUCCESS(find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
))) {
2310 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
&& tp
.item
->size
>= sizeof(ROOT_ITEM
)) {
2311 ROOT_ITEM
* ri
= (ROOT_ITEM
*)tp
.item
->data
;
2313 sb
->csum_root_addr
= ri
->block_number
;
2314 sb
->csum_root_generation
= ri
->generation
;
2315 sb
->csum_root_level
= ri
->root_level
;
2319 sb
->total_bytes
= Vcb
->superblock
.total_bytes
;
2320 sb
->bytes_used
= Vcb
->superblock
.bytes_used
;
2321 sb
->num_devices
= Vcb
->superblock
.num_devices
;
2324 static NTSTATUS
write_superblocks(device_extension
* Vcb
) {
2329 TRACE("(%p)\n", Vcb
);
2331 le
= Vcb
->trees
.Flink
;
2332 while (le
!= &Vcb
->trees
) {
2333 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
2335 if (t
->write
&& !t
->parent
) {
2336 if (t
->root
== Vcb
->root_root
) {
2337 Vcb
->superblock
.root_tree_addr
= t
->new_address
;
2338 Vcb
->superblock
.root_level
= t
->header
.level
;
2339 } else if (t
->root
== Vcb
->chunk_root
) {
2340 Vcb
->superblock
.chunk_tree_addr
= t
->new_address
;
2341 Vcb
->superblock
.chunk_root_generation
= t
->header
.generation
;
2342 Vcb
->superblock
.chunk_root_level
= t
->header
.level
;
2349 for (i
= 0; i
< BTRFS_NUM_BACKUP_ROOTS
- 1; i
++) {
2350 RtlCopyMemory(&Vcb
->superblock
.backup
[i
], &Vcb
->superblock
.backup
[i
+1], sizeof(superblock_backup
));
2353 update_backup_superblock(Vcb
, &Vcb
->superblock
.backup
[BTRFS_NUM_BACKUP_ROOTS
- 1]);
2355 for (i
= 0; i
< Vcb
->superblock
.num_devices
; i
++) {
2356 if (Vcb
->devices
[i
].devobj
) {
2357 Status
= write_superblock(Vcb
, &Vcb
->devices
[i
]);
2358 if (!NT_SUCCESS(Status
)) {
2359 ERR("write_superblock returned %08x\n", Status
);
2365 return STATUS_SUCCESS
;
2368 static NTSTATUS
update_chunk_usage(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
2369 LIST_ENTRY
* le
= Vcb
->chunks
.Flink
;
2373 BLOCK_GROUP_ITEM
* bgi
;
2376 TRACE("(%p)\n", Vcb
);
2378 while (le
!= &Vcb
->chunks
) {
2379 c
= CONTAINING_RECORD(le
, chunk
, list_entry
);
2381 if (c
->used
!= c
->oldused
) {
2382 searchkey
.obj_id
= c
->offset
;
2383 searchkey
.obj_type
= TYPE_BLOCK_GROUP_ITEM
;
2384 searchkey
.offset
= c
->chunk_item
->size
;
2386 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
2387 if (!NT_SUCCESS(Status
)) {
2388 ERR("error - find_item returned %08x\n", Status
);
2392 if (keycmp(&searchkey
, &tp
.item
->key
)) {
2393 ERR("could not find (%llx,%x,%llx) in extent_root\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
2395 return STATUS_INTERNAL_ERROR
;
2398 if (tp
.item
->size
< sizeof(BLOCK_GROUP_ITEM
)) {
2399 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(BLOCK_GROUP_ITEM
));
2400 return STATUS_INTERNAL_ERROR
;
2403 bgi
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
2405 ERR("out of memory\n");
2406 return STATUS_INSUFFICIENT_RESOURCES
;
2409 RtlCopyMemory(bgi
, tp
.item
->data
, tp
.item
->size
);
2410 bgi
->used
= c
->used
;
2412 TRACE("adjusting usage of chunk %llx to %llx\n", c
->offset
, c
->used
);
2414 delete_tree_item(Vcb
, &tp
, rollback
);
2416 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
, bgi
, tp
.item
->size
, NULL
, rollback
)) {
2417 ERR("insert_tree_item failed\n");
2419 return STATUS_INTERNAL_ERROR
;
2422 TRACE("bytes_used = %llx\n", Vcb
->superblock
.bytes_used
);
2423 TRACE("chunk_item type = %llx\n", c
->chunk_item
->type
);
2425 if (c
->chunk_item
->type
& BLOCK_FLAG_RAID0
) {
2426 FIXME("RAID0 not yet supported\n");
2428 return STATUS_INTERNAL_ERROR
;
2429 } else if (c
->chunk_item
->type
& BLOCK_FLAG_RAID1
) {
2430 FIXME("RAID1 not yet supported\n");
2432 return STATUS_INTERNAL_ERROR
;
2433 } else if (c
->chunk_item
->type
& BLOCK_FLAG_DUPLICATE
) {
2434 Vcb
->superblock
.bytes_used
= Vcb
->superblock
.bytes_used
+ (2 * (c
->used
- c
->oldused
));
2435 } else if (c
->chunk_item
->type
& BLOCK_FLAG_RAID10
) {
2436 FIXME("RAID10 not yet supported\n");
2438 return STATUS_INTERNAL_ERROR
;
2439 } else if (c
->chunk_item
->type
& BLOCK_FLAG_RAID5
) {
2440 FIXME("RAID5 not yet supported\n");
2442 return STATUS_INTERNAL_ERROR
;
2443 } else if (c
->chunk_item
->type
& BLOCK_FLAG_RAID6
) {
2444 FIXME("RAID6 not yet supported\n");
2446 return STATUS_INTERNAL_ERROR
;
2448 Vcb
->superblock
.bytes_used
= Vcb
->superblock
.bytes_used
+ c
->used
- c
->oldused
;
2451 TRACE("bytes_used = %llx\n", Vcb
->superblock
.bytes_used
);
2453 c
->oldused
= c
->used
;
2459 return STATUS_SUCCESS
;
2462 static void get_first_item(tree
* t
, KEY
* key
) {
2465 le
= t
->itemlist
.Flink
;
2466 while (le
!= &t
->itemlist
) {
2467 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2474 static NTSTATUS STDCALL
split_tree_at(device_extension
* Vcb
, tree
* t
, tree_data
* newfirstitem
, UINT32 numitems
, UINT32 size
) {
2477 tree_data
* oldlastitem
;
2479 // // tree_data *firsttd, *lasttd;
2480 // // LIST_ENTRY* le;
2481 // #ifdef DEBUG_PARANOID
2482 // KEY lastkey1, lastkey2;
2483 // traverse_ptr tp, next_tp;
2484 // ULONG numitems1, numitems2;
2487 TRACE("splitting tree in %llx at (%llx,%x,%llx)\n", t
->root
->id
, newfirstitem
->key
.obj_id
, newfirstitem
->key
.obj_type
, newfirstitem
->key
.offset
);
2489 // #ifdef DEBUG_PARANOID
2490 // lastkey1.obj_id = 0xffffffffffffffff;
2491 // lastkey1.obj_type = 0xff;
2492 // lastkey1.offset = 0xffffffffffffffff;
2494 // if (!find_item(Vcb, t->root, &tp, &lastkey1, NULL, FALSE))
2495 // ERR("error - find_item failed\n");
2497 // lastkey1 = tp.item->key;
2499 // while (find_prev_item(Vcb, &tp, &next_tp, NULL, FALSE)) {
2500 // free_traverse_ptr(&tp);
2504 // free_traverse_ptr(&tp);
2508 nt
= ExAllocatePoolWithTag(PagedPool
, sizeof(tree
), ALLOC_TAG
);
2510 ERR("out of memory\n");
2511 return STATUS_INSUFFICIENT_RESOURCES
;
2514 RtlCopyMemory(&nt
->header
, &t
->header
, sizeof(tree_header
));
2515 nt
->header
.address
= 0;
2516 nt
->header
.generation
= Vcb
->superblock
.generation
;
2517 nt
->header
.num_items
= t
->header
.num_items
- numitems
;
2518 nt
->header
.flags
= HEADER_FLAG_MIXED_BACKREF
;
2520 nt
->has_address
= FALSE
;
2522 nt
->parent
= t
->parent
;
2524 // nt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
2525 nt
->new_address
= 0;
2526 nt
->has_new_address
= FALSE
;
2527 nt
->flags
= t
->flags
;
2528 InitializeListHead(&nt
->itemlist
);
2530 // ExInitializeResourceLite(&nt->nonpaged->load_tree_lock);
2532 oldlastitem
= CONTAINING_RECORD(newfirstitem
->list_entry
.Blink
, tree_data
, list_entry
);
2534 // // firsttd = CONTAINING_RECORD(wt->tree->itemlist.Flink, tree_data, list_entry);
2535 // // lasttd = CONTAINING_RECORD(wt->tree->itemlist.Blink, tree_data, list_entry);
2537 // // TRACE("old tree in %x was from (%x,%x,%x) to (%x,%x,%x)\n",
2538 // // (UINT32)wt->tree->root->id, (UINT32)firsttd->key.obj_id, firsttd->key.obj_type, (UINT32)firsttd->key.offset,
2539 // // (UINT32)lasttd->key.obj_id, lasttd->key.obj_type, (UINT32)lasttd->key.offset);
2541 // // le = wt->tree->itemlist.Flink;
2542 // // while (le != &wt->tree->itemlist) {
2543 // // td = CONTAINING_RECORD(le, tree_data, list_entry);
2544 // // TRACE("old tree item was (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2545 // // le = le->Flink;
2548 nt
->itemlist
.Flink
= &newfirstitem
->list_entry
;
2549 nt
->itemlist
.Blink
= t
->itemlist
.Blink
;
2550 nt
->itemlist
.Flink
->Blink
= &nt
->itemlist
;
2551 nt
->itemlist
.Blink
->Flink
= &nt
->itemlist
;
2553 t
->itemlist
.Blink
= &oldlastitem
->list_entry
;
2554 t
->itemlist
.Blink
->Flink
= &t
->itemlist
;
2556 // // le = wt->tree->itemlist.Flink;
2557 // // while (le != &wt->tree->itemlist) {
2558 // // td = CONTAINING_RECORD(le, tree_data, list_entry);
2559 // // TRACE("old tree item now (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2560 // // le = le->Flink;
2563 // // firsttd = CONTAINING_RECORD(wt->tree->itemlist.Flink, tree_data, list_entry);
2564 // // lasttd = CONTAINING_RECORD(wt->tree->itemlist.Blink, tree_data, list_entry);
2566 // // TRACE("old tree in %x is now from (%x,%x,%x) to (%x,%x,%x)\n",
2567 // // (UINT32)wt->tree->root->id, (UINT32)firsttd->key.obj_id, firsttd->key.obj_type, (UINT32)firsttd->key.offset,
2568 // // (UINT32)lasttd->key.obj_id, lasttd->key.obj_type, (UINT32)lasttd->key.offset);
2570 nt
->size
= t
->size
- size
;
2572 t
->header
.num_items
= numitems
;
2576 InterlockedIncrement(&Vcb
->open_trees
);
2577 InsertTailList(&Vcb
->trees
, &nt
->list_entry
);
2580 // // td = wt->tree->items;
2582 // // if (!td->ignore) {
2583 // // TRACE("old tree item: (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2585 // // td = td->next;
2588 // // oldlastitem->next = NULL;
2589 // // wt->tree->lastitem = oldlastitem;
2591 // // TRACE("last item is now (%x,%x,%x)\n", (UINT32)oldlastitem->key.obj_id, oldlastitem->key.obj_type, (UINT32)oldlastitem->key.offset);
2593 if (nt
->header
.level
> 0) {
2594 LIST_ENTRY
* le
= nt
->itemlist
.Flink
;
2596 while (le
!= &nt
->itemlist
) {
2597 tree_data
* td2
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2599 if (td2
->treeholder
.tree
)
2600 td2
->treeholder
.tree
->parent
= nt
;
2607 td
= ExAllocatePoolWithTag(PagedPool
, sizeof(tree_data
), ALLOC_TAG
);
2609 ERR("out of memory\n");
2610 return STATUS_INSUFFICIENT_RESOURCES
;
2613 td
->key
= newfirstitem
->key
;
2615 InsertHeadList(&t
->paritem
->list_entry
, &td
->list_entry
);
2618 td
->inserted
= TRUE
;
2619 td
->treeholder
.tree
= nt
;
2620 init_tree_holder(&td
->treeholder
);
2621 // td->treeholder.nonpaged->status = tree_holder_loaded;
2624 nt
->parent
->header
.num_items
++;
2625 nt
->parent
->size
+= sizeof(internal_node
);
2630 TRACE("adding new tree parent\n");
2632 if (nt
->header
.level
== 255) {
2633 ERR("cannot add parent to tree at level 255\n");
2634 return STATUS_INTERNAL_ERROR
;
2637 pt
= ExAllocatePoolWithTag(PagedPool
, sizeof(tree
), ALLOC_TAG
);
2639 ERR("out of memory\n");
2640 return STATUS_INSUFFICIENT_RESOURCES
;
2643 RtlCopyMemory(&pt
->header
, &nt
->header
, sizeof(tree_header
));
2644 pt
->header
.address
= 0;
2645 pt
->header
.num_items
= 2;
2646 pt
->header
.level
= nt
->header
.level
+ 1;
2647 pt
->header
.flags
= HEADER_FLAG_MIXED_BACKREF
;
2649 pt
->has_address
= FALSE
;
2654 pt
->new_address
= 0;
2655 pt
->has_new_address
= FALSE
;
2656 // pt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
2657 pt
->size
= pt
->header
.num_items
* sizeof(internal_node
);
2658 pt
->flags
= t
->flags
;
2659 InitializeListHead(&pt
->itemlist
);
2661 // ExInitializeResourceLite(&pt->nonpaged->load_tree_lock);
2663 InterlockedIncrement(&Vcb
->open_trees
);
2664 InsertTailList(&Vcb
->trees
, &pt
->list_entry
);
2666 td
= ExAllocatePoolWithTag(PagedPool
, sizeof(tree_data
), ALLOC_TAG
);
2668 ERR("out of memory\n");
2669 return STATUS_INSUFFICIENT_RESOURCES
;
2672 get_first_item(t
, &td
->key
);
2674 td
->inserted
= FALSE
;
2675 td
->treeholder
.address
= 0;
2676 td
->treeholder
.generation
= Vcb
->superblock
.generation
;
2677 td
->treeholder
.tree
= t
;
2678 init_tree_holder(&td
->treeholder
);
2679 // td->treeholder.nonpaged->status = tree_holder_loaded;
2680 InsertTailList(&pt
->itemlist
, &td
->list_entry
);
2683 td
= ExAllocatePoolWithTag(PagedPool
, sizeof(tree_data
), ALLOC_TAG
);
2685 ERR("out of memory\n");
2686 return STATUS_INSUFFICIENT_RESOURCES
;
2689 td
->key
= newfirstitem
->key
;
2691 td
->inserted
= FALSE
;
2692 td
->treeholder
.address
= 0;
2693 td
->treeholder
.generation
= Vcb
->superblock
.generation
;
2694 td
->treeholder
.tree
= nt
;
2695 init_tree_holder(&td
->treeholder
);
2696 // td->treeholder.nonpaged->status = tree_holder_loaded;
2697 InsertTailList(&pt
->itemlist
, &td
->list_entry
);
2703 t
->root
->treeholder
.tree
= pt
;
2709 t
->root
->root_item
.bytes_used
+= Vcb
->superblock
.node_size
;
2711 // #ifdef DEBUG_PARANOID
2712 // lastkey2.obj_id = 0xffffffffffffffff;
2713 // lastkey2.obj_type = 0xff;
2714 // lastkey2.offset = 0xffffffffffffffff;
2716 // if (!find_item(Vcb, wt->tree->root, &tp, &lastkey2, NULL, FALSE))
2717 // ERR("error - find_item failed\n");
2719 // lastkey2 = tp.item->key;
2722 // while (find_prev_item(Vcb, &tp, &next_tp, NULL, FALSE)) {
2723 // free_traverse_ptr(&tp);
2727 // free_traverse_ptr(&tp);
2730 // ERR("lastkey1 = %llx,%x,%llx\n", lastkey1.obj_id, lastkey1.obj_type, lastkey1.offset);
2731 // ERR("lastkey2 = %llx,%x,%llx\n", lastkey2.obj_id, lastkey2.obj_type, lastkey2.offset);
2732 // ERR("numitems1 = %u\n", numitems1);
2733 // ERR("numitems2 = %u\n", numitems2);
2736 return STATUS_SUCCESS
;
2739 static NTSTATUS STDCALL
split_tree(device_extension
* Vcb
, tree
* t
) {
2741 UINT32 size
, ds
, numitems
;
2746 // FIXME - naïve implementation: maximizes number of filled trees
2748 le
= t
->itemlist
.Flink
;
2749 while (le
!= &t
->itemlist
) {
2750 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2753 if (t
->header
.level
== 0)
2754 ds
= sizeof(leaf_node
) + td
->size
;
2756 ds
= sizeof(internal_node
);
2758 // FIXME - move back if previous item was deleted item with same key
2759 if (size
+ ds
> Vcb
->superblock
.node_size
- sizeof(tree_header
))
2760 return split_tree_at(Vcb
, t
, td
, numitems
, size
);
2769 return STATUS_SUCCESS
;
2772 static NTSTATUS
try_tree_amalgamate(device_extension
* Vcb
, tree
* t
, LIST_ENTRY
* rollback
) {
2774 tree_data
* nextparitem
= NULL
;
2776 tree
*next_tree
, *par
;
2779 TRACE("trying to amalgamate tree in root %llx, level %x (size %u)\n", t
->root
->id
, t
->header
.level
, t
->size
);
2781 // FIXME - doesn't capture everything, as it doesn't ascend
2782 // FIXME - write proper function and put it in treefuncs.c
2783 le
= t
->paritem
->list_entry
.Flink
;
2784 while (le
!= &t
->parent
->itemlist
) {
2785 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2796 return STATUS_SUCCESS
;
2798 // FIXME - loop, and capture more than one tree if we can
2800 TRACE("nextparitem: key = %llx,%x,%llx\n", nextparitem
->key
.obj_id
, nextparitem
->key
.obj_type
, nextparitem
->key
.offset
);
2801 // nextparitem = t->paritem;
2803 // ExAcquireResourceExclusiveLite(&t->parent->nonpaged->load_tree_lock, TRUE);
2805 Status
= do_load_tree(Vcb
, &nextparitem
->treeholder
, t
->root
, t
->parent
, nextparitem
, &loaded
);
2806 if (!NT_SUCCESS(Status
)) {
2807 ERR("do_load_tree returned %08x\n", Status
);
2811 // ExReleaseResourceLite(&t->parent->nonpaged->load_tree_lock);
2813 next_tree
= nextparitem
->treeholder
.tree
;
2815 if (t
->size
+ next_tree
->size
<= Vcb
->superblock
.node_size
- sizeof(tree_header
)) {
2816 // merge two trees into one
2818 t
->header
.num_items
+= next_tree
->header
.num_items
;
2819 t
->size
+= next_tree
->size
;
2821 if (next_tree
->header
.level
> 0) {
2822 le
= next_tree
->itemlist
.Flink
;
2824 while (le
!= &next_tree
->itemlist
) {
2825 tree_data
* td2
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2827 if (td2
->treeholder
.tree
)
2828 td2
->treeholder
.tree
->parent
= t
;
2834 t
->itemlist
.Blink
->Flink
= next_tree
->itemlist
.Flink
;
2835 t
->itemlist
.Blink
->Flink
->Blink
= t
->itemlist
.Blink
;
2836 t
->itemlist
.Blink
= next_tree
->itemlist
.Blink
;
2837 t
->itemlist
.Blink
->Flink
= &t
->itemlist
;
2840 // le = t->itemlist.Flink;
2841 // while (le != &t->itemlist) {
2842 // tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2843 // if (!td->ignore) {
2844 // ERR("key: %llx,%x,%llx\n", td->key.obj_id, td->key.obj_type, td->key.offset);
2849 next_tree
->itemlist
.Flink
= next_tree
->itemlist
.Blink
= &next_tree
->itemlist
;
2851 next_tree
->header
.num_items
= 0;
2852 next_tree
->size
= 0;
2854 if (next_tree
->has_new_address
) { // delete associated EXTENT_ITEM
2855 Status
= reduce_tree_extent(Vcb
, next_tree
->new_address
, next_tree
, rollback
);
2857 if (!NT_SUCCESS(Status
)) {
2858 ERR("reduce_tree_extent returned %08x\n", Status
);
2861 } else if (next_tree
->has_address
) {
2862 Status
= reduce_tree_extent(Vcb
, next_tree
->header
.address
, next_tree
, rollback
);
2864 if (!NT_SUCCESS(Status
)) {
2865 ERR("reduce_tree_extent returned %08x\n", Status
);
2870 if (!nextparitem
->ignore
) {
2871 nextparitem
->ignore
= TRUE
;
2872 next_tree
->parent
->header
.num_items
--;
2873 next_tree
->parent
->size
-= sizeof(internal_node
);
2876 par
= next_tree
->parent
;
2885 RemoveEntryList(&nextparitem
->list_entry
);
2886 ExFreePool(next_tree
->paritem
);
2887 next_tree
->paritem
= NULL
;
2889 next_tree
->root
->root_item
.bytes_used
-= Vcb
->superblock
.node_size
;
2891 free_tree(next_tree
);
2893 // rebalance by moving items from second tree into first
2894 ULONG avg_size
= (t
->size
+ next_tree
->size
) / 2;
2895 KEY firstitem
= {0, 0, 0};
2897 TRACE("attempting rebalance\n");
2899 le
= next_tree
->itemlist
.Flink
;
2900 while (le
!= &next_tree
->itemlist
&& t
->size
< avg_size
&& next_tree
->header
.num_items
> 1) {
2901 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2905 if (next_tree
->header
.level
== 0)
2906 size
= sizeof(leaf_node
) + td
->size
;
2908 size
= sizeof(internal_node
);
2912 if (t
->size
+ size
< Vcb
->superblock
.node_size
- sizeof(tree_header
)) {
2913 RemoveEntryList(&td
->list_entry
);
2914 InsertTailList(&t
->itemlist
, &td
->list_entry
);
2916 if (next_tree
->header
.level
> 0 && td
->treeholder
.tree
)
2917 td
->treeholder
.tree
->parent
= t
;
2920 next_tree
->size
-= size
;
2922 next_tree
->header
.num_items
--;
2923 t
->header
.num_items
++;
2928 le
= next_tree
->itemlist
.Flink
;
2931 le
= next_tree
->itemlist
.Flink
;
2932 while (le
!= &next_tree
->itemlist
) {
2933 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
2936 firstitem
= td
->key
;
2943 // ERR("firstitem = %llx,%x,%llx\n", firstitem.obj_id, firstitem.obj_type, firstitem.offset);
2945 // FIXME - once ascension is working, make this work with parent's parent, etc.
2946 if (next_tree
->paritem
)
2947 next_tree
->paritem
->key
= firstitem
;
2959 return STATUS_SUCCESS
;
2962 static NTSTATUS
update_extent_level(device_extension
* Vcb
, UINT64 address
, tree
* t
, UINT8 level
, LIST_ENTRY
* rollback
) {
2967 if (Vcb
->superblock
.incompat_flags
& BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA
) {
2968 searchkey
.obj_id
= address
;
2969 searchkey
.obj_type
= TYPE_METADATA_ITEM
;
2970 searchkey
.offset
= t
->header
.level
;
2972 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
2973 if (!NT_SUCCESS(Status
)) {
2974 ERR("error - find_item returned %08x\n", Status
);
2978 if (!keycmp(&tp
.item
->key
, &searchkey
)) {
2979 EXTENT_ITEM_SKINNY_METADATA
* eism
;
2981 if (tp
.item
->size
> 0) {
2982 eism
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
2985 ERR("out of memory\n");
2986 return STATUS_INSUFFICIENT_RESOURCES
;
2989 RtlCopyMemory(eism
, tp
.item
->data
, tp
.item
->size
);
2993 delete_tree_item(Vcb
, &tp
, rollback
);
2995 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, address
, TYPE_METADATA_ITEM
, level
, eism
, tp
.item
->size
, NULL
, rollback
)) {
2996 ERR("insert_tree_item failed\n");
2998 return STATUS_INTERNAL_ERROR
;
3001 return STATUS_SUCCESS
;
3005 searchkey
.obj_id
= address
;
3006 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
3007 searchkey
.offset
= 0xffffffffffffffff;
3009 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
3010 if (!NT_SUCCESS(Status
)) {
3011 ERR("error - find_item returned %08x\n", Status
);
3015 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
) {
3016 EXTENT_ITEM_TREE
* eit
;
3018 if (tp
.item
->size
< sizeof(EXTENT_ITEM_TREE
)) {
3019 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM_TREE
));
3020 return STATUS_INTERNAL_ERROR
;
3023 eit
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
3026 ERR("out of memory\n");
3027 return STATUS_INSUFFICIENT_RESOURCES
;
3030 RtlCopyMemory(eit
, tp
.item
->data
, tp
.item
->size
);
3032 delete_tree_item(Vcb
, &tp
, rollback
);
3036 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, eit
, tp
.item
->size
, NULL
, rollback
)) {
3037 ERR("insert_tree_item failed\n");
3039 return STATUS_INTERNAL_ERROR
;
3042 return STATUS_SUCCESS
;
3045 ERR("could not find EXTENT_ITEM for address %llx\n", address
);
3047 return STATUS_INTERNAL_ERROR
;
3050 static NTSTATUS STDCALL
do_splits(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
3051 // LIST_ENTRY *le, *le2;
3054 UINT8 level
, max_level
;
3056 BOOL empty
, done_deletions
= FALSE
;
3060 TRACE("(%p)\n", Vcb
);
3064 for (level
= 0; level
<= 255; level
++) {
3065 LIST_ENTRY
*le
, *nextle
;
3069 TRACE("doing level %u\n", level
);
3071 le
= Vcb
->trees
.Flink
;
3073 while (le
!= &Vcb
->trees
) {
3074 t
= CONTAINING_RECORD(le
, tree
, list_entry
);
3078 if (t
->write
&& t
->header
.level
== level
) {
3081 if (t
->header
.num_items
== 0) {
3084 KEY firstitem
= {0xcccccccccccccccc,0xcc,0xcccccccccccccccc};
3089 done_deletions
= TRUE
;
3091 le2
= t
->itemlist
.Flink
;
3092 while (le2
!= &t
->itemlist
) {
3093 tree_data
* td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
3094 firstitem
= td
->key
;
3098 TRACE("deleting tree in root %llx (first item was %llx,%x,%llx)\n",
3099 t
->root
->id
, firstitem
.obj_id
, firstitem
.obj_type
, firstitem
.offset
);
3101 t
->root
->root_item
.bytes_used
-= Vcb
->superblock
.node_size
;
3103 if (t
->has_new_address
) { // delete associated EXTENT_ITEM
3104 Status
= reduce_tree_extent(Vcb
, t
->new_address
, t
, rollback
);
3106 if (!NT_SUCCESS(Status
)) {
3107 ERR("reduce_tree_extent returned %08x\n", Status
);
3110 } else if (t
->has_address
) {
3111 Status
= reduce_tree_extent(Vcb
,t
->header
.address
, t
, rollback
);
3113 if (!NT_SUCCESS(Status
)) {
3114 ERR("reduce_tree_extent returned %08x\n", Status
);
3119 if (!t
->paritem
->ignore
) {
3120 t
->paritem
->ignore
= TRUE
;
3121 t
->parent
->header
.num_items
--;
3122 t
->parent
->size
-= sizeof(internal_node
);
3125 RemoveEntryList(&t
->paritem
->list_entry
);
3126 ExFreePool(t
->paritem
);
3130 } else if (t
->header
.level
!= 0) {
3131 if (t
->has_new_address
) {
3132 Status
= update_extent_level(Vcb
, t
->new_address
, t
, 0, rollback
);
3134 if (!NT_SUCCESS(Status
)) {
3135 ERR("update_extent_level returned %08x\n", Status
);
3140 t
->header
.level
= 0;
3142 } else if (t
->size
> Vcb
->superblock
.node_size
- sizeof(tree_header
)) {
3143 TRACE("splitting overlarge tree (%x > %x)\n", t
->size
, Vcb
->superblock
.node_size
- sizeof(tree_header
));
3144 Status
= split_tree(Vcb
, t
);
3146 if (!NT_SUCCESS(Status
)) {
3147 ERR("split_tree returned %08x\n", Status
);
3159 TRACE("nothing found for level %u\n", level
);
3164 min_size
= (Vcb
->superblock
.node_size
- sizeof(tree_header
)) / 2;
3166 for (level
= 0; level
<= max_level
; level
++) {
3169 le
= Vcb
->trees
.Flink
;
3171 while (le
!= &Vcb
->trees
) {
3172 t
= CONTAINING_RECORD(le
, tree
, list_entry
);
3174 if (t
->write
&& t
->header
.level
== level
&& t
->header
.num_items
> 0 && t
->parent
&& t
->size
< min_size
) {
3175 Status
= try_tree_amalgamate(Vcb
, t
, rollback
);
3176 if (!NT_SUCCESS(Status
)) {
3177 ERR("try_tree_amalgamate returned %08x\n", Status
);
3186 // simplify trees if top tree only has one entry
3188 if (done_deletions
) {
3189 for (level
= max_level
; level
> 0; level
--) {
3190 LIST_ENTRY
*le
, *nextle
;
3192 le
= Vcb
->trees
.Flink
;
3193 while (le
!= &Vcb
->trees
) {
3195 t
= CONTAINING_RECORD(le
, tree
, list_entry
);
3197 if (t
->write
&& t
->header
.level
== level
) {
3198 if (!t
->parent
&& t
->header
.num_items
== 1) {
3199 LIST_ENTRY
* le2
= t
->itemlist
.Flink
;
3201 tree
* child_tree
= NULL
;
3203 while (le2
!= &t
->itemlist
) {
3204 td
= CONTAINING_RECORD(le2
, tree_data
, list_entry
);
3210 TRACE("deleting top-level tree in root %llx with one item\n", t
->root
->id
);
3212 if (t
->has_new_address
) { // delete associated EXTENT_ITEM
3213 Status
= reduce_tree_extent(Vcb
, t
->new_address
, t
, rollback
);
3215 if (!NT_SUCCESS(Status
)) {
3216 ERR("reduce_tree_extent returned %08x\n", Status
);
3219 } else if (t
->has_address
) {
3220 Status
= reduce_tree_extent(Vcb
,t
->header
.address
, t
, rollback
);
3222 if (!NT_SUCCESS(Status
)) {
3223 ERR("reduce_tree_extent returned %08x\n", Status
);
3228 if (!td
->treeholder
.tree
) { // load first item if not already loaded
3229 KEY searchkey
= {0,0,0};
3232 Status
= find_item(Vcb
, t
->root
, &tp
, &searchkey
, FALSE
);
3233 if (!NT_SUCCESS(Status
)) {
3234 ERR("error - find_item returned %08x\n", Status
);
3239 child_tree
= td
->treeholder
.tree
;
3242 child_tree
->parent
= NULL
;
3243 child_tree
->paritem
= NULL
;
3246 t
->root
->root_item
.bytes_used
-= Vcb
->superblock
.node_size
;
3251 child_tree
->root
->treeholder
.tree
= child_tree
;
3260 return STATUS_SUCCESS
;
3263 static NTSTATUS
remove_root_extents(device_extension
* Vcb
, root
* r
, tree_holder
* th
, UINT8 level
, LIST_ENTRY
* rollback
) {
3268 Status
= load_tree(Vcb
, th
->address
, r
, &th
->tree
);
3270 if (!NT_SUCCESS(Status
)) {
3271 ERR("load_tree(%llx) returned %08x\n", th
->address
, Status
);
3276 if (th
->tree
->header
.level
> 0) {
3277 LIST_ENTRY
* le
= th
->tree
->itemlist
.Flink
;
3279 while (le
!= &th
->tree
->itemlist
) {
3280 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
3283 Status
= remove_root_extents(Vcb
, r
, &td
->treeholder
, th
->tree
->header
.level
- 1, rollback
);
3285 if (!NT_SUCCESS(Status
)) {
3286 ERR("remove_root_extents returned %08x\n", Status
);
3296 if (!th
->tree
|| th
->tree
->has_address
) {
3297 Status
= reduce_tree_extent(Vcb
, th
->address
, NULL
, rollback
);
3299 if (!NT_SUCCESS(Status
)) {
3300 ERR("reduce_tree_extent(%llx) returned %08x\n", th
->address
, Status
);
3305 return STATUS_SUCCESS
;
3308 static NTSTATUS
drop_root(device_extension
* Vcb
, root
* r
, LIST_ENTRY
* rollback
) {
3313 Status
= remove_root_extents(Vcb
, r
, &r
->treeholder
, r
->root_item
.root_level
, rollback
);
3314 if (!NT_SUCCESS(Status
)) {
3315 ERR("remove_root_extents returned %08x\n", Status
);
3319 // remove entry in uuid root (tree 9)
3320 if (Vcb
->uuid_root
) {
3321 RtlCopyMemory(&searchkey
.obj_id
, &r
->root_item
.uuid
.uuid
[0], sizeof(UINT64
));
3322 searchkey
.obj_type
= TYPE_SUBVOL_UUID
;
3323 RtlCopyMemory(&searchkey
.offset
, &r
->root_item
.uuid
.uuid
[sizeof(UINT64
)], sizeof(UINT64
));
3325 if (searchkey
.obj_id
!= 0 || searchkey
.offset
!= 0) {
3326 Status
= find_item(Vcb
, Vcb
->uuid_root
, &tp
, &searchkey
, FALSE
);
3327 if (!NT_SUCCESS(Status
)) {
3328 WARN("find_item returned %08x\n", Status
);
3330 if (!keycmp(&tp
.item
->key
, &searchkey
))
3331 delete_tree_item(Vcb
, &tp
, rollback
);
3333 WARN("could not find (%llx,%x,%llx) in uuid tree\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
3340 searchkey
.obj_id
= r
->id
;
3341 searchkey
.obj_type
= TYPE_ROOT_ITEM
;
3342 searchkey
.offset
= 0xffffffffffffffff;
3344 Status
= find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
);
3345 if (!NT_SUCCESS(Status
)) {
3346 ERR("find_item returned %08x\n", Status
);
3350 if (tp
.item
->key
.obj_id
== searchkey
.obj_id
&& tp
.item
->key
.obj_type
== searchkey
.obj_type
)
3351 delete_tree_item(Vcb
, &tp
, rollback
);
3353 WARN("could not find (%llx,%x,%llx) in root_root\n", searchkey
.obj_id
, searchkey
.obj_type
, searchkey
.offset
);
3355 // delete items in tree cache
3357 free_trees_root(Vcb
, r
);
3359 return STATUS_SUCCESS
;
3362 static NTSTATUS
drop_roots(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
3363 LIST_ENTRY
*le
= Vcb
->drop_roots
.Flink
, *le2
;
3366 while (le
!= &Vcb
->drop_roots
) {
3367 root
* r
= CONTAINING_RECORD(le
, root
, list_entry
);
3371 Status
= drop_root(Vcb
, r
, rollback
);
3372 if (!NT_SUCCESS(Status
)) {
3373 ERR("drop_root(%llx) returned %08x\n", r
->id
, Status
);
3380 return STATUS_SUCCESS
;
3383 NTSTATUS STDCALL
do_write(device_extension
* Vcb
, LIST_ENTRY
* rollback
) {
3388 TRACE("(%p)\n", Vcb
);
3390 if (!IsListEmpty(&Vcb
->drop_roots
)) {
3391 Status
= drop_roots(Vcb
, rollback
);
3393 if (!NT_SUCCESS(Status
)) {
3394 ERR("drop_roots returned %08x\n", Status
);
3399 // If only changing superblock, e.g. changing label, we still need to rewrite
3400 // the root tree so the generations match, otherwise you won't be able to mount on Linux.
3401 if (Vcb
->write_trees
== 0) {
3405 searchkey
.obj_id
= 0;
3406 searchkey
.obj_type
= 0;
3407 searchkey
.offset
= 0;
3409 Status
= find_item(Vcb
, Vcb
->root_root
, &tp
, &searchkey
, FALSE
);
3410 if (!NT_SUCCESS(Status
)) {
3411 ERR("error - find_item returned %08x\n", Status
);
3415 if (!Vcb
->root_root
->treeholder
.tree
->write
) {
3416 Vcb
->root_root
->treeholder
.tree
->write
= TRUE
;
3422 Status
= add_parents(Vcb
, rollback
);
3423 if (!NT_SUCCESS(Status
)) {
3424 ERR("add_parents returned %08x\n", Status
);
3428 Status
= do_splits(Vcb
, rollback
);
3429 if (!NT_SUCCESS(Status
)) {
3430 ERR("do_splits returned %08x\n", Status
);
3434 Status
= allocate_tree_extents(Vcb
, rollback
);
3435 if (!NT_SUCCESS(Status
)) {
3436 ERR("add_parents returned %08x\n", Status
);
3440 Status
= update_chunk_usage(Vcb
, rollback
);
3441 if (!NT_SUCCESS(Status
)) {
3442 ERR("update_chunk_usage returned %08x\n", Status
);
3446 Status
= allocate_cache(Vcb
, &cache_changed
, rollback
);
3447 if (!NT_SUCCESS(Status
)) {
3448 ERR("allocate_cache returned %08x\n", Status
);
3451 } while (cache_changed
|| !trees_consistent(Vcb
, rollback
));
3453 TRACE("trees consistent\n");
3455 Status
= update_root_root(Vcb
, rollback
);
3456 if (!NT_SUCCESS(Status
)) {
3457 ERR("update_root_root returned %08x\n", Status
);
3461 Status
= write_trees(Vcb
);
3462 if (!NT_SUCCESS(Status
)) {
3463 ERR("write_trees returned %08x\n", Status
);
3467 Vcb
->superblock
.cache_generation
= Vcb
->superblock
.generation
;
3469 Status
= write_superblocks(Vcb
);
3470 if (!NT_SUCCESS(Status
)) {
3471 ERR("write_superblocks returned %08x\n", Status
);
3475 clean_space_cache(Vcb
);
3477 Vcb
->superblock
.generation
++;
3479 Status
= STATUS_SUCCESS
;
3481 le
= Vcb
->trees
.Flink
;
3482 while (le
!= &Vcb
->trees
) {
3483 tree
* t
= CONTAINING_RECORD(le
, tree
, list_entry
);
3490 Vcb
->write_trees
= 0;
3492 while (!IsListEmpty(&Vcb
->drop_roots
)) {
3493 LIST_ENTRY
* le
= RemoveHeadList(&Vcb
->drop_roots
);
3494 root
* r
= CONTAINING_RECORD(le
, root
, list_entry
);
3496 ExDeleteResourceLite(&r
->nonpaged
->load_tree_lock
);
3497 ExFreePool(r
->nonpaged
);
3502 TRACE("do_write returning %08x\n", Status
);
3507 NTSTATUS
consider_write(device_extension
* Vcb
) {
3508 // FIXME - call do_write if Vcb->write_trees high
3510 LIST_ENTRY rollback
;
3511 NTSTATUS Status
= STATUS_SUCCESS
;
3513 InitializeListHead(&rollback
);
3515 if (Vcb
->write_trees
> 0)
3516 Status
= do_write(Vcb
, &rollback
);
3518 free_tree_cache(&Vcb
->tree_cache
);
3520 if (!NT_SUCCESS(Status
))
3521 do_rollback(Vcb
, &rollback
);
3523 clear_rollback(&rollback
);
3527 return STATUS_SUCCESS
;
3531 // NTSTATUS STDCALL add_extent_ref(device_extension* Vcb, UINT64 address, UINT64 size, root* subvol, UINT64 inode, UINT64 offset, LIST_ENTRY* rollback) {
3535 // UINT8 *siptr, *type;
3538 // EXTENT_DATA_REF* edr;
3541 // TRACE("(%p, %llx, %llx, %llx, %llx, %llx)\n", Vcb, address, size, subvol->id, inode, offset);
3543 // searchkey.obj_id = address;
3544 // searchkey.obj_type = TYPE_EXTENT_ITEM;
3545 // searchkey.offset = size;
3547 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3548 // if (!NT_SUCCESS(Status)) {
3549 // ERR("error - find_item returned %08x\n", Status);
3553 // if (keycmp(&tp.item->key, &searchkey)) {
3554 // // create new entry
3556 // len = sizeof(EXTENT_ITEM) + sizeof(UINT8) + sizeof(EXTENT_DATA_REF);
3558 // ei = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
3560 // ERR("out of memory\n");
3561 // return STATUS_INSUFFICIENT_RESOURCES;
3564 // ei->refcount = 1;
3565 // ei->generation = Vcb->superblock.generation;
3566 // ei->flags = EXTENT_ITEM_DATA;
3568 // type = (UINT8*)&ei[1];
3569 // *type = TYPE_EXTENT_DATA_REF;
3571 // edr = (EXTENT_DATA_REF*)&type[1];
3572 // edr->root = subvol->id;
3573 // edr->objid = inode;
3574 // edr->offset = offset;
3577 // if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ei, len, NULL, rollback)) {
3578 // ERR("error - failed to insert item\n");
3579 // return STATUS_INTERNAL_ERROR;
3582 // // FIXME - update free space in superblock and CHUNK_ITEM
3584 // return STATUS_SUCCESS;
3587 // if (tp.item->size == sizeof(EXTENT_ITEM_V0)) { // old extent ref, convert
3588 // NTSTATUS Status = convert_old_data_extent(Vcb, address, size, rollback);
3589 // if (!NT_SUCCESS(Status)) {
3590 // ERR("convert_old_data_extent returned %08x\n", Status);
3594 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3595 // if (!NT_SUCCESS(Status)) {
3596 // ERR("error - find_item returned %08x\n", Status);
3600 // if (keycmp(&tp.item->key, &searchkey)) {
3601 // WARN("extent item not found for address %llx, size %llx\n", address, size);
3602 // return STATUS_SUCCESS;
3606 // ei = (EXTENT_ITEM*)tp.item->data;
3608 // if (tp.item->size < sizeof(EXTENT_ITEM)) {
3609 // ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
3610 // return STATUS_INTERNAL_ERROR;
3613 // if (extent_item_is_shared(ei, tp.item->size - sizeof(EXTENT_ITEM))) {
3614 // NTSTATUS Status = convert_shared_data_extent(Vcb, address, size, rollback);
3615 // if (!NT_SUCCESS(Status)) {
3616 // ERR("convert_shared_data_extent returned %08x\n", Status);
3620 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3621 // if (!NT_SUCCESS(Status)) {
3622 // ERR("error - find_item returned %08x\n", Status);
3626 // if (keycmp(&tp.item->key, &searchkey)) {
3627 // WARN("extent item not found for address %llx, size %llx\n", address, size);
3628 // return STATUS_SUCCESS;
3631 // ei = (EXTENT_ITEM*)tp.item->data;
3634 // if (ei->flags != EXTENT_ITEM_DATA) {
3635 // ERR("error - flag was not EXTENT_ITEM_DATA\n");
3636 // return STATUS_INTERNAL_ERROR;
3639 // hash = get_extent_data_ref_hash(subvol->id, inode, offset);
3641 // len = tp.item->size - sizeof(EXTENT_ITEM);
3642 // siptr = (UINT8*)&ei[1];
3645 // if (*siptr == TYPE_EXTENT_DATA_REF) {
3648 // edr = (EXTENT_DATA_REF*)&siptr[1];
3650 // // already exists - increase refcount
3651 // if (edr->root == subvol->id && edr->objid == inode && edr->offset == offset) {
3652 // ei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
3655 // ERR("out of memory\n");
3656 // return STATUS_INSUFFICIENT_RESOURCES;
3659 // RtlCopyMemory(ei, tp.item->data, tp.item->size);
3661 // edr = (EXTENT_DATA_REF*)((UINT8*)ei + ((UINT8*)edr - tp.item->data));
3665 // delete_tree_item(Vcb, &tp, rollback);
3667 // if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ei, tp.item->size, NULL, rollback)) {
3668 // ERR("error - failed to insert item\n");
3670 // return STATUS_INTERNAL_ERROR;
3673 // return STATUS_SUCCESS;
3676 // sihash = get_extent_data_ref_hash(edr->root, edr->objid, edr->offset);
3678 // if (sihash >= hash)
3681 // siptr += sizeof(UINT8) + sizeof(EXTENT_DATA_REF);
3683 // if (len > sizeof(EXTENT_DATA_REF) + sizeof(UINT8)) {
3684 // len -= sizeof(EXTENT_DATA_REF) + sizeof(UINT8);
3687 // // FIXME - TYPE_TREE_BLOCK_REF 0xB0
3689 // ERR("unrecognized extent subitem %x\n", *siptr);
3690 // return STATUS_INTERNAL_ERROR;
3692 // } while (len > 0);
3694 // len = tp.item->size + sizeof(UINT8) + sizeof(EXTENT_DATA_REF); // FIXME - die if too big
3695 // ei = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
3697 // ERR("out of memory\n");
3698 // return STATUS_INSUFFICIENT_RESOURCES;
3701 // RtlCopyMemory(ei, tp.item->data, siptr - tp.item->data);
3704 // type = (UINT8*)ei + (siptr - tp.item->data);
3705 // *type = TYPE_EXTENT_DATA_REF;
3707 // edr = (EXTENT_DATA_REF*)&type[1];
3708 // edr->root = subvol->id;
3709 // edr->objid = inode;
3710 // edr->offset = offset;
3713 // if (siptr < tp.item->data + tp.item->size)
3714 // RtlCopyMemory(&edr[1], siptr, tp.item->data + tp.item->size - siptr);
3716 // delete_tree_item(Vcb, &tp, rollback);
3718 // if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ei, len, NULL, rollback)) {
3719 // ERR("error - failed to insert item\n");
3721 // return STATUS_INTERNAL_ERROR;
3724 // return STATUS_SUCCESS;
3727 static BOOL
extent_item_is_shared(EXTENT_ITEM
* ei
, ULONG len
) {
3728 UINT8
* siptr
= (UINT8
*)&ei
[1];
3731 if (*siptr
== TYPE_TREE_BLOCK_REF
) {
3732 siptr
+= sizeof(TREE_BLOCK_REF
) + 1;
3733 len
-= sizeof(TREE_BLOCK_REF
) + 1;
3734 } else if (*siptr
== TYPE_EXTENT_DATA_REF
) {
3735 siptr
+= sizeof(EXTENT_DATA_REF
) + 1;
3736 len
-= sizeof(EXTENT_DATA_REF
) + 1;
3737 } else if (*siptr
== TYPE_SHARED_BLOCK_REF
) {
3739 } else if (*siptr
== TYPE_SHARED_DATA_REF
) {
3742 ERR("unrecognized extent subitem %x\n", *siptr
);
3750 // static NTSTATUS STDCALL remove_extent_ref(device_extension* Vcb, UINT64 address, UINT64 size, root* subvol, UINT64 inode, UINT64 offset, LIST_ENTRY* changed_sector_list, LIST_ENTRY* rollback) {
3756 // EXTENT_DATA_REF* edr;
3760 // TRACE("(%p, %llx, %llx, %llx, %llx, %llx)\n", Vcb, address, size, subvol->id, inode, offset);
3762 // searchkey.obj_id = address;
3763 // searchkey.obj_type = TYPE_EXTENT_ITEM;
3764 // searchkey.offset = size;
3766 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3767 // if (!NT_SUCCESS(Status)) {
3768 // ERR("error - find_item returned %08x\n", Status);
3772 // if (keycmp(&tp.item->key, &searchkey)) {
3773 // WARN("extent item not found for address %llx, size %llx\n", address, size);
3774 // return STATUS_SUCCESS;
3777 // if (tp.item->size == sizeof(EXTENT_ITEM_V0)) { // old extent ref, convert
3778 // NTSTATUS Status = convert_old_data_extent(Vcb, address, size, rollback);
3779 // if (!NT_SUCCESS(Status)) {
3780 // ERR("convert_old_data_extent returned %08x\n", Status);
3784 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3785 // if (!NT_SUCCESS(Status)) {
3786 // ERR("error - find_item returned %08x\n", Status);
3790 // if (keycmp(&tp.item->key, &searchkey)) {
3791 // WARN("extent item not found for address %llx, size %llx\n", address, size);
3792 // return STATUS_SUCCESS;
3796 // ei = (EXTENT_ITEM*)tp.item->data;
3798 // if (tp.item->size < sizeof(EXTENT_ITEM)) {
3799 // ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, tp.item->size, sizeof(EXTENT_ITEM));
3800 // return STATUS_INTERNAL_ERROR;
3803 // if (!(ei->flags & EXTENT_ITEM_DATA)) {
3804 // ERR("error - EXTENT_ITEM_DATA flag not set\n");
3805 // return STATUS_INTERNAL_ERROR;
3808 // if (extent_item_is_shared(ei, tp.item->size - sizeof(EXTENT_ITEM))) {
3809 // NTSTATUS Status = convert_shared_data_extent(Vcb, address, size, rollback);
3810 // if (!NT_SUCCESS(Status)) {
3811 // ERR("convert_shared_data_extent returned %08x\n", Status);
3815 // Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
3816 // if (!NT_SUCCESS(Status)) {
3817 // ERR("error - find_item returned %08x\n", Status);
3821 // if (keycmp(&tp.item->key, &searchkey)) {
3822 // WARN("extent item not found for address %llx, size %llx\n", address, size);
3823 // return STATUS_SUCCESS;
3826 // ei = (EXTENT_ITEM*)tp.item->data;
3829 // len = tp.item->size - sizeof(EXTENT_ITEM);
3830 // siptr = (UINT8*)&ei[1];
3834 // if (*siptr == TYPE_EXTENT_DATA_REF) {
3835 // edr = (EXTENT_DATA_REF*)&siptr[1];
3837 // if (edr->root == subvol->id && edr->objid == inode && edr->offset == offset) {
3838 // if (edr->count > 1) {
3839 // ei = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
3842 // ERR("out of memory\n");
3843 // return STATUS_INSUFFICIENT_RESOURCES;
3846 // RtlCopyMemory(ei, tp.item->data, tp.item->size);
3848 // edr = (EXTENT_DATA_REF*)((UINT8*)ei + ((UINT8*)edr - tp.item->data));
3852 // delete_tree_item(Vcb, &tp, rollback);
3854 // if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ei, tp.item->size, NULL, rollback)) {
3855 // ERR("error - failed to insert item\n");
3857 // return STATUS_INTERNAL_ERROR;
3860 // return STATUS_SUCCESS;
3867 // siptr += sizeof(UINT8) + sizeof(EXTENT_DATA_REF);
3869 // if (len > sizeof(EXTENT_DATA_REF) + sizeof(UINT8)) {
3870 // len -= sizeof(EXTENT_DATA_REF) + sizeof(UINT8);
3873 // // // FIXME - TYPE_TREE_BLOCK_REF 0xB0
3875 // ERR("unrecognized extent subitem %x\n", *siptr);
3876 // return STATUS_INTERNAL_ERROR;
3878 // } while (len > 0);
3881 // WARN("could not find extent data ref\n");
3882 // return STATUS_SUCCESS;
3885 // // FIXME - decrease subitem refcount if there already?
3887 // len = tp.item->size - sizeof(UINT8) - sizeof(EXTENT_DATA_REF);
3889 // delete_tree_item(Vcb, &tp, rollback);
3891 // if (len == sizeof(EXTENT_ITEM)) { // extent no longer needed
3895 // if (changed_sector_list) {
3896 // changed_sector* sc = ExAllocatePoolWithTag(PagedPool, sizeof(changed_sector), ALLOC_TAG);
3898 // ERR("out of memory\n");
3899 // return STATUS_INSUFFICIENT_RESOURCES;
3902 // sc->ol.key = address;
3903 // sc->checksums = NULL;
3904 // sc->length = size / Vcb->superblock.sector_size;
3906 // sc->deleted = TRUE;
3908 // insert_into_ordered_list(changed_sector_list, &sc->ol);
3912 // le2 = Vcb->chunks.Flink;
3913 // while (le2 != &Vcb->chunks) {
3914 // c = CONTAINING_RECORD(le2, chunk, list_entry);
3916 // TRACE("chunk: %llx, %llx\n", c->offset, c->chunk_item->size);
3918 // if (address >= c->offset && address + size < c->offset + c->chunk_item->size)
3921 // le2 = le2->Flink;
3923 // if (le2 == &Vcb->chunks) c = NULL;
3926 // decrease_chunk_usage(c, size);
3928 // add_to_space_list(c, address, size, SPACE_TYPE_DELETING);
3931 // return STATUS_SUCCESS;
3934 // ei = ExAllocatePoolWithTag(PagedPool, len, ALLOC_TAG);
3936 // ERR("out of memory\n");
3937 // return STATUS_INSUFFICIENT_RESOURCES;
3940 // RtlCopyMemory(ei, tp.item->data, siptr - tp.item->data);
3942 // ei->generation = Vcb->superblock.generation;
3944 // if (tp.item->data + len != siptr)
3945 // RtlCopyMemory((UINT8*)ei + (siptr - tp.item->data), siptr + sizeof(UINT8) + sizeof(EXTENT_DATA_REF), tp.item->size - (siptr - tp.item->data) - sizeof(UINT8) - sizeof(EXTENT_DATA_REF));
3947 // if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ei, len, NULL, rollback)) {
3948 // ERR("error - failed to insert item\n");
3950 // return STATUS_INTERNAL_ERROR;
3953 // return STATUS_SUCCESS;
3956 static __inline BOOL
entry_in_ordered_list(LIST_ENTRY
* list
, UINT64 value
) {
3957 LIST_ENTRY
* le
= list
->Flink
;
3960 while (le
!= list
) {
3961 ol
= (ordered_list
*)le
;
3963 if (ol
->key
> value
)
3965 else if (ol
->key
== value
)
3974 static BOOL
is_file_prealloc_inode(device_extension
* Vcb
, root
* subvol
, UINT64 inode
, UINT64 start_data
, UINT64 end_data
) {
3977 traverse_ptr tp
, next_tp
;
3980 searchkey
.obj_id
= inode
;
3981 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
3982 searchkey
.offset
= start_data
;
3984 Status
= find_item(Vcb
, subvol
, &tp
, &searchkey
, FALSE
);
3985 if (!NT_SUCCESS(Status
)) {
3986 ERR("error - find_item returned %08x\n", Status
);
3990 if (tp
.item
->key
.obj_id
!= inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
)
3994 EXTENT_DATA
* ed
= (EXTENT_DATA
*)tp
.item
->data
;
3995 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
3998 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
3999 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
4003 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
4004 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
4008 b
= find_next_item(Vcb
, &tp
, &next_tp
, FALSE
);
4010 len
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
;
4012 if (tp
.item
->key
.offset
< end_data
&& tp
.item
->key
.offset
+ len
>= start_data
&& ed
->type
== EXTENT_TYPE_PREALLOC
)
4018 if (tp
.item
->key
.obj_id
> inode
|| tp
.item
->key
.obj_type
> TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
>= end_data
)
4026 NTSTATUS
excise_extents_inode(device_extension
* Vcb
, root
* subvol
, UINT64 inode
, INODE_ITEM
* ii
, UINT64 start_data
, UINT64 end_data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4028 traverse_ptr tp
, next_tp
;
4030 BOOL b
, deleted_prealloc
= FALSE
;
4032 searchkey
.obj_id
= inode
;
4033 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
4034 searchkey
.offset
= start_data
;
4036 Status
= find_item(Vcb
, subvol
, &tp
, &searchkey
, FALSE
);
4037 if (!NT_SUCCESS(Status
)) {
4038 ERR("error - find_item returned %08x\n", Status
);
4043 EXTENT_DATA
* ed
= (EXTENT_DATA
*)tp
.item
->data
;
4044 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
4047 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
4048 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
4049 Status
= STATUS_INTERNAL_ERROR
;
4053 b
= find_next_item(Vcb
, &tp
, &next_tp
, FALSE
);
4055 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
)
4058 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
4059 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
4060 Status
= STATUS_INTERNAL_ERROR
;
4064 len
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
;
4066 if (tp
.item
->key
.offset
< end_data
&& tp
.item
->key
.offset
+ len
>= start_data
) {
4067 if (ed
->compression
!= BTRFS_COMPRESSION_NONE
) {
4068 FIXME("FIXME - compression not supported at present\n");
4069 Status
= STATUS_NOT_SUPPORTED
;
4073 if (ed
->encryption
!= BTRFS_ENCRYPTION_NONE
) {
4074 WARN("root %llx, inode %llx, extent %llx: encryption not supported (type %x)\n", subvol
->id
, inode
, tp
.item
->key
.offset
, ed
->encryption
);
4075 Status
= STATUS_NOT_SUPPORTED
;
4079 if (ed
->encoding
!= BTRFS_ENCODING_NONE
) {
4080 WARN("other encodings not supported\n");
4081 Status
= STATUS_NOT_SUPPORTED
;
4085 if (ed
->type
== EXTENT_TYPE_INLINE
) {
4086 if (start_data
<= tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ len
) { // remove all
4087 delete_tree_item(Vcb
, &tp
, rollback
);
4090 ii
->st_blocks
-= len
;
4091 } else if (start_data
<= tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ len
) { // remove beginning
4095 delete_tree_item(Vcb
, &tp
, rollback
);
4097 size
= len
- (end_data
- tp
.item
->key
.offset
);
4099 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + size
, ALLOC_TAG
);
4101 ERR("out of memory\n");
4102 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4106 ned
->generation
= Vcb
->superblock
.generation
;
4107 ned
->decoded_size
= size
;
4108 ned
->compression
= ed
->compression
;
4109 ned
->encryption
= ed
->encryption
;
4110 ned
->encoding
= ed
->encoding
;
4111 ned
->type
= ed
->type
;
4113 RtlCopyMemory(&ned
->data
[0], &ed
->data
[end_data
- tp
.item
->key
.offset
], size
);
4115 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, end_data
, ned
, sizeof(EXTENT_DATA
) - 1 + size
, NULL
, rollback
)) {
4116 ERR("insert_tree_item failed\n");
4118 Status
= STATUS_INTERNAL_ERROR
;
4123 ii
->st_blocks
-= end_data
- tp
.item
->key
.offset
;
4124 } else if (start_data
> tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ len
) { // remove end
4128 delete_tree_item(Vcb
, &tp
, rollback
);
4130 size
= start_data
- tp
.item
->key
.offset
;
4132 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + size
, ALLOC_TAG
);
4134 ERR("out of memory\n");
4135 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4139 ned
->generation
= Vcb
->superblock
.generation
;
4140 ned
->decoded_size
= size
;
4141 ned
->compression
= ed
->compression
;
4142 ned
->encryption
= ed
->encryption
;
4143 ned
->encoding
= ed
->encoding
;
4144 ned
->type
= ed
->type
;
4146 RtlCopyMemory(&ned
->data
[0], &ed
->data
[0], size
);
4148 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, sizeof(EXTENT_DATA
) - 1 + size
, NULL
, rollback
)) {
4149 ERR("insert_tree_item failed\n");
4151 Status
= STATUS_INTERNAL_ERROR
;
4156 ii
->st_blocks
-= tp
.item
->key
.offset
+ len
- start_data
;
4157 } else if (start_data
> tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ len
) { // remove middle
4161 delete_tree_item(Vcb
, &tp
, rollback
);
4163 size
= start_data
- tp
.item
->key
.offset
;
4165 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + size
, ALLOC_TAG
);
4167 ERR("out of memory\n");
4168 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4172 ned
->generation
= Vcb
->superblock
.generation
;
4173 ned
->decoded_size
= size
;
4174 ned
->compression
= ed
->compression
;
4175 ned
->encryption
= ed
->encryption
;
4176 ned
->encoding
= ed
->encoding
;
4177 ned
->type
= ed
->type
;
4179 RtlCopyMemory(&ned
->data
[0], &ed
->data
[0], size
);
4181 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, sizeof(EXTENT_DATA
) - 1 + size
, NULL
, rollback
)) {
4182 ERR("insert_tree_item failed\n");
4184 Status
= STATUS_INTERNAL_ERROR
;
4188 size
= tp
.item
->key
.offset
+ len
- end_data
;
4190 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + size
, ALLOC_TAG
);
4192 ERR("out of memory\n");
4193 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4197 ned
->generation
= Vcb
->superblock
.generation
;
4198 ned
->decoded_size
= size
;
4199 ned
->compression
= ed
->compression
;
4200 ned
->encryption
= ed
->encryption
;
4201 ned
->encoding
= ed
->encoding
;
4202 ned
->type
= ed
->type
;
4204 RtlCopyMemory(&ned
->data
[0], &ed
->data
[end_data
- tp
.item
->key
.offset
], size
);
4206 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, end_data
, ned
, sizeof(EXTENT_DATA
) - 1 + size
, NULL
, rollback
)) {
4207 ERR("insert_tree_item failed\n");
4209 Status
= STATUS_INTERNAL_ERROR
;
4214 ii
->st_blocks
-= end_data
- start_data
;
4216 } else if (ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) {
4217 if (start_data
<= tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ len
) { // remove all
4218 if (ed2
->address
!= 0) {
4219 Status
= decrease_extent_refcount_data(Vcb
, ed2
->address
, ed2
->size
, subvol
, inode
, tp
.item
->key
.offset
- ed2
->offset
, 1, changed_sector_list
, rollback
);
4220 if (!NT_SUCCESS(Status
)) {
4221 ERR("decrease_extent_refcount_data returned %08x\n", Status
);
4226 ii
->st_blocks
-= len
;
4229 if (ed
->type
== EXTENT_TYPE_PREALLOC
)
4230 deleted_prealloc
= TRUE
;
4232 delete_tree_item(Vcb
, &tp
, rollback
);
4233 } else if (start_data
<= tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ len
) { // remove beginning
4237 if (ed2
->address
!= 0 && ii
)
4238 ii
->st_blocks
-= end_data
- tp
.item
->key
.offset
;
4240 delete_tree_item(Vcb
, &tp
, rollback
);
4242 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), ALLOC_TAG
);
4244 ERR("out of memory\n");
4245 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4249 ned2
= (EXTENT_DATA2
*)&ned
->data
[0];
4251 ned
->generation
= Vcb
->superblock
.generation
;
4252 ned
->decoded_size
= ed
->decoded_size
;
4253 ned
->compression
= ed
->compression
;
4254 ned
->encryption
= ed
->encryption
;
4255 ned
->encoding
= ed
->encoding
;
4256 ned
->type
= ed
->type
;
4257 ned2
->address
= ed2
->address
;
4258 ned2
->size
= ed2
->size
;
4259 ned2
->offset
= ed2
->address
== 0 ? 0 : (ed2
->offset
+ (end_data
- tp
.item
->key
.offset
));
4260 ned2
->num_bytes
= ed2
->num_bytes
- (end_data
- tp
.item
->key
.offset
);
4262 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, end_data
, ned
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), NULL
, rollback
)) {
4263 ERR("insert_tree_item failed\n");
4265 Status
= STATUS_INTERNAL_ERROR
;
4268 } else if (start_data
> tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ len
) { // remove end
4272 if (ed2
->address
!= 0 && ii
)
4273 ii
->st_blocks
-= tp
.item
->key
.offset
+ len
- start_data
;
4275 delete_tree_item(Vcb
, &tp
, rollback
);
4277 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), ALLOC_TAG
);
4279 ERR("out of memory\n");
4280 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4284 ned2
= (EXTENT_DATA2
*)&ned
->data
[0];
4286 ned
->generation
= Vcb
->superblock
.generation
;
4287 ned
->decoded_size
= ed
->decoded_size
;
4288 ned
->compression
= ed
->compression
;
4289 ned
->encryption
= ed
->encryption
;
4290 ned
->encoding
= ed
->encoding
;
4291 ned
->type
= ed
->type
;
4292 ned2
->address
= ed2
->address
;
4293 ned2
->size
= ed2
->size
;
4294 ned2
->offset
= ed2
->address
== 0 ? 0 : ed2
->offset
;
4295 ned2
->num_bytes
= start_data
- tp
.item
->key
.offset
;
4297 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), NULL
, rollback
)) {
4298 ERR("insert_tree_item failed\n");
4300 Status
= STATUS_INTERNAL_ERROR
;
4303 } else if (start_data
> tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ len
) { // remove middle
4307 if (ed2
->address
!= 0 && ii
)
4308 ii
->st_blocks
-= end_data
- start_data
;
4310 delete_tree_item(Vcb
, &tp
, rollback
);
4312 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), ALLOC_TAG
);
4314 ERR("out of memory\n");
4315 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4319 ned2
= (EXTENT_DATA2
*)&ned
->data
[0];
4321 ned
->generation
= Vcb
->superblock
.generation
;
4322 ned
->decoded_size
= ed
->decoded_size
;
4323 ned
->compression
= ed
->compression
;
4324 ned
->encryption
= ed
->encryption
;
4325 ned
->encoding
= ed
->encoding
;
4326 ned
->type
= ed
->type
;
4327 ned2
->address
= ed2
->address
;
4328 ned2
->size
= ed2
->size
;
4329 ned2
->offset
= ed2
->address
== 0 ? 0 : ed2
->offset
;
4330 ned2
->num_bytes
= start_data
- tp
.item
->key
.offset
;
4332 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), NULL
, rollback
)) {
4333 ERR("insert_tree_item failed\n");
4335 Status
= STATUS_INTERNAL_ERROR
;
4339 ned
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), ALLOC_TAG
);
4341 ERR("out of memory\n");
4342 Status
= STATUS_INSUFFICIENT_RESOURCES
;
4346 ned2
= (EXTENT_DATA2
*)&ned
->data
[0];
4348 ned
->generation
= Vcb
->superblock
.generation
;
4349 ned
->decoded_size
= ed
->decoded_size
;
4350 ned
->compression
= ed
->compression
;
4351 ned
->encryption
= ed
->encryption
;
4352 ned
->encoding
= ed
->encoding
;
4353 ned
->type
= ed
->type
;
4354 ned2
->address
= ed2
->address
;
4355 ned2
->size
= ed2
->size
;
4356 ned2
->offset
= ed2
->address
== 0 ? 0 : (ed2
->offset
+ (end_data
- tp
.item
->key
.offset
));
4357 ned2
->num_bytes
= tp
.item
->key
.offset
+ len
- end_data
;
4359 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, end_data
, ned
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), NULL
, rollback
)) {
4360 ERR("insert_tree_item failed\n");
4362 Status
= STATUS_INTERNAL_ERROR
;
4366 if (ed2
->address
!= 0) {
4367 Status
= increase_extent_refcount_data(Vcb
, ed2
->address
, ed2
->size
, subvol
, inode
, tp
.item
->key
.offset
- ed2
->offset
, 1, rollback
);
4369 if (!NT_SUCCESS(Status
)) {
4370 ERR("increase_extent_refcount_data returned %08x\n", Status
);
4382 if (tp
.item
->key
.obj_id
> inode
|| tp
.item
->key
.obj_type
> TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
>= end_data
)
4387 // FIXME - do bitmap analysis of changed extents, and free what we can
4389 if (ii
&& deleted_prealloc
&& !is_file_prealloc_inode(Vcb
, subvol
, inode
, 0, sector_align(ii
->st_size
, Vcb
->superblock
.sector_size
)))
4390 ii
->flags
&= ~BTRFS_INODE_PREALLOC
;
4397 NTSTATUS
excise_extents(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 end_data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4400 TRACE("(%p, (%llx, %llx), %llx, %llx, %p)\n", Vcb
, fcb
->subvol
->id
, fcb
->inode
, start_data
, end_data
, changed_sector_list
);
4402 Status
= excise_extents_inode(Vcb
, fcb
->subvol
, fcb
->inode
, &fcb
->inode_item
, start_data
, end_data
, changed_sector_list
, rollback
);
4403 if (!NT_SUCCESS(Status
)) {
4404 ERR("excise_extents_inode returned %08x\n");
4408 return STATUS_SUCCESS
;
4411 static NTSTATUS
do_write_data(device_extension
* Vcb
, UINT64 address
, void* data
, UINT64 length
, LIST_ENTRY
* changed_sector_list
) {
4416 Status
= write_data(Vcb
, address
, data
, length
);
4417 if (!NT_SUCCESS(Status
)) {
4418 ERR("write_data returned %08x\n", Status
);
4422 if (changed_sector_list
) {
4423 sc
= ExAllocatePoolWithTag(PagedPool
, sizeof(changed_sector
), ALLOC_TAG
);
4425 ERR("out of memory\n");
4426 return STATUS_INSUFFICIENT_RESOURCES
;
4429 sc
->ol
.key
= address
;
4430 sc
->length
= length
/ Vcb
->superblock
.sector_size
;
4431 sc
->deleted
= FALSE
;
4433 sc
->checksums
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * sc
->length
, ALLOC_TAG
);
4434 if (!sc
->checksums
) {
4435 ERR("out of memory\n");
4437 return STATUS_INSUFFICIENT_RESOURCES
;
4440 for (i
= 0; i
< sc
->length
; i
++) {
4441 sc
->checksums
[i
] = ~calc_crc32c(0xffffffff, (UINT8
*)data
+ (i
* Vcb
->superblock
.sector_size
), Vcb
->superblock
.sector_size
);
4444 insert_into_ordered_list(changed_sector_list
, &sc
->ol
);
4447 return STATUS_SUCCESS
;
4450 BOOL
insert_extent_chunk_inode(device_extension
* Vcb
, root
* subvol
, UINT64 inode
, INODE_ITEM
* inode_item
, chunk
* c
, UINT64 start_data
,
4451 UINT64 length
, BOOL prealloc
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4456 ULONG edsize
= sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
);
4458 TRACE("(%p, (%llx, %llx), %llx, %llx, %llx, %p, %p)\n", Vcb
, subvol
->id
, inode
, c
->offset
, start_data
, length
, data
, changed_sector_list
);
4460 if (!find_address_in_chunk(Vcb
, c
, length
, &address
))
4463 Status
= increase_extent_refcount_data(Vcb
, address
, length
, subvol
, inode
, start_data
, 1, rollback
);
4464 if (!NT_SUCCESS(Status
)) {
4465 ERR("increase_extent_refcount_data returned %08x\n", Status
);
4470 Status
= do_write_data(Vcb
, address
, data
, length
, changed_sector_list
);
4471 if (!NT_SUCCESS(Status
)) {
4472 ERR("do_write_data returned %08x\n", Status
);
4477 // add extent data to inode
4478 ed
= ExAllocatePoolWithTag(PagedPool
, edsize
, ALLOC_TAG
);
4480 ERR("out of memory\n");
4484 ed
->generation
= Vcb
->superblock
.generation
;
4485 ed
->decoded_size
= length
;
4486 ed
->compression
= BTRFS_COMPRESSION_NONE
;
4487 ed
->encryption
= BTRFS_ENCRYPTION_NONE
;
4488 ed
->encoding
= BTRFS_ENCODING_NONE
;
4489 ed
->type
= prealloc
? EXTENT_TYPE_PREALLOC
: EXTENT_TYPE_REGULAR
;
4491 ed2
= (EXTENT_DATA2
*)ed
->data
;
4492 ed2
->address
= address
;
4495 ed2
->num_bytes
= length
;
4497 if (!insert_tree_item(Vcb
, subvol
, inode
, TYPE_EXTENT_DATA
, start_data
, ed
, edsize
, NULL
, rollback
)) {
4498 ERR("insert_tree_item failed\n");
4503 increase_chunk_usage(c
, length
);
4504 add_to_space_list(c
, address
, length
, SPACE_TYPE_WRITING
);
4507 inode_item
->st_blocks
+= length
;
4510 inode_item
->flags
|= BTRFS_INODE_PREALLOC
;
4516 static BOOL
insert_extent_chunk(device_extension
* Vcb
, fcb
* fcb
, chunk
* c
, UINT64 start_data
, UINT64 length
, BOOL prealloc
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4517 return insert_extent_chunk_inode(Vcb
, fcb
->subvol
, fcb
->inode
, &fcb
->inode_item
, c
, start_data
, length
, prealloc
, data
, changed_sector_list
, rollback
);
4520 static BOOL
extend_data(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 length
, void* data
,
4521 LIST_ENTRY
* changed_sector_list
, traverse_ptr
* edtp
, traverse_ptr
* eitp
, LIST_ENTRY
* rollback
) {
4530 TRACE("(%p, (%llx, %llx), %llx, %llx, %p, %p, %p, %p)\n", Vcb
, fcb
->subvol
->id
, fcb
->inode
, start_data
,
4531 length
, data
, changed_sector_list
, edtp
, eitp
);
4533 ed
= ExAllocatePoolWithTag(PagedPool
, edtp
->item
->size
, ALLOC_TAG
);
4535 ERR("out of memory\n");
4539 RtlCopyMemory(ed
, edtp
->item
->data
, edtp
->item
->size
);
4541 ed
->decoded_size
+= length
;
4542 ed2
= (EXTENT_DATA2
*)ed
->data
;
4543 ed2
->size
+= length
;
4544 ed2
->num_bytes
+= length
;
4546 delete_tree_item(Vcb
, edtp
, rollback
);
4548 if (!insert_tree_item(Vcb
, fcb
->subvol
, edtp
->item
->key
.obj_id
, edtp
->item
->key
.obj_type
, edtp
->item
->key
.offset
, ed
, edtp
->item
->size
, NULL
, rollback
)) {
4549 TRACE("insert_tree_item failed\n");
4555 ei
= ExAllocatePoolWithTag(PagedPool
, eitp
->item
->size
, ALLOC_TAG
);
4557 ERR("out of memory\n");
4562 RtlCopyMemory(ei
, eitp
->item
->data
, eitp
->item
->size
);
4564 if (!insert_tree_item(Vcb
, Vcb
->extent_root
, eitp
->item
->key
.obj_id
, eitp
->item
->key
.obj_type
, eitp
->item
->key
.offset
+ length
, ei
, eitp
->item
->size
, NULL
, rollback
)) {
4565 ERR("insert_tree_item failed\n");
4571 delete_tree_item(Vcb
, eitp
, rollback
);
4573 Status
= write_data(Vcb
, eitp
->item
->key
.obj_id
+ eitp
->item
->key
.offset
, data
, length
);
4574 if (!NT_SUCCESS(Status
)) {
4575 ERR("write_data returned %08x\n", Status
);
4579 if (changed_sector_list
) {
4580 sc
= ExAllocatePoolWithTag(PagedPool
, sizeof(changed_sector
), ALLOC_TAG
);
4582 ERR("out of memory\n");
4586 sc
->ol
.key
= eitp
->item
->key
.obj_id
+ eitp
->item
->key
.offset
;
4587 sc
->length
= length
/ Vcb
->superblock
.sector_size
;
4588 sc
->deleted
= FALSE
;
4590 sc
->checksums
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * sc
->length
, ALLOC_TAG
);
4591 if (!sc
->checksums
) {
4592 ERR("out of memory\n");
4597 for (i
= 0; i
< sc
->length
; i
++) {
4598 sc
->checksums
[i
] = ~calc_crc32c(0xffffffff, (UINT8
*)data
+ (i
* Vcb
->superblock
.sector_size
), Vcb
->superblock
.sector_size
);
4600 insert_into_ordered_list(changed_sector_list
, &sc
->ol
);
4603 c
= get_chunk_from_address(Vcb
, eitp
->item
->key
.obj_id
);
4606 increase_chunk_usage(c
, length
);
4608 add_to_space_list(c
, eitp
->item
->key
.obj_id
+ eitp
->item
->key
.offset
, length
, SPACE_TYPE_WRITING
);
4611 fcb
->inode_item
.st_blocks
+= length
;
4616 static BOOL
try_extend_data(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 length
, void* data
,
4617 LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4619 traverse_ptr tp
, tp2
;
4620 BOOL success
= FALSE
;
4629 searchkey
.obj_id
= fcb
->inode
;
4630 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
4631 searchkey
.offset
= start_data
;
4633 Status
= find_item(Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
4634 if (!NT_SUCCESS(Status
)) {
4635 ERR("error - find_item returned %08x\n", Status
);
4639 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
>= start_data
) {
4640 WARN("previous EXTENT_DATA not found\n");
4644 ed
= (EXTENT_DATA
*)tp
.item
->data
;
4646 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
4647 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
4651 if (ed
->type
!= EXTENT_TYPE_REGULAR
) {
4652 TRACE("not extending extent which is not EXTENT_TYPE_REGULAR\n");
4656 ed2
= (EXTENT_DATA2
*)ed
->data
;
4658 if (tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
4659 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(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
4663 if (tp
.item
->key
.offset
+ ed2
->num_bytes
!= start_data
) {
4664 TRACE("last EXTENT_DATA does not run up to start_data (%llx + %llx != %llx)\n", tp
.item
->key
.offset
, ed2
->num_bytes
, start_data
);
4668 if (ed
->compression
!= BTRFS_COMPRESSION_NONE
) {
4669 FIXME("FIXME: compression not yet supported\n");
4673 if (ed
->encryption
!= BTRFS_ENCRYPTION_NONE
) {
4674 WARN("encryption not supported\n");
4678 if (ed
->encoding
!= BTRFS_ENCODING_NONE
) {
4679 WARN("other encodings not supported\n");
4683 if (ed2
->size
- ed2
->offset
!= ed2
->num_bytes
) {
4684 TRACE("last EXTENT_DATA does not run all the way to the end of the extent\n");
4688 searchkey
.obj_id
= ed2
->address
;
4689 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
4690 searchkey
.offset
= ed2
->size
;
4692 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp2
, &searchkey
, FALSE
);
4693 if (!NT_SUCCESS(Status
)) {
4694 ERR("error - find_item returned %08x\n", Status
);
4698 if (keycmp(&tp2
.item
->key
, &searchkey
)) {
4699 ERR("error - extent %llx,%llx not found in tree\n", ed2
->address
, ed2
->size
);
4704 if (tp2
.item
->size
== sizeof(EXTENT_ITEM_V0
)) { // old extent ref, convert
4705 NTSTATUS Status
= convert_old_data_extent(Vcb
, ed2
->address
, ed2
->size
, rollback
);
4706 if (!NT_SUCCESS(Status
)) {
4707 ERR("convert_old_data_extent returned %08x\n", Status
);
4711 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp2
, &searchkey
, FALSE
);
4712 if (!NT_SUCCESS(Status
)) {
4713 ERR("error - find_item returned %08x\n", Status
);
4717 if (keycmp(&tp2
.item
->key
, &searchkey
)) {
4718 WARN("extent item not found for address %llx, size %llx\n", ed2
->address
, ed2
->size
);
4723 ei
= (EXTENT_ITEM
*)tp2
.item
->data
;
4725 if (tp
.item
->size
< sizeof(EXTENT_ITEM
)) {
4726 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM
));
4730 // FIXME - test this
4731 if (extent_item_is_shared(ei
, tp2
.item
->size
- sizeof(EXTENT_ITEM
))) {
4732 NTSTATUS Status
= convert_shared_data_extent(Vcb
, ed2
->address
, ed2
->size
, rollback
);
4733 if (!NT_SUCCESS(Status
)) {
4734 ERR("convert_shared_data_extent returned %08x\n", Status
);
4738 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp2
, &searchkey
, FALSE
);
4739 if (!NT_SUCCESS(Status
)) {
4740 ERR("error - find_item returned %08x\n", Status
);
4744 if (keycmp(&tp2
.item
->key
, &searchkey
)) {
4745 WARN("extent item not found for address %llx, size %llx\n", ed2
->address
, ed2
->size
);
4749 ei
= (EXTENT_ITEM
*)tp2
.item
->data
;
4751 if (tp
.item
->size
< sizeof(EXTENT_ITEM
)) {
4752 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_ITEM
));
4757 if (ei
->refcount
!= 1) {
4758 TRACE("extent refcount was not 1\n");
4762 if (ei
->flags
!= EXTENT_ITEM_DATA
) {
4763 ERR("error - extent was not a data extent\n");
4767 c
= get_chunk_from_address(Vcb
, ed2
->address
);
4769 le
= c
->space
.Flink
;
4770 while (le
!= &c
->space
) {
4771 s
= CONTAINING_RECORD(le
, space
, list_entry
);
4773 if (s
->offset
== ed2
->address
+ ed2
->size
) {
4774 if (s
->type
== SPACE_TYPE_FREE
&& s
->size
>= length
) {
4775 success
= extend_data(Vcb
, fcb
, start_data
, length
, data
, changed_sector_list
, &tp
, &tp2
, rollback
);
4778 } else if (s
->offset
> ed2
->address
+ ed2
->size
)
4789 static NTSTATUS
insert_prealloc_extent(fcb
* fcb
, UINT64 start
, UINT64 length
, LIST_ENTRY
* rollback
) {
4790 LIST_ENTRY
* le
= fcb
->Vcb
->chunks
.Flink
;
4794 // FIXME - how do we know which RAID level to put this to?
4795 flags
= BLOCK_FLAG_DATA
; // SINGLE
4797 // FIXME - if length is more than max chunk size, loop through and
4798 // create the new chunks first
4800 while (le
!= &fcb
->Vcb
->chunks
) {
4801 c
= CONTAINING_RECORD(le
, chunk
, list_entry
);
4803 if (c
->chunk_item
->type
== flags
&& (c
->chunk_item
->size
- c
->used
) >= length
) {
4804 if (insert_extent_chunk(fcb
->Vcb
, fcb
, c
, start
, length
, TRUE
, NULL
, NULL
, rollback
))
4805 return STATUS_SUCCESS
;
4811 if ((c
= alloc_chunk(fcb
->Vcb
, flags
, rollback
))) {
4812 if (c
->chunk_item
->type
== flags
&& (c
->chunk_item
->size
- c
->used
) >= length
) {
4813 if (insert_extent_chunk(fcb
->Vcb
, fcb
, c
, start
, length
, TRUE
, NULL
, NULL
, rollback
))
4814 return STATUS_SUCCESS
;
4818 // FIXME - rebalance chunks if free space elsewhere?
4819 WARN("couldn't find any data chunks with %llx bytes free\n", length
);
4821 return STATUS_DISK_FULL
;
4824 NTSTATUS
insert_sparse_extent(device_extension
* Vcb
, root
* r
, UINT64 inode
, UINT64 start
, UINT64 length
, LIST_ENTRY
* rollback
) {
4828 TRACE("(%p, %llx, %llx, %llx, %llx)\n", Vcb
, r
->id
, inode
, start
, length
);
4830 ed
= ExAllocatePoolWithTag(PagedPool
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), ALLOC_TAG
);
4832 ERR("out of memory\n");
4833 return STATUS_INSUFFICIENT_RESOURCES
;
4836 ed
->generation
= Vcb
->superblock
.generation
;
4837 ed
->decoded_size
= length
;
4838 ed
->compression
= BTRFS_COMPRESSION_NONE
;
4839 ed
->encryption
= BTRFS_ENCRYPTION_NONE
;
4840 ed
->encoding
= BTRFS_ENCODING_NONE
;
4841 ed
->type
= EXTENT_TYPE_REGULAR
;
4843 ed2
= (EXTENT_DATA2
*)ed
->data
;
4847 ed2
->num_bytes
= length
;
4849 if (!insert_tree_item(Vcb
, r
, inode
, TYPE_EXTENT_DATA
, start
, ed
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
), NULL
, rollback
)) {
4850 ERR("insert_tree_item failed\n");
4852 return STATUS_INTERNAL_ERROR
;
4855 return STATUS_SUCCESS
;
4858 // static void print_tree(tree* t) {
4859 // LIST_ENTRY* le = t->itemlist.Flink;
4860 // while (le != &t->itemlist) {
4861 // tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
4862 // ERR("%llx,%x,%llx (ignore = %s)\n", td->key.obj_id, td->key.obj_type, td->key.offset, td->ignore ? "TRUE" : "FALSE");
4867 static NTSTATUS
insert_extent(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 length
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4868 LIST_ENTRY
* le
= Vcb
->chunks
.Flink
;
4873 TRACE("(%p, (%llx, %llx), %llx, %llx, %p, %p)\n", Vcb
, fcb
->subvol
->id
, fcb
->inode
, start_data
, length
, data
, changed_sector_list
);
4875 // FIXME - split data up if not enough space for just one extent
4877 if (start_data
> 0 && try_extend_data(Vcb
, fcb
, start_data
, length
, data
, changed_sector_list
, rollback
))
4878 return STATUS_SUCCESS
;
4880 // if there is a gap before start_data, plug it with a sparse extent
4881 if (start_data
> 0) {
4887 searchkey
.obj_id
= fcb
->inode
;
4888 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
4889 searchkey
.offset
= start_data
;
4891 Status
= find_item(Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
4892 if (!NT_SUCCESS(Status
)) {
4893 ERR("error - find_item returned %08x\n", Status
);
4897 // if (tp.item->key.obj_id != fcb->inode || tp.item->key.obj_type != TYPE_EXTENT_DATA || tp.item->key.offset >= start_data) {
4898 // traverse_ptr next_tp;
4900 // ERR("error - did not find EXTENT_DATA expected - looking for %llx,%x,%llx, found %llx,%x,%llx\n",
4901 // searchkey.obj_id, searchkey.obj_type, searchkey.offset, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
4902 // print_tree(tp.tree);
4904 // if (find_next_item(Vcb, &tp, &next_tp, FALSE)) {
4906 // ERR("key = %llx,%x,%llx\n", next_tp.tree->paritem->key.obj_id, next_tp.tree->paritem->key.obj_type, next_tp.tree->paritem->key.offset);
4907 // print_tree(next_tp.tree);
4909 // free_traverse_ptr(&next_tp);
4911 // ERR("next item not found\n");
4914 // free_traverse_ptr(&tp);
4915 // return STATUS_INTERNAL_ERROR;
4918 if (tp
.item
->key
.obj_type
== TYPE_EXTENT_DATA
&& tp
.item
->size
>= sizeof(EXTENT_DATA
)) {
4921 ed
= (EXTENT_DATA
*)tp
.item
->data
;
4922 ed2
= (EXTENT_DATA2
*)ed
->data
;
4924 len
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
;
4928 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
|| !ed
|| tp
.item
->key
.offset
+ len
< start_data
) {
4929 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
)
4930 Status
= insert_sparse_extent(Vcb
, fcb
->subvol
, fcb
->inode
, 0, start_data
, rollback
);
4932 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
4934 Status
= insert_sparse_extent(Vcb
, fcb
->subvol
, fcb
->inode
, tp
.item
->key
.offset
+ len
,
4935 start_data
- tp
.item
->key
.offset
- len
, rollback
);
4937 if (!NT_SUCCESS(Status
)) {
4938 ERR("insert_sparse_extent returned %08x\n", Status
);
4944 // FIXME - how do we know which RAID level to put this to?
4945 flags
= BLOCK_FLAG_DATA
; // SINGLE
4947 // if (!chunk_test) { // TESTING
4948 // if ((c = alloc_chunk(Vcb, flags, NULL))) {
4949 // ERR("chunk_item->type = %llx\n", c->chunk_item->type);
4950 // ERR("size = %llx\n", c->chunk_item->size);
4951 // ERR("used = %llx\n", c->used);
4953 // if (c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= length) {
4954 // if (insert_extent_chunk(Vcb, fcb, c, start_data, length, data, changed_sector_list)) {
4955 // // chunk_test = TRUE;
4956 // ERR("SUCCESS\n");
4957 // return STATUS_SUCCESS;
4965 while (le
!= &Vcb
->chunks
) {
4966 c
= CONTAINING_RECORD(le
, chunk
, list_entry
);
4968 if (c
->chunk_item
->type
== flags
&& (c
->chunk_item
->size
- c
->used
) >= length
) {
4969 if (insert_extent_chunk(Vcb
, fcb
, c
, start_data
, length
, FALSE
, data
, changed_sector_list
, rollback
))
4970 return STATUS_SUCCESS
;
4976 if ((c
= alloc_chunk(Vcb
, flags
, rollback
))) {
4977 if (c
->chunk_item
->type
== flags
&& (c
->chunk_item
->size
- c
->used
) >= length
) {
4978 if (insert_extent_chunk(Vcb
, fcb
, c
, start_data
, length
, FALSE
, data
, changed_sector_list
, rollback
))
4979 return STATUS_SUCCESS
;
4983 // FIXME - rebalance chunks if free space elsewhere?
4984 WARN("couldn't find any data chunks with %llx bytes free\n", length
);
4986 return STATUS_DISK_FULL
;
4989 void update_checksum_tree(device_extension
* Vcb
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
4990 LIST_ENTRY
* le
= changed_sector_list
->Flink
;
4992 traverse_ptr tp
, next_tp
;
4997 if (!Vcb
->checksum_root
) {
4998 ERR("no checksum root\n");
5002 while (le
!= changed_sector_list
) {
5003 UINT64 startaddr
, endaddr
;
5008 ULONG runlength
, index
;
5010 cs
= (changed_sector
*)le
;
5012 searchkey
.obj_id
= EXTENT_CSUM_ID
;
5013 searchkey
.obj_type
= TYPE_EXTENT_CSUM
;
5014 searchkey
.offset
= cs
->ol
.key
;
5016 // FIXME - create checksum_root if it doesn't exist at all
5018 Status
= find_item(Vcb
, Vcb
->checksum_root
, &tp
, &searchkey
, FALSE
);
5019 if (!NT_SUCCESS(Status
)) { // tree is completely empty
5020 // FIXME - do proper check here that tree is empty
5022 checksums
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * cs
->length
, ALLOC_TAG
);
5024 ERR("out of memory\n");
5028 RtlCopyMemory(checksums
, cs
->checksums
, sizeof(UINT32
) * cs
->length
);
5030 if (!insert_tree_item(Vcb
, Vcb
->checksum_root
, EXTENT_CSUM_ID
, TYPE_EXTENT_CSUM
, cs
->ol
.key
, checksums
, sizeof(UINT32
) * cs
->length
, NULL
, rollback
)) {
5031 ERR("insert_tree_item failed\n");
5032 ExFreePool(checksums
);
5039 // FIXME - check entry is TYPE_EXTENT_CSUM?
5041 if (tp
.item
->key
.offset
< cs
->ol
.key
&& tp
.item
->key
.offset
+ (tp
.item
->size
* Vcb
->superblock
.sector_size
/ sizeof(UINT32
)) >= cs
->ol
.key
)
5042 startaddr
= tp
.item
->key
.offset
;
5044 startaddr
= cs
->ol
.key
;
5046 searchkey
.obj_id
= EXTENT_CSUM_ID
;
5047 searchkey
.obj_type
= TYPE_EXTENT_CSUM
;
5048 searchkey
.offset
= cs
->ol
.key
+ (cs
->length
* Vcb
->superblock
.sector_size
);
5050 Status
= find_item(Vcb
, Vcb
->checksum_root
, &tp
, &searchkey
, FALSE
);
5051 if (!NT_SUCCESS(Status
)) {
5052 ERR("error - find_item returned %08x\n", Status
);
5056 tplen
= tp
.item
->size
/ sizeof(UINT32
);
5058 if (tp
.item
->key
.offset
+ (tplen
* Vcb
->superblock
.sector_size
) >= cs
->ol
.key
+ (cs
->length
* Vcb
->superblock
.sector_size
))
5059 endaddr
= tp
.item
->key
.offset
+ (tplen
* Vcb
->superblock
.sector_size
);
5061 endaddr
= cs
->ol
.key
+ (cs
->length
* Vcb
->superblock
.sector_size
);
5063 TRACE("cs starts at %llx (%x sectors)\n", cs
->ol
.key
, cs
->length
);
5064 TRACE("startaddr = %llx\n", startaddr
);
5065 TRACE("endaddr = %llx\n", endaddr
);
5067 len
= (endaddr
- startaddr
) / Vcb
->superblock
.sector_size
;
5069 checksums
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * len
, ALLOC_TAG
);
5071 ERR("out of memory\n");
5075 bmparr
= ExAllocatePoolWithTag(PagedPool
, sizeof(ULONG
) * ((len
/8)+1), ALLOC_TAG
);
5077 ERR("out of memory\n");
5078 ExFreePool(checksums
);
5082 RtlInitializeBitMap(&bmp
, bmparr
, len
);
5083 RtlSetAllBits(&bmp
);
5085 searchkey
.obj_id
= EXTENT_CSUM_ID
;
5086 searchkey
.obj_type
= TYPE_EXTENT_CSUM
;
5087 searchkey
.offset
= cs
->ol
.key
;
5089 Status
= find_item(Vcb
, Vcb
->checksum_root
, &tp
, &searchkey
, FALSE
);
5090 if (!NT_SUCCESS(Status
)) {
5091 ERR("error - find_item returned %08x\n", Status
);
5095 // set bit = free space, cleared bit = allocated sector
5097 // ERR("start loop\n");
5098 while (tp
.item
->key
.offset
< endaddr
) {
5099 // ERR("%llx,%x,%llx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
5100 if (tp
.item
->key
.offset
>= startaddr
) {
5101 if (tp
.item
->size
> 0) {
5102 RtlCopyMemory(&checksums
[(tp
.item
->key
.offset
- startaddr
) / Vcb
->superblock
.sector_size
], tp
.item
->data
, tp
.item
->size
);
5103 RtlClearBits(&bmp
, (tp
.item
->key
.offset
- startaddr
) / Vcb
->superblock
.sector_size
, tp
.item
->size
/ sizeof(UINT32
));
5106 delete_tree_item(Vcb
, &tp
, rollback
);
5109 if (find_next_item(Vcb
, &tp
, &next_tp
, FALSE
)) {
5114 // ERR("end loop\n");
5117 RtlSetBits(&bmp
, (cs
->ol
.key
- startaddr
) / Vcb
->superblock
.sector_size
, cs
->length
);
5119 RtlCopyMemory(&checksums
[(cs
->ol
.key
- startaddr
) / Vcb
->superblock
.sector_size
], cs
->checksums
, cs
->length
* sizeof(UINT32
));
5120 RtlClearBits(&bmp
, (cs
->ol
.key
- startaddr
) / Vcb
->superblock
.sector_size
, cs
->length
);
5123 runlength
= RtlFindFirstRunClear(&bmp
, &index
);
5125 while (runlength
!= 0) {
5129 if (runlength
* sizeof(UINT32
) > MAX_CSUM_SIZE
)
5130 rl
= MAX_CSUM_SIZE
/ sizeof(UINT32
);
5134 data
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * rl
, ALLOC_TAG
);
5136 ERR("out of memory\n");
5138 ExFreePool(checksums
);
5142 RtlCopyMemory(data
, &checksums
[index
], sizeof(UINT32
) * rl
);
5144 if (!insert_tree_item(Vcb
, Vcb
->checksum_root
, EXTENT_CSUM_ID
, TYPE_EXTENT_CSUM
, startaddr
+ (index
* Vcb
->superblock
.sector_size
), data
, sizeof(UINT32
) * rl
, NULL
, rollback
)) {
5145 ERR("insert_tree_item failed\n");
5148 ExFreePool(checksums
);
5154 } while (runlength
> 0);
5156 runlength
= RtlFindNextForwardRunClear(&bmp
, index
, &index
);
5160 ExFreePool(checksums
);
5167 while (!IsListEmpty(changed_sector_list
)) {
5168 le
= RemoveHeadList(changed_sector_list
);
5169 cs
= (changed_sector
*)le
;
5172 ExFreePool(cs
->checksums
);
5178 NTSTATUS
truncate_file(fcb
* fcb
, UINT64 end
, LIST_ENTRY
* rollback
) {
5179 LIST_ENTRY changed_sector_list
;
5181 BOOL nocsum
= fcb
->inode_item
.flags
& BTRFS_INODE_NODATASUM
;
5184 InitializeListHead(&changed_sector_list
);
5186 // FIXME - convert into inline extent if short enough
5188 Status
= excise_extents(fcb
->Vcb
, fcb
, sector_align(end
, fcb
->Vcb
->superblock
.sector_size
),
5189 sector_align(fcb
->inode_item
.st_size
, fcb
->Vcb
->superblock
.sector_size
), nocsum
? NULL
: &changed_sector_list
, rollback
);
5190 if (!NT_SUCCESS(Status
)) {
5191 ERR("error - excise_extents failed\n");
5195 fcb
->inode_item
.st_size
= end
;
5196 TRACE("setting st_size to %llx\n", end
);
5198 fcb
->Header
.AllocationSize
.QuadPart
= sector_align(fcb
->inode_item
.st_size
, fcb
->Vcb
->superblock
.sector_size
);
5199 fcb
->Header
.FileSize
.QuadPart
= fcb
->inode_item
.st_size
;
5200 fcb
->Header
.ValidDataLength
.QuadPart
= fcb
->inode_item
.st_size
;
5201 // FIXME - inform cache manager of this
5203 TRACE("fcb %p FileSize = %llx\n", fcb
, fcb
->Header
.FileSize
.QuadPart
);
5206 update_checksum_tree(fcb
->Vcb
, &changed_sector_list
, rollback
);
5208 return STATUS_SUCCESS
;
5211 NTSTATUS
extend_file(fcb
* fcb
, file_ref
* fileref
, UINT64 end
, BOOL prealloc
, LIST_ENTRY
* rollback
) {
5212 UINT64 oldalloc
, newalloc
;
5218 TRACE("(%p, %x, %p)\n", fcb
, end
, rollback
);
5221 return stream_set_end_of_file_information(fcb
->Vcb
, end
, fcb
, fileref
, NULL
, FALSE
, rollback
) ;
5223 searchkey
.obj_id
= fcb
->inode
;
5224 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
5225 searchkey
.offset
= 0xffffffffffffffff;
5227 Status
= find_item(fcb
->Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
5228 if (!NT_SUCCESS(Status
)) {
5229 ERR("error - find_item returned %08x\n", Status
);
5234 if (tp
.item
->key
.obj_id
== fcb
->inode
&& tp
.item
->key
.obj_type
== TYPE_EXTENT_DATA
) {
5235 EXTENT_DATA
* ed
= (EXTENT_DATA
*)tp
.item
->data
;
5236 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
5238 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
5239 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
5240 return STATUS_INTERNAL_ERROR
;
5243 oldalloc
= tp
.item
->key
.offset
+ (ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
);
5244 cur_inline
= ed
->type
== EXTENT_TYPE_INLINE
;
5246 if (cur_inline
&& end
> fcb
->Vcb
->max_inline
) {
5247 LIST_ENTRY changed_sector_list
;
5248 BOOL nocsum
= fcb
->inode_item
.flags
& BTRFS_INODE_NODATASUM
;
5249 UINT64 origlength
, length
;
5252 TRACE("giving inline file proper extents\n");
5254 origlength
= ed
->decoded_size
;
5259 InitializeListHead(&changed_sector_list
);
5261 delete_tree_item(fcb
->Vcb
, &tp
, rollback
);
5263 length
= sector_align(origlength
, fcb
->Vcb
->superblock
.sector_size
);
5265 data
= ExAllocatePoolWithTag(PagedPool
, length
, ALLOC_TAG
);
5267 ERR("could not allocate %llx bytes for data\n", length
);
5268 return STATUS_INSUFFICIENT_RESOURCES
;
5271 if (length
> origlength
)
5272 RtlZeroMemory(data
+ origlength
, length
- origlength
);
5274 RtlCopyMemory(data
, ed
->data
, origlength
);
5276 fcb
->inode_item
.st_blocks
-= origlength
;
5278 Status
= insert_extent(fcb
->Vcb
, fcb
, tp
.item
->key
.offset
, length
, data
, nocsum
? NULL
: &changed_sector_list
, rollback
);
5279 if (!NT_SUCCESS(Status
)) {
5280 ERR("insert_extent returned %08x\n", Status
);
5285 oldalloc
= tp
.item
->key
.offset
+ length
;
5290 update_checksum_tree(fcb
->Vcb
, &changed_sector_list
, rollback
);
5296 if (end
> oldalloc
) {
5297 edsize
= sizeof(EXTENT_DATA
) - 1 + end
- tp
.item
->key
.offset
;
5298 ed
= ExAllocatePoolWithTag(PagedPool
, edsize
, ALLOC_TAG
);
5301 ERR("out of memory\n");
5302 return STATUS_INSUFFICIENT_RESOURCES
;
5305 RtlZeroMemory(ed
, edsize
);
5306 RtlCopyMemory(ed
, tp
.item
->data
, tp
.item
->size
);
5308 ed
->decoded_size
= end
- tp
.item
->key
.offset
;
5310 delete_tree_item(fcb
->Vcb
, &tp
, rollback
);
5312 if (!insert_tree_item(fcb
->Vcb
, fcb
->subvol
, tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, ed
, edsize
, NULL
, rollback
)) {
5313 ERR("error - failed to insert item\n");
5315 return STATUS_INTERNAL_ERROR
;
5319 TRACE("extending inline file (oldalloc = %llx, end = %llx)\n", oldalloc
, end
);
5321 fcb
->inode_item
.st_size
= end
;
5322 TRACE("setting st_size to %llx\n", end
);
5324 fcb
->inode_item
.st_blocks
= end
;
5326 fcb
->Header
.AllocationSize
.QuadPart
= fcb
->Header
.FileSize
.QuadPart
= fcb
->Header
.ValidDataLength
.QuadPart
= end
;
5328 newalloc
= sector_align(end
, fcb
->Vcb
->superblock
.sector_size
);
5330 if (newalloc
> oldalloc
) {
5332 // FIXME - try and extend previous extent first
5334 Status
= insert_prealloc_extent(fcb
, oldalloc
, newalloc
- oldalloc
, rollback
);
5336 if (!NT_SUCCESS(Status
)) {
5337 ERR("insert_prealloc_extent returned %08x\n", Status
);
5341 Status
= insert_sparse_extent(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, oldalloc
, newalloc
- oldalloc
, rollback
);
5343 if (!NT_SUCCESS(Status
)) {
5344 ERR("insert_sparse_extent returned %08x\n", Status
);
5350 fcb
->inode_item
.st_size
= end
;
5351 TRACE("setting st_size to %llx\n", end
);
5353 TRACE("newalloc = %llx\n", newalloc
);
5355 fcb
->Header
.AllocationSize
.QuadPart
= newalloc
;
5356 fcb
->Header
.FileSize
.QuadPart
= fcb
->Header
.ValidDataLength
.QuadPart
= end
;
5359 if (end
> fcb
->Vcb
->max_inline
) {
5360 newalloc
= sector_align(end
, fcb
->Vcb
->superblock
.sector_size
);
5363 Status
= insert_prealloc_extent(fcb
, 0, newalloc
, rollback
);
5365 if (!NT_SUCCESS(Status
)) {
5366 ERR("insert_prealloc_extent returned %08x\n", Status
);
5370 Status
= insert_sparse_extent(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, 0, newalloc
, rollback
);
5372 if (!NT_SUCCESS(Status
)) {
5373 ERR("insert_sparse_extent returned %08x\n", Status
);
5378 fcb
->inode_item
.st_size
= end
;
5379 TRACE("setting st_size to %llx\n", end
);
5381 TRACE("newalloc = %llx\n", newalloc
);
5383 fcb
->Header
.AllocationSize
.QuadPart
= newalloc
;
5384 fcb
->Header
.FileSize
.QuadPart
= fcb
->Header
.ValidDataLength
.QuadPart
= end
;
5389 edsize
= sizeof(EXTENT_DATA
) - 1 + end
;
5390 ed
= ExAllocatePoolWithTag(PagedPool
, edsize
, ALLOC_TAG
);
5393 ERR("out of memory\n");
5394 return STATUS_INSUFFICIENT_RESOURCES
;
5397 ed
->generation
= fcb
->Vcb
->superblock
.generation
;
5398 ed
->decoded_size
= end
;
5399 ed
->compression
= BTRFS_COMPRESSION_NONE
;
5400 ed
->encryption
= BTRFS_ENCRYPTION_NONE
;
5401 ed
->encoding
= BTRFS_ENCODING_NONE
;
5402 ed
->type
= EXTENT_TYPE_INLINE
;
5404 RtlZeroMemory(ed
->data
, end
);
5406 if (!insert_tree_item(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, 0, ed
, edsize
, NULL
, rollback
)) {
5407 ERR("error - failed to insert item\n");
5409 return STATUS_INTERNAL_ERROR
;
5412 fcb
->inode_item
.st_size
= end
;
5413 TRACE("setting st_size to %llx\n", end
);
5415 fcb
->inode_item
.st_blocks
= end
;
5417 fcb
->Header
.AllocationSize
.QuadPart
= fcb
->Header
.FileSize
.QuadPart
= fcb
->Header
.ValidDataLength
.QuadPart
= end
;
5422 return STATUS_SUCCESS
;
5425 static UINT64
get_extent_item_refcount(device_extension
* Vcb
, UINT64 address
) {
5432 searchkey
.obj_id
= address
;
5433 searchkey
.obj_type
= TYPE_EXTENT_ITEM
;
5434 searchkey
.offset
= 0xffffffffffffffff;
5436 Status
= find_item(Vcb
, Vcb
->extent_root
, &tp
, &searchkey
, FALSE
);
5437 if (!NT_SUCCESS(Status
)) {
5438 ERR("error - find_item returned %08x\n", Status
);
5442 if (tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| tp
.item
->key
.obj_type
!= searchkey
.obj_type
) {
5443 ERR("error - could not find EXTENT_ITEM for %llx\n", address
);
5447 if (tp
.item
->size
< sizeof(EXTENT_ITEM
)) {
5448 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(EXTENT_ITEM
));
5452 ei
= (EXTENT_ITEM
*)tp
.item
->data
;
5458 static BOOL
is_file_prealloc(fcb
* fcb
, UINT64 start_data
, UINT64 end_data
) {
5459 return is_file_prealloc_inode(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, start_data
, end_data
);
5462 static NTSTATUS
do_cow_write(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 end_data
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
5465 Status
= excise_extents(fcb
->Vcb
, fcb
, start_data
, end_data
, changed_sector_list
, rollback
);
5466 if (!NT_SUCCESS(Status
)) {
5467 ERR("error - excise_extents returned %08x\n", Status
);
5471 Status
= insert_extent(fcb
->Vcb
, fcb
, start_data
, end_data
- start_data
, data
, changed_sector_list
, rollback
);
5473 if (!NT_SUCCESS(Status
)) {
5474 ERR("error - insert_extent returned %08x\n", Status
);
5478 Status
= STATUS_SUCCESS
;
5484 static NTSTATUS
merge_data_extents(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 end_data
, LIST_ENTRY
* rollback
) {
5486 traverse_ptr tp
, next_tp
;
5491 searchkey
.obj_id
= fcb
->inode
;
5492 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
5493 searchkey
.offset
= start_data
;
5495 Status
= find_item(Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
5496 if (!NT_SUCCESS(Status
)) {
5497 ERR("error - find_item returned %08x\n", Status
);
5501 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
) {
5502 ERR("error - EXTENT_DATA not found\n");
5503 return STATUS_INTERNAL_ERROR
;
5506 if (tp
.item
->key
.offset
> 0) {
5507 traverse_ptr tp2
, prev_tp
;
5511 b
= find_prev_item(Vcb
, &tp2
, &prev_tp
, FALSE
);
5514 if (!prev_tp
.item
->ignore
)
5522 if (prev_tp
.item
->key
.obj_id
== fcb
->inode
&& prev_tp
.item
->key
.obj_type
== TYPE_EXTENT_DATA
)
5527 ed
= (EXTENT_DATA
*)tp
.item
->data
;
5528 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
5529 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
5530 return STATUS_INTERNAL_ERROR
;
5534 b
= find_next_item(Vcb
, &tp
, &next_tp
, FALSE
);
5539 if (next_tp
.item
->key
.obj_id
!= fcb
->inode
|| next_tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
)
5540 return STATUS_SUCCESS
;
5542 if (next_tp
.item
->size
< sizeof(EXTENT_DATA
)) {
5543 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", next_tp
.item
->key
.obj_id
, next_tp
.item
->key
.obj_type
, next_tp
.item
->key
.offset
, next_tp
.item
->size
, sizeof(EXTENT_DATA
));
5544 return STATUS_INTERNAL_ERROR
;
5547 ned
= (EXTENT_DATA
*)next_tp
.item
->data
;
5548 if ((ned
->type
== EXTENT_TYPE_REGULAR
|| ned
->type
== EXTENT_TYPE_PREALLOC
) && next_tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
5549 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", next_tp
.item
->key
.obj_id
, next_tp
.item
->key
.obj_type
, next_tp
.item
->key
.offset
, next_tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
5550 return STATUS_INTERNAL_ERROR
;
5553 if (ed
->type
== ned
->type
&& (ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
)) {
5554 EXTENT_DATA2
*ed2
, *ned2
;
5556 ed2
= (EXTENT_DATA2
*)ed
->data
;
5557 ned2
= (EXTENT_DATA2
*)ned
->data
;
5559 if (next_tp
.item
->key
.offset
== tp
.item
->key
.offset
+ ed2
->num_bytes
&& ed2
->address
== ned2
->address
&& ed2
->size
== ned2
->size
&& ned2
->offset
== ed2
->offset
+ ed2
->num_bytes
) {
5560 EXTENT_DATA
* buf
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5565 ERR("out of memory\n");
5566 return STATUS_INSUFFICIENT_RESOURCES
;
5569 RtlCopyMemory(buf
, tp
.item
->data
, tp
.item
->size
);
5570 buf
->generation
= Vcb
->superblock
.generation
;
5572 buf2
= (EXTENT_DATA2
*)buf
->data
;
5573 buf2
->num_bytes
+= ned2
->num_bytes
;
5575 delete_tree_item(Vcb
, &tp
, rollback
);
5576 delete_tree_item(Vcb
, &next_tp
, rollback
);
5578 if (!insert_tree_item(Vcb
, fcb
->subvol
, tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, buf
, tp
.item
->size
, &tp2
, rollback
)) {
5579 ERR("insert_tree_item failed\n");
5581 return STATUS_INTERNAL_ERROR
;
5584 Status
= decrease_extent_refcount_data(Vcb
, ed2
->address
, ed2
->size
, fcb
->subvol
, fcb
->inode
, tp
.item
->key
.offset
- buf2
->offset
, 1, NULL
, rollback
);
5585 if (!NT_SUCCESS(Status
)) {
5586 ERR("decrease_extent_refcount_data returned %08x\n", Status
);
5601 return STATUS_SUCCESS
;
5604 static NTSTATUS
do_prealloc_write(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 end_data
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
5607 traverse_ptr tp
, next_tp
;
5608 BOOL b
, deleted_prealloc
= FALSE
;
5609 UINT64 last_written
= start_data
;
5611 searchkey
.obj_id
= fcb
->inode
;
5612 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
5613 searchkey
.offset
= start_data
;
5615 Status
= find_item(fcb
->Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
5616 if (!NT_SUCCESS(Status
)) {
5617 ERR("error - find_item returned %08x\n", Status
);
5621 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
)
5622 return do_cow_write(Vcb
, fcb
, start_data
, end_data
, data
, changed_sector_list
, rollback
);
5625 EXTENT_DATA
* ed
= (EXTENT_DATA
*)tp
.item
->data
;
5626 EXTENT_DATA2
* ed2
= (EXTENT_DATA2
*)ed
->data
;
5628 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
5629 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
5630 return STATUS_INTERNAL_ERROR
;
5633 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
5634 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
5635 return STATUS_INTERNAL_ERROR
;
5638 b
= find_next_item(fcb
->Vcb
, &tp
, &next_tp
, FALSE
);
5640 if (ed
->type
== EXTENT_TYPE_PREALLOC
) {
5641 if (tp
.item
->key
.offset
> last_written
) {
5642 Status
= do_cow_write(Vcb
, fcb
, last_written
, tp
.item
->key
.offset
, (UINT8
*)data
+ last_written
- start_data
, changed_sector_list
, rollback
);
5644 if (!NT_SUCCESS(Status
)) {
5645 ERR("do_cow_write returned %08x\n", Status
);
5650 last_written
= tp
.item
->key
.offset
;
5653 if (start_data
<= tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ ed2
->num_bytes
) { // replace all
5654 EXTENT_DATA
* ned
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5657 ERR("out of memory\n");
5659 return STATUS_INSUFFICIENT_RESOURCES
;
5662 RtlCopyMemory(ned
, tp
.item
->data
, tp
.item
->size
);
5664 ned
->type
= EXTENT_TYPE_REGULAR
;
5666 delete_tree_item(Vcb
, &tp
, rollback
);
5668 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, tp
.item
->size
, NULL
, rollback
)) {
5669 ERR("insert_tree_item failed\n");
5671 return STATUS_INTERNAL_ERROR
;
5674 Status
= do_write_data(Vcb
, ed2
->address
+ ed2
->offset
, (UINT8
*)data
+ tp
.item
->key
.offset
- start_data
, ed2
->num_bytes
, changed_sector_list
);
5675 if (!NT_SUCCESS(Status
)) {
5676 ERR("do_write_data returned %08x\n", Status
);
5681 deleted_prealloc
= TRUE
;
5683 last_written
= tp
.item
->key
.offset
+ ed2
->num_bytes
;
5684 } else if (start_data
<= tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ ed2
->num_bytes
) { // replace beginning
5685 EXTENT_DATA
*ned
, *nedb
;
5688 ned
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5691 ERR("out of memory\n");
5693 return STATUS_INSUFFICIENT_RESOURCES
;
5696 nedb
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5699 ERR("out of memory\n");
5702 return STATUS_INSUFFICIENT_RESOURCES
;
5705 delete_tree_item(Vcb
, &tp
, rollback
);
5707 RtlCopyMemory(ned
, tp
.item
->data
, tp
.item
->size
);
5709 ned
->type
= EXTENT_TYPE_REGULAR
;
5710 ned2
= (EXTENT_DATA2
*)ned
->data
;
5711 ned2
->num_bytes
= end_data
- tp
.item
->key
.offset
;
5713 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, tp
.item
->size
, NULL
, rollback
)) {
5714 ERR("insert_tree_item failed\n");
5718 return STATUS_INTERNAL_ERROR
;
5721 RtlCopyMemory(nedb
, tp
.item
->data
, tp
.item
->size
);
5722 ned2
= (EXTENT_DATA2
*)nedb
->data
;
5723 ned2
->offset
+= end_data
- tp
.item
->key
.offset
;
5724 ned2
->num_bytes
-= end_data
- tp
.item
->key
.offset
;
5726 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, end_data
, nedb
, tp
.item
->size
, NULL
, rollback
)) {
5727 ERR("insert_tree_item failed\n");
5730 return STATUS_INTERNAL_ERROR
;
5733 Status
= do_write_data(Vcb
, ed2
->address
+ ed2
->offset
, (UINT8
*)data
+ tp
.item
->key
.offset
- start_data
, end_data
- tp
.item
->key
.offset
, changed_sector_list
);
5734 if (!NT_SUCCESS(Status
)) {
5735 ERR("do_write_data returned %08x\n", Status
);
5740 Status
= increase_extent_refcount_data(Vcb
, ned2
->address
, ned2
->size
, fcb
->subvol
, fcb
->inode
, tp
.item
->key
.offset
- ed2
->offset
, 1, rollback
);
5741 if (!NT_SUCCESS(Status
)) {
5742 ERR("increase_extent_refcount_data returned %08x\n", Status
);
5746 last_written
= end_data
;
5747 } else if (start_data
> tp
.item
->key
.offset
&& end_data
>= tp
.item
->key
.offset
+ ed2
->num_bytes
) { // replace end
5748 EXTENT_DATA
*ned
, *nedb
;
5751 // FIXME - test this
5753 ned
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5756 ERR("out of memory\n");
5758 return STATUS_INSUFFICIENT_RESOURCES
;
5761 nedb
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5764 ERR("out of memory\n");
5767 return STATUS_INSUFFICIENT_RESOURCES
;
5770 delete_tree_item(Vcb
, &tp
, rollback
);
5772 RtlCopyMemory(ned
, tp
.item
->data
, tp
.item
->size
);
5774 ned2
= (EXTENT_DATA2
*)ned
->data
;
5775 ned2
->num_bytes
= start_data
- tp
.item
->key
.offset
;
5777 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, tp
.item
->size
, NULL
, rollback
)) {
5778 ERR("insert_tree_item failed\n");
5782 return STATUS_INTERNAL_ERROR
;
5785 RtlCopyMemory(nedb
, tp
.item
->data
, tp
.item
->size
);
5787 nedb
->type
= EXTENT_TYPE_REGULAR
;
5788 ned2
= (EXTENT_DATA2
*)nedb
->data
;
5789 ned2
->offset
+= start_data
- tp
.item
->key
.offset
;
5790 ned2
->num_bytes
= tp
.item
->key
.offset
+ ed2
->num_bytes
- start_data
;
5792 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, start_data
, nedb
, tp
.item
->size
, NULL
, rollback
)) {
5793 ERR("insert_tree_item failed\n");
5796 return STATUS_INTERNAL_ERROR
;
5799 Status
= do_write_data(Vcb
, ed2
->address
+ ned2
->offset
, data
, ned2
->num_bytes
, changed_sector_list
);
5800 if (!NT_SUCCESS(Status
)) {
5801 ERR("do_write_data returned %08x\n", Status
);
5806 Status
= increase_extent_refcount_data(Vcb
, ned2
->address
, ned2
->size
, fcb
->subvol
, fcb
->inode
, tp
.item
->key
.offset
- ed2
->offset
, 1, rollback
);
5807 if (!NT_SUCCESS(Status
)) {
5808 ERR("increase_extent_refcount_data returned %08x\n", Status
);
5813 last_written
= start_data
+ ned2
->num_bytes
;
5814 } else if (start_data
> tp
.item
->key
.offset
&& end_data
< tp
.item
->key
.offset
+ ed2
->num_bytes
) { // replace middle
5815 EXTENT_DATA
*ned
, *nedb
, *nedc
;
5818 // FIXME - test this
5820 ned
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5823 ERR("out of memory\n");
5825 return STATUS_INSUFFICIENT_RESOURCES
;
5828 nedb
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5831 ERR("out of memory\n");
5834 return STATUS_INSUFFICIENT_RESOURCES
;
5837 nedc
= ExAllocatePoolWithTag(PagedPool
, tp
.item
->size
, ALLOC_TAG
);
5840 ERR("out of memory\n");
5844 return STATUS_INSUFFICIENT_RESOURCES
;
5847 delete_tree_item(Vcb
, &tp
, rollback
);
5849 RtlCopyMemory(ned
, tp
.item
->data
, tp
.item
->size
);
5850 RtlCopyMemory(nedb
, tp
.item
->data
, tp
.item
->size
);
5851 RtlCopyMemory(nedc
, tp
.item
->data
, tp
.item
->size
);
5853 ned2
= (EXTENT_DATA2
*)ned
->data
;
5854 ned2
->num_bytes
= start_data
- tp
.item
->key
.offset
;
5856 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, tp
.item
->key
.offset
, ned
, tp
.item
->size
, NULL
, rollback
)) {
5857 ERR("insert_tree_item failed\n");
5862 return STATUS_INTERNAL_ERROR
;
5865 nedb
->type
= EXTENT_TYPE_REGULAR
;
5866 ned2
= (EXTENT_DATA2
*)nedb
->data
;
5867 ned2
->offset
+= start_data
- tp
.item
->key
.offset
;
5868 ned2
->num_bytes
= end_data
- start_data
;
5870 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, start_data
, nedb
, tp
.item
->size
, NULL
, rollback
)) {
5871 ERR("insert_tree_item failed\n");
5875 return STATUS_INTERNAL_ERROR
;
5878 ned2
= (EXTENT_DATA2
*)nedc
->data
;
5879 ned2
->offset
+= end_data
- tp
.item
->key
.offset
;
5880 ned2
->num_bytes
-= end_data
- tp
.item
->key
.offset
;
5882 if (!insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, end_data
, nedc
, tp
.item
->size
, NULL
, rollback
)) {
5883 ERR("insert_tree_item failed\n");
5886 return STATUS_INTERNAL_ERROR
;
5889 ned2
= (EXTENT_DATA2
*)nedb
->data
;
5890 Status
= do_write_data(Vcb
, ed2
->address
+ ned2
->offset
, data
, end_data
- start_data
, changed_sector_list
);
5891 if (!NT_SUCCESS(Status
)) {
5892 ERR("do_write_data returned %08x\n", Status
);
5897 Status
= increase_extent_refcount_data(Vcb
, ed2
->address
, ed2
->size
, fcb
->subvol
, fcb
->inode
, tp
.item
->key
.offset
- ed2
->offset
, 2, rollback
);
5898 if (!NT_SUCCESS(Status
)) {
5899 ERR("increase_extent_refcount_data returned %08x\n", Status
);
5903 last_written
= end_data
;
5910 if (tp
.item
->key
.obj_id
> fcb
->inode
|| tp
.item
->key
.obj_type
> TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
>= end_data
)
5915 if (last_written
< end_data
) {
5916 Status
= do_cow_write(Vcb
, fcb
, last_written
, end_data
, (UINT8
*)data
+ last_written
- start_data
, changed_sector_list
, rollback
);
5918 if (!NT_SUCCESS(Status
)) {
5919 ERR("do_cow_write returned %08x\n", Status
);
5924 Status
= merge_data_extents(Vcb
, fcb
, start_data
, end_data
, rollback
);
5925 if (!NT_SUCCESS(Status
)) {
5926 ERR("merge_data_extents returned %08x\n", Status
);
5930 if (deleted_prealloc
&& !is_file_prealloc(fcb
, 0, sector_align(fcb
->inode_item
.st_size
, Vcb
->superblock
.sector_size
)))
5931 fcb
->inode_item
.flags
&= ~BTRFS_INODE_PREALLOC
;
5933 return STATUS_SUCCESS
;
5936 static NTSTATUS
do_nocow_write(device_extension
* Vcb
, fcb
* fcb
, UINT64 start_data
, UINT64 length
, void* data
, LIST_ENTRY
* changed_sector_list
, LIST_ENTRY
* rollback
) {
5938 traverse_ptr tp
, next_tp
;
5943 UINT64 size
, new_start
, new_end
, last_write
= 0;
5945 TRACE("(%p, (%llx, %llx), %llx, %llx, %p, %p)\n", Vcb
, fcb
->subvol
->id
, fcb
->inode
, start_data
, length
, data
, changed_sector_list
);
5947 searchkey
.obj_id
= fcb
->inode
;
5948 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
5949 searchkey
.offset
= start_data
;
5951 Status
= find_item(Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
5952 if (!NT_SUCCESS(Status
)) {
5953 ERR("error - find_item returned %08x\n", Status
);
5957 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
> start_data
) {
5958 ERR("previous EXTENT_DATA not found (found %llx,%x,%llx)\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
);
5959 Status
= STATUS_INTERNAL_ERROR
;
5964 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
5965 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
5966 Status
= STATUS_INTERNAL_ERROR
;
5970 ed
= (EXTENT_DATA
*)tp
.item
->data
;
5972 if ((ed
->type
== EXTENT_TYPE_REGULAR
|| ed
->type
== EXTENT_TYPE_PREALLOC
) && tp
.item
->size
< sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
)) {
5973 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
) - 1 + sizeof(EXTENT_DATA2
));
5974 Status
= STATUS_INTERNAL_ERROR
;
5978 eds
= (EXTENT_DATA2
*)&ed
->data
[0];
5980 b
= find_next_item(Vcb
, &tp
, &next_tp
, TRUE
);
5983 case EXTENT_TYPE_REGULAR
:
5985 UINT64 rc
= get_extent_item_refcount(Vcb
, eds
->address
);
5988 ERR("get_extent_item_refcount failed\n");
5989 Status
= STATUS_INTERNAL_ERROR
;
5997 case EXTENT_TYPE_INLINE
:
6001 case EXTENT_TYPE_PREALLOC
:
6002 FIXME("FIXME - handle prealloc extents\n"); // FIXME
6003 Status
= STATUS_NOT_SUPPORTED
;
6007 ERR("error - unknown extent type %x\n", ed
->type
);
6008 Status
= STATUS_NOT_SUPPORTED
;
6012 if (ed
->compression
!= BTRFS_COMPRESSION_NONE
) {
6013 FIXME("FIXME: compression not yet supported\n");
6014 Status
= STATUS_NOT_SUPPORTED
;
6018 if (ed
->encryption
!= BTRFS_ENCRYPTION_NONE
) {
6019 WARN("encryption not supported\n");
6020 Status
= STATUS_INTERNAL_ERROR
;
6024 if (ed
->encoding
!= BTRFS_ENCODING_NONE
) {
6025 WARN("other encodings not supported\n");
6026 Status
= STATUS_INTERNAL_ERROR
;
6030 size
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: eds
->num_bytes
;
6032 TRACE("extent: start = %llx, length = %llx\n", tp
.item
->key
.offset
, size
);
6034 new_start
= tp
.item
->key
.offset
< start_data
? start_data
: tp
.item
->key
.offset
;
6035 new_end
= tp
.item
->key
.offset
+ size
> start_data
+ length
? (start_data
+ length
) : (tp
.item
->key
.offset
+ size
);
6037 TRACE("new_start = %llx\n", new_start
);
6038 TRACE("new_end = %llx\n", new_end
);
6041 TRACE("doing COW write\n");
6043 Status
= excise_extents(Vcb
, fcb
, new_start
, new_start
+ new_end
, changed_sector_list
, rollback
);
6045 if (!NT_SUCCESS(Status
)) {
6046 ERR("error - excise_extents returned %08x\n", Status
);
6050 Status
= insert_extent(Vcb
, fcb
, new_start
, new_end
- new_start
, (UINT8
*)data
+ new_start
- start_data
, changed_sector_list
, rollback
);
6052 if (!NT_SUCCESS(Status
)) {
6053 ERR("error - insert_extent returned %08x\n", Status
);
6059 writeaddr
= eds
->address
+ eds
->offset
+ new_start
- tp
.item
->key
.offset
;
6060 TRACE("doing non-COW write to %llx\n", writeaddr
);
6062 Status
= write_data(Vcb
, writeaddr
, (UINT8
*)data
+ new_start
- start_data
, new_end
- new_start
);
6064 if (!NT_SUCCESS(Status
)) {
6065 ERR("error - write_data returned %08x\n", Status
);
6069 if (changed_sector_list
) {
6073 sc
= ExAllocatePoolWithTag(PagedPool
, sizeof(changed_sector
), ALLOC_TAG
);
6075 ERR("out of memory\n");
6076 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6080 sc
->ol
.key
= writeaddr
;
6081 sc
->length
= (new_end
- new_start
) / Vcb
->superblock
.sector_size
;
6082 sc
->deleted
= FALSE
;
6084 sc
->checksums
= ExAllocatePoolWithTag(PagedPool
, sizeof(UINT32
) * sc
->length
, ALLOC_TAG
);
6085 if (!sc
->checksums
) {
6086 ERR("out of memory\n");
6088 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6092 for (i
= 0; i
< sc
->length
; i
++) {
6093 sc
->checksums
[i
] = ~calc_crc32c(0xffffffff, (UINT8
*)data
+ new_start
- start_data
+ (i
* Vcb
->superblock
.sector_size
), Vcb
->superblock
.sector_size
);
6096 insert_into_ordered_list(changed_sector_list
, &sc
->ol
);
6100 last_write
= new_end
;
6105 if (tp
.item
->key
.obj_id
!= fcb
->inode
|| tp
.item
->key
.obj_type
!= TYPE_EXTENT_DATA
|| tp
.item
->key
.offset
>= start_data
+ length
)
6110 if (last_write
< start_data
+ length
) {
6111 new_start
= last_write
;
6112 new_end
= start_data
+ length
;
6114 TRACE("new_start = %llx\n", new_start
);
6115 TRACE("new_end = %llx\n", new_end
);
6117 Status
= insert_extent(Vcb
, fcb
, new_start
, new_end
- new_start
, (UINT8
*)data
+ new_start
- start_data
, changed_sector_list
, rollback
);
6119 if (!NT_SUCCESS(Status
)) {
6120 ERR("error - insert_extent returned %08x\n", Status
);
6125 Status
= STATUS_SUCCESS
;
6132 #ifdef DEBUG_PARANOID
6133 static void print_loaded_trees(tree
* t
, int spaces
) {
6138 for (i
= 0; i
< spaces
; i
++) {
6144 ERR("%s(not loaded)\n", pref
);
6148 le
= t
->itemlist
.Flink
;
6149 while (le
!= &t
->itemlist
) {
6150 tree_data
* td
= CONTAINING_RECORD(le
, tree_data
, list_entry
);
6152 ERR("%s%llx,%x,%llx ignore=%s\n", pref
, td
->key
.obj_id
, td
->key
.obj_type
, td
->key
.offset
, td
->ignore
? "TRUE" : "FALSE");
6154 if (t
->header
.level
> 0) {
6155 print_loaded_trees(td
->treeholder
.tree
, spaces
+1);
6162 static void check_extents_consistent(device_extension
* Vcb
, fcb
* fcb
) {
6164 traverse_ptr tp
, next_tp
;
6165 UINT64 length
, oldlength
, lastoff
, alloc
;
6170 if (fcb
->ads
|| fcb
->inode_item
.st_size
== 0 || fcb
->deleted
)
6173 TRACE("inode = %llx, subvol = %llx\n", fcb
->inode
, fcb
->subvol
->id
);
6175 searchkey
.obj_id
= fcb
->inode
;
6176 searchkey
.obj_type
= TYPE_EXTENT_DATA
;
6177 searchkey
.offset
= 0;
6179 Status
= find_item(Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
6180 if (!NT_SUCCESS(Status
)) {
6181 ERR("error - find_item returned %08x\n", Status
);
6185 if (keycmp(&searchkey
, &tp
.item
->key
)) {
6186 ERR("could not find EXTENT_DATA at offset 0\n");
6190 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
6191 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
6195 ed
= (EXTENT_DATA
*)tp
.item
->data
;
6196 ed2
= (EXTENT_DATA2
*)&ed
->data
[0];
6198 length
= oldlength
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
;
6199 lastoff
= tp
.item
->key
.offset
;
6201 TRACE("(%llx,%x,%llx) length = %llx\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, length
);
6204 if (ed
->type
!= EXTENT_TYPE_REGULAR
|| ed2
->address
!= 0) {
6208 while (find_next_item(Vcb
, &tp
, &next_tp
, FALSE
)) {
6209 if (next_tp
.item
->key
.obj_id
!= searchkey
.obj_id
|| next_tp
.item
->key
.obj_type
!= searchkey
.obj_type
)
6214 if (tp
.item
->size
< sizeof(EXTENT_DATA
)) {
6215 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, sizeof(EXTENT_DATA
));
6219 ed
= (EXTENT_DATA
*)tp
.item
->data
;
6220 ed2
= (EXTENT_DATA2
*)&ed
->data
[0];
6222 length
= ed
->type
== EXTENT_TYPE_INLINE
? ed
->decoded_size
: ed2
->num_bytes
;
6224 TRACE("(%llx,%x,%llx) length = %llx\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, length
);
6226 if (tp
.item
->key
.offset
!= lastoff
+ oldlength
) {
6227 ERR("EXTENT_DATA in %llx,%llx was at %llx, expected %llx\n", fcb
->subvol
->id
, fcb
->inode
, tp
.item
->key
.offset
, lastoff
+ oldlength
);
6231 if (ed
->type
!= EXTENT_TYPE_REGULAR
|| ed2
->address
!= 0) {
6236 lastoff
= tp
.item
->key
.offset
;
6239 if (alloc
!= fcb
->inode_item
.st_blocks
) {
6240 ERR("allocation size was %llx, expected %llx\n", alloc
, fcb
->inode_item
.st_blocks
);
6244 // if (fcb->inode_item.st_blocks != lastoff + oldlength) {
6245 // ERR("extents finished at %x, expected %x\n", (UINT32)(lastoff + oldlength), (UINT32)fcb->inode_item.st_blocks);
6252 if (fcb
->subvol
->treeholder
.tree
)
6253 print_loaded_trees(fcb
->subvol
->treeholder
.tree
, 0);
6258 // static void check_extent_tree_consistent(device_extension* Vcb) {
6260 // traverse_ptr tp, next_tp;
6262 // BOOL b, inconsistency;
6264 // searchkey.obj_id = 0;
6265 // searchkey.obj_type = 0;
6266 // searchkey.offset = 0;
6268 // if (!find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE)) {
6269 // ERR("error - could not find any entries in extent_root\n");
6274 // inconsistency = FALSE;
6277 // if (tp.item->key.obj_type == TYPE_EXTENT_ITEM) {
6278 // // ERR("%x,%x,%x\n", (UINT32)tp.item->key.obj_id, tp.item->key.obj_type, (UINT32)tp.item->key.offset);
6280 // if (tp.item->key.obj_id < lastaddr) {
6281 // // ERR("inconsistency!\n");
6283 // inconsistency = TRUE;
6286 // lastaddr = tp.item->key.obj_id + tp.item->key.offset;
6289 // b = find_next_item(Vcb, &tp, &next_tp, NULL, FALSE);
6291 // free_traverse_ptr(&tp);
6296 // free_traverse_ptr(&tp);
6298 // if (!inconsistency)
6301 // ERR("Inconsistency detected:\n");
6303 // if (!find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE)) {
6304 // ERR("error - could not find any entries in extent_root\n");
6309 // if (tp.item->key.obj_type == TYPE_EXTENT_ITEM) {
6310 // ERR("%x,%x,%x\n", (UINT32)tp.item->key.obj_id, tp.item->key.obj_type, (UINT32)tp.item->key.offset);
6312 // if (tp.item->key.obj_id < lastaddr) {
6313 // ERR("inconsistency!\n");
6316 // lastaddr = tp.item->key.obj_id + tp.item->key.offset;
6319 // b = find_next_item(Vcb, &tp, &next_tp, NULL, FALSE);
6321 // free_traverse_ptr(&tp);
6326 // free_traverse_ptr(&tp);
6332 NTSTATUS
write_file2(device_extension
* Vcb
, PIRP Irp
, LARGE_INTEGER offset
, void* buf
, ULONG
* length
, BOOL paging_io
, BOOL no_cache
, LIST_ENTRY
* rollback
) {
6333 PIO_STACK_LOCATION IrpSp
= IoGetCurrentIrpStackLocation(Irp
);
6334 PFILE_OBJECT FileObject
= IrpSp
->FileObject
;
6338 UINT64 newlength
, start_data
, end_data
;
6342 LIST_ENTRY changed_sector_list
;
6343 INODE_ITEM
*ii
, *origii
;
6344 BOOL changed_length
= FALSE
, nocsum
, nocow
/*, lazy_writer = FALSE, write_eof = FALSE*/;
6351 BOOL paging_lock
= FALSE
;
6353 TRACE("(%p, %p, %llx, %p, %x, %u, %u)\n", Vcb
, FileObject
, offset
.QuadPart
, buf
, *length
, paging_io
, no_cache
);
6356 WARN("returning success for zero-length write\n");
6357 return STATUS_SUCCESS
;
6361 ERR("error - FileObject was NULL\n");
6362 return STATUS_ACCESS_DENIED
;
6365 fcb
= FileObject
->FsContext
;
6366 ccb
= FileObject
->FsContext2
;
6367 fileref
= ccb
? ccb
->fileref
: NULL
;
6369 if (fcb
->type
!= BTRFS_TYPE_FILE
&& fcb
->type
!= BTRFS_TYPE_SYMLINK
) {
6370 WARN("tried to write to something other than a file or symlink (inode %llx, type %u, %p, %p)\n", fcb
->inode
, fcb
->type
, &fcb
->type
, fcb
);
6371 return STATUS_INVALID_DEVICE_REQUEST
;
6374 if (offset
.LowPart
== FILE_WRITE_TO_END_OF_FILE
&& offset
.HighPart
== -1) {
6375 offset
= fcb
->Header
.FileSize
;
6376 // write_eof = TRUE;
6379 TRACE("fcb->Header.Flags = %x\n", fcb
->Header
.Flags
);
6381 if (no_cache
&& !paging_io
&& FileObject
->SectionObjectPointer
->DataSectionObject
) {
6382 IO_STATUS_BLOCK iosb
;
6384 ExAcquireResourceExclusiveLite(fcb
->Header
.PagingIoResource
, TRUE
);
6386 CcFlushCache(FileObject
->SectionObjectPointer
, &offset
, *length
, &iosb
);
6388 if (!NT_SUCCESS(iosb
.Status
)) {
6389 ExReleaseResourceLite(fcb
->Header
.PagingIoResource
);
6390 ERR("CcFlushCache returned %08x\n", iosb
.Status
);
6396 CcPurgeCacheSection(FileObject
->SectionObjectPointer
, &offset
, *length
, FALSE
);
6400 ExAcquireResourceSharedLite(fcb
->Header
.PagingIoResource
, TRUE
);
6404 nocsum
= fcb
->ads
? TRUE
: fcb
->inode_item
.flags
& BTRFS_INODE_NODATASUM
;
6405 nocow
= fcb
->ads
? TRUE
: fcb
->inode_item
.flags
& BTRFS_INODE_NODATACOW
;
6407 newlength
= fcb
->ads
? fcb
->adssize
: fcb
->inode_item
.st_size
;
6412 TRACE("newlength = %llx\n", newlength
);
6414 // if (KeGetCurrentThread() == fcb->lazy_writer_thread) {
6415 // ERR("lazy writer on the TV\n");
6416 // lazy_writer = TRUE;
6419 if (offset
.QuadPart
+ *length
> newlength
) {
6421 if (offset
.QuadPart
>= newlength
) {
6422 TRACE("paging IO tried to write beyond end of file (file size = %llx, offset = %llx, length = %x)\n", newlength
, offset
.QuadPart
, *length
);
6423 TRACE("filename %S\n", file_desc(FileObject
));
6424 TRACE("FileObject: AllocationSize = %llx, FileSize = %llx, ValidDataLength = %llx\n",
6425 fcb
->Header
.AllocationSize
.QuadPart
, fcb
->Header
.FileSize
.QuadPart
, fcb
->Header
.ValidDataLength
.QuadPart
);
6426 Status
= STATUS_SUCCESS
;
6430 *length
= newlength
- offset
.QuadPart
;
6432 newlength
= offset
.QuadPart
+ *length
;
6433 changed_length
= TRUE
;
6435 TRACE("extending length to %llx\n", newlength
);
6439 make_inline
= fcb
->ads
? FALSE
: newlength
<= fcb
->Vcb
->max_inline
;
6441 if (changed_length
) {
6442 if (newlength
> fcb
->Header
.AllocationSize
.QuadPart
) {
6443 Status
= extend_file(fcb
, fileref
, newlength
, FALSE
, rollback
);
6444 if (!NT_SUCCESS(Status
)) {
6445 ERR("extend_file returned %08x\n", Status
);
6448 } else if (fcb
->ads
)
6449 fcb
->adssize
= newlength
;
6451 fcb
->inode_item
.st_size
= newlength
;
6453 fcb
->Header
.FileSize
.QuadPart
= newlength
;
6454 fcb
->Header
.ValidDataLength
.QuadPart
= newlength
;
6456 TRACE("AllocationSize = %llx\n", fcb
->Header
.AllocationSize
.QuadPart
);
6457 TRACE("FileSize = %llx\n", fcb
->Header
.FileSize
.QuadPart
);
6458 TRACE("ValidDataLength = %llx\n", fcb
->Header
.ValidDataLength
.QuadPart
);
6464 if (!FileObject
->PrivateCacheMap
|| changed_length
) {
6467 ccfs
.AllocationSize
= fcb
->Header
.AllocationSize
;
6468 ccfs
.FileSize
= fcb
->Header
.FileSize
;
6469 ccfs
.ValidDataLength
= fcb
->Header
.ValidDataLength
;
6471 if (!FileObject
->PrivateCacheMap
) {
6472 TRACE("calling CcInitializeCacheMap...\n");
6473 CcInitializeCacheMap(FileObject
, &ccfs
, FALSE
, cache_callbacks
, FileObject
);
6475 CcSetReadAheadGranularity(FileObject
, READ_AHEAD_GRANULARITY
);
6477 CcSetFileSizes(FileObject
, &ccfs
);
6481 // FIXME - uncomment this when async is working
6482 // wait = IoIsOperationSynchronous(Irp) ? TRUE : FALSE;
6485 if (IrpSp
->MinorFunction
& IRP_MN_MDL
) {
6486 CcPrepareMdlWrite(FileObject
, &offset
, *length
, &Irp
->MdlAddress
, &Irp
->IoStatus
);
6488 Status
= Irp
->IoStatus
.Status
;
6491 TRACE("CcCopyWrite(%p, %llx, %x, %u, %p)\n", FileObject
, offset
.QuadPart
, *length
, wait
, buf
);
6492 if (!CcCopyWrite(FileObject
, &offset
, *length
, wait
, buf
)) {
6493 TRACE("CcCopyWrite failed.\n");
6495 IoMarkIrpPending(Irp
);
6496 Status
= STATUS_PENDING
;
6499 TRACE("CcCopyWrite finished\n");
6502 Status
= STATUS_SUCCESS
;
6511 if (!get_xattr(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, fcb
->adsxattr
.Buffer
, fcb
->adshash
, &data
, &datalen
)) {
6512 ERR("get_xattr failed\n");
6513 Status
= STATUS_INTERNAL_ERROR
;
6517 if (changed_length
) {
6518 // find maximum length of xattr
6519 maxlen
= Vcb
->superblock
.node_size
- sizeof(tree_header
) - sizeof(leaf_node
);
6521 searchkey
.obj_id
= fcb
->inode
;
6522 searchkey
.obj_type
= TYPE_XATTR_ITEM
;
6523 searchkey
.offset
= fcb
->adshash
;
6525 Status
= find_item(fcb
->Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
6526 if (!NT_SUCCESS(Status
)) {
6527 ERR("error - find_item returned %08x\n", Status
);
6531 if (keycmp(&tp
.item
->key
, &searchkey
)) {
6532 ERR("error - could not find key for xattr\n");
6533 Status
= STATUS_INTERNAL_ERROR
;
6537 if (tp
.item
->size
< datalen
) {
6538 ERR("(%llx,%x,%llx) was %u bytes, expected at least %u\n", tp
.item
->key
.obj_id
, tp
.item
->key
.obj_type
, tp
.item
->key
.offset
, tp
.item
->size
, datalen
);
6539 Status
= STATUS_INTERNAL_ERROR
;
6543 maxlen
-= tp
.item
->size
- datalen
; // subtract XATTR_ITEM overhead
6545 if (newlength
> maxlen
) {
6546 ERR("error - xattr too long (%llu > %u)\n", newlength
, maxlen
);
6547 Status
= STATUS_DISK_FULL
;
6551 fcb
->adssize
= newlength
;
6553 data2
= ExAllocatePoolWithTag(PagedPool
, newlength
, ALLOC_TAG
);
6555 ERR("out of memory\n");
6556 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6560 RtlCopyMemory(data2
, data
, datalen
);
6562 if (offset
.QuadPart
> datalen
)
6563 RtlZeroMemory(&data2
[datalen
], offset
.QuadPart
- datalen
);
6568 RtlCopyMemory(&data2
[offset
.QuadPart
], buf
, *length
);
6570 Status
= set_xattr(fcb
->Vcb
, fcb
->subvol
, fcb
->inode
, fcb
->adsxattr
.Buffer
, fcb
->adshash
, data2
, newlength
, rollback
);
6571 if (!NT_SUCCESS(Status
)) {
6572 ERR("set_xattr returned %08x\n", Status
);
6576 if (data
) ExFreePool(data
);
6577 if (data2
!= data
) ExFreePool(data2
);
6579 fcb
->Header
.ValidDataLength
.QuadPart
= newlength
;
6583 end_data
= sector_align(newlength
, fcb
->Vcb
->superblock
.sector_size
);
6584 bufhead
= sizeof(EXTENT_DATA
) - 1;
6586 start_data
= offset
.QuadPart
& ~(fcb
->Vcb
->superblock
.sector_size
- 1);
6587 end_data
= sector_align(offset
.QuadPart
+ *length
, fcb
->Vcb
->superblock
.sector_size
);
6591 fcb
->Header
.ValidDataLength
.QuadPart
= newlength
;
6592 TRACE("fcb %p FileSize = %llx\n", fcb
, fcb
->Header
.FileSize
.QuadPart
);
6594 data
= ExAllocatePoolWithTag(PagedPool
, end_data
- start_data
+ bufhead
, ALLOC_TAG
);
6596 ERR("out of memory\n");
6597 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6601 RtlZeroMemory(data
+ bufhead
, end_data
- start_data
);
6603 TRACE("start_data = %llx\n", start_data
);
6604 TRACE("end_data = %llx\n", end_data
);
6606 if (offset
.QuadPart
> start_data
|| offset
.QuadPart
+ *length
< end_data
) {
6607 if (changed_length
) {
6608 if (fcb
->inode_item
.st_size
> start_data
)
6609 Status
= read_file(Vcb
, fcb
->subvol
, fcb
->inode
, data
+ bufhead
, start_data
, fcb
->inode_item
.st_size
- start_data
, NULL
);
6611 Status
= STATUS_SUCCESS
;
6613 Status
= read_file(Vcb
, fcb
->subvol
, fcb
->inode
, data
+ bufhead
, start_data
, end_data
- start_data
, NULL
);
6615 if (!NT_SUCCESS(Status
)) {
6616 ERR("read_file returned %08x\n", Status
);
6622 RtlCopyMemory(data
+ bufhead
+ offset
.QuadPart
- start_data
, buf
, *length
);
6625 InitializeListHead(&changed_sector_list
);
6628 Status
= excise_extents(fcb
->Vcb
, fcb
, start_data
, end_data
, nocsum
? NULL
: &changed_sector_list
, rollback
);
6629 if (!NT_SUCCESS(Status
)) {
6630 ERR("error - excise_extents returned %08x\n", Status
);
6635 ed2
= (EXTENT_DATA
*)data
;
6636 ed2
->generation
= fcb
->Vcb
->superblock
.generation
;
6637 ed2
->decoded_size
= newlength
;
6638 ed2
->compression
= BTRFS_COMPRESSION_NONE
;
6639 ed2
->encryption
= BTRFS_ENCRYPTION_NONE
;
6640 ed2
->encoding
= BTRFS_ENCODING_NONE
;
6641 ed2
->type
= EXTENT_TYPE_INLINE
;
6643 insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_EXTENT_DATA
, 0, ed2
, sizeof(EXTENT_DATA
) - 1 + newlength
, NULL
, rollback
);
6645 fcb
->inode_item
.st_blocks
+= newlength
;
6646 } else if (!nocow
) {
6647 if (is_file_prealloc(fcb
, start_data
, end_data
)) {
6648 Status
= do_prealloc_write(fcb
->Vcb
, fcb
, start_data
, end_data
, data
, nocsum
? NULL
: &changed_sector_list
, rollback
);
6650 if (!NT_SUCCESS(Status
)) {
6651 ERR("error - do_prealloc_write returned %08x\n", Status
);
6656 Status
= do_cow_write(fcb
->Vcb
, fcb
, start_data
, end_data
, data
, nocsum
? NULL
: &changed_sector_list
, rollback
);
6658 if (!NT_SUCCESS(Status
)) {
6659 ERR("error - do_cow_write returned %08x\n", Status
);
6667 Status
= do_nocow_write(fcb
->Vcb
, fcb
, start_data
, end_data
- start_data
, data
, nocsum
? NULL
: &changed_sector_list
, rollback
);
6669 if (!NT_SUCCESS(Status
)) {
6670 ERR("error - do_nocow_write returned %08x\n", Status
);
6679 KeQuerySystemTime(&time
);
6680 win_time_to_unix(time
, &now
);
6682 // ERR("no_cache = %s, FileObject->PrivateCacheMap = %p\n", no_cache ? "TRUE" : "FALSE", FileObject->PrivateCacheMap);
6685 // if (!FileObject->PrivateCacheMap) {
6686 // CC_FILE_SIZES ccfs;
6688 // ccfs.AllocationSize = fcb->Header.AllocationSize;
6689 // ccfs.FileSize = fcb->Header.FileSize;
6690 // ccfs.ValidDataLength = fcb->Header.ValidDataLength;
6692 // TRACE("calling CcInitializeCacheMap...\n");
6693 // CcInitializeCacheMap(FileObject, &ccfs, FALSE, cache_callbacks, fcb);
6695 // changed_length = FALSE;
6700 if (fileref
&& fileref
->parent
)
6701 origii
= &fileref
->parent
->fcb
->inode_item
;
6703 ERR("no parent fcb found for stream\n");
6704 Status
= STATUS_INTERNAL_ERROR
;
6708 origii
= &fcb
->inode_item
;
6710 origii
->transid
= Vcb
->superblock
.generation
;
6712 origii
->st_ctime
= now
;
6715 TRACE("setting st_size to %llx\n", newlength
);
6716 origii
->st_size
= newlength
;
6717 origii
->st_mtime
= now
;
6720 searchkey
.obj_id
= fcb
->inode
;
6721 searchkey
.obj_type
= TYPE_INODE_ITEM
;
6722 searchkey
.offset
= 0;
6724 Status
= find_item(fcb
->Vcb
, fcb
->subvol
, &tp
, &searchkey
, FALSE
);
6725 if (!NT_SUCCESS(Status
)) {
6726 ERR("error - find_item returned %08x\n", Status
);
6730 if (!keycmp(&tp
.item
->key
, &searchkey
))
6731 delete_tree_item(Vcb
, &tp
, rollback
);
6733 WARN("couldn't find existing INODE_ITEM\n");
6735 ii
= ExAllocatePoolWithTag(PagedPool
, sizeof(INODE_ITEM
), ALLOC_TAG
);
6737 ERR("out of memory\n");
6738 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6742 RtlCopyMemory(ii
, origii
, sizeof(INODE_ITEM
));
6743 insert_tree_item(Vcb
, fcb
->subvol
, fcb
->inode
, TYPE_INODE_ITEM
, 0, ii
, sizeof(INODE_ITEM
), NULL
, rollback
);
6745 // FIXME - update inode_item of open FCBs pointing to the same inode (i.e. hardlinked files)
6748 update_checksum_tree(Vcb
, &changed_sector_list
, rollback
);
6750 if (changed_length
) {
6753 ccfs
.AllocationSize
= fcb
->Header
.AllocationSize
;
6754 ccfs
.FileSize
= fcb
->Header
.FileSize
;
6755 ccfs
.ValidDataLength
= fcb
->Header
.ValidDataLength
;
6757 CcSetFileSizes(FileObject
, &ccfs
);
6760 // FIXME - make sure this still called if STATUS_PENDING and async
6762 // if (!CcCopyWrite(FileObject, &offset, *length, TRUE, buf)) {
6763 // ERR("CcCopyWrite failed.\n");
6767 fcb
->subvol
->root_item
.ctransid
= Vcb
->superblock
.generation
;
6768 fcb
->subvol
->root_item
.ctime
= now
;
6770 Status
= STATUS_SUCCESS
;
6773 if (FileObject
->Flags
& FO_SYNCHRONOUS_IO
&& !paging_io
) {
6774 TRACE("CurrentByteOffset was: %llx\n", FileObject
->CurrentByteOffset
.QuadPart
);
6775 FileObject
->CurrentByteOffset
.QuadPart
= offset
.QuadPart
+ (NT_SUCCESS(Status
) ? *length
: 0);
6776 TRACE("CurrentByteOffset now: %llx\n", FileObject
->CurrentByteOffset
.QuadPart
);
6780 ExReleaseResourceLite(fcb
->Header
.PagingIoResource
);
6785 NTSTATUS
write_file(PDEVICE_OBJECT DeviceObject
, PIRP Irp
) {
6786 PIO_STACK_LOCATION IrpSp
= IoGetCurrentIrpStackLocation(Irp
);
6787 device_extension
* Vcb
= DeviceObject
->DeviceExtension
;
6790 LARGE_INTEGER offset
= IrpSp
->Parameters
.Write
.ByteOffset
;
6791 PFILE_OBJECT FileObject
= IrpSp
->FileObject
;
6792 fcb
* fcb
= FileObject
? FileObject
->FsContext
: NULL
;
6793 BOOL locked
= FALSE
;
6794 // LARGE_INTEGER freq, time1, time2;
6795 LIST_ENTRY rollback
;
6797 InitializeListHead(&rollback
);
6800 return STATUS_MEDIA_WRITE_PROTECTED
;
6802 if (fcb
&& fcb
->subvol
->root_item
.flags
& BTRFS_SUBVOL_READONLY
)
6803 return STATUS_ACCESS_DENIED
;
6805 // time1 = KeQueryPerformanceCounter(&freq);
6809 Irp
->IoStatus
.Information
= 0;
6811 TRACE("offset = %llx\n", offset
.QuadPart
);
6812 TRACE("length = %x\n", IrpSp
->Parameters
.Write
.Length
);
6814 if (!Irp
->AssociatedIrp
.SystemBuffer
) {
6815 buf
= map_user_buffer(Irp
);
6817 if (Irp
->MdlAddress
&& !buf
) {
6818 ERR("MmGetSystemAddressForMdlSafe returned NULL\n");
6819 Status
= STATUS_INSUFFICIENT_RESOURCES
;
6823 buf
= Irp
->AssociatedIrp
.SystemBuffer
;
6825 TRACE("buf = %p\n", buf
);
6827 if (Irp
->Flags
& IRP_NOCACHE
) {
6828 acquire_tree_lock(Vcb
, TRUE
);
6832 if (fcb
&& !(Irp
->Flags
& IRP_PAGING_IO
) && !FsRtlCheckLockForWriteAccess(&fcb
->lock
, Irp
)) {
6833 WARN("tried to write to locked region\n");
6834 Status
= STATUS_FILE_LOCK_CONFLICT
;
6838 // ERR("Irp->Flags = %x\n", Irp->Flags);
6839 Status
= write_file2(Vcb
, Irp
, offset
, buf
, &IrpSp
->Parameters
.Write
.Length
, Irp
->Flags
& IRP_PAGING_IO
, Irp
->Flags
& IRP_NOCACHE
, &rollback
);
6840 if (!NT_SUCCESS(Status
)) {
6841 if (Status
!= STATUS_PENDING
)
6842 ERR("write_file2 returned %08x\n", Status
);
6847 Status
= consider_write(Vcb
);
6849 if (NT_SUCCESS(Status
)) {
6850 Irp
->IoStatus
.Information
= IrpSp
->Parameters
.Write
.Length
;
6852 #ifdef DEBUG_PARANOID
6854 check_extents_consistent(Vcb
, FileObject
->FsContext
); // TESTING
6856 // check_extent_tree_consistent(Vcb);
6862 if (NT_SUCCESS(Status
))
6863 clear_rollback(&rollback
);
6865 do_rollback(Vcb
, &rollback
);
6867 release_tree_lock(Vcb
, TRUE
);
6870 // time2 = KeQueryPerformanceCounter(NULL);
6872 // ERR("time = %u (freq = %u)\n", (UINT32)(time2.QuadPart - time1.QuadPart), (UINT32)freq.QuadPart);