malloc.c File Reference

Dynamic memory allocation. More...

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>
#include <gpxe/io.h>
#include <gpxe/list.h>
#include <gpxe/init.h>
#include <gpxe/malloc.h>

Go to the source code of this file.

Data Structures
struct	memory_block
	A free block of memory. More...
struct	autosized_block
	A block of allocated memory complete with size information. More...
Defines
#define	MIN_MEMBLOCK_SIZE   ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )
#define	NOWHERE   ( ( void * ) ~( ( intptr_t ) 0 ) )
	Address for zero-length memory blocks.
#define	HEAP_SIZE   ( 128 * 1024 )
	Heap size.
Functions
	FILE_LICENCE (GPL2_OR_LATER)
static	LIST_HEAD (free_blocks)
	List of free memory blocks.
void *	alloc_memblock (size_t size, size_t align)
	Allocate a memory block.
void	free_memblock (void *ptr, size_t size)
	Free a memory block.
void *	realloc (void *old_ptr, size_t new_size)
	Reallocate memory.
void *	malloc (size_t size)
	Allocate memory.
void	free (void *ptr)
	Free memory.
void *	zalloc (size_t size)
	Allocate cleared memory.
void	mpopulate (void *start, size_t len)
	Add memory to allocation pool.
static void	init_heap (void)
	Initialise the heap.
struct init_fn heap_init_fn	__init_fn (INIT_EARLY)
	Memory allocator initialisation function.
Variables
size_t	freemem
	Total amount of free memory.
static char	heap [HEAP_SIZE]
	The heap itself.

---

Detailed Description

Dynamic memory allocation.

Definition in file malloc.c.

---

Define Documentation

#define MIN_MEMBLOCK_SIZE   ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )

Definition at line 44 of file malloc.c.

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

#define NOWHERE   ( ( void * ) ~( ( intptr_t ) 0 ) )

Address for zero-length memory blocks.

malloc(0) or realloc(ptr,0) will return the special value NOWHERE. Calling free(NOWHERE) will have no effect.

This is consistent with the ANSI C standards, which state that "either NULL or a pointer suitable to be passed to free()" must be returned in these cases. Using a special non-NULL value means that the caller can take a NULL return value to indicate failure, without first having to check for a requested size of zero.

Code outside of malloc.c do not ever need to refer to the actual value of NOWHERE; this is an internal definition.

Definition at line 70 of file malloc.c.

Referenced by realloc().

#define HEAP_SIZE   ( 128 * 1024 )

Heap size.

Currently fixed at 128kB.

Definition at line 83 of file malloc.c.

---

Function Documentation

FILE_LICENCE

(

GPL2_OR_LATER

)

static LIST_HEAD

(

free_blocks

)

[static]

List of free memory blocks.

void* alloc_memblock	(	size_t	size,
		size_t	align
	)

Allocate a memory block.

Parameters:

	size	Requested size
	align	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 100 of file malloc.c.

References DBG, freemem, memory_block::list, list_add, list_del, list_for_each_entry, MIN_MEMBLOCK_SIZE, NULL, memory_block::size, and virt_to_phys().

Referenced by malloc_dma(), mtnic_alloc_aligned(), and realloc().

                                                    {
        struct memory_block *block;
        size_t align_mask;
        size_t pre_size;
        ssize_t post_size;
        struct memory_block *pre;
        struct memory_block *post;

        /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
         * calculate alignment mask.
         */
        size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
        align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );

        DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );

        /* Search through blocks for the first one with enough space */
        list_for_each_entry ( block, &free_blocks, list ) {
                pre_size = ( - virt_to_phys ( block ) ) & align_mask;
                post_size = block->size - pre_size - size;
                if ( post_size >= 0 ) {
                        /* 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 ) + size     );
                        DBG ( "[%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 ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
                                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 );
                        /* Update total free memory */
                        freemem -= size;
                        /* Return allocated block */
                        DBG ( "Allocated [%p,%p)\n", block,
                              ( ( ( void * ) block ) + size ) );
                        return block;
                }
        }

        DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
        return NULL;
}

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 174 of file malloc.c.

References DBG, freemem, memory_block::list, list_add_tail, list_del, list_for_each_entry, MIN_MEMBLOCK_SIZE, and memory_block::size.

Referenced by free_dma(), mpopulate(), mtnic_alloc_cq(), mtnic_alloc_resources(), mtnic_alloc_ring(), mtnic_close(), mtnic_disable(), mtnic_init_card(), mtnic_open(), and realloc().

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

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

        /* Round up size to match actual size that alloc_memblock()
         * would have used.
         */
        size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
        freeing = ptr;
        freeing->size = size;
        DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));

        /* Insert/merge into free list */
        list_for_each_entry ( block, &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 ) {
                        DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
                              ( ( ( void * ) block ) + block->size ), freeing,
                              ( ( ( void * ) freeing ) + freeing->size ),block,
                              ( ( ( void * ) freeing ) + freeing->size ) );
                        block->size += size;
                        list_del ( &block->list );
                        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.
         */
        DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
        list_add_tail ( &freeing->list, &block->list );
        if ( gap_after == 0 ) {
                DBG ( "[%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 );
        }

        /* Update free memory counter */
        freemem += size;
}

