1 // Copyright 2021 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 #include <iostream>
16 #include <random>
17 #include <vector>
18 
19 #include "gmock/gmock.h"
20 #include "gtest/gtest.h"
21 #include "absl/base/config.h"
22 #include "absl/strings/cord.h"
23 #include "absl/strings/internal/cord_internal.h"
24 #include "absl/strings/internal/cord_rep_btree.h"
25 #include "absl/strings/internal/cord_rep_flat.h"
26 #include "absl/strings/internal/cord_rep_ring.h"
27 #include "absl/strings/internal/cordz_info.h"
28 #include "absl/strings/internal/cordz_sample_token.h"
29 #include "absl/strings/internal/cordz_statistics.h"
30 #include "absl/strings/internal/cordz_update_scope.h"
31 #include "absl/strings/internal/cordz_update_tracker.h"
32 #include "absl/synchronization/internal/thread_pool.h"
33 #include "absl/synchronization/notification.h"
34 
35 namespace absl {
36 ABSL_NAMESPACE_BEGIN
37 namespace cord_internal {
38 
39 // Do not print statistics contents, the matcher prints them as needed.
PrintTo(const CordzStatistics & stats,std::ostream * s)40 inline void PrintTo(const CordzStatistics& stats, std::ostream* s) {
41   if (s) *s << "CordzStatistics{...}";
42 }
43 
44 namespace {
45 
46 using ::testing::Ge;
47 
48 // Creates a flat of the specified allocated size
Flat(size_t size)49 CordRepFlat* Flat(size_t size) {
50   // Round up to a tag size, as we are going to poke an exact tag size back into
51   // the allocated flat. 'size returning allocators' could grant us more than we
52   // wanted, but we are ok to poke the 'requested' size in the tag, even in the
53   // presence of sized deletes, so we need to make sure the size rounds
54   // perfectly to a tag value.
55   assert(size >= kMinFlatSize);
56   size = RoundUpForTag(size);
57   CordRepFlat* flat = CordRepFlat::New(size - kFlatOverhead);
58   flat->tag = AllocatedSizeToTag(size);
59   flat->length = size - kFlatOverhead;
60   return flat;
61 }
62 
63 // Creates an external of the specified length
External(int length=512)64 CordRepExternal* External(int length = 512) {
65   return static_cast<CordRepExternal*>(
66       NewExternalRep(absl::string_view("", length), [](absl::string_view) {}));
67 }
68 
69 // Creates a substring on the provided rep of length - 1
Substring(CordRep * rep)70 CordRepSubstring* Substring(CordRep* rep) {
71   auto* substring = new CordRepSubstring;
72   substring->length = rep->length - 1;
73   substring->tag = SUBSTRING;
74   substring->child = rep;
75   return substring;
76 }
77 
78 // Creates a concat on the provided reps
Concat(CordRep * left,CordRep * right)79 CordRepConcat* Concat(CordRep* left, CordRep* right) {
80   auto* concat = new CordRepConcat;
81   concat->length = left->length + right->length;
82   concat->tag = CONCAT;
83   concat->left = left;
84   concat->right = right;
85   return concat;
86 }
87 
88 // Reference count helper
89 struct RefHelper {
90   std::vector<CordRep*> refs;
91 
~RefHelperabsl::cord_internal::__anon41b934eb0111::RefHelper92   ~RefHelper() {
93     for (CordRep* rep : refs) {
94       CordRep::Unref(rep);
95     }
96   }
97 
98   // Invokes CordRep::Unref() on `rep` when this instance is destroyed.
99   template <typename T>
NeedsUnrefabsl::cord_internal::__anon41b934eb0111::RefHelper100   T* NeedsUnref(T* rep) {
101     refs.push_back(rep);
102     return rep;
103   }
104 
105   // Adds `n` reference counts to `rep` which will be unreffed when this
106   // instance is destroyed.
107   template <typename T>
Refabsl::cord_internal::__anon41b934eb0111::RefHelper108   T* Ref(T* rep, size_t n = 1) {
109     while (n--) {
110       NeedsUnref(CordRep::Ref(rep));
111     }
112     return rep;
113   }
114 };
115 
116 // Sizeof helper. Returns the allocated size of `p`, excluding any child
117 // elements for substring, concat and ring cord reps.
118 template <typename T>
SizeOf(const T * rep)119 size_t SizeOf(const T* rep) {
120   return sizeof(T);
121 }
122 
123 template <>
SizeOf(const CordRepFlat * rep)124 size_t SizeOf(const CordRepFlat* rep) {
125   return rep->AllocatedSize();
126 }
127 
128 template <>
SizeOf(const CordRepExternal * rep)129 size_t SizeOf(const CordRepExternal* rep) {
130   // See cord.cc
131   return sizeof(CordRepExternalImpl<intptr_t>) + rep->length;
132 }
133 
134 template <>
SizeOf(const CordRepRing * rep)135 size_t SizeOf(const CordRepRing* rep) {
136   return CordRepRing::AllocSize(rep->capacity());
137 }
138 
139 // Computes fair share memory used in a naive 'we dare to recurse' way.
FairShareImpl(CordRep * rep,size_t ref)140 double FairShareImpl(CordRep* rep, size_t ref) {
141   double self = 0.0, children = 0.0;
142   ref *= rep->refcount.Get();
143   if (rep->tag >= FLAT) {
144     self = SizeOf(rep->flat());
145   } else if (rep->tag == EXTERNAL) {
146     self = SizeOf(rep->external());
147   } else if (rep->tag == SUBSTRING) {
148     self = SizeOf(rep->substring());
149     children = FairShareImpl(rep->substring()->child, ref);
150   } else if (rep->tag == BTREE) {
151     self = SizeOf(rep->btree());
152     for (CordRep*edge : rep->btree()->Edges()) {
153       children += FairShareImpl(edge, ref);
154     }
155   } else if (rep->tag == RING) {
156     self = SizeOf(rep->ring());
157     rep->ring()->ForEach([&](CordRepRing::index_type i) {
158       self += FairShareImpl(rep->ring()->entry_child(i), 1);
159     });
160   } else if (rep->tag == CONCAT) {
161     self = SizeOf(rep->concat());
162     children = FairShareImpl(rep->concat()->left, ref) +
163                FairShareImpl(rep->concat()->right, ref);
164   } else {
165     assert(false);
166   }
167   return self / ref + children;
168 }
169 
170 // Returns the fair share memory size from `ShareFhareImpl()` as a size_t.
FairShare(CordRep * rep,size_t ref=1)171 size_t FairShare(CordRep* rep, size_t ref = 1) {
172   return static_cast<size_t>(FairShareImpl(rep, ref));
173 }
174 
175 // Samples the cord and returns CordzInfo::GetStatistics()
SampleCord(CordRep * rep)176 CordzStatistics SampleCord(CordRep* rep) {
177   InlineData cord(rep);
178   CordzInfo::TrackCord(cord, CordzUpdateTracker::kUnknown);
179   CordzStatistics stats = cord.cordz_info()->GetCordzStatistics();
180   cord.cordz_info()->Untrack();
181   return stats;
182 }
183 
184 MATCHER_P(EqStatistics, stats, "Statistics equal expected values") {
185   bool ok = true;
186 
187 #define STATS_MATCHER_EXPECT_EQ(member)                              \
188   if (stats.member != arg.member) {                                  \
189     *result_listener << "\n    stats." << #member                    \
190                      << ": actual = " << arg.member << ", expected " \
191                      << stats.member;                                \
192     ok = false;                                                      \
193   }
194 
195   STATS_MATCHER_EXPECT_EQ(size);
196   STATS_MATCHER_EXPECT_EQ(node_count);
197   STATS_MATCHER_EXPECT_EQ(node_counts.flat);
198   STATS_MATCHER_EXPECT_EQ(node_counts.flat_64);
199   STATS_MATCHER_EXPECT_EQ(node_counts.flat_128);
200   STATS_MATCHER_EXPECT_EQ(node_counts.flat_256);
201   STATS_MATCHER_EXPECT_EQ(node_counts.flat_512);
202   STATS_MATCHER_EXPECT_EQ(node_counts.flat_1k);
203   STATS_MATCHER_EXPECT_EQ(node_counts.external);
204   STATS_MATCHER_EXPECT_EQ(node_counts.concat);
205   STATS_MATCHER_EXPECT_EQ(node_counts.substring);
206   STATS_MATCHER_EXPECT_EQ(node_counts.ring);
207   STATS_MATCHER_EXPECT_EQ(node_counts.btree);
208   STATS_MATCHER_EXPECT_EQ(estimated_memory_usage);
209   STATS_MATCHER_EXPECT_EQ(estimated_fair_share_memory_usage);
210 
211 #undef STATS_MATCHER_EXPECT_EQ
212 
213   return ok;
214 }
215 
TEST(CordzInfoStatisticsTest,Flat)216 TEST(CordzInfoStatisticsTest, Flat) {
217   RefHelper ref;
218   auto* flat = ref.NeedsUnref(Flat(512));
219 
220   CordzStatistics expected;
221   expected.size = flat->length;
222   expected.estimated_memory_usage = SizeOf(flat);
223   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
224   expected.node_count = 1;
225   expected.node_counts.flat = 1;
226   expected.node_counts.flat_512 = 1;
227 
228   EXPECT_THAT(SampleCord(flat), EqStatistics(expected));
229 }
230 
TEST(CordzInfoStatisticsTest,SharedFlat)231 TEST(CordzInfoStatisticsTest, SharedFlat) {
232   RefHelper ref;
233   auto* flat = ref.Ref(ref.NeedsUnref(Flat(64)));
234 
235   CordzStatistics expected;
236   expected.size = flat->length;
237   expected.estimated_memory_usage = SizeOf(flat);
238   expected.estimated_fair_share_memory_usage = SizeOf(flat) / 2;
239   expected.node_count = 1;
240   expected.node_counts.flat = 1;
241   expected.node_counts.flat_64 = 1;
242 
243   EXPECT_THAT(SampleCord(flat), EqStatistics(expected));
244 }
245 
TEST(CordzInfoStatisticsTest,External)246 TEST(CordzInfoStatisticsTest, External) {
247   RefHelper ref;
248   auto* external = ref.NeedsUnref(External());
249 
250   CordzStatistics expected;
251   expected.size = external->length;
252   expected.estimated_memory_usage = SizeOf(external);
253   expected.estimated_fair_share_memory_usage = SizeOf(external);
254   expected.node_count = 1;
255   expected.node_counts.external = 1;
256 
257   EXPECT_THAT(SampleCord(external), EqStatistics(expected));
258 }
259 
TEST(CordzInfoStatisticsTest,SharedExternal)260 TEST(CordzInfoStatisticsTest, SharedExternal) {
261   RefHelper ref;
262   auto* external = ref.Ref(ref.NeedsUnref(External()));
263 
264   CordzStatistics expected;
265   expected.size = external->length;
266   expected.estimated_memory_usage = SizeOf(external);
267   expected.estimated_fair_share_memory_usage = SizeOf(external) / 2;
268   expected.node_count = 1;
269   expected.node_counts.external = 1;
270 
271   EXPECT_THAT(SampleCord(external), EqStatistics(expected));
272 }
273 
TEST(CordzInfoStatisticsTest,Substring)274 TEST(CordzInfoStatisticsTest, Substring) {
275   RefHelper ref;
276   auto* flat = Flat(1024);
277   auto* substring = ref.NeedsUnref(Substring(flat));
278 
279   CordzStatistics expected;
280   expected.size = substring->length;
281   expected.estimated_memory_usage = SizeOf(substring) + SizeOf(flat);
282   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
283   expected.node_count = 2;
284   expected.node_counts.flat = 1;
285   expected.node_counts.flat_1k = 1;
286   expected.node_counts.substring = 1;
287 
288   EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
289 }
290 
TEST(CordzInfoStatisticsTest,SharedSubstring)291 TEST(CordzInfoStatisticsTest, SharedSubstring) {
292   RefHelper ref;
293   auto* flat = ref.Ref(Flat(511), 2);
294   auto* substring = ref.Ref(ref.NeedsUnref(Substring(flat)));
295 
296   CordzStatistics expected;
297   expected.size = substring->length;
298   expected.estimated_memory_usage = SizeOf(flat) + SizeOf(substring);
299   expected.estimated_fair_share_memory_usage =
300       SizeOf(substring) / 2 + SizeOf(flat) / 6;
301   expected.node_count = 2;
302   expected.node_counts.flat = 1;
303   expected.node_counts.flat_512 = 1;
304   expected.node_counts.substring = 1;
305 
306   EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
307 }
308 
TEST(CordzInfoStatisticsTest,Concat)309 TEST(CordzInfoStatisticsTest, Concat) {
310   RefHelper ref;
311   auto* flat1 = Flat(300);
312   auto* flat2 = Flat(2000);
313   auto* concat = ref.NeedsUnref(Concat(flat1, flat2));
314 
315   CordzStatistics expected;
316   expected.size = concat->length;
317   expected.estimated_memory_usage =
318       SizeOf(concat) + SizeOf(flat1) + SizeOf(flat2);
319   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
320   expected.node_count = 3;
321   expected.node_counts.flat = 2;
322   expected.node_counts.flat_512 = 1;
323   expected.node_counts.concat = 1;
324 
325   EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
326 }
327 
TEST(CordzInfoStatisticsTest,DeepConcat)328 TEST(CordzInfoStatisticsTest, DeepConcat) {
329   RefHelper ref;
330   auto* flat1 = Flat(300);
331   auto* flat2 = Flat(2000);
332   auto* flat3 = Flat(400);
333   auto* external = External(3000);
334   auto* substring = Substring(external);
335   auto* concat1 = Concat(flat1, flat2);
336   auto* concat2 = Concat(flat3, substring);
337   auto* concat = ref.NeedsUnref(Concat(concat1, concat2));
338 
339   CordzStatistics expected;
340   expected.size = concat->length;
341   expected.estimated_memory_usage = SizeOf(concat) * 3 + SizeOf(flat1) +
342                                     SizeOf(flat2) + SizeOf(flat3) +
343                                     SizeOf(external) + SizeOf(substring);
344   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
345 
346   expected.node_count = 8;
347   expected.node_counts.flat = 3;
348   expected.node_counts.flat_512 = 2;
349   expected.node_counts.external = 1;
350   expected.node_counts.concat = 3;
351   expected.node_counts.substring = 1;
352 
353   EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
354 }
355 
TEST(CordzInfoStatisticsTest,DeepSharedConcat)356 TEST(CordzInfoStatisticsTest, DeepSharedConcat) {
357   RefHelper ref;
358   auto* flat1 = Flat(40);
359   auto* flat2 = ref.Ref(Flat(2000), 4);
360   auto* flat3 = Flat(70);
361   auto* external = ref.Ref(External(3000));
362   auto* substring = ref.Ref(Substring(external), 3);
363   auto* concat1 = Concat(flat1, flat2);
364   auto* concat2 = Concat(flat3, substring);
365   auto* concat = ref.Ref(ref.NeedsUnref(Concat(concat1, concat2)));
366 
367   CordzStatistics expected;
368   expected.size = concat->length;
369   expected.estimated_memory_usage = SizeOf(concat) * 3 + SizeOf(flat1) +
370                                     SizeOf(flat2) + SizeOf(flat3) +
371                                     SizeOf(external) + SizeOf(substring);
372   expected.estimated_fair_share_memory_usage = FairShare(concat);
373   expected.node_count = 8;
374   expected.node_counts.flat = 3;
375   expected.node_counts.flat_64 = 1;
376   expected.node_counts.flat_128 = 1;
377   expected.node_counts.external = 1;
378   expected.node_counts.concat = 3;
379   expected.node_counts.substring = 1;
380 
381   EXPECT_THAT(SampleCord(concat), EqStatistics(expected));
382 }
383 
TEST(CordzInfoStatisticsTest,Ring)384 TEST(CordzInfoStatisticsTest, Ring) {
385   RefHelper ref;
386   auto* flat1 = Flat(240);
387   auto* flat2 = Flat(2000);
388   auto* flat3 = Flat(70);
389   auto* external = External(3000);
390   CordRepRing* ring = CordRepRing::Create(flat1);
391   ring = CordRepRing::Append(ring, flat2);
392   ring = CordRepRing::Append(ring, flat3);
393   ring = ref.NeedsUnref(CordRepRing::Append(ring, external));
394 
395   CordzStatistics expected;
396   expected.size = ring->length;
397   expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) +
398                                     SizeOf(flat2) + SizeOf(flat3) +
399                                     SizeOf(external);
400   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
401   expected.node_count = 5;
402   expected.node_counts.flat = 3;
403   expected.node_counts.flat_128 = 1;
404   expected.node_counts.flat_256 = 1;
405   expected.node_counts.external = 1;
406   expected.node_counts.ring = 1;
407 
408   EXPECT_THAT(SampleCord(ring), EqStatistics(expected));
409 }
410 
TEST(CordzInfoStatisticsTest,SharedSubstringRing)411 TEST(CordzInfoStatisticsTest, SharedSubstringRing) {
412   RefHelper ref;
413   auto* flat1 = ref.Ref(Flat(240));
414   auto* flat2 = Flat(200);
415   auto* flat3 = Flat(70);
416   auto* external = ref.Ref(External(3000), 5);
417   CordRepRing* ring = CordRepRing::Create(flat1);
418   ring = CordRepRing::Append(ring, flat2);
419   ring = CordRepRing::Append(ring, flat3);
420   ring = ref.Ref(CordRepRing::Append(ring, external), 4);
421   auto* substring = ref.Ref(ref.NeedsUnref(Substring(ring)));
422 
423 
424   CordzStatistics expected;
425   expected.size = substring->length;
426   expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) +
427                                     SizeOf(flat2) + SizeOf(flat3) +
428                                     SizeOf(external) + SizeOf(substring);
429   expected.estimated_fair_share_memory_usage = FairShare(substring);
430   expected.node_count = 6;
431   expected.node_counts.flat = 3;
432   expected.node_counts.flat_128 = 1;
433   expected.node_counts.flat_256 = 2;
434   expected.node_counts.external = 1;
435   expected.node_counts.ring = 1;
436   expected.node_counts.substring = 1;
437 
438   EXPECT_THAT(SampleCord(substring), EqStatistics(expected));
439 }
440 
TEST(CordzInfoStatisticsTest,BtreeLeaf)441 TEST(CordzInfoStatisticsTest, BtreeLeaf) {
442   ASSERT_THAT(CordRepBtree::kMaxCapacity, Ge(3));
443   RefHelper ref;
444   auto* flat1 = Flat(2000);
445   auto* flat2 = Flat(200);
446   auto* substr = Substring(flat2);
447   auto* external = External(3000);
448 
449   CordRepBtree* tree = CordRepBtree::Create(flat1);
450   tree = CordRepBtree::Append(tree, substr);
451   tree = CordRepBtree::Append(tree, external);
452   size_t flat3_count = CordRepBtree::kMaxCapacity - 3;
453   size_t flat3_size = 0;
454   for (size_t i = 0; i < flat3_count; ++i) {
455     auto* flat3 = Flat(70);
456     flat3_size += SizeOf(flat3);
457     tree = CordRepBtree::Append(tree, flat3);
458   }
459   ref.NeedsUnref(tree);
460 
461   CordzStatistics expected;
462   expected.size = tree->length;
463   expected.estimated_memory_usage = SizeOf(tree) + SizeOf(flat1) +
464                                     SizeOf(flat2) + SizeOf(substr) +
465                                     flat3_size + SizeOf(external);
466   expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage;
467   expected.node_count = 1 + 3 + 1 + flat3_count;
468   expected.node_counts.flat = 2 + flat3_count;
469   expected.node_counts.flat_128 = flat3_count;
470   expected.node_counts.flat_256 = 1;
471   expected.node_counts.external = 1;
472   expected.node_counts.substring = 1;
473   expected.node_counts.btree = 1;
474 
475   EXPECT_THAT(SampleCord(tree), EqStatistics(expected));
476 }
477 
TEST(CordzInfoStatisticsTest,BtreeNodeShared)478 TEST(CordzInfoStatisticsTest, BtreeNodeShared) {
479   RefHelper ref;
480   static constexpr int leaf_count = 3;
481   const size_t flat3_count = CordRepBtree::kMaxCapacity - 3;
482   ASSERT_THAT(flat3_count, Ge(0));
483 
484   CordRepBtree* tree = nullptr;
485   size_t mem_size = 0;
486   for (int i = 0; i < leaf_count; ++i) {
487     auto* flat1 = ref.Ref(Flat(2000), 9);
488     mem_size += SizeOf(flat1);
489     if (i == 0) {
490       tree = CordRepBtree::Create(flat1);
491     } else {
492       tree = CordRepBtree::Append(tree, flat1);
493     }
494 
495     auto* flat2 = Flat(200);
496     auto* substr = Substring(flat2);
497     mem_size += SizeOf(flat2) + SizeOf(substr);
498     tree = CordRepBtree::Append(tree, substr);
499 
500     auto* external = External(30);
501     mem_size += SizeOf(external);
502     tree = CordRepBtree::Append(tree, external);
503 
504     for (size_t i = 0; i < flat3_count; ++i) {
505       auto* flat3 = Flat(70);
506       mem_size += SizeOf(flat3);
507       tree = CordRepBtree::Append(tree, flat3);
508     }
509 
510     if (i == 0) {
511       mem_size += SizeOf(tree);
512     } else {
513       mem_size += SizeOf(tree->Edges().back()->btree());
514     }
515   }
516   ref.NeedsUnref(tree);
517 
518   // Ref count: 2 for top (add 1), 5 for leaf 0 (add 4).
519   ref.Ref(tree, 1);
520   ref.Ref(tree->Edges().front(), 4);
521 
522   CordzStatistics expected;
523   expected.size = tree->length;
524   expected.estimated_memory_usage = SizeOf(tree) + mem_size;
525   expected.estimated_fair_share_memory_usage = FairShare(tree);
526 
527   expected.node_count = 1 + leaf_count * (1 + 3 + 1 + flat3_count);
528   expected.node_counts.flat = leaf_count * (2 + flat3_count);
529   expected.node_counts.flat_128 = leaf_count * flat3_count;
530   expected.node_counts.flat_256 = leaf_count;
531   expected.node_counts.external = leaf_count;
532   expected.node_counts.substring = leaf_count;
533   expected.node_counts.btree = 1 + leaf_count;
534 
535   EXPECT_THAT(SampleCord(tree), EqStatistics(expected));
536 }
537 
TEST(CordzInfoStatisticsTest,ThreadSafety)538 TEST(CordzInfoStatisticsTest, ThreadSafety) {
539   Notification stop;
540   static constexpr int kNumThreads = 8;
541   int64_t sampled_node_count = 0;
542 
543   {
544     absl::synchronization_internal::ThreadPool pool(kNumThreads);
545 
546     // Run analyzer thread emulating a CordzHandler collection.
547     pool.Schedule([&]() {
548       while (!stop.HasBeenNotified()) {
549         // Run every 10us (about 100K total collections).
550         absl::SleepFor(absl::Microseconds(10));
551         CordzSampleToken token;
552         for (const CordzInfo& cord_info : token) {
553           CordzStatistics stats = cord_info.GetCordzStatistics();
554           sampled_node_count += stats.node_count;
555         }
556       }
557     });
558 
559     // Run 'application threads'
560     for (int i = 0; i < kNumThreads; ++i) {
561       pool.Schedule([&]() {
562         // Track 0 - 2 cordz infos at a time, providing permutations of 0, 1
563         // and 2 CordzHandle and CordzInfo queues being active, with plenty of
564         // 'empty to non empty' transitions.
565         InlineData cords[2];
566         std::minstd_rand gen;
567         std::uniform_int_distribution<int> coin_toss(0, 1);
568 
569         while (!stop.HasBeenNotified()) {
570           for (InlineData& cord : cords) {
571             // 50/50 flip the state of the cord
572             if (coin_toss(gen) != 0) {
573               if (cord.is_tree()) {
574                 // 50/50 simulate delete (untrack) or 'edit to empty'
575                 if (coin_toss(gen) != 0) {
576                   CordzInfo::MaybeUntrackCord(cord.cordz_info());
577                 } else {
578                   CordzUpdateScope scope(cord.cordz_info(),
579                                          CordzUpdateTracker::kUnknown);
580                   scope.SetCordRep(nullptr);
581                 }
582                 CordRep::Unref(cord.as_tree());
583                 cord.set_inline_size(0);
584               } else {
585                 // Coin toss to 25% ring, 25% btree, and 50% flat.
586                 CordRep* rep = Flat(256);
587                 if (coin_toss(gen) != 0) {
588                   if (coin_toss(gen) != 0) {
589                     rep = CordRepRing::Create(rep);
590                   } else {
591                     rep = CordRepBtree::Create(rep);
592                   }
593                 }
594                 cord.make_tree(rep);
595 
596                 // 50/50 sample
597                 if (coin_toss(gen) != 0) {
598                   CordzInfo::TrackCord(cord, CordzUpdateTracker::kUnknown);
599                 }
600               }
601             }
602           }
603         }
604         for (InlineData& cord : cords) {
605           if (cord.is_tree()) {
606             CordzInfo::MaybeUntrackCord(cord.cordz_info());
607             CordRep::Unref(cord.as_tree());
608           }
609         }
610       });
611     }
612 
613     // Run for 1 second to give memory and thread safety analyzers plenty of
614     // time to detect any mishaps or undefined behaviors.
615     absl::SleepFor(absl::Seconds(1));
616     stop.Notify();
617   }
618 
619   std::cout << "Sampled " << sampled_node_count << " nodes\n";
620 }
621 
622 }  // namespace
623 }  // namespace cord_internal
624 ABSL_NAMESPACE_END
625 }  // namespace absl
626