arduino-esp8266 WiFi探针代码源码

# umm_malloc - Memory Manager For Small(ish) Microprocessors This is a memory management library specifically designed to work with the ARM7 embedded processor, but it should work on many other 32 bit processors, as well as 16 and 8 bit devices. You can even use it on a bigger project where a single process might want to manage a large number of smaller objects, and using the system heap might get expensive. ## Acknowledgements Joerg Wunsch and the avr-libc provided the first malloc() implementation that I examined in detail. http://www.nongnu.org/avr-libc Doug Lea's paper on malloc() was another excellent reference and provides a lot of detail on advanced memory management techniques such as binning. http://g.oswego.edu/dl/html/malloc.html Bill Dittman provided excellent suggestions, including macros to support using these functions in critical sections, and for optimizing realloc() further by checking to see if the previous block was free and could be used for the new block size. This can help to reduce heap fragmentation significantly. Yaniv Ankin suggested that a way to dump the current heap condition might be useful. I combined this with an idea from plarroy to also allow checking a free pointer to make sure it's valid. ## Background The memory manager assumes the following things: 1. The standard POSIX compliant malloc/realloc/free semantics are used 1. All memory used by the manager is allocated at link time, it is aligned on a 32 bit boundary, it is contiguous, and its extent (start and end address) is filled in by the linker. 1. All memory used by the manager is initialized to 0 as part of the runtime startup routine. No other initialization is required. The fastest linked list implementations use doubly linked lists so that its possible to insert and delete blocks in constant time. This memory manager keeps track of both free and used blocks in a doubly linked list. Most memory managers use some kind of list structure made up of pointers to keep track of used - and sometimes free - blocks of memory. In an embedded system, this can get pretty expensive as each pointer can use up to 32 bits. In most embedded systems there is no need for managing large blocks of memory dynamically, so a full 32 bit pointer based data structure for the free and used block lists is wasteful. A block of memory on the free list would use 16 bytes just for the pointers! This memory management library sees the malloc heap as an array of blocks, and uses block numbers to keep track of locations. The block numbers are 15 bits - which allows for up to 32767 blocks of memory. The high order bit marks a block as being either free or in use, which will be explained later. The result is that a block of memory on the free list uses just 8 bytes instead of 16. In fact, we go even one step futher when we realize that the free block index values are available to store data when the block is allocated. The overhead of an allocated block is therefore just 4 bytes. Each memory block holds 8 bytes, and there are up to 32767 blocks available, for about 256K of heap space. If that's not enough, you can always add more data bytes to the body of the memory block at the expense of free block size overhead. There are a lot of little features and optimizations in this memory management system that makes it especially suited to small embedded, but the best way to appreciate them is to review the data structures and algorithms used, so let's get started. ## Detailed Description We have a general notation for a block that we'll use to describe the different scenarios that our memory allocation algorithm must deal with: ``` +----+----+----+----+ c |* n | p | nf | pf | +----+----+----+----+ ``` Where: - c is the index of this block - * is the indicator for a free block - n is the index of the next block in the heap - p is the index of the previous block in the heap - nf is the index of the next block in the free list - pf is the index of the previous block in the free list The fact that we have forward and backward links in the block descriptors means that malloc() and free() operations can be very fast. It's easy to either allocate the whole free item to a new block or to allocate part of the free item and leave the rest on the free list without traversing the list from front to back first. The entire block of memory used by the heap is assumed to be initialized to 0. The very first block in the heap is special - it't the head of the free block list. It is never assimilated with a free block (more on this later). Once a block has been allocated to the application, it looks like this: ``` +----+----+----+----+ c | n | p | ... | +----+----+----+----+ ``` Where: - c is the index of this block - n is the index of the next block in the heap - p is the index of the previous block in the heap Note that the free list information is gone, because it's now being used to store actual data for the application. It would have been nice to store the next and previous free list indexes as well, but that would be a waste of space. If we had even 500 items in use, that would be 2,000 bytes for free list information. We simply can't afford to waste that much. The address of the `...` area is what is returned to the application for data storage. The following sections describe the scenarios encountered during the operation of the library. There are two additional notation conventions: `??` inside a pointer block means that the data is irrelevant. We don't care about it because we don't read or modify it in the scenario being described. `...` between memory blocks indicates zero or more additional blocks are allocated for use by the upper block. And while we're talking about "upper" and "lower" blocks, we should make a comment about adresses. In the diagrams, a block higher up in the picture is at a lower address. And the blocks grow downwards their block index increases as does their physical address. Finally, there's one very important characteristic of the individual blocks that make up the heap - there can never be two consecutive free memory blocks, but there can be consecutive used memory blocks. The reason is that we always want to have a short free list of the largest possible block sizes. By always assimilating a newly freed block with adjacent free blocks, we maximize the size of each free memory area. ### Operation of malloc right after system startup As part of the system startup code, all of the heap has been cleared. During the very first malloc operation, we start traversing the free list starting at index 0. The index of the next free block is 0, which means we're at the end of the list! At this point, the malloc has a special test that checks if the current block index is 0, which it is. This special case initializes the free list to point at block index 1. ``` BEFORE AFTER +----+----+----+----+ +----+----+----+----+ 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | +----+----+----+----+ +----+----+----+----+ +----+----+----+----+ 1 | 0 | 0 | 0 | 0 | +----+----+----+----+ ``` The heap is now ready to complete the first malloc operation. ### Operation of malloc when we have reached the end of the free list and there is no block large enough to accommodate the request. This happens at the very first malloc operation, or any time the free list is traversed and no free block large enough for the request is found. The current block pointer will be at the end of the free list, and we know we're at the end of the list because the nf index is 0, like this: ``` BEFORE AFTER +----+----+----+----+ +----+----+----+----+ pf |*?? | ?? | cf | ?? | pf |*?? | ?? | lf | ?? | +----+----+---