1

--Important Edit--

Thanks for the tip on compiling with -fsanitize=address -g, it allowed me to track down the problem. I'm almost done and I've isolated the issue (which happens near the top of the cleanup function). To simplify things, why does the following (when compiled with the above flags) fail?

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

struct pair {
    char *left;
    char *right;
};

int main() {
    struct pair *pairs = malloc(100 * sizeof(*pairs));
    for (int x = 0; x < 100; x++) {
        printf("%i\n", x);
        pairs->left = pairs->right = NULL;
        pairs += sizeof(*pairs);
    }
    return 0;
}

After printing 0-7 on new lines, I get ==9803==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x61b000000788 at pc 0x00010cb90d88 bp 0x7ffee306fa90 sp 0x7ffee306fa88...Address 0x61b000000788 is a wild pointer.

--Original Question--

I've been working on a brainfuck interpreter in C, but I keep inconsistently getting a segfault. While trying to debug this for a day, I've done many things which, rather than catching where the problem is, simply cause it not to happen. I think at this point I'm encountering undefined behavior, but after rereading my code multiple times I don't see where it could be happening. All of these things cause the program to work as intended:

  • Printing a variable amount of characters between the bottom of the function body of cleanup and the top of the function body of execute (including inside the main function), though this isn't always consistent
  • Compiling with the -g flag for debugging
  • At the top of the execute function
    unsigned char *pointer = (unsigned char*) calloc(30000, 1);
    unsigned char *leftbound = pointer, *rightbound = pointer;
    rightbound += 29999;
    
    changing 30000 to 1000 and 29999 to 999

I've read the documentation on malloc, realloc, and calloc, and browsed for other answers, and I still can't tell the problem. As far as I can tell, I have no memory leaks (even when I realloc a struct pair*, the memory at the pointers within each struct is not leaked because it is within the char *program block) or other issues. That's why I would provide the minimal answer to reproduce the problem, but I'm beginning to doubt that removing seemingly unrelated parts of my source code will have no effect on it (though I have stripped down my code a lot still).

I'm using Mac OS X 10.14, bash "gcc -o brainfc brainfc.c" OR "clang -o brainfc brainfc.c" to compile, "brainfc mandelbrot.b" to run program. The mandelbrot.b file can be found here: http://esoteric.sange.fi/brainfuck/utils/mandelbrot/mandelbrot.b

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

char *program = NULL;

struct pair {
    char *left;
    char *right;
};

//Reads into global variable program from file
void fileinput(char *filename) {
    FILE *fp;
    fp = fopen(filename, "rb");
    if (fp) {
        size_t inputlen = 0;
        fseek(fp, 0, SEEK_END);
        int filesize = ftell(fp);
        rewind(fp);
        program = malloc(filesize + 1);
        fread(program, filesize, 1, fp);
        *(program + filesize) = 0;
        fclose(fp);
    }
}

//Removes unwanted characters from program, as well as compiling lookup table of pairs
//This happens in a single sweep through the program for efficiency,
//though again this problem might not occur if I optimized for readability
struct pair* cleanup() {
    int pairsize = 200;
    struct pair *pairs = calloc(pairsize, sizeof(*pairs));
    char *src, *dest;
    struct pair *buildptr = pairs;
    int bracketlevel = 0;
    for (src = dest = program; *src; dest += (strchr("<>+-[].,", *src++) != NULL)) {
        *dest = *src;
        if (*dest == '[') {
            bracketlevel++;
            while (buildptr->left) {
                if (buildptr == pairs + (pairsize - 1) * sizeof(*pairs)) {
                    pairsize += 100;
                    pairs = realloc(pairs, pairsize * sizeof(*pairs));
                    for (int x = 0; x < 100; x++) {
                        buildptr += sizeof(*pairs);
                        buildptr->left = buildptr->right = NULL;
                    }
                    buildptr -= sizeof(*pairs) * 100;
                }
                buildptr += sizeof(*pairs);
            }
            buildptr->left = dest;
        } else if (*dest == ']') {
            bracketlevel--;
            if (bracketlevel < 0) {
                return NULL;
            }
            while (buildptr->right) {
                buildptr -= sizeof(*pairs);
            }
            buildptr->right = dest;
        }
    }
    if (bracketlevel != 0) {
        return NULL;
    }
    *dest = 0;
    program = realloc(program, strlen(program) + 1);
    return pairs;
}

