Infinite loop

>>     if(sizearray[i]==rounded && empty[i]==1){
>>       return malloc(sizearray[i]);
>>     }

Shouldn't you set empty[i] to 0 before returning ? And should you do anything with memarray ?


>>   while(sizearray[i]!=NULL)

NULL implies that sizearray is an array of pointers, but elsewhere you use it as an array of block sizes (int values). Don't use NULL for ints, as it causes confusion.


>>     while(sizearray[i]!=NULL){
>>       if(sizearray[i]>=rounded && sizearray[i]<split){
>>         split=sizearray[i];
>>         splitindex=i;
>>       }
>>     }

You never check whether the block is empty before splitting it.


>>     rounded = rounded/2;

Why do you do that ? Do you suddenly want less memory to be allocated ?



Btw, the point of the buddy algorithm is to replace the malloc function. You allocate one big block of memory, and then you use smaller blocks within that big block to satisfy allocation requests. You do not do any more malloc calls.

Also, the setup with the arrays makes it more complicated than it needs to be. It would be easier to use a binary tree to keep track of the memory blocks.

Finally, you can use a struct to group related data (like size, memory, and empty flag).

>> Shouldn't you set empty[i] to 0 before returning ? And should you do anything with memarray ?

Thats right, good catch.

>> NULL implies that sizearray is an array of pointers, but elsewhere you use it as an array of block sizes (int values). Don't use NULL for ints, as it causes confusion.

So I could just substitute memarray for sizearray correct?

>> You never check whether the block is empty before splitting it.

Also a good catch.

>> Why do you do that ? Do you suddenly want less memory to be allocated ?

No, because in the example I've split the big chunk of 8K into two 4K chunks and now I want to split one of the 4K chunks into a 2K chunk so I can meet the request.


>> Btw, the point of the buddy algorithm is to replace the malloc function. You allocate one big block of memory, and then you use smaller blocks within that big block to satisfy allocation requests. You do not do any more malloc calls.

So one I have the memory address of the big chunk, how do I split that up into the two smaller chunks without using malloc?

>> So I could just substitute memarray for sizearray correct?

Depends what you're trying to do.
NULL is for pointers. 0 is for integers.


>> No, because in the example I've split the big chunk of 8K into two 4K chunks and now I want to split one of the 4K chunks into a 2K chunk so I can meet the request.

Yes, but rounded is the requested size. You can't halve that, or you'll look for a block that is too small.


>> So one I have the memory address of the big chunk, how do I split that up into the two smaller chunks without using malloc?

You have the start address (x) and the size (s). If you want to split that block up in two, you get two blocks :

1) the first with start address x, and size (s / 2)
2) the second with start address (x + (s / 2)), and size (s / 2)

It becomes more clear if you draw it on a piece of paper.

