This article is about interrupt delivery process from external devices in x86 system. It tries to answer to questions such as:

<ul>
	<li>what is PIC and what is it for?</li>
	<li>what is APIC and what is it for? What is a purpose of LAPIC and I/O APIC?</li>
	<li>what are the differences between APIC, xAPIC and x2APIC?</li>
	<li>what is MSI? What are the differences between MSI and MSI-X?</li>
	<li>what is a role of tables $PIR, MPtable, ACPI?</li>
</ul>
If you want to know the answer for one of these questions, or if you simply want to know about  interrupt controllers evolution, please, welcome.
<cut />
<h3>Introduction</h3>
We all know what interrupt is. For those who don't, here is a quote from Wikipedia:

<blockquote>In system programming, an interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention. An interrupt alerts the processor to a high-priority condition requiring the interruption of the current code the processor is executing. The processor responds by suspending its current activities, saving its state, and executing a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is temporary, and, after the interrupt handler finishes, the processor resumes normal activities.

There are two types of interrupts: hardware interrupts and software interrupts (softirqs):

<ul>
	<li>Hardware interrupts are used by devices to communicate that they require attention from the operating system. Internally, hardware interrupts are implemented using electronic alerting signals that are sent to the processor from an external device, which is either a part of the computer itself, such as a disk controller, or an external peripheral. For example, pressing a key on the keyboard or moving the mouse triggers hardware interrupts that cause the processor to read the keystroke or mouse position. The act of initiating a hardware interrupt is referred to as an interrupt request (IRQ).</li>
	<li>A software interrupt is caused either by an exceptional condition in the processor itself, or a special instruction in the instruction set which causes an interrupt when it is executed. The former is often called a trap or exception and is used for errors or events occurring during program execution that are exceptional enough that they cannot be handled within the program itself. For example, a divide-by-zero exception will be thrown if the processor's arithmetic logic unit is commanded to divide a number by zero as this instruction is an error and impossible. </li>
</ul></blockquote>

This article is about hardware/external interrupts IRQ.

What is a purpose of interrupts? For example, we want to make some action with incoming packet from network card, as soon as packet arrive. If you don't want to continiously ask network card "have my packet arrived?" and waste your processor time, you can make use of external hardware interrupt IRQ. Interrupt line from a device should be connected to INTR line of CPU, and after each packet receive, network card will make a signal over this line. CPU will sense this signal, and know that network card has information for it. Only after that CPU will read incoming packet.

But what to do if there are a lot of external devices? Cause there are can't be enough pins on CPU for all of them.

<img src="https://habrastorage.org/webt/vg/3q/3v/vg3q3v7kx8vjttp43xo99o8pccs.png" />

To solve this problem special chip was invented - interrupt controller.

<h3>PIC</h3>
(<a href="https://en.wikipedia.org/wiki/Programmable_interrupt_controller">wiki</a>/<a href="https://wiki.osdev.org/8259_PIC">osdev</a>)

The first interrupt controller chip was <a href="https://en.wikipedia.org/wiki/Intel_8259">Intel 8259 PIC</a>. 8 input lines (IRQ0-7) and 1 output line which connects interrupt controller with INTR line of CPU. When there is an interrupt from one of the devices on its input lines, 8259 will make a signal over INTR line. After that CPU will know that some device require its immediate attention, and processor will ask PIC which of 8 input lines (IRQx) was a source of this interrupt. There is some overhead for this polling, but now we have 8 interrupt lines instead of 1.

<img src="https://habrastorage.org/webt/le/yf/6e/leyf6enogyzp6flpijo2d0x1w9g.png" />

Soon 8 lines weren't enough. To increase total interrupt line number two controllers 8259 (master and slave) were connected in cascad (Dual PIC).

IRQs from 0 to 7 are processed with the first Intel 8259 PIC (master), and IRQs from 8 to 15 are processed with the second Intel 8259 PIC (slave). Only master is connected to CPU and can signal about incoming interrupt. If there is an interrupt on lines 8-15, the second PIC (slave) will signal about it to master on line IRQ2, and after that master will make a signal to CPU. This cascaded interrupt takes 1 from 16 lines, but makes total of 15 interrupts for all external devices.

