1/* $NetBSD: attr.c,v 1.1.1.4 2010/12/12 15:22:18 adam Exp $ */ 2 3/* attr.c - routines for dealing with attributes */ 4/* OpenLDAP: pkg/ldap/servers/slapd/attr.c,v 1.112.2.12 2010/04/13 20:23:10 kurt Exp */ 5/* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 1998-2010 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18/* Portions Copyright (c) 1995 Regents of the University of Michigan. 19 * All rights reserved. 20 * 21 * Redistribution and use in source and binary forms are permitted 22 * provided that this notice is preserved and that due credit is given 23 * to the University of Michigan at Ann Arbor. The name of the University 24 * may not be used to endorse or promote products derived from this 25 * software without specific prior written permission. This software 26 * is provided ``as is'' without express or implied warranty. 27 */ 28 29#include "portable.h" 30 31#include <stdio.h> 32 33#ifdef HAVE_FCNTL_H 34#include <fcntl.h> 35#endif 36 37#include <ac/ctype.h> 38#include <ac/errno.h> 39#include <ac/socket.h> 40#include <ac/string.h> 41#include <ac/time.h> 42 43#include "slap.h" 44 45/* 46 * Allocate in chunks, minimum of 1000 at a time. 47 */ 48#define CHUNK_SIZE 1000 49typedef struct slap_list { 50 struct slap_list *next; 51} slap_list; 52static slap_list *attr_chunks; 53static Attribute *attr_list; 54static ldap_pvt_thread_mutex_t attr_mutex; 55 56int 57attr_prealloc( int num ) 58{ 59 Attribute *a; 60 slap_list *s; 61 62 if (!num) return 0; 63 64 s = ch_calloc( 1, sizeof(slap_list) + num * sizeof(Attribute)); 65 s->next = attr_chunks; 66 attr_chunks = s; 67 68 a = (Attribute *)(s+1); 69 for ( ;num>1; num--) { 70 a->a_next = a+1; 71 a++; 72 } 73 a->a_next = attr_list; 74 attr_list = (Attribute *)(s+1); 75 76 return 0; 77} 78 79Attribute * 80attr_alloc( AttributeDescription *ad ) 81{ 82 Attribute *a; 83 84 ldap_pvt_thread_mutex_lock( &attr_mutex ); 85 if ( !attr_list ) 86 attr_prealloc( CHUNK_SIZE ); 87 a = attr_list; 88 attr_list = a->a_next; 89 a->a_next = NULL; 90 ldap_pvt_thread_mutex_unlock( &attr_mutex ); 91 92 a->a_desc = ad; 93 94 return a; 95} 96 97/* Return a list of num attrs */ 98Attribute * 99attrs_alloc( int num ) 100{ 101 Attribute *head = NULL; 102 Attribute **a; 103 104 ldap_pvt_thread_mutex_lock( &attr_mutex ); 105 for ( a = &attr_list; *a && num > 0; a = &(*a)->a_next ) { 106 if ( !head ) 107 head = *a; 108 num--; 109 } 110 attr_list = *a; 111 if ( num > 0 ) { 112 attr_prealloc( num > CHUNK_SIZE ? num : CHUNK_SIZE ); 113 *a = attr_list; 114 for ( ; *a && num > 0; a = &(*a)->a_next ) { 115 if ( !head ) 116 head = *a; 117 num--; 118 } 119 attr_list = *a; 120 } 121 *a = NULL; 122 ldap_pvt_thread_mutex_unlock( &attr_mutex ); 123 124 return head; 125} 126 127 128void 129attr_clean( Attribute *a ) 130{ 131 if ( a->a_nvals && a->a_nvals != a->a_vals && 132 !( a->a_flags & SLAP_ATTR_DONT_FREE_VALS )) { 133 if ( a->a_flags & SLAP_ATTR_DONT_FREE_DATA ) { 134 free( a->a_nvals ); 135 } else { 136 ber_bvarray_free( a->a_nvals ); 137 } 138 } 139 /* a_vals may be equal to slap_dummy_bv, a static empty berval; 140 * this is used as a placeholder for attributes that do not carry 141 * values, e.g. when proxying search entries with the "attrsonly" 142 * bit set. */ 143 if ( a->a_vals != &slap_dummy_bv && 144 !( a->a_flags & SLAP_ATTR_DONT_FREE_VALS )) { 145 if ( a->a_flags & SLAP_ATTR_DONT_FREE_DATA ) { 146 free( a->a_vals ); 147 } else { 148 ber_bvarray_free( a->a_vals ); 149 } 150 } 151 a->a_desc = NULL; 152 a->a_vals = NULL; 153 a->a_nvals = NULL; 154#ifdef LDAP_COMP_MATCH 155 a->a_comp_data = NULL; 156#endif 157 a->a_flags = 0; 158 a->a_numvals = 0; 159} 160 161void 162attr_free( Attribute *a ) 163{ 164 attr_clean( a ); 165 ldap_pvt_thread_mutex_lock( &attr_mutex ); 166 a->a_next = attr_list; 167 attr_list = a; 168 ldap_pvt_thread_mutex_unlock( &attr_mutex ); 169} 170 171#ifdef LDAP_COMP_MATCH 172void 173comp_tree_free( Attribute *a ) 174{ 175 Attribute *next; 176 177 for( ; a != NULL ; a = next ) { 178 next = a->a_next; 179 if ( component_destructor && a->a_comp_data ) { 180 if ( a->a_comp_data->cd_mem_op ) 181 component_destructor( a->a_comp_data->cd_mem_op ); 182 free ( a->a_comp_data ); 183 } 184 } 185} 186#endif 187 188void 189attrs_free( Attribute *a ) 190{ 191 if ( a ) { 192 Attribute *b = (Attribute *)0xBAD, *tail, *next; 193 194 /* save tail */ 195 tail = a; 196 do { 197 next = a->a_next; 198 attr_clean( a ); 199 a->a_next = b; 200 b = a; 201 a = next; 202 } while ( next ); 203 204 ldap_pvt_thread_mutex_lock( &attr_mutex ); 205 /* replace NULL with current attr list and let attr list 206 * start from last attribute returned to list */ 207 tail->a_next = attr_list; 208 attr_list = b; 209 ldap_pvt_thread_mutex_unlock( &attr_mutex ); 210 } 211} 212 213static void 214attr_dup2( Attribute *tmp, Attribute *a ) 215{ 216 tmp->a_flags = a->a_flags & SLAP_ATTR_PERSISTENT_FLAGS; 217 if ( a->a_vals != NULL ) { 218 unsigned i, j; 219 220 tmp->a_numvals = a->a_numvals; 221 tmp->a_vals = ch_malloc( (tmp->a_numvals + 1) * sizeof(struct berval) ); 222 for ( i = 0; i < tmp->a_numvals; i++ ) { 223 ber_dupbv( &tmp->a_vals[i], &a->a_vals[i] ); 224 if ( BER_BVISNULL( &tmp->a_vals[i] ) ) break; 225 /* FIXME: error? */ 226 } 227 BER_BVZERO( &tmp->a_vals[i] ); 228 229 /* a_nvals must be non null; it may be equal to a_vals */ 230 assert( a->a_nvals != NULL ); 231 232 if ( a->a_nvals != a->a_vals ) { 233 234 tmp->a_nvals = ch_malloc( (tmp->a_numvals + 1) * sizeof(struct berval) ); 235 for ( j = 0; !BER_BVISNULL( &a->a_nvals[j] ); j++ ) { 236 assert( j < i ); 237 ber_dupbv( &tmp->a_nvals[j], &a->a_nvals[j] ); 238 if ( BER_BVISNULL( &tmp->a_nvals[j] ) ) break; 239 /* FIXME: error? */ 240 } 241 assert( j == i ); 242 BER_BVZERO( &tmp->a_nvals[j] ); 243 244 } else { 245 tmp->a_nvals = tmp->a_vals; 246 } 247 } 248} 249 250Attribute * 251attr_dup( Attribute *a ) 252{ 253 Attribute *tmp; 254 255 if ( a == NULL) return NULL; 256 257 tmp = attr_alloc( a->a_desc ); 258 attr_dup2( tmp, a ); 259 return tmp; 260} 261 262Attribute * 263attrs_dup( Attribute *a ) 264{ 265 int i; 266 Attribute *tmp, *anew; 267 268 if( a == NULL ) return NULL; 269 270 /* count them */ 271 for( tmp=a,i=0; tmp; tmp=tmp->a_next ) { 272 i++; 273 } 274 275 anew = attrs_alloc( i ); 276 277 for( tmp=anew; a; a=a->a_next ) { 278 tmp->a_desc = a->a_desc; 279 attr_dup2( tmp, a ); 280 tmp=tmp->a_next; 281 } 282 283 return anew; 284} 285 286int 287attr_valfind( 288 Attribute *a, 289 unsigned flags, 290 struct berval *val, 291 unsigned *slot, 292 void *ctx ) 293{ 294 struct berval nval = BER_BVNULL, *cval; 295 MatchingRule *mr; 296 const char *text; 297 int match = -1, rc; 298 unsigned i; 299 300 if ( flags & SLAP_MR_ORDERING ) 301 mr = a->a_desc->ad_type->sat_ordering; 302 else 303 mr = a->a_desc->ad_type->sat_equality; 304 305 if( !SLAP_IS_MR_ASSERTED_VALUE_NORMALIZED_MATCH( flags ) && 306 mr->smr_normalize ) 307 { 308 rc = (mr->smr_normalize)( 309 flags & (SLAP_MR_TYPE_MASK|SLAP_MR_SUBTYPE_MASK|SLAP_MR_VALUE_OF_SYNTAX), 310 a->a_desc->ad_type->sat_syntax, 311 mr, val, &nval, ctx ); 312 313 if( rc != LDAP_SUCCESS ) { 314 return LDAP_INVALID_SYNTAX; 315 } 316 cval = &nval; 317 } else { 318 cval = val; 319 } 320 321 if ( a->a_flags & SLAP_ATTR_SORTED_VALS ) { 322 /* Binary search */ 323 unsigned base = 0, n = a->a_numvals; 324 325 while ( 0 < n ) { 326 unsigned pivot = n >> 1; 327 i = base + pivot; 328 rc = value_match( &match, a->a_desc, mr, flags, 329 &a->a_nvals[i], cval, &text ); 330 if ( rc == LDAP_SUCCESS && match == 0 ) 331 break; 332 if ( match < 0 ) { 333 base = i+1; 334 n -= pivot+1; 335 } else { 336 n = pivot; 337 } 338 } 339 if ( match < 0 ) 340 i++; 341 } else { 342 /* Linear search */ 343 for ( i = 0; i < a->a_numvals; i++ ) { 344 const char *text; 345 346 rc = ordered_value_match( &match, a->a_desc, mr, flags, 347 &a->a_nvals[i], cval, &text ); 348 if ( rc == LDAP_SUCCESS && match == 0 ) 349 break; 350 } 351 } 352 if ( slot ) 353 *slot = i; 354 if ( match ) 355 rc = LDAP_NO_SUCH_ATTRIBUTE; 356 if ( nval.bv_val ) 357 slap_sl_free( nval.bv_val, ctx ); 358 359 return rc; 360} 361 362int 363attr_valadd( 364 Attribute *a, 365 BerVarray vals, 366 BerVarray nvals, 367 int nn ) 368{ 369 int i; 370 BerVarray v2; 371 372 v2 = (BerVarray) SLAP_REALLOC( (char *) a->a_vals, 373 (a->a_numvals + nn + 1) * sizeof(struct berval) ); 374 if( v2 == NULL ) { 375 Debug(LDAP_DEBUG_TRACE, 376 "attr_valadd: SLAP_REALLOC failed.\n", 0, 0, 0 ); 377 return LBER_ERROR_MEMORY; 378 } 379 a->a_vals = v2; 380 if ( nvals ) { 381 v2 = (BerVarray) SLAP_REALLOC( (char *) a->a_nvals, 382 (a->a_numvals + nn + 1) * sizeof(struct berval) ); 383 if( v2 == NULL ) { 384 Debug(LDAP_DEBUG_TRACE, 385 "attr_valadd: SLAP_REALLOC failed.\n", 0, 0, 0 ); 386 return LBER_ERROR_MEMORY; 387 } 388 a->a_nvals = v2; 389 } else { 390 a->a_nvals = a->a_vals; 391 } 392 393 /* If sorted and old vals exist, must insert */ 394 if (( a->a_flags & SLAP_ATTR_SORTED_VALS ) && a->a_numvals ) { 395 unsigned slot; 396 int j, rc; 397 v2 = nvals ? nvals : vals; 398 for ( i = 0; i < nn; i++ ) { 399 rc = attr_valfind( a, SLAP_MR_EQUALITY | SLAP_MR_VALUE_OF_ASSERTION_SYNTAX | 400 SLAP_MR_ASSERTED_VALUE_NORMALIZED_MATCH | SLAP_MR_ATTRIBUTE_VALUE_NORMALIZED_MATCH, 401 &v2[i], &slot, NULL ); 402 if ( rc != LDAP_NO_SUCH_ATTRIBUTE ) { 403 /* should never happen */ 404 if ( rc == LDAP_SUCCESS ) 405 rc = LDAP_TYPE_OR_VALUE_EXISTS; 406 return rc; 407 } 408 for ( j = a->a_numvals; j >= (int)slot; j-- ) { 409 a->a_vals[j+1] = a->a_vals[j]; 410 if ( nvals ) 411 a->a_nvals[j+1] = a->a_nvals[j]; 412 } 413 ber_dupbv( &a->a_nvals[slot], &v2[i] ); 414 if ( nvals ) 415 ber_dupbv( &a->a_vals[slot], &vals[i] ); 416 a->a_numvals++; 417 } 418 BER_BVZERO( &a->a_vals[a->a_numvals] ); 419 if ( a->a_vals != a->a_nvals ) 420 BER_BVZERO( &a->a_nvals[a->a_numvals] ); 421 } else { 422 v2 = &a->a_vals[a->a_numvals]; 423 for ( i = 0 ; i < nn; i++ ) { 424 ber_dupbv( &v2[i], &vals[i] ); 425 if ( BER_BVISNULL( &v2[i] ) ) break; 426 } 427 BER_BVZERO( &v2[i] ); 428 429 if ( nvals ) { 430 v2 = &a->a_nvals[a->a_numvals]; 431 for ( i = 0 ; i < nn; i++ ) { 432 ber_dupbv( &v2[i], &nvals[i] ); 433 if ( BER_BVISNULL( &v2[i] ) ) break; 434 } 435 BER_BVZERO( &v2[i] ); 436 } 437 a->a_numvals += i; 438 } 439 return 0; 440} 441 442/* 443 * attr_merge - merge the given type and value with the list of 444 * attributes in attrs. 445 * 446 * nvals must be NULL if the attribute has no normalizer. 447 * In this case, a->a_nvals will be set equal to a->a_vals. 448 * 449 * returns 0 everything went ok 450 * -1 trouble 451 */ 452 453int 454attr_merge( 455 Entry *e, 456 AttributeDescription *desc, 457 BerVarray vals, 458 BerVarray nvals ) 459{ 460 int i = 0; 461 462 Attribute **a; 463 464 for ( a = &e->e_attrs; *a != NULL; a = &(*a)->a_next ) { 465 if ( (*a)->a_desc == desc ) { 466 break; 467 } 468 } 469 470 if ( *a == NULL ) { 471 *a = attr_alloc( desc ); 472 } else { 473 /* 474 * FIXME: if the attribute already exists, the presence 475 * of nvals and the value of (*a)->a_nvals must be consistent 476 */ 477 assert( ( nvals == NULL && (*a)->a_nvals == (*a)->a_vals ) 478 || ( nvals != NULL && ( 479 ( (*a)->a_vals == NULL && (*a)->a_nvals == NULL ) 480 || ( (*a)->a_nvals != (*a)->a_vals ) ) ) ); 481 } 482 483 if ( vals != NULL ) { 484 for ( ; !BER_BVISNULL( &vals[i] ); i++ ) ; 485 } 486 return attr_valadd( *a, vals, nvals, i ); 487} 488 489/* 490 * if a normalization function is defined for the equality matchingRule 491 * of desc, the value is normalized and stored in nval; otherwise nval 492 * is NULL 493 */ 494int 495attr_normalize( 496 AttributeDescription *desc, 497 BerVarray vals, 498 BerVarray *nvalsp, 499 void *memctx ) 500{ 501 int rc = LDAP_SUCCESS; 502 BerVarray nvals = NULL; 503 504 *nvalsp = NULL; 505 506 if ( desc->ad_type->sat_equality && 507 desc->ad_type->sat_equality->smr_normalize ) 508 { 509 int i; 510 511 for ( i = 0; !BER_BVISNULL( &vals[i] ); i++ ); 512 513 nvals = slap_sl_calloc( sizeof(struct berval), i + 1, memctx ); 514 for ( i = 0; !BER_BVISNULL( &vals[i] ); i++ ) { 515 rc = desc->ad_type->sat_equality->smr_normalize( 516 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX, 517 desc->ad_type->sat_syntax, 518 desc->ad_type->sat_equality, 519 &vals[i], &nvals[i], memctx ); 520 521 if ( rc != LDAP_SUCCESS ) { 522 BER_BVZERO( &nvals[i + 1] ); 523 break; 524 } 525 } 526 BER_BVZERO( &nvals[i] ); 527 *nvalsp = nvals; 528 } 529 530 if ( rc != LDAP_SUCCESS && nvals != NULL ) { 531 ber_bvarray_free_x( nvals, memctx ); 532 } 533 534 return rc; 535} 536 537int 538attr_merge_normalize( 539 Entry *e, 540 AttributeDescription *desc, 541 BerVarray vals, 542 void *memctx ) 543{ 544 BerVarray nvals = NULL; 545 int rc; 546 547 rc = attr_normalize( desc, vals, &nvals, memctx ); 548 if ( rc == LDAP_SUCCESS ) { 549 rc = attr_merge( e, desc, vals, nvals ); 550 if ( nvals != NULL ) { 551 ber_bvarray_free_x( nvals, memctx ); 552 } 553 } 554 555 return rc; 556} 557 558int 559attr_merge_one( 560 Entry *e, 561 AttributeDescription *desc, 562 struct berval *val, 563 struct berval *nval ) 564{ 565 Attribute **a; 566 567 for ( a = &e->e_attrs; *a != NULL; a = &(*a)->a_next ) { 568 if ( (*a)->a_desc == desc ) { 569 break; 570 } 571 } 572 573 if ( *a == NULL ) { 574 *a = attr_alloc( desc ); 575 } 576 577 return attr_valadd( *a, val, nval, 1 ); 578} 579 580/* 581 * if a normalization function is defined for the equality matchingRule 582 * of desc, the value is normalized and stored in nval; otherwise nval 583 * is NULL 584 */ 585int 586attr_normalize_one( 587 AttributeDescription *desc, 588 struct berval *val, 589 struct berval *nval, 590 void *memctx ) 591{ 592 int rc = LDAP_SUCCESS; 593 594 BER_BVZERO( nval ); 595 596 if ( desc->ad_type->sat_equality && 597 desc->ad_type->sat_equality->smr_normalize ) 598 { 599 rc = desc->ad_type->sat_equality->smr_normalize( 600 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX, 601 desc->ad_type->sat_syntax, 602 desc->ad_type->sat_equality, 603 val, nval, memctx ); 604 605 if ( rc != LDAP_SUCCESS ) { 606 return rc; 607 } 608 } 609 610 return rc; 611} 612 613int 614attr_merge_normalize_one( 615 Entry *e, 616 AttributeDescription *desc, 617 struct berval *val, 618 void *memctx ) 619{ 620 struct berval nval = BER_BVNULL; 621 struct berval *nvalp = NULL; 622 int rc; 623 624 rc = attr_normalize_one( desc, val, &nval, memctx ); 625 if ( rc == LDAP_SUCCESS && !BER_BVISNULL( &nval ) ) { 626 nvalp = &nval; 627 } 628 629 rc = attr_merge_one( e, desc, val, nvalp ); 630 if ( nvalp != NULL ) { 631 slap_sl_free( nval.bv_val, memctx ); 632 } 633 return rc; 634} 635 636/* 637 * attrs_find - find attribute(s) by AttributeDescription 638 * returns next attribute which is subtype of provided description. 639 */ 640 641Attribute * 642attrs_find( 643 Attribute *a, 644 AttributeDescription *desc ) 645{ 646 for ( ; a != NULL; a = a->a_next ) { 647 if ( is_ad_subtype( a->a_desc, desc ) ) { 648 return( a ); 649 } 650 } 651 652 return( NULL ); 653} 654 655/* 656 * attr_find - find attribute by type 657 */ 658 659Attribute * 660attr_find( 661 Attribute *a, 662 AttributeDescription *desc ) 663{ 664 for ( ; a != NULL; a = a->a_next ) { 665 if ( a->a_desc == desc ) { 666 return( a ); 667 } 668 } 669 670 return( NULL ); 671} 672 673/* 674 * attr_delete - delete the attribute type in list pointed to by attrs 675 * return 0 deleted ok 676 * 1 not found in list a 677 * -1 something bad happened 678 */ 679 680int 681attr_delete( 682 Attribute **attrs, 683 AttributeDescription *desc ) 684{ 685 Attribute **a; 686 687 for ( a = attrs; *a != NULL; a = &(*a)->a_next ) { 688 if ( (*a)->a_desc == desc ) { 689 Attribute *save = *a; 690 *a = (*a)->a_next; 691 attr_free( save ); 692 693 return LDAP_SUCCESS; 694 } 695 } 696 697 return LDAP_NO_SUCH_ATTRIBUTE; 698} 699 700int 701attr_init( void ) 702{ 703 ldap_pvt_thread_mutex_init( &attr_mutex ); 704 return 0; 705} 706 707int 708attr_destroy( void ) 709{ 710 slap_list *a; 711 712 for ( a=attr_chunks; a; a=attr_chunks ) { 713 attr_chunks = a->next; 714 free( a ); 715 } 716 ldap_pvt_thread_mutex_destroy( &attr_mutex ); 717 return 0; 718} 719