1 /*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2021 Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 * conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 * of conditions and the following disclaimer in the documentation and/or other materials
13 * provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #include "los_futex_pri.h"
33 #include "los_exc.h"
34 #include "los_hash.h"
35 #include "los_init.h"
36 #include "los_process_pri.h"
37 #include "los_sched_pri.h"
38 #include "los_sys_pri.h"
39 #include "los_mp.h"
40 #include "los_mux_pri.h"
41 #include "user_copy.h"
42
43
44 #ifdef LOSCFG_KERNEL_VM
45
46 #define OS_FUTEX_FROM_FUTEXLIST(ptr) LOS_DL_LIST_ENTRY(ptr, FutexNode, futexList)
47 #define OS_FUTEX_FROM_QUEUELIST(ptr) LOS_DL_LIST_ENTRY(ptr, FutexNode, queueList)
48 #define OS_FUTEX_KEY_BASE USER_ASPACE_BASE
49 #define OS_FUTEX_KEY_MAX (USER_ASPACE_BASE + USER_ASPACE_SIZE)
50
51 /* private: 0~63 hash index_num
52 * shared: 64~79 hash index_num */
53 #define FUTEX_INDEX_PRIVATE_MAX 64
54 #define FUTEX_INDEX_SHARED_MAX 16
55 #define FUTEX_INDEX_MAX (FUTEX_INDEX_PRIVATE_MAX + FUTEX_INDEX_SHARED_MAX)
56
57 #define FUTEX_INDEX_SHARED_POS FUTEX_INDEX_PRIVATE_MAX
58 #define FUTEX_HASH_PRIVATE_MASK (FUTEX_INDEX_PRIVATE_MAX - 1)
59 #define FUTEX_HASH_SHARED_MASK (FUTEX_INDEX_SHARED_MAX - 1)
60
61 typedef struct {
62 LosMux listLock;
63 LOS_DL_LIST lockList;
64 } FutexHash;
65
66 FutexHash g_futexHash[FUTEX_INDEX_MAX];
67
OsFutexLock(LosMux * lock)68 STATIC INT32 OsFutexLock(LosMux *lock)
69 {
70 UINT32 ret = LOS_MuxLock(lock, LOS_WAIT_FOREVER);
71 if (ret != LOS_OK) {
72 PRINT_ERR("Futex lock failed! ERROR: 0x%x!\n", ret);
73 return LOS_EINVAL;
74 }
75 return LOS_OK;
76 }
77
OsFutexUnlock(LosMux * lock)78 STATIC INT32 OsFutexUnlock(LosMux *lock)
79 {
80 UINT32 ret = LOS_MuxUnlock(lock);
81 if (ret != LOS_OK) {
82 PRINT_ERR("Futex unlock failed! ERROR: 0x%x!\n", ret);
83 return LOS_EINVAL;
84 }
85 return LOS_OK;
86 }
87
OsFutexInit(VOID)88 UINT32 OsFutexInit(VOID)
89 {
90 INT32 count;
91 UINT32 ret;
92
93 for (count = 0; count < FUTEX_INDEX_MAX; count++) {
94 LOS_ListInit(&g_futexHash[count].lockList);
95 ret = LOS_MuxInit(&(g_futexHash[count].listLock), NULL);
96 if (ret) {
97 return ret;
98 }
99 }
100
101 return LOS_OK;
102 }
103
104 LOS_MODULE_INIT(OsFutexInit, LOS_INIT_LEVEL_KMOD_EXTENDED);
105
106 #ifdef LOS_FUTEX_DEBUG
OsFutexShowTaskNodeAttr(const LOS_DL_LIST * futexList)107 STATIC VOID OsFutexShowTaskNodeAttr(const LOS_DL_LIST *futexList)
108 {
109 FutexNode *tempNode = NULL;
110 FutexNode *lastNode = NULL;
111 LosTaskCB *taskCB = NULL;
112 LOS_DL_LIST *queueList = NULL;
113
114 tempNode = OS_FUTEX_FROM_FUTEXLIST(futexList);
115 PRINTK("key(pid) : 0x%x(%u) : ->", tempNode->key, tempNode->pid);
116
117 for (queueList = &tempNode->queueList; ;) {
118 lastNode = OS_FUTEX_FROM_QUEUELIST(queueList);
119 if (!LOS_ListEmpty(&(lastNode->pendList))) {
120 taskCB = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(lastNode->pendList)));
121 PRINTK(" %u(%u) ->", taskCB->taskID, taskCB->priority);
122 } else {
123 taskCB = LOS_DL_LIST_ENTRY(lastNode, LosTaskCB, futex);
124 PRINTK(" %u(%d) ->", taskCB->taskID, -1);
125 }
126 queueList = queueList->pstNext;
127 if (queueList == &tempNode->queueList) {
128 break;
129 }
130 }
131 PRINTK("\n");
132 }
133
OsFutexHashShow(VOID)134 VOID OsFutexHashShow(VOID)
135 {
136 LOS_DL_LIST *futexList = NULL;
137 INT32 count;
138 /* The maximum number of barrels of a hash table */
139 INT32 hashNodeMax = FUTEX_INDEX_MAX;
140 PRINTK("#################### los_futex_pri.hash ####################\n");
141 for (count = 0; count < hashNodeMax; count++) {
142 futexList = &(g_futexHash[count].lockList);
143 if (LOS_ListEmpty(futexList)) {
144 continue;
145 }
146 PRINTK("hash -> index : %d\n", count);
147 for (futexList = futexList->pstNext;
148 futexList != &(g_futexHash[count].lockList);
149 futexList = futexList->pstNext) {
150 OsFutexShowTaskNodeAttr(futexList);
151 }
152 }
153 }
154 #endif
155
OsFutexFlagsToKey(const UINT32 * userVaddr,const UINT32 flags)156 STATIC INLINE UINTPTR OsFutexFlagsToKey(const UINT32 *userVaddr, const UINT32 flags)
157 {
158 UINTPTR futexKey;
159
160 if (flags & FUTEX_PRIVATE) {
161 futexKey = (UINTPTR)userVaddr;
162 } else {
163 futexKey = (UINTPTR)LOS_PaddrQuery((UINT32 *)userVaddr);
164 }
165
166 return futexKey;
167 }
168
OsFutexKeyToIndex(const UINTPTR futexKey,const UINT32 flags)169 STATIC INLINE UINT32 OsFutexKeyToIndex(const UINTPTR futexKey, const UINT32 flags)
170 {
171 UINT32 index = LOS_HashFNV32aBuf(&futexKey, sizeof(UINTPTR), FNV1_32A_INIT);
172
173 if (flags & FUTEX_PRIVATE) {
174 index &= FUTEX_HASH_PRIVATE_MASK;
175 } else {
176 index &= FUTEX_HASH_SHARED_MASK;
177 index += FUTEX_INDEX_SHARED_POS;
178 }
179
180 return index;
181 }
182
OsFutexSetKey(UINTPTR futexKey,UINT32 flags,FutexNode * node)183 STATIC INLINE VOID OsFutexSetKey(UINTPTR futexKey, UINT32 flags, FutexNode *node)
184 {
185 node->key = futexKey;
186 node->index = OsFutexKeyToIndex(futexKey, flags);
187 node->pid = (flags & FUTEX_PRIVATE) ? LOS_GetCurrProcessID() : OS_INVALID;
188 }
189
OsFutexDeinitFutexNode(FutexNode * node)190 STATIC INLINE VOID OsFutexDeinitFutexNode(FutexNode *node)
191 {
192 node->index = OS_INVALID_VALUE;
193 node->pid = 0;
194 LOS_ListDelete(&node->queueList);
195 }
196
OsFutexReplaceQueueListHeadNode(FutexNode * oldHeadNode,FutexNode * newHeadNode)197 STATIC INLINE VOID OsFutexReplaceQueueListHeadNode(FutexNode *oldHeadNode, FutexNode *newHeadNode)
198 {
199 LOS_DL_LIST *futexList = oldHeadNode->futexList.pstPrev;
200 LOS_ListDelete(&oldHeadNode->futexList);
201 LOS_ListHeadInsert(futexList, &newHeadNode->futexList);
202 if ((newHeadNode->queueList.pstNext == NULL) || (newHeadNode->queueList.pstPrev == NULL)) {
203 LOS_ListInit(&newHeadNode->queueList);
204 }
205 }
206
OsFutexDeleteKeyFromFutexList(FutexNode * node)207 STATIC INLINE VOID OsFutexDeleteKeyFromFutexList(FutexNode *node)
208 {
209 LOS_ListDelete(&node->futexList);
210 }
211
OsFutexDeleteKeyNodeFromHash(FutexNode * node,BOOL isDeleteHead,FutexNode ** headNode,BOOL * queueFlags)212 STATIC VOID OsFutexDeleteKeyNodeFromHash(FutexNode *node, BOOL isDeleteHead, FutexNode **headNode, BOOL *queueFlags)
213 {
214 FutexNode *nextNode = NULL;
215
216 if (node->index >= FUTEX_INDEX_MAX) {
217 return;
218 }
219
220 if (LOS_ListEmpty(&node->queueList)) {
221 OsFutexDeleteKeyFromFutexList(node);
222 if (queueFlags != NULL) {
223 *queueFlags = TRUE;
224 }
225 goto EXIT;
226 }
227
228 /* FutexList is not NULL, but the header node of queueList */
229 if (node->futexList.pstNext != NULL) {
230 if (isDeleteHead == TRUE) {
231 nextNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_FIRST(&node->queueList));
232 OsFutexReplaceQueueListHeadNode(node, nextNode);
233 if (headNode != NULL) {
234 *headNode = nextNode;
235 }
236 } else {
237 return;
238 }
239 }
240
241 EXIT:
242 OsFutexDeinitFutexNode(node);
243 return;
244 }
245
OsFutexNodeDeleteFromFutexHash(FutexNode * node,BOOL isDeleteHead,FutexNode ** headNode,BOOL * queueFlags)246 VOID OsFutexNodeDeleteFromFutexHash(FutexNode *node, BOOL isDeleteHead, FutexNode **headNode, BOOL *queueFlags)
247 {
248 FutexHash *hashNode = NULL;
249
250 UINT32 index = OsFutexKeyToIndex(node->key, (node->pid == OS_INVALID) ? 0 : FUTEX_PRIVATE);
251 if (index >= FUTEX_INDEX_MAX) {
252 return;
253 }
254
255 hashNode = &g_futexHash[index];
256 if (OsMuxLockUnsafe(&hashNode->listLock, LOS_WAIT_FOREVER)) {
257 return;
258 }
259
260 if (node->index != index) {
261 goto EXIT;
262 }
263
264 OsFutexDeleteKeyNodeFromHash(node, isDeleteHead, headNode, queueFlags);
265
266 EXIT:
267 if (OsMuxUnlockUnsafe(OsCurrTaskGet(), &hashNode->listLock, NULL)) {
268 return;
269 }
270
271 return;
272 }
273
OsFutexDeleteAlreadyWakeTaskAndGetNext(const FutexNode * node,FutexNode ** headNode,BOOL isDeleteHead)274 STATIC FutexNode *OsFutexDeleteAlreadyWakeTaskAndGetNext(const FutexNode *node, FutexNode **headNode, BOOL isDeleteHead)
275 {
276 FutexNode *tempNode = (FutexNode *)node;
277 FutexNode *nextNode = NULL;
278 BOOL queueFlag = FALSE;
279
280 while (LOS_ListEmpty(&(tempNode->pendList))) { /* already weak */
281 if (!LOS_ListEmpty(&(tempNode->queueList))) { /* It's not a head node */
282 nextNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_FIRST(&(tempNode->queueList)));
283 }
284
285 OsFutexDeleteKeyNodeFromHash(tempNode, isDeleteHead, headNode, &queueFlag);
286 if (queueFlag) {
287 return NULL;
288 }
289
290 tempNode = nextNode;
291 }
292
293 return tempNode;
294 }
295
OsFutexInsertNewFutexKeyToHash(FutexNode * node)296 STATIC VOID OsFutexInsertNewFutexKeyToHash(FutexNode *node)
297 {
298 FutexNode *headNode = NULL;
299 FutexNode *tailNode = NULL;
300 LOS_DL_LIST *futexList = NULL;
301 FutexHash *hashNode = &g_futexHash[node->index];
302
303 if (LOS_ListEmpty(&hashNode->lockList)) {
304 LOS_ListHeadInsert(&(hashNode->lockList), &(node->futexList));
305 goto EXIT;
306 }
307
308 headNode = OS_FUTEX_FROM_FUTEXLIST(LOS_DL_LIST_FIRST(&(hashNode->lockList)));
309 /* The small key is at the front of the queue */
310 if (node->key < headNode->key) {
311 LOS_ListHeadInsert(&(hashNode->lockList), &(node->futexList));
312 goto EXIT;
313 }
314
315 tailNode = OS_FUTEX_FROM_FUTEXLIST(LOS_DL_LIST_LAST(&(hashNode->lockList)));
316 if (node->key > tailNode->key) {
317 LOS_ListTailInsert(&(hashNode->lockList), &(node->futexList));
318 goto EXIT;
319 }
320
321 for (futexList = hashNode->lockList.pstNext;
322 futexList != &(hashNode->lockList);
323 futexList = futexList->pstNext) {
324 headNode = OS_FUTEX_FROM_FUTEXLIST(futexList);
325 if (node->key <= headNode->key) {
326 LOS_ListTailInsert(&(headNode->futexList), &(node->futexList));
327 break;
328 }
329 }
330
331 EXIT:
332 return;
333 }
334
OsFutexInsertFindFormBackToFront(LOS_DL_LIST * queueList,const LosTaskCB * runTask,FutexNode * node)335 STATIC INT32 OsFutexInsertFindFormBackToFront(LOS_DL_LIST *queueList, const LosTaskCB *runTask, FutexNode *node)
336 {
337 LOS_DL_LIST *listHead = queueList;
338 LOS_DL_LIST *listTail = queueList->pstPrev;
339 FutexNode *tempNode = NULL;
340 LosTaskCB *taskTail = NULL;
341
342 for (; listHead != listTail; listTail = listTail->pstPrev) {
343 tempNode = OS_FUTEX_FROM_QUEUELIST(listTail);
344 tempNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(tempNode, NULL, FALSE);
345 if (tempNode == NULL) {
346 return LOS_NOK;
347 }
348 taskTail = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tempNode->pendList)));
349 if (runTask->priority >= taskTail->priority) {
350 LOS_ListHeadInsert(&(tempNode->queueList), &(node->queueList));
351 return LOS_OK;
352 } else if (runTask->priority < taskTail->priority) {
353 if (listTail->pstPrev == listHead) {
354 LOS_ListTailInsert(&(tempNode->queueList), &(node->queueList));
355 return LOS_OK;
356 }
357 }
358 }
359
360 return LOS_NOK;
361 }
362
OsFutexInsertFindFromFrontToBack(LOS_DL_LIST * queueList,const LosTaskCB * runTask,FutexNode * node)363 STATIC INT32 OsFutexInsertFindFromFrontToBack(LOS_DL_LIST *queueList, const LosTaskCB *runTask, FutexNode *node)
364 {
365 LOS_DL_LIST *listHead = queueList;
366 LOS_DL_LIST *listTail = queueList->pstPrev;
367 FutexNode *tempNode = NULL;
368 LosTaskCB *taskHead = NULL;
369
370 for (; listHead != listTail; listHead = listHead->pstNext) {
371 tempNode = OS_FUTEX_FROM_QUEUELIST(listHead);
372 tempNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(tempNode, NULL, FALSE);
373 if (tempNode == NULL) {
374 return LOS_NOK;
375 }
376 taskHead = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tempNode->pendList)));
377 /* High priority comes before low priority,
378 * in the case of the same priority, after the current node
379 */
380 if (runTask->priority >= taskHead->priority) {
381 if (listHead->pstNext == listTail) {
382 LOS_ListHeadInsert(&(tempNode->queueList), &(node->queueList));
383 return LOS_OK;
384 }
385 continue;
386 } else if (runTask->priority < taskHead->priority) {
387 LOS_ListTailInsert(&(tempNode->queueList), &(node->queueList));
388 return LOS_OK;
389 }
390 }
391
392 return LOS_NOK;
393 }
394
OsFutexRecycleAndFindHeadNode(FutexNode * headNode,FutexNode * node,FutexNode ** firstNode)395 STATIC INT32 OsFutexRecycleAndFindHeadNode(FutexNode *headNode, FutexNode *node, FutexNode **firstNode)
396 {
397 UINT32 intSave;
398
399 SCHEDULER_LOCK(intSave);
400 *firstNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(headNode, NULL, TRUE);
401 SCHEDULER_UNLOCK(intSave);
402
403 /* The head node is removed and there was originally only one node under the key */
404 if (*firstNode == NULL) {
405 OsFutexInsertNewFutexKeyToHash(node);
406 LOS_ListInit(&(node->queueList));
407 return LOS_OK;
408 }
409
410 return LOS_OK;
411 }
412
OsFutexInsertTasktoPendList(FutexNode ** firstNode,FutexNode * node,const LosTaskCB * run)413 STATIC INT32 OsFutexInsertTasktoPendList(FutexNode **firstNode, FutexNode *node, const LosTaskCB *run)
414 {
415 LosTaskCB *taskHead = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&((*firstNode)->pendList)));
416 LOS_DL_LIST *queueList = &((*firstNode)->queueList);
417 FutexNode *tailNode = NULL;
418 LosTaskCB *taskTail = NULL;
419
420 if (run->priority < taskHead->priority) {
421 /* The one with the highest priority is inserted at the top of the queue */
422 LOS_ListTailInsert(queueList, &(node->queueList));
423 OsFutexReplaceQueueListHeadNode(*firstNode, node);
424 *firstNode = node;
425 return LOS_OK;
426 }
427
428 if (LOS_ListEmpty(queueList) && (run->priority >= taskHead->priority)) {
429 /* Insert the next position in the queue with equal priority */
430 LOS_ListHeadInsert(queueList, &(node->queueList));
431 return LOS_OK;
432 }
433
434 tailNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_LAST(queueList));
435 taskTail = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tailNode->pendList)));
436 if ((run->priority >= taskTail->priority) ||
437 ((run->priority - taskHead->priority) > (taskTail->priority - run->priority))) {
438 return OsFutexInsertFindFormBackToFront(queueList, run, node);
439 }
440
441 return OsFutexInsertFindFromFrontToBack(queueList, run, node);
442 }
443
OsFindFutexNode(const FutexNode * node)444 STATIC FutexNode *OsFindFutexNode(const FutexNode *node)
445 {
446 FutexHash *hashNode = &g_futexHash[node->index];
447 LOS_DL_LIST *futexList = &(hashNode->lockList);
448 FutexNode *headNode = NULL;
449
450 for (futexList = futexList->pstNext;
451 futexList != &(hashNode->lockList);
452 futexList = futexList->pstNext) {
453 headNode = OS_FUTEX_FROM_FUTEXLIST(futexList);
454 if ((headNode->key == node->key) && (headNode->pid == node->pid)) {
455 return headNode;
456 }
457 }
458
459 return NULL;
460 }
461
OsFindAndInsertToHash(FutexNode * node)462 STATIC INT32 OsFindAndInsertToHash(FutexNode *node)
463 {
464 FutexNode *headNode = NULL;
465 FutexNode *firstNode = NULL;
466 UINT32 intSave;
467 INT32 ret;
468
469 headNode = OsFindFutexNode(node);
470 if (headNode == NULL) {
471 OsFutexInsertNewFutexKeyToHash(node);
472 LOS_ListInit(&(node->queueList));
473 return LOS_OK;
474 }
475
476 ret = OsFutexRecycleAndFindHeadNode(headNode, node, &firstNode);
477 if (ret != LOS_OK) {
478 return ret;
479 } else if (firstNode == NULL) {
480 return ret;
481 }
482
483 SCHEDULER_LOCK(intSave);
484 ret = OsFutexInsertTasktoPendList(&firstNode, node, OsCurrTaskGet());
485 SCHEDULER_UNLOCK(intSave);
486
487 return ret;
488 }
489
OsFutexKeyShmPermCheck(const UINT32 * userVaddr,const UINT32 flags)490 STATIC INT32 OsFutexKeyShmPermCheck(const UINT32 *userVaddr, const UINT32 flags)
491 {
492 PADDR_T paddr;
493
494 /* Check whether the futexKey is a shared lock */
495 if (!(flags & FUTEX_PRIVATE)) {
496 paddr = (UINTPTR)LOS_PaddrQuery((UINT32 *)userVaddr);
497 if (paddr == 0) return LOS_NOK;
498 }
499
500 return LOS_OK;
501 }
502
OsFutexWaitParamCheck(const UINT32 * userVaddr,UINT32 flags,UINT32 absTime)503 STATIC INT32 OsFutexWaitParamCheck(const UINT32 *userVaddr, UINT32 flags, UINT32 absTime)
504 {
505 VADDR_T vaddr = (VADDR_T)(UINTPTR)userVaddr;
506
507 if (OS_INT_ACTIVE) {
508 return LOS_EINTR;
509 }
510
511 if (flags & (~FUTEX_PRIVATE)) {
512 PRINT_ERR("Futex wait param check failed! error flags: 0x%x\n", flags);
513 return LOS_EINVAL;
514 }
515
516 if ((vaddr % sizeof(INT32)) || (vaddr < OS_FUTEX_KEY_BASE) || (vaddr >= OS_FUTEX_KEY_MAX)) {
517 PRINT_ERR("Futex wait param check failed! error userVaddr: 0x%x\n", vaddr);
518 return LOS_EINVAL;
519 }
520
521 if (flags && (OsFutexKeyShmPermCheck(userVaddr, flags) != LOS_OK)) {
522 PRINT_ERR("Futex wait param check failed! error shared memory perm userVaddr: 0x%x\n", userVaddr);
523 return LOS_EINVAL;
524 }
525
526 if (!absTime) {
527 return LOS_EINVAL;
528 }
529
530 return LOS_OK;
531 }
532
OsFutexDeleteTimeoutTaskNode(FutexHash * hashNode,FutexNode * node)533 STATIC INT32 OsFutexDeleteTimeoutTaskNode(FutexHash *hashNode, FutexNode *node)
534 {
535 UINT32 intSave;
536 if (OsFutexLock(&hashNode->listLock)) {
537 return LOS_EINVAL;
538 }
539
540 if (node->index < FUTEX_INDEX_MAX) {
541 SCHEDULER_LOCK(intSave);
542 (VOID)OsFutexDeleteAlreadyWakeTaskAndGetNext(node, NULL, TRUE);
543 SCHEDULER_UNLOCK(intSave);
544 }
545
546 #ifdef LOS_FUTEX_DEBUG
547 OsFutexHashShow();
548 #endif
549
550 if (OsFutexUnlock(&hashNode->listLock)) {
551 return LOS_EINVAL;
552 }
553 return LOS_ETIMEDOUT;
554 }
555
OsFutexInsertTaskToHash(LosTaskCB ** taskCB,FutexNode ** node,const UINTPTR futexKey,const UINT32 flags)556 STATIC INT32 OsFutexInsertTaskToHash(LosTaskCB **taskCB, FutexNode **node, const UINTPTR futexKey, const UINT32 flags)
557 {
558 INT32 ret;
559 *taskCB = OsCurrTaskGet();
560 *node = &((*taskCB)->futex);
561 OsFutexSetKey(futexKey, flags, *node);
562
563 ret = OsFindAndInsertToHash(*node);
564 if (ret) {
565 return LOS_NOK;
566 }
567
568 LOS_ListInit(&((*node)->pendList));
569 return LOS_OK;
570 }
571
OsFutexWaitTask(const UINT32 * userVaddr,const UINT32 flags,const UINT32 val,const UINT32 timeOut)572 STATIC INT32 OsFutexWaitTask(const UINT32 *userVaddr, const UINT32 flags, const UINT32 val, const UINT32 timeOut)
573 {
574 INT32 futexRet;
575 UINT32 intSave, lockVal;
576 LosTaskCB *taskCB = NULL;
577 FutexNode *node = NULL;
578 UINTPTR futexKey = OsFutexFlagsToKey(userVaddr, flags);
579 UINT32 index = OsFutexKeyToIndex(futexKey, flags);
580 FutexHash *hashNode = &g_futexHash[index];
581
582 if (OsFutexLock(&hashNode->listLock)) {
583 return LOS_EINVAL;
584 }
585
586 if (LOS_ArchCopyFromUser(&lockVal, userVaddr, sizeof(UINT32))) {
587 PRINT_ERR("Futex wait param check failed! copy from user failed!\n");
588 futexRet = LOS_EINVAL;
589 goto EXIT_ERR;
590 }
591
592 if (lockVal != val) {
593 futexRet = LOS_EBADF;
594 goto EXIT_ERR;
595 }
596
597 if (OsFutexInsertTaskToHash(&taskCB, &node, futexKey, flags)) {
598 futexRet = LOS_NOK;
599 goto EXIT_ERR;
600 }
601
602 SCHEDULER_LOCK(intSave);
603 OsTaskWaitSetPendMask(OS_TASK_WAIT_FUTEX, futexKey, timeOut);
604 OsSchedTaskWait(&(node->pendList), timeOut, FALSE);
605 OsSchedLock();
606 LOS_SpinUnlock(&g_taskSpin);
607
608 futexRet = OsFutexUnlock(&hashNode->listLock);
609 if (futexRet) {
610 OsSchedUnlock();
611 LOS_IntRestore(intSave);
612 goto EXIT_UNLOCK_ERR;
613 }
614
615 LOS_SpinLock(&g_taskSpin);
616 OsSchedUnlock();
617
618 /*
619 * it will immediately do the scheduling, so there's no need to release the
620 * task spinlock. when this task's been rescheduled, it will be holding the spinlock.
621 */
622 OsSchedResched();
623
624 if (taskCB->taskStatus & OS_TASK_STATUS_TIMEOUT) {
625 taskCB->taskStatus &= ~OS_TASK_STATUS_TIMEOUT;
626 SCHEDULER_UNLOCK(intSave);
627 return OsFutexDeleteTimeoutTaskNode(hashNode, node);
628 }
629
630 SCHEDULER_UNLOCK(intSave);
631 return LOS_OK;
632
633 EXIT_ERR:
634 (VOID)OsFutexUnlock(&hashNode->listLock);
635 EXIT_UNLOCK_ERR:
636 return futexRet;
637 }
638
OsFutexWait(const UINT32 * userVaddr,UINT32 flags,UINT32 val,UINT32 absTime)639 INT32 OsFutexWait(const UINT32 *userVaddr, UINT32 flags, UINT32 val, UINT32 absTime)
640 {
641 INT32 ret;
642 UINT32 timeOut = LOS_WAIT_FOREVER;
643
644 ret = OsFutexWaitParamCheck(userVaddr, flags, absTime);
645 if (ret) {
646 return ret;
647 }
648 if (absTime != LOS_WAIT_FOREVER) {
649 timeOut = OsNS2Tick((UINT64)absTime * OS_SYS_NS_PER_US);
650 }
651
652 return OsFutexWaitTask(userVaddr, flags, val, timeOut);
653 }
654
OsFutexWakeParamCheck(const UINT32 * userVaddr,UINT32 flags)655 STATIC INT32 OsFutexWakeParamCheck(const UINT32 *userVaddr, UINT32 flags)
656 {
657 VADDR_T vaddr = (VADDR_T)(UINTPTR)userVaddr;
658
659 if ((flags & (~FUTEX_PRIVATE)) != FUTEX_WAKE) {
660 PRINT_ERR("Futex wake param check failed! error flags: 0x%x\n", flags);
661 return LOS_EINVAL;
662 }
663
664 if ((vaddr % sizeof(INT32)) || (vaddr < OS_FUTEX_KEY_BASE) || (vaddr >= OS_FUTEX_KEY_MAX)) {
665 PRINT_ERR("Futex wake param check failed! error userVaddr: 0x%x\n", userVaddr);
666 return LOS_EINVAL;
667 }
668
669 if (flags && (OsFutexKeyShmPermCheck(userVaddr, flags) != LOS_OK)) {
670 PRINT_ERR("Futex wake param check failed! error shared memory perm userVaddr: 0x%x\n", userVaddr);
671 return LOS_EINVAL;
672 }
673
674 return LOS_OK;
675 }
676
677 /* Check to see if the task to be awakened has timed out
678 * if time out, to weak next pend task.
679 */
OsFutexCheckAndWakePendTask(FutexNode * headNode,const INT32 wakeNumber,FutexHash * hashNode,FutexNode ** nextNode,BOOL * wakeAny)680 STATIC VOID OsFutexCheckAndWakePendTask(FutexNode *headNode, const INT32 wakeNumber,
681 FutexHash *hashNode, FutexNode **nextNode, BOOL *wakeAny)
682 {
683 INT32 count;
684 LosTaskCB *taskCB = NULL;
685 FutexNode *node = headNode;
686 for (count = 0; count < wakeNumber; count++) {
687 /* Ensure the integrity of the head */
688 *nextNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(node, NULL, FALSE);
689 if (*nextNode == NULL) {
690 /* The last node in queuelist is invalid or the entire list is invalid */
691 return;
692 }
693 node = *nextNode;
694 taskCB = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(node->pendList)));
695 OsTaskWakeClearPendMask(taskCB);
696 OsSchedTaskWake(taskCB);
697 *wakeAny = TRUE;
698 *nextNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_FIRST(&(node->queueList)));
699 if (node != headNode) {
700 OsFutexDeinitFutexNode(node);
701 }
702
703 if (LOS_ListEmpty(&headNode->queueList)) {
704 /* Wakes up the entire linked list node */
705 *nextNode = NULL;
706 return;
707 }
708
709 node = *nextNode;
710 }
711 return;
712 }
713
OsFutexWakeTask(UINTPTR futexKey,UINT32 flags,INT32 wakeNumber,FutexNode ** newHeadNode,BOOL * wakeAny)714 STATIC INT32 OsFutexWakeTask(UINTPTR futexKey, UINT32 flags, INT32 wakeNumber, FutexNode **newHeadNode, BOOL *wakeAny)
715 {
716 UINT32 intSave;
717 FutexNode *node = NULL;
718 FutexNode *headNode = NULL;
719 UINT32 index = OsFutexKeyToIndex(futexKey, flags);
720 FutexHash *hashNode = &g_futexHash[index];
721 FutexNode tempNode = {
722 .key = futexKey,
723 .index = index,
724 .pid = (flags & FUTEX_PRIVATE) ? LOS_GetCurrProcessID() : OS_INVALID,
725 };
726
727 node = OsFindFutexNode(&tempNode);
728 if (node == NULL) {
729 return LOS_EBADF;
730 }
731
732 headNode = node;
733
734 SCHEDULER_LOCK(intSave);
735 OsFutexCheckAndWakePendTask(headNode, wakeNumber, hashNode, newHeadNode, wakeAny);
736 if ((*newHeadNode) != NULL) {
737 OsFutexReplaceQueueListHeadNode(headNode, *newHeadNode);
738 OsFutexDeinitFutexNode(headNode);
739 } else if (headNode->index < FUTEX_INDEX_MAX) {
740 OsFutexDeleteKeyFromFutexList(headNode);
741 OsFutexDeinitFutexNode(headNode);
742 }
743 SCHEDULER_UNLOCK(intSave);
744
745 return LOS_OK;
746 }
747
OsFutexWake(const UINT32 * userVaddr,UINT32 flags,INT32 wakeNumber)748 INT32 OsFutexWake(const UINT32 *userVaddr, UINT32 flags, INT32 wakeNumber)
749 {
750 INT32 ret, futexRet;
751 UINTPTR futexKey;
752 UINT32 index;
753 FutexHash *hashNode = NULL;
754 FutexNode *headNode = NULL;
755 BOOL wakeAny = FALSE;
756
757 if (OsFutexWakeParamCheck(userVaddr, flags)) {
758 return LOS_EINVAL;
759 }
760
761 futexKey = OsFutexFlagsToKey(userVaddr, flags);
762 index = OsFutexKeyToIndex(futexKey, flags);
763
764 hashNode = &g_futexHash[index];
765 if (OsFutexLock(&hashNode->listLock)) {
766 return LOS_EINVAL;
767 }
768
769 ret = OsFutexWakeTask(futexKey, flags, wakeNumber, &headNode, &wakeAny);
770 if (ret) {
771 goto EXIT_ERR;
772 }
773
774 #ifdef LOS_FUTEX_DEBUG
775 OsFutexHashShow();
776 #endif
777
778 futexRet = OsFutexUnlock(&hashNode->listLock);
779 if (futexRet) {
780 goto EXIT_UNLOCK_ERR;
781 }
782
783 if (wakeAny == TRUE) {
784 LOS_MpSchedule(OS_MP_CPU_ALL);
785 LOS_Schedule();
786 }
787
788 return LOS_OK;
789
790 EXIT_ERR:
791 futexRet = OsFutexUnlock(&hashNode->listLock);
792 EXIT_UNLOCK_ERR:
793 if (futexRet) {
794 return futexRet;
795 }
796 return ret;
797 }
798
OsFutexRequeueInsertNewKey(UINTPTR newFutexKey,INT32 newIndex,FutexNode * oldHeadNode)799 STATIC INT32 OsFutexRequeueInsertNewKey(UINTPTR newFutexKey, INT32 newIndex, FutexNode *oldHeadNode)
800 {
801 BOOL queueListIsEmpty = FALSE;
802 INT32 ret;
803 UINT32 intSave;
804 LosTaskCB *task = NULL;
805 FutexNode *nextNode = NULL;
806 FutexNode newTempNode = {
807 .key = newFutexKey,
808 .index = newIndex,
809 .pid = (newIndex < FUTEX_INDEX_SHARED_POS) ? LOS_GetCurrProcessID() : OS_INVALID,
810 };
811 LOS_DL_LIST *queueList = &oldHeadNode->queueList;
812 FutexNode *newHeadNode = OsFindFutexNode(&newTempNode);
813 if (newHeadNode == NULL) {
814 OsFutexInsertNewFutexKeyToHash(oldHeadNode);
815 return LOS_OK;
816 }
817
818 do {
819 nextNode = OS_FUTEX_FROM_QUEUELIST(queueList);
820 SCHEDULER_LOCK(intSave);
821 if (LOS_ListEmpty(&nextNode->pendList)) {
822 if (LOS_ListEmpty(queueList)) {
823 queueListIsEmpty = TRUE;
824 } else {
825 queueList = queueList->pstNext;
826 }
827 OsFutexDeinitFutexNode(nextNode);
828 SCHEDULER_UNLOCK(intSave);
829 if (queueListIsEmpty) {
830 return LOS_OK;
831 }
832
833 continue;
834 }
835
836 task = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(nextNode->pendList)));
837 if (LOS_ListEmpty(queueList)) {
838 queueListIsEmpty = TRUE;
839 } else {
840 queueList = queueList->pstNext;
841 }
842 LOS_ListDelete(&nextNode->queueList);
843 ret = OsFutexInsertTasktoPendList(&newHeadNode, nextNode, task);
844 SCHEDULER_UNLOCK(intSave);
845 if (ret != LOS_OK) {
846 PRINT_ERR("Futex requeue insert new key failed!\n");
847 }
848 } while (!queueListIsEmpty);
849
850 return LOS_OK;
851 }
852
OsFutexRequeueSplitTwoLists(FutexHash * oldHashNode,FutexNode * oldHeadNode,UINT32 flags,UINTPTR futexKey,INT32 count)853 STATIC VOID OsFutexRequeueSplitTwoLists(FutexHash *oldHashNode, FutexNode *oldHeadNode,
854 UINT32 flags, UINTPTR futexKey, INT32 count)
855 {
856 LOS_DL_LIST *queueList = &oldHeadNode->queueList;
857 FutexNode *tailNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_LAST(queueList));
858 INT32 newIndex = OsFutexKeyToIndex(futexKey, flags);
859 FutexNode *nextNode = NULL;
860 FutexNode *newHeadNode = NULL;
861 LOS_DL_LIST *futexList = NULL;
862 BOOL isAll = FALSE;
863 INT32 i;
864
865 for (i = 0; i < count; i++) {
866 nextNode = OS_FUTEX_FROM_QUEUELIST(queueList);
867 nextNode->key = futexKey;
868 nextNode->index = newIndex;
869 if (queueList->pstNext == &oldHeadNode->queueList) {
870 isAll = TRUE;
871 break;
872 }
873
874 queueList = queueList->pstNext;
875 }
876
877 futexList = oldHeadNode->futexList.pstPrev;
878 LOS_ListDelete(&oldHeadNode->futexList);
879 if (isAll == TRUE) {
880 return;
881 }
882
883 newHeadNode = OS_FUTEX_FROM_QUEUELIST(queueList);
884 LOS_ListHeadInsert(futexList, &newHeadNode->futexList);
885 oldHeadNode->queueList.pstPrev = &nextNode->queueList;
886 nextNode->queueList.pstNext = &oldHeadNode->queueList;
887 newHeadNode->queueList.pstPrev = &tailNode->queueList;
888 tailNode->queueList.pstNext = &newHeadNode->queueList;
889 return;
890 }
891
OsFutexRequeueRemoveOldKeyAndGetHead(UINTPTR oldFutexKey,UINT32 flags,INT32 wakeNumber,UINTPTR newFutexKey,INT32 requeueCount,BOOL * wakeAny)892 STATIC FutexNode *OsFutexRequeueRemoveOldKeyAndGetHead(UINTPTR oldFutexKey, UINT32 flags, INT32 wakeNumber,
893 UINTPTR newFutexKey, INT32 requeueCount, BOOL *wakeAny)
894 {
895 INT32 ret;
896 INT32 oldIndex = OsFutexKeyToIndex(oldFutexKey, flags);
897 FutexNode *oldHeadNode = NULL;
898 FutexHash *oldHashNode = &g_futexHash[oldIndex];
899 FutexNode oldTempNode = {
900 .key = oldFutexKey,
901 .index = oldIndex,
902 .pid = (flags & FUTEX_PRIVATE) ? LOS_GetCurrProcessID() : OS_INVALID,
903 };
904
905 if (wakeNumber > 0) {
906 ret = OsFutexWakeTask(oldFutexKey, flags, wakeNumber, &oldHeadNode, wakeAny);
907 if ((ret != LOS_OK) || (oldHeadNode == NULL)) {
908 return NULL;
909 }
910 }
911
912 if (requeueCount <= 0) {
913 return NULL;
914 }
915
916 if (oldHeadNode == NULL) {
917 oldHeadNode = OsFindFutexNode(&oldTempNode);
918 if (oldHeadNode == NULL) {
919 return NULL;
920 }
921 }
922
923 OsFutexRequeueSplitTwoLists(oldHashNode, oldHeadNode, flags, newFutexKey, requeueCount);
924
925 return oldHeadNode;
926 }
927
OsFutexRequeueParamCheck(const UINT32 * oldUserVaddr,UINT32 flags,const UINT32 * newUserVaddr)928 STATIC INT32 OsFutexRequeueParamCheck(const UINT32 *oldUserVaddr, UINT32 flags, const UINT32 *newUserVaddr)
929 {
930 VADDR_T oldVaddr = (VADDR_T)(UINTPTR)oldUserVaddr;
931 VADDR_T newVaddr = (VADDR_T)(UINTPTR)newUserVaddr;
932
933 if (oldVaddr == newVaddr) {
934 return LOS_EINVAL;
935 }
936
937 if ((flags & (~FUTEX_PRIVATE)) != FUTEX_REQUEUE) {
938 PRINT_ERR("Futex requeue param check failed! error flags: 0x%x\n", flags);
939 return LOS_EINVAL;
940 }
941
942 if ((oldVaddr % sizeof(INT32)) || (oldVaddr < OS_FUTEX_KEY_BASE) || (oldVaddr >= OS_FUTEX_KEY_MAX)) {
943 PRINT_ERR("Futex requeue param check failed! error old userVaddr: 0x%x\n", oldUserVaddr);
944 return LOS_EINVAL;
945 }
946
947 if ((newVaddr % sizeof(INT32)) || (newVaddr < OS_FUTEX_KEY_BASE) || (newVaddr >= OS_FUTEX_KEY_MAX)) {
948 PRINT_ERR("Futex requeue param check failed! error new userVaddr: 0x%x\n", newUserVaddr);
949 return LOS_EINVAL;
950 }
951
952 return LOS_OK;
953 }
954
OsFutexRequeue(const UINT32 * userVaddr,UINT32 flags,INT32 wakeNumber,INT32 count,const UINT32 * newUserVaddr)955 INT32 OsFutexRequeue(const UINT32 *userVaddr, UINT32 flags, INT32 wakeNumber, INT32 count, const UINT32 *newUserVaddr)
956 {
957 INT32 ret;
958 UINTPTR oldFutexKey;
959 UINTPTR newFutexKey;
960 INT32 oldIndex;
961 INT32 newIndex;
962 FutexHash *oldHashNode = NULL;
963 FutexHash *newHashNode = NULL;
964 FutexNode *oldHeadNode = NULL;
965 BOOL wakeAny = FALSE;
966
967 if (OsFutexRequeueParamCheck(userVaddr, flags, newUserVaddr)) {
968 return LOS_EINVAL;
969 }
970
971 oldFutexKey = OsFutexFlagsToKey(userVaddr, flags);
972 newFutexKey = OsFutexFlagsToKey(newUserVaddr, flags);
973 oldIndex = OsFutexKeyToIndex(oldFutexKey, flags);
974 newIndex = OsFutexKeyToIndex(newFutexKey, flags);
975
976 oldHashNode = &g_futexHash[oldIndex];
977 if (OsFutexLock(&oldHashNode->listLock)) {
978 return LOS_EINVAL;
979 }
980
981 oldHeadNode = OsFutexRequeueRemoveOldKeyAndGetHead(oldFutexKey, flags, wakeNumber, newFutexKey, count, &wakeAny);
982 if (oldHeadNode == NULL) {
983 (VOID)OsFutexUnlock(&oldHashNode->listLock);
984 if (wakeAny == TRUE) {
985 ret = LOS_OK;
986 goto EXIT;
987 }
988 return LOS_EBADF;
989 }
990
991 newHashNode = &g_futexHash[newIndex];
992 if (oldIndex != newIndex) {
993 if (OsFutexUnlock(&oldHashNode->listLock)) {
994 return LOS_EINVAL;
995 }
996
997 if (OsFutexLock(&newHashNode->listLock)) {
998 return LOS_EINVAL;
999 }
1000 }
1001
1002 ret = OsFutexRequeueInsertNewKey(newFutexKey, newIndex, oldHeadNode);
1003
1004 if (OsFutexUnlock(&newHashNode->listLock)) {
1005 return LOS_EINVAL;
1006 }
1007
1008 EXIT:
1009 if (wakeAny == TRUE) {
1010 LOS_MpSchedule(OS_MP_CPU_ALL);
1011 LOS_Schedule();
1012 }
1013
1014 return ret;
1015 }
1016 #endif
1017
1018