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

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

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

    27 #include "memory/metaspace/metabase.hpp"

    28 

    28 #include "memory/metaspace/metaspaceCommon.hpp"

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

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

    32 class MetachunkTest;

    34 

    35 class outputStream;

    42 //            +--------------+ <- end    --+       --+

    45 //            +--------------+ <- end    ----+         --+

    43 //            |              |             |         |

    46 //            |              |               |           |

    44 //            |              |             | free    |

    47 //            |              |               | free      |

    45 //            |              |             |         |

    48 //            |              |               |

    46 //            |              |             |         | size | capacity

    49 //            |              |               |           | size (aka capacity)

    47 //            |              |             |         |

    50 //            |              |               |           |

    48 //            |              | <- top   -- +         |

    51 //            | -----------  | <- top     -- +           |

    49 //            |              |             |         |

    52 //            |              |               |           |

    50 //            |              |             | used    |

    53 //            |              |               | used      |

    51 //            |              |             |         |

    54 //            +--------------+ <- start   -- +        -- +

    52 //            |              |             |         |

    55 

    53 //            +--------------+ <- bottom --+       --+

    56 // Note: this is a chunk **descriptor**. The real Payload area lives in metaspace,

    54 

    57 // this class lives somewhere else.

    55 enum ChunkOrigin {

    58 class Metachunk {

    56   // Chunk normally born (via take_from_committed)

    59 

    57   origin_normal = 1,

    60   // start of chunk memory; NULL if dead.

    58   // Chunk was born as padding chunk

    61   MetaWord* _base;

    59   origin_pad = 2,

    62 

    60   // Chunk was born as leftover chunk in VirtualSpaceNode::retire

    63   // Used words.

    61   origin_leftover = 3,

    64   size_t _used_words;

    62   // Chunk was born as result of a merge of smaller chunks

    65 

    63   origin_merge = 4,

    66   // Guaranteed-to-be-committed-words, counted from base

    64   // Chunk was born as result of a split of a larger chunk

    67   //  (This is a performance optimization. The underlying VirtualSpaceNode knows

    65   origin_split = 5,

    68   //  which granules are committed; but we want to avoid asking it unnecessarily

    66 

    69   //  in Metachunk::allocate(), so we keep a limit until which we are guaranteed

    67   origin_minimum = origin_normal,

    70   //  to have committed memory under us.)

    68   origin_maximum = origin_split,

    71   size_t _committed_words;

    69   origins_count = origin_maximum + 1

    72 

    73   chklvl_t _level; // aka size.

    74 

    75   // state_free:    free, owned by ChunkManager

    76   // state_in_use:  in-use, owned by SpaceManager

    77   // dead:          just a hollow chunk header without associated memory, owned

    78   //                 by chunk header pool.

    79   enum state_t {

    80     state_free = 0,

    81     state_in_use = 1,

    82     state_dead = 2

    83   };

    84   state_t _state;

    85 

    86   // We need unfortunately a back link to the virtual space node

    87   // for splitting and merging nodes.

    88   VirtualSpaceNode* _vsnode;

    89 

    90 

    91   // A chunk header is kept in a list:

    92   // - in the list of used chunks inside a SpaceManager, if it is in use

    93   // - in the list of free chunks inside a ChunkManager, if it is free

    94   // - in the freelist of unused headers inside the ChunkHeaderPool,

    95   //   if it is unused (e.g. result of chunk merging) and has no associated

    96   //   memory area.

    97   Metachunk* _prev;

    98   Metachunk* _next;

    99 

   100   // Furthermore, we keep, per chunk, information about the neighboring chunks.

   101   // This is needed to split and merge chunks.

   102   Metachunk* _prev_in_vs;

   103   Metachunk* _next_in_vs;

   104 

   105   MetaWord* top() const           { return base() + _used_words; }

   106 

   107   // Commit uncommitted section of the chunk.

   108   // Fails if we hit a commit limit.

   109   bool commit_up_to(size_t new_committed_words);

   110 

   111 public:

   112 

   113   Metachunk()

   114     : _base(NULL),

   115       _used_words(0),

   116       _committed_words(0),

   117       _level(chklvl::ROOT_CHUNK_LEVEL),

   118       _state(state_free),

   119       _vsnode(NULL),

   120       _prev(NULL), _next(NULL),

   121       _prev_in_vs(NULL), _next_in_vs(NULL)

   122   {}

   123 

   124   size_t word_size() const        { return chklvl::word_size_for_level(_level); }

   125 

   126   MetaWord* base() const          { return _base; }

   127 //  void set_base(MetaWord* p)      { _base = p; }

   128   MetaWord* end() const           { return base() + word_size(); }

   129 

   130   // Chunk list wiring

   131   void set_prev(Metachunk* c)     { _prev = c; }

   132   Metachunk* prev() const         { return _prev; }

   133   void set_next(Metachunk* c)     { _next = c; }

   134   Metachunk* next() const         { return _next; }

   135 

   136   DEBUG_ONLY(bool in_list() const { return _prev != NULL || _next != NULL; })

   137 

   138   // Physical neighbors wiring

   139   void set_prev_in_vs(Metachunk* c) { _prev_in_vs = c; }

   140   Metachunk* prev_in_vs() const     { return _prev_in_vs; }

   141   void set_next_in_vs(Metachunk* c) { _next_in_vs = c; }

   142   Metachunk* next_in_vs() const     { return _next_in_vs; }

   143 

   144   bool is_free() const            { return _state == state_free; }

   145   bool is_in_use() const          { return _state == state_in_use; }

   146   bool is_dead() const            { return _state == state_dead; }

   147   void set_free()                 { _state = state_free; }

   148   void set_in_use()               { _state = state_in_use; }

   149   void set_dead()                 { _state = state_dead; }

   150 

   151   // Return a single char presentation of the state ('f', 'u', 'd')

   152   char get_state_char() const;

   153 

   154   void inc_level()                { _level ++; DEBUG_ONLY(chklvl::is_valid_level(_level);) }

   155   void dec_level()                { _level --; DEBUG_ONLY(chklvl::is_valid_level(_level);) }

   156 //  void set_level(chklvl_t v)      { _level = v; DEBUG_ONLY(chklvl::is_valid_level(_level);) }

   157   chklvl_t level() const          { return _level; }

   158 

   159   // Convenience functions for extreme levels.

   160   bool is_root_chunk() const      { return chklvl::ROOT_CHUNK_LEVEL == _level; }

   161   bool is_leaf_chunk() const      { return chklvl::HIGHEST_CHUNK_LEVEL == _level; }

   162 

   163   VirtualSpaceNode* vsnode() const        { return _vsnode; }

   164 //  void set_vsnode(VirtualSpaceNode* n)    { _vsnode = n; }

   165 

   166   size_t used_words() const                   { return _used_words; }

   167   size_t free_words() const                   { return word_size() - used_words(); }

   168   size_t free_below_committed_words() const   { return committed_words() - used_words(); }

   169   void reset_used_words()                     { _used_words = 0; }

   170 

   171   size_t committed_words() const      { return _committed_words; }

   172   void set_committed_words(size_t v);

   173   bool is_fully_committed() const     { return committed_words() == word_size(); }

   174   bool is_fully_uncommitted() const   { return committed_words() == 0; }

   175 

   176   // Ensure that chunk is committed up to at least new_committed_words words.

   177   // Fails if we hit a commit limit.

   178   bool ensure_committed(size_t new_committed_words);

   179   bool ensure_committed_locked(size_t new_committed_words);

   180 

   181   bool ensure_fully_committed()           { return ensure_committed(word_size()); }

   182   bool ensure_fully_committed_locked()    { return ensure_committed_locked(word_size()); }

   183 

   184   // Uncommit chunk area. The area must be a common multiple of the

   185   // commit granule size (in other words, we cannot uncommit chunks smaller than

   186   // a commit granule size).

   187   void uncommit();

   188   void uncommit_locked();

   189 

   190   // Alignment of an allocation.

   191   static const size_t allocation_alignment_bytes = 8;

   192   static const size_t allocation_alignment_words = allocation_alignment_bytes / BytesPerWord;

   193 

   194   // Allocation from a chunk

   195 

   196   // Allocate word_size words from this chunk (word_size must be aligned to

   197   //  allocation_alignment_words).

   198   //

   199   // May cause memory to be committed. That may fail if we hit a commit limit. In that case,

   200   //  NULL is returned and p_did_hit_commit_limit will be set to true.

   201   // If the remainder portion of the chunk was too small to hold the allocation,

   202   //  NULL is returned and p_did_hit_commit_limit will be set to false.

   203   MetaWord* allocate(size_t net_word_size, bool* p_did_hit_commit_limit);

   204 

   205   // Given a memory range which may or may not have been allocated from this chunk, attempt

   206   // to roll its allocation back. This can work if this is the very last allocation we did

   207   // from this chunk, in which case we just lower the top pointer again.

   208   // Returns true if this succeeded, false if it failed.

   209   bool attempt_rollback_allocation(MetaWord* p, size_t word_size);

   210 

   211   // Initialize structure for reuse.

   212   void initialize(VirtualSpaceNode* node, MetaWord* base, chklvl_t lvl) {

   213     _vsnode = node; _base = base; _level = lvl;

   214     _used_words = _committed_words = 0; _state = state_free;

   215     _next = _prev = _next_in_vs = _prev_in_vs = NULL;

   216   }

   217 

   218   // Returns true if this chunk is the leader in its buddy pair, false if not.

   219   // Must not be called for root chunks.

   220   bool is_leader() const {

   221     assert(!is_root_chunk(), "Root chunks have no buddy.");

   222     // I am sure this can be done smarter...

   223     return is_aligned(base(), chklvl::word_size_for_level(level() - 1) * BytesPerWord);

   224   }

   225 

   226   //// Debug stuff ////

   227 #ifdef ASSERT

   228   void verify(bool slow) const;

   229   void zap_header(uint8_t c = 0x17);

   230   void fill_with_pattern(MetaWord pattern, size_t word_size);

   231   void check_pattern(MetaWord pattern, size_t word_size);

   232 

   233   // Returns true if pointer points into the used area of this chunk.

   234   bool is_valid_pointer(const MetaWord* p) const {

   235     return base() <= p && p < top();

   236   }

   237 #endif // ASSERT

   238 

   239   void print_on(outputStream* st) const;

   240 

    72 inline bool is_valid_chunkorigin(ChunkOrigin origin) {

   243 // Little print helpers: since we often print out chunks, here some convenience macros

    73   return origin == origin_normal ||

   244 #define METACHUNK_FORMAT                "@" PTR_FORMAT ", %c, base " PTR_FORMAT ", level " CHKLVL_FORMAT

    74     origin == origin_pad ||

   245 #define METACHUNK_FORMAT_ARGS(chunk)    p2i(chunk), chunk->get_state_char(), p2i(chunk->base()), chunk->level()

    75     origin == origin_leftover ||

   246 

    76     origin == origin_merge ||

   247 #define METACHUNK_FULL_FORMAT                "@" PTR_FORMAT ", %c, base " PTR_FORMAT ", level " CHKLVL_FORMAT " (" SIZE_FORMAT "), used: " SIZE_FORMAT ", committed: " SIZE_FORMAT

    77     origin == origin_split;

   248 #define METACHUNK_FULL_FORMAT_ARGS(chunk)    p2i(chunk), chunk->get_state_char(), p2i(chunk->base()), chunk->level(), chunk->word_size(), chunk->used_words(), chunk->committed_words()

    78 }

   249 

    79 

   250 /////////

    80 class Metachunk : public Metabase<Metachunk> {

   251 // A list of Metachunks.

    81 

   252 class MetachunkList {

    82   friend class ::MetachunkTest;

   253 

    83 

   254   Metachunk* _first;

    84   // The VirtualSpaceNode containing this chunk.

   255 

    85   VirtualSpaceNode* const _container;

   256   // Number of chunks

    86 

   257   IntCounter _num;

    87   // Current allocation top.

   258 

    88   MetaWord* _top;

   259 public:

    89 

   260 

    90   // A 32bit sentinel for debugging purposes.

   261   MetachunkList() : _first(NULL), _num() {}

    91   enum { CHUNK_SENTINEL = 0x4d4554EF,  // "MET"

   262 

    92          CHUNK_SENTINEL_INVALID = 0xFEEEEEEF

   263   Metachunk* first() const { return _first; }

    93   };

   264   int size() const { return _num.get(); }

    94 

   265 

    95   uint32_t _sentinel;

   266   void add(Metachunk* c) {

    96 

   267     assert(!c->in_list(), "Chunk must not be in a list");

    97   const ChunkIndex _chunk_type;

   268     if (_first) {

    98   const bool _is_class;

   269       _first->set_prev(c);

    99   // Whether the chunk is free (in freelist) or in use by some class loader.

   270     }

   100   bool _is_tagged_free;

   271     c->set_next(_first);

   101 

   272     c->set_prev(NULL);

   102   ChunkOrigin _origin;

   273     _first = c;

   103   int _use_count;

   274     _num.increment();

   104 

   275   }

   105   MetaWord* initial_top() const { return (MetaWord*)this + overhead(); }

   276 

   106   MetaWord* top() const         { return _top; }

   277   // Remove first node unless empty. Returns node or NULL.

   107 

   278   Metachunk* remove_first() {

   108  public:

   279     Metachunk* c = _first;

   109   // Metachunks are allocated out of a MetadataVirtualSpace and

   280     if (c != NULL) {

   110   // and use some of its space to describe itself (plus alignment

   281       assert(c->prev() == NULL, "Sanity");

   111   // considerations).  Metadata is allocated in the rest of the chunk.

   282       Metachunk* c2 = c->next();

   112   // This size is the overhead of maintaining the Metachunk within

   283       if (c2 != NULL) {

   113   // the space.

   284         c2->set_prev(NULL);

   114 

   285       }

   115   // Alignment of each allocation in the chunks.

   286       _first = c2;

   116   static size_t object_alignment();

   287       c->set_next(NULL);

   117 

   288       _num.decrement();

   118   // Size of the Metachunk header, in words, including alignment.

   289     }

   119   static size_t overhead();

   290     return c;

   120 

   291   }

   121   Metachunk(ChunkIndex chunktype, bool is_class, size_t word_size, VirtualSpaceNode* container);

   292 

   122 

   293   // Remove given chunk from list. List must contain that chunk.

   123   MetaWord* allocate(size_t word_size);

   294   void remove(Metachunk* c) {

   124 

   295     assert(contains(c), "List does not contain this chunk");

   125   VirtualSpaceNode* container() const { return _container; }

   296     if (_first == c) {

   126 

   297       _first = c->next();

   127   MetaWord* bottom() const { return (MetaWord*) this; }

   298       if (_first != NULL) {

   128 

   299         _first->set_prev(NULL);

   129   // Reset top to bottom so chunk can be reused.

   300       }

   130   void reset_empty() { _top = initial_top(); clear_next(); clear_prev(); }

   301     } else {

   131   bool is_empty() { return _top == initial_top(); }

   302       if (c->next() != NULL) {

   132 

   303         c->next()->set_prev(c->prev());

   133   // used (has been allocated)

   304       }

   134   // free (available for future allocations)

   305       if (c->prev() != NULL) {

   135   size_t word_size() const { return size(); }

   306         c->prev()->set_next(c->next());

   136   size_t used_word_size() const;

   307       }

   137   size_t free_word_size() const;

   308     }

   138 

   309     c->set_prev(NULL);

   139   bool is_tagged_free() { return _is_tagged_free; }

   310     c->set_next(NULL);

   140   void set_is_tagged_free(bool v) { _is_tagged_free = v; }

   311     _num.decrement();

   141 

   312   }

   142   bool contains(const void* ptr) { return bottom() <= ptr && ptr < _top; }

   313 

   314 #ifdef ASSERT

   315   bool contains(const Metachunk* c) const;

   316   void verify(bool slow) const;

   317 #endif

   318 

   319   // Returns size, in words, of committed space of all chunks in this list.

   320   // Note: walks list.

   321   size_t committed_word_size() const {

   322     size_t l = 0;

   323     for (const Metachunk* c = _first; c != NULL; c = c->next()) {

   324       l += c->committed_words();

   325     }

   326     return l;

   327   }

   163 

   333 //////////////////

   164 // Helper function that does a bunch of checks for a chunk.

   334 // A cluster of Metachunk Lists, one for each chunk level, together with associated counters.

   165 DEBUG_ONLY(void do_verify_chunk(Metachunk* chunk);)

   335 class MetachunkListCluster {

   166 

   336 

   167 // Given a Metachunk, update its in-use information (both in the

   337   MetachunkList _lists[chklvl::NUM_CHUNK_LEVELS];

   168 // chunk and the occupancy map).

   338   SizeCounter   _total_word_size;

   169 void do_update_in_use_info_for_chunk(Metachunk* chunk, bool inuse);

   339   IntCounter    _total_num_chunks;

   340 

   341   const MetachunkList* list_for_level(chklvl_t lvl) const         { DEBUG_ONLY(chklvl::check_valid_level(lvl)); return _lists + lvl; }

   342   MetachunkList* list_for_level(chklvl_t lvl)                     { DEBUG_ONLY(chklvl::check_valid_level(lvl)); return _lists + lvl; }

   343 

   344   const MetachunkList* list_for_chunk(const Metachunk* c) const   { return list_for_level(c->level()); }

   345   MetachunkList* list_for_chunk(const Metachunk* c)               { return list_for_level(c->level()); }

   346 

   347 public:

   348 

   349   const Metachunk* first_at_level(chklvl_t lvl) const   { return list_for_level(lvl)->first(); }

   350   Metachunk* first_at_level(chklvl_t lvl)               { return list_for_level(lvl)->first(); }

   351 

   352   // Remove given chunk from its list. List must contain that chunk.

   353   void remove(Metachunk* c) {

   354     list_for_chunk(c)->remove(c);

   355     _total_word_size.decrement_by(c->word_size());

   356     _total_num_chunks.decrement();

   357   }

   358 

   359   // Remove first node unless empty. Returns node or NULL.

   360   Metachunk* remove_first(chklvl_t lvl) {

   361     Metachunk* c = list_for_level(lvl)->remove_first();

   362     if (c != NULL) {

   363       _total_word_size.decrement_by(c->word_size());

   364       _total_num_chunks.decrement();

   365     }

   366     return c;

   367   }

   368 

   369   void add(Metachunk* c) {

   370     list_for_chunk(c)->add(c);

   371     _total_word_size.increment_by(c->word_size());

   372     _total_num_chunks.increment();

   373   }

   374 

   375   // Returns number of chunks for a given level.

   376   int num_chunks_at_level(chklvl_t lvl) const {

   377     return list_for_level(lvl)->size();

   378   }

   379 

   380   // Returns number of chunks for a given level.

   381   size_t committed_word_size_at_level(chklvl_t lvl) const {

   382     return list_for_level(lvl)->committed_word_size();

   383   }

   384 

   385   // Returs word size, in total, of all chunks in all lists.

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

   387 

   388   // Returns number of chunks in total

   389   int total_num_chunks() const            { return _total_num_chunks.get(); }

   390 

   391   // Returns size, in words, of committed space of all chunks in all list.

   392   // Note: walks lists.

   393   size_t total_committed_word_size() const {

   394     size_t l = 0;

   395     for (chklvl_t l = chklvl::LOWEST_CHUNK_LEVEL; l <= chklvl::HIGHEST_CHUNK_LEVEL; l ++) {

   396       l += list_for_level(l)->committed_word_size();

   397     }

   398     return l;

   399   }

   400 

   401   DEBUG_ONLY(void verify(bool slow) const;)

   402   DEBUG_ONLY(bool contains(const Metachunk* c) const;)

   403 

   404   void print_on(outputStream* st) const;

   405 

   406 };

   407