Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!rphroy!caen!uwm.edu!ux1.cso.uiuc.edu!uxa.cso.uiuc.edu!ml27192
From: ml27192@uxa.cso.uiuc.edu (Mark Lanett)
Newsgroups: comp.lang.c++
Subject: Re: fragmentation of free store
Keywords: free store, new, delete
Message-ID: <1991Apr5.203340.13766@ux1.cso.uiuc.edu>
Date: 5 Apr 91 20:33:40 GMT
References: <285@paradim.UUCP> <1986@godzilla.tcs.com> <1398@glinda.ctron.com>
Sender: usenet@ux1.cso.uiuc.edu (News)
Organization: University of Illinois at Urbana
Lines: 47

smith@glinda.ctron.com (Larry Smith) writes:

[frag problem deleted]

>More modern systems use double-indirection to solve this problem.  Basically,
>the memory manager keeps a list of master pointers and only gives out pointers
>(in most cases, actually indexes) to these master pointers.  When the blocks
>are moved, the master pointers are updated, and, since the master pointers
>don't move, the program's pointers remain valid.  This scheme is no end of
>useful - you can, for example, augment each master pointer with a count.  You
>increment the count each time the master pointer is allocated.  When an
>actual pointer is assigned it gets a copy of this count and each time it is
>dereferenced the counts are checked.  If they don't match - BAM! - dangling
>pointer, the program is trying to reference freed (and maybe *reallocated*)
>memory.

>There are lots of other things you can do with this type of scheme, but I won't
>go into them now.  Sadly, few compilers use this mechanism to implement
>pointers.  C, C++, Pascal, etc all implement pointers as bare addresses.  Of
>course, you can implement the above scheme yourself in C, etc, but then you'll
>have to dereference twice whereever the pointer is used.  This is why you'll
>always see things like "WindowRecord^^.HorizSize" in Macintosh Pascal code -
>the Mac's menu manager does this, but the compiler is unaware of it.  Result:
>ugly code.

>It will be a great advance for the poor overworked programmers of the world
>when all compilers understand double-indirection schemes like this.  Until
>then references to free memory or an over-fragmented heap will continue to
>blow us out of the water - or force us to write code like the Mac's.

In fact, Apple's Object Pascal uses "handles" (their term for pointers to
master pointers) when dealing with objects. You say FooClass.fieldOrMember,
which then leads to an automatic double-indirection. The system gets to
move things around, and for the most part it's one happy system. To make
things even better, when you enter an object it's automatically locked so
any memory allocation you do inside the object doesn't cause it to get moved
around. Apple's version of CFront gives you these handle-based objects so
you can use them in C++ also, tho' you give up multiple inheritance (no great
loss -- yet). In C++ the class does the second dereferencing automatically so
you never see it. In both cases you may not allocate such an object on the heap.

>Larry Smith
>smith@ctron.com

--
//-----------------------------------------------------------------------------
Mark Lanett						ml27192@uxa.cs.uiuc.edu