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...

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

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. More...
void	free_memblock (void *ptr, size_t size)
	Free a memory block. More...
void	mdumpfree (void)
	Dump free block list (for debugging) More...
static void *__malloc	malloc_phys_offset (size_t size, size_t phys_align, size_t offset)
	Allocate memory with specified physical alignment and offset. More...
static void *__malloc	malloc_phys (size_t size, size_t phys_align)
	Allocate memory with specified physical alignment. More...
static void	free_phys (void *ptr, size_t size)
	Free memory allocated with malloc_phys() More...

Variables
size_t	freemem
	Total amount of free memory. More...
size_t	usedmem
	Total amount of used memory. More...
size_t	maxusedmem
	Maximum amount of used memory. More...
struct cache_discarder	__attribute__

Detailed Description

Dynamic memory allocation.

Definition in file malloc.h.

Macro Definition Documentation

CACHE_DISCARDERS

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

Cache discarder table.

Definition at line 92 of file malloc.h.

__cache_discarder

#define __cache_discarder

(

cost

)

__table_entry ( CACHE_DISCARDERS, cost )

Declare a cache discarder.

Definition at line 95 of file malloc.h.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

alloc_memblock()

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

Allocate a memory block.

Parameters

size	Requested size
align	Physical alignment
offset	Offset from physical alignment

Return values

