8000 WIP: Initial overlay of upstream version of umm_malloc over · esp8266/Arduino@88a32c8 · GitHub
[go: up one dir, main page]
Skip to content

Commit 88a32c8

Browse files
mhightower83mhightower83
committed
WIP: Initial overlay of upstream version of umm_malloc over
our current version w/o any edits. Using files from: https://github.com/rhempel/umm_malloc/tree/master/src https://github.com/rhempel/c-helper-macros/tree/develop The following file remanents from our old version were removed: umm_malloc.cpp, umm_performance.h, umm_performance.cpp, and umm_stats.h This is intended to be a "compare to" for changes made to upstream version.
1 parent 55539ae commit 88a32c8

15 files changed

+1578
-2320
lines changed

‎cores/esp8266/umm_malloc/README.md

Lines changed: 86 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -10,18 +10,18 @@ might get expensive.
1010

1111
## Acknowledgements
1212

13-
Joerg Wunsch and the avr-libc provided the first malloc() implementation
13+
Joerg Wunsch and the avr-libc provided the first `malloc()` implementation
1414
that I examined in detail.
1515

16-
http://www.nongnu.org/avr-libc
16+
`http://www.nongnu.org/avr-libc`
1717

1818
Doug Lea's paper on malloc() was another excellent reference and provides
1919
a lot of detail on advanced memory management techniques such as binning.
2020

21-
http://g.oswego.edu/dl/html/malloc.html
21+
`http://g.oswego.edu/dl/html/malloc.html`
2222

2323
Bill Dittman provided excellent suggestions, including macros to support
24-
using these functions in critical sections, and for optimizing realloc()
24+
using these functions in critical sections, and for optimizing `realloc()`
2525
further by checking to see if the previous block was free and could be
2626
used for the new block size. This can help to reduce heap fragmentation
2727
significantly.
@@ -30,11 +30,73 @@ Yaniv Ankin suggested that a way to dump the current heap condition
3030
might be useful. I combined this with an idea from plarroy to also
3131
allow checking a free pointer to make sure it's valid.
3232

