5 ms·

Visual overview of a custom malloc() implementation

92 points by signa11 3y ago

ksvarma 3y ago
Excellent, very well written.
tilt_error 3y ago
Why are the letters ’p’, ’q’ and ’t’ missing from the article? Makes it a bit annoying to read.
- oplaadpunt 3y ago
  I think this might be a client-side issue, since I can see those letters normally.
- Karellen 3y ago
  I also had that issue when reading the article on Safari/iOS. Switching to reader mode fixed it though. No issue on Firefox/Linux. Looks like a platform-specific font rendering issue?
- wcrossbow 3y ago
  I don't see `r`s. Firefox/Mac
- tlb 3y ago
  No 'r's or '3's on Safari/Mac. It's a custom font 'Cantarell', evidently a bit broken.
  - hgs3 3y ago
    > evidently a bit broken And here I thought the author was making a fragmentation joke.
unwind 3y ago
This was very good! I was really happy when the first code on the page, for once, did not look like it was written by someone writing C when they would much rather write something else. This line: struct article *my_article = malloc(sizeof *my_article); Is almost exactly how I would have written it, and (to me) does three things very right: - Does not use a pointless, wordy, bloated cast to somehow "convert" the pointer to the proper type. The point of malloc() returning a void pointer is that no such cast is needed. - Does not hardcode a size, but uses the sizeof operator to let the compiler compute it. - Does not repeat the type name, which is brittle and wordy, but instead (again) lets the compiler compute it from the target pointer. I was a bit more hesitant about this line, later in the article: return (void *)b + sizeof(block_t) + b->size; Not sure what language standard is targeted by the code in the article, but being able to do pointer arithmetic with void pointers is a GCC extension which at least should be mentioned.
- senkora 3y ago
  For context, the reason why you often see explicit casts from void* to other pointer types is that C++ forbids implicit casts from void*, which is one of the few compatibility breaks that C++ did with C. (For better or for worse, people often compile C-style code with a C++ compiler)
  - flohofwoe 3y ago
    > which is one of the few compatibility breaks that C++ did with C It's not "few" though, it's "quite a lot". C and C++ semantics are so different that you'll have to write in a specific "common C/C++ subset" for code that should compile both in C and C++ mode. For all the flak that Objective-C usually gets by both C and C++ people it did one thing right: it respects C as a proper subset instead of creating its own bastard-fork like C++ did and then freezing it in the mid-90s.
  - unwind 3y ago
    I know, that's why I wrote that the code looked like it was written by someone who wanted to write in C (as opposed to someone who wanted to write in C++, a different language).
astrange 3y ago
Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.
- masklinn 3y ago
  Also unfortunate are the use of a heap segment representation, and sbrk.
  - matheusmoreira 3y ago
    I understand why the use of sbrk is unfortunate but what's wrong with the representation? Are there better ones?
    - masklinn 3y ago
      The heap growing towards the stack is a property of the heap segment (used by brk/sbrk). mmap is not bound to this model, and unless used with MAP_FIXED can associate the allocation with virtual addresses anywhere in the address space.
- Karellen 3y ago
  If you're writing your own malloc(), you could argue you are legitimately part of the system implementation. Those type names are reserved for you.
