dn2id.c 29.2 KB
Newer Older
Kurt Zeilenga's avatar
Kurt Zeilenga committed
1
2
/* dn2id.c - routines to deal with the dn2id index */
/* $OpenLDAP$ */
Kurt Zeilenga's avatar
Notices    
Kurt Zeilenga committed
3
4
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
5
 * Copyright 2000-2007 The OpenLDAP Foundation.
Kurt Zeilenga's avatar
Notices    
Kurt Zeilenga committed
6
7
8
9
10
11
12
13
14
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
Kurt Zeilenga's avatar
Kurt Zeilenga committed
15
16
17
18
19
20
21
22
 */

#include "portable.h"

#include <stdio.h>
#include <ac/string.h>

#include "back-bdb.h"
23
#include "idl.h"
Howard Chu's avatar
Howard Chu committed
24
#include "lutil.h"
Kurt Zeilenga's avatar
Kurt Zeilenga committed
25

Howard Chu's avatar
Howard Chu committed
26
27
28
29
30
31
32
33
34
35
#define bdb_dn2id_lock					BDB_SYMBOL(dn2id_lock)

static int
bdb_dn2id_lock( struct bdb_info *bdb, struct berval *dn,
	int rw, u_int32_t locker, DB_LOCK *lock )
{
	int       rc;
	DBT       lockobj;
	int       db_rw;

36
37
38
	if (!locker)
		return 0;

Howard Chu's avatar
Howard Chu committed
39
40
41
42
43
44
45
46
47
48
49
50
51
	if (rw)
		db_rw = DB_LOCK_WRITE;
	else
		db_rw = DB_LOCK_READ;

	lockobj.data = dn->bv_val;
	lockobj.size = dn->bv_len;

	rc = LOCK_GET(bdb->bi_dbenv, locker, DB_LOCK_NOWAIT,
					&lockobj, db_rw, lock);
	return rc;
}

52
#ifndef BDB_HIER
Kurt Zeilenga's avatar
Kurt Zeilenga committed
53
int
54
bdb_dn2id_add(
55
	Operation *op,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
56
	DB_TXN *txn,
57
	EntryInfo *eip,
58
	Entry		*e )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
59
{
60
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
61
	DB *db = bdb->bi_dn2id->bdi_db;
62
63
	int		rc;
	DBT		key, data;
64
	ID		nid;
65
66
	char		*buf;
	struct berval	ptr, pdn;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
67

Howard Chu's avatar
Howard Chu committed
68
69
	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );
70
	assert( e->e_id != NOID );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
71
72

	DBTzero( &key );
Howard Chu's avatar
Howard Chu committed
73
	key.size = e->e_nname.bv_len + 2;
74
75
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
76
	buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
77
78
	key.data = buf;
	buf[0] = DN_BASE_PREFIX;
79
80
81
82
	ptr.bv_val = buf + 1;
	ptr.bv_len = e->e_nname.bv_len;
	AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
	ptr.bv_val[ptr.bv_len] = '\0';
Kurt Zeilenga's avatar
Kurt Zeilenga committed
83
84

	DBTzero( &data );
85
86
87
	data.data = &nid;
	data.size = sizeof( nid );
	BDB_ID2DISK( e->e_id, &nid );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
88
89
90
91

	/* store it -- don't override */
	rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
	if( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
92
93
		Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add 0x%lx: put failed: %s %d\n",
			e->e_id, db_strerror(rc), rc );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
94
95
96
		goto done;
	}

97
#ifndef BDB_MULTIPLE_SUFFIXES
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
98
	if( !be_issuffix( op->o_bd, &ptr ))
99
#endif
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
100
	{
101
		buf[0] = DN_SUBTREE_PREFIX;
102
		rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
103
104
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
105
106
			"=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n",
			e->e_id, ptr.bv_val, rc );
107
108
			goto done;
		}
109
		
110
#ifdef BDB_MULTIPLE_SUFFIXES
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
111
	if( !be_issuffix( op->o_bd, &ptr ))
