diff --git a/fs_mgr/fs_mgr_verity.c b/fs_mgr/fs_mgr_verity.c
index a4a99c3..eddc3e4 100644
--- a/fs_mgr/fs_mgr_verity.c
+++ b/fs_mgr/fs_mgr_verity.c
@@ -47,6 +47,8 @@
 
 #define VERITY_METADATA_SIZE 32768
 #define VERITY_TABLE_RSA_KEY "/verity_key"
+#define VERITY_TABLE_HASH_IDX 8
+#define VERITY_TABLE_SALT_IDX 9
 
 #define METADATA_MAGIC 0x01564c54
 #define METADATA_TAG_MAX_LENGTH 63
@@ -141,6 +143,33 @@
     return retval;
 }
 
+static int invalidate_table(char *table, int table_length)
+{
+    int n = 0;
+    int idx = 0;
+    int cleared = 0;
+
+    while (n < table_length) {
+        if (table[n++] == ' ') {
+            ++idx;
+        }
+
+        if (idx != VERITY_TABLE_HASH_IDX && idx != VERITY_TABLE_SALT_IDX) {
+            continue;
+        }
+
+        while (n < table_length && table[n] != ' ') {
+            table[n++] = '0';
+        }
+
+        if (++cleared == 2) {
+            return 0;
+        }
+    }
+
+    return -1;
+}
+
 static int squashfs_get_target_device_size(char *blk_device, uint64_t *device_size)
 {
     struct squashfs_info sq_info;
@@ -957,6 +986,7 @@
     char *verity_blk_name = 0;
     char *verity_table = 0;
     char *verity_table_signature = 0;
+    int verity_table_length = 0;
     uint64_t device_size = 0;
 
     _Alignas(struct dm_ioctl) char buffer[DM_BUF_SIZE];
@@ -979,6 +1009,7 @@
     }
 
     retval = FS_MGR_SETUP_VERITY_FAIL;
+    verity_table_length = strlen(verity_table);
 
     // get the device mapper fd
     if ((fd = open("/dev/device-mapper", O_RDWR)) < 0) {
@@ -998,13 +1029,6 @@
         goto out;
     }
 
