Really this crate should have set up a proper CI. Currently I'm running all the tests manually before opening a pull request, but this is error prone, as a test simply could be forgotten. Continuous integration is the tool that solves it. Personally I wouldn't really trust a crate in such a sensitive environment without a proper CI. At least the green checkmarks after the commits should be visible.

The necessary checks are:

Due to my recent experimentation with CircleCI I suggest using this as the provider. As the repository is Open Source, there are no limitations.

When looking at the published source code of emballoc 0.1.2 one can see the .circleci-folder. This should be excluded, since the user does not benefit by providing that files. Excluding them saves bandwidth and storage space.

This can be fixed with the following entry in Cargo.toml:

# in the `[package]`-section
exclude = ["/.circleci"]

Publishing version 0.1.0 yields the following output:

$ cargo publish
    Updating crates.io index
   Packaging emballoc v0.1.0 (/home/jfrimmel/git/emballoc)
   Verifying emballoc v0.1.0 (/home/jfrimmel/git/emballoc)
   Compiling spin v0.9.4
   Compiling emballoc v0.1.0 (/home/jfrimmel/git/emballoc/target/package/emballoc-0.1.0)
    Finished dev [unoptimized + debuginfo] target(s) in 2.04s
   Uploading emballoc v0.1.0 (/home/jfrimmel/git/emballoc)
warning: the following are not valid category slugs and were ignored: allocator. Please see https://crates.io/category_slugs for the list of all category slugs.

The last warning should be fixed.

Part of #8.

See the following picture:

The documentation link is missing. This is bad, since I and presumably many others use that link often, so if it is missing, one might think, there is no proper documentation available.

Despite the cargo-documentation saying, that this link is auto-generated if missing, it obviously does not happen. Therefore the fix would be to add the following tag to the [package]-section of the 'Cargo.toml:

documentation = "https://docs.rs/emballoc"

When using c292526, the following integration test reliably deadlocks on my machine:

#![no_std]

#[global_allocator]
static ALLOCATOR: emballoc::Allocator<4096> = emballoc::Allocator::new();

extern crate alloc;

#[test]
fn vec() {
    let mut v = alloc::vec![1, 2, 3];
    v.push(4);

    assert_eq!((1..=4).collect::<alloc::vec::Vec<_>>(), v);
}

The CPU usage is permanently 100% on one core, so I think, that the allocator deadlocked (together with other parts of the program).

Machine details

$ uname -a
Linux infinitybook 5.19.2-arch1-1 #1 SMP PREEMPT_DYNAMIC Wed, 17 Aug 2022 13:48:51 +0000 x86_64 GNU/Linux
$ rustc --version --verbose
rustc 1.63.0 (4b91a6ea7 2022-08-08)
binary: rustc
commit-hash: 4b91a6ea7258a947e59c6522cd5898e7c0a6a88f
commit-date: 2022-08-08
host: x86_64-unknown-linux-gnu
release: 1.63.0
LLVM version: 14.0.5

The latest CI run shows, that there are two non-covered lines/regions in entry.rs. From looking at the tests, I think this is due to those two asserts not tested for their failing cases:

While looking at this part of the code I though, that it might be beneficial to also assert, that the size is a multiple of 4, since this would uncover bugs, where there is memory "lost" due to to short lengths.

 pub const fn free(size: usize) -> Self {
     assert!(size <= 0x7FFF_FFFF);
+    assert!(size % 4 == 0);
     #[allow(clippy::cast_possible_truncation)] // asserted above
     Self((size << 1) as _)
 }

The algorithm description of emballoc 0.1.1 mentions, that the concatenation of free blocks only happens with the following block and not the previous one (cf. step 12). I propose a simple solution, that will prevent such scenarios without the need for the mentioned linear scan.

The key idea is to write the Entry not only to the start of a block (as it is currently done as a header), but also into the block itself. If the block is written to the last four bytes of the memory, the length of the block is known. This in turn would allow to patch the header of that block with the length of the current block to be freed (and the following free block if there is such a block).
It also works with "empty" blocks: from the view of the following block, the previous 4 bytes are a valid header and one needs to jump 0 bytes to the left to access the "real" header (which is the same). This keeps the logic simple and straightforward.
There is no alignment issue, since an allocated block is always rounded up to a multiple of 4, so the entry can safely be written or read.

Thanks a lot for the very well documented crate!

I've been testing emballoc a bit for an embedded project as global allocator. I set it up like suggested in the documentation, using:

#[global_allocator]
static ALLOCATOR: emballoc::Allocator<4096> = emballoc::Allocator::new();

Testing with different heap sizes I noticed that having a large heap also results in large binary sizes. Because of the non-zero initialization in Buffer::new(), the entire heap ends up in the .data segment with 4 initialized bytes and the rest of it zeroed.

This means that the entire heap must be unnecessarily stored and loaded from the flash (or similar). Unfortunately, the MaybeUninit::uninit() in Buffer::new() does not seem to help for the static case because there is no way to represent such a partial initialization in the linker/final binary.

Is this something you have considered? Perhaps there is an easy solution for this that I'm missing.

I could think of one of the following approaches to avoid this:

• Initialize to zero (-> .bss): Perhaps it would be possible to initialize the first entry to zero and detect that case on the first allocation. That way the heap would end up in the .bss segment which is typically not stored as part of the binary but initialized at runtime. It's still somewhat unnecessarily zeroed completely before use but at least it would not consume space in the flash.

• Provide a way to place the heap fully uninitialized in a custom linker section: To avoid the unnecessary pre-initialization of the heap entirely I would expect that it's necessary to place the heap in a custom linker section that is not stored in the flash (like .data) but also not initialized at runtime (like .bss). In that case it would be fully uninitialized though, which cannot be properly distinguished from an initialized state later at runtime. I don't see a way how one would make this approach work without some unsafe call at the very beginning of the main() function, like required for linked-list-allocator for example.

The documentation of this crate should be improved in the following ways:

• mention, that the allocator is mutli-thread-safe
• mention, that allocation in interrupts might cause deadlocks and thus should be avoided
• #10
• mention in the README.md, that this crate is not suitable for usages with MMU
• add license file
• mention, that the stable compiler can be used (compared to some other popular embedded allocators, no nightly compiler is required)
• specify MSRV (is currently 1.62 both in the Cargo.toml and in the CI)
• mention, that the crate has only a single dependency on spin
• display badges
  • crates.io
  • docs.rs
  • CircleCI
• (maybe) provide an example with cortex-m-rt
• (maybe) provide an example with MPU