1/*	$NetBSD$	*/
2
3/* entry.c - routines for dealing with entries */
4/* OpenLDAP: pkg/ldap/servers/slapd/entry.c,v 1.148.2.14 2010/04/16 15:03:36 quanah Exp */
5/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
6 *
7 * Copyright 1998-2010 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/* Portions Copyright (c) 1995 Regents of the University of Michigan.
19 * All rights reserved.
20 *
21 * Redistribution and use in source and binary forms are permitted
22 * provided that this notice is preserved and that due credit is given
23 * to the University of Michigan at Ann Arbor. The name of the University
24 * may not be used to endorse or promote products derived from this
25 * software without specific prior written permission. This software
26 * is provided ``as is'' without express or implied warranty.
27 */
28
29#include "portable.h"
30
31#include <stdio.h>
32
33#include <ac/ctype.h>
34#include <ac/errno.h>
35#include <ac/socket.h>
36#include <ac/string.h>
37
38#include "slap.h"
39#include "ldif.h"
40
41static char		*ebuf;	/* buf returned by entry2str		 */
42static char		*ecur;	/* pointer to end of currently used ebuf */
43static int		emaxsize;/* max size of ebuf			 */
44
45/*
46 * Empty root entry
47 */
48const Entry slap_entry_root = {
49	NOID, { 0, "" }, { 0, "" }, NULL, 0, { 0, "" }, NULL
50};
51
52/*
53 * these mutexes must be used when calling the entry2str()
54 * routine since it returns a pointer to static data.
55 */
56ldap_pvt_thread_mutex_t	entry2str_mutex;
57
58static const struct berval dn_bv = BER_BVC("dn");
59
60/*
61 * Entry free list
62 *
63 * Allocate in chunks, minimum of 1000 at a time.
64 */
65#define	CHUNK_SIZE	1000
66typedef struct slap_list {
67	struct slap_list *next;
68} slap_list;
69static slap_list *entry_chunks;
70static Entry *entry_list;
71static ldap_pvt_thread_mutex_t entry_mutex;
72
73int entry_destroy(void)
74{
75	slap_list *e;
76	if ( ebuf ) free( ebuf );
77	ebuf = NULL;
78	ecur = NULL;
79	emaxsize = 0;
80
81	for ( e=entry_chunks; e; e=entry_chunks ) {
82		entry_chunks = e->next;
83		free( e );
84	}
85
86	ldap_pvt_thread_mutex_destroy( &entry_mutex );
87	ldap_pvt_thread_mutex_destroy( &entry2str_mutex );
88	return attr_destroy();
89}
90
91int
92entry_init(void)
93{
94	ldap_pvt_thread_mutex_init( &entry2str_mutex );
95	ldap_pvt_thread_mutex_init( &entry_mutex );
96	return attr_init();
97}
98
99Entry *
100str2entry( char *s )
101{
102	return str2entry2( s, 1 );
103}
104
105#define bvcasematch(bv1, bv2)	(ber_bvstrcasecmp(bv1, bv2) == 0)
106
107Entry *
108str2entry2( char *s, int checkvals )
109{
110	int rc;
111	Entry		*e;
112	struct berval	*type, *vals, *nvals;
113	char 	*freeval;
114	AttributeDescription *ad, *ad_prev;
115	const char *text;
116	char	*next;
117	int		attr_cnt;
118	int		i, lines;
119	Attribute	ahead, *atail;
120
121	/*
122	 * LDIF is used as the string format.
123	 * An entry looks like this:
124	 *
125	 *	dn: <dn>\n
126	 *	[<attr>:[:] <value>\n]
127	 *	[<tab><continuedvalue>\n]*
128	 *	...
129	 *
130	 * If a double colon is used after a type, it means the
131	 * following value is encoded as a base 64 string.  This
132	 * happens if the value contains a non-printing character
133	 * or newline.
134	 */
135
136	Debug( LDAP_DEBUG_TRACE, "=> str2entry: \"%s\"\n",
137		s ? s : "NULL", 0, 0 );
138
139	e = entry_alloc();
140
141	if( e == NULL ) {
142		Debug( LDAP_DEBUG_ANY,
143			"<= str2entry NULL (entry allocation failed)\n",
144			0, 0, 0 );
145		return( NULL );
146	}
147
148	/* initialize entry */
149	e->e_id = NOID;
150
151	/* dn + attributes */
152	atail = &ahead;
153	ahead.a_next = NULL;
154	ad = NULL;
155	ad_prev = NULL;
156	attr_cnt = 0;
157	next = s;
158
159	lines = ldif_countlines( s );
160	type = ch_calloc( 1, (lines+1)*3*sizeof(struct berval)+lines );
161	vals = type+lines+1;
162	nvals = vals+lines+1;
163	freeval = (char *)(nvals+lines+1);
164	i = -1;
165
166	/* parse into individual values, record DN */
167	while ( (s = ldif_getline( &next )) != NULL ) {
168		int freev;
169		if ( *s == '\n' || *s == '\0' ) {
170			break;
171		}
172		i++;
173		if (i >= lines) {
174			Debug( LDAP_DEBUG_TRACE,
175				"<= str2entry ran past end of entry\n", 0, 0, 0 );
176			goto fail;
177		}
178
179		rc = ldif_parse_line2( s, type+i, vals+i, &freev );
180		freeval[i] = freev;
181		if ( rc ) {
182			Debug( LDAP_DEBUG_TRACE,
183				"<= str2entry NULL (parse_line)\n", 0, 0, 0 );
184			continue;
185		}
186
187		if ( bvcasematch( &type[i], &dn_bv ) ) {
188			if ( e->e_dn != NULL ) {
189				Debug( LDAP_DEBUG_ANY, "str2entry: "
190					"entry %ld has multiple DNs \"%s\" and \"%s\"\n",
191					(long) e->e_id, e->e_dn, vals[i].bv_val );
192				goto fail;
193			}
194
195			rc = dnPrettyNormal( NULL, &vals[i], &e->e_name, &e->e_nname, NULL );
196			if( rc != LDAP_SUCCESS ) {
197				Debug( LDAP_DEBUG_ANY, "str2entry: "
198					"entry %ld has invalid DN \"%s\"\n",
199					(long) e->e_id, vals[i].bv_val, 0 );
200				goto fail;
201			}
202			if ( freeval[i] ) free( vals[i].bv_val );
203			vals[i].bv_val = NULL;
204			i--;
205			continue;
206		}
207	}
208	lines = i+1;
209
210	/* check to make sure there was a dn: line */
211	if ( BER_BVISNULL( &e->e_name )) {
212		Debug( LDAP_DEBUG_ANY, "str2entry: entry %ld has no dn\n",
213			(long) e->e_id, 0, 0 );
214		goto fail;
215	}
216
217	/* Make sure all attributes with multiple values are contiguous */
218	if ( checkvals ) {
219		int j, k;
220		struct berval bv;
221		int fv;
222
223		for (i=0; i<lines; i++) {
224			for ( j=i+1; j<lines; j++ ) {
225				if ( bvcasematch( type+i, type+j )) {
226					/* out of order, move intervening attributes down */
227					if ( j != i+1 ) {
228						bv = vals[j];
229						fv = freeval[j];
230						for ( k=j; k>i; k-- ) {
231							type[k] = type[k-1];
232							vals[k] = vals[k-1];
233							freeval[k] = freeval[k-1];
234						}
235						k++;
236						type[k] = type[i];
237						vals[k] = bv;
238						freeval[k] = fv;
239					}
240					i++;
241				}
242			}
243		}
244	}
245
246	if ( lines > 0 ) {
247		for ( i=0; i<=lines; i++ ) {
248			ad_prev = ad;
249			if ( !ad || ( i<lines && !bvcasematch( type+i, &ad->ad_cname ))) {
250				ad = NULL;
251				rc = slap_bv2ad( type+i, &ad, &text );
252
253				if( rc != LDAP_SUCCESS ) {
254					Debug( slapMode & SLAP_TOOL_MODE
255						? LDAP_DEBUG_ANY : LDAP_DEBUG_TRACE,
256						"<= str2entry: str2ad(%s): %s\n", type[i].bv_val, text, 0 );
257					if( slapMode & SLAP_TOOL_MODE ) {
258						goto fail;
259					}
260
261					rc = slap_bv2undef_ad( type+i, &ad, &text, 0 );
262					if( rc != LDAP_SUCCESS ) {
263						Debug( LDAP_DEBUG_ANY,
264							"<= str2entry: slap_str2undef_ad(%s): %s\n",
265								type[i].bv_val, text, 0 );
266						goto fail;
267					}
268				}
269
270				/* require ';binary' when appropriate (ITS#5071) */
271				if ( slap_syntax_is_binary( ad->ad_type->sat_syntax ) && !slap_ad_is_binary( ad ) ) {
272					Debug( LDAP_DEBUG_ANY,
273						"str2entry: attributeType %s #%d: "
274						"needs ';binary' transfer as per syntax %s\n",
275						ad->ad_cname.bv_val, 0,
276						ad->ad_type->sat_syntax->ssyn_oid );
277					goto fail;
278				}
279			}
280
281			if (( ad_prev && ad != ad_prev ) || ( i == lines )) {
282				int j, k;
283				/* FIXME: we only need this when migrating from an unsorted DB */
284				if ( atail != &ahead && atail->a_desc->ad_type->sat_flags & SLAP_AT_SORTED_VAL ) {
285					rc = slap_sort_vals( (Modifications *)atail, &text, &j, NULL );
286					if ( rc == LDAP_SUCCESS ) {
287						atail->a_flags |= SLAP_ATTR_SORTED_VALS;
288					} else if ( rc == LDAP_TYPE_OR_VALUE_EXISTS ) {
289						Debug( LDAP_DEBUG_ANY,
290							"str2entry: attributeType %s value #%d provided more than once\n",
291							atail->a_desc->ad_cname.bv_val, j, 0 );
292						goto fail;
293					}
294				}
295				atail->a_next = attr_alloc( NULL );
296				atail = atail->a_next;
297				atail->a_flags = 0;
298				atail->a_numvals = attr_cnt;
299				atail->a_desc = ad_prev;
300				atail->a_vals = ch_malloc( (attr_cnt + 1) * sizeof(struct berval));
301				if( ad_prev->ad_type->sat_equality &&
302					ad_prev->ad_type->sat_equality->smr_normalize )
303					atail->a_nvals = ch_malloc( (attr_cnt + 1) * sizeof(struct berval));
304				else
305					atail->a_nvals = NULL;
306				k = i - attr_cnt;
307				for ( j=0; j<attr_cnt; j++ ) {
308					if ( freeval[k] )
309						atail->a_vals[j] = vals[k];
310					else
311						ber_dupbv( atail->a_vals+j, &vals[k] );
312					vals[k].bv_val = NULL;
313					if ( atail->a_nvals ) {
314						atail->a_nvals[j] = nvals[k];
315						nvals[k].bv_val = NULL;
316					}
317					k++;
318				}
319				BER_BVZERO( &atail->a_vals[j] );
320				if ( atail->a_nvals ) {
321					BER_BVZERO( &atail->a_nvals[j] );
322				} else {
323					atail->a_nvals = atail->a_vals;
324				}
325				attr_cnt = 0;
326				if ( i == lines ) break;
327			}
328
329			if ( BER_BVISNULL( &vals[i] ) ) {
330				Debug( LDAP_DEBUG_ANY,
331					"str2entry: attributeType %s #%d: "
332					"no value\n",
333					ad->ad_cname.bv_val, attr_cnt, 0 );
334				goto fail;
335			}
336
337			if( slapMode & SLAP_TOOL_MODE ) {
338				struct berval pval;
339				slap_syntax_validate_func *validate =
340					ad->ad_type->sat_syntax->ssyn_validate;
341				slap_syntax_transform_func *pretty =
342					ad->ad_type->sat_syntax->ssyn_pretty;
343
344				if ( pretty ) {
345					rc = ordered_value_pretty( ad,
346						&vals[i], &pval, NULL );
347
348				} else if ( validate ) {
349					/*
350				 	 * validate value per syntax
351				 	 */
352					rc = ordered_value_validate( ad, &vals[i], LDAP_MOD_ADD );
353
354				} else {
355					Debug( LDAP_DEBUG_ANY,
356						"str2entry: attributeType %s #%d: "
357						"no validator for syntax %s\n",
358						ad->ad_cname.bv_val, attr_cnt,
359						ad->ad_type->sat_syntax->ssyn_oid );
360					goto fail;
361				}
362
363				if( rc != 0 ) {
364					Debug( LDAP_DEBUG_ANY,
365						"str2entry: invalid value "
366						"for attributeType %s #%d (syntax %s)\n",
367						ad->ad_cname.bv_val, attr_cnt,
368						ad->ad_type->sat_syntax->ssyn_oid );
369					goto fail;
370				}
371
372				if( pretty ) {
373					if ( freeval[i] ) free( vals[i].bv_val );
374					vals[i] = pval;
375					freeval[i] = 1;
376				}
377			}
378
379			if ( ad->ad_type->sat_equality &&
380				ad->ad_type->sat_equality->smr_normalize )
381			{
382				rc = ordered_value_normalize(
383					SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
384					ad,
385					ad->ad_type->sat_equality,
386					&vals[i], &nvals[i], NULL );
387
388				if ( rc ) {
389					Debug( LDAP_DEBUG_ANY,
390				   		"<= str2entry NULL (smr_normalize %s %d)\n", ad->ad_cname.bv_val, rc, 0 );
391					goto fail;
392				}
393			}
394
395			attr_cnt++;
396		}
397	}
398
399	free( type );
400	atail->a_next = NULL;
401	e->e_attrs = ahead.a_next;
402
403	Debug(LDAP_DEBUG_TRACE, "<= str2entry(%s) -> 0x%lx\n",
404		e->e_dn, (unsigned long) e, 0 );
405	return( e );
406
407fail:
408	for ( i=0; i<lines; i++ ) {
409		if ( freeval[i] ) free( vals[i].bv_val );
410		free( nvals[i].bv_val );
411	}
412	free( type );
413	entry_free( e );
414	return NULL;
415}
416
417
418#define GRABSIZE	BUFSIZ
419
420#define MAKE_SPACE( n )	{ \
421		while ( ecur + (n) > ebuf + emaxsize ) { \
422			ptrdiff_t	offset; \
423			offset = (int) (ecur - ebuf); \
424			ebuf = ch_realloc( ebuf, \
425				emaxsize + GRABSIZE ); \
426			emaxsize += GRABSIZE; \
427			ecur = ebuf + offset; \
428		} \
429	}
430
431char *
432entry2str(
433	Entry	*e,
434	int		*len )
435{
436	Attribute	*a;
437	struct berval	*bv;
438	int		i;
439	ber_len_t tmplen;
440
441	assert( e != NULL );
442
443	/*
444	 * In string format, an entry looks like this:
445	 *	dn: <dn>\n
446	 *	[<attr>: <value>\n]*
447	 */
448
449	ecur = ebuf;
450
451	/* put the dn */
452	if ( e->e_dn != NULL ) {
453		/* put "dn: <dn>" */
454		tmplen = e->e_name.bv_len;
455		MAKE_SPACE( LDIF_SIZE_NEEDED( 2, tmplen ));
456		ldif_sput( &ecur, LDIF_PUT_VALUE, "dn", e->e_dn, tmplen );
457	}
458
459	/* put the attributes */
460	for ( a = e->e_attrs; a != NULL; a = a->a_next ) {
461		/* put "<type>:[:] <value>" line for each value */
462		for ( i = 0; a->a_vals[i].bv_val != NULL; i++ ) {
463			bv = &a->a_vals[i];
464			tmplen = a->a_desc->ad_cname.bv_len;
465			MAKE_SPACE( LDIF_SIZE_NEEDED( tmplen, bv->bv_len ));
466			ldif_sput( &ecur, LDIF_PUT_VALUE,
467				a->a_desc->ad_cname.bv_val,
468				bv->bv_val, bv->bv_len );
469		}
470	}
471	MAKE_SPACE( 1 );
472	*ecur = '\0';
473	*len = ecur - ebuf;
474
475	return( ebuf );
476}
477
478void
479entry_clean( Entry *e )
480{
481	/* free an entry structure */
482	assert( e != NULL );
483
484	/* e_private must be freed by the caller */
485	assert( e->e_private == NULL );
486
487	e->e_id = 0;
488
489	/* free DNs */
490	if ( !BER_BVISNULL( &e->e_name ) ) {
491		free( e->e_name.bv_val );
492		BER_BVZERO( &e->e_name );
493	}
494	if ( !BER_BVISNULL( &e->e_nname ) ) {
495		free( e->e_nname.bv_val );
496		BER_BVZERO( &e->e_nname );
497	}
498
499	if ( !BER_BVISNULL( &e->e_bv ) ) {
500		free( e->e_bv.bv_val );
501		BER_BVZERO( &e->e_bv );
502	}
503
504	/* free attributes */
505	if ( e->e_attrs ) {
506		attrs_free( e->e_attrs );
507		e->e_attrs = NULL;
508	}
509
510	e->e_ocflags = 0;
511}
512
513void
514entry_free( Entry *e )
515{
516	entry_clean( e );
517
518	ldap_pvt_thread_mutex_lock( &entry_mutex );
519	e->e_private = entry_list;
520	entry_list = e;
521	ldap_pvt_thread_mutex_unlock( &entry_mutex );
522}
523
524/* These parameters work well on AMD64 */
525#if 0
526#define	STRIDE 8
527#define	STRIPE 5
528#else
529#define	STRIDE 1
530#define	STRIPE 1
531#endif
532#define	STRIDE_FACTOR (STRIDE*STRIPE)
533
534int
535entry_prealloc( int num )
536{
537	Entry *e, **prev, *tmp;
538	slap_list *s;
539	int i, j;
540
541	if (!num) return 0;
542
543#if STRIDE_FACTOR > 1
544	/* Round up to our stride factor */
545	num += STRIDE_FACTOR-1;
546	num /= STRIDE_FACTOR;
547	num *= STRIDE_FACTOR;
548#endif
549
550	s = ch_calloc( 1, sizeof(slap_list) + num * sizeof(Entry));
551	s->next = entry_chunks;
552	entry_chunks = s;
553
554	prev = &tmp;
555	for (i=0; i<STRIPE; i++) {
556		e = (Entry *)(s+1);
557		e += i;
558		for (j=i; j<num; j+= STRIDE) {
559			*prev = e;
560			prev = (Entry **)&e->e_private;
561			e += STRIDE;
562		}
563	}
564	*prev = entry_list;
565	entry_list = (Entry *)(s+1);
566
567	return 0;
568}
569
570Entry *
571entry_alloc( void )
572{
573	Entry *e;
574
575	ldap_pvt_thread_mutex_lock( &entry_mutex );
576	if ( !entry_list )
577		entry_prealloc( CHUNK_SIZE );
578	e = entry_list;
579	entry_list = e->e_private;
580	e->e_private = NULL;
581	ldap_pvt_thread_mutex_unlock( &entry_mutex );
582
583	return e;
584}
585
586
587/*
588 * These routines are used only by Backend.
589 *
590 * the Entry has three entry points (ways to find things):
591 *
592 *	by entry	e.g., if you already have an entry from the cache
593 *			and want to delete it. (really by entry ptr)
594 *	by dn		e.g., when looking for the base object of a search
595 *	by id		e.g., for search candidates
596 *
597 * these correspond to three different avl trees that are maintained.
598 */
599
600int
601entry_cmp( Entry *e1, Entry *e2 )
602{
603	return SLAP_PTRCMP( e1, e2 );
604}
605
606int
607entry_dn_cmp( const void *v_e1, const void *v_e2 )
608{
609	/* compare their normalized UPPERCASED dn's */
610	const Entry *e1 = v_e1, *e2 = v_e2;
611
612	return ber_bvcmp( &e1->e_nname, &e2->e_nname );
613}
614
615int
616entry_id_cmp( const void *v_e1, const void *v_e2 )
617{
618	const Entry *e1 = v_e1, *e2 = v_e2;
619	return( e1->e_id < e2->e_id ? -1 : (e1->e_id > e2->e_id ? 1 : 0) );
620}
621
622/* This is like a ber_len */
623#define entry_lenlen(l)	(((l) < 0x80) ? 1 : ((l) < 0x100) ? 2 : \
624	((l) < 0x10000) ? 3 : ((l) < 0x1000000) ? 4 : 5)
625
626static void
627entry_putlen(unsigned char **buf, ber_len_t len)
628{
629	ber_len_t lenlen = entry_lenlen(len);
630
631	if (lenlen == 1) {
632		**buf = (unsigned char) len;
633	} else {
634		int i;
635		**buf = 0x80 | ((unsigned char) lenlen - 1);
636		for (i=lenlen-1; i>0; i--) {
637			(*buf)[i] = (unsigned char) len;
638			len >>= 8;
639		}
640	}
641	*buf += lenlen;
642}
643
644static ber_len_t
645entry_getlen(unsigned char **buf)
646{
647	ber_len_t len;
648	int i;
649
650	len = *(*buf)++;
651	if (len <= 0x7f)
652		return len;
653	i = len & 0x7f;
654	len = 0;
655	for (;i > 0; i--) {
656		len <<= 8;
657		len |= *(*buf)++;
658	}
659	return len;
660}
661
662/* Count up the sizes of the components of an entry */
663void entry_partsize(Entry *e, ber_len_t *plen,
664	int *pnattrs, int *pnvals, int norm)
665{
666	ber_len_t len, dnlen, ndnlen;
667	int i, nat = 0, nval = 0;
668	Attribute *a;
669
670	dnlen = e->e_name.bv_len;
671	len = dnlen + 1;	/* trailing NUL byte */
672	len += entry_lenlen(dnlen);
673	if (norm) {
674		ndnlen = e->e_nname.bv_len;
675		len += ndnlen + 1;
676		len += entry_lenlen(ndnlen);
677	}
678	for (a=e->e_attrs; a; a=a->a_next) {
679		/* For AttributeDesc, we only store the attr name */
680		nat++;
681		len += a->a_desc->ad_cname.bv_len+1;
682		len += entry_lenlen(a->a_desc->ad_cname.bv_len);
683		for (i=0; a->a_vals[i].bv_val; i++) {
684			nval++;
685			len += a->a_vals[i].bv_len + 1;
686			len += entry_lenlen(a->a_vals[i].bv_len);
687		}
688		len += entry_lenlen(i);
689		nval++;	/* empty berval at end */
690		if (norm && a->a_nvals != a->a_vals) {
691			for (i=0; a->a_nvals[i].bv_val; i++) {
692				nval++;
693				len += a->a_nvals[i].bv_len + 1;
694				len += entry_lenlen(a->a_nvals[i].bv_len);
695			}
696			len += entry_lenlen(i);	/* i nvals */
697			nval++;
698		} else {
699			len += entry_lenlen(0);	/* 0 nvals */
700		}
701	}
702	len += entry_lenlen(nat);
703	len += entry_lenlen(nval);
704	*plen = len;
705	*pnattrs = nat;
706	*pnvals = nval;
707}
708
709/* Add up the size of the entry for a flattened buffer */
710ber_len_t entry_flatsize(Entry *e, int norm)
711{
712	ber_len_t len;
713	int nattrs, nvals;
714
715	entry_partsize(e, &len, &nattrs, &nvals, norm);
716	len += sizeof(Entry) + (nattrs * sizeof(Attribute)) +
717		(nvals * sizeof(struct berval));
718	return len;
719}
720
721/* Flatten an Entry into a buffer. The buffer is filled with just the
722 * strings/bervals of all the entry components. Each field is preceded
723 * by its length, encoded the way ber_put_len works. Every field is NUL
724 * terminated.  The entire buffer size is precomputed so that a single
725 * malloc can be performed. The entry size is also recorded,
726 * to aid in entry_decode.
727 */
728int entry_encode(Entry *e, struct berval *bv)
729{
730	ber_len_t len, dnlen, ndnlen, i;
731	int nattrs, nvals;
732	Attribute *a;
733	unsigned char *ptr;
734
735	Debug( LDAP_DEBUG_TRACE, "=> entry_encode(0x%08lx): %s\n",
736		(long) e->e_id, e->e_dn, 0 );
737
738	dnlen = e->e_name.bv_len;
739	ndnlen = e->e_nname.bv_len;
740
741	entry_partsize( e, &len, &nattrs, &nvals, 1 );
742
743	bv->bv_len = len;
744	bv->bv_val = ch_malloc(len);
745	ptr = (unsigned char *)bv->bv_val;
746	entry_putlen(&ptr, nattrs);
747	entry_putlen(&ptr, nvals);
748	entry_putlen(&ptr, dnlen);
749	AC_MEMCPY(ptr, e->e_dn, dnlen);
750	ptr += dnlen;
751	*ptr++ = '\0';
752	entry_putlen(&ptr, ndnlen);
753	AC_MEMCPY(ptr, e->e_ndn, ndnlen);
754	ptr += ndnlen;
755	*ptr++ = '\0';
756
757	for (a=e->e_attrs; a; a=a->a_next) {
758		entry_putlen(&ptr, a->a_desc->ad_cname.bv_len);
759		AC_MEMCPY(ptr, a->a_desc->ad_cname.bv_val,
760			a->a_desc->ad_cname.bv_len);
761		ptr += a->a_desc->ad_cname.bv_len;
762		*ptr++ = '\0';
763		if (a->a_vals) {
764			for (i=0; a->a_vals[i].bv_val; i++);
765			assert( i == a->a_numvals );
766			entry_putlen(&ptr, i);
767			for (i=0; a->a_vals[i].bv_val; i++) {
768				entry_putlen(&ptr, a->a_vals[i].bv_len);
769				AC_MEMCPY(ptr, a->a_vals[i].bv_val,
770					a->a_vals[i].bv_len);
771				ptr += a->a_vals[i].bv_len;
772				*ptr++ = '\0';
773			}
774			if (a->a_nvals != a->a_vals) {
775				entry_putlen(&ptr, i);
776				for (i=0; a->a_nvals[i].bv_val; i++) {
777					entry_putlen(&ptr, a->a_nvals[i].bv_len);
778					AC_MEMCPY(ptr, a->a_nvals[i].bv_val,
779					a->a_nvals[i].bv_len);
780					ptr += a->a_nvals[i].bv_len;
781					*ptr++ = '\0';
782				}
783			} else {
784				entry_putlen(&ptr, 0);
785			}
786		}
787	}
788
789	Debug( LDAP_DEBUG_TRACE, "<= entry_encode(0x%08lx): %s\n",
790		(long) e->e_id, e->e_dn, 0 );
791
792	return 0;
793}
794
795/* Retrieve an Entry that was stored using entry_encode above.
796 * First entry_header must be called to decode the size of the entry.
797 * Then a single block of memory must be malloc'd to accomodate the
798 * bervals and the bulk data. Next the bulk data is retrieved from
799 * the DB and parsed by entry_decode.
800 *
801 * Note: everything is stored in a single contiguous block, so
802 * you can not free individual attributes or names from this
803 * structure. Attempting to do so will likely corrupt memory.
804 */
805int entry_header(EntryHeader *eh)
806{
807	unsigned char *ptr = (unsigned char *)eh->bv.bv_val;
808
809	eh->nattrs = entry_getlen(&ptr);
810	if ( !eh->nattrs ) {
811		Debug( LDAP_DEBUG_ANY,
812			"entry_header: attribute count was zero\n", 0, 0, 0);
813		return LDAP_OTHER;
814	}
815	eh->nvals = entry_getlen(&ptr);
816	if ( !eh->nvals ) {
817		Debug( LDAP_DEBUG_ANY,
818			"entry_header: value count was zero\n", 0, 0, 0);
819		return LDAP_OTHER;
820	}
821	eh->data = (char *)ptr;
822	return LDAP_SUCCESS;
823}
824
825int
826entry_decode_dn( EntryHeader *eh, struct berval *dn, struct berval *ndn )
827{
828	int i;
829	unsigned char *ptr = (unsigned char *)eh->bv.bv_val;
830
831	assert( dn != NULL || ndn != NULL );
832
833	ptr = (unsigned char *)eh->data;
834	i = entry_getlen(&ptr);
835	if ( dn != NULL ) {
836		dn->bv_val = (char *) ptr;
837		dn->bv_len = i;
838	}
839
840	if ( ndn != NULL ) {
841		ptr += i + 1;
842		i = entry_getlen(&ptr);
843		ndn->bv_val = (char *) ptr;
844		ndn->bv_len = i;
845	}
846
847	Debug( LDAP_DEBUG_TRACE,
848		"entry_decode_dn: \"%s\"\n",
849		dn ? dn->bv_val : ndn->bv_val, 0, 0 );
850
851	return 0;
852}
853
854#ifdef SLAP_ZONE_ALLOC
855int entry_decode(EntryHeader *eh, Entry **e, void *ctx)
856#else
857int entry_decode(EntryHeader *eh, Entry **e)
858#endif
859{
860	int i, j, nattrs, nvals;
861	int rc;
862	Attribute *a;
863	Entry *x;
864	const char *text;
865	AttributeDescription *ad;
866	unsigned char *ptr = (unsigned char *)eh->bv.bv_val;
867	BerVarray bptr;
868
869	nattrs = eh->nattrs;
870	nvals = eh->nvals;
871	x = entry_alloc();
872	x->e_attrs = attrs_alloc( nattrs );
873	ptr = (unsigned char *)eh->data;
874	i = entry_getlen(&ptr);
875	x->e_name.bv_val = (char *) ptr;
876	x->e_name.bv_len = i;
877	ptr += i+1;
878	i = entry_getlen(&ptr);
879	x->e_nname.bv_val = (char *) ptr;
880	x->e_nname.bv_len = i;
881	ptr += i+1;
882	Debug( LDAP_DEBUG_TRACE,
883		"entry_decode: \"%s\"\n",
884		x->e_dn, 0, 0 );
885	x->e_bv = eh->bv;
886
887	a = x->e_attrs;
888	bptr = (BerVarray)eh->bv.bv_val;
889
890	while ((i = entry_getlen(&ptr))) {
891		struct berval bv;
892		bv.bv_len = i;
893		bv.bv_val = (char *) ptr;
894		ad = NULL;
895		rc = slap_bv2ad( &bv, &ad, &text );
896
897		if( rc != LDAP_SUCCESS ) {
898			Debug( LDAP_DEBUG_TRACE,
899				"<= entry_decode: str2ad(%s): %s\n", ptr, text, 0 );
900			rc = slap_bv2undef_ad( &bv, &ad, &text, 0 );
901
902			if( rc != LDAP_SUCCESS ) {
903				Debug( LDAP_DEBUG_ANY,
904					"<= entry_decode: slap_str2undef_ad(%s): %s\n",
905						ptr, text, 0 );
906				return rc;
907			}
908		}
909		ptr += i + 1;
910		a->a_desc = ad;
911		a->a_flags = SLAP_ATTR_DONT_FREE_DATA | SLAP_ATTR_DONT_FREE_VALS;
912		j = entry_getlen(&ptr);
913		a->a_numvals = j;
914		a->a_vals = bptr;
915
916		while (j) {
917			i = entry_getlen(&ptr);
918			bptr->bv_len = i;
919			bptr->bv_val = (char *)ptr;
920			ptr += i+1;
921			bptr++;
922			j--;
923		}
924		bptr->bv_val = NULL;
925		bptr->bv_len = 0;
926		bptr++;
927
928		j = entry_getlen(&ptr);
929		if (j) {
930			a->a_nvals = bptr;
931			while (j) {
932				i = entry_getlen(&ptr);
933				bptr->bv_len = i;
934				bptr->bv_val = (char *)ptr;
935				ptr += i+1;
936				bptr++;
937				j--;
938			}
939			bptr->bv_val = NULL;
940			bptr->bv_len = 0;
941			bptr++;
942		} else {
943			a->a_nvals = a->a_vals;
944		}
945		/* FIXME: This is redundant once a sorted entry is saved into the DB */
946		if ( a->a_desc->ad_type->sat_flags & SLAP_AT_SORTED_VAL ) {
947			rc = slap_sort_vals( (Modifications *)a, &text, &j, NULL );
948			if ( rc == LDAP_SUCCESS ) {
949				a->a_flags |= SLAP_ATTR_SORTED_VALS;
950			} else if ( rc == LDAP_TYPE_OR_VALUE_EXISTS ) {
951				/* should never happen */
952				Debug( LDAP_DEBUG_ANY,
953					"entry_decode: attributeType %s value #%d provided more than once\n",
954					a->a_desc->ad_cname.bv_val, j, 0 );
955				return rc;
956			}
957		}
958		a = a->a_next;
959		nattrs--;
960		if ( !nattrs )
961			break;
962	}
963
964	Debug(LDAP_DEBUG_TRACE, "<= entry_decode(%s)\n",
965		x->e_dn, 0, 0 );
966	*e = x;
967	return 0;
968}
969
970Entry *
971entry_dup2( Entry *dest, Entry *source )
972{
973	assert( dest != NULL );
974	assert( source != NULL );
975
976	assert( dest->e_private == NULL );
977
978	dest->e_id = source->e_id;
979	ber_dupbv( &dest->e_name, &source->e_name );
980	ber_dupbv( &dest->e_nname, &source->e_nname );
981	dest->e_attrs = attrs_dup( source->e_attrs );
982	dest->e_ocflags = source->e_ocflags;
983
984	return dest;
985}
986
987Entry *
988entry_dup( Entry *e )
989{
990	return entry_dup2( entry_alloc(), e );
991}
992
993#if 1
994/* Duplicates an entry using a single malloc. Saves CPU time, increases
995 * heap usage because a single large malloc is harder to satisfy than
996 * lots of small ones, and the freed space isn't as easily reusable.
997 *
998 * Probably not worth using this function.
999 */
1000Entry *entry_dup_bv( Entry *e )
1001{
1002	ber_len_t len;
1003	int nattrs, nvals;
1004	Entry *ret;
1005	struct berval *bvl;
1006	char *ptr;
1007	Attribute *src, *dst;
1008
1009	ret = entry_alloc();
1010
1011	entry_partsize(e, &len, &nattrs, &nvals, 1);
1012	ret->e_id = e->e_id;
1013	ret->e_attrs = attrs_alloc( nattrs );
1014	ret->e_ocflags = e->e_ocflags;
1015	ret->e_bv.bv_len = len + nvals * sizeof(struct berval);
1016	ret->e_bv.bv_val = ch_malloc( ret->e_bv.bv_len );
1017
1018	bvl = (struct berval *)ret->e_bv.bv_val;
1019	ptr = (char *)(bvl + nvals);
1020
1021	ret->e_name.bv_len = e->e_name.bv_len;
1022	ret->e_name.bv_val = ptr;
1023	AC_MEMCPY( ptr, e->e_name.bv_val, e->e_name.bv_len );
1024	ptr += e->e_name.bv_len;
1025	*ptr++ = '\0';
1026
1027	ret->e_nname.bv_len = e->e_nname.bv_len;
1028	ret->e_nname.bv_val = ptr;
1029	AC_MEMCPY( ptr, e->e_nname.bv_val, e->e_nname.bv_len );
1030	ptr += e->e_name.bv_len;
1031	*ptr++ = '\0';
1032
1033	dst = ret->e_attrs;
1034	for (src = e->e_attrs; src; src=src->a_next,dst=dst->a_next ) {
1035		int i;
1036		dst->a_desc = src->a_desc;
1037		dst->a_flags = SLAP_ATTR_DONT_FREE_DATA | SLAP_ATTR_DONT_FREE_VALS;
1038		dst->a_vals = bvl;
1039		dst->a_numvals = src->a_numvals;
1040		for ( i=0; src->a_vals[i].bv_val; i++ ) {
1041			bvl->bv_len = src->a_vals[i].bv_len;
1042			bvl->bv_val = ptr;
1043			AC_MEMCPY( ptr, src->a_vals[i].bv_val, bvl->bv_len );
1044			ptr += bvl->bv_len;
1045			*ptr++ = '\0';
1046			bvl++;
1047		}
1048		BER_BVZERO(bvl);
1049		bvl++;
1050		if ( src->a_vals != src->a_nvals ) {
1051			dst->a_nvals = bvl;
1052			for ( i=0; src->a_nvals[i].bv_val; i++ ) {
1053				bvl->bv_len = src->a_nvals[i].bv_len;
1054				bvl->bv_val = ptr;
1055				AC_MEMCPY( ptr, src->a_nvals[i].bv_val, bvl->bv_len );
1056				ptr += bvl->bv_len;
1057				*ptr++ = '\0';
1058				bvl++;
1059			}
1060			BER_BVZERO(bvl);
1061			bvl++;
1062		}
1063	}
1064	return ret;
1065}
1066#endif
1067