Stack overflow in tokio-runtime-worker in fork-tree implementation

[nazar-pc]

I keep getting stack overflow in tokio-runtime-worker thread at large block height (700_000-900_000 blocks), it seems like related to absence of the finality gadget in my chain, am I right?:

(gdb) bt
#0  0x000055555594cc39 in <sc_client_db::BlockchainDb<Block> as sp_blockchain::header_metadata::HeaderMetadata<Block>>::header_metadata ()
#1  0x0000555555fba225 in sp_blockchain::header_metadata::lowest_common_ancestor ()
#2  0x0000555555acb10d in sc_client_api::utils::is_descendent_of::{{closure}} ()
#3  0x00005555560aeb21 in fork_tree::node_implementation::Node<H,N,V>::import ()
... many more lines just like that
#2998 0x00005555560aea7c in fork_tree::node_implementation::Node<H,N,V>::import ()
#2999 0x0000555555ebdc0d in fork_tree::ForkTree<H,N,V>::import ()
#3000 0x0000555555ae3ce5 in sc_consensus_epochs::EpochChanges<Hash,Number,E>::import ()
#3001 0x00005555560dd4cd in <sc_consensus_poc::PoCBlockImport<Block,Client,Inner> as sc_consensus::block_import::BlockImport<Block>>::import_block::{{closure}} ()
#3002 0x00005555561601a3 in <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll ()
#3003 0x00005555560ff475 in sc_consensus_slots::SimpleSlotWorker::on_slot::{{closure}} ()
#3004 0x0000555556177be3 in <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll ()
#3005 0x000055555616a129 in <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll ()
#3006 0x0000555556163aae in <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll ()
#3007 0x0000555555cf78c8 in <futures_util::future::maybe_done::MaybeDone<Fut> as core::future::future::Future>::poll ()
#3008 0x0000555555f845bf in <futures_util::future::join::Join<Fut1,Fut2> as core::future::future::Future>::poll ()
#3009 0x00005555559cab7a in <futures_util::future::future::map::Map<Fut,F> as core::future::future::Future>::poll ()
#3010 0x00005555559c5a63 in <futures_util::future::future::map::Map<Fut,F> as core::future::future::Future>::poll ()
#3011 0x0000555555debfaf in <sc_service::task_manager::prometheus_future::PrometheusFuture<T> as core::future::future::Future>::poll ()
#3012 0x0000555555cd1aa7 in <futures_util::future::select::Select<A,B> as core::future::future::Future>::poll ()
#3013 0x000055555619e64f in <core::future::from_generator::GenFuture<T> as core::future::future::Future>::poll ()
#3014 0x0000555555e51f42 in std::thread::local::LocalKey<T>::with ()
#3015 0x0000555555c064ca in tokio::park::thread::CachedParkThread::block_on ()
#3016 0x0000555555c8feba in tokio::runtime::handle::Handle::block_on ()
#3017 0x000055555614d53f in tokio::runtime::task::core::CoreStage<T>::poll ()
#3018 0x0000555555910650 in tokio::runtime::task::harness::Harness<T,S>::poll ()
#3019 0x0000555556b8e162 in tokio::runtime::blocking::pool::Inner::run ()
#3020 0x0000555556b91d5b in std::sys_common::backtrace::__rust_begin_short_backtrace::he5973d87642e29ac ()
#3021 0x0000555556b922b8 in core::ops::function::FnOnce::call_once{{vtable.shim}} ()
#3022 0x000055555748e5e3 in alloc::boxed::{impl#44}::call_once<(), dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global> () at /rustc/2c7bc5e33c25e29058cbafefe680da8d5e9220e9/library/alloc/src/boxed.rs:1636
#3023 alloc::boxed::{impl#44}::call_once<(), alloc::boxed::Box<dyn core::ops::function::FnOnce<(), Output=()>, alloc::alloc::Global>, alloc::alloc::Global> () at /rustc/2c7bc5e33c25e29058cbafefe680da8d5e9220e9/library/alloc/src/boxed.rs:1636
#3024 std::sys::unix::thread::{impl#2}::new::thread_start () at library/std/src/sys/unix/thread.rs:106
#3025 0x00007ffff7d30450 in start_thread (arg=0x7ffb6f9fc640) at pthread_create.c:473
#3026 0x00007ffff7afbd53 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

I think I'm missing something that would prevent such behavior, but don't know what.

[bkchr]

CC @andresilva

[nazar-pc]

I believe this is where the issue is:

substrate/client/consensus/babe/src/lib.rs

Lines 1551 to 1566 in c45c1cb

	prune_finalized(self.client.clone(), &mut epoch_changes)?;
	epoch_changes
	.import(
	descendent_query(&*self.client),
	hash,
	number,
	*block.header.parent_hash(),
	next_epoch,
	)
	.map_err(|e| {
	ConsensusError::ClientImport(format!(
	"Error importing epoch changes: {:?}",
	e
	))
	})?;

In case no blocks are finalized, this recursively traverses the whole tree apparently:

substrate/utils/fork-tree/src/lib.rs

Lines 683 to 720 in c45c1cb

	pub fn import<F, E: std::error::Error>(
	&mut self,
	mut hash: H,
	mut number: N,
	mut data: V,
	is_descendent_of: &F,
	) -> Result<Option<(H, N, V)>, Error<E>>
	where
	E: fmt::Debug,
	F: Fn(&H, &H) -> Result<bool, E>,
	{
	if self.hash == hash {
	return Err(Error::Duplicate)
	};
	if number <= self.number {
	return Ok(Some((hash, number, data)))
	}
	for node in self.children.iter_mut() {
	match node.import(hash, number, data, is_descendent_of)? {
	Some((h, n, d)) => {
	hash = h;
	number = n;
	data = d;
	},
	None => return Ok(None),
	}
	}
	if is_descendent_of(&self.hash, &hash)? {
	self.children.push(Node { data, hash, number, children: Vec::new() });
	Ok(None)
	} else {
	Ok(Some((hash, number, data)))
	}
	}

[andresilva]

The current implementation of BABE keeps all "open" epoch data in an in-memory data structure. Any epoch that has not been finalized is considered "open" since we could in theory build a fork on top of it. This in-memory data structure is the fork-tree and it is currently implemented as a recursive data structure. If a chain doesn't have any finality then this data structure will grow indefinitely and since it's currently recursive it will eventually lead to stack overflows. Even if it was rewritten to be iterative it would eventually lead to other problems like performance regressions (since it grows indefinitely). Since you don't have a finality gadget in your chain I would suggest that you still "manually" finalize blocks by calling client.finalize_block for example every 10000 blocks (or whatever long enough period you think is reasonable for your chain).