void* realloc	(	void *	old_ptr,
		size_t	new_size
	)

Reallocate memory.

Parameters:

	old_ptr	Memory previously allocated by malloc(), or NULL
	new_size	Requested size

Return values:

new_ptr

Allocated memory, or NULL

Allocates memory with no particular alignment requirement. new_ptr will be aligned to at least a multiple of sizeof(void*). If old_ptr is non-NULL, then the contents of the newly allocated memory will be the same as the contents of the previously allocated memory, up to the minimum of the old and new sizes. The old memory will be freed.

If allocation fails the previously allocated block is left untouched and NULL is returned.

Calling realloc() with a new size of zero is a valid way to free a memory block.

Definition at line 253 of file malloc.c.

References alloc_memblock(), container_of, autosized_block::data, free_memblock(), memcpy, NOWHERE, NULL, offsetof, and autosized_block::size.

Referenced by bitmap_resize(), free(), line_buffer(), malloc(), more_comps(), and resize_dhcp_option().

                                                  {
        struct autosized_block *old_block;
        struct autosized_block *new_block;
        size_t old_total_size;
        size_t new_total_size;
        size_t old_size;
        void *new_ptr = NOWHERE;

        /* Allocate new memory if necessary.  If allocation fails,
         * return without touching the old block.
         */
        if ( new_size ) {
                new_total_size = ( new_size +
                                   offsetof ( struct autosized_block, data ) );
                new_block = alloc_memblock ( new_total_size, 1 );
                if ( ! new_block )
                        return NULL;
                new_block->size = new_total_size;
                new_ptr = &new_block->data;
        }
        
        /* Copy across relevant part of the old data region (if any),
         * then free it.  Note that at this point either (a) new_ptr
         * is valid, or (b) new_size is 0; either way, the memcpy() is
         * valid.
         */
        if ( old_ptr && ( old_ptr != NOWHERE ) ) {
                old_block = container_of ( old_ptr, struct autosized_block,
                                           data );
                old_total_size = old_block->size;
                old_size = ( old_total_size -
                             offsetof ( struct autosized_block, data ) );
                memcpy ( new_ptr, old_ptr,
                         ( ( old_size < new_size ) ? old_size : new_size ) );
                free_memblock ( old_block, old_total_size );
        }

        return new_ptr;
}

void* malloc

(

size_t

size

)

Allocate memory.

Parameters:

size

Requested size

Return values:

ptr

Memory, or NULL

Allocates memory with no particular alignment requirement. ptr will be aligned to at least a multiple of sizeof(void*).

Definition at line 302 of file malloc.c.

References NULL, and realloc().

Referenced by add_ipv4_miniroute(), add_ipv6_miniroute(), add_tls(), aes_unwrap(), aes_wrap(), alloc(), apply_iscsi_string_setting(), ath5k_hw_rfregs_init(), bi_mod_power(), chap_init(), derwin(), dupwin(), eisabus_probe(), fetch_string_setting_copy(), ipv4_reassemble(), isabus_probe(), isapnpbus_probe(), iscsi_rx_buffered_data(), mcabus_probe(), net80211_probe_start(), net80211_register(), newwin(), pcibus_probe(), register_nvo(), RSA_decrypt(), rtl_open(), strndup(), subwin(), t509bus_probe(), tls_assemble_block(), tls_assemble_stream(), tls_new_ciphertext(), tls_newdata_process_header(), tls_set_cipher(), vasprintf(), wpa_make_rsn_ie(), wpa_start(), x509_rsa_public_key(), and zalloc().

                              {
        return realloc ( NULL, size );
}

void free

(

void *

ptr

)

Free memory.

Parameters:

ptr

Memory allocated by malloc(), or NULL

Memory allocated with malloc_dma() cannot be freed with free(); it must be freed with free_dma() instead.

If ptr is NULL, no action is taken.

Definition at line 316 of file malloc.c.

References realloc().

