package main

// Where the disk space goes. A few times a day (every 6 hours, jittered, postponed while the
// machine is busy) the background worker walks each real filesystem once (bind mounts of the same
// device are walked once), adding up the space files actually take (allocated blocks, so sparse
// files count for what they use), without following symbolic links and without crossing into
// other mounts. It keeps the size of directories up to 6 levels deep and of files of 16 MiB or
// more, and reports:
//   - the biggest directories, drilling down into the big branches (/var → /var/lib →
//     /var/lib/docker → …), and the ones that grew most since the previous scan;
//   - the largest files and the fastest-growing ones, with a kind (log, db, backup, cache, docker).
// Only paths and sizes leave the machine, never file contents. The walk is paced by the worker's
// gentle mode (slices of ~2 ms, then a pause) and has hard budgets: 20 s of work, 3 million
// entries, 45 minutes; when one is hit the result is marked partial (sizes are then lower bounds).
// `disable: [disk_scan]` switches it off.

import (
	"os"
	"path/filepath"
	"sort"
	"strings"
	"time"
)

const (
	scanRecordDepth = 6       // directories recorded up to this depth below the mount point
	scanMaxDepth    = 64      // deeper directories are not entered
	scanDirMin      = 1 << 20 // directories smaller than this are not recorded
	scanFileMin     = 16 << 20
	scanMaxDirs     = 20000
	scanMaxFiles    = 5000
)

type ScanMount struct {
	Mount   string `json:"mount"`
	FS      string `json:"fs"`
	Used    uint64 `json:"used"`    // statfs
	Scanned int64  `json:"scanned"` // what the walk added up
}

type ScanDir struct {
	Path  string `json:"path"`
	Bytes int64  `json:"bytes"`
	Files int64  `json:"files"`
	Delta *int64 `json:"delta"` // since the previous scan; null when not measured then
}

type ScanFile struct {
	Path  string `json:"path"`
	Bytes int64  `json:"bytes"`
	Delta *int64 `json:"delta"`
	Kind  string `json:"kind"`
}

type DiskScanOut struct {
	At      int64       `json:"at"`
	PrevAt  *int64      `json:"prev_at"`
	TookS   int64       `json:"took_s"`
	WorkMs  int64       `json:"work_ms"`
	Entries int64       `json:"entries"`
	Partial bool        `json:"partial"`
	Mounts  []ScanMount `json:"mounts"`
	Dirs    []ScanDir   `json:"dirs"`
	Files   []ScanFile  `json:"files"`
}

type dirStat struct {
	bytes, files int64
	depth        int
}

// scanAcc is the state of one walk, shared by the platform walkers.
type scanAcc struct {
	g        *Gentle
	dirs     map[string]dirStat
	files    map[string]int64
	fileMin  int64
	entries  int64
	maxEnt   int64
	maxWork  time.Duration
	deadline time.Time
	stopped  bool
	bufs     [][]byte
}

// tick counts an entry and paces the walk; it returns false once a budget is used up.
func (a *scanAcc) tick() bool {
	if a.stopped {
		return false
	}
	a.entries++
	if a.entries >= a.maxEnt {
		a.stopped = true
		return false
	}
	if a.entries&63 == 0 {
		a.g.Tick()
		if a.g.Work() > a.maxWork || time.Now().After(a.deadline) {
			a.stopped = true
			return false
		}
	}
	return true
}

func (a *scanAcc) dir(path string, depth int, bytes, files int64) {
	if depth > scanRecordDepth || bytes < scanDirMin {
		return
	}
	if len(a.dirs) >= scanMaxDirs && depth > 2 {
		return
	}
	a.dirs[path] = dirStat{bytes: bytes, files: files, depth: depth}
}

func (a *scanAcc) file(path string, size int64) {
	if size < a.fileMin {
		return
	}
	a.files[path] = size
	if len(a.files) >= 2*scanMaxFiles { // keep the larger half, raise the bar
		sizes := make([]int64, 0, len(a.files))
		for _, s := range a.files {
			sizes = append(sizes, s)
		}
		sort.Slice(sizes, func(i, j int) bool { return sizes[i] > sizes[j] })
		a.fileMin = sizes[scanMaxFiles-1]
		for p, s := range a.files {
			if s < a.fileMin {
				delete(a.files, p)
			}
		}
	}
}

// buf returns the directory-listing buffer of one depth (each level keeps its own while the walk
// is below it).
func (a *scanAcc) buf(depth int) []byte {
	for len(a.bufs) <= depth {
		a.bufs = append(a.bufs, nil)
	}
	if a.bufs[depth] == nil {
		a.bufs[depth] = make([]byte, 8192)
	}
	return a.bufs[depth]
}

