heap.c

rtai-3.1-test3的源代码(Real-Time Application Interface )

/*!\file heap.c
 * \brief Dynamic memory allocation services.
 * \author Philippe Gerum
 *
 * Copyright (C) 2001,2002,2003 Philippe Gerum <[e-mail]>.
 *
 * Xenomai is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Xenomai is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Xenomai; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * As a special exception, the RTAI project gives permission
 * for additional uses of the text contained in its release of
 * Xenomai.
 *
 * The exception is that, if you link the Xenomai libraries with other
 * files to produce an executable, this does not by itself cause the
 * resulting executable to be covered by the GNU General Public License.
 * Your use of that executable is in no way restricted on account of
 * linking the Xenomai libraries code into it.
 *
 * This exception does not however invalidate any other reasons why
 * the executable file might be covered by the GNU General Public
 * License.
 *
 * This exception applies only to the code released by the
 * RTAI project under the name Xenomai.  If you copy code from other
 * RTAI project releases into a copy of Xenomai, as the General Public
 * License permits, the exception does not apply to the code that you
 * add in this way.  To avoid misleading anyone as to the status of
 * such modified files, you must delete this exception notice from
 * them.
 *
 * If you write modifications of your own for Xenomai, it is your
 * choice whether to permit this exception to apply to your
 * modifications. If you do not wish that, delete this exception
 * notice.
 *
 * \ingroup heap
 */

/*!
 * \ingroup xenomai
 * \defgroup heap Dynamic memory allocation services.
 *
 * Dynamic memory allocation services.
 *
 * Implements the nanokernel memory allocator based on the algorithm described
 * in "Design of a General Purpose Memory  Allocator for the 4.3BSD Unix Kernel"
 * by Marshall K. McKusick and  Michael J. Karels.
 *
 *@{*/

#define XENO_HEAP_MODULE

#include <xenomai/pod.h>
#include <xenomai/mutex.h>
#include <xenomai/thread.h>
#include <xenomai/heap.h>

/*
 * Description: Implements the nanokernel memory allocator based
 * on the algorithm described in "Design of a General Purpose Memory
 * Allocator for the 4.3BSD Unix Kernel" by Marshall K. McKusick and
 * Michael J. Karels.
 */

xnheap_t kheap;			/* System heap */

static void init_extent (xnheap_t *heap,
			 xnextent_t *extent)
{
    caddr_t freepage;
    int n, lastpgnum;

    inith(&extent->link);

    /* The page area starts right after the (aligned) header. */
    extent->membase = (caddr_t)extent + heap->hdrsize;
    lastpgnum = heap->npages - 1;

    /* Mark each page as free in the page map. */
    for (n = 0, freepage = extent->membase;
	 n < lastpgnum; n++, freepage += heap->pagesize)
	{
	*((caddr_t *)freepage) = freepage + heap->pagesize;
	extent->pagemap[n] = XNHEAP_PFREE;
	}

    *((caddr_t *)freepage) = NULL;
    extent->pagemap[lastpgnum] = XNHEAP_PFREE;
    extent->memlim = freepage + heap->pagesize;

    /* The first page starts the free list of a new extent. */
    extent->freelist = extent->membase;
}

