← Back to branch summary

~ubuntu-branches/ubuntu/saucy/389-ds-base/saucy

« back to all changes in this revision

Viewing changes to .pc/fix-CVE-2013-0312.diff/ldap/servers/slapd/back-ldbm/sort.c

  • Committer: Package Import Robot
  • Author(s): Timo Aaltonen
  • Date: 2013-03-12 09:53:20 UTC
  • Revision ID: package-import@ubuntu.com-20130312095320-kd20z6oloopyt133
Tags: 1.3.0.3-1ubuntu1
* Sync from Debian unstable.
  - cve fix

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/fix-CVE-2013-0312.diff/ldap/servers/slapd/back-ldbm/sort.c
 
1
/** BEGIN COPYRIGHT BLOCK
 
2
 * This Program is free software; you can redistribute it and/or modify it under
 
3
 * the terms of the GNU General Public License as published by the Free Software
 
4
 * Foundation; version 2 of the License.
 
5
 * 
 
6
 * This Program is distributed in the hope that it will be useful, but WITHOUT
 
7
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 
8
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 
9
 * 
 
10
 * You should have received a copy of the GNU General Public License along with
 
11
 * this Program; if not, write to the Free Software Foundation, Inc., 59 Temple
 
12
 * Place, Suite 330, Boston, MA 02111-1307 USA.
 
13
 * 
 
14
 * In addition, as a special exception, Red Hat, Inc. gives You the additional
 
15
 * right to link the code of this Program with code not covered under the GNU
 
16
 * General Public License ("Non-GPL Code") and to distribute linked combinations
 
17
 * including the two, subject to the limitations in this paragraph. Non-GPL Code
 
18
 * permitted under this exception must only link to the code of this Program
 
19
 * through those well defined interfaces identified in the file named EXCEPTION
 
20
 * found in the source code files (the "Approved Interfaces"). The files of
 
21
 * Non-GPL Code may instantiate templates or use macros or inline functions from
 
22
 * the Approved Interfaces without causing the resulting work to be covered by
 
23
 * the GNU General Public License. Only Red Hat, Inc. may make changes or
 
24
 * additions to the list of Approved Interfaces. You must obey the GNU General
 
25
 * Public License in all respects for all of the Program code and other code used
 
26
 * in conjunction with the Program except the Non-GPL Code covered by this
 
27
 * exception. If you modify this file, you may extend this exception to your
 
28
 * version of the file, but you are not obligated to do so. If you do not wish to
 
29
 * provide this exception without modification, you must delete this exception
 
30
 * statement from your version and license this file solely under the GPL without
 
31
 * exception. 
 
32
 * 
 
33
 * 
 
34
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 
35
 * Copyright (C) 2005 Red Hat, Inc.
 
36
 * All rights reserved.
 
37
 * END COPYRIGHT BLOCK **/
 
38
 
 
39
#ifdef HAVE_CONFIG_H
 
40
#  include <config.h>
 
41
#endif
 
42
 
 
43
/* Code to implement result sorting */
 
44
 
 
45
#include "back-ldbm.h"
 
46
 
 
47
#define CHECK_INTERVAL 10 /* The frequency whith which we'll check the admin limits */
 
48
 
 
49
/* Structure to carry the things we need down the call stack */
 
50
struct baggage_carrier {
 
51
        backend *be; /* For id2entry */
 
52
        Slapi_PBlock *pb; /* For slapi_op_abandoned */
 
53
        time_t  stoptime; /* For timelimit policing */
 
54
        int lookthrough_limit;
 
55
        int check_counter; /* Used to avoid checking every 100ns */
 
56
};
 
57
typedef struct baggage_carrier baggage_carrier;
 
58
 
 
59
static int slapd_qsort (baggage_carrier *bc,IDList *list,sort_spec *s);
 
60
static int print_out_sort_spec(char* buffer,sort_spec *s,int *size);
 
61
 
 
62
static void sort_spec_thing_free(sort_spec_thing *s)
 
63
{
 
64
        if (NULL != s->type) {
 
65
                slapi_ch_free((void **)&s->type);
 
66
        }
 
67
        if (NULL != s->matchrule) {
 
68
                slapi_ch_free( (void**)&s->matchrule);
 
69
        }
 
70
        if (NULL != s->mr_pb) {
 
71
                destroy_matchrule_indexer(s->mr_pb);
 
72
            slapi_pblock_destroy (s->mr_pb);
 
73
        }
 
74
        attr_done(&s->sattr);
 
75
        slapi_ch_free( (void**)&s);
 
76
}
 
77
 
 
78
static sort_spec_thing *sort_spec_thing_allocate()
 
79
{
 
80
        return (sort_spec_thing *) slapi_ch_calloc(1,sizeof (sort_spec_thing));
 
81
}
 
82
 
 
83
void sort_spec_free(sort_spec *s)
 
84
{
 
85
        /* Walk down the list freeing */
 
86
        sort_spec_thing *t = (sort_spec_thing*)s;
 
87
        sort_spec_thing *p = NULL;
 
88
        do {
 
89
                p = t->next;
 
90
                sort_spec_thing_free(t);
 
91
                t = p;
 
92
        } while (p);
 
93
}
 
94
 
 
95
static sort_spec_thing * sort_spec_thing_new(char *type, char* matchrule, int reverse)
 
96
{
 
97
        sort_spec_thing *s = sort_spec_thing_allocate();
 
98
        if (NULL == s) {
 
99
                return s;
 
100
        }
 
101
        s->type = type;
 
102
        s->matchrule = matchrule;
 
103
        s->order = reverse;
 
104
    slapi_attr_init(&s->sattr, type);
 
105
        return s;
 
106
}
 
107
 
 
108
void sort_log_access(Slapi_PBlock *pb,sort_spec_thing *s,IDList *candidates)
 
