Вобщем, у всех четверг - у меня пятница, и поэтому, любителям стрельбы себе в ногу посвящается...

Нашел интересный "баг" с ConcurrentHashMap. Решил поделиться, причем тут а не на хабре. Там злые - минусуют. Всегда считал, что многопоточные классы можно безопасно использовать в одном потоке. Ну, как бы, вроде это само собой разумеется. Мне так казалось. Сегодня выяснил - оказывается, нет.

Сейчас попытаюсь объяснить на пальцах. У ConcurrentHashMap есть активное ожидание некоторых величин. Но, само понятие "ожидание" означает, что мы в потоке А ждем, когда что-то в потоке Б произойдет. А если у нас нет потока Б, значит это что-то никогда не произойдет. В этом плане, ожидание на флажках отличается от ожидания на synchronized. Роль флажков в ConcurrentHashMap выполняют ссылки на объекты, которые ConcurrentHashMap дергает через CAS.

Начиная с 1.8 это организовать легко: в ней появились методы compute*, которые пересчитывают значение по нужному ключу, вызывая пользовательскую лямбду. Вызов лямбды внутри хэшмапы синхнронизирован по бакету, плюс этот бакет при помощи CAS публикуется всем другим потокам. И это поведение описано в документации, мол, на время выполнения compute некоторые другие потоки могут быть блокированы. Но если у нас поток 1, то таким образом ConcurrentHashMap можно повесить, просто вызвав из compute что-нибудь такое, что в многопоточном использовании compute блокировал бы. На практике это remove объекту с некоторым хэшкодом, который будет связан с бакетом, созданым compute.

Тут еще вот что интересно. Мапа пустая, и удаляем мы из нее несуществующий объект. И это вызывает зависание.




Если бы мы дергали compute и remove из разных потоков, то на время выполнения compute поток c remove() висел бы в активном ожидании завершения compute. И у нас он висит в активном ожидании. Только у нас всего 1 поток, и поэтому compute не завершится. Таким образом, это своего рода разновидность дедлока: ресурсы ожидают друг друга. Такой "дедлок" даже java pathfinder не ловит!

Скорей всего так же, возможны всякие интересные побочные эффекты. Я не пробовал так делать, но по идее, если потоку с remove дать повыше приоритет, то на одноядерниках это тоже будет дедлок. Никакой инверсии приоритетов там не делается.

Это вопрос терминологии. Вы это назвали "уходит в бесконечный цикл". Можно и так назвать. Даже, наверное, корректней.

Я рассматриваю то, что происходит внутри remove, как разновидность активного ожидания. Просто явного одного while нету,
но по сути из потока который выполняет compute в другие потоки при помощи CAS публикуется ресурс по которому они могут синхронизироваться. Фрагмент из compute





Причем, публикация может неполучиться, но тогда мы не заходим внутрь if. Но если публикация удалась, то мы заходим внутрь if, и тогда в массиве tab по индексу i будет лежать ReservationNode, который после нашей лямбды внутри finally так или иначе будет заменен либо на null, либо на ноду.
То есть, тут по сути, ReservationNode - это объект синхронизации, он публикуется для других потоков при помощи CAS.
Тут еще надо заметить, что хэшкод у ReservationNode всегда равен -3, она так устроена.


Фрагмент, по которому бегаем внутри remove:



В (1) мы получили ресурс для синхронизации. В данном случае, получаем наш ReservationNode, опубликованный ранее.

В (2) мы получили хеш этой ноды, на нашем случае -3. Отрицательные хеши отведены для служебных нужд. По сути, тут сравнение с MOVED - это своего рода instanceof. Это нерекомендуемый для простых смертных подход: когда в классе заводят поле с его типом.

В (3) у нас fh==-3, что меньше нуля. То есть, мы видим, что хэш служебный. А раз хэш служебный, значит пока с ним делать ничего нельзя - и мы не входим в удаление, а идем на следующий цикл.

То есть, (1)-(2)-(3) это активное ожидание того, что или сам обьект синхронизации станет null, или хэш станет MOVED (то есть -1), или хэш станет больше нуля.


Ну вобщем да, это не дедлок, а бесконечный цикл. Какой же это дедлок, если у нас 1 поток. Но в данном случае мыслить можно не потоками, а ресурсами. Просто это чуть менее привычно. Методу compute нужен ресурс - "процессорное время", но мы его блокируем, а потом сами блокируемся в активном ожидании на завершении метода compute.

Ресурс А - процессорное время
Ресурс Б - ReservationNode

