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.
122 **Figure 3. Example of a malloc heap and malloc elements within the malloc library**
124 .. image4_png has been renamed
128 Structure: malloc_elem
129 ^^^^^^^^^^^^^^^^^^^^^^
130 The malloc_elem structure is used as a generic header structure for various blocks of memory in a memzone.
131 It is used in three different ways - all shown in the diagram above:
133 #. As a header on a block of free or allocated memory - normal case
135 #. As a padding header inside a block of memory
137 #. As an end-of-memzone marker
139 The most important fields in the structure and how they are used are described below.
143 If the usage of a particular field in one of the above three usages is not described,
144 the field can be assumed to have an undefined value in that situation, for example,
145 for padding headers only the "state" and "pad" fields have valid values.
147 * heap - this pointer is a reference back to the heap structure from which this block was allocated.
148 It is used for normal memory blocks when they are being freed,
149 to add the newly-freed block to the heap's free-list.
151 * prev - this pointer points to the header element/block in the memzone immediately behind the current one.
152 When freeing a block, this pointer is used to reference the previous block to check if that block is also free.
153 If so, then the two free blocks are merged to form a single larger block.
155 * next_free - this pointer is used to chain the free-list of unallocated memory blocks together.
156 Again, it is only used in normal memory blocks - on malloc() to find a suitable free block to allocate,
157 and on free() to add the newly freed element to the free-list.
159 * state - This field can have one of three values: "Free", "Busy" or "Pad".
160 The former two, are to indicate the allocation state of a normal memory block,
161 and the latter is to indicate that the element structure is a dummy structure at the end of the start-of-block padding
162 (i.e. where the start of the data within a block is not at the start of the block itself, due to alignment constraints).
163 In this case, the pad header is used to locate the actual malloc element header for the block.
164 For the end-of-memzone structure, this is always a "busy" value, which ensures that no element,
165 on being freed, searches beyond the end of the memzone for other blocks to merge with into a larger free area.
167 * pad - this holds the length of the padding present at the start of the block.
168 In the case of a normal block header, it is added to the address of the end of the header
169 to give the address of the start of the data area i.e.
170 the value passed back to the application on a malloc.
171 Within a dummy header inside the padding, this same value is stored,
172 and is subtracted from the address of the dummy header to yield the address of the actual block header.
174 * size - the size of the data block, including the header itself.
175 For end-of-memzone structures, this size is given as zero, though it is never actually checked.
176 For normal blocks which are being freed,
177 this size value is used in place of a "next" pointer to identify the location of the next block of memory
178 (so that if it too is free, the two free blocks can be merged into one).
183 When an application makes a call to a malloc-like function,
184 the malloc function will first index the lcore_config structure for the calling thread,
185 and determine the NUMA node idea of that thread.
186 That is used to index the array of malloc_heap structures,
187 and the heap_alloc () function is called with that heap as parameter,
188 along with the requested size, type and alignment parameters.
190 The heap_alloc() function will scan the free_list for the heap,
191 and attempt to find a free block suitable for storing data of the requested size,
192 with the requested alignment constraints.
193 If no suitable block is found - for example, the first time malloc is called for a node,
194 and the free-list is NULL - a new memzone is reserved and set up as heap elements.
195 The setup involves placing a dummy structure at the end of the memzone
196 to act as a sentinel to prevent accesses beyond the end
197 (as the sentinel is marked as BUSY, the malloc library code will never attempt to reference it further),
198 and a proper element header at the start of the memzone.
199 This latter header identifies all space in the memzone, bar the sentinel value at the end,
200 as a single free heap element, and it is then added to the free_list for the heap.
202 Once the new memzone has been set up, the scan of the free-list for the heap is redone,
203 and on this occasion should find the newly created,
204 suitable element as the size of memory reserved in the memzone is set to be
205 at least the size of the requested data block plus the alignment -
206 subject to a minimum size specified in the DPDK compile-time configuration.
208 When a suitable, free element has been identified, the pointer to be returned to the user is calculated,
209 with the space to be provided to the user being at the end of the free block.
210 The cache-line of memory immediately preceding this space is filled with a struct malloc_elem header:
211 if the remaining space within the block is small e.g. <=128 bytes,
212 then a pad header is used, and the remaining space is wasted.
213 If, however, the remaining space is greater than this, then the single free element block is split into two,
214 and a new, proper, malloc_elem header is put before the returned data space.
215 [The advantage of allocating the memory from the end of the existing element is that
216 in this case no adjustment of the free list needs to take place -
217 the existing element on the free list just has its size pointer adjusted,
218 and the following element has its "prev" pointer redirected to the newly created element].
223 To free an area of memory, the pointer to the start of the data area is passed to the free function.
224 The size of the malloc_elem structure is subtracted from this pointer to get the element header for the block.
225 If this header is of type "PAD" then the pad length is further subtracted from the pointer
226 to get the proper element header for the entire block.
228 From this element header, we get pointers to the heap from which the block came -- and to where it must be freed,
229 as well as the pointer to the previous element, and, via the size field,
230 we can calculate the pointer to the next element.
231 These next and previous elements are then checked to see if they too are free,
232 and if so, they are merged with the current elements.
233 This means that we can never have two free memory blocks adjacent to one another,
234 they are always merged into a single block.
236 .. |malloc_heap| image:: img/malloc_heap.*