iPXE
Data Structures | Defines | Functions | Variables
malloc.h File Reference

Dynamic memory allocation. More...

#include <stdint.h>
#include <stdlib.h>
#include <ipxe/tables.h>
#include <valgrind/memcheck.h>

Go to the source code of this file.

Data Structures

struct  cache_discarder
 A cache discarder. More...

Defines

#define CACHE_DISCARDERS   __table ( struct cache_discarder, "cache_discarders" )
 Cache discarder table.
#define __cache_discarder(cost)   __table_entry ( CACHE_DISCARDERS, cost )
 Declare a cache discarder.
#define CACHE_CHEAP   01
 Items with a low replacement cost.
#define CACHE_NORMAL   02
 Items with a normal replacement cost.
#define CACHE_EXPENSIVE   03
 Items with a high replacement cost.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
void *__malloc alloc_memblock (size_t size, size_t align, size_t offset)
 Allocate a memory block.
void free_memblock (void *ptr, size_t size)
 Free a memory block.
void mpopulate (void *start, size_t len)
 Add memory to allocation pool.
void mdumpfree (void)
static void *__malloc malloc_dma_offset (size_t size, size_t phys_align, size_t offset)
 Allocate memory for DMA.
static void *__malloc malloc_dma (size_t size, size_t phys_align)
 Allocate memory for DMA.
static void free_dma (void *ptr, size_t size)
 Free memory allocated with malloc_dma()

Variables

size_t freemem
 Total amount of free memory.
size_t usedmem
 Total amount of used memory.
size_t maxusedmem
 Maximum amount of used memory.

Detailed Description

Dynamic memory allocation.

Definition in file malloc.h.


Define Documentation

#define CACHE_DISCARDERS   __table ( struct cache_discarder, "cache_discarders" )

Cache discarder table.

Definition at line 97 of file malloc.h.

Referenced by discard_cache().

Declare a cache discarder.

Definition at line 100 of file malloc.h.


Function Documentation

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )
void* __malloc alloc_memblock ( size_t  size,
size_t  align,
size_t  offset 
)

Allocate a memory block.

Parameters:
sizeRequested size
alignPhysical alignment
offsetOffset from physical alignment
Return values:
ptrMemory block, or NULL

Allocates a memory block physically aligned as requested. No guarantees are provided for the alignment of the virtual address.

align must be a power of two. size may not be zero.

Definition at line 279 of file malloc.c.

References assert, block, check_blocks(), DBGC, DBGC2, discard_cache(), done, freemem, heap, memory_block::list, list_add, list_del, list_for_each_entry, maxusedmem, MIN_MEMBLOCK_SIZE, NULL, memory_block::size, usedmem, valgrind_make_blocks_defined(), valgrind_make_blocks_noaccess(), VALGRIND_MAKE_MEM_NOACCESS, VALGRIND_MAKE_MEM_UNDEFINED, and virt_to_phys().

