Подсчёт ссылок в libmary.

Классы:
    Referenced
    MtReferenced

    Ref
    MtRef

    WeakRef
    MtWeakRef


==== Применение подсчёта ссылок в контейнерах ====

// При этом реализация List остаётся неизменной, потому что не изменяются
// смещения от начала объекта к полям данных. Можно оборачивать как в
// Referenced, так и в Object.
Ref< RefWrap< List<Foo> > >
Ref< MtRefWrap< List<Foo> > >
Ref< ObjWrap< List<Foo> > >
Ref< MtObjWrap< List<Foo> > >


TODO libmtref:

  1. Подробно описать механизм reference counting;
  2. Обосновать принятые решения;
  3. Выполнить эффективную реализацию с использованием полного арсенала средств
     C++0x;
  4. Протестировать то, что получилось;
  5. Пропиарить результат.

  Результатом будет:
      Эффективная библиотека для multithreaded reference counting на C++.
      - будет оформлена в виде единственного заголовочного файла libmtref.hpp.

  ...C++ хорош только отчасти. Но передовые разработки сейчас ведутся именно
  под него.


------

Важно отметить, что существуют более эффективные способы управления атомарными
переменными: с использованием различных типов барьеров памяти, ассоциируемых
с атомарными операциями. Такие средства включены в драфт стандарта C++0x, но
свободной реализации этих средств пока нет. Также можно использовать библиотеку
поддержки атомарных операций, входящую в Boehm Garbage Collector.

* Средства atomic C++0x - только для экспертов;
* Набор memory_order_* - достаточно полный, но, всё же, компромиссный;
* Пытаться полностью понять memory model так, как она сформулирована в
  стандарте, бесполезно. Да и сформулирована она ещё не окончательно;
* Ответы на вопросы есть в документации по архитектурам Alpha, PPC, SPARC. Но
  никак не Intel;
* Невозможно отладиться без соответствующего железа. x86 даёт довольно строгие
  гарантии для обычных операций.

------

Схема подсчёта ссылок в libmary.

Поддерживается два дипа ссылок:

1. Обыкновенные ссылки (reference - Ref);
2. Слабые ссылки (weak reference - WeakRef).

Обыкновенные ссылки, или просто ссылки, определяют время жизни объекта.
Объект удаляется, когда не остаётся ни одной связанной с ним обыкновенной
ссылки. Кол-во ссылок, связанных с объектом, хранится в поле refcount, которое
класс объекта получает, наследуя от Referenced.

Слабые ссылки связаны с объектом, но не влияют на его время жизни. Из слабой
ссылки можно получить обыкновенную ссылку, вызвав метод getRef(). Результат
getRef() - либо корректная ссылка на объект, либо null, что означает, что объект
уже удалён. Основное
свойство слабых ссылок, отличающее их от обычных указателей, состоит в том,
что все слабые ссылки автоматически зануляются при удалении объекта. Невозможна
ситуация, когда часть слабых ссылок занулена, а часть - нет. С точки зрения
внешней программной логики в произвольный момент времени либо занулены все
слабые ссылки, либо не занулено ни одной.

Слабые ссылки нужны в двух основных случаях:
1. Для принудительного разрыва циклов ссылок;
2. В случаях, когда мы хотим, чтобы время жизни объекта управлялось извне.
   Например, мы не хотим выполнять отложенное действие, если объект, поставивший
   задачу, был удалён.

        Объект               Тень объекта
     +-----------+         +---------------+ 
     | refcount  |         |    lock       |
     +-----------+         |   weak_ptr    |
     | shadow    |         |  lastref_cnt  |
     +-----------+         +---------------+

# При захвате слабой ссылки увеличивается refcount объекта. Между считыванием
# weak_ptr и увеличением refcount не должно изменяться значение weak_ptr.
# Поэтому мы используем простой lock на тень объекта (хотя могли бы использовать
# rw_lock, но lock просто проще). Здесь наверняка можно было бы использовать
# lock-free алгоритм.

Чтобы обеспечить одномоментное зануление слабых ссылок, заводим вспомогательный
объект Object_Shadow. В этом объекте содержатся указатель weak_ptr и мьютекс,
синхронизирующий доступ к объекту-тени. При выполнении getRef() слабая ссылка
блокирует тень и использует weak_ptr. Занулить слабые ссылки - значит занулить
weak_ptr. Это можно сделать одномоментно, заблокировав тень и установив weak_ptr
в NULL. Object_Shadow - объект Referenced. Каждая слабая ссылка удерживает
ссылку на Object_Shadow. Также ссылка на тень есть в основном объекте. Объект
тени создаётся при первом вызове getShadow(). Синхронизация - по мьютексу
состояния объекта MtObject::mutex.

