← Back to branch summary

~ttx/openldap/lucid-gssapi-495418

« back to all changes in this revision

Viewing changes to servers/slapd/back-bdb/dn2id.c

  • Committer: Bazaar Package Importer
  • Author(s): Mathias Gug
  • Date: 2008-07-10 14:45:49 UTC
  • Revision ID: james.westby@ubuntu.com-20080710144549-wck73med0e72gfyo
Tags: upstream-2.4.10
Import upstream version 2.4.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
servers/slapd/back-bdb/dn2id.c
 
1
/* dn2id.c - routines to deal with the dn2id index */
 
2
/* $OpenLDAP: pkg/ldap/servers/slapd/back-bdb/dn2id.c,v 1.137.2.10 2008/05/20 00:14:04 quanah Exp $ */
 
3
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 
4
 *
 
5
 * Copyright 2000-2008 The OpenLDAP Foundation.
 
6
 * All rights reserved.
 
7
 *
 
8
 * Redistribution and use in source and binary forms, with or without
 
9
 * modification, are permitted only as authorized by the OpenLDAP
 
10
 * Public License.
 
11
 *
 
12
 * A copy of this license is available in the file LICENSE in the
 
13
 * top-level directory of the distribution or, alternatively, at
 
14
 * <http://www.OpenLDAP.org/license.html>.
 
15
 */
 
16
 
 
17
#include "portable.h"
 
18
 
 
19
#include <stdio.h>
 
20
#include <ac/string.h>
 
21
 
 
22
#include "back-bdb.h"
 
23
#include "idl.h"
 
24
#include "lutil.h"
 
25
 
 
26
#define bdb_dn2id_lock                                  BDB_SYMBOL(dn2id_lock)
 
27
 
 
28
static int
 
29
bdb_dn2id_lock( struct bdb_info *bdb, struct berval *dn,
 
30
        int rw, BDB_LOCKER locker, DB_LOCK *lock )
 
31
{
 
32
        int       rc;
 
33
        DBT       lockobj;
 
34
        int       db_rw;
 
35
 
 
36
        if (!locker)
 
37
                return 0;
 
38
 
 
39
        if (rw)
 
40
                db_rw = DB_LOCK_WRITE;
 
41
        else
 
42
                db_rw = DB_LOCK_READ;
 
43
 
 
44
        lockobj.data = dn->bv_val;
 
45
        lockobj.size = dn->bv_len;
 
46
 
 
47
        rc = LOCK_GET(bdb->bi_dbenv, BDB_LOCKID(locker), DB_LOCK_NOWAIT,
 
48
                                        &lockobj, db_rw, lock);
 
49
        return rc;
 
50
}
 
51
 
 
52
#ifndef BDB_HIER
 
53
int
 
54
bdb_dn2id_add(
 
55
        Operation *op,
 
56
        DB_TXN *txn,
 
57
        EntryInfo *eip,
 
58
        Entry           *e )
 
59
{
 
60
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
61
        DB *db = bdb->bi_dn2id->bdi_db;
 
62
        int             rc;
 
63
        DBT             key, data;
 
64
        ID              nid;
 
65
        char            *buf;
 
66
        struct berval   ptr, pdn;
 
67
 
 
68
        Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n",
 
69
                e->e_id, e->e_ndn, 0 );
 
70
        assert( e->e_id != NOID );
 
71
 
 
72
        DBTzero( &key );
 
73
        key.size = e->e_nname.bv_len + 2;
 
74
        key.ulen = key.size;
 
75
        key.flags = DB_DBT_USERMEM;
 
76
        buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 
77
        key.data = buf;
 
78
        buf[0] = DN_BASE_PREFIX;
 
79
        ptr.bv_val = buf + 1;
 
80
        ptr.bv_len = e->e_nname.bv_len;
 
81
        AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
 
82
        ptr.bv_val[ptr.bv_len] = '\0';
 
83
 
 
84
        DBTzero( &data );
 
85
        data.data = &nid;
 
86
        data.size = sizeof( nid );
 
87
        BDB_ID2DISK( e->e_id, &nid );
 
88
 
 
89
        /* store it -- don't override */
 
90
        rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
 
91
        if( rc != 0 ) {
 
92
                Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add 0x%lx: put failed: %s %d\n",
 
93
                        e->e_id, db_strerror(rc), rc );
 
94
                goto done;
 
95
        }
 
96
 
 
97
#ifndef BDB_MULTIPLE_SUFFIXES
 
98
        if( !be_issuffix( op->o_bd, &ptr ))
 
99
#endif
 
100
        {
 
101
                buf[0] = DN_SUBTREE_PREFIX;
 
102
                rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
 
103
                if( rc != 0 ) {
 
104
                        Debug( LDAP_DEBUG_ANY,
 
105
                        "=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n",
 
106
                        e->e_id, ptr.bv_val, rc );
 
107
                        goto done;
 
108
                }
 
109
                
 
110
#ifdef BDB_MULTIPLE_SUFFIXES
 
111
        if( !be_issuffix( op->o_bd, &ptr ))
 
112
#endif
 
113
        {
 
114
                dnParent( &ptr, &pdn );
 
115
        
 
116
                key.size = pdn.bv_len + 2;
 
117
                key.ulen = key.size;
 
118
                pdn.bv_val[-1] = DN_ONE_PREFIX;
 
119
                key.data = pdn.bv_val-1;
 
120
                ptr = pdn;
 
121
 
 
122
                rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 
123
 
 
124
                if( rc != 0 ) {
 
125
                        Debug( LDAP_DEBUG_ANY,
 
126
                                "=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n",
 
127
                                        e->e_id, ptr.bv_val, rc );
 
128
                        goto done;
 
129
                }
 
130
        }
 
131
 
 
132
#ifndef BDB_MULTIPLE_SUFFIXES
 
133
        while( !be_issuffix( op->o_bd, &ptr ))
 
134
#else
 
135
        for (;;)
 
136
#endif
 
137
        {
 
138
                ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 
139
 
 
140
                rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 
141
 
 
142
                if( rc != 0 ) {
 
143
                        Debug( LDAP_DEBUG_ANY,
 
144
                                "=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n",
 
145
                                        e->e_id, ptr.bv_val, rc );
 
146
                        break;
 
147
                }
 
148
#ifdef BDB_MULTIPLE_SUFFIXES
 
149
                if( be_issuffix( op->o_bd, &ptr )) break;
 
150
#endif
 
151
                dnParent( &ptr, &pdn );
 
152
 
 
153
                key.size = pdn.bv_len + 2;
 
154
                key.ulen = key.size;
 
155
                key.data = pdn.bv_val - 1;
 
156
                ptr = pdn;
 
157
        }
 
158
        }
 