109
{
 
110
#define SORT_LOG_BSZ 64
 
111
#define SORT_LOG_PAD 22 /* space for the number of candidates */ 
 
112
        char stack_buffer[SORT_LOG_BSZ + SORT_LOG_PAD];
 
113
        char *buffer = NULL;
 
114
        int ret = 0;
 
115
        int size = SORT_LOG_BSZ + SORT_LOG_PAD;
 
116
        char *prefix = "SORT ";
 
117
        int prefix_size = strlen(prefix);
 
118
        char candidate_buffer[32]; /* store u_long value; max 20 digits */
 
119
        int candidate_size = 0;
 
120
 
 
121
        buffer = stack_buffer;
 
122
        size -= PR_snprintf(buffer,sizeof(stack_buffer),"%s",prefix);
 
123
        if (candidates) {
 
124
                if (ALLIDS(candidates)) {
 
125
                        PR_snprintf(candidate_buffer, sizeof(candidate_buffer), "(*)");
 
126
                        candidate_size = strlen(candidate_buffer);
 
127
                } else {
 
128
                        PR_snprintf(candidate_buffer, sizeof(candidate_buffer),
 
129
                                                        "(%lu)", (u_long)candidates->b_nids);
 
130
                        candidate_size = strlen(candidate_buffer);
 
131
                }
 
132
        }
 
133
        size -= (candidate_size + 1);   /* 1 for '\0' */
 
134
        ret = print_out_sort_spec(buffer+prefix_size,s,&size);
 
135
        if (0 != ret) {
 
136
                /* It wouldn't fit in the buffer */
 
137
                buffer =
 
138
                        slapi_ch_malloc(prefix_size + size + candidate_size + SORT_LOG_PAD);
 
139
                sprintf(buffer,"%s",prefix);
 
140
                ret = print_out_sort_spec(buffer+prefix_size,s,&size);
 
141
        }
 
142
        if (0 == ret && candidates) {
 
143
                sprintf(buffer+size+prefix_size, "%s", candidate_buffer);
 
144
        }
 
145
        /* Now output it */
 
146
        ldbm_log_access_message(pb,buffer);
 
147
        if (buffer != stack_buffer) {
 
148
                slapi_ch_free( (void**)&buffer);
 
149
        }
 
150
}
 
151
 
 
152
/* Fix for bug # 394184, SD, 20 Jul 00 */
 
153
/* replace the hard coded return value by the appropriate LDAP error code */
 
154
/* also removed an useless if (0 == return_value) {} statement */
 
155
/* Given a candidate list and a list of sort order specifications, sort this, or cop out */
 
156
/* Returns:  0 -- sorted OK                  now is: LDAP_SUCCESS (fix for bug #394184)
 
157
 *                      -1 -- protocol error             now is: LDAP_PROTOCOL_ERROR 
 
158
 *                      -2 -- too hard to sort these     now is: LDAP_UNWILLING_TO_PERFORM
 
159
 *                      -3 -- operation error            now is: LDAP_OPERATIONS_ERROR
 
160
 *                      -4 -- timeout                    now is: LDAP_TIMELIMIT_EXCEEDED
 
161
 *                      -5 -- admin limit exceeded       now is: LDAP_ADMINLIMIT_EXCEEDED
 
162
 *          -6 -- abandoned                  now is: LDAP_OTHER
 
163
 */
 
164
/* 
 
165
 * So here's the plan:
 
166
 * Plan A:  We do a regular quicksort on the entries.
 
167
 * Plan B:  Through some hint given us from on high, we
 
168
 *                      determine that the entries are _already_
 
169
 *                      sorted as requested, thus we do nothing !
 
170
 * Plan C:  We determine that sorting these suckers is
 
171
 *                      far too hard for us to even try, so we refuse.
 
172
 */
 
173
int sort_candidates(backend *be,int lookthrough_limit,time_t time_up, Slapi_PBlock *pb, 
 
174
                                        IDList  *candidates, sort_spec_thing *s, char **sort_error_type)
 
175
{
 
176
        int return_value = LDAP_SUCCESS;
 
177
        baggage_carrier bc = {0};
 
178
        sort_spec_thing *this_s = NULL;
 
179
 
 
180
        /* We refuse to sort a non-existent IDlist */
 
181
        if (NULL == candidates) {
 
182
                return LDAP_UNWILLING_TO_PERFORM;
 
183
        }
 
184
        /* we refuse to sort a candidate list which is vast */
 
185
        if (ALLIDS(candidates)) {
 
186
                LDAPDebug( LDAP_DEBUG_TRACE, "Asked to sort ALLIDS candidate list, refusing\n",0, 0, 0 );
 
187
                return LDAP_UNWILLING_TO_PERFORM;
 
188
        }
 
189
 
 
190
        /* Iterate over the sort types */
 
191
        for (this_s = s; this_s; this_s=this_s->next) {
 
192
                if (NULL == this_s->matchrule) {
 
193
                        int return_value = 0;
 
194
                        return_value = attr_get_value_cmp_fn( &this_s->sattr, &(this_s->compare_fn) );
 
195
                        if (return_value  != 0 ) {
 
196
                                LDAPDebug( LDAP_DEBUG_TRACE, "Attempting to sort a non-ordered attribute (%s)\n",this_s->type, 0, 0 );
 
197
                                /* DBDB we should set the error type here */
 
198
                                return_value = LDAP_UNWILLING_TO_PERFORM;
 
199
                                *sort_error_type = this_s->type;
 
200
                                return return_value;
 
201
                        }                       
 
202
                } else {
 
203
                        /* Need to---find the matching rule plugin, 
 
204
                         * tell it it needs to do ordering for this OID 
 
205
                         * see whether it agrees---if not signal error to client 
 
206
                         * Then later use it for generating ordering keys. 
 
207
                         * finally, free it up 
 
208
                         */
 
209
                        return_value = create_matchrule_indexer(&this_s->mr_pb,this_s->matchrule,this_s->type);
 
210
                        if (LDAP_SUCCESS != return_value) {
 
211
                                *sort_error_type = this_s->type;
 
212
                                return return_value;
 
213
                        }
 
214
                        this_s->compare_fn = slapi_berval_cmp; 
 
215
                }
 
216
        }
 
217
 
 
218
        bc.be = be; 
 
219
        bc.pb = pb; 
 
220
        bc.stoptime = time_up;
 
221
        bc.lookthrough_limit = lookthrough_limit;
 
222
        bc.check_counter = 1;
 
223
 
 
224
        return_value = slapd_qsort(&bc,candidates,s);
 
225
        LDAPDebug( LDAP_DEBUG_TRACE, "<= Sorting done\n",0, 0, 0 );
 
226
 
 
227
        return return_value;
 
228
}
 
