Skip to content

Deterministically iterate status listeners#2109

Merged
robgjansen merged 4 commits intoshadow:mainfrom
robgjansen:deterministic_ht_iter
May 5, 2022
Merged

Deterministically iterate status listeners#2109
robgjansen merged 4 commits intoshadow:mainfrom
robgjansen:deterministic_ht_iter

Conversation

@robgjansen
Copy link
Copy Markdown
Member

@robgjansen robgjansen commented Apr 30, 2022

Because hash table iterators are not guaranteed to provide deterministic ordering, we must assign our own deterministic order to the items held by the hash table and then iterate them in sorted order. This fixes two related areas in the code where StatusListener objects were being iterated according to an undefined hash table order: in the descriptor and futex modules.

Deterministic hash table ordering tests are difficult on a small scale so no new tests have been added. It would be nice if in the future we can design a data structure like a ring where we can guarantee in-order traversal but also change the starting point of the iterator on every iteration so that the same listeners don't always get woken up first (potentially starving items at the end of the list).

refs #666

@robgjansen robgjansen added Type: Bug Error or flaw producing unexpected results Component: Main Composing the core Shadow executable labels Apr 30, 2022
@robgjansen robgjansen self-assigned this Apr 30, 2022
@stevenengler
Copy link
Copy Markdown
Contributor

stevenengler commented Apr 30, 2022

Running this patch, the "relay1" tor process in the tor minimal test generates the exact same strace log (--strace-logging-mode deterministic) for multiple runs.

@robgjansen robgjansen marked this pull request as ready for review May 1, 2022 00:19
@robgjansen robgjansen requested a review from stevenengler May 1, 2022 00:20
@robgjansen
Copy link
Copy Markdown
Member Author

robgjansen commented May 2, 2022

I ran two 5% Tor nets in our CI and the syscall counts are identical:

➜  cat 1
{read:965033373, epoll_wait:572659245, write:300416837, recvfrom:174426355, epoll_ctl:163261773, getsockopt:90317920, ioctl:89344837, sendto:75512005, timerfd_settime:48214389, getrandom:23770644, close:8713196, lseek:7132421, open:4671325, fstat:4570252, openat:2711721, timerfd_create:2647364, setsockopt:1949467, socket:1856423, connect:1854201, getsockname:1780430, uname:1745424, fcntl:1741799, accept:1733311, shutdown:1523557, futex:1225778, accept4:974244, brk:379352, shadow_hostname_to_addr_ipv4:15809, mmap:15360, munmap:11151, rt_sigaction:10994, mprotect:6456, getpid:1958, shadow_init_memory_manager:1958, bind:1883, listen:1883, epoll_create:1657, fchmod:1092, epoll_create1:753, flock:753, pipe2:753, sysinfo:753, clone:678, getdents64:678, rt_sigprocmask:678, set_robust_list:678, shadow_get_shm_blk:678, eventfd2:339}
➜  cat 2
{read:965033373, epoll_wait:572659245, write:300416837, recvfrom:174426355, epoll_ctl:163261773, getsockopt:90317920, ioctl:89344837, sendto:75512005, timerfd_settime:48214389, getrandom:23770644, close:8713196, lseek:7132421, open:4671325, fstat:4570252, openat:2711721, timerfd_create:2647364, setsockopt:1949467, socket:1856423, connect:1854201, getsockname:1780430, uname:1745424, fcntl:1741799, accept:1733311, shutdown:1523557, futex:1225778, accept4:974244, brk:379352, shadow_hostname_to_addr_ipv4:15809, mmap:15360, munmap:11151, rt_sigaction:10994, mprotect:6456, getpid:1958, shadow_init_memory_manager:1958, bind:1883, listen:1883, epoll_create:1657, fchmod:1092, epoll_create1:753, flock:753, pipe2:753, sysinfo:753, clone:678, getdents64:678, rt_sigprocmask:678, set_robust_list:678, shadow_get_shm_blk:678, eventfd2:339}
➜  diff -s 1 2
Files 1 and 2 are identical

I checked the json simulated performance stats files:

➜ cd tornet-0.05-1/tornet.plot.data/
➜ for name in *json ; do diff -qs ${name} ../../tornet-0.05-2/tornet.plot.data/${name} ; done

The Tor simulated network performance stats are identical across the repeated trials:

Files error_rate.exit.json and ../../tornet-0.05-2/tornet.plot.data/error_rate.exit.json are identical
Files error_rate.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/error_rate.onionservice.json are identical
Files perfclient_circuit_build_time.exit.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_circuit_build_time.exit.json are identical
Files perfclient_circuit_build_time.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_circuit_build_time.onionservice.json are identical
Files perfclient_goodput.exit.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_goodput.exit.json are identical
Files perfclient_goodput.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_goodput.onionservice.json are identical
Files perfclient_goodput_5MiB.exit.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_goodput_5MiB.exit.json are identical
Files perfclient_goodput_5MiB.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/perfclient_goodput_5MiB.onionservice.json are identical
Files relay_goodput.json and ../../tornet-0.05-2/tornet.plot.data/relay_goodput.json are identical
Files round_trip_time.exit.json and ../../tornet-0.05-2/tornet.plot.data/round_trip_time.exit.json are identical
Files round_trip_time.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/round_trip_time.onionservice.json are identical
Files simulation_info.json and ../../tornet-0.05-2/tornet.plot.data/simulation_info.json are identical
Files time_to_first_byte_recv.exit.json and ../../tornet-0.05-2/tornet.plot.data/time_to_first_byte_recv.exit.json are identical
Files time_to_first_byte_recv.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/time_to_first_byte_recv.onionservice.json are identical
Files time_to_last_byte_recv.exit.json and ../../tornet-0.05-2/tornet.plot.data/time_to_last_byte_recv.exit.json are identical
Files time_to_last_byte_recv.onionservice.json and ../../tornet-0.05-2/tornet.plot.data/time_to_last_byte_recv.onionservice.json are identical

The Shadow resource usage stats varied, which is expected because the host hardware is not running a deterministic OS and we don't expect Shadow itself to run in the exact same amount of time.

Files resource_usage.json and ../../tornet-0.05-2/tornet.plot.data/resource_usage.json differ

@robgjansen robgjansen changed the title Deterministically iterate listeners stored in hash tables Deterministically iterate status listeners May 2, 2022
stevenengler
stevenengler approved these changes May 2, 2022
View reviewed changes
@robgjansen robgjansen force-pushed the deterministic_ht_iter branch from 6b61abf to 9faa33c Compare May 5, 2022 15:24
@robgjansen robgjansen mentioned this pull request May 5, 2022
Closed
7 tasks
@robgjansen robgjansen merged commit fc5bc48 into shadow:main May 5, 2022
@robgjansen robgjansen deleted the deterministic_ht_iter branch May 5, 2022 16:01
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@stevenengler stevenengler stevenengler approved these changes

Assignees

@robgjansen robgjansen

Labels

Component: Main Composing the core Shadow executable Type: Bug Error or flaw producing unexpected results

Projects

None yet

Milestone

Remove sources of non-determinism

Development

Successfully merging this pull request may close these issues.

2 participants

@robgjansen @stevenengler