Annotation of prex-old/usr/lib/prex/malloc/malloc.c, Revision 1.1
1.1 ! nbrk 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: */
! 29:
! 30: #include <prex/prex.h>
! 31: #include <sys/param.h>
! 32: #include <sys/syslog.h>
! 33: #include <string.h>
! 34: #include <errno.h>
! 35: #include "malloc.h"
! 36:
! 37: #ifdef _REENTRANT
! 38: static mutex_t malloc_lock = MUTEX_INITIALIZER;
! 39: #endif
! 40:
! 41: static struct header *more_core(size_t size);
! 42:
! 43: static struct header free_list; /* start of free list */
! 44: static struct header *scan_head; /* start point to scan */
! 45:
! 46: /*
! 47: * Simple memory allocator from K&R
! 48: */
! 49: void *
! 50: malloc(size_t size)
! 51: {
! 52: struct header *p, *prev;
! 53:
! 54: if (size == 0) /* sanity check */
! 55: return NULL;
! 56: size = ROUNDUP(size + sizeof(struct header));
! 57:
! 58: MALLOC_LOCK();
! 59:
! 60: if (scan_head == NULL) {
! 61: /* Initialize */
! 62: free_list.next = &free_list;
! 63: free_list.size = 0;
! 64: free_list.vm_size = 0;
! 65: scan_head = &free_list;
! 66: }
! 67: prev = scan_head;
! 68: for (p = prev->next;; prev = p, p = p->next) {
! 69: if (p->size >= size) { /* big enough */
! 70: if (p->size == size) /* exactly */
! 71: prev->next = p->next;
! 72: else { /* allocate tail end */
! 73: p->size -= size;
! 74: p = (struct header *)((u_long)p + p->size);
! 75: p->size = size;
! 76: p->vm_size = 0;
! 77: }
! 78: #ifdef CONFIG_MCHECK
! 79: p->magic = MALLOC_MAGIC;
! 80: #endif
! 81: scan_head = prev;
! 82: break;
! 83: }
! 84: if (p == scan_head) {
! 85: if ((p = more_core(size)) == NULL)
! 86: break;
! 87: }
! 88: }
! 89: MALLOC_UNLOCK();
! 90:
! 91: if (p == NULL) {
! 92: #ifdef CONFIG_MCHECK
! 93: sys_panic("malloc: out of memory");
! 94: #endif
! 95: return NULL;
! 96: }
! 97: return (void *)(p + 1);
! 98: }
! 99:
! 100: /*
! 101: * Create new block and insert it to the free list.
! 102: */
! 103: static struct header *more_core(size_t size)
! 104: {
! 105: struct header *p, *prev;
! 106:
! 107: size = PAGE_ALIGN(size);
! 108: if (vm_allocate(task_self(), (void *)&p, size, 1))
! 109: return NULL;
! 110: p->size = size;
! 111: p->vm_size = size;
! 112:
! 113: /* Insert to free list */
! 114: for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
! 115: if (prev >= prev->next && (p > prev || p < prev->next))
! 116: break;
! 117: }
! 118: p->next = prev->next;
! 119: prev->next = p;
! 120: scan_head = prev;
! 121: return prev;
! 122: }
! 123:
! 124: void
! 125: free(void *addr)
! 126: {
! 127: struct header *p, *prev;
! 128:
! 129: if (addr == NULL)
! 130: return;
! 131:
! 132: MALLOC_LOCK();
! 133: p = (struct header *)addr - 1;
! 134: #ifdef CONFIG_MCHECK
! 135: if (p->magic != MALLOC_MAGIC)
! 136: sys_panic("free: invalid pointer");
! 137: p->magic = 0;
! 138: #endif
! 139: for (prev = scan_head; !(p > prev && p < prev->next); prev = prev->next) {
! 140: if (prev >= prev->next && (p > prev || p < prev->next))
! 141: break;
! 142: }
! 143: if ((prev->next->vm_size == 0) && /* join to upper block */
! 144: ((u_long)p + p->size == (u_long)prev->next)) {
! 145: p->size += prev->next->size;
! 146: p->next = prev->next->next;
! 147: } else {
! 148: p->next = prev->next;
! 149: }
! 150: if ((p->vm_size == 0) && /* join to lower block */
! 151: ((u_long)prev + prev->size == (u_long)p)) {
! 152: prev->size += p->size;
! 153: prev->next = p->next;
! 154: } else {
! 155: prev->next = p;
! 156: }
! 157: /* Deallocate pool */
! 158: if (p->size == p->vm_size) {
! 159: prev->next = p->next;
! 160: vm_free(task_self(), p);
! 161: }
! 162: scan_head = prev;
! 163: MALLOC_UNLOCK();
! 164: }
! 165:
! 166: #ifdef CONFIG_MSTAT
! 167: void
! 168: mstat(void)
! 169: {
! 170: struct header *p;
! 171:
! 172: syslog(LOG_INFO, "mstat: task=%x\n", task_self());
! 173: for (p = free_list.next; p != &free_list; p = p->next) {
! 174: syslog(LOG_INFO, "mstat: addr=%x size=%d next=%x\n", p, p->size, p->next);
! 175: }
! 176: }
! 177: #endif
CVSweb