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_INLINE_HPP

    27 #define SHARE_MEMORY_METASPACE_LEFTOVERBINS_INLINE_HPP

    28 

    29 #include "memory/allocation.hpp"

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

    31 #include "utilities/debug.hpp"

    32 #include "utilities/globalDefinitions.hpp"

    33 #include "utilities/ostream.hpp"

    34 

    35 namespace metaspace {

    36 

    37 

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

    39 // Return -1 if not found.

    40 int BinMap::find_next_set_bit(int pos) const {

    41   if (get_bit(pos)) {

    42     return pos;

    43   }

    44   mask_type m2 = _mask;

    45   int pos2 = pos + 1;

    46   m2 >>= pos2;

    47   if (m2 > 0) {

    48     while ((m2 & (mask_type)1) == 0) {

    49       m2 >>= 1;

    50       pos2 ++;

    51     }

    52     return pos2;

    53   }

    54   return -1;

    55 }

    56 

    57 ///////////////////////////////////////

    58 

    59 template <size_t min_word_size, size_t spread, int num_bins>

    60 void Bins<min_word_size, spread, num_bins>::put(MetaWord* p, size_t word_size) {

    61   assert(word_size >= minimal_word_size() && word_size < maximal_word_size(), "Invalid word size");

    62   block_t* b = (block_t*)p;

    63   int bno = bin_for_size(word_size);

    64   assert(bno >= 0 && bno < num_bins, "Sanity");

    65   assert(b != _bins[bno], "double add?");

    66   b->next = _bins[bno];

    67   b->size = word_size;

    68   _bins[bno] = b;

    69   _mask.set_bit(bno);

    70 }

    71 

    72 template <size_t min_word_size, size_t spread, int num_bins>

    73 block_t* Bins<min_word_size, spread, num_bins>::get(size_t word_size) {

    74   // Adjust size for spread (we need the bin number which guarantees word_size).

    75   word_size += (spread - 1);

    76   if (word_size >= maximal_word_size()) {

    77     return NULL;

    78   }

    79   int bno = bin_for_size(word_size);

    80   bno = _mask.find_next_set_bit(bno);

    81   if (bno != -1) {

    82     assert(bno >= 0 && bno < num_bins, "Sanity");

    83     assert(_bins[bno] != NULL, "Sanity");

    84     block_t* b = _bins[bno];

    85     _bins[bno] = b->next;

    86     if (_bins[bno] == NULL) {

    87       _mask.clr_bit(bno);

    88     }

    89     return b;

    90   }

    91   return NULL;

    92 }

    93 

    94 #ifdef ASSERT

    95 template <size_t min_word_size, size_t spread, int num_bins>

    96 void Bins<min_word_size, spread, num_bins>::verify() const {

    97   for (int i = 0; i < num_bins; i ++) {

    98     assert(_mask.get_bit(i) == (_bins[i] != NULL), "Sanity");

    99     const size_t min_size = minimal_word_size_in_bin(i);

   100     const size_t max_size = maximal_word_size_in_bin(i);

   101     for(block_t* b = _bins[i]; b != NULL; b = b->next) {

   102       assert(b->size >= min_size && b->size < max_size, "Sanity");

   103     }

   104   }

   105 }

   106 #endif // ASSERT

   107 

   108 

   109 template <size_t min_word_size, size_t spread, int num_bins>

   110 void Bins<min_word_size, spread, num_bins>::statistics(block_stats_t* stats) const {

   111   for (int i = 0; i < num_bins; i ++) {

   112     for(block_t* b = _bins[i]; b != NULL; b = b->next) {

   113       stats->num_blocks ++;

   114       stats->word_size += b->size;

   115     }

   116   }

   117 }

   118 

   119 template <size_t min_word_size, size_t spread, int num_bins>

   120 void Bins<min_word_size, spread, num_bins>::print(outputStream* st) const {

   121   bool first = true;

   122   for (int i = 0; i < num_bins; i ++) {

   123     int n = 0;

   124     for(block_t* b = _bins[i]; b != NULL; b = b->next) {

   125       n ++;

   126     }

   127     if (n > 0) {

   128       if (!first) {

   129         st->print(", ");

   130       } else {

   131         first = false;

   132       }

   133       st->print(SIZE_FORMAT "=%d", minimal_word_size_in_bin(i), n);

   134     }

   135   }

   136 }

   137 

   138 

   139 

   140 ///////////////////////////////////////

   141 

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

   143 // and make it current.

   144 inline void LeftOverManager::prime_current() {

   145   if (_large_block_reserve != NULL) {

   146     _current = (MetaWord*) _large_block_reserve;

   147     _current_size = _large_block_reserve->size;

   148     _large_block_reserve = _large_block_reserve->next;

   149   } else {

   150     _current = NULL;

   151     _current_size = 0;

   152   }

   153 }

   154 

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

   156 // is too small.

   157 inline MetaWord* LeftOverManager::alloc_from_current(size_t word_size) {

   158   if (_current_size >= word_size) {

   159     assert(_current != NULL, "Must be");

   160     MetaWord* p = _current;

   161     size_t remaining = _current_size - word_size;

   162     if (remaining >= _very_small_bins.minimal_word_size()) {

   163       _current = p + word_size;

   164       _current_size = remaining;

   165     } else {

   166       // completely used up old large block. Proceed to next.

   167       prime_current();

   168     }

   169     return p;

   170   }

   171   return NULL;

   172 }

   173 

   174 inline void LeftOverManager::add_block(MetaWord* p, size_t word_size) {

   175   if (word_size >= minimal_word_size()) {

   176     if (word_size < _very_small_bins.maximal_word_size()) {

   177       _very_small_bins.put(p, word_size);

   178     } else {

   179       if (_current == NULL) {

   180         assert(_large_block_reserve == NULL, "Should be primed.");

   181         _current = p;

   182         _current_size = word_size;

   183       } else {

   184         assert(sizeof(block_t) <= word_size * BytesPerWord, "must be");

   185         block_t* b = (block_t*)p;

   186         b->size = word_size;

   187         b->next = _large_block_reserve;

   188         _large_block_reserve = b;

   189       }

   190     }

   191     _total_word_size.increment_by(word_size);

   192   }

   193 

   194   DEBUG_ONLY(verify();)

   195 

   196 }

   197 

   198 inline MetaWord* LeftOverManager::get_block(size_t requested_word_size) {

   199 

   200   requested_word_size = MAX2(requested_word_size, minimal_word_size());

   201 

   202   // First attempt to take from current large block because that is cheap (pointer bump)

   203   // and efficient (no spread)

   204   MetaWord* p = alloc_from_current(requested_word_size);

   205   if (p == NULL && _current_size > 0) {

   206     // current large block is too small. If it is moth-eaten enough to be put

   207     // into the small remains bin, do so.

   208     if (_current_size < _very_small_bins.maximal_word_size()) {

   209       _very_small_bins.put(_current, _current_size);

   210       prime_current(); // proceed to next large block.

   211       // --- and re-attempt - but only once more. If that fails too, we give up.

   212       p = alloc_from_current(requested_word_size);

   213     }

   214   }

   215 

   216   if (p == NULL) {

   217     // Did not work. Check the small bins.

   218     if (requested_word_size < _very_small_bins.maximal_word_size()) {

   219       block_t* b = _very_small_bins.get(requested_word_size);

   220       if (b != NULL) {

   221         p = (MetaWord*)b;

   222         size_t remaining = b->size - requested_word_size;

   223         if (remaining >= _very_small_bins.minimal_word_size()) {

   224           MetaWord* q = p + requested_word_size;

   225           _very_small_bins.put(q, remaining);

   226         }

   227       }

   228     }

   229   }

   230 

   231   if (p != NULL) {

   232     _total_word_size.decrement_by(requested_word_size);

   233     DEBUG_ONLY(verify();)

   234   }

   235 

   236   return p;

   237 

   238 }

   239 

   240 

   241 } // namespace metaspace

   242 

   243 #endif // SHARE_MEMORY_METASPACE_CHUNKMANAGER_HPP