• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
blueshogun96

Linked List Node Corruption Problem

3 posts in this topic

I have this linked list code that I've been using for quite some time now, but until my latest project, it's been giving me some rare but random crashes. So far, I haven't been able to track down the problem but I did find a way to replicate it (at least I think so).  This is a C-based linked list, and yes, my game is written in pure C.

 

What's happening is (from what I understand) that in rare instances, when iterating through the linked list, the current "node" pointer will have a bogus memory address.  Here's an example:

 

void update_smoke()
{
    struct node_t* n = smoke;
    
    if( !smoke )
        return;
    
    while( n != NULL )
    {
        struct smoke_t* s = n->data;
        
        if( s != NULL )
        {
            /* */
            if( ++s->timer > s->anim_speed )
            {
                s->frame++;
                s->timer = 0;
                if( s->frame >= s->max_frame )
                {
                    set_deletion_callback( delete_smoke_func );
                    list_delete( &smoke, s );
                    s = NULL;
                }
            }
        }
        
        n = n->next;
    }
}

 

This is how I iterate through my linked lists, and I'm currently managing several of them.  As I mentioned, I rarely run into problems with it, but when I do, the problem is almost a complete mystery to me.

 

Let's say smoke is located at 0x000000010008efd3.  The first iteration around, the temporary pointer n will be located in the same location.  If/when this does crash, then when I check the location of n, It's usually the same address with an offset (i.e. 0xd00000010008efd3).  It's always an address absurdly higher than what I originally started with.  This only occurs in loops where I am deleting nodes.  

 

This problem always occurs when I am deleting a node from two lists in the same loop.  To work around this, I just set a flag to remove the node later in another pass.  My assumption is that the same problem is what's causing random crashes.  These crashes are so rare and unpredictable, they're hard to track.  This one function is a perfect example.

 


void check_missiles_for_collisions()
{
    struct node_t* n = enemies;
    
    if( !enemies )
        return;
    
    if( !missiles )
        return;
    
    /* Go through the entire list of enemies and check for collisions with the missile */
    
    while( n != NULL )
    {
        struct enemy_t* e = n->data;
        
        if( e != NULL )
        {
            float x1 = e->x-(e->w/2.0f);
            float y1 = e->y-(e->h/2.0f);
            float x2 = e->x+(e->w/2.0f);
            float y2 = e->y+(e->h/2.0f);
            
            struct node_t* mn = missiles;
            
            while( mn != NULL )
            {
                struct missle_t* m = mn->data;
                
                if( m != NULL )
                {
                    if( m->x > x1 && m->x < x2 &&
                       m->y > y1 && m->y < y2 )
                    {
                        /* Subtract the damage and check for a kill */
                        e->energy -= 5;
                        
                        if( e->energy < 1 )
                        {
                            /* If so, delete this enemy, it's spline, and add an explosion */
                            /* Also, add it's score value to the user's score */
                            user.score += e->score_value;
                            add_explosion( e->x, e->y, No );
                            
                            /* Add a small crystal */
                            add_new_crystal( e->x, e->y, Yes );
                            
                            set_deletion_callback( enemy_delete_func );
                            list_delete( &enemies, e );
                            e = NULL;
                        }
                        
                        /* Go ahead and delete this missile too */
            //            set_deletion_callback( missile_deletion_func );
            //            list_delete( &missiles, m );
            //            m = NULL;
                        m->was_used = Yes;
                        
                        break;
                    }
                }
                
                mn = mn->next;
            }
        }
        
        n = n->next;
    }
}

 

 

Note where I commented out the part where I delete the missile.  If I uncomment this, it will crash later on down the line somewhere, somehow.  Once again, I have no idea what's causing this.  Apparently, ignoring the problem and using a workaround was NOT a good idea as this is a prime example of how an isolated problem can evolve into a cancer in your game engine.

 

If it helps, I'm using XCode 4.5.2 (Apple's LLVM compiler) under MacOSX Lion.  I assume the problem will remain the same under Windows.  Somehow, I assume the current node or the next pointer is getting corrupted.

 

For those who want to see the linked list code, here it is:

#include <stdio.h>
#include <stdlib.h>
#include "linkedlist.h"


/* linked list head */
//struct node_t* head = NULL;

/* Deletion callback function */
void (*delete_func)(void*);


/* Add a node at the beginning of the list */
void list_add_beginning( struct node_t** head, void* data )
{
	struct node_t* temp;

	temp = ( struct node_t* ) malloc( sizeof( struct node_t ) );
	temp->data = data;

	if( (*head) == NULL )
	{
		(*head) = temp;
		(*head)->next = NULL;
	}
	else
	{
		temp->next = (*head);
		(*head) = temp;
	}
}

/* Add list node to the end */
void list_add_end( struct node_t** head, void* data )
{
	struct node_t* temp1;
	struct node_t* temp2;

	temp1 = (struct node_t*) malloc( sizeof( struct node_t ) );
	temp1->data = data;

	temp2 = (*head);

	if( (*head) == NULL )
	{
		(*head) = temp1;
		(*head)->next = NULL;
	}
	else
	{
		while( temp2->next != NULL )
			temp2 = temp2->next;

		temp1->next = NULL;
		temp2->next = temp1;
	}
}

/* Add a new node at a specific position */
void list_add_at( struct node_t** head, void* data, int loc )
{
	int i;
	struct node_t *temp, *prev_ptr, *cur_ptr;

	cur_ptr = (*head);

	if( loc > (list_length( head )+1) || loc <= 0 )
	{
	}
	else
	{
		if( loc == 1 )
		{
			list_add_beginning(head, data);
		}
		else
		{
			for( i = 1; i < loc; i++ )
			{
				prev_ptr = cur_ptr;
				cur_ptr = cur_ptr->next;
			}

			temp = (struct node_t*) malloc( sizeof( struct node_t ) );
			temp->data = data;

			prev_ptr->next = temp;
			temp->next = cur_ptr;
		}
	}
}


