On Wednesday, March 16, 2022 at 1:56:50 PM UTC-5, Ivan Godard wrote:
> On 3/16/2022 8:57 AM, MitchAlsup wrote:
> > On Tuesday, March 15, 2022 at 9:46:07 PM UTC-5, robf...@gmail.com wrote:
> >> On Tuesday, March 15, 2022 at 10:24:03 PM UTC-4, EricP wrote:
> >>> BGB wrote:
> >>>> On 3/15/2022 1:08 PM, MitchAlsup wrote:
> >>>>> On Tuesday, March 15, 2022 at 12:23:56 PM UTC-5, EricP wrote:
> >>>>>> What about address translate skipping page table levels?
> >>>>> <
> >>>>> Skipping levels is, in my opinion, a necessity. I was part of the
> >>>>> I/OMMU team
> >>>>> at AMD where we put in level skipping as part of its design. I think
> >>>>> CPU tables
> >>>>> and I/OMMU tables should be one and the same, along with the "a
> >>>>> pointer is a
> >>>>> pointer" philosophy. I/O device should get virtual address of
> >>>>> originating thread,
> >>>>> I/O DMA should be translated thought page tables of originating
> >>>>> thread, I/O
> >>>>> completion interrupt should be delivered to Guest OS hosting
> >>>>> originating thread.
> >>>>
> >>>> One drawback of level skipping though, is that one can either ignore
> >>>> bits (effectively multi-mapping the skipped levels), or assumes them to
> >>>> be zero (doesn't work for randomized addresses), neither of which are
> >>>> ideal in a large+sparse ASLR scenario.
> >>> As I mention below, it can assume the missing values are 0's
> >>> or have a PTE bit to specify the value.
> >>>
> >>> A PTE bit allows one to differentiate between whether the
> >>> page is part of a grow-up or grow-down memory section.
> >>> E.g. heap areas expand upward, stack expand downwards.
> >>>>>> Another issue is what the fill values should be that were skipped.
> >>>>>> MMU can assume the the address bits skipped were all 0's,
> >>>>>> or the PTE could have a bit to prescribe the skipped value as 0 or 1.
> >>>>> <
> >>>>> I am following the rules of canonicality AMD uses when skipping levels
> >>>>> in the I/O MMU.
> >>> More feature bits also puts more presure on the PTE which is already full.
> >>
> >>> A PTE bit allows one to differentiate between whether the
> >>> page is part of a grow-up or grow-down memory section.
> >>> E.g. heap areas expand upward, stack expand downwards.
> > <
> >> I wonder if the address could be sign-extended, or multi-bit sign-extended?
> >> One may want to have ROM / IO mapped to virtual addresses that are the
> >> same as physical ones, high in memory.
> > <
> > I put ROM in its own 64-bit physical address space.
> > I put MMI/O in its own 64-bit physical address space.
> > I put configuration in its own 64-bit physical address space.
> > Leaving all 64-bits for real memory (DRAM).
<
> As opposed to mapping virtual to physical and then picking off slices of
> physical with apertures that map physical to device?
<
Yes, My 66000 Transport supports a 66-bit universal address space.
<
There are different consistency and coherence rules for these different
spaces, too. ROM ends up cacheable, but does not use cache coherence
messages--lowering overhead. Configuration space accesses are strongly
ordered. While MMI/O is sequentially consistent per Bus:Device,Function.
<
Also note: memory moves that do not cross a page boundary are ATOMIC
(all sent in 1 payload across the transport). So core[k] can feed device[j]
an entire "read disk[i]sector[m] to VA" in a single payload, eliminating another
source of kernel locks--and minimizing the necessity to lean on sequentially
consistency for guarantees of working.
<
This also minimizes HyperVisor overhead when simulating devices on
behalf of non-paravirtualized Guest OSs. HV gets the entire transaction
at once, instead of building it up MMI/O write by MMI/O write.
>
> The problem with embedding subspaces (which is what apertures recognize)
> into the TLB is that it prevents dynamically adding more spaces. Say you
> have two kinds of RAM, on disjoint pins but both with device addresses
> starting at zero. That's just another aperture, but in the TLB its a new
> chip.
>
> Granted that's not something done by bog-standard usage. I may have been
> perverted by experience with partionable pinsets.
<
It is more about recognizing 'empty' encodings once some other encoding is
recognized, then using those bits for other purposes. Entropy.

MitchAlsup <MitchAlsup@aol.com> schrieb:

> There are different consistency and coherence rules for these different
> spaces, too. ROM ends up cacheable, but does not use cache coherence
> messages--lowering overhead.

Could an operating system also choose to apply this to executables
and shared libraries?

On Wednesday, March 16, 2022 at 3:34:55 PM UTC-5, Thomas Koenig wrote:
> MitchAlsup <Mitch...@aol.com> schrieb:
> > There are different consistency and coherence rules for these different
> > spaces, too. ROM ends up cacheable, but does not use cache coherence
> > messages--lowering overhead.
<
> Could an operating system also choose to apply this to executables
> and shared libraries?
<
I am hoping that certain C-library functions are in ROM for exactly these reasons.
under the caveat that ROM is approximately as fast as DRAM.
<
One cannot avoid the coherence traffic in DRAM because HW does not know
that a page will be swapped out to DISK/SSD/over-the-network. With ROM
you actually do know this. {Well, it is possible to swap ROM to disk, but the
ROM still contains the same data, and will continue to contain the same
data even if disk writes over ROM. DRAM does not have this property.}

On Tuesday, March 15, 2022 at 11:33:12 PM UTC-5, robf...@gmail.com wrote:
> On Tuesday, March 15, 2022 at 10:52:20 PM UTC-4, BGB wrote:
> > On 3/15/2022 6:54 PM, MitchAlsup wrote:

> > >>> I started here about 2006.
> I am preferring hash tables over hierarchical tables. They are easier to deal with
> in some ways. They do not need to process in power-of-two addressing so the
> size of entries can be adjusted to suit.
>
This has some minor negative comments about hash tables and
L2 hit rates of cached data (translation tables or otherwise.)
<
https://cs.rice.edu/CS/Architecture/docs/barr-isca10.pdf
>
>
> I am wondering though how often pages of memory are shared?
>
> Using a simple hash table where the table index corresponds to the physical
> address four virtual address entries could be supported at the same cost as
> using a complex hash table that stores both the physical and virtual addresses
> and doubles the size of the table to allow for some sharing. But with the simple
> table sharing would be limited to four shares per page. To get more shares of a
> page pages would need to be replicated at a different physical address. But it
> seems like it could work.
>
> Big users of shared memory are probably the OS and other libraries and frameworks.
>
> Making copies might be one way to help with system integrity. If something
> goes amiss with one copy of the OS, other copies are not affected.

On Wednesday, March 16, 2022 at 4:44:58 PM UTC-4, MitchAlsup wrote:
> On Tuesday, March 15, 2022 at 11:33:12 PM UTC-5, robf...@gmail.com wrote:
> > On Tuesday, March 15, 2022 at 10:52:20 PM UTC-4, BGB wrote:
> > > On 3/15/2022 6:54 PM, MitchAlsup wrote:
>
> > > >>> I started here about 2006.
> > I am preferring hash tables over hierarchical tables. They are easier to deal with
> > in some ways. They do not need to process in power-of-two addressing so the
> > size of entries can be adjusted to suit.
> >
> This has some minor negative comments about hash tables and
> L2 hit rates of cached data (translation tables or otherwise.)
> <
> https://cs.rice.edu/CS/Architecture/docs/barr-isca10.pdf
> >
> >
> > I am wondering though how often pages of memory are shared?
> >
> > Using a simple hash table where the table index corresponds to the physical
> > address four virtual address entries could be supported at the same cost as
> > using a complex hash table that stores both the physical and virtual addresses
> > and doubles the size of the table to allow for some sharing. But with the simple
> > table sharing would be limited to four shares per page. To get more shares of a
> > page pages would need to be replicated at a different physical address. But it
> > seems like it could work.
> >
> > Big users of shared memory are probably the OS and other libraries and frameworks.
> >
> > Making copies might be one way to help with system integrity. If something
> > goes amiss with one copy of the OS, other copies are not affected.

Thanks for the pointer to the article. Hash tables might be better used when worried
about the memory consumption.

My PT now caches PDEs. Save about four clocks per PDE lookup plus memory access time.

>Works great if you have 72-bits in a word. But not so great if you have a 64-bit
>PTE mapping from a 64-bit VA to a 64-bit PA.

It can work with as few as two available bits.

I am using 128-bit PTEs, with physical addressing up to 72 bits. Virtual addressing up to
106 bits. PDEs, page directory entries, are 64-bit. 13+13+13+13+13+13+13+16
Decided to go with 64kB pages now that they can be sectioned off into 1kB chunks.
For a small app < 64kB required, the app could be stored in the page table itself so that all
the extra space in the table is not wasted. It might need only three PTEs for code, data,
and stack and they could all point into the page table page.

64, 1kB stacks for threads associated with a process could all be stored in the same page of
memory.

MitchAlsup <MitchAlsup@aol.com> schrieb:
> On Wednesday, March 16, 2022 at 3:34:55 PM UTC-5, Thomas Koenig wrote:
>> MitchAlsup <Mitch...@aol.com> schrieb:
>> > There are different consistency and coherence rules for these different
>> > spaces, too. ROM ends up cacheable, but does not use cache coherence
>> > messages--lowering overhead.
><
>> Could an operating system also choose to apply this to executables
>> and shared libraries?
><
> I am hoping that certain C-library functions are in ROM for exactly these reasons.
> under the caveat that ROM is approximately as fast as DRAM.

Unlikely to happen for general purpose computers - what should
happen in the event of a security upgrade? And should this ROM
be for Linux, or for Windows, or for one of the BSD variants?
One exception is probably the BIOS.

> One cannot avoid the coherence traffic in DRAM because HW does not know
> that a page will be swapped out to DISK/SSD/over-the-network.

That is the point I was trying to make. The operating system should
know, and if there is a mechanism that it could tell the hardware
"I guarantee you that this page will not change", then that could
have advantages. (If the system in question has a BMC, then this
could get more complicated - could My66000 be run under OpenBMC,
for exaple?)

On 3/17/2022 12:23 AM, Thomas Koenig wrote:
> MitchAlsup <MitchAlsup@aol.com> schrieb:
>> On Wednesday, March 16, 2022 at 3:34:55 PM UTC-5, Thomas Koenig wrote:
>>> MitchAlsup <Mitch...@aol.com> schrieb:
>>>> There are different consistency and coherence rules for these different
>>>> spaces, too. ROM ends up cacheable, but does not use cache coherence
>>>> messages--lowering overhead.
>> <
>>> Could an operating system also choose to apply this to executables
>>> and shared libraries?
>> <
>> I am hoping that certain C-library functions are in ROM for exactly these reasons.
>> under the caveat that ROM is approximately as fast as DRAM.
>
> Unlikely to happen for general purpose computers - what should
> happen in the event of a security upgrade? And should this ROM
> be for Linux, or for Windows, or for one of the BSD variants?
> One exception is probably the BIOS.
>
>> One cannot avoid the coherence traffic in DRAM because HW does not know
>> that a page will be swapped out to DISK/SSD/over-the-network.
>
> That is the point I was trying to make. The operating system should
> know, and if there is a mechanism that it could tell the hardware
> "I guarantee you that this page will not change", then that could
> have advantages.

I must be missing something. If the page is marked with no write
permission, i.e. a page containing executable code, there should be no
coherence traffic. If the OS decides to do some I/O into that page to
change it for some reason, then ISTM that the OS is responsible for
notifying all the relevant caches that the relevant data should be
invalidated.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

BGB <cr88192@gmail.com> wrote:
>
> I am not sure whether "in general" a chain-hash or B-Tree would be
> better for a large sparse address space, would need to model this.

Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
Trees? They're great for searching, high density, but the cost of
updating may be too high for your application. They also depend
critically on a fast POPCOUNT instruction. But even if they don't work
for your application, you might find some inspiration here.

https://lampwww.epfl.ch/papers/idealhashtrees.pdf

Andrew.

Stephen Fuld wrote:
> On 3/17/2022 12:23 AM, Thomas Koenig wrote:
>> MitchAlsup <MitchAlsup@aol.com> schrieb:
>>> On Wednesday, March 16, 2022 at 3:34:55 PM UTC-5, Thomas Koenig wrote:
>>>> MitchAlsup <Mitch...@aol.com> schrieb:
>>>>> There are different consistency and coherence rules for these
>>>>> different
>>>>> spaces, too. ROM ends up cacheable, but does not use cache coherence
>>>>> messages--lowering overhead.
>>> <
>>>> Could an operating system also choose to apply this to executables
>>>> and shared libraries?
>>> <
>>> I am hoping that certain C-library functions are in ROM for exactly
>>> these reasons.
>>> under the caveat that ROM is approximately as fast as DRAM.
>>
>> Unlikely to happen for general purpose computers - what should
>> happen in the event of a security upgrade? And should this ROM
>> be for Linux, or for Windows, or for one of the BSD variants?
>> One exception is probably the BIOS.
>>
>>> One cannot avoid the coherence traffic in DRAM because HW does not know
>>> that a page will be swapped out to DISK/SSD/over-the-network.
>>
>> That is the point I was trying to make. The operating system should
>> know, and if there is a mechanism that it could tell the hardware
>> "I guarantee you that this page will not change", then that could
>> have advantages.
>
> I must be missing something. If the page is marked with no write
> permission, i.e. a page containing executable code, there should be no
> coherence traffic. If the OS decides to do some I/O into that page to
> change it for some reason, then ISTM that the OS is responsible for
> notifying all the relevant caches that the relevant data should be
> invalidated.

A memory address that is marked read-only in an MMU prevents that process
from writing that address. It is not an assertion that this physical
address is unwritable by anyone. Therefore the cache hierarchy cannot
use the read-only protection to optimize how a cache line is managed.

For example in a server that publishes an information table to clients,
a page can be mapped RW in the server and RO in the clients.
The client cache will still receive Invalidates for those RO page lines.

That being said, off hand I can't think of a way that a cache could
make use of a PTE flag that marked a page as "unchangeable".
If it doesn't cache it, then it is the same as other non-cacheable pages.
If it does cache it, then it will just never receive an Invalidate
for those lines and they will eventually fall out.

I suppose it guarantees that such ROM cache evicts can be "silent".
There is no need for home directory for ROM physical address and no
tracking of who has copies, so no one to coordinate with on evicts.
But some coherence protocols already allow for silent Shared evicts.

MitchAlsup wrote:
> On Wednesday, March 16, 2022 at 12:13:39 PM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>>> On Tuesday, March 15, 2022 at 9:46:07 PM UTC-5, robf...@gmail.com wrote:
>>>>> On 3/15/2022 1:08 PM, MitchAlsup wrote:
>>>>> So, what they need is a quick way of getting an address to the failing PTP/PTE.
>>>> I am reminded of a trace cache. Something similar could be used.
>>>>
>>>> It would be easier if a link back to the parent were in a PTP. Since the failing PTE
>>>> / PTP is known, back links could be followed. I wonder if an empty entry in the
>>>> PTP could be used as a back-link. Is it faster to scan a page for a back-link or use
>>>> other means? If there were extra room in the PTP a link could be added in the
>>>> header.
>>> <
>>> Linux uses struct_page (about 2 cache lines per entry) to keep track of "all the
>>> states a page can get into": so struct_page[PPN] gets you to everything you need
>>> to know about a page in 1 layer of indirection.
>>> <
>>> Since HW makes no claims to the bit patterns when p = 0 (present), PPN of this
>>> entry should be pointing at what this non-present PTP would have been pointing
>>> at were it present.
>> The struct_page table is used for different purposes.
>> It is used for recording info about the status of each physical page.
>> There can be multiple virtual addresses in multiple processes
>> mapped to the same physical page.
>>
>> Page faults are different.
>> The page fault exception stack gets the instruction pointer of
>> the start of the faulting instruction, the faulting address,
>> and some status bits indicating the error, what access was being attempted.
> <
> Page Fault gets attached to thread number (which accesses the faulting IP)
> ....................gets the faulting instruction-specifier in R1

I assume this is the instruction pointer.

> ....................gets the faulting virtual address in R2
> ....................gets the address of fault generating PTE/PTP in R3

Passing the physical address of the faulting PTE to the page fault
handler doesn't harm anything but it doesn't really help.
Though I've not seen a page fault exception frame the does this.

This misses the critical page fault reason info. The page fault handler
needs to know what the thread was attempting to do when it triggered
the fault. Looking at x86 that is a set of bit flags indicating:

P = Caused by Not-Present PTE, or other protection codes
R/W = Caused by Read, or caused by Write
U/S = Cause by User/Super mode
RSVD = Reserved bit non-zero
I/D = access was instruction fetch, or data access
PK = Protection Key violation
SGX = SGX Software Guard Extensions violation

> If the problem is in Guest OS translations Guest OS page fault handler
> receives control. If the problem is in HyperVisor Tables, HV page fault
> handler receives control. In both cases the faulting thread becomes
> a "customer" of the fault handler. This customer thing is a means to
> access customer memory to fix exceptions, and access to customer
> state {to fix page tables,...} from afar using indirection without needing
> to have the customer virtual memory mapped into handler.

Ok, except that is not how OS's currently handle page faults.
They assume each thread receives its own page faults and "fixes itself".
Your approach is more like how Mach OS does things.

>> The page faulting thread's handler acquires a page table mutex
>> and uses the faulting virtual address to walk down the PGT doing
>> the same checks a HW walker would do. For it to access the page table
>> the PTP must (somehow) already be mapped into virtual memory.
> <
> No need to walk the tables you already have a pointer to the fault detecting
> PTP/PTE. Only if you need to go back up the table do you need to walk it.
> But, here, you can LDPT LVL-1 and let HW give you the address to the
> upper level table.

This assumes direct access to memory through a physical address.
Some OS do have a memory section that maps all of physical memory into
a virtual range indexed by physical page number for exactly this purpose.
However that takes up a big chunk of kernel virtual space.
That is not always possible so kernel dynamically adds a PTE to itself to
map the target physical address, access memory, unmaps the target address.

Using the faulting virtual address to walk the already self-mapped PTP's
accomplishes the same thing in a portable manner.

>> There are many situations that can occur.
>> Two threads could have faulted the same page at once.
>> The first fixes the fault, releases the mutex and returns.
>> The second walks the table and finds the fault already fixed
>> and just returns.
> <
> Except you don't have to walk the table.

Its not that big of a burdened and the algorithm is portable.

>> Or maybe it walks the table and finds an interior PTP marked Not-Present.
>> Or maybe the faulting page was Present but marked read-only and
>> this thread attempted a write.
> <
> Anything is possible; you just don't have to walk the table; you receive
> control with a pointer to where the fault detecting memory management
> pointer PTP/PTE resides in the translation tables themselves.
> <
> And you only have to lock the table if you want to change it.
> And when you get the table locked, you have to check that the table has
> not already been updated by some other thread. More test-and-test-and-set
> than just test-and-set.

Ok I think I see where you are going with this now.
You want to eliminate the software table walk, which eliminates
the need to acquire a page table mutex for some/many situations
and allow the PTE to be fixed "atomically".

The thing is there are other data structures that are guarded by
that one mutex on "the process address space"
- the process page table
- the virtual section table.
- maybe working set tracking tables if an OS has them.

There are other data structures with their own mutexes:
shared memory sections, page file management management, file system.

The page fault handler needs access to all these data structures
in a synchronized manner. So even if you could eliminate the
SW table walk for some situations, that is not going to buy you much.

On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Wednesday, March 16, 2022 at 12:13:39 PM UTC-5, EricP wrote:
> >> MitchAlsup wrote:
> >>> On Tuesday, March 15, 2022 at 9:46:07 PM UTC-5, robf...@gmail.com wrote:
> >>>>> On 3/15/2022 1:08 PM, MitchAlsup wrote:
> >>>>> So, what they need is a quick way of getting an address to the failing PTP/PTE.
> >>>> I am reminded of a trace cache. Something similar could be used.
> >>>>
> >>>> It would be easier if a link back to the parent were in a PTP. Since the failing PTE
> >>>> / PTP is known, back links could be followed. I wonder if an empty entry in the
> >>>> PTP could be used as a back-link. Is it faster to scan a page for a back-link or use
> >>>> other means? If there were extra room in the PTP a link could be added in the
> >>>> header.
> >>> <
> >>> Linux uses struct_page (about 2 cache lines per entry) to keep track of "all the
> >>> states a page can get into": so struct_page[PPN] gets you to everything you need
> >>> to know about a page in 1 layer of indirection.
> >>> <
> >>> Since HW makes no claims to the bit patterns when p = 0 (present), PPN of this
> >>> entry should be pointing at what this non-present PTP would have been pointing
> >>> at were it present.
> >> The struct_page table is used for different purposes.
> >> It is used for recording info about the status of each physical page.
> >> There can be multiple virtual addresses in multiple processes
> >> mapped to the same physical page.
> >>
> >> Page faults are different.
> >> The page fault exception stack gets the instruction pointer of
> >> the start of the faulting instruction, the faulting address,
> >> and some status bits indicating the error, what access was being attempted.
> > <
> > Page Fault gets attached to thread number (which accesses the faulting IP)
> > ....................gets the faulting instruction-specifier in R1
>
> I assume this is the instruction pointer.
<
It is the first 32-bits of the instruction itself. This contains everything but the
constants.
<
>
> > ....................gets the faulting virtual address in R2
> > ....................gets the address of fault generating PTE/PTP in R3
>
> Passing the physical address of the faulting PTE to the page fault
> handler doesn't harm anything but it doesn't really help.
> Though I've not seen a page fault exception frame the does this.
>
> This misses the critical page fault reason info. The page fault handler
> needs to know what the thread was attempting to do when it triggered
> the fault. Looking at x86 that is a set of bit flags indicating:
>
> P = Caused by Not-Present PTE, or other protection codes
> R/W = Caused by Read, or caused by Write
> U/S = Cause by User/Super mode
> RSVD = Reserved bit non-zero
> I/D = access was instruction fetch, or data access
> PK = Protection Key violation
> SGX = SGX Software Guard Extensions violation
<
The given address points at the PT[PE] where the fault was detected.
So, for example if you were trying to Read the first PT[PE] that does not have
read permission is where you end up pointing {same for write and execute}
<
The instruction tells you what the instruction stream was doing.
Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
Inst<31..26> = 1000xx LD
Inst<31..26> = 1001xx ST
<
So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
{mal-formed instructions arrive at the Operation exception handler}
the page fault handler can look at Instruction<31> and decide to look at
Inst<28> or Inst<7> where 0->LD and 1->ST.
So 3 PREDs in a row parse the instruction that caused the page fault.
<
But you make a good point:: I have another 32-bits in R1 I could completely
specify what problem was detected. Let me work on that.
<
My 66000 does not have a u/s mode in the architecture
..................does not have storage keys (yet)
..................does not have software guard extension
..................Keeps RWE separate
<
> > If the problem is in Guest OS translations Guest OS page fault handler
> > receives control. If the problem is in HyperVisor Tables, HV page fault
> > handler receives control. In both cases the faulting thread becomes
> > a "customer" of the fault handler. This customer thing is a means to
> > access customer memory to fix exceptions, and access to customer
> > state {to fix page tables,...} from afar using indirection without needing
> > to have the customer virtual memory mapped into handler.
<
> Ok, except that is not how OS's currently handle page faults.
<
My model allows for applications to use 64-bit virtual address space,
while allowing the HyperVisor to have its 64-bit virtual address space,
and each guest OS to have its 64-bit virtual address space. All separate.
While having 64-bit physical address space for DRAM.
<
> They assume each thread receives its own page faults and "fixes itself".
> Your approach is more like how Mach OS does things.
<
My 66000 model is still that some service provider handles page faults
and when done, returns control to fault initiator. The only real difference
is the the service provider does not have to have its translation tables
map the excepting application.
<
> >> The page faulting thread's handler acquires a page table mutex
> >> and uses the faulting virtual address to walk down the PGT doing
> >> the same checks a HW walker would do. For it to access the page table
> >> the PTP must (somehow) already be mapped into virtual memory.
> > <
> > No need to walk the tables you already have a pointer to the fault detecting
> > PTP/PTE. Only if you need to go back up the table do you need to walk it.
> > But, here, you can LDPT LVL-1 and let HW give you the address to the
> > upper level table.
<
> This assumes direct access to memory through a physical address.
<
No; it assumes a memory reference instruction who kicks the table walker
in the side, and lets the table walker do its job. Its just the result goes into a
register instead of going into the TLB. So, for example, Guest OS could ask
for Level-3 table entry; table walker has to walk Application table, which
has to walk HyperVisor table for Guest OS, to get a PT[PE] to Guest OS
{never being able to see any HyperVisor state or even know one is present}.
<
> Some OS do have a memory section that maps all of physical memory into
> a virtual range indexed by physical page number for exactly this purpose.
> However that takes up a big chunk of kernel virtual space.
<
Which is why is is better to do this with PTE at a high level than a Root.
<
> That is not always possible so kernel dynamically adds a PTE to itself to
> map the target physical address, access memory, unmaps the target address.
>
> Using the faulting virtual address to walk the already self-mapped PTP's
> accomplishes the same thing in a portable manner.
<> >> There are many situations that can occur.
> >> Two threads could have faulted the same page at once.
> >> The first fixes the fault, releases the mutex and returns.
> >> The second walks the table and finds the fault already fixed
> >> and just returns.
> > <
> > Except you don't have to walk the table.
> Its not that big of a burdened and the algorithm is portable.
> >> Or maybe it walks the table and finds an interior PTP marked Not-Present.
> >> Or maybe the faulting page was Present but marked read-only and
> >> this thread attempted a write.
> > <
> > Anything is possible; you just don't have to walk the table; you receive
> > control with a pointer to where the fault detecting memory management
> > pointer PTP/PTE resides in the translation tables themselves.
> > <
> > And you only have to lock the table if you want to change it.
> > And when you get the table locked, you have to check that the table has
> > not already been updated by some other thread. More test-and-test-and-set
> > than just test-and-set.
<
> Ok I think I see where you are going with this now.
> You want to eliminate the software table walk, which eliminates
> the need to acquire a page table mutex for some/many situations
> and allow the PTE to be fixed "atomically".
>
> The thing is there are other data structures that are guarded by
> that one mutex on "the process address space"
> - the process page table
> - the virtual section table.
> - maybe working set tracking tables if an OS has them.
<
Either more Mutexes are in order, or you grab the big one in early generation
ports and clean it up in later ports.
>
> There are other data structures with their own mutexes:
> shared memory sections, page file management management, file system.
>
> The page fault handler needs access to all these data structures
> in a synchronized manner. So even if you could eliminate the
> SW table walk for some situations, that is not going to buy you much.
<
It prevents a bunch of field extractions,
if the page fault was recent, the tables are going to be found in L2--say
......15 cycles per layer in the page hierarchy,
Handler only needs faulting Root pointer.
It uses the table walk accelerators
......(which are guaranteed to hit on recent fault),
And it saves the flow control overhead incurred with level skipping,
So instead of taking 100+ (1-level) cycles it takes 5-cycles using Guest OS
and HyperVisor tables as they sit in their various memory spaces.
<
But on the large scheme of things maybe this is not many cycles.

On 3/18/2022 4:51 AM, aph@littlepinkcloud.invalid wrote:
> BGB <cr88192@gmail.com> wrote:
>>
>> I am not sure whether "in general" a chain-hash or B-Tree would be
>> better for a large sparse address space, would need to model this.
>
> Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
> Trees? They're great for searching, high density, but the cost of
> updating may be too high for your application. They also depend
> critically on a fast POPCOUNT instruction. But even if they don't work
> for your application, you might find some inspiration here.
>
> https://lampwww.epfl.ch/papers/idealhashtrees.pdf
>

It is possible, though I don't have a direct analog of this instruction.

I have yet to evaluate performance tradeoffs, but thus far the AVL trees
appear to be the clear winner in terms of memory overhead (for some
simple synthetic tests) among the options I have tested thus far.

So, for example, 256x 1MB at random addresses:
3-level page table: 8MB
8-level page table: 33MB
AVL Tree: 512K
Hybrid AVL (Last Level is Page Table): 4MB

Current suspicion is that an AVL tree walk will be significantly slower
than a page-table walk.

The AVL Tree variants don't really care as much about address space
size, and will take about the same space in both a 48 and 96 bit address
space (unlike traditional page tables).

I have yet to implement and test a B-Tree.
I have also yet to evaluate the code complexity tradeoffs of the B-Tree.

However, the B-Tree is likely to use up less space than the AVL Tree,
but is likely to be slower (Still TBD).

In the hybrid approach, the AVL tree is used to point to the last level
of a page-table, using page-table pages for the "bottom" level. In
theory, this could be space-competitive, but only when the last-level
pages are more than 25% full (doesn't happen with 1MB allocs).

However, these would reduce the number of "last-level" steps.

One issue with the AVL tree implementation is that I haven't yet gotten
the tree rebalancing working correctly as of yet, which is a fairly
critical part of making the performance "reasonable" (otherwise,
inserting items in sequential order is prone to significantly
unbalancing the tree).

The AVL code isn't helped though by being implemented via a bunch of
bit-twiddly (obscuring where the logic is going wrong). I could have
used structs, but this would likely be slower.

Balancing is less of an issue with B-Trees, as the design of the
structure keeps the tree balanced. Nodes split and merge laterally,
rather than being inserted below another element and then rotated into
position. However, a B-Tree may need to be able to split the top-level
node, whereas node-splitting doesn't exist for AVL Trees.

I may also need to compare against a chain hash.
It is not clear which would win yet: hash walking is simpler, but chain
lengths are likely to be longer than the log2 lookup distance.

I am not sure yet whether a naive benchmark performed on x86 will be
directly comparable to results on BJX2.

I am testing this at present within a partial mockup of TestKern's
memory management facilities implemented on x86-64.

....

May post more when I do more testing here...

On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
> On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
> > BGB <cr8...@gmail.com> wrote:
> >>
> >> I am not sure whether "in general" a chain-hash or B-Tree would be
> >> better for a large sparse address space, would need to model this.
> >
> > Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
> > Trees? They're great for searching, high density, but the cost of
> > updating may be too high for your application. They also depend
> > critically on a fast POPCOUNT instruction. But even if they don't work
> > for your application, you might find some inspiration here.
> >
> > https://lampwww.epfl.ch/papers/idealhashtrees.pdf
> >
> It is possible, though I don't have a direct analog of this instruction.
>
>
> I have yet to evaluate performance tradeoffs, but thus far the AVL trees
> appear to be the clear winner in terms of memory overhead (for some
> simple synthetic tests) among the options I have tested thus far.
>
>
> So, for example, 256x 1MB at random addresses:
> 3-level page table: 8MB
> 8-level page table: 33MB
> AVL Tree: 512K
> Hybrid AVL (Last Level is Page Table): 4MB
>
> Current suspicion is that an AVL tree walk will be significantly slower
> than a page-table walk.
<
At 1 memory ref per level and 1-bit of VA per level, you can be your bottom
dollar it would be slow. 51-level table when application is "really big". When
application is the sizeof "cat" you would only be making 3-accesses per walk.
<
With 1MB sized application and 4K pages, 8-level AVL walk, but the size of the
page tables is about 2 pages. With level skipping conventional page tables
the number of pages will be about 5. With level-skipping sized-super-pages
the size of the translation table is about 1 page.
<
>
> The AVL Tree variants don't really care as much about address space
> size, and will take about the same space in both a 48 and 96 bit address
> space (unlike traditional page tables).
>
>
> I have yet to implement and test a B-Tree.
> I have also yet to evaluate the code complexity tradeoffs of the B-Tree.
>
> However, the B-Tree is likely to use up less space than the AVL Tree,
> but is likely to be slower (Still TBD).
>
>
> In the hybrid approach, the AVL tree is used to point to the last level
> of a page-table, using page-table pages for the "bottom" level. In
> theory, this could be space-competitive, but only when the last-level
> pages are more than 25% full (doesn't happen with 1MB allocs).
>
> However, these would reduce the number of "last-level" steps.
>
>
>
>
> One issue with the AVL tree implementation is that I haven't yet gotten
> the tree rebalancing working correctly as of yet, which is a fairly
> critical part of making the performance "reasonable" (otherwise,
> inserting items in sequential order is prone to significantly
> unbalancing the tree).
>
> The AVL code isn't helped though by being implemented via a bunch of
> bit-twiddly (obscuring where the logic is going wrong). I could have
> used structs, but this would likely be slower.
>
> Balancing is less of an issue with B-Trees, as the design of the
> structure keeps the tree balanced. Nodes split and merge laterally,
> rather than being inserted below another element and then rotated into
> position. However, a B-Tree may need to be able to split the top-level
> node, whereas node-splitting doesn't exist for AVL Trees.
>
>
> I may also need to compare against a chain hash.
> It is not clear which would win yet: hash walking is simpler, but chain
> lengths are likely to be longer than the log2 lookup distance.
>
>
>
> I am not sure yet whether a naive benchmark performed on x86 will be
> directly comparable to results on BJX2.
>
> I am testing this at present within a partial mockup of TestKern's
> memory management facilities implemented on x86-64.
>
>
> ...
>
> May post more when I do more testing here...

On Friday, March 18, 2022 at 6:53:44 PM UTC-4, MitchAlsup wrote:
> On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
> > On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
> > > BGB <cr8...@gmail.com> wrote:
> > >>
> > >> I am not sure whether "in general" a chain-hash or B-Tree would be
> > >> better for a large sparse address space, would need to model this.
> > >
> > > Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
> > > Trees? They're great for searching, high density, but the cost of
> > > updating may be too high for your application. They also depend
> > > critically on a fast POPCOUNT instruction. But even if they don't work
> > > for your application, you might find some inspiration here.
> > >
> > > https://lampwww.epfl.ch/papers/idealhashtrees.pdf
> > >
> > It is possible, though I don't have a direct analog of this instruction.
> >
> >
> > I have yet to evaluate performance tradeoffs, but thus far the AVL trees
> > appear to be the clear winner in terms of memory overhead (for some
> > simple synthetic tests) among the options I have tested thus far.
> >
> >
> > So, for example, 256x 1MB at random addresses:
> > 3-level page table: 8MB
> > 8-level page table: 33MB
> > AVL Tree: 512K
> > Hybrid AVL (Last Level is Page Table): 4MB
> >
> > Current suspicion is that an AVL tree walk will be significantly slower
> > than a page-table walk.
> <
> At 1 memory ref per level and 1-bit of VA per level, you can be your bottom
> dollar it would be slow. 51-level table when application is "really big". When
> application is the sizeof "cat" you would only be making 3-accesses per walk.
> <
> With 1MB sized application and 4K pages, 8-level AVL walk, but the size of the
> page tables is about 2 pages. With level skipping conventional page tables
> the number of pages will be about 5. With level-skipping sized-super-pages
> the size of the translation table is about 1 page.
> <
> >
> > The AVL Tree variants don't really care as much about address space
> > size, and will take about the same space in both a 48 and 96 bit address
> > space (unlike traditional page tables).
> >
> >
> > I have yet to implement and test a B-Tree.
> > I have also yet to evaluate the code complexity tradeoffs of the B-Tree.
> >
> > However, the B-Tree is likely to use up less space than the AVL Tree,
> > but is likely to be slower (Still TBD).
> >
> >
> > In the hybrid approach, the AVL tree is used to point to the last level
> > of a page-table, using page-table pages for the "bottom" level. In
> > theory, this could be space-competitive, but only when the last-level
> > pages are more than 25% full (doesn't happen with 1MB allocs).
> >
> > However, these would reduce the number of "last-level" steps.
> >
> >
> >
> >
> > One issue with the AVL tree implementation is that I haven't yet gotten
> > the tree rebalancing working correctly as of yet, which is a fairly
> > critical part of making the performance "reasonable" (otherwise,
> > inserting items in sequential order is prone to significantly
> > unbalancing the tree).
> >
> > The AVL code isn't helped though by being implemented via a bunch of
> > bit-twiddly (obscuring where the logic is going wrong). I could have
> > used structs, but this would likely be slower.
> >
> > Balancing is less of an issue with B-Trees, as the design of the
> > structure keeps the tree balanced. Nodes split and merge laterally,
> > rather than being inserted below another element and then rotated into
> > position. However, a B-Tree may need to be able to split the top-level
> > node, whereas node-splitting doesn't exist for AVL Trees.
> >
> >
> > I may also need to compare against a chain hash.
> > It is not clear which would win yet: hash walking is simpler, but chain
> > lengths are likely to be longer than the log2 lookup distance.
> >
> >
> >
> > I am not sure yet whether a naive benchmark performed on x86 will be
> > directly comparable to results on BJX2.
> >
> > I am testing this at present within a partial mockup of TestKern's
> > memory management facilities implemented on x86-64.
> >
> >
> > ...
> >
> > May post more when I do more testing here...

My favorite has got to be hash tables although they are likely a bit slower than
hierarchical tables if MMU caches are used. They conserve memory space
which may be important for smaller systems. A small hash table could fit
entirely in a cache. For the FPGA board only 8192 pages need be managed,
256k RAM. It is tempting to dedicate block RAM for this rather than use main
memory and possibly get rid of the TLB. I could then make the RAM wide so
that a PTG could read in a single cycle. The hash table can likely be entirely
resident in memory.

If page table groups are used, keys that hash to the same value end up in the
same group. This can be used to get some locality of reference. I have my hash
function ignoring an extra pair of low address bits. That means hashes of similar
addresses will hash to the same PTG making it local. I also cache the PTGs in
the MMU so for a small set of address hashes things are coming from the cache.
Entries could be re-arranged in the PTGs to give move frequently used entries
preference so that they are hit first.

I have the page tables located in the physical address space instead of the virtual
address space. Are page tables ever located in the virtual address space? It
seems to me that would require the ability to process nested TLB misses.

I am wondering if ASLR is used for page tables? I am assuming the OS could move
data around to different physical pages to randomize things then update the page
table to point to the new data location.

On 3/18/2022 5:53 PM, MitchAlsup wrote:
> On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
>> On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
>>> BGB <cr8...@gmail.com> wrote:
>>>>
>>>> I am not sure whether "in general" a chain-hash or B-Tree would be
>>>> better for a large sparse address space, would need to model this.
>>>
>>> Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
>>> Trees? They're great for searching, high density, but the cost of
>>> updating may be too high for your application. They also depend
>>> critically on a fast POPCOUNT instruction. But even if they don't work
>>> for your application, you might find some inspiration here.
>>>
>>> https://lampwww.epfl.ch/papers/idealhashtrees.pdf
>>>
>> It is possible, though I don't have a direct analog of this instruction.
>>
>>
>> I have yet to evaluate performance tradeoffs, but thus far the AVL trees
>> appear to be the clear winner in terms of memory overhead (for some
>> simple synthetic tests) among the options I have tested thus far.
>>
>>
>> So, for example, 256x 1MB at random addresses:
>> 3-level page table: 8MB
>> 8-level page table: 33MB
>> AVL Tree: 512K
>> Hybrid AVL (Last Level is Page Table): 4MB
>>
>> Current suspicion is that an AVL tree walk will be significantly slower
>> than a page-table walk.
> <
> At 1 memory ref per level and 1-bit of VA per level, you can be your bottom
> dollar it would be slow. 51-level table when application is "really big". When
> application is the sizeof "cat" you would only be making 3-accesses per walk.
> <
> With 1MB sized application and 4K pages, 8-level AVL walk, but the size of the
> page tables is about 2 pages. With level skipping conventional page tables
> the number of pages will be about 5. With level-skipping sized-super-pages
> the size of the translation table is about 1 page.
> <

In this case, it is more about trying to conserve memory than making it
fast. Aggressive ASLR would do bad things to page-table size.

In ongoing tests, direct page table is fastest by a significant margin.

AVL vs Hash seems to be break-even ~ 384MB (24576 pages).
Less than this, Hash is faster;
More than this, AVL is faster.

Both of these seem to be around 10x slower than the 3-level page table.
The 8-level table is around 4x slower than the 3-level table.

At this point:
Hash size is 2048, So ~ 12 steps per hash chain.
Log2 is ~ 14.6 ...

This is slightly curious though as I would have expected the chain-hash
walk to be slightly faster. Either way, seems to follow the (expected)
pattern that whichever results in the shorter path length wins.

The "hybrid" strategy is around twice as fast as the pure AVL, or around
5x slower than the 3-level page table.

The hybrid strategy benefits considerably if one does a smaller number
of larger allocations (whereas neither Hash nor AVL gain much here).

Both the AVL Tree and Chain Hash seem to end up taking approximately the
same amount of memory in this case.

It also seems that the time is directly proportional to the number of
steps needed to get to the target.

Granted, ended up "cheesing it" for the AVL rebalancing, as I didn't
implement the full set of node rotations (2 out of 4), which seems to
result in the rebalancing getting "stuck" in situations where it tries
in vain to endlessly rotate the same nodes (and getting stuck in an
infinite loop).

The cheese strategy being to keep a counter, and if the rebalancing
takes too many steps, it gives up and stops rotating the nodes.

Could try implementing a B-Tree, but at this point I am not super
optimistic about it...

Some of this also opens up the possibility of a Radix-8 or Radix-16
table, which functions (in premise) similar to a conventional page
table, except that each directory only has 8 or 16 entries.

Though, a Radix-16 table would need 24 steps to resolve a 96-bit
address, which implies that (based on the currently seen pattern) this
would likely be slower than the AVL tree.

....

On Friday, March 18, 2022 at 10:13:22 PM UTC-4, BGB wrote:
> On 3/18/2022 5:53 PM, MitchAlsup wrote:
> > On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
> >> On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
> >>> BGB <cr8...@gmail.com> wrote:
> >>>>
> >>>> I am not sure whether "in general" a chain-hash or B-Tree would be
> >>>> better for a large sparse address space, would need to model this.
> >>>
> >>> Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
> >>> Trees? They're great for searching, high density, but the cost of
> >>> updating may be too high for your application. They also depend
> >>> critically on a fast POPCOUNT instruction. But even if they don't work
> >>> for your application, you might find some inspiration here.
> >>>
> >>> https://lampwww.epfl.ch/papers/idealhashtrees.pdf
> >>>
> >> It is possible, though I don't have a direct analog of this instruction.
> >>
> >>
> >> I have yet to evaluate performance tradeoffs, but thus far the AVL trees
> >> appear to be the clear winner in terms of memory overhead (for some
> >> simple synthetic tests) among the options I have tested thus far.
> >>
> >>
> >> So, for example, 256x 1MB at random addresses:
> >> 3-level page table: 8MB
> >> 8-level page table: 33MB
> >> AVL Tree: 512K
> >> Hybrid AVL (Last Level is Page Table): 4MB
> >>
> >> Current suspicion is that an AVL tree walk will be significantly slower
> >> than a page-table walk.
> > <
> > At 1 memory ref per level and 1-bit of VA per level, you can be your bottom
> > dollar it would be slow. 51-level table when application is "really big". When
> > application is the sizeof "cat" you would only be making 3-accesses per walk.
> > <
> > With 1MB sized application and 4K pages, 8-level AVL walk, but the size of the
> > page tables is about 2 pages. With level skipping conventional page tables
> > the number of pages will be about 5. With level-skipping sized-super-pages
> > the size of the translation table is about 1 page.
> > <
> In this case, it is more about trying to conserve memory than making it
> fast. Aggressive ASLR would do bad things to page-table size.
>
>
> In ongoing tests, direct page table is fastest by a significant margin.
>
> AVL vs Hash seems to be break-even ~ 384MB (24576 pages).
> Less than this, Hash is faster;
> More than this, AVL is faster.
>
>
> Both of these seem to be around 10x slower than the 3-level page table.
> The 8-level table is around 4x slower than the 3-level table.
>
>
>
> At this point:
> Hash size is 2048, So ~ 12 steps per hash chain.
> Log2 is ~ 14.6 ...
>
> This is slightly curious though as I would have expected the chain-hash
> walk to be slightly faster. Either way, seems to follow the (expected)
> pattern that whichever results in the shorter path length wins.
>
>
> The "hybrid" strategy is around twice as fast as the pure AVL, or around
> 5x slower than the 3-level page table.
>
> The hybrid strategy benefits considerably if one does a smaller number
> of larger allocations (whereas neither Hash nor AVL gain much here).
>
>
> Both the AVL Tree and Chain Hash seem to end up taking approximately the
> same amount of memory in this case.
>
>
> It also seems that the time is directly proportional to the number of
> steps needed to get to the target.
>
>
>
> Granted, ended up "cheesing it" for the AVL rebalancing, as I didn't
> implement the full set of node rotations (2 out of 4), which seems to
> result in the rebalancing getting "stuck" in situations where it tries
> in vain to endlessly rotate the same nodes (and getting stuck in an
> infinite loop).
>
> The cheese strategy being to keep a counter, and if the rebalancing
> takes too many steps, it gives up and stops rotating the nodes.
>
>
> Could try implementing a B-Tree, but at this point I am not super
> optimistic about it...
>
>
> Some of this also opens up the possibility of a Radix-8 or Radix-16
> table, which functions (in premise) similar to a conventional page
> table, except that each directory only has 8 or 16 entries.
>
> Though, a Radix-16 table would need 24 steps to resolve a 96-bit
> address, which implies that (based on the currently seen pattern) this
> would likely be slower than the AVL tree.
>
> ...

>At this point:
>Hash size is 2048, So ~ 12 steps per hash chain.
>Log2 is ~ 14.6 ...

That does not sound right. A decent hash usually averages 1.2 steps.
Decimal in the wrong place?
I am just in the process of getting a hash table to work. It is only 3.5x as
many block rams as the TLB was. Uses a 256-bit wide port on the cpu side
for loading and storing and a 2048-bit wide port on the memory side to
allow an entire page group to be read in a single cycle. It has the same
performance as a cache. But the block RAM is dedicated in the BIU, bus
interface unit, so it would not work with a multi-core cpu. Keeping the
RAM coherent between cores would be a challenge.

robf...@gmail.com wrote:
>
> I have the page tables located in the physical address space instead of the virtual
> address space. Are page tables ever located in the virtual address space? It
> seems to me that would require the ability to process nested TLB misses.

Yes, VAX had page tables located in virtual space.
I never looked in detail at Alpha/VMS but since it used a software
managed TLB it was quite possible they emulated it there too
as that's probably cheaper than rewriting an OS.
Alpha 21064 also had a virtually indexed L1 cache which
would have functioned equivalent to a large second level TLB.

Yes, VAX used nested TLB misses. IIRC...
Address space was separated into 4 regions by the 2 upper address bits.
These were process space P0 (user), and P1 (supervisor),
and system space S0 (executive) and S1 (kernel).

Address bits [29:9] were the Virtual Page Number (VPN).
System space S1 was mapped by the system page table, a vector of PTE's
stored in S1, indexed from a *physical* base register using the VPN,
with a count register giving the number of valid PTE's.

Process space P0 and P1 were each mapped by a page table, a vector of
PTE's indexed from a *virtual* base register using the VPN,
with a count register giving the number of valid PTE's.
The virtual addresses in the P0 and P1 base registers are
virtual addresses in S1 space.

Translation extracts the VPN for user code/data and looks up in TLB.
(1) If it is a hit then it gets the physical address.
(2) If it is a TLB-miss then it adds the VPN to the P0-base creating
a system virtual address for the PTE which it looks up in TLB.
(3) If it is a hit then it loads the PTE into TLB and repeats (1).
(4) If it is a TLB-miss then it extracts the VPN from the PTE's
system virtual address and adds it to the S1-base creating
a system physical address for the system PTE,
which it loads to TLB and repeats (3).

And the PTE Present and protection bits are being checked at each step.

The net effect is a backwards page table walk.
Intel also does a backward table walk but it does so by caching
interior page table nodes in the TLB while walking down the tree.

Because the process and system page table pages are virtually indexed
the OS can choose which process and system page table pages to swap.

A process address space switch can be accomplished by simply
changing the P0-base and P1-base registers to different values.
They will index to different PTE's in the system space.

On 3/19/2022 8:26 AM, robf...@gmail.com wrote:
> On Friday, March 18, 2022 at 10:13:22 PM UTC-4, BGB wrote:
>> On 3/18/2022 5:53 PM, MitchAlsup wrote:
>>> On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
>>>> On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
>>>>> BGB <cr8...@gmail.com> wrote:
>>>>>>
>>>>>> I am not sure whether "in general" a chain-hash or B-Tree would be
>>>>>> better for a large sparse address space, would need to model this.
>>>>>
>>>>> Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
>>>>> Trees? They're great for searching, high density, but the cost of
>>>>> updating may be too high for your application. They also depend
>>>>> critically on a fast POPCOUNT instruction. But even if they don't work
>>>>> for your application, you might find some inspiration here.
>>>>>
>>>>> https://lampwww.epfl.ch/papers/idealhashtrees.pdf
>>>>>
>>>> It is possible, though I don't have a direct analog of this instruction.
>>>>
>>>>
>>>> I have yet to evaluate performance tradeoffs, but thus far the AVL trees
>>>> appear to be the clear winner in terms of memory overhead (for some
>>>> simple synthetic tests) among the options I have tested thus far.
>>>>
>>>>
>>>> So, for example, 256x 1MB at random addresses:
>>>> 3-level page table: 8MB
>>>> 8-level page table: 33MB
>>>> AVL Tree: 512K
>>>> Hybrid AVL (Last Level is Page Table): 4MB
>>>>
>>>> Current suspicion is that an AVL tree walk will be significantly slower
>>>> than a page-table walk.
>>> <
>>> At 1 memory ref per level and 1-bit of VA per level, you can be your bottom
>>> dollar it would be slow. 51-level table when application is "really big". When
>>> application is the sizeof "cat" you would only be making 3-accesses per walk.
>>> <
>>> With 1MB sized application and 4K pages, 8-level AVL walk, but the size of the
>>> page tables is about 2 pages. With level skipping conventional page tables
>>> the number of pages will be about 5. With level-skipping sized-super-pages
>>> the size of the translation table is about 1 page.
>>> <
>> In this case, it is more about trying to conserve memory than making it
>> fast. Aggressive ASLR would do bad things to page-table size.
>>
>>
>> In ongoing tests, direct page table is fastest by a significant margin.
>>
>> AVL vs Hash seems to be break-even ~ 384MB (24576 pages).
>> Less than this, Hash is faster;
>> More than this, AVL is faster.
>>
>>
>> Both of these seem to be around 10x slower than the 3-level page table.
>> The 8-level table is around 4x slower than the 3-level table.
>>
>>
>>
>> At this point:
>> Hash size is 2048, So ~ 12 steps per hash chain.
>> Log2 is ~ 14.6 ...
>>
>> This is slightly curious though as I would have expected the chain-hash
>> walk to be slightly faster. Either way, seems to follow the (expected)
>> pattern that whichever results in the shorter path length wins.
>>
>>
>> The "hybrid" strategy is around twice as fast as the pure AVL, or around
>> 5x slower than the 3-level page table.
>>
>> The hybrid strategy benefits considerably if one does a smaller number
>> of larger allocations (whereas neither Hash nor AVL gain much here).
>>
>>
>> Both the AVL Tree and Chain Hash seem to end up taking approximately the
>> same amount of memory in this case.
>>
>>
>> It also seems that the time is directly proportional to the number of
>> steps needed to get to the target.
>>
>>
>>
>> Granted, ended up "cheesing it" for the AVL rebalancing, as I didn't
>> implement the full set of node rotations (2 out of 4), which seems to
>> result in the rebalancing getting "stuck" in situations where it tries
>> in vain to endlessly rotate the same nodes (and getting stuck in an
>> infinite loop).
>>
>> The cheese strategy being to keep a counter, and if the rebalancing
>> takes too many steps, it gives up and stops rotating the nodes.
>>
>>
>> Could try implementing a B-Tree, but at this point I am not super
>> optimistic about it...
>>
>>
>> Some of this also opens up the possibility of a Radix-8 or Radix-16
>> table, which functions (in premise) similar to a conventional page
>> table, except that each directory only has 8 or 16 entries.
>>
>> Though, a Radix-16 table would need 24 steps to resolve a 96-bit
>> address, which implies that (based on the currently seen pattern) this
>> would likely be slower than the AVL tree.
>>
>> ...
>
>> At this point:
>> Hash size is 2048, So ~ 12 steps per hash chain.
>> Log2 is ~ 14.6 ...
>
> That does not sound right. A decent hash usually averages 1.2 steps.
> Decimal in the wrong place?

24576 pages, with a 2048-entry chain hash: 24576/2048 = 12.
Both theoretical estimates and measured values appear to roughly agree here.

One could make the starting hash bigger, which would reduce this, say:
24576 pages, with a 4096-entry chain hash: 24576/4096 = 6.

So, one goes through the first stage hash, and then it becomes a linked
list walk. The size of the first hash working as constant division
factor for the average linked-list length.

This was the measured "break-even" point (according to benchmarks on
x86-64). A smaller number of pages favors the hash, a larger number
favors AVL.

A direct hash would give 1 or 2 steps, however, a direct hash could not
be expanded linearly (resizing a direct hash requires rehashing
everything in the hash table).

So, I went with a chain-hash in this test.

The mystery, though, is why the per-element cost in the hash seems to be
slightly higher than the AVL, when the logic for the hash-list walk is
simpler (simply moves on to the next element, rather than needing to
also compare the address to go down the left or right side).

Both could actually be a little faster, as I wrote the logic to deal
with a full 96-bit address. If the VA space were reduced to 76 or 78
bits, then a simpler/cheaper 64-bit compare could be used.

I was initially going to use 128-bit ops, but then (since I wanted to be
able to test this in MSVC), I ended up switching to 64 bit operations
(and also hacking around the issue that Win10 is using 48-bit VA's which
were breaking the bit-field lengths I was using).

But, as-noted, I am using bit-packed structures, and:
struct AvlNode_s {
AvlNode *right; //Right Child Node
AvlNode *left; //Left Child Node
u64 pte; //Page Table Entry (Phys Addr)
byte level; //Node Depth
u64 vaddr_lo; //Virtual Addr and Pivot
u64 vaddr_hi; //Virtual Addr and Pivot
};

Would exceed the current 32-byte size limit.

The Chain-Hash Entry would be more like:
struct HashNode_s {
HashNode *next; //Next entry in Hash
u64 pte; //Page Table Entry (Phys Addr)
u64 vaddr_lo; //Virtual Addr and Pivot
u64 vaddr_hi; //Virtual Addr and Pivot
};

This isn't too far off from how it works already...

Hash-list lookup, expressed this way, would be effectively:
cur=pagehash[hidx];
while(cur)
{
if( (vaddr_hi==cur->vaddr_hi) &&
(vaddr_lo==cur->vaddr_lo))
return(cur->pte);
cur=cur->next;
}

> I am just in the process of getting a hash table to work. It is only 3.5x as
> many block rams as the TLB was. Uses a 256-bit wide port on the cpu side
> for loading and storing and a 2048-bit wide port on the memory side to
> allow an entire page group to be read in a single cycle. It has the same
> performance as a cache. But the block RAM is dedicated in the BIU, bus
> interface unit, so it would not work with a multi-core cpu. Keeping the
> RAM coherent between cores would be a challenge.

OK.

As noted, I am using a software managed TLB, where by extension the page
management structures are mostly written in C (with some bits written in
ASM).

....

On 3/19/2022 12:06 PM, BGB wrote:
> On 3/19/2022 8:26 AM, robf...@gmail.com wrote:
>> On Friday, March 18, 2022 at 10:13:22 PM UTC-4, BGB wrote:
>>> On 3/18/2022 5:53 PM, MitchAlsup wrote:
>>>> On Friday, March 18, 2022 at 5:37:57 PM UTC-5, BGB wrote:
>>>>> On 3/18/2022 4:51 AM, a...@littlepinkcloud.invalid wrote:
>>>>>> BGB <cr8...@gmail.com> wrote:
>>>>>>>
>>>>>>> I am not sure whether "in general" a chain-hash or B-Tree would be
>>>>>>> better for a large sparse address space, would need to model this.
>>>>>>
>>>>>> Or perhaps a hybrid: do you know about Phil Bagwell's Ideal Hash
>>>>>> Trees? They're great for searching, high density, but the cost of
>>>>>> updating may be too high for your application. They also depend
>>>>>> critically on a fast POPCOUNT instruction. But even if they don't
>>>>>> work
>>>>>> for your application, you might find some inspiration here.
>>>>>>
>>>>>> https://lampwww.epfl.ch/papers/idealhashtrees.pdf
>>>>>>
>>>>> It is possible, though I don't have a direct analog of this
>>>>> instruction.
>>>>>
>>>>>
>>>>> I have yet to evaluate performance tradeoffs, but thus far the AVL
>>>>> trees
>>>>> appear to be the clear winner in terms of memory overhead (for some
>>>>> simple synthetic tests) among the options I have tested thus far.
>>>>>
>>>>>
>>>>> So, for example, 256x 1MB at random addresses:
>>>>> 3-level page table: 8MB
>>>>> 8-level page table: 33MB
>>>>> AVL Tree: 512K
>>>>> Hybrid AVL (Last Level is Page Table): 4MB
>>>>>
>>>>> Current suspicion is that an AVL tree walk will be significantly
>>>>> slower
>>>>> than a page-table walk.
>>>> <
>>>> At 1 memory ref per level and 1-bit of VA per level, you can be your
>>>> bottom
>>>> dollar it would be slow. 51-level table when application is "really
>>>> big". When
>>>> application is the sizeof "cat" you would only be making 3-accesses
>>>> per walk.
>>>> <
>>>> With 1MB sized application and 4K pages, 8-level AVL walk, but the
>>>> size of the
>>>> page tables is about 2 pages. With level skipping conventional page
>>>> tables
>>>> the number of pages will be about 5. With level-skipping
>>>> sized-super-pages
>>>> the size of the translation table is about 1 page.
>>>> <
>>> In this case, it is more about trying to conserve memory than making it
>>> fast. Aggressive ASLR would do bad things to page-table size.
>>>
>>>
>>> In ongoing tests, direct page table is fastest by a significant margin.
>>>
>>> AVL vs Hash seems to be break-even ~ 384MB (24576 pages).
>>> Less than this, Hash is faster;
>>> More than this, AVL is faster.
>>>
>>>
>>> Both of these seem to be around 10x slower than the 3-level page table.
>>> The 8-level table is around 4x slower than the 3-level table.
>>>
>>>
>>>
>>> At this point:
>>> Hash size is 2048, So ~ 12 steps per hash chain.
>>> Log2 is ~ 14.6 ...
>>>
>>> This is slightly curious though as I would have expected the chain-hash
>>> walk to be slightly faster. Either way, seems to follow the (expected)
>>> pattern that whichever results in the shorter path length wins.
>>>
>>>
>>> The "hybrid" strategy is around twice as fast as the pure AVL, or around
>>> 5x slower than the 3-level page table.
>>>
>>> The hybrid strategy benefits considerably if one does a smaller number
>>> of larger allocations (whereas neither Hash nor AVL gain much here).
>>>
>>>
>>> Both the AVL Tree and Chain Hash seem to end up taking approximately the
>>> same amount of memory in this case.
>>>
>>>
>>> It also seems that the time is directly proportional to the number of
>>> steps needed to get to the target.
>>>
>>>
>>>
>>> Granted, ended up "cheesing it" for the AVL rebalancing, as I didn't
>>> implement the full set of node rotations (2 out of 4), which seems to
>>> result in the rebalancing getting "stuck" in situations where it tries
>>> in vain to endlessly rotate the same nodes (and getting stuck in an
>>> infinite loop).
>>>
>>> The cheese strategy being to keep a counter, and if the rebalancing
>>> takes too many steps, it gives up and stops rotating the nodes.
>>>
>>>
>>> Could try implementing a B-Tree, but at this point I am not super
>>> optimistic about it...
>>>
>>>
>>> Some of this also opens up the possibility of a Radix-8 or Radix-16
>>> table, which functions (in premise) similar to a conventional page
>>> table, except that each directory only has 8 or 16 entries.
>>>
>>> Though, a Radix-16 table would need 24 steps to resolve a 96-bit
>>> address, which implies that (based on the currently seen pattern) this
>>> would likely be slower than the AVL tree.
>>>
>>> ...
>>
>>> At this point:
>>> Hash size is 2048, So ~ 12 steps per hash chain.
>>> Log2 is ~ 14.6 ...
>>
>> That does not sound right. A decent hash usually averages 1.2 steps.
>> Decimal in the wrong place?
>
> 24576 pages, with a 2048-entry chain hash: 24576/2048 = 12.
> Both theoretical estimates and measured values appear to roughly agree
> here.
>
> One could make the starting hash bigger, which would reduce this, say:
> 24576 pages, with a 4096-entry chain hash: 24576/4096 = 6.
>
> So, one goes through the first stage hash, and then it becomes a linked
> list walk. The size of the first hash working as constant division
> factor for the average linked-list length.
>
>
> This was the measured "break-even" point (according to benchmarks on
> x86-64). A smaller number of pages favors the hash, a larger number
> favors AVL.
>
>
>
> A direct hash would give 1 or 2 steps, however, a direct hash could not
> be expanded linearly (resizing a direct hash requires rehashing
> everything in the hash table).

Rehashing need not be all encompassing.

The scheme I've used has a starting hash table of some smallish size. If
that fills for a trigger level, I create a new empty table twice (or
some factor) the size, linked to the old table. Searches start in the
new table, and of course miss and then look in the old table, whence
hits move the entry to the new table, to the position that was just
found to be empty so no recalculation of the hash is needed. Soon all
the hotties are in the new table, so the amortized cost is close to one
probe.

Rinse repeat. When the chain of tables gets too long (another trigger) a
background process walks the oldest table, touching all remaining live
entries and hence hoisting them to a newer table. The oldest table is
then delinked. While somewhat sensitive to the distribution of (and
definition of) liveness, three tables seem to be a good chain length in
practice.

Because both new table creation and old table destruction are triggered
background events, there is no global-halt-and-sweep as would be
required for a total rehash. And the mean probe depth is close to one
because all the hot references are on top.

MitchAlsup wrote:
> On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>>> <
>>> Page Fault gets attached to thread number (which accesses the faulting IP)
>>> ....................gets the faulting instruction-specifier in R1
>> I assume this is the instruction pointer.
> <
> It is the first 32-bits of the instruction itself. This contains everything but the
> constants.

If it faults during instruction fetch then this instruction specifier
buffer could be empty or partially filled.

It absolutely needs the address of the start of the faulting instruction.
Structured exception handlers. Debugger watch points.
These can't function without it.

You can provide this partial instruction bits in addition to the standard
exception details. Though as I point out below I don't think anyone
will need this if the page fault syndrome bits are provided.

> <
>>> ....................gets the faulting virtual address in R2
>>> ....................gets the address of fault generating PTE/PTP in R3
>> Passing the physical address of the faulting PTE to the page fault
>> handler doesn't harm anything but it doesn't really help.
>> Though I've not seen a page fault exception frame the does this.
>>
>> This misses the critical page fault reason info. The page fault handler
>> needs to know what the thread was attempting to do when it triggered
>> the fault. Looking at x86 that is a set of bit flags indicating:
>>
>> P = Caused by Not-Present PTE, or other protection codes
>> R/W = Caused by Read, or caused by Write
>> U/S = Cause by User/Super mode
>> RSVD = Reserved bit non-zero
>> I/D = access was instruction fetch, or data access
>> PK = Protection Key violation
>> SGX = SGX Software Guard Extensions violation
> <
> The given address points at the PT[PE] where the fault was detected.
> So, for example if you were trying to Read the first PT[PE] that does not have
> read permission is where you end up pointing {same for write and execute}
> <
> The instruction tells you what the instruction stream was doing.
> Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
> Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
> Inst<31..26> = 1000xx LD
> Inst<31..26> = 1001xx ST
> <
> So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
> {mal-formed instructions arrive at the Operation exception handler}
> the page fault handler can look at Instruction<31> and decide to look at
> Inst<28> or Inst<7> where 0->LD and 1->ST.
> So 3 PREDs in a row parse the instruction that caused the page fault.
> <
> But you make a good point:: I have another 32-bits in R1 I could completely
> specify what problem was detected. Let me work on that.

The fault syndrome bits should be sufficient.
I don't think anyone wants to have to reverse guesstimate what the
problem was in a page fault handler by parsing instructions.

An emulator might want to parse the faulting instructions but that
is an application specific use for the general page fault mechanism
and would take place in an application specific user mode handler.

On Saturday, March 19, 2022 at 4:19:12 PM UTC-4, EricP wrote:
> MitchAlsup wrote:
> > On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
> >> MitchAlsup wrote:
> >>> <
> >>> Page Fault gets attached to thread number (which accesses the faulting IP)
> >>> ....................gets the faulting instruction-specifier in R1
> >> I assume this is the instruction pointer.
> > <
> > It is the first 32-bits of the instruction itself. This contains everything but the
> > constants.
> If it faults during instruction fetch then this instruction specifier
> buffer could be empty or partially filled.
>
> It absolutely needs the address of the start of the faulting instruction.
> Structured exception handlers. Debugger watch points.
> These can't function without it.
>
> You can provide this partial instruction bits in addition to the standard
> exception details. Though as I point out below I don't think anyone
> will need this if the page fault syndrome bits are provided.
> > <
> >>> ....................gets the faulting virtual address in R2
> >>> ....................gets the address of fault generating PTE/PTP in R3
> >> Passing the physical address of the faulting PTE to the page fault
> >> handler doesn't harm anything but it doesn't really help.
> >> Though I've not seen a page fault exception frame the does this.
> >>
> >> This misses the critical page fault reason info. The page fault handler
> >> needs to know what the thread was attempting to do when it triggered
> >> the fault. Looking at x86 that is a set of bit flags indicating:
> >>
> >> P = Caused by Not-Present PTE, or other protection codes
> >> R/W = Caused by Read, or caused by Write
> >> U/S = Cause by User/Super mode
> >> RSVD = Reserved bit non-zero
> >> I/D = access was instruction fetch, or data access
> >> PK = Protection Key violation
> >> SGX = SGX Software Guard Extensions violation
> > <
> > The given address points at the PT[PE] where the fault was detected.
> > So, for example if you were trying to Read the first PT[PE] that does not have
> > read permission is where you end up pointing {same for write and execute}
> > <
> > The instruction tells you what the instruction stream was doing.
> > Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
> > Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
> > Inst<31..26> = 1000xx LD
> > Inst<31..26> = 1001xx ST
> > <
> > So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
> > {mal-formed instructions arrive at the Operation exception handler}
> > the page fault handler can look at Instruction<31> and decide to look at
> > Inst<28> or Inst<7> where 0->LD and 1->ST.
> > So 3 PREDs in a row parse the instruction that caused the page fault.
> > <
> > But you make a good point:: I have another 32-bits in R1 I could completely
> > specify what problem was detected. Let me work on that.
> The fault syndrome bits should be sufficient.
> I don't think anyone wants to have to reverse guesstimate what the
> problem was in a page fault handler by parsing instructions.
>
> An emulator might want to parse the faulting instructions but that
> is an application specific use for the general page fault mechanism
> and would take place in an application specific user mode handler.

For my core I have both the address of the faulting instruction stored in an exception
instruction pointer register, and the faulting address stored in a bad address register.
The cause of an exception is stored in a cause register. Maybe the cause register
does not have enough information, but it can tell if the fault was data or instruction,
or read, write, or execute violations.

Looks like its back to the drawing board for me. Planning on using compressed
pages, an idea gleaned from BGB’s posting.
I was using an inverted hash table, but had not considered memory paged out to disk.
Being able to swap out to disk means making the page table larger, meaning it will no
longer fit in block RAM. So, back to using a TLB. I was thinking of increasing the page
table size by a factor four, ¼ real memory ¾ disk storage. I gather its not a good idea
to have too large of a swap file.

The TLBE is 256 bits in size, and about 90% of the bits are used. The PTE could be
smaller, but I am having it mimic the TLBE to keep things simple.
For the hash table, hash groups are used to alleviate the need to walk chains. The hash
chain walks by a group not by a single entry. Groups contain eight entries that hashed to
the same value or are displaced, so there is seldom a need to walk more than two or
three steps.

On Tuesday, March 22, 2022 at 1:28:05 AM UTC-5, robf...@gmail.com wrote:
> On Saturday, March 19, 2022 at 4:19:12 PM UTC-4, EricP wrote:
> > MitchAlsup wrote:
> > > On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
> > >> MitchAlsup wrote:
> > >>> <
> > >>> Page Fault gets attached to thread number (which accesses the faulting IP)
> > >>> ....................gets the faulting instruction-specifier in R1
> > >> I assume this is the instruction pointer.
> > > <
> > > It is the first 32-bits of the instruction itself. This contains everything but the
> > > constants.
> > If it faults during instruction fetch then this instruction specifier
> > buffer could be empty or partially filled.
> >
> > It absolutely needs the address of the start of the faulting instruction.
> > Structured exception handlers. Debugger watch points.
> > These can't function without it.
> >
> > You can provide this partial instruction bits in addition to the standard
> > exception details. Though as I point out below I don't think anyone
> > will need this if the page fault syndrome bits are provided.
> > > <
> > >>> ....................gets the faulting virtual address in R2
> > >>> ....................gets the address of fault generating PTE/PTP in R3
> > >> Passing the physical address of the faulting PTE to the page fault
> > >> handler doesn't harm anything but it doesn't really help.
> > >> Though I've not seen a page fault exception frame the does this.
> > >>
> > >> This misses the critical page fault reason info. The page fault handler
> > >> needs to know what the thread was attempting to do when it triggered
> > >> the fault. Looking at x86 that is a set of bit flags indicating:
> > >>
> > >> P = Caused by Not-Present PTE, or other protection codes
> > >> R/W = Caused by Read, or caused by Write
> > >> U/S = Cause by User/Super mode
> > >> RSVD = Reserved bit non-zero
> > >> I/D = access was instruction fetch, or data access
> > >> PK = Protection Key violation
> > >> SGX = SGX Software Guard Extensions violation
> > > <
> > > The given address points at the PT[PE] where the fault was detected.
> > > So, for example if you were trying to Read the first PT[PE] that does not have
> > > read permission is where you end up pointing {same for write and execute}
> > > <
> > > The instruction tells you what the instruction stream was doing.
> > > Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
> > > Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
> > > Inst<31..26> = 1000xx LD
> > > Inst<31..26> = 1001xx ST
> > > <
> > > So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
> > > {mal-formed instructions arrive at the Operation exception handler}
> > > the page fault handler can look at Instruction<31> and decide to look at
> > > Inst<28> or Inst<7> where 0->LD and 1->ST.
> > > So 3 PREDs in a row parse the instruction that caused the page fault.
> > > <
> > > But you make a good point:: I have another 32-bits in R1 I could completely
> > > specify what problem was detected. Let me work on that.
> > The fault syndrome bits should be sufficient.
> > I don't think anyone wants to have to reverse guesstimate what the
> > problem was in a page fault handler by parsing instructions.
> >
> > An emulator might want to parse the faulting instructions but that
> > is an application specific use for the general page fault mechanism
> > and would take place in an application specific user mode handler.
> For my core I have both the address of the faulting instruction stored in an exception
> instruction pointer register, and the faulting address stored in a bad address register.
> The cause of an exception is stored in a cause register. Maybe the cause register
> does not have enough information, but it can tell if the fault was data or instruction,
> or read, write, or execute violations.
<
There is also the case of a poorly-formed table entry.
>
> Looks like its back to the drawing board for me. Planning on using compressed
> pages, an idea gleaned from BGB’s posting.
> I was using an inverted hash table, but had not considered memory paged out to disk.
> Being able to swap out to disk means making the page table larger, meaning it will no
> longer fit in block RAM. So, back to using a TLB. I was thinking of increasing the page
> table size by a factor four, ¼ real memory ¾ disk storage. I gather its not a good idea
> to have too large of a swap file.
>
> The TLBE is 256 bits in size, and about 90% of the bits are used. The PTE could be
> smaller, but I am having it mimic the TLBE to keep things simple.
> For the hash table, hash groups are used to alleviate the need to walk chains. The hash
> chain walks by a group not by a single entry. Groups contain eight entries that hashed to
> the same value or are displaced, so there is seldom a need to walk more than two or
> three steps.

On Tuesday, March 22, 2022 at 11:07:15 AM UTC-4, MitchAlsup wrote:
> On Tuesday, March 22, 2022 at 1:28:05 AM UTC-5, robf...@gmail.com wrote:
> > On Saturday, March 19, 2022 at 4:19:12 PM UTC-4, EricP wrote:
> > > MitchAlsup wrote:
> > > > On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
> > > >> MitchAlsup wrote:
> > > >>> <
> > > >>> Page Fault gets attached to thread number (which accesses the faulting IP)
> > > >>> ....................gets the faulting instruction-specifier in R1
> > > >> I assume this is the instruction pointer.
> > > > <
> > > > It is the first 32-bits of the instruction itself. This contains everything but the
> > > > constants.
> > > If it faults during instruction fetch then this instruction specifier
> > > buffer could be empty or partially filled.
> > >
> > > It absolutely needs the address of the start of the faulting instruction.
> > > Structured exception handlers. Debugger watch points.
> > > These can't function without it.
> > >
> > > You can provide this partial instruction bits in addition to the standard
> > > exception details. Though as I point out below I don't think anyone
> > > will need this if the page fault syndrome bits are provided.
> > > > <
> > > >>> ....................gets the faulting virtual address in R2
> > > >>> ....................gets the address of fault generating PTE/PTP in R3
> > > >> Passing the physical address of the faulting PTE to the page fault
> > > >> handler doesn't harm anything but it doesn't really help.
> > > >> Though I've not seen a page fault exception frame the does this.
> > > >>
> > > >> This misses the critical page fault reason info. The page fault handler
> > > >> needs to know what the thread was attempting to do when it triggered
> > > >> the fault. Looking at x86 that is a set of bit flags indicating:
> > > >>
> > > >> P = Caused by Not-Present PTE, or other protection codes
> > > >> R/W = Caused by Read, or caused by Write
> > > >> U/S = Cause by User/Super mode
> > > >> RSVD = Reserved bit non-zero
> > > >> I/D = access was instruction fetch, or data access
> > > >> PK = Protection Key violation
> > > >> SGX = SGX Software Guard Extensions violation
> > > > <
> > > > The given address points at the PT[PE] where the fault was detected..
> > > > So, for example if you were trying to Read the first PT[PE] that does not have
> > > > read permission is where you end up pointing {same for write and execute}
> > > > <
> > > > The instruction tells you what the instruction stream was doing.
> > > > Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
> > > > Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
> > > > Inst<31..26> = 1000xx LD
> > > > Inst<31..26> = 1001xx ST
> > > > <
> > > > So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
> > > > {mal-formed instructions arrive at the Operation exception handler}
> > > > the page fault handler can look at Instruction<31> and decide to look at
> > > > Inst<28> or Inst<7> where 0->LD and 1->ST.
> > > > So 3 PREDs in a row parse the instruction that caused the page fault.
> > > > <
> > > > But you make a good point:: I have another 32-bits in R1 I could completely
> > > > specify what problem was detected. Let me work on that.
> > > The fault syndrome bits should be sufficient.
> > > I don't think anyone wants to have to reverse guesstimate what the
> > > problem was in a page fault handler by parsing instructions.
> > >
> > > An emulator might want to parse the faulting instructions but that
> > > is an application specific use for the general page fault mechanism
> > > and would take place in an application specific user mode handler.
> > For my core I have both the address of the faulting instruction stored in an exception
> > instruction pointer register, and the faulting address stored in a bad address register.
> > The cause of an exception is stored in a cause register. Maybe the cause register
> > does not have enough information, but it can tell if the fault was data or instruction,
> > or read, write, or execute violations.
> <
> There is also the case of a poorly-formed table entry.
> >
> > Looks like its back to the drawing board for me. Planning on using compressed
> > pages, an idea gleaned from BGB’s posting.
> > I was using an inverted hash table, but had not considered memory paged out to disk.
> > Being able to swap out to disk means making the page table larger, meaning it will no
> > longer fit in block RAM. So, back to using a TLB. I was thinking of increasing the page
> > table size by a factor four, ¼ real memory ¾ disk storage. I gather its not a good idea
> > to have too large of a swap file.
> >
> > The TLBE is 256 bits in size, and about 90% of the bits are used. The PTE could be
> > smaller, but I am having it mimic the TLBE to keep things simple.
> > For the hash table, hash groups are used to alleviate the need to walk chains. The hash
> > chain walks by a group not by a single entry. Groups contain eight entries that hashed to
> > the same value or are displaced, so there is seldom a need to walk more than two or
> > three steps.

There are only a couple of things I could think of for poorly formed table entries. If the
physical address is not a legal value, or if the page mask begin is greater than the page
mask end. Otherwise, the remaining fields could have just about any value. If the physical
address is not legal a PMA exception will occur when the address is mapped. If the page
mask begin is greater than the end, then there will be no access to the page resulting in
read, write, or execute violations. I suppose the cause code could be expanded to add
syndrome bits. They may be useful for other units too.

I have the page compression indicators covering a 4kB block sub-page range. While the
page mask begin, end divides the page into 1kB blocks. It may be better to cover the
same range with both fields. 4kB blocks might be used to emulate an older system.
The first half of the PTE is mainly the translation info. The second half is access rights,
key and compression indicators. The second half of the PTE is loaded from a per-page
page management table. It is info that needs to be in the TLBE so the PTE is just used to
cache the information. The second half of the PTE could be stuffed with other information
for software use until the access rights info is made valid.

I am assuming the PPN field can be used to store the page-file swap address when the
page is not resident in memory.

On 3/22/2022 10:59 AM, robf...@gmail.com wrote:
> On Tuesday, March 22, 2022 at 11:07:15 AM UTC-4, MitchAlsup wrote:
>> On Tuesday, March 22, 2022 at 1:28:05 AM UTC-5, robf...@gmail.com wrote:
>>> On Saturday, March 19, 2022 at 4:19:12 PM UTC-4, EricP wrote:
>>>> MitchAlsup wrote:
>>>>> On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
>>>>>> MitchAlsup wrote:
>>>>>>> <
>>>>>>> Page Fault gets attached to thread number (which accesses the faulting IP)
>>>>>>> ....................gets the faulting instruction-specifier in R1
>>>>>> I assume this is the instruction pointer.
>>>>> <
>>>>> It is the first 32-bits of the instruction itself. This contains everything but the
>>>>> constants.
>>>> If it faults during instruction fetch then this instruction specifier
>>>> buffer could be empty or partially filled.
>>>>
>>>> It absolutely needs the address of the start of the faulting instruction.
>>>> Structured exception handlers. Debugger watch points.
>>>> These can't function without it.
>>>>
>>>> You can provide this partial instruction bits in addition to the standard
>>>> exception details. Though as I point out below I don't think anyone
>>>> will need this if the page fault syndrome bits are provided.
>>>>> <
>>>>>>> ....................gets the faulting virtual address in R2
>>>>>>> ....................gets the address of fault generating PTE/PTP in R3
>>>>>> Passing the physical address of the faulting PTE to the page fault
>>>>>> handler doesn't harm anything but it doesn't really help.
>>>>>> Though I've not seen a page fault exception frame the does this.
>>>>>>
>>>>>> This misses the critical page fault reason info. The page fault handler
>>>>>> needs to know what the thread was attempting to do when it triggered
>>>>>> the fault. Looking at x86 that is a set of bit flags indicating:
>>>>>>
>>>>>> P = Caused by Not-Present PTE, or other protection codes
>>>>>> R/W = Caused by Read, or caused by Write
>>>>>> U/S = Cause by User/Super mode
>>>>>> RSVD = Reserved bit non-zero
>>>>>> I/D = access was instruction fetch, or data access
>>>>>> PK = Protection Key violation
>>>>>> SGX = SGX Software Guard Extensions violation
>>>>> <
>>>>> The given address points at the PT[PE] where the fault was detected.
>>>>> So, for example if you were trying to Read the first PT[PE] that does not have
>>>>> read permission is where you end up pointing {same for write and execute}
>>>>> <
>>>>> The instruction tells you what the instruction stream was doing.
>>>>> Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
>>>>> Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
>>>>> Inst<31..26> = 1000xx LD
>>>>> Inst<31..26> = 1001xx ST
>>>>> <
>>>>> So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
>>>>> {mal-formed instructions arrive at the Operation exception handler}
>>>>> the page fault handler can look at Instruction<31> and decide to look at
>>>>> Inst<28> or Inst<7> where 0->LD and 1->ST.
>>>>> So 3 PREDs in a row parse the instruction that caused the page fault.
>>>>> <
>>>>> But you make a good point:: I have another 32-bits in R1 I could completely
>>>>> specify what problem was detected. Let me work on that.
>>>> The fault syndrome bits should be sufficient.
>>>> I don't think anyone wants to have to reverse guesstimate what the
>>>> problem was in a page fault handler by parsing instructions.
>>>>
>>>> An emulator might want to parse the faulting instructions but that
>>>> is an application specific use for the general page fault mechanism
>>>> and would take place in an application specific user mode handler.
>>> For my core I have both the address of the faulting instruction stored in an exception
>>> instruction pointer register, and the faulting address stored in a bad address register.
>>> The cause of an exception is stored in a cause register. Maybe the cause register
>>> does not have enough information, but it can tell if the fault was data or instruction,
>>> or read, write, or execute violations.
>> <
>> There is also the case of a poorly-formed table entry.
>>>
>>> Looks like its back to the drawing board for me. Planning on using compressed
>>> pages, an idea gleaned from BGB’s posting.
>>> I was using an inverted hash table, but had not considered memory paged out to disk.
>>> Being able to swap out to disk means making the page table larger, meaning it will no
>>> longer fit in block RAM. So, back to using a TLB. I was thinking of increasing the page
>>> table size by a factor four, ¼ real memory ¾ disk storage. I gather its not a good idea
>>> to have too large of a swap file.
>>>

I think the size of a swap file is a matter of interpretation.

In current tests, sizes are:
RAM = 128MB (set to match the Nexys A7 I am using)
SWAP = 256MB or 384MB in emulation and simulation tests.

On my SDcard, IIRC, the swapfile was set up as 2GB (and I didn't
originally think it would take this long to before trying to get this
stuff working).

I am not assuming any particular limit at the moment, apart from the 4GB
size limit implied by FAT32 (at present, this would be 256k pages).

Currently, the swap code sets up a 32MB region of RAM to be used as swap
pages, with the rest (for now) being left for either physical mapping or
direct remapping (where pages are mapped into virtual addresses, but are
not backed by swap).

I initially thought 32MB would be too limiting, but it appears that Doom
and similar can sit pretty easily in this space.

Doom doesn't really generate any swapfile traffic, but Quake uses enough
memory that does start accessing swap.

One limit for swapfile size would be the relative cost of any management
structures.

So, for example, with a 4GB swapfile, if spending 8B per page to track
page location / compression, this would be an ~ 2MB array, ...

In the current (uncompressed) page-table scheme, page management is
mostly limited to a few bitmaps and similar.

Though, this stuff still doesn't work particularly reliably as of yet
(trying to run programs from swapfile backed memory is still pretty buggy).

There is also some hackery, like needing to make sure that everything in
the FAT driver and similar is using physically mapped memory.

There are ending up being various functions for memory allocation with
various properties:
tk_malloc: Generic malloc, may use Swap
tk_malloc_usr: Usermode accessible (kernel), may use Swap
tk_malloc_wxe: Read/Write/Execute, Physically Mapped
tk_malloc_krn: Kernel-Mode memory, Physically Mapped
...

Internally, these map to a "tk_malloc_cat" function, which adds a
"category" argument describing the type of memory one wants (currently
as a "magic number" scheme).

Generally, anything allocated from "userland" (with the exception of WXE
memory) is currently assumed to use Swap.

Anything which may be accessed from an ISR needs to be physically mapped
(ISRs don't use address translation).

....

However, the program loaders still use direct-mapping for the '.text'
sections and similar (for now at least, may change this later). It is
likely though that the '.data'/'.bss' sections could be put into
swap-backed memory (in my ABI, the read-only and read/write sections are
handled independently of each other, *).

*: This is a little hacky as PE/COFF wasn't really designed to be used
this way, but either way.

Because both may access the SD card, trying to page stuff in or out from
within another IO operation is potentially catastrophic (though the
swapfile code does mostly bypass the FAT driver; it figures out the LBA
range and goes from there).

It doesn't currently deal with any fragmentation in the pagefile, it is
possible I could try to deal with this, to be decided if doing so is
worthwhile.

Would require either:
Pretranslating and caching the FAT cluster chains;
Hacking into the FAT FS driver internals;
Feeding swapfile operations through normal filesystem IO interfaces.

On Tuesday, March 22, 2022 at 4:50:14 PM UTC-4, BGB wrote:
> On 3/22/2022 10:59 AM, robf...@gmail.com wrote:
> > On Tuesday, March 22, 2022 at 11:07:15 AM UTC-4, MitchAlsup wrote:
> >> On Tuesday, March 22, 2022 at 1:28:05 AM UTC-5, robf...@gmail.com wrote:
> >>> On Saturday, March 19, 2022 at 4:19:12 PM UTC-4, EricP wrote:
> >>>> MitchAlsup wrote:
> >>>>> On Friday, March 18, 2022 at 11:08:08 AM UTC-5, EricP wrote:
> >>>>>> MitchAlsup wrote:
> >>>>>>> <
> >>>>>>> Page Fault gets attached to thread number (which accesses the faulting IP)
> >>>>>>> ....................gets the faulting instruction-specifier in R1
> >>>>>> I assume this is the instruction pointer.
> >>>>> <
> >>>>> It is the first 32-bits of the instruction itself. This contains everything but the
> >>>>> constants.
> >>>> If it faults during instruction fetch then this instruction specifier
> >>>> buffer could be empty or partially filled.
> >>>>
> >>>> It absolutely needs the address of the start of the faulting instruction.
> >>>> Structured exception handlers. Debugger watch points.
> >>>> These can't function without it.
> >>>>
> >>>> You can provide this partial instruction bits in addition to the standard
> >>>> exception details. Though as I point out below I don't think anyone
> >>>> will need this if the page fault syndrome bits are provided.
> >>>>> <
> >>>>>>> ....................gets the faulting virtual address in R2
> >>>>>>> ....................gets the address of fault generating PTE/PTP in R3
> >>>>>> Passing the physical address of the faulting PTE to the page fault
> >>>>>> handler doesn't harm anything but it doesn't really help.
> >>>>>> Though I've not seen a page fault exception frame the does this.
> >>>>>>
> >>>>>> This misses the critical page fault reason info. The page fault handler
> >>>>>> needs to know what the thread was attempting to do when it triggered
> >>>>>> the fault. Looking at x86 that is a set of bit flags indicating:
> >>>>>>
> >>>>>> P = Caused by Not-Present PTE, or other protection codes
> >>>>>> R/W = Caused by Read, or caused by Write
> >>>>>> U/S = Cause by User/Super mode
> >>>>>> RSVD = Reserved bit non-zero
> >>>>>> I/D = access was instruction fetch, or data access
> >>>>>> PK = Protection Key violation
> >>>>>> SGX = SGX Software Guard Extensions violation
> >>>>> <
> >>>>> The given address points at the PT[PE] where the fault was detected..
> >>>>> So, for example if you were trying to Read the first PT[PE] that does not have
> >>>>> read permission is where you end up pointing {same for write and execute}
> >>>>> <
> >>>>> The instruction tells you what the instruction stream was doing.
> >>>>> Inst<31..26> = 001001 & Inst<10..5> = 0000xx -> LD
> >>>>> Inst<31..26> = 001001 & Inst<10..5> = 00x1xx -> ST
> >>>>> Inst<31..26> = 1000xx LD
> >>>>> Inst<31..26> = 1001xx ST
> >>>>> <
> >>>>> So, there is a clever trick, Because My 66000 detects all mal-formed instructions,
> >>>>> {mal-formed instructions arrive at the Operation exception handler}
> >>>>> the page fault handler can look at Instruction<31> and decide to look at
> >>>>> Inst<28> or Inst<7> where 0->LD and 1->ST.
> >>>>> So 3 PREDs in a row parse the instruction that caused the page fault.
> >>>>> <
> >>>>> But you make a good point:: I have another 32-bits in R1 I could completely
> >>>>> specify what problem was detected. Let me work on that.
> >>>> The fault syndrome bits should be sufficient.
> >>>> I don't think anyone wants to have to reverse guesstimate what the
> >>>> problem was in a page fault handler by parsing instructions.
> >>>>
> >>>> An emulator might want to parse the faulting instructions but that
> >>>> is an application specific use for the general page fault mechanism
> >>>> and would take place in an application specific user mode handler.
> >>> For my core I have both the address of the faulting instruction stored in an exception
> >>> instruction pointer register, and the faulting address stored in a bad address register.
> >>> The cause of an exception is stored in a cause register. Maybe the cause register
> >>> does not have enough information, but it can tell if the fault was data or instruction,
> >>> or read, write, or execute violations.
> >> <
> >> There is also the case of a poorly-formed table entry.
> >>>
> >>> Looks like its back to the drawing board for me. Planning on using compressed
> >>> pages, an idea gleaned from BGB’s posting.
> >>> I was using an inverted hash table, but had not considered memory paged out to disk.
> >>> Being able to swap out to disk means making the page table larger, meaning it will no
> >>> longer fit in block RAM. So, back to using a TLB. I was thinking of increasing the page
> >>> table size by a factor four, ¼ real memory ¾ disk storage. I gather its not a good idea
> >>> to have too large of a swap file.
> >>>
> I think the size of a swap file is a matter of interpretation.
>
> In current tests, sizes are:
> RAM = 128MB (set to match the Nexys A7 I am using)
> SWAP = 256MB or 384MB in emulation and simulation tests.
>
>
> On my SDcard, IIRC, the swapfile was set up as 2GB (and I didn't
> originally think it would take this long to before trying to get this
> stuff working).
>
> I am not assuming any particular limit at the moment, apart from the 4GB
> size limit implied by FAT32 (at present, this would be 256k pages).
>
>
> Currently, the swap code sets up a 32MB region of RAM to be used as swap
> pages, with the rest (for now) being left for either physical mapping or
> direct remapping (where pages are mapped into virtual addresses, but are
> not backed by swap).
>
> I initially thought 32MB would be too limiting, but it appears that Doom
> and similar can sit pretty easily in this space.
>
> Doom doesn't really generate any swapfile traffic, but Quake uses enough
> memory that does start accessing swap.
>
> One limit for swapfile size would be the relative cost of any management
> structures.
>
> So, for example, with a 4GB swapfile, if spending 8B per page to track
> page location / compression, this would be an ~ 2MB array, ...
>
> In the current (uncompressed) page-table scheme, page management is
> mostly limited to a few bitmaps and similar.
>
>
>
> Though, this stuff still doesn't work particularly reliably as of yet
> (trying to run programs from swapfile backed memory is still pretty buggy).
>
> There is also some hackery, like needing to make sure that everything in
> the FAT driver and similar is using physically mapped memory.
>
> There are ending up being various functions for memory allocation with
> various properties:
> tk_malloc: Generic malloc, may use Swap
> tk_malloc_usr: Usermode accessible (kernel), may use Swap
> tk_malloc_wxe: Read/Write/Execute, Physically Mapped
> tk_malloc_krn: Kernel-Mode memory, Physically Mapped
> ...
>
> Internally, these map to a "tk_malloc_cat" function, which adds a
> "category" argument describing the type of memory one wants (currently
> as a "magic number" scheme).
>
>
> Generally, anything allocated from "userland" (with the exception of WXE
> memory) is currently assumed to use Swap.
>
> Anything which may be accessed from an ISR needs to be physically mapped
> (ISRs don't use address translation).
>
> ...
>
>
>
> However, the program loaders still use direct-mapping for the '.text'
> sections and similar (for now at least, may change this later). It is
> likely though that the '.data'/'.bss' sections could be put into
> swap-backed memory (in my ABI, the read-only and read/write sections are
> handled independently of each other, *).
>
> *: This is a little hacky as PE/COFF wasn't really designed to be used
> this way, but either way.
>
>
>
> Because both may access the SD card, trying to page stuff in or out from
> within another IO operation is potentially catastrophic (though the
> swapfile code does mostly bypass the FAT driver; it figures out the LBA
> range and goes from there).
>
> It doesn't currently deal with any fragmentation in the pagefile, it is
> possible I could try to deal with this, to be decided if doing so is
> worthwhile.
>
> Would require either:
> Pretranslating and caching the FAT cluster chains;
> Hacking into the FAT FS driver internals;
> Feeding swapfile operations through normal filesystem IO interfaces.
>
> Sending swapfile stuff through the filesystem driver is undesirable, for
> various reasons. For the time being, it is easier to require an
> unfragmented swapfile (which, granted, does require some special care
> when setting up the SDcard).
>
> Would have almost gone the Linux route of requiring a swap partition,
> except I am using Windows and there is no good way to set this up short
> of doing it on a Linux machine, so using a file was the easier option.
>
>
>
> I am at the moment again torn between wanting to post the code to GitHub
> (since it has been a few weeks), and not wanting to post the code when
> stuff is still obviously buggy or broken.
>
>
> I am left to wonder if all this stuff is usually so much of a PITA to
> debug for everyone else, or if I just kinda suck at it...
> >>> The TLBE is 256 bits in size, and about 90% of the bits are used. The PTE could be
> >>> smaller, but I am having it mimic the TLBE to keep things simple.
> >>> For the hash table, hash groups are used to alleviate the need to walk chains. The hash
> >>> chain walks by a group not by a single entry. Groups contain eight entries that hashed to
> >>> the same value or are displaced, so there is seldom a need to walk more than two or
> >>> three steps.
> >
> > There are only a couple of things I could think of for poorly formed table entries. If the
> > physical address is not a legal value, or if the page mask begin is greater than the page
> > mask end. Otherwise, the remaining fields could have just about any value. If the physical
> > address is not legal a PMA exception will occur when the address is mapped. If the page
> > mask begin is greater than the end, then there will be no access to the page resulting in
> > read, write, or execute violations. I suppose the cause code could be expanded to add
> > syndrome bits. They may be useful for other units too.
> >
> > I have the page compression indicators covering a 4kB block sub-page range. While the
> > page mask begin, end divides the page into 1kB blocks. It may be better to cover the
> > same range with both fields. 4kB blocks might be used to emulate an older system.
> > The first half of the PTE is mainly the translation info. The second half is access rights,
> > key and compression indicators. The second half of the PTE is loaded from a per-page
> > page management table. It is info that needs to be in the TLBE so the PTE is just used to
> > cache the information. The second half of the PTE could be stuffed with other information
> > for software use until the access rights info is made valid.
> >
> So, considering something simplistic like "skip zeroed parts of a
> not-entirely-zero" page or something?...
>
>
> I guess this is possible, vs what I was considering of having one of 3
> options:
> Zeroed / Skipped;
> Stored;
> LZ Compressed.
>
> At present (with an uncompressed pagefile), only the Zeroed and Stored
> states exist.
>
>
> Though, I still have a few concerns with my idea:
> Making LZ compression sufficiently fast is still an issue;
> Doing a chunk buffer turns a large number of small stalls into a smaller
> number of large stalls.
>
> It will probably be painfully obvious if the whole system stalls for
> several seconds at a time to write several MB of compressed pagefile
> data to the SD card.
>
>
> Though, looking stuff up, it appears I may not need to write the data
> all at once, rather it may be sufficient to (merely) write to the data
> in a roughly sequential order.
>
> This would imply abandoning the 4MB chunking idea, and instead treating
> the swap as a circular log. This would, however, require some way to
> relocate or skip over existing pages if they are "still live".
>
> I could probably manage this with a cell bitmap (probably with 512B or
> 1K cells), effectively treating the pagefile like a large bitmap-managed
> heap. This could work OK, but its effectiveness (outside of an explicit
> "compactor" mechanism) would depend highly on fragmentation.
>
>
> Assuming 1K cells with a 2GB pagefile, would need 256K at 1b/cell.
> Would need ~ 28b to encode the size and location of a compressed page.
> Assuming there are 128k pages (each 16K), with 4B overhead per page,
> this part costs 512K.
>
> Probably doable...
>
>
> Though, it is possible that (if enough pages are poorly compressible),
> that fragmentation would result in the pagefile turning into an unusable
> state with this design.
>
> Assuming a 1:1 parity between pagefile size and logical page count; this
> will likely only work OK if average compressed page size is below around
> 8K or so. The alternative being to only fill the pagefile to 50% or 75%
> capacity, such that the pagefile still works even if a majority of the
> pages are poorly compressible.
>
> But, at that point, one would be better off using an uncompressed pagefile.
>
>
> Some of my mock-up tests aren't giving as good of compression as I had
> hoped. This idea would work a lot better if pages got an average
> compression ratio of around 75% or so, but the 45%..65% I am seeing in
> my mock-up tests is likely to be borderline at best.
>
>
> From what I can find, most OS's seem to be using uncompressed pagefiles.
> > I am assuming the PPN field can be used to store the page-file swap address when the
> > page is not resident in memory.
> >
> Storing the logical pagefile page-number in non-resident pages is how I
> was doing it.
>
> Address is Virtual:
> Present==1:
> Page number maps to a physical page address;
> Present==0:
> Page Number==0: PTE is Free (PTE==0) or Reserved (PTE!=0)
> Page Number!=0: PTE points at a pagefile page
>
> ...
>
> Pagefile page 0 is currently reserved.