Add Simple Paged Results

For more details, see the design doc at http://directory.fedoraproject.org/wiki/Simple_Paged_Results_Design

17 files changed, 1410 insertions, 708 deletions

diff --git a/ldap/servers/slapd/back-ldbm/filterindex.c b/ldap/servers/slapd/back-ldbm/filterindex.c
index 413d01f4..d41829f8 100644
--- a/ldap/servers/slapd/back-ldbm/filterindex.c
+++ b/ldap/servers/slapd/back-ldbm/filterindex.c
@@ -782,16 +782,31 @@ list_candidates(
                 (idl_length(idl) <= FILTER_TEST_THRESHOLD))
                 break;
         } else {
+            Slapi_Operation *operation;
+            struct ldbminfo *li;
+            slapi_pblock_get( pb, SLAPI_OPERATION, &operation );
+            slapi_pblock_get( pb, SLAPI_PLUGIN_PRIVATE, &li );
+
             idl = idl_union( be, idl, tmp );
             idl_free( tmp );
             idl_free( tmp2 );
             /* stop if we're already committed to an exhaustive
              * search. :(
              */
+            /* PAGED RESULTS: if not Directory Manager, we strictly limit
+             *                the idlist size by the lookthrough limit.
+             */
+            if (operation->o_flags & OP_FLAG_PAGED_RESULTS) {
+                int nids = IDL_NIDS(idl);
+                int lookthroughlimits = compute_lookthrough_limit( pb, li );
+                if ( lookthroughlimits > 0 && nids > lookthroughlimits ) {
+                    idl_free( idl );
+                    idl = idl_allids( be );
+                }
+            }
             if (idl_is_allids(idl))
                 break;
         }
-
     }
 
     LDAPDebug( LDAP_DEBUG_TRACE, "<= list_candidates %lu\n",
diff --git a/ldap/servers/slapd/back-ldbm/init.c b/ldap/servers/slapd/back-ldbm/init.c
index f6c00aa8..c32f9825 100644
--- a/ldap/servers/slapd/back-ldbm/init.c
+++ b/ldap/servers/slapd/back-ldbm/init.c
@@ -182,6 +182,8 @@ ldbm_back_init( Slapi_PBlock *pb )
 	    (void *) ldbm_back_next_search_entry_ext );
 	rc |= slapi_pblock_set( pb, SLAPI_PLUGIN_DB_ENTRY_RELEASE_FN,
 	    (void *) ldbm_back_entry_release );
+	rc |= slapi_pblock_set( pb, SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN,
+	    (void *) ldbm_back_search_results_release );
 	rc |= slapi_pblock_set( pb, SLAPI_PLUGIN_DB_COMPARE_FN, 
 	    (void *) ldbm_back_compare );
 	rc |= slapi_pblock_set( pb, SLAPI_PLUGIN_DB_MODIFY_FN, 
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_search.c b/ldap/servers/slapd/back-ldbm/ldbm_search.c
index 600a9c47..7d91d47a 100644
--- a/ldap/servers/slapd/back-ldbm/ldbm_search.c
+++ b/ldap/servers/slapd/back-ldbm/ldbm_search.c
@@ -66,7 +66,7 @@ static int can_skip_filter_test( Slapi_PBlock *pb, struct slapi_filter *f,
 
 #define ISLEGACY(be) (be?(be->be_instance_info?(((ldbm_instance *)be->be_instance_info)->inst_li?(((ldbm_instance *)be->be_instance_info)->inst_li->li_legacy_errcode):0):0):0)
 
-static int
+int
 compute_lookthrough_limit( Slapi_PBlock *pb, struct ldbminfo *li )
 {
     Slapi_Connection    *conn = NULL;
@@ -122,6 +122,8 @@ int ldbm_back_search_cleanup(Slapi_PBlock *pb, struct ldbminfo *li, sort_spec_th
         back_search_result_set *sr = NULL;
         slapi_pblock_get( pb, SLAPI_SEARCH_RESULT_SET, &sr );
         if ( (NULL != sr) && (function_result != 0) ) {
+            /* in case paged results, clean up the conn */
+            pagedresults_set_search_result(pb->pb_conn, NULL);
             delete_search_result_set(&sr);
         }
     }
@@ -214,6 +216,8 @@ ldbm_back_search( Slapi_PBlock *pb )
                 /* Badly formed SORT control */
                 return ldbm_back_search_cleanup(pb, li, sort_control, LDAP_PROTOCOL_ERROR, "Sort Control", SLAPI_FAIL_GENERAL, &basesdn, NULL);
             }
+            /* set this operation includes the server side sorting */
+            operation->o_flags |= OP_FLAG_SERVER_SIDE_SORTING;
         }
         is_sorting_critical = is_sorting_critical_orig;
 
@@ -303,7 +307,7 @@ ldbm_back_search( Slapi_PBlock *pb )
             vlv_make_response_control(pb, &vlv_response);
             if (sort)
             {
-                make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
+                sort_make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
             }
             if (ISLEGACY(be))
             {
@@ -327,7 +331,7 @@ ldbm_back_search( Slapi_PBlock *pb )
                     vlv_response.result = LDAP_UNWILLING_TO_PERFORM;
                     vlv_make_response_control(pb, &vlv_response);
                 }
-                make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
+                sort_make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
                 return ldbm_back_search_cleanup(pb, li, sort_control,
                             LDAP_UNAVAILABLE_CRITICAL_EXTENSION, ctrlstr,
                             SLAPI_FAIL_GENERAL, &basesdn, &vlv_request_control);
@@ -341,7 +345,7 @@ ldbm_back_search( Slapi_PBlock *pb )
                 }
                 if (sort)
                 {
-                    make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
+                    sort_make_sort_response_control(pb, LDAP_UNWILLING_TO_PERFORM, NULL);
                 }
                 sort = 0;
                 virtual_list_view = 0;
@@ -385,39 +389,58 @@ ldbm_back_search( Slapi_PBlock *pb )
         int vlv_rc;
         /*
          * Build a list of IDs for this entry and scope
-        */    
-        if ((NULL != controls) && (sort)) {
-            switch (vlv_search_build_candidate_list(pb, &basesdn, &vlv_rc, sort_control, (vlv ? &vlv_request_control : NULL), &candidates, &vlv_response_control)) {
+         */    
+        if ((NULL != controls) && (sort) && (vlv)) {
+            /* This candidate list is for vlv, no need for sort only. */
+            switch (vlv_search_build_candidate_list(pb, &basesdn, &vlv_rc,
+                                          sort_control,
+                                          (vlv ? &vlv_request_control : NULL),
+                                          &candidates, &vlv_response_control)) {
             case VLV_ACCESS_DENIED:
-                return ldbm_back_search_cleanup(pb, li, sort_control, vlv_rc, "VLV Control", SLAPI_FAIL_GENERAL, &basesdn, &vlv_request_control);
-                
+                return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                vlv_rc, "VLV Control",
+                                                SLAPI_FAIL_GENERAL, &basesdn,
+                                                &vlv_request_control);
             case VLV_BLD_LIST_FAILED:
-                return ldbm_back_search_cleanup(pb, li, sort_control, vlv_response_control.result, NULL, SLAPI_FAIL_GENERAL, &basesdn, &vlv_request_control);
+                return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                vlv_response_control.result,
+                                                NULL, SLAPI_FAIL_GENERAL,
+                                                &basesdn, &vlv_request_control);
                 
             case LDAP_SUCCESS:
                 /* Log to the access log the particulars of this sort request */
-                /* Log message looks like this: SORT <key list useful for input to ldapsearch> <#candidates> | <unsortable> */
+                /* Log message looks like this: SORT <key list useful for input
+                 * to ldapsearch> <#candidates> | <unsortable> */
                 sort_log_access(pb,sort_control,NULL);
                 /* Since a pre-computed index was found for the VLV Search then
-                * the candidate list now contains exactly what should be returned.
-                * There's no need to sort or trim the candidate list.
-                *
-                * However, the client will be expecting a Sort Response control
-                */
-                if (LDAP_SUCCESS != make_sort_response_control( pb, 0, NULL ) )
+                 * the candidate list now contains exactly what should be 
+                 * returned.
+                 * There's no need to sort or trim the candidate list.
+                 *
+                 * However, the client will be expecting a Sort Response control
+                 */
+                if (LDAP_SUCCESS !=
+                    sort_make_sort_response_control( pb, 0, NULL ) )
                 {
-                    return ldbm_back_search_cleanup(pb, li, sort_control, LDAP_OPERATIONS_ERROR, "Sort Response Control", SLAPI_FAIL_GENERAL, &basesdn, &vlv_request_control);
+                    return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                    LDAP_OPERATIONS_ERROR,
+                                                    "Sort Response Control",
+                                                    SLAPI_FAIL_GENERAL,
+                                                    &basesdn,
+                                                    &vlv_request_control);
                 }
             }
         }
-        if(candidates==NULL)
+        if (candidates == NULL)
         {
             int rc = build_candidate_list(pb, be, e, base, scope,
-                    &lookup_returned_allids, &candidates);
+                                          &lookup_returned_allids, &candidates);
             if (rc)
             {
                 /* Error result sent by build_candidate_list */
-                return ldbm_back_search_cleanup(pb, li, sort_control, -1, NULL, rc, &basesdn, &vlv_request_control);
+                return ldbm_back_search_cleanup(pb, li, sort_control, -1,
+                                                NULL, rc, &basesdn,
+                                                &vlv_request_control);
             }
             /*
              * If we're sorting then we must check what administrative
@@ -434,7 +457,7 @@ ldbm_back_search( Slapi_PBlock *pb )
                 /* 
                  * (tlimit==-1) means no time limit
                  */
-                time_up = ( tlimit==-1 ? -1 : optime + tlimit);
+                time_up = (tlimit==-1 ? -1 : optime + tlimit);
 
                 lookthrough_limit = compute_lookthrough_limit( pb, li );
             }
@@ -445,19 +468,23 @@ ldbm_back_search( Slapi_PBlock *pb )
              */
             if (virtual_list_view && (NULL != candidates))
             {
-                int r= 0;
-                IDList *idl= NULL;
-                Slapi_Filter *filter= NULL;
+                int r = 0;
+                IDList *idl = NULL;
+                Slapi_Filter *filter = NULL;
                 slapi_pblock_get( pb, SLAPI_SEARCH_FILTER, &filter );
-                r= vlv_filter_candidates(be, pb, candidates, &basesdn, scope, filter, &idl, lookthrough_limit, time_up);
-                if(r==0)
+                r = vlv_filter_candidates(be, pb, candidates, &basesdn,
+                                          scope, filter, &idl,
+                                          lookthrough_limit, time_up);
+                if(r == 0)
                 {
                     idl_free(candidates);
                     candidates= idl;
                 }
                 else
                 {
-                    return ldbm_back_search_cleanup(pb, li, sort_control, r, NULL, -1, &basesdn, &vlv_request_control);
+                    return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                    r, NULL, -1, &basesdn,
+                                                    &vlv_request_control);
                 }
             }
             /*
@@ -480,39 +507,50 @@ ldbm_back_search( Slapi_PBlock *pb )
 
                 /* Don't log internal operations */
                 if (!operation_is_flag_set(operation, OP_FLAG_INTERNAL)) {
-                    /* Log to the access log the particulars of this sort request */
-                    /* Log message looks like this: SORT <key list useful for input to ldapsearch> <#candidates> | <unsortable> */
+                    /* Log to the access log the particulars of this
+                     * sort request */
+                    /* Log message looks like this: SORT <key list useful for 
+                     * input to ldapsearch> <#candidates> | <unsortable> */
                     sort_log_access(pb,sort_control,candidates);
                 }
-                sort_return_value = sort_candidates( be, lookthrough_limit, time_up, pb, candidates, sort_control, &sort_error_type );
+                sort_return_value = sort_candidates( be, lookthrough_limit,
+                                                     time_up, pb, candidates,
+                                                     sort_control,
+                                                     &sort_error_type );
                 /* Fix for bugid # 394184, SD, 20 Jul 00 */
-                /* replace the hard coded return value by the appropriate LDAP error code */
+                /* replace the hard coded return value by the appropriate 
+                 * LDAP error code */
                 switch (sort_return_value) {
                    case LDAP_SUCCESS:  /* Everything OK */
                     vlv_response_control.result= LDAP_SUCCESS;
                     break;
                 case LDAP_PROTOCOL_ERROR:  /* A protocol error */
-                    return ldbm_back_search_cleanup(pb, li, sort_control, LDAP_PROTOCOL_ERROR, "Sort Control", -1, &basesdn, &vlv_request_control);
+                    return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                    LDAP_PROTOCOL_ERROR,
+                                                    "Sort Control", -1,
+                                                    &basesdn,
+                                                    &vlv_request_control);
                 case LDAP_UNWILLING_TO_PERFORM:  /* Too hard */
                 case LDAP_OPERATIONS_ERROR:  /* Operation error */
                 case LDAP_TIMELIMIT_EXCEEDED:  /* Timeout */
                     vlv_response_control.result= LDAP_TIMELIMIT_EXCEEDED;
                     break;
                 case LDAP_ADMINLIMIT_EXCEEDED:  /* Admin limit exceeded */
-                    vlv_response_control.result= LDAP_ADMINLIMIT_EXCEEDED;
+                    vlv_response_control.result = LDAP_ADMINLIMIT_EXCEEDED;
                     break;
                 case LDAP_OTHER:  /* Abandoned */
-                    abandoned= 1; /* So that we don't return a result code */
-                    is_sorting_critical= 1;  /* In order to have the results discarded */
+                    abandoned = 1; /* So that we don't return a result code */
+                    is_sorting_critical = 1;  /* In order to have the results
+                                                 discarded */
                     break;
                 default:  /* Should never get here */
                     break;
                 }
                 /* End fix for bug # 394184 */
                 /*
-                 * If the sort control was marked as critical, and there was an error in sorting,
-                 * don't return any entries, and return unavailableCriticalExtension in the 
-                 * searchResultDone message.
+                 * If the sort control was marked as critical, and there was
+                 * an error in sorting, don't return any entries, and return 
+                 * unavailableCriticalExtension in the searchResultDone message.
                  */
                 /* Fix for bugid #394184, SD, 05 Jul 00 */
                 /* we were not actually returning unavailableCriticalExtension;
@@ -525,10 +563,15 @@ ldbm_back_search( Slapi_PBlock *pb )
                     tmp_desc = "Sort Response Control";
                 }
                 /* end Fix for bugid #394184 */
