Cache VectorDrawables in an atlas

Optimize VectorDrawables for Skia pipeline: draw small VectorDrawables
in a GPU atlas instead of seprate offscreen buffers.
This implementation is using CacheManger and allows for the atlas to
be released if there is a memory pressure.

Test: A new unit test for VectorDrawableAtlas is passing. Systrace shows
0.5ms faster DrawFrame for fling in Settings app main screen.
Change-Id: Ide3884eefae777e1547f1dfdb67b807185839fb4
diff --git a/libs/hwui/Android.bp b/libs/hwui/Android.bp
index 842e053..770a57a 100644
--- a/libs/hwui/Android.bp
+++ b/libs/hwui/Android.bp
@@ -36,6 +36,7 @@
         "external/skia/src/effects",
         "external/skia/src/image",
         "external/skia/src/utils",
+        "external/skia/src/gpu",
     ],
 
     product_variables: {
@@ -133,6 +134,7 @@
         "pipeline/skia/SkiaProfileRenderer.cpp",
         "pipeline/skia/SkiaRecordingCanvas.cpp",
         "pipeline/skia/SkiaVulkanPipeline.cpp",
+        "pipeline/skia/VectorDrawableAtlas.cpp",
         "renderstate/Blend.cpp",
         "renderstate/MeshState.cpp",
         "renderstate/OffscreenBufferPool.cpp",
@@ -340,6 +342,7 @@
         "tests/unit/TextureCacheTests.cpp",
 	"tests/unit/TypefaceTests.cpp",
         "tests/unit/VectorDrawableTests.cpp",
+        "tests/unit/VectorDrawableAtlasTests.cpp",
     ],
 }
 
diff --git a/libs/hwui/VectorDrawable.cpp b/libs/hwui/VectorDrawable.cpp
index f6b2912..8a1de02 100644
--- a/libs/hwui/VectorDrawable.cpp
+++ b/libs/hwui/VectorDrawable.cpp
@@ -491,34 +491,103 @@
     return *mCache.bitmap;
 }
 
