heap.c

DirectFB-1.0.1可用于linux的嵌入式GUI

/*
   (c) Copyright 2001-2007  The DirectFB Organization (directfb.org)
   (c) Copyright 2000-2004  Convergence (integrated media) GmbH

   All rights reserved.

   Written by Denis Oliver Kropp <[e-mail]>,
              Andreas Hundt <[e-mail]>,
              Sven Neumann <[e-mail]>,
              Ville Syrjälä <[e-mail]> and
              Claudio Ciccani <[e-mail]>.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library 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
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.
*/

/* Heap management adapted from libc
   Copyright 1990, 1991, 1992 Free Software Foundation, Inc.
                  Written May 1989 by Mike Haertel.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

This library 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
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with this library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 675 Mass Ave,
Cambridge, MA 02139, USA.

   The author may be reached (Email) at the address [e-mail],
   or (US mail) as Mike Haertel c/o Free Software Foundation.  */

#include <config.h>

#include <unistd.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <grp.h>

#include <direct/debug.h>
#include <direct/list.h>
#include <direct/mem.h>
#include <direct/memcpy.h>
#include <direct/messages.h>
#include <direct/util.h>

#include <fusion/conf.h>
#include <fusion/shmalloc.h>
#include <fusion/fusion_internal.h>

#include <fusion/shm/pool.h>
#include <fusion/shm/shm_internal.h>


D_DEBUG_DOMAIN( Fusion_SHMHeap, "Fusion/SHMHeap", "Fusion Shared Memory Heap" );

/**********************************************************************************************************************/

/* Aligned allocation.  */
static void *
align( shmalloc_heap *heap, size_t size )
{
     void          *result;
     unsigned long  adj;

     D_DEBUG_AT( Fusion_SHMHeap, "%s( %p, %zu )\n", __FUNCTION__, heap, size );

     D_MAGIC_ASSERT( heap, shmalloc_heap );

     result = __shmalloc_brk( heap, size );

     adj = (unsigned long) result % BLOCKSIZE;
     if (adj != 0) {
          adj = BLOCKSIZE - adj;
          __shmalloc_brk( heap, adj );
          result = (char *) result + adj;
     }

     return result;
}

/* Get neatly aligned memory, initializing or
   growing the heap info table as necessary. */
static void *
morecore( shmalloc_heap *heap, size_t size )
{
     void *result;
     shmalloc_info *newinfo, *oldinfo;
     size_t newsize;

     D_DEBUG_AT( Fusion_SHMHeap, "%s( %p, %zu )\n", __FUNCTION__, heap, size );

     D_MAGIC_ASSERT( heap, shmalloc_heap );

     result = align( heap, size );
     if (result == NULL)
          return NULL;

     /* Check if we need to grow the info table.  */
     if ((size_t) BLOCK ((char *) result + size) > heap->heapsize) {
          newsize = heap->heapsize;

          while ((size_t) BLOCK ((char *) result + size) > newsize)
               newsize *= 2;

          newinfo = (shmalloc_info *) align( heap, newsize * sizeof (shmalloc_info) );
          if (newinfo == NULL) {
               __shmalloc_brk( heap, -size );
               return NULL;
          }

          direct_memcpy( newinfo, heap->heapinfo,
                         heap->heapsize * sizeof (shmalloc_info) );

          memset (newinfo + heap->heapsize,
                  0, (newsize - heap->heapsize) * sizeof (shmalloc_info));

          oldinfo = heap->heapinfo;

          newinfo[BLOCK (oldinfo)].busy.type = 0;
          newinfo[BLOCK (oldinfo)].busy.info.size = BLOCKIFY (heap->heapsize * sizeof (shmalloc_info));

          heap->heapinfo = newinfo;

          _fusion_shfree( heap, oldinfo );

          heap->heapsize = newsize;
     }

     heap->heaplimit = BLOCK ((char *) result + size);

     return result;
}

/**********************************************************************************************************************/

