Почему эти безблокировочные реализации подсчета ссылок не взрываются (или взрываются)?

Я пытаюсь разобраться в алгоритмах LFRC, но продолжаю находить примеры, в которых я предполагаю, что они работают, но не могу понять, почему. Я сосредоточен на копировании и удалении. В частности, есть три, которые следуют одному и тому же общему шаблону (псевдокод):

Copy {
  shared = source->shared;
  if (shared != null) {
     Atomically_Increment_Counter(shared);
  }
}

Delete {
  if (shared != null) {
     oldcounter = Atomically_Decrement_Counter(shared);
     if (oldcounter == value signifying all references released) {
        Deallocate(shared);
     }
  }
}

Первый из статьи Lock-Free Reference Counting Дэвида Л. Детлефса, рисунок 2, страница 8 (отредактировано для форматирования):

void LFRCCopy(SNode **v, SNode *w) {
   Snode *oldv = *v;
   if (w != null) 
      add_to_rc(w,1);
   *v = w;
   LFRCDestroy(oldv);
}

void LFRCDestroy(SNode *v) {
   if (v != null && add_to_rc(v, -1)==1) {
     LFRCDestroy(v->L);
     LFRCDestroy(v->R);
     delete v;
   }
}

Где add_to_rc — атомарное приращение и нагрузка. Второй — из реализации Mat в opencv4 (отредактировано для краткости):

// Line 405
Mat::Mat(const Mat& m)
    : flags(m.flags), dims(m.dims), rows(m.rows), cols(m.cols), data(m.data),
      datastart(m.datastart), dataend(m.dataend), datalimit(m.datalimit), allocator(m.allocator),
      u(m.u), size(&rows), step(0)
{
    if ( u )
        CV_XADD(&u->refcount, 1);
    ...
}

// Line 551
void Mat::release()
{
    if ( u && CV_XADD(&u->refcount, -1) == 1 )
        deallocate();
    u = NULL;
    ...
}

Где CV_XADD — атомарное приращение и нагрузка. И третий — из реализации std::shared_ptr, которая поставляется с libstdc++ в самой последней версии GCC (10.2) (эта реализация очень сложная, и я сильно ее отредактировал для краткости):

class _Sp_counted_base {

    void _M_add_ref_copy()
    { __gnu_cxx::__atomic_add_dispatch(&_M_use_count, 1); }

    // Line 161 for full implementation
    void _M_release() noexcept
    {
       _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_use_count);
       if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) == 1)
       {
          _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_use_count);
          _M_dispose();
          if (_Mutex_base<_Lp>::_S_need_barriers)
             __atomic_thread_fence (__ATOMIC_ACQ_REL);
          // editors note: weak pointer handling removed for brevity
          _M_destroy();
       }
    }

}

class __shared_count {

    __shared_count(const __shared_count& __r) noexcept 
        : _M_pi(__r._M_pi)
    {
        if (_M_pi != nullptr)
           _M_pi->_M_add_ref_copy();
    }
    
    ~__shared_count() noexcept
    {
        if (_M_pi != nullptr)
           _M_pi->_M_release();
    }

    _Sp_counted_base* _M_pi;

}

class __shared_ptr {

    __shared_ptr(const __shared_ptr&) noexcept = default;

    ~__shared_ptr() = default;

    element_type*   _M_ptr;         // Contained pointer.
    __shared_count  _M_refcount;    // Reference counter.

}

Некоторое объяснение последнего, поскольку оно косвенное:

  • Копирование: __shared_ptr конструктор копирования по умолчанию копирует _M_refcount, чей конструктор копирования использует тот же _Sp_counted_base, что и оригинал, и атомарно увеличивает счетчик ссылок.
  • Удалить: __shared_ptr деструктор по умолчанию уничтожает _M_refcount, чей деструктор вызывает _M_release для _Sp_counted_base, что атомарно уменьшает и, возможно, освобождает счетчик ссылок.