229
/* End  fix for bug # 394184 */
 
230
 
 
231
static int term_tag(ber_tag_t tag)
 
232
{
 
233
        return ( (LBER_END_OF_SEQORSET == tag) || (LBER_ERROR == tag) );
 
234
}
 
235
 
 
236
/* hacky function to convert a sort spec to a string 
 
237
   you specify a buffer and a size. If the thing won't fit, it returns 
 
238
   non-zero, and the size needed. Pass NULL buffer to just get the size */
 
239
static int print_out_sort_spec(char* buffer,sort_spec *s,int *size)
 
240
{
 
241
        /* Walk down the list printing */
 
242
        sort_spec_thing *t = (sort_spec_thing*)s;
 
243
        sort_spec_thing *p = NULL;
 
244
        int buffer_size = 0;
 
245
        int input_size = 0;
 
246
 
 
247
        if (NULL != size) {
 
248
                input_size = *size;
 
249
        }
 
250
        do {
 
251
                p = t->next;
 
252
 
 
253
                buffer_size += strlen(t->type);
 
254
                if (t->order) {
 
255
                        buffer_size += 1; /* For the '-' */
 
256
                }
 
257
                if (NULL != t->matchrule) {
 
258
                        /* space for matchrule + semicolon */
 
259
                        buffer_size += strlen(t->matchrule) + 1;
 
260
                }
 
261
                buffer_size += 1; /* for the space */
 
262
                if ( (NULL != buffer) && (buffer_size <= input_size) ) {
 
263
                        /* write into the buffer */
 
264
                        buffer += sprintf(buffer,"%s%s%s%s ", 
 
265
                                t->order ? "-" : "",
 
266
                                t->type,
 
267
                                ( NULL == t->matchrule ) ? "" : ";",
 
268
                                ( NULL == t->matchrule ) ? "" : t->matchrule);
 
269
                }
 
270
 
 
271
                t = p;
 
272
        } while (p);
 
273
        if (NULL != size) {
 
274
                *size = buffer_size;
 
275
        }
 
276
        if (buffer_size <= input_size) {
 
277
                return 0;
 
278
        } else {
 
279
                return 1;
 
280
        }
 
281
}
 
282
 
 
283
int parse_sort_spec(struct berval *sort_spec_ber, sort_spec **ps)
 
284
{
 
285
        /* So here we call ber_scanf to get the sort spec */
 
286
        /* This control looks like this : 
 
287
     SortKeyList ::= SEQUENCE OF SEQUENCE {
 
288
                attributeType   AttributeType,
 
289
                orderingRule    [0] MatchingRuleId OPTIONAL,
 
290
                reverseOrder    [1] BOOLEAN DEFAULT FALSE }      
 
291
        */
 
292
        BerElement *ber = NULL;
 
293
        sort_spec_thing *listhead = NULL;
 
294
        ber_tag_t tag = 0;
 
295
        ber_len_t len = -1;
 
296
        char *last = NULL;
 
297
        sort_spec_thing *listpointer = NULL;
 
298
        char *type = NULL;
 
299
        char *matchrule = NULL;
 
300
        int rc = LDAP_SUCCESS;
 
301
 
 
302
        if (NULL == sort_spec_ber->bv_val) {
 
303
                return LDAP_PROTOCOL_ERROR;
 
304
        }
 
305
 
 
306
        ber = ber_init(sort_spec_ber);
 
307
    if(ber==NULL)
 
308
    {
 
309
        return -1;
 
310
    }
 
311
 
 
312
        /* Work our way along the BER, one sort spec at a time */
 
313
        for ( tag = ber_first_element( ber, &len, &last ); !term_tag(tag); tag = ber_next_element( ber, &len, last )) {
 
314
                /* we're now pointing at the beginning of a sequence of type, matching rule and reverse indicator */
 
315
 
 
316
                char *inner_last = NULL;
 
317
                char *rtype = NULL;
 
318
                int reverse = 0;
 
319
                ber_tag_t next_tag = 0;
 
320
                sort_spec_thing *s = NULL;
 
321
                ber_tag_t return_value;
 
322
 
 
323
                len = -1; /* reset - not used here */
 
324
                next_tag = ber_first_element( ber, &len, &inner_last );
 
325
 
 
326
                /* The type is not optional */
 
327
 
 
328
                return_value = ber_scanf(ber,"a",&rtype);
 
329
                if (LBER_ERROR == return_value) {
 
330
                        slapi_ch_free_string(&rtype);
 
331
                        rc = LDAP_PROTOCOL_ERROR;
 
332
                        goto err;
 
333
                }
 
334
                /* normalize */
 
335
                type = slapi_attr_syntax_normalize(rtype);
 
336
                slapi_ch_free_string(&rtype);
 
337
 
 
338
                /* Now look for the next tag. */
 
339
 
 
340
                len = -1; /* reset - not used here */
 
341
                next_tag = ber_next_element(ber,&len, inner_last);
 
342
 
 
343
                /* Are we done ? */
 
344
                if ( !term_tag(next_tag) ) { 
 
345
                        /* Is it the matching rule ? */
 
346
                        if (LDAP_TAG_SK_MATCHRULE == next_tag) {
 
347
                                /* If so, get it */
 
348
                                return_value = ber_scanf(ber,"a",&matchrule);
 
349
                                if (LBER_ERROR == return_value) {
 
350
                                        rc = LDAP_PROTOCOL_ERROR;
 
351
                                        goto err;
 
352
                                }
 
353
 
 
354
                                /* That can be followed by a reverse indicator */
 
355
                                len = -1; /* reset - not used here */
 
356
                                next_tag = ber_next_element(ber,&len, inner_last);
 
357
                                if (LDAP_TAG_SK_REVERSE == next_tag) {
 
358
                                        /* Get the reverse sort indicator here */
 
359
                                        return_value = ber_scanf(ber,"b",&reverse);
 
360
                                        /* The protocol police say--"You must have other than your default value" */
 
361
                                        if ((LBER_ERROR == return_value) || (0 == reverse)) {
 
362
                                                /* Protocol error */
 
363
                                                rc = LDAP_PROTOCOL_ERROR;
 
364
                                                goto err;
 
365
                                        }
 
366
                                } else {
 
367
                                        /* Perhaps we're done now ? */
 
368
                                        if ((LBER_END_OF_SEQORSET != next_tag) && (len != -1)) {
 
369
                                                /* Protocol error---we got a matching rule, but followed by something other 
 
370
                                                 * than reverse or end of sequence.
 
371
                                                 */
 
372
                                                rc = LDAP_PROTOCOL_ERROR;
 
373
                                                goto err;
 
374
                                        }
 
375
                                }
 
376
                        } else {
 
377
                                /* Is it the reverse indicator ? */
 
378
                                if (LDAP_TAG_SK_REVERSE == next_tag) {
 
379
                                        /* If so, get it */
 
380
                                        return_value = ber_scanf(ber,"b",&reverse);
 
381
                                        if (LBER_ERROR == return_value) {
 
382
                                                rc = LDAP_PROTOCOL_ERROR;
 
383
                                                goto err;
 
384
                                        }
 
385
                                } else {
 
386
                                        /* Protocol error---tag which isn't either of the legal ones came first */
 
387
                                        rc = LDAP_PROTOCOL_ERROR;
 
388
                                        goto err;
 
389
                                }
 
390
                        }
 
391
                }
 
392
 
 
393
                s = sort_spec_thing_new(type,matchrule,reverse);
 
394
                if (NULL == s) {
 
395
                        /* Memory allocation failed */
 
396
                        rc = LDAP_OPERATIONS_ERROR;
 
397
                        goto err;
 
398
                }
 
399
                type = matchrule = NULL;
 
400
                if (NULL != listpointer) {
 
401
                        listpointer->next = s;
 
402
                }
 
403
                listpointer = s;
 
404
                if (NULL == listhead) {
 
405
                        listhead = s;
 
406
                }
 
407
                len = -1; /* reset for next loop iter */
 
408
        }
 
409
 
 
410
        if (NULL == listhead) {  /* LP - defect #559792 - don't return null listhead */
 
411
                *ps = NULL;
 
412
                rc = LDAP_PROTOCOL_ERROR;
 
413
                goto err;
 
414
        }
 
415
 
 
416
        /* the ber encoding is no longer needed */
 
417
        ber_free(ber,1);
 
418
 
 
419
        *ps = (sort_spec *)listhead;
 
420
 
 
421
 
 
422
        return LDAP_SUCCESS;
 
423
 
 
424
 err: 
 
425
        if (listhead) sort_spec_free((sort_spec*) listhead);
 
426
        slapi_ch_free((void**)&type);
 
427
        slapi_ch_free((void**)&matchrule);
 
428
        ber_free(ber,1);
 
429
 
 
430
        return rc;
 
431
}
 
