1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2010-2014 Intel Corporation. 3 4.. _Environment_Abstraction_Layer: 5 6Environment Abstraction Layer 7============================= 8 9The Environment Abstraction Layer (EAL) is responsible for gaining access to low-level resources such as hardware and memory space. 10It provides a generic interface that hides the environment specifics from the applications and libraries. 11It is the responsibility of the initialization routine to decide how to allocate these resources 12(that is, memory space, PCI devices, timers, consoles, and so on). 13 14Typical services expected from the EAL are: 15 16* DPDK Loading and Launching: 17 The DPDK and its application are linked as a single application and must be loaded by some means. 18 19* Core Affinity/Assignment Procedures: 20 The EAL provides mechanisms for assigning execution units to specific cores as well as creating execution instances. 21 22* System Memory Reservation: 23 The EAL facilitates the reservation of different memory zones, for example, physical memory areas for device interactions. 24 25* PCI Address Abstraction: The EAL provides an interface to access PCI address space. 26 27* Trace and Debug Functions: Logs, dump_stack, panic and so on. 28 29* Utility Functions: Spinlocks and atomic counters that are not provided in libc. 30 31* CPU Feature Identification: Determine at runtime if a particular feature, for example, Intel® AVX is supported. 32 Determine if the current CPU supports the feature set that the binary was compiled for. 33 34* Interrupt Handling: Interfaces to register/unregister callbacks to specific interrupt sources. 35 36* Alarm Functions: Interfaces to set/remove callbacks to be run at a specific time. 37 38EAL in a Linux-userland Execution Environment 39--------------------------------------------- 40 41In a Linux user space environment, the DPDK application runs as a user-space application using the pthread library. 42PCI information about devices and address space is discovered through the /sys kernel interface and through kernel modules such as uio_pci_generic, or igb_uio. 43Refer to the UIO: User-space drivers documentation in the Linux kernel. This memory is mmap'd in the application. 44 45The EAL performs physical memory allocation using mmap() in hugetlbfs (using huge page sizes to increase performance). 46This memory is exposed to DPDK service layers such as the :ref:`Mempool Library <Mempool_Library>`. 47 48At this point, the DPDK services layer will be initialized, then through pthread setaffinity calls, 49each execution unit will be assigned to a specific logical core to run as a user-level thread. 50 51The time reference is provided by the CPU Time-Stamp Counter (TSC) or by the HPET kernel API through a mmap() call. 52 53Initialization and Core Launching 54~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 55 56Part of the initialization is done by the start function of glibc. 57A check is also performed at initialization time to ensure that the micro architecture type chosen in the config file is supported by the CPU. 58Then, the main() function is called. The core initialization and launch is done in rte_eal_init() (see the API documentation). 59It consist of calls to the pthread library (more specifically, pthread_self(), pthread_create(), and pthread_setaffinity_np()). 60 61.. _figure_linuxapp_launch: 62 63.. figure:: img/linuxapp_launch.* 64 65 EAL Initialization in a Linux Application Environment 66 67 68.. note:: 69 70 Initialization of objects, such as memory zones, rings, memory pools, lpm tables and hash tables, 71 should be done as part of the overall application initialization on the master lcore. 72 The creation and initialization functions for these objects are not multi-thread safe. 73 However, once initialized, the objects themselves can safely be used in multiple threads simultaneously. 74 75Shutdown and Cleanup 76~~~~~~~~~~~~~~~~~~~~ 77 78During the initialization of EAL resources such as hugepage backed memory can be 79allocated by core components. The memory allocated during ``rte_eal_init()`` 80can be released by calling the ``rte_eal_cleanup()`` function. Refer to the 81API documentation for details. 82 83Multi-process Support 84~~~~~~~~~~~~~~~~~~~~~ 85 86The Linuxapp EAL allows a multi-process as well as a multi-threaded (pthread) deployment model. 87See chapter 88:ref:`Multi-process Support <Multi-process_Support>` for more details. 89 90Memory Mapping Discovery and Memory Reservation 91~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 92 93The allocation of large contiguous physical memory is done using the hugetlbfs kernel filesystem. 94The EAL provides an API to reserve named memory zones in this contiguous memory. 95The physical address of the reserved memory for that memory zone is also returned to the user by the memory zone reservation API. 96 97.. note:: 98 99 Memory reservations done using the APIs provided by rte_malloc are also backed by pages from the hugetlbfs filesystem. 100 101PCI Access 102~~~~~~~~~~ 103 104The EAL uses the /sys/bus/pci utilities provided by the kernel to scan the content on the PCI bus. 105To access PCI memory, a kernel module called uio_pci_generic provides a /dev/uioX device file 106and resource files in /sys 107that can be mmap'd to obtain access to PCI address space from the application. 108The DPDK-specific igb_uio module can also be used for this. Both drivers use the uio kernel feature (userland driver). 109 110Per-lcore and Shared Variables 111~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 112 113.. note:: 114 115 lcore refers to a logical execution unit of the processor, sometimes called a hardware *thread*. 116 117Shared variables are the default behavior. 118Per-lcore variables are implemented using *Thread Local Storage* (TLS) to provide per-thread local storage. 119 120Logs 121~~~~ 122 123A logging API is provided by EAL. 124By default, in a Linux application, logs are sent to syslog and also to the console. 125However, the log function can be overridden by the user to use a different logging mechanism. 126 127Trace and Debug Functions 128^^^^^^^^^^^^^^^^^^^^^^^^^ 129 130There are some debug functions to dump the stack in glibc. 131The rte_panic() function can voluntarily provoke a SIG_ABORT, 132which can trigger the generation of a core file, readable by gdb. 133 134CPU Feature Identification 135~~~~~~~~~~~~~~~~~~~~~~~~~~ 136 137The EAL can query the CPU at runtime (using the rte_cpu_get_features() function) to determine which CPU features are available. 138 139User Space Interrupt Event 140~~~~~~~~~~~~~~~~~~~~~~~~~~ 141 142+ User Space Interrupt and Alarm Handling in Host Thread 143 144The EAL creates a host thread to poll the UIO device file descriptors to detect the interrupts. 145Callbacks can be registered or unregistered by the EAL functions for a specific interrupt event 146and are called in the host thread asynchronously. 147The EAL also allows timed callbacks to be used in the same way as for NIC interrupts. 148 149.. note:: 150 151 In DPDK PMD, the only interrupts handled by the dedicated host thread are those for link status change 152 (link up and link down notification) and for sudden device removal. 153 154 155+ RX Interrupt Event 156 157The receive and transmit routines provided by each PMD don't limit themselves to execute in polling thread mode. 158To ease the idle polling with tiny throughput, it's useful to pause the polling and wait until the wake-up event happens. 159The RX interrupt is the first choice to be such kind of wake-up event, but probably won't be the only one. 160 161EAL provides the event APIs for this event-driven thread mode. 162Taking linuxapp as an example, the implementation relies on epoll. Each thread can monitor an epoll instance 163in which all the wake-up events' file descriptors are added. The event file descriptors are created and mapped to 164the interrupt vectors according to the UIO/VFIO spec. 165From bsdapp's perspective, kqueue is the alternative way, but not implemented yet. 166 167EAL initializes the mapping between event file descriptors and interrupt vectors, while each device initializes the mapping 168between interrupt vectors and queues. In this way, EAL actually is unaware of the interrupt cause on the specific vector. 169The eth_dev driver takes responsibility to program the latter mapping. 170 171.. note:: 172 173 Per queue RX interrupt event is only allowed in VFIO which supports multiple MSI-X vector. In UIO, the RX interrupt 174 together with other interrupt causes shares the same vector. In this case, when RX interrupt and LSC(link status change) 175 interrupt are both enabled(intr_conf.lsc == 1 && intr_conf.rxq == 1), only the former is capable. 176 177The RX interrupt are controlled/enabled/disabled by ethdev APIs - 'rte_eth_dev_rx_intr_*'. They return failure if the PMD 178hasn't support them yet. The intr_conf.rxq flag is used to turn on the capability of RX interrupt per device. 179 180+ Device Removal Event 181 182This event is triggered by a device being removed at a bus level. Its 183underlying resources may have been made unavailable (i.e. PCI mappings 184unmapped). The PMD must make sure that on such occurrence, the application can 185still safely use its callbacks. 186 187This event can be subscribed to in the same way one would subscribe to a link 188status change event. The execution context is thus the same, i.e. it is the 189dedicated interrupt host thread. 190 191Considering this, it is likely that an application would want to close a 192device having emitted a Device Removal Event. In such case, calling 193``rte_eth_dev_close()`` can trigger it to unregister its own Device Removal Event 194callback. Care must be taken not to close the device from the interrupt handler 195context. It is necessary to reschedule such closing operation. 196 197Blacklisting 198~~~~~~~~~~~~ 199 200The EAL PCI device blacklist functionality can be used to mark certain NIC ports as blacklisted, 201so they are ignored by the DPDK. 202The ports to be blacklisted are identified using the PCIe* description (Domain:Bus:Device.Function). 203 204Misc Functions 205~~~~~~~~~~~~~~ 206 207Locks and atomic operations are per-architecture (i686 and x86_64). 208 209Memory Segments and Memory Zones (memzone) 210------------------------------------------ 211 212The mapping of physical memory is provided by this feature in the EAL. 213As physical memory can have gaps, the memory is described in a table of descriptors, 214and each descriptor (called rte_memseg ) describes a contiguous portion of memory. 215 216On top of this, the memzone allocator's role is to reserve contiguous portions of physical memory. 217These zones are identified by a unique name when the memory is reserved. 218 219The rte_memzone descriptors are also located in the configuration structure. 220This structure is accessed using rte_eal_get_configuration(). 221The lookup (by name) of a memory zone returns a descriptor containing the physical address of the memory zone. 222 223Memory zones can be reserved with specific start address alignment by supplying the align parameter 224(by default, they are aligned to cache line size). 225The alignment value should be a power of two and not less than the cache line size (64 bytes). 226Memory zones can also be reserved from either 2 MB or 1 GB hugepages, provided that both are available on the system. 227 228 229Multiple pthread 230---------------- 231 232DPDK usually pins one pthread per core to avoid the overhead of task switching. 233This allows for significant performance gains, but lacks flexibility and is not always efficient. 234 235Power management helps to improve the CPU efficiency by limiting the CPU runtime frequency. 236However, alternately it is possible to utilize the idle cycles available to take advantage of 237the full capability of the CPU. 238 239By taking advantage of cgroup, the CPU utilization quota can be simply assigned. 240This gives another way to improve the CPU efficiency, however, there is a prerequisite; 241DPDK must handle the context switching between multiple pthreads per core. 242 243For further flexibility, it is useful to set pthread affinity not only to a CPU but to a CPU set. 244 245EAL pthread and lcore Affinity 246~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 247 248The term "lcore" refers to an EAL thread, which is really a Linux/FreeBSD pthread. 249"EAL pthreads" are created and managed by EAL and execute the tasks issued by *remote_launch*. 250In each EAL pthread, there is a TLS (Thread Local Storage) called *_lcore_id* for unique identification. 251As EAL pthreads usually bind 1:1 to the physical CPU, the *_lcore_id* is typically equal to the CPU ID. 252 253When using multiple pthreads, however, the binding is no longer always 1:1 between an EAL pthread and a specified physical CPU. 254The EAL pthread may have affinity to a CPU set, and as such the *_lcore_id* will not be the same as the CPU ID. 255For this reason, there is an EAL long option '--lcores' defined to assign the CPU affinity of lcores. 256For a specified lcore ID or ID group, the option allows setting the CPU set for that EAL pthread. 257 258The format pattern: 259 --lcores='<lcore_set>[@cpu_set][,<lcore_set>[@cpu_set],...]' 260 261'lcore_set' and 'cpu_set' can be a single number, range or a group. 262 263A number is a "digit([0-9]+)"; a range is "<number>-<number>"; a group is "(<number|range>[,<number|range>,...])". 264 265If a '\@cpu_set' value is not supplied, the value of 'cpu_set' will default to the value of 'lcore_set'. 266 267 :: 268 269 For example, "--lcores='1,2@(5-7),(3-5)@(0,2),(0,6),7-8'" which means start 9 EAL thread; 270 lcore 0 runs on cpuset 0x41 (cpu 0,6); 271 lcore 1 runs on cpuset 0x2 (cpu 1); 272 lcore 2 runs on cpuset 0xe0 (cpu 5,6,7); 273 lcore 3,4,5 runs on cpuset 0x5 (cpu 0,2); 274 lcore 6 runs on cpuset 0x41 (cpu 0,6); 275 lcore 7 runs on cpuset 0x80 (cpu 7); 276 lcore 8 runs on cpuset 0x100 (cpu 8). 277 278Using this option, for each given lcore ID, the associated CPUs can be assigned. 279It's also compatible with the pattern of corelist('-l') option. 280 281non-EAL pthread support 282~~~~~~~~~~~~~~~~~~~~~~~ 283 284It is possible to use the DPDK execution context with any user pthread (aka. Non-EAL pthreads). 285In a non-EAL pthread, the *_lcore_id* is always LCORE_ID_ANY which identifies that it is not an EAL thread with a valid, unique, *_lcore_id*. 286Some libraries will use an alternative unique ID (e.g. TID), some will not be impacted at all, and some will work but with limitations (e.g. timer and mempool libraries). 287 288All these impacts are mentioned in :ref:`known_issue_label` section. 289 290Public Thread API 291~~~~~~~~~~~~~~~~~ 292 293There are two public APIs ``rte_thread_set_affinity()`` and ``rte_thread_get_affinity()`` introduced for threads. 294When they're used in any pthread context, the Thread Local Storage(TLS) will be set/get. 295 296Those TLS include *_cpuset* and *_socket_id*: 297 298* *_cpuset* stores the CPUs bitmap to which the pthread is affinitized. 299 300* *_socket_id* stores the NUMA node of the CPU set. If the CPUs in CPU set belong to different NUMA node, the *_socket_id* will be set to SOCKET_ID_ANY. 301 302 303.. _known_issue_label: 304 305Known Issues 306~~~~~~~~~~~~ 307 308+ rte_mempool 309 310 The rte_mempool uses a per-lcore cache inside the mempool. 311 For non-EAL pthreads, ``rte_lcore_id()`` will not return a valid number. 312 So for now, when rte_mempool is used with non-EAL pthreads, the put/get operations will bypass the default mempool cache and there is a performance penalty because of this bypass. 313 Only user-owned external caches can be used in a non-EAL context in conjunction with ``rte_mempool_generic_put()`` and ``rte_mempool_generic_get()`` that accept an explicit cache parameter. 314 315+ rte_ring 316 317 rte_ring supports multi-producer enqueue and multi-consumer dequeue. 318 However, it is non-preemptive, this has a knock on effect of making rte_mempool non-preemptable. 319 320 .. note:: 321 322 The "non-preemptive" constraint means: 323 324 - a pthread doing multi-producers enqueues on a given ring must not 325 be preempted by another pthread doing a multi-producer enqueue on 326 the same ring. 327 - a pthread doing multi-consumers dequeues on a given ring must not 328 be preempted by another pthread doing a multi-consumer dequeue on 329 the same ring. 330 331 Bypassing this constraint may cause the 2nd pthread to spin until the 1st one is scheduled again. 332 Moreover, if the 1st pthread is preempted by a context that has an higher priority, it may even cause a dead lock. 333 334 This does not mean it cannot be used, simply, there is a need to narrow down the situation when it is used by multi-pthread on the same core. 335 336 1. It CAN be used for any single-producer or single-consumer situation. 337 338 2. It MAY be used by multi-producer/consumer pthread whose scheduling policy are all SCHED_OTHER(cfs). User SHOULD be aware of the performance penalty before using it. 339 340 3. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR. 341 342+ rte_timer 343 344 Running ``rte_timer_manage()`` on a non-EAL pthread is not allowed. However, resetting/stopping the timer from a non-EAL pthread is allowed. 345 346+ rte_log 347 348 In non-EAL pthreads, there is no per thread loglevel and logtype, global loglevels are used. 349 350+ misc 351 352 The debug statistics of rte_ring, rte_mempool and rte_timer are not supported in a non-EAL pthread. 353 354cgroup control 355~~~~~~~~~~~~~~ 356 357The following is a simple example of cgroup control usage, there are two pthreads(t0 and t1) doing packet I/O on the same core ($CPU). 358We expect only 50% of CPU spend on packet IO. 359 360 .. code-block:: console 361 362 mkdir /sys/fs/cgroup/cpu/pkt_io 363 mkdir /sys/fs/cgroup/cpuset/pkt_io 364 365 echo $cpu > /sys/fs/cgroup/cpuset/cpuset.cpus 366 367 echo $t0 > /sys/fs/cgroup/cpu/pkt_io/tasks 368 echo $t0 > /sys/fs/cgroup/cpuset/pkt_io/tasks 369 370 echo $t1 > /sys/fs/cgroup/cpu/pkt_io/tasks 371 echo $t1 > /sys/fs/cgroup/cpuset/pkt_io/tasks 372 373 cd /sys/fs/cgroup/cpu/pkt_io 374 echo 100000 > pkt_io/cpu.cfs_period_us 375 echo 50000 > pkt_io/cpu.cfs_quota_us 376 377 378Malloc 379------ 380 381The EAL provides a malloc API to allocate any-sized memory. 382 383The objective of this API is to provide malloc-like functions to allow 384allocation from hugepage memory and to facilitate application porting. 385The *DPDK API Reference* manual describes the available functions. 386 387Typically, these kinds of allocations should not be done in data plane 388processing because they are slower than pool-based allocation and make 389use of locks within the allocation and free paths. 390However, they can be used in configuration code. 391 392Refer to the rte_malloc() function description in the *DPDK API Reference* 393manual for more information. 394 395Cookies 396~~~~~~~ 397 398When CONFIG_RTE_MALLOC_DEBUG is enabled, the allocated memory contains 399overwrite protection fields to help identify buffer overflows. 400 401Alignment and NUMA Constraints 402~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 403 404The rte_malloc() takes an align argument that can be used to request a memory 405area that is aligned on a multiple of this value (which must be a power of two). 406 407On systems with NUMA support, a call to the rte_malloc() function will return 408memory that has been allocated on the NUMA socket of the core which made the call. 409A set of APIs is also provided, to allow memory to be explicitly allocated on a 410NUMA socket directly, or by allocated on the NUMA socket where another core is 411located, in the case where the memory is to be used by a logical core other than 412on the one doing the memory allocation. 413 414Use Cases 415~~~~~~~~~ 416 417This API is meant to be used by an application that requires malloc-like 418functions at initialization time. 419 420For allocating/freeing data at runtime, in the fast-path of an application, 421the memory pool library should be used instead. 422 423Internal Implementation 424~~~~~~~~~~~~~~~~~~~~~~~ 425 426Data Structures 427^^^^^^^^^^^^^^^ 428 429There are two data structure types used internally in the malloc library: 430 431* struct malloc_heap - used to track free space on a per-socket basis 432 433* struct malloc_elem - the basic element of allocation and free-space 434 tracking inside the library. 435 436Structure: malloc_heap 437"""""""""""""""""""""" 438 439The malloc_heap structure is used to manage free space on a per-socket basis. 440Internally, there is one heap structure per NUMA node, which allows us to 441allocate memory to a thread based on the NUMA node on which this thread runs. 442While this does not guarantee that the memory will be used on that NUMA node, 443it is no worse than a scheme where the memory is always allocated on a fixed 444or random node. 445 446The key fields of the heap structure and their function are described below 447(see also diagram above): 448 449* lock - the lock field is needed to synchronize access to the heap. 450 Given that the free space in the heap is tracked using a linked list, 451 we need a lock to prevent two threads manipulating the list at the same time. 452 453* free_head - this points to the first element in the list of free nodes for 454 this malloc heap. 455 456.. note:: 457 458 The malloc_heap structure does not keep track of in-use blocks of memory, 459 since these are never touched except when they are to be freed again - 460 at which point the pointer to the block is an input to the free() function. 461 462.. _figure_malloc_heap: 463 464.. figure:: img/malloc_heap.* 465 466 Example of a malloc heap and malloc elements within the malloc library 467 468 469.. _malloc_elem: 470 471Structure: malloc_elem 472"""""""""""""""""""""" 473 474The malloc_elem structure is used as a generic header structure for various 475blocks of memory. 476It is used in three different ways - all shown in the diagram above: 477 478#. As a header on a block of free or allocated memory - normal case 479 480#. As a padding header inside a block of memory 481 482#. As an end-of-memseg marker 483 484The most important fields in the structure and how they are used are described below. 485 486.. note:: 487 488 If the usage of a particular field in one of the above three usages is not 489 described, the field can be assumed to have an undefined value in that 490 situation, for example, for padding headers only the "state" and "pad" 491 fields have valid values. 492 493* heap - this pointer is a reference back to the heap structure from which 494 this block was allocated. 495 It is used for normal memory blocks when they are being freed, to add the 496 newly-freed block to the heap's free-list. 497 498* prev - this pointer points to the header element/block in the memseg 499 immediately behind the current one. When freeing a block, this pointer is 500 used to reference the previous block to check if that block is also free. 501 If so, then the two free blocks are merged to form a single larger block. 502 503* next_free - this pointer is used to chain the free-list of unallocated 504 memory blocks together. 505 It is only used in normal memory blocks; on ``malloc()`` to find a suitable 506 free block to allocate and on ``free()`` to add the newly freed element to 507 the free-list. 508 509* state - This field can have one of three values: ``FREE``, ``BUSY`` or 510 ``PAD``. 511 The former two are to indicate the allocation state of a normal memory block 512 and the latter is to indicate that the element structure is a dummy structure 513 at the end of the start-of-block padding, i.e. where the start of the data 514 within a block is not at the start of the block itself, due to alignment 515 constraints. 516 In that case, the pad header is used to locate the actual malloc element 517 header for the block. 518 For the end-of-memseg structure, this is always a ``BUSY`` value, which 519 ensures that no element, on being freed, searches beyond the end of the 520 memseg for other blocks to merge with into a larger free area. 521 522* pad - this holds the length of the padding present at the start of the block. 523 In the case of a normal block header, it is added to the address of the end 524 of the header to give the address of the start of the data area, i.e. the 525 value passed back to the application on a malloc. 526 Within a dummy header inside the padding, this same value is stored, and is 527 subtracted from the address of the dummy header to yield the address of the 528 actual block header. 529 530* size - the size of the data block, including the header itself. 531 For end-of-memseg structures, this size is given as zero, though it is never 532 actually checked. 533 For normal blocks which are being freed, this size value is used in place of 534 a "next" pointer to identify the location of the next block of memory that 535 in the case of being ``FREE``, the two free blocks can be merged into one. 536 537Memory Allocation 538^^^^^^^^^^^^^^^^^ 539 540On EAL initialization, all memsegs are setup as part of the malloc heap. 541This setup involves placing a dummy structure at the end with ``BUSY`` state, 542which may contain a sentinel value if ``CONFIG_RTE_MALLOC_DEBUG`` is enabled, 543and a proper :ref:`element header<malloc_elem>` with ``FREE`` at the start 544for each memseg. 545The ``FREE`` element is then added to the ``free_list`` for the malloc heap. 546 547When an application makes a call to a malloc-like function, the malloc function 548will first index the ``lcore_config`` structure for the calling thread, and 549determine the NUMA node of that thread. 550The NUMA node is used to index the array of ``malloc_heap`` structures which is 551passed as a parameter to the ``heap_alloc()`` function, along with the 552requested size, type, alignment and boundary parameters. 553 554The ``heap_alloc()`` function will scan the free_list of the heap, and attempt 555to find a free block suitable for storing data of the requested size, with the 556requested alignment and boundary constraints. 557 558When a suitable free element has been identified, the pointer to be returned 559to the user is calculated. 560The cache-line of memory immediately preceding this pointer is filled with a 561struct malloc_elem header. 562Because of alignment and boundary constraints, there could be free space at 563the start and/or end of the element, resulting in the following behavior: 564 565#. Check for trailing space. 566 If the trailing space is big enough, i.e. > 128 bytes, then the free element 567 is split. 568 If it is not, then we just ignore it (wasted space). 569 570#. Check for space at the start of the element. 571 If the space at the start is small, i.e. <=128 bytes, then a pad header is 572 used, and the remaining space is wasted. 573 If, however, the remaining space is greater, then the free element is split. 574 575The advantage of allocating the memory from the end of the existing element is 576that no adjustment of the free list needs to take place - the existing element 577on the free list just has its size pointer adjusted, and the following element 578has its "prev" pointer redirected to the newly created element. 579 580Freeing Memory 581^^^^^^^^^^^^^^ 582 583To free an area of memory, the pointer to the start of the data area is passed 584to the free function. 585The size of the ``malloc_elem`` structure is subtracted from this pointer to get 586the element header for the block. 587If this header is of type ``PAD`` then the pad length is further subtracted from 588the pointer to get the proper element header for the entire block. 589 590From this element header, we get pointers to the heap from which the block was 591allocated and to where it must be freed, as well as the pointer to the previous 592element, and via the size field, we can calculate the pointer to the next element. 593These next and previous elements are then checked to see if they are also 594``FREE``, and if so, they are merged with the current element. 595This means that we can never have two ``FREE`` memory blocks adjacent to one 596another, as they are always merged into a single block. 597