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