From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 15680 invoked from network); 2 Aug 2020 16:22:45 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 2 Aug 2020 16:22:45 -0000 Received: (qmail 3640 invoked by uid 550); 2 Aug 2020 16:22:39 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 3622 invoked from network); 2 Aug 2020 16:22:38 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=0KC89nKLvBig+Sd9Ir0L5XQTEQ/DnybLCrZ8WIKK39c=; b=ahKGRzkw6LwcFh16FWYymXBMR/o2IuH7I2WZeNdwpGIh2keaib3U+zjZYvyVhCYJlT Tvyhh39P+WMn27/ByAVd1fxRcsUS1qvp4pbf5Kt3+M+o1diqcRGx2mAuS03UNXwvty5H mP7qjz7cfVWp9UGb825qpxJtlSRR96CWYL9u4srHv4wRZqvzhho6FXJRD8tlN49B0lt8 yw/q4lHfEEujE0LHoBQva3ZqeB7GinXLFuUsi1dQcQhBQ02nAvmEAfDBvfvXlD3/5Ff7 xOQe9mzJsq1Lux4KpLMgqZBWN7LbUsrhwnAvNSv9msK2GpK2hrb/RkkXpmgP+pYCplcE /I6g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=0KC89nKLvBig+Sd9Ir0L5XQTEQ/DnybLCrZ8WIKK39c=; b=PkrVVkezsoev+Y2MHODAnInZKCJmnkzReu4qnS1Q0ypBC5QAtTE5Cxceu31pDY89gK CX4Pj41/DsE+xsRWb7TBQsnUawvp7OC7Nz34RaJLP8OEdxEbYp89tUdO55NahnVW2CoN v/y01jAnO2ETn+s0bbkTy+xSPT4XcM1aklvd0BudVmipkNI1eW/Euuex7naoQbpiLUNy gJ5gUWqCRUtZCmxt8rz/qj878w5Ee4GGRsHz3+BwDz/EorIin/kRk5f65nXsct3OJf+r 6dylJ5LrSl9VE/YzGoM/cQEsPA9Yz3noBXtJV+ZC4ikB+y5YCWIMJSZ1xbDcu4Pp9zbM MkdQ== X-Gm-Message-State: AOAM530W8pC/XnAxY6BdKmK0gsozh95O/8vcxoUQ0ur8AdetmJevKSly HdVhyCL5QguUUHQiLG3sEoPRgNvyuixSm34rMXjzrvc82zY= X-Google-Smtp-Source: ABdhPJzKehcNMNAc+s9zNn58TEQJk71/TSW1stz70F+oM8ShETa9Rwxr50FGlkmU9u0D/YnIvN0VthaiscrRr2pNrmU= X-Received: by 2002:a92:ce8b:: with SMTP id r11mr13640277ilo.86.1596385346212; Sun, 02 Aug 2020 09:22:26 -0700 (PDT) MIME-Version: 1.0 References: <20200731172216.GB2076@voyager> <20200731192339.GV6949@brightrain.aerifal.cx> In-Reply-To: <20200731192339.GV6949@brightrain.aerifal.cx> From: Zhao Zhengyu Date: Mon, 3 Aug 2020 00:22:14 +0800 Message-ID: To: musl@lists.openwall.com Content-Type: multipart/alternative; boundary="0000000000007c5e0905abe76d3a" Subject: Re: [musl] When to reclaim pages in __bin_chunk? --0000000000007c5e0905abe76d3a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I read the code of mallocng carefully and found some ideas similar to my current work: For malloc requirements of the =E2=80=9Csmall size=E2=80=9D, = I split one page into the specified size, and manage them as a group. When free, I give them back to heap together. But at the point of reclaiming physical pages to kernel, I can't get enough inspiration from mallocng. Anyway, I understand the question I asked. Thanks! On Sat, Aug 1, 2020 at 3:24 AM Rich Felker wrote: > On Fri, Jul 31, 2020 at 07:22:16PM +0200, Markus Wichmann wrote: > > On Fri, Jul 31, 2020 at 08:17:02AM +0800, Zhao Zhengyu wrote: > > > Hello, > > > > > > When chunks are merged, we use "(curr_size + pre_size) ^ pre_size > > > > pre_size" to decide whether to reclaim. I think this may be something > > > related to performance, but I can=E2=80=99t prove it. I want to know = the > > > reason. > > > > > > Thank you! > > > > > > Zhengyu > > > > I asked that same question a while ago. For one, this was in the old > > malloc code, which is now usually no longer used. For two, this tries t= o > > figure out if adding current size to previous size rolls over into a ne= w > > power of two. Usually, curr_size will be small and pre_size will be > > large. Therefore, adding the two will not change much about the high > > bits of pre_size, so due to the XOR operator, those bits will cancel ou= t > > and the result will be smaller than pre_size. However, if the sum does > > roll over, then the sum has one bit set that isn't in pre_size and is > > larger than all the ones in pre_size. So the XOR can't cancel that bit, > > and the result of the XOR is greater than pre_size. > > > > Fundamentally, it is an optimized version of (a_clz(curr_size + > > pre_size) < a_clz(pre_size)). > > Yes, it's a heuristic at least approximately equivalent to "crossed > the next power of two size boundary" to limit the frequency of madvise > syscalls when a large free zone keeps getting expanded by adjacent > tiny frees. However it does not work very well in practice, and > doesn't even mitigate the possibility of continuous syscall load when > a repeated malloc/free cycle occurs right at a power-of-two boundary. > > mallocng handles this kind of thing much better by grouping same-sized > allocations and returning them as a group when all are freed, only > holding back from doing so if it's observed allocations of this size > "bouncing" (repeatedly creating and destroying the same group). > > Rich > --0000000000007c5e0905abe76d3a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I read the code of mallocng carefully and found = some ideas similar to my current work: For malloc requirements of the =E2= =80=9Csmall size=E2=80=9D, I split one page into the specified size, and ma= nage them as a group.=C2=A0 When free, I give them back to=C2=A0 heap toget= her. But at the point of reclaiming physical pages to kernel, I can't g= et enough inspiration from mallocng.=C2=A0
Anyway, I = understand the question I asked. Thanks!
<= /div>
O= n Sat, Aug 1, 2020 at 3:24 AM Rich Felker <dalias@libc.org> wrote:
On Fri, Jul 31, 2020 at 07:22:16PM += 0200, Markus Wichmann wrote:
> On Fri, Jul 31, 2020 at 08:17:02AM +0800, Zhao Zhengyu wrote:
> > Hello,
> >
> > When chunks are merged, we use "(curr_size + pre_size) ^ pre= _size >
> > pre_size" to decide whether to reclaim. I think this may be = something
> > related to performance, but I can=E2=80=99t prove it. I want to k= now the
> > reason.
> >
> > Thank you!
> >
> > Zhengyu
>
> I asked that same question a while ago. For one, this was in the old > malloc code, which is now usually no longer used. For two, this tries = to
> figure out if adding current size to previous size rolls over into a n= ew
> power of two. Usually, curr_size will be small and pre_size will be > large. Therefore, adding the two will not change much about the high > bits of pre_size, so due to the XOR operator, those bits will cancel o= ut
> and the result will be smaller than pre_size. However, if the sum does=
> roll over, then the sum has one bit set that isn't in pre_size and= is
> larger than all the ones in pre_size. So the XOR can't cancel that= bit,
> and the result of the XOR is greater than pre_size.
>
> Fundamentally, it is an optimized version of (a_clz(curr_size +
> pre_size) < a_clz(pre_size)).

Yes, it's a heuristic at least approximately equivalent to "crosse= d
the next power of two size boundary" to limit the frequency of madvise=
syscalls when a large free zone keeps getting expanded by adjacent
tiny frees. However it does not work very well in practice, and
doesn't even mitigate the possibility of continuous syscall load when a repeated malloc/free cycle occurs right at a power-of-two boundary.

mallocng handles this kind of thing much better by grouping same-sized
allocations and returning them as a group when all are freed, only
holding back from doing so if it's observed allocations of this size "bouncing" (repeatedly creating and destroying the same group).
Rich
--0000000000007c5e0905abe76d3a--