1  package queue_test
  2  
  3  import (
  4  	"testing"
  5  	"time"
  6  
  7  	"github.com/lightningnetwork/lnd/queue"
  8  )
  9  
 10  // testItem is an item type we'll be using to test the GCQueue.
 11  type testItem uint32
 12  
 13  // TestGCQueueGCCycle asserts that items that are kept in the GCQueue past their
 14  // expiration will be released by a subsequent gc cycle.
 15  func TestGCQueueGCCycle(t *testing.T) {
 16  	t.Parallel()
 17  
 18  	const (
 19  		gcInterval     = time.Second
 20  		expiryInterval = 250 * time.Millisecond
 21  		numItems       = 6
 22  	)
 23  
 24  	newItem := func() interface{} { return new(testItem) }
 25  
 26  	bp := queue.NewGCQueue(newItem, 100, gcInterval, expiryInterval)
 27  
 28  	// Take numItems items from the queue, and immediately return them.
 29  	// Returning the items will trigger the gc ticker to start.
 30  	itemSet1 := takeN(t, bp, numItems)
 31  	returnAll(bp, itemSet1)
 32  
 33  	// Allow enough time for all expired items to be released by the queue.
 34  	<-time.After(gcInterval + expiryInterval)
 35  
 36  	// Take another set of numItems items from the queue.
 37  	itemSet2 := takeN(t, bp, numItems)
 38  
 39  	// Since the gc ticker should have elapsed, we expect the intersection
 40  	// of sets 1 and 2 to be empty.
 41  	for item := range itemSet2 {
 42  		if _, ok := itemSet1[item]; ok {
 43  			t.Fatalf("items taken should not have been reused")
 44  		}
 45  	}
 46  }
 47  
 48  // TestGCQueuePartialGCCycle asserts that the GCQueue will only garbage collect
 49  // the items in its queue that have fully expired. We test this by adding items
 50  // into the queue such that the garbage collection will occur before the items
 51  // expire. Taking items after the gc cycle should return the items that were not
 52  // released by the gc cycle.
 53  func TestGCQueuePartialGCCycle(t *testing.T) {
 54  	t.Parallel()
 55  
 56  	const (
 57  		gcInterval     = time.Second
 58  		expiryInterval = 250 * time.Millisecond
 59  		numItems       = 6
 60  	)
 61  
 62  	newItem := func() interface{} { return new(testItem) }
 63  
 64  	bp := queue.NewGCQueue(newItem, 100, gcInterval, expiryInterval)
 65  
 66  	// Take numItems items from the gc queue.
 67  	itemSet1 := takeN(t, bp, numItems)
 68  
 69  	// Immediately return half of the items, and construct a set of items
 70  	// consisting of the half that were not returned.
 71  	halfItemSet1 := returnN(t, bp, itemSet1, numItems/2)
 72  
 73  	// Wait long enough to ensure that adding subsequent items will not be
 74  	// released in the next gc cycle.
 75  	<-time.After(gcInterval - expiryInterval/2)
 76  
 77  	// Return the remaining items from itemSet1.
 78  	returnAll(bp, halfItemSet1)
 79  
 80  	// Wait until the gc cycle as done a sweep of the items and released all
 81  	// those that have expired.
 82  	<-time.After(expiryInterval / 2)
 83  
 84  	// Retrieve numItems items from the gc queue.
 85  	itemSet2 := takeN(t, bp, numItems)
 86  
 87  	// Tally the number of items returned from Take that are in the second
 88  	// half of items returned.
 89  	var numReused int
 90  	for item := range itemSet2 {
 91  		if _, ok := halfItemSet1[item]; ok {
 92  			numReused++
 93  		}
 94  	}
 95  
 96  	// We expect the number of reused items to be equal to half numItems.
 97  	if numReused != numItems/2 {
 98  		t.Fatalf("expected %d items to be reused, got %d",
 99  			numItems/2, numReused)
100  	}
101  }
102  
103  // takeN draws n items from the provided GCQueue. This method also asserts that
104  // n unique items are drawn, and then returns the resulting set.
105  func takeN(t *testing.T, q *queue.GCQueue, n int) map[interface{}]struct{} {
106  	t.Helper()
107  
108  	items := make(map[interface{}]struct{})
109  	for i := 0; i < n; i++ {
110  		// Wait a small duration to ensure the tests behave reliable,
111  		// and don't activate the non-blocking case unintentionally.
112  		<-time.After(time.Millisecond)
113  
114  		items[q.Take()] = struct{}{}
115  	}
116  
117  	if len(items) != n {
118  		t.Fatalf("items taken from gc queue should be distinct, "+
119  			"want %d unique items, got %d", n, len(items))
120  	}
121  
122  	return items
123  }
124  
125  // returnAll returns the items of the given set back to the GCQueue.
126  func returnAll(q *queue.GCQueue, items map[interface{}]struct{}) {
127  	for item := range items {
128  		q.Return(item)
129  
130  		// Wait a small duration to ensure the tests behave reliable,
131  		// and don't activate the non-blocking case unintentionally.
132  		<-time.After(time.Millisecond)
133  	}
134  }
135  
136  // returnN returns n items at random from the set of items back to the GCQueue.
137  // This method fails if the set's cardinality is smaller than n.
138  func returnN(t *testing.T, q *queue.GCQueue,
139  	items map[interface{}]struct{}, n int) map[interface{}]struct{} {
140  
141  	t.Helper()
142  
143  	var remainingItems = make(map[interface{}]struct{})
144  	var numReturned int
145  	for item := range items {
146  		if numReturned < n {
147  			q.Return(item)
148  			numReturned++
149  
150  			// Wait a small duration to ensure the tests behave
151  			// reliable, and don't activate the non-blocking case
152  			// unintentionally.
153  			<-time.After(time.Millisecond)
154  		} else {
155  			remainingItems[item] = struct{}{}
156  		}
157  	}
158  
159  	if numReturned < n {
160  		t.Fatalf("insufficient number of items to return, need %d, "+
161  			"got %d", n, numReturned)
162  	}
163  
164  	return remainingItems
165  }