© Sasun Bughdaryan / 123RF.com

Um speicherfressende Dateien auf der Festplatte aufzustöbern, schreibt Mike Schilli eine kleine Terminal-UI in Go.

Beim Einbau einer neuen Festplatte wähnen sich User im siebten Himmel – es scheint schier unmöglich, die Disk jemals vollzuschreiben. Angesichts gigantischer Kapazitäten entwickelt sich allerdings jeder früher oder später zum gedankenlosen Platzverschwender. Die Platte füllt sich zusehends, und es gilt, Platz zu schaffen, um den Weiterbetrieb zu gewährleisten. Meist verursachen längst nicht mehr genutzte Riesendateien, die in vergessenen Verzeichnissen herumlungern, die drangvolle Enge. Am effektivsten ist oft die simple Strategie, die größten Verschwender aufzustöbern und die entsprechenden Dateileichen zu löschen.

Das Go-Programm dieser Ausgabe hilft bei diesem Hausputz, indem es ausgehend von einem Wurzelverzeichnis die speicherintensivsten Pfade samt dem dort jeweils verbratenen Plattenplatz in Bytes angibt. Wie Abbildung 1 zeigt, schaltet das mit dem zu analysierenden Verzeichnis aufgerufene Go-Binary das Terminal in den Grafikmodus und stellt die Speicherpfade als interaktiven Baum dar. Dessen grüne Elemente lassen sich per Tastendruck oder Mausklick weiter auffächern, um festzustellen, in welchen Ordnern die dicksten Brummer liegen.

Abbildung 1: UI mit speicherintensiven Git-Verzeichnissen.

Dickste Brummer

Im vorliegenden Fall nahm sich das Go-Binary »spacetree« das Verzeichnis »~/git/« zur Brust und fand heraus, dass darunter etwa 14 GByte an Daten liegen. Mit den Pfeiltasten, deren Vi-Entsprechungen [J]+ und [K] oder auch per Mausklick lassen sich die grün unterlegten Verzeichnisse anfahren und durch einen Druck auf die Eingabetaste auffächern. In Abbildung 2 stellt sich so heraus, dass zum Beispiel das Verzeichnis »articles/«, in dem die Artikel aus 26 Jahren dieser Kolumne liegen, insgesamt fast 4 GByte belegt.

Abbildung 2: Aufgefächerte Verzeichnisse zeigen die dicksten Brummer.

Das meiste, etwa 850 MByte, liegt im Git-internen Verzeichnis ».git«, der verschwenderischste Artikel ist der Netzwerkprüfer »wifi« aus der August-Ausgabe 2023 – allerdings nur, weil noch das zugehörige Snapshot-Video darin liegt. Weg damit, und schon wieder sind 850 MByte gespart! Der Artikel zum Fortschrittsbalken vom Dezember 2018 enthält die Dateileichen »foo« und »foo.bak«, die weggeputzt gehören.

Schlauer mit Heap

Wie durchwandert das Go-Programm die tief verschachtelte Dateistruktur, um die Bytes jeder einzelnen Datei zu zählen und eine kurze Liste der größten Dateien auszugeben? Gesucht werden die umfangreichsten zehn Exemplare aus einer riesigen Zahl von Dateien, die schnell bis in die Millionen gehen kann. Da verbietet sich die einfache Lösung, alle Einträge in ein Array abzulegen, es absteigend nach Dateigröße zu sortieren und anschließend die ersten zehn Einträge auszugeben. Selbst ein effektiver Sortieralgorithmus braucht für eine Million Einträge seine Zeit, ganz zu schweigen vom RAM, das so ein riesiges Array verschwendet, von dem am Ende nur zehn Einträge interessieren.

