ITS#2082: idl_intersection fix

undifdef -DBDB_IDL_MULTI

diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h
index 18d2ab941999e43e04352a8956cc099844d17316..d724733552cf6994e43c9eea0765e828c8354759 100644 (file)
--- a/servers/slapd/back-bdb/back-bdb.h
+++ b/servers/slapd/back-bdb/back-bdb.h
@@ -15,7 +15,6 @@
 
 LDAP_BEGIN_DECL
 
-#define BDB_IDL_MULTI          1
 /* #define BDB_HIER            1 */
 
 #define DN_BASE_PREFIX         SLAP_INDEX_EQUALITY_PREFIX
@@ -50,22 +49,14 @@ LDAP_BEGIN_DECL
 /* The bdb on-disk entry format is pretty space-inefficient. Average
  * sized user entries are 3-4K each. You need at least two entries to
  * fit into a single database page, more is better. 64K is BDB's
- * upper bound. The same issues arise with IDLs in the index databases,
- * but it's nearly impossible to avoid overflows there.
- *
- * When using BDB_IDL_MULTI, the IDL size is no longer an issue. Smaller
- * pages are better for concurrency.
+ * upper bound. Smaller pages are better for concurrency.
  */
 #ifndef BDB_ID2ENTRY_PAGESIZE
 #define        BDB_ID2ENTRY_PAGESIZE   16384
 #endif
 
 #ifndef BDB_PAGESIZE
-#ifdef BDB_IDL_MULTI
 #define        BDB_PAGESIZE    4096    /* BDB's original default */
-#else
-#define        BDB_PAGESIZE    16384
-#endif
 #endif
 
 #define DEFAULT_CACHE_SIZE     1000

