Memory manager

[quanganht]

I've been thinking for a while, and still not able to choose which way to implement memory manager. I want a manager, which doesn't use paging, and still be able to protect memory pieces. I have read this page http://en.wikipedia.org/wiki/Memory_protection, and seems like Protection keys and Capability-based addressing is the two candidates. But they are confusing. First, I don't know if they are supported on x86. Second, if I'm not using paging, and an application just access a memory address, how can I know that?

I know they are a little dumb questions, but I will highly appreciate any help.

[DeleteMe]

you can use segmentation, but i will not recomand it. you got ONLY 2 chouces on a x86, paging or segmentation. but you can "emualate" many of ohter types whit paging.




f*** my bad english.

JTR

[manonthemoon]

I have read this page http://en.wikipedia.org/wiki/Memory_protection, and seems like Protection keys and Capability-based addressing is the two candidates.

The article specifically says which processors support those methods, and neither mention x86.

Second, if I'm not using paging, and an application just access a memory address, how can I know that?

You can't. Paging is the only way, except for segmentation. In that case, the kernel will only find out if a program accesses memory beyond the segment's limit.

Why don't you want paging? It's flexible, and there's plenty of documentation on how to use it. For an x86 processor, it's really your only choice.

[gravaera]

Well, actually, there is a way, but it's software implemented, and not very sturdy. It involves polling and setting certain bits, and seeing if they've been changed. But this assumes that you've created a structure similar in purpose to Paging, such that you have some sort of way of receiving requests from apps for on-demand memory allocation (not in the context of a heap). From there, you can regularly unset allocated space in your struct, and if the app asks for it back, it means it's needed. Else, for the time that you receive no more requests for that bit of space, you can leave it swapped out.

Obviously this can, of course, be implemented about 10 times faster with paging, though. But by no means is paging the only memory model out there. There's tons of models and their relevant algorithms. Paging is great for the x86 because it's hardware supported. That's why it's more or less the 'choice of champions' if you will.

EDIT: And like pcfrek said: paging can be used VERY flexibly.

You don't even have to use virtual resolution. You can simply identity map everything, and make a nice, flat memory model. And then, depending on how much access you want to grant to apps, you can either have only ONE page dir for every process including the kernel, such that every process sees memory the same way, or have two page dirs: one for the kernel with full identity mapping, and one for the apps with some pages (hardware IO ranges, registers, etc) set to supervisor mode, and whatnot.

And you'll find that paging would be faster.

[jal]

Well, actually, there is a way, but it's software implemented, and not very sturdy. It involves polling and setting certain bits, and seeing if they've been changed.

Errr... That is totally bogus. If you don't use paging (and segmentation), there's no way to prevent memory access on an x86. At best you *might* be able to detect illegal writes, but this is incredibly slow (scanning 2GB anyone?) and the damage has already been done.


JAL

[gravaera]

Well, actually, there is a way, but it's software implemented, and not very sturdy. It involves polling and setting certain bits, and seeing if they've been changed.

Errr... That is totally bogus. If you don't use paging (and segmentation), there's no way to prevent memory access on an x86. At best you *might* be able to detect illegal writes, but this is incredibly slow (scanning 2GB anyone?) and the damage has already been done.


JAL

But...I wasn't talking about memory protection. He asked i there was any way to tell whether or not appilcations have accessed a memory address. I gave him a workable, albeit impossibly slow method.

I definitely wasn't talking about memory protection.

I probably should have quoted the part I was responding to:

Second, if I'm not using paging, and an application just access a memory address, how can I know that?

[iammisc]

If you want to implement an architecture that the processor that you want does not support you are going to have to emulate it. Since there is no practical way on the x86 or amd64 to detect arbitrary reads and writes you are going to have to bypass the use of native machine code in your operating system programs. Therefore the only way to implement these exotic addressing schemes is to emulate an architecture which does support them. Basically write a virtual machine. You can use a jit compiler to achieve good performance. But a virtual machine is the only sure way to detect an memory write and read and enforce the kind of security you want.

However, this is going to be extremely slow. Unless your bytecode for your virtual machine is high-level enough to enforce certain memory access optimizations, you're going to be stuck with a lot of software checks and such which are going to slow your computer down. For example, on every read or write your going to have to perform some logic and then either allow or disallow that access. Let's say you have a function can_access that returns whether this program can access a certain address. Now this function is going to be called each time your virtual machine either executes a memory accessing instruction or the native code that your machine generates is going to have to call this function every time it runs. Since memory accesses make up a good portion of most substantial programs, a good part of your processing time is going to be wasted figuring out whether or not an instruction could even access the memory it wants.

Therefore, implementing such a system on an architecture that does not natively support the behavior you are trying to achieve is impractical. If the behavior were something different like network access, it might be feasible but memory access is such a pervasive part of most software programs that to alter its behavior through the use of a time consuming function is a waste of processor time IMHO. No matter the implementation, you are going to have to call that function and that is going to waste your time.

