Back to index

openldap  2.4.31
sssvlv.c
Go to the documentation of this file.
00001 /* sssvlv.c - server side sort / virtual list view */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2009-2012 The OpenLDAP Foundation.
00006  * Portions copyright 2009 Symas Corporation.
00007  * All rights reserved.
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted only as authorized by the OpenLDAP
00011  * Public License.
00012  *
00013  * A copy of this license is available in the file LICENSE in the
00014  * top-level directory of the distribution or, alternatively, at
00015  * <http://www.OpenLDAP.org/license.html>.
00016  */
00017 /* ACKNOWLEDGEMENTS:
00018  * This work was initially developed by Howard Chu for inclusion in
00019  * OpenLDAP Software. Support for multiple sorts per connection added
00020  * by Raphael Ouazana.
00021  */
00022 
00023 #include "portable.h"
00024 
00025 #ifdef SLAPD_OVER_SSSVLV
00026 
00027 #include <stdio.h>
00028 
00029 #include <ac/string.h>
00030 #include <ac/ctype.h>
00031 
00032 #include <avl.h>
00033 
00034 #include "slap.h"
00035 #include "lutil.h"
00036 #include "config.h"
00037 
00038 #include "../../../libraries/liblber/lber-int.h" /* ber_rewind */
00039 
00040 /* RFC2891: Server Side Sorting
00041  * RFC2696: Paged Results
00042  */
00043 #ifndef LDAP_MATCHRULE_IDENTIFIER
00044 #define LDAP_MATCHRULE_IDENTIFIER      0x80L
00045 #define LDAP_REVERSEORDER_IDENTIFIER   0x81L
00046 #define LDAP_ATTRTYPES_IDENTIFIER      0x80L
00047 #endif
00048 
00049 /* draft-ietf-ldapext-ldapv3-vlv-09.txt: Virtual List Views
00050  */
00051 #ifndef LDAP_VLVBYINDEX_IDENTIFIER
00052 #define LDAP_VLVBYINDEX_IDENTIFIER    0xa0L
00053 #define LDAP_VLVBYVALUE_IDENTIFIER     0x81L
00054 #define LDAP_VLVCONTEXT_IDENTIFIER     0x04L
00055 
00056 #define LDAP_VLV_SSS_MISSING       0x4C
00057 #define LDAP_VLV_RANGE_ERROR       0x4D
00058 #endif
00059 
00060 #define SAFESTR(macro_str, macro_def) ((macro_str) ? (macro_str) : (macro_def))
00061 
00062 #define SSSVLV_DEFAULT_MAX_KEYS    5
00063 #define SSSVLV_DEFAULT_MAX_REQUEST_PER_CONN 5
00064 
00065 #define NO_PS_COOKIE (PagedResultsCookie) -1
00066 #define NO_VC_CONTEXT (unsigned long) -1
00067 
00068 typedef struct vlv_ctrl {
00069        int vc_before;
00070        int vc_after;
00071        int    vc_offset;
00072        int vc_count;
00073        struct berval vc_value;
00074        unsigned long vc_context;
00075 } vlv_ctrl;
00076 
00077 typedef struct sort_key
00078 {
00079        AttributeDescription *sk_ad;
00080        MatchingRule                *sk_ordering;
00081        int                                       sk_direction; /* 1=normal, -1=reverse */
00082 } sort_key;
00083 
00084 typedef struct sort_ctrl {
00085        int sc_nkeys;
00086        sort_key sc_keys[1];
00087 } sort_ctrl;
00088 
00089 
00090 typedef struct sort_node
00091 {
00092        int sn_conn;
00093        int sn_session;
00094        struct berval sn_dn;
00095        struct berval *sn_vals;
00096 } sort_node;
00097 
00098 typedef struct sssvlv_info
00099 {
00100        int svi_max;  /* max concurrent sorts */
00101        int svi_num;  /* current # sorts */
00102        int svi_max_keys;    /* max sort keys per request */
00103        int svi_max_percon; /* max concurrent sorts per con */
00104 } sssvlv_info;
00105 
00106 typedef struct sort_op
00107 {
00108        Avlnode       *so_tree;
00109        sort_ctrl *so_ctrl;
00110        sssvlv_info *so_info;
00111        int so_paged;
00112        int so_page_size;
00113        int so_nentries;
00114        int so_vlv;
00115        int so_vlv_rc;
00116        int so_vlv_target;
00117        int so_session;
00118        unsigned long so_vcontext;
00119 } sort_op;
00120 
00121 /* There is only one conn table for all overlay instances */
00122 /* Each conn can handle one session by context */
00123 static sort_op ***sort_conns;
00124 static ldap_pvt_thread_mutex_t sort_conns_mutex;
00125 static int ov_count;
00126 static const char *debug_header = "sssvlv";
00127 
00128 static int sss_cid;
00129 static int vlv_cid;
00130 
00131 /* RFC 2981 Section 2.2
00132  * If a sort key is a multi-valued attribute, and an entry happens to
00133  * have multiple values for that attribute and no other controls are
00134  * present that affect the sorting order, then the server SHOULD use the
00135  * least value (according to the ORDERING rule for that attribute).
00136  */
00137 static struct berval* select_value(
00138        Attribute            *attr,
00139        sort_key                    *key )
00140 {
00141        struct berval* ber1, *ber2;
00142        MatchingRule *mr = key->sk_ordering;
00143        unsigned i;
00144        int cmp;
00145 
00146        ber1 = &(attr->a_nvals[0]);
00147        ber2 = ber1+1;
00148        for ( i = 1; i < attr->a_numvals; i++,ber2++ ) {
00149               mr->smr_match( &cmp, 0, mr->smr_syntax, mr, ber1, ber2 );
00150               if ( cmp > 0 ) {
00151                      ber1 = ber2;
00152               }
00153        }
00154 
00155        Debug(LDAP_DEBUG_TRACE, "%s: value selected for compare: %s\n",
00156               debug_header,
00157               SAFESTR(ber1->bv_val, "<Empty>"),
00158               0);
00159 
00160        return ber1;
00161 }
00162 
00163 static int node_cmp( const void* val1, const void* val2 )
00164 {
00165        sort_node *sn1 = (sort_node *)val1;
00166        sort_node *sn2 = (sort_node *)val2;
00167        sort_ctrl *sc;
00168        MatchingRule *mr;
00169        int i, cmp = 0;
00170        assert( sort_conns[sn1->sn_conn]
00171               && sort_conns[sn1->sn_conn][sn1->sn_session]
00172               && sort_conns[sn1->sn_conn][sn1->sn_session]->so_ctrl );
00173        sc = sort_conns[sn1->sn_conn][sn1->sn_session]->so_ctrl;
00174 
00175        for ( i=0; cmp == 0 && i<sc->sc_nkeys; i++ ) {
00176               if ( BER_BVISNULL( &sn1->sn_vals[i] )) {
00177                      if ( BER_BVISNULL( &sn2->sn_vals[i] ))
00178                             cmp = 0;
00179                      else
00180                             cmp = sc->sc_keys[i].sk_direction;
00181               } else if ( BER_BVISNULL( &sn2->sn_vals[i] )) {
00182                      cmp = sc->sc_keys[i].sk_direction * -1;
00183               } else {
00184                      mr = sc->sc_keys[i].sk_ordering;
00185                      mr->smr_match( &cmp, 0, mr->smr_syntax, mr,
00186                             &sn1->sn_vals[i], &sn2->sn_vals[i] );
00187                      if ( cmp )
00188                             cmp *= sc->sc_keys[i].sk_direction;
00189               }
00190        }
00191        return cmp;
00192 }
00193 
00194 static int node_insert( const void *val1, const void *val2 )
00195 {
00196        /* Never return equal so that new entries are always inserted */
00197        return node_cmp( val1, val2 ) < 0 ? -1 : 1;
00198 }
00199 
00200 static int pack_vlv_response_control(
00201        Operation            *op,
00202        SlapReply            *rs,
00203        sort_op                     *so,
00204        LDAPControl   **ctrlsp )
00205 {
00206        LDAPControl                 *ctrl;
00207        BerElementBuffer     berbuf;
00208        BerElement                  *ber          = (BerElement *)&berbuf;
00209        struct berval        cookie, bv;
00210        int                                rc;
00211 
00212        ber_init2( ber, NULL, LBER_USE_DER );
00213        ber_set_option( ber, LBER_OPT_BER_MEMCTX, &op->o_tmpmemctx );
00214 
00215        rc = ber_printf( ber, "{iie", so->so_vlv_target, so->so_nentries,
00216               so->so_vlv_rc );
00217 
00218        if ( rc != -1 && so->so_vcontext ) {
00219               cookie.bv_val = (char *)&so->so_vcontext;
00220               cookie.bv_len = sizeof(so->so_vcontext);
00221               rc = ber_printf( ber, "tO", LDAP_VLVCONTEXT_IDENTIFIER, &cookie );
00222        }
00223 
00224        if ( rc != -1 ) {
00225               rc = ber_printf( ber, "}" );
00226        }
00227 
00228        if ( rc != -1 ) {
00229               rc = ber_flatten2( ber, &bv, 0 );
00230        }
00231 
00232        if ( rc != -1 ) {
00233               ctrl = (LDAPControl *)op->o_tmpalloc( sizeof(LDAPControl)+
00234                      bv.bv_len, op->o_tmpmemctx );
00235               ctrl->ldctl_oid                    = LDAP_CONTROL_VLVRESPONSE;
00236               ctrl->ldctl_iscritical      = 0;
00237               ctrl->ldctl_value.bv_val = (char *)(ctrl+1);
00238               ctrl->ldctl_value.bv_len = bv.bv_len;
00239               AC_MEMCPY( ctrl->ldctl_value.bv_val, bv.bv_val, bv.bv_len );
00240               ctrlsp[0] = ctrl;
00241        } else {
00242               ctrlsp[0] = NULL;
00243               rs->sr_err = LDAP_OTHER;
00244        }
00245 
00246        ber_free_buf( ber );
00247 
00248        return rs->sr_err;
00249 }
00250 
00251 static int pack_pagedresult_response_control(
00252        Operation            *op,
00253        SlapReply            *rs,
00254        sort_op                     *so,
00255        LDAPControl   **ctrlsp )
00256 {
00257        LDAPControl                 *ctrl;
00258        BerElementBuffer     berbuf;
00259        BerElement                  *ber          = (BerElement *)&berbuf;
00260        PagedResultsCookie   resp_cookie;
00261        struct berval        cookie, bv;
00262        int                                rc;
00263 
00264        ber_init2( ber, NULL, LBER_USE_DER );
00265        ber_set_option( ber, LBER_OPT_BER_MEMCTX, &op->o_tmpmemctx );
00266 
00267        if ( so->so_nentries > 0 ) {
00268               resp_cookie          = ( PagedResultsCookie )so->so_tree;
00269               cookie.bv_len = sizeof( PagedResultsCookie );
00270               cookie.bv_val = (char *)&resp_cookie;
00271        } else {
00272               resp_cookie          = ( PagedResultsCookie )0;
00273               BER_BVZERO( &cookie );
00274        }
00275 
00276        op->o_conn->c_pagedresults_state.ps_cookie = resp_cookie;
00277        op->o_conn->c_pagedresults_state.ps_count
00278               = ((PagedResultsState *)op->o_pagedresults_state)->ps_count
00279                 + rs->sr_nentries;
00280 
00281        rc = ber_printf( ber, "{iO}", so->so_nentries, &cookie );
00282        if ( rc != -1 ) {
00283               rc = ber_flatten2( ber, &bv, 0 );
00284        }
00285 
00286        if ( rc != -1 ) {
00287               ctrl = (LDAPControl *)op->o_tmpalloc( sizeof(LDAPControl)+
00288                      bv.bv_len, op->o_tmpmemctx );
00289               ctrl->ldctl_oid                    = LDAP_CONTROL_PAGEDRESULTS;
00290               ctrl->ldctl_iscritical      = 0;
00291               ctrl->ldctl_value.bv_val = (char *)(ctrl+1);
00292               ctrl->ldctl_value.bv_len = bv.bv_len;
00293               AC_MEMCPY( ctrl->ldctl_value.bv_val, bv.bv_val, bv.bv_len );
00294               ctrlsp[0] = ctrl;
00295        } else {
00296               ctrlsp[0] = NULL;
00297               rs->sr_err = LDAP_OTHER;
00298        }
00299 
00300        ber_free_buf( ber );
00301 
00302        return rs->sr_err;
00303 }
00304 
00305 static int pack_sss_response_control(
00306        Operation            *op,
00307        SlapReply            *rs,
00308        LDAPControl   **ctrlsp )
00309 {
00310        LDAPControl                 *ctrl;
00311        BerElementBuffer     berbuf;
00312        BerElement                  *ber          = (BerElement *)&berbuf;
00313        struct berval        bv;
00314        int                                rc;
00315 
00316        ber_init2( ber, NULL, LBER_USE_DER );
00317        ber_set_option( ber, LBER_OPT_BER_MEMCTX, &op->o_tmpmemctx );
00318 
00319        /* Pack error code */
00320        rc = ber_printf(ber, "{e}", rs->sr_err);
00321 
00322        if ( rc != -1)
00323               rc = ber_flatten2( ber, &bv, 0 );
00324 
00325        if ( rc != -1 ) {
00326               ctrl = (LDAPControl *)op->o_tmpalloc( sizeof(LDAPControl)+
00327                      bv.bv_len, op->o_tmpmemctx );
00328               ctrl->ldctl_oid                    = LDAP_CONTROL_SORTRESPONSE;
00329               ctrl->ldctl_iscritical      = 0;
00330               ctrl->ldctl_value.bv_val = (char *)(ctrl+1);
00331               ctrl->ldctl_value.bv_len = bv.bv_len;
00332               AC_MEMCPY( ctrl->ldctl_value.bv_val, bv.bv_val, bv.bv_len );
00333               ctrlsp[0] = ctrl;
00334        } else {
00335               ctrlsp[0] = NULL;
00336               rs->sr_err = LDAP_OTHER;
00337        }
00338 
00339        ber_free_buf( ber );
00340 
00341        return rs->sr_err;
00342 }
00343 
00344 /* Return the session id or -1 if unknown */
00345 static int find_session_by_so(
00346        int svi_max_percon,
00347        int conn_id,
00348        sort_op *so )
00349 {
00350        int sess_id;
00351        if (so == NULL) {
00352               return -1;
00353        }
00354        for (sess_id = 0; sess_id < svi_max_percon; sess_id++) {
00355               if ( sort_conns[conn_id] && sort_conns[conn_id][sess_id] == so )
00356                      return sess_id;
00357        }
00358        return -1;
00359 }
00360 
00361 /* Return the session id or -1 if unknown */
00362 static int find_session_by_context(
00363        int svi_max_percon,
00364        int conn_id,
00365        unsigned long vc_context,
00366        PagedResultsCookie ps_cookie )
00367 {
00368        int sess_id;
00369        for(sess_id = 0; sess_id < svi_max_percon; sess_id++) {
00370               if( sort_conns[conn_id] && sort_conns[conn_id][sess_id] &&
00371                   ( sort_conns[conn_id][sess_id]->so_vcontext == vc_context || 
00372                       (PagedResultsCookie) sort_conns[conn_id][sess_id]->so_tree == ps_cookie ) )
00373                      return sess_id;
00374        }
00375        return -1;
00376 }
00377 
00378 static int find_next_session(
00379        int svi_max_percon,
00380        int conn_id )
00381 {
00382        int sess_id;
00383        assert(sort_conns[conn_id] != NULL);
00384        for(sess_id = 0; sess_id < svi_max_percon; sess_id++) {
00385               if(!sort_conns[conn_id][sess_id]) {
00386                      return sess_id;
00387               }
00388        }
00389        if (sess_id >= svi_max_percon) {
00390               return -1;
00391        } else {
00392               return sess_id;
00393        }
00394 }
00395        
00396 static void free_sort_op( Connection *conn, sort_op *so )
00397 {
00398        int sess_id;
00399        if ( so->so_tree ) {
00400               tavl_free( so->so_tree, ch_free );
00401               so->so_tree = NULL;
00402        }
00403 
00404        ldap_pvt_thread_mutex_lock( &sort_conns_mutex );
00405        sess_id = find_session_by_so( so->so_info->svi_max_percon, conn->c_conn_idx, so );
00406        sort_conns[conn->c_conn_idx][sess_id] = NULL;
00407        so->so_info->svi_num--;
00408        ldap_pvt_thread_mutex_unlock( &sort_conns_mutex );
00409 
00410        ch_free( so );
00411 }
00412 
00413 static void free_sort_ops( Connection *conn, sort_op **sos, int svi_max_percon )
00414 {
00415        int sess_id;
00416        sort_op *so;
00417 
00418        for( sess_id = 0; sess_id < svi_max_percon ; sess_id++ ) {
00419               so = sort_conns[conn->c_conn_idx][sess_id];
00420               if ( so ) {
00421                      free_sort_op( conn, so );
00422                      sort_conns[conn->c_conn_idx][sess_id] = NULL;
00423               }
00424        }
00425 }
00426        
00427 static void send_list(
00428        Operation            *op,
00429        SlapReply            *rs,
00430        sort_op                     *so)
00431 {
00432        Avlnode       *cur_node, *tmp_node;
00433        vlv_ctrl *vc = op->o_controls[vlv_cid];
00434        int i, j, dir, rc;
00435        BackendDB *be;
00436        Entry *e;
00437        LDAPControl *ctrls[2];
00438 
00439        rs->sr_attrs = op->ors_attrs;
00440 
00441        /* FIXME: it may be better to just flatten the tree into
00442         * an array before doing all of this...
00443         */
00444 
00445        /* Are we just counting an offset? */
00446        if ( BER_BVISNULL( &vc->vc_value )) {
00447               if ( vc->vc_offset == vc->vc_count ) {
00448                      /* wants the last entry in the list */
00449                      cur_node = tavl_end(so->so_tree, TAVL_DIR_RIGHT);
00450                      so->so_vlv_target = so->so_nentries;
00451               } else if ( vc->vc_offset == 1 ) {
00452                      /* wants the first entry in the list */
00453                      cur_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
00454                      so->so_vlv_target = 1;
00455               } else {
00456                      int target;
00457                      /* Just iterate to the right spot */
00458                      if ( vc->vc_count && vc->vc_count != so->so_nentries ) {
00459                             if ( vc->vc_offset > vc->vc_count )
00460                                    goto range_err;
00461                             target = so->so_nentries * vc->vc_offset / vc->vc_count;
00462                      } else {
00463                             if ( vc->vc_offset > so->so_nentries ) {
00464 range_err:
00465                                    so->so_vlv_rc = LDAP_VLV_RANGE_ERROR;
00466                                    pack_vlv_response_control( op, rs, so, ctrls );
00467                                    ctrls[1] = NULL;
00468                                    slap_add_ctrls( op, rs, ctrls );
00469                                    rs->sr_err = LDAP_VLV_ERROR;
00470                                    return;
00471                             }
00472                             target = vc->vc_offset;
00473                      }
00474                      so->so_vlv_target = target;
00475                      /* Start at left and go right, or start at right and go left? */
00476                      if ( target < so->so_nentries / 2 ) {
00477                             cur_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
00478                             dir = TAVL_DIR_RIGHT;
00479                      } else {
00480                             cur_node = tavl_end(so->so_tree, TAVL_DIR_RIGHT);
00481                             dir = TAVL_DIR_LEFT;
00482                             target = so->so_nentries - target + 1;
00483                      }
00484                      for ( i=1; i<target; i++ )
00485                             cur_node = tavl_next( cur_node, dir );
00486               }
00487        } else {
00488        /* we're looking for a specific value */
00489               sort_ctrl *sc = so->so_ctrl;
00490               MatchingRule *mr = sc->sc_keys[0].sk_ordering;
00491               sort_node *sn;
00492               struct berval bv;
00493 
00494               if ( mr->smr_normalize ) {
00495                      rc = mr->smr_normalize( SLAP_MR_VALUE_OF_SYNTAX,
00496                             mr->smr_syntax, mr, &vc->vc_value, &bv, op->o_tmpmemctx );
00497                      if ( rc ) {
00498                             so->so_vlv_rc = LDAP_INAPPROPRIATE_MATCHING;
00499                             pack_vlv_response_control( op, rs, so, ctrls );
00500                             ctrls[1] = NULL;
00501                             slap_add_ctrls( op, rs, ctrls );
00502                             rs->sr_err = LDAP_VLV_ERROR;
00503                             return;
00504                      }
00505               } else {
00506                      bv = vc->vc_value;
00507               }
00508 
00509               sn = op->o_tmpalloc( sizeof(sort_node) +
00510                      sc->sc_nkeys * sizeof(struct berval), op->o_tmpmemctx );
00511               sn->sn_vals = (struct berval *)(sn+1);
00512               sn->sn_conn = op->o_conn->c_conn_idx;
00513               sn->sn_session = find_session_by_so( so->so_info->svi_max_percon, op->o_conn->c_conn_idx, so );
00514               sn->sn_vals[0] = bv;
00515               for (i=1; i<sc->sc_nkeys; i++) {
00516                      BER_BVZERO( &sn->sn_vals[i] );
00517               }
00518               cur_node = tavl_find3( so->so_tree, sn, node_cmp, &j );
00519               /* didn't find >= match */
00520               if ( j > 0 ) {
00521                      if ( cur_node )
00522                             cur_node = tavl_next( cur_node, TAVL_DIR_RIGHT );
00523               }
00524               op->o_tmpfree( sn, op->o_tmpmemctx );
00525 
00526               if ( !cur_node ) {
00527                      so->so_vlv_target = so->so_nentries + 1;
00528               } else {
00529                      sort_node *sn = so->so_tree->avl_data;
00530                      /* start from the left or the right side? */
00531                      mr->smr_match( &i, 0, mr->smr_syntax, mr, &bv, &sn->sn_vals[0] );
00532                      if ( i > 0 ) {
00533                             tmp_node = tavl_end(so->so_tree, TAVL_DIR_RIGHT);
00534                             dir = TAVL_DIR_LEFT;
00535                      } else {
00536                             tmp_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
00537                             dir = TAVL_DIR_RIGHT;
00538                      }
00539                      for (i=0; tmp_node != cur_node;
00540                             tmp_node = tavl_next( tmp_node, dir ), i++);
00541                      so->so_vlv_target = (dir == TAVL_DIR_RIGHT) ? i+1 : so->so_nentries - i;
00542               }
00543               if ( bv.bv_val != vc->vc_value.bv_val )
00544                      op->o_tmpfree( bv.bv_val, op->o_tmpmemctx );
00545        }
00546        if ( !cur_node ) {
00547               i = 1;
00548               cur_node = tavl_end(so->so_tree, TAVL_DIR_RIGHT);
00549        } else {
00550               i = 0;
00551        }
00552        for ( ; i<vc->vc_before; i++ ) {
00553               tmp_node = tavl_next( cur_node, TAVL_DIR_LEFT );
00554               if ( !tmp_node ) break;
00555               cur_node = tmp_node;
00556        }
00557        j = i + vc->vc_after + 1;
00558        be = op->o_bd;
00559        for ( i=0; i<j; i++ ) {
00560               sort_node *sn = cur_node->avl_data;
00561 
00562               if ( slapd_shutdown ) break;
00563 
00564               op->o_bd = select_backend( &sn->sn_dn, 0 );
00565               e = NULL;
00566               rc = be_entry_get_rw( op, &sn->sn_dn, NULL, NULL, 0, &e );
00567 
00568               if ( e && rc == LDAP_SUCCESS ) {
00569                      rs->sr_entry = e;
00570                      rs->sr_flags = REP_ENTRY_MUSTRELEASE;
00571                      rs->sr_err = send_search_entry( op, rs );
00572                      if ( rs->sr_err == LDAP_UNAVAILABLE )
00573                             break;
00574               }
00575               cur_node = tavl_next( cur_node, TAVL_DIR_RIGHT );
00576               if ( !cur_node ) break;
00577        }
00578        so->so_vlv_rc = LDAP_SUCCESS;
00579 
00580        op->o_bd = be;
00581 }
00582 
00583 static void send_page( Operation *op, SlapReply *rs, sort_op *so )
00584 {
00585        Avlnode              *cur_node            = so->so_tree;
00586        Avlnode              *next_node           = NULL;
00587        BackendDB *be = op->o_bd;
00588        Entry *e;
00589        int rc;
00590 
00591        rs->sr_attrs = op->ors_attrs;
00592 
00593        while ( cur_node && rs->sr_nentries < so->so_page_size ) {
00594               sort_node *sn = cur_node->avl_data;
00595 
00596               if ( slapd_shutdown ) break;
00597 
00598               next_node = tavl_next( cur_node, TAVL_DIR_RIGHT );
00599 
00600               op->o_bd = select_backend( &sn->sn_dn, 0 );
00601               e = NULL;
00602               rc = be_entry_get_rw( op, &sn->sn_dn, NULL, NULL, 0, &e );
00603 
00604               ch_free( cur_node->avl_data );
00605               ber_memfree( cur_node );
00606 
00607               cur_node = next_node;
00608               so->so_nentries--;
00609 
00610               if ( e && rc == LDAP_SUCCESS ) {
00611                      rs->sr_entry = e;
00612                      rs->sr_flags = REP_ENTRY_MUSTRELEASE;
00613                      rs->sr_err = send_search_entry( op, rs );
00614                      if ( rs->sr_err == LDAP_UNAVAILABLE )
00615                             break;
00616               }
00617        }
00618 
00619        /* Set the first entry to send for the next page */
00620        so->so_tree = next_node;
00621 
00622        op->o_bd = be;
00623 }
00624 
00625 static void send_entry(
00626        Operation            *op,
00627        SlapReply            *rs,
00628        sort_op                     *so)
00629 {
00630        Debug(LDAP_DEBUG_TRACE,
00631               "%s: response control: status=%d, text=%s\n",
00632               debug_header, rs->sr_err, SAFESTR(rs->sr_text, "<None>"));
00633 
00634        if ( !so->so_tree )
00635               return;
00636 
00637        /* RFC 2891: If critical then send the entries iff they were
00638         * succesfully sorted.  If non-critical send all entries
00639         * whether they were sorted or not.
00640         */
00641        if ( (op->o_ctrlflag[sss_cid] != SLAP_CONTROL_CRITICAL) ||
00642                (rs->sr_err == LDAP_SUCCESS) )
00643        {
00644               if ( so->so_vlv > SLAP_CONTROL_IGNORED ) {
00645                      send_list( op, rs, so );
00646               } else {
00647                      /* Get the first node to send */
00648                      Avlnode *start_node = tavl_end(so->so_tree, TAVL_DIR_LEFT);
00649                      so->so_tree = start_node;
00650 
00651                      if ( so->so_paged <= SLAP_CONTROL_IGNORED ) {
00652                             /* Not paged result search.  Send all entries.
00653                              * Set the page size to the number of entries
00654                              * so that send_page() will send all entries.
00655                              */
00656                             so->so_page_size = so->so_nentries;
00657                      }
00658 
00659                      send_page( op, rs, so );
00660               }
00661        }
00662 }
00663 
00664 static void send_result(
00665        Operation            *op,
00666        SlapReply            *rs,
00667        sort_op                     *so)
00668 {
00669        LDAPControl *ctrls[3];
00670        int rc, i = 0;
00671 
00672        rc = pack_sss_response_control( op, rs, ctrls );
00673        if ( rc == LDAP_SUCCESS ) {
00674               i++;
00675               rc = -1;
00676               if ( so->so_paged > SLAP_CONTROL_IGNORED ) {
00677                      rc = pack_pagedresult_response_control( op, rs, so, ctrls+1 );
00678               } else if ( so->so_vlv > SLAP_CONTROL_IGNORED ) {
00679                      rc = pack_vlv_response_control( op, rs, so, ctrls+1 );
00680               }
00681               if ( rc == LDAP_SUCCESS )
00682                      i++;
00683        }
00684        ctrls[i] = NULL;
00685 
00686        if ( ctrls[0] != NULL )
00687               slap_add_ctrls( op, rs, ctrls );
00688        send_ldap_result( op, rs );
00689 
00690        if ( so->so_tree == NULL ) {
00691               /* Search finished, so clean up */
00692               free_sort_op( op->o_conn, so );
00693        }
00694 }
00695 
00696 static int sssvlv_op_response(
00697        Operation     *op,
00698        SlapReply     *rs )
00699 {
00700        sort_ctrl *sc = op->o_controls[sss_cid];
00701        sort_op *so = op->o_callback->sc_private;
00702 
00703        if ( rs->sr_type == REP_SEARCH ) {
00704               int i;
00705               size_t len;
00706               sort_node *sn, *sn2;
00707               struct berval *bv;
00708               char *ptr;
00709 
00710               len = sizeof(sort_node) + sc->sc_nkeys * sizeof(struct berval) +
00711                      rs->sr_entry->e_nname.bv_len + 1;
00712               sn = op->o_tmpalloc( len, op->o_tmpmemctx );
00713               sn->sn_vals = (struct berval *)(sn+1);
00714 
00715               /* Build tmp list of key values */
00716               for ( i=0; i<sc->sc_nkeys; i++ ) {
00717                      Attribute *a = attr_find( rs->sr_entry->e_attrs,
00718                             sc->sc_keys[i].sk_ad );
00719                      if ( a ) {
00720                             if ( a->a_numvals > 1 ) {
00721                                    bv = select_value( a, &sc->sc_keys[i] );
00722                             } else {
00723                                    bv = a->a_nvals;
00724                             }
00725                             sn->sn_vals[i] = *bv;
00726                             len += bv->bv_len + 1;
00727                      } else {
00728                             BER_BVZERO( &sn->sn_vals[i] );
00729                      }
00730               }
00731 
00732               /* Now dup into regular memory */
00733               sn2 = ch_malloc( len );
00734               sn2->sn_vals = (struct berval *)(sn2+1);
00735               AC_MEMCPY( sn2->sn_vals, sn->sn_vals,
00736                             sc->sc_nkeys * sizeof(struct berval));
00737 
00738               ptr = (char *)(sn2->sn_vals + sc->sc_nkeys);
00739               sn2->sn_dn.bv_val = ptr;
00740               sn2->sn_dn.bv_len = rs->sr_entry->e_nname.bv_len;
00741               AC_MEMCPY( ptr, rs->sr_entry->e_nname.bv_val,
00742                      rs->sr_entry->e_nname.bv_len );
00743               ptr += rs->sr_entry->e_nname.bv_len;
00744               *ptr++ = '\0';
00745               for ( i=0; i<sc->sc_nkeys; i++ ) {
00746                      if ( !BER_BVISNULL( &sn2->sn_vals[i] )) {
00747                             AC_MEMCPY(ptr, sn2->sn_vals[i].bv_val, sn2->sn_vals[i].bv_len);
00748                             sn2->sn_vals[i].bv_val = ptr;
00749                             ptr += sn2->sn_vals[i].bv_len;
00750                             *ptr++ = '\0';
00751                      }
00752               }
00753               op->o_tmpfree( sn, op->o_tmpmemctx );
00754               sn = sn2;
00755               sn->sn_conn = op->o_conn->c_conn_idx;
00756               sn->sn_session = find_session_by_so( so->so_info->svi_max_percon, op->o_conn->c_conn_idx, so );
00757 
00758               /* Insert into the AVL tree */
00759               tavl_insert(&(so->so_tree), sn, node_insert, avl_dup_error);
00760 
00761               so->so_nentries++;
00762 
00763               /* Collected the keys so that they can be sorted.  Thus, stop
00764                * the entry from propagating.
00765                */
00766               rs->sr_err = LDAP_SUCCESS;
00767        }
00768        else if ( rs->sr_type == REP_RESULT ) {
00769               /* Remove serversort response callback.
00770                * We don't want the entries that we are about to send to be
00771                * processed by serversort response again.
00772                */
00773               if ( op->o_callback->sc_response == sssvlv_op_response ) {
00774                      op->o_callback = op->o_callback->sc_next;
00775               }
00776 
00777               send_entry( op, rs, so );
00778               send_result( op, rs, so );
00779        }
00780 
00781        return rs->sr_err;
00782 }
00783 
00784 static int sssvlv_op_search(
00785        Operation            *op,
00786        SlapReply            *rs)
00787 {
00788        slap_overinst               *on                  = (slap_overinst *)op->o_bd->bd_info;
00789        sssvlv_info                        *si                  = on->on_bi.bi_private;
00790        int                                       rc                   = SLAP_CB_CONTINUE;
00791        int    ok;
00792        sort_op *so = NULL, so2;
00793        sort_ctrl *sc;
00794        PagedResultsState *ps;
00795        vlv_ctrl *vc;
00796        int sess_id;
00797 
00798        if ( op->o_ctrlflag[sss_cid] <= SLAP_CONTROL_IGNORED ) {
00799               if ( op->o_ctrlflag[vlv_cid] > SLAP_CONTROL_IGNORED ) {
00800                      LDAPControl *ctrls[2];
00801                      so2.so_vcontext = 0;
00802                      so2.so_vlv_target = 0;
00803                      so2.so_nentries = 0;
00804                      so2.so_vlv_rc = LDAP_VLV_SSS_MISSING;
00805                      so2.so_vlv = op->o_ctrlflag[vlv_cid];
00806                      rc = pack_vlv_response_control( op, rs, &so2, ctrls );
00807                      if ( rc == LDAP_SUCCESS ) {
00808                             ctrls[1] = NULL;
00809                             slap_add_ctrls( op, rs, ctrls );
00810                      }
00811                      rs->sr_err = LDAP_VLV_ERROR;
00812                      rs->sr_text = "Sort control is required with VLV";
00813                      goto leave;
00814               }
00815               /* Not server side sort so just continue */
00816               return SLAP_CB_CONTINUE;
00817        }
00818 
00819        Debug(LDAP_DEBUG_TRACE,
00820               "==> sssvlv_search: <%s> %s, control flag: %d\n",
00821               op->o_req_dn.bv_val, op->ors_filterstr.bv_val,
00822               op->o_ctrlflag[sss_cid]);
00823 
00824        sc = op->o_controls[sss_cid];
00825        if ( sc->sc_nkeys > si->svi_max_keys ) {
00826               rs->sr_text = "Too many sort keys";
00827               rs->sr_err = LDAP_UNWILLING_TO_PERFORM;
00828               goto leave;
00829        }
00830 
00831        ps = ( op->o_pagedresults > SLAP_CONTROL_IGNORED ) ?
00832               (PagedResultsState*)(op->o_pagedresults_state) : NULL;
00833        vc = op->o_ctrlflag[vlv_cid] > SLAP_CONTROL_IGNORED ?
00834               op->o_controls[vlv_cid] : NULL;
00835 
00836        if ( ps && vc ) {
00837               rs->sr_text = "VLV incompatible with PagedResults";
00838               rs->sr_err = LDAP_UNWILLING_TO_PERFORM;
00839               goto leave;
00840        }
00841 
00842        ok = 1;
00843        ldap_pvt_thread_mutex_lock( &sort_conns_mutex );
00844        /* Is there already a sort running on this conn? */
00845        sess_id = find_session_by_context( si->svi_max_percon, op->o_conn->c_conn_idx, vc ? vc->vc_context : NO_VC_CONTEXT, ps ? ps->ps_cookie : NO_PS_COOKIE );
00846        if ( sess_id >= 0 ) {
00847               so = sort_conns[op->o_conn->c_conn_idx][sess_id];
00848               /* Is it a continuation of a VLV search? */
00849               if ( !vc || so->so_vlv <= SLAP_CONTROL_IGNORED ||
00850                      vc->vc_context != so->so_vcontext ) {
00851                      /* Is it a continuation of a paged search? */
00852                      if ( !ps || so->so_paged <= SLAP_CONTROL_IGNORED ||
00853                             op->o_conn->c_pagedresults_state.ps_cookie != ps->ps_cookie ) {
00854                             ok = 0;
00855                      } else if ( !ps->ps_size ) {
00856                      /* Abandoning current request */
00857                             ok = 0;
00858                             so->so_nentries = 0;
00859                             rs->sr_err = LDAP_SUCCESS;
00860                      }
00861               }
00862               if (( vc && so->so_paged > SLAP_CONTROL_IGNORED ) ||
00863                      ( ps && so->so_vlv > SLAP_CONTROL_IGNORED )) {
00864                      /* changed from paged to vlv or vice versa, abandon */
00865                      ok = 0;
00866                      so->so_nentries = 0;
00867                      rs->sr_err = LDAP_UNWILLING_TO_PERFORM;
00868               }
00869        /* Are there too many running overall? */
00870        } else if ( si->svi_num >= si->svi_max ) {
00871               ok = 0;
00872        } else if ( ( sess_id = find_next_session(si->svi_max_percon, op->o_conn->c_conn_idx ) ) < 0 ) {
00873               ok = 0;
00874        } else {
00875               /* OK, this connection now has a sort running */
00876               si->svi_num++;
00877               sort_conns[op->o_conn->c_conn_idx][sess_id] = &so2;
00878               sort_conns[op->o_conn->c_conn_idx][sess_id]->so_session = sess_id;
00879        }
00880        ldap_pvt_thread_mutex_unlock( &sort_conns_mutex );
00881        if ( ok ) {
00882               /* If we're a global overlay, this check got bypassed */
00883               if ( !op->ors_limit && limits_check( op, rs ))
00884                      return rs->sr_err;
00885               /* are we continuing a VLV search? */
00886               if ( so && vc && vc->vc_context ) {
00887                      so->so_ctrl = sc;
00888                      send_list( op, rs, so );
00889                      send_result( op, rs, so );
00890                      rc = LDAP_SUCCESS;
00891               /* are we continuing a paged search? */
00892               } else if ( so && ps && ps->ps_cookie ) {
00893                      so->so_ctrl = sc;
00894                      send_page( op, rs, so );
00895                      send_result( op, rs, so );
00896                      rc = LDAP_SUCCESS;
00897               } else {
00898                      slap_callback *cb = op->o_tmpalloc( sizeof(slap_callback),
00899                             op->o_tmpmemctx );
00900                      /* Install serversort response callback to handle a new search */
00901                      if ( ps || vc ) {
00902                             so = ch_calloc( 1, sizeof(sort_op));
00903                      } else {
00904                             so = op->o_tmpcalloc( 1, sizeof(sort_op), op->o_tmpmemctx );
00905                      }
00906                      sort_conns[op->o_conn->c_conn_idx][sess_id] = so;
00907 
00908                      cb->sc_cleanup              = NULL;
00909                      cb->sc_response             = sssvlv_op_response;
00910                      cb->sc_next                 = op->o_callback;
00911                      cb->sc_private              = so;
00912 
00913                      so->so_tree = NULL;
00914                      so->so_ctrl = sc;
00915                      so->so_info = si;
00916                      if ( ps ) {
00917                             so->so_paged = op->o_pagedresults;
00918                             so->so_page_size = ps->ps_size;
00919                             op->o_pagedresults = SLAP_CONTROL_IGNORED;
00920                      } else {
00921                             so->so_paged = 0;
00922                             so->so_page_size = 0;
00923                             if ( vc ) {
00924                                    so->so_vlv = op->o_ctrlflag[vlv_cid];
00925                                    so->so_vlv_target = 0;
00926                                    so->so_vlv_rc = 0;
00927                             } else {
00928                                    so->so_vlv = SLAP_CONTROL_NONE;
00929                             }
00930                      }
00931                      so->so_session = sess_id;
00932                      so->so_vlv = op->o_ctrlflag[vlv_cid];
00933                      so->so_vcontext = (unsigned long)so;
00934                      so->so_nentries = 0;
00935 
00936                      op->o_callback              = cb;
00937               }
00938        } else {
00939               if ( so && !so->so_nentries ) {
00940                      free_sort_op( op->o_conn, so );
00941               } else {
00942                      rs->sr_text = "Other sort requests already in progress";
00943                      rs->sr_err = LDAP_BUSY;
00944               }
00945 leave:
00946               rc = rs->sr_err;
00947               send_ldap_result( op, rs );
00948        }
00949 
00950        return rc;
00951 }
00952 
00953 static int get_ordering_rule(
00954        AttributeDescription *ad,
00955        struct berval               *matchrule,
00956        SlapReply                          *rs,
00957        MatchingRule                **ordering )
00958 {
00959        MatchingRule* mr;
00960 
00961        if ( matchrule && matchrule->bv_val ) {
00962               mr = mr_find( matchrule->bv_val );
00963               if ( mr == NULL ) {
00964                      rs->sr_err = LDAP_INAPPROPRIATE_MATCHING;
00965                      rs->sr_text = "serverSort control: No ordering rule";
00966                      Debug(LDAP_DEBUG_TRACE, "%s: no ordering rule function for %s\n",
00967                             debug_header, matchrule->bv_val, 0);
00968               }
00969        }
00970        else {
00971               mr = ad->ad_type->sat_ordering;
00972               if ( mr == NULL ) {
00973                      rs->sr_err = LDAP_INAPPROPRIATE_MATCHING;
00974                      rs->sr_text = "serverSort control: No ordering rule";
00975                      Debug(LDAP_DEBUG_TRACE,
00976                             "%s: no ordering rule specified and no default ordering rule for attribute %s\n",
00977                             debug_header, ad->ad_cname.bv_val, 0);
00978               }
00979        }
00980 
00981        *ordering = mr;
00982        return rs->sr_err;
00983 }
00984 
00985 static int count_key(BerElement *ber)
00986 {
00987        char *end;
00988        ber_len_t len;
00989        ber_tag_t tag;
00990        int count = 0;
00991 
00992        /* Server Side Sort Control is a SEQUENCE of SEQUENCE */
00993        for ( tag = ber_first_element( ber, &len, &end );
00994                 tag == LBER_SEQUENCE;
00995                 tag = ber_next_element( ber, &len, end ))
00996        {
00997               tag = ber_skip_tag( ber, &len );
00998               ber_skip_data( ber, len );
00999               ++count;
01000        }
01001        ber_rewind( ber );
01002 
01003        return count;
01004 }
01005 
01006 static int build_key(
01007        BerElement           *ber,
01008        SlapReply            *rs,
01009        sort_key                    *key )
01010 {
01011        struct berval attr;
01012        struct berval matchrule = BER_BVNULL;
01013        ber_int_t reverse = 0;
01014        ber_tag_t tag;
01015        ber_len_t len;
01016        MatchingRule *ordering = NULL;
01017        AttributeDescription *ad = NULL;
01018        const char *text;
01019 
01020        if (( tag = ber_scanf( ber, "{" )) == LBER_ERROR ) {
01021               rs->sr_text = "serverSort control: decoding error";
01022               rs->sr_err = LDAP_PROTOCOL_ERROR;
01023               return rs->sr_err;
01024        }
01025 
01026        if (( tag = ber_scanf( ber, "m", &attr )) == LBER_ERROR ) {
01027               rs->sr_text = "serverSort control: attribute decoding error";
01028               rs->sr_err = LDAP_PROTOCOL_ERROR;
01029               return rs->sr_err;
01030        }
01031 
01032        tag = ber_peek_tag( ber, &len );
01033        if ( tag == LDAP_MATCHRULE_IDENTIFIER ) {
01034               if (( tag = ber_scanf( ber, "m", &matchrule )) == LBER_ERROR ) {
01035                      rs->sr_text = "serverSort control: matchrule decoding error";
01036                      rs->sr_err = LDAP_PROTOCOL_ERROR;
01037                      return rs->sr_err;
01038               }
01039               tag = ber_peek_tag( ber, &len );
01040        }
01041 
01042        if ( tag == LDAP_REVERSEORDER_IDENTIFIER ) {
01043               if (( tag = ber_scanf( ber, "b", &reverse )) == LBER_ERROR ) {
01044                      rs->sr_text = "serverSort control: reverse decoding error";
01045                      rs->sr_err = LDAP_PROTOCOL_ERROR;
01046                      return rs->sr_err;
01047               }
01048        }
01049 
01050        if (( tag = ber_scanf( ber, "}" )) == LBER_ERROR ) {
01051               rs->sr_text = "serverSort control: decoding error";
01052               rs->sr_err = LDAP_PROTOCOL_ERROR;
01053               return rs->sr_err;
01054        }
01055 
01056        if ( slap_bv2ad( &attr, &ad, &text ) != LDAP_SUCCESS ) {
01057               rs->sr_text =
01058                      "serverSort control: Unrecognized attribute type in sort key";
01059               Debug(LDAP_DEBUG_TRACE,
01060                      "%s: Unrecognized attribute type in sort key: %s\n",
01061                      debug_header, SAFESTR(attr.bv_val, "<None>"), 0);
01062               rs->sr_err = LDAP_NO_SUCH_ATTRIBUTE;
01063               return rs->sr_err;
01064        }
01065 
01066        /* get_ordering_rule will set sr_err and sr_text */
01067        get_ordering_rule( ad, &matchrule, rs, &ordering );
01068        if ( rs->sr_err != LDAP_SUCCESS ) {
01069               return rs->sr_err;
01070        }
01071 
01072        key->sk_ad = ad;
01073        key->sk_ordering = ordering;
01074        key->sk_direction = reverse ? -1 : 1;
01075 
01076        return rs->sr_err;
01077 }
01078 
01079 static int sss_parseCtrl(
01080        Operation            *op,
01081        SlapReply            *rs,
01082        LDAPControl          *ctrl )
01083 {
01084        BerElementBuffer     berbuf;
01085        BerElement                  *ber;
01086        ber_tag_t            tag;
01087        ber_len_t            len;
01088        int                                i;
01089        sort_ctrl     *sc;
01090 
01091        rs->sr_err = LDAP_PROTOCOL_ERROR;
01092 
01093        if ( op->o_ctrlflag[sss_cid] > SLAP_CONTROL_IGNORED ) {
01094               rs->sr_text = "sorted results control specified multiple times";
01095        } else if ( BER_BVISNULL( &ctrl->ldctl_value ) ) {
01096               rs->sr_text = "sorted results control value is absent";
01097        } else if ( BER_BVISEMPTY( &ctrl->ldctl_value ) ) {
01098               rs->sr_text = "sorted results control value is empty";
01099        } else {
01100               rs->sr_err = LDAP_SUCCESS;
01101        }
01102        if ( rs->sr_err != LDAP_SUCCESS )
01103               return rs->sr_err;
01104 
01105        op->o_ctrlflag[sss_cid] = ctrl->ldctl_iscritical ?
01106               SLAP_CONTROL_CRITICAL : SLAP_CONTROL_NONCRITICAL;
01107 
01108        ber = (BerElement *)&berbuf;
01109        ber_init2( ber, &ctrl->ldctl_value, 0 );
01110        i = count_key( ber );
01111 
01112        sc = op->o_tmpalloc( sizeof(sort_ctrl) +
01113               (i-1) * sizeof(sort_key), op->o_tmpmemctx );
01114        sc->sc_nkeys = i;
01115        op->o_controls[sss_cid] = sc;
01116 
01117        /* peel off initial sequence */
01118        ber_scanf( ber, "{" );
01119 
01120        i = 0;
01121        do {
01122               if ( build_key( ber, rs, &sc->sc_keys[i] ) != LDAP_SUCCESS )
01123                      break;
01124               i++;
01125               tag = ber_peek_tag( ber, &len );
01126        } while ( tag != LBER_DEFAULT );
01127 
01128        return rs->sr_err;
01129 }
01130 
01131 static int vlv_parseCtrl(
01132        Operation            *op,
01133        SlapReply            *rs,
01134        LDAPControl          *ctrl )
01135 {
01136        BerElementBuffer     berbuf;
01137        BerElement                  *ber;
01138        ber_tag_t            tag;
01139        ber_len_t            len;
01140        vlv_ctrl      *vc, vc2;
01141 
01142        rs->sr_err = LDAP_PROTOCOL_ERROR;
01143        rs->sr_text = NULL;
01144 
01145        if ( op->o_ctrlflag[vlv_cid] > SLAP_CONTROL_IGNORED ) {
01146               rs->sr_text = "vlv control specified multiple times";
01147        } else if ( BER_BVISNULL( &ctrl->ldctl_value ) ) {
01148               rs->sr_text = "vlv control value is absent";
01149        } else if ( BER_BVISEMPTY( &ctrl->ldctl_value ) ) {
01150               rs->sr_text = "vlv control value is empty";
01151        }
01152        if ( rs->sr_text != NULL )
01153               return rs->sr_err;
01154 
01155        op->o_ctrlflag[vlv_cid] = ctrl->ldctl_iscritical ?
01156               SLAP_CONTROL_CRITICAL : SLAP_CONTROL_NONCRITICAL;
01157 
01158        ber = (BerElement *)&berbuf;
01159        ber_init2( ber, &ctrl->ldctl_value, 0 );
01160 
01161        rs->sr_err = LDAP_PROTOCOL_ERROR;
01162 
01163        tag = ber_scanf( ber, "{ii", &vc2.vc_before, &vc2.vc_after );
01164        if ( tag == LBER_ERROR ) {
01165               return rs->sr_err;
01166        }
01167 
01168        tag = ber_peek_tag( ber, &len );
01169        if ( tag == LDAP_VLVBYINDEX_IDENTIFIER ) {
01170               tag = ber_scanf( ber, "{ii}", &vc2.vc_offset, &vc2.vc_count );
01171               if ( tag == LBER_ERROR )
01172                      return rs->sr_err;
01173               BER_BVZERO( &vc2.vc_value );
01174        } else if ( tag == LDAP_VLVBYVALUE_IDENTIFIER ) {
01175               tag = ber_scanf( ber, "m", &vc2.vc_value );
01176               if ( tag == LBER_ERROR || BER_BVISNULL( &vc2.vc_value ))
01177                      return rs->sr_err;
01178        } else {
01179               return rs->sr_err;
01180        }
01181        tag = ber_peek_tag( ber, &len );
01182        if ( tag == LDAP_VLVCONTEXT_IDENTIFIER ) {
01183               struct berval bv;
01184               tag = ber_scanf( ber, "m", &bv );
01185               if ( tag == LBER_ERROR || bv.bv_len != sizeof(vc2.vc_context))
01186                      return rs->sr_err;
01187               AC_MEMCPY( &vc2.vc_context, bv.bv_val, bv.bv_len );
01188        } else {
01189               vc2.vc_context = 0;
01190        }
01191 
01192        vc = op->o_tmpalloc( sizeof(vlv_ctrl), op->o_tmpmemctx );
01193        *vc = vc2;
01194        op->o_controls[vlv_cid] = vc;
01195        rs->sr_err = LDAP_SUCCESS;
01196 
01197        return rs->sr_err;
01198 }
01199 
01200 static int sssvlv_connection_destroy( BackendDB *be, Connection *conn )
01201 {
01202        slap_overinst *on           = (slap_overinst *)be->bd_info;
01203        sssvlv_info *si = on->on_bi.bi_private;
01204 
01205        if ( sort_conns[conn->c_conn_idx] ) {
01206               free_sort_ops( conn, sort_conns[conn->c_conn_idx], si->svi_max_percon );
01207        }
01208 
01209        return LDAP_SUCCESS;
01210 }
01211 
01212 static int sssvlv_db_open(
01213        BackendDB            *be,
01214        ConfigReply          *cr )
01215 {
01216        slap_overinst *on = (slap_overinst *)be->bd_info;
01217        sssvlv_info *si = on->on_bi.bi_private;
01218        int rc;
01219        int conn_index;
01220 
01221        /* If not set, default to 1/2 of available threads */
01222        if ( !si->svi_max )
01223               si->svi_max = connection_pool_max / 2;
01224 
01225        if ( dtblsize && !sort_conns ) {
01226               ldap_pvt_thread_mutex_init( &sort_conns_mutex );
01227               /* accommodate for c_conn_idx == -1 */
01228               sort_conns = ch_calloc( dtblsize + 1, sizeof(sort_op **) );
01229               for ( conn_index = 0 ; conn_index < dtblsize + 1 ; conn_index++ ) {
01230                      sort_conns[conn_index] = ch_calloc( si->svi_max_percon, sizeof(sort_op *) );
01231               }
01232               sort_conns++;
01233        }
01234 
01235        rc = overlay_register_control( be, LDAP_CONTROL_SORTREQUEST );
01236        if ( rc == LDAP_SUCCESS )
01237               rc = overlay_register_control( be, LDAP_CONTROL_VLVREQUEST );
01238        return rc;
01239 }
01240 
01241 static ConfigTable sssvlv_cfg[] = {
01242        { "sssvlv-max", "num",
01243               2, 2, 0, ARG_INT|ARG_OFFSET,
01244                      (void *)offsetof(sssvlv_info, svi_max),
01245               "( OLcfgOvAt:21.1 NAME 'olcSssVlvMax' "
01246                      "DESC 'Maximum number of concurrent Sort requests' "
01247                      "SYNTAX OMsInteger SINGLE-VALUE )", NULL, NULL },
01248        { "sssvlv-maxkeys", "num",
01249               2, 2, 0, ARG_INT|ARG_OFFSET,
01250                      (void *)offsetof(sssvlv_info, svi_max_keys),
01251               "( OLcfgOvAt:21.2 NAME 'olcSssVlvMaxKeys' "
01252                      "DESC 'Maximum number of Keys in a Sort request' "
01253                      "SYNTAX OMsInteger SINGLE-VALUE )", NULL, NULL },
01254        { "sssvlv-maxpercon", "num",
01255               2, 2, 0, ARG_INT|ARG_OFFSET,
01256                      (void *)offsetof(sssvlv_info, svi_max_percon),
01257               "( OLcfgOvAt:21.3 NAME 'olcSssVlvMaxPerConn' "
01258                      "DESC 'Maximum number of concurrent paged search requests per connection' "
01259                      "SYNTAX OMsInteger SINGLE-VALUE )", NULL, NULL },
01260        { NULL, NULL, 0, 0, 0, ARG_IGNORED }
01261 };
01262 
01263 static ConfigOCs sssvlv_ocs[] = {
01264        { "( OLcfgOvOc:21.1 "
01265               "NAME 'olcSssVlvConfig' "
01266               "DESC 'SSS VLV configuration' "
01267               "SUP olcOverlayConfig "
01268               "MAY ( olcSssVlvMax $ olcSssVlvMaxKeys ) )",
01269               Cft_Overlay, sssvlv_cfg, NULL, NULL },
01270        { NULL, 0, NULL }
01271 };
01272 
01273 static int sssvlv_db_init(
01274        BackendDB            *be,
01275        ConfigReply          *cr)
01276 {
01277        slap_overinst *on = (slap_overinst *)be->bd_info;
01278        sssvlv_info *si;
01279 
01280        if ( ov_count == 0 ) {
01281               int rc;
01282 
01283               rc = register_supported_control2( LDAP_CONTROL_SORTREQUEST,
01284                      SLAP_CTRL_SEARCH,
01285                      NULL,
01286                      sss_parseCtrl,
01287                      1 /* replace */,
01288                      &sss_cid );
01289               if ( rc != LDAP_SUCCESS ) {
01290                      Debug( LDAP_DEBUG_ANY, "Failed to register Sort Request control '%s' (%d)\n",
01291                             LDAP_CONTROL_SORTREQUEST, rc, 0 );
01292                      return rc;
01293               }
01294 
01295               rc = register_supported_control2( LDAP_CONTROL_VLVREQUEST,
01296                      SLAP_CTRL_SEARCH,
01297                      NULL,
01298                      vlv_parseCtrl,
01299                      1 /* replace */,
01300                      &vlv_cid );
01301               if ( rc != LDAP_SUCCESS ) {
01302                      Debug( LDAP_DEBUG_ANY, "Failed to register VLV Request control '%s' (%d)\n",
01303                             LDAP_CONTROL_VLVREQUEST, rc, 0 );
01304 #ifdef SLAP_CONFIG_DELETE
01305                      overlay_unregister_control( be, LDAP_CONTROL_SORTREQUEST );
01306                      unregister_supported_control( LDAP_CONTROL_SORTREQUEST );
01307 #endif /* SLAP_CONFIG_DELETE */
01308                      return rc;
01309               }
01310        }
01311        
01312        si = (sssvlv_info *)ch_malloc(sizeof(sssvlv_info));
01313        on->on_bi.bi_private = si;
01314 
01315        si->svi_max = 0;
01316        si->svi_num = 0;
01317        si->svi_max_keys = SSSVLV_DEFAULT_MAX_KEYS;
01318        si->svi_max_percon = SSSVLV_DEFAULT_MAX_REQUEST_PER_CONN;
01319 
01320        ov_count++;
01321 
01322        return LDAP_SUCCESS;
01323 }
01324 
01325 static int sssvlv_db_destroy(
01326        BackendDB            *be,
01327        ConfigReply          *cr )
01328 {
01329        slap_overinst *on = (slap_overinst *)be->bd_info;
01330        sssvlv_info *si = (sssvlv_info *)on->on_bi.bi_private;
01331        int conn_index;
01332 
01333        ov_count--;
01334        if ( !ov_count && sort_conns) {
01335               sort_conns--;
01336               for ( conn_index = 0 ; conn_index < dtblsize + 1 ; conn_index++ ) {
01337                      ch_free(sort_conns[conn_index]);
01338               }
01339               ch_free(sort_conns);
01340               ldap_pvt_thread_mutex_destroy( &sort_conns_mutex );
01341        }
01342 
01343 #ifdef SLAP_CONFIG_DELETE
01344        overlay_unregister_control( be, LDAP_CONTROL_SORTREQUEST );
01345        overlay_unregister_control( be, LDAP_CONTROL_VLVREQUEST );
01346        if ( ov_count == 0 ) {
01347               unregister_supported_control( LDAP_CONTROL_SORTREQUEST );
01348               unregister_supported_control( LDAP_CONTROL_VLVREQUEST );
01349        }
01350 #endif /* SLAP_CONFIG_DELETE */
01351 
01352        if ( si ) {
01353               ch_free( si );
01354               on->on_bi.bi_private = NULL;
01355        }
01356        return LDAP_SUCCESS;
01357 }
01358 
01359 static slap_overinst sssvlv;
01360 
01361 int sssvlv_initialize()
01362 {
01363        int rc;
01364 
01365        sssvlv.on_bi.bi_type                      = "sssvlv";
01366        sssvlv.on_bi.bi_db_init                          = sssvlv_db_init;
01367        sssvlv.on_bi.bi_db_destroy                = sssvlv_db_destroy;
01368        sssvlv.on_bi.bi_db_open                          = sssvlv_db_open;
01369        sssvlv.on_bi.bi_connection_destroy = sssvlv_connection_destroy;
01370        sssvlv.on_bi.bi_op_search                 = sssvlv_op_search;
01371 
01372        sssvlv.on_bi.bi_cf_ocs = sssvlv_ocs;
01373 
01374        rc = config_register_schema( sssvlv_cfg, sssvlv_ocs );
01375        if ( rc )
01376               return rc;
01377 
01378        rc = overlay_register( &sssvlv );
01379        if ( rc != LDAP_SUCCESS ) {
01380               Debug( LDAP_DEBUG_ANY, "Failed to register server side sort overlay\n", 0, 0, 0 );
01381        }
01382 
01383        return rc;
01384 }
01385 
01386 #if SLAPD_OVER_SSSVLV == SLAPD_MOD_DYNAMIC
01387 int init_module( int argc, char *argv[])
01388 {
01389        return sssvlv_initialize();
01390 }
01391 #endif
01392 
01393 #endif /* SLAPD_OVER_SSSVLV */