Проблема в реализации многопоточности для операций над связанным списком

Question

В следующем коде я попытался обработать различные операции со связанным списком, используя несколько потоков. Можно поддерживать несколько связанных списков, и все функции являются обобщенными c, за исключением того, что я сохранил несколько операторов 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 был вставлен в положение 2 с помощью функции insert_mid, но почему он меняется на -2087655584? Что такое решение?

Если требуется какая-либо информация, пожалуйста, сообщите.

Answer 1

Краткое резюме: Вы сохраняете адрес локальной переменной в узле списка, и эта переменная выходит из области видимости, поэтому адрес становится недействительным.

---

Ваша функция new_node(void *val) получает адрес в качестве аргумента и сохраняет этот адрес в структуре узла как node->val.

В вашей функции main вы сначала создаете 3 узла с адресами локальных переменных.

        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);

Эти переменные действительны до конца main, поэтому здесь нет проблем.

В этом l oop

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

вы создаете потоки, работающие thread_operation и передать счетчик l oop, приведенный к void* в качестве аргумента.

В thread_operation при вызове со значением аргумента 0 вы добавляете узел, используя адрес локальной переменной 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. */
/* ... */
}

Когда thread_operation покидает тело

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

, переменная выходит из области видимости и становится недействительной. (Если вы компилируете свою программу без оптимизации, она, вероятно, сохраняет свое значение до тех пор, пока функция не вернется, но это не гарантируется.)

Когда вернется thread_operation, область стека, в которой находилась эта переменная, будет расположена и будет используется для других вызовов функций позже.

Когда вы печатаете содержимое списка, узел, вставленный потоком с идентификатором 0, указывает на некоторый адрес в стеке, который когда-то содержал переменную v и мог находиться в использовать или могли быть использованы для чего-то еще впоследствии. Вот почему значение меняется. Это неопределенное поведение.

Чтобы решить эту проблему, вы можете либо изменить структуру вашего узла на , сохранить значение переменной в виде int вместо адреса переменной как void * или Вы должны выделить память и создать копию данных следующим образом

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;
}

Дополнительная возможная проблема:

Вы создаете объект блокировки в каждом узле списка. Если вы хотите использовать это для защиты доступа к данным в узле, соответствующий поток должен получить (как минимум) блокировку чтения для списка, чтобы другие потоки не могли удалить узел.