Hi,
(Using a one-level page table)
Let's suppose that a program's virtual image can grow dynamically. If this is the case, then a dynamic page table would be necessary, since a larger page table is necessary for a larger virtual image.
Now, if this is the case, then it would be impossible to keep the page table in contiguous memory, but a requirement for the page table is to be in contiguous memory, otherwise the Memory Management Hardware cannot index into the table.
Can anyone explain this contradiction?
Thanks

Non PAE 32 bit x86 uses a two-level page table.
PAE 32 bit x86 uses a three-level page table.
X86_64 uses a four-level page table.

You could pre allocate the page table for the max virtual size, since any entry in the page table can be marked non resident.

So even with a one level page table the virtual size of the task could grow.

Who requires that?

What Memory Management unit? Some hypothetical one level paging design? I don't know the details of that unlikely design.

It seems you are making false assumptions. That tends to lead to contradictions.

If the page-table cannot grow dynamically, then the kernel have to allocate it in the maximum possible size. Of course it would be an overkill (example: 4 GiB address space, 4 KiB page size, 32 bit/page-table-entry => 4 MiB for the page table); that's why we use two-, three- or even more level hierarchical page-tables.

Examples:
IBM/360 (24-bit): two levels: 16 MiB = 256*32*2KiB (address-bits: 32=8+5+11)
x86/32-bit: two levels: 4 GiB = 1024*1024*4 KiB (address-bits: 32=10+10+12)
x86/32-bit/PAE: three levels: 4 GiB = 4*512*512*4 KiB (address-bits: 32=2+9+9+12)
x86-64/48-bit: four levels: 256 TiB = 512*512*512*512*4 KiB (address-bits: 48=9+9+9+9+12)

Slight typo there. I think you meant:

x86-64/48-bit: four levels: 256 TiB = 512*512*512*512*4 KiB (address-bits: 9+9+9+9+12)

Fixed -- thank you!

That's why I asked for a one-level page table, but it seems that it is not used because of its inefficiency. I know that in order to support a big image sizes a multi-level is the way to go. (Or even something like an inverse page table).

I said that a requirement was that it was in contiguous memory because it does not matter the level of the page table hierarchy, the first table has to be in contiguous memory. Otherwise the address translation mechanism of adding the leftmost bits of the logical address (page number) to the first table's base address would not work. Of course the rest of the tables can be managed with the same paging mechanism as the user processes.

Ok, since johnsfine clarified that a one-level page table is unlikely to be around because of its inefficiency, then my question about a one-level page table is officially solved. But I have another question:
Having a multi-level page table, since a dynamic growth of the virtual image implies a dynamic growth for all the tables (no matter the level used) then as johnsfine suggested the solution would be to pre-allocate the tables to accommodate a predefined image size. However, johnsfine, don't you think that allocating a table for the maximum virtual size is an overkill? Wouldn't there be a mechanism at compile time to specify the maximum size of the process?

Note that it does not matter how many levels are in the design, the last table will always have (memory_size)/(page_size) entries....

sorry about the overkill question, i just read NevemTeve post

I said "You could pre allocate". That was not a suggested design. That was just showing a possibility in a theoretical discussion.

The max size is usually not known at compile time.

I think you mean (memory_size*entry_size)/(page_size)

In PAE and x86-64 the entry size is 8 and the pages size is 4096, so up to a 512*4096 byte memory area could be mapped by a 4096 byte page table.

But usually the image is not contiguous, so each level is a somewhat bigger fraction of the level it maps than that formula suggests.

Philosophical mind games are all well and good, but MMUs deal with physical memory. They neither know nor care of virtual addressing.
The kernel is mapped into non-paged ram. Period. It has page tables but they map one-to-one into physical addresses, unlike user-space.