SuperMem: Enabling Application-transparent Secure Persistent Memory with Low Overheads

This paper proposes SuperMem, a hardware design optimized for counter mode encryption. This paper identifies a few problems of existing counter mode encryption schemes. First, current hardware platform does not guarantee tha atomicity of persistence for more than one cache line sized block, which introduces the problem of inconsistent data block and counter value. To solve this issue, prior researches have proposed large battery-backed buffer on the memory controller to allow both the counter and the block to be buffered, upgrading the basic unit of atomicity from one cache line to two cache lines. Such a design, however, may significantly change the underlying hardware, or become difficult to implement on commercial systems. The second problem is that prior proposals do not take advantage of the potential locality in the access pattern of most applications. Counter mode encryption essentially doubles the number of cache lines written into the NVM device by updating the counter array whenever a cache line is evicted or flushed from the LLC. If care is not taken, this can easily become a performance bottleneck since the effective bandwidth of the NVM is halved. The last problem is that certain proposals change NVM programming interface by adding additional directives to the library for optimizing counter accesses. For example, in Selective Counter-Atomicity (SCA), it is observed that atomicity of updates are not required for data when undo/redo logging is used. This observation is based on the fact that when the transaction is interrupted by the crash before commit, the data updated by the transaction is inconsistent anyway, which will then be discarded by the recovery process using undo log entries or restored using redo log entries. The atomicity requirement for counter updates on these data can therefore be relaxed to avoid stalling the processor waiting for the write back to complete. In order to achieve selective atomicity of memory updates, SCA adds a special programming construct which issues counter cache write back instruction when executed, which acts like a barrier after which all pending counter and data updates are completed. The paper points out that although moderate speedup is achieved by combining SCA with logging, the change in software interface makes it difficult to use, since most logging implementations reside in the library, which is out of the control of application programmers.

The paper assumes the following baseline hardware. First, counter mode encryption is employed to provide access to the NVM, the content of which can only be accessed with a secure key. The baseline counter mode encryption works by dedicating 1/8 storage on the NVM device to store 8 byte counters for each cache line sized block on the NVM. When a cache line is evicted out of the LLC, the corresponding counter used to encrypt this line is also sent to the memory controller for persistence. The baseline design does not assume any synchronization between these two requests, and is hence susceptible to inconsistencies caused by power loss. We address this problem in SuperMem by adding an extra register to ensure that both data and counter are persisted atomically. In order to better overlap counter access and data access, a counter cache is added at the LLC level to remove NVM reads for frequently accessed counters. When a memory requests misses the LLC, the cache controller initiates two requests in parallel, one for accessing the NVM device, and the other for accessing the counter cache. Since the counter cache has lower latency than NVM, the counter value will be returned before the read completes. The cache controller then generates the OTP (One-Time Padding) using the counter, the access address, and the secret key. When the read completes, the read value is XOR’ed with the OTP, and the decoded result is sent to the cache hierarchy. This scheme avoids adding a significant number of cycles for decoding the cache line, since bitwise XOR is a fast operation.

SuperMem differs from previous propals in three aspects. First, SuperMem does not assume any extra state backed by battery (ADR) on the memory controller, and only adds one extra register for stashing counter values when the cache line is not yet available. Second, SuperMem expolits spacial locality of access by encoding counters for cache lines within a page in a way such that they can be stored in a 64 byte cache line. In addition, SuperMem also leverages the chance for coalescing writes on the counter, which reduces the number of NVM writes. Lastly, SuperMem arranges data write and counter write in such a way that the internal parallelism of the NVM device is considered. Data and counters can be written in parallel for the majority of cases.

