From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: * X-Spam-Status: No, score=1.2 required=5.0 tests=BAYES_00,FROM_WORDY, INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,184737148aef02ac X-Google-Attributes: gid103376,public From: "Nick Roberts" Subject: Re: GC+FSD for GNAT/GCC Date: 1999/02/06 Message-ID: <79hsmq$jhv$1@plug.news.pipex.net>#1/1 X-Deja-AN: 441398277 References: <78sojm$crk$1@plug.news.pipex.net> <7982p7$nll$1@plug.news.pipex.net> <87aeyv4kbg.fsf@mihalis.ix.netcom.com> <79asc3$cq3$1@nnrp1.dejanews.com> <79enud$lvc$2@plug.news.pipex.net> X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3 Organization: UUNET WorldCom server (post doesn't reflect views of UUNET WorldCom) Newsgroups: comp.lang.ada Date: 1999-02-06T00:00:00+00:00 List-Id: Andi Kleen wrote in message ... [...] |I wonder how hard it would be to put a "malloc()" plugin compatible conservative |GC like the Boehm GC into the GNAT run time library. As far as I can see |GNAT uses a wrapper around the C Library's malloc function for its memory |allocation needs. What would happen if I linked it with a GC malloc library? This strategy alone couldn't perform heap compaction - I'm going to call it 'free space defragmentation' (FSD) from now on (if nobody minds) - only GC, and even then there are better ways (I think) of providing the GC. Without FSD, however, you inevitably get creeping fragmentation (unless all blocks allocated in the pool are the same size). I doubt that a GC scheme which does not deal with fragmentation is of much value, in reality, but I would welcome comments on this. One kind of 'mark-sweep' scheme I am envisioning at this stage has the following broad design. The compiler (I'm not sure whether the front or back end) generates a piece of constant data which encodes the locations of all access objects within each record and array type, and of all access objects, and access component-containing records and arrays, within each stack-frame. This data is called the 'crib'. The pool type's implementation can then use this crib to 'sweep' over all access objects (including all those in the pool itself), 'marking' all allocated objects which are still accessed (thus finding out all which are not accessed, so performing GC), and then to sweep again, adjusting the access values (or their data-pointers) as required (as a part of FSD). Finally, the extant objects are shuffled into their new positions (completing the FSD). This is a non-locking scheme. The user (Ada programmer) must ensure that the execution of a block which contains code that uses a pool (managed by this scheme) in one task will never overlap with the execution of a block which contains code that uses the same pool in another task. (If this cannot be arranged, a locking scheme must be selected instead.) The most common case will be where the pool is only ever used in one task (indeed, frequently in a program which only has one task). The compiler must generate code such that: no access object is in a temporary location whenever an allocator or deallocator (of a managed pool) is called; for every access object whose value is put into a temporary location within a certain block, the value is written back into the non-temporary location before the end of that block. There are some details of this scheme I haven't quite sorted out yet (it's quite complicated), but nothing major (with luck). It is important to realise that this is just one scheme (albeit the most important one, I think). I believe a variety of schemes - locking/non-locking, mark-sweep/reference counter, crib-reiteration/double-indirection/ring-of-pointers - will have to be supplied. Comments? ------------------------------------------- Nick Roberts ------------------------------------------- PS: I think the __GNAT_malloc() and __GNAT_free() routines would remain unchanged, the entire GC+FSD stuff being managed at a higher level.