Running lock free

Допустим, вы торопитесь и вы знаете куда вы спешите. Если это не так - лучше сходите посмотреть чудесный фильм :)


Итак, мы пишем программу, которая торопится. Для того, чтобы успеть мы как взрослые пацаны решили все распараллелить по тредам, ведь уже 21-й век и меньше двух тредов осталось разве что в отсталых сотовых телефонах.

Однако, многие треды приводят к многим печалям и для того, чтобы все работало как мы задумали нам нужно как-то ограничивать паралелизм. Надежным способом для этого служит mutex/critical_section/semaphore/younameit - надежный примитив синхронизации, изобретенный ндесят лет назад. Сводится он, как известно, к блокированию исполнения всех тредов кроме одного. Правильное приготовление этого метода описано в том числе здесь. Возможно, для вас станет открытием, что при реализации busy wait lock-а лучше делать предварительную проверку с помощью volatile read на предмет возможности захвата перед попыткой собственно захвата с помощью locked инструкции. Т.е. перед xchg [cs], xz / lock cmpxchg [cs], xz лучше сначала сделать простое cmp [cs], 0.

Однако, если мы действительно торопимся, то исполнять всего один тред из всех это совсем не то, что мы хотим делать. Особенно, если система может этот единственный тред вытеснить и наш тред будет ожидать какого-нибудь "важного" процесса типа чтения блока из swap-file-a. Btw, если вы торопитесь, то swap лучше таки отрубить напрочь. По идее, вытеснение единственного работающего треда в процессе это редкость. Однако, если ваша система носит гордое имя FreeBSD, то событие становится вероятным. А если вы имели неосторожность запустить свою программу на кластере и обязательно ждете все N-сто ответов, то вероятность успешно превращается в закономерность.

Как же нам обойти проблему и не ждать? Для этого человечество в лице Мориса Херлихуя (затрудняюсь правильно скзаать по-русски Herlihy) изобрело wait free synchronization. Точнее, Морис доказал, что с помощью примитива CAS (compare and swap) можно реализовать любой wait free алгоритм. Инструкция CAS имеет 3 параметра - адрес переменной, тестовое значение и новое значение. Если в переменной лежит тествое значение, то CAS заменяет его на новое, иначе значение переменной не меняется. На правильных процессорах CAS может выполняться атомарно.

bool CAS(void **addr, void *new, void *old) if (*addr == old) { *addr = new; return true; } else return false; }

_Winnie C++ Colorizer

Способ сделать любую операцию lock free, например, такой: У нас есть некая структура данных и есть указатель на нее по имени Ptr. Мы берем текущее значение Ptr, пусть это pDataOld. Мы копируем структуру и проводим нужную операцию с копией. В результате мы получаем модифицированную копию pDataNew. Теперь мы с помощью CAS пытаемся заменить значение на новое: CAS(Ptr, pDataNew, pDataOld). Если CAS прошла успешно, то все получилось, если обломалась, то кто-то успел раньше нас и нам надо начинать с начала.

Начиная с 486-го в процессорах Intel есть реализация CAS под именем cmpxchg. Сделать ее atomic можно с помощью префикса lock. Звать ее можно так.

Отлично. Не откладывая в долгий ящик переходим на lock-free синхронизацию между потоками с помощью lock-free stack. Lock-free stack - пожалуй самая простая структура данных, которую можно использовать для передачи данных из одного потока в другой. Используя свеже полученные знания быстро кодаем:

Push(T *obj) n = new Node(obj); n->Val = obj; do { n->Next = Top; } while (!CAS(&Top, n, n->Next)); T *Pop() for(;;) { Node *t = Top; if (t == 0) return 0; if (CAS(&Top, t->Next, t)) { T *res = t->Val; delete t; // жопа-кеды return res; } }

_Winnie C++ Colorizer

Готово! Изготовив подобный код я не замедлил его запустить. И чудо произошло - программа магическим образом ускорилась даже на моем рабочем компе всего с 2-мя ядрами. Теперь она не ждала впустую на тупых critical sections, а молотила во все транзисторы.

Однако, у вас может возникнуть резонный вопрос - что это за комментарий такой после delete t? Дело в том, что если эту строчку закомментировать, то все будет отлично работать, разве что будет бесконечно есть память. Но вы можете это побороть регулярно рестартуя программу :) Если это не входит в ваши планы, то строчку придется вернуть и успех наступает неотвратимо. Тот, кто самостоятельно догадается о механизме возникновения успеха будет пользоваться моим безграничным уважением.

Для остальных сообщаю, что проблема имеет название ABA и происходит это так:

Первый тред выполняет Pop(), считывает текущий Top, записывает его в t и готовится стать отцом заменить Top на t->Next. Для этого он зачитывает t->Next в регистр и... Но в этом месте его прерывают. Его более шустрый сосед выполняет Pop(), который заканчивается успешно (у нас же lock-free) и выполняет пресловутый delete t; Т.е. теперь первый тред имеет указатель t, выставленный на объект, который уже во free memory. Но это ведь не страшно, ведь великий CAS защитит нас и не даст выставить Top в уже неправильный t->Next? Правильно? Конечно, правильно. Однако, второй тред не стоит на месте и в свою очередь зовет Push(), который успешно выполняется целиком. Теперь, если у нас перспективный memory manager, который первыми выделяет недавно освободившиеся блоки, то элемент Node, который Push() выделяет с помощью "new Node" будет в точности равен t из первого потока. Занавес, смена декораций и управление передается первому потоку. Первый поток выполняет CAS и CAS оказывается успешным, ведь Top таки равен t. Правда, хотя адрес и совпадает, это уже совсем другой объект и t->Next у него совсем другой, но первый поток об этом не узнает, ведь он уже прочитал t->Next в регистр. Хобана жопа-кеды. (Термин жопа-кеды - (с) by sim0nsays).

Что же делать, что же делать??? Очевидный ответ - не использовать delete t, однако, думаю, он не всем подойдет :) Далее мнения разошлись и предлагаются такие варианты исправления:

