Skip to content
  • Michael Roth's avatar
    json-parser: don't replicate tokens at each level of recursion · 65c0f1e9
    Michael Roth authored
    
    
    Currently, when parsing a stream of tokens we make a copy of the token
    list at the beginning of each level of recursion so that we do not
    modify the original list in cases where we need to fall back to an
    earlier state.
    
    In the worst case, we will only read 1 or 2 tokens off the list before
    recursing again, which means an upper bound of roughly N^2 token allocations.
    
    For a "reasonably" sized QMP request (in this a QMP representation of
    cirrus_vga's device state, generated via QIDL, being passed in via
    qom-set), this caused my 16GB's of memory to be exhausted before any
    noticeable progress was made by the parser.
    
    This patch works around the issue by using single copy of the token list
    in the form of an indexable array so that we can save/restore state by
    manipulating indices.
    
    A subsequent commit adds a "large_dict" test case which exhibits the
    same behavior as above. With this patch applied the test case successfully
    completes in under a second.
    
    Tested with valgrind, make check, and QMP.
    
    Reviewed-by: default avatarEric Blake <eblake@redhat.com>
    Signed-off-by: default avatarMichael Roth <mdroth@linux.vnet.ibm.com>
    Signed-off-by: default avatarAnthony Liguori <aliguori@us.ibm.com>
    65c0f1e9