1 /*
2  * Copyright (c) 2020, 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/freeChunkList.hpp"
29 #include "memory/metaspace/metachunkList.hpp"
30 #include "memory/metaspace/metaspaceSettings.hpp"
31 //#define LOG_PLEASE
32 #include "metaspaceGtestCommon.hpp"
33 #include "metaspaceGtestContexts.hpp"
34 #include "metaspaceGtestRangeHelpers.hpp"
35 
36 using metaspace::FreeChunkList;
37 using metaspace::FreeChunkListVector;
38 using metaspace::MemRangeCounter;
39 using metaspace::MetachunkList;
40 using metaspace::Settings;
41 
TEST_VM(metaspace,metachunklist)42 TEST_VM(metaspace, metachunklist) {
43 
44   ChunkGtestContext context;
45 
46   MetachunkList lst;
47 
48   Metachunk* chunks[10];
49   size_t total_size = 0;
50 
51   for (int i = 0; i < 10; i++) {
52     Metachunk* c = NULL;
53     context.alloc_chunk_expect_success(&c, ChunkLevelRanges::all_chunks().random_value());
54     chunks[i] = c;
55     total_size += c->committed_words();
56 
57     lst.add(c);
58     EXPECT_EQ(lst.first(), c);
59 
60     Metachunk* c2 = lst.remove_first();
61     EXPECT_EQ(c, c2);
62 
63     EXPECT_EQ(lst.count(), i);
64     lst.add(c);
65     EXPECT_EQ(lst.count(), i + 1);
66     EXPECT_EQ(lst.calc_committed_word_size(), total_size);
67 
68   }
69 
70   for (int i = 0; i < 10; i++) {
71     DEBUG_ONLY(EXPECT_TRUE(lst.contains(chunks[i]));)
72   }
73 
74   for (int i = 0; i < 10; i++) {
75     Metachunk* c = lst.remove_first();
76     DEBUG_ONLY(EXPECT_FALSE(lst.contains(c));)
77     context.return_chunk(c);
78   }
79 
80   EXPECT_EQ(lst.count(), 0);
81   EXPECT_EQ(lst.calc_committed_word_size(), (size_t)0);
82 
83 }
84 
TEST_VM(metaspace,freechunklist)85 TEST_VM(metaspace, freechunklist) {
86 
87   ChunkGtestContext context;
88 
89   FreeChunkListVector lst;
90 
91   MemRangeCounter cnt;
92   MemRangeCounter committed_cnt;
93 
94   // Add random chunks to list and check the counter apis (word_size, commited_word_size, num_chunks)
95   // Make every other chunk randomly uncommitted, and later we check that committed chunks are sorted in at the front
96   // of the lists.
97   for (int i = 0; i < 100; i++) {
98     Metachunk* c = NULL;
99     context.alloc_chunk_expect_success(&c, ChunkLevelRanges::all_chunks().random_value());
100     bool uncommitted_chunk = i % 3;
101     if (uncommitted_chunk) {
102       context.uncommit_chunk_with_test(c);
103       c->set_in_use();
104     }
105 
106     lst.add(c);
107 
108     LOG("->" METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c));
109 
110     cnt.add(c->word_size());
111     committed_cnt.add(c->committed_words());
112 
113     EXPECT_EQ(lst.num_chunks(), (int)cnt.count());
114     EXPECT_EQ(lst.word_size(), cnt.total_size());
115     EXPECT_EQ(lst.calc_committed_word_size(), committed_cnt.total_size());
116   }
117 
118   // Drain each list separately, front to back. While draining observe the order
119   //  in which the chunks come: since uncommitted chunks are added to the tail of
120   //  the list (see FreeChunkList::add_chunk()), no committed chunk should ever
121   //  follow an uncommitted chunk.
122   for (chunklevel_t lvl = LOWEST_CHUNK_LEVEL; lvl <= HIGHEST_CHUNK_LEVEL; lvl++) {
123     Metachunk* c = lst.remove_first(lvl);
124     bool found_uncommitted = false;
125     while (c != NULL) {
126 
127       LOG("<-" METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c));
128 
129       if (found_uncommitted) {
130         EXPECT_TRUE(c->is_fully_uncommitted());
131       } else {
132         found_uncommitted = c->is_fully_uncommitted();
133       }
134 
135       cnt.sub(c->word_size());
136       committed_cnt.sub(c->committed_words());
137 
138       EXPECT_EQ(lst.num_chunks(), (int)cnt.count());
139       EXPECT_EQ(lst.word_size(), cnt.total_size());
140       EXPECT_EQ(lst.calc_committed_word_size(), committed_cnt.total_size());
141 
142       context.return_chunk(c);
143 
144       c = lst.remove_first(lvl);
145     }
146   }
147 
148 }
149 
150 // Test, for a list populated with a mixture of fully/partially/uncommitted chunks,
151 // the retrieval-by-minimally-committed-words function.
TEST_VM(metaspace,freechunklist_retrieval)152 TEST_VM(metaspace, freechunklist_retrieval) {
153 
154   if (Settings::new_chunks_are_fully_committed()) {
155     return;
156   }
157 
158   ChunkGtestContext context;
159   FreeChunkList fcl;
160   Metachunk* c = NULL;
161 
162   // For a chunk level which allows us to have partially committed chunks...
163   const size_t chunk_word_size = Settings::commit_granule_words() * 4;
164   const chunklevel_t lvl = level_fitting_word_size(chunk_word_size);
165 
166   // get some chunks:
167 
168   // ...a completely uncommitted one ...
169   Metachunk* c_0 = NULL;
170   context.alloc_chunk_expect_success(&c_0, lvl, lvl, 0);
171 
172   // ... a fully committed one ...
173   Metachunk* c_full = NULL;
174   context.alloc_chunk_expect_success(&c_full, lvl);
175 
176   // ... a chunk with one commit granule committed ...
177   Metachunk* c_1g = NULL;
178   context.alloc_chunk_expect_success(&c_1g, lvl, lvl, Settings::commit_granule_words());
179 
180   // ... a chunk with two commit granules committed.
181   Metachunk* c_2g = NULL;
182   context.alloc_chunk_expect_success(&c_2g, lvl, lvl, Settings::commit_granule_words() * 2);
183 
184   LOG("c_0: " METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c_0));
185   LOG("c_full: " METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c_full));
186   LOG("c_1g: " METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c_1g));
187   LOG("c_2g: " METACHUNK_FULL_FORMAT, METACHUNK_FULL_FORMAT_ARGS(c_2g));
188 
189 
190   // Simple check 1. Empty list should yield nothing.
191   {
192     c = fcl.first_minimally_committed(0);
193     ASSERT_NULL(c);
194   }
195 
196   // Simple check 2. Just a single uncommitted chunk.
197   {
198     fcl.add(c_0);
199     c = fcl.first_minimally_committed(0);
200     ASSERT_EQ(c_0, c);
201     c = fcl.first_minimally_committed(1);
202     ASSERT_NULL(c);
203     fcl.remove(c_0);
204   }
205 
206   // Now a check with a fully populated list.
207   //  For different insert orders, try to retrieve different chunks by minimal commit level
208   //  and check the result.
209   for (int insert_order = 0; insert_order < 4; insert_order ++) {
210 
211     switch (insert_order) {
212     case 0:
213       fcl.add(c_0);
214       fcl.add(c_full);
215       fcl.add(c_1g);
216       fcl.add(c_2g);
217       break;
218     case 1:
219       fcl.add(c_1g);
220       fcl.add(c_2g);
221       fcl.add(c_0);
222       fcl.add(c_full);
223       break;
224     case 2:
225       fcl.add(c_2g);
226       fcl.add(c_1g);
227       fcl.add(c_full);
228       fcl.add(c_0);
229       break;
230     case 3:
231       fcl.add(c_full);
232       fcl.add(c_2g);
233       fcl.add(c_1g);
234       fcl.add(c_0);
235       break;
236     }
237 
238     c = fcl.first_minimally_committed(0);
239     ASSERT_TRUE(c == c_full || c == c_0 || c == c_1g || c == c_2g);
240 
241     c = fcl.first_minimally_committed(1);
242     ASSERT_TRUE(c == c_full || c == c_1g || c == c_2g);
243 
244     c = fcl.first_minimally_committed(Settings::commit_granule_words());
245     ASSERT_TRUE(c == c_full || c == c_1g || c == c_2g);
246 
247     c = fcl.first_minimally_committed(Settings::commit_granule_words() + 1);
248     ASSERT_TRUE(c == c_full || c == c_2g);
249 
250     c = fcl.first_minimally_committed(Settings::commit_granule_words() * 2);
251     ASSERT_TRUE(c == c_full || c == c_2g);
252 
253     c = fcl.first_minimally_committed((Settings::commit_granule_words() * 2) + 1);
254     ASSERT_TRUE(c == c_full);
255 
256     c = fcl.first_minimally_committed(chunk_word_size);
257     ASSERT_TRUE(c == c_full);
258 
259     c = fcl.first_minimally_committed(chunk_word_size + 1);
260     ASSERT_NULL(c);
261 
262     fcl.remove(c_0);
263     fcl.remove(c_full);
264     fcl.remove(c_1g);
265     fcl.remove(c_2g);
266 
267   }
268 
269   context.return_chunk(c_0);
270   context.return_chunk(c_full);
271   context.return_chunk(c_1g);
272   context.return_chunk(c_2g);
273 
274 }
275 
276