159
 
 
160
done:
 
161
        op->o_tmpfree( buf, op->o_tmpmemctx );
 
162
        Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 
163
        return rc;
 
164
}
 
165
 
 
166
int
 
167
bdb_dn2id_delete(
 
168
        Operation *op,
 
169
        DB_TXN *txn,
 
170
        EntryInfo       *eip,
 
171
        Entry           *e )
 
172
{
 
173
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
174
        DB *db = bdb->bi_dn2id->bdi_db;
 
175
        char            *buf;
 
176
        DBT             key;
 
177
        DB_LOCK lock;
 
178
        struct berval   pdn, ptr;
 
179
        int             rc;
 
180
 
 
181
        Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n",
 
182
                e->e_id, e->e_ndn, 0 );
 
183
 
 
184
        DBTzero( &key );
 
185
        key.size = e->e_nname.bv_len + 2;
 
186
        buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 
187
        key.data = buf;
 
188
        key.flags = DB_DBT_USERMEM;
 
189
        buf[0] = DN_BASE_PREFIX;
 
190
        ptr.bv_val = buf+1;
 
191
        ptr.bv_len = e->e_nname.bv_len;
 
192
        AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
 
193
        ptr.bv_val[ptr.bv_len] = '\0';
 
194
 
 
195
        /* We hold this lock until the TXN completes */
 
196
        rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
 
197
        if ( rc ) goto done;
 
198
 
 
199
        /* delete it */
 
200
        rc = db->del( db, txn, &key, 0 );
 
201
        if( rc != 0 ) {
 
202
                Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n",
 
203
                        e->e_id, db_strerror(rc), rc );
 
204
                goto done;
 
205
        }
 
206
 
 
207
#ifndef BDB_MULTIPLE_SUFFIXES
 
208
        if( !be_issuffix( op->o_bd, &ptr ))
 
209
#endif
 
210
        {
 
211
                buf[0] = DN_SUBTREE_PREFIX;
 
212
                rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 
213
                if( rc != 0 ) {
 
214
                        Debug( LDAP_DEBUG_ANY,
 
215
                        "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 
216
                        e->e_id, ptr.bv_val, rc );
 
217
                        goto done;
 
218
                }
 
219
 
 
220
#ifdef BDB_MULTIPLE_SUFFIXES
 
221
        if( !be_issuffix( op->o_bd, &ptr ))
 
222
#endif
 
223
        {
 
224
                dnParent( &ptr, &pdn );
 
225
 
 
226
                key.size = pdn.bv_len + 2;
 
227
                key.ulen = key.size;
 
228
                pdn.bv_val[-1] = DN_ONE_PREFIX;
 
229
                key.data = pdn.bv_val - 1;
 
230
                ptr = pdn;
 
231
 
 
232
                rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 
233
 
 
234
                if( rc != 0 ) {
 
235
                        Debug( LDAP_DEBUG_ANY,
 
236
                                "=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n",
 
237
                                e->e_id, ptr.bv_val, rc );
 
238
                        goto done;
 
239
                }
 
240
        }
 
241
 
 
242
#ifndef BDB_MULTIPLE_SUFFIXES
 
243
        while( !be_issuffix( op->o_bd, &ptr ))
 
244
#else
 
245
        for (;;)
 
246
#endif
 
247
        {
 
248
                ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 
249
 
 
250
                rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 
251
                if( rc != 0 ) {
 
252
                        Debug( LDAP_DEBUG_ANY,
 
253
                                "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 
254
                                e->e_id, ptr.bv_val, rc );
 
255
                        goto done;
 
256
                }
 
257
#ifdef BDB_MULTIPLE_SUFFIXES
 
258
                if( be_issuffix( op->o_bd, &ptr )) break;
 
259
#endif
 
260
                dnParent( &ptr, &pdn );
 
261
 
 
262
                key.size = pdn.bv_len + 2;
 
263
                key.ulen = key.size;
 
264
                key.data = pdn.bv_val - 1;
 
265
                ptr = pdn;
 
266
        }
 
267
        }
 
268
 
 
269
done:
 
270
        op->o_tmpfree( buf, op->o_tmpmemctx );
 
271
        Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 
272
        return rc;
 
273
}
 
274
 
 
275
int
 
276
bdb_dn2id(
 
277
        Operation *op,
 
278
        struct berval   *dn,
 
279
        EntryInfo *ei,
 
280
        BDB_LOCKER locker,
 
281
        DB_LOCK *lock )
 
282
{
 
283
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
284
        DB *db = bdb->bi_dn2id->bdi_db;
 
285
        DBC     *cursor;
 
286
        int             rc;
 
287
        DBT             key, data;
 
288
        ID              nid;
 
289
 
 
290
        Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );
 
291
 
 
292
        DBTzero( &key );
 
293
        key.size = dn->bv_len + 2;
 
294
        key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 
295
        ((char *)key.data)[0] = DN_BASE_PREFIX;
 
296
        AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
 
297
 
 
298
        /* store the ID */
 
299
        DBTzero( &data );
 
300
        data.data = &nid;
 
301
        data.ulen = sizeof(ID);
 
302
        data.flags = DB_DBT_USERMEM;
 
303
 
 
304
        rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 
305
        if ( rc ) goto func_leave;
 
306
 
 
307
        rc = bdb_dn2id_lock( bdb, dn, 0, locker, lock );
 
308
        if ( rc ) goto nolock;
 
309
 
 
310
        if ( locker ) {
 
311
                CURSOR_SETLOCKER(cursor, locker);
 
312
        }
 
313
 
 
314
        /* fetch it */
 
