I just pressed 666 and something magical happened to the computer...

[[394490]]

There is a classic question in the computer field: What happens between the time you enter a URL in your browser and press Enter and the web page is rendered?

This question is used to test a candidate's understanding of computer networks, and therefore appears in countless interview situations.

There is no doubt that this is a good question, and I have seen no less than 100 articles exploring the answer to this question.

Today, I want to discuss another question with you: From the time you press a "6" on the keyboard to the time it is displayed on the screen, what happens to the computer?

This problem is much smaller than the original one in terms of both spatial and temporal scales.

In terms of spatial scale, this problem is only explored on one computer and does not cross the network.

In terms of time scale, the first question is on the order of seconds, while this question is on the order of milliseconds.

Although the scale is small, the technical knowledge behind it is not less.

I believe that after you finish reading this article and figure out the answer to this question, you will have a completely different understanding of computer composition principles, operating systems, and CPUs.

Get ready, let's go!

0x01: What the keyboard does when a key is pressed

Most early computers had PS2 interfaces, which are like this:

However, this type of interface is inconvenient to plug in and is not universal. In recent years, there are more and more USB interface keyboards, so we will take USB keyboards as the research object.

When you press a key on the keyboard, the circuit "switch" under the key position will be turned on. There is such a switch under each key, and they together form a matrix:

The global matrix looks like this:

If you take apart the keyboard and take a look, you will find a chip like the one below inside the keyboard. It is responsible for periodically scanning the circuit to detect which keys are pressed.

When it detects a key press event, it will get the keyboard scan code of the corresponding key position (note that pressing and releasing correspond to different scan codes), and then encapsulate a key message through the USB interface communication protocol and pass it out. This message contains the scan code of the key you pressed/released. If there are multiple keys, there will be multiple scan codes in the message.

The keyboard USB connector is connected to the USB port on the computer motherboard. Behind the USB port is the USB bus system on the motherboard. Therefore, the key message follows the keyboard connection, passes through the USB port and arrives at the USB bus.

The USB bus is connected to a USB controller chip, which is the one that "talks" to the USB devices.

0x02: Advanced Programmable Interrupt Controller APIC

After the USB controller receives the key message, it cannot submit it directly to the CPU. It has to deliver the message through another person in charge, which is the interrupt controller.

When it comes to interrupt controllers, you may have seen a chip called 8259A in many places:

It will then tell you that the keyboard is connected via the IRQ1 interrupt input source:

But please forget it now. This thing is a product of the last century. I guarantee that you will not find it if you disassemble your computer.

The reason is that with the rise of CPU multi-core technology, 8259A can no longer meet the needs of the times, so it has been replaced by another more advanced interrupt controller, APIC.

Yes, its name is that simple and direct: Advanced Programmable Interrupt Controller.

What exactly is so advanced about this more senior manager?

First of all, it is not a single chip, but is divided into two parts: Local APIC and I/O APIC.

Local APIC is like an outsourced team that is stationed in every core of the CPU and is responsible for interrupting each core.

The I/O APIC is independent of the CPU and receives interrupt sources from all I/O devices.

Let's look at an early IOAPIC chip: 82093AA

It replaces the traditional 8259A PIC to manage the interrupt signals of these peripherals on the motherboard. The pin diagram of this thing looks like this:

You can count the input pins responsible for interrupt sources, there are INTIN0-INTIN23, a total of 24, which is more than the number of traditional 8259A chips cascaded together.

If you disassemble your computer motherboard, I guarantee you still won't see this chip called IOAPIC, because this guy has now been integrated into the south bridge.

What? What is South Bridge? Next, we need to add some knowledge about computer motherboards.

0x03: Computer motherboard structure

On traditional computer motherboards, there is a classic architecture of CPU + North Bridge + South Bridge:

The North Bridge and South Bridge are the two most important chips on the motherboard besides the CPU. The so-called North and South come from the fact that in terms of drawing position, the north is at the top and the south is at the bottom, hence the name.

The north bridge is connected to the CPU and is responsible for connecting to high-speed devices such as memory and graphics cards.

The South Bridge is connected to the North Bridge and is responsible for connecting low-speed devices such as network cards, hard drives, keyboards, and mice.

