Valgrind output, missing frees?

Question

So, working on an exercise for school, but we apparently we're leaking memory. No matter how much I stare at the valgrind output, I can't figure it out. I think we're missing 3 frees? But it also seems to suggest there's a problem in our malloc, yet the only explicit malloc comes from the code provided by our teacher. Surely that's not it? There's no line 299 either, the program ends at 239. But maybe that's because I'm working on a different pc than the one that ran valgrind.

Part of the Valgrind output:

Invalid write of size 8
    at 0x.....: enqueue
    by 0x.....: insertUnique
    by 0x.....: timeable
    by 0x.....: main
Address 0x...... is 16 bytes inside a block of size 24 free'd
    at 0x.....: free (vg_replace_malloc.c:530)
    by 0x.....: removeFirstNode
    by 0x.....: dequeue
    by 0x.....: timeable
    by 0x.....: main
Block was alloc'd at
    at 0x.....: malloc (vg_replace_malloc.c:299)
    by 0x.....: addItem
    by 0x.....: enqueue
    by 0x.....: insertUnique
    by 0x.....: timeable
    by 0x.....: main

HEAP SUMMARY
in use at exit: 72 bytes in 3 blocks
total heap usage: 31 allocs, 28 frees, 2,744 bytes allocated

24 bytes in 1 blocks are definitely lost in loss records 2 of 3
    at 0x.....: malloc (vg_replace_malloc.c:299)
    by 0x.....: addItem
    by 0x.....: addItemAtPos
    by 0x.....: addItemAtPos
    by 0x.....: addItemAtPos
    by 0x.....: insertUnique
    by 0x.....: timeable
    by 0x.....: main

48 (24 direct, 24 indirect) bytes in 1 blovks are definitely lost in loss records 2 of 3
    at 0x.....: malloc (vg_replace_malloc.c:299)
    by 0x.....: addItem
    by 0x.....: enqueue
    by 0x.....: insertUnique
    by 0x.....: timeable
    by 0x.....: main

LEAK SUMMARY
definitely lost: 48 bytes in 2 blocks
indirectly lost: 24 bytes in 1 blocks
possibly lost: 0 bytes in 0 blocks
still reachable: 0 bytes in 0 blocks
suppressed: 0 bytes in 0 blocks

Header (provided)

#ifndef QUEUES_H
#define QUEUES_H

/* First the type definitions. */

typedef struct State { /* a state contains a time and the states of the two sandglasses */
  int time;
  int sg1, sg2;
} State;

typedef struct ListNode *List;  /* List is the type of lists of states */

struct ListNode {
  State item;
  List next;
};


typedef struct Queue { /* a queue is a list and a pointer to the last node */
  List list;
  List lastNode;
} Queue;

List newEmptyList();
int isEmptyList (List li);
void listEmptyError();
List addItem(State s, List li);
void listTooShort();
List addItemAtPos(List li, State s, int p);
State firstItem(List li);
List removeFirstNode(List li);
void freeList(List li);
Queue newEmptyQueue ();
int isEmptyQueue (Queue q);
void emptyQueueError ();
void enqueue (State s, Queue *qp);
State dequeue(Queue *qp);
void freeQueue (Queue q);

 #endif

queues.c (provided)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queues.h"

/* We use the functions on lists as defined in 1.3 of the lecture notes.
 */

List newEmptyList() {
  return NULL;
}

int isEmptyList (List li) {
  return ( li==NULL );
}

void listEmptyError() {    
  printf("list empty\n");
  abort();
}

List addItem(State s, List li) {
  List newList = malloc(sizeof(struct ListNode));
  assert(newList!=NULL);
  newList->item = s;
  newList->next = li;
  return newList;
//  free(newList); maybe?
}

void listTooShort(){
    printf("List too short\n");
    abort();
}

List addItemAtPos(List li, State s, int p){
    if (p ==0){
        return addItem(s,li);
    }
    if (li == NULL){
        listTooShort();
        //addItem(s, li);
    }
    li->next =addItemAtPos(li->next, s, p-1);
    return li;
}


State firstItem(List li) {
  if ( li == NULL ) {
    listEmptyError();
  }
  return li->item;
}

List removeFirstNode(List li) {
  List returnList;
  if ( li == NULL ) {
    listEmptyError();
  }
  returnList = li->next;
  free(li);
  return returnList;
}

void freeList(List li) {
  List li1;
  while ( li != NULL ) {
    li1 = li->next;
    free(li);
    li = li1;
  }
  return;
}


/* We define some functions on queues, based on the definitions in 1.3.1 of the
 * lecture notes. Integers are replaced by states, and enqueue has output type void here.
 */

Queue newEmptyQueue () {
  Queue q;
  q.list = newEmptyList();
  q.lastNode = NULL;
  return q;
}

int isEmptyQueue (Queue q) {
  return isEmptyList(q.list);
}

void emptyQueueError () {
  printf("queue empty\n");
  exit(0);
}

