Sample program to test our functions Write a collection of C functions that prov

Question

Sample program to test our functions
Write a collection of C functions that provide the functionality of a heap manager These are the functions that you should provide: void heap_init(int num pages for heap) void heap_alloc(int num bytes to allocate) void heap_free(void "pointer to area to free) I will write a set of test programs which invoke your functions. The program must manage the space in a set of pages which you obtain via the mmap system call. It should use the first-fit algorithm to allocate new space The program must align requests on 16-byte addresses The program will need to maintain data structures that minimally keep track of blocks of free space. These data structures should NOT be in the allocated pages themselves If the user frees two blocks of memory that are adjacent, your program should coalesce them. If the user attempts to allocate more space than is available in an open free block, then heap alloc should return NULL

Explanation / Answer

p2test2.c

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

void heap_init(int num_pages_for_heap);
void *heap_alloc(int num_bytes_to_allocate);
void heap_free(void *pointer_to_area_to_free);

int main(int argc, char *argv[])
{
    char *p1, *p2, *p3, *p4, *p5, *p6;

    heap_init(1);

    p1 = (char *) heap_alloc(1000);
    if ((long int)p1 % 16 != 0)
    {
        printf("p1 bad %p pmod16 %d ",p1,((long int)p1)%16);
        exit(-1);
    }
    memset(p1,'A',1000);

    p2 = (char *) heap_alloc(1000);
    if ((long int)p2 % 16 != 0)
    {
        printf("p2 bad %p pmod16 %d ",p2,((long int)p2)%16);
        exit(-1);
    }
    memset(p2,'B',1000);

    p3 = (char *) heap_alloc(1000);
    if ((long int)p3 % 16 != 0)
    {
        printf("p3 bad %p pmod16 %d ",p3,((long int)p3)%16);
        exit(-1);
    }
    memset(p3,'C',1000);

    p4 = (char *) heap_alloc(1000);
    if ((long int)p4 % 16 != 0)
    {
        printf("p4 bad %p pmod16 %d ",p4,((long int)p4)%16);
        exit(-1);
    }
    memset(p4,'D',1000);

    p5 = (char *) heap_alloc(1600);    // 1st try should fail
    if (p5 != NULL)
    {
        printf("p5 should have been NULL, but is %p ",p5);
        exit(-1);
    }

    heap_free( (void *)p2 );
    p5 = (char *) heap_alloc(1600);    // 2nd try should fail
    if (p5 != NULL)
    {
        printf("p5 should have been NULL, but is %p ",p5);
        exit(-1);
    }

    heap_free( (void *)p3 );
    p5 = (char *) heap_alloc(1600);    // 3rd try should succeed
    if (p5 == NULL)
    {
        printf("p5 should NOT have been NULL here %p ",p5);
        exit(-1);
    }
    if ((long int)p5 % 16 != 0)
    {
        printf("p4 bad %p pmod16 %d ",p4,((long int)p4)%16);
        exit(-1);
    }
    if ( *(p5+32) != 'B')     // first few bytes should be B
    {
        printf("p5 (%p) first byte should be B but is %c ",p5,*(p5+32));
        exit(-1);
    }
    if ( *(p5+1200) != 'C') // bytes near the end should be C
    {
        printf("p5 (%p) end bytes should be C but are %c ",p5,*(p5+1200));
        exit(-1);
    }

    printf("DONE ");

    return 0;
}

p2.c

#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct freeBlock{
   char check;
   void *address;
   int size;
   int freeSpace;
   struct freeBlock *next;
};
// struct to track the start of our linked list
struct freeBlock *head;

void heap_init (int num_pages_for_heap){

   void *heap;
   num_pages_for_heap = num_pages_for_heap * getpagesize();
   heap = mmap(NULL, num_pages_for_heap, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
   memset( heap,'X',num_pages_for_heap );
   head = (struct freeBlock *) malloc(sizeof(struct freeBlock));
   head->freeSpace = num_pages_for_heap;
   head->address = heap;
   head->check = 'B';
   head->size = 0;
   head->next = NULL;
  
   return;
}

void *heap_alloc(int num_bytes_to_allocate)
{
   struct freeBlock *temp,*newBlock;

   char *t;
   long int freeSpace, math;
   temp = head;

   while( temp->next != NULL){

       if ((temp->check == 'A') && (temp->size >= num_bytes_to_allocate))
        {
            temp->check = 'B';
            temp->size = num_bytes_to_allocate;
            return temp->address;
        }

       freeSpace = temp->freeSpace;
       if ( temp->freeSpace < num_bytes_to_allocate ) return NULL;
       temp = temp->next;
   }
      
    math = temp->size;

    while (( (long int)temp->address + math) % 16 !=0 )
    {  
        math += 1;
        if ( num_bytes_to_allocate + math>temp->freeSpace ) return NULL;
    }
  
    newBlock = (struct freeBlock *) malloc( sizeof(struct freeBlock) ) ;

    temp->next = newBlock;

    newBlock->check = 'B';
    newBlock->next = NULL;
    newBlock->freeSpace = temp->freeSpace-math;
    newBlock->size = num_bytes_to_allocate;
    newBlock->address = temp->address + math;

   return newBlock->address;

}
  
  
void heap_free(void *pointer_to_area_to_free){

    struct freeBlock *temp,*prev;
    temp = head;
    while( temp->address != pointer_to_area_to_free )
    {
        prev = temp;
        temp = temp->next;
    }
    temp->check='A';
    if ( temp->next->check == 'A' )
    {
        temp->size += temp->next->size;
        temp->freeSpace += temp->next->size;
        temp->next = temp->next->next;
    }
    if (prev->check=='A')
    {
        prev->size += temp->size;
        prev->freeSpace += prev->size;
        prev->next = temp->next;
    }
      
}
      

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.