17 ms·

Parsing can become accidentally quadratic because of sscanf

510 points by JdeBP 6y ago

ufo 6y ago
In case anyone missed it, this sscanf behavior was the cause of the long loading times in GTA V, a story that hit the front page yesterday: https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339
- aparsons 6y ago
  That was a brilliant investigation. Reminded me of when I used to work on Windows debuggers. I wish the author touched on symbolization more. That is where a lot of the fun lies when dissecting precompiled binaries.
  - jjoonathan 6y ago
    What are the tools for symbolization? I recently spent a lot of time laboriously propagating RTTI information around Visual C++ binaries by hand in Ghidra, so I would be very interested in learning about this tooling, even if it's all IDA for now.
    - wcarss 6y ago
      just a little related: I watched a guy step'n'watch the no-symbols code once after he hooked WINDBG up to an MS Office process that had a paint issue. He narrowed it down to something IME was doing -- I gained nothing but awe.
    - aparsons 6y ago
      It has been 2-3 decades since I’ve worked on this, so this may be outdated advice. In fact, I just learned of Ghidra when I read the article. In general there are three cases: - Developer forgot to strip/obfuscate symbols, in which case you’re golden - Symbol you seek is in a shared library: patch the DLL. Often what we did was do investigations in a VM, where the n most common shared library calls were patched to send stack and symbol data to a local DB. Very similar play to RR, but only in the patched code. - If the (missing) symbol you seek is pre linked (static), things get interesting. We built a pattern matcher that was incredible. Idea is, if you have the disassembly and a loop, like: int fun(char* str) { call processChar on each uppercase character } It pattern matched a name like rax_foreach_iflte_cx_call_obfuscatedSymbolForProcessChar 90+% of code either: - enters the same dynamic library trampoline - displays very very common programming patterns. From what I know, we never released this outside early MS DN members because the 10% is often very useful code and developer tools weren’t given away for free yet. But once the DLL is patched, you propagate names up graph. Any remaining symbols were hand annotated (and we run the propagator again). Brian Parks went on to extend this system to work with C++ templates. C++ mangling is very predictable, so his program could scavenge for symbols (obfuscators only worked on the root symbol name) and build out the class at compile time for us to reference.
  - saagarjha 6y ago
    I'm sure that symbols were not mentioned much as the code was from an obfuscated game engine.
- masklinn 6y ago
  Well half the cause (or probably two thirds), as the post shows there’s a second quadratic blowup when filling the not-a-hashmap thing after the very slow parsing has completed.
  - crowbahr 6y ago
    A filling that wasn't even required because it was de-duping already de-duped data instead of just inserting it into a list (or a hashmap, as suggested in the post).
    - masklinn 6y ago
      The filling was necessary, but the deduplication (in linear time as it works over an array) indeed was not as the input is unique. I can see why the devs would not trust that though. So it’s the inefficiency of the dedup’ which bugs me more than the dedup itself.
dividuum 6y ago
Seen the GTA post already and the sscanf behavior is very surprising as one would expect it to parse the given string until the given format is satisfied or \0 is hit. Seems like this is not the case. Found this: https://stackoverflow.com/a/23924112 https://stackoverflow.com/a/23924112 > sscanf() converts the string you pass in to an _IO_FILE* to make the string look like a "file". This is so the same internal _IO_vfscanf() can be used for both a string and a FILE*. However, as part of that conversion, done in a _IO_str_init_static_internal() function, it calls __rawmemchr (ptr, '\0'); essentially a strlen() call, on your input string. Looks correct. Call flow: https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/stdio-common/sscanf.c#L34 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/libio/strfile.h#L90 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/libio/strops.c#L41 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/83908b3a1ea51e3aa7ff422275940e56dbba989f/string/rawmemchr.c#L39-L45 https://github.com/bminor/glibc/blob/83908b3a1ea51e3aa7ff422...
- kazinator 6y ago
  By itself, that doesn't add up to N-squared behavior, though. > It looks like the problem is that reading floats is done using c4::from_chars -> c4::atof -> sscanf which ultimately calls _IO_str_init_static_internal in the glibc implementation. As far as I understand, this essentially causes strlen to be called on the string that rapidyaml passes to it, essentially causing strlen to be called O(n^2) times. As such, this doesn't follow. Just because sscanf takes the length of the entire source string doesn't mean will get N^2 behavior, unless you do silly things with sscanf, like extract a small token from the beginning of a large string, and then skip past it to do the same thing again after that small token: essentially, build a lexical analyzer in which the pattern matcher consists of calls to scanf. This is not an intended use case for sscanf. No self-respecting language parser designer would do such a thing in a non-throwaway, production program. sscanf has undefined behaviors for out-of-range numeric values, so you can't use it for just blindly extracting numeric tokens at all, regardless of any other issues. sscanf should only be used on a string that your program has either prepared itself, or carefully delimited by some other means. For instance, suppose we have a string which holds a date (could be an input to the program). We can test whether it's in the YYYY-MM-DD format, and get those values out: int year, month, day; char junk; if (sscanf(input, "%4d-%2d-%2d%c", &year, &month, &day, &junk) == 3) { /* we got it */ } The purpose of junk is to test that there is no trailing garbage character. If there is, it will be scanned and the return value will be 4. If we don't care about that, we can just omit that argument and conversion specifier. This will accept inputs like 01-1-1. Worse, it will scan leading signs! If you wan to insist on nothing but digits, and exact digit counts, you can break it up as string tokens first: char yearstr[5], monthstr[3], daystr[3]; char junk; if (sscanf(input, "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3) { int year = atoi(yearstr); int month = atoi(monthstr); int day = atoi(daystr); } atoi is safe here, by the way, because we know that the integers are decimal strings no more than four digits. This is the sort of thing where sscanf comes in very handy. If you know how to use it, it solves these sorts of things nicely, and the performance is probably okay. At least not degenerately bad. Complete sample with all the validation: #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char **argv) { char yearstr[5] = "", monthstr[3] = "", daystr[3] = ""; char junk; if (argv[0] && argv[1] && sscanf(argv[1], "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3 && yearstr[3] && monthstr[1] && daystr[1]) { int year = atoi(yearstr); int month = atoi(monthstr); int day = atoi(daystr); printf("%d:%d:%d\n", year, month, day); return 0; } return EXIT_FAILURE; } Some tests: $ ./date asdf $ ./date 1-2-3 $ ./date 2020-01-1 $ ./date 20-01-01 $ ./date 2020-01-01 2020:1:1 $ ./date 2020-01-01z $ ./date 2020-01-12 2020:1:12