-                /* Generate the control returned to the client to indicate sort result */
-                if (LDAP_SUCCESS != make_sort_response_control( pb, sort_return_value, sort_error_type ) )
+                /* Generate the control returned to the client to indicate 
+                 * sort result */
+                if (LDAP_SUCCESS != sort_make_sort_response_control( pb,
+                                          sort_return_value, sort_error_type ) )
                 {
-                    return ldbm_back_search_cleanup(pb, li, sort_control, (abandoned?-1:LDAP_PROTOCOL_ERROR), "Sort Response Control", -1, &basesdn, &vlv_request_control);
+                    return ldbm_back_search_cleanup(pb, li, sort_control,
+                                             (abandoned?-1:LDAP_PROTOCOL_ERROR),
+                                             "Sort Response Control", -1,
+                                             &basesdn, &vlv_request_control);
                 }
             }
             /*
@@ -540,30 +583,39 @@ ldbm_back_search( Slapi_PBlock *pb )
                 if (NULL != candidates && candidates->b_nids>0)
                 {
                     IDList *idl= NULL;
-                    vlv_response_control.result= vlv_trim_candidates(be, candidates, sort_control, &vlv_request_control, &idl, &vlv_response_control);
+                    vlv_response_control.result =
+                        vlv_trim_candidates(be, candidates, sort_control,
+                        &vlv_request_control, &idl, &vlv_response_control);
                     if(vlv_response_control.result==0)
                     {
                         idl_free(candidates);
-                        candidates= idl;
+                        candidates = idl;
                     }
                     else
                     {
-                        return ldbm_back_search_cleanup(pb, li, sort_control, vlv_response_control.result, NULL, -1, &basesdn, &vlv_request_control);
+                        return ldbm_back_search_cleanup(pb, li, sort_control,
+                                                    vlv_response_control.result,
+                                                    NULL, -1, &basesdn,
+                                                    &vlv_request_control);
                     }
                 }
                 else
                 {
-                    vlv_response_control.targetPosition= 0;
-                    vlv_response_control.contentCount= 0;
-                    vlv_response_control.result= LDAP_SUCCESS;
+                    vlv_response_control.targetPosition = 0;
+                    vlv_response_control.contentCount = 0;
+                    vlv_response_control.result = LDAP_SUCCESS;
                 }
             }
         }
         if (virtual_list_view)
         {
-            if(LDAP_SUCCESS != vlv_make_response_control( pb, &vlv_response_control ))
+            if(LDAP_SUCCESS != 
+                         vlv_make_response_control( pb, &vlv_response_control ))
             {
-                return ldbm_back_search_cleanup(pb, li, sort_control, (abandoned?-1:LDAP_PROTOCOL_ERROR), "VLV Response Control", -1, &basesdn, &vlv_request_control);
+                return ldbm_back_search_cleanup(pb, li, sort_control,
+                                             (abandoned?-1:LDAP_PROTOCOL_ERROR),
+                                             "VLV Response Control", -1,
+                                             &basesdn, &vlv_request_control);
             }
             /* Log the VLV operation */
             vlv_print_access_log(pb,&vlv_request_control,&vlv_response_control);
