Repository: restic/restic (go)

Issue:
Information command
It would be nice, to have a `restic info` command.

Currently there is no way to see the number of snapshots and the size of the repo (and much more info) with one command.

I would open a PR implementing this, if somebody could guide me in the right direction. 

Pull request description:
stats: Add `debug` mode to collect repository statistics
<!--
Thank you very much for contributing code or documentation to restic! Please
fill out the following questions to make it easier for us to review your
changes.
-->

What does this PR change? What problem does it solve?
-----------------------------------------------------
`restic stats --mode debug` now prints statistics about the size of the individual blob / files types in a repository. The idea is to help with debugging issues related to unexpectedly high memory / cache usage.

So far the command is not shown in the help output of the stats command, as I'm not sure what use cases besides debugging would be.

Sample output:
```
Collecting size statistics

File Type: key
Count: 1
Total Size: 451 B
Size            Count
---------------------
100 - 999 Byte  1
---------------------

File Type: lock
Count: 2
Total Size: 302 B
Size            Count
---------------------
100 - 999 Byte  2
---------------------

File Type: index
Count: 106
Total Size: 230.657 MiB
Size                    Count
-----------------------------
    10000 - 99999 Byte  8
  100000 - 999999 Byte  3
1000000 - 9999999 Byte  95
-----------------------------

File Type: data
Count: 15428
Total Size: 246.514 GiB
Size                      Count
-------------------------------
      10000 - 99999 Byte  1
    100000 - 999999 Byte  16
  1000000 - 9999999 Byte  286
10000000 - 99999999 Byte  15125
-------------------------------

Blob Type: data
Count: 3753205
Total Size: 241.391 GiB
Size                    Count
-------------------------------
          10 - 99 Byte  46443
        100 - 999 Byte  1129200
      1000 - 9999 Byte  1569321
    10000 - 99999 Byte  628942
  100000 - 999999 Byte  311586
1000000 - 9999999 Byte  67713
-------------------------------


Blob Type: tree
Count: 1313735
Total Size: 1.178 GiB
Size                    Count
-------------------------------
          10 - 99 Byte  1
        100 - 999 Byte  1127061
      1000 - 9999 Byte  173620
    10000 - 99999 Byte  12481
  100000 - 999999 Byte  570
1000000 - 9999999 Byte  2
-------------------------------
```
<!--
Describe the changes and their purpose here, as detailed as needed.
-->

Was the change previously discussed in an issue or on the forum?
----------------------------------------------------------------
Alternative to #2543 
Fixes #1047

<!--
Link issues and relevant forum posts here.

If this PR resolves an issue on GitHub, use "Closes #1234" so that the issue
is closed automatically when this PR is merged.
-->

Checklist
---------

<!--
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. Enable a checkbox by replacing [ ] with [x].
-->

