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
init_stmem(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 *
alloc_stmem(u_long size,void ** phys_addr)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
free_stmem(void * mem)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