dn2id.c 23.6 KB
Newer Older
Howard Chu's avatar
Howard Chu committed
1
2
3
4
/* dn2id.c - routines to deal with the dn2id index */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
5
 * Copyright 2000-2020 The OpenLDAP Foundation.
Howard Chu's avatar
Howard Chu committed
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 * 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>.
 */

#include "portable.h"

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

#include "back-mdb.h"
#include "idl.h"
#include "lutil.h"

/* Management routines for a hierarchically structured database.
 *
 * 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
 * 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
 * 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.
 *
39
40
41
 * Also each child node contains a count of the number of entries in
 * its subtree, appended after its entryID.
 *
Howard Chu's avatar
Howard Chu committed
42
43
44
45
46
47
48
49
 * The diskNode is a variable length structure. This definition is not
 * directly usable for in-memory manipulation.
 */
typedef struct diskNode {
	unsigned char nrdnlen[2];
	char nrdn[1];
	char rdn[1];                        /* variable placement */
	unsigned char entryID[sizeof(ID)];  /* variable placement */
50
	/* unsigned char nsubs[sizeof(ID)];	in child nodes only */
Howard Chu's avatar
Howard Chu committed
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
} diskNode;

/* Sort function for the sorted duplicate data items of a dn2id key.
 * Sorts based on normalized RDN, in length order.
 */
int
mdb_dup_compare(
	const MDB_val *usrkey,
	const MDB_val *curkey
)
{
	diskNode *un, *cn;
	int rc, nrlen;

	un = (diskNode *)usrkey->mv_data;
	cn = (diskNode *)curkey->mv_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;

74
	nrlen = ((un->nrdnlen[0] & 0x7f) << 8) | un->nrdnlen[1];
Howard Chu's avatar
Howard Chu committed
75
76
77
78
79
80
81
82
83
84
	return strncmp( un->nrdn, cn->nrdn, nrlen );
}

/* 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.
 */
int
mdb_dn2id_add(
	Operation	*op,
85
86
	MDB_cursor	*mcp,
	MDB_cursor	*mcd,
Howard Chu's avatar
Howard Chu committed
87
	ID pid,
88
	ID nsubs,
89
	int upsub,
Howard Chu's avatar
Howard Chu committed
90
91
92
93
94
95
96
97
98
99
	Entry		*e )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_val		key, data;
	ID		nid;
	int		rc, rlen, nrlen;
	diskNode *d;
	char *ptr;

	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_add 0x%lx: \"%s\"\n",
Howard Chu's avatar
Howard Chu committed
100
		e->e_id, e->e_ndn ? e->e_ndn : "", 0 );
Howard Chu's avatar
Howard Chu committed
101
102
103
104
105
106
107
108
109

	nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
	if (nrlen) {
		rlen = dn_rdnlen( op->o_bd, &e->e_name );
	} else {
		nrlen = e->e_nname.bv_len;
		rlen = e->e_name.bv_len;
	}

110
	d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen + sizeof(ID), op->o_tmpmemctx);
Howard Chu's avatar
Howard Chu committed
111
112
113
114
115
116
117
	d->nrdnlen[1] = nrlen & 0xff;
	d->nrdnlen[0] = (nrlen >> 8) | 0x80;
	ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
	*ptr++ = '\0';
	ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
	*ptr++ = '\0';
	memcpy( ptr, &e->e_id, sizeof( ID ));
118
119
	ptr += sizeof( ID );
	memcpy( ptr, &nsubs, sizeof( ID ));
Howard Chu's avatar
Howard Chu committed
120
121
122
123
124
125
126
127
128
129
130
131
132
133

	key.mv_size = sizeof(ID);
	key.mv_data = &nid;

	nid = pid;

	/* Need to make dummy root node once. Subsequent attempts
	 * will fail harmlessly.
	 */
	if ( pid == 0 ) {
		diskNode dummy = {{0, 0}, "", "", ""};
		data.mv_data = &dummy;
		data.mv_size = sizeof(diskNode);

134
		mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
Howard Chu's avatar
Howard Chu committed
135
136
137
	}

	data.mv_data = d;
138
	data.mv_size = sizeof(diskNode) + rlen + nrlen + sizeof( ID );
