Speicherfresser am Werk
Trotz aller Bemühungen kommt es immer wieder zum Überschreiben von Kernelspeicher. Grund sind aller Wahrscheinlichkeit nach "use-after-free" Fehler, d.h. Zugriff auf Speicherbereiche, die schon nicht mehr in Benutzung sind. Eine Fehlersuche ist im produktiven System nicht möglich, da dies die Systeme extrem verlangsamt und massiv Abstürze generiert.
Es gibt zwei Strategien, diese Probleme abzumildern:
- Die Speicherverwaltung wird pro Verwendungszweck getrennt. Damit sollten die Querschläger zwischen den Prozessen (NetGraph schreibt in NAT-Tabellen) eingedämmt werden. Die notwendigen Anpassungen dafür habe ich bereits entworfen.
- Die Speicherverwaltung des Kernels wird so geändert, daß die Speicherbereiche nicht sofort freigegeben werden, sondern erst nach einer gewissen Wartezeit wieder für die Neuvergabe zur Verfügung stehen. Dies hat zur Folge, daß der Freispeicher knapp werden kann und das System an Speichermangel eingeht. Diese Anpassungen erfordern also besondere Sorgfalt.
In den Tiefen
Pro Verwendungszweck wird in FreeBSD die Struktur struct malloc_type benutzt. Es ist also notwendig, sich an diese anzuhängen.
Glücklicherweise ist für die Erweiterung bereits ein interes Datenfeld struct malloc_type_internal vorgesehen. Die ABI, also die Binärschnittstelle des Kernels zu seinen Modulen, bleibt bei Änderungen an dieser Stelle unbeeinflußt.
An dieser Stelle hänge ich einen Ringpuffer fester Größe ein. Eine dynamische Warteschlange würde zu leicht malloc rekursiv aufrufen, und das will man unbedingt vermeiden.
--- sys/malloc.h (revision 243948)
+++ sys/malloc.h (working copy)
@@ -87,10 +87,29 @@
#define DTMALLOC_PROBE_FREE 1
#define DTMALLOC_PROBE_MAX 2
+/*
+ * Delayed free definitions.
+ */
+#define DELAYED_FREE_MAX 10000
+struct delayed_free_buffer {
+ int head, tail;
+ u_long bytes;
+ struct delayed_free_entry {
+ void * pointer;
+ u_long size;
+ u_long checksum;
+ } stale[DELAYED_FREE_MAX];
+};
+#define DELAYED_FREE_INCR(i) (((i)+1)%DELAYED_FREE_MAX)
+#define DELAYED_FREE_ISEMPTY(dfp) ((dfp)->tail == (dfp)->head)
+#define DELAYED_FREE_ISFULL(dfp) ((dfp)->tail == DELAYED_FREE_INCR((dfp)->head))
+#define DELAYED_FREE_INIT(dfp) do { (dfp)->head = (dfp)->tail = 0; } while(0)
+
struct malloc_type_internal {
uint32_t mti_probes[DTMALLOC_PROBE_MAX];
/* DTrace probe ID array. */
struct malloc_type_stats mti_stats[MAXCPU];
+ struct delayed_free_buffer delayed_free;
};
/*Der Ringpuffer arbeitet mit zwei Indizes, die einer Moduloarithmetik gehorchen. Das nächste und unbenutzte Element steht bei head. Mit tail findet man das älteste, benutzte Element. Stehen beide Zeiger aufeinander ist der Puffer leer. Es ist also immer ein Element in der Liste unbenutzt.
Die Logik zum Einfügen und Löschen von Elementen in den Ringpuffer ist also ganz einfach. Es werden die Zeiger auf den Speicherbereich, die Länge des Speicherbereichs und eine Prüfsumme über den Speicher im Ringpuffer abgelegt. Darüberhinaus wird Buch über die gesamte noch nicht freigegebene Speichermenge geführt.
--- kern/kern_malloc.c (revision 243948)
+++ kern/kern_malloc.c (working copy)
@@ -61,6 +61,7 @@
#include <sys/proc.h>
#include <sys/sbuf.h>
#include <sys/sysctl.h>
+#include <sys/syslog.h>
#include <sys/time.h>
#include <vm/vm.h>
@@ -243,6 +244,140 @@
&malloc_failure_count, 0, "Number of imposed M_NOWAIT malloc failures");
#endif
+static u_long delayed_free_max_size = 1000000;
+static int delayed_free_min_free = DELAYED_FREE_MAX/10;
+enum delayed_free_error {
+ DF_NO_ERROR, DF_OVERRUN, DF_UNDERRUN,
+ DF_CONTAINS_NULL, DF_MODFIED_AFTER_FREE
+};
+static char const * delayed_free_errortext(enum delayed_free_error e) {
+ switch(e) {
+ case DF_NO_ERROR : return "OK";
+ case DF_OVERRUN : return "Circular buffer overrun";
+ case DF_UNDERRUN : return "Circular buffer underrun";
+ case DF_CONTAINS_NULL : return "Delay of a NULL pointer";
+ case DF_MODFIED_AFTER_FREE: return "Detecting modify after free";
+ default : return "Unknown error code (Can't happen)";
+ }
+
+static enum delayed_free_error delayed_free_add(struct malloc_type *mtp, void * x, size_t s);
+static enum delayed_free_error delayed_free_remove(struct malloc_type *mtp, void ** to_be_freed);
+static void delayed_free_free(struct malloc_type *mtp, int all);
+static void delayed_free_incremental(struct malloc_type *mtp);
+static void delayed_free_all(struct malloc_type *mtp);
+static u_long delayed_free_checksum(void const * p, size_t l);
+void free2(void *addr, struct malloc_type *mtp, int delayed);
+
+static u_long delayed_free_checksum(void const *p, size_t l) {
+ return crc32(p, 128 < l ? 128 : l);
+}
+
+static enum delayed_free_error
+delayed_free_add(struct malloc_type *mtp, void * x, size_t s) {
+ enum delayed_free_error error = DF_NO_ERROR;
+
+ critical_enter();
+ {
+ struct malloc_type_internal *mtip = mtp->ks_handle;
+ struct delayed_free_buffer *dfp = &mtip->delayed_free;
+ struct delayed_free_entry *phead = &dfp->stale[dfp->head];
+
+ if(DELAYED_FREE_ISFULL(dfp)) {
+ struct delayed_free_entry *ptail = &dfp->stale[dfp->tail];
+ ptail->pointer = NULL;
+ ptail->size = 0;
+ dfp->tail = DELAYED_FREE_INCR(dfp->tail);
+ error = DF_OVERRUN;
+ }
+ phead->pointer = x;
+ phead->size = s;
+ phead->checksum = delayed_free_checksum(x,s);
+ dfp->bytes += s;
+ dfp->head = DELAYED_FREE_INCR(dfp->head);
+ }
+ critical_exit();
+
+ return error;
+}
+
+static enum delayed_free_error
+delayed_free_remove(struct malloc_type *mtp, void ** to_be_freed) {
+ enum delayed_free_error error = DF_NO_ERROR;
+
+ critical_enter();
+ {
+ struct malloc_type_internal *mtip = mtp->ks_handle;
+ struct delayed_free_buffer *dfp = &mtip->delayed_free;
+
+ if(DELAYED_FREE_ISEMPTY(dfp)) {
+ (*to_be_freed) = NULL;
+ error = DF_UNDERRUN;
+ } else {
+ struct delayed_free_entry *ptail = &dfp->stale[dfp->tail];
+
+ if(ptail->pointer == NULL) {
+ error = DF_CONTAINS_NULL;
+ } else if(ptail->checksum != delayed_free_checksum(ptail->pointer, ptail->size)) {
+ error = DF_MODFIED_AFTER_FREE;
+ }
+
+ (*to_be_freed) = ptail->pointer;
+ dfp->bytes -= ptail->size;
+ ptail->pointer = NULL;
+ ptail->size = 0;
+ dfp->tail = DELAYED_FREE_INCR(dfp->tail);
+ }
+ }
+ critical_exit();
+
+ return error;
+}
+
+static void
+delayed_free_free(struct malloc_type *mtp, int all) {
+ struct malloc_type_internal *mtip;
+ struct delayed_free_buffer *dfp;
+ enum delayed_free_error err;
+
+ KASSERT(mtp->ks_magic == M_MAGIC, ("free: bad malloc type magic"));
+
+ mtip = mtp->ks_handle;
+ dfp = &mtip->delayed_free;
+
+ do {
+ void *p = NULL;
+
+ mtx_lock(&malloc_mtx);
+ if(all || (dfp->head + (DELAYED_FREE_MAX - dfp->tail))%DELAYED_FREE_MAX > delayed_free_min_free || dfp->bytes > delayed_free_max_size) {
+ err = delayed_free_remove(mtp, &p);
+ } else {
+ err = DF_UNDERRUN;
+ }
+ mtx_unlock(&malloc_mtx);
+
+ switch(err) {
+ default:
+ log(LOG_ERR, "Freeing delayed in %s returned '%s'\n", mtp->ks_shortdesc, delayed_free_errortext(err));
+ case DF_NO_ERROR:
+ free2(p, mtp, 0);
+ case DF_UNDERRUN:
+ break;
+ }
+ } while(err != DF_UNDERRUN);
+}
+
+static void
+delayed_free_incremental(struct malloc_type *mtp) {
+ delayed_free_free(mtp, 0);
+}
+
+static void
+delayed_free_all(struct malloc_type *mtp) {
+ delayed_free_free(mtp, 1);
+}
+
+
static int
sysctl_kmem_map_size(SYSCTL_HANDLER_ARGS)
{Es sollte solange verzögert werden, bis der Ringpuffer voll ist. Aber ein voller Ringpuffer kann viel zuviel Freispeicher auffressen. Deswegen wird ab einem Limit (das später tunable werden kann) ebenfalls schon Speicher freigegeben.
Nach jedem malloc und vor jedem free werden die verzögerteten frees ausgeführt, wenn die Limits überschritten sind.
@@ -439,6 +574,7 @@
if (va != NULL)
va = redzone_setup(va, osize);
#endif
+ delayed_free_incremental(mtp);
return ((void *) va);
}
@@ -452,6 +588,13 @@
void
free(void *addr, struct malloc_type *mtp)
{
+ delayed_free_incremental(mtp);
+ free2(addr, mtp, 1);
+}
+
+void
+free2(void *addr, struct malloc_type *mtp, int delayed)
+{
uma_slab_t slab;
u_long size;
@@ -485,6 +628,9 @@
struct malloc_type **mtpp = addr;
#endif
size = slab->us_keg->uk_size;
+ if(delayed) {
+ goto delaying;
+ }
#ifdef INVARIANTS
/*
* Cache a pointer to the malloc_type that most recently freed
@@ -503,9 +649,29 @@
uma_zfree_arg(LIST_FIRST(&slab->us_keg->uk_zones), addr, slab);
} else {
size = slab->us_size;
+ if(delayed) {
+ goto delaying;
+ }
uma_large_free(slab);
}
malloc_type_freed(mtp, size);
+ return;
+
+delaying:
+ {
+ enum delayed_free_error err;
+ mtx_lock(&malloc_mtx);
+ err = delayed_free_add(mtp, addr, size);
+
+ switch(err) {
+ default:
+ log(LOG_ERR, "Delaying free in %s returned '%s'\n", mtp->ks_shortdesc, delayed_free_errortext(err));
+ case DF_NO_ERROR:
+ break;
+ }
+ mtx_unlock(&malloc_mtx);
+ return;
+ }
}
/*
@@ -703,6 +869,7 @@
panic("malloc_init: bad malloc type magic");
mtip = uma_zalloc(mt_zone, M_WAITOK | M_ZERO);
+ DELAYED_FREE_INIT(&mtip->delayed_free);
mtp->ks_handle = mtip;
mtx_lock(&malloc_mtx);
@@ -727,6 +894,8 @@
("malloc_uninit: bad malloc type magic"));
KASSERT(mtp->ks_handle != NULL, ("malloc_deregister: cookie NULL"));
+ delayed_free_all(mtp);
+
mtx_lock(&malloc_mtx);
mtip = mtp->ks_handle;
mtp->ks_handle = NULL;Mal sehen, wie sich dieses Codestück tut. Es sollte die "use-after-free" Fehler bei Raceconditions komplett ausschalten und die "modify-after-free" Fehler benennen können.
Mit der Information, welche Codeteile da quer durch den Speicher schreibt, kann man die Fehler, die sich in der libalias offenbart, überhaupt anfangen zu suchen.
Erste Ergebnisse
Die ersten Ergebnisse sahen schrecklich aus und gingen auf fehlerhaftes Locking zurück.
Nun melden einige Allokatoren häufig einen Overrun, weil mehere Prozesse parallel um das Ende der Warteschlange kämpfen. Bei dem fehlerhaften Lock führte das zu willden Fehlermeldungen, insbesondere zu mit NULL überschriebenen Werten.
Allerdings bestätigt auch vmstat, daß einige dieser Allokatoren das maximale 1MB voll ausnutzen.
# vmstat -m | egrep '99.K|1...K|Size' | cut -c-45 Type InUse MemUse HighUse Requests filedesc 1788 1023K - 37160 temp 6794 1603K - 84225 subproc 536 1290K - 37259 cred 6329 993K - 427648 bus-sc 293 1416K - 8601 bus 10269 1112K - 20615 kobj 356 1424K - 356 ether_multi 43424 1987K - 43424 CAM XPT 977 1136K - 6553 sctpnat 96 1280K - 96 netgraph_msg 10755 1020K - 4177567 netgraph 7200 1824K - 7231
Läuft die Warteschlange über, leakt der Speicher. Unter Last (normal aber nicht) verliere ich so um die 500 Byte in 10 Sekunden. Mit 10 GB unbenutzem Hauptspeicher halte ich das einige Monate aus.
Trotzdem habe ich den Code abgeändert und warte nicht mehr auf den letzten Slot, sondern lasse 10% frei. Damit ist das Speicherleck geschlossen. Und nun kann ich mich auf die eigentliche Fehler konzentrieren.
Jun 17 15:12:38 kernel: Freeing delayed in netgraph_msg returned 'Detecting modify after free' Jun 17 15:12:44 kernel: 1. retry to throw away broken NAT tables (will leak memory)
Kurz nachdem netgraph_msg aus dem Ruder gelaufen ist, bemerkt auch die libalias das Problem und findet in ihrem Speicherbereich die schon bekannte netgraph Nachricht. Kurz darauf stürzt das System ab.
All dies deutet auf einen Fehler in der Netgraph Nachrichtenverarbeitung hin. Für ein entsprechendes Debugging brauche ich nun aber einen vollständigen Memorydump und dafür brauche ich eine Testmaschine. Die rennt schon grundsätzlich unter Hyper-V.
Nachtrag
Mit dem Verzicht auf das Löschen von Interface-Knoten konnten die Fehler bisher vollständig beseitigt werden.