315
        rc = cursor->c_get( cursor, &key, &data, DB_SET );
 
316
 
 
317
nolock:
 
318
        cursor->c_close( cursor );
 
319
func_leave:
 
320
 
 
321
        if( rc != 0 ) {
 
322
                Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
 
323
                        db_strerror( rc ), rc, 0 );
 
324
        } else {
 
325
                BDB_DISK2ID( &nid, &ei->bei_id );
 
326
                Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
 
327
                        ei->bei_id, 0, 0 );
 
328
        }
 
329
        op->o_tmpfree( key.data, op->o_tmpmemctx );
 
330
        return rc;
 
331
}
 
332
 
 
333
int
 
334
bdb_dn2id_children(
 
335
        Operation *op,
 
336
        DB_TXN *txn,
 
337
        Entry *e )
 
338
{
 
339
        DBT             key, data;
 
340
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
341
        DB *db = bdb->bi_dn2id->bdi_db;
 
342
        ID              id;
 
343
        int             rc;
 
344
 
 
345
        Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
 
346
                e->e_nname.bv_val, 0, 0 );
 
347
        DBTzero( &key );
 
348
        key.size = e->e_nname.bv_len + 2;
 
349
        key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 
350
        ((char *)key.data)[0] = DN_ONE_PREFIX;
 
351
        AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
 
352
 
 
353
        if ( bdb->bi_idl_cache_size ) {
 
354
                rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 
355
                if ( rc != LDAP_NO_SUCH_OBJECT ) {
 
356
                        op->o_tmpfree( key.data, op->o_tmpmemctx );
 
357
                        return rc;
 
358
                }
 
359
        }
 
360
        /* we actually could do a empty get... */
 
361
        DBTzero( &data );
 
362
        data.data = &id;
 
363
        data.ulen = sizeof(id);
 
364
        data.flags = DB_DBT_USERMEM;
 
365
        data.doff = 0;
 
366
        data.dlen = sizeof(id);
 
367
 
 
368
        rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
 
369
        op->o_tmpfree( key.data, op->o_tmpmemctx );
 
370
 
 
371
        Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n",
 
372
                e->e_nname.bv_val,
 
373
                rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
 
374
                        db_strerror(rc) ), rc );
 
375
 
 
376
        return rc;
 
377
}
 
378
 
 
379
int
 
380
bdb_dn2idl(
 
381
        Operation *op,
 
382
        BDB_LOCKER locker,
 
383
        struct berval *ndn,
 
384
        EntryInfo *ei,
 
385
        ID *ids,
 
386
        ID *stack )
 
387
{
 
388
        int             rc;
 
389
        DBT             key;
 
390
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
391
        DB *db = bdb->bi_dn2id->bdi_db;
 
392
        int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 
393
                ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 
394
 
 
395
        Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n",
 
396
                ndn->bv_val, 0, 0 );
 
397
 
 
398
#ifndef BDB_MULTIPLE_SUFFIXES
 
399
        if ( prefix == DN_SUBTREE_PREFIX
 
400
                && ( ei->bei_id == 0 || ei->bei_parent->bei_id == 0 )) {
 
401
                BDB_IDL_ALL(bdb, ids);
 
402
                return 0;
 
403
        }
 
404
#endif
 
405
 
 
406
        DBTzero( &key );
 
407
        key.size = ndn->bv_len + 2;
 
408
        key.ulen = key.size;
 
409
        key.flags = DB_DBT_USERMEM;
 
410
        key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 
411
        ((char *)key.data)[0] = prefix;
 
412
        AC_MEMCPY( &((char *)key.data)[1], ndn->bv_val, key.size - 1 );
 
413
 
 
414
        BDB_IDL_ZERO( ids );
 
415
        rc = bdb_idl_fetch_key( op->o_bd, db, locker, &key, ids, NULL, 0 );
 
416
 
 
417
        if( rc != 0 ) {
 
418
                Debug( LDAP_DEBUG_TRACE,
 
419
                        "<= bdb_dn2idl: get failed: %s (%d)\n",
 
420
                        db_strerror( rc ), rc, 0 );
 
421
 
 
422
        } else {
 
423
                Debug( LDAP_DEBUG_TRACE,
 
424
                        "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
 
425
                        (long) ids[0],
 
426
                        (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
 
427
        }
 
428
 
 
429
        op->o_tmpfree( key.data, op->o_tmpmemctx );
 
430
        return rc;
 
431
}
 
432
 
 
433
#else   /* BDB_HIER */
 
434
/* Management routines for a hierarchically structured database.
 
435
 *
 
436
 * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 
437
 * entry in this database is a struct diskNode, keyed by entryID and with
 
438
 * the data containing the RDN and entryID of the node's children. We use
 
439
 * a B-Tree with sorted duplicates to store all the children of a node under
 
440
 * the same key. Also, the first item under the key contains the entry's own
 
441
 * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
 
442
 * well as top-down. To keep this info first in the list, the high bit of all
 
443
 * subsequent nrdnlen's is always set. This means we can only accomodate
 
444
 * RDNs up to length 32767, but that's fine since full DNs are already
 
445
 * restricted to 8192.
 
446
 *
 
447
 * The diskNode is a variable length structure. This definition is not
 
448
 * directly usable for in-memory manipulation.
 
449
 */
 
450
typedef struct diskNode {
 
451
        unsigned char nrdnlen[2];
 
452
        char nrdn[1];
 
453
        char rdn[1];                        /* variable placement */
 
454
        unsigned char entryID[sizeof(ID)];  /* variable placement */
 
455
} diskNode;
 
456
 
 
457
/* Sort function for the sorted duplicate data items of a dn2id key.
 
458
 * Sorts based on normalized RDN, in length order.
 
459
 */
 
460
int
 
461
hdb_dup_compare(
 
462
        DB *db, 
 
463
        const DBT *usrkey,
 
464
        const DBT *curkey
 
465
)
 
466
{
 
467
        diskNode *un, *cn;
 
468
        int rc;
 
469
 
 
470
        un = (diskNode *)usrkey->data;
 
471
        cn = (diskNode *)curkey->data;
 
472
 
 
473
        /* data is not aligned, cannot compare directly */
 
474
        rc = un->nrdnlen[0] - cn->nrdnlen[0];
 
475
        if ( rc ) return rc;
 
476
        rc = un->nrdnlen[1] - cn->nrdnlen[1];
 
477
        if ( rc ) return rc;
 
478
 
 
479
        return strcmp( un->nrdn, cn->nrdn );
 
480
}
 
481
 
 
482
/* This function constructs a full DN for a given entry.
 
483
 */
 
484
int hdb_fix_dn(
 
485
        Entry *e,
 
486
        int checkit )
 
487
{
 
488
        EntryInfo *ei;
 
489
        int rlen = 0, nrlen = 0;
 
490
        char *ptr, *nptr;
 
491
        int max = 0;
 
492
 
 
493
        if ( !e->e_id )
 
494
                return 0;
 
495
 
 
496
        /* count length of all DN components */
 
497
        for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 
498
                rlen += ei->bei_rdn.bv_len + 1;
 
499
                nrlen += ei->bei_nrdn.bv_len + 1;
 
500
                if (ei->bei_modrdns > max) max = ei->bei_modrdns;
 
501
        }
 
502
 
 
503
        /* See if the entry DN was invalidated by a subtree rename */
 
504
        if ( checkit ) {
 
505
                if ( BEI(e)->bei_modrdns >= max ) {
 
506
                        return 0;
 
507
                }
 
508
                /* We found a mismatch, tell the caller to lock it */
 
509
                if ( checkit == 1 ) {
 
510
                        return 1;
 
511
                }
 
512
                /* checkit == 2. do the fix. */
 
513
                free( e->e_name.bv_val );
 
514
                free( e->e_nname.bv_val );
 
515
        }
 
516
 
 
517
        e->e_name.bv_len = rlen - 1;
 
518
        e->e_nname.bv_len = nrlen - 1;
 
519
        e->e_name.bv_val = ch_malloc(rlen);
 
520
        e->e_nname.bv_val = ch_malloc(nrlen);
 
521
        ptr = e->e_name.bv_val;
 
522
        nptr = e->e_nname.bv_val;
 
523
        for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 
524
                ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
 
525
                nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
 
526
                if ( ei->bei_parent ) {
 
527
                        *ptr++ = ',';
 
528
                        *nptr++ = ',';
 
529
                }
 
530
        }
 
