Repository: rclone/rclone
Pull request #6663 (2023-01-02 09:02:56)

Port a fast C-implemented quickXorHash
<!--
Thank you very much for contributing code or documentation to rclone! Please
fill out the following questions to make it easier for us to review your
changes.

You do not need to check all the boxes below all at once, feel free to take
your time and add more commits. If you're done and ready for review, please
check the last box.
-->

#### What is the purpose of this change?
speed up `onedrive Bussiness` specified hash algo by port the algo from a fast C-implementation from https://github.com/namazso/QuickXorHash
It was slower than a single HDD in my nas(N5105) so i done this

```
# goos: darwin
# goarch: arm64
# model: Apple M1 Pro 10-core
# Bench for every 1<<20 (1MB)
name             old time/op   new time/op    delta
QuickXorHash-10   2.01ms ± 1%    0.34ms ± 1%   -83.07%  (p=0.000 n=10+9)

name             old speed     new speed      delta
QuickXorHash-10  521MB/s ± 1%  3077MB/s ± 1%  +490.83%  (p=0.000 n=10+9)
```

Thanks for @namazso

<!--
Describe the changes here
-->

#### Was the change discussed in an issue or in the forum before?

Nope. 

<!--
Link issues and relevant forum posts here.
-->

#### Checklist