1. В качестве указателя использовать пару (указатель, счетчик). Счетчик прибавлять за каждую операцию. Другие публикации автора. Однако, этот метод требует более широкой операции CAS (т.н. CAS2), которая могла бы менять одновременно 8 байт для 32-битной и 16 байт для 64-битной платформы. Такие инструкции в x86 есть, но связываться с ними совсем не хочется. Это совсем не common path, а редко используемые инструкции. Поэтому у тех, кто их таки использует велика вероятность стать экспертом по особенностям реализации cmpxchg8b на каком-нибудь новом или маргинальном процессоре типа VIA. Еще в gamedev-е меня научили тратить время более продуктивным способом, чем искать ошибки в hardware/драйверах. Можно, конечно, реализовать и без CAS2 и даже есть такая бесплатная "реализация". Однако, так как их замена CAS2 не является атомарной, то и вся эта бесплатная "реализация" некорректна.

1а. Т.к. CAS2 редко где есть, то расположим counter в младших битах указателя. Без комментариев.

1б. Используем в качестве указателя 32-битное число. Скажем, в старших битах индекс в массиве, в младших - counter. Уже лучше, но тогда нам нужно либо ограничить сверху количество Node, которые потребуются программе (если закажем мало - стремно, могут кончится, если много - жалко память), либо нужен lock-free dynamic array. К тому же counter может wrap-нуться...

2. Hazard pointers - вроде изобретение небезызвестного Doug Lea. Рабочая идея, но треды, которые знают про другие треды... Пожалуйста, без меня, я такого с memory manager`ом уже наелся :)

3. Cнабдить каждый Node RefCounter-ом. Изобретение товарища Valois.

Изобретении Valois-a мне сначала понравилось. Выглядит самым простым решением - добавляем в Node RefCount. Чтение указателей на Node реализуется с помощью функции SafeRead:

Node *SafeRead(Node *volatile*ptr) for(;;) { Node * volatile res = *ptr; if (res == 0) return 0; atomic_add(res->RefCount, 1); if (res == *ptr) return res; else atomic_add(res->RefCount, -1); }

_Winnie C++ Colorizer

Т.е. если несколько объектов прочитали в Pop() указатель на один и тот же объект, то объект не будет освобожден, пока все треды не прекратят на него смотреть. ABA удалось избежать. Открываем шампанское!

Закрываем шампанское. Теперь мы можем прибавлять RefCount объекту, который был освобожден в соседнем треде и уже болтается во free memory! Для этого переключение потоков должно произойти между "res = *ptr" и "atomic_add()". Мы, конечно, после этого вернем все "на место" и вычтем прибавленную единичку, но какие волшебные баги это может породить, если память из под Node была использована в другом месте мне даже представить страшно. То ли я чего-то не понял, то ли товарищ Valois предлагает форменную диверсию или забыл сообщить, что под Node надо сделать выделенный пул и выделять память под Node только из него. Да и race-condition-ами пугают.

Посмотрев на все это и отчаявшись найти короткий кусок кода, который делает только то, что нужно и ничего больше, напесал свой. Для решения проблемы ABA я сделал RefCount на весь стек. Память будет освободжаться только когда никто не использует стек. Конечно, если все треды только и делают, что лезут в стек такое никогда не случится и память будет поглощаться неограниченно. Однако, в моем случае использование таких стеков гораздо менее напряженное. Код здесь. Если вы вдруг найдете ошибку в этом коде буду очень вам признателен.

Рассмотренные нами реализации стека - lock free, но вовсе не wait-free, как могло показаться. Ведь в них таки есть циклы и они могут в них крутиться, а wait-free гарантирует выполнение за конечное число шагов. Ну что, хотите по-настоящему? Тогда вас заинтересуют wait-free алгоритмы (подробнее про различия).

Например, wait free stack по имени elimination-backoff stack

Удачи!

Update Ошибку наконец нашли, ура! Исправить, имхо, таки можно, например, так