Stacks Explained with Real Examples from the Linux Kernel

A stack is one of the simplest data structures there is. You can learn the idea in one minute. But it is also one of the most useful, and it sits inside every program you have ever run, including the Linux kernel.

Let's start with the idea, then look at where the kernel uses it.

What is a stack?

Think of a pile of plates. You put a new plate on top. When you need one, you take the top plate. You never pull one from the middle. The last plate you put on is the first one you take off.

That rule has a name: last in, first out, or LIFO. A stack has only two main actions:

• Push puts a new item on top
• Pop takes the top item off

Most stacks also let you peek at the top item without removing it, and check if the stack is empty.

A tiny stack in C

Here is a stack of integers using a plain array. It is small, but it shows the whole idea.

#define MAX 100

int stack[MAX];
int top = -1;          /* -1 means the stack is empty */

void push(int x) {
    if (top == MAX - 1) return;   /* full, so we stop */
    stack[++top] = x;
}

int pop(void) {
    if (top == -1) return -1;     /* empty, nothing to give */
    return stack[top--];
}

Both actions are quick. They do not depend on how many items are in the stack. That is why stacks are used in places where speed matters a lot.

Where the Linux kernel uses stacks

Every process on Linux gets its own stack inside the kernel. It is separate from the stack your program uses in normal mode. In the Linux 2.6 days on x86, this kernel stack lived in a fixed area of 8 KB, which is two memory pages. The small data block that describes the process sat at the start of that area, and the stack started at the far end and grew backwards toward it.

Notice the detail here. The stack does not grow forward. It starts at the high end and moves down as you push. A register called esp always points to the current top. When the stack is empty, it points just past the end of the area. This is the same thing as top = -1 in our small example, only done at machine level.

Function calls

When one function calls another, the CPU pushes the return address and the local variables on the stack. When the function ends, they are popped, and the program goes back to exactly where it left off. If function A calls B, and B calls C, then C must finish first, then B, then A. That is LIFO again. You never have to think about it, because the stack does it for you.

Interrupts

Now the more interesting case. When a device such as a keyboard or a network card needs attention, the CPU stops what it is doing and runs an interrupt handler. The first thing the kernel does is save the CPU registers on the kernel stack. The last thing it does is restore them, so the interrupted work can carry on as if nothing happened.

Interrupts can also be nested. One handler can be interrupted by another one, and that one by another. How does the kernel remember where to go back to? It just pushes each one on the stack. The newest handler finishes first, then it returns to the one before it, and so on, until the CPU is back to the original work. A stack is the natural fit, because the last thing that started is always the first thing that must finish.

Switching between processes

When the kernel stops one process and starts another, it has to save the state of the first one so it can be continued later. Part of that state is stored in the process's own kernel stack. Because each process has its own stack, the kernel can switch to another process by changing the stack pointer. In the code, the switch is really a swap from one stack to another.

Why the stack is small

You may wonder why the kernel keeps this stack so small. It is because kernel code is careful. It does not use deep chains of function calls or big local arrays. A stack that runs out of space is a serious bug, since the data next to it can be overwritten. The kernel also had a setting for even smaller 4 KB stacks, and in that case it used a few extra stacks just for interrupts, so that deeply nested handlers would not run it out of room.

The lesson for your own code is the same. A stack has a limit, and if you go too deep, for example with a function that calls itself forever, you get the famous stack overflow.

More places you already use stacks

• The undo button in your editor
• The back button in your browser
• Checking that brackets match in code, like { ( ) }
• Evaluating expressions like 3 + 4 * 2
• Depth first search in graphs and trees

Try it yourself

1. Write a function that uses a stack to check if a string like {[()]} has matching brackets.
2. Reverse a string using only push and pop.
3. What happens in the code above if you call pop() on an empty stack? How would you handle it better?

If you can do these three, you understand stacks well enough for most interviews.

What comes next

Next in the series is the queue. It is the stack's opposite, first in and first out, and the kernel uses it a lot too. If you want to practise as you read, our C and data structures course covers stacks, queues and the rest hands-on.

---

I first published this on the Jupius Learning blog. If you want to practice, the C, data structures and algorithms course is a good place to start.