432
 
 
433
#if 0
 
434
static int attr_value_compare(struct berval *value_a, struct berval *value_b)
 
435
{
 
436
        /* return value_cmp(value_a,value_b,syntax,3); */
 
437
        return strcasecmp(value_a->bv_val, value_b->bv_val);
 
438
}
 
439
#endif
 
440
 
 
441
struct berval* attr_value_lowest(struct berval **values, value_compare_fn_type compare_fn)
 
442
{       
 
443
        /* We iterate through the values, storing our last best guess as to the lowest */
 
444
        struct berval *lowest_so_far = values[0];
 
445
        struct berval *this_one = NULL;
 
446
 
 
447
        for (this_one = *values; this_one; this_one = *values++) {
 
448
                if (compare_fn(lowest_so_far,this_one) > 0) {
 
449
                        lowest_so_far = this_one;
 
450
                }
 
451
        }
 
452
        return lowest_so_far;
 
453
}
 
454
 
 
455
int sort_attr_compare(struct berval ** value_a, struct berval ** value_b, value_compare_fn_type compare_fn)
 
456
{
 
457
        /* So, the thing we need to do here is to look out for multi-valued
 
458
         * attributes. When we get one of those, we need to look through all the 
 
459
         * values to find the lowest one (per X.511 edict). We then use that one to
 
460
         * compare against the other. We should really put some logic in here to
 
461
         * prevent us partying on an attribute with thousands of values for a long time.
 
462
         */
 
463
        struct berval *compare_value_a = NULL;
 
464
        struct berval *compare_value_b = NULL;
 
465
 
 
466
        compare_value_a = attr_value_lowest(value_a, compare_fn);
 
467
        compare_value_b = attr_value_lowest(value_b, compare_fn);
 
468
 
 
469
        return compare_fn(compare_value_a,compare_value_b);
 
470
 
 
471
}
 
472
 
 
473
 
 
474
#if 0
 
475
/* USE THE _SV VERSION NOW */
 
476
 
 
477
/* Comparison routine, called by qsort.
 
478
 * The job here is to return the correct value
 
479
 * for the operation a < b
 
480
 * Returns:
 
481
 * <0 when  a < b
 
482
 * 0  when a == b
 
483
 * >0 when a > b
 
484
 */
 
485
static int compare_entries(ID *id_a, ID *id_b, sort_spec *s,baggage_carrier *bc, int *error)
 