33+
Dimitry Frank contributed many helpful additions to make things more
34+
robust including a user specified config file and a method of testing
35+
the integrity of the data structures.
36+
37+
## Usage
38+
39+
Copy the `umm_malloc_cfg_example.h` file to `umm_malloc_cfg.h` and
40+
make the changes required to support your application.
41+
42+
The following `#define`s must be set to something useful for the
43+
library to work at all
44+
45+
- `UMM_MALLOC_CFG_HEAP_ADDR` must be set to the symbol representing
46+
the starting address of the heap. The heap must be
47+
aligned on the natural boundary size of the processor.
48+
- `UMM_MALLOC_CFG_HEAP_SIZE` must be set to the size of the heap.
49+
The heap size must be a multiple of the natural boundary size of
50+
the processor.
51+
52+
The fit algorithm is defined as either:
53+
54+
- `UMM_BEST_FIT` which scans the entire free list and looks
55+
for either an exact fit or the smallest block that will
56+
satisfy the request. This is the default fit method.
57+
- `UMM_FIRST_FIT` which scans the entire free list and looks
58+
for the first block that satisfies the request.
59+
60+
The following `#define`s are disabled by default and should
61+
remain disabled for production use. They are helpful when
62+
testing allocation errors (which are normally due to bugs in
63+
the application code) or for running the test suite when
64+
making changes to the code.
65+
66+
You can define them in your compiler command line or uncomment
67+
the corresponding entries is `umm_malloc_cfg.h`:
68+
69+
- `UMM_INFO` is used to include code that allows dumping
70+
the entire heap structure (helpful when there's a problem).
71+
72+
- `UMM_INTEGRITY_CHECK` is used to include code that
73+
performs an integrity check on the heap structure. It's
74+
up to you to call the `umm_integrity_check()` function.
75+
76+
- `UMM_POISON_CHECK` is used to include code that
77+
adds some bytes around the memory being allocated that
78+
are filled with known data. If the data is not intact
79+
when the block is checked, then somone has written outside
80+
of the memory block they have been allocated. It is up
81+
to you to call the `umm_poison_check()` function.
82+
83+
## API
84+
85+
The following functions are available for your application:
86+
87+
- `void *umm_malloc( size_t size );`
88+
- `void *umm_calloc( size_t num, size_t size );`
89+
- `void *umm_realloc( void *ptr, size_t size );`
90+
- `void umm_free( void *ptr );`
91+
92+
They have exactly the same semantics as the corresponding standard library
93+
functions.
94+
3395
## Background
3496

3597
The memory manager assumes the following things:
3698

37-
1. The standard POSIX compliant malloc/realloc/free semantics are used
99+
1. The standard POSIX compliant malloc/calloc/realloc/free semantics are used
38100
1. All memory used by the manager is allocated at link time, it is aligned
39101
on a 32 bit boundary, it is contiguous, and its extent (start and end
40102
address) is filled in by the linker.
@@ -45,17 +107,17 @@ The fastest linked list implementations use doubly linked lists so that
45107
its possible to insert and delete blocks in constant time. This memory
46108
manager keeps track of both free and used blocks in a doubly linked list.
47109

48-
Most memory managers use some kind of list structure made up of pointers
110+
Most memory managers use a list structure made up of pointers
49111
to keep track of used - and sometimes free - blocks of memory. In an
50112
embedded system, this can get pretty expensive as each pointer can use
51113
up to 32 bits.
52114

53-
In most embedded systems there is no need for managing large blocks
54-
of memory dynamically, so a full 32 bit pointer based data structure
115+
In most embedded systems there is no need for managing a large quantity
116+
of memory block dynamically, so a full 32 bit pointer based data structure
55117
for the free and used block lists is wasteful. A block of memory on
56118
the free list would use 16 bytes just for the pointers!
57119

58-
This memory management library sees the malloc heap as an array of blocks,
120+
This memory management library sees the heap as an array of blocks,
59121
and uses block numbers to keep track of locations. The block numbers are
60122
15 bits - which allows for up to 32767 blocks of memory. The high order
61123
bit marks a block as being either free or in use, which will be explained
@@ -75,7 +137,7 @@ can always add more data bytes to the body of the memory block
75137
at the expense of free block size overhead.
76138

77139
There are a lot of little features and optimizations in this memory
78-
management system that makes it especially suited to small embedded, but
140+
management system that makes it especially suited to small systems, and
79141
the best way to appreciate them is to review the data structures and
80142
algorithms used, so let's get started.
81143

@@ -124,10 +186,9 @@ Where:
124186
- n is the index of the next block in the heap
125187
- p is the index of the previous block in the heap
126188

127-
Note that the free list information is gone, because it's now being used to
128-
store actual data for the application. It would have been nice to store
129-
the next and previous free list indexes as well, but that would be a waste
130-
of space. If we had even 500 items in use, that would be 2,000 bytes for
189+
Note that the free list information is gone because it's now
190+
being used to store actual data for the application. If we had
191+
even 500 items in use, that would be 2,000 bytes for
131192
free list information. We simply can't afford to waste that much.
132193

133194
The address of the `...` area is what is returned to the application
@@ -143,7 +204,7 @@ described.
143204
`...` between memory blocks indicates zero or more additional blocks are
144205
allocated for use by the upper block.
145206

146-
And while we're talking about "upper" and "lower" blocks, we should make
207+
While we're talking about "upper" and "lower" blocks, we should make
147208
a comment about adresses. In the diagrams, a block higher up in the
148209
picture is at a lower address. And the blocks grow downwards their
149210
block index increases as does their physical address.
@@ -166,24 +227,27 @@ we're at the end of the list!
166227

167228
At this point, the malloc has a special test that checks if the current
168229
block index is 0, which it is. This special case initializes the free
169-
list to point at block index 1.
230+
list to point at block index 1 and then points block 1 to the
231+
last block (lf) on the heap.
170232

171233
```
172234
BEFORE AFTER
173235
174236
+----+----+----+----+ +----+----+----+----+
175-
0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
237+
0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
176238
+----+----+----+----+ +----+----+----+----+
177239
+----+----+----+----+
178-
1 | 0 | 0 | 0 | 0 |
240+
1 |*lf | 0 | 0 | 0 |
241+
+----+----+----+----+
242+
...
243+
+----+----+----+----+
244+
lf | 0 | 1 | 0 | 0 |
179245
+----+----+----+----+
180246
```
181247

182248
The heap is now ready to complete the first malloc operation.
183249

184-
185-
### Operation of malloc when we have reached the end of the free list and
186-
there is no block large enough to accommodate the request.
250+
### Operation of malloc when we have reached the end of the free list and there is no block large enough to accommodate the request.
187251

188252
This happens at the very first malloc operation, or any time the free
189253
list is traversed and no free block large enough for the request is
@@ -306,8 +370,7 @@ else
306370
```
307371

308372
Step 1 of the free operation checks if the next block is free, and if it
309-
is then insert this block into the free list and assimilate the next block
310-
with this one.
373+
is assimilate the next block with this one.
311374

312375
Note that c is the block we are freeing up, cf is the free block that
313376
follows it.

‎cores/esp8266/umm_malloc/dbglog/LICENSE

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
MIT License
2+
3+
Copyright (c) 2016 Ralph Hempel
4+
5+
Permission is hereby granted, free of charge, to any person obtaining a copy
6+
of this software and associated documentation files (the "Software"), to deal
7+
in the Software without restriction, including without limitation the rights
8+
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+
copies of the Software, and to permit persons to whom the Software is
10+
furnished to do so, subject to the following conditions:
11+
12+
The above copyright notice and this permission notice shall be included in all
13+
copies or substantial portions of the Software.
14+
15+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21+
SOFTWARE.

‎cores/esp8266/umm_malloc/dbglog/README.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
Downloaded from: https://github.com/rhempel/c-helper-macros/tree/develop

‎cores/esp8266/umm_malloc/dbglog/dbglog.h

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
/* ----------------------------------------------------------------------------
2+
* dbglog.h - A set of macros that cleans up code that needs to produce debug
3+
* or log information.
4+
*
5+
* Many embedded systems still put a premium on code space and therefore need
6+
* a way to conditionally compile in debug code. Yes, it can lead to code that
7+
* runs differently depending on whether the debug code is cmpiled in or not
8+
* but you need to be able to evaluate the tradeoff.
9+
*
10+
* See copyright notice in LICENSE.TXT
11+
* ----------------------------------------------------------------------------
12+
* NOTE WELL that this file may be included multiple times - this allows you
13+
* to set the trace level #define DBGLOG_LEVEL x
14+
*
15+
* To update which of the DBGLOG macros are compiled in, you must redefine the
16+
* DBGLOG_LEVEL macro and the inlcude the dbglog.h file again, like this:
17+
*
18+
* #undef DBGLOG_LEVEL
19+
* #define DBGLOG_LEVEL 6
20+
* #include "dbglog/dbglog.txt"
21+
*
22+
* To handle multiple inclusion, we need to first undefine any macros we define
23+
* so that the compiler does not warn us that we are changing a macro.
24+
* ----------------------------------------------------------------------------
25+
* The DBGLOG_LEVEL and DBGLOG_FUNCTION should be defined BEFORE this
26+
* file is included or else the following defaults are used:
27+
*
28+
* #define DBGLOG_LEVEL 0
29+
* #define DBGLOG_FUNCTION printf
30+
* ----------------------------------------------------------------------------
31+
* There are macros to handle the following decreasing levels of detail:
32+
*
33+
* 6 = TRACE
34+
* 5 = DEBUG
35+
* 4 = CRITICAL
36+
* 3 = ERROR
37+
* 2 = WARNING
38+
* 1 = INFO
39+
* 0 = FORCE - The DBGLOG_FUNCTION is always compiled in and is called only when
40+
* the first parameter to the macro is non-0
41+
* ----------------------------------------------------------------------------
42+
*/
43+
44+
#undef DBGLOG_TRACE
45+
#undef DBGLOG_DEBUG
46+
#undef DBGLOG_CRITICAL
47+
#undef DBGLOG_ERROR
48+
#undef DBGLOG_WARNING
49+
#undef DBGLOG_INFO
50+
#undef DBGLOG_FORCE
51+
52+
#ifndef DBGLOG_LEVEL
53+
# define DBGLOG_LEVEL 0
54+
#endif
55+
56+
#ifndef DBGLOG_FUNCTION
57+
# define DBGLOG_FUNCTION printf
58+
#endif
59+
60+
/* ------------------------------------------------------------------------- */
61+
62+
#if DBGLOG_LEVEL >= 6
63+
# define DBGLOG_TRACE(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
64+
#else
65+
# define DBGLOG_TRACE(format, ...)
66+
#endif
67+
68+
#if DBGLOG_LEVEL >= 5
69+
# define DBGLOG_DEBUG(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
70+
#else
71+
# define DBGLOG_DEBUG(format, ...)
72+
#endif
73+
74+
#if DBGLOG_LEVEL >= 4
75+
# define DBGLOG_CRITICAL(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
76+
#else
77+
# define DBGLOG_CRITICAL(format, ...)
78+
#endif
79+
80+
#if DBGLOG_LEVEL >= 3
81+
# define DBGLOG_ERROR(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
82+
#else
83+
# define DBGLOG_ERROR(format, ...)
84+
#endif
85+
86+
#if DBGLOG_LEVEL >= 2
87+
# define DBGLOG_WARNING(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
88+
#else
89+
# define DBGLOG_WARNING(format, ...)
90+
#endif
91+
92+
#if DBGLOG_LEVEL >= 1
93+
# define DBGLOG_INFO(format, ...) DBGLOG_FUNCTION(format, ## __VA_ARGS__)
94+
#else
95+
# define DBGLOG_INFO(format, ...)
96+
#endif
97+
98+
#define DBGLOG_FORCE(force, format, ...) {if(force) {DBGLOG_FUNCTION(format, ## __VA_ARGS__);}}

0 commit comments

Comments
 (0)
0