ctcard(a)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/