486
{
 
487
        /* We get passed the IDs, but need to fetch the entries in order to
 
488
         * perform the comparison .
 
489
         */
 
490
        struct backentry *a = NULL;
 
491
        struct backentry *b = NULL;
 
492
        int result = 0;
 
493
        sort_spec_thing *this_one = NULL;
 
494
        int return_value = -1;
 
495
        backend *be = bc->be;
 
496
        ldbm_instance *inst = (ldbm_instance *) be->be_instance_info;
 
497
        int err;
 
498
 
 
499
        *error = 1;
 
500
        a = id2entry(be,*id_a,NULL,&err);
 
501
        if (NULL == a) {
 
502
                if (0 != err ) {
 
503
                        LDAPDebug(LDAP_DEBUG_ANY,"compare_entries db err %d\n",err,0,0);
 
504
                }
 
505
                /* Were up a creek without paddle here */
 
506
                /* Best to log error and set some flag */
 
507
                return 0;
 
508
        }
 
509
        b = id2entry(be,*id_b,NULL,&err);
 
510
        if (NULL == b) {
 
511
                if (0 != err ) {
 
512
                        LDAPDebug(LDAP_DEBUG_ANY,"compare_entries db err %d\n",err,0,0);
 
513
                }
 
514
                return 0;
 
515
        }
 
516
        /* OK, now we have the entries, so we work our way down the attribute list comparing as we go */
 
517
        for (this_one = (sort_spec_thing*)s; this_one ; this_one = this_one->next) {
 
518
 
 
519
                char *type = this_one->type;
 
520
                int order = this_one->order;
 
521
                Slapi_Attr *attr_a = NULL;
 
522
                Slapi_Attr *attr_b = NULL;
 
523
                struct berval **value_a = NULL;
 
524
                struct berval **value_b = NULL;
 
525
 
 
526
                /* Get the two attribute values from the entries */
 
527
                return_value = slapi_entry_attr_find(a->ep_entry,type,&attr_a);
 
528
                return_value = slapi_entry_attr_find(b->ep_entry,type,&attr_b);
 
529
                /* What do we do if one or more of the entries lacks this attribute ? */
 
530
                /* if one lacks the attribute */
 
531
                if (NULL == attr_a) {
 
532
                        /* then if the other does too, they're equal */
 
533
                        if (NULL == attr_b) {
 
534
                                result = 0;
 
535
                                continue;
 
536
                        } else
 
537
                        {
 
538
                                /* If one has the attribute, and the other
 
539
                                 * doesn't, the missing attribute is the
 
540
                                 * LARGER one.  (bug #108154)  -robey
 
541
                                 */
 
542
                                result = 1;
 
543
                                break;
 
544
                        }
 
545
                }
 
546
                if (NULL == attr_b) {
 
547
                        result = -1;
 
548
                        break;
 
549
                }
 
550
                /* Somewhere in here, we need to go sideways for match rule case 
 
551
                 * we need to call the match rule plugin to get the attribute values
 
552
                 * converted into ordering keys. Then we proceed as usual to use those,
 
553
                 * but ensuring that we don't leak memory anywhere. This works as follows:
 
554
                 * the code assumes that the attrs are references into the entry, so 
 
555
                 * doesn't try to free them. We need to note at the right place that
 
556
                 * we're on the matchrule path, and accordingly free the keys---this turns out
 
557
                 * to be when we free the indexer */ 
 
558
                if (NULL == s->matchrule) {
 
559
                        /* Non-match rule case */
 
560
                    /* xxxPINAKI
 
561
                       needs modification
 
562
                       
 
563
                        value_a = attr_a->a_vals;
 
564
                        value_b = attr_b->a_vals;
 
565
                        */
 
566
                } else {
 
567
                        /* Match rule case */
 
568
                        struct berval **actual_value_b = NULL;
 
569
                        struct berval **temp_value = NULL;
 
570
 
 
571
                        /* xxxPINAKI
 
572
                           needs modification
 
573
                        struct berval **actual_value_a = NULL;
 
574
                           
 
575
                        actual_value_a = attr_a->a_vals;
 
576
                        actual_value_b = attr_b->a_vals;
 
577
                        matchrule_values_to_keys(s->mr_pb,actual_value_a,&temp_value);
 
578
                        */
 
579
                        /* Now copy it, so the second call doesn't crap on it */
 
580
                        value_a = slapi_ch_bvecdup(temp_value); /* Really, we'd prefer to not call the chXXX variant...*/
 
581
                        matchrule_values_to_keys(s->mr_pb,actual_value_b,&value_b);
 
582
                }
 
583
                /* Compare them */
 
584
                if (!order) {
 
585
                        result = sort_attr_compare(value_a, value_b, s->compare_fn);
 
586
                } else {
 
587
                        /* If reverse, invert the sense of the comparison */
 
588
                        result = sort_attr_compare(value_b, value_a, s->compare_fn);
 
589
                }
 
590
                /* Time to free up the attribute allocated above */
 
591
                if (NULL != s->matchrule) {
 
592
                        ber_bvecfree(value_a);
 
593
                }
 
594
                /* Are they equal ? */
 
595
                if (0 != result) {
 
596
                        /* If not, we're done */
 
597
                        break;
 
598
                } 
 
599
                /* If so, proceed to the next attribute for comparison */
 
600
        }
 
601
        CACHE_RETURN(&inst->inst_cache,&a);
 
602
        CACHE_RETURN(&inst->inst_cache,&b);
 
603
        *error = 0;
 
604
        return result;
 
605
}
 
606
#endif
 
607
 
 
608
/* Comparison routine, called by qsort.
 
609
 * The job here is to return the correct value
 
610
 * for the operation a < b
 
611
 * Returns:
 
612
 * <0 when  a < b
 
613
 * 0  when a == b
 
614
 * >0 when a > b
 
615
 */
 
616
static int compare_entries_sv(ID *id_a, ID *id_b, sort_spec *s,baggage_carrier *bc, int *error)
 