Howard Chu's avatar
Howard Chu committed
139

140
	/* Add our child node under parent's key */
141
	rc = mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
Howard Chu's avatar
Howard Chu committed
142

143
	/* Add our own node */
Howard Chu's avatar
Howard Chu committed
144
	if (rc == 0) {
145
		int flag = MDB_NODUPDATA;
Howard Chu's avatar
Howard Chu committed
146
		nid = e->e_id;
147
148
149
		/* drop subtree count */
		data.mv_size -= sizeof( ID );
		ptr -= sizeof( ID );
Howard Chu's avatar
Howard Chu committed
150
151
152
		memcpy( ptr, &pid, sizeof( ID ));
		d->nrdnlen[0] ^= 0x80;

Howard Chu's avatar
Howard Chu committed
153
		if ((slapMode & SLAP_TOOL_MODE) || (e->e_id == mdb->mi_nextid))
154
155
			flag |= MDB_APPEND;
		rc = mdb_cursor_put( mcd, &key, &data, flag );
Howard Chu's avatar
Howard Chu committed
156
157
	}
	op->o_tmpfree( d, op->o_tmpmemctx );
158
159

	/* Add our subtree count to all superiors */
160
	if ( rc == 0 && upsub && pid ) {
161
162
163
164
165
166
167
		ID subs;
		nid = pid;
		do {
			/* Get parent's RDN */
			rc = mdb_cursor_get( mcp, &key, &data, MDB_SET );
			if ( !rc ) {
				char *p2;
168
				ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
169
170
171
172
173
174
175
176
177
178
179
180
				memcpy( &nid, ptr, sizeof( ID ));
				/* Get parent's node under grandparent */
				d = data.mv_data;
				rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
				p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
				memcpy( p2, data.mv_data, rlen+2 );
				*p2 ^= 0x80;
				data.mv_data = p2;
				rc = mdb_cursor_get( mcp, &key, &data, MDB_GET_BOTH );
				op->o_tmpfree( p2, op->o_tmpmemctx );
				if ( !rc ) {
					/* Get parent's subtree count */
181
					ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
					memcpy( &subs, ptr, sizeof( ID ));
					subs += nsubs;
					p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
					memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
					memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
					data.mv_data = p2;
					rc = mdb_cursor_put( mcp, &key, &data, MDB_CURRENT );
					op->o_tmpfree( p2, op->o_tmpmemctx );
				}
			}
			if ( rc )
				break;
		} while ( nid );
	}

Howard Chu's avatar
Howard Chu committed
197
198
199
200
201
	Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );

	return rc;
}

202
/* mc must have been set by mdb_dn2id */
Howard Chu's avatar
Howard Chu committed
203
204
205
int
mdb_dn2id_delete(
	Operation	*op,
206
	MDB_cursor *mc,
207
208
	ID id,
	ID nsubs )
Howard Chu's avatar
Howard Chu committed
209
{
210
211
	ID nid;
	char *ptr;
212
	int rc;
Howard Chu's avatar
Howard Chu committed
213

214
215
	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_delete 0x%lx\n",
		id, 0, 0 );
Howard Chu's avatar
Howard Chu committed
216
217

	/* Delete our ID from the parent's list */
218
	rc = mdb_cursor_del( mc, 0 );
