What is malloc doing, anyway?

Posted by benmandrew 12 hours ago

Counter213Comment59OpenOriginal

Comments

Comment by assumed_throwaw 11 hours ago

Tangential, but the complexity and over-head of the malloc abstraction is precisely what made me very intrigued by "stack-only" languages, such a recently published Goose. There is something very elegant and exciting about the idea of (almost) completely getting rid of it. Just as modern programming languages have developed good ergonomics that replaces a garbage collector, the same could hopefully be done to replace heap-allocated memory.

Comment by i2talics 5 hours ago

If your takeaway from this was "wow malloc has so much overhead" then you may want to notice the part where they benchmark against glibc malloc and glibc is somewhere between 20-150x faster than their implementation. And that's fine, this exposition is basically what you would learn in an undergraduate systems programming course, but production allocators are able to significantly cut down the amount of work needed to grab an allocation, especially for small ones that occur frequently.

Comment by SkiFire13 4 hours ago

> the complexity and over-head of the malloc abstraction is precisely what made me very intrigued by "stack-only" languages, such a recently published Goose.

Goose's stacks have quite some complexity themselves. They preallocate a ton of memory. The compiler has to magically match your code to each stack. You are not allowed to have nested growing types (e.g. creating an adjacency list is not so easy). And after all for some usecases you still end up using an allocator (Goose's linked list example ends up building a pool allocator for the linked list nodes!)

Comment by smashspectacle 9 hours ago

This is actually what first drew me to zig. Most people talk about error handling, but the explicit allocator handling and making choosing an allocator a deliberate consideration has pushed me to better coding habits in general. I don't think it is possible or practical to completely abandon heap-allocated memory, but explicitly choosing between allocation types and styles that most precisely fit a job has great potential for meeting that spirit.

Comment by EPWN3D 8 hours ago

I don't think we can get rid of heap memory, but I do think we can get rid of a shared heap.

Comment by tremon 3 hours ago

To me the value of zig's approach is in being able to control the allocations that happen in (library) code. When you call a C function, all kinds of heap allocations may happen between the callee and malloc, even if the return value of the call is in caller-allocated memory. With zig, you can pass a local (arena) allocator instead and avoid uncontrolled global allocations.

Comment by dreamcompiler 3 hours ago

You can definitely avoid heap-allocated memory; early versions of Fortran could not do dynamic memory allocation at all. You basically had to preallocate giant arrays and build your own memory manager. It was sheer hell but it worked.

Comment by lawandjustice 9 hours ago

[flagged]

Comment by eschneider 8 hours ago

Embedded programming has taught me that almost anything can be a stack-only language if you want it to be, even C++. :)

Comment by connicpu 9 hours ago

Avoiding the heap entirely isn't required and will prevent you from working with substantial amounts of data. The real key is to allocate all the memory you need up front and use that large block for a long duration.

Comment by packetlost 7 hours ago

> Avoiding the heap ... will prevent you from working with substantial amounts of data

This isn't really true of Goose, it's avoiding 'the heap' in the C sense, not in the OS allocated pages of memory sense. One is a programming abstraction provided by the other, but GP is only talking about the programming abstraction. I have never encountered a program that couldn't have memory be explicitly tied to lexical scope, but it can result in less efficient use of it in some cases.

Goose is almost, but not exactly the "allocate all your stuff at the beginning" the programming language. It's honestly the most exciting language I've seen in quite some time.

Comment by dataflow 7 hours ago

> I have never encountered a program that couldn't have memory be explicitly tied to lexical scope, but it can result in less efficient use of it in some cases.

> Goose is honestly the most exciting language I've seen in quite some time.

I took a look at its home page [1] and I immediately see red flags:

- Over sixteen benchmarks Goose runs at 3.3x the speed of idiomatic C++, 1.16x hand-optimized C++ and 1.12x the best safe Rust, and uses 1.9x, 1.3x and 1.2x less memory (results). These gains come from Goose's data layouts and memory model.