531
        BEI(e)->bei_modrdns = max;
 
532
        ptr[-1] = '\0';
 
533
        nptr[-1] = '\0';
 
534
 
 
535
        return 0;
 
536
}
 
537
 
 
538
/* We add two elements to the DN2ID database - a data item under the parent's
 
539
 * entryID containing the child's RDN and entryID, and an item under the
 
540
 * child's entryID containing the parent's entryID.
 
541
 */
 
542
int
 
543
hdb_dn2id_add(
 
544
        Operation       *op,
 
545
        DB_TXN *txn,
 
546
        EntryInfo       *eip,
 
547
        Entry           *e )
 
548
{
 
549
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
550
        DB *db = bdb->bi_dn2id->bdi_db;
 
551
        DBT             key, data;
 
552
        ID              nid;
 
553
        int             rc, rlen, nrlen;
 
554
        diskNode *d;
 
555
        char *ptr;
 
556
 
 
557
        Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n",
 
558
                e->e_id, e->e_ndn, 0 );
 
559
 
 
560
        nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 
561
        if (nrlen) {
 
562
                rlen = dn_rdnlen( op->o_bd, &e->e_name );
 
563
        } else {
 
564
                nrlen = e->e_nname.bv_len;
 
565
                rlen = e->e_name.bv_len;
 
566
        }
 
567
 
 
568
        d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
 
569
        d->nrdnlen[1] = nrlen & 0xff;
 
570
        d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 
571
        ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
 
572
        *ptr++ = '\0';
 
573
        ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
 
574
        *ptr++ = '\0';
 
575
        BDB_ID2DISK( e->e_id, ptr );
 
576
 
 
577
        DBTzero(&key);
 
578
        DBTzero(&data);
 
579
        key.size = sizeof(ID);
 
580
        key.flags = DB_DBT_USERMEM;
 
581
        BDB_ID2DISK( eip->bei_id, &nid );
 
582
 
 
583
        key.data = &nid;
 
584
 
 
585
        /* Need to make dummy root node once. Subsequent attempts
 
586
         * will fail harmlessly.
 
587
         */
 
588
        if ( eip->bei_id == 0 ) {
 
589
                diskNode dummy = {{0, 0}, "", "", ""};
 
590
                data.data = &dummy;
 
591
                data.size = sizeof(diskNode);
 
592
                data.flags = DB_DBT_USERMEM;
 
593
 
 
594
                db->put( db, txn, &key, &data, DB_NODUPDATA );
 
595
        }
 
596
 
 
597
        data.data = d;
 
598
        data.size = sizeof(diskNode) + rlen + nrlen;
 
599
        data.flags = DB_DBT_USERMEM;
 
600
 
 
601
        rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 
602
 
 
603
        if (rc == 0) {
 
604
                BDB_ID2DISK( e->e_id, &nid );
 
605
                BDB_ID2DISK( eip->bei_id, ptr );
 
606
                d->nrdnlen[0] ^= 0x80;
 
607
 
 
608
                rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 
609
        }
 
610
 
 
611
        /* Update all parents' IDL cache entries */
 
612
        if ( rc == 0 && bdb->bi_idl_cache_size ) {
 
613
                ID tmp[2];
 
614
                char *ptr = ((char *)&tmp[1])-1;
 
615
                key.data = ptr;
 
616
                key.size = sizeof(ID)+1;
 
617
                tmp[1] = eip->bei_id;
 
618
                *ptr = DN_ONE_PREFIX;
 
619
                bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 
620
                *ptr = DN_SUBTREE_PREFIX;
 
621
                for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 
622
                        tmp[1] = eip->bei_id;
 
623
                        bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 
624
                }
 
625
        }
 
626
 
 
627
func_leave:
 
628
        op->o_tmpfree( d, op->o_tmpmemctx );
 
629
        Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 
630
 
 
631
        return rc;
 
632
}
 
633
 
 
634
int
 
