1 /*****************************************************************************\
2 * Copyright (C) 2010 Lawrence Livermore National Security, LLC.
3 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
4 * Written by Brian Behlendorf <behlendorf1@llnl.gov>.
7 * This file is part of the SPL, Solaris Porting Layer.
8 * For details, see <http://zfsonlinux.org/>.
10 * The SPL is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the
12 * Free Software Foundation; either version 2 of the License, or (at your
13 * option) any later version.
15 * The SPL is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 * You should have received a copy of the GNU General Public License along
21 * with the SPL. If not, see <http://www.gnu.org/licenses/>.
22 *****************************************************************************
23 * Solaris Porting Layer (SPL) Thread Specific Data Implementation.
25 * Thread specific data has implemented using a hash table, this avoids
26 * the need to add a member to the task structure and allows maximum
27 * portability between kernels. This implementation has been optimized
28 * to keep the tsd_set() and tsd_get() times as small as possible.
30 * The majority of the entries in the hash table are for specific tsd
31 * entries. These entries are hashed by the product of their key and
32 * pid because by design the key and pid are guaranteed to be unique.
33 * Their product also has the desirable properly that it will be uniformly
34 * distributed over the hash bins providing neither the pid nor key is zero.
35 * Under linux the zero pid is always the init process and thus won't be
36 * used, and this implementation is careful to never to assign a zero key.
37 * By default the hash table is sized to 512 bins which is expected to
38 * be sufficient for light to moderate usage of thread specific data.
40 * The hash table contains two additional type of entries. They first
41 * type is entry is called a 'key' entry and it is added to the hash during
42 * tsd_create(). It is used to store the address of the destructor function
43 * and it is used as an anchor point. All tsd entries which use the same
44 * key will be linked to this entry. This is used during tsd_destory() to
45 * quickly call the destructor function for all tsd associated with the key.
46 * The 'key' entry may be looked up with tsd_hash_search() by passing the
47 * key you wish to lookup and DTOR_PID constant as the pid.
49 * The second type of entry is called a 'pid' entry and it is added to the
50 * hash the first time a process set a key. The 'pid' entry is also used
51 * as an anchor and all tsd for the process will be linked to it. This
52 * list is using during tsd_exit() to ensure all registered destructors
53 * are run for the process. The 'pid' entry may be looked up with
54 * tsd_hash_search() by passing the PID_KEY constant as the key, and
55 * the process pid. Note that tsd_exit() is called by thread_exit()
56 * so if your using the Solaris thread API you should not need to call
57 * tsd_exit() directly.
59 \*****************************************************************************/
62 #include <sys/thread.h>
64 #include <spl-debug.h>
66 #ifdef DEBUG_SUBSYSTEM
67 #undef DEBUG_SUBSYSTEM
70 #define DEBUG_SUBSYSTEM SS_TSD
71 #define DEBUG_SUBSYSTEM SS_TSD
73 typedef struct tsd_hash_bin
{
75 struct hlist_head hb_head
;
78 typedef struct tsd_hash_table
{
82 tsd_hash_bin_t
*ht_bins
;
85 typedef struct tsd_hash_entry
{
90 struct hlist_node he_list
;
91 struct list_head he_key_list
;
92 struct list_head he_pid_list
;
95 static tsd_hash_table_t
*tsd_hash_table
= NULL
;
99 * tsd_hash_search - searches hash table for tsd_hash_entry
104 static tsd_hash_entry_t
*
105 tsd_hash_search(tsd_hash_table_t
*table
, uint_t key
, pid_t pid
)
107 struct hlist_node
*node
;
108 tsd_hash_entry_t
*entry
;
113 hash
= hash_long((ulong_t
)key
* (ulong_t
)pid
, table
->ht_bits
);
114 bin
= &table
->ht_bins
[hash
];
115 spin_lock(&bin
->hb_lock
);
116 hlist_for_each(node
, &bin
->hb_head
) {
117 entry
= list_entry(node
, tsd_hash_entry_t
, he_list
);
118 if ((entry
->he_key
== key
) && (entry
->he_pid
== pid
)) {
119 spin_unlock(&bin
->hb_lock
);
124 spin_unlock(&bin
->hb_lock
);
129 * tsd_hash_dtor - call the destructor and free all entries on the list
130 * @work: list of hash entries
132 * For a list of entries which have all already been removed from the
133 * hash call their registered destructor then free the associated memory.
136 tsd_hash_dtor(struct hlist_head
*work
)
138 tsd_hash_entry_t
*entry
;
141 while (!hlist_empty(work
)) {
142 entry
= hlist_entry(work
->first
, tsd_hash_entry_t
, he_list
);
143 hlist_del(&entry
->he_list
);
145 if (entry
->he_dtor
&& entry
->he_pid
!= DTOR_PID
)
146 entry
->he_dtor(entry
->he_value
);
148 kmem_free(entry
, sizeof(tsd_hash_entry_t
));
155 * tsd_hash_add - adds an entry to hash table
160 * The caller is responsible for ensuring the unique key/pid do not
161 * already exist in the hash table. This possible because all entries
162 * are thread specific thus a concurrent thread will never attempt to
163 * add this key/pid. Because multiple bins must be checked to add
164 * links to the dtor and pid entries the entire table is locked.
167 tsd_hash_add(tsd_hash_table_t
*table
, uint_t key
, pid_t pid
, void *value
)
169 tsd_hash_entry_t
*entry
, *dtor_entry
, *pid_entry
;
175 ASSERT3P(tsd_hash_search(table
, key
, pid
), ==, NULL
);
177 /* New entry allocate structure, set value, and add to hash */
178 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
184 entry
->he_value
= value
;
185 INIT_HLIST_NODE(&entry
->he_list
);
186 INIT_LIST_HEAD(&entry
->he_key_list
);
187 INIT_LIST_HEAD(&entry
->he_pid_list
);
189 spin_lock(&table
->ht_lock
);
191 /* Destructor entry must exist for all valid keys */
192 dtor_entry
= tsd_hash_search(table
, entry
->he_key
, DTOR_PID
);
193 ASSERT3P(dtor_entry
, !=, NULL
);
194 entry
->he_dtor
= dtor_entry
->he_dtor
;
196 /* Process entry must exist for all valid processes */
197 pid_entry
= tsd_hash_search(table
, PID_KEY
, entry
->he_pid
);
198 ASSERT3P(pid_entry
, !=, NULL
);
200 hash
= hash_long((ulong_t
)key
* (ulong_t
)pid
, table
->ht_bits
);
201 bin
= &table
->ht_bins
[hash
];
202 spin_lock(&bin
->hb_lock
);
204 /* Add to the hash, key, and pid lists */
205 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
206 list_add(&entry
->he_key_list
, &dtor_entry
->he_key_list
);
207 list_add(&entry
->he_pid_list
, &pid_entry
->he_pid_list
);
209 spin_unlock(&bin
->hb_lock
);
210 spin_unlock(&table
->ht_lock
);
216 * tsd_hash_add_key - adds a destructor entry to the hash table
219 * @dtor: key destructor
221 * For every unique key there is a single entry in the hash which is used
222 * as anchor. All other thread specific entries for this key are linked
223 * to this anchor via the 'he_key_list' list head. On return they keyp
224 * will be set to the next available key for the hash table.
227 tsd_hash_add_key(tsd_hash_table_t
*table
, uint_t
*keyp
, dtor_func_t dtor
)
229 tsd_hash_entry_t
*tmp_entry
, *entry
;
232 int keys_checked
= 0;
235 ASSERT3P(table
, !=, NULL
);
237 /* Allocate entry to be used as a destructor for this key */
238 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
242 /* Determine next available key value */
243 spin_lock(&table
->ht_lock
);
245 /* Limited to TSD_KEYS_MAX concurrent unique keys */
246 if (table
->ht_key
++ > TSD_KEYS_MAX
)
249 /* Ensure failure when all TSD_KEYS_MAX keys are in use */
250 if (keys_checked
++ >= TSD_KEYS_MAX
) {
251 spin_unlock(&table
->ht_lock
);
255 tmp_entry
= tsd_hash_search(table
, table
->ht_key
, DTOR_PID
);
258 /* Add destructor entry in to hash table */
259 entry
->he_key
= *keyp
= table
->ht_key
;
260 entry
->he_pid
= DTOR_PID
;
261 entry
->he_dtor
= dtor
;
262 entry
->he_value
= NULL
;
263 INIT_HLIST_NODE(&entry
->he_list
);
264 INIT_LIST_HEAD(&entry
->he_key_list
);
265 INIT_LIST_HEAD(&entry
->he_pid_list
);
267 hash
= hash_long((ulong_t
)*keyp
* (ulong_t
)DTOR_PID
, table
->ht_bits
);
268 bin
= &table
->ht_bins
[hash
];
269 spin_lock(&bin
->hb_lock
);
271 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
273 spin_unlock(&bin
->hb_lock
);
274 spin_unlock(&table
->ht_lock
);
280 * tsd_hash_add_pid - adds a process entry to the hash table
284 * For every process these is a single entry in the hash which is used
285 * as anchor. All other thread specific entries for this process are
286 * linked to this anchor via the 'he_pid_list' list head.
289 tsd_hash_add_pid(tsd_hash_table_t
*table
, pid_t pid
)
291 tsd_hash_entry_t
*entry
;
296 /* Allocate entry to be used as the process reference */
297 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
301 spin_lock(&table
->ht_lock
);
302 entry
->he_key
= PID_KEY
;
304 entry
->he_dtor
= NULL
;
305 entry
->he_value
= NULL
;
306 INIT_HLIST_NODE(&entry
->he_list
);
307 INIT_LIST_HEAD(&entry
->he_key_list
);
308 INIT_LIST_HEAD(&entry
->he_pid_list
);
310 hash
= hash_long((ulong_t
)PID_KEY
* (ulong_t
)pid
, table
->ht_bits
);
311 bin
= &table
->ht_bins
[hash
];
312 spin_lock(&bin
->hb_lock
);
314 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
316 spin_unlock(&bin
->hb_lock
);
317 spin_unlock(&table
->ht_lock
);
323 * tsd_hash_del - delete an entry from hash table, key, and pid lists
329 tsd_hash_del(tsd_hash_table_t
*table
, tsd_hash_entry_t
*entry
)
333 ASSERT(spin_is_locked(&table
->ht_lock
));
334 hlist_del(&entry
->he_list
);
335 list_del_init(&entry
->he_key_list
);
336 list_del_init(&entry
->he_pid_list
);
342 * tsd_hash_table_init - allocate a hash table
343 * @bits: hash table size
345 * A hash table with 2^bits bins will be created, it may not be resized
346 * after the fact and must be free'd with tsd_hash_table_fini().
348 static tsd_hash_table_t
*
349 tsd_hash_table_init(uint_t bits
)
351 tsd_hash_table_t
*table
;
352 int hash
, size
= (1 << bits
);
355 table
= kmem_zalloc(sizeof(tsd_hash_table_t
), KM_SLEEP
);
359 table
->ht_bins
= kmem_zalloc(sizeof(tsd_hash_bin_t
) * size
,
360 KM_SLEEP
| KM_NODEBUG
);
361 if (table
->ht_bins
== NULL
) {
362 kmem_free(table
, sizeof(tsd_hash_table_t
));
366 for (hash
= 0; hash
< size
; hash
++) {
367 spin_lock_init(&table
->ht_bins
[hash
].hb_lock
);
368 INIT_HLIST_HEAD(&table
->ht_bins
[hash
].hb_head
);
371 spin_lock_init(&table
->ht_lock
);
372 table
->ht_bits
= bits
;
379 * tsd_hash_table_fini - free a hash table
382 * Free a hash table allocated by tsd_hash_table_init(). If the hash
383 * table is not empty this function will call the proper destructor for
384 * all remaining entries before freeing the memory used by those entries.
387 tsd_hash_table_fini(tsd_hash_table_t
*table
)
391 tsd_hash_entry_t
*entry
;
395 ASSERT3P(table
, !=, NULL
);
396 spin_lock(&table
->ht_lock
);
397 for (i
= 0, size
= (1 << table
->ht_bits
); i
< size
; i
++) {
398 bin
= &table
->ht_bins
[i
];
399 spin_lock(&bin
->hb_lock
);
400 while (!hlist_empty(&bin
->hb_head
)) {
401 entry
= hlist_entry(bin
->hb_head
.first
,
402 tsd_hash_entry_t
, he_list
);
403 tsd_hash_del(table
, entry
);
404 hlist_add_head(&entry
->he_list
, &work
);
406 spin_unlock(&bin
->hb_lock
);
408 spin_unlock(&table
->ht_lock
);
410 tsd_hash_dtor(&work
);
411 kmem_free(table
->ht_bins
, sizeof(tsd_hash_bin_t
)*(1<<table
->ht_bits
));
412 kmem_free(table
, sizeof(tsd_hash_table_t
));
418 * tsd_set - set thread specific data
420 * @value: value to set
422 * Caller must prevent racing tsd_create() or tsd_destroy(), protected
423 * from racing tsd_get() or tsd_set() because it is thread specific.
424 * This function has been optimized to be fast for the update case.
425 * When setting the tsd initially it will be slower due to additional
426 * required locking and potential memory allocations.
429 tsd_set(uint_t key
, void *value
)
431 tsd_hash_table_t
*table
;
432 tsd_hash_entry_t
*entry
;
437 table
= tsd_hash_table
;
438 pid
= curthread
->pid
;
439 ASSERT3P(table
, !=, NULL
);
441 if ((key
== 0) || (key
> TSD_KEYS_MAX
))
444 /* Entry already exists in hash table update value */
445 entry
= tsd_hash_search(table
, key
, pid
);
447 entry
->he_value
= value
;
451 /* Add a process entry to the hash if not yet exists */
452 entry
= tsd_hash_search(table
, PID_KEY
, pid
);
454 rc
= tsd_hash_add_pid(table
, pid
);
459 rc
= tsd_hash_add(table
, key
, pid
, value
);
462 EXPORT_SYMBOL(tsd_set
);
465 * tsd_get - get thread specific data
468 * Caller must prevent racing tsd_create() or tsd_destroy(). This
469 * implementation is designed to be fast and scalable, it does not
470 * lock the entire table only a single hash bin.
475 tsd_hash_entry_t
*entry
;
478 ASSERT3P(tsd_hash_table
, !=, NULL
);
480 if ((key
== 0) || (key
> TSD_KEYS_MAX
))
483 entry
= tsd_hash_search(tsd_hash_table
, key
, curthread
->pid
);
487 SRETURN(entry
->he_value
);
489 EXPORT_SYMBOL(tsd_get
);
492 * tsd_create - create thread specific data key
493 * @keyp: lookup key address
494 * @dtor: destructor called during tsd_destroy() or tsd_exit()
496 * Provided key must be set to 0 or it assumed to be already in use.
497 * The dtor is allowed to be NULL in which case no additional cleanup
498 * for the data is performed during tsd_destroy() or tsd_exit().
500 * Caller must prevent racing tsd_set() or tsd_get(), this function is
501 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
504 tsd_create(uint_t
*keyp
, dtor_func_t dtor
)
508 ASSERT3P(keyp
, !=, NULL
);
514 (void)tsd_hash_add_key(tsd_hash_table
, keyp
, dtor
);
518 EXPORT_SYMBOL(tsd_create
);
521 * tsd_destroy - destroy thread specific data
522 * @keyp: lookup key address
524 * Destroys the thread specific data on all threads which use this key.
526 * Caller must prevent racing tsd_set() or tsd_get(), this function is
527 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
530 tsd_destroy(uint_t
*keyp
)
533 tsd_hash_table_t
*table
;
534 tsd_hash_entry_t
*dtor_entry
, *entry
;
535 tsd_hash_bin_t
*dtor_entry_bin
, *entry_bin
;
539 table
= tsd_hash_table
;
540 ASSERT3P(table
, !=, NULL
);
542 spin_lock(&table
->ht_lock
);
543 dtor_entry
= tsd_hash_search(table
, *keyp
, DTOR_PID
);
544 if (dtor_entry
== NULL
) {
545 spin_unlock(&table
->ht_lock
);
551 * All threads which use this key must be linked off of the
552 * DTOR_PID entry. They are removed from the hash table and
553 * linked in to a private working list to be destroyed.
555 while (!list_empty(&dtor_entry
->he_key_list
)) {
556 entry
= list_entry(dtor_entry
->he_key_list
.next
,
557 tsd_hash_entry_t
, he_key_list
);
558 ASSERT3U(dtor_entry
->he_key
, ==, entry
->he_key
);
559 ASSERT3P(dtor_entry
->he_dtor
, ==, entry
->he_dtor
);
561 hash
= hash_long((ulong_t
)entry
->he_key
*
562 (ulong_t
)entry
->he_pid
, table
->ht_bits
);
563 entry_bin
= &table
->ht_bins
[hash
];
565 spin_lock(&entry_bin
->hb_lock
);
566 tsd_hash_del(table
, entry
);
567 hlist_add_head(&entry
->he_list
, &work
);
568 spin_unlock(&entry_bin
->hb_lock
);
571 hash
= hash_long((ulong_t
)dtor_entry
->he_key
*
572 (ulong_t
)dtor_entry
->he_pid
, table
->ht_bits
);
573 dtor_entry_bin
= &table
->ht_bins
[hash
];
575 spin_lock(&dtor_entry_bin
->hb_lock
);
576 tsd_hash_del(table
, dtor_entry
);
577 hlist_add_head(&dtor_entry
->he_list
, &work
);
578 spin_unlock(&dtor_entry_bin
->hb_lock
);
579 spin_unlock(&table
->ht_lock
);
581 tsd_hash_dtor(&work
);
586 EXPORT_SYMBOL(tsd_destroy
);
589 * tsd_exit - destroys all thread specific data for this thread
591 * Destroys all the thread specific data for this thread.
593 * Caller must prevent racing tsd_set() or tsd_get(), this function is
594 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
600 tsd_hash_table_t
*table
;
601 tsd_hash_entry_t
*pid_entry
, *entry
;
602 tsd_hash_bin_t
*pid_entry_bin
, *entry_bin
;
606 table
= tsd_hash_table
;
607 ASSERT3P(table
, !=, NULL
);
609 spin_lock(&table
->ht_lock
);
610 pid_entry
= tsd_hash_search(table
, PID_KEY
, curthread
->pid
);
611 if (pid_entry
== NULL
) {
612 spin_unlock(&table
->ht_lock
);
618 * All keys associated with this pid must be linked off of the
619 * PID_KEY entry. They are removed from the hash table and
620 * linked in to a private working list to be destroyed.
623 while (!list_empty(&pid_entry
->he_pid_list
)) {
624 entry
= list_entry(pid_entry
->he_pid_list
.next
,
625 tsd_hash_entry_t
, he_pid_list
);
626 ASSERT3U(pid_entry
->he_pid
, ==, entry
->he_pid
);
628 hash
= hash_long((ulong_t
)entry
->he_key
*
629 (ulong_t
)entry
->he_pid
, table
->ht_bits
);
630 entry_bin
= &table
->ht_bins
[hash
];
632 spin_lock(&entry_bin
->hb_lock
);
633 tsd_hash_del(table
, entry
);
634 hlist_add_head(&entry
->he_list
, &work
);
635 spin_unlock(&entry_bin
->hb_lock
);
638 hash
= hash_long((ulong_t
)pid_entry
->he_key
*
639 (ulong_t
)pid_entry
->he_pid
, table
->ht_bits
);
640 pid_entry_bin
= &table
->ht_bins
[hash
];
642 spin_lock(&pid_entry_bin
->hb_lock
);
643 tsd_hash_del(table
, pid_entry
);
644 hlist_add_head(&pid_entry
->he_list
, &work
);
645 spin_unlock(&pid_entry_bin
->hb_lock
);
646 spin_unlock(&table
->ht_lock
);
648 tsd_hash_dtor(&work
);
652 EXPORT_SYMBOL(tsd_exit
);
659 tsd_hash_table
= tsd_hash_table_init(TSD_HASH_TABLE_BITS_DEFAULT
);
660 if (tsd_hash_table
== NULL
)
670 tsd_hash_table_fini(tsd_hash_table
);
671 tsd_hash_table
= NULL
;