HongMeng kernel source code analysis (mutex) | than full spinlock mutex OpenHarmony source | | best blog analysis v27.03

The Master said, “Crazy but not straight, dong but unwilling, 悾悾 but unconvinced, I do not know.” The Analects of Confucius: Tabor

A hundred blog series. This is: v27. Xx HongMeng kernel source code analysis (mutex) | than full spinlock mutex

Process communication related articles are:

• V26. Xx HongMeng kernel source code analysis (spinlocks) | when chastity memorial arch good comrade
• V27. Xx HongMeng kernel source code analysis (mutex) | than full spinlock mutex
• V28. Xx HongMeng kernel source code analysis (process) | took nine interprocess communication speed
• V29. Xx HongMeng kernel source code analysis (semaphore) | who is responsible for solving task synchronization
• V30. Xx HongMeng kernel source code analysis control (events) | intertask synchronization scheme of many-to-many
• V33. Xx HongMeng kernel source code analysis (message queue) | how to asynchronous communication between processes the data

This article explains mutex

Where in the kernel are mutex used? Look at the picture:

In this picture, the kernel module initializes the mutex, has files, has memory, uses the message queue, and so on, uses the very wide range. In fact, in the process of annotating the kernel source code, you will see a large number of spin locks and mutex, their existence in order to ensure the normal operation of the kernel and application. Is a very basic and important function.

An overview of the

Spin-locks and mutex are both locks, but solve different problems. Spin-locks solve the race for shared memory between CPU cores, while mutex solves the race for shared memory between threads (tasks).

A spin lock is a feature that the CPU is busy waiting for another CPU to release the resource. Therefore, the shared code segment should not be too complex, otherwise it is prone to deadlock, shock.

The feature of a mutex is that the original task is blocked when the lock is not obtained, and a new task is switched to run. The CPU will always run. It’s easy to think of a few questions:

First, there will be many tasks in the same lock situation, because switching new tasks may also be blocked by the same lock, and the CPU is switched to new tasks. This creates an equal-lock linked list.

Second: can the party who holds the lock apply for the same lock again successfully? The answer is yes, this type of locking is called recursive locking and is the default mode of the hongmeng kernel.

Third: when A task with A high priority fails to lock, it actively lets the CPU go to sleep. What if B task with A lock has A low priority and cannot wait for the task to run and cannot release the lock? The answer is that the task priority of B is temporarily adjusted to be as high as that of A, so that B can be quickly dispatched, and when B releases the lock, its priority is reversed. So the priority of a task will rise and fall depending on the situation.

Fourth: after task B releases the lock, it should actively wake up the linked list of tasks with equal locks so that they can join the ready queue and wait to be scheduled. The scheduling algorithm is non-discriminatory, it only looks at priority.

With these problems, into the hongmeng kernel mutex implementation code, this code is large, each line of code is annotated.

What does a mutex look like?

enum {
    LOS_MUX_PRIO_NONE = 0.// Thread priority and scheduling are not affected by mutex, first come first served, normal queuing.
    LOS_MUX_PRIO_INHERIT = 1.// While the higher-priority thread waits for the lower-priority thread to release the lock, the lower-priority thread runs at the higher-priority thread's priority.
           // When a thread unlocks a mutex, its priority is automatically restored to its original priority
    LOS_MUX_PRIO_PROTECT = 2 // See the notes in OsMuxPendOp that specify the meaning of LOS_MUX_PRIO_PROTECT
};
enum {
    LOS_MUX_NORMAL = 0.// A non-recursive lock has only [0.1] two states. No special error detection is performed, and no deadlock detection is performed.
    LOS_MUX_RECURSIVE = 1.Recursive locking allows the same thread to lock the mutex multiple times before it is unlocked. A recursive mutex maintains the count of locks. If the number of unlocked and locked times is different, the lock is not released, and no other thread can lock the mutex.
    LOS_MUX_ERRORCHECK = 2.// Error checking. If a thread attempts to relock a locked mutex or unlock an unlocked mutex, an error is returned.
    LOS_MUX_DEFAULT = LOS_MUX_RECURSIVE // Recursive locking is used by default
};
typedef struct { // Mutex attributes
    UINT8 protocol;  / / agreement
    UINT8 prioceiling; // Priority upper limit
    UINT8 type;   // Type attributes
    UINT8 reserved;  // Reserve the field
} LosMuxAttr;