Als effiziente Datenstruktur für derartige Probleme erweist sich der sogenannte Min-Heap. Die Knoten dieses Binärbaums genügen immer der Vorschrift, dass die Exemplare unterhalb eines bestimmten Knotens immer größere Werte aufweisen als der Knoten selbst. So steht in Abbildung 3 oben an der Wurzel des Baums der Node mit dem Wert 3, der kleiner als alle anderen Werte des Baums ist. Die Vorschrift gilt übrigens nur für direkt oder indirekt miteinander verbundene Knoten. Daher ist es durchaus zulässig, dass zum Beispiel in Abbildung 3 in der zweiten Reihe von oben der Wert 8 steht, aber in der dritten Reihe des rechten Teilbaums der Wert 7.

Abbildung 3: Die Datenstruktur Min-Heap und ihre Array-Repräsentation.

Minimaler Haufen

Programme stellen den Baum als simples Array dar, das, wie in Abbildung 3 gezeigt, für die Reihen des Baums jeweils Bereiche mit ein, zwei, vier, acht, … Einträgen anlegt, die nahtlos aneinandergrenzen. Es fällt nun relativ leicht, den kleinsten Eintrag im Baum zu finden und zu entfernen, denn er befindet sich stets oben an der Wurzel. Anschließend sortiert man den Baum so um, dass ein anderer Knoten den Platz des entfernten einnimmt. Dann rücken die folgenden Nodes auf, auf dass der Baum wieder den alten Knotenregeln genüge. Das lässt sich relativ einfach mit einem standardisierten Algorithmus bewerkstelligen.

Damit eignet sich die Datenstruktur ideal für eine aktiv aktualisierte Liste der N größten bislang gefundenen Dateien: Enthält der Baum anfangs noch weniger als N Knoten, wandern alle neu gefundenen Dateien ungeprüft hinein. Wächst der Baum beim Einfügen einer neuen Datei hingegen auf N+1 Knoten an, muss er wieder auf N Knoten schrumpfen. Das klappt am besten, indem der Algorithmus den Wurzelknoten mit der kleinsten Datei entfernt und die restlichen Knoten nachrücken lässt.

Abbildung 3 zeigt die Ausgabe des Testprogramms aus Listing 1. Es schreibt erst den Heap mit den Pfaden zu acht Dateien und deren Größe in Bytes voll. Dabei begrenzt es aber die Maximalgröße des Heaps auf sechs Einträge. Heraus kommen am Ende die sechs größten Dateien aus dem Gesamtkorpus, und zwar absteigend sortiert nach Dateigröße. Die Einträge »abc« und »ghi« mit den Byte-Zählern 123 und 124 bleiben als kleinste Dateien erwartungsgemäß außen vor.

Abbildung 4: Ausgabe des Testprogramms für den Min-Heap.

Listing 1 legt dazu mit »NewTopN()« in Zeile 16 einen Min-Heap mit maximal sechs Knoten an. Die For-Schleife ab Zeile 17 wirft mit »Add()« jeweils den nächsten Eintrag aus dem Array-Slice »entries« auf den Min-Heap. Abschließend arbeitet sich »Iterate()« ab Zeile 20 durch die Gewinner-Einträge in der Datenstruktur, und zwar von der Datei mit dem höchsten Byte-Zähler bis zur kleinsten der Top Sechs.

package main
import (
  "fmt"
)
func main() {
  entries := []FsEntry{
    {path: "abc", used: 123},
    {path: "def", used: 456},
    {path: "ghi", used: 124},
    {path: "jkl", used: 457},
    {path: "mno", used: 125},
    {path: "pqr", used: 458},
    {path: "stu", used: 126},
    {path: "vwx", used: 999},
  }
  h := NewTopN(6)
  for _, e := range entries {
    h.Add(e)
  }
  h.Iterate(func(e FsEntry) {
    fmt.Printf("%s %d\n", e.path, e.used)
  })
}

Baum als Hitparade

