mem.c,v

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

head	1.3;
access;
symbols;
locks
	root:1.3; strict;
comment	@ * @;


1.3
date	2004.06.27.04.53.34;	author root;	state Exp;
branches;
next	1.2;

1.2
date	2004.06.07.12.42.38;	author root;	state Exp;
branches;
next	1.1;

1.1
date	2004.06.07.12.40.35;	author root;	state Exp;
branches;
next	;


desc
@init version
@


1.3
log
@removed a bug to make the last free block can be revoked
@
text
@/*

  Snixos Project version 1.0, 2003.6
  (C) Copyright 2003,2004,2005 Jockeyson,KeqianGao <Snallie@@tom.com>
  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 liablity 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 Snallie@@tom.com .

  mem.c   : heap memory management for the Snixos OS project
  Author  : snallie@@tom.com
  Time    : 2003.6
  
  note: function in C for management implemented :malloc(),free()
	 realloc(),calloc().
	 First-fit algorithm for malloc().
	 free() coalesces adjacent free blocks.
*/

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

    printf("\n");
    for (m = (mcb_t *) heap_bot; m != NULL && m->magic == MALLOC_MAGIC;
	 m = m->next) {
	printf("blk %x: %7d bytes %s\n", m, m->size,
	       m->used ? "used" : "free");
	if (m->used) {
	    blks_used++;
	    bytes_used += m->size;
	} else {
	    blks_free++;
	    bytes_free += m->size;
	}
    }
    printf("blks:  %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("heap_bot=0x%x, kbrk_addr=0x%x, heap_top=0x%x\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
//extern void getKey();
	getKey();
#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)
	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().   Otherwise,  or if free(ptr) has
       already been called before,  undefined  behaviour  occurs.
       If ptr is NULL, no operation is performed.
*/
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.  The contents will be  unchanged  to
       the minimum of the old and new sizes; newly allocated mem-
       ory will be uninitialized.  If ptr is NULL,  the  call  is
       equivalent  to malloc(size); if size is equal to zero, the
       call is equivalent to free(ptr).  Unless ptr is  NULL,  it
       must  have  been  returned by an earlier call to malloc(),
       calloc() or realloc().

       realloc() returns a pointer to the newly allocated memory,
       which is suitably aligned for any kind of variable and may
       be different from ptr, or NULL if the request fails or  if
       size  was  equal  to  0.   If realloc() fails the original
       block is left untouched - it is not freed or moved.
*/
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;
}

/* done */

#ifndef _IN_SNIXOS

void testmem()
{
    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();
}

main()
{
    initMem();
    testmem();
}

#endif				/*  _IN_SNIXOS */
@


1.2
log
@add symbol _IN_SNIXOS for selective compile, if want mem.c used in snixos kernel add #define _IN_SNIXOS at the head of mem.c
@
text
@d2 22
a23 15
*
*  Snixos Project version 1.0, 2003.6
*  (C) Copyright 2003-2004 Snallie Jockeyson <Snallie@@tom.com>
*  All Rights Reserved.
*  Distributed under the terms of the GNU General Public License.
*
*  mem.c   : heap memory management for the Snixos OS project
*  Author  : snallie@@tom.com
*  Time    : 2003.6
*  
*  note: function in C for management implemented :malloc(),free()
*	 realloc(),calloc().
*	 First-fit algorithm for malloc().
*	 free() coalesces adjacent free blocks.
*
d29 1
a29 2
#define _IN_SNIXOS	// if used in snixos ,uncomment this 
#define	HEAP_SIZE 2*1024*1024	/* totaly 1M bytes memory reserved as heap ranged from 0x10000 to 0x20000 */
d55 1
a55 1
	printf("blk %x: %d bytes %s\n", m, m->size,
d65 1
a65 1
    printf("blks:  %d used, %d free, %d total\n", blks_used,
d67 1
a67 1
    printf("bytes: %d used, %d free, %d total\n", bytes_used,
d76 4
d146 23
d170 1
a170 1

@


1.1
log
@Initial revision
@
text
@d22 1
d31 1
a31 1
    struct _malloc *next;	/* link to the next memory block released or occupied */
d47 4
a50 3
    for (m = (mcb_t *) heap_bot; m != NULL; m = m->next) {
	printf("blk %x: %d bytes %s\n", m,
	       m->size, m->used ? "used" : "free");
d67 1
a67 1
    if (total != kbrk_addr - heap_bot)
d69 1
a73 1

a78 1
    //static char *heap = (char *) HEAP_START_ADDR;     // 1M memory boundary, heap ranged from 1M~2M mem
d81 3
a83 4
    /* heap doesn't exist yet */
    if (heap_bot == NULL) {
	heap_bot = kbrk_addr = heap;
	heap_top = heap_bot + HEAP_SIZE;
a84 7

    new_brk = kbrk_addr + enlargement_size;
    if (new_brk < heap_bot)
	return NULL;		/* too low: return NULL */
    if (new_brk >= heap_top)
	return NULL;		/* too high: return NULL */

d101 1
a101 1
    if (size <= 0)
d103 3
a105 1
    total_size = size + sizeof(mcb_t);	/* size to be allocated actually ,include size of mcb */
d108 2
a109 2
    /* heap_bot == 0 == NULL if heap does not yet exist */
    if (m != NULL) {
d118 1
a118 1
	    if (size == m->size)
d120 1
a120 3
	    else {
		/* otherwise, we need an extra sizeof(mcb_t) bytes for the header
		   of a second, free block */
d128 1
a128 1
		n->used = 0;
d141 1
a141 1
    if (n == NULL)
d143 2
a144 1
    if (m != NULL)
d146 1
d183 1
a183 1
	if (n == m)
d185 1
d228 2
a229 3
    /* size == 0: free block */
    if (size == 0) {
	if (blk != NULL)
d231 1
a256 1

d264 1
a264 1
    if (m == NULL)
d266 1
a266 1
    else {
d272 1
a272 1
initMem()
d274 7
a280 2
    heap = (char *) HEAP_START_ADDR;	// 1M memory boundary, heap ranged from 1M~2M mem
    heap_bot = NULL;
d283 12
a294 1
//done
d296 2
d299 2
d302 2
d305 2
d308 18
d327 1
@