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;
}