Apriltag detection algorithm (specifically UnionFind.h) is not threadsafe

[joshi-bharat]

Describe the bug
The unionfind.h is contains unionfind_get_representative() method which is called from different workerpool threads as part unionfind_t* connected_components(...) and do_gradient_clusters() in apriltag_quas_thesh.c. As a result is not 100% threadsafe.

To Reproduce
Steps to reproduce the behavior:
Build with tsan flag and run on an image with 2 threads.

mkdir build_tsan
cd build_tsan
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_C_FLAGS="-fsanitize=thread -g -O1 -fno-omit-frame-pointer" ..
make -j12
./apriltag_demo -x 1 -t 2 ~/Downloads/detection.jpg

Expected behavior
Tsan throws warnings

WARNING: ThreadSanitizer: data race (pid=1368781)
  Read of size 4 at 0x7f0ff9c0a0b0 by thread T2:
    #0 unionfind_get_representative /home/bharatjoshi/code/apriltag/common/unionfind.h:93 (libapriltagd.so.3+0x1b688)
    #1 do_gradient_clusters /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1635 (libapriltagd.so.3+0x1b688)
    #2 do_cluster_task /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1693 (libapriltagd.so.3+0x1d2cf)
    #3 worker_thread /home/bharatjoshi/code/apriltag/common/workerpool.c:90 (libapriltagd.so.3+0x3e56b)

  Previous write of size 4 at 0x7f0ff9c0a0b0 by thread T1:
    #0 unionfind_get_representative /home/bharatjoshi/code/apriltag/common/unionfind.h:100 (libapriltagd.so.3+0x1c173)
    #1 do_gradient_clusters /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1565 (libapriltagd.so.3+0x1c173)
    #2 do_cluster_task /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1693 (libapriltagd.so.3+0x1d2cf)
    #3 worker_thread /home/bharatjoshi/code/apriltag/common/workerpool.c:90 (libapriltagd.so.3+0x3e56b)

  Location is heap block of size 7372808 at 0x7f0ff98f7000 allocated by main thread:
    #0 malloc ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:655 (libtsan.so.0+0x31c57)
    #1 unionfind_create /home/bharatjoshi/code/apriltag/common/unionfind.h:51 (libapriltagd.so.3+0x1b273)
    #2 connected_components /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1499 (libapriltagd.so.3+0x1b273)
    #3 apriltag_quad_thresh /home/bharatjoshi/code/apriltag/apriltag_quad_thresh.c:1864 (libapriltagd.so.3+0x1e41a)
    #4 apriltag_detector_detect /home/bharatjoshi/code/apriltag/apriltag.c:1109 (libapriltagd.so.3+0xe031)
    #5 main /home/bharatjoshi/code/apriltag/example/apriltag_demo.c:204 (apriltag_demo+0x301e)

  Thread T2 (tid=1368784, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
    #1 workerpool_create /home/bharatjoshi/code/apriltag/common/workerpool.c:113 (libapriltagd.so.3+0x3e760)
    #2 apriltag_detector_detect /home/bharatjoshi/code/apriltag/apriltag.c:1039 (libapriltagd.so.3+0xd7f2)
    #3 main /home/bharatjoshi/code/apriltag/example/apriltag_demo.c:204 (apriltag_demo+0x301e)

  Thread T1 (tid=1368783, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
    #1 workerpool_create /home/bharatjoshi/code/apriltag/common/workerpool.c:113 (libapriltagd.so.3+0x3e760)
    #2 apriltag_detector_detect /home/bharatjoshi/code/apriltag/apriltag.c:1039 (libapriltagd.so.3+0xd7f2)
    #3 main /home/bharatjoshi/code/apriltag/example/apriltag_demo.c:204 (apriltag_demo+0x301e)

** Input Image**
If applicable, please attach the input image that reproduces the problem.

Screenshots
If applicable, add screenshots to help explain your problem.

Operating Sytem
Ubuntu 22.04

** Installation Method**
Installed using following commands

mkdir build_tsan
cd build_tsan
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_C_FLAGS="-fsanitize=thread -g -O1 -fno-omit-frame-pointer" ..
make -j12

** Code version **
v3.4.3

Additional context
Add any other context about the problem here.

[joshi-bharat]

I was able to add mutexes and fix it. However, that results in very slow processing times.

[christian-rauch]

I am wondering why locking sections of the code should slow down processing that much. Can you send a PR with your solution and some processing statistics for the runtime with and without your PR for different thread counts?