The Master said, “When you eat and drink, when you bend your head and rest your head, happiness is also in it. Unjust and rich and precious, to me like clouds.” Analects of Confucius: A review

A hundred blog series. This paper is: the v19. Xx HongMeng kernel source code analysis (bitmap management articles) | who can be divided into two and a half a penny

The basic tools are:

  • V01. Xx HongMeng kernel source code analysis (two-way chain table) | who is the most important kernel structure
  • V19. Xx HongMeng kernel source code analysis (bitmap management) | who can be divided into two and a half to spend a penny
  • V20. Xx HongMeng kernel source code analysis (using stack) | programs run site provided by the who
  • V31. Xx HongMeng kernel source code analysis (timer) | which task of top priority
  • V34. Xx HongMeng kernel source code analysis (atomic) | who escort for atomic operations
  • V35. Xx HongMeng kernel source code analysis (time management) | who is a basic unit of time the kernel

Let’s start with four macro definitions: process and thread (a thread is a task) highest and lowest priority definitions. The range [0,31] is 32 levels. Priority is used for scheduling, and the CPU uses this to decide which process and task to run first.

#define OS_PROCESS_PRIORITY_HIGHEST      0 // The process has the highest priority
#define OS_PROCESS_PRIORITY_LOWEST       31 // The process has the lowest priority
#define OS_TASK_PRIORITY_HIGHEST    0 // The task has the highest priority. The soft clock task is the highest priority. See OsSwtmrTaskCreate
#define OS_TASK_PRIORITY_LOWEST     31 // The task has the lowest priority
Copy the code

Why do processes and threads have 32 priorities?

Before we answer that question, let’s answer another question: why do almost all human civilizations count in the decimal system? The answer is to count your fingers, because you have ten fingers. The Mayan twenty decimal notation that’s counting toes, but it’s also a decimal notation.

Does this show that cognition is influenced by the environment and the direction is what is easy/convenient. This could also explain why human languages, including dialects, sound similar to the word “mama,” because it’s easiest for a baby to say mama. This is important to realize!

And the computer world is binary, right and wrong, very clear, very simple, binary is as simple as it can be, after all, it couldn’t be simpler. Remember the bidirectional linked list said, because it is simple so it is not simple ah, if the avenue is simple, the computer will rely on this 01 code, the expression of thousands of world.

But the human brain is not good at storage, binary too long count up to 100 brain burst, remember, in order to memory and operation is convenient, commonly used programming near the decimal hexadecimal, 0 x9527abcd looked at a much more comfortable than in 0011000111100101010100111.

What are the differences between application development and kernel development?

Difference is very big still, only speak a little, here is the registration control ability, the kernel will appear a lot of bitwise operations (&, |, ~, ^), a variable of a express different meanings, but this in the application programmer that is rarely seen, they use is more of a logic operations, &&, | |,!)

#define OS_TASK_STATUS_INIT         0x0001U // Initialization state
#define OS_TASK_STATUS_READY        0x0002U // All ready tasks will be inserted into the ready queue
#define OS_TASK_STATUS_RUNNING      0x0004U // Running status
#define OS_TASK_STATUS_SUSPEND      0x0008U // Suspend state
#define OS_TASK_STATUS_PEND         0x0010U // Block
Copy the code

This is a representation of the various states of the task, which can be reduced to binary:

0000000000000001 = 0x0001U

0000000000000010 = 0x0002U

0000000000000100 = 0x0004U

0000000000001000 = 0x0008U

0000000000010000 = 0x0010U

See if there’s a difference on the binary side, where each bit represents a different state, 1 for yes, 0 for no.

The benefits are twofold:

1. Multiple tags can exist at the same time, such as 0x07 = 0B00000111, corresponding to the above task has three tags (initial, ready, and running), processes and threads are allowed to have multiple tags at the same time during running.

2. To save space, one variable is done. If an application programmer wants to implement three tags at the same time, it is customary to define three variables, because your exclusivity granularity is a variable and not a bit.

For bitwise management/operations, a dedicated manager is required: bitmap manager (see source los_bitmap.c).

What is a bitmap manager?

Directly on the part of the code, the code has added Chinese annotations in key places, simply speaking, is a variety of operations, such as how to set 1 in a certain bit? How do you figure out which position is the highest one? These functions are very useful.

