diff --git a/libs/hwui/Android.mk b/libs/hwui/Android.mk
index 1fb9ac5..939b9f6 100644
--- a/libs/hwui/Android.mk
+++ b/libs/hwui/Android.mk
@@ -250,7 +250,8 @@
     tests/unit/SkiaBehaviorTests.cpp \
     tests/unit/StringUtilsTests.cpp \
     tests/unit/TextDropShadowCacheTests.cpp \
-    tests/unit/VectorDrawableTests.cpp
+    tests/unit/VectorDrawableTests.cpp \
+    tests/unit/GradientCacheTests.cpp
 
 ifeq (true, $(HWUI_NEW_OPS))
     LOCAL_SRC_FILES += \
diff --git a/libs/hwui/GradientCache.cpp b/libs/hwui/GradientCache.cpp
index e899ac7..eec9ed1 100644
--- a/libs/hwui/GradientCache.cpp
+++ b/libs/hwui/GradientCache.cpp
@@ -168,10 +168,13 @@
     texture->blend = info.hasAlpha;
     texture->generation = 1;
 
-    // Asume the cache is always big enough
+    // Assume the cache is always big enough
     const uint32_t size = info.width * 2 * bytesPerPixel();
     while (getSize() + size > mMaxSize) {
-        mCache.removeOldest();
+        LOG_ALWAYS_FATAL_IF(!mCache.removeOldest(),
+                "Ran out of things to remove from the cache? getSize() = %" PRIu32
+                ", size = %" PRIu32 ", mMaxSize = %" PRIu32 ", width = %" PRIu32,
+                getSize(), size, mMaxSize, info.width);
     }
 
     generateTexture(colors, positions, info.width, 2, texture);
diff --git a/libs/hwui/tests/unit/GradientCacheTests.cpp b/libs/hwui/tests/unit/GradientCacheTests.cpp
new file mode 100644
index 0000000..5ee1705
--- /dev/null
+++ b/libs/hwui/tests/unit/GradientCacheTests.cpp
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gtest/gtest.h>
+
+#include "Extensions.h"
+#include "GradientCache.h"
+#include "tests/common/TestUtils.h"
+
+using namespace android;
+using namespace android::uirenderer;
+
+RENDERTHREAD_TEST(GradientCache, addRemove) {
+    Extensions extensions;
+    GradientCache cache(extensions);
+    cache.setMaxSize(5000);
+
+    SkColor colors[] = { 0xFF00FF00, 0xFFFF0000, 0xFF0000FF };
+    float positions[] = { 1, 2, 3 };
+    Texture* texture = cache.get(colors, positions, 3);
+    ASSERT_TRUE(texture);
+    ASSERT_FALSE(texture->cleanup);
+    ASSERT_EQ((uint32_t) texture->objectSize(), cache.getSize());
+    ASSERT_TRUE(cache.getSize());
+    cache.clear();
+    ASSERT_EQ(cache.getSize(), 0u);
+}