112
#endif
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
113
	{
114
		dnParent( &ptr, &pdn );
115
	
116
		key.size = pdn.bv_len + 2;
117
		key.ulen = key.size;
118
119
		pdn.bv_val[-1] = DN_ONE_PREFIX;
		key.data = pdn.bv_val-1;
120
		ptr = pdn;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
121

122
		rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
123
124
125

		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
126
127
				"=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n",
					e->e_id, ptr.bv_val, rc );
128
			goto done;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
129
130
131
		}
	}

Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
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 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
141

142
143
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
144
145
				"=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n",
					e->e_id, ptr.bv_val, rc );
146
			break;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
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;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
157
	}
158
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
159
160

done:
161
	op->o_tmpfree( buf, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
162
	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
163
164
165
166
167
	return rc;
}

int
bdb_dn2id_delete(
168
	Operation *op,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
169
	DB_TXN *txn,
170
	EntryInfo	*eip,
171
	Entry		*e )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
172
{
173
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
174
	DB *db = bdb->bi_dn2id->bdi_db;
175
	char		*buf;
Howard Chu's avatar
Howard Chu committed
176
177
	DBT		key;
	DB_LOCK	lock;
178
	struct berval	pdn, ptr;
Howard Chu's avatar
Howard Chu committed
179
	int		rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
180

Howard Chu's avatar
Howard Chu committed
181
182
	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
183
184

	DBTzero( &key );
Howard Chu's avatar
Howard Chu committed
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
191
192
193
	ptr.bv_val = buf+1;
	ptr.bv_len = e->e_nname.bv_len;
	AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
	ptr.bv_val[ptr.bv_len] = '\0';
Kurt Zeilenga's avatar
Kurt Zeilenga committed
194

Howard Chu's avatar
Howard Chu committed
195
196
197
198
	/* We hold this lock until the TXN completes */
	rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
	if ( rc ) goto done;

199
	/* delete it */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
200
201
	rc = db->del( db, txn, &key, 0 );
	if( rc != 0 ) {
Howard Chu's avatar
Howard Chu committed
202
203
		Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n",
			e->e_id, db_strerror(rc), rc );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
204
205
206
		goto done;
	}

207
#ifndef BDB_MULTIPLE_SUFFIXES
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
208
	if( !be_issuffix( op->o_bd, &ptr ))
209
#endif
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
210
	{
211
		buf[0] = DN_SUBTREE_PREFIX;
212
		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
213
214
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
215
216
			"=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
			e->e_id, ptr.bv_val, rc );
217
218
			goto done;
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
219

220
#ifdef BDB_MULTIPLE_SUFFIXES
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
221
	if( !be_issuffix( op->o_bd, &ptr ))
222
#endif
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
223
	{
224
		dnParent( &ptr, &pdn );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
225

226
		key.size = pdn.bv_len + 2;
227
		key.ulen = key.size;
228
229
		pdn.bv_val[-1] = DN_ONE_PREFIX;
		key.data = pdn.bv_val - 1;
230
		ptr = pdn;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
231

232
		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
233
234
235

		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
236
237
				"=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n",
				e->e_id, ptr.bv_val, rc );
238
239
			goto done;
		}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
240
241
	}

Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
242
243
#ifndef BDB_MULTIPLE_SUFFIXES
	while( !be_issuffix( op->o_bd, &ptr ))
244
#else
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
245
	for (;;)
