fence.txt

实现C语言中的malloc()函数

ssd6(系统级编程)---ex3(2008-10-28 18:25:30)标签：杂谈    

//"debugmalloc.c"

#include <stdlib.h>
#include <string.h>
#include "debugmalloc.h"
#include "dmhelper.h"
#include <stdio.h>

#define ALIGN  8
#define THEFENCE 0xDEADBEEF
#define HEADERSIZE sizeof(struct header)
 
struct header {
 int checksum;
 size_t size;
 int fence;
};

#define FOOTERSIZE sizeof(struct footer)
 
struct footer {
 int fence;
};


int allocatedSize = 0;


typedef struct block_node block_list;
struct block_node {
 void *ptr;
 int size;
 char *filename;
 int linenum;
 block_list *next;
};                  

         
block_list *allocatedList;//the header of the list


int add_block_to_list(void *ptr, int size, char *filename, int linenum) {
 block_list *newblock;
 char *name;

 newblock = (block_list *) malloc(sizeof(struct block_node));
 if (!newblock) {
  return -1;                    
 }
 name = (char *) malloc(strlen(filename) + 1);
 if (!name) {
  free(newblock);
  return -1;                                                                                                                                                                                                                                          
 }                                                                                                                                                                                      
 strcpy(name, filename);             
                                                                                                                                         
 newblock->ptr = ptr;
 newblock->size = size;
 newblock->filename = name;
 newblock->linenum = linenum;
 newblock->next = allocatedList;
 allocatedList = newblock;
 return 0;
}

int remove_block_from_list(void *ptr) {
 block_list *currblock = allocatedList, *prevblock = NULL;

 while (currblock) {
  if (currblock->ptr ==ptr ) { //if it is equal to the ptr                                                    
   if (!prevblock) {
    allocatedList = currblock->next; //the next block of currblock
   }
   else {
    prevblock->next = currblock->next;  //the next block of prevblock
   }
   free(currblock->filename);  //free the filename of currblock
   free(currblock);  //free the currblock
   return 0;
  }
  prevblock = currblock;  //equal to the currblock
  currblock = currblock->next;  //equal to the next of currblock
 }
 return -1;
}
// one mark

block_list *find_block(void *ptr) {
 block_list *currblock = allocatedList;
 while (currblock) {
  if (currblock->ptr == ptr) {
   return currblock ;  //return currblock
  }
  currblock = currblock->next;
 }
 return NULL;  //return the null pointer
}



int bitCount(int x) {

   
    int m1 = 0x11 | (0x11 << 8);
    int mask = m1 | (m1 << 16);
    int s = x & mask;
    s += x>>1 & mask;
    s += x>>2 & mask;
    s += x>>3 & mask;
   
    s = s + (s >> 16);

   
    mask = 0xF | (0xF << 8);
    s = (s & mask) + ((s >> 4) & mask);
    return (s + (s>>8)) & 0x3F;
}




void *MyMalloc(size_t size, char *filename, int linenumber) {
 char *headptr, *footptr;
 struct header h;
 struct footer f;
 int amount;
 int temp;
 
 h.fence = THEFENCE;
 f.fence  = THEFENCE; //the footer f and its element fence
 h.size = size;
 h.checksum = bitCount(size) + bitCount(h.fence);
 
 
 size += ALIGN - 1;
 size -= size % ALIGN;
 
 headptr = malloc(size + HEADERSIZE + FOOTERSIZE);
 if (!headptr)
  return NULL;
 footptr = headptr + HEADERSIZE + size;  //plus the size as well

 memcpy(headptr, &h, HEADERSIZE);
 memcpy(footptr, &f, FOOTERSIZE);  //FOOTERSIZE as well

 
 amount = (ALIGN - (h.size % ALIGN));
 temp = THEFENCE;
 if (amount > 0) {
  if (amount <= 4) {  //less than 4
   strncpy(footptr - amount, (char *) &temp, amount);
  }
  else {
   strncpy(footptr - amount, (char *) &temp, 4);
   strncpy(footptr - amount + 4, (char *) &temp, amount - 4);
  }
 }


 
 allocatedSize +=  h.size;   //the current value of allocatedSize and h.size

 
 if (add_block_to_list((void *) (headptr + HEADERSIZE), h.size, filename, linenumber) == -1) {
  free(headptr);  //free the headptr
  return NULL;  //free the null pointer
 }

 return (void *) (headptr + HEADERSIZE);
}


int checkBlock(void *ptr) {
 struct header *headptr = (struct header *) ptr - 1;
 struct footer *footptr;  
 int temp = THEFENCE;
 int size = headptr->size, amount; 
 
 if (headptr->fence != THEFENCE) {
  return 1;
 }
 if (headptr->checksum != bitCount(headptr->size) + bitCount(headptr->fence)) {
  return 3;  //return the value 3
 }
 // one mark
 
 size += ALIGN - 1;
 size -= size % ALIGN;
 
 footptr = (struct footer *) ((char *) ptr + size);
 if (footptr ->fence != THEFENCE) {  //the element of fence
  return 2;
 }
 
 
 amount = (ALIGN - (headptr->size % ALIGN));
 if (amount > 0) {  //greater than zero
  if (amount <= 4) {
   if (strncmp((char *) footptr - amount, (char *) &temp, amount) != 0) {
    return 2;  
   }
  }
  else {
   if (strncmp((char *) footptr - amount, (char *) &temp, 4) != 0
    || strncmp((char *) footptr - amount + 4, (char *) &temp, amount - 4) != 0) {
    return 2;  
   }   
  }
 }

 return 0;
}

void MyFree(void *ptr, char *filename, int linenumber) {
 struct header *headptr = (struct header *) ptr - 1;
 block_list *theBlock;   //define the *theBlock
 int ret;
 
 if (!(theBlock = find_block(ptr))) {
  error(4, filename, linenumber);  //the linenumber as well
 }
 if (ret = checkBlock(ptr)) {
  errorfl(ret, theBlock->filename, theBlock->linenum, filename, linenumber);
 }
 
 allocatedSize -= headptr->size;
 free(headptr); 
 remove_block_from_list(ptr);
}


int AllocatedSize() {
 return allocatedSize;  //return the allocatedSize
}

 

 


void PrintAllocatedBlocks() {
 block_list *currblock = allocatedList;
 printf("Currently allocated blocks:\n");
 while (currblock) {
  PRINTBLOCK(currblock->size, currblock->filename, currblock->linenum);
  currblock = currblock ->next;  //point to the next block of currblock
 }
}


int HeapCheck() {
 block_list *currblock = allocatedList;
 int ret = 0, err;
 while (currblock) {
  if (err = checkBlock(currblock->ptr)) {
   ret = -1;
   PRINTERROR(err, currblock->filename, currblock->linenum);
  }
  currblock = currblock->next;  //the currblock points to the next
 } 
 return ret;
}
// one mark with demonstration