Howard Chu's avatar
Howard Chu committed
219
220
221
222
223
224

	/* 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 ) {
Howard Chu's avatar
Howard Chu committed
225
		MDB_val	key, data;
226
227
228
229
		if ( nsubs ) {
			mdb_cursor_get( mc, &key, NULL, MDB_GET_CURRENT );
			memcpy( &nid, key.mv_data, sizeof( ID ));
		}
230
231
		key.mv_size = sizeof(ID);
		key.mv_data = &id;
Howard Chu's avatar
Howard Chu committed
232
		rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
233
234
		if ( rc == 0 )
			rc = mdb_cursor_del( mc, 0 );
Howard Chu's avatar
Howard Chu committed
235
236
	}

237
238
239
240
241
242
243
244
245
246
247
248
	/* Delete our subtree count from all superiors */
	if ( rc == 0 && nsubs && nid ) {
		MDB_val key, data;
		ID subs;
		key.mv_data = &nid;
		key.mv_size = sizeof( ID );
		do {
			rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
			if ( !rc ) {
				char *p2;
				diskNode *d;
				int rlen;
249
				ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
250
251
252
253
254
255
256
257
258
259
260
261
				memcpy( &nid, ptr, sizeof( ID ));
				/* Get parent's node under grandparent */
				d = data.mv_data;
				rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
				p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
				memcpy( p2, data.mv_data, rlen+2 );
				*p2 ^= 0x80;
				data.mv_data = p2;
				rc = mdb_cursor_get( mc, &key, &data, MDB_GET_BOTH );
				op->o_tmpfree( p2, op->o_tmpmemctx );
				if ( !rc ) {
					/* Get parent's subtree count */
262
					ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
					memcpy( &subs, ptr, sizeof( ID ));
					subs -= nsubs;
					p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
					memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
					memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
					data.mv_data = p2;
					rc = mdb_cursor_put( mc, &key, &data, MDB_CURRENT );
					op->o_tmpfree( p2, op->o_tmpmemctx );
				}

			}
			if ( rc )
				break;
		} while ( nid );
	}

279
	Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_delete 0x%lx: %d\n", id, rc, 0 );
Howard Chu's avatar
Howard Chu committed
280
281
282
	return rc;
}

283
284
/* return last found ID in *id if no match
 * If mc is provided, it will be left pointing to the RDN's
285
286
 * record under the parent's ID. If nsubs is provided, return
 * the number of entries in this entry's subtree.
287
 */
Howard Chu's avatar
Howard Chu committed
288
289
290
291
int
mdb_dn2id(
	Operation	*op,
	MDB_txn *txn,
292
	MDB_cursor	*mc,
Howard Chu's avatar
Howard Chu committed
293
294
	struct berval	*in,
	ID	*id,
295
	ID	*nsubs,
Howard Chu's avatar
Howard Chu committed
296
297
298
299
300
301
302
303
304
305
306
307
308
309
	struct berval	*matched,
	struct berval	*nmatched )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_cursor *cursor;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
	int		rc = 0, nrlen;
	diskNode *d;
	char	*ptr;
	char dn[SLAP_LDAPDN_MAXLEN];
	ID pid, nid;
	struct berval tmp;

Howard Chu's avatar
Howard Chu committed
310
	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id(\"%s\")\n", in->bv_val ? in->bv_val : "", 0, 0 );
Howard Chu's avatar
Howard Chu committed
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

	if ( matched ) {
		matched->bv_val = dn + sizeof(dn) - 1;
		matched->bv_len = 0;
		*matched->bv_val-- = '\0';
	}
	if ( nmatched ) {
		nmatched->bv_len = 0;
		nmatched->bv_val = 0;
	}

	if ( !in->bv_len ) {
		*id = 0;
		nid = 0;
		goto done;
	}

	tmp = *in;

	if ( op->o_bd->be_nsuffix[0].bv_len ) {
		nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
		tmp.bv_val += nrlen;
		tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
	} else {
		for ( ptr = tmp.bv_val + tmp.bv_len - 1; ptr >= tmp.bv_val; ptr-- )
			if (DN_SEPARATOR(*ptr))
				break;
		ptr++;
		tmp.bv_len -= ptr - tmp.bv_val;
		tmp.bv_val = ptr;
	}
	nid = 0;
	key.mv_size = sizeof(ID);

345
346
347
348
	if ( mc ) {
		cursor = mc;
	} else {
		rc = mdb_cursor_open( txn, dbi, &cursor );
Leonid Yuriev's avatar
Leonid Yuriev committed
349
		if ( rc ) goto done;
350
	}