617
{
 
618
        /* We get passed the IDs, but need to fetch the entries in order to
 
619
         * perform the comparison .
 
620
         */
 
621
        struct backentry *a = NULL;
 
622
        struct backentry *b = NULL;
 
623
        int result = 0;
 
624
        sort_spec_thing *this_one = NULL;
 
625
        backend *be = bc->be;
 
626
        ldbm_instance *inst = (ldbm_instance *) be->be_instance_info;
 
627
        int err;
 
628
    back_txn txn = {NULL};
 
629
 
 
630
    slapi_pblock_get(bc->pb, SLAPI_TXN, &txn.back_txn_txn);
 
631
        *error = 1;
 
632
        a = id2entry(be,*id_a,&txn,&err);
 
633
        if (NULL == a) {
 
634
                if (0 != err ) {
 
635
                        LDAPDebug(LDAP_DEBUG_TRACE,"compare_entries db err %d\n",err,0,0);
 
636
                }
 
637
                /* Were up a creek without paddle here */
 
638
                /* Best to log error and set some flag */
 
639
                return 0;
 
640
        }
 
641
        b = id2entry(be,*id_b,&txn,&err);
 
642
        if (NULL == b) {
 
643
                if (0 != err ) {
 
644
                        LDAPDebug(LDAP_DEBUG_TRACE,"compare_entries db err %d\n",err,0,0);
 
645
                }
 
646
                CACHE_RETURN(&inst->inst_cache,&a);
 
647
                return 0;
 
648
        }
 
649
        /* OK, now we have the entries, so we work our way down the attribute list comparing as we go */
 
650
        for (this_one = (sort_spec_thing*)s; this_one ; this_one = this_one->next) {
 
651
 
 
652
                char *type = this_one->type;
 
653
                int order = this_one->order;
 
654
                Slapi_Attr *attr_a = NULL;
 
655
                Slapi_Attr *attr_b = NULL;
 
656
                struct berval **value_a = NULL;
 
657
                struct berval **value_b = NULL;
 
658
 
 
659
                /* Get the two attribute values from the entries */
 
660
                slapi_entry_attr_find(a->ep_entry,type,&attr_a);
 
661
                slapi_entry_attr_find(b->ep_entry,type,&attr_b);
 
662
                /* What do we do if one or more of the entries lacks this attribute ? */
 
663
                /* if one lacks the attribute */
 
664
                if (NULL == attr_a) {
 
665
                        /* then if the other does too, they're equal */
 
666
                        if (NULL == attr_b) {
 
667
                                result = 0;
 
668
                                continue;
 
669
                        } else
 
670
                        {
 
671
                                /* If one has the attribute, and the other
 
672
                                 * doesn't, the missing attribute is the
 
673
                                 * LARGER one.  (bug #108154)  -robey
 
674
                                 */
 
675
                                result = 1;
 
676
                                break;
 
677
                        }
 
678
                }
 
679
                if (NULL == attr_b) {
 
680
                        result = -1;
 
681
                        break;
 
682
                }
 
683
                /* Somewhere in here, we need to go sideways for match rule case 
 
684
                 * we need to call the match rule plugin to get the attribute values
 
685
                 * converted into ordering keys. Then we proceed as usual to use those,
 
686
                 * but ensuring that we don't leak memory anywhere. This works as follows:
 
687
                 * the code assumes that the attrs are references into the entry, so 
 
688
                 * doesn't try to free them. We need to note at the right place that
 
689
                 * we're on the matchrule path, and accordingly free the keys---this turns out
 
690
                 * to be when we free the indexer */ 
 
691
                if (NULL == s->matchrule) {
 
692
                        /* Non-match rule case */
 
693
                    valuearray_get_bervalarray(valueset_get_valuearray(&attr_a->a_present_values),&value_a);
 
694
                    valuearray_get_bervalarray(valueset_get_valuearray(&attr_b->a_present_values),&value_b);
 
695
                } else {
 
696
                        /* Match rule case */
 
697
                        struct berval **actual_value_a = NULL;
 
698
                        struct berval **actual_value_b = NULL;
 
699
                        struct berval **temp_value = NULL;
 
700
 
 
701
                        valuearray_get_bervalarray(valueset_get_valuearray(&attr_a->a_present_values),&actual_value_a);
 
702
                        valuearray_get_bervalarray(valueset_get_valuearray(&attr_b->a_present_values),&actual_value_b);
 
703
                        matchrule_values_to_keys(s->mr_pb,actual_value_a,&temp_value);
 
704
                        /* Now copy it, so the second call doesn't crap on it */
 
705
                        value_a = slapi_ch_bvecdup(temp_value); /* Really, we'd prefer to not call the chXXX variant...*/
 
706
                        matchrule_values_to_keys(s->mr_pb,actual_value_b,&value_b);
 
707
                        if (actual_value_a) ber_bvecfree(actual_value_a);
 
708
                        if (actual_value_b) ber_bvecfree(actual_value_b);
 
709
                }
 
710
                /* Compare them */
 
711
                if (!order) {
 
712
                        result = sort_attr_compare(value_a, value_b, s->compare_fn);
 
713
                } else {
 
714
                        /* If reverse, invert the sense of the comparison */
 
715
                        result = sort_attr_compare(value_b, value_a, s->compare_fn);
 
716
                }
 
717
                /* Time to free up the attributes allocated above */
 
718
                if (NULL != s->matchrule) {
 
719
                        ber_bvecfree(value_a);
 
720
                } else {
 
721
                        ber_bvecfree(value_a);
 
722
                        ber_bvecfree(value_b);
 
723
                }
 
724
                /* Are they equal ? */
 
725
                if (0 != result) {
 
726
                        /* If not, we're done */
 
727
                        break;
 
728
                } 
 
729
                /* If so, proceed to the next attribute for comparison */
 
730
        }
 
731
        CACHE_RETURN(&inst->inst_cache,&a);
 
732
        CACHE_RETURN(&inst->inst_cache,&b);
 
733
        *error = 0;
 
734
        return result;
 
735
}
 
736
 
 
737
/* Fix for bug # 394184, SD, 20 Jul 00 */
 
738
/* replace the hard coded return value by the appropriate LDAP error code */
 
739
/* 
 
740
 * Returns:
 
741
 *  0: Everything OK          now is: LDAP_SUCCESS (fix for bug #394184)
 
742
 * -1: A protocol error       now is: LDAP_PROTOCOL_ERROR 
 
743
 * -2: Too hard               now is: LDAP_UNWILLING_TO_PERFORM
 
744
 * -3: Operation error        now is: LDAP_OPERATIONS_ERROR
 
745
 * -4: Timeout                now is: LDAP_TIMELIMIT_EXCEEDED
 
746
 * -5: Admin limit exceeded   now is: LDAP_ADMINLIMIT_EXCEEDED
 
747
 * -6: Abandoned              now is: LDAP_OTHER
 
748
 */
 
