Adventskalender 20. Dezember 2023 - unlink

[Meillo]

Im heutigen Tuerchen geht es um die Eigenheiten des Loeschens von Dateien in Unix. Die Betrachtung ist auf Dateisystem- und Kernel-Ebene. Konkret geht es um den Aufbau des Dateisystems, den Systemcall unlink(2) und das was warum im Kernel so passiert.

Erster Kontakt

Bevor ich mit Unix in Kontakt gekommen bin, habe ich schon mit PHP programmiert. Dort war ich ziemlich irritiert, dass es dort keine delete()-Funktion gibt, sondern, dass sie unlink() heisst. Da ich mit dieser Irritation nicht alleine bin, gibt es heute in der PHP-Dokumenation einen Eintrag fuer delete(), der diesen Text enthaelt:

There is no delete keyword or function in the PHP language. If you arrived at this page seeking to delete a file, try unlink().

Erst als ich Unix und dessen Dateisystem kennengelernt habe, konnte ich die sonderbare Benennung verstehen. Viele Funktionen in PHP sind von Unix und C inspiriert.

Systemcalls

Will man in Unix Dateien loeschen, so muss man dafuer den Systemcall unlink() aufrufen. Systemcalls sind die Funktionen, die der Betriebssstemkern bereitstellt. Der Betriebssystemkern/Kernel verwaltet die Ressourcen/Hardware des Computers. Ein Programm kann rechnen was es will, aber wenn es auf das Dateisystem zugreifen will, oder generell jede Art von Input/Output machen will, dann muss es dafuer letztlich Systemcalls nutzen, da diese die einzige Moeglichkeit sind, vom Kernel etwas zu bekommen. Da der Kernel das Dateisystem verwaltet, muss jeder Zugriff und jede Veraenderung des Dateisystems ueber den Kernel und damit ueber Systemcalls laufen. (So sichert der Kernel die Integritaet des Dateisystems.)

Inodes

Im Unix-Dateisystem besteht jede Datei aus zwei Komponenten:

1) einer Inode
2) einer variablen Anzahl von Datenbloecken

D.h. der reine Inhalt einer Datei ist getrennt von ihrer Verwaltungs- und Metainformation. Konkret stehen in der Inode Informationen, wie wem die Datei gehoert, welche Rechte fuer sie gelten, wann sie zuletzt geaendert worden ist, usw. Zudem enthaelt die Inode Verweise zu den Datenbloecken mit dem eigentlichen Dateiinhalt.

Jede Inode hat eine Nummer -- umgangsprachlich meist ebenfalls Inode genannt, die eigentliche Bezeichnung ist aber I-Nummer. (``Inode'' steht fuer ``index node'', also Index-Knoten, und ``i-number'' ist die ``index number''.)