@@ -608,7 +660,7 @@ ldbm_back_search( Slapi_PBlock *pb )
     /* check to see if we can skip the filter test */
     if ( li->li_filter_bypass && NULL != candidates && !virtual_list_view
                 && !lookup_returned_allids ) {
-        Slapi_Filter *filter= NULL;
+        Slapi_Filter *filter = NULL;
 
         slapi_pblock_get( pb, SLAPI_SEARCH_FILTER, &filter );
         if ( can_skip_filter_test( pb, filter, scope, candidates)) {
@@ -618,7 +670,9 @@ ldbm_back_search( Slapi_PBlock *pb )
 
     /* Fix for bugid #394184, SD, 05 Jul 00 */
     /* tmp_err == -1: no error */
-    return ldbm_back_search_cleanup(pb, li, sort_control, tmp_err, tmp_desc, (tmp_err  == -1 ? 0 : -1), &basesdn, &vlv_request_control);
+    return ldbm_back_search_cleanup(pb, li, sort_control, tmp_err, tmp_desc,
+                                    (tmp_err  == -1 ? 0 : -1), &basesdn,
+                                    &vlv_request_control);
     /* end Fix for bugid #394184 */
 }
 
@@ -1082,6 +1136,8 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
         /* check for abandon */
         if ( slapi_op_abandoned( pb ))
         {
+            /* in case paged results, clean up the conn */
+            pagedresults_set_search_result(pb->pb_conn, NULL);
             delete_search_result_set( &sr );
             if ( use_extension ) {
                 slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, NULL );
@@ -1096,6 +1152,8 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
         if ( tlimit != -1 && curtime > stoptime )
         {
             slapi_send_ldap_result( pb, LDAP_TIMELIMIT_EXCEEDED, NULL, NULL, nentries, urls );
+            /* in case paged results, clean up the conn */
+            pagedresults_set_search_result(pb->pb_conn, NULL);
             delete_search_result_set( &sr );
             if ( use_extension ) {
                 slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, NULL );
@@ -1109,6 +1167,8 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
         if ( llimit != -1 && sr->sr_lookthroughcount >= llimit )
         {
             slapi_send_ldap_result( pb, LDAP_ADMINLIMIT_EXCEEDED, NULL, NULL, nentries, urls );
+            /* in case paged results, clean up the conn */
+            pagedresults_set_search_result(pb->pb_conn, NULL);
             delete_search_result_set( &sr );
             if ( use_extension ) {
                 slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, NULL );
@@ -1123,6 +1183,9 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
         if ( id == NOID )
         {
             /* No more entries */
+            /* destroy back_search_result_set */
+            /* in case paged results, clean up the conn */
+            pagedresults_set_search_result(pb->pb_conn, NULL);
             delete_search_result_set( &sr );
             if ( use_extension ) {
                 slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, NULL );
@@ -1261,6 +1324,8 @@ ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension )
                  {
                      if ( --slimit < 0 ) {
                          cache_return( &inst->inst_cache, &e );
+                         /* in case paged results, clean up the conn */
+                         pagedresults_set_search_result(pb->pb_conn, NULL);
                          delete_search_result_set( &sr );
                          slapi_send_ldap_result( pb, LDAP_SIZELIMIT_EXCEEDED, NULL, NULL, nentries, urls );
                          rc = SLAPI_FAIL_GENERAL;
@@ -1348,6 +1413,11 @@ delete_search_result_set( back_search_result_set **sr )
     slapi_ch_free( (void**)sr );
 }
 
+void
+ldbm_back_search_results_release( void **sr )
+{
+    delete_search_result_set( (back_search_result_set **)sr );
+}
 
 int
 ldbm_back_entry_release( Slapi_PBlock *pb, void *backend_info_ptr ) {
diff --git a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
index 341e64cb..30d607ee 100644
--- a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
+++ b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h
@@ -459,6 +459,7 @@ int ldbm_back_next_search_entry( Slapi_PBlock *pb );
 int ldbm_back_next_search_entry_ext( Slapi_PBlock *pb, int use_extension );
 int ldbm_back_db_test( Slapi_PBlock *pb ); 
 int ldbm_back_entry_release( Slapi_PBlock *pb, void *backend_info_ptr );
+void ldbm_back_search_results_release( void **search_results );
 int ldbm_back_init( Slapi_PBlock *pb ); 
 
 /*
@@ -534,13 +535,15 @@ int bedse_add_index_entry(int argc, char **argv);
 #endif
 
 /*
- * search.c
+ * ldbm_search.c
  */
 Slapi_Filter* create_onelevel_filter(Slapi_Filter* filter, const struct backentry *e, int managedsait, Slapi_Filter** fid2kids, Slapi_Filter** focref, Slapi_Filter** fand, Slapi_Filter** forr);
 Slapi_Filter* create_subtree_filter(Slapi_Filter* filter, int managedsait, Slapi_Filter** focref, Slapi_Filter** forr);
 IDList* subtree_candidates(Slapi_PBlock *pb, backend *be, const char *base, const struct backentry *e, Slapi_Filter *filter, int managedsait, int *allids_before_scopingp, int *err);
 void search_set_tune(struct ldbminfo *li,int val);
 int search_get_tune(struct ldbminfo *li);
+int compute_lookthrough_limit( Slapi_PBlock *pb, struct ldbminfo *li );
+
 
 /*
  * matchrule.c
diff --git a/ldap/servers/slapd/back-ldbm/sort.c b/ldap/servers/slapd/back-ldbm/sort.c
index 055a5c86..2694338e 100644
--- a/ldap/servers/slapd/back-ldbm/sort.c
+++ b/ldap/servers/slapd/back-ldbm/sort.c
@@ -230,81 +230,6 @@ int sort_candidates(backend *be,int lookthrough_limit,time_t time_up, Slapi_PBlo
 }
 /* End  fix for bug # 394184 */
 
-/*  Fix for bug # 394184, SD, 20 Jul 00 */
-/* fix and cleanup (switch(code) {} removed) */
-/* arg 'code' has now the correct sortResult value */
-int
-make_sort_response_control ( Slapi_PBlock *pb, int code, char *error_type) {
-
-	LDAPControl	new_ctrl = {0};
-    BerElement		*ber= NULL;    
-	struct berval	*bvp = NULL;
-	int rc = -1;
-	ber_int_t control_code = code;
-
-	/*
-	     SortResult ::= SEQUENCE {
-        sortResult  ENUMERATED {
-            success                   (0), -- results are sorted
-            operationsError           (1), -- server internal failure
-            timeLimitExceeded         (3), -- timelimit reached before
-                                           -- sorting was completed
-            strongAuthRequired        (8), -- refused to return sorted
-                                           -- results via insecure
-                                           -- protocol
-            adminLimitExceeded       (11), -- too many matching entries
-                                           -- for the server to sort
-            noSuchAttribute          (16), -- unrecognized attribute
-                                           -- type in sort key
-            inappropriateMatching    (18), -- unrecognized or inappro-
-                                           -- priate matching rule in
-                                           -- sort key
-            insufficientAccessRights (50), -- refused to return sorted
-                                           -- results to this client
-            busy                     (51), -- too busy to process
-            unwillingToPerform       (53), -- unable to sort
-            other                    (80)
-            },
-      attributeType [0] AttributeType OPTIONAL }
-
-	 */
-	
-    if ( ( ber = ber_alloc()) == NULL ) {
-		return -1;
-    }
-
-    if (( rc = ber_printf( ber, "{e", control_code )) != -1 ) {
-		if ( rc != -1 && NULL != error_type ) {
-			rc = ber_printf( ber, "s", error_type );
-		}
-		if ( rc != -1 ) {
-			rc = ber_printf( ber, "}" );
-		}
-    }
-    if ( rc != -1 ) {
-		rc = ber_flatten( ber, &bvp );
-    }
-    
-	ber_free( ber, 1 );
-
-    if ( rc == -1 ) {
-		return rc;
-    }
-        
-	new_ctrl.ldctl_oid = LDAP_CONTROL_SORTRESPONSE;
-	new_ctrl.ldctl_value = *bvp;
-	new_ctrl.ldctl_iscritical = 1;         
-
-	if ( slapi_pblock_set( pb, SLAPI_ADD_RESCONTROL, &new_ctrl ) != 0 ) {
-            ber_bvfree(bvp);
-            return( -1 );
-	}
-
-        ber_bvfree(bvp);
-	return( LDAP_SUCCESS );
-}
-/* End fix for bug #394184 */
-
 static int term_tag(ber_tag_t tag)
 {
 	return ( (LBER_END_OF_SEQORSET == tag) || (LBER_ERROR == tag) );
@@ -804,7 +729,7 @@ static int compare_entries_sv(ID *id_a, ID *id_b, sort_spec *s,baggage_carrier *
  * -5: Admin limit exceeded   now is: LDAP_ADMINLIMIT_EXCEEDED
  * -6: Abandoned              now is: LDAP_OTHER
  */
-static int sort_nazi(baggage_carrier *bc)
+static int sort_check(baggage_carrier *bc)
 {
 	time_t curtime = 0;
 	/* check for abandon */
@@ -956,7 +881,7 @@ recurse:
             swap(loguy, higuy);
 
 			/* Check admin and time limits here on the sort */
-			if ( LDAP_SUCCESS != (return_value = sort_nazi(bc)) )
+			if ( LDAP_SUCCESS != (return_value = sort_check(bc)) )
 			{
 				return return_value;
 			}
diff --git a/ldap/servers/slapd/backend.c b/ldap/servers/slapd/backend.c
index e6083a66..1bded05e 100644
--- a/ldap/servers/slapd/backend.c
+++ b/ldap/servers/slapd/backend.c
@@ -393,6 +393,9 @@ slapi_be_getentrypoint(Slapi_Backend *be, int entrypoint, void **ret_fnptr, Slap
 	case SLAPI_PLUGIN_DB_ENTRY_RELEASE_FN:
 		*ret_fnptr = (void*)be->be_entry_release;
 		break;
+	case SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN:
+		*ret_fnptr = (void*)be->be_search_results_release;
+		break;
 	case SLAPI_PLUGIN_DB_SIZE_FN:
 		*ret_fnptr = (void*)be->be_dbsize;
 		break;
@@ -498,6 +501,9 @@ slapi_be_setentrypoint(Slapi_Backend *be, int entrypoint, void *ret_fnptr, Slapi
 	case SLAPI_PLUGIN_DB_ENTRY_RELEASE_FN:
         be->be_entry_release=(IFP) ret_fnptr;
         break;
+	case SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN:
+        be->be_search_results_release=(IFP) ret_fnptr;
+        break;
 	case SLAPI_PLUGIN_DB_SIZE_FN:
         be->be_dbsize=(IFP) ret_fnptr;
         break;
diff --git a/ldap/servers/slapd/connection.c b/ldap/servers/slapd/connection.c
index 045e527c..874766b8 100644
--- a/ldap/servers/slapd/connection.c
+++ b/ldap/servers/slapd/connection.c
@@ -130,8 +130,8 @@ void
 connection_cleanup(Connection *conn)
 {
 	bind_credentials_clear( conn, PR_FALSE /* do not lock conn */,
-			PR_TRUE /* clear external creds. */ );
-        slapi_ch_free((void**)&conn->c_authtype);
+							PR_TRUE /* clear external creds. */ );
+	slapi_ch_free((void**)&conn->c_authtype);
 
 	/* Call the plugin extension destructors */
 	factory_destroy_extension(connection_type,conn,NULL/*Parent*/,&(conn->c_extension));
@@ -197,6 +197,15 @@ connection_cleanup(Connection *conn)
 	/* remove any SASL I/O from the connection */
 	sasl_io_cleanup(conn);
 	sasl_dispose((sasl_conn_t**)&conn->c_sasl_conn);
+	/* PAGED_RESULTS */
+	if (conn->c_search_result_set) {
+		conn->c_current_be->be_search_results_release(&(conn->c_search_result_set));
+		conn->c_search_result_set = NULL;
+	}
+	conn->c_current_be = NULL;
+	conn->c_search_result_count = 0;
+	conn->c_timelimit = 0;
+	/* PAGED_RESULTS ENDS */
 
 	/* free the connection socket buffer */
 	connection_free_private_buffer(conn);
@@ -1946,11 +1955,17 @@ void connection_enter_leave_turbo(Connection *conn, int *new_turbo_flag)
 	PR_Lock(conn->c_mutex);
 	/* We can already be in turbo mode, or not */
 	current_mode = conn->c_private->turbo_flag;
-	if(conn->c_private->operation_rate == 0) {
-		/* The connection is ranked by the passed activities. If some other connection have more activity, 
-		   increase rank by one. The highest rank is least activity, good candidates to move out of turbo mode. 
-		   However, if no activity on all the connections, then every connection gets 0 rank, so none move out. 
-		   No bother to do so much calcuation, short-cut to non-turbo mode if no activities in passed interval */
+	if (conn->c_search_result_set) {
+		/* PAGED_RESULTS does not need turbo mode */
+		new_mode = 0;
+	} else if (conn->c_private->operation_rate == 0) {
+		/* The connection is ranked by the passed activities. If some other
+		 * connection have more activity, increase rank by one. The highest 
+		 * rank is least activity, good candidates to move out of turbo mode. 
+		 * However, if no activity on all the connections, then every 
+		 * connection gets 0 rank, so none move out. 
+		 * No bother to do so much calcuation, short-cut to non-turbo mode 
+		 * if no activities in passed interval */
 		new_mode = 0;
 	} else {
 	  double activet = 0.0;
@@ -1964,7 +1979,7 @@ void connection_enter_leave_turbo(Connection *conn, int *new_turbo_flag)
 	     one measure to reduce thread startvation.
 	   */
 	  if (connection_count > threshold_rank) {
-	  	threshold_rank -= (connection_count - threshold_rank) / 5;
+		threshold_rank -= (connection_count - threshold_rank) / 5;
 	  }
 
 	  if (current_mode) {
@@ -2065,7 +2080,7 @@ connection_threadmain()
 			PR_Unlock(conn->c_mutex);
 			if (! config_check_referral_mode()) {
 			  slapi_counter_increment(ops_initiated);
-	    		  slapi_counter_increment(g_get_global_snmp_vars()->ops_tbl.dsInOps); 
+			  slapi_counter_increment(g_get_global_snmp_vars()->ops_tbl.dsInOps); 
 			}
 		}
 		/* Once we're here we have a pb */ 
@@ -2097,7 +2112,7 @@ connection_threadmain()
 		switch (ret) {
 			case CONN_DONE:
 				/* This means that the connection was closed, so clear turbo mode */
-			/*FALLTHROUGH*/
+				/*FALLTHROUGH*/
 			case CONN_TIMEDOUT:
 				thread_turbo_flag = 0;
 				is_timedout = 1;
diff --git a/ldap/servers/slapd/control.c b/ldap/servers/slapd/control.c
index 268a48cd..aadf201b 100644
--- a/ldap/servers/slapd/control.c
+++ b/ldap/servers/slapd/control.c
@@ -112,6 +112,10 @@ init_controls( void )
 */
 	slapi_register_supported_control( LDAP_CONTROL_GET_EFFECTIVE_RIGHTS,
 		SLAPI_OPERATION_SEARCH );
+
+	/* LDAP_CONTROL_PAGEDRESULTS is shared by request and response */
+	slapi_register_supported_control( LDAP_CONTROL_PAGEDRESULTS,
+		SLAPI_OPERATION_SEARCH );
 }
 
 
@@ -124,8 +128,7 @@ slapi_register_supported_control( char *controloid, unsigned long controlops )
 	if ( controloid != NULL ) {
 		PR_RWLock_Wlock(supported_controls_lock);
 		++supported_controls_count;
-		charray_add( &supported_controls,
-		    slapi_ch_strdup( controloid ));
+		charray_add( &supported_controls, slapi_ch_strdup( controloid ));
 		supported_controls_ops = (unsigned long *)slapi_ch_realloc(
 		    (char *)supported_controls_ops,
 		    supported_controls_count * sizeof( unsigned long ));
@@ -418,10 +421,8 @@ slapi_control_present( LDAPControl **controls, char *oid, struct berval **val, i
 
 	for ( i = 0; controls[i] != NULL; i++ ) {
 		if ( strcmp( controls[i]->ldctl_oid, oid ) == 0 ) {
-			if ( val != NULL ) {
-				if (NULL != val) {
-					*val = &controls[i]->ldctl_value;
-				}
+			if (NULL != val) {
+				*val = &controls[i]->ldctl_value;
 				if (NULL != iscritical) {
 					*iscritical = (int) controls[i]->ldctl_iscritical;
 				}
@@ -502,7 +503,7 @@ add_control_ext( LDAPControl ***ctrlsp, LDAPControl *newctrl, int copy )
 {
 	int	count;
 
-        if ( *ctrlsp == NULL ) {
+	if ( *ctrlsp == NULL ) {
 		count = 0;
 	} else {
 		for ( count = 0; (*ctrlsp)[count] != NULL; ++count ) {
@@ -510,14 +511,14 @@ add_control_ext( LDAPControl ***ctrlsp, LDAPControl *newctrl, int copy )
 		}
 	}
 
-        *ctrlsp = (LDAPControl **)slapi_ch_realloc( (char *)*ctrlsp,
-                ( count + 2 ) * sizeof(LDAPControl *));
+	*ctrlsp = (LDAPControl **)slapi_ch_realloc( (char *)*ctrlsp,
+				( count + 2 ) * sizeof(LDAPControl *));
 
-        if (copy) {
-            (*ctrlsp)[ count ] = slapi_dup_control( newctrl );
-        } else {
-            (*ctrlsp)[ count ] = newctrl;
-        }
+	if (copy) {
+		(*ctrlsp)[ count ] = slapi_dup_control( newctrl );
+	} else {
+		(*ctrlsp)[ count ] = newctrl;
+	}
 	(*ctrlsp)[ ++count ] = NULL;
 }
 
diff --git a/ldap/servers/slapd/daemon.c b/ldap/servers/slapd/daemon.c
index 3e91c124..3b070e20 100644
--- a/ldap/servers/slapd/daemon.c
+++ b/ldap/servers/slapd/daemon.c
@@ -1219,6 +1219,16 @@ setup_pr_read_pds(Connection_Table *ct, PRFileDesc **n_tcps, PRFileDesc **s_tcps
 					c->c_fdi = SLAPD_INVALID_SOCKET_INDEX;
 				}
 			}
+			if (c->c_timelimit > 0) /* check timeout for PAGED RESULTS */
+			{
+				time_t ctime = current_time();
+				if (ctime > c->c_timelimit)
+				{
+					/* Exceeded the timelimit; disconnect the client */
+					disconnect_server_nomutex(c, c->c_connid, -1,
+												SLAPD_DISCONNECT_IO_TIMEOUT, 0);
+				}
+			}
 			PR_Unlock( c->c_mutex );
 		}
 		c = next;
diff --git a/ldap/servers/slapd/opshared.c b/ldap/servers/slapd/opshared.c
index 8fc24126..06ff32f6 100644
--- a/ldap/servers/slapd/opshared.c
+++ b/ldap/servers/slapd/opshared.c
@@ -45,74 +45,78 @@
 #include "slap.h"
 #include "index_subsys.h"
 
+#define PAGEDRESULTS_PAGE_END 1
+#define PAGEDRESULTS_SEARCH_END 2
+
 /* helper functions */
 static void compute_limits (Slapi_PBlock *pb);
 
 /* attributes that no clients are allowed to add or modify */
-static char *protected_attrs_all [] = {	PSEUDO_ATTR_UNHASHEDUSERPASSWORD,
-										NULL
-									  };
+static char *protected_attrs_all [] = {    PSEUDO_ATTR_UNHASHEDUSERPASSWORD,
+                                        NULL
+                                      };
 static char *pwpolicy_lock_attrs_all [] = { "passwordRetryCount",
-											"retryCountResetTime",
-											"accountUnlockTime",
-											NULL};
+                                            "retryCountResetTime",
+                                            "accountUnlockTime",
+                                            NULL};
 /* Forward declarations */
 static void compute_limits (Slapi_PBlock *pb);
 static int  send_results (Slapi_PBlock *pb, int send_result, int *nentries);
+static int  send_results_ext (Slapi_PBlock *pb, int send_result, int *nentries, int pagesize, unsigned int *pr_stat);
 static int process_entry(Slapi_PBlock *pb, Slapi_Entry *e, int send_result);
-			
+            
 int op_shared_is_allowed_attr (const char *attr_name, int replicated_op)
 {
-	int 				i;
-	slapdFrontendConfig_t *slapdFrontendConfig = getFrontendConfig();
-
-	/* check list of attributes that no client is allowed to specify */
-	for (i = 0; protected_attrs_all[i]; i ++)
-	{
-		if (strcasecmp (attr_name, protected_attrs_all[i]) == 0)
-		{
-			/* this attribute is not allowed */
-			return 0;
-		}
-	}
-
-	/* ONREPL - should allow backends to plugin here to specify 
-				attributes that are not allowed */
-
-	if (!replicated_op)
-	{
-		/*
-		 * check to see if attribute is marked as one clients can't modify
-		 */
-		struct asyntaxinfo	*asi;
-		int					no_user_mod = 0;
-
-		asi = attr_syntax_get_by_name( attr_name );
-		if ( NULL != asi &&
-				0 != ( asi->asi_flags & SLAPI_ATTR_FLAG_NOUSERMOD ))
-		{
-			/* this attribute is not allowed */
-			no_user_mod = 1;
-		}
-		attr_syntax_return( asi );
-
-		if ( no_user_mod ) {
-			return( 0 );
-		}
-	} else if (!slapdFrontendConfig->pw_is_global_policy) {
-		/* check list of password policy attributes for locking accounts */
-		for (i = 0; pwpolicy_lock_attrs_all[i]; i ++)
-		{
-			if (strcasecmp (attr_name, pwpolicy_lock_attrs_all[i]) == 0)
-			{
-				/* this attribute is not allowed */
-				return 0;
-			}
-		}
-	}
-
-	/* this attribute is ok */
-	return 1;
+    int                 i;
+    slapdFrontendConfig_t *slapdFrontendConfig = getFrontendConfig();
+
+    /* check list of attributes that no client is allowed to specify */
+    for (i = 0; protected_attrs_all[i]; i ++)
+    {
+        if (strcasecmp (attr_name, protected_attrs_all[i]) == 0)
+        {
+            /* this attribute is not allowed */
+            return 0;
+        }
+    }
+
+    /* ONREPL - should allow backends to plugin here to specify 
+                attributes that are not allowed */
+
+    if (!replicated_op)
+    {
+        /*
+         * check to see if attribute is marked as one clients can't modify
+         */
+        struct asyntaxinfo    *asi;
+        int                    no_user_mod = 0;
+
+        asi = attr_syntax_get_by_name( attr_name );
+        if ( NULL != asi &&
+                0 != ( asi->asi_flags & SLAPI_ATTR_FLAG_NOUSERMOD ))
+        {
+            /* this attribute is not allowed */
+            no_user_mod = 1;
+        }
+        attr_syntax_return( asi );
+
+        if ( no_user_mod ) {
+            return( 0 );
+        }
+    } else if (!slapdFrontendConfig->pw_is_global_policy) {
+        /* check list of password policy attributes for locking accounts */
+        for (i = 0; pwpolicy_lock_attrs_all[i]; i ++)
+        {
+            if (strcasecmp (attr_name, pwpolicy_lock_attrs_all[i]) == 0)
+            {
+                /* this attribute is not allowed */
+                return 0;
+            }
+        }
+    }
+
+    /* this attribute is ok */
+    return 1;
 }
 
 
@@ -122,95 +126,102 @@ void
 do_ps_service(Slapi_Entry *e, Slapi_Entry *eprev, ber_int_t chgtype, ber_int_t chgnum)
 {
     if (NULL == ps_service_fn) {
-	if (get_entry_point(ENTRY_POINT_PS_SERVICE, (caddr_t *)(&ps_service_fn)) < 0) {
-	    return;
-	}
+        if (get_entry_point(ENTRY_POINT_PS_SERVICE, (caddr_t *)(&ps_service_fn)) < 0) {
+            return;
+        }
     }
     (ps_service_fn)(e, eprev, chgtype, chgnum);
 }
 
 void modify_update_last_modified_attr(Slapi_PBlock *pb, Slapi_Mods *smods)
 {
-	char		buf[20];
-	struct berval	bv;
-	struct berval	*bvals[2];
-	time_t		curtime;
-	struct tm	utm;
-	Operation	*op;
-
-	LDAPDebug(LDAP_DEBUG_TRACE, "modify_update_last_modified_attr\n", 0, 0, 0);
-
-	slapi_pblock_get(pb, SLAPI_OPERATION, &op);
-
-	bvals[0] = &bv;
-	bvals[1] = NULL;
-
-	/* fill in modifiersname */
-	if (slapi_sdn_isempty(&op->o_sdn)) {
-		bv.bv_val = "";
-		bv.bv_len = strlen(bv.bv_val);
-	} else {
-		bv.bv_val = (char*)slapi_sdn_get_dn(&op->o_sdn);
-		bv.bv_len = strlen(bv.bv_val);
-	}
-
-	slapi_mods_add_modbvps(smods, LDAP_MOD_REPLACE | LDAP_MOD_BVALUES, 
-						   "modifiersname", bvals);	
-
-	/* fill in modifytimestamp */
-	curtime = current_time();
+    char        buf[20];
+    struct berval    bv;
+    struct berval    *bvals[2];
+    time_t        curtime;
+    struct tm    utm;
+    Operation    *op;
+
+    LDAPDebug(LDAP_DEBUG_TRACE, "modify_update_last_modified_attr\n", 0, 0, 0);
+
+    slapi_pblock_get(pb, SLAPI_OPERATION, &op);
+
+    bvals[0] = &bv;
+    bvals[1] = NULL;
+
+    /* fill in modifiersname */
+    if (slapi_sdn_isempty(&op->o_sdn)) {
+        bv.bv_val = "";
+        bv.bv_len = strlen(bv.bv_val);
+    } else {
+        bv.bv_val = (char*)slapi_sdn_get_dn(&op->o_sdn);
+        bv.bv_len = strlen(bv.bv_val);
+    }
+
+    slapi_mods_add_modbvps(smods, LDAP_MOD_REPLACE | LDAP_MOD_BVALUES, 
+                           "modifiersname", bvals);    
+
+    /* fill in modifytimestamp */
+    curtime = current_time();
 #ifdef _WIN32
 {
-	struct tm *pt;
-	pt = gmtime(&curtime);
-	memcpy(&utm, pt, sizeof(struct tm));
+    struct tm *pt;
+    pt = gmtime(&curtime);
+    memcpy(&utm, pt, sizeof(struct tm));
 }
 #else
-	gmtime_r(&curtime, &utm);
+    gmtime_r(&curtime, &utm);
 #endif
-	strftime(buf, sizeof(buf), "%Y%m%d%H%M%SZ", &utm);
-	bv.bv_val = buf;
-	bv.bv_len = strlen(bv.bv_val);
-	slapi_mods_add_modbvps(smods, LDAP_MOD_REPLACE | LDAP_MOD_BVALUES, 
-						   "modifytimestamp", bvals);
+    strftime(buf, sizeof(buf), "%Y%m%d%H%M%SZ", &utm);
+    bv.bv_val = buf;
+    bv.bv_len = strlen(bv.bv_val);
+    slapi_mods_add_modbvps(smods, LDAP_MOD_REPLACE | LDAP_MOD_BVALUES, 
+                           "modifytimestamp", bvals);
 }
 
 /*
- * Returns: 0	- if the operation is successful
- * 		    < 0	- if operation fails. 
+ * Returns: 0    - if the operation is successful
+ *        < 0    - if operation fails. 
  * Note that an operation is considered "failed" if a result is sent 
  * directly to the client when send_result is 0.
  */
 void
 op_shared_search (Slapi_PBlock *pb, int send_result)
 {
-  char          *base, *fstr;
-  int           scope;
-  Slapi_Backend *be = NULL;
-  Slapi_Backend *be_single = NULL;
-  Slapi_Backend *be_list[BE_LIST_SIZE];
-  Slapi_Entry   *referral_list[BE_LIST_SIZE];
-  char          ebuf[ BUFSIZ ];
-  char          attrlistbuf[ 1024 ], *attrliststr, **attrs = NULL;
-  int           rc = 0;
-  int           internal_op;
+  char            *base, *fstr;
+  int             scope;
+  Slapi_Backend   *be = NULL;
+  Slapi_Backend   *be_single = NULL;
+  Slapi_Backend   *be_list[BE_LIST_SIZE];
+  Slapi_Entry     *referral_list[BE_LIST_SIZE];
+  char            ebuf[ BUFSIZ ];
+  char            attrlistbuf[ 1024 ], *attrliststr, **attrs = NULL;
+  int             rc = 0;
+  int             internal_op;
   Slapi_DN        sdn;
   Slapi_Operation *operation;
-  Slapi_Entry   *referral = NULL;
+  Slapi_Entry     *referral = NULL;
  
-  char          errorbuf[BUFSIZ];
-  int           nentries,pnentries;
-  int           flag_search_base_found = 0;
-  int           flag_no_such_object = 0;
-  int           flag_referral = 0;
-  int           flag_psearch = 0;
-  int           err_code = LDAP_SUCCESS;
-  LDAPControl   **ctrlp;
-  struct berval *ctl_value = NULL;
-  int           iscritical = 0;
-  char          * be_name = NULL;
-  int           index = 0;
-  int		sent_result = 0;
+  char            errorbuf[BUFSIZ];
+  int             nentries,pnentries;
+  int             flag_search_base_found = 0;
+  int             flag_no_such_object = 0;
+  int             flag_referral = 0;
+  int             flag_psearch = 0;
+  int             err_code = LDAP_SUCCESS;
+  LDAPControl     **ctrlp;
+  struct berval   *ctl_value = NULL;
+  int             iscritical = 0;
+  char            *be_name = NULL;
+  int             index = 0;
+  int             sent_result = 0;
+  unsigned int    pr_stat = 0;
+
+  ber_int_t pagesize = -1;
+  int curr_search_count = 0;
+  Slapi_Backend *pr_be = NULL;
+  void *pr_search_result = NULL;
+  int pr_search_result_count = 0;
 
   be_list[0] = NULL;
   referral_list[0] = NULL;
@@ -234,7 +245,7 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
 #define SLAPD_SEARCH_FMTSTR_BASE_INT "conn=%s op=%d SRCH base=\"%s\" scope=%d "
 #define SLAPD_SEARCH_FMTSTR_REMAINDER " attrs=%s%s\n"
 
-	  PR_ASSERT(fstr);
+      PR_ASSERT(fstr);
       if ( strlen(fstr) > 1024 )
       {
           /*
@@ -349,11 +360,30 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
           }
       }
 
-	  if ( slapi_control_present (ctrlp, LDAP_CONTROL_GET_EFFECTIVE_RIGHTS,
-				&ctl_value, &iscritical) )
-	  {
-			operation->o_flags |= OP_FLAG_GET_EFFECTIVE_RIGHTS;
-	  }
+      if ( slapi_control_present (ctrlp, LDAP_CONTROL_GET_EFFECTIVE_RIGHTS,
+                                  &ctl_value, &iscritical) )
+      {
+          operation->o_flags |= OP_FLAG_GET_EFFECTIVE_RIGHTS;
+      }
+
+      if ( slapi_control_present (ctrlp, LDAP_CONTROL_PAGEDRESULTS,
+                                  &ctl_value, &iscritical) )
+      {
+          rc = pagedresults_parse_control_value(ctl_value,
+                                               &pagesize, &curr_search_count);
+          if (LDAP_SUCCESS == rc) {
+              operation->o_flags |= OP_FLAG_PAGED_RESULTS;
+              pr_be = pagedresults_get_current_be(pb->pb_conn);
+              pr_search_result = pagedresults_get_search_result(pb->pb_conn);
+              pr_search_result_count =
+                             pagedresults_get_search_result_count(pb->pb_conn);
+          } else {
+              /* parse paged-results-control failed */
+              if (iscritical) { /* return an error since it's critical */
+                  goto free_and_return;
+              }
+          }
+      }
   }
 
   if (be_name == NULL)
@@ -372,18 +402,29 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
     if (be_list[0] != NULL)
     {
       index = 0;
-      while (be_list[index] && be_list[index+1])
-        index++;
+      if (pr_be) { /* PAGED RESULT: be is found from the previous paging. */
+        /* move the index in the be_list which matches pr_be */
+        while (be_list[index] && be_list[index+1] && pr_be != be_list[index])
+          index++;
+      } else {
+        while (be_list[index] && be_list[index+1])
+          index++;
+      }
+      /* "be" is either pr_be or the last backend */
       be = be_list[index];
     }
     else
-      be = NULL;
+      be = pr_be?pr_be:NULL;
   }
   else
   {
       /* specific backend be_name was requested, use slapi_be_select_by_instance_name
        */
-      be_single = be = slapi_be_select_by_instance_name(be_name);
+      if (pr_be) {
+        be_single = be = pr_be;
+      } else {
+        be_single = be = slapi_be_select_by_instance_name(be_name);
+      }
       if (be_single)
         slapi_be_Rlock(be_single);
       be_list[0] = NULL;
@@ -454,7 +495,17 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
         slapi_pblock_get(pb, SLAPI_PLUGIN_OPRETURN, &rc);
         goto free_and_return;
     }
-  } 
+  }
+
+  /* set the timelimit to clean up the too-long-lived-paged results requests */
+  if (operation->o_flags & OP_FLAG_PAGED_RESULTS) {
+    time_t optime, time_up;
+    int tlimit;
+	slapi_pblock_get( pb, SLAPI_SEARCH_TIMELIMIT, &tlimit );
+	slapi_pblock_get( pb, SLAPI_OPINITIATED_TIME, &optime );
+	time_up = (tlimit==-1 ? -1 : optime + tlimit); /* -1: no time limit */
+    pagedresults_set_timelimit(pb->pb_conn, time_up);
+  }
 
   /* PAR: now filters have been rewritten, we can assign plugins to work on them */
   index_subsys_assign_filter_decoders(pb);
@@ -465,6 +516,7 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
   {
     const Slapi_DN * be_suffix;
     int err = 0;
+    Slapi_Backend   *next_be = NULL;
 
     if (be->be_search == NULL)
     {
@@ -489,136 +541,196 @@ op_shared_search (Slapi_PBlock *pb, int send_result)
 
     /* that's mean we only support one suffix per backend */
     be_suffix = slapi_be_getsuffix(be, 0);
-        
-    /* be_suffix null means that we are searching the default backend
-     * -> don't change the search parameters in pblock
-     */
-    if (be_suffix != NULL)
+
+    if (be_list[0] == NULL)
+    {
+      next_be = NULL;
+    }
+    else
     {
-      if ((be_name == NULL) && (scope == LDAP_SCOPE_ONELEVEL))
+      index--;
+      if (index>=0)
+        next_be = be_list[index];
+      else
+        next_be = NULL;
+    }
+        
+    if ((operation->o_flags & OP_FLAG_PAGED_RESULTS) && pr_search_result) {
+      /* PAGED RESULTS and already have the search results from the prev op */
+      slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_SET, pr_search_result );
+      rc = send_results_ext (pb, 1, &pnentries, pagesize, &pr_stat);
+
+      if (PAGEDRESULTS_SEARCH_END == pr_stat) {
+        /* no more entries to send in the backend */
+        if (NULL == next_be) {
+          /* no more entries && no more backends */
+          curr_search_count = -1;
+        } else {
+          curr_search_count = pnentries;
+        }
+      } else {
+        curr_search_count = pnentries;
+      }
+      pagedresults_set_response_control(pb, 0, pagesize, curr_search_count);
+      if (pagedresults_get_with_sort(pb->pb_conn)) {
+        sort_make_sort_response_control(pb, CONN_GET_SORT_RESULT_CODE, NULL);
+      }
+      next_be = NULL; /* to break the loop */
+    } else {
+      /* be_suffix null means that we are searching the default backend
+       * -> don't change the search parameters in pblock
+       */
+      if (be_suffix != NULL)
       {
-                /* one level searches 
-                 * - depending on the suffix of the backend we might have to
-                 *   do a one level search or a base search
-                 * - we might also have to change the search target 
-                 */
-        if (slapi_sdn_isparent(&sdn, be_suffix)
-            || (slapi_sdn_get_ndn_len(&sdn) == 0))
+        if ((be_name == NULL) && (scope == LDAP_SCOPE_ONELEVEL))
         {
-          int tmp_scope = LDAP_SCOPE_BASE;
-          slapi_pblock_set(pb, SLAPI_SEARCH_SCOPE, &tmp_scope);
-          slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
-                   (void *)slapi_sdn_get_ndn(be_suffix));
+                  /* one level searches 
+                   * - depending on the suffix of the backend we might have to
+                   *   do a one level search or a base search
+                   * - we might also have to change the search target 
+                   */
+          if (slapi_sdn_isparent(&sdn, be_suffix)
+              || (slapi_sdn_get_ndn_len(&sdn) == 0))
+          {
+            int tmp_scope = LDAP_SCOPE_BASE;
+            slapi_pblock_set(pb, SLAPI_SEARCH_SCOPE, &tmp_scope);
+            slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
+                     (void *)slapi_sdn_get_ndn(be_suffix));
+          }
+          else if (slapi_sdn_issuffix(&sdn, be_suffix))
+          {
+            int tmp_scope = LDAP_SCOPE_ONELEVEL;
+            slapi_pblock_set(pb, SLAPI_SEARCH_SCOPE, &tmp_scope);
+            slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
+                     (void *)slapi_sdn_get_ndn (&sdn));
+          }
+          else
+            goto next_be;
         }
-        else if (slapi_sdn_issuffix(&sdn, be_suffix))
+      
+        /* subtree searches :
+         * if the search was started above the backend suffix 
+         * - temporarily set the SLAPI_SEARCH_TARGET to the 
+         *   base of the node so that we don't get a NO SUCH OBJECT error
+         * - do not change the scope
+         */
+        if (scope == LDAP_SCOPE_SUBTREE)
         {
-          int tmp_scope = LDAP_SCOPE_ONELEVEL;
-          slapi_pblock_set(pb, SLAPI_SEARCH_SCOPE, &tmp_scope);
-          slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
-                   (void *)slapi_sdn_get_ndn (&sdn));
+          if (slapi_sdn_issuffix(be_suffix, &sdn))
+          {
+            slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
+                     (void *)slapi_sdn_get_ndn(be_suffix));
+          }
+          else
+              slapi_pblock_set(pb, SLAPI_SEARCH_TARGET, (void *)slapi_sdn_get_ndn(&sdn));
         }
-        else
-          goto next_be;
       }
-    
-      /* subtree searches :
-       * if the search was started above the backend suffix 
-       * - temporarily set the SLAPI_SEARCH_TARGET to the 
-       *   base of the node so that we don't get a NO SUCH OBJECT error
-       * - do not change the scope
-       */
-      if (scope == LDAP_SCOPE_SUBTREE)
+      
+      slapi_pblock_set(pb, SLAPI_BACKEND, be);
+      slapi_pblock_set(pb, SLAPI_PLUGIN, be->be_database);
+      slapi_pblock_set(pb, SLAPI_SEARCH_RESULT_SET, NULL);
+      
+      /* ONREPL - we need to be able to tell the backend not to send results directly */
+      rc = (*be->be_search)(pb);
+      switch (rc)
       {
-        if (slapi_sdn_issuffix(be_suffix, &sdn))
+      case 1:
+        /* if the backend returned LDAP_NO_SUCH_OBJECT for a SEARCH request,
+         * it will not have sent back a result - otherwise, it will have
+         * sent a result */
+        rc = SLAPI_FAIL_GENERAL;
+        slapi_pblock_get(pb, SLAPI_RESULT_CODE, &err);
+        if (err == LDAP_NO_SUCH_OBJECT)
         {
-          slapi_pblock_set(pb, SLAPI_SEARCH_TARGET,
-                   (void *)slapi_sdn_get_ndn(be_suffix));
+            /* may be the object exist somewhere else
+             * wait the end of the loop to send back this error 
+             */
+            flag_no_such_object = 1;
+            break;
+        }
+        /* err something other than LDAP_NO_SUCH_OBJECT, so the backend will
+         * have sent the result -
+         * Set a flag here so we don't return another result. */
+        sent_result = 1;
+        /* fall through */
+  
+      case -1:    /* an error occurred */            
+        slapi_pblock_get(pb, SLAPI_RESULT_CODE, &err);
+        if (err == LDAP_NO_SUCH_OBJECT)
+        {
+            /* may be the object exist somewhere else
+             * wait the end of the loop to send back this error 
+             */
+            flag_no_such_object = 1;
+            break;
         }
         else
-            slapi_pblock_set(pb, SLAPI_SEARCH_TARGET, (void *)slapi_sdn_get_ndn(&sdn));
-      }
-    }
-    
-    slapi_pblock_set(pb, SLAPI_BACKEND, be);
-    slapi_pblock_set(pb, SLAPI_PLUGIN, be->be_database);
-    slapi_pblock_set(pb, SLAPI_SEARCH_RESULT_SET, NULL);
-    
-    /* ONREPL - we need to be able to tell the backend not to send results directly */
-    rc = (*be->be_search)(pb);
-    switch (rc)
-    {
-    case 1:        /* if the backend returned LDAP_NO_SUCH_OBJECT for a SEARCH request,
-                      it will not have sent back a result - otherwise, it will have
-                      sent a result */
-      rc = SLAPI_FAIL_GENERAL;
-      slapi_pblock_get(pb, SLAPI_RESULT_CODE, &err);
-      if (err == LDAP_NO_SUCH_OBJECT)
-      {
-          /* may be the object exist somewhere else
-           * wait the end of the loop to send back this error 
-           */
-          flag_no_such_object = 1;
-          break;
-      }
-      /* err something other than LDAP_NO_SUCH_OBJECT, so the backend will have sent the result -
-         Set a flag here so we don't return another result. */
-      sent_result = 1;
-      /* fall through */
-
-    case -1:    /* an error occurred */            
-      slapi_pblock_get(pb, SLAPI_RESULT_CODE, &err);
-      if (err == LDAP_NO_SUCH_OBJECT)
-      {
-          /* may be the object exist somewhere else
-           * wait the end of the loop to send back this error 
-           */
-          flag_no_such_object = 1;
-          break;
-      }
-      else
-      {
-          /* for error other than LDAP_NO_SUCH_OBJECT
-           * the error has already been sent
-           * stop the search here
-           */
+        {
+            /* for error other than LDAP_NO_SUCH_OBJECT
+             * the error has already been sent
+             * stop the search here
+             */
+            goto free_and_return;
+        }
+  
+        /* when rc == SLAPI_FAIL_DISKFULL this case is executed */ 
+  
+      case SLAPI_FAIL_DISKFULL: 
+        operation_out_of_disk_space(); 
+        goto free_and_return; 
+                          
+      case 0:        /* search was successful and we need to send the result */
+        flag_search_base_found++;
+        rc = send_results_ext (pb, 1, &pnentries, pagesize, &pr_stat);
+  
+        /* PAGED RESULTS */
+        if (operation->o_flags & OP_FLAG_PAGED_RESULTS) {
+            void *sr = NULL;
+            int with_sort = operation->o_flags & OP_FLAG_SERVER_SIDE_SORTING;
+  
+            curr_search_count = pnentries;
+            if (PAGEDRESULTS_SEARCH_END == pr_stat) {
+              if (NULL == next_be) {
+                /* no more entries && no more backends */
+                curr_search_count = -1;
+              } else {
+                /* no more entries, but at least another backend */
+                if (pagedresults_set_current_be(pb->pb_conn, next_be) < 0) {
+                  goto free_and_return;
+                }
+              }
+            } else {
+              curr_search_count = pnentries;
+              slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_SET, &sr);
+              if (pagedresults_set_current_be(pb->pb_conn, be) < 0 ||
+                  pagedresults_set_search_result(pb->pb_conn, sr) < 0 ||
+                  pagedresults_set_search_result_count(pb->pb_conn,
+                                                   curr_search_count) < 0 ||
+                  pagedresults_set_with_sort(pb->pb_conn, with_sort) < 0) {
+                goto free_and_return;
+              }
+            }
+            pagedresults_set_response_control(pb, 0,
+                                              pagesize, curr_search_count);
+            slapi_pblock_set( pb, SLAPI_SEARCH_RESULT_SET, NULL );
+            next_be = NULL; /* to break the loop */
+        }
+  
+        /* if rc != 0 an error occurred while sending back the entries
+         * to the LDAP client
+         * LDAP error should already have been sent to the client
+         * stop the search, free and return
+         */
+        if (rc != 0)     
           goto free_and_return;
+        break;
       }
-
-      /* when rc == SLAPI_FAIL_DISKFULL this case is executed */ 
-
-    case SLAPI_FAIL_DISKFULL: 
-      operation_out_of_disk_space(); 
-      goto free_and_return; 
-                        
-    case 0:        /* search was successful and we need to send the result */
-      flag_search_base_found++;
-      rc = send_results (pb, 1, &pnentries);
-
-      /* if rc != 0 an error occurred while sending back the entries
-       * to the LDAP client
-       * LDAP error should already have been sent to the client
-       * stop the search, free and return
-       */
-      if (rc != 0)     
-        goto free_and_return;
-      break;
     }
             
     nentries += pnentries;
 
-    next_be:
-    if (be_list[0] == NULL)
-    {
-      be = NULL;
-    }
-    else
-    {
-      index--;
-      if (index>=0)
-        be = be_list[index];
-      else
-        be = NULL;
-    }
+next_be:
+    be = next_be; /* this be won't be used for PAGED_RESULTS */
   }
 
   /* if referrals were sent back by the mapping tree
@@ -731,14 +843,14 @@ process_entry(Slapi_PBlock *pb, Slapi_Entry *e, int send_result)
 {
     int managedsait;
     Slapi_Attr *a=NULL;
-	int numValues=0, i;
+    int numValues=0, i;
 
     if (!send_result) 
-	{
-		/* server requested that we don't send results to the client,
-		   for instance, in case of a persistent search
-		 */
-		return 1;
+    {
+        /* server requested that we don't send results to the client,
+           for instance, in case of a persistent search
+         */
+        return 1;
     }
     
    /* ONREPL - check if the entry should be referred (because of the copyingFrom) */
@@ -749,48 +861,48 @@ process_entry(Slapi_PBlock *pb, Slapi_Entry *e, int send_result)
      * the referrals are just squirreled away and sent with the
      * final result.  For v3, the referrals are sent in separate LDAP messages.
      */
-	slapi_pblock_get(pb, SLAPI_MANAGEDSAIT, &managedsait);
+    slapi_pblock_get(pb, SLAPI_MANAGEDSAIT, &managedsait);
     if (!managedsait && slapi_entry_attr_find(e, "ref", &a)== 0)
-	{
-		/* to fix 522189: when rootDSE, don't interpret attribute ref as a referral entry  */
-
-		if ( slapi_is_rootdse(slapi_entry_get_dn_const(e)) )
-			return 0;	/* more to do for this entry, e.g., send it back to the client */
-
-		/* end fix */
-		slapi_attr_get_numvalues(a, &numValues );
-		if (numValues == 0) 
-		{
-			char ebuf[ BUFSIZ ];
-			LDAPDebug(LDAP_DEBUG_ANY, "null ref in (%s)\n",
-					  escape_string(slapi_entry_get_dn_const(e), ebuf), 0, 0);
-		}
-		else 
-		{
-			Slapi_Value *val=NULL;
-			struct berval **refscopy=NULL;
-			struct berval **urls, **tmpUrls=NULL;
-			tmpUrls=(struct berval **) slapi_ch_malloc((numValues + 1) * sizeof(struct berval*));
-			for ( i = slapi_attr_first_value(a, &val); i != -1;
-				 i = slapi_attr_next_value(a, i, &val)) {
-				tmpUrls[i]=(struct berval*)slapi_value_get_berval(val);
-			}
-			tmpUrls[numValues]=NULL;
-			refscopy = ref_adjust(pb, tmpUrls, slapi_entry_get_sdn_const(e), 1);
-			slapi_pblock_get(pb, SLAPI_SEARCH_REFERRALS, &urls);
-			send_ldap_referral(pb, e, refscopy, &urls);
-			slapi_pblock_set(pb, SLAPI_SEARCH_REFERRALS, urls);
-			if (NULL != refscopy) 
-			{
-				ber_bvecfree(refscopy);
-				refscopy = NULL;
-			}
-			if( NULL != tmpUrls) {
-				slapi_ch_free( (void **)&tmpUrls );
-			}
-		}
-
-		return 1;		/* done with this entry */
+    {
+        /* to fix 522189: when rootDSE, don't interpret attribute ref as a referral entry  */
+
+        if ( slapi_is_rootdse(slapi_entry_get_dn_const(e)) )
+            return 0;    /* more to do for this entry, e.g., send it back to the client */
+
+        /* end fix */
+        slapi_attr_get_numvalues(a, &numValues );
+        if (numValues == 0) 
+        {
+            char ebuf[ BUFSIZ ];
+            LDAPDebug(LDAP_DEBUG_ANY, "null ref in (%s)\n",
+                      escape_string(slapi_entry_get_dn_const(e), ebuf), 0, 0);
+        }
+        else 
+        {
+            Slapi_Value *val=NULL;
+            struct berval **refscopy=NULL;
+            struct berval **urls, **tmpUrls=NULL;
+            tmpUrls=(struct berval **) slapi_ch_malloc((numValues + 1) * sizeof(struct berval*));
+            for ( i = slapi_attr_first_value(a, &val); i != -1;
+                 i = slapi_attr_next_value(a, i, &val)) {
+                tmpUrls[i]=(struct berval*)slapi_value_get_berval(val);
+            }
+            tmpUrls[numValues]=NULL;
+            refscopy = ref_adjust(pb, tmpUrls, slapi_entry_get_sdn_const(e), 1);
+            slapi_pblock_get(pb, SLAPI_SEARCH_REFERRALS, &urls);
+            send_ldap_referral(pb, e, refscopy, &urls);
+            slapi_pblock_set(pb, SLAPI_SEARCH_REFERRALS, urls);
+            if (NULL != refscopy) 
+            {
+                ber_bvecfree(refscopy);
+                refscopy = NULL;
+            }
+            if( NULL != tmpUrls) {
+                slapi_ch_free( (void **)&tmpUrls );
+            }
+        }
+
+        return 1;        /* done with this entry */
     } 
 
     return 0;
@@ -812,7 +924,7 @@ iterate_with_lookahead(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int
     Slapi_Entry *next_e;
     void *next_backend_info_ptr;
     char **attrs = NULL;    
-	int send_result_status = 0;
+    int send_result_status = 0;
 
     slapi_pblock_get(pb, SLAPI_SEARCH_ATTRS, &attrs);
     slapi_pblock_get(pb, SLAPI_SEARCH_ATTRSONLY, &attrsonly);
@@ -820,24 +932,24 @@ iterate_with_lookahead(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int
     /* setup for the loop */
     rc = be->be_next_search_entry_ext(pb, 1);
     if (rc < 0) 
-	{
-		/*
-		 * Some exceptional condition occurred.  Results
-		 * have been sent, so we're finished.
-		 */
-		if (rc == SLAPI_FAIL_DISKFULL) 
-		{
-			operation_out_of_disk_space();
-		}
-		return -1;
+    {
+        /*
+         * Some exceptional condition occurred.  Results
+         * have been sent, so we're finished.
+         */
+        if (rc == SLAPI_FAIL_DISKFULL) 
+        {
+            operation_out_of_disk_space();
+        }
+        return -1;
     } 
-		
+        
     slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY, &next_e);
     slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, &next_backend_info_ptr);
     if (NULL == next_e) 
-	{
-		/* no entries */
-		done = 1;
+    {
+        /* no entries */
+        done = 1;
     }
 
     backend_info_ptr = NULL;
@@ -845,98 +957,98 @@ iterate_with_lookahead(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int
     /* Done setting up the loop, now here it comes */
     
     while (!done) 
-	{
-		/* Allow the backend to free the entry we just finished using */
-		/* It is ok to call this when backend_info_ptr is NULL */
-		be->be_entry_release(pb, backend_info_ptr);
-		e = next_e;
-		backend_info_ptr = next_backend_info_ptr;
-
-		rc = be->be_next_search_entry_ext(pb, 1);
-		if (rc < 0) 
-		{
-			/*
-			 * Some exceptional condition occurred.  Results
-			 * have been sent, so we're finished.
-			 */
-			if (rc == SLAPI_FAIL_DISKFULL) 
-			{
-				operation_out_of_disk_space();
-			}
-			return -1;
-		} 
-		else 
-		{
-			slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY, &next_e);
-			slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, &next_backend_info_ptr);
-			if (next_e == NULL) 
-			{
-				/* no more entries */
-				done = 1;
-			}
-		}
-
-		if (process_entry(pb, e, send_result)) 
-		{
-			/* shouldn't  send this entry */
-			continue;
-		}
-
-		/*
-		 * It's a regular entry, or it's a referral and
-		 * managedsait control is on.  In either case, send the entry.
-		 */
-		if (done) 
-		{
-			struct berval **urls = NULL;
-			/* Send the entry and the result at the same time */
-			slapi_pblock_get(pb, SLAPI_SEARCH_REFERRALS, &urls);
-			rc = send_ldap_search_entry_ext(pb, e, NULL, attrs, attrsonly, 1, 
-											(*pnentries)+1, urls);
-			if (rc == 1) 
-			{
-				/* this means we didn't have access to the entry. Since the
-				 * entry was not sent, we need to send the done packet.
-				 */
-				send_result_status = 1;
-			}
-		} 
-		else 
-		{
-			/* Send the entry */
-			rc = send_ldap_search_entry(pb, e, NULL, attrs, 
-						attrsonly);
-		}
-		switch (rc) 
-		{
-			case 0:		/* entry sent ok */
-				(*pnentries)++;
-				slapi_pblock_set(pb, SLAPI_NENTRIES, pnentries);
-				break;
-			case 1:		/* entry not sent */
-				break;
-			case -1:	/* connection closed */
-				/*
-				 * mark the operation as abandoned so the backend
-				 * next entry function gets called again and has
-				 * a chance to clean things up.
-				 */
-				pb->pb_op->o_status = SLAPI_OP_STATUS_ABANDONED;
-				break;
-		}
+    {
+        /* Allow the backend to free the entry we just finished using */
+        /* It is ok to call this when backend_info_ptr is NULL */
+        be->be_entry_release(pb, backend_info_ptr);
+        e = next_e;
+        backend_info_ptr = next_backend_info_ptr;
+
+        rc = be->be_next_search_entry_ext(pb, 1);
+        if (rc < 0) 
+        {
+            /*
+             * Some exceptional condition occurred.  Results
+             * have been sent, so we're finished.
+             */
+            if (rc == SLAPI_FAIL_DISKFULL) 
+            {
+                operation_out_of_disk_space();
+            }
+            return -1;
+        } 
+        else 
+        {
+            slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY, &next_e);
+            slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY_EXT, &next_backend_info_ptr);
+            if (next_e == NULL) 
+            {
+                /* no more entries */
+                done = 1;
+            }
+        }
+
+        if (process_entry(pb, e, send_result)) 
+        {
+            /* shouldn't  send this entry */
+            continue;
+        }
+
+        /*
+         * It's a regular entry, or it's a referral and
+         * managedsait control is on.  In either case, send the entry.
+         */
+        if (done) 
+        {
+            struct berval **urls = NULL;
+            /* Send the entry and the result at the same time */
+            slapi_pblock_get(pb, SLAPI_SEARCH_REFERRALS, &urls);
+            rc = send_ldap_search_entry_ext(pb, e, NULL, attrs, attrsonly, 1, 
+                                            (*pnentries)+1, urls);
+            if (rc == 1) 
+            {
+                /* this means we didn't have access to the entry. Since the
+                 * entry was not sent, we need to send the done packet.
+                 */
+                send_result_status = 1;
+            }
+        } 
+        else 
+        {
+            /* Send the entry */
+            rc = send_ldap_search_entry(pb, e, NULL, attrs, 
+                        attrsonly);
+        }
+        switch (rc) 
+        {
+            case 0:        /* entry sent ok */
+                (*pnentries)++;
+                slapi_pblock_set(pb, SLAPI_NENTRIES, pnentries);
+                break;
+            case 1:        /* entry not sent */
+                break;
+            case -1:    /* connection closed */
+                /*
+                 * mark the operation as abandoned so the backend
+                 * next entry function gets called again and has
+                 * a chance to clean things up.
+                 */
+                pb->pb_op->o_status = SLAPI_OP_STATUS_ABANDONED;
+                break;
+        }
     }
 
     be->be_entry_release(pb, backend_info_ptr);
     if (*pnentries == 0 || send_result_status) 
-	{
-		/* We didn't send the result done message so the caller 
-		 * must send it */
-		return 1;
+    {
+        /* We didn't send the result done message so the caller 
+         * must send it */
+        return 1;
     } 
-	else 
-	{
-		/* The result message has been sent */
-		return 0;
+    else 
+    {
+        /* The result message has been sent */
+        return 0;
     }
 }
 #endif
@@ -948,7 +1060,8 @@ iterate_with_lookahead(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int
  * iterate_with_lookahead trys to do.
  */
 static int
-iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries) 
+iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result,
+        int *pnentries, int pagesize, unsigned int *pr_stat) 
 {
     int rc;
     int attrsonly;
@@ -960,6 +1073,9 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
     slapi_pblock_get(pb, SLAPI_SEARCH_ATTRSONLY, &attrsonly);
 
     *pnentries = 0;
+    if (pr_stat) {
+        *pr_stat = 0;
+    }
     
     while (!done) 
     {
@@ -970,12 +1086,15 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
         if (rc < 0) 
         {
             /*
-             * Some exceptional condition occurred. Results have been sent, so we're finished.
+             * Some exceptional condition occurred. Results have been sent,
+             * so we're finished.
              */
             if (rc == SLAPI_FAIL_DISKFULL) 
             {
                 operation_out_of_disk_space();
             }
+            *pr_stat = PAGEDRESULTS_SEARCH_END;
+            pagedresults_set_timelimit(pb->pb_conn, 0);
             return -1;
         } 
 
@@ -1025,6 +1144,7 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
                     slapi_pblock_get(pb, SLAPI_SEARCH_RESULT_ENTRY, &e);
                     if (NULL == e) {
                         /* everything is ok - don't send the result */
+                        *pr_stat = PAGEDRESULTS_SEARCH_END;
                         return 1;
                     }
                     gerentry = e;
@@ -1044,6 +1164,7 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
                         slapi_entry_free(gerentry);
                         gerentry = e = NULL;
                     }
+                    *pr_stat = PAGEDRESULTS_SEARCH_END;
                     return( -1 );
                 }
                 slapi_ch_free ( (void**)&errbuf );
@@ -1097,6 +1218,9 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
             {
                 /* no more entries */
                 done = 1;
+                if (pr_stat) {
+                    *pr_stat = PAGEDRESULTS_SEARCH_END;
+                }
             }
         }
         else if (e)
@@ -1129,11 +1253,22 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
                     pb->pb_op->o_status = SLAPI_OP_STATUS_ABANDONED;
                     break;
             }
+            if (pagesize == *pnentries)
+            { 
+                /* PAGED RESULTS: reached the pagesize */
+                done = 1;
+                if (pr_stat) {
+                    *pr_stat = PAGEDRESULTS_PAGE_END;
+                }
+            }
         }
         else
         {
             /* no more entries */
             done = 1;
+            if (pr_stat) {
+                *pr_stat = PAGEDRESULTS_SEARCH_END;
+            }
         }
     }
 
@@ -1141,8 +1276,8 @@ iterate(Slapi_PBlock *pb, Slapi_Backend *be, int send_result, int *pnentries)
 }
 
 
-static int		timelimit_reslimit_handle = -1;
-static int		sizelimit_reslimit_handle = -1;
+static int        timelimit_reslimit_handle = -1;
+static int        sizelimit_reslimit_handle = -1;
 
 /*
  * Register size and time limit with the binder-based resource limits
@@ -1151,18 +1286,18 @@ static int		sizelimit_reslimit_handle = -1;
 int
 search_register_reslimits( void )
 {
-	int		rc1, rc2;
+    int        rc1, rc2;
 
     rc1 = slapi_reslimit_register( SLAPI_RESLIMIT_TYPE_INT,
             "nsSizeLimit" , &sizelimit_reslimit_handle );
     rc2 = slapi_reslimit_register( SLAPI_RESLIMIT_TYPE_INT,
             "nsTimeLimit", &timelimit_reslimit_handle );
 
-	if ( rc1 != SLAPI_RESLIMIT_STATUS_SUCCESS ) {
-		return( rc1 );
-	} else {
-		return( rc2 );
-	}
+    if ( rc1 != SLAPI_RESLIMIT_STATUS_SUCCESS ) {
+        return( rc1 );
+    } else {
+        return( rc2 );
+    }
 }
 
 
@@ -1179,162 +1314,171 @@ search_register_reslimits( void )
 static void
 compute_limits (Slapi_PBlock *pb)
 {
-	int timelimit, sizelimit;
-	int requested_timelimit, max_timelimit, requested_sizelimit, max_sizelimit;
-	int isroot;
-	int isCertAuth;
-	Slapi_ComponentId *component_id = NULL;
-	Slapi_Backend *be;
-
-	slapi_pblock_get (pb, SLAPI_SEARCH_TIMELIMIT, &requested_timelimit);
-	slapi_pblock_get (pb, SLAPI_SEARCH_SIZELIMIT, &requested_sizelimit);
-	slapi_pblock_get (pb, SLAPI_REQUESTOR_ISROOT, &isroot);
-	slapi_pblock_get (pb, SLAPI_BACKEND, &be);
-
-
-	/* If the search belongs to the client authentication process, take the value at
-	 * nsslapd-timelimit as the actual time limit.
-	 */
-	
-	slapi_pblock_get (pb, SLAPI_PLUGIN_IDENTITY, &component_id);
-	if (component_id) {
-	     isCertAuth = (! strcasecmp(component_id->sci_component_name, COMPONENT_CERT_AUTH) ) ? 1 : 0;
-	     if (isCertAuth) {
-	           timelimit = config_get_timelimit();
-		   goto set_timelimit;
-	     }
-	}
-
-	/*
-	 * Compute the time limit.
-	 */
-	if ( slapi_reslimit_get_integer_limit( pb->pb_conn,
-			timelimit_reslimit_handle, &max_timelimit )
-			!= SLAPI_RESLIMIT_STATUS_SUCCESS ) {
-		/*
-		 * no limit associated with binder/connection or some other error
-		 * occurred.  use the default maximum.
-	 	 */
-		if ( isroot ) {
-			max_timelimit = -1;	/* no limit */
-		} else {
-			max_timelimit = be->be_timelimit;
-		}
-	}
-
-	if ( requested_timelimit == 0 ) {
-			timelimit = ( max_timelimit == -1 ) ? -1 : max_timelimit;
-	} else if ( max_timelimit == -1 || requested_timelimit < max_timelimit ) {
-			timelimit = requested_timelimit;
-	} else {
-			timelimit = max_timelimit;
-	}
+    int timelimit, sizelimit;
+    int requested_timelimit, max_timelimit, requested_sizelimit, max_sizelimit;
+    int isroot;
+    int isCertAuth;
+    Slapi_ComponentId *component_id = NULL;
+    Slapi_Backend *be;
+
+    slapi_pblock_get (pb, SLAPI_SEARCH_TIMELIMIT, &requested_timelimit);
+    slapi_pblock_get (pb, SLAPI_SEARCH_SIZELIMIT, &requested_sizelimit);
+    slapi_pblock_get (pb, SLAPI_REQUESTOR_ISROOT, &isroot);
+    slapi_pblock_get (pb, SLAPI_BACKEND, &be);
+
+
+    /* If the search belongs to the client authentication process, take the value at
+     * nsslapd-timelimit as the actual time limit.
+     */
+    
+    slapi_pblock_get (pb, SLAPI_PLUGIN_IDENTITY, &component_id);
+    if (component_id) {
+         isCertAuth = (! strcasecmp(component_id->sci_component_name, COMPONENT_CERT_AUTH) ) ? 1 : 0;
+         if (isCertAuth) {
+               timelimit = config_get_timelimit();
+           goto set_timelimit;
+         }
+    }
+
+    /*
+     * Compute the time limit.
+     */
+    if ( slapi_reslimit_get_integer_limit( pb->pb_conn,
+            timelimit_reslimit_handle, &max_timelimit )
+            != SLAPI_RESLIMIT_STATUS_SUCCESS ) {
+        /*
+         * no limit associated with binder/connection or some other error
+         * occurred.  use the default maximum.
+          */
+        if ( isroot ) {
+            max_timelimit = -1;    /* no limit */
+        } else {
+            max_timelimit = be->be_timelimit;
+        }
+    }
+
+    if ( requested_timelimit == 0 ) {
+            timelimit = ( max_timelimit == -1 ) ? -1 : max_timelimit;
+    } else if ( max_timelimit == -1 || requested_timelimit < max_timelimit ) {
+            timelimit = requested_timelimit;
+    } else {
+            timelimit = max_timelimit;
+    }
 
  set_timelimit:
-	slapi_pblock_set(pb, SLAPI_SEARCH_TIMELIMIT, &timelimit);
-
-
-	/*
-	 * Compute the size limit.
-	 */
-	if ( slapi_reslimit_get_integer_limit( pb->pb_conn,
-			sizelimit_reslimit_handle, &max_sizelimit )
-			!= SLAPI_RESLIMIT_STATUS_SUCCESS ) {
-		/*
-		 * no limit associated with binder/connection or some other error
-		 * occurred.  use the default maximum.
-	 	 */
-		if ( isroot ) {
-			max_sizelimit = -1;	/* no limit */
-		} else {
-			max_sizelimit = be->be_sizelimit;
-		}
-	}
-
-	if ( requested_sizelimit == 0 ) {
-			sizelimit = ( max_sizelimit == -1 ) ? -1 : max_sizelimit;
-	} else if ( max_sizelimit == -1 || requested_sizelimit < max_sizelimit ) {
-			sizelimit = requested_sizelimit;
-	} else {
-			sizelimit = max_sizelimit;
-	}
-	slapi_pblock_set(pb, SLAPI_SEARCH_SIZELIMIT, &sizelimit);
-
-	LDAPDebug( LDAP_DEBUG_TRACE,
-			"=> compute_limits: sizelimit=%d, timelimit=%d\n",
-			sizelimit, timelimit, 0 );
+    slapi_pblock_set(pb, SLAPI_SEARCH_TIMELIMIT, &timelimit);
+
+
+    /*
+     * Compute the size limit.
+     */
+    if ( slapi_reslimit_get_integer_limit( pb->pb_conn,
+            sizelimit_reslimit_handle, &max_sizelimit )
+            != SLAPI_RESLIMIT_STATUS_SUCCESS ) {
+        /*
+         * no limit associated with binder/connection or some other error
+         * occurred.  use the default maximum.
+          */
+        if ( isroot ) {
+            max_sizelimit = -1;    /* no limit */
+        } else {
+            max_sizelimit = be->be_sizelimit;
+        }
+    }
+
+    if ( requested_sizelimit == 0 ) {
+            sizelimit = ( max_sizelimit == -1 ) ? -1 : max_sizelimit;
+    } else if ( max_sizelimit == -1 || requested_sizelimit < max_sizelimit ) {
+            sizelimit = requested_sizelimit;
+    } else {
+            sizelimit = max_sizelimit;
+    }
+    slapi_pblock_set(pb, SLAPI_SEARCH_SIZELIMIT, &sizelimit);
+
+    LDAPDebug( LDAP_DEBUG_TRACE,
+            "=> compute_limits: sizelimit=%d, timelimit=%d\n",
+            sizelimit, timelimit, 0 );
 }
 
+/* Iterates through results and send them to the client.
+ * Returns 0 if successful and -1 otherwise
+ */
+static int
+send_results_ext(Slapi_PBlock *pb, int send_result, int *nentries, int pagesize, unsigned int *pr_stat)
+{
+    Slapi_Backend *be; 
+    int rc;
+
+    slapi_pblock_get (pb, SLAPI_BACKEND, &be);
+
+    if (be->be_next_search_entry == NULL)
+    {
+        /* we need to send the result, but the function to iterate through 
+           the result set is not implemented */
+        /* ONREPL - log error */
+        send_ldap_result(pb, LDAP_UNWILLING_TO_PERFORM, NULL, "Search not supported", 0, NULL);
+        return -1;
+    }
+
+    /* Iterate through the returned result set */
+    if (be->be_next_search_entry_ext != NULL)
+    {
+        /* The iterate look ahead is causing a whole mess with the ACL.
+        ** the entries are now visiting the ACL land in a random way
+        ** and not the ordered way it was before. Until we figure out
+        ** let's not change the behavior.
+        **
+        ** Don't use iterate_with_lookahead because it sends the result 
+        * in the same times as the entry and this can cause failure
+        * of the mapping tree scanning algorithme
+        * if (getFrontendConfig()->result_tweak)
+        * {
+        *    rc = iterate_with_lookahead(pb, be, send_result, nentries);
+        * }
+        * else
+        */
+        rc = iterate(pb, be, send_result, nentries, pagesize, pr_stat);
+    }
+    else
+    {
+        rc = iterate(pb, be, send_result, nentries, pagesize, pr_stat);
+    }
+
+    switch(rc) 
+    {
+        case -1:    /* an error occured */
+
+        case 0 :    /* everything is ok - result is sent */
+                    /* If this happens we are dead but hopefully iterate
+                     * never sends the result itself 
+                     */
+                    break;    
+
+        case 1:        /* everything is ok - don't send the result */
+                    rc = 0;
+    }
+    
+    return rc;
+}
 
 /* Iterates through results and send them to the client.
  * Returns 0 if successful and -1 otherwise
  */
-static int  send_results (Slapi_PBlock *pb, int send_result, int * nentries)
+static int 
+send_results(Slapi_PBlock *pb, int send_result, int *nentries)
 {
-	Slapi_Backend *be; 
-	int rc;
-
-	slapi_pblock_get (pb, SLAPI_BACKEND, &be);
-
-	if (be->be_next_search_entry == NULL)
-	{
-		/* we need to send the result, but the function to iterate through 
-		   the result set is not implemented */
-		/* ONREPL - log error */
-		send_ldap_result(pb, LDAP_UNWILLING_TO_PERFORM, NULL, "Search not supported", 0, NULL);
-		return -1;
-	}
-
-	/* Iterate through the returned result set */
-	if (be->be_next_search_entry_ext != NULL)
-	{
-	   /* The iterate look ahead is causing a whole mess with the ACL.
-		** the entries are now visiting the ACL land in a random way
-		** and not the ordered way it was before. Until we figure out
-		** let's not change the behavior.
-		**
-		** Don't use iterate_with_lookahead because it sends the result 
-		* in the same times as the entry and this can cause failure
-		* of the mapping tree scanning algorithme
-		* if (getFrontendConfig()->result_tweak)
-		* {
-		*	rc = iterate_with_lookahead(pb, be, send_result, nentries);
-		* }
-		* else
-		*/
-			rc = iterate(pb, be, send_result, nentries);
-	}
-	else
-	{
-		rc = iterate(pb, be, send_result, nentries);
-	}		 
-
-	switch(rc) 
-	{
-		case -1:	/* an error occured */
-
-		case 0 :	/* everything is ok - result is sent */
-				    /* If this happens we are dead but hopefully iterate
-					 * never sends the result itself 
-					 */
-					break;	
-
-		case 1:		/* everything is ok - don't send the result */
-					rc = 0;
-	}
-	
-	return rc;
+    return send_results_ext(pb, send_result, nentries, -1, NULL);
 }
 
 void op_shared_log_error_access (Slapi_PBlock *pb, const char *type, const char *dn, const char *msg)
 {
-	char ebuf[BUFSIZ];
-	slapi_log_access( LDAP_DEBUG_STATS, "conn=%" NSPRIu64 " op=%d %s dn=\"%s\", %s\n",
-		              ( pb->pb_conn ? pb->pb_conn->c_connid : 0), 
-					  ( pb->pb_op ? pb->pb_op->o_opid : 0), 
-					  type, 
-					  escape_string( dn, ebuf ), 
-					  msg ? msg : "" );
+    char ebuf[BUFSIZ];
+    slapi_log_access( LDAP_DEBUG_STATS, "conn=%" NSPRIu64 " op=%d %s dn=\"%s\", %s\n",
+                      ( pb->pb_conn ? pb->pb_conn->c_connid : 0), 
+                      ( pb->pb_op ? pb->pb_op->o_opid : 0), 
+                      type, 
+                      escape_string( dn, ebuf ), 
+                      msg ? msg : "" );
 
 }
 
diff --git a/ldap/servers/slapd/pagedresults.c b/ldap/servers/slapd/pagedresults.c
new file mode 100644
index 00000000..f140933e
--- /dev/null
+++ b/ldap/servers/slapd/pagedresults.c
@@ -0,0 +1,315 @@
+/** BEGIN COPYRIGHT BLOCK
+ * This Program is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software
+ * Foundation; version 2 of the License.
+ * 
+ * This Program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License along with
+ * this Program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA.
+ * 
+ * In addition, as a special exception, Red Hat, Inc. gives You the additional
+ * right to link the code of this Program with code not covered under the GNU
+ * General Public License ("Non-GPL Code") and to distribute linked combinations
+ * including the two, subject to the limitations in this paragraph. Non-GPL Code
+ * permitted under this exception must only link to the code of this Program
+ * through those well defined interfaces identified in the file named EXCEPTION
+ * found in the source code files (the "Approved Interfaces"). The files of
+ * Non-GPL Code may instantiate templates or use macros or inline functions from
+ * the Approved Interfaces without causing the resulting work to be covered by
+ * the GNU General Public License. Only Red Hat, Inc. may make changes or
+ * additions to the list of Approved Interfaces. You must obey the GNU General
+ * Public License in all respects for all of the Program code and other code used
+ * in conjunction with the Program except the Non-GPL Code covered by this
+ * exception. If you modify this file, you may extend this exception to your
+ * version of the file, but you are not obligated to do so. If you do not wish to
+ * provide this exception without modification, you must delete this exception
+ * statement from your version and license this file solely under the GPL without
+ * exception. 
+ * 
+ * 
+ * Copyright (C) 2009 Red Hat, Inc.
+ * All rights reserved.
+ * END COPYRIGHT BLOCK **/
+
+#ifdef HAVE_CONFIG_H
+#  include <config.h>
+#endif
+
+#include "slap.h"
+
+/*
+ * Parse the value from an LDAPv3 "Simple Paged Results" control.  They look
+ * like this:
+ * 
+ *   realSearchControlValue ::= SEQUENCE {
+ *   size INTEGER (0..maxInt),
+ *   -- requested page size from client
+ *   -- result set size estimate from server
+ *   cookie OCTET STRING
+ *   }
+ *
+ * Return an LDAP error code (LDAP_SUCCESS if all goes well).
+ */
+int
+pagedresults_parse_control_value( struct berval *psbvp,
+                                  ber_int_t *pagesize, int *curr_search_count )
+{
+    int rc = LDAP_SUCCESS;
+    struct berval cookie = {0};
+
+    if ( NULL == pagesize || NULL == curr_search_count ) {
+        return LDAP_OPERATIONS_ERROR;
+    }
+
+    if ( psbvp->bv_len == 0 || psbvp->bv_val == NULL )
+    {
+        rc = LDAP_PROTOCOL_ERROR;
+    }
+    else
+    {
+        BerElement *ber = ber_init( psbvp );
+        if ( ber == NULL )
+        {
+            rc = LDAP_OPERATIONS_ERROR;
+        }
+        else
+        {
+            if ( ber_scanf( ber, "{io}", pagesize, &cookie ) == LBER_ERROR )
+            {
+                rc = LDAP_PROTOCOL_ERROR;
+            }
+            /* the ber encoding is no longer needed */
+            ber_free(ber, 1);
+            if ( cookie.bv_len <= 0 ) {
+                *curr_search_count = 0;
+            } else {
+                /* not an error */
+                char *ptr = slapi_ch_malloc(cookie.bv_len + 1);
+                memcpy(ptr, cookie.bv_val, cookie.bv_len);
+                *(ptr+cookie.bv_len) = '\0';
+                *curr_search_count = strtol(ptr, NULL, 10);
+                slapi_ch_free_string(&ptr);
+            }
+            slapi_ch_free((void **)&cookie.bv_val);
+        }
+    }
+
+    return rc;
+}
+
+/*
+ * controlType = LDAP_CONTROL_PAGEDRESULTS;
+ * criticality = n/a;
+ * controlValue:
+ *   realSearchControlValue ::= SEQUENCE {
+ *   size INTEGER (0..maxInt),
+ *   -- requested page size from client
+ *   -- result set size estimate from server
+ *   cookie OCTET STRING
+ *   }
+ */
+void
+pagedresults_set_response_control( Slapi_PBlock *pb, int iscritical,
+                                    ber_int_t pagesize, int curr_search_count )
+{
+    LDAPControl **resultctrls = NULL;
+    LDAPControl pr_respctrl;
+    BerElement *ber = NULL;
+    struct berval *berval = NULL;
+    char *cookie_str = NULL;
+    int found = 0;
+    int i;
+
+    if ( (ber = der_alloc()) == NULL )
+    {
+        goto bailout;
+    }
+
+    /* begin sequence, payload, end sequence */
+    if (curr_search_count < 0) {
+        cookie_str = slapi_ch_smprintf("");
+    } else {
+        cookie_str = slapi_ch_smprintf("%d", curr_search_count);
+    }
+    ber_printf ( ber, "{io}", pagesize, cookie_str, strlen(cookie_str) );
+    if ( ber_flatten ( ber, &berval ) != LDAP_SUCCESS )
+    {
+        goto bailout;
+    }
+    pr_respctrl.ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
+    pr_respctrl.ldctl_iscritical = iscritical;
+    pr_respctrl.ldctl_value.bv_val = berval->bv_val;
+    pr_respctrl.ldctl_value.bv_len = berval->bv_len;
+
+    slapi_pblock_get ( pb, SLAPI_RESCONTROLS, &resultctrls );
+    for (i = 0; resultctrls && resultctrls[i]; i++)
+    {
+        if (strcmp(resultctrls[i]->ldctl_oid, LDAP_CONTROL_PAGEDRESULTS) == 0)
+        {
+            /*
+             * We get here if search returns more than one entry
+             * and this is not the first entry.
+             */
+            ldap_control_free ( resultctrls[i] );
+            resultctrls[i] = slapi_dup_control (&pr_respctrl);
+            found = 1;
+            break;
+        }
+    }
+
+    if ( !found )
+    {
+        /* slapi_pblock_set() will dup the control */
+        slapi_pblock_set ( pb, SLAPI_ADD_RESCONTROL, &pr_respctrl );
+    }
+
+bailout:
+    slapi_ch_free_string(&cookie_str);
+    ber_free ( ber, 1 );    /* ber_free() checks for NULL param */
+    ber_bvfree ( berval );    /* ber_bvfree() checks for NULL param */
+}
+
+/* setters and getters for the connection */
+Slapi_Backend *
+pagedresults_get_current_be(Connection *conn)
+{
+    Slapi_Backend *be = NULL;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        be = conn->c_current_be;
+        PR_Unlock(conn->c_mutex);
+    }
+    return be;
+}
+
+int
+pagedresults_set_current_be(Connection *conn, Slapi_Backend *be)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        conn->c_current_be = be;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
+void *
+pagedresults_get_search_result(Connection *conn)
+{
+    void *sr = NULL;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        sr = conn->c_search_result_set;
+        PR_Unlock(conn->c_mutex);
+    }
+    return sr;
+}
+
+int
+pagedresults_set_search_result(Connection *conn, void *sr)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        conn->c_search_result_set = sr;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
+int
+pagedresults_get_search_result_count(Connection *conn)
+{
+    int count = 0;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        count = conn->c_search_result_count;
+        PR_Unlock(conn->c_mutex);
+    }
+    return count;
+}
+
+int
+pagedresults_set_search_result_count(Connection *conn, int count)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        conn->c_search_result_count = count;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
+int
+pagedresults_get_with_sort(Connection *conn)
+{
+    int flags = 0;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        flags = conn->c_flags&CONN_FLAG_PAGEDRESULTS_WITH_SORT;
+        PR_Unlock(conn->c_mutex);
+    }
+    return flags;
+}
+
+int
+pagedresults_set_with_sort(Connection *conn, int flags)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        if (flags & OP_FLAG_SERVER_SIDE_SORTING)
+          conn->c_flags |= CONN_FLAG_PAGEDRESULTS_WITH_SORT;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
+int
+pagedresults_get_sort_result_code(Connection *conn)
+{
+    int code = 0;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        code = conn->c_sort_result_code;
+        PR_Unlock(conn->c_mutex);
+    }
+    return code;
+}
+
+int
+pagedresults_set_sort_result_code(Connection *conn, int code)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        conn->c_sort_result_code = code;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
+int
+pagedresults_set_timelimit(Connection *conn, time_t timelimit)
+{
+    int rc = -1;
+    if (conn) {
+        PR_Lock(conn->c_mutex);
+        conn->c_timelimit = timelimit;
+        PR_Unlock(conn->c_mutex);
+        rc = 0;
+    }
+    return rc;
+}
+
diff --git a/ldap/servers/slapd/pblock.c b/ldap/servers/slapd/pblock.c
index 062a87f8..dd8239db 100644
--- a/ldap/servers/slapd/pblock.c
+++ b/ldap/servers/slapd/pblock.c
@@ -512,6 +512,12 @@ slapi_pblock_get( Slapi_PBlock *pblock, int arg, void *value )
 		}
 		(*(IFP *)value) = pblock->pb_plugin->plg_entry_release;
 		break;
