Indirection in the queue functions

Why is it that the queue_prepend() and queue_append() functions accept a void * parameter, while queue_dequeue() accepts a void ** item?

This is C's method of returning multiple results from a function. Remember that C only uses call-by-value, and the return keyword only returns a single type. queue_dequeue() is supposed to return true or false based on its success. It is also supposed to return a pointer to an element. It does the former with a statement like return 0;. It does the latter by taking a pointer to a location, and writing the return value to that location. As we wish to return a void *, we must pass in an void * *.

For example, let's say you have a function that is supposed to return height (which in our example is 10) and width (which in our example is 20). If you do the obvious:

int getheightwidth(int width) {
        width = 20;
        return 10;
}

int main() {
        int h = 0,w = 0;

        h = getheightwidth(w);
}

The change you made to width will not be visible to the calling routine - w will still be 0 after the call, because C uses call-by-value parameters.

You can get around this problem by passing in a pointer:

int getheightwidth(int *width) {
        *width = 20;
        return 10;
}

int main() {
        int h = 0,w = 0;

        h = getheightwidth(&w);
}

Working through an example and convincing yourself that this approach works is the best thing to do. If you have further questions, please see the course staff during one of the TA hours.

Thread setup and initialization

Queue functions and behavior

Error Reporting

What should we do about errors (in non-C jargon, "exceptions") which occur in the functions we write?

It depends on what causes the error. If it's because of bad parameters passed by the caller, or because a data structure is empty when the caller thought it was full, or some similar condition, then you should return an error code indicating what the error is, if necessary. If the error is one which the function or the caller can't deal with gracefully (memory corruption, not enough memory for a malloc, etc), then it may be better to print out as descriptive an error message as possible, and terminate the program, since the error is likely to be unrecoverable.

Assertions

What is the assert() function for? When should I use it?

assert() is for detecting mistakes and inconsistencies when you're writing and debugging code. If the condition in the assert fails, the program prints an error and dumps core (writes the contents of its memory to a file, for non-Unix people). For instance, if at at the start of function A, the value of X should be 2, and the value of Y should be 8, you could put an assert(X == 2 && Y == 8) at the top.

Asserts are useful for detecting when you made an incorrect assumption about a program invariant, or you violated the invariant elsewhere in your code. You should not really use them for catching any caller-caused errors.

Memory Management Errors in C

I seem to be getting some kind of corruption of memory pointed to by pointers. What could be the cause?

There are many causes for memory errors. We list a few common errors here, and a way to find and locate any memory error quite efficiently.

There are several common causes of memory errors:

• Using a pointer to an object on a stack frame, which is then deallocated.
• Writing past the end of an allocated structure, often caused by allocating too little memory to fit an object.
• Freeing the same object more than once.

Here's how the first case can arise in practice: you use a pointer to a local variable on the stack, which you returned from a function. For instance:

char* return_a_string(...) {
    char string[32];
    ...
    return string;
}

int main() {
    char* x = return_a_string(...);
    ...
}

This is a serious, but unfortunately common C mistake, which is often hard to spot. The problem is that a function allocates its local variables on the stack, which is shared by subsequent function invocations. The pointer x ends up pointing to some location on the stack, which may get used for some other data and overwritten by a later function invocation. Returning this kind of a pointer is even more dangerous because you might not notice the bug immediately. If in place of return_a_string we had:

then we'd have a different version of the same problem. Be aware that the problem still occurs if you store one of these pointers-to-the-stack in a data structure which gets used after the function finishes, as well. You just have to be careful.

The second case of memory errors is often caused by code like this:

struct foo { int x; int y};
typedef struct foo *foo_t;

void function(...) {
    ...
    /* this code allocates too small a space for a struct foo */
   foo_t myptr = (foo_t) malloc(sizeof(foo_t));
   myptr->y = 13; // writing past the end of allocated memory
   ...
}

Here, foo_t is a pointer to an object. The amount of memory that has to be allocated to hold a struct foo object is sizeof(struct foo). sizeof(foo_t) will always return the size of a single pointer, (4 bytes on 32-bit architectures, no matter how big the actual object might be).

Finally, if you free the same object several times, the memory allocator's internal data structures may become inconsistent, and may lead to a crash during a subsequent malloc or free. Some memory allocators will catch this kind of memory errors and alert you, especially if you build within a debug as opposed to a release environment; others might silently fail later.

Luckily, debugging memory errors is fairly straightforward most of the time. When the crash occurs, you need to identify which virtual address caused the crash. Then you need to examine the instruction at the crashed program counter to see what type of an access was performed. Then work backwards from that point to determine what kind of an inconsistency in memory is the root cause of the problem (e.g. location 0x4003fdc has an erroneous value of 0xdeadbeef stored in it, which causes a subsequent store to location 0xdeadbeef). Finally, set up a watchpoint such that you can see the value stored at that address, and perform a binary search through the program execution to find the instruction that is creating the inconsistency in the first place. For instance, stop the program halfway through to the crash to see the value stored at location 0x4003fdc. If it's not 0xdeadbeef, the memory access is occuring in the second half of the execution. Using binary search, you should be able to pinpoint the root cause of the problem in log N steps.

Some memory errors require a bit more detective work, especially if the crash is not easily reproducible or "non-deterministic" (by that, most people actually mean that the crash is triggered by external events over which they have little control, such as the timing of interrupts. But keep in mind that most crashes can be made "deterministic" with some effort. For example, recording the PC values at which interrupts occurred, and disabling interrupts at all PC's except those recorded in the crash, will often enable the deterministic reproduction of timing-related errors). Finally, it helps to do the debugging as a team.

Guard Pages

I am getting a "guard page exception" when running my system, what is the reason?

It could be because you are declaring an array as a local variable in a function, which is too big to fit on the stack. Threads have quite small stacks (about 64k). Either increase the stack size (defined by the STACKSIZE constant in minithread_md.h), or make the array smaller.

The Build

Cannot open include file: 'windows.h'

I get a linker error like:

fatal error C1083: Cannot open include file: 'windows.h': No such file or directory

How do I fix this?

Are you compiling from the command prompt? Several of the CSUGLAB machines will not build within Visual Studio, and so we recommend building from the command prompt.

syntax error : identifier 'semaphore_create'

I see the following error:

synch.c(19) : error C2016: C requires that a struct or union has at least one member
synch.c(26) : error C2061: syntax error : identifier 'semaphore_create'
synch.c(26) : error C2059: syntax error : ';'
synch.c(26) : error C2059: syntax error : ')'

What's going on?

You need to populate struct semaphore (even if you do so with a temp variable).

struct semaphore {
    int temp;
};

ml64.exe

I see the following error:

"ml64.exe /c /Zi /Zf machineprimitives_x86_64_asm.S
'ml64.exe' is not recognized as an internal or external command, operable program or 
   batch file.
NMAKE : fatal error U1077: 'ml64.exe' : return code '0x1'"

Is my Visual Studio broken?

Project 1 description has a section on how to get started. Follow these instructions, paying particular attention to configuring the Makefile.