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=-2.5 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL, SUBJ_OBFU_PUNCT_FEW autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 8211 invoked from network); 7 Jun 2020 02:13:47 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 7 Jun 2020 02:13:47 -0000 Received: (qmail 22279 invoked by uid 550); 7 Jun 2020 02:13: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 22261 invoked from network); 7 Jun 2020 02:13:38 -0000 Date: Sat, 6 Jun 2020 22:13:26 -0400 From: Rich Felker To: musl@lists.openwall.com Message-ID: <20200607021325.GB1079@brightrain.aerifal.cx> References: <20200512220801.GS21576@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200512220801.GS21576@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] Options for mallocng+ldso reclaim_gaps On Tue, May 12, 2020 at 06:08:02PM -0400, Rich Felker wrote: > I have an out-of-tree mockup of the ldso reclaim_gaps equivalent for > mallocng. Right now the way it works is by repeatedly placing a > single-slot group of each power-of-two-sized class (in which nested > groups can be allocated) that fits, in order of decreasing powers. So > a 2600 byte gap would get filled with > > - 2048 (16 header + 1x2032) > - 512 (16 header + 1x496) > - (remainder 40 bytes too small to be useful) > > This yields a total of 5x496 for groups of small allocations, and even > some larger things like 2x240 that might be useful for struct dso. But > it's only one option. > > The other option is treating each donation as a blank slate for bump > allocation of permanent groups of any size that fit. For example the > above could fit: > > - 1x1632, 1x676, 1x240 > - 1x1344, 1x672, 1x496[, 1x64] > - 1x1008, 1x1344, 1x240 > - etc. > > Desptie this seeming attractive, the permanence of the division (it > really doesn't make sense to make any complex dlmalloc reinvention for > merging these back for reuse in different divisions) means it's very > possible that small programs that benefit the most from reclaim_gaps > might never get to use the reclaimed memory again, if they don't need > the same size class again. On the other hand, the largest-fit > power-of-two mockup I have now gives slots that can hold almost any > nested group of smaller size. > > Thoughts on any of this? Anything I might be missing in pros or cons > or other reasonable choices that might be better? The first method is working really well in practice with my WIP integration. I have, coming from just main program and libc gaps, and possibly also the gaps of the LD_PRELOAD library measuing this: 2 1x128 1 1x240 3 1x496 2 1x1008 3 1x2032 Inside those, the following fit with plenty of space left over: 1 30x16 1 15x32 1 10x48 1 7x64 1 5x96 2 2x240 1 3x320 3 2x496 2 2x1008 Making up nominal allocations of 2996 bytes and free slots worth up to 6272 bytes. The only non-gap memory this test trace is using is one page for the out-of-band metadata. (Presently I'm not using gaps for that because it has a predictable address. But the below-data gaps, if any, are naturally guarded by text and would be fairly safe to use, aside from having predictable addresses, if we wanted to.) Rich