git.sur5r.net Git - openldap/blob - servers/slapd/mods.c

   1 /*
   2  * Copyright 1998-2002 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 #undef QUICK_DIRTY_DUPLICATE_CHECK
  22
  23 int
  24 modify_check_duplicates(
  25         AttributeDescription    *ad,
  26         MatchingRule            *mr,
  27         BerVarray               vals,
  28         BerVarray               mods,
  29         const char      **text,
  30         char *textbuf, size_t textlen )
  31 {
  32         int             i, j, numvals = 0, nummods,
  33                         rc = LDAP_SUCCESS;
  34         BerVarray       nvals = NULL, nmods;
  35
  36         /*
  37          * FIXME: better do the following
  38          *
  39          *   - count the existing values
  40          *   - count the new values
  41          *
  42          *   - if the existing values are less than the new ones {
  43          *       - normalize all the existing values
  44          *       - for each new value {
  45          *           - normalize
  46          *           - check with existing
  47          *           - cross-check with already normalized new vals
  48          *       }
  49          *   } else {
  50          *       - for each new value {
  51          *           - normalize
  52          *           - cross-check with already normalized new vals
  53          *       }
  54          *       - for each existing value {
  55          *           - normalize
  56          *           - check with already normalized new values
  57          *       }
  58          *   }
  59          *
  60          * The first case is good when adding a lot of new values,
  61          * and significantly at first import of values (e.g. adding
  62          * a new group); the latter case seems to be quite important
  63          * as well, because it is likely to be the most frequently
  64          * used when administering the entry.  The current
  65          * implementation will always normalize all the existing
  66          * values before checking.  If there's no duplicate, the
  67          * performances should not change; they will in case of error.
  68          */
  69
  70         for ( nummods = 0; mods[ nummods ].bv_val != NULL; nummods++ )
  71                 /* count new values */ ;
  72
  73         if ( vals ) {
  74                 for ( numvals = 0; vals[ numvals ].bv_val != NULL; numvals++ )
  75                         /* count existing values */ ;
  76         }
  77
  78         if ( numvals > 0 && numvals < nummods ) {
  79                 nvals = ch_calloc( numvals + 1, sizeof( struct berval ) );
  80
  81                 /* normalize the existing values first */
  82                 for ( j = 0; vals[ j ].bv_val != NULL; j++ ) {
  83                         rc = value_normalize( ad, SLAP_MR_EQUALITY,
  84                                 &vals[ j ], &nvals[ j ], text );
  85
  86                         /* existing attribute values must normalize */
  87                         assert( rc == LDAP_SUCCESS );
  88
  89                         if ( rc != LDAP_SUCCESS ) {
  90                                 nvals[ j ].bv_val = NULL;
  91                                 goto return_results;
  92                         }
  93                 }
  94                 nvals[ j ].bv_val = NULL;
  95         }
  96
  97         /*
  98          * If the existing values are less than the new values,
  99          * it is more convenient to normalize all the existing
 100          * values and test each new value against them first,
 101          * then to other already normalized values
 102          */
 103         nmods = ch_calloc( nummods + 1, sizeof( struct berval ) );
 104
 105         for ( i = 0; mods[ i ].bv_val != NULL; i++ ) {
 106                 rc = value_normalize( ad, SLAP_MR_EQUALITY,
 107                         &mods[ i ], &nmods[ i ], text );
 108
 109                 if ( rc != LDAP_SUCCESS ) {
 110                         nmods[ i ].bv_val = NULL;
 111                         goto return_results;
 112                 }
 113
 114                 if ( numvals > 0 && numvals < nummods ) {
 115                         for ( j = 0; nvals[ j ].bv_val; j++ ) {
 116 #ifdef QUICK_DIRTY_DUPLICATE_CHECK
 117                                 if ( bvmatch( &nmods[ i ], &nvals[ j ] ) ) {
 118 #else /* !QUICK_DIRTY_DUPLICATE_CHECK */
 119                                 int match;
 120
 121                                 rc = (mr->smr_match)( &match,
 122                                         SLAP_MR_VALUE_SYNTAX_MATCH,
 123                                         ad->ad_type->sat_syntax,
 124                                         mr, &nmods[ i ], &nvals[ j ] );
 125                                 if ( rc != LDAP_SUCCESS ) {
 126                                         nmods[ i + 1 ].bv_val = NULL;
 127                                         goto return_results;
 128                                 }
 129
 130                                 if ( match == 0 ) {
 131 #endif /* !QUICK_DIRTY_DUPLICATE_CHECK */
 132                                         snprintf( textbuf, textlen,
 133                                                 "%s: value #%d provided more than once",
 134                                                 ad->ad_cname.bv_val, i );
 135                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
 136                                         nmods[ i + 1 ].bv_val = NULL;
 137                                         goto return_results;
 138                                 }
 139                         }
 140                 }
 141
 142                 for ( j = 0; j < i; j++ ) {
 143 #ifdef QUICK_DIRTY_DUPLICATE_CHECK
 144                         if ( bvmatch( &nmods[ i ], &nmods[ j ] ) ) {
 145 #else /* !QUICK_DIRTY_DUPLICATE_CHECK */
 146                         int match;
 147
 148                         rc = (mr->smr_match)( &match,
 149                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 150                                 ad->ad_type->sat_syntax,
 151                                 mr, &nmods[ i ], &nmods[ j ] );
 152                         if ( rc != LDAP_SUCCESS ) {
 153                                 nmods[ i + 1 ].bv_val = NULL;
 154                                 goto return_results;
 155                         }
 156
 157                         if ( match == 0 ) {
 158 #endif /* !QUICK_DIRTY_DUPLICATE_CHECK */
 159                                 snprintf( textbuf, textlen,
 160                                         "%s: value #%d provided more than once",
 161                                         ad->ad_cname.bv_val, j );
 162                                 rc = LDAP_TYPE_OR_VALUE_EXISTS;
 163                                 nmods[ i + 1 ].bv_val = NULL;
 164                                 goto return_results;
 165                         }
 166                 }
 167         }
 168         nmods[ i ].bv_val = NULL;
 169
 170         /*
 171          * if new values are more than existing values, it is more
 172          * convenient to normalize and check all new values first,
 173          * then check each new value against existing values, which
 174          * can be normalized in place
 175          */
 176
 177         if ( numvals >= nummods ) {
 178                 for ( j = 0; vals[ j ].bv_val; j++ ) {
 179                         struct berval   asserted;
 180
 181                         rc = value_normalize( ad, SLAP_MR_EQUALITY,
 182                                 &vals[ j ], &asserted, text );
 183
 184                         if ( rc != LDAP_SUCCESS ) {
 185                                 goto return_results;
 186                         }
 187
 188                         for ( i = 0; nmods[ i ].bv_val; i++ ) {
 189 #ifdef QUICK_DIRTY_DUPLICATE_CHECK
 190                                 if ( bvmatch( &nmods[ i ], &asserted ) ) {
 191 #else /* !QUICK_DIRTY_DUPLICATE_CHECK */
 192                                 int match;
 193
 194                                 rc = (mr->smr_match)( &match,
 195                                         SLAP_MR_VALUE_SYNTAX_MATCH,
 196                                         ad->ad_type->sat_syntax,
 197                                         mr, &nmods[ i ], &asserted );
 198                                 if ( rc != LDAP_SUCCESS ) {
 199                                         goto return_results;
 200                                 }
 201
 202                                 if ( match == 0 ) {
 203 #endif /* !QUICK_DIRTY_DUPLICATE_CHECK */
 204                                         snprintf( textbuf, textlen,
 205                                                 "%s: value #%d provided more than once",
 206                                                 ad->ad_cname.bv_val, j );
 207                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
 208                                         goto return_results;
 209                                 }
 210                         }
 211
 212                 }
 213         }
 214
 215 return_results:;
 216         if ( nvals ) {
 217                 ber_bvarray_free( nvals );
 218         }
 219         if ( nmods ) {
 220                 ber_bvarray_free( nmods );
 221         }
 222
 223         return rc;
 224 }
 225
 226 int
 227 modify_add_values(
 228         Entry   *e,
 229         Modification    *mod,
 230         const char      **text,
 231         char *textbuf, size_t textlen
 232 )
 233 {
 234         int             i, j;
 235         Attribute       *a;
 236         MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
 237         const char *op;
 238
 239         switch( mod->sm_op ) {
 240         case LDAP_MOD_ADD:
 241                 op = "add";
 242                 break;
 243         case LDAP_MOD_REPLACE:
 244                 op = "replace";
 245                 break;
 246         default:
 247                 op = "?";
 248                 assert( 0 );
 249         }
 250
 251         a = attr_find( e->e_attrs, mod->sm_desc );
 252
 253         /* check if the values we're adding already exist */
 254         if( mr == NULL || !mr->smr_match ) {
 255                 if ( a != NULL ) {
 256                         /* do not allow add of additional attribute
 257                                 if no equality rule exists */
 258                         *text = textbuf;
 259                         snprintf( textbuf, textlen,
 260                                 "modify/%s: %s: no equality matching rule",
 261                                 op, mod->sm_desc->ad_cname.bv_val );
 262                         return LDAP_INAPPROPRIATE_MATCHING;
 263                 }
 264
 265                 for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
 266                         /* test asserted values against existing values */
 267                         if( a ) {
 268                                 for( j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
 269                                         if ( bvmatch( &mod->sm_bvalues[i],
 270                                                 &a->a_vals[j] ) ) {
 271
 272                                                 /* value exists already */
 273                                                 *text = textbuf;
 274                                                 snprintf( textbuf, textlen,
 275                                                         "modify/%s: %s: value #%i already exists",
 276                                                         op, mod->sm_desc->ad_cname.bv_val, j );
 277                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
 278                                         }
 279                                 }
 280                         }
 281
 282                         /* test asserted values against themselves */
 283                         for( j = 0; j < i; j++ ) {
 284                                 if ( bvmatch( &mod->sm_bvalues[i],
 285                                         &mod->sm_bvalues[j] ) ) {
 286
 287                                         /* value exists already */
 288                                         *text = textbuf;
 289                                         snprintf( textbuf, textlen,
 290                                                 "modify/%s: %s: value #%i already exists",
 291                                                 op, mod->sm_desc->ad_cname.bv_val, j );
 292                                         return LDAP_TYPE_OR_VALUE_EXISTS;
 293                                 }
 294                         }
 295                 }
 296
 297         } else {
 298
 299                 /*
 300                  * The original code performs ( n ) normalizations
 301                  * and ( n * ( n - 1 ) / 2 ) matches, which hide
 302                  * the same number of normalizations.  The new code
 303                  * performs the same number of normalizations ( n )
 304                  * and ( n * ( n - 1 ) / 2 ) mem compares, far less
 305                  * expensive than an entire match, if a match is
 306                  * equivalent to a normalization and a mem compare ...
 307                  *
 308                  * This is far more memory expensive than the previous,
 309                  * but it can heavily improve performances when big
 310                  * chunks of data are added (typical example is a group
 311                  * with thousands of DN-syntax members; on my system:
 312                  * for members of 5-RDN DNs,
 313
 314                 members         orig            bvmatch (dirty) new
 315                 1000            0m38.456s       0m0.553s        0m0.608s
 316                 2000            2m33.341s       0m0.851s        0m1.003s
 317
 318                  * Moreover, 100 groups with 10000 members each were
 319                  * added in 37m27.933s (an analogous LDIF file was
 320                  * loaded into Active Directory in 38m28.682s, BTW).
 321                  *
 322                  * Maybe we could switch to the new algorithm when
 323                  * the number of values overcomes a given threshold?
 324                  */
 325
 326                 int             rc;
 327                 const char      *text = NULL;
 328                 char            textbuf[ SLAP_TEXT_BUFLEN ] = { '\0' };
 329
 330                 if ( mod->sm_bvalues[ 1 ].bv_val == 0 ) {
 331                         if ( a != NULL ) {
 332                                 struct berval   asserted;
 333                                 int             i;
 334
 335                                 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
 336                                         &mod->sm_bvalues[ 0 ], &asserted, &text );
 337
 338                                 if ( rc != LDAP_SUCCESS ) {
 339                                         return rc;
 340                                 }
 341
 342                                 for ( i = 0; a->a_vals[ i ].bv_val; i++ ) {
 343                                         int     match;
 344
 345                                         rc = value_match( &match, mod->sm_desc, mr,
 346                                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 347                                                 &a->a_vals[ i ], &asserted, &text );
 348
 349                                         if( rc == LDAP_SUCCESS && match == 0 ) {
 350                                                 free( asserted.bv_val );
 351                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
 352                                         }
 353                                 }
 354                         }
 355
 356                 } else {
 357                         rc = modify_check_duplicates( mod->sm_desc, mr,
 358                                         a ? a->a_vals : NULL, mod->sm_bvalues,
 359                                         &text, textbuf, sizeof( textbuf ) );
 360
 361                         if ( rc != LDAP_SUCCESS ) {
 362                                 return rc;
 363                         }
 364                 }
 365         }
 366
 367         /* no - add them */
 368         if( attr_merge( e, mod->sm_desc, mod->sm_bvalues ) != 0 ) {
 369                 /* this should return result of attr_merge */
 370                 *text = textbuf;
 371                 snprintf( textbuf, textlen,
 372                         "modify/%s: %s: merge error",
 373                         op, mod->sm_desc->ad_cname.bv_val );
 374                 return LDAP_OTHER;
 375         }
 376
 377         return LDAP_SUCCESS;
 378 }
 379
 380 int
 381 modify_delete_values(
 382         Entry   *e,
 383         Modification    *mod,
 384         const char      **text,
 385         char *textbuf, size_t textlen
 386 )
 387 {
 388         int             i, j, k, found;
 389         Attribute       *a;
 390         MatchingRule    *mr = mod->sm_desc->ad_type->sat_equality;
 391
 392         /* delete the entire attribute */
 393         if ( mod->sm_bvalues == NULL ) {
 394                 int rc = attr_delete( &e->e_attrs, mod->sm_desc );
 395
 396                 if( rc != LDAP_SUCCESS ) {
 397                         *text = textbuf;
 398                         snprintf( textbuf, textlen,
 399                                 "modify/delete: %s: no such attribute",
 400                                 mod->sm_desc->ad_cname.bv_val );
 401                         rc = LDAP_NO_SUCH_ATTRIBUTE;
 402                 }
 403                 return rc;
 404         }
 405
 406         if( mr == NULL || !mr->smr_match ) {
 407                 /* disallow specific attributes from being deleted if
 408                         no equality rule */
 409                 *text = textbuf;
 410                 snprintf( textbuf, textlen,
 411                         "modify/delete: %s: no equality matching rule",
 412                         mod->sm_desc->ad_cname.bv_val );
 413                 return LDAP_INAPPROPRIATE_MATCHING;
 414         }
 415
 416         /* delete specific values - find the attribute first */
 417         if ( (a = attr_find( e->e_attrs, mod->sm_desc )) == NULL ) {
 418                 *text = textbuf;
 419                 snprintf( textbuf, textlen,
 420                         "modify/delete: %s: no such attribute",
 421                         mod->sm_desc->ad_cname.bv_val );
 422                 return LDAP_NO_SUCH_ATTRIBUTE;
 423         }
 424
 425         /* find each value to delete
 426          *
 427          * FIXME: need to optimize this operation too,
 428          * see modify_check_duplicates()
 429          */
 430         for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
 431                 int rc;
 432                 struct berval asserted;
 433
 434                 rc = value_normalize( mod->sm_desc,
 435                         SLAP_MR_EQUALITY,
 436                         &mod->sm_bvalues[i],
 437                         &asserted,
 438                         text );
 439
 440                 if( rc != LDAP_SUCCESS ) return rc;
 441
 442                 found = 0;
 443                 for ( j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
 444                         int match;
 445                         int rc = value_match( &match, mod->sm_desc, mr,
 446                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 447                                 &a->a_vals[j], &asserted, text );
 448
 449                         if( rc == LDAP_SUCCESS && match != 0 ) {
 450                                 continue;
 451                         }
 452
 453                         /* found a matching value */
 454                         found = 1;
 455
 456                         /* delete it */
 457                         free( a->a_vals[j].bv_val );
 458                         for ( k = j + 1; a->a_vals[k].bv_val != NULL; k++ ) {
 459                                 a->a_vals[k - 1] = a->a_vals[k];
 460                         }
 461                         a->a_vals[k - 1].bv_val = NULL;
 462                         a->a_vals[k - 1].bv_len = 0;
 463
 464                         break;
 465                 }
 466
 467                 free( asserted.bv_val );
 468
 469                 /* looked through them all w/o finding it */
 470                 if ( ! found ) {
 471                         *text = textbuf;
 472                         snprintf( textbuf, textlen,
 473                                 "modify/delete: %s: no such value",
 474                                 mod->sm_desc->ad_cname.bv_val );
 475                         return LDAP_NO_SUCH_ATTRIBUTE;
 476                 }
 477         }
 478
 479         /* if no values remain, delete the entire attribute */
 480         if ( a->a_vals[0].bv_val == NULL ) {
 481                 if ( attr_delete( &e->e_attrs, mod->sm_desc ) ) {
 482                         *text = textbuf;
 483                         snprintf( textbuf, textlen,
 484                                 "modify/delete: %s: no such attribute",
 485                                 mod->sm_desc->ad_cname.bv_val );
 486                         return LDAP_NO_SUCH_ATTRIBUTE;
 487                 }
 488         }
 489
 490         return LDAP_SUCCESS;
 491 }
 492
 493 int
 494 modify_replace_values(
 495         Entry   *e,
 496         Modification    *mod,
 497         const char      **text,
 498         char *textbuf, size_t textlen
 499 )
 500 {
 501         (void) attr_delete( &e->e_attrs, mod->sm_desc );
 502
 503         if ( mod->sm_bvalues ) {
 504                 return modify_add_values( e, mod, text, textbuf, textlen );
 505         }
 506
 507         return LDAP_SUCCESS;
 508 }
 509
 510 void
 511 slap_mod_free(
 512         Modification    *mod,
 513         int                             freeit
 514 )
 515 {
 516 #if 0
 517         if ( mod->sm_type.bv_val)
 518                 free( mod->sm_type.bv_val );
 519 #endif
 520         if ( mod->sm_bvalues != NULL )
 521                 ber_bvarray_free( mod->sm_bvalues );
 522
 523         if( freeit )
 524                 free( mod );
 525 }
 526
 527 void
 528 slap_mods_free(
 529     Modifications       *ml
 530 )
 531 {
 532         Modifications *next;
 533
 534         for ( ; ml != NULL; ml = next ) {
 535                 next = ml->sml_next;
 536
 537                 slap_mod_free( &ml->sml_mod, 0 );
 538                 free( ml );
 539         }
 540 }
 541