/* Allocate memory from the heap.  */
void *
_fusion_shmalloc( shmalloc_heap *heap, size_t size )
{
     void *result;
     size_t block, blocks, lastblocks, start;
     register size_t i;
     struct list *next;

     D_DEBUG_AT( Fusion_SHMHeap, "%s( %p, %zu )\n", __FUNCTION__, heap, size );

     D_MAGIC_ASSERT( heap, shmalloc_heap );

     /* Some programs will call shmalloc (0). We let them pass. */
     if (size == 0)
          return NULL;

     if (size < sizeof (struct list))
          size = sizeof (struct list);

     /* Determine the allocation policy based on the request size.  */
     if (size <= BLOCKSIZE / 2) {
          /* Small allocation to receive a fragment of a block.
             Determine the logarithm to base two of the fragment size. */
          register size_t log = 1;
          --size;
          while ((size /= 2) != 0)
               ++log;

          /* Look in the fragment lists for a
             free fragment of the desired size. */
          next = heap->fraghead[log].next;
          if (next != NULL) {
               /* There are free fragments of this size.
                  Pop a fragment out of the fragment list and return it.
                  Update the block's nfree and first counters. */
               result = (void *) next;
               next->prev->next = next->next;
               if (next->next != NULL)
                    next->next->prev = next->prev;
               block = BLOCK (result);
               if (--(heap->heapinfo[block].busy.info.frag.nfree) != 0)
                    heap->heapinfo[block].busy.info.frag.first = (unsigned long int)
                                                                   ((unsigned long int) ((char *) next->next - (char *) NULL)
                                                                    % BLOCKSIZE) >> log;

               /* Update the statistics.  */
               heap->chunks_used++;
               heap->bytes_used += 1 << log;
               heap->chunks_free--;
               heap->bytes_free -= 1 << log;
          }
          else {
               /* No free fragments of the desired size, so get a new block
                  and break it into fragments, returning the first.  */
               result = _fusion_shmalloc( heap, BLOCKSIZE );
               if (result == NULL)
                    return NULL;
#if 1   /* Adapted from Mike */
               heap->fragblocks[log]++;
#endif

               /* Link all fragments but the first into the free list.  */
               for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) {
                    next = (struct list *) ((char *) result + (i << log));
                    next->next = heap->fraghead[log].next;
                    next->prev = &heap->fraghead[log];
                    next->prev->next = next;
                    if (next->next != NULL)
                         next->next->prev = next;
               }

               /* Initialize the nfree and first counters for this block.  */
               block = BLOCK (result);
               heap->heapinfo[block].busy.type = log;
               heap->heapinfo[block].busy.info.frag.nfree = i - 1;
               heap->heapinfo[block].busy.info.frag.first = i - 1;

               heap->chunks_free += (BLOCKSIZE >> log) - 1;
               heap->bytes_free += BLOCKSIZE - (1 << log);
               heap->bytes_used -= BLOCKSIZE - (1 << log);
          }
     }
     else {
          /* Large allocation to receive one or more blocks.
             Search the free list in a circle starting at the last place visited.
             If we loop completely around without finding a large enough
             space we will have to get more memory from the system.  */
          blocks = BLOCKIFY (size);
          start = block = heap->heapindex;
          while (heap->heapinfo[block].free.size < blocks) {
               block = heap->heapinfo[block].free.next;
               if (block == start) {
                    /* Need to get more from the system.  Check to see if
                       the new core will be contiguous with the final free
                       block; if so we don't need to get as much.  */
                    block = heap->heapinfo[0].free.prev;
                    lastblocks = heap->heapinfo[block].free.size;
                    if (heap->heaplimit != 0 && block + lastblocks == heap->heaplimit &&
                        __shmalloc_brk( heap, 0 ) == ADDRESS (block + lastblocks) &&
                        (morecore( heap, (blocks - lastblocks) * BLOCKSIZE) ) != NULL) {
#if 1   /* Adapted from Mike */

                         /* Note that morecore() can change the location of
                            the final block if it moves the info table and the
                            old one gets coalesced into the final block. */
                         block = heap->heapinfo[0].free.prev;
                         heap->heapinfo[block].free.size += blocks - lastblocks;
#else
                         heap->heapinfo[block].free.size = blocks;
#endif
                         heap->bytes_free += (blocks - lastblocks) * BLOCKSIZE;
                         continue;
                    }
                    result = morecore( heap, blocks * BLOCKSIZE );
                    if (result == NULL)