Deallocation hangs -- regression moving from `0.9.1` to `0.10.*`

[kevinaboos]

We just ran into a strange issue in Theseus OS where the deallocation path hangs. I'm not yet 100% sure what the precise failure condition is, but I wanted to post this issue sooner rather than later in case anyone else has run across this.

So far it only occurs in an OS execution path that causes more heap allocations than what we normally do, so it could be related to heavy heap usage. Also not sure if it's related to the pending issue #66, which alludes to an issue with fragmentation (?).

Relevant details

Theseus uses linked_list_allocator as its early heap allocator. Through bisection, I've confirmed that this issue only occurred after upgrading from linked_list_allocator 0.9.1 to 0.10.3 (https://github.com/theseus-os/Theseus/pull/646), and I confirmed that the problem is present in both 0.10.1 and 0.10.2 as well. If it's relevant, we're using linked_list_allocator as such:

[dependencies.linked_list_allocator]
version = "0.10.3"
default-features = false
features = [ "const_mut_refs" ]

Using Rust nightly 1.64

$ rustc --version
rustc 1.64.0-nightly (f8588549c 2022-07-18)

Backtrace

I have a partial backtrace from GDB but it isn't complete; will work on improving it as I narrow down the exact cause.

#0  0xffffffff8011e916 in linked_list_allocator::hole::Cursor::try_insert_after (node=..., self=<optimized out>) at src/hole.rs:547
#1  linked_list_allocator::hole::deallocate (list=<optimized out>, addr=0xfffffe80004d1700 "\000", size=4096) at src/hole.rs:679
#2  linked_list_allocator::hole::HoleList::deallocate (self=<optimized out>, ptr=..., layout=...) at src/hole.rs:438

I can also add steps to repro this behavior in Theseus but it probably wouldn't be useful until I can more specifically determine the exact failure condition.

[MaderNoob]

I created an alternative memory allocator which solves this problem and provides many more benefits, such as improved performance and memory utilization.

[phil-opp]

Thanks for reporting this! We just published a new v0.10.4 release to fix #66, maybe this fixes your issue as well. Is there some test case that we could try to investigare this?

[kevinaboos]

I created an alternative memory allocator which solves this problem and provides many more benefits, such as improved performance and memory utilization.

Thanks for letting me know, i'll check it out!

[kevinaboos]

Thanks for reporting this! We just published a new v0.10.4 release to fix #66, maybe this fixes your issue as well. Is there some test case that we could try to investigare this?

Unfortunately I can confirm that the problem still occurs with v0.10.4. Apologies, I haven't yet had the time to identify the specific allocation pattern that causes the hang so I can create an easy test case. It is consistently reproducible on Theseus, however it is theoretically possible that this behavior is a manifestation of another unrelated problem lurking in Theseus.

I plan to dig into it within the next two weeks and will update this issue with my findings.

[phil-opp]

Thanks for testing! Let me know if I can help with any debugging.