25 #define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - sizeof(leaf_node)) 49 #ifndef _MSC_VER // not in mingw yet 50 #define DEVICE_DSM_FLAG_TRIM_NOT_FS_ALLOCATED 0x80000000 84 ERR(
"IoAllocateIrp failed\n");
93 Irp->AssociatedIrp.SystemBuffer =
data;
98 if (!
Irp->MdlAddress) {
113 ERR(
"MmProbeAndLockPages threw exception %08lx\n",
Status);
138 ERR(
"IoCallDriver returned %08lx\n",
Status);
155 ERR(
"out of memory\n");
161 dev->num_trim_entries++;
169 if (
Vcb->trim && !
Vcb->options.no_trim) {
199 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
200 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim)
205 uint16_t startoffstripe, endoffstripe,
i;
207 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &startoff, &startoffstripe);
208 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &endoff, &endoffstripe);
210 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
211 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim) {
214 if (startoffstripe >
i)
215 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
216 else if (startoffstripe ==
i)
217 stripestart = startoff;
219 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
221 if (endoffstripe >
i)
222 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
223 else if (endoffstripe ==
i)
224 stripeend = endoff + 1;
226 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
228 if (stripestart != stripeend)
234 uint16_t sub_stripes, startoffstripe, endoffstripe,
i;
236 sub_stripes =
max(1,
c->chunk_item->sub_stripes);
238 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &startoff, &startoffstripe);
239 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &endoff, &endoffstripe);
241 startoffstripe *= sub_stripes;
242 endoffstripe *= sub_stripes;
244 for (
i = 0;
i <
c->chunk_item->num_stripes;
i += sub_stripes) {
248 if (startoffstripe >
i)
249 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
250 else if (startoffstripe ==
i)
251 stripestart = startoff;
253 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
255 if (endoffstripe >
i)
256 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
257 else if (endoffstripe ==
i)
258 stripeend = endoff + 1;
260 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
262 if (stripestart != stripeend) {
263 for (
j = 0;
j < sub_stripes;
j++) {
264 if (
c->devices[
i+
j] &&
c->devices[
i+
j]->devobj && !
c->devices[
i+
j]->readonly &&
c->devices[
i+
j]->trim)
283 #ifdef DEBUG_TRIM_EMULATION 309 #ifdef DEBUG_TRIM_EMULATION 310 static void trim_emulation(
device*
dev) {
313 unsigned int i = 0,
count = 0;
315 le =
dev->trim_list.Flink;
316 while (le != &
dev->trim_list) {
327 ERR(
"out of memory\n");
334 le =
dev->trim_list.Flink;
335 while (le != &
dev->trim_list) {
339 WARN(
"(%I64x, %I64x)\n",
s->address,
s->size);
344 ERR(
"IoAllocateIrp failed\n");
353 ERR(
"out of memory\n");
360 ERR(
"IoAllocateMdl failed\n");
402 #ifndef DEBUG_TRIM_EMULATION 410 le =
Vcb->chunks.Flink;
411 while (le != &
Vcb->chunks) {
414 if (
c->space_changed) {
417 if (
c->space_changed)
420 c->space_changed =
false;
430 if (
Vcb->trim && !
Vcb->options.no_trim) {
431 #ifndef DEBUG_TRIM_EMULATION 437 le =
Vcb->devices.Flink;
438 while (le != &
Vcb->devices) {
441 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0)
457 ERR(
"out of memory\n");
464 le =
Vcb->devices.Flink;
465 while (le != &
Vcb->devices) {
468 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0) {
469 #ifdef DEBUG_TRIM_EMULATION 480 ERR(
"out of memory\n");
487 stripe->dmdsa->ParameterBlockOffset = 0;
488 stripe->dmdsa->ParameterBlockLength = 0;
496 le2 =
dev->trim_list.Flink;
497 while (le2 != &
dev->trim_list) {
510 ERR(
"IoAllocateIrp failed\n");
522 stripe->Irp->AssociatedIrp.SystemBuffer =
stripe->dmdsa;
538 dev->num_trim_entries = 0;
540 #ifndef DEBUG_TRIM_EMULATION 548 #ifndef DEBUG_TRIM_EMULATION 568 le =
Vcb->trees.Flink;
569 while (le != &
Vcb->trees) {
573 if (
t->header.num_items == 0 &&
t->parent) {
574 #ifdef DEBUG_WRITE_LOOPS 575 ERR(
"empty tree found, looping again\n");
580 if (
t->size > maxsize) {
581 #ifdef DEBUG_WRITE_LOOPS 582 ERR(
"overlarge tree found (%u > %u), looping again\n",
t->size, maxsize);
587 if (!
t->has_new_address) {
588 #ifdef DEBUG_WRITE_LOOPS 589 ERR(
"tree found without new address, looping again\n");
606 bool nothing_found =
true;
610 le =
Vcb->trees.Flink;
611 while (le != &
Vcb->trees) {
614 if (
t->write &&
t->header.level ==
level) {
615 TRACE(
"tree %p: root = %I64x, level = %x, parent = %p\n",
t,
t->header.tree_id,
t->header.level,
t->parent);
617 nothing_found =
false;
620 if (!
t->parent->write)
621 TRACE(
"adding tree %p (level %x)\n",
t->parent,
t->header.level);
623 t->parent->write =
true;
624 }
else if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
632 searchkey.
obj_id =
t->root->id;
634 searchkey.
offset = 0xffffffffffffffff;
638 ERR(
"error - find_item returned %08lx\n",
Status);
643 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
651 ERR(
"out of memory\n");
659 ERR(
"delete_tree_item returned %08lx\n",
Status);
666 ERR(
"insert_tree_item returned %08lx\n",
Status);
709 ERR(
"out of memory\n");
721 ERR(
"insert_tree_item returned %08lx\n",
Status);
743 if (
Vcb->superblock.node_size >
c->chunk_item->size -
c->used)
746 if (!
c->cache_loaded) {
750 ERR(
"load_cache_chunk returned %08lx\n",
Status);
758 if (!
c->last_alloc_set) {
761 c->last_alloc =
s->address;
762 c->last_alloc_set =
true;
764 if (
s->size >=
Vcb->superblock.node_size) {
766 c->last_alloc +=
Vcb->superblock.node_size;
772 while (le != &
c->space) {
775 if (
s->address <=
c->last_alloc &&
s->address +
s->size >=
c->last_alloc +
Vcb->superblock.node_size) {
777 c->last_alloc +=
Vcb->superblock.node_size;
785 while (le != &
c->space_size) {
788 if (
s->size ==
Vcb->superblock.node_size) {
790 c->last_alloc =
s->address +
Vcb->superblock.node_size;
792 }
else if (
s->size <
Vcb->superblock.node_size) {
793 if (le ==
c->space_size.
Flink)
799 c->last_alloc =
s->address +
Vcb->superblock.node_size;
809 if (
s->size >
Vcb->superblock.node_size) {
811 c->last_alloc =
s->address +
Vcb->superblock.node_size;
824 TRACE(
"(%p, %x, %I64x, %p, %p, %p, %p)\n",
Vcb,
level, root_id,
c, new_address,
Irp,
rollback);
840 ERR(
"out of memory\n");
853 ERR(
"insert_tree_item returned %08lx\n",
Status);
882 if (
t->has_address) {
887 t->new_address =
addr;
888 t->has_new_address =
true;
895 le =
Vcb->chunks.Flink;
896 while (le != &
Vcb->chunks) {
899 if (!
c->readonly && !
c->reloc) {
906 t->new_address =
addr;
907 t->has_new_address =
true;
923 ERR(
"alloc_chunk returned %08lx\n",
Status);
930 if ((
c->chunk_item->size -
c->used) >=
Vcb->superblock.node_size) {
934 t->new_address =
addr;
935 t->has_new_address =
true;
944 ERR(
"couldn't find any metadata chunks with %x bytes free\n",
Vcb->superblock.node_size);
957 ERR(
"error - refcount for extent %I64x was 0\n",
address);
964 root =
t->header.tree_id;
968 ERR(
"decrease_extent_refcount_tree returned %08lx\n",
Status);
978 if (!
c->cache_loaded) {
982 ERR(
"load_cache_chunk returned %08lx\n",
Status);
988 c->used -=
Vcb->superblock.node_size;
994 ERR(
"could not find chunk for address %I64x\n",
address);
1007 while (le2 !=
list) {
1020 ERR(
"out of memory\n");
1044 while (le2 !=
list) {
1057 ERR(
"out of memory\n");
1079 if (!
t->updated_extents &&
t->has_address) {
1082 ERR(
"update_tree_extents returned %08lx\n",
Status);
1087 searchkey.
obj_id =
t->header.address;
1089 searchkey.
offset = 0xffffffffffffffff;
1093 ERR(
"error - find_item returned %08lx\n",
Status);
1109 ERR(
"refcount for extent %I64x was 0\n",
t->header.address);
1117 if (
t->header.level == 0) {
1121 while (le != &
t->itemlist) {
1138 le2 =
c->changed_extents.
Flink;
1139 while (le2 != &
c->changed_extents) {
1151 edr.
root =
t->root->id;
1159 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1165 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1172 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1182 sdr.
offset =
t->header.address;
1188 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1196 while (le2 != &ce->
refs) {
1242 while (le != &
t->itemlist) {
1249 &tbr, &td->
key,
t->header.level - 1,
Irp);
1251 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1261 sbr.
offset =
t->header.address;
1264 t->header.address,
false,
Irp);
1266 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1285 sbr.
offset =
t->parent->header.address;
1288 t->parent->header.address,
false,
Irp);
1290 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1297 tbr.
offset =
t->parent->header.tree_id;
1299 tbr.
offset =
t->header.tree_id;
1302 t->parent ? &
t->paritem->key :
NULL,
t->header.level,
Irp);
1304 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1313 if (rc > 1 ||
t->header.tree_id ==
t->root->id) {
1317 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
1322 t->has_address =
false;
1325 if (
t->header.tree_id ==
t->root->id) {
1330 if (
t->header.level > 0) {
1334 while (le != &
t->itemlist) {
1338 if (
t->header.tree_id ==
t->root->id) {
1341 sbr.
offset =
t->header.address;
1353 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1364 while (le != &
t->itemlist) {
1380 le2 =
c->changed_extents.
Flink;
1381 while (le2 != &
c->changed_extents) {
1393 if (
t->header.tree_id ==
t->root->id) {
1396 sdr.
offset =
t->header.address;
1402 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1408 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1417 edr.
root =
t->root->id;
1425 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1431 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1440 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1452 t->updated_extents =
true;
1453 t->header.tree_id =
t->root->id;
1461 bool changed =
false;
1466 le =
Vcb->trees.Flink;
1467 while (le != &
Vcb->trees) {
1470 if (
t->write && !
t->has_new_address) {
1473 if (
t->has_address) {
1477 if (!
c->cache_loaded) {
1480 if (!
c->cache_loaded) {
1484 ERR(
"load_cache_chunk returned %08lx\n",
Status);
1497 ERR(
"get_tree_new_address returned %08lx\n",
Status);
1501 TRACE(
"allocated extent %I64x\n",
t->new_address);
1506 c->used +=
Vcb->superblock.node_size;
1508 ERR(
"could not find chunk for address %I64x\n",
t->new_address);
1514 if (
t->header.level > max_level)
1515 max_level =
t->header.level;
1526 le =
Vcb->trees.Flink;
1527 while (le != &
Vcb->trees) {
1530 if (
t->write && !
t->updated_extents &&
t->has_address &&
t->header.level ==
level) {
1533 ERR(
"update_tree_extents returned %08lx\n",
Status);
1556 le =
Vcb->trees.Flink;
1557 while (le != &
Vcb->trees) {
1560 if (
t->write && !
t->parent) {
1561 if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
1565 searchkey.
obj_id =
t->root->id;
1567 searchkey.
offset = 0xffffffffffffffff;
1571 ERR(
"error - find_item returned %08lx\n",
Status);
1576 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
1580 TRACE(
"updating the address for root %I64x to %I64x\n", searchkey.
obj_id,
t->new_address);
1582 t->root->root_item.block_number =
t->new_address;
1583 t->root->root_item.root_level =
t->header.level;
1584 t->root->root_item.generation =
Vcb->superblock.generation;
1585 t->root->root_item.generation2 =
Vcb->superblock.generation;
1592 t->root->treeholder.address =
t->new_address;
1593 t->root->treeholder.generation =
Vcb->superblock.generation;
1605 ERR(
"update_chunk_caches returned %08lx\n",
Status);
1621 bool raid56 =
false;
1625 le = tree_writes->
Flink;
1626 while (le != tree_writes) {
1638 ERR(
"out of memory\n");
1673 le = tree_writes->
Flink;
1674 while (le != tree_writes) {
1684 ERR(
"out of memory\n");
1688 le = tree_writes->
Flink;
1690 while (le != tree_writes) {
1704 ERR(
"write_data returned %08lx\n",
Status);
1706 for (
i = 0;
i < num_bits;
i++) {
1719 for (
i = 0;
i < num_bits;
i++) {
1720 if (wtc[
i].stripes.Flink != &wtc[
i].
stripes) {
1723 while (le != &wtc[
i].stripes) {
1736 for (
i = 0;
i < num_bits;
i++) {
1737 if (wtc[
i].need_wait)
1741 for (
i = 0;
i < num_bits;
i++) {
1743 while (le != &wtc[
i].stripes) {
1763 le = tree_writes->
Flink;
1764 while (le != tree_writes) {
1783 ERR(
"flush_partial_stripe returned %08lx\n",
Status);
1800 switch (
Vcb->superblock.csum_type) {
1832 bool nothing_found =
true;
1836 le =
Vcb->trees.Flink;
1837 while (le != &
Vcb->trees) {
1840 if (
t->write &&
t->header.level ==
level) {
1841 KEY firstitem, searchkey;
1845 if (!
t->has_new_address) {
1846 ERR(
"error - tried to write tree with no new address\n");
1851 while (le2 != &
t->itemlist) {
1854 firstitem = td->
key;
1861 t->paritem->key = firstitem;
1862 t->paritem->treeholder.address =
t->new_address;
1863 t->paritem->treeholder.generation =
Vcb->superblock.generation;
1869 searchkey.
obj_id =
t->new_address;
1871 searchkey.
offset =
Vcb->superblock.node_size;
1875 ERR(
"error - find_item returned %08lx\n",
Status);
1880 ERR(
"could not find %I64x,%x,%I64x in extent_root (found %I64x,%x,%I64x instead)\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset,
tp.
item->
key.
obj_id,
tp.
item->
key.
obj_type,
tp.
item->
key.
offset);
1893 nothing_found =
false;
1903 TRACE(
"allocated tree extents\n");
1905 le =
Vcb->trees.Flink;
1906 while (le != &
Vcb->trees) {
1909 #ifdef DEBUG_PARANOID 1915 #ifdef DEBUG_PARANOID 1920 while (le2 != &
t->itemlist) {
1929 }
else if (
keycmp(td->
key, lastkey) == -1) {
1938 if (
t->header.level == 0)
1944 if (
t->header.level == 0)
1949 if (num_items !=
t->header.num_items) {
1950 ERR(
"tree %I64x, level %x: num_items was %x, expected %x\n",
t->root->id,
t->header.level, num_items,
t->header.num_items);
1954 if (
size !=
t->size) {
1955 ERR(
"tree %I64x, level %x: size was %x, expected %x\n",
t->root->id,
t->header.level,
size,
t->size);
1959 if (
t->header.num_items == 0 &&
t->parent) {
1960 ERR(
"tree %I64x, level %x: tried to write empty tree with parent\n",
t->root->id,
t->header.level);
1965 ERR(
"tree %I64x, level %x: tried to write overlarge tree (%x > %Ix)\n",
t->root->id,
t->header.level,
t->size,
Vcb->superblock.node_size -
sizeof(
tree_header));
1970 ERR(
"tree %p\n",
t);
1972 while (le2 != &
t->itemlist) {
1982 t->header.address =
t->new_address;
1983 t->header.generation =
Vcb->superblock.generation;
1984 t->header.tree_id =
t->root->id;
1986 t->header.fs_uuid =
Vcb->superblock.metadata_uuid;
1987 t->has_address =
true;
1991 ERR(
"out of memory\n");
2001 if (
t->header.level == 0) {
2007 while (le2 != &
t->itemlist) {
2028 while (le2 != &
t->itemlist) {
2045 ERR(
"out of memory\n");
2059 bool inserted =
false;
2061 le2 = tree_writes.
Flink;
2062 while (le2 != &tree_writes) {
2084 ERR(
"do_tree_writes returned %08lx\n",
Status);
2111 sb->root_tree_generation =
Vcb->superblock.generation;
2115 sb->chunk_tree_generation =
Vcb->superblock.chunk_root_generation;
2120 searchkey.
offset = 0xffffffffffffffff;
2238 ERR(
"out of memory\n");
2254 ERR(
"out of memory\n");
2263 ERR(
"IoAllocateIrp failed\n");
2277 stripe->Irp->AssociatedIrp.SystemBuffer =
sb;
2284 ERR(
"IoAllocateMdl failed\n");
2314 ERR(
"no superblocks written!\n");
2327 le =
Vcb->trees.Flink;
2328 while (le != &
Vcb->trees) {
2331 if (
t->write && !
t->parent) {
2332 if (
t->root ==
Vcb->root_root) {
2333 Vcb->superblock.root_tree_addr =
t->new_address;
2334 Vcb->superblock.root_level =
t->header.level;
2335 }
else if (
t->root ==
Vcb->chunk_root) {
2336 Vcb->superblock.chunk_tree_addr =
t->new_address;
2337 Vcb->superblock.chunk_root_generation =
t->header.generation;
2338 Vcb->superblock.chunk_root_level =
t->header.level;
2355 le =
Vcb->devices.Flink;
2356 while (le != &
Vcb->devices) {
2359 if (
dev->devobj && !
dev->readonly) {
2362 ERR(
"write_superblock returned %08lx\n",
Status);
2371 ERR(
"error - not writing any superblocks\n");
2377 while (le != &
context.stripes) {
2388 while (le != &
context.stripes) {
2446 while (le != &ce->
refs) {
2469 ERR(
"increase_extent_refcount_data returned %08lx\n",
Status);
2492 while (le != &ce->
refs) {
2520 ERR(
"decrease_extent_refcount_data returned %08lx\n",
Status);
2536 ERR(
"error - find_item returned %08lx\n",
Status);
2541 ERR(
"could not find (%I64x,%x,%I64x) in extent tree\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2549 ERR(
"out of memory\n");
2559 ERR(
"insert_tree_item returned %08lx\n",
Status);
2566 ERR(
"delete_tree_item returned %08lx\n",
Status);
2578 #ifdef DEBUG_PARANOID 2580 WARN(
"old_refs not empty\n");
2585 c->used -= ce->
size;
2625 ERR(
"out of memory\n");
2634 ERR(
"insert_tree_item returned %08lx\n",
Status);
2642 off += il *
Vcb->superblock.sector_size;
2645 }
while (length2 > 0);
2648 ERR(
"find_item returned %08lx\n",
Status);
2667 ERR(
"find_item returned %08lx\n",
Status);
2680 TRACE(
"endaddr = %I64x\n", endaddr);
2686 ERR(
"out of memory\n");
2692 ERR(
"out of memory\n");
2706 ERR(
"find_item returned %08lx\n",
Status);
2726 ERR(
"delete_tree_item returned %08lx\n",
Status);
2749 while (runlength != 0) {
2772 ERR(
"out of memory\n");
2784 ERR(
"insert_tree_item returned %08lx\n",
Status);
2793 }
while (runlength > 0);
2815 while (le != &
Vcb->chunks) {
2820 if (!
c->cache_loaded && (!
IsListEmpty(&
c->changed_extents) ||
c->used !=
c->oldused)) {
2824 ERR(
"load_cache_chunk returned %08lx\n",
Status);
2830 le2 =
c->changed_extents.Flink;
2831 while (le2 != &
c->changed_extents) {
2837 ERR(
"flush_changed_extent returned %08lx\n",
Status);
2850 ERR(
"create_chunk returned %08lx\n",
Status);
2857 if (
c->old_cache->dirty) {
2864 ERR(
"flush_fcb returned %08lx\n",
Status);
2872 ERR(
"commit_batch_list returned %08lx\n",
Status);
2880 if (
c->old_cache->refcount == 0)
2883 c->old_cache =
NULL;
2886 if (
c->used !=
c->oldused) {
2892 searchkey.
offset =
c->chunk_item->size;
2896 ERR(
"error - find_item returned %08lx\n",
Status);
2902 ERR(
"could not find (%I64x,%x,%I64x) in extent_root\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2917 ERR(
"out of memory\n");
2924 bgi->
used =
c->used;
2926 #ifdef DEBUG_PARANOID 2927 if (bgi->
used & 0x8000000000000000) {
2928 ERR(
"refusing to write BLOCK_GROUP_ITEM with negative usage value (%I64x)", bgi->
used);
2933 TRACE(
"adjusting usage of chunk %I64x to %I64x\n",
c->offset,
c->used);
2937 ERR(
"delete_tree_item returned %08lx\n",
Status);
2945 ERR(
"insert_tree_item returned %08lx\n",
Status);
2959 if (
Vcb->superblock.bytes_used + phys_used > old_phys_used)
2960 Vcb->superblock.bytes_used += phys_used - old_phys_used;
2962 Vcb->superblock.bytes_used = 0;
2964 c->oldused =
c->used;
2984 while (le != &
t->itemlist) {
3001 ERR(
"out of memory\n");
3005 if (
t->header.level > 0) {
3007 if (!
nt->nonpaged) {
3008 ERR(
"out of memory\n");
3018 nt->header.address = 0;
3019 nt->header.generation =
Vcb->superblock.generation;
3020 nt->header.num_items =
t->header.num_items - numitems;
3023 nt->has_address =
false;
3025 nt->parent =
t->parent;
3027 #ifdef DEBUG_PARANOID 3028 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3032 nt->new_address = 0;
3033 nt->has_new_address =
false;
3034 nt->updated_extents =
false;
3035 nt->uniqueness_determined =
true;
3036 nt->is_unique =
true;
3037 nt->list_entry_hash.Flink =
NULL;
3044 nt->itemlist.Blink =
t->itemlist.Blink;
3045 nt->itemlist.Flink->Blink = &
nt->itemlist;
3046 nt->itemlist.Blink->Flink = &
nt->itemlist;
3049 t->itemlist.
Blink->Flink = &
t->itemlist;
3053 t->header.num_items = numitems;
3058 if (
nt->header.level > 0) {
3061 while (le != &
nt->itemlist) {
3066 #ifdef DEBUG_PARANOID 3076 while (le != &
nt->itemlist) {
3083 ERR(
"out of memory\n");
3097 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3099 ERR(
"out of memory\n");
3103 td->
key = newfirstitem->
key;
3112 nt->parent->header.num_items++;
3118 TRACE(
"adding new tree parent\n");
3120 if (
nt->header.level == 255) {
3121 ERR(
"cannot add parent to tree at level 255\n");
3127 ERR(
"out of memory\n");
3132 if (!
pt->nonpaged) {
3133 ERR(
"out of memory\n");
3141 pt->header.address = 0;
3142 pt->header.num_items = 2;
3143 pt->header.level =
nt->header.level + 1;
3146 pt->has_address =
false;
3151 pt->new_address = 0;
3152 pt->has_new_address =
false;
3153 pt->updated_extents =
false;
3155 pt->uniqueness_determined =
true;
3156 pt->is_unique =
true;
3157 pt->list_entry_hash.Flink =
NULL;
3163 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3165 ERR(
"out of memory\n");
3178 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3180 ERR(
"out of memory\n");
3184 td->
key = newfirstitem->
key;
3195 t->root->treeholder.tree =
pt;
3200 #ifdef DEBUG_PARANOID 3201 if (
t->parent &&
t->parent->header.level <=
t->header.level)
int3;
3202 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3206 t->root->root_item.bytes_used +=
Vcb->superblock.node_size;
3221 while (le != &
t->itemlist) {
3225 if (
t->header.level == 0)
3230 if (numitems == 0 &&
ds >
Vcb->superblock.node_size -
sizeof(
tree_header)) {
3231 ERR(
"(%I64x,%x,%I64x) in tree %I64x is too large (%x > %Ix)\n",
3259 if (
t->uniqueness_determined)
3260 return t->is_unique;
3265 if (
t->has_address) {
3266 searchkey.
obj_id =
t->header.address;
3268 searchkey.
offset = 0xffffffffffffffff;
3272 ERR(
"error - find_item returned %08lx\n",
Status);
3309 t->uniqueness_determined =
true;
3318 tree *next_tree, *par;
3322 TRACE(
"trying to amalgamate tree in root %I64x, level %x (size %u)\n",
t->root->id,
t->header.level,
t->size);
3325 le =
t->paritem->list_entry.
Flink;
3326 while (le != &
t->parent->itemlist) {
3345 ERR(
"do_load_tree returned %08lx\n",
Status);
3358 ERR(
"update_tree_extents returned %08lx\n",
Status);
3367 t->size += next_tree->
size;
3372 while (le != &next_tree->
itemlist) {
3377 #ifdef DEBUG_PARANOID 3388 while (le != &next_tree->
itemlist) {
3395 ERR(
"out of memory\n");
3409 t->itemlist.Blink->Flink->Blink =
t->itemlist.Blink;
3411 t->itemlist.Blink->Flink = &
t->itemlist;
3416 next_tree->
size = 0;
3422 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3429 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3434 if (!nextparitem->
ignore) {
3435 nextparitem->
ignore =
true;
3436 next_tree->
parent->header.num_items--;
3439 *done_deletions =
true;
3452 next_tree->
root->root_item.bytes_used -=
Vcb->superblock.node_size;
3459 ULONG avg_size = (
t->size + next_tree->
size) / 2;
3460 KEY firstitem = {0, 0, 0};
3461 bool changed =
false;
3463 TRACE(
"attempting rebalance\n");
3484 #ifdef DEBUG_PARANOID 3491 ERR(
"out of memory\n");
3505 t->header.num_items++;
3516 while (le != &next_tree->
itemlist) {
3520 firstitem = td->
key;
3552 searchkey.
offset =
t->header.level;
3556 ERR(
"error - find_item returned %08lx\n",
Status);
3567 ERR(
"out of memory\n");
3577 ERR(
"delete_tree_item returned %08lx\n",
Status);
3584 ERR(
"insert_tree_item returned %08lx\n",
Status);
3595 searchkey.
offset = 0xffffffffffffffff;
3599 ERR(
"error - find_item returned %08lx\n",
Status);
3614 ERR(
"out of memory\n");
3622 ERR(
"delete_tree_item returned %08lx\n",
Status);
3631 ERR(
"insert_tree_item returned %08lx\n",
Status);
3639 ERR(
"could not find EXTENT_ITEM for address %I64x\n",
address);
3647 if (
t->parent && !
t->parent->updated_extents &&
t->parent->has_address) {
3655 ERR(
"update_tree_extents returned %08lx\n",
Status);
3665 bool empty, done_deletions =
false;
3680 le =
Vcb->trees.Flink;
3682 while (le != &
Vcb->trees) {
3687 if (
t->write &&
t->header.level ==
level) {
3690 if (
t->header.num_items == 0) {
3692 done_deletions =
true;
3694 TRACE(
"deleting tree in root %I64x\n",
t->root->id);
3696 t->root->root_item.bytes_used -=
Vcb->superblock.node_size;
3698 if (
t->has_new_address) {
3702 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3706 t->has_new_address =
false;
3707 }
else if (
t->has_address) {
3711 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3715 t->has_address =
false;
3718 if (!
t->paritem->ignore) {
3719 t->paritem->ignore =
true;
3720 t->parent->header.num_items--;
3729 }
else if (
t->header.level != 0) {
3730 if (
t->has_new_address) {
3734 ERR(
"update_extent_level returned %08lx\n",
Status);
3739 t->header.level = 0;
3741 }
else if (
t->size >
Vcb->superblock.node_size -
sizeof(
tree_header)) {
3742 TRACE(
"splitting overlarge tree (%x > %Ix)\n",
t->size,
Vcb->superblock.node_size -
sizeof(
tree_header));
3744 if (!
t->updated_extents &&
t->has_address) {
3747 ERR(
"update_tree_extents_recursive returned %08lx\n",
Status);
3755 ERR(
"split_tree returned %08lx\n",
Status);
3767 TRACE(
"nothing found for level %lu\n",
level);
3772 min_size = (
Vcb->superblock.node_size -
sizeof(
tree_header)) / 2;
3777 le =
Vcb->trees.Flink;
3779 while (le != &
Vcb->trees) {
3782 if (
t->write &&
t->header.level ==
level &&
t->header.num_items > 0 &&
t->parent &&
t->size < min_size &&
3789 ERR(
"try_tree_amalgamate returned %08lx\n",
Status);
3792 }
while (done &&
t->size < min_size);
3801 if (done_deletions) {
3805 le =
Vcb->trees.Flink;
3806 while (le != &
Vcb->trees) {
3810 if (
t->write &&
t->header.level ==
level) {
3811 if (!
t->parent &&
t->header.num_items == 1) {
3816 while (le2 != &
t->itemlist) {
3823 TRACE(
"deleting top-level tree in root %I64x with one item\n",
t->root->id);
3825 if (
t->has_new_address) {
3829 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3833 t->has_new_address =
false;
3834 }
else if (
t->has_address) {
3838 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3842 t->has_address =
false;
3846 KEY searchkey = {0,0,0};
3851 ERR(
"error - find_item returned %08lx\n",
Status);