On Mon, Jul 30, 2018 at 11:09:05AM -0400, Christopher Friedt wrote:
> I wrote it originally for using on the kernel-side of an rtos, but it could
> easily be extended to make a syscall when a process runs out of ram.
>
> Obviously, a shortcoming is that the memory blocks must be PoT and there is
> the potential for fragmentation. Otherwise though, the meta-information is
> intrinsic within the pointer, which obliviates the need for external
> storage.
>
That does sound interesting, but I don't really follow. The meta-info
which we need to save is the length of the object returned. How can you
encode that in the pointer without any external storage? Using internal
storage? Yeah, that is where we are right now, and that means there's
only one buffer overflow between us and oblivion at any given time.
Or do you essentially have a large block of memory, with one area for
the 16-byte objects, one for the 32-byte ones, &c. But then what do you
do if your given area runs out and the application still wants more?
The 'bins' do overlap (e.g. a 64 byte chunk can also be used as 2 32-byte chunks or "buddies"), but their size (when using a bitmap for metadata) is encoded by the position of the bit in the map. This also encodes if a parent (or child) of a specific memory region is already in use or free.
My original implementation was for an rtos with a compile-time-fixed memory size. In user space (since doubling ram usage is obviously bad) it would be best to use some container (e.g. an interval tree) to contain buddy-malloc nodes and general slabs of mmap. Current usage, a configurable fragmentation threshold, and the system pagesize, would determine if an allocation would use an existing buddy-malloc node, a new buddy-malloc node (PoT # of pages) or a sequence of pages. Pages would, of course, be allocated with mmap.
I've personally not implemented malloc debugging for a buddy allocator though, since bits are precious enough, and there is no fundamental requirement for it, although technically, it would mean adding some padding with a computable bit pattern. I suppose if checking is enabled, it can be run before free(3) returns or before realloc(3) does anything. A global check on every function call would be more thorough, but obviously more expensive.