How OS detects memory access violations

How does an operating system (preferably Linux) know that you've accessed a memory location that you're not allowed to?

This question was inspired by those damn pointers! The way I see it is: everything in computers is about a compromise between speed, security, integrity, and such things.

I'm well aware of memory maps in Linux, but it sounds a bit ridiculous to me that the kernel checks if the location you're trying to access resides in a valid range EVERY TIME you make an access. It sounds like it would waste so much time, which could be spent doing something more productive (but possibly less safe with no checking!). Or maybe it remembers all recent accesses and checks them on every hardware timer tick? (But that sounds unsafe, and yet again, slow.)

I was surprised that this question appears to be unanswered anywhere. It's something I've always wondered. It makes me think there is a section of hardware which will do this on behalf of the OS, in a nice, convenient level of abstraction. But still, it would possibly require loading the next processes memory maps on every context switch, which again sounds slow.

So yes, anyway, I'm going on a bit: how does an OS detect a memory violation?

Thanks

(The following answer assumes a “modern” desktop, server, or upper-end embedded platform (such as smartphones, and more and more smaller systems as well). For x86 systems, modern means 386 and up. The following answer also assumes a “modern” OS, such as almost any unix, or Windows since 95.)

This is not happening in the OS, it's happening in the processor, specifically in the MMU (memory management unit). The MMU supports virtual addressing, whereby the bits that make up a pointer don't directly indicate the physical location of the bits in memory.

In a typical MMU, when a pointer is dereferenced, the MMU breaks down the bits into two groups: the high-order bits make up the page number, and the low-order bits make up the address inside the page. Most desktop and server machines use 4kB pages. The MMU looks up the virtual page number in a table called TLB (that's what you called the “process memory maps”). The TLB indicates the number of the physical page that corresponds to this virtual page. The MMU then fetches the data from the physical page in memory.

If the TLB doesn't contain an entry for this particular virtual page number, the MMU notifies the processor that an invalid access occurred; this is typically called an exception.

Note that I haven't mentioned the OS so far. That's because all this operation is independent from the OS. The OS comes into play because it configures things in two ways:

• The OS is responsible for switching tasks. When it does so, as you suspected, it saves the current TLB and replaces it by the saved TLB for the next scheduled task. That way, each process has a TLB, so address 0x123456 in process X might not point to the same actual place in RAM as that same address in process Y, or might simply invalid. If a process tries to dereference a pointer outside its address space, it doesn't reach into another process's space, rather it reaches nowhere.

• The OS decides what happens when an exception is raised. It can terminate the process for doing an invalid memory access (segmentation fault, general protection fault, ...). This is also the way in which swapping is implemented: the exception handler might decide to fetch some data from the swap space, update the TLB accordingly and perform the access again.

Note that the MMU provides security because the process cannot change its own TLB. Only the OS kernel can change TLBs. How TLB change permissions work is beyond the scope of this answer.

1) Segfaults are detected by the memory management unit. When you ask for memory, the OS asks the Memory Management Unit to get some from the hardware. There has to be something that keeps track of all the big memory blocks the OS gives you. The OS kind of hands that off to the MMU. Since it knows all the memory it gave you, it can also tell you when you try to access a memory location you didn't get from allocations, The OS specifically has an event for this, memory you don't own. Eventually the OS kills your app, triggering either a segfault or the equivalent on other OSes.

Not all OSs have this protection. MacOS up to 9 didn't have any of this, even though the MMU did support this. Neither did Win 3.1. Win95 had some protection, as it transitioned between having no protection and then adding some.

2) The OS doesn't know any details other than this. If you have a stray pointer that accesses memory you never allocated, it knows. If you have one that goes into another part of your application, it doesn't know of course. It lets you corrupt this. This is where you get corrupt stacks, with stray pointers from your app overwriting other parts of your app.

So, yes, you can screw your own data. If you have a stray pointer that overwrites your own app, you HOPE you hit your stack, since that will probably case another violation when you try to return off stack, but if you hit your own data, you'll never know.

You can try to be more strict than 'no protection', there's a tool called Electric Fence (http://perens.com/FreeSoftware/ElectricFence/) that will trick your MMU to work a bit more, and cause it to detect more faults.