Реализация методов ref/unref.

Для класса MtObject unref() усложнён тем, что, пока не занулены слабые ссылки,
в произвольный момент может появиться новая ссылка на объект, потенциально
отменяющая удаление объекта. Для того, чтобы ловить такие случаи, заводим в
тени специальный счётчик lastref_cnt (инициализируется в 1).
Если при выполнении ref() атомарная
операция fetch_add вернула 0, то увеличиваем значение lastref_cnt на 1.
Когда refcount достигает нуля, выполняем декремент lastref_cnt.
Удалять объект можно только когда lastref_cnt равно нулю. Всё это имеет особое
значение только при выполнении getRef() на слабой ссылке.

-------

Циклическая зависимость, мешающая компиляции:

template <class T>
class MtCallback
{
    WeakRef<MtObject> weak_obj;
};

class MtObject
{
    class DeletionSubscription
    {
	MtCallback<DeletionCallback> cb;
    };
};

template <class T>
class WeakRef
{
    // Нужно, чтобы Object_Shadow был разным для Object и MtObject.
    // ...В принципе, можно использовать Ref<Referenced> и делать static_cast.
    //     - нельзя, потому что нужно различать Referenced и MtReferenced.
    // Т.е. я полагаю, что для того, чтобы сохранить единый вид WeakRef,
    // здесь нужно использовать typename T::ObjectShadow. Для этого требуется,
    // чтобы определение T было доступно на момент инстанцирования WeakRef<T>.
    // Т.е. в нашем случае обпределение MtObject _должно_ стоять перед WeakRef.
    Ref<typename T::Object_Shadow> shadow;
};

Решение - разместить определения в таком порядке:

1. WeakRef;
2. MtObject;
3. MtCallback;
4. MtObject::DeletionSubscription.

...и всё же в целом эта схема находится на грани разрешимости.

------

Логический конфликт:

* Операции ref/unref для MtReferenced можно реализовать эффективнее, чем для
  MtObject;
* Использование виртуальных функций для ref/unref недопустимо из соображений
  производительности;
* Если реализации ref/unref в MtReferenced и MtObject будут совершенно разными,
  то невозможно будет использовать Ref<MtReferenced> для объектов MtObject;
* Следовательно, либо я оставляю MtReferenced и MtObject разделёнными, либо
  мирюсь с тем, что ref/unref в MtReferenced неоптимальны. Это будет означать,
  что нужно вводить в MtCallback раздельные члены "Ref<MtReferenced> ref" и
  "Ref<MtObject> obj". По сути, это - единственное неудобство, связанное с
  разделением Referenced/Object.

...также это означает, что разделение Referenced и Object будет аналогичным,
чтобы не нарушать симметрию.

* У Referenced и Object всё равно есть vtable, так почему бы в него не поместить
  виртуальные virt_ref/virt_unref, в добавление к невиртуальным? Они сыграли бы
  роль RefCallback/UnrefCallback, и в MtCallback не пришлось бы хранить 2
  ссылки, одна из которых постоянно не исполльзуется.

  Для этого нужно добавить классы VirtReferenced и VirtRef.

------

Идиома guard_obj.

При установке MtCallback используем идиому guard_obj.

Само по себе разделение Callback - MtCallback - уже проблема. В идеале
MtCallback нужно оформить так, чтобы можно было безболезненно объединить этот
класс с Callback, аналогично Ref и WeakRef.

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

    guard_obj - это:
      * Индикатор возможности вызова callback'а;
      * Объект, на удаление которого можно подписаться.

Возникает резонный вопрос о различиях в реализации MtObject и Object. Какие
гарантии можно дать для Object? Нужен ли вообще такой отдельный класс?

Попробую вывести необходимые гарантии с точки зрения многопоточности из примеров
применения Object и MtObject.

1. Object. Применяется, когда доступ к объекту полностью синхронный. То есть
   такие объекты относятся к некоторой синхронизированной области, не выходя
   за её пределы. В целом это означает, что объекты Object могут использоваться
   только в пределах реализации некоторого класса (только одного). В этом случае
   совершенно не имеют смысла средства DeletionCallback. Полезность WeakRef в
   этом случае также весьма сомнительна (трудно представить себе ситуацию, в
   которой в рамках реализации класса требуется использование слабых ссылок).