246
#endif
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
247
	{
248
		ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
249

250
		rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
251
252
		if( rc != 0 ) {
			Debug( LDAP_DEBUG_ANY,
Howard Chu's avatar
Howard Chu committed
253
254
				"=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
				e->e_id, ptr.bv_val, rc );
255
			goto done;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
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;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
266
	}
267
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
268
269

done:
270
	op->o_tmpfree( buf, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
271
	Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
272
273
274
275
	return rc;
}

int
Kurt Zeilenga's avatar
Kurt Zeilenga committed
276
bdb_dn2id(
277
	Operation *op,
278
	struct berval	*dn,
Howard Chu's avatar
Howard Chu committed
279
280
281
	EntryInfo *ei,
	u_int32_t locker,
	DB_LOCK *lock )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
282
{
283
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
284
	DB *db = bdb->bi_dn2id->bdi_db;
Howard Chu's avatar
Howard Chu committed
285
	DBC	*cursor;
286
287
288
	int		rc;
	DBT		key, data;
	ID		nid;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
289

290
	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );
Howard Chu's avatar
Howard Chu committed
291

Kurt Zeilenga's avatar
Kurt Zeilenga committed
292
	DBTzero( &key );
293
	key.size = dn->bv_len + 2;
294
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
295
	((char *)key.data)[0] = DN_BASE_PREFIX;
296
	AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
297

Kurt Zeilenga's avatar
Kurt Zeilenga committed
298
	/* store the ID */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
299
	DBTzero( &data );
300
	data.data = &nid;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
301
	data.ulen = sizeof(ID);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
302
303
	data.flags = DB_DBT_USERMEM;

Howard Chu's avatar
Howard Chu committed
304
305
306
307
308
309
310
311
312
313
	rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
	if ( rc ) goto leave;

	rc = bdb_dn2id_lock( bdb, dn, 0, locker, lock );
	if ( rc ) goto nolock;

	if ( locker ) {
		cursor->locker = locker;
	}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
314
	/* fetch it */
Howard Chu's avatar
Howard Chu committed
315
316
317
318
319
	rc = cursor->c_get( cursor, &key, &data, DB_SET );

nolock:
	cursor->c_close( cursor );
leave:
Kurt Zeilenga's avatar
Kurt Zeilenga committed
320

Kurt Zeilenga's avatar
Kurt Zeilenga committed
321
322
323
324
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
	} else {
Howard Chu's avatar
Howard Chu committed
325
		BDB_DISK2ID( &nid, &ei->bei_id );
Howard Chu's avatar
Howard Chu committed
326
		Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
Howard Chu's avatar
Howard Chu committed
327
			ei->bei_id, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
328
	}
329
	op->o_tmpfree( key.data, op->o_tmpmemctx );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
330
	return rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
331
332
}

Kurt Zeilenga's avatar
Kurt Zeilenga committed
333
334
int
bdb_dn2id_children(
335
	Operation *op,
Kurt Zeilenga's avatar
Kurt Zeilenga committed
336
	DB_TXN *txn,
337
	Entry *e )
Kurt Zeilenga's avatar
Kurt Zeilenga committed
338
{
339
340
341
342
	DBT		key, data;
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
	DB *db = bdb->bi_dn2id->bdi_db;
	ID		id;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
343
	int		rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
344

345
	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
346
		e->e_nname.bv_val, 0, 0 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
347
	DBTzero( &key );
348
	key.size = e->e_nname.bv_len + 2;
349
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
350
	((char *)key.data)[0] = DN_ONE_PREFIX;
351
	AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
352

353
354
355
	if ( bdb->bi_idl_cache_size ) {
		rc = bdb_idl_cache_get( bdb, db, &key, NULL );
		if ( rc != LDAP_NO_SUCH_OBJECT ) {
356
			op->o_tmpfree( key.data, op->o_tmpmemctx );
357
358
359
			return rc;
		}
	}
Kurt Zeilenga's avatar
Kurt Zeilenga committed
360
361
362
363
364
365
366
	/* we actually could do a empty get... */
	DBTzero( &data );
	data.data = &id;
	data.ulen = sizeof(id);
	data.flags = DB_DBT_USERMEM;
	data.doff = 0;
	data.dlen = sizeof(id);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
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 " :
Kurt Zeilenga's avatar
Kurt Zeilenga committed
374
			db_strerror(rc) ), rc );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
375

Kurt Zeilenga's avatar
Kurt Zeilenga committed
376
	return rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
377
}
378
379
380

int
bdb_dn2idl(
381
382
	Operation *op,
	Entry *e,
Howard Chu's avatar
Howard Chu committed
383
	ID *ids,
384
	ID *stack )
385
386
{
	int		rc;
387
	DBT		key;
388
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
389
	DB *db = bdb->bi_dn2id->bdi_db;
390
391
	int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
		? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
392

393
	Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n",
394
		e->e_nname.bv_val, 0, 0 );
