1 /* $NetBSD: stalloc.c,v 1.20 2023/01/24 07:57:20 mlelstv Exp $ */ 2 3 /* 4 * Copyright (c) 1995 Leo Weppelman (Atari modifications) 5 * Copyright (c) 1994 Christian E. Hopps (allocator stuff) 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include <sys/cdefs.h> 37 __KERNEL_RCSID(0, "$NetBSD: stalloc.c,v 1.20 2023/01/24 07:57:20 mlelstv Exp $"); 38 39 #include <sys/types.h> 40 #include <sys/param.h> 41 #include <sys/systm.h> 42 #include <sys/queue.h> 43 44 #include <atari/atari/stalloc.h> 45 46 /* 47 * St-mem allocator. 48 */ 49 /* 50 * From atari_init.c 51 */ 52 extern u_long st_pool_size, st_pool_virt, st_pool_phys; 53 54 #define PHYS_ADDR(virt) ((u_long)(virt) - st_pool_virt + st_pool_phys) 55 56 static TAILQ_HEAD(stlist, mem_node) st_list; 57 static TAILQ_HEAD(freelist, mem_node) free_list; 58 u_long stmem_total; /* total free. */ 59 60 void 61 init_stmem(void) 62 { 63 int s; 64 struct mem_node *mem; 65 66 s = splhigh(); 67 stmem_total = st_pool_size - sizeof(*mem); 68 69 mem = (struct mem_node *)st_pool_virt; 70 mem->size = st_pool_size - sizeof(*mem); 71 72 TAILQ_INIT(&st_list); 73 TAILQ_INIT(&free_list); 74 75 TAILQ_INSERT_HEAD(&st_list, mem, link); 76 TAILQ_INSERT_HEAD(&free_list, mem, free_link); 77 splx(s); 78 } 79 80 void * 81 alloc_stmem(u_long size, void **phys_addr) 82 { 83 struct mem_node *mn, *new, *bfit; 84 int s; 85 86 if (size == 0) 87 return NULL; 88 89 s = splhigh(); 90 91 if ((size & ~(ST_BLOCKMASK)) != 0) 92 size = (size & ST_BLOCKMASK) + ST_BLOCKSIZE; 93 94 /* 95 * walk list of available nodes, finding the best-fit. 96 */ 97 bfit = NULL; 98 TAILQ_FOREACH(mn, &free_list, free_link) { 99 if (size <= mn->size) { 100 if ((bfit != NULL) && 101 (bfit->size < mn->size)) 102 continue; 103 bfit = mn; 104 } 105 } 106 if (bfit != NULL) 107 mn = bfit; 108 if (mn == NULL) { 109 printf("St-mem pool exhausted, binpatch 'st_pool_size'" 110 "to get more\n"); 111 splx(s); 112 return NULL; 113 } 114 115 if ((mn->size - size) <= sizeof(*mn)) { 116 /* 117 * our allocation would not leave room 118 * for a new node in between. 119 */ 120 TAILQ_REMOVE(&free_list, mn, free_link); 121 mn->type = MNODE_USED; 122 size = mn->size; /* increase size. (or same) */ 123 stmem_total -= mn->size; 124 splx(s); 125 *phys_addr = (void*)PHYS_ADDR(&mn[1]); 126 return (void *)&mn[1]; 127 } 128 129 /* 130 * split the node's memory. 131 */ 132 new = mn; 133 new->size -= size + sizeof(*mn); 134 mn = (struct mem_node *)(MNODES_MEM(new) + new->size); 135 mn->size = size; 136 137 /* 138 * add split node to node list 139 * and mark as not on free list 140 */ 141 TAILQ_INSERT_AFTER(&st_list, new, mn, link); 142 mn->type = MNODE_USED; 143 144 stmem_total -= size + sizeof(*mn); 145 splx(s); 146 *phys_addr = (void*)PHYS_ADDR(&mn[1]); 147 return (void *)&mn[1]; 148 } 149 150 void 151 free_stmem(void *mem) 152 { 153 struct mem_node *mn, *next, *prev; 154 int s; 155 156 if (mem == NULL) 157 return; 158 159 s = splhigh(); 160 mn = (struct mem_node *)mem - 1; 161 next = TAILQ_NEXT(mn, link); 162 prev = TAILQ_PREV(mn, stlist, link); 163 164 /* 165 * check ahead of us. 166 */ 167 if (next != NULL && next->type == MNODE_FREE) { 168 /* 169 * if next is: a valid node and a free node. ==> merge 170 */ 171 TAILQ_INSERT_BEFORE(next, mn, free_link); 172 mn->type = MNODE_FREE; 173 TAILQ_REMOVE(&st_list, next, link); 174 TAILQ_REMOVE(&free_list, next, free_link); 175 stmem_total += mn->size + sizeof(*mn); 176 mn->size += next->size + sizeof(*mn); 177 } 178 if (prev != NULL && prev->type == MNODE_FREE) { 179 /* 180 * if prev is: a valid node and a free node. ==> merge 181 */ 182 if (mn->type != MNODE_FREE) 183 stmem_total += mn->size + sizeof(*mn); 184 else { 185 /* already on free list */ 186 TAILQ_REMOVE(&free_list, mn, free_link); 187 mn->type = MNODE_USED; 188 stmem_total += sizeof(*mn); 189 } 190 TAILQ_REMOVE(&st_list, mn, link); 191 prev->size += mn->size + sizeof(*mn); 192 } else if (mn->type != MNODE_FREE) { 193 /* 194 * we still are not on free list and we need to be. 195 * <-- | --> 196 */ 197 while (next != NULL && prev != NULL) { 198 if (next->type == MNODE_FREE) { 199 TAILQ_INSERT_BEFORE(next, mn, free_link); 200 mn->type = MNODE_FREE; 201 break; 202 } 203 if (prev->type == MNODE_FREE) { 204 TAILQ_INSERT_AFTER(&free_list, prev, mn, 205 free_link); 206 mn->type = MNODE_FREE; 207 break; 208 } 209 prev = TAILQ_PREV(prev, stlist, link); 210 next = TAILQ_NEXT(next, link); 211 } 212 if (mn->type != MNODE_FREE) { 213 if (next == NULL) { 214 /* 215 * we are not on list so we can add 216 * ourselves to the tail. (we walked to it.) 217 */ 218 TAILQ_INSERT_TAIL(&free_list,mn,free_link); 219 } else { 220 TAILQ_INSERT_HEAD(&free_list,mn,free_link); 221 } 222 mn->type = MNODE_FREE; 223 } 224 stmem_total += mn->size;/* add our helpings to the pool. */ 225 } 226 splx(s); 227 } 228