Получаем ~ следующую схему:

    Реализация одного класса| Сложный программный модуль | Программный комплекс
  --------------------------+----------------------------+----------------------
       Обычные редства C++  |    Ref<MtReferenced>       |   Обмен сообщениями
       Ref<Referenced>      |    Ref<MtObject>           |       (myrelay)

То есть нет смысла в синхронной версии Object. На практике оправдана только
асинхронная версия - MtObject.

Соответсвенно, получаю, что guard_obj имеет смысл только на уровне сложного
программного модуля. Это означает, что все стыки с callback'ами разделяются
по уровню использования. Более высокоуровневые поддерживают guard_obj. Стыки
местного значения guard_obj не используют.

Защита на уровне weak_obj в MtCallback в стиле MyCpp - не вполне корректный
механизм. При его использовании ответственность за выполнение проверки
доступности целевого объекта переносится в место приссваивания cb.weak_obj= и
на вызывающий код. С другой стороны, это избавляет от необходимости создавать
вспомогательный объект Data для поддержки вызова. Но был ли хоть один случай,
когда Data не надо было создавать по другой причине? (по-моему, если и было,
то очень немного) И всё-таки, требование проверки weak_obj было весьма удобным.

Выводы:
    * Отказываюсь от weak_obj в MtCallback;
    * При необходимости guard_obj задаётся явно рядом с callback'ом - для
      того, чтобы подписываться на удаление клиента. ! В этом случае можно
      давать гарантии невызова после удаления, то есть можно не проверять
      weak_obj на стороне клиента - это и есть реальная и правильная
      альтернатива встраиванию weak_obj в MtCallback.
    * Важно понимать природу каждого конкретного callback'а. Но классический
      callback выполняется в стиле MtCallback: со ссылкой VirtRef на данные.

      ! Данные можно оформлять как Referenced (а не MtReferenced), если
      управление ими полностью передаётся объекту-генератору событий - но только
      при условии, что внутренняя логика управления этими данными проста
      (например, refcount строго <= 1). В противном случае таких строгих
      гарантий дать нельзя. Да и генерирующей стороне не стоит рассчитывать
      на эксклюзивное управление пользовательскими данными. Это означает, что
      данные в объекте callback должны быть MtReferenced или MtObject, что,
      в свою очередь, означает, что нужно чёткое разделение между MtReferenced
      и Referenced: не должно быть способа их спутать.
      
      А вот MtObject может быть представлен как MtReferenced. Это делается через
      VirtMtReferenced. Название само по себе - отпугивающее, и подразумевает
      существование VirtReferenced, который лишён смысла ввиду отсутствия
      Object. Полагаю, что стоит выделить не-mt-safe классы, а mt-safe избавить
      от префикса "Mt". Это поможет предотвратить нечаянное использование
      Referenced там, где на самом деле требуется MtReferenced (! верно).
      Подойдёт название вроде "BasicReferenced". Такое название подчёркивает,
      что при работе с этим типом нужно синхронизироваться так же, как и при
      работе с basic data types (а название "SimplyReferenced", которое мне
      вполне по душе, уже занято устаревшим кодом MyCpp).

Результаты:
    * VirtReferenced - базовый для Referenced и Object, содержит всего два
      виртуальных метода: ref и unref;
    * Referenced - объекты, поддерживающие только упрощённый mt-safe
      подсчёт ссылок (Ref);
    * Object - mt-safe объекты, поддерживающие расширенный подсчёт ссылок
      (Ref, WeakRef) и deletion callbacks. Имеют встроенный мьютекс состояния
      Object::mutex;
    * BasicReferenced - не-mt-safe объекты, поддерживающие элементарный
      не-mt-safe подсчёт ссылок (Ref);
    * Callback - обобщённый mt-safe callback с элементом "VirtRef ref";
    * Ref - применим к Object, Referenced и BasicReferenced;
    * WeakRef - применим только к Object;
    * VirtRef - применимо к потомкам VirtReferenced.

Если потребуется обобщённый не-mt-safe callback, то он будет называться
"BasicCallback".

------

11.05.31 Объединил код подсчёта ссылок в MyCpp и LibMary: теперь MyCpp
использует новую реализацию, а старая удалена. Выявился ряд проблем в LibMary.
В связи с этим возвращаюсь к доводке кода подсчёта ссылок. Основные вопросы:
    * DeletionSubscriptions:
	  - В MyCpp клиент удерживает объект, описывающий подписку, ref'ом.
	    Подписка содержит поле valid;
	  - Текущая реализация MT-некорректна (особенно в части mutual_sbn).
    * Нужно общее обоснование корректности кода;
    * Реализация DeletionQueue нетривиальна и требует комментариев.

