Хорошие вопросы, спасибо! Отвечу сначала на первый.
Как всегда, ответ будет двоякий, — и не правильно, и правильно.
Для большинства методов внешнюю rcu-блокировку своими силами выставлять не нужно. Все методы контейнеров делают это сами: блокируют и разблокируют RCU в своем теле там, где нужно.
Более того, для erase-методов (тех, кто удаляет элементы из контейнера) это недопустимо, так как erase-методы в своем теле требуют вызова rcu.retire_ptr(). А rcu.retire_ptr() приводит (или может приводить в случае буферизованного rcu) к rcu.synchronize(), который ожидает завершения текущего grace-периода, то есть снятия блокировки. Получим deadlock.
Поэтому в описании erase-методов на кошерном нижегородском английском явно написано, что RCU не должен быть блокирован.
Но. Сейчас я работаю над новой фичей: добавить в lock-free set/map методы, возвращающие указатель на элемент контейнера. Это будут методы get() — поиск элемента по ключу, и extract() — удаление по ключу, оба возвращают указатель на найденный элемент. В RCU-специализациях таких контейнеров придется блокировать RCU перед вызовом явно в пользовательском коде, — именно то, что вы написали.
Вопросы 2 и 3 взаимосвязаны и требуют приложения мозга. Попробую составить пример с одним flip-and-wait, который ломает RCU. Отвечу позже
Но для mutex-based логики не нужны lock-free навороты. Mutex-контейнеры намного проще по внутреннему строению.
ИМХО, мы увидим, насколько быстрее/медленнее HP по сравнению с MTX, но ничего не сможем сказать о контейнере. А ведь в программе нам важен именно контейнер, а не костыль к нему в виде схемы управления памятью (SMR — именно костыль).
А, понял.
Мысль интересная, только времени, боюсь, на это уйдет много, а результат неясен.
Дело в том, что для разных схем SMR часто приходится писать разные специализации контейнеров. Для HP-like схем — HP, HRC, PTB, — мне удалось свести реализацию контейнеров к одной, а вот для RCU пришлось писать отдельные специализации template.
Боюсь, для гипотетического cds::gc::MTX вылезет ещё одна специализация.
Нет, не пробовал.
Lock-free структурами данных я заинтересовался именно благодаря борьбе с мьютексами.
Вместо реализации схемы на мьютексах проще сравнить, например, std::map/std::queue под мьютексом с lock-free аналогом. Сразу скажу, результат будет неоднозначный: можно получить как проседание, так и взлет производительности. Все зависит от железа и задачи. Общее наблюдение — чем «сервернее» железо, тем хуже мьютексы и лучше lock-free.
Наконец-то! Автору — огромный респект.
Пару лет назад я пробовал донести коллегам эту мысль — использование сопрограмм и переключения контекста — в асинхронном программировании, но многие не поняли, чем такой подход лучше прямого «чисто асинхронного» подхода.
А выгода в том, что если наш алгоритм обработки сам должен сходить в кучу мест по сети (и тоже, естественно, асинхронно) и по окончании аггрегировать результат, то алгоритм распадается на кучу никак программно не связанных кусков, связанных доморощенным объектом-контекстом, поддерживать которые — адъ. При «сопрограммном» подходе алгоритм выглядит единым последовательным действием без объекта-контекста (все нужное — в локальных данных), — удобно сопровождать. Вся асинхронность скрыта внутри обращений к источникам данных.
На реинкарнацию сопрограмм меня натолкнул Lua с его концепцией thread'ов (которые в Lua — сопрограммы).
Кстати, boost:asio мне не очень нравится именно потому, что он подталкивает к использованию «традиционного» асинхронного подхода, когда алгоритм распадается на кучу несвязанных обработчиков. Но это ИМХО
Да, вы правы, наверное, сказывается C-шный подход. Я не знаток модели памяти явы, слышал только, что в ней применяется модель sequential consistency, и существует довольно обширное её описание. Собственно, при проектировании модели памяти C++ решали две задачи: добиться более компактного описания (за это ратовал, вроде бы, тот же H.Boehm) + большей свободы выбора (= большей эффективности кода, где это можно).
Как я рассуждаю в терминах барьеров — хороший вопрос. На самом деле, все довольно просто: я рассуждаю в терминах абстрактных memory ordering, заданных стандартом, при этом имея в виду, что за ними кроется, — в основном это переупорядочение компилятором (acquire/release-полубарьеры), и только во вторую очередь — процессором. При этом как реализован тот или иной memory ordering на конкретной архитектуре, мне не важно, — я надеюсь на реализацию atomic в STL. К сожалению, мне пришлось спускаться ниже и делать свой atomic-велосипед. Тому было (частично и есть) две причины:
во времена моих первых шагов не было C++11
разработчики компиляторов до сих пор, похоже, не сошлись во мнении, как должна быть реализована C++11 MM. На это намекает недавно обнаруженный баг в libcds с использованием Clang + libc++ (родная реализация STL для Clang). Опыт учит — ищи ошибку прежде всего у себя, но странное поведение, — крах в однопоточном коде, где всё должно работать и на relaxed atomic, — наводит на мысль, что дело все-таки в компиляторе
Мыслить в терминах отношений happens-before и пр. у меня как-то не особо получается. Когда вижу чью-либо статью, основанную на отношениях, — кажется, всё понимаю, а вот сам применить на практике — увы… Судя по обилию блогов/заметок о C++11 atomic, такой мозговой клинч наблюдается не только у меня, — многие в разговоре об atomic переходят к рассуждениям о барьерах. Быть может, просто не хватает практики — «об этом надо говорить (и спорить)».
Я согласен, что отношения — более правильный подход. Вот только он слишком абстрактен, приводит к огромным по размеру выкладкам в случае более-менее сложного алгоритма, в котором взаимодействуют более двух atomic, и пока ещё нет инструментов (точнее, только-только появляются первые) по проверке его применения на практике (инструментов верификации).
Проблема чем-то напоминает понятия формальной системы и её интерпретации: можно построить очень интересную формальную теорию, но найти ей интерпретацию, то есть её воплощение в реальном мире, бывает просто невозможно. Путь познания, как правило, другой: от интерпретации (наблюдаемого в жизни) — к формальному описанию. В нашем частном случае формальная модель — это happeds-before, synchronized-with и пр. отношения, а интерпретация — в конечном счете, банальные барьеры.
Вообще, все сказанное мной в статьях и комментариях, — это мое ИМХО, кое в чем я до конца не уверен. Например, в том, правильно ли я проставляю memory ordering в libcds ;-)
Нетрадиционные костыли, призванные «более улучшить» традиционные костыли (в виде кэша) не рассматриваем, — для них требуются специальные костыли методы применения, о которых, как правило, подробно написано в разных местах мануалов.
Согласен, во фразе, наверное, не хватает "особо требует верификации".
Про data race — тоже согласен. По сути, обращение к атомарной переменной — это всегда data race; можно сказать, что это легализованный стандартом data race, все остальные — UB.
Про отношения happend-before и пр. Подготавливая эту заметку, я метался между подходом C++11 (отношениями) и тем, из чего вырос этот подход — барьерами. Не умаляя достоинств отношений и аксиоматики, хочу сказать, что всё же более приземленный подход, основанный на постановке барьеров, мне импонирует больше, он для меня более понятен и более применим. Барьер я могу пощупать, он материален, он воплощается в инструкции процессора. Об отношениях пусть говорят люди более сведущие, например, А.Вильямс.
Я не видел работ, объясняющих расстановку memory ordering с точки зрения happens-before и прочих в чем-то более сложном, чем стек или самая простая очередь. Да, существует ряд исследований, посвященных попыткам автоматизации расстановки memory ordering в алгоритмах (насколько помню, Dechev и другие), но серьезных успехов к настоящему времени не достигнуто, насколько я знаю.
Мне кажется, что для модели памяти C++11 не хватает типичных паттернов применения. По моим наблюдениям, такие паттерны все-таки существуют, по крайней мере в алгоритмах lock-free структур данных, но пока не нашлась пресловутая «банда четырех» для их обнаружения и «легализации».
Про тестирование.
Набор тестов, включенных в либу, прогоняется постоянно. Перед очередным релизом все тесты прогоняются для всех компиляторов — GCC от 4.3 до 4.8, MS VC++ 2008 — 2012, CLang 3.0 — 3.3 — в основном на Linux 32/64 и Windows 32/64 десктопах. Один прогон полного теста занимает порядка 12 часов (очень зависит от железа), так что суммарно тесты занимают где-то неделю. После тестирования на десктопах — прогон на серверах. Здесь мне очень помогает GCCfarm — там в основном Linux, зато хороший зоопарк процессоров. На прошлых работах был хороший зоопарк железа и осей — на них отлаживал свой atomic-велосипед.
Если всё OK — выкладываю релиз.
Вообще тестирование lock-free алгоритмов в многопотоковом режиме — интересная тема. Например, как тестировать очередь? Как проверить в multithread, что основное свойство очереди — FIFO — не нарушается? То же самое — с set/map: неудача поиска по ключу — это что? Элемент ещё не включен в контейнер, уже удален из него, или это ошибка в алгоритме поиска?..
В патологических случаях приходится применять тяжелые инструменты типа valgrind. Тормозная вещь, но иногда помогает уловить чтение удаленных данных и т.п.
Сейчас присматриваюсь к новому инструменту — ThreadSanitizer (включено в Clang 3.2 и GCC 4.8 x86). По описаниям вещь более подходящая.
По поводу проектов.
libcds выросла из реальной исследовательской работы, поэтому кое-что я применял (и применяю) в проприетарных серверных разработках.
Судя по feedback и поиску в инете, определенное распространение либа получил в студенческих кругах — видимо, потому, что сделана по опубликованным работам с указанием источников ;-) Студентам легко писать лабы/курсовики )))))
Интересный факт: после того, как я влез в lock-free и стал его курить применять, я все чаще стал избегать применения каких-либо разделяемых данных. Поразительно, что в 50% случаев удается-таки найти приемлемое решение без shared data.
Вот что я нашел по поводу этих барьеров:
#LoadStore предотвращает переупорядочение инструкций, то есть спекулятивное выполнение. Например, такое переупорядочение может иметь место, если чтение (load) привело к промаху в кэше (и пошел работать асинхронный MESI-протокол), а следующая инструкция store может быть выполнена немедленно — все уже находится в кэше CPU в состоянии Exclusive. Тогда CPU может выполнить сначала store, а затем (когда отработает MESI) load. Барьер #LoadStore как раз и запрещает подобное переупорядочение.
Про барьер #StoreLoad написано, что он приводит фактически к полной синхронизации — сбросу store buffer CPU в кэш. Чтобы все чтения (loads) после барьера могли увидеть новые значения, находящиеся в store buffer.
Мне тоже не совсем понятно, почему это приводит обязательно к сбросу store buffer в кэш, то есть к полной синхронизации… Но это свойство всех современных архитектур.
Описываемое поведение происходит на вымышленном ущербном процессоре, в котором есть кэш и есть store buffer, никак с кэшем не связанный по сути. Просто буфер записи.
Автор в статье пытается выстроить архитектуру, в которой не было бы артефактов, и в каждой итерации на примерах показывает, какие грабли исчезли, а какие появились. Не стоит отождествлять CPU на каждой итерации с каким-то реальным процессором. Думаю, такие «CPU» существуют только в лабораториях вендоров и только в виде программной модели.
Субаллокатор и offset-указатели… Да, согласен, на этом пути можно добиться многого. Готовых решений, заточенных под lock-free, я не знаю. Быть может, вы будете первым, кто реализует подобное?.. Я серьезно, без всякой иронии. Дерзайте!
Наверное, я был недостаточно точен.
Я не говорю про ненужность (и тем более вредность) вообще, я говорю про избыточность для атомарных переменных. Атомарная переменная — это переменная типа atomic<T>. Несмотря на то, что она определена в STL и, вроде бы, независима от самого языка, на самом деле на atomic<T> навешано довольно много семантики, то есть [очень грубо] можно считать, что atomic<T> является ключевым словом. И компиляторы, поддерживающие C++11 atomic, были существенно переработаны внутри, чтобы поддержать требования стандарта, новую модель памяти.
Были обсуждения при подготовке стандарта, нужно или нет навешивать acquire/release семантику на чтение/записть volatile-переменных, как это сделали в C#. И было принято решение — не нужно. Эту семантику навесили на atomic<T>.
Кстати, один из аргументов против придания volatile какого-то статуса в C++11 был таким:
Эта структура очень большая (по объему) и никак не влезает в atomic. Поэтому и acquire/release семантику на её представителей (x в данном примере) навесить не получится.
Никто не отменял (или переопределял) значения volatile, как это случилось с auto в C++11. Используйте на здоровье! Просто надо помнить, что для атомарных переменных volatile избыточна.
Насчет выравнивания. Атомарная переменная должна быть правильно выровнена. Это необходимое условие атомарности. Иначе — UB.
По поводу packed — это нас x86 избаловала. На другой архитектуре при попытке обращения к невыровненному int мы получим segmentation fault. Это и называется в стандарте «неопределенным поведением» (UB).
Про Java. Могу сказать, что изобретатели lock-free алгоритмов очень любят Java (вся книга Shavit & Herlihy «The Art of Multiprocessor programming» наполнена примерами только на Java). И это понятно: в Java они избавлены от необходимости следить за указателями, за правильным (в подходящий момент) удалением и пр. — за них все делает GC. Поэтому портировать Java-алгоритмы на C++ бывает довольно сложно.
Существуют ли lock-free контейнеры с поддержкой такой операции?
Явных контейнеров с перетаскиванием не встречал. Хотя такая задача иногда возникала на практике. Обходился своими силами — если понимаешь, как контейнер реализован (вернее, когда можно удаленный элемент контейнера 1 поместить в контейнер 2, — это уже из области алгоритмов safe memory reclamation типа Hazard Pointer), это не представляет труда.
внедрение счетчика в неиспользуемые биты указателя — совершенно верно! Это техника tagged pointers. В статье я утверждаю, что для неё нужен dwCAS, но на самом деле — не всегда. Можно использовать и неиспользуемые биты указателя. В современных 64-битовых платформах на самом деле адресуется, вроде бы, 48 бит (или 42? — не помню). Остальное может быть, в принципе, использовано. Насколько я знаю, boost.lockfree построен на этом.
Мне такой подход не нравится, — нет никакой уверенности, что в какой-то прекрасный момент производитель не сделает настоящий 64-битный адрес. И всё — наш алгоритм отправится на свалку :-(
Про достаточную разрядность счетчика — интересный и хороший вопрос! На этот счет были исследования. Насколько я помню (пруф сейчас не готов указать), их результатом было: достаточно 32-битового счетчика. Меньше — можно попасть на переполнение в неподходящий момент (а следствие — ABA). Обоснование: таймслот, выделяемый ОС для потока. Например, где-то в mail-list разработчиков Линукса я встречал такую оценку таймслота: 300 — 500 тысяч «простых» инструкций. После этого поток вытесняется. 300 тысяч не влезут в 16 бит. Это ещё один аргумент против использования 16 бит 64-битового указателя.
Про специальный аллокатор. Здесь я ничего сказать не могу, — очень большая тема. Я остановился на схемах безопасного освобождения памяти (Hazard Pointer, Pass-the-Buck, RCU), они решают все эти вопросы про ABA и освобождение (конечно, при правильном приготовлении :-) Повесить это на аллокатор… Нужно думать
Мне трудно ответить на этот вопрос, так как я не знаток Java. Поэтому могу только поразмышлять.
Если мы говорим о физическом удалении, то ABA-проблема возникает при удалении (delete) и тут же включении вновь (allocate) некоего элемента. Удаление в C++ — это физическое удаление. В языках же с GC физического удаления не произойдет, пока кто-то держит ссылку на удаляемый элемент. Такую локальную ссылку какой-то поток держит (тот, который работает с CAS, на котором возникает ABA). Поэтому мой ответ — да, языки с GC свободны от ABA-проблемы.
Ответ на второй вопрос — решим ли мы проблему если никогда не будем освобождать выделенную память — скорее отрицательный. В общем случае не решим.
Рассмотрим такой пример, на двух lock-free интрузивных стеках (интрузивный контейнер — хранит не копии данных, а сами данные, — сишный подход, позволяет избавиться от аллокатора в контейнере): поток 1 делает stack1.pop(), доходит до CAS и, к примеру, вытесняется. Поток 2, пока первый вытеснен, успевает сделать:
T * a = stack1.pop() ;
T * anext = stack1.pop() ;
stack1.push( a ) ;
stack2.push( anext );
Вслед за этим поток 1 выполняет CAS, меняя a на anext, который он запомнил. Но anext теперь включен в stack2! Нарушение stack1: он теперь будет указывать в stack2. ABA-проблема, без освобождения выделенной памяти.
Кажется, что этот пример входит в противоречие с моим первым утверждением — языки с GC свободны от ABA. На самом деле, противоречия нет. Языки с GC не позволяют работать с сырыми указателями (а если всё же позволяют, то на ваш страх и риск).
PS: смотрите внимательно, я могу наврать в примерах. ABA — очень тонкая вещь для обнаружения и объяснения, хотя и очень понятная, когда (и если :) разберешься.
Совершенно правильно.
Я намеренно разделил CAS и compare_exchange. compare_exchange — это из C++11, аргумент nExpected передается по ссылке и на выходе содержит текущее значение *pAddr. Именно в этом часто бывают ошибки/описки или излишне чтение в CAS-циклах.
Да, volatile в C++11 излишне. Более того, если строго следовать стандарту, оно приводит к data race (ведь volatile обычно используют для разделяемых данных), что, согласно нового стандарта, есть undefined behaviour. То есть поведение программы никак не гарантируется.
Data race не будет только на атомарных переменных atomic (это постулируется стандартом). Поэтому в C++11 в качестве флажков нужно использовать atomic.
Compare_exchange вовсе не обязателен — можно использовать и atomic load/store (разумеется, с правильным memory_order).
Вообще про volatile в C++ была большая и интересная дискуссия среди авторов нового стандарта. С кучей примеров pro и contra. В конце концов решили, что в C++11 не будут наделять volatile какой-то магической силой, как это сделали в Java или C#.
Я так подробно расписывал compare_exchange не потому, что только его нужно использовать, а потому, что он самый удобный и распространенный для lock-free алгоритмов. Конечно, есть множество алгоритмов, построенных без compare_exchange.
Спасибо, очень интересный для меня материал, — как ваша заметка, так и ссылки. Радует, что прогресс у hardware-вендоров не стоит на месте и вместо гигагерцев они наконец-то серьезно озаботились внутренней архитектурой и разруливанием узких мест в процессорах.
По сути — да, не меняется.
Но иногда 32 бита — мало. 32 бита — это выравненность по 4 байтам, то есть 2 младших бита адреса всегда нули. В 64 — имеем нулевыми 3 младших бита. В lock-free алгоритмах часто нужно вместе с некоторым адресом атомарно поменять и некоторые статусы. Для статусов необходимо использовать как раз эти младшие свободные биты в адресе (это так называемый marked pointer), чтобы и адрес, и статусы влезли в CAS. Естественно, в 3 бита влезет больше статусов, чем в 2. Иногда этот лишний бит в 64 бывает очень полезен. А в 32-битовой архитектуре приходится явно указывать выравнивание по 8 байтам, чтобы алгоритм был работоспособным. И тут начинаются танцы с бубном — aligned-распределение памяти (оно зачастую намного медленнее и прожорливей), компиляторно-зависимые конструкции и ограничения и пр.
Совершенно согласен! В своей повседневной профессиональной деятельности я уже лет 5 сижу на 64 битах.
Но 32 бита ещё довольно распространены, особенно для десктопных и «смартфонных» приложений. К тому же, когда пишешь некую библиотеку с замахом на общность, — 32 бита дисциплинируют. Иногда приходится поломать голову, как засунуть то, что хорошо вписывается в 64-битовую архитектуру, в 32 бита.
Как всегда, ответ будет двоякий, — и не правильно, и правильно.
Для большинства методов внешнюю rcu-блокировку своими силами выставлять не нужно. Все методы контейнеров делают это сами: блокируют и разблокируют RCU в своем теле там, где нужно.
Более того, для erase-методов (тех, кто удаляет элементы из контейнера) это недопустимо, так как erase-методы в своем теле требуют вызова
rcu.retire_ptr(). Аrcu.retire_ptr()приводит (или может приводить в случае буферизованного rcu) кrcu.synchronize(), который ожидает завершения текущего grace-периода, то есть снятия блокировки. Получим deadlock.Поэтому в описании erase-методов на кошерном нижегородском английском явно написано, что RCU не должен быть блокирован.
Но. Сейчас я работаю над новой фичей: добавить в lock-free set/map методы, возвращающие указатель на элемент контейнера. Это будут методы
get()— поиск элемента по ключу, иextract()— удаление по ключу, оба возвращают указатель на найденный элемент. В RCU-специализациях таких контейнеров придется блокировать RCU перед вызовом явно в пользовательском коде, — именно то, что вы написали.Вопросы 2 и 3 взаимосвязаны и требуют приложения мозга. Попробую составить пример с одним flip-and-wait, который ломает RCU. Отвечу позже
ИМХО, мы увидим, насколько быстрее/медленнее HP по сравнению с MTX, но ничего не сможем сказать о контейнере. А ведь в программе нам важен именно контейнер, а не костыль к нему в виде схемы управления памятью (SMR — именно костыль).
Мысль интересная, только времени, боюсь, на это уйдет много, а результат неясен.
Дело в том, что для разных схем SMR часто приходится писать разные специализации контейнеров. Для HP-like схем — HP, HRC, PTB, — мне удалось свести реализацию контейнеров к одной, а вот для RCU пришлось писать отдельные специализации template.
Боюсь, для гипотетического cds::gc::MTX вылезет ещё одна специализация.
Lock-free структурами данных я заинтересовался именно благодаря борьбе с мьютексами.
Вместо реализации схемы на мьютексах проще сравнить, например, std::map/std::queue под мьютексом с lock-free аналогом. Сразу скажу, результат будет неоднозначный: можно получить как проседание, так и взлет производительности. Все зависит от железа и задачи. Общее наблюдение — чем «сервернее» железо, тем хуже мьютексы и лучше lock-free.
Пару лет назад я пробовал донести коллегам эту мысль — использование сопрограмм и переключения контекста — в асинхронном программировании, но многие не поняли, чем такой подход лучше прямого «чисто асинхронного» подхода.
А выгода в том, что если наш алгоритм обработки сам должен сходить в кучу мест по сети (и тоже, естественно, асинхронно) и по окончании аггрегировать результат, то алгоритм распадается на кучу никак программно не связанных кусков, связанных доморощенным объектом-контекстом, поддерживать которые — адъ. При «сопрограммном» подходе алгоритм выглядит единым последовательным действием без объекта-контекста (все нужное — в локальных данных), — удобно сопровождать. Вся асинхронность скрыта внутри обращений к источникам данных.
На реинкарнацию сопрограмм меня натолкнул Lua с его концепцией thread'ов (которые в Lua — сопрограммы).
Кстати, boost:asio мне не очень нравится именно потому, что он подталкивает к использованию «традиционного» асинхронного подхода, когда алгоритм распадается на кучу несвязанных обработчиков. Но это ИМХО
Как я рассуждаю в терминах барьеров — хороший вопрос. На самом деле, все довольно просто: я рассуждаю в терминах абстрактных memory ordering, заданных стандартом, при этом имея в виду, что за ними кроется, — в основном это переупорядочение компилятором (acquire/release-полубарьеры), и только во вторую очередь — процессором. При этом как реализован тот или иной memory ordering на конкретной архитектуре, мне не важно, — я надеюсь на реализацию atomic в STL. К сожалению, мне пришлось спускаться ниже и делать свой atomic-велосипед. Тому было (частично и есть) две причины:
Мыслить в терминах отношений happens-before и пр. у меня как-то не особо получается. Когда вижу чью-либо статью, основанную на отношениях, — кажется, всё понимаю, а вот сам применить на практике — увы… Судя по обилию блогов/заметок о C++11 atomic, такой мозговой клинч наблюдается не только у меня, — многие в разговоре об atomic переходят к рассуждениям о барьерах. Быть может, просто не хватает практики — «об этом надо говорить (и спорить)».
Я согласен, что отношения — более правильный подход. Вот только он слишком абстрактен, приводит к огромным по размеру выкладкам в случае более-менее сложного алгоритма, в котором взаимодействуют более двух atomic, и пока ещё нет инструментов (точнее, только-только появляются первые) по проверке его применения на практике (инструментов верификации).
Проблема чем-то напоминает понятия формальной системы и её интерпретации: можно построить очень интересную формальную теорию, но найти ей интерпретацию, то есть её воплощение в реальном мире, бывает просто невозможно. Путь познания, как правило, другой: от интерпретации (наблюдаемого в жизни) — к формальному описанию. В нашем частном случае формальная модель — это happeds-before, synchronized-with и пр. отношения, а интерпретация — в конечном счете, банальные барьеры.
Вообще, все сказанное мной в статьях и комментариях, — это мое ИМХО, кое в чем я до конца не уверен. Например, в том, правильно ли я проставляю memory ordering в libcds ;-)
костылиметоды применения, о которых, как правило, подробно написано в разных местах мануалов.Про data race — тоже согласен. По сути, обращение к атомарной переменной — это всегда data race; можно сказать, что это легализованный стандартом data race, все остальные — UB.
Про отношения happend-before и пр. Подготавливая эту заметку, я метался между подходом C++11 (отношениями) и тем, из чего вырос этот подход — барьерами. Не умаляя достоинств отношений и аксиоматики, хочу сказать, что всё же более приземленный подход, основанный на постановке барьеров, мне импонирует больше, он для меня более понятен и более применим. Барьер я могу пощупать, он материален, он воплощается в инструкции процессора. Об отношениях пусть говорят люди более сведущие, например, А.Вильямс.
Я не видел работ, объясняющих расстановку memory ordering с точки зрения happens-before и прочих в чем-то более сложном, чем стек или самая простая очередь. Да, существует ряд исследований, посвященных попыткам автоматизации расстановки memory ordering в алгоритмах (насколько помню, Dechev и другие), но серьезных успехов к настоящему времени не достигнуто, насколько я знаю.
Мне кажется, что для модели памяти C++11 не хватает типичных паттернов применения. По моим наблюдениям, такие паттерны все-таки существуют, по крайней мере в алгоритмах lock-free структур данных, но пока не нашлась пресловутая «банда четырех» для их обнаружения и «легализации».
Набор тестов, включенных в либу, прогоняется постоянно. Перед очередным релизом все тесты прогоняются для всех компиляторов — GCC от 4.3 до 4.8, MS VC++ 2008 — 2012, CLang 3.0 — 3.3 — в основном на Linux 32/64 и Windows 32/64 десктопах. Один прогон полного теста занимает порядка 12 часов (очень зависит от железа), так что суммарно тесты занимают где-то неделю. После тестирования на десктопах — прогон на серверах. Здесь мне очень помогает GCCfarm — там в основном Linux, зато хороший зоопарк процессоров. На прошлых работах был хороший зоопарк железа и осей — на них отлаживал свой atomic-велосипед.
Если всё OK — выкладываю релиз.
Вообще тестирование lock-free алгоритмов в многопотоковом режиме — интересная тема. Например, как тестировать очередь? Как проверить в multithread, что основное свойство очереди — FIFO — не нарушается? То же самое — с set/map: неудача поиска по ключу — это что? Элемент ещё не включен в контейнер, уже удален из него, или это ошибка в алгоритме поиска?..
В патологических случаях приходится применять тяжелые инструменты типа valgrind. Тормозная вещь, но иногда помогает уловить чтение удаленных данных и т.п.
Сейчас присматриваюсь к новому инструменту — ThreadSanitizer (включено в Clang 3.2 и GCC 4.8 x86). По описаниям вещь более подходящая.
По поводу проектов.
libcds выросла из реальной исследовательской работы, поэтому кое-что я применял (и применяю) в проприетарных серверных разработках.
Судя по feedback и поиску в инете, определенное распространение либа получил в студенческих кругах — видимо, потому, что сделана по опубликованным работам с указанием источников ;-) Студентам легко писать лабы/курсовики )))))
Интересный факт: после того, как я влез в lock-free и стал его
куритьприменять, я все чаще стал избегать применения каких-либо разделяемых данных. Поразительно, что в 50% случаев удается-таки найти приемлемое решение без shared data.#LoadStore предотвращает переупорядочение инструкций, то есть спекулятивное выполнение. Например, такое переупорядочение может иметь место, если чтение (load) привело к промаху в кэше (и пошел работать асинхронный MESI-протокол), а следующая инструкция store может быть выполнена немедленно — все уже находится в кэше CPU в состоянии Exclusive. Тогда CPU может выполнить сначала store, а затем (когда отработает MESI) load. Барьер #LoadStore как раз и запрещает подобное переупорядочение.
Про барьер #StoreLoad написано, что он приводит фактически к полной синхронизации — сбросу store buffer CPU в кэш. Чтобы все чтения (loads) после барьера могли увидеть новые значения, находящиеся в store buffer.
Мне тоже не совсем понятно, почему это приводит обязательно к сбросу store buffer в кэш, то есть к полной синхронизации… Но это свойство всех современных архитектур.
Автор в статье пытается выстроить архитектуру, в которой не было бы артефактов, и в каждой итерации на примерах показывает, какие грабли исчезли, а какие появились. Не стоит отождествлять CPU на каждой итерации с каким-то реальным процессором. Думаю, такие «CPU» существуют только в лабораториях вендоров и только в виде программной модели.
Я не говорю про ненужность (и тем более вредность) вообще, я говорю про избыточность для атомарных переменных. Атомарная переменная — это переменная типа
atomic<T>. Несмотря на то, что она определена в STL и, вроде бы, независима от самого языка, на самом деле наatomic<T>навешано довольно много семантики, то есть [очень грубо] можно считать, чтоatomic<T>является ключевым словом. И компиляторы, поддерживающие C++11 atomic, были существенно переработаны внутри, чтобы поддержать требования стандарта, новую модель памяти.Были обсуждения при подготовке стандарта, нужно или нет навешивать acquire/release семантику на чтение/записть volatile-переменных, как это сделали в C#. И было принято решение — не нужно. Эту семантику навесили на
atomic<T>.Кстати, один из аргументов против придания
volatileкакого-то статуса в C++11 был таким:Эта структура очень большая (по объему) и никак не влезает в atomic. Поэтому и acquire/release семантику на её представителей (
xв данном примере) навесить не получится.Никто не отменял (или переопределял) значения
volatile, как это случилось сautoв C++11. Используйте на здоровье! Просто надо помнить, что для атомарных переменныхvolatileизбыточна.Насчет выравнивания. Атомарная переменная должна быть правильно выровнена. Это необходимое условие атомарности. Иначе — UB.
По поводу packed — это нас x86 избаловала. На другой архитектуре при попытке обращения к невыровненному
intмы получим segmentation fault. Это и называется в стандарте «неопределенным поведением» (UB).Существуют ли lock-free контейнеры с поддержкой такой операции?
Явных контейнеров с перетаскиванием не встречал. Хотя такая задача иногда возникала на практике. Обходился своими силами — если понимаешь, как контейнер реализован (вернее, когда можно удаленный элемент контейнера 1 поместить в контейнер 2, — это уже из области алгоритмов safe memory reclamation типа Hazard Pointer), это не представляет труда.
внедрение счетчика в неиспользуемые биты указателя — совершенно верно! Это техника tagged pointers. В статье я утверждаю, что для неё нужен dwCAS, но на самом деле — не всегда. Можно использовать и неиспользуемые биты указателя. В современных 64-битовых платформах на самом деле адресуется, вроде бы, 48 бит (или 42? — не помню). Остальное может быть, в принципе, использовано. Насколько я знаю, boost.lockfree построен на этом.
Мне такой подход не нравится, — нет никакой уверенности, что в какой-то прекрасный момент производитель не сделает настоящий 64-битный адрес. И всё — наш алгоритм отправится на свалку :-(
Про достаточную разрядность счетчика — интересный и хороший вопрос! На этот счет были исследования. Насколько я помню (пруф сейчас не готов указать), их результатом было: достаточно 32-битового счетчика. Меньше — можно попасть на переполнение в неподходящий момент (а следствие — ABA). Обоснование: таймслот, выделяемый ОС для потока. Например, где-то в mail-list разработчиков Линукса я встречал такую оценку таймслота: 300 — 500 тысяч «простых» инструкций. После этого поток вытесняется. 300 тысяч не влезут в 16 бит. Это ещё один аргумент против использования 16 бит 64-битового указателя.
Про специальный аллокатор. Здесь я ничего сказать не могу, — очень большая тема. Я остановился на схемах безопасного освобождения памяти (Hazard Pointer, Pass-the-Buck, RCU), они решают все эти вопросы про ABA и освобождение (конечно, при правильном приготовлении :-) Повесить это на аллокатор… Нужно думать
Если мы говорим о физическом удалении, то ABA-проблема возникает при удалении (delete) и тут же включении вновь (allocate) некоего элемента. Удаление в C++ — это физическое удаление. В языках же с GC физического удаления не произойдет, пока кто-то держит ссылку на удаляемый элемент. Такую локальную ссылку какой-то поток держит (тот, который работает с CAS, на котором возникает ABA). Поэтому мой ответ — да, языки с GC свободны от ABA-проблемы.
Ответ на второй вопрос — решим ли мы проблему если никогда не будем освобождать выделенную память — скорее отрицательный. В общем случае не решим.
Рассмотрим такой пример, на двух lock-free интрузивных стеках (интрузивный контейнер — хранит не копии данных, а сами данные, — сишный подход, позволяет избавиться от аллокатора в контейнере): поток 1 делает
stack1.pop(), доходит до CAS и, к примеру, вытесняется. Поток 2, пока первый вытеснен, успевает сделать:Вслед за этим поток 1 выполняет CAS, меняя
aнаanext, который он запомнил. Ноanextтеперь включен вstack2! Нарушениеstack1: он теперь будет указывать вstack2. ABA-проблема, без освобождения выделенной памяти.Кажется, что этот пример входит в противоречие с моим первым утверждением — языки с GC свободны от ABA. На самом деле, противоречия нет. Языки с GC не позволяют работать с сырыми указателями (а если всё же позволяют, то на ваш страх и риск).
PS: смотрите внимательно, я могу наврать в примерах. ABA — очень тонкая вещь для обнаружения и объяснения, хотя и очень понятная, когда (и если :) разберешься.
Я намеренно разделил CAS и
compare_exchange.compare_exchange— это из C++11, аргументnExpectedпередается по ссылке и на выходе содержит текущее значение*pAddr. Именно в этом часто бывают ошибки/описки или излишне чтение в CAS-циклах.Data race не будет только на атомарных переменных atomic (это постулируется стандартом). Поэтому в C++11 в качестве флажков нужно использовать atomic.
Compare_exchange вовсе не обязателен — можно использовать и atomic load/store (разумеется, с правильным memory_order).
Вообще про volatile в C++ была большая и интересная дискуссия среди авторов нового стандарта. С кучей примеров pro и contra. В конце концов решили, что в C++11 не будут наделять volatile какой-то магической силой, как это сделали в Java или C#.
Я так подробно расписывал compare_exchange не потому, что только его нужно использовать, а потому, что он самый удобный и распространенный для lock-free алгоритмов. Конечно, есть множество алгоритмов, построенных без compare_exchange.
Но иногда 32 бита — мало. 32 бита — это выравненность по 4 байтам, то есть 2 младших бита адреса всегда нули. В 64 — имеем нулевыми 3 младших бита. В lock-free алгоритмах часто нужно вместе с некоторым адресом атомарно поменять и некоторые статусы. Для статусов необходимо использовать как раз эти младшие свободные биты в адресе (это так называемый marked pointer), чтобы и адрес, и статусы влезли в CAS. Естественно, в 3 бита влезет больше статусов, чем в 2. Иногда этот лишний бит в 64 бывает очень полезен. А в 32-битовой архитектуре приходится явно указывать выравнивание по 8 байтам, чтобы алгоритм был работоспособным. И тут начинаются танцы с бубном — aligned-распределение памяти (оно зачастую намного медленнее и прожорливей), компиляторно-зависимые конструкции и ограничения и пр.
Но 32 бита ещё довольно распространены, особенно для десктопных и «смартфонных» приложений. К тому же, когда пишешь некую библиотеку с замахом на общность, — 32 бита дисциплинируют. Иногда приходится поломать голову, как засунуть то, что хорошо вписывается в 64-битовую архитектуру, в 32 бита.