Annotation of prex-old/usr/lib/prex/malloc/malloc.c, Revision 1.1.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