28 #define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - (2 * sizeof(leaf_node))) 83 ERR(
"IoAllocateIrp failed\n");
92 Irp->AssociatedIrp.SystemBuffer =
data;
97 if (!
Irp->MdlAddress) {
112 ERR(
"MmProbeAndLockPages threw exception %08lx\n",
Status);
137 ERR(
"IoCallDriver returned %08lx\n",
Status);
154 ERR(
"out of memory\n");
160 dev->num_trim_entries++;
189 while (le != &
c->deleting) {
198 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
199 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim)
204 uint16_t startoffstripe, endoffstripe,
i;
206 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &startoff, &startoffstripe);
207 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &endoff, &endoffstripe);
209 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
210 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim) {
213 if (startoffstripe >
i)
214 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
215 else if (startoffstripe ==
i)
216 stripestart = startoff;
218 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
220 if (endoffstripe >
i)
221 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
222 else if (endoffstripe ==
i)
223 stripeend = endoff + 1;
225 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
227 if (stripestart != stripeend)
233 uint16_t sub_stripes, startoffstripe, endoffstripe,
i;
235 sub_stripes =
max(1,
c->chunk_item->sub_stripes);
237 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &startoff, &startoffstripe);
238 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &endoff, &endoffstripe);
240 startoffstripe *= sub_stripes;
241 endoffstripe *= sub_stripes;
243 for (
i = 0;
i <
c->chunk_item->num_stripes;
i += sub_stripes) {
247 if (startoffstripe >
i)
248 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
249 else if (startoffstripe ==
i)
250 stripestart = startoff;
252 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
254 if (endoffstripe >
i)
255 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
256 else if (endoffstripe ==
i)
257 stripeend = endoff + 1;
259 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
261 if (stripestart != stripeend) {
262 for (
j = 0;
j < sub_stripes;
j++) {
263 if (
c->devices[
i+
j] &&
c->devices[
i+
j]->devobj && !
c->devices[
i+
j]->readonly &&
c->devices[
i+
j]->trim)
281 #ifdef DEBUG_TRIM_EMULATION 307 #ifdef DEBUG_TRIM_EMULATION 308 static void trim_emulation(
device*
dev) {
311 unsigned int i = 0,
count = 0;
313 le =
dev->trim_list.Flink;
314 while (le != &
dev->trim_list) {
325 ERR(
"out of memory\n");
332 le =
dev->trim_list.Flink;
333 while (le != &
dev->trim_list) {
337 WARN(
"(%I64x, %I64x)\n",
s->address,
s->size);
342 ERR(
"IoAllocateIrp failed\n");
351 ERR(
"out of memory\n");
358 ERR(
"IoAllocateMdl failed\n");
400 #ifndef DEBUG_TRIM_EMULATION 408 le =
Vcb->chunks.Flink;
409 while (le != &
Vcb->chunks) {
412 if (
c->space_changed) {
415 if (
c->space_changed) {
416 if (
Vcb->trim && !
Vcb->options.no_trim)
428 c->space_changed =
false;
438 if (
Vcb->trim && !
Vcb->options.no_trim) {
439 #ifndef DEBUG_TRIM_EMULATION 445 le =
Vcb->devices.Flink;
446 while (le != &
Vcb->devices) {
449 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0)
465 ERR(
"out of memory\n");
472 le =
Vcb->devices.Flink;
473 while (le != &
Vcb->devices) {
476 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0) {
477 #ifdef DEBUG_TRIM_EMULATION 488 ERR(
"out of memory\n");
495 stripe->dmdsa->ParameterBlockOffset = 0;
496 stripe->dmdsa->ParameterBlockLength = 0;
504 le2 =
dev->trim_list.Flink;
505 while (le2 != &
dev->trim_list) {
518 ERR(
"IoAllocateIrp failed\n");
530 stripe->Irp->AssociatedIrp.SystemBuffer =
stripe->dmdsa;
546 dev->num_trim_entries = 0;
548 #ifndef DEBUG_TRIM_EMULATION 556 #ifndef DEBUG_TRIM_EMULATION 576 le =
Vcb->trees.Flink;
577 while (le != &
Vcb->trees) {
581 if (
t->header.num_items == 0 &&
t->parent) {
582 #ifdef DEBUG_WRITE_LOOPS 583 ERR(
"empty tree found, looping again\n");
588 if (
t->size > maxsize) {
589 #ifdef DEBUG_WRITE_LOOPS 590 ERR(
"overlarge tree found (%u > %u), looping again\n",
t->size, maxsize);
595 if (!
t->has_new_address) {
596 #ifdef DEBUG_WRITE_LOOPS 597 ERR(
"tree found without new address, looping again\n");
614 bool nothing_found =
true;
618 le =
Vcb->trees.Flink;
619 while (le != &
Vcb->trees) {
622 if (
t->write &&
t->header.level ==
level) {
623 TRACE(
"tree %p: root = %I64x, level = %x, parent = %p\n",
t,
t->header.tree_id,
t->header.level,
t->parent);
625 nothing_found =
false;
628 if (!
t->parent->write)
629 TRACE(
"adding tree %p (level %x)\n",
t->parent,
t->header.level);
631 t->parent->write =
true;
632 }
else if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
637 searchkey.
obj_id =
t->root->id;
639 searchkey.
offset = 0xffffffffffffffff;
643 ERR(
"error - find_item returned %08lx\n",
Status);
648 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
656 ERR(
"out of memory\n");
664 ERR(
"delete_tree_item returned %08lx\n",
Status);
671 ERR(
"insert_tree_item returned %08lx\n",
Status);
710 ERR(
"out of memory\n");
722 ERR(
"insert_tree_item returned %08lx\n",
Status);
744 if (
Vcb->superblock.node_size >
c->chunk_item->size -
c->used)
747 if (!
c->cache_loaded) {
751 ERR(
"load_cache_chunk returned %08lx\n",
Status);
759 if (!
c->last_alloc_set) {
762 c->last_alloc =
s->address;
763 c->last_alloc_set =
true;
765 if (
s->size >=
Vcb->superblock.node_size) {
767 c->last_alloc +=
Vcb->superblock.node_size;
773 while (le != &
c->space) {
776 if (
s->address <=
c->last_alloc &&
s->address +
s->size >=
c->last_alloc +
Vcb->superblock.node_size) {
778 c->last_alloc +=
Vcb->superblock.node_size;
786 while (le != &
c->space_size) {
789 if (
s->size ==
Vcb->superblock.node_size) {
791 c->last_alloc =
s->address +
Vcb->superblock.node_size;
793 }
else if (
s->size <
Vcb->superblock.node_size) {
794 if (le ==
c->space_size.
Flink)
800 c->last_alloc =
s->address +
Vcb->superblock.node_size;
810 if (
s->size >
Vcb->superblock.node_size) {
812 c->last_alloc =
s->address +
Vcb->superblock.node_size;
825 TRACE(
"(%p, %x, %I64x, %p, %p, %p, %p)\n",
Vcb,
level, root_id,
c, new_address,
Irp,
rollback);
841 ERR(
"out of memory\n");
854 ERR(
"insert_tree_item returned %08lx\n",
Status);
883 if (
t->has_address) {
888 t->new_address =
addr;
889 t->has_new_address =
true;
896 le =
Vcb->chunks.Flink;
897 while (le != &
Vcb->chunks) {
900 if (!
c->readonly && !
c->reloc) {
907 t->new_address =
addr;
908 t->has_new_address =
true;
924 ERR(
"alloc_chunk returned %08lx\n",
Status);
931 if ((
c->chunk_item->size -
c->used) >=
Vcb->superblock.node_size) {
935 t->new_address =
addr;
936 t->has_new_address =
true;
945 ERR(
"couldn't find any metadata chunks with %x bytes free\n",
Vcb->superblock.node_size);
958 ERR(
"error - refcount for extent %I64x was 0\n",
address);
965 root =
t->header.tree_id;
969 ERR(
"decrease_extent_refcount_tree returned %08lx\n",
Status);
979 if (!
c->cache_loaded) {
983 ERR(
"load_cache_chunk returned %08lx\n",
Status);
989 c->used -=
Vcb->superblock.node_size;
995 ERR(
"could not find chunk for address %I64x\n",
address);
1008 while (le2 !=
list) {
1021 ERR(
"out of memory\n");
1045 while (le2 !=
list) {
1058 ERR(
"out of memory\n");
1080 if (!
t->updated_extents &&
t->has_address) {
1083 ERR(
"update_tree_extents returned %08lx\n",
Status);
1088 searchkey.
obj_id =
t->header.address;
1090 searchkey.
offset = 0xffffffffffffffff;
1094 ERR(
"error - find_item returned %08lx\n",
Status);
1110 ERR(
"refcount for extent %I64x was 0\n",
t->header.address);
1118 if (
t->header.level == 0) {
1122 while (le != &
t->itemlist) {
1139 le2 =
c->changed_extents.
Flink;
1140 while (le2 != &
c->changed_extents) {
1152 edr.
root =
t->root->id;
1160 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1166 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1173 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1183 sdr.
offset =
t->header.address;
1189 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1197 while (le2 != &ce->
refs) {
1243 while (le != &
t->itemlist) {
1250 &tbr, &td->
key,
t->header.level - 1,
Irp);
1252 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1262 sbr.
offset =
t->header.address;
1265 t->header.address,
false,
Irp);
1267 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1286 sbr.
offset =
t->parent->header.address;
1289 t->parent->header.address,
false,
Irp);
1291 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1298 tbr.
offset =
t->parent->header.tree_id;
1300 tbr.
offset =
t->header.tree_id;
1303 t->parent ? &
t->paritem->key :
NULL,
t->header.level,
Irp);
1305 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1314 if (rc > 1 ||
t->header.tree_id ==
t->root->id) {
1318 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
1323 t->has_address =
false;
1326 if (
t->header.tree_id ==
t->root->id) {
1331 if (
t->header.level > 0) {
1335 while (le != &
t->itemlist) {
1339 if (
t->header.tree_id ==
t->root->id) {
1342 sbr.
offset =
t->header.address;
1354 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1365 while (le != &
t->itemlist) {
1381 le2 =
c->changed_extents.
Flink;
1382 while (le2 != &
c->changed_extents) {
1394 if (
t->header.tree_id ==
t->root->id) {
1397 sdr.
offset =
t->header.address;
1403 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1409 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1418 edr.
root =
t->root->id;
1426 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1432 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1441 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1453 t->updated_extents =
true;
1454 t->header.tree_id =
t->root->id;
1462 bool changed =
false;
1467 le =
Vcb->trees.Flink;
1468 while (le != &
Vcb->trees) {
1471 if (
t->write && !
t->has_new_address) {
1474 if (
t->has_address) {
1478 if (!
c->cache_loaded) {
1481 if (!
c->cache_loaded) {
1485 ERR(
"load_cache_chunk returned %08lx\n",
Status);
1498 ERR(
"get_tree_new_address returned %08lx\n",
Status);
1502 TRACE(
"allocated extent %I64x\n",
t->new_address);
1507 c->used +=
Vcb->superblock.node_size;
1509 ERR(
"could not find chunk for address %I64x\n",
t->new_address);
1515 if (
t->header.level > max_level)
1516 max_level =
t->header.level;
1527 le =
Vcb->trees.Flink;
1528 while (le != &
Vcb->trees) {
1531 if (
t->write && !
t->updated_extents &&
t->has_address &&
t->header.level ==
level) {
1534 ERR(
"update_tree_extents returned %08lx\n",
Status);
1557 le =
Vcb->trees.Flink;
1558 while (le != &
Vcb->trees) {
1561 if (
t->write && !
t->parent) {
1562 if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
1566 searchkey.
obj_id =
t->root->id;
1568 searchkey.
offset = 0xffffffffffffffff;
1572 ERR(
"error - find_item returned %08lx\n",
Status);
1577 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
1581 TRACE(
"updating the address for root %I64x to %I64x\n", searchkey.
obj_id,
t->new_address);
1583 t->root->root_item.block_number =
t->new_address;
1584 t->root->root_item.root_level =
t->header.level;
1585 t->root->root_item.generation =
Vcb->superblock.generation;
1586 t->root->root_item.generation2 =
Vcb->superblock.generation;
1593 t->root->treeholder.address =
t->new_address;
1594 t->root->treeholder.generation =
Vcb->superblock.generation;
1606 ERR(
"update_chunk_caches returned %08lx\n",
Status);
1622 bool raid56 =
false;
1626 le = tree_writes->
Flink;
1627 while (le != tree_writes) {
1639 ERR(
"out of memory\n");
1674 le = tree_writes->
Flink;
1675 while (le != tree_writes) {
1685 ERR(
"out of memory\n");
1689 le = tree_writes->
Flink;
1691 while (le != tree_writes) {
1705 ERR(
"write_data returned %08lx\n",
Status);
1707 for (
i = 0;
i < num_bits;
i++) {
1720 for (
i = 0;
i < num_bits;
i++) {
1721 if (wtc[
i].stripes.Flink != &wtc[
i].
stripes) {
1724 while (le != &wtc[
i].stripes) {
1737 for (
i = 0;
i < num_bits;
i++) {
1738 if (wtc[
i].need_wait)
1742 for (
i = 0;
i < num_bits;
i++) {
1744 while (le != &wtc[
i].stripes) {
1764 le = tree_writes->
Flink;
1765 while (le != tree_writes) {
1784 ERR(
"flush_partial_stripe returned %08lx\n",
Status);
1801 switch (
Vcb->superblock.csum_type) {
1833 bool nothing_found =
true;
1837 le =
Vcb->trees.Flink;
1838 while (le != &
Vcb->trees) {
1841 if (
t->write &&
t->header.level ==
level) {
1842 KEY firstitem, searchkey;
1846 if (!
t->has_new_address) {
1847 ERR(
"error - tried to write tree with no new address\n");
1852 while (le2 != &
t->itemlist) {
1855 firstitem = td->
key;
1862 t->paritem->key = firstitem;
1863 t->paritem->treeholder.address =
t->new_address;
1864 t->paritem->treeholder.generation =
Vcb->superblock.generation;
1870 searchkey.
obj_id =
t->new_address;
1872 searchkey.
offset =
Vcb->superblock.node_size;
1876 ERR(
"error - find_item returned %08lx\n",
Status);
1881 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);
1894 nothing_found =
false;
1904 TRACE(
"allocated tree extents\n");
1906 le =
Vcb->trees.Flink;
1907 while (le != &
Vcb->trees) {
1910 #ifdef DEBUG_PARANOID 1916 #ifdef DEBUG_PARANOID 1921 while (le2 != &
t->itemlist) {
1930 }
else if (
keycmp(td->
key, lastkey) == -1) {
1939 if (
t->header.level == 0)
1945 if (
t->header.level == 0)
1950 if (num_items !=
t->header.num_items) {
1951 ERR(
"tree %I64x, level %x: num_items was %x, expected %x\n",
t->root->id,
t->header.level, num_items,
t->header.num_items);
1955 if (
size !=
t->size) {
1956 ERR(
"tree %I64x, level %x: size was %x, expected %x\n",
t->root->id,
t->header.level,
size,
t->size);
1960 if (
t->header.num_items == 0 &&
t->parent) {
1961 ERR(
"tree %I64x, level %x: tried to write empty tree with parent\n",
t->root->id,
t->header.level);
1966 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));
1971 ERR(
"tree %p\n",
t);
1973 while (le2 != &
t->itemlist) {
1983 t->header.address =
t->new_address;
1984 t->header.generation =
Vcb->superblock.generation;
1985 t->header.tree_id =
t->root->id;
1987 t->header.fs_uuid =
Vcb->superblock.metadata_uuid;
1988 t->has_address =
true;
1992 ERR(
"out of memory\n");
2002 if (
t->header.level == 0) {
2008 while (le2 != &
t->itemlist) {
2029 while (le2 != &
t->itemlist) {
2046 ERR(
"out of memory\n");
2060 bool inserted =
false;
2062 le2 = tree_writes.
Flink;
2063 while (le2 != &tree_writes) {
2085 ERR(
"do_tree_writes returned %08lx\n",
Status);
2112 sb->root_tree_generation =
Vcb->superblock.generation;
2116 sb->chunk_tree_generation =
Vcb->superblock.chunk_root_generation;
2121 searchkey.
offset = 0xffffffffffffffff;
2239 ERR(
"out of memory\n");
2255 ERR(
"out of memory\n");
2264 ERR(
"IoAllocateIrp failed\n");
2278 stripe->Irp->AssociatedIrp.SystemBuffer =
sb;
2285 ERR(
"IoAllocateMdl failed\n");
2315 ERR(
"no superblocks written!\n");
2328 le =
Vcb->trees.Flink;
2329 while (le != &
Vcb->trees) {
2332 if (
t->write && !
t->parent) {
2333 if (
t->root ==
Vcb->root_root) {
2334 Vcb->superblock.root_tree_addr =
t->new_address;
2335 Vcb->superblock.root_level =
t->header.level;
2336 }
else if (
t->root ==
Vcb->chunk_root) {
2337 Vcb->superblock.chunk_tree_addr =
t->new_address;
2338 Vcb->superblock.chunk_root_generation =
t->header.generation;
2339 Vcb->superblock.chunk_root_level =
t->header.level;
2356 le =
Vcb->devices.Flink;
2357 while (le != &
Vcb->devices) {
2360 if (
dev->devobj && !
dev->readonly) {
2363 ERR(
"write_superblock returned %08lx\n",
Status);
2372 ERR(
"error - not writing any superblocks\n");
2378 while (le != &
context.stripes) {
2389 while (le != &
context.stripes) {
2447 while (le != &ce->
refs) {
2470 ERR(
"increase_extent_refcount_data returned %08lx\n",
Status);
2493 while (le != &ce->
refs) {
2521 ERR(
"decrease_extent_refcount_data returned %08lx\n",
Status);
2537 ERR(
"error - find_item returned %08lx\n",
Status);
2542 ERR(
"could not find (%I64x,%x,%I64x) in extent tree\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2550 ERR(
"out of memory\n");
2560 ERR(
"insert_tree_item returned %08lx\n",
Status);
2567 ERR(
"delete_tree_item returned %08lx\n",
Status);
2579 #ifdef DEBUG_PARANOID 2581 WARN(
"old_refs not empty\n");
2586 c->used -= ce->
size;
2626 ERR(
"out of memory\n");
2635 ERR(
"insert_tree_item returned %08lx\n",
Status);
2646 }
while (length2 > 0);
2649 ERR(
"find_item returned %08lx\n",
Status);
2668 ERR(
"find_item returned %08lx\n",
Status);
2681 TRACE(
"endaddr = %I64x\n", endaddr);
2687 ERR(
"out of memory\n");
2693 ERR(
"out of memory\n");
2707 ERR(
"find_item returned %08lx\n",
Status);
2727 ERR(
"delete_tree_item returned %08lx\n",
Status);
2750 while (runlength != 0) {
2773 ERR(
"out of memory\n");
2785 ERR(
"insert_tree_item returned %08lx\n",
Status);
2794 }
while (runlength > 0);
2816 while (le != &
Vcb->chunks) {
2821 if (!
c->cache_loaded && (!
IsListEmpty(&
c->changed_extents) ||
c->used !=
c->oldused)) {
2825 ERR(
"load_cache_chunk returned %08lx\n",
Status);
2831 le2 =
c->changed_extents.Flink;
2832 while (le2 != &
c->changed_extents) {
2838 ERR(
"flush_changed_extent returned %08lx\n",
Status);
2851 ERR(
"create_chunk returned %08lx\n",
Status);
2858 if (
c->old_cache->dirty) {
2865 ERR(
"flush_fcb returned %08lx\n",
Status);
2873 ERR(
"commit_batch_list returned %08lx\n",
Status);
2881 if (
c->old_cache->refcount == 0)
2884 c->old_cache =
NULL;
2887 if (
c->used !=
c->oldused) {
2890 searchkey.
offset =
c->chunk_item->size;
2894 ERR(
"error - find_item returned %08lx\n",
Status);
2900 ERR(
"could not find (%I64x,%x,%I64x) in extent_root\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2915 ERR(
"out of memory\n");
2922 bgi->
used =
c->used;
2924 #ifdef DEBUG_PARANOID 2925 if (bgi->
used & 0x8000000000000000) {
2926 ERR(
"refusing to write BLOCK_GROUP_ITEM with negative usage value (%I64x)", bgi->
used);
2931 TRACE(
"adjusting usage of chunk %I64x to %I64x\n",
c->offset,
c->used);
2935 ERR(
"delete_tree_item returned %08lx\n",
Status);
2943 ERR(
"insert_tree_item returned %08lx\n",
Status);
2949 Vcb->superblock.bytes_used +=
c->used -
c->oldused;
2950 c->oldused =
c->used;
2970 while (le != &
t->itemlist) {
2987 ERR(
"out of memory\n");
2991 if (
t->header.level > 0) {
2993 if (!
nt->nonpaged) {
2994 ERR(
"out of memory\n");
3004 nt->header.address = 0;
3005 nt->header.generation =
Vcb->superblock.generation;
3006 nt->header.num_items =
t->header.num_items - numitems;
3009 nt->has_address =
false;
3011 nt->parent =
t->parent;
3013 #ifdef DEBUG_PARANOID 3014 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3018 nt->new_address = 0;
3019 nt->has_new_address =
false;
3020 nt->updated_extents =
false;
3021 nt->uniqueness_determined =
true;
3022 nt->is_unique =
true;
3023 nt->list_entry_hash.Flink =
NULL;
3030 nt->itemlist.Blink =
t->itemlist.Blink;
3031 nt->itemlist.Flink->Blink = &
nt->itemlist;
3032 nt->itemlist.Blink->Flink = &
nt->itemlist;
3035 t->itemlist.
Blink->Flink = &
t->itemlist;
3039 t->header.num_items = numitems;
3044 if (
nt->header.level > 0) {
3047 while (le != &
nt->itemlist) {
3052 #ifdef DEBUG_PARANOID 3062 while (le != &
nt->itemlist) {
3069 ERR(
"out of memory\n");
3083 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3085 ERR(
"out of memory\n");
3089 td->
key = newfirstitem->
key;
3098 nt->parent->header.num_items++;
3104 TRACE(
"adding new tree parent\n");
3106 if (
nt->header.level == 255) {
3107 ERR(
"cannot add parent to tree at level 255\n");
3113 ERR(
"out of memory\n");
3118 if (!
pt->nonpaged) {
3119 ERR(
"out of memory\n");
3127 pt->header.address = 0;
3128 pt->header.num_items = 2;
3129 pt->header.level =
nt->header.level + 1;
3132 pt->has_address =
false;
3137 pt->new_address = 0;
3138 pt->has_new_address =
false;
3139 pt->updated_extents =
false;
3141 pt->uniqueness_determined =
true;
3142 pt->is_unique =
true;
3143 pt->list_entry_hash.Flink =
NULL;
3149 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3151 ERR(
"out of memory\n");
3164 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3166 ERR(
"out of memory\n");
3170 td->
key = newfirstitem->
key;
3181 t->root->treeholder.tree =
pt;
3186 #ifdef DEBUG_PARANOID 3187 if (
t->parent &&
t->parent->header.level <=
t->header.level)
int3;
3188 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3192 t->root->root_item.bytes_used +=
Vcb->superblock.node_size;
3207 while (le != &
t->itemlist) {
3211 if (
t->header.level == 0)
3216 if (numitems == 0 &&
ds >
Vcb->superblock.node_size -
sizeof(
tree_header)) {
3217 ERR(
"(%I64x,%x,%I64x) in tree %I64x is too large (%x > %Ix)\n",
3245 if (
t->uniqueness_determined)
3246 return t->is_unique;
3251 if (
t->has_address) {
3252 searchkey.
obj_id =
t->header.address;
3254 searchkey.
offset = 0xffffffffffffffff;
3258 ERR(
"error - find_item returned %08lx\n",
Status);
3295 t->uniqueness_determined =
true;
3304 tree *next_tree, *par;
3308 TRACE(
"trying to amalgamate tree in root %I64x, level %x (size %u)\n",
t->root->id,
t->header.level,
t->size);
3311 le =
t->paritem->list_entry.
Flink;
3312 while (le != &
t->parent->itemlist) {
3331 ERR(
"do_load_tree returned %08lx\n",
Status);
3344 ERR(
"update_tree_extents returned %08lx\n",
Status);
3353 t->size += next_tree->
size;
3358 while (le != &next_tree->
itemlist) {
3363 #ifdef DEBUG_PARANOID 3374 while (le != &next_tree->
itemlist) {
3381 ERR(
"out of memory\n");
3395 t->itemlist.Blink->Flink->Blink =
t->itemlist.Blink;
3397 t->itemlist.Blink->Flink = &
t->itemlist;
3402 next_tree->
size = 0;
3408 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3415 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3420 if (!nextparitem->
ignore) {
3421 nextparitem->
ignore =
true;
3422 next_tree->
parent->header.num_items--;
3425 *done_deletions =
true;
3438 next_tree->
root->root_item.bytes_used -=
Vcb->superblock.node_size;
3445 ULONG avg_size = (
t->size + next_tree->
size) / 2;
3446 KEY firstitem = {0, 0, 0};
3447 bool changed =
false;
3449 TRACE(
"attempting rebalance\n");
3470 #ifdef DEBUG_PARANOID 3477 ERR(
"out of memory\n");
3491 t->header.num_items++;
3502 while (le != &next_tree->
itemlist) {
3506 firstitem = td->
key;
3538 searchkey.
offset =
t->header.level;
3542 ERR(
"error - find_item returned %08lx\n",
Status);
3553 ERR(
"out of memory\n");
3563 ERR(
"delete_tree_item returned %08lx\n",
Status);
3570 ERR(
"insert_tree_item returned %08lx\n",
Status);
3581 searchkey.
offset = 0xffffffffffffffff;
3585 ERR(
"error - find_item returned %08lx\n",
Status);
3600 ERR(
"out of memory\n");
3608 ERR(
"delete_tree_item returned %08lx\n",
Status);
3617 ERR(
"insert_tree_item returned %08lx\n",
Status);
3625 ERR(
"could not find EXTENT_ITEM for address %I64x\n",
address);
3633 if (
t->parent && !
t->parent->updated_extents &&
t->parent->has_address) {
3641 ERR(
"update_tree_extents returned %08lx\n",
Status);
3651 bool empty, done_deletions =
false;
3666 le =
Vcb->trees.Flink;
3668 while (le != &
Vcb->trees) {
3673 if (
t->write &&
t->header.level ==
level) {
3676 if (
t->header.num_items == 0) {
3678 done_deletions =
true;
3680 TRACE(
"deleting tree in root %I64x\n",
t->root->id);
3682 t->root->root_item.bytes_used -=
Vcb->superblock.node_size;
3684 if (
t->has_new_address) {
3688 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3692 t->has_new_address =
false;
3693 }
else if (
t->has_address) {
3697 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3701 t->has_address =
false;
3704 if (!
t->paritem->ignore) {
3705 t->paritem->ignore =
true;
3706 t->parent->header.num_items--;
3715 }
else if (
t->header.level != 0) {
3716 if (
t->has_new_address) {
3720 ERR(
"update_extent_level returned %08lx\n",
Status);
3725 t->header.level = 0;
3727 }
else if (
t->size >
Vcb->superblock.node_size -
sizeof(
tree_header)) {
3728 TRACE(
"splitting overlarge tree (%x > %Ix)\n",
t->size,
Vcb->superblock.node_size -
sizeof(
tree_header));
3730 if (!
t->updated_extents &&
t->has_address) {
3733 ERR(
"update_tree_extents_recursive returned %08lx\n",
Status);
3741 ERR(
"split_tree returned %08lx\n",
Status);
3753 TRACE(
"nothing found for level %lu\n",
level);
3758 min_size = (
Vcb->superblock.node_size -
sizeof(
tree_header)) / 2;
3759 min_size_fst = (
Vcb->superblock.node_size -
sizeof(
tree_header)) / 4;
3764 le =
Vcb->trees.Flink;
3766 while (le != &
Vcb->trees) {
3769 if (
t->write &&
t->header.level ==
level &&
t->header.num_items > 0 &&
t->parent &&
3777 ERR(
"try_tree_amalgamate returned %08lx\n",
Status);
3780 }
while (done &&
t->size < min_size);
3789 if (done_deletions) {
3793 le =
Vcb->trees.Flink;
3794 while (le != &
Vcb->trees) {
3798 if (
t->write &&
t->header.level ==
level) {
3799 if (!
t->parent &&
t->header.num_items == 1) {
3804 while (le2 != &
t->itemlist) {
3811 TRACE(
"deleting top-level tree in root %I64x with one item\n",
t->root->id);
3813 if (
t->has_new_address) {
3817 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3821 t->has_new_address =
false;
3822 }
else if (
t->has_address) {
3826 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3830 t->has_address =
false;
3834 KEY searchkey = {0,0,0};
3839 ERR(
"error - find_item returned %08lx\n",
Status);
3851 t->root->root_item.bytes_used -=
Vcb->superblock.node_size;
3856 child_tree->
root->treeholder.tree = child_tree;