Listing 2 zeigt die Implementierung der Top-N-Liste mittels eines Min-Heaps aus der Go-Standard-Bibliothek »container/heap«. Die Struktur vom Typ »FsEntry« ab Zeile 5 repräsentiert jeweils eine Datei samt Zugriffspfad und Größe in Bytes. Die Struktur »topN« ab Zeile 9 enthält im Feld »entries« einen ganzen Array-Slice von »FsEntry«-Strukturen sowie im Feld »n« die Maximalgröße des verwendeten Heaps.

package main
import (
  "container/heap"
)
type FsEntry struct {
  path string
  used int64
}
type topN struct {
  entries []FsEntry
  n       int
}
func NewTopN(n int) *topN {
  h := &topN{n: n, entries: []FsEntry{}}
  heap.Init(h)
  return h
}
func (h *topN) Add(fse FsEntry) {
  heap.Push(h, fse)
  if h.Len() > h.n {
    heap.Pop(h)
  }
}
func (h *topN) Iterate(cb func(fse FsEntry)) {
  save := make([]FsEntry, len(h.entries))
  copy(save, h.entries)
  r := make([]FsEntry, h.Len())
  for i := len(r) - 1; i >= 0; i-- {
    r[i] = heap.Pop(h).(FsEntry)
  }
  for _, e := range r {
    cb(e)
  }
  h.entries = save
}
func (h topN) Len() int {
  return len(h.entries)
}
func (h topN) Less(i, j int) bool {
  return h.entries[i].used < h.entries[j].used
}
func (h topN) Swap(i, j int) {
  h.entries[i], h.entries[j] = h.entries[j], h.entries[i]
}
func (h *topN) Push(x interface{}) {
  h.entries = append(h.entries, x.(FsEntry))
}
func (h *topN) Pop() interface{} {
  old := h.entries
  n := len(old)
  x := old[n-1]
  h.entries = old[:n-1]
  return x
}

Der Konstruktor »NewTopN« ab Zeile 13 legt die in der Go-Objektorientierung übliche Instanz einer Struktur als Objekt an und ruft die Heap-Initialisierung »heap.Init()« aus der Standardbibliothek auf. Dann gibt er einen Zeiger auf die Struktur an den Aufrufer zurück, der diesen für zukünftige Aufrufe als Verweis auf die Objektinstanz nutzt.

Die Funktion »Add()« ab Zeile 18 nimmt eine Variable vom Typ »FsEntry« mit dem Pfad zu einer Datei und deren Größe entgegen und wirft sie auf den Min-Heap. Dazu nutzt sie die Funktion »heap.Push()« aus der Standardbibliothek »container/heap«, prüft aber anschließend mittels »Len()«, ob diese Aktion den Heap nicht über die zulässige Länge hinaus vergrößert hat. Ist dies der Fall, korrigiert »heap.Pop()« in Zeile 21 das Malheur, indem es den Eintrag an der Wurzel des Baums – also die kleinste Datei – entfernt und verwirft.

Um die Einträge im Heap zu durchwandern, baut »Iterate()« ab Zeile 24 mit sukzessiven Aufrufen von »heap.Pop()« den Heap ab. Dabei fängt es mit dem kleinsten Element an der Wurzel des Baums an und arbeitet sich dann weiter zum jeweils nächstgrößeren vor. Die Ausgabe soll jedoch umgekehrt erfolgen, also beginnend mit der größten Datei und endend mit der kleinsten. Daher legt die For-Schleife ab Zeile 28 die hereinkommenden Werte rückwärts in einem neu angelegten Array »r« ab. Das durchschreitet die For-Schleife ab Zeile 31 anschließend vorwärts und ruft für jeden gefundenen Knoten die vom Aufrufer hereingereichte Callback-Funktion »cb()« auf.

Dort kann dann der Aufrufer definieren, was mit dem Ergebnis geschieht. Im Fall des Testprogramms gibt die Funktion einfach die Kombination aus Pfad und verbrauchtem Speicherplatz aus. Da »heap.Pop()« den Heap sukzessive abbaut und damit zerstört, sichert »Iterate()« die interne Datenstruktur vorab, um sie am Ende wieder herzustellen. Dazu kopiert sie den Array-Slice »entries« mittels der Go-internen Funktion »copy()« in ein weiteres Array und restauriert das Heap-Objekt abschließend damit. So bleibt es für später folgende Aufrufe intakt.