//Executes program
int execute(struct pair *pairs) {
    unsigned char *pointer = (unsigned char*) calloc(30000, 1);
    unsigned char *leftbound = pointer, *rightbound = pointer;
    rightbound += 29999;
    for (char *pc = program; *pc; pc++) {
        switch (*pc) {
            case '<':
                if (pointer == leftbound) return 1;
                pointer--;
                break;
            case '>':
                if (pointer == rightbound) return 1;
                pointer++;
                break;
            case '+':
                (*pointer)++;
                break;
            case '-':
                (*pointer)--;
                break;
            case '[':
                while (pairs->left != pc) pairs += sizeof(*pairs);
                if (!(*pointer)) pc = pairs->right;
                break;
            case ']':
                while (pairs->right != pc) pairs -= sizeof(*pairs);
                if (*pointer) pc = pairs->left;
                break;
            case '.':
                printf("%c", *pointer);
                break;
            case ',':
                printf("Inputting 10 (for now)\n");
                *pointer = 10;
                break;
        }
    }
    return 0;
}

//Parses command line arguments, calls each function in order
int main(int argc, char *argv[]) {
    if (argc > 0) {
        char *filepath = argv[1];
        fileinput(filepath);
    }
    if (program == NULL) {
        printf("Error: File not found\n");
        return 3;
    }
    struct pair *pairs = cleanup();
    if (pairs == NULL) {
        printf("Error: Invalid program\n");
        return 4;
    }
    int execstatus = execute(pairs);
    switch (execstatus) {
        case 1:
            printf("\nError: Pointer out-of-bounds\n");
            return 1;
        case 2:
            printf("\nError: Byte overflow\n");
            return 2;
        default:
            return 0;
    }
}

Any help would be greatly appreciated.

9
  • 1
    If things happen, then for no apparent reason suddenly stop happening I think I would look for sources of undefined behavior Commented Dec 29, 2020 at 20:11
  • Yeah I'm pretty certain this is undefined behavior. I've checked for the usual suspects though, and I just can't spot where the problem might be Commented Dec 29, 2020 at 20:18
  • 1
    valgrind may help. Commented Dec 29, 2020 at 20:18
  • 2
    Compile with gcc -fsanitize=address -g and run, this should provide an immediate clue. Commented Dec 29, 2020 at 20:36
  • 2
    Everytime you increase or decrease a struct pair * pointer, you just need to do so by 1 -- the multiplication by sizeof(struct pair) happens implicitly. Commented Dec 29, 2020 at 20:37

2 Answers 2

1
    pairs += sizeof(*pairs);

Pointer arithmetic in C is always in units of the type pointed to - here, it's in units of struct pairs. So if you want pairs to point to the next struct pair in the array, add 1. (The compiler will internally translate this into adding the appropriate number of bytes, or however pointers happen to work on your system.) This line should be pairs += 1; or pairs++; or ++pairs; according to your taste.

As it stands, if sizeof(*pairs) happens to be, say, 16 on your system, you are skipping past 15 more struct pairs every time you iterate. You will end up accessing the 0th, 16th, 32nd, ... 1584th struct pair in the array. Since it only contains 100, obviously most of these will be out of bounds. Hence your segfault.

Sign up to request clarification or add additional context in comments.

Comments

1

As previously mentioned the usage of pointers is a bit messed up.

Instead of

    pairs->left = pairs->right = NULL;
    pairs += sizeof(*pairs);

Use

    pairs[x].left = pairs[x].right = NULL;

As a bonus you have pairs still intact to do the clean up

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.