forked from metallb/metallb
-
Notifications
You must be signed in to change notification settings - Fork 0
/
allocator.go
371 lines (331 loc) · 10.4 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
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
package allocator // import "go.universe.tf/metallb/internal/allocator"
import (
"errors"
"fmt"
"math"
"net"
"strings"
"go.universe.tf/metallb/internal/config"
"github.com/mikioh/ipaddr"
)
// An Allocator tracks IP address pools and allocates addresses from them.
type Allocator struct {
pools map[string]*config.Pool
allocated map[string]*alloc // svc -> alloc
sharingKeyForIP map[string]*key // ip.String() -> assigned sharing key
portsInUse map[string]map[Port]string // ip.String() -> Port -> svc
servicesOnIP map[string]map[string]bool // ip.String() -> svc -> allocated?
poolIPsInUse map[string]map[string]int // poolName -> ip.String() -> number of users
poolServices map[string]int // poolName -> #services
}
// Port represents one port in use by a service.
type Port struct {
Proto string
Port int
}
// String returns a text description of the port.
func (p Port) String() string {
return fmt.Sprintf("%s/%d", p.Proto, p.Port)
}
type key struct {
sharing string
backend string
}
type alloc struct {
pool string
ip net.IP
ports []Port
key
}
// New returns an Allocator managing no pools.
func New() *Allocator {
return &Allocator{
pools: map[string]*config.Pool{},
allocated: map[string]*alloc{},
sharingKeyForIP: map[string]*key{},
portsInUse: map[string]map[Port]string{},
servicesOnIP: map[string]map[string]bool{},
poolIPsInUse: map[string]map[string]int{},
poolServices: map[string]int{},
}
}
// SetPools updates the set of address pools that the allocator owns.
func (a *Allocator) SetPools(pools map[string]*config.Pool) error {
// All the fancy sharing stuff only influences how new allocations
// can be created. For changing the underlying configuration, the
// only question we have to answer is: can we fit all allocated
// IPs into address pools under the new configuration?
for svc, alloc := range a.allocated {
if poolFor(pools, alloc.ip) == "" {
return fmt.Errorf("new config not compatible with assigned IPs: service %q cannot own %q under new config", svc, alloc.ip)
}
}
for n := range a.pools {
if pools[n] == nil {
stats.poolCapacity.DeleteLabelValues(n)
stats.poolActive.DeleteLabelValues(n)
stats.poolAllocated.DeleteLabelValues(n)
}
}
a.pools = pools
// Need to rearrange existing pool mappings and counts
for svc, alloc := range a.allocated {
pool := poolFor(a.pools, alloc.ip)
if pool != alloc.pool {
a.Unassign(svc)
alloc.pool = pool
// Use the internal assign, we know for a fact the IP is
// still usable.
a.assign(svc, alloc)
}
}
return nil
}
// assign unconditionally updates internal state to reflect svc's
// allocation of alloc. Caller must ensure that this call is safe.
func (a *Allocator) assign(svc string, alloc *alloc) {
a.Unassign(svc)
a.allocated[svc] = alloc
a.sharingKeyForIP[alloc.ip.String()] = &alloc.key
if a.portsInUse[alloc.ip.String()] == nil {
a.portsInUse[alloc.ip.String()] = map[Port]string{}
}
for _, port := range alloc.ports {
a.portsInUse[alloc.ip.String()][port] = svc
}
if a.servicesOnIP[alloc.ip.String()] == nil {
a.servicesOnIP[alloc.ip.String()] = map[string]bool{}
}
a.servicesOnIP[alloc.ip.String()][svc] = true
if a.poolIPsInUse[alloc.pool] == nil {
a.poolIPsInUse[alloc.pool] = map[string]int{}
}
a.poolIPsInUse[alloc.pool][alloc.ip.String()]++
a.poolServices[alloc.pool]++
stats.poolActive.WithLabelValues(alloc.pool).Set(float64(len(a.poolIPsInUse[alloc.pool])))
stats.poolActive.WithLabelValues(alloc.pool).Set(float64(a.poolServices[alloc.pool]))
}
// Assign assigns the requested ip to svc, if the assignment is
// permissible by sharingKey and backendKey.
func (a *Allocator) Assign(svc string, ip net.IP, ports []Port, sharingKey, backendKey string) error {
pool := poolFor(a.pools, ip)
if pool == "" {
return fmt.Errorf("%q is not allowed in config", ip)
}
sk := &key{
sharing: sharingKey,
backend: backendKey,
}
// Does the IP already have allocs? If so, needs to be the same
// sharing key, and have non-overlapping ports. If not, the
// proposed IP needs to be allowed by configuration.
if existingSK := a.sharingKeyForIP[ip.String()]; existingSK != nil {
if err := sharingOK(existingSK, sk); err != nil {
// Sharing key is incompatible. However, if the owner is
// the same service, and is the only user of the IP, we
// can just update its sharing key in place.
var otherSvcs []string
for otherSvc := range a.servicesOnIP[ip.String()] {
if otherSvc != svc {
otherSvcs = append(otherSvcs, otherSvc)
}
}
if len(otherSvcs) > 0 {
return fmt.Errorf("can't change sharing key for %q, address also in use by %s", svc, strings.Join(otherSvcs, ","))
}
}
for _, port := range ports {
if curSvc, ok := a.portsInUse[ip.String()][port]; ok && curSvc != svc {
return fmt.Errorf("port %s is already in use on %q", port, ip)
}
}
}
// Either the IP is entirely unused, or the requested use is
// compatible with existing uses. Assign! But unassign first, in
// case we're mutating an existing service (see the "already have
// an allocation" block above). Unassigning is idempotent, so it's
// unconditionally safe to do.
alloc := &alloc{
pool: pool,
ip: ip,
ports: make([]Port, len(ports)),
key: *sk,
}
for i, port := range ports {
port := port
alloc.ports[i] = port
}
a.assign(svc, alloc)
return nil
}
// Unassign frees the IP associated with service, if any.
func (a *Allocator) Unassign(svc string) bool {
if a.allocated[svc] == nil {
return false
}
al := a.allocated[svc]
delete(a.allocated, svc)
for _, port := range al.ports {
if curSvc := a.portsInUse[al.ip.String()][port]; curSvc != svc {
panic(fmt.Sprintf("incoherent state, I thought port %q belonged to service %q, but it seems to belong to %q", port, svc, curSvc))
}
delete(a.portsInUse[al.ip.String()], port)
}
delete(a.servicesOnIP[al.ip.String()], svc)
if len(a.portsInUse[al.ip.String()]) == 0 {
delete(a.portsInUse, al.ip.String())
delete(a.sharingKeyForIP, al.ip.String())
}
a.poolIPsInUse[al.pool][al.ip.String()]--
if a.poolIPsInUse[al.pool][al.ip.String()] == 0 {
// Explicitly delete unused IPs from the pool, so that len()
// is an accurate count of IPs in use.
delete(a.poolIPsInUse[al.pool], al.ip.String())
}
a.poolServices[al.pool]--
return true
}
// AllocateFromPool assigns an available IP from pool to service.
func (a *Allocator) AllocateFromPool(svc, poolName string, ports []Port, sharingKey, backendKey string) (net.IP, error) {
if alloc := a.allocated[svc]; alloc != nil {
if err := a.Assign(svc, alloc.ip, ports, sharingKey, backendKey); err != nil {
return nil, err
}
return alloc.ip, nil
}
pool := a.pools[poolName]
if pool == nil {
return nil, fmt.Errorf("unknown pool %q", poolName)
}
for _, cidr := range pool.CIDR {
c := ipaddr.NewCursor([]ipaddr.Prefix{*ipaddr.NewPrefix(cidr)})
for pos := c.First(); pos != nil; pos = c.Next() {
ip := pos.IP
if pool.AvoidBuggyIPs && ipConfusesBuggyFirmwares(ip) {
continue
}
// Somewhat inefficiently brute-force by invoking the
// IP-specific allocator.
if err := a.Assign(svc, ip, ports, sharingKey, backendKey); err == nil {
return ip, nil
}
}
}
// Woops, run out of IPs :( Fail.
return nil, fmt.Errorf("no available IPs in pool %q", poolName)
}
// Allocate assigns any available and assignable IP to service.
func (a *Allocator) Allocate(svc string, ports []Port, sharingKey, backendKey string) (net.IP, error) {
if alloc := a.allocated[svc]; alloc != nil {
if err := a.Assign(svc, alloc.ip, ports, sharingKey, backendKey); err != nil {
return nil, err
}
return alloc.ip, nil
}
for poolName := range a.pools {
if !a.pools[poolName].AutoAssign {
continue
}
if ip, err := a.AllocateFromPool(svc, poolName, ports, sharingKey, backendKey); err == nil {
return ip, nil
}
}
return nil, errors.New("no available IPs")
}
// IP returns the IP address allocated to service, or nil if none are allocated.
func (a *Allocator) IP(svc string) net.IP {
if alloc := a.allocated[svc]; alloc != nil {
return alloc.ip
}
return nil
}
// Pool returns the pool from which service's IP was allocated. If
// service has no IP allocated, "" is returned.
func (a *Allocator) Pool(svc string) string {
ip := a.IP(svc)
if ip == nil {
return ""
}
return poolFor(a.pools, ip)
}
func sharingOK(existing, new *key) error {
if existing.sharing == "" {
return errors.New("existing service does not allow sharing")
}
if new.sharing == "" {
return errors.New("new service does not allow sharing")
}
if existing.sharing != new.sharing {
return fmt.Errorf("sharing key %q does not match existing sharing key %q", new.sharing, existing.sharing)
}
if existing.backend != new.backend {
return fmt.Errorf("backend key %q does not match existing sharing key %q", new.backend, existing.backend)
}
return nil
}
// poolCount returns the number of addresses in the pool.
func poolCount(p *config.Pool) int64 {
var total int64
for _, cidr := range p.CIDR {
o, b := cidr.Mask.Size()
sz := int64(math.Pow(2, float64(b-o)))
cur := ipaddr.NewCursor([]ipaddr.Prefix{*ipaddr.NewPrefix(cidr)})
firstIP := cur.First().IP
lastIP := cur.Last().IP
if p.AvoidBuggyIPs {
if o <= 24 {
// A pair of buggy IPs occur for each /24 present in the range.
buggies := int64(math.Pow(2, float64(24-o))) * 2
sz -= buggies
} else {
// Ranges smaller than /24 contain 1 buggy IP if they
// start/end on a /24 boundary, otherwise they contain
// none.
if ipConfusesBuggyFirmwares(firstIP) {
sz--
}
if ipConfusesBuggyFirmwares(lastIP) {
sz--
}
}
}
total += sz
}
return total
}
// poolFor returns the pool that owns the requested IP, or "" if none.
func poolFor(pools map[string]*config.Pool, ip net.IP) string {
for pname, p := range pools {
if p.AvoidBuggyIPs && ipConfusesBuggyFirmwares(ip) {
continue
}
for _, cidr := range p.CIDR {
if cidr.Contains(ip) {
return pname
}
}
}
return ""
}
func portsEqual(a, b []Port) bool {
if len(a) != len(b) {
return false
}
for i := range a {
if a[i] != b[i] {
return false
}
}
return true
}
// ipConfusesBuggyFirmwares returns true if ip is an IPv4 address ending in 0 or 255.
//
// Such addresses can confuse smurf protection on crappy CPE
// firmwares, leading to packet drops.
func ipConfusesBuggyFirmwares(ip net.IP) bool {
ip = ip.To4()
if ip == nil {
return false
}
return ip[3] == 0 || ip[3] == 255
}