4 ms·

Memory allocation for the curious

64 points by kahlonel 9y ago

karlkloppenborg 9y ago
Pretty cool blog post, I'd like to see a followup which discusses garbage collection, dealloc, release. et-all.
- oso2k 9y ago
  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/ http://nullprogram.com/blog/2015/02/17/ [1] https://github.com/lpsantil/vgc/blob/master/original/t/t00000.c https://github.com/lpsantil/vgc/blob/master/original/t/t0000... [2] https://github.com/lpsantil/vgc/blob/master/original/include/vgc/vgc.h https://github.com/lpsantil/vgc/blob/master/original/include... [3] http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...
dfox 9y ago
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)
- kahlonel 9y ago
  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 http://man7.org/linux/man-pages/man3/malloc.3.html
  - kahlonel 9y ago
    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
  - deleted 9y ago
    [deleted]
- joosters 9y ago
  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.
  - elderK 9y ago
    Wouldn't sbrk kind of get in the way of ASLR?
- pjmlp 9y ago
  Only in Linux's case.
katastic 9y ago
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.
- kobeya 9y ago
  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.
lostmsu 9y ago
Too shallow from any point.
panic 9y ago
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 https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c
oso2k 9y ago
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 https://github.com/lpsantil/rt0/blob/master/t/sbrk.c

64 points by kahlonel 9y ago

karlkloppenborg 9y ago

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

oso2k 9y ago
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/ http://nullprogram.com/blog/2015/02/17/ [1] https://github.com/lpsantil/vgc/blob/master/original/t/t00000.c https://github.com/lpsantil/vgc/blob/master/original/t/t0000... [2] https://github.com/lpsantil/vgc/blob/master/original/include/vgc/vgc.h https://github.com/lpsantil/vgc/blob/master/original/include... [3] http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...

dfox 9y ago

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)

kahlonel 9y ago
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 http://man7.org/linux/man-pages/man3/malloc.3.html
- kahlonel 9y ago
  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
- deleted 9y ago
  [deleted]
joosters 9y ago
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.
- elderK 9y ago
  Wouldn't sbrk kind of get in the way of ASLR?
pjmlp 9y ago
Only in Linux's case.

katastic 9y ago

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.

kobeya 9y ago
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.

lostmsu 9y ago

Too shallow from any point.

panic 9y ago

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 https://git.musl-libc.org/cgit/musl/tree/src/malloc/malloc.c

oso2k 9y ago

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 https://github.com/lpsantil/rt0/blob/master/t/sbrk.c