func joinPath(dir, name string) string {
	if strings.HasSuffix(dir, "/") {
		return dir + name
	}
	return dir + "/" + name
}

// DiskScanner keeps the previous scan to report what grew.
type DiskScanner struct {
	prevDirs   map[string]int64
	prevFiles  map[string]int64
	prevAt     int64
	MaxEntries int64
	MaxWork    time.Duration
	MaxWall    time.Duration
}

func NewDiskScanner() *DiskScanner {
	return &DiskScanner{MaxEntries: 3_000_000, MaxWork: 20 * time.Second, MaxWall: 45 * time.Minute}
}

// Scan walks the mounts (real filesystems, as the disk list has them) and builds the report.
func (d *DiskScanner) Scan(mounts []Mount, statfs func(string) (DiskUsage, error), g *Gentle, now time.Time) *DiskScanOut {
	start := time.Now()
	if g == nil {
		g = &Gentle{}
	}
	g.Begin()
	acc := &scanAcc{g: g, dirs: map[string]dirStat{}, files: map[string]int64{}, fileMin: scanFileMin, maxEnt: d.MaxEntries,
		maxWork: d.MaxWork, deadline: start.Add(d.MaxWall)}
	out := &DiskScanOut{At: now.Unix(), Mounts: []ScanMount{}, Dirs: []ScanDir{}, Files: []ScanFile{}}
	// One walk per device: bind mounts of an already walked device are skipped (shortest path first).
	ms := append([]Mount(nil), mounts...)
	sort.Slice(ms, func(i, j int) bool { return len(ms[i].Point) < len(ms[j].Point) })
	seenDev := map[uint64]bool{}
	var scanned []ScanMount
	for _, m := range ms {
		if acc.stopped || len(scanned) >= 16 {
			break
		}
		dev, ok := devOf(m.Point)
		if !ok || seenDev[dev] {
			continue
		}
		if fi, err := os.Stat(m.Point); err != nil || !fi.IsDir() { // a bind-mounted file (/etc/hosts in a container)
			continue
		}
		seenDev[dev] = true
		bytes, files := walkTree(m.Point, dev, acc)
		acc.dirs[m.Point] = dirStat{bytes: bytes, files: files, depth: 0}
		sm := ScanMount{Mount: m.Point, FS: m.FSType, Scanned: bytes}
		if du, err := statfs(m.Point); err == nil {
			sm.Used = du.Used
		}
		scanned = append(scanned, sm)
	}
	out.Mounts = scanned
	out.Entries = acc.entries
	out.Partial = acc.stopped
	out.WorkMs = g.Work().Milliseconds()
	out.TookS = int64(time.Since(start).Seconds())
	if d.prevAt > 0 && !out.Partial {
		p := d.prevAt
		out.PrevAt = &p
	}
	if out.Partial { // sizes are lower bounds: no growth is computed from them, and they are not kept as the reference
		saved, savedF := d.prevDirs, d.prevFiles
		d.prevDirs, d.prevFiles = nil, nil
		out.Dirs = d.pickDirs(acc.dirs, scanned)
		out.Files = d.pickFiles(acc.files)
		d.prevDirs, d.prevFiles = saved, savedF
		return out
	}
	out.Dirs = d.pickDirs(acc.dirs, scanned)
	out.Files = d.pickFiles(acc.files)
	nd := make(map[string]int64, len(acc.dirs))
	for p, s := range acc.dirs {
		nd[p] = s.bytes
	}
	d.prevDirs, d.prevFiles, d.prevAt = nd, acc.files, now.Unix()
	return out
}

func (d *DiskScanner) delta(prev map[string]int64, path string, now int64) *int64 {
	if prev == nil {
		return nil
	}
	p, ok := prev[path]
	if !ok {
		return nil
	}
	v := now - p
	return &v
}