You can understand it this way: the CPU is the big star on the entire motherboard, and all other devices on the motherboard revolve around it. This star has two agents, one is responsible for fast docking speed, and the other is responsible for slow docking speed.

Starting with Intel's Core processor (2008), the functions of the north bridge chip were integrated into the CPU. From then on, there was only one south bridge on the motherboard, so there was no distinction between north and south. It even changed its appearance and name: PCH.

This thing called PCH is not simple. It needs to connect to the CPU as well as a bunch of devices on the PCI bus and ISA bus.

Our keyboard is connected to the USB bus and is also connected to this PCH chip.

Through the cpu-z tool, you can see the PCH chip model on your computer motherboard:

As shown in the picture above, my computer is equipped with the B360 chip. You can find its detailed information on Intel's official website.

Where is this thing located on the computer motherboard?

Take away the heat sink, and you'll see this:

This tiny chip integrates a USB controller responsible for communicating with USB devices, as well as the advanced programmable interrupt controller IOAPIC responsible for interrupting the CPU. These two devices play a key role in the issues discussed today.

The USB controller is responsible for communicating with the USB device, and it will receive the key message packet transmitted by the USB keyboard.

0x04: Delivery of interrupt signal

Now the USB controller and APIC have been integrated into the PCH, and the internal structure is unknown, but in general, after the USB controller receives the key message, it initiates a notification through the interrupt source input pin of IOAPIC: Brother, something is wrong, please help me notify the CPU boss.

Inside the IOAPIC, there is a table PRT that records the configuration information of interrupt distribution. There are 24 table entries for 24 interrupt sources (in fact, some are reserved). Each entry in the table is called RTE, and each occupies 64 bits.

After the electrical signal from the USB controller is input to IOAPIC, IOAPIC will format an interrupt message through the corresponding table entry RTE according to the pre-programmed configuration information, and then send it out through the bus system.

In the early days, there was a dedicated APIC bus to communicate between IOAPIC and Local APIC inside the CPU, but it was cancelled starting from Pentium 4, and a public bus system was used to transmit interrupt messages.

After the message is sent, who will receive it?

In this interrupt message, the identification number of the recipient: Local APIC is filled in.

The signal on the bus system is transmitted to the inside of the CPU through the CPU pins. The Local APICs of all the internal cores can receive the interrupt message, but only the Local APIC of one core detects that the recipient is itself, and the others will ignore the message.

It finds that the recipient is its own Local APIC and starts to notify its core that an interrupt request has arrived.

The core of the CPU has been executing instructions continuously. At the end of each instruction cycle, it will check whether there is an interrupt request. After executing the instruction at hand, it finds the interrupt request submitted by the Local APIC.

Next, it is time for the CPU to start processing the interrupt message.

0x05: Interrupt handling

The first action saves the execution context.

The so-called interruption literally means interruption in the middle of writing. It is like when you are writing code and suddenly a product comes to you to add requirements, you are interrupted. It is not so bad for humans, we have memory ability, after communicating with the product, we can go back to the original place and continue writing code. But machines do not have memory thinking. Before interrupting to do other things, they must save what they were doing before, so that they can come back to continue doing the rest later.

This saving process is called execution context saving. Where is it saved?

The answer is the thread stack.

But please note that the stack here is not the thread stack we usually see, but another stack located in the kernel address space.

Whether it is Windows or Linux, basically each thread has two stacks when executing. One is used when the application we write executes code in user mode, called the user stack, and the other is used when the program enters kernel mode for execution due to system calls, exceptions, interrupts, etc., called the kernel stack. Compared with the user stack, the kernel stack has much smaller space.

Note: Not every thread has two stacks. Some operating systems' pure kernel threads only have kernel stacks and no user stacks.

When an interrupt occurs, the CPU will automatically save the current execution context at the top of the kernel stack. The so-called context is actually a bunch of register values. Note that this action is not completed by the operating system software, but is automatically completed by the hardware circuit inside the CPU.

The second action is to execute the interrupt handling function

After saving the context, the next step is to handle the interrupt. How to handle it is the job of the operating system.

