1.1 --- a/src/sh4/mmu.c	Fri Oct 31 02:57:59 2008 +0000
     1.2 +++ b/src/sh4/mmu.c	Fri Nov 07 06:39:12 2008 +0000
     1.3 @@ -18,6 +18,7 @@
     1.4  #define MODULE sh4_module
     1.5  
     1.6  #include <stdio.h>
     1.7 +#include <assert.h>
     1.8  #include "sh4/sh4mmio.h"
     1.9  #include "sh4/sh4core.h"
    1.10  #include "sh4/sh4trans.h"
    1.11 @@ -101,6 +102,13 @@
    1.12      uint32_t pcmcia; // extra pcmcia data - not used
    1.13  };
    1.14  
    1.15 +struct utlb_sort_entry {
    1.16 +    sh4addr_t key; // Masked VPN + ASID
    1.17 +    uint32_t mask; // Mask + 0x00FF
    1.18 +    int entryNo;
    1.19 +};
    1.20 +    
    1.21 +
    1.22  static struct itlb_entry mmu_itlb[ITLB_ENTRY_COUNT];
    1.23  static struct utlb_entry mmu_utlb[UTLB_ENTRY_COUNT];
    1.24  static uint32_t mmu_urc;
    1.25 @@ -108,9 +116,14 @@
    1.26  static uint32_t mmu_lrui;
    1.27  static uint32_t mmu_asid; // current asid
    1.28  
    1.29 +static struct utlb_sort_entry mmu_utlb_sorted[UTLB_ENTRY_COUNT];
    1.30 +static uint32_t mmu_utlb_entries; // Number of entries in mmu_utlb_sorted. 
    1.31 +
    1.32  static sh4ptr_t cache = NULL;
    1.33  
    1.34  static void mmu_invalidate_tlb();
    1.35 +static void mmu_utlb_sorted_reset();
    1.36 +static void mmu_utlb_sorted_reload(); 
    1.37  
    1.38  
    1.39  static uint32_t get_mask_for_flags( uint32_t flags )
    1.40 @@ -169,7 +182,7 @@
    1.41          mmu_lrui = (val >> 26) & 0x3F;
    1.42          val &= 0x00000301;
    1.43          tmp = MMIO_READ( MMU, MMUCR );
    1.44 -        if( (val ^ tmp) & MMUCR_AT ) {
    1.45 +        if( (val ^ tmp) & (MMUCR_AT|MMUCR_SV) ) {
    1.46              // AT flag has changed state - flush the xlt cache as all bets
    1.47              // are off now. We also need to force an immediate exit from the
    1.48              // current block
    1.49 @@ -215,6 +228,7 @@
    1.50  {
    1.51      mmio_region_MMU_write( CCR, 0 );
    1.52      mmio_region_MMU_write( MMUCR, 0 );
    1.53 +    mmu_utlb_sorted_reload();
    1.54  }
    1.55  
    1.56  void MMU_save_state( FILE *f )
    1.57 @@ -255,6 +269,7 @@
    1.58      if( fread( &mmu_asid, sizeof(mmu_asid), 1, f ) != 1 ) {
    1.59          return 1;
    1.60      }
    1.61 +    mmu_utlb_sorted_reload();
    1.62      return 0;
    1.63  }
    1.64  
    1.65 @@ -277,6 +292,120 @@
    1.66      }
    1.67  }
    1.68  
    1.69 +/******************* Sorted TLB data structure ****************/
    1.70 +/*
    1.71 + * mmu_utlb_sorted maintains a list of all active (valid) entries,
    1.72 + * sorted by masked VPN and then ASID. Multi-hit entries are resolved 
    1.73 + * ahead of time, and have -1 recorded as the corresponding PPN.
    1.74 + * 
    1.75 + * FIXME: Multi-hit detection doesn't pick up cases where two pages 
    1.76 + * overlap due to different sizes (and don't share the same base
    1.77 + * address). 
    1.78 + */ 
    1.79 +static void mmu_utlb_sorted_reset() 
    1.80 +{
    1.81 +    mmu_utlb_entries = 0;
    1.82 +}
    1.83 +
    1.84 +/**
    1.85 + * Find an entry in the sorted table (VPN+ASID check). 
    1.86 + */
    1.87 +static inline int mmu_utlb_sorted_find( sh4addr_t vma )
    1.88 +{
    1.89 +    int low = 0;
    1.90 +    int high = mmu_utlb_entries;
    1.91 +    uint32_t lookup = (vma & 0xFFFFFC00) + mmu_asid;
    1.92 +
    1.93 +    mmu_urc++;
    1.94 +    if( mmu_urc == mmu_urb || mmu_urc == 0x40 ) {
    1.95 +        mmu_urc = 0;
    1.96 +    }
    1.97 +
    1.98 +    while( low != high ) {
    1.99 +        int posn = (high+low)>>1;
   1.100 +        int masked = lookup & mmu_utlb_sorted[posn].mask;
   1.101 +        if( mmu_utlb_sorted[posn].key < masked ) {
   1.102 +            low = posn+1;
   1.103 +        } else if( mmu_utlb_sorted[posn].key > masked ) {
   1.104 +            high = posn;
   1.105 +        } else {
   1.106 +            return mmu_utlb_sorted[posn].entryNo;
   1.107 +        }
   1.108 +    }
   1.109 +    return -1;
   1.110 +
   1.111 +}
   1.112 +
   1.113 +static void mmu_utlb_insert_entry( int entry )
   1.114 +{
   1.115 +    int low = 0;
   1.116 +    int high = mmu_utlb_entries;
   1.117 +    uint32_t key = (mmu_utlb[entry].vpn & mmu_utlb[entry].mask) + mmu_utlb[entry].asid;
   1.118 +
   1.119 +    assert( mmu_utlb_entries < UTLB_ENTRY_COUNT );
   1.120 +    /* Find the insertion point */
   1.121 +    while( low != high ) {
   1.122 +        int posn = (high+low)>>1;
   1.123 +        if( mmu_utlb_sorted[posn].key < key ) {
   1.124 +            low = posn+1;
   1.125 +        } else if( mmu_utlb_sorted[posn].key > key ) {
   1.126 +            high = posn;
   1.127 +        } else {
   1.128 +            /* Exact match - multi-hit */
   1.129 +            mmu_utlb_sorted[posn].entryNo = -2;
   1.130 +            return;
   1.131 +        }
   1.132 +    } /* 0 2 4 6 */
   1.133 +    memmove( &mmu_utlb_sorted[low+1], &mmu_utlb_sorted[low], 
   1.134 +             (mmu_utlb_entries - low) * sizeof(struct utlb_sort_entry) );
   1.135 +    mmu_utlb_sorted[low].key = key;
   1.136 +    mmu_utlb_sorted[low].mask = mmu_utlb[entry].mask | 0x000000FF;
   1.137 +    mmu_utlb_sorted[low].entryNo = entry;
   1.138 +    mmu_utlb_entries++;
   1.139 +}
   1.140 +
   1.141 +static void mmu_utlb_remove_entry( int entry )
   1.142 +{
   1.143 +    int low = 0;
   1.144 +    int high = mmu_utlb_entries;
   1.145 +    uint32_t key = (mmu_utlb[entry].vpn & mmu_utlb[entry].mask) + mmu_utlb[entry].asid;
   1.146 +    while( low != high ) {
   1.147 +        int posn = (high+low)>>1;
   1.148 +        if( mmu_utlb_sorted[posn].key < key ) {
   1.149 +            low = posn+1;
   1.150 +        } else if( mmu_utlb_sorted[posn].key > key ) {
   1.151 +            high = posn;
   1.152 +        } else {
   1.153 +            if( mmu_utlb_sorted[posn].entryNo == -2 ) {
   1.154 +                /* Multiple-entry recorded - rebuild the whole table minus entry */
   1.155 +                int i;
   1.156 +                mmu_utlb_entries = 0;
   1.157 +                for( i=0; i< UTLB_ENTRY_COUNT; i++ ) {
   1.158 +                    if( i != entry && (mmu_utlb[i].flags & TLB_VALID)  ) {
   1.159 +                        mmu_utlb_insert_entry(i);
   1.160 +                    }
   1.161 +                }
   1.162 +            } else {
   1.163 +                mmu_utlb_entries--;
   1.164 +                memmove( &mmu_utlb_sorted[posn], &mmu_utlb_sorted[posn+1],
   1.165 +                         (mmu_utlb_entries - posn)*sizeof(struct utlb_sort_entry) );
   1.166 +            }
   1.167 +            return;
   1.168 +        }
   1.169 +    }
   1.170 +    assert( 0 && "UTLB key not found!" );
   1.171 +}
   1.172 +
   1.173 +static void mmu_utlb_sorted_reload()
   1.174 +{
   1.175 +    int i;
   1.176 +    mmu_utlb_entries = 0;
   1.177 +    for( i=0; i<UTLB_ENTRY_COUNT; i++ ) {
   1.178 +        if( mmu_utlb[i].flags & TLB_VALID ) 
   1.179 +            mmu_utlb_insert_entry( i );
   1.180 +    }
   1.181 +}
   1.182 +
   1.183  /* TLB maintanence */
   1.184  
   1.185  /**
   1.186 @@ -285,12 +414,18 @@
   1.187   */
   1.188  void MMU_ldtlb()
   1.189  {
   1.190 +    if( mmu_utlb[mmu_urc].flags & TLB_VALID )
   1.191 +        mmu_utlb_remove_entry( mmu_urc );
   1.192      mmu_utlb[mmu_urc].vpn = MMIO_READ(MMU, PTEH) & 0xFFFFFC00;
   1.193      mmu_utlb[mmu_urc].asid = MMIO_READ(MMU, PTEH) & 0x000000FF;
   1.194      mmu_utlb[mmu_urc].ppn = MMIO_READ(MMU, PTEL) & 0x1FFFFC00;
   1.195      mmu_utlb[mmu_urc].flags = MMIO_READ(MMU, PTEL) & 0x00001FF;
   1.196      mmu_utlb[mmu_urc].pcmcia = MMIO_READ(MMU, PTEA);
   1.197      mmu_utlb[mmu_urc].mask = get_mask_for_flags(mmu_utlb[mmu_urc].flags);
   1.198 +    if( mmu_utlb[mmu_urc].ppn >= 0x1C000000 )
   1.199 +        mmu_utlb[mmu_urc].ppn |= 0xE0000000;
   1.200 +    if( mmu_utlb[mmu_urc].flags & TLB_VALID )
   1.201 +        mmu_utlb_insert_entry( mmu_urc );
   1.202  }
   1.203  
   1.204  static void mmu_invalidate_tlb()
   1.205 @@ -302,6 +437,7 @@
   1.206      for( i=0; i<UTLB_ENTRY_COUNT; i++ ) {
   1.207          mmu_utlb[i].flags &= (~TLB_VALID);
   1.208      }
   1.209 +    mmu_utlb_entries = 0;
   1.210  }
   1.211  
   1.212  #define ITLB_ENTRY(addr) ((addr>>7)&0x03)
   1.213 @@ -314,7 +450,7 @@
   1.214  int32_t mmu_itlb_data_read( sh4addr_t addr )
   1.215  {
   1.216      struct itlb_entry *ent = &mmu_itlb[ITLB_ENTRY(addr)];
   1.217 -    return ent->ppn | ent->flags;
   1.218 +    return (ent->ppn & 0x1FFFFC00) | ent->flags;
   1.219  }
   1.220  
   1.221  void mmu_itlb_addr_write( sh4addr_t addr, uint32_t val )
   1.222 @@ -331,6 +467,8 @@
   1.223      ent->ppn = val & 0x1FFFFC00;
   1.224      ent->flags = val & 0x00001DA;
   1.225      ent->mask = get_mask_for_flags(val);
   1.226 +    if( ent->ppn >= 0x1C000000 )
   1.227 +        ent->ppn |= 0xE0000000;
   1.228  }
   1.229  
   1.230  #define UTLB_ENTRY(addr) ((addr>>8)&0x3F)
   1.231 @@ -349,7 +487,7 @@
   1.232      if( UTLB_DATA2(addr) ) {
   1.233          return ent->pcmcia;
   1.234      } else {
   1.235 -        return ent->ppn | ent->flags;
   1.236 +        return (ent->ppn&0x1FFFFC00) | ent->flags;
   1.237      }
   1.238  }
   1.239  
   1.240 @@ -402,9 +540,15 @@
   1.241          int utlb = mmu_utlb_lookup_assoc( val, mmu_asid );
   1.242          if( utlb >= 0 ) {
   1.243              struct utlb_entry *ent = &mmu_utlb[utlb];
   1.244 +            uint32_t old_flags = ent->flags;
   1.245              ent->flags = ent->flags & ~(TLB_DIRTY|TLB_VALID);
   1.246              ent->flags |= (val & TLB_VALID);
   1.247              ent->flags |= ((val & 0x200)>>7);
   1.248 +            if( (old_flags & TLB_VALID) && !(ent->flags&TLB_VALID) ) {
   1.249 +                mmu_utlb_remove_entry( utlb );
   1.250 +            } else if( !(old_flags & TLB_VALID) && (ent->flags&TLB_VALID) ) {
   1.251 +                mmu_utlb_insert_entry( utlb );
   1.252 +            }
   1.253          }
   1.254  
   1.255          int itlb = mmu_itlb_lookup_assoc( val, mmu_asid );
   1.256 @@ -419,11 +563,15 @@
   1.257          }
   1.258      } else {
   1.259          struct utlb_entry *ent = &mmu_utlb[UTLB_ENTRY(addr)];
   1.260 +        if( ent->flags & TLB_VALID ) 
   1.261 +            mmu_utlb_remove_entry( UTLB_ENTRY(addr) );
   1.262          ent->vpn = (val & 0xFFFFFC00);
   1.263          ent->asid = (val & 0xFF);
   1.264          ent->flags = (ent->flags & ~(TLB_DIRTY|TLB_VALID));
   1.265          ent->flags |= (val & TLB_VALID);
   1.266          ent->flags |= ((val & 0x200)>>7);
   1.267 +        if( ent->flags & TLB_VALID ) 
   1.268 +            mmu_utlb_insert_entry( UTLB_ENTRY(addr) );
   1.269      }
   1.270  }
   1.271  
   1.272 @@ -433,9 +581,15 @@
   1.273      if( UTLB_DATA2(addr) ) {
   1.274          ent->pcmcia = val & 0x0000000F;
   1.275      } else {
   1.276 +        if( ent->flags & TLB_VALID ) 
   1.277 +            mmu_utlb_remove_entry( UTLB_ENTRY(addr) );
   1.278          ent->ppn = (val & 0x1FFFFC00);
   1.279          ent->flags = (val & 0x000001FF);
   1.280          ent->mask = get_mask_for_flags(val);
   1.281 +        if( mmu_utlb[mmu_urc].ppn >= 0x1C000000 )
   1.282 +            mmu_utlb[mmu_urc].ppn |= 0xE0000000;
   1.283 +        if( ent->flags & TLB_VALID ) 
   1.284 +            mmu_utlb_insert_entry( UTLB_ENTRY(addr) );
   1.285      }
   1.286  }
   1.287  
   1.288 @@ -603,7 +757,7 @@
   1.289      }
   1.290  
   1.291      if( result == -1 ) {
   1.292 -        int utlbEntry = mmu_utlb_lookup_vpn_asid( vpn );
   1.293 +        int utlbEntry = mmu_utlb_sorted_find( vpn );
   1.294          if( utlbEntry < 0 ) {
   1.295              return utlbEntry;
   1.296          } else {
   1.297 @@ -663,7 +817,7 @@
   1.298  
   1.299      return result;
   1.300  }
   1.301 -
   1.302 + 
   1.303  sh4addr_t FASTCALL mmu_vma_to_phys_read( sh4vma_t addr )
   1.304  {
   1.305      uint32_t mmucr = MMIO_READ(MMU,MMUCR);
   1.306 @@ -693,7 +847,7 @@
   1.307      /* If we get this far, translation is required */
   1.308      int entryNo;
   1.309      if( ((mmucr & MMUCR_SV) == 0) || !IS_SH4_PRIVMODE() ) {
   1.310 -        entryNo = mmu_utlb_lookup_vpn_asid( addr );
   1.311 +        entryNo = mmu_utlb_sorted_find( addr );
   1.312      } else {
   1.313          entryNo = mmu_utlb_lookup_vpn( addr );
   1.314      }
   1.315 @@ -714,11 +868,8 @@
   1.316          }
   1.317  
   1.318          /* finally generate the target address */
   1.319 -        sh4addr_t pma = (mmu_utlb[entryNo].ppn & mmu_utlb[entryNo].mask) |
   1.320 +        return (mmu_utlb[entryNo].ppn & mmu_utlb[entryNo].mask) |
   1.321          	(addr & (~mmu_utlb[entryNo].mask));
   1.322 -        if( pma > 0x1C000000 ) // Remap 1Cxx .. 1Fxx region to P4
   1.323 -        	pma |= 0xE0000000;
   1.324 -        return pma;
   1.325      }
   1.326  }
   1.327  
   1.328 @@ -751,7 +902,7 @@
   1.329      /* If we get this far, translation is required */
   1.330      int entryNo;
   1.331      if( ((mmucr & MMUCR_SV) == 0) || !IS_SH4_PRIVMODE() ) {
   1.332 -        entryNo = mmu_utlb_lookup_vpn_asid( addr );
   1.333 +        entryNo = mmu_utlb_sorted_find( addr );
   1.334      } else {
   1.335          entryNo = mmu_utlb_lookup_vpn( addr );
   1.336      }
   1.337 @@ -779,8 +930,6 @@
   1.338          /* finally generate the target address */
   1.339          sh4addr_t pma = (mmu_utlb[entryNo].ppn & mmu_utlb[entryNo].mask) |
   1.340          	(addr & (~mmu_utlb[entryNo].mask));
   1.341 -        if( pma > 0x1C000000 ) // Remap 1Cxx .. 1Fxx region to P4
   1.342 -        	pma |= 0xE0000000;
   1.343          return pma;
   1.344      }
   1.345  }