Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1139188
  • 博文数量: 196
  • 博客积分: 4141
  • 博客等级: 中将
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2009-03-21 20:04
文章存档

2019年(31)

2016年(1)

2014年(16)

2011年(8)

2010年(25)

2009年(115)

分类: C/C++

2009-05-10 14:03:33


#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;
}

阅读(1788) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~