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.It depends how you read the comment. If the function is *entered* with root == NULL, then I agree that -1 is returned, but if the while loop exits with root == NULL then the last comparison result is returned, which causes problems to the call in sssvlv.c.>
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. Possibly. But with the patch as suggested, the sssvlv code works correctly and gets the correct node.If you think these changes might break other uses of tavl_find3() (of which there didn't seem to be many), perhapstavl_find4() could be added.
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
-
ctcard＠hotmail.com