1// Copyright 2017 The Prometheus Authors
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14package tombstones
15
16import (
17	"io/ioutil"
18	"math"
19	"math/rand"
20	"os"
21	"sync"
22	"testing"
23	"time"
24
25	"github.com/go-kit/log"
26	"github.com/stretchr/testify/require"
27	"go.uber.org/goleak"
28)
29
30func TestMain(m *testing.M) {
31	goleak.VerifyTestMain(m)
32}
33
34func TestWriteAndReadbackTombstones(t *testing.T) {
35	tmpdir, _ := ioutil.TempDir("", "test")
36	defer func() {
37		require.NoError(t, os.RemoveAll(tmpdir))
38	}()
39
40	ref := uint64(0)
41
42	stones := NewMemTombstones()
43	// Generate the tombstones.
44	for i := 0; i < 100; i++ {
45		ref += uint64(rand.Int31n(10)) + 1
46		numRanges := rand.Intn(5) + 1
47		dranges := make(Intervals, 0, numRanges)
48		mint := rand.Int63n(time.Now().UnixNano())
49		for j := 0; j < numRanges; j++ {
50			dranges = dranges.Add(Interval{mint, mint + rand.Int63n(1000)})
51			mint += rand.Int63n(1000) + 1
52		}
53		stones.AddInterval(ref, dranges...)
54	}
55
56	_, err := WriteFile(log.NewNopLogger(), tmpdir, stones)
57	require.NoError(t, err)
58
59	restr, _, err := ReadTombstones(tmpdir)
60	require.NoError(t, err)
61
62	// Compare the two readers.
63	require.Equal(t, stones, restr)
64}
65
66func TestDeletingTombstones(t *testing.T) {
67	stones := NewMemTombstones()
68
69	ref := uint64(42)
70	mint := rand.Int63n(time.Now().UnixNano())
71	dranges := make(Intervals, 0, 1)
72	dranges = dranges.Add(Interval{mint, mint + rand.Int63n(1000)})
73	stones.AddInterval(ref, dranges...)
74	stones.AddInterval(uint64(43), dranges...)
75
76	intervals, err := stones.Get(ref)
77	require.NoError(t, err)
78	require.Equal(t, intervals, dranges)
79
80	stones.DeleteTombstones(map[uint64]struct{}{ref: struct{}{}})
81
82	intervals, err = stones.Get(ref)
83	require.NoError(t, err)
84	require.Empty(t, intervals)
85}
86
87func TestTruncateBefore(t *testing.T) {
88	cases := []struct {
89		before  Intervals
90		beforeT int64
91		after   Intervals
92	}{
93		{
94			before:  Intervals{{1, 2}, {4, 10}, {12, 100}},
95			beforeT: 3,
96			after:   Intervals{{4, 10}, {12, 100}},
97		},
98		{
99			before:  Intervals{{1, 2}, {4, 10}, {12, 100}, {200, 1000}},
100			beforeT: 900,
101			after:   Intervals{{200, 1000}},
102		},
103		{
104			before:  Intervals{{1, 2}, {4, 10}, {12, 100}, {200, 1000}},
105			beforeT: 2000,
106			after:   nil,
107		},
108		{
109			before:  Intervals{{1, 2}, {4, 10}, {12, 100}, {200, 1000}},
110			beforeT: 0,
111			after:   Intervals{{1, 2}, {4, 10}, {12, 100}, {200, 1000}},
112		},
113	}
114	for _, c := range cases {
115		ref := uint64(42)
116		stones := NewMemTombstones()
117		stones.AddInterval(ref, c.before...)
118
119		stones.TruncateBefore(c.beforeT)
120		ts, err := stones.Get(ref)
121		require.NoError(t, err)
122		require.Equal(t, c.after, ts)
123	}
124}
125
126func TestAddingNewIntervals(t *testing.T) {
127	cases := []struct {
128		exist Intervals
129		new   Interval
130
131		exp Intervals
132	}{
133		{
134			new: Interval{1, 2},
135			exp: Intervals{{1, 2}},
136		},
137		{
138			exist: Intervals{{1, 2}},
139			new:   Interval{1, 2},
140			exp:   Intervals{{1, 2}},
141		},
142		{
143			exist: Intervals{{1, 4}, {6, 6}},
144			new:   Interval{5, 6},
145			exp:   Intervals{{1, 6}},
146		},
147		{
148			exist: Intervals{{1, 10}, {12, 20}, {25, 30}},
149			new:   Interval{21, 25},
150			exp:   Intervals{{1, 10}, {12, 30}},
151		},
152		{
153			exist: Intervals{{1, 10}, {12, 20}, {25, 30}},
154			new:   Interval{22, 23},
155			exp:   Intervals{{1, 10}, {12, 20}, {22, 23}, {25, 30}},
156		},
157		{
158			exist: Intervals{{1, 2}, {3, 5}, {7, 7}},
159			new:   Interval{6, 7},
160			exp:   Intervals{{1, 2}, {3, 7}},
161		},
162		{
163			exist: Intervals{{1, 10}, {12, 20}, {25, 30}},
164			new:   Interval{18, 23},
165			exp:   Intervals{{1, 10}, {12, 23}, {25, 30}},
166		},
167		{
168			exist: Intervals{{1, 10}, {12, 20}, {25, 30}},
169			new:   Interval{9, 23},
170			exp:   Intervals{{1, 23}, {25, 30}},
171		},
172		{
173			exist: Intervals{{1, 10}, {12, 20}, {25, 30}},
174			new:   Interval{9, 230},
175			exp:   Intervals{{1, 230}},
176		},
177		{
178			exist: Intervals{{5, 10}, {12, 20}, {25, 30}},
179			new:   Interval{1, 4},
180			exp:   Intervals{{1, 10}, {12, 20}, {25, 30}},
181		},
182		{
183			exist: Intervals{{5, 10}, {12, 20}, {25, 30}},
184			new:   Interval{11, 14},
185			exp:   Intervals{{5, 20}, {25, 30}},
186		},
187		{
188			exist: Intervals{{5, 10}, {12, 20}, {25, 30}},
189			new:   Interval{1, 3},
190			exp:   Intervals{{1, 3}, {5, 10}, {12, 20}, {25, 30}},
191		},
192		{
193			exist: Intervals{{5, 10}, {12, 20}, {25, 30}},
194			new:   Interval{35, 40},
195			exp:   Intervals{{5, 10}, {12, 20}, {25, 30}, {35, 40}},
196		},
197		{
198			new: Interval{math.MinInt64, 2},
199			exp: Intervals{{math.MinInt64, 2}},
200		},
201		{
202			exist: Intervals{{math.MinInt64, 2}},
203			new:   Interval{9, math.MaxInt64},
204			exp:   Intervals{{math.MinInt64, 2}, {9, math.MaxInt64}},
205		},
206		{
207			exist: Intervals{{9, math.MaxInt64}},
208			new:   Interval{math.MinInt64, 2},
209			exp:   Intervals{{math.MinInt64, 2}, {9, math.MaxInt64}},
210		},
211		{
212			exist: Intervals{{9, math.MaxInt64}},
213			new:   Interval{math.MinInt64, 10},
214			exp:   Intervals{{math.MinInt64, math.MaxInt64}},
215		},
216	}
217
218	for _, c := range cases {
219		t.Run("", func(t *testing.T) {
220			require.Equal(t, c.exp, c.exist.Add(c.new))
221		})
222	}
223}
224
225// TestMemTombstonesConcurrency to make sure they are safe to access from different goroutines.
226func TestMemTombstonesConcurrency(t *testing.T) {
227	tomb := NewMemTombstones()
228	totalRuns := 100
229	var wg sync.WaitGroup
230	wg.Add(2)
231
232	go func() {
233		for x := 0; x < totalRuns; x++ {
234			tomb.AddInterval(uint64(x), Interval{int64(x), int64(x)})
235		}
236		wg.Done()
237	}()
238	go func() {
239		for x := 0; x < totalRuns; x++ {
240			_, err := tomb.Get(uint64(x))
241			require.NoError(t, err)
242		}
243		wg.Done()
244	}()
245	wg.Wait()
246}
247