Re: [TUHS] Memory management in Dennis Ritchie's C Compiler

On Mon, Aug 17, 2020 at 4:16 PM Dibyendu Majumdar <mobile(a)majumdar.org.uk> wrote: No, that's not true; or at least it's only partially true. Note that I'm talking specifically about 10th Edition here. The compiler is implemented as several cooperating processes, some of which employ different memory management strategies. Notice, for example, that `ccom` uses `malloc` but not `sbrk`, while `c2` does the opposite and uses `sbrk` but not `malloc`. On the other hand, `cpp` does no dynamic memory allocation and instead has fixed-size symbol tables for preprocessor definitions etc. Finally, the assembler uses `sbrk` but `ld` uses `malloc`. So in a nutshell, `sbrk` works by setting the "break" pointer: that is, the highest usable virtual address in the process's data segment. Stacks may be at the top of the user portion of the address space; but I'd have to double check the details. When the process starts up and gets going, one can discover the initial value of that pointer by executing `sbrk(0)`: since `sbrk` takes a delta and returns the old value of the break, the return value will be (basically) the current end of the data segment. By manipulating the break pointer via `sbrk`, one can cause the kernel to allocate memory to a process. That memory can then be managed internally (that is, within the process) via e.g. malloc _or_ a hand-rolled allocator (e.g., a "bump" allocator): when you want to put something in memory, you know where the next available pointer is (after the last one you allocated), you know how much space is available on the heap (since you allocated it using `sbrk`) and you presumably know how big the thing you want to store is; if the current pointer + alignment + size of next object is > break, you allocate more memory using `sbrk` and continue. There are a couple of approaches you can take to modernize this. The first you've already discovered: preallocate a heap that you manage with a stub `sbrk` and be done with it. Another might be to try and find some otherwise unallocated region of the address space and using `mmap()` to allocate successive pages to that portion of the address space to simulate `sbrk`; this may fail if you run into something that's already allocated in one of those regions. The most robust way might be the hardest, which is to replace the `sbrk`-based allocator with calls to e.g. `malloc`. However, looking a little more closely at 10th Ed's `c2`, for example`, this doesn't seem like it would be all that bad: `sbrk` is mostly wrapped by a function called `alloc` that takes an integer number of bytes to allocate and returns a `struct node *`; the return value is cast to whatever type is needed though. The use of `struct node *` as the return value is almost certainly because the compiler was written before `void *` had achieved primacy in the ANSI C world. Anyway, I suspect if you simply replaced the guts of `alloc` with `return malloc(an);` you'd get approximately what you want. Memory can be used for declarations, trees (for expressions) and Not exactly. The return type of `alloc` is `struct node *`, but that's just a detail; in the dialect of C that e.g. 10th Ed's PCC is written in, the return type doesn't matter: it's just a pointer. You can cast it to `char *` and copy string data there if you want to. I don't know why `struct node *` was chosen for `alloc`, but I suspect simply convenience. It seems that tree memory is allocated in a stack discipline. But what This sounds like it's something independent of the allocator and more about the program's strategy around allocation in general. It's a common trick in C programs to e.g., allocate the space for some structs plus things that may be pointed to by those structs in a single allocation; not only does this cut down on overhead with respect to calling into the allocator, it also gives you locality. I don't think you want separate _heaps_ for the things you mention, though you may want to allocate them separately using independent calls to e.g. `malloc`. That's fine. I guess no one really dug into this code - as presumably once PCC came 10th Edition `cc` _is_ `pcc`. I haven't looked at the 7th Ed compiler in detail. - Dan C.