-void Tree::updateCache(sk_sp<SkSurface> surface) {
-    if (surface.get()) {
-        mCache.surface = surface;
+void Tree::updateCache(sp<skiapipeline::VectorDrawableAtlas>& atlas, GrContext* context) {
+    SkRect dst;
+    sk_sp<SkSurface> surface = mCache.getSurface(&dst);
+    bool canReuseSurface = surface && dst.width() >= mProperties.getScaledWidth()
+            && dst.height() >= mProperties.getScaledHeight();
+    if (!canReuseSurface) {
+        int scaledWidth = SkScalarCeilToInt(mProperties.getScaledWidth());
+        int scaledHeight = SkScalarCeilToInt(mProperties.getScaledHeight());
+        auto atlasEntry = atlas->requestNewEntry(scaledWidth, scaledHeight, context);
+        if (INVALID_ATLAS_KEY != atlasEntry.key) {
+            dst = atlasEntry.rect;
+            surface = atlasEntry.surface;
+            mCache.setAtlas(atlas, atlasEntry.key);
+        } else {
+            //don't draw, if we failed to allocate an offscreen buffer
+            mCache.clear();
+            surface.reset();
+        }
     }
-    if (surface.get() || mCache.dirty) {
-        SkSurface* vdSurface = mCache.surface.get();
-        SkCanvas* canvas = vdSurface->getCanvas();
-        float scaleX = vdSurface->width() / mProperties.getViewportWidth();
-        float scaleY = vdSurface->height() / mProperties.getViewportHeight();
-        SkAutoCanvasRestore acr(canvas, true);
-        canvas->clear(SK_ColorTRANSPARENT);
-        canvas->scale(scaleX, scaleY);
-        mRootNode->draw(canvas, false);
+    if (!canReuseSurface || mCache.dirty) {
+        draw(surface.get(), dst);
         mCache.dirty = false;
-        canvas->flush();
     }
 }
 
+void Tree::draw(SkSurface* surface, const SkRect& dst) {
+    if (surface) {
+        SkCanvas* canvas = surface->getCanvas();
+        float scaleX = dst.width() / mProperties.getViewportWidth();
+        float scaleY = dst.height() / mProperties.getViewportHeight();
+        SkAutoCanvasRestore acr(canvas, true);
+        canvas->translate(dst.fLeft, dst.fTop);
+        canvas->clipRect(SkRect::MakeWH(dst.width(), dst.height()));
+        canvas->clear(SK_ColorTRANSPARENT);
+        canvas->scale(scaleX, scaleY);
+        mRootNode->draw(canvas, false);
+    }
+}
+
+void Tree::Cache::setAtlas(sp<skiapipeline::VectorDrawableAtlas> newAtlas,
+        skiapipeline::AtlasKey newAtlasKey) {
+    LOG_ALWAYS_FATAL_IF(newAtlasKey == INVALID_ATLAS_KEY);
+    clear();
+    mAtlas = newAtlas;
+    mAtlasKey = newAtlasKey;
+}
+
+sk_sp<SkSurface> Tree::Cache::getSurface(SkRect* bounds) {
+    sk_sp<SkSurface> surface;
+    sp<skiapipeline::VectorDrawableAtlas> atlas = mAtlas.promote();
+    if (atlas.get() && mAtlasKey != INVALID_ATLAS_KEY) {
+        auto atlasEntry = atlas->getEntry(mAtlasKey);
+        *bounds = atlasEntry.rect;
+        surface = atlasEntry.surface;
+        mAtlasKey = atlasEntry.key;
+    }
+
+    return surface;
+}
+
+void Tree::Cache::clear() {
+    sp<skiapipeline::VectorDrawableAtlas> lockAtlas = mAtlas.promote();
+    if (lockAtlas.get()) {
+        lockAtlas->releaseEntry(mAtlasKey);
+    }
+    mAtlas = nullptr;
+    mAtlasKey = INVALID_ATLAS_KEY;
+}
+
 void Tree::draw(SkCanvas* canvas) {
-   /*
-    * TODO address the following...
-    *
-    * 1) figure out how to set path's as volatile during animation
-    * 2) if mRoot->getPaint() != null either promote to layer (during
-    *    animation) or cache in SkSurface (for static content)
-    */
-    canvas->drawImageRect(mCache.surface->makeImageSnapshot().get(),
-        mutateProperties()->getBounds(), getPaint());
+    SkRect src;
+    sk_sp<SkSurface> vdSurface = mCache.getSurface(&src);
+    if (vdSurface) {
+        canvas->drawImageRect(vdSurface->makeImageSnapshot().get(), src,
+                mutateProperties()->getBounds(), getPaint());
+    } else {
+        // Handle the case when VectorDrawableAtlas has been destroyed, because of memory pressure.
+        // We render the VD into a temporary standalone buffer and mark the frame as dirty. Next
+        // frame will be cached into the atlas.
+        int scaledWidth = SkScalarCeilToInt(mProperties.getScaledWidth());
+        int scaledHeight = SkScalarCeilToInt(mProperties.getScaledHeight());
+        SkRect src = SkRect::MakeWH(scaledWidth, scaledHeight);
+#ifndef ANDROID_ENABLE_LINEAR_BLENDING
+        sk_sp<SkColorSpace> colorSpace = nullptr;
+#else
+        sk_sp<SkColorSpace> colorSpace = SkColorSpace::MakeSRGB();
+#endif
+        SkImageInfo info = SkImageInfo::MakeN32(scaledWidth, scaledHeight, kPremul_SkAlphaType,
+                colorSpace);
+        sk_sp<SkSurface> surface = SkSurface::MakeRenderTarget(canvas->getGrContext(),
+                SkBudgeted::kYes, info);
+        draw(surface.get(), src);
+        mCache.clear();
+        canvas->drawImageRect(surface->makeImageSnapshot().get(), mutateProperties()->getBounds(),
+                getPaint());
+        markDirty();
+    }
 }
 
 void Tree::updateBitmapCache(Bitmap& bitmap, bool useStagingData) {
diff --git a/libs/hwui/VectorDrawable.h b/libs/hwui/VectorDrawable.h
index 22cfe29..efbb695 100644
--- a/libs/hwui/VectorDrawable.h
+++ b/libs/hwui/VectorDrawable.h
@@ -19,6 +19,7 @@
 
 #include "hwui/Canvas.h"
 #include "hwui/Bitmap.h"
+#include "renderthread/CacheManager.h"
 #include "DisplayList.h"
 
 #include <SkBitmap.h>
@@ -687,35 +688,61 @@
     bool getPropertyChangeWillBeConsumed() const { return mWillBeConsumed; }
     void setPropertyChangeWillBeConsumed(bool willBeConsumed) { mWillBeConsumed = willBeConsumed; }
 
-    // Returns true if VD cache surface is big enough. This should always be called from RT and it
-    // works with Skia pipelines only.
-    bool canReuseSurface() {
-        SkSurface* surface = mCache.surface.get();
-        return surface && surface->width() >= mProperties.getScaledWidth()
-              && surface->height() >= mProperties.getScaledHeight();
-    }
-
-    // Draws VD cache into a canvas. This should always be called from RT and it works with Skia
-    // pipelines only.
+    /**
+     * Draws VD cache into a canvas. This should always be called from RT and it works with Skia
+     * pipelines only.
+     */
     void draw(SkCanvas* canvas);
 
-    // Draws VD into a GPU backed surface. If canReuseSurface returns false, then "surface" must
-    // contain a new surface. This should always be called from RT and it works with Skia pipelines
-    // only.
-    void updateCache(sk_sp<SkSurface> surface);
+    /**
+     * Draws VD into a GPU backed surface.
+     * This should always be called from RT and it works with Skia pipeline only.
+     */
+    void updateCache(sp<skiapipeline::VectorDrawableAtlas>& atlas, GrContext* context);
 
 private:
-    struct Cache {
+    class Cache {
+    public:
         sk_sp<Bitmap> bitmap; //used by HWUI pipeline and software
         //TODO: use surface instead of bitmap when drawing in software canvas
-        sk_sp<SkSurface> surface; //used only by Skia pipelines
         bool dirty = true;
+
+        // the rest of the code in Cache is used by Skia pipelines only
+
+        ~Cache() { clear(); }
+
+        /**
+         * Stores a weak pointer to the atlas and a key.
+         */
+        void setAtlas(sp<skiapipeline::VectorDrawableAtlas> atlas,
+                skiapipeline::AtlasKey newAtlasKey);
+
+        /**
+         * Gets a surface and bounds from the atlas.
+         *
+         * @return nullptr if the altas has been deleted.
+         */
+        sk_sp<SkSurface> getSurface(SkRect* bounds);
+
+        /**
+         * Releases atlas key from the atlas, which makes it available for reuse.
+         */
+        void clear();
+    private:
+        wp<skiapipeline::VectorDrawableAtlas> mAtlas;
+        skiapipeline::AtlasKey mAtlasKey = INVALID_ATLAS_KEY;
     };
 
     SkPaint* updatePaint(SkPaint* outPaint, TreeProperties* prop);
     bool allocateBitmapIfNeeded(Cache& cache, int width, int height);
     bool canReuseBitmap(Bitmap*, int width, int height);
     void updateBitmapCache(Bitmap& outCache, bool useStagingData);
+
+    /**
+     * Draws the root node into "surface" at a given "dst" position.
+     */
+    void draw(SkSurface* surface, const SkRect& dst);
+
     // Cap the bitmap size, such that it won't hurt the performance too much
     // and it won't crash due to a very large scale.
     // The drawable will look blurry above this size.
diff --git a/libs/hwui/pipeline/skia/SkiaPipeline.cpp b/libs/hwui/pipeline/skia/SkiaPipeline.cpp
index 0bab793..09d758b 100644
--- a/libs/hwui/pipeline/skia/SkiaPipeline.cpp
+++ b/libs/hwui/pipeline/skia/SkiaPipeline.cpp
@@ -183,26 +183,16 @@
 };
 
 void SkiaPipeline::renderVectorDrawableCache() {
-    //render VectorDrawables into offscreen buffers
-    for (auto vd : mVectorDrawables) {
-        sk_sp<SkSurface> surface;
-        if (!vd->canReuseSurface()) {
-#ifndef ANDROID_ENABLE_LINEAR_BLENDING
-            sk_sp<SkColorSpace> colorSpace = nullptr;
-#else
-            sk_sp<SkColorSpace> colorSpace = SkColorSpace::MakeSRGB();
-#endif
-            int scaledWidth = SkScalarCeilToInt(vd->properties().getScaledWidth());
-            int scaledHeight = SkScalarCeilToInt(vd->properties().getScaledHeight());
-            SkImageInfo info = SkImageInfo::MakeN32(scaledWidth, scaledHeight,
-                    kPremul_SkAlphaType, colorSpace);
-            SkASSERT(mRenderThread.getGrContext() != nullptr);
-            surface = SkSurface::MakeRenderTarget(mRenderThread.getGrContext(), SkBudgeted::kYes,
-                    info);
+    if (!mVectorDrawables.empty()) {
+        sp<VectorDrawableAtlas> atlas = mRenderThread.cacheManager().acquireVectorDrawableAtlas();
+        auto grContext = mRenderThread.getGrContext();
+        atlas->prepareForDraw(grContext);
+        for (auto vd : mVectorDrawables) {
+            vd->updateCache(atlas, grContext);
         }
-        vd->updateCache(surface);
+        grContext->flush();
+        mVectorDrawables.clear();
     }
-    mVectorDrawables.clear();
 }
 
 void SkiaPipeline::renderFrame(const LayerUpdateQueue& layers, const SkRect& clip,
diff --git a/libs/hwui/pipeline/skia/VectorDrawableAtlas.cpp b/libs/hwui/pipeline/skia/VectorDrawableAtlas.cpp
new file mode 100644
index 0000000..437653a
--- /dev/null
+++ b/libs/hwui/pipeline/skia/VectorDrawableAtlas.cpp
@@ -0,0 +1,269 @@
+/*
+ * Copyright (C) 2017 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 "VectorDrawableAtlas.h"
+
+#include <GrRectanizer_pow2.h>
+#include <SkCanvas.h>
+#include <cmath>
+#include "utils/TraceUtils.h"
+#include "renderthread/RenderProxy.h"
+
+namespace android {
+namespace uirenderer {
+namespace skiapipeline {
+
+VectorDrawableAtlas::VectorDrawableAtlas(size_t surfaceArea, StorageMode storageMode)
+        : mWidth((int)std::sqrt(surfaceArea))
+        , mHeight((int)std::sqrt(surfaceArea))
+        , mStorageMode(storageMode) {
+}
+
+void VectorDrawableAtlas::prepareForDraw(GrContext* context) {
+    if (StorageMode::allowSharedSurface == mStorageMode) {
+        if (!mSurface) {
+            mSurface = createSurface(mWidth, mHeight, context);
+            mRectanizer = std::make_unique<GrRectanizerPow2>(mWidth, mHeight);
+            mPixelUsedByVDs = 0;
+            mPixelAllocated = 0;
+            mConsecutiveFailures = 0;
+            mFreeRects.clear();
+        } else {
+            if (isFragmented()) {
+                // Invoke repack outside renderFrame to avoid jank.
+                renderthread::RenderProxy::repackVectorDrawableAtlas();
+            }
+        }
+    }
+}
+
+#define MAX_CONSECUTIVE_FAILURES 5
+#define MAX_UNUSED_RATIO 2.0f
+
+bool VectorDrawableAtlas::isFragmented() {
+    return mConsecutiveFailures > MAX_CONSECUTIVE_FAILURES
+            && mPixelUsedByVDs*MAX_UNUSED_RATIO < mPixelAllocated;
+}
+
+void VectorDrawableAtlas::repackIfNeeded(GrContext* context) {
+    // We repackage when atlas failed to allocate space MAX_CONSECUTIVE_FAILURES consecutive
+    // times and the atlas allocated pixels are at least MAX_UNUSED_RATIO times higher than pixels
+    // used by atlas VDs.
+    if (isFragmented() && mSurface) {
+        repack(context);
+    }
+}
+
+// compare to CacheEntry objects based on VD area.
+bool VectorDrawableAtlas::compareCacheEntry(const CacheEntry& first, const CacheEntry& second)
+{
+    return first.VDrect.width()*first.VDrect.height() < second.VDrect.width()*second.VDrect.height();
+}
+
+void VectorDrawableAtlas::repack(GrContext* context) {
+    ATRACE_CALL();
+    sk_sp<SkSurface> newSurface;
+    SkCanvas* canvas = nullptr;
+    if (StorageMode::allowSharedSurface == mStorageMode) {
+        newSurface = createSurface(mWidth, mHeight, context);
+        if (!newSurface) {
+            return;
+        }
+        canvas = newSurface->getCanvas();
+        canvas->clear(SK_ColorTRANSPARENT);
+        mRectanizer = std::make_unique<GrRectanizerPow2>(mWidth, mHeight);
+    } else {
+        if (!mSurface) {
+            return; //nothing to repack
+        }
+        mRectanizer.reset();
+    }
+    mFreeRects.clear();
+    SkImage* sourceImageAtlas = nullptr;
+    if (mSurface) {
+        sourceImageAtlas = mSurface->makeImageSnapshot().get();
+    }
+
+    // Sort the list by VD size, which allows for the smallest VDs to get first in the atlas.
+    // Sorting is safe, because it does not affect iterator validity.
+    if (mRects.size() <= 100) {
+        mRects.sort(compareCacheEntry);
+    }
+
+    for (CacheEntry& entry : mRects) {
+        SkRect currentVDRect = entry.VDrect;
+        SkImage* sourceImage; //copy either from the atlas or from a standalone surface
+        if (entry.surface) {
+            if (!fitInAtlas(currentVDRect.width(), currentVDRect.height())) {
+                continue; //don't even try to repack huge VD
+            }
+            sourceImage = entry.surface->makeImageSnapshot().get();
+        } else {
+            sourceImage = sourceImageAtlas;
+        }
+        size_t VDRectArea = currentVDRect.width()*currentVDRect.height();
+        SkIPoint16 pos;
+        if (canvas && mRectanizer->addRect(currentVDRect.width(), currentVDRect.height(), &pos)) {
+            SkRect newRect = SkRect::MakeXYWH(pos.fX, pos.fY, currentVDRect.width(),
+                    currentVDRect.height());
+            canvas->drawImageRect(sourceImage, currentVDRect, newRect, nullptr);
+            entry.VDrect = newRect;
+            entry.rect = newRect;
+            if (entry.surface) {
+                // A rectangle moved from a standalone surface to the atlas.
+                entry.surface = nullptr;
+                mPixelUsedByVDs += VDRectArea;
+            }
+        } else {
+            // Repack failed for this item. If it is not already, store it in a standalone
+            // surface.
+            if (!entry.surface) {
+                // A rectangle moved from an atlas to a standalone surface.
+                mPixelUsedByVDs -= VDRectArea;
+                SkRect newRect = SkRect::MakeWH(currentVDRect.width(),
+                        currentVDRect.height());
+                entry.surface = createSurface(newRect.width(), newRect.height(), context);
+                auto tempCanvas = entry.surface->getCanvas();
+                tempCanvas->clear(SK_ColorTRANSPARENT);
+                tempCanvas->drawImageRect(sourceImageAtlas, currentVDRect, newRect, nullptr);
+                entry.VDrect = newRect;
+                entry.rect = newRect;
+            }
+        }
+    }
+    mPixelAllocated = mPixelUsedByVDs;
+    context->flush();
+    mSurface = newSurface;
+    mConsecutiveFailures = 0;
+}
+
+AtlasEntry VectorDrawableAtlas::requestNewEntry(int width, int height, GrContext* context) {
+    AtlasEntry result;
+    if (width <= 0 || height <= 0) {
+        return result;
+    }
+
+    if (mSurface) {
+        const size_t area = width*height;
+
+        // Use a rectanizer to allocate unused space from the atlas surface.
+        bool notTooBig = fitInAtlas(width, height);
+        SkIPoint16 pos;
+        if (notTooBig && mRectanizer->addRect(width, height, &pos)) {
+            mPixelUsedByVDs += area;
+            mPixelAllocated += area;
+            result.rect = SkRect::MakeXYWH(pos.fX, pos.fY, width, height);
+            result.surface = mSurface;
+            auto eraseIt = mRects.emplace(mRects.end(), result.rect, result.rect, nullptr);
+            CacheEntry* entry = &(*eraseIt);
+            entry->eraseIt = eraseIt;
+            result.key = reinterpret_cast<AtlasKey>(entry);
+            mConsecutiveFailures = 0;
+            return result;
+        }
+
+        // Try to reuse atlas memory from rectangles freed by "releaseEntry".
+        auto freeRectIt = mFreeRects.lower_bound(area);
+        while (freeRectIt != mFreeRects.end()) {
+            SkRect& freeRect = freeRectIt->second;
+            if (freeRect.width() >= width && freeRect.height() >= height) {
+                result.rect = SkRect::MakeXYWH(freeRect.fLeft, freeRect.fTop, width, height);
+                result.surface = mSurface;
+                auto eraseIt = mRects.emplace(mRects.end(), result.rect, freeRect, nullptr);
+                CacheEntry* entry = &(*eraseIt);
+                entry->eraseIt = eraseIt;
+                result.key = reinterpret_cast<AtlasKey>(entry);
+                mPixelUsedByVDs += area;
+                mFreeRects.erase(freeRectIt);
+                mConsecutiveFailures = 0;
+                return result;
+            }
+            freeRectIt++;
+        }
+
+        if (notTooBig && mConsecutiveFailures <= MAX_CONSECUTIVE_FAILURES) {
+            mConsecutiveFailures++;
+        }
+    }
+
+    // Allocate a surface for a rectangle that is too big or if atlas is full.
+    if (nullptr != context) {
+        result.rect = SkRect::MakeWH(width, height);
+        result.surface = createSurface(width, height, context);
+        auto eraseIt = mRects.emplace(mRects.end(), result.rect, result.rect, result.surface);
+        CacheEntry* entry = &(*eraseIt);
+        entry->eraseIt = eraseIt;
+        result.key = reinterpret_cast<AtlasKey>(entry);
+    }
+
+    return result;
+}
+
+AtlasEntry VectorDrawableAtlas::getEntry(AtlasKey atlasKey) {
+    AtlasEntry result;
+    if (INVALID_ATLAS_KEY != atlasKey) {
+        CacheEntry* entry = reinterpret_cast<CacheEntry*>(atlasKey);
+        result.rect = entry->VDrect;
+        result.surface = entry->surface;
+        if (!result.surface) {
+            result.surface = mSurface;
+        }
+        result.key = atlasKey;
+    }
+    return result;
+}
+
+void VectorDrawableAtlas::releaseEntry(AtlasKey atlasKey) {
+    if (INVALID_ATLAS_KEY != atlasKey) {
+        CacheEntry* entry = reinterpret_cast<CacheEntry*>(atlasKey);
+        if (!entry->surface) {
+            // Store freed atlas rectangles in "mFreeRects" and try to reuse them later, when atlas
+            // is full.
+            SkRect& removedRect = entry->rect;
+            size_t rectArea = removedRect.width()*removedRect.height();
+            mFreeRects.emplace(rectArea, removedRect);
+            SkRect& removedVDRect = entry->VDrect;
+            size_t VDRectArea = removedVDRect.width()*removedVDRect.height();
+            mPixelUsedByVDs -= VDRectArea;
+            mConsecutiveFailures = 0;
+        }
+        auto eraseIt = entry->eraseIt;
+        mRects.erase(eraseIt);
+    }
+}
+
+sk_sp<SkSurface> VectorDrawableAtlas::createSurface(int width, int height, GrContext* context) {
+#ifndef ANDROID_ENABLE_LINEAR_BLENDING
+    sk_sp<SkColorSpace> colorSpace = nullptr;
+#else
+    sk_sp<SkColorSpace> colorSpace = SkColorSpace::MakeSRGB();
+#endif
+    SkImageInfo info = SkImageInfo::MakeN32(width, height, kPremul_SkAlphaType, colorSpace);
+    return SkSurface::MakeRenderTarget(context, SkBudgeted::kYes, info);
+}
+
+void VectorDrawableAtlas::setStorageMode(StorageMode mode) {
+    mStorageMode = mode;
+    if (StorageMode::disallowSharedSurface == mStorageMode && mSurface) {
+        mSurface.reset();
+        mRectanizer.reset();
+        mFreeRects.clear();
+    }
+}
+
+} /* namespace skiapipeline */
+} /* namespace uirenderer */
+} /* namespace android */
diff --git a/libs/hwui/pipeline/skia/VectorDrawableAtlas.h b/libs/hwui/pipeline/skia/VectorDrawableAtlas.h
new file mode 100644
index 0000000..496c557
--- /dev/null
+++ b/libs/hwui/pipeline/skia/VectorDrawableAtlas.h
@@ -0,0 +1,198 @@
+/*
+ * Copyright (C) 2017 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.
+ */
+
+#pragma once
+
+#include <map>
+#include <SkSurface.h>
+#include <utils/FatVector.h>
+#include <utils/RefBase.h>
+#include <list>
+
+class GrRectanizer;
+
+namespace android {
+namespace uirenderer {
+namespace skiapipeline {
+
+typedef uintptr_t AtlasKey;
+
+#define INVALID_ATLAS_KEY 0
+
+struct AtlasEntry {
+    sk_sp<SkSurface> surface;
+    SkRect rect;
+    AtlasKey key = INVALID_ATLAS_KEY;
+};
+
+/**
+ * VectorDrawableAtlas provides offscreen buffers used to draw VD and AnimatedVD.
+ * VectorDrawableAtlas can allocate a standalone surface or provide a subrect from a shared surface.
+ * VectorDrawableAtlas is owned by the CacheManager and weak pointers are kept by each
+ * VectorDrawable that is using it. VectorDrawableAtlas and its surface can be deleted at any time,
+ * except during a renderFrame call. VectorDrawable does not contain a pointer to atlas SkSurface
+ * nor any coordinates into the atlas, but instead holds a rectangle "id", which is resolved only
+ * when drawing. This design makes VectorDrawableAtlas free to move the data internally.
+ * At draw time a VectorDrawable may find, that its atlas has been deleted, which will make it
+ * draw in a standalone cache surface not part of an atlas. In this case VD won't use
+ * VectorDrawableAtlas until the next frame.
+ * VectorDrawableAtlas tries to fit VDs in the atlas SkSurface. If there is not enough space in
+ * the atlas, VectorDrawableAtlas creates a standalone surface for each VD.
+ * When a VectorDrawable is deleted, it invokes VectorDrawableAtlas::releaseEntry, which is keeping
+ * track of free spaces and allow to reuse the surface for another VD.
+ */
+ //TODO: Check if not using atlas for AnimatedVD is more efficient.
+ //TODO: For low memory situations, when there are no paint effects in VD, we may render without an
+ //TODO: offscreen surface.
+class VectorDrawableAtlas : public virtual RefBase {
+public:
+    enum class StorageMode {
+        allowSharedSurface,
+        disallowSharedSurface
+    };
+
+    VectorDrawableAtlas(size_t surfaceArea,
+            StorageMode storageMode = StorageMode::allowSharedSurface);
+
+    /**
+     * "prepareForDraw" may allocate a new surface if needed. It may schedule to repack the
+     * atlas at a later time.
+     */
+    void prepareForDraw(GrContext* context);
+
+    /**
+     * Repack the atlas if needed, by moving used rectangles into a new atlas surface.
+     * The goal of repacking is to fix a fragmented atlas.
+     */
+    void repackIfNeeded(GrContext* context);
+
+    /**
+     * Returns true if atlas is fragmented and repack is needed.
+     */
+    bool isFragmented();
+
+    /**
+     * "requestNewEntry" is called by VectorDrawable to allocate a new rectangle area from the atlas
+     * or create a standalone surface if atlas is full.
+     * On success it returns a non-negative unique id, which can be used later with "getEntry" and
+     * "releaseEntry".
+     */
+    AtlasEntry requestNewEntry(int width, int height, GrContext* context);
+
+    /**
+     * "getEntry" extracts coordinates and surface of a previously created rectangle.
+     * "atlasKey" is an unique id created by "requestNewEntry". Passing a non-existing "atlasKey" is
+     * causing an undefined behaviour.
+     * On success it returns a rectangle Id -> may be same or different from "atlasKey" if
+     * implementation decides to move the record internally.
+     */
+    AtlasEntry getEntry(AtlasKey atlasKey);
+
+    /**
+     * "releaseEntry" is invoked when a VectorDrawable is deleted. Passing a non-existing "atlasKey"
+     * is causing an undefined behaviour.
+     */
+    void releaseEntry(AtlasKey atlasKey);
+
+    void setStorageMode(StorageMode mode);
+
+private:
+    struct CacheEntry {
+        CacheEntry(const SkRect& newVDrect, const SkRect& newRect,
+                const sk_sp<SkSurface>& newSurface)
+                : VDrect(newVDrect)
+                , rect(newRect)
+                , surface(newSurface) { }
+
+        /**
+         * size and position of VectorDrawable into the atlas or in "this.surface"
+         */
+        SkRect VDrect;
+
+        /**
+         * rect allocated in atlas surface or "this.surface". It may be bigger than "VDrect"
+         */
+        SkRect rect;
+
+        /**
+         * this surface is used if atlas is full or VD is too big
+         */
+        sk_sp<SkSurface> surface;
+
+        /**
+         * iterator is used to delete self with a constant complexity (without traversing the list)
+         */
+        std::list<CacheEntry>::iterator eraseIt;
+    };
+
+    /**
+     * atlas surface shared by all VDs
+     */
+    sk_sp<SkSurface> mSurface;
+
+    std::unique_ptr<GrRectanizer> mRectanizer;
+    const int mWidth;
+    const int mHeight;
+
+    /**
+     * "mRects" keeps records only for rectangles used by VDs. List has nice properties: constant
+     * complexity to insert and erase and references are not invalidated by insert/erase.
+     */
+    std::list<CacheEntry> mRects;
+
+    /**
+     * Rectangles freed by "releaseEntry" are removed from "mRects" and added to "mFreeRects".
+     * "mFreeRects" is using for an index the rectangle area. There could be more than one free
+     * rectangle with the same area, which is the reason to use "multimap" instead of "map".
+     */
+    std::multimap<size_t, SkRect> mFreeRects;
+
+    /**
+     * area in atlas used by VectorDrawables (area in standalone surface not counted)
+     */
+    int mPixelUsedByVDs = 0;
+
+    /**
+     * area allocated in mRectanizer
+     */
+    int mPixelAllocated = 0;
+
+    /**
+     * Consecutive times we had to allocate standalone surfaces, because atlas was full.
+     */
+    int mConsecutiveFailures = 0;
+
+    /**
+     * mStorageMode allows using a shared surface to store small vector drawables.
+     * Using a shared surface can boost the performance by allowing GL ops to be batched, but may
+     * consume more memory.
+     */
+    StorageMode mStorageMode;
+
+    sk_sp<SkSurface> createSurface(int width, int height, GrContext* context);
+
+    inline bool fitInAtlas(int width, int height) {
+        return 2*width < mWidth && 2*height < mHeight;
+    }
+
+    void repack(GrContext* context);
+
+    static bool compareCacheEntry(const CacheEntry& first, const CacheEntry& second);
+};
+
+} /* namespace skiapipeline */
+} /* namespace uirenderer */
+} /* namespace android */
diff --git a/libs/hwui/renderthread/CacheManager.cpp b/libs/hwui/renderthread/CacheManager.cpp
index f0d6b38..55694d0 100644
--- a/libs/hwui/renderthread/CacheManager.cpp
+++ b/libs/hwui/renderthread/CacheManager.cpp
@@ -43,7 +43,8 @@
 
 CacheManager::CacheManager(const DisplayInfo& display)
         : mMaxSurfaceArea(display.w * display.h) {
-    mVectorDrawableAtlas.reset(new VectorDrawableAtlas);
+    mVectorDrawableAtlas = new skiapipeline::VectorDrawableAtlas(mMaxSurfaceArea/2,
+            skiapipeline::VectorDrawableAtlas::StorageMode::allowSharedSurface);
 }
 
 void CacheManager::reset(GrContext* context) {
@@ -61,7 +62,7 @@
 void CacheManager::destroy() {
     // cleanup any caches here as the GrContext is about to go away...
     mGrContext.reset(nullptr);
-    mVectorDrawableAtlas.reset(new VectorDrawableAtlas);
+    mVectorDrawableAtlas = new skiapipeline::VectorDrawableAtlas(mMaxSurfaceArea/2);
 }
 
 void CacheManager::updateContextCacheSizes() {
@@ -104,7 +105,7 @@
 
     switch (mode) {
         case TrimMemoryMode::Complete:
-            mVectorDrawableAtlas.reset(new VectorDrawableAtlas);
+            mVectorDrawableAtlas = new skiapipeline::VectorDrawableAtlas(mMaxSurfaceArea/2);
             mGrContext->freeGpuResources();
             break;
         case TrimMemoryMode::UiHidden:
@@ -121,24 +122,14 @@
     mGrContext->purgeResourcesNotUsedInMs(std::chrono::seconds(30));
 }
 
-VectorDrawableAtlas* CacheManager::acquireVectorDrawableAtlas() {
+sp<skiapipeline::VectorDrawableAtlas> CacheManager::acquireVectorDrawableAtlas() {
     LOG_ALWAYS_FATAL_IF(mVectorDrawableAtlas.get() == nullptr);
     LOG_ALWAYS_FATAL_IF(mGrContext == nullptr);
 
     /**
-     * TODO LIST:
-     *    1) compute the atlas based on the surfaceArea surface
-     *    2) identify a way to reuse cache entries
-     *    3) add ability to repack the cache?
-     *    4) define memory conditions where we clear the cache (e.g. surface->reset())
+     * TODO: define memory conditions where we clear the cache (e.g. surface->reset())
      */
-
-    return mVectorDrawableAtlas.release();
-}
-void CacheManager::releaseVectorDrawableAtlas(VectorDrawableAtlas* atlas) {
-    LOG_ALWAYS_FATAL_IF(mVectorDrawableAtlas.get() != nullptr);
-    mVectorDrawableAtlas.reset(atlas);
-    mVectorDrawableAtlas->isNewAtlas = false;
+    return mVectorDrawableAtlas;
 }
 
 void CacheManager::dumpMemoryUsage(String8& log, const RenderState* renderState) {
diff --git a/libs/hwui/renderthread/CacheManager.h b/libs/hwui/renderthread/CacheManager.h
index 43d58f2..90362f3 100644
--- a/libs/hwui/renderthread/CacheManager.h
+++ b/libs/hwui/renderthread/CacheManager.h
@@ -22,6 +22,7 @@
 #include <ui/DisplayInfo.h>
 #include <utils/String8.h>
 #include <vector>
+#include "pipeline/skia/VectorDrawableAtlas.h"
 
 namespace android {
 
@@ -36,11 +37,6 @@
 class IRenderPipeline;
 class RenderThread;
 
-struct VectorDrawableAtlas {
-    sk_sp<SkSurface> surface;
-    bool isNewAtlas = true;
-};
-
 class CacheManager {
 public:
     enum class TrimMemoryMode {
@@ -53,8 +49,7 @@
     void trimStaleResources();
     void dumpMemoryUsage(String8& log, const RenderState* renderState = nullptr);
 
-    VectorDrawableAtlas* acquireVectorDrawableAtlas();
-    void releaseVectorDrawableAtlas(VectorDrawableAtlas*);
+    sp<skiapipeline::VectorDrawableAtlas> acquireVectorDrawableAtlas();
 
     size_t getCacheSize() const { return mMaxResourceBytes; }
     size_t getBackgroundCacheSize() const { return mBackgroundResourceBytes; }
@@ -81,7 +76,7 @@
         size_t surfaceArea = 0;
     };
 
-    std::unique_ptr<VectorDrawableAtlas> mVectorDrawableAtlas;
+    sp<skiapipeline::VectorDrawableAtlas> mVectorDrawableAtlas;
 };
 
 } /* namespace renderthread */
diff --git a/libs/hwui/renderthread/RenderProxy.cpp b/libs/hwui/renderthread/RenderProxy.cpp
index 370cf52..7fe966d 100644
--- a/libs/hwui/renderthread/RenderProxy.cpp
+++ b/libs/hwui/renderthread/RenderProxy.cpp
@@ -21,6 +21,7 @@
 #include "Properties.h"
 #include "Readback.h"
 #include "Rect.h"
+#include "pipeline/skia/VectorDrawableAtlas.h"
 #include "renderthread/CanvasContext.h"
 #include "renderthread/EglManager.h"
 #include "renderthread/RenderTask.h"
@@ -718,6 +719,19 @@
     mRenderThread.queue(task);
 }
 
+CREATE_BRIDGE1(repackVectorDrawableAtlas, RenderThread* thread) {
+    args->thread->cacheManager().acquireVectorDrawableAtlas()->repackIfNeeded(
+            args->thread->getGrContext());
+    return nullptr;
+}
+
+void RenderProxy::repackVectorDrawableAtlas() {
+    RenderThread& thread = RenderThread::getInstance();
+    SETUP_TASK(repackVectorDrawableAtlas);
+    args->thread = &thread;
+    thread.queue(task);
+}
+
 void* RenderProxy::postAndWait(MethodInvokeRenderTask* task) {
     void* retval;
     task->setReturnPtr(&retval);
diff --git a/libs/hwui/renderthread/RenderProxy.h b/libs/hwui/renderthread/RenderProxy.h
index 31f0ce6..06eaebd 100644
--- a/libs/hwui/renderthread/RenderProxy.h
+++ b/libs/hwui/renderthread/RenderProxy.h
@@ -140,6 +140,9 @@
     static void onBitmapDestroyed(uint32_t pixelRefId);
 
     ANDROID_API static void disableVsync();
+
+    static void repackVectorDrawableAtlas();
+
 private:
     RenderThread& mRenderThread;
     CanvasContext* mContext;
diff --git a/libs/hwui/tests/unit/VectorDrawableAtlasTests.cpp b/libs/hwui/tests/unit/VectorDrawableAtlasTests.cpp
new file mode 100644
index 0000000..17f8176
--- /dev/null
+++ b/libs/hwui/tests/unit/VectorDrawableAtlasTests.cpp
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2017 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 "tests/common/TestUtils.h"
+#include <GrRectanizer.h>
+#include "pipeline/skia/VectorDrawableAtlas.h"
+
+using namespace android;
+using namespace android::uirenderer;
+using namespace android::uirenderer::renderthread;
+using namespace android::uirenderer::skiapipeline;
+
+RENDERTHREAD_SKIA_PIPELINE_TEST(VectorDrawableAtlas, addGetRemove) {
+    VectorDrawableAtlas atlas(100*100);
+    atlas.prepareForDraw(renderThread.getGrContext());
+    //create 150 rects 10x10, which won't fit in the atlas (atlas can fit no more than 100 rects)
+    const int MAX_RECTS = 150;
+    AtlasEntry VDRects[MAX_RECTS];
+
+    sk_sp<SkSurface> atlasSurface;
+
+    //check we are able to allocate new rects
+    //check that rects in the atlas do not intersect
+    for (uint32_t i = 0; i < MAX_RECTS; i++) {
+        VDRects[i] = atlas.requestNewEntry(10, 10, renderThread.getGrContext());
+        if (0 == i) {
+            atlasSurface = VDRects[0].surface;
+        }
+        ASSERT_TRUE(VDRects[i].key != INVALID_ATLAS_KEY);
+        ASSERT_TRUE(VDRects[i].surface.get() != nullptr);
+        ASSERT_TRUE(VDRects[i].rect.width() == 10 && VDRects[i].rect.height() == 10);
+
+        //nothing in the atlas should intersect
+        if (atlasSurface.get() == VDRects[i].surface.get()) {
+            for (uint32_t j = 0; j < i; j++) {
+                if (atlasSurface.get() == VDRects[j].surface.get()) {
+                    ASSERT_FALSE(VDRects[i].rect.intersect(VDRects[j].rect));
+                }
+            }
+        }
+    }
+
+    //first 1/3 rects should all be in the same surface
+    for (uint32_t i = 1; i < MAX_RECTS/3; i++) {
+        ASSERT_NE(VDRects[i].key, VDRects[0].key);
+        ASSERT_EQ(VDRects[i].surface.get(), atlasSurface.get());
+    }
+
+    //first rect is using atlas and last is a standalone surface
+    ASSERT_NE(VDRects[0].surface.get(), VDRects[MAX_RECTS-1].surface.get());
+
+    //check getEntry returns the same surfaces that we had created
+    for (uint32_t i = 0; i < MAX_RECTS; i++) {
+        auto VDRect = atlas.getEntry(VDRects[i].key);
+        ASSERT_TRUE(VDRect.key != INVALID_ATLAS_KEY);
+        ASSERT_EQ(VDRects[i].key, VDRect.key);
+        ASSERT_EQ(VDRects[i].surface.get(), VDRect.surface.get());
+        ASSERT_EQ(VDRects[i].rect, VDRect.rect);
+        atlas.releaseEntry(VDRect.key);
+    }
+
+    //check that any new rects will be allocated in the atlas, even that rectanizer is full.
+    //rects in the atlas should not intersect.
+    for (uint32_t i = 0; i < MAX_RECTS/3; i++) {
+        VDRects[i] = atlas.requestNewEntry(10, 10, renderThread.getGrContext());
+        ASSERT_TRUE(VDRects[i].key != INVALID_ATLAS_KEY);
+        ASSERT_EQ(VDRects[i].surface.get(), atlasSurface.get());
+        ASSERT_TRUE(VDRects[i].rect.width() == 10 && VDRects[i].rect.height() == 10);
+        for (uint32_t j = 0; j < i; j++) {
+            ASSERT_FALSE(VDRects[i].rect.intersect(VDRects[j].rect));
+        }
+    }
+}
+
+
+RENDERTHREAD_SKIA_PIPELINE_TEST(VectorDrawableAtlas, disallowSharedSurface) {
+    VectorDrawableAtlas atlas(100*100);
+    //don't allow to use a shared surface
+    atlas.setStorageMode(VectorDrawableAtlas::StorageMode::disallowSharedSurface);
+    atlas.prepareForDraw(renderThread.getGrContext());
+    //create 150 rects 10x10, which won't fit in the atlas (atlas can fit no more than 100 rects)
+    const int MAX_RECTS = 150;
+    AtlasEntry VDRects[MAX_RECTS];
+
+    //check we are able to allocate new rects
+    //check that rects in the atlas use unique surfaces
+    for (uint32_t i = 0; i < MAX_RECTS; i++) {
+        VDRects[i] = atlas.requestNewEntry(10, 10, renderThread.getGrContext());
+        ASSERT_TRUE(VDRects[i].key != INVALID_ATLAS_KEY);
+        ASSERT_TRUE(VDRects[i].surface.get() != nullptr);
+        ASSERT_TRUE(VDRects[i].rect.width() == 10 && VDRects[i].rect.height() == 10);
+
+        //nothing in the atlas should use the same surface
+        for (uint32_t j = 0; j < i; j++) {
+            ASSERT_NE(VDRects[i].surface.get(), VDRects[j].surface.get());
+        }
+    }
+}
+
+RENDERTHREAD_SKIA_PIPELINE_TEST(VectorDrawableAtlas, repack) {
+    VectorDrawableAtlas atlas(100*100);
+    ASSERT_FALSE(atlas.isFragmented());
+    atlas.prepareForDraw(renderThread.getGrContext());
+    ASSERT_FALSE(atlas.isFragmented());
+    //create 150 rects 10x10, which won't fit in the atlas (atlas can fit no more than 100 rects)
+    const int MAX_RECTS = 150;
+    AtlasEntry VDRects[MAX_RECTS];
+
+    sk_sp<SkSurface> atlasSurface;
+
+    //fill the atlas with check we are able to allocate new rects
+    for (uint32_t i = 0; i < MAX_RECTS; i++) {
+        VDRects[i] = atlas.requestNewEntry(10, 10, renderThread.getGrContext());
+        if (0 == i) {
+            atlasSurface = VDRects[0].surface;
+        }
+        ASSERT_TRUE(VDRects[i].key != INVALID_ATLAS_KEY);
+    }
+
+    ASSERT_FALSE(atlas.isFragmented());
+
+    //first 1/3 rects should all be in the same surface
+    for (uint32_t i = 1; i < MAX_RECTS/3; i++) {
+        ASSERT_NE(VDRects[i].key, VDRects[0].key);
+        ASSERT_EQ(VDRects[i].surface.get(), atlasSurface.get());
+    }
+
+    //release all entries
+    for (uint32_t i = 0; i < MAX_RECTS; i++) {
+        auto VDRect = atlas.getEntry(VDRects[i].key);
+        ASSERT_TRUE(VDRect.key != INVALID_ATLAS_KEY);
+        atlas.releaseEntry(VDRect.key);
+    }
+
+    ASSERT_FALSE(atlas.isFragmented());
+
+    //allocate 4x4 rects, which will fragment the atlas badly, because each entry occupies a 10x10
+    //area
+    for (uint32_t i = 0; i < 4*MAX_RECTS; i++) {
+        AtlasEntry entry = atlas.requestNewEntry(4, 4, renderThread.getGrContext());
+        ASSERT_TRUE(entry.key != INVALID_ATLAS_KEY);
+    }
+
+    ASSERT_TRUE(atlas.isFragmented());
+
+    atlas.repackIfNeeded(renderThread.getGrContext());
+
+    ASSERT_FALSE(atlas.isFragmented());
+}
\ No newline at end of file