635
hdb_dn2id_delete(
 
636
        Operation       *op,
 
637
        DB_TXN *txn,
 
638
        EntryInfo       *eip,
 
639
        Entry   *e )
 
640
{
 
641
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
642
        DB *db = bdb->bi_dn2id->bdi_db;
 
643
        DBT             key, data;
 
644
        DBC     *cursor;
 
645
        diskNode *d;
 
646
        int rc;
 
647
        ID      nid;
 
648
        unsigned char dlen[2];
 
649
        DB_LOCK lock;
 
650
 
 
651
        Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n",
 
652
                e->e_id, e->e_ndn, 0 );
 
653
 
 
654
        DBTzero(&key);
 
655
        key.size = sizeof(ID);
 
656
        key.ulen = key.size;
 
657
        key.flags = DB_DBT_USERMEM;
 
658
        BDB_ID2DISK( eip->bei_id, &nid );
 
659
 
 
660
        DBTzero(&data);
 
661
        data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1;
 
662
        data.ulen = data.size;
 
663
        data.dlen = data.size;
 
664
        data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 
665
 
 
666
        key.data = &nid;
 
667
 
 
668
        d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
 
669
        d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
 
670
        d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
 
671
        dlen[0] = d->nrdnlen[0];
 
672
        dlen[1] = d->nrdnlen[1];
 
673
        strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
 
674
        data.data = d;
 
675
 
 
676
        rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 
677
        if ( rc ) goto func_leave;
 
678
 
 
679
        /* We hold this lock until the TXN completes */
 
680
        rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
 
681
        if ( rc ) goto nolock;
 
682
 
 
683
        /* Delete our ID from the parent's list */
 
684
        rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 
685
        if ( rc == 0 ) {
 
686
                if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] &&
 
687
                        !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val ))
 
688
                        rc = cursor->c_del( cursor, 0 );
 
689
                else
 
690
                        rc = DB_NOTFOUND;
 
691
        }
 
692
 
 
693
        /* Delete our ID from the tree. With sorted duplicates, this
 
694
         * will leave any child nodes still hanging around. This is OK
 
695
         * for modrdn, which will add our info back in later.
 
696
         */
 
697
        if ( rc == 0 ) {
 
698
                BDB_ID2DISK( e->e_id, &nid );
 
699
                rc = cursor->c_get( cursor, &key, &data, DB_SET );
 
700
                if ( rc == 0 )
 
701
                        rc = cursor->c_del( cursor, 0 );
 
702
        }
 
703
 
 
704
nolock:
 
705
        cursor->c_close( cursor );
 
706
func_leave:
 
707
        op->o_tmpfree( d, op->o_tmpmemctx );
 
708
 
 
709
        /* Delete IDL cache entries */
 
710
        if ( rc == 0 && bdb->bi_idl_cache_size ) {
 
711
                ID tmp[2];
 
712
                char *ptr = ((char *)&tmp[1])-1;
 
713
                key.data = ptr;
 
714
                key.size = sizeof(ID)+1;
 
715
                tmp[1] = eip->bei_id;
 
716
                *ptr = DN_ONE_PREFIX;
 
717
                bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 
718
                *ptr = DN_SUBTREE_PREFIX;
 
719
                for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 
720
                        tmp[1] = eip->bei_id;
 
721
                        bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 
722
                }
 
723
        }
 
724
        Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 
725
        return rc;
 
726
}
 
727
 
 
728
 
 
729
int
 
730
hdb_dn2id(
 
731
        Operation       *op,
 
732
        struct berval   *in,
 
733
        EntryInfo       *ei,
 
734
        BDB_LOCKER locker,
 
735
        DB_LOCK *lock )
 
736
{
 
737
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
738
        DB *db = bdb->bi_dn2id->bdi_db;
 
739
        DBT             key, data;
 
740
        DBC     *cursor;
 
741
        int             rc = 0, nrlen;
 
742
        diskNode *d;
 
743
        char    *ptr;
 
744
        unsigned char dlen[2];
 
745
        ID idp, parentID;
 
746
 
 
747
        Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );
 
748
 
 
749
        nrlen = dn_rdnlen( op->o_bd, in );
 
750
        if (!nrlen) nrlen = in->bv_len;
 
751
 
 
752
        DBTzero(&key);
 
753
        key.size = sizeof(ID);
 
754
        key.data = &idp;
 
755
        key.ulen = sizeof(ID);
 
756
        key.flags = DB_DBT_USERMEM;
 
757
        parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0;
 
758
        BDB_ID2DISK( parentID, &idp );
 
759
 
 
760
        DBTzero(&data);
 
761
        data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
 
762
        data.ulen = data.size * 3;
 
763
        data.dlen = data.ulen;
 
764
        data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 
765
 
 
766
        rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 
767
        if ( rc ) return rc;
 
768
        if ( locker ) {
 
769
                CURSOR_SETLOCKER( cursor, locker );
 
770
        }
 
771
 
 
772
        d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
 
773
        d->nrdnlen[1] = nrlen & 0xff;
 
774
        d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 
775
        dlen[0] = d->nrdnlen[0];
 
776
        dlen[1] = d->nrdnlen[1];
 
777
        ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
 
778
        *ptr = '\0';
 
779
        data.data = d;
 
780
 
 
781
        rc = bdb_dn2id_lock( bdb, in, 0, locker, lock );
 
782
        if ( rc ) goto func_leave;
 
783
 
 
784
        rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 
785
        if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] ||
 
786
                strncmp( d->nrdn, in->bv_val, nrlen ))) {
 
787
                rc = DB_NOTFOUND;
 
788
        }
 
789
        if ( rc == 0 ) {
 
790
                ptr = (char *) data.data + data.size - sizeof(ID);
 
791
                BDB_DISK2ID( ptr, &ei->bei_id );
 
792
                ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
 
793
                ptr = d->nrdn + nrlen + 1;
 
794
                ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 
795
                if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) {
 
796
                        db_recno_t dkids;
 
797
                        /* How many children does the parent have? */
 
798
                        /* FIXME: do we need to lock the parent
 
799
                         * entryinfo? Seems safe...
 
800
                         */
 
801
                        cursor->c_count( cursor, &dkids, 0 );
 
802
                        ei->bei_parent->bei_dkids = dkids;
 
803
                }
 