- push returns a reference to the new element, so a program can link elements while building the array. A vector<T> or Vec<T> may reallocate and cannot provide this guarantee. Stable references account for several benchmark gains.

You're suggesting a performance loss (as expected), but they're claiming a (rather incredible) performance gain?

And they're claiming their vector stable and doesn't reallocate, yet without a performance loss, which makes no sense... it's not a vector anymore. And if you want a non-vector then you can do that in C++ too.

The whole LLM vibe doesn't help inspire confidence either, but even ignoring that, the technical claims themselves are incredible and bizarre, and I'm only a few paragraphs in.

[1] https://aardappel.github.io/goose/

Comment by kbolino 2 hours ago

It might be worthwhile to balance these positive claims against the language's own stated limitations [1].

Also, I took a closer look at the actual benchmark results [2]. For memory usage, at least, the median would show Goose using slightly more memory than the well optimized C++ and Rust. It looks like the mean is skewed in Goose's favor by a couple of benchmarks where it does extremely well due to its variable-length enums.

[1]: https://aardappel.github.io/goose/docs/tutorial.html#18-limi...

[2]: https://aardappel.github.io/goose/bench/results.html

Comment by Someone 2 hours ago

> You're suggesting a performance loss (as expected), but they're claiming a (rather incredible) performance gain?

I think part of the reason they’re getting higher performance is that they accept higher memory usage. Memory can be ‘freed’ later than in traditional languages, and the combined size of all stacks will be larger (maybe even much larger) than maximum memory usage.

The language likely also has limitations in that some constructs are hard or impossible to express (similar to how Rust has memory safety safer, but pays for it by having problems implemented doubly-linked lists)

Comment by senderista 5 hours ago

I just want to point out that the author of Goose has plenty of technical cred, having authored flatbuffers and lots of other cool stuff.

Comment by dataflow 3 hours ago

That's great, but it doesn't explain anything I'm seeing. I'm just commenting on the (presentation of) the project. It's entirely possible they have something awesome that just isn't presented well, or that I'm just too dense to grasp the awesomeness of what's before me. Whatever it is, I'm just saying I can't make sense of what I'm being sold.

Comment by packetlost 6 hours ago

Goose is a weird language. It uses a pile of pre-allocated datastacks, enforces lexical lifetimes for all data, and has first-class syntactic support for capped, growable, and shrinkable arrays. It also spits out a pile of C that gets all the optimization benefits of <insert C compiler of choices>.

Goose in particular excites me because I have done similar design work over the years.

Comment by jacquesm 9 hours ago

Most stack oriented languages also have a heap.

Comment by nialv7 10 hours ago

the stack is just a bump allocator. the unique thing about stack-only languages is lifetime management, not really how they allocate.

Comment by saagarjha 10 hours ago

A stack only language that called into malloc to service allocations would not be very interesting.

Comment by loeg 3 hours ago

This is mostly describing a kind of obsolete allocator that uses the brk to adjust a single contiguous heap range. This is basically irrelevant with virtual memory and mmap. The good malloc impls (jemalloc, mimalloc) don't do this.

Comment by bkallus 2 hours ago

> The good malloc impls (jemalloc, mimalloc) don't do this.

I agree.

> This is mostly describing a kind of obsolete allocator

I disagree. glibc malloc is still extremely relevant and sees a lot of development, and uses exactly this strategy (unless an allocation request is too big, in which case it mmaps, just like the allocator described in the article).

Comment by schmichael 2 hours ago

mmap is covered later on, and as an introduction to heap memory management this seems like the right place to start. jemalloc and mimalloc build upon the fundamentals explained here.

What I'd love is for an article that goes a step back in allocator theory instead of "forward" to jemalloc/mimalloc. Optimal resource allocation has a rich history in pre-computer fields whose general theories are applicable today. Replace "linear memory" with "paper roll" and "types" with "items", and instead of malloc you have the cutting stock problem! https://en.wikipedia.org/wiki/Cutting_stock_problem