void enqueue (State s, Queue *qp) {
  if ( isEmptyList(qp->list) ) {
    qp->list = addItem(s,NULL);
    qp->lastNode = qp->list;
  } else {
    (qp->lastNode)->next = addItem(s,NULL);
    qp->lastNode = (qp->lastNode->next);
  }
}

State dequeue(Queue *qp) {
  State s = firstItem(qp->list);
  qp->list = removeFirstNode(qp->list);
  if ( isEmptyList(qp->list) )  {
    qp->lastNode = NULL;
  }
  return s;
}

void freeQueue (Queue q) {
    freeList(q.list);
}

and finally our own code (which is probably horribly messy, sorry. Compiled with -std=c99 -Wall *.c in a map containing the only the previous codes):

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queues.h"

void printState(State s){
    printf("\tsg1\t\tsg2\n");
    printf("\t%d\t\t%d\n", s.sg1, s.sg2);
    printf("\t\tt=%d\n", s.time);
    printf("------------------------------------------\n");
}

/* The function action generates a new state from an existing state.
 */
State action(State s, int actionType, int cap1, int cap2 ) { 
    State res;

    res.time = s.time;
    res.sg1 = s.sg1;            /* sg1 & sg2 are original values/previous state */
    res.sg2 = s.sg2;

    if (res.sg1  <= res.sg2 ){  /* A is smaller or equal to B */ 
        if (res.sg1 != 0) { 
            res.sg2 -= res.sg1 ;
            res.time += res.sg1 ;
            res.sg1 = 0;
        } else { 
            res.time +=res.sg2;
            res.sg2 = 0;
        }
        //printf("next time point A<B: time=%d res.sg1=%d res.sg2=%d\n\n", res.time, res.sg1, res.sg2);
    } else {                    /* A is bigger than B */
        if (res.sg2 != 0) { 
        res.sg1 -= res.sg2;
        res.time += res.sg2;
        res.sg2 = 0;
    } else { 
        res.time += res.sg1;
        res.sg1 = 0;
    }
        //printf("next time point A>B: time=%d res.sg1=%d res.sg2=%d\n\n", res.time, res.sg1, res.sg2);
    }

    switch(actionType){
        case 1:             /* flip A */
        res.sg1 = cap1 - res.sg1; 
        break;  
        case 2:             /* flip B */
        res.sg2 = cap2 - res.sg2;
        break; 
        case 3:             /* flip A&B */
        res.sg1 = cap1 - res.sg1;
        res.sg2 = cap2 - res.sg2;
        break;
        case 4:             /* do nothing */
        res.sg1 = res.sg1;
        res.sg2 = res.sg2;
        break;
    }
    //printf("state after action %d:\n", actionType); 
    //printState(res);

    return res;
}

int compare(State a, State b){ /*Return -1 if a < b, 0 if a==b, +1 if a > b*/
    if(a.time < b.time){
        return -1;
    }
    if(a.time > b.time){
        return 1;
    }

    if(a.sg1 < b.sg1){
        return -1;
    }
    if(a.sg1 > b.sg1){
        return 1;
    }
    if(a.sg2 < b.sg2){
        return -1;
    }
    if(a.sg2 > b.sg2){
        return 1;
    }
    return 0;
} 

int findPos(State s, List li){
    int pos = 0;
    /*
    if(isEmptyList(li)){
        //printf("List Empty\n");
        return pos;
    }
    */
    while(li != NULL){

        int com = compare(li->item, s);
        if (com == 0){
            return -1; 
        }
        if (com == 1){
            return pos;
        }
        pos+=1;
        li=li->next;
    }
    return pos;
}

void insertUnique(State s, Queue *q){
    int pos = findPos(s, q->list);
    //printf("Inserting new state at pos %d\n", pos);
    //printState(s);
    if(pos == 0){
        enqueue(s, q);
    }else if(pos != -1){ /*-1 is value for duplicate*/

        addItemAtPos(q->list, s, pos);
        //listPrinter(q->list);
    } 
    if(pos == -1){
        //printf("DENIED A STATE FOR DUPLICATE\n");
    }
}

int isCorrect(State act, int goalTime){
    if(act.time == goalTime ) return 1;
    return 0;
}

int isValidAction(State act, State curr, int action, int goalTime){
    if(act.time > goalTime) return 0;
    if(curr.sg1==0 && curr.sg2 == 0 && action == 4){
        return 0;
    }
    return 1;
}

/* The function timeable checks whether a given time can be determined
 * exactly by two sandglasses with given capacities.
 */
