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_LEFTOVERBINS_HPP

    27 #define SHARE_MEMORY_METASPACE_LEFTOVERBINS_HPP

    28 

    29 #include "memory/allocation.hpp"

    30 #include "memory/metaspace/counter.hpp"

    31 #include "utilities/bitMap.hpp"

    32 #include "utilities/debug.hpp"

    33 #include "utilities/globalDefinitions.hpp"

    34 

    35 

    36 class outputStream;

    37 

    38 namespace metaspace {

    39 

    40 // The LeftOverManager is responsible for managing small leftover-

    41 // and deallocated blocks.

    42 // They come from two sources:

    43 // a) the leftover space left in a chunk when a chunk gets retired

    44 //    because it cannot serve a requested allocation. These blocks

    45 //    can be largeish (100s - 1000s of words).

    46 // b) when a metaspace allocation is deallocated prematurely - e.g.

    47 //    due to interrupted class loading. These blocks are small or

    48 //    very small.

    49 

    50 class BinMap {

    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   BinMap() : _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 struct block_t {

    76   block_t* next;

    77   size_t size;

    78 };

    79 

    80 struct block_stats_t {

    81   size_t word_size;

    82   int num_blocks;

    83 };

    84 

    85 template <

    86   size_t min_word_size,

    87   size_t spread,

    88   int num_bins

    89 >

    90 class Bins {

    91 

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

    93 

    94   block_t* _bins[num_bins];

    95 

    96   BinMap _mask;

    97 

    98   // e.g. spread = 4

    99   //

   100   // sz    bno (put)  bno (get)

   101   //         (guarant)

   102   // 0     00         00

   103   // 1     00         01

   104   // 2     00         01

   105   // 3     00         01

   106   // 4     01         01

   107   // 5     01         02

   108   // 6     01         02

   109   // 7     01         02

   110   // 8     02         02

   111   // 9     02         03

   112   // 10    02         03

   113   // 11    02         03

   114   //

   115   // put -> no = wordsize / spread

   116   //

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

   118 

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

   120   static int bin_for_size(size_t word_size) {

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

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

   123     return (word_size - min_word_size) / spread;

   124   }

   125 

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

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

   128   // is guaranteed.

   129   static size_t minimal_word_size_in_bin(int bno) {

   130     return min_word_size + (bno * spread);

   131   }

   132   static size_t maximal_word_size_in_bin(int bno) {

   133     return minimal_word_size_in_bin(bno) + spread;

   134   }

   135 

   136 public:

   137 

   138   Bins() : _mask() {

   139     assert(BinMap::size() >= num_bins, "mask too small");

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

   141   }

   142 

   143   // [min, max) word size

   144   static size_t minimal_word_size() { return min_word_size; }

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

   146 

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

   148 

   149   inline block_t* get(size_t word_size);

   150 

   151 #ifdef ASSERT

   152   void verify() const;

   153 #endif

   154 

   155   void statistics(block_stats_t* stats) const;

   156 

   157   void print(outputStream* st) const;

   158 

   159 };

   160 

   161 

   162 class LeftOverManager : public CHeapObj<mtInternal> {

   163 

   164   typedef Bins<2, 2, 16> VerySmallBinsType;

   165   VerySmallBinsType _very_small_bins;

   166 

   167   block_t* _large_block_reserve;

   168 

   169   // The current large block we gnaw on

   170   MetaWord* _current;

   171   size_t _current_size;

   172 

   173   SizeCounter _total_word_size;

   174 

   175   // Take the topmost block from the large block reserve list

   176   // and make it current.

   177   inline void prime_current();

   178 

   179   // Allocate from current block. Returns NULL if current block

   180   // is too small.

   181   inline MetaWord* alloc_from_current(size_t word_size);

   182 

   183   void large_block_statistics(block_stats_t* stats) const;

   184 

   185 public:

   186 

   187   static size_t minimal_word_size() {

   188     return VerySmallBinsType::minimal_word_size();

   189   }

   190 

   191   LeftOverManager() :

   192     _very_small_bins(),

   193     _large_block_reserve(NULL),

   194     _current(NULL),

   195     _current_size(0)

   196   {}

   197 

   198   inline void add_block(MetaWord* p, size_t word_size);

   199 

   200   inline MetaWord* get_block(size_t requested_word_size);

   201 

   202 #ifdef ASSERT

   203   void verify() const;

   204 #endif

   205 

   206   void statistics(block_stats_t* stats) const;

   207 

   208   void print(outputStream* st, bool detailed = false) const;

   209 

   210   size_t total_word_size() const { return _total_word_size.get(); }

   211 

   212 };

   213 

   214 

   215 

   216 

   217 } // namespace metaspace

   218 

   219 #endif // SHARE_MEMORY_METASPACE_CHUNKMANAGER_HPP