xref: /titanic_51/usr/src/cmd/nscd/nscd_dbimpl.c (revision b819cea2f73f98c5662230cc9affc8cc84f77fcf)
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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #pragma ident	"%Z%%M%	%I%	%E% SMI"
27 
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 #include <ctype.h>
32 #include "nscd_db.h"
33 
34 /*
35  * This file implements the database functionality used by the
36  * switch and configuration components. The implementation is
37  * based on hash and has table. If the need arises in the future,
38  * the code in this file can be changed to use other algorithms.
39  * The following lists the functions implemented:
40  *
41  * _nscd_add_db_entry
42  * _nscd_delete_db_entry
43  * _nscd_get_db_entry
44  * _nscd_alloc_db
45  * _nscd_free_db
46  * _nscd_walk_db
47  * _nscd_delete_db_entry_cookie
48  */
49 
50 /*
51  * This structure defines an instance of the hash entry
52  * which implements the nscd database entry. The
53  * db_entry field should always be the first one in
54  * the structure.
55  */
56 typedef struct nscd_hash {
57 	nscd_db_entry_t		db_entry;
58 	struct nscd_hash	*next_p;
59 	struct nscd_hash	*prev_p;
60 } nscd_hash_t;
61 
62 /*
63  * This structure defines a nscd database which
64  * is implemented as an array of nscd_hash_t.
65  */
66 struct nscd_db_s {
67 	int		array_size; /* number of elements in hash_tbl_p */
68 	nscd_hash_t	**hash_tbl_p;
69 };
70 
71 /*
72  * This cookie structure is used to iterate through the
73  * database entries contained in a nscd database.
74  */
75 struct cookie {
76 	int		idx;	/* the current bucket */
77 	nscd_hash_t	*hash;	/* the current hash entry */
78 	nscd_db_t	*db;    /* the database */
79 };
80 
81 /*
82  * FUNCTION: calc_hash
83  *
84  * Calculate a hash for a string based on the elf_hash
85  * algorithm, hash is case insensitive. Uses tolower
86  * instead of _tolower because of I18N.
87  */
88 static unsigned long
89 calc_hash(
90 	const char	*str)
91 {
92 	unsigned int	hval = 0;
93 	char		ch;
94 
95 	while (*str != NULL) {
96 		unsigned int	g;
97 
98 		ch = (char)*str++;
99 		if (isupper(ch))
100 			ch = _tolower(ch);
101 		hval = (hval << 4) + ch;
102 		if ((g = (hval & 0xf0000000)) != 0)
103 			hval ^= g >> 24;
104 		hval &= ~g;
105 	}
106 	return ((unsigned long)hval);
107 }
108 
109 /*
110  * FUNCTION: scan_hash
111  *
112  * Scan a hash table for a matching hash entry. Assume 'str' is
113  * not NULL. If option is NSCD_GET_NEXT_DB_ENTRY and id_num
114  * is less than zero, then treats the option as NSCD_GET_FIRST_DB_ENTRY.
115  */
116 
117 static const nscd_hash_t *
118 scan_hash(
119 	int			type,
120 	const char		*str,
121 	const nscd_hash_t	*idx_p,
122 	nscd_db_option_t	option,
123 	int			id_num)
124 {
125 	int			id_matched = 0;
126 	nscd_db_entry_t		*db_entry;
127 
128 	while (idx_p != NULL) {
129 		db_entry = &((nscd_hash_t *)idx_p)->db_entry;
130 		if (db_entry->type == type) {
131 			if (strcasecmp(str, db_entry->name) == 0) {
132 				switch (option) {
133 				case NSCD_GET_FIRST_DB_ENTRY:
134 					return (idx_p);
135 				case NSCD_GET_EXACT_DB_ENTRY:
136 					if (id_num == db_entry->id_num)
137 						return (idx_p);
138 					break;
139 				case NSCD_GET_NEXT_DB_ENTRY:
140 					if (id_num < 0)
141 						return (idx_p);
142 					if (id_matched == 1)
143 						return (idx_p);
144 					if (id_num == db_entry->id_num)
145 						id_matched = 1;
146 					break;
147 				}
148 			}
149 		}
150 		idx_p = idx_p->next_p;
151 	}
152 	return (NULL);
153 }
154 
155 /*
156  * FUNCTION: _nscd_get_db_entry
157  *
158  * Find a nscd database entry from a nscd database.
159  */
160 const nscd_db_entry_t *
161 _nscd_get_db_entry(
162 	const nscd_db_t		*db,
163 	int			type,
164 	const char		*str,
165 	nscd_db_option_t	option,
166 	int			id_num)
167 {
168 	unsigned long		hash;
169 	const nscd_hash_t	*idx_p, *hash_p;
170 
171 	if (db == NULL || str == NULL)
172 		return (NULL);
173 
174 	hash = calc_hash(str);
175 	idx_p = db->hash_tbl_p[hash % db->array_size];
176 
177 	hash_p = scan_hash(type, str, idx_p, option, id_num);
178 
179 	return (&hash_p->db_entry);
180 }
181 
182 /*
183  * FUNCTION: _nscd_add_db_entry
184  *
185  * Add a nscd database entry to a nscd database. This function
186  * is not MT safe. The caller should lock the database to
187  * prevent concurrent updates done by other threads.
188  */
189 nscd_rc_t
190 _nscd_add_db_entry(
191 	nscd_db_t		*db,
192 	const char 		*str,
193 	nscd_db_entry_t		*entry,
194 	nscd_db_option_t	option)
195 {
196 	int			i;
197 	unsigned long		hash;
198 	nscd_hash_t		*next_p = NULL, *prev_p = NULL;
199 	nscd_hash_t		*idx_p, *hash_entry;
200 	nscd_db_entry_t		*db_entry;
201 
202 	/* find the bucket */
203 	hash = calc_hash(str);
204 	i = hash % db->array_size;
205 	idx_p = db->hash_tbl_p[i];
206 
207 	/* can not replace nothing */
208 	if (idx_p == NULL)
209 		if (option == NSCD_ADD_DB_ENTRY_REPLACE)
210 			return (NSCD_DB_ENTRY_NOT_FOUND);
211 
212 	while (idx_p != NULL) {
213 		db_entry = &idx_p->db_entry;
214 		switch (option) {
215 
216 		case NSCD_ADD_DB_ENTRY_FIRST:
217 			next_p = idx_p;
218 			goto add_entry;
219 
220 		case NSCD_ADD_DB_ENTRY_REPLACE:
221 			if (db_entry->type != entry->type)
222 				goto cont;
223 			if (strcasecmp(db_entry->name, str) != 0)
224 				goto cont;
225 
226 			if (db_entry->id_num == entry->id_num) {
227 				prev_p = idx_p->prev_p;
228 				next_p = idx_p->next_p;
229 				free(idx_p);
230 				goto add_entry;
231 			}
232 			goto cont;
233 
234 		case NSCD_ADD_DB_ENTRY_IF_NONE:
235 			if (db_entry->type != entry->type)
236 				break;
237 			if (strcasecmp(db_entry->name, str) != 0)
238 				break;
239 			return (NSCD_DB_ENTRY_FOUND);
240 		}
241 
242 		if (idx_p->next_p == NULL) {
243 			if (option == NSCD_ADD_DB_ENTRY_LAST ||
244 				option == NSCD_ADD_DB_ENTRY_IF_NONE) {
245 				prev_p = idx_p;
246 				goto add_entry;
247 			}
248 		}
249 
250 		cont:
251 		idx_p = idx_p->next_p;
252 	}
253 
254 	add_entry:
255 
256 	/*
257 	 * the nscd_entry_t field should be the first field
258 	 * in a nscd_hash_t
259 	 */
260 	hash_entry = (nscd_hash_t *)entry;
261 
262 	/* update the prev link list */
263 	hash_entry->prev_p = prev_p;
264 	if (prev_p == NULL)
265 		db->hash_tbl_p[i] = hash_entry;
266 	else
267 		prev_p->next_p = hash_entry;
268 
269 	/* update the next link list */
270 	hash_entry->next_p = next_p;
271 	if (next_p != NULL)
272 		next_p->prev_p = hash_entry;
273 
274 	return (NSCD_SUCCESS);
275 }
276 
277 /*
278  * FUNCTION: _nscd_delete_db_entry
279  *
280  * Delete a nscd database entry from a nscd database. This
281  * function is not MT safe. The caller should lock the
282  * database to prevent concurrent updates done by other
283  * threads.
284  */
285 nscd_rc_t
286 _nscd_delete_db_entry(
287 	nscd_db_t		*db,
288 	int			type,
289 	const char		*str,
290 	nscd_db_option_t	option,
291 	int			id_num)
292 {
293 	int			i;
294 	int			del_more = 0;
295 	unsigned long		hash;
296 	nscd_hash_t		*idx_p, *next_p = NULL, *prev_p = NULL;
297 	nscd_db_entry_t		*db_entry;
298 
299 	/* find the bucket */
300 	hash = calc_hash(str);
301 	i = hash % db->array_size;
302 	idx_p = db->hash_tbl_p[i];
303 
304 	/* delete nothing always works */
305 	if (idx_p == NULL)
306 		return (NSCD_SUCCESS);
307 
308 	while (idx_p != NULL) {
309 		db_entry = &idx_p->db_entry;
310 		if (db_entry->type != type)
311 			goto cont;
312 		if (strcasecmp(db_entry->name, str) != 0)
313 			goto cont;
314 
315 		switch (option) {
316 
317 		case NSCD_DEL_FIRST_DB_ENTRY:
318 			prev_p = idx_p->prev_p;
319 			next_p = idx_p->next_p;
320 			del_more = 0;
321 			break;
322 
323 		case NSCD_DEL_EXACT_DB_ENTRY:
324 			if (db_entry->id_num == id_num) {
325 				prev_p = idx_p->prev_p;
326 				next_p = idx_p->next_p;
327 				del_more = 0;
328 			} else
329 				goto cont;
330 			break;
331 
332 		case NSCD_DEL_ALL_DB_ENTRY:
333 			prev_p = idx_p->prev_p;
334 			next_p = idx_p->next_p;
335 			break;
336 		}
337 
338 		if (prev_p == NULL)
339 			db->hash_tbl_p[i] = next_p;
340 		else
341 			prev_p->next_p = next_p;
342 
343 		if (next_p != NULL)
344 			next_p->prev_p = prev_p;
345 
346 		free(idx_p);
347 
348 		if (del_more == 0)
349 			break;
350 		/*
351 		 * only when option == NSCD_DEL_ALL_DB_ENTRY
352 		 * will we get here. next_p should be set to
353 		 * idx_p->next_p beforehand
354 		 */
355 		idx_p = next_p;
356 		continue;
357 
358 		cont:
359 
360 		idx_p = idx_p->next_p;
361 	}
362 
363 	return (NSCD_SUCCESS);
364 }
365 
366 /*
367  * FUNCTION: _nscd_alloc_db_entry
368  *
369  * Allocate and return the memory for a database entry
370  * so the caller can insert data and then add it to the
371  * database.
372  */
373 nscd_db_entry_t *
374 _nscd_alloc_db_entry(
375 	int			type,
376 	const char 		*name,
377 	int			dataSize,
378 	int			num_data,
379 	int			num_array)
380 {
381 	int			size;
382 	int			array_o, data_o;
383 	nscd_hash_t		*hash;
384 	void			*p;
385 
386 	/* first part: hash data structure and name string */
387 	size = sizeof (*hash) + strlen(name) + 1;
388 	array_o = size = roundup(size);
389 
390 	/* second part: pointer array to data */
391 	size += (num_data  + num_array) * sizeof (void **);
392 	size = roundup(size);
393 
394 	/* third part: actual data */
395 	data_o = size;
396 	size += dataSize;
397 
398 	/* allocate the memory */
399 	hash = (nscd_hash_t *)calloc(1, size);
400 
401 	if (hash == NULL)
402 		return (NULL);
403 
404 	/* init the entry based on caller's input */
405 	hash->db_entry.num_data = num_data;
406 	hash->db_entry.num_array = num_array;
407 	hash->db_entry.type = type;
408 	hash->db_entry.name = (char *)hash + sizeof (*hash);
409 	p = (char *)hash + array_o;
410 	hash->db_entry.data_array = (void **)p;
411 	*(hash->db_entry.data_array) = (char *)hash + data_o;
412 	(void) strcpy(hash->db_entry.name, name);
413 
414 	return (&hash->db_entry);
415 }
416 
417 /*
418  * FUNCTION: _nscd_delete_db_entry_cookie
419  *
420  * Delete a database entry using the information from
421  * the input 'cookie'.
422  */
423 void
424 _nscd_delete_db_entry_cookie(
425 	nscd_db_t	*db,
426 	void		**cookie)
427 {
428 	nscd_hash_t	*hp;
429 	struct cookie	*c;
430 
431 	/* snaity check */
432 	if (cookie == NULL || *cookie == NULL || db == NULL)
433 		return;
434 	c = *cookie;
435 
436 	/* more snaity check */
437 	if (db != c->db || c->hash == NULL ||
438 		c->idx < 0 || c->idx >= db->array_size)
439 		return;
440 
441 	/* retrieve the hash entry from the cookie */
442 	hp = c->hash;
443 
444 	/*
445 	 * Update the next/previous link list.
446 	 * Need to update c->hash as well, in case
447 	 * the cookie is also used in a walk-db
448 	 * loop. This is to make sure that the
449 	 * next _nscd_walk_db() call will
450 	 * find the (updated) next hash entry in line.
451 	 */
452 	if (hp->prev_p == NULL)	{
453 		/*
454 		 * make sure the current bucket will be
455 		 * walked again if _nscd_walk_db is
456 		 * called next
457 		 */
458 		c->hash = NULL;
459 		db->hash_tbl_p[c->idx] = hp->next_p;
460 		c->idx--;
461 
462 	} else {
463 		c->hash = hp->prev_p;
464 		hp->prev_p->next_p = hp->next_p;
465 	}
466 	if (hp->next_p != NULL)
467 		hp->next_p->prev_p = hp->prev_p;
468 
469 	/* delete the entry */
470 	free(hp);
471 }
472 
473 /*
474  * FUNCTION: _nscd_alloc_db
475  *
476  * Allocate the space for a nscd database.
477  *
478  * The input argument, size, indicates the size of the database.
479  * NSCD_DB_SIZE_LARGE specifies an bucket array of size 67,
480  * NSCD_DB_SIZE_MEDIUM specifies an bucket array of size 37,
481  * NSCD_DB_SIZE_SMALL specifies an bucket array of size 13,
482  * NSCD_DB_SIZE_TINY specifies an bucket array of size 3.
483  */
484 nscd_db_t *
485 _nscd_alloc_db(
486 	int		size)
487 {
488 	int		sz;
489 	nscd_db_t	*db;
490 
491 	/* allocate the database */
492 	db = (nscd_db_t *)calloc(1, sizeof (nscd_db_t));
493 	if (db == NULL)
494 		return (NULL);
495 
496 	/* allocate the bucket array */
497 	if (size == NSCD_DB_SIZE_LARGE)
498 		sz = 67;
499 	else if (size == NSCD_DB_SIZE_MEDIUM)
500 		sz = 37;
501 	else if (size == NSCD_DB_SIZE_SMALL)
502 		sz = 13;
503 	else if (size == NSCD_DB_SIZE_TINY)
504 		sz = 3;
505 	db->hash_tbl_p = (nscd_hash_t  **)calloc(sz + 1,
506 			sizeof (nscd_hash_t *));
507 	if (db->hash_tbl_p == NULL) {
508 		free(db);
509 		return (NULL);
510 	}
511 
512 	db->array_size = sz;
513 
514 	return (db);
515 }
516 
517 /*
518  * FUNCTION: _nscd_free_db
519  *
520  * Delete a nscd database.
521  */
522 void
523 _nscd_free_db(
524 	nscd_db_t	*db)
525 {
526 	int		i;
527 	nscd_hash_t	*hp, *next_p;
528 
529 	/*
530 	 * find non-empty buckets and for each one of them,
531 	 * delete all the database entries in it's link list
532 	 */
533 	for (i = 0; i < db->array_size; i++) {
534 
535 		hp = db->hash_tbl_p[i];
536 
537 		while (hp != NULL) {
538 			next_p = hp->next_p;
539 			free(hp);
540 			hp = next_p;
541 		}
542 	}
543 
544 	/* free the bucket array */
545 	free(db->hash_tbl_p);
546 
547 	free(db);
548 }
549 
550 /*
551  * FUNCTION: _nscd_walk_db
552  *
553  * Iterate through the database entries contained in
554  * a nscd database and return one entry at a time.
555  * The cookie structure is used to indicate the
556  * location of the returned entry for the next call
557  * to this function. For the very first call, *cookie
558  * should be set to NULL. For subsequent calls, the one
559  * returned by the previous call sould be used.
560  */
561 nscd_db_entry_t *
562 _nscd_walk_db(
563 	nscd_db_t	*db,
564 	void		**cookie)
565 {
566 	struct cookie	*c;
567 
568 	/* sanity check */
569 	if (cookie == NULL || db == NULL)
570 		return (NULL);
571 
572 	if (*cookie != NULL) {
573 
574 		c = *cookie;
575 
576 		/*
577 		 * More sanity check. _nscd_delete_db_entry_cookie()
578 		 * could change c->idx to -1.
579 		 */
580 		if (db != c->db ||
581 			c->idx < -1 || c->idx >= db->array_size)
582 			return (NULL);
583 
584 		/* is there a next entry ? */
585 		if (c->hash != NULL)
586 			c->hash = c->hash->next_p;
587 
588 		/* yes, return it */
589 		if (c->hash != NULL) {
590 			return (&c->hash->db_entry);
591 		}
592 	} else {
593 		c = (struct cookie *)calloc(1, sizeof (*c));
594 		if (c == NULL)
595 			return (NULL);
596 		c->idx = -1;
597 		c->hash = NULL;
598 		c->db = db;
599 	}
600 
601 	/* find the first non-empty bucket */
602 	for (c->idx++; c->idx < db->array_size; c->idx++) {
603 		c->hash = db->hash_tbl_p[c->idx];
604 		if (c->hash != NULL)
605 			break;
606 	}
607 
608 	/* no (more) non-empty bucket, we are done */
609 	if (c->hash == NULL) {
610 		free(c);
611 		*cookie = NULL;
612 		return (NULL);
613 	}
614 
615 	*cookie = c;
616 	return (&c->hash->db_entry);
617 }
618