Repository: kopia/kopia
Pull request #2389 (2022-09-09 23:07:38)

build(deps): bump github.com/aws/aws-sdk-go from 1.44.94 to 1.44.95
Bumps [github.com/aws/aws-sdk-go](https://github.com/aws/aws-sdk-go) from 1.44.94 to 1.44.95.
<details>
<summary>Release notes</summary>
<p><em>Sourced from <a href="https://github.com/aws/aws-sdk-go/releases">github.com/aws/aws-sdk-go's releases</a>.</em></p>
<blockquote>
<h1>Release v1.44.95 (2022-09-09)</h1>
<h3>Service Client Updates</h3>
<ul>
<li><code>service/cloudtrail</code>: Updates service API, documentation, and paginators
<ul>
<li>This release adds CloudTrail getChannel and listChannels APIs to allow customer to view the ServiceLinkedChannel configurations.</li>
</ul>
</li>
<li><code>service/models.lex.v2</code>: Updates service API and documentation</li>
<li><code>service/pi</code>: Updates service API</li>
<li><code>service/redshift</code>: Updates service documentation
<ul>
<li>This release updates documentation for AQUA features and other description updates.</li>
</ul>
</li>
<li><code>service/runtime.lex.v2</code>: Updates service API and documentation</li>
</ul>
</blockquote>
</details>
<details>
<summary>Changelog</summary>
<p><em>Sourced from <a href="https://github.com/aws/aws-sdk-go/blob/main/CHANGELOG.md">github.com/aws/aws-sdk-go's changelog</a>.</em></p>
<blockquote>
<h1>Release v1.44.95 (2022-09-09)</h1>
<h3>Service Client Updates</h3>
<ul>
<li><code>service/cloudtrail</code>: Updates service API, documentation, and paginators
<ul>
<li>This release adds CloudTrail getChannel and listChannels APIs to allow customer to view the ServiceLinkedChannel configurations.</li>
</ul>
</li>
<li><code>service/models.lex.v2</code>: Updates service API and documentation</li>
<li><code>service/pi</code>: Updates service API</li>
<li><code>service/redshift</code>: Updates service documentation
<ul>
<li>This release updates documentation for AQUA features and other description updates.</li>
</ul>
</li>
<li><code>service/runtime.lex.v2</code>: Updates service API and documentation</li>
</ul>
</blockquote>
</details>
<details>
<summary>Commits</summary>
<ul>
<li><a href="https://github.com/aws/aws-sdk-go/commit/9e7ca5ae08141365830537ac3a480fa44e92997f"><code>9e7ca5a</code></a> Release v1.44.95 (2022-09-09) (<a href="https://github-redirect.dependabot.com/aws/aws-sdk-go/issues/4553">#4553</a>)</li>
<li>See full diff in <a href="https://github.com/aws/aws-sdk-go/compare/v1.44.94...v1.44.95">compare view</a></li>
</ul>
</details>
<br />


[![Dependabot compatibility score](https://dependabot-badges.githubapp.com/badges/compatibility_score?dependency-name=github.com/aws/aws-sdk-go&package-manager=go_modules&previous-version=1.44.94&new-version=1.44.95)](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores)

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting `@dependabot rebase`.

[//]: # (dependabot-automerge-start)
Dependabot will merge this PR once CI passes on it, as requested by @kopia-builder.

[//]: # (dependabot-automerge-end)

---

<details>
<summary>Dependabot commands and options</summary>
<br />

You can trigger Dependabot actions by commenting on this PR:
- `@dependabot rebase` will rebase this PR
- `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it
- `@dependabot merge` will merge this PR after your CI passes on it
- `@dependabot squash and merge` will squash and merge this PR after your CI passes on it
- `@dependabot cancel merge` will cancel a previously requested merge and block automerging
- `@dependabot reopen` will reopen this PR if it is closed
- `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
- `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
- `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
- `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)


</details>

codecov[bot]: # [Codecov](https://codecov.io/gh/kopia/kopia/pull/2389?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia) Report
> Merging [#2389](https://codecov.io/gh/kopia/kopia/pull/2389?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia) (066cdd9) into [master](https://codecov.io/gh/kopia/kopia/commit/64c2fcd48192550ea91e702369580df1ea01ce66?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia) (64c2fcd) will **increase** coverage by `0.03%`.
> The diff coverage is `n/a`.

```diff
@@            Coverage Diff             @@
##           master    #2389      +/-   ##
==========================================
+ Coverage   74.37%   74.41%   +0.03%     
==========================================
  Files         436      436              
  Lines       34522    34522              
==========================================
+ Hits        25676    25688      +12     
+ Misses       6970     6961       -9     
+ Partials     1876     1873       -3     
```


| [Impacted Files](https://codecov.io/gh/kopia/kopia/pull/2389?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia) | Coverage Δ | |
|---|---|---|
| [repo/blob/throttling/throttling\_semaphore.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-cmVwby9ibG9iL3Rocm90dGxpbmcvdGhyb3R0bGluZ19zZW1hcGhvcmUuZ28=) | `97.05% <0.00%> (-2.95%)` | :arrow_down: |
| [internal/cache/persistent\_lru\_cache.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-aW50ZXJuYWwvY2FjaGUvcGVyc2lzdGVudF9scnVfY2FjaGUuZ28=) | `96.05% <0.00%> (-1.76%)` | :arrow_down: |
| [repo/open.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-cmVwby9vcGVuLmdv) | `74.53% <0.00%> (-1.11%)` | :arrow_down: |
| [snapshot/snapshotfs/upload.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-c25hcHNob3Qvc25hcHNob3Rmcy91cGxvYWQuZ28=) | `83.40% <0.00%> (+0.66%)` | :arrow_up: |
| [snapshot/snapshotfs/repofs.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-c25hcHNob3Qvc25hcHNob3Rmcy9yZXBvZnMuZ28=) | `80.80% <0.00%> (+1.51%)` | :arrow_up: |
| [repo/content/content\_manager\_iterate.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-cmVwby9jb250ZW50L2NvbnRlbnRfbWFuYWdlcl9pdGVyYXRlLmdv) | `91.71% <0.00%> (+2.20%)` | :arrow_up: |
| [cli/command\_content\_verify.go](https://codecov.io/gh/kopia/kopia/pull/2389/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia#diff-Y2xpL2NvbW1hbmRfY29udGVudF92ZXJpZnkuZ28=) | `81.03% <0.00%> (+6.03%)` | :arrow_up: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=kopia)


Patch:
diff --git a/.codecov.yml b/.codecov.yml
index ac94fc5e..fa4aeb64 100644
--- a/.codecov.yml
+++ b/.codecov.yml
@@ -25,4 +25,5 @@ ignore:
  - internal/repotesting/
  - internal/fshasher/
  - internal/blobtesting/
+ - internal/bigmap/bigmapbench/
  
\ No newline at end of file
diff --git a/cli/command_snapshot_fix.go b/cli/command_snapshot_fix.go
index 51ad751f..336809b0 100644
--- a/cli/command_snapshot_fix.go
+++ b/cli/command_snapshot_fix.go
@@ -64,12 +64,16 @@ func failedEntryCallback(rep repo.RepositoryWriter, enumVal string) snapshotfs.R
 }
 
 func (c *commonRewriteSnapshots) rewriteMatchingSnapshots(ctx context.Context, rep repo.RepositoryWriter, rewrite snapshotfs.RewriteDirEntryCallback) error {
-	rw := snapshotfs.NewDirRewriter(rep, snapshotfs.DirRewriterOptions{
+	rw, err := snapshotfs.NewDirRewriter(ctx, rep, snapshotfs.DirRewriterOptions{
 		Parallel:               c.parallel,
 		RewriteEntry:           rewrite,
 		OnDirectoryReadFailure: failedEntryCallback(rep, c.invalidDirHandling),
 	})
-	defer rw.Close()
+	if err != nil {
+		return errors.Wrap(err, "unable to create dir rewriter")
+	}
+
+	defer rw.Close(ctx)
 
 	var updatedSnapshots int
 
diff --git a/go.mod b/go.mod
index fc44390f..397b80cc 100644
--- a/go.mod
+++ b/go.mod
@@ -9,7 +9,7 @@ require (
 	github.com/GehirnInc/crypt v0.0.0-20200316065508-bb7000b8a962 // indirect
 	github.com/alecthomas/kingpin v1.3.8-0.20220615105907-eae6867f4166 // this is pulling master, which is newer than v2
 	github.com/alecthomas/units v0.0.0-20210927113745-59d0afb8317a
-	github.com/aws/aws-sdk-go v1.44.94
+	github.com/aws/aws-sdk-go v1.44.95
 	github.com/chmduquesne/rollinghash v4.0.0+incompatible
 	github.com/dustinkirkland/golang-petname v0.0.0-20191129215211-8e5a1ed0cff0
 	github.com/fatih/color v1.13.0
diff --git a/go.sum b/go.sum
index 3bf44969..657aa622 100644
--- a/go.sum
+++ b/go.sum
@@ -101,8 +101,8 @@ github.com/alecthomas/units v0.0.0-20210927113745-59d0afb8317a/go.mod h1:OMCwj8V
 github.com/alessio/shellescape v1.4.1 h1:V7yhSDDn8LP4lc4jS8pFkt0zCnzVJlG5JXy9BVKJUX0=
 github.com/alessio/shellescape v1.4.1/go.mod h1:PZAiSCk0LJaZkiCSkPv8qIobYglO3FPpyFjDCtHLS30=
 github.com/antihax/optional v1.0.0/go.mod h1:uupD/76wgC+ih3iEmQUL+0Ugr19nfwCT1kdvxnR2qWY=
-github.com/aws/aws-sdk-go v1.44.94 h1:hDqJSv03ZVvqT448gUE63JEIHKx++vKLoDkiZxbNmIk=
-github.com/aws/aws-sdk-go v1.44.94/go.mod h1:y4AeaBuwd2Lk+GepC1E9v0qOiTws0MIWAX4oIKwKHZo=
+github.com/aws/aws-sdk-go v1.44.95 h1:QwmA+PeR6v4pF0f/dPHVPWGAshAhb9TnGZBTM5uKuI8=
+github.com/aws/aws-sdk-go v1.44.95/go.mod h1:y4AeaBuwd2Lk+GepC1E9v0qOiTws0MIWAX4oIKwKHZo=
 github.com/benbjohnson/clock v1.1.0 h1:Q92kusRqC1XV2MjkWETPvjJVqKetz1OzxZB7mHJLju8=
 github.com/benbjohnson/clock v1.1.0/go.mod h1:J11/hYXuz8f4ySSvYwY0FKfm+ezbsZBKZxNJlLklBHA=
 github.com/beorn7/perks v0.0.0-20180321164747-3a771d992973/go.mod h1:Dwedo/Wpr24TaqPxmxbtue+5NUziq4I4S80YR8gNf3Q=
diff --git a/internal/bigmap/bigmap_internal.go b/internal/bigmap/bigmap_internal.go
new file mode 100644
index 00000000..691acaf8
--- /dev/null
+++ b/internal/bigmap/bigmap_internal.go
@@ -0,0 +1,476 @@
+// Package bigmap implements a custom hashmap data structure where keys and values are binary
+// and keys are meant to be well-distributed hashes, such as content IDs, object IDs, etc.
+//
+// Unlike regular maps this map is limited to adding and getting elements but does not support
+// any iteration or deletion, but is much more efficient in terms of memory usage.
+//
+// Data for the hash table is stored in large contiguous memory blocks (for small sets)
+// and automatically spills over to memory-mapped files for larger sets using only 8 bytes
+// per key in RAM.
+package bigmap
+
+import (
+	"bytes"
+	"context"
+	"encoding/binary"
+	"os"
+	"path/filepath"
+	"sync"
+
+	"github.com/edsrzf/mmap-go"
+	"github.com/google/uuid"
+	"github.com/pkg/errors"
+
+	"github.com/kopia/kopia/repo/logging"
+)
+
+const (
+	defaultNumMemorySegments    = 8          // number of segments to keep in RAM
+	defaultMemorySegmentSize    = 18 * 1e6   // 18MB enough to store >1M 16-17-byte keys
+	defaultFileSegmentSize      = 1024 << 20 // 1 GiB
+	defaultInitialSizeLogarithm = 20
+	mmapFileMode                = 0o600
+
+	// grow hash table above this percentage utilization, higher values (close to 100) will be very slow,
+	// smaller values will waste memory.
+	defaultLoadFactorPercentage = 75
+
+	minKeyLength = 4 // first 4 bytes of each key are used as uint32 hash value
+	maxKeyLength = 255
+
+	minSizeLogarithm = 8
+)
+
+var log = logging.Module("bigmap")
+
+// Options provides options for the internalMap.
+type Options struct {
+	LoadFactorPercentage int   // grow the size of the hash table when this percentage full
+	NumMemorySegments    int   // number of segments to keep in RAM
+	MemorySegmentSize    int64 // size of a single memory segment
+	FileSegmentSize      int   // size of a single file segment, defaults to 1 GiB
+
+	InitialSizeLogarithm int // logarithm of the initial size of the hash table, default - 20
+}
+
+// internalMap is a custom hashtable implementation using https://en.wikipedia.org/wiki/Double_hashing
+// that stores all (key,value) pairs densely packed in segments of fixed size to minimize data
+// fragmentation.
+type internalMap struct {
+	hasValues bool    // +checklocksignore
+	opts      Options // +checklocksignore
+
+	mu sync.RWMutex
+	// +checklocks:mu
+	tableSizeIndex int // index into tableSizesPrimes == len(slots)
+	// +checklocks:mu
+	segments []mmap.MMap // ([keyLength][key][valueLength][value])*
+	// +checklocks:mu
+	slots []entry // current hash table slots
+
+	// +checklocks:mu
+	count int // number of elements in the hash tables
+	// +checklocks:mu
+	h2Prime uint64 // prime < len(slots)
+
+	// +checklocks:mu
+	cleanups []func()
+
+	// +checklocks:mu
+	tempDir string
+}
+
+// The list of prime numbers close to 2^N from https://primes.utm.edu/lists/2small/0bit.html
+
+//nolint:gochecknoglobals
+var tableSizesPrimes = []uint64{
+	1<<8 - 59, // minSizeLogarithm
+	1<<9 - 55,
+	1<<10 - 57,
+	1<<11 - 61,
+	1<<12 - 77,
+	1<<13 - 91,
+	1<<14 - 111,
+	1<<15 - 135,
+	1<<16 - 123,
+	1<<17 - 99,
+	1<<18 - 93,
+	1<<19 - 87,
+	1<<20 - 185, // initial H2 prime
+	1<<21 - 129, // initial number of hashtable slots
+	1<<22 - 123,
+	1<<23 - 159,
+	1<<24 - 167,
+	1<<25 - 183,
+	1<<26 - 135,
+	1<<27 - 235,
+	1<<28 - 273,
+	1<<29 - 133,
+	1<<30 - 173,
+	1<<31 - 171,
+	1<<32 - 267,
+	1<<33 - 355,
+	1<<34 - 281,
+	1<<35 - 325,
+	1<<36 - 233,
+	1<<37 - 375,
+	1<<38 - 257,
+	1<<39 - 301,
+	1<<40 - 437,
+	1<<41 - 139,
+	1<<42 - 227,
+	1<<43 - 369,
+	1<<44 - 377,
+	1<<45 - 229,
+	1<<46 - 311,
+	1<<47 - 649,
+	1<<48 - 257,
+	1<<49 - 339,
+	1<<50 - 233,
+	1<<51 - 439,
+	1<<52 - 395,
+	1<<53 - 421,
+	1<<54 - 327,
+	1<<55 - 267,
+	1<<56 - 195,
+	1<<57 - 423,
+	1<<58 - 251,
+	1<<59 - 871,
+	1<<60 - 453,
+	1<<61 - 465,
+	1<<62 - 273,
+	1<<63 - 471,
+}
+
+type entry struct {
+	segment uint32 // 0-empty, otherwise index into internalMap.segments+1
+	offset  uint32 // offset within a segment
+}
+
+// Contains returns true if the provided key is in the map.
+func (m *internalMap) Contains(key []byte) bool {
+	m.mu.RLock()
+	defer m.mu.RUnlock()
+
+	slot := m.findSlot(key)
+
+	return m.slots[slot].segment != 0
+}
+
+// Get gets the value associated with a given key. It is appended to the provided buffer.
+func (m *internalMap) Get(buf, key []byte) ([]byte, bool) {
+	m.mu.RLock()
+	defer m.mu.RUnlock()
+
+	slot := m.findSlot(key)
+	e := m.slots[slot]
+
+	if e.segment == 0 {
+		return nil, false
+	}
+
+	if !m.hasValues {
+		return nil, true
+	}
+
+	data := m.segments[e.segment-1] // 1-indexed
+	koff := e.offset
+
+	off := koff + uint32(data[koff]) + 1
+	vlen, vlenLen := binary.Uvarint(data[off:])
+	start := off + uint32(vlenLen)
+
+	return append(buf, data[start:start+uint32(vlen)]...), true
+}
+
+func (m *internalMap) hashValue(key []byte) uint64 {
+	if len(key) < 8 { //nolint:gomnd
+		return uint64(binary.BigEndian.Uint32(key))
+	}
+
+	return binary.BigEndian.Uint64(key)
+}
+
+// h2 returns the secondary hash value used for double hashing.
+func (m *internalMap) h2(key []byte) uint64 {
+	if len(key) < 16 { //nolint:gomnd
+		// use linear scan.
+		return 1
+	}
+
+	return binary.BigEndian.Uint64(key[8:])
+}
+
+// +checklocksread:m.mu
+func (m *internalMap) keyEquals(e entry, key []byte) bool {
+	data := m.segments[e.segment-1] // 1-indexed
+	koff := e.offset
+	keyLen := uint32(data[koff])
+
+	return bytes.Equal(key, data[koff+1:koff+1+keyLen])
+}
+
+// +checklocksread:m.mu
+func (m *internalMap) findSlotInSlice(key []byte, slots []entry, h2Prime uint64) uint64 {
+	slot := m.hashValue(key) % uint64(len(slots))
+
+	delta := m.h2(key) % h2Prime
+	if delta == 0 {
+		delta = 1
+	}
+
+	for slots[slot].segment != 0 && !m.keyEquals(slots[slot], key) {
+		slot = (slot + delta) % uint64(len(slots))
+	}
+
+	return slot
+}
+
+// +checklocksread:m.mu
+func (m *internalMap) findSlot(key []byte) uint64 {
+	return m.findSlotInSlice(key, m.slots, m.h2Prime)
+}
+
+// +checklocks:m.mu
+func (m *internalMap) growLocked(newSize uint64) {
+	newSlots := make([]entry, newSize)
+	newH2Prime := uint64(len(m.slots))
+
+	for segNum, seg := range m.segments {
+		p := 0
+
+		for p < len(seg) && seg[p] != 0 {
+			koff := p
+			key := seg[p+1 : p+1+int(seg[p])]
+			p += len(key) + 1
+
+			if m.hasValues {
+				vlen, vlenLen := binary.Uvarint(seg[p:])
+				p += vlenLen + int(vlen)
+			}
+
+			slot := m.findSlotInSlice(key, newSlots, newH2Prime)
+			newSlots[slot] = entry{segment: uint32(segNum) + 1, offset: uint32(koff)}
+		}
+	}
+
+	m.h2Prime = newH2Prime
+	m.slots = newSlots
+}
+
+// PutIfAbsent conditionally adds the provided (key, value) to the map if the provided key is absent.
+func (m *internalMap) PutIfAbsent(ctx context.Context, key, value []byte) bool {
+	m.mu.Lock()
+	defer m.mu.Unlock()
+
+	if len(key) < minKeyLength {
+		panic("key too short")
+	}
+
+	if len(key) > maxKeyLength {
+		panic("key too long")
+	}
+
+	if !m.hasValues && len(value) > 0 {
+		panic("values are not enabled")
+	}
+
+	slot := m.findSlot(key)
+	if m.slots[slot].segment != 0 {
+		return false
+	}
+
+	if m.count >= len(m.slots)*m.opts.LoadFactorPercentage/100 {
+		m.tableSizeIndex++
+		m.growLocked(tableSizesPrimes[m.tableSizeIndex])
+		slot = m.findSlot(key)
+	}
+
+	payloadLength := 1 + len(key) + binary.MaxVarintLen32 + len(value)
+
+	current := m.segments[len(m.segments)-1]
+
+	// ensure that the key we're adding fits in the segment, start a new segment if not enough room.
+	if len(current)+payloadLength > cap(current) {
+		current = m.newSegment(ctx)
+		m.segments = append(m.segments, current)
+	}
+
+	koff := uint32(len(current))
+
+	current = append(current, byte(len(key)))
+	current = append(current, key...)
+
+	// append the value
+	if m.hasValues {
+		var vlen [binary.MaxVarintLen32]byte
+
+		n := binary.PutUvarint(vlen[:], uint64(len(value)))
+
+		current = append(current, vlen[0:n]...)
+		current = append(current, value...)
+	}
+
+	m.segments[len(m.segments)-1] = current
+	m.count++
+
+	m.slots[slot] = entry{
+		segment: uint32(len(m.segments)), // this is 1-based, 0==empty slot
+		offset:  koff,
+	}
+
+	return true
+}
+
+// +checklocks:m.mu
+func (m *internalMap) newMemoryMappedSegment(ctx context.Context) (mmap.MMap, error) {
+	flags := 0
+
+	f, err := m.maybeCreateMappedFile(ctx)
+	if err != nil {
+		return nil, err
+	}
+
+	s, err := mmap.MapRegion(f, m.opts.FileSegmentSize, mmap.RDWR, flags, 0)
+	if err != nil {
+		return nil, errors.Wrap(err, "unable to map region")
+	}
+
+	m.cleanups = append(m.cleanups, func() {
+		if err := s.Unmap(); err != nil {
+			log(ctx).Warnf("unable to unmap memory region: %v", err)
+		}
+	})
+
+	return s[:0], nil
+}
+
+// +checklocks:m.mu
+func (m *internalMap) maybeCreateMappedFile(ctx context.Context) (*os.File, error) {
+	if m.tempDir == "" {
+		tempDir, err := os.MkdirTemp("", "kopia-map")
+		if err != nil {
+			return nil, errors.Wrap(err, "unable to create temp directory")
+		}
+
+		m.tempDir = tempDir
+	}
+
+	fname := filepath.Join(m.tempDir, uuid.NewString())
+
+	f, err := os.OpenFile(fname, os.O_CREATE|os.O_EXCL|os.O_RDWR, mmapFileMode) //nolint:gosec
+	if err != nil {
+		return nil, errors.Wrap(err, "unable to create memory-mapped file")
+	}
+
+	if err := f.Truncate(int64(m.opts.FileSegmentSize)); err != nil {
+		closeAndRemoveFile(ctx, f, fname)
+
+		return nil, errors.Wrap(err, "unable to truncate memory-mapped file")
+	}
+
+	m.cleanups = append(m.cleanups, func() {
+		closeAndRemoveFile(ctx, f, fname)
+	})
+
+	return f, nil
+}
+
+func closeAndRemoveFile(ctx context.Context, f *os.File, fname string) {
+	if err := f.Close(); err != nil {
+		log(ctx).Warnf("unable to close segment file: %v", err)
+	}
+
+	if err := os.Remove(fname); err != nil {
+		log(ctx).Warnf("unable to remove segment file: %v", err)
+	}
+}
+
+// +checklocks:m.mu
+func (m *internalMap) newSegment(ctx context.Context) mmap.MMap {
+	var s mmap.MMap
+
+	if len(m.segments) >= m.opts.NumMemorySegments {
+		var err error
+
+		s, err = m.newMemoryMappedSegment(ctx)
+		if err != nil {
+			log(ctx).Warnf("unable to create memory-mapped segment: %v", err)
+		}
+	}
+
+	if s == nil {
+		s = make([]byte, 0, m.opts.MemorySegmentSize)
+	}
+
+	return s
+}
+
+// Close releases all resources associated with a map.
+func (m *internalMap) Close(ctx context.Context) {
+	m.mu.Lock()
+	defer m.mu.Unlock()
+
+	for i := len(m.cleanups) - 1; i >= 0; i-- {
+		m.cleanups[i]()
+	}
+
+	m.cleanups = nil
+	m.segments = nil
+
+	if m.tempDir != "" {
+		os.RemoveAll(m.tempDir) //nolint:errcheck
+	}
+}
+
+// newInternalMap creates new internalMap.
+func newInternalMap(ctx context.Context) (*internalMap, error) {
+	return newInternalMapWithOptions(ctx, true, nil)
+}
+
+// newInternalMapWithOptions creates a new instance of internalMap.
+func newInternalMapWithOptions(ctx context.Context, hasValues bool, opts *Options) (*internalMap, error) {
+	if opts == nil {
+		opts = &Options{}
+	}
+
+	if opts.LoadFactorPercentage == 0 {
+		opts.LoadFactorPercentage = defaultLoadFactorPercentage
+	}
+
+	if opts.MemorySegmentSize == 0 {
+		opts.MemorySegmentSize = defaultMemorySegmentSize
+	}
+
+	if opts.NumMemorySegments == 0 {
+		opts.NumMemorySegments = defaultNumMemorySegments
+	}
+
+	if opts.FileSegmentSize == 0 {
+		opts.FileSegmentSize = defaultFileSegmentSize
+	}
+
+	if opts.InitialSizeLogarithm == 0 {
+		opts.InitialSizeLogarithm = defaultInitialSizeLogarithm
+	}
+
+	tablewSizeIndex := opts.InitialSizeLogarithm - minSizeLogarithm
+
+	if tablewSizeIndex < 1 {
+		return nil, errors.Errorf("invalid initial size")
+	}
+
+	m := &internalMap{
+		hasValues:      hasValues,
+		opts:           *opts,
+		tableSizeIndex: tablewSizeIndex,
+		h2Prime:        tableSizesPrimes[tablewSizeIndex-1], // h2 prime < number of slots
+		slots:          make([]entry, tableSizesPrimes[tablewSizeIndex]),
+	}
+
+	m.mu.Lock()
+	m.segments = append(m.segments, m.newSegment(ctx))
+	m.mu.Unlock()
+
+	return m, nil
+}
diff --git a/internal/bigmap/bigmap_map.go b/internal/bigmap/bigmap_map.go
new file mode 100644
index 00000000..e210c677
--- /dev/null
+++ b/internal/bigmap/bigmap_map.go
@@ -0,0 +1,126 @@
+package bigmap
+
+import (
+	"context"
+	"crypto/aes"
+	"crypto/cipher"
+	"crypto/rand"
+	"encoding/binary"
+	"sync/atomic"
+
+	"github.com/pkg/errors"
+
+	"github.com/kopia/kopia/internal/gather"
+)
+
+const (
+	aesNonceSize = 12
+	aesKeySize   = 32 // AES-256
+)
+
+// Map is a wrapper around internalMap that adds encryption.
+type Map struct {
+	aead      cipher.AEAD
+	inner     *internalMap
+	nextNonce *uint64
+}
+
+// PutIfAbsent adds the element to the map, returns true if the element was added (as opposed to having
+// existed before).
+func (s *Map) PutIfAbsent(ctx context.Context, key, value []byte) bool {
+	if len(value) == 0 {
+		return s.inner.PutIfAbsent(ctx, key, nil)
+	}
+
+	var tmp gather.WriteBuffer
+	defer tmp.Close()
+
+	buf := tmp.MakeContiguous(aesNonceSize + len(value) + s.aead.Overhead())
+	nonce, input := buf[0:aesNonceSize], buf[aesNonceSize:aesNonceSize+len(value)]
+	copy(input, value)
+
+	nonceVal := atomic.AddUint64(s.nextNonce, 1)
+	if nonceVal == 0 {
+		panic("nonce counter wrapped beyond 64 bits, that should never happen")
+	}
+
+	binary.BigEndian.PutUint64(nonce, nonceVal)
+	s.aead.Seal(input[:0], nonce, input, key)
+
+	return s.inner.PutIfAbsent(ctx, key, buf)
+}
+
+// Get gets the element from the map and appends the value to the provided buffer.
+func (s *Map) Get(ctx context.Context, output, key []byte) (result []byte, ok bool, err error) {
+	if v, ok := s.inner.Get(output, key); ok {
+		result, err := s.decrypt(key, v)
+
+		return result, true, err
+	}
+
+	return nil, false, nil
+}
+
+func (s *Map) decrypt(key, buf []byte) ([]byte, error) {
+	if len(buf) == 0 {
+		return nil, nil
+	}
+
+	nonce, input := buf[0:aesNonceSize], buf[aesNonceSize:]
+
+	result, err := s.aead.Open(input[:0], nonce, input, key)
+	if err != nil {
+		return nil, errors.Errorf("unable to decrypt content: %v", err)
+	}
+
+	return result, nil
+}
+
+// Contains returns true if a given key exists in the set.
+func (s *Map) Contains(key []byte) bool {
+	return s.inner.Contains(key)
+}
+
+// Close releases resources associated with the set.
+func (s *Map) Close(ctx context.Context) {
+	s.inner.Close(ctx)
+}
+
+// NewMap creates new Map.
+func NewMap(ctx context.Context) (*Map, error) {
+	return NewMapWithOptions(ctx, nil)
+}
+
+// NewMapWithOptions creates new Map with options.
+func NewMapWithOptions(ctx context.Context, opt *Options) (*Map, error) {
+	inner, err := newInternalMapWithOptions(ctx, true, opt)
+	if err != nil {
+		return nil, err
+	}
+
+	key := make([]byte, aesKeySize)
+
+	if _, err = rand.Read(key); err != nil {
+		return nil, errors.Wrap(err, "error initializing map key")
+	}
+
+	enc, err := aes.NewCipher(key)
+	if err != nil {
+		return nil, errors.Wrap(err, "error initializing map cipher")
+	}
+
+	aead, err := cipher.NewGCM(enc)
+	if err != nil {
+		return nil, errors.Wrap(err, "error initializing map AEAD")
+	}
+
+	if aead.NonceSize() != aesNonceSize {
+		return nil, errors.Errorf("unexpected nonce size: %v, expected %v", aead.NonceSize(), aesNonceSize)
+	}
+
+	return &Map{
+		aead:      aead,
+		inner:     inner,
+		nextNonce: new(uint64),
+	}, nil
+}
diff --git a/internal/bigmap/bigmap_set.go b/internal/bigmap/bigmap_set.go
new file mode 100644
index 00000000..a170245a
--- /dev/null
+++ b/internal/bigmap/bigmap_set.go
@@ -0,0 +1,39 @@
+package bigmap
+
+import "context"
+
+// Set is a wrapper around Map that only supports Put() and Contains().
+type Set struct {
+	inner *internalMap
+}
+
+// Put adds the element to a set, returns true if the element was added (as opposed to having
+// existed before).
+func (s *Set) Put(ctx context.Context, key []byte) bool {
+	return s.inner.PutIfAbsent(ctx, key, nil)
+}
+
+// Contains returns true if a given key exists in the set.
+func (s *Set) Contains(key []byte) bool {
+	return s.inner.Contains(key)
+}
+
+// Close releases resources associated with the set.
+func (s *Set) Close(ctx context.Context) {
+	s.inner.Close(ctx)
+}
+
+// NewSet creates new Set.
+func NewSet(ctx context.Context) (*Set, error) {
+	return NewSetWithOptions(ctx, nil)
+}
+
+// NewSetWithOptions creates new Set with options.
+func NewSetWithOptions(ctx context.Context, opt *Options) (*Set, error) {
+	inner, err := newInternalMapWithOptions(ctx, false, opt)
+	if err != nil {
+		return nil, err
+	}
+
+	return &Set{inner}, nil
+}
diff --git a/internal/bigmap/bigmapbench/main.go b/internal/bigmap/bigmapbench/main.go
new file mode 100644
index 00000000..c276ee4e
--- /dev/null
+++ b/internal/bigmap/bigmapbench/main.go
@@ -0,0 +1,113 @@
+package main
+
+import (
+	"context"
+	"crypto/sha256"
+	"encoding/binary"
+	"flag"
+	"fmt"
+	"os"
+	"runtime"
+	"sync"
+	"time"
+
+	"github.com/pkg/profile"
+
+	"github.com/kopia/kopia/internal/bigmap"
+	"github.com/kopia/kopia/internal/clock"
+	"github.com/kopia/kopia/repo/logging"
+)
+
+const (
+	implSyncMap           = 0
+	implMapWithEmptyValue = 1
+	implMapWithValues     = 2
+)
+
+//nolint:gochecknoglobals
+var (
+	impl          = flag.Int("impl", implMapWithEmptyValue, "Select implementation")
+	profileDir    = flag.String("profile-dir", "", "Profile directory")
+	profileCPU    = flag.Bool("profile-cpu", false, "Profile CPU")
+	profileMemory = flag.Bool("profile-memory", false, "Profile RAM")
+)
+
+func main() {
+	flag.Parse()
+
+	ctx := logging.WithLogger(context.Background(), logging.ToWriter(os.Stderr))
+
+	var (
+		bm     *bigmap.Map
+		sm     *sync.Map
+		num    [8]byte
+		keyBuf [sha256.Size]byte
+		ms0    runtime.MemStats
+	)
+
+	if *profileDir != "" {
+		pp := profile.ProfilePath(*profileDir)
+
+		if *profileCPU {
+			defer profile.Start(pp, profile.CPUProfile).Stop()
+		}
+
+		if *profileMemory {
+			defer profile.Start(pp, profile.MemProfile).Stop()
+		}
+	}
+
+	switch *impl {
+	case implSyncMap:
+		sm = &sync.Map{}
+
+		fmt.Println("using sync.Map")
+	case implMapWithEmptyValue:
+		fmt.Println("using bigmap.Map without values")
+
+		bm, _ = bigmap.NewMapWithOptions(ctx, &bigmap.Options{})
+	case implMapWithValues:
+		fmt.Println("using bigmap.Map with values")
+
+		bm, _ = bigmap.NewMapWithOptions(ctx, &bigmap.Options{})
+	}
+
+	h := sha256.New()
+
+	runtime.ReadMemStats(&ms0)
+
+	t0 := clock.Now()
+
+	for i := 0; i < 300_000_000; i++ {
+		if i%1_000_000 == 0 && i > 0 {
+			var ms runtime.MemStats
+
+			runtime.ReadMemStats(&ms)
+
+			alloc := ms.HeapAlloc - ms0.HeapAlloc
+			dur := clock.Now().Sub(t0).Truncate(time.Second)
+
+			fmt.Printf("elapsed %v count: %v M bytes: %v MB bytes/item: %v Mitems/sec: %.1f\n",
+				dur,
+				float64(i)/1e6,
+				alloc/1e6,
+				alloc/uint64(i),
+				float64(i)/dur.Seconds()/1e6)
+		}
+
+		// generate key=sha256(i) without allocations.
+		h.Reset()
+		binary.LittleEndian.PutUint64(num[:], uint64(i))
+		h.Write(num[:])
+		h.Sum(keyBuf[:0])
+
+		switch *impl {
+		case implSyncMap:
+			sm.LoadOrStore(keyBuf, nil)
+		case implMapWithEmptyValue:
+			bm.PutIfAbsent(ctx, keyBuf[:], nil)
+		case implMapWithValues:
+			bm.PutIfAbsent(ctx, keyBuf[:], keyBuf[:])
+		}
+	}
+}
diff --git a/repo/content/content_manager_iterate.go b/repo/content/content_manager_iterate.go
index fee5fbd7..af563f82 100644
--- a/repo/content/content_manager_iterate.go
+++ b/repo/content/content_manager_iterate.go
@@ -9,6 +9,7 @@
 
 	"github.com/pkg/errors"
 
+	"github.com/kopia/kopia/internal/bigmap"
 	"github.com/kopia/kopia/repo/blob"
 	"github.com/kopia/kopia/repo/content/index"
 )
@@ -228,7 +229,12 @@ func(ci Info) error {
 
 // IterateUnreferencedBlobs returns the list of unreferenced storage blobs.
 func (bm *WriteManager) IterateUnreferencedBlobs(ctx context.Context, blobPrefixes []blob.ID, parallellism int, callback func(blob.Metadata) error) error {
-	var usedPacks sync.Map
+	usedPacks, err := bigmap.NewSet(ctx)
+	if err != nil {
+		return errors.Wrap(err, "new set")
+	}
+
+	defer usedPacks.Close(ctx)
 
 	bm.log.Debugf("determining blobs in use")
 	// find packs in use
@@ -240,7 +246,7 @@ func (bm *WriteManager) IterateUnreferencedBlobs(ctx context.Context, blobPrefix
 		},
 		func(pi PackInfo) error {
 			if pi.ContentCount > 0 {
-				usedPacks.Store(pi.PackID, struct{}{})
+				usedPacks.Put(ctx, []byte(pi.PackID))
 			}
 			return nil
 		}); err != nil {
@@ -270,7 +276,7 @@ func(pi PackInfo) error {
 
 	if err := blob.IterateAllPrefixesInParallel(ctx, parallellism, bm.st, prefixes,
 		func(bm blob.Metadata) error {
-			if _, ok := usedPacks.Load(bm.BlobID); ok {
+			if usedPacks.Contains([]byte(bm.BlobID)) {
 				return nil
 			}
 
diff --git a/repo/content/index/id.go b/repo/content/index/id.go
index 430f49a0..e57e046e 100644
--- a/repo/content/index/id.go
+++ b/repo/content/index/id.go
@@ -108,6 +108,19 @@ func (i ID) AppendToLogBuffer(sb *logging.Buffer) {
 	sb.AppendBytes(buf[0 : i.idLen*2])
 }
 
+// Append appends content ID to the slice.
+func (i ID) Append(out []byte) []byte {
+	var buf [128]byte
+
+	if i.prefix != 0 {
+		out = append(out, i.prefix)
+	}
+
+	hex.Encode(buf[0:i.idLen*2], i.data[0:i.idLen])
+
+	return append(out, buf[0:i.idLen*2]...)
+}
+
 // String returns a string representation of ID.
 func (i ID) String() string {
 	return string(i.Prefix()) + hex.EncodeToString(i.data[:i.idLen])
diff --git a/repo/object/objectid.go b/repo/object/objectid.go
index 663ed750..d078cfd9 100644
--- a/repo/object/objectid.go
+++ b/repo/object/objectid.go
@@ -80,6 +80,19 @@ func (i ID) String() string {
 	return indirectPrefix + compressionPrefix + i.cid.String()
 }
 
+// Append appends string representation of ObjectID that is suitable for displaying in the UI.
+func (i ID) Append(out []byte) []byte {
+	for j := 0; j < int(i.indirection); j++ {
+		out = append(out, 'I')
+	}
+
+	if i.compression {
+		out = append(out, 'Z')
+	}
+
+	return i.cid.Append(out)
+}
+
 // IndexObjectID returns the object ID of the underlying index object.
 func (i ID) IndexObjectID() (ID, bool) {
 	if i.indirection > 0 {
diff --git a/snapshot/snapshotfs/dir_rewriter.go b/snapshot/snapshotfs/dir_rewriter.go
index a98176fc..5dbb6deb 100644
--- a/snapshot/snapshotfs/dir_rewriter.go
+++ b/snapshot/snapshotfs/dir_rewriter.go
@@ -7,10 +7,10 @@
 	"encoding/json"
 	"path"
 	"runtime"
-	"sync"
 
 	"github.com/pkg/errors"
 
+	"github.com/kopia/kopia/internal/bigmap"
 	"github.com/kopia/kopia/internal/impossible"
 	"github.com/kopia/kopia/internal/workshare"
 	"github.com/kopia/kopia/repo"
@@ -53,7 +53,7 @@ type DirRewriter struct {
 	ws   *workshare.Pool
 	opts DirRewriterOptions
 
-	cache sync.Map
+	cache *bigmap.Map
 
 	rep repo.RepositoryWriter
 }
@@ -91,9 +91,16 @@ func (rw *DirRewriter) getCachedReplacement(ctx context.Context, parentPath stri
 	key := rw.getCacheKey(input)
 
 	// see if we already processed this exact directory entry
-	if v, ok := rw.cache.Load(key); ok {
-		//nolint:forcetypeassert
-		return v.(*snapshot.DirEntry).Clone(), nil
+	cached, ok, err := rw.cache.Get(ctx, nil, key[:])
+	if err != nil {
+		return nil, errors.Wrap(err, "cache get")
+	}
+
+	if ok {
+		de := &snapshot.DirEntry{}
+		jerr := json.Unmarshal(cached, de)
+
+		return de, errors.Wrap(jerr, "json unmarshal")
 	}
 
 	// entry not cached yet, run rewriter
@@ -114,10 +121,14 @@ func (rw *DirRewriter) getCachedReplacement(ctx context.Context, parentPath stri
 		result = rep2
 	}
 
-	actual, _ := rw.cache.LoadOrStore(key, result.Clone())
+	v, err := json.Marshal(result)
+	if err != nil {
+		return nil, errors.Wrap(err, "unable to marshal JSON")
+	}
+
+	rw.cache.PutIfAbsent(ctx, key[:], v)
 
-	//nolint:forcetypeassert
-	return actual.(*snapshot.DirEntry), nil
+	return result, nil
 }
 
 func (rw *DirRewriter) processDirectory(ctx context.Context, pathFromRoot string, entry *snapshot.DirEntry) (*snapshot.DirEntry, error) {
@@ -232,8 +243,10 @@ func (rw *DirRewriter) RewriteSnapshotManifest(ctx context.Context, man *snapsho
 }
 
 // Close closes the rewriter.
-func (rw *DirRewriter) Close() {
+func (rw *DirRewriter) Close(ctx context.Context) {
 	rw.ws.Close()
+
+	rw.cache.Close(ctx)
 }
 
 // RewriteKeep is a callback that keeps the unreadable entry.
@@ -294,7 +307,7 @@ func RewriteRemove(ctx context.Context, parentPath string, entry *snapshot.DirEn
 }
 
 // NewDirRewriter creates a new directory rewriter.
-func NewDirRewriter(rep repo.RepositoryWriter, opts DirRewriterOptions) *DirRewriter {
+func NewDirRewriter(ctx context.Context, rep repo.RepositoryWriter, opts DirRewriterOptions) (*DirRewriter, error) {
 	if opts.Parallel == 0 {
 		opts.Parallel = runtime.NumCPU()
 	}
@@ -303,9 +316,15 @@ func NewDirRewriter(rep repo.RepositoryWriter, opts DirRewriterOptions) *DirRewr
 		opts.OnDirectoryReadFailure = RewriteFail
 	}
 
-	return &DirRewriter{
-		ws:   workshare.NewPool(opts.Parallel - 1),
-		opts: opts,
-		rep:  rep,
+	cache, err := bigmap.NewMap(ctx)
+	if err != nil {
+		return nil, errors.Wrap(err, "new map")
 	}
+
+	return &DirRewriter{
+		ws:    workshare.NewPool(opts.Parallel - 1),
+		opts:  opts,
+		rep:   rep,
+		cache: cache,
+	}, nil
 }
diff --git a/snapshot/snapshotfs/snapshot_storage_stats.go b/snapshot/snapshotfs/snapshot_storage_stats.go
index b5f06c3a..d9ac7304 100644
--- a/snapshot/snapshotfs/snapshot_storage_stats.go
+++ b/snapshot/snapshotfs/snapshot_storage_stats.go
@@ -2,13 +2,13 @@
 
 import (
 	"context"
-	"sync"
 	"sync/atomic"
 	"time"
 
 	"github.com/pkg/errors"
 
 	"github.com/kopia/kopia/fs"
+	"github.com/kopia/kopia/internal/bigmap"
 	"github.com/kopia/kopia/repo"
 	"github.com/kopia/kopia/repo/object"
 	"github.com/kopia/kopia/snapshot"
@@ -24,9 +24,14 @@ func CalculateStorageStats(ctx context.Context, rep repo.Repository, manifests [
 	unique := new(snapshot.StorageUsageDetails)
 	runningTotal := new(snapshot.StorageUsageDetails)
 
-	var uniqueContents sync.Map
+	uniqueContents, err := bigmap.NewSet(ctx)
+	if err != nil {
+		return errors.Wrap(err, "NewSet")
+	}
+
+	defer uniqueContents.Close(ctx)
 
-	tw := NewTreeWalker(TreeWalkerOptions{
+	tw, twerr := NewTreeWalker(ctx, TreeWalkerOptions{
 		EntryCallback: func(ctx context.Context, entry fs.Entry, oid object.ID, entryPath string) error {
 			if !entry.IsDir() {
 				atomic.AddInt32(&unique.FileObjectCount, 1)
@@ -44,8 +49,10 @@ func CalculateStorageStats(ctx context.Context, rep repo.Repository, manifests [
 				return errors.Wrapf(err, "error verifying object %v", oid)
 			}
 
+			var cidbuf [128]byte
+
 			for _, cid := range contentIDs {
-				if _, loaded := uniqueContents.LoadOrStore(cid, struct{}{}); !loaded {
+				if uniqueContents.Put(ctx, cid.Append(cidbuf[:0])) {
 					atomic.AddInt32(&unique.ContentCount, 1)
 					atomic.AddInt32(&runningTotal.ContentCount, 1)
 
@@ -71,7 +78,10 @@ func CalculateStorageStats(ctx context.Context, rep repo.Repository, manifests [
 			return nil
 		},
 	})
-	defer tw.Close()
+	if twerr != nil {
+		return errors.Wrap(twerr, "tree walker")
+	}
+	defer tw.Close(ctx)
 
 	src := manifests[0].Source
 
diff --git a/snapshot/snapshotfs/snapshot_tree_walker.go b/snapshot/snapshotfs/snapshot_tree_walker.go
index 9757bd03..94a80d4e 100644
--- a/snapshot/snapshotfs/snapshot_tree_walker.go
+++ b/snapshot/snapshotfs/snapshot_tree_walker.go
@@ -9,6 +9,7 @@
 	"github.com/pkg/errors"
 
 	"github.com/kopia/kopia/fs"
+	"github.com/kopia/kopia/internal/bigmap"
 	"github.com/kopia/kopia/internal/workshare"
 	"github.com/kopia/kopia/repo/object"
 )
@@ -23,7 +24,7 @@
 type TreeWalker struct {
 	options TreeWalkerOptions
 
-	enqueued sync.Map
+	enqueued *bigmap.Set
 	wp       *workshare.Pool
 
 	mu sync.Mutex
@@ -85,9 +86,10 @@ func (w *TreeWalker) TooManyErrors() bool {
 	return w.numErrors >= w.options.MaxErrors
 }
 
-func (w *TreeWalker) alreadyProcessed(e fs.Entry) bool {
-	_, existing := w.enqueued.LoadOrStore(oidOf(e), struct{}{})
-	return existing
+func (w *TreeWalker) alreadyProcessed(ctx context.Context, e fs.Entry) bool {
+	var idbuf [128]byte
+
+	return !w.enqueued.Put(ctx, oidOf(e).Append(idbuf[:0]))
 }
 
 func (w *TreeWalker) processEntry(ctx context.Context, e fs.Entry, entryPath string) {
@@ -117,7 +119,7 @@ type errStop struct {
 			return errStop{errors.New("")}
 		}
 
-		if w.alreadyProcessed(ent) {
+		if w.alreadyProcessed(ctx, ent) {
 			return nil
 		}
 
@@ -146,7 +148,7 @@ func (w *TreeWalker) Process(ctx context.Context, e fs.Entry, entryPath string)
 		return errors.Errorf("entry does not have ObjectID")
 	}
 
-	if w.alreadyProcessed(e) {
+	if w.alreadyProcessed(ctx, e) {
 		return nil
 	}
 
@@ -156,8 +158,9 @@ func (w *TreeWalker) Process(ctx context.Context, e fs.Entry, entryPath string)
 }
 
 // Close closes the tree walker.
-func (w *TreeWalker) Close() {
+func (w *TreeWalker) Close(ctx context.Context) {
 	w.wp.Close()
+	w.enqueued.Close(ctx)
 }
 
 // TreeWalkerOptions provides optional fields for TreeWalker.
@@ -169,7 +172,7 @@ type TreeWalkerOptions struct {
 }
 
 // NewTreeWalker creates new tree walker.
-func NewTreeWalker(options TreeWalkerOptions) *TreeWalker {
+func NewTreeWalker(ctx context.Context, options TreeWalkerOptions) (*TreeWalker, error) {
 	if options.Parallelism <= 0 {
 		options.Parallelism = runtime.NumCPU() * walkersPerCPU
 	}
@@ -178,8 +181,14 @@ func NewTreeWalker(options TreeWalkerOptions) *TreeWalker {
 		options.MaxErrors = 1
 	}
 
-	return &TreeWalker{
-		options: options,
-		wp:      workshare.NewPool(options.Parallelism - 1),
+	s, err := bigmap.NewSet(ctx)
+	if err != nil {
+		return nil, errors.Wrap(err, "NewSet")
 	}
+
+	return &TreeWalker{
+		options:  options,
+		wp:       workshare.NewPool(options.Parallelism - 1),
+		enqueued: s,
+	}, nil
 }
diff --git a/snapshot/snapshotfs/snapshot_verifier.go b/snapshot/snapshotfs/snapshot_verifier.go
index 290745e1..5b376a11 100644
--- a/snapshot/snapshotfs/snapshot_verifier.go
+++ b/snapshot/snapshotfs/snapshot_verifier.go
@@ -129,12 +129,15 @@ type VerifierOptions struct {
 // InParallel starts parallel verification and invokes the provided function which can call
 // call Process() on in the provided TreeWalker.
 func (v *Verifier) InParallel(ctx context.Context, enqueue func(tw *TreeWalker) error) error {
-	tw := NewTreeWalker(TreeWalkerOptions{
+	tw, twerr := NewTreeWalker(ctx, TreeWalkerOptions{
 		Parallelism:   v.opts.Parallelism,
 		EntryCallback: v.verifyObject,
 		MaxErrors:     v.opts.MaxErrors,
 	})
-	defer tw.Close()
+	if twerr != nil {
+		return errors.Wrap(twerr, "tree walker")
+	}
+	defer tw.Close(ctx)
 
 	v.fileWorkQueue = make(chan verifyFileWorkItem, v.opts.FileQueueLength)
 
diff --git a/snapshot/snapshotgc/gc.go b/snapshot/snapshotgc/gc.go
index 318fed96..ef2c400e 100644
--- a/snapshot/snapshotgc/gc.go
+++ b/snapshot/snapshotgc/gc.go
@@ -3,12 +3,12 @@
 
 import (
 	"context"
-	"sync"
 	"time"
 
 	"github.com/pkg/errors"
 
 	"github.com/kopia/kopia/fs"
+	"github.com/kopia/kopia/internal/bigmap"
 	"github.com/kopia/kopia/internal/stats"
 	"github.com/kopia/kopia/internal/units"
 	"github.com/kopia/kopia/repo"
@@ -23,7 +23,7 @@
 
 var log = logging.Module("snapshotgc")
 
-func findInUseContentIDs(ctx context.Context, rep repo.Repository, used *sync.Map) error {
+func findInUseContentIDs(ctx context.Context, rep repo.Repository, used *bigmap.Set) error {
 	ids, err := snapshot.ListSnapshotManifests(ctx, rep, nil, nil)
 	if err != nil {
 		return errors.Wrap(err, "unable to list snapshot manifest IDs")
@@ -34,21 +34,27 @@ func findInUseContentIDs(ctx context.Context, rep repo.Repository, used *sync.Ma
 		return errors.Wrap(err, "unable to load manifest IDs")
 	}
 
-	w := snapshotfs.NewTreeWalker(snapshotfs.TreeWalkerOptions{
+	w, twerr := snapshotfs.NewTreeWalker(ctx, snapshotfs.TreeWalkerOptions{
 		EntryCallback: func(ctx context.Context, entry fs.Entry, oid object.ID, entryPath string) error {
-			contentIDs, err := rep.VerifyObject(ctx, oid)
-			if err != nil {
-				return errors.Wrapf(err, "error verifying %v", oid)
+			contentIDs, verr := rep.VerifyObject(ctx, oid)
+			if verr != nil {
+				return errors.Wrapf(verr, "error verifying %v", oid)
 			}
 
+			var cidbuf [128]byte
+
 			for _, cid := range contentIDs {
-				used.Store(cid, nil)
+				used.Put(ctx, cid.Append(cidbuf[:0]))
 			}
 
 			return nil
 		},
 	})
-	defer w.Close()
+	if twerr != nil {
+		return errors.Wrap(err, "unable to create tree walker")
+	}
+
+	defer w.Close(ctx)
 
 	log(ctx).Infof("Looking for active contents...")
 
@@ -93,13 +99,15 @@ func Run(ctx context.Context, rep repo.DirectRepositoryWriter, gcDelete bool, sa
 }
 
 func runInternal(ctx context.Context, rep repo.DirectRepositoryWriter, gcDelete bool, safety maintenance.SafetyParameters, maintenanceStartTime time.Time, st *Stats) error {
-	var (
-		used sync.Map
+	var unused, inUse, system, tooRecent, undeleted stats.CountSum
 
-		unused, inUse, system, tooRecent, undeleted stats.CountSum
-	)
+	used, serr := bigmap.NewSet(ctx)
+	if serr != nil {
+		return errors.Wrap(serr, "unable to create new set")
+	}
+	defer used.Close(ctx)
 
-	if err := findInUseContentIDs(ctx, rep, &used); err != nil {
+	if err := findInUseContentIDs(ctx, rep, used); err != nil {
 		return errors.Wrap(err, "unable to find in-use content ID")
 	}
 
@@ -113,7 +121,9 @@ func runInternal(ctx context.Context, rep repo.DirectRepositoryWriter, gcDelete
 			return nil
 		}
 
-		if _, ok := used.Load(ci.GetContentID()); ok {
+		var cidbuf [128]byte
+
+		if used.Contains(ci.GetContentID().Append(cidbuf[:0])) {
 			if ci.GetDeleted() {
 				if err := rep.ContentManager().UndeleteContent(ctx, ci.GetContentID()); err != nil {
 					return errors.Wrapf(err, "Could not undelete referenced content: %v", ci)


Test patch:
diff --git a/internal/bigmap/bigmap_internal_test.go b/internal/bigmap/bigmap_internal_test.go
new file mode 100644
index 00000000..6c3b868a
--- /dev/null
+++ b/internal/bigmap/bigmap_internal_test.go
@@ -0,0 +1,290 @@
+package bigmap
+
+import (
+	"bytes"
+	"crypto/sha256"
+	"encoding/binary"
+	"hash"
+	"sync"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/kopia/kopia/internal/testlogging"
+)
+
+func TestInternalMap(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	impl, err := newInternalMap(ctx)
+	require.NoError(t, err)
+
+	defer impl.Close(ctx)
+
+	key1 := []byte("key1")
+	key2 := []byte("longerkey2")
+	val1 := []byte("val1")
+	val2 := []byte("val2")
+
+	v, ok := impl.Get(nil, key1)
+	require.Nil(t, v)
+	require.False(t, ok)
+
+	impl.PutIfAbsent(ctx, key1, val1)
+
+	v, ok = impl.Get(nil, key1)
+	require.True(t, ok)
+	require.Equal(t, val1, v)
+
+	v, ok = impl.Get(nil, key2)
+	require.Nil(t, v)
+	require.False(t, ok)
+
+	impl.PutIfAbsent(ctx, key2, val2)
+
+	v, ok = impl.Get(nil, key2)
+	require.True(t, ok)
+	require.Equal(t, val2, v)
+
+	v, ok = impl.Get(nil, key1)
+	require.True(t, ok)
+	require.Equal(t, val1, v)
+}
+
+func TestGrowingMap(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	impl, err := newInternalMapWithOptions(ctx, true, &Options{
+		InitialSizeLogarithm: 9,
+		NumMemorySegments:    3,
+		MemorySegmentSize:    1000,
+		FileSegmentSize:      4 << 20,
+	})
+	require.NoError(t, err)
+
+	defer impl.Close(ctx)
+
+	h := sha256.New()
+
+	// insert 20K hashes
+	for i := 0; i < 20000; i++ {
+		var keybuf, valbuf, valbuf2 [sha256.Size]byte
+
+		k := sha256Key(h, keybuf[:0], i)
+		v := sha256Key(h, valbuf[:0], i+3)
+
+		require.True(t, impl.PutIfAbsent(ctx, k, v))
+
+		// ensure that previously written key is still there.
+		pkindex := i / 2
+		pk := sha256Key(h, keybuf[:0], pkindex)
+		require.True(t, impl.Contains(pk))
+
+		pv, ok := impl.Get(valbuf2[:0], pk)
+		require.True(t, ok)
+		require.Equal(t, pv, sha256Key(h, valbuf[:0], pkindex+3))
+
+		// ensure that key not written yet is not there.
+		nk := sha256Key(h, keybuf[:0], i+1)
+
+		require.False(t, impl.Contains(nk))
+
+		_, ok2 := impl.Get(valbuf2[:0], nk)
+		require.False(t, ok2)
+	}
+}
+
+func TestGrowingSet(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	impl, err := NewSetWithOptions(ctx, &Options{
+		InitialSizeLogarithm: 9,
+		NumMemorySegments:    3,
+		MemorySegmentSize:    1000,
+		FileSegmentSize:      4 << 20,
+	})
+	require.NoError(t, err)
+
+	defer impl.Close(ctx)
+
+	h := sha256.New()
+
+	// insert 20K hashes
+	for i := 0; i < 20000; i++ {
+		var keybuf [sha256.Size]byte
+
+		k := sha256Key(h, keybuf[:0], i)
+
+		require.True(t, impl.Put(ctx, k))
+		require.False(t, impl.Put(ctx, k))
+
+		// ensure that previously written key is still there.
+		pkindex := i / 2
+		pk := sha256Key(h, keybuf[:0], pkindex)
+		require.True(t, impl.Contains(pk))
+
+		// ensure that key not written yet is not there.
+		nk := sha256Key(h, keybuf[:0], i+1)
+
+		require.False(t, impl.Contains(nk))
+	}
+}
+
+func sha256Key(h hash.Hash, out []byte, i int) []byte {
+	var num [8]byte
+
+	// generate key=sha256(i) without allocations.
+	h.Reset()
+	binary.LittleEndian.PutUint64(num[:], uint64(i))
+	h.Write(num[:])
+
+	s := h.Sum(out)
+
+	return s
+}
+
+func BenchmarkInternalMap_NoValue(b *testing.B) {
+	ctx := testlogging.Context(b)
+	m, err := newInternalMapWithOptions(ctx, false, nil)
+	require.NoError(b, err)
+
+	defer m.Close(ctx)
+
+	benchmarkInternalMap(b, m, []byte{})
+}
+
+func BenchmarkInternalMap_WithValue(b *testing.B) {
+	ctx := testlogging.Context(b)
+	m, err := newInternalMap(ctx)
+	require.NoError(b, err)
+
+	defer m.Close(ctx)
+
+	benchmarkInternalMap(b, m, []byte{1, 2, 3})
+}
+
+//nolint:thelper
+func benchmarkInternalMap(b *testing.B, m *internalMap, someVal []byte) {
+	ctx := testlogging.Context(b)
+
+	b.ResetTimer()
+
+	var (
+		h      = sha256.New()
+		num    [8]byte
+		keyBuf [sha256.Size]byte
+	)
+
+	for i := 0; i < b.N; i++ {
+		// generate key=sha256(i) without allocations.
+		h.Reset()
+		binary.LittleEndian.PutUint64(num[:], uint64(i))
+		h.Write(num[:])
+		key := h.Sum(keyBuf[:0])
+
+		m.PutIfAbsent(ctx, key, someVal)
+	}
+
+	valBuf := make([]byte, 10)
+
+	for j := 0; j < 4; j++ {
+		for i := 0; i < b.N; i++ {
+			// generate key=sha256(i) without allocations.
+			h.Reset()
+			binary.LittleEndian.PutUint64(num[:], uint64(i))
+			h.Write(num[:])
+			key := h.Sum(keyBuf[:0])
+
+			_, ok := m.Get(valBuf[:0], key)
+			require.True(b, ok)
+		}
+	}
+}
+
+func BenchmarkSyncMap_NoValue(b *testing.B) {
+	benchmarkSyncMap(b, []byte{})
+}
+
+func BenchmarkSyncMap_WithValue(b *testing.B) {
+	someVal := []byte{1, 2, 3}
+
+	benchmarkSyncMap(b, someVal)
+}
+
+//nolint:thelper
+func benchmarkSyncMap(b *testing.B, someVal []byte) {
+	var m sync.Map
+
+	var (
+		h      = sha256.New()
+		num    [8]byte
+		keyBuf [sha256.Size]byte
+	)
+
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		// generate key=sha256(i) without allocations.
+		h.Reset()
+		binary.LittleEndian.PutUint64(num[:], uint64(i))
+		h.Write(num[:])
+		key := h.Sum(keyBuf[:0])
+
+		m.Store(string(key), append([]byte{}, someVal...))
+	}
+
+	for j := 0; j < 4; j++ {
+		for i := 0; i < b.N; i++ {
+			// generate key=sha256(i) without allocations.
+			h.Reset()
+			binary.LittleEndian.PutUint64(num[:], uint64(i))
+			h.Write(num[:])
+			key := h.Sum(keyBuf[:0])
+
+			val, ok := m.Load(string(key))
+			require.True(b, ok)
+			require.Equal(b, someVal, val)
+		}
+	}
+}
+
+func TestErrors(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	_, err := newInternalMapWithOptions(ctx, true, &Options{
+		InitialSizeLogarithm: 8,
+	})
+
+	require.ErrorContains(t, err, "invalid initial size")
+}
+
+func TestPanics(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	m, err := NewSet(ctx)
+	require.NoError(t, err)
+
+	// too short keys
+	require.Panics(t, func() { m.Put(ctx, nil) })
+	require.Panics(t, func() { m.Put(ctx, []byte{1}) })
+
+	// too long key
+	require.Panics(t, func() { m.Put(ctx, bytes.Repeat([]byte{1}, 256)) })
+}
+
+func TestMapWithoutValue(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	// this is a corner case, it's possible to create a map that can only support zero-length values.
+	m, err := newInternalMapWithOptions(ctx, false, nil)
+	require.NoError(t, err)
+
+	key := []byte{1, 2, 3, 4}
+	m.PutIfAbsent(ctx, key, nil)
+
+	require.Panics(t, func() { m.PutIfAbsent(ctx, key, []byte{3, 4, 5}) })
+
+	v, ok := m.Get(nil, key)
+	require.True(t, ok)
+	require.Nil(t, v)
+}
diff --git a/internal/bigmap/bigmap_map_test.go b/internal/bigmap/bigmap_map_test.go
new file mode 100644
index 00000000..b72d7bd5
--- /dev/null
+++ b/internal/bigmap/bigmap_map_test.go
@@ -0,0 +1,130 @@
+package bigmap_test
+
+import (
+	"crypto/sha256"
+	"encoding/binary"
+	"hash"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/kopia/kopia/internal/bigmap"
+	"github.com/kopia/kopia/internal/testlogging"
+)
+
+func TestGrowingMap(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	impl, err := bigmap.NewMapWithOptions(ctx, &bigmap.Options{
+		InitialSizeLogarithm: 9,
+		NumMemorySegments:    3,
+		MemorySegmentSize:    1000,
+		FileSegmentSize:      4 << 20,
+	})
+	require.NoError(t, err)
+
+	defer impl.Close(ctx)
+
+	h := sha256.New()
+
+	// insert 20K hashes
+	for i := 0; i < 20000; i++ {
+		var keybuf, valbuf, valbuf2 [sha256.Size]byte
+
+		k := sha256Key(h, keybuf[:0], i)
+		v := sha256Key(h, valbuf[:0], i+3)
+
+		require.True(t, impl.PutIfAbsent(ctx, k, v))
+
+		// ensure that previously written key is still there.
+		pkindex := i / 2
+		pk := sha256Key(h, keybuf[:0], pkindex)
+		require.True(t, impl.Contains(pk))
+
+		pv, ok, err := impl.Get(ctx, valbuf2[:0], pk)
+		require.NoError(t, err)
+		require.True(t, ok)
+		require.Equal(t, pv, sha256Key(h, valbuf[:0], pkindex+3))
+
+		// ensure that key not written yet is not there.
+		nk := sha256Key(h, keybuf[:0], i+1)
+
+		require.False(t, impl.Contains(nk))
+
+		_, ok2, err := impl.Get(ctx, valbuf2[:0], nk)
+		require.NoError(t, err)
+		require.False(t, ok2)
+	}
+}
+
+func sha256Key(h hash.Hash, out []byte, i int) []byte {
+	var num [8]byte
+
+	// generate key=sha256(i) without allocations.
+	h.Reset()
+	binary.LittleEndian.PutUint64(num[:], uint64(i))
+	h.Write(num[:])
+
+	s := h.Sum(out)
+
+	return s
+}
+
+func BenchmarkMap_NoValue(b *testing.B) {
+	ctx := testlogging.Context(b)
+	m, err := bigmap.NewMapWithOptions(ctx, nil)
+	require.NoError(b, err)
+
+	defer m.Close(ctx)
+
+	benchmarkMap(b, m, []byte{})
+}
+
+func BenchmarkMap_WithValue(b *testing.B) {
+	ctx := testlogging.Context(b)
+	m, err := bigmap.NewMap(ctx)
+	require.NoError(b, err)
+
+	defer m.Close(ctx)
+
+	benchmarkMap(b, m, []byte{1, 2, 3})
+}
+
+//nolint:thelper
+func benchmarkMap(b *testing.B, m *bigmap.Map, someVal []byte) {
+	ctx := testlogging.Context(b)
+
+	b.ResetTimer()
+
+	var (
+		h      = sha256.New()
+		num    [8]byte
+		keyBuf [sha256.Size]byte
+	)
+
+	for i := 0; i < b.N; i++ {
+		// generate key=sha256(i) without allocations.
+		h.Reset()
+		binary.LittleEndian.PutUint64(num[:], uint64(i))
+		h.Write(num[:])
+		key := h.Sum(keyBuf[:0])
+
+		m.PutIfAbsent(ctx, key, someVal)
+	}
+
+	valBuf := make([]byte, 10)
+
+	for j := 0; j < 4; j++ {
+		for i := 0; i < b.N; i++ {
+			// generate key=sha256(i) without allocations.
+			h.Reset()
+			binary.LittleEndian.PutUint64(num[:], uint64(i))
+			h.Write(num[:])
+			key := h.Sum(keyBuf[:0])
+
+			_, ok, err := m.Get(ctx, valBuf[:0], key)
+			require.NoError(b, err)
+			require.True(b, ok)
+		}
+	}
+}
diff --git a/internal/bigmap/bigmap_set_test.go b/internal/bigmap/bigmap_set_test.go
new file mode 100644
index 00000000..12bada23
--- /dev/null
+++ b/internal/bigmap/bigmap_set_test.go
@@ -0,0 +1,101 @@
+package bigmap_test
+
+import (
+	"bytes"
+	"crypto/sha256"
+	"encoding/binary"
+	"testing"
+
+	"github.com/stretchr/testify/require"
+
+	"github.com/kopia/kopia/internal/bigmap"
+	"github.com/kopia/kopia/internal/testlogging"
+)
+
+func TestGrowingSet(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	impl, err := bigmap.NewSetWithOptions(ctx, &bigmap.Options{
+		InitialSizeLogarithm: 9,
+		NumMemorySegments:    3,
+		MemorySegmentSize:    1000,
+		FileSegmentSize:      4 << 20,
+	})
+	require.NoError(t, err)
+
+	defer impl.Close(ctx)
+
+	h := sha256.New()
+
+	// insert 20K hashes
+	for i := 0; i < 20000; i++ {
+		var keybuf [sha256.Size]byte
+
+		k := sha256Key(h, keybuf[:0], i)
+
+		require.True(t, impl.Put(ctx, k))
+		require.False(t, impl.Put(ctx, k))
+
+		// ensure that previously written key is still there.
+		pkindex := i / 2
+		pk := sha256Key(h, keybuf[:0], pkindex)
+		require.True(t, impl.Contains(pk))
+
+		// ensure that key not written yet is not there.
+		nk := sha256Key(h, keybuf[:0], i+1)
+
+		require.False(t, impl.Contains(nk))
+	}
+}
+
+func BenchmarkSet(b *testing.B) {
+	ctx := testlogging.Context(b)
+	m, err := bigmap.NewSet(ctx)
+	require.NoError(b, err)
+
+	defer m.Close(ctx)
+
+	b.ResetTimer()
+
+	var (
+		h      = sha256.New()
+		num    [8]byte
+		keyBuf [sha256.Size]byte
+	)
+
+	for i := 0; i < b.N; i++ {
+		// generate key=sha256(i) without allocations.
+		h.Reset()
+		binary.LittleEndian.PutUint64(num[:], uint64(i))
+		h.Write(num[:])
+		key := h.Sum(keyBuf[:0])
+
+		m.Put(ctx, key)
+	}
+
+	for j := 0; j < 4; j++ {
+		for i := 0; i < b.N; i++ {
+			// generate key=sha256(i) without allocations.
+			h.Reset()
+			binary.LittleEndian.PutUint64(num[:], uint64(i))
+			h.Write(num[:])
+			key := h.Sum(keyBuf[:0])
+
+			require.True(b, m.Contains(key))
+		}
+	}
+}
+
+func TestSetPanics(t *testing.T) {
+	ctx := testlogging.Context(t)
+
+	m, err := bigmap.NewSet(ctx)
+	require.NoError(t, err)
+
+	// too short keys
+	require.Panics(t, func() { m.Put(ctx, nil) })
+	require.Panics(t, func() { m.Put(ctx, []byte{1}) })
+
+	// too long key
+	require.Panics(t, func() { m.Put(ctx, bytes.Repeat([]byte{1}, 256)) })
+}
diff --git a/internal/testutil/testutil.go b/internal/testutil/testutil.go
index 6fe3d5b9..60961ed4 100644
--- a/internal/testutil/testutil.go
+++ b/internal/testutil/testutil.go
@@ -75,7 +75,7 @@ func ShouldReduceTestComplexity() bool {
 		return true
 	}
 
-	return strings.Contains(runtime.GOARCH, "arm")
+	return strings.Contains(runtime.GOARCH, "arm") && runtime.GOOS != "darwin"
 }
 
 // ShouldSkipUnicodeFilenames returns true if:
diff --git a/repo/content/index/id_test.go b/repo/content/index/id_test.go
index ee55ba79..ebcdb66c 100644
--- a/repo/content/index/id_test.go
+++ b/repo/content/index/id_test.go
@@ -2,6 +2,7 @@
 
 import (
 	"encoding/json"
+	"fmt"
 	"testing"
 
 	"github.com/stretchr/testify/require"
@@ -122,6 +123,8 @@ func TestIDHash(t *testing.T) {
 			require.NoError(t, err)
 			require.Equal(t, h, cid.Hash())
 
+			require.Equal(t, fmt.Sprintf("%v%x", prefix, h), string(cid.Append(nil)))
+
 			require.Equal(t, prefix != "", cid.HasPrefix())
 			require.Equal(t, prefix, cid.Prefix())
 		}
diff --git a/repo/object/objectid_test.go b/repo/object/objectid_test.go
index 29dd916c..61560b62 100644
--- a/repo/object/objectid_test.go
+++ b/repo/object/objectid_test.go
@@ -67,6 +67,21 @@ func TestToStrings(t *testing.T) {
 	require.Equal(t, []string{"f0f0", "f1f1"}, strs)
 }
 
+func TestString(t *testing.T) {
+	cases := map[ID]string{
+		EmptyID:                  "",
+		mustParseID(t, "Dabcd"):  "abcd",
+		mustParseID(t, "abcd"):   "abcd",
+		mustParseID(t, "IIabcd"): "IIabcd",
+		mustParseID(t, "Zabcd"):  "Zabcd",
+	}
+
+	for id, str := range cases {
+		require.Equal(t, str, id.String())
+		require.Equal(t, str, string(id.Append(nil)))
+	}
+}
+
 func mustParseID(t *testing.T, s string) ID {
 	t.Helper()
 
diff --git a/snapshot/snapshotfs/snapshot_tree_walker_test.go b/snapshot/snapshotfs/snapshot_tree_walker_test.go
index 3d40b689..4f9a8529 100644
--- a/snapshot/snapshotfs/snapshot_tree_walker_test.go
+++ b/snapshot/snapshotfs/snapshot_tree_walker_test.go
@@ -19,16 +19,19 @@
 func TestSnapshotTreeWalker(t *testing.T) {
 	callbackCounter := new(int32)
 
-	w := snapshotfs.NewTreeWalker(
+	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+
+	w, err := snapshotfs.NewTreeWalker(
+		ctx,
 		snapshotfs.TreeWalkerOptions{
 			EntryCallback: func(ctx context.Context, entry fs.Entry, oid object.ID, entryPath string) error {
 				atomic.AddInt32(callbackCounter, 1)
 				return nil
 			},
 		})
-	defer w.Close()
+	require.NoError(t, err)
 
-	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+	defer w.Close(ctx)
 
 	sourceRoot := mockfs.NewDirectory()
 	require.Error(t, w.Process(ctx, sourceRoot, "."))
@@ -79,7 +82,10 @@ func TestSnapshotTreeWalker(t *testing.T) {
 func TestSnapshotTreeWalker_Errors(t *testing.T) {
 	someErr1 := errors.Errorf("some error")
 
-	w := snapshotfs.NewTreeWalker(
+	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+
+	w, err := snapshotfs.NewTreeWalker(
+		ctx,
 		snapshotfs.TreeWalkerOptions{
 			Parallelism: 1,
 			EntryCallback: func(ctx context.Context, entry fs.Entry, oid object.ID, entryPath string) error {
@@ -90,9 +96,9 @@ func TestSnapshotTreeWalker_Errors(t *testing.T) {
 				return nil
 			},
 		})
-	defer w.Close()
+	require.NoError(t, err)
 
-	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+	defer w.Close(ctx)
 
 	sourceRoot := mockfs.NewDirectory()
 	require.Error(t, w.Process(ctx, sourceRoot, "root-dir"))
@@ -118,7 +124,10 @@ func TestSnapshotTreeWalker_Errors(t *testing.T) {
 func TestSnapshotTreeWalker_MultipleErrors(t *testing.T) {
 	someErr1 := errors.Errorf("some error")
 
-	w := snapshotfs.NewTreeWalker(
+	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+
+	w, err := snapshotfs.NewTreeWalker(
+		ctx,
 		snapshotfs.TreeWalkerOptions{
 			Parallelism: 1,
 			MaxErrors:   -1,
@@ -134,9 +143,9 @@ func TestSnapshotTreeWalker_MultipleErrors(t *testing.T) {
 				return nil
 			},
 		})
-	defer w.Close()
+	require.NoError(t, err)
 
-	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+	defer w.Close(ctx)
 
 	sourceRoot := mockfs.NewDirectory()
 	require.Error(t, w.Process(ctx, sourceRoot, "root-dir"))
@@ -165,7 +174,10 @@ func TestSnapshotTreeWalker_MultipleErrors(t *testing.T) {
 func TestSnapshotTreeWalker_MultipleErrorsSameOID(t *testing.T) {
 	someErr1 := errors.Errorf("some error")
 
-	w := snapshotfs.NewTreeWalker(
+	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+
+	w, err := snapshotfs.NewTreeWalker(
+		ctx,
 		snapshotfs.TreeWalkerOptions{
 			Parallelism: 1,
 			MaxErrors:   -1,
@@ -181,9 +193,9 @@ func TestSnapshotTreeWalker_MultipleErrorsSameOID(t *testing.T) {
 				return nil
 			},
 		})
-	defer w.Close()
+	require.NoError(t, err)
 
-	ctx, env := repotesting.NewEnvironment(t, repotesting.FormatNotImportant)
+	defer w.Close(ctx)
 
 	sourceRoot := mockfs.NewDirectory()
 	require.Error(t, w.Process(ctx, sourceRoot, "root-dir"))
diff --git a/snapshot/snapshotfs/upload_test.go b/snapshot/snapshotfs/upload_test.go
index 5fb82244..740835d9 100644
--- a/snapshot/snapshotfs/upload_test.go
+++ b/snapshot/snapshotfs/upload_test.go
@@ -909,14 +909,14 @@ func TestUpload_VirtualDirectoryWithStreamingFileWithModTime(t *testing.T) {
 			require.Equal(t, int32(1), atomic.LoadInt32(&man1.Stats.TotalDirectoryCount))
 			require.Equal(t, int32(1), atomic.LoadInt32(&man1.Stats.TotalFileCount))
 
+			// wait a little bit to ensure clock moves forward which is not always the case on Windows.
+			time.Sleep(100 * time.Millisecond)
+
 			// Rebuild tree because reader only works once.
 			staticRoot = virtualfs.NewStaticDirectory("rootdir", []fs.Entry{
 				tc.getFile(),
 			})
 
-			// wait a little bit to ensure clock moves forward which is not always the case on Windows.
-			time.Sleep(100 * time.Millisecond)
-
 			// Second upload may find some cached files depending on timestamps.
 			man2, err := u.Upload(ctx, staticRoot, policyTree, snapshot.SourceInfo{}, man1)
 			require.NoError(t, err)