Add a class to allocate small objects w/o extra calls to new.

src/core/SkStackAllocator.h

Index: src/core/SkStackAllocator.h
diff --git a/src/core/SkStackAllocator.h b/src/core/SkStackAllocator.h
new file mode 100644
index 0000000000000000000000000000000000000000..bbc5fe648a51243f1a7241b4518197c6bdedf2fa
--- /dev/null
+++ b/src/core/SkStackAllocator.h
@@ -0,0 +1,144 @@
+/*
+ * Copyright 2014 Google, Inc
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+// FIXME: Move to SkSmallAllocator.h

[mtklein, 2014/03/05 20:59:56]

:)  I have found writing a git-fr (find-replace) script helps for this sort of
thing:

/m/s/skia (clean) $ cat ~/bin/git-fr
#!/bin/sh
git grep -l "$1" | xargs perl -p -i -e "s/$1/$2/g"

+#ifndef SkSmallAllocator_DEFINED
+#define SkSmallAllocator_DEFINED
+
+#include "SkTDArray.h"
+#include "SkTypes.h"
+
+// Used by SkSmallAllocator to call the destructor for objects it has
+// allocated.
+template<typename T> void destroyT(void* ptr) {
+   static_cast<T*>(ptr)->~T();
+}
+
+/*
+ *  Template class for allocating small objects without additional heap memory
+ *  allocations. kMaxObjects is a hard limit on the number of objects that can
+ *  be allocated using this class. After that, attempts to create more objects
+ *  with this class will return NULL.
+ *  kBytes is the number of bytes provided for storage. If an object is larger

[mtklein, 2014/03/05 20:59:56]

It's kBytes total?  Or kBytes per object?  E.g. if I use <2, 12>, then can I
create up to 2 objects each up to 12 bytes, or up to two objects up to 12 bytes
in total?  Trying to think about what
  typedef SkSmallAllocator<2, sizeof(SkBitmapProcShader)> SkTBlitterAllocator;
means.  I read it and its comment together as "you can allocate 0,1 or 2 objects
each <= sizeof(SkBitmapProcShader)".

[scroggo, 2014/03/05 23:23:26]

I thought this was pretty clear, but I've changed kBytes to kTotalBytes and
modified the comment a bit. The comment in SkBitmapProcShader.h is definitely
confusing. I've updated that one as well.

[mtklein, 2014/03/06 15:04:07]

Thanks!  I am no longer confused.  I see now this comment was clear and correct,
but the one in the other file was confusing.

+ *  than the storage (minus storage already used), it will be allocated on the

[mtklein, 2014/03/05 20:59:56]

Can we get away with a hard failure like for count instead of falling back on
heap?  I'd go as far as return NULL and assert in debug for both types of
overrun.  It'd be nice to know that if you're using this it just never hits
heap.

[scroggo, 2014/03/05 23:23:26]

That's a good idea. Added an assert for too many objects (and modified the test
accordingly). One concern about making the storage size a hard limit though: How
good do we think our testing coverage is? I'm not positive I know our largest
blitter. The old code falls back to the heap if the blitter is larger than
SkBitmapProcShader. If we ever had to fall back we'll have to find whatever's
bigger. (reed@, do you remember why we used sizeof(SkBitmapProcShader)? Any idea
whether we ever exceeded that?) Might there be a blitter that we don't test (or
combo blitter plus 3DBlitter) that would fail but we wouldn't catch until it
happens on a particular website? (Also, once I use this for setContext as well,
we'll have to consider a new object for each shader. And SkComposeShader allows
devious objects, as you could compose two SkComposeShaders which each are
composed of two SkComposeShaders. For those we may have to give up and use the
heap.)

[mtklein, 2014/03/06 15:04:07]

Hmm, that's a good point.  It'd be easy to see a heap fallback happen if we've
got a test that triggers it, but it's not easy to prove that no possible input
could trigger that path.  Perhaps we could SkASSERT that heap fallback does not
happen but handle it correctly anyway, and add a comment explaining we'd like it
not to happen but aren't sure if it's happening in the Chromium wild.  (Then
guard our unittest for it with #if !SK_DEBUG.)

Won't the devious SkComposeShaders overrun the hard count limit?

[scroggo, 2014/03/06 18:07:04]

That sounds like a good compromise. Done. I didn't hit the assert using our SKPs
in render pictures or in gm, tests (after modifying my test) or dm.
That may depend on how it's implemented. The plan is to ask the shader up front
how much space will be needed for the context, and count that as one object
(from the SkSmallAllocator's perspective). See
https://codereview.chromium.org/160103002/ if you're curious.

+ *  heap. This class's destructor will handle calling the destructor for each
+ *  object it allocated and freeing its memory.
+ */
+template<uint32_t kMaxObjects, size_t kBytes>
+class SkSmallAllocator : public SkNoncopyable {
+public:
+    SkSmallAllocator()
+    : fStorageUsed(0)
+    , fNumObjects(0)
+    {}
+
+    ~SkSmallAllocator() {
+        // Destruct in reverse order, in case an earlier object points to a
+        // later object.
+        while (fNumObjects > 0) {
+            fNumObjects--;
+            Rec* rec = &fRecs[fNumObjects];
+            rec->fKillProc(rec->fObj);
+            // Safe to do if fObj is in fStorage, since fHeapStorage will
+            // point to NULL.
+            sk_free(rec->fHeapStorage);
+        }
+    }
+
+    /*
+     *  Create a new object of type T. Its lifetime will be handled by this
+     *  SkSmallAllocator.
+     *  Each version behaves the same but takes a different number of
+     *  arguments.
+     *  Note: If kMaxObjects have been created by this SkSmallAllocator, NULL
+     *  will be returned.
+     */
+    template<typename T> T* createT() {

[mtklein, 2014/03/05 20:59:56]

Might want to break the line after > for all of them for consistency?

[scroggo, 2014/03/05 23:23:26]

Done.

+        void* buf = this->reserveT<T>();
+        if (NULL == buf) {
+            return NULL;
+        }
+        SkNEW_PLACEMENT(buf, T);
+        return static_cast<T*>(buf);
+    }
+
+    template<typename T, typename A1> T* createT(const A1& a1) {
+        void* buf = this->reserveT<T>();
+        if (NULL == buf) {
+            return NULL;
+        }
+        SkNEW_PLACEMENT_ARGS(buf, T, (a1));
+        return static_cast<T*>(buf);
+    }
+
+    template<typename T, typename A1, typename A2>
+    T* createT(const A1& a1, const A2& a2) {
+        void* buf = this->reserveT<T>();
+        if (NULL == buf) {
+            return NULL;
+        }
+        SkNEW_PLACEMENT_ARGS(buf, T, (a1, a2));
+        return static_cast<T*>(buf);
+    }
+
+    template<typename T, typename A1, typename A2, typename A3>
+    T* createT(const A1& a1, const A2& a2, const A3& a3) {
+        void* buf = this->reserveT<T>();
+        if (NULL == buf) {
+            return NULL;
+        }
+        SkNEW_PLACEMENT_ARGS(buf, T, (a1, a2, a3));
+        return static_cast<T*>(buf);
+    }
+
+private:
+    /*
+     *  Helper function to provide space for one T. The space will be in
+     *  fStorage if there is room, or on the heap otherwise. Either way, this
+     *  class will call ~T() in its destructor and free the heap allocation if
+     *  necessary.
+     */
+    template<typename T> void* reserveT() {
+        SkASSERT(fNumObjects <= kMaxObjects);
+        if (kMaxObjects == fNumObjects) {
+            return NULL;
+        }
+        const size_t storageRemaining = SkAlign4(kBytes) - fStorageUsed;
+        const size_t storageRequired = SkAlign4(sizeof(T));
+        Rec* rec = &fRecs[fNumObjects];
+        if (storageRequired > storageRemaining) {
+            // Allocate on the heap
+            rec->fHeapStorage = sk_malloc_throw(storageRequired);
+            rec->fObj = static_cast<void*>(rec->fHeapStorage);
+        } else {
+            // There is space in fStorage.
+            rec->fHeapStorage = NULL;
+            SkASSERT(SkIsAlign4(fStorageUsed));
+            rec->fObj = static_cast<void*>(fStorage + (fStorageUsed >> 2));

[mtklein, 2014/03/05 20:59:56]

I'm developing a preference for / 4 unless the argument is really meant to be
interpreted as bits, like an 8888 or 565 pixel.  Here we really semantically
mean "divide by 4" not "shift those bits over by two".

[scroggo, 2014/03/05 23:23:26]

Done.

+            fStorageUsed += storageRequired;
+        }
+        rec->fKillProc = destroyT<T>;
+        fNumObjects++;
+        return rec->fObj;
+    }
+
+private:
+    struct Rec {
+        void* fObj;

[mtklein, 2014/03/05 20:59:56]

Now that I'm thinking about it, it's probably not worth using tagged pointers
here for these guys.  We're not making zillions of these at a time; we're making
1 or 2.  The space used by the extra pointer isn't a big deal, especially
compared to the complexity of using tagged pointers.

+        void* fHeapStorage;
+        void  (*fKillProc)(void*);
+    };
+
+    // Number of bytes used so far.
+    size_t              fStorageUsed;
+    // Pad the storage size to be 4-byte aligned.
+    uint32_t            fStorage[SkAlign4(kBytes) >> 2];
+    uint32_t            fNumObjects;
+    Rec                 fRecs[kMaxObjects];
+};
+
+#endif // SkSmallAllocator_DEFINED