804
        }
 
805
 
 
806
func_leave:
 
807
        cursor->c_close( cursor );
 
808
        op->o_tmpfree( d, op->o_tmpmemctx );
 
809
        if( rc != 0 ) {
 
810
                Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n",
 
811
                        db_strerror( rc ), rc, 0 );
 
812
        } else {
 
813
                Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n",
 
814
                        ei->bei_id, 0, 0 );
 
815
        }
 
816
 
 
817
        return rc;
 
818
}
 
819
 
 
820
int
 
821
hdb_dn2id_parent(
 
822
        Operation *op,
 
823
        BDB_LOCKER      locker,
 
824
        EntryInfo *ei,
 
825
        ID *idp )
 
826
{
 
827
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
828
        DB *db = bdb->bi_dn2id->bdi_db;
 
829
        DBT             key, data;
 
830
        DBC     *cursor;
 
831
        int             rc = 0;
 
832
        diskNode *d;
 
833
        char    *ptr;
 
834
        ID      nid;
 
835
 
 
836
        DBTzero(&key);
 
837
        key.size = sizeof(ID);
 
838
        key.data = &nid;
 
839
        key.ulen = sizeof(ID);
 
840
        key.flags = DB_DBT_USERMEM;
 
841
        BDB_ID2DISK( ei->bei_id, &nid );
 
842
 
 
843
        DBTzero(&data);
 
844
        data.flags = DB_DBT_USERMEM;
 
845
 
 
846
        rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 
847
        if ( rc ) return rc;
 
848
        if ( locker ) {
 
849
                CURSOR_SETLOCKER(cursor, locker);
 
850
        }
 
851
 
 
852
        data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
 
853
        d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
 
854
        data.data = d;
 
855
 
 
856
        rc = cursor->c_get( cursor, &key, &data, DB_SET );
 
857
        if ( rc == 0 ) {
 
858
                if (d->nrdnlen[0] & 0x80) {
 
859
                        rc = LDAP_OTHER;
 
860
                } else {
 
861
                        db_recno_t dkids;
 
862
                        ptr = (char *) data.data + data.size - sizeof(ID);
 
863
                        BDB_DISK2ID( ptr, idp );
 
864
                        ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 
865
                        ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
 
866
                        ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
 
867
                                ei->bei_nrdn.bv_len;
 
868
                        ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
 
869
                        ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 
870
                        /* How many children does this node have? */
 
871
                        cursor->c_count( cursor, &dkids, 0 );
 
872
                        ei->bei_dkids = dkids;
 
873
                }
 
874
        }
 
875
        cursor->c_close( cursor );
 
876
        op->o_tmpfree( d, op->o_tmpmemctx );
 
877
        return rc;
 
878
}
 
879
 
 
880
int
 
881
hdb_dn2id_children(
 
882
        Operation *op,
 
883
        DB_TXN *txn,
 
884
        Entry *e )
 
885
{
 
886
        struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 
887
        DB *db = bdb->bi_dn2id->bdi_db;
 
888
        DBT             key, data;
 
889
        DBC             *cursor;
 
890
        int             rc;
 
891
        ID              id;
 
892
        diskNode d;
 
893
 
 
894
        DBTzero(&key);
 
895
        key.size = sizeof(ID);
 
896
        key.data = &e->e_id;
 
897
        key.flags = DB_DBT_USERMEM;
 
898
        BDB_ID2DISK( e->e_id, &id );
 
899
 
 
900
        /* IDL cache is in host byte order */
 
901
        if ( bdb->bi_idl_cache_size ) {
 
902
                rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 
903
                if ( rc != LDAP_NO_SUCH_OBJECT ) {
 
904
                        return rc;
 
905
                }
 
906
        }
 
907
 
 
908
        key.data = &id;
 
909
        DBTzero(&data);
 
910
        data.data = &d;
 
911
        data.ulen = sizeof(d);
 
912
        data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 
913
        data.dlen = sizeof(d);
 
914
 
 
915
        rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 
916
        if ( rc ) return rc;
 
917
 
 
918
        rc = cursor->c_get( cursor, &key, &data, DB_SET );
 
919
        if ( rc == 0 ) {
 
920
                db_recno_t dkids;
 
921
                rc = cursor->c_count( cursor, &dkids, 0 );
 
922
                if ( rc == 0 ) {
 
923
                        BEI(e)->bei_dkids = dkids;
 
924
                        if ( dkids < 2 ) rc = DB_NOTFOUND;
 
925
                }
 
926
        }
 
927
        cursor->c_close( cursor );
 
928
        return rc;
 
929
}
 
930
 
 
931
/* bdb_dn2idl:
 
932
 * We can't just use bdb_idl_fetch_key because
 
933
 * 1 - our data items are longer than just an entry ID
 
934
 * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 
935
 *
 
936
 * We descend the tree recursively, so we define this cookie
 
937
 * to hold our necessary state information. The bdb_dn2idl_internal
 
938
 * function uses this cookie when calling itself.
 
939
 */
 
940
 
 
941
struct dn2id_cookie {
 
942
        struct bdb_info *bdb;
 
943
        Operation *op;
 
944
        BDB_LOCKER locker;
 
945
        EntryInfo *ei;
 
946
        ID *ids;
 
947
        ID *tmp;
 
948
        ID *buf;
 
949
        DB *db;
 
950
        DBC *dbc;
 
951
        DBT key;
 
952
        DBT data;
 
953
        ID dbuf;
 
954
        ID id;
 
955
        ID nid;
 
956
        int rc;
 
957
        int depth;
 
958
        char need_sort;
 
959
        char prefix;
 
960
};
 
961
 
 
962
static int
 
963
apply_func(
 
964
        void *data,
 
965
        void *arg )
 
966
{
 
967
        EntryInfo *ei = data;
 
968
        ID *idl = arg;
 
969
 
 
970
        bdb_idl_append_one( idl, ei->bei_id );
 
971
        return 0;
 
972
}
 
973
 
 
974
static int
 
975
hdb_dn2idl_internal(
 
976
        struct dn2id_cookie *cx
 
977
)
 
