In a personal project I need a low-level memory allocator and as I
don't know how one works and need to read Knuth 6 times to begin
to misunderstand it, I decided to learn how the allocator I use
every day works: OpenBSDs malloc.
To do this means reading the code and making notes describing what
I understand is happening. As I've been doing a lot of programming
recently using Knuth's Literate Programming technique I decided I'd
make those notes while also converting it to Literate C.
I decided to upload the first draft of this file in case it interests
anybody (or if anybody wants to help improve the text!) The files
are too big to send out on the mailing list at 85 and 442 KB each
so I pushed them to the interweb.
http://zeus.jtan.com/~chohag/malloc.w
http://zeus.jtan.com/~chohag/malloc.pdf
Although not the main goal, the malloc.w source file can be used
to generate a malloc.c file which works in place of the real malloc.c.
The result is almost identical except that because the contents of
malloc.c end up being in a different order the object file produced
is also ordered differently (and about 60 bytes shorter! I think
the optimiser got lucky).
To generate the pdf or C source requires CWEB, included as part of
TeXlive (which is huge). I think the package texlive_texmf-minimal-2021
is enough.
C: ctangle malloc.w
TeX (first step): cweave malloc.w
PDF (second step): pdftex malloc.tex
I plan at least one more run through this for my own understanding
as there's quite a bit that I skimmed over and cutting the code
into pieces was done quite haphazardly (not to mention with zero
understanding at the beginning) but I have no other plans for this
beyond maybe a bit of a polish, however if there's any interest
then I'm happy to put a bit of elbow grease into making this a more
coherent description of how the allocator works (including diving
into thread_private.h --- yech!) and keeping it up to date.
Finally, as I went through I noted a few improvements which could
be made as well as other questions (not all written down), eg. some
routines use u_short while others use ushort and other little things
like that. Some require a deeper dive into CVS history so I'll come
out with a comprehensive list some time over Christmas.
Cheers,
Matthew