Сначала разбираюсь с тем, как должны работать DeletionSubscriptions.

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

При подписке на удаление клиента сервер получает DeletionSubscriptionKey. Этот
ключ гарантированно валиден до тех пор, пока сервер не откажется от подписки
или пока сервер или клиент не будут удалены. Такое определение времени жизни
ключа выглядит логичным, поэтому нет необходимости в удержании
DeletionSubscription ссылкой Ref<>, как это было принято в MyCpp. Таким образом,
текущая семантика DeletionSubscription в LibMary остаётся неизменной, и нужно
только исправить ошибки в реализации.

Логика DeletionSubscription и WeakRef практически не пересекается. Их можно
проверять отдельно. Для WeakRef нужно объяснить начзначение счётчика
lastref_cnt.

---

Фигуранты по DeletionSubscription:
    * DeletionSubscription;
	  Структура, описывающая подписку;
    * deletion_subscription_list;
	  Список DeletionSubscriptions. Доступ к этому списку синхронизируется
	  с помощью Object::mutex;
    * mutualDeletionCallback();
	  Уведомление об удалении сервера;
    * addDeletionCallbackNonmutual();
	  Добавляет DeletionCallback, не устанавливая обратную связь по удалению
	  клиента;
    * last_unref()
	  Вызывается асинхронно при достижении refcount == 0;
	  Вызывает do_delete(), если пришло время удалить объект;
    * do_delete()
	  Ставит объект в очередь deletionQueue, если нужно;
	  Вызывает deletion subscriptions;
    * addDeletionCallback_unlocked();
	  Версия addDeletionCallback(), не захватывающая mutex.
    * addDeletionCallback();
	  Добавляет DeletionCallback и устанавливает обратную связь по удалению
	  клиента;
    * removeDeletionCallback_unlocked();
	  Версия removeDeletionCallback(), не захватывающая mutex;
    * removeDeletionCallback();
	  Удаляет ответную подписку, удаляет DeletionSubscription;
    * ~Object()
	  Удаляет _Shadow.

? Есть ли смысл в существовании класса Callback отдельно от Cb?
    - Класс Cb удобен тем, что позволяет устанавливать связи с MT-unsafe
      объектами, работа которых синхронизируется извне. Оба класса нужны только
      там, где нужно генерировать события для асинхронных получателей.
      Класс Callback в текущем исполнении подходит только для объектов, которые
      синхронизируют себя самостоятельно.
      
      Callback эффективнее, чем Cb, так как операция ref() легче, чем _GetRef().
      Задача обоих классов - защитить уведомляемый объект от разрушения на время
      работы callback'а. Cb опирается на механизм CodeReferenced и требует,
      чтобы контейнер уведомляемого объекта был порождён от Object. Второй
      недостаток Cb в том, что он удерживает Ref на _Shadow контейнера.

      Для того, чтобы обойтись без Cb, нужно синхронизировать управление
      подписками извне механизмом, который использется для внешней синхронизации
      работы объекта. Этому мешает многослойная декомпозиция программы.

      Механизм Cb более универсален, чем Callback. Он позволяет создавать более
      общие интерфейсы, которые могут реализовываться как асинхронными, так и
      синхронными объектами (при условии, что Cb устанавливается однократно
      во время инициализации синхронного объекта, либо с использованием внешнего
      механизма синхронизации). Стоит заметить, что Cb во многом повторяет
      MyCpp::CallbackDesc и дополняет его CodeRef'ами.

      Оставляю оба механизма, так как нет достаточно веских аргументов в пользу
      отказа от любого из них. Callback - эффективный интерфейс, Cb - более
      гибкий, удобный, но менее эффективный.

      Callback можно переименовать в CbLight.

Строим корректную реализацию DeletionSubscriptions.