978
{
 
979
        BDB_IDL_ZERO( cx->tmp );
 
980
 
 
981
        if ( cx->bdb->bi_idl_cache_size ) {
 
982
                char *ptr = ((char *)&cx->id)-1;
 
983
 
 
984
                cx->key.data = ptr;
 
985
                cx->key.size = sizeof(ID)+1;
 
986
                if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 
987
                        ID *ids = cx->depth ? cx->tmp : cx->ids;
 
988
                        *ptr = cx->prefix;
 
989
                        cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, ids);
 
990
                        if ( cx->rc == LDAP_SUCCESS ) {
 
991
                                if ( cx->depth ) {
 
992
                                        bdb_idl_append( cx->ids, cx->tmp );
 
993
                                        cx->need_sort = 1;
 
994
                                }
 
995
                                return cx->rc;
 
996
                        }
 
997
                }
 
998
                *ptr = DN_ONE_PREFIX;
 
999
                cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp);
 
1000
                if ( cx->rc == LDAP_SUCCESS ) {
 
1001
                        goto gotit;
 
1002
                }
 
1003
                if ( cx->rc == DB_NOTFOUND ) {
 
1004
                        return cx->rc;
 
1005
                }
 
1006
        }
 
1007
 
 
1008
        bdb_cache_entryinfo_lock( cx->ei );
 
1009
 
 
1010
        /* If number of kids in the cache differs from on-disk, load
 
1011
         * up all the kids from the database
 
1012
         */
 
1013
        if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
 
1014
                EntryInfo ei;
 
1015
                db_recno_t dkids = cx->ei->bei_dkids;
 
1016
                ei.bei_parent = cx->ei;
 
1017
 
 
1018
                /* Only one thread should load the cache */
 
1019
                while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
 
1020
                        bdb_cache_entryinfo_unlock( cx->ei );
 
1021
                        ldap_pvt_thread_yield();
 
1022
                        bdb_cache_entryinfo_lock( cx->ei );
 
1023
                        if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
 
1024
                                goto synced;
 
1025
                        }
 
1026
                }
 
1027
 
 
1028
                cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
 
1029
 
 
1030
                bdb_cache_entryinfo_unlock( cx->ei );
 
1031
 
 
1032
                cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
 
1033
                        cx->bdb->bi_db_opflags );
 
1034
                if ( cx->rc )
 
1035
                        goto done_one;
 
1036
 
 
1037
                cx->data.data = &cx->dbuf;
 
1038
                cx->data.ulen = sizeof(ID);
 
1039
                cx->data.dlen = sizeof(ID);
 
1040
                cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 
1041
 
 
1042
                /* The first item holds the parent ID. Ignore it. */
 
1043
                cx->key.data = &cx->nid;
 
1044
                cx->key.size = sizeof(ID);
 
1045
                cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
 
1046
                if ( cx->rc ) {
 
1047
                        cx->dbc->c_close( cx->dbc );
 
1048
                        goto done_one;
 
1049
                }
 
1050
 
 
1051
                /* If the on-disk count is zero we've never checked it.
 
1052
                 * Count it now.
 
1053
                 */
 
1054
                if ( !dkids ) {
 
1055
                        cx->dbc->c_count( cx->dbc, &dkids, 0 );
 
1056
                        cx->ei->bei_dkids = dkids;
 
1057
                }
 
1058
 
 
1059
                cx->data.data = cx->buf;
 
1060
                cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID);
 
1061
                cx->data.flags = DB_DBT_USERMEM;
 
1062
 
 
1063
                if ( dkids > 1 ) {
 
1064
                        /* Fetch the rest of the IDs in a loop... */
 
1065
                        while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
 
1066
                                DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
 
1067
                                u_int8_t *j;
 
1068
                                size_t len;
 
1069
                                void *ptr;
 
1070
                                DB_MULTIPLE_INIT( ptr, &cx->data );
 
1071
                                while (ptr) {
 
1072
                                        DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
 
1073
                                        if (j) {
 
1074
                                                EntryInfo *ei2;
 
1075
                                                diskNode *d = (diskNode *)j;
 
1076
                                                short nrlen;
 
1077
 
 
1078
                                                BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
 
1079
                                                nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
 
1080
                                                ei.bei_nrdn.bv_len = nrlen;
 
1081
                                                /* nrdn/rdn are set in-place.
 
1082
                                                 * hdb_cache_load will copy them as needed
 
1083
                                                 */
 
1084
                                                ei.bei_nrdn.bv_val = d->nrdn;
 
1085
                                                ei.bei_rdn.bv_len = len - sizeof(diskNode)
 
1086
                                                        - ei.bei_nrdn.bv_len;
 
1087
                                                ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
 
1088
                                                bdb_idl_append_one( cx->tmp, ei.bei_id );
 
1089
                                                hdb_cache_load( cx->bdb, &ei, &ei2 );
 
1090
                                        }
 
1091
                                }
 
1092
                        }
 
1093
                }
 
1094
 
 
1095
                cx->rc = cx->dbc->c_close( cx->dbc );
 
1096
done_one:
 
1097
                bdb_cache_entryinfo_lock( cx->ei );
 
1098
                cx->ei->bei_state ^= CACHE_ENTRY_ONELEVEL;
 
1099
                bdb_cache_entryinfo_unlock( cx->ei );
 
1100
                if ( cx->rc )
 
1101
                        return cx->rc;
 
1102
 
 
1103
        } else {
 
1104
                /* The in-memory cache is in sync with the on-disk data.
 
1105
                 * do we have any kids?
 
1106
                 */
 
1107
synced:
 
1108
                cx->rc = 0;
 
1109
                if ( cx->ei->bei_ckids > 0 ) {
 
1110
                        /* Walk the kids tree; order is irrelevant since bdb_idl_sort
 
1111
                         * will sort it later.
 
1112
                         */
 
1113
                        avl_apply( cx->ei->bei_kids, apply_func,
 
1114
                                cx->tmp, -1, AVL_POSTORDER );
 
1115
                }
 
1116
                bdb_cache_entryinfo_unlock( cx->ei );
 
1117
        }
 
