Stack overflow with DynamicJsonBuffer::alloc()

Created by: miloyip

I tried to use ArduinoJson to parse some JSON (several 100KBs in size) on PC (OS X), and found that it makes stack overflow, as shown as follows.

* thread #1: tid = 0x96775, 0x00007fff95ff9e3d libsystem_malloc.dylib`szone_malloc_should_clear + 42, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x7fff5f3ffff4)
  * frame #0: 0x00007fff95ff9e3d libsystem_malloc.dylib`szone_malloc_should_clear + 42
    frame #1: 0x00007fff95ff9877 libsystem_malloc.dylib`malloc_zone_malloc + 71
    frame #2: 0x00007fff95ff8395 libsystem_malloc.dylib`malloc + 42
    frame #3: 0x0000000100007c44 nativejson_debug_x64_gmake`Memory::Malloc(this=0x0000000100314378, size=56) + 36 at memorystat.h:34
    frame #4: 0x00000001000079ad nativejson_debug_x64_gmake`operator new(size=56) + 29 at memorystat.cpp:31
    frame #5: 0x000000010000b972 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::allocInOtherBlocks(this=0x0000000102d6f6c0, bytes=24) + 50 at DynamicJsonBuffer.hpp:57
    frame #6: 0x000000010000b889 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::alloc(this=0x0000000102d6f6c0, bytes=24) + 121 at DynamicJsonBuffer.hpp:33
    frame #7: 0x000000010000b9e7 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::allocInOtherBlocks(this=0x0000000102d6f680, bytes=24) + 167 at DynamicJsonBuffer.hpp:60
    frame #8: 0x000000010000b889 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::alloc(this=0x0000000102d6f680, bytes=24) + 121 at DynamicJsonBuffer.hpp:33
...
    frame #116404: 0x000000010000b889 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::alloc(this=0x0000000100c000e0, bytes=24) + 121 at DynamicJsonBuffer.hpp:33
    frame #116405: 0x000000010000b9e7 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::allocInOtherBlocks(this=0x0000000100c000a0, bytes=24) + 167 at DynamicJsonBuffer.hpp:60
    frame #116406: 0x000000010000b889 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::alloc(this=0x0000000100c000a0, bytes=24) + 121 at DynamicJsonBuffer.hpp:33
    frame #116407: 0x000000010000b9e7 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::allocInOtherBlocks(this=0x0000000100c00060, bytes=24) + 167 at DynamicJsonBuffer.hpp:60
    frame #116408: 0x000000010000b889 nativejson_debug_x64_gmake`ArduinoJson::DynamicJsonBuffer::alloc(this=0x0000000100c00060, bytes=24) + 121 at DynamicJsonBuffer.hpp:33
    frame #116409: 0x0000000100009dea nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonBufferAllocated::operator new(n=24, jsonBuffer=0x0000000100c00060) + 42 at JsonBufferAllocated.hpp:17
    frame #116410: 0x0000000100009bc8 nativejson_debug_x64_gmake`ArduinoJson::Internals::List<ArduinoJson::JsonVariant>::createNode(this=0x0000000102d6f628) + 72 at List.hpp:53
    frame #116411: 0x0000000100007f7f nativejson_debug_x64_gmake`ArduinoJson::JsonArray::add(this=0x0000000102d6f628) + 31 at JsonArray.cpp:24
    frame #116412: 0x000000010000851c nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseArray(this=0x00007fff5fbfe9a0) + 108 at JsonParser.cpp:100
    frame #116413: 0x00000001000094b0 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000102d6f6e0) + 336 at JsonParser.cpp:49
    frame #116414: 0x000000010000852d nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseArray(this=0x00007fff5fbfe9a0) + 125 at JsonParser.cpp:101
    frame #116415: 0x00000001000094b0 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000102c8ac20) + 336 at JsonParser.cpp:49
    frame #116416: 0x000000010000852d nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseArray(this=0x00007fff5fbfe9a0) + 125 at JsonParser.cpp:101
    frame #116417: 0x00000001000094b0 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000100c006b8) + 336 at JsonParser.cpp:49
    frame #116418: 0x00000001000086bc nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseObject(this=0x00007fff5fbfe9a0) + 188 at JsonParser.cpp:136
    frame #116419: 0x00000001000094d9 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000100c005f8) + 377 at JsonParser.cpp:53
    frame #116420: 0x00000001000086bc nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseObject(this=0x00007fff5fbfe9a0) + 188 at JsonParser.cpp:136
    frame #116421: 0x00000001000094d9 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000100c00140) + 377 at JsonParser.cpp:53
    frame #116422: 0x000000010000852d nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseArray(this=0x00007fff5fbfe9a0) + 125 at JsonParser.cpp:101
    frame #116423: 0x00000001000094b0 nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseAnythingTo(this=0x00007fff5fbfe9a0, destination=0x0000000100c00108) + 336 at JsonParser.cpp:49
    frame #116424: 0x00000001000086bc nativejson_debug_x64_gmake`ArduinoJson::Internals::JsonParser::parseObject(this=0x00007fff5fbfe9a0) + 188 at JsonParser.cpp:136
    frame #116425: 0x00000001000085f6 nativejson_debug_x64_gmake`ArduinoJson::JsonBuffer::parseObject(this=0x0000000100c00060, json=0x0000000102800000, nestingLimit='\n') + 54 at JsonBuffer.cpp:33
    frame #116426: 0x000000010000b4e1 nativejson_debug_x64_gmake`ArduinojsonTest::Parse(this=0x000000010031ba68, json=0x0000000100900000, length=2251051) const + 145 at arduinojsontest.cpp:97
    frame #116427: 0x0000000100005006 nativejson_debug_x64_gmake`Verify(test=0x000000010031ba68, testJsons=0x00007fff5fbff960) + 582 at main.cpp:170
    frame #116428: 0x0000000100001a36 nativejson_debug_x64_gmake`VerifyAll(testJsons=0x00007fff5fbff960) + 390 at main.cpp:291
    frame #116429: 0x000000010000100a nativejson_debug_x64_gmake`main((null)=1, argv=0x00007fff5fbffb28) + 682 at main.cpp:759
    frame #116430: 0x00007fff965545c9 libdyld.dylib`start + 1
    frame #116431: 0x00007fff965545c9 libdyld.dylib`start + 1

After investigating the code, I would like to give some suggestions:

It would be better to keep a pointer to the last block. So it doesn't need to recurse (or iterate) to obtain the last block. Then it will be O(1) instead of O(N). To reduce memory storage of additional pointer, we can create a separated Block class which contains the buffer array and next pointer. And the DynamicJsonBuffer contains the pointer to the head block and the actual first block. When adding a new block, just like inserting at the head of singly linked list:

class DynamicJsonBuffer {
public:
  DynamicJsonBuffer() : _head(&first) { ... }
private:
  struct Block {
    size_t _size;
    uint8_t _buffer[BLOCK_CAPACITY];
  };
  Block* _head;
  Block _first;
};

Other functions (size(), blockCount()) should use iteration instead of recursion.
It may be necessary to make BLOCK_CAPACITY adjustable, either in run-time or even just compile-time like macro or template parameter.