source: buchla-68k/orig/GEMDOS/MEMORY.C@ 6099cac

Last change on this file since 6099cac was 3ae31e9, checked in by Thomas Lopatic <thomas@…>, 8 years ago

Imported original source code.
  • Property mode set to 100755
File size: 10.7 KB
Line 
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
62struct _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
74struct _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
82short 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
90static HEAP heaps = { (HEAP *)0 };
91
92/*
93
94*/
95
96/*
97 =============================================================================
98 a_heap() --get another heap from GEMDOS
99 =============================================================================
100*/
101
102static
103HEAP *
104a_heap(x)
105long 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
175static
176s_split(mcb, x)
177MCB *mcb;
178long 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
227static
228MCB *
229aloc_s(x, heap)
230long x;
231HEAP *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
276static
277unfree(mcb)
278MCB *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
292static
293collect()
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
349char *
350malloc(n)
351unsigned 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
397free(mcb)
398MCB *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
467char *
468realloc(mcb, n)
469MCB *mcb;
470unsigned 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}
Note: See TracBrowser for help on using the repository browser.