Prex Home / Browse Source - Prex Version: 0.9.0

root/usr/lib/prex/malloc/malloc.c

DEFINITIONS

1. malloc
2. more_core
3. free
4. mstat

   1 /*
   2  * Copyright (c) 2005-2007, Kohsuke Ohtani
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the author nor the names of any co-contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  30 #include <sys/types.h>
  31 #include <sys/prex.h>
  32 #include <sys/param.h>
  33 #include <sys/syslog.h>
  34 #include <string.h>
  35 #include <errno.h>
  36 #include <stdlib.h>
  37 #include "malloc.h"
  39 #ifdef _REENTRANT
  40 static mutex_t malloc_lock = MUTEX_INITIALIZER;
  41 #endif
  43 static struct header *more_core(size_t size);
  45 static struct header free_list;         /* start of free list */
  46 static struct header *scan_head;        /* start point to scan */
  48 /*
  49  * Simple memory allocator from K&R
  50  */
  51 void *
malloc(size_t size)
  53 {
  54         struct header *p, *prev;
  56         if (size == 0)          /* sanity check */
  57                 return NULL;
size = ROUNDUP(size + sizeof(struct header));
MALLOC_LOCK();
  62         if (scan_head == NULL) {
  63                 /* Initialize */
free_list.next = &free_list;
free_list.size = 0;
free_list.vm_size = 0;
scan_head = &free_list;
  68         }
prev = scan_head;
  70         for (p = prev->next;; prev = p, p = p->next) {
  71                 if (p->size >= size) {  /* big enough */
  72                         if (p->size == size)    /* exactly */
prev->next = p->next;
  74                         else {                  /* allocate tail end */
p->size -= size;
p = (struct header *)((char *)p + p->size);
p->size = size;
p->vm_size = 0;
  79                         }
  80 #ifdef DEBUG_MALLOC
p->magic = MALLOC_MAGIC;
  82 #endif
scan_head = prev;
  84                         break;
  85                 }
  86                 if (p == scan_head) {
  87                         if ((p = more_core(size)) == NULL)
  88                                 break;
  89                 }
  90         }
MALLOC_UNLOCK();
  93         if (p == NULL) {
  94 #ifdef DEBUG_MALLOC
sys_panic("malloc: out of memory");
  96 #endif
  97                 return NULL;
  98         }
  99         return (void *)(p + 1);
 100 }
 102 /*
 103  * Create new block and insert it to the free list.
 104  */
 105 static struct header *more_core(size_t size)
 106 {
 107         struct header *p, *prev;
size = round_page(size);
 110         if (vm_allocate(task_self(), (void *)&p, size, 1))
 111                 return NULL;
p->size = size;
p->vm_size = size;
 115         /* Insert to free list */
 116         for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
 117                 if (prev >= prev->next && (p > prev || p < prev->next))
 118                         break;
 119         }
p->next = prev->next;
prev->next = p;
scan_head = prev;
 123         return prev;
 124 }
 126 void
free(void *addr)
 128 {
 129         struct header *p, *prev;
 131         if (addr == NULL)
 132                 return;
MALLOC_LOCK();
p = (struct header *)addr - 1;
 136 #ifdef DEBUG_MALLOC
 137         if (p->magic != MALLOC_MAGIC)
sys_panic("free: invalid pointer");
p->magic = 0;
 140 #endif
 141         for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
 142                 if (prev >= prev->next && (p > prev || p < prev->next))
 143                         break;
 144         }
 145         if ((prev->next->vm_size == 0) &&       /* join to upper block */
 146             ((char *)p + p->size == (char *)prev->next)) {
p->size += prev->next->size;
p->next = prev->next->next;
 149         } else {
p->next = prev->next;
 151         }
 152         if ((p->vm_size == 0) &&        /* join to lower block */
 153             ((char *)prev + prev->size == (char *)p)) {
prev->size += p->size;
prev->next = p->next;
 156         } else {
prev->next = p;
 158         }
 159         /* Deallocate pool */
 160         if (p->size == p->vm_size) {
prev->next = p->next;
vm_free(task_self(), p);
 163         }
scan_head = prev;
MALLOC_UNLOCK();
 166 }
 168 #ifdef DEBUG_MALLOC
 169 void
 170 mstat(void)
 171 {
 172         struct header *p;
printf("mstat: task=%x\n", task_self());
 175         for (p = free_list.next; p != &free_list; p = p->next) {
printf("mstat: addr=%x size=%d next=%x\n", p, p->size, p->next);
 177         }
 178 }
 179 #endif