Memory Allocator (ITI8510)

Real-Time Operating Systems and Systems Programming

Basic Linux command-line and utilities for accessing it Standard Streams Stack Exploration Exploring Debugger Signals Threads Processes File Attributes Reading Binary Files LAB: Hufmann Encoder Network Sockets Optimization (mmap() helps here)

[ @ ]

This task will be part of the final grading. Keep the program in directory "rtos/lab2" and name it allocator.c (and don't forget allocator.h for compilation) for it to be found for checking-script.

You have three weeks to complete the task (until May, 11).

Task

Write your own memory allocator which could replace malloc()/free() pair. There are a few requirements:

• Allocator should re-use freed memory.
• It should not crash.

Write two functions:

void * Malloc(size_t size)
void Free(void * ptr)

Questions

• How should I allocate the memory for allocator?

Since the program should handle its memory all by itself, you should use sbrk() function to move the heap pointer (the same thing what malloc does internally). Do not free the memory using sbrk(), just mark it for re-use.

• What algorithm should I use?

Use either first-fit or best fit algorithm. Joining of nearby blocks is highly recommended. Memory segregation is not needed (you do not have to create classes for larger and smaller allocations).

Testing

I used the following code for testing (and it works with standard malloc):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "allocator.h"

#define MAXSTR 2
#define MAXLEN 1024
#define MAXCHAR 'x'
#define MAXALL 1024

typedef struct memloc {
  char * loc;
  int size;
  char ch;
} Mloc;

int depth = 0;
Mloc mloc[MAXALL];
Mloc * mindex = mloc;


void writestring(char ch, char * ptr, int length) {
  ptr[length-1] = '\0';
  length--;
  while(length--) {
    *ptr++ = ch;
  }
}

void readstring(char ch, char *ptr, int length) {
  if(ptr[length-1] != '\0') error(EXIT_FAILURE, 0, "Problem with strings (not 0 terminated\n");
  length--;
  while (length--) {
    if(*ptr++ != ch) error(EXIT_FAILURE, 0, "Problem with strings (%c != %c\n", *(ptr-1), ch-1);
  }
}

void allocate_str() {
  int length, i;
  char ch, *chp;

  /* iterate over str length*/
  for(length=2; length <= MAXLEN; length = length << 1) { 
    printf("Allocations with %d bytes\n", length);
    for (ch = 'a'; ch <= MAXCHAR; ch++) {
      mindex->loc = Malloc(length); /* store memloc*/
      if(!mindex->loc) {
        error(EXIT_FAILURE, 0, "Malloc failure\n");
      }

      /* copy content */
      chp = mindex->loc;
      i = length - 1;
      do {
        *chp++=ch;
      } while ( i--);
      chp = '\0';

      mindex->ch = ch;
      mindex->size = length;
      mindex++;
    }
  }
 
}

void test_str() {
  Mloc * loc = mloc;
  
  char ch, *chp;
  int len;
   /* testing routine for all the memory */
  while(loc->loc) { /* global is 0 by default inside the array  */
    ch = loc->ch;
    chp = loc->loc;
    len = loc->size -1; /* \0 skip */
    while(len) {
      if(*chp != ch) error(EXIT_FAILURE, 0, "Error with string, not %d, length %d\n", ch, loc->size);

      chp++;
      len--;
    }

    loc++;
    mindex = loc;
  }
}

void testmem() {
  /* allocate some stuff */

  allocate_str();


  /* some non-symmetric allocations */

  char * ptr = Malloc(2);
  writestring('x', ptr, 2);
  puts(ptr);
  readstring('x', ptr,2);
  Free(ptr);
  putchar('\n');

  test_str();


}

int main(int argc, char ** argv){
  testmem();
  return EXIT_SUCCESS;

}