diff --git a/servers/slapd/back-bdb/dbcache.c b/servers/slapd/back-bdb/dbcache.c
index 2110554fac0f59461ca97dcd28927e4276d0e68c..7d8d082590125beaf3a8a950444c8fc03a7820d0 100644 (file)
--- a/servers/slapd/back-bdb/dbcache.c
+++ b/servers/slapd/back-bdb/dbcache.c
@@ -101,10 +101,8 @@ bdb_db_cache(
 
        rc = db->bdi_db->set_pagesize( db->bdi_db, BDB_PAGESIZE );
        rc = db->bdi_db->set_h_hash( db->bdi_db, bdb_db_hash );
-#ifdef BDB_IDL_MULTI
        rc = db->bdi_db->set_flags( db->bdi_db, DB_DUP | DB_DUPSORT );
        rc = db->bdi_db->set_dup_compare( db->bdi_db, bdb_bt_compare );
-#endif
 
        file = ch_malloc( strlen( name ) + sizeof(BDB_SUFFIX) );
        sprintf( file, "%s" BDB_SUFFIX, name );

diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index 9dcde2352c0852e5227db74d08898331c0353e4e..ecc856cb0e41bc01bc7a02a702991b3ec2432aba 100644 (file)
--- a/servers/slapd/back-bdb/idl.c
+++ b/servers/slapd/back-bdb/idl.c
@@ -254,21 +254,22 @@ bdb_idl_fetch_key(
        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
        int rc;
        DBT data;
-#ifdef BDB_IDL_MULTI
-       /* buf must be large enough to grab the entire IDL in one
-        * get(), otherwise BDB 4 will leak resources on subsequent
-        * get's. We can safely call get() twice - once for the data,
-        * and once to get the DB_NOTFOUND result meaning there's
-        * no more data. See ITS#2040 for details.
-        */
-       ID buf[BDB_IDL_DB_SIZE*5];
        DBC *cursor;
        ID *i;
        void *ptr;
        size_t len;
        int rc2;
        int flags = bdb->bi_db_opflags | DB_MULTIPLE;
-#endif
+
+       /* buf must be large enough to grab the entire IDL in one
+        * get(), otherwise BDB 4 will leak resources on subsequent
+        * get's. We can safely call get() twice - once for the data,
+        * and once to get the DB_NOTFOUND result meaning there's
+        * no more data. See ITS#2040 for details. This bug is fixed
+        * in BDB 4.1 so a smaller buffer will work if stack space is
+        * too limited.
+        */
+       ID buf[BDB_IDL_DB_SIZE*5];
 
        {
                char buf[16];
@@ -286,7 +287,6 @@ bdb_idl_fetch_key(
 
        DBTzero( &data );
 
-#ifdef BDB_IDL_MULTI
        data.data = buf;
        data.ulen = sizeof(buf);
        data.flags = DB_DBT_USERMEM;
@@ -356,14 +356,6 @@ bdb_idl_fetch_key(
 #endif
                return rc2;
        }
-#else /* BDB_IDL_MULTI */
-       data.data = ids;
-       data.ulen = BDB_IDL_UM_SIZEOF;
-       data.flags = DB_DBT_USERMEM;
-       /* fetch it */
-       rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
-#endif /* BDB_IDL_MULTI */
-
        if( rc == DB_NOTFOUND ) {
                return rc;
 
@@ -421,13 +413,9 @@ bdb_idl_insert_key(
        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
        int     rc;
        DBT data;
-#ifdef BDB_IDL_MULTI
        DBC *cursor;
        ID lo, hi, tmp;
        char *err;
-#else
-       ID ids[BDB_IDL_DB_SIZE];
-#endif
 
        {
                char buf[16];
@@ -445,7 +433,6 @@ bdb_idl_insert_key(
        assert( id != NOID );
 
        DBTzero( &data );
-#ifdef BDB_IDL_MULTI
        data.size = sizeof( ID );
        data.ulen = data.size;
        data.flags = DB_DBT_USERMEM;
@@ -593,104 +580,14 @@ fail:
                return rc;
        }
        rc = cursor->c_close( cursor );
-#else  /* !BDB_IDL_MULTI */
-       data.data = ids;
-       data.ulen = sizeof ids;
-       data.flags = DB_DBT_USERMEM;
-
-       /* fetch the key for read/modify/write */
-       rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
-
-       if( rc == DB_NOTFOUND ) {
-               ids[0] = 1;
-               ids[1] = id;
-               data.size = 2 * sizeof( ID );
-
-       } else if ( rc != 0 ) {
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, "bdb_idl_insert_key: get failed: %s (%d)\n", 
-                       db_strerror(rc), rc, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
-                       "get failed: %s (%d)\n",
-                       db_strerror(rc), rc, 0 );
-#endif
-               return rc;
-
-       } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
-               /* size not multiple of ID size */
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, 
-                       "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n", 
-                       (long) sizeof( ID ), (long) data.size, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
-                       "odd size: expected %ld multiple, got %ld\n",
-                       (long) sizeof( ID ), (long) data.size, 0 );
-#endif
-               return -1;
-       
-       } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
-               /* size mismatch */
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, 
-                       "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n", 
-                       (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
-                       "get size mismatch: expected %ld, got %ld\n",
-                       (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
-#endif
-               return -1;
-
-       } else if ( BDB_IDL_IS_RANGE(ids) ) {
-               if( id < ids[1] ) {
-                       ids[1] = id;
-               } else if ( ids[2] > id ) {
-                       ids[2] = id;
-               } else {
-                       return 0;
-               }
-
-       } else {
-               rc = bdb_idl_insert( ids, id );
-
-               if( rc == -1 ) {
-#ifdef NEW_LOGGING
-                       LDAP_LOG( INDEX, DETAIL1, "bdb_idl_insert_key: dup\n", 0, 0, 0 );
-#else
-                       Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
-                               0, 0, 0 );
-#endif
-                       return 0;
-               }
-               if( rc != 0 ) {
-#ifdef NEW_LOGGING
-                       LDAP_LOG( INDEX, ERR, 
-                               "bdb_idl_insert_key: insert failed: (%d)\n", rc, 0, 0 );
-#else
-                       Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
-                               "bdb_idl_insert failed (%d)\n",
-                               rc, 0, 0 );
-#endif
-                       
-                       return rc;
-               }
-
-               data.size = BDB_IDL_SIZEOF( ids );
-       }
-
-       /* store the key */
-       rc = db->put( db, tid, key, &data, 0 );
-#endif
-       if( rc != 0 && rc != DB_KEYEXIST ) {
+       if( rc != 0 ) {
 #ifdef NEW_LOGGING
                LDAP_LOG( INDEX, ERR, 
-                       "bdb_idl_insert_key: put failed: %s (%d)\n", 
+                       "bdb_idl_insert_key: c_close failed: %s (%d)\n", 
                        db_strerror(rc), rc, 0 );
 #else
                Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
-                       "put failed: %s (%d)\n",
+                       "c_close failed: %s (%d)\n",
                        db_strerror(rc), rc, 0 );
 #endif
        }
@@ -708,13 +605,9 @@ bdb_idl_delete_key(
        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
        int     rc;
        DBT data;
-#ifdef BDB_IDL_MULTI
        DBC *cursor;
        ID lo, hi, tmp;
        char *err;
-#else
-       ID ids[BDB_IDL_DB_SIZE];
-#endif
 
        {
                char buf[16];
@@ -731,8 +624,6 @@ bdb_idl_delete_key(
        assert( id != NOID );
 
        DBTzero( &data );
-
-#ifdef BDB_IDL_MULTI
        data.data = &tmp;
        data.size = sizeof( id );
        data.ulen = data.size;
@@ -841,103 +732,13 @@ fail:
                return rc;
        }
        rc = cursor->c_close( cursor );
-
-#else  /* BDB_IDL_MULTI */
-
-       data.data = ids;
-       data.ulen = sizeof( ids );
-       data.flags = DB_DBT_USERMEM;
-
-       /* fetch the key for read/modify/write */
-       rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
-
-       if ( rc != 0 ) {
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: get failed: %s (%d)\n", 
-                       db_strerror(rc), rc, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
-                       "get failed: %s (%d)\n",
-                       db_strerror(rc), rc, 0 );
-#endif
-               return rc;
-
-       } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
-               /* size not multiple of ID size */
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, 
-                       "bdb_idl_delete_key: odd size: expected: %ld multiple, got %ld\n", 
-                       (long) sizeof( ID ), (long) data.size, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
-                       "odd size: expected %ld multiple, got %ld\n",
-                       (long) sizeof( ID ), (long) data.size, 0 );
-#endif
-               return -1;
-       
-       } else if ( BDB_IDL_IS_RANGE(ids) ) {
-               return 0;
-
-       } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
-               /* size mismatch */
-#ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, 
-                       "bdb_idl_delete_key: get size mismatch: expected: %ld, got %ld\n", 
-                       (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
-#else
-               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
-                       "get size mismatch: expected %ld, got %ld\n",
-                       (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
-#endif
-               return -1;
-
-       } else {
-               rc = idl_delete( ids, id );
-
-               if( rc != 0 ) {
-#ifdef NEW_LOGGING
-                       LDAP_LOG( INDEX, ERR, 
-                               "bdb_idl_delete_key: delete failed: (%d)\n", rc, 0, 0 );
-#else
-                       Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
-                               "idl_delete failed (%d)\n",
-                               rc, 0, 0 );
-#endif
-                       return rc;
-               }
-
-               if( ids[0] == 0 ) {
-                       /* delete the key */
-                       rc = db->del( db, tid, key, 0 );
-                       if( rc != 0 ) {
-#ifdef NEW_LOGGING
-                               LDAP_LOG( INDEX, ERR, 
-                                       "bdb_idl_delete_key: delete failed: %s (%d)\n",
-                                       db_strerror(rc), rc, 0 );
-#else
-                               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
-                                       "delete failed: %s (%d)\n",
-                                       db_strerror(rc), rc, 0 );
-#endif
-                       }
-                       return rc;
-               }
-
-               data.size = (ids[0]+1) * sizeof( ID );
-       }
-
-       /* store the key */
-       rc = db->put( db, tid, key, &data, 0 );
-
-#endif /* BDB_IDL_MULTI */
-
        if( rc != 0 ) {
 #ifdef NEW_LOGGING
-               LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: put failed: %s (%d)\n", 
+               LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: c_close failed: %s (%d)\n", 
                        db_strerror(rc), rc, 0 );
 #else
                Debug( LDAP_DEBUG_ANY,
-                       "=> bdb_idl_delete_key: put failed: %s (%d)\n",
+                       "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
                        db_strerror(rc), rc, 0 );
 #endif
        }
