[fpc-devel] TAVLTree(avl_tree.pp) thread safety, fcl-xml(DOM) is also concerned.

[Inoussa OUEDRAOGO]

2008/8/6 Mattias Gaertner <nc-gaertnma at netcologne.de>:
> On Wed, 6 Aug 2008 21:19:13 +0100
> "Inoussa OUEDRAOGO" <inoussa12 at gmail.com> wrote:
>
>> 2008/8/6 Mattias Gaertner <nc-gaertnma at netcologne.de>:
>> > On Wed, 6 Aug 2008 19:41:27 +0100
>> > "Inoussa OUEDRAOGO" <inoussa12 at gmail.com> wrote:
>> >
>> >> Hi,
>> >>
>> >> TAVLTree in avl_tree.pp is not thread safe due to the node
>> >> allocation and de-allocation done through the global
>> >> declared "NodeMemManager" variable. TAVLTreeNodeMemManager
>> >> implementation is cleary not thread safe, which btw IMHO
>> >> is a good thing ( for performance reason).
>> >>
>> >> Proposition :
>> >>
>> >> (a) TAVLTree should allow, at construct time, to
>> >>     specify a Node memory manager which will be kept and used.
>> >>     If not specified the global one will be used.
>> >>
>> >> (b) "NodeMemManager" should be declared as "ThreadVar".
>> >>
>> >> This changes does not break the API while making the
>> >> implementation thread safe.
>> >>
>> >> By the way note that the XML DOM's implementation
>> >> ( TDOMNode_WithChildren ) uses TAVLTree, so every code that uses
>> >> the fcl-xml package mainly the DOM unit, is not thread safe. If
>> >> this proposition is accepted it will be nice to have it introduced
>> >> in the soon to be release fpc 2.2.2, in the case that is still
>> >> possible, mainly for server programming.
>> >>
>> >> Attached is a patch that demonstrate the above proposition.
>> >
>> > Providing a local node mem manager does not repair xml dom.
>>
>> A "threadvar" declared variable is local to the calling thread.
>
> The variable is currently initialized via the initialization section.
> A ThreadA creating a TXMLConfig, which creates a tree will have no mem
> manager.
>
>> But if object is modified in more than one thread, indeed there are
>> still some problems ( for objects using the default manager ) :
>>  Thread A create a node n1 and the node is released in ThreadB .
>>
>> > Maybe move NodeMemManager to the interface, so that a user can
>> > replace it with a threadsafe one?
>>
>> Good solution, but : if ThreadA create an avl object that is
>> _exclusively_ used in ThreadA, why should ThreadA wait in a
>> multithreaded node mem manager? That is when comes the constructor
>> that takes a node mem manager. That way, ThreadA could provide a
>> local node mem manager that is not multithreaded and thus not paying
>> penalty of multithreaded node mem manager.
>
> Yes, threadvar is a good idea. But still a thread needs to initialize
> it.

You are absolutely rigth.

> But a structure with less mem might be even better for dom xml as
> already mentioned by Sergei.

Indeed. But the avl implementation provided can be used without xml. So
my second proposition :

Another proposition is to introduce a base avl class say TBaseAVLTree
that defines two abstract virtual methods "NewNode()" and "FreeNode()"
and then define :
  - TAVLTree : that _do not_ use a node mem manager
  - TAVLMangedTree that uses a node mem manager provided in the constructor


TBaseAVLTree = class
...
protected
  function NewNode() : TAVLTreeNode;virtual;abstract;
  procedure FreeNode(ANode : TAVLTree);virtual;abstract;
...
end;

TAVLTree = class(TBaseAVLTree)
protected
  function NewNode() : TAVLTreeNode;override;
  { implemented as
    begin
      Result:=TAVLTreeNode.Create();
    end;}

  procedure FreeNode(ANode : TAVLTree);override;
  { implemented as
    begin
      if ( ANode <> nil ) then
        ANode.Free();
    end;}
end;

TAVLMangedTree = class(TBaseAVLTree)
private
  FNodeMemManager : TAVLTreeNodeMemManager;
protected
  // these implementations use FNodeMemManager
  function NewNode() : TAVLTreeNode;override;
  procedure FreeNode(ANode : TAVLTree);override;
public
  constructor Create(OnCompareMethod: TListSortCompare;
ANodeMemManager : TAVLTreeNodeMemManager);
end;


-- 
Inoussa O.