Source file src/k8s.io/kubernetes/pkg/registry/core/service/allocator/bitmap_test.go

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

     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 allocator
    18  
    19  import (
    20  	"testing"
    21  
    22  	"k8s.io/apimachinery/pkg/util/sets"
    23  )
    24  
    25  func TestAllocate(t *testing.T) {
    26  	testCases := []struct {
    27  		name      string
    28  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
    29  		max       int
    30  		reserved  int
    31  	}{
    32  		{
    33  			name:      "NewAllocationMap",
    34  			allocator: NewAllocationMapWithOffset,
    35  			max:       32,
    36  			reserved:  0,
    37  		},
    38  		{
    39  			name:      "NewAllocationMapWithOffset max < 16",
    40  			allocator: NewAllocationMapWithOffset,
    41  			max:       8,
    42  			reserved:  0,
    43  		},
    44  		{
    45  			name:      "NewAllocationMapWithOffset max > 16",
    46  			allocator: NewAllocationMapWithOffset,
    47  			max:       128,
    48  			reserved:  16,
    49  		},
    50  		{
    51  			name:      "NewAllocationMapWithOffset max > 256",
    52  			allocator: NewAllocationMapWithOffset,
    53  			max:       1024,
    54  			reserved:  64,
    55  		},
    56  		{
    57  			name:      "NewAllocationMapWithOffset max value",
    58  			allocator: NewAllocationMapWithOffset,
    59  			max:       65535,
    60  			reserved:  256,
    61  		},
    62  	}
    63  	for _, tc := range testCases {
    64  		t.Run(tc.name, func(t *testing.T) {
    65  			m := tc.allocator(tc.max, "test", tc.reserved)
    66  
    67  			if _, ok, _ := m.AllocateNext(); !ok {
    68  				t.Fatalf("unexpected error")
    69  			}
    70  			if m.count != 1 {
    71  				t.Errorf("expect to get %d, but got %d", 1, m.count)
    72  			}
    73  			if f := m.Free(); f != tc.max-1 {
    74  				t.Errorf("expect to get %d, but got %d", tc.max-1, f)
    75  			}
    76  		})
    77  	}
    78  }
    79  
    80  func TestAllocateMax(t *testing.T) {
    81  	testCases := []struct {
    82  		name      string
    83  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
    84  		max       int
    85  		reserved  int
    86  	}{
    87  		{
    88  			name:      "NewAllocationMap",
    89  			allocator: NewAllocationMapWithOffset,
    90  			max:       32,
    91  			reserved:  0,
    92  		},
    93  		{
    94  			name:      "NewAllocationMapWithOffset max < 16",
    95  			allocator: NewAllocationMapWithOffset,
    96  			max:       8,
    97  			reserved:  0,
    98  		},
    99  		{
   100  			name:      "NewAllocationMapWithOffset max > 16",
   101  			allocator: NewAllocationMapWithOffset,
   102  			max:       128,
   103  			reserved:  16,
   104  		},
   105  		{
   106  			name:      "NewAllocationMapWithOffset max > 256",
   107  			allocator: NewAllocationMapWithOffset,
   108  			max:       1024,
   109  			reserved:  64,
   110  		},
   111  		{
   112  			name:      "NewAllocationMapWithOffset max value",
   113  			allocator: NewAllocationMapWithOffset,
   114  			max:       65535,
   115  			reserved:  256,
   116  		},
   117  	}
   118  	for _, tc := range testCases {
   119  		t.Run(tc.name, func(t *testing.T) {
   120  			m := tc.allocator(tc.max, "test", tc.reserved)
   121  			for i := 0; i < tc.max; i++ {
   122  				if ok, err := m.Allocate(i); !ok || err != nil {
   123  					t.Fatalf("unexpected error")
   124  				}
   125  			}
   126  			if _, ok, _ := m.AllocateNext(); ok {
   127  				t.Errorf("unexpected success")
   128  			}
   129  
   130  			if ok, err := m.Allocate(tc.max); ok || err == nil {
   131  				t.Fatalf("unexpected allocation")
   132  			}
   133  
   134  			if f := m.Free(); f != 0 {
   135  				t.Errorf("expect to get %d, but got %d", 0, f)
   136  			}
   137  		})
   138  	}
   139  }
   140  
   141  func TestAllocateNextMax(t *testing.T) {
   142  	testCases := []struct {
   143  		name      string
   144  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
   145  		max       int
   146  		reserved  int
   147  	}{
   148  		{
   149  			name:      "NewAllocationMap",
   150  			allocator: NewAllocationMapWithOffset,
   151  			max:       32,
   152  			reserved:  0,
   153  		},
   154  		{
   155  			name:      "NewAllocationMapWithOffset max < 16",
   156  			allocator: NewAllocationMapWithOffset,
   157  			max:       8,
   158  			reserved:  0,
   159  		},
   160  		{
   161  			name:      "NewAllocationMapWithOffset max > 16",
   162  			allocator: NewAllocationMapWithOffset,
   163  			max:       128,
   164  			reserved:  16,
   165  		},
   166  		{
   167  			name:      "NewAllocationMapWithOffset max > 256",
   168  			allocator: NewAllocationMapWithOffset,
   169  			max:       1024,
   170  			reserved:  64,
   171  		},
   172  		{
   173  			name:      "NewAllocationMapWithOffset max value",
   174  			allocator: NewAllocationMapWithOffset,
   175  			max:       65535,
   176  			reserved:  256,
   177  		},
   178  	}
   179  	for _, tc := range testCases {
   180  		t.Run(tc.name, func(t *testing.T) {
   181  			m := tc.allocator(tc.max, "test", tc.reserved)
   182  			for i := 0; i < tc.max; i++ {
   183  				if _, ok, _ := m.AllocateNext(); !ok {
   184  					t.Fatalf("unexpected error")
   185  				}
   186  			}
   187  			if _, ok, _ := m.AllocateNext(); ok {
   188  				t.Errorf("unexpected success")
   189  			}
   190  			if f := m.Free(); f != 0 {
   191  				t.Errorf("expect to get %d, but got %d", 0, f)
   192  			}
   193  		})
   194  	}
   195  }
   196  func TestAllocateError(t *testing.T) {
   197  	testCases := []struct {
   198  		name      string
   199  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
   200  		max       int
   201  		reserved  int
   202  	}{
   203  		{
   204  			name:      "NewAllocationMap",
   205  			allocator: NewAllocationMapWithOffset,
   206  			max:       32,
   207  			reserved:  0,
   208  		},
   209  		{
   210  			name:      "NewAllocationMapWithOffset max < 16",
   211  			allocator: NewAllocationMapWithOffset,
   212  			max:       8,
   213  			reserved:  0,
   214  		},
   215  		{
   216  			name:      "NewAllocationMapWithOffset max > 16",
   217  			allocator: NewAllocationMapWithOffset,
   218  			max:       128,
   219  			reserved:  16,
   220  		},
   221  		{
   222  			name:      "NewAllocationMapWithOffset max > 256",
   223  			allocator: NewAllocationMapWithOffset,
   224  			max:       1024,
   225  			reserved:  64,
   226  		},
   227  		{
   228  			name:      "NewAllocationMapWithOffset max value",
   229  			allocator: NewAllocationMapWithOffset,
   230  			max:       65535,
   231  			reserved:  256,
   232  		},
   233  	}
   234  	for _, tc := range testCases {
   235  		t.Run(tc.name, func(t *testing.T) {
   236  			m := tc.allocator(tc.max, "test", tc.reserved)
   237  			if ok, _ := m.Allocate(3); !ok {
   238  				t.Errorf("error allocate offset %v", 3)
   239  			}
   240  			if ok, _ := m.Allocate(3); ok {
   241  				t.Errorf("unexpected success")
   242  			}
   243  		})
   244  	}
   245  }
   246  
   247  func TestRelease(t *testing.T) {
   248  	testCases := []struct {
   249  		name      string
   250  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
   251  		max       int
   252  		reserved  int
   253  	}{
   254  		{
   255  			name:      "NewAllocationMap",
   256  			allocator: NewAllocationMapWithOffset,
   257  			max:       32,
   258  			reserved:  0,
   259  		},
   260  		{
   261  			name:      "NewAllocationMapWithOffset max < 16",
   262  			allocator: NewAllocationMapWithOffset,
   263  			max:       8,
   264  			reserved:  0,
   265  		},
   266  		{
   267  			name:      "NewAllocationMapWithOffset max > 16",
   268  			allocator: NewAllocationMapWithOffset,
   269  			max:       128,
   270  			reserved:  16,
   271  		},
   272  		{
   273  			name:      "NewAllocationMapWithOffset max > 256",
   274  			allocator: NewAllocationMapWithOffset,
   275  			max:       1024,
   276  			reserved:  64,
   277  		},
   278  		{
   279  			name:      "NewAllocationMapWithOffset max value",
   280  			allocator: NewAllocationMapWithOffset,
   281  			max:       65535,
   282  			reserved:  256,
   283  		},
   284  	}
   285  	for _, tc := range testCases {
   286  		t.Run(tc.name, func(t *testing.T) {
   287  			m := tc.allocator(tc.max, "test", tc.reserved)
   288  			offset := 3
   289  			if ok, _ := m.Allocate(offset); !ok {
   290  				t.Errorf("error allocate offset %v", offset)
   291  			}
   292  
   293  			if !m.Has(offset) {
   294  				t.Errorf("expect offset %v allocated", offset)
   295  			}
   296  
   297  			if err := m.Release(offset); err != nil {
   298  				t.Errorf("unexpected error: %v", err)
   299  			}
   300  
   301  			if m.Has(offset) {
   302  				t.Errorf("expect offset %v not allocated", offset)
   303  			}
   304  		})
   305  	}
   306  
   307  }
   308  
   309  func TestForEach(t *testing.T) {
   310  	testCases := []struct {
   311  		name      string
   312  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
   313  		max       int
   314  		reserved  int
   315  	}{
   316  		{
   317  			name:      "NewAllocationMap",
   318  			allocator: NewAllocationMapWithOffset,
   319  			max:       32,
   320  			reserved:  0,
   321  		},
   322  		{
   323  			name:      "NewAllocationMapWithOffset max < 16",
   324  			allocator: NewAllocationMapWithOffset,
   325  			max:       8,
   326  			reserved:  0,
   327  		},
   328  		{
   329  			name:      "NewAllocationMapWithOffset max > 16",
   330  			allocator: NewAllocationMapWithOffset,
   331  			max:       128,
   332  			reserved:  16,
   333  		},
   334  		{
   335  			name:      "NewAllocationMapWithOffset max > 256",
   336  			allocator: NewAllocationMapWithOffset,
   337  			max:       1024,
   338  			reserved:  64,
   339  		},
   340  		{
   341  			name:      "NewAllocationMapWithOffset max value",
   342  			allocator: NewAllocationMapWithOffset,
   343  			max:       65535,
   344  			reserved:  256,
   345  		},
   346  	}
   347  	for _, tc := range testCases {
   348  		t.Run(tc.name, func(t *testing.T) {
   349  			subTests := []sets.Int{
   350  				sets.NewInt(),
   351  				sets.NewInt(0),
   352  				sets.NewInt(0, 2, 5),
   353  				sets.NewInt(0, 1, 2, 3, 4, 5, 6, 7),
   354  			}
   355  
   356  			for i, ts := range subTests {
   357  				m := tc.allocator(tc.max, "test", tc.reserved)
   358  				for offset := range ts {
   359  					if ok, _ := m.Allocate(offset); !ok {
   360  						t.Errorf("[%d] error allocate offset %v", i, offset)
   361  					}
   362  					if !m.Has(offset) {
   363  						t.Errorf("[%d] expect offset %v allocated", i, offset)
   364  					}
   365  				}
   366  				calls := sets.NewInt()
   367  				m.ForEach(func(i int) {
   368  					calls.Insert(i)
   369  				})
   370  				if len(calls) != len(ts) {
   371  					t.Errorf("[%d] expected %d calls, got %d", i, len(ts), len(calls))
   372  				}
   373  				if !calls.Equal(ts) {
   374  					t.Errorf("[%d] expected calls to equal testcase: %v vs %v", i, calls.List(), ts.List())
   375  				}
   376  			}
   377  		})
   378  	}
   379  }
   380  
   381  func TestSnapshotAndRestore(t *testing.T) {
   382  	testCases := []struct {
   383  		name      string
   384  		allocator func(max int, rangeSpec string, reserved int) *AllocationBitmap
   385  		max       int
   386  		reserved  int
   387  	}{
   388  		{
   389  			name:      "NewAllocationMap",
   390  			allocator: NewAllocationMapWithOffset,
   391  			max:       32,
   392  			reserved:  0,
   393  		},
   394  		{
   395  			name:      "NewAllocationMapWithOffset max < 16",
   396  			allocator: NewAllocationMapWithOffset,
   397  			max:       8,
   398  			reserved:  0,
   399  		},
   400  		{
   401  			name:      "NewAllocationMapWithOffset max > 16",
   402  			allocator: NewAllocationMapWithOffset,
   403  			max:       128,
   404  			reserved:  16,
   405  		},
   406  		{
   407  			name:      "NewAllocationMapWithOffset max > 256",
   408  			allocator: NewAllocationMapWithOffset,
   409  			max:       1024,
   410  			reserved:  64,
   411  		},
   412  		{
   413  			name:      "NewAllocationMapWithOffset max value",
   414  			allocator: NewAllocationMapWithOffset,
   415  			max:       65535,
   416  			reserved:  256,
   417  		},
   418  	}
   419  	for _, tc := range testCases {
   420  		t.Run(tc.name, func(t *testing.T) {
   421  			m := tc.allocator(tc.max, "test", tc.reserved)
   422  			offset := 3
   423  			if ok, _ := m.Allocate(offset); !ok {
   424  				t.Errorf("error allocate offset %v", offset)
   425  			}
   426  			spec, bytes := m.Snapshot()
   427  
   428  			m2 := tc.allocator(10, "test", tc.reserved)
   429  			err := m2.Restore(spec, bytes)
   430  			if err != nil {
   431  				t.Errorf("unexpected error: %v", err)
   432  			}
   433  
   434  			if m2.count != 1 {
   435  				t.Errorf("expect count to %d, but got %d", 0, m.count)
   436  			}
   437  			if !m2.Has(offset) {
   438  				t.Errorf("expect offset %v allocated", offset)
   439  			}
   440  		})
   441  	}
   442  
   443  }
   444  
   445  // TestAllocateMaxReserved should allocate first values greater or equal than the reserved values
   446  func TestAllocateMax_BitmapReserved(t *testing.T) {
   447  	max := 128
   448  	dynamicOffset := 16
   449  
   450  	// just to double check off by one errors
   451  	allocated := 0
   452  	// modify if necessary
   453  	m := NewAllocationMapWithOffset(max, "test", dynamicOffset)
   454  	for i := 0; i < max-dynamicOffset; i++ {
   455  		if _, ok, _ := m.AllocateNext(); !ok {
   456  			t.Fatalf("unexpected error")
   457  		}
   458  		allocated++
   459  	}
   460  
   461  	if f := m.Free(); f != dynamicOffset {
   462  		t.Errorf("expect to get %d, but got %d", dynamicOffset-1, f)
   463  	}
   464  
   465  	for i := 0; i < dynamicOffset; i++ {
   466  		if m.Has(i) {
   467  			t.Errorf("unexpected allocated value %d", i)
   468  		}
   469  	}
   470  	// it should allocate one value of the reserved block
   471  	if _, ok, _ := m.AllocateNext(); !ok {
   472  		t.Fatalf("unexpected error")
   473  	}
   474  	allocated++
   475  	if allocated != m.count {
   476  		t.Errorf("expect to get %d, but got %d", allocated, m.count)
   477  	}
   478  
   479  	if m.count != max-dynamicOffset+1 {
   480  		t.Errorf("expect to get %d, but got %d", max-dynamicOffset+1, m.count)
   481  	}
   482  	if f := m.Free(); f != max-allocated {
   483  		t.Errorf("expect to get %d, but got %d", max-allocated, f)
   484  	}
   485  }
   486  
   487  func TestPreAllocateReservedFull_BitmapReserved(t *testing.T) {
   488  	max := 128
   489  	dynamicOffset := 16
   490  	// just to double check off by one errors
   491  	allocated := 0
   492  	m := NewAllocationMapWithOffset(max, "test", dynamicOffset)
   493  	// Allocate all possible values except the reserved
   494  	for i := dynamicOffset; i < max; i++ {
   495  		if ok, _ := m.Allocate(i); !ok {
   496  			t.Errorf("error allocate i %v", i)
   497  		} else {
   498  			allocated++
   499  		}
   500  	}
   501  	// Allocate all the values of the reserved block except one
   502  	for i := 0; i < dynamicOffset-1; i++ {
   503  		if ok, _ := m.Allocate(i); !ok {
   504  			t.Errorf("error allocate i %v", i)
   505  		} else {
   506  			allocated++
   507  		}
   508  	}
   509  
   510  	// there should be only one free value
   511  	if f := m.Free(); f != 1 {
   512  		t.Errorf("expect to get %d, but got %d", 1, f)
   513  	}
   514  	// check if the last free value is in the lower band
   515  	count := 0
   516  	for i := 0; i < dynamicOffset; i++ {
   517  		if !m.Has(i) {
   518  			count++
   519  		}
   520  	}
   521  	if count != 1 {
   522  		t.Errorf("expected one remaining free value, got %d", count)
   523  	}
   524  
   525  	if _, ok, _ := m.AllocateNext(); !ok {
   526  		t.Errorf("unexpected allocation error")
   527  	} else {
   528  		allocated++
   529  	}
   530  	if f := m.Free(); f != 0 {
   531  		t.Errorf("expect to get %d, but got %d", max-1, f)
   532  	}
   533  
   534  	if _, ok, _ := m.AllocateNext(); ok {
   535  		t.Errorf("unexpected success")
   536  	}
   537  	if m.count != allocated {
   538  		t.Errorf("expect to get %d, but got %d", max, m.count)
   539  	}
   540  	if f := m.Free(); f != 0 {
   541  		t.Errorf("expect to get %d, but got %d", max-1, f)
   542  	}
   543  }
   544  
   545  func TestAllocateUniqueness(t *testing.T) {
   546  	max := 128
   547  	dynamicOffset := 16
   548  	uniqueAllocated := map[int]bool{}
   549  	m := NewAllocationMapWithOffset(max, "test", dynamicOffset)
   550  
   551  	// Allocate all the values in both the dynamic and reserved blocks
   552  	for i := 0; i < max; i++ {
   553  		alloc, ok, _ := m.AllocateNext()
   554  		if !ok {
   555  			t.Fatalf("unexpected error")
   556  		}
   557  		if _, ok := uniqueAllocated[alloc]; ok {
   558  			t.Fatalf("unexpected allocated value %d", alloc)
   559  		} else {
   560  			uniqueAllocated[alloc] = true
   561  		}
   562  	}
   563  
   564  	if max != len(uniqueAllocated) {
   565  		t.Errorf("expect to get %d, but got %d", max, len(uniqueAllocated))
   566  	}
   567  }
   568  

View as plain text