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