749
static int sort_check(baggage_carrier *bc)
 
750
{
 
751
        time_t curtime = 0;
 
752
        /* check for abandon */
 
753
        if ( slapi_op_abandoned( bc->pb)) {
 
754
            return LDAP_OTHER;
 
755
        }
 
756
 
 
757
        /* Check to see if our journey is really necessary */
 
758
 
 
759
        if (0 == ((bc->check_counter)++ % CHECK_INTERVAL) ) {
 
760
 
 
761
                /* check time limit */
 
762
                curtime = current_time();
 
763
                if ( bc->stoptime != -1 && curtime > bc->stoptime ) {
 
764
                        return LDAP_TIMELIMIT_EXCEEDED;
 
765
                }
 
766
                        
 
767
                /* Fix for bugid #394184, SD, 05 Jul 00 */
 
768
                /*  not sure this is the appropriate place to do this;
 
769
                   since the entries are swaped in slapd_qsort, some of them are most
 
770
                   probably counted more than once */
 
771
                /* hence commenting out the following test and moving it into slapd_qsort */
 
772
                /* check lookthrough limit */
 
773
                /* if ( bc->lookthrough_limit != -1 && (bc->lookthrough_limit -= CHECK_INTERVAL) < 0 ) {
 
774
                   return LDAP_ADMINLIMIT_EXCEEDED;
 
775
                   } */
 
776
                /* end  for bugid  #394184 */
 
777
 
 
778
        }
 
779
        return LDAP_SUCCESS;
 
780
}
 
781
/* End fix for bug # 394184 */
 
782
 
 
783
/* prototypes for local routines */
 
784
static void  shortsort(baggage_carrier *bc,ID *lo, ID *hi,sort_spec *s );
 
785
static void      swap (ID *a,ID *b);
 
786
 
 
787
/* this parameter defines the cutoff between using quick sort and
 
788
   insertion sort for arrays; arrays with lengths shorter or equal to the
 
789
   below value use insertion sort */
 
790
 
 
791
#define CUTOFF 8            /* testing shows that this is good value */
 
792
 
 
793
 
 
794
/* Fix for bug # 394184, SD, 20 Jul 00 */
 
795
/* replace the hard coded return value by the appropriate LDAP error code */
 
796
/* Our qsort needs to police the client timeout and lookthrough limit ?
 
797
 * It knows how to compare entries, so we don't bother with all the void * stuff.
 
798
 */
 
799
/* 
 
800
 * Returns:
 
801
 *  0: Everything OK         now is: LDAP_SUCCESS (fix for bug #394184)
 
802
 * -1: A protocol error      now is: LDAP_PROTOCOL_ERROR
 
803
 * -2: Too hard              now is: LDAP_UNWILLING_TO_PERFORM 
 
804
 * -3: Operation error       now is: LDAP_OPERATIONS_ERROR
 
805
 * -4: Timeout               now is: LDAP_TIMELIMIT_EXCEEDED
 
806
 * -5: Admin limit exceeded  now is: LDAP_ADMINLIMIT_EXCEEDED
 
807
 * -6: Abandoned             now is: LDAP_OTHER
 
808
 */
 
809
static int  slapd_qsort(baggage_carrier *bc,IDList *list, sort_spec *s)
 