<img src="https://habrastorage.org/webt/xj/yn/dh/xjyndhabujjwz0alrbx831zfzt8.png" />

This scheme was approved by community and when now someone talks about PIC (Programm Interrupt Controller) they mean this Dual PIC system. After some time controllers 8259 have gotten some impovements and got a new name 8259A. And this scheme was included in chipset. In times when the main bus for external devices connection was ISA bus, this system was enough. It was only necessary to watch out of many devices on one IRQ line, as this produces conflicts, cause ISA interrupts aren't shareable.

Usually device interrupt mapping was pretty much standard:

Example (from <a href="https://en.wikipedia.org/wiki/Interrupt_request_(PC_architecture)">here</a>):
IRQ 0 — system timer
IRQ 1 — keyboard controller
IRQ 2 — cascade (interrupt from slave controller)
IRQ 3 — serial port COM2
IRQ 4 — serial port COM1
IRQ 5 — parallel port 2 and 3 or sound card
IRQ 6 — floppy controller
IRQ 7 — parallel port 1
IRQ 8 — RTC timer
IRQ 9 — ACPI
IRQ 10 — open/SCSI/NIC
IRQ 11 — open/SCSI/NIC
IRQ 12 — mouse controller
IRQ 13 — math co-processor
IRQ 14 — ATA channel 1
IRQ 15 — ATA channel 2

Configuration and working with 8259 chips is carried out with I/O ports:
<table class="tg">
  <tr>
    <th class="tg-0lax">Chip</th>
    <th class="tg-0lax">Register</th>
    <th class="tg-0lax">I/O port</th>
  </tr>
  <tr>
    <td class="tg-0lax">Master PIC</td>
    <td class="tg-0lax">Command</td>
    <td class="tg-0lax">0x0020</td>
  </tr>
  <tr>
    <td class="tg-0lax">Master PIC</td>
    <td class="tg-0lax">Data</td>
    <td class="tg-0lax">0x0021</td>
  </tr>
  <tr>
    <td class="tg-0lax">Slave PIC</td>
    <td class="tg-0lax">Command</td>
    <td class="tg-0lax">0x00A0</td>
  </tr>
  <tr>
    <td class="tg-0lax">Slave PIC</td>
    <td class="tg-0lax">Data</td>
    <td class="tg-0lax">0x00A1</td>
  </tr></table>
→Full documentation of 8259A is possible to find <a href="https://pdos.csail.mit.edu/6.828/2005/readings/hardware/8259A.pdf">here</a>

After ISA bus there came PCI bus. Device amount quickly became to
exceed number 15. Plus instead of static ISA bus in PCI bus devices can be added to system dynamically. But luckily, in PCI bus interrupts can be shared (it means that it is possible to connect many devices to one interrupt line IRQ). In the end, to solve the problem of low number of interrupt lines, it was decided to group interrupts from all of PCI devices to PIRQ lines (Programmable Interrupt Request).

For example we have 4 free interrupt lines on PIC controller and 20 PCI devices. We can combine interrupts by 5 devices at one PIRQx line, and connect these PIRQx lines to PIC controller. In this case if there is an interrupt on one of PIRQx lines, processor will have to ask all devices connected to this line about interrupt, to know who is responsible for it, but in the end it solves the problem. The device that connects PCI interrupt lines to PIRQ lines is often called PIR router.

In this method it is necessary to watch out that PIRQx lines don't connect to lines with ISA interrupts (cause this will produce conflicts) and PIRQx lines are ballanced (the more devices we connect to one line, the more devices CPU will need to poll, when it will need to understand which device is responsible for interrupt).

<img src="https://habrastorage.org/webt/u_/jr/u9/u_jru9pemdeda2xvvbqihvgtp3y.png" />

<b>Note</b>: on the image mapping PCI device -> PIR is pictured abstractedly, cause in the real case it is a little bit more complicated. In real life every PCI device have 4 interrupt lines (INTA, INTB, INTC, INTD). Also every PCI device can have up to 8 functions. And every function can have only one of these INTx interrupts. Which INTx line will be used by each function is determined by a chipset configuration.