В любом случае, все это сводится к одному вопросу, который является сутью моей неспособности понять, почему они работают (даже эта старая статья доктора Доббса и связанные с ней вопросы здесь, на SO [я чувствую, что ответ может быть здесь но я его не вижу] вызвало у меня больше вопросов, чем ответов):

В операции копирования, что предотвращает состояние гонки, когда другой поток выполняет операцию удаления последнего счетчика ссылок (возможно, через другое представление общего объекта), а затем освобождает объект между началом операции копирования и началом атомарного приращение счетчика - таким образом, из того, что я (неправильно) понимаю, заставляя копию увеличивать освобожденный счетчик и аварийно завершать работу или сбрасывать ядро ​​везде или что-то в этом роде?

То есть, ссылаясь на вышеприведенную реализацию opencv (поскольку именно с ее изучения начался весь мой мини-исследовательский проект здесь):

Mat::Mat(const Mat& m)
    : flags(m.flags), dims(m.dims), rows(m.rows), cols(m.cols), data(m.data),
      datastart(m.datastart), dataend(m.dataend), datalimit(m.datalimit), allocator(m.allocator),
      u(m.u),   // <--- START OF DANGER ZONE 
      size(&rows), step(0)
{
    if ( u )     
                // <--- ALMOST AT END OF DANGER ZONE 
        CV_XADD(&u->refcount, 1);
    ...
}

void Mat::release()
{
    if ( u && CV_XADD(&u->refcount, -1) == 1 )
        deallocate();
    u = NULL;
    ...
}

Что удерживает другой поток от выпуска последней ссылки через m в помеченной «опасной зоне» в конструкторе копирования, таким образом оставляя u не нулевым, но указывающим на мусор после освобождения?

Что мне здесь не хватает? Я чувствую, что это может быть очевидно, и, возможно, я слишком долго не спал. В частности, тот факт, что реализация libstdc++, похоже, также следует этому шаблону, придает ей массу уличного доверия; Я просто не могу понять подробности.

Обычно это сводится к ожидаемой степени безопасности операций. Ожидается, что эти RC-объекты будут потокобезопасными, а не атомарными. Таким образом, ответственность за предотвращение одновременной записи (или одновременного чтения и записи) одной и той же ссылки по-прежнему лежит на пользователе, иначе возникает состояние гонки.

Marc Glisse 15.12.2020 08:18

@MarcGlisse Да; но счетчики ссылок являются общими, не так ли? Например: shared_ptr x(object) = ...; start_new_thread(shared_ptr(x) /* copy */);, разве в новом потоке все еще не возможна гонка, даже если он работает с единственным экземпляром безопасно созданной копии, если какая-то копия там происходит в то же время, когда последний shared_ptr до object уничтожен в другом месте?

Jason C 15.12.2020 08:23

Другими словами, если в операции копирования я поставлю искусственную 30-секундную задержку непосредственно перед увеличением счетчика ссылок, будет ли все по-прежнему работать? Что предотвратило бы тем временем уничтожение всех остальных объектов, разделяющих этот rc, что привело бы к уничтожению счетчика?

Jason C 15.12.2020 08:24

@JasonC Я думаю, что вы не можете использовать один и тот же объект shared_ptr (x в вашем случае) в двух потоках. Такой, что нельзя "скопировать" его в одном потоке и "уничтожить" в другом.

Daniel Langr 15.12.2020 08:28

Если вы используете shared_ptr в одном потоке, другой поток не может иметь единственную ссылку.

Marc Glisse 15.12.2020 08:30

Если вы используете shared_ptr в одном потоке, либо другой поток имеет свой собственный shared_ptr, и поэтому «доля» в подсчете ссылок и его> = 2 или какая-либо другая синхронизация обеспечивает «заимствование». При заимствовании предпочтительным методом является передача необработанного указателя (shared_ptr::get()), чтобы показать, что он имеет ссылку на сохраненный объект, но не имеет прямой «доли» в его счетчике ссылок.

Persixty 15.12.2020 09:25

