bitmap.go

Documentation: k8s.io/kubernetes/pkg/registry/core/service/ipallocator

     1  /*
     2  Copyright 2015 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package ipallocator
    18  
    19  import (
    20  	"fmt"
    21  	"math/big"
    22  	"net"
    23  
    24  	api "k8s.io/kubernetes/pkg/apis/core"
    25  	"k8s.io/kubernetes/pkg/registry/core/service/allocator"
    26  	netutils "k8s.io/utils/net"
    27  )
    28  
    29  // Range is a contiguous block of IPs that can be allocated atomically.
    30  //
    31  // The internal structure of the range is:
    32  //
    33  //	For CIDR 10.0.0.0/24
    34  //	254 addresses usable out of 256 total (minus base and broadcast IPs)
    35  //	  The number of usable addresses is r.max
    36  //
    37  //	CIDR base IP          CIDR broadcast IP
    38  //	10.0.0.0                     10.0.0.255
    39  //	|                                     |
    40  //	0 1 2 3 4 5 ...         ... 253 254 255
    41  //	  |                              |
    42  //	r.base                     r.base + r.max
    43  //	  |                              |
    44  //	offset #0 of r.allocated   last offset of r.allocated
    45  type Range struct {
    46  	net *net.IPNet
    47  	// base is a cached version of the start IP in the CIDR range as a *big.Int
    48  	base *big.Int
    49  	// max is the maximum size of the usable addresses in the range
    50  	max int
    51  	// family is the IP family of this range
    52  	family api.IPFamily
    53  
    54  	alloc allocator.Interface
    55  	// metrics is a metrics recorder that can be disabled
    56  	metrics metricsRecorderInterface
    57  }
    58  
    59  var _ Interface = (*Range)(nil)
    60  
    61  // New creates a Range over a net.IPNet, calling allocatorFactory to construct the backing store.
    62  func New(cidr *net.IPNet, allocatorFactory allocator.AllocatorWithOffsetFactory) (*Range, error) {
    63  	max := netutils.RangeSize(cidr)
    64  	base := netutils.BigForIP(cidr.IP)
    65  	rangeSpec := cidr.String()
    66  	var family api.IPFamily
    67  
    68  	if netutils.IsIPv6CIDR(cidr) {
    69  		family = api.IPv6Protocol
    70  		// Limit the max size, since the allocator keeps a bitmap of that size.
    71  		if max > 65536 {
    72  			max = 65536
    73  		}
    74  	} else {
    75  		family = api.IPv4Protocol
    76  		// Don't use the IPv4 network's broadcast address, but don't just
    77  		// Allocate() it - we don't ever want to be able to release it.
    78  		max--
    79  	}
    80  
    81  	// Don't use the network's ".0" address, but don't just Allocate() it - we
    82  	// don't ever want to be able to release it.
    83  	base.Add(base, big.NewInt(1))
    84  	max--
    85  
    86  	// cidr with whole mask can be negative
    87  	if max < 0 {
    88  		max = 0
    89  	}
    90  
    91  	r := Range{
    92  		net:     cidr,
    93  		base:    base,
    94  		max:     maximum(0, int(max)),
    95  		family:  family,
    96  		metrics: &emptyMetricsRecorder{}, // disabled by default
    97  	}
    98  
    99  	offset := calculateRangeOffset(cidr)
   100  
   101  	var err error
   102  	r.alloc, err = allocatorFactory(r.max, rangeSpec, offset)
   103  	if err != nil {
   104  		return nil, err
   105  	}
   106  	return &r, nil
   107  }
   108  
   109  // NewInMemory creates an in-memory allocator.
   110  func NewInMemory(cidr *net.IPNet) (*Range, error) {
   111  	return New(cidr, func(max int, rangeSpec string, offset int) (allocator.Interface, error) {
   112  		return allocator.NewAllocationMapWithOffset(max, rangeSpec, offset), nil
   113  	})
   114  }
   115  
   116  // NewFromSnapshot allocates a Range and initializes it from a snapshot.
   117  func NewFromSnapshot(snap *api.RangeAllocation) (*Range, error) {
   118  	_, ipnet, err := netutils.ParseCIDRSloppy(snap.Range)
   119  	if err != nil {
   120  		return nil, err
   121  	}
   122  	r, err := NewInMemory(ipnet)
   123  	if err != nil {
   124  		return nil, err
   125  	}
   126  	if err := r.Restore(ipnet, snap.Data); err != nil {
   127  		return nil, err
   128  	}
   129  	return r, nil
   130  }
   131  
   132  func maximum(a, b int) int {
   133  	if a > b {
   134  		return a
   135  	}
   136  	return b
   137  }
   138  
   139  // Free returns the count of IP addresses left in the range.
   140  func (r *Range) Free() int {
   141  	return r.alloc.Free()
   142  }
   143  
   144  // Used returns the count of IP addresses used in the range.
   145  func (r *Range) Used() int {
   146  	return r.max - r.alloc.Free()
   147  }
   148  
   149  // CIDR returns the CIDR covered by the range.
   150  func (r *Range) CIDR() net.IPNet {
   151  	return *r.net
   152  }
   153  
   154  // DryRun returns a non-persisting form of this Range.
   155  func (r *Range) DryRun() Interface {
   156  	return dryRunRange{r}
   157  }
   158  
   159  // For clearer code.
   160  const dryRunTrue = true
   161  const dryRunFalse = false
   162  
   163  // Allocate attempts to reserve the provided IP. ErrNotInRange or
   164  // ErrAllocated will be returned if the IP is not valid for this range
   165  // or has already been reserved.  ErrFull will be returned if there
   166  // are no addresses left.
   167  func (r *Range) Allocate(ip net.IP) error {
   168  	return r.allocate(ip, dryRunFalse)
   169  }
   170  
   171  func (r *Range) allocate(ip net.IP, dryRun bool) error {
   172  	label := r.CIDR()
   173  	ok, offset := r.contains(ip)
   174  	if !ok {
   175  		if !dryRun {
   176  			// update metrics
   177  			r.metrics.incrementAllocationErrors(label.String(), "static")
   178  		}
   179  		return &ErrNotInRange{ip, r.net.String()}
   180  	}
   181  	if dryRun {
   182  		// Don't bother to check whether the IP is actually free. It's racy and
   183  		// not worth the effort to plumb any further.
   184  		return nil
   185  	}
   186  
   187  	allocated, err := r.alloc.Allocate(offset)
   188  	if err != nil {
   189  		// update metrics
   190  		r.metrics.incrementAllocationErrors(label.String(), "static")
   191  
   192  		return err
   193  	}
   194  	if !allocated {
   195  		// update metrics
   196  		r.metrics.incrementAllocationErrors(label.String(), "static")
   197  
   198  		return ErrAllocated
   199  	}
   200  	// update metrics
   201  	r.metrics.incrementAllocations(label.String(), "static")
   202  	r.metrics.setAllocated(label.String(), r.Used())
   203  	r.metrics.setAvailable(label.String(), r.Free())
   204  
   205  	return nil
   206  }
   207  
   208  // AllocateNext reserves one of the IPs from the pool. ErrFull may
   209  // be returned if there are no addresses left.
   210  func (r *Range) AllocateNext() (net.IP, error) {
   211  	return r.allocateNext(dryRunFalse)
   212  }
   213  
   214  func (r *Range) allocateNext(dryRun bool) (net.IP, error) {
   215  	label := r.CIDR()
   216  	if dryRun {
   217  		// Don't bother finding a free value. It's racy and not worth the
   218  		// effort to plumb any further.
   219  		return r.CIDR().IP, nil
   220  	}
   221  
   222  	offset, ok, err := r.alloc.AllocateNext()
   223  	if err != nil {
   224  		// update metrics
   225  		r.metrics.incrementAllocationErrors(label.String(), "dynamic")
   226  
   227  		return nil, err
   228  	}
   229  	if !ok {
   230  		// update metrics
   231  		r.metrics.incrementAllocationErrors(label.String(), "dynamic")
   232  
   233  		return nil, ErrFull
   234  	}
   235  	// update metrics
   236  	r.metrics.incrementAllocations(label.String(), "dynamic")
   237  	r.metrics.setAllocated(label.String(), r.Used())
   238  	r.metrics.setAvailable(label.String(), r.Free())
   239  
   240  	return netutils.AddIPOffset(r.base, offset), nil
   241  }
   242  
   243  // Release releases the IP back to the pool. Releasing an
   244  // unallocated IP or an IP out of the range is a no-op and
   245  // returns no error.
   246  func (r *Range) Release(ip net.IP) error {
   247  	return r.release(ip, dryRunFalse)
   248  }
   249  
   250  func (r *Range) release(ip net.IP, dryRun bool) error {
   251  	ok, offset := r.contains(ip)
   252  	if !ok {
   253  		return nil
   254  	}
   255  	if dryRun {
   256  		return nil
   257  	}
   258  
   259  	err := r.alloc.Release(offset)
   260  	if err == nil {
   261  		// update metrics
   262  		label := r.CIDR()
   263  		r.metrics.setAllocated(label.String(), r.Used())
   264  		r.metrics.setAvailable(label.String(), r.Free())
   265  	}
   266  	return err
   267  }
   268  
   269  // ForEach calls the provided function for each allocated IP.
   270  func (r *Range) ForEach(fn func(net.IP)) {
   271  	r.alloc.ForEach(func(offset int) {
   272  		ip, _ := netutils.GetIndexedIP(r.net, offset+1) // +1 because Range doesn't store IP 0
   273  		fn(ip)
   274  	})
   275  }
   276  
   277  // Has returns true if the provided IP is already allocated and a call
   278  // to Allocate(ip) would fail with ErrAllocated.
   279  func (r *Range) Has(ip net.IP) bool {
   280  	ok, offset := r.contains(ip)
   281  	if !ok {
   282  		return false
   283  	}
   284  
   285  	return r.alloc.Has(offset)
   286  }
   287  
   288  // IPFamily returns the IP family of this range.
   289  func (r *Range) IPFamily() api.IPFamily {
   290  	return r.family
   291  }
   292  
   293  // Snapshot saves the current state of the pool.
   294  func (r *Range) Snapshot(dst *api.RangeAllocation) error {
   295  	snapshottable, ok := r.alloc.(allocator.Snapshottable)
   296  	if !ok {
   297  		return fmt.Errorf("not a snapshottable allocator")
   298  	}
   299  	rangeString, data := snapshottable.Snapshot()
   300  	dst.Range = rangeString
   301  	dst.Data = data
   302  	return nil
   303  }
   304  
   305  // Restore restores the pool to the previously captured state. ErrMismatchedNetwork
   306  // is returned if the provided IPNet range doesn't exactly match the previous range.
   307  func (r *Range) Restore(net *net.IPNet, data []byte) error {
   308  	if !net.IP.Equal(r.net.IP) || net.Mask.String() != r.net.Mask.String() {
   309  		return ErrMismatchedNetwork
   310  	}
   311  	snapshottable, ok := r.alloc.(allocator.Snapshottable)
   312  	if !ok {
   313  		return fmt.Errorf("not a snapshottable allocator")
   314  	}
   315  	if err := snapshottable.Restore(net.String(), data); err != nil {
   316  		return fmt.Errorf("restoring snapshot encountered %v", err)
   317  	}
   318  	return nil
   319  }
   320  
   321  // contains returns true and the offset if the ip is in the range, and false
   322  // and nil otherwise. The first and last addresses of the CIDR are omitted.
   323  func (r *Range) contains(ip net.IP) (bool, int) {
   324  	if !r.net.Contains(ip) {
   325  		return false, 0
   326  	}
   327  
   328  	offset := calculateIPOffset(r.base, ip)
   329  	if offset < 0 || offset >= r.max {
   330  		return false, 0
   331  	}
   332  	return true, offset
   333  }
   334  
   335  // Destroy shuts down internal allocator.
   336  func (r *Range) Destroy() {
   337  	r.alloc.Destroy()
   338  }
   339  
   340  // EnableMetrics enables metrics recording.
   341  func (r *Range) EnableMetrics() {
   342  	registerMetrics()
   343  	r.metrics = &metricsRecorder{}
   344  }
   345  
   346  // calculateIPOffset calculates the integer offset of ip from base such that
   347  // base + offset = ip. It requires ip >= base.
   348  func calculateIPOffset(base *big.Int, ip net.IP) int {
   349  	return int(big.NewInt(0).Sub(netutils.BigForIP(ip), base).Int64())
   350  }
   351  
   352  // calculateRangeOffset estimates the offset used on the range for statically allocation based on
   353  // the following formula `min(max($min, cidrSize/$step), $max)`, described as ~never less than
   354  // $min or more than $max, with a graduated step function between them~. The function returns 0
   355  // if any of the parameters is invalid.
   356  func calculateRangeOffset(cidr *net.IPNet) int {
   357  	// default values for min(max($min, cidrSize/$step), $max)
   358  	const (
   359  		min  = 16
   360  		max  = 256
   361  		step = 16
   362  	)
   363  
   364  	cidrSize := netutils.RangeSize(cidr)
   365  	// available addresses are always less than the cidr size
   366  	// A /28 CIDR returns 16 addresses, but 2 of them, the network
   367  	// and broadcast addresses are not available.
   368  	if cidrSize <= min {
   369  		return 0
   370  	}
   371  
   372  	offset := cidrSize / step
   373  	if offset < min {
   374  		return min
   375  	}
   376  	if offset > max {
   377  		return max
   378  	}
   379  	return int(offset)
   380  }
   381  
   382  // dryRunRange is a shim to satisfy Interface without persisting state.
   383  type dryRunRange struct {
   384  	real *Range
   385  }
   386  
   387  func (dry dryRunRange) Allocate(ip net.IP) error {
   388  	return dry.real.allocate(ip, dryRunTrue)
   389  }
   390  
   391  func (dry dryRunRange) AllocateNext() (net.IP, error) {
   392  	return dry.real.allocateNext(dryRunTrue)
   393  }
   394  
   395  func (dry dryRunRange) Release(ip net.IP) error {
   396  	return dry.real.release(ip, dryRunTrue)
   397  }
   398  
   399  func (dry dryRunRange) ForEach(cb func(net.IP)) {
   400  	dry.real.ForEach(cb)
   401  }
   402  
   403  func (dry dryRunRange) CIDR() net.IPNet {
   404  	return dry.real.CIDR()
   405  }
   406  
   407  func (dry dryRunRange) IPFamily() api.IPFamily {
   408  	return dry.real.IPFamily()
   409  }
   410  
   411  func (dry dryRunRange) DryRun() Interface {
   412  	return dry
   413  }
   414  
   415  func (dry dryRunRange) Has(ip net.IP) bool {
   416  	return dry.real.Has(ip)
   417  }
   418  
   419  func (dry dryRunRange) Destroy() {
   420  }
   421  
   422  func (dry dryRunRange) EnableMetrics() {
   423  }
   424
View as plain text