395

396
#ifndef	BDB_MULTIPLE_SUFFIXES
397
	if ( prefix == DN_SUBTREE_PREFIX && BEI(e)->bei_parent->bei_id == 0 ) {
398
399
400
		BDB_IDL_ALL(bdb, ids);
		return 0;
	}
401
#endif
402

403
	DBTzero( &key );
404
	key.size = e->e_nname.bv_len + 2;
405
406
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
407
	key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
408
	((char *)key.data)[0] = prefix;
409
	AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
410

411
	BDB_IDL_ZERO( ids );
412
	rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids, NULL, 0 );
413
414
415
416
417

	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_dn2idl: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
418

419
420
421
	} else {
		Debug( LDAP_DEBUG_TRACE,
			"<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
422
423
			(long) ids[0],
			(long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
424
425
	}

426
	op->o_tmpfree( key.data, op->o_tmpmemctx );
427
428
	return rc;
}
429

Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
430
#else	/* BDB_HIER */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
431
/* Management routines for a hierarchically structured database.
432
 *
433
434
435
436
 * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 * entry in this database is a struct diskNode, keyed by entryID and with
 * the data containing the RDN and entryID of the node's children. We use
 * a B-Tree with sorted duplicates to store all the children of a node under
Howard Chu's avatar
Howard Chu committed
437
438
 * the same key. Also, the first item under the key contains the entry's own
 * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
Kurt Zeilenga's avatar
Kurt Zeilenga committed
439
440
441
442
 * well as top-down. To keep this info first in the list, the high bit of all
 * subsequent nrdnlen's is always set. This means we can only accomodate
 * RDNs up to length 32767, but that's fine since full DNs are already
 * restricted to 8192.
443
444
445
 *
 * The diskNode is a variable length structure. This definition is not
 * directly usable for in-memory manipulation.
446
447
 */
typedef struct diskNode {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
448
	unsigned char nrdnlen[2];
Kurt Zeilenga's avatar
Kurt Zeilenga committed
449
450
451
	char nrdn[1];
	char rdn[1];                        /* variable placement */
	unsigned char entryID[sizeof(ID)];  /* variable placement */
452
453
} diskNode;

Howard Chu's avatar
Howard Chu committed
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
/* Sort function for the sorted duplicate data items of a dn2id key.
 * Sorts based on normalized RDN, in length order.
 */
int
hdb_dup_compare(
	DB *db, 
	const DBT *usrkey,
	const DBT *curkey
)
{
	diskNode *un, *cn;
	int rc, ul, cl;

	un = (diskNode *)usrkey->data;
	cn = (diskNode *)curkey->data;

	/* data is not aligned, cannot compare directly */
	rc = un->nrdnlen[0] - cn->nrdnlen[0];
	if ( rc ) return rc;
	rc = un->nrdnlen[1] - cn->nrdnlen[1];
	if ( rc ) return rc;

	return strcmp( un->nrdn, cn->nrdn );
}

479
/* This function constructs a full DN for a given entry.
480
 */
481
int hdb_fix_dn(
482
	Entry *e,
Kurt Zeilenga's avatar
cleanup    
Kurt Zeilenga committed
483
	int checkit )
484
{
485
486
	EntryInfo *ei;
	int rlen = 0, nrlen = 0;
487
	char *ptr, *nptr;
488
	int max = 0;
489

490
491
492
	if ( !e->e_id )
		return 0;

493
	/* count length of all DN components */
Howard Chu's avatar
Howard Chu committed
494
	for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
495
496
		rlen += ei->bei_rdn.bv_len + 1;
		nrlen += ei->bei_nrdn.bv_len + 1;
497
		if (ei->bei_modrdns > max) max = ei->bei_modrdns;
498
	}
499
500
501
502
503
504
505
506
507
508
509
510

	/* See if the entry DN was invalidated by a subtree rename */
	if ( checkit ) {
		if ( BEI(e)->bei_modrdns >= max ) {
			return 0;
		}
		/* We found a mismatch, tell the caller to lock it */
		if ( checkit == 1 ) {
			return 1;
		}
		/* checkit == 2. do the fix. */
		free( e->e_name.bv_val );
511
		free( e->e_nname.bv_val );
512
513
	}

514
515
	e->e_name.bv_len = rlen - 1;
	e->e_nname.bv_len = nrlen - 1;
516
517
	e->e_name.bv_val = ch_malloc(rlen);
	e->e_nname.bv_val = ch_malloc(nrlen);
518
519
	ptr = e->e_name.bv_val;
	nptr = e->e_nname.bv_val;
Howard Chu's avatar
Howard Chu committed
520
	for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
521
522
523
524
525
526
		ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
		nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
		if ( ei->bei_parent ) {
			*ptr++ = ',';
			*nptr++ = ',';
		}
527
	}
