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