Home | History | Annotate | Line # | Download | only in libsa
alloc.c revision 1.8
      1 /*	$NetBSD: alloc.c,v 1.8 1997/06/13 14:28:52 drochner Exp $	*/
      2 
      3 /*
      4  * Copyright (c) 1997 Christopher G. Demetriou.  All rights reserved.
      5  * Copyright (c) 1996
      6  *	Matthias Drochner.  All rights reserved.
      7  * Copyright (c) 1993
      8  *	The Regents of the University of California.  All rights reserved.
      9  *
     10  * This code is derived from software contributed to Berkeley by
     11  * The Mach Operating System project at Carnegie-Mellon University.
     12  *
     13  * Redistribution and use in source and binary forms, with or without
     14  * modification, are permitted provided that the following conditions
     15  * are met:
     16  * 1. Redistributions of source code must retain the above copyright
     17  *    notice, this list of conditions and the following disclaimer.
     18  * 2. Redistributions in binary form must reproduce the above copyright
     19  *    notice, this list of conditions and the following disclaimer in the
     20  *    documentation and/or other materials provided with the distribution.
     21  * 3. All advertising materials mentioning features or use of this software
     22  *    must display the following acknowledgement:
     23  *	This product includes software developed by the University of
     24  *	California, Berkeley and its contributors.
     25  * 4. Neither the name of the University nor the names of its contributors
     26  *    may be used to endorse or promote products derived from this software
     27  *    without specific prior written permission.
     28  *
     29  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     30  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     39  * SUCH DAMAGE.
     40  *
     41  *	@(#)alloc.c	8.1 (Berkeley) 6/11/93
     42  *
     43  *
     44  * Copyright (c) 1989, 1990, 1991 Carnegie Mellon University
     45  * All Rights Reserved.
     46  *
     47  * Author: Alessandro Forin
     48  *
     49  * Permission to use, copy, modify and distribute this software and its
     50  * documentation is hereby granted, provided that both the copyright
     51  * notice and this permission notice appear in all copies of the
     52  * software, derivative works or modified versions, and any portions
     53  * thereof, and that both notices appear in supporting documentation.
     54  *
     55  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
     56  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
     57  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
     58  *
     59  * Carnegie Mellon requests users of this software to return to
     60  *
     61  *  Software Distribution Coordinator  or  Software.Distribution (at) CS.CMU.EDU
     62  *  School of Computer Science
     63  *  Carnegie Mellon University
     64  *  Pittsburgh PA 15213-3890
     65  *
     66  * any improvements or extensions that they make and grant Carnegie the
     67  * rights to redistribute these changes.
     68  */
     69 
     70 /*
     71  * Dynamic memory allocator.
     72  *
     73  * Compile options:
     74  *
     75  *	ALLOC_TRACE	enable tracing of allocations/deallocations
     76 
     77  *	ALLOC_FIRST_FIT	use a first-fit allocation algorithm, rather than
     78  *			the default best-fit algorithm.
     79  *
     80  *	HEAP_LIMIT	heap limit address (defaults to "no limit").
     81  *
     82  *	HEAP_START	start address of heap (defaults to '&end').
     83  *
     84  *	DEBUG		enable debugging sanity checks.
     85  */
     86 
     87 #include <sys/param.h>
     88 #include "stand.h"
     89 
     90 /*
     91  * Each block actually has ALIGN(unsigned) + ALIGN(size) bytes allocated
     92  * to it, as follows:
     93  *
     94  * 0 ... (sizeof(unsigned) - 1)
     95  *	allocated or unallocated: holds size of user-data part of block.
     96  *
     97  * sizeof(unsigned) ... (ALIGN(sizeof(unsigned)) - 1)
     98  *	allocated: unused
     99  *	unallocated: depends on packing of struct fl
    100  *
    101  * ALIGN(sizeof(unsigned)) ... (ALIGN(sizeof(unsigned)) + ALIGN(data size) - 1)
    102  *	allocated: user data
    103  *	unallocated: depends on packing of struct fl
    104  *
    105  * 'next' is only used when the block is unallocated (i.e. on the free list).
    106  * However, note that ALIGN(sizeof(unsigned)) + ALIGN(data size) must
    107  * be at least 'sizeof(struct fl)', so that blocks can be used as structures
    108  * when on the free list.
    109  */
    110 struct fl {
    111 	unsigned	size;
    112 	struct fl	*next;
    113 } *freelist = (struct fl *)0;
    114 
    115 #ifdef HEAP_START
    116 static char *top = (char*)HEAP_START;
    117 #else
    118 extern char end[];
    119 static char *top = end;
    120 #endif
    121 
    122 void *
    123 alloc(size)
    124 	unsigned size;
    125 {
    126 	register struct fl **f = &freelist, **bestf = NULL;
    127 	unsigned bestsize = 0xffffffff;	/* greater than any real size */
    128 	char *help;
    129 	int failed;
    130 
    131 #ifdef ALLOC_TRACE
    132 	printf("alloc(%u)", size);
    133 #endif
    134 
    135 #ifdef ALLOC_FIRST_FIT
    136 	while (*f != (struct fl *)0 && (*f)->size < size)
    137 		f = &((*f)->next);
    138 	bestf = f;
    139 	failed = (*bestf == (struct fl *)0);
    140 #else
    141 	/* scan freelist */
    142 	while (*f) {
    143 		if ((*f)->size >= size) {
    144 			if ((*f)->size == size) /* exact match */
    145 				goto found;
    146 
    147 			if ((*f)->size < bestsize) {
    148 				/* keep best fit */
    149 	                        bestf = f;
    150 	                        bestsize = (*f)->size;
    151 	                }
    152 	        }
    153 	        f = &((*f)->next);
    154 	}
    155 
    156 	/* no match in freelist if bestsize unchanged */
    157 	failed = (bestsize == 0xffffffff);
    158 #endif
    159 
    160 	if (failed) { /* nothing found */
    161 	        /*
    162 		 * allocate from heap, keep chunk len in
    163 		 * first word
    164 		 */
    165 	        help = top;
    166 
    167 		/* make _sure_ the region can hold a struct fl. */
    168 		if (size < ALIGN(sizeof (struct fl *)))
    169 			size = ALIGN(sizeof (struct fl *));
    170 		top += ALIGN(sizeof(unsigned)) + ALIGN(size);
    171 #ifdef HEAP_LIMIT
    172 		if (top > (char*)HEAP_LIMIT)
    173 		        panic("heap full (0x%lx+%u)", help, size);
    174 #endif
    175 		*(unsigned *)help = ALIGN(size);
    176 #ifdef ALLOC_TRACE
    177 		printf("=%x\n", help + ALIGN(sizeof(unsigned)));
    178 #endif
    179 		return(help + ALIGN(sizeof(unsigned)));
    180 	}
    181 
    182 	/* we take the best fit */
    183 	f = bestf;
    184 
    185 found:
    186         /* remove from freelist */
    187         help = (char*)*f;
    188 	*f = (*f)->next;
    189 #ifdef ALLOC_TRACE
    190 	printf("=%lx (origsize %u)\n", help + ALIGN(sizeof(unsigned)),
    191 	    *(unsigned *)help);
    192 #endif
    193 	return(help + ALIGN(sizeof(unsigned)));
    194 }
    195 
    196 void
    197 free(ptr, size)
    198 	void *ptr;
    199 	unsigned size; /* only for consistence check */
    200 {
    201 	register struct fl *f =
    202 	    (struct fl *)((char*)ptr - ALIGN(sizeof(unsigned)));
    203 #ifdef ALLOC_TRACE
    204 	printf("free(%lx, %u) (origsize %u)\n", ptr, size, f->size);
    205 #endif
    206 #ifdef DEBUG
    207         if (size > f->size)
    208 	        printf("free %u bytes @%lx, should be <=%u\n",
    209 		    size, ptr, f->size);
    210 #ifdef HEAP_START
    211 	if (ptr < (void *)HEAP_START)
    212 #else
    213 	if (ptr < (void *)end[])
    214 #endif
    215 		printf("free: %lx before start of heap.\n", (u_long)ptr);
    216 
    217 #ifdef HEAP_LIMIT
    218 	if (ptr > (void *)HEAP_LIMIT)
    219 		printf("free: %lx beyond end of heap.\n", (u_long)ptr);
    220 #endif
    221 #endif /* DEBUG */
    222 	/* put into freelist */
    223 	f->next = freelist;
    224 	freelist = f;
    225 }
    226