1 /*
2 * Copyright (c) 2013-2019 Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020-2022 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 ->", taskCB->taskID);
122 } else {
123 taskCB = LOS_DL_LIST_ENTRY(lastNode, LosTaskCB, futex);
124 PRINTK(" %u ->", taskCB->taskID);
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
340 for (; listHead != listTail; listTail = listTail->pstPrev) {
341 FutexNode *tempNode = OS_FUTEX_FROM_QUEUELIST(listTail);
342 tempNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(tempNode, NULL, FALSE);
343 if (tempNode == NULL) {
344 return LOS_NOK;
345 }
346 LosTaskCB *taskTail = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tempNode->pendList)));
347 INT32 ret = OsSchedParamCompare(runTask, taskTail);
348 if (ret >= 0) {
349 LOS_ListHeadInsert(&(tempNode->queueList), &(node->queueList));
350 return LOS_OK;
351 } else {
352 if (listTail->pstPrev == listHead) {
353 LOS_ListTailInsert(&(tempNode->queueList), &(node->queueList));
354 return LOS_OK;
355 }
356 }
357 }
358
359 return LOS_NOK;
360 }
361
OsFutexInsertFindFromFrontToBack(LOS_DL_LIST * queueList,const LosTaskCB * runTask,FutexNode * node)362 STATIC INT32 OsFutexInsertFindFromFrontToBack(LOS_DL_LIST *queueList, const LosTaskCB *runTask, FutexNode *node)
363 {
364 LOS_DL_LIST *listHead = queueList;
365 LOS_DL_LIST *listTail = queueList->pstPrev;
366
367 for (; listHead != listTail; listHead = listHead->pstNext) {
368 FutexNode *tempNode = OS_FUTEX_FROM_QUEUELIST(listHead);
369 tempNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(tempNode, NULL, FALSE);
370 if (tempNode == NULL) {
371 return LOS_NOK;
372 }
373 LosTaskCB *taskHead = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tempNode->pendList)));
374 /* High priority comes before low priority,
375 * in the case of the same priority, after the current node
376 */
377 INT32 ret = OsSchedParamCompare(runTask, taskHead);
378 if (ret >= 0) {
379 if (listHead->pstNext == listTail) {
380 LOS_ListHeadInsert(&(tempNode->queueList), &(node->queueList));
381 return LOS_OK;
382 }
383 continue;
384 } else {
385 LOS_ListTailInsert(&(tempNode->queueList), &(node->queueList));
386 return LOS_OK;
387 }
388 }
389
390 return LOS_NOK;
391 }
392
OsFutexRecycleAndFindHeadNode(FutexNode * headNode,FutexNode * node,FutexNode ** firstNode)393 STATIC INT32 OsFutexRecycleAndFindHeadNode(FutexNode *headNode, FutexNode *node, FutexNode **firstNode)
394 {
395 UINT32 intSave;
396
397 SCHEDULER_LOCK(intSave);
398 *firstNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(headNode, NULL, TRUE);
399 SCHEDULER_UNLOCK(intSave);
400
401 /* The head node is removed and there was originally only one node under the key */
402 if (*firstNode == NULL) {
403 OsFutexInsertNewFutexKeyToHash(node);
404 LOS_ListInit(&(node->queueList));
405 return LOS_OK;
406 }
407
408 return LOS_OK;
409 }
410
OsFutexInsertTasktoPendList(FutexNode ** firstNode,FutexNode * node,const LosTaskCB * run)411 STATIC INT32 OsFutexInsertTasktoPendList(FutexNode **firstNode, FutexNode *node, const LosTaskCB *run)
412 {
413 LosTaskCB *taskHead = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&((*firstNode)->pendList)));
414 LOS_DL_LIST *queueList = &((*firstNode)->queueList);
415
416 INT32 ret1 = OsSchedParamCompare(run, taskHead);
417 if (ret1 < 0) {
418 /* The one with the highest priority is inserted at the top of the queue */
419 LOS_ListTailInsert(queueList, &(node->queueList));
420 OsFutexReplaceQueueListHeadNode(*firstNode, node);
421 *firstNode = node;
422 return LOS_OK;
423 }
424
425 if (LOS_ListEmpty(queueList) && (ret1 >= 0)) {
426 /* Insert the next position in the queue with equal priority */
427 LOS_ListHeadInsert(queueList, &(node->queueList));
428 return LOS_OK;
429 }
430
431 FutexNode *tailNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_LAST(queueList));
432 LosTaskCB *taskTail = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(tailNode->pendList)));
433 INT32 ret2 = OsSchedParamCompare(taskTail, run);
434 if ((ret2 <= 0) || (ret1 > ret2)) {
435 return OsFutexInsertFindFormBackToFront(queueList, run, node);
436 }
437
438 return OsFutexInsertFindFromFrontToBack(queueList, run, node);
439 }
440
OsFindFutexNode(const FutexNode * node)441 STATIC FutexNode *OsFindFutexNode(const FutexNode *node)
442 {
443 FutexHash *hashNode = &g_futexHash[node->index];
444 LOS_DL_LIST *futexList = &(hashNode->lockList);
445 FutexNode *headNode = NULL;
446
447 for (futexList = futexList->pstNext;
448 futexList != &(hashNode->lockList);
449 futexList = futexList->pstNext) {
450 headNode = OS_FUTEX_FROM_FUTEXLIST(futexList);
451 if ((headNode->key == node->key) && (headNode->pid == node->pid)) {
452 return headNode;
453 }
454 }
455
456 return NULL;
457 }
458
OsFindAndInsertToHash(FutexNode * node)459 STATIC INT32 OsFindAndInsertToHash(FutexNode *node)
460 {
461 FutexNode *headNode = NULL;
462 FutexNode *firstNode = NULL;
463 UINT32 intSave;
464 INT32 ret;
465
466 headNode = OsFindFutexNode(node);
467 if (headNode == NULL) {
468 OsFutexInsertNewFutexKeyToHash(node);
469 LOS_ListInit(&(node->queueList));
470 return LOS_OK;
471 }
472
473 ret = OsFutexRecycleAndFindHeadNode(headNode, node, &firstNode);
474 if (ret != LOS_OK) {
475 return ret;
476 } else if (firstNode == NULL) {
477 return ret;
478 }
479
480 SCHEDULER_LOCK(intSave);
481 ret = OsFutexInsertTasktoPendList(&firstNode, node, OsCurrTaskGet());
482 SCHEDULER_UNLOCK(intSave);
483
484 return ret;
485 }
486
OsFutexKeyShmPermCheck(const UINT32 * userVaddr,const UINT32 flags)487 STATIC INT32 OsFutexKeyShmPermCheck(const UINT32 *userVaddr, const UINT32 flags)
488 {
489 PADDR_T paddr;
490
491 /* Check whether the futexKey is a shared lock */
492 if (!(flags & FUTEX_PRIVATE)) {
493 paddr = (UINTPTR)LOS_PaddrQuery((UINT32 *)userVaddr);
494 if (paddr == 0) return LOS_NOK;
495 }
496
497 return LOS_OK;
498 }
499
OsFutexWaitParamCheck(const UINT32 * userVaddr,UINT32 flags,UINT32 absTime)500 STATIC INT32 OsFutexWaitParamCheck(const UINT32 *userVaddr, UINT32 flags, UINT32 absTime)
501 {
502 VADDR_T vaddr = (VADDR_T)(UINTPTR)userVaddr;
503
504 if (OS_INT_ACTIVE) {
505 return LOS_EINTR;
506 }
507
508 if (flags & (~FUTEX_PRIVATE)) {
509 PRINT_ERR("Futex wait param check failed! error flags: 0x%x\n", flags);
510 return LOS_EINVAL;
511 }
512
513 if ((vaddr % sizeof(INT32)) || (vaddr < OS_FUTEX_KEY_BASE) || (vaddr >= OS_FUTEX_KEY_MAX)) {
514 PRINT_ERR("Futex wait param check failed! error userVaddr: 0x%x\n", vaddr);
515 return LOS_EINVAL;
516 }
517
518 if (flags && (OsFutexKeyShmPermCheck(userVaddr, flags) != LOS_OK)) {
519 PRINT_ERR("Futex wait param check failed! error shared memory perm userVaddr: 0x%x\n", userVaddr);
520 return LOS_EINVAL;
521 }
522
523 if (!absTime) {
524 return LOS_ETIMEDOUT;
525 }
526
527 return LOS_OK;
528 }
529
OsFutexDeleteTimeoutTaskNode(FutexHash * hashNode,FutexNode * node)530 STATIC INT32 OsFutexDeleteTimeoutTaskNode(FutexHash *hashNode, FutexNode *node)
531 {
532 UINT32 intSave;
533 if (OsFutexLock(&hashNode->listLock)) {
534 return LOS_EINVAL;
535 }
536
537 if (node->index < FUTEX_INDEX_MAX) {
538 SCHEDULER_LOCK(intSave);
539 (VOID)OsFutexDeleteAlreadyWakeTaskAndGetNext(node, NULL, TRUE);
540 SCHEDULER_UNLOCK(intSave);
541 }
542
543 #ifdef LOS_FUTEX_DEBUG
544 OsFutexHashShow();
545 #endif
546
547 if (OsFutexUnlock(&hashNode->listLock)) {
548 return LOS_EINVAL;
549 }
550 return LOS_ETIMEDOUT;
551 }
552
OsFutexInsertTaskToHash(LosTaskCB ** taskCB,FutexNode ** node,const UINTPTR futexKey,const UINT32 flags)553 STATIC INT32 OsFutexInsertTaskToHash(LosTaskCB **taskCB, FutexNode **node, const UINTPTR futexKey, const UINT32 flags)
554 {
555 INT32 ret;
556 *taskCB = OsCurrTaskGet();
557 *node = &((*taskCB)->futex);
558 OsFutexSetKey(futexKey, flags, *node);
559
560 ret = OsFindAndInsertToHash(*node);
561 if (ret) {
562 return LOS_NOK;
563 }
564
565 LOS_ListInit(&((*node)->pendList));
566 return LOS_OK;
567 }
568
OsFutexWaitTask(const UINT32 * userVaddr,const UINT32 flags,const UINT32 val,const UINT32 timeout)569 STATIC INT32 OsFutexWaitTask(const UINT32 *userVaddr, const UINT32 flags, const UINT32 val, const UINT32 timeout)
570 {
571 INT32 futexRet;
572 UINT32 intSave, lockVal;
573 LosTaskCB *taskCB = NULL;
574 FutexNode *node = NULL;
575 UINTPTR futexKey = OsFutexFlagsToKey(userVaddr, flags);
576 UINT32 index = OsFutexKeyToIndex(futexKey, flags);
577 FutexHash *hashNode = &g_futexHash[index];
578
579 if (OsFutexLock(&hashNode->listLock)) {
580 return LOS_EINVAL;
581 }
582
583 if (LOS_ArchCopyFromUser(&lockVal, userVaddr, sizeof(UINT32))) {
584 PRINT_ERR("Futex wait param check failed! copy from user failed!\n");
585 futexRet = LOS_EINVAL;
586 goto EXIT_ERR;
587 }
588
589 if (lockVal != val) {
590 futexRet = LOS_EBADF;
591 goto EXIT_ERR;
592 }
593
594 if (OsFutexInsertTaskToHash(&taskCB, &node, futexKey, flags)) {
595 futexRet = LOS_NOK;
596 goto EXIT_ERR;
597 }
598
599 SCHEDULER_LOCK(intSave);
600 OsSchedLock();
601 OsTaskWaitSetPendMask(OS_TASK_WAIT_FUTEX, futexKey, timeout);
602 taskCB->ops->wait(taskCB, &(node->pendList), timeout);
603 LOS_SpinUnlock(&g_taskSpin);
604
605 futexRet = OsFutexUnlock(&hashNode->listLock);
606 if (futexRet) {
607 OsSchedUnlock();
608 LOS_IntRestore(intSave);
609 goto EXIT_UNLOCK_ERR;
610 }
611
612 LOS_SpinLock(&g_taskSpin);
613 OsSchedUnlock();
614
615 /*
616 * it will immediately do the scheduling, so there's no need to release the
617 * task spinlock. when this task's been rescheduled, it will be holding the spinlock.
618 */
619 OsSchedResched();
620
621 if (taskCB->taskStatus & OS_TASK_STATUS_TIMEOUT) {
622 taskCB->taskStatus &= ~OS_TASK_STATUS_TIMEOUT;
623 SCHEDULER_UNLOCK(intSave);
624 return OsFutexDeleteTimeoutTaskNode(hashNode, node);
625 }
626
627 SCHEDULER_UNLOCK(intSave);
628 return LOS_OK;
629
630 EXIT_ERR:
631 (VOID)OsFutexUnlock(&hashNode->listLock);
632 EXIT_UNLOCK_ERR:
633 return futexRet;
634 }
635
OsFutexWait(const UINT32 * userVaddr,UINT32 flags,UINT32 val,UINT32 absTime)636 INT32 OsFutexWait(const UINT32 *userVaddr, UINT32 flags, UINT32 val, UINT32 absTime)
637 {
638 INT32 ret;
639 UINT32 timeout = LOS_WAIT_FOREVER;
640
641 ret = OsFutexWaitParamCheck(userVaddr, flags, absTime);
642 if (ret) {
643 return ret;
644 }
645 if (absTime != LOS_WAIT_FOREVER) {
646 timeout = OsNS2Tick((UINT64)absTime * OS_SYS_NS_PER_US);
647 }
648
649 return OsFutexWaitTask(userVaddr, flags, val, timeout);
650 }
651
OsFutexWakeParamCheck(const UINT32 * userVaddr,UINT32 flags)652 STATIC INT32 OsFutexWakeParamCheck(const UINT32 *userVaddr, UINT32 flags)
653 {
654 VADDR_T vaddr = (VADDR_T)(UINTPTR)userVaddr;
655
656 if ((flags & (~FUTEX_PRIVATE)) != FUTEX_WAKE) {
657 PRINT_ERR("Futex wake param check failed! error flags: 0x%x\n", flags);
658 return LOS_EINVAL;
659 }
660
661 if ((vaddr % sizeof(INT32)) || (vaddr < OS_FUTEX_KEY_BASE) || (vaddr >= OS_FUTEX_KEY_MAX)) {
662 PRINT_ERR("Futex wake param check failed! error userVaddr: 0x%x\n", userVaddr);
663 return LOS_EINVAL;
664 }
665
666 if (flags && (OsFutexKeyShmPermCheck(userVaddr, flags) != LOS_OK)) {
667 PRINT_ERR("Futex wake param check failed! error shared memory perm userVaddr: 0x%x\n", userVaddr);
668 return LOS_EINVAL;
669 }
670
671 return LOS_OK;
672 }
673
674 /* Check to see if the task to be awakened has timed out
675 * if time out, to weak next pend task.
676 */
OsFutexCheckAndWakePendTask(FutexNode * headNode,const INT32 wakeNumber,FutexHash * hashNode,FutexNode ** nextNode,BOOL * wakeAny)677 STATIC VOID OsFutexCheckAndWakePendTask(FutexNode *headNode, const INT32 wakeNumber,
678 FutexHash *hashNode, FutexNode **nextNode, BOOL *wakeAny)
679 {
680 INT32 count;
681 LosTaskCB *taskCB = NULL;
682 FutexNode *node = headNode;
683 for (count = 0; count < wakeNumber; count++) {
684 /* Ensure the integrity of the head */
685 *nextNode = OsFutexDeleteAlreadyWakeTaskAndGetNext(node, NULL, FALSE);
686 if (*nextNode == NULL) {
687 /* The last node in queuelist is invalid or the entire list is invalid */
688 return;
689 }
690 node = *nextNode;
691 taskCB = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(node->pendList)));
692 OsTaskWakeClearPendMask(taskCB);
693 taskCB->ops->wake(taskCB);
694 *wakeAny = TRUE;
695 *nextNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_FIRST(&(node->queueList)));
696 if (node != headNode) {
697 OsFutexDeinitFutexNode(node);
698 }
699
700 if (LOS_ListEmpty(&headNode->queueList)) {
701 /* Wakes up the entire linked list node */
702 *nextNode = NULL;
703 return;
704 }
705
706 node = *nextNode;
707 }
708 return;
709 }
710
OsFutexWakeTask(UINTPTR futexKey,UINT32 flags,INT32 wakeNumber,FutexNode ** newHeadNode,BOOL * wakeAny)711 STATIC INT32 OsFutexWakeTask(UINTPTR futexKey, UINT32 flags, INT32 wakeNumber, FutexNode **newHeadNode, BOOL *wakeAny)
712 {
713 UINT32 intSave;
714 FutexNode *node = NULL;
715 FutexNode *headNode = NULL;
716 UINT32 index = OsFutexKeyToIndex(futexKey, flags);
717 FutexHash *hashNode = &g_futexHash[index];
718 FutexNode tempNode = {
719 .key = futexKey,
720 .index = index,
721 .pid = (flags & FUTEX_PRIVATE) ? LOS_GetCurrProcessID() : OS_INVALID,
722 };
723
724 node = OsFindFutexNode(&tempNode);
725 if (node == NULL) {
726 return LOS_EBADF;
727 }
728
729 headNode = node;
730
731 SCHEDULER_LOCK(intSave);
732 OsFutexCheckAndWakePendTask(headNode, wakeNumber, hashNode, newHeadNode, wakeAny);
733 if ((*newHeadNode) != NULL) {
734 OsFutexReplaceQueueListHeadNode(headNode, *newHeadNode);
735 OsFutexDeinitFutexNode(headNode);
736 } else if (headNode->index < FUTEX_INDEX_MAX) {
737 OsFutexDeleteKeyFromFutexList(headNode);
738 OsFutexDeinitFutexNode(headNode);
739 }
740 SCHEDULER_UNLOCK(intSave);
741
742 return LOS_OK;
743 }
744
OsFutexWake(const UINT32 * userVaddr,UINT32 flags,INT32 wakeNumber)745 INT32 OsFutexWake(const UINT32 *userVaddr, UINT32 flags, INT32 wakeNumber)
746 {
747 INT32 ret, futexRet;
748 UINTPTR futexKey;
749 UINT32 index;
750 FutexHash *hashNode = NULL;
751 FutexNode *headNode = NULL;
752 BOOL wakeAny = FALSE;
753
754 if (OsFutexWakeParamCheck(userVaddr, flags)) {
755 return LOS_EINVAL;
756 }
757
758 futexKey = OsFutexFlagsToKey(userVaddr, flags);
759 index = OsFutexKeyToIndex(futexKey, flags);
760
761 hashNode = &g_futexHash[index];
762 if (OsFutexLock(&hashNode->listLock)) {
763 return LOS_EINVAL;
764 }
765
766 ret = OsFutexWakeTask(futexKey, flags, wakeNumber, &headNode, &wakeAny);
767 if (ret) {
768 goto EXIT_ERR;
769 }
770
771 #ifdef LOS_FUTEX_DEBUG
772 OsFutexHashShow();
773 #endif
774
775 futexRet = OsFutexUnlock(&hashNode->listLock);
776 if (futexRet) {
777 goto EXIT_UNLOCK_ERR;
778 }
779
780 if (wakeAny == TRUE) {
781 LOS_MpSchedule(OS_MP_CPU_ALL);
782 LOS_Schedule();
783 }
784
785 return LOS_OK;
786
787 EXIT_ERR:
788 futexRet = OsFutexUnlock(&hashNode->listLock);
789 EXIT_UNLOCK_ERR:
790 if (futexRet) {
791 return futexRet;
792 }
793 return ret;
794 }
795
OsFutexRequeueInsertNewKey(UINTPTR newFutexKey,INT32 newIndex,FutexNode * oldHeadNode)796 STATIC INT32 OsFutexRequeueInsertNewKey(UINTPTR newFutexKey, INT32 newIndex, FutexNode *oldHeadNode)
797 {
798 BOOL queueListIsEmpty = FALSE;
799 INT32 ret;
800 UINT32 intSave;
801 LosTaskCB *task = NULL;
802 FutexNode *nextNode = NULL;
803 FutexNode newTempNode = {
804 .key = newFutexKey,
805 .index = newIndex,
806 .pid = (newIndex < FUTEX_INDEX_SHARED_POS) ? LOS_GetCurrProcessID() : OS_INVALID,
807 };
808 LOS_DL_LIST *queueList = &oldHeadNode->queueList;
809 FutexNode *newHeadNode = OsFindFutexNode(&newTempNode);
810 if (newHeadNode == NULL) {
811 OsFutexInsertNewFutexKeyToHash(oldHeadNode);
812 return LOS_OK;
813 }
814
815 do {
816 nextNode = OS_FUTEX_FROM_QUEUELIST(queueList);
817 SCHEDULER_LOCK(intSave);
818 if (LOS_ListEmpty(&nextNode->pendList)) {
819 if (LOS_ListEmpty(queueList)) {
820 queueListIsEmpty = TRUE;
821 } else {
822 queueList = queueList->pstNext;
823 }
824 OsFutexDeinitFutexNode(nextNode);
825 SCHEDULER_UNLOCK(intSave);
826 if (queueListIsEmpty) {
827 return LOS_OK;
828 }
829
830 continue;
831 }
832
833 task = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(nextNode->pendList)));
834 if (LOS_ListEmpty(queueList)) {
835 queueListIsEmpty = TRUE;
836 } else {
837 queueList = queueList->pstNext;
838 }
839 LOS_ListDelete(&nextNode->queueList);
840 ret = OsFutexInsertTasktoPendList(&newHeadNode, nextNode, task);
841 SCHEDULER_UNLOCK(intSave);
842 if (ret != LOS_OK) {
843 PRINT_ERR("Futex requeue insert new key failed!\n");
844 }
845 } while (!queueListIsEmpty);
846
847 return LOS_OK;
848 }
849
OsFutexRequeueSplitTwoLists(FutexHash * oldHashNode,FutexNode * oldHeadNode,UINT32 flags,UINTPTR futexKey,INT32 count)850 STATIC VOID OsFutexRequeueSplitTwoLists(FutexHash *oldHashNode, FutexNode *oldHeadNode,
851 UINT32 flags, UINTPTR futexKey, INT32 count)
852 {
853 LOS_DL_LIST *queueList = &oldHeadNode->queueList;
854 FutexNode *tailNode = OS_FUTEX_FROM_QUEUELIST(LOS_DL_LIST_LAST(queueList));
855 INT32 newIndex = OsFutexKeyToIndex(futexKey, flags);
856 FutexNode *nextNode = NULL;
857 FutexNode *newHeadNode = NULL;
858 LOS_DL_LIST *futexList = NULL;
859 BOOL isAll = FALSE;
860 INT32 i;
861
862 for (i = 0; i < count; i++) {
863 nextNode = OS_FUTEX_FROM_QUEUELIST(queueList);
864 nextNode->key = futexKey;
865 nextNode->index = newIndex;
866 if (queueList->pstNext == &oldHeadNode->queueList) {
867 isAll = TRUE;
868 break;
869 }
870
871 queueList = queueList->pstNext;
872 }
873
874 futexList = oldHeadNode->futexList.pstPrev;
875 LOS_ListDelete(&oldHeadNode->futexList);
876 if (isAll == TRUE) {
877 return;
878 }
879
880 newHeadNode = OS_FUTEX_FROM_QUEUELIST(queueList);
881 LOS_ListHeadInsert(futexList, &newHeadNode->futexList);
882 oldHeadNode->queueList.pstPrev = &nextNode->queueList;
883 nextNode->queueList.pstNext = &oldHeadNode->queueList;
884 newHeadNode->queueList.pstPrev = &tailNode->queueList;
885 tailNode->queueList.pstNext = &newHeadNode->queueList;
886 return;
887 }
888
OsFutexRequeueRemoveOldKeyAndGetHead(UINTPTR oldFutexKey,UINT32 flags,INT32 wakeNumber,UINTPTR newFutexKey,INT32 requeueCount,BOOL * wakeAny)889 STATIC FutexNode *OsFutexRequeueRemoveOldKeyAndGetHead(UINTPTR oldFutexKey, UINT32 flags, INT32 wakeNumber,
890 UINTPTR newFutexKey, INT32 requeueCount, BOOL *wakeAny)
891 {
892 INT32 ret;
893 INT32 oldIndex = OsFutexKeyToIndex(oldFutexKey, flags);
894 FutexNode *oldHeadNode = NULL;
895 FutexHash *oldHashNode = &g_futexHash[oldIndex];
896 FutexNode oldTempNode = {
897 .key = oldFutexKey,
898 .index = oldIndex,
899 .pid = (flags & FUTEX_PRIVATE) ? LOS_GetCurrProcessID() : OS_INVALID,
900 };
901
902 if (wakeNumber > 0) {
903 ret = OsFutexWakeTask(oldFutexKey, flags, wakeNumber, &oldHeadNode, wakeAny);
904 if ((ret != LOS_OK) || (oldHeadNode == NULL)) {
905 return NULL;
906 }
907 }
908
909 if (requeueCount <= 0) {
910 return NULL;
911 }
912
913 if (oldHeadNode == NULL) {
914 oldHeadNode = OsFindFutexNode(&oldTempNode);
915 if (oldHeadNode == NULL) {
916 return NULL;
917 }
918 }
919
920 OsFutexRequeueSplitTwoLists(oldHashNode, oldHeadNode, flags, newFutexKey, requeueCount);
921
922 return oldHeadNode;
923 }
924
OsFutexRequeueParamCheck(const UINT32 * oldUserVaddr,UINT32 flags,const UINT32 * newUserVaddr)925 STATIC INT32 OsFutexRequeueParamCheck(const UINT32 *oldUserVaddr, UINT32 flags, const UINT32 *newUserVaddr)
926 {
927 VADDR_T oldVaddr = (VADDR_T)(UINTPTR)oldUserVaddr;
928 VADDR_T newVaddr = (VADDR_T)(UINTPTR)newUserVaddr;
929
930 if (oldVaddr == newVaddr) {
931 return LOS_EINVAL;
932 }
933
934 if ((flags & (~FUTEX_PRIVATE)) != FUTEX_REQUEUE) {
935 PRINT_ERR("Futex requeue param check failed! error flags: 0x%x\n", flags);
936 return LOS_EINVAL;
937 }
938
939 if ((oldVaddr % sizeof(INT32)) || (oldVaddr < OS_FUTEX_KEY_BASE) || (oldVaddr >= OS_FUTEX_KEY_MAX)) {
940 PRINT_ERR("Futex requeue param check failed! error old userVaddr: 0x%x\n", oldUserVaddr);
941 return LOS_EINVAL;
942 }
943
944 if ((newVaddr % sizeof(INT32)) || (newVaddr < OS_FUTEX_KEY_BASE) || (newVaddr >= OS_FUTEX_KEY_MAX)) {
945 PRINT_ERR("Futex requeue param check failed! error new userVaddr: 0x%x\n", newUserVaddr);
946 return LOS_EINVAL;
947 }
948
949 return LOS_OK;
950 }
951
OsFutexRequeue(const UINT32 * userVaddr,UINT32 flags,INT32 wakeNumber,INT32 count,const UINT32 * newUserVaddr)952 INT32 OsFutexRequeue(const UINT32 *userVaddr, UINT32 flags, INT32 wakeNumber, INT32 count, const UINT32 *newUserVaddr)
953 {
954 INT32 ret;
955 UINTPTR oldFutexKey;
956 UINTPTR newFutexKey;
957 INT32 oldIndex;
958 INT32 newIndex;
959 FutexHash *oldHashNode = NULL;
960 FutexHash *newHashNode = NULL;
961 FutexNode *oldHeadNode = NULL;
962 BOOL wakeAny = FALSE;
963
964 if (OsFutexRequeueParamCheck(userVaddr, flags, newUserVaddr)) {
965 return LOS_EINVAL;
966 }
967
968 oldFutexKey = OsFutexFlagsToKey(userVaddr, flags);
969 newFutexKey = OsFutexFlagsToKey(newUserVaddr, flags);
970 oldIndex = OsFutexKeyToIndex(oldFutexKey, flags);
971 newIndex = OsFutexKeyToIndex(newFutexKey, flags);
972
973 oldHashNode = &g_futexHash[oldIndex];
974 if (OsFutexLock(&oldHashNode->listLock)) {
975 return LOS_EINVAL;
976 }
977
978 oldHeadNode = OsFutexRequeueRemoveOldKeyAndGetHead(oldFutexKey, flags, wakeNumber, newFutexKey, count, &wakeAny);
979 if (oldHeadNode == NULL) {
980 (VOID)OsFutexUnlock(&oldHashNode->listLock);
981 if (wakeAny == TRUE) {
982 ret = LOS_OK;
983 goto EXIT;
984 }
985 return LOS_EBADF;
986 }
987
988 newHashNode = &g_futexHash[newIndex];
989 if (oldIndex != newIndex) {
990 if (OsFutexUnlock(&oldHashNode->listLock)) {
991 return LOS_EINVAL;
992 }
993
994 if (OsFutexLock(&newHashNode->listLock)) {
995 return LOS_EINVAL;
996 }
997 }
998
999 ret = OsFutexRequeueInsertNewKey(newFutexKey, newIndex, oldHeadNode);
1000
1001 if (OsFutexUnlock(&newHashNode->listLock)) {
1002 return LOS_EINVAL;
1003 }
1004
1005 EXIT:
1006 if (wakeAny == TRUE) {
1007 LOS_MpSchedule(OS_MP_CPU_ALL);
1008 LOS_Schedule();
1009 }
1010
1011 return ret;
1012 }
1013 #endif
1014
1015