blog · git · desktop · images · contact


Linux: Speicherfragmentierung und Verdichtung

2017-12-23

Bin noch dabei, die Out-of-Memory-Situationen von kürzlich zu analysieren.

Werfen wir einen Blick auf Speicherfragmentierung. Da die deutsche Sprache hier etwas unpräzise ist: Es geht um Arbeitsspeicher. RAM. Nicht um das Dateisystem auf der Festplatte.

Externe Fragmentierung

Man habe ein Stück linearen Speicher, der in Gänze unbenutzt ist. Man teilt ihn jetzt ein mehrere Stücke gleicher Größe ein. Man kann immer nur einen solchen Block allokieren und nicht etwa nur einen Teil davon. Nun allokiert man drei Blöcke nacheinander und gibt danach den Block in der Mitte wieder frei.

Sieht so aus:

1)    [ ----- ][ ----- ][ ----- ][ ----- ]    Leer
2)    [ - A - ][ - B - ][ - C - ][ ----- ]    A, B, C allokiert
3)    [ - A - ][ ----- ][ - C - ][ ----- ]    B wieder freigegeben

Dieses Bild entspricht quasi dem des Wikipedia-Artikels zu dem Thema.

Wenn man jetzt annimmt, dass das aller Speicher ist, den man hat, dann läuft man in ein Problem, wenn es jetzt eine Anfrage für zwei benachbarte Blöcke gibt. Es gibt nämlich keine. Der Speicher ist fragmentiert. Selbst, wenn also nun ein hypothetisches Programm ähnlich free(1) ausgeben würde, dass „10 von 20 MB verfügbar“ sind, würde eine Anfrage für 8 MB Speicher am Stück fehlschlagen.

(Interne Fragmentierung passiert, wenn man nicht den kompletten Speicher ausnutzt, der einem zugewiesen wurde. Beispielsweise könnte oben der Block A eigentlich nur ein Byte benutzen. Das soll uns hier aber nicht weiter interessieren.)

Würde man den Block C eins nach links schieben können, so könnte man die Fragmentierung beheben. Das wird dann Verdichtung oder „Compaction“ genannt.

Fragmentierung in Linux anzeigen

In /proc/buddyinfo stehen wertvolle Informationen über den Speicher:

# cat /proc/buddyinfo
Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
Node 0, zone    DMA32      2      2     10     17     12      4      2      2      1      2    466

(Das ist in einer VM.)

In der Zone „DMA32“ gibt es zwei Bereiche des Rangs 0, danach zwei des Rangs 1, gefolgt von 10 Stück des Rangs 2, dann 17 von Rang 3 und so weiter. Ganz am Ende befinden sich 466 Bereiche von Rang 10. „Rang“ meint hier den Exponenten n in 2^n. Die genannten 466 Bereiche sind also 2^10 · 4096 Bytes, was etwa die gesamten 2 GB sind, die ich meiner VM zugewiesen habe.

Sprich, quasi der ganze Speicher ist unbenutzt und es gibt viele große und zusammenhängende Bereiche.

So im Allgemeinen will man meistens eher größere Zahlen in den rechten Spalten stehen haben. Wenn diese Zahlen sinken oder gar auf Null zurückgehen, läuft man in Fragmentierung. Steht ganz rechts eine Null, dann heißt das immerhin, dass nicht einmal mehr 4 MiB (!) am Stück irgendwo vorhanden sind. Das ist allerdings nicht notwendigerweise ein Problem, weil oft genug Speicher bei Bedarf auch wieder freigegeben oder vielleicht verdichtet werden kann.

Uns interessiert hier auch die Gesamtmenge, die von einer Zeile in /proc/buddyinfo beschrieben wird. Das folgende, nicht gerade komplizierte awk-Snippet namens analyze erledigt das:

#!/usr/bin/awk -f

{
    sum = $5 * 2**0 * 4096 + \
          $6 * 2**1 * 4096 + \
          $7 * 2**2 * 4096 + \
          $8 * 2**3 * 4096 + \
          $9 * 2**4 * 4096 + \
          $10 * 2**5 * 4096 + \
          $11 * 2**6 * 4096 + \
          $12 * 2**7 * 4096 + \
          $13 * 2**8 * 4096 + \
          $14 * 2**9 * 4096 + \
          $15 * 2**10 * 4096
    printf "%7.2f MiB    ", sum / 1024 / 1024
    print
}

