Commit | Line | Data |
---|---|---|
15637ed4 RG |
1 | /* |
2 | * Copyright (c) 1992 William F. Jolitz, TeleMuse | |
3 | * All rights reserved. | |
4 | * | |
5 | * Redistribution and use in source and binary forms, with or without | |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * 1. Redistributions of source code must retain the above copyright | |
9 | * notice, this list of conditions and the following disclaimer. | |
10 | * 2. Redistributions in binary form must reproduce the above copyright | |
11 | * notice, this list of conditions and the following disclaimer in the | |
12 | * documentation and/or other materials provided with the distribution. | |
13 | * 3. All advertising materials mentioning features or use of this software | |
14 | * must display the following acknowledgement: | |
15 | * This software is a component of "386BSD" developed by | |
16 | William F. Jolitz, TeleMuse. | |
17 | * 4. Neither the name of the developer nor the name "386BSD" | |
18 | * may be used to endorse or promote products derived from this software | |
19 | * without specific prior written permission. | |
20 | * | |
21 | * THIS SOFTWARE IS A COMPONENT OF 386BSD DEVELOPED BY WILLIAM F. JOLITZ | |
22 | * AND IS INTENDED FOR RESEARCH AND EDUCATIONAL PURPOSES ONLY. THIS | |
23 | * SOFTWARE SHOULD NOT BE CONSIDERED TO BE A COMMERCIAL PRODUCT. | |
24 | * THE DEVELOPER URGES THAT USERS WHO REQUIRE A COMMERCIAL PRODUCT | |
25 | * NOT MAKE USE THIS WORK. | |
26 | * | |
27 | * FOR USERS WHO WISH TO UNDERSTAND THE 386BSD SYSTEM DEVELOPED | |
28 | * BY WILLIAM F. JOLITZ, WE RECOMMEND THE USER STUDY WRITTEN | |
29 | * REFERENCES SUCH AS THE "PORTING UNIX TO THE 386" SERIES | |
30 | * (BEGINNING JANUARY 1991 "DR. DOBBS JOURNAL", USA AND BEGINNING | |
31 | * JUNE 1991 "UNIX MAGAZIN", GERMANY) BY WILLIAM F. JOLITZ AND | |
32 | * LYNNE GREER JOLITZ, AS WELL AS OTHER BOOKS ON UNIX AND THE | |
33 | * ON-LINE 386BSD USER MANUAL BEFORE USE. A BOOK DISCUSSING THE INTERNALS | |
34 | * OF 386BSD ENTITLED "386BSD FROM THE INSIDE OUT" WILL BE AVAILABLE LATE 1992. | |
35 | * | |
36 | * THIS SOFTWARE IS PROVIDED BY THE DEVELOPER ``AS IS'' AND | |
37 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
38 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
39 | * ARE DISCLAIMED. IN NO EVENT SHALL THE DEVELOPER BE LIABLE | |
40 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
41 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
42 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
43 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
44 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
45 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
46 | * SUCH DAMAGE. | |
47 | * | |
736d20f2 | 48 | * $Id$ |
15637ed4 | 49 | */ |
15637ed4 | 50 | |
fde1aeb2 GW |
51 | #include "param.h" |
52 | #include "systm.h" | |
736d20f2 | 53 | #include "cdefs.h" |
fde1aeb2 | 54 | #include "malloc.h" |
15637ed4 | 55 | #include "rlist.h" |
736d20f2 DG |
56 | #include "vm/vm.h" |
57 | #include "vm/vm_map.h" | |
58 | ||
59 | extern vm_map_t kernel_map; | |
15637ed4 RG |
60 | |
61 | /* | |
62 | * Resource lists. | |
63 | */ | |
64 | ||
736d20f2 DG |
65 | #define RLIST_MIN 128 |
66 | static int rlist_count=0; | |
67 | static struct rlist *rlfree; | |
68 | int rlist_active; | |
69 | ||
70 | static struct rlist * | |
71 | rlist_malloc() | |
72 | { | |
73 | struct rlist *rl; | |
74 | int i; | |
75 | while( rlist_count < RLIST_MIN) { | |
76 | extern vm_map_t kmem_map; | |
77 | int s = splhigh(); | |
78 | rl = (struct rlist *)kmem_malloc(kmem_map, NBPG, 0); | |
79 | splx(s); | |
80 | if( !rl) | |
81 | break; | |
82 | ||
83 | for(i=0;i<(NBPG/(sizeof *rl));i++) { | |
84 | rl->rl_next = rlfree; | |
85 | rlfree = rl; | |
86 | rlist_count++; | |
87 | rl++; | |
88 | } | |
89 | } | |
90 | ||
91 | if( (rl = rlfree) == 0 ) | |
92 | panic("Cannot get an rlist entry"); | |
93 | ||
94 | --rlist_count; | |
95 | rlfree = rl->rl_next; | |
96 | return rl; | |
97 | } | |
98 | ||
99 | inline static void | |
100 | rlist_mfree( struct rlist *rl) | |
101 | { | |
102 | rl->rl_next = rlfree; | |
103 | rlfree = rl; | |
104 | ++rlist_count; | |
105 | } | |
106 | ||
107 | ||
15637ed4 RG |
108 | /* |
109 | * Add space to a resource list. Used to either | |
110 | * initialize a list or return free space to it. | |
111 | */ | |
4c45483e | 112 | void |
15637ed4 | 113 | rlist_free (rlp, start, end) |
4c45483e GW |
114 | register struct rlist **rlp; |
115 | unsigned start, end; | |
116 | { | |
15637ed4 | 117 | struct rlist *head; |
736d20f2 DG |
118 | register struct rlist *olp = 0; |
119 | int s; | |
120 | ||
121 | s = splhigh(); | |
122 | while( rlist_active) | |
123 | tsleep((caddr_t)&rlist_active, PSWP, "rlistf", 0); | |
124 | rlist_active = 1; | |
125 | splx(s); | |
15637ed4 RG |
126 | |
127 | head = *rlp; | |
128 | ||
129 | loop: | |
130 | /* if nothing here, insert (tail of list) */ | |
131 | if (*rlp == 0) { | |
736d20f2 | 132 | *rlp = rlist_malloc(); |
15637ed4 RG |
133 | (*rlp)->rl_start = start; |
134 | (*rlp)->rl_end = end; | |
135 | (*rlp)->rl_next = 0; | |
736d20f2 DG |
136 | rlist_active = 0; |
137 | wakeup((caddr_t)&rlist_active); | |
15637ed4 RG |
138 | return; |
139 | } | |
140 | ||
141 | /* if new region overlaps something currently present, panic */ | |
142 | if (start >= (*rlp)->rl_start && start <= (*rlp)->rl_end) { | |
143 | printf("Frag %d:%d, ent %d:%d ", start, end, | |
144 | (*rlp)->rl_start, (*rlp)->rl_end); | |
145 | panic("overlapping front rlist_free: freed twice?"); | |
146 | } | |
147 | if (end >= (*rlp)->rl_start && end <= (*rlp)->rl_end) { | |
148 | printf("Frag %d:%d, ent %d:%d ", start, end, | |
149 | (*rlp)->rl_start, (*rlp)->rl_end); | |
150 | panic("overlapping tail rlist_free: freed twice?"); | |
151 | } | |
152 | ||
153 | /* are we adjacent to this element? (in front) */ | |
154 | if (end+1 == (*rlp)->rl_start) { | |
155 | /* coalesce */ | |
156 | (*rlp)->rl_start = start; | |
157 | goto scan; | |
158 | } | |
159 | ||
160 | /* are we before this element? */ | |
161 | if (end < (*rlp)->rl_start) { | |
162 | register struct rlist *nlp; | |
163 | ||
736d20f2 | 164 | nlp = rlist_malloc(); |
15637ed4 RG |
165 | nlp->rl_start = start; |
166 | nlp->rl_end = end; | |
167 | nlp->rl_next = *rlp; | |
736d20f2 DG |
168 | /* |
169 | * If the new element is in front of the list, | |
170 | * adjust *rlp, else don't. | |
171 | */ | |
172 | if( olp) { | |
173 | olp->rl_next = nlp; | |
174 | } else { | |
175 | *rlp = nlp; | |
176 | } | |
177 | rlist_active = 0; | |
178 | wakeup((caddr_t)&rlist_active); | |
15637ed4 RG |
179 | return; |
180 | } | |
181 | ||
182 | /* are we adjacent to this element? (at tail) */ | |
183 | if ((*rlp)->rl_end + 1 == start) { | |
184 | /* coalesce */ | |
185 | (*rlp)->rl_end = end; | |
186 | goto scan; | |
187 | } | |
188 | ||
189 | /* are we after this element */ | |
190 | if (start > (*rlp)->rl_end) { | |
736d20f2 | 191 | olp = *rlp; |
15637ed4 RG |
192 | rlp = &((*rlp)->rl_next); |
193 | goto loop; | |
194 | } else | |
195 | panic("rlist_free: can't happen"); | |
196 | ||
197 | scan: | |
198 | /* can we coalesce list now that we've filled a void? */ | |
199 | { | |
200 | register struct rlist *lp, *lpn; | |
201 | ||
202 | for (lp = head; lp->rl_next ;) { | |
203 | lpn = lp->rl_next; | |
204 | ||
205 | /* coalesce ? */ | |
206 | if (lp->rl_end + 1 == lpn->rl_start) { | |
207 | lp->rl_end = lpn->rl_end; | |
208 | lp->rl_next = lpn->rl_next; | |
736d20f2 | 209 | rlist_mfree(lpn); |
15637ed4 RG |
210 | } else |
211 | lp = lp->rl_next; | |
212 | } | |
213 | } | |
736d20f2 DG |
214 | rlist_active = 0; |
215 | wakeup((caddr_t)&rlist_active); | |
15637ed4 RG |
216 | } |
217 | ||
218 | /* | |
219 | * Obtain a region of desired size from a resource list. | |
220 | * If nothing available of that size, return 0. Otherwise, | |
221 | * return a value of 1 and set resource start location with | |
222 | * "*loc". (Note: loc can be zero if we don't wish the value) | |
223 | */ | |
224 | int rlist_alloc (rlp, size, loc) | |
736d20f2 DG |
225 | struct rlist **rlp; |
226 | unsigned size, *loc; | |
227 | { | |
15637ed4 | 228 | register struct rlist *lp; |
736d20f2 DG |
229 | int s; |
230 | register struct rlist *olp = 0; | |
15637ed4 | 231 | |
736d20f2 DG |
232 | s = splhigh(); |
233 | while( rlist_active) | |
234 | tsleep((caddr_t)&rlist_active, PSWP, "rlista", 0); | |
235 | rlist_active = 1; | |
236 | splx(s); | |
15637ed4 RG |
237 | |
238 | /* walk list, allocating first thing that's big enough (first fit) */ | |
239 | for (; *rlp; rlp = &((*rlp)->rl_next)) | |
240 | if(size <= (*rlp)->rl_end - (*rlp)->rl_start + 1) { | |
241 | ||
242 | /* hand it to the caller */ | |
243 | if (loc) *loc = (*rlp)->rl_start; | |
244 | (*rlp)->rl_start += size; | |
245 | ||
246 | /* did we eat this element entirely? */ | |
247 | if ((*rlp)->rl_start > (*rlp)->rl_end) { | |
248 | lp = (*rlp)->rl_next; | |
736d20f2 DG |
249 | rlist_mfree(*rlp); |
250 | /* | |
251 | * if the deleted element was in fromt | |
252 | * of the list, adjust *rlp, else don't. | |
253 | */ | |
254 | if (olp) { | |
255 | olp->rl_next = lp; | |
256 | } else { | |
257 | *rlp = lp; | |
258 | } | |
15637ed4 RG |
259 | } |
260 | ||
736d20f2 DG |
261 | rlist_active = 0; |
262 | wakeup((caddr_t)&rlist_active); | |
15637ed4 | 263 | return (1); |
736d20f2 DG |
264 | } else { |
265 | olp = *rlp; | |
15637ed4 RG |
266 | } |
267 | ||
736d20f2 DG |
268 | rlist_active = 0; |
269 | wakeup((caddr_t)&rlist_active); | |
15637ed4 RG |
270 | /* nothing in list that's big enough */ |
271 | return (0); | |
272 | } | |
273 | ||
274 | /* | |
275 | * Finished with this resource list, reclaim all space and | |
276 | * mark it as being empty. | |
277 | */ | |
4c45483e | 278 | void |
15637ed4 | 279 | rlist_destroy (rlp) |
4c45483e GW |
280 | struct rlist **rlp; |
281 | { | |
15637ed4 RG |
282 | struct rlist *lp, *nlp; |
283 | ||
284 | lp = *rlp; | |
285 | *rlp = 0; | |
286 | for (; lp; lp = nlp) { | |
287 | nlp = lp->rl_next; | |
736d20f2 | 288 | rlist_mfree(lp); |
15637ed4 RG |
289 | } |
290 | } |