С таким спин локом, тоже падает...
Может я зря грешу на malloc/free?

P.S.
Временами, relacy на спин локе зависает наглухо...

P.P.S Пока malloc не отработает, память в список не записывается. Но он может быть вызван до того, как free закончит работать (а может ещё операционка что-то делает с ОЗУ?).
Что ж, это за зверь такой: "lock free malloc"?

Это сообщение отредактировал(а) Леопольд - 3.12.2010, 11:39

Очевидно что отдельно от push, pop отрабатывает нормально:
сперва забиваю стек (10 миллионов элементов), потом 100 потоков начинают дёргать pop
что радует, когда последний поток закончил работать, вся память полностью освободилась (в отличие от предыдущих "кривоногих" версий).
Шанс получить "хвост" в конце работы всех потоков пренебрежительно мал. И чем больше потоков, тем меньше шансов. Самый невезучий подчищает за всеми.

http://liveworkspace.org/code/1d76fb72fafa...af5403f5ae0b02e

На одноядерной (Ubuntu 10.04 g++4.5.1) тоже работает без сбоев.



Тут вывод поинтереснее: http://liveworkspace.org/code/81347b6f4ba2...09c75a0fbcc31a5


Это сообщение отредактировал(а) Леопольд - 3.12.2010, 14:19

Леопольд

Добавил немного комментариев, теперь давай прочитаем код

начнем со строки 24.
тут ты сперва проверяешь, что это единственный поток в функции pop (кстати все время хочу спросить почему value - 1 == 0 а не value == 1?).
потом проверяешь, что никто не менял m_deleted_head и он все еще равен head-у, т.е. поменять может в том случае, если в этом промежутке создался другой поток.
дальше, если ничего менялось ты удаляешь все элементы.
Вот тут то и проблема. Представь, что 1 твой поток дошел до строки 33, удали элемент, на который на данный момент указывает m_deleted_head (так как m_deleted_head и head указывают на ту же область памяти) и передал управление второму, который пытается добавить следующий элемент в список на удаление, но натыкается на UB на строке 20.
В примере я не зря очищал m_deleted_head и отделял от него весь список в локальный указатель, это делалось для того, чтобы другой поток в это время не смог с ним работать.

Если поток1 находится на двадцатой строке, то m_threads_on_lap($).fetch_sub(1) - 1 == 0 не выполнится. Если потокN дошёл до 9-й строки, то он никак не может получить тот же указатель "head" из-за 10 строки.

Это сообщение отредактировал(а) Леопольд - 3.12.2010, 14:25

Ты забываешь, что это две разные проверки и они НЕ атомарны. Потому я и отделил их в два отдельных if-а, чтобы было нагляднее.
Возможна такая ситуация: первая проверка выполняется, перед началом выполнения второй, другой поток входит в функцию pop.

Добавлено через 1 минуту и 56 секунд


Это сообщение отредактировал(а) azesmcar - 3.12.2010, 14:25

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

Можно и сильнее нагрузить, результать будет тот же.
100 потоков удаляют 10000000 элементов из стека размером 100000001 элементов:
http://liveworkspace.org/code/81347b6f4ba2...09c75a0fbcc31a5

пусть выполняет. Он уже никак не сможет получить тот же указатель из m_head. Если потокY в этот момент заменит m_deleted_head, то у него указатель на начало очереди на удаление, в которой и "наш" сидит уже. Оставляем очищать ему.

Это сообщение отредактировал(а) Леопольд - 3.12.2010, 14:43

Это проверка нужна не для того, что-бы гарантировать единственность. Она гарантирует что все потоки, которые зашли в pop прошли эту отметку и закончили работу со своими указателями. Почему не сравниваю с единицей сам не пойму 

Я пытался найти способ ответвить один поток в своё русло при помощи одного только стчётчика, но так и не смог. Но тут помогла compare_exchange_strong на m_deleted_head. Тот, кто смог её выполинть, гарантированно владеет списком указателей, с которыми больше никто не работает. Поэтому вся работа с указателями происходит до того как уменьшается счётчик. Я и имя ему такое дал, что бы с гонками ассоциировалось. Чистит хвосты самый нерадивый. 
Это, кстати, наглядно из логов видно (пару постов назад)


Это сообщение отредактировал(а) Леопольд - 3.12.2010, 14:58

Леопольд

Да, это я напутал..ты тоже тут выделяешь список в отдельную переменную, но проблема все равно та же.

процитирую статью


описываю проблемную ситуацию, номера строк смотри в моем коде.
1-ый поток входит в pop
2-ой поток входит в pop
3-ий поток входит в pop
1-ый поток продолжает выполнение и доходит до строки 27, так-как остальные два потока пока не инкрементировали значение счетчика
2-ой поток начинает выполнение и доходит до строки 10
3-ий поток начинает выполнение и доходит до строки 10
2-ой поток удаляет элемент из списка и дойдя до строки 20 помещает его в список на удаление
1-ый поток продолжает работу и выделяет список в локальную переменную m_deleted_head
1-ый поток доходит до цикла на строке 30 и начинает удалять элементы, включая тот, который туда поместил 2-ой поток
3-ий поток просыпается и все еще ссылается на тот элемент, который поместил в список на удаление 2-ой поток
3-ий поток при попытке выполнить 10-ую строку вылетит с ошибкой

в двух словах: один поток удаляет объект, помещенный в список другим поток, на который ссылается третий.

Это сообщение отредактировал(а) azesmcar - 3.12.2010, 15:06

Этого не будет. 1-ый поток один раз попытается сделать strong CAS, но 2-ой поток изменил его, пэтому 1-ый поток получит false (не сможет выделить список в локальную переменную).

Но такая бага действительно имела место быть в предыдущих вариантах (по моему, relacy мне её показал).

Вообще, relacy классная штука. Я когда первый вариант ему подсунул, он тут же показал что память течёт рекой... 

Добавлено @ 15:31
Вариант из статьи форсирует алгоритм "гулять" по очереди туда-обратно. К тому же, он вставляет очередь обратно по одномоу элементу, постоянно мешая другим потокам, что очень негативно сказывается на производительности. С 10 миллионами элементов он будет работать очень долго. Сперва я пытался сделать что-бы он вставлял обратно очередь сразу всю целиком, но всё равно приходилось "гулять" из конца в конец. Именно поэтому, я решил попробовать сделать иначе. Обойти этот момент. Похоже удалось.

Но возникает какая-то загадочная проблема с выделением и освобождением памяти параллельно.


Это сообщение отредактировал(а) Леопольд - 3.12.2010, 15:36

Да, верно..невнимательный я что-то, не обратил внимания на if. А тут точно есть проблема в функции pop? Я ничего другого не вижу, вроде все в порядке.

Похоже что нет. Я пришёл к мнению что с pop всё ОК. Пробовал под большой нагрузкой и relacy всё проверил. 


Это сообщение отредактировал(а) Леопольд - 3.12.2010, 15:38

где и как это проявляется?

Надо несколько потоков запустить. Половина вставляет элементы, другая половина выкидывает. При большом  количестве потоков и элементов.

P.S. пора домой...


Это сообщение отредактировал(а) Леопольд - 3.12.2010, 15:40

Леопольд, 

я теряюсь в твоих исходниках, уже не понимаю которая версия правильная, которая нет..покажи пальцем где и когда происходит.

Леопольд

А у тебя там случайно не bad_alloc вылетает?