rust-osdev/linked-list-allocator

linked-list-allocator's Issues

no `Alloc` in `alloc`

   Compiling bitflags v1.2.1
   Compiling lazy_static v1.4.0
   Compiling linked_list_allocator v0.6.5
error[E0432]: unresolved import `alloc::alloc::Alloc`
  --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.6.5/src/lib.rs:14:20
   |
14 | use alloc::alloc::{Alloc, AllocErr, Layout};
   |                    ^^^^^
   |                    |
   |                    no `Alloc` in `alloc`
   |                    help: a similar name exists in the module: `alloc`

error: aborting due to previous error

Crate does not compile

https://github.com/phil-opp/linked-list-allocator/blob/b1332a3268b07dcac60f109e6d56634e0a8fe61c/src/hole.rs#L14

For whatever reason, I had no issues so far, however, today I was greeted with the following error:

error[E0658]: mutable references are not allowed in constant functions
  --> /home/dani/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.8.5/src/hole.rs:18:23
   |
18 |                 next: None,
   |                       ^^^^
   |
   = note: see issue #57349 <https://github.com/rust-lang/rust/issues/57349> for more information
   = help: add `#![feature(const_mut_refs)]` to the crate attributes to enable

What's weird to me, is that I was able to use the crate for months without any complaint from the compiler, but I did not find a compiler on godbolt.org that compiled the relevant bits of code. Maybe something was broken for months in nightly?

Anyways, the versions I tried:

• 2020-09-22 (1.48 nightly) compiles fine
• 2020-10-21 (1.49 nightly) has the above error

How to provide implementation of libc calloc, free, realloc

I'm currently using alloc-cortex-m which uses this crate and I'd like to implement some memory intrinsics of libc using the list allocator. In particular I need to implement calloc, free, realloc but I'm currently stuck with how to do it.

I think I've managed to do it for calloc (https://os.phil-opp.com/heap-allocation/ has been helpfulp 😄), but I've no idea for free and realloc. alloc::dealloc requires to know the layout, but the C function provides only a pointer, whereas alloc::realloc is not currently implemented in this crate.

This is what I've written so far, the target is thumbv7m-none-eabi:

const ALIGN: usize = core::mem::size_of::<i32>();

#[no_mangle]
pub extern "C" fn calloc(num: size_t, size: size_t) -> *mut c_void {
    let size = (num * size) as usize;
    let layout = core::alloc::Layout::from_size_align(size, ALIGN).expect("Cannot create layout");

    unsafe { alloc::alloc::alloc(layout) as *mut c_void }
}

#[no_mangle]
pub extern "C" fn free(_ptr: *mut u8) {
    unimplemented!()
}

#[no_mangle]
pub extern "C" fn realloc(ptr: *mut c_void, size: size_t) -> *mut c_void {
    if ptr.is_null() {
        return calloc(1, size);
    }

    unimplemented!()
}

extend with "unavailable" space

Hi!

I would like to have an extend method that allows to extend the heap with a space that is considered taken.
I'm working in embedded systems without MMU, so I have to work with raw memory spaces. I have three SRAM areas at 0x10000000 with the size of 16kB and at 0x20000000 with 2kB and 0x20004000 with 2kB.

Currently I can only define the global allocator to use the memory space from 0x10000000 to 0x10004000, because it's the largest continous block of memory. I would like to be able to add a "used" area at the end of size 0x2000000 - 0x10004000 = 0xFFFC000 with size of 2kB. This is invalid memory, so it should seem like already allocated space that is never read from or written to, but I should be able to add a 0x800 size free block after that. And another unavailable from 0x3800 and another free of 0x800.

If I see correctly the .extend method should be .... well extended with a parameter for wether the block should count as free space or as allocated space. It is already an unsafe function, so that's not an issue, but probably would need to add a guarantee that when defining a "used" space, that area will never be read from or written to by the allocator.

Compilation failed with nightly-2021-08-20

