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;
  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 = ch_calloc( numvals + 1, sizeof( struct berval ) );
  77
  78                         /* normalize the existing values first */
  79                         for ( j = 0; vals[ j ].bv_val != NULL; j++ ) {
  80                                 rc = value_normalize( ad, SLAP_MR_EQUALITY,
  81                                         &vals[ j ], &nvals[ j ], text );
  82
  83                                 /* existing attribute values must normalize */
  84                                 assert( rc == LDAP_SUCCESS );
  85
  86                                 if ( rc != LDAP_SUCCESS ) {
  87                                         nvals[ j ].bv_val = NULL;
  88                                         goto return_results;
  89                                 }
  90                         }
  91                         nvals[ j ].bv_val = NULL;
  92                 }
  93         }
  94
  95         /*
  96          * If the existing values are less than the new values,
  97          * it is more convenient to normalize all the existing
  98          * values and test each new value against them first,
  99          * then to other already normalized values
 100          */
 101         nmods = ch_calloc( nummods + 1, sizeof( struct berval ) );
 102
 103         for ( i = 0; mods[ i ].bv_val != NULL; i++ ) {
 104                 rc = value_normalize( ad, SLAP_MR_EQUALITY,
 105                         &mods[ i ], &nmods[ i ], text );
 106
 107                 if ( rc != LDAP_SUCCESS ) {
 108                         nmods[ i ].bv_val = NULL;
 109                         goto return_results;
 110                 }
 111
 112                 if ( numvals > 0 && numvals < nummods ) {
 113                         for ( j = 0; nvals[ j ].bv_val; j++ ) {
 114                                 int match;
 115
 116                                 rc = (*mr->smr_match)( &match,
 117                                         SLAP_MR_VALUE_SYNTAX_MATCH,
 118                                         ad->ad_type->sat_syntax,
 119                                         mr, &nmods[ i ], &nvals[ j ] );
 120                                 if ( rc != LDAP_SUCCESS ) {
 121                                         nmods[ i + 1 ].bv_val = NULL;
 122                                         *text = textbuf;
 123                                         snprintf( textbuf, textlen,
 124                                                 "%s: matching rule failed",
 125                                                 ad->ad_cname.bv_val );
 126                                         goto return_results;
 127                                 }
 128
 129                                 if ( match == 0 ) {
 130                                         *text = textbuf;
 131                                         snprintf( textbuf, textlen,
 132                                                 "%s: value #%d provided more than once",
 133                                                 ad->ad_cname.bv_val, i );
 134                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
 135                                         nmods[ i + 1 ].bv_val = NULL;
 136                                         goto return_results;
 137                                 }
 138                         }
 139                 }
 140
 141                 for ( j = 0; j < i; j++ ) {
 142                         int match;
 143
 144                         rc = (*mr->smr_match)( &match,
 145                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 146                                 ad->ad_type->sat_syntax,
 147                                 mr, &nmods[ i ], &nmods[ j ] );
 148                         if ( rc != LDAP_SUCCESS ) {
 149                                 nmods[ i + 1 ].bv_val = NULL;
 150                                 *text = textbuf;
 151                                 snprintf( textbuf, textlen,
 152                                         "%s: matching rule failed",
 153                                         ad->ad_cname.bv_val );
 154                                 goto return_results;
 155                         }
 156
 157                         if ( match == 0 ) {
 158                                 *text = textbuf;
 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                                 int match;
 190
 191                                 rc = (*mr->smr_match)( &match,
 192                                         SLAP_MR_VALUE_SYNTAX_MATCH,
 193                                         ad->ad_type->sat_syntax,
 194                                         mr, &nmods[ i ], &asserted );
 195                                 if ( rc != LDAP_SUCCESS ) {
 196                                         *text = textbuf;
 197                                         snprintf( textbuf, textlen,
 198                                                 "%s: matching rule failed",
 199                                                 ad->ad_cname.bv_val );
 200                                         goto return_results;
 201                                 }
 202
 203                                 if ( match == 0 ) {
 204                                         *text = textbuf;
 205                                         snprintf( textbuf, textlen,
 206                                                 "%s: value #%d provided more than once",
 207                                                 ad->ad_cname.bv_val, j );
 208                                         rc = LDAP_TYPE_OR_VALUE_EXISTS;
 209                                         goto return_results;
 210                                 }
 211                         }
 212
 213                 }
 214         }
 215
 216 return_results:;
 217         if ( nvals ) {
 218                 ber_bvarray_free( nvals );
 219         }
 220         if ( nmods ) {
 221                 ber_bvarray_free( nmods );
 222         }
 223
 224         return rc;
 225 }
 226
 227 int
 228 modify_add_values(
 229         Entry   *e,
 230         Modification    *mod,
 231         const char      **text,
 232         char *textbuf, size_t textlen
 233 )
 234 {
 235         int             i, j;
 236         Attribute       *a;
 237         MatchingRule *mr = mod->sm_desc->ad_type->sat_equality;
 238         const char *op;
 239
 240         switch( mod->sm_op ) {
 241         case LDAP_MOD_ADD:
 242                 op = "add";
 243                 break;
 244         case LDAP_MOD_REPLACE:
 245                 op = "replace";
 246                 break;
 247         default:
 248                 op = "?";
 249                 assert( 0 );
 250         }
 251
 252         a = attr_find( e->e_attrs, mod->sm_desc );
 253
 254         /* check if the values we're adding already exist */
 255         if( mr == NULL || !mr->smr_match ) {
 256                 if ( a != NULL ) {
 257                         /* do not allow add of additional attribute
 258                                 if no equality rule exists */
 259                         *text = textbuf;
 260                         snprintf( textbuf, textlen,
 261                                 "modify/%s: %s: no equality matching rule",
 262                                 op, mod->sm_desc->ad_cname.bv_val );
 263                         return LDAP_INAPPROPRIATE_MATCHING;
 264                 }
 265
 266                 for ( i = 0; mod->sm_bvalues[i].bv_val != NULL; i++ ) {
 267                         /* test asserted values against existing values */
 268                         if( a ) {
 269                                 for( j = 0; a->a_vals[j].bv_val != NULL; j++ ) {
 270                                         if ( bvmatch( &mod->sm_bvalues[i],
 271                                                 &a->a_vals[j] ) ) {
 272
 273                                                 /* value exists already */
 274                                                 *text = textbuf;
 275                                                 snprintf( textbuf, textlen,
 276                                                         "modify/%s: %s: value #%i already exists",
 277                                                         op, mod->sm_desc->ad_cname.bv_val, j );
 278                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
 279                                         }
 280                                 }
 281                         }
 282
 283                         /* test asserted values against themselves */
 284                         for( j = 0; j < i; j++ ) {
 285                                 if ( bvmatch( &mod->sm_bvalues[i],
 286                                         &mod->sm_bvalues[j] ) ) {
 287
 288                                         /* value exists already */
 289                                         *text = textbuf;
 290                                         snprintf( textbuf, textlen,
 291                                                 "modify/%s: %s: value #%i already exists",
 292                                                 op, mod->sm_desc->ad_cname.bv_val, j );
 293                                         return LDAP_TYPE_OR_VALUE_EXISTS;
 294                                 }
 295                         }
 296                 }
 297
 298         } else {
 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
 328                 if ( mod->sm_bvalues[ 1 ].bv_val == 0 ) {
 329                         if ( a != NULL ) {
 330                                 struct berval   asserted;
 331                                 int             i;
 332
 333                                 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
 334                                         &mod->sm_bvalues[ 0 ], &asserted, text );
 335
 336                                 if ( rc != LDAP_SUCCESS ) {
 337                                         return rc;
 338                                 }
 339
 340                                 for ( i = 0; a->a_vals[ i ].bv_val; i++ ) {
 341                                         int     match;
 342
 343                                         rc = value_match( &match, mod->sm_desc, mr,
 344                                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 345                                                 &a->a_vals[ i ], &asserted, text );
 346
 347                                         if( rc == LDAP_SUCCESS && match == 0 ) {
 348                                                 free( asserted.bv_val );
 349                                                 *text = textbuf;
 350                                                 snprintf( textbuf, textlen,
 351                                                         "modify/%s: %s: value #0 already exists",
 352                                                         op, mod->sm_desc->ad_cname.bv_val, 0 );
 353                                                 return LDAP_TYPE_OR_VALUE_EXISTS;
 354                                         }
 355                                 }
 356                         }
 357
 358                 } else {
 359                         rc = modify_check_duplicates( mod->sm_desc, mr,
 360                                         a ? a->a_vals : NULL, mod->sm_bvalues,
 361                                         text, textbuf, textlen );
 362
 363                         if ( rc != LDAP_SUCCESS ) {
 364                                 return rc;
 365                         }
 366                 }
 367         }
 368
 369         /* no - add them */
 370         if( attr_merge( e, mod->sm_desc, mod->sm_bvalues ) != 0 ) {
 371                 /* this should return result of attr_merge */
 372                 *text = textbuf;
 373                 snprintf( textbuf, textlen,
 374                         "modify/%s: %s: merge error",
 375                         op, mod->sm_desc->ad_cname.bv_val );
 376                 return LDAP_OTHER;
 377         }
 378
 379         return LDAP_SUCCESS;
 380 }
 381
 382 int
 383 modify_delete_values(
 384         Entry   *e,
 385         Modification    *mod,
 386         const char      **text,
 387         char *textbuf, size_t textlen
 388 )
 389 {
 390         int             i, j, k, rc = LDAP_SUCCESS;
 391         Attribute       *a;
 392         MatchingRule    *mr = mod->sm_desc->ad_type->sat_equality;
 393         BerVarray       nvals = NULL;
 394         char            dummy = '\0';
 395
 396         /* delete the entire attribute */
 397         if ( mod->sm_bvalues == NULL ) {
 398                 rc = attr_delete( &e->e_attrs, mod->sm_desc );
 399
 400                 if( rc != LDAP_SUCCESS ) {
 401                         *text = textbuf;
 402                         snprintf( textbuf, textlen,
 403                                 "modify/delete: %s: no such attribute",
 404                                 mod->sm_desc->ad_cname.bv_val );
 405                         rc = LDAP_NO_SUCH_ATTRIBUTE;
 406                 }
 407                 return rc;
 408         }
 409
 410         if( mr == NULL || !mr->smr_match ) {
 411                 /* disallow specific attributes from being deleted if
 412                         no equality rule */
 413                 *text = textbuf;
 414                 snprintf( textbuf, textlen,
 415                         "modify/delete: %s: no equality matching rule",
 416                         mod->sm_desc->ad_cname.bv_val );
 417                 return LDAP_INAPPROPRIATE_MATCHING;
 418         }
 419
 420         /* delete specific values - find the attribute first */
 421         if ( (a = attr_find( e->e_attrs, mod->sm_desc )) == NULL ) {
 422                 *text = textbuf;
 423                 snprintf( textbuf, textlen,
 424                         "modify/delete: %s: no such attribute",
 425                         mod->sm_desc->ad_cname.bv_val );
 426                 return LDAP_NO_SUCH_ATTRIBUTE;
 427         }
 428
 429         /* find each value to delete */
 430         for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ )
 431                 /* count existing values */ ;
 432
 433         nvals = (BerVarray)ch_calloc( j + 1, sizeof ( struct berval ) );
 434
 435         /* normalize existing values */
 436         for ( j = 0; a->a_vals[ j ].bv_val != NULL; j++ ) {
 437                 rc = value_normalize( a->a_desc, SLAP_MR_EQUALITY,
 438                         &a->a_vals[ j ], &nvals[ j ], text );
 439
 440                 if ( rc != LDAP_SUCCESS ) {
 441                         nvals[ j ].bv_val = NULL;
 442                         goto return_results;
 443                 }
 444         }
 445
 446         for ( i = 0; mod->sm_bvalues[ i ].bv_val != NULL; i++ ) {
 447                 struct  berval asserted;
 448                 int     found = 0;
 449
 450                 /* normalize the value to be deleted */
 451                 rc = value_normalize( mod->sm_desc, SLAP_MR_EQUALITY,
 452                         &mod->sm_bvalues[ i ], &asserted, text );
 453
 454                 if( rc != LDAP_SUCCESS ) {
 455                         goto return_results;
 456                 }
 457
 458                 /* search it */
 459                 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
 460                         int match;
 461
 462                         if ( nvals[ j ].bv_val == &dummy ) {
 463                                 continue;
 464                         }
 465
 466                         rc = (*mr->smr_match)( &match,
 467                                 SLAP_MR_VALUE_SYNTAX_MATCH,
 468                                 a->a_desc->ad_type->sat_syntax,
 469                                 mr, &nvals[ j ], &asserted );
 470
 471                         if ( rc != LDAP_SUCCESS ) {
 472                                 free( asserted.bv_val );
 473                                 *text = textbuf;
 474                                 snprintf( textbuf, textlen,
 475                                         "%s: matching rule failed",
 476                                         mod->sm_desc->ad_cname.bv_val );
 477                                 goto return_results;
 478                         }
 479
 480                         if ( match != 0 ) {
 481                                 continue;
 482                         }
 483
 484                         found = 1;
 485
 486                         /* delete value and mark it as dummy */
 487                         free( nvals[ j ].bv_val );
 488                         nvals[ j ].bv_val = &dummy;
 489
 490                         break;
 491                 }
 492
 493                 free( asserted.bv_val );
 494
 495                 if ( found == 0 ) {
 496                         *text = textbuf;
 497                         snprintf( textbuf, textlen,
 498                                 "modify/delete: %s: no such value",
 499                                 mod->sm_desc->ad_cname.bv_val );
 500                         rc = LDAP_NO_SUCH_ATTRIBUTE;
 501                         goto return_results;
 502                 }
 503         }
 504
 505         /* compact array skipping dummies */
 506         for ( k = 0, j = 0; nvals[ k ].bv_val != NULL; j++, k++ ) {
 507
 508                 /* delete and skip dummies */ ;
 509                 for ( ; nvals[ k ].bv_val == &dummy; k++ ) {
 510                         free( a->a_vals[ k ].bv_val );
 511                 }
 512
 513                 if ( j != k ) {
 514                         a->a_vals[ j ] = a->a_vals[ k ];
 515                 }
 516
 517                 if ( a->a_vals[ k ].bv_val == NULL ) {
 518                         break;
 519                 }
 520         }
 521         a->a_vals[ j ].bv_val = NULL;
 522
 523         assert( i == k - j );
 524
 525         /* if no values remain, delete the entire attribute */
 526         if ( a->a_vals[0].bv_val == NULL ) {
 527                 if ( attr_delete( &e->e_attrs, mod->sm_desc ) ) {
 528                         *text = textbuf;
 529                         snprintf( textbuf, textlen,
 530                                 "modify/delete: %s: no such attribute",
 531                                 mod->sm_desc->ad_cname.bv_val );
 532                         rc = LDAP_NO_SUCH_ATTRIBUTE;
 533                 }
 534         }
 535
 536 return_results:;
 537         if ( nvals ) {
 538                 /* delete the remaining normalized values */
 539                 for ( j = 0; nvals[ j ].bv_val != NULL; j++ ) {
 540                         if ( nvals[ j ].bv_val != &dummy ) {
 541                                 ber_memfree( nvals[ j ].bv_val );
 542                         }
 543                 }
 544                 ber_memfree( nvals );
 545         }
 546
 547         return rc;
 548 }
 549
 550 int
 551 modify_replace_values(
 552         Entry   *e,
 553         Modification    *mod,
 554         const char      **text,
 555         char *textbuf, size_t textlen
 556 )
 557 {
 558         (void) attr_delete( &e->e_attrs, mod->sm_desc );
 559
 560         if ( mod->sm_bvalues ) {
 561                 return modify_add_values( e, mod, text, textbuf, textlen );
 562         }
 563
 564         return LDAP_SUCCESS;
 565 }
 566
 567 void
 568 slap_mod_free(
 569         Modification    *mod,
 570         int                             freeit
 571 )
 572 {
 573 #if 0
 574         if ( mod->sm_type.bv_val)
 575                 free( mod->sm_type.bv_val );
 576 #endif
 577         if ( mod->sm_bvalues != NULL )
 578                 ber_bvarray_free( mod->sm_bvalues );
 579
 580         if( freeit )
 581                 free( mod );
 582 }
 583
 584 void
 585 slap_mods_free(
 586     Modifications       *ml
 587 )
 588 {
 589         Modifications *next;
 590
 591         for ( ; ml != NULL; ml = next ) {
 592                 next = ml->sml_next;
 593
 594                 slap_mod_free( &ml->sml_mod, 0 );
 595                 free( ml );
 596         }
 597 }
 598