Подсчет ссылок в C

Question

Пытается передать структуру между потоками в plain C с использованием подсчета ссылок. У меня есть pthreads и gcc atomics. Я могу заставить его работать, но я ищу пуленепробиваемый.

Сначала я использовал PTHREAD семафор, принадлежащий самой структуры:

struct item { 
    int ref; 
    pthread_mutex_t mutex; 
}; 

void ref(struct item *item) { 
    pthread_mutex_lock(&item->mutex); 
    item->ref++; 
    pthread_mutex_unlock(&item->mutex); 
} 

void unref(struct item *item) { 
    pthread_mutex_lock(&item->mutex); 
    item->ref--; 
    pthread_mutex_unlock(&item->mutex); 
    if (item->ref <= 0) 
    free(item); 
} 

struct item *alloc_item(void) { 
    struct item *item = calloc(1, sizeof(*item)); 
    return item; 
} 

Но, понял, что мьютекс не должны принадлежать данному вопросу:

static pthread_mutex_t mutex; 
struct item { 
    int ref; 
}; 

void ref(struct item *item) { 
    pthread_mutex_lock(&mutex); 
    item->ref++; 
    pthread_mutex_unlock(&mutex); 
} 

void unref(struct item *item) { 
    pthread_mutex_lock(&mutex); 
    item->ref--; 
    if (item->ref <= 0) 
    free(item); 
    pthread_mutex_unlock(&mutex); 
} 

struct item *alloc_item(void) { 
    struct item *item = calloc(1, sizeof(*item)); 
    return item; 
} 

Затем, в дальнейшем реализованы указатели передаются по значению, поэтому у меня теперь есть:

static pthread_mutex_t mutex; 
struct item { 
    int ref; 
}; 

void ref(struct item **item) { 
    pthread_mutex_lock(&mutex); 
    if (item != NULL) { 
    if (*item != NULL) { 
     (*item)->ref++; 
    } 
    } 
    pthread_mutex_unlock(&mutex); 
} 

void unref(struct item **item) { 
    pthread_mutex_lock(&mutex); 
    if (item != NULL) { 
    if (*item != NULL) { 
     (*item)->ref--; 
     if ((*item)->ref == 0) { 
     free((*item)); 
     *item = NULL; 
     } 
    } 
    } 
    pthread_mutex_unlock(&mutex); 
} 

struct item *alloc_item(void) { 
    struct item *item = calloc(1, sizeof(*item)); 
    if (item != NULL) 
    item->ref = 1; 
    return item; 
} 

Есть ли какие-либо логические ошибки здесь? Благодаря!

Answer 1

Я не знаю решения общего назначения.

Было бы неплохо уменьшить это до атомного добавления/вычитания счетчика ссылок. В самом деле, большую часть времени это все, что требуется ... так что переход через мьютекс или что-то еще болит.

Но настоящая проблема заключается в управлении счетчиком ссылок и указателем на элемент в то же время.

Когда нить доходит до ref() предмета, как она найдет его? Если он еще не существует, возможно, он должен его создать. Если он уже существует, он должен избегать другого потока, освобождающего его до того, как счетчик ссылок будет увеличен.

Итак ... ваши void ref(struct item** item) работает на том основании, что мьютекс защищает struct item** указатель ... в то время как вы держите семафор, никакой другой поток не может изменить указатель - это только один поток может создать элемент (и приращение счет 0-> 1), и только один поток может уничтожить элемент (после декрементации счета 1-> 0).

Говорят, что многие проблемы в информатике могут быть решены путем введения нового уровня косвенности, и это то, что происходит здесь. Проблема в том, как все нити получают адрес элемента - учитывая, что он может (мягко и внезапно) исчезнуть? Ответ: придумайте уровень косвенности.

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

Таким образом, чеки if (item == NULL) после блокировки мьютекса являются подозрительными. Если мьютекс также защищает указатель на элемент, то этот мьютекс должен быть заблокирован до, устанавливая адрес указателя на элемент - и в этом случае проверка после блокировки слишком поздняя. Или адрес указателя на элемент защищен каким-либо другим способом (возможно, другим мьютексом) - и в этом случае проверка может быть выполнена перед блокировкой (и перемещение ее там дает понять, что защищает мьютекс, и что он не защищает).

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

У меня есть большие динамические структуры данных (хеш-таблицы, очереди, деревья и т. Д.), Которые разделяются несколькими потоками. В основном, потоки ищут и удерживают предметы в течение некоторого времени. Когда система занята, она очень занята, и уничтожение предметов можно отложить до тех пор, пока ситуация не станет более спокойной. Поэтому я использую блокировки чтения/записи на больших структурах, атомарное добавление/вычитание для счетчиков ссылок и сборщик мусора для фактического уничтожения предметов. Дело здесь в том, что выбор механизма для (по-видимому, простого и самодостаточного) приращения/уменьшения счетчика ссылок зависит от того, как управляется создание и уничтожение элементов, а также о том, как потоки имеют указатель на элемент (который, в конце концов, подсчитывает счетчик ссылок).

---

Если у вас есть 128-битную атомарной операции под рукой, вы можете поставить 64-битный адрес и 64-разрядную ссылку на кол вместе и сделать что-то вдоль линий:

ref: bar = fetch_add(*foo, 1) ; 
     ptr = bar >> 64 ; 
     if (ptr == NULL) 
     { 
      if (bar & 0xF...F) 
       ...create item etc. 
      else 
       ...wait for item 
     } ; 

unref: bar = fetch_sub(*foo, 1) ; 
     if ((bar & 0xF...F) == 0) 
     { 
      if (cmp_xchg(*foo, bar, (NULL << 64) | 0))) 
       ...free(bar >> 64) ; 
     } ; 

где foo - это 128-битный комбинированный ptr/ref-count (существование которого защищено некоторыми внешними средствами) - при условии, что 64-битный ptr и 64-битный счетчик - и bar является локальной переменной этой формы, а ptr является недействительным *.

Если поиск указателя NULL запускает создание элемента, то первый поток для перемещения счетчика из 0-> 1 знает, кто они, и любые потоки, которые прибывают до создания элемента, и набор указателей, также знают кто они есть и могут ждать. Для установки указателя требуется cmp_xchg(), и затем создатель обнаруживает, сколько потоков ожидает их.

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

Это заменяет мьютексы в ваших функциях ref и unref ... но НЕ решает проблему того, как защищена эта ссылка.