check-detection.c

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

#define PAGE_SIZE 8192

typedef uint16_t uint16;
typedef uint32_t uint32;
typedef uint64_t uint64;

#include "checksums-crc32c.c"

double testSingleBitFlip(char *buf, uint16_t expected, uint32_t blkno) {
    int word;
    uint32_t tmp;
    uint32_t collisions = 0;
    uint32_t bit;
    uint32_t * volatile ptr32Buf = (uint32_t*) buf;
    
    for (word = 0; word < PAGE_SIZE/4; word++) {
        if (word == 2) {
            continue;
        }
        tmp = ptr32Buf[word];
        for (bit = 0x80000000; bit; bit >>= 1) {
            ptr32Buf[word] = tmp ^ bit;
            if (checksum_fast((char*)ptr32Buf, blkno) == expected) {
                collisions++;
            }
        }
        ptr32Buf[word] = tmp;
    }
    
    return (double) collisions / 8. / (PAGE_SIZE-4);
}

double testWriteByte(uint64_t *tests, char *buf, uint16_t expected, uint32_t blkno, uint8_t v) {
    int byte;
    uint8_t tmp;    
    uint32_t collisions = 0;
    uint32_t count = 0;
    uint8_t * volatile ptr8Buf = (uint8_t*) buf;
    
    for (byte = 10; byte < PAGE_SIZE; byte++) {
        tmp = ptr8Buf[byte];
        if (tmp != v) {
            count++;
            ptr8Buf[byte] = v;
            if (checksum_fast(ptr8Buf, blkno) == expected) {
                collisions++;
            }
            ptr8Buf[byte] = tmp;
        }
    }
    if (!count)
        return 0;
    *tests += count;
    return (double) collisions;
}

void flipBit(uint8_t * volatile ptr8Buf, uint32_t bit) {
    ptr8Buf[bit/8] = ptr8Buf[bit/8] ^ (1 << (bit % 8));
}

double testNBitFlip(uint64_t *tests, void *buf, uint16_t expected, uint32_t blkno, int iters, int bits) {    
    uint32_t bitpositions[bits];
    uint32_t collisions = 0;
    int i, j, k;
    uint8_t * volatile ptr8Buf = (uint8_t*) buf;
    
    for (i = 0; i < iters; i++) {
        for (j = 0; j < bits; j++) {
            do {
                again:
                bitpositions[j] = (random() % (PAGE_SIZE*8));
                for (k = 0; k < j; k++)
                    if (bitpositions[j] == bitpositions[k]) goto again;
                
            } while (bitpositions[j] >= 64 && bitpositions[j] < 80);
            
            flipBit(ptr8Buf, bitpositions[j]);
        }
        if (checksum_fast(ptr8Buf, blkno) == expected) {
            collisions++;
        }
                
        for (j = 0; j < bits; j++) {
            flipBit(ptr8Buf, bitpositions[j]);
        }
        
    }
    *tests += iters;
    return (double) collisions;
}

double testPartialWrite(uint64_t *tests, char *buf, uint16_t expected, uint32_t blkno, int iters) {    
    uint32_t cut_pos;
    uint32_t collisions = 0;
    uint32_t max_nonzero = PAGE_SIZE;
    int i, j;
    char *tmp_buf;

    tmp_buf = malloc(PAGE_SIZE);
    
    while (max_nonzero > 0 && buf[max_nonzero-1] == 0) {
        max_nonzero--;
    }
    if (max_nonzero == 0) {
        return 0;
    }
    
    for (i = 0; i < iters; i++) {
        cut_pos = ((uint32_t)random() % max_nonzero);

        memset(tmp_buf, 0, PAGE_SIZE);
        memcpy(tmp_buf, buf, cut_pos);
        if (checksum_fast(tmp_buf, blkno) == expected) {
            collisions++;
        }
    }
    free(tmp_buf);

    *tests += iters;
    return (double) collisions;
}