Programmierte Magie

Aufmerksame Leser wundern sich nun, wie es denn kommt, dass die benutzerdefinierte Struktur vom Typ »topN« auf einmal in Aufrufen wie »heap.Init()« als Parameter auftaucht, ohne dass Go mit seinem strengen Typsystem sich über den Fremdkörper beschwert. Woher weiß die Standard-Library »container/heap«, dass sich der im Heap verwendete Array-Slice im Feld »entries« befindet oder wie sich die Elemente vom Typ »FsEntry« absteigend nach Dateigröße sortieren lassen?

Des Rätsels Lösung: Der Typ »topN« definiert ab Zeile 36 in Listing 2 die Funktionen »Len()«, »Push()«, »Pop()«, »Less()« und »Swap()« und genügt damit dem Interface von »container/heap«. So kann die Standard-Library die Länge des Heaps bestimmen, Elemente ans Ende des internen Arrays einhängen oder dessen letztes Element entfernen.

»Less()« ab Zeile 39 bestimmt, welches von zwei Elemente das größere ist, und »Swap()« gibt an, wie der Algorithmus zur Wartung des Heaps zwei Elemente vertauscht. Mit diesem Werkzeugkasten kann eine Funktion wie »heap.Pop()« (nicht zu verwechseln mit »Pop()« aus Listing 1, Zeile 48) dann später den Knoten an der Wurzel des Baums entfernen, ihn zurückgeben und den Baum wieder in Form bringen. Programmierte Magie!

Auf Tauchgang

Mit diesem Rüstzeug geht nun Listing 3 daran, das vom User auf der Kommandozeile angegebene Verzeichnis rekursiv zu durchforsten. Es addiert die verbrauchte Byte-Anzahl der in den Untiefen der Hierarchie liegenden Dateien zu einer Gesamtsumme auf und legt für jedes direkte Unterverzeichnis einen Min-Heap mit den fünf gierigsten Speicherfressern an.

Dazu steigt die Standardfunktion »Walk()« aus der Go-Bibliothek »filepath« in einer Depth-First-Suche (Abbildung 5) hinab in die Verzeichnisstruktur der Festplatte und ruft für jeden gefundenen Eintrag den ab Zeile 14 definierten Callback auf. Der ignoriert aufgestöberte Unterverzeichnisse (ab Zeile 18). Er bestimmt lediglich bei Dateien (oder Links) ab Zeile 21 deren relativen Pfad zum Einstiegsverzeichnis sowie das oberste Unterverzeichnis (»topDir«). Unter diesem Schlüssel erzeugt der Code jeweils einen Eintrag in der Hash-Map »duTotal«, der die bislang aufsummierten Bytes und einen neuen Min-Hash zum Verfolgen der dicksten Dateien speichert.

Abbildung 5: Die Depth-First-Methode der Baumdurchquerung.

Harte Links

Ganz präzise arbeitet diese einfache Version des Byte-Zählers übrigens nicht: Zusätzliche Hardlinks – also weitere Inodes, die auf bereits bestehende Dateien zeigen – zählt sie doppelt. Mit etwas Aufwand lässt sich das allerdings korrigieren. Der Erbsenzähler muss dazu eine riesige Tabelle anlegen und zu jeder bereits gesehenen Datei die Festplattennummer und deren Inode ablegen. Trifft er anschließend auf einen Eintrag, der dieselben Werte hat, handelt es sich um einen Hardlink, der nur einmal gezählt werden sollte.