Howard Chu's avatar
Howard Chu committed
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366

	for (;;) {
		key.mv_data = &pid;
		pid = nid;

		data.mv_size = sizeof(diskNode) + tmp.bv_len;
		d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
		d->nrdnlen[1] = tmp.bv_len & 0xff;
		d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
		ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
		*ptr = '\0';
		data.mv_data = d;
		rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
		op->o_tmpfree( d, op->o_tmpmemctx );
		if ( rc )
			break;
367
		ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
Howard Chu's avatar
Howard Chu committed
368
369
370
371
372
373
		memcpy( &nid, ptr, sizeof(ID));

		/* grab the non-normalized RDN */
		if ( matched ) {
			int rlen;
			d = data.mv_data;
374
			rlen = data.mv_size - sizeof(diskNode) - tmp.bv_len - sizeof(ID);
Howard Chu's avatar
Howard Chu committed
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
			matched->bv_len += rlen;
			matched->bv_val -= rlen + 1;
			ptr = lutil_strcopy( matched->bv_val, d->rdn + tmp.bv_len );
			if ( pid ) {
				*ptr = ',';
				matched->bv_len++;
			}
		}
		if ( nmatched ) {
			nmatched->bv_val = tmp.bv_val;
		}

		if ( tmp.bv_val > in->bv_val ) {
			for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
				!DN_SEPARATOR(*ptr); ptr--)	/* empty */;
			if ( ptr >= in->bv_val ) {
				if (DN_SEPARATOR(*ptr)) ptr++;
				tmp.bv_len = tmp.bv_val - ptr - 1;
				tmp.bv_val = ptr;
			}
		} else {
			break;
		}
	}
	*id = nid; 
400
401
	/* return subtree count if requested */
	if ( !rc && nsubs ) {
402
		ptr = (char *)data.mv_data + data.mv_size - sizeof(ID);
403
404
		memcpy( nsubs, ptr, sizeof( ID ));
	}
405
406
	if ( !mc )
		mdb_cursor_close( cursor );
Howard Chu's avatar
Howard Chu committed
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
done:
	if ( matched ) {
		if ( matched->bv_len ) {
			ptr = op->o_tmpalloc( matched->bv_len+1, op->o_tmpmemctx );
			strcpy( ptr, matched->bv_val );
			matched->bv_val = ptr;
		} else {
			if ( BER_BVISEMPTY( &op->o_bd->be_nsuffix[0] ) && !nid ) {
				ber_dupbv( matched, (struct berval *)&slap_empty_bv );
			} else {
				matched->bv_val = NULL;
			}
		}
	}
	if ( nmatched ) {
		if ( nmatched->bv_val ) {
			nmatched->bv_len = in->bv_len - (nmatched->bv_val - in->bv_val);
		} else {
			*nmatched = slap_empty_bv;
		}
	}

	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: get failed: %s (%d)\n",
			mdb_strerror( rc ), rc, 0 );
	} else {
		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n",
			nid, 0, 0 );
	}

	return rc;
}

/* return IDs from root to parent of DN */
int
mdb_dn2sups(
	Operation	*op,
	MDB_txn *txn,
	struct berval	*in,
	ID	*ids )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_cursor *cursor;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
	int		rc = 0, nrlen;
	diskNode *d;
	char	*ptr;
	ID pid, nid;
	struct berval tmp;

	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2sups(\"%s\")\n", in->bv_val, 0, 0 );

	if ( !in->bv_len ) {
		goto done;
	}

	tmp = *in;

	nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
	tmp.bv_val += nrlen;
	tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
	nid = 0;
	key.mv_size = sizeof(ID);

	rc = mdb_cursor_open( txn, dbi, &cursor );
Leonid Yuriev's avatar
Leonid Yuriev committed
473
	if ( rc ) goto done;
Howard Chu's avatar
Howard Chu committed
474
475
476
477
478
479
480
481
482
483
484
485
486
487

	for (;;) {
		key.mv_data = &pid;
		pid = nid;

		data.mv_size = sizeof(diskNode) + tmp.bv_len;
		d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
		d->nrdnlen[1] = tmp.bv_len & 0xff;
		d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
		ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
		*ptr = '\0';
		data.mv_data = d;
		rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
		op->o_tmpfree( d, op->o_tmpmemctx );
488
		if ( rc )
Howard Chu's avatar
Howard Chu committed
489
			break;
490
		ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
Howard Chu's avatar
Howard Chu committed
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
		memcpy( &nid, ptr, sizeof(ID));

		if ( pid )
			mdb_idl_insert( ids, pid );

		if ( tmp.bv_val > in->bv_val ) {
			for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
				!DN_SEPARATOR(*ptr); ptr--)	/* empty */;
			if ( ptr >= in->bv_val ) {
				if (DN_SEPARATOR(*ptr)) ptr++;
				tmp.bv_len = tmp.bv_val - ptr - 1;
				tmp.bv_val = ptr;
			}
		} else {
			break;
		}
	}
