Please help me figure out malloc issue

Question

I have a project to write cache simulation in C and so far i am stuck on allocating space for an array and program crashes. Please help me out. I have to use pointers in this program. When i had array simply created in the main function, there were no problems, but after making a pointer to in global, program started to crash and i have to have it global. Its one of the requirements.

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

int INDEXLENGTH; // global variable for num of bits in index
int OFFSETLENGTH; // global variable for num of bits in byte offset
int TAGBITS; // global variable for num of bits in the tag
int misses=0; //variable for total number of misses
int hits=0;
int **tagAr; // LRUArray pointer
int **lruAr; // tagArray pointer
int cacheSize; // user specified size of cache
int blockSize; // user specified size of each block
int linesperset;
int sets;

int main(void)
{
    int i; // simply a few variables for future for loops
    int j;

    printf("Welcome to Lab A Cache Simulator by Divya, Alex and Jenn.\n");
    printf("To begin, please input the size of the cache you will be simulating in bytes.\n");
    scanf(" %d", &cacheSize); // (cache size in bytes) is read in from the user
    printf("You have inputed this: %d\n", cacheSize);

    printf("Next, please input the size of each cache line in bytes.\n");
    scanf(" %d", &blockSize); // blocksize is read in from the user
    printf("You have inputed this: %d\n", blockSize);

    printf("Finally, please input the number of ways of associativity for this cache.\n");
    printf("Also, input the number as a power of 2.\n");
    scanf(" %d", &linesperset); // linesperset is read in from the user
    printf("You have inputed this: %d\n", linesperset);

    sets = (cacheSize/(blockSize*linesperset));
    printf("Variable sets is: %d\n", sets);


    tagAr=(int **)malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) tagAr[i]=(int *)malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]

    lruAr=(int **)malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) lruAr[i]=(int *)malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]


    for (i=0; i<sets; i++)
        {
            for (j=0; j<blockSize; j++)
            {
                tagAr[i][j] = -1;
                lruAr[i][j] = -1;
            }
        }

    for (i = 0; i < sets; i++) //This part of the code prints array for debuging purposes
        {
            for (j = 0; j < blockSize; j++)
            {
                printf(" %d", lruAr[i][j]);
            }
            printf("\n");
            printf("\n");
        }

    printf("This is the value of IndexLength before setting, should be 0 : %d\n", INDEXLENGTH); //only for debuging purposes
    setIndexLength();
    printf("This is the value of IndexLength after setting: %d\n", INDEXLENGTH); //only for debuging purposes
    printf("This is the value of OffsetLength before setting, should be 0 : %d\n", OFFSETLENGTH); //only for debuging purposes
    offsetLength();
    printf("This is the value of OffsetLength after setting: %d\n", OFFSETLENGTH); //only for debuging purposes





    return misses;
}

Answer 1

You have a typo, in the code below you set tagAr[i] twice and never set lruAr[i];

    tagAr=(int **)malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) tagAr[i]=(int *)malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]

    lruAr=(int **)malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) tagAr[i]=(int *)malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]

That second tagAr[i] assignment should be to lruAr[i].

So, this is what you want:

    tagAr=malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) tagAr[i]=malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]

    lruAr=malloc(sets*sizeof(int *)); // allocating space for "l" array pointers
    for (i=0; i<sets; i++) lruAr[i]=malloc(linesperset*sizeof(int)); //allocates space for k columns for each p[i]

Answer 2

This isn't really an answer but rather a follow-up to Pankrates' very good suggestion.

If you run the program under valgrind (after compiling it with debug information and no optimizations, just to be safe)

$ gcc -O0 -g -o test.o -W -Wall test.c   # Compile

$ valgrind ./test.o     # run simple Valgrind

you get:

==26726== Use of uninitialised value of size 8
==26726==    at 0x4008C5: main (test.c:54)
==26726==
==26726== Invalid write of size 4
==26726==    at 0x4008C5: main (test.c:54)
==26726==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==26726==
==26726==

which tells you that in the source file, at line 54, you are writing to an uninitialized variable. Something you did not allocate. Valgrind tells you what and where. To discover the why, the line is:

