]> git.sur5r.net Git - openldap/blob - servers/slapd/mods.c
81b6930cbe6d3dba03a5bbe98ba57484511c61fa
[openldap] / servers / slapd / mods.c
1 /*
2  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
3  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
4  */
5 /*
6  * Copyright (c) 1995 Regents of the University of Michigan.
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms are permitted
10  * provided that this notice is preserved and that due credit is given
11  * to the University of Michigan at Ann Arbor. The name of the University
12  * may not be used to endorse or promote products derived from this
13  * software without specific prior written permission. This software
14  * is provided ``as is'' without express or implied warranty.
15  */
16
17 #include "portable.h"
18
19 #include "slap.h"
20
21 int
22 modify_check_duplicates(
23         AttributeDescription    *ad,
24         MatchingRule            *mr,
25         BerVarray               vals,
26         BerVarray               mods,
27         int                     permissive,
28         const char      **text,
29         char *textbuf, size_t textlen )
30 {
31         int             i, j, numvals = 0, nummods,
32                         rc = LDAP_SUCCESS, matched;
33         BerVarray       nvals = NULL, nmods = NULL;
34
35         /*
36          * FIXME: better do the following
37          * 
38          *   - count the existing values
39          *   - count the new values
40          *   
41          *   - if the existing values are less than the new ones {
42          *       - normalize all the existing values
43          *       - for each new value {
44          *           - normalize
45          *           - check with existing
46          *           - cross-check with already normalized new vals
47          *       }
48          *   } else {
49          *       - for each new value {
50          *           - normalize
51          *           - cross-check with already normalized new vals
52          *       }
53          *       - for each existing value {
54          *           - normalize
55          *           - check with already normalized new values
56          *       }
57          *   }
58          *
59          * The first case is good when adding a lot of new values,
60          * and significantly at first import of values (e.g. adding
61          * a new group); the latter case seems to be quite important
62          * as well, because it is likely to be the most frequently
63          * used when administering the entry.  The current 
64          * implementation will always normalize all the existing
65          * values before checking.  If there's no duplicate, the
66          * performances should not change; they will in case of error.
67          */
68
69         for ( nummods = 0; mods[ nummods ].bv_val != NULL; nummods++ )
70                 /* count new values */ ;
71
72         if ( vals ) {
73                 for ( numvals = 0; vals[ numvals ].bv_val != NULL; numvals++ )
74                         /* count existing values */ ;
75
76                 if ( numvals < nummods ) {
77                         nvals = SLAP_CALLOC( numvals + 1, sizeof( struct berval ) );
78                         if( nvals == NULL ) {
79 #ifdef NEW_LOGGING
80                                 LDAP_LOG( OPERATION, ERR,
81                                         "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
82 #else
83                                 Debug( LDAP_DEBUG_ANY, 
84                                         "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
85 #endif
86                                 goto return_results;
87                         }
88
89                         /* normalize the existing values first */
90                         for ( j = 0; vals[ j ].bv_val != NULL; j++ ) {
91                                 rc = value_normalize( ad, SLAP_MR_EQUALITY,
92                                         &vals[ j ], &nvals[ j ], text );
93
94                                 /* existing attribute values must normalize */
95                                 assert( rc == LDAP_SUCCESS );
96
97                                 if ( rc != LDAP_SUCCESS ) {
98                                         nvals[ j ].bv_val = NULL;
99                                         goto return_results;
100                                 }
101                         }
102                         nvals[ j ].bv_val = NULL;
103                 }
104         }
105
106         /*
107          * If the existing values are less than the new values,
108          * it is more convenient to normalize all the existing
109          * values and test each new value against them first,
110          * then to other already normalized values
111          */
112         nmods = SLAP_CALLOC( nummods + 1, sizeof( struct berval ) );
113         if ( nmods == NULL ) {
114 #ifdef NEW_LOGGING
115                 LDAP_LOG( OPERATION, ERR,
116                         "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
117 #else
118                 Debug( LDAP_DEBUG_ANY, 
119                         "modify_check_duplicates: SLAP_CALLOC failed", 0, 0, 0 );
120 #endif
121                 goto return_results;
122         }
123
124         for ( i = 0; mods[ i ].bv_val != NULL; i++ ) {
125                 rc = value_normalize( ad, SLAP_MR_EQUALITY,
126                         &mods[ i ], &nmods[ i ], text );
127
128                 if ( rc != LDAP_SUCCESS ) {
129                         nmods[ i ].bv_val = NULL;
130                         goto return_results;
131                 }
132
133                 if ( numvals > 0 && numvals < nummods ) {
134                         for ( matched = 0, j = 0; nvals[ j ].bv_val; j++ ) {
135                                 int match;
136
137                                 rc = (*mr->smr_match)( &match,
138                                         SLAP_MR_VALUE_SYNTAX_MATCH,
139                                         ad->ad_type->sat_syntax,
140                                         mr, &nmods[ i ], &nvals[ j ] );
141                                 if ( rc != LDAP_SUCCESS ) {
142                                         nmods[ i + 1 ].bv_val = NULL;
143                                         *text = textbuf;
144                                         snprintf( textbuf, textlen,
145                                                 "%s: matching rule failed",
146                                                 ad->ad_cname.bv_val );
147                                         goto return_results;
148                                 }
149
150                                 if ( match == 0 ) {
151                                         if ( permissive ) {
152                                                 matched++;
153                                                 continue;
154                                         }
155                                         *text = textbuf;
156                                         snprintf( textbuf, textlen,
157                                                 "%s: value #%d provided more than once",
158                                                 ad->ad_cname.bv_val, i );
159                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
160                                         nmods[ i + 1 ].bv_val = NULL;
161                                         goto return_results;
162                                 }
163                         }
164
165                         if ( permissive && matched == j ) {
166                                 nmods[ i + 1 ].bv_val = NULL;
167                                 rc = LDAP_TYPE_OR_VALUE_EXISTS;
168                                 goto return_results;
169                         }
170                 }
171         
172                 for ( matched = 0, j = 0; j < i; j++ ) {
173                         int match;
174
175                         rc = (*mr->smr_match)( &match,
176                                 SLAP_MR_VALUE_SYNTAX_MATCH,
177                                 ad->ad_type->sat_syntax,
178                                 mr, &nmods[ i ], &nmods[ j ] );
179                         if ( rc != LDAP_SUCCESS ) {
180                                 nmods[ i + 1 ].bv_val = NULL;
181                                 *text = textbuf;
182                                 snprintf( textbuf, textlen,
183                                         "%s: matching rule failed",
184                                         ad->ad_cname.bv_val );
185                                 goto return_results;
186                         }
187
188                         if ( match == 0 ) {
189                                 if ( permissive ) {
190                                         matched++;
191                                         continue;
192                                 }
193                                 *text = textbuf;
194                                 snprintf( textbuf, textlen,
195                                         "%s: value #%d provided more than once",
196                                         ad->ad_cname.bv_val, j );
197                                 rc = LDAP_TYPE_OR_VALUE_EXISTS;
198                                 nmods[ i + 1 ].bv_val = NULL;
199                                 goto return_results;
200                         }
201                 }
202
203                 if ( permissive && matched == j ) {
204                         nmods[ i + 1 ].bv_val = NULL;
205                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
206                         goto return_results;
207                 }
208         }
209         nmods[ i ].bv_val = NULL;
210
211         /*
212          * if new values are more than existing values, it is more
213          * convenient to normalize and check all new values first,
214          * then check each new value against existing values, which 
215          * can be normalized in place
216          */
217
218         if ( numvals >= nummods ) {
219                 for ( j = 0; vals[ j ].bv_val; j++ ) {
220                         struct berval   asserted;
221
222                         rc = value_normalize( ad, SLAP_MR_EQUALITY,
223                                 &vals[ j ], &asserted, text );
224
225                         if ( rc != LDAP_SUCCESS ) {
226                                 goto return_results;
227                         }
228
229                         for ( matched = 0, i = 0; nmods[ i ].bv_val; i++ ) {
230                                 int match;
231
232                                 rc = (*mr->smr_match)( &match,
233                                         SLAP_MR_VALUE_SYNTAX_MATCH,
234                                         ad->ad_type->sat_syntax,
235                                         mr, &nmods[ i ], &asserted );
236                                 if ( rc != LDAP_SUCCESS ) {
237                                         *text = textbuf;
238                                         snprintf( textbuf, textlen,
239                                                 "%s: matching rule failed",
240                                                 ad->ad_cname.bv_val );
241                                         goto return_results;
242                                 }
243
244                                 if ( match == 0 ) {
245                                         if ( permissive ) {
246                                                 matched++;
247                                                 continue;
248                                         }
249                                         *text = textbuf;
250                                         snprintf( textbuf, textlen,
251                                                 "%s: value #%d provided more than once",
252                                                 ad->ad_cname.bv_val, j );
253                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
254                                         goto return_results;
255                                 }
256                         }
257
258                         if ( permissive && matched == i ) {
259                                 rc = LDAP_TYPE_OR_VALUE_EXISTS;
260                                 goto return_results;
261                         }
262                 }
263         }
264
265 return_results:;
266         if ( nvals ) {
267                 ber_bvarray_free( nvals );
268         }
269         if ( nmods ) {
270                 ber_bvarray_free( nmods );
271         }
272
273         return rc;
274 }
275
276 int
277 modify_add_values(
278         Entry   *e,
279         Modification    *mod,
280         int     permissive,
281         const char      **text,
282         char *textbuf, size_t textlen
283 )
284 {
285         int             i, j;
286         int             matched;
287         Attribute       *a;
288         MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
289         const char *op;
290
291         switch( mod->sm_op ) {
292         case LDAP_MOD_ADD:
293                 op = "add";
294                 break;
295         case LDAP_MOD_REPLACE:
296                 op = "replace";
297                 break;
298         default:
299                 op = "?";
300                 assert( 0 );
301         }
302
303         a = attr_find( e->e_attrs, mod->sm_desc );
304
305         /*
306          * With permissive set, as long as the attribute being added
307          * has the same value(s?) as the existing attribute, then the
308          * modify will succeed.
309          */
310
311         /* check if the values we're adding already exist */
312         if( mr == NULL || !mr->smr_match ) {
313                 if ( a != NULL ) {
314                         /* do not allow add of additional attribute
315                                 if no equality rule exists */
316                         *text = textbuf;
317                         snprintf( textbuf, textlen,
318                                 "modify/%s: %s: no equality matching rule",
319                                 op, mod->sm_desc->ad_cname.bv_val );
320                         return LDAP_INAPPROPRIATE_MATCHING;
321                 }
322
323                 for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
324                         /* test asserted values against existing values */
325                         if( a ) {
326                                 for( matched = 0, j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
327                                         if ( bvmatch( &mod->sm_bvalues[i],
328                                                 &a->a_vals[j] ) ) {
329                                                 if ( permissive ) {
330                                                         matched++;
331                                                         continue;
332                                                 }
333                                                 /* value exists already */
334                                                 *text = textbuf;
335                                                 snprintf( textbuf, textlen,
336                                                         "modify/%s: %s: value #%i already exists",
337                                                         op, mod->sm_desc->ad_cname.bv_val, j );
338                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
339                                         }
340                                 }
341                                 if ( permissive && matched == j ) {
342                                         /* values already exist; do nothing */
343                                         return LDAP_SUCCESS;
344                                 }
345                         }
346
347                         /* test asserted values against themselves */
348                         for( j = 0; j < i; j++ ) {
349                                 if ( bvmatch( &mod->sm_bvalues[i],
350                                         &mod->sm_bvalues[j] ) ) {
351
352                                         /* value exists already */
353                                         *text = textbuf;
354                                         snprintf( textbuf, textlen,
355                                                 "modify/%s: %s: value #%i already exists",
356                                                 op, mod->sm_desc->ad_cname.bv_val, j );
357                                         return LDAP_TYPE_OR_VALUE_EXISTS;
358                                 }
359                         }
360                 }
361
362         } else {
363                 /*
364                  * The original code performs ( n ) normalizations 
365                  * and ( n * ( n - 1 ) / 2 ) matches, which hide
366                  * the same number of normalizations.  The new code
367                  * performs the same number of normalizations ( n )
368                  * and ( n * ( n - 1 ) / 2 ) mem compares, far less
369                  * expensive than an entire match, if a match is
370                  * equivalent to a normalization and a mem compare ...
371                  * 
372                  * This is far more memory expensive than the previous,
373                  * but it can heavily improve performances when big
374                  * chunks of data are added (typical example is a group
375                  * with thousands of DN-syntax members; on my system:
376                  * for members of 5-RDN DNs,
377
378                 members         orig            bvmatch (dirty) new
379                 1000            0m38.456s       0m0.553s        0m0.608s
380                 2000            2m33.341s       0m0.851s        0m1.003s
381
382                  * Moreover, 100 groups with 10000 members each were
383                  * added in 37m27.933s (an analogous LDIF file was
384                  * loaded into Active Directory in 38m28.682s, BTW).
385                  * 
386                  * Maybe we could switch to the new algorithm when
387                  * the number of values overcomes a given threshold?
388                  */
389
390                 int             rc;
391
392                 if ( mod->sm_bvalues[ 1 ].bv_val == 0 ) {
393                         if ( a != NULL ) {
394                                 struct berval   asserted;
395                                 int             i;
396
397                                 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
398                                         &mod->sm_bvalues[ 0 ], &asserted, text );
399
400                                 if ( rc != LDAP_SUCCESS ) {
401                                         return rc;
402                                 }
403
404                                 for ( matched = 0, i = 0; a->a_vals[ i ].bv_val; i++ ) {
405                                         int     match;
406
407                                         rc = value_match( &match, mod->sm_desc, mr,
408                                                 SLAP_MR_VALUE_SYNTAX_MATCH,
409                                                 &a->a_vals[ i ], &asserted, text );
410
411                                         if( rc == LDAP_SUCCESS && match == 0 ) {
412                                                 if ( permissive ) {
413                                                         matched++;
414                                                         continue;
415                                                 }
416                                                 free( asserted.bv_val );
417                                                 *text = textbuf;
418                                                 snprintf( textbuf, textlen,
419                                                         "modify/%s: %s: value #0 already exists",
420                                                         op, mod->sm_desc->ad_cname.bv_val, 0 );
421                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
422                                         }
423                                 }
424                                 if ( permissive && matched == i ) {
425                                         /* values already exist; do nothing */
426                                         return LDAP_SUCCESS;
427                                 }
428                         }
429
430                 } else {
431                         rc = modify_check_duplicates( mod->sm_desc, mr,
432                                         a ? a->a_vals : NULL, mod->sm_bvalues,
433                                         permissive,
434                                         text, textbuf, textlen );
435
436                         if ( permissive && rc == LDAP_TYPE_OR_VALUE_EXISTS ) {
437                                 return LDAP_SUCCESS;
438                         }
439
440                         if ( rc != LDAP_SUCCESS ) {
441                                 return rc;
442                         }
443                 }
444         }
445
446         /* no - add them */
447         if( attr_merge( e, mod->sm_desc, mod->sm_bvalues ) != 0 ) {
448                 /* this should return result of attr_merge */
449                 *text = textbuf;
450                 snprintf( textbuf, textlen,
451                         "modify/%s: %s: merge error",
452                         op, mod->sm_desc->ad_cname.bv_val );
453                 return LDAP_OTHER;
454         }
455
456         return LDAP_SUCCESS;
457 }
458
459 int
460 modify_delete_values(
461         Entry   *e,
462         Modification    *mod,
463         int     permissive,
464         const char      **text,
465         char *textbuf, size_t textlen
466 )
467 {
468         int             i, j, k, rc = LDAP_SUCCESS;
469         Attribute       *a;
470         MatchingRule    *mr = mod->sm_desc->ad_type->sat_equality;
471         BerVarray       nvals = NULL;
472         char            dummy = '\0';
473
474         /*
475          * If permissive is set, then the non-existence of an 
476          * attribute is not treated as an error.
477          */
478
479         /* delete the entire attribute */
480         if ( mod->sm_bvalues == NULL ) {
481                 rc = attr_delete( &e->e_attrs, mod->sm_desc );
482
483                 if( permissive ) {
484                         rc = LDAP_SUCCESS;
485                 } else if( rc != LDAP_SUCCESS ) {
486                         *text = textbuf;
487                         snprintf( textbuf, textlen,
488                                 "modify/delete: %s: no such attribute",
489                                 mod->sm_desc->ad_cname.bv_val );
490                         rc = LDAP_NO_SUCH_ATTRIBUTE;
491                 }
492                 return rc;
493         }
494
495         if( mr == NULL || !mr->smr_match ) {
496                 /* disallow specific attributes from being deleted if
497                         no equality rule */
498                 *text = textbuf;
499                 snprintf( textbuf, textlen,
500                         "modify/delete: %s: no equality matching rule",
501                         mod->sm_desc->ad_cname.bv_val );
502                 return LDAP_INAPPROPRIATE_MATCHING;
503         }
504
505         /* delete specific values - find the attribute first */
506         if ( (a = attr_find( e->e_attrs, mod->sm_desc )) == NULL ) {
507                 if( permissive ) {
508                         return LDAP_SUCCESS;
509                 }
510                 *text = textbuf;
511                 snprintf( textbuf, textlen,
512                         "modify/delete: %s: no such attribute",
513                         mod->sm_desc->ad_cname.bv_val );
514                 return LDAP_NO_SUCH_ATTRIBUTE;
515         }
516
517         /* find each value to delete */
518         for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ )
519                 /* count existing values */ ;
520
521         nvals = (BerVarray)SLAP_CALLOC( j + 1, sizeof ( struct berval ) );
522         if( nvals == NULL ) {
523 #ifdef NEW_LOGGING
524                 LDAP_LOG( OPERATION, ERR,
525                         "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
526 #else
527                 Debug( LDAP_DEBUG_ANY, 
528                         "modify_delete_values: SLAP_CALLOC failed", 0, 0, 0 );
529 #endif
530                                 goto return_results;
531         }
532
533         /* normalize existing values */
534         for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ ) {
535                 rc = value_normalize( a->a_desc, SLAP_MR_EQUALITY,
536                         &a->a_vals[ j ], &nvals[ j ], text );
537
538                 if ( rc != LDAP_SUCCESS ) {
539                         nvals[ j ].bv_val = NULL;
540                         goto return_results;
541                 }
542         }
543
544         for ( i = 0; mod->sm_bvalues[ i ].bv_val != NULL; i++ ) {
545                 struct  berval asserted;
546                 int     found = 0;
547
548                 /* normalize the value to be deleted */
549                 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
550                         &mod->sm_bvalues[ i ], &asserted, text );
551
552                 if( rc != LDAP_SUCCESS ) {
553                         goto return_results;
554                 }
555
556                 /* search it */
557                 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
558                         int match;
559
560                         if ( nvals[ j ].bv_val == &dummy ) {
561                                 continue;
562                         }
563
564                         rc = (*mr->smr_match)( &match,
565                                 SLAP_MR_VALUE_SYNTAX_MATCH,
566                                 a->a_desc->ad_type->sat_syntax,
567                                 mr, &nvals[ j ], &asserted );
568
569                         if ( rc != LDAP_SUCCESS ) {
570                                 free( asserted.bv_val );
571                                 *text = textbuf;
572                                 snprintf( textbuf, textlen,
573                                         "%s: matching rule failed",
574                                         mod->sm_desc->ad_cname.bv_val );
575                                 goto return_results;
576                         }
577
578                         if ( match != 0 ) {
579                                 continue;
580                         }
581
582                         found = 1;
583
584                         /* delete value and mark it as dummy */
585                         free( nvals[ j ].bv_val );
586                         nvals[ j ].bv_val = &dummy;
587
588                         break;
589                 }
590
591                 free( asserted.bv_val );
592
593                 if ( found == 0 ) {
594                         *text = textbuf;
595                         snprintf( textbuf, textlen,
596                                 "modify/delete: %s: no such value",
597                                 mod->sm_desc->ad_cname.bv_val );
598                         rc = LDAP_NO_SUCH_ATTRIBUTE;
599                         goto return_results;
600                 }
601         }
602
603         /* compact array skipping dummies */
604         for ( k = 0, j = 0; nvals[ k ].bv_val != NULL; j++, k++ ) {
605
606                 /* delete and skip dummies */ ;
607                 for ( ; nvals[ k ].bv_val == &dummy; k++ ) {
608                         free( a->a_vals[ k ].bv_val );
609                 }
610
611                 if ( j != k ) {
612                         a->a_vals[ j ] = a->a_vals[ k ];
613                 }
614
615                 if ( a->a_vals[ k ].bv_val == NULL ) {
616                         break;
617                 }
618         }
619         a->a_vals[ j ].bv_val = NULL;
620
621         assert( i == k - j );
622
623         /* if no values remain, delete the entire attribute */
624         if ( a->a_vals[0].bv_val == NULL ) {
625                 if ( attr_delete( &e->e_attrs, mod->sm_desc ) ) {
626                         *text = textbuf;
627                         snprintf( textbuf, textlen,
628                                 "modify/delete: %s: no such attribute",
629                                 mod->sm_desc->ad_cname.bv_val );
630                         rc = LDAP_NO_SUCH_ATTRIBUTE;
631                 }
632         }
633
634 return_results:;
635         if ( nvals ) {
636                 /* delete the remaining normalized values */
637                 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
638                         if ( nvals[ j ].bv_val != &dummy ) {
639                                 ber_memfree( nvals[ j ].bv_val );
640                         }
641                 }
642                 ber_memfree( nvals );
643         }
644
645         return rc;
646 }
647
648 int
649 modify_replace_values(
650         Entry   *e,
651         Modification    *mod,
652         int             permissive,
653         const char      **text,
654         char *textbuf, size_t textlen
655 )
656 {
657         (void) attr_delete( &e->e_attrs, mod->sm_desc );
658
659         if ( mod->sm_bvalues ) {
660                 return modify_add_values( e, mod, permissive, text, textbuf, textlen );
661         }
662
663         return LDAP_SUCCESS;
664 }
665
666 void
667 slap_mod_free(
668         Modification    *mod,
669         int                             freeit
670 )
671 {
672 #if 0
673         if ( mod->sm_type.bv_val)
674                 free( mod->sm_type.bv_val );
675 #endif
676         if ( mod->sm_bvalues != NULL )
677                 ber_bvarray_free( mod->sm_bvalues );
678
679         if( freeit )
680                 free( mod );
681 }
682
683 void
684 slap_mods_free(
685     Modifications       *ml
686 )
687 {
688         Modifications *next;
689
690         for ( ; ml != NULL; ml = next ) {
691                 next = ml->sml_next;
692
693                 slap_mod_free( &ml->sml_mod, 0 );
694                 free( ml );
695         }
696 }
697