Hardware and software co-design for efficient memory access

Abstract

Virtual memory is a crucial computing abstraction that has stood the test of time. The level of indirection that it introduces, facilitates programming, i.e. creates the illusion that physical memory is vast, linear and private per application or enables the access of I/O devices in memory space, and assists agile resource management. However these fundamental properties do not come for free. Virtual memory assumes that the Operating System (OS) must maintain the abstraction of memory that each process acknowledges, the virtual address space indirection, and map it to actual physical resources. It also assumes that each CPU memory access operation must go through a translation step. None of the above mechanisms is cheap and, if anything, their costs are getting more and more profound.There are four trends that stress the performance of virtual memory today, (i) the meteoric rise in memory demands and capacities, (ii) the seismic shift of users from enterprise data centers to the cloud, (iii) the rapid evolution of high-performance storage devices and (iv) the increasing heterogeneity in both the compute and the store landscape of data-center systems. The first two considerably raise the efficiency bar for address translation and the second two urge us to revisit the legacy virtual memory interfaces semantics and consecutively their design. This thesis contributes in both directions.The exponential growth of global data and the corresponding increase in the memory demands of workloads led virtual memory’s dominant implementation – paging– hit the Address Translation Wall almost a decade ago. In this thesis we show that despite the fact that vendors tripled translation hardware budget since then, e.g. by incorporating larger TLBs and MMU caches or better huge page support, memory-intensive workloads can still spend up to 30% of their execution time in address translation – especially when they run in virtualized environments. To deal with paging’s poor performance scaling, this thesis proposes synergistic software and hardware mechanisms that create and exploit linearity in mappings. We propose Contiguity-Aware (CA) paging, a novel memory management technique that enhances the Operating System’s page fault handler with hints to allocate target pages and create vast contiguous virtual-to-physical mappings per process. CA paging is applicable to both native and nested paging and it maintains all lightweight memory management techniques of a modern OS, i.e demand paging, Copy-On-Write etc, while avoiding any memory reservation or pre-allocation. We implement our proposal in stock Linux and make it publicly available. On the hardware side, to harvest the generated contiguity, we propose Speculative Offset Address Translation (SpOT). SpOT is a micro-architecture engine that exploits the underlying linearity in mappings to predict address translation on the TLB miss path. While most state-of-the-art hardware proposals fail to support virtualization, due to the architectural complexity of tracking and caching arbitrarily sized mappings in two-dimensional execution, SpOT is directly and transparently applicable to both native and virtualized environments –because it works entirely on the micro-architecture level. Combined with CA paging, SpOT reduces the translation overheads of nested paging from ∼16.5% to ∼0.9% on average for memory-intensive workloads, in a design that trades architectural complexity with strong security guarantees.Apart from a physical memory abstraction, virtual memory is also an important interface towards IO devices; file mappings allow applications to access persistent data via memory dereference. However, high-performance storage has evolved significantly the past decade and nowadays devices offer single digit or even sub-microsecond latencies, exposing the kernel software IO stack as a prohibitively expensive data path. In this thesis, we study the case of persistent memory (PMem) and the direct access file interface (DAX). With PMem and DAX, virtual memory can map storage locations directly to user-space, enabling persistent data access via CPU load/store instructions; forming the shortest existing path to storage. Yet in our study we find that virtual memory operations often throttle direct access performance, failing to deliver what the underlying hardware can provide. In this thesis we break down all sources of overhead in using memory as a file interface. We study how the expensive mechanisms of virtual memory are affected by the new fast storage technology or if they even become obsolete. Based on our analysis, we propose a new interface for fast and scalable direct access to persistent data. DaxVM is a POSIX-relaxed file mapping interface for persistent memory, implemented by redesigning virtual memory operations and extending PMem-aware file systems –all changes driven by direct access unique characteristics. DaxVM supports (i) O(1) memory mapping operations via persistent page tables integrated in file system’s inode metadata, (ii) lazy invalidation of the TLBs, (iii) scalable address space management for ephemeral mappings, (iv) elimination of kernel-space durability management support when user-space is in charge and (v) asynchronous storage block pre-zeroing by the file system to accelerate DAX append operations. We implement DaxVM in stock Linux and the ext4-DAX and NOVA file systems and make it publicly available. We evaluate it on a real system equipped with Intel Optane. For multi-threaded workloads that process multiple small files for short intervals, e.g., Apache, DaxVM improves standard mmap performance up to 4.9x. It also reverses the trend that favors read for such setups, outperforming it by up to 1.5x. DaxVM also increases system availability, providing fast boot times for PMem databases, and sustains high throughput even when they run on fragmented file system images.Overall, this thesis revisits today’s virtual memory design and proposes hardware and software techniques that extend it to (i) scale better with the ever increasing memory capacities, through efficient address translation, and (ii) form a dedicated file mapping interface to push performance to the limits of what the underlying hardware can provide for direct access to persistent data.