The reason why allocator fundamentals are important is because there is no universally optimal solution. jemalloc "emphasizes fragmentation avoidance and scalable concurrency support" while mimalloc focuses on a bounded worst-case allocation latency. Meanwhile if you're writing extremely memory constrained code for certain embedded systems, you may still be best off using a simple bump allocator with no free! https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98... The optimal resource allocation strategy is always use case dependent.

Comment by nayuki 1 hour ago

> Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.

I would argue that the missile performs the ultimate in physical garbage creation at the end of its flight.

Comment by cadamsdotcom 45 minutes ago

Whoosh

Comment by senderista 5 hours ago

If you want to study how modern allocators work I'd recommend something like mimalloc, which has a reasonably approachable codebase. No brk/sbrk in sight, btw (or boundary tags, or splitting/merging...).

Comment by K0IN 8 hours ago

When getting into wasm when it was new and had clang support, I wrote my own libc and malloc, which was so a great learning all these low level functions and tricks (free lists for example), I also like that I can read wasm quite well, and tooling is good to just return a .wat and read it.

Comment by gebt 2 hours ago

This phrack article on malloc is highly recommended:

Vudo malloc tricks by Michel "MaXX" Kaempf (2001)

https://phrack.org/issues/57/vudo-malloc-tricks

Comment by virtyaluk 4 hours ago

I highly recommend reading Professional Linux Kernel Architecture by Wolfgang Mauerer, which describes the Linux memory management system in great detail.

Comment by okanat 2 hours ago

Kernel usually uses SLABs which work differently than general purpose userspace allocators.

Comment by syngrog66 29 minutes ago

As a rough rule of thumb: if you want smallest latency for small allocs use malloc not mmap, and for largest allocs prefer an ANON mmap. The blog post goes into more fractal detail, in general.

Comment by projectileboy 6 hours ago

Good learning resource for this (and related) topics: https://cs61.seas.harvard.edu/site/2026/

Comment by wpmaven 10 hours ago

I found this one very well explained time ago, for those looking for more details: https://sploitfun.wordpress.com/2015/02/10/understanding-gli...

Comment by benmandrew 10 hours ago

That's a great reference, thanks!

Comment by incognito124 4 hours ago

mental reminder to finish my history of malloc writeup. It's almost 20 llm-less pages with context and examples. goes through general purpose malloc like dlmalloc, mimalloc, tcmalloc, jemalloc and others, while also mentioning some purpose-specific ones like scudo.

Comment by zbentley 1 hour ago

I would enjoy reading that immensely. I hope it’s a “labor of love” big project and not a “this thing has gotten so big I hate it now” big project! Ping me if you want any proofreaders!

Comment by incognito124 46 minutes ago

It's a bit of a mix between "but wait there's even more details!" and "life will now suck for the foreseeable future".

Thanks, I'll keep that in mind, but don't get your hopes up

Comment by bajard 6 hours ago

Malloc() is sloooow. Even more if you also use free(). Consider allocating a single array and scratching there if possible.

Comment by BatchJob 1 hour ago

allocating memory, usually.

Comment by 0xbadcafebee 9 hours ago

This shows you how you could "secure" memory code in C by using more robust implementations of these functions. But it doesn't show you that you don't even need them anyway. I think in my entire career I've only used dynamic memory in C twice. The rest of the time I use functions with static allocations, buffers, unrolled loops, etc. Maybe it's paranoia, or habits from embedded programming, or being a control freak... But my C programs don't get memory leaks or crash from memory issues.

Comment by hansvm 8 hours ago

You can secure part of C with robust memory-handling functions. So long as people are using --> and ++ to parallel iterate through buffers where they have to pass the right length around separate from its pointer though, you're not going to fix it all.

