1 | Memory allocation package - Implementation Notes |
---|
2 | ------------------------------------------------ |
---|
3 | |
---|
4 | |
---|
5 | |
---|
6 | Made with loving care by Jonathan Larmour (jlarmour@redhat.com) |
---|
7 | Initial version: 2000-07-03 |
---|
8 | Last updated: 2000-07-03 |
---|
9 | |
---|
10 | |
---|
11 | |
---|
12 | Meta |
---|
13 | ---- |
---|
14 | |
---|
15 | This document describes some interesting bits and pieces about the memory |
---|
16 | allocation package - CYGPKG_MEMALLOC. It is intended as a guide to |
---|
17 | developers, not users. This isn't (yet) in formal documentation format, |
---|
18 | and probably should be. |
---|
19 | |
---|
20 | |
---|
21 | Philosophy |
---|
22 | ---------- |
---|
23 | |
---|
24 | The object of this package is to provide everything required for dynamic |
---|
25 | memory allocation, some sample implementations, the ability to plug in |
---|
26 | more implementations, and a standard malloc() style interface to those |
---|
27 | allocators. |
---|
28 | |
---|
29 | The classic Unix-style view of a heap is using brk()/sbrk() to extend the |
---|
30 | data segment of the application. However this is inappropriate for an |
---|
31 | embedded system because: |
---|
32 | |
---|
33 | - you may not have an MMU, which means memory may be disjoint, thus breaking |
---|
34 | this paradigm |
---|
35 | |
---|
36 | - in a single process system there is no need to play tricks since there |
---|
37 | is only the one address space and therefore heap area to use. |
---|
38 | |
---|
39 | Therefore instead, we base the heap on the idea of fixed size memory pools. |
---|
40 | The size of each pool is known in advance. |
---|
41 | |
---|
42 | |
---|
43 | Overview |
---|
44 | -------- |
---|
45 | |
---|
46 | Most of the infrastructure this package provides is geared towards |
---|
47 | supporting the ISO standard malloc() family of functions. A "standard" |
---|
48 | eCos allocator should be able to plug in to this infrastructure and |
---|
49 | transparently work. The interface is based on simple use of C++ - nothing |
---|
50 | too advanced. |
---|
51 | |
---|
52 | The allocator to use is dictated by the |
---|
53 | CYGBLD_MEMALLOC_MALLOC_IMPLEMENTATION_HEADER option. Choosing the |
---|
54 | allocator can be done by ensuring the CDL for the new allocator |
---|
55 | has a "requires" that sets the location of the header to use when that |
---|
56 | allocator is enabled. New allocators should default to disabled, so they |
---|
57 | don't have to worry about which one is the default, thus causing CDL |
---|
58 | conflicts. When enabled the new allocator should also claim to implement |
---|
59 | CYGINT_MEMALLOC_MALLOC_ALLOCATORS. |
---|
60 | |
---|
61 | The implementation header file that is set must have a special property |
---|
62 | though - it may be included with __MALLOC_IMPL_WANTED defined. If this |
---|
63 | is the case, then this means the infrastructure wants to find out the |
---|
64 | name of the class that is implemented in this header file. This is done |
---|
65 | by setting CYGCLS_MEMALLOC_MALLOC_IMPL. If __MALLOC_IMPL_WANTED is defined |
---|
66 | then no non-preprocessor output should be generated, as this will be included |
---|
67 | in a TCL script in due course. An existing example from this package would |
---|
68 | be: |
---|
69 | |
---|
70 | #define CYGCLS_MEMALLOC_MALLOC_IMPL Cyg_Mempool_dlmalloc |
---|
71 | |
---|
72 | // if the implementation is all that's required, don't output anything else |
---|
73 | #ifndef __MALLOC_IMPL_WANTED |
---|
74 | |
---|
75 | class Cyg_Mempool_dlmalloc |
---|
76 | { |
---|
77 | [etc.] |
---|
78 | |
---|
79 | To meet the expectations of malloc, the class should have the following |
---|
80 | public interfaces (for details it is best to look at some of the |
---|
81 | examples in this package): |
---|
82 | |
---|
83 | - a constructor taking arguments of the form: |
---|
84 | |
---|
85 | ALLOCATORNAME( cyg_uint8 *base, cyg_int32 size ); |
---|
86 | |
---|
87 | If you want to be able to support other arguments for when accessing |
---|
88 | the allocator directly you can add them, but give them default values, |
---|
89 | or use overloading |
---|
90 | |
---|
91 | - a destructor |
---|
92 | |
---|
93 | - a try_alloc() function that returns new memory, or NULL on failure: |
---|
94 | |
---|
95 | cyg_uint8 * |
---|
96 | try_alloc( cyg_int32 size ); |
---|
97 | |
---|
98 | - a free() function taking one pointer argument that returns a boolean |
---|
99 | for success or failure: |
---|
100 | |
---|
101 | cyg_bool |
---|
102 | free( cyg_uint8 *ptr ); |
---|
103 | |
---|
104 | Again, extra arguments can be added, as long as they are defaulted. |
---|
105 | |
---|
106 | |
---|
107 | - resize_alloc() which is designed purely to support realloc(). It |
---|
108 | has the prototype: |
---|
109 | cyg_uint8 * |
---|
110 | resize_alloc( cyg_uint8 *alloc_ptr, cyg_int32 newsize, |
---|
111 | cyg_int32 *oldsize ); |
---|
112 | |
---|
113 | The idea is that if alloc_ptr can be adjusted to newsize, then it will |
---|
114 | be. If oldsize is non-NULL the old size (possibly rounded) is placed |
---|
115 | there. However what this *doesn't* do (unlike the real realloc()) is |
---|
116 | fall back to doing a new malloc(). All it does is try to do tricks |
---|
117 | inside the allocator. It's up to higher layers to call malloc(). |
---|
118 | |
---|
119 | - get_status() allows the retrieval of info from the allocator. The idea |
---|
120 | is to pass in the bitmask OR of the flags defined in common.hxx, which |
---|
121 | selects what information is requested. If the request is supported by |
---|
122 | the allocator, the approriate structure fields are filled in; otherwise |
---|
123 | unsupported fields will be left with the value -1. (The constructor for |
---|
124 | Cyg_Mempool_Status initializes them to -1). If you want to reinitialize |
---|
125 | the structure and deliberately lose the data in a Cyg_Mempool_Status |
---|
126 | object, you need to invoke the init() method of the status object to |
---|
127 | reinitialize it. |
---|
128 | |
---|
129 | void |
---|
130 | get_status( cyg_mempool_status_flag_t flags, Cyg_Mempool_Status &status ); |
---|
131 | |
---|
132 | A subset of the available stats are exported via mallinfo() |
---|
133 | |
---|
134 | |
---|
135 | Cyg_Mempolt2 template |
---|
136 | --------------------- |
---|
137 | |
---|
138 | If using the eCos kernel with multiple threads accessing the allocators, |
---|
139 | then obviously you need to be sure that the allocator is accessed in a |
---|
140 | thread-safe way. The malloc() wrappers do not make any assumptions |
---|
141 | about this. One helpful approach currently used by all the allocators |
---|
142 | in this package is to (optionally) use a template (Cyg_Mempolt2) that |
---|
143 | provides extra functions like a blocking alloc() that waits for memory |
---|
144 | to be freed before returning, and a timed variant. Other calls are |
---|
145 | generally passed straight through, but with the kernel scheduler locked |
---|
146 | to prevent pre-emption. |
---|
147 | |
---|
148 | You don't have to use this facility to fit into the infrastructure though, |
---|
149 | and thread safety is not a prerequisite for the rest of the infrastructure. |
---|
150 | And indeed certain allocators will be able to do scheduling at a finer |
---|
151 | granularity than just locking the scheduler every time. |
---|
152 | |
---|
153 | The odd name is because of an original desire to keep 8.3 filenames, which |
---|
154 | was reflected in the class name to make it correspond to the filename. |
---|
155 | There used to be an alternative Cyg_Mempoolt template, but that has fallen |
---|
156 | into disuse and is no longer supported. |
---|
157 | |
---|
158 | |
---|
159 | Automatic heap sizing |
---|
160 | --------------------- |
---|
161 | |
---|
162 | This package contains infrastructure to allow the automatic definition |
---|
163 | of memory pools that occupy all available memory. In order to do this |
---|
164 | you must use the eCos Memory Layout Tool to define a user-defined section. |
---|
165 | These sections *must* have the prefix "heap", for example "heap1", "heap2", |
---|
166 | "heapdram" etc. otherwise they will be ignored. |
---|
167 | |
---|
168 | The user-defined section may be of fixed size, or of unknown size. If it |
---|
169 | has unknown size then its size is dictated by either the location of |
---|
170 | the next following section with an absolute address, or if there are |
---|
171 | no following sections, the end of the memory region. The latter should |
---|
172 | be the norm. |
---|
173 | |
---|
174 | If no user-defined sections starting with "heap" are found, a fallback |
---|
175 | static array (i.e. allocated in the BSS) will be used, whose size can |
---|
176 | be set in the configuration. |
---|
177 | |
---|
178 | It is also possible to define multiple heap sections. This is |
---|
179 | necessary when you have multiple disjoint memory regions, and no MMU |
---|
180 | to join it up into one contiguous memory space. In which case |
---|
181 | a special wrapper allocator object is automatically used. This object |
---|
182 | is an instantiation of the Cyg_Mempool_Joined template class, |
---|
183 | defined in memjoin.hxx. It is instantiated with a list of every heap |
---|
184 | section, which it then records. It's sole purpose is to act as a go |
---|
185 | between to the underlying implementation, and does the right thing by |
---|
186 | using pointer addresses to determine which memory pool the pointer |
---|
187 | allocator, and therefore which memory pool instantiation to use. |
---|
188 | |
---|
189 | Obviously using the Cyg_Mempool_Joined class adds overhead, but if this |
---|
190 | is a problem, then in that case you shouldn't define multiple disjoint |
---|
191 | heaps! |
---|
192 | |
---|
193 | |
---|
194 | Run-time heap sizing |
---|
195 | -------------------- |
---|
196 | |
---|
197 | As a special case, some platforms support the addition of memory in the |
---|
198 | field, in which case it is desirable to automatically make this |
---|
199 | available to malloc. The mechanism for this is to define a macro in |
---|
200 | the HAL, specifically, defined in hal_intr.h: |
---|
201 | |
---|
202 | HAL_MEM_REAL_REGION_TOP( cyg_uint8 *regionend ) |
---|
203 | |
---|
204 | This macro takes the address of the "normal" end of the region. This |
---|
205 | corresponds with the size of the memory region in the MLT, and would |
---|
206 | be end of the "unexpanded" region. This makes sense because the memory |
---|
207 | region must be determined by the "worst case" of what memory will be |
---|
208 | installed. |
---|
209 | |
---|
210 | This macro then returns a pointer which is the *real* region end, |
---|
211 | as determined by the HAL at run-time. |
---|
212 | |
---|
213 | By having the macro in this form, it is therefore flexible enough to |
---|
214 | work with multiple memory regions. |
---|
215 | |
---|
216 | There is an example in the ARM HAL - specifically the EBSA285. |
---|
217 | |
---|
218 | |
---|
219 | How it works |
---|
220 | ------------ |
---|
221 | |
---|
222 | The MLT outputs macros providing information about user-defined sections |
---|
223 | into a header file, available via system.h with the CYGHWR_MEMORY_LAYOUT_H |
---|
224 | define. When the user-defined section has no known size, it determines |
---|
225 | the size correctly relative to the end of the region, and sets the SIZE |
---|
226 | macro accordingly. |
---|
227 | |
---|
228 | A custom build rule preprocesses src/heapgen.cpp to generate heapgeninc.tcl |
---|
229 | This contains TCL "set"s to allow access to the values of various |
---|
230 | bits of configuration data. heapgen.cpp also includes the malloc |
---|
231 | implementation header (as defined by |
---|
232 | CYGBLD_MEMALLOC_MALLOC_IMPLEMENTATION_HEADER) with __MALLOC_IMPL_WANTED |
---|
233 | defined. This tells the header that it should define the macro |
---|
234 | CYGCLS_MEMALLOC_MALLOC_IMPL to be the name of the actual class. This |
---|
235 | is then also exported with a TCL "set". |
---|
236 | |
---|
237 | src/heapgen.tcl then includes heapgeninc.tcl which gives it access to |
---|
238 | the configuration values. heapgen.tcl then searches the LDI file for |
---|
239 | any sections beginning with "heap" (with possibly leading underscores). |
---|
240 | It records each one it finds and then generates a file heaps.cxx in the |
---|
241 | build tree to instantiate a memory pool object of the required class for |
---|
242 | each heap. It also generates a list containing the addresses of each |
---|
243 | pool that was instantiated. A header file heaps.hxx is then generated |
---|
244 | that exports the number of pools, a reference to this list array and |
---|
245 | includes the implementation header. |
---|
246 | |
---|
247 | Custom build rules then copy the heaps.hxx into the include/pkgconf |
---|
248 | subdir of the install tree, and compile the heaps.cxx. |
---|
249 | |
---|
250 | To access the generated information, you must #include <pkgconf/heaps.hxx> |
---|
251 | The number of heaps is given by the CYGMEM_HEAP_COUNT macro. The type of |
---|
252 | the pools is given by CYGCLS_MEMALLOC_MALLOC_IMPL, and the array of |
---|
253 | instantiated pools is available with cygmem_memalloc_heaps. For example, |
---|
254 | here is a sample heaps.hxx: |
---|
255 | |
---|
256 | #ifndef CYGONCE_PKGCONF_HEAPS_HXX |
---|
257 | #define CYGONCE_PKGCONF_HEAPS_HXX |
---|
258 | /* <pkgconf/heaps.hxx> */ |
---|
259 | |
---|
260 | /* This is a generated file - do not edit! */ |
---|
261 | |
---|
262 | #define CYGMEM_HEAP_COUNT 1 |
---|
263 | #include <cyg/memalloc/dlmalloc.hxx> |
---|
264 | |
---|
265 | extern Cyg_Mempool_dlmalloc *cygmem_memalloc_heaps[ 2 ]; |
---|
266 | |
---|
267 | #endif |
---|
268 | /* EOF <pkgconf/heaps.hxx> */ |
---|
269 | |
---|
270 | The array has size 2 because it consists of one pool, plus a terminating |
---|
271 | NULL. |
---|
272 | |
---|
273 | In future the addition of cdl_get() available from TCL scripts contained |
---|
274 | within the CDL scripts will remove the need for a lot of this magic. |
---|
275 | |
---|
276 | |
---|
277 | dlmalloc |
---|
278 | -------- |
---|
279 | |
---|
280 | A port of dlmalloc is included. Far too many changes were required to make |
---|
281 | it fit within the scheme above, so therefore there was no point |
---|
282 | trying to preserve the layout to make it easier to merge in new versions. |
---|
283 | However dlmalloc rarely changes any more - it is very stable. |
---|
284 | |
---|
285 | The version of dlmalloc used was a mixture of 2.6.6 and the dlmalloc from |
---|
286 | newlib (based on 2.6.4). In the event, most of the patches merged were |
---|
287 | of no consequence to the final version. |
---|
288 | |
---|
289 | For reference, the various versions examined are included in the |
---|
290 | doc/dlmalloc subdirectory: dlmalloc-2.6.4.c, dlmalloc-2.6.6.c, |
---|
291 | dlmalloc-newlib.c and dlmalloc-merged.c (which is the result of merging |
---|
292 | the changes between 2.6.4 and the newlib version into 2.6.6). Note it |
---|
293 | was not tested at that point. |
---|
294 | |
---|
295 | |
---|
296 | Remaining issues |
---|
297 | ---------------- |
---|
298 | |
---|
299 | You should be allowed to have different allocators for different memory |
---|
300 | regions. The biggest hurdle here is host tools support to express this. |
---|
301 | |
---|
302 | Currently the "joined" allocator wrapper simply treats each memory pool |
---|
303 | as an equal. It doesn't understand that some memory pools may be faster |
---|
304 | than others, and cannot make decisions about which pools (and therefore |
---|
305 | regions and therefore possibly speeds of memory) to use on the basis |
---|
306 | of allocation size. This should be (configurably) possible. |
---|
307 | |
---|
308 | |
---|
309 | History |
---|
310 | ------- |
---|
311 | |
---|
312 | |
---|
313 | A long, long time ago, in a galaxy far far away.... the situation used to |
---|
314 | be that the kernel package contained the fixed block and simple variable |
---|
315 | block memory allocators, and those were the only memory allocator |
---|
316 | implementations. This was all a bit incongruous as it meant that any code |
---|
317 | wanting dynamic memory allocation had to include the whole kernel, even |
---|
318 | though the dependencies could be encapsulated. This was particularly silly |
---|
319 | because the implementation of malloc() (etc.) in the C library didn't use |
---|
320 | any of the features that *did* depend on the kernel, such as timed waits |
---|
321 | while allocating memory, etc. |
---|
322 | |
---|
323 | The C library malloc was pretty naff then too. It used a static buffer |
---|
324 | as the basis of the memory pool, with a hard-coded size, set in the |
---|
325 | configuration. You couldn't make it fit into all of memory. |
---|
326 | |
---|
327 | Jifl |
---|
328 | 2000-07-03 |
---|
329 | |
---|
330 | //####ECOSGPLCOPYRIGHTBEGIN#### |
---|
331 | // ------------------------------------------- |
---|
332 | // This file is part of eCos, the Embedded Configurable Operating System. |
---|
333 | // Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc. |
---|
334 | // |
---|
335 | // eCos is free software; you can redistribute it and/or modify it under |
---|
336 | // the terms of the GNU General Public License as published by the Free |
---|
337 | // Software Foundation; either version 2 or (at your option) any later version. |
---|
338 | // |
---|
339 | // eCos is distributed in the hope that it will be useful, but WITHOUT ANY |
---|
340 | // WARRANTY; without even the implied warranty of MERCHANTABILITY or |
---|
341 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
---|
342 | // for more details. |
---|
343 | // |
---|
344 | // You should have received a copy of the GNU General Public License along |
---|
345 | // with eCos; if not, write to the Free Software Foundation, Inc., |
---|
346 | // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. |
---|
347 | // |
---|
348 | // As a special exception, if other files instantiate templates or use macros |
---|
349 | // or inline functions from this file, or you compile this file and link it |
---|
350 | // with other works to produce a work based on this file, this file does not |
---|
351 | // by itself cause the resulting work to be covered by the GNU General Public |
---|
352 | // License. However the source code for this file must still be made available |
---|
353 | // in accordance with section (3) of the GNU General Public License. |
---|
354 | // |
---|
355 | // This exception does not invalidate any other reasons why a work based on |
---|
356 | // this file might be covered by the GNU General Public License. |
---|
357 | // |
---|
358 | // Alternative licenses for eCos may be arranged by contacting Red Hat, Inc. |
---|
359 | // at http://sources.redhat.com/ecos/ecos-license/ |
---|
360 | // ------------------------------------------- |
---|
361 | //####ECOSGPLCOPYRIGHTEND#### |
---|