merge sort potential stack smashing

[evanmayer]

Describe the bug
Program crashes in 2nd recursion of merge() with a segfault after taking image of lens cap.

To Reproduce
Steps to reproduce the behavior:

1. Use a large sensor (e.g. 16 MP)
2. Put lens cap on
3. Use a low blob SNR threshold
4. Start program and observe crash

Expected behavior
Code handles large numbers of candidate blobs gracefully, either handling the large memory involved, or limiting the memory usage to the most important (brightest) blobs.

Screenshots

+---------------------------------------------------------+
| Server waiting for new client, 1 already connected	  |
+---------------------------------------------------------+
New client did not connect.
FC2 parameter thread sent packet to 192.168.1.4:4971
FC1 parameter thread sent packet to 192.168.1.3:4971
User 192.168.0.220 did not send any commands. Send telemetry and camera settings back anyway.
Sending telemetry: 256 bytes
Telemetry and image bytes sent back to user.

+---------------------------------------------------------+
|		Telemetry for User			  |
|---------------------------------------------------------|
|	Current rawtime: 1748978803.000000			  |
|	RA: 0.000000000000000				  |
|	DEC: 0.000000000000000				  |
|	FR: 0.000000000000000				  |
|	AZ: 0.000000000000000				  |
|	ALT: 0.000000000000000				  |
|	IR: 0.000000000000000				  |
|	PS: 0.000000					  |
|	Logodds: 10000000000.000000				  |
|	Latitude: 0.000000000000000			  |
|	Longitude: 0.000000000000000			  |
|	Height: 0.000000				  |
+---------------------------------------------------------+


Thread 16 "commands" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7fffe93ff6c0 (LWP 157018)]
0x000055555555f521 in merge (A=0x7fff78ad6010, p=0, q=188549, r=377099, X=0x7fff7c67d010, 
    Y=0x7fff7adf5010) at /media/blastcam/camera.c:2435

(gdb) bt
#0  0x000055555555f521 in merge (A=0x7fff78ad6010, p=0, q=188549, r=377099, 
    X=0x7fff7c67d010, Y=0x7fff7adf5010) at /media/blastcam/camera.c:2435
#1  0x000055555555f946 in part (A=0x7fff78ad6010, p=0, r=377099, X=0x7fff7c67d010, 
    Y=0x7fff7adf5010) at /media/blastcam/camera.c:2479
#2  0x000055555555f903 in part (A=0x7fff78ad6010, p=0, r=754199, X=0x7fff7c67d010, 
    Y=0x7fff7adf5010) at /media/blastcam/camera.c:2477
#3  0x000055555555f903 in part (A=0x7fff78ad6010, p=0, r=1508399, X=0x7fff7c67d010, 
    Y=0x7fff7adf5010) at /media/blastcam/camera.c:2477
#4  0x000055555555f127 in findBlobs (input_buffer=0x55555745e000 <unpacked_image>, 
    w=5320, h=3032, star_x=0x555559322360 <star_x>, star_y=0x555559322368 <star_y>, 
    star_mags=0x555559322370 <star_mags>, output_buffer=0x7fffb3275010)
    at /media/blastcam/camera.c:2418
#5  0x0000555555560373 in doCameraAndAstrometry () at /media/blastcam/camera.c:2816
#6  0x0000555555559acb in updateAstrometry () at /media/blastcam/commands.c:216
#7  0x00007ffff749caa4 in start_thread (arg=<optimized out>)
    at ./nptl/pthread_create.c:447
#8  0x00007ffff7529c3c in clone3 () at ../sysdeps/unix/sysv/linux/x86_64/clone3.S:78

merge() allocates temporary arrays on the stack for the sorting operation here:

void merge(double * A, int p, int q, int r, double * X, double * Y)
{
    int n1 = q - p + 1, n2 = r - q;
    int lin = n1 + 1, rin = n2 + 1;
    double LM[lin], LX[lin], LY[lin], RM[rin], RX[rin], RY[rin];
    [...]

Environment info (please complete the following information):

• PC hardware: VirtualBox Ubuntu VM, USB [https://www.ids-imaging.us/download-details/1010327.html](U3-31N0CP-M-GL Rev.2.2)
• OS: Ubuntu 20.04.2 LTS
• Software version: branch ids-peak, commit hash 5ff695e

Additional context

~1.5mil 8-byte doubles is ~12 MB, x6 arrays, so plausible for the stack to fill up. I think recursion makes this problem worse, since the stack must contend with the recursive memory usage of the upstream calls?

My preferred solution would be to never, ever call realloc (or even malloc) in real-time code. Instead, choose the maximum useful number of (real + spurious) blobs to send to astrometry.net and allocate arrays for those. Then add blobs to those buckets of storage, sorting as blobs are found, bumping off the least significant blobs until all blobs are processed. 500 seems like it would be overkill, just from intuition/experience sending a lot of images to astrometry.net.

This would have the side effect of limiting the length of time spent inside astrometry (esp. kdtree search). It's no use getting a solution to the attitude control system that is more than a few seconds old because it took forever to solve an image.

[evanmayer]

Also, even when the program doesn't crash, this combination of inputs will make the SC appear unresponsive to a client, because it will not send images or telemetry to the GUI, or telemetry to any flight computers, because it's trying to find and then process millions of candidate blobs.