1 /*

     2  * Copyright (c) 2019, SAP SE. All rights reserved.

     3  * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.

     4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     5  *

     6  * This code is free software; you can redistribute it and/or modify it

     7  * under the terms of the GNU General Public License version 2 only, as

     8  * published by the Free Software Foundation.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  *

    24  */

    25 

    26 #ifndef SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP

    27 #define SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP

    28 

    29 #include "memory/allocation.hpp"

    30 #include "utilities/debug.hpp"

    31 #include "utilities/globalDefinitions.hpp"

    32 

    33 

    34 class outputStream;

    35 

    36 namespace metaspace {

    37 

    38 struct block_t {

    39   block_t* next;

    40   size_t size;

    41 };

    42 

    43 struct block_stats_t {

    44   size_t word_size;

    45   int num_blocks;

    46 };

    47 

    48 // A bitmap keeping track of which list is occupied. Smallest list corresponds to lowest order bit.

    49 // 1 means list is not empty, 0 means list is empty.

    50 class BlockListFreeMap {

    51 

    52   typedef uint32_t mask_type;

    53   mask_type _mask;

    54 

    55   static mask_type mask_for_pos(int pos) { return 1 << pos; }

    56 

    57 public:

    58 

    59   BlockListFreeMap() : _mask(0) {}

    60 

    61   bool all_zero() const          { return _mask == 0; }

    62 

    63   bool get_bit(int pos) const    { return (_mask & mask_for_pos(pos)) != 0 ? true : false; }

    64   void set_bit(int pos)          { _mask |= mask_for_pos(pos); }

    65   void clr_bit(int pos)          { _mask &= ~mask_for_pos(pos); }

    66 

    67   // Starting at (including) pos, find the position of the next 1 bit.

    68   // Return -1 if not found.

    69   inline int find_next_set_bit(int pos) const;

    70 

    71   static int size() { return sizeof(mask_type) * 8; }

    72 

    73 };

    74 

    75 template <

    76   size_t min_word_size,

    77   size_t spread,

    78   int num_bins

    79 >

    80 class BlockListArray {

    81 

    82   STATIC_ASSERT(sizeof(block_t) <= (min_word_size * BytesPerWord));

    83 

    84   block_t* _bins[num_bins];

    85 

    86   BlockListFreeMap _map;

    87 

    88   // e.g. spread = 4

    89   //

    90   // sz    bno (put)  bno (get)

    91   //         (guarant)

    92   // 0     00         00

    93   // 1     00         01

    94   // 2     00         01

    95   // 3     00         01

    96   // 4     01         01

    97   // 5     01         02

    98   // 6     01         02

    99   // 7     01         02

   100   // 8     02         02

   101   // 9     02         03

   102   // 10    02         03

   103   // 11    02         03

   104   //

   105   // put -> no = wordsize / spread

   106   //

   107   // get -> no = (req_wordsize + spread - 1) / spread

   108 

   109   // The bin number for a given word size.

   110   static int bin_for_size(size_t word_size) {

   111     assert(word_size >= min_word_size && word_size < maximal_word_size(),

   112            "Word size oob (" SIZE_FORMAT ")", word_size);

   113     return (word_size - min_word_size) / spread;

   114   }

   115 

   116   // [minimal, maximal) size of blocks which are held in a bin.

   117   // Note that when taking a block out of the bin, only the minimum block size

   118   // is guaranteed.

   119   static size_t minimal_word_size_in_bin(int bno) {

   120     return min_word_size + (bno * spread);

   121   }

   122   static size_t maximal_word_size_in_bin(int bno) {

   123     return minimal_word_size_in_bin(bno) + spread;

   124   }

   125 

   126 public:

   127 

   128   BlockListArray() : _map() {

   129     assert(BlockListFreeMap::size() >= num_bins, "Map too small.");

   130     ::memset(_bins, 0, sizeof(_bins));

   131   }

   132 

   133   // [min, max) word size

   134   static size_t minimal_word_size() { return min_word_size; }

   135   static size_t maximal_word_size() { return min_word_size + (spread * num_bins); }

   136 

   137   inline void put(MetaWord* p, size_t word_size);

   138 

   139   inline block_t* get(size_t word_size);

   140 

   141 #ifdef ASSERT

   142   void verify() const;

   143 #endif

   144 

   145   void statistics(block_stats_t* stats) const;

   146 

   147   void print(outputStream* st) const;

   148 

   149 };

   150 

   151 

   152 } // namespace metaspace

   153 

   154 #endif // SHARE_MEMORY_METASPACE_BLOCKLISTARRAY_HPP