Der Aufruf von »Add()« des Min-Heaps in Zeile 35 registriert den aktuell gefundenen Eintrag. Der wird nur dann nicht sofort verworfen, wenn er aufgrund seiner Größe noch in die Top Fünf passt. Insgesamt erhält der Aufrufer von »duDir()« zwei Resultate: zum einen die Gesamtzahl der unter dem analysierten Verzeichnis verbratenen Bytes, zum anderen eine Hash-Tabelle »duTotal«. Letztere weist die obersten Verzeichnisse der Hierarchie ihren Min-Heaps zu. Der Parameter steht als Pointer in der Aufrufliste und dient damit gleichzeitig als Rückgabewert.

package main
import (
  "os"
  "path/filepath"
  "strings"
)
type duEntry struct {
  h    *topN
  used int64
}
func duDir(dir string, duTotal *map[string]duEntry) (int64, error) {
  total := int64(0)
  err := filepath.Walk(dir,
    func(fpath string, info os.FileInfo, err error) error {
      if err != nil {
        return err
      }
      if info.IsDir() {
        return nil
      }
      fpath, _ = filepath.Rel(dir, fpath)
      parts := strings.Split(fpath, "/")
      fileName := strings.TrimPrefix(fpath, parts[0]+"/")
      topPath := parts[0]
      // find or create new path mapping
      var due duEntry
      var ok bool
      if due, ok = (*duTotal)[topPath]; !ok {
        due = duEntry{}
        due.h = NewTopN(5)
      }
      // add file to dir's heap
      fse := FsEntry{path: fileName, used: info.Size()}
      fse.used = info.Size()
      due.h.Add(fse)
      due.used += info.Size()
      (*duTotal)[topPath] = due
      total += info.Size()
      return nil
    })
  return total, err
}

Zum Hauptgang

Das Hauptprogramm in Listing 4 prüft als Erstes, ob der User ihm auf der Kommandozeile auch ein Verzeichnis zur Analyse mitgegeben hat, und beschwert sich anderenfalls. Mit einer anfangs leeren Map »duTotal«, die den obersten Verzeichnissen jeweils Zähler vom Typ »duEntry« zuweist, ruft es dann »duDir()« aus Listing 3 auf. Das durchstöbert die Festplatte und reicht die Ergebnisse durch. Liegen anschließend mehr als zehn Top-Verzeichnisse vor, filtert der Min-Hash ab Zeile 19 die dicksten zehn heraus. Die bringt die Sortierfunktion ab Zeile 30 in alphabetische Reihenfolge, bevor der Aufruf von »ui()« in Zeile 33 das Ganze zur Anzeige an die Terminal-UI weiterreicht.

package main
import (
  "fmt"
  "os"
  "sort"
  "strings"
)
func main() {
  if len(os.Args) != 2 {
    fmt.Printf("usage: %s dir\n", os.Args[0])
    os.Exit(1)
  }
  topDir := os.Args[1]
  duTotal := map[string]duEntry{}
  bytes, err := duDir(topDir, &duTotal)
  if err != nil {
    panic(err)
  }
  topn := NewTopN(10)
  for dir, due := range duTotal {
    if strings.Count(dir, "/") > 1 {
      continue
    }
   topn.Add(FsEntry{path: dir, used: due.used})
  }
  lines := []FsEntry{}
  topn.Iterate(func(e FsEntry) {
    lines = append(lines, e)
  })
  sort.Slice(lines, func(i, j int) bool {
    return lines[i].path < lines[j].path
  })
  ui(topDir, bytes, lines, duTotal)
}

Ins Terminal zeichnen

Zur grafischen Anzeige der bislang gesammelten Daten schreitet dann Listing 5 mit dem schon im letzten Snapshot verwendeten Framework »tview« zur Darstellung im Grafik-Modus des Terminals.