Метод compute захватывает сначала ресурс Б потом у него исполнение отбирают (то есть он как бы блокируется на ожидании освобождения ресурса А) и отобравший ожидает освобождения ресурса Б неотдавая при этом А. Если мыслить категориями ресурсов - дедлок.

"явного while нету", а это он, но он не явный while, а for в котором нету никаких проверок на ресурсах. Ну то есть сразу, вроде как, и не понять, что это блокировка на ожидание ресурса. И вы, судя по каментам, и не поняли: мол, уходит в бесконечный цикл, и нету никаких блокировок, не верю, дайте код. Или я неправильно расценил [18971772]?

Блокировка с активным ожиданием. Конечно оно там внутри проверяется, просто сразу не видно, что ждет ресурс. Если бегло смотреть, то кажется, что проверяются какие-то условия, а что эти условия являются проверкой свободности ресурса - это уже становится ясно, если вникать.


BlazkowiczУ deadlock (взаимоблокировки) существует академическое определение.
можете его привести?

0FDИнтересно и то, как автор выбрал 0x22a71081, ведь при других значения цикла нет.

Если кратко - случайно попал, начал разбираться.

логика была примерно такой: "Нужен свой многопоточный кэш, но хотелось хитрый: с блэкджеком. Готовых решений не нашлось. Значит, заюзаем ConcurrentHashMap. А вот тут нужен remove, раз из другого потока он так может, то и из того же звать можно, я верю в ConcurrentHashMap, он умный, он сможет...". Не то чтобы такой кэш сильно-сильно был нужен, но я решил его сделать. Просто хотелось отвлечься от основной задачи.

При, этом, еще отдельно пришлось навернуть механизм, гарантирующий, что объект, которому делают remove, не схватят с другого потока - чтоб не было дедолка. Но были сомнения все ли я учел, поэтому я взял java pathfinder и начал это анализировать на дедлоки. Попутно нашел баг в самом pathfinder, отправил им репорт и сделал pull request чуваку на гитхабе, который его переводил на gradle (его нету в mavencentral и jcenter). И тогда "доработанную и проверенную" версию своего кэша я запустил - сразу все повисло. Бгг.

Сложней было заставить это повиснуть под дебагом. Если java запускать с дебагом - оно дебажилось нормально, а висло только если запускаешь с консоли и без дебага. Случайность. Не те хешкоды. Под идеей тоже не висло. У нее там свой раннер, какие-то дополнительные классы, а значит по-другому ложатся хэшкоды. Но вобщем, после каких-то бубноплясок это получилось сделать, и когда вышло его подвесить под дебагом, то дальше это было уже дело техники - выдрал хэшкоды из повисшего приложения.

BlazkowiczНет, это когда разные процессы, (не меньше двух), заблокировали ресурсы и ждут освобождения других заблокированных ресурсов. Которых, кстати, тоже не меньше двух.

Это определение не академическое.

BlazkowiczТы нашёл что процитировать. Нигде не утверждается что это даже определение.

Вы писали, что оно существует. Мне оно неизвестно. И я немножко погуглил - не нашел ничего похожего на такое определение. Везде объяснено "своими словами".
Если вам оно известно - поделитесь плыз. Скорей всего, если бы оно существовало и было общепринятым, его удалось бы найти сразу.

Blazkowiczchabapok,

jgiIn computer science, deadlock refers to a specific condition when two or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions).

Ну, если рассматривать это как академическую формулировку. Ну вот смотрите. Тут речь о каких-то "процессах". Значит, если потоки ждут друг друга - это уже что ли не дедлок? Очевидно, дедлок. Это означает, что должно существовать некое академическое же определение того, что такое "процесс". Например, он включает в себя и процесс и поток, и еще что-нибудь. Например, почему бы не сказать, что один процесс - это compute, а второй - remove, один из ресурсов - процессорное время и тд, как я расписал это вконце 18972030 .

На самом деле, ИМХО, прямо вот такого строгого определения, что нельзя сделать шаг вправо-влево, - не было и нет. Это ж не религия, зачем быть настолько догматичным? Так что это даже не определение, а объяснение ситуации, которую так называют. Оно допускает некоторые отклонения.

И честно говоря, я не понимаю зачем вы вообще к словам прицепились. В исходном сообщении я употребил фразу "своего рода разновидность дедлока", это что по вашему - недостаточно конкретный намек, что это не совсем делок? Или эту длиннющую фразу надо было дальше везде по тексту использовать?