Check in gVisor.

PiperOrigin-RevId: 194583126
Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463

7 files changed, 353 insertions, 0 deletions

diff --git a/pkg/bits/BUILD b/pkg/bits/BUILD
new file mode 100644
index 000000000..9897e5dc3
--- /dev/null
+++ b/pkg/bits/BUILD
@@ -0,0 +1,55 @@
+package(licenses = ["notice"])  # Apache 2.0
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance")
+
+go_library(
+    name = "bits",
+    srcs = [
+        "bits.go",
+        "bits32.go",
+        "bits64.go",
+        "uint64_arch_amd64.go",
+        "uint64_arch_amd64_asm.s",
+        "uint64_arch_generic.go",
+    ],
+    importpath = "gvisor.googlesource.com/gvisor/pkg/bits",
+    visibility = ["//:sandbox"],
+)
+
+go_template(
+    name = "bits_template",
+    srcs = ["bits_template.go"],
+    types = [
+        "T",
+    ],
+)
+
+go_template_instance(
+    name = "bits64",
+    out = "bits64.go",
+    package = "bits",
+    suffix = "64",
+    template = ":bits_template",
+    types = {
+        "T": "uint64",
+    },
+)
+
+go_template_instance(
+    name = "bits32",
+    out = "bits32.go",
+    package = "bits",
+    suffix = "32",
+    template = ":bits_template",
+    types = {
+        "T": "uint32",
+    },
+)
+
+go_test(
+    name = "bits_test",
+    size = "small",
+    srcs = ["uint64_test.go"],
+    embed = [":bits"],
+)
diff --git a/pkg/bits/bits.go b/pkg/bits/bits.go
new file mode 100644
index 000000000..50ca4bff7
--- /dev/null
+++ b/pkg/bits/bits.go
@@ -0,0 +1,16 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Package bits includes all bit related types and operations.
+package bits
diff --git a/pkg/bits/bits_template.go b/pkg/bits/bits_template.go
new file mode 100644
index 000000000..0a01f29c2
--- /dev/null
+++ b/pkg/bits/bits_template.go
@@ -0,0 +1,44 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bits
+
+// Non-atomic bit operations on a template type T.
+
+// T is a required type parameter that must be an integral type.
+type T uint64
+
+// IsOn returns true if *all* bits set in 'bits' are set in 'mask'.
+func IsOn(mask, bits T) bool {
+	return mask&bits == bits
+}
+
+// IsAnyOn returns true if *any* bit set in 'bits' is set in 'mask'.
+func IsAnyOn(mask, bits T) bool {
+	return mask&bits != 0
+}
+
+// Mask returns a T with all of the given bits set.
+func Mask(is ...int) T {
+	ret := T(0)
+	for _, i := range is {
+		ret |= MaskOf(i)
+	}
+	return ret
+}
+
+// MaskOf is like Mask, but sets only a single bit (more efficiently).
+func MaskOf(i int) T {
+	return T(1) << T(i)
+}
diff --git a/pkg/bits/uint64_arch_amd64.go b/pkg/bits/uint64_arch_amd64.go
new file mode 100644
index 000000000..068597f68
--- /dev/null
+++ b/pkg/bits/uint64_arch_amd64.go
@@ -0,0 +1,36 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build amd64
+
+package bits
+
+// TrailingZeros64 returns the number of bits before the least significant 1
+// bit in x; in other words, it returns the index of the least significant 1
+// bit in x. If x is 0, TrailingZeros64 returns 64.
+func TrailingZeros64(x uint64) int
+
+// MostSignificantOne64 returns the index of the most significant 1 bit in
+// x. If x is 0, MostSignificantOne64 returns 64.
+func MostSignificantOne64(x uint64) int
+
+// ForEachSetBit64 calls f once for each set bit in x, with argument i equal to
+// the set bit's index.
+func ForEachSetBit64(x uint64, f func(i int)) {
+	for x != 0 {
+		i := TrailingZeros64(x)
+		f(i)
+		x &^= MaskOf64(i)
+	}
+}
diff --git a/pkg/bits/uint64_arch_amd64_asm.s b/pkg/bits/uint64_arch_amd64_asm.s
new file mode 100644
index 000000000..33885641a
--- /dev/null
+++ b/pkg/bits/uint64_arch_amd64_asm.s
@@ -0,0 +1,31 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build amd64
+
+TEXT ·TrailingZeros64(SB),$0-16
+  BSFQ  x+0(FP), AX
+  JNZ   end
+  MOVQ  $64, AX
+end:
+  MOVQ  AX, ret+8(FP)
+  RET
+
+TEXT ·MostSignificantOne64(SB),$0-16
+  BSRQ  x+0(FP), AX
+  JNZ   end
+  MOVQ  $64, AX
+end:
+  MOVQ  AX, ret+8(FP)
+  RET
diff --git a/pkg/bits/uint64_arch_generic.go b/pkg/bits/uint64_arch_generic.go
new file mode 100644
index 000000000..862033a4b
--- /dev/null
+++ b/pkg/bits/uint64_arch_generic.go
@@ -0,0 +1,55 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// +build !amd64
+
+package bits
+
+// TrailingZeros64 returns the number of bits before the least significant 1
+// bit in x; in other words, it returns the index of the least significant 1
+// bit in x. If x is 0, TrailingZeros64 returns 64.
+func TrailingZeros64(x uint64) int {
+	if x == 0 {
+		return 64
+	}
+	i := 0
+	for ; x&1 == 0; i++ {
+		x >>= 1
+	}
+	return i
+}
+
+// MostSignificantOne64 returns the index of the most significant 1 bit in
+// x. If x is 0, MostSignificantOne64 returns 64.
+func MostSignificantOne64(x uint64) int {
+	if x == 0 {
+		return 64
+	}
+	i := 63
+	for ; x&(1<<63) == 0; i-- {
+		x <<= 1
+	}
+	return i
+}
+
+// ForEachSetBit64 calls f once for each set bit in x, with argument i equal to
+// the set bit's index.
+func ForEachSetBit64(x uint64, f func(i int)) {
+	for i := 0; x != 0; i++ {
+		if x&1 != 0 {
+			f(i)
+		}
+		x >>= 1
+	}
+}
diff --git a/pkg/bits/uint64_test.go b/pkg/bits/uint64_test.go
new file mode 100644
index 000000000..906017e1a
--- /dev/null
+++ b/pkg/bits/uint64_test.go
@@ -0,0 +1,116 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bits
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestTrailingZeros64(t *testing.T) {
+	for i := 0; i <= 64; i++ {
+		n := uint64(1) << uint(i)
+		if got, want := TrailingZeros64(n), i; got != want {
+			t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+
+	for i := 0; i < 64; i++ {
+		n := ^uint64(0) << uint(i)
+		if got, want := TrailingZeros64(n), i; got != want {
+			t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+
+	for i := 0; i < 64; i++ {
+		n := ^uint64(0) >> uint(i)
+		if got, want := TrailingZeros64(n), 0; got != want {
+			t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+}
+
+func TestMostSignificantOne64(t *testing.T) {
+	for i := 0; i <= 64; i++ {
+		n := uint64(1) << uint(i)
+		if got, want := MostSignificantOne64(n), i; got != want {
+			t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+
+	for i := 0; i < 64; i++ {
+		n := ^uint64(0) >> uint(i)
+		if got, want := MostSignificantOne64(n), 63-i; got != want {
+			t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+
+	for i := 0; i < 64; i++ {
+		n := ^uint64(0) << uint(i)
+		if got, want := MostSignificantOne64(n), 63; got != want {
+			t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+		}
+	}
+}
+
+func TestForEachSetBit64(t *testing.T) {
+	for _, want := range [][]int{
+		{},
+		{0},
+		{1},
+		{63},
+		{0, 1},
+		{1, 3, 5},
+		{0, 63},
+	} {
+		n := Mask64(want...)
+		// "Slice values are deeply equal when ... they are both nil or both
+		// non-nil ..."
+		got := make([]int, 0)
+		ForEachSetBit64(n, func(i int) {
+			got = append(got, i)
+		})
+		if !reflect.DeepEqual(got, want) {
+			t.Errorf("ForEachSetBit64(%#x): iterated bits %v, wanted %v", n, got, want)
+		}
+	}
+}
+
+func TestIsOn(t *testing.T) {
+	type spec struct {
+		mask uint64
+		bits uint64
+		any  bool
+		all  bool
+	}
+	for _, s := range []spec{
+		{Mask64(0), Mask64(0), true, true},
+		{Mask64(63), Mask64(63), true, true},
+		{Mask64(0), Mask64(1), false, false},
+		{Mask64(0), Mask64(0, 1), true, false},
+
+		{Mask64(1, 63), Mask64(1), true, true},
+		{Mask64(1, 63), Mask64(1, 63), true, true},
+		{Mask64(1, 63), Mask64(0, 1, 63), true, false},
+		{Mask64(1, 63), Mask64(0, 62), false, false},
+	} {
+		if ok := IsAnyOn64(s.mask, s.bits); ok != s.any {
+			t.Errorf("IsAnyOn(%#x, %#x) = %v, wanted: %v", s.mask, s.bits, ok, s.any)
+		}
+		if ok := IsOn64(s.mask, s.bits); ok != s.all {
+			t.Errorf("IsOn(%#x, %#x) = %v, wanted: %v", s.mask, s.bits, ok, s.all)
+		}
+	}
+}