Error Reading Variable, Cannot Access Memory at Address X

Question

Probably just another silly pointer issue from a C newbie. Couldn't figure this one out though. It seems that somehow my stack frame is corrupted. The assignment seems mostly irrelevant, but it's a fairly basic I/O exercises. Attempting to read in an array of structures with a single read (cannot use advanced I/O functions such as fread()).

#include "A2_Phase2.h"

void read_directory(Cdir directory[], int cnt) 
{
    int fd;
    char filename[] = "RandomStructDir.bin";

    fd = open(filename, O_RDONLY, S_IRWXU);
    if (fd < 0)
        perror(strcat(filename, " failed to open."));

    if (read(fd, &(directory[0].code[0]), sizeof(Cdir) * cnt) < 0) {
        perror(strcat(filename, " could not be accessed."));
    }

    close(fd);
}

int binary_search(Cdir directory[], char *key, int l, int r) {

    int mid = (int) r / 2;

    if (strncmp(key, directory[mid].code, 3) < 0)
        return binary_search(directory, key, l, mid - 1);
    else if (strncmp(key, directory[mid].code, 3) > 0)
        return binary_search(directory, key, mid + 1, r);
    else
        return mid;
}

int main(int argc, char *argv[]) 
{
    int COUNTRY_COUNT = atoi(argv[1]);
    printf("%d", COUNTRY_COUNT);

    Cdir *directory = (Cdir *) malloc(sizeof(Cdir) * COUNTRY_COUNT);
    read_directory(directory, COUNTRY_COUNT);
    binary_search(directory, "ZWE", 0, 238);
    free(directory);
}

I receive this error via GDB:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400940 in binary_search (
    directory=<error reading variable: Cannot access memory at address 0x7fffff7feff8>, 
    key=<error reading variable: Cannot access memory at address 0x7fffff7feff0>, l=<error reading variable: Cannot access memory at address 0x7fffff7fefec>, 
    r=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>)
    at A2_Phase2.c:19