- flohofwoe 3y ago
  C and POSIX are different things though. The only reason why POSIX reserves _t is to avoid potential name collisions, but POSIX moves so slowly that such collisions are rarely a problem (and on any non-UNIX system it's a non-issue anyway). I *would* have used a prefix for namespacing though, e.g. not `block_t` but `prefix_block_t`.
- acuozzo 3y ago
  Do you know if any of the popular static analysis tools detect mistakes like this?
anonymousDan 3y ago
Is segmentation still viewed as terrible? There seems to be a trend towards hardware mechanisms for more fine-grained intra-process memory protection than is practical with paging. Nice intro though.
- flohofwoe 3y ago
  I'm not an expert in memory allocation strategies, but AFAIK fragmentation can still be a problem with a naive allocator that doesn't group small allocations (less than a page size) into buckets. You won't run out of virtual address space (as was the case with 32-bit processes on computers with much more than 4 GB physical memory), but you may run out of physical memory if the allocator is "blocking" a whole memory page from being recycled because there's a tiny live allocation in it.
  - mort96 3y ago
    Segmentation isn't fragmentation. "Segmentation" is when you have a machine with 16 bit machine words, which would usually mean you can only address up to 2^16 = 65536 bytes of memory, but you want to support up to 1 MiB of RAM so you add a segment register and read all memory reads as relative to (segment register << 4) so that you support up to 20 bit memory addresses. (The details differ of course, but this is how Intel did it.) This results in a split between "near pointers" and "far pointers". "Near pointers" are pointers which are 16 bit and assumed to be relative to the "current segment", and can thus be dereferenced directly with any memory load instruction. "Far pointers" are 32 bit and carry a segment part and a relative part, and to dereference it, you must first write the segment part to the segment register, then do the memory load instruction with the relative part, and then you probably wanna clean up after yourself by restoring the segment register to its old state. There were multiple segment registers too, one used for data ("heap") memory operations, one for stack memory operations, one for reading machine code, and some extra segments for convenience. You had to remember which of the segment registers your near pointer was supposed to be relative to. If this all sounds very tedious... well, it was, and that's why, yes, segmentation is still viewed as terrible :) (I wasn't around back when this was common, but I did write some 16-bit real mode code for a bootloader for an OS course once, and I have designed and implemented some toy 8 bit CPUs which used segmentation to have more than 256 bytes of RAM, so I do have some experience with it)
matheusmoreira 3y ago
Could have used an article like this when I was implementing my own allocator! This is great. The Wilson1995 paper referenced is also quite useful. The algorithm I implemented is very similar to the one implemented in this article: start with a huge block of free memory; split it into multiple blocks on allocation; merge with free neighbors on deallocation. Merging blocks is the reason why doubly linked lists are needed. It worked well enough so I didn't make it a priority to organize the free lists by size. I really should implement that already but there are so many other things to do... It's also important to discuss the fact that implementing a memory allocator in C essentially requires undefined behavior. Arithmetic will be done with arbitrary pointers and the result will be cast to structures. Compiling with strict aliasing turned off is essentially a must. Others have described to me "pointer laundering" techniques where they pass the pointer through some inline assembly just to prevent the optimizer from making incorrect assumptions. Just turning off strict aliasing seems like a better idea. It's a stupid feature anyway. If you're writing C, you're probably aliasing pointers and reinterpreting memory and the last thing you need is the compiler getting clever about it. Alignment was pretty difficult to wrap my head around at first, especially the universal alignment concept. It also illustrates one of the limitations of C's malloc interface: > malloc() can simply return maximally-aligned pointers in order to accommodate any data type This wastes quite a lot of memory when the maximum alignment is not necessary... It should also be possible to segregate free lists by alignment, right? Seems like alignment should be a parameter of the memory allocation function. This article is also really great: https://nullprogram.com/blog/2023/12/17/ https://nullprogram.com/blog/2023/12/17/ https://news.ycombinator.com/item?id=38675379 https://news.ycombinator.com/item?id=38675379 Explores the idea of breaking away from C's legacy memory allocation interfaces. If you're like me and enjoy the idea of reinventing things from scratch, it's a great read. Also linked from its HN discussion: https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
saagarjha 3y ago
> This means that the largest alignment requirement of any basic type (max_align_t in C++, usually 4 bytes for 32-bit architectures and 8 bytes for 64-bit architectures) is suitable for every single type in the language. Usually alignment is a bit larger, to accommodate SSE etc. which requires larger alignment.

92 points by signa11 3y ago

ksvarma 3y ago

Excellent, very well written.

tilt_error 3y ago

Why are the letters ’p’, ’q’ and ’t’ missing from the article? Makes it a bit annoying to read.

oplaadpunt 3y ago
I think this might be a client-side issue, since I can see those letters normally.
Karellen 3y ago
I also had that issue when reading the article on Safari/iOS. Switching to reader mode fixed it though. No issue on Firefox/Linux. Looks like a platform-specific font rendering issue?
wcrossbow 3y ago
I don't see `r`s. Firefox/Mac
tlb 3y ago
No 'r's or '3's on Safari/Mac. It's a custom font 'Cantarell', evidently a bit broken.
- hgs3 3y ago
  > evidently a bit broken And here I thought the author was making a fragmentation joke.

unwind 3y ago

This was very good! I was really happy when the first code on the page, for once, did not look like it was written by someone writing C when they would much rather write something else. This line: struct article *my_article = malloc(sizeof *my_article); Is almost exactly how I would have written it, and (to me) does three things very right: - Does not use a pointless, wordy, bloated cast to somehow "convert" the pointer to the proper type. The point of malloc() returning a void pointer is that no such cast is needed. - Does not hardcode a size, but uses the sizeof operator to let the compiler compute it. - Does not repeat the type name, which is brittle and wordy, but instead (again) lets the compiler compute it from the target pointer. I was a bit more hesitant about this line, later in the article: return (void *)b + sizeof(block_t) + b->size; Not sure what language standard is targeted by the code in the article, but being able to do pointer arithmetic with void pointers is a GCC extension which at least should be mentioned.

senkora 3y ago
For context, the reason why you often see explicit casts from void* to other pointer types is that C++ forbids implicit casts from void*, which is one of the few compatibility breaks that C++ did with C. (For better or for worse, people often compile C-style code with a C++ compiler)
- flohofwoe 3y ago
  > which is one of the few compatibility breaks that C++ did with C It's not "few" though, it's "quite a lot". C and C++ semantics are so different that you'll have to write in a specific "common C/C++ subset" for code that should compile both in C and C++ mode. For all the flak that Objective-C usually gets by both C and C++ people it did one thing right: it respects C as a proper subset instead of creating its own bastard-fork like C++ did and then freezing it in the mid-90s.
- unwind 3y ago
  I know, that's why I wrote that the code looked like it was written by someone who wanted to write in C (as opposed to someone who wanted to write in C++, a different language).

astrange 3y ago

Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.

masklinn 3y ago
Also unfortunate are the use of a heap segment representation, and sbrk.
- matheusmoreira 3y ago
  I understand why the use of sbrk is unfortunate but what's wrong with the representation? Are there better ones?
  - masklinn 3y ago
    The heap growing towards the stack is a property of the heap segment (used by brk/sbrk). mmap is not bound to this model, and unless used with MAP_FIXED can associate the allocation with virtual addresses anywhere in the address space.
Karellen 3y ago
If you're writing your own malloc(), you could argue you are legitimately part of the system implementation. Those type names are reserved for you.
flohofwoe 3y ago
C and POSIX are different things though. The only reason why POSIX reserves _t is to avoid potential name collisions, but POSIX moves so slowly that such collisions are rarely a problem (and on any non-UNIX system it's a non-issue anyway). I *would* have used a prefix for namespacing though, e.g. not `block_t` but `prefix_block_t`.
acuozzo 3y ago
Do you know if any of the popular static analysis tools detect mistakes like this?

anonymousDan 3y ago

Is segmentation still viewed as terrible? There seems to be a trend towards hardware mechanisms for more fine-grained intra-process memory protection than is practical with paging. Nice intro though.

flohofwoe 3y ago
I'm not an expert in memory allocation strategies, but AFAIK fragmentation can still be a problem with a naive allocator that doesn't group small allocations (less than a page size) into buckets. You won't run out of virtual address space (as was the case with 32-bit processes on computers with much more than 4 GB physical memory), but you may run out of physical memory if the allocator is "blocking" a whole memory page from being recycled because there's a tiny live allocation in it.
- mort96 3y ago
  Segmentation isn't fragmentation. "Segmentation" is when you have a machine with 16 bit machine words, which would usually mean you can only address up to 2^16 = 65536 bytes of memory, but you want to support up to 1 MiB of RAM so you add a segment register and read all memory reads as relative to (segment register << 4) so that you support up to 20 bit memory addresses. (The details differ of course, but this is how Intel did it.) This results in a split between "near pointers" and "far pointers". "Near pointers" are pointers which are 16 bit and assumed to be relative to the "current segment", and can thus be dereferenced directly with any memory load instruction. "Far pointers" are 32 bit and carry a segment part and a relative part, and to dereference it, you must first write the segment part to the segment register, then do the memory load instruction with the relative part, and then you probably wanna clean up after yourself by restoring the segment register to its old state. There were multiple segment registers too, one used for data ("heap") memory operations, one for stack memory operations, one for reading machine code, and some extra segments for convenience. You had to remember which of the segment registers your near pointer was supposed to be relative to. If this all sounds very tedious... well, it was, and that's why, yes, segmentation is still viewed as terrible :) (I wasn't around back when this was common, but I did write some 16-bit real mode code for a bootloader for an OS course once, and I have designed and implemented some toy 8 bit CPUs which used segmentation to have more than 256 bytes of RAM, so I do have some experience with it)

matheusmoreira 3y ago

Could have used an article like this when I was implementing my own allocator! This is great. The Wilson1995 paper referenced is also quite useful. The algorithm I implemented is very similar to the one implemented in this article: start with a huge block of free memory; split it into multiple blocks on allocation; merge with free neighbors on deallocation. Merging blocks is the reason why doubly linked lists are needed. It worked well enough so I didn't make it a priority to organize the free lists by size. I really should implement that already but there are so many other things to do... It's also important to discuss the fact that implementing a memory allocator in C essentially requires undefined behavior. Arithmetic will be done with arbitrary pointers and the result will be cast to structures. Compiling with strict aliasing turned off is essentially a must. Others have described to me "pointer laundering" techniques where they pass the pointer through some inline assembly just to prevent the optimizer from making incorrect assumptions. Just turning off strict aliasing seems like a better idea. It's a stupid feature anyway. If you're writing C, you're probably aliasing pointers and reinterpreting memory and the last thing you need is the compiler getting clever about it. Alignment was pretty difficult to wrap my head around at first, especially the universal alignment concept. It also illustrates one of the limitations of C's malloc interface: > malloc() can simply return maximally-aligned pointers in order to accommodate any data type This wastes quite a lot of memory when the maximum alignment is not necessary... It should also be possible to segregate free lists by alignment, right? Seems like alignment should be a parameter of the memory allocation function. This article is also really great: https://nullprogram.com/blog/2023/12/17/ https://nullprogram.com/blog/2023/12/17/ https://news.ycombinator.com/item?id=38675379 https://news.ycombinator.com/item?id=38675379 Explores the idea of breaking away from C's legacy memory allocation interfaces. If you're like me and enjoy the idea of reinventing things from scratch, it's a great read. Also linked from its HN discussion: https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...

saagarjha 3y ago

> This means that the largest alignment requirement of any basic type (max_align_t in C++, usually 4 bytes for 32-bit architectures and 8 bytes for 64-bit architectures) is suitable for every single type in the language. Usually alignment is a bit larger, to accommodate SSE etc. which requires larger alignment.