sys/arch/macppc/stand/ofwboot/alloc.c

   1 /*      $NetBSD: alloc.c,v 1.9 2006/01/27 04:51:47 uwe Exp $    */
   2
   3 /*-
   4  * Copyright (c) 1997 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Jason R. Thorpe.
   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  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * Copyright (c) 1997 Christopher G. Demetriou.  All rights reserved.
  34  * Copyright (c) 1996
  35  *      Matthias Drochner.  All rights reserved.
  36  * Copyright (C) 1995, 1996 Wolfgang Solfrank.
  37  * Copyright (C) 1995, 1996 TooLs GmbH.
  38  * All rights reserved.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions
  42  * are met:
  43  * 1. Redistributions of source code must retain the above copyright
  44  *    notice, this list of conditions and the following disclaimer.
  45  * 2. Redistributions in binary form must reproduce the above copyright
  46  *    notice, this list of conditions and the following disclaimer in the
  47  *    documentation and/or other materials provided with the distribution.
  48  * 3. All advertising materials mentioning features or use of this software
  49  *    must display the following acknowledgement:
  50  *      This product includes software developed by TooLs GmbH.
  51  * 4. The name of TooLs GmbH may not be used to endorse or promote products
  52  *    derived from this software without specific prior written permission.
  53  *
  54  * THIS SOFTWARE IS PROVIDED BY TOOLS GMBH ``AS IS'' AND ANY EXPRESS OR
  55  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  56  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  57  * IN NO EVENT SHALL TOOLS GMBH BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  58  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  59  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  60  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  61  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  62  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  63  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  64  */
  65
  66 /*
  67  * Dynamic memory allocator suitable for use with OpenFirmware.
  68  *
  69  * Compile options:
  70  *
  71  *      ALLOC_TRACE     enable tracing of allocations/deallocations
  72  *
  73  *      ALLOC_FIRST_FIT use a first-fit allocation algorithm, rather than
  74  *                      the default best-fit algorithm.
  75  *
  76  *      DEBUG           enable debugging sanity checks.
  77  */
  78
  79 #include <sys/param.h>
  80 #include <sys/queue.h>
  81
  82 #include <lib/libsa/stand.h>
  83
  84 #include "openfirm.h"
  85
  86 /*
  87  * Each block actually has ALIGN(struct ml) + ALIGN(size) bytes allocated
  88  * to it, as follows:
  89  *
  90  * 0 ... (sizeof(struct ml) - 1)
  91  *      allocated or unallocated: holds size of user-data part of block.
  92  *
  93  * sizeof(struct ml) ... (ALIGN(sizeof(struct ml)) - 1)
  94  *      allocated: unused
  95  *      unallocated: depends on packing of struct fl
  96  *
  97  * ALIGN(sizeof(struct ml)) ... (ALIGN(sizeof(struct ml)) +
  98  *   ALIGN(data size) - 1)
  99  *      allocated: user data
 100  *      unallocated: depends on packing of struct fl
 101  *
 102  * 'next' is only used when the block is unallocated (i.e. on the free list).
 103  * However, note that ALIGN(sizeof(struct ml)) + ALIGN(data size) must
 104  * be at least 'sizeof(struct fl)', so that blocks can be used as structures
 105  * when on the free list.
 106  */
 107
 108 /*
 109  * Memory lists.
 110  */
 111 struct ml {
 112         unsigned        size;
 113         LIST_ENTRY(ml)  list;
 114 };
 115
 116 LIST_HEAD(, ml) freelist = LIST_HEAD_INITIALIZER(freelist);
 117 LIST_HEAD(, ml) allocatedlist = LIST_HEAD_INITIALIZER(allocatedlist);
 118
 119 #define OVERHEAD        ALIGN(sizeof (struct ml))       /* shorthand */
 120
 121 void *
 122 alloc(size_t size)
 123 {
 124         struct ml *f, *bestf;
 125 #ifndef ALLOC_FIRST_FIT
 126         unsigned bestsize = 0xffffffff; /* greater than any real size */
 127 #endif
 128         char *help;
 129         int failed;
 130
 131 #ifdef ALLOC_TRACE
 132         printf("alloc(%zu)", size);
 133 #endif
 134
 135         /*
 136          * Account for overhead now, so that we don't get an
 137          * "exact fit" which doesn't have enough space.
 138          */
 139         size = ALIGN(size) + OVERHEAD;
 140
 141 #ifdef ALLOC_FIRST_FIT
 142         /* scan freelist */
 143         for (f = freelist.lh_first; f != NULL && (size_t)f->size < size;
 144             f = f->list.le_next)
 145                 /* noop */ ;
 146         bestf = f;
 147         failed = (bestf == NULL);
 148 #else
 149         /* scan freelist */
 150         bestf = NULL;           /* XXXGCC: -Wuninitialized */
 151         f = freelist.lh_first;
 152         while (f != NULL) {
 153                 if ((size_t)f->size >= size) {
 154                         if ((size_t)f->size == size)    /* exact match */
 155                                 goto found;
 156
 157                         if (f->size < bestsize) {
 158                                 /* keep best fit */
 159                                 bestf = f;
 160                                 bestsize = f->size;
 161                         }
 162                 }
 163                 f = f->list.le_next;
 164         }
 165
 166         /* no match in freelist if bestsize unchanged */
 167         failed = (bestsize == 0xffffffff);
 168 #endif
 169
 170         if (failed) {   /* nothing found */
 171                 /*
 172                  * Allocate memory from the OpenFirmware, rounded
 173                  * to page size, and record the chunk size.
 174                  */
 175                 size = roundup(size, NBPG);
 176                 help = OF_claim(NULL, (unsigned)size, NBPG);
 177                 if (help == (char *)-1)
 178                         panic("alloc: out of memory");
 179
 180                 f = (struct ml *)help;
 181                 f->size = (unsigned)size;
 182 #ifdef ALLOC_TRACE
 183                 printf("=%lx (new chunk size %u)\n",
 184                     (u_long)(help + OVERHEAD), f->size);
 185 #endif
 186                 goto out;
 187         }
 188
 189         /* we take the best fit */
 190         f = bestf;
 191
 192 #ifndef ALLOC_FIRST_FIT
 193  found:
 194 #endif
 195         /* remove from freelist */
 196         LIST_REMOVE(f, list);
 197         help = (char *)f;
 198 #ifdef ALLOC_TRACE
 199         printf("=%lx (origsize %u)\n", (u_long)(help + OVERHEAD), f->size);
 200 #endif
 201  out:
 202         /* place on allocated list */
 203         LIST_INSERT_HEAD(&allocatedlist, f, list);
 204         return (help + OVERHEAD);
 205 }
 206
 207 void
 208 dealloc(void *ptr, size_t size)
 209 {
 210         register struct ml *a = (struct ml *)((char*)ptr - OVERHEAD);
 211
 212 #ifdef ALLOC_TRACE
 213         printf("dealloc(%lx, %zu) (origsize %u)\n", (u_long)ptr, size, a->size);
 214 #endif
 215 #ifdef DEBUG
 216         if (size > (size_t)a->size)
 217                 printf("dealloc %zu bytes @%lx, should be <=%u\n",
 218                     size, (u_long)ptr, a->size);
 219 #endif
 220
 221         /* Remove from allocated list, place on freelist. */
 222         LIST_REMOVE(a, list);
 223         LIST_INSERT_HEAD(&freelist, a, list);
 224 }
 225
 226 void
 227 freeall(void)
 228 {
 229 #ifdef __notyet__
 230         struct ml *m;
 231
 232         /* Release chunks on freelist... */
 233         while ((m = freelist.lh_first) != NULL) {
 234                 LIST_REMOVE(m, list);
 235                 OF_release(m, m->size);
 236         }
 237
 238         /* ...and allocated list. */
 239         while ((m = allocatedlist.lh_first) != NULL) {
 240                 LIST_REMOVE(m, list);
 241                 OF_release(m, m->size);
 242         }
 243 #endif /* __notyet__ */
 244 }