c - 为链表上的操作实现多线程的问题

Question

在下面的代码中，我尝试使用多个线程处理各种链表操作。可以支持多个链表，所有函数都是通用的，除了我保留了一些printf语句来调试代码。

typedef void (*gen_fun_t)(void *);

ll_t thread[2];
int ret;

#define RWLOCK(lt, lk) (ret=(lt) == l_read)? pthread_rwlock_rdlock(&(lk)): pthread_rwlock_wrlock(&(lk))
#define RWUNLOCK(lk) pthread_rwlock_unlock(&(lk));

typedef enum locktype locktype_t;

enum locktype
{
    l_read,
    l_write
};

struct node
{
    void *val;

    struct node  *next;

    pthread_rwlock_t m;
};


struct ll
{
        int len;

        struct node *head;
        pthread_rwlock_t m;

        gen_fun_t val_teardown;

        gen_fun_t val_printer;
};
typedef struct ll* ll_t;

typedef struct node * ll_node;

ll_t create( gen_fun_t val_teardown)
{
        ll_t list=(ll_t)malloc(sizeof(struct ll));
        list->head=NULL;
        list->len=0;
        list->val_teardown = val_teardown;

        pthread_rwlock_init(&list->m, NULL);

        return list;
}

ll_node new_node(void *val)
{
        ll_node node= (ll_node)malloc(sizeof(struct node));
        node->val=val;
        node->next=NULL;
        pthread_rwlock_init(&node->m, NULL);

        return node;
}


int remove_mid(ll_t list, int n)
{
        printf("Before deletion \n");
        print(list);
        ll_node temp;
        if(n==0)
        {
                temp=list->head;
                list->head=temp->next;
                printf("%d \n", *(int *)(list->head)->val);
        }
        else
        {
                ll_node it;
                it=list->head;
                for(;n>1;n--)
                        it=it->next;
                printf("%d \n", *(int *)(it->next)->val);
                temp=it->next;
                it->next=it->next==NULL? NULL: temp->next;
                printf("%d \n", *(int *)(it->next)->val);
        }
        (list->len)--;

        list->val_teardown(temp->val);
        free(temp);
        return list->len;
}

int insert_mid(ll_t list, void *val, int n)
{
        ll_node node= new_node(val);

        if(n==0)
        {
                node->next=list->head;
                list->head=node;
        }
        else
        {
                ll_node it;
                it=list->head;
                for(;n>1;n--)
                        it=it->next;
                node->next=it->next;
                it->next=node;
                printf("After insertion \n");
                print(list);
                printf("\n");
        }
        (list->len)++;
        return list->len;
}

void *thread_operation(void * arg)
{
        long id= (long) arg;

        if(id==0)
        {
                        RWLOCK(l_write, list[0]->m);
                        //RWLOCK(l_read, list[0]->m);
                        printf("The status of lock operation is %d \n", ret);
                        printf("\nThread: %ld \n", id);
                        int v=rand()%100;
                        int pos=rand()%list[0]->len;
                        printf("The position inserted is %d \n",pos+1);
                        pos=insert_mid(list[0], &v, pos);
                        //RWUNLOCK(list[0]->m);
                        RWUNLOCK(list[0]->m);

        }
        else
        {
                        RWLOCK(l_write, list[0]->m);
                        //RWLOCK(l_read, list[0]->m);
                        printf("The status of lock operation is %d \n", ret);
                        printf("\nThread: %ld \n", id);
                        int pos=rand()%list[0]->len;
                        printf("The position to be deleted is %d \n", pos+1);
                        pos=remove_mid(list[0], pos);
                        print(list[0]);
                        //RWUNLOCK(list[0]->m);
                        RWUNLOCK(list[0]->m);
        }
}

int main()
{

        int thread_count=2;
        long thread;
        srand(time(0));

        list[0]= create(int_tear);
        list[0]->val_printer = int_printer;

        list[1]=create(float_tear);
        list[1]->val_printer= float_printer;

        pthread_t *thread_handles;

        int l, a=2, b=8, c=15;

        l=insert_first(list[0], &a);
        l=insert_end(list[0], &b);
        l=insert_mid(list[0], &c, rand()%l);

        double start, finish, elapsed;

        start=clock();

        thread_handles= (pthread_t *) malloc(thread_count*sizeof(pthread_t));

        for(thread=0;thread<thread_count;thread++)
                pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);

        for(thread=0;thread<thread_count;thread++)
                pthread_join(thread_handles[thread], NULL);

        finish=clock();
        elapsed =(finish-start)/CLOCKS_PER_SEC;
        return 0;
}

它给出的输出为

Thread: 0 
The position to be inserted is 3 
After insertion 
ll: 2 15 79 8 


Thread: 1 
The position to be deleted is 1 
Before deletion 
ll: 2 15 -2087655584 8

ll: 15 -2087655584 8

显然，79 被insert_mid函数插入到了位置 2，但为什么它会变成 -2087655584？解决办法是什么？

如果需要任何信息，请告知。

score 0 · Accepted Answer

Short summary: You store the address of a local variable in a list node and this variable goes out of scope, so the address becomes invalid.

Your function new_node(void *val) gets an address as an argument and stores this address in the node structure as node->val.

In your main function you first create 3 nodes with the addresses of local variables.

        int l, a=2, b=8, c=15;

        l=insert_first(list[0], &a);
        l=insert_end(list[0], &b);
        l=insert_mid(list[0], &c, rand()%l);

These variables are valid until the end of main, so there is no problem here.

In this loop

        for(thread=0;thread<thread_count;thread++)
                pthread_create(&thread_handles[thread], NULL, thread_operation, (void *)thread);

you create threads running thread_operation and pass the loop counter, casted to a void* as an argument.

In thread_operation when called with argument value 0 you add a node using the address of a local variable v

void *thread_operation(void * arg)
{
        long id= (long) arg;

        if(id==0)
        {
/* ... */
                        int v=rand()%100;
                        int pos=rand()%list[0]->len;
/* ... */
                        pos=insert_mid(list[0], &v, pos); /* &v is the address of a local variable */
/* ... */
        }
        else
        {
/* ... */
        }
}

/* ... */
int insert_mid(ll_t list, void *val, int n)
{
        ll_node node= new_node(val); /* The address is passed to the new node. */
/* ... */
}

When thread_operation leaves the body of

        if(id==0)
        {
/* ... */
        }

the variable goes out of scope and becomes invalid. (If you compile your program without optimization it probably keeps its value until the function returns, but this is not guaranteed.)

When thread_operation returns, the stack area where this variable was located is disposed and will be used for other function calls later.

When you print the contents of the list, the node inserted by the thread with ID 0 points to some address on the stack that once held the variable v and might be in use or might have been used for something else afterwards. That's why the value gets changed. This is undefined behavior.

To fix this problem you can either change your node structure to store the value of the variable as an int instead of the address of the variable as a void * or you have to allocate memory and create a copy of the data like this

ll_node new_node(void *val, size_t size)
{
        ll_node node= (ll_node)malloc(sizeof(struct node));
        /* TODO check that malloc did not return NULL */
        node->val = malloc(size);
        /* TODO check that malloc did not return NULL */
        memcpy(node->val, val, size);
        node->next=NULL;
        pthread_rwlock_init(&node->m, NULL);

        return node;
}

Additional possible problem:

You create a lock object in every list node. If you want to use this to to protect access to the data in the node, the corresponding thread must get (at least) a read lock for the list to prevent other threads from deleting the node.

c - 为链表上的操作实现多线程的问题

1 回答 1

Related

Reference