peachslasher 0 Newbie Poster

Hi guys I am trying to implement a buddy system using C, I've free the memory using myfree() and i've allocated memory using mymalloc(). I've tried to run the program, but it keep on generating segmentation error, would you guys please see the code, and tell me if you've spotted mistakes within my code

Thanks
Amy

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <math.h>
//#include <vector.h>
// 159.335 assignment 3
// This is a working memory allocation program
// but it is slow and uses lots of memory.
// Martin Johnson 16/5/2000, 21/9/2000, 26/9/2001 & 15/5/2002

// the following is fixed by the OS
// you are not allowed to change it
#define PAGESIZE 4096
// you may want to change the following lines if your
// machine is very faster or very slow to get sensible times
// but when you submit please put them back to these values.
#define NO_OF_POINTERS 2000
#define NO_OF_ITERATIONS 2000000
// change the following lines to test the real malloc and free
#define MALLOC mymalloc
#define FREE myfree
// The following ugly stuff is to allow us to measure
// cpu time on NT. Win95/98 only lets us measure
// elapsed time so times will not be as accurate
typedef struct { unsigned long l,h; } ti;
typedef struct { unsigned long sz,ml,tp,ap,tpg,apg,tv,av; } ms;
//#ifdef __cplusplus
//extern "C" {
//#endif
//unsigned long * _stdcall VirtualAlloc(void *,unsigned long,unsigned long,unsigned long);
//int _stdcall VirtualFree(void *,unsigned long,unsigned long);
//void _stdcall GlobalMemoryStatus(ms *);
//void * _stdcall GetCurrentProcess(void);
//unsigned long _stdcall GetVersion(void);
//int _stdcall GetProcessTimes(void *, ti *,ti *, ti *, ti *);
//void _stdcall Sleep(unsigned long);
//#ifdef __cplusplus
//}
//#endif


//create the 'record' structure
//notice the third line, the same structure is included as a entry
struct record {
	int number; //size
	int allocation; //determine wheather block is allocated or not
	struct record *prev;    //allow to point to the prev entry
	struct record *next;	//this allows to point to the next entry
};

//create the 'node' type
typedef struct record node;

int SIZEOFWHOLEMEMORY= 32;

node *array_of_list[6];

node *wholememory;

int power(int a, int b){
	int i;
	if(b<=0) return 0;
	else{
	  int c =1;
	  for(i=0;i<b;i++){
		c*=a;
	 }
	return c;
	}
}

int cputime(void) { // return cpu time used by current process



}
int memory(void) { // return memory available to current process
//cat /proc/PID/statm
//14991 426 314 175 0 134 0
//In order:
//1) total process size
//2) The size of the process resident in physical memory
//3) The memory shared with other processes—that is, memory mapped both by this process and at least one other (such as shared libraries or untouched copy-on-write pages)
//4) The text size of the process—that is, the size of loaded executable code
//5) The size of shared libraries mapped into this process
//6) The memory used by this process for its stack
//7) The number of dirty pages—that is, pages of memory that have been modified by the program
  FILE* fp;
  char buffer[1024];
  int memd0;
  int memd1;
  int memd2;
  int memd3;
  int memd4;
  int memd5;
  int memd6;
  size_t bytes_read;
  /* Read the /proc/PID/statm */
  int mypid= (int) getpid ();
  char temp[100];
  sprintf(temp,"/proc/%d/statm",mypid);
  
  fp = fopen (temp, "r");
  bytes_read = fread (buffer, 1, sizeof (buffer), fp);
  fclose (fp);
  /* Bail if read failed or if buffer isn’t big enough. */
  if (bytes_read == 0 || bytes_read == sizeof (buffer))
    return 0;
  /* NUL-terminate the text. */
  buffer[bytes_read]='\0';
  //printf("BUFFER %s \n",buffer);
  /* Locate the line that starts with “cpu MHz”. */
  sscanf(buffer,"%d %d %d %d %d %d %d",&memd0,&memd1,&memd2,&memd3,&memd4,&memd5,&memd6);
  //printf(" pid %d \n",(int) getpid ());
  //char temp2[200];
  //sprintf(temp2,"cat /proc/%d/statm",mypid);
  //system (temp2);
  //printf(" MEMORY USE %d %d %d %d %d %d %d \n",memd0,memd1,memd2,memd3,memd4,memd5,memd6);
  return memd0;
}

// you are not allowed to change the following function
/*void *allocpages(int n) { // allocate n pages and return start address
//   return VirtualAlloc(0,n * PAGESIZE,4096+8192,4);
return (void *) malloc(n*PAGESIZE+1);
}

// you are not allowed to change the following function
int freepages(void *p) { // free previously allocated pages.
//   return VirtualFree(p,0,32768);
      free(p);
      return(1);//indicate true
}
*/

