|
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "list.h"
#include "hash.h"
#include "min_malloc.h"
#define NUMBER_OF_LIST_IN_MALLOC 3
#define MALLOC_MANAGE_LIST 0
#define MALLOC_FREE_LIST 1
#define MALLOC_USED_LIST 2
#define MALLOC_FREE_SIZE_INC 1024
#define MALLOC_FREE_HASH_SIZE MAX_HASH_HEADER_LEN
#define MALLOC_USED_HASH_SIZE MAX_HASH_HEADER_LEN
typedef unsigned long uint_32;
#define offsetof(s,m) (size_t)&(((s *)0)->m)
#define container_of(TYPE, MEMBER, ADDR) \
(size_t)((size_t)ADDR - offsetof(TYPE, MEMBER))
#define DATA_ALIGN_16(x) (((x) + 0xF) & 0xFFFFFFF0)
#define MALLOC_HEADER sizeof(struct malloc_header)
#define MALLOC_SIZE_INIT 10000000
#define MALLOC_SIZE(x) ((x) >= (MALLOC_SIZE_INIT - MALLOC_HEADER) ? (2 * (x)) : MALLOC_SIZE_INIT)
FILE *fp = fopen("malloc.log", "w");
static char *malloc_mem = NULL;
static struct DListHeader malloc_list;
static struct hash_struct_info malloc_hash_free_head;
static struct hash_struct_info malloc_hash_used_head;
struct malloc_header
{
struct DListNode list[NUMBER_OF_LIST_IN_MALLOC];
uint_32 addr;
int size;
};
static int malloc_free_cmp(void *src1, void *src2)
{
struct malloc_header * p1 = NULL;
struct malloc_header * p2 = NULL;
int *size = NULL;
if (src1 == NULL)
{
printf("The src1 is NULL.\n");
exit(1);
}
if (src2 == NULL)
{
printf("The src2 is NULL.\n");
exit(1);
}
p1 = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], src1);
p2 = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], src2);
return p1->size < p2->size;
}
static int malloc_used_cmp(void *src1, void *src2)
{
struct malloc_header * p1 = NULL;
struct malloc_header * p2 = NULL;
if (src1 == NULL)
{
printf("The src1 is NULL.\n");
exit(1);
}
if (src2 == NULL)
{
printf("The src2 is NULL.\n");
exit(1);
}
p1 = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_USED_LIST], src1);
p2 = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_USED_LIST], src2);
return p1->addr != p2->addr;
}
static int malloc_free_hash(void *src)
{
struct malloc_header * p = NULL;
if (src == NULL)
{
printf("The src1 is NULL.\n");
exit(1);
}
p = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], src);
return ((p->size / MALLOC_FREE_SIZE_INC) >= MALLOC_FREE_HASH_SIZE) ? (MALLOC_FREE_HASH_SIZE - 1): (p->size / MALLOC_FREE_SIZE_INC);
}
static int malloc_used_hash(void *src)
{
struct malloc_header * p = NULL;
if (src == NULL)
{
printf("The src1 is NULL.\n");
exit(1);
}
p = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_USED_LIST], src);
return p->addr;
}
static struct DListNode * malloc_list_search(struct hash_struct_info *head, struct DListNode *src)
{
struct DListNode *plink;
struct DListHeader *header;
if (head == NULL)
{
printf("The hash_struct_info head is NULL.\n");
exit(1);
}
if (src == NULL)
{
printf("The src is NULL\n");
exit(1);
}
header = head->get_list_header(head, src);
do
{
plink = DList_get_next(header, &(header->head));
while(plink != NULL)
{
if (head->cmp((void *)plink, (void *)src) == 0)
return plink;
plink = DList_get_next(header, plink);
}
header += 1;
}while(header < (head->hash_list + head->size));
return NULL;
}
int malloc_debug()
{
int i = 0;
int malloc_sum = 0;
int malloc_free = 0;
struct DListNode *p = NULL;
struct malloc_header * malloc_point = NULL;
if (0)
{
p = &malloc_list.head;
i = 0;
while (p)
{
++i;
malloc_point = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_MANAGE_LIST], p);
if (p != &malloc_list.head)
{
malloc_sum += malloc_point->size;
if (malloc_point->list[MALLOC_FREE_LIST].pre != NULL && malloc_point->list[MALLOC_FREE_LIST].next != NULL)
malloc_free += malloc_point->size;
}
fprintf(fp, "malloc_list :NO.%d %8x %8x %8x size:%d\n", i, (uint_32)p, (uint_32)p->pre, (uint_32)p->next, malloc_point->size);
p = DList_get_next(&malloc_list, p);
}
}
fprintf(fp, "The sum of malloc: %d The sum of free: %d\n", malloc_sum, malloc_free);
fprintf(fp, "\n");
return 0;
}
void * min_malloc(int size)
{
struct malloc_header malloc_temp;
struct malloc_header *malloc_free = NULL;
struct malloc_header *malloc_node = NULL;
struct DListNode *node = NULL;
void *p = NULL;
/*long long qstart, qend;
LARGE_INTEGER litmp;
QueryPerformanceCounter(&litmp);
qstart = litmp.QuadPart;*/
size = DATA_ALIGN_16(size);
/* first call min_malloc, and apply a large block */
if (malloc_mem == NULL)
{
malloc_mem = (char *)malloc(MALLOC_SIZE(size));
malloc_node = (struct malloc_header *)malloc_mem;
malloc_node->addr = (uint_32)malloc_mem;
malloc_node->size = MALLOC_SIZE(size);
initialize_Dlist_header(&malloc_list);
DList_add_tail(&malloc_list, &malloc_node->list[MALLOC_MANAGE_LIST]);
hash_init(&malloc_hash_free_head, malloc_free_hash, malloc_free_cmp);
hash_change_function(&malloc_hash_free_head, HASH_MEMBER_SEARCH, (void (__cdecl *)(void))malloc_list_search);
malloc_hash_free_head.insert_node(&malloc_hash_free_head, &(malloc_node->list[MALLOC_FREE_LIST]));
hash_init(&malloc_hash_used_head, malloc_used_hash, malloc_used_cmp);
}
// search the first enough memory
malloc_temp.size = size + (int)MALLOC_HEADER;
node = malloc_hash_free_head.search_node(&malloc_hash_free_head, &malloc_temp.list[MALLOC_FREE_LIST]);
if (node == NULL)
{
return NULL;
}
node = malloc_hash_free_head.delete_node(&malloc_hash_free_head, node);
malloc_node = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], node);
/*QueryPerformanceCounter(&litmp);
qend = litmp.QuadPart;
printf("%lld\n", qend - qstart);*/
if (malloc_node->size <= size + (int)MALLOC_HEADER * 2)
{
malloc_hash_used_head.insert_node(&malloc_hash_used_head, &malloc_node->list[MALLOC_USED_LIST]);
p = (void *)(malloc_node->addr + MALLOC_HEADER);
}
else
{
p = (void *)(malloc_node->addr + MALLOC_HEADER);
malloc_free = (struct malloc_header *)(malloc_node->addr + MALLOC_HEADER + size);
malloc_free->addr = malloc_node->addr + MALLOC_HEADER + size;
malloc_free->size = malloc_node->size - MALLOC_HEADER - size;
malloc_node->size = MALLOC_HEADER + size;
malloc_hash_used_head.insert_node(&malloc_hash_used_head, &malloc_node->list[MALLOC_USED_LIST]);
malloc_hash_free_head.insert_node(&malloc_hash_free_head, &malloc_free->list[MALLOC_FREE_LIST]);
DList_add_after(&malloc_list, &malloc_node->list[MALLOC_MANAGE_LIST], &malloc_free->list[MALLOC_MANAGE_LIST]);
}
return p;
}
void min_free(void *addr)
{
int coalesce_case = 0;
struct DListNode *node = NULL;
struct malloc_header malloc_temp;
struct malloc_header * malloc_node = NULL;
struct malloc_header * malloc_free_pre = NULL;
struct malloc_header * malloc_free_next = NULL;
if (addr == NULL)
return;
/* find out the management structure */
malloc_temp.addr = (uint_32)addr - (uint_32)MALLOC_HEADER;
node = malloc_hash_used_head.search_node(&malloc_hash_used_head, &malloc_temp.list[MALLOC_USED_LIST]);
if (node == NULL)
{
printf("The bad address!\n");
exit(1);
}
node = malloc_hash_used_head.delete_node(&malloc_hash_used_head, node);
malloc_node = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_USED_LIST], node);
/* coalesce with pre */
malloc_free_pre = (struct malloc_header *)DList_get_pre(&malloc_list, &malloc_node->list[MALLOC_MANAGE_LIST]);
if (malloc_free_pre != NULL && malloc_free_pre->list[MALLOC_FREE_LIST].next != NULL && malloc_free_pre->list[MALLOC_FREE_LIST].pre != NULL)
coalesce_case |= 1;
/* coalesce with next */
malloc_free_next = (struct malloc_header *)DList_get_next(&malloc_list, &malloc_node->list[MALLOC_MANAGE_LIST]);
if (malloc_free_next != NULL && malloc_free_next->list[MALLOC_FREE_LIST].next != NULL && malloc_free_next->list[MALLOC_FREE_LIST].pre != NULL)
coalesce_case |= 2;
switch(coalesce_case)
{
case 0: /* coalesce with nothing */
case 3: /* coalesce with both */
case 1: /* coalesce with pre */
if (coalesce_case & 1)
{
node = malloc_hash_free_head.delete_node(&malloc_hash_free_head, &malloc_free_pre->list[MALLOC_FREE_LIST]);
malloc_free_pre = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], node);
malloc_free_pre->size += malloc_node->size;
DList_delete_node(&malloc_list, &malloc_node->list[MALLOC_MANAGE_LIST]);
malloc_node = malloc_free_pre;
}
case 2: /* coalesce with next */
if (coalesce_case & 2)
{
node = malloc_hash_free_head.delete_node(&malloc_hash_free_head, &malloc_free_next->list[MALLOC_FREE_LIST]);
malloc_free_next = (struct malloc_header *)container_of(struct malloc_header, list[MALLOC_FREE_LIST], node);
malloc_node->size += malloc_free_next->size;
DList_delete_node(&malloc_list, &malloc_free_next->list[MALLOC_MANAGE_LIST]);
}
malloc_hash_free_head.insert_node(&malloc_hash_free_head, &malloc_node->list[MALLOC_FREE_LIST]);
break;
}
return;
}
|
