1// Copyright 2016 The Fuchsia Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#include <inttypes.h> 6#include <limits.h> 7#include <sched.h> 8#include <stdio.h> 9#include <stdlib.h> 10#include <string.h> 11#include <threads.h> 12#include <time.h> 13#include <unistd.h> 14#include <unittest/unittest.h> 15#include <zircon/syscalls.h> 16#include <zircon/threads.h> 17#include <zircon/time.h> 18#include <zircon/types.h> 19 20static bool test_futex_wait_value_mismatch() { 21 BEGIN_TEST; 22 int32_t futex_value = 123; 23 zx_status_t rc = zx_futex_wait(&futex_value, futex_value + 1, 24 ZX_TIME_INFINITE); 25 ASSERT_EQ(rc, ZX_ERR_BAD_STATE, "Futex wait should have reurned bad state"); 26 END_TEST; 27} 28 29static bool test_futex_wait_timeout() { 30 BEGIN_TEST; 31 int32_t futex_value = 123; 32 zx_status_t rc = zx_futex_wait(&futex_value, futex_value, 0); 33 ASSERT_EQ(rc, ZX_ERR_TIMED_OUT, "Futex wait should have reurned timeout"); 34 END_TEST; 35} 36 37// This test checks that the timeout in futex_wait() is respected 38static bool test_futex_wait_timeout_elapsed() { 39 BEGIN_TEST; 40 int32_t futex_value = 0; 41 constexpr zx_duration_t kRelativeDeadline = ZX_MSEC(500); 42 for (int i = 0; i < 5; ++i) { 43 zx_time_t now = zx_clock_get_monotonic(); 44 zx_status_t rc = zx_futex_wait(&futex_value, 0, zx_deadline_after(kRelativeDeadline)); 45 ASSERT_EQ(rc, ZX_ERR_TIMED_OUT, "wait should time out"); 46 zx_duration_t elapsed = zx_time_sub_time(zx_clock_get_monotonic(), now); 47 if (elapsed < kRelativeDeadline) { 48 unittest_printf("\nelapsed %" PRIu64 49 " < kRelativeDeadline: %" PRIu64 "\n", 50 elapsed, kRelativeDeadline); 51 EXPECT_TRUE(false, "wait returned early"); 52 } 53 } 54 END_TEST; 55} 56 57 58static bool test_futex_wait_bad_address() { 59 BEGIN_TEST; 60 // Check that the wait address is checked for validity. 61 zx_status_t rc = zx_futex_wait(nullptr, 123, ZX_TIME_INFINITE); 62 ASSERT_EQ(rc, ZX_ERR_INVALID_ARGS, "Futex wait should have reurned invalid_arg"); 63 END_TEST; 64} 65 66// Poll until the kernel says that the given thread is blocked on a futex. 67static bool wait_until_blocked_on_some_futex(zx_handle_t thread) { 68 for (;;) { 69 zx_info_thread_t info; 70 ASSERT_EQ(zx_object_get_info(thread, ZX_INFO_THREAD, &info, 71 sizeof(info), nullptr, nullptr), ZX_OK); 72 if (info.state == ZX_THREAD_STATE_RUNNING) { 73 zx_nanosleep(zx_deadline_after(ZX_USEC(100))); 74 continue; 75 } 76 ASSERT_EQ(info.state, ZX_THREAD_STATE_BLOCKED_FUTEX); 77 return true; 78 } 79} 80 81// This starts a thread which waits on a futex. We can do futex_wake() 82// operations and then test whether or not this thread has been woken up. 83class TestThread { 84public: 85 TestThread(volatile int32_t* futex_addr, 86 zx_duration_t timeout_in_us = ZX_TIME_INFINITE) 87 : futex_addr_(futex_addr), 88 timeout_in_ns_(timeout_in_us) { 89 auto ret = thrd_create_with_name(&thread_, wakeup_test_thread, this, "wakeup_test_thread"); 90 EXPECT_EQ(ret, thrd_success, "Error during thread creation"); 91 while (state_ == STATE_STARTED) { 92 sched_yield(); 93 } 94 // Note that this could fail if futex_wait() gets a spurious wakeup. 95 EXPECT_EQ(state_, STATE_ABOUT_TO_WAIT, "wrong state"); 96 97 // We should only do this after state_ is STATE_ABOUT_TO_WAIT, 98 // otherwise it could return when the thread has temporarily 99 // blocked on a libc-internal futex. 100 EXPECT_TRUE(wait_until_blocked_on_some_futex(get_thread_handle())); 101 102 // This could also fail if futex_wait() gets a spurious wakeup. 103 EXPECT_EQ(state_, STATE_ABOUT_TO_WAIT, "wrong state"); 104 } 105 106 TestThread(const TestThread &) = delete; 107 TestThread& operator=(const TestThread &) = delete; 108 109 ~TestThread() { 110 if (handle_ != ZX_HANDLE_INVALID) { 111 // kill_thread() was used, so the thrd_t is in undefined state. 112 // Use the kernel handle to ensure the thread has died. 113 EXPECT_EQ(zx_object_wait_one(handle_, ZX_THREAD_TERMINATED, 114 ZX_TIME_INFINITE, NULL), ZX_OK, 115 "zx_object_wait_one failed on killed thread"); 116 EXPECT_EQ(zx_handle_close(handle_), ZX_OK, 117 "zx_handle_close failed on killed thread's handle"); 118 // The thrd_t and state associated with it is leaked at this point. 119 } else { 120 EXPECT_EQ(thrd_join(thread_, NULL), thrd_success, 121 "thrd_join failed"); 122 } 123 } 124 125 void assert_thread_woken() { 126 while (state_ == STATE_ABOUT_TO_WAIT) { 127 sched_yield(); 128 } 129 EXPECT_EQ(state_, STATE_WAIT_RETURNED, "wrong state"); 130 } 131 132 void assert_thread_not_woken() { 133 EXPECT_EQ(state_, STATE_ABOUT_TO_WAIT, "wrong state"); 134 } 135 136 bool wait_for_timeout() { 137 ASSERT_EQ(state_, STATE_ABOUT_TO_WAIT, "wrong state"); 138 while (state_ == STATE_ABOUT_TO_WAIT) { 139 struct timespec wait_time = {0, 50 * 1000000 /* nanoseconds */}; 140 ASSERT_EQ(nanosleep(&wait_time, NULL), 0, "Error during sleep"); 141 } 142 EXPECT_EQ(state_, STATE_WAIT_RETURNED, "wrong state"); 143 return true; 144 } 145 146 void kill_thread() { 147 EXPECT_EQ(handle_, ZX_HANDLE_INVALID, "kill_thread called twice??"); 148 EXPECT_EQ(zx_handle_duplicate(thrd_get_zx_handle(thread_), 149 ZX_RIGHT_SAME_RIGHTS, &handle_), 150 ZX_OK, "zx_handle_duplicate failed on thread handle"); 151 EXPECT_EQ(zx_task_kill(handle_), ZX_OK, "zx_task_kill() failed"); 152 } 153 154 zx_handle_t get_thread_handle() { 155 return thrd_get_zx_handle(thread_); 156 } 157 158private: 159 static int wakeup_test_thread(void* thread_arg) { 160 TestThread* thread = reinterpret_cast<TestThread*>(thread_arg); 161 thread->state_ = STATE_ABOUT_TO_WAIT; 162 zx_time_t deadline = thread->timeout_in_ns_ == ZX_TIME_INFINITE ? ZX_TIME_INFINITE : 163 zx_deadline_after(thread->timeout_in_ns_); 164 zx_status_t rc = zx_futex_wait(const_cast<int32_t*>(thread->futex_addr_), 165 *thread->futex_addr_, deadline); 166 if (thread->timeout_in_ns_ == ZX_TIME_INFINITE) { 167 EXPECT_EQ(rc, ZX_OK, "Error while wait"); 168 } else { 169 EXPECT_EQ(rc, ZX_ERR_TIMED_OUT, "wait should have timedout"); 170 } 171 thread->state_ = STATE_WAIT_RETURNED; 172 return 0; 173 } 174 175 thrd_t thread_; 176 volatile int32_t* futex_addr_; 177 zx_duration_t timeout_in_ns_; 178 zx_handle_t handle_ = ZX_HANDLE_INVALID; 179 volatile enum { 180 STATE_STARTED = 100, 181 STATE_ABOUT_TO_WAIT = 200, 182 STATE_WAIT_RETURNED = 300, 183 } state_ = STATE_STARTED; 184}; 185 186void check_futex_wake(volatile int32_t* futex_addr, int nwake) { 187 zx_status_t rc = zx_futex_wake(const_cast<int32_t*>(futex_addr), nwake); 188 EXPECT_EQ(rc, ZX_OK, "error during futex wait"); 189} 190 191// Test that we can wake up a single thread. 192bool test_futex_wakeup() { 193 BEGIN_TEST; 194 volatile int32_t futex_value = 1; 195 TestThread thread(&futex_value); 196 check_futex_wake(&futex_value, INT_MAX); 197 thread.assert_thread_woken(); 198 END_TEST; 199} 200 201// Test that we can wake up multiple threads, and that futex_wake() heeds 202// the wakeup limit. 203bool test_futex_wakeup_limit() { 204 BEGIN_TEST; 205 volatile int32_t futex_value = 1; 206 TestThread thread1(&futex_value); 207 TestThread thread2(&futex_value); 208 TestThread thread3(&futex_value); 209 TestThread thread4(&futex_value); 210 check_futex_wake(&futex_value, 2); 211 // Test that threads are woken up in the order that they were added to 212 // the wait queue. This is not necessarily true for the Linux 213 // implementation of futexes, but it is true for Zircon's 214 // implementation. 215 thread1.assert_thread_woken(); 216 thread2.assert_thread_woken(); 217 thread3.assert_thread_not_woken(); 218 thread4.assert_thread_not_woken(); 219 220 // Clean up: Wake the remaining threads so that they can exit. 221 check_futex_wake(&futex_value, INT_MAX); 222 thread3.assert_thread_woken(); 223 thread4.assert_thread_woken(); 224 END_TEST; 225} 226 227// Check that futex_wait() and futex_wake() heed their address arguments 228// properly. A futex_wait() call on one address should not be woken by a 229// futex_wake() call on another address. 230bool test_futex_wakeup_address() { 231 BEGIN_TEST; 232 volatile int32_t futex_value1 = 1; 233 volatile int32_t futex_value2 = 1; 234 volatile int32_t dummy_addr = 1; 235 TestThread thread1(&futex_value1); 236 TestThread thread2(&futex_value2); 237 238 check_futex_wake(&dummy_addr, INT_MAX); 239 thread1.assert_thread_not_woken(); 240 thread2.assert_thread_not_woken(); 241 242 check_futex_wake(&futex_value1, INT_MAX); 243 thread1.assert_thread_woken(); 244 thread2.assert_thread_not_woken(); 245 246 // Clean up: Wake the remaining thread so that it can exit. 247 check_futex_wake(&futex_value2, INT_MAX); 248 thread2.assert_thread_woken(); 249 END_TEST; 250} 251 252// Check that when futex_wait() times out, it removes the thread from 253// the futex wait queue. 254bool test_futex_unqueued_on_timeout() { 255 BEGIN_TEST; 256 volatile int32_t futex_value = 1; 257 zx_status_t rc = zx_futex_wait(const_cast<int32_t*>(&futex_value), 258 futex_value, zx_deadline_after(1)); 259 ASSERT_EQ(rc, ZX_ERR_TIMED_OUT, "wait should have timedout"); 260 TestThread thread(&futex_value); 261 // If the earlier futex_wait() did not remove itself from the wait 262 // queue properly, the following futex_wake() call will attempt to wake 263 // a thread that is no longer waiting, rather than waking the child 264 // thread. 265 check_futex_wake(&futex_value, 1); 266 thread.assert_thread_woken(); 267 END_TEST; 268} 269 270// This tests for a specific bug in list handling. 271bool test_futex_unqueued_on_timeout_2() { 272 BEGIN_TEST; 273 volatile int32_t futex_value = 10; 274 TestThread thread1(&futex_value); 275 TestThread thread2(&futex_value, ZX_MSEC(200)); 276 ASSERT_TRUE(thread2.wait_for_timeout()); 277 // With the bug present, thread2 was removed but the futex wait queue's 278 // tail pointer still points to thread2. When another thread is 279 // enqueued, it gets added to the thread2 node and lost. 280 281 TestThread thread3(&futex_value); 282 check_futex_wake(&futex_value, 2); 283 thread1.assert_thread_woken(); 284 thread3.assert_thread_woken(); 285 END_TEST; 286} 287 288// This tests for a specific bug in list handling. 289bool test_futex_unqueued_on_timeout_3() { 290 BEGIN_TEST; 291 volatile int32_t futex_value = 10; 292 TestThread thread1(&futex_value, ZX_MSEC(400)); 293 TestThread thread2(&futex_value); 294 TestThread thread3(&futex_value); 295 ASSERT_TRUE(thread1.wait_for_timeout()); 296 // With the bug present, thread1 was removed but the futex wait queue 297 // is set to the thread2 node, which has an invalid (null) tail 298 // pointer. When another thread is enqueued, we get a null pointer 299 // dereference or an assertion failure. 300 301 TestThread thread4(&futex_value); 302 check_futex_wake(&futex_value, 3); 303 thread2.assert_thread_woken(); 304 thread3.assert_thread_woken(); 305 thread4.assert_thread_woken(); 306 END_TEST; 307} 308 309bool test_futex_requeue_value_mismatch() { 310 BEGIN_TEST; 311 int32_t futex_value1 = 100; 312 int32_t futex_value2 = 200; 313 zx_status_t rc = zx_futex_requeue(&futex_value1, 1, futex_value1 + 1, 314 &futex_value2, 1); 315 ASSERT_EQ(rc, ZX_ERR_BAD_STATE, "requeue should have returned bad state"); 316 END_TEST; 317} 318 319bool test_futex_requeue_same_addr() { 320 BEGIN_TEST; 321 int32_t futex_value = 100; 322 zx_status_t rc = zx_futex_requeue(&futex_value, 1, futex_value, 323 &futex_value, 1); 324 ASSERT_EQ(rc, ZX_ERR_INVALID_ARGS, "requeue should have returned invalid args"); 325 END_TEST; 326} 327 328// Test that futex_requeue() can wake up some threads and requeue others. 329bool test_futex_requeue() { 330 BEGIN_TEST; 331 volatile int32_t futex_value1 = 100; 332 volatile int32_t futex_value2 = 200; 333 TestThread thread1(&futex_value1); 334 TestThread thread2(&futex_value1); 335 TestThread thread3(&futex_value1); 336 TestThread thread4(&futex_value1); 337 TestThread thread5(&futex_value1); 338 TestThread thread6(&futex_value1); 339 340 zx_status_t rc = zx_futex_requeue( 341 const_cast<int32_t*>(&futex_value1), 3, futex_value1, 342 const_cast<int32_t*>(&futex_value2), 2); 343 ASSERT_EQ(rc, ZX_OK, "Error in requeue"); 344 // 3 of the threads should have been woken. 345 thread1.assert_thread_woken(); 346 thread2.assert_thread_woken(); 347 thread3.assert_thread_woken(); 348 thread4.assert_thread_not_woken(); 349 thread5.assert_thread_not_woken(); 350 thread6.assert_thread_not_woken(); 351 352 // Since 2 of the threads should have been requeued, waking all the 353 // threads on futex_value2 should wake 2 threads. 354 check_futex_wake(&futex_value2, INT_MAX); 355 thread4.assert_thread_woken(); 356 thread5.assert_thread_woken(); 357 thread6.assert_thread_not_woken(); 358 359 // Clean up: Wake the remaining thread so that it can exit. 360 check_futex_wake(&futex_value1, 1); 361 thread6.assert_thread_woken(); 362 END_TEST; 363} 364 365// Test the case where futex_wait() times out after having been moved to a 366// different queue by futex_requeue(). Check that futex_wait() removes 367// itself from the correct queue in that case. 368bool test_futex_requeue_unqueued_on_timeout() { 369 BEGIN_TEST; 370 zx_duration_t timeout_in_ns = ZX_MSEC(300); 371 volatile int32_t futex_value1 = 100; 372 volatile int32_t futex_value2 = 200; 373 TestThread thread1(&futex_value1, timeout_in_ns); 374 zx_status_t rc = zx_futex_requeue( 375 const_cast<int32_t*>(&futex_value1), 0, futex_value1, 376 const_cast<int32_t*>(&futex_value2), INT_MAX); 377 ASSERT_EQ(rc, ZX_OK, "Error in requeue"); 378 TestThread thread2(&futex_value2); 379 // thread1 and thread2 should now both be waiting on futex_value2. 380 381 ASSERT_TRUE(thread1.wait_for_timeout()); 382 thread2.assert_thread_not_woken(); 383 // thread1 should have removed itself from futex_value2's wait queue, 384 // so only thread2 should be waiting on futex_value2. We can test that 385 // by doing futex_wake() with count=1. 386 387 check_futex_wake(&futex_value2, 1); 388 thread2.assert_thread_woken(); 389 END_TEST; 390} 391 392// Test that we can successfully kill a thread that is waiting on a futex, 393// and that we can join the thread afterwards. This checks that waiting on 394// a futex does not leave the thread in an unkillable state. 395bool test_futex_thread_killed() { 396 BEGIN_TEST; 397 volatile int32_t futex_value = 1; 398 // Note: TestThread will ensure the kernel thread died, though 399 // it's not possible to thrd_join after killing the thread. 400 TestThread thread(&futex_value); 401 thread.kill_thread(); 402 403 // Check that the futex_wait() syscall does not return control to 404 // userland before the thread gets killed. 405 struct timespec wait_time = {0, 10 * 1000000 /* nanoseconds */}; 406 ASSERT_EQ(nanosleep(&wait_time, NULL), 0, "Error during sleep"); 407 thread.assert_thread_not_woken(); 408 409 END_TEST; 410} 411 412// Test that the futex_wait() syscall is restarted properly if the thread 413// calling it gets suspended and resumed. (This tests for a bug where the 414// futex_wait() syscall would return ZX_ERR_TIMED_OUT and not get restarted by 415// the syscall wrapper in the VDSO.) 416static bool test_futex_thread_suspended() { 417 BEGIN_TEST; 418 volatile int32_t futex_value = 1; 419 TestThread thread(&futex_value); 420 421 zx_handle_t suspend_token = ZX_HANDLE_INVALID; 422 ASSERT_EQ(zx_task_suspend_token(thread.get_thread_handle(), 423 &suspend_token), ZX_OK); 424 // Wait some time for the thread suspension to take effect. 425 struct timespec wait_time = {0, 10 * 1000000 /* nanoseconds */}; 426 ASSERT_EQ(nanosleep(&wait_time, NULL), 0, "Error during sleep"); 427 428 ASSERT_EQ(zx_handle_close(suspend_token), ZX_OK); 429 // Wait some time for the thread to resume and execute. 430 ASSERT_EQ(nanosleep(&wait_time, NULL), 0, "Error during sleep"); 431 432 thread.assert_thread_not_woken(); 433 check_futex_wake(&futex_value, 1); 434 thread.assert_thread_woken(); 435 436 END_TEST; 437} 438 439// Test that misaligned pointers cause futex syscalls to return a failure. 440static bool test_futex_misaligned() { 441 BEGIN_TEST; 442 443 // Make sure the whole thing is aligned, so the 'futex' member will 444 // definitely be misaligned. 445 alignas(zx_futex_t) struct { 446 uint8_t misalign; 447 zx_futex_t futex[2]; 448 } __attribute__((packed)) buffer; 449 zx_futex_t* const futex = &buffer.futex[0]; 450 zx_futex_t* const futex_2 = &buffer.futex[1]; 451 ASSERT_GT(alignof(zx_futex_t), 1); 452 ASSERT_NE((uintptr_t)futex % alignof(zx_futex_t), 0); 453 ASSERT_NE((uintptr_t)futex_2 % alignof(zx_futex_t), 0); 454 455 // zx_futex_requeue might check the waited-for value before it 456 // checks the second futex's alignment, so make sure the call is 457 // valid other than the alignment. (Also don't ask anybody to 458 // look at uninitialized stack space!) 459 memset(&buffer, 0, sizeof(buffer)); 460 461 ASSERT_EQ(zx_futex_wait(futex, 0, ZX_TIME_INFINITE), ZX_ERR_INVALID_ARGS); 462 ASSERT_EQ(zx_futex_wake(futex, 1), ZX_ERR_INVALID_ARGS); 463 ASSERT_EQ(zx_futex_requeue(futex, 1, 0, futex_2, 1), ZX_ERR_INVALID_ARGS); 464 465 END_TEST; 466} 467 468static void log(const char* str) { 469 zx_time_t now = zx_clock_get_monotonic(); 470 unittest_printf("[%08" PRIu64 ".%08" PRIu64 "]: %s", 471 now / 1000000000, now % 1000000000, str); 472} 473 474class Event { 475public: 476 Event() 477 : signaled_(0) {} 478 479 void wait() { 480 if (signaled_ == 0) { 481 zx_futex_wait(&signaled_, signaled_, ZX_TIME_INFINITE); 482 } 483 } 484 485 void signal() { 486 if (signaled_ == 0) { 487 signaled_ = 1; 488 zx_futex_wake(&signaled_, UINT32_MAX); 489 } 490 } 491 492private: 493 int32_t signaled_; 494}; 495 496static Event event; 497 498static int signal_thread1(void* arg) { 499 log("thread 1 waiting on event\n"); 500 event.wait(); 501 log("thread 1 done\n"); 502 return 0; 503} 504 505static int signal_thread2(void* arg) { 506 log("thread 2 waiting on event\n"); 507 event.wait(); 508 log("thread 2 done\n"); 509 return 0; 510} 511 512static int signal_thread3(void* arg) { 513 log("thread 3 waiting on event\n"); 514 event.wait(); 515 log("thread 3 done\n"); 516 return 0; 517} 518 519static bool test_event_signaling() { 520 BEGIN_TEST; 521 thrd_t thread1, thread2, thread3; 522 523 log("starting signal threads\n"); 524 thrd_create_with_name(&thread1, signal_thread1, NULL, "thread 1"); 525 thrd_create_with_name(&thread2, signal_thread2, NULL, "thread 2"); 526 thrd_create_with_name(&thread3, signal_thread3, NULL, "thread 3"); 527 528 zx_nanosleep(zx_deadline_after(ZX_MSEC(300))); 529 log("signaling event\n"); 530 event.signal(); 531 532 log("joining signal threads\n"); 533 thrd_join(thread1, NULL); 534 log("signal_thread 1 joined\n"); 535 thrd_join(thread2, NULL); 536 log("signal_thread 2 joined\n"); 537 thrd_join(thread3, NULL); 538 log("signal_thread 3 joined\n"); 539 END_TEST; 540} 541 542BEGIN_TEST_CASE(futex_tests) 543RUN_TEST(test_futex_wait_value_mismatch); 544RUN_TEST(test_futex_wait_timeout); 545RUN_TEST(test_futex_wait_timeout_elapsed); 546RUN_TEST(test_futex_wait_bad_address); 547RUN_TEST(test_futex_wakeup); 548RUN_TEST(test_futex_wakeup_limit); 549RUN_TEST(test_futex_wakeup_address); 550RUN_TEST(test_futex_unqueued_on_timeout); 551RUN_TEST(test_futex_unqueued_on_timeout_2); 552RUN_TEST(test_futex_unqueued_on_timeout_3); 553RUN_TEST(test_futex_requeue_value_mismatch); 554RUN_TEST(test_futex_requeue_same_addr); 555RUN_TEST(test_futex_requeue); 556RUN_TEST(test_futex_requeue_unqueued_on_timeout); 557RUN_TEST(test_futex_thread_killed); 558RUN_TEST(test_futex_thread_suspended); 559RUN_TEST(test_futex_misaligned); 560RUN_TEST(test_event_signaling); 561END_TEST_CASE(futex_tests) 562 563#ifndef BUILD_COMBINED_TESTS 564int main(int argc, char** argv) { 565 bool success = unittest_run_all_tests(argc, argv); 566 return success ? 0 : -1; 567} 568#endif 569