[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 6 Jul 2017 19:10:25 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: Clever code in malloc()
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
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.
