xref: /illumos-gate/usr/src/cmd/sgs/rtld/common/malloc.c (revision 31c6d826)
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
scribble(ulong_t * membgn,int pattern,size_t size)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
defrag()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
split(struct block * block,size_t size)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 *
malloc(size_t size)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 *
calloc(size_t num,size_t size)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 *
realloc(void * ptr,size_t size)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
free(void * ptr)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
lfree(void * ptr,size_t size)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
addfree(void * ptr,size_t bytes)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 }
334