1. Address translation circuitry for translating virtual addresses to physical addresses for a data processor in response to access requests from said data processor targeting virtual addresses, said address translation circuitry comprising: a data store comprising a plurality of entries for storing a plurality of mappings of ranges of virtual addresses to ranges of physical addresses for said data processor and additional data associated with each of said plurality of mappings within a table, said data processor being responsive to said access requests to access said table to retrieve a corresponding mapping and to access a further store of mappings if said corresponding mapping is not present in said table; updating circuitry for updating said table in response to an access request for a virtual address that is not mapped by said table, said updating circuitry being responsive to receipt of a mapping for said virtual address from said further store to: select a plurality of entries in said table suitable for storing said received mapping; and determine one of said plurality of selected entries to be overwritten by said received mapping in dependence upon at least a portion of said additional data stored in said one of said plurality of selected entries.