528
	BEI(e)->bei_modrdns = max;
Howard Chu's avatar
Howard Chu committed
529
530
	ptr[-1] = '\0';
	nptr[-1] = '\0';
531
532
533
534

	return 0;
}

535
536
537
538
/* We add two elements to the DN2ID database - a data item under the parent's
 * entryID containing the child's RDN and entryID, and an item under the
 * child's entryID containing the parent's entryID.
 */
539
int
540
hdb_dn2id_add(
541
	Operation	*op,
542
	DB_TXN *txn,
543
	EntryInfo	*eip,
544
	Entry		*e )
545
{
546
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
547
	DB *db = bdb->bi_dn2id->bdi_db;
548
	DBT		key, data;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
549
	ID		nid;
550
	int		rc, rlen, nrlen;
551
	diskNode *d;
552
	char *ptr;
553

Howard Chu's avatar
Howard Chu committed
554
555
556
	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );

557
	nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
Howard Chu's avatar
Howard Chu committed
558
	if (nrlen) {
559
		rlen = dn_rdnlen( op->o_bd, &e->e_name );
Howard Chu's avatar
Howard Chu committed
560
	} else {
Howard Chu's avatar
Howard Chu committed
561
562
		nrlen = e->e_nname.bv_len;
		rlen = e->e_name.bv_len;
Howard Chu's avatar
Howard Chu committed
563
	}
564

565
	d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
566
567
	d->nrdnlen[1] = nrlen & 0xff;
	d->nrdnlen[0] = (nrlen >> 8) | 0x80;
568
569
570
	ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
	*ptr++ = '\0';
	ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
571
572
	*ptr++ = '\0';
	BDB_ID2DISK( e->e_id, ptr );
573
574
575
576
577

	DBTzero(&key);
	DBTzero(&data);
	key.size = sizeof(ID);
	key.flags = DB_DBT_USERMEM;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
578
	BDB_ID2DISK( eip->bei_id, &nid );
579

580
581
	key.data = &nid;

Howard Chu's avatar
Howard Chu committed
582
583
584
585
	/* Need to make dummy root node once. Subsequent attempts
	 * will fail harmlessly.
	 */
	if ( eip->bei_id == 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
586
		diskNode dummy = {{0, 0}, "", "", ""};
Howard Chu's avatar
Howard Chu committed
587
588
589
590
591
592
593
		data.data = &dummy;
		data.size = sizeof(diskNode);
		data.flags = DB_DBT_USERMEM;

		db->put( db, txn, &key, &data, DB_NODUPDATA );
	}

594
	data.data = d;
Howard Chu's avatar
Howard Chu committed
595
	data.size = sizeof(diskNode) + rlen + nrlen;
596
597
	data.flags = DB_DBT_USERMEM;

Howard Chu's avatar
Howard Chu committed
598
	rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
599
600

	if (rc == 0) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
601
602
603
		BDB_ID2DISK( e->e_id, &nid );
		BDB_ID2DISK( eip->bei_id, ptr );
		d->nrdnlen[0] ^= 0x80;
604

Howard Chu's avatar
Howard Chu committed
605
		rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
606
	}
607

