Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!glinda!smith
From: smith@glinda.ctron.com (Larry Smith)
Newsgroups: comp.lang.c++
Subject: Re: fragmentation of free store
Keywords: free store, new, delete
Message-ID: <1398@glinda.ctron.com>
Date: 4 Apr 91 18:44:43 GMT
References: <285@paradim.UUCP> <1986@godzilla.tcs.com>
Organization: Cabletron Systems Inc.  Rochester, NH
Lines: 48

In article <1986@godzilla.tcs.com> gwu@nujoizey.tcs.com (George Wu) writes:
>In article <285@paradim.UUCP>, jean@paradim.UUCP (Jean Pierre LeJacq) writes:
>|> The free store memory managment system can coalesce
>|> deleted memory to form larger blocks.  However, it
>|> does not appear possible to defragment this memory
>|> due to direct references to free store memory.
>
>     Am I dated, here?  Jean Pierre's article seems to indicate there is
>an implemented solution to memory fragmentation, but for some reason I don't
>understand, this solution is not wholey effective.  Anyways, the remainder
>of this message is based upon the assumption that no one has yet bothered
>to implement a way to coalesce multiple memory fragments into a larger
>single chunk of memory.

Actually, I believe the problem is due to the fact that *currently allocated*
chunks of memory are fragging the free space, and there is nothing that can
be done about this.  The only fix is to move the allocated blocks around
until they are all contiguous, and if you move them the zillions of pointers
imbedded in the data structures on the stack and in the heap will be wrong.

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.

Larry Smith
smith@ctron.com