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 2009 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /*
28 * Copyright (c) 1988 AT&T
29 * All Rights Reserved
30 */
31
32 /*
33 * Simplified version of malloc(), calloc() and free(), to be linked with
34 * utilities that use [s]brk() and do not define their own version of the
35 * routines.
36 * The algorithm maps /dev/zero to get extra memory space.
37 * Each call to mmap() creates a page. The pages are linked in a list.
38 * Each page is divided in blocks. There is at least one block in a page.
39 * New memory chunks are allocated on a first-fit basis.
40 * Freed blocks are joined in larger blocks. Free pages are unmapped.
41 */
42
43 #include <stdlib.h>
44 #include <sys/types.h>
45 #include <sys/mman.h>
46 #include <sys/debug.h>
47 #include <memory.h>
48 #include "_rtld.h"
49 #include "msg.h"
50
51 struct block {
52 size_t size; /* Space available for user */
53 struct page *page; /* Backwards reference to page */
54 int status;
55 struct block *next;
56 void * memstart[1];
57 };
58
59 struct page {
60 size_t size; /* Total page size (incl. header) */
61 struct page *next;
62 struct block block[1];
63 };
64
65 #define FREE 0
66 #define BUSY 1
67
68 #define HDR_BLOCK (sizeof (struct block) - sizeof (void *))
69 #define HDR_PAGE (sizeof (struct page) - sizeof (void *))
70
71 static struct page *memstart;
72
73 #if DEBUG
74 /*
75 * When built for debugging, scribble a pattern over newly allocated and
76 * freed memory.
77 */
78 #define NEWMEM 0
79 #define FREMEM 1
80
81 /* LINTED */
82 const ulong_t patterns[] = {
83 (ulong_t)0xbaddcafebaddcafeULL, (ulong_t)0xdeadbeefdeadbeefULL
84 };
85
86 static void
87 scribble(ulong_t *membgn, int pattern, size_t size)
88 {
89 size_t memsize = size / sizeof (ulong_t);
90
91 while (memsize--) {
92 if (pattern == FREMEM)
93 ASSERT(*membgn != patterns[pattern]);
94 *membgn++ = patterns[pattern];
95 }
96 }
97 #endif
98
99 /*
100 * Defragmentation
101 */
102 void
103 defrag()
104 {
105 struct page *page;
106 Aliste idx;
107
108 for (APLIST_TRAVERSE(free_alp, idx, page)) {
109 struct block *block;
110
111 for (block = page->block; block; block = block->next) {
112 struct block *block2;
113
114 if (block->status == BUSY)
115 continue;
116 for (block2 = block->next; block2 &&
117 block2->status == FREE; block2 = block2->next) {
118 block->next = block2->next;
119 block->size += block2->size + HDR_BLOCK;
120 }
121 }
122
123 /*
124 * If a page becomes free, leave it, and save the unmapping
125 * expense, as we'll probably come back and reclaim the page
126 * for later malloc activity.
127 *
128 * Free the defrag index.
129 */
130 aplist_delete(free_alp, &idx);
131 }
132 }
133
134 static void
135 split(struct block *block, size_t size)
136 {
137 if (block->size > size + sizeof (struct block)) {
138 struct block *newblock;
139 /* LINTED */
140 newblock = (struct block *)
141 ((char *)block + HDR_BLOCK + size);
142 newblock->next = block->next;
143 block->next = newblock;
144 newblock->status = FREE;
145 newblock->page = block->page;
146 newblock->size = block->size - size - HDR_BLOCK;
147 block->size = size;
148 }
149 }
150
151 #include <stdio.h>
152
153 /*
154 * Replace both malloc() and lmalloc() (libc's private memory allocator).
155 * They are both private here.
156 */
157 #pragma weak lmalloc = malloc
158 void *
159 malloc(size_t size)
160 {
161 struct block *block;
162 struct page *page;
163
164 size = S_DROUND(size);
165
166 /*
167 * Try to locate necessary space
168 */
169 for (page = memstart; page; page = page->next) {
170 for (block = page->block; block; block = block->next) {
171 if ((block->status == FREE) && (block->size >= size))
172 goto found;
173 }
174 }
175 found:
176 /*
177 * Need to allocate a new page
178 */
179 if (!page) {
180 size_t totsize = size + HDR_PAGE;
181 size_t totpage = S_ROUND(totsize, syspagsz);
182
183 if ((page = dz_map(0, 0, totpage,
184 PROT_READ | PROT_WRITE | PROT_EXEC,
185 MAP_PRIVATE)) == MAP_FAILED)
186 return (0);
187
188 page->next = memstart;
189 memstart = page;
190 page->size = totpage;
191 block = page->block;
192 block->next = 0;
193 block->status = FREE;
194 block->size = totpage - HDR_PAGE;
195 block->page = page;
196 }
197
198 split(block, size);
199 #if DEBUG
200 scribble((ulong_t *)&block->memstart, NEWMEM, block->size);
201 #endif
202 block->status = BUSY;
203 return (&block->memstart);
204 }
205
206 void *
207 calloc(size_t num, size_t size)
208 {
209 void * mp;
210 size_t total;
211
212 if (num == 0 || size == 0) {
213 total = 0;
214 } else {
215 total = num * size;
216
217 /* check for overflow */
218 if ((total / num) != size) {
219 errno = ENOMEM;
220 return (NULL);
221 }
222 }
223
224 if ((mp = malloc(total)) == NULL)
225 return (NULL);
226 (void) memset(mp, 0, total);
227 return (mp);
228 }
229
230 void *
231 realloc(void *ptr, size_t size)
232 {
233 struct block *block;
234 size_t osize;
235 void * newptr;
236
237 if (ptr == NULL)
238 return (malloc(size));
239
240 /* LINTED */
241 block = (struct block *)((char *)ptr - HDR_BLOCK);
242 size = S_DROUND(size);
243 osize = block->size;
244
245 /*
246 * Join block with next one if it is free
247 */
248 if (block->next && block->next->status == FREE) {
249 block->size += block->next->size + HDR_BLOCK;
250 block->next = block->next->next;
251 }
252
253 if (size <= block->size) {
254 split(block, size);
255 #if DEBUG
256 if (block->size > osize)
257 scribble((ulong_t *)((char *)ptr + osize), NEWMEM,
258 (block->size - osize));
259 #endif
260 return (ptr);
261 }
262
263 if ((newptr = malloc(size)) == NULL)
264 return (NULL);
265 (void) memcpy(newptr, ptr, osize);
266 block->status = FREE;
267
268 /*
269 * Add the free block to the free APlist for later defragmentation.
270 * However, this addition can only be achieved if there is room on the
271 * free APlist. The APlist can't be allowed to grow, as the growth
272 * requires a realloc(), which would recurse back here, resulting in an
273 * infinite loop. If the free APlist is full, defrag() now. This
274 * defragmentation might not be able to collapse any free space, but
275 * the free APlist will be cleared as part of the processing, ensuring
276 * room for the addition.
277 */
278 if (free_alp && (aplist_nitems(free_alp) >= aplist_arritems(free_alp)))
279 defrag();
280 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
281 return (newptr);
282 }
283
284 /*
285 * Replace both free() and lfree() (libc's private memory allocator).
286 * They are both private here.
287 */
288 void
289 free(void *ptr)
290 {
291 struct block *block;
292
293 if (ptr == NULL)
294 return;
295
296 /* LINTED */
297 block = (struct block *)((char *)ptr - HDR_BLOCK);
298 block->status = FREE;
299 #if DEBUG
300 scribble((ulong_t *)&block->memstart, FREMEM, block->size);
301 #endif
302 (void) aplist_test(&free_alp, block->page, AL_CNT_FREELIST);
303 }
304
305 /* ARGSUSED1 */
306 void
307 lfree(void *ptr, size_t size)
308 {
309 free(ptr);
310 }
311
312 /*
313 * We can use any memory after ld.so.1's .bss up until the next page boundary
314 * as allocatable memory.
315 */
316 void
317 addfree(void *ptr, size_t bytes)
318 {
319 struct block *block;
320 struct page *page;
321
322 if (bytes <= sizeof (struct page))
323 return;
324 page = ptr;
325 page->next = memstart;
326 memstart = page;
327 page->size = bytes;
328 block = page->block;
329 block->next = 0;
330 block->status = FREE;
331 block->size = bytes - HDR_PAGE;
332 block->page = page;
333 }