debugmalloc_3.c

SSD6网上教程全部练习及答案 原版的正确答案

#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)
	/* currently 12 bytes */
struct header {
	int checksum;
	size_t size; /* 4 bytes
				size does not include header and footer */
	int fence;
};

#define FOOTERSIZE	sizeof(struct footer)
	/* currently 4 bytes */
struct footer {
	int fence;
};

/* Global indicating # bytes allocated */
int allocatedSize = 0;

/* Linked list structure holding allocated block info */
typedef struct block_node	block_list;
struct block_node {
	void *ptr;
	int size;
	char *filename;
	int linenum;
	block_list *next;
};

/* global list */
block_list *allocatedList;

/* helper functions */
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 (!prevblock) {
				allocatedList = currblock->next;
			}
			else {
				prevblock->next = currblock->next;
			}
			free(currblock->filename);
			free(currblock);
			return 0;
		}
		prevblock = currblock;
		currblock = currblock->next;
	}
	return -1;
}


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


/* Taken from 15-213 Lab 1 */
int bitCount(int x) {

    /* Sum 8 groups of 4 bits each */
    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;
    /* Now combine high and low order sums */
    s = s + (s >> 16);

    /* Low order 16 bits now consists of 4 sums,
       each ranging between 0 and 8.
       Split into two groups and sum */
    mask = 0xF | (0xF << 8);
    s = (s & mask) + ((s >> 4) & mask);
    return (s + (s>>8)) & 0x3F;
}


/* Wrappers for malloc and free */

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;
	h.size = size;
	h.checksum = bitCount(size) + bitCount(h.fence);
	
	/* round up  size */
	size += ALIGN - 1;
	size -= size % ALIGN;
	
	headptr = malloc(size + HEADERSIZE + FOOTERSIZE);
	if (!headptr)
		return NULL;
	footptr = headptr + HEADERSIZE + size;

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

	/* if there is space after payload and before footer
		because of alignment, fill in parts of THEFENCE */
	amount = (ALIGN - (h.size % ALIGN));
	temp = THEFENCE;
	if (amount > 0) {
		if (amount <= 4) {
			strncpy(footptr - amount, (char *) &temp, amount);
		}
		else {
			strncpy(footptr - amount, (char *) &temp, 4);
			strncpy(footptr - amount + 4, (char *) &temp, amount - 4);
		}
	}

	/* add to allocatedSize */
	allocatedSize += h.size;

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

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

/* returns error code or 0 on success */
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;
	}
	
	/* round up size */
	size += ALIGN - 1;
	size -= size % ALIGN;
	
	footptr = (struct footer *) ((char *) ptr + size);
	if (footptr->fence != THEFENCE) {
		return 2;
	}
	
	/* check area before footer if not part of payload */
	amount = (ALIGN - (headptr->size % ALIGN));
	if (amount > 0) {
		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;
	int ret;
	
	if (!(theBlock = find_block(ptr))) {
		error(4, filename, linenumber);
	}
	if (ret = checkBlock(ptr)) {
		errorfl(ret, theBlock->filename, theBlock->linenum, filename, linenumber);
	}
	
	allocatedSize -= headptr->size;
	free(headptr);	
	remove_block_from_list(ptr);
}

/* returns number of bytes allocated using MyMalloc/MyFree:
	used as a debugging tool to test for memory leaks */
int AllocatedSize() {
	return allocatedSize;
}



/* Optional functions */

/* Prints a list of all allocated blocks with the
	filename/line number when they were MALLOC'd */
void PrintAllocatedBlocks() {
	block_list *currblock = allocatedList;
	printf("Currently allocated blocks:\n");
	while (currblock) {
		PRINTBLOCK(currblock->size, currblock->filename, currblock->linenum);
		currblock = currblock->next;
	}
}

/* Goes through the currently allocated blocks and checks
	to see if they are all valid.
	Returns -1 if it receives an error, 0 if all blocks are
	okay.
*/
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;
	}	
	return ret;
}