int timeable(int cap1, int cap2, int goalTime   ) { 
  /* Should probably make a queue of lists, where each list in the queue is a list of possible actions with the following state */
    /*Queue q = newEmptyQueue();*/  /* This mgiht work */
    if(goalTime == 0){
        return 1;
    }
    State begin;        /* Maybe change to global but idk */
    begin.time = 0;
    begin.sg1 = cap1;
    begin.sg2 = cap2;
    //printf("begin:\n");
    //printState(begin);
    Queue q = newEmptyQueue();
    enqueue(begin, &q); /*Enqueue begin because less code dupe*/
    //free(begin);
    while(1){ /*No end for while because there SHOULD always be a return*/
        if(isEmptyQueue(q)){
            //printf("QUEUE IS EMPTY\n");
            freeQueue(q);

            return 0;
        }
        State curr = dequeue(&q);

        for(int i=1; i<=4; i++){
            State act = action(curr, i, cap1, cap2);
            if (isCorrect(act, goalTime)){      /**TODO**/
                freeQueue(q);
                return 1;
            } 
            if(isValidAction(act, curr, i, goalTime)){ /**TODO**//*Anything larger than queue isn't worth computing*/
                //printf("ENQUEUEING FOR ACT %d\n", i);
                //printState(act);
                insertUnique(act, &q); /** Is action working?**/
            }
        }
    }
}

/* main performs a dialogue with the user. The user is asked to provide three numbers: 
 * the (positive) capacities of the sandglasses and the goal time (>= 0).
 * The program indicates whether the goal time can be determined exactly. 
 * The dialogue is ended by the input '0'.
 */

int main(int argc, char *argv[]){
  int cap1, cap2, goalTime;  
  printf("give the sandglass capacities and the goal time: ");
  scanf("%d",&cap1);
  while ( cap1 > 0 ) {
    scanf("%d",&cap2);
    assert( cap2 > 0 );
    scanf("%d",&goalTime);
    assert( goalTime >= 0 );

    if ( timeable(cap1, cap2, goalTime) ) {
      printf("%d and %d can time %d\n", cap1, cap2, goalTime);
    } else {
      printf("%d and %d cannot time %d\n", cap1, cap2, goalTime);
    }
    printf("\ngive the sandglass capacities and the goal time: ");
    scanf("%d",&cap1);
  }  
  printf("good bye\n");
  return 0;
}

I'd be very grateful if you could help me spot the problem, we're kind of noobs at this. Or maybe explain what the valgrind messages actually mean? Most posts I've seen seem to go wrong with the malloc (using sizeof(int) for a pointer, for instance) but as far as I can see that's not the case here. And what's the differene between direct and indirect loss? Regardless of that, is there a part that is horribly inefficient? It takes quite long for larger values (11 39 10000 for example).

Answer 1

Or maybe explain what the valgrind messages actually mean?

Valgrind has good documentation that covers this and much more. In short:

An "invalid write" message means you've attempted to write to memory that is not presently allocated to your program. In your particular case, valgrind complains that you're writing to a block of memory after it was freed.

A "blocks are definitely lost" message means that you have a memory leak. At the end of the program there is allocated memory that is impossible to reach via any chain of pointers. A block is "directly" lost if no pointers to that block remain. A block is "indirectly" lost if there remain pointers, but all of those themselves reside in unreachable blocks.

In either case, the line numbers reported in your particular loss records refer to a file in Valgrind's own implementation, as you can tell from the provided file name.

HOWEVER, all of that seems moot, because I cannot reproduce the memory problems in my environment with the code and input you've presented, and I don't see any reason to think that I should be able to do.

Regardless of that, is there a part that is horribly inefficient?

Your algorithm explores the entire region of the system's state space for which the elapsed time does not exceed the target time. I presume that is the intention. Nevertheless, you have O(cap1 * cap2 * goalTime) states to search, and in order to avoid redundant computations, you search the queue's contents when adding each state. That appears to be the most costly step, resulting on an overall bound of O(cap1² * cap2² * goalTime²). Of course, that's only an upper bound, there can be inputs that run a lot quicker than the upper bound.

On the other hand, yes, there are some gross inefficiencies. In particular, insertUnique() does about twice as much work as it needs to do, because it iterates through the list to find an insertion position (findPos()), and then iterates through it again to perform the actual insertion (addItemAtPos()). There might be some other minor efficiencies to be gained, but nothing of the same scope.

Moreover, you're making things more complicated than they need to be by using a queue, because you're not using it as a queue. You're instead using the queue implementation's internal list, as a list. This presents two sorts of problems:

• If the exercise requires you to perform the task using a queue, then your approach would not get full marks from me because you're primarily relying on list operations, not queue operations. It is possible to perform your de-duplication with queue operations, but it requires two queues.

• If the exercise allows you to use a list instead of a queue, then your approach still would not get full marks from me (though it would do better than in the other case), because it's unclear to me whether you in fact understand that you're using a list as opposed to a queue.

---

Note also: the structure of the exercise, in particular the inefficiencies you're struggling with, seems like an ideal lead up to introduction of a new data structure: the priority queue. That would be a better choice for this problem than a plain queue.

Answer 2

You need to address the first error ("Invalid write of size 8") before you start investigating any leaks. This diagnostic is an error -- it indicates that your program is attempting to write to memory that has already been freed. This may actually be responsible for some of the leaks that are reported later.

The only line numbers mentioned in the Valgrind output are relative to vg_replace_malloc.c. This file is internal to Valgrind; what matters are the stack frames above it. To get line numbers in your code, you will need to compile your code with debug symbols -- add the -ggdb compiler option and rebuild your application.