Queue using doubly linked list in c - program is killed when I am using large number of operations

Question

I wrote the following code and run it on Ubuntu. It works fine when the size is up to 2048X2048(I need powers of 2 ). But when the size is 4096X4096 the program is killed. There is no memory leak when the sizes are 512X512, and when I try running it via valgrind with larger sizes the program is also killed.

Why?

#define SIZE_X 2048
#define SIZE_Y 2048

unsigned long long int counter =0;

struct task{

    int x,y,dx,dy;

};

typedef struct task* Task;

struct node{

    Task data;
    struct node* next, *prev;

};

typedef struct node* Node;

struct queue{

    Node head, tail;
};

typedef struct queue* Queue;

Queue tasksQueue =NULL;

void enqueue(Task t){

    assert(t!=NULL);
    Node node = (Node)malloc(sizeof(struct node));
    assert(node!=NULL);
    node->data = t;
    node->next = NULL;
    node->prev = NULL;  
    if(tasksQueue==NULL){

        tasksQueue =(Queue)malloc(sizeof(struct queue));
        assert(tasksQueue!=NULL);
        tasksQueue->head = node;
        tasksQueue->tail = node;
        return;

    }
    else if(tasksQueue->head == NULL && tasksQueue->tail == NULL){

        tasksQueue->head = node;
        tasksQueue->tail = node;
        return;

    }
    assert(tasksQueue->head != NULL && tasksQueue->tail != NULL);       
    tasksQueue->tail->next = node; 
    node->prev =tasksQueue->tail;
    tasksQueue->tail = node;    
    assert(tasksQueue->head!=NULL);
}

Task dequeue(){
    if(tasksQueue==NULL){

        return NULL;
    }
    else if(tasksQueue->head==NULL && tasksQueue->tail==NULL){
        return NULL;
    }
    assert(tasksQueue->head!=NULL && tasksQueue->tail!=NULL);
    Task tempT = tasksQueue->head->data;
    assert( tempT !=NULL);  
    Node tempN = tasksQueue->head;
    assert( tasksQueue->tail->next==NULL);  
    if(tasksQueue->head->next==NULL){   
        tasksQueue->head = NULL;
        tasksQueue->tail = NULL;
    }
    else{
        tasksQueue->head->next->prev =NULL;
        tasksQueue->head = tasksQueue->head->next;

    }   
    free(tempN);
    tempN = NULL;       
    return tempT;   
}


void executeTask(Task t){

    assert(t!=NULL);       
    if(t->dx ==1 && t->dy ==1){

        counter++;
        free(t);
        t=NULL;
    }
    else{   

        Task t1 = (Task)malloc(sizeof(struct task));
        Task t2 = (Task)malloc(sizeof(struct task));
        Task t3 = (Task)malloc(sizeof(struct task));
        Task t4 = (Task)malloc(sizeof(struct task));
        assert(t1!=NULL);
        assert(t2!=NULL);   
        assert(t3!=NULL);   
        assert(t4!=NULL);                       
        t1->x = t->x;
        t1->y = t->y;
        t1->dx = t->dx/2;
        t1->dy = t->dy/2;
        t2->x = t1->x + t1->dx;
        t2->y = t1->y ;
        t2->dx = t1->dx;
        t2->dy = t1->dy;
        t3->x = t1->x;
        t3->y = t1->y + t1->dy;
        t3->dx = t1->dx;
        t3->dy = t1->dy;
        t4->x = t1->x + t1->dx;
        t4->y = t1->y + t1->dy;
        t4->dx = t1->dx;
        t4->dy = t1->dy;
        free(t);
        t=NULL;

        enqueue(t1);
        enqueue(t2);
        enqueue(t3);
        enqueue(t4);    
        }
}

int main(){
    int i;
    Task t0 = (Task)malloc(sizeof(struct task));
    assert(t0!=NULL);                   
    t0->x = 0;
    t0->y = 0;
    t0->dx = SIZE_X;
    t0->dy = SIZE_Y;    
    enqueue(t0);

    while(counter<SIZE_X*SIZE_Y){
        if(counter%1000000==0 && counter!=0){   
            printf("counter is:%llu\n",counter);
            printf("another 1000000 done\n");
        }
        Task t = dequeue();         
        if(t!=NULL){    
            executeTask(t);     
        }
    }
}

Looks like memory starvation: http://stackoverflow.com/questions/726690/who-killed-my-process-and-why — Jiminion, May 13 '14 at 18:25
You need more memory! You can track it using top and see how big it gets before failing. — Jiminion, May 13 '14 at 18:54

score 0 · Answer 1 · answered May 13 '14 at 18:12

0

Check memory limits via ulimit -a. Check rss/data segment/stack limit sizes. Try to increase them one by one and check if your program works. Changing limits in /etc/security/limits.conf may require relogining. Also greping system logs may show you something interesting.

answered May 13 '14 at 18:12

I don't know these methods. I'm a student. Do you think that using a circular array instead of a doubly linked list will work OK? – user3553583 May 13 '14 at 19:14
If I'm right - then no - nothing will help you, as this memory limit is forced by OS kernel. If this limits is a reason of this behavior - your only solution is to increase limits or try run code from other user(more privileged). – May 13 '14 at 19:18
You both were wright. thanks. It worked from a different computer. – user3553583 May 13 '14 at 19:57

Queue using doubly linked list in c - program is killed when I am using large number of operations

1 Answers1