JdeBP 6y ago
I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300 . There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not. The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far. There have been several assertions that library support for strings in C++ is poor. However, note that the fix here was to switch from the Standard C library function sscanf() to a C++ library. * https://github.com/fastfloat https://github.com/fastfloat One might advocate using other people's libraries, on the grounds that they will have got such things right. However, note that this is RapidYAML, and the bug got fixed several years after GTA Online was released. Other third-party parsing libraries have suffered from being layered on top of sscanf() in other ways. * https://github.com/json-c/json-c/issues/173 https://github.com/json-c/json-c/issues/173 * https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a4dead0a63d9d9ac1c189 https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a...
- Jasper_ 6y ago
  Musl reads the "file" in 256 byte increments and calls strlen on each one. Still a strlen, but on short strings it would only be called once, on a short amount of data. It would work fine for this use case.
  - JdeBP 6y ago
    As laid out at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300, it doesn't call strlen(); and it isn't 256 bytes. Moreover that use case is not the use cases at hand, which are people parsing 10MiB of JSON and 504KiB of YAML with parsers that are not calling sscanf() just once. MUSL, with the same implementation strategy of nonce FILE objects, ends up performing multiple passes over those big input strings, once to look for NUL and a second time to pull each character out one by one. And it's doing those multiple passes multiple times, as it sets up and tears down the nonce FILE object each call to sscanf(), meaning that it's scanning the same parts of the string for NUL over and over again as it repeats the same buffer fill(s) from the input string a few characters further on. As I said before, it's not entirely free of this behaviour. With the other implementation strategy, in contrast, there's only a single pass over the whole input string, even with those multiple calls to sscanf().
smasher164 6y ago
Sounds like a new entry for https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/?
mazykhan1 6y ago
(y)
yread 6y ago
Just another example of the old adage "whatever problem you're facing someone on the internet has already seen it and solved it". We just need to get better at searching
- ant6n 6y ago
  True. Searching is turning more and more into a not solved problem. For a while, it seemed close to being a solved problem.
- aeturnum 6y ago
  Well, as long as you're facing this problem in 2020 and not around 2012. Even though Rockstar should should have patched GTA by now, battle-tested JSON parsing solutions were a lot rarer 8 years ago.
