projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
[BTRFS]
[reactos.git] / reactos / drivers / filesystems / btrfs / flushthread.c
1 /* Copyright (c) Mark Harmstone 2016
2 *
3 * This file is part of WinBtrfs.
4 *
5 * WinBtrfs is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Lesser General Public Licence as published by
7 * the Free Software Foundation, either version 3 of the Licence, or
8 * (at your option) any later version.
9 *
10 * WinBtrfs is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Lesser General Public Licence for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public Licence
16 * along with WinBtrfs. If not, see <http://www.gnu.org/licenses/>. */
17
18 #include "btrfs_drv.h"
19
20 #define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - sizeof(leaf_node))
21
22 // #define DEBUG_WRITE_LOOPS
23
24 typedef struct {
25 KEVENT Event;
26 IO_STATUS_BLOCK iosb;
27 } write_context;
28
29 typedef struct {
30 EXTENT_ITEM_TREE eit;
31 UINT8 type;
32 TREE_BLOCK_REF tbr;
33 } EXTENT_ITEM_TREE2;
34
35 typedef struct {
36 EXTENT_ITEM ei;
37 UINT8 type;
38 TREE_BLOCK_REF tbr;
39 } EXTENT_ITEM_SKINNY_METADATA;
40
41 typedef struct {
42 UINT64 address;
43 UINT32 length;
44 BOOL overlap;
45 UINT8* data;
46 LIST_ENTRY list_entry;
47 } tree_write;
48
49 static NTSTATUS create_chunk(device_extension* Vcb, chunk* c, PIRP Irp, LIST_ENTRY* rollback);
50
51 static BOOL insert_tree_item_batch(LIST_ENTRY* batchlist, device_extension* Vcb, root* r, UINT64 objid, UINT64 objtype, UINT64 offset,
52 void* data, UINT16 datalen, enum batch_operation operation, PIRP Irp, LIST_ENTRY* rollback);
53
54 static NTSTATUS STDCALL write_completion(PDEVICE_OBJECT DeviceObject, PIRP Irp, PVOID conptr) {
55 write_context* context = conptr;
56
57 context->iosb = Irp->IoStatus;
58 KeSetEvent(&context->Event, 0, FALSE);
59
60 // return STATUS_SUCCESS;
61 return STATUS_MORE_PROCESSING_REQUIRED;
62 }
63
64 NTSTATUS STDCALL write_data_phys(PDEVICE_OBJECT device, UINT64 address, void* data, UINT32 length) {
65 NTSTATUS Status;
66 LARGE_INTEGER offset;
67 PIRP Irp;
68 PIO_STACK_LOCATION IrpSp;
69 write_context* context = NULL;
70
71 TRACE("(%p, %llx, %p, %x)\n", device, address, data, length);
72
73 context = ExAllocatePoolWithTag(NonPagedPool, sizeof(write_context), ALLOC_TAG);
74 if (!context) {
75 ERR("out of memory\n");
76 return STATUS_INSUFFICIENT_RESOURCES;
77 }
78
79 RtlZeroMemory(context, sizeof(write_context));
80
81 KeInitializeEvent(&context->Event, NotificationEvent, FALSE);
82
83 offset.QuadPart = address;
84
85 // Irp = IoBuildSynchronousFsdRequest(IRP_MJ_WRITE, Vcb->device, data, length, &offset, NULL, &context->iosb);
86
87 Irp = IoAllocateIrp(device->StackSize, FALSE);
88
89 if (!Irp) {
90 ERR("IoAllocateIrp failed\n");
91 Status = STATUS_INTERNAL_ERROR;
92 goto exit2;
93 }
94
95 IrpSp = IoGetNextIrpStackLocation(Irp);
96 IrpSp->MajorFunction = IRP_MJ_WRITE;
97
98 if (device->Flags & DO_BUFFERED_IO) {
99 Irp->AssociatedIrp.SystemBuffer = data;
100
101 Irp->Flags = IRP_BUFFERED_IO;
102 } else if (device->Flags & DO_DIRECT_IO) {
103 Irp->MdlAddress = IoAllocateMdl(data, length, FALSE, FALSE, NULL);
104 if (!Irp->MdlAddress) {
105 DbgPrint("IoAllocateMdl failed\n");
106 goto exit;
107 }
108
109 MmProbeAndLockPages(Irp->MdlAddress, KernelMode, IoWriteAccess);
110 } else {
111 Irp->UserBuffer = data;
112 }
113
114 IrpSp->Parameters.Write.Length = length;
115 IrpSp->Parameters.Write.ByteOffset = offset;
116
117 Irp->UserIosb = &context->iosb;
118
119 Irp->UserEvent = &context->Event;
120
121 IoSetCompletionRoutine(Irp, write_completion, context, TRUE, TRUE, TRUE);
122
123 Status = IoCallDriver(device, Irp);
124
125 if (Status == STATUS_PENDING) {
126 KeWaitForSingleObject(&context->Event, Executive, KernelMode, FALSE, NULL);
127 Status = context->iosb.Status;
128 }
129
130 if (!NT_SUCCESS(Status)) {
131 ERR("IoCallDriver returned %08x\n", Status);
132 }
133
134 if (device->Flags & DO_DIRECT_IO) {
135 MmUnlockPages(Irp->MdlAddress);
136 IoFreeMdl(Irp->MdlAddress);
137 }
138
139 exit:
140 IoFreeIrp(Irp);
141
142 exit2:
143 if (context)
144 ExFreePool(context);
145
146 return Status;
147 }
148
149 static void clean_space_cache_chunk(device_extension* Vcb, chunk* c) {
150 // FIXME - loop through c->deleting and do TRIM if device supports it
151 // FIXME - also find way of doing TRIM of dropped chunks
152
153 while (!IsListEmpty(&c->deleting)) {
154 space* s = CONTAINING_RECORD(c->deleting.Flink, space, list_entry);
155
156 RemoveEntryList(&s->list_entry);
157 ExFreePool(s);
158 }
159 }
160
161 static void clean_space_cache(device_extension* Vcb) {
162 chunk* c;
163
164 TRACE("(%p)\n", Vcb);
165
166 while (!IsListEmpty(&Vcb->chunks_changed)) {
167 c = CONTAINING_RECORD(Vcb->chunks_changed.Flink, chunk, list_entry_changed);
168
169 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
170
171 clean_space_cache_chunk(Vcb, c);
172 RemoveEntryList(&c->list_entry_changed);
173 c->list_entry_changed.Flink = NULL;
174
175 ExReleaseResourceLite(&c->lock);
176 }
177 }
178
179 static BOOL trees_consistent(device_extension* Vcb, LIST_ENTRY* rollback) {
180 ULONG maxsize = Vcb->superblock.node_size - sizeof(tree_header);
181 LIST_ENTRY* le;
182
183 le = Vcb->trees.Flink;
184 while (le != &Vcb->trees) {
185 tree* t = CONTAINING_RECORD(le, tree, list_entry);
186
187 if (t->write) {
188 if (t->header.num_items == 0 && t->parent) {
189 #ifdef DEBUG_WRITE_LOOPS
190 ERR("empty tree found, looping again\n");
191 #endif
192 return FALSE;
193 }
194
195 if (t->size > maxsize) {
196 #ifdef DEBUG_WRITE_LOOPS
197 ERR("overlarge tree found (%u > %u), looping again\n", t->size, maxsize);
198 #endif
199 return FALSE;
200 }
201
202 if (!t->has_new_address) {
203 #ifdef DEBUG_WRITE_LOOPS
204 ERR("tree found without new address, looping again\n");
205 #endif
206 return FALSE;
207 }
208 }
209
210 le = le->Flink;
211 }
212
213 return TRUE;
214 }
215
216 static NTSTATUS add_parents(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
217 UINT8 level;
218 LIST_ENTRY* le;
219
220 for (level = 0; level <= 255; level++) {
221 BOOL nothing_found = TRUE;
222
223 TRACE("level = %u\n", level);
224
225 le = Vcb->trees.Flink;
226 while (le != &Vcb->trees) {
227 tree* t = CONTAINING_RECORD(le, tree, list_entry);
228
229 if (t->write && t->header.level == level) {
230 TRACE("tree %p: root = %llx, level = %x, parent = %p\n", t, t->header.tree_id, t->header.level, t->parent);
231
232 nothing_found = FALSE;
233
234 if (t->parent) {
235 if (!t->parent->write)
236 TRACE("adding tree %p (level %x)\n", t->parent, t->header.level);
237
238 t->parent->write = TRUE;
239 } else if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
240 KEY searchkey;
241 traverse_ptr tp;
242 NTSTATUS Status;
243
244 searchkey.obj_id = t->root->id;
245 searchkey.obj_type = TYPE_ROOT_ITEM;
246 searchkey.offset = 0xffffffffffffffff;
247
248 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
249 if (!NT_SUCCESS(Status)) {
250 ERR("error - find_item returned %08x\n", Status);
251 return Status;
252 }
253
254 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
255 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey.obj_id);
256 return STATUS_INTERNAL_ERROR;
257 }
258
259 if (tp.item->size < sizeof(ROOT_ITEM)) { // if not full length, delete and create new entry
260 ROOT_ITEM* ri = ExAllocatePoolWithTag(PagedPool, sizeof(ROOT_ITEM), ALLOC_TAG);
261
262 if (!ri) {
263 ERR("out of memory\n");
264 return STATUS_INSUFFICIENT_RESOURCES;
265 }
266
267 RtlCopyMemory(ri, &t->root->root_item, sizeof(ROOT_ITEM));
268
269 delete_tree_item(Vcb, &tp, rollback);
270
271 if (!insert_tree_item(Vcb, Vcb->root_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, ri, sizeof(ROOT_ITEM), NULL, Irp, rollback)) {
272 ERR("insert_tree_item failed\n");
273 return STATUS_INTERNAL_ERROR;
274 }
275 }
276 }
277 }
278
279 le = le->Flink;
280 }
281
282 if (nothing_found)
283 break;
284 }
285
286 return STATUS_SUCCESS;
287 }
288
289 static void add_parents_to_cache(device_extension* Vcb, tree* t) {
290 while (t->parent) {
291 t = t->parent;
292 t->write = TRUE;
293 }
294 }
295
296 static BOOL insert_tree_extent_skinny(device_extension* Vcb, UINT8 level, UINT64 root_id, chunk* c, UINT64 address, PIRP Irp, LIST_ENTRY* rollback) {
297 EXTENT_ITEM_SKINNY_METADATA* eism;
298 traverse_ptr insert_tp;
299
300 eism = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_ITEM_SKINNY_METADATA), ALLOC_TAG);
301 if (!eism) {
302 ERR("out of memory\n");
303 return FALSE;
304 }
305
306 eism->ei.refcount = 1;
307 eism->ei.generation = Vcb->superblock.generation;
308 eism->ei.flags = EXTENT_ITEM_TREE_BLOCK;
309 eism->type = TYPE_TREE_BLOCK_REF;
310 eism->tbr.offset = root_id;
311
312 if (!insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, eism, sizeof(EXTENT_ITEM_SKINNY_METADATA), &insert_tp, Irp, rollback)) {
313 ERR("insert_tree_item failed\n");
314 ExFreePool(eism);
315 return FALSE;
316 }
317
318 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
319
320 space_list_subtract(Vcb, c, FALSE, address, Vcb->superblock.node_size, rollback);
321
322 ExReleaseResourceLite(&c->lock);
323
324 add_parents_to_cache(Vcb, insert_tp.tree);
325
326 return TRUE;
327 }
328
329 static BOOL insert_tree_extent(device_extension* Vcb, UINT8 level, UINT64 root_id, chunk* c, UINT64* new_address, PIRP Irp, LIST_ENTRY* rollback) {
330 UINT64 address;
331 EXTENT_ITEM_TREE2* eit2;
332 traverse_ptr insert_tp;
333
334 TRACE("(%p, %x, %llx, %p, %p, %p, %p)\n", Vcb, level, root_id, c, new_address, rollback);
335
336 if (!find_address_in_chunk(Vcb, c, Vcb->superblock.node_size, &address))
337 return FALSE;
338
339 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
340 BOOL b = insert_tree_extent_skinny(Vcb, level, root_id, c, address, Irp, rollback);
341
342 if (b)
343 *new_address = address;
344
345 return b;
346 }
347
348 eit2 = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_ITEM_TREE2), ALLOC_TAG);
349 if (!eit2) {
350 ERR("out of memory\n");
351 return FALSE;
352 }
353
354 eit2->eit.extent_item.refcount = 1;
355 eit2->eit.extent_item.generation = Vcb->superblock.generation;
356 eit2->eit.extent_item.flags = EXTENT_ITEM_TREE_BLOCK;
357 // eit2->eit.firstitem = wt->firstitem;
358 eit2->eit.level = level;
359 eit2->type = TYPE_TREE_BLOCK_REF;
360 eit2->tbr.offset = root_id;
361
362 // #ifdef DEBUG_PARANOID
363 // if (wt->firstitem.obj_type == 0xcc) { // TESTING
364 // ERR("error - firstitem not set (wt = %p, tree = %p, address = %x)\n", wt, wt->tree, (UINT32)address);
365 // 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);
366 // int3;
367 // }
368 // #endif
369
370 if (!insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_EXTENT_ITEM, Vcb->superblock.node_size, eit2, sizeof(EXTENT_ITEM_TREE2), &insert_tp, Irp, rollback)) {
371 ERR("insert_tree_item failed\n");
372 ExFreePool(eit2);
373 return FALSE;
374 }
375
376 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
377
378 space_list_subtract(Vcb, c, FALSE, address, Vcb->superblock.node_size, rollback);
379
380 ExReleaseResourceLite(&c->lock);
381
382 add_parents_to_cache(Vcb, insert_tp.tree);
383
384 *new_address = address;
385
386 return TRUE;
387 }
388
389 NTSTATUS get_tree_new_address(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
390 chunk *origchunk = NULL, *c;
391 LIST_ENTRY* le;
392 UINT64 flags = t->flags, addr;
393
394 if (flags == 0) {
395 if (t->root->id == BTRFS_ROOT_CHUNK)
396 flags = BLOCK_FLAG_SYSTEM | BLOCK_FLAG_DUPLICATE;
397 else if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_MIXED_GROUPS)
398 flags = BLOCK_FLAG_DATA | BLOCK_FLAG_METADATA;
399 else
400 flags = BLOCK_FLAG_METADATA | BLOCK_FLAG_DUPLICATE;
401 }
402
403 // TRACE("flags = %x\n", (UINT32)wt->flags);
404
405 // if (!chunk_test) { // TESTING
406 // if ((c = alloc_chunk(Vcb, flags))) {
407 // if ((c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
408 // if (insert_tree_extent(Vcb, t, c)) {
409 // chunk_test = TRUE;
410 // return STATUS_SUCCESS;
411 // }
412 // }
413 // }
414 // }
415
416 if (t->has_address) {
417 origchunk = get_chunk_from_address(Vcb, t->header.address);
418
419 if (!origchunk->readonly && insert_tree_extent(Vcb, t->header.level, t->root->id, origchunk, &addr, Irp, rollback)) {
420 t->new_address = addr;
421 t->has_new_address = TRUE;
422 return STATUS_SUCCESS;
423 }
424 }
425
426 ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, TRUE);
427
428 le = Vcb->chunks.Flink;
429 while (le != &Vcb->chunks) {
430 c = CONTAINING_RECORD(le, chunk, list_entry);
431
432 if (!c->readonly) {
433 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
434
435 if (c != origchunk && c->chunk_item->type == flags && (c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
436 if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
437 ExReleaseResourceLite(&c->lock);
438 ExReleaseResourceLite(&Vcb->chunk_lock);
439 t->new_address = addr;
440 t->has_new_address = TRUE;
441 return STATUS_SUCCESS;
442 }
443 }
444
445 ExReleaseResourceLite(&c->lock);
446 }
447
448 le = le->Flink;
449 }
450
451 // allocate new chunk if necessary
452 if ((c = alloc_chunk(Vcb, flags))) {
453 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
454
455 if ((c->chunk_item->size - c->used) >= Vcb->superblock.node_size) {
456 if (insert_tree_extent(Vcb, t->header.level, t->root->id, c, &addr, Irp, rollback)) {
457 ExReleaseResourceLite(&c->lock);
458 ExReleaseResourceLite(&Vcb->chunk_lock);
459 t->new_address = addr;
460 t->has_new_address = TRUE;
461 return STATUS_SUCCESS;
462 }
463 }
464
465 ExReleaseResourceLite(&c->lock);
466 }
467
468 ExReleaseResourceLite(&Vcb->chunk_lock);
469
470 ERR("couldn't find any metadata chunks with %x bytes free\n", Vcb->superblock.node_size);
471
472 return STATUS_DISK_FULL;
473 }
474
475 // TESTING
476 // static void check_tree_num_items(tree* t) {
477 // LIST_ENTRY* le2;
478 // UINT32 ni;
479 //
480 // le2 = t->itemlist.Flink;
481 // ni = 0;
482 // while (le2 != &t->itemlist) {
483 // tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
484 // if (!td->ignore)
485 // ni++;
486 // le2 = le2->Flink;
487 // }
488 //
489 // if (t->header.num_items != ni) {
490 // ERR("tree %p not okay: num_items was %x, expecting %x\n", t, ni, t->header.num_items);
491 // int3;
492 // } else {
493 // ERR("tree %p okay\n", t);
494 // }
495 // }
496 //
497 // static void check_trees_num_items(LIST_ENTRY* tc) {
498 // LIST_ENTRY* le = tc->Flink;
499 // while (le != tc) {
500 // tree_cache* tc2 = CONTAINING_RECORD(le, tree_cache, list_entry);
501 //
502 // check_tree_num_items(tc2->tree);
503 //
504 // le = le->Flink;
505 // }
506 // }
507
508 static NTSTATUS reduce_tree_extent(device_extension* Vcb, UINT64 address, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
509 NTSTATUS Status;
510 UINT64 rc, root;
511
512 TRACE("(%p, %llx, %p)\n", Vcb, address, t);
513
514 rc = get_extent_refcount(Vcb, address, Vcb->superblock.node_size, Irp);
515 if (rc == 0) {
516 ERR("error - refcount for extent %llx was 0\n", address);
517 return STATUS_INTERNAL_ERROR;
518 }
519
520 if (t->parent)
521 root = t->parent->header.tree_id;
522 else
523 root = t->header.tree_id;
524
525 Status = decrease_extent_refcount_tree(Vcb, address, Vcb->superblock.node_size, root, t->header.level, Irp, rollback);
526 if (!NT_SUCCESS(Status)) {
527 ERR("decrease_extent_refcount_tree returned %08x\n", Status);
528 return Status;
529 }
530
531 if (rc == 1) {
532 chunk* c = get_chunk_from_address(Vcb, address);
533
534 if (c) {
535 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
536
537 decrease_chunk_usage(c, Vcb->superblock.node_size);
538
539 space_list_add(Vcb, c, TRUE, address, Vcb->superblock.node_size, rollback);
540
541 ExReleaseResourceLite(&c->lock);
542 } else
543 ERR("could not find chunk for address %llx\n", address);
544 }
545
546 return STATUS_SUCCESS;
547 }
548
549 static NTSTATUS add_changed_extent_ref_edr(changed_extent* ce, EXTENT_DATA_REF* edr, BOOL old) {
550 LIST_ENTRY *le2, *list;
551 changed_extent_ref* cer;
552
553 list = old ? &ce->old_refs : &ce->refs;
554
555 le2 = list->Flink;
556 while (le2 != list) {
557 cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
558
559 if (cer->type == TYPE_EXTENT_DATA_REF && cer->edr.root == edr->root && cer->edr.objid == edr->objid && cer->edr.offset == edr->offset) {
560 cer->edr.count += edr->count;
561 goto end;
562 }
563
564 le2 = le2->Flink;
565 }
566
567 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
568 if (!cer) {
569 ERR("out of memory\n");
570 return STATUS_INSUFFICIENT_RESOURCES;
571 }
572
573 cer->type = TYPE_EXTENT_DATA_REF;
574 RtlCopyMemory(&cer->edr, edr, sizeof(EXTENT_DATA_REF));
575 InsertTailList(list, &cer->list_entry);
576
577 end:
578 if (old)
579 ce->old_count += edr->count;
580 else
581 ce->count += edr->count;
582
583 return STATUS_SUCCESS;
584 }
585
586 static NTSTATUS add_changed_extent_ref_sdr(changed_extent* ce, SHARED_DATA_REF* sdr, BOOL old) {
587 LIST_ENTRY *le2, *list;
588 changed_extent_ref* cer;
589
590 list = old ? &ce->old_refs : &ce->refs;
591
592 le2 = list->Flink;
593 while (le2 != list) {
594 cer = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
595
596 if (cer->type == TYPE_SHARED_DATA_REF && cer->sdr.offset == sdr->offset) {
597 cer->sdr.count += sdr->count;
598 goto end;
599 }
600
601 le2 = le2->Flink;
602 }
603
604 cer = ExAllocatePoolWithTag(PagedPool, sizeof(changed_extent_ref), ALLOC_TAG);
605 if (!cer) {
606 ERR("out of memory\n");
607 return STATUS_INSUFFICIENT_RESOURCES;
608 }
609
610 cer->type = TYPE_SHARED_DATA_REF;
611 RtlCopyMemory(&cer->sdr, sdr, sizeof(SHARED_DATA_REF));
612 InsertTailList(list, &cer->list_entry);
613
614 end:
615 if (old)
616 ce->old_count += sdr->count;
617 else
618 ce->count += sdr->count;
619
620 return STATUS_SUCCESS;
621 }
622
623 static BOOL shared_tree_is_unique(device_extension* Vcb, tree* t, PIRP Irp) {
624 KEY searchkey;
625 traverse_ptr tp;
626 NTSTATUS Status;
627
628 searchkey.obj_id = t->header.address;
629 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
630 searchkey.offset = 0xffffffffffffffff;
631
632 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
633 if (!NT_SUCCESS(Status)) {
634 ERR("error - find_item returned %08x\n", Status);
635 return FALSE;
636 }
637
638 if (tp.item->key.obj_id == t->header.address && (tp.item->key.obj_type == TYPE_METADATA_ITEM || tp.item->key.obj_type == TYPE_EXTENT_ITEM))
639 return FALSE;
640 else
641 return TRUE;
642 }
643
644 static NTSTATUS update_tree_extents(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
645 NTSTATUS Status;
646 UINT64 rc = get_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, Irp);
647 UINT64 flags = get_extent_flags(Vcb, t->header.address, Irp);
648
649 if (rc == 0) {
650 ERR("refcount for extent %llx was 0\n", t->header.address);
651 return STATUS_INTERNAL_ERROR;
652 }
653
654 if (flags & EXTENT_ITEM_SHARED_BACKREFS || t->header.flags & HEADER_FLAG_SHARED_BACKREF || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
655 TREE_BLOCK_REF tbr;
656 BOOL unique = rc > 1 ? FALSE : (t->parent ? shared_tree_is_unique(Vcb, t->parent, Irp) : FALSE);
657
658 if (t->header.level == 0) {
659 LIST_ENTRY* le;
660
661 le = t->itemlist.Flink;
662 while (le != &t->itemlist) {
663 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
664
665 if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
666 EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
667
668 if (ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) {
669 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
670
671 if (ed2->size > 0) {
672 EXTENT_DATA_REF edr;
673 changed_extent* ce = NULL;
674 chunk* c = get_chunk_from_address(Vcb, ed2->address);
675
676 if (c) {
677 LIST_ENTRY* le2;
678
679 le2 = c->changed_extents.Flink;
680 while (le2 != &c->changed_extents) {
681 changed_extent* ce2 = CONTAINING_RECORD(le2, changed_extent, list_entry);
682
683 if (ce2->address == ed2->address) {
684 ce = ce2;
685 break;
686 }
687
688 le2 = le2->Flink;
689 }
690 }
691
692 edr.root = t->root->id;
693 edr.objid = td->key.obj_id;
694 edr.offset = td->key.offset - ed2->offset;
695 edr.count = 1;
696
697 if (ce) {
698 Status = add_changed_extent_ref_edr(ce, &edr, TRUE);
699 if (!NT_SUCCESS(Status)) {
700 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
701 return Status;
702 }
703
704 Status = add_changed_extent_ref_edr(ce, &edr, FALSE);
705 if (!NT_SUCCESS(Status)) {
706 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
707 return Status;
708 }
709 }
710
711 Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp, rollback);
712 if (!NT_SUCCESS(Status)) {
713 ERR("increase_extent_refcount returned %08x\n", Status);
714 return Status;
715 }
716
717 if ((flags & EXTENT_ITEM_SHARED_BACKREFS && unique) || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
718 UINT64 sdrrc = find_extent_shared_data_refcount(Vcb, ed2->address, t->header.address, Irp);
719
720 if (sdrrc > 0) {
721 SHARED_DATA_REF sdr;
722
723 sdr.offset = t->header.address;
724 sdr.count = sdrrc;
725
726 Status = decrease_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_SHARED_DATA_REF, &sdr, NULL, 0,
727 t->header.address, Irp, rollback);
728 if (!NT_SUCCESS(Status)) {
729 ERR("decrease_extent_refcount returned %08x\n", Status);
730 return Status;
731 }
732
733 if (ce) {
734 ce->count--;
735 ce->old_count--;
736 }
737 }
738 }
739
740 // FIXME - clear shared flag if unique?
741 }
742 }
743 }
744
745 le = le->Flink;
746 }
747 } else {
748 LIST_ENTRY* le;
749
750 le = t->itemlist.Flink;
751 while (le != &t->itemlist) {
752 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
753
754 if (!td->inserted) {
755 TREE_BLOCK_REF tbr;
756
757 tbr.offset = t->root->id;
758
759 Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF,
760 &tbr, &td->key, t->header.level - 1, Irp, rollback);
761 if (!NT_SUCCESS(Status)) {
762 ERR("increase_extent_refcount returned %08x\n", Status);
763 return Status;
764 }
765
766 if (unique || !(t->header.flags & HEADER_FLAG_MIXED_BACKREF)) {
767 UINT64 sbrrc = find_extent_shared_tree_refcount(Vcb, td->treeholder.address, t->header.address, Irp);
768
769 if (sbrrc > 0) {
770 SHARED_BLOCK_REF sbr;
771
772 sbr.offset = t->header.address;
773
774 Status = decrease_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
775 t->header.address, Irp, rollback);
776 if (!NT_SUCCESS(Status)) {
777 ERR("decrease_extent_refcount returned %08x\n", Status);
778 return Status;
779 }
780 }
781 }
782
783 // FIXME - clear shared flag if unique?
784 }
785
786 le = le->Flink;
787 }
788 }
789
790 if (unique) {
791 UINT64 sbrrc = find_extent_shared_tree_refcount(Vcb, t->header.address, t->parent->header.address, Irp);
792
793 if (sbrrc == 1) {
794 SHARED_BLOCK_REF sbr;
795
796 sbr.offset = t->parent->header.address;
797
798 Status = decrease_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, NULL, 0,
799 t->parent->header.address, Irp, rollback);
800 if (!NT_SUCCESS(Status)) {
801 ERR("decrease_extent_refcount returned %08x\n", Status);
802 return Status;
803 }
804 }
805 }
806
807 if (t->parent)
808 tbr.offset = t->parent->header.tree_id;
809 else
810 tbr.offset = t->header.tree_id;
811
812 Status = increase_extent_refcount(Vcb, t->header.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr,
813 t->parent ? &t->paritem->key : NULL, t->header.level, Irp, rollback);
814 if (!NT_SUCCESS(Status)) {
815 ERR("increase_extent_refcount returned %08x\n", Status);
816 return Status;
817 }
818
819 // FIXME - clear shared flag if unique?
820
821 t->header.flags &= ~HEADER_FLAG_SHARED_BACKREF;
822 }
823
824 Status = reduce_tree_extent(Vcb, t->header.address, t, Irp, rollback);
825
826 if (!NT_SUCCESS(Status)) {
827 ERR("reduce_tree_extent returned %08x\n", Status);
828 return Status;
829 }
830
831 t->has_address = FALSE;
832
833 if (rc > 1 && !(flags & EXTENT_ITEM_SHARED_BACKREFS)) {
834 if (t->header.tree_id == t->root->id) {
835 flags |= EXTENT_ITEM_SHARED_BACKREFS;
836 update_extent_flags(Vcb, t->header.address, flags, Irp);
837 }
838
839 if (t->header.level > 0) {
840 LIST_ENTRY* le;
841
842 le = t->itemlist.Flink;
843 while (le != &t->itemlist) {
844 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
845
846 if (!td->inserted) {
847 if (t->header.tree_id == t->root->id) {
848 SHARED_BLOCK_REF sbr;
849
850 sbr.offset = t->header.address;
851
852 Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_SHARED_BLOCK_REF, &sbr, &td->key, t->header.level - 1, Irp, rollback);
853 } else {
854 TREE_BLOCK_REF tbr;
855
856 tbr.offset = t->root->id;
857
858 Status = increase_extent_refcount(Vcb, td->treeholder.address, Vcb->superblock.node_size, TYPE_TREE_BLOCK_REF, &tbr, &td->key, t->header.level - 1, Irp, rollback);
859 }
860
861 if (!NT_SUCCESS(Status)) {
862 ERR("increase_extent_refcount returned %08x\n", Status);
863 return Status;
864 }
865 }
866
867 le = le->Flink;
868 }
869 } else {
870 LIST_ENTRY* le;
871
872 le = t->itemlist.Flink;
873 while (le != &t->itemlist) {
874 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
875
876 if (!td->inserted && td->key.obj_type == TYPE_EXTENT_DATA && td->size >= sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
877 EXTENT_DATA* ed = (EXTENT_DATA*)td->data;
878
879 if (ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) {
880 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
881
882 if (ed2->size > 0) {
883 changed_extent* ce = NULL;
884 chunk* c = get_chunk_from_address(Vcb, ed2->address);
885
886 if (c) {
887 LIST_ENTRY* le2;
888
889 le2 = c->changed_extents.Flink;
890 while (le2 != &c->changed_extents) {
891 changed_extent* ce2 = CONTAINING_RECORD(le2, changed_extent, list_entry);
892
893 if (ce2->address == ed2->address) {
894 ce = ce2;
895 break;
896 }
897
898 le2 = le2->Flink;
899 }
900 }
901
902 if (t->header.tree_id == t->root->id) {
903 SHARED_DATA_REF sdr;
904
905 sdr.offset = t->header.address;
906 sdr.count = 1;
907
908 if (ce) {
909 Status = add_changed_extent_ref_sdr(ce, &sdr, TRUE);
910 if (!NT_SUCCESS(Status)) {
911 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
912 return Status;
913 }
914
915 Status = add_changed_extent_ref_sdr(ce, &sdr, FALSE);
916 if (!NT_SUCCESS(Status)) {
917 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
918 return Status;
919 }
920 }
921
922 Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_SHARED_DATA_REF, &sdr, NULL, 0, Irp, rollback);
923 } else {
924 EXTENT_DATA_REF edr;
925
926 edr.root = t->root->id;
927 edr.objid = td->key.obj_id;
928 edr.offset = td->key.offset - ed2->offset;
929 edr.count = 1;
930
931 if (ce) {
932 Status = add_changed_extent_ref_edr(ce, &edr, TRUE);
933 if (!NT_SUCCESS(Status)) {
934 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
935 return Status;
936 }
937
938 Status = add_changed_extent_ref_edr(ce, &edr, FALSE);
939 if (!NT_SUCCESS(Status)) {
940 ERR("add_changed_extent_ref_edr returned %08x\n", Status);
941 return Status;
942 }
943 }
944
945 Status = increase_extent_refcount(Vcb, ed2->address, ed2->size, TYPE_EXTENT_DATA_REF, &edr, NULL, 0, Irp, rollback);
946 }
947
948 if (!NT_SUCCESS(Status)) {
949 ERR("increase_extent_refcount returned %08x\n", Status);
950 return Status;
951 }
952 }
953 }
954 }
955
956 le = le->Flink;
957 }
958 }
959 }
960
961 t->updated_extents = TRUE;
962 t->header.tree_id = t->root->id;
963
964 return STATUS_SUCCESS;
965 }
966
967 static NTSTATUS allocate_tree_extents(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
968 LIST_ENTRY* le;
969 NTSTATUS Status;
970 BOOL changed = FALSE;
971 UINT8 max_level = 0, level;
972
973 TRACE("(%p)\n", Vcb);
974
975 le = Vcb->trees.Flink;
976 while (le != &Vcb->trees) {
977 tree* t = CONTAINING_RECORD(le, tree, list_entry);
978
979 if (t->write && !t->has_new_address) {
980 chunk* c;
981
982 Status = get_tree_new_address(Vcb, t, Irp, rollback);
983 if (!NT_SUCCESS(Status)) {
984 ERR("get_tree_new_address returned %08x\n", Status);
985 return Status;
986 }
987
988 TRACE("allocated extent %llx\n", t->new_address);
989
990 c = get_chunk_from_address(Vcb, t->new_address);
991
992 if (c) {
993 increase_chunk_usage(c, Vcb->superblock.node_size);
994 } else {
995 ERR("could not find chunk for address %llx\n", t->new_address);
996 return STATUS_INTERNAL_ERROR;
997 }
998
999 changed = TRUE;
1000
1001 if (t->header.level > max_level)
1002 max_level = t->header.level;
1003 }
1004
1005 le = le->Flink;
1006 }
1007
1008 if (!changed)
1009 return STATUS_SUCCESS;
1010
1011 level = max_level;
1012 do {
1013 le = Vcb->trees.Flink;
1014 while (le != &Vcb->trees) {
1015 tree* t = CONTAINING_RECORD(le, tree, list_entry);
1016
1017 if (t->write && !t->updated_extents && t->has_address && t->header.level == level) {
1018 Status = update_tree_extents(Vcb, t, Irp, rollback);
1019 if (!NT_SUCCESS(Status)) {
1020 ERR("update_tree_extents returned %08x\n", Status);
1021 return Status;
1022 }
1023 }
1024
1025 le = le->Flink;
1026 }
1027
1028 if (level == 0)
1029 break;
1030
1031 level--;
1032 } while (TRUE);
1033
1034 return STATUS_SUCCESS;
1035 }
1036
1037 static NTSTATUS update_root_root(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
1038 LIST_ENTRY* le;
1039 NTSTATUS Status;
1040
1041 TRACE("(%p)\n", Vcb);
1042
1043 le = Vcb->trees.Flink;
1044 while (le != &Vcb->trees) {
1045 tree* t = CONTAINING_RECORD(le, tree, list_entry);
1046
1047 if (t->write && !t->parent) {
1048 if (t->root != Vcb->root_root && t->root != Vcb->chunk_root) {
1049 KEY searchkey;
1050 traverse_ptr tp;
1051
1052 searchkey.obj_id = t->root->id;
1053 searchkey.obj_type = TYPE_ROOT_ITEM;
1054 searchkey.offset = 0xffffffffffffffff;
1055
1056 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
1057 if (!NT_SUCCESS(Status)) {
1058 ERR("error - find_item returned %08x\n", Status);
1059 return Status;
1060 }
1061
1062 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
1063 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey.obj_id);
1064 int3;
1065 return STATUS_INTERNAL_ERROR;
1066 }
1067
1068 TRACE("updating the address for root %llx to %llx\n", searchkey.obj_id, t->new_address);
1069
1070 t->root->root_item.block_number = t->new_address;
1071 t->root->root_item.root_level = t->header.level;
1072 t->root->root_item.generation = Vcb->superblock.generation;
1073 t->root->root_item.generation2 = Vcb->superblock.generation;
1074
1075 // item is guaranteed to be at least sizeof(ROOT_ITEM), due to add_parents
1076
1077 RtlCopyMemory(tp.item->data, &t->root->root_item, sizeof(ROOT_ITEM));
1078 }
1079
1080 t->root->treeholder.address = t->new_address;
1081 }
1082
1083 le = le->Flink;
1084 }
1085
1086 Status = update_chunk_caches(Vcb, Irp, rollback);
1087 if (!NT_SUCCESS(Status)) {
1088 ERR("update_chunk_caches returned %08x\n", Status);
1089 return Status;
1090 }
1091
1092 return STATUS_SUCCESS;
1093 }
1094
1095 static NTSTATUS write_trees(device_extension* Vcb, PIRP Irp) {
1096 UINT8 level;
1097 UINT8 *data, *body;
1098 UINT32 crc32;
1099 NTSTATUS Status;
1100 LIST_ENTRY* le;
1101 write_data_context* wtc;
1102 LIST_ENTRY tree_writes;
1103 tree_write* tw;
1104 chunk* c;
1105
1106 TRACE("(%p)\n", Vcb);
1107
1108 InitializeListHead(&tree_writes);
1109
1110 for (level = 0; level <= 255; level++) {
1111 BOOL nothing_found = TRUE;
1112
1113 TRACE("level = %u\n", level);
1114
1115 le = Vcb->trees.Flink;
1116 while (le != &Vcb->trees) {
1117 tree* t = CONTAINING_RECORD(le, tree, list_entry);
1118
1119 if (t->write && t->header.level == level) {
1120 KEY firstitem, searchkey;
1121 LIST_ENTRY* le2;
1122 traverse_ptr tp;
1123 EXTENT_ITEM_TREE* eit;
1124
1125 if (!t->has_new_address) {
1126 ERR("error - tried to write tree with no new address\n");
1127 int3;
1128 }
1129
1130 le2 = t->itemlist.Flink;
1131 while (le2 != &t->itemlist) {
1132 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1133 if (!td->ignore) {
1134 firstitem = td->key;
1135 break;
1136 }
1137 le2 = le2->Flink;
1138 }
1139
1140 if (t->parent) {
1141 t->paritem->key = firstitem;
1142 t->paritem->treeholder.address = t->new_address;
1143 t->paritem->treeholder.generation = Vcb->superblock.generation;
1144 }
1145
1146 if (!(Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA)) {
1147 searchkey.obj_id = t->new_address;
1148 searchkey.obj_type = TYPE_EXTENT_ITEM;
1149 searchkey.offset = Vcb->superblock.node_size;
1150
1151 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1152 if (!NT_SUCCESS(Status)) {
1153 ERR("error - find_item returned %08x\n", Status);
1154 return Status;
1155 }
1156
1157 if (keycmp(searchkey, tp.item->key)) {
1158 // traverse_ptr next_tp;
1159 // BOOL b;
1160 // tree_data* paritem;
1161
1162 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);
1163
1164 // searchkey.obj_id = 0;
1165 // searchkey.obj_type = 0;
1166 // searchkey.offset = 0;
1167 //
1168 // find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE);
1169 //
1170 // paritem = NULL;
1171 // do {
1172 // if (tp.tree->paritem != paritem) {
1173 // paritem = tp.tree->paritem;
1174 // ERR("paritem: %llx,%x,%llx\n", paritem->key.obj_id, paritem->key.obj_type, paritem->key.offset);
1175 // }
1176 //
1177 // ERR("%llx,%x,%llx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
1178 //
1179 // b = find_next_item(Vcb, &tp, &next_tp, NULL, FALSE);
1180 // if (b) {
1181 // free_traverse_ptr(&tp);
1182 // tp = next_tp;
1183 // }
1184 // } while (b);
1185 //
1186 // free_traverse_ptr(&tp);
1187
1188 return STATUS_INTERNAL_ERROR;
1189 }
1190
1191 if (tp.item->size < sizeof(EXTENT_ITEM_TREE)) {
1192 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));
1193 return STATUS_INTERNAL_ERROR;
1194 }
1195
1196 eit = (EXTENT_ITEM_TREE*)tp.item->data;
1197 eit->firstitem = firstitem;
1198 }
1199
1200 nothing_found = FALSE;
1201 }
1202
1203 le = le->Flink;
1204 }
1205
1206 if (nothing_found)
1207 break;
1208 }
1209
1210 TRACE("allocated tree extents\n");
1211
1212 wtc = ExAllocatePoolWithTag(NonPagedPool, sizeof(write_data_context), ALLOC_TAG);
1213 if (!wtc) {
1214 ERR("out of memory\n");
1215 return STATUS_INSUFFICIENT_RESOURCES;
1216 }
1217
1218 KeInitializeEvent(&wtc->Event, NotificationEvent, FALSE);
1219 InitializeListHead(&wtc->stripes);
1220 wtc->tree = TRUE;
1221 wtc->stripes_left = 0;
1222
1223 le = Vcb->trees.Flink;
1224 while (le != &Vcb->trees) {
1225 tree* t = CONTAINING_RECORD(le, tree, list_entry);
1226 #ifdef DEBUG_PARANOID
1227 UINT32 num_items = 0, size = 0;
1228 LIST_ENTRY* le2;
1229 BOOL crash = FALSE;
1230 #endif
1231
1232 if (t->write) {
1233 #ifdef DEBUG_PARANOID
1234 le2 = t->itemlist.Flink;
1235 while (le2 != &t->itemlist) {
1236 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1237 if (!td->ignore) {
1238 num_items++;
1239
1240 if (t->header.level == 0)
1241 size += td->size;
1242 }
1243 le2 = le2->Flink;
1244 }
1245
1246 if (t->header.level == 0)
1247 size += num_items * sizeof(leaf_node);
1248 else
1249 size += num_items * sizeof(internal_node);
1250
1251 if (num_items != t->header.num_items) {
1252 ERR("tree %llx, level %x: num_items was %x, expected %x\n", t->root->id, t->header.level, num_items, t->header.num_items);
1253 crash = TRUE;
1254 }
1255
1256 if (size != t->size) {
1257 ERR("tree %llx, level %x: size was %x, expected %x\n", t->root->id, t->header.level, size, t->size);
1258 crash = TRUE;
1259 }
1260
1261 if (t->header.num_items == 0 && t->parent) {
1262 ERR("tree %llx, level %x: tried to write empty tree with parent\n", t->root->id, t->header.level);
1263 crash = TRUE;
1264 }
1265
1266 if (t->size > Vcb->superblock.node_size - sizeof(tree_header)) {
1267 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));
1268 crash = TRUE;
1269 }
1270
1271 if (crash) {
1272 ERR("tree %p\n", t);
1273 le2 = t->itemlist.Flink;
1274 while (le2 != &t->itemlist) {
1275 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1276 if (!td->ignore) {
1277 ERR("%llx,%x,%llx inserted=%u\n", td->key.obj_id, td->key.obj_type, td->key.offset, td->inserted);
1278 }
1279 le2 = le2->Flink;
1280 }
1281 int3;
1282 }
1283 #endif
1284 t->header.address = t->new_address;
1285 t->header.generation = Vcb->superblock.generation;
1286 t->header.tree_id = t->root->id;
1287 t->header.flags |= HEADER_FLAG_MIXED_BACKREF;
1288 t->header.fs_uuid = Vcb->superblock.uuid;
1289 t->has_address = TRUE;
1290
1291 data = ExAllocatePoolWithTag(NonPagedPool, Vcb->superblock.node_size, ALLOC_TAG);
1292 if (!data) {
1293 ERR("out of memory\n");
1294 Status = STATUS_INSUFFICIENT_RESOURCES;
1295 goto end;
1296 }
1297
1298 body = data + sizeof(tree_header);
1299
1300 RtlCopyMemory(data, &t->header, sizeof(tree_header));
1301 RtlZeroMemory(body, Vcb->superblock.node_size - sizeof(tree_header));
1302
1303 if (t->header.level == 0) {
1304 leaf_node* itemptr = (leaf_node*)body;
1305 int i = 0;
1306 LIST_ENTRY* le2;
1307 UINT8* dataptr = data + Vcb->superblock.node_size;
1308
1309 le2 = t->itemlist.Flink;
1310 while (le2 != &t->itemlist) {
1311 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1312 if (!td->ignore) {
1313 dataptr = dataptr - td->size;
1314
1315 itemptr[i].key = td->key;
1316 itemptr[i].offset = (UINT8*)dataptr - (UINT8*)body;
1317 itemptr[i].size = td->size;
1318 i++;
1319
1320 if (td->size > 0)
1321 RtlCopyMemory(dataptr, td->data, td->size);
1322 }
1323
1324 le2 = le2->Flink;
1325 }
1326 } else {
1327 internal_node* itemptr = (internal_node*)body;
1328 int i = 0;
1329 LIST_ENTRY* le2;
1330
1331 le2 = t->itemlist.Flink;
1332 while (le2 != &t->itemlist) {
1333 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
1334 if (!td->ignore) {
1335 itemptr[i].key = td->key;
1336 itemptr[i].address = td->treeholder.address;
1337 itemptr[i].generation = td->treeholder.generation;
1338 i++;
1339 }
1340
1341 le2 = le2->Flink;
1342 }
1343 }
1344
1345 crc32 = calc_crc32c(0xffffffff, (UINT8*)&((tree_header*)data)->fs_uuid, Vcb->superblock.node_size - sizeof(((tree_header*)data)->csum));
1346 crc32 = ~crc32;
1347 *((UINT32*)data) = crc32;
1348 TRACE("setting crc32 to %08x\n", crc32);
1349
1350 tw = ExAllocatePoolWithTag(PagedPool, sizeof(tree_write), ALLOC_TAG);
1351 if (!tw) {
1352 ERR("out of memory\n");
1353 return STATUS_INSUFFICIENT_RESOURCES;
1354 }
1355
1356 tw->address = t->new_address;
1357 tw->length = Vcb->superblock.node_size;
1358 tw->data = data;
1359 tw->overlap = FALSE;
1360
1361 if (IsListEmpty(&tree_writes))
1362 InsertTailList(&tree_writes, &tw->list_entry);
1363 else {
1364 LIST_ENTRY* le2;
1365 BOOL inserted = FALSE;
1366
1367 le2 = tree_writes.Flink;
1368 while (le2 != &tree_writes) {
1369 tree_write* tw2 = CONTAINING_RECORD(le2, tree_write, list_entry);
1370
1371 if (tw2->address > tw->address) {
1372 InsertHeadList(le2->Blink, &tw->list_entry);
1373 inserted = TRUE;
1374 break;
1375 }
1376
1377 le2 = le2->Flink;
1378 }
1379
1380 if (!inserted)
1381 InsertTailList(&tree_writes, &tw->list_entry);
1382 }
1383 }
1384
1385 le = le->Flink;
1386 }
1387
1388 Status = STATUS_SUCCESS;
1389
1390 // merge together runs
1391 c = NULL;
1392 le = tree_writes.Flink;
1393 while (le != &tree_writes) {
1394 tw = CONTAINING_RECORD(le, tree_write, list_entry);
1395
1396 if (!c || tw->address < c->offset || tw->address >= c->offset + c->chunk_item->size)
1397 c = get_chunk_from_address(Vcb, tw->address);
1398 else {
1399 tree_write* tw2 = CONTAINING_RECORD(le->Blink, tree_write, list_entry);
1400
1401 if (tw->address == tw2->address + tw2->length) {
1402 data = ExAllocatePoolWithTag(NonPagedPool, tw2->length + tw->length, ALLOC_TAG);
1403
1404 if (!data) {
1405 ERR("out of memory\n");
1406 Status = STATUS_INSUFFICIENT_RESOURCES;
1407 goto end;
1408 }
1409
1410 RtlCopyMemory(data, tw2->data, tw2->length);
1411 RtlCopyMemory(&data[tw2->length], tw->data, tw->length);
1412
1413 ExFreePool(tw2->data);
1414 tw2->data = data;
1415 tw2->length += tw->length;
1416
1417 ExFreePool(tw->data);
1418 RemoveEntryList(&tw->list_entry);
1419 ExFreePool(tw);
1420
1421 le = tw2->list_entry.Flink;
1422 continue;
1423 }
1424 }
1425
1426 le = le->Flink;
1427 }
1428
1429 // mark RAID5/6 overlaps so we can do them one by one
1430 c = NULL;
1431 le = tree_writes.Flink;
1432 while (le != &tree_writes) {
1433 tw = CONTAINING_RECORD(le, tree_write, list_entry);
1434
1435 if (!c || tw->address < c->offset || tw->address >= c->offset + c->chunk_item->size)
1436 c = get_chunk_from_address(Vcb, tw->address);
1437 else if (c->chunk_item->type & BLOCK_FLAG_RAID5) {
1438 tree_write* tw2 = CONTAINING_RECORD(le->Blink, tree_write, list_entry);
1439 UINT64 last_stripe, this_stripe;
1440
1441 last_stripe = (tw2->address + tw2->length - 1 - c->offset) / (c->chunk_item->stripe_length * (c->chunk_item->num_stripes - 1));
1442 this_stripe = (tw->address - c->offset) / (c->chunk_item->stripe_length * (c->chunk_item->num_stripes - 1));
1443
1444 if (last_stripe == this_stripe)
1445 tw->overlap = TRUE;
1446 } else if (c->chunk_item->type & BLOCK_FLAG_RAID6) {
1447 tree_write* tw2 = CONTAINING_RECORD(le->Blink, tree_write, list_entry);
1448 UINT64 last_stripe, this_stripe;
1449
1450 last_stripe = (tw2->address + tw2->length - 1 - c->offset) / (c->chunk_item->stripe_length * (c->chunk_item->num_stripes - 2));
1451 this_stripe = (tw->address - c->offset) / (c->chunk_item->stripe_length * (c->chunk_item->num_stripes - 2));
1452
1453 if (last_stripe == this_stripe)
1454 tw->overlap = TRUE;
1455 }
1456
1457 le = le->Flink;
1458 }
1459
1460 le = tree_writes.Flink;
1461 while (le != &tree_writes) {
1462 tw = CONTAINING_RECORD(le, tree_write, list_entry);
1463
1464 if (!tw->overlap) {
1465 TRACE("address: %llx, size: %x, overlap = %u\n", tw->address, tw->length, tw->overlap);
1466
1467 Status = write_data(Vcb, tw->address, tw->data, TRUE, tw->length, wtc, NULL, NULL);
1468 if (!NT_SUCCESS(Status)) {
1469 ERR("write_data returned %08x\n", Status);
1470 goto end;
1471 }
1472 }
1473
1474 le = le->Flink;
1475 }
1476
1477 if (wtc->stripes.Flink != &wtc->stripes) {
1478 // launch writes and wait
1479 le = wtc->stripes.Flink;
1480 while (le != &wtc->stripes) {
1481 write_data_stripe* stripe = CONTAINING_RECORD(le, write_data_stripe, list_entry);
1482
1483 if (stripe->status != WriteDataStatus_Ignore)
1484 IoCallDriver(stripe->device->devobj, stripe->Irp);
1485
1486 le = le->Flink;
1487 }
1488
1489 KeWaitForSingleObject(&wtc->Event, Executive, KernelMode, FALSE, NULL);
1490
1491 le = wtc->stripes.Flink;
1492 while (le != &wtc->stripes) {
1493 write_data_stripe* stripe = CONTAINING_RECORD(le, write_data_stripe, list_entry);
1494
1495 if (stripe->status != WriteDataStatus_Ignore && !NT_SUCCESS(stripe->iosb.Status)) {
1496 Status = stripe->iosb.Status;
1497 break;
1498 }
1499
1500 le = le->Flink;
1501 }
1502
1503 free_write_data_stripes(wtc);
1504 }
1505
1506 le = tree_writes.Flink;
1507 while (le != &tree_writes) {
1508 tw = CONTAINING_RECORD(le, tree_write, list_entry);
1509
1510 if (tw->overlap) {
1511 TRACE("address: %llx, size: %x, overlap = %u\n", tw->address, tw->length, tw->overlap);
1512
1513 Status = write_data_complete(Vcb, tw->address, tw->data, tw->length, Irp, NULL);
1514 if (!NT_SUCCESS(Status)) {
1515 ERR("write_data_complete returned %08x\n", Status);
1516 goto end;
1517 }
1518 }
1519
1520 le = le->Flink;
1521 }
1522
1523 end:
1524 ExFreePool(wtc);
1525
1526 while (!IsListEmpty(&tree_writes)) {
1527 le = RemoveHeadList(&tree_writes);
1528 tw = CONTAINING_RECORD(le, tree_write, list_entry);
1529
1530 ExFreePool(tw);
1531 }
1532
1533 return Status;
1534 }
1535
1536 static void update_backup_superblock(device_extension* Vcb, superblock_backup* sb, PIRP Irp) {
1537 KEY searchkey;
1538 traverse_ptr tp;
1539
1540 RtlZeroMemory(sb, sizeof(superblock_backup));
1541
1542 sb->root_tree_addr = Vcb->superblock.root_tree_addr;
1543 sb->root_tree_generation = Vcb->superblock.generation;
1544 sb->root_level = Vcb->superblock.root_level;
1545
1546 sb->chunk_tree_addr = Vcb->superblock.chunk_tree_addr;
1547 sb->chunk_tree_generation = Vcb->superblock.chunk_root_generation;
1548 sb->chunk_root_level = Vcb->superblock.chunk_root_level;
1549
1550 searchkey.obj_id = BTRFS_ROOT_EXTENT;
1551 searchkey.obj_type = TYPE_ROOT_ITEM;
1552 searchkey.offset = 0xffffffffffffffff;
1553
1554 if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp))) {
1555 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
1556 ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
1557
1558 sb->extent_tree_addr = ri->block_number;
1559 sb->extent_tree_generation = ri->generation;
1560 sb->extent_root_level = ri->root_level;
1561 }
1562 }
1563
1564 searchkey.obj_id = BTRFS_ROOT_FSTREE;
1565
1566 if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp))) {
1567 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
1568 ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
1569
1570 sb->fs_tree_addr = ri->block_number;
1571 sb->fs_tree_generation = ri->generation;
1572 sb->fs_root_level = ri->root_level;
1573 }
1574 }
1575
1576 searchkey.obj_id = BTRFS_ROOT_DEVTREE;
1577
1578 if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp))) {
1579 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
1580 ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
1581
1582 sb->dev_root_addr = ri->block_number;
1583 sb->dev_root_generation = ri->generation;
1584 sb->dev_root_level = ri->root_level;
1585 }
1586 }
1587
1588 searchkey.obj_id = BTRFS_ROOT_CHECKSUM;
1589
1590 if (NT_SUCCESS(find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp))) {
1591 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type && tp.item->size >= sizeof(ROOT_ITEM)) {
1592 ROOT_ITEM* ri = (ROOT_ITEM*)tp.item->data;
1593
1594 sb->csum_root_addr = ri->block_number;
1595 sb->csum_root_generation = ri->generation;
1596 sb->csum_root_level = ri->root_level;
1597 }
1598 }
1599
1600 sb->total_bytes = Vcb->superblock.total_bytes;
1601 sb->bytes_used = Vcb->superblock.bytes_used;
1602 sb->num_devices = Vcb->superblock.num_devices;
1603 }
1604
1605 static NTSTATUS STDCALL write_superblock(device_extension* Vcb, device* device) {
1606 NTSTATUS Status;
1607 unsigned int i = 0;
1608 UINT32 crc32;
1609 #ifdef __REACTOS__
1610 Status = STATUS_INTERNAL_ERROR;
1611 #endif
1612
1613 RtlCopyMemory(&Vcb->superblock.dev_item, &device->devitem, sizeof(DEV_ITEM));
1614
1615 // All the documentation says that the Linux driver only writes one superblock
1616 // if it thinks a disk is an SSD, but this doesn't seem to be the case!
1617
1618 while (superblock_addrs[i] > 0 && device->length >= superblock_addrs[i] + sizeof(superblock)) {
1619 TRACE("writing superblock %u\n", i);
1620
1621 Vcb->superblock.sb_phys_addr = superblock_addrs[i];
1622
1623 crc32 = calc_crc32c(0xffffffff, (UINT8*)&Vcb->superblock.uuid, (ULONG)sizeof(superblock) - sizeof(Vcb->superblock.checksum));
1624 crc32 = ~crc32;
1625 TRACE("crc32 is %08x\n", crc32);
1626 RtlCopyMemory(&Vcb->superblock.checksum, &crc32, sizeof(UINT32));
1627
1628 Status = write_data_phys(device->devobj, superblock_addrs[i], &Vcb->superblock, sizeof(superblock));
1629
1630 if (!NT_SUCCESS(Status))
1631 break;
1632
1633 i++;
1634 }
1635
1636 if (i == 0) {
1637 ERR("no superblocks written!\n");
1638 }
1639
1640 return Status;
1641 }
1642
1643 static NTSTATUS write_superblocks(device_extension* Vcb, PIRP Irp) {
1644 UINT64 i;
1645 NTSTATUS Status;
1646 LIST_ENTRY* le;
1647
1648 TRACE("(%p)\n", Vcb);
1649
1650 le = Vcb->trees.Flink;
1651 while (le != &Vcb->trees) {
1652 tree* t = CONTAINING_RECORD(le, tree, list_entry);
1653
1654 if (t->write && !t->parent) {
1655 if (t->root == Vcb->root_root) {
1656 Vcb->superblock.root_tree_addr = t->new_address;
1657 Vcb->superblock.root_level = t->header.level;
1658 } else if (t->root == Vcb->chunk_root) {
1659 Vcb->superblock.chunk_tree_addr = t->new_address;
1660 Vcb->superblock.chunk_root_generation = t->header.generation;
1661 Vcb->superblock.chunk_root_level = t->header.level;
1662 }
1663 }
1664
1665 le = le->Flink;
1666 }
1667
1668 for (i = 0; i < BTRFS_NUM_BACKUP_ROOTS - 1; i++) {
1669 RtlCopyMemory(&Vcb->superblock.backup[i], &Vcb->superblock.backup[i+1], sizeof(superblock_backup));
1670 }
1671
1672 update_backup_superblock(Vcb, &Vcb->superblock.backup[BTRFS_NUM_BACKUP_ROOTS - 1], Irp);
1673
1674 for (i = 0; i < Vcb->superblock.num_devices; i++) {
1675 if (Vcb->devices[i].devobj && !Vcb->devices[i].readonly) {
1676 Status = write_superblock(Vcb, &Vcb->devices[i]);
1677 if (!NT_SUCCESS(Status)) {
1678 ERR("write_superblock returned %08x\n", Status);
1679 return Status;
1680 }
1681 }
1682 }
1683
1684 return STATUS_SUCCESS;
1685 }
1686
1687 static NTSTATUS flush_changed_extent(device_extension* Vcb, chunk* c, changed_extent* ce, PIRP Irp, LIST_ENTRY* rollback) {
1688 LIST_ENTRY *le, *le2;
1689 NTSTATUS Status;
1690 UINT64 old_size;
1691
1692 le = ce->refs.Flink;
1693 while (le != &ce->refs) {
1694 changed_extent_ref* cer = CONTAINING_RECORD(le, changed_extent_ref, list_entry);
1695 LIST_ENTRY* le3 = le->Flink;
1696 UINT64 old_count = 0;
1697
1698 if (cer->type == TYPE_EXTENT_DATA_REF) {
1699 le2 = ce->old_refs.Flink;
1700 while (le2 != &ce->old_refs) {
1701 changed_extent_ref* cer2 = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
1702
1703 if (cer2->type == TYPE_EXTENT_DATA_REF && cer2->edr.root == cer->edr.root && cer2->edr.objid == cer->edr.objid && cer2->edr.offset == cer->edr.offset) {
1704 old_count = cer2->edr.count;
1705
1706 RemoveEntryList(&cer2->list_entry);
1707 ExFreePool(cer2);
1708 break;
1709 }
1710
1711 le2 = le2->Flink;
1712 }
1713
1714 old_size = ce->old_count > 0 ? ce->old_size : ce->size;
1715
1716 if (cer->edr.count > old_count) {
1717 Status = increase_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset, cer->edr.count - old_count, Irp, rollback);
1718
1719 if (!NT_SUCCESS(Status)) {
1720 ERR("increase_extent_refcount_data returned %08x\n", Status);
1721 return Status;
1722 }
1723 } else if (cer->edr.count < old_count) {
1724 Status = decrease_extent_refcount_data(Vcb, ce->address, old_size, cer->edr.root, cer->edr.objid, cer->edr.offset,
1725 old_count - cer->edr.count, Irp, rollback);
1726
1727 if (!NT_SUCCESS(Status)) {
1728 ERR("decrease_extent_refcount_data returned %08x\n", Status);
1729 return Status;
1730 }
1731 }
1732
1733 if (ce->size != ce->old_size && ce->old_count > 0) {
1734 KEY searchkey;
1735 traverse_ptr tp;
1736 void* data;
1737
1738 searchkey.obj_id = ce->address;
1739 searchkey.obj_type = TYPE_EXTENT_ITEM;
1740 searchkey.offset = ce->old_size;
1741
1742 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
1743 if (!NT_SUCCESS(Status)) {
1744 ERR("error - find_item returned %08x\n", Status);
1745 return Status;
1746 }
1747
1748 if (keycmp(searchkey, tp.item->key)) {
1749 ERR("could not find (%llx,%x,%llx) in extent tree\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
1750 return STATUS_INTERNAL_ERROR;
1751 }
1752
1753 if (tp.item->size > 0) {
1754 data = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
1755
1756 if (!data) {
1757 ERR("out of memory\n");
1758 return STATUS_INSUFFICIENT_RESOURCES;
1759 }
1760
1761 RtlCopyMemory(data, tp.item->data, tp.item->size);
1762 } else
1763 data = NULL;
1764
1765 if (!insert_tree_item(Vcb, Vcb->extent_root, ce->address, TYPE_EXTENT_ITEM, ce->size, data, tp.item->size, NULL, Irp, rollback)) {
1766 ERR("insert_tree_item failed\n");
1767 return STATUS_INTERNAL_ERROR;
1768 }
1769
1770 delete_tree_item(Vcb, &tp, rollback);
1771 }
1772 } else if (cer->type == TYPE_SHARED_DATA_REF) {
1773 le2 = ce->old_refs.Flink;
1774 while (le2 != &ce->old_refs) {
1775 changed_extent_ref* cer2 = CONTAINING_RECORD(le2, changed_extent_ref, list_entry);
1776
1777 if (cer2->type == TYPE_SHARED_DATA_REF && cer2->sdr.offset == cer->sdr.offset) {
1778 // old_count = cer2->edr.count;
1779
1780 RemoveEntryList(&cer2->list_entry);
1781 ExFreePool(cer2);
1782 break;
1783 }
1784
1785 le2 = le2->Flink;
1786 }
1787 }
1788
1789 RemoveEntryList(&cer->list_entry);
1790 ExFreePool(cer);
1791
1792 le = le3;
1793 }
1794
1795 #ifdef DEBUG_PARANOID
1796 if (!IsListEmpty(&ce->old_refs))
1797 WARN("old_refs not empty\n");
1798 #endif
1799
1800 if (ce->count == 0 && !ce->superseded) {
1801 if (!ce->no_csum) {
1802 LIST_ENTRY changed_sector_list;
1803
1804 changed_sector* sc = ExAllocatePoolWithTag(PagedPool, sizeof(changed_sector), ALLOC_TAG);
1805 if (!sc) {
1806 ERR("out of memory\n");
1807 return STATUS_INSUFFICIENT_RESOURCES;
1808 }
1809
1810 sc->ol.key = ce->address;
1811 sc->checksums = NULL;
1812 sc->length = ce->size / Vcb->superblock.sector_size;
1813
1814 sc->deleted = TRUE;
1815
1816 InitializeListHead(&changed_sector_list);
1817 insert_into_ordered_list(&changed_sector_list, &sc->ol);
1818
1819 ExAcquireResourceExclusiveLite(&Vcb->checksum_lock, TRUE);
1820 commit_checksum_changes(Vcb, &changed_sector_list);
1821 ExReleaseResourceLite(&Vcb->checksum_lock);
1822 }
1823
1824 decrease_chunk_usage(c, ce->size);
1825
1826 space_list_add(Vcb, c, TRUE, ce->address, ce->size, rollback);
1827 }
1828
1829 RemoveEntryList(&ce->list_entry);
1830 ExFreePool(ce);
1831
1832 return STATUS_SUCCESS;
1833 }
1834
1835 static void update_checksum_tree(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
1836 LIST_ENTRY* le = Vcb->sector_checksums.Flink;
1837 changed_sector* cs;
1838 traverse_ptr tp, next_tp;
1839 KEY searchkey;
1840 UINT32* data;
1841 NTSTATUS Status;
1842
1843 if (!Vcb->checksum_root) {
1844 ERR("no checksum root\n");
1845 goto exit;
1846 }
1847
1848 while (le != &Vcb->sector_checksums) {
1849 UINT64 startaddr, endaddr;
1850 ULONG len;
1851 UINT32* checksums;
1852 RTL_BITMAP bmp;
1853 ULONG* bmparr;
1854 ULONG runlength, index;
1855
1856 cs = (changed_sector*)le;
1857
1858 searchkey.obj_id = EXTENT_CSUM_ID;
1859 searchkey.obj_type = TYPE_EXTENT_CSUM;
1860 searchkey.offset = cs->ol.key;
1861
1862 // FIXME - create checksum_root if it doesn't exist at all
1863
1864 Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, FALSE, Irp);
1865 if (Status == STATUS_NOT_FOUND) { // tree is completely empty
1866 if (!cs->deleted) {
1867 checksums = ExAllocatePoolWithTag(PagedPool, sizeof(UINT32) * cs->length, ALLOC_TAG);
1868 if (!checksums) {
1869 ERR("out of memory\n");
1870 goto exit;
1871 }
1872
1873 RtlCopyMemory(checksums, cs->checksums, sizeof(UINT32) * cs->length);
1874
1875 if (!insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, cs->ol.key, checksums, sizeof(UINT32) * cs->length, NULL, Irp, rollback)) {
1876 ERR("insert_tree_item failed\n");
1877 ExFreePool(checksums);
1878 goto exit;
1879 }
1880 }
1881 } else if (!NT_SUCCESS(Status)) {
1882 ERR("find_item returned %08x\n", Status);
1883 goto exit;
1884 } else {
1885 UINT32 tplen;
1886
1887 // FIXME - check entry is TYPE_EXTENT_CSUM?
1888
1889 if (tp.item->key.offset < cs->ol.key && tp.item->key.offset + (tp.item->size * Vcb->superblock.sector_size / sizeof(UINT32)) >= cs->ol.key)
1890 startaddr = tp.item->key.offset;
1891 else
1892 startaddr = cs->ol.key;
1893
1894 searchkey.obj_id = EXTENT_CSUM_ID;
1895 searchkey.obj_type = TYPE_EXTENT_CSUM;
1896 searchkey.offset = cs->ol.key + (cs->length * Vcb->superblock.sector_size);
1897
1898 Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, FALSE, Irp);
1899 if (!NT_SUCCESS(Status)) {
1900 ERR("error - find_item returned %08x\n", Status);
1901 goto exit;
1902 }
1903
1904 tplen = tp.item->size / sizeof(UINT32);
1905
1906 if (tp.item->key.offset + (tplen * Vcb->superblock.sector_size) >= cs->ol.key + (cs->length * Vcb->superblock.sector_size))
1907 endaddr = tp.item->key.offset + (tplen * Vcb->superblock.sector_size);
1908 else
1909 endaddr = cs->ol.key + (cs->length * Vcb->superblock.sector_size);
1910
1911 TRACE("cs starts at %llx (%x sectors)\n", cs->ol.key, cs->length);
1912 TRACE("startaddr = %llx\n", startaddr);
1913 TRACE("endaddr = %llx\n", endaddr);
1914
1915 len = (endaddr - startaddr) / Vcb->superblock.sector_size;
1916
1917 checksums = ExAllocatePoolWithTag(PagedPool, sizeof(UINT32) * len, ALLOC_TAG);
1918 if (!checksums) {
1919 ERR("out of memory\n");
1920 goto exit;
1921 }
1922
1923 bmparr = ExAllocatePoolWithTag(PagedPool, sizeof(ULONG) * ((len/8)+1), ALLOC_TAG);
1924 if (!bmparr) {
1925 ERR("out of memory\n");
1926 ExFreePool(checksums);
1927 goto exit;
1928 }
1929
1930 RtlInitializeBitMap(&bmp, bmparr, len);
1931 RtlSetAllBits(&bmp);
1932
1933 searchkey.obj_id = EXTENT_CSUM_ID;
1934 searchkey.obj_type = TYPE_EXTENT_CSUM;
1935 searchkey.offset = cs->ol.key;
1936
1937 Status = find_item(Vcb, Vcb->checksum_root, &tp, &searchkey, FALSE, Irp);
1938 if (!NT_SUCCESS(Status)) {
1939 ERR("error - find_item returned %08x\n", Status);
1940 goto exit;
1941 }
1942
1943 // set bit = free space, cleared bit = allocated sector
1944
1945 // ERR("start loop\n");
1946 while (tp.item->key.offset < endaddr) {
1947 // ERR("%llx,%x,%llx\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
1948 if (tp.item->key.offset >= startaddr) {
1949 if (tp.item->size > 0) {
1950 RtlCopyMemory(&checksums[(tp.item->key.offset - startaddr) / Vcb->superblock.sector_size], tp.item->data, tp.item->size);
1951 RtlClearBits(&bmp, (tp.item->key.offset - startaddr) / Vcb->superblock.sector_size, tp.item->size / sizeof(UINT32));
1952 }
1953
1954 delete_tree_item(Vcb, &tp, rollback);
1955 }
1956
1957 if (find_next_item(Vcb, &tp, &next_tp, FALSE, Irp)) {
1958 tp = next_tp;
1959 } else
1960 break;
1961 }
1962 // ERR("end loop\n");
1963
1964 if (cs->deleted) {
1965 RtlSetBits(&bmp, (cs->ol.key - startaddr) / Vcb->superblock.sector_size, cs->length);
1966 } else {
1967 RtlCopyMemory(&checksums[(cs->ol.key - startaddr) / Vcb->superblock.sector_size], cs->checksums, cs->length * sizeof(UINT32));
1968 RtlClearBits(&bmp, (cs->ol.key - startaddr) / Vcb->superblock.sector_size, cs->length);
1969 }
1970
1971 runlength = RtlFindFirstRunClear(&bmp, &index);
1972
1973 while (runlength != 0) {
1974 do {
1975 ULONG rl;
1976 UINT64 off;
1977
1978 if (runlength * sizeof(UINT32) > MAX_CSUM_SIZE)
1979 rl = MAX_CSUM_SIZE / sizeof(UINT32);
1980 else
1981 rl = runlength;
1982
1983 data = ExAllocatePoolWithTag(PagedPool, sizeof(UINT32) * rl, ALLOC_TAG);
1984 if (!data) {
1985 ERR("out of memory\n");
1986 ExFreePool(bmparr);
1987 ExFreePool(checksums);
1988 goto exit;
1989 }
1990
1991 RtlCopyMemory(data, &checksums[index], sizeof(UINT32) * rl);
1992
1993 off = startaddr + UInt32x32To64(index, Vcb->superblock.sector_size);
1994
1995 if (!insert_tree_item(Vcb, Vcb->checksum_root, EXTENT_CSUM_ID, TYPE_EXTENT_CSUM, off, data, sizeof(UINT32) * rl, NULL, Irp, rollback)) {
1996 ERR("insert_tree_item failed\n");
1997 ExFreePool(data);
1998 ExFreePool(bmparr);
1999 ExFreePool(checksums);
2000 goto exit;
2001 }
2002
2003 runlength -= rl;
2004 index += rl;
2005 } while (runlength > 0);
2006
2007 runlength = RtlFindNextForwardRunClear(&bmp, index, &index);
2008 }
2009
2010 ExFreePool(bmparr);
2011 ExFreePool(checksums);
2012 }
2013
2014 le = le->Flink;
2015 }
2016
2017 exit:
2018 while (!IsListEmpty(&Vcb->sector_checksums)) {
2019 le = RemoveHeadList(&Vcb->sector_checksums);
2020 cs = (changed_sector*)le;
2021
2022 if (cs->checksums)
2023 ExFreePool(cs->checksums);
2024
2025 ExFreePool(cs);
2026 }
2027 }
2028
2029 static NTSTATUS update_chunk_usage(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
2030 LIST_ENTRY *le = Vcb->chunks.Flink, *le2;
2031 chunk* c;
2032 KEY searchkey;
2033 traverse_ptr tp;
2034 BLOCK_GROUP_ITEM* bgi;
2035 NTSTATUS Status;
2036 BOOL flushed_extents = FALSE;
2037
2038 TRACE("(%p)\n", Vcb);
2039
2040 ExAcquireResourceSharedLite(&Vcb->chunk_lock, TRUE);
2041
2042 while (le != &Vcb->chunks) {
2043 c = CONTAINING_RECORD(le, chunk, list_entry);
2044
2045 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
2046
2047 le2 = c->changed_extents.Flink;
2048 while (le2 != &c->changed_extents) {
2049 LIST_ENTRY* le3 = le2->Flink;
2050 changed_extent* ce = CONTAINING_RECORD(le2, changed_extent, list_entry);
2051
2052 Status = flush_changed_extent(Vcb, c, ce, Irp, rollback);
2053 if (!NT_SUCCESS(Status)) {
2054 ERR("flush_changed_extent returned %08x\n", Status);
2055 ExReleaseResourceLite(&c->lock);
2056 goto end;
2057 }
2058
2059 flushed_extents = TRUE;
2060
2061 le2 = le3;
2062 }
2063
2064 // This is usually done by update_chunks, but we have to check again in case any new chunks
2065 // have been allocated since.
2066 if (c->created) {
2067 Status = create_chunk(Vcb, c, Irp, rollback);
2068 if (!NT_SUCCESS(Status)) {
2069 ERR("create_chunk returned %08x\n", Status);
2070 ExReleaseResourceLite(&c->lock);
2071 goto end;
2072 }
2073 }
2074
2075 if (c->used != c->oldused) {
2076 searchkey.obj_id = c->offset;
2077 searchkey.obj_type = TYPE_BLOCK_GROUP_ITEM;
2078 searchkey.offset = c->chunk_item->size;
2079
2080 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2081 if (!NT_SUCCESS(Status)) {
2082 ERR("error - find_item returned %08x\n", Status);
2083 ExReleaseResourceLite(&c->lock);
2084 goto end;
2085 }
2086
2087 if (keycmp(searchkey, tp.item->key)) {
2088 ERR("could not find (%llx,%x,%llx) in extent_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
2089 int3;
2090 Status = STATUS_INTERNAL_ERROR;
2091 ExReleaseResourceLite(&c->lock);
2092 goto end;
2093 }
2094
2095 if (tp.item->size < sizeof(BLOCK_GROUP_ITEM)) {
2096 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));
2097 Status = STATUS_INTERNAL_ERROR;
2098 ExReleaseResourceLite(&c->lock);
2099 goto end;
2100 }
2101
2102 bgi = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
2103 if (!bgi) {
2104 ERR("out of memory\n");
2105 Status = STATUS_INSUFFICIENT_RESOURCES;
2106 ExReleaseResourceLite(&c->lock);
2107 goto end;
2108 }
2109
2110 RtlCopyMemory(bgi, tp.item->data, tp.item->size);
2111 bgi->used = c->used;
2112
2113 TRACE("adjusting usage of chunk %llx to %llx\n", c->offset, c->used);
2114
2115 delete_tree_item(Vcb, &tp, rollback);
2116
2117 if (!insert_tree_item(Vcb, Vcb->extent_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, bgi, tp.item->size, NULL, Irp, rollback)) {
2118 ERR("insert_tree_item failed\n");
2119 ExFreePool(bgi);
2120 Status = STATUS_INTERNAL_ERROR;
2121 ExReleaseResourceLite(&c->lock);
2122 goto end;
2123 }
2124
2125 TRACE("bytes_used = %llx\n", Vcb->superblock.bytes_used);
2126
2127 Vcb->superblock.bytes_used += c->used - c->oldused;
2128
2129 TRACE("bytes_used = %llx\n", Vcb->superblock.bytes_used);
2130
2131 c->oldused = c->used;
2132 }
2133
2134 ExReleaseResourceLite(&c->lock);
2135
2136 le = le->Flink;
2137 }
2138
2139 if (flushed_extents) {
2140 ExAcquireResourceExclusiveLite(&Vcb->checksum_lock, TRUE);
2141 if (!IsListEmpty(&Vcb->sector_checksums)) {
2142 update_checksum_tree(Vcb, Irp, rollback);
2143 }
2144 ExReleaseResourceLite(&Vcb->checksum_lock);
2145 }
2146
2147 Status = STATUS_SUCCESS;
2148
2149 end:
2150 ExReleaseResourceLite(&Vcb->chunk_lock);
2151
2152 return Status;
2153 }
2154
2155 static void get_first_item(tree* t, KEY* key) {
2156 LIST_ENTRY* le;
2157
2158 le = t->itemlist.Flink;
2159 while (le != &t->itemlist) {
2160 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2161
2162 *key = td->key;
2163 return;
2164 }
2165 }
2166
2167 static NTSTATUS STDCALL split_tree_at(device_extension* Vcb, tree* t, tree_data* newfirstitem, UINT32 numitems, UINT32 size) {
2168 tree *nt, *pt;
2169 tree_data* td;
2170 tree_data* oldlastitem;
2171 // write_tree* wt2;
2172 // // tree_data *firsttd, *lasttd;
2173 // // LIST_ENTRY* le;
2174 // #ifdef DEBUG_PARANOID
2175 // KEY lastkey1, lastkey2;
2176 // traverse_ptr tp, next_tp;
2177 // ULONG numitems1, numitems2;
2178 // #endif
2179
2180 TRACE("splitting tree in %llx at (%llx,%x,%llx)\n", t->root->id, newfirstitem->key.obj_id, newfirstitem->key.obj_type, newfirstitem->key.offset);
2181
2182 // #ifdef DEBUG_PARANOID
2183 // lastkey1.obj_id = 0xffffffffffffffff;
2184 // lastkey1.obj_type = 0xff;
2185 // lastkey1.offset = 0xffffffffffffffff;
2186 //
2187 // if (!find_item(Vcb, t->root, &tp, &lastkey1, NULL, FALSE))
2188 // ERR("error - find_item failed\n");
2189 // else {
2190 // lastkey1 = tp.item->key;
2191 // numitems1 = 0;
2192 // while (find_prev_item(Vcb, &tp, &next_tp, NULL, FALSE)) {
2193 // free_traverse_ptr(&tp);
2194 // tp = next_tp;
2195 // numitems1++;
2196 // }
2197 // free_traverse_ptr(&tp);
2198 // }
2199 // #endif
2200
2201 nt = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
2202 if (!nt) {
2203 ERR("out of memory\n");
2204 return STATUS_INSUFFICIENT_RESOURCES;
2205 }
2206
2207 RtlCopyMemory(&nt->header, &t->header, sizeof(tree_header));
2208 nt->header.address = 0;
2209 nt->header.generation = Vcb->superblock.generation;
2210 nt->header.num_items = t->header.num_items - numitems;
2211 nt->header.flags = HEADER_FLAG_MIXED_BACKREF;
2212
2213 nt->has_address = FALSE;
2214 nt->Vcb = Vcb;
2215 nt->parent = t->parent;
2216
2217 #ifdef DEBUG_PARANOID
2218 if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
2219 #endif
2220
2221 nt->root = t->root;
2222 // nt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
2223 nt->new_address = 0;
2224 nt->has_new_address = FALSE;
2225 nt->updated_extents = FALSE;
2226 nt->flags = t->flags;
2227 InitializeListHead(&nt->itemlist);
2228
2229 // ExInitializeResourceLite(&nt->nonpaged->load_tree_lock);
2230
2231 oldlastitem = CONTAINING_RECORD(newfirstitem->list_entry.Blink, tree_data, list_entry);
2232
2233 // // firsttd = CONTAINING_RECORD(wt->tree->itemlist.Flink, tree_data, list_entry);
2234 // // lasttd = CONTAINING_RECORD(wt->tree->itemlist.Blink, tree_data, list_entry);
2235 // //
2236 // // TRACE("old tree in %x was from (%x,%x,%x) to (%x,%x,%x)\n",
2237 // // (UINT32)wt->tree->root->id, (UINT32)firsttd->key.obj_id, firsttd->key.obj_type, (UINT32)firsttd->key.offset,
2238 // // (UINT32)lasttd->key.obj_id, lasttd->key.obj_type, (UINT32)lasttd->key.offset);
2239 // //
2240 // // le = wt->tree->itemlist.Flink;
2241 // // while (le != &wt->tree->itemlist) {
2242 // // td = CONTAINING_RECORD(le, tree_data, list_entry);
2243 // // TRACE("old tree item was (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2244 // // le = le->Flink;
2245 // // }
2246
2247 nt->itemlist.Flink = &newfirstitem->list_entry;
2248 nt->itemlist.Blink = t->itemlist.Blink;
2249 nt->itemlist.Flink->Blink = &nt->itemlist;
2250 nt->itemlist.Blink->Flink = &nt->itemlist;
2251
2252 t->itemlist.Blink = &oldlastitem->list_entry;
2253 t->itemlist.Blink->Flink = &t->itemlist;
2254
2255 // // le = wt->tree->itemlist.Flink;
2256 // // while (le != &wt->tree->itemlist) {
2257 // // td = CONTAINING_RECORD(le, tree_data, list_entry);
2258 // // TRACE("old tree item now (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2259 // // le = le->Flink;
2260 // // }
2261 // //
2262 // // firsttd = CONTAINING_RECORD(wt->tree->itemlist.Flink, tree_data, list_entry);
2263 // // lasttd = CONTAINING_RECORD(wt->tree->itemlist.Blink, tree_data, list_entry);
2264 // //
2265 // // TRACE("old tree in %x is now from (%x,%x,%x) to (%x,%x,%x)\n",
2266 // // (UINT32)wt->tree->root->id, (UINT32)firsttd->key.obj_id, firsttd->key.obj_type, (UINT32)firsttd->key.offset,
2267 // // (UINT32)lasttd->key.obj_id, lasttd->key.obj_type, (UINT32)lasttd->key.offset);
2268
2269 nt->size = t->size - size;
2270 t->size = size;
2271 t->header.num_items = numitems;
2272 nt->write = TRUE;
2273
2274 InterlockedIncrement(&Vcb->open_trees);
2275 InsertTailList(&Vcb->trees, &nt->list_entry);
2276
2277 // // // TESTING
2278 // // td = wt->tree->items;
2279 // // while (td) {
2280 // // if (!td->ignore) {
2281 // // TRACE("old tree item: (%x,%x,%x)\n", (UINT32)td->key.obj_id, td->key.obj_type, (UINT32)td->key.offset);
2282 // // }
2283 // // td = td->next;
2284 // // }
2285
2286 // // oldlastitem->next = NULL;
2287 // // wt->tree->lastitem = oldlastitem;
2288
2289 // // TRACE("last item is now (%x,%x,%x)\n", (UINT32)oldlastitem->key.obj_id, oldlastitem->key.obj_type, (UINT32)oldlastitem->key.offset);
2290
2291 if (nt->header.level > 0) {
2292 LIST_ENTRY* le = nt->itemlist.Flink;
2293
2294 while (le != &nt->itemlist) {
2295 tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
2296
2297 if (td2->treeholder.tree) {
2298 td2->treeholder.tree->parent = nt;
2299 #ifdef DEBUG_PARANOID
2300 if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
2301 #endif
2302 }
2303
2304 le = le->Flink;
2305 }
2306 }
2307
2308 if (nt->parent) {
2309 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2310 if (!td) {
2311 ERR("out of memory\n");
2312 return STATUS_INSUFFICIENT_RESOURCES;
2313 }
2314
2315 td->key = newfirstitem->key;
2316
2317 InsertHeadList(&t->paritem->list_entry, &td->list_entry);
2318
2319 td->ignore = FALSE;
2320 td->inserted = TRUE;
2321 td->treeholder.tree = nt;
2322 // td->treeholder.nonpaged->status = tree_holder_loaded;
2323 nt->paritem = td;
2324
2325 nt->parent->header.num_items++;
2326 nt->parent->size += sizeof(internal_node);
2327
2328 goto end;
2329 }
2330
2331 TRACE("adding new tree parent\n");
2332
2333 if (nt->header.level == 255) {
2334 ERR("cannot add parent to tree at level 255\n");
2335 return STATUS_INTERNAL_ERROR;
2336 }
2337
2338 pt = ExAllocatePoolWithTag(PagedPool, sizeof(tree), ALLOC_TAG);
2339 if (!pt) {
2340 ERR("out of memory\n");
2341 return STATUS_INSUFFICIENT_RESOURCES;
2342 }
2343
2344 RtlCopyMemory(&pt->header, &nt->header, sizeof(tree_header));
2345 pt->header.address = 0;
2346 pt->header.num_items = 2;
2347 pt->header.level = nt->header.level + 1;
2348 pt->header.flags = HEADER_FLAG_MIXED_BACKREF | HEADER_FLAG_WRITTEN;
2349
2350 pt->has_address = FALSE;
2351 pt->Vcb = Vcb;
2352 pt->parent = NULL;
2353 pt->paritem = NULL;
2354 pt->root = t->root;
2355 pt->new_address = 0;
2356 pt->has_new_address = FALSE;
2357 pt->updated_extents = FALSE;
2358 // pt->nonpaged = ExAllocatePoolWithTag(NonPagedPool, sizeof(tree_nonpaged), ALLOC_TAG);
2359 pt->size = pt->header.num_items * sizeof(internal_node);
2360 pt->flags = t->flags;
2361 InitializeListHead(&pt->itemlist);
2362
2363 // ExInitializeResourceLite(&pt->nonpaged->load_tree_lock);
2364
2365 InterlockedIncrement(&Vcb->open_trees);
2366 InsertTailList(&Vcb->trees, &pt->list_entry);
2367
2368 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2369 if (!td) {
2370 ERR("out of memory\n");
2371 return STATUS_INSUFFICIENT_RESOURCES;
2372 }
2373
2374 get_first_item(t, &td->key);
2375 td->ignore = FALSE;
2376 td->inserted = FALSE;
2377 td->treeholder.address = 0;
2378 td->treeholder.generation = Vcb->superblock.generation;
2379 td->treeholder.tree = t;
2380 // td->treeholder.nonpaged->status = tree_holder_loaded;
2381 InsertTailList(&pt->itemlist, &td->list_entry);
2382 t->paritem = td;
2383
2384 td = ExAllocateFromPagedLookasideList(&Vcb->tree_data_lookaside);
2385 if (!td) {
2386 ERR("out of memory\n");
2387 return STATUS_INSUFFICIENT_RESOURCES;
2388 }
2389
2390 td->key = newfirstitem->key;
2391 td->ignore = FALSE;
2392 td->inserted = FALSE;
2393 td->treeholder.address = 0;
2394 td->treeholder.generation = Vcb->superblock.generation;
2395 td->treeholder.tree = nt;
2396 // td->treeholder.nonpaged->status = tree_holder_loaded;
2397 InsertTailList(&pt->itemlist, &td->list_entry);
2398 nt->paritem = td;
2399
2400 pt->write = TRUE;
2401
2402 t->root->treeholder.tree = pt;
2403
2404 t->parent = pt;
2405 nt->parent = pt;
2406
2407 #ifdef DEBUG_PARANOID
2408 if (t->parent && t->parent->header.level <= t->header.level) int3;
2409 if (nt->parent && nt->parent->header.level <= nt->header.level) int3;
2410 #endif
2411
2412 end:
2413 t->root->root_item.bytes_used += Vcb->superblock.node_size;
2414
2415 // #ifdef DEBUG_PARANOID
2416 // lastkey2.obj_id = 0xffffffffffffffff;
2417 // lastkey2.obj_type = 0xff;
2418 // lastkey2.offset = 0xffffffffffffffff;
2419 //
2420 // if (!find_item(Vcb, wt->tree->root, &tp, &lastkey2, NULL, FALSE))
2421 // ERR("error - find_item failed\n");
2422 // else {
2423 // lastkey2 = tp.item->key;
2424 //
2425 // numitems2 = 0;
2426 // while (find_prev_item(Vcb, &tp, &next_tp, NULL, FALSE)) {
2427 // free_traverse_ptr(&tp);
2428 // tp = next_tp;
2429 // numitems2++;
2430 // }
2431 // free_traverse_ptr(&tp);
2432 // }
2433 //
2434 // ERR("lastkey1 = %llx,%x,%llx\n", lastkey1.obj_id, lastkey1.obj_type, lastkey1.offset);
2435 // ERR("lastkey2 = %llx,%x,%llx\n", lastkey2.obj_id, lastkey2.obj_type, lastkey2.offset);
2436 // ERR("numitems1 = %u\n", numitems1);
2437 // ERR("numitems2 = %u\n", numitems2);
2438 // #endif
2439
2440 return STATUS_SUCCESS;
2441 }
2442
2443 static NTSTATUS STDCALL split_tree(device_extension* Vcb, tree* t) {
2444 LIST_ENTRY* le;
2445 UINT32 size, ds, numitems;
2446
2447 size = 0;
2448 numitems = 0;
2449
2450 // FIXME - naïve implementation: maximizes number of filled trees
2451
2452 le = t->itemlist.Flink;
2453 while (le != &t->itemlist) {
2454 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2455
2456 if (!td->ignore) {
2457 if (t->header.level == 0)
2458 ds = sizeof(leaf_node) + td->size;
2459 else
2460 ds = sizeof(internal_node);
2461
2462 // FIXME - move back if previous item was deleted item with same key
2463 if (size + ds > Vcb->superblock.node_size - sizeof(tree_header))
2464 return split_tree_at(Vcb, t, td, numitems, size);
2465
2466 size += ds;
2467 numitems++;
2468 }
2469
2470 le = le->Flink;
2471 }
2472
2473 return STATUS_SUCCESS;
2474 }
2475
2476 BOOL is_tree_unique(device_extension* Vcb, tree* t, PIRP Irp) {
2477 KEY searchkey;
2478 traverse_ptr tp;
2479 NTSTATUS Status;
2480
2481 do {
2482 EXTENT_ITEM* ei;
2483 UINT8* type;
2484
2485 if (t->has_address) {
2486 searchkey.obj_id = t->header.address;
2487 searchkey.obj_type = Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA ? TYPE_METADATA_ITEM : TYPE_EXTENT_ITEM;
2488 searchkey.offset = 0xffffffffffffffff;
2489
2490 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2491 if (!NT_SUCCESS(Status)) {
2492 ERR("error - find_item returned %08x\n", Status);
2493 return FALSE;
2494 }
2495
2496 if (tp.item->key.obj_id != t->header.address || (tp.item->key.obj_type != TYPE_METADATA_ITEM && tp.item->key.obj_type != TYPE_EXTENT_ITEM))
2497 return FALSE;
2498
2499 if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && tp.item->size == sizeof(EXTENT_ITEM_V0))
2500 return FALSE;
2501
2502 if (tp.item->size < sizeof(EXTENT_ITEM))
2503 return FALSE;
2504
2505 ei = (EXTENT_ITEM*)tp.item->data;
2506
2507 if (ei->refcount > 1)
2508 return FALSE;
2509
2510 if (tp.item->key.obj_type == TYPE_EXTENT_ITEM && ei->flags & EXTENT_ITEM_TREE_BLOCK) {
2511 EXTENT_ITEM2* ei2;
2512
2513 if (tp.item->size < sizeof(EXTENT_ITEM) + sizeof(EXTENT_ITEM2))
2514 return FALSE;
2515
2516 ei2 = (EXTENT_ITEM2*)&ei[1];
2517 type = (UINT8*)&ei2[1];
2518 } else
2519 type = (UINT8*)&ei[1];
2520
2521 if (type >= tp.item->data + tp.item->size || *type != TYPE_TREE_BLOCK_REF)
2522 return FALSE;
2523 }
2524
2525 t = t->parent;
2526 } while (t);
2527
2528 return TRUE;
2529 }
2530
2531 static NTSTATUS try_tree_amalgamate(device_extension* Vcb, tree* t, PIRP Irp, LIST_ENTRY* rollback) {
2532 LIST_ENTRY* le;
2533 tree_data* nextparitem = NULL;
2534 NTSTATUS Status;
2535 tree *next_tree, *par;
2536 BOOL loaded;
2537
2538 TRACE("trying to amalgamate tree in root %llx, level %x (size %u)\n", t->root->id, t->header.level, t->size);
2539
2540 // FIXME - doesn't capture everything, as it doesn't ascend
2541 // FIXME - write proper function and put it in treefuncs.c
2542 le = t->paritem->list_entry.Flink;
2543 while (le != &t->parent->itemlist) {
2544 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2545
2546 if (!td->ignore) {
2547 nextparitem = td;
2548 break;
2549 }
2550
2551 le = le->Flink;
2552 }
2553
2554 if (!nextparitem)
2555 return STATUS_SUCCESS;
2556
2557 // FIXME - loop, and capture more than one tree if we can
2558
2559 TRACE("nextparitem: key = %llx,%x,%llx\n", nextparitem->key.obj_id, nextparitem->key.obj_type, nextparitem->key.offset);
2560 // nextparitem = t->paritem;
2561
2562 // ExAcquireResourceExclusiveLite(&t->parent->nonpaged->load_tree_lock, TRUE);
2563
2564 Status = do_load_tree(Vcb, &nextparitem->treeholder, t->root, t->parent, nextparitem, &loaded, NULL);
2565 if (!NT_SUCCESS(Status)) {
2566 ERR("do_load_tree returned %08x\n", Status);
2567 return Status;
2568 }
2569
2570 if (!is_tree_unique(Vcb, nextparitem->treeholder.tree, Irp))
2571 return STATUS_SUCCESS;
2572
2573 // ExReleaseResourceLite(&t->parent->nonpaged->load_tree_lock);
2574
2575 next_tree = nextparitem->treeholder.tree;
2576
2577 if (t->size + next_tree->size <= Vcb->superblock.node_size - sizeof(tree_header)) {
2578 // merge two trees into one
2579
2580 t->header.num_items += next_tree->header.num_items;
2581 t->size += next_tree->size;
2582
2583 if (next_tree->header.level > 0) {
2584 le = next_tree->itemlist.Flink;
2585
2586 while (le != &next_tree->itemlist) {
2587 tree_data* td2 = CONTAINING_RECORD(le, tree_data, list_entry);
2588
2589 if (td2->treeholder.tree) {
2590 td2->treeholder.tree->parent = t;
2591 #ifdef DEBUG_PARANOID
2592 if (td2->treeholder.tree->parent && td2->treeholder.tree->parent->header.level <= td2->treeholder.tree->header.level) int3;
2593 #endif
2594 }
2595
2596 le = le->Flink;
2597 }
2598 }
2599
2600 t->itemlist.Blink->Flink = next_tree->itemlist.Flink;
2601 t->itemlist.Blink->Flink->Blink = t->itemlist.Blink;
2602 t->itemlist.Blink = next_tree->itemlist.Blink;
2603 t->itemlist.Blink->Flink = &t->itemlist;
2604
2605 // // TESTING
2606 // le = t->itemlist.Flink;
2607 // while (le != &t->itemlist) {
2608 // tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2609 // if (!td->ignore) {
2610 // ERR("key: %llx,%x,%llx\n", td->key.obj_id, td->key.obj_type, td->key.offset);
2611 // }
2612 // le = le->Flink;
2613 // }
2614
2615 next_tree->itemlist.Flink = next_tree->itemlist.Blink = &next_tree->itemlist;
2616
2617 next_tree->header.num_items = 0;
2618 next_tree->size = 0;
2619
2620 if (next_tree->has_new_address) { // delete associated EXTENT_ITEM
2621 Status = reduce_tree_extent(Vcb, next_tree->new_address, next_tree, Irp, rollback);
2622
2623 if (!NT_SUCCESS(Status)) {
2624 ERR("reduce_tree_extent returned %08x\n", Status);
2625 return Status;
2626 }
2627 } else if (next_tree->has_address) {
2628 Status = reduce_tree_extent(Vcb, next_tree->header.address, next_tree, Irp, rollback);
2629
2630 if (!NT_SUCCESS(Status)) {
2631 ERR("reduce_tree_extent returned %08x\n", Status);
2632 return Status;
2633 }
2634 }
2635
2636 if (!nextparitem->ignore) {
2637 nextparitem->ignore = TRUE;
2638 next_tree->parent->header.num_items--;
2639 next_tree->parent->size -= sizeof(internal_node);
2640 }
2641
2642 par = next_tree->parent;
2643 while (par) {
2644 par->write = TRUE;
2645 par = par->parent;
2646 }
2647
2648 RemoveEntryList(&nextparitem->list_entry);
2649 ExFreePool(next_tree->paritem);
2650 next_tree->paritem = NULL;
2651
2652 next_tree->root->root_item.bytes_used -= Vcb->superblock.node_size;
2653
2654 free_tree(next_tree);
2655 } else {
2656 // rebalance by moving items from second tree into first
2657 ULONG avg_size = (t->size + next_tree->size) / 2;
2658 KEY firstitem = {0, 0, 0};
2659 BOOL changed = FALSE;
2660
2661 TRACE("attempting rebalance\n");
2662
2663 le = next_tree->itemlist.Flink;
2664 while (le != &next_tree->itemlist && t->size < avg_size && next_tree->header.num_items > 1) {
2665 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2666 ULONG size;
2667
2668 if (!td->ignore) {
2669 if (next_tree->header.level == 0)
2670 size = sizeof(leaf_node) + td->size;
2671 else
2672 size = sizeof(internal_node);
2673 } else
2674 size = 0;
2675
2676 if (t->size + size < Vcb->superblock.node_size - sizeof(tree_header)) {
2677 RemoveEntryList(&td->list_entry);
2678 InsertTailList(&t->itemlist, &td->list_entry);
2679
2680 if (next_tree->header.level > 0 && td->treeholder.tree) {
2681 td->treeholder.tree->parent = t;
2682 #ifdef DEBUG_PARANOID
2683 if (td->treeholder.tree->parent && td->treeholder.tree->parent->header.level <= td->treeholder.tree->header.level) int3;
2684 #endif
2685 }
2686
2687 if (!td->ignore) {
2688 next_tree->size -= size;
2689 t->size += size;
2690 next_tree->header.num_items--;
2691 t->header.num_items++;
2692 }
2693
2694 changed = TRUE;
2695 } else
2696 break;
2697
2698 le = next_tree->itemlist.Flink;
2699 }
2700
2701 if (changed) {
2702 le = next_tree->itemlist.Flink;
2703 while (le != &next_tree->itemlist) {
2704 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
2705
2706 if (!td->ignore) {
2707 firstitem = td->key;
2708 break;
2709 }
2710
2711 le = le->Flink;
2712 }
2713
2714 // ERR("firstitem = %llx,%x,%llx\n", firstitem.obj_id, firstitem.obj_type, firstitem.offset);
2715
2716 // FIXME - once ascension is working, make this work with parent's parent, etc.
2717 if (next_tree->paritem)
2718 next_tree->paritem->key = firstitem;
2719
2720 par = next_tree;
2721 while (par) {
2722 par->write = TRUE;
2723 par = par->parent;
2724 }
2725 }
2726 }
2727
2728 return STATUS_SUCCESS;
2729 }
2730
2731 static NTSTATUS update_extent_level(device_extension* Vcb, UINT64 address, tree* t, UINT8 level, PIRP Irp, LIST_ENTRY* rollback) {
2732 KEY searchkey;
2733 traverse_ptr tp;
2734 NTSTATUS Status;
2735
2736 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_SKINNY_METADATA) {
2737 searchkey.obj_id = address;
2738 searchkey.obj_type = TYPE_METADATA_ITEM;
2739 searchkey.offset = t->header.level;
2740
2741 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2742 if (!NT_SUCCESS(Status)) {
2743 ERR("error - find_item returned %08x\n", Status);
2744 return Status;
2745 }
2746
2747 if (!keycmp(tp.item->key, searchkey)) {
2748 EXTENT_ITEM_SKINNY_METADATA* eism;
2749
2750 if (tp.item->size > 0) {
2751 eism = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
2752
2753 if (!eism) {
2754 ERR("out of memory\n");
2755 return STATUS_INSUFFICIENT_RESOURCES;
2756 }
2757
2758 RtlCopyMemory(eism, tp.item->data, tp.item->size);
2759 } else
2760 eism = NULL;
2761
2762 delete_tree_item(Vcb, &tp, rollback);
2763
2764 if (!insert_tree_item(Vcb, Vcb->extent_root, address, TYPE_METADATA_ITEM, level, eism, tp.item->size, NULL, Irp, rollback)) {
2765 ERR("insert_tree_item failed\n");
2766 ExFreePool(eism);
2767 return STATUS_INTERNAL_ERROR;
2768 }
2769
2770 return STATUS_SUCCESS;
2771 }
2772 }
2773
2774 searchkey.obj_id = address;
2775 searchkey.obj_type = TYPE_EXTENT_ITEM;
2776 searchkey.offset = 0xffffffffffffffff;
2777
2778 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
2779 if (!NT_SUCCESS(Status)) {
2780 ERR("error - find_item returned %08x\n", Status);
2781 return Status;
2782 }
2783
2784 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type) {
2785 EXTENT_ITEM_TREE* eit;
2786
2787 if (tp.item->size < sizeof(EXTENT_ITEM_TREE)) {
2788 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));
2789 return STATUS_INTERNAL_ERROR;
2790 }
2791
2792 eit = ExAllocatePoolWithTag(PagedPool, tp.item->size, ALLOC_TAG);
2793
2794 if (!eit) {
2795 ERR("out of memory\n");
2796 return STATUS_INSUFFICIENT_RESOURCES;
2797 }
2798
2799 RtlCopyMemory(eit, tp.item->data, tp.item->size);
2800
2801 delete_tree_item(Vcb, &tp, rollback);
2802
2803 eit->level = level;
2804
2805 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, Irp, rollback)) {
2806 ERR("insert_tree_item failed\n");
2807 ExFreePool(eit);
2808 return STATUS_INTERNAL_ERROR;
2809 }
2810
2811 return STATUS_SUCCESS;
2812 }
2813
2814 ERR("could not find EXTENT_ITEM for address %llx\n", address);
2815
2816 return STATUS_INTERNAL_ERROR;
2817 }
2818
2819 static NTSTATUS STDCALL do_splits(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
2820 // LIST_ENTRY *le, *le2;
2821 // write_tree* wt;
2822 // tree_data* td;
2823 UINT8 level, max_level;
2824 UINT32 min_size;
2825 BOOL empty, done_deletions = FALSE;
2826 NTSTATUS Status;
2827 tree* t;
2828
2829 TRACE("(%p)\n", Vcb);
2830
2831 max_level = 0;
2832
2833 for (level = 0; level <= 255; level++) {
2834 LIST_ENTRY *le, *nextle;
2835
2836 empty = TRUE;
2837
2838 TRACE("doing level %u\n", level);
2839
2840 le = Vcb->trees.Flink;
2841
2842 while (le != &Vcb->trees) {
2843 t = CONTAINING_RECORD(le, tree, list_entry);
2844
2845 nextle = le->Flink;
2846
2847 if (t->write && t->header.level == level) {
2848 empty = FALSE;
2849
2850 if (t->header.num_items == 0) {
2851 if (t->parent) {
2852 LIST_ENTRY* le2;
2853 KEY firstitem = {0xcccccccccccccccc,0xcc,0xcccccccccccccccc};
2854 #ifdef __REACTOS__
2855 (void)firstitem;
2856 #endif
2857
2858 done_deletions = TRUE;
2859
2860 le2 = t->itemlist.Flink;
2861 while (le2 != &t->itemlist) {
2862 tree_data* td = CONTAINING_RECORD(le2, tree_data, list_entry);
2863 firstitem = td->key;
2864 break;
2865 }
2866
2867 TRACE("deleting tree in root %llx (first item was %llx,%x,%llx)\n",
2868 t->root->id, firstitem.obj_id, firstitem.obj_type, firstitem.offset);
2869
2870 t->root->root_item.bytes_used -= Vcb->superblock.node_size;
2871
2872 if (t->has_new_address) { // delete associated EXTENT_ITEM
2873 Status = reduce_tree_extent(Vcb, t->new_address, t, Irp, rollback);
2874
2875 if (!NT_SUCCESS(Status)) {
2876 ERR("reduce_tree_extent returned %08x\n", Status);
2877 return Status;
2878 }
2879
2880 t->has_new_address = FALSE;
2881 } else if (t->has_address) {
2882 Status = reduce_tree_extent(Vcb,t->header.address, t, Irp, rollback);
2883
2884 if (!NT_SUCCESS(Status)) {
2885 ERR("reduce_tree_extent returned %08x\n", Status);
2886 return Status;
2887 }
2888
2889 t->has_address = FALSE;
2890 }
2891
2892 if (!t->paritem->ignore) {
2893 t->paritem->ignore = TRUE;
2894 t->parent->header.num_items--;
2895 t->parent->size -= sizeof(internal_node);
2896 }
2897
2898 RemoveEntryList(&t->paritem->list_entry);
2899 ExFreePool(t->paritem);
2900 t->paritem = NULL;
2901
2902 free_tree(t);
2903 } else if (t->header.level != 0) {
2904 if (t->has_new_address) {
2905 Status = update_extent_level(Vcb, t->new_address, t, 0, Irp, rollback);
2906
2907 if (!NT_SUCCESS(Status)) {
2908 ERR("update_extent_level returned %08x\n", Status);
2909 return Status;
2910 }
2911 }
2912
2913 t->header.level = 0;
2914 }
2915 } else if (t->size > Vcb->superblock.node_size - sizeof(tree_header)) {
2916 TRACE("splitting overlarge tree (%x > %x)\n", t->size, Vcb->superblock.node_size - sizeof(tree_header));
2917 Status = split_tree(Vcb, t);
2918
2919 if (!NT_SUCCESS(Status)) {
2920 ERR("split_tree returned %08x\n", Status);
2921 return Status;
2922 }
2923 }
2924 }
2925
2926 le = nextle;
2927 }
2928
2929 if (!empty) {
2930 max_level = level;
2931 } else {
2932 TRACE("nothing found for level %u\n", level);
2933 break;
2934 }
2935 }
2936
2937 min_size = (Vcb->superblock.node_size - sizeof(tree_header)) / 2;
2938
2939 for (level = 0; level <= max_level; level++) {
2940 LIST_ENTRY* le;
2941
2942 le = Vcb->trees.Flink;
2943
2944 while (le != &Vcb->trees) {
2945 t = CONTAINING_RECORD(le, tree, list_entry);
2946
2947 if (t->write && t->header.level == level && t->header.num_items > 0 && t->parent && t->size < min_size && is_tree_unique(Vcb, t, Irp)) {
2948 Status = try_tree_amalgamate(Vcb, t, Irp, rollback);
2949 if (!NT_SUCCESS(Status)) {
2950 ERR("try_tree_amalgamate returned %08x\n", Status);
2951 return Status;
2952 }
2953 }
2954
2955 le = le->Flink;
2956 }
2957 }
2958
2959 // simplify trees if top tree only has one entry
2960
2961 if (done_deletions) {
2962 for (level = max_level; level > 0; level--) {
2963 LIST_ENTRY *le, *nextle;
2964
2965 le = Vcb->trees.Flink;
2966 while (le != &Vcb->trees) {
2967 nextle = le->Flink;
2968 t = CONTAINING_RECORD(le, tree, list_entry);
2969
2970 if (t->write && t->header.level == level) {
2971 if (!t->parent && t->header.num_items == 1) {
2972 LIST_ENTRY* le2 = t->itemlist.Flink;
2973 tree_data* td;
2974 tree* child_tree = NULL;
2975
2976 while (le2 != &t->itemlist) {
2977 td = CONTAINING_RECORD(le2, tree_data, list_entry);
2978 if (!td->ignore)
2979 break;
2980 le2 = le2->Flink;
2981 }
2982
2983 TRACE("deleting top-level tree in root %llx with one item\n", t->root->id);
2984
2985 if (t->has_new_address) { // delete associated EXTENT_ITEM
2986 Status = reduce_tree_extent(Vcb, t->new_address, t, Irp, rollback);
2987
2988 if (!NT_SUCCESS(Status)) {
2989 ERR("reduce_tree_extent returned %08x\n", Status);
2990 return Status;
2991 }
2992
2993 t->has_new_address = FALSE;
2994 } else if (t->has_address) {
2995 Status = reduce_tree_extent(Vcb,t->header.address, t, Irp, rollback);
2996
2997 if (!NT_SUCCESS(Status)) {
2998 ERR("reduce_tree_extent returned %08x\n", Status);
2999 return Status;
3000 }
3001
3002 t->has_address = FALSE;
3003 }
3004
3005 if (!td->treeholder.tree) { // load first item if not already loaded
3006 KEY searchkey = {0,0,0};
3007 traverse_ptr tp;
3008
3009 Status = find_item(Vcb, t->root, &tp, &searchkey, FALSE, Irp);
3010 if (!NT_SUCCESS(Status)) {
3011 ERR("error - find_item returned %08x\n", Status);
3012 return Status;
3013 }
3014 }
3015
3016 child_tree = td->treeholder.tree;
3017
3018 if (child_tree) {
3019 child_tree->parent = NULL;
3020 child_tree->paritem = NULL;
3021 }
3022
3023 t->root->root_item.bytes_used -= Vcb->superblock.node_size;
3024
3025 free_tree(t);
3026
3027 if (child_tree)
3028 child_tree->root->treeholder.tree = child_tree;
3029 }
3030 }
3031
3032 le = nextle;
3033 }
3034 }
3035 }
3036
3037 return STATUS_SUCCESS;
3038 }
3039
3040 static NTSTATUS remove_root_extents(device_extension* Vcb, root* r, tree_holder* th, UINT8 level, PIRP Irp, LIST_ENTRY* rollback) {
3041 NTSTATUS Status;
3042
3043 if (level > 0) {
3044 if (!th->tree) {
3045 Status = load_tree(Vcb, th->address, r, &th->tree, NULL, NULL);
3046
3047 if (!NT_SUCCESS(Status)) {
3048 ERR("load_tree(%llx) returned %08x\n", th->address, Status);
3049 return Status;
3050 }
3051 }
3052
3053 if (th->tree->header.level > 0) {
3054 LIST_ENTRY* le = th->tree->itemlist.Flink;
3055
3056 while (le != &th->tree->itemlist) {
3057 tree_data* td = CONTAINING_RECORD(le, tree_data, list_entry);
3058
3059 if (!td->ignore) {
3060 Status = remove_root_extents(Vcb, r, &td->treeholder, th->tree->header.level - 1, Irp, rollback);
3061
3062 if (!NT_SUCCESS(Status)) {
3063 ERR("remove_root_extents returned %08x\n", Status);
3064 return Status;
3065 }
3066 }
3067
3068 le = le->Flink;
3069 }
3070 }
3071 }
3072
3073 if (!th->tree || th->tree->has_address) {
3074 Status = reduce_tree_extent(Vcb, th->address, NULL, Irp, rollback);
3075
3076 if (!NT_SUCCESS(Status)) {
3077 ERR("reduce_tree_extent(%llx) returned %08x\n", th->address, Status);
3078 return Status;
3079 }
3080 }
3081
3082 return STATUS_SUCCESS;
3083 }
3084
3085 static NTSTATUS drop_root(device_extension* Vcb, root* r, PIRP Irp, LIST_ENTRY* rollback) {
3086 NTSTATUS Status;
3087 KEY searchkey;
3088 traverse_ptr tp;
3089
3090 Status = remove_root_extents(Vcb, r, &r->treeholder, r->root_item.root_level, Irp, rollback);
3091 if (!NT_SUCCESS(Status)) {
3092 ERR("remove_root_extents returned %08x\n", Status);
3093 return Status;
3094 }
3095
3096 // remove entry in uuid root (tree 9)
3097 if (Vcb->uuid_root) {
3098 RtlCopyMemory(&searchkey.obj_id, &r->root_item.uuid.uuid[0], sizeof(UINT64));
3099 searchkey.obj_type = TYPE_SUBVOL_UUID;
3100 RtlCopyMemory(&searchkey.offset, &r->root_item.uuid.uuid[sizeof(UINT64)], sizeof(UINT64));
3101
3102 if (searchkey.obj_id != 0 || searchkey.offset != 0) {
3103 Status = find_item(Vcb, Vcb->uuid_root, &tp, &searchkey, FALSE, Irp);
3104 if (!NT_SUCCESS(Status)) {
3105 WARN("find_item returned %08x\n", Status);
3106 } else {
3107 if (!keycmp(tp.item->key, searchkey))
3108 delete_tree_item(Vcb, &tp, rollback);
3109 else
3110 WARN("could not find (%llx,%x,%llx) in uuid tree\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
3111 }
3112 }
3113 }
3114
3115 // delete ROOT_ITEM
3116
3117 searchkey.obj_id = r->id;
3118 searchkey.obj_type = TYPE_ROOT_ITEM;
3119 searchkey.offset = 0xffffffffffffffff;
3120
3121 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
3122 if (!NT_SUCCESS(Status)) {
3123 ERR("find_item returned %08x\n", Status);
3124 return Status;
3125 }
3126
3127 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type)
3128 delete_tree_item(Vcb, &tp, rollback);
3129 else
3130 WARN("could not find (%llx,%x,%llx) in root_root\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
3131
3132 // delete items in tree cache
3133
3134 free_trees_root(Vcb, r);
3135
3136 return STATUS_SUCCESS;
3137 }
3138
3139 static NTSTATUS drop_roots(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
3140 LIST_ENTRY *le = Vcb->drop_roots.Flink, *le2;
3141 NTSTATUS Status;
3142
3143 while (le != &Vcb->drop_roots) {
3144 root* r = CONTAINING_RECORD(le, root, list_entry);
3145
3146 le2 = le->Flink;
3147
3148 Status = drop_root(Vcb, r, Irp, rollback);
3149 if (!NT_SUCCESS(Status)) {
3150 ERR("drop_root(%llx) returned %08x\n", r->id, Status);
3151 return Status;
3152 }
3153
3154 le = le2;
3155 }
3156
3157 return STATUS_SUCCESS;
3158 }
3159
3160 static NTSTATUS update_dev_item(device_extension* Vcb, device* device, PIRP Irp, LIST_ENTRY* rollback) {
3161 KEY searchkey;
3162 traverse_ptr tp;
3163 DEV_ITEM* di;
3164 NTSTATUS Status;
3165
3166 searchkey.obj_id = 1;
3167 searchkey.obj_type = TYPE_DEV_ITEM;
3168 searchkey.offset = device->devitem.dev_id;
3169
3170 Status = find_item(Vcb, Vcb->chunk_root, &tp, &searchkey, FALSE, Irp);
3171 if (!NT_SUCCESS(Status)) {
3172 ERR("error - find_item returned %08x\n", Status);
3173 return Status;
3174 }
3175
3176 if (keycmp(tp.item->key, searchkey)) {
3177 ERR("error - could not find DEV_ITEM for device %llx\n", device->devitem.dev_id);
3178 return STATUS_INTERNAL_ERROR;
3179 }
3180
3181 delete_tree_item(Vcb, &tp, rollback);
3182
3183 di = ExAllocatePoolWithTag(PagedPool, sizeof(DEV_ITEM), ALLOC_TAG);
3184 if (!di) {
3185 ERR("out of memory\n");
3186 return STATUS_INSUFFICIENT_RESOURCES;
3187 }
3188
3189 RtlCopyMemory(di, &device->devitem, sizeof(DEV_ITEM));
3190
3191 if (!insert_tree_item(Vcb, Vcb->chunk_root, 1, TYPE_DEV_ITEM, device->devitem.dev_id, di, sizeof(DEV_ITEM), NULL, Irp, rollback)) {
3192 ERR("insert_tree_item failed\n");
3193 return STATUS_INTERNAL_ERROR;
3194 }
3195
3196 return STATUS_SUCCESS;
3197 }
3198
3199 static void regen_bootstrap(device_extension* Vcb) {
3200 sys_chunk* sc2;
3201 USHORT i = 0;
3202 LIST_ENTRY* le;
3203
3204 i = 0;
3205 le = Vcb->sys_chunks.Flink;
3206 while (le != &Vcb->sys_chunks) {
3207 sc2 = CONTAINING_RECORD(le, sys_chunk, list_entry);
3208
3209 TRACE("%llx,%x,%llx\n", sc2->key.obj_id, sc2->key.obj_type, sc2->key.offset);
3210
3211 RtlCopyMemory(&Vcb->superblock.sys_chunk_array[i], &sc2->key, sizeof(KEY));
3212 i += sizeof(KEY);
3213
3214 RtlCopyMemory(&Vcb->superblock.sys_chunk_array[i], sc2->data, sc2->size);
3215 i += sc2->size;
3216
3217 le = le->Flink;
3218 }
3219 }
3220
3221 static NTSTATUS add_to_bootstrap(device_extension* Vcb, UINT64 obj_id, UINT8 obj_type, UINT64 offset, void* data, ULONG size) {
3222 sys_chunk *sc, *sc2;
3223 LIST_ENTRY* le;
3224
3225 if (Vcb->superblock.n + sizeof(KEY) + size > SYS_CHUNK_ARRAY_SIZE) {
3226 ERR("error - bootstrap is full\n");
3227 return STATUS_INTERNAL_ERROR;
3228 }
3229
3230 sc = ExAllocatePoolWithTag(PagedPool, sizeof(sys_chunk), ALLOC_TAG);
3231 if (!sc) {
3232 ERR("out of memory\n");
3233 return STATUS_INSUFFICIENT_RESOURCES;
3234 }
3235
3236 sc->key.obj_id = obj_id;
3237 sc->key.obj_type = obj_type;
3238 sc->key.offset = offset;
3239 sc->size = size;
3240 sc->data = ExAllocatePoolWithTag(PagedPool, sc->size, ALLOC_TAG);
3241 if (!sc->data) {
3242 ERR("out of memory\n");
3243 ExFreePool(sc);
3244 return STATUS_INSUFFICIENT_RESOURCES;
3245 }
3246
3247 RtlCopyMemory(sc->data, data, sc->size);
3248
3249 le = Vcb->sys_chunks.Flink;
3250 while (le != &Vcb->sys_chunks) {
3251 sc2 = CONTAINING_RECORD(le, sys_chunk, list_entry);
3252
3253 if (keycmp(sc2->key, sc->key) == 1)
3254 break;
3255
3256 le = le->Flink;
3257 }
3258 InsertTailList(le, &sc->list_entry);
3259
3260 Vcb->superblock.n += sizeof(KEY) + size;
3261
3262 regen_bootstrap(Vcb);
3263
3264 return STATUS_SUCCESS;
3265 }
3266
3267 static NTSTATUS create_chunk(device_extension* Vcb, chunk* c, PIRP Irp, LIST_ENTRY* rollback) {
3268 CHUNK_ITEM* ci;
3269 CHUNK_ITEM_STRIPE* cis;
3270 BLOCK_GROUP_ITEM* bgi;
3271 UINT16 i, factor;
3272 NTSTATUS Status;
3273
3274 ci = ExAllocatePoolWithTag(PagedPool, c->size, ALLOC_TAG);
3275 if (!ci) {
3276 ERR("out of memory\n");
3277 return STATUS_INSUFFICIENT_RESOURCES;
3278 }
3279
3280 RtlCopyMemory(ci, c->chunk_item, c->size);
3281
3282 if (!insert_tree_item(Vcb, Vcb->chunk_root, 0x100, TYPE_CHUNK_ITEM, c->offset, ci, c->size, NULL, Irp, rollback)) {
3283 ERR("insert_tree_item failed\n");
3284 ExFreePool(ci);
3285 return STATUS_INTERNAL_ERROR;
3286 }
3287
3288 if (c->chunk_item->type & BLOCK_FLAG_SYSTEM) {
3289 Status = add_to_bootstrap(Vcb, 0x100, TYPE_CHUNK_ITEM, c->offset, ci, c->size);
3290 if (!NT_SUCCESS(Status)) {
3291 ERR("add_to_bootstrap returned %08x\n", Status);
3292 return Status;
3293 }
3294 }
3295
3296 // add BLOCK_GROUP_ITEM to tree 2
3297
3298 bgi = ExAllocatePoolWithTag(PagedPool, sizeof(BLOCK_GROUP_ITEM), ALLOC_TAG);
3299 if (!bgi) {
3300 ERR("out of memory\n");
3301 return STATUS_INSUFFICIENT_RESOURCES;
3302 }
3303
3304 bgi->used = c->used;
3305 bgi->chunk_tree = 0x100;
3306 bgi->flags = c->chunk_item->type;
3307
3308 if (!insert_tree_item(Vcb, Vcb->extent_root, c->offset, TYPE_BLOCK_GROUP_ITEM, c->chunk_item->size, bgi, sizeof(BLOCK_GROUP_ITEM), NULL, Irp, rollback)) {
3309 ERR("insert_tree_item failed\n");
3310 ExFreePool(bgi);
3311 return STATUS_INSUFFICIENT_RESOURCES;
3312 }
3313
3314 if (c->chunk_item->type & BLOCK_FLAG_RAID0)
3315 factor = c->chunk_item->num_stripes;
3316 else if (c->chunk_item->type & BLOCK_FLAG_RAID10)
3317 factor = c->chunk_item->num_stripes / c->chunk_item->sub_stripes;
3318 else if (c->chunk_item->type & BLOCK_FLAG_RAID5)
3319 factor = c->chunk_item->num_stripes - 1;
3320 else if (c->chunk_item->type & BLOCK_FLAG_RAID6)
3321 factor = c->chunk_item->num_stripes - 2;
3322 else // SINGLE, DUPLICATE, RAID1
3323 factor = 1;
3324
3325 // add DEV_EXTENTs to tree 4
3326
3327 cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
3328
3329 for (i = 0; i < c->chunk_item->num_stripes; i++) {
3330 DEV_EXTENT* de;
3331
3332 de = ExAllocatePoolWithTag(PagedPool, sizeof(DEV_EXTENT), ALLOC_TAG);
3333 if (!de) {
3334 ERR("out of memory\n");
3335 return STATUS_INSUFFICIENT_RESOURCES;
3336 }
3337
3338 de->chunktree = Vcb->chunk_root->id;
3339 de->objid = 0x100;
3340 de->address = c->offset;
3341 de->length = c->chunk_item->size / factor;
3342 de->chunktree_uuid = Vcb->chunk_root->treeholder.tree->header.chunk_tree_uuid;
3343
3344 if (!insert_tree_item(Vcb, Vcb->dev_root, c->devices[i]->devitem.dev_id, TYPE_DEV_EXTENT, cis[i].offset, de, sizeof(DEV_EXTENT), NULL, Irp, rollback)) {
3345 ERR("insert_tree_item failed\n");
3346 ExFreePool(de);
3347 return STATUS_INTERNAL_ERROR;
3348 }
3349
3350 // FIXME - no point in calling this twice for the same device
3351 Status = update_dev_item(Vcb, c->devices[i], Irp, rollback);
3352 if (!NT_SUCCESS(Status)) {
3353 ERR("update_dev_item returned %08x\n", Status);
3354 return Status;
3355 }
3356 }
3357
3358 c->created = FALSE;
3359
3360 return STATUS_SUCCESS;
3361 }
3362
3363 static void remove_from_bootstrap(device_extension* Vcb, UINT64 obj_id, UINT8 obj_type, UINT64 offset) {
3364 sys_chunk* sc2;
3365 LIST_ENTRY* le;
3366
3367 le = Vcb->sys_chunks.Flink;
3368 while (le != &Vcb->sys_chunks) {
3369 sc2 = CONTAINING_RECORD(le, sys_chunk, list_entry);
3370
3371 if (sc2->key.obj_id == obj_id && sc2->key.obj_type == obj_type && sc2->key.offset == offset) {
3372 RemoveEntryList(&sc2->list_entry);
3373
3374 Vcb->superblock.n -= sizeof(KEY) + sc2->size;
3375
3376 ExFreePool(sc2->data);
3377 ExFreePool(sc2);
3378 regen_bootstrap(Vcb);
3379 return;
3380 }
3381
3382 le = le->Flink;
3383 }
3384 }
3385
3386 static NTSTATUS STDCALL set_xattr(device_extension* Vcb, LIST_ENTRY* batchlist, root* subvol, UINT64 inode, char* name, UINT32 crc32,
3387 UINT8* data, UINT16 datalen, PIRP Irp, LIST_ENTRY* rollback) {
3388 ULONG xasize;
3389 DIR_ITEM* xa;
3390
3391 TRACE("(%p, %llx, %llx, %s, %08x, %p, %u)\n", Vcb, subvol->id, inode, name, crc32, data, datalen);
3392
3393 xasize = sizeof(DIR_ITEM) - 1 + (ULONG)strlen(name) + datalen;
3394
3395 xa = ExAllocatePoolWithTag(PagedPool, xasize, ALLOC_TAG);
3396 if (!xa) {
3397 ERR("out of memory\n");
3398 return STATUS_INSUFFICIENT_RESOURCES;
3399 }
3400
3401 xa->key.obj_id = 0;
3402 xa->key.obj_type = 0;
3403 xa->key.offset = 0;
3404 xa->transid = Vcb->superblock.generation;
3405 xa->m = datalen;
3406 xa->n = (UINT16)strlen(name);
3407 xa->type = BTRFS_TYPE_EA;
3408 RtlCopyMemory(xa->name, name, strlen(name));
3409 RtlCopyMemory(xa->name + strlen(name), data, datalen);
3410
3411 if (!insert_tree_item_batch(batchlist, Vcb, subvol, inode, TYPE_XATTR_ITEM, crc32, xa, xasize, Batch_SetXattr, Irp, rollback))
3412 return STATUS_INTERNAL_ERROR;
3413
3414 return STATUS_SUCCESS;
3415 }
3416
3417 static BOOL STDCALL delete_xattr(device_extension* Vcb, root* subvol, UINT64 inode, char* name, UINT32 crc32, PIRP Irp, LIST_ENTRY* rollback) {
3418 KEY searchkey;
3419 traverse_ptr tp;
3420 DIR_ITEM* xa;
3421 NTSTATUS Status;
3422
3423 TRACE("(%p, %llx, %llx, %s, %08x)\n", Vcb, subvol->id, inode, name, crc32);
3424
3425 searchkey.obj_id = inode;
3426 searchkey.obj_type = TYPE_XATTR_ITEM;
3427 searchkey.offset = crc32;
3428
3429 Status = find_item(Vcb, subvol, &tp, &searchkey, FALSE, Irp);
3430 if (!NT_SUCCESS(Status)) {
3431 ERR("error - find_item returned %08x\n", Status);
3432 return FALSE;
3433 }
3434
3435 if (!keycmp(tp.item->key, searchkey)) { // key exists
3436 ULONG size = tp.item->size;
3437
3438 if (tp.item->size < sizeof(DIR_ITEM)) {
3439 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(DIR_ITEM));
3440
3441 return FALSE;
3442 } else {
3443 xa = (DIR_ITEM*)tp.item->data;
3444
3445 while (TRUE) {
3446 ULONG oldxasize;
3447
3448 if (size < sizeof(DIR_ITEM) || size < sizeof(DIR_ITEM) - 1 + xa->m + xa->n) {
3449 ERR("(%llx,%x,%llx) was truncated\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
3450
3451 return FALSE;
3452 }
3453
3454 oldxasize = sizeof(DIR_ITEM) - 1 + xa->m + xa->n;
3455
3456 if (xa->n == strlen(name) && RtlCompareMemory(name, xa->name, xa->n) == xa->n) {
3457 ULONG newsize;
3458 UINT8 *newdata, *dioff;
3459
3460 newsize = tp.item->size - (sizeof(DIR_ITEM) - 1 + xa->n + xa->m);
3461
3462 delete_tree_item(Vcb, &tp, rollback);
3463
3464 if (newsize == 0) {
3465 TRACE("xattr %s deleted\n", name);
3466
3467 return TRUE;
3468 }
3469
3470 // FIXME - deleting collisions almost certainly works, but we should test it properly anyway
3471 newdata = ExAllocatePoolWithTag(PagedPool, newsize, ALLOC_TAG);
3472 if (!newdata) {
3473 ERR("out of memory\n");
3474 return FALSE;
3475 }
3476
3477 if ((UINT8*)xa > tp.item->data) {
3478 RtlCopyMemory(newdata, tp.item->data, (UINT8*)xa - tp.item->data);
3479 dioff = newdata + ((UINT8*)xa - tp.item->data);
3480 } else {
3481 dioff = newdata;
3482 }
3483
3484 if ((UINT8*)&xa->name[xa->n+xa->m] - tp.item->data < tp.item->size)
3485 RtlCopyMemory(dioff, &xa->name[xa->n+xa->m], tp.item->size - ((UINT8*)&xa->name[xa->n+xa->m] - tp.item->data));
3486
3487 insert_tree_item(Vcb, subvol, inode, TYPE_XATTR_ITEM, crc32, newdata, newsize, NULL, Irp, rollback);
3488
3489
3490 return TRUE;
3491 }
3492
3493 if (xa->m + xa->n >= size) { // FIXME - test this works
3494 WARN("xattr %s not found\n", name);
3495
3496 return FALSE;
3497 } else {
3498 xa = (DIR_ITEM*)&xa->name[xa->m + xa->n];
3499 size -= oldxasize;
3500 }
3501 }
3502 }
3503 } else {
3504 WARN("xattr %s not found\n", name);
3505
3506 return FALSE;
3507 }
3508 }
3509
3510 static NTSTATUS insert_sparse_extent(fcb* fcb, UINT64 start, UINT64 length, PIRP Irp, LIST_ENTRY* rollback) {
3511 EXTENT_DATA* ed;
3512 EXTENT_DATA2* ed2;
3513
3514 TRACE("((%llx, %llx), %llx, %llx)\n", fcb->subvol->id, fcb->inode, start, length);
3515
3516 ed = ExAllocatePoolWithTag(PagedPool, sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2), ALLOC_TAG);
3517 if (!ed) {
3518 ERR("out of memory\n");
3519 return STATUS_INSUFFICIENT_RESOURCES;
3520 }
3521
3522 ed->generation = fcb->Vcb->superblock.generation;
3523 ed->decoded_size = length;
3524 ed->compression = BTRFS_COMPRESSION_NONE;
3525 ed->encryption = BTRFS_ENCRYPTION_NONE;
3526 ed->encoding = BTRFS_ENCODING_NONE;
3527 ed->type = EXTENT_TYPE_REGULAR;
3528
3529 ed2 = (EXTENT_DATA2*)ed->data;
3530 ed2->address = 0;
3531 ed2->size = 0;
3532 ed2->offset = 0;
3533 ed2->num_bytes = length;
3534
3535 if (!insert_tree_item(fcb->Vcb, fcb->subvol, fcb->inode, TYPE_EXTENT_DATA, start, ed, sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2), NULL, Irp, rollback)) {
3536 ERR("insert_tree_item failed\n");
3537 return STATUS_INTERNAL_ERROR;
3538 }
3539
3540 return STATUS_SUCCESS;
3541 }
3542
3543 static BOOL insert_tree_item_batch(LIST_ENTRY* batchlist, device_extension* Vcb, root* r, UINT64 objid, UINT64 objtype, UINT64 offset,
3544 void* data, UINT16 datalen, enum batch_operation operation, PIRP Irp, LIST_ENTRY* rollback) {
3545 LIST_ENTRY* le;
3546 batch_root* br = NULL;
3547 batch_item* bi;
3548
3549 le = batchlist->Flink;
3550 while (le != batchlist) {
3551 batch_root* br2 = CONTAINING_RECORD(le, batch_root, list_entry);
3552
3553 if (br2->r == r) {
3554 br = br2;
3555 break;
3556 }
3557
3558 le = le->Flink;
3559 }
3560
3561 if (!br) {
3562 br = ExAllocatePoolWithTag(PagedPool, sizeof(batch_root), ALLOC_TAG);
3563 if (!br) {
3564 ERR("out of memory\n");
3565 return FALSE;
3566 }
3567
3568 br->r = r;
3569 InitializeListHead(&br->items);
3570 InsertTailList(batchlist, &br->list_entry);
3571 }
3572
3573 bi = ExAllocateFromPagedLookasideList(&Vcb->batch_item_lookaside);
3574 if (!bi) {
3575 ERR("out of memory\n");
3576 return FALSE;
3577 }
3578
3579 bi->key.obj_id = objid;
3580 bi->key.obj_type = objtype;
3581 bi->key.offset = offset;
3582 bi->data = data;
3583 bi->datalen = datalen;
3584 bi->operation = operation;
3585
3586 le = br->items.Blink;
3587 while (le != &br->items) {
3588 batch_item* bi2 = CONTAINING_RECORD(le, batch_item, list_entry);
3589
3590 if (keycmp(bi2->key, bi->key) == -1) {
3591 InsertHeadList(&bi2->list_entry, &bi->list_entry);
3592 return TRUE;
3593 }
3594
3595 le = le->Blink;
3596 }
3597
3598 InsertHeadList(&br->items, &bi->list_entry);
3599
3600 return TRUE;
3601 }
3602
3603 typedef struct {
3604 UINT64 address;
3605 UINT64 length;
3606 UINT64 offset;
3607 BOOL changed;
3608 chunk* chunk;
3609 UINT64 skip_start;
3610 UINT64 skip_end;
3611 LIST_ENTRY list_entry;
3612 } extent_range;
3613
3614 static void rationalize_extents(fcb* fcb, PIRP Irp) {
3615 LIST_ENTRY* le;
3616 LIST_ENTRY extent_ranges;
3617 extent_range* er;
3618 BOOL changed = FALSE, truncating = FALSE;
3619 UINT32 num_extents = 0;
3620
3621 InitializeListHead(&extent_ranges);
3622
3623 le = fcb->extents.Flink;
3624 while (le != &fcb->extents) {
3625 extent* ext = CONTAINING_RECORD(le, extent, list_entry);
3626
3627 if ((ext->data->type == EXTENT_TYPE_REGULAR || ext->data->type == EXTENT_TYPE_PREALLOC) && ext->data->compression == BTRFS_COMPRESSION_NONE && ext->unique) {
3628 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ext->data->data;
3629
3630 if (ed2->size != 0) {
3631 LIST_ENTRY* le2;
3632
3633 le2 = extent_ranges.Flink;
3634 while (le2 != &extent_ranges) {
3635 extent_range* er2 = CONTAINING_RECORD(le2, extent_range, list_entry);
3636
3637 if (er2->address == ed2->address) {
3638 er2->skip_start = min(er2->skip_start, ed2->offset);
3639 er2->skip_end = min(er2->skip_end, ed2->size - ed2->offset - ed2->num_bytes);
3640 goto cont;
3641 } else if (er2->address > ed2->address)
3642 break;
3643
3644 le2 = le2->Flink;
3645 }
3646
3647 er = ExAllocatePoolWithTag(PagedPool, sizeof(extent_range), ALLOC_TAG); // FIXME - should be from lookaside?
3648 if (!er) {
3649 ERR("out of memory\n");
3650 goto end;
3651 }
3652
3653 er->address = ed2->address;
3654 er->length = ed2->size;
3655 er->offset = ext->offset - ed2->offset;
3656 er->changed = FALSE;
3657 er->chunk = NULL;
3658 er->skip_start = ed2->offset;
3659 er->skip_end = ed2->size - ed2->offset - ed2->num_bytes;
3660
3661 if (er->skip_start != 0 || er->skip_end != 0)
3662 truncating = TRUE;
3663
3664 InsertHeadList(le2->Blink, &er->list_entry);
3665 num_extents++;
3666 }
3667 }
3668
3669 cont:
3670 le = le->Flink;
3671 }
3672
3673 if (num_extents == 0 || (num_extents == 1 && !truncating))
3674 goto end;
3675
3676 le = extent_ranges.Flink;
3677 while (le != &extent_ranges) {
3678 er = CONTAINING_RECORD(le, extent_range, list_entry);
3679
3680 if (!er->chunk) {
3681 LIST_ENTRY* le2;
3682
3683 er->chunk = get_chunk_from_address(fcb->Vcb, er->address);
3684
3685 if (!er->chunk) {
3686 ERR("get_chunk_from_address(%llx) failed\n", er->address);
3687 goto end;
3688 }
3689
3690 le2 = le->Flink;
3691 while (le2 != &extent_ranges) {
3692 extent_range* er2 = CONTAINING_RECORD(le2, extent_range, list_entry);
3693
3694 if (!er2->chunk && er2->address >= er->chunk->offset && er2->address < er->chunk->offset + er->chunk->chunk_item->size)
3695 er2->chunk = er->chunk;
3696
3697 le2 = le2->Flink;
3698 }
3699 }
3700
3701 le = le->Flink;
3702 }
3703
3704 if (truncating) {
3705 // truncate beginning or end of extent if unused
3706
3707 le = extent_ranges.Flink;
3708 while (le != &extent_ranges) {
3709 er = CONTAINING_RECORD(le, extent_range, list_entry);
3710
3711 if (er->skip_start > 0) {
3712 LIST_ENTRY* le2 = fcb->extents.Flink;
3713 while (le2 != &fcb->extents) {
3714 extent* ext = CONTAINING_RECORD(le2, extent, list_entry);
3715
3716 if ((ext->data->type == EXTENT_TYPE_REGULAR || ext->data->type == EXTENT_TYPE_PREALLOC) && ext->data->compression == BTRFS_COMPRESSION_NONE && ext->unique) {
3717 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ext->data->data;
3718
3719 if (ed2->size != 0 && ed2->address == er->address) {
3720 NTSTATUS Status;
3721
3722 Status = update_changed_extent_ref(fcb->Vcb, er->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3723 -1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM, TRUE, Irp);
3724 if (!NT_SUCCESS(Status)) {
3725 ERR("update_changed_extent_ref returned %08x\n", Status);
3726 goto end;
3727 }
3728
3729 ext->data->decoded_size -= er->skip_start;
3730 ed2->size -= er->skip_start;
3731 ed2->address += er->skip_start;
3732 ed2->offset -= er->skip_start;
3733
3734 add_changed_extent_ref(er->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3735 1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM);
3736 }
3737 }
3738
3739 le2 = le2->Flink;
3740 }
3741
3742 if (!(fcb->inode_item.flags & BTRFS_INODE_NODATASUM)) {
3743 LIST_ENTRY changed_sector_list;
3744
3745 changed_sector* sc = ExAllocatePoolWithTag(PagedPool, sizeof(changed_sector), ALLOC_TAG);
3746 if (!sc) {
3747 ERR("out of memory\n");
3748 goto end;
3749 }
3750
3751 sc->ol.key = er->address;
3752 sc->checksums = NULL;
3753 sc->length = er->skip_start / fcb->Vcb->superblock.sector_size;
3754
3755 sc->deleted = TRUE;
3756
3757 InitializeListHead(&changed_sector_list);
3758 insert_into_ordered_list(&changed_sector_list, &sc->ol);
3759
3760 commit_checksum_changes(fcb->Vcb, &changed_sector_list);
3761 }
3762
3763 decrease_chunk_usage(er->chunk, er->skip_start);
3764
3765 space_list_add(fcb->Vcb, er->chunk, TRUE, er->address, er->skip_start, NULL);
3766
3767 er->address += er->skip_start;
3768 er->length -= er->skip_start;
3769 }
3770
3771 if (er->skip_end > 0) {
3772 LIST_ENTRY* le2 = fcb->extents.Flink;
3773 while (le2 != &fcb->extents) {
3774 extent* ext = CONTAINING_RECORD(le2, extent, list_entry);
3775
3776 if ((ext->data->type == EXTENT_TYPE_REGULAR || ext->data->type == EXTENT_TYPE_PREALLOC) && ext->data->compression == BTRFS_COMPRESSION_NONE && ext->unique) {
3777 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ext->data->data;
3778
3779 if (ed2->size != 0 && ed2->address == er->address) {
3780 NTSTATUS Status;
3781
3782 Status = update_changed_extent_ref(fcb->Vcb, er->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3783 -1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM, TRUE, Irp);
3784 if (!NT_SUCCESS(Status)) {
3785 ERR("update_changed_extent_ref returned %08x\n", Status);
3786 goto end;
3787 }
3788
3789 ext->data->decoded_size -= er->skip_end;
3790 ed2->size -= er->skip_end;
3791
3792 add_changed_extent_ref(er->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3793 1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM);
3794 }
3795 }
3796
3797 le2 = le2->Flink;
3798 }
3799
3800 if (!(fcb->inode_item.flags & BTRFS_INODE_NODATASUM)) {
3801 LIST_ENTRY changed_sector_list;
3802
3803 changed_sector* sc = ExAllocatePoolWithTag(PagedPool, sizeof(changed_sector), ALLOC_TAG);
3804 if (!sc) {
3805 ERR("out of memory\n");
3806 goto end;
3807 }
3808
3809 sc->ol.key = er->address + er->length - er->skip_end;
3810 sc->checksums = NULL;
3811 sc->length = er->skip_end / fcb->Vcb->superblock.sector_size;
3812
3813 sc->deleted = TRUE;
3814
3815 InitializeListHead(&changed_sector_list);
3816 insert_into_ordered_list(&changed_sector_list, &sc->ol);
3817
3818 commit_checksum_changes(fcb->Vcb, &changed_sector_list);
3819 }
3820
3821 decrease_chunk_usage(er->chunk, er->skip_end);
3822
3823 space_list_add(fcb->Vcb, er->chunk, TRUE, er->address + er->length - er->skip_end, er->skip_end, NULL);
3824
3825 er->length -= er->skip_end;
3826 }
3827
3828 le = le->Flink;
3829 }
3830 }
3831
3832 if (num_extents < 2)
3833 goto end;
3834
3835 // merge together adjacent extents
3836 le = extent_ranges.Flink;
3837 while (le != &extent_ranges) {
3838 er = CONTAINING_RECORD(le, extent_range, list_entry);
3839
3840 if (le->Flink != &extent_ranges && er->length < MAX_EXTENT_SIZE) {
3841 extent_range* er2 = CONTAINING_RECORD(le->Flink, extent_range, list_entry);
3842
3843 if (er->chunk == er2->chunk) {
3844 if (er2->address == er->address + er->length && er2->offset >= er->offset + er->length) {
3845 if (er->length + er2->length <= MAX_EXTENT_SIZE) {
3846 er->length += er2->length;
3847 er->changed = TRUE;
3848
3849 RemoveEntryList(&er2->list_entry);
3850 ExFreePool(er2);
3851
3852 changed = TRUE;
3853 continue;
3854 // } else { // FIXME - make changing of beginning of offset work
3855 // er2->length = er2->address + er->length - er->address - MAX_EXTENT_SIZE;
3856 // er2->address = er->address + MAX_EXTENT_SIZE;
3857 // er->length = MAX_EXTENT_SIZE;
3858 }
3859 }
3860 }
3861 }
3862
3863 le = le->Flink;
3864 }
3865
3866 if (!changed)
3867 goto end;
3868
3869 le = fcb->extents.Flink;
3870 while (le != &fcb->extents) {
3871 extent* ext = CONTAINING_RECORD(le, extent, list_entry);
3872
3873 if ((ext->data->type == EXTENT_TYPE_REGULAR || ext->data->type == EXTENT_TYPE_PREALLOC) && ext->data->compression == BTRFS_COMPRESSION_NONE && ext->unique) {
3874 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ext->data->data;
3875
3876 if (ed2->size != 0) {
3877 LIST_ENTRY* le2;
3878
3879 le2 = extent_ranges.Flink;
3880 while (le2 != &extent_ranges) {
3881 extent_range* er2 = CONTAINING_RECORD(le2, extent_range, list_entry);
3882
3883 if (ed2->address >= er2->address && ed2->address + ed2->size <= er2->address + er2->length && er2->changed) {
3884 NTSTATUS Status;
3885
3886 Status = update_changed_extent_ref(fcb->Vcb, er2->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3887 -1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM, TRUE, Irp);
3888 if (!NT_SUCCESS(Status)) {
3889 ERR("update_changed_extent_ref returned %08x\n", Status);
3890 goto end;
3891 }
3892
3893 ed2->offset += ed2->address - er2->address;
3894 ed2->address = er2->address;
3895 ed2->size = er2->length;
3896 ext->data->decoded_size = ed2->size;
3897
3898 add_changed_extent_ref(er2->chunk, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset,
3899 1, fcb->inode_item.flags & BTRFS_INODE_NODATASUM);
3900
3901 break;
3902 }
3903
3904 le2 = le2->Flink;
3905 }
3906 }
3907 }
3908
3909 le = le->Flink;
3910 }
3911
3912 end:
3913 while (!IsListEmpty(&extent_ranges)) {
3914 le = RemoveHeadList(&extent_ranges);
3915 er = CONTAINING_RECORD(le, extent_range, list_entry);
3916
3917 ExFreePool(er);
3918 }
3919 }
3920
3921 void flush_fcb(fcb* fcb, BOOL cache, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) {
3922 traverse_ptr tp;
3923 KEY searchkey;
3924 NTSTATUS Status;
3925 INODE_ITEM* ii;
3926 UINT64 ii_offset;
3927 #ifdef DEBUG_PARANOID
3928 UINT64 old_size = 0;
3929 BOOL extents_changed;
3930 #endif
3931
3932 // ExAcquireResourceExclusiveLite(fcb->Header.Resource, TRUE);
3933
3934 while (!IsListEmpty(&fcb->index_list)) {
3935 LIST_ENTRY* le = RemoveHeadList(&fcb->index_list);
3936 index_entry* ie = CONTAINING_RECORD(le, index_entry, list_entry);
3937
3938 if (ie->utf8.Buffer) ExFreePool(ie->utf8.Buffer);
3939 if (ie->filepart_uc.Buffer) ExFreePool(ie->filepart_uc.Buffer);
3940 ExFreePool(ie);
3941 }
3942
3943 fcb->index_loaded = FALSE;
3944
3945 if (fcb->ads) {
3946 if (fcb->deleted)
3947 delete_xattr(fcb->Vcb, fcb->subvol, fcb->inode, fcb->adsxattr.Buffer, fcb->adshash, Irp, rollback);
3948 else {
3949 Status = set_xattr(fcb->Vcb, batchlist, fcb->subvol, fcb->inode, fcb->adsxattr.Buffer, fcb->adshash, (UINT8*)fcb->adsdata.Buffer, fcb->adsdata.Length, Irp, rollback);
3950 if (!NT_SUCCESS(Status)) {
3951 ERR("set_xattr returned %08x\n", Status);
3952 goto end;
3953 }
3954 }
3955 goto end;
3956 }
3957
3958 #ifdef DEBUG_PARANOID
3959 extents_changed = fcb->extents_changed;
3960 #endif
3961
3962 if (fcb->extents_changed) {
3963 BOOL b;
3964 traverse_ptr next_tp;
3965 LIST_ENTRY* le;
3966 BOOL prealloc = FALSE, extents_inline = FALSE;
3967 UINT64 last_end;
3968
3969 // delete ignored extent items
3970 le = fcb->extents.Flink;
3971 while (le != &fcb->extents) {
3972 LIST_ENTRY* le2 = le->Flink;
3973 extent* ext = CONTAINING_RECORD(le, extent, list_entry);
3974
3975 if (ext->ignore) {
3976 RemoveEntryList(&ext->list_entry);
3977 ExFreePool(ext->data);
3978 ExFreePool(ext);
3979 }
3980
3981 le = le2;
3982 }
3983
3984 if (!IsListEmpty(&fcb->extents)) {
3985 rationalize_extents(fcb, Irp);
3986
3987 // merge together adjacent EXTENT_DATAs pointing to same extent
3988
3989 le = fcb->extents.Flink;
3990 while (le != &fcb->extents) {
3991 LIST_ENTRY* le2 = le->Flink;
3992 extent* ext = CONTAINING_RECORD(le, extent, list_entry);
3993
3994 if ((ext->data->type == EXTENT_TYPE_REGULAR || ext->data->type == EXTENT_TYPE_PREALLOC) && le->Flink != &fcb->extents) {
3995 extent* nextext = CONTAINING_RECORD(le->Flink, extent, list_entry);
3996
3997 if (ext->data->type == nextext->data->type) {
3998 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ext->data->data;
3999 EXTENT_DATA2* ned2 = (EXTENT_DATA2*)nextext->data->data;
4000
4001 if (ed2->size != 0 && ed2->address == ned2->address && ed2->size == ned2->size &&
4002 nextext->offset == ext->offset + ed2->num_bytes && ned2->offset == ed2->offset + ed2->num_bytes) {
4003 chunk* c;
4004
4005 ext->data->generation = fcb->Vcb->superblock.generation;
4006 ed2->num_bytes += ned2->num_bytes;
4007
4008 RemoveEntryList(&nextext->list_entry);
4009 ExFreePool(nextext->data);
4010 ExFreePool(nextext);
4011
4012 c = get_chunk_from_address(fcb->Vcb, ed2->address);
4013
4014 if (!c) {
4015 ERR("get_chunk_from_address(%llx) failed\n", ed2->address);
4016 } else {
4017 Status = update_changed_extent_ref(fcb->Vcb, c, ed2->address, ed2->size, fcb->subvol->id, fcb->inode, ext->offset - ed2->offset, -1,
4018 fcb->inode_item.flags & BTRFS_INODE_NODATASUM, FALSE, Irp);
4019 if (!NT_SUCCESS(Status)) {
4020 ERR("update_changed_extent_ref returned %08x\n", Status);
4021 goto end;
4022 }
4023 }
4024
4025 le2 = le;
4026 }
4027 }
4028 }
4029
4030 le = le2;
4031 }
4032 }
4033
4034 if (!fcb->created) {
4035 // delete existing EXTENT_DATA items
4036
4037 searchkey.obj_id = fcb->inode;
4038 searchkey.obj_type = TYPE_EXTENT_DATA;
4039 searchkey.offset = 0;
4040
4041 Status = find_item(fcb->Vcb, fcb->subvol, &tp, &searchkey, FALSE, Irp);
4042 if (!NT_SUCCESS(Status)) {
4043 ERR("error - find_item returned %08x\n", Status);
4044 goto end;
4045 }
4046
4047 do {
4048 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type)
4049 delete_tree_item(fcb->Vcb, &tp, rollback);
4050
4051 b = find_next_item(fcb->Vcb, &tp, &next_tp, FALSE, Irp);
4052
4053 if (b) {
4054 tp = next_tp;
4055
4056 if (tp.item->key.obj_id > searchkey.obj_id || (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type > searchkey.obj_type))
4057 break;
4058 }
4059 } while (b);
4060 }
4061
4062 if (!fcb->deleted) {
4063 // add new EXTENT_DATAs
4064
4065 last_end = 0;
4066
4067 le = fcb->extents.Flink;
4068 while (le != &fcb->extents) {
4069 extent* ext = CONTAINING_RECORD(le, extent, list_entry);
4070 EXTENT_DATA* ed;
4071
4072 if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_NO_HOLES) && ext->offset > last_end) {
4073 Status = insert_sparse_extent(fcb, last_end, ext->offset - last_end, Irp, rollback);
4074 if (!NT_SUCCESS(Status)) {
4075 ERR("insert_sparse_extent returned %08x\n", Status);
4076 goto end;
4077 }
4078 }
4079
4080 ed = ExAllocatePoolWithTag(PagedPool, ext->datalen, ALLOC_TAG);
4081 if (!ed) {
4082 ERR("out of memory\n");
4083 Status = STATUS_INSUFFICIENT_RESOURCES;
4084 goto end;
4085 }
4086
4087 RtlCopyMemory(ed, ext->data, ext->datalen);
4088
4089 if (!insert_tree_item_batch(batchlist, fcb->Vcb, fcb->subvol, fcb->inode, TYPE_EXTENT_DATA, ext->offset,
4090 ed, ext->datalen, Batch_Insert, Irp, rollback)) {
4091 ERR("insert_tree_item_batch failed\n");
4092 Status = STATUS_INTERNAL_ERROR;
4093 goto end;
4094 }
4095
4096 if (ext->datalen >= sizeof(EXTENT_DATA) && ed->type == EXTENT_TYPE_PREALLOC)
4097 prealloc = TRUE;
4098
4099 if (ext->datalen >= sizeof(EXTENT_DATA) && ed->type == EXTENT_TYPE_INLINE)
4100 extents_inline = TRUE;
4101
4102 if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_NO_HOLES)) {
4103 if (ed->type == EXTENT_TYPE_INLINE)
4104 last_end = ext->offset + ed->decoded_size;
4105 else {
4106 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
4107
4108 last_end = ext->offset + ed2->num_bytes;
4109 }
4110 }
4111
4112 le = le->Flink;
4113 }
4114
4115 if (!(fcb->Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_NO_HOLES) && !extents_inline &&
4116 sector_align(fcb->inode_item.st_size, fcb->Vcb->superblock.sector_size) > last_end) {
4117 Status = insert_sparse_extent(fcb, last_end, sector_align(fcb->inode_item.st_size, fcb->Vcb->superblock.sector_size) - last_end, Irp, rollback);
4118 if (!NT_SUCCESS(Status)) {
4119 ERR("insert_sparse_extent returned %08x\n", Status);
4120 goto end;
4121 }
4122 }
4123
4124 // update prealloc flag in INODE_ITEM
4125
4126 if (!prealloc)
4127 fcb->inode_item.flags &= ~BTRFS_INODE_PREALLOC;
4128 else
4129 fcb->inode_item.flags |= BTRFS_INODE_PREALLOC;
4130
4131 fcb->inode_item_changed = TRUE;
4132 }
4133
4134 fcb->extents_changed = FALSE;
4135 }
4136
4137 if ((!fcb->created && fcb->inode_item_changed) || cache) {
4138 searchkey.obj_id = fcb->inode;
4139 searchkey.obj_type = TYPE_INODE_ITEM;
4140 searchkey.offset = 0xffffffffffffffff;
4141
4142 Status = find_item(fcb->Vcb, fcb->subvol, &tp, &searchkey, FALSE, Irp);
4143 if (!NT_SUCCESS(Status)) {
4144 ERR("error - find_item returned %08x\n", Status);
4145 goto end;
4146 }
4147
4148 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
4149 if (cache) {
4150 ii = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_ITEM), ALLOC_TAG);
4151 if (!ii) {
4152 ERR("out of memory\n");
4153 goto end;
4154 }
4155
4156 RtlCopyMemory(ii, &fcb->inode_item, sizeof(INODE_ITEM));
4157
4158 if (!insert_tree_item(fcb->Vcb, fcb->subvol, fcb->inode, TYPE_INODE_ITEM, 0, ii, sizeof(INODE_ITEM), NULL, Irp, rollback)) {
4159 ERR("insert_tree_item failed\n");
4160 goto end;
4161 }
4162
4163 ii_offset = 0;
4164 } else {
4165 ERR("could not find INODE_ITEM for inode %llx in subvol %llx\n", fcb->inode, fcb->subvol->id);
4166 int3;
4167 goto end;
4168 }
4169 } else {
4170 #ifdef DEBUG_PARANOID
4171 INODE_ITEM* ii2 = (INODE_ITEM*)tp.item->data;
4172
4173 old_size = ii2->st_size;
4174 #endif
4175
4176 ii_offset = tp.item->key.offset;
4177 }
4178
4179 if (!cache)
4180 delete_tree_item(fcb->Vcb, &tp, rollback);
4181 else {
4182 searchkey.obj_id = fcb->inode;
4183 searchkey.obj_type = TYPE_INODE_ITEM;
4184 searchkey.offset = ii_offset;
4185
4186 Status = find_item(fcb->Vcb, fcb->subvol, &tp, &searchkey, FALSE, Irp);
4187 if (!NT_SUCCESS(Status)) {
4188 ERR("error - find_item returned %08x\n", Status);
4189 goto end;
4190 }
4191
4192 if (keycmp(tp.item->key, searchkey)) {
4193 ERR("could not find INODE_ITEM for inode %llx in subvol %llx\n", fcb->inode, fcb->subvol->id);
4194 int3;
4195 goto end;
4196 } else
4197 RtlCopyMemory(tp.item->data, &fcb->inode_item, min(tp.item->size, sizeof(INODE_ITEM)));
4198 }
4199 } else
4200 ii_offset = 0;
4201
4202 #ifdef DEBUG_PARANOID
4203 if (!extents_changed && fcb->type != BTRFS_TYPE_DIRECTORY && old_size != fcb->inode_item.st_size) {
4204 ERR("error - size has changed but extents not marked as changed\n");
4205 int3;
4206 }
4207 #endif
4208
4209 fcb->created = FALSE;
4210
4211 if (fcb->deleted) {
4212 traverse_ptr tp2;
4213
4214 // delete XATTR_ITEMs
4215
4216 searchkey.obj_id = fcb->inode;
4217 searchkey.obj_type = TYPE_XATTR_ITEM;
4218 searchkey.offset = 0;
4219
4220 Status = find_item(fcb->Vcb, fcb->subvol, &tp, &searchkey, FALSE, Irp);
4221 if (!NT_SUCCESS(Status)) {
4222 ERR("error - find_item returned %08x\n", Status);
4223 goto end;
4224 }
4225
4226 while (find_next_item(fcb->Vcb, &tp, &tp2, FALSE, Irp)) {
4227 tp = tp2;
4228
4229 if (tp.item->key.obj_id == fcb->inode) {
4230 // FIXME - do metadata thing here too?
4231 if (tp.item->key.obj_type == TYPE_XATTR_ITEM) {
4232 delete_tree_item(fcb->Vcb, &tp, rollback);
4233 TRACE("deleting (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
4234 }
4235 } else
4236 break;
4237 }
4238
4239 goto end;
4240 }
4241
4242 if (!cache && fcb->inode_item_changed) {
4243 ii = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_ITEM), ALLOC_TAG);
4244 if (!ii) {
4245 ERR("out of memory\n");
4246 goto end;
4247 }
4248
4249 RtlCopyMemory(ii, &fcb->inode_item, sizeof(INODE_ITEM));
4250
4251 if (!insert_tree_item_batch(batchlist, fcb->Vcb, fcb->subvol, fcb->inode, TYPE_INODE_ITEM, ii_offset, ii, sizeof(INODE_ITEM),
4252 Batch_Insert, Irp, rollback)) {
4253 ERR("insert_tree_item_batch failed\n");
4254 goto end;
4255 }
4256
4257 fcb->inode_item_changed = FALSE;
4258 }
4259
4260 if (fcb->sd_dirty) {
4261 Status = set_xattr(fcb->Vcb, batchlist, fcb->subvol, fcb->inode, EA_NTACL, EA_NTACL_HASH, (UINT8*)fcb->sd, RtlLengthSecurityDescriptor(fcb->sd), Irp, rollback);
4262 if (!NT_SUCCESS(Status)) {
4263 ERR("set_xattr returned %08x\n", Status);
4264 }
4265
4266 fcb->sd_dirty = FALSE;
4267 }
4268
4269 if (fcb->atts_changed) {
4270 if (!fcb->atts_deleted) {
4271 UINT8 val[16], *val2;
4272 ULONG atts = fcb->atts;
4273
4274 TRACE("inserting new DOSATTRIB xattr\n");
4275
4276 val2 = &val[sizeof(val) - 1];
4277
4278 do {
4279 UINT8 c = atts % 16;
4280 *val2 = (c >= 0 && c <= 9) ? (c + '0') : (c - 0xa + 'a');
4281
4282 val2--;
4283 atts >>= 4;
4284 } while (atts != 0);
4285
4286 *val2 = 'x';
4287 val2--;
4288 *val2 = '0';
4289
4290 Status = set_xattr(fcb->Vcb, batchlist, fcb->subvol, fcb->inode, EA_DOSATTRIB, EA_DOSATTRIB_HASH, val2, val + sizeof(val) - val2, Irp, rollback);
4291 if (!NT_SUCCESS(Status)) {
4292 ERR("set_xattr returned %08x\n", Status);
4293 goto end;
4294 }
4295 } else
4296 delete_xattr(fcb->Vcb, fcb->subvol, fcb->inode, EA_DOSATTRIB, EA_DOSATTRIB_HASH, Irp, rollback);
4297
4298 fcb->atts_changed = FALSE;
4299 fcb->atts_deleted = FALSE;
4300 }
4301
4302 if (fcb->reparse_xattr_changed) {
4303 if (fcb->reparse_xattr.Buffer && fcb->reparse_xattr.Length > 0) {
4304 Status = set_xattr(fcb->Vcb, batchlist, fcb->subvol, fcb->inode, EA_REPARSE, EA_REPARSE_HASH, (UINT8*)fcb->reparse_xattr.Buffer, fcb->reparse_xattr.Length, Irp, rollback);
4305 if (!NT_SUCCESS(Status)) {
4306 ERR("set_xattr returned %08x\n", Status);
4307 goto end;
4308 }
4309 } else
4310 delete_xattr(fcb->Vcb, fcb->subvol, fcb->inode, EA_REPARSE, EA_REPARSE_HASH, Irp, rollback);
4311
4312 fcb->reparse_xattr_changed = FALSE;
4313 }
4314
4315 if (fcb->ea_changed) {
4316 if (fcb->ea_xattr.Buffer && fcb->ea_xattr.Length > 0) {
4317 Status = set_xattr(fcb->Vcb, batchlist, fcb->subvol, fcb->inode, EA_EA, EA_EA_HASH, (UINT8*)fcb->ea_xattr.Buffer, fcb->ea_xattr.Length, Irp, rollback);
4318 if (!NT_SUCCESS(Status)) {
4319 ERR("set_xattr returned %08x\n", Status);
4320 goto end;
4321 }
4322 } else
4323 delete_xattr(fcb->Vcb, fcb->subvol, fcb->inode, EA_EA, EA_EA_HASH, Irp, rollback);
4324
4325 fcb->ea_changed = FALSE;
4326 }
4327
4328 end:
4329 fcb->dirty = FALSE;
4330
4331 // ExReleaseResourceLite(fcb->Header.Resource);
4332 return;
4333 }
4334
4335 static NTSTATUS drop_chunk(device_extension* Vcb, chunk* c, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) {
4336 NTSTATUS Status;
4337 KEY searchkey;
4338 traverse_ptr tp;
4339 UINT64 i, factor;
4340 CHUNK_ITEM_STRIPE* cis;
4341
4342 TRACE("dropping chunk %llx\n", c->offset);
4343
4344 // remove free space cache
4345 if (c->cache) {
4346 c->cache->deleted = TRUE;
4347
4348 flush_fcb(c->cache, TRUE, batchlist, Irp, rollback);
4349
4350 free_fcb(c->cache);
4351
4352 searchkey.obj_id = FREE_SPACE_CACHE_ID;
4353 searchkey.obj_type = 0;
4354 searchkey.offset = c->offset;
4355
4356 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4357 if (!NT_SUCCESS(Status)) {
4358 ERR("error - find_item returned %08x\n", Status);
4359 return Status;
4360 }
4361
4362 if (!keycmp(tp.item->key, searchkey)) {
4363 delete_tree_item(Vcb, &tp, rollback);
4364 }
4365 }
4366
4367 if (c->chunk_item->type & BLOCK_FLAG_RAID0)
4368 factor = c->chunk_item->num_stripes;
4369 else if (c->chunk_item->type & BLOCK_FLAG_RAID10)
4370 factor = c->chunk_item->num_stripes / c->chunk_item->sub_stripes;
4371 else // SINGLE, DUPLICATE, RAID1
4372 factor = 1;
4373
4374 cis = (CHUNK_ITEM_STRIPE*)&c->chunk_item[1];
4375 for (i = 0; i < c->chunk_item->num_stripes; i++) {
4376 if (!c->created) {
4377 // remove DEV_EXTENTs from tree 4
4378 searchkey.obj_id = cis[i].dev_id;
4379 searchkey.obj_type = TYPE_DEV_EXTENT;
4380 searchkey.offset = cis[i].offset;
4381
4382 Status = find_item(Vcb, Vcb->dev_root, &tp, &searchkey, FALSE, Irp);
4383 if (!NT_SUCCESS(Status)) {
4384 ERR("error - find_item returned %08x\n", Status);
4385 return Status;
4386 }
4387
4388 if (!keycmp(tp.item->key, searchkey)) {
4389 delete_tree_item(Vcb, &tp, rollback);
4390
4391 if (tp.item->size >= sizeof(DEV_EXTENT)) {
4392 DEV_EXTENT* de = (DEV_EXTENT*)tp.item->data;
4393
4394 c->devices[i]->devitem.bytes_used -= de->length;
4395
4396 space_list_add2(Vcb, &c->devices[i]->space, NULL, cis[i].offset, de->length, rollback);
4397 }
4398 } else
4399 WARN("could not find (%llx,%x,%llx) in dev tree\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset);
4400 } else {
4401 UINT64 len = c->chunk_item->size / factor;
4402
4403 c->devices[i]->devitem.bytes_used -= len;
4404 space_list_add2(Vcb, &c->devices[i]->space, NULL, cis[i].offset, len, rollback);
4405 }
4406 }
4407
4408 // modify DEV_ITEMs in chunk tree
4409 for (i = 0; i < c->chunk_item->num_stripes; i++) {
4410 if (c->devices[i]) {
4411 UINT64 j;
4412 DEV_ITEM* di;
4413
4414 searchkey.obj_id = 1;
4415 searchkey.obj_type = TYPE_DEV_ITEM;
4416 searchkey.offset = c->devices[i]->devitem.dev_id;
4417
4418 Status = find_item(Vcb, Vcb->chunk_root, &tp, &searchkey, FALSE, Irp);
4419 if (!NT_SUCCESS(Status)) {
4420 ERR("error - find_item returned %08x\n", Status);
4421 return Status;
4422 }
4423
4424 if (keycmp(tp.item->key, searchkey)) {
4425 ERR("error - could not find DEV_ITEM for device %llx\n", searchkey.offset);
4426 return STATUS_INTERNAL_ERROR;
4427 }
4428
4429 delete_tree_item(Vcb, &tp, rollback);
4430
4431 di = ExAllocatePoolWithTag(PagedPool, sizeof(DEV_ITEM), ALLOC_TAG);
4432 if (!di) {
4433 ERR("out of memory\n");
4434 return STATUS_INSUFFICIENT_RESOURCES;
4435 }
4436
4437 RtlCopyMemory(di, &c->devices[i]->devitem, sizeof(DEV_ITEM));
4438
4439 if (!insert_tree_item(Vcb, Vcb->chunk_root, 1, TYPE_DEV_ITEM, c->devices[i]->devitem.dev_id, di, sizeof(DEV_ITEM), NULL, Irp, rollback)) {
4440 ERR("insert_tree_item failed\n");
4441 return STATUS_INTERNAL_ERROR;
4442 }
4443
4444 for (j = i + 1; j < c->chunk_item->num_stripes; j++) {
4445 if (c->devices[j] == c->devices[i])
4446 c->devices[j] = NULL;
4447 }
4448 }
4449 }
4450
4451 if (!c->created) {
4452 // remove CHUNK_ITEM from chunk tree
4453 searchkey.obj_id = 0x100;
4454 searchkey.obj_type = TYPE_CHUNK_ITEM;
4455 searchkey.offset = c->offset;
4456
4457 Status = find_item(Vcb, Vcb->chunk_root, &tp, &searchkey, FALSE, Irp);
4458 if (!NT_SUCCESS(Status)) {
4459 ERR("error - find_item returned %08x\n", Status);
4460 return Status;
4461 }
4462
4463 if (!keycmp(tp.item->key, searchkey))
4464 delete_tree_item(Vcb, &tp, rollback);
4465 else
4466 WARN("could not find CHUNK_ITEM for chunk %llx\n", c->offset);
4467
4468 // remove BLOCK_GROUP_ITEM from extent tree
4469 searchkey.obj_id = c->offset;
4470 searchkey.obj_type = TYPE_BLOCK_GROUP_ITEM;
4471 searchkey.offset = 0xffffffffffffffff;
4472
4473 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
4474 if (!NT_SUCCESS(Status)) {
4475 ERR("error - find_item returned %08x\n", Status);
4476 return Status;
4477 }
4478
4479 if (tp.item->key.obj_id == searchkey.obj_id && tp.item->key.obj_type == searchkey.obj_type)
4480 delete_tree_item(Vcb, &tp, rollback);
4481 else
4482 WARN("could not find BLOCK_GROUP_ITEM for chunk %llx\n", c->offset);
4483 }
4484
4485 if (c->chunk_item->type & BLOCK_FLAG_SYSTEM)
4486 remove_from_bootstrap(Vcb, 0x100, TYPE_CHUNK_ITEM, c->offset);
4487
4488 RemoveEntryList(&c->list_entry);
4489
4490 if (c->list_entry_changed.Flink)
4491 RemoveEntryList(&c->list_entry_changed);
4492
4493 ExFreePool(c->chunk_item);
4494 ExFreePool(c->devices);
4495
4496 while (!IsListEmpty(&c->space)) {
4497 space* s = CONTAINING_RECORD(c->space.Flink, space, list_entry);
4498
4499 RemoveEntryList(&s->list_entry);
4500 ExFreePool(s);
4501 }
4502
4503 while (!IsListEmpty(&c->deleting)) {
4504 space* s = CONTAINING_RECORD(c->deleting.Flink, space, list_entry);
4505
4506 RemoveEntryList(&s->list_entry);
4507 ExFreePool(s);
4508 }
4509
4510 ExDeleteResourceLite(&c->lock);
4511 ExDeleteResourceLite(&c->changed_extents_lock);
4512
4513 ExFreePool(c);
4514
4515 return STATUS_SUCCESS;
4516 }
4517
4518 static NTSTATUS update_chunks(device_extension* Vcb, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) {
4519 LIST_ENTRY *le = Vcb->chunks_changed.Flink, *le2;
4520 NTSTATUS Status;
4521 UINT64 used_minus_cache;
4522
4523 ExAcquireResourceExclusiveLite(&Vcb->chunk_lock, TRUE);
4524
4525 // FIXME - do tree chunks before data chunks
4526
4527 while (le != &Vcb->chunks_changed) {
4528 chunk* c = CONTAINING_RECORD(le, chunk, list_entry_changed);
4529
4530 le2 = le->Flink;
4531
4532 ExAcquireResourceExclusiveLite(&c->lock, TRUE);
4533
4534 used_minus_cache = c->used;
4535
4536 // subtract self-hosted cache
4537 if (used_minus_cache > 0 && c->chunk_item->type & BLOCK_FLAG_DATA && c->cache && c->cache->inode_item.st_size == c->used) {
4538 LIST_ENTRY* le3;
4539
4540 le3 = c->cache->extents.Flink;
4541 while (le3 != &c->cache->extents) {
4542 extent* ext = CONTAINING_RECORD(le3, extent, list_entry);
4543 EXTENT_DATA* ed = ext->data;
4544
4545 if (!ext->ignore) {
4546 if (ext->datalen < sizeof(EXTENT_DATA)) {
4547 ERR("extent %llx was %u bytes, expected at least %u\n", ext->offset, ext->datalen, sizeof(EXTENT_DATA));
4548 break;
4549 }
4550
4551 if (ed->type == EXTENT_TYPE_REGULAR || ed->type == EXTENT_TYPE_PREALLOC) {
4552 EXTENT_DATA2* ed2 = (EXTENT_DATA2*)ed->data;
4553
4554 if (ext->datalen < sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2)) {
4555 ERR("extent %llx was %u bytes, expected at least %u\n", ext->offset, ext->datalen,
4556 sizeof(EXTENT_DATA) - 1 + sizeof(EXTENT_DATA2));
4557 break;
4558 }
4559
4560 if (ed2->size != 0 && ed2->address >= c->offset && ed2->address + ed2->size <= c->offset + c->chunk_item->size)
4561 used_minus_cache -= ed2->size;
4562 }
4563 }
4564
4565 le3 = le3->Flink;
4566 }
4567 }
4568
4569 if (used_minus_cache == 0) {
4570 Status = drop_chunk(Vcb, c, batchlist, Irp, rollback);
4571 if (!NT_SUCCESS(Status)) {
4572 ERR("drop_chunk returned %08x\n", Status);
4573 ExReleaseResourceLite(&c->lock);
4574 ExReleaseResourceLite(&Vcb->chunk_lock);
4575 return Status;
4576 }
4577 } else if (c->created) {
4578 Status = create_chunk(Vcb, c, Irp, rollback);
4579 if (!NT_SUCCESS(Status)) {
4580 ERR("create_chunk returned %08x\n", Status);
4581 ExReleaseResourceLite(&c->lock);
4582 ExReleaseResourceLite(&Vcb->chunk_lock);
4583 return Status;
4584 }
4585 }
4586
4587 if (used_minus_cache > 0)
4588 ExReleaseResourceLite(&c->lock);
4589
4590 le = le2;
4591 }
4592
4593 ExReleaseResourceLite(&Vcb->chunk_lock);
4594
4595 return STATUS_SUCCESS;
4596 }
4597
4598 static NTSTATUS delete_root_ref(device_extension* Vcb, UINT64 subvolid, UINT64 parsubvolid, UINT64 parinode, PANSI_STRING utf8, PIRP Irp, LIST_ENTRY* rollback) {
4599 KEY searchkey;
4600 traverse_ptr tp;
4601 NTSTATUS Status;
4602
4603 searchkey.obj_id = parsubvolid;
4604 searchkey.obj_type = TYPE_ROOT_REF;
4605 searchkey.offset = subvolid;
4606
4607 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4608 if (!NT_SUCCESS(Status)) {
4609 ERR("error - find_item returned %08x\n", Status);
4610 return Status;
4611 }
4612
4613 if (!keycmp(searchkey, tp.item->key)) {
4614 if (tp.item->size < sizeof(ROOT_REF)) {
4615 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(ROOT_REF));
4616 return STATUS_INTERNAL_ERROR;
4617 } else {
4618 ROOT_REF* rr;
4619 ULONG len;
4620
4621 rr = (ROOT_REF*)tp.item->data;
4622 len = tp.item->size;
4623
4624 do {
4625 ULONG itemlen;
4626
4627 if (len < sizeof(ROOT_REF) || len < sizeof(ROOT_REF) - 1 + rr->n) {
4628 ERR("(%llx,%x,%llx) was truncated\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
4629 break;
4630 }
4631
4632 itemlen = sizeof(ROOT_REF) - sizeof(char) + rr->n;
4633
4634 if (rr->dir == parinode && rr->n == utf8->Length && RtlCompareMemory(rr->name, utf8->Buffer, rr->n) == rr->n) {
4635 ULONG newlen = tp.item->size - itemlen;
4636
4637 delete_tree_item(Vcb, &tp, rollback);
4638
4639 if (newlen == 0) {
4640 TRACE("deleting (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
4641 } else {
4642 UINT8 *newrr = ExAllocatePoolWithTag(PagedPool, newlen, ALLOC_TAG), *rroff;
4643
4644 if (!newrr) {
4645 ERR("out of memory\n");
4646 return STATUS_INSUFFICIENT_RESOURCES;
4647 }
4648
4649 TRACE("modifying (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
4650
4651 if ((UINT8*)rr > tp.item->data) {
4652 RtlCopyMemory(newrr, tp.item->data, (UINT8*)rr - tp.item->data);
4653 rroff = newrr + ((UINT8*)rr - tp.item->data);
4654 } else {
4655 rroff = newrr;
4656 }
4657
4658 if ((UINT8*)&rr->name[rr->n] - tp.item->data < tp.item->size)
4659 RtlCopyMemory(rroff, &rr->name[rr->n], tp.item->size - ((UINT8*)&rr->name[rr->n] - tp.item->data));
4660
4661 insert_tree_item(Vcb, Vcb->root_root, tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset, newrr, newlen, NULL, Irp, rollback);
4662 }
4663
4664 break;
4665 }
4666
4667 if (len > itemlen) {
4668 len -= itemlen;
4669 rr = (ROOT_REF*)&rr->name[rr->n];
4670 } else
4671 break;
4672 } while (len > 0);
4673 }
4674 } else {
4675 WARN("could not find ROOT_REF entry for subvol %llx in %llx\n", searchkey.offset, searchkey.obj_id);
4676 return STATUS_NOT_FOUND;
4677 }
4678
4679 return STATUS_SUCCESS;
4680 }
4681
4682 static NTSTATUS add_root_ref(device_extension* Vcb, UINT64 subvolid, UINT64 parsubvolid, ROOT_REF* rr, PIRP Irp, LIST_ENTRY* rollback) {
4683 KEY searchkey;
4684 traverse_ptr tp;
4685 NTSTATUS Status;
4686
4687 searchkey.obj_id = parsubvolid;
4688 searchkey.obj_type = TYPE_ROOT_REF;
4689 searchkey.offset = subvolid;
4690
4691 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4692 if (!NT_SUCCESS(Status)) {
4693 ERR("error - find_item returned %08x\n", Status);
4694 return Status;
4695 }
4696
4697 if (!keycmp(searchkey, tp.item->key)) {
4698 ULONG rrsize = tp.item->size + sizeof(ROOT_REF) - 1 + rr->n;
4699 UINT8* rr2;
4700
4701 rr2 = ExAllocatePoolWithTag(PagedPool, rrsize, ALLOC_TAG);
4702 if (!rr2) {
4703 ERR("out of memory\n");
4704 return STATUS_INSUFFICIENT_RESOURCES;
4705 }
4706
4707 if (tp.item->size > 0)
4708 RtlCopyMemory(rr2, tp.item->data, tp.item->size);
4709
4710 RtlCopyMemory(rr2 + tp.item->size, rr, sizeof(ROOT_REF) - 1 + rr->n);
4711 ExFreePool(rr);
4712
4713 delete_tree_item(Vcb, &tp, rollback);
4714
4715 if (!insert_tree_item(Vcb, Vcb->root_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, rr2, rrsize, NULL, Irp, rollback)) {
4716 ERR("error - failed to insert item\n");
4717 ExFreePool(rr2);
4718 return STATUS_INTERNAL_ERROR;
4719 }
4720 } else {
4721 if (!insert_tree_item(Vcb, Vcb->root_root, searchkey.obj_id, searchkey.obj_type, searchkey.offset, rr, sizeof(ROOT_REF) - 1 + rr->n, NULL, Irp, rollback)) {
4722 ERR("error - failed to insert item\n");
4723 ExFreePool(rr);
4724 return STATUS_INTERNAL_ERROR;
4725 }
4726 }
4727
4728 return STATUS_SUCCESS;
4729 }
4730
4731 static NTSTATUS STDCALL update_root_backref(device_extension* Vcb, UINT64 subvolid, UINT64 parsubvolid, PIRP Irp, LIST_ENTRY* rollback) {
4732 KEY searchkey;
4733 traverse_ptr tp;
4734 UINT8* data;
4735 ULONG datalen;
4736 NTSTATUS Status;
4737
4738 searchkey.obj_id = parsubvolid;
4739 searchkey.obj_type = TYPE_ROOT_REF;
4740 searchkey.offset = subvolid;
4741
4742 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4743 if (!NT_SUCCESS(Status)) {
4744 ERR("error - find_item returned %08x\n", Status);
4745 return Status;
4746 }
4747
4748 if (!keycmp(tp.item->key, searchkey) && tp.item->size > 0) {
4749 datalen = tp.item->size;
4750
4751 data = ExAllocatePoolWithTag(PagedPool, datalen, ALLOC_TAG);
4752 if (!data) {
4753 ERR("out of memory\n");
4754 return STATUS_INSUFFICIENT_RESOURCES;
4755 }
4756
4757 RtlCopyMemory(data, tp.item->data, datalen);
4758 } else {
4759 datalen = 0;
4760 }
4761
4762 searchkey.obj_id = subvolid;
4763 searchkey.obj_type = TYPE_ROOT_BACKREF;
4764 searchkey.offset = parsubvolid;
4765
4766 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4767 if (!NT_SUCCESS(Status)) {
4768 ERR("error - find_item returned %08x\n", Status);
4769
4770 if (datalen > 0)
4771 ExFreePool(data);
4772
4773 return Status;
4774 }
4775
4776 if (!keycmp(tp.item->key, searchkey))
4777 delete_tree_item(Vcb, &tp, rollback);
4778
4779 if (datalen > 0) {
4780 if (!insert_tree_item(Vcb, Vcb->root_root, subvolid, TYPE_ROOT_BACKREF, parsubvolid, data, datalen, NULL, Irp, rollback)) {
4781 ERR("error - failed to insert item\n");
4782 ExFreePool(data);
4783 return STATUS_INTERNAL_ERROR;
4784 }
4785 }
4786
4787 return STATUS_SUCCESS;
4788 }
4789
4790 static NTSTATUS add_root_item_to_cache(device_extension* Vcb, UINT64 root, PIRP Irp, LIST_ENTRY* rollback) {
4791 KEY searchkey;
4792 traverse_ptr tp;
4793 NTSTATUS Status;
4794
4795 searchkey.obj_id = root;
4796 searchkey.obj_type = TYPE_ROOT_ITEM;
4797 searchkey.offset = 0xffffffffffffffff;
4798
4799 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
4800 if (!NT_SUCCESS(Status)) {
4801 ERR("error - find_item returned %08x\n", Status);
4802 return Status;
4803 }
4804
4805 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
4806 ERR("could not find ROOT_ITEM for tree %llx\n", searchkey.obj_id);
4807 int3;
4808 return STATUS_INTERNAL_ERROR;
4809 }
4810
4811 if (tp.item->size < sizeof(ROOT_ITEM)) { // if not full length, create new entry with new bits zeroed
4812 ROOT_ITEM* ri = ExAllocatePoolWithTag(PagedPool, sizeof(ROOT_ITEM), ALLOC_TAG);
4813 if (!ri) {
4814 ERR("out of memory\n");
4815 return STATUS_INSUFFICIENT_RESOURCES;
4816 }
4817
4818 if (tp.item->size > 0)
4819 RtlCopyMemory(ri, tp.item->data, tp.item->size);
4820
4821 RtlZeroMemory(((UINT8*)ri) + tp.item->size, sizeof(ROOT_ITEM) - tp.item->size);
4822
4823 delete_tree_item(Vcb, &tp, rollback);
4824
4825 if (!insert_tree_item(Vcb, Vcb->root_root, searchkey.obj_id, searchkey.obj_type, tp.item->key.offset, ri, sizeof(ROOT_ITEM), NULL, Irp, rollback)) {
4826 ERR("insert_tree_item failed\n");
4827 return STATUS_INTERNAL_ERROR;
4828 }
4829 } else {
4830 tp.tree->write = TRUE;
4831 }
4832
4833 return STATUS_SUCCESS;
4834 }
4835
4836 static NTSTATUS add_dir_item(device_extension* Vcb, root* subvol, UINT64 inode, UINT32 crc32, DIR_ITEM* di, ULONG disize, PIRP Irp, LIST_ENTRY* rollback) {
4837 KEY searchkey;
4838 traverse_ptr tp;
4839 UINT8* di2;
4840 NTSTATUS Status;
4841
4842 searchkey.obj_id = inode;
4843 searchkey.obj_type = TYPE_DIR_ITEM;
4844 searchkey.offset = crc32;
4845
4846 Status = find_item(Vcb, subvol, &tp, &searchkey, FALSE, Irp);
4847 if (!NT_SUCCESS(Status)) {
4848 ERR("error - find_item returned %08x\n", Status);
4849 return Status;
4850 }
4851
4852 if (!keycmp(tp.item->key, searchkey)) {
4853 ULONG maxlen = Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node);
4854
4855 if (tp.item->size + disize > maxlen) {
4856 WARN("DIR_ITEM was longer than maxlen (%u + %u > %u)\n", tp.item->size, disize, maxlen);
4857 return STATUS_INTERNAL_ERROR;
4858 }
4859
4860 di2 = ExAllocatePoolWithTag(PagedPool, tp.item->size + disize, ALLOC_TAG);
4861 if (!di2) {
4862 ERR("out of memory\n");
4863 return STATUS_INSUFFICIENT_RESOURCES;
4864 }
4865
4866 if (tp.item->size > 0)
4867 RtlCopyMemory(di2, tp.item->data, tp.item->size);
4868
4869 RtlCopyMemory(di2 + tp.item->size, di, disize);
4870
4871 delete_tree_item(Vcb, &tp, rollback);
4872
4873 insert_tree_item(Vcb, subvol, inode, TYPE_DIR_ITEM, crc32, di2, tp.item->size + disize, NULL, Irp, rollback);
4874
4875 ExFreePool(di);
4876 } else {
4877 insert_tree_item(Vcb, subvol, inode, TYPE_DIR_ITEM, crc32, di, disize, NULL, Irp, rollback);
4878 }
4879
4880 return STATUS_SUCCESS;
4881 }
4882
4883 static NTSTATUS add_inode_extref(device_extension* Vcb, root* subvol, UINT64 inode, UINT64 parinode, UINT64 index, PANSI_STRING utf8, PIRP Irp, LIST_ENTRY* rollback) {
4884 KEY searchkey;
4885 traverse_ptr tp;
4886 INODE_EXTREF* ier;
4887 NTSTATUS Status;
4888
4889 searchkey.obj_id = inode;
4890 searchkey.obj_type = TYPE_INODE_EXTREF;
4891 searchkey.offset = calc_crc32c((UINT32)parinode, (UINT8*)utf8->Buffer, utf8->Length);
4892
4893 Status = find_item(Vcb, subvol, &tp, &searchkey, FALSE, Irp);
4894 if (!NT_SUCCESS(Status)) {
4895 ERR("error - find_item returned %08x\n", Status);
4896 return Status;
4897 }
4898
4899 if (!keycmp(searchkey, tp.item->key)) {
4900 ULONG iersize = tp.item->size + sizeof(INODE_EXTREF) - 1 + utf8->Length;
4901 UINT8* ier2;
4902 UINT32 maxlen = Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node);
4903
4904 if (iersize > maxlen) {
4905 ERR("item would be too long (%u > %u)\n", iersize, maxlen);
4906 return STATUS_INTERNAL_ERROR;
4907 }
4908
4909 ier2 = ExAllocatePoolWithTag(PagedPool, iersize, ALLOC_TAG);
4910 if (!ier2) {
4911 ERR("out of memory\n");
4912 return STATUS_INSUFFICIENT_RESOURCES;
4913 }
4914
4915 if (tp.item->size > 0)
4916 RtlCopyMemory(ier2, tp.item->data, tp.item->size);
4917
4918 ier = (INODE_EXTREF*)&ier2[tp.item->size];
4919 ier->dir = parinode;
4920 ier->index = index;
4921 ier->n = utf8->Length;
4922 RtlCopyMemory(ier->name, utf8->Buffer, utf8->Length);
4923
4924 delete_tree_item(Vcb, &tp, rollback);
4925
4926 if (!insert_tree_item(Vcb, subvol, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ier2, iersize, NULL, Irp, rollback)) {
4927 ERR("error - failed to insert item\n");
4928 return STATUS_INTERNAL_ERROR;
4929 }
4930 } else {
4931 ier = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_EXTREF) - 1 + utf8->Length, ALLOC_TAG);
4932 if (!ier) {
4933 ERR("out of memory\n");
4934 return STATUS_INSUFFICIENT_RESOURCES;
4935 }
4936
4937 ier->dir = parinode;
4938 ier->index = index;
4939 ier->n = utf8->Length;
4940 RtlCopyMemory(ier->name, utf8->Buffer, utf8->Length);
4941
4942 if (!insert_tree_item(Vcb, subvol, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ier, sizeof(INODE_EXTREF) - 1 + utf8->Length, NULL, Irp, rollback)) {
4943 ERR("error - failed to insert item\n");
4944 return STATUS_INTERNAL_ERROR;
4945 }
4946 }
4947
4948 return STATUS_SUCCESS;
4949 }
4950
4951 static NTSTATUS add_inode_ref(device_extension* Vcb, root* subvol, UINT64 inode, UINT64 parinode, UINT64 index, PANSI_STRING utf8, PIRP Irp, LIST_ENTRY* rollback) {
4952 KEY searchkey;
4953 traverse_ptr tp;
4954 INODE_REF* ir;
4955 NTSTATUS Status;
4956
4957 searchkey.obj_id = inode;
4958 searchkey.obj_type = TYPE_INODE_REF;
4959 searchkey.offset = parinode;
4960
4961 Status = find_item(Vcb, subvol, &tp, &searchkey, FALSE, Irp);
4962 if (!NT_SUCCESS(Status)) {
4963 ERR("error - find_item returned %08x\n", Status);
4964 return Status;
4965 }
4966
4967 if (!keycmp(searchkey, tp.item->key)) {
4968 ULONG irsize = tp.item->size + sizeof(INODE_REF) - 1 + utf8->Length;
4969 UINT8* ir2;
4970 UINT32 maxlen = Vcb->superblock.node_size - sizeof(tree_header) - sizeof(leaf_node);
4971
4972 if (irsize > maxlen) {
4973 if (Vcb->superblock.incompat_flags & BTRFS_INCOMPAT_FLAGS_EXTENDED_IREF) {
4974 TRACE("INODE_REF too long, creating INODE_EXTREF\n");
4975 return add_inode_extref(Vcb, subvol, inode, parinode, index, utf8, Irp, rollback);
4976 } else {
4977 ERR("item would be too long (%u > %u)\n", irsize, maxlen);
4978 return STATUS_INTERNAL_ERROR;
4979 }
4980 }
4981
4982 ir2 = ExAllocatePoolWithTag(PagedPool, irsize, ALLOC_TAG);
4983 if (!ir2) {
4984 ERR("out of memory\n");
4985 return STATUS_INSUFFICIENT_RESOURCES;
4986 }
4987
4988 if (tp.item->size > 0)
4989 RtlCopyMemory(ir2, tp.item->data, tp.item->size);
4990
4991 ir = (INODE_REF*)&ir2[tp.item->size];
4992 ir->index = index;
4993 ir->n = utf8->Length;
4994 RtlCopyMemory(ir->name, utf8->Buffer, utf8->Length);
4995
4996 delete_tree_item(Vcb, &tp, rollback);
4997
4998 if (!insert_tree_item(Vcb, subvol, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ir2, irsize, NULL, Irp, rollback)) {
4999 ERR("error - failed to insert item\n");
5000 return STATUS_INTERNAL_ERROR;
5001 }
5002 } else {
5003 ir = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_REF) - 1 + utf8->Length, ALLOC_TAG);
5004 if (!ir) {
5005 ERR("out of memory\n");
5006 return STATUS_INSUFFICIENT_RESOURCES;
5007 }
5008
5009 ir->index = index;
5010 ir->n = utf8->Length;
5011 RtlCopyMemory(ir->name, utf8->Buffer, utf8->Length);
5012
5013 if (!insert_tree_item(Vcb, subvol, searchkey.obj_id, searchkey.obj_type, searchkey.offset, ir, sizeof(INODE_REF) - 1 + ir->n, NULL, Irp, rollback)) {
5014 ERR("error - failed to insert item\n");
5015 return STATUS_INTERNAL_ERROR;
5016 }
5017 }
5018
5019 return STATUS_SUCCESS;
5020 }
5021
5022 static NTSTATUS flush_fileref(file_ref* fileref, LIST_ENTRY* batchlist, PIRP Irp, LIST_ENTRY* rollback) {
5023 NTSTATUS Status;
5024
5025 // if fileref created and then immediately deleted, do nothing
5026 if (fileref->created && fileref->deleted) {
5027 fileref->dirty = FALSE;
5028 return STATUS_SUCCESS;
5029 }
5030
5031 if (fileref->fcb->ads) {
5032 fileref->dirty = FALSE;
5033 return STATUS_SUCCESS;
5034 }
5035
5036 if (fileref->created) {
5037 ULONG disize;
5038 DIR_ITEM *di, *di2;
5039 UINT32 crc32;
5040
5041 crc32 = calc_crc32c(0xfffffffe, (UINT8*)fileref->utf8.Buffer, fileref->utf8.Length);
5042
5043 disize = sizeof(DIR_ITEM) - 1 + fileref->utf8.Length;
5044 di = ExAllocatePoolWithTag(PagedPool, disize, ALLOC_TAG);
5045 if (!di) {
5046 ERR("out of memory\n");
5047 return STATUS_INSUFFICIENT_RESOURCES;
5048 }
5049
5050 if (fileref->parent->fcb->subvol == fileref->fcb->subvol) {
5051 di->key.obj_id = fileref->fcb->inode;
5052 di->key.obj_type = TYPE_INODE_ITEM;
5053 di->key.offset = 0;
5054 } else { // subvolume
5055 di->key.obj_id = fileref->fcb->subvol->id;
5056 di->key.obj_type = TYPE_ROOT_ITEM;
5057 di->key.offset = 0xffffffffffffffff;
5058 }
5059
5060 di->transid = fileref->fcb->Vcb->superblock.generation;
5061 di->m = 0;
5062 di->n = (UINT16)fileref->utf8.Length;
5063 di->type = fileref->fcb->type;
5064 RtlCopyMemory(di->name, fileref->utf8.Buffer, fileref->utf8.Length);
5065
5066 di2 = ExAllocatePoolWithTag(PagedPool, disize, ALLOC_TAG);
5067 if (!di2) {
5068 ERR("out of memory\n");
5069 return STATUS_INSUFFICIENT_RESOURCES;
5070 }
5071
5072 RtlCopyMemory(di2, di, disize);
5073
5074 if (!insert_tree_item_batch(batchlist, fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, TYPE_DIR_INDEX, fileref->index,
5075 di, disize, Batch_Insert, Irp, rollback)) {
5076 ERR("insert_tree_item_batch failed\n");
5077 return STATUS_INTERNAL_ERROR;
5078 }
5079
5080 if (!insert_tree_item_batch(batchlist, fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, TYPE_DIR_ITEM, crc32,
5081 di2, disize, Batch_DirItem, Irp, rollback)) {
5082 ERR("insert_tree_item_batch failed\n");
5083 return STATUS_INTERNAL_ERROR;
5084 }
5085
5086 if (fileref->parent->fcb->subvol == fileref->fcb->subvol) {
5087 INODE_REF* ir;
5088
5089 ir = ExAllocatePoolWithTag(PagedPool, sizeof(INODE_REF) - 1 + fileref->utf8.Length, ALLOC_TAG);
5090 if (!ir) {
5091 ERR("out of memory\n");
5092 return STATUS_INSUFFICIENT_RESOURCES;
5093 }
5094
5095 ir->index = fileref->index;
5096 ir->n = fileref->utf8.Length;
5097 RtlCopyMemory(ir->name, fileref->utf8.Buffer, ir->n);
5098
5099 if (!insert_tree_item_batch(batchlist, fileref->fcb->Vcb, fileref->fcb->subvol, fileref->fcb->inode, TYPE_INODE_REF, fileref->parent->fcb->inode,
5100 ir, sizeof(INODE_REF) - 1 + ir->n, Batch_InodeRef, Irp, rollback)) {
5101 ERR("insert_tree_item_batch failed\n");
5102 return STATUS_INTERNAL_ERROR;
5103 }
5104 } else {
5105 ULONG rrlen;
5106 ROOT_REF* rr;
5107
5108 rrlen = sizeof(ROOT_REF) - 1 + fileref->utf8.Length;
5109
5110 rr = ExAllocatePoolWithTag(PagedPool, rrlen, ALLOC_TAG);
5111 if (!rr) {
5112 ERR("out of memory\n");
5113 return STATUS_INSUFFICIENT_RESOURCES;
5114 }
5115
5116 rr->dir = fileref->parent->fcb->inode;
5117 rr->index = fileref->index;
5118 rr->n = fileref->utf8.Length;
5119 RtlCopyMemory(rr->name, fileref->utf8.Buffer, fileref->utf8.Length);
5120
5121 Status = add_root_ref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, rr, Irp, rollback);
5122 if (!NT_SUCCESS(Status)) {
5123 ERR("add_root_ref returned %08x\n", Status);
5124 return Status;
5125 }
5126
5127 Status = update_root_backref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, Irp, rollback);
5128 if (!NT_SUCCESS(Status)) {
5129 ERR("update_root_backref returned %08x\n", Status);
5130 return Status;
5131 }
5132 }
5133
5134 fileref->created = FALSE;
5135 } else if (fileref->deleted) {
5136 UINT32 crc32;
5137 KEY searchkey;
5138 traverse_ptr tp;
5139 ANSI_STRING* name;
5140
5141 if (fileref->oldutf8.Buffer)
5142 name = &fileref->oldutf8;
5143 else
5144 name = &fileref->utf8;
5145
5146 crc32 = calc_crc32c(0xfffffffe, (UINT8*)name->Buffer, name->Length);
5147
5148 TRACE("deleting %.*S\n", file_desc_fileref(fileref));
5149
5150 // delete DIR_ITEM (0x54)
5151
5152 Status = delete_dir_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, crc32, name, Irp, rollback);
5153 if (!NT_SUCCESS(Status)) {
5154 ERR("delete_dir_item returned %08x\n", Status);
5155 return Status;
5156 }
5157
5158 if (fileref->parent->fcb->subvol == fileref->fcb->subvol) {
5159 // delete INODE_REF (0xc)
5160
5161 Status = delete_inode_ref(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->fcb->inode, fileref->parent->fcb->inode, name, Irp, rollback);
5162 if (!NT_SUCCESS(Status)) {
5163 ERR("delete_inode_ref returned %08x\n", Status);
5164 return Status;
5165 }
5166 } else { // subvolume
5167 Status = delete_root_ref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, fileref->parent->fcb->inode, name, Irp, rollback);
5168 if (!NT_SUCCESS(Status)) {
5169 ERR("delete_root_ref returned %08x\n", Status);
5170 }
5171
5172 Status = update_root_backref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, Irp, rollback);
5173 if (!NT_SUCCESS(Status)) {
5174 ERR("update_root_backref returned %08x\n", Status);
5175 return Status;
5176 }
5177 }
5178
5179 // delete DIR_INDEX (0x60)
5180
5181 searchkey.obj_id = fileref->parent->fcb->inode;
5182 searchkey.obj_type = TYPE_DIR_INDEX;
5183 searchkey.offset = fileref->index;
5184
5185 Status = find_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, &tp, &searchkey, FALSE, Irp);
5186 if (!NT_SUCCESS(Status)) {
5187 ERR("error - find_item returned %08x\n", Status);
5188 Status = STATUS_INTERNAL_ERROR;
5189 return Status;
5190 }
5191
5192 if (!keycmp(searchkey, tp.item->key)) {
5193 delete_tree_item(fileref->fcb->Vcb, &tp, rollback);
5194 TRACE("deleting (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
5195 }
5196
5197 if (fileref->oldutf8.Buffer) {
5198 ExFreePool(fileref->oldutf8.Buffer);
5199 fileref->oldutf8.Buffer = NULL;
5200 }
5201 } else { // rename or change type
5202 PANSI_STRING oldutf8 = fileref->oldutf8.Buffer ? &fileref->oldutf8 : &fileref->utf8;
5203 UINT32 crc32, oldcrc32;
5204 ULONG disize;
5205 DIR_ITEM *di, *di2;
5206 KEY searchkey;
5207 traverse_ptr tp;
5208
5209 crc32 = calc_crc32c(0xfffffffe, (UINT8*)fileref->utf8.Buffer, fileref->utf8.Length);
5210
5211 if (!fileref->oldutf8.Buffer)
5212 oldcrc32 = crc32;
5213 else
5214 oldcrc32 = calc_crc32c(0xfffffffe, (UINT8*)fileref->oldutf8.Buffer, fileref->oldutf8.Length);
5215
5216 // delete DIR_ITEM (0x54)
5217
5218 Status = delete_dir_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, oldcrc32, oldutf8, Irp, rollback);
5219 if (!NT_SUCCESS(Status)) {
5220 ERR("delete_dir_item returned %08x\n", Status);
5221 return Status;
5222 }
5223
5224 // add DIR_ITEM (0x54)
5225
5226 disize = sizeof(DIR_ITEM) - 1 + fileref->utf8.Length;
5227 di = ExAllocatePoolWithTag(PagedPool, disize, ALLOC_TAG);
5228 if (!di) {
5229 ERR("out of memory\n");
5230 return STATUS_INSUFFICIENT_RESOURCES;
5231 }
5232
5233 di2 = ExAllocatePoolWithTag(PagedPool, disize, ALLOC_TAG);
5234 if (!di2) {
5235 ERR("out of memory\n");
5236 ExFreePool(di);
5237 return STATUS_INSUFFICIENT_RESOURCES;
5238 }
5239
5240 if (fileref->parent->fcb->subvol == fileref->fcb->subvol) {
5241 di->key.obj_id = fileref->fcb->inode;
5242 di->key.obj_type = TYPE_INODE_ITEM;
5243 di->key.offset = 0;
5244 } else { // subvolume
5245 di->key.obj_id = fileref->fcb->subvol->id;
5246 di->key.obj_type = TYPE_ROOT_ITEM;
5247 di->key.offset = 0xffffffffffffffff;
5248 }
5249
5250 di->transid = fileref->fcb->Vcb->superblock.generation;
5251 di->m = 0;
5252 di->n = (UINT16)fileref->utf8.Length;
5253 di->type = fileref->fcb->type;
5254 RtlCopyMemory(di->name, fileref->utf8.Buffer, fileref->utf8.Length);
5255
5256 RtlCopyMemory(di2, di, disize);
5257
5258 Status = add_dir_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, crc32, di, disize, Irp, rollback);
5259 if (!NT_SUCCESS(Status)) {
5260 ERR("add_dir_item returned %08x\n", Status);
5261 return Status;
5262 }
5263
5264 if (fileref->parent->fcb->subvol == fileref->fcb->subvol) {
5265 // delete INODE_REF (0xc)
5266
5267 Status = delete_inode_ref(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->fcb->inode, fileref->parent->fcb->inode, oldutf8, Irp, rollback);
5268 if (!NT_SUCCESS(Status)) {
5269 ERR("delete_inode_ref returned %08x\n", Status);
5270 return Status;
5271 }
5272
5273 // add INODE_REF (0xc)
5274
5275 Status = add_inode_ref(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->fcb->inode, fileref->parent->fcb->inode, fileref->index, &fileref->utf8, Irp, rollback);
5276 if (!NT_SUCCESS(Status)) {
5277 ERR("add_inode_ref returned %08x\n", Status);
5278 return Status;
5279 }
5280 } else { // subvolume
5281 ULONG rrlen;
5282 ROOT_REF* rr;
5283
5284 // FIXME - make sure this works with duff subvols within snapshots
5285
5286 Status = delete_root_ref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, fileref->parent->fcb->inode, oldutf8, Irp, rollback);
5287 if (!NT_SUCCESS(Status)) {
5288 ERR("delete_root_ref returned %08x\n", Status);
5289 }
5290
5291 rrlen = sizeof(ROOT_REF) - 1 + fileref->utf8.Length;
5292
5293 rr = ExAllocatePoolWithTag(PagedPool, rrlen, ALLOC_TAG);
5294 if (!rr) {
5295 ERR("out of memory\n");
5296 return STATUS_INSUFFICIENT_RESOURCES;
5297 }
5298
5299 rr->dir = fileref->parent->fcb->inode;
5300 rr->index = fileref->index;
5301 rr->n = fileref->utf8.Length;
5302 RtlCopyMemory(rr->name, fileref->utf8.Buffer, fileref->utf8.Length);
5303
5304 Status = add_root_ref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, rr, Irp, rollback);
5305 if (!NT_SUCCESS(Status)) {
5306 ERR("add_root_ref returned %08x\n", Status);
5307 return Status;
5308 }
5309
5310 Status = update_root_backref(fileref->fcb->Vcb, fileref->fcb->subvol->id, fileref->parent->fcb->subvol->id, Irp, rollback);
5311 if (!NT_SUCCESS(Status)) {
5312 ERR("update_root_backref returned %08x\n", Status);
5313 return Status;
5314 }
5315 }
5316
5317 // delete DIR_INDEX (0x60)
5318
5319 searchkey.obj_id = fileref->parent->fcb->inode;
5320 searchkey.obj_type = TYPE_DIR_INDEX;
5321 searchkey.offset = fileref->index;
5322
5323 Status = find_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, &tp, &searchkey, FALSE, Irp);
5324 if (!NT_SUCCESS(Status)) {
5325 ERR("error - find_item returned %08x\n", Status);
5326 Status = STATUS_INTERNAL_ERROR;
5327 return Status;
5328 }
5329
5330 if (!keycmp(searchkey, tp.item->key)) {
5331 delete_tree_item(fileref->fcb->Vcb, &tp, rollback);
5332 TRACE("deleting (%llx,%x,%llx)\n", tp.item->key.obj_id, tp.item->key.obj_type, tp.item->key.offset);
5333 } else
5334 WARN("could not find (%llx,%x,%llx) in subvol %llx\n", searchkey.obj_id, searchkey.obj_type, searchkey.offset, fileref->fcb->subvol->id);
5335
5336 // add DIR_INDEX (0x60)
5337
5338 if (!insert_tree_item(fileref->fcb->Vcb, fileref->parent->fcb->subvol, fileref->parent->fcb->inode, TYPE_DIR_INDEX, fileref->index, di2, disize, NULL, Irp, rollback)) {
5339 ERR("insert_tree_item failed\n");
5340 Status = STATUS_INTERNAL_ERROR;
5341 return Status;
5342 }
5343
5344 if (fileref->oldutf8.Buffer) {
5345 ExFreePool(fileref->oldutf8.Buffer);
5346 fileref->oldutf8.Buffer = NULL;
5347 }
5348 }
5349
5350 fileref->dirty = FALSE;
5351
5352 return STATUS_SUCCESS;
5353 }
5354
5355 NTSTATUS STDCALL do_write(device_extension* Vcb, PIRP Irp, LIST_ENTRY* rollback) {
5356 NTSTATUS Status;
5357 LIST_ENTRY *le, batchlist;
5358 BOOL cache_changed = FALSE;
5359 #ifdef DEBUG_FLUSH_TIMES
5360 UINT64 filerefs = 0, fcbs = 0;
5361 LARGE_INTEGER freq, time1, time2;
5362 #endif
5363 #ifdef DEBUG_WRITE_LOOPS
5364 UINT loops = 0;
5365 #endif
5366
5367 TRACE("(%p)\n", Vcb);
5368
5369 InitializeListHead(&batchlist);
5370
5371 #ifdef DEBUG_FLUSH_TIMES
5372 time1 = KeQueryPerformanceCounter(&freq);
5373 #endif
5374
5375 while (!IsListEmpty(&Vcb->dirty_filerefs)) {
5376 dirty_fileref* dirt;
5377
5378 le = RemoveHeadList(&Vcb->dirty_filerefs);
5379
5380 dirt = CONTAINING_RECORD(le, dirty_fileref, list_entry);
5381
5382 flush_fileref(dirt->fileref, &batchlist, Irp, rollback);
5383 free_fileref(dirt->fileref);
5384 ExFreePool(dirt);
5385
5386 #ifdef DEBUG_FLUSH_TIMES
5387 filerefs++;
5388 #endif
5389 }
5390
5391 commit_batch_list(Vcb, &batchlist, Irp, rollback);
5392
5393 #ifdef DEBUG_FLUSH_TIMES
5394 time2 = KeQueryPerformanceCounter(NULL);
5395
5396 ERR("flushed %llu filerefs in %llu (freq = %llu)\n", filerefs, time2.QuadPart - time1.QuadPart, freq.QuadPart);
5397
5398 time1 = KeQueryPerformanceCounter(&freq);
5399 #endif
5400
5401 // We process deleted streams first, so we don't run over our xattr
5402 // limit unless we absolutely have to.
5403
5404 le = Vcb->dirty_fcbs.Flink;
5405 while (le != &Vcb->dirty_fcbs) {
5406 dirty_fcb* dirt;
5407 LIST_ENTRY* le2 = le->Flink;
5408
5409 dirt = CONTAINING_RECORD(le, dirty_fcb, list_entry);
5410
5411 if (dirt->fcb->deleted && dirt->fcb->ads) {
5412 RemoveEntryList(le);
5413
5414 flush_fcb(dirt->fcb, FALSE, &batchlist, Irp, rollback);
5415 free_fcb(dirt->fcb);
5416 ExFreePool(dirt);
5417
5418 #ifdef DEBUG_FLUSH_TIMES
5419 fcbs++;
5420 #endif
5421 }
5422
5423 le = le2;
5424 }
5425
5426 le = Vcb->dirty_fcbs.Flink;
5427 while (le != &Vcb->dirty_fcbs) {
5428 dirty_fcb* dirt;
5429 LIST_ENTRY* le2 = le->Flink;
5430
5431 dirt = CONTAINING_RECORD(le, dirty_fcb, list_entry);
5432
5433 if (dirt->fcb->subvol != Vcb->root_root || dirt->fcb->deleted) {
5434 RemoveEntryList(le);
5435
5436 flush_fcb(dirt->fcb, FALSE, &batchlist, Irp, rollback);
5437 free_fcb(dirt->fcb);
5438 ExFreePool(dirt);
5439
5440 #ifdef DEBUG_FLUSH_TIMES
5441 fcbs++;
5442 #endif
5443 }
5444
5445 le = le2;
5446 }
5447
5448 commit_batch_list(Vcb, &batchlist, Irp, rollback);
5449
5450 #ifdef DEBUG_FLUSH_TIMES
5451 time2 = KeQueryPerformanceCounter(NULL);
5452
5453 ERR("flushed %llu fcbs in %llu (freq = %llu)\n", filerefs, time2.QuadPart - time1.QuadPart, freq.QuadPart);
5454 #endif
5455
5456 ExAcquireResourceExclusiveLite(&Vcb->checksum_lock, TRUE);
5457 if (!IsListEmpty(&Vcb->sector_checksums)) {
5458 update_checksum_tree(Vcb, Irp, rollback);
5459 }
5460 ExReleaseResourceLite(&Vcb->checksum_lock);
5461
5462 if (!IsListEmpty(&Vcb->drop_roots)) {
5463 Status = drop_roots(Vcb, Irp, rollback);
5464
5465 if (!NT_SUCCESS(Status)) {
5466 ERR("drop_roots returned %08x\n", Status);
5467 return Status;
5468 }
5469 }
5470
5471 if (!IsListEmpty(&Vcb->chunks_changed)) {
5472 Status = update_chunks(Vcb, &batchlist, Irp, rollback);
5473
5474 if (!NT_SUCCESS(Status)) {
5475 ERR("update_chunks returned %08x\n", Status);
5476 return Status;
5477 }
5478 }
5479
5480 commit_batch_list(Vcb, &batchlist, Irp, rollback);
5481
5482 // If only changing superblock, e.g. changing label, we still need to rewrite
5483 // the root tree so the generations match, otherwise you won't be able to mount on Linux.
5484 if (!Vcb->root_root->treeholder.tree || !Vcb->root_root->treeholder.tree->write) {
5485 KEY searchkey;
5486
5487 traverse_ptr tp;
5488
5489 searchkey.obj_id = 0;
5490 searchkey.obj_type = 0;
5491 searchkey.offset = 0;
5492
5493 Status = find_item(Vcb, Vcb->root_root, &tp, &searchkey, FALSE, Irp);
5494 if (!NT_SUCCESS(Status)) {
5495 ERR("error - find_item returned %08x\n", Status);
5496 return Status;
5497 }
5498
5499 Vcb->root_root->treeholder.tree->write = TRUE;
5500 }
5501
5502 // make sure we always update the extent tree
5503 Status = add_root_item_to_cache(Vcb, BTRFS_ROOT_EXTENT, Irp, rollback);
5504 if (!NT_SUCCESS(Status)) {
5505 ERR("add_root_item_to_cache returned %08x\n", Status);
5506 return Status;
5507 }
5508
5509 do {
5510 Status = add_parents(Vcb, Irp, rollback);
5511 if (!NT_SUCCESS(Status)) {
5512 ERR("add_parents returned %08x\n", Status);
5513 goto end;
5514 }
5515
5516 Status = do_splits(Vcb, Irp, rollback);
5517 if (!NT_SUCCESS(Status)) {
5518 ERR("do_splits returned %08x\n", Status);
5519 goto end;
5520 }
5521
5522 Status = allocate_tree_extents(Vcb, Irp, rollback);
5523 if (!NT_SUCCESS(Status)) {
5524 ERR("add_parents returned %08x\n", Status);
5525 goto end;
5526 }
5527
5528 Status = update_chunk_usage(Vcb, Irp, rollback);
5529 if (!NT_SUCCESS(Status)) {
5530 ERR("update_chunk_usage returned %08x\n", Status);
5531 goto end;
5532 }
5533
5534 Status = allocate_cache(Vcb, &cache_changed, Irp, rollback);
5535 if (!NT_SUCCESS(Status)) {
5536 ERR("allocate_cache returned %08x\n", Status);
5537 goto end;
5538 }
5539
5540 #ifdef DEBUG_WRITE_LOOPS
5541 loops++;
5542
5543 if (cache_changed)
5544 ERR("cache has changed, looping again\n");
5545 #endif
5546 } while (cache_changed || !trees_consistent(Vcb, rollback));
5547
5548 #ifdef DEBUG_WRITE_LOOPS
5549 ERR("%u loops\n", loops);
5550 #endif
5551
5552 TRACE("trees consistent\n");
5553
5554 Status = update_root_root(Vcb, Irp, rollback);
5555 if (!NT_SUCCESS(Status)) {
5556 ERR("update_root_root returned %08x\n", Status);
5557 goto end;
5558 }
5559
5560 Status = write_trees(Vcb, Irp);
5561 if (!NT_SUCCESS(Status)) {
5562 ERR("write_trees returned %08x\n", Status);
5563 goto end;
5564 }
5565
5566 Vcb->superblock.cache_generation = Vcb->superblock.generation;
5567
5568 Status = write_superblocks(Vcb, Irp);
5569 if (!NT_SUCCESS(Status)) {
5570 ERR("write_superblocks returned %08x\n", Status);
5571 goto end;
5572 }
5573
5574 clean_space_cache(Vcb);
5575
5576 Vcb->superblock.generation++;
5577
5578 Status = STATUS_SUCCESS;
5579
5580 le = Vcb->trees.Flink;
5581 while (le != &Vcb->trees) {
5582 tree* t = CONTAINING_RECORD(le, tree, list_entry);
5583
5584 #ifdef DEBUG_PARANOID
5585 KEY searchkey;
5586 traverse_ptr tp;
5587
5588 searchkey.obj_id = t->header.address;
5589 searchkey.obj_type = TYPE_METADATA_ITEM;
5590 searchkey.offset = 0xffffffffffffffff;
5591
5592 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
5593 if (!NT_SUCCESS(Status)) {
5594 ERR("error - find_item returned %08x\n", Status);
5595 int3;
5596 }
5597
5598 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
5599 searchkey.obj_id = t->header.address;
5600 searchkey.obj_type = TYPE_EXTENT_ITEM;
5601 searchkey.offset = 0xffffffffffffffff;
5602
5603 Status = find_item(Vcb, Vcb->extent_root, &tp, &searchkey, FALSE, Irp);
5604 if (!NT_SUCCESS(Status)) {
5605 ERR("error - find_item returned %08x\n", Status);
5606 int3;
5607 }
5608
5609 if (tp.item->key.obj_id != searchkey.obj_id || tp.item->key.obj_type != searchkey.obj_type) {
5610 ERR("error - could not find entry in extent tree for tree at %llx\n", t->header.address);
5611 int3;
5612 }
5613 }
5614 #endif
5615
5616 t->write = FALSE;
5617
5618 le = le->Flink;
5619 }
5620
5621 Vcb->need_write = FALSE;
5622
5623 while (!IsListEmpty(&Vcb->drop_roots)) {
5624 LIST_ENTRY* le = RemoveHeadList(&Vcb->drop_roots);
5625 root* r = CONTAINING_RECORD(le, root, list_entry);
5626
5627 ExDeleteResourceLite(&r->nonpaged->load_tree_lock);
5628 ExFreePool(r->nonpaged);
5629 ExFreePool(r);
5630 }
5631
5632 end:
5633 TRACE("do_write returning %08x\n", Status);
5634
5635 return Status;
5636 }
5637
5638 #ifdef DEBUG_STATS
5639 static void print_stats(device_extension* Vcb) {
5640 ERR("READ STATS:\n");
5641 ERR("number of reads: %llu\n", Vcb->stats.num_reads);
5642 ERR("data read: %llu bytes\n", Vcb->stats.data_read);
5643 ERR("total time taken: %llu\n", Vcb->stats.read_total_time);
5644 ERR("csum time taken: %llu\n", Vcb->stats.read_csum_time);
5645 ERR("disk time taken: %llu\n", Vcb->stats.read_disk_time);
5646 ERR("other time taken: %llu\n", Vcb->stats.read_total_time - Vcb->stats.read_csum_time - Vcb->stats.read_disk_time);
5647
5648 RtlZeroMemory(&Vcb->stats, sizeof(debug_stats));
5649 }
5650 #endif
5651
5652 static void do_flush(device_extension* Vcb) {
5653 LIST_ENTRY rollback;
5654
5655 InitializeListHead(&rollback);
5656
5657 FsRtlEnterFileSystem();
5658
5659 ExAcquireResourceExclusiveLite(&Vcb->tree_lock, TRUE);
5660
5661 #ifdef DEBUG_STATS
5662 print_stats(Vcb);
5663 #endif
5664
5665 if (Vcb->need_write && !Vcb->readonly)
5666 do_write(Vcb, NULL, &rollback);
5667
5668 free_trees(Vcb);
5669
5670 clear_rollback(Vcb, &rollback);
5671
5672 ExReleaseResourceLite(&Vcb->tree_lock);
5673
5674 FsRtlExitFileSystem();
5675 }
5676
5677 void STDCALL flush_thread(void* context) {
5678 DEVICE_OBJECT* devobj = context;
5679 device_extension* Vcb = devobj->DeviceExtension;
5680 LARGE_INTEGER due_time;
5681
5682 ObReferenceObject(devobj);
5683
5684 KeInitializeTimer(&Vcb->flush_thread_timer);
5685
5686 due_time.QuadPart = (UINT64)Vcb->options.flush_interval * -10000000;
5687
5688 KeSetTimer(&Vcb->flush_thread_timer, due_time, NULL);
5689
5690 while (TRUE) {
5691 KeWaitForSingleObject(&Vcb->flush_thread_timer, Executive, KernelMode, FALSE, NULL);
5692
5693 if (!(devobj->Vpb->Flags & VPB_MOUNTED) || Vcb->removing)
5694 break;
5695
5696 do_flush(Vcb);
5697
5698 KeSetTimer(&Vcb->flush_thread_timer, due_time, NULL);
5699 }
5700
5701 ObDereferenceObject(devobj);
5702 KeCancelTimer(&Vcb->flush_thread_timer);
5703
5704 KeSetEvent(&Vcb->flush_thread_finished, 0, FALSE);
5705
5706 PsTerminateSystemThread(STATUS_SUCCESS);
5707 }
A free Windows-compatible Operating System