Column (libsmartcols.so) permahangs with certain inputs #3003
Description
Starting with libsmartcols version v2.39 or newer, I started noticing the column command hanging under specific situations. I was able to track it down to specific inputs and arguments causing the column command to hang with my specific arguments.
I've reproduced it on 2.39-rc1, 2.39, 2.39.1, 2.39.2, 2.39.3, 2.39.4, and 2.40 (and the latest master: 926b607) . It doesn't seem to matter what the exact character in the text input, but as long as the lengths of the fields are the same, the hang happens.
Reproducing the error
Since the math in reduce seems to vary a little from version to version, most of my more realistic examples only fail in a few versions, but after experimenting and reducing the amount of data needed to cause the error, I was finally able to make a file that appears to hang on all tested versions of libsmartcols.
Bad file
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x
x
x
Test commands
# Fails with 2.39.3
docker run -it --rm -e LIBSMARTCOLS_DEBUG=all alpine:3.19 sh -c "apk add util-linux; printf 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\nx\nx\nx\n' | timeout 1 column -c1 -t"
# Fail with 2.39.4
docker run -it --rm -e LIBSMARTCOLS_DEBUG=all fedora:39 sh -c "dnf install -y util-linux; printf 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\nx\nx\nx\n' | timeout 1 column -c1 -t"
# Fails with 2.40
docker run -it --rm -e LIBSMARTCOLS_DEBUG=all alpine:20240329 sh -c "apk add util-linux; printf 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\nx\nx\nx\n' | timeout 1 column -c1 -t"
Workarounds
- Setting
-c1to-c2makes the hang go away in my tests, but I'm guessing there are just different conditions that might make it fail on-c2. Given the me inability to predict what causes this, I don't know if this really works around the issue or just changes what patterns cause the hang - Removing
-c1altogether also seems to fix the issue
Additionally gathered information
- I tried using column 2.38 with libsmartcols 2.39, and observe the hang
- I tried using column 2.39 with libsmartcols 2.38, and did no observe the hang.
This is what led me to believe the issue is in libsmartcols somewhere
It looks like the reduce code changes a little between 2.38 and 2.39. It was also hard to reproduce in all the versions, as the same file didn't not necessarily hang on all the different versions. I suspect the math behind reduce changed in the different versions, and use average and deviation, but I'm just guessing as I didn't look too deeply into it.
2.39.4
4013986: libsmartcols: TAB: [0x5626b97f8e10]: -----calculate-(termwidth=1)-----
4013986: libsmartcols: COL: [0x5626b97f8f40]: (null) seq=0, width=34, hint=0, max=34, min=1, 0x040 []
4013986: libsmartcols: COL: [0x5626b97f9130]: (null) seq=1, width=56, hint=0, max=56, min=1, 0x0410 [ noextrem]
4013986: libsmartcols: COL: [0x5626b97f8f40]: (null) avg=26, deviation=5.34522
4013986: libsmartcols: COL: [0x5626b97f9130]: (null) avg=15.625, deviation=16.7923
4013986: libsmartcols: TAB: [0x5626b97f8e10]: sorting by deviation
4013986: libsmartcols: COL: [0x5626b97f8f40]: (null) seq=0, width=34, hint=0, max=34, min=1, 0x040 []
4013986: libsmartcols: COL: [0x5626b97f9130]: (null) seq=1, width=56, hint=0, max=56, min=1, 0x0410 [ noextrem]
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #0 reduce stage (width=92, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 56-->32
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #0 reduce stage (width=68, term=1)
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #1 reduce stage (width=68, term=1)
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #2 reduce stage (width=68, term=1)
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #3 reduce stage (width=68, term=1)
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #4 reduce stage (width=68, term=1)
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=68, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 32-->29
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=65, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 29-->26
...
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=38, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 2-->18446744073709551615
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=35, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 18446744073709551615-->18446744073709551612
...
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=2, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 18446744073709551582-->18446744073709551579
4013986: libsmartcols: TAB: [0x5626b97f8e10]: #5 reduce stage (width=18446744073709551615, term=1)
4013986: libsmartcols: COL: [0x5626b97f9130]: [01] (null) reduced 18446744073709551579-->18446744073709551576
...
∞
In v2.39 or newer, it appears to continuously subtract, and occasionally hits a uint64 wrap around (which I'm guessing is more likely with small versions of -c