2 Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
9 * Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11 * Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions and the following disclaimer in
13 the documentation and/or other materials provided with the
15 * Neither the name of Intel Corporation nor the names of its
16 contributors may be used to endorse or promote products derived
17 from this software without specific prior written permission.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 The librte_malloc library provides an API to allocate any-sized memory.
38 The objective of this library is to provide malloc-like functions to allow allocation from hugepage memory
39 and to facilitate application porting.
40 The *DPDK API Reference* manual describes the available functions.
42 Typically, these kinds of allocations should not be done in data plane processing
43 because they are slower than pool-based allocation and make use of locks within the allocation
45 However, they can be used in configuration code.
47 Refer to the rte_malloc() function description in the *DPDK API Reference* manual for more information.
52 When CONFIG_RTE_MALLOC_DEBUG is enabled, the allocated memory contains overwrite protection fields
53 to help identify buffer overflows.
55 Alignment and NUMA Constraints
56 ------------------------------
58 The rte_malloc() takes an align argument that can be used to request a memory area
59 that is aligned on a multiple of this value (which must be a power of two).
61 On systems with NUMA support, a call to the rte_malloc() function will return memory
62 that has been allocated on the NUMA socket of the core which made the call.
63 A set of APIs is also provided, to allow memory to be explicitly allocated on a NUMA socket directly,
64 or by allocated on the NUMA socket where another core is located,
65 in the case where the memory is to be used by a logical core other than on the one doing the memory allocation.
70 This library is needed by an application that requires malloc-like functions at initialization time,
71 and does not require the physical address information for the individual memory blocks.
73 For allocating/freeing data at runtime, in the fast-path of an application,
74 the memory pool library should be used instead.
76 If a block of memory with a known physical address is needed,
77 e.g. for use by a hardware device, a memory zone should be used.
79 Internal Implementation
80 -----------------------
85 There are two data structure types used internally in the malloc library:
87 * struct malloc_heap - used to track free space on a per-socket basis
89 * struct malloc_elem - the basic element of allocation and free-space tracking inside the library.
91 Structure: malloc_heap
92 ^^^^^^^^^^^^^^^^^^^^^^
94 The malloc_heap structure is used in the library to manage free space on a per-socket basis.
95 Internally in the library, there is one heap structure per NUMA node,
96 which allows us to allocate memory to a thread based on the NUMA node on which this thread runs.
97 While this does not guarantee that the memory will be used on that NUMA node,
98 it is no worse than a scheme where the memory is always allocated on a fixed or random node.
100 The key fields of the heap structure and their function are described below (see also diagram above):
102 * mz_count - field to count the number of memory zones which have been allocated for heap memory on this NUMA node.
103 The sole use of this value is, in combination with the numa_socket value,
104 to generate a suitable, unique name for each memory zone.
106 * lock - the lock field is needed to synchronize access to the heap.
107 Given that the free space in the heap is tracked using a linked list,
108 we need a lock to prevent two threads manipulating the list at the same time.
110 * free_head - this points to the first element in the list of free nodes for this malloc heap.
114 The malloc_heap structure does not keep track of either the memzones allocated,
115 since there is little point as they cannot be freed.
116 Neither does it track the in-use blocks of memory,
117 since these are never touched except when they are to be freed again -
118 at which point the pointer to the block is an input to the free() function.
120 .. _figure_malloc_heap:
122 .. figure:: img/malloc_heap.*
124 Example of a malloc heap and malloc elements within the malloc library
127 Structure: malloc_elem
128 ^^^^^^^^^^^^^^^^^^^^^^
129 The malloc_elem structure is used as a generic header structure for various blocks of memory in a memzone.
130 It is used in three different ways - all shown in the diagram above:
132 #. As a header on a block of free or allocated memory - normal case
134 #. As a padding header inside a block of memory
136 #. As an end-of-memzone marker
138 The most important fields in the structure and how they are used are described below.
142 If the usage of a particular field in one of the above three usages is not described,
143 the field can be assumed to have an undefined value in that situation, for example,
144 for padding headers only the "state" and "pad" fields have valid values.
146 * heap - this pointer is a reference back to the heap structure from which this block was allocated.
147 It is used for normal memory blocks when they are being freed,
148 to add the newly-freed block to the heap's free-list.
150 * prev - this pointer points to the header element/block in the memzone immediately behind the current one.
151 When freeing a block, this pointer is used to reference the previous block to check if that block is also free.
152 If so, then the two free blocks are merged to form a single larger block.
154 * next_free - this pointer is used to chain the free-list of unallocated memory blocks together.
155 Again, it is only used in normal memory blocks - on malloc() to find a suitable free block to allocate,
156 and on free() to add the newly freed element to the free-list.
158 * state - This field can have one of three values: "Free", "Busy" or "Pad".
159 The former two, are to indicate the allocation state of a normal memory block,
160 and the latter is to indicate that the element structure is a dummy structure at the end of the start-of-block padding
161 (i.e. where the start of the data within a block is not at the start of the block itself, due to alignment constraints).
162 In this case, the pad header is used to locate the actual malloc element header for the block.
163 For the end-of-memzone structure, this is always a "busy" value, which ensures that no element,
164 on being freed, searches beyond the end of the memzone for other blocks to merge with into a larger free area.
166 * pad - this holds the length of the padding present at the start of the block.
167 In the case of a normal block header, it is added to the address of the end of the header
168 to give the address of the start of the data area i.e.
169 the value passed back to the application on a malloc.
170 Within a dummy header inside the padding, this same value is stored,
171 and is subtracted from the address of the dummy header to yield the address of the actual block header.
173 * size - the size of the data block, including the header itself.
174 For end-of-memzone structures, this size is given as zero, though it is never actually checked.
175 For normal blocks which are being freed,
176 this size value is used in place of a "next" pointer to identify the location of the next block of memory
177 (so that if it too is free, the two free blocks can be merged into one).
182 When an application makes a call to a malloc-like function,
183 the malloc function will first index the lcore_config structure for the calling thread,
184 and determine the NUMA node idea of that thread.
185 That is used to index the array of malloc_heap structures,
186 and the heap_alloc () function is called with that heap as parameter,
187 along with the requested size, type and alignment parameters.
189 The heap_alloc() function will scan the free_list for the heap,
190 and attempt to find a free block suitable for storing data of the requested size,
191 with the requested alignment constraints.
192 If no suitable block is found - for example, the first time malloc is called for a node,
193 and the free-list is NULL - a new memzone is reserved and set up as heap elements.
194 The setup involves placing a dummy structure at the end of the memzone
195 to act as a sentinel to prevent accesses beyond the end
196 (as the sentinel is marked as BUSY, the malloc library code will never attempt to reference it further),
197 and a proper element header at the start of the memzone.
198 This latter header identifies all space in the memzone, bar the sentinel value at the end,
199 as a single free heap element, and it is then added to the free_list for the heap.
201 Once the new memzone has been set up, the scan of the free-list for the heap is redone,
202 and on this occasion should find the newly created,
203 suitable element as the size of memory reserved in the memzone is set to be
204 at least the size of the requested data block plus the alignment -
205 subject to a minimum size specified in the DPDK compile-time configuration.
207 When a suitable, free element has been identified, the pointer to be returned to the user is calculated,
208 with the space to be provided to the user being at the end of the free block.
209 The cache-line of memory immediately preceding this space is filled with a struct malloc_elem header:
210 if the remaining space within the block is small e.g. <=128 bytes,
211 then a pad header is used, and the remaining space is wasted.
212 If, however, the remaining space is greater than this, then the single free element block is split into two,
213 and a new, proper, malloc_elem header is put before the returned data space.
214 [The advantage of allocating the memory from the end of the existing element is that
215 in this case no adjustment of the free list needs to take place -
216 the existing element on the free list just has its size pointer adjusted,
217 and the following element has its "prev" pointer redirected to the newly created element].
222 To free an area of memory, the pointer to the start of the data area is passed to the free function.
223 The size of the malloc_elem structure is subtracted from this pointer to get the element header for the block.
224 If this header is of type "PAD" then the pad length is further subtracted from the pointer
225 to get the proper element header for the entire block.
227 From this element header, we get pointers to the heap from which the block came -- and to where it must be freed,
228 as well as the pointer to the previous element, and, via the size field,
229 we can calculate the pointer to the next element.
230 These next and previous elements are then checked to see if they too are free,
231 and if so, they are merged with the current elements.
232 This means that we can never have two free memory blocks adjacent to one another,
233 they are always merged into a single block.