void *mymalloc(int req) { // very simple memory allocation
	int i,f,n;
	printf("mymalloc()!");
	node *new;	
	//if request is too big
	if(req > SIZEOFWHOLEMEMORY){
	  printf("Size: %d, System dont have enough memory", req);
	}
	//Take the first available block from array_of_list 
	 for(i=0;i<5;i++){
		if(req < array_of_list[i]->number && req > (array_of_list[i]->number/2) && array_of_list[i]->allocation==1){
			//create node then allocate it - assign it to the process
			if(array_of_list[i]->next != NULL){
			//if its not null then add extra element
								
				new =(node*)(wholememory + (int)array_of_list[i]->number); //wholememory is 0 + 32,16...2
				new->allocation = 0; //this block is on use
				new->number = req;
				new->next = NULL;
				new->prev = NULL;
				array_of_list[i]->next = new;
				break;
			//if its null and its the first element then allocate it
			}else if(i=0){
				//if this is the first list then allocate it	
				new =(node*)(wholememory + (int)array_of_list[i]->number); //wholememory is 0 + 32,16...2
				new->allocation = 0; //this block is on use
				new->number = req;
				new->next = NULL;
				new->prev = NULL;
				break;
			 	}else{
				//if this is not the first one on the list then:
					//make sure the list before the list before this is null
					if(array_of_list[i-1]->next==NULL){
						//then we have to devide the memory
						array_of_list[i-1]=NULL; //destroy the node
						new =(node*)(wholememory + (int)array_of_list[i]->number); 
						//wholememory is 0 + 32,16...2
						new->allocation = 0; //this block is on use
						new->number = req;
						new->next = NULL;
						new->prev = NULL;
						break;
					}else {
						//if the list before the list is not null
						//just add the new node
						array_of_list[i-1]=NULL; //destroy the node
						new =(node*)(wholememory + (int)array_of_list[i]->number); 
						//wholememory is 0 + 32,16...2
						new->allocation = 0; //this block is on use
						new->number = req;
						new->next = NULL;
						new->prev = NULL;
						array_of_list[i]->next = new;
						break;
					}
				}
			}
		}
		if(array_of_list[i]->allocation == 0){
		//if all the memory on use
		printf("All memory is on use");
		}
}

   
//}
/*  void *p;
   p=allocpages((req/PAGESIZE)+1);
   if(!p) puts("Failed");
   return p;
*/


int myfree(void *p) { 
	//free the block of memory 
	//myfree() received the pointer to the data(pointer that point to the data), not to the linked list element.	
	printf("myfree()!");
	node *newelement =NULL; //temporary node 
	node *temp=NULL;
	temp = (node*)((int)p-sizeof(node)); //temporary pointer
	temp->allocation = 1; //free this block

	node *buddy=NULL; 
	//find the correct address for buddy block of temp
	buddy = (node*)(((int)temp-(int)wholememory) ^ ((int)temp->number) + ((int)wholememory));
 
	//check if the buddy block is free
	if(buddy->allocation == 1){
		//coalest memory by deleting temp and buddy, then create a new element with twice size in the next
		//next linked list. depending where they were located
		if(temp>buddy){
			//newelement = (node*)buddy;//+ (int)(sizeof(node)*2));
			buddy = NULL;
			temp = NULL;
			newelement = (node*)buddy; 
			//newelement = (node*)((int)buddy+ (int)(sizeof(node)*2));
		}else{			
			buddy = NULL;
			temp = NULL;
			newelement = (node*)temp;
			//newelement = (node*)((int)temp+ (int)(sizeof(node)*2)); 
		}
		newelement->number = newelement-> number * 2;
	}
	node *buddyofnextbuddy=NULL;
	//the memory first memory is all ready coalest now
	//find the next memory of the next element by using newelement node
	//we have to coalesed the rest of linked list until buddy blocks are alocated or reach the maximum block size
	
	while(sizeof(newelement) <= SIZEOFWHOLEMEMORY){
		node *nextbuddy= (node*)newelement;
		buddyofnextbuddy = (node*)(((int)nextbuddy-(int)wholememory) ^ ((int)nextbuddy->number) + ((int)wholememory)); 
		//check if the buddy block is free
		if(buddyofnextbuddy->allocation == 1 && nextbuddy->number == buddyofnextbuddy->number){
			//coalest memory by deleting temp and buddy, then create a new element with twice size in the next
			//next linked list. depending where they were located
			if(buddyofnextbuddy>nextbuddy){
				//newelement = (node*)buddyofnextbuddy;
				nextbuddy = NULL;
				buddyofnextbuddy = NULL;
				newelement = (node*)buddyofnextbuddy;
				//newelement = (node*)((int)buddyofnextbuddy+ (int)(sizeof(node)*2));
			}else{
				//newelement = (node*)nextbuddy;				
				nextbuddy = NULL;
				buddyofnextbuddy = NULL;
				newelement = (node*)nextbuddy;					
				//newelement = (node*)((int)nextbuddy+ (int)(sizeof(node)*2));
			}
		newelement->number = newelement-> number * 2;
		}
	}
}	
   
  /* n=freepages(p);
   if(!n) puts("Failed");
   return n;
  */
	
