Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAF4BF-SWa80WdO7y_BNuze6wS-xfthTM7YG7EkW-BgPT09Xh+Q@mail.gmail.com>
Date: Mon, 30 Jul 2018 15:14:14 -0400
From: Christopher Friedt <chrisfriedt@...il.com>
To: musl@...ts.openwall.com
Subject: Re: malloc implementation survey: omalloc

On Mon, Jul 30, 2018, 11:09 AM Christopher Friedt, <chrisfriedt@...il.com>
wrote:

> otential for fragmentation. Otherwise though, the meta-information is
> intrinsic within the pointer, which obliviates the need for external
> storage.
>

I should clarify.

The meta-info in my buddy allocator is only intrinsic if the size of ram,
and offset are constant. Additionally, there is a bitmap of constant size
in .data[1].

Of course, in userspace, there would need to be 1 void*, 1 size_t, and a
bitmap per PoT chunk of memory to manage.

For a 4096-byte page, on a 32-bit system, that would be 4 + 4 + 256 = 304
bytes of overhead.


C

[1]
The size of the bitmap (in bits) is given directly by the geometric series:

F(n) = sum(k, n-1) r^k = (1-r^n)/(1-r)

r is 2.

If 2^U is the memory size, and 2^L is the smallest granularity of
allocation, then n = U - L + 1, and the number of bits in the bitmap is F(
n ).

E.g. 64 bytes of memory, min 8-byte allocation, then F( 4 ) = 15 bits (2
bytes) are needed for the bitmap.

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.