1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
28 /* All Rights Reserved */
29
30 #include <sys/types.h>
31
32
33 /*
34 * Simplified version of malloc(), free() and realloc(), to be linked with
35 * utilities that use [s]brk() and do not define their own version of the
36 * routines.
37 *
38 * The algorithm used to get extra memory space by mmap'ing /dev/zero. This
39 * breaks if the application closes the open descriptor, so now it uses
40 * mmap's MAP_ANON feature.
41 *
42 * Each call to mmap() creates a page. The pages are linked in a list.
43 * Each page is divided in blocks. There is at least one block in a page.
44 * New memory chunks are allocated on a first-fit basis.
45 * Freed blocks are joined in larger blocks. Free pages are unmapped.
46 */
47 #include <stdlib.h>
48 #include <sys/types.h>
49 #include <sys/mman.h>
50 #include <fcntl.h>
51 #include <errno.h>
52 #include <unistd.h>
53 #include <thread.h>
54 #include <pthread.h>
55 #include <synch.h>
56 #include <string.h>
57
58 static mutex_t lock = DEFAULTMUTEX;
59
60 struct block {
61 size_t size; /* Space available for user */
62 struct page *page; /* Backwards reference to page */
63 int status;
64 struct block *next;
65 void *memstart[1];
66 };
67
68 struct page {
69 size_t size; /* Total page size (incl. header) */
70 struct page *next;
71 struct block block[1];
72 };
73
74 #define FREE 0
75 #define BUSY 1
76
77 #define HDR_BLOCK (sizeof (struct block) - sizeof (void *))
78 #define HDR_PAGE (sizeof (struct page) - sizeof (void *))
79 #define MINSZ sizeof (double)
80
81 /* for convenience */
82 #ifndef NULL
83 #define NULL (0)
84 #endif
85
86 struct page *memstart;
87 static int pagesize;
88 static void defrag(struct page *);
89 static void split(struct block *, size_t);
90 static void *malloc_unlocked(size_t);
91 static size_t align(size_t, int);
92
93 void *
malloc(size_t size)94 malloc(size_t size)
95 {
96 void *retval;
97 (void) mutex_lock(&lock);
98 retval = malloc_unlocked(size);
99 (void) mutex_unlock(&lock);
100 return (retval);
101 }
102
103
104 static void *
malloc_unlocked(size_t size)105 malloc_unlocked(size_t size)
106 {
107 struct block *block;
108 struct page *page;
109
110 if (pagesize == 0)
111 pagesize = (int)sysconf(_SC_PAGESIZE);
112
113 size = align(size, MINSZ);
114
115 /*
116 * Try to locate necessary space
117 */
118 for (page = memstart; page; page = page->next) {
119 for (block = page->block; block; block = block->next) {
120 if (block->status == FREE && block->size >= size)
121 goto found;
122 }
123 }
124 found:
125
126 /*
127 * Need to allocate a new page
128 */
129 if (!page) {
130 size_t totsize = size + HDR_PAGE;
131 size_t totpage = align(totsize, pagesize);
132
133 if ((page = (struct page *)mmap(0, totpage,
134 PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, -1, 0))
135 == MAP_FAILED)
136 return (0);
137
138 page->next = memstart;
139 memstart = page;
140 page->size = totpage;
141 block = page->block;
142 block->next = 0;
143 block->status = FREE;
144 block->size = totpage - HDR_PAGE;
145 block->page = page;
146 }
147
148 split(block, size);
149
150 block->status = BUSY;
151 return (&block->memstart);
152 }
153
154 void *
realloc(void * ptr,size_t size)155 realloc(void *ptr, size_t size)
156 {
157 struct block *block;
158 size_t osize;
159 void *newptr;
160
161 (void) mutex_lock(&lock);
162 if (ptr == NULL) {
163 newptr = malloc_unlocked(size);
164 (void) mutex_unlock(&lock);
165 return (newptr);
166 }
167 block = (struct block *)((char *)ptr - HDR_BLOCK);
168 size = align(size, MINSZ);
169 osize = block->size;
170
171 /*
172 * Join block with next one if it is free
173 */
174 if (block->next && block->next->status == FREE) {
175 block->size += block->next->size + HDR_BLOCK;
176 block->next = block->next->next;
177 }
178
179 if (size <= block->size) {
180 split(block, size);
181 (void) mutex_unlock(&lock);
182 return (ptr);
183 }
184
185 newptr = malloc_unlocked(size);
186 (void) memcpy(newptr, ptr, osize);
187 block->status = FREE;
188 defrag(block->page);
189 (void) mutex_unlock(&lock);
190 return (newptr);
191 }
192
193 void
free(void * ptr)194 free(void *ptr)
195 {
196 struct block *block;
197
198 (void) mutex_lock(&lock);
199 if (ptr == NULL) {
200 (void) mutex_unlock(&lock);
201 return;
202 }
203 block = (struct block *)((char *)ptr - HDR_BLOCK);
204 block->status = FREE;
205
206 defrag(block->page);
207 (void) mutex_unlock(&lock);
208 }
209
210 /*
211 * Align size on an appropriate boundary
212 */
213 static size_t
align(size_t size,int bound)214 align(size_t size, int bound)
215 {
216 if (size < bound)
217 return ((size_t)bound);
218 else
219 return (size + bound - 1 - (size + bound - 1) % bound);
220 }
221
222 static void
split(struct block * block,size_t size)223 split(struct block *block, size_t size)
224 {
225 if (block->size > size + sizeof (struct block)) {
226 struct block *newblock;
227 newblock = (struct block *)((char *)block + HDR_BLOCK + size);
228 newblock->next = block->next;
229 block->next = newblock;
230 newblock->status = FREE;
231 newblock->page = block->page;
232 newblock->size = block->size - size - HDR_BLOCK;
233 block->size = size;
234 }
235 }
236
237 /*
238 * Defragmentation
239 */
240 static void
defrag(struct page * page)241 defrag(struct page *page)
242 {
243 struct block *block;
244
245 for (block = page->block; block; block = block->next) {
246 struct block *block2;
247
248 if (block->status == BUSY)
249 continue;
250 for (block2 = block->next; block2 && block2->status == FREE;
251 block2 = block2->next) {
252 block->next = block2->next;
253 block->size += block2->size + HDR_BLOCK;
254 }
255 }
256
257 /*
258 * Free page
259 */
260 if (page->block->size == page->size - HDR_PAGE) {
261 if (page == memstart)
262 memstart = page->next;
263 else {
264 struct page *page2;
265 for (page2 = memstart; page2->next;
266 page2 = page2->next) {
267 if (page2->next == page) {
268 page2->next = page->next;
269 break;
270 }
271 }
272 }
273 (void) munmap((caddr_t)page, page->size);
274 }
275 }
276
277 static void
malloc_prepare()278 malloc_prepare()
279 {
280 (void) mutex_lock(&lock);
281 }
282
283 static void
malloc_release()284 malloc_release()
285 {
286 (void) mutex_unlock(&lock);
287 }
288
289 #pragma init(malloc_init)
290 static void
malloc_init(void)291 malloc_init(void)
292 {
293 (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
294 }
295