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
|
// 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.
// This allocator only returns prefixes of a single size
// This is much simpler to implement (reduces the problem to an equivalent of
// single ip allocations), probably makes sense in cases where the available
// range is much larger than the expected number of clients. Also is what KEA
// does so at least it's not worse than that
package bitmap
import (
"errors"
"fmt"
"net"
"strconv"
"sync"
"github.com/bits-and-blooms/bitset"
"github.com/coredhcp/coredhcp/logger"
"github.com/coredhcp/coredhcp/plugins/allocators"
)
var log = logger.GetLogger("plugins/allocators/bitmap")
// Allocator is a prefix allocator allocating in chunks of a fixed size
// regardless of the size requested by the client.
// It consumes an amount of memory proportional to the total amount of available prefixes
type Allocator struct {
containing net.IPNet
page int
bitmap *bitset.BitSet
l sync.Mutex
}
// prefix must verify: containing.Mask.Size < prefix.Mask.Size < page
func (a *Allocator) toIndex(base net.IP) (uint, error) {
value, err := allocators.Offset(base, a.containing.IP, a.page)
if err != nil {
return 0, fmt.Errorf("Cannot compute prefix index: %w", err)
}
return uint(value), nil
}
func (a *Allocator) toPrefix(idx uint) (net.IP, error) {
return allocators.AddPrefixes(a.containing.IP, uint64(idx), uint64(a.page))
}
// Allocate reserves a maxsize-sized block and returns a block of size
// min(maxsize, hint.size)
func (a *Allocator) Allocate(hint net.IPNet) (ret net.IPNet, err error) {
// Ensure size is max(maxsize, hint.size)
reqSize, hintErr := hint.Mask.Size()
if reqSize < a.page || hintErr != 128 {
reqSize = a.page
}
ret.Mask = net.CIDRMask(reqSize, 128)
// Try to allocate the requested prefix
a.l.Lock()
defer a.l.Unlock()
if hint.IP.To16() != nil && a.containing.Contains(hint.IP) {
idx, hintErr := a.toIndex(hint.IP)
if hintErr == nil && !a.bitmap.Test(idx) {
a.bitmap.Set(idx)
ret.IP, err = a.toPrefix(idx)
return
}
}
// Find a free prefix
next, ok := a.bitmap.NextClear(0)
if !ok {
err = allocators.ErrNoAddrAvail
return
}
a.bitmap.Set(next)
ret.IP, err = a.toPrefix(next)
if err != nil {
// This violates the assumption that every index in the bitmap maps back to a valid prefix
err = fmt.Errorf("BUG: could not get prefix from allocation: %w", err)
a.bitmap.Clear(next)
}
return
}
// Free returns the given prefix to the available pool if it was taken.
func (a *Allocator) Free(prefix net.IPNet) error {
idx, err := a.toIndex(prefix.IP.Mask(prefix.Mask))
if err != nil {
return fmt.Errorf("Could not find prefix in pool: %w", err)
}
a.l.Lock()
defer a.l.Unlock()
if !a.bitmap.Test(idx) {
return &allocators.ErrDoubleFree{Loc: prefix}
}
a.bitmap.Clear(idx)
return nil
}
// NewBitmapAllocator creates a new allocator, allocating /`size` prefixes
// carved out of the given `pool` prefix
func NewBitmapAllocator(pool net.IPNet, size int) (*Allocator, error) {
poolSize, _ := pool.Mask.Size()
allocOrder := size - poolSize
if allocOrder < 0 {
return nil, errors.New("The size of allocated prefixes cannot be larger than the pool they're allocated from")
} else if allocOrder >= strconv.IntSize {
return nil, fmt.Errorf("A pool with more than 2^%d items is not representable", size-poolSize)
} else if allocOrder >= 32 {
log.Warningln("Using a pool of more than 2^32 elements may result in large memory consumption")
}
if !(1<<uint(allocOrder) <= bitset.Cap()) {
return nil, errors.New("Can't fit this pool using the bitmap allocator")
}
alloc := Allocator{
containing: pool,
page: size,
bitmap: bitset.New(1 << uint(allocOrder)),
}
return &alloc, nil
}
|
