mem.c

一个小型的操作系统,采用gcc进行开发,几千行的代码,方便初学者学习

/*
*  Snixos Project version 1.0, 2003.6
*  (C) Copyright 2003,2004,2005 Jockeyson,KeqiangGao <[e-mail]>
*  All Rights Reserved.
*  Distributed under the terms of the GNU General Public License.
*
*  This program is a free and open source software and you can redistribute 
*  it and/or modify it under the terms of the GNU General Public License as
*  published by the Free Software Foundation. As no any liability is assumed 
*  for any incidental or consequential damages in connection with the 
*  information or program fragments contained herein,so any exception arised
*  is at your own risk. It is ABSOLUTELY WITHOUT ANY WARRANTY.
*  Bug report please send to [e-mail] .
*/
/*
  mem.c   : heap memory management for the Snixos OS project
  Author  : [e-mail]
  Time    : 2003.6
  
  note: function in C for management implemented :malloc(),free() realloc(),calloc().
        first-fit algorithm adopted when allocating memory 
*/

#include <string.h>		/* memset() memcpy() */
#include <stdio.h>		/* printf() */

#define	HEAP_SIZE 4*1024*1024	/* totaly 4M bytes memory reserved as heap ranged from 0x10000 to +4M */
#define	MALLOC_MAGIC	0x3A7C	/* must be < 0x8000, only 15 bits long */
#define HEAP_START_ADDR 0X100000	/* !! heap start at 0x100000 !! */
#define BLK_OCCUPIED 1
#define BLK_RELEASED 0

typedef struct _malloc {
    size_t size;		/* size of this block allocated */
    struct _malloc *next;	/* link to the next memory block whatever released or occupied */
    unsigned magic:15;		/* magic word for valid mcb */
    unsigned used:1;		/* status bit for released(0) or occupied(1) */
} mcb_t;			/* memory control block */

static char *heap_bot = 0, *kbrk_addr, *heap_top;
char *heap;

void dump_heap(void)
{
    unsigned blks_used = 0, blks_free = 0;
    size_t bytes_used = 0, bytes_free = 0;
    mcb_t *m;
    int total, i = 0;

    printf("\n");
    for (m = (mcb_t *) heap_bot; m != NULL && m->magic == MALLOC_MAGIC;
	 m = m->next, i++) {
	printf("block %2d 0x%8X: %7d bytes %s\n", i, m, m->size,
	       m->used ? "used" : "free");
	if (m->used) {
	    blks_used++;
	    bytes_used += m->size;
	} else {
	    blks_free++;
	    bytes_free += m->size;
	}
    }
    printf("blocks:  %8d used, %8d free, %8d total\n", blks_used,
	   blks_free, blks_used + blks_free);
    printf("bytes:   %8d used, %8d free, %8d total\n", bytes_used,
	   bytes_free, bytes_used + bytes_free);
    printf("bottom=0x%08x, break=0x%08x, top=0x%08x\n",
	   heap_bot, kbrk_addr, heap_top);
    total = (bytes_used + bytes_free) +
	(blks_used + blks_free) * sizeof(mcb_t);
    if (total != kbrk_addr - heap_bot) {
	printf("MEMERR: some heap memory is not accounted for\n");
    }
#ifdef _IN_SNIXOS
    waitAnyKey();
#endif
}

/* 
void *kbrk( int enlargement_size )
purpose:steal a new block, whose size is enlargement_size, from heap, 
	enlargement_size include the user block and mcb
*/
static void *kbrk(int enlargement_size)
{
    char *new_brk, *old_brk;

    new_brk = kbrk_addr + enlargement_size;
    if (new_brk < heap_bot || new_brk >= heap_top) {
	return NULL;		/* too low or too high: return NULL */
    }
    /* success: adjust kbrk_addr value */
    old_brk = kbrk_addr;
    kbrk_addr = new_brk;
    return old_brk;		/* return old brk value */
}

/* 
void *kmalloc(size_t size)
	allcating a memory block in size ,if allocated ok then return
	the block address, otherwise return NULL.
	argument size should be any positive integer. 
*/
void *kmalloc(size_t size)
{
    unsigned total_size;
    mcb_t *m, *n;
    int delta;

    if (size <= 0) {
	return NULL;
    }
    total_size = size + sizeof(mcb_t);	/* size to be allocated, actually ,include size of mcb */

    /* search heap for free block with the FIRST-FIT algorithm */
    m = (mcb_t *) heap_bot;
    /* m== kbrk_addr if the first time to invoke this */
    if (m != NULL && (char *) m != kbrk_addr) {	/*  not the first time to call kmalloc */
	if (m->magic != MALLOC_MAGIC) {
	    printf("MEMERR: kernel heap is corrupt in kmalloc()\n");
	    return NULL;
	}
	for (; m->next != NULL; m = m->next) {
	    if (m->used)	/* BLK_OCCUPIED */
		continue;
	    /* size == m->size is a perfect fit */
	    if (size == m->size) {
		m->used = BLK_OCCUPIED;
	    } else {		/* otherwise, we need an extra sizeof(mcb_t) bytes for the header of a second, free block */
		if (total_size > m->size)
		    continue;
		/* create a new, smaller free block after this one, n=new blk's mcb addr */
		n = (mcb_t *) ((char *) m + total_size);
		n->size = m->size - total_size;
		n->next = m->next;
		n->magic = MALLOC_MAGIC;
		n->used = BLK_RELEASED;
		/* reduce the size of this block and mark it used */
		m->size = size;
		m->next = n;
		m->used = BLK_OCCUPIED;
	    }
	    return (char *) m + sizeof(mcb_t);
	}
	/* if the last free block may fit */
	if (m->next == NULL && m->used == BLK_RELEASED) {
	    if (size == m->size) {	/* just fit , got it */
		m->used = BLK_OCCUPIED;
		return (char *) m + sizeof(mcb_t);
	    } else {
		if (total_size > m->size)	/* not fit , new break */
		    goto newBrk;
		else {		/* split block */
		    /* create a new, smaller free block after this one, n=new blk's mcb addr */
		    n = (mcb_t *) ((char *) m + total_size);
		    n->size = m->size - total_size;
		    n->next = m->next;
		    n->magic = MALLOC_MAGIC;
		    n->used = BLK_RELEASED;
		    /* reduce the size of this block and mark it used */
		    m->size = size;
		    m->next = n;
		    m->used = BLK_OCCUPIED;
		    return (char *) m + sizeof(mcb_t);
		}
	    }
	}
    }

  newBrk:
    /* use kbrk() to enlarge heap */
    delta = total_size;
    n = kbrk(delta);
    if (n == NULL) {
	return NULL;
    }
    if ((char *) m != kbrk_addr) {	/* not the first time to call kmalloc */
	m->next = n;
    }
    n->size = size;
    n->magic = MALLOC_MAGIC;
    n->used = BLK_OCCUPIED;
    n->next = NULL;		/* NULL indicate n is the last block */

    return (char *) n + sizeof(mcb_t);	/* return the starting address of the block user required */
}

