libc/stdlib/nano-malloc.c

/*
 * Copyright (c) 2012, 2013 ARM Ltd
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL ARM LTD BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "nano-malloc.h"

/* List list header of free blocks */
chunk_t *__malloc_free_list;

/* Starting point of memory allocated from system */
char * __malloc_sbrk_start;
char * __malloc_sbrk_top;

/*
 * Algorithm:
 *   Use sbrk() to obtain more memory and ensure the storage is
 *   MALLOC_CHUNK_ALIGN aligned. Optimise for the case that it is
 *   already aligned - only ask for extra padding after we know we
 *   need it
 */
static void *
__malloc_sbrk_aligned(size_t s)
{
    char *p, *align_p;

#ifdef __APPLE__
    /* Mac OS X 'emulates' sbrk, but the
     * parameter is int, not intptr_t or ptrdiff_t,
     */
    int d = (int) s;
    if (d < 0 || (size_t) d != s)
	return (void *)-1;
#else
    intptr_t d = (intptr_t)s;

    if (d < 0)
	return (void *)-1;
#endif
    p = sbrk(d);

    /* sbrk returns -1 if fail to allocate */
    if (p == (void *)-1)
        return p;

    __malloc_sbrk_top = p + s;

    /* Adjust returned space so that the storage area
     * is MALLOC_CHUNK_ALIGN aligned and the head is
     * MALLOC_HEAD_ALIGN aligned.
     */
    align_p = __align_up(p + MALLOC_HEAD, MALLOC_CHUNK_ALIGN) - MALLOC_HEAD;

    if (align_p != p)
    {
        /* p is not aligned, ask for a few more bytes so that we have
         * s bytes reserved from align_p. This should only occur for
         * the first sbrk in a chunk of memory as all others should be
         * aligned to the right value as chunk sizes are selected to
         * make them abut in memory
	 */
	intptr_t adjust = align_p - p;
        char *extra = sbrk(adjust);
        if (extra != p + s)
            return (void *) -1;
	__malloc_sbrk_top = extra + adjust;
    }
    if (__malloc_sbrk_start == NULL)
	__malloc_sbrk_start = align_p;

    return align_p;
}

bool
__malloc_grow_chunk(chunk_t *c, size_t new_size)
{
    char *chunk_e = chunk_end(c);

    if (chunk_e != __malloc_sbrk_top)
	return false;
    size_t add_size = MAX(MALLOC_MINSIZE, new_size - _size(c));

    /* Ask for the extra memory needed */
    char *heap = __malloc_sbrk_aligned(add_size);

    /* Check if we got what we wanted */
    if (heap == chunk_e)
    {
	/* Set size and return */
	*_size_ref(c) += add_size;
	return true;
    }

    if (heap != (char *) -1)
    {
	/* sbrk returned unexpected memory, free it */
	make_free_chunk((chunk_t *) (heap + MALLOC_HEAD), add_size);
    }
    return false;
}

/** Function malloc
  * Algorithm:
  *   Walk through the free list to find the first match. If fails to find
  *   one, call sbrk to allocate a new chunk_t.
  */
void *
malloc(size_t s)
{
    chunk_t **p, *r;
    char * ptr;
    size_t alloc_size;

    if (s > MALLOC_MAXSIZE)
    {
        errno = ENOMEM;
        return NULL;
    }

    alloc_size = chunk_size(s);

    MALLOC_LOCK;

    for (p = &__malloc_free_list; (r = *p) != NULL; p = &r->next)
    {
        if (_size(r) >= alloc_size)
        {
	    size_t rem = _size(r) - alloc_size;

            if (rem >= MALLOC_MINSIZE)
            {
                /* Find a chunk_t that much larger than required size, break
		 * it into two chunks and return the first one
		 */

		chunk_t *s = (chunk_t *)((char *)r + alloc_size);
                _set_size(s, rem);
		s->next = r->next;
		*p = s;

                _set_size(r, alloc_size);
            }
	    else
	    {
		/* Find a chunk_t that is exactly the size or slightly bigger
		 * than requested size, just return this chunk_t
		 */
		*p = r->next;
	    }
            break;
        }
	if (!r->next && __malloc_grow_chunk(r, alloc_size))
	{
	    /* Grow the last chunk in memory to the requested size,
	     * just return it
	     */
	    *p = r->next;
	    break;
	}
    }

    /* Failed to find a appropriate chunk_t. Ask for more memory */
    if (r == NULL)
    {
        void *blob = __malloc_sbrk_aligned(alloc_size);

        /* sbrk returns -1 if fail to allocate */
        if (blob == (void *)-1)
        {
            errno = ENOMEM;
            MALLOC_UNLOCK;
            return NULL;
        }
        r = blob_to_chunk(blob);
        _set_size(r, alloc_size);
    }

    MALLOC_UNLOCK;

    ptr = chunk_to_ptr(r);

    memset(ptr, '\0', alloc_size - MALLOC_HEAD);

    return ptr;
}

#ifdef _HAVE_ALIAS_ATTRIBUTE
#ifndef __clang__
#pragma GCC diagnostic ignored "-Wmissing-attributes"
#endif
__strong_reference(malloc, __malloc_malloc);
#endif

#if MALLOC_DEBUG

#include <assert.h>

void
__malloc_validate_block(chunk_t *r)
{
    assert (__align_up(chunk_to_ptr(r), MALLOC_CHUNK_ALIGN) == chunk_to_ptr(r));
    assert (__align_up(r, MALLOC_HEAD_ALIGN) == r);
    assert (_size(r) >= MALLOC_MINSIZE);
    assert (_size(r) < 0x80000000UL);
    assert (__align_up(_size(r), MALLOC_HEAD_ALIGN) == _size(r));
}

void
__malloc_validate(void)
{
    chunk_t *r;

    for (r = __malloc_free_list; r; r = r->next) {
	__malloc_validate_block(r);
	assert (r->next == NULL || (char *) r + _size(r) <= (char *) r->next);
    }
}

#endif