![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to st_alloc.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / f / usr / include / kernel|
Return to st_alloc.h CVS log | Up to [MW Coherent from dump] / coherent / f / usr / include / kernel |
1.1 root 1: #ifndef __KERNEL_ST_ALLOC_H__
2: #define __KERNEL_ST_ALLOC_H__
3:
4: /*
5: *-IMPORTS:
6: * <common/ccompat.h>
7: * __CONST__
8: * __PROTO__
9: * __VOID__
10: * __PROTO ()
11: * <common/xdebug.h>
12: * __LOCAL__
13: */
14:
15: #include <limits.h>
16: #include <common/ccompat.h>
17: #include <common/xdebug.h>
18: #include <common/_size.h>
19:
20:
21: /*
22: * Definitions/declarations for the quick arena manager.
23: *
24: * The quick arena manager's basic algorithm utilizes a heap (in the sense
25: * defined below) to implement a binary-searchable index of block buckets
26: * ordered by size.
27: *
28: * The primariy characteristic of this algorithm is its' speed ; the growth
29: * rate of the execution time is O (log W), where W is the number of words in
30: * the arena being managed.
31: *
32: * This implementation is directly derived from the article in which this
33: * algorithm first appeared;
34: *
35: * "Efficient Implementation of the First-Fit Strategy for Dynamic
36: * Storage Allocation"
37: * R. P. Brent, Australian National University
38: * ACM Transactions on Programming Languages and Systems
39: * Volume 11, No. 3, July 1989 pp 388-403.
40: */
41:
42:
43: /*
44: * This source code deviates somewhat from the terminology used in the
45: * article, due to the large number of ambiguous terms here. The following
46: * definitions are used exclusively in the commentary and selection of
47: * identifiers within this source code :
48: *
49: * heap a balanced binary tree with implicit links, esp.
50: * used to perform max/min calculations or binary search
51: *
52: * arena the memory area being managed
53: *
54: * block a single unit of contiguous allocated or free memory
55: *
56: * bucket a subsection of the heap containing zero or more
57: * blocks
58: */
59:
60:
61: /*
62: * Definition of the type of an underlying machine address for each one of
63: * the pointer types used in the arena control structure.
64: *
65: * An interesting question : what type should be being used for the heap
66: * control words, short or long? If a short is used for the size of a
67: * control word, then we are limited to 64k bytes for the size of a single
68: * allocation arena.
69: */
70:
71: typedef int _ST_WORD_T;
72:
73: #if INT_MAX > SHRT_MAX
74: #define _ST_SIZE_MASK 0x7FFFFFFF
75: #define _ST_FREE_MASK 0x80000000
76: #else
77: #define _ST_SIZE_MASK 0x7FFF
78: #define _ST_FREE_MASK 0x8000
79: #endif
80:
81: typedef _ST_WORD_T * _ST_ADDR_T;
82:
83: #define _ST_HEAP_ADDR(q,a) (a)
84: #define _ST_HEAP_BUCKET(q,a) (((char *) (a) - (char *) (q)->_arena_base) / ((q)->_words_per_bucket * sizeof (_ST_WORD_T)))
85:
86:
87: /*
88: * For the control word of a block, it is *vital* that all used blocks
89: * compare as "<" with a free block, and that free blocks test as normal
90: * integers.
91: */
92:
93: #define _ST_BLOCK_CONTROL(q,a) (* _ST_HEAP_ADDR (q, (a)))
94: #define _ST_BLOCK_SIZE(c) ((c) & _ST_SIZE_MASK)
95: #define _ST_BLOCK_FREE(c) (((c) & _ST_FREE_MASK) == 0)
96: #define _ST_BLOCK_SET_FREE(q,a,n) (void) (_ST_BLOCK_CONTROL (q, (a)) = (n) & ~ _ST_FREE_MASK)
97: #define _ST_BLOCK_SET_USED(q,a,n) (void) (_ST_BLOCK_CONTROL (q, (a)) = (n) | _ST_FREE_MASK)
98:
99:
100: #define _ST_HEAP_BIGGEST(q,s) ((q)->_bucket_biggest [s])
101: #define _ST_HEAP_FIRST(q,s) ((q)->_bucket_first [s])
102:
103: #define _ST_BUCKET_SIBLING(b) (b ^ 1)
104: #define _ST_BUCKET_PARENT(b) (b >>= 1)
105:
106: #define _ST_HEAP_NEXT(a,c) ((_ST_ADDR_T) ((a) + _ST_BLOCK_SIZE (c)))
107: #define _ST_HEAP_NEXT_RAW(a,c) ((_ST_ADDR_T) ((a) + (c)))
108:
109: #define _ST_SET_ERROR(q,e) ((q)->_heap_error = (e))
110: #define _ST_HEAP_ERROR(q) ((q)->_heap_error)
111:
112:
113: /*
114: * Help clients initialise the arena.
115: */
116:
117: #define _ST_HEAP_CONTROL_SIZE(segs)\
118: (sizeof (struct _st_heap_control) + \
119: (segs) * (2 * sizeof (_ST_WORD_T) + sizeof (_ST_ADDR_T)))
120:
121: /*
122: * Allocation control block. This block is normally followed by vectors
123: * containing a maximum block size heap and a vector defining the first free
124: * block in an allocation bucket.
125: */
126:
127: struct _st_heap_control {
128:
129: int _buckets_inuse; /* number of active buckets */
130: int _buckets_maximum; /* maximum possible buckets */
131: int _words_per_bucket; /* memory words per bucket */
132: size_t _arena_size; /* total bytes in arena */
133:
134: _ST_WORD_T * _bucket_biggest; /* bucket size ordered heap */
135: _ST_ADDR_T * _bucket_first; /* address of first block */
136: _ST_ADDR_T _arena_base;
137: /*
138: * base address of the first
139: * word in the arena, same as
140: * _bucket_first [0]
141: */
142: _ST_ADDR_T _arena_end;
143: /*
144: * Address of last word in
145: * the arena +1
146: */
147: __CONST__ char * _heap_error;
148: /*
149: * If this heap is corrupt,
150: * points to a string that
151: * describes the problem
152: */
153: };
154:
155: typedef struct _st_heap_control _ST_HEAP_CONTROL, * _ST_HEAP_CONTROL_P;
156:
157:
158: /*
159: * As an additional check, we can make clients of st_disp () pass in the
160: * size of the block to free as (i) an additional assertion check against
161: * bugs, and (ii) because a faster/less overhead implementation of the
162: * algorithm might be possible where there is no header for allocated blocks
163: * (the free blocks contain a size and a pointer to the next free block).
164: */
165:
166: #define USE_ST_SIZE
167:
168: #ifdef USE_ST_SIZE
169: #define ST_FREE_SIZE(x) , x
170: #else
171: #define ST_FREE_SIZE(x)
172: #endif
173:
174:
175: /*
176: * Public function prototypes
177: */
178:
179: __EXTERN_C_BEGIN__
180:
181: int st_assert __PROTO ((_ST_HEAP_CONTROL_P _q));
182: __VOID__ * st_alloc __PROTO ((_ST_HEAP_CONTROL_P _q,
183: size_t _size));
184: int st_free __PROTO ((_ST_HEAP_CONTROL_P _q,
185: __VOID__ * _a
186: ST_FREE_SIZE (size_t _size)));
187: __VOID__ * st_realloc __PROTO ((_ST_HEAP_CONTROL_P _q,
188: __VOID__ * _a, size_t _newsize
189: ST_FREE_SIZE (size_t _oldsize)));
190: void st_init __PROTO ((_ST_HEAP_CONTROL_P _q));
191: void st_ctor __PROTO ((_ST_HEAP_CONTROL_P _q, int _segs,
192: size_t _arensize,
193: _ST_ADDR_T _arenabase));
194: size_t st_maxavail __PROTO ((_ST_HEAP_CONTROL_P _q));
195:
196: __EXTERN_C_END__
197:
198: #endif /* ! defined (__KERNEL_ST_ALLOC_H__) */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.