typedef struct OsMux { // Mutex structure
    UINT32 magic;        /**< magic number */  // Magic number
    LosMuxAttr attr;     /**< Mutex attribute */ // Mutex attribute
    LOS_DL_LIST holdList; /**< The task holding the lock change */ // When a task holds the lock, attach it to the task's chain list via the holdList node
    LOS_DL_LIST muxList; /**< Mutex linked list */ // This is a holdList of tasks.
    VOID *owner;         /**< The current thread that is locking a mutex */ // The task that currently owns the lock
    UINT16 muxCount;     /**< Times of locking a mutex */ // The number of times a mutex is locked. Recursive locking is allowed multiple times
} LosMux;

Copy the code

This mutex is significantly longer than a spinlock, remember what spinlocks look like, with one variable, painfully thin.

Initialize the

LITE_OS_SEC_TEXT UINT32 LOS_MuxInit(LosMux * mutex,const LosMuxAttr *attr)
{   / /...
    SCHEDULER_LOCK(intSave);		// Get the scheduling spin lock
    mutex->muxCount = 0;			// The number of times the mutex was locked
    mutex->owner = NULL;			// The task that holds the lock
    LOS_ListInit(&mutex->muxList);	// Initializes the list of tasks waiting for the lock
    mutex->magic = OS_MUX_MAGIC;	// Fixed identifier, mutex magic number
    SCHEDULER_UNLOCK(intSave);		// Release the scheduling spin lock
    return LOS_OK;
}
Copy the code

Note that mutex->muxList is a bidirectional list, which is the most important element of the kernel. In the Linux kernel, list_head, as well as list_head, is a fixture of the host structure.

Three application modes

There are three modes for applying for a mutex: non-blocking mode, permanent blocking mode, and periodic blocking mode.

Non-blocking mode: When a task applies for a mutex, timeout is 0. If no task currently holds the mutex, or the task holding the mutex and the task applying for the mutex are the same, the application is successful. Otherwise, the application fails immediately.

Permanent blocking mode: When a task applies for a mutex, timeout is equal to 0xFFFFFFFF. If no task currently holds the mutex, the application is successful. Otherwise, the task enters the blocking state, and the system switches to the task with the highest priority in the ready task. After a task enters the blocking state, it cannot be executed again until another task releases the mutex.

Timed blocking mode: 0<timeout<0xFFFFFFFF when a task applies for a mutex. If no task currently holds the mutex, the application is successful. Otherwise, the task is blocked, and the system switches to the task with the highest priority. After a task enters the blocked state, if other tasks release the mutex before time out, the task can successfully obtain the mutex and continue to execute the task. If the mutex is not obtained before time out, the interface returns a timeout error code.

If any task is blocked by the mutex, the task with the highest priority is awakened, the task enters the ready state, and the task is scheduled. If no task is blocking the mutex, the mutex is released successfully.

Apply the mutex main function OsMuxPendOp

