xref: /illumos-gate/usr/src/lib/libnisdb/db_table.cc (revision 8c69cc8fbe729fa7b091e901c4b50508ccc6bb33)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  *	db_table.cc
24  *
25  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
26  * Use is subject to license terms.
27  *
28  * Copyright 2015 RackTop Systems.
29  * Copyright (c) 2016 by Delphix. All rights reserved.
30  */
31 
32 #include <stdio.h>
33 #include <malloc.h>
34 #include <string.h>
35 #include <stdlib.h>		/* srand48() */
36 #include <lber.h>
37 #include <ldap.h>
38 #include "db_headers.h"
39 #include "db_table.h"
40 #include "db_pickle.h"    /* for dump and load */
41 #include "db_entry.h"
42 #include "nisdb_mt.h"
43 
44 #include "ldap_parse.h"
45 #include "ldap_util.h"
46 #include "ldap_map.h"
47 #include "ldap_xdr.h"
48 #include "nis_hashitem.h"
49 #include "nisdb_ldap.h"
50 #include "nis_parse_ldap_conf.h"
51 
52 static time_t	maxTimeT;
53 
54 /*
55  * Find the largest (positive) value of time_t.
56  *
57  * If time_t is unsigned, the largest possible value is just ~0.
58  * However, if it's signed, then ~0 is negative. Since lint (for
59  * sure), and perhaps the compiler too, dislike comparing an
60  * unsigned quantity to see if it's less than zero, we compare
61  * to one instead. If negative, the largest possible value is
62  * th inverse of 2**(N-1), where N is the number of bits in a
63  * time_t.
64  */
65 extern "C" {
66 static void
67 __setMaxTimeT(void)
68 {
69 	unsigned char	b[sizeof (time_t)];
70 	int		i;
71 
72 	/* Compute ~0 for an unknown length integer */
73 	for (i = 0; i < sizeof (time_t); i++) {
74 		b[i] = 0xff;
75 	}
76 	/* Set maxTimeT to ~0 of appropriate length */
77 	(void) memcpy(&maxTimeT, b, sizeof (time_t));
78 
79 	if (maxTimeT < 1)
80 		maxTimeT = ~(1L<<((8*sizeof (maxTimeT))-1));
81 }
82 #pragma init(__setMaxTimeT)
83 }
84 
85 /* How much to grow table by */
86 #define	DB_TABLE_GROWTH_INCREMENT 1024
87 
88 /* 0'th not used; might be confusing. */
89 #define	DB_TABLE_START 1
90 
91 /* prevents wrap around numbers from being passed */
92 #define	CALLOC_LIMIT 536870911
93 
94 /* Initial table sizes to use before using 1K increments. */
95 /* This helps conserve memory usage when there are lots of small tables. */
96 static int tabsizes[] = {
97 	16,
98 	128,
99 	512,
100 	DB_TABLE_GROWTH_INCREMENT,
101 	0
102 	};
103 
104 /* Returns the next size to use for table */
105 static long unsigned
106 get_new_table_size(long unsigned oldsize)
107 {
108 	long unsigned newsize = 0, n;
109 	if (oldsize == 0)
110 		newsize = tabsizes[0];
111 	else {
112 		for (n = 0; newsize = tabsizes[n++]; )
113 			if (oldsize == newsize) {
114 				newsize = tabsizes[n];	/* get next size */
115 				break;
116 			}
117 		if (newsize == 0)
118 			newsize = oldsize + DB_TABLE_GROWTH_INCREMENT;
119 	}
120 	return (newsize);
121 }
122 
123 
124 /* destructor */
125 db_free_list::~db_free_list()
126 {
127 	WRITELOCKV(this, "w db_free_list::~db_free_list");
128 	reset();   /* free list entries */
129 	DESTROYRW(free_list);
130 }
131 
132 void
133 db_free_list::reset()
134 {
135 	db_free_entry *current, *nextentry;
136 
137 	WRITELOCKV(this, "w db_free_list::reset");
138 	for (current = head; current != NULL; ) {
139 		nextentry = current->next;
140 		delete current;
141 		current = nextentry;
142 	}
143 	head = NULL;
144 	count = 0;
145 	WRITEUNLOCKV(this, "wu db_free_list::reset");
146 }
147 
148 /* Returns the location of a free entry, or 0, if there aren't any. */
149 entryp
150 db_free_list::pop()
151 {
152 	WRITELOCK(this, 0, "w db_free_list::pop");
153 	if (head == NULL) {
154 		WRITEUNLOCK(this, 0, "wu db_free_list::pop");
155 		return (0);
156 	}
157 	db_free_entry* old_head = head;
158 	entryp found = head->where;
159 	head = head->next;
160 	delete old_head;
161 	--count;
162 	WRITEUNLOCK(this, found, "wu db_free_list::pop");
163 	return (found);
164 }
165 
166 /*
167  * Adds given location to the free list.
168  * Returns TRUE if successful, FALSE otherwise (when out of memory).
169 */
170 bool_t
171 db_free_list::push(entryp tabloc)
172 {
173 	db_free_entry * newentry = new db_free_entry;
174 
175 	WRITELOCK(this, FALSE, "w db_free_list::push");
176 	if (newentry == NULL) {
177 		WRITEUNLOCK(this, FALSE, "wu db_free_list::push");
178 	    FATAL3("db_free_list::push: cannot allocation space",
179 		    DB_MEMORY_LIMIT, FALSE);
180 	}
181 	newentry->where = tabloc;
182 	newentry->next = head;
183 	head = newentry;
184 	++count;
185 	WRITEUNLOCK(this, TRUE, "wu db_free_list::push");
186 	return (TRUE);
187 }
188 
189 /*
190  * Returns in a vector the information in the free list.
191  * Vector returned is of form: [n free cells][n1][n2][loc1], ..[locn].
192  * Leave the first 'n' cells free.
193  * n1 is the number of entries that should be in the freelist.
194  * n2 is the number of entries actually found in the freelist.
195  * [loc1...locn] are the entries.   n2 <= n1 because we never count beyond n1.
196  * It is up to the caller to free the returned vector when it is through.
197 */
198 long *
199 db_free_list::stats(int nslots)
200 {
201 	long	realcount = 0,
202 		i,
203 		liststart = nslots,		// start of freelist
204 		listend = nslots+count+2;	// end of freelist
205 	db_free_entry_p current = head;
206 
207 	READLOCK(this, NULL, "r db_free_list::stats");
208 
209 	long *answer = (long *)malloc((int)(listend)*sizeof (long));
210 	if (answer == 0) {
211 		READUNLOCK(this, NULL, "ru db_free_list::stats");
212 		FATAL3("db_free_list::stats:  cannot allocation space",
213 		    DB_MEMORY_LIMIT, NULL);
214 	}
215 
216 	answer[liststart] = count;  /* size of freelist */
217 
218 	for (i = liststart+2; i < listend && current != NULL; i++) {
219 		answer[i] = current->where;
220 		current = current->next;
221 		++realcount;
222 	}
223 
224 	answer[liststart+1] = realcount;
225 	READUNLOCK(this, answer, "ru db_free_list::stats");
226 	return (answer);
227 }
228 
229 
230 /* Set default values for the mapping structure */
231 void
232 db_table::initMappingStruct(__nisdb_table_mapping_t *m) {
233 	if (m == 0)
234 		return;
235 
236 	m->initTtlLo = (ldapDBTableMapping.initTtlLo > 0) ?
237 			ldapDBTableMapping.initTtlLo : (3600-1800);
238 	m->initTtlHi = (ldapDBTableMapping.initTtlHi > 0) ?
239 			ldapDBTableMapping.initTtlHi : (3600+1800);
240 	m->ttl = (ldapDBTableMapping.ttl > 0) ?
241 			ldapDBTableMapping.ttl : 3600;
242 	m->enumExpire = 0;
243 	m->fromLDAP = FALSE;
244 	m->toLDAP = FALSE;
245 	m->isMaster = FALSE;
246 	m->retrieveError = ldapDBTableMapping.retrieveError;
247 	m->retrieveErrorRetry.attempts =
248 		ldapDBTableMapping.retrieveErrorRetry.attempts;
249 	m->retrieveErrorRetry.timeout =
250 		ldapDBTableMapping.retrieveErrorRetry.timeout;
251 	m->storeError = ldapDBTableMapping.storeError;
252 	m->storeErrorRetry.attempts =
253 		ldapDBTableMapping.storeErrorRetry.attempts;
254 	m->storeErrorRetry.timeout =
255 		ldapDBTableMapping.storeErrorRetry.timeout;
256 	m->storeErrorDisp = ldapDBTableMapping.storeErrorDisp;
257 	m->refreshError = ldapDBTableMapping.refreshError;
258 	m->refreshErrorRetry.attempts =
259 		ldapDBTableMapping.refreshErrorRetry.attempts;
260 	m->refreshErrorRetry.timeout =
261 		ldapDBTableMapping.refreshErrorRetry.timeout;
262 	m->matchFetch = ldapDBTableMapping.matchFetch;
263 
264 	if (mapping.expire != 0)
265 		free(mapping.expire);
266 	m->expire = 0;
267 
268 	if (m->tm != 0)
269 		free(m->tm);
270 	m->tm = 0;
271 
272 	/*
273 	 * The 'objType' field obviously indicates the type of object.
274 	 * However, we also use it to tell us if we've retrieved mapping
275 	 * data from LDAP or not; in the latter case, 'objType' is
276 	 * NIS_BOGUS_OBJ. For purposes of maintaining expiration times,
277 	 * we may need to know if the object is a table or a directory
278 	 * _before_ we've retrieved any mapping data. Hence the 'expireType'
279 	 * field, which starts as NIS_BOGUS_OBJ (meaning, don't know, assume
280 	 * directory for now), and later is set to NIS_DIRECTORY_OBJ
281 	 * (always keep expiration data, in case one of the dir entries
282 	 * is mapped) or NIS_TABLE_OBJ (only need expiration data if
283 	 * tha table is mapped).
284 	 */
285 	m->objType = NIS_BOGUS_OBJ;
286 	m->expireType = NIS_BOGUS_OBJ;
287 	if (m->objName != 0)
288 		free(m->objName);
289 	m->objName = 0;
290 }
291 
292 void
293 db_table::db_table_ldap_init(void) {
294 
295 	INITRW(table);
296 
297 	enumMode.flag = 0;
298 	enumCount.flag = 0;
299 	enumIndex.ptr = 0;
300 	enumArray.ptr = 0;
301 
302 	mapping.expire = 0;
303 	mapping.tm = 0;
304 	mapping.objName = 0;
305 	mapping.isDeferredTable = FALSE;
306 	(void) mutex_init(&mapping.enumLock, 0, 0);
307 	mapping.enumTid = 0;
308 	mapping.enumStat = -1;
309 	mapping.enumDeferred = 0;
310 	mapping.enumEntries = 0;
311 	mapping.enumTime = 0;
312 }
313 
314 /* db_table constructor */
315 db_table::db_table() : freelist()
316 {
317 	tab = NULL;
318 	table_size = 0;
319 	last_used = 0;
320 	count = 0;
321 
322 	db_table_ldap_init();
323 	initMappingStruct(&mapping);
324 
325 /*  grow(); */
326 }
327 
328 /*
329  * db_table destructor:
330  * 1.  Get rid of contents of freelist
331  * 2.  delete all entries hanging off table
332  * 3.  get rid of table itself
333 */
334 db_table::~db_table()
335 {
336 	WRITELOCKV(this, "w db_table::~db_table");
337 	reset();
338 	DESTROYRW(table);
339 }
340 
341 /* reset size and pointers */
342 void
343 db_table::reset()
344 {
345 	int i, done = 0;
346 
347 	WRITELOCKV(this, "w db_table::reset");
348 	freelist.reset();
349 
350 	/* Add sanity check in case of table corruption */
351 	if (tab != NULL) {
352 		for (i = 0;
353 			i <= last_used && i < table_size && done < count;
354 			i++) {
355 			if (tab[i]) {
356 				free_entry(tab[i]);
357 				++done;
358 			}
359 		}
360 	}
361 
362 	delete tab;
363 	table_size = last_used = count = 0;
364 	tab = NULL;
365 	sfree(mapping.expire);
366 	mapping.expire = NULL;
367 	mapping.objType = NIS_BOGUS_OBJ;
368 	mapping.expireType = NIS_BOGUS_OBJ;
369 	sfree(mapping.objName);
370 	mapping.objName = 0;
371 	/* Leave other values of the mapping structure unchanged */
372 	enumMode.flag = 0;
373 	enumCount.flag = 0;
374 	sfree(enumIndex.ptr);
375 	enumIndex.ptr = 0;
376 	sfree(enumArray.ptr);
377 	enumArray.ptr = 0;
378 	WRITEUNLOCKV(this, "wu db_table::reset");
379 }
380 
381 db_status
382 db_table::allocateExpire(long oldSize, long newSize) {
383 	time_t			*newExpire;
384 
385 	newExpire = (time_t *)realloc(mapping.expire,
386 				newSize * sizeof (mapping.expire[0]));
387 	if (newExpire != NULL) {
388 		/* Initialize new portion */
389 		(void) memset(&newExpire[oldSize], 0,
390 				(newSize-oldSize) * sizeof (newExpire[0]));
391 		mapping.expire = newExpire;
392 	} else {
393 		return (DB_MEMORY_LIMIT);
394 	}
395 
396 	return (DB_SUCCESS);
397 }
398 
399 db_status
400 db_table::allocateEnumArray(long oldSize, long newSize) {
401 	entry_object	**newEnumArray;
402 	const char	*myself = "db_table::allocateEnumArray";
403 
404 	if (enumCount.flag > 0) {
405 		if (enumIndex.ptr == 0) {
406 			enumIndex.ptr = (entryp *)am(myself, enumCount.flag *
407 						sizeof (entryp));
408 			if (enumIndex.ptr == 0)
409 				return (DB_MEMORY_LIMIT);
410 		}
411 		oldSize = 0;
412 		newSize = enumCount.flag;
413 	}
414 	newEnumArray = (entry_object **)realloc(enumArray.ptr,
415 			newSize * sizeof (entry_object *));
416 	if (newEnumArray != 0 && newSize > oldSize) {
417 		(void) memcpy(&newEnumArray[oldSize], &tab[oldSize],
418 			(newSize-oldSize) * sizeof (entry_object *));
419 		enumArray.ptr = newEnumArray;
420 	} else if (newEnumArray == 0) {
421 		return (DB_MEMORY_LIMIT);
422 	}
423 
424 	return (DB_SUCCESS);
425 }
426 
427 /* Expand the table.  Fatal error if insufficient memory. */
428 void
429 db_table::grow()
430 {
431 	WRITELOCKV(this, "w db_table::grow");
432 	long oldsize = table_size;
433 	entry_object_p *oldtab = tab;
434 	long i;
435 
436 	table_size = get_new_table_size(oldsize);
437 
438 #ifdef DEBUG
439 	fprintf(stderr, "db_table GROWING to %d\n", table_size);
440 #endif
441 
442 	if (table_size > CALLOC_LIMIT) {
443 		table_size = oldsize;
444 		WRITEUNLOCKV(this, "wu db_table::grow");
445 		FATAL("db_table::grow: table size exceeds calloc limit",
446 			DB_MEMORY_LIMIT);
447 	}
448 
449 //  if ((tab = new entry_object_p[table_size]) == NULL)
450 	if ((tab = (entry_object_p*)
451 		calloc((unsigned int) table_size,
452 			sizeof (entry_object_p))) == NULL) {
453 		tab = oldtab;		// restore previous table info
454 		table_size = oldsize;
455 		WRITEUNLOCKV(this, "wu db_table::grow");
456 		FATAL("db_table::grow: cannot allocate space", DB_MEMORY_LIMIT);
457 	}
458 
459 	/*
460 	 * For directories, we may need the expire time array even if the
461 	 * directory itself isn't mapped. If the objType and expireType both
462 	 * are bogus, we don't  know yet if this is a table or a directory,
463 	 * and must proceed accordingly.
464 	 */
465 	if (mapping.objType == NIS_DIRECTORY_OBJ ||
466 			mapping.expireType != NIS_TABLE_OBJ ||
467 			mapping.fromLDAP) {
468 		db_status stat = allocateExpire(oldsize, table_size);
469 		if (stat != DB_SUCCESS) {
470 			free(tab);
471 			tab = oldtab;
472 			table_size = oldsize;
473 			WRITEUNLOCKV(this, "wu db_table::grow expire");
474 			FATAL(
475 		"db_table::grow: cannot allocate space for expire", stat);
476 		}
477 	}
478 
479 	if (oldtab != NULL) {
480 		for (i = 0; i < oldsize; i++) { // transfer old to new
481 			tab[i] = oldtab[i];
482 		}
483 		delete oldtab;
484 	}
485 
486 	if (enumMode.flag) {
487 		db_status stat = allocateEnumArray(oldsize, table_size);
488 		if (stat != DB_SUCCESS) {
489 			free(tab);
490 			tab = oldtab;
491 			table_size = oldsize;
492 			WRITEUNLOCKV(this, "wu db_table::grow enumArray");
493 			FATAL(
494 		"db_table::grow: cannot allocate space for enumArray", stat);
495 		}
496 	}
497 
498 	WRITEUNLOCKV(this, "wu db_table::grow");
499 }
500 
501 /*
502  * Return the first entry in table, also return its position in
503  * 'where'.  Return NULL in both if no next entry is found.
504  */
505 entry_object*
506 db_table::first_entry(entryp * where)
507 {
508 	ASSERTRHELD(table);
509 	if (count == 0 || tab == NULL) {  /* empty table */
510 		*where = 0;
511 		return (NULL);
512 	} else {
513 		entryp i;
514 		for (i = DB_TABLE_START;
515 			i < table_size && i <= last_used; i++) {
516 			if (tab[i] != NULL) {
517 				*where = i;
518 				return (tab[i]);
519 			}
520 		}
521 	}
522 	*where = 0;
523 	return (NULL);
524 }
525 
526 /*
527  * Return the next entry in table from 'prev', also return its position in
528  * 'newentry'.  Return NULL in both if no next entry is found.
529  */
530 entry_object *
531 db_table::next_entry(entryp prev, entryp* newentry)
532 {
533 	long i;
534 
535 	ASSERTRHELD(table);
536 	if (prev >= table_size || tab == NULL || tab[prev] == NULL)
537 		return (NULL);
538 	for (i = prev+1; i < table_size && i <= last_used; i++) {
539 		if (tab[i] != NULL) {
540 			*newentry = i;
541 			return (tab[i]);
542 		}
543 	}
544 	*newentry = 0;
545 	return (NULL);
546 }
547 
548 /* Return entry at location 'where', NULL if location is invalid. */
549 entry_object *
550 db_table::get_entry(entryp where)
551 {
552 	ASSERTRHELD(table);
553 	if (where < table_size && tab != NULL && tab[where] != NULL)
554 		return (tab[where]);
555 	else
556 		return (NULL);
557 }
558 
559 void
560 db_table::setEntryExp(entryp where, entry_obj *obj, int initialLoad) {
561 	nis_object		*o;
562 	const char		*myself = "db_table::setEntryExp";
563 
564 	/*
565 	 * If we don't know what type of object this is yet, we
566 	 * can find out now. If it's a directory, the pseudo-object
567 	 * in column zero will have the type "IN_DIRECTORY";
568 	 * otherwise, it's a table object.
569 	 */
570 	if (mapping.expireType == NIS_BOGUS_OBJ) {
571 		if (obj != 0) {
572 			if (obj->en_type != 0 &&
573 				strcmp(obj->en_type, "IN_DIRECTORY") == 0) {
574 				mapping.expireType = NIS_DIRECTORY_OBJ;
575 			} else {
576 				mapping.expireType = NIS_TABLE_OBJ;
577 				if (!mapping.fromLDAP) {
578 					free(mapping.expire);
579 					mapping.expire = 0;
580 				}
581 			}
582 		}
583 	}
584 
585 	/* Set the entry TTL */
586 	if (mapping.expire != NULL) {
587 		struct timeval	now;
588 		time_t		lo, hi, ttl;
589 
590 		(void) gettimeofday(&now, NULL);
591 		if (mapping.expireType == NIS_TABLE_OBJ) {
592 			lo = mapping.initTtlLo;
593 			hi = mapping.initTtlHi;
594 			ttl = mapping.ttl;
595 			/* TTL == 0 means always expired */
596 			if (ttl == 0)
597 				ttl = -1;
598 		} else {
599 			__nis_table_mapping_t	*t = 0;
600 
601 			o = unmakePseudoEntryObj(obj, 0);
602 			if (o != 0) {
603 				__nis_buffer_t	b = {0, 0};
604 
605 				bp2buf(myself, &b, "%s.%s",
606 					o->zo_name, o->zo_domain);
607 				t = getObjMapping(b.buf, 0, 1, 0, 0);
608 				sfree(b.buf);
609 				nis_destroy_object(o);
610 			}
611 
612 			if (t != 0) {
613 				lo = t->initTtlLo;
614 				hi = t->initTtlHi;
615 				ttl = t->ttl;
616 				/* TTL == 0 means always expired */
617 				if (ttl == 0)
618 					ttl = -1;
619 			} else {
620 				/*
621 				 * No expiration time initialization
622 				 * data. Cook up values that will
623 				 * result in mapping.expire[where]
624 				 * set to maxTimeT.
625 				 */
626 				hi = lo = ttl = maxTimeT - now.tv_sec;
627 			}
628 		}
629 
630 		if (initialLoad) {
631 			int	interval = hi - lo + 1;
632 			if (interval <= 1) {
633 				mapping.expire[where] = now.tv_sec + lo;
634 			} else {
635 				srand48(now.tv_sec);
636 				mapping.expire[where] = now.tv_sec +
637 							(lrand48() % interval);
638 			}
639 			if (mapping.enumExpire == 0 ||
640 					mapping.expire[where] <
641 							mapping.enumExpire)
642 				mapping.enumExpire = mapping.expire[where];
643 		} else {
644 			mapping.expire[where] = now.tv_sec + ttl;
645 		}
646 	}
647 }
648 
649 /*
650  * Add given entry to table in first available slot (either look in freelist
651  * or add to end of table) and return the the position of where the record
652  * is placed. 'count' is incremented if entry is added. Table may grow
653  * as a side-effect of the addition. Copy is made of input.
654 */
655 entryp
656 db_table::add_entry(entry_object *obj, int initialLoad) {
657 	/*
658 	 * We're returning an index of the table array, so the caller
659 	 * should hold a lock until done with the index. To save us
660 	 * the bother of upgrading to a write lock, it might as well
661 	 * be a write lock to begin with.
662 	 */
663 	ASSERTWHELD(table);
664 	entryp where = freelist.pop();
665 	if (where == 0) {				/* empty freelist */
666 		if (last_used >= (table_size-1))	/* full (> is for 0) */
667 			grow();
668 		where = ++last_used;
669 	}
670 	if (tab != NULL) {
671 		++count;
672 		setEntryExp(where, obj, initialLoad);
673 
674 		if (enumMode.flag)
675 			enumTouch(where);
676 		tab[where] = new_entry(obj);
677 		return (where);
678 	} else {
679 		return (0);
680 	}
681 }
682 
683 /*
684  * Replaces object at specified location by given entry.
685  * Returns TRUE if replacement successful; FALSE otherwise.
686  * There must something already at the specified location, otherwise,
687  * replacement fails. Copy is not made of the input.
688  * The pre-existing entry is freed.
689  */
690 bool_t
691 db_table::replace_entry(entryp where, entry_object * obj)
692 {
693 	ASSERTWHELD(table);
694 	if (where < DB_TABLE_START || where >= table_size ||
695 	    tab == NULL || tab[where] == NULL)
696 		return (FALSE);
697 	/* (Re-)set the entry TTL */
698 	setEntryExp(where, obj, 0);
699 
700 	if (enumMode.flag)
701 		enumTouch(where);
702 	free_entry(tab[where]);
703 	tab[where] = obj;
704 	return (TRUE);
705 }
706 
707 /*
708  * Deletes entry at specified location.  Returns TRUE if location is valid;
709  * FALSE if location is invalid, or the freed location cannot be added to
710  * the freelist.  'count' is decremented if the deletion occurs.  The object
711  * at that location is freed.
712  */
713 bool_t
714 db_table::delete_entry(entryp where)
715 {
716 	bool_t	ret = TRUE;
717 
718 	ASSERTWHELD(table);
719 	if (where < DB_TABLE_START || where >= table_size ||
720 	    tab == NULL || tab[where] == NULL)
721 		return (FALSE);
722 	if (mapping.expire != NULL) {
723 		mapping.expire[where] = 0;
724 	}
725 	if (enumMode.flag)
726 		enumTouch(where);
727 	free_entry(tab[where]);
728 	tab[where] = NULL;    /* very important to set it to null */
729 	--count;
730 	if (where == last_used) { /* simple case, deleting from end */
731 		--last_used;
732 		return (TRUE);
733 	} else {
734 		return (freelist.push(where));
735 	}
736 	return (ret);
737 }
738 
739 /*
740  * Returns statistics of table.
741  * [vector_size][table_size][last_used][count][freelist].
742  * It is up to the caller to free the returned vector when it is through.
743  * The free list is included if 'fl' is TRUE.
744 */
745 long *
746 db_table::stats(bool_t include_freelist)
747 {
748 	long *answer;
749 
750 	READLOCK(this, NULL, "r db_table::stats");
751 	if (include_freelist)
752 		answer = freelist.stats(3);
753 	else {
754 		answer = (long *)malloc(3*sizeof (long));
755 	}
756 
757 	if (answer) {
758 		answer[0] = table_size;
759 		answer[1] = last_used;
760 		answer[2] = count;
761 	}
762 	READUNLOCK(this, answer, "ru db_table::stats");
763 	return (answer);
764 }
765 
766 bool_t
767 db_table::configure(char *tablePath) {
768 	long		i;
769 	struct timeval	now;
770 	const char	*myself = "db_table::configure";
771 
772 	(void) gettimeofday(&now, NULL);
773 
774 	WRITELOCK(this, FALSE, "db_table::configure w");
775 
776 	/* (Re-)initialize from global info */
777 	initMappingStruct(&mapping);
778 
779 	/* Retrieve table mapping for this table */
780 	mapping.tm = (__nis_table_mapping_t *)__nis_find_item_mt(
781 					tablePath, &ldapMappingList, 0, 0);
782 	if (mapping.tm != 0) {
783 		__nis_object_dn_t	*odn = mapping.tm->objectDN;
784 
785 		/*
786 		 * The mapping.fromLDAP and mapping.toLDAP fields serve as
787 		 * quick-references that tell us if mapping is enabled.
788 		 * Hence, initialize them appropriately from the table
789 		 * mapping objectDN.
790 		 */
791 		while (odn != 0 && (!mapping.fromLDAP || !mapping.toLDAP)) {
792 			if (odn->read.scope != LDAP_SCOPE_UNKNOWN)
793 				mapping.fromLDAP = TRUE;
794 			if (odn->write.scope != LDAP_SCOPE_UNKNOWN)
795 				mapping.toLDAP = TRUE;
796 			odn = (__nis_object_dn_t *)odn->next;
797 		}
798 
799 		/* Set the timeout values */
800 		mapping.initTtlLo = mapping.tm->initTtlLo;
801 		mapping.initTtlHi = mapping.tm->initTtlHi;
802 		mapping.ttl = mapping.tm->ttl;
803 
804 		mapping.objName = sdup(myself, T, mapping.tm->objName);
805 		if (mapping.objName == 0 && mapping.tm->objName != 0) {
806 			WRITEUNLOCK(this, FALSE,
807 				"db_table::configure wu objName");
808 			FATAL3("db_table::configure objName",
809 				DB_MEMORY_LIMIT, FALSE);
810 		}
811 	}
812 
813 	/*
814 	 * In order to initialize the expiration times, we need to know
815 	 * if 'this' represents a table or a directory. To that end, we
816 	 * find an entry in the table, and invoke setEntryExp() on it.
817 	 * As a side effect, setEntryExp() will examine the pseudo-object
818 	 * in the entry, and set the expireType accordingly.
819 	 */
820 	if (tab != 0) {
821 		for (i = 0; i <= last_used; i++) {
822 			if (tab[i] != NULL) {
823 				setEntryExp(i, tab[i], 1);
824 				break;
825 			}
826 		}
827 	}
828 
829 	/*
830 	 * If mapping from an LDAP repository, make sure we have the
831 	 * expiration time array.
832 	 */
833 	if ((mapping.expireType != NIS_TABLE_OBJ || mapping.fromLDAP) &&
834 			mapping.expire == NULL && table_size > 0 && tab != 0) {
835 		db_status stat = allocateExpire(0, table_size);
836 		if (stat != DB_SUCCESS) {
837 			WRITEUNLOCK(this, FALSE,
838 				"db_table::configure wu expire");
839 			FATAL3("db_table::configure expire",
840 				stat, FALSE);
841 		}
842 	} else if (mapping.expireType == NIS_TABLE_OBJ && !mapping.fromLDAP &&
843 			mapping.expire != NULL) {
844 		/* Not using expiration times */
845 		free(mapping.expire);
846 		mapping.expire = NULL;
847 	}
848 
849 	/*
850 	 * Set initial expire times for entries that don't already have one.
851 	 * Establish the enumeration expiration time to be the minimum of
852 	 * all expiration times in the table, though no larger than current
853 	 * time plus initTtlHi.
854 	 */
855 	if (mapping.expire != NULL) {
856 		int	interval = mapping.initTtlHi - mapping.initTtlLo + 1;
857 		time_t	enumXp = now.tv_sec + mapping.initTtlHi;
858 
859 		if (interval > 1)
860 			srand48(now.tv_sec);
861 		for (i = 0; i <= last_used; i++) {
862 			if (tab[i] != NULL && mapping.expire[i] == 0) {
863 				if (mapping.expireType == NIS_TABLE_OBJ) {
864 					if (interval > 1)
865 						mapping.expire[i] =
866 							now.tv_sec +
867 							(lrand48() % interval);
868 					else
869 						mapping.expire[i] =
870 							now.tv_sec +
871 							mapping.initTtlLo;
872 				} else {
873 					setEntryExp(i, tab[i], 1);
874 				}
875 			}
876 			if (enumXp > mapping.expire[i])
877 				enumXp = mapping.expire[i];
878 		}
879 		mapping.enumExpire = enumXp;
880 	}
881 
882 	WRITEUNLOCK(this, FALSE, "db_table::configure wu");
883 
884 	return (TRUE);
885 }
886 
887 /* Return TRUE if the entry at 'loc' hasn't expired */
888 bool_t
889 db_table::cacheValid(entryp loc) {
890 	bool_t		ret;
891 	struct timeval	now;
892 
893 	(void) gettimeofday(&now, 0);
894 
895 	READLOCK(this, FALSE, "db_table::cacheValid r");
896 
897 	if (loc < 0 || loc >= table_size || tab == 0 || tab[loc] == 0)
898 		ret = FALSE;
899 	else if (mapping.expire == 0 || mapping.expire[loc] >= now.tv_sec)
900 		ret = TRUE;
901 	else
902 		ret = FALSE;
903 
904 	READUNLOCK(this, ret, "db_table::cacheValid ru");
905 
906 	return (ret);
907 }
908 
909 /*
910  * If the supplied object has the same content as the one at 'loc',
911  * update the expiration time for the latter, and return TRUE.
912  */
913 bool_t
914 db_table::dupEntry(entry_object *obj, entryp loc) {
915 	if (obj == 0 || loc < 0 || loc >= table_size || tab == 0 ||
916 			tab[loc] == 0)
917 		return (FALSE);
918 
919 	if (sameEntry(obj, tab[loc])) {
920 		setEntryExp(loc, tab[loc], 0);
921 
922 		if (enumMode.flag > 0)
923 			enumTouch(loc);
924 		return (TRUE);
925 	}
926 
927 	return (FALSE);
928 }
929 
930 /*
931  * If enumeration mode is enabled, we keep a shadow array that initially
932  * starts out the same as 'tab'. Any update activity (add, remove, replace,
933  * or update timestamp) for an entry in the table means we delete the shadow
934  * array pointer. When ending enumeration mode, we return the shadow array.
935  * Any non-NULL entries in the array have not been updated since the start
936  * of the enum mode.
937  *
938  * The indended use is for enumeration of an LDAP container, where we
939  * will update all entries that currently exist in LDAP. The entries we
940  * don't update are those that don't exist in LDAP, and thus should be
941  * removed.
942  *
943  * Note that any LDAP query strictly speaking can be a partial enumeration
944  * (i.e., return more than one match). Since the query might also have
945  * matched multiple local DB entries, we need to do the same work as for
946  * enumeration for any query. In order to avoid having to work on the
947  * whole 'tab' array for simple queries (which we expect usually will
948  * match just one or at most a few entries), we have a "reduced" enum mode,
949  * where the caller supplies a count of the number of DB entries (derived
950  * from db_mindex::satisfy_query() or similar), and then uses enumSetup()
951  * to specify which 'tab' entries we're interested in.
952  */
953 void
954 db_table::setEnumMode(long enumNum) {
955 	const char	*myself = "setEnumMode";
956 
957 	enumMode.flag++;
958 	if (enumMode.flag == 1) {
959 		db_status	stat;
960 
961 		if (enumNum < 0)
962 			enumNum = 0;
963 		else if (enumNum >= table_size)
964 			enumNum = table_size;
965 
966 		enumCount.flag = enumNum;
967 
968 		stat = allocateEnumArray(0, table_size);
969 
970 		if (stat != DB_SUCCESS) {
971 			enumMode.flag = 0;
972 			enumCount.flag = 0;
973 			logmsg(MSG_NOTIMECHECK, LOG_ERR,
974 		"%s: No memory for enum check array; entry removal disabled",
975 				myself);
976 		}
977 	}
978 }
979 
980 void
981 db_table::clearEnumMode(void) {
982 	if (enumMode.flag > 0) {
983 		enumMode.flag--;
984 		if (enumMode.flag == 0) {
985 			sfree(enumArray.ptr);
986 			enumArray.ptr = 0;
987 			if (enumCount.flag > 0) {
988 				sfree(enumIndex.ptr);
989 				enumIndex.ptr = 0;
990 				enumCount.flag = 0;
991 			}
992 		}
993 	}
994 }
995 
996 entry_object **
997 db_table::endEnumMode(long *numEa) {
998 	if (enumMode.flag > 0) {
999 		enumMode.flag--;
1000 		if (enumMode.flag == 0) {
1001 			entry_obj	**ea = (entry_object **)enumArray.ptr;
1002 			long		nea;
1003 
1004 			enumArray.ptr = 0;
1005 
1006 			if (enumCount.flag > 0) {
1007 				nea = enumCount.flag;
1008 				enumCount.flag = 0;
1009 				sfree(enumIndex.ptr);
1010 				enumIndex.ptr = 0;
1011 			} else {
1012 				nea = table_size;
1013 			}
1014 
1015 			if (numEa != 0)
1016 				*numEa = nea;
1017 
1018 			return (ea);
1019 		}
1020 	}
1021 
1022 	if (numEa != 0)
1023 		*numEa = 0;
1024 
1025 	return (0);
1026 }
1027 
1028 /*
1029  * Set the appropriate entry in the enum array to NULL.
1030  */
1031 void
1032 db_table::enumTouch(entryp loc) {
1033 	if (loc < 0 || loc >= table_size)
1034 		return;
1035 
1036 	if (enumMode.flag > 0) {
1037 		if (enumCount.flag < 1) {
1038 			((entry_object **)enumArray.ptr)[loc] = 0;
1039 		} else {
1040 			int	i;
1041 
1042 			for (i = 0; i < enumCount.flag; i++) {
1043 				if (loc == ((entryp *)enumIndex.ptr)[i]) {
1044 					((entry_object **)enumArray.ptr)[i] = 0;
1045 					break;
1046 				}
1047 			}
1048 		}
1049 	}
1050 }
1051 
1052 /*
1053  * Add the entry indicated by 'loc' to the enumIndex array, at 'index'.
1054  */
1055 void
1056 db_table::enumSetup(entryp loc, long index) {
1057 	if (enumMode.flag == 0 || loc < 0 || loc >= table_size ||
1058 			index < 0 || index >= enumCount.flag)
1059 		return;
1060 
1061 	((entryp *)enumIndex.ptr)[index] = loc;
1062 	((entry_object **)enumArray.ptr)[index] = tab[loc];
1063 }
1064 
1065 /*
1066  * Touch, i.e., update the expiration time for the entry. Also, if enum
1067  * mode is in effect, mark the entry used for enum purposes.
1068  */
1069 void
1070 db_table::touchEntry(entryp loc) {
1071 	if (loc < 0 || loc >= table_size || tab == 0 || tab[loc] == 0)
1072 		return;
1073 
1074 	setEntryExp(loc, tab[loc], 0);
1075 
1076 	enumTouch(loc);
1077 }
1078 
1079 /* ************************* pickle_table ********************* */
1080 /* Does the actual writing to/from file specific for db_table structure. */
1081 /*
1082  * This was a static earlier with the func name being transfer_aux. The
1083  * backup and restore project needed this to copy files over.
1084  */
1085 bool_t
1086 transfer_aux_table(XDR* x, pptr dp)
1087 {
1088 	return (xdr_db_table(x, (db_table*) dp));
1089 }
1090 
1091 class pickle_table: public pickle_file {
1092     public:
1093 	pickle_table(char *f, pickle_mode m) : pickle_file(f, m) {}
1094 
1095 	/* Transfers db_table structure pointed to by dp to/from file. */
1096 	int transfer(db_table* dp)
1097 	{ return (pickle_file::transfer((pptr) dp, &transfer_aux_table)); }
1098 };
1099 
1100 /*
1101  * Writes the contents of table, including the all the entries, into the
1102  * specified file in XDR format.  May need to change this to use APPEND
1103  * mode instead.
1104  */
1105 int
1106 db_table::dump(char *file)
1107 {
1108 	int	ret;
1109 	READLOCK(this, -1, "r db_table::dump");
1110 	pickle_table f(file, PICKLE_WRITE);   /* may need to use APPEND mode */
1111 	int status = f.transfer(this);
1112 
1113 	if (status == 1)
1114 		ret = -1;
1115 	else
1116 		ret = status;
1117 	READUNLOCK(this, ret, "ru db_table::dump");
1118 }
1119 
1120 /* Constructor that loads in the table from the given file */
1121 db_table::db_table(char *file)  : freelist()
1122 {
1123 	pickle_table f(file, PICKLE_READ);
1124 	tab = NULL;
1125 	table_size = last_used = count = 0;
1126 
1127 	/* load  table */
1128 	if (f.transfer(this) < 0) {
1129 		/* fell through, something went wrong, initialize to null */
1130 		tab = NULL;
1131 		table_size = last_used = count = 0;
1132 		freelist.init();
1133 	}
1134 
1135 	db_table_ldap_init();
1136 	initMappingStruct(&mapping);
1137 }
1138 
1139 /* Returns whether location is valid. */
1140 bool_t db_table::entry_exists_p(entryp i) {
1141 	bool_t	ret = FALSE;
1142 	READLOCK(this, FALSE, "r db_table::entry_exists_p");
1143 	if (tab != NULL && i < table_size)
1144 		ret = tab[i] != NULL;
1145 	READUNLOCK(this, ret, "ru db_table::entry_exists_p");
1146 	return (ret);
1147 }
1148 
1149 /* Empty free list */
1150 void db_free_list::init() {
1151 	WRITELOCKV(this, "w db_free_list::init");
1152 	head = NULL;
1153 	count = 0;
1154 	WRITEUNLOCKV(this, "wu db_free_list::init");
1155 }
1156