By its nature functions are separate logical blocks. For example one PCI device can have Smbus controller function, SATA controller function, LPC bridge function. From the point of operating system (OS) every function is like a separate device with its own configuration space (PCI config).


Information about PIC controller interrupt routing is sent to OS by BIOS with a help of table $PIR and through registers 3Ch (INT_LN Interrupt Line (R/W)) and 3Dh (INT_PN Interrupt Pin (RO)) of PCI configuration space for every function.

Specification for $PIR table recently was <a href="http://www.microsoft.com/whdc/archive/pciirq.mspx">on Intel website</a>, but currently it is unavailable. Is is possible to understand table content from <a href="http://www.o3one.org/hwdocs/bios_doc/pci_bios_21.pdf">PCI BIOS Specification</a> [4.2.2. Get PCI Interrupt Routing Options] or read it <a href="http://ru.osdev.wikia.com/wiki/PCI_IRQ_Routing_Table_Specification">here</a> (last link is in russian, but you can try to google for "PCI IRQ Routing Table Specification")

<h3>APIC </h3>
(<a href="https://en.wikipedia.org/wiki/Advanced_Programmable_Interrupt_Controller">wiki</a>, <a href="https://wiki.osdev.org/APIC">osdev</a>)

The last method was working until multiprocessor system have arrived. It is because by its nature PIC can send interrupts only to the one CPU. And of course it is desired to load CPUs in multiprocessor system in a ballanced way. The solution to this problem was a new interface called APIC (Advanced PIC).

For every processor special controller called LAPIC (Local APIC) is added. Also for routing interrupts from external devices controller <a href="https://wiki.osdev.org/IOAPIC">I/O APIC</a> is added. All these controllers are combined in a common bus with a name APIC (modern systems instead of this separate APIC bus make use of a standard system bus for this task).

When external interrupt arrives on I/O APIC input, controller will send an interrupt message to LAPIC of one of the system CPUs. This way I/O APIC controller help to ballance interrupt load between processors.

The first APIC chip was <a href="https://4donline.ihs.com/images/VipMasterIC/IC/INTL/INTLD047/INTLD047-2-1259.pdf?hkey=EF798316E3902B6ED9A73243A3159BB0">82489DX</a>, this was a separate chip with connected LAPIC and I/O APIC in itself. To make system with 2 processors it was needed 3 such chips (2 for LAPIC and 1 for I/O APIC). Later LAPIC functionality was directly included in processors, and I/O APIC part was made to separate 82093AA chip.

I/O APIC <a href="https://pdos.csail.mit.edu/6.828/2016/readings/ia32/ioapic.pdf">82093AA</a> had 24 inputs, and APIC architecture could support up to 16 CPUs. For compatibility with older systems interrupts 0~15 were left for old ISA interrupts. And interrupts from PCI devices start to route on IRQ lines 16-23. With this you can forget about conflicts between ISA and PCI interrupts. Also cause of increased number of free interrupt lines it is became possible to increase number of PIRQx lines.

<img src="https://habrastorage.org/webt/mc/ra/hj/mcrahjn-owk9qrcmyiixcmhomcq.png" />

I/O APIC and LAPIC programming is made with a help of MMIO. LAPIC registers usually are placed on address 0xFEE00000, and I/O APIC registers on address 0xFEС00000. But it is possible to reconfigure all these addresses.

As in PIC case, separate chips at first became part of a chipset later.

Later APIC architecture get a modernization and its new variant get a name xAPIC (x - extended). With a full backward compatibility, total number of possible CPUs in system was increased to 256.

The next step in architecture development have got a name <a href="https://www.intel.com/content/dam/doc/specification-update/64-architecture-x2apic-specification.pdf">x2APIC</a>. The number of possible CPUs in system was increased to 2^32. Controllers can work in backward compatibility mode to xAPIC, or they can work in new x2APIC mode. In this new mode controller programming is made not through MMIO but through MSR registers (which is much more faster). According to <a href="https://blahg.josefsipek.net/?tag=xAPIC">this link</a> for this mode IOMMU support is necessary.