lruAr[i][j] = -1;

so you check where you allocated lruAr (valgrind says it's not allocated!), and you quickly find out what looks like a copy-and-paste bug:

for (i=0; i)malloc(linespersetsizeof(int)); //allocates space for k columns for each p[i]

tagAr=(int **)malloc(sets*sizeof(int *));
for (i=0; i<sets; i++) {
    tagAr[i]=(int *)malloc(linesperset*sizeof(int)); // <-- ORIGINAL LINE
}

lruAr=(int **)malloc(sets*sizeof(int *));
for (i=0; i<sets; i++) {
    tagAr[i]=(int *)malloc(linesperset*sizeof(int)); // <-- THE COPY ("tagAr"?)
}

The fix is the one described by Charlie Burns.

Valgrind can help you do much more than this, and will help you intercept much subtler bugs - bugs that are not so kind as to crash your application immediately and reproduceably.

For the same reason, do not use casts (or do so only as a last resort). By casting, you are telling the compiler "I know better". Truth is, the compiler usually knows better than you and me and mostly everybody else. By not using casts, you let it stand up and speak whenever you unwittingly do something suspicious, rather than go on dumbly and do what you told it to do instead of what you meant it to do.

(Sorry for the long and patronizing rant. But I got bitten so many times, I thought maybe I might save you some skin :-) )

Update

"Still crashes". Okay, so we run valgrind again after updating the source, and this times we get

==28686== Invalid write of size 4
==28686==    at 0x4008B8: main (test.c:54)
==28686==  Address 0x51e00a0 is 0 bytes after a block of size 16 alloc'd
==28686==    at 0x4C2C27B: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==28686==    by 0x4007F3: main (test.c:43)
==28686==
==28686== Invalid write of size 4
==28686==    at 0x4008E2: main (test.c:55)
==28686==  Address 0x51e0190 is 0 bytes after a block of size 16 alloc'd
==28686==    at 0x4C2C27B: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==28686==    by 0x400852: main (test.c:46)

Notice: we are writing 0 bytes after a block. This means we have a buffer overrun: we did allocate an array, but it is too small. Or our write is too large.

The array was allocated at lines 43 and 46 (the two cycled mallocs) and is written here:

            tagAr[i][j] = -1;
            lruAr[i][j] = -1;

...so this means that tagAr[i] has a width, but blockSize is bigger.

This might be due to me inserting nonsensical data, so you'd have to check yourself. But it is apparent that you alloc linesperset elements, and write blockSize of them. At the very least, blockSize must never be allowed to exceed linesperset.

Finally

The code below passes valgrind tests. I have also added a check that the memory has indeed be allocated: it is almost always unnecessary, and without it, the program will almost never crash and coredump. If almost never and shouldn't aren't good enough for you, you'll better check.

// allocating space for "l" array pointers
tagAr=malloc(sets*sizeof(int *));
lruAr=malloc(sets*sizeof(int *));

if ((NULL == tagAr)||(NULL == lruAr)) {
    fprintf(stderr, "out of memory\n");
}

for (i=0; i < sets; i++) {
    tagAr[i] = malloc(linesperset*sizeof(int));
    lruAr[i] = malloc(linesperset*sizeof(int));
    for (j=0; j < linesperset; j++) {
         tagAr[i][j] =
         lruAr[i][j] = -1;
    }
}

For the same reason, even if many call it being paranoid and anal-retentive, and modern garbage collecting languages laugh at it, it is a good habit to free every allocated pointer once you're done, and set it to NULL for good measure (not to prevent loitering - but to ensure you're not using an obsoleted value somewhere).

// To free:
for (i=sets; i > 0; ) {
    i--;
    // To be really sure, you might want to bzero()
    // lruAr[i] and tagAr[i], or better still, memset()
    // them to an invalid and easily recognizable value.
    // I usually use 0xDEADBEEF, 0xDEAD or 0xA9.
    free(lruAr[i]); lruAr[i] = NULL;
    free(tagAr[i]); tagAr[i] = NULL;
}
free(lruAr); lruAr = NULL;
free(tagAr); tagAr = NULL;

(The above practices, including the 0xA9 value, from Writing Solid Code).