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