If this is just for research, fun, and hobby, by all means use a virtual machine and do what you want but if this is for a practical operating system, I'd stick to paging or segmentation or some other native-to-your-arch memory scheme.

[quanganht]

Ok, if there is no way to catch memory access, how can I protect an application's memory pages from being attacked by other apps?

EDIT: I recently read about Capability-based OS. Can it answer the question?

[jal]

Ok, if there is no way to catch memory access, how can I protect an application's memory pages from being attacked by other apps?

You can't, unless you do not allow apps to run native code (i.e. use bytecode or the like).


JAL

[quanganht]

Ok, if there is no way to catch memory access, how can I protect an application's memory pages from being attacked by other apps?

You can't, unless you do not allow apps to run native code (i.e. use bytecode or the like).

JAL

That's funny. I bet there must be a way to archive it w/o bytecode. (I'm thinking about capability-based and code uploading)

[Brendan]

Hi,

Ok, if there is no way to catch memory access, how can I protect an application's memory pages from being attacked by other apps?

It is possible to catch memory accesses.

You start with all pages marked as "not present". When a program tries to access a page you get a page fault, and the value in CR2 tells you which address the program tried to access (but you don't know if the program is reading/writing a byte, or a dword, or maybe even doing an FXSAVE/FXRSTOR and reading/writing almost 500 bytes in one go). To find out how much data the program is reading/writing, your page fault hander would map a temporary copy of the pages at CR2 and set "break on data read or write" breakpoint just above the highest address you want to allow (using DR0 to DR3 and DR7). Your page fault handler would also enable "single stepping". Once all this is done you'd return to the instruction that caused the page fault, and this instruction will execute correctly and then generate a debugging exception. Your debugging exception handler would determine if the "break on data read or write" breakpoint was triggered or not, and can determine if the access should have been allowed or not. If the access should have been allowed you copy the data from the temporary copy of the pages back into the real version of the pages, disable single stepping, disable the breakpoint, map the page/s as "not present".

It is a complex mess; but it would be possible to implement capability-based addressing without using emulation or JIT. The problem is that with 2 exceptions (and TLB invalidations, etc) every time you access anything it'll be extremely slow (and emulation/JIT would probably be faster anyway). However, there are things you could do to improve performance.

If a program should have access to every byte in a page, then you could leave that page as "present", so the program can access the data with no extra overhead at all (note: the program's code and stack *must* be "present" or the method described above won't work). You could also arrange the data to maximize the number of pages that are left as "present". For example, if there's 100 data structures and you need one capability to access 35 of the data structures and a different capability to access the other 65 data structures, then you'd have one group of pages that contain the first 35 data structures and another group of pages that contain the other 65 data structures; and these groups of pages would become "present" or "not present" depending on whether or not the program has the corresponding capability. You could make pages present or not present during task switches, but you could also give each program it's own page directory and page tables that keep track of which groups of pages it's allowed to access (to avoid doing so much work during task switches). In both of these cases, if a program's capabilities are changed you'd need to change which groups of pages are "present".

If you arrange the data carefully (e.g. one or more whole pages for each combination of capabilities) then you don't need any of that messy exception handling stuff; and if you give each program it's own page directory and page tables then (as long as a program's capabilities don't change often) there'd be almost no added overhead at all.

It's funny, but after optimizing "capability-based addressing" it ends up doing almost exactly the same as normal OSs, which can be described as "stuff that a program can access is mapped into that program's address space, and stuff that a program can't access isn't"...


Cheers,

Brendan

[tantrikwizard]

<snip>...(but you don't know if the program is reading/writing a byte, or a dword, or maybe even doing an FXSAVE/FXRSTOR and reading/writing almost 500 bytes in one go)..<snip>

This could be achieved by disassembling the EIP thats pushed on the fault handler's stack.

[Brendan]

Hi,

<snip>...(but you don't know if the program is reading/writing a byte, or a dword, or maybe even doing an FXSAVE/FXRSTOR and reading/writing almost 500 bytes in one go)..<snip>

This could be achieved by disassembling the EIP thats pushed on the fault handler's stack.

Decoding instructions would add a lot of overhead (mostly due to unpredictable/mis-predicted branches), and it'd add a lot of complexity (there's about 720 instructions that can be used from CPL=3, most can access memory, and some support multiple data sizes).

My main point was that all of this hassle disappears once you optimize it to use paging properly (and that if you don't optimize it to use paging then it's probably better to use JIT instead).


Cheers,

Brendan

[jal]

Ok, if there is no way to catch memory access, how can I protect an application's memory pages from being attacked by other apps?

You can't, unless you do not allow apps to run native code (i.e. use bytecode or the like).

That's funny. I bet there must be a way to achieve it w/o bytecode. (I'm thinking about capability-based and code uploading)

Perrhaps we are talking about different subjects, but I have the original 8086 (or 68000 if you prefer) in mind as an example of a CPU without any form of memory protection. There's really no way to stop memory access, as there is no protection at all (without additional hardware, that is).


JAL