It is worth to notice that it is possible to have many I/O APIC controllers in system. For example, one for 24 interrupts in southbridge and the other one for 32 interrupts in northbridge. In the context of I/O APIC, interrupts usually titled as GSI (Global System Interrupt). So, forementioned system has GSI 0-55.

Does the CPU have internal LAPIC and which APIC architecture exactly? It is possible to get answers to these questions by inspecting bit-flags from CPUID.
To help OS to discover LAPIC and I/O APIC, BIOS should present information about them either through MPtable (old method) or through ACPI table (MADT table in this case). Besides common information, both MPtable and ACPI (in this case DSDT table) should contain info about interrupt routing. This means information about which device uses which interrupt line ($PIR table analogy).

You can read about MPtable in official <a href="https://web.archive.org/web/20121002210153/http://download.intel.com/design/archives/processors/pro/docs/24201606.pdf">specification</a>. Earlier specification was on Intel website, but currently it is only possible to find it in archive version. ACPI specification can be found on UEFI website (current version is <a href="https://www.uefi.org/sites/default/files/resources/ACPI_6_2.pdf">6.2</a>). It is worth to notice that with ACPI it is possible to declare interrupt routing for systems without APIC (instead of providing a separate $PIR table).

 <h3>MSI </h3>
(<a href="https://en.wikipedia.org/wiki/Message_Signaled_Interrupts">wiki</a>)

Last variant with APIC was good, but not without downsides. All these interrupt lines from devices make system very complicated and thus increase error probability. PCI express bus came to replace PCI bus, and PCI express simplifies all interrupt system completely. It doesn't have interrupt lines at all. For backward compatibility interrupt signals (INTx#) are emulated with separate kind of messages. With PCI interrupt lines their connection was made with physical wires connection. With PCI express interrupt lines connection is logical and is made by PCI express bridges. But this support of legacy INTx interrupts only exist for backward compatibility with PCI bus. PCI express introduces completely new method of interrupt delivery - MSI (Message Signaled Interrupts). In this method device signals about interrupt simply by writing in a special place in MMIO region of CPUs LAPIC.

Earlier one PCI device (this means all its functions) could have only 4 interrupts, but now it is became possible to address up to 32 interrupts.

In a case of MSI there is no sharing for interrupt lines, every interrupt naturally corresponds to its device.

MSI interrupts also solve one more problem. For example let's imagine a situation where device makes memory-write transaction, and wants to signal about its completion through interrupt. But write transaction can be delayed on bus in a process of its transmission (and device couldn't know about it). In this case signal about interrupt will come to CPU first, so processor will read yet not valid data. If MSI is used, information about MSI is trasmitted in a same way as data messages, and it can't came earlier.

It is worth to notice that MSI interrupts can't work without LAPIC, but MSI's can replace I/O APIC (one more design simplicity).

After some time MSI method was extended to MSI-X. Now every device can have up to 2048 interrupts. Also now it's possible to specify which CPU should process which interrupt. It can be very usefull for highload devices like network cards for example.

There is no need in separate BIOS table for MSI support. But device should indicate about its MSI support through one of the Capabilities in its PCI Config space. Also device driver should include all necessary support for working with MSI.

<h3>Сonclusion</h3>
In this article we have studied information about interrupt controller evolution and have got a common theoretical knowledge about interrupt delivery from external devices in x86 system.

In the next part we will go practice and see how to engage every of forementioned interrupt controllers in Linux.

In the third part we will look in coreboot code and see, what settings are need to be done in chipset for correct interrupt routing.

<h4>Links:</h4>
<ul>
	<li><a href="https://people.freebsd.org/~jhb/papers/bsdcan/2007/article/node4.html">Interrupt Controllers (Stuff in the Middle)</a></li>
	<li><a href="https://electronics.stackexchange.com/questions/76867/what-do-the-different-interrupts-in-pcie-do-i-referring-to-msi-msi-x-and-intx">What do the different interrupts in PCIe do?</a></li>
	<li><a href="https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/msg-signaled-interrupts-paper.pdf">Reducing Interrupt Latency Through the Use of Message Signaled Interrupts</a></li>
</ul>