17 Aug
2020
17 Aug
'20
2:02 a.m.
From: Dibyendu Majumdar
the C compiler from V7/V10. I wanted to check if
anyone here knows
about the memory management in the compiler (c0 only for now). I am
trying to migrate the memory management to malloc/free but I am
struggling to understand exactly how memory is being managed.
Well, I don't know much about the V7 compiler; the V6 one, which I have looked
at, doesn't (except for the optimizer, C2) use allocated memory at all.
The V7 compiler seems to use sbrk() (the system call to manage the location of
the end of a process' data space), and manage the additional data space
'manually'; it does not seem to use a true generic heap. See gblock() in
c01.c:
https://minnie.tuhs.org//cgi-bin/utree.pl?file=V7/usr/src/cmd/c/c01.c
which seems to use two static variables (curbase and coremax) to manage
that additional memory:
p = curbase;
if ((curbase =+ n) >= coremax) {
if (sbrk(1024) == -1) {
error("Out of space");
exit(1);
}
coremax =+ 1024;
}
return(p);
My guess is that there's no 'free' at all; each C source file is processed
by a new invocation of C0, and the old 'heap' is thrown away when the
process exits when it gets to the EOF.
Noel
17 Aug
17 Aug
6:02 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
On 8/16/20, Noel Chiappa <jnc(a)mercury.lcs.mit.edu> wrote:
The V7 compiler seems to use sbrk() (the system call to manage the location of
the end of a process' data space), and manage the additional data space
'manually'; it does not seem to use a true generic heap. See gblock() in
c01.c:
This is very common in compilers. Both the DEC/Compaq and Intel
compilers manage heap memory this way. Each particular phase or pass
of a compiler tends to build its on set of data structures in heap,
and then free the whole mess when the phase/pass is done. malloc/free
doesn't fit the model very well because you have to free each
structure individually, and for more persistent structures you don't
get very good locality of reference. What works better is to use a
multitude of mini-heaps that can be freed up all in one go.
-Paul W.
6:13 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
You beat me to my response. malloc/free are great for long running
processes where memory can't just infinitely increase, but there's a ton of
stuff in a compiler -- types, expressions, symbols -- that survives until
the process exits. There's benefit in both space (because you don't have to
add headers to the blocks as malloc() does, so free() can work) and time to
doing it this way.
On Mon, Aug 17, 2020 at 2:03 PM Paul Winalski <paul.winalski(a)gmail.com>
wrote:
On 8/16/20, Noel Chiappa
<jnc(a)mercury.lcs.mit.edu> wrote:
The V7 compiler seems to use sbrk() (the system call to manage the
location of
the end of a process' data space), and
manage the additional data space
'manually'; it does not seem to use a true generic heap. See gblock() in
c01.c:
This is very common in compilers. Both the DEC/Compaq and Intel
compilers manage heap memory this way. Each particular phase or pass
of a compiler tends to build its on set of data structures in heap,
and then free the whole mess when the phase/pass is done. malloc/free
doesn't fit the model very well because you have to free each
structure individually, and for more persistent structures you don't
get very good locality of reference. What works better is to use a
multitude of mini-heaps that can be freed up all in one go.
-Paul W.
6:48 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
On 8/17/20, Jim Geist <velocityboy(a)gmail.com> wrote:
You beat me to my response. malloc/free are great for
long running
processes where memory can't just infinitely increase, but there's a ton of
stuff in a compiler -- types, expressions, symbols -- that survives until
the process exits. There's benefit in both space (because you don't have to
add headers to the blocks as malloc() does, so free() can work) and time to
doing it this way.
The other issue is locality of reference. Data structures such as the
symbol table get built up gradually as the compilation processes each
routine. Typically the symbol table is stored as a hash table where
each entry is a pointer to the actual symbol table entry data
structure. If you malloc() each symbol table entry individually, they
can end up scattered all over the virtual address space. It's not as
important these days, when main memory is measured in gigabytes, but
back when machines had less real memory, the scattering could lead to
excessive page faulting. Much better to allocate symbol table entries
in chunks, and the easiest way to do that is to give the symbol table
its own mini-heap.
VMS implemented the mini-heap concept (VMS calls them zones) back in
its first release in 1978. Dave Cutler took the concept to Windows NT
(Microsoft calls them private heaps). Lots of applications have built
their own mini-heap system on top of sbrk(), but has a library of
mini-heap-type APIs ever been distributed on Unix?
-Paul W.
7:08 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
When did mmap(2) come about? Another thing I've seen is building a small
block allocator on top of that. You can guarantee that all your objects are
nicely collected into the same set of pages for locality with very little
overhead.
On Mon, Aug 17, 2020 at 2:48 PM Paul Winalski <paul.winalski(a)gmail.com>
wrote:
On 8/17/20, Jim Geist <velocityboy(a)gmail.com>
wrote:
You beat me to my response. malloc/free are great
for long running
processes where memory can't just infinitely increase, but there's a ton
of
stuff in a compiler -- types, expressions,
symbols -- that survives until
the process exits. There's benefit in both space (because you don't have
to
add headers to the blocks as malloc() does, so
free() can work) and time
to
doing it this way.
The other issue is locality of reference. Data structures such as the
symbol table get built up gradually as the compilation processes each
routine. Typically the symbol table is stored as a hash table where
each entry is a pointer to the actual symbol table entry data
structure. If you malloc() each symbol table entry individually, they
can end up scattered all over the virtual address space. It's not as
important these days, when main memory is measured in gigabytes, but
back when machines had less real memory, the scattering could lead to
excessive page faulting. Much better to allocate symbol table entries
in chunks, and the easiest way to do that is to give the symbol table
its own mini-heap.
VMS implemented the mini-heap concept (VMS calls them zones) back in
its first release in 1978. Dave Cutler took the concept to Windows NT
(Microsoft calls them private heaps). Lots of applications have built
their own mini-heap system on top of sbrk(), but has a library of
mini-heap-type APIs ever been distributed on Unix?
-Paul W.
7:28 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
On 8/17/20, Jim Geist <velocityboy(a)gmail.com> wrote:
When did mmap(2) come about? Another thing I've
seen is building a small
block allocator on top of that. You can guarantee that all your objects are
nicely collected into the same set of pages for locality with very little
overhead.
mmap(2) certainly can be used to allocate blocks for the mini-heap
itself, but you still have to write your own equivalents of malloc()
and free() to allocate data structures within the mini-heap. The nice
thing about VMS heap zones and Microsoft's private heaps is that you
get the malloc()/free() layer off-the-shelf; you don't have to roll
your own.
-Paul W.
7:35 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
True, but zones and HeapAlloc do a fair bit of work to handle objects of
multiple sizes. If you're partitioning up a page and you know every object
on the page is 8 or 16 or 48 bytes, it's MUCH simpler. And a lot of the
data structures in a compiler tend to be small-tens-of-bytes nodes.
On Mon, Aug 17, 2020 at 3:28 PM Paul Winalski <paul.winalski(a)gmail.com>
wrote:
On 8/17/20, Jim Geist <velocityboy(a)gmail.com>
wrote:
When did mmap(2) come about? Another thing
I've seen is building a small
block allocator on top of that. You can guarantee that all your objects
are
nicely collected into the same set of pages for
locality with very little
overhead.
mmap(2) certainly can be used to allocate blocks for the mini-heap
itself, but you still have to write your own equivalents of malloc()
and free() to allocate data structures within the mini-heap. The nice
thing about VMS heap zones and Microsoft's private heaps is that you
get the malloc()/free() layer off-the-shelf; you don't have to roll
your own.
-Paul W.
7:41 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
Apache has the "pool" concept, per-request storage; there are a few
versions:
https://commons.apache.org/proper/commons-pool/ (java)
http://www.apachetutor.org/dev/pools (C server)
11:40 p.m.
New subject: Memory management in Dennis Ritchie's C Compiler
Richard Salz wrote in
<CAFH29tpbNrUKVP2hp25wdu9BYCxQr+RrmcWJ8F+SbtwsGE4VKw(a)mail.gmail.com>om>:
|Apache has the "pool" concept, per-request storage; there are a few
And BSD Mail had the "stringdope" of Kurt Shoens from the very
start in 1978. It serves allocations of various size until reset
time. (Different to the Apache thing it does not support
destructor calls -- if i recall the Apache stuff, i have looked
into that two decades ago.)
I personally had objects caches and fluctuating object caches
backed by generic C types
pub GOCache(uir _objsz, uir _growby=8-1);
...
pub uir count(void) const { return(m_count); }
pub void *alloc(void);
pub GOCache &free(void *_ptr);
pub GOCache &clear(void);
pub GOCache &swap(GOCache &_t);
and used via all-inline template wrappers
template<class T> class OCache : private GOCache{
...
OCache(uir _growby=8-1) : Super(szof(T), _growby) {}
...
pub T *newObject(void) { return(SF_newHeap(T, Super::alloc())); }
pub OCache &delObject(T *_tptr){
_AssertRetThis(_tptr != NIL);
_tptr->~T();
return(s(Me&,Super::free(_tptr)));
}
...
The difference was that the normal could not free individual
chunks, the other could
pri union Atom{
Chunk *owner; // used
Atom *next; // free
}SF_CC_PACKED;
pri struct Chunk{
Chunk *right;
Atom *free; // freelist
ui1 *top; // cast point or NIL if full
uir count; // user pointers this Chunk
}SF_CC_PACKED;
vs
pri struct Atom{
Atom *next;
}SF_CC_PACKED;
pri struct Chunk{
Chunk *right;
ui1 *top; // cast point or NIL if full
}SF_CC_PACKED;
(here the free Atom free list was part of the cache object).
That even worked out fine to serve nodes on hashmap and list
objects, in practice.
|versions:
| https://commons.apache.org/proper/commons-pool/ (java)
| http://www.apachetutor.org/dev/pools (C server)
--steffen
|
|Der Kragenbaer, The moon bear,
|der holt sich munter he cheerfully and one by one
|einen nach dem anderen runter wa.ks himself off
|(By Robert Gernhardt)
1352
days inactive
1352
days old
8 comments
5 participants
participants (5)
-
Jim Geist -
jnc＠mercury.lcs.mit.edu -
Paul Winalski -
Richard Salz -
Steffen Nurpmeso