git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/index.c

   1 /* index.c - routines for dealing with attribute indexes */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11
  12 #include <ac/string.h>
  13 #include <ac/socket.h>
  14
  15 #include "slap.h"
  16 #include "back-bdb.h"
  17 #include "lutil_hash.h"
  18
  19 static char presence_keyval[LUTIL_HASH_BYTES] = {0,0,0,1};
  20 static struct berval presence_key = {LUTIL_HASH_BYTES, presence_keyval};
  21
  22 static slap_mask_t index_mask(
  23         Backend *be,
  24         AttributeDescription *desc,
  25         struct berval *atname )
  26 {
  27         AttributeType *at;
  28         slap_mask_t mask = 0;
  29
  30         bdb_attr_mask( be->be_private, desc, &mask );
  31
  32         if( mask ) {
  33                 *atname = desc->ad_cname;
  34                 return mask;
  35         }
  36
  37         /* If there is a tagging option, did we ever index the base
  38          * type? If so, check for mask, otherwise it's not there.
  39          */
  40         if( slap_ad_is_tagged( desc ) && desc != desc->ad_type->sat_ad ) {
  41                 /* has tagging option */
  42                 bdb_attr_mask( be->be_private, desc->ad_type->sat_ad, &mask );
  43
  44                 if ( mask && ( mask ^ SLAP_INDEX_NOTAGS ) ) {
  45                         *atname = desc->ad_type->sat_cname;
  46                         return mask;
  47                 }
  48         }
  49
  50         /* see if supertype defined mask for its subtypes */
  51         for( at = desc->ad_type; at != NULL ; at = at->sat_sup ) {
  52                 /* If no AD, we've never indexed this type */
  53                 if ( !at->sat_ad ) continue;
  54
  55                 bdb_attr_mask( be->be_private, at->sat_ad, &mask );
  56
  57                 if ( mask && ( mask ^ SLAP_INDEX_NOSUBTYPES ) ) {
  58                         *atname = at->sat_cname;
  59                         return mask;
  60                 }
  61         }
  62
  63         return 0;
  64 }
  65
  66 int bdb_index_is_indexed(
  67         Backend *be,
  68         AttributeDescription *desc )
  69 {
  70         slap_mask_t mask;
  71         struct berval prefix;
  72
  73         mask = index_mask( be, desc, &prefix );
  74
  75         if( mask == 0 ) {
  76                 return LDAP_INAPPROPRIATE_MATCHING;
  77         }
  78
  79         return LDAP_SUCCESS;
  80 }
  81
  82 int bdb_index_param(
  83         Backend *be,
  84         AttributeDescription *desc,
  85         int ftype,
  86         DB **dbp,
  87         slap_mask_t *maskp,
  88         struct berval *prefixp )
  89 {
  90         int rc;
  91         slap_mask_t mask;
  92         DB *db;
  93
  94         mask = index_mask( be, desc, prefixp );
  95
  96         if( mask == 0 ) {
  97                 return LDAP_INAPPROPRIATE_MATCHING;
  98         }
  99
 100         rc = bdb_db_cache( be, NULL, prefixp->bv_val, &db );
 101
 102         if( rc != LDAP_SUCCESS ) {
 103                 return rc;
 104         }
 105
 106         switch( ftype ) {
 107         case LDAP_FILTER_PRESENT:
 108                 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
 109                         *prefixp = presence_key;
 110                         goto done;
 111                 }
 112                 break;
 113
 114         case LDAP_FILTER_APPROX:
 115                 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
 116                         goto done;
 117                 }
 118                 /* fall thru */
 119
 120         case LDAP_FILTER_EQUALITY:
 121                 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
 122                         goto done;
 123                 }
 124                 break;
 125
 126         case LDAP_FILTER_SUBSTRINGS:
 127                 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
 128                         goto done;
 129                 }
 130                 break;
 131
 132         default:
 133                 return LDAP_OTHER;
 134         }
 135
 136         return LDAP_INAPPROPRIATE_MATCHING;
 137
 138 done:
 139         *dbp = db;
 140         *maskp = mask;
 141         return LDAP_SUCCESS;
 142 }
 143
 144 static int indexer(
 145         Operation *op,
 146         DB_TXN *txn,
 147         AttributeDescription *ad,
 148         struct berval *atname,
 149         BerVarray vals,
 150         BerVarray xvals,
 151         ID id,
 152         int opid,
 153         slap_mask_t mask )
 154 {
 155         int rc, i, j;
 156         const char *text;
 157         DB *db;
 158         struct berval *keys, *xkeys = NULL;
 159         void *mark;
 160
 161         assert( mask );
 162
 163         rc = bdb_db_cache( op->o_bd, txn, atname->bv_val, &db );
 164
 165         if ( rc != LDAP_SUCCESS ) {
 166 #ifdef NEW_LOGGING
 167                 LDAP_LOG( INDEX, ERR,
 168                         "bdb_index_read: Could not open DB %s\n",
 169                         atname->bv_val, 0, 0 );
 170 #else
 171                 Debug( LDAP_DEBUG_ANY,
 172                         "bdb_index_read: Could not open DB %s\n",
 173                         atname->bv_val, 0, 0 );
 174 #endif
 175                 return LDAP_OTHER;
 176         }
 177
 178         mark = sl_mark(op->o_tmpmemctx);
 179
 180         /* For a delete op, make sure we're deleting the entire
 181          * attribute (xvals == NULL) before changing the presence
 182          * index. xvals is only non-NULL when deleting part of an attribute.
 183          */
 184         if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) && xvals == NULL ) {
 185                 rc = bdb_key_change( op->o_bd, db, txn, &presence_key, id, opid );
 186                 if( rc ) {
 187                         goto done;
 188                 }
 189         }
 190
 191         if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
 192                 rc = ad->ad_type->sat_equality->smr_indexer(
 193                         LDAP_FILTER_EQUALITY,
 194                         mask,
 195                         ad->ad_type->sat_syntax,
 196                         ad->ad_type->sat_equality,
 197                         atname, vals, &keys, op->o_tmpmemctx );
 198
 199                 if( rc == LDAP_SUCCESS && keys != NULL ) {
 200                         /* xvals is only provided on deletes. Generate the keys for
 201                          * xvals, representing all of the keys that will exist in
 202                          * the index when we're done. If we find a delete key that
 203                          * is in the xkeys, nullify the delete on that key.
 204                          */
 205                         if( xvals ) {
 206                                 rc = ad->ad_type->sat_equality->smr_indexer(
 207                                         LDAP_FILTER_EQUALITY, mask,
 208                                         ad->ad_type->sat_syntax,
 209                                         ad->ad_type->sat_equality,
 210                                         atname, xvals, &xkeys,
 211                                         op->o_tmpmemctx );
 212
 213                                 for( i=0; keys[i].bv_val; i++ ) {
 214                                         for( j=0; xkeys[j].bv_val != NULL; j++ ) {
 215                                                 if( bvmatch( &keys[i], &xkeys[j] ) ) {
 216                                                         keys[i].bv_len = 0;
 217                                                 }
 218                                         }
 219                                 }
 220                         }
 221                         for( i=0; keys[i].bv_val != NULL; i++ ) {
 222                                 /* ignore nullified keys */
 223                                 if( keys[i].bv_len == 0 ) continue;
 224                                 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
 225                                 if( rc ) break;
 226                         }
 227                         if( xkeys ) {
 228                                 ber_bvarray_free_x( xkeys, op->o_tmpmemctx );
 229                                 xkeys = NULL;
 230                         }
 231                         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 232                         if( rc ) goto done;
 233                 }
 234                 rc = LDAP_SUCCESS;
 235         }
 236
 237         if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
 238                 rc = ad->ad_type->sat_approx->smr_indexer(
 239                         LDAP_FILTER_APPROX,
 240                         mask,
 241                         ad->ad_type->sat_syntax,
 242                         ad->ad_type->sat_approx,
 243                         atname, vals, &keys, op->o_tmpmemctx );
 244
 245                 if( rc == LDAP_SUCCESS && keys != NULL ) {
 246                         /* nullify duplicate keys */
 247                         for( i=0; keys[i].bv_val; i++ ) {
 248                                 if( !keys[i].bv_len ) continue;
 249                                 for( j=i+1; keys[j].bv_val; j++ ) {
 250                                         if( bvmatch( &keys[i], &keys[j] ) ) {
 251                                                 keys[j].bv_len = 0;
 252                                                 break;
 253                                         }
 254                                 }
 255                         }
 256                         if( xvals ) {
 257                                 rc = ad->ad_type->sat_equality->smr_indexer(
 258                                         LDAP_FILTER_APPROX, mask,
 259                                         ad->ad_type->sat_syntax,
 260                                         ad->ad_type->sat_approx,
 261                                         atname, xvals, &xkeys,
 262                                         op->o_tmpmemctx );
 263
 264                                 for( i=0; keys[i].bv_val; i++ ) {
 265                                         for( j=0; xkeys[j].bv_val != NULL; j++ ) {
 266                                                 if( bvmatch( &keys[i], &xkeys[j] ) ) {
 267                                                         keys[i].bv_len = 0;
 268                                                 }
 269                                         }
 270                                 }
 271                         }
 272                         for( i=0; keys[i].bv_val != NULL; i++ ) {
 273                                 /* ignore nullified keys */
 274                                 if( keys[i].bv_len == 0 ) continue;
 275                                 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
 276                                 if( rc ) break;
 277                         }
 278                         if( xkeys ) {
 279                                 ber_bvarray_free_x( xkeys, op->o_tmpmemctx );
 280                                 xkeys = NULL;
 281                         }
 282                         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 283                         if( rc ) goto done;
 284                 }
 285
 286                 rc = LDAP_SUCCESS;
 287         }
 288
 289         if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
 290                 rc = ad->ad_type->sat_substr->smr_indexer(
 291                         LDAP_FILTER_SUBSTRINGS,
 292                         mask,
 293                         ad->ad_type->sat_syntax,
 294                         ad->ad_type->sat_substr,
 295                         atname, vals, &keys, op->o_tmpmemctx );
 296
 297                 if( rc == LDAP_SUCCESS && keys != NULL ) {
 298                         /* nullify duplicate keys */
 299                         for( i=0; keys[i].bv_val; i++ ) {
 300                                 if( !keys[i].bv_len ) continue;
 301                                 for( j=i+1; keys[j].bv_val; j++ ) {
 302                                         if( bvmatch( &keys[i], &keys[j] ) ) {
 303                                                 keys[j].bv_len = 0;
 304                                                 break;
 305                                         }
 306                                 }
 307                         }
 308                         if( xvals ) {
 309                                 rc = ad->ad_type->sat_equality->smr_indexer(
 310                                         LDAP_FILTER_SUBSTRINGS, mask,
 311                                         ad->ad_type->sat_syntax,
 312                                         ad->ad_type->sat_substr,
 313                                         atname, xvals, &xkeys,
 314                                         op->o_tmpmemctx );
 315
 316                                 for( i=0; keys[i].bv_val; i++ ) {
 317                                         for( j=0; xkeys[j].bv_val != NULL; j++ ) {
 318                                                 if( bvmatch( &keys[i], &xkeys[j] ) ) {
 319                                                         keys[i].bv_len = 0;
 320                                                 }
 321                                         }
 322                                 }
 323                         }
 324                         for( i=0; keys[i].bv_val != NULL; i++ ) {
 325                                 /* ignore nullified keys */
 326                                 if ( keys[i].bv_len == 0 ) continue;
 327                                 bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
 328                                 if( rc ) break;
 329                         }
 330                         if( xkeys ) {
 331                                 ber_bvarray_free_x( xkeys, op->o_tmpmemctx );
 332                                 xkeys = NULL;
 333                         }
 334                         ber_bvarray_free_x( keys, op->o_tmpmemctx );
 335                         if( rc ) goto done;
 336                 }
 337
 338                 rc = LDAP_SUCCESS;
 339         }
 340
 341 done:
 342         sl_release( mark, op->o_tmpmemctx );
 343         return rc;
 344 }
 345
 346 static int index_at_values(
 347         Operation *op,
 348         DB_TXN *txn,
 349         AttributeDescription *ad,
 350         AttributeType *type,
 351         struct berval *tags,
 352         BerVarray vals,
 353         BerVarray xvals,
 354         ID id,
 355         int opid )
 356 {
 357         int rc;
 358         slap_mask_t mask = 0;
 359
 360         if( type->sat_sup ) {
 361                 /* recurse */
 362                 rc = index_at_values( op, txn, NULL,
 363                         type->sat_sup, tags,
 364                         vals, xvals, id, opid );
 365
 366                 if( rc ) return rc;
 367         }
 368
 369         /* If this type has no AD, we've never used it before */
 370         if( type->sat_ad ) {
 371                 bdb_attr_mask( op->o_bd->be_private, type->sat_ad, &mask );
 372                 ad = type->sat_ad;
 373         }
 374
 375         if( mask ) {
 376                 rc = indexer( op, txn, ad, &type->sat_cname,
 377                         vals, xvals, id, opid,
 378                         mask );
 379
 380                 if( rc ) return rc;
 381         }
 382
 383         if( tags->bv_len ) {
 384                 AttributeDescription *desc;
 385
 386                 mask = 0;
 387
 388                 desc = ad_find_tags( type, tags );
 389                 if( desc ) {
 390                         bdb_attr_mask( op->o_bd->be_private, desc, &mask );
 391                 }
 392
 393                 if( mask ) {
 394                         rc = indexer( op, txn, desc, &desc->ad_cname,
 395                                 vals, xvals, id, opid,
 396                                 mask );
 397
 398                         if( rc ) {
 399                                 return rc;
 400                         }
 401                 }
 402         }
 403
 404         return LDAP_SUCCESS;
 405 }
 406
 407 int bdb_index_values(
 408         Operation *op,
 409         DB_TXN *txn,
 410         AttributeDescription *desc,
 411         BerVarray vals,
 412         BerVarray xvals,
 413         ID id,
 414         int opid )
 415 {
 416         int rc;
 417
 418         rc = index_at_values( op, txn, desc,
 419                 desc->ad_type, &desc->ad_tags,
 420                 vals, xvals, id, opid );
 421
 422         return rc;
 423 }
 424
 425 int
 426 bdb_index_entry(
 427         Operation *op,
 428         DB_TXN *txn,
 429         int opid,
 430         Entry   *e )
 431 {
 432         int rc;
 433         Attribute *ap = e->e_attrs;
 434
 435 #ifdef NEW_LOGGING
 436         LDAP_LOG( INDEX, ENTRY, "index_entry: %s (%s) %ld\n",
 437                 opid == SLAP_INDEX_ADD_OP ? "add" : "del", e->e_dn, (long) e->e_id );
 438 #else
 439         Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n",
 440                 opid == SLAP_INDEX_ADD_OP ? "add" : "del",
 441                 (long) e->e_id, e->e_dn );
 442 #endif
 443
 444         /* add each attribute to the indexes */
 445         for ( ; ap != NULL; ap = ap->a_next ) {
 446                 rc = bdb_index_values( op, txn, ap->a_desc,
 447                         ap->a_nvals, NULL, e->e_id, opid );
 448
 449                 if( rc != LDAP_SUCCESS ) {
 450 #ifdef NEW_LOGGING
 451                         LDAP_LOG( INDEX, ENTRY,
 452                                 "index_entry: failure (%d)\n", rc, 0, 0 );
 453 #else
 454                         Debug( LDAP_DEBUG_TRACE,
 455                                 "<= index_entry_%s( %ld, \"%s\" ) failure\n",
 456                                 opid == SLAP_INDEX_ADD_OP ? "add" : "del",
 457                                 (long) e->e_id, e->e_dn );
 458 #endif
 459                         return rc;
 460                 }
 461         }
 462
 463 #ifdef NEW_LOGGING
 464         LDAP_LOG( INDEX, ENTRY, "index_entry: success\n", 0, 0, 0  );
 465 #else
 466         Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n",
 467                 opid == SLAP_INDEX_ADD_OP ? "add" : "del",
 468                 (long) e->e_id, e->e_dn );
 469 #endif
 470
 471         return LDAP_SUCCESS;
 472 }