- [x] I have read the [contribution guidelines](https://github.com/rclone/rclone/blob/master/CONTRIBUTING.md#submitting-a-new-feature-or-bug-fix).
- [x] I have added tests for all changes in this PR if appropriate.
- [ ] I have added documentation for the changes if appropriate.
- [x] All commit messages are in [house style](https://github.com/rclone/rclone/blob/master/CONTRIBUTING.md#commit-messages).
- [x] I'm done, this Pull Request is ready for review :-)


LXY1226: Added another enhancement at [f440be0](https://github.com/rclone/rclone/pull/6663/commits/f440be03d235ca68b83a0702976698b495c4c207) and all tests passed but a bit of `unsafe` used 
```
goos: linux
goarch: amd64
pkg: od_down/quickxorhash
cpu: Intel(R) Celeron(R) N5105 @ 2.00GHz
name            old time/op   new time/op    delta
QuickXorHash-4   2.39ms ± 3%    0.13ms ± 1%    -94.61%  (p=0.000 n=9+9)

name            old speed     new speed      delta
QuickXorHash-4  438MB/s ± 3%  8125MB/s ± 1%  +1754.62%  (p=0.000 n=9+9)
```

namazso: No idea how Go works, but my original C version relies on the compiler to vectorize and maybe unroll the block xors. Is the Go compiler bad at that? Maybe there's some hinting macros?
The most compatible fastest way on x86 would be with SSE, doing 128 bits at a time. This is also what clang does: https://godbolt.org/z/5GePfhzG5
LXY1226: > reply https://github.com/rclone/rclone/pull/6663#issuecomment-1369460462

hmm yes, gc (go compiler) is just make that loop xor in bytes, so i [manual adjust](https://github.com/rclone/rclone/pull/6663/commits/f440be03d235ca68b83a0702976698b495c4c207) it to 8-bytes for a balance between speed and portability. most host supports 64-bit operations and gc would split it to 32-bit if necessary
and the SIMD version of xoring could be implemented by assembly only but losing portability between hosts... 
and that is fast enough! thanks for codes again @namazso
LXY1226: @ncw Thanks for review this!
Benchmark and some Fuzz test added.
all suggestions are accepted.

could you help me review again
ncw: Looks like this needs a bit of fixing up (some imports in the test code I think).
LXY1226: > Looks like this needs a bit of fixing up (some imports in the test code I think).

fixed (i think)  
im writing another onedrive operating tool so that tests is pasted here.. sorry about that
LXY1226: Benchmark results: 
```
goos: linux
goarch: amd64
cpu: Intel(R) Celeron(R) N5105 @ 2.00GHz
QuickXorHash-Before  2.49ms   422MB/s ±11%  100.00%
QuickXorHash-Bytes    796µs  1317MB/s ± 1%  212.50% △212%
QuickXorHash-uint64   129µs  8129MB/s ± 1% 1828.46% △617%
QuickXorHash-Subtle  87.9µs 11932MB/s ± 5% 2730.83% △146%
```
Cnly: The performance boost looks impressive indeed :) But I also kinda think we may not need to bring the `unsafe` into the code at this point. For one thing it might need extra effort to validate maintain, as @ncw said. For another, go 1.20 is around the corner and, if I understand correctly, we'll get the even larger boost without `unsafe`, which the majority of rclone users will also get if they install the official releases compiled with go 1.20. Even if we achieve better performance with `unsafe` now, we may quickly want to remove it again at that time.
LXY1226: okay, i'll try my best to achieve more without unsafe and push back later.
ncw: go1.20 is about to be released and rclone v1.61 will very likely be released using it.
ncw: I have merged to master now go1.20 to be the default compiler for rclone.

So if you want to adjust this PR so it uses the go1.20 goodness for go >= 1.20 (need build tag `go1.20`) that would be great :-)

The update to go1.20 took a lot longer than I thought it was going to as there were two changes in the go stdlib which caused regressions. All fixed now though.
LXY1226: Sorry for the lack of response recently 😢   
I have removed the `unsafe` part and it is ready to merge now. But I don't have a clue about the test failure mentioned above, can you help me trigger the pipeline again? 🤔 

Patch:
diff --git a/backend/onedrive/quickxorhash/quickxorhash.go b/backend/onedrive/quickxorhash/quickxorhash.go
index c918ca58a..242d704f1 100644
--- a/backend/onedrive/quickxorhash/quickxorhash.go
+++ b/backend/onedrive/quickxorhash/quickxorhash.go
@@ -7,51 +7,40 @@
 // See: https://docs.microsoft.com/en-us/onedrive/developer/code-snippets/quickxorhash
 package quickxorhash
 
-// This code was ported from the code snippet linked from
-// https://docs.microsoft.com/en-us/onedrive/developer/code-snippets/quickxorhash
-// Which has the copyright
-
-// ------------------------------------------------------------------------------
-//  Copyright (c) 2016 Microsoft Corporation
+// This code was ported from a fast C-implementation from
+// https://github.com/namazso/QuickXorHash
+// which has licenced as BSD Zero Clause License
+//
+// BSD Zero Clause License
 //
-//  Permission is hereby granted, free of charge, to any person obtaining a copy
-//  of this software and associated documentation files (the "Software"), to deal
-//  in the Software without restriction, including without limitation the rights
-//  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-//  copies of the Software, and to permit persons to whom the Software is
-//  furnished to do so, subject to the following conditions:
+// Copyright (c) 2022 namazso <admin@namazso.eu>
 //
-//  The above copyright notice and this permission notice shall be included in
-//  all copies or substantial portions of the Software.
+// Permission to use, copy, modify, and/or distribute this software for any
+// purpose with or without fee is hereby granted.
 //
-//  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-//  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-//  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-//  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-//  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-//  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-//  THE SOFTWARE.
-// ------------------------------------------------------------------------------
+// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+// PERFORMANCE OF THIS SOFTWARE.
 
-import (
-	"hash"
-)
+import "hash"
 
 const (
 	// BlockSize is the preferred size for hashing
 	BlockSize = 64
 	// Size of the output checksum
-	Size           = 20
-	bitsInLastCell = 32
-	shift          = 11
-	widthInBits    = 8 * Size
-	dataSize       = (widthInBits-1)/64 + 1
+	Size        = 20
+	shift       = 11
+	widthInBits = 8 * Size
+	dataSize    = shift * widthInBits
 )
 
 type quickXorHash struct {
-	data        [dataSize]uint64
-	lengthSoFar uint64
-	shiftSoFar  int
+	data [dataSize]byte
+	size uint64
 }
 
 // New returns a new hash.Hash computing the quickXorHash checksum.
@@ -70,94 +59,37 @@ func New() hash.Hash {
 //
 // Implementations must not retain p.
 func (q *quickXorHash) Write(p []byte) (n int, err error) {
-	currentshift := q.shiftSoFar
-
-	// The bitvector where we'll start xoring
-	vectorArrayIndex := currentshift / 64
-
-	// The position within the bit vector at which we begin xoring
-	vectorOffset := currentshift % 64
-	iterations := len(p)
-	if iterations > widthInBits {
-		iterations = widthInBits
+	var i int
+	// fill last remain
+	lastRemain := int(q.size) % dataSize
+	if lastRemain != 0 {
+		i += xorBytes(q.data[lastRemain:], p)
 	}
 
-	for i := 0; i < iterations; i++ {
-		isLastCell := vectorArrayIndex == len(q.data)-1
-		var bitsInVectorCell int
-		if isLastCell {
-			bitsInVectorCell = bitsInLastCell
-		} else {
-			bitsInVectorCell = 64
-		}
-
-		// There's at least 2 bitvectors before we reach the end of the array
-		if vectorOffset <= bitsInVectorCell-8 {
-			for j := i; j < len(p); j += widthInBits {
-				q.data[vectorArrayIndex] ^= uint64(p[j]) << uint(vectorOffset)
-			}
-		} else {
-			index1 := vectorArrayIndex
-			var index2 int
-			if isLastCell {
-				index2 = 0
-			} else {
-				index2 = vectorArrayIndex + 1
-			}
-			low := byte(bitsInVectorCell - vectorOffset)
-
-			xoredByte := byte(0)
-			for j := i; j < len(p); j += widthInBits {
-				xoredByte ^= p[j]
-			}
-			q.data[index1] ^= uint64(xoredByte) << uint(vectorOffset)
-			q.data[index2] ^= uint64(xoredByte) >> low
-		}
-		vectorOffset += shift
-		for vectorOffset >= bitsInVectorCell {
-			if isLastCell {
-				vectorArrayIndex = 0
-			} else {
-				vectorArrayIndex = vectorArrayIndex + 1
-			}
-			vectorOffset -= bitsInVectorCell
+	if i != len(p) {
+		for len(p)-i >= dataSize {
+			i += xorBytes(q.data[:], p[i:])
 		}
+		xorBytes(q.data[:], p[i:])
 	}
-
-	// Update the starting position in a circular shift pattern
-	q.shiftSoFar = (q.shiftSoFar + shift*(len(p)%widthInBits)) % widthInBits
-
-	q.lengthSoFar += uint64(len(p))
-
+	q.size += uint64(len(p))
 	return len(p), nil
 }
 
 // Calculate the current checksum
-func (q *quickXorHash) checkSum() (h [Size]byte) {
-	// Output the data as little endian bytes
-	ph := 0
-	for i := 0; i < len(q.data)-1; i++ {
-		d := q.data[i]
-		_ = h[ph+7] // bounds check
-		h[ph+0] = byte(d >> (8 * 0))
-		h[ph+1] = byte(d >> (8 * 1))
-		h[ph+2] = byte(d >> (8 * 2))
-		h[ph+3] = byte(d >> (8 * 3))
-		h[ph+4] = byte(d >> (8 * 4))
-		h[ph+5] = byte(d >> (8 * 5))
-		h[ph+6] = byte(d >> (8 * 6))
-		h[ph+7] = byte(d >> (8 * 7))
-		ph += 8
+func (q *quickXorHash) checkSum() (h [Size + 1]byte) {
+	for i := 0; i < dataSize; i++ {
+		shift := (i * 11) % 160
+		shiftBytes := shift / 8
+		shiftBits := shift % 8
+		shifted := int(q.data[i]) << shiftBits
+		h[shiftBytes] ^= byte(shifted)
+		h[shiftBytes+1] ^= byte(shifted >> 8)
 	}
-	// remaining 32 bits
-	d := q.data[len(q.data)-1]
-	h[Size-4] = byte(d >> (8 * 0))
-	h[Size-3] = byte(d >> (8 * 1))
-	h[Size-2] = byte(d >> (8 * 2))
-	h[Size-1] = byte(d >> (8 * 3))
+	h[0] ^= h[20]
 
 	// XOR the file length with the least significant bits in little endian format
-	d = q.lengthSoFar
+	d := q.size
 	h[Size-8] ^= byte(d >> (8 * 0))
 	h[Size-7] ^= byte(d >> (8 * 1))
 	h[Size-6] ^= byte(d >> (8 * 2))
@@ -174,7 +106,7 @@ func (q *quickXorHash) checkSum() (h [Size]byte) {
 // It does not change the underlying hash state.
 func (q *quickXorHash) Sum(b []byte) []byte {
 	hash := q.checkSum()
-	return append(b, hash[:]...)
+	return append(b, hash[:Size]...)
 }
 
 // Reset resets the Hash to its initial state.
@@ -196,8 +128,10 @@ func (q *quickXorHash) BlockSize() int {
 }
 
 // Sum returns the quickXorHash checksum of the data.
-func Sum(data []byte) [Size]byte {
+func Sum(data []byte) (h [Size]byte) {
 	var d quickXorHash
 	_, _ = d.Write(data)
-	return d.checkSum()
+	s := d.checkSum()
+	copy(h[:], s[:])
+	return h
 }
diff --git a/backend/onedrive/quickxorhash/xor.go b/backend/onedrive/quickxorhash/xor.go
new file mode 100644
index 000000000..895da8de9
--- /dev/null
+++ b/backend/onedrive/quickxorhash/xor.go
@@ -0,0 +1,20 @@
+//go:build !go1.20
+
+package quickxorhash
+
+func xorBytes(dst, src []byte) int {
+	n := len(dst)
+	if len(src) < n {
+		n = len(src)
+	}
+	if n == 0 {
+		return 0
+	}
+	dst = dst[:n]
+	//src = src[:n]
+	src = src[:len(dst)] // remove bounds check in loop
+	for i := range dst {
+		dst[i] ^= src[i]
+	}
+	return n
+}
diff --git a/backend/onedrive/quickxorhash/xor_1.20.go b/backend/onedrive/quickxorhash/xor_1.20.go
new file mode 100644
index 000000000..fb3556962
--- /dev/null
+++ b/backend/onedrive/quickxorhash/xor_1.20.go
@@ -0,0 +1,9 @@
+//go:build go1.20
+
+package quickxorhash
+
+import "crypto/subtle"
+
+func xorBytes(dst, src []byte) int {
+	return subtle.XORBytes(dst, src, dst)
+}
diff --git a/backend/oracleobjectstorage/options.go b/backend/oracleobjectstorage/options.go
index 2916157be..004465093 100644
--- a/backend/oracleobjectstorage/options.go
+++ b/backend/oracleobjectstorage/options.go
@@ -17,9 +17,7 @@ const (
 	defaultUploadCutoff        = fs.SizeSuffix(200 * 1024 * 1024)
 	defaultUploadConcurrency   = 10
 	maxUploadCutoff            = fs.SizeSuffix(5 * 1024 * 1024 * 1024)
-	minSleep                   = 100 * time.Millisecond
-	maxSleep                   = 5 * time.Minute
-	decayConstant              = 1 // bigger for slower decay, exponential
+	minSleep                   = 10 * time.Millisecond
 	defaultCopyTimeoutDuration = fs.Duration(time.Minute)
 )
 
diff --git a/backend/oracleobjectstorage/oracleobjectstorage.go b/backend/oracleobjectstorage/oracleobjectstorage.go
index 6f730f258..c5f64744d 100644
--- a/backend/oracleobjectstorage/oracleobjectstorage.go
+++ b/backend/oracleobjectstorage/oracleobjectstorage.go
@@ -64,14 +64,18 @@ func NewFs(ctx context.Context, name, root string, m configmap.Mapper) (fs.Fs, e
 	if err != nil {
 		return nil, err
 	}
-	p := pacer.NewDefault(pacer.MinSleep(minSleep), pacer.MaxSleep(maxSleep), pacer.DecayConstant(decayConstant))
+	pc := fs.NewPacer(ctx, pacer.NewS3(pacer.MinSleep(minSleep)))
+	// Set pacer retries to 2 (1 try and 1 retry) because we are
+	// relying on SDK retry mechanism, but we allow 2 attempts to
+	// retry directory listings after XMLSyntaxError
+	pc.SetRetries(2)
 	f := &Fs{
 		name:  name,
 		opt:   *opt,
 		ci:    ci,
 		srv:   objectStorageClient,
 		cache: bucket.NewCache(),
-		pacer: fs.NewPacer(ctx, p),
+		pacer: pc,
 	}
 	f.setRoot(root)
 	f.features = (&fs.Features{
diff --git a/docs/content/bisync.md b/docs/content/bisync.md
index 3258fffaf..1d99acdbb 100644
--- a/docs/content/bisync.md
+++ b/docs/content/bisync.md
@@ -164,14 +164,27 @@ deleting **everything** in the other path.
 Access check files are an additional safety measure against data loss.
 bisync will ensure it can find matching `RCLONE_TEST` files in the same places
 in the Path1 and Path2 filesystems.
+`RCLONE_TEST` files are not generated automatically.
+For `--check-access`to succeed, you must first either:
+**A)** Place one or more `RCLONE_TEST` files in the Path1 or Path2 filesystem
+and then do either a run without `--check-access` or a [--resync](#resync) to
+set matching files on both filesystems, or
+**B)** Set `--check-filename` to a filename already in use in various locations
+throughout your sync'd fileset.
 Time stamps and file contents are not important, just the names and locations.
-Place one or more `RCLONE_TEST` files in the Path1 or Path2 filesystem and
-then do either a run without `--check-access` or a `--resync` to set
-matching files on both filesystems.
 If you have symbolic links in your sync tree it is recommended to place
 `RCLONE_TEST` files in the linked-to directory tree to protect against
 bisync assuming a bunch of deleted files if the linked-to tree should not be
-accessible. Also see the `--check-filename` flag.
+accessible.
+See also the [--check-filename](--check-filename) flag.
+
+#### --check-filename
+
+Name of the file(s) used in access health validation.
+The default `--check-filename` is `RCLONE_TEST`.
+One or more files having this filename must exist, synchronized between your
+source and destination filesets, in order for `--check-access` to succeed.
+See [--check-access](#check-access) for additional details.
 
 #### --max-delete
 
diff --git a/docs/content/docs.md b/docs/content/docs.md
index 8c9cae769..b00177c2b 100644
--- a/docs/content/docs.md
+++ b/docs/content/docs.md
@@ -338,7 +338,7 @@ Will get their own names
 ### Valid remote names
 
 Remote names are case sensitive, and must adhere to the following rules:
- - May contain number, letter, `_`, `-`, `.` and space.
+ - May contain number, letter, `_`, `-`, `.`, `+`, `@` and space.
  - May not start with `-` or space.
  - May not end with space.
 
diff --git a/fs/fspath/path.go b/fs/fspath/path.go
index 5a6775207..09e71d08e 100644
--- a/fs/fspath/path.go
+++ b/fs/fspath/path.go
@@ -13,12 +13,12 @@ import (
 )
 
 const (
-	configNameRe              = `[\w\p{L}\p{N}.]+(?:[ -]+[\w\p{L}\p{N}.-]+)*` // May contain Unicode numbers and letters, as well as `_`, `-`, `.` and space, but not start with `-` (it complicates usage, see #4261) or space, and not end with space
-	illegalPartOfConfigNameRe = `^[ -]+|[^\w\p{L}\p{N}. -]+|[ ]+$`
+	configNameRe              = `[\w\p{L}\p{N}.+@]+(?:[ -]+[\w\p{L}\p{N}.+@-]+)*` // May contain Unicode numbers and letters, as well as `_` (covered by \w), `-`, `.`, `+`, `@` and space, but not start with `-` (it complicates usage, see #4261) or space, and not end with space
+	illegalPartOfConfigNameRe = `^[ -]+|[^\w\p{L}\p{N}.+@ -]+|[ ]+$`
 )
 
 var (
-	errInvalidCharacters = errors.New("config name contains invalid characters - may only contain numbers, letters, `_`, `-`, `.` and space, while not start with `-` or space, and not end with space")
+	errInvalidCharacters = errors.New("config name contains invalid characters - may only contain numbers, letters, `_`, `-`, `.`, `+`, `@` and space, while not start with `-` or space, and not end with space")
 	errCantBeEmpty       = errors.New("can't use empty string as a path")
 	errBadConfigParam    = errors.New("config parameters may only contain `0-9`, `A-Z`, `a-z` and `_`")
 	errEmptyConfigParam  = errors.New("config parameters can't be empty")


Test patch:
diff --git a/backend/onedrive/quickxorhash/quickxorhash_test.go b/backend/onedrive/quickxorhash/quickxorhash_test.go
index 51f6972d8..40539439d 100644
--- a/backend/onedrive/quickxorhash/quickxorhash_test.go
+++ b/backend/onedrive/quickxorhash/quickxorhash_test.go
@@ -4,6 +4,7 @@ import (
 	"encoding/base64"
 	"fmt"
 	"hash"
+	"math/rand"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
@@ -166,3 +167,16 @@ func TestReset(t *testing.T) {
 
 // check interface
 var _ hash.Hash = (*quickXorHash)(nil)
+
+func BenchmarkQuickXorHash(b *testing.B) {
+	b.SetBytes(1 << 20)
+	buf := make([]byte, 1<<20)
+	rand.Read(buf)
+	h := New()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		h.Reset()
+		h.Write(buf)
+		h.Sum(nil)
+	}
+}
diff --git a/fs/config/ui_test.go b/fs/config/ui_test.go
index 0756481d1..6a4d5aee0 100644
--- a/fs/config/ui_test.go
+++ b/fs/config/ui_test.go
@@ -183,7 +183,7 @@ func TestNewRemoteName(t *testing.T) {
 	config.ReadLine = makeReadLine([]string{
 		"test",           // already exists
 		"",               // empty string not allowed
-		"bad@characters", // bad characters
+		"bad^characters", // bad characters
 		"newname",        // OK
 	})
 
diff --git a/fs/fspath/path_test.go b/fs/fspath/path_test.go
index d1828c102..07becd876 100644
--- a/fs/fspath/path_test.go
+++ b/fs/fspath/path_test.go
@@ -41,6 +41,8 @@ func TestCheckConfigName(t *testing.T) {
 		{"..", nil, ".."},
 		{".r.e.m.o.t.e.", nil, ".r.e.m.o.t.e."},
 		{"rem ote", nil, "rem ote"},
+		{"user@example.com", nil, "user@example.com"},
+		{"user+junkmail@example.com", nil, "user+junkmail@example.com"},
 		{"blåbær", nil, "blåbær"},
 		{"chữ Quốc ngữ", nil, "chữ Quốc ngữ"},
 		{"remote ", errInvalidCharacters, "remote_"},
@@ -68,6 +70,8 @@ func TestCheckRemoteName(t *testing.T) {
 		{".r.e.m.o.t.e.:", nil},
 		{"-r-emote-:", errInvalidCharacters},
 		{"rem ote:", nil},
+		{"user@example.com:", nil},
+		{"user+junkmail@example.com:", nil},
 		{"blåbær:", nil},
 		{"chữ Quốc ngữ:", nil},
 		{"remote :", errInvalidCharacters},