Comment by OhMeadhbh 9 hours ago

   One of  my pet  peeves is  when people,  trying to  make a
   point, use code  that doesn't compile.  I  mean, it's fine
   when you're sketching  out code on a white  board.  But on
   an  article you've  had  time to  prepare,  it's a  little
   annoying.

   Take for instance, this code fragment:

   .. static void *ptrs[1000];
   .. 
   .. int main(void) {
   ..     for (int i = 0; i < 1000; i++)
   ..         ptrs[i] = malloc(16);
   ..     }
   ..  }

   I'm pretty sure what they //meant// to write was:

   .. #include <stdlib.h>
   ..
   .. static void *ptrs[1000];
   .. 
   .. int main(void) {
   ..     for (int i = 0; i < 1000; i++)
   ..         ptrs[i] = malloc(16);
   ..     }
   ..     return( 0 );
   ..  }

   I  understand why  the  author produced  the  code on  top
   instead of the code at the bottom.  The code on the bottom
   includes  features extraneous  to  the conversation.   The
   include  directive  and  return statement  only  serve  to
   distract from the point the author is making.

   If you read far enough down,  you'll see he has links to a
   broken GitHub  repo presumably  with code  fragments.  (or
   maybe  GitHub itself  is  broken today  or  it decided  it
   didn't  like me  trying to  access the  repo from  an AT&T
   fiber line.)

   I'm sure when GitHub decides to behave and serve bits like
   it's supposed to, there will be compilable code so readers
   can understand  the author's intent within  the context it
   was intended to be viewed.

   Which is to say:

   1. It's probably  okay to have only code  fragments in the
      main part  of your  discussion.  Please provide  a note
      that  there is  code which  shows your  snippet in  the
      context  of a  compilable program.   And put  that note
      somewhere near the code fragment.

      Or... consider putting  a note at the  beginning of the
      article saying  something like "Compilable  versions of
      code  fragments  in this  article  are  available at  a
      GitHub  repository  referenced  at the  bottom  of  the
      page."

   2. Do  not depend on  GitHub to hold your  code fragments.
      You do not  know when it will be down  or which readers
      it will randomly decide to block.

   3.  I really  do  think  you should  include  more of  the
      "layout"  code.   When   reading  "The  Address  Space"
      section,   it  was   unclear  where   the  initialized,
      uninitialized and local came from.  I initially thought
      the  author was  using a  version of  C I  had not  yet
      encountered that defined these symbols.

   4.  Since  the code  uses  ``sbrk()``,  the author  should
      probably have  cautioned readers  the code  isn't POSIX
      compliant, but should compile  and run on Linux systems
      using gcc.   There's a  comment about  demonstrating it
      with  glibc, but  I think  that's not  a strong  enough
      warning since you can  compile programs with clang that
      are intended to link against glibc.
      
      I doubt there  are many QNX users out  there who expect
      random code from  the internet to run  on their systems
      without alteration, but it  seems good form to describe
      the environment you are targeting.

      Now I'm wondering if this is expected to work on Darwin
      as well as Linux.

   5.  It  might  be  a  decent  idea  to  order  the  SHOW()
      statements in  the code in "The  Address Space" section
      to follow  the order  of the diagram  at the  bottom of
      that section:

      .. SHOW( "local (stack)", &local );
      .. SHOW( "printf (libc)", printf );
      .. SHOW( "program break", sbrk(0) );
      .. SHOW( "malloc(16) (heap)", malloc(16) );
      .. SHOW( "uninitialised (bss)", &uninitialised);
      .. SHOW( "initialised (data)", &initialised );
      .. SHOW( "main(text)", main );

   6.  In  the  "Chunks  and  Headers"  section,  it  may  be
      interesting to mention what the flags in the allocation
      headers actually mean.

   7. glibc does late fill,  right?  I can't remember.  If it
      does,  it might  be  useful to  mention  in the  Demand
      Paging section since it affects the program logic.
   
   Now that I've yelled at the  cloud a bit, allow me to say,
   I enjoyed the article.  Things I liked:

   1. The author  used the exact strace command  they used to
      produce  the  output  discussed  in  the  text  of  the
      article.

   2. The graphics are quite nice.

   3. Despite grousing about  fragments being fragments, they
      do a good job of illustrating points made in the text.

   EDIT: After complaining about  GitHub not being available,
   it's finally come back.  The web interface is still borked
   for me, but  I can clone the repo mentioned  at the bottom
   of the page and view the local copy of the source.

