xref: /netbsd-src/external/bsd/openldap/dist/servers/slapd/back-mdb/dn2id.c (revision 549b59ed3ccf0d36d3097190a0db27b770f3a839)
1 /*	$NetBSD: dn2id.c,v 1.3 2021/08/14 16:15:00 christos Exp $	*/
2 
3 /* dn2id.c - routines to deal with the dn2id index */
4 /* $OpenLDAP$ */
5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6  *
7  * Copyright 2000-2021 The OpenLDAP Foundation.
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted only as authorized by the OpenLDAP
12  * Public License.
13  *
14  * A copy of this license is available in the file LICENSE in the
15  * top-level directory of the distribution or, alternatively, at
16  * <http://www.OpenLDAP.org/license.html>.
17  */
18 
19 #include <sys/cdefs.h>
20 __RCSID("$NetBSD: dn2id.c,v 1.3 2021/08/14 16:15:00 christos Exp $");
21 
22 #include "portable.h"
23 
24 #include <stdio.h>
25 #include <ac/string.h>
26 
27 #include "back-mdb.h"
28 #include "idl.h"
29 #include "lutil.h"
30 
31 /* Management routines for a hierarchically structured database.
32  *
33  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
34  * entry in this database is a struct diskNode, keyed by entryID and with
35  * the data containing the RDN and entryID of the node's children. We use
36  * a B-Tree with sorted duplicates to store all the children of a node under
37  * the same key. Also, the first item under the key contains the entry's own
38  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
39  * well as top-down. To keep this info first in the list, the high bit of all
40  * subsequent nrdnlen's is always set. This means we can only accommodate
41  * RDNs up to length 32767, but that's fine since full DNs are already
42  * restricted to 8192.
43  *
44  * Also each child node contains a count of the number of entries in
45  * its subtree, appended after its entryID.
46  *
47  * The diskNode is a variable length structure. This definition is not
48  * directly usable for in-memory manipulation.
49  */
50 typedef struct diskNode {
51 	unsigned char nrdnlen[2];
52 	char nrdn[1];
53 	char rdn[1];                        /* variable placement */
54 	unsigned char entryID[sizeof(ID)];  /* variable placement */
55 	/* unsigned char nsubs[sizeof(ID)];	in child nodes only */
56 } diskNode;
57 
58 /* Sort function for the sorted duplicate data items of a dn2id key.
59  * Sorts based on normalized RDN, in length order.
60  */
61 int
mdb_dup_compare(const MDB_val * usrkey,const MDB_val * curkey)62 mdb_dup_compare(
63 	const MDB_val *usrkey,
64 	const MDB_val *curkey
65 )
66 {
67 	diskNode *un, *cn;
68 	int rc, nrlen;
69 
70 	un = (diskNode *)usrkey->mv_data;
71 	cn = (diskNode *)curkey->mv_data;
72 
73 	/* data is not aligned, cannot compare directly */
74 	rc = un->nrdnlen[0] - cn->nrdnlen[0];
75 	if ( rc ) return rc;
76 	rc = un->nrdnlen[1] - cn->nrdnlen[1];
77 	if ( rc ) return rc;
78 
79 	nrlen = ((un->nrdnlen[0] & 0x7f) << 8) | un->nrdnlen[1];
80 	return strncmp( un->nrdn, cn->nrdn, nrlen );
81 }
82 
83 /* We add two elements to the DN2ID database - a data item under the parent's
84  * entryID containing the child's RDN and entryID, and an item under the
85  * child's entryID containing the parent's entryID.
86  */
87 int
mdb_dn2id_add(Operation * op,MDB_cursor * mcp,MDB_cursor * mcd,ID pid,ID nsubs,int upsub,Entry * e)88 mdb_dn2id_add(
89 	Operation	*op,
90 	MDB_cursor	*mcp,
91 	MDB_cursor	*mcd,
92 	ID pid,
93 	ID nsubs,
94 	int upsub,
95 	Entry		*e )
96 {
97 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
98 	MDB_val		key, data;
99 	ID		nid;
100 	int		rc, rlen, nrlen;
101 	diskNode *d;
102 	char *ptr;
103 
104 	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_add 0x%lx: \"%s\"\n",
105 		e->e_id, e->e_ndn ? e->e_ndn : "" );
106 
107 	nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
108 	if (nrlen) {
109 		rlen = dn_rdnlen( op->o_bd, &e->e_name );
110 	} else {
111 		nrlen = e->e_nname.bv_len;
112 		rlen = e->e_name.bv_len;
113 	}
114 
115 	d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen + sizeof(ID), op->o_tmpmemctx);
116 	d->nrdnlen[1] = nrlen & 0xff;
117 	d->nrdnlen[0] = (nrlen >> 8) | 0x80;
118 	ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
119 	*ptr++ = '\0';
120 	ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
121 	*ptr++ = '\0';
122 	memcpy( ptr, &e->e_id, sizeof( ID ));
123 	ptr += sizeof( ID );
124 	memcpy( ptr, &nsubs, sizeof( ID ));
125 
126 	key.mv_size = sizeof(ID);
127 	key.mv_data = &nid;
128 
129 	nid = pid;
130 
131 	/* Need to make dummy root node once. Subsequent attempts
132 	 * will fail harmlessly.
133 	 */
134 	if ( pid == 0 ) {
135 		diskNode dummy = {{0, 0}, "", "", ""};
136 		data.mv_data = &dummy;
137 		data.mv_size = sizeof(diskNode);
138 
139 		mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
140 	}
141 
142 	data.mv_data = d;
143 	data.mv_size = sizeof(diskNode) + rlen + nrlen + sizeof( ID );
144 
145 	/* Add our child node under parent's key */
146 	rc = mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
147 
148 	/* Add our own node */
149 	if (rc == 0) {
150 		int flag = MDB_NODUPDATA;
151 		nid = e->e_id;
152 		/* drop subtree count */
153 		data.mv_size -= sizeof( ID );
154 		ptr -= sizeof( ID );
155 		memcpy( ptr, &pid, sizeof( ID ));
156 		d->nrdnlen[0] ^= 0x80;
157 
158 		if ((slapMode & SLAP_TOOL_MODE) || (e->e_id == mdb->mi_nextid))
159 			flag |= MDB_APPEND;
160 		rc = mdb_cursor_put( mcd, &key, &data, flag );
161 	}
162 	op->o_tmpfree( d, op->o_tmpmemctx );
163 
164 	/* Add our subtree count to all superiors */
165 	if ( rc == 0 && upsub && pid ) {
166 		ID subs;
167 		nid = pid;
168 		do {
169 			/* Get parent's RDN */
170 			rc = mdb_cursor_get( mcp, &key, &data, MDB_SET );
171 			if ( !rc ) {
172 				char *p2;
173 				ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
174 				memcpy( &nid, ptr, sizeof( ID ));
175 				/* Get parent's node under grandparent */
176 				d = data.mv_data;
177 				rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
178 				p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
179 				memcpy( p2, data.mv_data, rlen+2 );
180 				*p2 ^= 0x80;
181 				data.mv_data = p2;
182 				rc = mdb_cursor_get( mcp, &key, &data, MDB_GET_BOTH );
183 				op->o_tmpfree( p2, op->o_tmpmemctx );
184 				if ( !rc ) {
185 					/* Get parent's subtree count */
186 					ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
187 					memcpy( &subs, ptr, sizeof( ID ));
188 					subs += nsubs;
189 					p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
190 					memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
191 					memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
192 					data.mv_data = p2;
193 					rc = mdb_cursor_put( mcp, &key, &data, MDB_CURRENT );
194 					op->o_tmpfree( p2, op->o_tmpmemctx );
195 				}
196 			}
197 			if ( rc )
198 				break;
199 		} while ( nid );
200 	}
201 
202 	Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_add 0x%lx: %d\n", e->e_id, rc );
203 
204 	return rc;
205 }
206 
207 /* mc must have been set by mdb_dn2id */
208 int
mdb_dn2id_delete(Operation * op,MDB_cursor * mc,ID id,ID nsubs)209 mdb_dn2id_delete(
210 	Operation	*op,
211 	MDB_cursor *mc,
212 	ID id,
213 	ID nsubs )
214 {
215 	ID nid;
216 	char *ptr;
217 	int rc;
218 
219 	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_delete 0x%lx\n",
220 		id );
221 
222 	/* Delete our ID from the parent's list */
223 	rc = mdb_cursor_del( mc, 0 );
224 
225 	/* Delete our ID from the tree. With sorted duplicates, this
226 	 * will leave any child nodes still hanging around. This is OK
227 	 * for modrdn, which will add our info back in later.
228 	 */
229 	if ( rc == 0 ) {
230 		MDB_val	key, data;
231 		if ( nsubs ) {
232 			mdb_cursor_get( mc, &key, NULL, MDB_GET_CURRENT );
233 			memcpy( &nid, key.mv_data, sizeof( ID ));
234 		}
235 		key.mv_size = sizeof(ID);
236 		key.mv_data = &id;
237 		rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
238 		if ( rc == 0 )
239 			rc = mdb_cursor_del( mc, 0 );
240 	}
241 
242 	/* Delete our subtree count from all superiors */
243 	if ( rc == 0 && nsubs && nid ) {
244 		MDB_val key, data;
245 		ID subs;
246 		key.mv_data = &nid;
247 		key.mv_size = sizeof( ID );
248 		do {
249 			rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
250 			if ( !rc ) {
251 				char *p2;
252 				diskNode *d;
253 				int rlen;
254 				ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
255 				memcpy( &nid, ptr, sizeof( ID ));
256 				/* Get parent's node under grandparent */
257 				d = data.mv_data;
258 				rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
259 				p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
260 				memcpy( p2, data.mv_data, rlen+2 );
261 				*p2 ^= 0x80;
262 				data.mv_data = p2;
263 				rc = mdb_cursor_get( mc, &key, &data, MDB_GET_BOTH );
264 				op->o_tmpfree( p2, op->o_tmpmemctx );
265 				if ( !rc ) {
266 					/* Get parent's subtree count */
267 					ptr = (char *)data.mv_data + data.mv_size - sizeof( ID );
268 					memcpy( &subs, ptr, sizeof( ID ));
269 					subs -= nsubs;
270 					p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
271 					memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
272 					memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
273 					data.mv_data = p2;
274 					rc = mdb_cursor_put( mc, &key, &data, MDB_CURRENT );
275 					op->o_tmpfree( p2, op->o_tmpmemctx );
276 				}
277 
278 			}
279 			if ( rc )
280 				break;
281 		} while ( nid );
282 	}
283 
284 	Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_delete 0x%lx: %d\n", id, rc );
285 	return rc;
286 }
287 
288 /* return last found ID in *id if no match
289  * If mc is provided, it will be left pointing to the RDN's
290  * record under the parent's ID. If nsubs is provided, return
291  * the number of entries in this entry's subtree.
292  */
293 int
mdb_dn2id(Operation * op,MDB_txn * txn,MDB_cursor * mc,struct berval * in,ID * id,ID * nsubs,struct berval * matched,struct berval * nmatched)294 mdb_dn2id(
295 	Operation	*op,
296 	MDB_txn *txn,
297 	MDB_cursor	*mc,
298 	struct berval	*in,
299 	ID	*id,
300 	ID	*nsubs,
301 	struct berval	*matched,
302 	struct berval	*nmatched )
303 {
304 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
305 	MDB_cursor *cursor;
306 	MDB_dbi dbi = mdb->mi_dn2id;
307 	MDB_val		key, data;
308 	int		rc = 0, nrlen;
309 	diskNode *d;
310 	char	*ptr;
311 	char dn[SLAP_LDAPDN_MAXLEN];
312 	ID pid, nid;
313 	struct berval tmp;
314 
315 	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id(\"%s\")\n", in->bv_val ? in->bv_val : "" );
316 
317 	if ( matched ) {
318 		matched->bv_val = dn + sizeof(dn) - 1;
319 		matched->bv_len = 0;
320 		*matched->bv_val-- = '\0';
321 	}
322 	if ( nmatched ) {
323 		nmatched->bv_len = 0;
324 		nmatched->bv_val = 0;
325 	}
326 
327 	if ( !in->bv_len ) {
328 		*id = 0;
329 		nid = 0;
330 		goto done;
331 	}
332 
333 	tmp = *in;
334 
335 	if ( op->o_bd->be_nsuffix[0].bv_len ) {
336 		nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
337 		tmp.bv_val += nrlen;
338 		tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
339 	} else {
340 		for ( ptr = tmp.bv_val + tmp.bv_len - 1; ptr >= tmp.bv_val; ptr-- )
341 			if (DN_SEPARATOR(*ptr))
342 				break;
343 		ptr++;
344 		tmp.bv_len -= ptr - tmp.bv_val;
345 		tmp.bv_val = ptr;
346 	}
347 	nid = 0;
348 	key.mv_size = sizeof(ID);
349 
350 	if ( mc ) {
351 		cursor = mc;
352 	} else {
353 		rc = mdb_cursor_open( txn, dbi, &cursor );
354 		if ( rc ) goto done;
355 	}
356 
357 	for (;;) {
358 		key.mv_data = &pid;
359 		pid = nid;
360 
361 		data.mv_size = sizeof(diskNode) + tmp.bv_len;
362 		d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
363 		d->nrdnlen[1] = tmp.bv_len & 0xff;
364 		d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
365 		ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
366 		*ptr = '\0';
367 		data.mv_data = d;
368 		rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
369 		op->o_tmpfree( d, op->o_tmpmemctx );
370 		if ( rc )
371 			break;
372 		ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
373 		memcpy( &nid, ptr, sizeof(ID));
374 
375 		/* grab the non-normalized RDN */
376 		if ( matched ) {
377 			int rlen;
378 			d = data.mv_data;
379 			rlen = data.mv_size - sizeof(diskNode) - tmp.bv_len - sizeof(ID);
380 			matched->bv_len += rlen;
381 			matched->bv_val -= rlen + 1;
382 			ptr = lutil_strcopy( matched->bv_val, d->rdn + tmp.bv_len );
383 			if ( pid ) {
384 				*ptr = ',';
385 				matched->bv_len++;
386 			}
387 		}
388 		if ( nmatched ) {
389 			nmatched->bv_val = tmp.bv_val;
390 		}
391 
392 		if ( tmp.bv_val > in->bv_val ) {
393 			for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
394 				!DN_SEPARATOR(*ptr); ptr--)	/* empty */;
395 			if ( ptr >= in->bv_val ) {
396 				if (DN_SEPARATOR(*ptr)) ptr++;
397 				tmp.bv_len = tmp.bv_val - ptr - 1;
398 				tmp.bv_val = ptr;
399 			}
400 		} else {
401 			break;
402 		}
403 	}
404 	*id = nid;
405 	/* return subtree count if requested */
406 	if ( !rc && nsubs ) {
407 		ptr = (char *)data.mv_data + data.mv_size - sizeof(ID);
408 		memcpy( nsubs, ptr, sizeof( ID ));
409 	}
410 	if ( !mc )
411 		mdb_cursor_close( cursor );
412 done:
413 	if ( matched ) {
414 		if ( matched->bv_len ) {
415 			ptr = op->o_tmpalloc( matched->bv_len+1, op->o_tmpmemctx );
416 			strcpy( ptr, matched->bv_val );
417 			matched->bv_val = ptr;
418 		} else {
419 			if ( BER_BVISEMPTY( &op->o_bd->be_nsuffix[0] ) && !nid ) {
420 				ber_dupbv( matched, (struct berval *)&slap_empty_bv );
421 			} else {
422 				matched->bv_val = NULL;
423 			}
424 		}
425 	}
426 	if ( nmatched ) {
427 		if ( nmatched->bv_val ) {
428 			nmatched->bv_len = in->bv_len - (nmatched->bv_val - in->bv_val);
429 		} else {
430 			*nmatched = slap_empty_bv;
431 		}
432 	}
433 
434 	if( rc != 0 ) {
435 		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: get failed: %s (%d)\n",
436 			mdb_strerror( rc ), rc );
437 	} else {
438 		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n",
439 			nid );
440 	}
441 
442 	return rc;
443 }
444 
445 /* return IDs from root to parent of DN */
446 int
mdb_dn2sups(Operation * op,MDB_txn * txn,struct berval * in,ID * ids)447 mdb_dn2sups(
448 	Operation	*op,
449 	MDB_txn *txn,
450 	struct berval	*in,
451 	ID	*ids )
452 {
453 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
454 	MDB_cursor *cursor;
455 	MDB_dbi dbi = mdb->mi_dn2id;
456 	MDB_val		key, data;
457 	int		rc = 0, nrlen;
458 	diskNode *d;
459 	char	*ptr;
460 	ID pid, nid;
461 	struct berval tmp;
462 
463 	Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2sups(\"%s\")\n", in->bv_val );
464 
465 	if ( !in->bv_len ) {
466 		goto done;
467 	}
468 
469 	tmp = *in;
470 
471 	nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
472 	tmp.bv_val += nrlen;
473 	tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
474 	nid = 0;
475 	key.mv_size = sizeof(ID);
476 
477 	rc = mdb_cursor_open( txn, dbi, &cursor );
478 	if ( rc ) goto done;
479 
480 	for (;;) {
481 		key.mv_data = &pid;
482 		pid = nid;
483 
484 		data.mv_size = sizeof(diskNode) + tmp.bv_len;
485 		d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
486 		d->nrdnlen[1] = tmp.bv_len & 0xff;
487 		d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
488 		ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
489 		*ptr = '\0';
490 		data.mv_data = d;
491 		rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
492 		op->o_tmpfree( d, op->o_tmpmemctx );
493 		if ( rc )
494 			break;
495 		ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
496 		memcpy( &nid, ptr, sizeof(ID));
497 
498 		if ( pid )
499 			mdb_idl_insert( ids, pid );
500 
501 		if ( tmp.bv_val > in->bv_val ) {
502 			for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
503 				!DN_SEPARATOR(*ptr); ptr--)	/* empty */;
504 			if ( ptr >= in->bv_val ) {
505 				if (DN_SEPARATOR(*ptr)) ptr++;
506 				tmp.bv_len = tmp.bv_val - ptr - 1;
507 				tmp.bv_val = ptr;
508 			}
509 		} else {
510 			break;
511 		}
512 	}
513 	mdb_cursor_close( cursor );
514 done:
515 	if( rc != 0 ) {
516 		Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n",
517 			mdb_strerror( rc ), rc );
518 	}
519 
520 	return rc;
521 }
522 
523 int
mdb_dn2id_children(Operation * op,MDB_txn * txn,Entry * e)524 mdb_dn2id_children(
525 	Operation *op,
526 	MDB_txn *txn,
527 	Entry *e )
528 {
529 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
530 	MDB_dbi dbi = mdb->mi_dn2id;
531 	MDB_val		key, data;
532 	MDB_cursor	*cursor;
533 	int		rc;
534 	ID		id;
535 
536 	key.mv_size = sizeof(ID);
537 	key.mv_data = &id;
538 	id = e->e_id;
539 
540 	rc = mdb_cursor_open( txn, dbi, &cursor );
541 	if ( rc ) return rc;
542 
543 	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
544 	if ( rc == 0 ) {
545 		size_t dkids;
546 		rc = mdb_cursor_count( cursor, &dkids );
547 		if ( rc == 0 ) {
548 			if ( dkids < 2 ) rc = MDB_NOTFOUND;
549 		}
550 	}
551 	mdb_cursor_close( cursor );
552 	return rc;
553 }
554 
555 int
mdb_id2name(Operation * op,MDB_txn * txn,MDB_cursor ** cursp,ID id,struct berval * name,struct berval * nname)556 mdb_id2name(
557 	Operation *op,
558 	MDB_txn *txn,
559 	MDB_cursor **cursp,
560 	ID id,
561 	struct berval *name,
562 	struct berval *nname )
563 {
564 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
565 	MDB_dbi dbi = mdb->mi_dn2id;
566 	MDB_val		key, data;
567 	MDB_cursor	*cursor;
568 	int		rc, len, nlen;
569 	char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr;
570 	char *dptr, *nptr;
571 	diskNode *d;
572 
573 	key.mv_size = sizeof(ID);
574 
575 	if ( !*cursp ) {
576 		rc = mdb_cursor_open( txn, dbi, cursp );
577 		if ( rc ) return rc;
578 	}
579 	cursor = *cursp;
580 
581 	len = 0;
582 	nlen = 0;
583 	dptr = dn;
584 	nptr = ndn;
585 	while (id) {
586 		unsigned int nrlen, rlen;
587 		key.mv_data = &id;
588 		data.mv_size = 0;
589 		data.mv_data = "";
590 		rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
591 		if ( rc ) break;
592 		ptr = data.mv_data;
593 		ptr += data.mv_size - sizeof(ID);
594 		memcpy( &id, ptr, sizeof(ID) );
595 		d = data.mv_data;
596 		nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
597 		rlen = data.mv_size - sizeof(diskNode) - nrlen;
598 		assert( nrlen < 1024 && rlen < 1024 );	/* FIXME: Sanity check */
599 		if (nptr > ndn) {
600 			*nptr++ = ',';
601 			*dptr++ = ',';
602 		}
603 		/* copy name and trailing NUL */
604 		memcpy( nptr, d->nrdn, nrlen+1 );
605 		memcpy( dptr, d->nrdn+nrlen+1, rlen+1 );
606 		nptr += nrlen;
607 		dptr += rlen;
608 	}
609 	if ( rc == 0 ) {
610 		name->bv_len = dptr - dn;
611 		nname->bv_len = nptr - ndn;
612 		name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx );
613 		nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx );
614 		memcpy( name->bv_val, dn, name->bv_len );
615 		name->bv_val[name->bv_len] = '\0';
616 		memcpy( nname->bv_val, ndn, nname->bv_len );
617 		nname->bv_val[nname->bv_len] = '\0';
618 	}
619 	return rc;
620 }
621 
622 /* Find each id in ids that is a child of base and move it to res.
623  */
624 int
mdb_idscope(Operation * op,MDB_txn * txn,ID base,ID * ids,ID * res)625 mdb_idscope(
626 	Operation *op,
627 	MDB_txn *txn,
628 	ID base,
629 	ID *ids,
630 	ID *res )
631 {
632 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
633 	MDB_dbi dbi = mdb->mi_dn2id;
634 	MDB_val		key, data;
635 	MDB_cursor	*cursor;
636 	ID ida, id, cid = 0, ci0 = 0, idc = 0;
637 	char	*ptr;
638 	int		rc, copy;
639 
640 	key.mv_size = sizeof(ID);
641 
642 	MDB_IDL_ZERO( res );
643 
644 	rc = mdb_cursor_open( txn, dbi, &cursor );
645 	if ( rc ) return rc;
646 
647 	/* first see if base has any children at all */
648 	key.mv_data = &base;
649 	rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
650 	if ( rc ) {
651 		goto leave;
652 	}
653 	{
654 		size_t dkids;
655 		rc = mdb_cursor_count( cursor, &dkids );
656 		if ( rc == 0 ) {
657 			if ( dkids < 2 ) {
658 				goto leave;
659 			}
660 		}
661 	}
662 
663 	ida = mdb_idl_first( ids, &cid );
664 
665 	/* Don't bother moving out of ids if it's a range */
666 	if (!MDB_IDL_IS_RANGE(ids)) {
667 		idc = ids[0];
668 		ci0 = cid;
669 	}
670 
671 	while (ida != NOID) {
672 		copy = 1;
673 		id = ida;
674 		while (id) {
675 			key.mv_data = &id;
676 			rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
677 			if ( rc ) {
678 				/* not found, drop this from ids */
679 				copy = 0;
680 				break;
681 			}
682 			ptr = data.mv_data;
683 			ptr += data.mv_size - sizeof(ID);
684 			memcpy( &id, ptr, sizeof(ID) );
685 			if ( id == base ) {
686 				if ( res[0] >= MDB_idl_db_max ) {
687 					/* too many aliases in scope. Fallback to range */
688 					MDB_IDL_RANGE( res, MDB_IDL_FIRST( ids ), MDB_IDL_LAST( ids ));
689 					goto leave;
690 				}
691 				res[0]++;
692 				res[res[0]] = ida;
693 				copy = 0;
694 				break;
695 			}
696 			if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
697 				break;
698 		}
699 		if (idc) {
700 			if (copy) {
701 				if (ci0 != cid)
702 					ids[ci0] = ids[cid];
703 				ci0++;
704 			} else
705 				idc--;
706 		}
707 		ida = mdb_idl_next( ids, &cid );
708 	}
709 	if (!MDB_IDL_IS_RANGE( ids ))
710 		ids[0] = idc;
711 
712 leave:
713 	mdb_cursor_close( cursor );
714 	return rc;
715 }
716 
717 /* See if base is a child of any of the scopes
718  */
719 int
mdb_idscopes(Operation * op,IdScopes * isc)720 mdb_idscopes(
721 	Operation *op,
722 	IdScopes *isc )
723 {
724 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
725 	MDB_dbi dbi = mdb->mi_dn2id;
726 	MDB_val		key, data;
727 	ID id, prev;
728 	ID2 id2;
729 	char	*ptr;
730 	int		rc = 0;
731 	unsigned int x;
732 	unsigned int nrlen, rlen;
733 	diskNode *d;
734 
735 	key.mv_size = sizeof(ID);
736 
737 	if ( !isc->mc ) {
738 		rc = mdb_cursor_open( isc->mt, dbi, &isc->mc );
739 		if ( rc ) return rc;
740 	}
741 
742 	id = isc->id;
743 
744 	/* Catch entries from deref'd aliases */
745 	x = mdb_id2l_search( isc->scopes, id );
746 	if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
747 		isc->nscope = x;
748 		return MDB_SUCCESS;
749 	}
750 
751 	isc->sctmp[0].mid = 0;
752 	while (id) {
753 		if ( !rc ) {
754 			key.mv_data = &id;
755 			rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
756 			if ( rc )
757 				return rc;
758 
759 			/* save RDN info */
760 		}
761 		d = data.mv_data;
762 		nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
763 		rlen = data.mv_size - sizeof(diskNode) - nrlen;
764 		isc->nrdns[isc->numrdns].bv_len = nrlen;
765 		isc->nrdns[isc->numrdns].bv_val = d->nrdn;
766 		isc->rdns[isc->numrdns].bv_len = rlen;
767 		isc->rdns[isc->numrdns].bv_val = d->nrdn+nrlen+1;
768 		isc->numrdns++;
769 
770 		if (!rc && id != isc->id) {
771 			/* remember our chain of parents */
772 			id2.mid = id;
773 			id2.mval = data;
774 			mdb_id2l_insert( isc->sctmp, &id2 );
775 		}
776 		ptr = data.mv_data;
777 		ptr += data.mv_size - sizeof(ID);
778 		prev = id;
779 		memcpy( &id, ptr, sizeof(ID) );
780 		/* If we didn't advance, some parent is missing */
781 		if ( id == prev )
782 			return MDB_NOTFOUND;
783 
784 		x = mdb_id2l_search( isc->scopes, id );
785 		if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
786 			if ( !isc->scopes[x].mval.mv_data ) {
787 				/* This node is in scope, add parent chain to scope */
788 				int i;
789 				for ( i = 1; i <= isc->sctmp[0].mid; i++ ) {
790 					rc = mdb_id2l_insert( isc->scopes, &isc->sctmp[i] );
791 					if ( rc )
792 						break;
793 				}
794 				/* check id again since inserts may have changed its position */
795 				if ( isc->scopes[x].mid != id )
796 					x = mdb_id2l_search( isc->scopes, id );
797 				isc->nscope = x;
798 				return MDB_SUCCESS;
799 			}
800 			data = isc->scopes[x].mval;
801 			rc = 1;
802 		}
803 		if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
804 			break;
805 	}
806 	return MDB_SUCCESS;
807 }
808 
809 /* See if ID is a child of any of the scopes,
810  * return MDB_KEYEXIST if so.
811  */
812 int
mdb_idscopechk(Operation * op,IdScopes * isc)813 mdb_idscopechk(
814 	Operation *op,
815 	IdScopes *isc )
816 {
817 	struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
818 	MDB_val		key, data;
819 	ID id, prev;
820 	char	*ptr;
821 	int		rc = 0;
822 	unsigned int x;
823 
824 	key.mv_size = sizeof(ID);
825 
826 	if ( !isc->mc ) {
827 		rc = mdb_cursor_open( isc->mt, mdb->mi_dn2id, &isc->mc );
828 		if ( rc ) return rc;
829 	}
830 
831 	id = isc->id;
832 
833 	while (id) {
834 		if ( !rc ) {
835 			key.mv_data = &id;
836 			rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
837 			if ( rc )
838 				return rc;
839 		}
840 
841 		ptr = data.mv_data;
842 		ptr += data.mv_size - sizeof(ID);
843 		prev = id;
844 		memcpy( &id, ptr, sizeof(ID) );
845 		/* If we didn't advance, some parent is missing */
846 		if ( id == prev )
847 			return MDB_NOTFOUND;
848 
849 		x = mdb_id2l_search( isc->scopes, id );
850 		if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id )
851 			return MDB_KEYEXIST;
852 	}
853 	return MDB_SUCCESS;
854 }
855 
856 int
mdb_dn2id_walk(Operation * op,IdScopes * isc)857 mdb_dn2id_walk(
858 	Operation *op,
859 	IdScopes *isc
860 )
861 {
862 	MDB_val key, data;
863 	diskNode *d;
864 	char *ptr;
865 	int rc, n;
866 	ID nsubs;
867 
868 	if ( !isc->numrdns ) {
869 		key.mv_data = &isc->id;
870 		key.mv_size = sizeof(ID);
871 		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
872 		isc->scopes[0].mid = isc->id;
873 		isc->numrdns++;
874 		isc->nscope = 0;
875 		/* skip base if not a subtree walk */
876 		if ( isc->oscope == LDAP_SCOPE_SUBTREE ||
877 			isc->oscope == LDAP_SCOPE_BASE )
878 			return rc;
879 	}
880 	if ( isc->oscope == LDAP_SCOPE_BASE )
881 		return MDB_NOTFOUND;
882 
883 	for (;;) {
884 		/* Get next sibling */
885 		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_NEXT_DUP );
886 		if ( !rc ) {
887 			ptr = (char *)data.mv_data + data.mv_size - 2*sizeof(ID);
888 			d = data.mv_data;
889 			memcpy( &isc->id, ptr, sizeof(ID));
890 
891 			/* If we're pushing down, see if there's any children to find */
892 			if ( isc->nscope ) {
893 				ptr += sizeof(ID);
894 				memcpy( &nsubs, ptr, sizeof(ID));
895 				/* No children, go to next sibling */
896 				if ( nsubs < 2 )
897 					continue;
898 			}
899 			n = isc->numrdns;
900 			isc->scopes[n].mid = isc->id;
901 			n--;
902 			isc->nrdns[n].bv_len = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1];
903 			isc->nrdns[n].bv_val = d->nrdn;
904 			isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1;
905 			isc->rdns[n].bv_len = data.mv_size - sizeof(diskNode) - isc->nrdns[n].bv_len - sizeof(ID);
906 			/* return this ID to caller */
907 			if ( !isc->nscope )
908 				break;
909 
910 			/* push down to child */
911 			key.mv_data = &isc->id;
912 			mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
913 			isc->nscope = 0;
914 			isc->numrdns++;
915 			continue;
916 
917 		} else if ( rc == MDB_NOTFOUND ) {
918 			if ( !isc->nscope && isc->oscope != LDAP_SCOPE_ONELEVEL ) {
919 				/* reset to first dup */
920 				mdb_cursor_get( isc->mc, &key, NULL, MDB_GET_CURRENT );
921 				mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
922 				isc->nscope = 1;
923 				continue;
924 			} else {
925 				isc->numrdns--;
926 				/* stack is empty? */
927 				if ( !isc->numrdns )
928 					break;
929 				/* pop up to prev node */
930 				n = isc->numrdns - 1;
931 				key.mv_data = &isc->scopes[n].mid;
932 				key.mv_size = sizeof(ID);
933 				data.mv_data = isc->nrdns[n].bv_val - 2;
934 				data.mv_size = 1;	/* just needs to be non-zero, mdb_dup_compare doesn't care */
935 				mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH );
936 				continue;
937 			}
938 		} else {
939 			break;
940 		}
941 	}
942 	return rc;
943 }
944 
945 /* restore the nrdn/rdn pointers after a txn reset */
mdb_dn2id_wrestore(Operation * op,IdScopes * isc)946 void mdb_dn2id_wrestore (
947 	Operation *op,
948 	IdScopes *isc
949 )
950 {
951 	MDB_val key, data;
952 	diskNode *d;
953 	int rc, n, nrlen;
954 	char *ptr;
955 
956 	/* We only need to restore up to the n-1th element,
957 	 * the nth element will be replaced anyway
958 	 */
959 	key.mv_size = sizeof(ID);
960 	for ( n=0; n<isc->numrdns-1; n++ ) {
961 		key.mv_data = &isc->scopes[n+1].mid;
962 		rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
963 		if ( rc )
964 			continue;
965 		/* we can't use this data directly since its nrlen
966 		 * is missing the high bit setting, so copy it and
967 		 * set it properly. we just copy enough to satisfy
968 		 * mdb_dup_compare.
969 		 */
970 		d = data.mv_data;
971 		nrlen = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1];
972 		ptr = op->o_tmpalloc( nrlen+2, op->o_tmpmemctx );
973 		memcpy( ptr, data.mv_data, nrlen+2 );
974 		key.mv_data = &isc->scopes[n].mid;
975 		data.mv_data = ptr;
976 		data.mv_size = 1;
977 		*ptr |= 0x80;
978 		mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH );
979 		op->o_tmpfree( ptr, op->o_tmpmemctx );
980 
981 		/* now we're back to where we wanted to be */
982 		d = data.mv_data;
983 		isc->nrdns[n].bv_val = d->nrdn;
984 		isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1;
985 	}
986 }
987