Clever code in malloc()

Clever code in malloc()

[Markus Wichmann]

Hello,

since it was brought up recently, I do have a question about some code
in malloc(). Namely this line:


			if (new_size+size > RECLAIM && (new_size+size^size) > size)
				reclaim = 1;

What is that doing? I just do not get it at all. For one, I have never
seen an expression of the form a+b^b. I don't know what that is supposed
to do. I tried evaluating it for a couple of inputs but could find no
patterns. And what's it supposed to do, anyway? At that point, new_size
is the size of the chunk we originally wanted to free, and size is the
size of the chunk we are currently devouring. Other already devoured
chunks are not taken into account (that would be in final_size).

The only thing this decision will change is whether or not the central
part of the chunk will be sent to madvise(), to tell the kernel that we
won't need the memory anytime soon. Which seems to me we could do
whenever the chunk we free is large enough in the end. Or is there some
reason not to do this in all cases?

So, could someone clarify this? And maybe add an explanatory comment?

Ciao,
Markus

Re: Clever code in malloc()

[Rich Felker]

On Thu, Jul 06, 2017 at 09:14:23PM +0200, Markus Wichmann wrote:
> Hello,
> 
> since it was brought up recently, I do have a question about some code
> in malloc(). Namely this line:
> 
> 
> 			if (new_size+size > RECLAIM && (new_size+size^size) > size)
> 				reclaim = 1;
> 
> What is that doing? I just do not get it at all. For one, I have never
> seen an expression of the form a+b^b. I don't know what that is supposed
> to do. I tried evaluating it for a couple of inputs but could find no
> patterns. And what's it supposed to do, anyway? At that point, new_size
> is the size of the chunk we originally wanted to free, and size is the
> size of the chunk we are currently devouring. Other already devoured
> chunks are not taken into account (that would be in final_size).
> 
> The only thing this decision will change is whether or not the central
> part of the chunk will be sent to madvise(), to tell the kernel that we
> won't need the memory anytime soon. Which seems to me we could do
> whenever the chunk we free is large enough in the end. Or is there some
> reason not to do this in all cases?
> 
> So, could someone clarify this? And maybe add an explanatory comment?

The interesting case is when size (the size of an existing free chunk)
is large and a relatively small new chunk (new_size) is being merged
into it. This is going to happen A LOT, and you don't want to make a
syscall each time or free will be unusably slow. What the inequality
expression above does is check whether the increase is crossing a
power-of-two boundary, resulting in a sort of exponential backoff.

To see how it's working, consider the bits of the sum new_size+size.
There will be a highest bit position at which the sum differs from
size, and the xor operation will then clear all bits above that point
(and muddle up everything below. The result can be greater than size
if and only if the sum introduced at least one new bit place above the
highest bit set in size. Otherwise, the xor cleared at least one
leading bit of size without introducing a new higher one, resulting in
a smaller value.

Rich

Re: Clever code in malloc()

[Markus Wichmann]

On Thu, Jul 06, 2017 at 07:10:25PM -0400, Rich Felker wrote:
> The interesting case is when size (the size of an existing free chunk)
> is large and a relatively small new chunk (new_size) is being merged
> into it. This is going to happen A LOT, and you don't want to make a
> syscall each time or free will be unusably slow. What the inequality
> expression above does is check whether the increase is crossing a
> power-of-two boundary, resulting in a sort of exponential backoff.
> 
> To see how it's working, consider the bits of the sum new_size+size.
> There will be a highest bit position at which the sum differs from
> size, and the xor operation will then clear all bits above that point
> (and muddle up everything below. The result can be greater than size
> if and only if the sum introduced at least one new bit place above the
> highest bit set in size. Otherwise, the xor cleared at least one
> leading bit of size without introducing a new higher one, resulting in
> a smaller value.
> 

Thank you for the explanation. But does that not mean that an
application could trigger the madvise() at every free() call if the only
available chunk just exceeds a power of two in size, and the application
keeps allocating and then freeing enough to put the chunk under that
size?

Let's take a statically linked application on a thirty-two bit system
(statically linked, so the dynamic memory reclamation doesn't get in the
way of my example, and thirty-two bits because the header size is
machine word dependent, and I need to choose something). Let's further
assume that brk() works.

The application allocates twenty bytes. adjust_size() will increase this
size by two machine words, then round up to the next four-word boundary.
So this comes out at thirty-two bytes.

Since nothing is allocated so far, a heap expansion is triggered. A page
is allocated. The initial chunk in that page will be four thousand
eighty-eight bytes to make room for the footer. The requested thirty-two
byte chunk will be split off, leaving the first heap page with a
thirty-two byte chunk allocated and a four thousand fifty-six byte chunk
freed.

The application then requests four thousand and fourty bytes. After
adjustment this comes out at four thousand and fifty-six, so the last
free chunk is allocated.

The application the requests another ten bytes (so thirty-two after
adjustment) and then allocates the rest of that second page, and will
never free it. Then it frees the four thousand and fifty-six byte chunk
and the second thirty-two byte chunk. Since adjacent chunks are
coalesced, we now have a free chunk of four thousand and eighty-eight
bytes in size. If the application now frees its initial thirty-two byte
chunk, the chunk size puts the free chunk size over the edge of the four
thousand ninety-six boundary, so the expression triggers.

If the application now continues to allocate and free twenty bytes, the
expression will trigger at every free().

Well, OK, it won't, but only because I ignored the minimum size
requirement of 160k.

The example is admittedly contrived, but many more are thinkable.

> Rich

Ciao,
Markus