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 is disclosed . the address translation circuitry comprises : 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 ; 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 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 .