Inodes/I-Nummern anzeigen lassen kann man mit `ls -i' (``print the index number of each file''):

Code: Alles auswählen

:-Q ls -i1 /
   524462 bin/
   524451 boot/
290009897 dev/
   131075 etc/
   131125 home/
     8193 lib/
   131090 lib64/
       11 lost+found/
   525135 media/
   524452 mnt/
   131349 opt/
        1 proc/
   131126 root/
290012438 run/
   393217 sbin/
   525133 srv/
        1 sys/
   131114 tmp/
   393220 usr/
   524289 var/

I-Nummern gelten immer fuer das jeweilige Dateisystem. /dev, /run, /proc und /sys sind hier jeweils eigene Dateisysteme (tmpfs bzw. vom Kernel direkt bereitgestellt), darum kann z.B. die 1 hier doppelt vorkommen. In jedem einzelnen Dateisystem sind sie eindeutig. Wenn es im gleichen Dateisystem die gleiche Inode ist, dann ist es die gleiche Datei.

Verzeichnisse

Was die Inode *nicht* enthaelt, ist der Name der Datei. Dieser findet sich im Verzeichniseintrag. Verzeichnisse in Unix -- und darum heissen sie Verzeichnisse und nicht Ordner -- sind Listen, die Paare von I-Nummern und Dateinamen enthalten. Diese Listen stecken ebenfalls in Dateien, bloss sind diese vom Typ Verzeichnis und koennen nur vom Kernel selbst modifiziert werden. (Der Typ Verzeichnis ist nur ein Kennzeichen in der Inode; Verzeichnisdateien sind sonst technisch genau gleich wie normale Dateien.)

Der Inhalt der Root-Verzeichnis-Datei von obigem Beispiel sieht gewissermassen genau so aus wie die gezeigte Ausgabe: Fuer jede Datei des Verzeichnisses gibt es einen Eintrag (man kann sich vorstellen, dass das eine Zeile waere), bestehend aus der Nummer der Inode und des Namens, unter dem sie in diesem Verzeichnis verknuepft ist.

Links

Da die Verzeichniseintraege (also die Namen) von den Dateien selbst (also Inodes und Dateiinhaltsdatenbloecken) entkoppelt sind, ist es problemlos moeglich, fuer eine Datei/Inode mehrere Links anzulegen, d.h. sie unter mehrere Namen im Dateisystem ansprechbar zu machen. Das geht mittels ln(1), das intern den Systemcall link(2) -- make a new name for a file -- nutzt. (Link und Name sind hier austauschbare Begriffe.)

Hier ein Beispiel:

Code: Alles auswählen

:-Q ls -1i

:-Q touch a

:-Q ls -1i 
160607 a

:-Q ln a b

:-Q ls -1i
160607 a
160607 b

:-Q touch c

:-Q ls -1i 
160607 a
160607 b
161309 c

:-Q cp a d

:-Q ls -1i
160607 a
160607 b
161309 c
161317 d

Wie man sieht, verweisen a und b auf die gleiche Inode, d.h. sie *sind* die gleiche Datei! Die Kopie d dagegen ist eine andere Datei (mit in dem Moment gleichem Inhalt).

(Uebrigens geht es hier um Hardlinks. Softlinks/Symlinks sind technisch etwas anderes und historisch erst viel spaeter eingefuehrt worden.)

unlink(2)

Nun kommen wir zum eigentlich Thema: Der Systemcall unlink().

So wie wir mit link(2) einen weiteren Namen fuer eine (existierende) Datei angelegt haben -- konkret haben wir einfach einen weiteren Verzeichniseintrag gemacht, nichts weiter! -- so koennen wir einen solchen mit unlink(2) auch wieder entfernen.

Dabei bearbeitet der Kernel einfach die Verzeichnisdatei und entfernt den einen Eintrag ... und hier kommt nun der interessante Punkt: Mit dem Loeschen von Daten hat das erstmal gar nicht zu tun! -- Und dies ist der Grund, warum der Systemcall nicht delete() heisst.

Garbage Collection

Wie werden die Daten (also die Inode und die Datenbloecke) aber dann geloescht? Dies erledigt eine Art Garbage-Collection, wie man sie aus Programmiersprachen kennt, bloss ist sie im Unix-Dateisystem einfacher.

In der Inode ist ein Link-Count hinterlegt, also die Anzahl von Links/Namen, die diese Datei hat. Man sieht das in der Ausgabe von `ls -l' schoen bei den Namen a und b, die auf die gleiche Datei verweisen (der Link-Count ist die Zahl zwischen Permissions und Owner):

Code: Alles auswählen

:-Q ls -li
total 0
160607 -rw-r--r-- 2 meillo meillo 0 Dec 19 20:30 a
160607 -rw-r--r-- 2 meillo meillo 0 Dec 19 20:30 b
161309 -rw-r--r-- 1 meillo meillo 0 Dec 19 20:30 c
161317 -rw-r--r-- 1 meillo meillo 0 Dec 19 20:32 d