// The mutex body function, called by OsMuxlockUnsafe, one of the most important functions of the mutex module
// The worst case scenario is that the lock fails, the CPU is released, and the task becomes blocked, waiting for another task to release the lock and then execute it.
STATIC UINT32 OsMuxPendOp(LosTaskCB *runTask, LosMux * MUtex, UINT32 Timeout)
{
    UINT32 ret;
    LOS_DL_LIST *node = NULL;
    LosTaskCB *owner = NULL;

    if ((mutex->muxList.pstPrev == NULL) || (mutex->muxList.pstNext == NULL)) {// The list is empty
        /* This is for mutex macro initialization. */
        mutex->muxCount = 0;// lock counter clear 0
        mutex->owner = NULL;// The lock has no owning task
        LOS_ListInit(&mutex->muxList);// Initializes the lock task list, which will be attached to the subsequent application for this lock task
    }

    if (mutex->muxCount == 0) {// If no task uses a lock, you must get the lock. Return inside
        mutex->muxCount++;				// The mutex counter increases by 1
        mutex->owner = (VOID *)runTask;	// The current task is to get the lock
        LOS_ListTailInsert(& runTask - > lockList, & mutex - > holdList);// The task holding the lock has changed, and the node is attached to the current task's chain list
        if ((runTask->priority > mutex->attr.prioceiling) && (mutex->attr.protocol == LOS_MUX_PRIO_PROTECT)) {// How does the protection protocol work?
            LOS_BitmapSet(& runTask - > priBitMap runTask - > priority);//1. PriBitMap is a bitmap that records task priority changes. The current priority of the task is recorded in priBitMap
            OsTaskPriModify(runTask, mutex - > attr. Prioceiling);//2. Set mutex->attr. Prioceiling to the priority of the current task.
        }// Note that there are 32 task priorities, 0 is the highest and 31 is the lowest!! In this case, the priority of the task is increased, so that the probability of the task being selected continues to increase in the next schedule, so as to quickly release the lock.
        return LOS_OK;
    }
	// muxCount>0; // muxCount>0; The lock was taken by another mission
    if (((LosTaskCB *)mutex->owner == runTask) && (mutex->attr.type == LOS_MUX_RECURSIVE)) {// In the first case runTask is the lock holder
        mutex->muxCount++;	LOS_MUX_DEFAULT = LOS_MUX_RECURSIVE; LOS_MUX_DEFAULT = LOS_MUX_RECURSIVE; LOS_MUX_DEFAULT = LOS_MUX_RECURSIVE
        return LOS_OK;		// Exit successfully
    }
	// The current task can only be blocked.
    if(! timeout) {// The timeout parameter indicates how long to wait before picking up the lock
        return LOS_EINVAL;//timeout = 0 See LOS_MuxTrylock
    }
	// If you want to block, you can only apply for scheduling, freeing CPU core for other tasks
    if (!OsPreemptableInSched()) {// Can't apply for scheduling (can't schedule because no scheduling task spinlocks are held)
        return LOS_EDEADLK;// Return error, the spin lock is held by another CPU core
    }

    OsMuxBitmapSetMutex, runTask, (LosTaskCB *)mutex->owner);// Set the lock bitmap to increase the priority of lock holding task as much as possible

    owner = (LosTaskCB *)mutex->owner;	// Record the task holding the lock
    runTask->taskMux = (VOID *)mutex;	// Note that the current task is waiting for the lock
    node = OsMuxPendFindPos(runTask， mutex);// Find a task with a lower priority than the current task in the list of equal chains
    ret = OsTaskWait(node， timeout， TRUE);// The task is in the waiting state. TRUE indicates that the task needs to be scheduled
    if (ret == LOS_ERRNO_TSK_TIMEOUT) {// This line of code is next to OsTaskWait, but it takes a long time to execute because the CPU switches the task context in OsTaskWait
        runTask->taskMux = NULL;// So when I come back here, I may have run out of time
        ret = LOS_ETIMEDOUT;// Return timeout
    }

    if(timeout ! = LOS_WAIT_FOREVER) {// It is not a case of waiting forever
        OsMuxBitmapRestore(mutex， runTask， owner);// Restore the bitmap of the lock
    }

    return ret;
}
Copy the code

The main lock release function OsMuxPostOp

