ImDrawList::AddPolyline stack overflow on large polylines #5704

Closed
opened 2022-09-23 18:04:10 +00:00 by azonenberg · 2 comments
azonenberg commented 2022-09-23 18:04:10 +00:00 (Migrated from github.com)

The AddPolyline() function uses alloca() for temporary variables even with very large polylines (tens of thousands to millions of segments). This can lead to stack overflows.

=================================================================
==337686==ERROR: AddressSanitizer: stack-overflow on address 0x7fffa45456b8 (pc 0x5653344a17d0 bp 0x7fffa5c290a0 sp 0x7fffa45456c0 T0)
    #0 0x5653344a17d0 in ImDrawList::AddPolyline(ImVec2 const*, int, unsigned int, int, float) /ceph/fast/home/azonenberg/code/scopehal-apps/src/imgui/imgui_draw.cpp:764
    #1 0x565334410a2d in ImDrawList::PathStroke(unsigned int, int, float) /ceph/fast/home/azonenberg/code/scopehal-apps/src/imgui/imgui.h:2681
    #2 0x56533503f201 in WaveformArea::RenderAnalogWaveform(StreamDescriptor, ImVec2, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:331
    #3 0x56533503eda7 in WaveformArea::RenderWaveforms(ImVec2, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:298
    #4 0x56533503e4c1 in WaveformArea::Render(int, int, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:248
    #5 0x56533505b3c7 in WaveformGroup::Render() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformGroup.cpp:106
    #6 0x565334eddc08 in MainWindow::RenderUI() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/MainWindow.cpp:286
    #7 0x56533501ea93 in VulkanWindow::Render() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/VulkanWindow.cpp:296
    #8 0x565335063cd3 in main /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/main.cpp:142
    #9 0x7f5c8b75bd09 in __libc_start_main ../csu/libc-start.c:308
    #10 0x56533433cdc9 in _start (/ceph/fast/home/azonenberg/code/scopehal-apps/asan-build/src/ngscopeclient/ngscopeclient+0x220dc9)

This is not a major blocker for my application, which will be using custom shaders for large graphs in the future. I tried to use ImDrawList as a temporary debug visualization and apparently it can't handle it :)

But there should be, at minimum, a better failure mode such as throwing an assertion or falling back to malloc()'d memory. And any hard limits on primitive count should be documented somewhere.

The AddPolyline() function uses alloca() for temporary variables even with very large polylines (tens of thousands to millions of segments). This can lead to stack overflows. ``` ================================================================= ==337686==ERROR: AddressSanitizer: stack-overflow on address 0x7fffa45456b8 (pc 0x5653344a17d0 bp 0x7fffa5c290a0 sp 0x7fffa45456c0 T0) #0 0x5653344a17d0 in ImDrawList::AddPolyline(ImVec2 const*, int, unsigned int, int, float) /ceph/fast/home/azonenberg/code/scopehal-apps/src/imgui/imgui_draw.cpp:764 #1 0x565334410a2d in ImDrawList::PathStroke(unsigned int, int, float) /ceph/fast/home/azonenberg/code/scopehal-apps/src/imgui/imgui.h:2681 #2 0x56533503f201 in WaveformArea::RenderAnalogWaveform(StreamDescriptor, ImVec2, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:331 #3 0x56533503eda7 in WaveformArea::RenderWaveforms(ImVec2, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:298 #4 0x56533503e4c1 in WaveformArea::Render(int, int, ImVec2) /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformArea.cpp:248 #5 0x56533505b3c7 in WaveformGroup::Render() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/WaveformGroup.cpp:106 #6 0x565334eddc08 in MainWindow::RenderUI() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/MainWindow.cpp:286 #7 0x56533501ea93 in VulkanWindow::Render() /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/VulkanWindow.cpp:296 #8 0x565335063cd3 in main /ceph/fast/home/azonenberg/code/scopehal-apps/src/ngscopeclient/main.cpp:142 #9 0x7f5c8b75bd09 in __libc_start_main ../csu/libc-start.c:308 #10 0x56533433cdc9 in _start (/ceph/fast/home/azonenberg/code/scopehal-apps/asan-build/src/ngscopeclient/ngscopeclient+0x220dc9) ``` This is not a major blocker for my application, which will be using custom shaders for large graphs in the future. I tried to use ImDrawList as a temporary debug visualization and apparently it can't handle it :) But there should be, at minimum, a better failure mode such as throwing an assertion or falling back to malloc()'d memory. And any hard limits on primitive count should be documented somewhere.
ocornut commented 2022-09-26 09:29:15 +00:00 (Migrated from github.com)

Now that we have access to a shared ImDrawListSharedData instance I think it would be reasonable to turn this into a reused ImVector and use reserve_discard(). I may investigate this.

Also note #1811 could still potentially apply but is a separate task.

Now that we have access to a shared ImDrawListSharedData instance I think it would be reasonable to turn this into a reused ImVector and use reserve_discard(). I may investigate this. Also note #1811 could still potentially apply but is a separate task.
ocornut commented 2022-09-30 14:01:55 +00:00 (Migrated from github.com)

Pushed this change f2a522d, no notable change.

image
image

I even forgot to use reserve_discard() (instead of reserve()) when I took those number, so amortization will be faster.

Note we do not have a policy for freeing that shared buffer, so if you throw a million points at it it won't be freed.

We could use a moving-average approximation (without storage) to shrink back

Pushed this change f2a522d, no notable change. ![image](https://user-images.githubusercontent.com/8225057/193282174-824e3466-85da-4332-a95d-e61621902ed1.png) ![image](https://user-images.githubusercontent.com/8225057/193282294-9b43e206-22de-4f65-b58e-ee4fa13176b6.png) I even forgot to use reserve_discard() (instead of `reserve()`) when I took those number, so amortization will be faster. Note we do not have a policy for freeing that shared buffer, so if you throw a million points at it it won't be freed. We could use a moving-average approximation (without storage) to shrink back
Sign in to join this conversation.
No milestone
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
ocornut/imgui#5704
No description provided.