Referenced by malloc_dma_offset(), and realloc().

                                                                   {
        struct memory_block *block;
        size_t align_mask;
        size_t actual_size;
        size_t pre_size;
        size_t post_size;
        struct memory_block *pre;
        struct memory_block *post;
        unsigned int discarded;
        void *ptr;

        /* Sanity checks */
        assert ( size != 0 );
        assert ( ( align == 0 ) || ( ( align & ( align - 1 ) ) == 0 ) );
        valgrind_make_blocks_defined();
        check_blocks();

        /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
         * calculate alignment mask.
         */
        actual_size = ( ( size + MIN_MEMBLOCK_SIZE - 1 ) &
                        ~( MIN_MEMBLOCK_SIZE - 1 ) );
        if ( ! actual_size ) {
                /* The requested size is not permitted to be zero.  A
                 * zero result at this point indicates that either the
                 * original requested size was zero, or that unsigned
                 * integer overflow has occurred.
                 */
                ptr = NULL;
                goto done;
        }
        assert ( actual_size >= size );
        align_mask = ( ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 ) );

        DBGC2 ( &heap, "Allocating %#zx (aligned %#zx+%zx)\n",
                size, align, offset );
        while ( 1 ) {
                /* Search through blocks for the first one with enough space */
                list_for_each_entry ( block, &free_blocks, list ) {
                        pre_size = ( ( offset - virt_to_phys ( block ) )
                                     & align_mask );
                        if ( ( block->size < pre_size ) ||
                             ( ( block->size - pre_size ) < actual_size ) )
                                continue;
                        post_size = ( block->size - pre_size - actual_size );
                        /* Split block into pre-block, block, and
                         * post-block.  After this split, the "pre"
                         * block is the one currently linked into the
                         * free list.
                         */
                        pre   = block;
                        block = ( ( ( void * ) pre   ) + pre_size );
                        post  = ( ( ( void * ) block ) + actual_size );
                        DBGC2 ( &heap, "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
                                ( ( ( void * ) pre ) + pre->size ), pre, block,
                                post, ( ( ( void * ) pre ) + pre->size ) );
                        /* If there is a "post" block, add it in to
                         * the free list.  Leak it if it is too small
                         * (which can happen only at the very end of
                         * the heap).
                         */
                        if ( post_size >= MIN_MEMBLOCK_SIZE ) {
                                VALGRIND_MAKE_MEM_UNDEFINED ( post,
                                                              sizeof ( *post ));
                                post->size = post_size;
                                list_add ( &post->list, &pre->list );
                        }
                        /* Shrink "pre" block, leaving the main block
                         * isolated and no longer part of the free
                         * list.
                         */
                        pre->size = pre_size;
                        /* If there is no "pre" block, remove it from
                         * the list.  Also remove it (i.e. leak it) if
                         * it is too small, which can happen only at
                         * the very start of the heap.
                         */
                        if ( pre_size < MIN_MEMBLOCK_SIZE ) {
                                list_del ( &pre->list );
                                VALGRIND_MAKE_MEM_NOACCESS ( pre,
                                                             sizeof ( *pre ) );
                        }
                        /* Update memory usage statistics */
                        freemem -= actual_size;
                        usedmem += actual_size;
                        if ( usedmem > maxusedmem )
                                maxusedmem = usedmem;
                        /* Return allocated block */
                        DBGC2 ( &heap, "Allocated [%p,%p)\n", block,
                                ( ( ( void * ) block ) + size ) );
                        ptr = block;
                        VALGRIND_MAKE_MEM_UNDEFINED ( ptr, size );
                        goto done;
                }

                /* Try discarding some cached data to free up memory */
                DBGC ( &heap, "Attempting discard for %#zx (aligned %#zx+%zx), "
                       "used %zdkB\n", size, align, offset, ( usedmem >> 10 ) );
                valgrind_make_blocks_noaccess();
                discarded = discard_cache();
                valgrind_make_blocks_defined();
                check_blocks();
                if ( ! discarded ) {
                        /* Nothing available to discard */
                        DBGC ( &heap, "Failed to allocate %#zx (aligned "
                               "%#zx)\n", size, align );
                        ptr = NULL;
                        goto done;
                }
        }

 done:
        check_blocks();
        valgrind_make_blocks_noaccess();
        return ptr;
}
void free_memblock ( void *  ptr,
size_t  size 
)

Free a memory block.

Parameters:
ptrMemory allocated by alloc_memblock(), or NULL
sizeSize of the memory

If ptr is NULL, no action is taken.

Definition at line 404 of file malloc.c.

References assert, block, check_blocks(), DBGC, DBGC2, freemem, heap, memory_block::list, list_add_tail, list_del, list_for_each_entry, list_for_each_entry_safe, MIN_MEMBLOCK_SIZE, usedmem, valgrind_make_blocks_defined(), valgrind_make_blocks_noaccess(), VALGRIND_MAKE_MEM_NOACCESS, and VALGRIND_MAKE_MEM_UNDEFINED.