Bei jedem unlink() verringert der Kernel den Link-Count in der zugehoerigen Inode um 1. Ist er anschliessend auf 0, so war dies der letzte Link. Somit hat die Datei keinen Namen mehr, kann also nicht mehr angesprochen werden, und der Kernel gibt dann Inode und Datenbloecke frei (vereinfacht gesagt).

Zyklen und Baeume

In Programmiersprachen sind Garbage-Collectors viel komplizierter, da dort Objekte wiederum auf andere Objekte verweisen koennen, die wiederum auf andere Objekte ... und eben ggf. auch auf ein voriges Objekt in der Verknuepfungskette verweisen koennen. Dadurch entsteht ein Zyklus. Wenn A auf B verweist und B auf C und C wieder auf A, dann hat jedes Objekt einen Link-Count von 1, aber dieser Zyklus kann dennoch voellig vom Rest separiert und darum nicht mehr adressierbar sein. Darum brauchen Programmiersprachen aufwaendigere Garbage-Collection-Verfahren als nur einen Link-Count.

Dieses Problem kann im Unix Dateisystem nicht auftreten, da Dateien immer Blaetter im Graph sind, d.h. sie koennen nicht mehr auf andere Dateien verweisen. Verweise/Links zu anderen Dateien kann es nur in Verzeichnissen geben. Es muss also sichergestellt sein, dass Verzeichnisse nicht auf andere Verzeichnisse verweisen, die wiederum auf das erste Verzeichnis verweisen und so einen Zyklus erzeugen. Dies wird einfach dadurch verhindert, dass man keine Hardlinks auf Verzeichnisse anlegen kann:

Code: Alles auswählen

:-Q mkdir Z

:-Q ln Z Y
ln: `Z': hard link not allowed for directory

D.h. man kann einem Verzeichnis nicht mehrere Namen geben, wie das fuer normale Dateien geht. Dadurch wird aus dem Verzeichnis-Graph ein Verzeichnis-Baum -- ein Baum ist ein Graph ohne Zyklen.

Der Kernel kann dieses Verbot erzwingen, da alle Veraenderungen im Dateisystem nur ueber das Systemcall-Interface von ihm selbst ausgefuehrt werden.

Dot und Dot-Dot

Nun stimmt es allerdings nicht ganz, dass es keine Hardlinks auf Verzeichnisse gibt, denn warum hat mein Beispielverzeichnis einen Link-Count von 3!?

Code: Alles auswählen

:-Q ls -lid .
205091 drwxr-xr-x 3 meillo meillo 4096 Dec 19 20:54 ./

Auch wenn von Programmen (aus dem Userspace) keine Hardlinks auf Verzeichnisse angelegt werden koennen, so legt der Kernel selbst welche an ... allerdings nur in genau definierter Weise.

In jedem leeren Verzeichnis legt er automatisch zwei Verzeichniseintraege an: `.' und `..'. Das sind stinknormale Verzeichniseintraege, die, weil sie mit einem Punkt beginnen, unsichtbar sind und bei `ls' mit `-a' sichtbar geschaltet werden muessen. Sie unterscheiden sich nur insofern, dass der Kernel sie unter eigener Kontrolle behaelt. Programme koennen sie nicht veraendern.

`.' ist ein Hardlink auf das eigene Verzeichnis und `..' ist ein Hardlink auf das uebergeordnete Verzeichnis. Dies koennen wir leicht anhand der I-Nummern pruefen:

Code: Alles auswählen

 :-Q ls -lia  
total 12
205091 drwxr-xr-x 3 meillo meillo 4096 Dec 19 20:54 ./
131114 drwxrwxrwt 8 root   root   4096 Dec 19 21:02 ../
160607 -rw-r--r-- 2 meillo meillo    0 Dec 19 20:30 a
160607 -rw-r--r-- 2 meillo meillo    0 Dec 19 20:30 b
161309 -rw-r--r-- 1 meillo meillo    0 Dec 19 20:30 c
161317 -rw-r--r-- 1 meillo meillo    0 Dec 19 20:32 d
205092 drwxr-xr-x 2 meillo meillo 4096 Dec 19 20:54 Z/