Comment by kano92-dir 2 hours ago

[flagged]

Comment by giannischatz 4 hours ago

A thing worth adding for anyone reading: in long-running PHP processes (workers, queue runners, Laravel Octane), the overhead of malloc/free patterns compounds in ways the request/response model hides.

A page handler that leaks 2KB per request is invisible under php-fpm (the process dies on the next request anyway) but becomes a slow memory creep in a queue worker that runs for hours. The fix usually isn't "call unset more" — it's recognizing which objects Zend's refcount can't collect without a full GC cycle (circular references, mostly), and forcing `gc_collect_cycles()` at known-safe points.

Took me a while to realize that in production.

Comment by haiderstudio 5 hours ago

[flagged]

Comment by arbor-group 9 hours ago

[flagged]

Comment by amelius 11 hours ago

If the DRAM scarcity continues, not much.

Comment by xnickb 10 hours ago

It's a consumer market scarcity. Since you're supposed to run everything on rented hardware, own nothing and be happy, I'd expect the malloc to be the right place to invest into once it is IPO.

Comment by loeg 3 hours ago

Hyperscalars are also experiencing DRAM scarcity, FWIW.

Comment by colejohnson66 8 hours ago

MaaS (malloc as a service)? Everytime your serverless function needs to allocate, you pay some fraction of a penny?

Comment by ozgrakkurt 6 hours ago

Just give us water as a service at this point

Comment by toast0 5 hours ago

Most people have that at home? Personally, I don't but electricity as a service + a well pump is WaaS with extra steps.

Comment by ozgrakkurt 3 hours ago

No no, I want the version where you have to subscribe per person and it is extremely difficult to unsubscribe a person from it.

Also where it gets worse and more expensive up to the point where people really can't pay for it anymore.

If you think about it, it should be possible to sell drinking water for 10$ per glass since people will buy it at that price. Just need to consolidate all of the supply by selling it on subsidized prices until all the competitors are bankrupt.

Comment by tialaramex 22 minutes ago

