Heap fragmentation (2nd attempt)

Hi Groups,
unfortunately I am still trying to write a sample code that badly
fragments the heap and measure the time it take to allocate memory.
But this heap does not fragment, ant the time to allocate memory does not
increase. I don't know why. I tried different orders of malloc() free()
but I can't measure any runtime differences. In contrary, the first
mallocs on an unused heap take longer and later after some 1000
malloc/free actions the time used stabilizes on a lower value.
if I then after some time free all my allocated objects and then start
reallocating, time goes up for the first 1000 allocs and drops to the old
value. I don't know why.
either I am measureing the wrong stuff or the heap in linux 2.6 with glibc
does not fragment for any obscure reason.....

Can anyone tell me where the flaw in my model is?

below is the whole application code (tabsize 4), some parts are commented
out for testing diffent patterns. please play around a bit and tell me
what is wrong - if you can show fragmentation in any combination of
free()/malloc() runs please tell me how!

if the code is badly formatted you can download it at
http://www.ruschival.de/stuff/uni/heapfrag.c

Code follows: compile gcc -Wall -o heapfrag heapfrag.c

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <sys/time.h>

#define VARSIZE

/* number of objects to be created */
#ifndef NO_HEAPOBJS
#define NO_HEAPOBJS 500000
#endif
/* maximum size of each object in Byte */
#ifndef MAX_OBJSIZE
#define MAX_OBJSIZE 1021 // nice primenumber
#endif
/* how many objects should be allocated per cycle */
#ifndef OBJS_PER_CYCLE
#define OBJS_PER_CYCLE NO_HEAPOBJS/10
#endif

/** Types used */

/* redeclare size_t do be compliant with IAS coding guidelines */
typedef size_t Tsize;

/* Struct to keep track of allocations and pointers to memory returned by
malloc() */ typedef struct memchunk{
unsigned int allocated;
unsigned int size;
void* memory;
} Tmemchunk;



