How to Implement a Salami Memory Allocator in C?

[carl123]

Salami Allocator

In this warm-up submission you will write a totally trivial allocator:

The function init allocator() reserves a given portion of memory for the allocator. Every call to my_malloc() cuts off the requested amount of memory from the remainder of the reserved memory. The call to my_free() does not free any memory. When all the memory has been used, and no more memory is left, subsequent calls to my_malloc() return NULL. For the implementation all you need is a pointer to the beginning of the remaining memory. Whenever memory is allocated, advance the pointer, until you reach the end.

int memAvail;  // amount of memory to be made available to allocator

unsigned int init_allocator(unsigned int _basic_block_size, unsigned int _length){

/* This function initializes the memory allocator and makes a portion of
   ’_length’ bytes available. The allocator uses a ’_basic_block_size’ as
   its minimal unit of allocation. The function returns the amount of
   memory made available to the allocator. If an error occurred,
   it returns 0.
*/

if (_basic_block_size < _length){
    memAvail = _length/_basic_block_size;
    return memAvail;
}
else{

    return 0;
  }

}

void *my_malloc(size_t _length) {
 
 /* This preliminary implementation simply hands the call over the
     the C standard library!
     Of course this needs to be replaced by your implementation.
  */
 
 int *ptr;
  ptr = (int *) malloc(_length * sizeof(_length));
      return ptr;
  if (_length >= memAvail){
   return NULL;
 }
     return malloc(_length);
}

This my interpretation of the problem so far. It seems right to me but I don't know if I'm doing something wrong. Any help will be appreciated.

 

[Mark44]

Salami Allocator

In this warm-up submission you will write a totally trivial allocator:

The function init allocator() reserves a given portion of memory for the allocator. Every call to my_malloc() cuts off the requested amount of memory from the remainder of the reserved memory. The call to my_free() does not free any memory. When all the memory has been used, and no more memory is left, subsequent calls to my_malloc() return NULL. For the implementation all you need is a pointer to the beginning of the remaining memory. Whenever memory is allocated, advance the pointer, until you reach the end.

int memAvail;  // amount of memory to be made available to allocator

unsigned int init_allocator(unsigned int _basic_block_size, unsigned int _length){

/* This function initializes the memory allocator and makes a portion of
   ’_length’ bytes available. The allocator uses a ’_basic_block_size’ as
   its minimal unit of allocation. The function returns the amount of
   memory made available to the allocator. If an error occurred,
   it returns 0.
*/

if (_basic_block_size < _length){
    memAvail = _length/_basic_block_size;
    return memAvail;
}
else{

    return 0;
  }

}

void *my_malloc(size_t _length) {
 
 /* This preliminary implementation simply hands the call over the
     the C standard library!
     Of course this needs to be replaced by your implementation.
  */
 
 int *ptr;
  ptr = (int *) malloc(_length * sizeof(_length));
      return ptr;
  if (_length >= memAvail){
   return NULL;
 }
     return malloc(_length);
}

This my interpretation of the problem so far. It seems right to me but I don't know if I'm doing something wrong. Any help will be appreciated.

I don't think your implementation is what the problem is calling for. My reason for thinking this is that your my_malloc() function is not much more than a wrapper around the standard library function malloc().

As I interpret this problem, you need to allocate a reasonably large chunk of memory, possibly from stack memory using an array. Your my_malloc() function should process requests for storage out of this memory pool, keeping track of the section of memory that is being used. You should also return the memory when it is no longer needed, by implementing a my_free() function that makes the formerly used memory available again.

 

[willem2]

As I interpret this problem, you need to allocate a reasonably large chunk of memory, possibly from stack memory using an array. Your my_malloc() function should process requests for storage out of this memory pool, keeping track of the section of memory that is being used..

I would use the normal malloc once in the initialization to get this memory.
You also have to store the parameters of the initialization function to use them in the my_malloc() function.

You should also return the memory when it is no longer needed, by implementing a my_free() function that makes the formerly used memory available again.

The exercise says "The call to my_free() does not free any memory". Keeping track of which blocks are freed would make this much harder.

 

[jim mcnamara]

When you by process cured meat that comes in a large chub, you often want to make sandwiches with it at home. So the store has a slicing machine with a large round blade. They whack off as many slices from the chub and as thick or thin as you want. This is why the algorithm is called a salami allocator.

So. A salami allocator does this:

1. get a large chub of memory.  Use malloc().  Check the return code from malloc().  Important!
     a. Remember the start of the chub as a pointer - call it keepme.  This means storage for the 
          pointer has to stay "live", maybe in static or global memory.
     b. Remember the end of the chub - call it  the_end. (keepme + size) 
          This means storage for the pointer has to stay "live", maybe in static memory.
2. create a "blade" - a pointer in memory that keeps moving, starting from the beginning of the chub.  Call it blade, keep in non-volatile (static) memory
3. Every request for another slice of memory:
    a. check to see if your slice is small enough to be taken from the chub -
        i.e., check to see if adding the size of the slice to blade goes past the_end.
    b. if not,  copy blade to a temp pointer, add the size to blade, return temp - this is a single slice.
    c. if the request is too big or there is no more chub left, return null.
4. When everything is done (you decide what "done" means here) , call free() using keepme.  
      keepme should never change until you do this.

So there are lessons in here:

1. watch out where you ask the program to store variables. 
       Memory in a function is created on the stack, then destroyed when the function ends.

2. if keepme was declared as an automatic variable in a function, the whole program 
    would bomb or freeze - this is called undefined behavior. Undefined behavior means the 
    program can do anything - stack dump, reformat a disk, call Marios and order a pizza.  
    Anything.  
    Most modern compilers favor option one, which is to cause the program to abort somehow, 
     hopefully harmlessly.  Some aborts can cause a kernel panic (crash) on 
    older multiprocessing systems.  So then you have 50 other users mad at you.  
    Got the point?  If your compiler does option #3 feed them the pizza. 
 
3. When you get more experience you will find that keeping your never-to-lose variables in 
    a struct makes housekeeping simpler.

 

[carl123]

Thanks for the input everyone. All your suggestions have given me a clear idea of what I'm supposed to do. Appreciate it