The really remarkable thing here is that the Tory party (Britain's centre-right party) were able to actually privatise water. In Britain the drinking water is supplied by private and in most cases for-profit companies, which as you'd expect are both terrible at this and also much more expensive than the previous solution.

I'm sure they're excited by your suggestion though tempered by the fact that we did make it illegal for them to cut off your supply of drinking water if you're in debt. Not electricity, you can freeze or sit in the dark, but we decided that leaving the impoverished thirsty was a step too far and people might realise Capitalism wasn't such a great ideal after all...

Comment by TZubiri 10 hours ago

like many C functions you must remember that C is not low level, you won’t learn how memory is allocated by inspecting malloc() anymore than you would learn how characters are printed to the screen by reading printf() or how a file is written by reading write().

you will only learn about the thin or heavy wrapper that C is responsible for, the real magic is happening in the kernel and the device firmware

Comment by netbsdusers 8 hours ago

Notwithstanding that most kernels today are written almost entirely in C anyway, you'll see learn a great deal about memory allocation by inspecting malloc().

The usual division of labour in most operating systems is the kernel manages the virtual memory and physical pages and provides a mechanism for coarse page-aligned allocation of virtual address for userland. These coarse mappings userland (malloc or something else) is responsible for carving up, and in that is much design space. Just look at mimalloc for example.

The kernel's own page allocation is often very simple (many get by with a simple freelist, some use buddies.) The allocators for the kernel's own datastructures are usually relatively simple at least conceptually. Bonwick explains the slab allocator - the almost universally acknowledged queen of all kernel memory allocators and mother of those of Linux, BSD, and beyond - in a 12-page paper.

As for the firmware there's basically nothing of an ongoing role for it after the kernel is in charge. Its role is limited for the most part to providing the kernel with a map of the physical addres space.

By reading malloc() you will not learn everything about allocation - that is a problem that spans multiple layers - but you will certainly learn a lot about it. To call it a mere wrapper is not reasonable.

Comment by foobarian 9 hours ago

Disagree, I found malloc source useful, and writing a toy allocator especially useful because you learn about the brk() syscall which is a great breadcrumb into kernel land and a great bridge to connect the memory mapping lessons from computer architecture with application code.

Comment by stevekemp 9 hours ago

Depending on how low-level you're going, you don't even need to call brk.

My toy stop/copy GC and allocation routines just have this:

    %define HEAP_SIZE (4 * 1024 * 1024 * 1024)

    .section bss
    ;;
    ;; Two heaps so we can flip-flop between them
    ;;
    heap_a:
        resb HEAP_SIZE
    heap_a_end:
    heap_b:
        resb HEAP_SIZE
    heap_b_end:
Of course there are other syscalls involved in my compiler/runtime, but for memory allocations the static area sufficed for me.

Comment by netbsdusers 8 hours ago

These days brk and sbrk have fallen from grace (and I think even some Unix-likes no longer provide them as general mechanisms, at least I don't think macOS does) - mmap is usually favoured.

Comment by Joker_vD 8 hours ago

> and writing a toy allocator especially useful because you learn about the brk() syscall

Nobody in their right mind (except musl) use brk(2) nowadays; mmap(2) is pretty much universally accessible, and brk() has been non-portable for more than 20 years already (POSIX ditched it in 2001) anyhow. For goodness sake, stop keeping this stupid API from VM-lacking PDP-7 alive, and let it go away!

Edit: also, I have no idea how musl even uses it:

    uintptr_t new = ctx.brk + pagesize;
    int need_guard = 0;
    if (!ctx.brk) {
        need_guard = 1;
        ctx.brk = brk(0);
        // some ancient kernels returned _ebss
        // instead of next page as initial brk.
        ctx.brk += -ctx.brk & (pagesize-1);
        new = ctx.brk + 2*pagesize;
    }
    if (brk(new) != new) {
        ctx.brk = -1;
    } else {
        if (need_guard) mmap((void *)ctx.brk, pagesize,
                PROT_NONE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
        ctx.brk = new;
        ctx.avail_meta_areas = (void *)(new - pagesize);
        ctx.avail_meta_area_count = pagesize>>12;
        need_unprotect = 0;
    }
That's... not what brk() returns; it returns 0 on success and -1 on failure. Huh?

Comment by roelschroeven 7 hours ago

When you call brk() from a user program you use the lib wrapper, and that does indeed return 0 on success and -1 on failure. But the actual Linux system call, which I presume is what musl calls, returns the current break on failure instead of -1.

See the NOTES section in man brk(2):

> C library/kernel differences

> The return value described above for brk() is the behavior provided by the glibc wrapper function for the Linux brk() system call. (On most other implementations, the return value from brk() is the same; this return value was also specified in SUSv2.) However, the actual Linux system call returns the new program break on success. On failure, the system call returns the current break. The glibc wrapper function does some work (i.e., checks whether the new break is less than addr) to provide the 0 and -1 return values described above.

Comment by Someone 9 hours ago

Malloc needs the kernel to obtain memory, but in any reasonable implementation (you do not want to make a syscall for every malloc and free) is mostly user space, and studying that will tell you a lot about how your malloc works.

Comment by 100111011111 8 hours ago

Well, yes, but its low level , no matter what, I mean whats left thats lower?