The history of Unix's confusing set of low-level ways to allocate memory (2018) | Hacker News Reader

The history of Unix's confusing set of low-level ways to allocate memory (2018)

utcc.utoronto.ca

97 pointsjaytaylor26 comments

This brought back memories from college, when I tried to write my own C memory allocator. It was decidedly simple and extremely inefficient (pretty sure it used linked lists...), but after much hacking I did eventually get it to work with some small CLI programs using the LD_PRELOAD trick... but when I tried launching Gimp, the inefficiency quickly became apparent. I think eventually the splash screen did come up, but I never gave it enough time fully to start!

My implementation used brk()/sbrk() exclusively, but I thought about re-implementing with mmap(). Hell, maybe I can try to write an allocator in Rust and expose a C-compatible interface.

For what it's worth, in the Linux kernel brk() just calls mmap() to grow the bss segment. So under the hood, just about everything is mmap(), and brk() is shorthand for a mmap() call that operates on a well known pre-existing mmap() area.

This sounds so ancient, but I clearly remember seeing the sbrk() system call happening a lot when strace'ing processes on Linux, so it can't be much more than 20 years ago, or maybe much less even. When did allocators on Linux stop doing that? glibc?

EDIT: Never mind, the article answers that eventually, it's still used apparently: "I know that GNU libc does use brk() based allocation for programs that only make small allocations, for example /usr/bin/echo."

The old, original tcmalloc that is still widely used starts out using sbrk and only switches to mmap if it exhausts the heap. So if you trace a program using gperftools/tcmalloc you could expect to see plenty of sbrk.

(The newer hugepage-aware tcmalloc never uses sbrk.)

What do you mean when you say it exhausts the heap? I understand that the stack size is fixed but can't the heap grow unbounded using sbrk till it exhausts the address space?

I don't know anything aboug tcmalloc specifically but if the program is not mapped at 0, then there's space below it as well. The heap can meet the stack using sbrk while memory below where the program is could still be mmapped. This was the case on x86-32 anyway. On x86-64 programs are mapped much lower (on my system anyway.)

I think they mean that it grows to the point where it collides with the virtual address space allocated to another block (the stack, a shared library, a mmap'd area etc)

It's worth noting that WebAssembly, at least for the moment, only supports a single brk/sbrk-style growable heap -- allocators targeting the web can't use any of the mmap tricks.

Pardon my ignorance, but I'm really curious to know why?

The FAQ has a "what about mmap?" section which gives some justification: https://webassembly.org/docs/faq/#what-about-mmap

So much amusing past tense there, given that Linux has a sbrk() function and Glibc cheerfully uses it for small allocations in single-threaded programs. This stuff is today.

On Linux. On FreeBSD it’s all ancient history; kernel doesn’t even implement brk() on newer architectures.

I just found MacOS, Solaris and OpenBSD man pages documenting sbrk and brk.

There's even a FreeBSD one (https://man.freebsd.org/brk), which doesn't change the fact that this syscall is not implemented on eg aarch64 and riscv64.

Well, it doesn't change the fact because it's too busy documenting the fact in the first paragraph.

OpenBSD's page calls them "curiosities from before the days of virtual memory management" in the first paragraph, without mentioning that they are missing in any targets. (Still, they are entirely compatible with virtual memory management.)

Tangentially, libraries for microcontrollers (e.g. nanolib) will typically use sbrk(). To port the library to a new architecture for the memory stuff you usually implement sbrk() yourself, and this will be sufficient for malloc and friends to compile

On the other hand, as far as I know, there was never the concept of a "brk" in the DOS/Windows world; in DOS, by default programs got all memory (no virtual memory, all physical), and there was a set of malloc/free/realloc-ish functions for TSRs and other "advanced" techniques. DOS-based Windows memory allocation goes through DPMI which again provides similar functionality to malloc/free/realloc, as well as mmap. NT-based Windows is similar but without the DPMI.

Not quite true. DOS programs were not automatically given all memory. DOS programs needed to allocate various memories (Conventional, EMS, XMS memory) via API specific to each type. DOS programs running under Windows 95 and later were presented with a DPMI compatible API if they so choose to use. DPMI DOS Extenders were intended to provide DOS compatibility for 16-bit and 32-bit Protected Mode applications. Memory allocation was just one service type they provided. Some also provided virtual memory or Win32 API emulation.

https://fd.lod.bz/rbil/interrup/dos_kernel/2148.html#sect-29...

https://fd.lod.bz/rbil/interrup/memory/2f4310.html#sect-4815

https://fd.lod.bz/rbil/interrup/memory/673f_cx5145.html#sect...

https://en.wikipedia.org/wiki/DOS_extender#DOS_extenders

https://en.m.wikipedia.org/wiki/CWSDPMI

https://www.japheth.de/HX.html

In real-mode DOS the situation is that the program is loaded to continuous block of memory that is followed by it's BSS and heap. The MZ header only specifies how big the BSS+heap part should be. Typical MZ format EXE has the size specified as BSS size by minimum and no maximum, which causes the MZ loader to allocate everything from PSP to the end of present conventional memory to the process. One consequence of that is that if you want to run other programs you have to either change the usual default of "unlimited" heap size or free some memory manually (or use COM format executable which by default only gets one DS=CS=SS segment).

Tangential question: Is anything considered state-of-the-art in terms of replacing POSIX?

Fuchsia looks interesting to me. It has POSIX, but it seems to be a veneer over better ideas. Some of that is described here: https://fuchsia.dev/fuchsia-src/concepts/system/libc?hl=en

I'm not sure what's supposed to be confusing here but one thing I don't know is why it was called the heap. Did they use heap data structures or something?

As far as I can tell, the term heap comes from Algol 68. Algol 68 had garbage collection, and used mark and sweep. Mark and sweep works by searching memory like a tree, starting at the stack, so Algol 68 called this memory heap memory (at this point, heap was often used to just mean any tree). Languages like pascal and c also began calling their dynamic memory region the heap.

I am a not a native speaker but Google Dictionary says this:

Heap: "an untidy collection of objects placed haphazardly on top of each other". Example: "a heap of cardboard boxes"

This makes sense as the Unix Heap is just a space containing a random collection of objects with random sizes.

There is another way unix allocates memory, and that is with automatically growing regions that are used to allocate program stack.

This is pretty typical in nearly every modern operating system - the kernel hands out large chunks of memory and the user-mode side actually does the accounting to implement malloc/free. Memory management in NT is also done in usermode (i.e. in-process)

Reply on news.ycombinator.com