-    // verify the signature on the table
-    if (verify_table(verity_table_signature,
-                            verity_table,
-                            strlen(verity_table)) < 0) {
-        goto out;
-    }
-
     if (load_verity_state(fstab, &mode) < 0) {
         /* if accessing or updating the state failed, switch to the default
          * safe mode. This makes sure the device won't end up in an endless
@@ -1013,6 +1037,22 @@
         mode = VERITY_MODE_EIO;
     }
 
+    // verify the signature on the table
+    if (verify_table(verity_table_signature,
+                            verity_table,
+                            verity_table_length) < 0) {
+        if (mode == VERITY_MODE_LOGGING) {
+            // the user has been warned, allow mounting without dm-verity
+            retval = FS_MGR_SETUP_VERITY_SUCCESS;
+            goto out;
+        }
+
+        // invalidate root hash and salt to trigger device-specific recovery
+        if (invalidate_table(verity_table, verity_table_length) < 0) {
+            goto out;
+        }
+    }
+
     INFO("Enabling dm-verity for %s (mode %d)\n",  mount_point, mode);
 
     // load the verity mapping table
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
index cd9d7f9..7818b4e 100644
--- a/include/utils/LruCache.h
+++ b/include/utils/LruCache.h
@@ -17,8 +17,11 @@
 #ifndef ANDROID_UTILS_LRU_CACHE_H
 #define ANDROID_UTILS_LRU_CACHE_H
 
+#include <unordered_set>
+
 #include <UniquePtr.h>
-#include <utils/BasicHashtable.h>
+
+#include "utils/TypeHelpers.h"  // hash_t
 
 namespace android {
 
@@ -36,6 +39,7 @@
 class LruCache {
 public:
     explicit LruCache(uint32_t maxCapacity);
+    virtual ~LruCache();
 
     enum Capacity {
         kUnlimitedCapacity,
@@ -50,32 +54,6 @@
     void clear();
     const TValue& peekOldestValue();
 
-    class Iterator {
-    public:
-        Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
-        }
-
-        bool next() {
-            mIndex = mCache.mTable->next(mIndex);
-            return (ssize_t)mIndex != -1;
-        }
-
-        size_t index() const {
-            return mIndex;
-        }
-
-        const TValue& value() const {
-            return mCache.mTable->entryAt(mIndex).value;
-        }
-
-        const TKey& key() const {
-            return mCache.mTable->entryAt(mIndex).key;
-        }
-    private:
-        const LruCache<TKey, TValue>& mCache;
-        size_t mIndex;
-    };
-
 private:
     LruCache(const LruCache& that);  // disallow copy constructor
 
@@ -90,27 +68,79 @@
         const TKey& getKey() const { return key; }
     };
 
+    struct HashForEntry : public std::unary_function<Entry*, hash_t> {
+        size_t operator() (const Entry* entry) const {
+            return hash_type(entry->key);
+        };
+    };
+
+    struct EqualityForHashedEntries : public std::unary_function<Entry*, hash_t> {
+        bool operator() (const Entry* lhs, const Entry* rhs) const {
+            return lhs->key == rhs->key;
+        };
+    };
+
+    typedef std::unordered_set<Entry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
+
     void attachToCache(Entry& entry);
     void detachFromCache(Entry& entry);
-    void rehash(size_t newCapacity);
 
-    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+    typename LruCacheSet::iterator findByKey(const TKey& key) {
+        Entry entryForSearch(key, mNullValue);
+        typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
+        return result;
+    }
+
+    UniquePtr<LruCacheSet> mSet;
     OnEntryRemoved<TKey, TValue>* mListener;
     Entry* mOldest;
     Entry* mYoungest;
     uint32_t mMaxCapacity;
     TValue mNullValue;
+
+public:
+    class Iterator {
+    public:
+        Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIterator(mCache.mSet->begin()) {
+        }
+
+        bool next() {
+            if (mIterator == mCache.mSet->end()) {
+                return false;
+            }
+            std::advance(mIterator, 1);
+            return mIterator != mCache.mSet->end();
+        }
+
+        const TValue& value() const {
+            return (*mIterator)->value;
+        }
+
+        const TKey& key() const {
+            return (*mIterator)->key;
+        }
+    private:
+        const LruCache<TKey, TValue>& mCache;
+        typename LruCacheSet::iterator mIterator;
+    };
 };
 
 // Implementation is here, because it's fully templated
 template <typename TKey, typename TValue>
 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
-    : mTable(new BasicHashtable<TKey, Entry>)
+    : mSet(new LruCacheSet())
     , mListener(NULL)
     , mOldest(NULL)
     , mYoungest(NULL)
     , mMaxCapacity(maxCapacity)
     , mNullValue(NULL) {
+    mSet->max_load_factor(1.0);
+};
+
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::~LruCache() {
+    // Need to delete created entries.
+    clear();
 };
 
 template<typename K, typename V>
@@ -120,20 +150,19 @@
 
 template <typename TKey, typename TValue>
 size_t LruCache<TKey, TValue>::size() const {
-    return mTable->size();
+    return mSet->size();
 }
 
 template <typename TKey, typename TValue>
 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
-    hash_t hash = hash_type(key);
-    ssize_t index = mTable->find(-1, hash, key);
-    if (index == -1) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
         return mNullValue;
     }
-    Entry& entry = mTable->editEntryAt(index);
-    detachFromCache(entry);
-    attachToCache(entry);
-    return entry.value;
+    Entry *entry = *find_result;
+    detachFromCache(*entry);
+    attachToCache(*entry);
+    return entry->value;
 }
 
 template <typename TKey, typename TValue>
@@ -142,36 +171,29 @@
         removeOldest();
     }
 
-    hash_t hash = hash_type(key);
-    ssize_t index = mTable->find(-1, hash, key);
-    if (index >= 0) {
+    if (findByKey(key) != mSet->end()) {
         return false;
     }
-    if (!mTable->hasMoreRoom()) {
-        rehash(mTable->capacity() * 2);
-    }
 
-    // Would it be better to initialize a blank entry and assign key, value?
-    Entry initEntry(key, value);
-    index = mTable->add(hash, initEntry);
-    Entry& entry = mTable->editEntryAt(index);
-    attachToCache(entry);
+    Entry* newEntry = new Entry(key, value);
+    mSet->insert(newEntry);
+    attachToCache(*newEntry);
     return true;
 }
 
 template <typename TKey, typename TValue>
 bool LruCache<TKey, TValue>::remove(const TKey& key) {
-    hash_t hash = hash_type(key);
-    ssize_t index = mTable->find(-1, hash, key);
-    if (index < 0) {
+    typename LruCacheSet::const_iterator find_result = findByKey(key);
+    if (find_result == mSet->end()) {
         return false;
     }
-    Entry& entry = mTable->editEntryAt(index);
+    Entry* entry = *find_result;
     if (mListener) {
-        (*mListener)(entry.key, entry.value);
+        (*mListener)(entry->key, entry->value);
     }
-    detachFromCache(entry);
-    mTable->removeAt(index);
+    detachFromCache(*entry);
+    mSet->erase(entry);
+    delete entry;
     return true;
 }
 
@@ -201,7 +223,10 @@
     }
     mYoungest = NULL;
     mOldest = NULL;
-    mTable->clear();
+    for (auto entry : *mSet.get()) {
+        delete entry;
+    }
+    mSet->clear();
 }
 
 template <typename TKey, typename TValue>
@@ -232,19 +257,5 @@
     entry.child = NULL;
 }
 
-template <typename TKey, typename TValue>
-void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
-    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
-    Entry* oldest = mOldest;
-
-    mOldest = NULL;
-    mYoungest = NULL;
-    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
-    for (Entry* p = oldest; p != NULL; p = p->child) {
-        put(p->key, p->value);
-    }
 }
-
-}
-
 #endif // ANDROID_UTILS_LRU_CACHE_H
diff --git a/include/utils/String16.h b/include/utils/String16.h
index b2ab5dc..9a67c7a 100644
--- a/include/utils/String16.h
+++ b/include/utils/String16.h
@@ -65,8 +65,6 @@
     
     inline  const char16_t*     string() const;
     
-            const SharedBuffer* sharedBuffer() const;
-    
             size_t              size() const;
             void                setTo(const String16& other);
             status_t            setTo(const char16_t* other);
diff --git a/include/utils/String8.h b/include/utils/String8.h
index a8a37db..2a75b98 100644
--- a/include/utils/String8.h
+++ b/include/utils/String8.h
@@ -28,7 +28,6 @@
 
 namespace android {
 
-class SharedBuffer;
 class String16;
 class TextOutput;
 
@@ -69,7 +68,6 @@
     inline  bool                isEmpty() const;
     
             size_t              length() const;
-            const SharedBuffer* sharedBuffer() const;
     
             void                clear();
 
diff --git a/libutils/String16.cpp b/libutils/String16.cpp
index 67be9d8..6a5273f 100644
--- a/libutils/String16.cpp
+++ b/libutils/String16.cpp
@@ -171,11 +171,6 @@
     return SharedBuffer::sizeFromData(mString)/sizeof(char16_t)-1;
 }
 
-const SharedBuffer* String16::sharedBuffer() const
-{
-    return SharedBuffer::bufferFromData(mString);
-}
-
 void String16::setTo(const String16& other)
 {
     SharedBuffer::bufferFromData(other.mString)->acquire();
diff --git a/libutils/String8.cpp b/libutils/String8.cpp
index 5e85520..81bfccf 100644
--- a/libutils/String8.cpp
+++ b/libutils/String8.cpp
@@ -217,11 +217,6 @@
     return SharedBuffer::sizeFromData(mString)-1;
 }
 
-const SharedBuffer* String8::sharedBuffer() const
-{
-    return SharedBuffer::bufferFromData(mString);
-}
-
 String8 String8::format(const char* fmt, ...)
 {
     va_list args;
diff --git a/libutils/tests/LruCache_test.cpp b/libutils/tests/LruCache_test.cpp
index 6155def..2ed84d7 100644
--- a/libutils/tests/LruCache_test.cpp
+++ b/libutils/tests/LruCache_test.cpp
@@ -221,7 +221,7 @@
     cache.put(ComplexKey(0), ComplexValue(0));
     cache.put(ComplexKey(1), ComplexValue(1));
     EXPECT_EQ(2U, cache.size());
-    assertInstanceCount(2, 3);  // the null value counts as an instance
+    assertInstanceCount(2, 3);  // the member mNullValue counts as an instance
 }
 
 TEST_F(LruCacheTest, Clear) {