/* Returns the number of elements in the list */
int list_length( struct node_t** head )
{
	struct node_t* cur_ptr;
	int count= 0;

	cur_ptr = (*head);

	while( cur_ptr != NULL )
	{
		cur_ptr = cur_ptr->next;
		count++;
	}

	return count;
}


/* Delete a node from the list */
int list_delete( struct node_t** head, void* data )
{
	struct node_t *prev_ptr, *cur_ptr;

	cur_ptr = (*head);

	while( cur_ptr != NULL )
	{
		if( cur_ptr->data == data )
		{
			if( cur_ptr == (*head) )
			{
				(*head) = cur_ptr->next;
				if( delete_func ) delete_func( cur_ptr->data );
				free( cur_ptr );
				return 1;
			}
			else
			{
				prev_ptr->next = cur_ptr->next;
				if( delete_func ) delete_func( cur_ptr->data );
				free( cur_ptr );
				return 1;
			}
		}
		else
		{
			prev_ptr = cur_ptr;
			cur_ptr = cur_ptr->next;
		}
	}

	return 0;
}

/* Deletes a node from the given position */
int list_delete_loc( struct node_t** head, int loc )
{
	struct node_t *prev_ptr, *cur_ptr;
	int i;

	cur_ptr = (*head);

	if( loc > list_length( head ) || loc <= 0 )
	{
	}
	else
	{
		if( loc == 1 )
		{
			(*head) = cur_ptr->next;
			if( delete_func ) delete_func( cur_ptr->data );
			free(cur_ptr);
			return 1;
		}
		else
		{
			for( i = 1; i < loc; i++ )
			{
				prev_ptr = cur_ptr;
				cur_ptr = cur_ptr->next;
			}

			prev_ptr->next = cur_ptr->next;
			if( delete_func ) delete_func( cur_ptr->data );
			free(cur_ptr);
		}
	}

	return 0;
}

/* Deletes every node in the list */
void list_clear( struct node_t** head )
{
	struct node_t* cur_ptr, *temp;

	cur_ptr = (*head);

	while( cur_ptr )
	{
		temp = cur_ptr->next;
		if( delete_func ) delete_func( cur_ptr->data );
		free(cur_ptr);
		cur_ptr = temp;
	}
    
    (*head) = NULL;
}

/* Retrieve data from the selected node */
void* list_get_node_data( struct node_t** head, int loc )
{
	struct node_t* cur_ptr;
	int i = 1;

	cur_ptr = (*head);

	if( loc < 1 )
		return NULL;

	while( i < loc )
	{
		cur_ptr = cur_ptr->next;
		i++;
	}
    
    if( !cur_ptr )
        return NULL;
	
	return cur_ptr->data;
}
		
/* Node deletion callback */
void set_deletion_callback( void (*func)(void*) )
{
	delete_func = func;
}

 

 

I've been at this for a while, and have no idea what the problem is or how my pointers keep getting corrupted.  Any ideas?  Thanks ^^

 

Shogun

0

Share this post


Link to post
Share on other sites

I think the problem here is that your delete function gets rid of the associated node data, so this happens:

  1. Program decides to delete s.
  2. Program deletes s and its associated node n.
  3. Program tries to get the next member of n, but can't because that node has been deleted and can no longer be assumed to hold valid data.

How I would solve this is by moving the line n=n->next; to immediately after the program extracts the element from n, so that n will always be valid when you extract the next member from it.

2

Share this post


Link to post
Share on other sites

I concur with RulerOfNothing.

 

My recommendation would be to not delete data from linked list, basically remove this line: if( delete_func ) delete_func( cur_ptr->data );

 

You mentioned having two lists, if they both point to same data, than linked list code will attempt to delete it twice.  First time it will work, second time the result will be undefined.

 

Normally you would allocate and free resources in same module. Since linked list doesn't allocate data, it wouldn't be freeing it.

2

Share this post


Link to post
Share on other sites

I think the problem here is that your delete function gets rid of the associated node data, so this happens:

  1. Program decides to delete s.
  2. Program deletes s and its associated node n.
  3. Program tries to get the next member of n, but can't because that node has been deleted and can no longer be assumed to hold valid data.

How I would solve this is by moving the line n=n->next; to immediately after the program extracts the element from n, so that n will always be valid when you extract the next member from it.

 

Okay, this fixed the problem.  I felt so dumb after realizing this, I laughed for about 15 minutes straight.  Thanks.

 

I concur with RulerOfNothing.

 

My recommendation would be to not delete data from linked list, basically remove this line: if( delete_func ) delete_func( cur_ptr->data );

 

You mentioned having two lists, if they both point to same data, than linked list code will attempt to delete it twice.  First time it will work, second time the result will be undefined.

 

Normally you would allocate and free resources in same module. Since linked list doesn't allocate data, it wouldn't be freeing it.

 

I do have multiple lists, but none of them point to the same data though.  I have separate lists for things like enemies, enemy/user shoots, missiles, explosions, etc.  The delete_func callback is really important since very specific data is allocated within the structure it points to (i.e. textures, sound effects, splines) plus the structure was allocated on the heap as well via malloc().  What I do is create an instance of a structure after allocating it, then add it to the list.

 

Thanks for the replies, I really appreciate it! ^^

 

Shogun

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0