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