How should I implement the start address of the second (x+(s/2)?

I tried: memarray[splitindex+1]=memarray[splitindex+1]+(sizearray[splitindex+1]/2);

but I get this error:

"mymalloc.c", line 62: warning: pointer to void or function used in arithmetic

Instead of using a void*, use a pointer type that you can do arithmetic on, like unsigned char*.

I still seem to be stuck in an infinite loop.  It doesn't even get to the end of the while loop.  It prints out the information of the newly split memory chunks ... in this example two 4K chunks ... but then it just jumps out of the loop back to where it decides what the value of rounded is ... this is outside the while loop.

Any idea why this would occur ... I have attached my updated my_malloc.

void *my_malloc(int size){
 
  int i=0;
  int end;
  int rounded=1;
  int split=sizearray[0];
  int splitindex=0;
 
  while(rounded<size){
    rounded = rounded * 2;
  }
 
  while(memarray[i]!=NULL){ //Checks if memory chunk is already in a\
rray
    printf("Rounded: %d - Size: %d\n",rounded,sizearray[i]);
    if(sizearray[i]==rounded && empty[i]==1){
      empty[i]=0;
      return memarray[i];
    }
    i++;
  }
  end=i;
 
  while(1){
    i=1;
    while(memarray[i]!=NULL){
      if(sizearray[i]>=rounded && sizearray[i]<split && empty[i]==1)\
{
        split=sizearray[i];
        splitindex=i;
      }
    }
 
    printf("Split: %d - Split Index: %d\n",split,splitindex);
 
    for(i=end;i>splitindex;i--){
      memarray[i]=memarray[i-1];
      sizearray[i]=sizearray[i-1];
      empty[i]=empty[i-1];
    }
 
    memarray[splitindex]=memarray[splitindex+1];
    memarray[splitindex+1]=memarray[splitindex+1]+(sizearray[splitin\
dex+1]/2);
    sizearray[splitindex]=split/2;
    sizearray[splitindex+1]=split/2;
    empty[splitindex]=1;
    empty[splitindex+1]=1;
 
 
    end=end+1;
 
 
    i=end-1;
    while(i>=0){
      printf("\n%d - %x - %d - %d\n",i,memarray[i],sizearray[i],empt\
y[i]);
      i--;
    }
 
    if(sizearray[splitindex+1]==rounded){
      empty[splitindex+1]=0;
      return memarray[splitindex+1];
    }
 
    printf("Got to end of while");
 
  }
}

Select allOpen in new window

Sorry this is the output I get:

> ./p3
Rounded: 4194304 - Size: 8388608
Split: 8388608 - Split Index: 0

1 - 424448 - 4194304 - 1

0 - 24448 - 4194304 - 1
Rounded: 8388608 - Size: 4194304
Rounded: 8388608 - Size: 4194304
^C

It's normal that you don't reach the end of the while loop, since you were requesting a block of size 4194304, and so this :

>>     if(sizearray[splitindex+1]==rounded){
>>       empty[splitindex+1]=0;
>>       return memarray[splitindex+1];
>>     }

was satisfied.

I assume your code is calling my_malloc more than once.


>> 1 - 424448 - 4194304 - 1
>> 
>> 0 - 24448 - 4194304 - 1

Also, that doesn't seem to make a lot of sense. Can you post your whole code ?

No, in this example I am initializing and 8K block and requesting a 2K block.  So it successfully splits the 8 into two 4K's and then for some reason goes back up to rounded.  I have attached my code

Mymalloc.h:
 
#include <stdio.h>
#include <unistd.h>
 
/* function prototypes */
int   my_init(int);
void *my_malloc(int);
int   my_free(void *);
 
Mymalloc.c :
 
#include "mymalloc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void *memaddr;
unsigned char *memarray[999];
int sizearray[999];
int empty[999];
 
int my_init(int memsize){
  memaddr = malloc(memsize*1048576); //Converts memsize from megabytes to bytes
  memarray[0]=memaddr;
  sizearray[0]=memsize*1048576;
  empty[0]=1;
  if(memaddr != NULL)
    return 0;
  else
    return -1;
}
 
void *my_malloc(int size){
 
  int i=0;
  int end;
  int rounded=1;
  int split=sizearray[0];
  int splitindex=0;
 
  while(rounded<size){
    rounded = rounded * 2;
  }
  
  while(memarray[i]!=NULL){ //Checks if memory chunk is already in array
    printf("Rounded: %d - Size: %d\n",rounded,sizearray[i]);
    if(sizearray[i]==rounded && empty[i]==1){
      empty[i]=0;
      return memarray[i];
    }
    i++;
  }
  end=i;
 
  while(1){
    i=1;
    while(memarray[i]!=NULL){
      if(sizearray[i]>=rounded && sizearray[i]<split && empty[i]==1){
        split=sizearray[i];
        splitindex=i;
      }
    }
    
    printf("Split: %d - Split Index: %d\n",split,splitindex);
    
    for(i=end;i>splitindex;i--){
      memarray[i]=memarray[i-1];
      sizearray[i]=sizearray[i-1];
      empty[i]=empty[i-1];
    }
 
    memarray[splitindex]=memarray[splitindex+1];
    memarray[splitindex+1]=memarray[splitindex+1]+(sizearray[splitindex+1]/2);
    sizearray[splitindex]=split/2;
    sizearray[splitindex+1]=split/2;
    empty[splitindex]=1;
    empty[splitindex+1]=1;
    
    
    end=end+1;
    
    
    i=end-1;
    while(i>=0){
      printf("\n%d - %x - %d - %d\n",i,memarray[i],sizearray[i],empty[i]);
      i--;
    }
   
    if(sizearray[splitindex+1]==rounded){
      empty[splitindex+1]=0;
      return memarray[splitindex+1];
    }
 
    printf("Got to end of while");
 
    //return memaddr;
  }
}
 
int my_free(void *three){
 
}
 
tp0.c *Test file* :
 
#include "mymalloc.h"
 
#define MEMORY_SIZE 8 /* The size of memory in MB */
 
#define NUM_BUFS 5
#define SMALL_BUF_SIZE 32
#define LARGE_BUF_SIZE 1024
 
char *sbuf[NUM_BUFS], *lbuf[NUM_BUFS];
 
int main(){
  int i, j;
 
  my_init(MEMORY_SIZE);
  
  sbuf[i]=(char *)my_malloc(4194304);
  lbuf[i]=(char *)my_malloc(8388608);
  
  /*
  for (i = 0; i < NUM_BUFS; i++) {
    sbuf[i] = (char *)my_malloc(SMALL_BUF_SIZE);
    lbuf[i] = (char *)my_malloc(LARGE_BUF_SIZE);
  */
    printf("The buffer small pointers is %x, and large pointer is %x\n", (unsigned)sbuf[i], (unsigned)lbuf[i]);
   /*}
  
  for (i = 0; i < NUM_BUFS; i++) {
    my_free((void *) sbuf[i]);
    my_free((void *) lbuf[i]);
  }
 
  */
}

Select allOpen in new window

You never initialized the three arrays. You should initialize them to all 0's before doing anything else to them.


>> No, in this example I am initializing and 8K block and requesting a 2K block.

No, you're not :

>>   sbuf[i]=(char *)my_malloc(4194304);
>>   lbuf[i]=(char *)my_malloc(8388608);

You're requesting 4MB block, and then an 8MB block. But you only have 8MB available.
The first call succeeds (as you can see from your output), but the second fails (because there's not enough memory available).

should i initialize the first element of every array or how should I do that?

Godd call on the second part, I had it requesting 2K and then changed it, I guess I forgot to change it back

>> should i initialize the first element of every array or how should I do that?

All of them. Since you depend on memarray[i] to be NULL if it's not used, you have to make sure that it actually IS NULL to begin with.

Even now when I changed it it still is in an infinite loop

> ./p3
Rounded: 4194304 - Size: 8388608
Split: 8388608 - Split Index: 0

1 - 424448 - 4194304 - 1

0 - 24448 - 4194304 - 1
Rounded: 2097152 - Size: 4194304
Rounded: 2097152 - Size: 4194304
^C

how do i initialize them to NULL if they are global variables?

Did you initialize the whole array ? Can you show the new complete code ?

>> how do i initialize them to NULL if they are global variables?

You have a my_init function for that, don't you ? You can loop over the entire array, and initialize each element.

Yea I changed my_init so that when i initialize the arrays I initialize every spot after the initial spot to NULL.

int my_init(int memsize){
  memaddr = malloc(memsize*1048576); //Converts memsize from megabyt\
es to bytes
  memarray[0]=memaddr;
  sizearray[0]=memsize*1048576;
  empty[0]=1;
  for(int i=1;i<999;i++){
    memarray[i]==NULL;
    sizearray[i]==NULL;
    empty[i]==NULL;
  }
  if(memaddr != NULL)
    return 0;
  else
    return -1;
}

Select allOpen in new window

>> so that when i initialize the arrays I initialize every spot after the initial spot to NULL.

Remember when I said that NULL is for pointers, and 0 for integers ?


You also need to initialize i and j inside main (before using them).


And to solve your infinite loop problem, take a closer look at this loop :

>>     while(memarray[i]!=NULL){
>>       if(sizearray[i]>=rounded && sizearray[i]<split && empty[i]==1){
>>         split=sizearray[i];
>>         splitindex=i;
>>       }
>>     }

Try to run it in your head ... What will happen ? When will it end ? Which index will it check on the first iteration ? And on the second ?

The first index it will check first is 1 because just before the while loop I have i=1.  So originally memarray[1] is NULL because the only thing in memarray is memarray[0]="8K's address".  The split was already set to 8K and index to 0.  

Then if it goes through the loop after the 8K was split into two 4K's ... although I'm not 100% sure it does kind of confused where the program goes after the original split ... it will check index 1 first.  

I think I have to move the initialization of split and split index into the while loop so it will set the index to the new 4K index 0 and not the old 8K index 0.

So it checks index 1 but it is not empty so it stays at 0 and the split is the 4K in index 0 which I think it should be.

I'm not sure what this tells me to do to the while loop to fix the infinite loop problem.

>> So originally memarray[1] is NULL because the only thing in memarray is memarray[0]="8K's address".

So, it works for the first allocation request.

How about the second allocation request ? (the one for 2MB)

>> it will check index 1 first.

Yes, and then ? What will it do then ?

Yes it works for the first

It checks index 1 but it is not empty so it stays at 0 and the split is the 4K in index 0 which I think it should be.  However it never goes and splits that 4K into two 2K blocks.

No?  Not sure what your gettin at

>> It checks index 1 but it is not empty so it stays at 0 and the split is the 4K in index 0 which I think it should be.

That's what you WANT it to do. But that's not what's actually happen (as you noticed). So, there is something wrong :)

Look closer at that loop. So, the first iteration checks the element at index 1 ... What does it do in the second iteration ?

I've been looking at it for over a half hour and have no idea.  That's what I think it is doing but as you said I guess thats not what is happening.  What is happening?

i increases with i++ so i is now 2.

>> while(memarray[2]!=NULL){

memarray[2] is NULL so the while loop is over ... no?

>> i increases with i++ so i is now 2.

Where do you see i++ ?

while(memarray[i]!=NULL){ //Checks if memory chunk is already in a\
rray
    printf("Rounded: %d - Size: %d\n",rounded,sizearray[i]);
    if(sizearray[i]==rounded && empty[i]==1){
      empty[i]=0;
      return memarray[i];
    }
    i++;
  }

That's a different loop :) The loop I was talking about is the one I quoted in http:#24487373

>> so I just need to add i++ into the while loop you were talking about?

Try it, and see what happens ;)

That solved the infinite loop. Now a request for 32 bytes and 1024 bytes works.

But then if I request 32 bytes and 1024 bytes again it won't separate the 64 into two 32's and the 2048 into two 1024's.

Any idea.

Here is the output I'm gettin from my arrays:
Array index - Address - Size - Empty

24 - 424508 - 4194304 - 1
23 - 224508 - 2097152 - 1
22 - 124508 - 1048576 - 1
21 - a4508 - 524288 - 1
20 - 64508 - 262144 - 1
19 - 44508 - 131072 - 1
18 - 34508 - 65536 - 1
17 - 2c508 - 32768 - 1
16 - 28508 - 16384 - 1
15 - 26508 - 8192 - 1
14 - 25508 - 4096 - 1
13 - 24d08 - 2048 - 1
12 - 24908 - 1024 - 0
11 - 24708 - 512 - 1
10 - 24608 - 256 - 1
9 - 24588 - 128 - 1
8 - 24548 - 64 - 1
7 - 24528 - 32 - 0
6 - 24518 - 16 - 1
5 - 24510 - 8 - 1
4 - 2450c - 4 - 1
3 - 2450a - 2 - 1
2 - 24509 - 1 - 1
1 - 24508 - 0 - 1
0 - 24508 - 0 - 1Got to end of whileThe buffer small pointers is 24508, and large pointer is 0

Can you post the exact (complete) code you used to get that result ?

You should also try debugging this yourself ... Figure out what's going on, and where it deviates from what you want to happen.

You can use a debugger to see what's happening, or you can make use of printf's to show you the data you need.

I wanted to delete this question and I was wondering how I would do it or if it can be done.

Thanks

There's no reason to delete this question ;) But I see you changed your mind and started an auto-close instead. That's fine.

Do you have no more questions about this ? It's all working as you want it now ?