From: Florian Weimer <fweimer@redhat.com>
To: libc-alpha@sourceware.org
Subject: [5] malloc algorithm changes
Date: Sat, 14 Sep 2024 11:49:49 +0200 [thread overview]
Message-ID: <871q1mr2de.fsf@oldenburg3.str.redhat.com> (raw)
In-Reply-To: <87zfoar2tg.fsf@oldenburg3.str.redhat.com> (Florian Weimer's message of "Sat, 14 Sep 2024 11:40:11 +0200")
* Use real binary tree data structure for bins
* Reduce chunk header to 32 bits
* Track mmap allocations separately
* Packed heap support (no chunk headers)
* Use rseq virtual CPU ID (mm_cid)
This project is a successor to the malloc cleanup project. It is a
major one because it includes lots of benchmarking and workload
analysis, perhaps literature review, and adoption of new kernel
interfaces.
Each arena is grown in increments of 64 MiB heaps. Reportedly, this
results in excessive RSS usage. Lowering the heap size could reduce
this. However, due to the way the arena is computed from an address
(load from a fixed address with masking), this likely results in a
substantial increase in data cache misses due to increased
sharing. Instead, an arena ID could be encoded in the chunk header, so
that the arena access path uses the same data for all heaps in an arena.
Packed heaps consisting of chunks without a chunk header are another
idea to reduce RSS usage. This is tricky to implement because we need
to determine the heap type when free is called, just from the
address. This lookup has to happen before a chunk can land in the thread
cache because we need its size for that. This means that we need a data
structure that does not use atomics with fences.
Removing the chunk header from mmap allocations (which often requires an
extra page) and explicitly tracking mmap allocations could be beneficial
as well. This, too, needs some sort of address lookup, similar to
packed heaps.
Recent kernels added a concurrency CPU ID. We should explore using that
to find ways to avoid creating more arenas than concurrently executing
threads in a process. Cutting down the number of arenas should help to
reduce RSS usage significantly.
One trick we can play within glibc is to detach malloc data structures
from threads before we make a system call (especially those that are
potentially blocking). This, too, could be used to lower the number of
arenas we need.
To address arena bloat, we might want to investigate moving heaps from
one arena to another.
Our current malloc uses an ad-hoc data structure to manage binlists for
larger sizes. More recent versions of dlmalloc have switched to a
Patricia tree. We could explore using a red-black tree, maybe order by
size and then something address-derived. This could favor allocations
from “lower” addresses, so that more memory becomes available at the
“end” of the heap. (This is a bit tricky because we want to allocate in
increasing address order within a heap, but the kernel places mmap
segments in decreasing addresses.)
next prev parent reply other threads:[~2024-09-14 9:49 UTC|newest]
Thread overview: 55+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-09-14 9:40 Cauldron presentation: Mid-term larger projects for glibc (take two) Florian Weimer
2024-09-14 9:41 ` [1] Mid-term larger projects for glibc Florian Weimer
2024-09-14 9:45 ` [2] Target audiences Florian Weimer
2024-09-14 9:47 ` [3] ~~Gitlab/Github integration~~ Florian Weimer
2024-09-14 16:26 ` Andrew Pinski
2024-09-15 5:17 ` Arsen Arsenović
2024-09-15 16:51 ` Andreas K. Huettel
2024-09-15 17:00 ` Andrew Pinski
2024-09-18 7:11 ` Florian Weimer
2024-09-18 10:36 ` Florian Weimer
2024-09-14 18:37 ` Cristian Rodríguez
2024-09-15 5:14 ` Arsen Arsenović
2024-09-15 16:54 ` Andreas K. Huettel
2024-09-16 17:07 ` DJ Delorie
2024-09-16 19:39 ` Andreas K. Huettel
2024-09-16 19:59 ` DJ Delorie
2024-09-17 15:36 ` Noah Goldstein
2024-09-17 12:14 ` Florian Weimer
2024-09-16 11:52 ` Cyril Hrubis
2024-09-18 14:43 ` Alfred M. Szmidt
2024-09-18 14:59 ` Arsen Arsenović
2024-09-18 15:11 ` Alfred M. Szmidt
2024-09-14 9:48 ` [4] glibc malloc cleanup Florian Weimer
2024-10-02 14:02 ` Adhemerval Zanella Netto
2024-09-14 9:49 ` Florian Weimer [this message]
2024-10-03 16:14 ` [5] malloc algorithm changes Adhemerval Zanella Netto
2024-09-14 9:50 ` [6] malloc introspection support Florian Weimer
2024-09-14 9:54 ` [7] New TLS allocator Florian Weimer
2024-09-14 10:51 ` [8] New libio Florian Weimer
2024-09-14 10:59 ` [9] getenv improvements Florian Weimer
2024-09-14 11:00 ` [10] gmtime/localtime performance Florian Weimer
2024-09-15 17:55 ` Paul Eggert
2024-09-18 7:04 ` Florian Weimer
2024-09-18 7:43 ` Andreas Schwab
2024-09-18 7:53 ` Florian Weimer
2024-09-18 8:44 ` Andreas Schwab
2024-09-18 14:54 ` Paul Eggert
2024-09-14 11:01 ` [11] New NSS module API Florian Weimer
2024-09-15 18:55 ` Andreas K. Huettel
2024-09-16 13:59 ` Florian Weimer
2024-09-14 12:23 ` [12] New NSS application functions Florian Weimer
2024-09-14 12:24 ` [13] Useful clone3 wrapper Florian Weimer
2024-10-08 17:19 ` Adhemerval Zanella Netto
2024-09-14 12:26 ` [14] Backdating the ABI Florian Weimer
2024-09-15 16:57 ` Andreas K. Huettel
2024-09-15 20:34 ` H.J. Lu
2024-09-18 7:08 ` Florian Weimer
2024-09-14 12:27 ` [15] Address Sanitizer integration Florian Weimer
2024-09-14 12:27 ` [16] Initial symbol binding performance Florian Weimer
2024-09-14 12:30 ` [17] sysconf tuning for containers Florian Weimer
2024-09-14 12:31 ` [18] glibc build system modernization Florian Weimer
2024-09-14 12:32 ` [19] Fancier test framework Florian Weimer
2024-09-15 19:17 ` Andreas K. Huettel
2024-09-16 15:00 ` Cyril Hrubis
2024-09-18 5:56 ` Florian Weimer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=871q1mr2de.fsf@oldenburg3.str.redhat.com \
--to=fweimer@redhat.com \
--cc=libc-alpha@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).