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