[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: (ITS#6985) sssvlv / greaterThanOrEqual problem



ctcard@hotmail.com wrote:
>>>> Looking at the code in sssvlv.c, it uses tavl_find3() to search the values, but the
>>>> code in tavl_find3() looks to me that it only works properly with an exact match
>>>> type of matching rule:
>>>>
>>>> Avlnode *
>>>> tavl_find3( Avlnode *root, const void *data, AVL_CMP fcmp, int *ret )
>>>> {
>>>> int cmp = -1, dir;
>>>> Avlnode *prev = root;
>>>>
>>>> while ( root != 0&&  (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
>>>> prev = root;
>>>> dir = cmp>  0;
>>>> root = avl_child( root, dir );
>>>> }
>>>> *ret = cmp;
>>>> return root ? root : prev;
>>>> }
>>>>
>>>> since the while loop terminates when the fcmp function returns 0 (i.e. exact match).
>>>>
>>>
>>> I think I've worked out where the problem is.
>>> Firstly, there's a comment before tavl_find3() saying
>>> /*
>>> * tavl_find2 - returns Avlnode instead of data pointer.
>>> * tavl_find3 - as above, but returns Avlnode even if no match is found.
>>> * also set *ret = last comparison result, or -1 if root == NULL.
>>> */
>>>
>>> but the "or -1 if root == NULL" is not done.

Not true; since cmp is initialized to -1, it will return -1 when the function 
is entered with root == NULL. There is no bug in this part.

>>> Secondly, if no exact match is found, prev is returned which may point to a node which is less than the search
>>> node, depending on what the tree looks like, but we really want a pointer to the last node which was greater than
>>> the search node to be returned.
>>>
>>> Once these fixes are done, the correct node is returned by tavl_find3 to the call in send_list() in sssvlv.c (line 523).

This fix is also not correct. Possibly tavl_find3() has been misused in the 
sssvlv code, but this function works as designed.

>>> There is another bug in send_list() in sssvlv.c, at lines 535-544:
>>>
>>> if ( i>  0 ) {
>>> tmp_node = tavl_end(so->so_tree, TAVL_DIR_RIGHT);
>>> dir = TAVL_DIR_LEFT;
>>> } else {
>>> tmp_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
>>> dir = TAVL_DIR_RIGHT;
>>> }
>>> for (i=0; tmp_node != cur_node;
>>> tmp_node = tavl_next( tmp_node, dir ), i++);
>>> so->so_vlv_target = i;
>>> This code is ok if the cur_node is in the left hand side of the tree, but if it is in the rhs of the tree so_vlv_target is set
>>> to an offset from the end of the list, rather than the beginning.

OK, looks like you have a good patch for this.

>> One more issue: the most recent draft spec for vlv (http://tools.ietf.org/html/draft-ietf-ldapext-ldapv3-vlv-09) states that the offset field in the vlv request has range 1..maxInt whereas the targetPosition in the vlv response has range 0..maxInt.
>>
>> However, my interpretation of the spec is that offset and targetPosition represent the same thing, i.e. the position of the target entry in the list, with the first entry having offset/targetPosition = 1.
>>
>> If that interpretation is correct, the assignment of so_vlv_target in the code above is off by one, since i will be zero if cur_node is at the beginning of the list.
>>
>
> I've uploaded a patch to ftp.openldap.org, incoming/Chris-Card-110708.ITS-6985-fix.patch
>
> Chris

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/