1118
 
 
1119
        if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
 
1120
                bdb_idl_sort( cx->tmp, cx->buf );
 
1121
        if ( cx->bdb->bi_idl_cache_max_size && !BDB_IDL_IS_ZERO( cx->tmp )) {
 
1122
                char *ptr = ((char *)&cx->id)-1;
 
1123
                cx->key.data = ptr;
 
1124
                cx->key.size = sizeof(ID)+1;
 
1125
                *ptr = DN_ONE_PREFIX;
 
1126
                bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
 
1127
        }
 
1128
 
 
1129
gotit:
 
1130
        if ( !BDB_IDL_IS_ZERO( cx->tmp )) {
 
1131
                if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 
1132
                        bdb_idl_append( cx->ids, cx->tmp );
 
1133
                        cx->need_sort = 1;
 
1134
                        if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
 
1135
                                ID *save, idcurs;
 
1136
                                EntryInfo *ei = cx->ei;
 
1137
                                int nokids = 1;
 
1138
                                save = cx->op->o_tmpalloc( BDB_IDL_SIZEOF( cx->tmp ),
 
1139
                                        cx->op->o_tmpmemctx );
 
1140
                                BDB_IDL_CPY( save, cx->tmp );
 
1141
 
 
1142
                                idcurs = 0;
 
1143
                                cx->depth++;
 
1144
                                for ( cx->id = bdb_idl_first( save, &idcurs );
 
1145
                                        cx->id != NOID;
 
1146
                                        cx->id = bdb_idl_next( save, &idcurs )) {
 
1147
                                        cx->ei = bdb_cache_find_info( cx->bdb, cx->id );
 
1148
                                        if ( !cx->ei ||
 
1149
                                                ( cx->ei->bei_state & CACHE_ENTRY_NO_KIDS ))
 
1150
                                                continue;
 
1151
 
 
1152
                                        BDB_ID2DISK( cx->id, &cx->nid );
 
1153
                                        hdb_dn2idl_internal( cx );
 
1154
                                        if ( !BDB_IDL_IS_ZERO( cx->tmp ))
 
1155
                                                nokids = 0;
 
1156
                                }
 
1157
                                cx->depth--;
 
1158
                                cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
 
1159
                                if ( nokids ) {
 
1160
                                        bdb_cache_entryinfo_lock( ei );
 
1161
                                        ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
 
1162
                                        bdb_cache_entryinfo_unlock( ei );
 
1163
                                }
 
1164
                        }
 
1165
                        /* Make sure caller knows it had kids! */
 
1166
                        cx->tmp[0]=1;
 
1167
 
 
1168
                        cx->rc = 0;
 
1169
                } else {
 
1170
                        BDB_IDL_CPY( cx->ids, cx->tmp );
 
1171
                }
 
1172
        }
 
1173
        return cx->rc;
 
1174
}
 
1175
 
 
1176
int
 
1177
hdb_dn2idl(
 
1178
        Operation       *op,
 
1179
        BDB_LOCKER locker,
 
1180
        struct berval *ndn,
 
1181
        EntryInfo       *ei,
 
1182
        ID *ids,
 
1183
        ID *stack )
 
1184
{
 
1185
        struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
 
1186
        struct dn2id_cookie cx;
 
1187
 
 
1188
        Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2idl(\"%s\")\n",
 
1189
                ndn->bv_val, 0, 0 );
 
1190
 
 
1191
#ifndef BDB_MULTIPLE_SUFFIXES
 
1192
        if ( op->ors_scope != LDAP_SCOPE_ONELEVEL && 
 
1193
                ( ei->bei_id == 0 ||
 
1194
                ei->bei_parent->bei_id == 0 ))
 
1195
        {
 
1196
                BDB_IDL_ALL( bdb, ids );
 
1197
                return 0;
 
1198
        }
 
1199
#endif
 
1200
 
 
1201
        cx.id = ei->bei_id;
 
1202
        BDB_ID2DISK( cx.id, &cx.nid );
 
1203
        cx.ei = ei;
 
1204
        cx.bdb = bdb;
 
1205
        cx.db = cx.bdb->bi_dn2id->bdi_db;
 
1206
        cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
 
1207
                DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 
1208
        cx.ids = ids;
 
1209
        cx.tmp = stack;
 
1210
        cx.buf = stack + BDB_IDL_UM_SIZE;
 
1211
        cx.op = op;
 
1212
        cx.locker = locker;
 
1213
        cx.need_sort = 0;
 
1214
        cx.depth = 0;
 
1215
 
 
1216
        if ( cx.prefix == DN_SUBTREE_PREFIX ) {
 
1217
                ids[0] = 1;
 
1218
                ids[1] = cx.id;
 
1219
        } else {
 
1220
                BDB_IDL_ZERO( ids );
 
1221
        }
 
1222
        if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
 
1223
                return LDAP_SUCCESS;
 
1224
 
 
1225
        DBTzero(&cx.key);
 
1226
        cx.key.ulen = sizeof(ID);
 
1227
        cx.key.size = sizeof(ID);
 
1228
        cx.key.flags = DB_DBT_USERMEM;
 
1229
 
 
1230
        DBTzero(&cx.data);
 
1231
 
 
1232
        hdb_dn2idl_internal(&cx);
 
1233
        if ( cx.need_sort ) {
 
1234
                char *ptr = ((char *)&cx.id)-1;
 
1235
                if ( !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 ) 
 
1236
                        bdb_idl_sort( cx.ids, cx.tmp );
 
1237
                cx.key.data = ptr;
 
1238
                cx.key.size = sizeof(ID)+1;
 
1239
                *ptr = cx.prefix;
 
1240
                cx.id = ei->bei_id;
 
1241
                if ( cx.bdb->bi_idl_cache_max_size )
 
1242
                        bdb_idl_cache_put( cx.bdb, cx.db, &cx.key, cx.ids, cx.rc );
 
1243
        }
 
1244
 
 
1245
        if ( cx.rc == DB_NOTFOUND )
 
1246
                cx.rc = LDAP_SUCCESS;
 
1247
 
 
1248
        return cx.rc;
 
1249
}
 
1250
#endif  /* BDB_HIER */