Implementing a memory allocator seems to require system calls. What happens when there's no OS? For example on an MCU like Arduino, is the memory allocator packaged along with the program data? If so and in the case of an Arduino, is the code for it available anywhere? I would be curious to see how this is implemented on an embedded system.
In every allocator there has to be a way to get “the memory” that is available for you to hand out. When a normal OS is present, system calls are used to get this in the form of pages. On embedded environments you don’t need to do this because “the memory” is just something like “addresses from 0x2000000 to 0x8000000” and you don’t have to ask for it, it’s just there for you to use.
You could fairly easily implement a bitmapped memory allocator which hands out chunks of reserved memory. I think you could build a more complex allocator on top of that if needed. For a lot of embedded applications, you really want to avoid dynamic memory allocation though. Use mempools if you need dynamic memory, which will at least limit fragmentation.
Second this. It’s really easy to fragment memory, and for long running embedded systems it’s not uncommon for free() to be a nop. I had to implement malloc just last week to access psram, and after doing a little research decided all I needed was an offset and some byte alignment. Since I never needed to deallocate the memory, it was very simple code.
You generally don’t have dynamic memory allocation on such a system. All memory will either be statically allocated globals, or on the stack. Some systems even require stack allocation to be statically determined, which means no recursion.
For Arduino specifically, it certainly does have an allocator and heap by default, even on MCUs with less than 1KB RAM. However, there's no separation, so the stack and heap grow towards each other. If the heap is never used, it always stays at a size of 0. For code side, just not using malloc or anything that uses it will cause it not to be linked.