ptr	Memory 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 284 of file malloc.c.

                                                                   {
        struct memory_block *block;
        size_t actual_offset;
        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();

        /* Calculate offset of memory block */
        actual_offset = ( offset & ~( MEMBLOCK_ALIGN - 1 ) );
        assert ( actual_offset <= offset );

        /* Calculate size of memory block */
        actual_size = ( ( size + offset - actual_offset + MEMBLOCK_ALIGN - 1 )
                        & ~( MEMBLOCK_ALIGN - 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 );

        /* Calculate alignment mask */
        align_mask = ( ( align - 1 ) | ( MEMBLOCK_ALIGN - 1 ) );

        DBGC2 ( &heap, "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 = ( ( actual_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, "HEAP splitting [%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.
                         */
                        if ( post_size ) {
                                assert ( post_size >= MEMBLOCK_ALIGN );
                                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.
                         */
                        if ( ! pre_size ) {
                                list_del ( &pre->list );
                                VALGRIND_MAKE_MEM_NOACCESS ( pre,
                                                             sizeof ( *pre ) );
                        } else {
                                assert ( pre_size >= MEMBLOCK_ALIGN );
                        }
                        /* Update memory usage statistics */
                        freemem -= actual_size;
                        usedmem += actual_size;
                        if ( usedmem > maxusedmem )
                                maxusedmem = usedmem;
                        /* Return allocated block */
                        ptr = ( ( ( void * ) block ) + offset - actual_offset );
                        DBGC2 ( &heap, "HEAP allocated [%p,%p) within "
                                "[%p,%p)\n", ptr, ( ptr + size ), block,
                                ( ( ( void * ) block ) + actual_size ) );
                        VALGRIND_MAKE_MEM_UNDEFINED ( ptr, size );
                        goto done;
                }

                /* Try discarding some cached data to free up memory */
                DBGC ( &heap, "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, "HEAP failed to allocate %#zx (aligned "
                               "%#zx)\n", size, align );
                        ptr = NULL;
                        goto done;
                }
        }

 done:
        check_blocks();
        valgrind_make_blocks_noaccess();
        return ptr;
}

References align, assert(), block, check_blocks(), DBGC, DBGC2, discard_cache(), done, freemem, heap, memory_block::list, list_add, list_del, list_for_each_entry, maxusedmem, MEMBLOCK_ALIGN, NULL, offset, size, 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_phys_offset(), and realloc().

free_memblock()

void free_memblock	(	void *	ptr,
		size_t	size
	)

Free a memory block.

Parameters

ptr	Memory allocated by alloc_memblock(), or NULL
size	Size of the memory

If ptr is NULL, no action is taken.

Definition at line 416 of file malloc.c.

                                              {
        struct memory_block *freeing;
        struct memory_block *block;
        struct memory_block *tmp;
        size_t sub_offset;
        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 to match actual block that alloc_memblock() would
         * have allocated.
         */
        assert ( size != 0 );
        sub_offset = ( virt_to_phys ( ptr ) & ( MEMBLOCK_ALIGN - 1) );
        freeing = ( ptr - sub_offset );
        actual_size = ( ( size + sub_offset + MEMBLOCK_ALIGN - 1 ) &
                        ~( MEMBLOCK_ALIGN - 1 ) );
        DBGC2 ( &heap, "HEAP freeing [%p,%p) within [%p,%p)\n",
                ptr, ( ptr + size ), freeing,
                ( ( ( void * ) freeing ) + actual_size ) );
        VALGRIND_MAKE_MEM_UNDEFINED ( freeing, sizeof ( *freeing ) );

        /* 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, "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, "HEAP merging [%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, "HEAP freed [%p,%p)\n",
                freeing, ( ( ( void * ) freeing ) + freeing->size ) );
        list_add_tail ( &freeing->list, &block->list );
        if ( gap_after == 0 ) {
                DBGC2 ( &heap, "HEAP merging [%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();
}

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

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

mdumpfree()

void mdumpfree

(

void

)

Dump free block list (for debugging)

Definition at line 718 of file malloc.c.

                        {
        struct memory_block *block;

        dbg_printf ( "HEAP free block list:\n" );
        list_for_each_entry ( block, &free_blocks, list ) {
                dbg_printf ( "...[%p,%p] (size %#zx)\n", block,
                             ( ( ( void * ) block ) + block->size ),
                             block->size );
        }
}

References block, dbg_printf(), memory_block::list, and list_for_each_entry.

malloc_phys_offset()

static void* __malloc malloc_phys_offset ( size_t  size, size_t  phys_align, size_t  offset  )

inlinestatic

Allocate memory with specified physical alignment and offset.

Parameters

size	Requested size
align	Physical alignment
offset	Offset from physical alignment

Return values

ptr	Memory, or NULL

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

Definition at line 43 of file malloc.h.

                                                                   {
        void * ptr = alloc_memblock ( size, phys_align, offset );
        if ( ptr && size )
                VALGRIND_MALLOCLIKE_BLOCK ( ptr, size, 0, 0 );
        return ptr;
}

References alloc_memblock(), offset, size, and VALGRIND_MALLOCLIKE_BLOCK.

Referenced by alloc_iob_raw(), and malloc_phys().

malloc_phys()

static void* __malloc malloc_phys ( size_t  size, size_t  phys_align  )

inlinestatic

Allocate memory with specified physical alignment.

Parameters

size	Requested size
align	Physical alignment

Return values

ptr	Memory, or NULL

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

Definition at line 61 of file malloc.h.

                                                                             {
        return malloc_phys_offset ( size, phys_align, 0 );
}

References malloc_phys_offset(), and size.

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(), bnxt_alloc_mem(), efx_hunt_alloc_special_buffer(), ehci_bus_open(), ehci_ring_alloc(), ena_create_admin(), ena_create_async(), ena_create_cq(), ena_create_sq(), ena_probe(), 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(), 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(), 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(), and vmxnet3_open().

free_phys()

static void free_phys ( void *  ptr, size_t  size  )

inlinestatic

Free memory allocated with malloc_phys()

Parameters

ptr	Memory allocated by malloc_phys(), or NULL
size	Size of memory, as passed to malloc_phys()

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

If ptr is NULL, no action is taken.

Definition at line 76 of file malloc.h.

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

References free_memblock(), size, 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(), bnxt_free_mem(), efx_hunt_free_special_buffer(), ehci_bus_close(), ehci_bus_open(), ehci_ring_alloc(), ehci_ring_free(), ena_create_admin(), ena_create_async(), ena_create_cq(), ena_create_sq(), ena_destroy_admin(), ena_destroy_async(), ena_destroy_cq(), ena_destroy_sq(), ena_probe(), ena_remove(), 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(), 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(), 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(), and vmxnet3_open().

Variable Documentation

freemem

size_t freemem

Total amount of free memory.

Definition at line 95 of file malloc.c.

Referenced by alloc_memblock(), and free_memblock().

usedmem

size_t usedmem

Total amount of used memory.

Definition at line 98 of file malloc.c.

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

maxusedmem

size_t maxusedmem

Maximum amount of used memory.

Definition at line 101 of file malloc.c.

Referenced by alloc_memblock(), and shutdown_cache().

__attribute__

struct cache_discarder __attribute__