rust-toolchain
nightly-2021-08-20
Cargo.toml

[dependencies]
linked_list_allocator = "0.9.1"

src/main.rs

use linked_list_allocator::LockedHeap;

#[global_allocator]
static ALLOCATOR: LockedHeap = LockedHeap::empty();

pub fn init_heap() {
    let heap_start = 0;
    let heap_end = 1024;
    let heap_size = heap_end - heap_start;
    unsafe {
        ALLOCATOR.lock().init(heap_start, heap_size);
    }
}

fn main() {
    println!("Hello, world!");
}

Cargo build

$ cargo build
   Compiling scopeguard v1.1.0
   Compiling lock_api v0.4.7
   Compiling spinning_top v0.2.4
   Compiling linked_list_allocator v0.9.1
error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
   --> /home/test/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.9.1/src/lib.rs:224:20
    |
224 |         LockedHeap(Spinlock::new(Heap::empty()))
    |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0015`.
error: could not compile `linked_list_allocator` due to previous error

I lowered the lock_api in cargo.lock from 0.4.7 to 0.4.6, and the compilation was successful

Spin is no longer actively maintained (RUSTSEC-2019-0031)

Running cargo audit on https://github.com/google/OpenSK reveals that linked_list_allocator depends on spin, which is no longer actively maintained (advisory RUSTSEC-2019-0031).

Crate:  spin
Title:  spin is no longer actively maintained
Date:   2019-11-21
URL:    https://rustsec.org/advisories/RUSTSEC-2019-0031
Dependency tree: 
spin 0.5.2
└── linked_list_allocator 0.6.6
    └── libtock 0.1.0

Full Travis-CI log: https://travis-ci.org/google/OpenSK/builds/646900743.

It seems that spin is an optional dependency and active when the use_spin feature is enabled (which is by default).

The advisory suggests to migrate to https://crates.io/crates/lock_api or https://crates.io/crates/conquer-once (according to the advisory, both should support no_std).

Memory usage optimization

Based on the discussion in #16:

I think the pointer in the Hole structure can be removed and calculated on the fly from (&this as usize) + this.size.

Any reason we are not doing that?

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

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 (theseus-os/Theseus#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.

Allocating for sizes way beyond the heap size seems buggy

So I am using this crate now in https://github.com/rust-embedded/rust-raspberrypi-OS-tutorials/tree/master/19_kernel_heap (thanks for the crate!!).

The heap size provided in the tutorial is 16 MiB. I realized that when I try to allocate for something ridiculously large, e.g. 12 GiB, I don't get an allocation error, but a data abort exactly here: https://github.com/phil-opp/linked-list-allocator/blob/master/src/hole.rs#L271. Maybe some math going wrong?

Can be reproduced by adding an allocation for something this large at the end of main.rs and then run make qemu (needs docker). I am currently a bit short on time, so sorry for not investigating myself.

Make HoleList public or make Heap::extend accept non contiguous areas

Hi, I'm a follower of your work, that is excellent.
I currently develop a Rust OS based on the crates and the blog you wrote, but the user space allocation memory model doesn't follow the classic sbrk-like schema, instead uses a mmap oriented one.
So i gently request you to allow linked_list_allocator accept non contiguous areas in Heap::extend(by: usize) as extensions simply modifying the method to Heap::extend(start_addr: usize, size: usize).
Otherwise you could make public the HoleList module to allow external uses.

best regards Marco Cicognani

Can't see the documentation of this crate on docs.rs

I'm not sure this is a suitable place to notice this, so forgive me if this is not.

As the title says, we can't view the documentation of v0.9.0 because of a build error. (log). We can see the v0.8.11 one instead.

[Feature request] Heap canary

Recently I occurred a heap corruption bug in one of my real life projects:

Kernel panic - aborting: at /home/kazurin/.cargo/registry/src/rsproxy.cn-8f6827c7555bfaf8/linked_list_allocator-0.9.1/src/hole.rs:311: attempt to add with overflow

It took me long before I was able to discover the root cause, due to the complication of kernel debugging and the need to read the source code of various crates. It might be handy to have some simple heap canary mechanism (just like what Valgrind does) built into the allocator in such cases.

Features that I consider useful:

• Ability to detect the corruption of heap control structures (namely the Holes) using some predefined magic bytes in the structure
• Ability to reveal the corrupted structure's address in the panic message (for easier debugging)
• Ability to verify the integrity of the whole heap at any time
• The heap canary feature should be completely optional, in order not to cause preformance impact on production code

If such features are acceptable but not planned, perhaps I could do a PR in the future :)

Can't use the crate for the target riscv32i-unknown-none-elf

I don't know if this is an issue and I would like to apologize for that. (It is my first issue that i wrote. )

What I did was only include the linked_list_allocator in the Cargo.toml .

/* Cargo.toml */

[dependencies]
linked_list_allocator = "0.10.4"

Terminal Output:

error[E0432]: unresolved import `core::sync::atomic::AtomicUsize`
  --> /home/user123/.cargo/registry/src/github.com-1ecc6299db9ec823/lock_api-0.4.9/src/remutex.rs:19:20
     |
19 |     sync::atomic::{AtomicUsize, Ordering},
     |                    ^^^^^^^^^^^ no `AtomicUsize` in `sync::atomic`

The problem is that the Riscv32i does not contain an atomic instruction set (A) and that is why the error occurs.

I do not know if I have forgotten something or if it is a bug.

use_spin feature requires nightly. Is this intentional?

The readme suggests that the use_spin feature does not require nightly, however it enables the nightly feature of spinning_top, which means that it relies on nightly and the const_fn rustc unstable feature. Is this an error in the readme, or in the enabling of the nightly feature on spinning_top?

In recent versions, crate depends on alloc

Since release 0.3.0 of the crate, this library depends on alloc, and requires types from it to fill functions. Because alloc requires an allocator, you can't link it in any crate marked with #![allocator], so it all breaks down.

Fix: Remove dependency on alloc by replacing Layout parameters with size, and align usize parameters, like they were in v0.2.7

Merge padding inside global allocate_first_fit

I found that in function HoleList::allocate_first_fit, it will call the global allocate_first_fit.
The global allocate_first_fit will search and call split_hole to get the allocated memory, also generating front_padding and back_padding to cope with align problem.
However the two padding are merged by deallocate in HoleList::allocate_first_fit which seems less efficient. Since deallocate need to search for the previous holes of two padding, which means it has to go through the linked-list again all over.
In global allocate_first_fit after it call split_hole, it already get the previous hole that can merge the front padding and back padding. I think it will be more efficient to merge padding in global allocate_first_fit.

Please correct me if there are anything wrong.

Unable to build on rust version 1.43.0-nightly

I tried to build following code with dependency on linked-list-allocator version 0.7.0:

use linked_list_allocator::LockedHeap;

However I got this error:

error[E0053]: method `alloc` has an incompatible type for trait
   --> /Users/mac/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.7.0/src/lib.rs:133:5
    |
133 |     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected tuple, found struct `core::ptr::NonNull`
    |
    = note: expected fn pointer `unsafe fn(&mut Heap, core::alloc::Layout) -> core::result::Result<(core::ptr::NonNull<u8>, usize), _>`
               found fn pointer `unsafe fn(&mut Heap, core::alloc::Layout) -> core::result::Result<core::ptr::NonNull<u8>, _>`

My Rust version is rustc 1.43.0-nightly (75cf41afb 2020-03-04).

Release extended memory

Add a way to release extended memory since it might be the case where one allocates a large amount of memory temporarily and then never needs the allocate such large amount of memory and releasing memory is a must in this situation. So, it would be reasonable to have a function such as release_memory which takes in a closure that internally the allocater calls if a hole is available at the end of the heap and the actual memory can be freed.

Other ways?

Another way to accomplish this without changes to the allocator to itself (but will be pain) is to make the caller free the memory itself and allocate a block of memory at that location on a page fault (on the next allocation if required). Like kernel-heap-on-demand-paging and inefficient :^).

no method named `write` found for type `*mut hole::Hole`

error[E0599]: no method named `write` found for type `*mut hole::Hole` in the current scope
  --> src/hole.rs:29:13
   |
29 |         ptr.write(Hole { size: hole_size, next: None, });
   |             ^^^^^

The alloc_ref feature is currently broken

The build fails on the latest nightly: https://github.com/phil-opp/linked-list-allocator/runs/557083367?check_suite_focus=true

The reason is that the API of the AllocRef has changed on the Rust side.

Compilation fails with rustc 1.60.0-nightly (ee5d8d37b 2022-01-17)

$ cargo run --release
   Compiling uart_16550 v0.2.18
   Compiling pic8259 v0.10.2
   Compiling linked_list_allocator v0.9.1
error[E0015]: calls in constant functions are limited to constant functions, tuple structs and tuple variants
   --> C:\Users\robin\.cargo\registry\src\github.com-1ecc6299db9ec823\linked_list_allocator-0.9.1\src\lib.rs:224:20
    |
224 |         LockedHeap(Spinlock::new(Heap::empty()))
    |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0015`.