@@ -975,21 +776,28 @@ bdb_idl_intersection(
                return 0;
        }
 
-       if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
-               a[1] = idmin;
-               a[2] = idmax;
-               return 0;
-       }
-
        if ( BDB_IDL_IS_RANGE( a ) ) {
-               ID *tmp = a;
-               a = b;
-               b = tmp;
-               swap = 1;
+               if ( BDB_IDL_IS_RANGE(b) ) {
+               /* If both are ranges, just shrink the boundaries */
+                       a[1] = idmin;
+                       a[2] = idmax;
+                       return 0;
+               } else {
+               /* Else swap so that b is the range, a is a list */
+                       ID *tmp = a;
+                       a = b;
+                       b = tmp;
+                       swap = 1;
+               }
        }
 
-       if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
-               BDB_IDL_LAST( b ) >= idmax) {
+       /* If a range completely covers the list, the result is
+        * just the list. If idmin to idmax is contiguous, just
+        * turn it into a range.
+        */
+       if ( BDB_IDL_IS_RANGE( b )
+               && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
+               && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
                if (idmax - idmin + 1 == a[0])
                {
                        a[0] = NOID;
@@ -999,15 +807,14 @@ bdb_idl_intersection(
                goto done;
        }
 
+       /* Fine, do the intersection one element at a time.
+        * First advance to idmin in both IDLs.
+        */
+       cursora = cursorb = idmin;
        ida = bdb_idl_first( a, &cursora );
        idb = bdb_idl_first( b, &cursorb );
        cursorc = 0;
 
-       while( ida < idmin )
-               ida = bdb_idl_next( a, &cursora );
-       while( idb < idmin )
-               idb = bdb_idl_next( b, &cursorb );
-
        while( ida <= idmax || idb <= idmax ) {
                if( ida == idb ) {
                        a[++cursorc] = ida;