+	case SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN:
+		if ( pblock->pb_plugin->plg_type != SLAPI_PLUGIN_DATABASE ) {
+			return( -1 );
+		}
+		(*(IFP *)value) = pblock->pb_plugin->plg_search_results_release;
+		break;
 	case SLAPI_PLUGIN_DB_COMPARE_FN:
 		if ( pblock->pb_plugin->plg_type != SLAPI_PLUGIN_DATABASE ) {
 			return( -1 );
@@ -1804,6 +1810,12 @@ slapi_pblock_set( Slapi_PBlock *pblock, int arg, void *value )
 		}
 		pblock->pb_plugin->plg_entry_release = (IFP) value;
 		break;
+	case SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN:
+		if ( pblock->pb_plugin->plg_type != SLAPI_PLUGIN_DATABASE ) {
+			return( -1 );
+		}
+		pblock->pb_plugin->plg_search_results_release = (IFP) value;
+		break;
 	case SLAPI_PLUGIN_DB_COMPARE_FN:
 		if ( pblock->pb_plugin->plg_type != SLAPI_PLUGIN_DATABASE ) {
 			return( -1 );
diff --git a/ldap/servers/slapd/proto-slap.h b/ldap/servers/slapd/proto-slap.h
index 2041a997..1ba7ddae 100644
--- a/ldap/servers/slapd/proto-slap.h
+++ b/ldap/servers/slapd/proto-slap.h
@@ -1326,4 +1326,23 @@ void signal2sigaction( int s, void *a );
 int slapd_do_all_nss_ssl_init(int slapd_exemode, int importexport_encrypt,
                               int s_port, daemon_ports_t *ports_info);
 
+/*
+ * pagedresults.c
+ */
+int pagedresults_parse_control_value(struct berval *psbvp, ber_int_t *pagesize, int *curr_search_count);
+void pagedresults_set_response_control(Slapi_PBlock *pb, int	iscritical, ber_int_t pagesize, int curr_search_count);
+Slapi_Backend *pagedresults_get_current_be(Connection *conn);
+int pagedresults_set_current_be(Connection *conn, Slapi_Backend *be);
+void *pagedresults_get_search_result(Connection *conn);
+int pagedresults_set_search_result(Connection *conn, void *sr);
+int pagedresults_get_search_result_count(Connection *conn);
+int pagedresults_set_search_result_count(Connection *conn, int cnt);
+int pagedresults_get_with_sort(Connection *conn);
+int pagedresults_set_with_sort(Connection *conn, int flags);
+
+/*
+ * sort.c
+ */
+int sort_make_sort_response_control(Slapi_PBlock *pb, int code, char *error_type);
+
 #endif /* _PROTO_SLAP */
diff --git a/ldap/servers/slapd/result.c b/ldap/servers/slapd/result.c
index 749361f1..cd02f01f 100644
--- a/ldap/servers/slapd/result.c
+++ b/ldap/servers/slapd/result.c
@@ -67,10 +67,10 @@ static long	current_conn_count;
 static PRLock	*current_conn_count_mutex;
 
 static int flush_ber( Slapi_PBlock *pb, Connection *conn,
-	Operation *op, BerElement *ber, int type );
+					  Operation *op, BerElement *ber, int type );
 static char *notes2str( unsigned int notes, char *buf, size_t buflen );
 static void log_result( Slapi_PBlock *pb, Operation *op, int err,
-	ber_tag_t tag, int nentries );
+						ber_tag_t tag, int nentries );
 static void log_entry( Operation *op, Slapi_Entry *e );
 static void log_referral( Operation *op );
 