Fragmentierung herbeiführen

Sorgen wir mal für künstliche Fragmentierung in unserer VM. Relevant ist das nur für Kernelspeicher, also brauchen wir wieder ein kleines Kernelmodul – fragment.c. Es ist sehr zu empfehlen, das auch wirklich in einer VM zu machen, da es den Kernelspeicher korrumpieren wird (es bleiben nicht wieder freigebbare Pages zurück).

#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h>

#define N_MEM 100000
static char *mems[N_MEM];

static int
fragment_init(void)
{
    size_t i;

    for (i = 0; i < N_MEM; i++)
        mems[i] = kzalloc(16384, GFP_KERNEL);

    return 0;
}

static void
fragment_exit(void)
{
    size_t i;

    for (i = 0; i < N_MEM; i += 2)
        kfree(mems[i]);
}

module_init(fragment_init);
module_exit(fragment_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("nobody-cares");

In Arch Linux muss man wieder die beiden Pakete base-devel und linux-headers installieren, damit man das Modul mit folgender Makefile bauen kann (Tabs zur Einrückung sind wichtig):

obj-m := fragment.o

all:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

Das Modul allokiert 100'000 Speicherblöcke von je 16'384 Bytes. Sollte der Speicher dafür nicht reichen, legt es sich fürchterlich auf die Nase. Außerdem wird beim Entladen nur jeder zweite Block wieder freigegeben. Wenn man das Modul einmal entladen hat, will man die VM rebooten.

Das heißt, wir sehen etwa folgenden Ablauf:

1)    ________________    Ganzer Speicher unbenutzt
2)    ############____    Viel Speicher benutzt
3)    #_#_#_#_#_#_____    Die Hälfte dessen wieder freigegeben

Die Calls von kfree() habe ich in die Exit-Funktion gepackt, damit es einfacher ist, für jeden Schritt Speicherstatistiken anzuzeigen.

So sieht es dann aus. Bevor irgendwas passiert ist, ist viel Speicher ungenutzt:

# free -m ; echo ; ./analyze /proc/buddyinfo
              total        used        free      shared  buff/cache   available
Mem:           2000          41        1826           0         133        1823
Swap:             0           0           0

  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
1809.91 MiB    Node 0, zone    DMA32    114    136    104     13     12      5      8     10      6      2    447

Nachdem das Modul geladen ist, geht die Belegung nach oben. Man beachte, wie die Zahl der Rang-10-Bereiche deutlich nach unten geht:

# insmod module/fragment.ko
# free -m ; echo ; ./analyze /proc/buddyinfo
              total        used        free      shared  buff/cache   available
Mem:           2000        1604         261           0         134         260
Swap:             0           0           0

  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
 246.31 MiB    Node 0, zone    DMA32     60     94     92     13     10      5      9     10      5      3     56

Jetzt entladen wir das Modul wieder:

# rmmod fragment
# free -m ; echo ; ./analyze /proc/buddyinfo
              total        used        free      shared  buff/cache   available
Mem:           2000         822        1043           0         134        1042
Swap:             0           0           0

  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
1028.15 MiB    Node 0, zone    DMA32    116    145  50098     13     10      4      9     10      5      3     56

Knapp 800 MiB wurden freigegeben, was wir auch erwartet haben. Bei den Rang-2-Bereichen sehen wir jetzt eine ziemlich große Zahl. Das sind Bereiche der Größe 16'384 Bytes und die, die wir freigegeben haben. Wir sehen aber keine freien Bereiche höheren Ranges. Unser Speicher ist also erfolgreich fragmentiert.

Der Versuch, den Speicher zu verdichten

Man kann den Kernel darum bitten, den Speicher wieder zu verdichten. Machen wir das:

# echo 1 >/proc/sys/vm/compact_memory
# free -m ; echo ; ./analyze /proc/buddyinfo
              total        used        free      shared  buff/cache   available
Mem:           2000         822        1042           0         135        1042
Swap:             0           0           0

  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
1027.19 MiB    Node 0, zone    DMA32     48      8  50004     12      4      2      5      3      6      2     58

Ups.

Da sind zwar ein paar Bereiche wieder zusammengefasst worden, aber nur sehr wenige. Das lässt sich auch durch die normale Hintergrundaktivität des Systems erklären.