// pickDirs: the mount points, then their big children drilled down (at most 8 per parent, each at
// least 64 MiB and either 2% of the mount or a quarter of its parent), then the growers.
func (d *DiskScanner) pickDirs(dirs map[string]dirStat, mounts []ScanMount) []ScanDir {
	kids := map[string][]string{}
	for p := range dirs {
		par := filepath.Dir(p)
		if par != p {
			kids[par] = append(kids[par], p)
		}
	}
	sel := map[string]bool{}
	var order []string
	add := func(p string) {
		if !sel[p] && len(order) < 60 {
			sel[p] = true
			order = append(order, p)
		}
	}
	type item struct {
		path  string
		total int64
	}
	var queue []item
	for _, m := range mounts {
		add(m.Mount)
		queue = append(queue, item{m.Mount, m.Scanned})
	}
	for len(queue) > 0 && len(order) < 45 {
		it := queue[0]
		queue = queue[1:]
		ch := kids[it.path]
		sort.Slice(ch, func(i, j int) bool { return dirs[ch[i]].bytes > dirs[ch[j]].bytes })
		parent := dirs[it.path].bytes
		for i, c := range ch {
			b := dirs[c].bytes
			if i >= 8 || b < 64<<20 || (b*50 < it.total && b*4 < parent) {
				break
			}
			add(c)
			queue = append(queue, item{c, it.total})
		}
	}
	// growers since the previous scan
	type grow struct {
		path  string
		delta int64
	}
	var gs []grow
	for p, s := range dirs {
		if prev, ok := d.prevDirs[p]; ok && s.bytes-prev >= 32<<20 {
			gs = append(gs, grow{p, s.bytes - prev})
		}
	}
	sort.Slice(gs, func(i, j int) bool { return gs[i].delta > gs[j].delta })
	for i, g := range gs {
		if i >= 15 {
			break
		}
		add(g.path)
	}
	out := make([]ScanDir, 0, len(order))
	for _, p := range order {
		s := dirs[p]
		out = append(out, ScanDir{Path: truncate(p, 300), Bytes: s.bytes, Files: s.files, Delta: d.delta(d.prevDirs, p, s.bytes)})
	}
	return out
}

// pickFiles: the 15 largest and the 15 fastest-growing (by at least 16 MiB) files.
func (d *DiskScanner) pickFiles(files map[string]int64) []ScanFile {
	type f struct {
		path  string
		size  int64
		delta int64
	}
	all := make([]f, 0, len(files))
	for p, s := range files {
		x := f{path: p, size: s}
		if prev, ok := d.prevFiles[p]; ok {
			x.delta = s - prev
		} else if d.prevFiles != nil {
			x.delta = s // new since the previous scan (or just crossed 16 MiB)
		}
		all = append(all, x)
	}
	sel := map[string]bool{}
	var out []ScanFile
	add := func(x f) {
		if sel[x.path] {
			return
		}
		sel[x.path] = true
		out = append(out, ScanFile{Path: truncate(x.path, 300), Bytes: x.size, Delta: d.delta(d.prevFiles, x.path, x.size), Kind: FileKind(x.path)})
	}
	sort.Slice(all, func(i, j int) bool { return all[i].size > all[j].size })
	for i := 0; i < len(all) && i < 15; i++ {
		add(all[i])
	}
	sort.Slice(all, func(i, j int) bool { return all[i].delta > all[j].delta })
	for i := 0; i < len(all) && i < 15 && all[i].delta >= 16<<20; i++ {
		add(all[i])
	}
	if out == nil {
		out = []ScanFile{}
	}
	return out
}

// FileKind classifies a big file by its path.
func FileKind(p string) string {
	lp := strings.ToLower(p)
	base := filepath.Base(lp)
	has := func(xs ...string) bool {
		for _, x := range xs {
			if strings.Contains(lp, x) {
				return true
			}
		}
		return false
	}
	suffix := func(xs ...string) bool {
		for _, x := range xs {
			if strings.HasSuffix(base, x) {
				return true
			}
		}
		return false
	}
	switch {
	case strings.HasSuffix(base, "-json.log") || strings.HasPrefix(lp, "/var/log/") || suffix(".log", ".journal", ".journal~") ||
		strings.Contains(base, ".log.") || has("/log/", "/logs/"):
		return "log"
	case has("/var/lib/docker/", "/var/lib/containerd/", "/var/lib/containers/"):
		return "docker"
	case has("/var/lib/mysql/", "/var/lib/postgresql/", "/var/lib/pgsql/", "/var/lib/mongodb/", "/var/lib/redis/", "/var/lib/clickhouse/",
		"/var/lib/elasticsearch/", "/var/lib/influxdb/") || suffix(".sqlite", ".sqlite3", ".db", ".ibd", ".rdb", ".aof", ".mdb", ".wal") ||
		strings.HasPrefix(base, "ibdata") || strings.HasPrefix(base, "binlog.") || strings.HasPrefix(base, "mysql-bin."):
		return "db"
	case suffix(".bak", ".backup", ".tar", ".tar.gz", ".tgz", ".tar.zst", ".tar.xz", ".zip", ".7z", ".rar", ".sql", ".sql.gz", ".dump", ".gz", ".xz", ".zst", ".img", ".iso") ||
		has("backup", "/bak/", "snapshot"):
		return "backup"
	case has("/.cache/", "/var/cache/", "/tmp/", "/var/tmp/", "/cache/"):
		return "cache"
	}
	return "other"
}
