X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fsets.c;h=e25d8c3fe642298f205223824dee56a2b6331a78;hb=a7f4102bbfd42681ac505f2adb3ff35d8aba3d88;hp=fa7b92e90c1ef1d5d5a9989740bc743ca2ed7940;hpb=acbb5cf689a4336af05c9f259d909d8141055bac;p=openldap diff --git a/servers/slapd/sets.c b/servers/slapd/sets.c index fa7b92e90c..e25d8c3fe6 100644 --- a/servers/slapd/sets.c +++ b/servers/slapd/sets.c @@ -1,7 +1,7 @@ /* $OpenLDAP$ */ /* This work is part of OpenLDAP Software . * - * Copyright 2000-2006 The OpenLDAP Foundation. + * Copyright 2000-2009 The OpenLDAP Foundation. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -24,20 +24,22 @@ static BerVarray set_chase( SLAP_SET_GATHER gatherer, SetCookie *cookie, BerVarray set, AttributeDescription *desc, int closure ); +/* Count the array members */ static long slap_set_size( BerVarray set ) { - long i; + long i = 0; - i = 0; if ( set != NULL ) { while ( !BER_BVISNULL( &set[ i ] ) ) { i++; } } + return i; } +/* Return 0 if there is at least one array member, non-zero otherwise */ static int slap_set_isempty( BerVarray set ) { @@ -52,6 +54,14 @@ slap_set_isempty( BerVarray set ) return 1; } +/* Dispose of the contents of the array and the array itself according + * to the flags value. If SLAP_SET_REFVAL, don't dispose of values; + * if SLAP_SET_REFARR, don't dispose of the array itself. In case of + * binary operators, there are LEFT flags and RIGHT flags, referring to + * the first and the second operator arguments, respectively. In this + * case, flags must be transformed using macros SLAP_SET_LREF2REF() and + * SLAP_SET_RREF2REF() before calling this function. + */ static void slap_set_dispose( SetCookie *cp, BerVarray set, unsigned flags ) { @@ -65,6 +75,10 @@ slap_set_dispose( SetCookie *cp, BerVarray set, unsigned flags ) } } +/* Duplicate a set. If SLAP_SET_REFARR, is not set, the original array + * with the original values is returned, otherwise the array is duplicated; + * if SLAP_SET_REFVAL is set, also the values are duplicated. + */ static BerVarray set_dup( SetCookie *cp, BerVarray set, unsigned flags ) { @@ -80,7 +94,7 @@ set_dup( SetCookie *cp, BerVarray set, unsigned flags ) for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) ; newset = cp->set_op->o_tmpcalloc( i + 1, - sizeof(struct berval), + sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( newset == NULL ) { return NULL; @@ -103,6 +117,19 @@ set_dup( SetCookie *cp, BerVarray set, unsigned flags ) return newset; } +/* Join two sets according to operator op and flags op_flags. + * op can be: + * '|' (or): the union between the two sets is returned, + * eliminating duplicates + * '&' (and): the intersection between the two sets + * is returned + * '+' (add): the inner product of the two sets is returned, + * namely a set containing the concatenation of + * all combinations of the two sets members, + * except for duplicates. + * The two sets are disposed of according to the flags as described + * for slap_set_dispose(). + */ BerVarray slap_set_join( SetCookie *cp, @@ -111,33 +138,38 @@ slap_set_join( BerVarray rset ) { BerVarray set; - long i, j, last; + long i, j, last, rlast; unsigned op = ( op_flags & SLAP_SET_OPMASK ); set = NULL; switch ( op ) { case '|': /* union */ - if ( lset == NULL || BER_BVISNULL( lset ) ) { + if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] ) ) { if ( rset == NULL ) { if ( lset == NULL ) { set = cp->set_op->o_tmpcalloc( 1, - sizeof(struct berval), + sizeof( struct berval ), cp->set_op->o_tmpmemctx ); - BER_BVZERO( set ); - return set; + BER_BVZERO( &set[ 0 ] ); + goto done2; } - return set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + goto done2; } slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); - return set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) ); + set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) ); + goto done2; } - if ( rset == NULL || BER_BVISNULL( rset ) ) { + if ( rset == NULL || BER_BVISNULL( &rset[ 0 ] ) ) { slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) ); - return set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + goto done2; } - i = slap_set_size( lset ) + slap_set_size( rset ) + 1; - set = cp->set_op->o_tmpcalloc( i, sizeof(struct berval), cp->set_op->o_tmpmemctx ); + /* worst scenario: no duplicates */ + rlast = slap_set_size( rset ); + i = slap_set_size( lset ) + rlast + 1; + set = cp->set_op->o_tmpcalloc( i, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( set != NULL ) { /* set_chase() depends on this routine to * keep the first elements of the result @@ -153,6 +185,9 @@ slap_set_join( } } + /* pointers to values have been used in set - don't free twice */ + op_flags |= SLAP_SET_LREFVAL; + last = i; for ( i = 0; !BER_BVISNULL( &rset[ i ] ); i++ ) { @@ -163,11 +198,13 @@ slap_set_join( { if ( !( op_flags & SLAP_SET_RREFVAL ) ) { cp->set_op->o_tmpfree( rset[ i ].bv_val, cp->set_op->o_tmpmemctx ); - BER_BVZERO( &rset[ i ] ); + rset[ i ] = rset[ --rlast ]; + BER_BVZERO( &rset[ rlast ] ); + i--; } exists = 1; - break; - } + break; + } } if ( !exists ) { @@ -180,37 +217,59 @@ slap_set_join( last++; } } + + /* pointers to values have been used in set - don't free twice */ + op_flags |= SLAP_SET_RREFVAL; + BER_BVZERO( &set[ last ] ); } break; case '&': /* intersection */ - if ( lset == NULL || BER_BVISNULL( lset ) - || rset == NULL || BER_BVISNULL( rset ) ) + if ( lset == NULL || BER_BVISNULL( &lset[ 0 ] ) + || rset == NULL || BER_BVISNULL( &rset[ 0 ] ) ) { - set = cp->set_op->o_tmpcalloc( 1, sizeof(struct berval), + set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); - BER_BVZERO( set ); + BER_BVZERO( &set[ 0 ] ); + break; } else { - set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + long llen, rlen; + BerVarray sset; + + llen = slap_set_size( lset ); + rlen = slap_set_size( rset ); + + /* dup the shortest */ + if ( llen < rlen ) { + last = llen; + set = set_dup( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + lset = NULL; + sset = rset; + + } else { + last = rlen; + set = set_dup( cp, rset, SLAP_SET_RREF2REF( op_flags ) ); + rset = NULL; + sset = lset; + } + if ( set == NULL ) { break; } - lset = NULL; - last = slap_set_size( set ) - 1; + for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) { - for ( j = 0; !BER_BVISNULL( &rset[ j ] ); j++ ) { - if ( bvmatch( &set[ i ], &rset[ j ] ) ) { + for ( j = 0; !BER_BVISNULL( &sset[ j ] ); j++ ) { + if ( bvmatch( &set[ i ], &sset[ j ] ) ) { break; } } - if ( BER_BVISNULL( &rset[ j ] ) ) { + if ( BER_BVISNULL( &sset[ j ] ) ) { cp->set_op->o_tmpfree( set[ i ].bv_val, cp->set_op->o_tmpmemctx ); - set[ i ] = set[ last ]; + set[ i ] = set[ --last ]; BER_BVZERO( &set[ last ] ); - last--; i--; } } @@ -221,7 +280,18 @@ slap_set_join( i = slap_set_size( rset ); j = slap_set_size( lset ); - set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof(struct berval), + /* handle empty set cases */ + if ( i == 0 || j == 0 ) { + set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), + cp->set_op->o_tmpmemctx ); + if ( set == NULL ) { + break; + } + BER_BVZERO( &set[ 0 ] ); + break; + } + + set = cp->set_op->o_tmpcalloc( i * j + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( set == NULL ) { break; @@ -232,17 +302,36 @@ slap_set_join( struct berval bv; long k; - bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len; - bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1, - cp->set_op->o_tmpmemctx ); - if ( bv.bv_val == NULL ) { - slap_set_dispose( cp, set, 0 ); - set = NULL; - goto done; + /* don't concatenate with the empty string */ + if ( BER_BVISEMPTY( &lset[ i ] ) ) { + ber_dupbv_x( &bv, &rset[ j ], cp->set_op->o_tmpmemctx ); + if ( bv.bv_val == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + set = NULL; + goto done; + } + + } else if ( BER_BVISEMPTY( &rset[ j ] ) ) { + ber_dupbv_x( &bv, &lset[ i ], cp->set_op->o_tmpmemctx ); + if ( bv.bv_val == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + set = NULL; + goto done; + } + + } else { + bv.bv_len = lset[ i ].bv_len + rset[ j ].bv_len; + bv.bv_val = cp->set_op->o_tmpalloc( bv.bv_len + 1, + cp->set_op->o_tmpmemctx ); + if ( bv.bv_val == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + set = NULL; + goto done; + } + AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len ); + AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len ); + bv.bv_val[ bv.bv_len ] = '\0'; } - AC_MEMCPY( bv.bv_val, lset[ i ].bv_val, lset[ i ].bv_len ); - AC_MEMCPY( &bv.bv_val[ lset[ i ].bv_len ], rset[ j ].bv_val, rset[ j ].bv_len ); - bv.bv_val[ bv.bv_len ] = '\0'; for ( k = 0; k < last; k++ ) { if ( bvmatch( &set[ k ], &bv ) ) { @@ -264,12 +353,19 @@ slap_set_join( } done:; - if ( !( op_flags & SLAP_SET_LREFARR ) && lset != NULL ) { - cp->set_op->o_tmpfree( lset, cp->set_op->o_tmpmemctx ); - } + if ( lset ) slap_set_dispose( cp, lset, SLAP_SET_LREF2REF( op_flags ) ); + if ( rset ) slap_set_dispose( cp, rset, SLAP_SET_RREF2REF( op_flags ) ); + +done2:; + if ( LogTest( LDAP_DEBUG_ACL ) ) { + if ( BER_BVISNULL( set ) ) { + Debug( LDAP_DEBUG_ACL, " ACL set: empty\n", 0, 0, 0 ); - if ( !( op_flags & SLAP_SET_RREFARR ) && rset != NULL ) { - cp->set_op->o_tmpfree( rset, cp->set_op->o_tmpmemctx ); + } else { + for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) { + Debug( LDAP_DEBUG_ACL, " ACL set[%ld]=%s\n", i, set[i].bv_val, 0 ); + } + } } return set; @@ -283,9 +379,11 @@ set_chase( SLAP_SET_GATHER gatherer, int i; if ( set == NULL ) { - set = cp->set_op->o_tmpcalloc( 1, sizeof(struct berval), + set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); - BER_BVZERO( set ); + if ( set != NULL ) { + BER_BVZERO( &set[ 0 ] ); + } return set; } @@ -293,22 +391,22 @@ set_chase( SLAP_SET_GATHER gatherer, return set; } - nset = cp->set_op->o_tmpcalloc( 1, sizeof(struct berval), cp->set_op->o_tmpmemctx ); + nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( nset == NULL ) { - slap_set_dispose( cp, set, 0 ); + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); return NULL; } for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) { - vals = (gatherer)( cp, &set[ i ], desc ); + vals = gatherer( cp, &set[ i ], desc ); if ( vals != NULL ) { nset = slap_set_join( cp, nset, '|', vals ); } } - slap_set_dispose( cp, set, 0 ); + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); if ( closure ) { for ( i = 0; !BER_BVISNULL( &nset[ i ] ); i++ ) { - vals = (gatherer)( cp, &nset[ i ], desc ); + vals = gatherer( cp, &nset[ i ], desc ); if ( vals != NULL ) { nset = slap_set_join( cp, nset, '|', vals ); if ( nset == NULL ) { @@ -321,6 +419,127 @@ set_chase( SLAP_SET_GATHER gatherer, return nset; } + +static BerVarray +set_parents( SetCookie *cp, BerVarray set ) +{ + int i, j, last; + struct berval bv, pbv; + BerVarray nset, vals; + + if ( set == NULL ) { + set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), + cp->set_op->o_tmpmemctx ); + if ( set != NULL ) { + BER_BVZERO( &set[ 0 ] ); + } + return set; + } + + if ( BER_BVISNULL( &set[ 0 ] ) ) { + return set; + } + + nset = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); + if ( nset == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + return NULL; + } + + BER_BVZERO( &nset[ 0 ] ); + + for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) { + int level = 1; + + pbv = bv = set[ i ]; + for ( ; !BER_BVISEMPTY( &pbv ); dnParent( &bv, &pbv ) ) { + level++; + bv = pbv; + } + + vals = cp->set_op->o_tmpcalloc( level + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); + if ( vals == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + ber_bvarray_free_x( nset, cp->set_op->o_tmpmemctx ); + return NULL; + } + BER_BVZERO( &vals[ 0 ] ); + last = 0; + + bv = set[ i ]; + for ( j = 0 ; j < level ; j++ ) { + ber_dupbv_x( &vals[ last ], &bv, cp->set_op->o_tmpmemctx ); + last++; + dnParent( &bv, &bv ); + } + BER_BVZERO( &vals[ last ] ); + + nset = slap_set_join( cp, nset, '|', vals ); + } + + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + + return nset; +} + + + +static BerVarray +set_parent( SetCookie *cp, BerVarray set, int level ) +{ + int i, j, last; + struct berval bv; + BerVarray nset; + + if ( set == NULL ) { + set = cp->set_op->o_tmpcalloc( 1, sizeof( struct berval ), + cp->set_op->o_tmpmemctx ); + if ( set != NULL ) { + BER_BVZERO( &set[ 0 ] ); + } + return set; + } + + if ( BER_BVISNULL( &set[ 0 ] ) ) { + return set; + } + + nset = cp->set_op->o_tmpcalloc( slap_set_size( set ) + 1, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); + if ( nset == NULL ) { + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + return NULL; + } + + BER_BVZERO( &nset[ 0 ] ); + last = 0; + + for ( i = 0; !BER_BVISNULL( &set[ i ] ); i++ ) { + bv = set[ i ]; + + for ( j = 0 ; j < level ; j++ ) { + dnParent( &bv, &bv ); + } + + for ( j = 0; !BER_BVISNULL( &nset[ j ] ); j++ ) { + if ( bvmatch( &bv, &nset[ j ] ) ) + { + break; + } + } + + if ( BER_BVISNULL( &nset[ j ] ) ) { + ber_dupbv_x( &nset[ last ], &bv, cp->set_op->o_tmpmemctx ); + last++; + } + } + + BER_BVZERO( &nset[ last ] ); + + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); + + return nset; +} + int slap_set_filter( SLAP_SET_GATHER gatherer, SetCookie *cp, struct berval *fbv, @@ -329,13 +548,13 @@ slap_set_filter( SLAP_SET_GATHER gatherer, #define STACK_SIZE 64 #define IS_SET(x) ( (unsigned long)(x) >= 256 ) #define IS_OP(x) ( (unsigned long)(x) < 256 ) -#define SF_ERROR(x) do { rc = -1; goto _error; } while (0) -#define SF_TOP() ( (BerVarray)( (stp < 0) ? 0 : stack[ stp ] ) ) -#define SF_POP() ( (BerVarray)( (stp < 0) ? 0 : stack[ stp-- ] ) ) +#define SF_ERROR(x) do { rc = -1; goto _error; } while ( 0 ) +#define SF_TOP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp ] ) ) +#define SF_POP() ( (BerVarray)( ( stp < 0 ) ? 0 : stack[ stp-- ] ) ) #define SF_PUSH(x) do { \ - if (stp >= (STACK_SIZE - 1)) SF_ERROR(overflow); \ + if ( stp >= ( STACK_SIZE - 1 ) ) SF_ERROR( overflow ); \ stack[ ++stp ] = (BerVarray)(long)(x); \ - } while (0) + } while ( 0 ) BerVarray set, lset; BerVarray stack[ STACK_SIZE ] = { 0 }; @@ -380,7 +599,7 @@ slap_set_filter( SLAP_SET_GATHER gatherer, SF_POP(); set = slap_set_join( cp, lset, op, set ); if ( set == NULL ) { - SF_ERROR(memory); + SF_ERROR( memory ); } SF_PUSH( set ); set = NULL; @@ -421,18 +640,18 @@ slap_set_filter( SLAP_SET_GATHER gatherer, if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) { SF_ERROR( syntax ); } - for ( len = 0; ( c = *filter++ ) && (c != /* [ */ ']'); len++ ) + for ( len = 0; ( c = *filter++ ) && ( c != /* [ */ ']' ); len++ ) ; if ( c == 0 ) { - SF_ERROR(syntax); + SF_ERROR( syntax ); } - set = cp->set_op->o_tmpcalloc( 2, sizeof(struct berval), + set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( set == NULL ) { - SF_ERROR(memory); + SF_ERROR( memory ); } - set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof(char), + set->bv_val = cp->set_op->o_tmpcalloc( len + 1, sizeof( char ), cp->set_op->o_tmpmemctx ); if ( BER_BVISNULL( set ) ) { SF_ERROR( memory ); @@ -444,11 +663,44 @@ slap_set_filter( SLAP_SET_GATHER gatherer, break; case '-': - c = *filter++; - if ( c != '>' ) { - SF_ERROR( syntax ); + if ( ( SF_TOP() == (void *)'/' ) + && ( *filter == '*' || ASCII_DIGIT( *filter ) ) ) + { + SF_POP(); + + if ( *filter == '*' ) { + set = set_parents( cp, SF_POP() ); + filter++; + + } else { + char *next = NULL; + long parent = strtol( filter, &next, 10 ); + + if ( next == filter ) { + SF_ERROR( syntax ); + } + + set = SF_POP(); + if ( parent != 0 ) { + set = set_parent( cp, set, parent ); + } + filter = next; + } + + if ( set == NULL ) { + SF_ERROR( memory ); + } + + SF_PUSH( set ); + set = NULL; + break; + } else { + c = *filter++; + if ( c != '>' ) { + SF_ERROR( syntax ); + } + /* fall through to next case */ } - /* fall through to next case */ case '/': if ( IS_OP( SF_TOP() ) ) { @@ -458,27 +710,27 @@ slap_set_filter( SLAP_SET_GATHER gatherer, break; default: - if ( ( c != '_' ) - && ( c < 'A' || c > 'Z' ) - && ( c < 'a' || c > 'z' ) ) - { + if ( !AD_LEADCHAR( c ) ) { SF_ERROR( syntax ); } filter--; for ( len = 1; - ( c = filter[ len ] ) - && ( ( c >= '0' && c <= '9' ) - || ( c >= 'A' && c <= 'Z' ) - || ( c >= 'a' && c <= 'z' ) ); - len++ ) - /* count */ ; + ( c = filter[ len ] ) && AD_CHAR( c ); + len++ ) + { + /* count */ + if ( c == '-' && !AD_CHAR( filter[ len + 1 ] ) ) { + break; + } + } if ( len == 4 && memcmp( "this", filter, len ) == 0 ) { + assert( !BER_BVISNULL( target ) ); if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) { SF_ERROR( syntax ); } - set = cp->set_op->o_tmpcalloc( 2, sizeof(struct berval), + set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( set == NULL ) { SF_ERROR( memory ); @@ -495,15 +747,15 @@ slap_set_filter( SLAP_SET_GATHER gatherer, if ( ( SF_TOP() == (void *)'/' ) || IS_SET( SF_TOP() ) ) { SF_ERROR( syntax ); } - set = cp->set_op->o_tmpcalloc( 2, sizeof(struct berval), + if ( BER_BVISNULL( user ) ) { + SF_ERROR( memory ); + } + set = cp->set_op->o_tmpcalloc( 2, sizeof( struct berval ), cp->set_op->o_tmpmemctx ); if ( set == NULL ) { SF_ERROR( memory ); } ber_dupbv_x( set, user, cp->set_op->o_tmpmemctx ); - if ( BER_BVISNULL( set ) ) { - SF_ERROR( memory ); - } BER_BVZERO( &set[ 1 ] ); } else if ( SF_TOP() != (void *)'/' ) { @@ -569,11 +821,11 @@ slap_set_filter( SLAP_SET_GATHER gatherer, _error: if ( IS_SET( set ) ) { - slap_set_dispose( cp, set, 0 ); + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); } while ( ( set = SF_POP() ) ) { if ( IS_SET( set ) ) { - slap_set_dispose( cp, set, 0 ); + ber_bvarray_free_x( set, cp->set_op->o_tmpmemctx ); } } return rc;