unsigned seed=7652;

int myrand() { // pick a random number
   seed=(seed*2416+374441)%1771875;
   return seed;
}

int randomsize() { // choose the size of memory to allocate
   int j,k;
   k=myrand();
   j=(k&3)+(k>>2 &3)+(k>>4 &3)+(k>>6 &3)+(k>>8 &3)+(k>>10 &3);
   j=1<<j;
   return (myrand() % j) +1;
}

void list_out(node *head)
{
	node *current;//a variable to control where the pointer is
	current = head;//initially points to head, the first element
	printf("\n\n");
	if (current == NULL)//if head is NULL, the linked list is empty
		printf("list empty\n");
	else
	{
		while (current != NULL)//while it is not the last element
		{
				printf("size %d allocation %d. The next element will be in %x\n",current->number,current->allocation,current->next);
				current = current->next;//go to the next element
		}
	}
}

int main() {
   int i,k;
   int inc, c,nm;
   unsigned char *n[NO_OF_POINTERS]; // used to store pointers to allocated memory
   int size;
   int s[5000]; // used to store sizes when testing
   int start_time;
   int start_mem;
   wholememory = (node *) malloc(SIZEOFWHOLEMEMORY); //this is the head of the list and will hold the size of
							   // availablle memory
  for(inc=0;inc<6;inc++){
	nm =SIZEOFWHOLEMEMORY/power(2,inc);
	array_of_list[inc]=(node*)((int)(wholememory+nm));//(SIZEOFWHOLEMEMORY/power(2,inc)));
	array_of_list[inc]->allocation = 1;
	array_of_list[0]->number = SIZEOFWHOLEMEMORY;
	array_of_list[inc]->number = nm;//(SIZEOFWHOLEMEMORY/power(2,inc));
	array_of_list[inc]->next = NULL;
	array_of_list[inc]->prev = NULL;
  }

  for(c=0;c<5;c++){
	list_out(array_of_list[c]);
  }
  
   for(i=0;i<NO_OF_POINTERS;i++) {
      n[i]=0;     // initially nothing is allocated
   }

//get time
   struct timespec time1,time2;
   float timedif;
   clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1);
   printf("Initial TOTAL MEMORY %d \n",memory());
   start_mem=memory();
	
  //start_mem = array_of_list[0];
   //allocating memory as much as number of itterations
   for(i=0;i<NO_OF_ITERATIONS;i++) {
      //k=myrand()%NO_OF_POINTERS; // pick a pointer
      if(n[k]) { // if it was allocated then free it
         // check that the stuff we wrote has not changed
         //if ( n[k][0]!=(unsigned char)(n[k]+s[k]+k) )
         if ( (n[k][0]) != (unsigned char) k)//(n[k]+s[k]+k) )
            printf("Error when checking first byte! in n[%d] \n",k);
         if(s[k]>1 && (n[k][s[k]-1])!=(unsigned char) k )//(n[k]-s[k]-k))
            printf("Error when checking last byte! in n[%d] \n",k);
         FREE(n[k]); //free the memory
      }
      size=randomsize(); // pick a random size
  
      n[k]=(unsigned char *)MALLOC(size); // do the allocation 
      //FREE the 
      s[k]=size; // remember the size
      n[k][0]=(unsigned char) k;//(n[k]+s[k]+k);  // put some data in the first and
      //if(size>1) n[k][size-1]=(unsigned char) k;//(n[k]-s[k]-k); // last byte
      if(s[k]>1) n[k][s[k]-1]=(unsigned char) k;//(n[k]-s[k]-k); // last byte
   }
// print some statistics
   clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2);
   timedif=(float) ((time2.tv_sec-time1.tv_sec)+((float)(time2.tv_nsec-time1.tv_nsec)/1000000000));

   printf("%d iterations took %.3f seconds and used %d bytes\n", i, timedif, memory()-start_mem);
   printf("After allocations, TOTAL MEMORY %d \n",memory());

   return 1;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.