Referenced by free_dma(), mpopulate(), and realloc().

                                              {
        struct memory_block *freeing;
        struct memory_block *block;
        struct memory_block *tmp;
        size_t actual_size;
        ssize_t gap_before;
        ssize_t gap_after = -1;

        /* Allow for ptr==NULL */
        if ( ! ptr )
                return;
        VALGRIND_MAKE_MEM_NOACCESS ( ptr, size );

        /* Sanity checks */
        valgrind_make_blocks_defined();
        check_blocks();

        /* Round up size to match actual size that alloc_memblock()
         * would have used.
         */
        assert ( size != 0 );
        actual_size = ( ( size + MIN_MEMBLOCK_SIZE - 1 ) &
                        ~( MIN_MEMBLOCK_SIZE - 1 ) );
        freeing = ptr;
        VALGRIND_MAKE_MEM_UNDEFINED ( freeing, sizeof ( *freeing ) );
        DBGC2 ( &heap, "Freeing [%p,%p)\n",
                freeing, ( ( ( void * ) freeing ) + size ) );

        /* Check that this block does not overlap the free list */
        if ( ASSERTING ) {
                list_for_each_entry ( block, &free_blocks, list ) {
                        if ( ( ( ( void * ) block ) <
                               ( ( void * ) freeing + actual_size ) ) &&
                             ( ( void * ) freeing <
                               ( ( void * ) block + block->size ) ) ) {
                                assert ( 0 );
                                DBGC ( &heap, "Double free of [%p,%p) "
                                       "overlapping [%p,%p) detected from %p\n",
                                       freeing,
                                       ( ( ( void * ) freeing ) + size ), block,
                                       ( ( void * ) block + block->size ),
                                       __builtin_return_address ( 0 ) );
                        }
                }
        }

        /* Insert/merge into free list */
        freeing->size = actual_size;
        list_for_each_entry_safe ( block, tmp, &free_blocks, list ) {
                /* Calculate gaps before and after the "freeing" block */
                gap_before = ( ( ( void * ) freeing ) - 
                               ( ( ( void * ) block ) + block->size ) );
                gap_after = ( ( ( void * ) block ) - 
                              ( ( ( void * ) freeing ) + freeing->size ) );
                /* Merge with immediately preceding block, if possible */
                if ( gap_before == 0 ) {
                        DBGC2 ( &heap, "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
                                ( ( ( void * ) block ) + block->size ), freeing,
                                ( ( ( void * ) freeing ) + freeing->size ),
                                block,
                                ( ( ( void * ) freeing ) + freeing->size ) );
                        block->size += actual_size;
                        list_del ( &block->list );
                        VALGRIND_MAKE_MEM_NOACCESS ( freeing,
                                                     sizeof ( *freeing ) );
                        freeing = block;
                }
                /* Stop processing as soon as we reach a following block */
                if ( gap_after >= 0 )
                        break;
        }

        /* Insert before the immediately following block.  If
         * possible, merge the following block into the "freeing"
         * block.
         */
        DBGC2 ( &heap, "[%p,%p)\n",
                freeing, ( ( ( void * ) freeing ) + freeing->size ) );
        list_add_tail ( &freeing->list, &block->list );
        if ( gap_after == 0 ) {
                DBGC2 ( &heap, "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
                        ( ( ( void * ) freeing ) + freeing->size ), block,
                        ( ( ( void * ) block ) + block->size ), freeing,
                        ( ( ( void * ) block ) + block->size ) );
                freeing->size += block->size;
                list_del ( &block->list );
                VALGRIND_MAKE_MEM_NOACCESS ( block, sizeof ( *block ) );
        }

        /* Update memory usage statistics */
        freemem += actual_size;
        usedmem -= actual_size;

        check_blocks();
        valgrind_make_blocks_noaccess();
}
void mpopulate ( void *  start,
size_t  len 
)

Add memory to allocation pool.

Parameters:
startStart address
endEnd address

Adds a block of memory [start,end) to the allocation pool. This is a one-way operation; there is no way to reclaim this memory.

start must be aligned to at least a multiple of sizeof(void*).

Definition at line 648 of file malloc.c.

References free_memblock(), len, MIN_MEMBLOCK_SIZE, and usedmem.

Referenced by init_heap().

                                           {

        /* Prevent free_memblock() from rounding up len beyond the end
         * of what we were actually given...
         */
        len &= ~( MIN_MEMBLOCK_SIZE - 1 );

        /* Add to allocation pool */
        free_memblock ( start, len );

        /* Fix up memory usage statistics */
        usedmem += len;
}
void mdumpfree ( void  )
static void* __malloc malloc_dma_offset ( size_t  size,
size_t  phys_align,
size_t  offset 
) [inline, static]