@@ -1346,7 +1346,7 @@ send_ldap_search_entry_ext(
 
 	if ( conn->c_ldapversion >= LDAP_VERSION3 ) {
 		if ( ectrls != NULL ) {
-	    	rc = write_controls( ber, ectrls );
+			rc = write_controls( ber, ectrls );
 		}
 		/*
 		 * The get-effective-rights control is called within
@@ -1360,7 +1360,20 @@ send_ldap_search_entry_ext(
 				if (strcmp(ctrlp[i]->ldctl_oid, LDAP_CONTROL_GET_EFFECTIVE_RIGHTS ) == 0 ) {
 					gerctrl[0] = ctrlp[i];
 					gerctrl[1] = NULL;
-	    			rc = write_controls( ber, gerctrl );
+					rc = write_controls( ber, gerctrl );
+					break;
+				}
+			}
+		}
+		if ( operation->o_flags & OP_FLAG_PAGED_RESULTS ) {
+			LDAPControl *pagedctrl[2];
+			slapi_pblock_get (pb, SLAPI_RESCONTROLS, &ctrlp);
+			for ( i = 0; ctrlp != NULL && ctrlp[i] != NULL; i++ ) {
+				if (strcmp(ctrlp[i]->ldctl_oid, LDAP_CONTROL_PAGEDRESULTS )
+																	== 0 ) {
+					pagedctrl[0] = ctrlp[i];
+					pagedctrl[1] = NULL;
+					rc = write_controls( ber, pagedctrl );
 					break;
 				}
 			}
diff --git a/ldap/servers/slapd/slap.h b/ldap/servers/slapd/slap.h
index 724bef93..3bcadde8 100644
--- a/ldap/servers/slapd/slap.h
+++ b/ldap/servers/slapd/slap.h
@@ -202,6 +202,11 @@ typedef struct symbol_t {
 #define LDAP_CONTROL_GET_EFFECTIVE_RIGHTS "1.3.6.1.4.1.42.2.27.9.5.2"
 #endif
 
+/* PAGED RESULTS control (shared by request and response) */
+#ifndef LDAP_CONTROL_PAGEDRESULTS
+#define LDAP_CONTROL_PAGEDRESULTS      "1.2.840.113556.1.4.319"
+#endif
+
 #define SLAPD_VENDOR_NAME	"Fedora Project"
 #define SLAPD_VERSION_STR	"Fedora-Directory/" PRODUCTTEXT
 #define SLAPD_SHORT_VERSION_STR	PRODUCTTEXT
@@ -760,6 +765,7 @@ struct slapdplugin {
 			IFP	plg_un_db_search;	  /* search */
 			IFP	plg_un_db_next_search_entry;	/* iterate */
 	        IFP plg_un_db_next_search_entry_ext;
+			IFP plg_un_db_search_results_release; /* PAGED RESULTS */
 	        IFP plg_un_db_entry_release;
 			IFP	plg_un_db_compare;	  /* compare */
 			IFP	plg_un_db_modify;	  /* modify */
@@ -797,6 +803,7 @@ struct slapdplugin {
 #define plg_search		plg_un.plg_un_db.plg_un_db_search
 #define plg_next_search_entry	plg_un.plg_un_db.plg_un_db_next_search_entry
 #define plg_next_search_entry_ext plg_un.plg_un_db.plg_un_db_next_search_entry_ext
+#define plg_search_results_release plg_un.plg_un_db.plg_un_db_search_results_release
 #define plg_entry_release       plg_un.plg_un_db.plg_un_db_entry_release
 #define plg_compare		plg_un.plg_un_db.plg_un_db_compare
 #define plg_modify		plg_un.plg_un_db.plg_un_db_modify
@@ -1050,6 +1057,7 @@ typedef struct backend {
 #define	be_next_search_entry be_database->plg_next_search_entry
 #define be_next_search_entry_ext be_database->plg_next_search_entry_ext
 #define be_entry_release be_database->plg_entry_release
+#define be_search_results_release be_database->plg_search_results_release
 #define be_compare		be_database->plg_compare
 #define be_modify		be_database->plg_modify
 #define be_modrdn		be_database->plg_modrdn
@@ -1268,6 +1276,13 @@ typedef struct conn {
     int				c_local_valid; /* flag true if the uid/gid are valid */
     uid_t			c_local_uid;  /* uid of connecting process */
     gid_t			c_local_gid;  /* gid of connecting process */
+    /* PAGED_RESULTS */
+    Slapi_Backend   *c_current_be;         /* backend being used */
+    void            *c_search_result_set;  /* search result set for paging */
+    int             c_search_result_count; /* search result count */
+    int             c_sort_result_code;    /* sort result put in response */
+    time_t          c_timelimit;           /* time limit for this connection */
+    /* PAGED_RESULTS ENDS */
 } Connection;
 #define CONN_FLAG_SSL	1	/* Is this connection an SSL connection or not ? 
 							 * Used to direct I/O code when SSL is handled differently 
@@ -1291,6 +1306,10 @@ typedef struct conn {
                                      * successfully completed.
                                      */
 
+#define CONN_FLAG_PAGEDRESULTS_WITH_SORT 64 /* paged results control is
+                                             * sent with server side sorting
+                                             */
+#define CONN_GET_SORT_RESULT_CODE (-1)
 
 #define START_TLS_OID    "1.3.6.1.4.1.1466.20037"
 
diff --git a/ldap/servers/slapd/slapi-private.h b/ldap/servers/slapd/slapi-private.h
index 115dcc2a..23baf296 100644
--- a/ldap/servers/slapd/slapi-private.h
+++ b/ldap/servers/slapd/slapi-private.h
@@ -417,6 +417,8 @@ slapi_filter_to_string_internal( const struct slapi_filter *f, char *buf, size_t
                                                   * is used to skip VLV op.
                                                   * (see #329951)
                                                   */
+#define OP_FLAG_PAGED_RESULTS            0x40000 /* simple paged results */
+#define OP_FLAG_SERVER_SIDE_SORTING      0x80000 /* server side sorting  */
 
 
 CSN *operation_get_csn(Slapi_Operation *op);
@@ -867,6 +869,7 @@ int valuearray_find(const Slapi_Attr *a, Slapi_Value **va, const Slapi_Value *v)
 #define SLAPI_PLUGIN_DB_UPGRADEDB_FN		235
 #define SLAPI_PLUGIN_DB_DBVERIFY_FN			236
 #define SLAPI_PLUGIN_DB_ADD_SCHEMA_FN		237
+#define SLAPI_PLUGIN_DB_SEARCH_RESULTS_RELEASE_FN	238
 /* database plugin-specific parameters */
 #define SLAPI_PLUGIN_DB_NO_ACL        		250
 #define SLAPI_PLUGIN_DB_RMDB_FN         	280
diff --git a/ldap/servers/slapd/sort.c b/ldap/servers/slapd/sort.c
new file mode 100644
index 00000000..b6814b26
--- /dev/null
+++ b/ldap/servers/slapd/sort.c
@@ -0,0 +1,130 @@
+/** BEGIN COPYRIGHT BLOCK
+ * This Program is free software; you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software
+ * Foundation; version 2 of the License.
+ * 
+ * This Program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License along with
+ * this Program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA.
+ * 
+ * In addition, as a special exception, Red Hat, Inc. gives You the additional
+ * right to link the code of this Program with code not covered under the GNU
+ * General Public License ("Non-GPL Code") and to distribute linked combinations
+ * including the two, subject to the limitations in this paragraph. Non-GPL Code
+ * permitted under this exception must only link to the code of this Program
+ * through those well defined interfaces identified in the file named EXCEPTION
+ * found in the source code files (the "Approved Interfaces"). The files of
+ * Non-GPL Code may instantiate templates or use macros or inline functions from
+ * the Approved Interfaces without causing the resulting work to be covered by
+ * the GNU General Public License. Only Red Hat, Inc. may make changes or
+ * additions to the list of Approved Interfaces. You must obey the GNU General
+ * Public License in all respects for all of the Program code and other code used
+ * in conjunction with the Program except the Non-GPL Code covered by this
+ * exception. If you modify this file, you may extend this exception to your
+ * version of the file, but you are not obligated to do so. If you do not wish to
+ * provide this exception without modification, you must delete this exception
+ * statement from your version and license this file solely under the GPL without
+ * exception. 
+ * 
+ * 
+ * Copyright (C) 2009 Red Hat, Inc.
+ * All rights reserved.
+ * END COPYRIGHT BLOCK **/
+
+#ifdef HAVE_CONFIG_H
+#  include <config.h>
+#endif
+
+#include "slap.h"
+
+/* Fix for bug # 394184, SD, 20 Jul 00 */
+/* fix and cleanup (switch(code) {} removed) */
+/* arg 'code' has now the correct sortResult value */
+int
+sort_make_sort_response_control ( Slapi_PBlock *pb, int code, char *error_type)
+{
+
+    LDAPControl     new_ctrl = {0};
+    BerElement      *ber= NULL;    
+    struct berval   *bvp = NULL;
+    int             rc = -1;
+    ber_int_t       control_code;
+
+    if (code == CONN_GET_SORT_RESULT_CODE) {
+        code = pagedresults_get_sort_result_code(pb->pb_conn);
+    } else {
+        Slapi_Operation *operation;
+        slapi_pblock_get (pb, SLAPI_OPERATION, &operation);
+        if (operation->o_flags & OP_FLAG_PAGED_RESULTS) {
+            pagedresults_set_sort_result_code(pb->pb_conn, code);
+        }
+    }
+
+    control_code = code;
+
+    /*
+       SortResult ::= SEQUENCE {
+         sortResult  ENUMERATED {
+            success                   (0), -- results are sorted
+            operationsError           (1), -- server internal failure
+            timeLimitExceeded         (3), -- timelimit reached before
+                                           -- sorting was completed
+            strongAuthRequired        (8), -- refused to return sorted
+                                           -- results via insecure
+                                           -- protocol
+            adminLimitExceeded       (11), -- too many matching entries
+                                           -- for the server to sort
+            noSuchAttribute          (16), -- unrecognized attribute
+                                           -- type in sort key
+            inappropriateMatching    (18), -- unrecognized or inappro-
+                                           -- priate matching rule in
+                                           -- sort key
+            insufficientAccessRights (50), -- refused to return sorted
+                                           -- results to this client
+            busy                     (51), -- too busy to process
+            unwillingToPerform       (53), -- unable to sort
+            other                    (80)
+         },
+         attributeType [0] AttributeType OPTIONAL
+       }
+     */
+    
+    if ( ( ber = ber_alloc()) == NULL ) {
+        return -1;
+    }
+
+    if (( rc = ber_printf( ber, "{e", control_code )) != -1 ) {
+        if ( rc != -1 && NULL != error_type ) {
+            rc = ber_printf( ber, "s", error_type );
+        }
+        if ( rc != -1 ) {
+            rc = ber_printf( ber, "}" );
+        }
+    }
+    if ( rc != -1 ) {
+        rc = ber_flatten( ber, &bvp );
+    }
+    
+    ber_free( ber, 1 );
+
+    if ( rc == -1 ) {
+        return rc;
+    }
+        
+    new_ctrl.ldctl_oid = LDAP_CONTROL_SORTRESPONSE;
+    new_ctrl.ldctl_value = *bvp;
+    new_ctrl.ldctl_iscritical = 1;         
+
+    if ( slapi_pblock_set( pb, SLAPI_ADD_RESCONTROL, &new_ctrl ) != 0 ) {
+            ber_bvfree(bvp);
+            return( -1 );
+    }
+
+        ber_bvfree(bvp);
+    return( LDAP_SUCCESS );
+}
+/* End fix for bug #394184 */