[LMH]New List Member

[Steve Krueger]

Robert Swindells wrote:

>Have you got any documentation on the hash function used to store
>entries in the PHT ? The SSDN2 doesn't describe the algorithm itself.
>
>At the moment the exploiter emulator just does a linear search. It
>works, but it would be good to use the real thing.
>  
>

I don't know for sure that it wasn't changed, but looking at ucode 
version 207 for Explorer I I'll type it as psuedo code:

PGF-MAP-MISS:
    if ( address >= A-Lowest-Direct-Virtual-Address)  {
        check for a-memory, frame-buffer or pdl-buffer access
    } else {
       PGF-L2A:
          turn_on_L2_miss_bar();
          SEARCH-PAGE-HASH-TABLE(address);
          switch (PHT1-Swap-Status-Code) {   // bit field <2:0>
             0: goto SWAPIN;            // 0   PHT entry invalid, get 
page from disk
             1: goto PGF-RL;              // 1   Normal, reload page map 
from PHT entry
             2: goto PGF-FL;              // 2    Flushable, change back 
to normal
             3: goto PGF-PRE;           // 3    Prepaged, change to 
normal, we want it now
             4: goto PGF-AG;            // 4    Age, change back to normal
             5: goto PGF-RL;             // 5    Wired-down page, reload 
page map
             6: call ILLOP;                 // 6    Unused code, crash
             7: call ILLOP;                 // 7    Unused code, crash
             default: call ILLOP;       // can't get here.
          }
    }


SEARCH-PAGE-HASH-TABLE:
   t = COMPUTE-PAGE-HASH(address);
   pht1 = PHT[ t ];
   while ( ! pht1 & byte-mask( 1,  6 ) ) {   // PHT1-Valid-Bit
       if  ( ! ( ( pht1 ^ address ) & byte-mask( 17 ,  8 ) ) ) return 
(list t pht1); // match
       t = t + 2;
       if ( t >= PHT-INDEX-LIMIT ) t = t - PHT-INDEX-LIMIT;
       pht1 = PHT[ t ];
    }
    // here if found an invalid entry
    return ( list t pht1 )

COMPUTE-PAGE-HASH:
    tem1 = byte-field(address, 11 , 14);     // address<24:14>
    t = byte-field(address, (25 - 4) , 4 ) & ~ 15;     // address<24:8> << 4
    t = ( tem1 ^ t ) & PHT-INDEX-MASK;
    if ( t >= PHT-INDEX-LIMIT ) t = t - PHT-INDEX-LIMIT;
    return t;


Several of the variables are A-memory variables that are bound to Lisp 
symbols:
    PHT-INDEX-LIMIT
    PHT-INDEX-MASK
    LOWEST-DIRECT-VIRTUAL-ADDRESS
    V-PAGE-TABLE-AREA                                 // the address of PHT

Each entry of the page table is two words long.  The second word is 
pretty much the L2 map bits.

I apologize now for any mistakes I've made in transliterating this from 
ucode.  Note that this is kind-a-C{tm}.  Probably the biggest systematic 
transgression from real-C is that the variable names were written ucode 
style with "-" between words.

I hope this helps.

    -Steve