// Is there any other task holding the mutex blocking? If so, wake it up. Note that waking one task is done by another task
//OsMuxPostOp is only addressed by OsMuxUnlockUnsafe, the unlockbroadening task returns the lock, and the unlockbroadening task returns the lock
STATIC UINT32 OsMuxPostOp(LosTaskCB *taskCB， LosMux *mutex， BOOL *needSched)
{
    LosTaskCB *resumedTask = NULL;

    if (LOS_ListEmpty(&mutex->muxList)) {// If the mutex list is empty
        LOS_ListDelete(&mutex->holdList);// Remove the mutex
        mutex->owner = NULL;
        return LOS_OK;
    }

    resumedTask = OS_TCB_FROM_PENDLIST(LOS_DL_LIST_FIRST(&(mutex->muxList)));// Get the first task entity waiting for the mutex chain list, then wake up the task
    if (mutex->attr.protocol == LOS_MUX_PRIO_INHERIT) {// How does the mutex protocol work if it is inherited?
        if (resumedTask->priority > taskCB->priority) {// The priority of the task to get the lock is lower than that of the parameter task
            if (LOS_HighBitGet(taskCB->priBitMap) ! = resumedTask->priority) {// The lowest priority in the parameter task bitmap is not equal to the priority of the task waiting for the lock
                LOS_BitmapClr(& taskCB - > priBitMap resumedTask - > priority);// Record the priority of the task awaiting the task lock in the bitmap of the parameter task}}else if(taskCB->priBitMap ! =0) {// If the bitmap is not equal to 0, the parameter task has the priority of task scheduling at least
            OsMuxPostOpSub(taskCB， mutex);//
        }
    }
    mutex->muxCount = 1;// The number of mutex is 1
    mutex->owner = (VOID *)resumedTask;// The owner of the mutex has changed
    resumedTask->taskMux = NULL;//resumedTask no longer waits for the lock
    LOS_ListDelete(&mutex->holdList);// Remove yourself from the list of chains
    LOS_ListTailInsert(& resumedTask - > lockList, & mutex - > holdList);// Attach the lock to the recovery task's chain list. The lockList is all the lock records held by the task
    OsTaskWake(resumedTask);//resumedTask wakes up when it has the lock because it was in the pend state when it didn't get the lock
    if(needSched ! =NULL) {// If not empty
        *needSched = TRUE;// Start scheduling the process again
    }

    return LOS_OK;
}
Copy the code

Programming instance

This example implements the following flow.

• Task Example_TaskEntry creates a mutex, locks task scheduling, and creates two tasks Example_MutexTask1 and Example_MutexTask2. Example_MutexTask2 has a higher priority than Example_MutexTask1, unlocks task scheduling, and then Example_TaskEntry sleeps 300 ticks.
• Example_MutexTask2 is scheduled, applies for a mutex in permanent blocking mode, obtains the mutex successfully, then sleeps for 100 ticks, Example_MutexTask2 is suspended, and Example_MutexTask1 is woke up.
• Example_MutexTask1 applies for a mutex in timed blocking mode, waits 10Tick, because the mutex is still held by Example_MutexTask2, and Example_MutexTask1 is suspended. When the 10Tick time expires, Example_MutexTask1 is woken up and applies for a mutex in permanent blocking mode. The mutex is still held by Example_MutexTask2, and Example_MutexTask1 is suspended.
• 100Tick sleep time expires, Example_MutexTask2 is awakened, the mutex is released, and Example_MutexTask1 is awakened. Example_MutexTask1 successfully obtains a mutex, and releases the lock.
• After the 300Tick sleep period expires, task Example_TaskEntry is scheduled and run. The mutex is deleted and two tasks are deleted.

/* Mutex handle id */
UINT32 g_testMux;
/* Task ID */
UINT32 g_testTaskId01;
UINT32 g_testTaskId02;

VOID Example_MutexTask1(VOID)
{
    UINT32 ret;

    printf("Task1 try to get mutex, wait 10 ticks.\n");
    /* Request a mutex */
    ret = LOS_MuxPend(g_testMux,10);

    if (ret == LOS_OK) {
        printf("task1 get mutex g_testMux.\n");
        /* Release the mutex */
        LOS_MuxPost(g_testMux);
        return;
    } else if (ret == LOS_ERRNO_MUX_TIMEOUT ) {
            printf("task1 timeout and try to get mutex， wait forever.\n");
            /* Request a mutex */
            ret = LOS_MuxPend(g_testMux LOS_WAIT_FOREVER);if (ret == LOS_OK) {
                printf("task1 wait forever， get mutex g_testMux.\n");
                /* Release the mutex */
                LOS_MuxPost(g_testMux);
                return; }}return;
}

VOID Example_MutexTask2(VOID)
{
    printf("Task2 try to get mutex, wait forever.\n");
    /* Request a mutex */
    (VOID)LOS_MuxPend(g_testMux LOS_WAIT_FOREVER);printf("task2 get mutex g_testMux and suspend 100 ticks.\n");

    /* The task sleeps 100Ticks */
    LOS_TaskDelay(100);

    printf("task2 resumed and post the g_testMux\n");
    /* Release the mutex */
    LOS_MuxPost(g_testMux);
    return;
}

UINT32 Example_TaskEntry(VOID)
{
    UINT32 ret;
    TSK_INIT_PARAM_S task1;
    TSK_INIT_PARAM_S task2;

    /* Create a mutex */
    LOS_MuxCreate(&g_testMux);

    /* Lock task scheduling */
    LOS_TaskLock(a);/* Create task 1 */
    memset(& task1,0.sizeof(TSK_INIT_PARAM_S));
    task1.pfnTaskEntry = (TSK_ENTRY_FUNC)Example_MutexTask1;
    task1.pcName       = "MutexTsk1";
    task1.uwStackSize  = LOSCFG_BASE_CORE_TSK_DEFAULT_STACK_SIZE;
    task1.usTaskPrio   = 5;
    ret = LOS_TaskCreate(& g_testTaskId01, & task1);if(ret ! = LOS_OK) {printf("task1 create failed.\n");
        return LOS_NOK;
    }

    /* Create task 2 */
    memset(& task2,0.sizeof(TSK_INIT_PARAM_S));
    task2.pfnTaskEntry = (TSK_ENTRY_FUNC)Example_MutexTask2;
    task2.pcName       = "MutexTsk2";
    task2.uwStackSize  = LOSCFG_BASE_CORE_TSK_DEFAULT_STACK_SIZE;
    task2.usTaskPrio   = 4;
    ret = LOS_TaskCreate(& g_testTaskId02, & task2);if(ret ! = LOS_OK) {printf("task2 create failed.\n");
        return LOS_NOK;
    }

    /* Unlock task scheduling */
    LOS_TaskUnlock(a);/* Sleep 300Ticks */
    LOS_TaskDelay(300);

    /* Remove the mutex */
    LOS_MuxDelete(g_testMux);

    /* Delete task 1 */
    ret = LOS_TaskDelete(g_testTaskId01);
    if(ret ! = LOS_OK) {printf("task1 delete failed .\n");
        return LOS_NOK;
    }
    /* Delete task 2 */
    ret = LOS_TaskDelete(g_testTaskId02);
    if(ret ! = LOS_OK) {printf("task2 delete failed .\n");
        return LOS_NOK;
    }

    return LOS_OK;
}

Copy the code

results

task2 tryTo get mutex, wait forever. Task2 get mutex g_testMuxand suspend 100 ticks.
task1 tryTo get mutex, wait10 ticks.
task1 timeout and tryTo get mutex, wait forever. Task2 resumedandPost the g_testMux task1 wait forever, get mutex g_testMux.Copy the code

conclusion

1. Mutex solves the problem of competing for shared memory among tasks.

2. The task that fails to apply for the lock will enter the sleep OsTaskWait. The kernel will compare the priority of the task that holds the lock with that of the task that applies for the lock, and adjust the priority of the task that holds the lock as high as possible, so that it can be scheduled and executed more quickly and the lock can be released as soon as possible.

3. The lock release task will find a high-priority task in the chain list, wake it up through OsTaskWake, and apply for scheduling from the scheduling algorithm. However, it should be noted that the scheduling algorithm only schedules according to the priority, and does not guarantee that the scheduled task is the task to wake up.

4. The key is to understand OsMuxPendOp and OsMuxPostOp functions.

Intensive reading of the kernel source code

Four code stores synchronous annotation kernel source code, >> view the Gitee repository

Analysis of 100 blogs. Dig deep into the core

Add comments to hongmeng kernel source code process, sort out the following article. Content based on the source code, often in life scene analogy as much as possible into the kernel knowledge of a scene, with a pictorial sense, easy to understand memory. It’s important to speak in a way that others can understand! The 100 blogs are by no means a bunch of ridiculously difficult concepts being put forward by Baidu. That’s not interesting. More hope to make the kernel become lifelike, feel more intimate. It’s hard, it’s hard, but there’s no turning back. 😛 and code bugs need to be constantly debug, there will be many mistakes and omissions in the article and annotation content, please forgive, but will be repeatedly amended, continuous update. Xx represents the number of modifications, refined, concise and comprehensive, and strive to create high-quality content.

HongMeng station | into a little bit every day, the original is not easy, welcome to reprint, please indicate the source.