// Set a flag bit of the status word to 1
VOID LOS_BitmapSet(UINT32 *bitmap, UINT16 pos)
{
    if (bitmap == NULL) {
        return;
    }

    *bitmap |= 1U << (pos & OS_BITMAP_MASK);// set the corresponding bit to 1
}
// Clear 0 for a flag bit of the status word
VOID LOS_BitmapClr(UINT32 *bitmap, UINT16 pos)
{
    if (bitmap == NULL) {
        return;
    }

    *bitmap &= ~(1U << (pos & OS_BITMAP_MASK));// set the corresponding bit to 0
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * miscellaneous arithmetic instruction CLZ operands are used to calculate the number of high-end 0, This instruction is mainly used for the two occasions to calculate operands standardization (at its highest level for 1) need to shift to the left of the digits to determine a priority mask the highest priority in the * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
// Get the highest bit of 1 in the status word for example: 00110110 return 5
UINT16 LOS_HighBitGet(UINT32 bitmap)
{
    if (bitmap == 0) {
        return LOS_INVALID_BIT_INDEX;
    }

    return (OS_BITMAP_MASK - CLZ(bitmap));
}
// Get the lowest value of 1 in the status word, for example, 00110110 returns 2
UINT16 LOS_LowBitGet(UINT32 bitmap)
{
    if (bitmap == 0) {
        return LOS_INVALID_BIT_INDEX;
    }

    return CTZ(bitmap);//
}


Copy the code

Where are bitmaps used?

A lot of modules in the kernel use bitmaps. I’m only talking about process and thread modules. Remember the question from the beginning, why are processes and threads 32 priorities? Their priority is managed by a bitmap, which manages a UINT32 variable. Therefore, they are 32 levels, with the highest bit having the lowest priority.

    UINT32          priBitMap;          /**< BitMap for recording the change of task priority, The priority can not be greater than 31 */   // The priority of the pass, for example.. 01001011 used to have priority 0,1,3,6


Copy the code

This is the definition of the scheduling priority bitmap in the task control block. Note that the priority of a task is not fixed during execution, and the kernel can change it according to the execution. This variable is used to keep a history of all priorities that the task has ever had.

For example, the priority bitmap of task A is 00000001001011. It can be seen that it has four scheduling level records. What if you want to know the lowest priority record?

UINT16 LOS_HighBitGet(UINT32 bitmap) UINT16 LOS_HighBitGet(UINT32 bitmap

Since task priority 0 is the highest, what it ultimately means is that task A has the lowest priority of 6 ever

Be sure to understand bitmap manipulation. There is a lot of this code in the kernel, especially in the assembly layer, where manipulation of registers occurs a lot.

Take this piece of assembly code.

MSR CPSR_c, # (CPSR_INT_DISABLE | CPSR_SVC_MODE) @ disabling interrupts and cut to the management mode of LDRH R1, [R0, #4] @ set the memory address to R0+4The low16Bit data is read into register R1 and R1 is high16A reset ORR R1, R1 = # OS_TASK_STATUS_RUNNING @ or instructions R1 | OS_TASK_STATUS_RUNNING STRH R1, [R0, #4] @ Lower register R116Bit writes with R0+4Is the address in memoryCopy the code

Programming instance

To implement bit operation on data, this example realizes the following functions:

  • A certain flag position 1.
  • Gets the highest bit with flag bit 1.
  • A flag bit is clear 0.
  • Gets the lowest bit with flag bit 1.
#include "los_bitmap.h"
#include "los_printf.h"

static UINT32 Bit_Sample(VOID)
{
  UINT32 flag = 0x10101010;
  UINT16 pos;

  dprintf("\nBitmap Sample! \n");
  dprintf("The flag is 0x%8x\n"The flag); pos =8;
  LOS_BitmapSet(& flag, pos);dprintf("LOS_BitmapSet:\t pos: %d, the flag is 0x%0+8x\n", pos, flag); pos =LOS_HighBitGet(flag);
  dprintf("LOS_HighBitGet:\t The highest one bit is %d, the flag is 0x%0+8x\n", pos, flag);LOS_BitmapClr(& flag, pos);dprintf("LOS_BitmapClr:\t pos: %d, the flag is 0x%0+8x\n", pos, flag); pos =LOS_LowBitGet(flag);
  dprintf("LOS_LowBitGet:\t The lowest one bit is %d, the flag is 0x%0+8x\n\n", pos, flag);return LOS_OK;
}
Copy the code

results

Bitmap Sample!
The flag is 0x10101010
LOS_BitmapSet: pos : 8The flag is0x10101110
LOS_HighBitGet:The highest one bit is 28The flag is0x10101110
LOS_BitmapClr: pos : 28The flag is0x00101110
LOS_LowBitGet: The lowest one bit is 4The flag is0x00101110
Copy the code

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.

Compile build The fundamental tools Loading operation Process management
Compile environment

The build process

Environment script

Build tools

Designed.the gn application

Ninja ninja

Two-way linked list

Bitmap management

In the stack way

The timer

Atomic operation

Time management

The ELF format

The ELF parsing

Static link

relocation

Process image

Process management

Process concept

Fork

Special process

Process recycling

Signal production

Signal consumption

Shell editor

Shell parsing

Process of communication Memory management Ins and outs Task management
spinlocks

The mutex

Process of communication

A semaphore

Incident control

The message queue

Memory allocation

Memory management

Memory assembly

The memory mapping

Rules of memory

Physical memory

Total directory

Scheduling the story

Main memory slave

The source code comments

Source structure

Static site

The clock task

Task scheduling

Task management

The scheduling queue

Scheduling mechanism

Thread concept

Concurrent parallel

The system calls

Task switching

The file system Hardware architecture
File concept

The file system

The index node

Mount the directory

Root file system

Character device

VFS

File handle

Pipeline file

Compilation basis

Assembly and the cords

Working mode

register

Anomaly over

Assembly summary

Interrupt switch

Interrupt concept

Interrupt management

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