Segmentation Fault with strcat

Question

Hi,

I'm having a bit of a problem with strcat and segmentation faults. The error is as follows:

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000000
0x00007fff82049f1f in __strcat_chk ()
(gdb) where
#0  0x00007fff82049f1f in __strcat_chk ()
#1  0x0000000100000adf in bloom_operation (bloom=0x100100080, item=0x100000e11 "hello world", operation=1) at bloom_filter.c:81
#2  0x0000000100000c0e in bloom_insert (bloom=0x100100080, to_insert=0x100000e11 "hello world") at bloom_filter.c:99
#3  0x0000000100000ce5 in main () at test.c:6

bloom_operation is as follows:

int bloom_operation(bloom_filter_t *bloom, const char *item, int operation)
{
    int i;    

    for(i = 0; i < bloom->number_of_hash_salts; i++)
    {
        char temp[sizeof(item) + sizeof(bloom->hash_salts[i]) + 2];
        strcat(temp, item);
        strcat(temp, *bloom->hash_salts[i]);

        switch(operation)
        {
            case BLOOM_INSERT:
                bloom->data[hash(temp) % bloom->buckets] = 1;
                break;
            case BLOOM_EXISTS:
                if(!bloom->data[hash(temp) % bloom->buckets]) return 0;
                break;
        }    
    }

    return 1;
}

The line with trouble is the second strcat. The bloom->hash_salts are part of a struct defined as follows:

typedef unsigned const char *hash_function_salt[33];
typedef struct {
    size_t buckets;    
    size_t number_of_hash_salts;
    int bytes_per_bucket;
    unsigned char *data;
    hash_function_salt *hash_salts;
} bloom_filter_t;

And they are initialized here:

bloom_filter_t* bloom_filter_create(size_t buckets, size_t number_of_hash_salts, ...) 
{
    bloom_filter_t *bloom;
    va_list args;
    int i;

    bloom = malloc(sizeof(bloom_filter_t));
    if(bloom == NULL) return NULL;

    // left out stuff here for brevity...

    bloom->hash_salts = calloc(bloom->number_of_hash_salts, sizeof(hash_function_salt));

    va_start(args, number_of_hash_salts);

    for(i = 0; i < number_of_hash_salts; ++i)
        bloom->hash_salts[i] = va_arg(args, hash_function_salt);

    va_end(args);

    // and here...
}

And bloom_filter_create is called as follows:

bloom_filter_create(100, 4, "3301cd0e145c34280951594b05a7f899", "0e7b1b108b3290906660cbcd0a3b3880", "8ad8664f1bb5d88711fd53471839d041", "7af95d27363c1b3bc8c4ccc5fcd20f32");

I'm doing something wrong but I'm really lost as to what. Thanks in advance,

Ben.

Answer 1

You need to use strlen, not sizeof. item is passed in as a pointer, not an array.

The line:

char temp[sizeof(item) + sizeof(bloom->hash_salts[i]) + 2];

will make temp the 34x the length of a pointer + 2. The size of item is the size of a pointer, and the sizeof(bloom->hash_salts[i]) is currently 33x the size of a pointer.

You need to use strlen for item, so you know the actual number of characters.

Second, bloom->hash_salts[i] is a hash_function_salt, which is an array of 33 pointers to char. It seems like hash_function_salt should be defined as:

since you want it to hold 33 characters, not 33 pointers. You should also remember that when you're passing a string literal to bloom_filter_create, you're passing a pointer. That means to initialize the hash_function_salt array we use memcpy or strcpy. memcpy is faster when we know the exact length (like here):

So we get:

typedef unsigned char hash_function_salt[33];

and in bloom_filter_create:

memcpy(bloom->hash_salts[i], va_arg(args, char*), sizeof(bloom->hash_salts[i]));

Going back to bloom_operation, we get:

char temp[strlen(item) + sizeof(bloom->hash_salts[i])];
strcpy(temp, item);
strcat(temp, bloom->hash_salts[i]);

We use strlen for item since it's a pointer, but sizeof for the hash_function_salt, which is a fixed size array of char. We don't need to add anything, because hash_function_salt already includes room for a NUL. We use strcpy first. strcat is for when you already have a NUL-terminated string (which we don't here). Note that we drop the *. That was a mistake following from your incorrect typedef.

Answer 2

I see a couple of problems:

char temp[sizeof(item) + sizeof(bloom->hash_salts[i]) + 2];

The sizeof(item) will only return 4 (or 8 on a 64-bit platform). You probably need to use strlen() for the actual length. Although I don't think you can declare it on the stack like that with strlen (although I think maybe I saw someone indicate that it was possible with newer versions of gcc - I may be out to lunch on that).

The other problem is that the temp array is not initialized. So the first strcat may not write to the beginning of the array. It needs to have a NULL (0) put in the first element before calling strcat.

It may already be in the code that was snipped out, but I didn't see that you initialized the number_of_hash_salts member in the structure.

Answer 3

Your array size calculation for temp uses sizeof(bloom->hash_salts[i]) (which is just the size of the pointer), but then you dereference the pointer and try to copy the entire string into temp.

Answer 4

Are you sure that the hash_function_salt type is defined correctly? You may have too many *'s:

(gdb) ptype bloom
type = struct {
    size_t buckets;
    size_t number_of_hash_salts;
    int bytes_per_bucket;
    unsigned char *data;
    hash_function_salt *hash_salts;
} *
(gdb) ptype bloom->hash_salts
type = const unsigned char **)[33]
(gdb) ptype bloom->hash_salts[0]
type = const unsigned char *[33]
(gdb) ptype *bloom->hash_salts[0]
type = const unsigned char *
(gdb) 

Answer 5

First, as everyone has said, you've sized temp based on the sizes of two pointers, not the lengths of the strings. You've now fixed that, and report that the symptom has moved to the call to strlen().

This is showing a more subtle bug.

You've initialized the array bloom->hash_salts[] from pointers returned by va_arg(). Those pointers will have a limited lifetime. They may not even outlast the call to va_end(), but they almost certainly do not outlive the call to bloom_filter_create(). Later, in bloom_filter_operation(), they point to arbitrary places and you are doomed to some kind of interesting failure.

Edit: Resolving this this requires that the pointers stored in the hash_salts array have sufficient lifetime. One way to deal with that is to allocate storage for them, copying them out of the varargs array, for example:

// fragment from bloom_filter_create()
bloom->hash_salts = calloc(bloom->number_of_hash_salts, sizeof(hash_function_salt));
va_start(args, number_of_hash_salts);
for(i = 0; i < number_of_hash_salts; ++i)
        bloom->hash_salts[i] = strdup(va_arg(args, hash_function_salt));
va_end(args);

Later, you would need to loop over hash_salts and call free() on each element before freeing the array of pointers itself.

Another approach that would require more overhead to initialize, but less effort to free would be to allocate the array of pointers along with enough space for all of the strings in a single allocation. Then copy the strings and fill in the pointers. Its a lot of code to get right for a very small advantage.