33

Typical implementations of malloc use brk/sbrk as the primary means of claiming memory from the OS. However, they also use mmap to get chunks for large allocations. Is there a real benefit to using brk instead of mmap, or is it just tradition? Wouldn't it work just as well to do it all with mmap?

(Note: I use sbrk and brk interchangeably here because they are interfaces to the same Linux system call, brk.)

For reference, here are a couple of documents describing the glibc malloc:

GNU C Library Reference Manual: The GNU Allocator
https://www.gnu.org/software/libc/manual/html_node/The-GNU-Allocator.html

glibc wiki: Overview of Malloc
https://sourceware.org/glibc/wiki/MallocInternals

What these documents describe is that sbrk is used to claim a primary arena for small allocations, mmap is used to claim secondary arenas, and mmap is also used to claim space for large objects ("much larger than a page").

The use of both the application heap (claimed with sbrk) and mmap introduces some additional complexity that might be unnecessary:

Allocated Arena - the main arena uses the application's heap. Other arenas use mmap'd heaps. To map a chunk to a heap, you need to know which case applies. If this bit is 0, the chunk comes from the main arena and the main heap. If this bit is 1, the chunk comes from mmap'd memory and the location of the heap can be computed from the chunk's address.

[Glibc malloc is derived from ptmalloc, which was derived from dlmalloc, which was started in 1987.]

