To-nights quandary, packing hash tables using a background process.
Tried to find info on this on the web. Anybody got any pointers? Using
a hash table to store address translations for memory management.
When there is a miss the table is searched with quadratic probing. If
it’s a real miss and no translation is present, then the first empty slot
in the hash table should be used to store the translation. As entries get removed from the table, following entries could be moved into those
empty positions to reduce search times. I think it requires keeping
track of the number of times the entry bounced before finding an
open spot. I was going to use a four-bit count to record this. The
bounce count needs to be present in the PTE. Entries that hash to the
same value are grouped together in a page table group, PTG, that
contains five PTEs.

On 3/9/2022 12:46 AM, robf...@gmail.com wrote:
> To-nights quandary, packing hash tables using a background process.
> Tried to find info on this on the web. Anybody got any pointers? Using
> a hash table to store address translations for memory management.
> When there is a miss the table is searched with quadratic probing. If
> it’s a real miss and no translation is present, then the first empty slot
> in the hash table should be used to store the translation. As entries get removed from the table, following entries could be moved into those
> empty positions to reduce search times. I think it requires keeping
> track of the number of times the entry bounced before finding an
> open spot. I was going to use a four-bit count to record this. The
> bounce count needs to be present in the PTE. Entries that hash to the
> same value are grouped together in a page table group, PTG, that
> contains five PTEs.

It is not really at all obvious what you mean by this...

But, yeah, assuming you are talking about a TLB:
In my case, it is 4 way associative, so all 4 entries get fetched from
the TLB array at the same time;
It checks for a hit;
Whichever entry hits is moved to the front of the list (with some
special cases for 96-bit addresses);
All 4 entries are written back to the TLB (in their updated order).

Currently, the index into the TLB array is address modulo, eg,
Addr[21:14]. This was because I had done some testing and found that
modulo had some useful properties when compared with an XOR hashed index.

A linear probing approach is probably not particularly likely to be
worthwhile IMO.

On Wednesday, March 9, 2022 at 3:48:43 AM UTC-5, BGB wrote:
> On 3/9/2022 12:46 AM, robf...@gmail.com wrote:
> > To-nights quandary, packing hash tables using a background process.
> > Tried to find info on this on the web. Anybody got any pointers? Using
> > a hash table to store address translations for memory management.
> > When there is a miss the table is searched with quadratic probing. If
> > it’s a real miss and no translation is present, then the first empty slot
> > in the hash table should be used to store the translation. As entries get removed from the table, following entries could be moved into those
> > empty positions to reduce search times. I think it requires keeping
> > track of the number of times the entry bounced before finding an
> > open spot. I was going to use a four-bit count to record this. The
> > bounce count needs to be present in the PTE. Entries that hash to the
> > same value are grouped together in a page table group, PTG, that
> > contains five PTEs.
> It is not really at all obvious what you mean by this...
>
> But, yeah, assuming you are talking about a TLB:
> In my case, it is 4 way associative, so all 4 entries get fetched from
> the TLB array at the same time;
> It checks for a hit;
> Whichever entry hits is moved to the front of the list (with some
> special cases for 96-bit addresses);
> All 4 entries are written back to the TLB (in their updated order).
>
>
> Currently, the index into the TLB array is address modulo, eg,
> Addr[21:14]. This was because I had done some testing and found that
> modulo had some useful properties when compared with an XOR hashed index.
>
> A linear probing approach is probably not particularly likely to be
> worthwhile IMO.

Entries in the TLB are searched in parallel for a match. The TLB uses a modulo
index. Only part of the virtual address page number is stored in the TLB since
the modulo index gives bits 12 to 21 of the virtual address. Translations are being
stored in a hash table. What I am wondering about is accelerating searches of the
hash table on a TLB miss. If entries in the hash table can be moved around so
they are closer to the initial hash position then the search time can be reduced. I
assume this could be done by a background process. I am wondering if it is
worth it to do?

This is for a hashed page table where the entries are stored in groups PTGs.. This
is borrowing a piece gleaned from the PowerPC architecture. But it could be a
hash-table in general. PowerPC I studied uses a double-hash to select two different PTGs
to search. Makes a lot of sense since translations are usually found within two or
three steps. I decided to use quadratic probing instead of a double-hash. It has the
property that PTGs are selected close by the original target, getting progressively
further away as the miss count increases. I think the idea is to try and make use of
some locality of reference.

The hashed table is searched on a TLB miss. The hashed table is organized into
groups of PTEs so that they can be searched in parallel for a translation match. If
there is one, then it is inserted into the TLB. If there is not one, then the next PTG
is searched and so on. The next PTG is selected according to quadratic probing.
Since the probe function always returns the same distance for a given miss count,
if the miss count is known then related PTGs can be found by searching backwards
or forwards. It is possible to choose a backward location in a single calculation /
table lookup. For example, if the PTE is sitting in a PTG a distance of nine away from
its ideal location, if there is an empty spot closer to the ideal location it could be
moved. This is a bit like garbage collection. I am wondering if it is worthwhile to
garbage collect the table?

If it can be guaranteed that PTGs will always fill up before another one is chosen to
store a PTE in, then searching the PTGs can be made to stop as soon as an empty
entry in a PTG is found. Otherwise, searches must continue for some time since
empty entries might be due to deletes.

robf...@gmail.com wrote:
> To-nights quandary, packing hash tables using a background process.
> Tried to find info on this on the web. Anybody got any pointers? Using
> a hash table to store address translations for memory management.
> When there is a miss the table is searched with quadratic probing. If
> it’s a real miss and no translation is present, then the first empty slot
> in the hash table should be used to store the translation. As entries get removed from the table, following entries could be moved into those
> empty positions to reduce search times. I think it requires keeping
> track of the number of times the entry bounced before finding an
> open spot. I was going to use a four-bit count to record this. The
> bounce count needs to be present in the PTE. Entries that hash to the
> same value are grouped together in a page table group, PTG, that
> contains five PTEs.

Note that operating systems such as Linux the hierarchical page table is
part of its design. To port it to Power with its hash/inverted page table
they kept the hierarchical table managed in memory as before,
and move valid PTE entries into and out of the hash table.

In effect, the hierarchical table is still the OS page table,
and the hash table is treated like a giant software managed TLB.
Software could implement, say, a FIFO mechanism to rotate a working set
of Present hierarchical PTE's through hash PTE slots,
similar to how a HW TLB might rotate through its entries.

In this arrangement, Address Space ID's (ASID) for the hash table entries
would be very important for efficiency, as without them a process switch
would require invalidating all hash table entries just like a real TLB.

On 3/9/2022 10:20 AM, EricP wrote:
> robf...@gmail.com wrote:
>> To-nights quandary, packing hash tables using a background process.
>> Tried to find info on this on the web. Anybody got any pointers? Using
>> a hash table to store address translations for memory management.
>> When there is a miss the table is searched with quadratic probing. If
>> it’s a real miss and no translation is present, then the first empty slot
>> in the hash table should be used to store the translation. As entries
>> get removed from the table, following entries could be moved into those
>> empty positions to reduce search times. I think it requires keeping
>> track of the number of times the entry bounced before finding an
>> open spot. I was going to use a four-bit count to record this. The
>> bounce count needs to be present in the PTE. Entries that hash to the
>> same value are grouped together in a page table group, PTG, that
>> contains five PTEs.
>
> Note that operating systems such as Linux the hierarchical page table is
> part of its design. To port it to Power with its hash/inverted page table
> they kept the hierarchical table managed in memory as before,
> and move valid PTE entries into and out of the hash table.
>
> In effect, the hierarchical table is still the OS page table,
> and the hash table is treated like a giant software managed TLB.
> Software could implement, say, a FIFO mechanism to rotate a working set
> of Present hierarchical PTE's through hash PTE slots,
> similar to how a HW TLB might rotate through its entries.
>
> In this arrangement, Address Space ID's (ASID) for the hash table entries
> would be very important for efficiency, as without them a process switch
> would require invalidating all hash table entries just like a real TLB.
>

OK. This gives more context for what I was confused about in my response.

In my case, I use a software managed TLB, with hierarchical page tables,
and no sort of intermediate stage representation.

TLB miss interrupt occurs, handler walks the page table, and loads the
resulting entry into the TLB. Basic design for the mechanism was
more-or-less lifted from SH-4, but with the major difference of going
from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.

Arguably, a 6-way or 8-way TLB could be better, but more expensive.

I had considered potentially using B-Trees for the upper levels (instead
of hierarchical nesting) for the 96-bit mode, mostly because as-is this
leads to a "very sparse" 8-level table, and a B-Tree could be more
compact (with more traditional nested page tables for the lower 2 or 3
levels).

Though, there are other (potentially simpler/cheaper) ways to deal with
this.

This would not really effect the hardware in my case.

On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
> On 3/9/2022 10:20 AM, EricP wrote:

> > Note that operating systems such as Linux the hierarchical page table is
> > part of its design. To port it to Power with its hash/inverted page table
> > they kept the hierarchical table managed in memory as before,
> > and move valid PTE entries into and out of the hash table.
> >
> > In effect, the hierarchical table is still the OS page table,
> > and the hash table is treated like a giant software managed TLB.
> > Software could implement, say, a FIFO mechanism to rotate a working set
> > of Present hierarchical PTE's through hash PTE slots,
> > similar to how a HW TLB might rotate through its entries.
> >
> > In this arrangement, Address Space ID's (ASID) for the hash table entries
> > would be very important for efficiency, as without them a process switch
> > would require invalidating all hash table entries just like a real TLB.
> >
Seems kind of kludgy. I am wondering why now this approach was used.

I have coded in the bus interface unit the capability to use either hashed or
hierarchical page tables. I was not so insane as to ignore the popularity of
hierarchical page tables. Can probably use both types at the same time.
Hashed tables are a better way to go for a large address
space in my opinion. They use less memory and may have faster look-ups.

