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 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #include <string.h>
28 #include <pthread.h>
29 #include <syslog.h>
30 #include <rpcsvc/nis.h>
31
32 #include "nis_hashitem.h"
33
34 /* We're the magician, so undefine the define-magic */
35 #undef NIS_HASH_ITEM
36 #undef NIS_HASH_TABLE
37 #undef nis_insert_item
38 #undef nis_find_item
39 #undef nis_pop_item
40 #undef nis_remove_item
41
42 #define set_thread_status(msg, state)
43
44 /*
45 * The hash table routines below implement nested (or recursive)
46 * one-writer-or-many-readers locking. The following restrictions
47 * exist:
48 *
49 * Unless an item destructor has been established, an item
50 * MUST NOT be removed from a list (__nis_pop_item_mt() or
51 * (__nis_remove_item_mt()) when the thread performing
52 * the deletion is holding a read-only lock on the item.
53 * Doing so will result in the thread blocking in
54 * pthread_cond_wait() waiting for itself to signal on
55 * the condition variable. Deletion when the invoking
56 * thread is holding a write lock (any level of nesting),
57 * or no lock, is OK.
58 */
59
60 void
__nis_init_hash_table(__nis_hash_table_mt * table,void (* itemDestructor)(void *))61 __nis_init_hash_table(__nis_hash_table_mt *table,
62 void (*itemDestructor)(void *)) {
63
64 int errorcode;
65
66 if (table != 0) {
67 errorcode = pthread_mutex_init(&table->lock, 0);
68 if (errorcode != 0) {
69 syslog(LOG_WARNING, "__nis_init_hash_table: "
70 "(table->lock) pthread_mutex_init returned %d (%s)",
71 errorcode, strerror(errorcode));
72 }
73
74 errorcode = pthread_cond_init(&table->cond, 0);
75 if (errorcode != 0) {
76 syslog(LOG_WARNING, "__nis_init_hash_table: "
77 "(table->cond) pthread_cond_init returned %d (%s)",
78 errorcode, strerror(errorcode));
79 }
80
81 errorcode = pthread_mutex_init(&table->traverser_id_lock, 0);
82 if (errorcode != 0) {
83 syslog(LOG_WARNING, "__nis_init_hash_table: "
84 "(table->traverser_id_lock) "
85 "pthread_mutex_init returned %d (%s)",
86 errorcode, strerror(errorcode));
87 }
88
89 table->traversed = 0;
90 table->locked_items = 0;
91 (void) memset(table->keys, 0, sizeof (table->keys));
92 table->first = 0;
93 table->destroyItem = itemDestructor;
94 }
95 }
96
97 int
__nis_lock_hash_table(__nis_hash_table_mt * table,int traverse,char * msg)98 __nis_lock_hash_table(__nis_hash_table_mt *table, int traverse, char *msg) {
99
100 pthread_t myself = pthread_self();
101
102 if (table != 0) {
103 if (traverse) {
104 /*
105 * We want exclusive access to everything in the
106 * table (list). Wait until there are no threads
107 * either traversing the list, or with exclusive
108 * access to an item.
109 */
110 set_thread_status(msg, "table WL");
111 (void) pthread_mutex_lock(&table->lock);
112 set_thread_status(msg, "table L");
113 while ((table->traversed != 0 &&
114 table->traverser_id != myself) ||
115 table->locked_items != 0) {
116 set_thread_status(msg, "traverse cond_wait");
117 MT_LOG(1, (LOG_NOTICE,
118 "%d: lh table 0x%x trav cond wait",
119 myself, table));
120 (void) pthread_cond_wait(&table->cond,
121 &table->lock);
122 }
123 set_thread_status(msg, "traverser_id WL");
124 (void) pthread_mutex_lock(&table->traverser_id_lock);
125 set_thread_status(msg, "traverser_id L");
126 table->traversed = 1;
127 table->traverser_id = myself;
128 (void) pthread_mutex_unlock(&table->traverser_id_lock);
129 set_thread_status(msg, "traverser_id U");
130 } else {
131 /*
132 * Called from the nis_*_item() functions. If no one's
133 * locked the table, lock it. If the table already is
134 * being traversed by us, do nothing. Otherwise, wait
135 * for the lock.
136 */
137 set_thread_status(msg, "non-traverse TL");
138 if (pthread_mutex_trylock(&table->lock) == EBUSY) {
139 int dolock = 1;
140 /* Already locked; find out if it's us */
141 set_thread_status(msg, "traverser_id L");
142 (void) pthread_mutex_lock(
143 &table->traverser_id_lock);
144 if (table->traversed != 0 &&
145 table->traverser_id == myself) {
146 /* It's us. No action. */
147 dolock = 0;
148 }
149 (void) pthread_mutex_unlock(
150 &table->traverser_id_lock);
151 set_thread_status(msg, "traverser_id U");
152 /* Not us. Wait for the lock */
153 if (dolock) {
154 MT_LOG(1, (LOG_NOTICE,
155 "%d: lh table 0x%x cond wait",
156 myself, table));
157 set_thread_status(msg, "table WL");
158 (void) pthread_mutex_lock(&table->lock);
159 set_thread_status(msg, "table L");
160 }
161 }
162 }
163 MT_LOG(1, (LOG_NOTICE, "%d: lh table %s lock acquired 0x%x",
164 myself, traverse?"traverse":"non-traverse", table));
165 return (1);
166 } else {
167 return (0);
168 }
169 }
170
171 int
__nis_ulock_hash_table(__nis_hash_table_mt * table,int traverse,char * msg)172 __nis_ulock_hash_table(__nis_hash_table_mt *table, int traverse, char *msg) {
173
174 int dounlock = 0;
175
176 if (table != 0) {
177 if (traverse) {
178 /*
179 * Since we're keeping track of who's traversing the
180 * table in order to avoid recursive locking in the
181 * nis_*item() functions, we might as well sanity check
182 * here.
183 */
184 set_thread_status(msg, "traverser_id WL");
185 (void) pthread_mutex_lock(&table->traverser_id_lock);
186 set_thread_status(msg, "traverser_id L");
187 if (table->traversed != 0 &&
188 table->traverser_id == pthread_self()) {
189 table->traversed = 0;
190 /*
191 * Leave traverser_id as it is, so that it
192 * possible to see which thread last held
193 * the traverser lock.
194 */
195 dounlock = 1;
196 /* Wake up other traversers-to-be */
197 set_thread_status(msg, "table cond_signal");
198 (void) pthread_cond_signal(&table->cond);
199 }
200 (void) pthread_mutex_unlock(&table->traverser_id_lock);
201 set_thread_status(msg, "traverser_id U");
202 } else {
203 /*
204 * Called from the nis_*_item() functions. If we're
205 * traversing the table, leave it locked.
206 */
207 set_thread_status(msg, "traverser_id WL");
208 (void) pthread_mutex_lock(&table->traverser_id_lock);
209 set_thread_status(msg, "traverser_id L");
210 if (table->traversed == 0) {
211 dounlock = 1;
212 }
213 (void) pthread_mutex_unlock(&table->traverser_id_lock);
214 set_thread_status(msg, "traverser_id U");
215 }
216 if (dounlock) {
217 (void) pthread_mutex_unlock(&table->lock);
218 set_thread_status(msg, "table U");
219 }
220 MT_LOG(1, (LOG_NOTICE, "%d: lh table %s release 0x%x (%s)",
221 pthread_self(), traverse?"traverse":"non-traverse", table,
222 dounlock?"unlocked":"still held"));
223 return (1);
224 } else {
225 return (0);
226 }
227 }
228
229 static __nis_hash_item_mt **
__find_item_mt(nis_name name,__nis_hash_table_mt * table,int * keyp)230 __find_item_mt(nis_name name, __nis_hash_table_mt *table, int *keyp) {
231
232 int key = 0;
233 unsigned char *s;
234 __nis_hash_item_mt *it, **pp;
235
236 /* Assume table!=0, table lock held */
237
238 for (s = (unsigned char *)name; *s != 0; s++) {
239 key += *s;
240 }
241 key %= (sizeof (table->keys) / sizeof (table->keys[0]));
242
243 if (keyp != 0) {
244 *keyp = key;
245 }
246 for (pp = &table->keys[key]; (it = *pp) != 0; pp = &it->next) {
247 if (strcmp(name, it->name) == 0) {
248 break;
249 }
250 }
251
252 return (pp);
253 }
254
255 /*
256 * The 'readwrite' argument is interpreted as follows on a successful
257 * return:
258 *
259 * < 0 Exclusive access to item
260 * 0 Item must not be used or referenced in any way
261 * > 0 Non-exclusive access (read-only) to item
262 *
263 * Except when 'readwrite' == 0, the caller must explicitly release the
264 * item (__nis_release_item()).
265 */
266 int
__nis_insert_item_mt(void * arg,__nis_hash_table_mt * table,int readwrite)267 __nis_insert_item_mt(void *arg, __nis_hash_table_mt *table, int readwrite) {
268
269 __nis_hash_item_mt *item = arg;
270 int key;
271 __nis_hash_item_mt **pp;
272
273 if (item == 0 || __nis_lock_hash_table(table, 0, "nitmt") == 0)
274 return (0);
275
276 if ((*(pp = __find_item_mt(item->name, table, &key))) != 0) {
277 (void) __nis_ulock_hash_table(table, 0, "nitmt");
278 return (0);
279 }
280
281 (void) pthread_cond_init(&item->lock, 0);
282 item->readers = item->writer = 0;
283 item->last_reader_id = item->writer_id = INV_PTHREAD_ID;
284 if (readwrite < 0) {
285 item->writer = 1;
286 item->writer_id = pthread_self();
287 table->locked_items++;
288 } else if (readwrite > 0) {
289 item->readers = 1;
290 item->last_reader_id = pthread_self();
291 table->locked_items++;
292 }
293 item->next = *pp;
294 *pp = item;
295 item->keychain = key;
296
297 if (table->first)
298 table->first->prv_item = item;
299
300 item->nxt_item = table->first;
301 item->prv_item = NULL;
302 table->first = item;
303
304 (void) __nis_ulock_hash_table(table, 0, "nitmt");
305
306 return (1);
307 }
308
309 void
__nis_insert_name_mt(nis_name name,__nis_hash_table_mt * table)310 __nis_insert_name_mt(nis_name name, __nis_hash_table_mt *table) {
311
312 __nis_hash_item_mt *item;
313
314 if (name == 0 || table == 0)
315 return;
316
317 if ((item = malloc(sizeof (*item))) == 0) {
318 syslog(LOG_WARNING, "__nis_insert_name_mt: malloc failed\n");
319 return;
320 }
321
322 if ((item->name = strdup(name)) == 0) {
323 syslog(LOG_WARNING, "__nis_insert_name_mt: strdup failed\n");
324 free(item);
325 return;
326 }
327
328 if (! __nis_insert_item_mt(item, table, 0)) {
329 free(item->name);
330 free(item);
331 }
332 }
333
334 /*
335 * readwrite: < 0 Exclusive access
336 * 0 No access; must not use returned item in any way,
337 * other than to confirm existence indicated by a non-NULL
338 * return value.
339 * > 0 Non-exclusive (read-only) access
340 *
341 * If trylock != 0 and *trylock != 0 and the item exists but the requested
342 * lock type cannot be acquired, set *trylock = -1 and return 0.
343 */
344 void *
__nis_find_item_mt(nis_name name,__nis_hash_table_mt * table,int readwrite,int * trylock)345 __nis_find_item_mt(nis_name name, __nis_hash_table_mt *table, int readwrite,
346 int *trylock) {
347
348 __nis_hash_item_mt *item;
349 pthread_t me = pthread_self();
350
351 if (name == 0 || __nis_lock_hash_table(table, 0, "nfimt") == 0)
352 return (0);
353
354 /*
355 * Block waiting for more favorable conditions unless:
356 *
357 * The item doesn't exist anymore
358 *
359 * 'readwrite' == 0 (verify existence only)
360 *
361 * There's a writer, but it's us
362 *
363 * There are no writers, and we're satisfied by RO access
364 *
365 * A trylock was requested
366 */
367 while ((item = *__find_item_mt(name, table, 0)) != 0) {
368 if (readwrite == 0 ||
369 (item->writer == 0 && item->readers == 0))
370 break;
371 if (item->writer == 0 && readwrite > 0)
372 break;
373 if ((item->writer != 0 && item->writer_id == me))
374 break;
375 if (trylock != 0 && *trylock != 0) {
376 *trylock = -1;
377 (void) __nis_ulock_hash_table(table, 0, "nfimt");
378 return (0);
379 }
380 (void) pthread_cond_wait(&item->lock, &table->lock);
381 }
382
383 if (item != 0) {
384 if (readwrite < 0) {
385 if (item->writer == 0) {
386 item->writer_id = me;
387 table->locked_items++;
388 }
389 item->writer++;
390 } else if (readwrite > 0) {
391 if (item->readers == 0) {
392 table->locked_items++;
393 }
394 item->last_reader_id = me;
395 item->readers++;
396 }
397 }
398
399 (void) __nis_ulock_hash_table(table, 0, "nfimt");
400
401 return (item);
402 }
403
404 void *
__nis_pop_item_mt(__nis_hash_table_mt * table)405 __nis_pop_item_mt(__nis_hash_table_mt *table) {
406
407 __nis_hash_item_mt *item, *cur, *prev;
408 pthread_t mtid;
409
410 if (__nis_lock_hash_table(table, 0, "npimt") == 0)
411 return (0);
412
413 /* Wait until the first item isn't in use by another thread */
414 mtid = pthread_self();
415 while ((item = table->first) != 0) {
416 if (table->destroyItem != 0)
417 break;
418 if (item->readers == 0 && item->writer == 0)
419 break;
420 if (item->writer != 0 && item->writer_id == mtid)
421 break;
422 (void) pthread_cond_wait(&item->lock, &table->lock);
423 }
424
425 /* List might be empty now */
426 if (item == 0) {
427 __nis_ulock_hash_table(table, 0, "npimt");
428 return (0);
429 }
430
431 prev = 0;
432 for (cur = table->keys[item->keychain]; cur;
433 prev = cur, cur = cur->next) {
434 if (cur == item) {
435 if (prev)
436 prev->next = cur->next;
437 else
438 table->keys[cur->keychain] = cur->next;
439 if (cur->prv_item)
440 cur->prv_item->nxt_item = cur->nxt_item;
441 else
442 table->first = cur->nxt_item;
443 if (cur->nxt_item)
444 cur->nxt_item->prv_item = cur->prv_item;
445 break;
446 }
447 }
448
449 /*
450 * We use keychain < 0 to indicate that the item isn't linked
451 * into the table anymore.
452 */
453 item->keychain = -1;
454
455 /* Adjust the count of locked items in the table */
456 if (table->locked_items != 0 &&
457 (item->writer > 0 || item->readers > 0)) {
458 table->locked_items--;
459 if (table->locked_items == 0) {
460 /* Wake up traversers-to-be */
461 (void) pthread_cond_signal(&table->cond);
462 }
463 }
464
465 /*
466 * Wake up any threads that were waiting for this item. Obviously,
467 * such threads must start over scanning the list.
468 */
469 (void) pthread_cond_signal(&item->lock);
470 (void) pthread_cond_destroy(&item->lock);
471
472 /*
473 * If the item isn't locked, and an item destructor has been
474 * established, invoke the destructor.
475 */
476 if (item->readers == 0 && item->writer == 0 &&
477 table->destroyItem != 0) {
478 (*table->destroyItem)(item);
479 item = 0;
480 } else {
481 item->next = 0;
482 item->prv_item = 0;
483 item->nxt_item = 0;
484 }
485
486 (void) __nis_ulock_hash_table(table, 0, "npimt");
487
488 /*
489 * If we get here, and the 'item' is NULL, we've popped the
490 * item, but also destroyed it. Returning NULL would make
491 * our caller believe the list is empty, so instead, we invoke
492 * ourselves to pop the next item.
493 */
494 return ((item != 0) ? item : __nis_pop_item_mt(table));
495 }
496
497 void *
__nis_remove_item_mt(nis_name name,__nis_hash_table_mt * table)498 __nis_remove_item_mt(nis_name name, __nis_hash_table_mt *table) {
499
500 __nis_hash_item_mt *nl, **pp;
501 pthread_t mtid;
502
503 if (__nis_lock_hash_table(table, 0, "nrimt") == 0)
504 return (0);
505
506 /* Find the item, and make sure it's not in use */
507 mtid = pthread_self();
508 while ((nl = *(pp = __find_item_mt(name, table, (int *)0))) != 0) {
509 if (table->destroyItem != 0)
510 break;
511 if (nl->readers == 0 && nl->writer == 0)
512 break;
513 if (nl->writer != 0 && nl->writer_id == mtid)
514 break;
515 (void) pthread_cond_wait(&nl->lock, &table->lock);
516 }
517
518 if (nl == 0) {
519 (void) __nis_ulock_hash_table(table, 0, "nrimt");
520 return (0);
521 }
522
523 /* Remove nl from the hash chain */
524 *pp = nl->next;
525 nl->next = 0;
526
527 /* Remove nl from the linked list of all names */
528 if (nl->prv_item)
529 nl->prv_item->nxt_item = nl->nxt_item;
530 else
531 table->first = nl->nxt_item;
532
533 if (nl->nxt_item)
534 nl->nxt_item->prv_item = nl->prv_item;
535 nl->prv_item = 0;
536 nl->nxt_item = 0;
537
538 /* keychain < 0 means not in table anymore */
539 nl->keychain = -1;
540
541 /*
542 * If this item was locked, we can now decrement the count of
543 * locked items for the table.
544 */
545 if (table->locked_items != 0 &&
546 (nl->writer > 0 || nl->readers > 0)) {
547 table->locked_items--;
548 if (table->locked_items == 0) {
549 /* Wake up traversers-to-be */
550 (void) pthread_cond_signal(&table->cond);
551 }
552 }
553 (void) pthread_cond_signal(&nl->lock);
554 (void) pthread_cond_destroy(&nl->lock);
555
556 /*
557 * If the item isn't locked, and an item destructor has been
558 * established, invoke the destructor. In that case, we return
559 * NULL, so that our caller doesn't try to reference the
560 * deleted item.
561 */
562 if (nl->readers == 0 && nl->writer == 0 && table->destroyItem != 0) {
563 (*table->destroyItem)(nl);
564 nl = 0;
565 }
566
567 (void) __nis_ulock_hash_table(table, 0, "nrimt");
568
569 return (nl);
570 }
571
572 /*
573 * Release an item that had been acquired exclusively or non-exclusively.
574 * Note that 'readwrite' can assume any integer value, and thus can be
575 * used to release any level of recursive locking. It's the responsibility
576 * of the caller to make sure that proper nesting is maintained.
577 */
578 int
__nis_release_item(void * arg,__nis_hash_table_mt * table,int readwrite)579 __nis_release_item(void *arg, __nis_hash_table_mt *table, int readwrite) {
580
581 __nis_hash_item_mt *item = arg;
582 int wakeup = 0;
583
584 if (item == 0 || __nis_lock_hash_table(table, 0, "nreli") == 0)
585 return (0);
586
587 if ((readwrite < 0 && abs(readwrite) > item->writer) ||
588 (readwrite < 0 && item->writer > 0 &&
589 item->writer_id != pthread_self()) ||
590 (readwrite > 0 && readwrite > item->readers)) {
591 /* Caller confused; ignore */
592 (void) __nis_ulock_hash_table(table, 0, "nreli");
593 return (0);
594 }
595
596 if (readwrite < 0) {
597 item->writer += readwrite;
598 if (item->writer == 0 && item->keychain >= 0) {
599 if (table->locked_items != 0)
600 table->locked_items--;
601 wakeup = 1;
602 }
603 } else if (readwrite > 0) {
604 item->readers -= readwrite;
605 item->last_reader_id = INV_PTHREAD_ID;
606 if (item->readers == 0 && item->keychain >= 0) {
607 if (table->locked_items != 0)
608 table->locked_items--;
609 wakeup = 1;
610 }
611 }
612
613 if (table->locked_items == 0) {
614 /* Wake up traversers-to-be */
615 (void) pthread_cond_signal(&table->cond);
616 }
617 if (wakeup) {
618 /* Wake up anyone else who wants this item */
619 (void) pthread_cond_signal(&item->lock);
620 }
621
622 /*
623 * Delete if no references, not linked into list, and destructor
624 * established.
625 */
626 if (item->keychain < 0 &&
627 item->readers == 0 && item->writer == 0 &&
628 item->next == 0 &&
629 item->prv_item == 0 && item->nxt_item == 0 &&
630 table->destroyItem != 0)
631 (*table->destroyItem)(item);
632
633 (void) __nis_ulock_hash_table(table, 0, "nreli");
634
635 return (1);
636 }
637
638 /*
639 * Return -1 if item checked out for both reading and writing, 1 if
640 * readonly, and 0 otherwise.
641 */
642 int
__nis_item_access(void * arg)643 __nis_item_access(void *arg) {
644
645 __nis_hash_item_mt *item = arg;
646
647 if (item != 0) {
648 if (item->writer > 0) {
649 if (item->writer_id != pthread_self())
650 abort();
651 return (-1);
652 } else if (item->readers > 0) {
653 return (1);
654 }
655 }
656
657 return (0);
658 }
659
660 /*
661 * __nis_scan_table_mt()
662 *
663 * Iterate over all items in a __nis_hash_table_mt. We ignore
664 * first/prv_item/nxt_item and scan in hash-chain order. The iterator
665 * function should *not* insert or delete items. If the iterator
666 * function returns TRUE the scan terminates. For compatibility with
667 * the existing non-MT nis_scan_table() this function has no return
668 * value.
669 */
670 void
__nis_scan_table_mt(__nis_hash_table_mt * table,bool_t (* func)(__nis_hash_item_mt *,void *),void * funcarg)671 __nis_scan_table_mt(
672 __nis_hash_table_mt *table,
673 bool_t (*func)(__nis_hash_item_mt *, void *),
674 void *funcarg)
675 {
676 int slot;
677
678 if (table == 0) {
679 return;
680 }
681
682 if (__nis_lock_hash_table(table, 1, "nstmt") == 0) {
683 syslog(LOG_DEBUG, "__nis_scan_table_mt: mutex lock failed ");
684 return;
685 }
686
687 for (slot = 0;
688 slot < sizeof (table->keys) / sizeof (table->keys[0]);
689 slot++) {
690 __nis_hash_item_mt *it;
691
692 for (it = table->keys[slot]; it != 0; it = it->next) {
693 if (TRUE == (*func)(it, funcarg)) {
694 break;
695 }
696 }
697 }
698 if (__nis_ulock_hash_table(table, 1, "nstmt") == 0)
699 syslog(LOG_DEBUG, "__nis_scan_table_mt: mutex unlock failed ");
700 }
701