508
	mdb_cursor_close( cursor );
Howard Chu's avatar
Howard Chu committed
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
done:
	if( rc != 0 ) {
		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n",
			mdb_strerror( rc ), rc, 0 );
	}

	return rc;
}

int
mdb_dn2id_children(
	Operation *op,
	MDB_txn *txn,
	Entry *e )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
	MDB_cursor	*cursor;
	int		rc;
	ID		id;

	key.mv_size = sizeof(ID);
	key.mv_data = &id;
	id = e->e_id;

	rc = mdb_cursor_open( txn, dbi, &cursor );
	if ( rc ) return rc;

	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
	if ( rc == 0 ) {
540
		size_t dkids;
Howard Chu's avatar
Howard Chu committed
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
		rc = mdb_cursor_count( cursor, &dkids );
		if ( rc == 0 ) {
			if ( dkids < 2 ) rc = MDB_NOTFOUND;
		}
	}
	mdb_cursor_close( cursor );
	return rc;
}

int
mdb_id2name(
	Operation *op,
	MDB_txn *txn,
	MDB_cursor **cursp,
	ID id,
	struct berval *name,
557
	struct berval *nname )
Howard Chu's avatar
Howard Chu committed
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
	MDB_cursor	*cursor;
	int		rc, len, nlen;
	char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr;
	char *dptr, *nptr;
	diskNode *d;

	key.mv_size = sizeof(ID);

	if ( !*cursp ) {
		rc = mdb_cursor_open( txn, dbi, cursp );
		if ( rc ) return rc;
	}
	cursor = *cursp;

	len = 0;
	nlen = 0;
	dptr = dn;
	nptr = ndn;
	while (id) {
		unsigned int nrlen, rlen;
		key.mv_data = &id;
		data.mv_size = 0;
		data.mv_data = "";
		rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
		if ( rc ) break;
		ptr = data.mv_data;
		ptr += data.mv_size - sizeof(ID);
		memcpy( &id, ptr, sizeof(ID) );
		d = data.mv_data;
		nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
		rlen = data.mv_size - sizeof(diskNode) - nrlen;
		assert( nrlen < 1024 && rlen < 1024 );	/* FIXME: Sanity check */
		if (nptr > ndn) {
			*nptr++ = ',';
			*dptr++ = ',';
		}
		/* copy name and trailing NUL */
		memcpy( nptr, d->nrdn, nrlen+1 );
		memcpy( dptr, d->nrdn+nrlen+1, rlen+1 );
		nptr += nrlen;
		dptr += rlen;
	}
	if ( rc == 0 ) {
		name->bv_len = dptr - dn;
		nname->bv_len = nptr - ndn;
		name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx );
		nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx );
		memcpy( name->bv_val, dn, name->bv_len );
		name->bv_val[name->bv_len] = '\0';
		memcpy( nname->bv_val, ndn, nname->bv_len );
		nname->bv_val[nname->bv_len] = '\0';
	}
	return rc;
}

/* Find each id in ids that is a child of base and move it to res.
 */
int
mdb_idscope(
	Operation *op,
	MDB_txn *txn,
	ID base,
	ID *ids,
	ID *res )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
	MDB_cursor	*cursor;
Howard Chu's avatar
Howard Chu committed
631
	ID ida, id, cid = 0, ci0 = 0, idc = 0;
Howard Chu's avatar
Howard Chu committed
632
	char	*ptr;
Howard Chu's avatar
Howard Chu committed
633
	int		rc, copy;
Howard Chu's avatar
Howard Chu committed
634
635
636
637
638
639
640
641

	key.mv_size = sizeof(ID);

	MDB_IDL_ZERO( res );

	rc = mdb_cursor_open( txn, dbi, &cursor );
	if ( rc ) return rc;

642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
	/* first see if base has any children at all */
	key.mv_data = &base;
	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
	if ( rc ) {
		goto leave;
	}
	{
		size_t dkids;
		rc = mdb_cursor_count( cursor, &dkids );
		if ( rc == 0 ) {
			if ( dkids < 2 ) {
				goto leave;
			}
		}
	}