Kurt Zeilenga's avatar
Kurt Zeilenga committed
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
	/* Update all parents' IDL cache entries */
	if ( rc == 0 && bdb->bi_idl_cache_size ) {
		ID tmp[2];
		char *ptr = ((char *)&tmp[1])-1;
		key.data = ptr;
		key.size = sizeof(ID)+1;
		tmp[1] = eip->bei_id;
		*ptr = DN_ONE_PREFIX;
		bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
		*ptr = DN_SUBTREE_PREFIX;
		for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
			tmp[1] = eip->bei_id;
			bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
		}
	}
Howard Chu's avatar
Howard Chu committed
623
624

leave:
625
	op->o_tmpfree( d, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
626
	Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
627

628
629
630
631
	return rc;
}

int
632
hdb_dn2id_delete(
633
	Operation	*op,
634
	DB_TXN *txn,
635
	EntryInfo	*eip,
636
	Entry	*e )
637
{
638
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
639
640
641
642
	DB *db = bdb->bi_dn2id->bdi_db;
	DBT		key, data;
	DBC	*cursor;
	diskNode *d;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
643
	int rc;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
644
	ID	nid;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
645
	unsigned char dlen[2];
Howard Chu's avatar
Howard Chu committed
646
647
648
649
	DB_LOCK	lock;

	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n",
		e->e_id, e->e_ndn, 0 );
650
651

	DBTzero(&key);
652
653
654
	key.size = sizeof(ID);
	key.ulen = key.size;
	key.flags = DB_DBT_USERMEM;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
655
	BDB_ID2DISK( eip->bei_id, &nid );
656

657
	DBTzero(&data);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
658
	data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1;
659
660
661
	data.ulen = data.size;
	data.dlen = data.size;
	data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
662

663
	key.data = &nid;
664

665
	d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
666
667
	d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
	d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
668
669
	dlen[0] = d->nrdnlen[0];
	dlen[1] = d->nrdnlen[1];
Howard Chu's avatar
Howard Chu committed
670
671
672
	strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
	data.data = d;

Howard Chu's avatar
Howard Chu committed
673
674
675
676
677
678
679
	rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
	if ( rc ) goto leave;

	/* We hold this lock until the TXN completes */
	rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
	if ( rc ) goto nolock;

Howard Chu's avatar
Howard Chu committed
680
	/* Delete our ID from the parent's list */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
681
	rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
682
	if ( rc == 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
683
		if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] &&
Kurt Zeilenga's avatar
Kurt Zeilenga committed
684
			!strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val ))
Kurt Zeilenga's avatar
Kurt Zeilenga committed
685
686
687
688
			rc = cursor->c_del( cursor, 0 );
		else
			rc = DB_NOTFOUND;
	}
689

Howard Chu's avatar
Howard Chu committed
690
691
692
693
694
	/* Delete our ID from the tree. With sorted duplicates, this
	 * will leave any child nodes still hanging around. This is OK
	 * for modrdn, which will add our info back in later.
	 */
	if ( rc == 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
695
		BDB_ID2DISK( e->e_id, &nid );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
696
		rc = cursor->c_get( cursor, &key, &data, DB_SET );
Howard Chu's avatar
Howard Chu committed
697
698
699
		if ( rc == 0 )
			rc = cursor->c_del( cursor, 0 );
	}
Howard Chu's avatar
Howard Chu committed
700
701

nolock:
Howard Chu's avatar
Howard Chu committed
702
	cursor->c_close( cursor );
Howard Chu's avatar
Howard Chu committed
703
leave:
704
	op->o_tmpfree( d, op->o_tmpmemctx );
705

Kurt Zeilenga's avatar
Kurt Zeilenga committed
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
	/* Delete IDL cache entries */
	if ( rc == 0 && bdb->bi_idl_cache_size ) {
		ID tmp[2];
		char *ptr = ((char *)&tmp[1])-1;
		key.data = ptr;
		key.size = sizeof(ID)+1;
		tmp[1] = eip->bei_id;
		*ptr = DN_ONE_PREFIX;
		bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
		*ptr = DN_SUBTREE_PREFIX;
		for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
			tmp[1] = eip->bei_id;
			bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
		}
	}
