1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
// Copyright 2018-present the CoreDHCP Authors. All rights reserved
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.
package bitmap
import (
"math"
"math/rand"
"net"
"testing"
"github.com/bits-and-blooms/bitset"
)
func getAllocator(bits int) *Allocator {
_, prefix, err := net.ParseCIDR("2001:db8::/56")
if err != nil {
panic(err)
}
alloc, err := NewBitmapAllocator(*prefix, 56+bits)
if err != nil {
panic(err)
}
return alloc
}
func TestAlloc(t *testing.T) {
alloc := getAllocator(8)
net, err := alloc.Allocate(net.IPNet{})
if err != nil {
t.Fatal(err)
}
err = alloc.Free(net)
if err != nil {
t.Fatal(err)
}
err = alloc.Free(net)
if err == nil {
t.Fatal("Expected DoubleFree error")
}
}
func TestExhaust(t *testing.T) {
_, prefix, _ := net.ParseCIDR("2001:db8::/62")
alloc, _ := NewBitmapAllocator(*prefix, 64)
allocd := []net.IPNet{}
for i := 0; i < 4; i++ {
net, err := alloc.Allocate(net.IPNet{Mask: net.CIDRMask(64, 128)})
if err != nil {
t.Fatalf("Error before exhaustion: %v", err)
}
allocd = append(allocd, net)
}
_, err := alloc.Allocate(net.IPNet{})
if err == nil {
t.Fatalf("Successfully allocated more prefixes than there are in the pool")
}
err = alloc.Free(allocd[1])
if err != nil {
t.Fatalf("Could not free: %v", err)
}
net, err := alloc.Allocate(allocd[1])
if err != nil {
t.Fatalf("Could not reallocate after free: %v", err)
}
if !net.IP.Equal(allocd[1].IP) || net.Mask.String() != allocd[1].Mask.String() {
t.Fatalf("Did not obtain the right network after free: got %v, expected %v", net, allocd[1])
}
}
func TestOutOfPool(t *testing.T) {
alloc := getAllocator(8)
_, prefix, _ := net.ParseCIDR("fe80:abcd::/48")
res, err := alloc.Allocate(*prefix)
if err != nil {
t.Fatalf("Failed to allocate with invalid hint: %v", err)
}
if !alloc.containing.Contains(res.IP) {
t.Fatal("Obtained prefix outside of range: ", res)
}
if prefLen, totalLen := res.Mask.Size(); prefLen != 64 || totalLen != 128 {
t.Fatalf("Prefixes have wrong size %d/%d", prefLen, totalLen)
}
}
func prefixSizeForAllocs(allocs int) int {
return int(math.Ceil(math.Log2(float64(allocs))))
}
// Benchmark parallel Allocate, when the bitmap is mostly empty and we're allocating few values
// compared to the available allocations
func BenchmarkParallelAllocInitiallyEmpty(b *testing.B) {
// Run with -race to debug concurrency issues
alloc := getAllocator(prefixSizeForAllocs(b.N) + 2) // Use max 25% of the bitmap (initially empty)
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
if net, err := alloc.Allocate(net.IPNet{}); err != nil {
b.Logf("Could not allocate (got %v and an error): %v", net, err)
b.Fail()
}
}
})
}
func BenchmarkParallelAllocPartiallyFilled(b *testing.B) {
// We'll make a bitmap with 2x the number of allocs we want to make.
// Then randomly fill it to about 50% utilization
alloc := getAllocator(prefixSizeForAllocs(b.N) + 1)
// Build a replacement bitmap that we'll put in the allocator, with approx. 50% of values filled
newbmap := make([]uint64, alloc.bitmap.Len())
for i := uint(0); i < alloc.bitmap.Len(); i++ {
newbmap[i] = rand.Uint64()
}
alloc.bitmap = bitset.From(newbmap)
b.ResetTimer()
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
if net, err := alloc.Allocate(net.IPNet{}); err != nil {
b.Logf("Could not allocate (got %v and an error): %v", net, err)
b.Fail()
}
}
})
}
|