Howard Chu's avatar
Howard Chu committed
658
659
660
661
662
663
664
665
666
	ida = mdb_idl_first( ids, &cid );

	/* Don't bother moving out of ids if it's a range */
	if (!MDB_IDL_IS_RANGE(ids)) {
		idc = ids[0];
		ci0 = cid;
	}

	while (ida != NOID) {
Howard Chu's avatar
Howard Chu committed
667
		copy = 1;
Howard Chu's avatar
Howard Chu committed
668
669
670
671
672
		id = ida;
		while (id) {
			key.mv_data = &id;
			rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
			if ( rc ) {
Howard Chu's avatar
Howard Chu committed
673
674
				/* not found, drop this from ids */
				copy = 0;
Howard Chu's avatar
Howard Chu committed
675
676
677
678
679
680
				break;
			}
			ptr = data.mv_data;
			ptr += data.mv_size - sizeof(ID);
			memcpy( &id, ptr, sizeof(ID) );
			if ( id == base ) {
681
682
683
684
685
				if ( res[0] >= MDB_IDL_DB_SIZE-1 ) {
					/* too many aliases in scope. Fallback to range */
					MDB_IDL_RANGE( res, MDB_IDL_FIRST( ids ), MDB_IDL_LAST( ids ));
					goto leave;
				}
Howard Chu's avatar
Howard Chu committed
686
687
				res[0]++;
				res[res[0]] = ida;
Howard Chu's avatar
Howard Chu committed
688
				copy = 0;
Howard Chu's avatar
Howard Chu committed
689
690
691
692
693
				break;
			}
			if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
				break;
		}
Howard Chu's avatar
Howard Chu committed
694
695
696
697
698
699
700
701
		if (idc) {
			if (copy) {
				if (ci0 != cid)
					ids[ci0] = ids[cid];
				ci0++;
			} else
				idc--;
		}
Howard Chu's avatar
Howard Chu committed
702
703
704
705
706
		ida = mdb_idl_next( ids, &cid );
	}
	if (!MDB_IDL_IS_RANGE( ids ))
		ids[0] = idc;

707
leave:
Howard Chu's avatar
Howard Chu committed
708
709
710
711
712
713
714
715
716
	mdb_cursor_close( cursor );
	return rc;
}

/* See if base is a child of any of the scopes
 */
int
mdb_idscopes(
	Operation *op,
Howard Chu's avatar
Howard Chu committed
717
	IdScopes *isc )
Howard Chu's avatar
Howard Chu committed
718
719
720
721
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_dbi dbi = mdb->mi_dn2id;
	MDB_val		key, data;
Howard Chu's avatar
Howard Chu committed
722
	ID id, prev;
Howard Chu's avatar
Howard Chu committed
723
	ID2 id2;
Howard Chu's avatar
Howard Chu committed
724
	char	*ptr;
725
	int		rc = 0;
Howard Chu's avatar
Howard Chu committed
726
	unsigned int x;
Howard Chu's avatar
Howard Chu committed
727
728
	unsigned int nrlen, rlen;
	diskNode *d;
Howard Chu's avatar
Howard Chu committed
729
730
731

	key.mv_size = sizeof(ID);

Howard Chu's avatar
Howard Chu committed
732
733
	if ( !isc->mc ) {
		rc = mdb_cursor_open( isc->mt, dbi, &isc->mc );
Howard Chu's avatar
Howard Chu committed
734
735
736
		if ( rc ) return rc;
	}

Howard Chu's avatar
Howard Chu committed
737
	id = isc->id;
Howard Chu's avatar
Howard Chu committed
738
739
740
741
742
743
744
745

	/* Catch entries from deref'd aliases */
	x = mdb_id2l_search( isc->scopes, id );
	if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
		isc->nscope = x;
		return MDB_SUCCESS;
	}

746
	isc->sctmp[0].mid = 0;
