1 /*
  2  * Copyright (c) 2020, 2024, Oracle and/or its affiliates. All rights reserved.
  3  * Copyright (c) 2020 SAP SE. 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 #include "precompiled.hpp"
 27 #include "memory/metaspace/counters.hpp"
 28 #include "memory/metaspace/freeBlocks.hpp"
 29 //#define LOG_PLEASE
 30 #include "metaspaceGtestCommon.hpp"
 31 
 32 using metaspace::FreeBlocks;
 33 using metaspace::SizeCounter;
 34 
 35 #define CHECK_CONTENT(fb, num_blocks_expected, word_size_expected) \
 36 { \
 37   if (word_size_expected > 0) { \
 38     EXPECT_FALSE(fb.is_empty()); \
 39   } else { \
 40     EXPECT_TRUE(fb.is_empty()); \
 41   } \
 42   EXPECT_EQ(fb.total_size(), (size_t)word_size_expected); \
 43   EXPECT_EQ(fb.count(), (int)num_blocks_expected); \
 44 }
 45 
 46 class FreeBlocksTest {
 47 
 48   FeederBuffer _fb;
 49   FreeBlocks _freeblocks;
 50 
 51   // random generator for block feeding
 52   RandSizeGenerator _rgen_feeding;
 53 
 54   // random generator for allocations (and, hence, deallocations)
 55   RandSizeGenerator _rgen_allocations;
 56 
 57   SizeCounter _allocated_words;
 58 
 59   struct allocation_t {
 60     allocation_t* next;
 61     size_t word_size;
 62     MetaWord* p;
 63   };
 64 
 65   // Array of the same size as the pool max capacity; holds the allocated elements.
 66   allocation_t* _allocations;
 67 
 68   int _num_allocs;
 69   int _num_deallocs;
 70   int _num_feeds;
 71 
 72   bool feed_some() {
 73     size_t word_size = _rgen_feeding.get();
 74     MetaWord* p = _fb.get(word_size);
 75     if (p != nullptr) {
 76       _freeblocks.add_block(p, word_size);
 77       return true;
 78     }
 79     return false;
 80   }
 81 
 82   bool deallocate_top() {
 83 
 84     allocation_t* a = _allocations;
 85     if (a != nullptr) {
 86       _allocations = a->next;
 87       check_marked_range(a->p, a->word_size);
 88       _freeblocks.add_block(a->p, a->word_size);
 89       delete a;
 90       DEBUG_ONLY(_freeblocks.verify();)
 91       return true;
 92     }
 93     return false;
 94   }
 95 
 96   void deallocate_all() {
 97     while (deallocate_top());
 98   }
 99 
100   bool allocate() {
101 
102     size_t word_size = MAX2(_rgen_allocations.get(), _freeblocks.MinWordSize);
103     MetaWord* p = _freeblocks.remove_block(word_size);
104     if (p != nullptr) {
105       _allocated_words.increment_by(word_size);
106       allocation_t* a = new allocation_t;
107       a->p = p; a->word_size = word_size;
108       a->next = _allocations;
109       _allocations = a;
110       DEBUG_ONLY(_freeblocks.verify();)
111       mark_range(p, word_size);
112       return true;
113     }
114     return false;
115   }
116 
117   void test_all_marked_ranges() {
118     for (allocation_t* a = _allocations; a != nullptr; a = a->next) {
119       check_marked_range(a->p, a->word_size);
120     }
121   }
122 
123   void test_loop() {
124     // We loop and in each iteration execute one of three operations:
125     // - allocation from fbl
126     // - deallocation to fbl of a previously allocated block
127     // - feeding a new larger block into the fbl (mimicks chunk retiring)
128     // When we have fed all large blocks into the fbl (feedbuffer empty), we
129     //  switch to draining the fbl completely (only allocs)
130     bool forcefeed = false;
131     bool draining = false;
132     bool stop = false;
133     int iter = 25000; // safety stop
134     while (!stop && iter > 0) {
135       iter --;
136       int surprise = (int)os::random() % 10;
137       if (!draining && (surprise >= 7 || forcefeed)) {
138         forcefeed = false;
139         if (feed_some()) {
140           _num_feeds++;
141         } else {
142           // We fed all input memory into the fbl. Now lets proceed until the fbl is drained.
143           draining = true;
144         }
145       } else if (!draining && surprise < 1) {
146         deallocate_top();
147         _num_deallocs++;
148       } else {
149         if (allocate()) {
150           _num_allocs++;
151         } else {
152           if (draining) {
153             stop = _freeblocks.total_size() < 512;
154           } else {
155             forcefeed = true;
156           }
157         }
158       }
159       if ((iter % 1000) == 0) {
160         DEBUG_ONLY(_freeblocks.verify();)
161         test_all_marked_ranges();
162         LOG("a %d (" SIZE_FORMAT "), d %d, f %d", _num_allocs, _allocated_words.get(), _num_deallocs, _num_feeds);
163 #ifdef LOG_PLEASE
164         _freeblocks.print(tty, true);
165         tty->cr();
166 #endif
167       }
168     }
169 
170     // Drain
171 
172   }
173 
174 public:
175 
176   FreeBlocksTest(size_t avg_alloc_size) :
177     _fb(512 * K), _freeblocks(),
178     _rgen_feeding(128, 4096),
179     _rgen_allocations(avg_alloc_size / 4, avg_alloc_size * 2, 0.01f, avg_alloc_size / 3, avg_alloc_size * 30),
180     _allocations(nullptr),
181     _num_allocs(0),
182     _num_deallocs(0),
183     _num_feeds(0)
184   {
185     CHECK_CONTENT(_freeblocks, 0, 0);
186     // some initial feeding
187     _freeblocks.add_block(_fb.get(1024), 1024);
188     CHECK_CONTENT(_freeblocks, 1, 1024);
189   }
190 
191   ~FreeBlocksTest() {
192     deallocate_all();
193   }
194 
195   static void test_small_allocations() {
196     FreeBlocksTest test(10);
197     test.test_loop();
198   }
199 
200   static void test_medium_allocations() {
201     FreeBlocksTest test(30);
202     test.test_loop();
203   }
204 
205   static void test_large_allocations() {
206     FreeBlocksTest test(150);
207     test.test_loop();
208   }
209 
210 };
211 
212 TEST_VM(metaspace, freeblocks_basics) {
213 
214   FreeBlocks fbl;
215   MetaWord tmp[1024];
216   CHECK_CONTENT(fbl, 0, 0);
217 
218   fbl.add_block(tmp, 1024);
219   DEBUG_ONLY(fbl.verify();)
220   ASSERT_FALSE(fbl.is_empty());
221   CHECK_CONTENT(fbl, 1, 1024);
222 
223   MetaWord* p = fbl.remove_block(1024);
224   EXPECT_EQ(p, tmp);
225   DEBUG_ONLY(fbl.verify();)
226   CHECK_CONTENT(fbl, 0, 0);
227 
228 }
229 
230 TEST_VM(metaspace, freeblocks_small) {
231   FreeBlocksTest::test_small_allocations();
232 }
233 
234 TEST_VM(metaspace, freeblocks_medium) {
235   FreeBlocksTest::test_medium_allocations();
236 }
237 
238 TEST_VM(metaspace, freeblocks_large) {
239   FreeBlocksTest::test_large_allocations();
240 }
241