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