understanding paging

[antoni]

I'm just trying to understand paging. I read "paging" and "setting up long mode" articles from OSDev wiki. I also tried to read AMD manual, but... I can't even understand OSDev article... It didn't help me much.

Let's start with a simple question, i.e. such a functions:

Code: Select all

int get_addr_in_pte(u32int addr)
{

        return (addr >> 12) & 4095;

}

I understand this one, but I need it to explain another one.

Code: Select all

int get_addr_in_pgd(u32int addr)
{
        return addr >> 22;
}

In the previous function, we removed twelve bits and took the next twelve. We have 8 left. Now we took 10 oldest bits, so 2 overlaps...

[iansjack]

I don't know where your functions came from, but the first one is wrong. 4095 (0xFFF) should be 1023 (0x3FF).

[bzt]

Hi,

What @iansjack said, plus

I read "paging" and "setting up long mode" articles from OSDev wiki

your code suggests you're calculating protected mode addresses, not long mode addresses. In long mode, you have:

Code: Select all

v & 4095 = offset within page
(v >> 12) & 511 = first level index (PTE), each entry covers 4096 bytes
(v >> (9+12)) & 511 = second level index (PDE) each entry covers 2M
(v >> (9+9+12)) & 511 = third level index, each entry covers 1G
(v >> (9+9+9+12) & 511 = fourth level index, each entry covers 512G
(v >> (9+9+9+9+12) & 65535 = fifth level index, either full 0, or full 1 bits; covers all virtual address space

I'm sorry, I never really cared which level is called page directory and page table or what ever. Numbers were always more logical to me

Cheers,
bzt

[antoni]

I have a problem with this function:

Code: Select all

void flushcr3()
{

        asm("movl %cr3, %eax \n\t movl %eax, %cr3");

}

It gives such an error:

Code: Select all

paging.c: Assembler messages:
paging.c:56: Error: unsupported instruction `mov'
paging.c:57: Error: unsupported instruction `mov'

[nexos]

I would recommend putting it in an assembly language file. Inline ASM is very tricky.

[antoni]

I would recommend putting it in an assembly language file. Inline ASM is very tricky.

Thanks, it worked for me.

[antoni]

In your OS, how do you check the virtual address of a given physical address? Do you go through the entire paging structure (which is slow), or do you have some other structure for this? Or is there an instruction that do this?

[iansjack]

Just as a matter of interest, why do you want to do this? Note that not all physical addresses will necessarily have corresponding virtual addresses. And it is a one-many relationship - many virtual addresses may map to the same physical page.

[antoni]

There are various structures in memory (multiboot info, ACPI, etc.) that I know the physical address of. I could simply map this same physical address to this same virtual address, but if I want a consistent address space without holes then I need to map virtual addresses to different physical addresses. But in such case I need to know their virtual addresses.

(My kernel only has one address space.)

[iansjack]

But the physical address won't have a corresponding virtual address until you have created the mapping. And that means you already know the virtual address as you chose it. You can then build this address into the code that accesses the resource; you really don't want to have to do some complicated lookup every time you need to access the resource.

[antoni]

OK.

But in ACPI tables there are physical addresses of other tables etc. So, of course, I know their virtual addresses in the moment of creating mapping, but where to store them?

Should I update table's content and fill it with virtual addresses? In such case this tables will be filled with both physical and virtual addresses (as I need and thus parse just a small part of this tables) which will be confusing and lead to errors.

I can also store this pointers in my own structures which is hard to implement.

And what do you do in your OS?

[thewrongchristian]

There are various structures in memory (multiboot info, ACPI, etc.) that I know the physical address of. I could simply map this same physical address to this same virtual address, but if I want a consistent address space without holes then I need to map virtual addresses to different physical addresses. But in such case I need to know their virtual addresses.

(My kernel only has one address space.)

The idea is you have a chain reverse references, rooted in the description of your physical page structure. When you add a virtual mapping to a physical page, a record of that reverse mapping is added to the chain of such references:

Code: Select all

struct rmap {
	process_address_space asid;
	void * address;
	struct rmap * next;
};

struct p_page {
	/* Stuff describing this physical page */

	/* Mappings of this physical page */
	struct rmap * rmaps;
};

void add_reverse_mapping(page_t pagenum, process_address_space asid, void * address)
{
	struct p_page * page = getpagestruct(pagenum);
	struct rmap * rmap = malloc(sizeof(*rmap));
	enter_critical_section(page);
	rmap->next = page->rmaps;
	rmap->asid = asid;
	rmap->address = address;
	page->rmaps = next;
	leave_critical_section(page);
}

void walk_reverse_mapping(page_t pagenum, void (*callback)(process_address_space asid, void * address))
{
	struct p_page * page = getpagestruct(pagenum);
	enter_critical_section(page);
	struct rmap * rmap = page->rmaps;
	while(rmap) {
		struct rmap * next = rmap->next;
		callback(rmap->asid, rmap->address);
		rmap = next;
	}
	leave_critical_section(page);
}

Then, when you want to do something to each mapping of a physical page, you call walk_reverse_mapping() with your page identifier and a callback, and that callback can do whatever you want, including removing the mapping:

Code: Select all

void unmap_virtual_address(process_address_space asid, void * address);
void unmap_page(page_t pagenum)
{
	walk_reverse_mapping(pagenum, unmap_virtual_address);
}

But the physical address won't have a corresponding virtual address until you have created the mapping. And that means you already know the virtual address as you chose it.

Exactly. You don't tend to need reverse mappings until you have to manage multiple mappings to pages. Until that time, if you have a one to one virtual to physical mapping, as you probably will do for structures such as ACPI data, then you just need the virtual address.

In which case you need either:

• A virtual memory address space allocator. This can be a simple bump pointer, dolling out segments of virtual address space on demand, or something more elaborate if you envisage free'ing and reusing regions of virtual address spaces. You allocate some virtual address space for your physical memory, and map it.
• A direct map of virtual->physical memory. This is more practical when the physical address spaces easily fits within the virtual address space (used by early Linux, for example, up until the point that physical memory started to exceed ~896MB.) Given your physical memory address, you just index into your virtual memory mapping of physical memory to access the physical page using the direct virtual address mapping.

[bzt]

OK.

But in ACPI tables there are physical addresses of other tables etc. So, of course, I know their virtual addresses in the moment of creating mapping, but where to store them?

Should I update table's content and fill it with virtual addresses? In such case this tables will be filled with both physical and virtual addresses (as I need and thus parse just a small part of this tables) which will be confusing and lead to errors.

I can also store this pointers in my own structures which is hard to implement.

No need to store them.

And what do you do in your OS?

Let's assume ACPI tables is at physical address P, mapped at virtual address V. Every time you read a pointer from the tables, do

Code: Select all

effective_ptr = acpi_ptr - P + V

and you'll be fine. No need to overwrite the ACPI tables (parts of it could be in read-only ROM area anyway) or to store the pointers because the offset displacement is going to be a constant.

Cheers,
bzt

[antoni]

From what BZT said, I presume that ACPI tables are not distributed throughout the memory, but are in one consistent, homogenous block? If so, how to find its size and where it starts?

I can find RSDP, RSDT, FADT and other tables, but to use offest to describe their location I would have to know where block they are in starts and how big is it.

[bzt]

From what BZT said, I presume that ACPI tables are not distributed throughout the memory, but are in one consistent, homogenous block? If so, how to find its size and where it starts?

I can find RSDP, RSDT, FADT and other tables, but to use offest to describe their location I would have to know where block they are in starts and how big is it.

Should be one block only, but if there are more blocks, then just use V1, V2 etc. one for each block depending where you've mapped that block. Just iterate through the memory map, you should find the blocks with starting address and size. If not, then use the RSDP and map the tables as you parse them, you can find the size of each table in their headers. The point is, remove the base physical ACPI address, and add the virtual one where you've mapped (no need to map contiguously, you could map each table at a different page if you'd like).

Cheers,
bzt