package main
import (
  "fmt"
  "github.com/gdamore/tcell/v2"
  "github.com/rivo/tview"
  "golang.org/x/text/language"
  "golang.org/x/text/message"
)
func ui(rootDir string, bytes int64, dirs []FsEntry, duTotal map[string]duEntry) {
  root := tview.NewTreeNode(fmt.Sprintf("%s %s", rootDir, commify(bytes))).
    SetColor(tcell.ColorRed)
  tree := tview.NewTreeView().
    SetRoot(root).
    SetCurrentNode(root)
  for _, dir := range dirs {
    node := tview.NewTreeNode(fmt.Sprintf("%s %s", dir.path, commify(dir.used))).
      SetExpanded(false).
      SetSelectable(false)
    // new dir
    root.AddChild(node)
    node.SetSelectable(true)
    node.SetColor(tcell.ColorGreen)
    dut, ok := duTotal[dir.path]
    if !ok {
      panic(fmt.Sprintf("Can't find %s", dir.path))
    }
    // add sub-menu
    h := dut.h
    h.Iterate(func(fse FsEntry) {
      line := fmt.Sprintf("%s %s", fse.path, commify(fse.used))
      n := tview.NewTreeNode(line).
        SetExpanded(false).
        SetSelectable(false)
      node.AddChild(n)
    })
  }
  tree.SetSelectedFunc(func(node *tview.TreeNode) {
    node.SetExpanded(!node.IsExpanded())
  })
  err := tview.NewApplication().SetRoot(tree, true).EnableMouse(true).Run()
  if err != nil {
    panic(err)
  }
}
func commify(i int64) string {
  p := message.NewPrinter(language.English)
  return p.Sprintf("%d", i)
}

Beim obersten Eintrag im dargestellten Baum handelt es sich um das dem Programm mitgegebene Startverzeichnis, zusammen mit der Gesamtzahl der dort verbrauchten Bytes. Zeile 10 definiert den Eintrag und färbt ihn rot. Der Baum selbst liegt in der Variablen »tree« ab Zeile 12. Der Code hängt erst den Root-Knoten ein und dann weiter unten in der For-Schleife ab Zeile 15 die Top-Verzeichnisse, die darunterliegen.

Jeder dieser Einträge gelangt via »AddChild()« als Ast in den Baum und wird mit »SetSelectable()« auswählbar gemacht. Der User drückt hierzu entweder die Eingabetaste oder klickt mit der Maus darauf. Was auf dieses Ereignis hin passiert, definiert der Aufruf der Funktion »SetSelectedFunc()« weiter unten in Zeile 37. Deren Callback »SetExpanded()« setzt das Attribut entweder auf wahr oder falsch, je nachdem, ob der Eintrag schon aufgefächert vorliegt.

Um die dargestellten Zahlenwerte besser lesbar zu machen, fügt die ab Zeile 45 definierte Funktion »commify()« Kommas in die Integer-Werte ein und macht so beispielsweise aus 123456789 das einfacher lesbare 123,456,789. Das erfolgt mittels der Standard-Libraries »language« und »message« aus »golang.org/x/text/language/«, deren Funktion »NewPrinter()« diese im englischsprachigen Raum übliche Darstellung vornimmt.

Zeile 40 fügt das vorher definierte Tree-Objekt in das von »tview« kontrollierte Terminalfenster ein und schaltet das Terminal in den Grafikmodus. »Run()« startet die Event-Schleife, die User-Eingaben abfängt und die Anzeige entsprechend eingehender Ereignisse auffrischt. Am Ende unterbricht die Tastenkombination [Strg]+[C] den Reigen, schaltet das Terminal zurück in den normalen Textmodus und lässt die Shell wieder zum Zug kommen.

$ go mod init duview
$ go mod tidy
$ go build duview.go space.go ui.go heap.go

Schlussverkauf

Der Dreisatz aus Listing 6 erzeugt aus den vier Quelldateien das Programm »duview«. Ruft man es mit einem zu analysierenden Verzeichnis auf, kommt abhängig von Füllstatus, Größe und Performance der Festplatte nach einigen Sekunden das Ergebnis auf den Schirm. Auf geht es zum Schlussverkauf, alles Alte muss raus! (uba/jlu)