scoutos / prex-0.9.0 / usr / lib / prex / malloc / malloc.c @ 03e9c04a
History | View | Annotate | Download (4.55 KB)
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 <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" |
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 *)((char *)p + p->size); |
77 |
p->size = size; |
78 |
p->vm_size = 0;
|
79 |
} |
80 |
#ifdef DEBUG_MALLOC
|
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 DEBUG_MALLOC
|
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 = round_page(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 DEBUG_MALLOC
|
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 |
((char *)p + p->size == (char *)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 |
((char *)prev + prev->size == (char *)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 DEBUG_MALLOC
|
169 |
void
|
170 |
mstat(void)
|
171 |
{ |
172 |
struct header *p;
|
173 |
|
174 |
printf("mstat: task=%x\n", task_self());
|
175 |
for (p = free_list.next; p != &free_list; p = p->next) {
|
176 |
printf("mstat: addr=%x size=%d next=%x\n", p, p->size, p->next);
|
177 |
} |
178 |
} |
179 |
#endif
|