1f60c 6y ago
I think "(2020)" should be added to the title. (There was a very similar story on the front page yesterday, but alas, it's ultimately unrelated.)
PaulHoule 6y ago
Another example of so many things wrong with the status quo. (1) Naive people find liberation in text-based protocols that don't require tools to understand. (2) With experience one finds that variable-length data structures are much more treacherous than fixed-length data structures: you find simplicity instead in binary data formats that are dead easy to parse. (3) Floating point numbers are astonishingly expensive to parse and unparse to ASCII compared to how many FLOPs you could do in that time. All that, for a function that isn't quite correct... That is, the number 1/5, which you write as "0.2" doesn't actually exist in IEEE floats. You don't notice at first because that number unparses as "0.2" -- but then note that "0.1 + 0.2 == 0.3" is false in most computer languages. (4) Null-terminated strings are the definition of insanity, rivaled only by "pointers are integers, integers are pointers" One pet project of mine lately is a "Data Assembler" that takes a graph of data structures (say test data for a family of logic chips, graphics data for a laser light show, or "maps" to upload to the engine control unit in your car) in Python and converts it to a byte array that is incorporated into an Arduino program. The total size of the structure could be up to 32kbytes on a small device, or up to 250kbytes or so on a big device, but the program memory is huge compared to the RAM which might be as little as 2kb so the unpacking code is going to stream the data with a small working area. The minimum it has to do is put together blocks of data that have references to one another that are only resolved once all of the blocks are otherwise complete. I deliberated a lot about how to handle variable length data structures and decided to embed a two-byte length before the block for all blocks. I could have saved some bytes when the length of the structure was known, but then I'd have to figure out how to code lengths then (e.g. for an array of 2-byte ints do I count the ints or bytes) and figured I'd make up my mind once.
- pjc50 6y ago
  > variable-length data structures are much more treacherous than fixed-length data structures A fixed-length structure is only fixed until you need to add a field to it. I understand the appeal, but good solutions seem to be very rare here. ASN.1 was possibly the first attempt but turned into a total nightmare. Protobuf seems to be doing a reasonable job, but only as a wire format and not a persistence format. Text always "works", even if inadequately. And it can be handled with your normal diff and editing tools.
high_byte 6y ago
GTA loading screen with cyberpunk music on loop intensifies
djhaskin987 6y ago
I ran up against this issue when I was creating a parser that parsed debian package information (code here[1]). Trying to match against a line with regex slowed the program down past feasibility. I had to switch to just assuming that two line breaks meant a new package record instead. After that, the program was zippy. 1: https://github.com/djhaskin987/degasolv/blob/develop/cli-src/degasolv/pkgsys/apt.clj#L117 https://github.com/djhaskin987/degasolv/blob/develop/cli-src...
- tambre 6y ago
  Does the control format have an official spec? I too have had to resort to parsing those files with regexes.
  - djhaskin987 6y ago
    Not that I know of, but I have noticed that two newline characters separate package records, and the record is of the form `Key: Value` for each line. As you can see in my code, I've gotten rid of most/all of the regex stuff, because, as we observe, it kills performance.
  - JdeBP 6y ago
    It's chapter 5 of the Debian Policy Manual.
randomNumber7 6y ago
I didn't think this is sensational, because I found this behavior while writing one of my first C programs a couple of years ago. Also you just have to google "sscanf slow"....
rob74 6y ago
Is this good ol' Shlemiel the painter (https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/) rearing his lovable-but-sometimes-a-little-bit-empty head again?
- thaumasiotes 6y ago
  Same pattern, but what's going on is that sscanf has been implemented as a call to a related function, with setup that incidentally does a bunch of unnecessary work. The scanning isn't what's causing the problem; it's that, before sscanf starts its actual work, it passes over the entire string to see how long it is.
simias 6y ago
I write a lot of C but I literally never use scanf. C simply lacks the facilities to make such an API truly useful and flexible. You can't scan custom types, error handling is super limited, it's very easy to mess up the format string and potentially end up with corrupted data and security vulnerabilities. If you need to parse JSON or some high level format look for a lib, for instance I can vouch for cJSON which is very small and has a rather nice API (by C standards at least). If I need to parse a simple format string like "id:name:description" something like strtok_r does the job to split the components and then you can parse individual components any way you like, potentially offering better error messages. If I need to parse a complex format then chances are scanf wouldn't do the trick anyway, so it's either custom made parser state machine or lex/yacc. Note for instance that in the GTA case the call was `sscanf(p, "%d", buf)` which is a glorified strtol with vastly worse performance. I would seriously advise not using scanf and friends for anything serious. Too many footguns.
whalesalad 6y ago
I believe I experienced a form of this recently with a regular expression. I never did figure out what exactly was going on but a certain string would cause the expression to run for an eternity. That was an interesting bug to track down.
- klyrs 6y ago
  Depends what you mean by "regular expression," but matching in perl regexps is NP-Hard. https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- secondcoming 6y ago
  A dodgy regex took down Cloudflare! https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ https://blog.cloudflare.com/details-of-the-cloudflare-outage...
brundolf 6y ago
Something I've mused about is whether it would be possible to reason about performance characteristics at a types level, to statically identify things like quadratic behavior. No idea what this would look like; I just see this gap where type systems have gotten quite good at ensuring against incorrectness (not C's, of course, but that's another discussion), but there's almost no equivalent story for catastrophic performance regressions, which in some cases can be just as serious as a program-crashing bug. Basically when it comes to performance we're still in the place that we used to be with correctness: "either read the entire stack of source code to understand everything that's happening, or try and remember to read the docs which may or may not be correct and exhaustive and just hope for the best". The performance characteristics of a piece of code are part of its contract with the outside world, but that contract is in no way formalized right now.
- zionic 6y ago
  This is brilliant, I too feel like there’s an opportunity there but don’t have any idea off the top of my head how to implement such a thing.
- voldacar 6y ago
  maybe you could encode the number of maximum nested loops into the type system, so when defining a function you set a maximum number which would fail to compile if exceeded? would be crude but possibly helpful at times
rurban 6y ago
I've been hit by this behaviour just a few days ago with the fantastic libfuzzer, which finds much more errors than afl++ or honggfuzz in much less time. But it's buffer strategy is enoying, leading to inefficiency and artificial sscanf bugs. Problem is, oss-fuzz/libfuzzer gives you a const char* buffer without zero termination. In reality every such input buffer is zero terminated, because otherwise strtol or sscanf are worthless and lead to buffer overflows. They don't even allow adding a zero at the end, so you have to copy the whole input buffer just to add your zero termination, which makes all the fuzzer speed advantages worthless.
deleted 6y ago
[deleted]
arduinomancer 6y ago
So if I understand is the issue not that sscanf reads the whole string length, but that people call sscanf multiple times on the same string for each value they want to parse? Meaning sscanf is actually designed to scan all your values in one pass?
- JdeBP 6y ago
  It isn't designed that way, no. This is simply an internal choice made by C library implementors, and one implementation choice fares very badly in this situation, as the strings grow long. The other choice is pretty much immune to long strings in these scenarios. You cannot infer from this an intended usage of sscanf(), because this issue isn't part of the interface contract, just an effect of a particular implementation.
rpnx 6y ago
Never been a fan of C style strings for exactly this reason. C style strlen is slow. In C++ strings, the size is included in the string structure. Also, fetching the distance between two std::string::iterator is fast. string_view::size should also be fast when that's available.
- TwoBit 6y ago
  Was there ever anybody a fan of C style strings? Maybe I misremember, but I think long ago people made arguments that C strings were superior because of how simple they were. Such was the thinking 30 years ago.
  - obviouslynotme 6y ago
    The null-terminated string is the most compact memory representation for a string. A strong competitor was Pascal strings which are led with a byte that carries the length of the string. The only problem is that limits you to 255 characters in a string. You would have to do some UTF-8 style length encoding to make it memory efficient while still capturing long strings. Older computers had a lot less memory. Programs would write their own virtual memory systems to swap code and data to and from disk. C was born in this era. By the time large flat memory and many registers were available, the old C string was already the standard. It is very difficult to get away from that because everything from the OS on up assume standard C strings.
petters 6y ago
This a performance bug in glibc (and others), right? Several developers seem to be hit by this.
dmix 6y ago
Unrelated but I found this but in the repo interesting: (Under the heading “is it rapid?” Measuring performance). > The 450MB/s read rate for JSON puts ryml squarely in the same ballpark as RapidJSON and other fast json readers (data from here). Even parsing full YAML is at ~150MB/s, which is still in that performance ballpark, albeit at its lower end. This is something to be proud of, as the YAML specification is much more complex than JSON: 23449 vs 1969 words. How did YAML get so complicated. I’d assume it would be much more similarity YAML’s quirks adding a few extra things to work on. But that spec is quite huge by comparison (of words alone).
- dragonwriter 6y ago
  > How did YAML get so complicated YAML has both more syntactical options, and broader semantic coverage; particularly, it includes the concept of schemas defining YAML profiles. Also, the YAML spec has much more informational content. Examples are a stark illustration: RFC 8259 has 5 example JSON documents (3 of which are simple scalar values). The preview chapter of the YAML 1.2 spec has 28 examples, only a handful of which are single scalars.
- imtringued 6y ago
  I'm a fan of the parts of YAML that work. I wish there was a universally acknowledged strict YAML standard similar to 'use strict' in Javascript. There are some solid ideas embedded in YAML but the warts make people yell at it. It's also being abused for things that it really isn't meant to do like Ansible.
joe_the_user 6y ago
Broadly, it's actually easy to see how naive parsing can become quadratic if a programmer isn't careful. You parse by processing a long string/file via "get-a-token(), add-token-to-structure()" repeating until you have built your structure or made an error in the construction process (here a token a kind, a type of substring and get-a-token retrieves the substring type in some form). The problems come because the naive programmer is only thinking about their structure building process, so they use some library function to get their tokens. Whether that's a regular expression interpreter or some other flexible facility by provided by the library, it's easy for it's definition of a token-string to include things "not in the string" as well as things in the string - a "quoted string" begins and ends with a quote, so to discover that X isn't a quoted string, you have to scan to the end. So if thing go wrong, each call to get-a-token may scan the while file to make sure this token isn't that. Just an example. The problem here seems to be tokenizing floats, which also has a "where it end" problem in c++. And the alternative is parsing floats yourself, which indeed no one wants to do since they are complex and defined by a complex standard.
salamanderman 6y ago
Two posts about sscanf today. I'm surprised how much people apparently use it. I basically never use it, though I've used strtok a lot.
BenFrantzDale 6y ago
This is an open bug in glibc from 7 years ago(!) https://sourceware.org/bugzilla/show_bug.cgi?id=17577 https://sourceware.org/bugzilla/show_bug.cgi?id=17577
- BenFrantzDale 6y ago
  And if it’s not a bug in glibc, it’s a bug in the C standard for not requiring it to be big-O of the number of varargs.
t0r0nat0r 6y ago
>First of all, I'm happy that as a matter of course ryml is already expected to be faster than alternatives by at least 10x, to the point that a mere 3x speedup is considered an issue! Lol just say thank you

510 points by JdeBP 6y ago

ufo 6y ago

In case anyone missed it, this sscanf behavior was the cause of the long loading times in GTA V, a story that hit the front page yesterday: https://news.ycombinator.com/item?id=26296339 https://news.ycombinator.com/item?id=26296339

aparsons 6y ago
That was a brilliant investigation. Reminded me of when I used to work on Windows debuggers. I wish the author touched on symbolization more. That is where a lot of the fun lies when dissecting precompiled binaries.
- jjoonathan 6y ago
  What are the tools for symbolization? I recently spent a lot of time laboriously propagating RTTI information around Visual C++ binaries by hand in Ghidra, so I would be very interested in learning about this tooling, even if it's all IDA for now.
  - wcarss 6y ago
    just a little related: I watched a guy step'n'watch the no-symbols code once after he hooked WINDBG up to an MS Office process that had a paint issue. He narrowed it down to something IME was doing -- I gained nothing but awe.
  - aparsons 6y ago
    It has been 2-3 decades since I’ve worked on this, so this may be outdated advice. In fact, I just learned of Ghidra when I read the article. In general there are three cases: - Developer forgot to strip/obfuscate symbols, in which case you’re golden - Symbol you seek is in a shared library: patch the DLL. Often what we did was do investigations in a VM, where the n most common shared library calls were patched to send stack and symbol data to a local DB. Very similar play to RR, but only in the patched code. - If the (missing) symbol you seek is pre linked (static), things get interesting. We built a pattern matcher that was incredible. Idea is, if you have the disassembly and a loop, like: int fun(char* str) { call processChar on each uppercase character } It pattern matched a name like rax_foreach_iflte_cx_call_obfuscatedSymbolForProcessChar 90+% of code either: - enters the same dynamic library trampoline - displays very very common programming patterns. From what I know, we never released this outside early MS DN members because the 10% is often very useful code and developer tools weren’t given away for free yet. But once the DLL is patched, you propagate names up graph. Any remaining symbols were hand annotated (and we run the propagator again). Brian Parks went on to extend this system to work with C++ templates. C++ mangling is very predictable, so his program could scavenge for symbols (obfuscators only worked on the root symbol name) and build out the class at compile time for us to reference.
- saagarjha 6y ago
  I'm sure that symbols were not mentioned much as the code was from an obfuscated game engine.
masklinn 6y ago
Well half the cause (or probably two thirds), as the post shows there’s a second quadratic blowup when filling the not-a-hashmap thing after the very slow parsing has completed.
- crowbahr 6y ago
  A filling that wasn't even required because it was de-duping already de-duped data instead of just inserting it into a list (or a hashmap, as suggested in the post).
  - masklinn 6y ago
    The filling was necessary, but the deduplication (in linear time as it works over an array) indeed was not as the input is unique. I can see why the devs would not trust that though. So it’s the inefficiency of the dedup’ which bugs me more than the dedup itself.

dividuum 6y ago

Seen the GTA post already and the sscanf behavior is very surprising as one would expect it to parse the given string until the given format is satisfied or \0 is hit. Seems like this is not the case. Found this: https://stackoverflow.com/a/23924112 https://stackoverflow.com/a/23924112 > sscanf() converts the string you pass in to an _IO_FILE* to make the string look like a "file". This is so the same internal _IO_vfscanf() can be used for both a string and a FILE*. However, as part of that conversion, done in a _IO_str_init_static_internal() function, it calls __rawmemchr (ptr, '\0'); essentially a strlen() call, on your input string. Looks correct. Call flow: https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/stdio-common/sscanf.c#L34 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/libio/strfile.h#L90 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/libio/strops.c#L41 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d... https://github.com/bminor/glibc/blob/83908b3a1ea51e3aa7ff422275940e56dbba989f/string/rawmemchr.c#L39-L45 https://github.com/bminor/glibc/blob/83908b3a1ea51e3aa7ff422...

kazinator 6y ago
By itself, that doesn't add up to N-squared behavior, though. > It looks like the problem is that reading floats is done using c4::from_chars -> c4::atof -> sscanf which ultimately calls _IO_str_init_static_internal in the glibc implementation. As far as I understand, this essentially causes strlen to be called on the string that rapidyaml passes to it, essentially causing strlen to be called O(n^2) times. As such, this doesn't follow. Just because sscanf takes the length of the entire source string doesn't mean will get N^2 behavior, unless you do silly things with sscanf, like extract a small token from the beginning of a large string, and then skip past it to do the same thing again after that small token: essentially, build a lexical analyzer in which the pattern matcher consists of calls to scanf. This is not an intended use case for sscanf. No self-respecting language parser designer would do such a thing in a non-throwaway, production program. sscanf has undefined behaviors for out-of-range numeric values, so you can't use it for just blindly extracting numeric tokens at all, regardless of any other issues. sscanf should only be used on a string that your program has either prepared itself, or carefully delimited by some other means. For instance, suppose we have a string which holds a date (could be an input to the program). We can test whether it's in the YYYY-MM-DD format, and get those values out: int year, month, day; char junk; if (sscanf(input, "%4d-%2d-%2d%c", &year, &month, &day, &junk) == 3) { /* we got it */ } The purpose of junk is to test that there is no trailing garbage character. If there is, it will be scanned and the return value will be 4. If we don't care about that, we can just omit that argument and conversion specifier. This will accept inputs like 01-1-1. Worse, it will scan leading signs! If you wan to insist on nothing but digits, and exact digit counts, you can break it up as string tokens first: char yearstr[5], monthstr[3], daystr[3]; char junk; if (sscanf(input, "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3) { int year = atoi(yearstr); int month = atoi(monthstr); int day = atoi(daystr); } atoi is safe here, by the way, because we know that the integers are decimal strings no more than four digits. This is the sort of thing where sscanf comes in very handy. If you know how to use it, it solves these sorts of things nicely, and the performance is probably okay. At least not degenerately bad. Complete sample with all the validation: #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char **argv) { char yearstr[5] = "", monthstr[3] = "", daystr[3] = ""; char junk; if (argv[0] && argv[1] && sscanf(argv[1], "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3 && yearstr[3] && monthstr[1] && daystr[1]) { int year = atoi(yearstr); int month = atoi(monthstr); int day = atoi(daystr); printf("%d:%d:%d\n", year, month, day); return 0; } return EXIT_FAILURE; } Some tests: $ ./date asdf $ ./date 1-2-3 $ ./date 2020-01-1 $ ./date 20-01-01 $ ./date 2020-01-01 2020:1:1 $ ./date 2020-01-01z $ ./date 2020-01-12 2020:1:12

JdeBP 6y ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300 . There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not. The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far. There have been several assertions that library support for strings in C++ is poor. However, note that the fix here was to switch from the Standard C library function sscanf() to a C++ library. * https://github.com/fastfloat https://github.com/fastfloat One might advocate using other people's libraries, on the grounds that they will have got such things right. However, note that this is RapidYAML, and the bug got fixed several years after GTA Online was released. Other third-party parsing libraries have suffered from being layered on top of sscanf() in other ways. * https://github.com/json-c/json-c/issues/173 https://github.com/json-c/json-c/issues/173 * https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a4dead0a63d9d9ac1c189 https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a...

Jasper_ 6y ago
Musl reads the "file" in 256 byte increments and calls strlen on each one. Still a strlen, but on short strings it would only be called once, on a short amount of data. It would work fine for this use case.
- JdeBP 6y ago
  As laid out at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300, it doesn't call strlen(); and it isn't 256 bytes. Moreover that use case is not the use cases at hand, which are people parsing 10MiB of JSON and 504KiB of YAML with parsers that are not calling sscanf() just once. MUSL, with the same implementation strategy of nonce FILE objects, ends up performing multiple passes over those big input strings, once to look for NUL and a second time to pull each character out one by one. And it's doing those multiple passes multiple times, as it sets up and tears down the nonce FILE object each call to sscanf(), meaning that it's scanning the same parts of the string for NUL over and over again as it repeats the same buffer fill(s) from the input string a few characters further on. As I said before, it's not entirely free of this behaviour. With the other implementation strategy, in contrast, there's only a single pass over the whole input string, even with those multiple calls to sscanf().

smasher164 6y ago

Sounds like a new entry for https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/?

mazykhan1 6y ago

(y)

yread 6y ago

Just another example of the old adage "whatever problem you're facing someone on the internet has already seen it and solved it". We just need to get better at searching

ant6n 6y ago
True. Searching is turning more and more into a not solved problem. For a while, it seemed close to being a solved problem.
aeturnum 6y ago
Well, as long as you're facing this problem in 2020 and not around 2012. Even though Rockstar should should have patched GTA by now, battle-tested JSON parsing solutions were a lot rarer 8 years ago.

1f60c 6y ago

I think "(2020)" should be added to the title. (There was a very similar story on the front page yesterday, but alas, it's ultimately unrelated.)

PaulHoule 6y ago

Another example of so many things wrong with the status quo. (1) Naive people find liberation in text-based protocols that don't require tools to understand. (2) With experience one finds that variable-length data structures are much more treacherous than fixed-length data structures: you find simplicity instead in binary data formats that are dead easy to parse. (3) Floating point numbers are astonishingly expensive to parse and unparse to ASCII compared to how many FLOPs you could do in that time. All that, for a function that isn't quite correct... That is, the number 1/5, which you write as "0.2" doesn't actually exist in IEEE floats. You don't notice at first because that number unparses as "0.2" -- but then note that "0.1 + 0.2 == 0.3" is false in most computer languages. (4) Null-terminated strings are the definition of insanity, rivaled only by "pointers are integers, integers are pointers" One pet project of mine lately is a "Data Assembler" that takes a graph of data structures (say test data for a family of logic chips, graphics data for a laser light show, or "maps" to upload to the engine control unit in your car) in Python and converts it to a byte array that is incorporated into an Arduino program. The total size of the structure could be up to 32kbytes on a small device, or up to 250kbytes or so on a big device, but the program memory is huge compared to the RAM which might be as little as 2kb so the unpacking code is going to stream the data with a small working area. The minimum it has to do is put together blocks of data that have references to one another that are only resolved once all of the blocks are otherwise complete. I deliberated a lot about how to handle variable length data structures and decided to embed a two-byte length before the block for all blocks. I could have saved some bytes when the length of the structure was known, but then I'd have to figure out how to code lengths then (e.g. for an array of 2-byte ints do I count the ints or bytes) and figured I'd make up my mind once.

pjc50 6y ago
> variable-length data structures are much more treacherous than fixed-length data structures A fixed-length structure is only fixed until you need to add a field to it. I understand the appeal, but good solutions seem to be very rare here. ASN.1 was possibly the first attempt but turned into a total nightmare. Protobuf seems to be doing a reasonable job, but only as a wire format and not a persistence format. Text always "works", even if inadequately. And it can be handled with your normal diff and editing tools.

high_byte 6y ago

GTA loading screen with cyberpunk music on loop intensifies

djhaskin987 6y ago

I ran up against this issue when I was creating a parser that parsed debian package information (code here[1]). Trying to match against a line with regex slowed the program down past feasibility. I had to switch to just assuming that two line breaks meant a new package record instead. After that, the program was zippy. 1: https://github.com/djhaskin987/degasolv/blob/develop/cli-src/degasolv/pkgsys/apt.clj#L117 https://github.com/djhaskin987/degasolv/blob/develop/cli-src...

tambre 6y ago
Does the control format have an official spec? I too have had to resort to parsing those files with regexes.
- djhaskin987 6y ago
  Not that I know of, but I have noticed that two newline characters separate package records, and the record is of the form `Key: Value` for each line. As you can see in my code, I've gotten rid of most/all of the regex stuff, because, as we observe, it kills performance.
- JdeBP 6y ago
  It's chapter 5 of the Debian Policy Manual.

randomNumber7 6y ago

I didn't think this is sensational, because I found this behavior while writing one of my first C programs a couple of years ago. Also you just have to google "sscanf slow"....

rob74 6y ago

Is this good ol' Shlemiel the painter (https://www.joelonsoftware.com/2001/12/11/back-to-basics/ https://www.joelonsoftware.com/2001/12/11/back-to-basics/) rearing his lovable-but-sometimes-a-little-bit-empty head again?

thaumasiotes 6y ago
Same pattern, but what's going on is that sscanf has been implemented as a call to a related function, with setup that incidentally does a bunch of unnecessary work. The scanning isn't what's causing the problem; it's that, before sscanf starts its actual work, it passes over the entire string to see how long it is.

simias 6y ago

I write a lot of C but I literally never use scanf. C simply lacks the facilities to make such an API truly useful and flexible. You can't scan custom types, error handling is super limited, it's very easy to mess up the format string and potentially end up with corrupted data and security vulnerabilities. If you need to parse JSON or some high level format look for a lib, for instance I can vouch for cJSON which is very small and has a rather nice API (by C standards at least). If I need to parse a simple format string like "id:name:description" something like strtok_r does the job to split the components and then you can parse individual components any way you like, potentially offering better error messages. If I need to parse a complex format then chances are scanf wouldn't do the trick anyway, so it's either custom made parser state machine or lex/yacc. Note for instance that in the GTA case the call was `sscanf(p, "%d", buf)` which is a glorified strtol with vastly worse performance. I would seriously advise not using scanf and friends for anything serious. Too many footguns.

whalesalad 6y ago

I believe I experienced a form of this recently with a regular expression. I never did figure out what exactly was going on but a certain string would cause the expression to run for an eternity. That was an interesting bug to track down.

klyrs 6y ago
Depends what you mean by "regular expression," but matching in perl regexps is NP-Hard. https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
secondcoming 6y ago
A dodgy regex took down Cloudflare! https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ https://blog.cloudflare.com/details-of-the-cloudflare-outage...

brundolf 6y ago

Something I've mused about is whether it would be possible to reason about performance characteristics at a types level, to statically identify things like quadratic behavior. No idea what this would look like; I just see this gap where type systems have gotten quite good at ensuring against incorrectness (not C's, of course, but that's another discussion), but there's almost no equivalent story for catastrophic performance regressions, which in some cases can be just as serious as a program-crashing bug. Basically when it comes to performance we're still in the place that we used to be with correctness: "either read the entire stack of source code to understand everything that's happening, or try and remember to read the docs which may or may not be correct and exhaustive and just hope for the best". The performance characteristics of a piece of code are part of its contract with the outside world, but that contract is in no way formalized right now.

zionic 6y ago
This is brilliant, I too feel like there’s an opportunity there but don’t have any idea off the top of my head how to implement such a thing.
voldacar 6y ago
maybe you could encode the number of maximum nested loops into the type system, so when defining a function you set a maximum number which would fail to compile if exceeded? would be crude but possibly helpful at times

rurban 6y ago

I've been hit by this behaviour just a few days ago with the fantastic libfuzzer, which finds much more errors than afl++ or honggfuzz in much less time. But it's buffer strategy is enoying, leading to inefficiency and artificial sscanf bugs. Problem is, oss-fuzz/libfuzzer gives you a const char* buffer without zero termination. In reality every such input buffer is zero terminated, because otherwise strtol or sscanf are worthless and lead to buffer overflows. They don't even allow adding a zero at the end, so you have to copy the whole input buffer just to add your zero termination, which makes all the fuzzer speed advantages worthless.

deleted 6y ago

[deleted]

arduinomancer 6y ago

So if I understand is the issue not that sscanf reads the whole string length, but that people call sscanf multiple times on the same string for each value they want to parse? Meaning sscanf is actually designed to scan all your values in one pass?

JdeBP 6y ago
It isn't designed that way, no. This is simply an internal choice made by C library implementors, and one implementation choice fares very badly in this situation, as the strings grow long. The other choice is pretty much immune to long strings in these scenarios. You cannot infer from this an intended usage of sscanf(), because this issue isn't part of the interface contract, just an effect of a particular implementation.

rpnx 6y ago

Never been a fan of C style strings for exactly this reason. C style strlen is slow. In C++ strings, the size is included in the string structure. Also, fetching the distance between two std::string::iterator is fast. string_view::size should also be fast when that's available.

TwoBit 6y ago
Was there ever anybody a fan of C style strings? Maybe I misremember, but I think long ago people made arguments that C strings were superior because of how simple they were. Such was the thinking 30 years ago.
- obviouslynotme 6y ago
  The null-terminated string is the most compact memory representation for a string. A strong competitor was Pascal strings which are led with a byte that carries the length of the string. The only problem is that limits you to 255 characters in a string. You would have to do some UTF-8 style length encoding to make it memory efficient while still capturing long strings. Older computers had a lot less memory. Programs would write their own virtual memory systems to swap code and data to and from disk. C was born in this era. By the time large flat memory and many registers were available, the old C string was already the standard. It is very difficult to get away from that because everything from the OS on up assume standard C strings.

petters 6y ago

This a performance bug in glibc (and others), right? Several developers seem to be hit by this.

dmix 6y ago

Unrelated but I found this but in the repo interesting: (Under the heading “is it rapid?” Measuring performance). > The 450MB/s read rate for JSON puts ryml squarely in the same ballpark as RapidJSON and other fast json readers (data from here). Even parsing full YAML is at ~150MB/s, which is still in that performance ballpark, albeit at its lower end. This is something to be proud of, as the YAML specification is much more complex than JSON: 23449 vs 1969 words. How did YAML get so complicated. I’d assume it would be much more similarity YAML’s quirks adding a few extra things to work on. But that spec is quite huge by comparison (of words alone).

dragonwriter 6y ago
> How did YAML get so complicated YAML has both more syntactical options, and broader semantic coverage; particularly, it includes the concept of schemas defining YAML profiles. Also, the YAML spec has much more informational content. Examples are a stark illustration: RFC 8259 has 5 example JSON documents (3 of which are simple scalar values). The preview chapter of the YAML 1.2 spec has 28 examples, only a handful of which are single scalars.
imtringued 6y ago
I'm a fan of the parts of YAML that work. I wish there was a universally acknowledged strict YAML standard similar to 'use strict' in Javascript. There are some solid ideas embedded in YAML but the warts make people yell at it. It's also being abused for things that it really isn't meant to do like Ansible.

joe_the_user 6y ago

Broadly, it's actually easy to see how naive parsing can become quadratic if a programmer isn't careful. You parse by processing a long string/file via "get-a-token(), add-token-to-structure()" repeating until you have built your structure or made an error in the construction process (here a token a kind, a type of substring and get-a-token retrieves the substring type in some form). The problems come because the naive programmer is only thinking about their structure building process, so they use some library function to get their tokens. Whether that's a regular expression interpreter or some other flexible facility by provided by the library, it's easy for it's definition of a token-string to include things "not in the string" as well as things in the string - a "quoted string" begins and ends with a quote, so to discover that X isn't a quoted string, you have to scan to the end. So if thing go wrong, each call to get-a-token may scan the while file to make sure this token isn't that. Just an example. The problem here seems to be tokenizing floats, which also has a "where it end" problem in c++. And the alternative is parsing floats yourself, which indeed no one wants to do since they are complex and defined by a complex standard.

salamanderman 6y ago

Two posts about sscanf today. I'm surprised how much people apparently use it. I basically never use it, though I've used strtok a lot.

BenFrantzDale 6y ago

This is an open bug in glibc from 7 years ago(!) https://sourceware.org/bugzilla/show_bug.cgi?id=17577 https://sourceware.org/bugzilla/show_bug.cgi?id=17577

BenFrantzDale 6y ago
And if it’s not a bug in glibc, it’s a bug in the C standard for not requiring it to be big-O of the number of varargs.

t0r0nat0r 6y ago

>First of all, I'm happy that as a matter of course ryml is already expected to be faster than alternatives by at least 10x, to the point that a mere 3x speedup is considered an issue! Lol just say thank you