Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Nice write up. Just to flesh out the third class using C++11.

    std::atomic<std::atomic<bool>*> lock;

    // Code that uses lock

    std::atomic<bool> my_flag = false;
    auto* other_flag = lock.exchange(&my_flag);

    // spin   
    if(other_flag) while(!other_flag->load());

    // You have the lock. Do work

    // Release lock

    auto* next_flag = &my_flag;
    if(!lock.compare_exchange_strong(next_flag, nullptr)) next_flag->store(true);


The way you wrote it there is a use-after-free because other_flag is not valid anymore immediately after the previous holder exits. Instead you spin on your own flag (which the holder sets to true when releasing the lock).

The correct code requires the local atomic to be a pointer to struct, containing both a pointer to the next link and the "still locked" flag. Alternatively, the locked flag can be snuck into the low bit of the pointer.

See https://lwn.net/Articles/590243/ for the full description of the algorithm.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: