/
allocator.go
342 lines (293 loc) · 8.66 KB
/
allocator.go
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
// Copyright 2021 Antrea Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package ipallocator
import (
"fmt"
"math/big"
"net"
"sync"
utilnet "k8s.io/utils/net"
)
type IPAllocator interface {
AllocateIP(ip net.IP) error
AllocateNext() (net.IP, error)
// Allocate range of continuous IPs in one go. If continuus chunk is not
// available, error will be returned.
AllocateRange(size int) ([]net.IP, error)
Release(ip net.IP) error
Used() int
Has(ip net.IP) bool
}
// SingleIPAllocator is responsible for allocating IPs from a contiguous IP range.
type SingleIPAllocator struct {
// The string format of the IP range. e.g. 10.10.10.0/24, or 10.10.10.10-10.10.10.20.
ipRangeStr string
mutex sync.RWMutex
// base is a cached version of the start IP in the CIDR range as a *big.Int.
base *big.Int
// max is the maximum size of the usable addresses in the range.
max int
// allocated is a bit array of the allocated items in the range.
allocated *big.Int
// count is the number of currently allocated elements in the range.
count int
// IPs inside the cidr not available for allocation
reservedIPs []net.IP
}
// NewCIDRAllocator creates an IPAllocator based on the provided CIDR.
func NewCIDRAllocator(cidr *net.IPNet, reservedIPs []net.IP) (*SingleIPAllocator, error) {
base := utilnet.BigForIP(cidr.IP)
// Start from "x.x.x.1".
base.Add(base, big.NewInt(1))
max := utilnet.RangeSize(cidr) - 1
if max < 0 {
return nil, fmt.Errorf("no available IP in %s", cidr.String())
}
// In case a big range occupies too much memory, allow at most 65536 IP for each IP range.
if max > 65536 {
max = 65536
}
allocator := &SingleIPAllocator{
ipRangeStr: cidr.String(),
base: base,
max: int(max),
allocated: big.NewInt(0),
count: 0,
reservedIPs: reservedIPs,
}
return allocator, nil
}
// NewIPRangeAllocator creates an IPAllocator based on the provided start IP and end IP.
// The start IP and end IP are inclusive.
func NewIPRangeAllocator(startIP, endIP net.IP) (*SingleIPAllocator, error) {
ipRangeStr := fmt.Sprintf("%s-%s", startIP.String(), endIP.String())
base := utilnet.BigForIP(startIP)
offset := big.NewInt(0).Sub(utilnet.BigForIP(endIP), base).Int64()
if offset < 0 {
return nil, fmt.Errorf("invalid IP range %s", ipRangeStr)
}
max := offset + 1
// In case a big range occupies too much memory, allow at most 65536 IP for each ipset.
if max > 65536 {
max = 65536
}
allocator := &SingleIPAllocator{
ipRangeStr: ipRangeStr,
base: base,
max: int(max),
allocated: big.NewInt(0),
count: 0,
}
return allocator, nil
}
func (a *SingleIPAllocator) Name() string {
return a.ipRangeStr
}
func (a *SingleIPAllocator) checkReserved(ip net.IP) error {
for _, reservedIP := range a.reservedIPs {
if reservedIP.Equal(ip) {
return fmt.Errorf("IP %v is reserved and not available for allocation", ip)
}
}
return nil
}
// AllocateIP allocates the specified IP. It returns error if the IP is not in the range or already allocated.
func (a *SingleIPAllocator) AllocateIP(ip net.IP) error {
offset := a.getOffset(ip)
if offset < 0 || offset >= a.max {
return fmt.Errorf("IP %v is not in the ipset", ip)
}
err := a.checkReserved(ip)
if err != nil {
return err
}
a.mutex.Lock()
defer a.mutex.Unlock()
if a.allocated.Bit(offset) == 1 {
return fmt.Errorf("IP %v is already allocated", ip)
}
a.allocated.SetBit(a.allocated, offset, 1)
a.count++
return nil
}
func (a *SingleIPAllocator) allocateOffset(i int) (net.IP, bool) {
if a.allocated.Bit(i) == 0 {
ip := utilnet.AddIPOffset(a.base, i)
if a.checkReserved(ip) != nil {
return nil, false
}
a.allocated.SetBit(a.allocated, i, 1)
a.count++
return ip, true
}
return nil, false
}
// AllocateNext allocates an IP from the IP range. It returns error if no IP is available.
func (a *SingleIPAllocator) AllocateNext() (net.IP, error) {
a.mutex.Lock()
defer a.mutex.Unlock()
if a.count >= a.max-len(a.reservedIPs) {
return nil, fmt.Errorf("no available IP")
}
for i := 0; i <= a.max; i++ {
if ip, ok := a.allocateOffset(i); ok {
return ip, nil
}
}
// we should never reach here
return nil, fmt.Errorf("no available IP")
}
// AllocateRange allocates continuous range of specified size. If not available, error is returned.
func (a *SingleIPAllocator) AllocateRange(size int) ([]net.IP, error) {
a.mutex.Lock()
defer a.mutex.Unlock()
if a.count+size > a.max-len(a.reservedIPs) {
return nil, fmt.Errorf("not enough available IPs")
}
rangeAvailable := func(offset int) bool {
for i := offset; i < offset+size; i++ {
ip := utilnet.AddIPOffset(a.base, i)
if a.checkReserved(ip) != nil || (a.allocated.Bit(i) == 1) {
return false
}
}
return true
}
for start := 0; start <= a.max-size; start++ {
// check if this continuous range is available
if rangeAvailable(start) {
// perform the actual allocation
ips := make([]net.IP, 0, size)
for i := 0; i < size; i++ {
offset := start + i
ip := utilnet.AddIPOffset(a.base, offset)
a.allocated.SetBit(a.allocated, i, 1)
a.count++
ips = append(ips, ip)
}
return ips, nil
}
}
return nil, fmt.Errorf("Continuous range of size %d is not available", size)
}
func (a *SingleIPAllocator) getOffset(ip net.IP) int {
return int(big.NewInt(0).Sub(utilnet.BigForIP(ip), a.base).Int64())
}
// Release releases the provided IP. It returns error if the IP is not in the range or not allocated.
func (a *SingleIPAllocator) Release(ip net.IP) error {
offset := a.getOffset(ip)
if offset < 0 || offset >= a.max {
return fmt.Errorf("IP %v is not in the ipset", ip)
}
a.mutex.Lock()
defer a.mutex.Unlock()
if a.allocated.Bit(offset) == 0 {
return fmt.Errorf("IP %v is not allocated", ip)
}
a.allocated.SetBit(a.allocated, offset, 0)
a.count--
return nil
}
// Used returns the number of the allocated IPs.
func (a *SingleIPAllocator) Used() int {
a.mutex.RLock()
defer a.mutex.RUnlock()
return a.count
}
// Free returns the number of free IPs.
func (a *SingleIPAllocator) Free() int {
a.mutex.RLock()
defer a.mutex.RUnlock()
return a.max - a.count - len(a.reservedIPs)
}
// Total returns the number total of IPs within the pool.
func (a *SingleIPAllocator) Total() int {
return a.max - len(a.reservedIPs)
}
// Has returns whether the provided IP is in the range or not.
func (a *SingleIPAllocator) Has(ip net.IP) bool {
offset := a.getOffset(ip)
return offset >= 0 && offset < a.max
}
// MultiIPAllocator is responsible for allocating IPs from multiple contiguous IP ranges.
type MultiIPAllocator []*SingleIPAllocator
func (ma MultiIPAllocator) Names() []string {
names := make([]string, 0, len(ma))
for _, a := range ma {
names = append(names, a.Name())
}
return names
}
func (ma MultiIPAllocator) AllocateIP(ip net.IP) error {
for _, a := range ma {
if err := a.AllocateIP(ip); err == nil {
return nil
}
}
return fmt.Errorf("cannot allocate IP %v in any range", ip)
}
func (ma MultiIPAllocator) AllocateNext() (net.IP, error) {
for _, a := range ma {
if ip, err := a.AllocateNext(); err == nil {
return ip, nil
}
}
return nil, fmt.Errorf("cannot allocate IP in any range")
}
// AllocateRange allocates continuous range of specified size.
// If not available in any allocator, error is returned.
func (ma MultiIPAllocator) AllocateRange(size int) ([]net.IP, error) {
if size > ma.Free() {
return nil, fmt.Errorf("Not enough IPs to reserve range of size %d", size)
}
for _, a := range ma {
if ips, err := a.AllocateRange(size); err == nil {
return ips, nil
}
}
return nil, fmt.Errorf("cannot allocate continuus IPs in any range")
}
func (ma MultiIPAllocator) Release(ip net.IP) error {
for _, a := range ma {
if err := a.Release(ip); err == nil {
return nil
}
}
return fmt.Errorf("cannot release IP in any range")
}
func (ma MultiIPAllocator) Used() int {
used := 0
for _, a := range ma {
used += a.Used()
}
return used
}
func (ma MultiIPAllocator) Free() int {
return ma.Total() - ma.Used()
}
func (ma MultiIPAllocator) Total() int {
total := 0
for _, a := range ma {
total += a.Total()
}
return total
}
func (ma MultiIPAllocator) Has(ip net.IP) bool {
for _, a := range ma {
if a.Has(ip) {
return true
}
}
return false
}