Howard Chu's avatar
Howard Chu committed
747
	while (id) {
748
		if ( !rc ) {
Howard Chu's avatar
Howard Chu committed
749
750
751
			key.mv_data = &id;
			rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
			if ( rc )
752
				return rc;
Howard Chu's avatar
Howard Chu committed
753

Howard Chu's avatar
Howard Chu committed
754
755
			/* save RDN info */
		}
Howard Chu's avatar
Howard Chu committed
756
757
758
759
760
761
762
763
764
		d = data.mv_data;
		nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
		rlen = data.mv_size - sizeof(diskNode) - nrlen;
		isc->nrdns[isc->numrdns].bv_len = nrlen;
		isc->nrdns[isc->numrdns].bv_val = d->nrdn;
		isc->rdns[isc->numrdns].bv_len = rlen;
		isc->rdns[isc->numrdns].bv_val = d->nrdn+nrlen+1;
		isc->numrdns++;

Howard Chu's avatar
Howard Chu committed
765
		if (!rc && id != isc->id) {
766
			/* remember our chain of parents */
Howard Chu's avatar
Howard Chu committed
767
768
			id2.mid = id;
			id2.mval = data;
769
			mdb_id2l_insert( isc->sctmp, &id2 );
Howard Chu's avatar
Howard Chu committed
770
		}
Howard Chu's avatar
Howard Chu committed
771
772
		ptr = data.mv_data;
		ptr += data.mv_size - sizeof(ID);
Howard Chu's avatar
Howard Chu committed
773
		prev = id;
Howard Chu's avatar
Howard Chu committed
774
		memcpy( &id, ptr, sizeof(ID) );
Howard Chu's avatar
Howard Chu committed
775
776
777
778
		/* If we didn't advance, some parent is missing */
		if ( id == prev )
			return MDB_NOTFOUND;

779
780
781
		x = mdb_id2l_search( isc->scopes, id );
		if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
			if ( !isc->scopes[x].mval.mv_data ) {
782
				/* This node is in scope, add parent chain to scope */
783
784
785
				int i;
				for ( i = 1; i <= isc->sctmp[0].mid; i++ ) {
					rc = mdb_id2l_insert( isc->scopes, &isc->sctmp[i] );
Howard Chu's avatar
Howard Chu committed
786
787
					if ( rc )
						break;
788
				}
789
790
791
				/* check id again since inserts may have changed its position */
				if ( isc->scopes[x].mid != id )
					x = mdb_id2l_search( isc->scopes, id );
792
793
794
795
796
797
				isc->nscope = x;
				return MDB_SUCCESS;
			}
			data = isc->scopes[x].mval;
			rc = 1;
		}
Howard Chu's avatar
Howard Chu committed
798
799
800
		if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
			break;
	}
801
	return MDB_SUCCESS;
Howard Chu's avatar
Howard Chu committed
802
}
803

Howard Chu's avatar
Howard Chu committed
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
/* See if ID is a child of any of the scopes,
 * return MDB_KEYEXIST if so.
 */
int
mdb_idscopechk(
	Operation *op,
	IdScopes *isc )
{
	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
	MDB_val		key, data;
	ID id, prev;
	char	*ptr;
	int		rc = 0;
	unsigned int x;

	key.mv_size = sizeof(ID);

	if ( !isc->mc ) {
		rc = mdb_cursor_open( isc->mt, mdb->mi_dn2id, &isc->mc );
		if ( rc ) return rc;
	}

	id = isc->id;

	while (id) {
		if ( !rc ) {
			key.mv_data = &id;
			rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
			if ( rc )
				return rc;
		}

		ptr = data.mv_data;
		ptr += data.mv_size - sizeof(ID);
		prev = id;
		memcpy( &id, ptr, sizeof(ID) );
		/* If we didn't advance, some parent is missing */
		if ( id == prev )
			return MDB_NOTFOUND;

		x = mdb_id2l_search( isc->scopes, id );
		if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id )
			return MDB_KEYEXIST;
	}
	return MDB_SUCCESS;
}

