Mail Archives: djgpp-workers/2002/05/17/12:42:17
Eli Zaretskii wrote:
>
> > Date: Thu, 16 May 2002 14:50:13 -0400
> > From: CBFalconer <cbfalconer AT yahoo DOT com>
> > >
> > > How do you overcome the problem of joining non-contiguous chunks?
> >
> > If the various sbrk calls returned something non-contiguous (the
> > unexpected returns) nothing can join those.
>
> I didn't mean memory that was non-contiguous to begin with. I meant
> memory that was returned as contiguous by sbrk, but was then
> subdivided into chunks by malloc, and became non-contiguous after
> several allocations and deallocations.
>
> > However everything in a contiguous sbrk chunk, whether created by
> > one or several sbrk calls, will be rejoined when all components are
> > freed.
>
> The problem is precisely that not everything is deallocated when you
> suddenly need a large chunk of memory. Some Lisp objects are
> short-lived, others tend to live for a long time before they die and
> are freed by the garbage collector. That's the reason for
> fragmentation.
>
> The only way to avoid the adverse effects of such fragmentation is to
> relocate memory when you don't have a contiguous block large enough to
> satisfy the request, but do have enough free memory in non-contiguous
> chunks. That's what the Emacs relocating allocator does, but that
> cannot be done in a C library.
The problem should be eased (not avoided) in nmalloc, because it
attempts to allocate from the smallest suitable free chunk.
Reallocs of current space won't help, because nmalloc tries hard
to avoid copying by attempting to extend the current block.
As the system works large blocks will tend to either be in use or
appear in large block free lists, while small blocks will either
coalesce into large blocks or be available in small block free
lists, where new small allocations will find them. I think the
tendency will be to physically separate large and small blocks.
My test sequences include long runs of random sized allocations
intermixed with frees and reallocs. IIRC those runs bear out the
above allegations.
Probably a further test sequence in tnmalloc where the
malloc/realloc/free cycle includes saving something in a growing
list, to be freed only on test run termination, would be
informative. That might simulate emacs gyrations to some extent.
>
> > nmalloc keeps track of adjacent allocations and rejoins them
> > when freed. Adjacent free blocks are always joined into one larger
> > block. It also attempts to do any new allocations from the free
> > space list on something close to best fit, and avoids sbrk calls as
> > far as possible.
>
> I think the current libc version also does that, at least within the
> bucket.
We are agreed on what can and cannot be done. The free space
allocator/tracking in nmalloc was basically taken from the
existing system. nmalloc tries harder to avoid sbrks during
realloc calls, etc.
However if something else effectively calls sbrk with a negative
value, nmalloc may later think it has a new noncontiguous block,
and may then very well allocate the same space twice!. This would
NOT be good.
It cannot be protected by insisting on monatonic increasing, since
I found that the startup code does some wierd things and leaves
things fragmented before the application starts.
--
Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT worldnet DOT att DOT net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
- Raw text -