/*
       void free(void *ptr);
       free()  frees  the  memory  space pointed to by ptr, which
       must have been returned by a previous  call  to  malloc(),
       calloc()  or  realloc().   
*/
void kfree(void *blk)
{
    mcb_t *m, *n;

    /* get address of blk's mcb */
    m = (mcb_t *) ((char *) blk - sizeof(mcb_t));
    if (m->magic != MALLOC_MAGIC) {
	printf
	    ("MEMERR: attempt to kfree() block at 0x%x with bad magic\n",
	     blk);
	return;
    }
    /* find this block in the heap */
    n = (mcb_t *) heap_bot;
    if (n->magic != MALLOC_MAGIC) {
	printf("MEMERR: kernel heap is corrupt in kfree()\n");
	return;
    }
    for (; n != NULL; n = n->next) {
	if (n == m) {
	    break;
	}
    }
    /* not found? bad pointer or no heap or something else? */
    if (n == NULL) {
	printf
	    ("MEMERR: attempt to kfree() block at 0x%x that is not in the heap\n",
	     blk);
	return;
    }
    m->used = BLK_RELEASED;	/* free the block */

    /* coalesce adjacent free blocks */
    for (m = (mcb_t *) heap_bot; m != NULL; m = m->next) {
	while (!m->used && m->next != NULL && !m->next->used) {
	    m->size += sizeof(mcb_t) + m->next->size;	/* resize this block */
	    m->next = m->next->next;	/* merge with next block */
	}
    }
}

/*
       void *realloc(void *ptr, size_t size);
       realloc()  changes the size of the memory block pointed to
       by ptr to size bytes.  
*/
void *krealloc(void *blk, size_t size)
{
    void *new_blk;
    mcb_t *m;

    if (size == 0) {		/* size == 0: free block */
	if (blk != NULL) {
	    kfree(blk);
	}
	new_blk = NULL;
    } else {
	/* allocate new block */
	new_blk = kmalloc(size);
	/* if allocation OK, and if old block exists, copy old block to new */
	if (new_blk != NULL && blk != NULL) {
	    m = (mcb_t *) ((char *) blk - sizeof(mcb_t));
	    if (m->magic != MALLOC_MAGIC) {
		printf
		    ("MEMERR: attempt to krealloc() block at 0x%x with bad magic\n",
		     blk);
		kfree(new_blk);
		return NULL;
	    }

	    /* copy minimum of old and new block sizes */
	    memcpy(new_blk, blk, (size > m->size) ? m->size : size);
	    kfree(blk);		/* free the old block */
	}
    }
    return new_blk;
}

/* 
 void *calloc(size_t nmemb, size_t size);
 calloc() allocates memory for an array of nmemb elements of size bytes each
 and returns a pointer to the allocated memory.  The memory is set to  zero.
*/
void *kcalloc(size_t nmemb, size_t size)
{
    char *m;
    m = kmalloc(nmemb * size);
    if (m == NULL) {
	return NULL;
    } else {
	memset(m, '\0', nmemb * size);
	return m;
    }
}

void initMem()
{
#ifdef _IN_SNIXOS
    heap = (char *) HEAP_START_ADDR;	/* memory boundary, heap ranged from bot~top  */
#else
    heap = (char *) malloc(HEAP_SIZE);
#endif
    heap_bot = kbrk_addr = heap;
    heap_top = heap_bot + HEAP_SIZE;
}

void memdump()
{
    void *b1, *b2, *b3;

    dump_heap();

    b1 = kmalloc(42);
    dump_heap();

    b2 = kmalloc(23);
    dump_heap();

    b3 = kcalloc(7, 1);
    dump_heap();

    b2 = krealloc(b2, 24);
    dump_heap();

    kfree(b1);
    dump_heap();

    b1 = kmalloc(5);
    dump_heap();

    kfree(b2);
    dump_heap();

    kfree(b3);
    dump_heap();

    kfree(b1);
    dump_heap();
}
/* done */

#ifndef _IN_SNIXOS

main()
{
    initMem();
    memdump();
}

#endif				/*  _IN_SNIXOS */