search

philip-w-howard / RP-Red-Black-Tree

Red Black Tree implemented with Relativistic Programming
13 stars 1 forks source link

RP-STM method Deadlock? #1

Open vvenkates27 opened 8 years ago

vvenkates27 commented 8 years ago

Hi Philip,

Very interesting work that you have done here, I was trying to try out with RP-STM approach, but was experiencing deadlock with this method for certain number of threads. I used SwissRP compiled with gcc and also libatomic library compiled with gcc. I wrote a simple openmp based code, to test this, and wasn't sure whether I was doing something wrong. If you can fill me in, if I am doing something wrong, that would be great. The source code I used for testing is found here.

void lock = NULL; my_tree = (rbtree_t ) malloc (sizeof(rbtree_t));

lock = lock_init(); lock_thread_init(lock,0); rb_create(my_tree, lock); lock_mb();

if (!rb_insert(my_tree, 10, ((void *)10))){ printf ("test10 insert Error\n"); }

if (!rb_insert(my_tree, 20, ((void *)20))){ printf ("test10 insert Error\n"); }

pragma omp parallel num_threads(11) shared(my_tree, lock)

{

          void *value;
            int tid = omp_get_thread_num();

            lock_thread_init(lock, tid);
            lock_mb();
            if (tid == 0){
                    if (!rb_insert(my_tree, 30, ((void *)30))){
                            printf ("test30 insert Error\n");
                    }

            }
            else if (tid == 1){
            if (!rb_insert(my_tree, 40, ((void *)40))){
                            printf ("test40 insert Error\n");
                    }

            }
            else if (tid == 2){
                    if (!rb_insert(my_tree, 5, ((void *)50))){
                            printf ("test 5 insert Error\n");
                    }

            }
            else if (tid == 3){
                    if (!rb_insert(my_tree, 8, ((void *)80))){
                                    printf ("test 8 insert Error\n");
                    }

            }
            else if (tid == 4){
                    if (!rb_insert(my_tree, 9, ((void *)90))){
                            printf ("test 9 insert Error\n");
                    }

            }
            else if (tid == 5){
           if(!rb_insert(my_tree, 11, ((void *)110))){
                            printf ("test 11 insert Error\n");
                    }

            }
            else if (tid == 6){
                    if(!rb_insert(my_tree,  12, ((void *)120))){
                            printf ("test 12 insert Error\n");
                    }

            }
            else if (tid == 7){
                    value  = rb_find(my_tree, 11);
                    if (value != NULL){
                            printf("Search 11 by thread 7 : %lu\n",
                                   (unsigned long)value);
                    }
                    else{
                            printf("Search 11 by thread 7 Value not found \n");
                    }
            }
            else if (tid == 8){
                    value  = rb_find(my_tree, 12);
                    if (value != NULL){  if (value != NULL){
                            printf("Search 12 by thread 8 : %lu\n",
                                   (unsigned long)value);
                    }
                    else{
                            printf("Search 12 by thread 8 Value not found \n");
                    }
            }
            else if (tid == 9){
                    if(!rb_insert(my_tree, 16, ((void *)160))){
                            printf ("test01 insert Error\n");
                    }

            }
            else{
                    value  = rb_find(my_tree, 10);
                    if (value != NULL)
                            printf("Search 10 by thread 9: %lu\n", (unsigned long)value);
                    else
                            printf("Search 10 by thread 9 Value not found \n");
            }
            lock_thread_close(lock, tid);
    }
    lock_mb();

Let me know if you need any other information to triage this issue.

Thanks Vish

philip-w-howard commented 8 years ago

Always glad to see when someone is using my work.

I took a quick glance at your code and didn't notice anything wrong. I'll take a closer look when I have more time (hopefully later today). I have not attempted to use my code with OpenMP. I am not familiar with the internals of OpenMP to know if it would cause any incompatibilities with my code. All of my work directly used pthreads. Is there a specific reason why you are using OpenMP?

I'll take a more detailed look and get back to you with what I find.

Phil

On Thu, Oct 29, 2015 at 7:25 AM, Vishwanath Venkatesan < notifications@github.com> wrote:

Hi Philip,

Very interesting work that you have done here, I was trying to try out with RP-STM approach, but was experiencing deadlock with this method for certain number of threads. I used SwissRP compiled with gcc and also libatomic library compiled with gcc. I wrote a simple openmp based code, to test this, and wasn't sure whether I was doing something wrong. If you can fill me in, if I am doing something wrong, that would be great. The source

code I used for testing is found here.

void lock = NULL; my_tree = (rbtree_t ) malloc (sizeof(rbtree_t));

lock = lock_init(); lock_thread_init(lock,0); rb_create(my_tree, lock); lock_mb();

if (!rb_insert(my_tree, 10, ((void *)10))){ printf ("test10 insert Error\n"); }

if (!rb_insert(my_tree, 20, ((void *)20))){ printf ("test10 insert Error\n"); }

pragma omp parallel num_threads(11) shared(my_tree, lock)

{

      void *value;
        int tid = omp_get_thread_num();

        lock_thread_init(lock, tid);
        lock_mb();
        if (tid == 0){
                if (!rb_insert(my_tree, 30, ((void *)30))){
                        printf ("test30 insert Error\n");
                }

        }
        else if (tid == 1){
        if (!rb_insert(my_tree, 40, ((void *)40))){
                        printf ("test40 insert Error\n");
                }

        }
        else if (tid == 2){
                if (!rb_insert(my_tree, 5, ((void *)50))){
                        printf ("test 5 insert Error\n");
                }

        }
        else if (tid == 3){
                if (!rb_insert(my_tree, 8, ((void *)80))){
                                printf ("test 8 insert Error\n");
                }

        }
        else if (tid == 4){
                if (!rb_insert(my_tree, 9, ((void *)90))){
                        printf ("test 9 insert Error\n");
                }

        }
        else if (tid == 5){
       if(!rb_insert(my_tree, 11, ((void *)110))){
                        printf ("test 11 insert Error\n");
                }

        }
        else if (tid == 6){
                if(!rb_insert(my_tree,  12, ((void *)120))){
                        printf ("test 12 insert Error\n");
                }

        }
        else if (tid == 7){
                value  = rb_find(my_tree, 11);
                if (value != NULL){
                        printf("Search 11 by thread 7 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 11 by thread 7 Value not found \n");
                }
        }
        else if (tid == 8){
                value  = rb_find(my_tree, 12);
                if (value != NULL){  if (value != NULL){
                        printf("Search 12 by thread 8 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 12 by thread 8 Value not found \n");
                }
        }
        else if (tid == 9){
                if(!rb_insert(my_tree, 16, ((void *)160))){
                        printf ("test01 insert Error\n");
                }

        }
        else{
                value  = rb_find(my_tree, 10);
                if (value != NULL)
                        printf("Search 10 by thread 9: %lu\n", (unsigned long)value);
                else
                        printf("Search 10 by thread 9 Value not found \n");
        }
        lock_thread_close(lock, tid);
}
lock_mb();

Let me know if you need any other information to triage this issue.

Thanks Vish

— Reply to this email directly or view it on GitHub https://github.com/philip-w-howard/RP-Red-Black-Tree/issues/1.

vvenkates27 commented 8 years ago

Thanks for the quick response. No specific reason for using OpenMP. I can try and implement this quickly with Pthreads, if that can help. Actually similar openmp code works fine with your RCU/RP implementations, so I was actually surprised to see it deadlocking with this version of the code

philip-w-howard commented 8 years ago

Finally had a chance to take another look at this....

I still don't see anything obviously wrong with your code, but here are a couple of observations:

1) Some of the routines call pthread_self() to get a thread ID. If openmp doesn't use pthreads, this could cause a problem. 2) The rcu version of lock_thread_close() appears to be a noop. This shouldn't be an issue for the code you showed me.

Were you able to identify where the deadlock occurred? With some versions of my code, the thread shutdown process had trouble, but all useful work was successful. I don't recall what the resolution of that issue was.

Something I should probably do with the code is port it to use the newer C++ concurrency features instead of continuing to rely on libatomic-ops, but provided you are on a supported platform, that library should work.

Sorry I can't be of more help. Did you get a pthreads version written?

Phil

On Thu, Oct 29, 2015 at 7:25 AM, Vishwanath Venkatesan < notifications@github.com> wrote:

Hi Philip,

Very interesting work that you have done here, I was trying to try out with RP-STM approach, but was experiencing deadlock with this method for certain number of threads. I used SwissRP compiled with gcc and also libatomic library compiled with gcc. I wrote a simple openmp based code, to test this, and wasn't sure whether I was doing something wrong. If you can fill me in, if I am doing something wrong, that would be great. The source

code I used for testing is found here.

void lock = NULL; my_tree = (rbtree_t ) malloc (sizeof(rbtree_t));

lock = lock_init(); lock_thread_init(lock,0); rb_create(my_tree, lock); lock_mb();

if (!rb_insert(my_tree, 10, ((void *)10))){ printf ("test10 insert Error\n"); }

if (!rb_insert(my_tree, 20, ((void *)20))){ printf ("test10 insert Error\n"); }

pragma omp parallel num_threads(11) shared(my_tree, lock)

{

      void *value;
        int tid = omp_get_thread_num();

        lock_thread_init(lock, tid);
        lock_mb();
        if (tid == 0){
                if (!rb_insert(my_tree, 30, ((void *)30))){
                        printf ("test30 insert Error\n");
                }

        }
        else if (tid == 1){
        if (!rb_insert(my_tree, 40, ((void *)40))){
                        printf ("test40 insert Error\n");
                }

        }
        else if (tid == 2){
                if (!rb_insert(my_tree, 5, ((void *)50))){
                        printf ("test 5 insert Error\n");
                }

        }
        else if (tid == 3){
                if (!rb_insert(my_tree, 8, ((void *)80))){
                                printf ("test 8 insert Error\n");
                }

        }
        else if (tid == 4){
                if (!rb_insert(my_tree, 9, ((void *)90))){
                        printf ("test 9 insert Error\n");
                }

        }
        else if (tid == 5){
       if(!rb_insert(my_tree, 11, ((void *)110))){
                        printf ("test 11 insert Error\n");
                }

        }
        else if (tid == 6){
                if(!rb_insert(my_tree,  12, ((void *)120))){
                        printf ("test 12 insert Error\n");
                }

        }
        else if (tid == 7){
                value  = rb_find(my_tree, 11);
                if (value != NULL){
                        printf("Search 11 by thread 7 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 11 by thread 7 Value not found \n");
                }
        }
        else if (tid == 8){
                value  = rb_find(my_tree, 12);
                if (value != NULL){  if (value != NULL){
                        printf("Search 12 by thread 8 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 12 by thread 8 Value not found \n");
                }
        }
        else if (tid == 9){
                if(!rb_insert(my_tree, 16, ((void *)160))){
                        printf ("test01 insert Error\n");
                }

        }
        else{
                value  = rb_find(my_tree, 10);
                if (value != NULL)
                        printf("Search 10 by thread 9: %lu\n", (unsigned long)value);
                else
                        printf("Search 10 by thread 9 Value not found \n");
        }
        lock_thread_close(lock, tid);
}
lock_mb();

Let me know if you need any other information to triage this issue.

Thanks Vish

— Reply to this email directly or view it on GitHub https://github.com/philip-w-howard/RP-Red-Black-Tree/issues/1.

philip-w-howard commented 8 years ago

Took one more look after reading your email more carefully. The STM RBTree code was quite different than the non-STM version. The STM version used macros for all the STM protected LOAD and STORE operations. I don't know what the behavior would be if you linked with the STM library but did not use the STM version of the RBTree code, but deadlock would not be out of the question. Are you sure you built the correct combination of source files?

Phil

On Mon, Nov 2, 2015 at 8:01 PM, Phil Howard phil.w.howard@gmail.com wrote:

Finally had a chance to take another look at this....

I still don't see anything obviously wrong with your code, but here are a couple of observations:

1) Some of the routines call pthread_self() to get a thread ID. If openmp doesn't use pthreads, this could cause a problem. 2) The rcu version of lock_thread_close() appears to be a noop. This shouldn't be an issue for the code you showed me.

Were you able to identify where the deadlock occurred? With some versions of my code, the thread shutdown process had trouble, but all useful work was successful. I don't recall what the resolution of that issue was.

Something I should probably do with the code is port it to use the newer C++ concurrency features instead of continuing to rely on libatomic-ops, but provided you are on a supported platform, that library should work.

Sorry I can't be of more help. Did you get a pthreads version written?

Phil

On Thu, Oct 29, 2015 at 7:25 AM, Vishwanath Venkatesan < notifications@github.com> wrote:

Hi Philip,

Very interesting work that you have done here, I was trying to try out with RP-STM approach, but was experiencing deadlock with this method for certain number of threads. I used SwissRP compiled with gcc and also libatomic library compiled with gcc. I wrote a simple openmp based code, to test this, and wasn't sure whether I was doing something wrong. If you can fill me in, if I am doing something wrong, that would be great. The source

code I used for testing is found here.

void lock = NULL; my_tree = (rbtree_t ) malloc (sizeof(rbtree_t));

lock = lock_init(); lock_thread_init(lock,0); rb_create(my_tree, lock); lock_mb();

if (!rb_insert(my_tree, 10, ((void *)10))){ printf ("test10 insert Error\n"); }

if (!rb_insert(my_tree, 20, ((void *)20))){ printf ("test10 insert Error\n"); }

pragma omp parallel num_threads(11) shared(my_tree, lock)

{

      void *value;
        int tid = omp_get_thread_num();

        lock_thread_init(lock, tid);
        lock_mb();
        if (tid == 0){
                if (!rb_insert(my_tree, 30, ((void *)30))){
                        printf ("test30 insert Error\n");
                }

        }
        else if (tid == 1){
        if (!rb_insert(my_tree, 40, ((void *)40))){
                        printf ("test40 insert Error\n");
                }

        }
        else if (tid == 2){
                if (!rb_insert(my_tree, 5, ((void *)50))){
                        printf ("test 5 insert Error\n");
                }

        }
        else if (tid == 3){
                if (!rb_insert(my_tree, 8, ((void *)80))){
                                printf ("test 8 insert Error\n");
                }

        }
        else if (tid == 4){
                if (!rb_insert(my_tree, 9, ((void *)90))){
                        printf ("test 9 insert Error\n");
                }

        }
        else if (tid == 5){
       if(!rb_insert(my_tree, 11, ((void *)110))){
                        printf ("test 11 insert Error\n");
                }

        }
        else if (tid == 6){
                if(!rb_insert(my_tree,  12, ((void *)120))){
                        printf ("test 12 insert Error\n");
                }

        }
        else if (tid == 7){
                value  = rb_find(my_tree, 11);
                if (value != NULL){
                        printf("Search 11 by thread 7 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 11 by thread 7 Value not found \n");
                }
        }
        else if (tid == 8){
                value  = rb_find(my_tree, 12);
                if (value != NULL){  if (value != NULL){
                        printf("Search 12 by thread 8 : %lu\n",
                               (unsigned long)value);
                }
                else{
                        printf("Search 12 by thread 8 Value not found \n");
                }
        }
        else if (tid == 9){
                if(!rb_insert(my_tree, 16, ((void *)160))){
                        printf ("test01 insert Error\n");
                }

        }
        else{
                value  = rb_find(my_tree, 10);
                if (value != NULL)
                        printf("Search 10 by thread 9: %lu\n", (unsigned long)value);
                else
                        printf("Search 10 by thread 9 Value not found \n");
        }
        lock_thread_close(lock, tid);
}
lock_mb();

Let me know if you need any other information to triage this issue.

Thanks Vish

— Reply to this email directly or view it on GitHub https://github.com/philip-w-howard/RP-Red-Black-Tree/issues/1.

vvenkates27 commented 8 years ago

I haven't had the chance to try out Pthread based runner program yet. I am looking to check for weak scaling numbers, number of inserts/lookups per-second. Can the runner program in the repo be used to generate these numbers?

I have been using swissRP for the Transactional memory and also the lib atomic and urcu libraries for additional compilation. The Makefile for RP-Red-black-tree did say lwlpdstm_rp. I was assuming this was the lwlpdstm generated from swissRP. Are these the correct dependencies?

Appreciate the responses. Thanks