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.
Visual overview of a custom malloc() implementation
11–20 of 31 posts
Re: Visual overview of a custom malloc() implementation
#12This 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 poin…
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)
> 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.
Re: Visual overview of a custom malloc() implementation
#13Is 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.
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.
Re: Visual overview of a custom malloc() implementation
#14Unfortunately 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.
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`.
Re: Visual overview of a custom malloc() implementation
#15This 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 poin…
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)
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).
Re: Visual overview of a custom malloc() implementation
#16Could 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://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/6b08643335388bbab0228db763f9921...
Re: Visual overview of a custom malloc() implementation
#17Unfortunately 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.
Do you know if any of the popular static analysis tools detect mistakes like this?
Re: Visual overview of a custom malloc() implementation
#18This 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 poin…
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)
Does anyone know, why does C++ forbid implicit casts from void*?
Re: Visual overview of a custom malloc() implementation
#19Why are the letters ’p’, ’q’ and ’t’ missing from the article? Makes it a bit annoying to read.
I don't see `r`s. Firefox/Mac
Re: Visual overview of a custom malloc() implementation
#20Earlier quoted context omitted.
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)
Does anyone know, why does C++ forbid implicit casts from void*?
C++ tries to have a slightly stricter type system than C. The compiler can't check anything when you cast from void*, and since C++ has other mechanisms which usually make casts from void* unnecessary (such as using 'new' instead of 'malloc' for heap allocation), I think it makes sense to require casts from void* to be explicit.