|
0
|
1 #ifndef CYGONCE_KERNEL_MVARIMPL_INL |
|
|
2 #define CYGONCE_KERNEL_MVARIMPL_INL |
|
|
3 |
|
|
4 //========================================================================== |
|
|
5 // |
|
2
|
6 // mvarimpl.inl |
|
0
|
7 // |
|
2
|
8 // Memory pool with variable block class declarations |
|
0
|
9 // |
|
|
10 //========================================================================== |
|
|
11 //####COPYRIGHTBEGIN#### |
|
|
12 // |
|
|
13 // ------------------------------------------- |
|
|
14 // The contents of this file are subject to the Cygnus eCos Public License |
|
|
15 // Version 1.0 (the "License"); you may not use this file except in |
|
|
16 // compliance with the License. You may obtain a copy of the License at |
|
|
17 // http://sourceware.cygnus.com/ecos |
|
|
18 // |
|
|
19 // Software distributed under the License is distributed on an "AS IS" |
|
|
20 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the |
|
|
21 // License for the specific language governing rights and limitations under |
|
|
22 // the License. |
|
|
23 // |
|
|
24 // The Original Code is eCos - Embedded Cygnus Operating System, released |
|
|
25 // September 30, 1998. |
|
|
26 // |
|
|
27 // The Initial Developer of the Original Code is Cygnus. Portions created |
|
2
|
28 // by Cygnus are Copyright (C) 1998,1999 Cygnus Solutions. All Rights Reserved. |
|
0
|
29 // ------------------------------------------- |
|
|
30 // |
|
|
31 //####COPYRIGHTEND#### |
|
|
32 //========================================================================== |
|
|
33 //#####DESCRIPTIONBEGIN#### |
|
|
34 // |
|
2
|
35 // Author(s): hmt |
|
|
36 // Contributors: hmt |
|
|
37 // Date: 1998-03-23 |
|
|
38 // Purpose: Define Mvarimpl class interface |
|
|
39 // Description: Inline class for constructing a variable block allocator |
|
|
40 // Usage: #include <cyg/kernel/mvarimpl.hxx> |
|
|
41 // #include <cyg/kernel/mvarimpl.inl> |
|
0
|
42 // |
|
|
43 //####DESCRIPTIONEND#### |
|
|
44 // |
|
|
45 //========================================================================== |
|
|
46 |
|
|
47 // Simple non-coalescing allocator |
|
|
48 |
|
|
49 // The free list is stored on a doubly linked list, each member of |
|
|
50 // which is stored in the body of the free memory. The head of the |
|
|
51 // list has the same structure but its size field is zero. This |
|
|
52 // resides in the memory pool structure. Always having at least one |
|
|
53 // item on the list simplifies the alloc and free code. |
|
|
54 |
|
|
55 // |
|
|
56 inline cyg_int32 |
|
|
57 Cyg_Mempool_Variable_Implementation::roundup( cyg_int32 size ) |
|
|
58 { |
|
|
59 |
|
|
60 size += sizeof(struct memdq); |
|
|
61 size = (size + alignment - 1) & -alignment; |
|
|
62 return size; |
|
|
63 } |
|
|
64 |
|
|
65 Cyg_Mempool_Variable_Implementation::Cyg_Mempool_Variable_Implementation( |
|
|
66 cyg_uint8 *base, |
|
|
67 cyg_int32 size, |
|
|
68 CYG_ADDRWORD align ) |
|
|
69 { |
|
|
70 CYG_ASSERT( align > 0, "Bad alignment" ); |
|
|
71 CYG_ASSERT( size > 0, "Bad size" ); |
|
|
72 CYG_ASSERT(0!=align ,"align is zero"); |
|
|
73 CYG_ASSERT(0==(align & align-1),"align not a power of 2"); |
|
|
74 |
|
|
75 obase=base; |
|
|
76 osize=size; |
|
|
77 oalign=align; |
|
|
78 |
|
|
79 alignment = align; |
|
|
80 while(alignment < (cyg_int32)sizeof(struct memdq)) |
|
|
81 alignment += alignment; |
|
|
82 CYG_ASSERT(0==(alignment & alignment-1),"alignment not a power of 2"); |
|
|
83 |
|
|
84 bottom = (cyg_uint8 *)roundup((cyg_int32)base); |
|
|
85 top = (cyg_uint8 *)((cyg_int32)(base+size) & -alignment); |
|
|
86 |
|
|
87 CYG_ASSERT( top > bottom , "heap too small" ); |
|
|
88 CYG_ASSERT( ((cyg_int32)bottom & alignment-1)==0, "bottom badly aligned" ); |
|
|
89 CYG_ASSERT( ((cyg_int32)top & alignment-1)==0, "top badly aligned" ); |
|
|
90 |
|
|
91 struct memdq *hdq = &head, *dq = (struct memdq *)bottom; |
|
|
92 |
|
|
93 hdq->prev = hdq->next = dq; |
|
|
94 hdq->size = 0; |
|
|
95 dq->prev = dq->next = hdq; |
|
|
96 |
|
|
97 freemem = dq->size = top-bottom; |
|
|
98 } |
|
|
99 |
|
|
100 Cyg_Mempool_Variable_Implementation::~Cyg_Mempool_Variable_Implementation() |
|
|
101 { |
|
|
102 } |
|
|
103 |
|
|
104 // allocation is simple |
|
|
105 // First we look down the free list for a large enough block |
|
|
106 // If we find a block the right size, we unlink the block from |
|
|
107 // the free list and return a pointer to it. |
|
|
108 // If we find a larger block, we chop a piece off the end |
|
|
109 // and return that |
|
|
110 // Otherwise we will eventually get back to the head of the list |
|
|
111 // and return NULL |
|
|
112 inline cyg_uint8 * |
|
|
113 Cyg_Mempool_Variable_Implementation::alloc( cyg_int32 size ) |
|
|
114 { |
|
|
115 struct memdq *dq = &head; |
|
|
116 cyg_uint8 *alloced; |
|
|
117 |
|
|
118 size = roundup(size); |
|
|
119 |
|
|
120 do { |
|
|
121 CYG_ASSERT( dq->next->prev==dq, "Bad link in dq"); |
|
|
122 dq = dq->next; |
|
|
123 if(0 == dq->size) { |
|
|
124 CYG_ASSERT(dq == &head, "bad free block"); |
|
|
125 return NULL; |
|
|
126 } |
|
|
127 } while(dq->size < size); |
|
|
128 |
|
|
129 if( size == dq->size ) { |
|
|
130 // exact fit -- unlink from free list |
|
|
131 dq->prev->next = dq->next; |
|
|
132 dq->next->prev = dq->prev; |
|
|
133 alloced = (cyg_uint8 *)dq; |
|
|
134 } else { |
|
|
135 |
|
|
136 CYG_ASSERT( dq->size > size, "block found is too small"); |
|
|
137 |
|
|
138 // allocate portion of memory from end of block |
|
|
139 |
|
|
140 dq->size -=size; |
|
|
141 |
|
|
142 // The portion left over has to be large enough to store a |
|
|
143 // struct memdq. This is guaranteed because the alignment is |
|
|
144 // larger than the size of this structure. |
|
|
145 |
|
|
146 CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=dq->size , |
|
|
147 "not enough space for list item" ); |
|
|
148 |
|
|
149 alloced = (cyg_uint8 *)dq + dq->size; |
|
|
150 } |
|
|
151 |
|
|
152 CYG_ASSERT( bottom<=alloced && alloced<=top, "alloced outside pool" ); |
|
|
153 |
|
|
154 // Set size on allocated block |
|
|
155 |
|
|
156 dq = (struct memdq *)alloced; |
|
|
157 dq->size = size; |
|
|
158 dq->next = dq->prev = (struct memdq *)0xd530d53; // magic number |
|
|
159 |
|
|
160 freemem -=size; |
|
|
161 return alloced + sizeof(struct memdq); |
|
|
162 } |
|
|
163 |
|
|
164 // As no coalescing is done, free is simply a matter of using the |
|
|
165 // freed memory as an element of the free list linking it in at the |
|
|
166 // start. |
|
|
167 |
|
|
168 inline cyg_bool |
|
|
169 Cyg_Mempool_Variable_Implementation::free( cyg_uint8 *p, cyg_int32 size ) |
|
|
170 { |
|
|
171 if(!(bottom<=p&&p<=top)) |
|
|
172 return false; |
|
|
173 |
|
|
174 struct memdq *hdq=&head,*dq=(struct memdq *)(p-sizeof(struct memdq)); |
|
|
175 |
|
|
176 // check magic number in block to be freed |
|
|
177 if(dq->next != dq->prev || dq->next != (struct memdq *)0xd530d53) |
|
|
178 return false; |
|
|
179 |
|
|
180 if(0==size) { |
|
|
181 size = dq->size; |
|
|
182 } else { |
|
|
183 size = roundup(size); |
|
|
184 } |
|
|
185 |
|
|
186 if(dq->size != size) |
|
|
187 return false; |
|
|
188 |
|
|
189 CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=size , |
|
|
190 "not enough space for list item" ); |
|
|
191 |
|
|
192 #ifdef CYGSEM_KERNEL_MEMORY_COALESCE |
|
|
193 // For simple coalescing have the free list be sorted by memory base address |
|
|
194 struct memdq *idq; |
|
|
195 |
|
|
196 for (idq = hdq->next; idq != hdq; idq = idq->next) { |
|
2
|
197 if (idq->next > dq) |
|
|
198 break; |
|
0
|
199 } |
|
|
200 dq->size = size; |
|
|
201 if (idq != hdq) { |
|
|
202 dq->prev = idq; |
|
|
203 dq->next = idq->next; |
|
|
204 idq->next = dq; |
|
|
205 dq->next->prev = dq; |
|
|
206 } else { |
|
|
207 dq->next = idq; |
|
2
|
208 dq->prev = idq->prev; |
|
|
209 idq->prev = dq; |
|
|
210 dq->prev->next = dq; |
|
0
|
211 } |
|
|
212 // Now do coalescing |
|
|
213 if ((char *)dq + dq->size == (char *)dq->next) { |
|
2
|
214 dq->size += dq->next->size; |
|
0
|
215 dq->next = dq->next->next; |
|
2
|
216 dq->next->prev = dq; |
|
0
|
217 } |
|
|
218 if ((char *)dq->prev + dq->prev->size == (char *)dq) { |
|
|
219 dq->prev->size += dq->size; |
|
2
|
220 dq->prev->next = dq->next; |
|
|
221 dq->next->prev = dq->prev; |
|
|
222 dq = dq->prev; |
|
0
|
223 } |
|
|
224 #else |
|
|
225 dq->prev = hdq; |
|
|
226 dq->next = hdq->next; |
|
|
227 dq->size = size; |
|
|
228 hdq->next = dq; |
|
|
229 dq->next->prev=dq; |
|
|
230 #endif |
|
|
231 |
|
|
232 freemem +=size; |
|
|
233 return true; |
|
|
234 } |
|
|
235 |
|
|
236 |
|
|
237 inline void |
|
|
238 Cyg_Mempool_Variable_Implementation::get_arena( |
|
|
239 cyg_uint8 * &base, |
|
|
240 cyg_int32 &size, |
|
|
241 CYG_ADDRWORD &maxfree) |
|
|
242 { |
|
|
243 struct memdq *dq = &head; |
|
|
244 cyg_int32 mf = 0; |
|
|
245 |
|
|
246 do { |
|
|
247 CYG_ASSERT( dq->next->prev==dq, "Bad link in dq"); |
|
|
248 dq = dq->next; |
|
|
249 if(0 == dq->size) { |
|
|
250 CYG_ASSERT(dq == &head, "bad free block"); |
|
|
251 break; |
|
|
252 } |
|
|
253 if(dq->size > mf) |
|
|
254 mf = dq->size; |
|
|
255 } while(1); |
|
|
256 |
|
|
257 base = obase; |
|
|
258 size = osize; |
|
|
259 maxfree = mf; |
|
|
260 } |
|
|
261 |
|
|
262 |
|
|
263 inline cyg_int32 |
|
|
264 Cyg_Mempool_Variable_Implementation::get_allocation_size( cyg_uint8 *ptr ) |
|
|
265 { |
|
|
266 CYG_CHECK_DATA_PTR(ptr, "Requested allocation size of bad data pointer!"); |
|
|
267 |
|
|
268 if(!(bottom<=ptr && ptr<=top)) |
|
|
269 return -1; |
|
|
270 |
|
|
271 struct memdq *dq=(struct memdq *)(ptr-sizeof(struct memdq)); |
|
|
272 |
|
|
273 // check magic number in block to be freed |
|
|
274 if(dq->next != dq->prev || dq->next != (struct memdq *)0xd530d53) |
|
|
275 return -1; |
|
|
276 |
|
|
277 return dq->size; |
|
|
278 |
|
|
279 } // get_allocation_size() |
|
|
280 |
|
|
281 // ------------------------------------------------------------------------- |
|
|
282 #endif // ifndef CYGONCE_KERNEL_MVARIMPL_INL |
|
|
283 // EOF mvarimpl.inl |
