2  * Copyright (c) 2018, 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.

    29 #include "memory/binaryTreeDictionary.hpp"

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

    30 #include "memory/freeList.hpp"

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

    40 typedef class FreeList<Metachunk> ChunkList;

    36 class VirtualSpaceList;

    41 typedef BinaryTreeDictionary<Metachunk, FreeList<Metachunk> > ChunkTreeDictionary;

    37 class cm_stats_t;

    43 // Manages the global free lists of chunks.

    39 // class ChunkManager

    40 //

    41 // The ChunkManager has a central role. Callers request chunks from it.

    42 // It keeps the freelists for chunks. If the freelist is exhausted it

    43 // allocates new chunks from a connected VirtualSpaceList.

    44 //

    47   // Free list of chunks of different sizes.

    47   // A chunk manager is connected to a virtual space list which is used

    48   //   SpecializedChunk

    48   // to allocate new root chunks when no free chunks are found.

    49   //   SmallChunk

    49   VirtualSpaceList* const _vslist;

    50   //   MediumChunk

    51   ChunkList _free_chunks[NumberOfFreeLists];

    53   // Whether or not this is the class chunkmanager.

    51   // Name

    54   const bool _is_class;

    52   const char* const _name;

    56   // Return non-humongous chunk list by its index.

    54   // Freelist

    57   ChunkList* free_chunks(ChunkIndex index);

    55   MetachunkListCluster _chunks;

    59   // Returns non-humongous chunk list for the given chunk word size.

    57   // Returns true if this manager contains the given chunk. Slow (walks free list) and

    60   ChunkList* find_free_chunks_list(size_t word_size);

    58   // only needed for verifications.

    59   DEBUG_ONLY(bool contains_chunk(Metachunk* c) const;)

    62   //   HumongousChunk

    61   // Given a chunk we are about to handout to the caller, make sure it is committed

    63   ChunkTreeDictionary _humongous_dictionary;

    62   // according to constants::committed_words_on_fresh_chunks.

    63   // May fail if we hit the commit limit.

    64   static bool commit_chunk_before_handout(Metachunk* c);

    65   // Returns the humongous chunk dictionary.

    66   // Take a single chunk from the given freelist and adjust counters. Returns NULL

    66   ChunkTreeDictionary* humongous_dictionary() { return &_humongous_dictionary; }

    67   // if there is no fitting chunk for this level.

    67   const ChunkTreeDictionary* humongous_dictionary() const { return &_humongous_dictionary; }

    68   Metachunk* remove_first_chunk_at_level(chklvl_t l);

    69   // Size, in metaspace words, of all chunks managed by this ChunkManager

    70   // Given a chunk which must be outside of a freelist and must be free, split it to

    70   size_t _free_chunks_total;

    71   // meet a target level and return it. Splinters are added to the freelist.

    71   // Number of chunks in this ChunkManager

    72   Metachunk* split_chunk_and_add_splinters(Metachunk* c, chklvl_t target_level);

    72   size_t _free_chunks_count;

    74   // Update counters after a chunk was added or removed removed.

    74   // Uncommit all chunks equal or below the given level.

    75   void account_for_added_chunk(const Metachunk* c);

    75   void uncommit_free_chunks(chklvl_t max_level);

    76   void account_for_removed_chunk(const Metachunk* c);

    78   // Given a pointer to a chunk, attempts to merge it with neighboring

    77 public:

    79   // free chunks to form a bigger chunk. Returns true if successful.

    80   bool attempt_to_coalesce_around_chunk(Metachunk* chunk, ChunkIndex target_chunk_type);

    82   // Helper for chunk merging:

    79   // Creates a chunk manager with a given name (which is for debug purposes only)

    83   //  Given an address range with 1-n chunks which are all supposed to be

    80   // and an associated space list which will be used to request new chunks from

    84   //  free and hence currently managed by this ChunkManager, remove them

    81   // (see get_chunk())

    85   //  from this ChunkManager and mark them as invalid.

    82   ChunkManager(const char* name, VirtualSpaceList* space_list);

    86   // - This does not correct the occupancy map.

    87   // - This does not adjust the counters in ChunkManager.

    88   // - Does not adjust container count counter in containing VirtualSpaceNode.

    89   // Returns number of chunks removed.

    90   int remove_chunks_in_area(MetaWord* p, size_t word_size);

    92   // Helper for chunk splitting: given a target chunk size and a larger free chunk,

    84   // Get a chunk and be smart about it.

    93   // split up the larger chunk into n smaller chunks, at least one of which should be

    85   // - 1) Attempt to find a free chunk of exactly the pref_level level

    94   // the target chunk of target chunk size. The smaller chunks, including the target

    86   // - 2) Failing that, attempt to find a chunk smaller or equal the maximal level.

    95   // chunk, are returned to the freelist. The pointer to the target chunk is returned.

    87   // - 3) Failing that, attempt to find a free chunk of larger size and split it.

    96   // Note that this chunk is supposed to be removed from the freelist right away.

    88   // - 4) Failing that, attempt to allocate a new chunk from the connected virtual space.

    97   Metachunk* split_chunk(size_t target_chunk_word_size, Metachunk* chunk);

    89   // - Failing that, give up and return NULL.

    90   // Note: this is not guaranteed to return a *committed* chunk. The chunk manager will

    91   //   attempt to commit the returned chunk according to constants::committed_words_on_fresh_chunks;

    92   //   but this may fail if we hit a commit limit. In that case, a partly uncommitted chunk

    93   //   will be returned, and the commit is attempted again when we allocate from the chunk's

    94   //   uncommitted area. See also Metachunk::allocate.

    95   Metachunk* get_chunk(chklvl_t max_level, chklvl_t pref_level);

    99  public:

    97   // Return a single chunk to the ChunkManager and adjust accounting. May merge chunk

    98   //  with neighbors.

    99   // Happens after a Classloader was unloaded and releases its metaspace chunks.

   100   // !! Notes:

   101   //    1) After this method returns, c may not be valid anymore. Do not access the chunk after this function returns.

   102   //    2) This function will not remove c from its current chunk list. This has to be done by the caller prior to

   103   //       calling this method.

   104   void return_chunk(Metachunk* c);

   101   ChunkManager(bool is_class);

   106   // Return a single chunk to the freelist and adjust accounting. No merge is attempted.

   107   void return_chunk_simple(Metachunk* c);

   103   // Add or delete (return) a chunk to the global freelist.

   109   // Given a chunk c, which must be "in use" and must not be a root chunk, attempt to

   104   Metachunk* chunk_freelist_allocate(size_t word_size);

   110   // enlarge it in place by claiming its trailing buddy.

   111   //

   112   // This will only work if c is the leader of the buddy pair and the trailing buddy is free.

   113   //

   114   // If successful, the follower chunk will be removed from the freelists, the leader chunk c will

   115   // double in size (level decreased by one).

   116   //

   117   // On success, true is returned, false otherwise.

   118   bool attempt_enlarge_chunk(Metachunk* c);

   106   // Map a size to a list index assuming that there are lists

   120   // Attempt to reclaim free areas in metaspace wholesale:

   107   // for special, small, medium, and humongous chunks.

   121   // - first, attempt to purge nodes of the backing virtual space. This can only be successful

   108   ChunkIndex list_index(size_t size);

   122   //   if whole nodes are only containing free chunks, so it highly depends on fragmentation.

   123   // - then, it will uncommit areas of free chunks according to the rules laid down in

   124   //   settings (see settings.hpp).

   125   void wholesale_reclaim();

   110   // Map a given index to the chunk size.

   127   // Run verifications. slow=true: verify chunk-internal integrity too.

   111   size_t size_by_index(ChunkIndex index) const;

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

   129   DEBUG_ONLY(void verify_locked(bool slow) const;)

   113   bool is_class() const { return _is_class; }

   131   // Returns the name of this chunk manager.

   132   const char* name() const                  { return _name; }

   115   // Convenience accessors.

   134   // Returns total number of chunks

   116   size_t medium_chunk_word_size() const { return size_by_index(MediumIndex); }

   135   int total_num_chunks() const              { return _chunks.total_num_chunks(); }

   117   size_t small_chunk_word_size() const { return size_by_index(SmallIndex); }

   118   size_t specialized_chunk_word_size() const { return size_by_index(SpecializedIndex); }

   120   // Take a chunk from the ChunkManager. The chunk is expected to be in

   137   // Returns number of words in all free chunks.

   121   // the chunk manager (the freelist if non-humongous, the dictionary if

   138   size_t total_word_size() const            { return _chunks.total_word_size(); }

   122   // humongous).

   123   void remove_chunk(Metachunk* chunk);

   125   // Return a single chunk of type index to the ChunkManager.

   140   // Update statistics.

   126   void return_single_chunk(Metachunk* chunk);

   141   void add_to_statistics(cm_stats_t* out) const;

   128   // Add the simple linked list of chunks to the freelist of chunks

   143   void print_on(outputStream* st) const;

   129   // of type index.

   144   void print_on_locked(outputStream* st) const;

   130   void return_chunk_list(Metachunk* chunk);

   132   // Total of the space in the free chunks list

   146 private:

   133   size_t free_chunks_total_words() const { return _free_chunks_total; }

   134   size_t free_chunks_total_bytes() const { return free_chunks_total_words() * BytesPerWord; }

   136   // Number of chunks in the free chunks list

   148   static ChunkManager* _chunkmanager_class;

   137   size_t free_chunks_count() const { return _free_chunks_count; }

   149   static ChunkManager* _chunkmanager_nonclass;

   139   // Remove from a list by size.  Selects list based on size of chunk.

   151 public:

   140   Metachunk* free_chunks_get(size_t chunk_word_size);

   142 #define index_bounds_check(index)                                         \

   153   static ChunkManager* chunkmanager_class() { return _chunkmanager_class; }

   143   assert(is_valid_chunktype(index), "Bad index: %d", (int) index)

   154   static ChunkManager* chunkmanager_nonclass() { return _chunkmanager_nonclass; }

   145   size_t num_free_chunks(ChunkIndex index) const {

   156   static void set_chunkmanager_class(ChunkManager* cm);

   146     index_bounds_check(index);

   157   static void set_chunkmanager_nonclass(ChunkManager* cm);

   147 

   148     if (index == HumongousIndex) {

   149       return _humongous_dictionary.total_free_blocks();

   150     }

   151 

   152     ssize_t count = _free_chunks[index].count();

   153     return count == -1 ? 0 : (size_t) count;

   154   }

   155 

   156   size_t size_free_chunks_in_bytes(ChunkIndex index) const {

   157     index_bounds_check(index);

   158 

   159     size_t word_size = 0;

   160     if (index == HumongousIndex) {

   161       word_size = _humongous_dictionary.total_size();

   162     } else {

   163       const size_t size_per_chunk_in_words = _free_chunks[index].size();

   164       word_size = size_per_chunk_in_words * num_free_chunks(index);

   165     }

   166 

   167     return word_size * BytesPerWord;

   168   }

   169 

   170   MetaspaceChunkFreeListSummary chunk_free_list_summary() const {

   171     return MetaspaceChunkFreeListSummary(num_free_chunks(SpecializedIndex),

   172                                          num_free_chunks(SmallIndex),

   173                                          num_free_chunks(MediumIndex),

   174                                          num_free_chunks(HumongousIndex),

   175                                          size_free_chunks_in_bytes(SpecializedIndex),

   176                                          size_free_chunks_in_bytes(SmallIndex),

   177                                          size_free_chunks_in_bytes(MediumIndex),

   178                                          size_free_chunks_in_bytes(HumongousIndex));

   179   }

   180 

   181 #ifdef ASSERT

   182   // Debug support

   183   // Verify free list integrity. slow=true: verify chunk-internal integrity too.

   184   void verify(bool slow) const;

   185   void locked_verify(bool slow) const;

   186 #endif

   187 

   188   void locked_print_free_chunks(outputStream* st);

   189 

   190   // Fill in current statistic values to the given statistics object.

   191   void collect_statistics(ChunkManagerStatistics* out) const;