...

Source file src/k8s.io/kubernetes/pkg/controller/nodeipam/ipam/cidrset/cidr_set_test.go

Documentation: k8s.io/kubernetes/pkg/controller/nodeipam/ipam/cidrset

     1  /*
     2  Copyright 2016 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 cidrset
    18  
    19  import (
    20  	"math/big"
    21  	"net"
    22  	"reflect"
    23  	"testing"
    24  
    25  	"k8s.io/component-base/metrics/testutil"
    26  	netutils "k8s.io/utils/net"
    27  )
    28  
    29  func TestCIDRSetFullyAllocated(t *testing.T) {
    30  	cases := []struct {
    31  		clusterCIDRStr string
    32  		subNetMaskSize int
    33  		expectedCIDR   string
    34  		description    string
    35  	}{
    36  		{
    37  			clusterCIDRStr: "127.123.234.0/30",
    38  			subNetMaskSize: 30,
    39  			expectedCIDR:   "127.123.234.0/30",
    40  			description:    "Fully allocated CIDR with IPv4",
    41  		},
    42  		{
    43  			clusterCIDRStr: "beef:1234::/30",
    44  			subNetMaskSize: 30,
    45  			expectedCIDR:   "beef:1234::/30",
    46  			description:    "Fully allocated CIDR with IPv6",
    47  		},
    48  	}
    49  	for _, tc := range cases {
    50  		_, clusterCIDR, _ := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
    51  		a, err := NewCIDRSet(clusterCIDR, tc.subNetMaskSize)
    52  		if err != nil {
    53  			t.Fatalf("unexpected error: %v for %v", err, tc.description)
    54  		}
    55  		p, err := a.AllocateNext()
    56  		if err != nil {
    57  			t.Fatalf("unexpected error: %v for %v", err, tc.description)
    58  		}
    59  		if p.String() != tc.expectedCIDR {
    60  			t.Fatalf("unexpected allocated cidr: %v, expecting %v for %v",
    61  				p.String(), tc.expectedCIDR, tc.description)
    62  		}
    63  
    64  		_, err = a.AllocateNext()
    65  		if err == nil {
    66  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
    67  		}
    68  
    69  		a.Release(p)
    70  
    71  		p, err = a.AllocateNext()
    72  		if err != nil {
    73  			t.Fatalf("unexpected error: %v for %v", err, tc.description)
    74  		}
    75  		if p.String() != tc.expectedCIDR {
    76  			t.Fatalf("unexpected allocated cidr: %v, expecting %v for %v",
    77  				p.String(), tc.expectedCIDR, tc.description)
    78  		}
    79  		_, err = a.AllocateNext()
    80  		if err == nil {
    81  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
    82  		}
    83  	}
    84  }
    85  
    86  func TestIndexToCIDRBlock(t *testing.T) {
    87  	cases := []struct {
    88  		clusterCIDRStr string
    89  		subnetMaskSize int
    90  		index          int
    91  		CIDRBlock      string
    92  		description    string
    93  	}{
    94  		{
    95  			clusterCIDRStr: "127.123.3.0/16",
    96  			subnetMaskSize: 24,
    97  			index:          0,
    98  			CIDRBlock:      "127.123.0.0/24",
    99  			description:    "1st IP address indexed with IPv4",
   100  		},
   101  		{
   102  			clusterCIDRStr: "127.123.0.0/16",
   103  			subnetMaskSize: 24,
   104  			index:          15,
   105  			CIDRBlock:      "127.123.15.0/24",
   106  			description:    "16th IP address indexed with IPv4",
   107  		},
   108  		{
   109  			clusterCIDRStr: "192.168.5.219/28",
   110  			subnetMaskSize: 32,
   111  			index:          5,
   112  			CIDRBlock:      "192.168.5.213/32",
   113  			description:    "5th IP address indexed with IPv4",
   114  		},
   115  		{
   116  			clusterCIDRStr: "2001:0db8:1234:3::/48",
   117  			subnetMaskSize: 64,
   118  			index:          0,
   119  			CIDRBlock:      "2001:db8:1234::/64",
   120  			description:    "1st IP address indexed with IPv6 /64",
   121  		},
   122  		{
   123  			clusterCIDRStr: "2001:0db8:1234::/48",
   124  			subnetMaskSize: 64,
   125  			index:          15,
   126  			CIDRBlock:      "2001:db8:1234:f::/64",
   127  			description:    "16th IP address indexed with IPv6 /64",
   128  		},
   129  		{
   130  			clusterCIDRStr: "2001:0db8:85a3::8a2e:0370:7334/50",
   131  			subnetMaskSize: 63,
   132  			index:          6425,
   133  			CIDRBlock:      "2001:db8:85a3:3232::/63",
   134  			description:    "6426th IP address indexed with IPv6 /63",
   135  		},
   136  		{
   137  			clusterCIDRStr: "2001:0db8::/32",
   138  			subnetMaskSize: 48,
   139  			index:          0,
   140  			CIDRBlock:      "2001:db8::/48",
   141  			description:    "1st IP address indexed with IPv6 /48",
   142  		},
   143  		{
   144  			clusterCIDRStr: "2001:0db8::/32",
   145  			subnetMaskSize: 48,
   146  			index:          15,
   147  			CIDRBlock:      "2001:db8:f::/48",
   148  			description:    "16th IP address indexed with IPv6 /48",
   149  		},
   150  		{
   151  			clusterCIDRStr: "2001:0db8:85a3::8a2e:0370:7334/32",
   152  			subnetMaskSize: 48,
   153  			index:          6425,
   154  			CIDRBlock:      "2001:db8:1919::/48",
   155  			description:    "6426th IP address indexed with IPv6 /48",
   156  		},
   157  		{
   158  			clusterCIDRStr: "2001:0db8:1234:ff00::/56",
   159  			subnetMaskSize: 72,
   160  			index:          0,
   161  			CIDRBlock:      "2001:db8:1234:ff00::/72",
   162  			description:    "1st IP address indexed with IPv6 /72",
   163  		},
   164  		{
   165  			clusterCIDRStr: "2001:0db8:1234:ff00::/56",
   166  			subnetMaskSize: 72,
   167  			index:          15,
   168  			CIDRBlock:      "2001:db8:1234:ff00:f00::/72",
   169  			description:    "16th IP address indexed with IPv6 /72",
   170  		},
   171  		{
   172  			clusterCIDRStr: "2001:0db8:1234:ff00::0370:7334/56",
   173  			subnetMaskSize: 72,
   174  			index:          6425,
   175  			CIDRBlock:      "2001:db8:1234:ff19:1900::/72",
   176  			description:    "6426th IP address indexed with IPv6 /72",
   177  		},
   178  		{
   179  			clusterCIDRStr: "2001:0db8:1234:0:1234::/80",
   180  			subnetMaskSize: 96,
   181  			index:          0,
   182  			CIDRBlock:      "2001:db8:1234:0:1234::/96",
   183  			description:    "1st IP address indexed with IPv6 /96",
   184  		},
   185  		{
   186  			clusterCIDRStr: "2001:0db8:1234:0:1234::/80",
   187  			subnetMaskSize: 96,
   188  			index:          15,
   189  			CIDRBlock:      "2001:db8:1234:0:1234:f::/96",
   190  			description:    "16th IP address indexed with IPv6 /96",
   191  		},
   192  		{
   193  			clusterCIDRStr: "2001:0db8:1234:ff00::0370:7334/80",
   194  			subnetMaskSize: 96,
   195  			index:          6425,
   196  			CIDRBlock:      "2001:db8:1234:ff00:0:1919::/96",
   197  			description:    "6426th IP address indexed with IPv6 /96",
   198  		},
   199  	}
   200  	for _, tc := range cases {
   201  		_, clusterCIDR, _ := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   202  		a, err := NewCIDRSet(clusterCIDR, tc.subnetMaskSize)
   203  		if err != nil {
   204  			t.Fatalf("error for %v ", tc.description)
   205  		}
   206  		cidr := a.indexToCIDRBlock(tc.index)
   207  		if cidr.String() != tc.CIDRBlock {
   208  			t.Fatalf("error for %v index %d %s", tc.description, tc.index, cidr.String())
   209  		}
   210  	}
   211  }
   212  
   213  func TestCIDRSet_RandomishAllocation(t *testing.T) {
   214  	cases := []struct {
   215  		clusterCIDRStr string
   216  		description    string
   217  	}{
   218  		{
   219  			clusterCIDRStr: "127.123.234.0/16",
   220  			description:    "RandomishAllocation with IPv4",
   221  		},
   222  		{
   223  			clusterCIDRStr: "beef:1234::/16",
   224  			description:    "RandomishAllocation with IPv6",
   225  		},
   226  	}
   227  	for _, tc := range cases {
   228  		_, clusterCIDR, _ := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   229  		a, err := NewCIDRSet(clusterCIDR, 24)
   230  		if err != nil {
   231  			t.Fatalf("Error allocating CIDRSet for %v", tc.description)
   232  		}
   233  		// allocate all the CIDRs
   234  		var cidrs []*net.IPNet
   235  
   236  		for i := 0; i < 256; i++ {
   237  			if c, err := a.AllocateNext(); err == nil {
   238  				cidrs = append(cidrs, c)
   239  			} else {
   240  				t.Fatalf("unexpected error: %v for %v", err, tc.description)
   241  			}
   242  		}
   243  
   244  		//var err error
   245  		_, err = a.AllocateNext()
   246  		if err == nil {
   247  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
   248  		}
   249  		// release them all
   250  		for i := 0; i < len(cidrs); i++ {
   251  			a.Release(cidrs[i])
   252  		}
   253  
   254  		// allocate the CIDRs again
   255  		var rcidrs []*net.IPNet
   256  		for i := 0; i < 256; i++ {
   257  			if c, err := a.AllocateNext(); err == nil {
   258  				rcidrs = append(rcidrs, c)
   259  			} else {
   260  				t.Fatalf("unexpected error: %d, %v for %v", i, err, tc.description)
   261  			}
   262  		}
   263  		_, err = a.AllocateNext()
   264  		if err == nil {
   265  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
   266  		}
   267  
   268  		if !reflect.DeepEqual(cidrs, rcidrs) {
   269  			t.Fatalf("expected re-allocated cidrs are the same collection for %v", tc.description)
   270  		}
   271  	}
   272  }
   273  
   274  func TestCIDRSet_AllocationOccupied(t *testing.T) {
   275  	cases := []struct {
   276  		clusterCIDRStr string
   277  		description    string
   278  	}{
   279  		{
   280  			clusterCIDRStr: "127.123.234.0/16",
   281  			description:    "AllocationOccupied with IPv4",
   282  		},
   283  		{
   284  			clusterCIDRStr: "beef:1234::/16",
   285  			description:    "AllocationOccupied with IPv6",
   286  		},
   287  	}
   288  	for _, tc := range cases {
   289  		_, clusterCIDR, _ := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   290  		a, err := NewCIDRSet(clusterCIDR, 24)
   291  		if err != nil {
   292  			t.Fatalf("Error allocating CIDRSet for %v", tc.description)
   293  		}
   294  		// allocate all the CIDRs
   295  		var cidrs []*net.IPNet
   296  		var numCIDRs = 256
   297  
   298  		for i := 0; i < numCIDRs; i++ {
   299  			if c, err := a.AllocateNext(); err == nil {
   300  				cidrs = append(cidrs, c)
   301  			} else {
   302  				t.Fatalf("unexpected error: %v for %v", err, tc.description)
   303  			}
   304  		}
   305  
   306  		//var err error
   307  		_, err = a.AllocateNext()
   308  		if err == nil {
   309  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
   310  		}
   311  		// release them all
   312  		for i := 0; i < len(cidrs); i++ {
   313  			a.Release(cidrs[i])
   314  		}
   315  		// occupy the last 128 CIDRs
   316  		for i := numCIDRs / 2; i < numCIDRs; i++ {
   317  			a.Occupy(cidrs[i])
   318  		}
   319  		// occupy the first of the last 128 again
   320  		a.Occupy(cidrs[numCIDRs/2])
   321  
   322  		// allocate the first 128 CIDRs again
   323  		var rcidrs []*net.IPNet
   324  		for i := 0; i < numCIDRs/2; i++ {
   325  			if c, err := a.AllocateNext(); err == nil {
   326  				rcidrs = append(rcidrs, c)
   327  			} else {
   328  				t.Fatalf("unexpected error: %d, %v for %v", i, err, tc.description)
   329  			}
   330  		}
   331  		_, err = a.AllocateNext()
   332  		if err == nil {
   333  			t.Fatalf("expected error because of fully-allocated range for %v", tc.description)
   334  		}
   335  
   336  		// check Occupy() work properly
   337  		for i := numCIDRs / 2; i < numCIDRs; i++ {
   338  			rcidrs = append(rcidrs, cidrs[i])
   339  		}
   340  		if !reflect.DeepEqual(cidrs, rcidrs) {
   341  			t.Fatalf("expected re-allocated cidrs are the same collection for %v", tc.description)
   342  		}
   343  	}
   344  }
   345  
   346  func TestDoubleOccupyRelease(t *testing.T) {
   347  	// Run a sequence of operations and check the number of occupied CIDRs
   348  	// after each one.
   349  	clusterCIDRStr := "10.42.0.0/16"
   350  	operations := []struct {
   351  		cidrStr     string
   352  		operation   string
   353  		numOccupied int
   354  	}{
   355  		// Occupy 1 element: +1
   356  		{
   357  			cidrStr:     "10.42.5.0/24",
   358  			operation:   "occupy",
   359  			numOccupied: 1,
   360  		},
   361  		// Occupy 1 more element: +1
   362  		{
   363  			cidrStr:     "10.42.9.0/24",
   364  			operation:   "occupy",
   365  			numOccupied: 2,
   366  		},
   367  		// Occupy 4 elements overlapping with one from the above: +3
   368  		{
   369  			cidrStr:     "10.42.8.0/22",
   370  			operation:   "occupy",
   371  			numOccupied: 5,
   372  		},
   373  		// Occupy an already-coccupied element: no change
   374  		{
   375  			cidrStr:     "10.42.9.0/24",
   376  			operation:   "occupy",
   377  			numOccupied: 5,
   378  		},
   379  		// Release an coccupied element: -1
   380  		{
   381  			cidrStr:     "10.42.9.0/24",
   382  			operation:   "release",
   383  			numOccupied: 4,
   384  		},
   385  		// Release an unoccupied element: no change
   386  		{
   387  			cidrStr:     "10.42.9.0/24",
   388  			operation:   "release",
   389  			numOccupied: 4,
   390  		},
   391  		// Release 4 elements, only one of which is occupied: -1
   392  		{
   393  			cidrStr:     "10.42.4.0/22",
   394  			operation:   "release",
   395  			numOccupied: 3,
   396  		},
   397  	}
   398  	// Check that there are exactly that many allocatable CIDRs after all
   399  	// operations have been executed.
   400  	numAllocatable24s := (1 << 8) - 3
   401  
   402  	_, clusterCIDR, _ := netutils.ParseCIDRSloppy(clusterCIDRStr)
   403  	a, err := NewCIDRSet(clusterCIDR, 24)
   404  	if err != nil {
   405  		t.Fatalf("Error allocating CIDRSet")
   406  	}
   407  
   408  	// Execute the operations
   409  	for _, op := range operations {
   410  		_, cidr, _ := netutils.ParseCIDRSloppy(op.cidrStr)
   411  		switch op.operation {
   412  		case "occupy":
   413  			a.Occupy(cidr)
   414  		case "release":
   415  			a.Release(cidr)
   416  		default:
   417  			t.Fatalf("test error: unknown operation %v", op.operation)
   418  		}
   419  		if a.allocatedCIDRs != op.numOccupied {
   420  			t.Fatalf("Expected %d occupied CIDRS, got %d", op.numOccupied, a.allocatedCIDRs)
   421  		}
   422  	}
   423  
   424  	// Make sure that we can allocate exactly `numAllocatable24s` elements.
   425  	for i := 0; i < numAllocatable24s; i++ {
   426  		_, err := a.AllocateNext()
   427  		if err != nil {
   428  			t.Fatalf("Expected to be able to allocate %d CIDRS, failed after %d", numAllocatable24s, i)
   429  		}
   430  	}
   431  
   432  	_, err = a.AllocateNext()
   433  	if err == nil {
   434  		t.Fatalf("Expected to be able to allocate exactly %d CIDRS, got one more", numAllocatable24s)
   435  	}
   436  }
   437  
   438  func TestGetBitforCIDR(t *testing.T) {
   439  	cases := []struct {
   440  		clusterCIDRStr string
   441  		subNetMaskSize int
   442  		subNetCIDRStr  string
   443  		expectedBit    int
   444  		expectErr      bool
   445  		description    string
   446  	}{
   447  		{
   448  			clusterCIDRStr: "127.0.0.0/8",
   449  			subNetMaskSize: 16,
   450  			subNetCIDRStr:  "127.0.0.0/16",
   451  			expectedBit:    0,
   452  			expectErr:      false,
   453  			description:    "Get 0 Bit with IPv4",
   454  		},
   455  		{
   456  			clusterCIDRStr: "be00::/8",
   457  			subNetMaskSize: 16,
   458  			subNetCIDRStr:  "be00::/16",
   459  			expectedBit:    0,
   460  			expectErr:      false,
   461  			description:    "Get 0 Bit with IPv6",
   462  		},
   463  		{
   464  			clusterCIDRStr: "127.0.0.0/8",
   465  			subNetMaskSize: 16,
   466  			subNetCIDRStr:  "127.123.0.0/16",
   467  			expectedBit:    123,
   468  			expectErr:      false,
   469  			description:    "Get 123rd Bit with IPv4",
   470  		},
   471  		{
   472  			clusterCIDRStr: "be00::/8",
   473  			subNetMaskSize: 16,
   474  			subNetCIDRStr:  "beef::/16",
   475  			expectedBit:    0xef,
   476  			expectErr:      false,
   477  			description:    "Get xef Bit with IPv6",
   478  		},
   479  		{
   480  			clusterCIDRStr: "127.0.0.0/8",
   481  			subNetMaskSize: 16,
   482  			subNetCIDRStr:  "127.168.0.0/16",
   483  			expectedBit:    168,
   484  			expectErr:      false,
   485  			description:    "Get 168th Bit with IPv4",
   486  		},
   487  		{
   488  			clusterCIDRStr: "be00::/8",
   489  			subNetMaskSize: 16,
   490  			subNetCIDRStr:  "be68::/16",
   491  			expectedBit:    0x68,
   492  			expectErr:      false,
   493  			description:    "Get x68th Bit with IPv6",
   494  		},
   495  		{
   496  			clusterCIDRStr: "127.0.0.0/8",
   497  			subNetMaskSize: 16,
   498  			subNetCIDRStr:  "127.224.0.0/16",
   499  			expectedBit:    224,
   500  			expectErr:      false,
   501  			description:    "Get 224th Bit with IPv4",
   502  		},
   503  		{
   504  			clusterCIDRStr: "be00::/8",
   505  			subNetMaskSize: 16,
   506  			subNetCIDRStr:  "be24::/16",
   507  			expectedBit:    0x24,
   508  			expectErr:      false,
   509  			description:    "Get x24th Bit with IPv6",
   510  		},
   511  		{
   512  			clusterCIDRStr: "192.168.0.0/16",
   513  			subNetMaskSize: 24,
   514  			subNetCIDRStr:  "192.168.12.0/24",
   515  			expectedBit:    12,
   516  			expectErr:      false,
   517  			description:    "Get 12th Bit with IPv4",
   518  		},
   519  		{
   520  			clusterCIDRStr: "beef::/16",
   521  			subNetMaskSize: 24,
   522  			subNetCIDRStr:  "beef:1200::/24",
   523  			expectedBit:    0x12,
   524  			expectErr:      false,
   525  			description:    "Get x12th Bit with IPv6",
   526  		},
   527  		{
   528  			clusterCIDRStr: "192.168.0.0/16",
   529  			subNetMaskSize: 24,
   530  			subNetCIDRStr:  "192.168.151.0/24",
   531  			expectedBit:    151,
   532  			expectErr:      false,
   533  			description:    "Get 151st Bit with IPv4",
   534  		},
   535  		{
   536  			clusterCIDRStr: "beef::/16",
   537  			subNetMaskSize: 24,
   538  			subNetCIDRStr:  "beef:9700::/24",
   539  			expectedBit:    0x97,
   540  			expectErr:      false,
   541  			description:    "Get x97st Bit with IPv6",
   542  		},
   543  		{
   544  			clusterCIDRStr: "192.168.0.0/16",
   545  			subNetMaskSize: 24,
   546  			subNetCIDRStr:  "127.168.224.0/24",
   547  			expectErr:      true,
   548  			description:    "Get error with IPv4",
   549  		},
   550  		{
   551  			clusterCIDRStr: "beef::/16",
   552  			subNetMaskSize: 24,
   553  			subNetCIDRStr:  "2001:db00::/24",
   554  			expectErr:      true,
   555  			description:    "Get error with IPv6",
   556  		},
   557  	}
   558  
   559  	for _, tc := range cases {
   560  		t.Run(tc.description, func(t *testing.T) {
   561  			_, clusterCIDR, err := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   562  			if err != nil {
   563  				t.Fatalf("unexpected error: %v", err)
   564  			}
   565  
   566  			cs, err := NewCIDRSet(clusterCIDR, tc.subNetMaskSize)
   567  			if err != nil {
   568  				t.Fatalf("Error allocating CIDRSet")
   569  			}
   570  			_, subnetCIDR, err := netutils.ParseCIDRSloppy(tc.subNetCIDRStr)
   571  			if err != nil {
   572  				t.Fatalf("unexpected error: %v", err)
   573  			}
   574  			got, err := cs.getIndexForIP(subnetCIDR.IP)
   575  			if err == nil && tc.expectErr {
   576  				t.Errorf("expected error but got null")
   577  				return
   578  			}
   579  
   580  			if err != nil && !tc.expectErr {
   581  				t.Errorf("unexpected error: %v", err)
   582  				return
   583  			}
   584  
   585  			if got != tc.expectedBit {
   586  				t.Errorf("expected %v, but got %v", tc.expectedBit, got)
   587  			}
   588  		})
   589  	}
   590  }
   591  
   592  func TestOccupy(t *testing.T) {
   593  	cases := []struct {
   594  		clusterCIDRStr    string
   595  		subNetMaskSize    int
   596  		subNetCIDRStr     string
   597  		expectedUsedBegin int
   598  		expectedUsedEnd   int
   599  		expectErr         bool
   600  		description       string
   601  	}{
   602  		{
   603  			clusterCIDRStr:    "127.0.0.0/8",
   604  			subNetMaskSize:    16,
   605  			subNetCIDRStr:     "127.0.0.0/8",
   606  			expectedUsedBegin: 0,
   607  			expectedUsedEnd:   255,
   608  			expectErr:         false,
   609  			description:       "Occupy all Bits with IPv4",
   610  		},
   611  		{
   612  			clusterCIDRStr:    "2001:beef:1200::/40",
   613  			subNetMaskSize:    48,
   614  			subNetCIDRStr:     "2001:beef:1200::/40",
   615  			expectedUsedBegin: 0,
   616  			expectedUsedEnd:   255,
   617  			expectErr:         false,
   618  			description:       "Occupy all Bits with IPv6",
   619  		},
   620  		{
   621  			clusterCIDRStr:    "127.0.0.0/8",
   622  			subNetMaskSize:    16,
   623  			subNetCIDRStr:     "127.0.0.0/2",
   624  			expectedUsedBegin: 0,
   625  			expectedUsedEnd:   255,
   626  			expectErr:         false,
   627  			description:       "Occupy every Bit with IPv4",
   628  		},
   629  		{
   630  			clusterCIDRStr:    "2001:beef:1200::/40",
   631  			subNetMaskSize:    48,
   632  			subNetCIDRStr:     "2001:beef:1234::/34",
   633  			expectedUsedBegin: 0,
   634  			expectedUsedEnd:   255,
   635  			expectErr:         false,
   636  			description:       "Occupy every Bit with IPv6",
   637  		},
   638  		{
   639  			clusterCIDRStr:    "127.0.0.0/8",
   640  			subNetMaskSize:    16,
   641  			subNetCIDRStr:     "127.0.0.0/16",
   642  			expectedUsedBegin: 0,
   643  			expectedUsedEnd:   0,
   644  			expectErr:         false,
   645  			description:       "Occupy 1st Bit with IPv4",
   646  		},
   647  		{
   648  			clusterCIDRStr:    "2001:beef:1200::/40",
   649  			subNetMaskSize:    48,
   650  			subNetCIDRStr:     "2001:beef:1200::/48",
   651  			expectedUsedBegin: 0,
   652  			expectedUsedEnd:   0,
   653  			expectErr:         false,
   654  			description:       "Occupy 1st Bit with IPv6",
   655  		},
   656  		{
   657  			clusterCIDRStr:    "127.0.0.0/8",
   658  			subNetMaskSize:    32,
   659  			subNetCIDRStr:     "127.0.0.0/16",
   660  			expectedUsedBegin: 0,
   661  			expectedUsedEnd:   65535,
   662  			expectErr:         false,
   663  			description:       "Occupy 65535 Bits with IPv4",
   664  		},
   665  		{
   666  			clusterCIDRStr:    "2001:beef:1200::/48",
   667  			subNetMaskSize:    64,
   668  			subNetCIDRStr:     "2001:beef:1200::/48",
   669  			expectedUsedBegin: 0,
   670  			expectedUsedEnd:   65535,
   671  			expectErr:         false,
   672  			description:       "Occupy 65535 Bits with IPv6",
   673  		},
   674  		{
   675  			clusterCIDRStr:    "127.0.0.0/7",
   676  			subNetMaskSize:    16,
   677  			subNetCIDRStr:     "127.0.0.0/15",
   678  			expectedUsedBegin: 256,
   679  			expectedUsedEnd:   257,
   680  			expectErr:         false,
   681  			description:       "Occupy 257th Bit with IPv4",
   682  		},
   683  		{
   684  			clusterCIDRStr:    "2001:beef:7f00::/39",
   685  			subNetMaskSize:    48,
   686  			subNetCIDRStr:     "2001:beef:7f00::/47",
   687  			expectedUsedBegin: 256,
   688  			expectedUsedEnd:   257,
   689  			expectErr:         false,
   690  			description:       "Occupy 257th Bit with IPv6",
   691  		},
   692  		{
   693  			clusterCIDRStr:    "127.0.0.0/7",
   694  			subNetMaskSize:    15,
   695  			subNetCIDRStr:     "127.0.0.0/15",
   696  			expectedUsedBegin: 128,
   697  			expectedUsedEnd:   128,
   698  			expectErr:         false,
   699  			description:       "Occupy 128th Bit with IPv4",
   700  		},
   701  		{
   702  			clusterCIDRStr:    "2001:beef:7f00::/39",
   703  			subNetMaskSize:    47,
   704  			subNetCIDRStr:     "2001:beef:7f00::/47",
   705  			expectedUsedBegin: 128,
   706  			expectedUsedEnd:   128,
   707  			expectErr:         false,
   708  			description:       "Occupy 128th Bit with IPv6",
   709  		},
   710  		{
   711  			clusterCIDRStr:    "127.0.0.0/7",
   712  			subNetMaskSize:    18,
   713  			subNetCIDRStr:     "127.0.0.0/15",
   714  			expectedUsedBegin: 1024,
   715  			expectedUsedEnd:   1031,
   716  			expectErr:         false,
   717  			description:       "Occupy 1031st Bit with IPv4",
   718  		},
   719  		{
   720  			clusterCIDRStr:    "2001:beef:7f00::/39",
   721  			subNetMaskSize:    50,
   722  			subNetCIDRStr:     "2001:beef:7f00::/47",
   723  			expectedUsedBegin: 1024,
   724  			expectedUsedEnd:   1031,
   725  			expectErr:         false,
   726  			description:       "Occupy 1031st Bit with IPv6",
   727  		},
   728  	}
   729  
   730  	for _, tc := range cases {
   731  		_, clusterCIDR, err := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   732  		if err != nil {
   733  			t.Fatalf("unexpected error: %v for %v", err, tc.description)
   734  		}
   735  
   736  		cs, err := NewCIDRSet(clusterCIDR, tc.subNetMaskSize)
   737  		if err != nil {
   738  			t.Fatalf("Error allocating CIDRSet for %v", tc.description)
   739  		}
   740  
   741  		_, subnetCIDR, err := netutils.ParseCIDRSloppy(tc.subNetCIDRStr)
   742  		if err != nil {
   743  			t.Fatalf("unexpected error: %v for %v", err, tc.description)
   744  		}
   745  
   746  		err = cs.Occupy(subnetCIDR)
   747  		if err == nil && tc.expectErr {
   748  			t.Errorf("expected error but got none for %v", tc.description)
   749  			continue
   750  		}
   751  		if err != nil && !tc.expectErr {
   752  			t.Errorf("unexpected error: %v for %v", err, tc.description)
   753  			continue
   754  		}
   755  
   756  		expectedUsed := big.Int{}
   757  		for i := tc.expectedUsedBegin; i <= tc.expectedUsedEnd; i++ {
   758  			expectedUsed.SetBit(&expectedUsed, i, 1)
   759  		}
   760  		if expectedUsed.Cmp(&cs.used) != 0 {
   761  			t.Errorf("error for %v", tc.description)
   762  		}
   763  	}
   764  }
   765  
   766  func TestCIDRSetv6(t *testing.T) {
   767  	cases := []struct {
   768  		clusterCIDRStr string
   769  		subNetMaskSize int
   770  		expectedCIDR   string
   771  		expectedCIDR2  string
   772  		expectErr      bool
   773  		description    string
   774  	}{
   775  		{
   776  			clusterCIDRStr: "127.0.0.0/8",
   777  			subNetMaskSize: 32,
   778  			expectErr:      false,
   779  			expectedCIDR:   "127.0.0.0/32",
   780  			expectedCIDR2:  "127.0.0.1/32",
   781  			description:    "Max cluster subnet size with IPv4",
   782  		},
   783  		{
   784  			clusterCIDRStr: "beef:1234::/32",
   785  			subNetMaskSize: 49,
   786  			expectErr:      true,
   787  			description:    "Max cluster subnet size with IPv6",
   788  		},
   789  		{
   790  			clusterCIDRStr: "2001:beef:1234:369b::/60",
   791  			subNetMaskSize: 64,
   792  			expectedCIDR:   "2001:beef:1234:3690::/64",
   793  			expectedCIDR2:  "2001:beef:1234:3691::/64",
   794  			expectErr:      false,
   795  			description:    "Allocate a few IPv6",
   796  		},
   797  	}
   798  	for _, tc := range cases {
   799  		t.Run(tc.description, func(t *testing.T) {
   800  			_, clusterCIDR, _ := netutils.ParseCIDRSloppy(tc.clusterCIDRStr)
   801  			a, err := NewCIDRSet(clusterCIDR, tc.subNetMaskSize)
   802  			if gotErr := err != nil; gotErr != tc.expectErr {
   803  				t.Fatalf("NewCIDRSet(%v, %v) = %v, %v; gotErr = %t, want %t", clusterCIDR, tc.subNetMaskSize, a, err, gotErr, tc.expectErr)
   804  			}
   805  			if a == nil {
   806  				return
   807  			}
   808  			p, err := a.AllocateNext()
   809  			if err == nil && tc.expectErr {
   810  				t.Errorf("a.AllocateNext() = nil, want error")
   811  			}
   812  			if err != nil && !tc.expectErr {
   813  				t.Errorf("a.AllocateNext() = %+v, want no error", err)
   814  			}
   815  			if !tc.expectErr {
   816  				if p != nil && p.String() != tc.expectedCIDR {
   817  					t.Fatalf("a.AllocateNext() got %+v, want %+v", p.String(), tc.expectedCIDR)
   818  				}
   819  			}
   820  			p2, err := a.AllocateNext()
   821  			if err == nil && tc.expectErr {
   822  				t.Errorf("a.AllocateNext() = nil, want error")
   823  			}
   824  			if err != nil && !tc.expectErr {
   825  				t.Errorf("a.AllocateNext() = %+v, want no error", err)
   826  			}
   827  			if !tc.expectErr {
   828  				if p2 != nil && p2.String() != tc.expectedCIDR2 {
   829  					t.Fatalf("a.AllocateNext() got %+v, want %+v", p2.String(), tc.expectedCIDR)
   830  				}
   831  			}
   832  		})
   833  	}
   834  }
   835  
   836  func TestCidrSetMetrics(t *testing.T) {
   837  	cidr := "10.0.0.0/16"
   838  	_, clusterCIDR, _ := netutils.ParseCIDRSloppy(cidr)
   839  	clearMetrics(map[string]string{"clusterCIDR": cidr})
   840  
   841  	// We have 256 free cidrs
   842  	a, err := NewCIDRSet(clusterCIDR, 24)
   843  	if err != nil {
   844  		t.Fatalf("unexpected error creating CidrSet: %v", err)
   845  	}
   846  
   847  	clusterMaskSize, _ := clusterCIDR.Mask.Size()
   848  	max := getMaxCIDRs(24, clusterMaskSize)
   849  	em := testMetrics{
   850  		usage:      0,
   851  		allocs:     0,
   852  		releases:   0,
   853  		allocTries: 0,
   854  		max:        float64(max),
   855  	}
   856  	expectMetrics(t, cidr, em)
   857  
   858  	// Allocate next all
   859  	for i := 1; i <= 256; i++ {
   860  		_, err := a.AllocateNext()
   861  		if err != nil {
   862  			t.Fatalf("unexpected error allocating a new CIDR: %v", err)
   863  		}
   864  		em := testMetrics{
   865  			usage:      float64(i) / float64(256),
   866  			allocs:     float64(i),
   867  			releases:   0,
   868  			allocTries: 0,
   869  			max:        float64(max),
   870  		}
   871  		expectMetrics(t, cidr, em)
   872  	}
   873  	// Release all
   874  	a.Release(clusterCIDR)
   875  	em = testMetrics{
   876  		usage:      0,
   877  		allocs:     256,
   878  		releases:   256,
   879  		allocTries: 0,
   880  		max:        float64(max),
   881  	}
   882  	expectMetrics(t, cidr, em)
   883  
   884  	// Allocate all
   885  	a.Occupy(clusterCIDR)
   886  	em = testMetrics{
   887  		usage:      1,
   888  		allocs:     512,
   889  		releases:   256,
   890  		allocTries: 0,
   891  		max:        float64(max),
   892  	}
   893  	expectMetrics(t, cidr, em)
   894  }
   895  
   896  func TestCidrSetMetricsHistogram(t *testing.T) {
   897  	cidr := "10.0.0.0/16"
   898  	_, clusterCIDR, _ := netutils.ParseCIDRSloppy(cidr)
   899  	clearMetrics(map[string]string{"clusterCIDR": cidr})
   900  
   901  	// We have 256 free cidrs
   902  	a, err := NewCIDRSet(clusterCIDR, 24)
   903  	if err != nil {
   904  		t.Fatalf("unexpected error creating CidrSet: %v", err)
   905  	}
   906  
   907  	clusterMaskSize, _ := clusterCIDR.Mask.Size()
   908  	max := getMaxCIDRs(24, clusterMaskSize)
   909  	em := testMetrics{
   910  		usage:      0,
   911  		allocs:     0,
   912  		releases:   0,
   913  		allocTries: 0,
   914  		max:        float64(max),
   915  	}
   916  	expectMetrics(t, cidr, em)
   917  
   918  	// Allocate half of the range
   919  	// Occupy does not update the nextCandidate
   920  	_, halfClusterCIDR, _ := netutils.ParseCIDRSloppy("10.0.0.0/17")
   921  	a.Occupy(halfClusterCIDR)
   922  	em = testMetrics{
   923  		usage:      0.5,
   924  		allocs:     128,
   925  		releases:   0,
   926  		allocTries: 0,
   927  		max:        float64(max),
   928  	}
   929  	expectMetrics(t, cidr, em)
   930  	// Allocate next should iterate until the next free cidr
   931  	// that is exactly the same number we allocated previously
   932  	_, err = a.AllocateNext()
   933  	if err != nil {
   934  		t.Fatalf("unexpected error allocating a new CIDR: %v", err)
   935  	}
   936  	em = testMetrics{
   937  		usage:      float64(129) / float64(256),
   938  		allocs:     129,
   939  		releases:   0,
   940  		allocTries: 128,
   941  		max:        float64(max),
   942  	}
   943  	expectMetrics(t, cidr, em)
   944  }
   945  
   946  func TestCidrSetMetricsDual(t *testing.T) {
   947  	// create IPv4 cidrSet
   948  	cidrIPv4 := "10.0.0.0/16"
   949  	_, clusterCIDRv4, _ := netutils.ParseCIDRSloppy(cidrIPv4)
   950  	clearMetrics(map[string]string{"clusterCIDR": cidrIPv4})
   951  
   952  	a, err := NewCIDRSet(clusterCIDRv4, 24)
   953  	if err != nil {
   954  		t.Fatalf("unexpected error creating CidrSet: %v", err)
   955  	}
   956  
   957  	clusterMaskSize, _ := clusterCIDRv4.Mask.Size()
   958  	maxIPv4 := getMaxCIDRs(24, clusterMaskSize)
   959  	em := testMetrics{
   960  		usage:      0,
   961  		allocs:     0,
   962  		releases:   0,
   963  		allocTries: 0,
   964  		max:        float64(maxIPv4),
   965  	}
   966  	expectMetrics(t, cidrIPv4, em)
   967  
   968  	// create IPv6 cidrSet
   969  	cidrIPv6 := "2001:db8::/48"
   970  	_, clusterCIDRv6, _ := netutils.ParseCIDRSloppy(cidrIPv6)
   971  	clearMetrics(map[string]string{"clusterCIDR": cidrIPv6})
   972  
   973  	b, err := NewCIDRSet(clusterCIDRv6, 64)
   974  	if err != nil {
   975  		t.Fatalf("unexpected error creating CidrSet: %v", err)
   976  	}
   977  
   978  	clusterMaskSize, _ = clusterCIDRv6.Mask.Size()
   979  	maxIPv6 := getMaxCIDRs(64, clusterMaskSize)
   980  	em = testMetrics{
   981  		usage:      0,
   982  		allocs:     0,
   983  		releases:   0,
   984  		allocTries: 0,
   985  		max:        float64(maxIPv6),
   986  	}
   987  	expectMetrics(t, cidrIPv6, em)
   988  
   989  	// Allocate all
   990  	a.Occupy(clusterCIDRv4)
   991  	em = testMetrics{
   992  		usage:      1,
   993  		allocs:     256,
   994  		releases:   0,
   995  		allocTries: 0,
   996  		max:        float64(maxIPv4),
   997  	}
   998  	expectMetrics(t, cidrIPv4, em)
   999  
  1000  	b.Occupy(clusterCIDRv6)
  1001  	em = testMetrics{
  1002  		usage:      1,
  1003  		allocs:     65536,
  1004  		releases:   0,
  1005  		allocTries: 0,
  1006  		max:        float64(maxIPv6),
  1007  	}
  1008  	expectMetrics(t, cidrIPv6, em)
  1009  
  1010  	// Release all
  1011  	a.Release(clusterCIDRv4)
  1012  	em = testMetrics{
  1013  		usage:      0,
  1014  		allocs:     256,
  1015  		releases:   256,
  1016  		allocTries: 0,
  1017  		max:        float64(maxIPv4),
  1018  	}
  1019  	expectMetrics(t, cidrIPv4, em)
  1020  	b.Release(clusterCIDRv6)
  1021  	em = testMetrics{
  1022  		usage:      0,
  1023  		allocs:     65536,
  1024  		releases:   65536,
  1025  		allocTries: 0,
  1026  		max:        float64(maxIPv6),
  1027  	}
  1028  	expectMetrics(t, cidrIPv6, em)
  1029  }
  1030  
  1031  func Test_getMaxCIDRs(t *testing.T) {
  1032  	cidrIPv4 := "10.0.0.0/16"
  1033  	_, clusterCIDRv4, _ := netutils.ParseCIDRSloppy(cidrIPv4)
  1034  
  1035  	cidrIPv6 := "2001:db8::/48"
  1036  	_, clusterCIDRv6, _ := netutils.ParseCIDRSloppy(cidrIPv6)
  1037  
  1038  	tests := []struct {
  1039  		name             string
  1040  		subNetMaskSize   int
  1041  		clusterCIDR      *net.IPNet
  1042  		expectedMaxCIDRs int
  1043  	}{
  1044  		{
  1045  			name:             "IPv4",
  1046  			subNetMaskSize:   24,
  1047  			clusterCIDR:      clusterCIDRv4,
  1048  			expectedMaxCIDRs: 256,
  1049  		},
  1050  		{
  1051  			name:             "IPv6",
  1052  			subNetMaskSize:   64,
  1053  			clusterCIDR:      clusterCIDRv6,
  1054  			expectedMaxCIDRs: 65536,
  1055  		},
  1056  	}
  1057  
  1058  	for _, test := range tests {
  1059  		t.Run(test.name, func(t *testing.T) {
  1060  			clusterMaskSize, _ := test.clusterCIDR.Mask.Size()
  1061  			maxCIDRs := getMaxCIDRs(test.subNetMaskSize, clusterMaskSize)
  1062  			if test.expectedMaxCIDRs != maxCIDRs {
  1063  				t.Errorf("incorrect maxCIDRs, expected: %d, got: %d", test.expectedMaxCIDRs, maxCIDRs)
  1064  			}
  1065  		})
  1066  	}
  1067  }
  1068  
  1069  // Metrics helpers
  1070  func clearMetrics(labels map[string]string) {
  1071  	cidrSetAllocations.Delete(labels)
  1072  	cidrSetReleases.Delete(labels)
  1073  	cidrSetUsage.Delete(labels)
  1074  	cidrSetAllocationTriesPerRequest.Delete(labels)
  1075  	cidrSetMaxCidrs.Delete(labels)
  1076  }
  1077  
  1078  type testMetrics struct {
  1079  	usage      float64
  1080  	allocs     float64
  1081  	releases   float64
  1082  	allocTries float64
  1083  	max        float64
  1084  }
  1085  
  1086  func expectMetrics(t *testing.T, label string, em testMetrics) {
  1087  	var m testMetrics
  1088  	var err error
  1089  	m.usage, err = testutil.GetGaugeMetricValue(cidrSetUsage.WithLabelValues(label))
  1090  	if err != nil {
  1091  		t.Errorf("failed to get %s value, err: %v", cidrSetUsage.Name, err)
  1092  	}
  1093  	m.allocs, err = testutil.GetCounterMetricValue(cidrSetAllocations.WithLabelValues(label))
  1094  	if err != nil {
  1095  		t.Errorf("failed to get %s value, err: %v", cidrSetAllocations.Name, err)
  1096  	}
  1097  	m.releases, err = testutil.GetCounterMetricValue(cidrSetReleases.WithLabelValues(label))
  1098  	if err != nil {
  1099  		t.Errorf("failed to get %s value, err: %v", cidrSetReleases.Name, err)
  1100  	}
  1101  	m.allocTries, err = testutil.GetHistogramMetricValue(cidrSetAllocationTriesPerRequest.WithLabelValues(label))
  1102  	if err != nil {
  1103  		t.Errorf("failed to get %s value, err: %v", cidrSetAllocationTriesPerRequest.Name, err)
  1104  	}
  1105  	m.max, err = testutil.GetGaugeMetricValue(cidrSetMaxCidrs.WithLabelValues(label))
  1106  	if err != nil {
  1107  		t.Errorf("failed to get %s value, err: %v", cidrSetMaxCidrs.Name, err)
  1108  	}
  1109  
  1110  	if m != em {
  1111  		t.Fatalf("metrics error: expected %v, received %v", em, m)
  1112  	}
  1113  }
  1114  
  1115  // Benchmarks
  1116  func benchmarkAllocateAllIPv6(cidr string, subnetMaskSize int, b *testing.B) {
  1117  	_, clusterCIDR, _ := netutils.ParseCIDRSloppy(cidr)
  1118  	a, _ := NewCIDRSet(clusterCIDR, subnetMaskSize)
  1119  	for n := 0; n < b.N; n++ {
  1120  		// Allocate the whole range + 1
  1121  		for i := 0; i <= a.maxCIDRs; i++ {
  1122  			a.AllocateNext()
  1123  		}
  1124  		// Release all
  1125  		a.Release(clusterCIDR)
  1126  	}
  1127  }
  1128  
  1129  func BenchmarkAllocateAll_48_52(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/48", 52, b) }
  1130  func BenchmarkAllocateAll_48_56(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/48", 56, b) }
  1131  
  1132  func BenchmarkAllocateAll_48_60(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/48", 60, b) }
  1133  func BenchmarkAllocateAll_48_64(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/48", 64, b) }
  1134  
  1135  func BenchmarkAllocateAll_64_68(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/64", 68, b) }
  1136  
  1137  func BenchmarkAllocateAll_64_72(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/64", 72, b) }
  1138  func BenchmarkAllocateAll_64_76(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/64", 76, b) }
  1139  
  1140  func BenchmarkAllocateAll_64_80(b *testing.B) { benchmarkAllocateAllIPv6("2001:db8::/64", 80, b) }
  1141  

View as plain text