1. do_delete(). Нужно аккуратно вызвать deletion subscripions.

   Ссылок на удаляемый объект на момент выполнения do_delete() уже нет, но
   связи по deletion subscriptions всё ещё есть. Они могут удаляться через
   механизм mutual_sbn при удалении peer'а, причём такое удаление будет также
   выполняться методом do_delete(). То есть в вопросе deletion subscriptions
   do_delete() должна синхронизироваться с самой собой.

   Это означает, что во время исполнения do_delete в любой момент может быть
   вызван метод mutualDeletionCallback. Это уже более серьёзная проблема. Можем
   ли мы отложить удаление объекта на время работы mutualDeletionCallback?

   Проблему можно снять, если использовать для вызова mutualDeletionCallback
   WeakRef. Это представляется недостаточно эффективным, потому что требует
   удержания Ref'а на Shadow. Но если я не придумаю способа синхронизации без
   дополнительных Ref'ов, то WeakRef - хороший вариант.

   ! Можно держать DeletionSubscription и mutual subscription в общем участке
     памяти. -1 malloc на установление связи по DeletionCallback. /Сначала
     доведу текущий вариант, потом можно оптимизировать./

   Допустим, во время работы do_delete() вызван mutualDeletionCallback. Он будет
   работать с теми же данными, что и do_delete(), с тем же объектом. Задача
   mutualDeletionCallback - удалить подписку из списка
   deletion_subscription_list и освободить занятые подпиской ресурсы.

   Вызов mutualDeletionCallback выполняется с незахваченным мьютексом mutex
   объекта, создавшего mutual-подписку. Чтобы это работало, необходим механизм
   удержания ссылки на объект на время выполнения mutualDeletionCallback. Есть
   два варианта:
       1) Использовать WeakRef. Это простой и понятный механизм. Хорошо
	  согласуется с текущей реализацией;
       2) Получать ссылку на объект в do_delete() до того, как отпускаем mutex
	  перед вызовом deletion callback. Это более быстрый вариант (не требует
	  удержания Ref'а на _Shadow), но появляется дополнительный усложняющий
	  фактор: даже после зануления weak_ptr в _Shadow в любой момент может
	  быть добавлена ссылка на объект.
	  ? А нужно ли удерживать Ref на _Shadow, если известно, что _Shadow
	    существует, пока в списке deletion_subscription_list под
	    Object::mutex есть подписка?
		- Нет, ссылку можно не удерживать, если выполнять _GetRef под
		  mutex'ом. Но остаётся разница в эффективности _GetRef() и
		  простого ref().

  Итак, единственное преимущество второго подхода состоит в том, что ref()
  эффективнее, чем _GetRef(). Рассмотрим этот случай подробнее.

    * В любой момент может появиться ссылка, _но_ только с целью вызова
      mutualDeletionCallback. До того момента, как мы занулили weak_ptr в
      _Shadow, эти дополнительные ссылки ничем не отличаются от обычных ссылок,
      и откладывают момент зануления _Shadow наравне со всеми, что допустимо.

      После зануления _Shadow начинаются коллизии. Первой нарушается логика
      lastref_cnt: пар getRef()/unref() одновременно может выполняться несколько.
      Здесь можем зацепиться за то, что произвольные ref'ы захватываются только
      для выполнения mutualDeletionCallack. Но тогда придётся вводить
      дополнительную пару ref/unref в do_delete чтобы гарантировать, что
      delete *this вызывается только 1 раз.
      
      Всё это выглядит как дублирование механизма WeakRef, поэтому для mutual
      deletion callbacks буду использовать WeakRef: это проще, это надёжнее.

      Нужно ли использовать WeakRef для первичных подписок?
      Два объекта могут удаляться одновременно, то есть мы одновременно можем
      оказаться в методах do_delete() двух разных объектов. Перед вызовом
      любого deletion callback нужно обеспечить доступность объекта на время
      вызова. Для этого нужно воспользоваться WeakRef. Поэтому WeakRef нужен
      всем подпискам без исключения.

  В MyCpp синхронизация выполнена с помощью удержания Ref'а на
  DeletionSubscription и атомарного флага invalid <- Это не совсем так, потому
  что основной механизм в MyCpp - WeakRef (!).

/ Делаю реализацию на WeakRef'ах /
/ Работает :) Перевёл все модули MyNC на новый механизм /

------

11.06.07 Можно ли использовать Object::mutex для синхронизации deletion subscriptions?

Попробуем разобраться. Действия с deletion subscriptions, требующие
синхронизации:
    * addDeletionCallback();
    * removeDeletionCallback();
    * вызов deletion subscriptions в do_delete();
    * mutualDeletionCallback().

Метод addDeletionCallback() может быть вызван в произвольный момент методом
другого объекта. Можно следить за тем, чтобы вообще не вызывать методов
с произвольным поведением при захваченном Object::mutex.

removeDeletionCallback() вызывается аналогично addDeletionCallback().

do_delete() - безопасное место, т к он не вызывается при захваченном
Object::mutex.

mutualDeletionCallback не вызывается при захваченном Object::mutex, т к это
StateMutex (активирует deletion queue для отложенного удаления объектов).

То есть конфликты могут возникать только при вызовае addDeletionCallback/
removeDeletionCallback. Думаю, с этим можно справиться.