:-Q ls -lia Z
total 8
205092 drwxr-xr-x 2 meillo meillo 4096 Dec 19 20:54 ./
205091 drwxr-xr-x 3 meillo meillo 4096 Dec 19 20:54 ../

Der Link-Count von 3 meines Arbeitsverzeichnisses kommt von dem `.'-Eintrag im Verzeichnis selbst, vom Namenseintrag im uebergeordneten Verzeichnis -- darum haben alle Verzeichnisse immer mindestens zwei Links --, und dem `..'-Eintrag im Unterverzeichnis Z -- jedes Unterverzeichnis erhoeht also den Link-Count.

Uebrigens hat auch ein leeres Root-Verzeichnis, das ja nicht von einem uebergeordneten Verzeichnis verlinkt ist, einen Link-Count von 2. Das liegt daran, dass im Root-Verzeichnis `..' auch auf das aktuelle Verzeichnis verlinkt.

Das Problem, dass der Verzeichnisbaum kein echter Baum mehr ist, weil er mit `.' und `..' doch Zyklen hat, ist in der Praxis nicht relevant, da diese Zyklen, die ja nur bei den zwei Verzeichniseintraegen `.' und `..' vorkommen, bei einem Baumdurchlauf einfach ignoriert werden koennen. Aber jede Person, die schonmal einen rekursiven Verzeichnisdurchlauf programmiert hat, weiss, dass es dabei immer eine Sonderbehandlung fuer `.' und `..' benoetigt.

Geoeffnete Dateien

Ich hatte geschrieben, dass der Kernel die Inode und die Datenbloecke freigibt, wenn der Link-Count auf 0 faellt. Das stimmt nicht ganz. Falls die Datei noch geoeffnet ist (was der Kernel anhand seiner Open File Table weiss), dann wird die Datei noch nicht geloescht, sondern erst wenn auch der letzte Filedeskriptor geschlossen ist.

Dies ist in der Manpage beschrieben:

unlink() deletes a name from the file system. If that
name was the last link to a file and no processes have
the file open the file is deleted and the space it was
using is made available for reuse.

If the name was the last link to a file but any processes
still have the file open the file will remain in exis‐
tence until the last file descriptor referring to it is
closed.

Da man keine Verzeichniseintraege zu beliebigen Inodes anlegen kann ... sondern nur fuer neue Inodes mit creat(2)/open(2) und zu bereits existierenden mit link(2), kann eine Datei/Inode, deren Link-Count einmal 0 erreicht hat, nicht mehr neu im Dateisystem verlinkt werden. Ihr kommender Tod ist folglich unabaenderlich ... sobald die Prozesse, die sie noch geoeffnet haben, (und ggf. etwaige Kindprozesse) beenden, wird sie geloescht werden. Daran fuehrt kein Weg vorbei.

Abschluss

Wie nun klar wird, ist Loeschen von Dateien in Unix, nichts was direkt verlangt werden kann, sondern nur eine indirekte und ggf. zeitversetzte Folgeaktion von unlink(2) -- dem Entfernen eines Namens der Datei.

Wirklich geloescht wird aber selbst dann nicht. Es kann dann die Daten nur nicht mehr angesprochen werden, weil es keine Verweise mehr zur Inode gibt (von der die Datenbloecke verlinkt sind). Unix vergisst nach dem Entfernen des letzten Verzeichnislinks und des letzten Eintrags der Datei in der Open File Table nur wo sich die Datei befindet ... und damit kann sie nicht mehr abgerufen werden. An Loeschaktion wird nur durchgefuehrt, dass die Datenbloecke der Inode und des Dateiinhalts im Dateisystem in die Free-List eingehaengt werden, wodurch sie als ungenutzt angesehen werden. Die Daten sind zu diesem Zeitpunkt aber weiterhin auf der Festplatte gespeichert ... allerdings nur so lange bis neue Dateien sie dann ueberschreiben.

Loeschen in Unix ist letztlich also Vergessen und Ueberscheiben.


Weiterfuehrendes

All das hier Besprochene kann mit Hilfe des Lions' Books im V6-Sourcecode von Unix nachvollzogen werden. Vielleicht hat ja jemand Lust, das zu tun und die entsprechenden Stellen herauszuarbeiten.
http://www.lemis.com/grog/Documentation/Lions/book.pdf
https://www.tom-yam.or.jp/2238/src/

18.15 Deletion of Files

New files are automatically entered into the filedirectory as permanent files as soon as they are “opened”. Subsequent “closing” of a file does not automatically cause its deletion. As was seen at line 7352, deletion will occur when the field “i_nlink” of the core “inode” entry is zero. This field is set to one initially by “maknode” (7464) when the file is first created. It may be incremented by the system call “link” (5941) and decremented by the system call “unlink” (3529).

Zum Mitdenken

Warum ist das so?

Code: Alles auswählen

:-Q unlink Z
unlink: cannot unlink `Z': Is a directory