851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
int
mdb_dn2id_walk(
	Operation *op,
	IdScopes *isc
)
{
	MDB_val key, data;
	diskNode *d;
	char *ptr;
	int rc, n;
	ID nsubs;

	if ( !isc->numrdns ) {
		key.mv_data = &isc->id;
		key.mv_size = sizeof(ID);
		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
		isc->scopes[0].mid = isc->id;
		isc->numrdns++;
		isc->nscope = 0;
		/* skip base if not a subtree walk */
Howard Chu's avatar
Howard Chu committed
871
872
		if ( isc->oscope == LDAP_SCOPE_SUBTREE ||
			isc->oscope == LDAP_SCOPE_BASE )
873
874
			return rc;
	}
Howard Chu's avatar
Howard Chu committed
875
	if ( isc->oscope == LDAP_SCOPE_BASE )
876
877
878
879
880
881
		return MDB_NOTFOUND;

	for (;;) {
		/* Get next sibling */
		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_NEXT_DUP );
		if ( !rc ) {
882
			ptr = (char *)data.mv_data + data.mv_size - 2*sizeof(ID);
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
			d = data.mv_data;
			memcpy( &isc->id, ptr, sizeof(ID));

			/* If we're pushing down, see if there's any children to find */
			if ( isc->nscope ) {
				ptr += sizeof(ID);
				memcpy( &nsubs, ptr, sizeof(ID));
				/* No children, go to next sibling */
				if ( nsubs < 2 )
					continue;
			}
			n = isc->numrdns;
			isc->scopes[n].mid = isc->id;
			n--;
			isc->nrdns[n].bv_len = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1];
			isc->nrdns[n].bv_val = d->nrdn;
			isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1;
			isc->rdns[n].bv_len = data.mv_size - sizeof(diskNode) - isc->nrdns[n].bv_len - sizeof(ID);
			/* return this ID to caller */
			if ( !isc->nscope )
				break;

			/* push down to child */
			key.mv_data = &isc->id;
			mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
			isc->nscope = 0;
			isc->numrdns++;
			continue;

		} else if ( rc == MDB_NOTFOUND ) {
Howard Chu's avatar
Howard Chu committed
913
			if ( !isc->nscope && isc->oscope != LDAP_SCOPE_ONELEVEL ) {
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
				/* reset to first dup */
				mdb_cursor_get( isc->mc, &key, NULL, MDB_GET_CURRENT );
				mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
				isc->nscope = 1;
				continue;
			} else {
				isc->numrdns--;
				/* stack is empty? */
				if ( !isc->numrdns )
					break;
				/* pop up to prev node */
				n = isc->numrdns - 1;
				key.mv_data = &isc->scopes[n].mid;
				key.mv_size = sizeof(ID);
				data.mv_data = isc->nrdns[n].bv_val - 2;
929
				data.mv_size = 1;	/* just needs to be non-zero, mdb_dup_compare doesn't care */
930
931
932
933
934
935
936
937
938
				mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH );
				continue;
			}
		} else {
			break;
		}
	}
	return rc;
}
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973

/* restore the nrdn/rdn pointers after a txn reset */
void mdb_dn2id_wrestore (
	Operation *op,
	IdScopes *isc
)
{
	MDB_val key, data;
	diskNode *d;
	int rc, n, nrlen;
	char *ptr;

	/* We only need to restore up to the n-1th element,
	 * the nth element will be replaced anyway
	 */
	key.mv_size = sizeof(ID);
	for ( n=0; n<isc->numrdns-1; n++ ) {
		key.mv_data = &isc->scopes[n+1].mid;
		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
		if ( rc )
			continue;
		/* we can't use this data directly since its nrlen
		 * is missing the high bit setting, so copy it and
		 * set it properly. we just copy enough to satisfy
		 * mdb_dup_compare.
		 */
		d = data.mv_data;
		nrlen = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1];
		ptr = op->o_tmpalloc( nrlen+2, op->o_tmpmemctx );
		memcpy( ptr, data.mv_data, nrlen+2 );
		key.mv_data = &isc->scopes[n].mid;
		data.mv_data = ptr;
		data.mv_size = 1;
		*ptr |= 0x80;
		mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH );
Howard Chu's avatar
Howard Chu committed
974
		op->o_tmpfree( ptr, op->o_tmpmemctx );
975
976
977
978
979
980
981

		/* now we're back to where we wanted to be */
		d = data.mv_data;
		isc->nrdns[n].bv_val = d->nrdn;
		isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1;
	}
}