1 /* valsort.c - sort attribute values */
2 /* $OpenLDAP$ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2005-2021 The OpenLDAP Foundation.
6 * Portions copyright 2005 Symas Corporation.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted only as authorized by the OpenLDAP
11 * Public License.
12 *
13 * A copy of this license is available in the file LICENSE in the
14 * top-level directory of the distribution or, alternatively, at
15 * <http://www.OpenLDAP.org/license.html>.
16 */
17 /* ACKNOWLEDGEMENTS:
18 * This work was initially developed by Howard Chu for inclusion in
19 * OpenLDAP Software. This work was sponsored by Stanford University.
20 */
21
22 /*
23 * This overlay sorts the values of multi-valued attributes when returning
24 * them in a search response.
25 */
26 #include "portable.h"
27
28 #ifdef SLAPD_OVER_VALSORT
29
30 #include <stdio.h>
31
32 #include <ac/string.h>
33 #include <ac/ctype.h>
34
35 #include "slap.h"
36 #include "config.h"
37 #include "lutil.h"
38
39 #define VALSORT_ASCEND 0
40 #define VALSORT_DESCEND 1
41
42 #define VALSORT_ALPHA 2
43 #define VALSORT_NUMERIC 4
44
45 #define VALSORT_WEIGHTED 8
46
47 typedef struct valsort_info {
48 struct valsort_info *vi_next;
49 struct berval vi_dn;
50 AttributeDescription *vi_ad;
51 slap_mask_t vi_sort;
52 } valsort_info;
53
54 static int valsort_cid;
55
56 static ConfigDriver valsort_cf_func;
57
58 static ConfigTable valsort_cfats[] = {
59 { "valsort-attr", "attribute> <dn> <sort-type", 4, 5, 0, ARG_MAGIC,
60 valsort_cf_func, "( OLcfgOvAt:5.1 NAME 'olcValSortAttr' "
61 "DESC 'Sorting rule for attribute under given DN' "
62 "EQUALITY caseIgnoreMatch "
63 "SYNTAX OMsDirectoryString )", NULL, NULL },
64 { NULL }
65 };
66
67 static ConfigOCs valsort_cfocs[] = {
68 { "( OLcfgOvOc:5.1 "
69 "NAME 'olcValSortConfig' "
70 "DESC 'Value Sorting configuration' "
71 "SUP olcOverlayConfig "
72 "MUST olcValSortAttr )",
73 Cft_Overlay, valsort_cfats },
74 { NULL }
75 };
76
77 static slap_verbmasks sorts[] = {
78 { BER_BVC("alpha-ascend"), VALSORT_ASCEND|VALSORT_ALPHA },
79 { BER_BVC("alpha-descend"), VALSORT_DESCEND|VALSORT_ALPHA },
80 { BER_BVC("numeric-ascend"), VALSORT_ASCEND|VALSORT_NUMERIC },
81 { BER_BVC("numeric-descend"), VALSORT_DESCEND|VALSORT_NUMERIC },
82 { BER_BVC("weighted"), VALSORT_WEIGHTED },
83 { BER_BVNULL, 0 }
84 };
85
86 static Syntax *syn_numericString;
87
88 static int
valsort_cf_func(ConfigArgs * c)89 valsort_cf_func(ConfigArgs *c) {
90 slap_overinst *on = (slap_overinst *)c->bi;
91 valsort_info vitmp, *vi;
92 const char *text = NULL;
93 int i, is_numeric;
94 struct berval bv = BER_BVNULL;
95
96 if ( c->op == SLAP_CONFIG_EMIT ) {
97 for ( vi = on->on_bi.bi_private; vi; vi = vi->vi_next ) {
98 struct berval bv2 = BER_BVNULL, bvret;
99 char *ptr;
100 int len;
101
102 len = vi->vi_ad->ad_cname.bv_len + 1 + vi->vi_dn.bv_len + 2;
103 i = vi->vi_sort;
104 if ( i & VALSORT_WEIGHTED ) {
105 enum_to_verb( sorts, VALSORT_WEIGHTED, &bv2 );
106 len += bv2.bv_len + 1;
107 i ^= VALSORT_WEIGHTED;
108 }
109 if ( i ) {
110 enum_to_verb( sorts, i, &bv );
111 len += bv.bv_len + 1;
112 }
113 bvret.bv_val = ch_malloc( len+1 );
114 bvret.bv_len = len;
115
116 ptr = lutil_strcopy( bvret.bv_val, vi->vi_ad->ad_cname.bv_val );
117 *ptr++ = ' ';
118 *ptr++ = '"';
119 ptr = lutil_strcopy( ptr, vi->vi_dn.bv_val );
120 *ptr++ = '"';
121 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
122 *ptr++ = ' ';
123 ptr = lutil_strcopy( ptr, bv2.bv_val );
124 }
125 if ( i ) {
126 *ptr++ = ' ';
127 strcpy( ptr, bv.bv_val );
128 }
129 ber_bvarray_add( &c->rvalue_vals, &bvret );
130 }
131 i = ( c->rvalue_vals != NULL ) ? 0 : 1;
132 return i;
133 } else if ( c->op == LDAP_MOD_DELETE ) {
134 if ( c->valx < 0 ) {
135 for ( vi = on->on_bi.bi_private; vi; vi = on->on_bi.bi_private ) {
136 on->on_bi.bi_private = vi->vi_next;
137 ch_free( vi->vi_dn.bv_val );
138 ch_free( vi );
139 }
140 } else {
141 valsort_info **prev;
142
143 for (i=0, prev = (valsort_info **)&on->on_bi.bi_private,
144 vi = *prev; vi && i<c->valx;
145 prev = &vi->vi_next, vi = vi->vi_next, i++ );
146 (*prev)->vi_next = vi->vi_next;
147 ch_free( vi->vi_dn.bv_val );
148 ch_free( vi );
149 }
150 return 0;
151 }
152 vitmp.vi_ad = NULL;
153 i = slap_str2ad( c->argv[1], &vitmp.vi_ad, &text );
154 if ( i ) {
155 snprintf( c->cr_msg, sizeof( c->cr_msg), "<%s> %s", c->argv[0], text );
156 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
157 c->log, c->cr_msg, c->argv[1] );
158 return(1);
159 }
160 if ( is_at_single_value( vitmp.vi_ad->ad_type )) {
161 snprintf( c->cr_msg, sizeof( c->cr_msg ), "<%s> %s is single-valued, ignoring", c->argv[0],
162 vitmp.vi_ad->ad_cname.bv_val );
163 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
164 c->log, c->cr_msg, c->argv[1] );
165 return(0);
166 }
167 is_numeric = ( vitmp.vi_ad->ad_type->sat_syntax == syn_numericString ||
168 vitmp.vi_ad->ad_type->sat_syntax == slap_schema.si_syn_integer ) ? 1
169 : 0;
170 ber_str2bv( c->argv[2], 0, 0, &bv );
171 i = dnNormalize( 0, NULL, NULL, &bv, &vitmp.vi_dn, NULL );
172 if ( i ) {
173 snprintf( c->cr_msg, sizeof( c->cr_msg ), "<%s> unable to normalize DN", c->argv[0] );
174 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
175 c->log, c->cr_msg, c->argv[2] );
176 return(1);
177 }
178 i = verb_to_mask( c->argv[3], sorts );
179 if ( BER_BVISNULL( &sorts[i].word )) {
180 snprintf( c->cr_msg, sizeof( c->cr_msg ), "<%s> unrecognized sort type", c->argv[0] );
181 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
182 c->log, c->cr_msg, c->argv[3] );
183 return(1);
184 }
185 vitmp.vi_sort = sorts[i].mask;
186 if ( sorts[i].mask == VALSORT_WEIGHTED && c->argc == 5 ) {
187 i = verb_to_mask( c->argv[4], sorts );
188 if ( BER_BVISNULL( &sorts[i].word )) {
189 snprintf( c->cr_msg, sizeof( c->cr_msg ), "<%s> unrecognized sort type", c->argv[0] );
190 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
191 c->log, c->cr_msg, c->argv[4] );
192 return(1);
193 }
194 vitmp.vi_sort |= sorts[i].mask;
195 }
196 if (( vitmp.vi_sort & VALSORT_NUMERIC ) && !is_numeric ) {
197 snprintf( c->cr_msg, sizeof( c->cr_msg ), "<%s> numeric sort specified for non-numeric syntax",
198 c->argv[0] );
199 Debug( LDAP_DEBUG_ANY, "%s: %s (%s)!\n",
200 c->log, c->cr_msg, c->argv[1] );
201 return(1);
202 }
203 vi = ch_malloc( sizeof(valsort_info) );
204 *vi = vitmp;
205 vi->vi_next = on->on_bi.bi_private;
206 on->on_bi.bi_private = vi;
207 return 0;
208 }
209
210 /* Use Insertion Sort algorithm on selected values */
211 static void
do_sort(Operation * op,Attribute * a,int beg,int num,slap_mask_t sort)212 do_sort( Operation *op, Attribute *a, int beg, int num, slap_mask_t sort )
213 {
214 int i, j, gotnvals;
215 struct berval tmp, ntmp, *vals = NULL, *nvals;
216
217 gotnvals = (a->a_vals != a->a_nvals );
218
219 nvals = a->a_nvals + beg;
220 if ( gotnvals )
221 vals = a->a_vals + beg;
222
223 if ( sort & VALSORT_NUMERIC ) {
224 long *numbers = op->o_tmpalloc( num * sizeof(long), op->o_tmpmemctx ),
225 idx;
226 for (i=0; i<num; i++)
227 numbers[i] = strtol( nvals[i].bv_val, NULL, 0 );
228
229 for (i=1; i<num; i++) {
230 idx = numbers[i];
231 ntmp = nvals[i];
232 if ( gotnvals ) tmp = vals[i];
233 j = i;
234 while ( j>0 ) {
235 int cmp = (sort & VALSORT_DESCEND) ? numbers[j-1] < idx :
236 numbers[j-1] > idx;
237 if ( !cmp ) break;
238 numbers[j] = numbers[j-1];
239 nvals[j] = nvals[j-1];
240 if ( gotnvals ) vals[j] = vals[j-1];
241 j--;
242 }
243 numbers[j] = idx;
244 nvals[j] = ntmp;
245 if ( gotnvals ) vals[j] = tmp;
246 }
247 op->o_tmpfree( numbers, op->o_tmpmemctx );
248 } else {
249 for (i=1; i<num; i++) {
250 ntmp = nvals[i];
251 if ( gotnvals ) tmp = vals[i];
252 j = i;
253 while ( j>0 ) {
254 int cmp = strcmp( nvals[j-1].bv_val, ntmp.bv_val );
255 cmp = (sort & VALSORT_DESCEND) ? (cmp < 0) : (cmp > 0);
256 if ( !cmp ) break;
257
258 nvals[j] = nvals[j-1];
259 if ( gotnvals ) vals[j] = vals[j-1];
260 j--;
261 }
262 nvals[j] = ntmp;
263 if ( gotnvals ) vals[j] = tmp;
264 }
265 }
266 }
267
268 static int
valsort_response(Operation * op,SlapReply * rs)269 valsort_response( Operation *op, SlapReply *rs )
270 {
271 slap_overinst *on;
272 valsort_info *vi;
273 Attribute *a;
274
275 /* If this is not a search response, or it is a syncrepl response,
276 * or the valsort control wants raw results, pass thru unmodified.
277 */
278 if ( rs->sr_type != REP_SEARCH ||
279 ( _SCM(op->o_sync) > SLAP_CONTROL_IGNORED ) ||
280 ( op->o_ctrlflag[valsort_cid] & SLAP_CONTROL_DATA0))
281 return SLAP_CB_CONTINUE;
282
283 on = (slap_overinst *) op->o_bd->bd_info;
284 vi = on->on_bi.bi_private;
285
286 /* And we must have something configured */
287 if ( !vi ) return SLAP_CB_CONTINUE;
288
289 /* Find a rule whose baseDN matches this entry */
290 for (; vi; vi = vi->vi_next ) {
291 int i, n;
292
293 if ( !dnIsSuffix( &rs->sr_entry->e_nname, &vi->vi_dn ))
294 continue;
295
296 /* Find attr that this rule affects */
297 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
298 if ( !a ) continue;
299
300 if ( rs_entry2modifiable( op, rs, on )) {
301 a = attr_find( rs->sr_entry->e_attrs, vi->vi_ad );
302 }
303
304 n = a->a_numvals;
305 if ( vi->vi_sort & VALSORT_WEIGHTED ) {
306 int j, gotnvals;
307 long *index = op->o_tmpalloc( n * sizeof(long), op->o_tmpmemctx );
308
309 gotnvals = (a->a_vals != a->a_nvals );
310
311 for (i=0; i<n; i++) {
312 char *ptr = ber_bvchr( &a->a_nvals[i], '{' );
313 char *end = NULL;
314 if ( !ptr ) {
315 Debug(LDAP_DEBUG_TRACE, "weights missing from attr %s "
316 "in entry %s\n", vi->vi_ad->ad_cname.bv_val,
317 rs->sr_entry->e_name.bv_val, 0 );
318 break;
319 }
320 index[i] = strtol( ptr+1, &end, 0 );
321 if ( *end != '}' ) {
322 Debug(LDAP_DEBUG_TRACE, "weights misformatted "
323 "in entry %s\n",
324 rs->sr_entry->e_name.bv_val, 0, 0 );
325 break;
326 }
327 /* Strip out weights */
328 ptr = a->a_nvals[i].bv_val;
329 end++;
330 for (;*end;)
331 *ptr++ = *end++;
332 *ptr = '\0';
333 a->a_nvals[i].bv_len = ptr - a->a_nvals[i].bv_val;
334
335 if ( a->a_vals != a->a_nvals ) {
336 ptr = a->a_vals[i].bv_val;
337 end = ber_bvchr( &a->a_vals[i], '}' );
338 assert( end != NULL );
339 end++;
340 for (;*end;)
341 *ptr++ = *end++;
342 *ptr = '\0';
343 a->a_vals[i].bv_len = ptr - a->a_vals[i].bv_val;
344 }
345 }
346 /* An attr was missing weights here, ignore it */
347 if ( i<n ) {
348 op->o_tmpfree( index, op->o_tmpmemctx );
349 continue;
350 }
351 /* Insertion sort */
352 for ( i=1; i<n; i++) {
353 long idx = index[i];
354 struct berval tmp = a->a_vals[i], ntmp;
355 if ( gotnvals ) ntmp = a->a_nvals[i];
356 j = i;
357 while (( j>0 ) && (index[j-1] > idx )) {
358 index[j] = index[j-1];
359 a->a_vals[j] = a->a_vals[j-1];
360 if ( gotnvals ) a->a_nvals[j] = a->a_nvals[j-1];
361 j--;
362 }
363 index[j] = idx;
364 a->a_vals[j] = tmp;
365 if ( gotnvals ) a->a_nvals[j] = ntmp;
366 }
367 /* Check for secondary sort */
368 if ( vi->vi_sort ^ VALSORT_WEIGHTED ) {
369 for ( i=0; i<n;) {
370 for (j=i+1; j<n; j++) {
371 if (index[i] != index[j])
372 break;
373 }
374 if( j-i > 1 )
375 do_sort( op, a, i, j-i, vi->vi_sort );
376 i = j;
377 }
378 }
379 op->o_tmpfree( index, op->o_tmpmemctx );
380 } else {
381 do_sort( op, a, 0, n, vi->vi_sort );
382 }
383 }
384 return SLAP_CB_CONTINUE;
385 }
386
387 static int
valsort_add(Operation * op,SlapReply * rs)388 valsort_add( Operation *op, SlapReply *rs )
389 {
390 slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
391 valsort_info *vi = on->on_bi.bi_private;
392
393 Attribute *a;
394 int i;
395 char *ptr, *end;
396
397 /* See if any weighted sorting applies to this entry */
398 for ( ;vi;vi=vi->vi_next ) {
399 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
400 continue;
401 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
402 continue;
403 a = attr_find( op->ora_e->e_attrs, vi->vi_ad );
404 if ( !a )
405 continue;
406 for (i=0; !BER_BVISNULL( &a->a_vals[i] ); i++) {
407 ptr = ber_bvchr(&a->a_vals[i], '{' );
408 if ( !ptr ) {
409 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
410 vi->vi_ad->ad_cname.bv_val, 0, 0);
411 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
412 "weight missing from attribute" );
413 return rs->sr_err;
414 }
415 strtol( ptr+1, &end, 0 );
416 if ( *end != '}' ) {
417 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
418 vi->vi_ad->ad_cname.bv_val, 0, 0);
419 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
420 "weight is misformatted" );
421 return rs->sr_err;
422 }
423 }
424 }
425 return SLAP_CB_CONTINUE;
426 }
427
428 static int
valsort_modify(Operation * op,SlapReply * rs)429 valsort_modify( Operation *op, SlapReply *rs )
430 {
431 slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
432 valsort_info *vi = on->on_bi.bi_private;
433
434 Modifications *ml;
435 int i;
436 char *ptr, *end;
437
438 /* See if any weighted sorting applies to this entry */
439 for ( ;vi;vi=vi->vi_next ) {
440 if ( !dnIsSuffix( &op->o_req_ndn, &vi->vi_dn ))
441 continue;
442 if ( !(vi->vi_sort & VALSORT_WEIGHTED ))
443 continue;
444 for (ml = op->orm_modlist; ml; ml=ml->sml_next ) {
445 /* Must be a Delete Attr op, so no values to consider */
446 if ( !ml->sml_values )
447 continue;
448 if ( ml->sml_desc == vi->vi_ad )
449 break;
450 }
451 if ( !ml )
452 continue;
453 for (i=0; !BER_BVISNULL( &ml->sml_values[i] ); i++) {
454 ptr = ber_bvchr(&ml->sml_values[i], '{' );
455 if ( !ptr ) {
456 Debug(LDAP_DEBUG_TRACE, "weight missing from attribute %s\n",
457 vi->vi_ad->ad_cname.bv_val, 0, 0);
458 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
459 "weight missing from attribute" );
460 return rs->sr_err;
461 }
462 strtol( ptr+1, &end, 0 );
463 if ( *end != '}' ) {
464 Debug(LDAP_DEBUG_TRACE, "weight is misformatted in %s\n",
465 vi->vi_ad->ad_cname.bv_val, 0, 0);
466 send_ldap_error( op, rs, LDAP_CONSTRAINT_VIOLATION,
467 "weight is misformatted" );
468 return rs->sr_err;
469 }
470 }
471 }
472 return SLAP_CB_CONTINUE;
473 }
474
475 static int
valsort_db_open(BackendDB * be,ConfigReply * cr)476 valsort_db_open(
477 BackendDB *be,
478 ConfigReply *cr
479 )
480 {
481 return overlay_register_control( be, LDAP_CONTROL_VALSORT );
482 }
483
484 static int
valsort_destroy(BackendDB * be,ConfigReply * cr)485 valsort_destroy(
486 BackendDB *be,
487 ConfigReply *cr
488 )
489 {
490 slap_overinst *on = (slap_overinst *)be->bd_info;
491 valsort_info *vi = on->on_bi.bi_private, *next;
492
493 #ifdef SLAP_CONFIG_DELETE
494 overlay_unregister_control( be, LDAP_CONTROL_VALSORT );
495 #endif /* SLAP_CONFIG_DELETE */
496
497 for (; vi; vi = next) {
498 next = vi->vi_next;
499 ch_free( vi->vi_dn.bv_val );
500 ch_free( vi );
501 }
502
503 return 0;
504 }
505
506 static int
valsort_parseCtrl(Operation * op,SlapReply * rs,LDAPControl * ctrl)507 valsort_parseCtrl(
508 Operation *op,
509 SlapReply *rs,
510 LDAPControl *ctrl )
511 {
512 ber_tag_t tag;
513 BerElementBuffer berbuf;
514 BerElement *ber = (BerElement *)&berbuf;
515 ber_int_t flag = 0;
516
517 if ( BER_BVISNULL( &ctrl->ldctl_value )) {
518 rs->sr_text = "valSort control value is absent";
519 return LDAP_PROTOCOL_ERROR;
520 }
521
522 if ( BER_BVISEMPTY( &ctrl->ldctl_value )) {
523 rs->sr_text = "valSort control value is empty";
524 return LDAP_PROTOCOL_ERROR;
525 }
526
527 ber_init2( ber, &ctrl->ldctl_value, 0 );
528 if (( tag = ber_scanf( ber, "{b}", &flag )) == LBER_ERROR ) {
529 rs->sr_text = "valSort control: flag decoding error";
530 return LDAP_PROTOCOL_ERROR;
531 }
532
533 op->o_ctrlflag[valsort_cid] = ctrl->ldctl_iscritical ?
534 SLAP_CONTROL_CRITICAL : SLAP_CONTROL_NONCRITICAL;
535 if ( flag )
536 op->o_ctrlflag[valsort_cid] |= SLAP_CONTROL_DATA0;
537
538 return LDAP_SUCCESS;
539 }
540
541 static slap_overinst valsort;
542
valsort_initialize(void)543 int valsort_initialize( void )
544 {
545 int rc;
546
547 valsort.on_bi.bi_type = "valsort";
548 valsort.on_bi.bi_db_destroy = valsort_destroy;
549 valsort.on_bi.bi_db_open = valsort_db_open;
550
551 valsort.on_bi.bi_op_add = valsort_add;
552 valsort.on_bi.bi_op_modify = valsort_modify;
553
554 valsort.on_response = valsort_response;
555
556 valsort.on_bi.bi_cf_ocs = valsort_cfocs;
557
558 rc = register_supported_control( LDAP_CONTROL_VALSORT,
559 SLAP_CTRL_SEARCH | SLAP_CTRL_HIDE, NULL, valsort_parseCtrl,
560 &valsort_cid );
561 if ( rc != LDAP_SUCCESS ) {
562 Debug( LDAP_DEBUG_ANY, "Failed to register control %d\n", rc, 0, 0 );
563 return rc;
564 }
565
566 syn_numericString = syn_find( "1.3.6.1.4.1.1466.115.121.1.36" );
567
568 rc = config_register_schema( valsort_cfats, valsort_cfocs );
569 if ( rc ) return rc;
570
571 return overlay_register(&valsort);
572 }
573
574 #if SLAPD_OVER_VALSORT == SLAPD_MOD_DYNAMIC
init_module(int argc,char * argv[])575 int init_module( int argc, char *argv[]) {
576 return valsort_initialize();
577 }
578 #endif
579
580 #endif /* SLAPD_OVER_VALSORT */
581