[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAF4BF-TEAY7OVKsqW_Bn5pabB-2nmqh5--CW=0iMW7oHfcGfTA@mail.gmail.com>
Date: Tue, 31 Jul 2018 10:49:53 -0400
From: Christopher Friedt <chrisfriedt@...il.com>
To: musl@...ts.openwall.com
Subject: Re: malloc implementation survey: omalloc
On Tue, Jul 31, 2018, 3:49 AM Markus Wichmann, <nullplan@....net> wrote:
> 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?
https://en.wikipedia.org/wiki/Buddy_memory_allocation
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.
Content of type "text/html" skipped
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