Howard Chu's avatar
Howard Chu committed
721
	Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
722
723
724
	return rc;
}

725

726
int
727
hdb_dn2id(
728
	Operation	*op,
729
	struct berval	*in,
Howard Chu's avatar
Howard Chu committed
730
731
732
	EntryInfo	*ei,
	u_int32_t locker,
	DB_LOCK *lock )
733
{
734
	struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
735
736
737
738
	DB *db = bdb->bi_dn2id->bdi_db;
	DBT		key, data;
	DBC	*cursor;
	int		rc = 0, nrlen;
Howard Chu's avatar
Howard Chu committed
739
	diskNode *d;
740
	char	*ptr;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
741
	unsigned char dlen[2];
Kurt Zeilenga's avatar
Kurt Zeilenga committed
742
	ID idp, parentID;
743

Howard Chu's avatar
Howard Chu committed
744
745
	Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );

746
	nrlen = dn_rdnlen( op->o_bd, in );
Howard Chu's avatar
Howard Chu committed
747
	if (!nrlen) nrlen = in->bv_len;
748

749
750
	DBTzero(&key);
	key.size = sizeof(ID);
Howard Chu's avatar
Howard Chu committed
751
752
	key.data = &idp;
	key.ulen = sizeof(ID);
753
	key.flags = DB_DBT_USERMEM;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
754
755
	parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0;
	BDB_ID2DISK( parentID, &idp );
756

757
	DBTzero(&data);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
758
	data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
759
	data.ulen = data.size * 3;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
760
761
	data.dlen = data.ulen;
	data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
Howard Chu's avatar
Howard Chu committed
762

Howard Chu's avatar
Howard Chu committed
763
	rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
764
	if ( rc ) return rc;
Howard Chu's avatar
Howard Chu committed
765
766
767
	if ( locker ) {
		cursor->locker = locker;
	}
768

769
	d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
770
771
	d->nrdnlen[1] = nrlen & 0xff;
	d->nrdnlen[0] = (nrlen >> 8) | 0x80;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
772
773
	dlen[0] = d->nrdnlen[0];
	dlen[1] = d->nrdnlen[1];
Howard Chu's avatar
Howard Chu committed
774
775
776
777
	ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
	*ptr = '\0';
	data.data = d;

Howard Chu's avatar
Howard Chu committed
778
779
780
	rc = bdb_dn2id_lock( bdb, in, 0, locker, lock );
	if ( rc ) goto leave;

Kurt Zeilenga's avatar
Kurt Zeilenga committed
781
	rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
782
783
	if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] ||
		strncmp( d->nrdn, in->bv_val, nrlen ))) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
784
785
		rc = DB_NOTFOUND;
	}
Howard Chu's avatar
Howard Chu committed
786
	if ( rc == 0 ) {
Kurt Zeilenga's avatar
Kurt Zeilenga committed
787
		ptr = (char *) data.data + data.size - sizeof(ID);
Kurt Zeilenga's avatar
Kurt Zeilenga committed
788
		BDB_DISK2ID( ptr, &ei->bei_id );
Howard Chu's avatar
Howard Chu committed
789
790
		ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
		ptr = d->nrdn + nrlen + 1;
791
		ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
Kurt Zeilenga's avatar
Kurt Zeilenga committed
792
		if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) {
793
794
795
796
797
798
799
800
			db_recno_t dkids;
			/* How many children does the parent have? */
			/* FIXME: do we need to lock the parent
			 * entryinfo? Seems safe...
			 */
			cursor->c_count( cursor, &dkids, 0 );
			ei->bei_parent->bei_dkids = dkids;
		}
Howard Chu's avatar
Howard Chu committed
801
	}
Howard Chu's avatar
Howard Chu committed
802
803

leave:
804
	cursor->c_close( cursor );
805
	op->o_tmpfree( d, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
806
807
808
809
810
811
812
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n",
			db_strerror( rc ), rc, 0 );
	} else {
		Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n",
			ei->bei_id, 0, 0 );
	}
Howard Chu's avatar
Howard Chu committed
813
814
815
816
817

	return rc;
}

int