Wie loescht man Verzeichnisse? Was sagt das Lions' Book dazu? ... ist das nicht seltsam?

[Livingston]

Danke Meillo, wieder mal schön hinter die Kulissen geschaut.

Bei der Gelegenheit möchte ich kurz noch ergänzen, dass man über Inodes auch "kaputte" Dateinamen zugänglich machen kann:

Code: Alles auswählen

$ touch `echo -ne "\0177"

Der Dateiname besteht aus dem ASCII-Zeichen DEL. Wie soll man da je wieder rankommen?
ls liefert eine "Rettungsanzeige", ls -Nl zeigt behelfsmäßig:

Code: Alles auswählen

...
-rw-r--r--  1 lstone lstone         0 20. Dez 13:06 ?
...

Also ran an die Inodes:
Mit ls -Ni finde ich genau eine Datei mit einem kaputten Dateinamen nämlich:

Code: Alles auswählen

18612439 ?

Das Fragezeichen ist nur ein Platzhalter. Zudem löscht rm "?" alles, was aus einem Zeichen besteht. Kann nach hinten losgehen. In dieser Situation hilft das gute alte Kommando find.
Also erstmal testen:

Code: Alles auswählen

$ find . -inum 18612439

liefert:

Code: Alles auswählen

./?

Also weg damit:

Code: Alles auswählen

$ find . -inum 18612439 -delete

Und weg ist das Teil.

EDIT: Formatierungen verbessert und missverständliche Formulierung korrigiert.
EDIT2: Korrektur mit wirklich bösartigem Zeichen "\0177"

[TRex]

Sehr cooles Hintergrundwissen, und danke für den Tipp mit find

[tobo]

Code: Alles auswählen

$ touch `echo -e "\077"

Der Dateiname besteht aus dem Zeichen Backspace. Wie soll man da je wieder rankommen?

\077 ist einfach nur das Fragezeichen - kann man also löschen mit `rm \?'. Backspace ist \010 oder einfach \b:

Code: Alles auswählen

$ echo -e "-\077+"
-?+
$ echo -e "-\010+"
+
$ echo -e "-\b+"
+
$ 

`rm ?' würde Dateien bestehend aus einem Zeichen löschen.

[Livingston]

Immer diese blöden Oktalzahlen. Also nun noch mal mit "\0177"
ls zeigt schlimmes Zeug an.
Eine Ausgabe mit ls -N liefert dann das "?" als Ersatz für nichtdruckbare Zeichen.

Hab das Beispiel oben entsprechend korrigiert.

[paedubucher]

Das ist so ein richtiges Feiertagstürchen, das ich mir für die Festtage aufspare, wenn ich es mal gründlich durchlesen kann. Schon einmal Danke dafür vor der genauen Lektüre!