/*! 
 * \fn int xnheap_init(xnheap_t *heap,
                       void *heapaddr,
		       u_long heapsize,
		       u_long pagesize);
 * \brief Initialize a memory heap.
 *
 * Initializes a memory heap suitable for dynamic memory allocation
 * requests.  The heap manager can operate in two modes, whether
 * time-bounded if the heap storage area and size are statically
 * defined at initialization time, or dynamically extendable at the
 * expense of a less deterministic behaviour.
 *
 * @param heap The address of a heap descriptor Xenomai will use to
 * store the allocation data.  This descriptor must always be valid
 * while the heap is active therefore it must be allocated in
 * permanent memory.
 *
 * @param heapaddr The address of a statically-defined heap storage
 * area. If this parameter is non-zero, all allocations will be made
 * from the given area in fully time-bounded mode. In such a case, the
 * heap is non-extendable. If a null address is passed, the heap
 * manager will attempt to extend the heap each time a memory
 * starvation is encountered. In the latter case, the heap manager
 * will request additional chunks of core memory to the host operating
 * environment when needed, voiding the real-time guarantee for the
 * caller.
 *
 * @param heapsize If heapaddr is non-zero, heapsize gives the size in
 * bytes of the statically-defined storage area. Otherwise, heapsize
 * defines the standard length of each extent that will be requested
 * to the host operating environment when a memory starvation is
 * encountered for the heap.  heapsize must be a multiple of pagesize
 * and lower than 16 Mbytes. Depending on the host environment,
 * requests for extent memory might be limited in size. For instance,
 * heapsize must be lower than 128Kb for kmalloc()-based allocations
 * used in Linux. In the current implementation, heapsize must be
 * large enough to contain an internal header. The following formula
 * gives the size of this header: hdrsize = (sizeof(xnextent_t) +
 * ((heapsize - sizeof(xnextent_t))) / (pagesize + 1) + 15) & ~15;
 *
 * @param pagesize The size in bytes of the fundamental memory page
 * which will be used to subdivide the heap internally. Choosing the
 * right page size is important regarding performance and memory
 * fragmentation issues, so it might be a good idea to take a look at
 * http://docs.FreeBSD.org/44doc/papers/kernmalloc.pdf to pick the
 * best one for your needs. In the current implementation, pagesize
 * must be a power of two in the range [ 8 .. 32768] inclusive.
 *
 * @return XN_OK is returned upon success, or one of the following
 * error codes:
 * - XNERR_PARAM is returned whenever a parameter is invalid.
 * - XNERR_NOMEM is returned if no initial extent can be allocated
 * for a dynamically extendable heap (i.e. heapaddr == NULL).
 *
 * Side-effect: This routine does not call the rescheduling procedure.
 *
 * Context: This routine must be called on behalf of a thread context.
 */

int xnheap_init (xnheap_t *heap,
		 void *heapaddr,
		 u_long heapsize,
		 u_long pagesize)
{
    u_long hdrsize, pmapsize, shiftsize, pageshift;
    xnextent_t *extent;
    int n;

    /*
     * Perform some parametrical checks first.
     * Constraints are:
     * PAGESIZE must be >= 2 ** MINLOG2.
     * PAGESIZE must be <= 2 ** MAXLOG2.
     * PAGESIZE must be a power of 2.
     * HEAPSIZE must be large enough to contain the static part of an
     * extent header.
     * HEAPSIZE must be a multiple of PAGESIZE.
     * HEAPSIZE must be lower than XNHEAP_MAXEXTSZ.
     */

    if ((pagesize < (1 << XNHEAP_MINLOG2)) ||
	(pagesize > (1 << XNHEAP_MAXLOG2)) ||
	(pagesize & (pagesize - 1)) != 0 ||
	heapsize <= sizeof(xnextent_t) ||
	heapsize > XNHEAP_MAXEXTSZ ||
	(heapsize & (pagesize - 1)) != 0)
	return XNERR_PARAM;

    /* Determine the page map overhead inside the given extent
       size. We need to reserve a byte in a page map for each page
       which is addressable into this extent. The page map is itself
       stored in the extent space, right after the static part of its
       header, and before the first allocatable page. */
    pmapsize = ((heapsize - sizeof(xnextent_t)) * sizeof(u_char)) / (pagesize + sizeof(u_char));

    /* The overall header size is: static_part + page_map rounded to
       the minimum alignment size. */
    hdrsize = (sizeof(xnextent_t) + pmapsize + XNHEAP_MINALIGNSZ - 1) & ~(XNHEAP_MINALIGNSZ - 1);

    /* An extent must contain at least two addressable pages to cope
       with allocation sizes between pagesize and 2 * pagesize. */
    if (hdrsize + 2 * pagesize > heapsize)
	return XNERR_PARAM;

    /* Compute the page shiftmask from the page size (i.e. log2 value). */
    for (pageshift = 0, shiftsize = pagesize;
	 shiftsize > 1; shiftsize >>= 1, pageshift++)
	; /* Loop */

    heap->flags = 0;
    heap->pagesize = pagesize;
    heap->pageshift = pageshift;
    heap->extentsize = heapsize;
    heap->hdrsize = hdrsize;
    heap->npages = (heapsize - hdrsize) >> pageshift;
    heap->ubytes = 0;
    heap->maxcont = heap->npages*pagesize;
    initq(&heap->extents);
    xnmutex_init(&heap->mutex);

    for (n = 0; n < XNHEAP_NBUCKETS; n++)
	heap->buckets[n] = NULL;

    if (!heapaddr)
	{
	/* NULL initial heap address means that we should obtain it
	   from the architecture-dependent allocation service. This
	   also means that this heap is extendable by requesting
	   additional extents to the very same service upon memory
	   starvation. */

	xnpod_check_context(XNPOD_THREAD_CONTEXT);

	/* When called on behalf of xnpod_init(), there is no running
	   thread. Running on behalf of the initialization context or
	   the root thread context means that we can use the
	   arch-dependent allocation service synchronously. */
	   
	extent = (xnextent_t *)xnarch_sysalloc(heapsize);

	if (!extent)
	    return XNERR_NOMEM;

	setbits(heap->flags,XNHEAP_EXTENDABLE);
	}
    else
	extent = (xnextent_t *)heapaddr;

    init_extent(heap,extent);

    appendq(&heap->extents,&extent->link);

    xnarch_init_display_context(heap);

    return XN_OK;
}

