sys/lib/libsa/alloc.c

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