Allocate memory for DMA.

Parameters:
sizeRequested size
alignPhysical alignment
offsetOffset from physical alignment
Return values:
ptrMemory, or NULL

Allocates physically-aligned memory for DMA.

align must be a power of two. size may not be zero.

Definition at line 46 of file malloc.h.

References alloc_memblock(), and VALGRIND_MALLOCLIKE_BLOCK.

Referenced by alloc_iob_raw(), and malloc_dma().

                                                                  {
        void * ptr = alloc_memblock ( size, phys_align, offset );
        if ( ptr && size )
                VALGRIND_MALLOCLIKE_BLOCK ( ptr, size, 0, 0 );
        return ptr;
}
static void* __malloc malloc_dma ( size_t  size,
size_t  phys_align 
) [inline, static]

Allocate memory for DMA.

Parameters:
sizeRequested size
alignPhysical alignment
Return values:
ptrMemory, or NULL

Allocates physically-aligned memory for DMA.

align must be a power of two. size may not be zero.

Definition at line 66 of file malloc.h.

References malloc_dma_offset().

Referenced by __vxge_hw_fifo_create(), __vxge_hw_ring_create(), a3c90x_setup_rx_ring(), a3c90x_setup_tx_ring(), arbel_alloc(), arbel_alloc_icm(), arbel_create_cq(), arbel_create_eq(), arbel_create_recv_wq(), arbel_create_send_wq(), ath5k_desc_alloc(), ath_descdma_setup(), atl1e_setup_ring_resources(), b44_init_rx_ring(), b44_init_tx_ring(), efx_hunt_alloc_special_buffer(), ehci_bus_open(), ehci_ring_alloc(), ena_create_admin(), ena_create_cq(), ena_create_sq(), exanic_probe(), falcon_alloc_special_buffer(), golan_cmd_init(), golan_create_cq(), golan_create_eq(), golan_create_qp_aux(), hermon_alloc(), hermon_create_cq(), hermon_create_eq(), hermon_create_qp(), hv_alloc_message(), hv_alloc_pages(), hvm_map_hypercall(), icplus_create_ring(), ifec_net_open(), ifec_tx_setup(), igbvf_setup_rx_resources(), igbvf_setup_tx_resources(), intel_create_ring(), intelxl_create_admin(), intelxl_create_ring(), jme_alloc_rx_resources(), jme_alloc_tx_resources(), linda_create_recv_wq(), linda_init_send(), mlx_memory_alloc_dma_priv(), myri10ge_net_open(), myson_create_ring(), natsemi_create_ring(), netfront_create_ring(), nv_init_rings(), pcnet32_setup_rx_resources(), pcnet32_setup_tx_resources(), phantom_create_rx_ctx(), phantom_create_tx_ctx(), phantom_open(), qib7322_create_recv_wq(), qib7322_init_send(), realtek_create_buffer(), realtek_create_ring(), rhine_create_ring(), rtl818x_init_rx_ring(), rtl818x_init_tx_ring(), sis190_open(), skge_up(), sky2_probe(), sky2_up(), tg3_alloc_consistent(), tg3_test_dma(), uhci_bus_open(), uhci_enqueue(), uhci_ring_alloc(), velocity_alloc_rings(), vmbus_open(), vmxnet3_open(), xhci_context(), xhci_dcbaa_alloc(), xhci_device_open(), xhci_event_alloc(), xhci_ring_alloc(), and xhci_scratchpad_alloc().

                                                                            {
        return malloc_dma_offset ( size, phys_align, 0 );
}
static void free_dma ( void *  ptr,
size_t  size 
) [inline, static]

Free memory allocated with malloc_dma()

Parameters:
ptrMemory allocated by malloc_dma(), or NULL
sizeSize of memory, as passed to malloc_dma()

Memory allocated with malloc_dma() can only be freed with free_dma(); it cannot be freed with the standard free().

If ptr is NULL, no action is taken.

Definition at line 81 of file malloc.h.

References free_memblock(), and VALGRIND_FREELIKE_BLOCK.

