source: SVN/cambria/redboot/packages/services/memalloc/common/current/doc/notes.txt @ 1

Last change on this file since 1 was 1, checked in by Tim Harvey, 2 years ago

restored latest version of files from server backup

Signed-off-by: Tim Harvey <tharvey@…>

File size: 14.6 KB
Line 
1                Memory allocation package - Implementation Notes
2                ------------------------------------------------
3
4
5
6Made with loving care by Jonathan Larmour (jlarmour@redhat.com)
7Initial version: 2000-07-03
8Last updated:    2000-07-03
9
10
11
12Meta
13----
14
15This document describes some interesting bits and pieces about the memory
16allocation package - CYGPKG_MEMALLOC. It is intended as a guide to
17developers, not users. This isn't (yet) in formal documentation format,
18and probably should be.
19
20
21Philosophy
22----------
23
24The object of this package is to provide everything required for dynamic
25memory allocation, some sample implementations, the ability to plug in
26more implementations, and a standard malloc() style interface to those
27allocators.
28
29The classic Unix-style view of a heap is using brk()/sbrk() to extend the
30data segment of the application. However this is inappropriate for an
31embedded 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
39Therefore instead, we base the heap on the idea of fixed size memory pools.
40The size of each pool is known in advance.
41
42
43Overview
44--------
45
46Most of the infrastructure this package provides is geared towards
47supporting the ISO standard malloc() family of functions. A "standard"
48eCos allocator should be able to plug in to this infrastructure and
49transparently work. The interface is based on simple use of C++ - nothing
50too advanced.
51
52The allocator to use is dictated by the
53CYGBLD_MEMALLOC_MALLOC_IMPLEMENTATION_HEADER option. Choosing the
54allocator can be done by ensuring the CDL for the new allocator
55has a "requires" that sets the location of the header to use when that
56allocator is enabled. New allocators should default to disabled, so they
57don't have to worry about which one is the default, thus causing CDL
58conflicts. When enabled the new allocator should also claim to implement
59CYGINT_MEMALLOC_MALLOC_ALLOCATORS.
60
61The implementation header file that is set must have a special property
62though - it may be included with __MALLOC_IMPL_WANTED defined. If this
63is the case, then this means the infrastructure wants to find out the
64name of the class that is implemented in this header file. This is done
65by setting CYGCLS_MEMALLOC_MALLOC_IMPL. If __MALLOC_IMPL_WANTED is defined
66then no non-preprocessor output should be generated, as this will be included
67in a TCL script in due course. An existing example from this package would
68be:
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
75class Cyg_Mempool_dlmalloc
76{
77[etc.]
78
79To meet the expectations of malloc, the class should have the following
80public interfaces (for details it is best to look at some of the
81examples 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
135Cyg_Mempolt2 template
136---------------------
137
138If using the eCos kernel with multiple threads accessing the allocators,
139then obviously you need to be sure that the allocator is accessed in a
140thread-safe way. The malloc() wrappers do not make any assumptions
141about this. One helpful approach currently used by all the allocators
142in this package is to (optionally) use a template (Cyg_Mempolt2) that
143provides extra functions like a blocking alloc() that waits for memory
144to be freed before returning, and a timed variant. Other calls are
145generally passed straight through, but with the kernel scheduler locked
146to prevent pre-emption.
147
148You don't have to use this facility to fit into the infrastructure though,
149and thread safety is not a prerequisite for the rest of the infrastructure.
150And indeed certain allocators will be able to do scheduling at a finer
151granularity than just locking the scheduler every time.
152
153The odd name is because of an original desire to keep 8.3 filenames, which
154was reflected in the class name to make it correspond to the filename.
155There used to be an alternative Cyg_Mempoolt template, but that has fallen
156into disuse and is no longer supported.
157
158
159Automatic heap sizing
160---------------------
161
162This package contains infrastructure to allow the automatic definition
163of memory pools that occupy all available memory. In order to do this
164you must use the eCos Memory Layout Tool to define a user-defined section.
165These sections *must* have the prefix "heap", for example "heap1", "heap2",
166"heapdram" etc. otherwise they will be ignored.
167
168The user-defined section may be of fixed size, or of unknown size. If it
169has unknown size then its size is dictated by either the location of
170the next following section with an absolute address, or if there are
171no following sections, the end of the memory region. The latter should
172be the norm.
173
174If no user-defined sections starting with "heap" are found, a fallback
175static array (i.e. allocated in the BSS) will be used, whose size can
176be set in the configuration.
177
178It is also possible to define multiple heap sections. This is
179necessary when you have multiple disjoint memory regions, and no MMU
180to join it up into one contiguous memory space. In which case
181a special wrapper allocator object is automatically used. This object
182is an instantiation of the Cyg_Mempool_Joined template class,
183defined in memjoin.hxx. It is instantiated with a list of every heap
184section, which it then records. It's sole purpose is to act as a go
185between to the underlying implementation, and does the right thing by
186using pointer addresses to determine which memory pool the pointer
187allocator, and therefore which memory pool instantiation to use.
188
189Obviously using the Cyg_Mempool_Joined class adds overhead, but if this
190is a problem, then in that case you shouldn't define multiple disjoint
191heaps!
192
193
194Run-time heap sizing
195--------------------
196
197As a special case, some platforms support the addition of memory in the
198field, in which case it is desirable to automatically make this
199available to malloc. The mechanism for this is to define a macro in
200the HAL, specifically, defined in hal_intr.h:
201
202HAL_MEM_REAL_REGION_TOP( cyg_uint8 *regionend )
203
204This macro takes the address of the "normal" end of the region. This
205corresponds with the size of the memory region in the MLT, and would
206be end of the "unexpanded" region. This makes sense because the memory
207region must be determined by the "worst case" of what memory will be
208installed.
209
210This macro then returns a pointer which is the *real* region end,
211as determined by the HAL at run-time.
212
213By having the macro in this form, it is therefore flexible enough to
214work with multiple memory regions.
215
216There is an example in the ARM HAL - specifically the EBSA285.
217
218
219How it works
220------------
221
222The MLT outputs macros providing information about user-defined sections
223into a header file, available via system.h with the CYGHWR_MEMORY_LAYOUT_H
224define. When the user-defined section has no known size, it determines
225the size correctly relative to the end of the region, and sets the SIZE
226macro accordingly.
227
228A custom build rule preprocesses src/heapgen.cpp to generate heapgeninc.tcl
229This contains TCL "set"s to allow access to the values of various
230bits of configuration data. heapgen.cpp also includes the malloc
231implementation header (as defined by
232CYGBLD_MEMALLOC_MALLOC_IMPLEMENTATION_HEADER) with __MALLOC_IMPL_WANTED
233defined. This tells the header that it should define the macro
234CYGCLS_MEMALLOC_MALLOC_IMPL to be the name of the actual class. This
235is then also exported with a TCL "set".
236
237src/heapgen.tcl then includes heapgeninc.tcl which gives it access to
238the configuration values. heapgen.tcl then searches the LDI file for
239any sections beginning with "heap" (with possibly leading underscores).
240It records each one it finds and then generates a file heaps.cxx in the
241build tree to instantiate a memory pool object of the required class for
242each heap. It also generates a list containing the addresses of each
243pool that was instantiated. A header file heaps.hxx is then generated
244that exports the number of pools, a reference to this list array and
245includes the implementation header.
246
247Custom build rules then copy the heaps.hxx into the include/pkgconf
248subdir of the install tree, and compile the heaps.cxx.
249
250To access the generated information, you must #include <pkgconf/heaps.hxx>
251The number of heaps is given by the CYGMEM_HEAP_COUNT macro. The type of
252the pools is given by CYGCLS_MEMALLOC_MALLOC_IMPL, and the array of
253instantiated pools is available with cygmem_memalloc_heaps. For example,
254here 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 
265extern Cyg_Mempool_dlmalloc *cygmem_memalloc_heaps[ 2 ];
266 
267#endif
268/* EOF <pkgconf/heaps.hxx> */
269
270The array has size 2 because it consists of one pool, plus a terminating
271NULL.
272
273In future the addition of cdl_get() available from TCL scripts contained
274within the CDL scripts will remove the need for a lot of this magic.
275
276
277dlmalloc
278--------
279
280A port of dlmalloc is included. Far too many changes were required to make
281it fit within the scheme above, so therefore there was no point
282trying to preserve the layout to make it easier to merge in new versions.
283However dlmalloc rarely changes any more - it is very stable.
284
285The version of dlmalloc used was a mixture of 2.6.6 and the dlmalloc from
286newlib (based on 2.6.4). In the event, most of the patches merged were
287of no consequence to the final version.
288
289For reference, the various versions examined are included in the
290doc/dlmalloc subdirectory: dlmalloc-2.6.4.c, dlmalloc-2.6.6.c,
291dlmalloc-newlib.c and dlmalloc-merged.c (which is the result of merging
292the changes between 2.6.4 and the newlib version into 2.6.6). Note it
293was not tested at that point.           
294
295
296Remaining issues
297----------------
298
299You should be allowed to have different allocators for different memory
300regions. The biggest hurdle here is host tools support to express this.
301
302Currently the "joined" allocator wrapper simply treats each memory pool
303as an equal. It doesn't understand that some memory pools may be faster
304than others, and cannot make decisions about which pools (and therefore
305regions and therefore possibly speeds of memory) to use on the basis
306of allocation size. This should be (configurably) possible.
307
308
309History
310-------
311
312
313A long, long time ago, in a galaxy far far away.... the situation used to
314be that the kernel package contained the fixed block and simple variable
315block memory allocators, and those were the only memory allocator
316implementations. This was all a bit incongruous as it meant that any code
317wanting dynamic memory allocation had to include the whole kernel, even
318though the dependencies could be encapsulated. This was particularly silly
319because the implementation of malloc() (etc.) in the C library didn't use
320any of the features that *did* depend on the kernel, such as timed waits
321while allocating memory, etc.
322
323The C library malloc was pretty naff then too. It used a static buffer
324as the basis of the memory pool, with a hard-coded size, set in the
325configuration. You couldn't make it fit into all of memory.
326
327Jifl
3282000-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####
Note: See TracBrowser for help on using the repository browser.