robust-co.de

– Robuste Heap-Objekte in C

Robuste Heap-Objekte in C

26.04.2014

Der robuste Umgang mit Heap-Objekten in maschinennahen Sprachen wie C, C++ oder Objective-C ist schwierig. Es existiert leider keine Typ-Prüfung zur Laufzeit. Diese kann sicherstellen, dass ein übergebenes Objekt tatsächlich von dem erwarteten Typ ist. Sprachen wie Java sind an dieser Stelle weiter.

In diesem Beitrag möchte ich zeigen, wie man in C sich diese Sicherheit Stück für Stück aufbauen kann. Dafür wird etwas Rechenzeit und etwas Speicher geopfert werden müssen.

Anforderungen an ein starkes Typ-System

Nehmen wir an, für ein Auswertungs-Tool benötigen wir die Summe von Messwerten und deren Anzahl, um den durchschnittlichen Messwert ermitteln zu können. Das Interface (der C-Header) sieht so aus:

avg.h:

#if !defined(avg_h)
#define avg_h

typedef struct entry Entry;

Entry *entry_alloc();
void entry_free(Entry *entry);

void entry_add(Entry *entry, double value);
double entry_avg(Entry *entry);

#endif

Und dies ist eine erste Implementierung:

avg_1.c:

#include "avg.h"

#include <stdio.h>
#include <stdlib.h>

struct entry {
    double sum;
    unsigned long count;
};

Entry *entry_alloc() {
    Entry *result = malloc(sizeof(Entry));
    if (!result) { puts("can't create entry"); return NULL; }

    result->sum = 0;
    result->count = 0;
    return result;
}

void entry_free(Entry *entry) {
    if (entry) free(entry);
}

void entry_add(Entry *entry, double value) {
    if (!entry) { puts("no entry to add to"); return; }

    entry->sum += value;
    ++entry->count;
}

double entry_avg(Entry *entry) {
    if (!entry) { puts("no entry to avg"); return 0; }
    if (!entry->count) { return 0; }

    return entry->sum / entry->count;
}

Diese Funktionen sind schon gar nicht schlecht. Aber der Compiler hindert mich nicht, die Funktionen mit völlig sinnlosen Parametern aufzurufen, z.B. mit

cpp entry_add((Entry *) 0x42, 42);

Je nach Platform kann dies zu Abstürzen führen. Der Code ist nicht robust. Damit haben wir das Paradigma der robusten Programmierung verletzt.

Der einfache Test, ob entry NULL ist, reicht nicht aus.

Wenn es nur wenige Instanzen gibt

Wenn die Anzahl der Instanzen überschaubar ist, könnnen wir sie in einer Liste verwalten. Dann wäre die Prüfung, ob der übergebene Zeiger in dieser Liste ist.

Am Interface nach außen muss sich nichts ändern, da die Struktur selbst ein abstrakter Datentyp ist und ihre Felder nicht veröffentlicht. Wenn die Liste direkt selber implementiert wird, kann der Code wie folgt aussehen:

avg_2.c:

#include "avg.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct entry {
    double sum;
    unsigned long count;
    Entry *next;
};

static Entry *_entries = NULL;

Entry *entry_alloc() {
    Entry *result = malloc(sizeof(Entry));
    if (!result) { puts("can't create entry"); return NULL; }

    result->sum = 0;
    result->count = 0;
    result->next = _entries;
    _entries = result;
    return result;
}

void entry_free(Entry *entry) {
    if (!entry) { puts("entry is NULL"); return; }

    bool found = false;
    if (entry == _entries) {
        found = true;
        _entries = entry->next;
    } else {
        for (
            Entry *prev = _entries;
            prev->next;
            prev = prev->next
        ) {
            if (prev->next == entry) {
                found = true;
                prev->next = entry->next;
                break;
            }
        }
    }
    if (!found) { puts("no valid entry"); return; }
    free(entry);
}

bool entry_valid(Entry *entry) {
    if (!entry) { puts("entry is NULL"); return false; }
    for (Entry *cur = _entries; cur; cur = cur->next) {
        if (cur == entry) return true;
    }
    puts("entry not valid");
    return false;
}

void entry_add(Entry *entry, double value) {
    if (!entry_valid(entry)) { return; }

    entry->sum += value;
    ++entry->count;
}

double entry_avg(Entry *entry) {
    if (!entry_valid(entry)) { return 0; }
    if (!entry->count) { return 0; }

    return entry->sum / entry->count;
}

Damit sind die Funktionen ohne Änderung des Interfaces in eine robuste Variante umgewandelt worden. Schmerzlich ist allerdings der hohe Aufwand für die Verifizierung.

Bei jedem Funktionsaufruf werden im Mittel die Hälfte aller Instanzen durchwandert. Es sollten daher wirklich nicht zu viele werden, wenn diese Variante verwendet wird.

Und bei vielen Instanzen?

Das gleiche Prinzip kann jedoch skalieren. Anstatt einer Liste sollte man einen Hash oder balancierten Baum verwenden, die beide einen konstanten Zugriff bieten.

Bibliotheken wie GLib bieten eine gute Hash-Implementierung.

Zusammenfassung

Parameter mit Zeigern sind in C nicht vertrauenswürdig. Für wirklich robuste Programme, sollten diese explizit geprüft werden, wenn sie ungültig sein könnten. Nur so kann verhindert werden, dass das Programm abbricht.

Dies mag vielen als Overkill vorkommen. Wenn man innerhalb eines Programms sicherstellen kann, dass der Missbrauch niemals eintreten kann, dann (und nur dann) kann auf diese Sicherung verzichtet werden.

Aber schon bei Bibliotheken, die von anderen Programmen genutzt werden können, bietet sich die Vorsicht an, um wirklich stabilen Code zu schreiben.

Aktualisierung am 1.5.2014

Ich habe den Source-Code angepasst und direkt eingebunden. Die Dateien sind verlinkt und können direkt verwendet werden.


Kommentare

Möchten Sie einen Beitrag korrigieren, ergänzen oder kommentieren? Senden Sie mir eine E-Mail an timm@robust-co.de. Interessante Beiträge veröffentliche ich gerne auf dieser Seite.