libgo/go/runtime/treap_test.go

   1 // Copyright 2019 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package runtime_test
   6
   7 import (
   8         "fmt"
   9         "runtime"
  10         "testing"
  11 )
  12
  13 var spanDesc = map[uintptr]struct {
  14         pages uintptr
  15         scav  bool
  16 }{
  17         0xc0000000: {2, false},
  18         0xc0006000: {1, false},
  19         0xc0010000: {8, false},
  20         0xc0022000: {7, false},
  21         0xc0034000: {4, true},
  22         0xc0040000: {5, false},
  23         0xc0050000: {5, true},
  24         0xc0060000: {5000, false},
  25 }
  26
  27 // Wrap the Treap one more time because go:notinheap doesn't
  28 // actually follow a structure across package boundaries.
  29 //
  30 //go:notinheap
  31 type treap struct {
  32         runtime.Treap
  33 }
  34
  35 func maskMatchName(mask, match runtime.TreapIterType) string {
  36         return fmt.Sprintf("%0*b-%0*b", runtime.TreapIterBits, uint8(mask), runtime.TreapIterBits, uint8(match))
  37 }
  38
  39 func TestTreapFilter(t *testing.T) {
  40         var iterTypes = [...]struct {
  41                 mask, match runtime.TreapIterType
  42                 filter      runtime.TreapIterFilter // expected filter
  43         }{
  44                 {0, 0, 0xf},
  45                 {runtime.TreapIterScav, 0, 0x5},
  46                 {runtime.TreapIterScav, runtime.TreapIterScav, 0xa},
  47                 {runtime.TreapIterScav | runtime.TreapIterHuge, runtime.TreapIterHuge, 0x4},
  48                 {runtime.TreapIterScav | runtime.TreapIterHuge, 0, 0x1},
  49                 {0, runtime.TreapIterScav, 0x0},
  50         }
  51         for _, it := range iterTypes {
  52                 t.Run(maskMatchName(it.mask, it.match), func(t *testing.T) {
  53                         if f := runtime.TreapFilter(it.mask, it.match); f != it.filter {
  54                                 t.Fatalf("got %#x, want %#x", f, it.filter)
  55                         }
  56                 })
  57         }
  58 }
  59
  60 // This test ensures that the treap implementation in the runtime
  61 // maintains all stated invariants after different sequences of
  62 // insert, removeSpan, find, and erase. Invariants specific to the
  63 // treap data structure are checked implicitly: after each mutating
  64 // operation, treap-related invariants are checked for the entire
  65 // treap.
  66 func TestTreap(t *testing.T) {
  67         // Set up a bunch of spans allocated into mheap_.
  68         // Also, derive a set of typeCounts of each type of span
  69         // according to runtime.TreapIterType so we can verify against
  70         // them later.
  71         spans := make([]runtime.Span, 0, len(spanDesc))
  72         typeCounts := [1 << runtime.TreapIterBits][1 << runtime.TreapIterBits]int{}
  73         for base, de := range spanDesc {
  74                 s := runtime.AllocSpan(base, de.pages, de.scav)
  75                 defer s.Free()
  76                 spans = append(spans, s)
  77
  78                 for i := runtime.TreapIterType(0); i < 1<<runtime.TreapIterBits; i++ {
  79                         for j := runtime.TreapIterType(0); j < 1<<runtime.TreapIterBits; j++ {
  80                                 if s.MatchesIter(i, j) {
  81                                         typeCounts[i][j]++
  82                                 }
  83                         }
  84                 }
  85         }
  86         t.Run("TypeCountsSanity", func(t *testing.T) {
  87                 // Just sanity check type counts for a few values.
  88                 check := func(mask, match runtime.TreapIterType, count int) {
  89                         tc := typeCounts[mask][match]
  90                         if tc != count {
  91                                 name := maskMatchName(mask, match)
  92                                 t.Fatalf("failed a sanity check for mask/match %s counts: got %d, wanted %d", name, tc, count)
  93                         }
  94                 }
  95                 check(0, 0, len(spanDesc))
  96                 check(runtime.TreapIterScav, 0, 6)
  97                 check(runtime.TreapIterScav, runtime.TreapIterScav, 2)
  98         })
  99         t.Run("Insert", func(t *testing.T) {
 100                 tr := treap{}
 101                 // Test just a very basic insert/remove for sanity.
 102                 tr.Insert(spans[0])
 103                 tr.RemoveSpan(spans[0])
 104         })
 105         t.Run("FindTrivial", func(t *testing.T) {
 106                 tr := treap{}
 107                 // Test just a very basic find operation for sanity.
 108                 tr.Insert(spans[0])
 109                 i := tr.Find(1)
 110                 if i.Span() != spans[0] {
 111                         t.Fatal("found unknown span in treap")
 112                 }
 113                 tr.RemoveSpan(spans[0])
 114         })
 115         t.Run("FindFirstFit", func(t *testing.T) {
 116                 // Run this 10 times, recreating the treap each time.
 117                 // Because of the non-deterministic structure of a treap,
 118                 // we'll be able to test different structures this way.
 119                 for i := 0; i < 10; i++ {
 120                         tr := runtime.Treap{}
 121                         for _, s := range spans {
 122                                 tr.Insert(s)
 123                         }
 124                         i := tr.Find(5)
 125                         if i.Span().Base() != 0xc0010000 {
 126                                 t.Fatalf("expected span at lowest address which could fit 5 pages, instead found span at %x", i.Span().Base())
 127                         }
 128                         for _, s := range spans {
 129                                 tr.RemoveSpan(s)
 130                         }
 131                 }
 132         })
 133         t.Run("Iterate", func(t *testing.T) {
 134                 for mask := runtime.TreapIterType(0); mask < 1<<runtime.TreapIterBits; mask++ {
 135                         for match := runtime.TreapIterType(0); match < 1<<runtime.TreapIterBits; match++ {
 136                                 iterName := maskMatchName(mask, match)
 137                                 t.Run(iterName, func(t *testing.T) {
 138                                         t.Run("StartToEnd", func(t *testing.T) {
 139                                                 // Ensure progressing an iterator actually goes over the whole treap
 140                                                 // from the start and that it iterates over the elements in order.
 141                                                 // Furthermore, ensure that it only iterates over the relevant parts
 142                                                 // of the treap.
 143                                                 // Finally, ensures that Start returns a valid iterator.
 144                                                 tr := treap{}
 145                                                 for _, s := range spans {
 146                                                         tr.Insert(s)
 147                                                 }
 148                                                 nspans := 0
 149                                                 lastBase := uintptr(0)
 150                                                 for i := tr.Start(mask, match); i.Valid(); i = i.Next() {
 151                                                         nspans++
 152                                                         if lastBase > i.Span().Base() {
 153                                                                 t.Fatalf("not iterating in correct order: encountered base %x before %x", lastBase, i.Span().Base())
 154                                                         }
 155                                                         lastBase = i.Span().Base()
 156                                                         if !i.Span().MatchesIter(mask, match) {
 157                                                                 t.Fatalf("found non-matching span while iteration over mask/match %s: base %x", iterName, i.Span().Base())
 158                                                         }
 159                                                 }
 160                                                 if nspans != typeCounts[mask][match] {
 161                                                         t.Fatal("failed to iterate forwards over full treap")
 162                                                 }
 163                                                 for _, s := range spans {
 164                                                         tr.RemoveSpan(s)
 165                                                 }
 166                                         })
 167                                         t.Run("EndToStart", func(t *testing.T) {
 168                                                 // See StartToEnd tests.
 169                                                 tr := treap{}
 170                                                 for _, s := range spans {
 171                                                         tr.Insert(s)
 172                                                 }
 173                                                 nspans := 0
 174                                                 lastBase := ^uintptr(0)
 175                                                 for i := tr.End(mask, match); i.Valid(); i = i.Prev() {
 176                                                         nspans++
 177                                                         if lastBase < i.Span().Base() {
 178                                                                 t.Fatalf("not iterating in correct order: encountered base %x before %x", lastBase, i.Span().Base())
 179                                                         }
 180                                                         lastBase = i.Span().Base()
 181                                                         if !i.Span().MatchesIter(mask, match) {
 182                                                                 t.Fatalf("found non-matching span while iteration over mask/match %s: base %x", iterName, i.Span().Base())
 183                                                         }
 184                                                 }
 185                                                 if nspans != typeCounts[mask][match] {
 186                                                         t.Fatal("failed to iterate backwards over full treap")
 187                                                 }
 188                                                 for _, s := range spans {
 189                                                         tr.RemoveSpan(s)
 190                                                 }
 191                                         })
 192                                 })
 193                         }
 194                 }
 195                 t.Run("Prev", func(t *testing.T) {
 196                         // Test the iterator invariant that i.prev().next() == i.
 197                         tr := treap{}
 198                         for _, s := range spans {
 199                                 tr.Insert(s)
 200                         }
 201                         i := tr.Start(0, 0).Next().Next()
 202                         p := i.Prev()
 203                         if !p.Valid() {
 204                                 t.Fatal("i.prev() is invalid")
 205                         }
 206                         if p.Next().Span() != i.Span() {
 207                                 t.Fatal("i.prev().next() != i")
 208                         }
 209                         for _, s := range spans {
 210                                 tr.RemoveSpan(s)
 211                         }
 212                 })
 213                 t.Run("Next", func(t *testing.T) {
 214                         // Test the iterator invariant that i.next().prev() == i.
 215                         tr := treap{}
 216                         for _, s := range spans {
 217                                 tr.Insert(s)
 218                         }
 219                         i := tr.Start(0, 0).Next().Next()
 220                         n := i.Next()
 221                         if !n.Valid() {
 222                                 t.Fatal("i.next() is invalid")
 223                         }
 224                         if n.Prev().Span() != i.Span() {
 225                                 t.Fatal("i.next().prev() != i")
 226                         }
 227                         for _, s := range spans {
 228                                 tr.RemoveSpan(s)
 229                         }
 230                 })
 231         })
 232         t.Run("EraseOne", func(t *testing.T) {
 233                 // Test that erasing one iterator correctly retains
 234                 // all relationships between elements.
 235                 tr := treap{}
 236                 for _, s := range spans {
 237                         tr.Insert(s)
 238                 }
 239                 i := tr.Start(0, 0).Next().Next().Next()
 240                 s := i.Span()
 241                 n := i.Next()
 242                 p := i.Prev()
 243                 tr.Erase(i)
 244                 if n.Prev().Span() != p.Span() {
 245                         t.Fatal("p, n := i.Prev(), i.Next(); n.prev() != p after i was erased")
 246                 }
 247                 if p.Next().Span() != n.Span() {
 248                         t.Fatal("p, n := i.Prev(), i.Next(); p.next() != n after i was erased")
 249                 }
 250                 tr.Insert(s)
 251                 for _, s := range spans {
 252                         tr.RemoveSpan(s)
 253                 }
 254         })
 255         t.Run("EraseAll", func(t *testing.T) {
 256                 // Test that erasing iterators actually removes nodes from the treap.
 257                 tr := treap{}
 258                 for _, s := range spans {
 259                         tr.Insert(s)
 260                 }
 261                 for i := tr.Start(0, 0); i.Valid(); {
 262                         n := i.Next()
 263                         tr.Erase(i)
 264                         i = n
 265                 }
 266                 if size := tr.Size(); size != 0 {
 267                         t.Fatalf("should have emptied out treap, %d spans left", size)
 268                 }
 269         })
 270 }