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