![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386|
Return to alloc.c CVS log | Up to [MW Coherent from dump] / coherent / b / STREAMS / coh.386 |
1.1 root 1: /* $Header: /src386/STREAMS/coh.386/RCS/alloc.c,v 2.3 93/08/09 13:35:06 bin Exp Locker: bin $ */
2: /* (lgl-
3: * The information contained herein is a trade secret of Mark Williams
4: * Company, and is confidential information. It is provided under a
5: * license agreement, and may be copied or disclosed only under the
6: * terms of that agreement. Any reproduction or disclosure of this
7: * material without the express written authorization of Mark Williams
8: * Company or persuant to the license agreement is unlawful.
9: *
10: * COHERENT Version 2.3.37
11: * Copyright (c) 1982, 1983, 1984.
12: * An unpublished work by Mark Williams Company, Chicago.
13: * All rights reserved.
14: -lgl) */
15: /*
16: * Coherent.
17: * Storage allocator.
18: *
19: * $Log: alloc.c,v $
20: * Revision 2.3 93/08/09 13:35:06 bin
21: * Kernel 82 changes
22: *
23: * Revision 2.2 93/07/26 14:28:19 nigel
24: * Nigel's R80
25: *
26: * Revision 1.4 93/04/14 10:06:13 root
27: * r75
28: *
29: * Revision 1.2 92/01/06 11:58:31 hal
30: * Compile with cc.mwc.
31: *
32: * Revision 1.1 88/03/24 16:13:25 src
33: * Initial revision
34: *
35: */
36:
37: #include <common/ccompat.h>
38: #include <common/__parith.h>
39: #include <common/_tricks.h>
40: #include <kernel/param.h>
41: #include <sys/debug.h>
42:
43: #include <sys/coherent.h>
44: #include <sys/errno.h>
45: #include <sys/proc.h>
46:
47: #include <kernel/alloc.h>
48:
49: /*
50: * Alloc definitions. These used to be in <sys/machine.h> for some unknown
51: * and unknowable reason. They belong here, so now here they are. Since the
52: * person(s) who wrote this stuff neglected to mention what the alignment
53: * issues are, we'll stay with what they did.
54: *
55: * This stuff is aligned on double-byte boundaries and the pointer to the
56: * next block in a circular list is tagged with the status of the current
57: * block. Blocks are not coalesced when freed, that is done by the allocator
58: * when trying to locate a sufficiently large free block.
59: *
60: * As an extra twist, you might have wondered why alloc () tries to loop
61: * twice over the whole arena. It does that because it looks for an exact fit
62: * (after coalescing). The allocator has no memory because there is no actual
63: * overall arena structure, so every call to alloc () will try to coalesce the
64: * entire arena unless there is an exact-sized hole.
65: */
66:
67: enum {
68: BLOCK_FREE = 0,
69: BLOCK_USED
70: };
71:
72: #define ALIGN_MASK 1
73: #define align(p) ((ALL *) ((__ptr_arith_t) (p) & ~ ALIGN_MASK))
74: #define link(p) align ((p)->a_link)
75: #define tstfree(p) (((p)->a_link & BLOCK_USED) == BLOCK_FREE)
76:
77: #define MAKE_LINK(a,f) ((__ptr_arith_t) a + (f))
78: #define MAKE_FREE(a) ((a)->a_link &= ~ BLOCK_USED)
79: #define MAKE_USED(a) ((a)->a_link |= BLOCK_USED)
80:
81:
82: typedef union all_u {
83: __ptr_arith_t a_link;
84: } ALL;
85:
86:
87: #define NEXT_FIT 1
88:
89: #if NEXT_FIT
90:
91: struct _heap {
92: ALL * _next_block;
93: };
94:
95: #define HEAP_CONTROL_SIZE sizeof (heap_t)
96: #define START_BLOCK(heap) ((heap)->_next_block)
97: #define SET_START_BLOCK(heap,newstart) \
98: ((heap)->_next_block = (newstart))
99: #else
100:
101: #define HEAP_CONTROL_SIZE 0
102: #define START_BLOCK(heap) ((ALL *) (heap))
103: #define SET_START_BLOCK(heap,newstart) ((void) 0)
104:
105: #endif
106:
107: #ifndef TEST /* Do not test setarena() or alloc() or free(). */
108:
109: /*
110: * Create an arena.
111: */
112:
113: heap_t *
114: setarena(cp, n)
115: register char *cp;
116: {
117: ALL * first_block;
118: ALL * last_block;
119: heap_t * heap_control;
120:
121: /*
122: * Begin by aligning the memory passed in and rounding down the size.
123: */
124:
125: {
126: int align = (__ptr_arith_t) cp & ALIGN_MASK;
127:
128: if (align) {
129: align = ALIGN_MASK + 1 - align;
130: cp += align;
131: n -= align;
132: }
133:
134: n &= ~ sizeof (ALL *);
135: }
136:
137: /*
138: * Make room for a heap control area.
139: */
140:
141: heap_control = (heap_t *) cp;
142:
143: cp += HEAP_CONTROL_SIZE;
144: n -= HEAP_CONTROL_SIZE;
145:
146: first_block = (ALL *) cp;
147: if ((last_block = (ALL *) (cp + n) - 1) < first_block)
148: panic("Arena %x too small", (int) cp);
149:
150: /*
151: * The initial memory arena consists of a circular list of blocks,
152: * one large free block and one tiny used block at the end. In the
153: * original "design", there was no heap control block.
154: */
155:
156: first_block->a_link = MAKE_LINK (last_block, BLOCK_FREE);
157: last_block->a_link = MAKE_LINK (first_block, BLOCK_USED);
158:
159: SET_START_BLOCK (heap_control, first_block);
160: return heap_control;
161: }
162:
163:
164: #if 0
165: /*
166: * NIGEL: This code intrigues me... let's keep statistics.
167: */
168:
169: typedef unsigned long stat_t;
170:
171: static stat_t _allocations;
172: static stat_t _block_tests;
173: static stat_t _block_fits;
174: static stat_t _exact_fits;
175:
176: #define ADD_STAT(stat) ((stat += 1) == 0 ? stat -- : 0)
177:
178: void dumpstats () {
179: printf ("allocations = %d\ntotal tests = %d\n"
180: "total matches = %d\nexact fits = %d\n",
181: _allocations, _block_tests, _block_fits, _exact_fits);
182: }
183: #else
184: # define ADD_STAT(stat) ((void) 0)
185: #endif
186:
187: /*
188: * Allocate `l' bytes of memory.
189: */
190:
191: __VOID__ *
192: alloc (heap_control, size)
193: heap_t * heap_control;
194: size_t size;
195: {
196: register ALL *scan_block;
197: register ALL *next_block;
198: register unsigned i;
199: register unsigned n;
200: register unsigned s;
201:
202: ADD_STAT (_allocations);
203:
204: n = 1 + __DIVIDE_ROUNDUP (size, sizeof (ALL));
205:
206: #if EXACT_FIT
207: for (i = 0 ; i < 2 ; i ++) {
208: #endif
209: for (scan_block = START_BLOCK (heap_control) ;
210: link (scan_block) != START_BLOCK (heap_control) ;
211: scan_block = link (scan_block)) {
212: ASSERT (vtop (scan_block) != NULL);
213: ADD_STAT (_block_tests);
214:
215: if (! tstfree (scan_block))
216: continue;
217:
218: for (next_block = link (scan_block) ;
219: tstfree (next_block) ;
220: next_block = link (next_block))
221: if (next_block == START_BLOCK (heap_control))
222: break;
223:
224: scan_block->a_link = MAKE_LINK (next_block,
225: BLOCK_FREE);
226: if ((s = next_block - scan_block) < n)
227: continue;
228:
229: ADD_STAT (_block_fits);
230:
231: if (s > n) {
232: #if EXACT_FIT
233: /*
234: * This innocent-looking line of code is what makes this system prefer
235: * exact fits (which only happen about 10% of the time from the
236: * statistics which I have collected).
237: */
238: if (i == 0)
239: continue;
240: #endif
241: (scan_block + n)->a_link =
242: MAKE_LINK (next_block, BLOCK_FREE);
243: next_block = scan_block + n;
244: scan_block->a_link = MAKE_LINK (next_block,
245: BLOCK_FREE);
246: }
247: MAKE_USED (scan_block);
248: SET_START_BLOCK (heap_control, next_block);
249: #if 0
250: memset (scan_block + 1, 0, size);
251: #endif
252: #if EXACT_FIT
253: if (i == 0)
254: ADD_STAT (_exact_fits);
255: #endif
256: return (__VOID__ *) (scan_block + 1);
257: }
258: #if EXACT_FIT
259: }
260: #endif
261: u.u_error = ENOSPC;
262: return NULL;
263: }
264:
265: /*
266: * Free memory.
267: */
268: free(cp)
269: char *cp;
270: {
271: register ALL *ap;
272: extern char __end;
273:
274: #if 0
275: ap = ((ALL *)cp) - 1;
276: if (ap<(ALL *)&__end || tstfree(ap))
277: panic("Bad free %x\n", (unsigned)cp);
278: #else
279: ap = ((ALL *)cp) - 1;
280: if (ap<(ALL *)&__end) {
281: int *r = (int *)(&cp); /* return address */
282: printf("cp=%x ap=%x &__end=%x\n", cp, ap, &__end);
283: panic("Bad free() from eip=%x\n", *(r-1));
284: }
285: if (tstfree(ap)) {
286: int *r = (int *)(&cp); /* return address */
287: printf("cp=%x tstfree(%x)=%x\n", cp, ap, tstfree(ap));
288: panic("Bad free() from eip=%x\n", *(r-1));
289: }
290: #endif
291: MAKE_FREE (ap);
292: }
293:
294: #endif /* TEST */
295:
296: #ifdef _I386
297: /*
298: * unsigned char *palloc(int size);
299: *
300: * Allocate 'size' bytes of kernel space, which does not cross a click
301: * boundary. Returns a pointer to the space allocated on success,
302: * NULL on failure.
303: *
304: * Allocate twice as much memory as we need, and then return a chunk that
305: * does not cross a click boundary. Immediately before the chunk that
306: * we return, we store the true address of the chunk that was kalloc()'d.
307: *
308: * Since this routine is for relatively small short-lived objects,
309: * which we expect to allocate frequently, speed is more important than
310: * space overhead.
311: *
312: * We assume that kalloc() returns word aligned addresses.
313: *
314: * There are two cases:
315: * There is enough room before the click boundary (or there is no click
316: * boundary) for the pointer and the memory we need.
317: * Otherwise, return the chunk starting at the click boundary, storing
318: * the pointer right before the click boundary. This trick allows
319: * us to allocate up to 1 full click.
320: *
321: * If kalloc() did NOT return word aligned chunks, then there would be
322: * a third case, where there might not be enough space for the pointer
323: * before the click boundary.
324: */
325:
326: #define c_boundry(x) ctob(btoc((x)+1)) /* Next click boundary above x. */
327: #define VOID unsigned char
328:
329: #ifdef TEST
330: #undef kalloc
331: #undef kfree
332: VOID *kalloc();
333: void kfree();
334: #endif /* TEST */
335:
336: VOID *
337: palloc(size)
338: int size; /* Size in bytes of area to allocate. */
339: {
340: VOID *local_arena; /* Value returned by kalloc(). */
341: VOID *boundry; /* Next click boundry above local_arena. */
342: VOID *retval; /* What we give back to our caller. */
343:
344: if (size > NBPC)
345: panic("palloc(%x): can not palloc more than 1 click.", size);
346:
347: /* Fetch twice as much space as requested, plus a pointer. */
348: if ((local_arena = (VOID *) kalloc (sizeof (VOID *) + (2 * size)))
349: == NULL)
350: return NULL;
351:
352: boundry = (VOID *) c_boundry (local_arena);
353:
354: T_PIGGY(0x2000, printf("b: %x ", boundry));
355:
356: /* First case: enough space before the boundry. */
357: if ( (boundry - local_arena) >= (size + sizeof(VOID *)) ) {
358:
359: T_PIGGY(0x2000, printf("c1 "));
360:
361: * (VOID **)local_arena = local_arena;
362: retval = local_arena + sizeof(VOID *);
363: } else if ((boundry - local_arena) < sizeof(VOID *)) {
364: /*
365: * Second case: There is not enough space before the
366: * boundry for the whole pointer.
367: */
368: T_PIGGY(0x2000, printf("c2 "));
369:
370: * (VOID **)local_arena = local_arena;
371: retval = local_arena + sizeof(VOID *);
372: } else {
373:
374: T_PIGGY(0x2000, printf("c3: %x ", (boundry - local_arena)));
375:
376: * (VOID **)(boundry - sizeof(VOID *)) = local_arena;
377: retval = boundry;
378: }
379:
380: T_PIGGY( 0x2000,
381: printf("palloc(%x) = %x:%x (was %x:%x), ",
382: size, retval, (retval+size)-1,
383: local_arena, (local_arena+(2*size)+sizeof(VOID *))-1)
384: );
385:
386: #if 0
387: /*
388: * NIGEL: Things in trace macros must now be expressions. These ones
389: * weren't worth cleaning up.
390: */
391: T_PIGGY( 0x2000,
392: if ((retval+size)-1 > (local_arena+(2*size)+sizeof(VOID *))-1) {
393: printf("\npalloc() overrun\n");
394: }
395: if (retval < local_arena) {
396: printf("\npalloc() underrun\n");
397: }
398: );
399: #endif
400:
401: return (VOID *) retval;
402: } /* palloc() */
403:
404: /*
405: * void pfree(VOID *ptr);
406: * Free the chunk of memory 'ptr' allocated by palloc().
407: *
408: * Note that 'ptr' is really a VOID *, but we call it VOID **
409: * to simplify arithmetic.
410: *
411: * The address returned by kalloc() is stored immediately
412: * before the chunk returned by palloc().
413: */
414: void
415: pfree(ptr)
416: VOID *ptr[];
417: {
418: T_PIGGY(0x2000, printf("pfree(%x):kfree(%x), ", ptr, *(ptr-1)));
419: kfree(*(ptr-1));
420: } /* pfree() */
421:
422:
423: #ifdef TEST
424:
425: #include <sys/compat.h>
426: #include <stdio.h>
427: #include <stdarg.h>
428:
429: #define FOURK 4096 /* How many bytes in 4K? */
430: #define NUM_TESTS 40 /* How many tests do we run? */
431: #define SMALL_NUMBER 6 /* A small number whose exact value we don't care about. */
432: #define HUGE (100*FOURK) /* Allocate from this pool. */
433: #define IGNORE(v) (v==v) /* Lint food. */
434:
435: unsigned t_piggy = 0x2000; /* Turn on TRACER bits. */
436:
437: main()
438: {
439: int i;
440: VOID *chunk;
441:
442: for (i = 0; i < NUM_TESTS; ++i) {
443: if (NULL == (chunk = palloc(SMALL_NUMBER))) {
444: printf("No more fake memory to eat.\n");
445: printf("This is probably a bug.\n");
446: exit(1);
447: }
448:
449: printf("chunk: %x\n", chunk);
450: }
451: } /* main() for TEST */
452:
453: /*
454: * Print a message and die.
455: */
456:
457: panic(format)
458: char * format;
459: {
460: va_list args;
461: va_start (args, format);
462: vprintf (format, args);
463: va_end (args);
464: exit(1);
465: }
466:
467: /*
468: * Fake kalloc() for use by palloc().
469: * Allocate a chunk of some non-existant memory space.
470: */
471: VOID *
472: kalloc(size)
473: int size;
474: {
475: static VOID *base = NULL;
476: static VOID *top_free = NULL;
477: VOID *retval;
478:
479:
480: /*
481: * First time through, allocate a nice big chunk of memory
482: * to carve up.
483: */
484: if (NULL == base) {
485: if (NULL == (base = malloc(HUGE))) {
486: printf("Can not malloc %d bytes.\n", HUGE);
487: exit(1);
488: }
489: /* Make sure we start close to a click boundry. */
490: top_free = c_boundry(base) + SMALL_NUMBER;
491: }
492:
493: retval = top_free;
494: /*
495: * We want to encourage test addresses to migrate accross
496: * click boundries.
497: */
498: if (size < (FOURK - 1)) {
499: top_free += (FOURK - 1);
500: } else {
501: top_free += size;
502: }
503:
504: return(retval);
505: } /* kalloc() */
506:
507: /*
508: * Fake kfree for pfree() to use.
509: */
510: void
511: kfree(addr)
512: VOID *addr;
513: {
514: IGNORE(addr);
515: /* Do nothing! */
516: } /* kfree() */
517:
518: #endif /* TEST */
519:
520: #endif /* _I386 */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.