Я думаю, что псевдокод немного расплывчатый. Как насчет was=Atomically_Decrement_Counter(shared); и следующей строки, которая будет if (was==INIT_VALUE), где INIT_VALUE — это то, что было установлено для общего доступа во время создания, и может не быть 1, если происходит особый жизненный цикл. Было должно быть значение общего доступа, замененное во время атомарного уменьшения.

Persixty 15.12.2020 09:47
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
7
564
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Короткий ответ, вы устали!

Это классическая «модель подсчета ссылок». Когда объект создается, его счетчик ссылок инициализируется (классически равным 1). Создающий поток владеет этой ссылкой. Этот поток может увеличивать или уменьшать этот счетчик, когда он создает новую ссылку, и когда он достигает 0, ссылки не существуют, и объект удаляется. Это все однопоточное, но ваш вопрос касается многопоточного.

Есть два дополнительных правила для многопоточности.

  1. Поток не должен пытаться уменьшить значение счетчика, если он уже не владеет ссылкой.
  2. Кроме того, (ключ) поток не должен пытаться увеличивать счетчик, если он уже не содержит ссылку.

Таким образом, условие гонки другого потока, пытающегося освободить объект, в то время как поток пытается увеличить количество ссылок (здесь, в копии), никогда не произойдет (и никогда не должно произойти).

Таким образом, если какой-либо другой поток одновременно освобождает ссылку, счетчик в то время как другой поток увеличивает его, счетчик всегда должен быть> = 2, потому что оба должны удерживать ссылку.

__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1) возвращает замененное значение, поэтому строка if (__gnu_cxx::__exchange_and_add_dispatch(&_M_use_count, -1)==1 означает «если этот поток заменил 1 на 0, что означает «если этот поток содержит последнюю ссылку».

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

В «пуле потоков», где объекты помещаются в очередь, может быть неопределенно, в какой поток передается ссылка, и требуется дальнейшая синхронизация (например, в очереди), чтобы гарантировать, что только один поток с когда-либо «претензиями», которые «общие» ссылка.

Под «владением» я подразумеваю либо «владеет», либо «заимствовал». Владение означает, что поток, который владеет ссылкой (обеспечит ее окончательный выпуск), а «заимствование» означает, что фактическое владение (который обеспечит ее окончательный выпуск) потоком будет синхронизирован с заемщиком и гарантирует, что он не будет выпущен до тех пор, пока другой поток (а) получил ссылку или (б) не должен снова обращаться к объекту.

Фрагменты кода кажутся действительными (я не знаком со всеми этими библиотеками в деталях), но подтверждают, что __exchange_and_add_dispatch возвращает старое значениеГлава 29. Параллелизм достаточно, чтобы убедить меня, что это то, что происходит.

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

Слабые ссылки являются тонкой тонкостью этой модели и представляют собой отдельный счетчик, который следует той же модели. Хотя может быть (как обычно для std::shared_ptr с использованием std::make_shared) выделено (new) вместе с основным объектом, и хотя основной объект может быть уничтожен до последней слабой ссылки, блок памяти deleted заполняется, когда оба счетчика достигают нуля, и если слабые ссылки существуют, когда освобождается последняя сильная ссылка, слабая ссылка помечается, чтобы показать, что основной объект был удален.

Ой! Я понимаю (наверное)! И ты прав, это определенно случай моей усталости. Вы излагаете это таким образом, что это ясно. Часть, которую я все время забывал, заключалась в том, что по крайней мере одна ссылка должна храниться во время ее копирования - вы не можете находиться посреди копии, пока не существует ссылок. Или что-то вроде того. Но я понимаю. И я также убежден, что пришло время прекратить работу и попробовать еще раз в утренние часы. Спасибо.

Jason C 15.12.2020 08:51

@JasonC Это расширение правила, согласно которому ни один поток не должен читать или записывать объект, если ссылка не «удерживается» на протяжении всего этого процесса. Спокойной ночи! Я гарантирую, что вы проснетесь с «конечно»!

Persixty 15.12.2020 08:58

Вы были правы, между прочим: сегодня утром я проснулся и подумал: «О... верно». 😂 Еще раз спасибо.

Jason C 16.12.2020 06:32

Другие вопросы по теме