Proposed fix to enforce byte alignment for static_array_backend feature

[nand-nor]

Problem statement

The wee_alloc implementation of the static_array_backend feature erroneously causes an out-of-memory error. The context where the problem arises is in compilation for a bare-metal embedded system (OS independent, target is something like armv7-unknown-linux-gnueabihf), using the static_array_backend feature and assigning wee_alloc as the global allocator.

The root cause of the resulting error is the implementation of imp_static_array::alloc_pages(). The function creates a pointer to a slice of the SCRATCH_HEAP of the requested size, which is used to create the FreeCell objects that compose the free list. The function does not enforce that the slice pointer maintain any byte boundary alignment, resulting in unaligned FreeCell objects. This ultimately creates an edge case error where allocation fails despite adequate memory left in the SCRATCH_HEAP. The error occurs regardless of the configured static backend array size exported at compile time. Additionally, the failure arises regardless of size policy (e.g. whether or not the size_classes feature is enabled).

Detailed description of the control flow in which the problem arises

The problem is immediately detectable by enabling the extra_assertions feature. With this feature enabled, the first call to allocate memory from the free list results in an alignment assertion failure, because as described above, the FreeCell objects created from the SCRATCH_HEAP object do not have the proper alignment. However, when extra_assertions feature is not enabled, the edge case in the example system occurs when the first 256 Kb of the free list are exhausted a.k.a. a full walk of the initial free list results in alloc_with_refill() executing the code branch to create and insert a new FreeCell.

Upon an allocation request, the allocator attempts to allocate from the SCRATCH_HEAP. This is done via call to the GlobalAlloc trait’s implementation of alloc(), which calls alloc_impl(), which then calls alloc_with_refill() within a function closure passed to self.with_free_list_and_policy_for_size. The alloc_with_refill function first calls alloc_first_fit() which walks the free list to find a FreeCell of adequate size. After the 256 Kb exhaustion point, alloc_first_fit fails to find a FreeCell of adequate size. At this point, the branch for creating and inserting a new FreeCell is executed via calls to new_cell_for_free_list() and insert_into_free_list(). Control flow then returns to alloc_with_refill, which calls alloc_first_fit again, which in turn calls try_alloc() on the newly inserted FreeCell object, which is the point of failure. The checks in try_alloc() assert that the newly inserted FreeCell is large enough to hold the requested allocation size, but that it is not big enough to be split in two. This leads to the final check in try_alloc(), which determines if the FreeCell is appropriately aligned, which, because of how alloc_pages() is implemented for the impl_static_array mod, results in a failure to allocate.

Steps to reproduce problem

1. Use the static array backend feature, compiled for a no_std target (e.g. armv7-unknown-linux-gnueabihf) and use the default backend array bytes size
2. Allocate via alloc::Vec::Vec() an empty vector of u32s, and then push 65 data to it.
3. wee_alloc will fail to allocate more heap memory at the attempt to push the 65th u32 to the vector, triggering an oom() error (if the system has one defined) via the method described above

Proposed problem fix

To address this error, the imp_static_array::alloc_pages() function should enforce alignment requirements such that pointers to slices of the SCRATCH_HEAP are always aligned to the needed byte boundary. The resulting FreeCell objects will therefore always meet alignment checks, whether or not the extra_assertions feature is enabled.

[nand-nor]

Edit: fixing the imp_windows.rs alloc_pages() function call that broke CI

[fitzgen]

Thanks, I'll take a look at this within the next couple days.

[fitzgen]

FYI: I've split out just the alignment of the scratch heap into #87

[nand-nor]

FYI: I've split out just the alignment of the scratch heap into #87

Should I close this PR then? Based on the above discussion / testing /and #87 the problem seems solved

[fitzgen]

Based on the above discussion / testing /and #87 the problem seems solved

Great! That was what I was hoping would happen, but I didn't want to close this out until you confirmed that :)

Should I close this PR then?

Yep, I think we can close this PR. If you run into any thing else, please file an issue!