1  /*
   2   * \brief  Allocator using bitmaps
   3   * \author Alexander Boettcher
   4   * \author Stefan Kalkowski
   5   * \date   2012-06-14
   6   */
   7  
   8  /*
   9   * Copyright (C) 2012-2013 Genode Labs GmbH
  10   *
  11   * This file is part of the Genode OS framework, which is distributed
  12   * under the terms of the GNU General Public License version 2.
  13   */
  14  
  15  #ifndef _INCLUDE__UTIL__BIT_ALLOCATOR_H_
  16  #define _INCLUDE__UTIL__BIT_ALLOCATOR_H_
  17  
  18  #include <util/bit_array.h>
  19  
  20  namespace Genode { template<unsigned> class Bit_allocator; } 
  21  
  22  
  23  template<unsigned BITS>
  24  class Genode::Bit_allocator
  25  {
  26     protected:
  27  
  28        enum {
  29           BITS_PER_BYTE = 8UL,
  30           BITS_PER_WORD = sizeof(addr_t) * BITS_PER_BYTE,
  31           BITS_ALIGNED  = (BITS + BITS_PER_WORD - 1UL)
  32                           & ~(BITS_PER_WORD - 1UL),
  33        };
  34  
  35        using Array = Bit_array<BITS_ALIGNED>;
  36  
  37        addr_t _next;
  38        Array  _array;
  39  
  40        /**
  41         * Reserve consecutive number of bits
  42         *
  43         * \noapi
  44         */
  45        void _reserve(addr_t bit_start, size_t const num)
  46        {
  47           if (!num) return;
  48  
  49           _array.set(bit_start, num);
  50        }
  51  
  52     public:
  53  
  54        class Out_of_indices : Exception {};
  55  
  56        Bit_allocator() : _next(0) {
  57           _reserve(BITS, BITS_ALIGNED - BITS); }
  58  
  59        addr_t alloc(size_t const num_log2 = 0)
  60        {
  61           addr_t const step = 1UL << num_log2;
  62           addr_t max = ~0UL;
  63  
  64           do {
  65              try {
  66                 /* throws exception if array is accessed outside bounds */
  67                 for (addr_t i = _next & ~(step - 1); i < max; i += step) {
  68                    if (_array.get(i, step))
  69                       continue;
  70  
  71                    _array.set(i, step);
  72                    _next = i + step;
  73                    return i;
  74                 }
  75              } catch (typename Array::Invalid_index_access) { }
  76  
  77              max = _next;
  78              _next = 0;
  79  
  80           } while (max != 0);
  81  
  82           throw Out_of_indices();
  83        }
  84  
  85        void free(addr_t const bit_start, size_t const num_log2 = 0)
  86        {
  87           _array.clear(bit_start, 1UL << num_log2);
  88           _next = bit_start;
  89        }
  90  };
  91  
  92  #endif /* _INCLUDE__UTIL__BIT_ALLOCATOR_H_ */