java-topology/defects/nfs-utils-0002/test/test_get_exportlist.c

/*
 * test_get_exportlist.c - CWE-407 unit test for nfs-utils get_exportlist
 *
 * Demonstrates O(E^2) behavior in get_exportlist() from two sources:
 *
 * 1. lookup_or_create_elist_entry(): linear scan of elist linked list
 *    to find matching export path. Called once per export entry.
 *    With E exports to P unique paths, cost is O(E*P).
 *
 * 2. insert_group(): linear scan of ex_groups linked list to check
 *    for duplicate group names. Called once per export.
 *    With G groups per path, cost is O(E*G).
 *
 * Combined: for E exports with E unique paths, total is O(E^2).
 *
 * Fix: use hash tables for both path lookup and group dedup.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* --- Simulate linked list approach (current code) --- */

struct groupnode {
    struct groupnode *next;
    char *name;
};

struct exportnode {
    struct exportnode *next;
    char *path;
    struct groupnode *groups;
};

static struct exportnode *elist_linear = NULL;

static struct exportnode *lookup_or_create_linear(const char *path)
{
    struct exportnode *e;
    for (e = elist_linear; e; e = e->next) {
        if (strcmp(path, e->path) == 0)
            return e;
    }
    e = calloc(1, sizeof(*e));
    e->path = strdup(path);
    e->groups = NULL;
    e->next = elist_linear;
    elist_linear = e;
    return e;
}

static void insert_group_linear(struct exportnode *e, const char *name)
{
    struct groupnode *g;
    for (g = e->groups; g; g = g->next)
        if (strcmp(g->name, name) == 0)
            return;
    g = calloc(1, sizeof(*g));
    g->name = strdup(name);
    g->next = e->groups;
    e->groups = g;
}

static void free_elist_linear(void)
{
    struct exportnode *e, *en;
    for (e = elist_linear; e; e = en) {
        en = e->next;
        struct groupnode *g, *gn;
        for (g = e->groups; g; g = gn) {
            gn = g->next;
            free(g->name);
            free(g);
        }
        free(e->path);
        free(e);
    }
    elist_linear = NULL;
}

/* --- Hash table approach (fix) --- */

#define HT_SIZE 4096

struct ht_path_entry {
    struct ht_path_entry *next;
    char *path;
    struct exportnode *node;
};

struct ht_group_entry {
    struct ht_group_entry *next;
    char *name;
};

static struct ht_path_entry *path_ht[HT_SIZE];

static unsigned int str_hash(const char *s)
{
    unsigned int h = 5381;
    for (; *s; s++)
        h = h * 33 + (unsigned char)*s;
    return h % HT_SIZE;
}

/* For group dedup, we use a simple per-export hash set.
 * In practice, each exportnode would carry its own hash set.
 * For this test, we simulate with a global set that resets per-path. */
static struct ht_group_entry *group_ht[HT_SIZE];

static struct exportnode *lookup_or_create_hash(const char *path)
{
    unsigned int idx = str_hash(path);
    struct ht_path_entry *he;
    for (he = path_ht[idx]; he; he = he->next) {
        if (strcmp(path, he->path) == 0)
            return he->node;
    }
    struct exportnode *e = calloc(1, sizeof(*e));
    e->path = strdup(path);
    e->groups = NULL;

    he = calloc(1, sizeof(*he));
    he->path = e->path;
    he->node = e;
    he->next = path_ht[idx];
    path_ht[idx] = he;
    return e;
}

static void insert_group_hash(struct exportnode *e, const char *name)
{
    unsigned int idx = str_hash(name);
    struct ht_group_entry *ge;
    for (ge = group_ht[idx]; ge; ge = ge->next)
        if (strcmp(ge->name, name) == 0)
            return;
    ge = calloc(1, sizeof(*ge));
    ge->name = strdup(name);
    ge->next = group_ht[idx];
    group_ht[idx] = ge;
}

static void free_hash(void)
{
    for (int i = 0; i < HT_SIZE; i++) {
        struct ht_path_entry *he, *hn;
        for (he = path_ht[i]; he; he = hn) {
            hn = he->next;
            free(he->node->path);
            free(he->node);
            free(he);
        }
        path_ht[i] = NULL;

        struct ht_group_entry *ge, *gn;
        for (ge = group_ht[i]; ge; ge = gn) {
            gn = ge->next;
            free(ge->name);
            free(ge);
        }
        group_ht[i] = NULL;
    }
}

static double measure_linear(int n)
{
    char pathbuf[128], hostbuf[128];
    struct timespec start, end;
    free_elist_linear();

    clock_gettime(CLOCK_MONOTONIC, &start);
    for (int i = 0; i < n; i++) {
        snprintf(pathbuf, sizeof(pathbuf), "/export/path%d", i);
        snprintf(hostbuf, sizeof(hostbuf), "client%d.example.com", i);
        struct exportnode *e = lookup_or_create_linear(pathbuf);
        insert_group_linear(e, hostbuf);
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    free_elist_linear();

    return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
}

static double measure_hash(int n)
{
    char pathbuf[128], hostbuf[128];
    struct timespec start, end;
    free_hash();

    clock_gettime(CLOCK_MONOTONIC, &start);
    for (int i = 0; i < n; i++) {
        snprintf(pathbuf, sizeof(pathbuf), "/export/path%d", i);
        snprintf(hostbuf, sizeof(hostbuf), "client%d.example.com", i);
        struct exportnode *e = lookup_or_create_hash(pathbuf);
        insert_group_hash(e, hostbuf);
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    free_hash();

    return (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
}

int main(void)
{
    int sizes[] = {500, 1000, 2000, 4000};
    int nsizes = sizeof(sizes) / sizeof(sizes[0]);
    int pass = 1;

    printf("nfs-utils-0002: get_exportlist O(E^2) linked list scan\n");
    printf("%-8s %-12s %-12s %-8s\n", "N", "linear(ms)", "hash(ms)", "ratio");

    for (int i = 0; i < nsizes; i++) {
        int n = sizes[i];
        double t_lin = measure_linear(n);
        double t_hash = measure_hash(n);
        double ratio = t_lin / (t_hash > 0 ? t_hash : 1e-9);

        printf("%-8d %-12.2f %-12.2f %-8.1fx\n",
               n, t_lin * 1000, t_hash * 1000, ratio);
    }

    /* Final pass/fail: at N=4000, ratio must be >= 5x */
    double t_lin = measure_linear(4000);
    double t_hash = measure_hash(4000);
    double final_ratio = t_lin / (t_hash > 0 ? t_hash : 1e-9);

    if (final_ratio < 5.0) {
        printf("FAIL: ratio %.1fx < 5x at N=4000\n", final_ratio);
        pass = 0;
    } else {
        printf("PASS: ratio %.1fx >= 5x at N=4000\n", final_ratio);
    }

    return pass ? 0 : 1;
}