Memory allocation for the curious | Hacker News Reader

Memory allocation for the curious

kahlonel.io

64 pointskahlonel13 comments

Or, wonder why the heck do I have to read 8k lines to understand how memory allocation works, …

glibc isn't exactly known for having readable code. There are other libc implementations with more of a focus on simplicity. The malloc in musl libc, for example, is only 533 lines long: https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c

I really wish the article would then follow up with much more depth. The presentation is good, and then it just stops. My brain was definitely desiring more.

I recommend writing a memory allocator. And then throwing it out and never using it because there are better off the shelf solutions, but now you'll understand why. Or read one of the white papers that accompanies new memory allocators. There's a couple good ones but I'm on mobile and can't pull them up.

I did so once, in my confused and reckless youth when I thought I could do better. I was running a level loader for a game, in 30 to 40% of the load time was being spent in memory allocation. How hard can that be I thought?

Turns out there's a whole heap (hah!) of trade-offs to be made, and a frightening amount of edge cases and performance concerns to be had with general allocation strategies. There is a wide spread belief that it is near impossible to design algorithms that scale horizontally with added cores. I'm convinced this belief started in academia with people writing memory allocators. The real takeaway I learned was to avoid memory allocation whenever and wherever possible, which actually works quite well.

Edit: Also the speech to text I'm using wants to transcribe memory allocator as memory alligator. I almost let that one stand. You should touch the allocator about as often and with as much caution as you want to touch an alligator.

Great post for learning.

I posted a similar test of sbrk() coding in my rt0 lib [0]. With less trivial examples, it's interesting to see how various addresses change as they're used to keep track of what the kernel is doing to the program's virtual address space.

[0] https://github.com/lpsantil/rt0/blob/master/t/sbrk.c

In fact, sbrk() is pretty much deprecated and right way to get virtual address space is mmap(MAP_ANONYMOUS) or its equivalents.

Most significant problem with sbrk()-style heap growth is that the continuous heap area can grow into virtual addresses that are already allocated for something else (SysV IPC-style shared memory being prime example)

malloc still uses sbrk() it seems; and only uses mmap() when requesting blocks larger than MMAP_THRESHOLD. I'll have to verify this I guess.

http://man7.org/linux/man-pages/man3/malloc.3.html

Yup that's true on my machine atleast. Ran this:

  #include <stdio.h>
  #include <stdlib.h>

  int main(void)
  {
  	int i = 0;
	for(i=0; i<200000; i+= 1000)
	{
		printf("%d",i);
		fflush(stdout);
		malloc(i);
	}

  return 0;
  }

strace output where it switches from sbrk to mmap:

  write(1, "125000", 6125000)                   = 6
  write(1, "126000", 6126000)                   = 6
  brk(0x1a65000)                          = 0x1a65000
  write(1, "127000", 6127000)                   = 6
  write(1, "128000", 6128000)                   = 6
  brk(0x1aa3000)                          = 0x1aa3000
  write(1, "129000", 6129000)                   = 6
  write(1, "130000", 6130000)                   = 6
  brk(0x1ae2000)                          = 0x1ae2000
  write(1, "131000", 6131000)                   = 6
  write(1, "132000", 6132000)                   = 6
  mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f3aa9b04000
  write(1, "133000", 6133000)                   = 6
  mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f3aa9ae3000
  write(1, "134000", 6134000)                   = 6
  mmap(NULL, 135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f3aa9ac2000

Maybe it depends upon the architecture? With a 64 bit address space, there should be plenty of room to allow for a contiguous sbrk-allocated chunk of memory and separate mmap regions that are far away from any possible overlap. 32 bit processes might have to take more precautions to prevent premature address space collisions.

Wouldn't sbrk kind of get in the way of ASLR?

Only in Linux's case.

Pretty cool blog post, I'd like to see a followup which discusses garbage collection, dealloc, release. et-all.

Skeeto/Chris Wellons [0] did a great write up on a basic Reference Counting Garbage Collector. I've done an initial translation [1][2] into a reusable library. Bob Nystrom also wrote a great tutorial on implementing a basic GC for a simple dynamic language [3].

[0] http://nullprogram.com/blog/2015/02/17/

[1] https://github.com/lpsantil/vgc/blob/master/original/t/t0000...

[2] https://github.com/lpsantil/vgc/blob/master/original/include...

[3] http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...

Too shallow from any point.

Reply on news.ycombinator.com