Changes in kernel/generic/src/synch/futex.c [9d58539:3ac5086] in mainline
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/synch/futex.c
r9d58539 r3ac5086 1 1 /* 2 2 * Copyright (c) 2006 Jakub Jermar 3 * Copyright (c) 2012 Adam Hraska 3 4 * All rights reserved. 4 5 * … … 34 35 * @file 35 36 * @brief Kernel backend for futexes. 37 * 38 * Kernel futex objects are stored in a global hash table futex_ht 39 * where the physical address of the futex variable (futex_t.paddr) 40 * is used as the lookup key. As a result multiple address spaces 41 * may share the same futex variable. 42 * 43 * A kernel futex object is created the first time a task accesses 44 * the futex (having a futex variable at a physical address not 45 * encountered before). Futex object's lifetime is governed by 46 * a reference count that represents the number of all the different 47 * user space virtual addresses from all tasks that map to the 48 * physical address of the futex variable. A futex object is freed 49 * when the last task having accessed the futex exits. 50 * 51 * Each task keeps track of the futex objects it accessed in a list 52 * of pointers (futex_ptr_t, task->futex_list) to the different futex 53 * objects. 54 * 55 * To speed up translation of futex variables' virtual addresses 56 * to their physical addresses, futex pointers accessed by the 57 * task are furthermore stored in a concurrent hash table (CHT, 58 * task->futexes->ht). A single lookup without locks or accesses 59 * to the page table translates a futex variable's virtual address 60 * into its futex kernel object. 36 61 */ 37 62 … … 39 64 #include <synch/mutex.h> 40 65 #include <synch/spinlock.h> 66 #include <synch/rcu.h> 41 67 #include <mm/frame.h> 42 68 #include <mm/page.h> … … 46 72 #include <genarch/mm/page_pt.h> 47 73 #include <genarch/mm/page_ht.h> 74 #include <adt/cht.h> 48 75 #include <adt/hash_table.h> 49 76 #include <adt/list.h> … … 52 79 #include <panic.h> 53 80 #include <errno.h> 54 #include <print.h>55 81 56 82 #define FUTEX_HT_SIZE 1024 /* keep it a power of 2 */ 57 83 58 static void futex_initialize(futex_t *futex); 59 60 static futex_t *futex_find(uintptr_t paddr); 84 /** Task specific pointer to a global kernel futex object. */ 85 typedef struct futex_ptr { 86 /** CHT link. */ 87 cht_link_t cht_link; 88 /** List of all futex pointers used by the task. */ 89 link_t all_link; 90 /** Kernel futex object. */ 91 futex_t *futex; 92 /** User space virtual address of the futex variable in the task. */ 93 uintptr_t uaddr; 94 } futex_ptr_t; 95 96 97 static void destroy_task_cache(work_t *work); 98 99 static void futex_initialize(futex_t *futex, uintptr_t paddr); 100 static void futex_add_ref(futex_t *futex); 101 static void futex_release_ref(futex_t *futex); 102 static void futex_release_ref_locked(futex_t *futex); 103 104 static futex_t *get_futex(uintptr_t uaddr); 105 static futex_t *find_cached_futex(uintptr_t uaddr); 106 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr); 107 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *phys_addr); 108 61 109 static size_t futex_ht_hash(sysarg_t *key); 62 110 static bool futex_ht_compare(sysarg_t *key, size_t keys, link_t *item); 63 111 static void futex_ht_remove_callback(link_t *item); 64 112 65 /** 66 * Mutex protecting global futex hash table. 67 * It is also used to serialize access to all futex_t structures. 68 * Must be acquired before the task futex B+tree lock. 113 static size_t task_fut_ht_hash(const cht_link_t *link); 114 static size_t task_fut_ht_key_hash(void *key); 115 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2); 116 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item); 117 118 119 /** Mutex protecting the global futex hash table. 120 * 121 * Acquire task specific TASK->futex_list_lock before this mutex. 69 122 */ 70 123 static mutex_t futex_ht_lock; 71 124 72 /** Futex hash table. */ 125 /** Global kernel futex hash table. Lock futex_ht_lock before accessing. 126 * 127 * Physical address of the futex variable is the lookup key. 128 */ 73 129 static hash_table_t futex_ht; 74 130 75 /** Futex hash table operations. */131 /** Global kernel futex hash table operations. */ 76 132 static hash_table_operations_t futex_ht_ops = { 77 133 .hash = futex_ht_hash, … … 80 136 }; 81 137 138 /** Task futex cache CHT operations. */ 139 static cht_ops_t task_futex_ht_ops = { 140 .hash = task_fut_ht_hash, 141 .key_hash = task_fut_ht_key_hash, 142 .equal = task_fut_ht_equal, 143 .key_equal = task_fut_ht_key_equal, 144 .remove_callback = NULL 145 }; 146 82 147 /** Initialize futex subsystem. */ 83 148 void futex_init(void) … … 87 152 } 88 153 89 /** Initialize kernel futex structure. 90 * 91 * @param futex Kernel futex structure. 92 */ 93 void futex_initialize(futex_t *futex) 154 /** Initializes the futex structures for the new task. */ 155 void futex_task_init(struct task *task) 156 { 157 task->futexes = malloc(sizeof(struct futex_cache), 0); 158 159 cht_create(&task->futexes->ht, 0, 0, 0, true, &task_futex_ht_ops); 160 161 list_initialize(&task->futexes->list); 162 mutex_initialize(&task->futexes->list_lock, MUTEX_PASSIVE); 163 } 164 165 /** Destroys the futex structures for the dying task. */ 166 void futex_task_deinit(task_t *task) 167 { 168 /* Interrupts are disabled so we must not block (cannot run cht_destroy). */ 169 if (interrupts_disabled()) { 170 /* Invoke the blocking cht_destroy in the background. */ 171 workq_global_enqueue_noblock(&task->futexes->destroy_work, 172 destroy_task_cache); 173 } else { 174 /* We can block. Invoke cht_destroy in this thread. */ 175 destroy_task_cache(&task->futexes->destroy_work); 176 } 177 } 178 179 /** Deallocates a task's CHT futex cache (must already be empty). */ 180 static void destroy_task_cache(work_t *work) 181 { 182 struct futex_cache *cache = 183 member_to_inst(work, struct futex_cache, destroy_work); 184 185 /* 186 * Destroy the cache before manually freeing items of the cache in case 187 * table resize is in progress. 188 */ 189 cht_destroy_unsafe(&cache->ht); 190 191 /* Manually free futex_ptr cache items. */ 192 list_foreach_safe(cache->list, cur_link, next_link) { 193 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link); 194 195 list_remove(cur_link); 196 free(fut_ptr); 197 } 198 199 free(cache); 200 } 201 202 /** Remove references from futexes known to the current task. */ 203 void futex_task_cleanup(void) 204 { 205 struct futex_cache *futexes = TASK->futexes; 206 207 /* All threads of this task have terminated. This is the last thread. */ 208 mutex_lock(&futexes->list_lock); 209 210 list_foreach_safe(futexes->list, cur_link, next_link) { 211 futex_ptr_t *fut_ptr = member_to_inst(cur_link, futex_ptr_t, all_link); 212 213 /* 214 * The function is free to free the futex. All other threads of this 215 * task have already terminated, so they have also definitely 216 * exited their CHT futex cache protecting rcu reader sections. 217 * Moreover release_ref() only frees the futex if this is the 218 * last task referencing the futex. Therefore, only threads 219 * of this task may have referenced the futex if it is to be freed. 220 */ 221 futex_release_ref_locked(fut_ptr->futex); 222 } 223 224 mutex_unlock(&futexes->list_lock); 225 } 226 227 228 /** Initialize the kernel futex structure. 229 * 230 * @param futex Kernel futex structure. 231 * @param paddr Physical address of the futex variable. 232 */ 233 static void futex_initialize(futex_t *futex, uintptr_t paddr) 94 234 { 95 235 waitq_initialize(&futex->wq); 96 236 link_initialize(&futex->ht_link); 97 futex->paddr = 0;237 futex->paddr = paddr; 98 238 futex->refcount = 1; 239 } 240 241 /** Increments the counter of tasks referencing the futex. */ 242 static void futex_add_ref(futex_t *futex) 243 { 244 ASSERT(mutex_locked(&futex_ht_lock)); 245 ASSERT(0 < futex->refcount); 246 ++futex->refcount; 247 } 248 249 /** Decrements the counter of tasks referencing the futex. May free the futex.*/ 250 static void futex_release_ref(futex_t *futex) 251 { 252 ASSERT(mutex_locked(&futex_ht_lock)); 253 ASSERT(0 < futex->refcount); 254 255 --futex->refcount; 256 257 if (0 == futex->refcount) { 258 hash_table_remove(&futex_ht, &futex->paddr, 1); 259 } 260 } 261 262 /** Decrements the counter of tasks referencing the futex. May free the futex.*/ 263 static void futex_release_ref_locked(futex_t *futex) 264 { 265 mutex_lock(&futex_ht_lock); 266 futex_release_ref(futex); 267 mutex_unlock(&futex_ht_lock); 268 } 269 270 /** Returns a futex for the virtual address @a uaddr (or creates one). */ 271 static futex_t *get_futex(uintptr_t uaddr) 272 { 273 futex_t *futex = find_cached_futex(uaddr); 274 275 if (futex) 276 return futex; 277 278 uintptr_t paddr; 279 280 if (!find_futex_paddr(uaddr, &paddr)) 281 return 0; 282 283 return get_and_cache_futex(paddr, uaddr); 284 } 285 286 287 /** Finds the physical address of the futex variable. */ 288 static bool find_futex_paddr(uintptr_t uaddr, uintptr_t *paddr) 289 { 290 page_table_lock(AS, true); 291 292 bool found = false; 293 pte_t *t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false); 294 295 if (t && PTE_VALID(t) && PTE_PRESENT(t)) { 296 found = true; 297 *paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE)); 298 } 299 300 page_table_unlock(AS, true); 301 302 return found; 303 } 304 305 /** Returns the futex cached in this task with the virtual address uaddr. */ 306 static futex_t *find_cached_futex(uintptr_t uaddr) 307 { 308 cht_read_lock(); 309 310 futex_t *futex; 311 cht_link_t *futex_ptr_link = cht_find_lazy(&TASK->futexes->ht, &uaddr); 312 313 if (futex_ptr_link) { 314 futex_ptr_t *futex_ptr 315 = member_to_inst(futex_ptr_link, futex_ptr_t, cht_link); 316 317 futex = futex_ptr->futex; 318 } else { 319 futex = NULL; 320 } 321 322 cht_read_unlock(); 323 324 return futex; 325 } 326 327 328 /** 329 * Returns a kernel futex for the physical address @a phys_addr and caches 330 * it in this task under the virtual address @a uaddr (if not already cached). 331 */ 332 static futex_t *get_and_cache_futex(uintptr_t phys_addr, uintptr_t uaddr) 333 { 334 futex_t *futex = malloc(sizeof(futex_t), 0); 335 336 /* 337 * Find the futex object in the global futex table (or insert it 338 * if it is not present). 339 */ 340 mutex_lock(&futex_ht_lock); 341 342 link_t *fut_link = hash_table_find(&futex_ht, &phys_addr); 343 344 if (fut_link) { 345 free(futex); 346 futex = member_to_inst(fut_link, futex_t, ht_link); 347 futex_add_ref(futex); 348 } else { 349 futex_initialize(futex, phys_addr); 350 hash_table_insert(&futex_ht, &phys_addr, &futex->ht_link); 351 } 352 353 mutex_unlock(&futex_ht_lock); 354 355 /* 356 * Cache the link to the futex object for this task. 357 */ 358 futex_ptr_t *fut_ptr = malloc(sizeof(futex_ptr_t), 0); 359 cht_link_t *dup_link; 360 361 fut_ptr->futex = futex; 362 fut_ptr->uaddr = uaddr; 363 364 cht_read_lock(); 365 366 /* Cache the mapping from the virtual address to the futex for this task. */ 367 if (cht_insert_unique(&TASK->futexes->ht, &fut_ptr->cht_link, &dup_link)) { 368 mutex_lock(&TASK->futexes->list_lock); 369 list_append(&fut_ptr->all_link, &TASK->futexes->list); 370 mutex_unlock(&TASK->futexes->list_lock); 371 } else { 372 /* Another thread of this task beat us to it. Use that mapping instead.*/ 373 free(fut_ptr); 374 futex_release_ref_locked(futex); 375 376 futex_ptr_t *dup = member_to_inst(dup_link, futex_ptr_t, cht_link); 377 futex = dup->futex; 378 } 379 380 cht_read_unlock(); 381 382 return futex; 99 383 } 100 384 … … 109 393 sysarg_t sys_futex_sleep(uintptr_t uaddr) 110 394 { 111 futex_t *futex; 112 uintptr_t paddr; 113 pte_t *t; 114 int rc; 115 116 /* 117 * Find physical address of futex counter. 118 */ 119 page_table_lock(AS, true); 120 t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false); 121 if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) { 122 page_table_unlock(AS, true); 395 futex_t *futex = get_futex(uaddr); 396 397 if (!futex) 123 398 return (sysarg_t) ENOENT; 124 }125 paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE));126 page_table_unlock(AS, true);127 128 futex = futex_find(paddr);129 399 130 400 #ifdef CONFIG_UDEBUG 131 401 udebug_stoppable_begin(); 132 402 #endif 133 rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE);403 int rc = waitq_sleep_timeout(&futex->wq, 0, SYNCH_FLAGS_INTERRUPTIBLE); 134 404 #ifdef CONFIG_UDEBUG 135 405 udebug_stoppable_end(); … … 146 416 sysarg_t sys_futex_wakeup(uintptr_t uaddr) 147 417 { 148 futex_t *futex; 149 uintptr_t paddr; 150 pte_t *t; 151 152 /* 153 * Find physical address of futex counter. 154 */ 155 page_table_lock(AS, true); 156 t = page_mapping_find(AS, ALIGN_DOWN(uaddr, PAGE_SIZE), false); 157 if (!t || !PTE_VALID(t) || !PTE_PRESENT(t)) { 158 page_table_unlock(AS, true); 418 futex_t *futex = get_futex(uaddr); 419 420 if (futex) { 421 waitq_wakeup(&futex->wq, WAKEUP_FIRST); 422 return 0; 423 } else { 159 424 return (sysarg_t) ENOENT; 160 425 } 161 paddr = PTE_GET_FRAME(t) + (uaddr - ALIGN_DOWN(uaddr, PAGE_SIZE)); 162 page_table_unlock(AS, true); 163 164 futex = futex_find(paddr); 165 166 waitq_wakeup(&futex->wq, WAKEUP_FIRST); 167 168 return 0; 169 } 170 171 /** Find kernel address of the futex structure corresponding to paddr. 172 * 173 * If the structure does not exist already, a new one is created. 174 * 175 * @param paddr Physical address of the userspace futex counter. 176 * 177 * @return Address of the kernel futex structure. 178 */ 179 futex_t *futex_find(uintptr_t paddr) 180 { 181 link_t *item; 182 futex_t *futex; 183 btree_node_t *leaf; 184 185 /* 186 * Find the respective futex structure 187 * or allocate new one if it does not exist already. 188 */ 189 mutex_lock(&futex_ht_lock); 190 item = hash_table_find(&futex_ht, &paddr); 191 if (item) { 192 futex = hash_table_get_instance(item, futex_t, ht_link); 193 194 /* 195 * See if the current task knows this futex. 196 */ 197 mutex_lock(&TASK->futexes_lock); 198 if (!btree_search(&TASK->futexes, paddr, &leaf)) { 199 /* 200 * The futex is new to the current task. 201 * Upgrade its reference count and put it to the 202 * current task's B+tree of known futexes. 203 */ 204 futex->refcount++; 205 btree_insert(&TASK->futexes, paddr, futex, leaf); 206 } 207 mutex_unlock(&TASK->futexes_lock); 208 } else { 209 futex = (futex_t *) malloc(sizeof(futex_t), 0); 210 futex_initialize(futex); 211 futex->paddr = paddr; 212 hash_table_insert(&futex_ht, &paddr, &futex->ht_link); 213 214 /* 215 * This is the first task referencing the futex. 216 * It can be directly inserted into its 217 * B+tree of known futexes. 218 */ 219 mutex_lock(&TASK->futexes_lock); 220 btree_insert(&TASK->futexes, paddr, futex, NULL); 221 mutex_unlock(&TASK->futexes_lock); 222 223 } 224 mutex_unlock(&futex_ht_lock); 225 226 return futex; 227 } 426 } 427 228 428 229 429 /** Compute hash index into futex hash table. … … 268 468 } 269 469 270 /** Remove references from futexes known to the current task. */ 271 void futex_cleanup(void) 272 { 273 mutex_lock(&futex_ht_lock); 274 mutex_lock(&TASK->futexes_lock); 275 276 list_foreach(TASK->futexes.leaf_list, cur) { 277 btree_node_t *node; 278 unsigned int i; 279 280 node = list_get_instance(cur, btree_node_t, leaf_link); 281 for (i = 0; i < node->keys; i++) { 282 futex_t *ftx; 283 uintptr_t paddr = node->key[i]; 284 285 ftx = (futex_t *) node->value[i]; 286 if (--ftx->refcount == 0) 287 hash_table_remove(&futex_ht, &paddr, 1); 288 } 289 } 290 291 mutex_unlock(&TASK->futexes_lock); 292 mutex_unlock(&futex_ht_lock); 293 } 470 /* 471 * Operations of a task's CHT that caches mappings of futex user space 472 * virtual addresses to kernel futex objects. 473 */ 474 475 static size_t task_fut_ht_hash(const cht_link_t *link) 476 { 477 const futex_ptr_t *fut_ptr = member_to_inst(link, futex_ptr_t, cht_link); 478 return fut_ptr->uaddr; 479 } 480 481 static size_t task_fut_ht_key_hash(void *key) 482 { 483 return *(uintptr_t*)key; 484 } 485 486 static bool task_fut_ht_equal(const cht_link_t *item1, const cht_link_t *item2) 487 { 488 const futex_ptr_t *fut_ptr1 = member_to_inst(item1, futex_ptr_t, cht_link); 489 const futex_ptr_t *fut_ptr2 = member_to_inst(item2, futex_ptr_t, cht_link); 490 491 return fut_ptr1->uaddr == fut_ptr2->uaddr; 492 } 493 494 static bool task_fut_ht_key_equal(void *key, const cht_link_t *item) 495 { 496 const futex_ptr_t *fut_ptr = member_to_inst(item, futex_ptr_t, cht_link); 497 uintptr_t uaddr = *(uintptr_t*)key; 498 499 return fut_ptr->uaddr == uaddr; 500 } 501 294 502 295 503 /** @}
Note:
See TracChangeset
for help on using the changeset viewer.