From f6f33c7a1989f7c5c109c72a2152dd27b23e8c15 Mon Sep 17 00:00:00 2001 From: "dependabot[bot]" <49699333+dependabot[bot]@users.noreply.github.com> Date: Wed, 25 Jan 2023 02:02:49 +0000 Subject: [PATCH] build(deps): bump github.com/bits-and-blooms/bitset from 1.2.0 to 1.5.0 Bumps [github.com/bits-and-blooms/bitset](https://github.com/bits-and-blooms/bitset) from 1.2.0 to 1.5.0. - [Release notes](https://github.com/bits-and-blooms/bitset/releases) - [Commits](https://github.com/bits-and-blooms/bitset/compare/v1.2.0...v1.5.0) --- updated-dependencies: - dependency-name: github.com/bits-and-blooms/bitset dependency-type: direct:production update-type: version-update:semver-minor ... Signed-off-by: dependabot[bot] --- go.mod | 2 +- go.sum | 3 +- .../bits-and-blooms/bitset/bitset.go | 231 +++++++++++------- vendor/modules.txt | 2 +- 4 files changed, 153 insertions(+), 85 deletions(-) diff --git a/go.mod b/go.mod index a45e2da843c..21cc1923f86 100644 --- a/go.mod +++ b/go.mod @@ -3,7 +3,7 @@ module github.com/opencontainers/runc go 1.15 require ( - github.com/bits-and-blooms/bitset v1.2.0 + github.com/bits-and-blooms/bitset v1.5.0 github.com/checkpoint-restore/go-criu/v5 v5.0.0 github.com/cilium/ebpf v0.6.2 github.com/containerd/console v1.0.3 diff --git a/go.sum b/go.sum index 7937c033bdb..feed67d988d 100644 --- a/go.sum +++ b/go.sum @@ -1,6 +1,7 @@ github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU= -github.com/bits-and-blooms/bitset v1.2.0 h1:Kn4yilvwNtMACtf1eYDlG8H77R07mZSPbMjLyS07ChA= github.com/bits-and-blooms/bitset v1.2.0/go.mod h1:gIdJ4wp64HaoK2YrL1Q5/N7Y16edYb8uY+O0FJTyyDA= +github.com/bits-and-blooms/bitset v1.5.0 h1:NpE8frKRLGHIcEzkR+gZhiioW1+WbYV6fKwD6ZIpQT8= +github.com/bits-and-blooms/bitset v1.5.0/go.mod h1:gIdJ4wp64HaoK2YrL1Q5/N7Y16edYb8uY+O0FJTyyDA= github.com/checkpoint-restore/go-criu/v5 v5.0.0 h1:TW8f/UvntYoVDMN1K2HlT82qH1rb0sOjpGw3m6Ym+i4= github.com/checkpoint-restore/go-criu/v5 v5.0.0/go.mod h1:cfwC0EG7HMUenopBsUf9d89JlCLQIfgVcNsNN0t6T2M= github.com/cilium/ebpf v0.6.2 h1:iHsfF/t4aW4heW2YKfeHrVPGdtYTL4C4KocpM8KTSnI= diff --git a/vendor/github.com/bits-and-blooms/bitset/bitset.go b/vendor/github.com/bits-and-blooms/bitset/bitset.go index d688806a54b..5751b686c65 100644 --- a/vendor/github.com/bits-and-blooms/bitset/bitset.go +++ b/vendor/github.com/bits-and-blooms/bitset/bitset.go @@ -33,7 +33,6 @@ Example use: As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets. - */ package bitset @@ -87,9 +86,20 @@ func (b *BitSet) safeSet() []uint64 { return b.set } +// SetBitsetFrom fills the bitset with an array of integers without creating a new BitSet instance +func (b *BitSet) SetBitsetFrom(buf []uint64) { + b.length = uint(len(buf)) * 64 + b.set = buf +} + // From is a constructor used to create a BitSet from an array of integers func From(buf []uint64) *BitSet { - return &BitSet{uint(len(buf)) * 64, buf} + return FromWithLength(uint(len(buf))*64, buf) +} + +// FromWithLength constructs from an array of integers and length. +func FromWithLength(len uint, set []uint64) *BitSet { + return &BitSet{len, set} } // Bytes returns the bitset as array of integers @@ -105,6 +115,17 @@ func wordsNeeded(i uint) int { return int((i + (wordSize - 1)) >> log2WordSize) } +// wordsNeededUnbound calculates the number of words needed for i bits, possibly exceeding the capacity. +// This function is useful if you know that the capacity cannot be exceeded (e.g., you have an existing bitmap). +func wordsNeededUnbound(i uint) int { + return int((i + (wordSize - 1)) >> log2WordSize) +} + +// wordsIndex calculates the index of words in a `uint64` +func wordsIndex(i uint) uint { + return i & (wordSize - 1) +} + // New creates a new BitSet with a hint that length bits will be required func New(length uint) (bset *BitSet) { defer func() { @@ -135,24 +156,22 @@ func (b *BitSet) Len() uint { return b.length } -// extendSetMaybe adds additional words to incorporate new bits if needed -func (b *BitSet) extendSetMaybe(i uint) { - if i >= b.length { // if we need more bits, make 'em - if i >= Cap() { - panic("You are exceeding the capacity") - } - nsize := wordsNeeded(i + 1) - if b.set == nil { - b.set = make([]uint64, nsize) - } else if cap(b.set) >= nsize { - b.set = b.set[:nsize] // fast resize - } else if len(b.set) < nsize { - newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x - copy(newset, b.set) - b.set = newset - } - b.length = i + 1 +// extendSet adds additional words to incorporate new bits if needed +func (b *BitSet) extendSet(i uint) { + if i >= Cap() { + panic("You are exceeding the capacity") } + nsize := wordsNeeded(i + 1) + if b.set == nil { + b.set = make([]uint64, nsize) + } else if cap(b.set) >= nsize { + b.set = b.set[:nsize] // fast resize + } else if len(b.set) < nsize { + newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x + copy(newset, b.set) + b.set = newset + } + b.length = i + 1 } // Test whether bit i is set. @@ -160,7 +179,7 @@ func (b *BitSet) Test(i uint) bool { if i >= b.length { return false } - return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0 + return b.set[i>>log2WordSize]&(1<>log2WordSize] |= 1 << (i & (wordSize - 1)) + if i >= b.length { // if we need more bits, make 'em + b.extendSet(i) + } + b.set[i>>log2WordSize] |= 1 << wordsIndex(i) return b } @@ -180,7 +201,7 @@ func (b *BitSet) Clear(i uint) *BitSet { if i >= b.length { return b } - b.set[i>>log2WordSize] &^= 1 << (i & (wordSize - 1)) + b.set[i>>log2WordSize] &^= 1 << wordsIndex(i) return b } @@ -205,7 +226,7 @@ func (b *BitSet) Flip(i uint) *BitSet { if i >= b.length { return b.Set(i) } - b.set[i>>log2WordSize] ^= 1 << (i & (wordSize - 1)) + b.set[i>>log2WordSize] ^= 1 << wordsIndex(i) return b } @@ -218,15 +239,18 @@ func (b *BitSet) FlipRange(start, end uint) *BitSet { if start >= end { return b } - - b.extendSetMaybe(end - 1) + if end-1 >= b.length { // if we need more bits, make 'em + b.extendSet(end - 1) + } var startWord uint = start >> log2WordSize var endWord uint = end >> log2WordSize - b.set[startWord] ^= ^(^uint64(0) << (start & (wordSize - 1))) + b.set[startWord] ^= ^(^uint64(0) << wordsIndex(start)) for i := startWord; i < endWord; i++ { b.set[i] = ^b.set[i] } - b.set[endWord] ^= ^uint64(0) >> (-end & (wordSize - 1)) + if end&(wordSize-1) != 0 { + b.set[endWord] ^= ^uint64(0) >> wordsIndex(-end) + } return b } @@ -254,7 +278,10 @@ func (b *BitSet) Shrink(lastbitindex uint) *BitSet { copy(shrunk, b.set[:idx]) b.set = shrunk b.length = length - b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1)))) + lastWordUsedBits := length % 64 + if lastWordUsedBits != 0 { + b.set[idx-1] &= allBits >> uint64(64-wordsIndex(lastWordUsedBits)) + } return b } @@ -283,7 +310,7 @@ func (b *BitSet) Compact() *BitSet { // this method could be extremely slow and in some cases might cause the entire BitSet // to be recopied. func (b *BitSet) InsertAt(idx uint) *BitSet { - insertAtElement := (idx >> log2WordSize) + insertAtElement := idx >> log2WordSize // if length of set is a multiple of wordSize we need to allocate more space first if b.isLenExactMultiple() { @@ -302,13 +329,13 @@ func (b *BitSet) InsertAt(idx uint) *BitSet { // generate a mask to extract the data that we need to shift left // within the element where we insert a bit - dataMask := ^(uint64(1)<> (i & (wordSize - 1)) + w = w >> wordsIndex(i) if w != 0 { return i + trailingZeroes64(w), true } @@ -413,21 +440,20 @@ func (b *BitSet) NextSet(i uint) (uint, bool) { // including possibly the current index and up to cap(buffer). // If the returned slice has len zero, then no more set bits were found // -// buffer := make([]uint, 256) // this should be reused -// j := uint(0) -// j, buffer = bitmap.NextSetMany(j, buffer) -// for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) { -// for k := range buffer { -// do something with buffer[k] -// } -// j += 1 -// } -// +// buffer := make([]uint, 256) // this should be reused +// j := uint(0) +// j, buffer = bitmap.NextSetMany(j, buffer) +// for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) { +// for k := range buffer { +// do something with buffer[k] +// } +// j += 1 +// } // // It is possible to retrieve all set bits as follow: // -// indices := make([]uint, bitmap.Count()) -// bitmap.NextSetMany(0, indices) +// indices := make([]uint, bitmap.Count()) +// bitmap.NextSetMany(0, indices) // // However if bitmap.Count() is large, it might be preferable to // use several calls to NextSetMany, for performance reasons. @@ -438,7 +464,7 @@ func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint) { if x >= len(b.set) || capacity == 0 { return 0, myanswer[:0] } - skip := i & (wordSize - 1) + skip := wordsIndex(i) word := b.set[x] >> skip myanswer = myanswer[:capacity] size := int(0) @@ -481,8 +507,8 @@ func (b *BitSet) NextClear(i uint) (uint, bool) { return 0, false } w := b.set[x] - w = w >> (i & (wordSize - 1)) - wA := allBits >> (i & (wordSize - 1)) + w = w >> wordsIndex(i) + wA := allBits >> wordsIndex(i) index := i + trailingZeroes64(^w) if w != wA && index < b.length { return index, true @@ -510,7 +536,7 @@ func (b *BitSet) ClearAll() *BitSet { // wordCount returns the number of words used in a bit set func (b *BitSet) wordCount() int { - return len(b.set) + return wordsNeededUnbound(b.length) } // Clone this BitSet @@ -522,9 +548,10 @@ func (b *BitSet) Clone() *BitSet { return c } -// Copy into a destination BitSet -// Returning the size of the destination BitSet -// like array copy +// Copy into a destination BitSet using the Go array copy semantics: +// the number of bits copied is the minimum of the number of bits in the current +// BitSet (Len()) and the destination Bitset. +// We return the number of bits copied in the destination BitSet. func (b *BitSet) Copy(c *BitSet) (count uint) { if c == nil { return @@ -536,9 +563,33 @@ func (b *BitSet) Copy(c *BitSet) (count uint) { if b.length < c.length { count = b.length } + // Cleaning the last word is needed to keep the invariant that other functions, such as Count, require + // that any bits in the last word that would exceed the length of the bitmask are set to 0. + c.cleanLastWord() return } +// CopyFull copies into a destination BitSet such that the destination is +// identical to the source after the operation, allocating memory if necessary. +func (b *BitSet) CopyFull(c *BitSet) { + if c == nil { + return + } + c.length = b.length + if len(b.set) == 0 { + if c.set != nil { + c.set = c.set[:0] + } + } else { + if cap(c.set) < len(b.set) { + c.set = make([]uint64, len(b.set)) + } else { + c.set = c.set[:len(b.set)] + } + copy(c.set, b.set) + } +} + // Count (number of set bits). // Also known as "popcount" or "population count". func (b *BitSet) Count() uint { @@ -561,10 +612,9 @@ func (b *BitSet) Equal(c *BitSet) bool { if b.length == 0 { // if they have both length == 0, then could have nil set return true } - // testing for equality shoud not transform the bitset (no call to safeSet) - - for p, v := range b.set { - if c.set[p] != v { + wn := b.wordCount() + for p:= 0; p < wn; p++ { + if c.set[p] != b.set[p] { return false } } @@ -671,7 +721,9 @@ func (b *BitSet) InPlaceIntersection(compare *BitSet) { b.set[i] = 0 } if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length-1 >= b.length { + b.extendSet(compare.length - 1) + } } } @@ -710,8 +762,8 @@ func (b *BitSet) InPlaceUnion(compare *BitSet) { if l > int(b.wordCount()) { l = int(b.wordCount()) } - if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length > 0 && compare.length-1 >= b.length { + b.extendSet(compare.length - 1) } for i := 0; i < l; i++ { b.set[i] |= compare.set[i] @@ -758,8 +810,8 @@ func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) { if l > int(b.wordCount()) { l = int(b.wordCount()) } - if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length > 0 && compare.length-1 >= b.length { + b.extendSet(compare.length - 1) } for i := 0; i < l; i++ { b.set[i] ^= compare.set[i] @@ -773,17 +825,17 @@ func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) { // Is the length an exact multiple of word sizes? func (b *BitSet) isLenExactMultiple() bool { - return b.length%wordSize == 0 + return wordsIndex(b.length) == 0 } // Clean last word by setting unused bits to 0 func (b *BitSet) cleanLastWord() { if !b.isLenExactMultiple() { - b.set[len(b.set)-1] &= allBits >> (wordSize - b.length%wordSize) + b.set[len(b.set)-1] &= allBits >> (wordSize - wordsIndex(b.length)) } } -// Complement computes the (local) complement of a biset (up to length bits) +// Complement computes the (local) complement of a bitset (up to length bits) func (b *BitSet) Complement() (result *BitSet) { panicIfNull(b) result = New(b.length) @@ -811,7 +863,6 @@ func (b *BitSet) None() bool { return false } } - return true } return true } @@ -852,7 +903,8 @@ func (b *BitSet) DumpAsBits() string { // BinaryStorageSize returns the binary storage requirements func (b *BitSet) BinaryStorageSize() int { - return binary.Size(uint64(0)) + binary.Size(b.set) + nWords := b.wordCount() + return binary.Size(uint64(0)) + binary.Size(b.set[:nWords]) } // WriteTo writes a BitSet to a stream @@ -866,7 +918,19 @@ func (b *BitSet) WriteTo(stream io.Writer) (int64, error) { } // Write set - err = binary.Write(stream, binaryOrder, b.set) + // current implementation of bufio.Writer is more memory efficient than + // binary.Write for large set + writer := bufio.NewWriter(stream) + var item = make([]byte, binary.Size(uint64(0))) // for serializing one uint64 + nWords := b.wordCount() + for i := range b.set[:nWords] { + binaryOrder.PutUint64(item, b.set[i]) + if nn, err := writer.Write(item); err != nil { + return int64(i*binary.Size(uint64(0)) + nn), err + } + } + + err = writer.Flush() return int64(b.BinaryStorageSize()), err } @@ -877,6 +941,9 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { // Read length first err := binary.Read(stream, binaryOrder, &length) if err != nil { + if err == io.EOF { + err = io.ErrUnexpectedEOF + } return 0, err } newset := New(uint(length)) @@ -885,10 +952,17 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { return 0, errors.New("unmarshalling error: type mismatch") } - // Read remaining bytes as set - err = binary.Read(stream, binaryOrder, newset.set) - if err != nil { - return 0, err + var item [8]byte + nWords := wordsNeeded(uint(length)) + reader := bufio.NewReader(io.LimitReader(stream, 8*int64(nWords))) + for i := 0; i < nWords; i++ { + if _, err := io.ReadFull(reader, item[:]); err != nil { + if err == io.EOF { + err = io.ErrUnexpectedEOF + } + return 0, err + } + newset.set[i] = binaryOrder.Uint64(item[:]) } *b = *newset @@ -898,25 +972,18 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { // MarshalBinary encodes a BitSet into a binary form and returns the result. func (b *BitSet) MarshalBinary() ([]byte, error) { var buf bytes.Buffer - writer := bufio.NewWriter(&buf) - - _, err := b.WriteTo(writer) + _, err := b.WriteTo(&buf) if err != nil { return []byte{}, err } - err = writer.Flush() - return buf.Bytes(), err } // UnmarshalBinary decodes the binary form generated by MarshalBinary. func (b *BitSet) UnmarshalBinary(data []byte) error { buf := bytes.NewReader(data) - reader := bufio.NewReader(buf) - - _, err := b.ReadFrom(reader) - + _, err := b.ReadFrom(buf) return err } diff --git a/vendor/modules.txt b/vendor/modules.txt index 24b3c52f52e..34867a9fdb3 100644 --- a/vendor/modules.txt +++ b/vendor/modules.txt @@ -1,4 +1,4 @@ -# github.com/bits-and-blooms/bitset v1.2.0 +# github.com/bits-and-blooms/bitset v1.5.0 ## explicit github.com/bits-and-blooms/bitset # github.com/checkpoint-restore/go-criu/v5 v5.0.0