810
{
 
811
    ID *lo, *hi;              /* ends of sub-array currently sorting */
 
812
    ID *mid;                  /* points to middle of subarray */
 
813
    ID *loguy, *higuy;        /* traveling pointers for partition step */
 
814
    NIDS size;              /* size of the sub-array */
 
815
    ID *lostk[30], *histk[30];
 
816
    int stkptr;                 /* stack for saving sub-array to be processed */
 
817
        NIDS num = list->b_nids;
 
818
        int return_value = LDAP_SUCCESS;
 
819
        int error = 0;
 
820
 
 
821
    /* Note: the number of stack entries required is no more than
 
822
       1 + log2(size), so 30 is sufficient for any array */
 
823
    if (num < 2 )
 
824
        return LDAP_SUCCESS;                 /* nothing to do */
 
825
 
 
826
    stkptr = 0;                 /* initialize stack */
 
827
 
 
828
    lo = &(list->b_ids[0]);
 
829
    hi = &(list->b_ids[num-1]);        /* initialize limits */
 
830
 
 
831
        /* Fix for bugid #394184, SD, 20 Jul 00 */
 
832
        if ( bc->lookthrough_limit != -1 && ( bc->lookthrough_limit <= (int) list->b_nids) ) {
 
833
                return LDAP_ADMINLIMIT_EXCEEDED;
 
834
        } 
 
835
        /* end Fix for bugid #394184 */
 
836
 
 
837
    /* this entry point is for pseudo-recursion calling: setting
 
838
       lo and hi and jumping to here is like recursion, but stkptr is
 
839
       prserved, locals aren't, so we preserve stuff on the stack */
 
840
recurse:
 
841
 
 
842
    size = (hi - lo) + 1;        /* number of el's to sort */
 
843
 
 
844
    /* below a certain size, it is faster to use a O(n^2) sorting method */
 
845
    if (size <= CUTOFF) {
 
846
         shortsort(bc,lo, hi, s );
 
847
    }
 
848
    else {
 
849
        /* First we pick a partititioning element.  The efficiency of the
 
850
           algorithm demands that we find one that is approximately the
 
851
           median of the values, but also that we select one fast.  Using
 
852
           the first one produces bad performace if the array is already
 
853
           sorted, so we use the middle one, which would require a very
 
854
           wierdly arranged array for worst case performance.  Testing shows
 
855
           that a median-of-three algorithm does not, in general, increase
 
856
           performance. */
 
857
 
 
858
        mid = lo + (size / 2);      /* find middle element */
 
859
        swap(mid, lo);               /* swap it to beginning of array */
 
860
 
 
861
        /* We now wish to partition the array into three pieces, one
 
862
           consisiting of elements <= partition element, one of elements
 
863
           equal to the parition element, and one of element >= to it.  This
 
864
           is done below; comments indicate conditions established at every
 
865
           step. */
 
866
 
 
867
        loguy = lo;
 
868
        higuy = hi + 1;
 
869
 
 
870
        /* Note that higuy decreases and loguy increases on every iteration,
 
871
           so loop must terminate. */
 
872
        for (;;) {
 
873
            /* lo <= loguy < hi, lo < higuy <= hi + 1,
 
874
               A[i] <= A[lo] for lo <= i <= loguy,
 
875
               A[i] >= A[lo] for higuy <= i <= hi */
 
876
 
 
877
            do  {
 
878
                loguy ++;
 
879
            } while (loguy <= hi && compare_entries_sv(loguy, lo, s, bc, &error) <= 0);
 
880
 
 
881
            /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
 
882
               either loguy > hi or A[loguy] > A[lo] */
 
883
 
 
884
            do  {
 
885
                higuy --;
 
886
            } while (higuy > lo && compare_entries_sv(higuy, lo, s, bc, &error) >= 0);
 
887
 
 
888
            /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
 
889
               either higuy <= lo or A[higuy] < A[lo] */
 
890
 
 
891
            if (higuy < loguy)
 
892
                break;
 
893
 
 
894
            /* if loguy > hi or higuy <= lo, then we would have exited, so
 
895
               A[loguy] > A[lo], A[higuy] < A[lo],
 
896
               loguy < hi, highy > lo */
 
897
 
 
898
            swap(loguy, higuy);
 
899
 
 
900
                        /* Check admin and time limits here on the sort */
 
901
                        if ( LDAP_SUCCESS != (return_value = sort_check(bc)) )
 
902
                        {
 
903
                                return return_value;
 
904
                        }
 
905
 
 
906
            /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
 
907
               of loop is re-established */
 
908
        }
 
909
 
 
910
        /*     A[i] >= A[lo] for higuy < i <= hi,
 
911
               A[i] <= A[lo] for lo <= i < loguy,
 
912
               higuy < loguy, lo <= higuy <= hi
 
913
           implying:
 
914
               A[i] >= A[lo] for loguy <= i <= hi,
 
915
               A[i] <= A[lo] for lo <= i <= higuy,
 
916
               A[i] = A[lo] for higuy < i < loguy */
 
917
 
 
918
        swap(lo, higuy);     /* put partition element in place */
 
919
 
 
920
        /* OK, now we have the following:
 
921
              A[i] >= A[higuy] for loguy <= i <= hi,
 
922
              A[i] <= A[higuy] for lo <= i < higuy
 
923
              A[i] = A[lo] for higuy <= i < loguy    */
 
924
 
 
925
        /* We've finished the partition, now we want to sort the subarrays
 
926
           [lo, higuy-1] and [loguy, hi].
 
927
           We do the smaller one first to minimize stack usage.
 
928
           We only sort arrays of length 2 or more.*/
 
929
 
 
930
        if ( higuy - 1 - lo >= hi - loguy ) {
 
931
            if (lo + 1 < higuy) {
 
932
                lostk[stkptr] = lo;
 
933
                histk[stkptr] = higuy - 1;
 
934
                ++stkptr;
 
935
            }                           /* save big recursion for later */
 
936
 
 
937
            if (loguy < hi) {
 
938
                lo = loguy;
 
939
                goto recurse;           /* do small recursion */
 
940
            }
 
941
        }
 
942
        else {
 
943
            if (loguy < hi) {
 
944
                lostk[stkptr] = loguy;
 
945
                histk[stkptr] = hi;
 
946
                ++stkptr;               /* save big recursion for later */
 
947
            }
 
948
 
 
949
            if (lo + 1 < higuy) {
 
950
                hi = higuy - 1;
 
951
                goto recurse;           /* do small recursion */
 
952
            }
 
953
        }
 
954
    }
 
955
 
 
956
    /* We have sorted the array, except for any pending sorts on the stack.
 
957
       Check if there are any, and do them. */
 
958
 
 
959
    --stkptr;
 
960
    if (stkptr >= 0) {
 
961
        lo = lostk[stkptr];
 
962
        hi = histk[stkptr];
 
963
        goto recurse;           /* pop subarray from stack */
 
964
    }
 
965
    else
 
966
        return LDAP_SUCCESS;                 /* all subarrays done */
 
967
}
 
968
/* End  fix for bug # 394184 */
 
969
 
 
970
 
 
971
static void  shortsort (
 
972
        baggage_carrier *bc,
 
973
    ID *lo,
 
974
    ID *hi,
 
975
    sort_spec *s
 
976
    )
 
977
{
 
978
    ID *p, *max;
 
979
        int error = 0;
 
980
 
 
981
    /* Note: in assertions below, i and j are alway inside original bound of
 
982
       array to sort. */
 
983
 
 
984
    while (hi > lo) {
 
985
        /* A[i] <= A[j] for i <= j, j > hi */
 
986
        max = lo;
 
987
        for (p = lo+1; p <= hi; p++) {
 
988
            /* A[i] <= A[max] for lo <= i < p */
 
989
            if (compare_entries_sv(p,max,s,bc,&error) > 0) {
 
990
                max = p;
 
991
            }
 
992
            /* A[i] <= A[max] for lo <= i <= p */
 
993
        }
 
994
 
 
995
        /* A[i] <= A[max] for lo <= i <= hi */
 
996
 
 
997
        swap(max, hi);
 
998
 
 
999
        /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
 
1000
 
 
1001
        hi--;
 
1002
 
 
1003
        /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
 
1004
    }
 
1005
    /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
 
1006
       so array is sorted */
 
1007
}
 
1008
 
 
1009
static void swap (ID *a,ID *b)
 
1010
{
 
1011
        ID tmp;
 
1012
 
 
1013
    if ( a != b ) {
 
1014
                tmp = *a;
 
1015
                *a = *b;
 
1016
                *b = tmp;
 
1017
        }
 
1018
}
 
1019
 
 
1020