double testWriteGarbage(uint64_t *tests, char *buf, uint16_t expected, uint32_t blkno, int iters, int garbage) {    
    uint32_t cut_pos1, cut_pos2, tmp;
    uint32_t collisions = 0;
    uint32_t changed = 0;
    uint32_t changes = 1;
    uint32_t max_nonzero = PAGE_SIZE;
    int i, j;
    uint8_t *tmp_buf;

    tmp_buf = malloc(PAGE_SIZE);
    
    for (i = 0; i < iters; i++) {
        do {
            cut_pos1 = ((uint32_t)random() % PAGE_SIZE);
            cut_pos2 = ((uint32_t)random() % PAGE_SIZE);
        } while (cut_pos1 == cut_pos2);
        if (cut_pos2 < cut_pos1) {
            tmp = cut_pos1;
            cut_pos1 = cut_pos2;
            cut_pos2 = tmp;
        }
        
        memcpy(tmp_buf, buf, PAGE_SIZE);
        changed = 0;
        for (j = cut_pos1; j < cut_pos2; j++) {
            uint8_t new_value = ((garbage < 0) ? random() : garbage) & 0xFF;
            if (new_value != tmp_buf[j]) {
                changed = 1;
            }
            tmp_buf[j] = new_value;
        }
        if (!changed)
	     continue;       
	changes++;

        if (checksum_fast(tmp_buf, blkno) == expected) {
            collisions++;
        }
    }
    free(tmp_buf);
    if (!changes)
        return 0;
    *tests += changes;
    return (double) collisions;
}

#ifndef SKIP
#define SKIP 1
#endif
#ifndef USERANDOM
#define USERANDOM 1
#endif
#ifndef PAGES
#define PAGES 10
#endif

#define N 10
int main() {
    char *page;
    double results[N];
    char *names[N] = {
        "Single bit flip",
        "Double bit flip",
        "Triple bit flip",
        "Quad bit flip",
        "Write 0x00 byte",
        "Write 0xFF byte",
        "Partial write",       
        "Write garbage",
        "Write run of 0",
        "Write run of FF",
    };
    uint64_t counts[N];
    uint16_t expected;
    uint32_t blkno;
    FILE *fp;
    int i;

    for (i = 0; i < N; i++) {
        results[i] = 0.0;
        counts[i] = 0;
    }

    page = malloc(PAGE_SIZE);
#if USERANDOM
    fp = fopen("/dev/urandom", "r");
#else
    fp = fopen("data.pages", "r");    
#endif
    
    for (i = 0; i < PAGES; i+=SKIP) {
        int z = 0;
        if (fread(page, 1, PAGE_SIZE, fp) != PAGE_SIZE)
            break;
        
        blkno = i;
        expected = checksum_fast(page, blkno);
        results[z] += testNBitFlip(&counts[z], page, expected, blkno, 100, 1);
        z++;
        results[z] += testNBitFlip(&counts[z], page, expected, blkno, 100, 2);
        z++;
        results[z] += testNBitFlip(&counts[z], page, expected, blkno, 100, 3);
        z++;
        results[z] += testNBitFlip(&counts[z], page, expected, blkno, 100, 4);
        z++;
        results[z] += testWriteByte(&counts[z], page, expected, blkno, 0x00);
        z++;
        results[z] += testWriteByte(&counts[z], page, expected, blkno, 0xFF);
        z++;
        results[z] += testPartialWrite(&counts[z], page, expected, blkno, 100);
        z++;
        results[z] += testWriteGarbage(&counts[z], page, expected, blkno, 100, -1);
        z++;
        results[z] += testWriteGarbage(&counts[z], page, expected, blkno, 100, 0);
        z++;
        results[z] += testWriteGarbage(&counts[z], page, expected, blkno, 100, 0xFF);
    }
    for (i = 0; i < N; i++) {
        results[i] /= counts[i];
        printf("%15s: 1:%0.0f\n", names[i], 1/results[i]);
    }
    fclose(fp);
    return 0;
}