error: could not compile `linked_list_allocator` due to previous error
warning: build failed, waiting for other jobs to finish...
error: build failed

Miri test failure: Stacked Borrow rules violated

Our scheduled CI jobs discovered a new set of Miri errors on the latest nightlies. The full logs are:

running 26 tests
error: Undefined Behavior: trying to retag from <202439> for SharedReadOnly permission at alloc86155[0x0], but that tag does not exist in the borrow stack for this location
   --> /home/runner/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:385:18
    |
385 |         unsafe { &*self.as_ptr() }
    |                  ^^^^^^^^^^^^^^^
    |                  |
    |                  trying to retag from <202439> for SharedReadOnly permission at alloc86155[0x0], but that tag does not exist in the borrow stack for this location
    |                  this error occurs as part of retag at alloc86155[0x0..0x10]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <202439> was created by a SharedReadWrite retag at offsets [0x0..0x3e8]
   --> src/test.rs:49:35
    |
49  |     let heap = unsafe { Heap::new(data.as_mut_ptr().cast(), data.len()) };
    |                                   ^^^^^^^^^^^^^^^^^
help: <202439> was later invalidated at offsets [0x0..0x400] by a Unique retag
   --> src/test.rs:53:16
    |
53  |       let drop = move || {
    |  ________________^
54  | |         let _ = heap_space;
55  | |     };
    | |_____^
    = note: BACKTRACE:
    = note: inside `core::ptr::NonNull::<hole::Hole>::as_ref::<'_>` at /home/runner/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:385:18
