1 | /*
|
---|
2 | =============================================================================
|
---|
3 | memory.c - memory allocation functions for GEMDOS
|
---|
4 | Version 4 -- 1988-05-03 -- Beckemeyer (original) / Lynxcairne (mods)
|
---|
5 |
|
---|
6 | These routines implement the Unix standard C runtime
|
---|
7 | library routines malloc(), free(), and realloc(),
|
---|
8 | but are NOT compatible with intermixed brk() and sbrk() calls.
|
---|
9 |
|
---|
10 | The routines manage "heaps" allocated from the system.
|
---|
11 | Each heap is carved up into some number of user memory
|
---|
12 | blocks, as requested by malloc() and realloc() calls.
|
---|
13 |
|
---|
14 | As blocks are returned with free() calls, they are merged
|
---|
15 | with any neighboring blocks that are free. Un-mergable
|
---|
16 | blocks are stored on a doubly linked list.
|
---|
17 |
|
---|
18 | As heaps become full, new ones are created. The list of
|
---|
19 | heaps is a singly linked list. Heaps are returned to the
|
---|
20 | system during garbage collection, which occurs whenever
|
---|
21 | the current set of heaps cannot fill a memory request.
|
---|
22 |
|
---|
23 | This scheme avoids GEMDOS memory management problems
|
---|
24 | and minimizes fragmentation.
|
---|
25 |
|
---|
26 | MINSEG below defines the minimum segment size allocated.
|
---|
27 | Whenever the remaining portion of a block is smaller than
|
---|
28 | this value, the entire block is returned to the caller.
|
---|
29 |
|
---|
30 | HEAPSIZE is the smallest system allocation we will ever
|
---|
31 | make. This value can be adjusted to your application.
|
---|
32 | If it is small, more GEMDOS Malloc calls will have to
|
---|
33 | be performed. If it is large compared to the amount of
|
---|
34 | memory actually aquired at runtime, there will be wasted
|
---|
35 | memory. Since too many GEMDOS Malloc calls may produce
|
---|
36 | a crash, it is wise to make HEAPSIZE at least 8K bytes.
|
---|
37 |
|
---|
38 | =============================================================================
|
---|
39 | */
|
---|
40 |
|
---|
41 | #define DEBUGIT 1 /* define non-zero to compile debug code */
|
---|
42 |
|
---|
43 | #include "stdio.h"
|
---|
44 | #include "osbind.h"
|
---|
45 | #include "stddefs.h"
|
---|
46 |
|
---|
47 | /* memory manager definitions */
|
---|
48 |
|
---|
49 | #define HEAPSIZE 16384L /* minimum size of each heap */
|
---|
50 | #define MINSEG 256L /* minimum size of allocated memory chunk */
|
---|
51 |
|
---|
52 | #define MAGIC 0x55AA /* magic number used for validation */
|
---|
53 |
|
---|
54 | /* the structure controlling the object known as a "heap" */
|
---|
55 |
|
---|
56 | #define HEAP struct _heap
|
---|
57 |
|
---|
58 | /* Memory Control Block */
|
---|
59 |
|
---|
60 | #define MCB struct _mcb
|
---|
61 |
|
---|
62 | struct _mcb {
|
---|
63 |
|
---|
64 | MCB *fore; /* forward link */
|
---|
65 | MCB *aft; /* backward link */
|
---|
66 | MCB *buddy; /* nearest lower address neighbor */
|
---|
67 | long size; /* size of this chunk including MCB */
|
---|
68 | HEAP *heap; /* 0L if free, else owner of this chunk */
|
---|
69 | int magic; /* magic number for validation */
|
---|
70 | };
|
---|
71 |
|
---|
72 | /* and here is the heap control block */
|
---|
73 |
|
---|
74 | struct _heap {
|
---|
75 |
|
---|
76 | HEAP *link; /* pointer to next heap (0 if end) */
|
---|
77 | MCB *avail; /* pointer to first free block or 0 */
|
---|
78 | MCB *limit; /* address of the end of this heap */
|
---|
79 | };
|
---|
80 |
|
---|
81 | #if DEBUGIT
|
---|
82 | short mal_dbg; /* set non-zero for malloc debug trace */
|
---|
83 | #endif
|
---|
84 |
|
---|
85 | /*
|
---|
86 | List of allocated heaps aquired from GEMDOS.
|
---|
87 | Start off with no heaps allocated (NULL terminated linked list).
|
---|
88 | */
|
---|
89 |
|
---|
90 | static HEAP heaps = { (HEAP *)0 };
|
---|
91 |
|
---|
92 | /* |
---|
93 |
|
---|
94 | */
|
---|
95 |
|
---|
96 | /*
|
---|
97 | =============================================================================
|
---|
98 | a_heap() --get another heap from GEMDOS
|
---|
99 | =============================================================================
|
---|
100 | */
|
---|
101 |
|
---|
102 | static
|
---|
103 | HEAP *
|
---|
104 | a_heap(x)
|
---|
105 | long x;
|
---|
106 | {
|
---|
107 | MCB *m;
|
---|
108 | HEAP *heap;
|
---|
109 |
|
---|
110 | /* locate end of the heap list */
|
---|
111 | /* (a tail pointer would help here) */
|
---|
112 |
|
---|
113 | for (heap = &heaps; heap->link; heap = heap->link)
|
---|
114 | ;
|
---|
115 |
|
---|
116 | /* adjust the request for the minmum required overhead */
|
---|
117 |
|
---|
118 | x = (x + sizeof(HEAP) + sizeof(MCB) + 1) & ~1L;
|
---|
119 |
|
---|
120 | /* grab a chunk from GEMDOS */
|
---|
121 |
|
---|
122 | if ((heap->link = (HEAP *)Malloc(x)) EQ 0) {
|
---|
123 |
|
---|
124 | #if DEBUGIT
|
---|
125 | if (mal_dbg) {
|
---|
126 |
|
---|
127 | printf("a_heap(%ld): GEMDOS Malloc() returned 0\n", x);
|
---|
128 | printf(" largest block available = %ld\n", Malloc(-1L));
|
---|
129 | }
|
---|
130 | #endif
|
---|
131 | return((HEAP *)0);
|
---|
132 | }
|
---|
133 |
|
---|
134 | /* add the heap to the heap list */
|
---|
135 |
|
---|
136 | heap = heap->link;
|
---|
137 | heap->link = (HEAP *)0;
|
---|
138 |
|
---|
139 | /* first chunk is just after header */
|
---|
140 |
|
---|
141 | m = (MCB *)(heap + 1);
|
---|
142 |
|
---|
143 | /* set up size and mark it as a free chunk */
|
---|
144 |
|
---|
145 | m->size = x - sizeof(HEAP);
|
---|
146 | m->heap = 0L;
|
---|
147 |
|
---|
148 | /* this is the last (only) chunk on the linked list */
|
---|
149 |
|
---|
150 | m->fore = (MCB *)0;
|
---|
151 | m->aft = (MCB *)(&heap->avail);
|
---|
152 |
|
---|
153 | /* there is no lower addressed neighbor to this chunk */
|
---|
154 |
|
---|
155 | m->buddy = (MCB *)0;
|
---|
156 |
|
---|
157 | /* mark the heap limit and place chunk on the free list */
|
---|
158 |
|
---|
159 | heap->limit = (MCB *)((char *)heap + x);
|
---|
160 | heap->avail = m;
|
---|
161 |
|
---|
162 | return(heap);
|
---|
163 | }
|
---|
164 |
|
---|
165 | /* |
---|
166 |
|
---|
167 | */
|
---|
168 |
|
---|
169 | /*
|
---|
170 | =============================================================================
|
---|
171 | s_split() -- split a segment into two chunks
|
---|
172 | =============================================================================
|
---|
173 | */
|
---|
174 |
|
---|
175 | static
|
---|
176 | s_split(mcb, x)
|
---|
177 | MCB *mcb;
|
---|
178 | long x;
|
---|
179 | {
|
---|
180 | MCB *m;
|
---|
181 | HEAP *heap;
|
---|
182 |
|
---|
183 | /* check for ownership here */
|
---|
184 |
|
---|
185 | if (mcb EQ 0 OR (heap = mcb->heap) EQ 0 OR mcb->magic NE MAGIC) {
|
---|
186 |
|
---|
187 | #if DEBUGIT
|
---|
188 | if (mal_dbg)
|
---|
189 | printf("s_split($%lx, %ld): MCB invalid\n", mcb, x);
|
---|
190 | #endif
|
---|
191 | return(FAILURE);
|
---|
192 | }
|
---|
193 |
|
---|
194 | /* make a new chunk inside this one */
|
---|
195 |
|
---|
196 | m = (MCB *)((char *)mcb + x);
|
---|
197 | m->size = mcb->size - x;
|
---|
198 | m->buddy = mcb;
|
---|
199 | m->heap = mcb->heap;
|
---|
200 | m->magic = MAGIC;
|
---|
201 |
|
---|
202 | /* shrink the old chunk */
|
---|
203 |
|
---|
204 | mcb->size = x;
|
---|
205 |
|
---|
206 | /* establish the forward neighbor's relationship to us */
|
---|
207 |
|
---|
208 | mcb = m;
|
---|
209 |
|
---|
210 | if ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit)
|
---|
211 | m->buddy = mcb;
|
---|
212 |
|
---|
213 | free(++mcb);
|
---|
214 | return(SUCCESS);
|
---|
215 | }
|
---|
216 |
|
---|
217 | /* |
---|
218 |
|
---|
219 | */
|
---|
220 |
|
---|
221 | /*
|
---|
222 | =============================================================================
|
---|
223 | aloc_s() -- allocate a chunk out of a heap
|
---|
224 | =============================================================================
|
---|
225 | */
|
---|
226 |
|
---|
227 | static
|
---|
228 | MCB *
|
---|
229 | aloc_s(x, heap)
|
---|
230 | long x;
|
---|
231 | HEAP *heap;
|
---|
232 | {
|
---|
233 | MCB *mcb;
|
---|
234 |
|
---|
235 | /* use first fit algorithm to find chunk to use */
|
---|
236 |
|
---|
237 | for (mcb = heap->avail; mcb; mcb = mcb->fore)
|
---|
238 | if (mcb->size GE x + sizeof(MCB))
|
---|
239 | break;
|
---|
240 |
|
---|
241 | if (mcb) {
|
---|
242 |
|
---|
243 | /* remove it from the free list */
|
---|
244 |
|
---|
245 | unfree(mcb);
|
---|
246 |
|
---|
247 | /* set up owner */
|
---|
248 |
|
---|
249 | mcb->heap = heap;
|
---|
250 | mcb->magic = MAGIC;
|
---|
251 |
|
---|
252 | /* if it's bigger than we need and splitable, split it */
|
---|
253 |
|
---|
254 | if (mcb->size - x > MINSEG)
|
---|
255 | if (s_split(mcb, x + sizeof(MCB)))
|
---|
256 | return((MCB *)0);
|
---|
257 |
|
---|
258 | /* return start of data area to caller */
|
---|
259 |
|
---|
260 | mcb++;
|
---|
261 | }
|
---|
262 |
|
---|
263 | return(mcb);
|
---|
264 | }
|
---|
265 |
|
---|
266 | /* |
---|
267 |
|
---|
268 | */
|
---|
269 |
|
---|
270 | /*
|
---|
271 | =============================================================================
|
---|
272 | unfree() -- remove (unlink) a chunk from the free list
|
---|
273 | =============================================================================
|
---|
274 | */
|
---|
275 |
|
---|
276 | static
|
---|
277 | unfree(mcb)
|
---|
278 | MCB *mcb;
|
---|
279 | {
|
---|
280 | if ((mcb->aft->fore = mcb->fore) NE 0)
|
---|
281 | mcb->fore->aft = mcb->aft;
|
---|
282 | }
|
---|
283 |
|
---|
284 |
|
---|
285 |
|
---|
286 | /*
|
---|
287 | =============================================================================
|
---|
288 | collect() -- GEMDOS garbage collection, return TRUE if anything changes
|
---|
289 | =============================================================================
|
---|
290 | */
|
---|
291 |
|
---|
292 | static
|
---|
293 | collect()
|
---|
294 | {
|
---|
295 | HEAP *heap, *h;
|
---|
296 | MCB *mcb;
|
---|
297 | int flag;
|
---|
298 |
|
---|
299 | #if DEBUGIT
|
---|
300 | if (mal_dbg)
|
---|
301 | printf("collect(): collecting garbage ...\n");
|
---|
302 | #endif
|
---|
303 |
|
---|
304 | for (flag = 0, heap = &heaps; (h = heap->link) NE 0; ) {
|
---|
305 |
|
---|
306 | if ((mcb = h->avail) NE 0 AND
|
---|
307 | NOT mcb->buddy AND ((char *)mcb + mcb->size) EQ h->limit) {
|
---|
308 |
|
---|
309 | heap->link = h->link;
|
---|
310 | Mfree(h);
|
---|
311 | flag++;
|
---|
312 |
|
---|
313 | } else
|
---|
314 | heap = h;
|
---|
315 | }
|
---|
316 |
|
---|
317 | return(flag);
|
---|
318 | }
|
---|
319 |
|
---|
320 | /* |
---|
321 |
|
---|
322 | */
|
---|
323 |
|
---|
324 | /*
|
---|
325 | =============================================================================
|
---|
326 |
|
---|
327 | Unix standard C runtime library routines
|
---|
328 | malloc(), free(), and realloc() follow.
|
---|
329 |
|
---|
330 | The three calls work as described in K & R,
|
---|
331 | except that they don't use brk() or sbrk(),
|
---|
332 | so BEWARE.
|
---|
333 |
|
---|
334 | This implementation uses a first fit algorithm
|
---|
335 | and does occasional garbage collection to
|
---|
336 | minimize system memory fragmentation.
|
---|
337 |
|
---|
338 | =============================================================================
|
---|
339 | */
|
---|
340 |
|
---|
341 |
|
---|
342 | /*
|
---|
343 | =============================================================================
|
---|
344 | malloc() -- allocate 'n' bytes of memory
|
---|
345 | =============================================================================
|
---|
346 | */
|
---|
347 |
|
---|
348 |
|
---|
349 | char *
|
---|
350 | malloc(n)
|
---|
351 | unsigned n;
|
---|
352 | {
|
---|
353 | register HEAP *heap;
|
---|
354 | register long x;
|
---|
355 | char *p;
|
---|
356 |
|
---|
357 | x = (long)(n + 1) & ~1L;
|
---|
358 |
|
---|
359 | /* first check all current heaps */
|
---|
360 |
|
---|
361 | for (heap = heaps.link; heap; heap = heap->link)
|
---|
362 | if ((p = aloc_s(x, heap)) NE 0)
|
---|
363 | return(p);
|
---|
364 |
|
---|
365 | /* not enough room on heap list, try garbage collection */
|
---|
366 |
|
---|
367 | collect();
|
---|
368 |
|
---|
369 | /* now allocate a new heap */
|
---|
370 |
|
---|
371 | if ((heap = a_heap(max(x, HEAPSIZE))) NE 0)
|
---|
372 | if ((p = aloc_s(x, heap)) NE 0)
|
---|
373 | return(p);
|
---|
374 |
|
---|
375 | /* couldn't get a chunk big enough */
|
---|
376 |
|
---|
377 | #if DEBUGIT
|
---|
378 | if (mal_dbg)
|
---|
379 | printf("malloc(%u): unable to find a large enough chunk\n", n);
|
---|
380 | #endif
|
---|
381 |
|
---|
382 | return((char *)0);
|
---|
383 | }
|
---|
384 |
|
---|
385 | /* |
---|
386 |
|
---|
387 | */
|
---|
388 |
|
---|
389 |
|
---|
390 | /*
|
---|
391 | =============================================================================
|
---|
392 | free() -- return a block 'mcb' of memory to the storage pool
|
---|
393 | =============================================================================
|
---|
394 | */
|
---|
395 |
|
---|
396 |
|
---|
397 | free(mcb)
|
---|
398 | MCB *mcb;
|
---|
399 | {
|
---|
400 | MCB *m;
|
---|
401 | HEAP *heap;
|
---|
402 |
|
---|
403 | /* address header */
|
---|
404 |
|
---|
405 | mcb--;
|
---|
406 |
|
---|
407 | /* check for ownership here */
|
---|
408 |
|
---|
409 | if (mcb EQ 0 OR (heap = mcb->heap) EQ 0 OR mcb->magic NE MAGIC) {
|
---|
410 |
|
---|
411 | #if DEBUGIT
|
---|
412 | printf("free($%lx): MCB invalid\n", mcb);
|
---|
413 | #endif
|
---|
414 |
|
---|
415 | return(-40);
|
---|
416 | }
|
---|
417 |
|
---|
418 | /* connect to chunks behind this one */
|
---|
419 |
|
---|
420 | while (mcb->buddy) {
|
---|
421 |
|
---|
422 | if (mcb->buddy->heap)
|
---|
423 | break;
|
---|
424 |
|
---|
425 | mcb->buddy->size += mcb->size;
|
---|
426 | mcb = mcb->buddy;
|
---|
427 | unfree(mcb);
|
---|
428 | }
|
---|
429 |
|
---|
430 | /* now connect to chunks after this one */
|
---|
431 |
|
---|
432 | while ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit) {
|
---|
433 |
|
---|
434 | m->buddy = mcb;
|
---|
435 |
|
---|
436 | if (m->heap)
|
---|
437 | break;
|
---|
438 |
|
---|
439 | mcb->size += m->size;
|
---|
440 | unfree(m);
|
---|
441 | }
|
---|
442 |
|
---|
443 | /* place the resultant chunk on the free list */
|
---|
444 |
|
---|
445 | for (m = (MCB *)(&heap->avail); m->fore; m = m->fore)
|
---|
446 | ;
|
---|
447 |
|
---|
448 | m->fore = mcb;
|
---|
449 | mcb->fore = (MCB *)0;
|
---|
450 | mcb->aft = m;
|
---|
451 | mcb->heap = 0L;
|
---|
452 | return(0);
|
---|
453 | }
|
---|
454 |
|
---|
455 | /* |
---|
456 |
|
---|
457 | */
|
---|
458 |
|
---|
459 |
|
---|
460 | /*
|
---|
461 | =============================================================================
|
---|
462 | realloc() -- reallocate a block of memory
|
---|
463 | =============================================================================
|
---|
464 | */
|
---|
465 |
|
---|
466 |
|
---|
467 | char *
|
---|
468 | realloc(mcb, n)
|
---|
469 | MCB *mcb;
|
---|
470 | unsigned n;
|
---|
471 | {
|
---|
472 | long x;
|
---|
473 | char *t, *s, *p;
|
---|
474 |
|
---|
475 | /* address header */
|
---|
476 |
|
---|
477 | --mcb;
|
---|
478 |
|
---|
479 | /* check for ownership here */
|
---|
480 |
|
---|
481 | if (mcb EQ 0 OR mcb->magic NE MAGIC) {
|
---|
482 |
|
---|
483 | #if DEBUGIT
|
---|
484 | printf("realloc($%lx, %u): MCB invalid\n", mcb, n);
|
---|
485 | #endif
|
---|
486 |
|
---|
487 | return((char *)0);
|
---|
488 | }
|
---|
489 |
|
---|
490 | /* round up the request and add overhead */
|
---|
491 |
|
---|
492 | x = (long)(n + 1 + sizeof(MCB)) & ~1L;
|
---|
493 |
|
---|
494 | /* if less than current size, just shrink it */
|
---|
495 |
|
---|
496 | if (mcb->size > x) {
|
---|
497 |
|
---|
498 | if (s_split(mcb, x))
|
---|
499 | return((char *)0);
|
---|
500 | else
|
---|
501 | return((char *)(++mcb));
|
---|
502 | }
|
---|
503 |
|
---|
504 | /* it's bigger - allocate new block, copy data, and free old one */
|
---|
505 |
|
---|
506 | if ((p = malloc(n)) NE 0) {
|
---|
507 |
|
---|
508 | x = mcb->size - sizeof(MCB);
|
---|
509 | s = ++mcb;
|
---|
510 | t = p;
|
---|
511 |
|
---|
512 | while (x--)
|
---|
513 | *t++ = *s++;
|
---|
514 |
|
---|
515 | free(mcb);
|
---|
516 | return(p);
|
---|
517 | }
|
---|
518 |
|
---|
519 | #if DEBUGIT
|
---|
520 | printf("realloc($%lx, %u): unable to reallocate\n", mcb, n);
|
---|
521 | #endif
|
---|
522 | return((char *)0);
|
---|
523 | }
|
---|