> OK. This gives more context for what I was confused about in my response.
>
> In my case, I use a software managed TLB, with hierarchical page tables,
> and no sort of intermediate stage representation.
>
> TLB miss interrupt occurs, handler walks the page table, and loads the
> resulting entry into the TLB. Basic design for the mechanism was
> more-or-less lifted from SH-4, but with the major difference of going
> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
>
> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
>
>
> I had considered potentially using B-Trees for the upper levels (instead
> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
> leads to a "very sparse" 8-level table, and a B-Tree could be more
> compact (with more traditional nested page tables for the lower 2 or 3
> levels).
>
> Though, there are other (potentially simpler/cheaper) ways to deal with
> this.
>
> This would not really effect the hardware in my case.

Page tables are walked via hardware for Thor. Software only gets involved on a
page fault. While software managing the TLB is probably comparable in
performance and more flexible than hardware, TLB updates with hardware
walking are almost invisible to software.

The TLB can be updated via software, its almost possible then to use a software
managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
then maybe things could have the option of software management.

I get the feeling there are too many choices available in Thor. Maybe a configuration
utility would be better than building in everything.

Wondering what entity to place share counts, access keys, and privilege levels in. I
had these in the PTE but took them out. There is only one set required for each page
of memory.

On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
>> On 3/9/2022 10:20 AM, EricP wrote:
>
>>> Note that operating systems such as Linux the hierarchical page table is
>>> part of its design. To port it to Power with its hash/inverted page table
>>> they kept the hierarchical table managed in memory as before,
>>> and move valid PTE entries into and out of the hash table.
>>>
>>> In effect, the hierarchical table is still the OS page table,
>>> and the hash table is treated like a giant software managed TLB.
>>> Software could implement, say, a FIFO mechanism to rotate a working set
>>> of Present hierarchical PTE's through hash PTE slots,
>>> similar to how a HW TLB might rotate through its entries.
>>>
>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
>>> would be very important for efficiency, as without them a process switch
>>> would require invalidating all hash table entries just like a real TLB.
>>>
> Seems kind of kludgy. I am wondering why now this approach was used.
>
> I have coded in the bus interface unit the capability to use either hashed or
> hierarchical page tables. I was not so insane as to ignore the popularity of
> hierarchical page tables. Can probably use both types at the same time.
> Hashed tables are a better way to go for a large address
> space in my opinion. They use less memory and may have faster look-ups.
>

Hashed tables could also make sense as an alternative to B-Trees.

A B-Tree lookup is likely to be relatively complicated and expensive if
compared to a hash lookup.

It is possible that I could also combine a hashed top-level with
2-levels of nested page table (optionally collapsing down the upper 6
levels into a single page).

>
>> OK. This gives more context for what I was confused about in my response.
>>
>> In my case, I use a software managed TLB, with hierarchical page tables,
>> and no sort of intermediate stage representation.
>>
>> TLB miss interrupt occurs, handler walks the page table, and loads the
>> resulting entry into the TLB. Basic design for the mechanism was
>> more-or-less lifted from SH-4, but with the major difference of going
>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
>>
>> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
>>
>>
>> I had considered potentially using B-Trees for the upper levels (instead
>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
>> leads to a "very sparse" 8-level table, and a B-Tree could be more
>> compact (with more traditional nested page tables for the lower 2 or 3
>> levels).
>>
>> Though, there are other (potentially simpler/cheaper) ways to deal with
>> this.
>>
>> This would not really effect the hardware in my case.
>
> Page tables are walked via hardware for Thor. Software only gets involved on a
> page fault. While software managing the TLB is probably comparable in
> performance and more flexible than hardware, TLB updates with hardware
> walking are almost invisible to software.
>

This was one annoyance with BJX2 with the use of software managed TLB:
Getting the software TLB miss interrupts stable was a major source of
annoyance, as there were a whole lot of "little things" that can go
wrong in these mechanisms.

The L1 caches needing to be able to stop what they are doing, then
quietly transfer control to an ISR, then resume normal operation without
any adverse side effects, was a bit of a pain to debug.

Some of the cases were infrequent, so one might to get Doom or Quake
launched (in a simulation) before the crash happens, where firing these
up inside a Verilog simulation is not exactly a fast process (the time
issue is also a major reason why I am using LZ compressed binaries and
WADs).

As noted, the MMU is temporarily disabled within ISRs, partly because
there is no way for an ISR to deal with a TLB miss (unlike some CPU
architectures, ISRs are not re-entrant in my case).

Similarly, the TLB miss handler would have to resolve page-fault
scenarios (for virtual memory), without access to the main filesystem
driver (it has to bypass the driver and access the SDCard directly), but
does also mean that a page fault (to virtual memory) during some other
SDcard IO request would be "potentially fatal".

....

Nevermind whether or not it makes sense to put a pagefile on an SDcard,
there is nowhere else to put it in this case.

What to do with a page-fault to an unmapped address (eg: not backed to
the page file) is currently an unresolved issue, but this is more a
software thing than a hardware thing (in a real OS, would probably
terminate the process or similar here; for the time being, the only real
solution is to trigger a breakpoint).

I may need to consider going and adding preemptive multitasking, as it
looks like most "real OS" stuff would depend on this (cooperative
multitasking doesn't scale particularly well, or leave any real good
solution for "OK, this program has gone into an infinite loop or
crashed", which basically leaves no real solution otherwise).

The debugging was getting bad enough that I almost started to debate
whether it would be worthwhile to add hardware page walking and not have
to deal with this as much (but would still need a Page Fault handler, so
it is not entirely avoidable).

Sorta spent most of February beating on trying to debug stuff related to
the L1 Caches and their interaction with the TLB Miss ISR, partly as
"poking at something" in the L1 D$ set off an unholy bees nest of bugs.

Likewise, much of my past debugging effort here was more focused on
"quick and dirty" fixes which typically don't really resolve the
underlying issues; but, trying to figure out "why" something is going
wrong is often a lot harder than adding "make it work" hacks (and then
notice the bug hasn't gone away, it has merely moved to a new location).

I still can't say (with much confidence) that the TLB is now stable, but
in my testing at the moment, it appears to work.

Though, this debugging effort wasn't helped with Verilator also having
the annoying behavior that adding and removing $display statements can
sometimes change the behavior of the logic...

> The TLB can be updated via software, its almost possible then to use a software
> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
> then maybe things could have the option of software management.
>

Could be.

In my case, TLB miss triggers an interrupt, and the ISR deals with it.

In the ISR, there is a 'TEA' register that holds the address of whatever
caused the interrupt (target address for TLB miss), and an 'EXSR'
register where the low bits encode which interrupt had occurred (as a
16-bit number divided into multiple bit fields).

> I get the feeling there are too many choices available in Thor. Maybe a configuration
> utility would be better than building in everything.
>
> Wondering what entity to place share counts, access keys, and privilege levels in. I
> had these in the PTE but took them out. There is only one set required for each page
> of memory.
>

I have this stuff in the PTEs/TLBEs.

There is also an ACL Cache with an ACL Miss interrupt as well.

The software side of things isn't really developed all that well yet, as
most of the time thus far had gone more into trying to get things stable
enough that the address translation and TLB miss interrupts weren't
prone to crash stuff.

I seem to have this part stable now, so now it should be possible to
start making forward progress in this area.

On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
> > On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
> >> On 3/9/2022 10:20 AM, EricP wrote:
> >
> >>> Note that operating systems such as Linux the hierarchical page table is
> >>> part of its design. To port it to Power with its hash/inverted page table
> >>> they kept the hierarchical table managed in memory as before,
> >>> and move valid PTE entries into and out of the hash table.
> >>>
> >>> In effect, the hierarchical table is still the OS page table,
> >>> and the hash table is treated like a giant software managed TLB.
> >>> Software could implement, say, a FIFO mechanism to rotate a working set
> >>> of Present hierarchical PTE's through hash PTE slots,
> >>> similar to how a HW TLB might rotate through its entries.
> >>>
> >>> In this arrangement, Address Space ID's (ASID) for the hash table entries
> >>> would be very important for efficiency, as without them a process switch
> >>> would require invalidating all hash table entries just like a real TLB.
> >>>
> > Seems kind of kludgy. I am wondering why now this approach was used.
> >
> > I have coded in the bus interface unit the capability to use either hashed or
> > hierarchical page tables. I was not so insane as to ignore the popularity of
> > hierarchical page tables. Can probably use both types at the same time.
> > Hashed tables are a better way to go for a large address
> > space in my opinion. They use less memory and may have faster look-ups.
> >
> Hashed tables could also make sense as an alternative to B-Trees.
>
> A B-Tree lookup is likely to be relatively complicated and expensive if
> compared to a hash lookup.
>
> It is possible that I could also combine a hashed top-level with
> 2-levels of nested page table (optionally collapsing down the upper 6
> levels into a single page).
> >
> >> OK. This gives more context for what I was confused about in my response.
> >>
> >> In my case, I use a software managed TLB, with hierarchical page tables,
> >> and no sort of intermediate stage representation.
> >>
> >> TLB miss interrupt occurs, handler walks the page table, and loads the
> >> resulting entry into the TLB. Basic design for the mechanism was
> >> more-or-less lifted from SH-4, but with the major difference of going
> >> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
> >>
> >> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
> >>
> >>
> >> I had considered potentially using B-Trees for the upper levels (instead
> >> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
> >> leads to a "very sparse" 8-level table, and a B-Tree could be more
> >> compact (with more traditional nested page tables for the lower 2 or 3
> >> levels).
> >>
> >> Though, there are other (potentially simpler/cheaper) ways to deal with
> >> this.
> >>
> >> This would not really effect the hardware in my case.
> >
> > Page tables are walked via hardware for Thor. Software only gets involved on a
> > page fault. While software managing the TLB is probably comparable in
> > performance and more flexible than hardware, TLB updates with hardware
> > walking are almost invisible to software.
> >
> This was one annoyance with BJX2 with the use of software managed TLB:
> Getting the software TLB miss interrupts stable was a major source of
> annoyance, as there were a whole lot of "little things" that can go
> wrong in these mechanisms.
>
> The L1 caches needing to be able to stop what they are doing, then
> quietly transfer control to an ISR, then resume normal operation without
> any adverse side effects, was a bit of a pain to debug.
>
> Some of the cases were infrequent, so one might to get Doom or Quake
> launched (in a simulation) before the crash happens, where firing these
> up inside a Verilog simulation is not exactly a fast process (the time
> issue is also a major reason why I am using LZ compressed binaries and
> WADs).
>
>
> As noted, the MMU is temporarily disabled within ISRs, partly because
> there is no way for an ISR to deal with a TLB miss (unlike some CPU
> architectures, ISRs are not re-entrant in my case).
>
>
> Similarly, the TLB miss handler would have to resolve page-fault
> scenarios (for virtual memory), without access to the main filesystem
> driver (it has to bypass the driver and access the SDCard directly), but
> does also mean that a page fault (to virtual memory) during some other
> SDcard IO request would be "potentially fatal".
>
> ...
>
> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
> there is nowhere else to put it in this case.
>
>
> What to do with a page-fault to an unmapped address (eg: not backed to
> the page file) is currently an unresolved issue, but this is more a
> software thing than a hardware thing (in a real OS, would probably
> terminate the process or similar here; for the time being, the only real
> solution is to trigger a breakpoint).
>
> I may need to consider going and adding preemptive multitasking, as it
> looks like most "real OS" stuff would depend on this (cooperative
> multitasking doesn't scale particularly well, or leave any real good
> solution for "OK, this program has gone into an infinite loop or
> crashed", which basically leaves no real solution otherwise).
>
>
>
> The debugging was getting bad enough that I almost started to debate
> whether it would be worthwhile to add hardware page walking and not have
> to deal with this as much (but would still need a Page Fault handler, so
> it is not entirely avoidable).
>
>
> Sorta spent most of February beating on trying to debug stuff related to
> the L1 Caches and their interaction with the TLB Miss ISR, partly as
> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
>
> Likewise, much of my past debugging effort here was more focused on
> "quick and dirty" fixes which typically don't really resolve the
> underlying issues; but, trying to figure out "why" something is going
> wrong is often a lot harder than adding "make it work" hacks (and then
> notice the bug hasn't gone away, it has merely moved to a new location).
>
>
> I still can't say (with much confidence) that the TLB is now stable, but
> in my testing at the moment, it appears to work.
>
> Though, this debugging effort wasn't helped with Verilator also having
> the annoying behavior that adding and removing $display statements can
> sometimes change the behavior of the logic...
> > The TLB can be updated via software, its almost possible then to use a software
> > managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
> > then maybe things could have the option of software management.
> >
> Could be.
>
> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
>
> In the ISR, there is a 'TEA' register that holds the address of whatever
> caused the interrupt (target address for TLB miss), and an 'EXSR'
> register where the low bits encode which interrupt had occurred (as a
> 16-bit number divided into multiple bit fields).
> > I get the feeling there are too many choices available in Thor. Maybe a configuration
> > utility would be better than building in everything.
> >
> > Wondering what entity to place share counts, access keys, and privilege levels in. I
> > had these in the PTE but took them out. There is only one set required for each page
> > of memory.
> >
> I have this stuff in the PTEs/TLBEs.
>
> There is also an ACL Cache with an ACL Miss interrupt as well.
>
> The software side of things isn't really developed all that well yet, as
> most of the time thus far had gone more into trying to get things stable
> enough that the address translation and TLB miss interrupts weren't
> prone to crash stuff.
>
> I seem to have this part stable now, so now it should be possible to
> start making forward progress in this area.

For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
share-counts, etc. included in it. A larger PTE would really complicate things.
The TLBE value can be loaded or stored from / to the TLB using a single
128-bit wide register. Anything wider means using a pair of registers. I could
maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
I had the thought that since there only needs to be one copy of the information it
could be stored in another entity. But this means potentially adding to the memory
access time since another table is accessed after the physical page number is
known.

On 3/10/2022 7:58 PM, robf...@gmail.com wrote:
> On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
>> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
>>> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
>>>> On 3/9/2022 10:20 AM, EricP wrote:
>>>
>>>>> Note that operating systems such as Linux the hierarchical page table is
>>>>> part of its design. To port it to Power with its hash/inverted page table
>>>>> they kept the hierarchical table managed in memory as before,
>>>>> and move valid PTE entries into and out of the hash table.
>>>>>
>>>>> In effect, the hierarchical table is still the OS page table,
>>>>> and the hash table is treated like a giant software managed TLB.
>>>>> Software could implement, say, a FIFO mechanism to rotate a working set
>>>>> of Present hierarchical PTE's through hash PTE slots,
>>>>> similar to how a HW TLB might rotate through its entries.
>>>>>
>>>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
>>>>> would be very important for efficiency, as without them a process switch
>>>>> would require invalidating all hash table entries just like a real TLB.
>>>>>
>>> Seems kind of kludgy. I am wondering why now this approach was used.
>>>
>>> I have coded in the bus interface unit the capability to use either hashed or
>>> hierarchical page tables. I was not so insane as to ignore the popularity of
>>> hierarchical page tables. Can probably use both types at the same time.
>>> Hashed tables are a better way to go for a large address
>>> space in my opinion. They use less memory and may have faster look-ups.
>>>
>> Hashed tables could also make sense as an alternative to B-Trees.
>>
>> A B-Tree lookup is likely to be relatively complicated and expensive if
>> compared to a hash lookup.
>>
>> It is possible that I could also combine a hashed top-level with
>> 2-levels of nested page table (optionally collapsing down the upper 6
>> levels into a single page).
>>>
>>>> OK. This gives more context for what I was confused about in my response.
>>>>
>>>> In my case, I use a software managed TLB, with hierarchical page tables,
>>>> and no sort of intermediate stage representation.
>>>>
>>>> TLB miss interrupt occurs, handler walks the page table, and loads the
>>>> resulting entry into the TLB. Basic design for the mechanism was
>>>> more-or-less lifted from SH-4, but with the major difference of going
>>>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
>>>>
>>>> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
>>>>
>>>>
>>>> I had considered potentially using B-Trees for the upper levels (instead
>>>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
>>>> leads to a "very sparse" 8-level table, and a B-Tree could be more
>>>> compact (with more traditional nested page tables for the lower 2 or 3
>>>> levels).
>>>>
>>>> Though, there are other (potentially simpler/cheaper) ways to deal with
>>>> this.
>>>>
>>>> This would not really effect the hardware in my case.
>>>
>>> Page tables are walked via hardware for Thor. Software only gets involved on a
>>> page fault. While software managing the TLB is probably comparable in
>>> performance and more flexible than hardware, TLB updates with hardware
>>> walking are almost invisible to software.
>>>
>> This was one annoyance with BJX2 with the use of software managed TLB:
>> Getting the software TLB miss interrupts stable was a major source of
>> annoyance, as there were a whole lot of "little things" that can go
>> wrong in these mechanisms.
>>
>> The L1 caches needing to be able to stop what they are doing, then
>> quietly transfer control to an ISR, then resume normal operation without
>> any adverse side effects, was a bit of a pain to debug.
>>
>> Some of the cases were infrequent, so one might to get Doom or Quake
>> launched (in a simulation) before the crash happens, where firing these
>> up inside a Verilog simulation is not exactly a fast process (the time
>> issue is also a major reason why I am using LZ compressed binaries and
>> WADs).
>>
>>
>> As noted, the MMU is temporarily disabled within ISRs, partly because
>> there is no way for an ISR to deal with a TLB miss (unlike some CPU
>> architectures, ISRs are not re-entrant in my case).
>>
>>
>> Similarly, the TLB miss handler would have to resolve page-fault
>> scenarios (for virtual memory), without access to the main filesystem
>> driver (it has to bypass the driver and access the SDCard directly), but
>> does also mean that a page fault (to virtual memory) during some other
>> SDcard IO request would be "potentially fatal".
>>
>> ...
>>
>> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
>> there is nowhere else to put it in this case.
>>
>>
>> What to do with a page-fault to an unmapped address (eg: not backed to
>> the page file) is currently an unresolved issue, but this is more a
>> software thing than a hardware thing (in a real OS, would probably
>> terminate the process or similar here; for the time being, the only real
>> solution is to trigger a breakpoint).
>>
>> I may need to consider going and adding preemptive multitasking, as it
>> looks like most "real OS" stuff would depend on this (cooperative
>> multitasking doesn't scale particularly well, or leave any real good
>> solution for "OK, this program has gone into an infinite loop or
>> crashed", which basically leaves no real solution otherwise).
>>
>>
>>
>> The debugging was getting bad enough that I almost started to debate
>> whether it would be worthwhile to add hardware page walking and not have
>> to deal with this as much (but would still need a Page Fault handler, so
>> it is not entirely avoidable).
>>
>>
>> Sorta spent most of February beating on trying to debug stuff related to
>> the L1 Caches and their interaction with the TLB Miss ISR, partly as
>> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
>>
>> Likewise, much of my past debugging effort here was more focused on
>> "quick and dirty" fixes which typically don't really resolve the
>> underlying issues; but, trying to figure out "why" something is going
>> wrong is often a lot harder than adding "make it work" hacks (and then
>> notice the bug hasn't gone away, it has merely moved to a new location).
>>
>>
>> I still can't say (with much confidence) that the TLB is now stable, but
>> in my testing at the moment, it appears to work.
>>
>> Though, this debugging effort wasn't helped with Verilator also having
>> the annoying behavior that adding and removing $display statements can
>> sometimes change the behavior of the logic...
>>> The TLB can be updated via software, its almost possible then to use a software
>>> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
>>> then maybe things could have the option of software management.
>>>
>> Could be.
>>
>> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
>>
>> In the ISR, there is a 'TEA' register that holds the address of whatever
>> caused the interrupt (target address for TLB miss), and an 'EXSR'
>> register where the low bits encode which interrupt had occurred (as a
>> 16-bit number divided into multiple bit fields).
>>> I get the feeling there are too many choices available in Thor. Maybe a configuration
>>> utility would be better than building in everything.
>>>
>>> Wondering what entity to place share counts, access keys, and privilege levels in. I
>>> had these in the PTE but took them out. There is only one set required for each page
>>> of memory.
>>>
>> I have this stuff in the PTEs/TLBEs.
>>
>> There is also an ACL Cache with an ACL Miss interrupt as well.
>>
>> The software side of things isn't really developed all that well yet, as
>> most of the time thus far had gone more into trying to get things stable
>> enough that the address translation and TLB miss interrupts weren't
>> prone to crash stuff.
>>
>> I seem to have this part stable now, so now it should be possible to
>> start making forward progress in this area.
>
> For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
> share-counts, etc. included in it. A larger PTE would really complicate things.
> The TLBE value can be loaded or stored from / to the TLB using a single
> 128-bit wide register. Anything wider means using a pair of registers. I could
> maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
> I had the thought that since there only needs to be one copy of the information it
> could be stored in another entity. But this means potentially adding to the memory
> access time since another table is accessed after the physical page number is
> known.
>

On Friday, March 11, 2022 at 12:46:33 AM UTC-5, BGB wrote:
> On 3/10/2022 7:58 PM, robf...@gmail.com wrote:
> > On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
> >> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
> >>> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
> >>>> On 3/9/2022 10:20 AM, EricP wrote:
> >>>
> >>>>> Note that operating systems such as Linux the hierarchical page table is
> >>>>> part of its design. To port it to Power with its hash/inverted page table
> >>>>> they kept the hierarchical table managed in memory as before,
> >>>>> and move valid PTE entries into and out of the hash table.
> >>>>>
> >>>>> In effect, the hierarchical table is still the OS page table,
> >>>>> and the hash table is treated like a giant software managed TLB.
> >>>>> Software could implement, say, a FIFO mechanism to rotate a working set
> >>>>> of Present hierarchical PTE's through hash PTE slots,
> >>>>> similar to how a HW TLB might rotate through its entries.
> >>>>>
> >>>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
> >>>>> would be very important for efficiency, as without them a process switch
> >>>>> would require invalidating all hash table entries just like a real TLB.
> >>>>>
> >>> Seems kind of kludgy. I am wondering why now this approach was used.
> >>>
> >>> I have coded in the bus interface unit the capability to use either hashed or
> >>> hierarchical page tables. I was not so insane as to ignore the popularity of
> >>> hierarchical page tables. Can probably use both types at the same time.
> >>> Hashed tables are a better way to go for a large address
> >>> space in my opinion. They use less memory and may have faster look-ups.
> >>>
> >> Hashed tables could also make sense as an alternative to B-Trees.
> >>
> >> A B-Tree lookup is likely to be relatively complicated and expensive if
> >> compared to a hash lookup.
> >>
> >> It is possible that I could also combine a hashed top-level with
> >> 2-levels of nested page table (optionally collapsing down the upper 6
> >> levels into a single page).
> >>>
> >>>> OK. This gives more context for what I was confused about in my response.
> >>>>
> >>>> In my case, I use a software managed TLB, with hierarchical page tables,
> >>>> and no sort of intermediate stage representation.
> >>>>
> >>>> TLB miss interrupt occurs, handler walks the page table, and loads the
> >>>> resulting entry into the TLB. Basic design for the mechanism was
> >>>> more-or-less lifted from SH-4, but with the major difference of going
> >>>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
> >>>>
> >>>> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
> >>>>
> >>>>
> >>>> I had considered potentially using B-Trees for the upper levels (instead
> >>>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
> >>>> leads to a "very sparse" 8-level table, and a B-Tree could be more
> >>>> compact (with more traditional nested page tables for the lower 2 or 3
> >>>> levels).
> >>>>
> >>>> Though, there are other (potentially simpler/cheaper) ways to deal with
> >>>> this.
> >>>>
> >>>> This would not really effect the hardware in my case.
> >>>
> >>> Page tables are walked via hardware for Thor. Software only gets involved on a
> >>> page fault. While software managing the TLB is probably comparable in
> >>> performance and more flexible than hardware, TLB updates with hardware
> >>> walking are almost invisible to software.
> >>>
> >> This was one annoyance with BJX2 with the use of software managed TLB:
> >> Getting the software TLB miss interrupts stable was a major source of
> >> annoyance, as there were a whole lot of "little things" that can go
> >> wrong in these mechanisms.
> >>
> >> The L1 caches needing to be able to stop what they are doing, then
> >> quietly transfer control to an ISR, then resume normal operation without
> >> any adverse side effects, was a bit of a pain to debug.
> >>
> >> Some of the cases were infrequent, so one might to get Doom or Quake
> >> launched (in a simulation) before the crash happens, where firing these
> >> up inside a Verilog simulation is not exactly a fast process (the time
> >> issue is also a major reason why I am using LZ compressed binaries and
> >> WADs).
> >>
> >>
> >> As noted, the MMU is temporarily disabled within ISRs, partly because
> >> there is no way for an ISR to deal with a TLB miss (unlike some CPU
> >> architectures, ISRs are not re-entrant in my case).
> >>
> >>
> >> Similarly, the TLB miss handler would have to resolve page-fault
> >> scenarios (for virtual memory), without access to the main filesystem
> >> driver (it has to bypass the driver and access the SDCard directly), but
> >> does also mean that a page fault (to virtual memory) during some other
> >> SDcard IO request would be "potentially fatal".
> >>
> >> ...
> >>
> >> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
> >> there is nowhere else to put it in this case.
> >>
> >>
> >> What to do with a page-fault to an unmapped address (eg: not backed to
> >> the page file) is currently an unresolved issue, but this is more a
> >> software thing than a hardware thing (in a real OS, would probably
> >> terminate the process or similar here; for the time being, the only real
> >> solution is to trigger a breakpoint).
> >>
> >> I may need to consider going and adding preemptive multitasking, as it
> >> looks like most "real OS" stuff would depend on this (cooperative
> >> multitasking doesn't scale particularly well, or leave any real good
> >> solution for "OK, this program has gone into an infinite loop or
> >> crashed", which basically leaves no real solution otherwise).
> >>
> >>
> >>
> >> The debugging was getting bad enough that I almost started to debate
> >> whether it would be worthwhile to add hardware page walking and not have
> >> to deal with this as much (but would still need a Page Fault handler, so
> >> it is not entirely avoidable).
> >>
> >>
> >> Sorta spent most of February beating on trying to debug stuff related to
> >> the L1 Caches and their interaction with the TLB Miss ISR, partly as
> >> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
> >>
> >> Likewise, much of my past debugging effort here was more focused on
> >> "quick and dirty" fixes which typically don't really resolve the
> >> underlying issues; but, trying to figure out "why" something is going
> >> wrong is often a lot harder than adding "make it work" hacks (and then
> >> notice the bug hasn't gone away, it has merely moved to a new location).
> >>
> >>
> >> I still can't say (with much confidence) that the TLB is now stable, but
> >> in my testing at the moment, it appears to work.
> >>
> >> Though, this debugging effort wasn't helped with Verilator also having
> >> the annoying behavior that adding and removing $display statements can
> >> sometimes change the behavior of the logic...
> >>> The TLB can be updated via software, its almost possible then to use a software
> >>> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
> >>> then maybe things could have the option of software management.
> >>>
> >> Could be.
> >>
> >> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
> >>
> >> In the ISR, there is a 'TEA' register that holds the address of whatever
> >> caused the interrupt (target address for TLB miss), and an 'EXSR'
> >> register where the low bits encode which interrupt had occurred (as a
> >> 16-bit number divided into multiple bit fields).
> >>> I get the feeling there are too many choices available in Thor. Maybe a configuration
> >>> utility would be better than building in everything.
> >>>
> >>> Wondering what entity to place share counts, access keys, and privilege levels in. I
> >>> had these in the PTE but took them out. There is only one set required for each page
> >>> of memory.
> >>>
> >> I have this stuff in the PTEs/TLBEs.
> >>
> >> There is also an ACL Cache with an ACL Miss interrupt as well.
> >>
> >> The software side of things isn't really developed all that well yet, as
> >> most of the time thus far had gone more into trying to get things stable
> >> enough that the address translation and TLB miss interrupts weren't
> >> prone to crash stuff.
> >>
> >> I seem to have this part stable now, so now it should be possible to
> >> start making forward progress in this area.
> >
> > For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
> > share-counts, etc. included in it. A larger PTE would really complicate things.
> > The TLBE value can be loaded or stored from / to the TLB using a single
> > 128-bit wide register. Anything wider means using a pair of registers. I could
> > maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
> > I had the thought that since there only needs to be one copy of the information it
> > could be stored in another entity. But this means potentially adding to the memory
> > access time since another table is accessed after the physical page number is
> > known.
> >
> I also have 128-bit TLBE's, with fields for 48 bit addresses.
>
> Though the address fields are actually 36 bits, because one can cut off
> the low-order bits for the address (and because the "base form"
> addressing is 48-bit).
>
> While there is a 96-bit virtual-address mode, as noted, it works by
> using TLBE's in pairs to get more bits (at the cost of associativity).
> It mostly just extends the virtual address by 48 bits, with most of the
> rest of the bits being unused.
>
> I ended up implementing the 256-bit TLB load via a "double pumping"
> strategy (load both halves and then the MMU sticks them together).
>
>
>
> Would be a little bit harder with a full 64-bit virtual address space
> though.
>
>
> Copy/Paste
>
> TLBE:
> * (127:112) = VUGID / ACLID
> * (111: 76) = Virtual Address Page
> * ( 75: 64) = KR Access
> * ( 63: 48) = ASID
> * ( 47: 12) = Physical Address Page
> * ( 11: 0) = Page Control bits
>
> VUGID:
> * (15:10) = VGID / VUID(Swap)
> * ( 9: 0) = VUID / VGID(Swap)
> * May be interpreted as a PID or ACLID.
> ** In these cases, VUGID is treated as a single 16-bit unit.
>
> ASID:
> * (15:10) = AGID (0=Shared, Global)
> * ( 9: 0) = APID (0=Shared, Group)
>
> KR Access:
> * (11): Other X
> * (10): Other W
> * ( 9): Other R
> * ( 8): Group X (VUGID Check Only)
> * ( 7): Group W (VUGID Check Only)
> * ( 6): Group R (VUGID Check Only)
> * ( 5): User X (VUGID Check Only)
> * ( 4): User W (VUGID Check Only)
> * ( 3): User R (VUGID Check Only)
> * ( 2): VUGID Mode 2
> * ( 1): VUGID Mode 1
> * ( 0): VUGID Mode 0
>
> The VUGID Mode bits basically encode what sort of check to perform
> (VUGID or ACL style).
>
>
> These include, say:
> Disabled, VUGID, VUGID (Swap), or ACL.
>
> In VUGID mode, it does User/Group/Other checks, Swap switches
> User/Group. ACL: Use ACL (in TLBE), Exact 16-bit match only (ACLE).
> > I do not know much about ACL except that I suspect it can be quite complicated to do
> > with hardware. Is there ACL for individual pages of memory? There can be users or
> > groups of users and system processes all with separate access requirements. I suspect
> > there would be some limits engineered into ACL. For instance, limited numbers of
> > groups and users to keep the reference fields a reasonable size. Can you elaborate on
> > the ACL?
> >
> These are per-page checks.
>
>
> The ACL checking doesn't really add all that much cost or complexity
> compared with the TLB itself.
>
> Main costs are mostly the need to spend TLB bits on it, and the addition
> of a Keyring Register (KRR).
>
> Most of the harder parts of the ACL Check (namely, performing the ACL
> lookups) would be handled in software, so all the hardware really needs
> to do is check whether the keyring entries are in the ACL Cache, and (it
> they hit) what sort of access is allowed to the page in question (the
> access bits are OR'ed together).
>
>
> ACLE:
> * (63:44): Reserved / MBZ
> * (43:32): KR Access Mode
> * (31:16): KRR VUGID / APID
> * (15: 0): TLB VUGID / ACLID
>
> So, one basically does associative checks between the entries in the
> ACLE cache, and the entries in KRR.
>
> Because KRR changes relatively infrequently, the ACLE can be pretty
> small (ideally, it is larger than the KRR though, so 6 or 8 entries
> would be better than 4, but I am using 4 entries for now).
>
>
> The combined result of VUGID/ACL, and Basic checks are combined into a
> single bit-mask saying what access is allowed (in a given operating mode
> and at a given time). The L1 Caches will use these bits during memory
> access.
> > In my PTE eight bits are used for access control to indicate read/write/execute/cache
> > for either user or system. Maybe these bits would be better used to refer to an ACL. If
> > I were to trim four bits off the page number fields that means a 16-bit ACL reference
> > field could be supported.
> OK.
>
> I was able to fit both Basic checks and ACL/VUGID checks.
>
> The Basic checks are used ye olde User/Supervisor and similar (R/W/X)
> and a few bits which effects caching or combinations which are used
> encode alternate special behaviors (Privledged-Execute and
> Execute-As-ACLID).
>
>
> ...
I cannot quite get my head around how the ACL comes into play, but I have provided for
an ACL in TLBE.

On Saturday, March 12, 2022 at 8:30:44 PM UTC-6, robf...@gmail.com wrote:
> On Friday, March 11, 2022 at 12:46:33 AM UTC-5, BGB wrote:
> > On 3/10/2022 7:58 PM, robf...@gmail.com wrote:
> > > On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
> > >> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
> > >>> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
> > >>>> On 3/9/2022 10:20 AM, EricP wrote:
> > >>>
> > >>>>> Note that operating systems such as Linux the hierarchical page table is
> > >>>>> part of its design. To port it to Power with its hash/inverted page table
> > >>>>> they kept the hierarchical table managed in memory as before,
> > >>>>> and move valid PTE entries into and out of the hash table.
> > >>>>>
> > >>>>> In effect, the hierarchical table is still the OS page table,
> > >>>>> and the hash table is treated like a giant software managed TLB.
> > >>>>> Software could implement, say, a FIFO mechanism to rotate a working set
> > >>>>> of Present hierarchical PTE's through hash PTE slots,
> > >>>>> similar to how a HW TLB might rotate through its entries.
> > >>>>>
> > >>>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
> > >>>>> would be very important for efficiency, as without them a process switch
> > >>>>> would require invalidating all hash table entries just like a real TLB.
> > >>>>>
> > >>> Seems kind of kludgy. I am wondering why now this approach was used..
> > >>>
> > >>> I have coded in the bus interface unit the capability to use either hashed or
> > >>> hierarchical page tables. I was not so insane as to ignore the popularity of
> > >>> hierarchical page tables. Can probably use both types at the same time.
> > >>> Hashed tables are a better way to go for a large address
> > >>> space in my opinion. They use less memory and may have faster look-ups.
> > >>>
> > >> Hashed tables could also make sense as an alternative to B-Trees.
> > >>
> > >> A B-Tree lookup is likely to be relatively complicated and expensive if
> > >> compared to a hash lookup.
> > >>
> > >> It is possible that I could also combine a hashed top-level with
> > >> 2-levels of nested page table (optionally collapsing down the upper 6
> > >> levels into a single page).
> > >>>
> > >>>> OK. This gives more context for what I was confused about in my response.
> > >>>>
> > >>>> In my case, I use a software managed TLB, with hierarchical page tables,
> > >>>> and no sort of intermediate stage representation.
> > >>>>
> > >>>> TLB miss interrupt occurs, handler walks the page table, and loads the
> > >>>> resulting entry into the TLB. Basic design for the mechanism was
> > >>>> more-or-less lifted from SH-4, but with the major difference of going
> > >>>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
> > >>>>
> > >>>> Arguably, a 6-way or 8-way TLB could be better, but more expensive..
> > >>>>
> > >>>>
> > >>>> I had considered potentially using B-Trees for the upper levels (instead
> > >>>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
> > >>>> leads to a "very sparse" 8-level table, and a B-Tree could be more
> > >>>> compact (with more traditional nested page tables for the lower 2 or 3
> > >>>> levels).
> > >>>>
> > >>>> Though, there are other (potentially simpler/cheaper) ways to deal with
> > >>>> this.
> > >>>>
> > >>>> This would not really effect the hardware in my case.
> > >>>
> > >>> Page tables are walked via hardware for Thor. Software only gets involved on a
> > >>> page fault. While software managing the TLB is probably comparable in
> > >>> performance and more flexible than hardware, TLB updates with hardware
> > >>> walking are almost invisible to software.
> > >>>
> > >> This was one annoyance with BJX2 with the use of software managed TLB:
> > >> Getting the software TLB miss interrupts stable was a major source of
> > >> annoyance, as there were a whole lot of "little things" that can go
> > >> wrong in these mechanisms.
> > >>
> > >> The L1 caches needing to be able to stop what they are doing, then
> > >> quietly transfer control to an ISR, then resume normal operation without
> > >> any adverse side effects, was a bit of a pain to debug.
> > >>
> > >> Some of the cases were infrequent, so one might to get Doom or Quake
> > >> launched (in a simulation) before the crash happens, where firing these
> > >> up inside a Verilog simulation is not exactly a fast process (the time
> > >> issue is also a major reason why I am using LZ compressed binaries and
> > >> WADs).
> > >>
> > >>
> > >> As noted, the MMU is temporarily disabled within ISRs, partly because
> > >> there is no way for an ISR to deal with a TLB miss (unlike some CPU
> > >> architectures, ISRs are not re-entrant in my case).
> > >>
> > >>
> > >> Similarly, the TLB miss handler would have to resolve page-fault
> > >> scenarios (for virtual memory), without access to the main filesystem
> > >> driver (it has to bypass the driver and access the SDCard directly), but
> > >> does also mean that a page fault (to virtual memory) during some other
> > >> SDcard IO request would be "potentially fatal".
> > >>
> > >> ...
> > >>
> > >> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
> > >> there is nowhere else to put it in this case.
> > >>
> > >>
> > >> What to do with a page-fault to an unmapped address (eg: not backed to
> > >> the page file) is currently an unresolved issue, but this is more a
> > >> software thing than a hardware thing (in a real OS, would probably
> > >> terminate the process or similar here; for the time being, the only real
> > >> solution is to trigger a breakpoint).
> > >>
> > >> I may need to consider going and adding preemptive multitasking, as it
> > >> looks like most "real OS" stuff would depend on this (cooperative
> > >> multitasking doesn't scale particularly well, or leave any real good
> > >> solution for "OK, this program has gone into an infinite loop or
> > >> crashed", which basically leaves no real solution otherwise).
> > >>
> > >>
> > >>
> > >> The debugging was getting bad enough that I almost started to debate
> > >> whether it would be worthwhile to add hardware page walking and not have
> > >> to deal with this as much (but would still need a Page Fault handler, so
> > >> it is not entirely avoidable).
> > >>
> > >>
> > >> Sorta spent most of February beating on trying to debug stuff related to
> > >> the L1 Caches and their interaction with the TLB Miss ISR, partly as
> > >> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
> > >>
> > >> Likewise, much of my past debugging effort here was more focused on
> > >> "quick and dirty" fixes which typically don't really resolve the
> > >> underlying issues; but, trying to figure out "why" something is going
> > >> wrong is often a lot harder than adding "make it work" hacks (and then
> > >> notice the bug hasn't gone away, it has merely moved to a new location).
> > >>
> > >>
> > >> I still can't say (with much confidence) that the TLB is now stable, but
> > >> in my testing at the moment, it appears to work.
> > >>
> > >> Though, this debugging effort wasn't helped with Verilator also having
> > >> the annoying behavior that adding and removing $display statements can
> > >> sometimes change the behavior of the logic...
> > >>> The TLB can be updated via software, its almost possible then to use a software
> > >>> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
> > >>> then maybe things could have the option of software management.
> > >>>
> > >> Could be.
> > >>
> > >> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
> > >>
> > >> In the ISR, there is a 'TEA' register that holds the address of whatever
> > >> caused the interrupt (target address for TLB miss), and an 'EXSR'
> > >> register where the low bits encode which interrupt had occurred (as a
> > >> 16-bit number divided into multiple bit fields).
> > >>> I get the feeling there are too many choices available in Thor. Maybe a configuration
> > >>> utility would be better than building in everything.
> > >>>
> > >>> Wondering what entity to place share counts, access keys, and privilege levels in. I
> > >>> had these in the PTE but took them out. There is only one set required for each page
> > >>> of memory.
> > >>>
> > >> I have this stuff in the PTEs/TLBEs.
> > >>
> > >> There is also an ACL Cache with an ACL Miss interrupt as well.
> > >>
> > >> The software side of things isn't really developed all that well yet, as
> > >> most of the time thus far had gone more into trying to get things stable
> > >> enough that the address translation and TLB miss interrupts weren't
> > >> prone to crash stuff.
> > >>
> > >> I seem to have this part stable now, so now it should be possible to
> > >> start making forward progress in this area.
> > >
> > > For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
> > > share-counts, etc. included in it. A larger PTE would really complicate things.
> > > The TLBE value can be loaded or stored from / to the TLB using a single
> > > 128-bit wide register. Anything wider means using a pair of registers.. I could
> > > maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
> > > I had the thought that since there only needs to be one copy of the information it
> > > could be stored in another entity. But this means potentially adding to the memory
> > > access time since another table is accessed after the physical page number is
> > > known.
> > >
> > I also have 128-bit TLBE's, with fields for 48 bit addresses.
> >
> > Though the address fields are actually 36 bits, because one can cut off
> > the low-order bits for the address (and because the "base form"
> > addressing is 48-bit).
> >
> > While there is a 96-bit virtual-address mode, as noted, it works by
> > using TLBE's in pairs to get more bits (at the cost of associativity).
> > It mostly just extends the virtual address by 48 bits, with most of the
> > rest of the bits being unused.
> >
> > I ended up implementing the 256-bit TLB load via a "double pumping"
> > strategy (load both halves and then the MMU sticks them together).
> >
> >
> >
> > Would be a little bit harder with a full 64-bit virtual address space
> > though.
> >
> >
> > Copy/Paste
> >
> > TLBE:
> > * (127:112) = VUGID / ACLID
> > * (111: 76) = Virtual Address Page
> > * ( 75: 64) = KR Access
> > * ( 63: 48) = ASID
> > * ( 47: 12) = Physical Address Page
> > * ( 11: 0) = Page Control bits
> >
> > VUGID:
> > * (15:10) = VGID / VUID(Swap)
> > * ( 9: 0) = VUID / VGID(Swap)
> > * May be interpreted as a PID or ACLID.
> > ** In these cases, VUGID is treated as a single 16-bit unit.
> >
> > ASID:
> > * (15:10) = AGID (0=Shared, Global)
> > * ( 9: 0) = APID (0=Shared, Group)
> >
> > KR Access:
> > * (11): Other X
> > * (10): Other W
> > * ( 9): Other R
> > * ( 8): Group X (VUGID Check Only)
> > * ( 7): Group W (VUGID Check Only)
> > * ( 6): Group R (VUGID Check Only)
> > * ( 5): User X (VUGID Check Only)
> > * ( 4): User W (VUGID Check Only)
> > * ( 3): User R (VUGID Check Only)
> > * ( 2): VUGID Mode 2
> > * ( 1): VUGID Mode 1
> > * ( 0): VUGID Mode 0
> >
> > The VUGID Mode bits basically encode what sort of check to perform
> > (VUGID or ACL style).
> >
> >
> > These include, say:
> > Disabled, VUGID, VUGID (Swap), or ACL.
> >
> > In VUGID mode, it does User/Group/Other checks, Swap switches
> > User/Group. ACL: Use ACL (in TLBE), Exact 16-bit match only (ACLE).
> > > I do not know much about ACL except that I suspect it can be quite complicated to do
> > > with hardware. Is there ACL for individual pages of memory? There can be users or
> > > groups of users and system processes all with separate access requirements. I suspect
> > > there would be some limits engineered into ACL. For instance, limited numbers of
> > > groups and users to keep the reference fields a reasonable size. Can you elaborate on
> > > the ACL?
> > >
> > These are per-page checks.
> >
> >
> > The ACL checking doesn't really add all that much cost or complexity
> > compared with the TLB itself.
> >
> > Main costs are mostly the need to spend TLB bits on it, and the addition
> > of a Keyring Register (KRR).
> >
> > Most of the harder parts of the ACL Check (namely, performing the ACL
> > lookups) would be handled in software, so all the hardware really needs
> > to do is check whether the keyring entries are in the ACL Cache, and (it
> > they hit) what sort of access is allowed to the page in question (the
> > access bits are OR'ed together).
> >
> >
> > ACLE:
> > * (63:44): Reserved / MBZ
> > * (43:32): KR Access Mode
> > * (31:16): KRR VUGID / APID
> > * (15: 0): TLB VUGID / ACLID
> >
> > So, one basically does associative checks between the entries in the
> > ACLE cache, and the entries in KRR.
> >
> > Because KRR changes relatively infrequently, the ACLE can be pretty
> > small (ideally, it is larger than the KRR though, so 6 or 8 entries
> > would be better than 4, but I am using 4 entries for now).
> >
> >
> > The combined result of VUGID/ACL, and Basic checks are combined into a
> > single bit-mask saying what access is allowed (in a given operating mode
> > and at a given time). The L1 Caches will use these bits during memory
> > access.
> > > In my PTE eight bits are used for access control to indicate read/write/execute/cache
> > > for either user or system. Maybe these bits would be better used to refer to an ACL. If
> > > I were to trim four bits off the page number fields that means a 16-bit ACL reference
> > > field could be supported.
> > OK.
> >
> > I was able to fit both Basic checks and ACL/VUGID checks.
> >
> > The Basic checks are used ye olde User/Supervisor and similar (R/W/X)
> > and a few bits which effects caching or combinations which are used
> > encode alternate special behaviors (Privledged-Execute and
> > Execute-As-ACLID).
> >
> >
> > ...
> I cannot quite get my head around how the ACL comes into play, but I have provided for
> an ACL in TLBE.
>
> I decided to use 160-bit PTEs. I really wanted to support at least a full 76-bit virtual
> address translation and things just would not fit into a 128-bit PTE. For a hashed table
> this works just fine. Six are packed into 1024 bit with 64-bits to spare. However, for a
> hierarchical table 160-bit PTEs are bit nightmarish.
<
My 66000 has 63-bit virtual address translates into a 66-bit universal address {hint:
MMI/O, Configuration, and ROM are not part of the 64-bit DRAM address space}.
Yet I fit each PTP and PTE into one (1) 64-bit container, and I can skip levels in the
tables so small applications (like cat) can fit in 23-bit virtual address and have 1
layer of PTPs and 1 layer of PTEs. I even have bits left over......
<
What is driving force for 76-bit virtual address ?
<
Secondly, even with a 76-bit virtual address, you should only be needing 90-bits±
for a PTE. Seems to me that the structure of you PTE needs rethought.
<
So, what is the structure of your PTE ?
<
> Just thinking to myself here. Since 160-bit PTEs do not pack a power of two into a
> memory page, that means either increasing the PTE size to 256 bits wasting a lot of
> space, Or doing a high-speed divide by a constant to calculate the page and entry number
> within a page. How practical is the high-speed divide? 204 PTEs will fit into a 4096-byte
> page. That means dividing the address by 204 instead of 256 to find the page number.
> This divide can be done as a multiply by constant reciprocal. 204**-1 * 4096 = 20. 12 bits
> was chosen to have a few extra bits of precision for the remainder. So, take the address
> multiply by 20 then shift right 12 times to get the page number. Multiply by 20 was
<
Notice that multiply by 20 = 4×5 so the only multiply is by 5, then shift up by 4 and down by 12
(or just down by 8).
<
> chosen also because its relatively painless to do. Then compute the entry number as the
> remainder. Multiply the quotient by 204 and subtract it from the original address to get the
> entry number. Example: entry #7000 = 20*7000 = 140000. 140000 >> 12 = 34 which is the
> page number. 34 * 204 = 6936. 7000-6936 = 64. So, entry 64 in page 34 is the desired
> entry. Multiply by 204=multiply by 128 + multiply by 64 + multiply by 8 which is just shifting
> plus a 3- entry adder. Seems straightforward enough. The question is, should it be done?
<
Seems to be addressing the first 2 question should come before this one.
>
> TLB entries are much larger, 224 bits now. They include the PTE plus a 32-bit access key
> from the access rights table and a 32-bit access counter. The access counter is used by
> the clock algorithm which is implemented in hardware. The TLB entry gets read and written
> with every access, so I figured it may as well be updating a counter at the same time.
> Another hardware state machine takes care of aging the counters.
<
Why is the access key in the PTE?--it should be a part of the page itself.
<
Seems to me you are putting useful things in the wrong places.

On Saturday, March 12, 2022 at 9:44:17 PM UTC-5, MitchAlsup wrote:
> On Saturday, March 12, 2022 at 8:30:44 PM UTC-6, robf...@gmail.com wrote:
> > On Friday, March 11, 2022 at 12:46:33 AM UTC-5, BGB wrote:
> > > On 3/10/2022 7:58 PM, robf...@gmail.com wrote:
> > > > On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
> > > >> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
> > > >>> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
> > > >>>> On 3/9/2022 10:20 AM, EricP wrote:
> > > >>>
> > > >>>>> Note that operating systems such as Linux the hierarchical page table is
> > > >>>>> part of its design. To port it to Power with its hash/inverted page table
> > > >>>>> they kept the hierarchical table managed in memory as before,
> > > >>>>> and move valid PTE entries into and out of the hash table.
> > > >>>>>
> > > >>>>> In effect, the hierarchical table is still the OS page table,
> > > >>>>> and the hash table is treated like a giant software managed TLB..
> > > >>>>> Software could implement, say, a FIFO mechanism to rotate a working set
> > > >>>>> of Present hierarchical PTE's through hash PTE slots,
> > > >>>>> similar to how a HW TLB might rotate through its entries.
> > > >>>>>
> > > >>>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
> > > >>>>> would be very important for efficiency, as without them a process switch
> > > >>>>> would require invalidating all hash table entries just like a real TLB.
> > > >>>>>
> > > >>> Seems kind of kludgy. I am wondering why now this approach was used.
> > > >>>
> > > >>> I have coded in the bus interface unit the capability to use either hashed or
> > > >>> hierarchical page tables. I was not so insane as to ignore the popularity of
> > > >>> hierarchical page tables. Can probably use both types at the same time.
> > > >>> Hashed tables are a better way to go for a large address
> > > >>> space in my opinion. They use less memory and may have faster look-ups.
> > > >>>
> > > >> Hashed tables could also make sense as an alternative to B-Trees.
> > > >>
> > > >> A B-Tree lookup is likely to be relatively complicated and expensive if
> > > >> compared to a hash lookup.
> > > >>
> > > >> It is possible that I could also combine a hashed top-level with
> > > >> 2-levels of nested page table (optionally collapsing down the upper 6
> > > >> levels into a single page).
> > > >>>
> > > >>>> OK. This gives more context for what I was confused about in my response.
> > > >>>>
> > > >>>> In my case, I use a software managed TLB, with hierarchical page tables,
> > > >>>> and no sort of intermediate stage representation.
> > > >>>>
> > > >>>> TLB miss interrupt occurs, handler walks the page table, and loads the
> > > >>>> resulting entry into the TLB. Basic design for the mechanism was
> > > >>>> more-or-less lifted from SH-4, but with the major difference of going
> > > >>>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB..
> > > >>>>
> > > >>>> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
> > > >>>>
> > > >>>>
> > > >>>> I had considered potentially using B-Trees for the upper levels (instead
> > > >>>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
> > > >>>> leads to a "very sparse" 8-level table, and a B-Tree could be more
> > > >>>> compact (with more traditional nested page tables for the lower 2 or 3
> > > >>>> levels).
> > > >>>>
> > > >>>> Though, there are other (potentially simpler/cheaper) ways to deal with
> > > >>>> this.
> > > >>>>
> > > >>>> This would not really effect the hardware in my case.
> > > >>>
> > > >>> Page tables are walked via hardware for Thor. Software only gets involved on a
> > > >>> page fault. While software managing the TLB is probably comparable in
> > > >>> performance and more flexible than hardware, TLB updates with hardware
> > > >>> walking are almost invisible to software.
> > > >>>
> > > >> This was one annoyance with BJX2 with the use of software managed TLB:
> > > >> Getting the software TLB miss interrupts stable was a major source of
> > > >> annoyance, as there were a whole lot of "little things" that can go
> > > >> wrong in these mechanisms.
> > > >>
> > > >> The L1 caches needing to be able to stop what they are doing, then
> > > >> quietly transfer control to an ISR, then resume normal operation without
> > > >> any adverse side effects, was a bit of a pain to debug.
> > > >>
> > > >> Some of the cases were infrequent, so one might to get Doom or Quake
> > > >> launched (in a simulation) before the crash happens, where firing these
> > > >> up inside a Verilog simulation is not exactly a fast process (the time
> > > >> issue is also a major reason why I am using LZ compressed binaries and
> > > >> WADs).
> > > >>
> > > >>
> > > >> As noted, the MMU is temporarily disabled within ISRs, partly because
> > > >> there is no way for an ISR to deal with a TLB miss (unlike some CPU
> > > >> architectures, ISRs are not re-entrant in my case).
> > > >>
> > > >>
> > > >> Similarly, the TLB miss handler would have to resolve page-fault
> > > >> scenarios (for virtual memory), without access to the main filesystem
> > > >> driver (it has to bypass the driver and access the SDCard directly), but
> > > >> does also mean that a page fault (to virtual memory) during some other
> > > >> SDcard IO request would be "potentially fatal".
> > > >>
> > > >> ...
> > > >>
> > > >> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
> > > >> there is nowhere else to put it in this case.
> > > >>
> > > >>
> > > >> What to do with a page-fault to an unmapped address (eg: not backed to
> > > >> the page file) is currently an unresolved issue, but this is more a
> > > >> software thing than a hardware thing (in a real OS, would probably
> > > >> terminate the process or similar here; for the time being, the only real
> > > >> solution is to trigger a breakpoint).
> > > >>
> > > >> I may need to consider going and adding preemptive multitasking, as it
> > > >> looks like most "real OS" stuff would depend on this (cooperative
> > > >> multitasking doesn't scale particularly well, or leave any real good
> > > >> solution for "OK, this program has gone into an infinite loop or
> > > >> crashed", which basically leaves no real solution otherwise).
> > > >>
> > > >>
> > > >>
> > > >> The debugging was getting bad enough that I almost started to debate
> > > >> whether it would be worthwhile to add hardware page walking and not have
> > > >> to deal with this as much (but would still need a Page Fault handler, so
> > > >> it is not entirely avoidable).
> > > >>
> > > >>
> > > >> Sorta spent most of February beating on trying to debug stuff related to
> > > >> the L1 Caches and their interaction with the TLB Miss ISR, partly as
> > > >> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
> > > >>
> > > >> Likewise, much of my past debugging effort here was more focused on
> > > >> "quick and dirty" fixes which typically don't really resolve the
> > > >> underlying issues; but, trying to figure out "why" something is going
> > > >> wrong is often a lot harder than adding "make it work" hacks (and then
> > > >> notice the bug hasn't gone away, it has merely moved to a new location).
> > > >>
> > > >>
> > > >> I still can't say (with much confidence) that the TLB is now stable, but
> > > >> in my testing at the moment, it appears to work.
> > > >>
> > > >> Though, this debugging effort wasn't helped with Verilator also having
> > > >> the annoying behavior that adding and removing $display statements can
> > > >> sometimes change the behavior of the logic...
> > > >>> The TLB can be updated via software, its almost possible then to use a software
> > > >>> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
> > > >>> then maybe things could have the option of software management.
> > > >>>
> > > >> Could be.
> > > >>
> > > >> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
> > > >>
> > > >> In the ISR, there is a 'TEA' register that holds the address of whatever
> > > >> caused the interrupt (target address for TLB miss), and an 'EXSR'
> > > >> register where the low bits encode which interrupt had occurred (as a
> > > >> 16-bit number divided into multiple bit fields).
> > > >>> I get the feeling there are too many choices available in Thor. Maybe a configuration
> > > >>> utility would be better than building in everything.
> > > >>>
> > > >>> Wondering what entity to place share counts, access keys, and privilege levels in. I
> > > >>> had these in the PTE but took them out. There is only one set required for each page
> > > >>> of memory.
> > > >>>
> > > >> I have this stuff in the PTEs/TLBEs.
> > > >>
> > > >> There is also an ACL Cache with an ACL Miss interrupt as well.
> > > >>
> > > >> The software side of things isn't really developed all that well yet, as
> > > >> most of the time thus far had gone more into trying to get things stable
> > > >> enough that the address translation and TLB miss interrupts weren't
> > > >> prone to crash stuff.
> > > >>
> > > >> I seem to have this part stable now, so now it should be possible to
> > > >> start making forward progress in this area.
> > > >
> > > > For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
> > > > share-counts, etc. included in it. A larger PTE would really complicate things.
> > > > The TLBE value can be loaded or stored from / to the TLB using a single
> > > > 128-bit wide register. Anything wider means using a pair of registers. I could
> > > > maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
> > > > I had the thought that since there only needs to be one copy of the information it
> > > > could be stored in another entity. But this means potentially adding to the memory
> > > > access time since another table is accessed after the physical page number is
> > > > known.
> > > >
> > > I also have 128-bit TLBE's, with fields for 48 bit addresses.
> > >
> > > Though the address fields are actually 36 bits, because one can cut off
> > > the low-order bits for the address (and because the "base form"
> > > addressing is 48-bit).
> > >
> > > While there is a 96-bit virtual-address mode, as noted, it works by
> > > using TLBE's in pairs to get more bits (at the cost of associativity)..
> > > It mostly just extends the virtual address by 48 bits, with most of the
> > > rest of the bits being unused.
> > >
> > > I ended up implementing the 256-bit TLB load via a "double pumping"
> > > strategy (load both halves and then the MMU sticks them together).
> > >
> > >
> > >
> > > Would be a little bit harder with a full 64-bit virtual address space
> > > though.
> > >
> > >
> > > Copy/Paste
> > >
> > > TLBE:
> > > * (127:112) = VUGID / ACLID
> > > * (111: 76) = Virtual Address Page
> > > * ( 75: 64) = KR Access
> > > * ( 63: 48) = ASID
> > > * ( 47: 12) = Physical Address Page
> > > * ( 11: 0) = Page Control bits
> > >
> > > VUGID:
> > > * (15:10) = VGID / VUID(Swap)
> > > * ( 9: 0) = VUID / VGID(Swap)
> > > * May be interpreted as a PID or ACLID.
> > > ** In these cases, VUGID is treated as a single 16-bit unit.
> > >
> > > ASID:
> > > * (15:10) = AGID (0=Shared, Global)
> > > * ( 9: 0) = APID (0=Shared, Group)
> > >
> > > KR Access:
> > > * (11): Other X
> > > * (10): Other W
> > > * ( 9): Other R
> > > * ( 8): Group X (VUGID Check Only)
> > > * ( 7): Group W (VUGID Check Only)
> > > * ( 6): Group R (VUGID Check Only)
> > > * ( 5): User X (VUGID Check Only)
> > > * ( 4): User W (VUGID Check Only)
> > > * ( 3): User R (VUGID Check Only)
> > > * ( 2): VUGID Mode 2
> > > * ( 1): VUGID Mode 1
> > > * ( 0): VUGID Mode 0
> > >
> > > The VUGID Mode bits basically encode what sort of check to perform
> > > (VUGID or ACL style).
> > >
> > >
> > > These include, say:
> > > Disabled, VUGID, VUGID (Swap), or ACL.
> > >
> > > In VUGID mode, it does User/Group/Other checks, Swap switches
> > > User/Group. ACL: Use ACL (in TLBE), Exact 16-bit match only (ACLE).
> > > > I do not know much about ACL except that I suspect it can be quite complicated to do
> > > > with hardware. Is there ACL for individual pages of memory? There can be users or
> > > > groups of users and system processes all with separate access requirements. I suspect
> > > > there would be some limits engineered into ACL. For instance, limited numbers of
> > > > groups and users to keep the reference fields a reasonable size. Can you elaborate on
> > > > the ACL?
> > > >
> > > These are per-page checks.
> > >
> > >
> > > The ACL checking doesn't really add all that much cost or complexity
> > > compared with the TLB itself.
> > >
> > > Main costs are mostly the need to spend TLB bits on it, and the addition
> > > of a Keyring Register (KRR).
> > >
> > > Most of the harder parts of the ACL Check (namely, performing the ACL
> > > lookups) would be handled in software, so all the hardware really needs
> > > to do is check whether the keyring entries are in the ACL Cache, and (it
> > > they hit) what sort of access is allowed to the page in question (the
> > > access bits are OR'ed together).
> > >
> > >
> > > ACLE:
> > > * (63:44): Reserved / MBZ
> > > * (43:32): KR Access Mode
> > > * (31:16): KRR VUGID / APID
> > > * (15: 0): TLB VUGID / ACLID
> > >
> > > So, one basically does associative checks between the entries in the
> > > ACLE cache, and the entries in KRR.
> > >
> > > Because KRR changes relatively infrequently, the ACLE can be pretty
> > > small (ideally, it is larger than the KRR though, so 6 or 8 entries
> > > would be better than 4, but I am using 4 entries for now).
> > >
> > >
> > > The combined result of VUGID/ACL, and Basic checks are combined into a
> > > single bit-mask saying what access is allowed (in a given operating mode
> > > and at a given time). The L1 Caches will use these bits during memory
> > > access.
> > > > In my PTE eight bits are used for access control to indicate read/write/execute/cache
> > > > for either user or system. Maybe these bits would be better used to refer to an ACL. If
> > > > I were to trim four bits off the page number fields that means a 16-bit ACL reference
> > > > field could be supported.
> > > OK.
> > >
> > > I was able to fit both Basic checks and ACL/VUGID checks.
> > >
> > > The Basic checks are used ye olde User/Supervisor and similar (R/W/X)
> > > and a few bits which effects caching or combinations which are used
> > > encode alternate special behaviors (Privledged-Execute and
> > > Execute-As-ACLID).
> > >
> > >
> > > ...
> > I cannot quite get my head around how the ACL comes into play, but I have provided for
> > an ACL in TLBE.
> >
> > I decided to use 160-bit PTEs. I really wanted to support at least a full 76-bit virtual
> > address translation and things just would not fit into a 128-bit PTE. For a hashed table
> > this works just fine. Six are packed into 1024 bit with 64-bits to spare. However, for a
> > hierarchical table 160-bit PTEs are bit nightmarish.
> <
> My 66000 has 63-bit virtual address translates into a 66-bit universal address {hint:
> MMI/O, Configuration, and ROM are not part of the 64-bit DRAM address space}.
> Yet I fit each PTP and PTE into one (1) 64-bit container, and I can skip levels in the
> tables so small applications (like cat) can fit in 23-bit virtual address and have 1
> layer of PTPs and 1 layer of PTEs. I even have bits left over......
> <
> What is driving force for 76-bit virtual address ?
> <
> Secondly, even with a 76-bit virtual address, you should only be needing 90-bits±
> for a PTE. Seems to me that the structure of you PTE needs rethought.
> <
> So, what is the structure of your PTE ?
> <
> > Just thinking to myself here. Since 160-bit PTEs do not pack a power of two into a
> > memory page, that means either increasing the PTE size to 256 bits wasting a lot of
> > space, Or doing a high-speed divide by a constant to calculate the page and entry number
> > within a page. How practical is the high-speed divide? 204 PTEs will fit into a 4096-byte
> > page. That means dividing the address by 204 instead of 256 to find the page number.
> > This divide can be done as a multiply by constant reciprocal. 204**-1 * 4096 = 20. 12 bits
> > was chosen to have a few extra bits of precision for the remainder. So, take the address
> > multiply by 20 then shift right 12 times to get the page number. Multiply by 20 was
> <
> Notice that multiply by 20 = 4×5 so the only multiply is by 5, then shift up by 4 and down by 12
> (or just down by 8).
> <
> > chosen also because its relatively painless to do. Then compute the entry number as the
> > remainder. Multiply the quotient by 204 and subtract it from the original address to get the
> > entry number. Example: entry #7000 = 20*7000 = 140000. 140000 >> 12 = 34 which is the
> > page number. 34 * 204 = 6936. 7000-6936 = 64. So, entry 64 in page 34 is the desired
> > entry. Multiply by 204=multiply by 128 + multiply by 64 + multiply by 8 which is just shifting
> > plus a 3- entry adder. Seems straightforward enough. The question is, should it be done?
> <
> Seems to be addressing the first 2 question should come before this one.
> >
> > TLB entries are much larger, 224 bits now. They include the PTE plus a 32-bit access key
> > from the access rights table and a 32-bit access counter. The access counter is used by
> > the clock algorithm which is implemented in hardware. The TLB entry gets read and written
> > with every access, so I figured it may as well be updating a counter at the same time.
> > Another hardware state machine takes care of aging the counters.
> <
> Why is the access key in the PTE?--it should be a part of the page itself..
> <
> Seems to me you are putting useful things in the wrong places.

On Saturday, March 12, 2022 at 9:36:59 PM UTC-6, robf...@gmail.com wrote:
> On Saturday, March 12, 2022 at 9:44:17 PM UTC-5, MitchAlsup wrote:
> > On Saturday, March 12, 2022 at 8:30:44 PM UTC-6, robf...@gmail.com wrote:

> > <
> > My 66000 has 63-bit virtual address translates into a 66-bit universal address {hint:
> > MMI/O, Configuration, and ROM are not part of the 64-bit DRAM address space}.
> > Yet I fit each PTP and PTE into one (1) 64-bit container, and I can skip levels in the
> > tables so small applications (like cat) can fit in 23-bit virtual address and have 1
> > layer of PTPs and 1 layer of PTEs. I even have bits left over......
> > <
> > What is driving force for 76-bit virtual address ?
> > <
> > Secondly, even with a 76-bit virtual address, you should only be needing 90-bits±
> > for a PTE. Seems to me that the structure of you PTE needs rethought.
> > <
> > So, what is the structure of your PTE ?
> > <
> > > Just thinking to myself here. Since 160-bit PTEs do not pack a power of two into a
> > > memory page, that means either increasing the PTE size to 256 bits wasting a lot of
> > > space, Or doing a high-speed divide by a constant to calculate the page and entry number
> > > within a page. How practical is the high-speed divide? 204 PTEs will fit into a 4096-byte
> > > page. That means dividing the address by 204 instead of 256 to find the page number.
> > > This divide can be done as a multiply by constant reciprocal. 204**-1 * 4096 = 20. 12 bits
> > > was chosen to have a few extra bits of precision for the remainder. So, take the address
> > > multiply by 20 then shift right 12 times to get the page number. Multiply by 20 was
> > <
> > Notice that multiply by 20 = 4×5 so the only multiply is by 5, then shift up by 4 and down by 12
> > (or just down by 8).
> > <
> > > chosen also because its relatively painless to do. Then compute the entry number as the
> > > remainder. Multiply the quotient by 204 and subtract it from the original address to get the
> > > entry number. Example: entry #7000 = 20*7000 = 140000. 140000 >> 12 = 34 which is the
> > > page number. 34 * 204 = 6936. 7000-6936 = 64. So, entry 64 in page 34 is the desired
> > > entry. Multiply by 204=multiply by 128 + multiply by 64 + multiply by 8 which is just shifting
> > > plus a 3- entry adder. Seems straightforward enough. The question is, should it be done?
> > <
> > Seems to be addressing the first 2 question should come before this one..
> > >
> > > TLB entries are much larger, 224 bits now. They include the PTE plus a 32-bit access key
> > > from the access rights table and a 32-bit access counter. The access counter is used by
> > > the clock algorithm which is implemented in hardware. The TLB entry gets read and written
> > > with every access, so I figured it may as well be updating a counter at the same time.
> > > Another hardware state machine takes care of aging the counters.
> > <
> > Why is the access key in the PTE?--it should be a part of the page itself.
> > <
> > Seems to me you are putting useful things in the wrong places.
>
> > What is driving force for 76-bit virtual address ?
> I am not quite sure why 76 bits, but my gut tells me that may not be enough. Emulating quantum
> and molecular computers? IDK. It does allow the memory allocator to just keep travelling forwards.
> The physical address needs to be stored in the PTE too. That and the virtual address take over 100
> bits. Add in the ASID and a few access control bits and there is no room left for the future.
> > So, what is the structure of your PTE ?
> The PTE contains mainly the address translation.
> Structure contains:
> PPN, (52 bits)
> VPN, (64 bits)
> ASID (12 bits)
> Global translation bit
> Valid bit
> Dirty bit
> Page size bit
> Read / Write / Execute / Cacheble bits for system and user modes (8 bits)
> Bounce count (6 bits) (for inverted page table defrag)
> 15 bits unused.
<
My 66000 Page Pointer {either a PTP or a PTE}
<
PPN<63..13>
RWE<12..10>
LVL<9..7>
Where<6..5> {L1, L2, allocated, unCacheable}
used<2>
mod<1>
present<0>
<
LVL = 001 means PTE, otherwise PTP
LVL on the pointer to PTE indicates size of the page
<
A PTE to an unCacheable page uses where<6..5> as the space of access
......{DRAM, MMI/O, Configuration, ROM} all which can be 64-bits.
<
ASID comes from a thread control register
My 66000 supports translation indirection so a service provider can access
into the service caller--this gets rid of any need for Global/Application or s/u
<
VPN is used to access PPN so it is stored in TLB but is not part of page pointing.
Pages larger than smallest, use the PPN field to enumerate the number of pages
this super page pointer points at. So, if you have a 8MB translation you can set
it up to contain 1MB if that is what is really needed.
<
There are 2 tables of translation, one used by Guest OS, the other used by
HyperVisor as a nested page table.
<
> > Why is the access key in the PTE?--it should be a part of the page itself.
<
I don't use a keyed protection scheme. I could work one in, but I would associate
each page with a key, and place the key in the thread control registers.
<
> The access key is not in the PTE. It does appear the TLB entry though along with an access
> counter. I have another table called ART that contains the access key, share count, privilege
> level and few other bits. Bits for which there is only a single copy per page. The ART is managed
> by software. Bits from ART are loaded automatically into the TLBE when needed.
<
> > Seems to me you are putting useful things in the wrong places.
<
> I have been studying MMUs on the web with the hopes of sorting things out.. Most of them do
> not include as much information in the PTE / TLBE or use smaller fields. To me it looks like
> some are legacy designs, inheriting from 32-bit perhaps. I have not found much mentioned
> about what to do with the per page information.
<
Almost everything you find on the web has been damaged by some kind of association
with x86 or other 32-bit MMUs.
<
> My design is using 128-bit registers, mainly to support quad precision 128-bit decimal floating-
> point.
<
How big is you int, your long, and your pointer ?

On 3/12/2022 8:44 PM, MitchAlsup wrote:
> On Saturday, March 12, 2022 at 8:30:44 PM UTC-6, robf...@gmail.com wrote:
>> On Friday, March 11, 2022 at 12:46:33 AM UTC-5, BGB wrote:
>>> On 3/10/2022 7:58 PM, robf...@gmail.com wrote:
>>>> On Thursday, March 10, 2022 at 1:15:31 PM UTC-5, BGB wrote:
>>>>> On 3/10/2022 9:04 AM, robf...@gmail.com wrote:
>>>>>> On Wednesday, March 9, 2022 at 12:37:26 PM UTC-5, BGB wrote:
>>>>>>> On 3/9/2022 10:20 AM, EricP wrote:
>>>>>>
>>>>>>>> Note that operating systems such as Linux the hierarchical page table is
>>>>>>>> part of its design. To port it to Power with its hash/inverted page table
>>>>>>>> they kept the hierarchical table managed in memory as before,
>>>>>>>> and move valid PTE entries into and out of the hash table.
>>>>>>>>
>>>>>>>> In effect, the hierarchical table is still the OS page table,
>>>>>>>> and the hash table is treated like a giant software managed TLB.
>>>>>>>> Software could implement, say, a FIFO mechanism to rotate a working set
>>>>>>>> of Present hierarchical PTE's through hash PTE slots,
>>>>>>>> similar to how a HW TLB might rotate through its entries.
>>>>>>>>
>>>>>>>> In this arrangement, Address Space ID's (ASID) for the hash table entries
>>>>>>>> would be very important for efficiency, as without them a process switch
>>>>>>>> would require invalidating all hash table entries just like a real TLB.
>>>>>>>>
>>>>>> Seems kind of kludgy. I am wondering why now this approach was used.
>>>>>>
>>>>>> I have coded in the bus interface unit the capability to use either hashed or
>>>>>> hierarchical page tables. I was not so insane as to ignore the popularity of
>>>>>> hierarchical page tables. Can probably use both types at the same time.
>>>>>> Hashed tables are a better way to go for a large address
>>>>>> space in my opinion. They use less memory and may have faster look-ups.
>>>>>>
>>>>> Hashed tables could also make sense as an alternative to B-Trees.
>>>>>
>>>>> A B-Tree lookup is likely to be relatively complicated and expensive if
>>>>> compared to a hash lookup.
>>>>>
>>>>> It is possible that I could also combine a hashed top-level with
>>>>> 2-levels of nested page table (optionally collapsing down the upper 6
>>>>> levels into a single page).
>>>>>>
>>>>>>> OK. This gives more context for what I was confused about in my response.
>>>>>>>
>>>>>>> In my case, I use a software managed TLB, with hierarchical page tables,
>>>>>>> and no sort of intermediate stage representation.
>>>>>>>
>>>>>>> TLB miss interrupt occurs, handler walks the page table, and loads the
>>>>>>> resulting entry into the TLB. Basic design for the mechanism was
>>>>>>> more-or-less lifted from SH-4, but with the major difference of going
>>>>>>> from a 64-entry fully associative TLB to a 64x or 256x 4-way TLB.
>>>>>>>
>>>>>>> Arguably, a 6-way or 8-way TLB could be better, but more expensive.
>>>>>>>
>>>>>>>
>>>>>>> I had considered potentially using B-Trees for the upper levels (instead
>>>>>>> of hierarchical nesting) for the 96-bit mode, mostly because as-is this
>>>>>>> leads to a "very sparse" 8-level table, and a B-Tree could be more
>>>>>>> compact (with more traditional nested page tables for the lower 2 or 3
>>>>>>> levels).
>>>>>>>
>>>>>>> Though, there are other (potentially simpler/cheaper) ways to deal with
>>>>>>> this.
>>>>>>>
>>>>>>> This would not really effect the hardware in my case.
>>>>>>
>>>>>> Page tables are walked via hardware for Thor. Software only gets involved on a
>>>>>> page fault. While software managing the TLB is probably comparable in
>>>>>> performance and more flexible than hardware, TLB updates with hardware
>>>>>> walking are almost invisible to software.
>>>>>>
>>>>> This was one annoyance with BJX2 with the use of software managed TLB:
>>>>> Getting the software TLB miss interrupts stable was a major source of
>>>>> annoyance, as there were a whole lot of "little things" that can go
>>>>> wrong in these mechanisms.
>>>>>
>>>>> The L1 caches needing to be able to stop what they are doing, then
>>>>> quietly transfer control to an ISR, then resume normal operation without
>>>>> any adverse side effects, was a bit of a pain to debug.
>>>>>
>>>>> Some of the cases were infrequent, so one might to get Doom or Quake
>>>>> launched (in a simulation) before the crash happens, where firing these
>>>>> up inside a Verilog simulation is not exactly a fast process (the time
>>>>> issue is also a major reason why I am using LZ compressed binaries and
>>>>> WADs).
>>>>>
>>>>>
>>>>> As noted, the MMU is temporarily disabled within ISRs, partly because
>>>>> there is no way for an ISR to deal with a TLB miss (unlike some CPU
>>>>> architectures, ISRs are not re-entrant in my case).
>>>>>
>>>>>
>>>>> Similarly, the TLB miss handler would have to resolve page-fault
>>>>> scenarios (for virtual memory), without access to the main filesystem
>>>>> driver (it has to bypass the driver and access the SDCard directly), but
>>>>> does also mean that a page fault (to virtual memory) during some other
>>>>> SDcard IO request would be "potentially fatal".
>>>>>
>>>>> ...
>>>>>
>>>>> Nevermind whether or not it makes sense to put a pagefile on an SDcard,
>>>>> there is nowhere else to put it in this case.
>>>>>
>>>>>
>>>>> What to do with a page-fault to an unmapped address (eg: not backed to
>>>>> the page file) is currently an unresolved issue, but this is more a
>>>>> software thing than a hardware thing (in a real OS, would probably
>>>>> terminate the process or similar here; for the time being, the only real
>>>>> solution is to trigger a breakpoint).
>>>>>
>>>>> I may need to consider going and adding preemptive multitasking, as it
>>>>> looks like most "real OS" stuff would depend on this (cooperative
>>>>> multitasking doesn't scale particularly well, or leave any real good
>>>>> solution for "OK, this program has gone into an infinite loop or
>>>>> crashed", which basically leaves no real solution otherwise).
>>>>>
>>>>>
>>>>>
>>>>> The debugging was getting bad enough that I almost started to debate
>>>>> whether it would be worthwhile to add hardware page walking and not have
>>>>> to deal with this as much (but would still need a Page Fault handler, so
>>>>> it is not entirely avoidable).
>>>>>
>>>>>
>>>>> Sorta spent most of February beating on trying to debug stuff related to
>>>>> the L1 Caches and their interaction with the TLB Miss ISR, partly as
>>>>> "poking at something" in the L1 D$ set off an unholy bees nest of bugs.
>>>>>
>>>>> Likewise, much of my past debugging effort here was more focused on
>>>>> "quick and dirty" fixes which typically don't really resolve the
>>>>> underlying issues; but, trying to figure out "why" something is going
>>>>> wrong is often a lot harder than adding "make it work" hacks (and then
>>>>> notice the bug hasn't gone away, it has merely moved to a new location).
>>>>>
>>>>>
>>>>> I still can't say (with much confidence) that the TLB is now stable, but
>>>>> in my testing at the moment, it appears to work.
>>>>>
>>>>> Though, this debugging effort wasn't helped with Verilator also having
>>>>> the annoying behavior that adding and removing $display statements can
>>>>> sometimes change the behavior of the logic...
>>>>>> The TLB can be updated via software, its almost possible then to use a software
>>>>>> managed TLB. I guess if the TLB miss signal were fed into the interrupt system,
>>>>>> then maybe things could have the option of software management.
>>>>>>
>>>>> Could be.
>>>>>
>>>>> In my case, TLB miss triggers an interrupt, and the ISR deals with it.
>>>>>
>>>>> In the ISR, there is a 'TEA' register that holds the address of whatever
>>>>> caused the interrupt (target address for TLB miss), and an 'EXSR'
>>>>> register where the low bits encode which interrupt had occurred (as a
>>>>> 16-bit number divided into multiple bit fields).
>>>>>> I get the feeling there are too many choices available in Thor. Maybe a configuration
>>>>>> utility would be better than building in everything.
>>>>>>
>>>>>> Wondering what entity to place share counts, access keys, and privilege levels in. I
>>>>>> had these in the PTE but took them out. There is only one set required for each page
>>>>>> of memory.
>>>>>>
>>>>> I have this stuff in the PTEs/TLBEs.
>>>>>
>>>>> There is also an ACL Cache with an ACL Miss interrupt as well.
>>>>>
>>>>> The software side of things isn't really developed all that well yet, as
>>>>> most of the time thus far had gone more into trying to get things stable
>>>>> enough that the address translation and TLB miss interrupts weren't
>>>>> prone to crash stuff.
>>>>>
>>>>> I seem to have this part stable now, so now it should be possible to
>>>>> start making forward progress in this area.
>>>>
>>>> For Thor, the TLBE / PTE is 128-bits in size with no room to spare without having the
>>>> share-counts, etc. included in it. A larger PTE would really complicate things.
>>>> The TLBE value can be loaded or stored from / to the TLB using a single
>>>> 128-bit wide register. Anything wider means using a pair of registers. I could
>>>> maybe reduce the size of the page number fields a few bits. The fields are 48-bit.
>>>> I had the thought that since there only needs to be one copy of the information it
>>>> could be stored in another entity. But this means potentially adding to the memory
>>>> access time since another table is accessed after the physical page number is
>>>> known.
>>>>
>>> I also have 128-bit TLBE's, with fields for 48 bit addresses.
>>>
>>> Though the address fields are actually 36 bits, because one can cut off
>>> the low-order bits for the address (and because the "base form"
>>> addressing is 48-bit).
>>>
>>> While there is a 96-bit virtual-address mode, as noted, it works by
>>> using TLBE's in pairs to get more bits (at the cost of associativity).
>>> It mostly just extends the virtual address by 48 bits, with most of the
>>> rest of the bits being unused.
>>>
>>> I ended up implementing the 256-bit TLB load via a "double pumping"
>>> strategy (load both halves and then the MMU sticks them together).
>>>
>>>
>>>
>>> Would be a little bit harder with a full 64-bit virtual address space
>>> though.
>>>
>>>
>>> Copy/Paste
>>>
>>> TLBE:
>>> * (127:112) = VUGID / ACLID
>>> * (111: 76) = Virtual Address Page
>>> * ( 75: 64) = KR Access
>>> * ( 63: 48) = ASID
>>> * ( 47: 12) = Physical Address Page
>>> * ( 11: 0) = Page Control bits
>>>
>>> VUGID:
>>> * (15:10) = VGID / VUID(Swap)
>>> * ( 9: 0) = VUID / VGID(Swap)
>>> * May be interpreted as a PID or ACLID.
>>> ** In these cases, VUGID is treated as a single 16-bit unit.
>>>
>>> ASID:
>>> * (15:10) = AGID (0=Shared, Global)
>>> * ( 9: 0) = APID (0=Shared, Group)
>>>
>>> KR Access:
>>> * (11): Other X
>>> * (10): Other W
>>> * ( 9): Other R
>>> * ( 8): Group X (VUGID Check Only)
>>> * ( 7): Group W (VUGID Check Only)
>>> * ( 6): Group R (VUGID Check Only)
>>> * ( 5): User X (VUGID Check Only)
>>> * ( 4): User W (VUGID Check Only)
>>> * ( 3): User R (VUGID Check Only)
>>> * ( 2): VUGID Mode 2
>>> * ( 1): VUGID Mode 1
>>> * ( 0): VUGID Mode 0
>>>
>>> The VUGID Mode bits basically encode what sort of check to perform
>>> (VUGID or ACL style).
>>>
>>>
>>> These include, say:
>>> Disabled, VUGID, VUGID (Swap), or ACL.
>>>
>>> In VUGID mode, it does User/Group/Other checks, Swap switches
>>> User/Group. ACL: Use ACL (in TLBE), Exact 16-bit match only (ACLE).
>>>> I do not know much about ACL except that I suspect it can be quite complicated to do
>>>> with hardware. Is there ACL for individual pages of memory? There can be users or
>>>> groups of users and system processes all with separate access requirements. I suspect
>>>> there would be some limits engineered into ACL. For instance, limited numbers of
>>>> groups and users to keep the reference fields a reasonable size. Can you elaborate on
>>>> the ACL?
>>>>
>>> These are per-page checks.
>>>
>>>
>>> The ACL checking doesn't really add all that much cost or complexity
>>> compared with the TLB itself.
>>>
>>> Main costs are mostly the need to spend TLB bits on it, and the addition
>>> of a Keyring Register (KRR).
>>>
>>> Most of the harder parts of the ACL Check (namely, performing the ACL
>>> lookups) would be handled in software, so all the hardware really needs
>>> to do is check whether the keyring entries are in the ACL Cache, and (it
>>> they hit) what sort of access is allowed to the page in question (the
>>> access bits are OR'ed together).
>>>
>>>
>>> ACLE:
>>> * (63:44): Reserved / MBZ
>>> * (43:32): KR Access Mode
>>> * (31:16): KRR VUGID / APID
>>> * (15: 0): TLB VUGID / ACLID
>>>
>>> So, one basically does associative checks between the entries in the
>>> ACLE cache, and the entries in KRR.
>>>
>>> Because KRR changes relatively infrequently, the ACLE can be pretty
>>> small (ideally, it is larger than the KRR though, so 6 or 8 entries
>>> would be better than 4, but I am using 4 entries for now).
>>>
>>>
>>> The combined result of VUGID/ACL, and Basic checks are combined into a
>>> single bit-mask saying what access is allowed (in a given operating mode
>>> and at a given time). The L1 Caches will use these bits during memory
>>> access.
>>>> In my PTE eight bits are used for access control to indicate read/write/execute/cache
>>>> for either user or system. Maybe these bits would be better used to refer to an ACL. If
>>>> I were to trim four bits off the page number fields that means a 16-bit ACL reference
>>>> field could be supported.
>>> OK.
>>>
>>> I was able to fit both Basic checks and ACL/VUGID checks.
>>>
>>> The Basic checks are used ye olde User/Supervisor and similar (R/W/X)
>>> and a few bits which effects caching or combinations which are used
>>> encode alternate special behaviors (Privledged-Execute and
>>> Execute-As-ACLID).
>>>
>>>
>>> ...
>> I cannot quite get my head around how the ACL comes into play, but I have provided for
>> an ACL in TLBE.
>>
>> I decided to use 160-bit PTEs. I really wanted to support at least a full 76-bit virtual
>> address translation and things just would not fit into a 128-bit PTE. For a hashed table
>> this works just fine. Six are packed into 1024 bit with 64-bits to spare. However, for a
>> hierarchical table 160-bit PTEs are bit nightmarish.
> <
> My 66000 has 63-bit virtual address translates into a 66-bit universal address {hint:
> MMI/O, Configuration, and ROM are not part of the 64-bit DRAM address space}.
> Yet I fit each PTP and PTE into one (1) 64-bit container, and I can skip levels in the
> tables so small applications (like cat) can fit in 23-bit virtual address and have 1
> layer of PTPs and 1 layer of PTEs. I even have bits left over......
> <
> What is driving force for 76-bit virtual address ?
> <
> Secondly, even with a 76-bit virtual address, you should only be needing 90-bits±
> for a PTE. Seems to me that the structure of you PTE needs rethought.
> <
> So, what is the structure of your PTE ?
> <

MitchAlsup wrote:
> On Saturday, March 12, 2022 at 9:36:59 PM UTC-6, robf...@gmail.com wrote:
>> I am not quite sure why 76 bits, but my gut tells me that may not be enough. Emulating quantum
>> and molecular computers? IDK. It does allow the memory allocator to just keep travelling forwards.
>> The physical address needs to be stored in the PTE too. That and the virtual address take over 100
>> bits. Add in the ASID and a few access control bits and there is no room left for the future.
>>> So, what is the structure of your PTE ?
>> The PTE contains mainly the address translation.
>> Structure contains:
>> PPN, (52 bits)
>> VPN, (64 bits)
>> ASID (12 bits)
>> Global translation bit
>> Valid bit
>> Dirty bit
>> Page size bit
>> Read / Write / Execute / Cacheble bits for system and user modes (8 bits)
>> Bounce count (6 bits) (for inverted page table defrag)
>> 15 bits unused.
> <
> My 66000 Page Pointer {either a PTP or a PTE}
> <
> PPN<63..13>
> RWE<12..10>
> LVL<9..7>
> Where<6..5> {L1, L2, allocated, unCacheable}
> used<2>
> mod<1>
> present<0>

You need 3 bits explicitly reserved to OS in a Present pte.
The OS will store status tracking info in those bits.
(In a Not-Present pte all of the other 63 bits are owned by OS
and its shashes all kinds of info in there.)

> <
> LVL = 001 means PTE, otherwise PTP
> LVL on the pointer to PTE indicates size of the page
> <
> A PTE to an unCacheable page uses where<6..5> as the space of access
> ......{DRAM, MMI/O, Configuration, ROM} all which can be 64-bits.
> <
> ASID comes from a thread control register
> My 66000 supports translation indirection so a service provider can access
> into the service caller--this gets rid of any need for Global/Application or s/u
> <
> VPN is used to access PPN so it is stored in TLB but is not part of page pointing.
> Pages larger than smallest, use the PPN field to enumerate the number of pages
> this super page pointer points at. So, if you have a 8MB translation you can set
> it up to contain 1MB if that is what is really needed.
> <
> There are 2 tables of translation, one used by Guest OS, the other used by
> HyperVisor as a nested page table.
> <
>>> Why is the access key in the PTE?--it should be a part of the page itself.
> <
> I don't use a keyed protection scheme. I could work one in, but I would associate
> each page with a key, and place the key in the thread control registers.
> <
>> The access key is not in the PTE. It does appear the TLB entry though along with an access
>> counter. I have another table called ART that contains the access key, share count, privilege
>> level and few other bits. Bits for which there is only a single copy per page. The ART is managed
>> by software. Bits from ART are loaded automatically into the TLBE when needed.
> <
>>> Seems to me you are putting useful things in the wrong places.
> <
>> I have been studying MMUs on the web with the hopes of sorting things out.. Most of them do
>> not include as much information in the PTE / TLBE or use smaller fields. To me it looks like
>> some are legacy designs, inheriting from 32-bit perhaps. I have not found much mentioned
>> about what to do with the per page information.

The hierarchical page tables also have an array of structs indexed by
Physical Page Number (PPN) that stores the OS defined status info.
In Linux this called "struct page".

Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
is open access, available on-line in HTML or as PDF's.
https://www.kernel.org/doc/gorman/html/understand
https://www.kernel.org/doc/gorman/pdf

Description of "struct page" descriptor:

2.4 Pages
https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15

On 3/13/2022 1:18 PM, EricP wrote:
> MitchAlsup wrote:
>> On Saturday, March 12, 2022 at 9:36:59 PM UTC-6, robf...@gmail.com wrote:
>>> I am not quite sure why 76 bits, but my gut tells me that may not be
>>> enough. Emulating quantum and molecular computers? IDK. It does allow
>>> the memory allocator to just keep travelling forwards. The physical
>>> address needs to be stored in the PTE too. That and the virtual
>>> address take over 100 bits. Add in the ASID and a few access control
>>> bits and there is no room left for the future.
>>>> So, what is the structure of your PTE ?
>>> The PTE contains mainly the address translation. Structure contains:
>>> PPN, (52 bits) VPN, (64 bits) ASID (12 bits) Global translation bit
>>> Valid bit Dirty bit Page size bit Read / Write / Execute / Cacheble
>>> bits for system and user modes (8 bits) Bounce count (6 bits) (for
>>> inverted page table defrag) 15 bits unused.
>> <
>> My 66000 Page Pointer {either a PTP or a PTE}
>> <
>> PPN<63..13>
>> RWE<12..10>
>> LVL<9..7>
>> Where<6..5>     {L1, L2, allocated, unCacheable}
>> used<2>
>> mod<1>
>> present<0>
>
> You need 3 bits explicitly reserved to OS in a Present pte.
> The OS will store status tracking info in those bits.
> (In a Not-Present pte all of the other 63 bits are owned by OS
> and its shashes all kinds of info in there.)
>

I have 4 "User" bits in my case, mostly intended to be used for
implementing virtual memory and similar.

For non-present pages, one may want to encode whether or not the address
bits encode an index into the pagefile, ...

The low 2 bits encode a page mode:
00: Not Present
01: Present, Exclusive
10: High Half (Of an XTLB 2-part TLBE)
11: Present, Shared

>> <
>> LVL = 001 means PTE, otherwise PTP
>> LVL on the pointer to PTE indicates size of the page
>> <
>> A PTE to an unCacheable page uses where<6..5> as the space of access
>> ......{DRAM, MMI/O, Configuration, ROM} all which can be 64-bits.
>> <
>> ASID comes from a thread control register
>> My 66000 supports translation indirection so a service provider can
>> access
>> into the service caller--this gets rid of any need for
>> Global/Application or s/u
>> <
>> VPN is used to access PPN so it is stored in TLB but is not part of
>> page pointing.
>> Pages larger than smallest, use the PPN field to enumerate the number
>> of pages
>> this super page pointer points at. So, if you have a 8MB translation
>> you can set
>> it up to contain 1MB if that is what is really needed.
>> <
>> There are 2 tables of translation, one used by Guest OS, the other
>> used by
>> HyperVisor as a nested page table.
>> <
>>>> Why is the access key in the PTE?--it should be a part of the page
>>>> itself.
>> <
>> I don't use a keyed protection scheme. I could work one in, but I
>> would associate
>> each page with a key, and place the key in the thread control registers.
>> <
>>> The access key is not in the PTE. It does appear the TLB entry though
>>> along with an access counter. I have another table called ART that
>>> contains the access key, share count, privilege level and few other
>>> bits. Bits for which there is only a single copy per page. The ART is
>>> managed by software. Bits from ART are loaded automatically into the
>>> TLBE when needed.
>> <
>>>> Seems to me you are putting useful things in the wrong places.
>> <
>>> I have been studying MMUs on the web with the hopes of sorting things
>>> out.. Most of them do not include as much information in the PTE /
>>> TLBE or use smaller fields. To me it looks like some are legacy
>>> designs, inheriting from 32-bit perhaps. I have not found much
>>> mentioned about what to do with the per page information.
>
> The hierarchical page tables also have an array of structs indexed by
> Physical Page Number (PPN) that stores the OS defined status info.
> In Linux this called "struct page".
>
> Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> is open access, available on-line in HTML or as PDF's.
> https://www.kernel.org/doc/gorman/html/understand
> https://www.kernel.org/doc/gorman/pdf
>
> Description of "struct page" descriptor:
>
> 2.4 Pages
> https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
>
>

Hmm, I had merely been tracking (low-level) page status with bitmaps and
rovers...

Things like mmaps were handled instead using sorted arrays assigned to
the virtual address space, which would represent the mmaps in terms of
spans.

Things like pagefile have a struct for each page in the region that can
be mapped into the pagefile.

This struct appears superficially similar to the one in the linked page,
but differs some in that it uses index numbers rather than pointers for
things like hash chaining and LRU.

It is possible that another difference is that I am currently only
reserving a fairly modest part of the address space for use by "pagefile
backed memory", whereas Linux throws most of its RAM at this (operating
primarily out of virtual memory).

Though, this latter point may change if I switch programs over to using
virtual memory as their primary backing memory.

I may be reaching the point where I can start experimenting with moving
the userland over pagefile backed memory. If this works, I could
probably get by with throwing, say, 50 or 75% of the RAM space at this
problem (the remaining RAM being mostly non-pagefile memory, either
physically-mapped or direct-remapping, *).

*: Where the physical address is remapped to a new location, but it
functions more like a conventional allocation, and is not backed by the
pagefile.

Current virtual memory layout is currently something like:
0000_00000000..0000_00FFFFFF: NULL Region (Unmapped)
0000_01000000..0000_3FFFFFFF: Physical Map (DRAM and similar).
0000_40000000..0000_BFFFFFFF: Low Virtual, Direct Mappings
0000_C0000000..0000_EFFFFFFF: Unused for now
0000_F0000000..0000_FFFFFFFF: Low MMIO Range
0001_00000000..7FFF_FFFFFFFF: High Virtual, Pagefile Backed

Not currently using 96-bit addressing.

So, basic idea being for now that everything using pagefile backed
memory will go into virtual addresses above the 4GB mark.

This would need to be different to support programs built with 32-bit
pointers, but even with a pagefile, these would be reasonably cramped in
an a shared address space.

Say:
0000_40000000..0000_7FFFFFFF: Low Virtual, Direct Mappings
0000_80000000..0000_BFFFFFFF: Low Virtual, Pagefile Backed

With all of the processes using 32-bit pointers mostly needing to fit
within a shared 1GB or 2GB of address space, and thus not much better
than in a NOMMU situation.

....

On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> MitchAlsup wrote:

> The hierarchical page tables also have an array of structs indexed by
> Physical Page Number (PPN) that stores the OS defined status info.
> In Linux this called "struct page".
>
> Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> is open access, available on-line in HTML or as PDF's.
> https://www.kernel.org/doc/gorman/html/understand
> https://www.kernel.org/doc/gorman/pdf
>
> Description of "struct page" descriptor:
>
> 2.4 Pages
> https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
<
Is there something equivalent to this with
a) 64-bit virtual-physical addresses
b) nested page tables

On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> MitchAlsup wrote:
> > On Saturday, March 12, 2022 at 9:36:59 PM UTC-6, robf...@gmail.com wrote:
> >> I am not quite sure why 76 bits, but my gut tells me that may not be enough. Emulating quantum
> >> and molecular computers? IDK. It does allow the memory allocator to just keep travelling forwards.
> >> The physical address needs to be stored in the PTE too. That and the virtual address take over 100
> >> bits. Add in the ASID and a few access control bits and there is no room left for the future.
> >>> So, what is the structure of your PTE ?
> >> The PTE contains mainly the address translation.
> >> Structure contains:
> >> PPN, (52 bits)
> >> VPN, (64 bits)
> >> ASID (12 bits)
> >> Global translation bit
> >> Valid bit
> >> Dirty bit
> >> Page size bit
> >> Read / Write / Execute / Cacheble bits for system and user modes (8 bits)
> >> Bounce count (6 bits) (for inverted page table defrag)
> >> 15 bits unused.
> > <
> > My 66000 Page Pointer {either a PTP or a PTE}
> > <
> > PPN<63..13>
> > RWE<12..10>
> > LVL<9..7>
> > Where<6..5> {L1, L2, allocated, unCacheable}
> > used<2>
> > mod<1>
> > present<0>
<
> You need 3 bits explicitly reserved to OS in a Present pte.
<
What are these 3-bits used for?
<
> The OS will store status tracking info in those bits.
<
What kind of status/tracking?
<
> (In a Not-Present pte all of the other 63 bits are owned by OS
> and its shashes all kinds of info in there.)
<
Sure
<
> > <
> > LVL = 001 means PTE, otherwise PTP
> > LVL on the pointer to PTE indicates size of the page
> > <
> > A PTE to an unCacheable page uses where<6..5> as the space of access
> > ......{DRAM, MMI/O, Configuration, ROM} all which can be 64-bits.
> > <
> > ASID comes from a thread control register
> > My 66000 supports translation indirection so a service provider can access
> > into the service caller--this gets rid of any need for Global/Application or s/u
> > <
> > VPN is used to access PPN so it is stored in TLB but is not part of page pointing.
> > Pages larger than smallest, use the PPN field to enumerate the number of pages
> > this super page pointer points at. So, if you have a 8MB translation you can set
> > it up to contain 1MB if that is what is really needed.
> > <
> > There are 2 tables of translation, one used by Guest OS, the other used by
> > HyperVisor as a nested page table.
> > <
> >>> Why is the access key in the PTE?--it should be a part of the page itself.
> > <
> > I don't use a keyed protection scheme. I could work one in, but I would associate
> > each page with a key, and place the key in the thread control registers.
> > <
> >> The access key is not in the PTE. It does appear the TLB entry though along with an access
> >> counter. I have another table called ART that contains the access key, share count, privilege
> >> level and few other bits. Bits for which there is only a single copy per page. The ART is managed
> >> by software. Bits from ART are loaded automatically into the TLBE when needed.
> > <
> >>> Seems to me you are putting useful things in the wrong places.
> > <
> >> I have been studying MMUs on the web with the hopes of sorting things out.. Most of them do
> >> not include as much information in the PTE / TLBE or use smaller fields. To me it looks like
> >> some are legacy designs, inheriting from 32-bit perhaps. I have not found much mentioned
> >> about what to do with the per page information.
> The hierarchical page tables also have an array of structs indexed by
> Physical Page Number (PPN) that stores the OS defined status info.
> In Linux this called "struct page".
>
> Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> is open access, available on-line in HTML or as PDF's.
> https://www.kernel.org/doc/gorman/html/understand
> https://www.kernel.org/doc/gorman/pdf
>
> Description of "struct page" descriptor:
>
> 2.4 Pages
> https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15

On Sunday, March 13, 2022 at 4:09:16 PM UTC-4, MitchAlsup wrote:
> On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> > MitchAlsup wrote:
> > > On Saturday, March 12, 2022 at 9:36:59 PM UTC-6, robf...@gmail.com wrote:
> > >> I am not quite sure why 76 bits, but my gut tells me that may not be enough. Emulating quantum
> > >> and molecular computers? IDK. It does allow the memory allocator to just keep travelling forwards.
> > >> The physical address needs to be stored in the PTE too. That and the virtual address take over 100
> > >> bits. Add in the ASID and a few access control bits and there is no room left for the future.
> > >>> So, what is the structure of your PTE ?
> > >> The PTE contains mainly the address translation.
> > >> Structure contains:
> > >> PPN, (52 bits)
> > >> VPN, (64 bits)
> > >> ASID (12 bits)
> > >> Global translation bit
> > >> Valid bit
> > >> Dirty bit
> > >> Page size bit
> > >> Read / Write / Execute / Cacheble bits for system and user modes (8 bits)
> > >> Bounce count (6 bits) (for inverted page table defrag)
> > >> 15 bits unused.
> > > <
> > > My 66000 Page Pointer {either a PTP or a PTE}
> > > <
> > > PPN<63..13>
> > > RWE<12..10>
> > > LVL<9..7>
> > > Where<6..5> {L1, L2, allocated, unCacheable}
> > > used<2>
> > > mod<1>
> > > present<0>
> <
> > You need 3 bits explicitly reserved to OS in a Present pte.
> <
> What are these 3-bits used for?
> <
> > The OS will store status tracking info in those bits.
> <
> What kind of status/tracking?
> <
> > (In a Not-Present pte all of the other 63 bits are owned by OS
> > and its shashes all kinds of info in there.)
> <
> Sure
> <
> > > <
> > > LVL = 001 means PTE, otherwise PTP
> > > LVL on the pointer to PTE indicates size of the page
> > > <
> > > A PTE to an unCacheable page uses where<6..5> as the space of access
> > > ......{DRAM, MMI/O, Configuration, ROM} all which can be 64-bits.
> > > <
> > > ASID comes from a thread control register
> > > My 66000 supports translation indirection so a service provider can access
> > > into the service caller--this gets rid of any need for Global/Application or s/u
> > > <
> > > VPN is used to access PPN so it is stored in TLB but is not part of page pointing.
> > > Pages larger than smallest, use the PPN field to enumerate the number of pages
> > > this super page pointer points at. So, if you have a 8MB translation you can set
> > > it up to contain 1MB if that is what is really needed.
> > > <
> > > There are 2 tables of translation, one used by Guest OS, the other used by
> > > HyperVisor as a nested page table.
> > > <
> > >>> Why is the access key in the PTE?--it should be a part of the page itself.
> > > <
> > > I don't use a keyed protection scheme. I could work one in, but I would associate
> > > each page with a key, and place the key in the thread control registers.
> > > <
> > >> The access key is not in the PTE. It does appear the TLB entry though along with an access
> > >> counter. I have another table called ART that contains the access key, share count, privilege
> > >> level and few other bits. Bits for which there is only a single copy per page. The ART is managed
> > >> by software. Bits from ART are loaded automatically into the TLBE when needed.
> > > <
> > >>> Seems to me you are putting useful things in the wrong places.
> > > <
> > >> I have been studying MMUs on the web with the hopes of sorting things out.. Most of them do
> > >> not include as much information in the PTE / TLBE or use smaller fields. To me it looks like
> > >> some are legacy designs, inheriting from 32-bit perhaps. I have not found much mentioned
> > >> about what to do with the per page information.
> > The hierarchical page tables also have an array of structs indexed by
> > Physical Page Number (PPN) that stores the OS defined status info.
> > In Linux this called "struct page".
> >
> > Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> > is open access, available on-line in HTML or as PDF's.
> > https://www.kernel.org/doc/gorman/html/understand
> > https://www.kernel.org/doc/gorman/pdf
> >
> > Description of "struct page" descriptor:
> >
> > 2.4 Pages
> > https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15

I had forgotten the hierarchical page tables do not need to store the virtual address / ASID.
Without the VPN things will easily fit into 96 bits. Still stuck with the issue of non-power of
two addressing unless the PTE size is increased to 128-bit or bits are trimmed from the PPN.

Storing the level in the entry seems like a good idea. With extra bits available in a page, the
level could be stored there. All PTEs in the page would have the same level.. I assume the
level is for debug / integrity. Could also use the bounce count field to store the level.

I had sort of wanted to keep the same PTE format for both types of tables, but I see now it
does not make sense to do this. It would waste too much space in a hierarchical table. PDEs
are only 64-bit since they only contain a reference to page and a couple of other bits.

>How big is you int, your long, and your pointer ?

An int is 64-bits. A long is 128-bits. And a short is 32-bits. Pointers are 64-bit. The pointer size
may be adjustable. Number of address bits in use can be specified for the compile.

I added the idea of regions to the MMU which are related to the PMA checks. There may be up
to eight regions defined. Currently only four are used, ROM, IO, scratchpad, and RAM. The
‘where’ field is computed based on the physical address. The physical address looks up a
region in the region table and returns the PMA. The PMA includes memory type and accessibility.

MitchAlsup wrote:
> On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>>> <
>>> My 66000 Page Pointer {either a PTP or a PTE}
>>> <
>>> PPN<63..13>
>>> RWE<12..10>
>>> LVL<9..7>
>>> Where<6..5> {L1, L2, allocated, unCacheable}
>>> used<2>
>>> mod<1>
>>> present<0>
> <
>> You need 3 bits explicitly reserved to OS in a Present pte.
> <
> What are these 3-bits used for?
> <
>> The OS will store status tracking info in those bits.
> <
> What kind of status/tracking?

Intel in 32-bit x86 PTE defined bits 11:9 as ignored.
x64 defines 4kB 64-bit PTE defines bits 11:9, 58:52 as ignored.
There are also PTE bits that are defined as Reserved, Must Be Zero.

In Linux for x64 it defines 4 OS bits of which 3 are used:
https://01.org/blogs/dave/2020/linux-consumption-x86-page-table-bits

Windows x64 has CopyOnWrite, Prototype and Write in ignored bits.
Write is used for handling certain race conditions in managing Dirty bit.

On Sunday, March 13, 2022 at 5:19:40 PM UTC-5, robf...@gmail.com wrote:
> On Sunday, March 13, 2022 at 4:09:16 PM UTC-4, MitchAlsup wrote:
> > On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> > > MitchAlsup wrote:

> > > The hierarchical page tables also have an array of structs indexed by
> > > Physical Page Number (PPN) that stores the OS defined status info.
> > > In Linux this called "struct page".
> > >
> > > Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> > > is open access, available on-line in HTML or as PDF's.
> > > https://www.kernel.org/doc/gorman/html/understand
> > > https://www.kernel.org/doc/gorman/pdf
> > >
> > > Description of "struct page" descriptor:
> > >
> > > 2.4 Pages
> > > https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
> I had forgotten the hierarchical page tables do not need to store the virtual address / ASID.
> Without the VPN things will easily fit into 96 bits. Still stuck with the issue of non-power of
> two addressing unless the PTE size is increased to 128-bit or bits are trimmed from the PPN.
>
> Storing the level in the entry seems like a good idea. With extra bits available in a page, the
> level could be stored there. All PTEs in the page would have the same level. I assume the
> level is for debug / integrity. Could also use the bounce count field to store the level.
<
Not quite::
<
LVL of the pointer to the page of translation entries indicates the address space covered by each
entry. But, you could have a LVL = 011 indicating a 8GB page; some entries could point at an
8MB entry (LVL = 010) some could point at an 8K page (LVL=001).
<
The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
number of accesses used to refill the TLB, and the number of pages used to for translations.
<
A small program like "cat" can be compiled with a 23-bit address space and use 1 page of translation
overhead; typically with 5 entries: .text, .bss, .data, .stack, .heap.
>
> I had sort of wanted to keep the same PTE format for both types of tables, but I see now it
> does not make sense to do this. It would waste too much space in a hierarchical table. PDEs
> are only 64-bit since they only contain a reference to page and a couple of other bits.
> >How big is you int, your long, and your pointer ?
> An int is 64-bits. A long is 128-bits. And a short is 32-bits. Pointers are 64-bit.
<
How does one access a 16-bit container?
<
< The pointer size
> may be adjustable. Number of address bits in use can be specified for the compile.
>
> I added the idea of regions to the MMU which are related to the PMA checks. There may be up
> to eight regions defined. Currently only four are used, ROM, IO, scratchpad, and RAM. The
<
I stole essentially the same thing from already available fields. When a page is unCacheable
(C=00) the used&modified bits indicate the space {00->DRAM, 01->MMI/O, 10->configuration,
11->ROM} each of these spaces can be 64-bits in size.
<
In addition, we know:: configuration space is unCacheable and strongly ordered; MMI/O is
strongly ordered per device, and sequentially consistent; ROM is cacheable, unordered,
without coherence traffic, and not writeable.
<
> ‘where’ field is computed based on the physical address. The physical address looks up a
> region in the region table and returns the PMA. The PMA includes memory type and accessibility.
<
PMA = Post Male Anxiety ?

On Sunday, March 13, 2022 at 6:49:36 PM UTC-4, MitchAlsup wrote:
> On Sunday, March 13, 2022 at 5:19:40 PM UTC-5, robf...@gmail.com wrote:
> > On Sunday, March 13, 2022 at 4:09:16 PM UTC-4, MitchAlsup wrote:
> > > On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> > > > MitchAlsup wrote:
>
> > > > The hierarchical page tables also have an array of structs indexed by
> > > > Physical Page Number (PPN) that stores the OS defined status info.
> > > > In Linux this called "struct page".
> > > >
> > > > Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> > > > is open access, available on-line in HTML or as PDF's.
> > > > https://www.kernel.org/doc/gorman/html/understand
> > > > https://www.kernel.org/doc/gorman/pdf
> > > >
> > > > Description of "struct page" descriptor:
> > > >
> > > > 2.4 Pages
> > > > https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
> > I had forgotten the hierarchical page tables do not need to store the virtual address / ASID.
> > Without the VPN things will easily fit into 96 bits. Still stuck with the issue of non-power of
> > two addressing unless the PTE size is increased to 128-bit or bits are trimmed from the PPN.
> >
> > Storing the level in the entry seems like a good idea. With extra bits available in a page, the
> > level could be stored there. All PTEs in the page would have the same level. I assume the
> > level is for debug / integrity. Could also use the bounce count field to store the level.
> <
> Not quite::
> <
> LVL of the pointer to the page of translation entries indicates the address space covered by each
> entry. But, you could have a LVL = 011 indicating a 8GB page; some entries could point at an
> 8MB entry (LVL = 010) some could point at an 8K page (LVL=001).
> <
> The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
> number of accesses used to refill the TLB, and the number of pages used to for translations.
> <
> A small program like "cat" can be compiled with a 23-bit address space and use 1 page of translation
> overhead; typically with 5 entries: .text, .bss, .data, .stack, .heap.
> >
> > I had sort of wanted to keep the same PTE format for both types of tables, but I see now it
> > does not make sense to do this. It would waste too much space in a hierarchical table. PDEs
> > are only 64-bit since they only contain a reference to page and a couple of other bits.
> > >How big is you int, your long, and your pointer ?
> > An int is 64-bits. A long is 128-bits. And a short is 32-bits. Pointers are 64-bit.
> <
> How does one access a 16-bit container?
> <
> < The pointer size
> > may be adjustable. Number of address bits in use can be specified for the compile.
> >
> > I added the idea of regions to the MMU which are related to the PMA checks. There may be up
> > to eight regions defined. Currently only four are used, ROM, IO, scratchpad, and RAM. The
> <
> I stole essentially the same thing from already available fields. When a page is unCacheable
> (C=00) the used&modified bits indicate the space {00->DRAM, 01->MMI/O, 10->configuration,
> 11->ROM} each of these spaces can be 64-bits in size.
> <
> In addition, we know:: configuration space is unCacheable and strongly ordered; MMI/O is
> strongly ordered per device, and sequentially consistent; ROM is cacheable, unordered,
> without coherence traffic, and not writeable.
> <
> > ‘where’ field is computed based on the physical address.. The physical address looks up a
> > region in the region table and returns the PMA. The PMA includes memory type and accessibility.
> <
> PMA = Post Male Anxiety ?

>The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
>number of accesses used to refill the TLB, and the number of pages used to for translations.

I just have the number of table levels specified in the PTBR. The PTBR points to the highest level PD needed.

>How does one access a 16-bit container?

By specifying int:16 as the type. The compiler supports size specs for ints of 8,16,32,64, and 128. Bytes
are also accessible as ‘byte’. I think chars are int:16. I think there is also a bit type to support bit arrays,
but this is experimental.
int:16 my_index;

> PMA = Post Male Anxiety ?

PMA = Physical Memory Attributes, stolen from RISCV docs.

On Sunday, March 13, 2022 at 7:10:48 PM UTC-4, robf...@gmail.com wrote:
> On Sunday, March 13, 2022 at 6:49:36 PM UTC-4, MitchAlsup wrote:
> > On Sunday, March 13, 2022 at 5:19:40 PM UTC-5, robf...@gmail.com wrote:
> > > On Sunday, March 13, 2022 at 4:09:16 PM UTC-4, MitchAlsup wrote:
> > > > On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
> > > > > MitchAlsup wrote:
> >
> > > > > The hierarchical page tables also have an array of structs indexed by
> > > > > Physical Page Number (PPN) that stores the OS defined status info..
> > > > > In Linux this called "struct page".
> > > > >
> > > > > Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
> > > > > is open access, available on-line in HTML or as PDF's.
> > > > > https://www.kernel.org/doc/gorman/html/understand
> > > > > https://www.kernel.org/doc/gorman/pdf
> > > > >
> > > > > Description of "struct page" descriptor:
> > > > >
> > > > > 2.4 Pages
> > > > > https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
> > > I had forgotten the hierarchical page tables do not need to store the virtual address / ASID.
> > > Without the VPN things will easily fit into 96 bits. Still stuck with the issue of non-power of
> > > two addressing unless the PTE size is increased to 128-bit or bits are trimmed from the PPN.
> > >
> > > Storing the level in the entry seems like a good idea. With extra bits available in a page, the
> > > level could be stored there. All PTEs in the page would have the same level. I assume the
> > > level is for debug / integrity. Could also use the bounce count field to store the level.
> > <
> > Not quite::
> > <
> > LVL of the pointer to the page of translation entries indicates the address space covered by each
> > entry. But, you could have a LVL = 011 indicating a 8GB page; some entries could point at an
> > 8MB entry (LVL = 010) some could point at an 8K page (LVL=001).
> > <
> > The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
> > number of accesses used to refill the TLB, and the number of pages used to for translations.
> > <
> > A small program like "cat" can be compiled with a 23-bit address space and use 1 page of translation
> > overhead; typically with 5 entries: .text, .bss, .data, .stack, .heap.
> > >
> > > I had sort of wanted to keep the same PTE format for both types of tables, but I see now it
> > > does not make sense to do this. It would waste too much space in a hierarchical table. PDEs
> > > are only 64-bit since they only contain a reference to page and a couple of other bits.
> > > >How big is you int, your long, and your pointer ?
> > > An int is 64-bits. A long is 128-bits. And a short is 32-bits. Pointers are 64-bit.
> > <
> > How does one access a 16-bit container?
> > <
> > < The pointer size
> > > may be adjustable. Number of address bits in use can be specified for the compile.
> > >
> > > I added the idea of regions to the MMU which are related to the PMA checks. There may be up
> > > to eight regions defined. Currently only four are used, ROM, IO, scratchpad, and RAM. The
> > <
> > I stole essentially the same thing from already available fields. When a page is unCacheable
> > (C=00) the used&modified bits indicate the space {00->DRAM, 01->MMI/O, 10->configuration,
> > 11->ROM} each of these spaces can be 64-bits in size.
> > <
> > In addition, we know:: configuration space is unCacheable and strongly ordered; MMI/O is
> > strongly ordered per device, and sequentially consistent; ROM is cacheable, unordered,
> > without coherence traffic, and not writeable.
> > <
> > > ‘where’ field is computed based on the physical address. The physical address looks up a
> > > region in the region table and returns the PMA. The PMA includes memory type and accessibility.
> > <
> > PMA = Post Male Anxiety ?
>
> >The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
> >number of accesses used to refill the TLB, and the number of pages used to for translations.
> I just have the number of table levels specified in the PTBR. The PTBR points to the highest level PD needed.
> >How does one access a 16-bit container?
> By specifying int:16 as the type. The compiler supports size specs for ints of 8,16,32,64, and 128. Bytes
> are also accessible as ‘byte’. I think chars are int:16. I think there is also a bit type to support bit arrays,
> but this is experimental.
> int:16 my_index;
> > PMA = Post Male Anxiety ?
> PMA = Physical Memory Attributes, stolen from RISCV docs.

Borrowed the level idea for my PT. I was just wondering what happens when a page at the same LVL as the
current is pointed to? Seems like it could form a linked list or a loop, or is a fault generated? At the moment
I have the code forcing the LVL down a level if it is the same or higher than the current LVL.

robf...@gmail.com wrote:
> On Sunday, March 13, 2022 at 7:10:48 PM UTC-4, robf...@gmail.com wrote:
>> On Sunday, March 13, 2022 at 6:49:36 PM UTC-4, MitchAlsup wrote:
>>> The important thing an LVL brings is skipping of levels in the translation hierarchy, saving the
>>> number of accesses used to refill the TLB, and the number of pages used to for translations.
>> I just have the number of table levels specified in the PTBR. The PTBR points to the highest level PD needed.
>
> Borrowed the level idea for my PT. I was just wondering what happens when a page at the same LVL as the
> current is pointed to? Seems like it could form a linked list or a loop, or is a fault generated? At the moment
> I have the code forcing the LVL down a level if it is the same or higher than the current LVL.

The OS is responsible for not creating page table loops.
That said, the HW table walker is hard wired to only walk N levels
and then quit so it shouldn't break the hardware.
What this would accomplish is a variation of what I describe below,
albeit a somewhat useless variant.

One thing to note about skipping PT levels is that OS can reuse
interior page table levels to access outer levels as data.

One question arises is exactly how does an OS edit the page tables?
That is, the OS needs to be able to read and write PTE's.
In order to do that, those page table pages (PTP) need to be
inside the current virtual space. Which means there need to be
level-1 PTE's that point to those PTP's as level-0 data.

It turns out there is already just such a set of PTE's:
the level-2 PTP's point to level-1 PTP.
So OS can reuse a PTL-2 PTP as a PTL-1 PTP,
making the PTP that level-1 points to accessible as level-0 data.

PTL3->PTL2a->PTL1->Data
|->PTL2b->PTL1

By adding a PTE to level-2 that point to a different level-2 page,
it makes that page act as a level-1 page, giving read/write access
as data to the level-1 page that it point to.

All of this should be compatible with level skipping.
If level-6 says skip to level-2, and level-2 reuses a PTL2 PTP
as a PTL1 PTP, then the table walker knows its is at level-2
and should only walk 1 more step.
A potential problem with level skipping is if it somehow skipped off the
end of the tree. That could only happen if the OS constructed an illegal
page table, so it could trigger a page fault with a unique error code.

All of this should be compatible with the bottom-up TLB-miss
table walking optimization, whereby on TLB-miss it walks backwards
up the table levels from level-1 towards level-6,
checking for interior level PTE caching.

I don't know if either Windows or Linux use this table management method.
If I was designing an OS paging subsystem I certainly would.

So what would a PTP that contains a PTE that points to itself do?
The table walker would loop N times, and end up with a virtual
address mapped to that same PTP as data, allowing access to itself.
As I said, not all that useful.

MitchAlsup wrote:
> On Sunday, March 13, 2022 at 1:19:23 PM UTC-5, EricP wrote:
>> MitchAlsup wrote:
>
>> The hierarchical page tables also have an array of structs indexed by
>> Physical Page Number (PPN) that stores the OS defined status info.
>> In Linux this called "struct page".
>>
>> Mel Gorman's 2007 book "Understanding the Linux Virtual Memory Manager"
>> is open access, available on-line in HTML or as PDF's.
>> https://www.kernel.org/doc/gorman/html/understand
>> https://www.kernel.org/doc/gorman/pdf
>>
>> Description of "struct page" descriptor:
>>
>> 2.4 Pages
>> https://www.kernel.org/doc/gorman/html/understand/understand005.html#toc15
> <
> Is there something equivalent to this with
> a) 64-bit virtual-physical addresses
> b) nested page tables

There is kernel documentation but is seems to be API oriented
rather than architecture or design oriented.

For example, I can't find how they map and edit the process page tables.
Or exactly how fork handles page tables.

The Linux Kernel documentation
https://www.kernel.org/doc/html/latest/index.html

Linux Memory Management Documentation
https://www.kernel.org/doc/html/latest/vm/index.html

Linux Virtualization Support
https://www.kernel.org/doc/html/latest/virt/index.html

There is some cpu specific info but the stuff I looked at was no help.

CPU Architectures
https://www.kernel.org/doc/html/latest/arch.html
x86-specific Documentation
https://www.kernel.org/doc/html/latest/x86/index.html