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