19  int binary_search(Cdir directory[], char *key, int l, int r) {

Thanks!

You should not cast the result of malloc – Eregrith Jan 23 '13 at 16:51 — Eregrith, Jan 23 '13 at 16:51
Why is this? Would love to know. – user2004672 Jan 23 '13 at 17:25 — user2004672, Jan 23 '13 at 17:25
http://stackoverflow.com/questions/605845 – Eregrith Jan 24 '13 at 08:09 — Eregrith, Jan 24 '13 at 08:09

simonc · Accepted Answer · 2013-01-23T19:09:10.490

5

int COUNTRY_COUNT = atoi(argv[1]);

reads the number of countries as an argument to the program but you later hard-code the assumption that this is >= 238 when you call

binary_search(directory, "ZWE", 0, 238);

Can you try

binary_search(directory, "ZWE", 0, COUNTRY_COUNT-1);

instead? There are also a few errors in your binary_search function which could be re-written as

int binary_search(Cdir directory[], const char *key, int l, int r)
{
    int mid = (r + l) / 2;
    int cmp = strncmp(key, directory[mid].code, 3);
    if (l >= r) {
        if (cmp == 0)
            return l;
        return -1;
    }
    if (cmp < 0) 
        return binary_search(directory, key, l, mid - 1);
    else if (cmp > 0)
        return binary_search(directory, key, mid + 1, r);
    else
        return mid;
}

The main changes are

calculation of mid takes account of l as well as r
(as noted by Kirilenko) recognise that its possible to find no match. return -1 in this case
reduce number of calls to strcmp. Very minor but it makes the code clearer to me and will improve performance of searches

Less importantly, there are some stylistic issues that make your code hard to read

Masses of unnecessary whitespace inside functions
Use of upper case (e.g. COUNTRY_COUNT) for variables is unusual. All upper case is often informally reserved for defines with variables using lower or camelCase

edited Jan 23 '13 at 19:09

answered Jan 23 '13 at 16:41

simonc

41,632
12
85
103

Thank you for all of the recommendations. I did apply them, although I am still getting the same segfault as it occurs as the binary_search function is being called, not within it. – user2004672 Jan 23 '13 at 17:24
@user2004672 Does the segfault occur the first time you call `binary_search` or at the end of a very long chain of calls? If it happens at the end of a long chain, you may be overflowing the stack, which would be an indication that the binary search algorithm was incorrect. – simonc Jan 23 '13 at 17:29
@user2004672 It would also be worth checking that you have precisely followed all suggestions. I suspect you haven't followed my code exactly - I just noticed that it wouldn't have compiled. (Now fixed) – simonc Jan 23 '13 at 17:31
1

If `l` and `r` are both supposed to be valid indices into the array, then binary_search() should probably initially be called with `COUNTRY_COUNT-1` as the larger argument. – JasonD Jan 23 '13 at 17:35
1

If I can suggest one more fix, I would check for `l >= r` rather than just `==`, as the values could overlap if the key is not found. – JasonD Jan 23 '13 at 17:40
I did not follow your suggestion exactly - I corrected the obvious errors (such as the improper comparison). The problem IS with the binary search method as it segfaults very deep into the recursion tree. Currently looking into any logic issues. – user2004672 Jan 23 '13 at 18:53
Just discovered the issue and applied all of the changes recommended by you guys. Thanks! (Also am taking into account your critique on my coding style - thanks for that as well). – user2004672 Jan 23 '13 at 19:02
@JasonD I'm not doing terribly well here... I can't immediately see when the values would overlap but I'm sure you're right. Changed as suggested. – simonc Jan 23 '13 at 19:10
1

@simonc If `l=0` and `r=1`, then `mid` will be 0. If the non-existent key is less than the lowest value in the array, it will search again to the left, using `r = mid - 1`, which is `-1` – JasonD Jan 23 '13 at 19:57
@user2004672 Glad you got it working. If my eventual answer didn't work for you, it'd be worth posting your code as an answer and accepting that. – simonc Jan 23 '13 at 20:54

JasonD · Answer 2 · 2013-01-23T17:47:18.100

int mid = (int) r / 2;

Really? I think you'll find that's not the mid point. Also, as pointed out elsewhere, there is no termination case if the value is not found. You need to think through how the recursion will work for different inputs, including invalid ones.

I would do it something like this:

int binary_search(Cdir directory[], char *key, int l, int r)
{
    int mid = (l+r) / 2;
    int c = strncmp(key, directory[mid].code, 3);

    if(c == 0) return mid;
    if(l>=r) return -1;

    if (c < 0)
        return binary_search(directory, key, l, mid - 1);

    return binary_search(directory, key, mid + 1, r);
}

Also this:

char filename[] = "RandomStructDir.bin";

fd = open(filename, O_RDONLY, S_IRWXU);
if (fd < 0)
    perror(strcat(filename, " failed to open."));

filename[] is a fixed length array on the stack. You try to concatenate onto it when an error occurs. That could just cause a more serious error, as it's undefined behaviour - you're trashing the stack.

Thank you, this knowledge is very useful. Interestingly enough, my professor provided this example of error handling... — user2004672, Jan 23 '13 at 17:26
@user2004672 writing `perror(strcat(filename, " could not be accessed."));` is idiotic, professor or no professor. — AndersK, Jan 23 '13 at 17:53

score 0 · Answer 3 · answered Jan 23 '13 at 16:41

0

In your recursive function, I can't see any terminaison case if there is no matching element.

answered Jan 23 '13 at 16:41

md5

23,373
3
44
93

score 0 · Answer 4 · answered Jun 15 '16 at 08:18

0

my stack frame is corrupted

Looks very much like you declared a variable that is too large for the stack. Instead of

int largeArray[1000][1000];

declare it as a pointer

int *largeArray[1000][1000];

Of course changes in the code are necessary.

answered Jun 15 '16 at 08:18

Michał Leon

2,108
1
15
15

Error Reading Variable, Cannot Access Memory at Address X

4 Answers4