Debugging Malloc Lab: Detecting Memory-Related Errors解答

实验三说明文档：

题目：

Take Assessment: Exercise 3: Debugging Malloc Lab
Debugging Malloc Lab: Detecting Memory-Related Errors
Introduction
The usual implementation of malloc and free are unforgiving to errors in their callers' code, including cases where the programmer overflows an array, forgets to free memory, or frees a memory block twice. This often does not affect the program immediately, waiting until the corrupted memory is used later (in the case of overwrites) or gradually accumulating allocated but unused blocks. Thus, debugging can be extremely difficult.
In this assignment, you will write a wrapper for the malloc package that will catch errors in the code that calls malloc and free. The skills you will have learned upon the completion of this exercise are pointer arithmetic and a greater understanding of the consequences of subtle memory mistakes.

原文：http://blog.csdn.net/qq_34861102/article/details/78575533

• 实验目的：

  • 本次实验的目的在于通过自己编写自定义的malloc和free函数以达到可以定位问题所在的行号，方便调试的目的

• 实验思路

  • 首先是题目中提示要通过自定义header和footer结构来记录在内存分配和释放中的相关信息以实现可以在问题出现的时候定位到问题的具体信息。示意图如下：

    

  • 其次，实验要求中要求实现 PrintAllocatedBlocks 和 HeapCheck 这两个函数，对于这两个函数的功能的实现则需要自己定义相关的数据结构来实现。

  • PrintAllocatedBlocks 函数要实现的是打印当前由 malloc 函数所分配的块的文件名和行号。HeapCheck函数实现对当前已分配块的错误信息检查以及相关的输出。可以看到，对于这两个函数的实现都需要遍历每一个块中含有的header和footer结构来实现，基于此，这里我想到的一个解决的方案是使用链表的结构来进行函数功能的实现。

• 实验实现

  • header结构和footer结构的实现

    按照题目中的信息：

    Information that you might want to store in this extra (header, footer) area include:
    ? a "fence" immediately around the requested payload with a known value like 0xCCDEADCC, so that you can check if it has been changed when the block is freed.
    ? the size of the block
    ? a checksum for the header to ensure that it has not been corrupted (A checksum of a sequence of bits is calculated by counting the number of "1" bits in the stream. For example, the checksum for "1000100010001000" is 4. It is a simple error detection mechanism.)
    ? the filename and line number of the MALLOC() call

    可以写出来header结构和footer结构应该含有的参数：

    // the definition of header
    typedef struct {int checksum;char * filename;int linenumber;int size; // the size of payloadint fence; // fence indicating whether writing past header} header;  // the definition of footertypedef struct {int fence; // fence indicating whether writing past footer
    } footer;
    

  • 链表结构的实现

    • 使用链表结构的同时要考虑到关联到header结构和footer结构，因此这里新定义一个结构体为链表的元素，同时初始化一个节点为链表的初始节点：

      //to record the information for the extra function
      typedef struct node {header *h;struct node *next;
      } footer_node;static footer_node header_node = { NULL, NULL };

  • MyMalloc函数的实现

    • 初始化header和footer

    • 计算 header 的 checksum 值，这里通过上一次实验中涉及到的相关位运算可以较为简便的计算checksum 。值得注意的是这里的temp是header的地址，要以char *的格式声明。（对于其他格式如 int *会导致进行++操作的时候导致实际地址变化大于 1），size为header的长度。

      while(size--) {// for the char the num of bits is 8for(int i = 0; i < 8; i++) {checksum += (*temp >> i) & 0x1;}   temp ++;
      }

    • 分配地址，这里我分配地址的代码为：

      void *temp = malloc(sizeof(header) + sizeof(footer_node) + size + sizeof(footer) + BUFFER + BUFFER);

      在题目原有的基础上增加了BUFFER结构和元素FOOTER_NODE结构，原因在于：

      实际中，如果直接将链表的元素放在块之后，对于部分测试会因为相关的地址操作会修改链表的元素而导致程序的出现读写错误。（这里可以从http://danluu.com/malloc-tutorial/中看到对于malloc操作地址分配的实现，可以判断得出上述结论）因此这里元素前后增加一个BUFFER使得测试代码中的操作不会对记录链表产生影响。

      示意图如下：

      

    • 向链表中添加元素

      通过向之前提到的初始链表中添加链表元素完成信息的连续记录，这里是将上面地址示意图的 FOOTER_NODE 加入到链表之中。 FOOTER_NODE结构中的h元素为当前块中header

      fn->h = h;
      fn->next = NULL;
      footer_node *ptmp = &header_node;
      while (ptmp->next){ptmp = ptmp->next;
      }
      ptmp->next = fn;

    • 依照地址示意图寻找到PAYLOAD的最低地址返回即可。

      return (void *)((char *)temp + sizeof(header));

  • MyFree函数的实现

    • 对链表中的元素进行判断，如果链表中不含当前FOOTER_NODE，则表明当前块已经被释放过了，则应该出现错误 4 。

      if (-1 == deleteNode(h)){error(4, filename, linenumber);return;
      }

    • 通过当前块PAYLOAD的值寻找到header

      header *h = (header *)((char *)ptr - sizeof(header));

    • 根据header包含的内容进行其余错误的判断：

      //get the footer information
      if (msize < 0)errorfl(3, mfilename, mlinenumber, filename, linenumber);
      elseffence = ((footer *)((char *)ptr + msize))->fence;//check whether writing past headerif (mfence != FENCENUM) {errorfl(1, mfilename, mlinenumber, filename, linenumber);}// check whether writing past footerif (ffence != FENCENUM) {errorfl(2, mfilename, mlinenumber, filename, linenumber);}//check whether header information corruptsh->checksum = 0;if (CalcheckSum((char *)h, sizeof(header)) != mchecksum) {errorfl(3, mfilename, mlinenumber, filename, linenumber);}

  • PrintAllocatedBlocks 和 HeapCheck 函数的实现

    对于PrintAllocatedBlocks和 HeapCheck 函数，直接对链表进行遍历，其中PrintAllocatedBlocks调用PRINTBLOCK即可。

    HeapCheck 函数仿照MyFree函数进行错误的判断，其中将打印函数errorfl替换成PRINTERROR即可。

• 实验结果