/*! 
 * \fn void xnheap_destroy(xnheap_t *heap);
 * \brief Destroys a memory heap.
 *
 * Destroys a memory heap. Dynamically allocated extents are returned
 * to the host operating environment.
 *
 * @param heap The descriptor address of the destroyed heap.
 *
 * Side-effect: This routine does not call the rescheduling procedure.
 *
 * Context: This routine must be called on behalf of a thread context.
 */

void xnheap_destroy (xnheap_t *heap)

{
    xnholder_t *holder;

    if (!testbits(heap->flags,XNHEAP_EXTENDABLE))
	return;

    /* If the heap is marked as extendable, we have to release each
       allocated extent back to the arch-dependent allocator. */

    xnpod_check_context(XNPOD_THREAD_CONTEXT);

    while ((holder = getq(&heap->extents)) != NULL)
	xnarch_sysfree(link2extent(holder),heap->extentsize);
}

/*
 * get_free_range() -- Obtain a range of contiguous free pages to
 * fulfill an allocation of 2 ** log2size. Each extent is searched,
 * and a new one is allocated if needed, provided the heap is
 * extendable. Must be called with the heap mutex locked.
 */

static caddr_t get_free_range (xnheap_t *heap,
			       u_long bsize,
			       int log2size,
			       int flags)
{
    caddr_t block, eblock, freepage, lastpage, headpage, freehead = NULL;
    u_long pagenum, pagecont, freecont;
    xnholder_t *holder;
    xnextent_t *extent;

    holder = getheadq(&heap->extents);

    while (holder != NULL)
	{
	extent = link2extent(holder);

searchrange:

	freepage = extent->freelist;

	while (freepage != NULL)
	    {
	    headpage = freepage;
    	    freecont = 0;

	    /* Search for a range of contiguous pages in the free page
	       list of the current extent. The range must be 'bsize'
	       long. */
	    do
		{
		lastpage = freepage;
		freepage = *((caddr_t *)freepage);
		freecont += heap->pagesize;
		}
	    while (freepage == lastpage + heap->pagesize && freecont < bsize);

	    if (freecont >= bsize)
		{
		/* Ok, got it. Just update the extent's free page
		   list, then proceed to the next step. */

		if (headpage == extent->freelist)
		    extent->freelist = *((caddr_t *)lastpage);
		else   
		    *((caddr_t *)freehead) = *((caddr_t *)lastpage);

		goto splitpage;
		}

	    freehead = lastpage;
	    }

	holder = nextq(&heap->extents,holder);