We first describe the mechanism for avoiding using ADR to flush extra states on power failure. SuperMem adds a special stashing register on the memory controller for storing the cache line and the counter. When a cache line is evicted out of the LLC, the counter of the line is read from the counter cache (or NVM if cache misses), incremented by one, and then used to encrypt the line. After this is done, we update both the counter and the line in the following update sequence. First, after incrementing the counter, we write is back to the counter cache (evict one entry if necessary), and also add the new value of the counter to the stashing register. Then, after the data has been encoded, we send the cache line to the memory controller, which will then be added to the stashing register as well. In the last step, the memory controller reserves two entries in its internal WPQ (wait for existing requests to drain if necessary), and atomically transfers the two cache lines into its ADR-backed WPQ. The datapath and logic are extended to support atomic transfer of two cache line sized requests. Once the atomic transfer completes, both the counter and the cache line data are guaranteed to persist, since the WPQ is backed by on-chip ADR. The paper noted that by writing back the counter every time we update the NVM image, essentially the counter cache becomes write-through, and no dirty state is maintained. Eviciting an entry from the counter cache no longer needs writing back the counter value. Instead, a simple invalidation of the entry suffices.

We next describe how locality of updates can be leveraged to reduce NVM writes. The observation is that for NVM based workloads, the updates seen by the LLC and the NVM have higher than usual locality, due to the fact that updates need to be frequently flushed back to the NVM for persistence. For example, in logging based schemes, both the log entry and the in-place data should be flushed back to the NVM before the transaction commit. The high degree of locality in updates can be leveraged as shown below. First, we encode all counters within a page in a 64 byte cache line, such that the counters can be stored in a seperate cache line, and that any update operation on the page will incur an update of the same cache line. The cache line consists of one 64 bit major counter and 64 7-bit minor counters. The minor counter is incremented every time the corresponding cache line is updated, and when the minor counter overflows, all minor counters are cleared to zero, and the major counter is incremented by one, in which case we will re-encrypt all cache lines in the page. When a cache line is evicted or written back, we concatenate the major and the corresponding minor counter to generate the OTP. By co-locating all counters in a 64 byte block, when a counter value is updated, we send the updated counter cache line to the meory controller as described above. When the request for the updated counters arrive at the memory controller, the memory controller searches its WPQ for a cache line on the same address, and merges these two updates by applying the updated counter value to the existing request. The request of a counter write back is modified to indicate its type and the counters that are updated since last write back. The memory controller also marks such lines in the WPQ for efficient searching.

The third feature of SuperMem is to leverage the internal parallelism of the NVM device. The paper makes the observation that if the data update accessed back X, while the counter access also accesses back X, then these two accesses are actually serialized by the device, reducing write throughput. If, on the other hand, that the data and counter updates are mapped to different banks, then the NVM device could handle these two requests in parallel, which translates to increased bandwidth. To formalize this, the paper proposes that the storage allocated to the counter area should satisfy the requirement such that if data update is mapped to bank K, then the counter update should be mapped to (K + B / 2) % B, where B is the number of banks in the device. In other words, the counter update should always be half of the total number of banks away from the data update. The reasoning behind this is that in most address mapping schemes, adjacent cache lines are often mapped to different banks in a certain order to handle the common case of large sequential writes (e.g. logging). By always placing the bank of the counter update (B / 2) banks away from the data update, we try to minimize the chance that the current counter update will conflict with a future data update, taking advantage of the internal parallelism of the NVM device.

When a minor counter overflows within a page, all minor counters are cleared, and the major counter is incremented, as we have described in previous paragraphs. Logically speaking, this re-encrypting process must be atomic, while in reality the atomicity is not guaranteed. To fill the gap, we add another special purpose register called Re-encryption Status Register (RSR) to record the progress of page re-encoding. The RSR stores the old major counter, and a bit vector to indicate the progress of page update. If a bit is set, then the corresponding cache line has been encrypted using the new counter. The RSR register is assumed to be within the persistence domain, the value of which will be saved to the NVM device using ADR before a crash. The page re-encryption process is just like a cache line eviction, in which cache lines are re-encrypted using the new counter, and then sent to the memory controller with the updated counter. The only difference is that we also set the corresponding bit when the two requests are transferred atomically to the WPQ. Note that during a page re-encryption, the counter in the WPQ can be coalesced as we described above, which reduces the actual number of updates of the counter cache line. When the system crashes, the recovery process reads the value of the RSR to check whether there is any pending page re-encryption. If positive, the old major counter and the old minor counter is read from the RSR and NVM respectively to load cache lines that have not been re-encrypted (note that minor counters are still in their old value if the cache line has not been re-encrypted). The re-encryption process could resume after reading all lines from the NVM by completing this process for the remaining cache lines.