Referenced by aes_unwrap(), aes_wrap(), aoe_free(), aoeboot(), apply_iscsi_string_setting(), arbel_create_cq(), arbel_create_qp(), arbel_destroy_cq(), arbel_destroy_qp(), arbel_probe(), arbel_remove(), ath5k_desc_free(), ath5k_eeprom_free_pcal_info(), ath5k_hw_attach(), ath5k_hw_detach(), ath5k_probe(), ath5k_remove(), atl1e_free_ring_resources(), bi_mod_power(), bi_terminate(), bitmap_free(), chap_finish(), del_ipv4_miniroute(), del_ipv6_miniroute(), delwin(), dhcp_free(), dns_resolv(), downloader_free(), efi_snp_driver_start(), efi_snp_driver_stop(), eisabus_probe(), eisabus_remove(), empty_line_buffer(), expand_command(), free_fragbuf(), free_image(), free_netdev(), free_tls(), ftp_free(), generic_settings_clear(), generic_settings_store(), hermon_create_cq(), hermon_create_qp(), hermon_destroy_cq(), hermon_destroy_qp(), hermon_probe(), hermon_remove(), http_free(), ib_create_conn(), ib_create_cq(), ib_create_mi(), ib_create_path(), ib_create_qp(), ib_destroy_conn(), ib_destroy_cq(), ib_destroy_madx(), ib_destroy_mi(), ib_destroy_path(), ib_destroy_qp(), ib_mcast_attach(), ib_mcast_detach(), ib_srpboot(), image_set_cmdline(), isabus_probe(), isabus_remove(), isapnpbus_probe(), isapnpbus_remove(), iscsi_free(), iscsi_handle_targetaddress_value(), iscsi_rx_buffered_data_done(), iscsiboot(), linda_create_send_wq(), linda_destroy_send_wq(), mcabus_probe(), mcabus_remove(), mtnic_disable(), mtnic_probe(), net80211_autoassociate(), net80211_free(), net80211_free_wlan(), net80211_free_wlanlist(), net80211_mgmt_dequeue(), net80211_netdev_close(), net80211_prepare_assoc(), net80211_probe_finish_all(), net80211_probe_finish_best(), net80211_step_associate(), pcibus_probe(), pcibus_remove(), posix_file_free(), pxe_menu_boot(), rc80211_free(), ref_put(), register_nvo(), resolve_uri(), RSA_decrypt(), RSA_free(), rtl818x_probe(), rtl_close(), sec80211_install(), shell(), sis190_free_phy(), skge_free(), skge_probe(), skge_remove(), sky2_free_rings(), sky2_probe(), sky2_remove(), slam_free(), system(), t509bus_probe(), t509bus_remove(), tftp_free(), tls_clear_cipher(), tls_new_ciphertext(), tls_newdata_process_data(), tls_send_plaintext(), undipci_probe(), undipci_remove(), undirom_probe(), unregister_nvo(), vxge_hw_device_terminate(), wpa_stop(), and x509_free_rsa_public_key().

                        {
        realloc ( ptr, 0 );
}

void* zalloc

(

size_t

size

)

Allocate cleared memory.

Parameters:

size

Requested size

Return values:

ptr

Allocated memory

Allocate memory as per malloc(), and zero it.

This function name is non-standard, but pretty intuitive. zalloc(size) is always equivalent to calloc(1,size)

Definition at line 331 of file malloc.c.

References autosized_block::data, malloc(), and memset().

Referenced by alloc_ibdev(), alloc_image(), alloc_netdev(), aoe_attach(), aoeboot(), arbel_create_cq(), arbel_create_qp(), arbel_probe(), ath5k_hw_attach(), ath5k_probe(), atl1e_setup_ring_resources(), autovivify_child_settings(), calloc(), create_downloader(), dhcp_deliver_iob(), dns_resolv(), efi_snp_driver_start(), ftp_open(), generic_settings_store(), hermon_create_cq(), hermon_create_qp(), hermon_probe(), http_open_filter(), hw_open(), ib_cmrc_open(), ib_create_conn(), ib_create_cq(), ib_create_madx(), ib_create_mi(), ib_create_path(), ib_create_qp(), ib_mcast_attach(), ib_srpboot(), iscsi_attach(), iscsiboot(), linda_create_send_wq(), mtnic_probe(), net80211_handle_mgmt(), net80211_prepare_assoc(), net80211_probe_start(), net80211_probe_step(), net80211_step_associate(), numeric_resolv(), open(), parse_uri(), pxe_menu_parse(), rc80211_init(), resolv(), rtl818x_probe(), sec80211_install(), sis190_mii_probe(), skge_probe(), skge_ring_alloc(), sky2_probe(), sky2_up(), slam_open(), srp_attach(), start_dhcp(), start_pxebs(), store_cached_dhcpack(), tcp_open(), tftp_core_open(), udp_open_common(), undipci_probe(), undirom_probe(), vxge_hw_device_initialize(), and xfer_open_named_socket().

                              {
        void *data;

        data = malloc ( size );
        if ( data )
                memset ( data, 0, size );
        return data;
}

void mpopulate	(	void *	start,
		size_t	len
	)

Add memory to allocation pool.

Parameters:

	start	Start address
	end	End 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 351 of file malloc.c.

References free_memblock(), and MIN_MEMBLOCK_SIZE.

Referenced by init_heap().

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

static void init_heap

(

void

)

[static]

Initialise the heap.

Definition at line 362 of file malloc.c.

References heap, and mpopulate().

                               {
        mpopulate ( heap, sizeof ( heap ) );
}

struct init_fn heap_init_fn __init_fn

(

INIT_EARLY

)

[read]

Memory allocator initialisation function.

---

Variable Documentation

size_t freemem

Total amount of free memory.

Definition at line 76 of file malloc.c.

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

char heap[HEAP_SIZE] [static]

The heap itself.

Definition at line 86 of file malloc.c.

Referenced by init_heap().