Wie ich dann gelernt habe, ist nicht jeder Speicherbereich verschiebbar. Wenn das nicht der Fall ist, kann die Verdichtung auch nichts bewirken. Dieser LWN-Artikel von 2010 sagt, dass der „meiste“ Speicher, der direkt vom Kernel verwendet wird, nicht verschoben werden kann.

Ein anderer LWN-Artikel zeigt noch ein paar weitere Details auf. Man muss sich schon ein bisschen anstrengen, um Speicher verschiebbar zu machen. Vielleicht probiere ich das in einem anderen Posting mal aus.

Erfolgreiche Speicherverdichtung

Funktioniert die Verdichtung mittels des echo überhaupt? Oder mache ich hier etwas komplett falsch?

Versuchen wir mal, Fragmentierung durch Userspace-Prozesse zu erzeugen. Die Annahme dabei ist, dass diese Speicherbereiche verschiebbar sind – warum sollten sie es auch nicht sein, immerhin können sie sogar auf die Festplatte rausgeswappt werden.

Auf diese Weise Fragmentierung zu erzeugen, ist nicht ganz so leicht. Der folgende Ansatz scheint zu funktionieren:

#include <stdio.h>
#include <string.h>
#include <unistd.h>

int
main()
{
    char *p;
    size_t i;

    p = sbrk(0);

    for (i = 0; i < 200000; i++)
    {
        sbrk(4096);
        memset(p + i * 4096, 'a', 4096);
    }

    puts("Allocated. Press Enter to quit.");
    getchar();
    return 0;
}

Ein Programm, das 200'000 · 4096 Bytes allokiert und dabei die Speicherverwaltung der libc zu umgehen versucht. Ja, der Speicher wird in kleinen Blöcken angefordert, aber das ist noch nicht der Knackpunkt. Wir kaufen damit nur Zeit. Viel wichtiger ist, dass das Programm zweimal parallel zu starten:

# ./userspace_fragment & ./userspace_fragment &

(Wenn das Programm dann von stdin lesen will, kriegt es ein SIGTTIN und wird dadurch angehalten. Das ist in Ordnung.)

Die Hoffnung ist, dass der Speicher nun so aussieht:

11212221121212121222212212

Es soll also Bereiche geben, die zu Prozess Nummer eins gehören, dann welche vom zweiten Prozess, dann wieder der erste und so weiter. Bricht man dann einen der beiden ab, sollte es zu Fragmentierung führen. Mal sehen.

Erstmal laufen beide Prozesse:

# ./analyze /proc/buddyinfo
  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
 198.29 MiB    Node 0, zone    DMA32    146    138    167    127     67      3      2      2      2      3     44

So weit, so gut. Der ganze Speicher ist allokiert. Schießen wir jetzt einen Prozess ab:

# kill %1
[1]-  Terminated              userspace_fragment
# ./analyze /proc/buddyinfo
  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
 980.84 MiB    Node 0, zone    DMA32   6446   6410   6335   6271   6214    136     21      4      4      3     47

Super! Etwa 800 MiB wurden freigegeben und wir sehen einiges an Fragmentierung. Jetzt kommt die Compaction:

# echo 1 >/proc/sys/vm/compact_memory
# ./analyze /proc/buddyinfo
  15.46 MiB    Node 0, zone      DMA      1      1      1      0      1      1      1      0      1      1      3
 980.19 MiB    Node 0, zone    DMA32    142    143    117     96     61     21     21     14     13     13    229

Na also. Wenn Speicher verschiebbar ist, dann funktioniert die Verdichtung auch.

Fazit

Sollte man jetzt einen Cronjob installieren, der jede Minute die Verdichtung anstößt? Nein. Das macht der Kernel nämlich automatisch, wenn die Notwendigkeit dafür besteht.

Das heißt dementsprechend, dass es ohnehin quasi wertlos ist, dieses echo 1 >/proc/sys/vm/compact_memory auszuführen. Ja, dadurch wird Speicher wieder verdichtet, aber vermutlich ist das in dem Moment völlig unnötig. Außerdem bringt es bei nichtverschiebbarem Kernel-Speicher auch nichts. Wenn also ein Kernelmodul durchdreht und Fragmentierung verursacht, dann gibt es vermutlich nichts, was man selbst dagegen tun kann. Mindestens Compaction wird nicht helfen.

Comments?