/* Testprogram to allocate and deallocate memory randomly to fragment the
heap */ /* measures the time used to allocate OBJS_PER_CYCLE on the heap
*/ int main(int argc, char** argv){
int i=0,j=0; // generic counter
variable Tsize size=MAX_OBJSIZE/2; // size of new memory chunk to
allocate Tmemchunk objs[NO_HEAPOBJS]; // array to keep pointers to memory
chunks


/* Variables for statistics */
struct timeval programstart;// timestamp for total runtime of
program struct timeval starttime; // timestamp before
allocation struct timeval stoptime; // timestamp after allocation
of objects double delta; // time elapsed
for malloc() double runtime; // total
program runtime long cycle = 0; // counter
for cycles long objs_allocated=0; // track how many objects
crrently allocated long alloc_actions=0; // count malloc()
operations long free_actions=0; // count free() operations
Tsize total_size=0; // track bytes
allocated; char *filename = "timings.dat";

/* write pointer for test results */
FILE *fp;

// initialize all heap objects as free
for(i=0; i< NO_HEAPOBJS ; i++){
objs[i].allocated = 0;
objs[i].size = 0;
objs[i].memory = NULL;
}

//open target file
fp = fopen(filename,"w");
if(fp == NULL){
printf("failed opening file\n");
exit(1);
}

/* start timing */
gettimeofday(&programstart,NULL);

/* printf("Allocating %d objects on the heap for initial usage
\n",NO_HEAPOBJS/2); */ /* // start timer */
/* gettimeofday(&starttime,NULL); */
/* /\* Initially fill the heap to 50% *\/ */
/* for(i=0; i< NO_HEAPOBJS/2 ; i++){ */
/* #ifdef VARSIZE */
/* size = (Tsize)(random() % MAX_OBJSIZE); // random size
*/ /* #endif */
/* if( ( objs[i].memory= malloc(size)) !=
NULL ){ */ /* objs[i].allocated = 1; */
/* objs[i].size = size; */
/* total_size+=size; */
/* alloc_actions++; */
/* } */
/* else{ */
/* printf("malloc() failed! \n"); */
/* objs_allocated= alloc_actions-free_actions; */
/* printf("alloc actions %ld objs_allocated:
%ld total_size: %d \n",alloc_actions, objs_allocated,total_size); */ /*
exit(1); */ /* } */
/* } */
/* //stop timer */
/* gettimeofday(&stoptime,NULL); */
/* // Timing calculations */
/* delta = (stoptime.tv_sec - starttime.tv_sec); */
/* delta += (stoptime.tv_usec -
starttime.tv_usec)/(double)1000000; */ /* runtime = (stoptime.tv_sec
- programstart.tv_sec); */ /* runtime += (stoptime.tv_usec -
programstart.tv_usec)/(double)1000000; */ /* objs_allocated=
alloc_actions-free_actions; */ /* // printf("allocs \tfrees
\tobjs \tsize \t\tdelta[s] \truntime[s] \tcycle\n"); */ /*
fprintf(fp,"%ld \t%ld \t%ld \t%d \t%lf \t%lf
\t%ld\n",alloc_actions,free_actions, objs_allocated, */ /*
total_size,delta,runtime,cycle); */


printf("Starting infinite run\n");
/* heap fragmenst so quickly 100 runs are more than enough*/
while(cycle < 1000){
cycle++;
alloc_actions=0;
free_actions=0;
// if too many objects allocated -> free some space
/* if(objs_allocated >= (NO_HEAPOBJS-OBJS_PER_CYCLE)){ */
/* // free randomly twice the memory we allocate
in a cycle */ /* for(i=0; i<(OBJS_PER_CYCLE);
i++){ */ /* // randomly pick allocated
space */ /* do{ */
/* j = random()%NO_HEAPOBJS; */
/* }while(objs[j].allocated == 0); */
/* // piece of memory found --> deallocate
*/ /* objs[j].allocated = 0; */
/* total_size -= objs[j].size; */
/* free(objs[j].memory); */
/* objs_allocated--; */
/* // printf("freeing memory \n"); */
/* } // end deallocation for */
/* }// end if not enough space left */

// start timer
gettimeofday(&starttime,NULL);
for(i=0; i<OBJS_PER_CYCLE; i++){
#ifdef VARSIZE
size = (Tsize)(random() % MAX_OBJSIZE); // random
size #endif
j = random()%NO_HEAPOBJS; // pick random
index if( objs[j].allocated == 1 ){ // if allocated -> free
// only every 2nd attempt we actually free
memory. // if( random()%2 == 0){
objs[j].allocated = 0;
total_size -= objs[j].size;
free(objs[j].memory);
free_actions++;
objs_allocated--;
// }
/* else{ // reallocate -> time goes up
because mem is copied */ /* objs[j].memory =
realloc(objs[j].memory,size); */ /*
total_size -= objs[j].size; */ /* total_size+=size; */
/* objs[j].size = size; */
/* } */
}
// else{ // try to allocate
if( (objs[j].memory = malloc(size)) !=
NULL ){ objs[j].allocated = 1;
objs[j].size = size;
total_size+=size;
objs_allocated++;
alloc_actions++;
}
else{
printf("malloc() failed! \n");
objs_allocated= alloc_actions-free_actions;
printf("alloc actions %ld objs_allocated: %ld
total_size: %d \n", alloc_actions, objs_allocated,total_size);
exit(1);
}// end if try to allocate
// }// end if allocated
}// end for
//stop timer
gettimeofday(&stoptime,NULL);
// Timing calculations
delta = (stoptime.tv_sec - starttime.tv_sec);
delta += (stoptime.tv_usec -
starttime.tv_usec)/(double)1000000; runtime = (stoptime.tv_sec -
programstart.tv_sec); runtime += (stoptime.tv_usec -
programstart.tv_usec)/(double)1000000;

fprintf(fp,"%ld \t%ld \t%ld \t%d \t%lf \t%lf
\t%ld\n",alloc_actions,free_actions, objs_allocated,
total_size,delta,runtime,cycle); // free all at once
if(objs_allocated == NO_HEAPOBJS){
for(i=0; i< NO_HEAPOBJS ; i++){
objs[i].allocated = 0;
objs[i].size = 0;
free(objs[i].memory);

}
total_size=0;
objs_allocated=0;
}
} // end infinite loop
return 0;
}
.

Relevant Pages

  • Re: Struct inside class
    ... The compiler figures computes the ... including anything derived from "Object": Heap pointer ... memory leaks and why the .NET good garbage collector is required. ... If GC_ALLOCATE can't allocate the requested ...
    (microsoft.public.dotnet.framework)
  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (comp.lang.cpp)
  • Re: Huge pages and small pages. . .
    ... >> what looks like contiguous memory and away you go. ... you need to have them cached in the TLB; if the TLB runs out of ... > low end of the heap, until someone figures out a way to tell the system ... When you allocate memory, the kernel just marks a promised ...
    (Linux-Kernel)
  • Re: Huge pages and small pages. . .
    ... Since the CPU uses virtual memory always, ... them, you need to have them cached in the TLB; if the TLB runs out of room, you invalidate entries; then when you hit entries not in the TLB, the TLB has to searhc for the page mapping in the PTE chain. ... When you allocate memory, the kernel just marks a promised ... They will stay forever allocated until the highest pages of the heap are unused by the program, in which case the heap manager brks down the heap and frees them to the system. ...
    (Linux-Kernel)