From: user5857@newsgrouper.org.invalid   
      
   Robert Finch  posted:   
      
   > On 2026-02-01 10:28 a.m., Kent Dickey wrote:   
   > > In article <10lji2u$2haq2$1@dont-email.me>,   
   > > Robert Finch   wrote:   
   > >> On 2026-01-30 4:44 p.m., BGB wrote:   
   > >>> On 1/30/2026 3:03 PM, Robert Finch wrote:   
   > >   
   > > [ Proposal is a hashed page table, with 2x the entries to cover the entire   
   > > physical address space, with each hash entry having 8 pages which need to   
   > > be searched before moving to the next entry].   
   > >   
   > >>> It isn't obvious (at least to me) how what you are describing is much   
   > >>> different from a SW managed TLB.   
   > >>>   
   > >> It is not a lot different. On a translation miss the table is walked   
   > >> with HW though instead of SW walking main memory. There are enough   
   > >> entries in the table to cover the physical address range. Only page   
   > >> faults are handled in SW which should be rare. A page fault is generated   
   > >> after 30 steps in the walk though. That is a miss on 240 possible   
   > >> locations. 240-way associativity is not enough?   
   > >> The page fault handler will like just report 'out-of-memory' then quit   
   > >> the app.   
   > >   
   > > I'm going to guess your physical address space is just 32-bits, otherwise   
   >   
   > Yes, this is for a 29-bit DRAM address space. I was going to use 2^13   
   > entries with 256kB (or possibly smaller) pages. It is only usable with a   
   > smaller address space that can fit into BRAM.   
   >   
   > > this table is huge.  I think you said you have 64KB pages (but then you   
   said   
   > > 256KB pages--which is just too big, so I'll ignore that), which for a   
   > > 44-bit physical address space would mean 2^28 entries, with each entry   
   > > being 128-bits, for a 4GB page table.  But for 32-bit, it's just 2^16   
   > > entries of 64-bits each.   
   > >   
   > > A page table which doesn't scale is problematic.  Especially if it needs   
   > > OS support.  Who wants to invest effort in a dead-end idea?   
   > >   
   > > Your hashed page table has issues which I think you should address:   
   > >   
   > > 1) Supporting multiple page sizes is a pain.  If you have 2MB pages and   
   > > 	64KB pages, there are 32 64KB pages for each 2MB page.  So do you   
   > > 	lazily load the hashtable only on misses, or load all 32 aliases   
   > > 	at once?   
   >   
   > Supporting multiple page sized is a pain even for a hierarchical table.   
   > Multiple TLBs are used, so maybe multiple hash tables could be used. But   
   > I was not planning on supporting more than one page size.   
      
   I support multiple page sizes, and at both the architectural level and   
   in the TLB circuits I did not find it all that difficult. {Hint: I built   
   one of the TLB for Ross HyperSparc chips.} There are several ways to do   
   it in logic, none of it "hard". Most of it "a bit different".   
      
   Defining Super pages is "just stopping" early in the tablewalk.   
   Skipping intermediate levels is just like "stopping early" except   
   for the stopping part.   
   Skipping top layers is "child's play" at that point {Smaller VAS}.   
      
   My 66000 has all of that; but in addition:   
   My 66000 SuperPages use the unused PA bits as a limit function so a   
   SuperPage of 1024 pages can be used to map 1-1024 actual page(s).   
      
   > >   
   > > 2) It's common to just do a single hash lookup, then trap to software.    
   Doing   
   > > 	probing is a big pain.  The problems come from removing entries.   
   > > 	If you page out a page, it leaves gaps in the table.  When you do   
   > > 	a hardware lookup, and find no valid pages at the first entry, this   
   > > 	doesn't tell you anything!  The obvious solution is ALL hardware   
   >   
   > Thanks, I had forgotten the issue with removes. Inserts are easy without   
   > removes. I wonder if the removes could be done in bulk similar to a   
   > garbage collection. Just mark the entry as deleted rather than leaving a   
   > gap, then have a process that periodically rebuilds the table. For the   
   > table size I am planning on using garbage collecting it may not be too bad.   
   >   
   > The table probes until it finds the entry, or an empty entry in a group   
   > where the lookup should be. It stops after a certain number of probes if   
   > there are no empty entries in the group.   
   >   
   > The lookup returns the group and the group empty status at which there   
   > is an empty entry if the lookup is not found. So, adding a new entry   
   > should be straightforward.   
   >   
   > > 	lookups must do the maximum searching before declaring a hash-table   
   > > 	miss--which you say is 30 steps, checking 240 entries.  I'm not sure   
   > > 	there's a better solution than that, but this is a pretty big   
   > > 	penalty for a TLB miss.   
   >   
   > 30 steps (in HW) is about as fast as a divide operation. It only works   
   > for BRAM, it was DRAM it would be many clocks per lookup.   
      
   Also: a far cry from a 6-cycle L2 TLB with 1024-E.   
   >   
   > >   
   > > 3) It's very complex to efficiently update the hash table.  On inserting   
   > > 	a new entry, where do you put it?  On one hand, a "move-to-front"   
   > > 	strategy seems like a good idea--newly added pages seem like they   
   > > 	should get lookup priority.  But how do you do this?  It looks like   
   > > 	each software handled miss has a TON of work to do.  It seems like   
   >   
   > I was not planning on anything that complex. The miss returns the group   
   > at which the entry should be located, so SW should know where to insert.   
   > For testing, the test bench fakes inserting pages. The issues rise when   
   > the table gets full.   
   >   
   > > 	you need to re-hash each entry you consider moving, to make sure it   
   > > 	stays on its proper hash chain.  And keeping the OS page structures   
   > > 	in sync looks like even more work.   
   > >   
   > > 4) The global nature of the hash table means multiple threads probably need   
   > > 	a lock to change it.  So misses to software have to get a lock before   
   > > 	making any hashtable changes.  This is very expensive.  This is   
   > > 	especially bad when a process ends--all of its translations need to   
   > > 	be removed, and so all page table misses are blocked while that   
   > > 	happens.  This is bad.   
   >   
   > Definitely an issue. May have only the system (one) thread able to   
   > update it.   
   >   
   > >   
   > > A simpler approach is a per-process hash table of variable size in memory,   
   > > sized to at least 2X the number of pages being used.  It's indexed by a   
   hash   
   > > of ASID+VA, and does a single probe.  It might be useful to do two hash   
   > > tables: one for large pages, and one for small pages (with 2 lookups).   
   > > On any miss, the hash entry to be updated is easy to find for software.   
   > > But: there's effectively no associativity--but just increase the hash   
   table's   
   > > size if software detects that you are getting conflicts.  Pick a good   
   > > hash function to avoid stupid conflicts.  I recommend you make the hash   
   > > function an instruction, so software can calculate it easily (so if you   
   > > reverse bits and do other stuff that may be hard for software to calculate,   
   > > you make it easy).   
   > >   
   > > This gives you the benefits of a hardware table walker with less trouble.   
   > >   
   > > An advantage of hashed page tables is the TLB itself has no "intermediate"   
      
   [continued in next message]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)