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://github.com/behlendorf/spl/>.
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_entry(entry
, node
, &bin
->hb_head
, he_list
) {
117 if ((entry
->he_key
== key
) && (entry
->he_pid
== pid
)) {
118 spin_unlock(&bin
->hb_lock
);
123 spin_unlock(&bin
->hb_lock
);
128 * tsd_hash_dtor - call the destructor and free all entries on the list
129 * @work: list of hash entries
131 * For a list of entries which have all already been removed from the
132 * hash call their registered destructor then free the associated memory.
135 tsd_hash_dtor(struct hlist_head
*work
)
137 tsd_hash_entry_t
*entry
;
140 while (!hlist_empty(work
)) {
141 entry
= hlist_entry(work
->first
, tsd_hash_entry_t
, he_list
);
142 hlist_del(&entry
->he_list
);
144 if (entry
->he_dtor
&& entry
->he_pid
!= DTOR_PID
)
145 entry
->he_dtor(entry
->he_value
);
147 kmem_free(entry
, sizeof(tsd_hash_entry_t
));
154 * tsd_hash_add - adds an entry to hash table
159 * The caller is responsible for ensuring the unique key/pid do not
160 * already exist in the hash table. This possible because all entries
161 * are thread specific thus a concurrent thread will never attempt to
162 * add this key/pid. Because multiple bins must be checked to add
163 * links to the dtor and pid entries the entire table is locked.
166 tsd_hash_add(tsd_hash_table_t
*table
, uint_t key
, pid_t pid
, void *value
)
168 tsd_hash_entry_t
*entry
, *dtor_entry
, *pid_entry
;
174 ASSERT3P(tsd_hash_search(table
, key
, pid
), ==, NULL
);
176 /* New entry allocate structure, set value, and add to hash */
177 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
183 entry
->he_value
= value
;
184 INIT_HLIST_NODE(&entry
->he_list
);
185 INIT_LIST_HEAD(&entry
->he_key_list
);
186 INIT_LIST_HEAD(&entry
->he_pid_list
);
188 spin_lock(&table
->ht_lock
);
190 /* Destructor entry must exist for all valid keys */
191 dtor_entry
= tsd_hash_search(table
, entry
->he_key
, DTOR_PID
);
192 ASSERT3P(dtor_entry
, !=, NULL
);
193 entry
->he_dtor
= dtor_entry
->he_dtor
;
195 /* Process entry must exist for all valid processes */
196 pid_entry
= tsd_hash_search(table
, PID_KEY
, entry
->he_pid
);
197 ASSERT3P(pid_entry
, !=, NULL
);
199 hash
= hash_long((ulong_t
)key
* (ulong_t
)pid
, table
->ht_bits
);
200 bin
= &table
->ht_bins
[hash
];
201 spin_lock(&bin
->hb_lock
);
203 /* Add to the hash, key, and pid lists */
204 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
205 list_add(&entry
->he_key_list
, &dtor_entry
->he_key_list
);
206 list_add(&entry
->he_pid_list
, &pid_entry
->he_pid_list
);
208 spin_unlock(&bin
->hb_lock
);
209 spin_unlock(&table
->ht_lock
);
215 * tsd_hash_add_key - adds a destructor entry to the hash table
218 * @dtor: key destructor
220 * For every unique key there is a single entry in the hash which is used
221 * as anchor. All other thread specific entries for this key are linked
222 * to this anchor via the 'he_key_list' list head. On return they keyp
223 * will be set to the next available key for the hash table.
226 tsd_hash_add_key(tsd_hash_table_t
*table
, uint_t
*keyp
, dtor_func_t dtor
)
228 tsd_hash_entry_t
*tmp_entry
, *entry
;
231 int keys_checked
= 0;
234 ASSERT3P(table
, !=, NULL
);
236 /* Allocate entry to be used as a destructor for this key */
237 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
241 /* Determine next available key value */
242 spin_lock(&table
->ht_lock
);
244 /* Limited to TSD_KEYS_MAX concurrent unique keys */
245 if (table
->ht_key
++ > TSD_KEYS_MAX
)
248 /* Ensure failure when all TSD_KEYS_MAX keys are in use */
249 if (keys_checked
++ >= TSD_KEYS_MAX
) {
250 spin_unlock(&table
->ht_lock
);
254 tmp_entry
= tsd_hash_search(table
, table
->ht_key
, DTOR_PID
);
257 /* Add destructor entry in to hash table */
258 entry
->he_key
= *keyp
= table
->ht_key
;
259 entry
->he_pid
= DTOR_PID
;
260 entry
->he_dtor
= dtor
;
261 entry
->he_value
= NULL
;
262 INIT_HLIST_NODE(&entry
->he_list
);
263 INIT_LIST_HEAD(&entry
->he_key_list
);
264 INIT_LIST_HEAD(&entry
->he_pid_list
);
266 hash
= hash_long((ulong_t
)*keyp
* (ulong_t
)DTOR_PID
, table
->ht_bits
);
267 bin
= &table
->ht_bins
[hash
];
268 spin_lock(&bin
->hb_lock
);
270 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
272 spin_unlock(&bin
->hb_lock
);
273 spin_unlock(&table
->ht_lock
);
279 * tsd_hash_add_pid - adds a process entry to the hash table
283 * For every process these is a single entry in the hash which is used
284 * as anchor. All other thread specific entries for this process are
285 * linked to this anchor via the 'he_pid_list' list head.
288 tsd_hash_add_pid(tsd_hash_table_t
*table
, pid_t pid
)
290 tsd_hash_entry_t
*entry
;
295 /* Allocate entry to be used as the process reference */
296 entry
= kmem_alloc(sizeof(tsd_hash_entry_t
), KM_PUSHPAGE
);
300 spin_lock(&table
->ht_lock
);
301 entry
->he_key
= PID_KEY
;
303 entry
->he_dtor
= NULL
;
304 entry
->he_value
= NULL
;
305 INIT_HLIST_NODE(&entry
->he_list
);
306 INIT_LIST_HEAD(&entry
->he_key_list
);
307 INIT_LIST_HEAD(&entry
->he_pid_list
);
309 hash
= hash_long((ulong_t
)PID_KEY
* (ulong_t
)pid
, table
->ht_bits
);
310 bin
= &table
->ht_bins
[hash
];
311 spin_lock(&bin
->hb_lock
);
313 hlist_add_head(&entry
->he_list
, &bin
->hb_head
);
315 spin_unlock(&bin
->hb_lock
);
316 spin_unlock(&table
->ht_lock
);
322 * tsd_hash_del - delete an entry from hash table, key, and pid lists
328 tsd_hash_del(tsd_hash_table_t
*table
, tsd_hash_entry_t
*entry
)
332 ASSERT(spin_is_locked(&table
->ht_lock
));
333 hlist_del(&entry
->he_list
);
334 list_del_init(&entry
->he_key_list
);
335 list_del_init(&entry
->he_pid_list
);
341 * tsd_hash_table_init - allocate a hash table
342 * @bits: hash table size
344 * A hash table with 2^bits bins will be created, it may not be resized
345 * after the fact and must be free'd with tsd_hash_table_fini().
347 static tsd_hash_table_t
*
348 tsd_hash_table_init(uint_t bits
)
350 tsd_hash_table_t
*table
;
351 int hash
, size
= (1 << bits
);
354 table
= kmem_zalloc(sizeof(tsd_hash_table_t
), KM_SLEEP
);
358 table
->ht_bins
= kmem_zalloc(sizeof(tsd_hash_bin_t
) * size
,
359 KM_SLEEP
| KM_NODEBUG
);
360 if (table
->ht_bins
== NULL
) {
361 kmem_free(table
, sizeof(tsd_hash_table_t
));
365 for (hash
= 0; hash
< size
; hash
++) {
366 spin_lock_init(&table
->ht_bins
[hash
].hb_lock
);
367 INIT_HLIST_HEAD(&table
->ht_bins
[hash
].hb_head
);
370 spin_lock_init(&table
->ht_lock
);
371 table
->ht_bits
= bits
;
378 * tsd_hash_table_fini - free a hash table
381 * Free a hash table allocated by tsd_hash_table_init(). If the hash
382 * table is not empty this function will call the proper destructor for
383 * all remaining entries before freeing the memory used by those entries.
386 tsd_hash_table_fini(tsd_hash_table_t
*table
)
390 tsd_hash_entry_t
*entry
;
394 ASSERT3P(table
, !=, NULL
);
395 spin_lock(&table
->ht_lock
);
396 for (i
= 0, size
= (1 << table
->ht_bits
); i
< size
; i
++) {
397 bin
= &table
->ht_bins
[i
];
398 spin_lock(&bin
->hb_lock
);
399 while (!hlist_empty(&bin
->hb_head
)) {
400 entry
= hlist_entry(bin
->hb_head
.first
,
401 tsd_hash_entry_t
, he_list
);
402 tsd_hash_del(table
, entry
);
403 hlist_add_head(&entry
->he_list
, &work
);
405 spin_unlock(&bin
->hb_lock
);
407 spin_unlock(&table
->ht_lock
);
409 tsd_hash_dtor(&work
);
410 kmem_free(table
->ht_bins
, sizeof(tsd_hash_bin_t
)*(1<<table
->ht_bits
));
411 kmem_free(table
, sizeof(tsd_hash_table_t
));
417 * tsd_set - set thread specific data
419 * @value: value to set
421 * Caller must prevent racing tsd_create() or tsd_destroy(), protected
422 * from racing tsd_get() or tsd_set() because it is thread specific.
423 * This function has been optimized to be fast for the update case.
424 * When setting the tsd initially it will be slower due to additional
425 * required locking and potential memory allocations.
428 tsd_set(uint_t key
, void *value
)
430 tsd_hash_table_t
*table
;
431 tsd_hash_entry_t
*entry
;
436 table
= tsd_hash_table
;
437 pid
= curthread
->pid
;
438 ASSERT3P(table
, !=, NULL
);
440 if ((key
== 0) || (key
> TSD_KEYS_MAX
))
443 /* Entry already exists in hash table update value */
444 entry
= tsd_hash_search(table
, key
, pid
);
446 entry
->he_value
= value
;
450 /* Add a process entry to the hash if not yet exists */
451 entry
= tsd_hash_search(table
, PID_KEY
, pid
);
453 rc
= tsd_hash_add_pid(table
, pid
);
458 rc
= tsd_hash_add(table
, key
, pid
, value
);
461 EXPORT_SYMBOL(tsd_set
);
464 * tsd_get - get thread specific data
467 * Caller must prevent racing tsd_create() or tsd_destroy(). This
468 * implementation is designed to be fast and scalable, it does not
469 * lock the entire table only a single hash bin.
474 tsd_hash_entry_t
*entry
;
477 ASSERT3P(tsd_hash_table
, !=, NULL
);
479 if ((key
== 0) || (key
> TSD_KEYS_MAX
))
482 entry
= tsd_hash_search(tsd_hash_table
, key
, curthread
->pid
);
486 SRETURN(entry
->he_value
);
488 EXPORT_SYMBOL(tsd_get
);
491 * tsd_create - create thread specific data key
492 * @keyp: lookup key address
493 * @dtor: destructor called during tsd_destroy() or tsd_exit()
495 * Provided key must be set to 0 or it assumed to be already in use.
496 * The dtor is allowed to be NULL in which case no additional cleanup
497 * for the data is performed during tsd_destroy() or tsd_exit().
499 * Caller must prevent racing tsd_set() or tsd_get(), this function is
500 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
503 tsd_create(uint_t
*keyp
, dtor_func_t dtor
)
507 ASSERT3P(keyp
, !=, NULL
);
513 (void)tsd_hash_add_key(tsd_hash_table
, keyp
, dtor
);
517 EXPORT_SYMBOL(tsd_create
);
520 * tsd_destroy - destroy thread specific data
521 * @keyp: lookup key address
523 * Destroys the thread specific data on all threads which use this key.
525 * Caller must prevent racing tsd_set() or tsd_get(), this function is
526 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
529 tsd_destroy(uint_t
*keyp
)
532 tsd_hash_table_t
*table
;
533 tsd_hash_entry_t
*dtor_entry
, *entry
;
536 table
= tsd_hash_table
;
537 ASSERT3P(table
, !=, NULL
);
539 spin_lock(&table
->ht_lock
);
540 dtor_entry
= tsd_hash_search(table
, *keyp
, DTOR_PID
);
541 if (dtor_entry
== NULL
) {
542 spin_unlock(&table
->ht_lock
);
548 * All threads which use this key must be linked off of the
549 * DTOR_PID entry. They are removed from the hash table and
550 * linked in to a private working list to be destroyed.
552 while (!list_empty(&dtor_entry
->he_key_list
)) {
553 entry
= list_entry(dtor_entry
->he_key_list
.next
,
554 tsd_hash_entry_t
, he_key_list
);
555 ASSERT3U(dtor_entry
->he_key
, ==, entry
->he_key
);
556 ASSERT3P(dtor_entry
->he_dtor
, ==, entry
->he_dtor
);
557 tsd_hash_del(table
, entry
);
558 hlist_add_head(&entry
->he_list
, &work
);
561 tsd_hash_del(table
, dtor_entry
);
562 hlist_add_head(&dtor_entry
->he_list
, &work
);
563 spin_unlock(&table
->ht_lock
);
565 tsd_hash_dtor(&work
);
570 EXPORT_SYMBOL(tsd_destroy
);
573 * tsd_exit - destroys all thread specific data for this thread
575 * Destroys all the thread specific data for this thread.
577 * Caller must prevent racing tsd_set() or tsd_get(), this function is
578 * safe from racing tsd_create(), tsd_destroy(), and tsd_exit().
584 tsd_hash_table_t
*table
;
585 tsd_hash_entry_t
*pid_entry
, *entry
;
588 table
= tsd_hash_table
;
589 ASSERT3P(table
, !=, NULL
);
591 spin_lock(&table
->ht_lock
);
592 pid_entry
= tsd_hash_search(table
, PID_KEY
, curthread
->pid
);
593 if (pid_entry
== NULL
) {
594 spin_unlock(&table
->ht_lock
);
600 * All keys associated with this pid must be linked off of the
601 * PID_KEY entry. They are removed from the hash table and
602 * linked in to a private working to be destroyed.
604 while (!list_empty(&pid_entry
->he_pid_list
)) {
605 entry
= list_entry(pid_entry
->he_pid_list
.next
,
606 tsd_hash_entry_t
, he_pid_list
);
607 ASSERT3U(pid_entry
->he_pid
, ==, entry
->he_pid
);
608 tsd_hash_del(table
, entry
);
609 hlist_add_head(&entry
->he_list
, &work
);
612 tsd_hash_del(table
, pid_entry
);
613 hlist_add_head(&pid_entry
->he_list
, &work
);
614 spin_unlock(&table
->ht_lock
);
616 tsd_hash_dtor(&work
);
620 EXPORT_SYMBOL(tsd_exit
);
627 tsd_hash_table
= tsd_hash_table_init(TSD_HASH_TABLE_BITS_DEFAULT
);
628 if (tsd_hash_table
== NULL
)
638 tsd_hash_table_fini(tsd_hash_table
);
639 tsd_hash_table
= NULL
;