Re: Heap fragmentation (2nd attempt)

Hi CBFalconer,
thanks alot for more insight!

very important
http://cbfalconer.home.att.net/nmalloc.zip
doesn't work --> 404 No such file!

C> To start with, your code does not survive transmission as a usenet
C> article because lines are overlong (should be limited to about 65
C> chars) and it uses // comments.
Sorry, I thought 80 chars is standard but as I posted I saw the mess.

C> It also usesnon-standard headers, such as <sys/time.h>, which are
C> unknown quantities to most readers here.
I didn't know this wither I have currently no access to other
operating systems. I only have Linux and Cygwin on windows (which can't
use the microseconds from timeval because of the bad clock granularity.

C> Secondly, heap fragmentation depends on the malloc package much
C> more than the sequence of calls. A good package will be relatively
C> impervious to the call sequence. The place you should be looking
C> is the source code to your own malloc package.
Thanks for the hint on the malloc source.
In University I learnt and understood that regardless the allocation
scheme the will be fragmentation of the heap using random sizes in
allocation. I can only avoid it completetly with several heaps that have
constant blocksizes. or a GC that does compactification once in a while.
At my current knowledge I think the heap is a simple list whose elements
look like
struct memchunk{
struct memchunk next;
unsigned int size;
}
followed by size words of data.
And every time malloc is called it follows the list until
(size-sizeof(memchunk)) >= required size form malloc()
therefore it inevitably collects many very small chunks at the beginning
of the list. If it doesn't find a machting chunk of memory it requests
a new memory location from the OS.

C> One of the biggest delays in many packages is the O(N*N) timing of
C> the free operation, where N is the number of blocks assigned. This
Why is free O(N*N) isn't it just simply adding the freed chunk at the end
of the list?
C> can be reduced to O(N) by making the actual free O(1).
is this what you are talking about?

C> <http://cbfalconer.home.att.net/nmalloc.zip>
sorry link is broken!

.

Relevant Pages

  • [NT] Apple Quicktime FLIC File Heap Overflow (Technical Details)
    ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... Apple Quicktime FLIC File Heap Overflow ... "COLOR_64 chunk" Quicktime parser. ... text:679FE4DA mov eax, ...
    (Securiteam)
  • Re: Why are variables stored on the stack?
    ... the stack than the heap is spurious - if I recall, ... A stack is Oto allocate a chunk, ...
    (comp.lang.c)
  • classes, pointers, vectors, and memory allocation
    ... ptr1 and ptr2 will be dynamically allocated in the heap, ... does A's memory get enlarged as a whole chunk? ... is not enough space for the whole chunk, will A get copied into another ...
    (comp.lang.cpp)
  • Re: GC in Jons raytracing benchmark
    ... Because if it does, then my limited-latency calculations, which depended on malloc and free taking time logarithmic to the number of items on the heap, are out the window and I need to redesign. ... data of the chunk you're freeing, probably coalesces it with the two neighboring chunks into one bigger chunk, puts it on the right free-list or whatever and then returns. ...
    (comp.lang.lisp)