The jemalloc manpage (http://jemalloc.net/jemalloc.3.html) has this to say:

Traditionally, allocators have used sbrk(2) to obtain memory, which is suboptimal for several reasons, including race conditions, increased fragmentation, and artificial limitations on maximum usable memory. If sbrk(2) is supported by the operating system, this allocator uses both mmap(2) and sbrk(2), in that order of preference; otherwise only mmap(2) is used.

So, they even say here that sbrk is suboptimal but they use it anyway, even though they've already gone to the trouble of writing their code so that it works without it.

[Writing of jemalloc started in 2005.]

UPDATE: Thinking about this more, that bit about "in order of preference" gives me a line on inquiry. Why the order of preference? Are they just using sbrk as a fallback in case mmap is not supported (or lacks necessary features), or is it possible for the process to get into some state where it can use sbrk but not mmap? I'll look at their code and see if I can figure out what it's doing.

I'm asking because I'm implementing a garbage collection system in C, and so far I see no reason to use anything besides mmap. I'm wondering if there's something I'm missing, though.

(In my case I have an additional reason to avoid brk, which is that I might need to use malloc at some point.)

Guy Avraham
  • 3,482
  • 3
  • 38
  • 50
Nate C-K
  • 5,744
  • 2
  • 29
  • 45
  • You mean using a single `mmap` to allocate a pool for thousands of smaller allocations, right? Not one `mmap` per allocation like you'd do for large ones – that other guy Apr 19 '19 at 22:42
  • There are versions of `malloc()` that use `mmap()`. – Barmar Apr 19 '19 at 22:44
  • 2
    Possible duplicate of [What does the brk() system call do?](https://stackoverflow.com/q/6988487/608639), [Does malloc() use brk() or mmap()?](https://stackoverflow.com/q/30542428/608639), [About sbrk() and malloc()](https://stackoverflow.com/q/34248854/608639), etc. – jww Apr 19 '19 at 23:36
  • @thatotherguy: I've added some info in the question about what the allocators that I've been reading about actually do. – Nate C-K Apr 20 '19 at 12:32
  • 1
    Note that glibc malloc *does* use `mmap` for large allocations. The `jemalloc` negative comments about `brk` apply most strongly to using it for *everything*, like ancient Unix history malloc implementations. (especially fragmentation: inability to give back memory to the kernel if there's a long-term small allocation after a short-term large allocation.) – Peter Cordes Jan 04 '22 at 12:07

5 Answers5

12

Calling mmap(2) once per memory allocation is not a viable approach for a general purpose memory allocator because the allocation granularity (the smallest individual unit which may be allocated at a time) for mmap(2) is PAGESIZE (usually 4096 bytes), and because it requires a slow and complicated syscall. The allocator fast path for small allocations with low fragmentation should require no syscalls.

So regardless what strategy you use, you still need to support multiple of what glibc calls memory arenas, and the GNU manual mentions: "The presence of multiple arenas allows multiple threads to allocate memory simultaneously in separate arenas, thus improving performance."

The jemalloc manpage (http://jemalloc.net/jemalloc.3.html) has this to say:

Traditionally, allocators have used sbrk(2) to obtain memory, which is suboptimal for several reasons, including race conditions, increased fragmentation, and artificial limitations on maximum usable memory. If sbrk(2) is supported by the operating system, this allocator uses both mmap(2) and sbrk(2), in that order of preference; otherwise only mmap(2) is used.

I don't see how any of these apply to the modern use of sbrk(2), as I understand it. Race conditions are handled by threading primitives. Fragmentation is handled just as would be done with memory arenas allocated by mmap(2). The maximum usable memory is irrelevant, because mmap(2) should be used for any large allocation to reduce fragmentation and to release memory back to the operating system immediately on free(3).

The use of both the application heap (claimed with sbrk) and mmap introduces some additional complexity that might be unnecessary:

Allocated Arena - the main arena uses the application's heap. Other arenas use mmap'd heaps. To map a chunk to a heap, you need to know which case applies. If this bit is 0, the chunk comes from the main arena and the main heap. If this bit is 1, the chunk comes from mmap'd memory and the location of the heap can be computed from the chunk's address.

So the question now is, if we're already using mmap(2), why not just allocate an arena at process start with mmap(2) instead of using sbrk(2)? Especially so if, as quoted, it is necessary to track which allocation type was used. There are several reasons:

  1. mmap(2) may not be supported.
  2. sbrk(2) is already initialized for a process, whereas mmap(2) would introduce additional requirements.
  3. As glibc wiki says, "If the request is large enough, mmap() is used to request memory directly from the operating system [...] and there may be a limit to how many such mappings there can be at one time. "
  4. A memory map allocated with mmap(2) cannot be extended as easily. Linux has mremap(2), but its use limits the allocator to kernels which support it. Premapping many pages with PROT_NONE access uses too much virtual memory. Using MMAP_FIXED unmaps any mapping which may have been there before without warning. sbrk(2) has none of these problems, and is explicitly designed to allow for extending its memory safely.
Community
  • 1
  • 1
  • 1
    Fragmentation would be a concern for brk if you used it for large allocations as well: you can only give memory back to the kernel in LIFO order, so a long-lived small allocation after a short-lived large allocation could stop us from giving back that big chunk of memory. Sure we can put it on the free list and chop it up into smaller blocks for future allocs, but if it's a gigabyte of dirty private memory, that's not what you want. Or if it's large but not quite large enough for the next big allocation, also not good. Those are basically fragmentation problems. (Which glibc avoids w. mmap) – Peter Cordes Jan 04 '22 at 12:12
  • 1
    Memory allocations in the break arena can't be extended if a separate `malloc` allocation follows a large allocation. We can extended the break just fine, but that doesn't help satisfy a `realloc` library call. So using a dedicated mmap for each large allocation makes it much more likely that realloc to become even larger can be done without hitting some other allocation. (And avoiding copying is more important the larger the allocation is). So that's another good reason for glibc to have a heuristic to switch from an arena to a direct mmap. – Peter Cordes Jan 04 '22 at 12:15
10

The system call brk() has the advantage of having only a single data item to track memory use, which happily is also directly related to the total size of the heap.

This has been in the exact same form since 1975's Unix V6. Mind you, V6 supported a user address space of 65,535 bytes. So there wasn't a lot of thought given for managing much more than 64K, certainly not terabytes.

Using mmap seems reasonable until I start wondering how altered or added-on garbage collection could use mmap but without rewriting the allocation algorithm too.

Will that work nicely with realloc(), fork(), etc.?

wallyk
  • 56,922
  • 16
  • 83
  • 148
  • The thing is, modern allocators have rewritten their allocation algorithms extensively since then. One, jemalloc, wasn't even written until 2005. And modern allocators do use `mmap` extensively, so it seems they've figured out how to make it work. However, the ones I've been looking at mix it with calls to `sbrk`, as I've now described in some updates to the question. – Nate C-K Apr 20 '19 at 12:50
9

mmap() didn't exist in the early versions of Unix. brk() was the only way to increase the size of the data segment of the process at that time. The first version of Unix with mmap() was SunOS in the mid 80's, the first open-source version was BSD-Reno in 1990.

And to be usable for malloc() you don't want to require a real file to back up the memory. In 1988 SunOS implemented /dev/zero for this purpose, and in the 1990's HP-UX implemented the MAP_ANONYMOUS flag.

There are now versions of mmap() that offer a variety of methods to allocate the heap.

Barmar
  • 741,623
  • 53
  • 500
  • 612
  • 4
    That explains why `mmap` wasn't used in the past, but modern versions *do* use it, so I'm not sure if the history explains why they don't use it exclusively. Maybe they were originally written to use `brk` only and then added `mmap` calls later as an improvement? But jemalloc only dates back to 2005 and it uses both `sbrk` and `mmap`. – Nate C-K Apr 19 '19 at 23:52
7

The obvious advantage is that you can grow the last allocation in place, which is something you can't do with mmap(2) (mremap(2) is a Linux extension, not portable).

For naive (and not-so-naive) programs which are using realloc(3) eg. to append to a string, this translates in a 1 or 2 orders of magnitude speed boost ;-)

  • Couldn't I just claim a large amount of RAM with mmap, say 1 GB, and then start filling it in from the bottom up? I don't think that would actually consume physical memory until the pages are touched, right? I could also mark the unused pages with PROT_NONE to make sure they aren't accessed accident before I mean to use them. – Nate C-K Apr 19 '19 at 23:35
  • 2
    without thinking too deep about it: claiming a bing chunk of contiguous virtual memory (eg. 1G) will create big problems on 32bit machines. This is usually done only with lisp vms, emulators and such; it's not acceptable that the implementation of a library function like malloc() hog most of the available address space. –  Apr 19 '19 at 23:47
  • Yes, that makes sense. Maybe that's part I was missing: malloc has to stay out of the way of other programs, and growing the heap from the bottom means that other programs know how to stay out of its way. But you could grow the heap from the bottom using mmap without bothering to call brk, couldn't you? Maybe if you're going to do that then you might as well do brk, though. – Nate C-K Apr 20 '19 at 00:09
  • 2
    Google suggests that Go's memory allocator is entirely `mmap` based – that other guy Apr 20 '19 at 01:44
  • 1
    @thatotherguy and so was FreeBSD's malloc iirc. –  Apr 20 '19 at 01:45
  • As far as I can tell, FreeBSD uses jemalloc in their libc. I've added some info about jemalloc in the question: it will rely entirely on mmap if sbrk is unavailable, but it can use sbrk. – Nate C-K Apr 20 '19 at 13:05
4

I don't know the details on Linux specifically, but on FreeBSD for several years now mmap is preferred and jemalloc in FreeBSD's libc has sbrk() completely disabled. brk()/sbrk() are not implemented in the kernel on the newer ports to aarch64 and risc-v.

If I understand the history of jemalloc correctly, it was originally the new allocator in FreeBSD's libc before it was broken out and made portable. Now FreeBSD is a downstream consumer of jemalloc. Its very possible that its preference for mmap() over sbrk() originated with the characteristics of the FreeBSD VM system that was built around implementing the mmap interface.

It's worth noting that in SUS and POSIX brk/sbrk are deprecated and should be considered non-portable at this point. If you are working on a new allocator you probably don't want to depend on them.

Bill Sorenson
  • 41
  • 1
  • symbolic constant 'MAN_ANONYMOUS' for mmap() is not specified in POSIX either... good luck trying to implement malloc() with mmap() without using anonymous mapping :/ – MrIo Apr 11 '23 at 12:14