- [x] I have read the [contribution guidelines](https://github.com/restic/restic/blob/master/CONTRIBUTING.md#providing-patches).
- [x] I have [enabled maintainer edits](https://help.github.com/en/github/collaborating-with-issues-and-pull-requests/allowing-changes-to-a-pull-request-branch-created-from-a-fork).
- [ ] I have added tests for all code changes.
- [x] I have added documentation for relevant changes (in the manual).
- [ ] There's a new file in `changelog/unreleased/` that describes the changes for our users (see [template](https://github.com/restic/restic/blob/master/changelog/TEMPLATE)).
- [x] I have run `gofmt` on the code in all commits.
- [x] All commit messages are formatted in the same style as [the other commits in the repo](https://github.com/restic/restic/blob/master/CONTRIBUTING.md#git-commits).
- [x] I'm done! This pull request is ready for review.


Patch:
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index e0f2e2c08..39a829337 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -68,6 +68,9 @@ it might be necessary to manually clean up stale lock files using
 On Windows, please set the environment variable `RESTIC_DEBUG_STACKTRACE_SIGINT`
 to `true` and press `Ctrl-C` to create a stacktrace.
 
+If you think restic uses too much memory or a too large cache directory, then
+please include the output of `restic stats --mode debug`.
+
 
 Development Environment
 =======================
diff --git a/cmd/restic/cmd_stats.go b/cmd/restic/cmd_stats.go
index 7032bdef8..a7ecd438f 100644
--- a/cmd/restic/cmd_stats.go
+++ b/cmd/restic/cmd_stats.go
@@ -5,11 +5,15 @@ import (
 	"encoding/json"
 	"fmt"
 	"path/filepath"
+	"strings"
 
+	"github.com/restic/chunker"
 	"github.com/restic/restic/internal/backend"
 	"github.com/restic/restic/internal/crypto"
+	"github.com/restic/restic/internal/repository"
 	"github.com/restic/restic/internal/restic"
 	"github.com/restic/restic/internal/ui"
+	"github.com/restic/restic/internal/ui/table"
 	"github.com/restic/restic/internal/walker"
 
 	"github.com/minio/sha256-simd"
@@ -99,6 +103,10 @@ func runStats(ctx context.Context, opts StatsOptions, gopts GlobalOptions, args
 		return err
 	}
 
+	if opts.countMode == countModeDebug {
+		return statsDebug(ctx, repo)
+	}
+
 	if !gopts.JSON {
 		Printf("scanning...\n")
 	}
@@ -291,6 +299,7 @@ func verifyStatsInput(opts StatsOptions) error {
 	case countModeUniqueFilesByContents:
 	case countModeBlobsPerFile:
 	case countModeRawData:
+	case countModeDebug:
 	default:
 		return fmt.Errorf("unknown counting mode: %s (use the -h flag to get a list of supported modes)", opts.countMode)
 	}
@@ -335,4 +344,149 @@ const (
 	countModeUniqueFilesByContents = "files-by-contents"
 	countModeBlobsPerFile          = "blobs-per-file"
 	countModeRawData               = "raw-data"
+	countModeDebug                 = "debug"
 )
+
+func statsDebug(ctx context.Context, repo restic.Repository) error {
+	Warnf("Collecting size statistics\n\n")
+	for _, t := range []restic.FileType{restic.KeyFile, restic.LockFile, restic.IndexFile, restic.PackFile} {
+		hist, err := statsDebugFileType(ctx, repo, t)
+		if err != nil {
+			return err
+		}
+		Warnf("File Type: %v\n%v\n", t, hist)
+	}
+
+	hist := statsDebugBlobs(ctx, repo)
+	for _, t := range []restic.BlobType{restic.DataBlob, restic.TreeBlob} {
+		Warnf("Blob Type: %v\n%v\n\n", t, hist[t])
+	}
+
+	return nil
+}
+
+func statsDebugFileType(ctx context.Context, repo restic.Repository, tpe restic.FileType) (*sizeHistogram, error) {
+	hist := newSizeHistogram(2 * repository.MaxPackSize)
+	err := repo.List(ctx, tpe, func(id restic.ID, size int64) error {
+		hist.Add(uint64(size))
+		return nil
+	})
+
+	return hist, err
+}
+
+func statsDebugBlobs(ctx context.Context, repo restic.Repository) [restic.NumBlobTypes]*sizeHistogram {
+	var hist [restic.NumBlobTypes]*sizeHistogram
+	for i := 0; i < len(hist); i++ {
+		hist[i] = newSizeHistogram(2 * chunker.MaxSize)
+	}
+
+	repo.Index().Each(ctx, func(pb restic.PackedBlob) {
+		hist[pb.Type].Add(uint64(pb.Length))
+	})
+
+	return hist
+}
+
+type sizeClass struct {
+	lower, upper uint64
+	count        int64
+}
+
+type sizeHistogram struct {
+	count     int64
+	totalSize uint64
+	buckets   []sizeClass
+	oversized []uint64
+}
+
+func newSizeHistogram(sizeLimit uint64) *sizeHistogram {
+	h := &sizeHistogram{}
+	h.buckets = append(h.buckets, sizeClass{0, 0, 0})
+
+	lowerBound := uint64(1)
+	growthFactor := uint64(10)
+
+	for lowerBound < sizeLimit {
+		upperBound := lowerBound*growthFactor - 1
+		if upperBound > sizeLimit {
+			upperBound = sizeLimit
+		}
+		h.buckets = append(h.buckets, sizeClass{lowerBound, upperBound, 0})
+		lowerBound *= growthFactor
+	}
+
+	return h
+}
+
+func (s *sizeHistogram) Add(size uint64) {
+	s.count++
+	s.totalSize += size
+
+	for i, bucket := range s.buckets {
+		if size >= bucket.lower && size <= bucket.upper {
+			s.buckets[i].count++
+			return
+		}
+	}
+
+	s.oversized = append(s.oversized, size)
+}
+
+func (s sizeHistogram) String() string {
+	var out strings.Builder
+
+	out.WriteString(fmt.Sprintf("Count: %d\n", s.count))
+	out.WriteString(fmt.Sprintf("Total Size: %s\n", ui.FormatBytes(s.totalSize)))
+
+	t := table.New()
+	t.AddColumn("Size", "{{.SizeRange}}")
+	t.AddColumn("Count", "{{.Count}}")
+	type line struct {
+		SizeRange string
+		Count     int64
+	}
+
+	// only print up to the highest used bucket size
+	lastFilledIdx := 0
+	for i := 0; i < len(s.buckets); i++ {
+		if s.buckets[i].count != 0 {
+			lastFilledIdx = i
+		}
+	}
+
+	var lines []line
+	hasStarted := false
+	for i, b := range s.buckets {
+		if i > lastFilledIdx {
+			break
+		}
+
+		if b.count > 0 {
+			hasStarted = true
+		}
+		if hasStarted {
+			lines = append(lines, line{
+				SizeRange: fmt.Sprintf("%d - %d Byte", b.lower, b.upper),
+				Count:     b.count,
+			})
+		}
+	}
+	longestRange := 0
+	for _, l := range lines {
+		if longestRange < len(l.SizeRange) {
+			longestRange = len(l.SizeRange)
+		}
+	}
+	for i := range lines {
+		lines[i].SizeRange = strings.Repeat(" ", longestRange-len(lines[i].SizeRange)) + lines[i].SizeRange
+		t.AddRow(lines[i])
+	}
+
+	_ = t.Write(&out)
+
+	if len(s.oversized) > 0 {
+		out.WriteString(fmt.Sprintf("Oversized: %v\n", s.oversized))
+	}
+	return out.String()
+}


Test patch:
diff --git a/cmd/restic/cmd_stats_test.go b/cmd/restic/cmd_stats_test.go
new file mode 100644
index 000000000..02d37acd9
--- /dev/null
+++ b/cmd/restic/cmd_stats_test.go
@@ -0,0 +1,62 @@
+package main
+
+import (
+	"testing"
+
+	rtest "github.com/restic/restic/internal/test"
+)
+
+func TestSizeHistogramNew(t *testing.T) {
+	h := newSizeHistogram(42)
+
+	exp := &sizeHistogram{
+		count:     0,
+		totalSize: 0,
+		buckets: []sizeClass{
+			{0, 0, 0},
+			{1, 9, 0},
+			{10, 42, 0},
+		},
+	}
+
+	rtest.Equals(t, exp, h)
+}
+
+func TestSizeHistogramAdd(t *testing.T) {
+	h := newSizeHistogram(42)
+	for i := uint64(0); i < 45; i++ {
+		h.Add(i)
+	}
+
+	exp := &sizeHistogram{
+		count:     45,
+		totalSize: 990,
+		buckets: []sizeClass{
+			{0, 0, 1},
+			{1, 9, 9},
+			{10, 42, 33},
+		},
+		oversized: []uint64{43, 44},
+	}
+
+	rtest.Equals(t, exp, h)
+}
+
+func TestSizeHistogramString(t *testing.T) {
+	t.Run("overflow", func(t *testing.T) {
+		h := newSizeHistogram(42)
+		h.Add(8)
+		h.Add(50)
+
+		rtest.Equals(t, "Count: 2\nTotal Size: 58 B\nSize        Count\n-----------------\n1 - 9 Byte  1\n-----------------\nOversized: [50]\n", h.String())
+	})
+
+	t.Run("withZero", func(t *testing.T) {
+		h := newSizeHistogram(42)
+		h.Add(0)
+		h.Add(1)
+		h.Add(10)
+
+		rtest.Equals(t, "Count: 3\nTotal Size: 11 B\nSize          Count\n-------------------\n  0 - 0 Byte  1\n  1 - 9 Byte  1\n10 - 42 Byte  1\n-------------------\n", h.String())
+	})
+}