note: inside `hole::Cursor::current` at src/hole.rs:50:18
   --> src/hole.rs:50:18
    |
50  |         unsafe { self.hole.as_ref() }
    |                  ^^^^^^^^^^^^^^^^^^
note: inside `hole::Cursor::split_current` at src/hole.rs:69:29
   --> src/hole.rs:69:29
    |
69  |             let hole_size = self.current().size;
    |                             ^^^^^^^^^^^^^^
note: inside `hole::HoleList::allocate_first_fit` at src/hole.rs:411:19
   --> src/hole.rs:411:19
    |
411 |             match cursor.split_current(aligned_layout) {
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `Heap::allocate_first_fit` at src/lib.rs:196:15
   --> src/lib.rs:196:15
    |
196 |         match self.holes.allocate_first_fit(layout) {
    |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `hole::test::aff` at src/hole.rs:723:17
   --> src/hole.rs:723:17
    |
723 |         let _ = heap.allocate_first_fit(reqd).unwrap();
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at src/hole.rs:720:14
   --> src/hole.rs:720:14
    |
719 |     #[test]
    |     ------- in this procedural macro expansion
720 |     fn aff() {
    |              ^
    = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

cc @jamesmunns

Issues running tests in miri

Hey! I'm building a sort of "liballoc replacement" for my work on MnemOS, and I'm both using linked_list_allocator, and doing some pretty gnarly unsafe stuff on top of it. Because of this, I wanted to get miri testing going to make sure I am not shooting myself in the foot, but it seems pretty upset about linked_list_allocator in general.

Even without the newer strict provenance checks, I'm getting errors like this just constructing the heap in the tests:

$ cargo +nightly miri test
...
test test::oom ... error: Undefined Behavior: not granting access to tag <untagged> because incompatible item is protected: [Unique for <189711> (call 54826)]
    --> /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1342:9
     |
1342 | ...   copy_nonoverlapping(&src as *const T, dst, 1);
     |       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not granting access to tag <untagged> because incompatible item is protected: [Unique for <189711> (call 54826)]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: tag was most recently created at offsets [0x0..0x3e8]
    --> src/lib.rs:126:23
     |
126  |         let address = mem.as_ptr() as usize;
     |                       ^^^^^^^^^^^^
help: tag was later invalidated at offsets [0x6..0x16]
    --> src/hole.rs:50:9
     |
50   | / ...   ptr.write(Hole {
51   | | ...       size: hole_size.saturating_sub(aligned...
52   | | ...       next: None,
53   | | ...   });
     | |________^
help: this tag was also created here at offsets [0x0..0x3e8]
    --> src/lib.rs:125:20
     |
125  |         let size = mem.len();
     |                    ^^^^^^^^^
help: <189707> was protected due to a tag which was created here
    --> src/test.rs:11:33
     |
11   |     let heap = Heap::from_slice(heap_space);
     |                                 ^^^^^^^^^^
help: this protector is live for this call
    --> src/lib.rs:124:5
     |
124  | /     pub fn from_slice(mem: &'static mut [MaybeUn...
125  | |         let size = mem.len();
126  | |         let address = mem.as_ptr() as usize;
127  | |         // SAFETY: The given address and size is...
128  | |         // mutable reference handed to us by the...
129  | |         unsafe { Self::new(address, size) }
130  | |     }
     | |_____^
     = note: inside `core::ptr::write::<hole::Hole>` at /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1342:9
     = note: inside `core::ptr::mut_ptr::<impl *mut hole::Hole>::write` at /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:1406:18
note: inside `hole::HoleList::new` at src/hole.rs:50:9
    --> src/hole.rs:50:9
     |
50   | / ...   ptr.write(Hole {
51   | | ...       size: hole_size.saturating_sub(aligned...
52   | | ...       next: None,
53   | | ...   });
     | |________^
note: inside `Heap::new` at src/lib.rs:115:24
    --> src/lib.rs:115:24
     |
115  | ...les: HoleList::new(heap_bottom, heap_size),
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `Heap::from_slice` at src/lib.rs:129:18
    --> src/lib.rs:129:18
     |
129  |         unsafe { Self::new(address, size) }
     |                  ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `test::new_heap` at src/test.rs:11:16
    --> src/test.rs:11:16
     |
11   |     let heap = Heap::from_slice(heap_space);
     |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `test::oom` at src/test.rs:39:20
    --> src/test.rs:39:20
     |
39   |     let mut heap = new_heap();
     |                    ^^^^^^^^^^
note: inside closure at src/test.rs:38:1
    --> src/test.rs:38:1
     |
37   |   #[test]
     |   ------- in this procedural macro expansion
38   | / fn oom() {
39   | |     let mut heap = new_heap();
40   | |     // let layout = Layout::from_size_align(heap...
41   | |     // let addr = heap.allocate_first_fit(layout...
42   | |     // assert!(addr.is_err());
43   | | }
     | |_^
     = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error; 5 warnings emitted

error: test failed, to rerun pass '--lib'

This seems pretty challenging to deal with: Miri is complaining that the allocator is holding a pointer with provenance to the entire range, and that writing the first Hole in that range is invalidating the tag.

I saw that you and @HeroicKatora had done some work to make miri happy in the past, I'm not sure if this has changed due to certain behaviors becoming defaults (stacked borrows maybe?).

I'd be happy to help getting these passing again if I can!

Version 0.6.6 breaking semver?

The freshly released 0.6.6 version (#20) causes this Travis-CI build to fail: https://travis-ci.org/google/OpenSK/builds/645900468

    Checking linked_list_allocator v0.6.6
error[E0432]: unresolved import `alloc::alloc::AllocRef`
  --> /home/travis/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.6.6/src/lib.rs:14:20
   |
14 | use alloc::alloc::{AllocRef, AllocErr, Layout};
   |                    ^^^^^^^^ no `AllocRef` in `alloc`
error: aborting due to previous error

This may be due to the fact that we pin a specific Rust toolchain - which didn't have the AllocRef symbol yet (indeed, the renaming in rust-lang/rust#68529 and rust-lang/rust#68736 was very brief, not leaving much time to migrate to the new name).

One could argue that given that the allocator API in unstable (#[unstable(feature = "allocator_api", issue = "32838")]) such breakage is expected from Rust's stdlib side.

On the one hand, linked-list-allocator >= 0.6.6 doesn't compile with old versions of Rust nightly. On the other hand, versions of linked-list-allocator < 0.6.5 won't compile anymore on new Rust nightlies due to the new name.

This seems to me like it could qualify as a semver breakage, as version ^0.6.5 can mean either 0.6.5 or 0.6.6 (depending on when one updated their crates), but in all cases (except the few days between rust-lang/rust#68529 and rust-lang/rust#68736 where Alloc and AllocRef both existed) either 0.6.5 or 0.6.6 won't compile (depending on the liballoc in the toolchain).

If instead a new 0.7.0 version is released and 0.6.6 is yanked, dependents of linked-list-allocator can choose between 0.6.x and 0.7.x according to their toolchain.

The `alloc_ref` feature is broken on latest nightly

Seems like the signature of the AllocRef trait was changed again in the Rust standard library. To fix the feature, we need to update our code to the new trait signature.

alloc::allocator reexport of alloc::alloc removed; builds failing on latest nightlies

See rust-lang/rust@26324d0. This is currently causing a build failure:

error[E0432]: unresolved import `alloc::allocator`                                                                             
  --> /home/erin/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.6.2/src/lib.rs:15:12
   |
15 | use alloc::allocator::{Alloc, AllocErr, Layout};
   |            ^^^^^^^^^ Could not find `allocator` in `alloc`

error[E0432]: unresolved import `alloc::allocator`
 --> /home/erin/.cargo/registry/src/github.com-1ecc6299db9ec823/linked_list_allocator-0.6.2/src/hole.rs:1:12
  |
1 | use alloc::allocator::{AllocErr, Layout};
  |            ^^^^^^^^^ Could not find `allocator` in `alloc`

error: aborting due to 2 previous errors

`const_fn` weirdness on v0.9.0

Hi, thank you for sharing all this awesomeness. It's truly amazing.

Since lock_api dropped the const_fn attribute, in v0.4.4 commit Amanieu/parking_lot@aea1350 I'm running into compile trouble using the use_spin_nightly feature. I'm using a custom-built 1.52.0-dev nightly Rust/Cargo and LLVM toolchain with Motorola 68000 family support, which I play around with to program for the Sega Megadrive. It's a blast.

dependency:
linked_list_allocator = { version = "0.9.0", default-features = false, features = ["use_spin_nightly"] }

I get:

error[E0723]: trait bounds other than `Sized` on const fn parameters are unstable
   --> /root/.cargo/registry/src/github.com-1ecc6299db9ec823/lock_api-0.4.4/src/rwlock.rs:348:6
    |
348 | impl<R: RawRwLock, T> RwLock<R, T> {
    |      ^
    |
    = note: see issue #57563 <https://github.com/rust-lang/rust/issues/57563> for more information
    = help: add `#![feature(const_fn)]` to the crate attributes to enable

I'm fairly new to this. I haven't done any systems programming before, and some elevator-music equivalent of Rust programming. Any idea on how to get around this? Thanks in advance for any pointers!

Memory leak

Problem

The heap implementation has a memory leak, so that even using only code that is considered safe, the heap memory can be exhausted so that next allocation requests will fail.

Cause

This happens because, when the back padding of a chunk is not enough to store a hole, it is considered to be part of the allocated chunk, but when that chunk is deallocated, this back padding is not taken into account, and the size of the hole is just set to the size of the aligned layout of the allocation.

Example

The following example provides a function which breaks the heap and wastes all of it's memory. Heap allocations that are performed after a call to break_heap and are of a size that is larger than 16 bytes will fail with an out of memory condition, even though this function properly deallocates every single allocation that it performs before returning.

Note that although this example contains unsafe blocks, it is considered safe, and if another allocator would have been used here, this function would not break the heap, since all allocations are properly deallocated, which is guaranteed by using the Allocation struct, and by wrapping allocations in a Box in the Barrier struct.

If this function is executed for example on the chunk allocator from the simple-chunk-allocator crate, the function loops infinitely because it keeps trying to waste the largest chunk but it doesn't get wasted since that heap implementation doesn't have this memory leak bug.

This function can break the heap even if some parts of it are used, and it will waste all of the currently unused chunks that are larger than 16 bytes.

fn break_heap() {
    /// A safe abstraction over a heap allocation.
    struct Allocation {
        ptr: *mut u8,
        layout: Layout,
    }
    impl Allocation {
        fn new(size: usize) -> Self {
            let layout = Layout::from_size_align(size, 1).unwrap();
            let ptr = unsafe { alloc(layout) };
            if ptr.is_null() {
                panic!("allocation failed, size: {}", size);
            }
            Self { ptr, layout }
        }

        fn try_new(size: usize) -> Option<Self> {
            let layout = Layout::from_size_align(size, 1).unwrap();
            let ptr = unsafe { alloc(layout) };
            if ptr.is_null() {
                return None;
            }
            Some(Self { ptr, layout })
        }
    }
    impl Drop for Allocation {
        fn drop(&mut self) {
            unsafe { dealloc(self.ptr, self.layout) }
        }
    }

    /// The barrier allocates many chunks of memory and must keep track of them.
    /// To do so it uses a linked list, and this struct represents a node in
    /// that linked list.
    struct BarrierLinkedListNode {
        next: Option<Box<BarrierLinkedListNode>>,
    }

    /// A barrier that is used to prevent the wasted chunk from merging with the
    /// top of the heap when deallocated.
    struct Barrier {
        _node: Box<BarrierLinkedListNode>,
    }
    impl Barrier {
        fn new() -> Self {
            // in order to create a barrier we must allocate as many chunks of 16 bytes as
            // possible, to make sure that we hit the right hole.

            fn try_allocate_node() -> Option<Box<BarrierLinkedListNode>> {
                // using the unsafe `alloc` function here so that we can check for allocation
                // failure instead of panicking.
                let ptr = unsafe { alloc(Layout::new::<BarrierLinkedListNode>()) }
                    .cast::<BarrierLinkedListNode>();

                if ptr.is_null() {
                    return None;
                }

                unsafe { ptr.write(BarrierLinkedListNode { next: None }) };

                Some(unsafe { Box::from_raw(ptr) })
            }

            // we expect at least 1 allocation to be successful.
            let mut cur = try_allocate_node().unwrap();

            loop {
                match try_allocate_node() {
                    Some(mut allocated_node) => {
                        allocated_node.next = Some(cur);
                        cur = allocated_node;
                    },
                    None => break,
                }
            }

            Self { _node: cur }
        }
    }

    /// Returns an estimation for the size of the largest chunk in the heap.
    ///
    /// The result is guaranteed to be aligned to 8 bytes.
    fn guess_heap_largest_chunk_size() -> usize {
        // start from the minimum allocation size
        let mut cur_allocation_size = 16;

        loop {
            if Allocation::try_new(cur_allocation_size * 2).is_none() {
                break;
            }
            cur_allocation_size *= 2;
        }

        // we now know that the heap size it between `cur_allocation_size` and
        // `cur_allocation_size * 2` (not including `cur_allocation_size * 2`).
        //
        // we can perform a binary search to find the actual heap size.
        let mut step = cur_allocation_size / 2;
        while step >= 8 {
            if Allocation::try_new(cur_allocation_size + step).is_some() {
                cur_allocation_size += step
            }
            step /= 2;
        }

        cur_allocation_size
    }

    // a loop which runs on each largest block in the heap
    loop {
        // find the size of the current largest chunk in the heap.
        let heap_largest_chunk_size = guess_heap_largest_chunk_size();

        println!("heap_largest_chunk_size: {}", heap_largest_chunk_size);

        // We can only waste chunks of memory that are larger than 16.
        // If the largest chunk is not larger than 16, then we don't have any more
        // chunks to waste.
        if heap_largest_chunk_size <= 16 {
            break;
        }

        // Now we must perform a trick to prevent this chunk form merging with the top
        // of the heap in case it is at the end of the heap.
        //
        // We don't know if it's indeed at the end or not, so we perform the trick
        // anyway.
        //
        // The trick involves splitting our huge chunk into 2 parts: a barrier
        // allocation and another allocation for the rest of the chunk.
        //
        // The barrier must come after the other chunk to prevent that chunk from
        // merging with the top of the heap.
        //
        // The initial allocation done below is the allocation for the rest of the chunk
        // other than the barrier, which will make the allocator create a hole
        // right at the end of the large chunk that we're currently wasting.
        // That hole will then be allocated to make it a barrier.

        // We must first allocate chunk at the end of the heap, so that the
        // `check_merge_top` function doesn't fix the problem. Thus, we leave 16
        // bytes which is the minimum chunk size, which will make sure that a hole
        // is created right after our initial allocation and we can then allocate
        // something into that hole.
        //
        // the purpose of the initial allocation is just to allow us to create that
        // barrier at the end of the heap.
        let initial_allocation_size = heap_largest_chunk_size - 16;

        // The allocation for the barrier.
        // Note that this allocation lives for the entire duration while we waste this
        // chunk, because otherwise the deallocated holes might merge with the
        // top of the heap.
        //
        // It's actually not necessary for it to live for the entire time, but just for
        // the first waste allocation, which will create a region of wasted
        // memory between the wasted chunk and the barrier.
        let _barrier_allocation;

        // the scope is so that the initial allocation is freed once we successfully
        // initialize the barrier, since the only purpose of the initial allocation
        // is to create the barrier.
        {
            let _initial_allocation = Allocation::new(initial_allocation_size);

            // after the initial allocation, make sure that we create a barrier to
            // "unfree" the hole that was created at the end of the heap, which will prevent
            // deallocations from merging with the top of the heap through the
            // `check_merge_top` function.
            _barrier_allocation = Barrier::new();
        }

        let mut cur_size = initial_allocation_size;

        // slowly waste the chunk.
        while cur_size > 16 {
            let smaller_size = cur_size - 8;

            {
                let _allocation = Allocation::new(smaller_size);
            }

            cur_size = smaller_size;
        }
    }
}

const_mut_refs is forcing spinning_top

After the change in #46, const_mut_refs now enables the spinning_top dependency, which I don't think is required. This is causing breakage on alloc-cortex-m because spinning_top uses CAS, which isn't available in thumbv6.