set_test.go

Documentation: github.com/opencontainers/go-digest/digestset

     1  // Copyright 2020, 2020 OCI Contributors
     2  // Copyright 2017 Docker, Inc.
     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  //     https://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  package digestset
    17  
    18  import (
    19  	"crypto/sha256"
    20  	_ "crypto/sha512"
    21  	"encoding/binary"
    22  	"math/rand"
    23  	"testing"
    24  
    25  	digest "github.com/opencontainers/go-digest"
    26  )
    27  
    28  func assertEqualDigests(t *testing.T, d1, d2 digest.Digest) {
    29  	if d1 != d2 {
    30  		t.Fatalf("Digests do not match:\n\tActual: %s\n\tExpected: %s", d1, d2)
    31  	}
    32  }
    33  
    34  func TestLookup(t *testing.T) {
    35  	digests := []digest.Digest{
    36  		"sha256:1234511111111111111111111111111111111111111111111111111111111111",
    37  		"sha256:1234111111111111111111111111111111111111111111111111111111111111",
    38  		"sha256:1234611111111111111111111111111111111111111111111111111111111111",
    39  		"sha256:5432111111111111111111111111111111111111111111111111111111111111",
    40  		"sha256:6543111111111111111111111111111111111111111111111111111111111111",
    41  		"sha256:6432111111111111111111111111111111111111111111111111111111111111",
    42  		"sha256:6542111111111111111111111111111111111111111111111111111111111111",
    43  		"sha256:6532111111111111111111111111111111111111111111111111111111111111",
    44  	}
    45  
    46  	dset := NewSet()
    47  	for i := range digests {
    48  		if err := dset.Add(digests[i]); err != nil {
    49  			t.Fatal(err)
    50  		}
    51  	}
    52  
    53  	dgst, err := dset.Lookup("54")
    54  	if err != nil {
    55  		t.Fatal(err)
    56  	}
    57  	assertEqualDigests(t, dgst, digests[3])
    58  
    59  	_, err = dset.Lookup("1234")
    60  	if err == nil {
    61  		t.Fatal("Expected ambiguous error looking up: 1234")
    62  	}
    63  	if err != ErrDigestAmbiguous {
    64  		t.Fatal(err)
    65  	}
    66  
    67  	_, err = dset.Lookup("9876")
    68  	if err == nil {
    69  		t.Fatal("Expected not found error looking up: 9876")
    70  	}
    71  	if err != ErrDigestNotFound {
    72  		t.Fatal(err)
    73  	}
    74  
    75  	_, err = dset.Lookup("sha256:1234")
    76  	if err == nil {
    77  		t.Fatal("Expected ambiguous error looking up: sha256:1234")
    78  	}
    79  	if err != ErrDigestAmbiguous {
    80  		t.Fatal(err)
    81  	}
    82  
    83  	dgst, err = dset.Lookup("sha256:12345")
    84  	if err != nil {
    85  		t.Fatal(err)
    86  	}
    87  	assertEqualDigests(t, dgst, digests[0])
    88  
    89  	dgst, err = dset.Lookup("sha256:12346")
    90  	if err != nil {
    91  		t.Fatal(err)
    92  	}
    93  	assertEqualDigests(t, dgst, digests[2])
    94  
    95  	dgst, err = dset.Lookup("12346")
    96  	if err != nil {
    97  		t.Fatal(err)
    98  	}
    99  	assertEqualDigests(t, dgst, digests[2])
   100  
   101  	dgst, err = dset.Lookup("12345")
   102  	if err != nil {
   103  		t.Fatal(err)
   104  	}
   105  	assertEqualDigests(t, dgst, digests[0])
   106  }
   107  
   108  func TestAddDuplication(t *testing.T) {
   109  	digests := []digest.Digest{
   110  		"sha256:1234111111111111111111111111111111111111111111111111111111111111",
   111  		"sha256:1234511111111111111111111111111111111111111111111111111111111111",
   112  		"sha256:1234611111111111111111111111111111111111111111111111111111111111",
   113  		"sha256:5432111111111111111111111111111111111111111111111111111111111111",
   114  		"sha256:6543111111111111111111111111111111111111111111111111111111111111",
   115  		"sha512:65431111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111",
   116  		"sha512:65421111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111",
   117  		"sha512:65321111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111",
   118  	}
   119  
   120  	dset := NewSet()
   121  	for i := range digests {
   122  		if err := dset.Add(digests[i]); err != nil {
   123  			t.Fatal(err)
   124  		}
   125  	}
   126  
   127  	if len(dset.entries) != 8 {
   128  		t.Fatal("Invalid dset size")
   129  	}
   130  
   131  	if err := dset.Add(digest.Digest("sha256:1234511111111111111111111111111111111111111111111111111111111111")); err != nil {
   132  		t.Fatal(err)
   133  	}
   134  
   135  	if len(dset.entries) != 8 {
   136  		t.Fatal("Duplicate digest insert should not increase entries size")
   137  	}
   138  
   139  	if err := dset.Add(digest.Digest("sha384:123451111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111")); err != nil {
   140  		t.Fatal(err)
   141  	}
   142  
   143  	if len(dset.entries) != 9 {
   144  		t.Fatal("Insert with different algorithm should be allowed")
   145  	}
   146  }
   147  
   148  func TestRemove(t *testing.T) {
   149  	digests, err := createDigests(10)
   150  	if err != nil {
   151  		t.Fatal(err)
   152  	}
   153  
   154  	dset := NewSet()
   155  	for i := range digests {
   156  		if err := dset.Add(digests[i]); err != nil {
   157  			t.Fatal(err)
   158  		}
   159  	}
   160  
   161  	dgst, err := dset.Lookup(digests[0].String())
   162  	if err != nil {
   163  		t.Fatal(err)
   164  	}
   165  	if dgst != digests[0] {
   166  		t.Fatalf("Unexpected digest value:\n\tExpected: %s\n\tActual: %s", digests[0], dgst)
   167  	}
   168  
   169  	if err := dset.Remove(digests[0]); err != nil {
   170  		t.Fatal(err)
   171  	}
   172  
   173  	if _, err := dset.Lookup(digests[0].String()); err != ErrDigestNotFound {
   174  		t.Fatalf("Expected error %v when looking up removed digest, got %v", ErrDigestNotFound, err)
   175  	}
   176  }
   177  
   178  func TestAll(t *testing.T) {
   179  	digests, err := createDigests(100)
   180  	if err != nil {
   181  		t.Fatal(err)
   182  	}
   183  
   184  	dset := NewSet()
   185  	for i := range digests {
   186  		if err := dset.Add(digests[i]); err != nil {
   187  			t.Fatal(err)
   188  		}
   189  	}
   190  
   191  	all := map[digest.Digest]struct{}{}
   192  	for _, dgst := range dset.All() {
   193  		all[dgst] = struct{}{}
   194  	}
   195  
   196  	if len(all) != len(digests) {
   197  		t.Fatalf("Unexpected number of unique digests found:\n\tExpected: %d\n\tActual: %d", len(digests), len(all))
   198  	}
   199  
   200  	for i, dgst := range digests {
   201  		if _, ok := all[dgst]; !ok {
   202  			t.Fatalf("Missing element at position %d: %s", i, dgst)
   203  		}
   204  	}
   205  
   206  }
   207  
   208  func assertEqualShort(t *testing.T, actual, expected string) {
   209  	if actual != expected {
   210  		t.Fatalf("Unexpected short value:\n\tExpected: %s\n\tActual: %s", expected, actual)
   211  	}
   212  }
   213  
   214  func TestShortCodeTable(t *testing.T) {
   215  	digests := []digest.Digest{
   216  		"sha256:1234111111111111111111111111111111111111111111111111111111111111",
   217  		"sha256:1234511111111111111111111111111111111111111111111111111111111111",
   218  		"sha256:1234611111111111111111111111111111111111111111111111111111111111",
   219  		"sha256:5432111111111111111111111111111111111111111111111111111111111111",
   220  		"sha256:6543111111111111111111111111111111111111111111111111111111111111",
   221  		"sha256:6432111111111111111111111111111111111111111111111111111111111111",
   222  		"sha256:6542111111111111111111111111111111111111111111111111111111111111",
   223  		"sha256:6532111111111111111111111111111111111111111111111111111111111111",
   224  	}
   225  
   226  	dset := NewSet()
   227  	for i := range digests {
   228  		if err := dset.Add(digests[i]); err != nil {
   229  			t.Fatal(err)
   230  		}
   231  	}
   232  
   233  	dump := ShortCodeTable(dset, 2)
   234  
   235  	if len(dump) < len(digests) {
   236  		t.Fatalf("Error unexpected size: %d, expecting %d", len(dump), len(digests))
   237  	}
   238  	assertEqualShort(t, dump[digests[0]], "12341")
   239  	assertEqualShort(t, dump[digests[1]], "12345")
   240  	assertEqualShort(t, dump[digests[2]], "12346")
   241  	assertEqualShort(t, dump[digests[3]], "54")
   242  	assertEqualShort(t, dump[digests[4]], "6543")
   243  	assertEqualShort(t, dump[digests[5]], "64")
   244  	assertEqualShort(t, dump[digests[6]], "6542")
   245  	assertEqualShort(t, dump[digests[7]], "653")
   246  }
   247  
   248  func createDigests(count int) ([]digest.Digest, error) {
   249  	r := rand.New(rand.NewSource(25823))
   250  	digests := make([]digest.Digest, count)
   251  	for i := range digests {
   252  		h := sha256.New()
   253  		if err := binary.Write(h, binary.BigEndian, r.Int63()); err != nil {
   254  			return nil, err
   255  		}
   256  		digests[i] = digest.NewDigest("sha256", h)
   257  	}
   258  	return digests, nil
   259  }
   260  
   261  func benchAddNTable(b *testing.B, n int) {
   262  	digests, err := createDigests(n)
   263  	if err != nil {
   264  		b.Fatal(err)
   265  	}
   266  	b.ResetTimer()
   267  	for i := 0; i < b.N; i++ {
   268  		dset := &Set{entries: digestEntries(make([]*digestEntry, 0, n))}
   269  		for j := range digests {
   270  			if err = dset.Add(digests[j]); err != nil {
   271  				b.Fatal(err)
   272  			}
   273  		}
   274  	}
   275  }
   276  
   277  func benchLookupNTable(b *testing.B, n int, shortLen int) {
   278  	digests, err := createDigests(n)
   279  	if err != nil {
   280  		b.Fatal(err)
   281  	}
   282  	dset := &Set{entries: digestEntries(make([]*digestEntry, 0, n))}
   283  	for i := range digests {
   284  		if err := dset.Add(digests[i]); err != nil {
   285  			b.Fatal(err)
   286  		}
   287  	}
   288  	shorts := make([]string, 0, n)
   289  	for _, short := range ShortCodeTable(dset, shortLen) {
   290  		shorts = append(shorts, short)
   291  	}
   292  
   293  	b.ResetTimer()
   294  	for i := 0; i < b.N; i++ {
   295  		if _, err = dset.Lookup(shorts[i%n]); err != nil {
   296  			b.Fatal(err)
   297  		}
   298  	}
   299  }
   300  
   301  func benchRemoveNTable(b *testing.B, n int) {
   302  	digests, err := createDigests(n)
   303  	if err != nil {
   304  		b.Fatal(err)
   305  	}
   306  	b.ResetTimer()
   307  	for i := 0; i < b.N; i++ {
   308  		dset := &Set{entries: digestEntries(make([]*digestEntry, 0, n))}
   309  		b.StopTimer()
   310  		for j := range digests {
   311  			if err = dset.Add(digests[j]); err != nil {
   312  				b.Fatal(err)
   313  			}
   314  		}
   315  		b.StartTimer()
   316  		for j := range digests {
   317  			if err = dset.Remove(digests[j]); err != nil {
   318  				b.Fatal(err)
   319  			}
   320  		}
   321  	}
   322  }
   323  
   324  func benchShortCodeNTable(b *testing.B, n int, shortLen int) {
   325  	digests, err := createDigests(n)
   326  	if err != nil {
   327  		b.Fatal(err)
   328  	}
   329  	dset := &Set{entries: digestEntries(make([]*digestEntry, 0, n))}
   330  	for i := range digests {
   331  		if err := dset.Add(digests[i]); err != nil {
   332  			b.Fatal(err)
   333  		}
   334  	}
   335  
   336  	b.ResetTimer()
   337  	for i := 0; i < b.N; i++ {
   338  		ShortCodeTable(dset, shortLen)
   339  	}
   340  }
   341  
   342  func BenchmarkAdd10(b *testing.B) {
   343  	benchAddNTable(b, 10)
   344  }
   345  
   346  func BenchmarkAdd100(b *testing.B) {
   347  	benchAddNTable(b, 100)
   348  }
   349  
   350  func BenchmarkAdd1000(b *testing.B) {
   351  	benchAddNTable(b, 1000)
   352  }
   353  
   354  func BenchmarkRemove10(b *testing.B) {
   355  	benchRemoveNTable(b, 10)
   356  }
   357  
   358  func BenchmarkRemove100(b *testing.B) {
   359  	benchRemoveNTable(b, 100)
   360  }
   361  
   362  func BenchmarkRemove1000(b *testing.B) {
   363  	benchRemoveNTable(b, 1000)
   364  }
   365  
   366  func BenchmarkLookup10(b *testing.B) {
   367  	benchLookupNTable(b, 10, 12)
   368  }
   369  
   370  func BenchmarkLookup100(b *testing.B) {
   371  	benchLookupNTable(b, 100, 12)
   372  }
   373  
   374  func BenchmarkLookup1000(b *testing.B) {
   375  	benchLookupNTable(b, 1000, 12)
   376  }
   377  
   378  func BenchmarkShortCode10(b *testing.B) {
   379  	benchShortCodeNTable(b, 10, 12)
   380  }
   381  func BenchmarkShortCode100(b *testing.B) {
   382  	benchShortCodeNTable(b, 100, 12)
   383  }
   384  func BenchmarkShortCode1000(b *testing.B) {
   385  	benchShortCodeNTable(b, 1000, 12)
   386  }
   387
View as plain text