Thoughts on simple paged search results

[Debajyoti Bera <dbera@cse.iitk.ac.in>]

Hi
	I thought of working on implementing OpenLDAP paged search result. I am 
jotting down my observations and thoughts below.
	Its clear that such a facility can't be built in to ldapsearch without 
support from backend. So primarily some backend routines are to be written to 
support some sort of range search. Now OpenLDAP supports a large number of 
backends, but it seems that the major ones are back-ldbm and back-bdb. 
However, back-bdb is still in rapid stages of development (implementation of 
indices are currently being carried out), so back-ldbm may be the place to 
start with.
	Now, the ldapsearch routine just calls the appropriate search function for 
the specified backend and passes it all the search paramaters alongwith 
(connection *conn, operation *op). The cursors of the databases can be used to 
store the point from which search for the next set of results can be started. 
As this seems to be some sort of persistent feature for that connection, it 
easier to store the cursors in 'conn'. Besides the cursor, the backend 
specific search depends on an array candidates[] of IDs. But the array is 
quite a large one, so currently we can store only a few such strcutures in 
conn (i.e. effectively limiting the number of simultaneous paged based search 
a client can do on one connection). So the changes go like this (I was 
changing them in the files but due to my incoming exams, I have stopped 
temporarily):

in struct slap_conn add field
void *paged_search;

During initialization of backends, this has to be properly initialised. For
back-ldbm (and similarly for back-bdb)
in back-ldbm (and similarly in back-bdb)

struct ldbm_paged_search_t{
	ID cursor;
	ID_BLOCK *candidates;
	//some other info
	char *cookie;
	int index; //index into the persistent_search array
	//some verification inforamtion like
	char *base_dn; //etc
};
#define LDBM_MAX_PAGED_SEARCH_CONNECTION 2
struct ldbm_paged_search_t ldbm_paged_search[LDBM_MAX_PAGED_SEARCH_CONNECTION];
paged_search=(void *)ldbm_paged_search;

Then when in ldapsearch (i.e. servers/slapd/search.c) the controls are
detected, these fields are initialized if there is a paged search control. The
search routine is similar, only the candidates[] and cursor are not to be
generated but taken from the conn->paged_search[...].cursor etc. The
appropriate index in the ldbm_paged_search[...] has to be found which may be
done by inserting the index number in the cookie itself or by searching the
presented cookie in all cookies (the size of the array ldbm_paged_search won't
be too large, so a linear search would do). Thus the when the do_search()
calls backend specific search function, it has to pass the new values like the
number of results desired, value of cookie etc. which can be passed by
creating another data type:
typedef struct paged_control_t{
	char *cookie;
	int range;
	//etc...
} paged_control;

To protect against non-conformant clients, the search routines should check
that the baseDN, scope etc in all the successive retreivals of a paged search
is the same as that of the first request. This check can be done in back-end
specific search routines as there we have the values for the current search
and as well as from the first search (during the first search the fields in
the lbdm_paged_search are initialised with corresponding values).
Lastly, care has to be taken to appropriately free the memory locations which
can be done as and when we know that the connection is closed (sort of
registering a callback with the destruction of conn - I didnot think on this
much).
I started implementing but had to stop at middle. The changes are not enough
to be submitted.
Sincerely,
Debajyoti