RE: (ITS#6985) sssvlv / greaterThanOrEqual problem

[ctcard@hotmail.com]

> > > >
> > > > I am running slapd built from HEAD on June 30th 2011, with back-sql
> > >
> > > Can you confirm this issue with another backend, e.g. back-bdb? Bugs
> > > specific to back-sql or to interaction with it could receive only marginal
> > > attention.
> > >
> > > p.
> > >
> >
> > I've imported my data into a server with a bdb backend, and I see the same problem.
> >
> > 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.
>
> 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).
>
> 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.
>

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.

Chris