Η εικονική μνήμη είναι μια κρίσιμη υπολογιστική αφαίρεση που έχει αντέξει στη δοκιμασία του χρόνου. Διευκολύνει τον προγραμματισμό δημιουργώντας την ψευδαίσθηση ότι η φυσική μνήμη είναι τεράστια, γραμμική και ιδιωτική ανά διεργασία, επιτρέπει την πρόσβαση σε συσκευες E/E στο χώρο της μνήμης και βοηθά στην ευέλικτη διαχείριση πόρων. Ωστόσο, αυτές οι θεμελιώδεις ιδιότητες δεν παρέχονται δωρεάν. Η εικονική μνήμη προϋποθέτει ότι το Λειτουργικό Σύστημα (ΛΣ) δημιουργεί και διαχειρίζεται αυτήν την αφαίρεση της φυσικής μνήμης που αναγνωρίζει κάθε διεργασία, τον λεγόμενο εικονικό χώρο διευθύνσεων, και τον αντιστοιχεί σε πραγματικούς φυσικούς πόρους. Η εικονική μνήμη επίσης επιβάλλει ότι κάθε λειτουργία πρόσβασης στη μνήμη (του επεξεργαστή) περνάει από ένα βήμα μετάφρασης. Κανένας από τους παραπάνω μηχανισμούς δεν είναι φθηνός και, για την ακρίβεια, το κόστος τους συνεχώς αυξάνεται. Υπάρχουν τέσσερις τάσεις που στρεσάρουν την απόδοση της εικονικής μνήμης σήμερα, (i) η μετεωρική άνοδος των απαιτήσεων χωρητικότητας μνήμης, (ii) η σεισμική μετατόπιση των χρηστών στη χρήση του υπολογιστικού νέφους (cloud), (iii) η ταχεία εξέλιξη των συσκευών αποθήκευσης με όρους απόδοσης και (iv) η αυξανόμενη ετερογένεια των συσκευών υπολογισμού και αποθήκευσης στα συστήματα μεγάλων δεδομένων. Οι δύο πρώτες ανεβάζουν σημαντικά τον πήχη απόδοσης της διαδικασίας μετάφρασης εικονικών διευθύνσεων σε φυσικές και οι δύο επόμενες μας προτρέπουν να ξανασκεφτούμε τη σημασιολογία και την υλοποίηση των διεπαφών της εικονικής μνήμης. Η παρούσα διατριβή συμβάλλει και προς τις δύο κατευθύνσεις. Η εκθετική αύξηση του όγκου των παγκόσμιων δεδομένων και η αντίστοιχη αύξηση των απαιτήσεων μνήμης των εφαρμογών, οδήγησαν την κυρίαρχη υλοποίηση της εικονικής μνήμης –τη σελιδοποίηση– στο λεγόμενο Τείχος Μετάφρασης (Address Translation Wall) περίπου μια δεκαετία πριν. Στην παρούσα διατριβή δείχνουμε ότι παρά το γεγονός ότι το υλικό μετάφρασης ανα επεξεργαστή τριαπλασσιάστηκε από τότε, π.χ. με την ενσωμάτωση μεγαλύτερων κρυφών μνημών αναζήτησης μετάφρασης (TLBs) η με την καλύτερη υποστήριξη των μεγάλων σελίδων, οι εφαρμογές μεγάλης έντασης δεδομένων (big data) μπορεί ακόμα να ξοδεύουν έως και το 30% του χρόνου εκτέλεσής τους στη μετάφραση διευθύνσεων – ειδικά όταν εκτελούνται σε εικονικά περιβάλλοντα. Για την αντιμετώπιση της κακής αυτής κλιμάκωσης απόδοσης της σελιδοποίησης, η παρούσα διατριβή προτείνει συνεργιστικούς μηχανισμούς λογισμικού και υλικού που δημιουργούν και εκμεταλλεύονται την ύπαρξη γραμμικότητας στις αντιστοιχίσεις εικονικών σελίδων σε φυσικές. Στο λογισμικό, προτείνουμε την Σελιδοποίηση με επίγνωση γειτνίασης (CA paging), μια νέα τεχνική διαχείρισης μνήμης που βελτιώνει τον χειριστή σφαλμάτων σελίδας του ΛΣ με υποδείξεις για την δέσμευση κατάλληλων σελίδων για τη δημιουργία μεγάλων συνεχόμενων αντιστοιχίσεων εικονικών διευθύνσεων σε φυσικές ανά διεργασία. Η σελιδοποίηση CA εφαρμόζεται τόσο σε φυσικές όσο και σε εικονικές μηχανές και διατηρεί τις ευέλικτες τεχνικές διαχείρισης μνήμης ενός σύγχρονου ΛΣ, π.χ. τη σελιδοποίηση κατ’απαίτηση και την αντιγραφή κατά την εγγραφή (CoW), ενώ αποφεύγει κάθε είδους εκ των προτέρων δέσμευση μνήμης. Υλοποιήσαμε την σελιδοποίηση CA στο ΛΣ Linux και τη διαθέτουμε ως λογισμικό ανοικτού κώδικα. Στο υλικό, για την αξιοποίηση της παραγόμενης γραμμικότητας στις απεικονίσεις, προτείνουμε την κερδοσκοπική μετάφραση διευθύνσεων με βάση τη μετατόπιση (SpOT). Το SpOT είναι μια μικρο-αρχιτεκτονική επέκταση που εκμεταλλεύεται την υποκείμενη γραμμικότητα στις αντιστοιχίσεις για να προβλέψει τη μετάφραση διευθύνσεων σε περίπτωση αστοχίας στην ιεραρχία των κρυφών μνημών TLB. Το SpOT μπορεί να εφαρμοστεί άμεσα και με διαφάνεια τόσο σε φυσικά όσο και σε εικονικά περιβάλλοντα – επειδή λειτουργεί εξ ολοκλήρου σε επίπεδο μικροαρχιτεκτονικής. Σε συνδυασμό με τη σελιδοποίηση CA, το SpOT μειώνει το κόστος μετάφρασης από ∼16,5% σε ∼0,9% κατά μέσο όρο για εφαρμογές μεγάλων δεδομένων που εκτελούνται σε εικονικές μηχανές, ανταλλάσοντας τις ισχυρές εγγυήσεις ασφάλειας (security) με εναν απλό αρχιτεκτονικό σχεδιασμό.Η εικονική μνήμη, εκτός από προγραμματιστική αφαίρεση για τη φυσική μνήμη, είναι επίσης μια σημαντική διεπαφή για την πρόσβαση στις συσκευές εισόδου-εξόδου (E/E). Οι αντιστοιχίσεις αρχείων επιτρέπουν στις εφαρμογές να έχουν πρόσβαση σε μόνιμα δεδομένα μέσω αναφορών στη μνήμη. Ωστόσο, οι συσκευές αποθήκευσης υψηλής απόδοσης έχουν εξελιχθεί σημαντικά την τελευταία δεκαετία και στις μέρες μας προσφέρουν χρόνους απόκρισης μονοψήφιους ή ακόμα και μικρότερους του δευτερολέπτου, εκθέτοντας το λογισμικό συστήματος E/E του ΛΣ ως απαγορευτικά ακριβό. Στη παρούσα διατριβή, μελετάμε την περίπτωση συσκευών μη πτητικής μνήμης (PMem) και της διεπαφής αρχείων άμεσης πρόσβασης (DAX). Με το PMem και το DAX, η εικονική μνήμη μπορεί να απεικονίσει φυσικές διευθύνσεις αποθήκευσης μόνιμων δεδομένων απευθείας στο χώρο του χρήστη, επιτρέποντας τη πρόσβαση σε μόνιμα δεδομένα μέσω εντολών load/store του επεξεργαστή. Ωστόσο, στη μελέτη μας διαπιστώνουμε ότι οι λειτουργίες της εικονικής μνήμης συχνά μειώνουν την απόδοση της άμεσης πρόσβασης, αποτυγχάνοντας να προσφέρουν αυτό που μπορεί να προσφέρει το υποκείμενο υλικό. Στη παρούσα διατριβή αναλύουμε όλες τις πηγές κόστους στη χρήση της μνήμης ως διεπαφής αρχείων και μελετάμε πως επηρεάζονται οι δαπανηροί μηχανισμοί της εικονικής μνήμης από νέες τεχνολογίες αποθήκευσης ή και εαν ακόμα γίνονται απαρχαιωμένοι. Με βάση την ανάλυσή μας, προτείνουμε μια νέα διεπαφή για γρήγορη και κλιμακώσιμη άμεση πρόσβαση σε μόνιμα δεδομένα (DaxVM). Το DaxVM είναι μια διεπαφή απεικόνισης αρχείων αποθηκευμένων σε μη-πτητικες μνήμες, που χαλαρώνει τη σημασιολογία POSIX, και υλοποιείται με επανασχεδιασμό των λειτουργιών της εικονικής μνήμης και με επέκταση των συστημάτων αρχείων για PMem – με όλες τις αλλαγές να καθοδηγούνται από τα μοναδικά χαρακτηριστικά της άμεσης πρόσβασης (dax). Το DaxVM υποστηρίζει (i) γρήγορες λειτουργίες αντιστοίχισης μνήμης (Ο(1)) μέσω μόνιμων πινάκων σελίδων ενσωματωμένων στα μεταδεδομένα του συστήματος αρχείων, (ii) τη νωχελική ακύρωση των TLB, (iii) την κλιμακώσιμη (σε πολλούς πυρήνες) διαχείριση του εικονικού χώρου διευθύνσεων για εφήμερες αντιστοιχίσεις, (iv) την εξάλειψη του κόστους δυνατότητας διαχείρισης της ανθεκτικότητας των μόνιμων δεδομένων από τον χώρο του πυρήνα όταν είναι υπεύθυνος ο χώρος χρήστη και (v) τον ασύγχρονο μηδενισμό των μπλοκ αποθήκευσης από το σύστημα αρχείων. Υλοποιήσαμε το DaxVM στο ΛΣ Linux και στα συστήματα αρχείων ext4-DAX και NOVA και το διαθέτουμε ως λογισμικό ανοιχτού κώδικα. Το αξιολογούμε σε ένα πραγματικό σύστημα εξοπλισμένο με Intel Optane. Για εφαρμογές πολλαπλών νημάτων που επεξεργάζονται πολλά μικρά αρχεία για μικρά διαστήματα, π.χ. Apache, το DaxVM βελτιώνει την απόδοση της κλήσης συστήματος mmap έως και 4,9x. Αντιστρέφει επίσης την τάση που ευνοεί τη χρήση της κλήσης συστήματος read για τέτοιες εφαρμογές, ξεπερνώντας την έως και 1,5x. Το DaxVM αυξάνει επίσης τη διαθεσιμότητα του συστήματος, παρέχοντας γρήγορους χρόνους εκκίνησης για βάσεις δεδομένων και διατηρεί υψηλή απόδοση ακόμα και όταν οι συσκευές αποθήκευσης υποφέρουν απο εξωτερικό κατακερματισμό.Συνοψίζοντας, η παρούσα διατριβή επανεξετάζει τη σχεδίαση και την υλοποίηση του μηχανισμού της εικονικής μνήμης στο σήμερα και προτείνει τεχνικές στο υλικό και στο λογισμικό που την επεκτείνουν ωστε να i) κλιμακώνει καλύτερα με τις συνεχώς αυξανόμενες χωρητικότητες της κύριας μνήμης μέσω ενός αποδοτικού μηχανισμού μετάφρασης διευθύνεσων και ii) προσφέρει μια ειδική διεπαφή αντιστοίχισης αρχείων που φέρνει την απόδοση στα όρια αυτού που μπορεί να παρέχει το υποκείμενο υλικό για άμεση πρόσβαση σε μόνιμα δεδομένα.