28#define MAX_CSUM_SIZE (4096 - sizeof(tree_header) - (2 * sizeof(leaf_node)))
32#define BATCH_ITEM_LIMIT 1000
89 ERR(
"IoAllocateIrp failed\n");
98 Irp->AssociatedIrp.SystemBuffer =
data;
103 if (!
Irp->MdlAddress) {
118 ERR(
"MmProbeAndLockPages threw exception %08lx\n",
Status);
143 ERR(
"IoCallDriver returned %08lx\n",
Status);
160 ERR(
"out of memory\n");
166 dev->num_trim_entries++;
195 while (le != &
c->deleting) {
204 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
205 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim)
210 uint16_t startoffstripe, endoffstripe,
i;
212 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &startoff, &startoffstripe);
213 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes, &endoff, &endoffstripe);
215 for (
i = 0;
i <
c->chunk_item->num_stripes;
i++) {
216 if (
c->devices[
i] &&
c->devices[
i]->devobj && !
c->devices[
i]->readonly &&
c->devices[
i]->trim) {
219 if (startoffstripe >
i)
220 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
221 else if (startoffstripe ==
i)
222 stripestart = startoff;
224 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
226 if (endoffstripe >
i)
227 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
228 else if (endoffstripe ==
i)
229 stripeend = endoff + 1;
231 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
233 if (stripestart != stripeend)
239 uint16_t sub_stripes, startoffstripe, endoffstripe,
i;
241 sub_stripes =
max(1,
c->chunk_item->sub_stripes);
243 get_raid0_offset(
s->address -
c->offset,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &startoff, &startoffstripe);
244 get_raid0_offset(
s->address -
c->offset +
s->size - 1,
c->chunk_item->stripe_length,
c->chunk_item->num_stripes / sub_stripes, &endoff, &endoffstripe);
246 startoffstripe *= sub_stripes;
247 endoffstripe *= sub_stripes;
249 for (
i = 0;
i <
c->chunk_item->num_stripes;
i += sub_stripes) {
253 if (startoffstripe >
i)
254 stripestart = startoff - (startoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
255 else if (startoffstripe ==
i)
256 stripestart = startoff;
258 stripestart = startoff - (startoff %
c->chunk_item->stripe_length);
260 if (endoffstripe >
i)
261 stripeend = endoff - (endoff %
c->chunk_item->stripe_length) +
c->chunk_item->stripe_length;
262 else if (endoffstripe ==
i)
263 stripeend = endoff + 1;
265 stripeend = endoff - (endoff %
c->chunk_item->stripe_length);
267 if (stripestart != stripeend) {
268 for (
j = 0;
j < sub_stripes;
j++) {
269 if (
c->devices[
i+
j] &&
c->devices[
i+
j]->devobj && !
c->devices[
i+
j]->readonly &&
c->devices[
i+
j]->trim)
287#ifdef DEBUG_TRIM_EMULATION
313#ifdef DEBUG_TRIM_EMULATION
317 unsigned int i = 0,
count = 0;
319 le =
dev->trim_list.Flink;
320 while (le != &
dev->trim_list) {
331 ERR(
"out of memory\n");
338 le =
dev->trim_list.Flink;
339 while (le != &
dev->trim_list) {
343 WARN(
"(%I64x, %I64x)\n",
s->address,
s->size);
348 ERR(
"IoAllocateIrp failed\n");
357 ERR(
"out of memory\n");
364 ERR(
"IoAllocateMdl failed\n");
406#ifndef DEBUG_TRIM_EMULATION
414 le =
Vcb->chunks.Flink;
415 while (le != &
Vcb->chunks) {
418 if (
c->space_changed) {
421 if (
c->space_changed) {
422 if (
Vcb->trim && !
Vcb->options.no_trim)
434 c->space_changed =
false;
444 if (
Vcb->trim && !
Vcb->options.no_trim) {
445#ifndef DEBUG_TRIM_EMULATION
451 le =
Vcb->devices.Flink;
452 while (le != &
Vcb->devices) {
455 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0)
471 ERR(
"out of memory\n");
478 le =
Vcb->devices.Flink;
479 while (le != &
Vcb->devices) {
482 if (
dev->devobj && !
dev->readonly &&
dev->trim &&
dev->num_trim_entries > 0) {
483#ifdef DEBUG_TRIM_EMULATION
494 ERR(
"out of memory\n");
501 stripe->dmdsa->ParameterBlockOffset = 0;
502 stripe->dmdsa->ParameterBlockLength = 0;
510 le2 =
dev->trim_list.Flink;
511 while (le2 != &
dev->trim_list) {
524 ERR(
"IoAllocateIrp failed\n");
536 stripe->Irp->AssociatedIrp.SystemBuffer =
stripe->dmdsa;
552 dev->num_trim_entries = 0;
554#ifndef DEBUG_TRIM_EMULATION
562#ifndef DEBUG_TRIM_EMULATION
582 le =
Vcb->trees.Flink;
583 while (le != &
Vcb->trees) {
587 if (
t->header.num_items == 0 &&
t->parent) {
588#ifdef DEBUG_WRITE_LOOPS
589 ERR(
"empty tree found, looping again\n");
594 if (
t->size > maxsize) {
595#ifdef DEBUG_WRITE_LOOPS
596 ERR(
"overlarge tree found (%u > %u), looping again\n",
t->size, maxsize);
601 if (!
t->has_new_address) {
602#ifdef DEBUG_WRITE_LOOPS
603 ERR(
"tree found without new address, looping again\n");
620 bool nothing_found =
true;
624 le =
Vcb->trees.Flink;
625 while (le != &
Vcb->trees) {
628 if (
t->write &&
t->header.level ==
level) {
629 TRACE(
"tree %p: root = %I64x, level = %x, parent = %p\n",
t,
t->header.tree_id,
t->header.level,
t->parent);
631 nothing_found =
false;
634 if (!
t->parent->write)
635 TRACE(
"adding tree %p (level %x)\n",
t->parent,
t->header.level);
637 t->parent->write =
true;
638 }
else if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
643 searchkey.
obj_id =
t->root->id;
645 searchkey.
offset = 0xffffffffffffffff;
649 ERR(
"error - find_item returned %08lx\n",
Status);
654 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
662 ERR(
"out of memory\n");
670 ERR(
"delete_tree_item returned %08lx\n",
Status);
677 ERR(
"insert_tree_item returned %08lx\n",
Status);
716 ERR(
"out of memory\n");
728 ERR(
"insert_tree_item returned %08lx\n",
Status);
750 if (
Vcb->superblock.node_size >
c->chunk_item->size -
c->used)
753 if (!
c->cache_loaded) {
757 ERR(
"load_cache_chunk returned %08lx\n",
Status);
765 if (!
c->last_alloc_set) {
768 c->last_alloc =
s->address;
769 c->last_alloc_set =
true;
771 if (
s->size >=
Vcb->superblock.node_size) {
773 c->last_alloc +=
Vcb->superblock.node_size;
779 while (le != &
c->space) {
782 if (
s->address <=
c->last_alloc &&
s->address +
s->size >=
c->last_alloc +
Vcb->superblock.node_size) {
784 c->last_alloc +=
Vcb->superblock.node_size;
792 while (le != &
c->space_size) {
795 if (
s->size ==
Vcb->superblock.node_size) {
797 c->last_alloc =
s->address +
Vcb->superblock.node_size;
799 }
else if (
s->size <
Vcb->superblock.node_size) {
800 if (le ==
c->space_size.
Flink)
806 c->last_alloc =
s->address +
Vcb->superblock.node_size;
816 if (
s->size >
Vcb->superblock.node_size) {
818 c->last_alloc =
s->address +
Vcb->superblock.node_size;
831 TRACE(
"(%p, %x, %I64x, %p, %p, %p, %p)\n",
Vcb,
level, root_id,
c, new_address,
Irp,
rollback);
847 ERR(
"out of memory\n");
860 ERR(
"insert_tree_item returned %08lx\n",
Status);
889 if (
t->has_address) {
894 t->new_address =
addr;
895 t->has_new_address =
true;
902 le =
Vcb->chunks.Flink;
903 while (le != &
Vcb->chunks) {
906 if (!
c->readonly && !
c->reloc) {
913 t->new_address =
addr;
914 t->has_new_address =
true;
930 ERR(
"alloc_chunk returned %08lx\n",
Status);
937 if ((
c->chunk_item->size -
c->used) >=
Vcb->superblock.node_size) {
941 t->new_address =
addr;
942 t->has_new_address =
true;
951 ERR(
"couldn't find any metadata chunks with %x bytes free\n",
Vcb->superblock.node_size);
964 ERR(
"error - refcount for extent %I64x was 0\n",
address);
971 root =
t->header.tree_id;
975 ERR(
"decrease_extent_refcount_tree returned %08lx\n",
Status);
985 if (!
c->cache_loaded) {
989 ERR(
"load_cache_chunk returned %08lx\n",
Status);
995 c->used -=
Vcb->superblock.node_size;
1001 ERR(
"could not find chunk for address %I64x\n",
address);
1014 while (le2 !=
list) {
1027 ERR(
"out of memory\n");
1051 while (le2 !=
list) {
1064 ERR(
"out of memory\n");
1086 if (!
t->updated_extents &&
t->has_address) {
1089 ERR(
"update_tree_extents returned %08lx\n",
Status);
1094 searchkey.
obj_id =
t->header.address;
1096 searchkey.
offset = 0xffffffffffffffff;
1100 ERR(
"error - find_item returned %08lx\n",
Status);
1116 ERR(
"refcount for extent %I64x was 0\n",
t->header.address);
1124 if (
t->header.level == 0) {
1128 while (le != &
t->itemlist) {
1145 le2 =
c->changed_extents.
Flink;
1146 while (le2 != &
c->changed_extents) {
1158 edr.
root =
t->root->id;
1166 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1172 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1179 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1189 sdr.
offset =
t->header.address;
1195 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1203 while (le2 != &ce->
refs) {
1249 while (le != &
t->itemlist) {
1256 &tbr, &td->
key,
t->header.level - 1,
Irp);
1258 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1268 sbr.
offset =
t->header.address;
1271 t->header.address,
false,
Irp);
1273 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1292 sbr.
offset =
t->parent->header.address;
1295 t->parent->header.address,
false,
Irp);
1297 ERR(
"decrease_extent_refcount returned %08lx\n",
Status);
1304 tbr.
offset =
t->parent->header.tree_id;
1306 tbr.
offset =
t->header.tree_id;
1309 t->parent ? &
t->paritem->key :
NULL,
t->header.level,
Irp);
1311 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1317 t->header.flags &= ~HEADER_FLAG_SHARED_BACKREF;
1320 if (rc > 1 ||
t->header.tree_id ==
t->root->id) {
1324 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
1329 t->has_address =
false;
1332 if (
t->header.tree_id ==
t->root->id) {
1337 if (
t->header.level > 0) {
1341 while (le != &
t->itemlist) {
1345 if (
t->header.tree_id ==
t->root->id) {
1348 sbr.
offset =
t->header.address;
1360 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1371 while (le != &
t->itemlist) {
1387 le2 =
c->changed_extents.
Flink;
1388 while (le2 != &
c->changed_extents) {
1400 if (
t->header.tree_id ==
t->root->id) {
1403 sdr.
offset =
t->header.address;
1409 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1415 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1424 edr.
root =
t->root->id;
1432 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1438 ERR(
"add_changed_extent_ref_edr returned %08lx\n",
Status);
1447 ERR(
"increase_extent_refcount returned %08lx\n",
Status);
1459 t->updated_extents =
true;
1460 t->header.tree_id =
t->root->id;
1468 bool changed =
false;
1473 le =
Vcb->trees.Flink;
1474 while (le != &
Vcb->trees) {
1477 if (
t->write && !
t->has_new_address) {
1480 if (
t->has_address) {
1484 if (!
c->cache_loaded) {
1487 if (!
c->cache_loaded) {
1491 ERR(
"load_cache_chunk returned %08lx\n",
Status);
1504 ERR(
"get_tree_new_address returned %08lx\n",
Status);
1508 TRACE(
"allocated extent %I64x\n",
t->new_address);
1513 c->used +=
Vcb->superblock.node_size;
1515 ERR(
"could not find chunk for address %I64x\n",
t->new_address);
1521 if (
t->header.level > max_level)
1522 max_level =
t->header.level;
1533 le =
Vcb->trees.Flink;
1534 while (le != &
Vcb->trees) {
1537 if (
t->write && !
t->updated_extents &&
t->has_address &&
t->header.level ==
level) {
1540 ERR(
"update_tree_extents returned %08lx\n",
Status);
1563 le =
Vcb->trees.Flink;
1564 while (le != &
Vcb->trees) {
1567 if (
t->write && !
t->parent) {
1568 if (
t->root !=
Vcb->root_root &&
t->root !=
Vcb->chunk_root) {
1572 searchkey.
obj_id =
t->root->id;
1574 searchkey.
offset = 0xffffffffffffffff;
1578 ERR(
"error - find_item returned %08lx\n",
Status);
1583 ERR(
"could not find ROOT_ITEM for tree %I64x\n", searchkey.
obj_id);
1587 TRACE(
"updating the address for root %I64x to %I64x\n", searchkey.
obj_id,
t->new_address);
1589 t->root->root_item.block_number =
t->new_address;
1590 t->root->root_item.root_level =
t->header.level;
1591 t->root->root_item.generation =
Vcb->superblock.generation;
1592 t->root->root_item.generation2 =
Vcb->superblock.generation;
1599 t->root->treeholder.address =
t->new_address;
1600 t->root->treeholder.generation =
Vcb->superblock.generation;
1612 ERR(
"update_chunk_caches returned %08lx\n",
Status);
1628 bool raid56 =
false;
1632 le = tree_writes->
Flink;
1633 while (le != tree_writes) {
1645 ERR(
"out of memory\n");
1680 le = tree_writes->
Flink;
1681 while (le != tree_writes) {
1691 ERR(
"out of memory\n");
1695 le = tree_writes->
Flink;
1697 while (le != tree_writes) {
1711 ERR(
"write_data returned %08lx\n",
Status);
1713 for (
i = 0;
i < num_bits;
i++) {
1726 for (
i = 0;
i < num_bits;
i++) {
1727 if (wtc[
i].stripes.Flink != &wtc[
i].
stripes) {
1730 while (le != &wtc[
i].stripes) {
1743 for (
i = 0;
i < num_bits;
i++) {
1744 if (wtc[
i].need_wait)
1748 for (
i = 0;
i < num_bits;
i++) {
1750 while (le != &wtc[
i].stripes) {
1770 le = tree_writes->
Flink;
1771 while (le != tree_writes) {
1790 ERR(
"flush_partial_stripe returned %08lx\n",
Status);
1807 switch (
Vcb->superblock.csum_type) {
1839 bool nothing_found =
true;
1843 le =
Vcb->trees.Flink;
1844 while (le != &
Vcb->trees) {
1847 if (
t->write &&
t->header.level ==
level) {
1848 KEY firstitem, searchkey;
1852 if (!
t->has_new_address) {
1853 ERR(
"error - tried to write tree with no new address\n");
1858 while (le2 != &
t->itemlist) {
1861 firstitem = td->
key;
1868 t->paritem->key = firstitem;
1869 t->paritem->treeholder.address =
t->new_address;
1870 t->paritem->treeholder.generation =
Vcb->superblock.generation;
1876 searchkey.
obj_id =
t->new_address;
1878 searchkey.
offset =
Vcb->superblock.node_size;
1882 ERR(
"error - find_item returned %08lx\n",
Status);
1887 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);
1900 nothing_found =
false;
1910 TRACE(
"allocated tree extents\n");
1912 le =
Vcb->trees.Flink;
1913 while (le != &
Vcb->trees) {
1916#ifdef DEBUG_PARANOID
1922#ifdef DEBUG_PARANOID
1927 while (le2 != &
t->itemlist) {
1936 }
else if (
keycmp(td->
key, lastkey) == -1) {
1945 if (
t->header.level == 0)
1951 if (
t->header.level == 0)
1956 if (num_items !=
t->header.num_items) {
1957 ERR(
"tree %I64x, level %x: num_items was %x, expected %x\n",
t->root->id,
t->header.level, num_items,
t->header.num_items);
1961 if (
size !=
t->size) {
1962 ERR(
"tree %I64x, level %x: size was %x, expected %x\n",
t->root->id,
t->header.level,
size,
t->size);
1966 if (
t->header.num_items == 0 &&
t->parent) {
1967 ERR(
"tree %I64x, level %x: tried to write empty tree with parent\n",
t->root->id,
t->header.level);
1972 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));
1977 ERR(
"tree %p\n",
t);
1979 while (le2 != &
t->itemlist) {
1989 t->header.address =
t->new_address;
1990 t->header.generation =
Vcb->superblock.generation;
1991 t->header.tree_id =
t->root->id;
1993 t->header.fs_uuid =
Vcb->superblock.metadata_uuid;
1994 t->has_address =
true;
1998 ERR(
"out of memory\n");
2008 if (
t->header.level == 0) {
2014 while (le2 != &
t->itemlist) {
2035 while (le2 != &
t->itemlist) {
2052 ERR(
"out of memory\n");
2066 bool inserted =
false;
2068 le2 = tree_writes.
Flink;
2069 while (le2 != &tree_writes) {
2091 ERR(
"do_tree_writes returned %08lx\n",
Status);
2118 sb->root_tree_generation =
Vcb->superblock.generation;
2122 sb->chunk_tree_generation =
Vcb->superblock.chunk_root_generation;
2127 searchkey.
offset = 0xffffffffffffffff;
2245 ERR(
"out of memory\n");
2261 ERR(
"out of memory\n");
2270 ERR(
"IoAllocateIrp failed\n");
2284 stripe->Irp->AssociatedIrp.SystemBuffer =
sb;
2291 ERR(
"IoAllocateMdl failed\n");
2321 ERR(
"no superblocks written!\n");
2334 le =
Vcb->trees.Flink;
2335 while (le != &
Vcb->trees) {
2338 if (
t->write && !
t->parent) {
2339 if (
t->root ==
Vcb->root_root) {
2340 Vcb->superblock.root_tree_addr =
t->new_address;
2341 Vcb->superblock.root_level =
t->header.level;
2342 }
else if (
t->root ==
Vcb->chunk_root) {
2343 Vcb->superblock.chunk_tree_addr =
t->new_address;
2344 Vcb->superblock.chunk_root_generation =
t->header.generation;
2345 Vcb->superblock.chunk_root_level =
t->header.level;
2362 le =
Vcb->devices.Flink;
2363 while (le != &
Vcb->devices) {
2366 if (
dev->devobj && !
dev->readonly) {
2369 ERR(
"write_superblock returned %08lx\n",
Status);
2378 ERR(
"error - not writing any superblocks\n");
2384 while (le != &
context.stripes) {
2395 while (le != &
context.stripes) {
2453 while (le != &ce->
refs) {
2476 ERR(
"increase_extent_refcount_data returned %08lx\n",
Status);
2499 while (le != &ce->
refs) {
2527 ERR(
"decrease_extent_refcount_data returned %08lx\n",
Status);
2543 ERR(
"error - find_item returned %08lx\n",
Status);
2548 ERR(
"could not find (%I64x,%x,%I64x) in extent tree\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2556 ERR(
"out of memory\n");
2566 ERR(
"insert_tree_item returned %08lx\n",
Status);
2573 ERR(
"delete_tree_item returned %08lx\n",
Status);
2585#ifdef DEBUG_PARANOID
2587 WARN(
"old_refs not empty\n");
2592 c->used -= ce->
size;
2632 ERR(
"out of memory\n");
2641 ERR(
"insert_tree_item returned %08lx\n",
Status);
2652 }
while (length2 > 0);
2655 ERR(
"find_item returned %08lx\n",
Status);
2674 ERR(
"find_item returned %08lx\n",
Status);
2687 TRACE(
"endaddr = %I64x\n", endaddr);
2693 ERR(
"out of memory\n");
2699 ERR(
"out of memory\n");
2713 ERR(
"find_item returned %08lx\n",
Status);
2733 ERR(
"delete_tree_item returned %08lx\n",
Status);
2756 while (runlength != 0) {
2779 ERR(
"out of memory\n");
2791 ERR(
"insert_tree_item returned %08lx\n",
Status);
2800 }
while (runlength > 0);
2822 while (le != &
Vcb->chunks) {
2827 if (!
c->cache_loaded && (!
IsListEmpty(&
c->changed_extents) ||
c->used !=
c->oldused)) {
2831 ERR(
"load_cache_chunk returned %08lx\n",
Status);
2837 le2 =
c->changed_extents.Flink;
2838 while (le2 != &
c->changed_extents) {
2844 ERR(
"flush_changed_extent returned %08lx\n",
Status);
2857 ERR(
"create_chunk returned %08lx\n",
Status);
2864 if (
c->old_cache->dirty) {
2871 ERR(
"flush_fcb returned %08lx\n",
Status);
2879 ERR(
"commit_batch_list returned %08lx\n",
Status);
2887 if (
c->old_cache->refcount == 0)
2890 c->old_cache =
NULL;
2893 if (
c->used !=
c->oldused) {
2896 searchkey.
offset =
c->chunk_item->size;
2900 ERR(
"error - find_item returned %08lx\n",
Status);
2906 ERR(
"could not find (%I64x,%x,%I64x) in extent_root\n", searchkey.
obj_id, searchkey.
obj_type, searchkey.
offset);
2921 ERR(
"out of memory\n");
2928 bgi->
used =
c->used;
2930#ifdef DEBUG_PARANOID
2931 if (bgi->
used & 0x8000000000000000) {
2932 ERR(
"refusing to write BLOCK_GROUP_ITEM with negative usage value (%I64x)\n", bgi->
used);
2937 TRACE(
"adjusting usage of chunk %I64x to %I64x\n",
c->offset,
c->used);
2941 ERR(
"delete_tree_item returned %08lx\n",
Status);
2949 ERR(
"insert_tree_item returned %08lx\n",
Status);
2955 Vcb->superblock.bytes_used +=
c->used -
c->oldused;
2956 c->oldused =
c->used;
2976 while (le != &
t->itemlist) {
2993 ERR(
"out of memory\n");
2997 if (
t->header.level > 0) {
2999 if (!
nt->nonpaged) {
3000 ERR(
"out of memory\n");
3010 nt->header.address = 0;
3011 nt->header.generation =
Vcb->superblock.generation;
3012 nt->header.num_items =
t->header.num_items - numitems;
3015 nt->has_address =
false;
3017 nt->parent =
t->parent;
3019#ifdef DEBUG_PARANOID
3020 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3024 nt->new_address = 0;
3025 nt->has_new_address =
false;
3026 nt->updated_extents =
false;
3027 nt->uniqueness_determined =
true;
3028 nt->is_unique =
true;
3029 nt->list_entry_hash.Flink =
NULL;
3036 nt->itemlist.Blink =
t->itemlist.Blink;
3037 nt->itemlist.Flink->Blink = &
nt->itemlist;
3038 nt->itemlist.Blink->Flink = &
nt->itemlist;
3041 t->itemlist.
Blink->Flink = &
t->itemlist;
3045 t->header.num_items = numitems;
3050 if (
nt->header.level > 0) {
3053 while (le != &
nt->itemlist) {
3058#ifdef DEBUG_PARANOID
3068 while (le != &
nt->itemlist) {
3075 ERR(
"out of memory\n");
3089 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3091 ERR(
"out of memory\n");
3095 td->
key = newfirstitem->
key;
3104 nt->parent->header.num_items++;
3110 TRACE(
"adding new tree parent\n");
3112 if (
nt->header.level == 255) {
3113 ERR(
"cannot add parent to tree at level 255\n");
3119 ERR(
"out of memory\n");
3124 if (!
pt->nonpaged) {
3125 ERR(
"out of memory\n");
3133 pt->header.address = 0;
3134 pt->header.num_items = 2;
3135 pt->header.level =
nt->header.level + 1;
3138 pt->has_address =
false;
3143 pt->new_address = 0;
3144 pt->has_new_address =
false;
3145 pt->updated_extents =
false;
3147 pt->uniqueness_determined =
true;
3148 pt->is_unique =
true;
3149 pt->list_entry_hash.Flink =
NULL;
3155 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3157 ERR(
"out of memory\n");
3170 td = ExAllocateFromPagedLookasideList(&
Vcb->tree_data_lookaside);
3172 ERR(
"out of memory\n");
3176 td->
key = newfirstitem->
key;
3187 t->root->treeholder.tree =
pt;
3192#ifdef DEBUG_PARANOID
3193 if (
t->parent &&
t->parent->header.level <=
t->header.level)
int3;
3194 if (
nt->parent &&
nt->parent->header.level <=
nt->header.level)
int3;
3198 t->root->root_item.bytes_used +=
Vcb->superblock.node_size;
3213 while (le != &
t->itemlist) {
3217 if (
t->header.level == 0)
3222 if (numitems == 0 &&
ds >
Vcb->superblock.node_size -
sizeof(
tree_header)) {
3223 ERR(
"(%I64x,%x,%I64x) in tree %I64x is too large (%x > %Ix)\n",
3251 if (
t->uniqueness_determined)
3252 return t->is_unique;
3257 if (
t->has_address) {
3258 searchkey.
obj_id =
t->header.address;
3260 searchkey.
offset = 0xffffffffffffffff;
3264 ERR(
"error - find_item returned %08lx\n",
Status);
3301 t->uniqueness_determined =
true;
3310 tree *next_tree, *par;
3314 TRACE(
"trying to amalgamate tree in root %I64x, level %x (size %u)\n",
t->root->id,
t->header.level,
t->size);
3317 le =
t->paritem->list_entry.
Flink;
3318 while (le != &
t->parent->itemlist) {
3337 ERR(
"do_load_tree returned %08lx\n",
Status);
3350 ERR(
"update_tree_extents returned %08lx\n",
Status);
3359 t->size += next_tree->
size;
3364 while (le != &next_tree->
itemlist) {
3369#ifdef DEBUG_PARANOID
3380 while (le != &next_tree->
itemlist) {
3387 ERR(
"out of memory\n");
3401 t->itemlist.Blink->Flink->Blink =
t->itemlist.Blink;
3403 t->itemlist.Blink->Flink = &
t->itemlist;
3408 next_tree->
size = 0;
3414 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3421 ERR(
"reduce_tree_extent returned %08lx\n",
Status);
3426 if (!nextparitem->
ignore) {
3427 nextparitem->
ignore =
true;
3428 next_tree->
parent->header.num_items--;
3431 *done_deletions =
true;
3444 next_tree->
root->root_item.bytes_used -=
Vcb->superblock.node_size;
3451 ULONG avg_size = (
t->size + next_tree->
size) / 2;
3452 KEY firstitem = {0, 0, 0};
3453 bool changed =
false;
3455 TRACE(
"attempting rebalance\n");
3476#ifdef DEBUG_PARANOID
3483 ERR(
"out of memory\n");
3497 t->header.num_items++;
3508 while (le != &next_tree->
itemlist) {
3512 firstitem = td->
key;
3544 searchkey.
offset =
t->header.level;
3548 ERR(
"error - find_item returned %08lx\n",
Status);
3559 ERR(
"out of memory\n");
3569 ERR(
"delete_tree_item returned %08lx\n",
Status);