MISRA C Avoid dynamic memory allocation

[ceolin]

Zephyr's kernel is using rb tree defined in rb.[ch]. This algorithm is using alloca() function to allocate memory using stack. If the allocation fails the behaviour is undefined.

part of: #9552

[ceolin]

@andyross This is not a trivial piece of code, can we check how much work is required to fix it ?

[andyross]

So... alloca() is allocating memory "dynamically", but on the stack. It won't fail in the sense of malloc() where someone else is using the memory. The only failure case is a stack overflow, which is something that is always possible. What exactly does MISRA say? Note that there are a few other spots in our codebase where we're doing equivalent allocations via variable-sized arrays (e.g. int foo[some_runtime_value];) which are likely to need attention too.

There's no good workaround. The "fix" would be to always allocate a maximally sized block (which isn't huge -- probably hundreds of bytes) I guess. Maybe we could put this under a CONFIG_MISRA_PEDANTRY flag or something so that normal apps can use the appropriate tool.

But really I'd hope that stack allocation would be possible in conforming MISRA code. I mean... fundamentally it's no different than recursion in terms of expression and safety.

[ceolin]

yep, it's allocating on stack but still dynamic. MISRA dooms dynamic allocation and everything should be pre-allocated. Btw, variable length arrays and alloca are different, they have different scope, memory allocated by alloca is release only when the function exits while the former is when the block exits.
VLAs are also part of C99 standard while alloca is not part of the standard. As fair as I understood there is no violation using VLAs. I'll double check it though.

[ceolin]

sorry, VLAs are also not allowed. Dammit, we may have to define one pattern for these cases and maybe create a deviation. Anyway, between alloca() and VLAs I stand to VLAs, at least is covered by standard and we have less chance to find problems with different compilers.

[ceolin]

Dir 4.12 and rule 21.3

[andyross]

FWIW: everywhere I'm aware of this is being done, the memory usage isn't unbounded (in fact it's generally log-sized in whatever the relevant data structure is). It's possible to decide on a tractable maximum size upfront and simply use that, obviously at the cost of significantly larger stacks for the common case.

[mped-oticon]

But really I'd hope that stack allocation would be possible in conforming MISRA code. I mean... fundamentally it's no different than recursion in terms of expression and safety.

MISRA-C prohibits recursion, but you could probably have guessed this already.

Personal opinion: It seems silly to rely on dynamic memory to implement dynamic memory.
That makes me in favor of avoiding VLA+alloca, placing that need exclusively on malloc instead.

[mped-oticon]

FWIW, these are the places VLAs are currently used:

ext/lib/crypto/tinycrypt/source/hmac.c
	int tc_hmac_set_key(TCHmacState_t ctx, const uint8_t *key,
lib/mempool/mempool.c
	int _sys_mem_pool_block_alloc(struct sys_mem_pool_base *p, size_t size,
	void _sys_mem_pool_block_free(struct sys_mem_pool_base *p, u32_t level,
lib/rbtree/rb.c
	void rb_insert(struct rbtree *tree, struct rbnode *node)
	void rb_remove(struct rbtree *tree, struct rbnode *node)
subsys/fs/fcb/fcb_append.c
	int fcb_append_finish(struct fcb *fcb, struct fcb_entry *loc)

[andyross]

An alloca()/VLA is hundreds of cycles faster than malloc() on most architectures (often more on some workloads if you factor in long term costs from fragmentation). In general it's implementable via a single subtraction from the stack pointer. It's absolutely the right way to solve problems like this where you have a need for small-ish amounts of non-constant-size memory that will affirmatively live only for the duration of a function call. That's why it's in the language, after all.

That said: the mempool and rbtree uses are mine, and those can be bounded well enough such that we can use the same code with a tolerable cost paid in stack sizing. I strongly suspect the same is true of tinycrypt (where it's likely to be a buffer sized according to algorithm and thus has some reasonable maximum). No idea about the flash thing.

[ceolin]

@andyross will this be done for 1.14 or should I change the milestone to future ?

[andyross]

In some form, sure. Worst case we can add maximally-sized iteration arrays somewhere (on the stack, or globally with appropriate locking, etc...).

(Edit: for clarity, that's talking about usage in the kernel. I don't think the tinycrypt and subsys/fs directories are in the line of fire for MISRAfiation in 1.14, right?)

[andyross]

Merged the VLA patch for the kernel, which I think is the scope here. There are a few spots in the I2C and SPI drivers that can be hit (as failures -- we error on VLA usage now) by trying to build the full test suite with CONFIG_MISRA_SANE. We can address those in specific bugs as needed.