1  /*
   2   * \brief  Heap partition
   3   * \author Norman Feske
   4   * \date   2006-05-15
   5   */
   6  
   7  /*
   8   * Copyright (C) 2006-2010 Genode Labs GmbH
   9   *
  10   * This file is part of the Genode OS framework, which is distributed
  11   * under the terms of the GNU General Public License version 2.
  12   */
  13  
  14  #ifndef _INCLUDE__BASE__HEAP_H_
  15  #define _INCLUDE__BASE__HEAP_H_
  16  
  17  #include <util/list.h>
  18  #include <ram_session/ram_session.h>
  19  #include <rm_session/rm_session.h>
  20  #include <base/allocator_avl.h>
  21  #include <base/lock.h>
  22  
  23  namespace Genode {
  24  
  25     /**
  26      * Heap that uses dataspaces as backing store
  27      *
  28      * The heap class provides an allocator that uses a list of dataspaces of a ram
  29      * session as backing store. One dataspace may be used for holding multiple blocks.
  30      */
  31     class Heap : public Allocator
  32     {
  33        private:
  34  
  35           enum {
  36              MIN_CHUNK_SIZE =    4*1024,  /* in machine words */
  37              MAX_CHUNK_SIZE = 1024*1024
  38           };
  39  
  40           class Dataspace : public List<Dataspace>::Element
  41           {
  42              public:
  43  
  44                 Ram_dataspace_capability cap;
  45                 void  *local_addr;
  46           };
  47  
  48           class Dataspace_pool : public List<Dataspace>
  49           {
  50              private:
  51  
  52                 Ram_session *_ram_session;  /* ram session for backing store */
  53                 Rm_session  *_rm_session;   /* region manager                */
  54  
  55              public:
  56  
  57                 /**
  58                  * Constructor
  59                  */
  60                 Dataspace_pool(Ram_session *ram_session, Rm_session *rm_session):
  61                    _ram_session(ram_session), _rm_session(rm_session) { }
  62  
  63                 /**
  64                  * Destructor
  65                  */
  66                 ~Dataspace_pool();
  67  
  68                 /**
  69                  * Expand dataspace by specified size
  70                  *
  71                  * \param size      number of bytes to add to the dataspace pool
  72                  * \param md_alloc  allocator to expand. This allocator is also
  73                  *                  used for meta data allocation (only after
  74                  *                  being successfully expanded).
  75                  * \throw           Rm_session::Invalid_dataspace,
  76                  *                  Rm_session::Region_conflict
  77                  * \return          0 on success or negative error code
  78                  */
  79                 int expand(size_t size, Range_allocator *alloc);
  80           };
  81  
  82           /*
  83            * NOTE: The order of the member variables is important for
  84            *       the calling order of the destructors!
  85            */
  86  
  87           Lock           _lock;
  88           Dataspace_pool _ds_pool;      /* list of dataspaces */
  89           Allocator_avl  _alloc;        /* local allocator    */
  90           size_t         _quota_limit;
  91           size_t         _quota_used;
  92           size_t         _chunk_size;
  93  
  94           /**
  95            * Try to allocate block at our local allocator
  96            *
  97            * \return true on success
  98            *
  99            * This function is a utility used by `alloc` to avoid
 100            * code duplication.
 101            */
 102           bool _try_local_alloc(size_t size, void **out_addr);
 103  
 104  
 105        public:
 106  
 107           enum { UNLIMITED = ~0 };
 108  
 109           Heap(Ram_session *ram_session,
 110                Rm_session  *rm_session,
 111                size_t       quota_limit = UNLIMITED,
 112                void        *static_addr = 0,
 113                size_t       static_size = 0)
 114           :
 115              _ds_pool(ram_session, rm_session),
 116              _quota_limit(quota_limit), _quota_used(0),
 117              _chunk_size(MIN_CHUNK_SIZE)
 118           {
 119              if (static_addr)
 120                 _alloc.add_range((addr_t)static_addr, static_size);
 121           }
 122  
 123           /**
 124            * Reconfigure quota limit
 125            *
 126            * \return  negative error code if new quota limit is higher than
 127            *          currently used quota.
 128            */
 129           int quota_limit(size_t new_quota_limit);
 130  
 131  
 132           /*************************
 133            ** Allocator interface **
 134            *************************/
 135  
 136           bool   alloc(size_t, void **);
 137           void   free(void *, size_t);
 138           size_t consumed() { return _quota_used; }
 139           size_t overhead() { return _alloc.overhead(); }
 140     };
 141  
 142  
 143     /**
 144      * Heap that allocates each block at a separate dataspace
 145      */
 146     class Sliced_heap : public Allocator
 147     {
 148        private:
 149  
 150           class Block;
 151  
 152           Ram_session    *_ram_session;  /* ram session for backing store */
 153           Rm_session     *_rm_session;   /* region manager                */
 154           size_t          _consumed;     /* number of allocated bytes     */
 155           List<Block>     _block_list;   /* list of allocated blocks      */
 156           Lock            _lock;         /* serialize allocations         */
 157  
 158        public:
 159  
 160           /**
 161            * Constructor
 162            */
 163           Sliced_heap(Ram_session *ram_session, Rm_session *rm_session);
 164  
 165           /**
 166            * Destructor
 167            */
 168           ~Sliced_heap();
 169  
 170  
 171           /*************************
 172            ** Allocator interface **
 173            *************************/
 174  
 175           bool   alloc(size_t, void **);
 176           void   free(void *, size_t);
 177           size_t consumed() { return _consumed; }
 178           size_t overhead();
 179     };
 180  }
 181  
 182  #endif /* _INCLUDE__BASE__HEAP_H_ */
© 2010 Genode Labs