Referenced by __vxge_hw_fifo_delete(), __vxge_hw_ring_delete(), a3c90x_free_rx_ring(), a3c90x_free_tx_ring(), alloc_iob_raw(), arbel_alloc(), arbel_alloc_icm(), arbel_create_cq(), arbel_create_eq(), arbel_create_qp(), arbel_create_recv_wq(), arbel_destroy_cq(), arbel_destroy_eq(), arbel_destroy_qp(), arbel_free(), arbel_free_icm(), ath5k_desc_alloc(), ath5k_desc_free(), ath_descdma_cleanup(), ath_descdma_setup(), atl1e_free_ring_resources(), b44_free_rx_ring(), b44_free_tx_ring(), b44_init_rx_ring(), b44_init_tx_ring(), efx_hunt_free_special_buffer(), ehci_bus_close(), ehci_bus_open(), ehci_ring_alloc(), ehci_ring_free(), ena_create_admin(), ena_create_cq(), ena_create_sq(), ena_destroy_admin(), ena_destroy_cq(), ena_destroy_sq(), exanic_probe(), exanic_remove(), falcon_free_special_buffer(), free_iob(), golan_cmd_init(), golan_cmd_uninit(), golan_create_cq(), golan_create_eq(), golan_create_qp_aux(), golan_destory_eq(), golan_destroy_cq(), golan_destroy_qp(), hermon_alloc(), hermon_create_cq(), hermon_create_eq(), hermon_create_qp(), hermon_destroy_cq(), hermon_destroy_eq(), hermon_destroy_qp(), hermon_free(), hv_alloc_pages(), hv_free_message(), hv_free_pages(), hvm_unmap_hypercall(), icplus_create_ring(), icplus_destroy_ring(), ifec_free(), ifec_net_open(), igbvf_free_rx_resources(), igbvf_free_tx_resources(), intel_destroy_ring(), intelxl_create_ring(), intelxl_destroy_admin(), intelxl_destroy_ring(), jme_free_rx_resources(), jme_free_tx_resources(), linda_create_recv_wq(), linda_destroy_recv_wq(), linda_fini_send(), linda_init_send(), mlx_memory_free_dma_priv(), myri10ge_net_close(), myri10ge_net_open(), myson_create_ring(), myson_destroy_ring(), natsemi_create_ring(), natsemi_destroy_ring(), netfront_create_ring(), netfront_destroy_ring(), nv_free_rxtx_resources(), pcnet32_free_rx_resources(), pcnet32_free_tx_resources(), phantom_close(), phantom_create_rx_ctx(), phantom_create_tx_ctx(), phantom_open(), qib7322_create_recv_wq(), qib7322_destroy_recv_wq(), qib7322_fini_send(), qib7322_init_send(), realtek_create_buffer(), realtek_destroy_buffer(), realtek_destroy_ring(), rhine_destroy_ring(), rtl818x_free_rx_ring(), rtl818x_free_tx_ring(), sis190_free(), skge_free(), sky2_free_rings(), sky2_probe(), sky2_remove(), tg3_free_consistent(), tg3_rx_prodring_fini(), tg3_test_dma(), uhci_bus_close(), uhci_bus_open(), uhci_dequeue(), uhci_enqueue(), uhci_ring_alloc(), uhci_ring_free(), velocity_alloc_rings(), velocity_close(), vmbus_close(), vmbus_open(), vmxnet3_close(), vmxnet3_open(), xhci_context(), xhci_dcbaa_alloc(), xhci_dcbaa_free(), xhci_device_close(), xhci_device_open(), xhci_event_alloc(), xhci_event_free(), xhci_ring_alloc(), xhci_ring_free(), xhci_scratchpad_alloc(), and xhci_scratchpad_free().

                                                       {
        VALGRIND_FREELIKE_BLOCK ( ptr, 0 );
        free_memblock ( ptr, size );
}

Variable Documentation

Total amount of free memory.

Definition at line 94 of file malloc.c.

Referenced by alloc_memblock(), and free_memblock().

Total amount of used memory.

Definition at line 97 of file malloc.c.

Referenced by alloc_memblock(), free_memblock(), and mpopulate().

Maximum amount of used memory.

Definition at line 100 of file malloc.c.

Referenced by alloc_memblock(), and shutdown_cache().