Each core of the CPU has an interrupt descriptor table (IDT) located in the memory. This table has 256 entries, each of which records the address of a processing function. Each core also has a register called IDTR inside that points to this table.

It should be noted that although IDT is called Interrupt Descriptor Table, the 256 items in it are not all used to record interrupt handling functions, but also exceptions, traps (soft interrupts), and tasks.

The processing function addresses in the table are arranged by the operating system at the beginning of startup, including our keyboard interrupt processing function.

When an interrupt occurs, the CPU will take out the table entry with the vector number as the index from the table pointed to by the IDTR register according to the interrupt vector number, jump to the function address recorded in it, and start executing the code. This process is still completed by the CPU's hardware circuit.

So where does this interrupt vector number come from?

The answer is that in the message sent by IOAPIC, in addition to the identifier of the recipient Local APIC, there is also the interrupt vector number required to handle the interrupt.

Going back further, this interrupt vector number is actually configured in the table called PRT inside the IOAPIC mentioned earlier. An important task at the beginning of the operating system startup is to program the APIC (the so-called programming is actually writing these internal configuration tables, also called registers), and set the interrupt vector number corresponding to each interrupt source. In this way, the mapping relationship between the 24 interrupt sources and the corresponding interrupt vector numbers is established.

In addition to assigning vector numbers to interrupt sources, the operating system also has the task of specifying which cores handle which interrupts. I have previously written an interesting story about this part of knowledge: The CPU has 8 cores, but why does the network card struggle with core 1?

Next, the operating system (or more precisely, the device driver in the operating system) begins to process the interrupt message.

I won’t go into detail about the specific driver processing part. Different versions of the system process slightly differently. On Microsoft’s official website, you can find a diagram of the driver processing stack structure for USB input devices (keyboards, mice):

Generally speaking, after the Windows operating system intervenes in the interrupt processing, it is processed by a series of drivers (USB, HID, etc.), the scan code is converted, and then the key press message is finally delivered to a guy called Win32k.sys.

0x06: Operating system intervention

Let's shift our focus from the hardware to the operating system. Windows is a graphical operating system based on windows, and most programs are message-driven. Friends who have done Windows client development should be familiar with this.

Programs with graphical windows on Windows come in various forms and have varying functions, but they all have one thing in common: they are message-driven.

These messages may come from the keyboard, mouse, other processes or even the network. A typical Windows program must have the following message loop in its main thread:

 while(GetMessage()) {
 TranslateMessage();
 DispatchMessage();
 }

The main thread continuously calls GetMessage() to obtain messages, and then distributes them for processing. If there is no message, GetMessage will block.

Where does this GetMessage() get the message from?

The answer is message queues.

Every program with a graphical visualization window has a message queue, which is maintained in the kernel space. GetMessage() continuously retrieves messages from here for processing. Every time you press a key, click the mouse, or move the mouse, a message is generated and placed in this queue, waiting to be retrieved and processed.

Then the question arises again, who delivers the message generated after you press the keyboard? In addition, each window program has a message queue, so to whom should the keyboard message I press be delivered?

The answer lies in the guy called Win32k.sys mentioned earlier! This is an important module for the Windows kernel to implement the graphical user interface. There is a kernel thread in it that is specifically responsible for doing this - constantly obtaining key events from the keyboard driver, then encapsulating them into messages, and then combining them with the currently activated window on the desktop, locating the corresponding message queue, and delivering the message.

Therefore, in the application's message loop, the GetMessage() function will get a WM_KEYDOWN message representing a keyboard key being pressed.

Let's look back at the message loop. After receiving the message, there will be a "conversion action": TranslateMessage(). This function will translate the key message into a WM_CHAR message, indicating that a character input message has arrived. A field in this message will indicate that the character 6 is input.

Finally, the application finally received a WM_CHAR message with a parameter of 6, knowing that the user pressed a 6, and the next step is to display it on the monitor.

Summarize

The article is a bit long, so let’s summarize and sort out what exactly happens to the computer after pressing 6 on the keyboard.

This article is reprinted from the WeChat public account "Programming Technology Universe", which can be followed through the following QR code. To reprint this article, please contact the Programming Technology Universe public account.