{"action":"created","issue":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/805","repository_url":"https://api.github.com/repos/ocaml/ocaml","labels_url":"https://api.github.com/repos/ocaml/ocaml/issues/805/labels{/name}","comments_url":"https://api.github.com/repos/ocaml/ocaml/issues/805/comments","events_url":"https://api.github.com/repos/ocaml/ocaml/issues/805/events","html_url":"https://github.com/ocaml/ocaml/pull/805","id":176305509,"number":805,"title":"Fix an overflow bug in String.concat","user":{"login":"yallop","id":1736496,"avatar_url":"https://avatars.githubusercontent.com/u/1736496?v=3","gravatar_id":"","url":"https://api.github.com/users/yallop","html_url":"https://github.com/yallop","followers_url":"https://api.github.com/users/yallop/followers","following_url":"https://api.github.com/users/yallop/following{/other_user}","gists_url":"https://api.github.com/users/yallop/gists{/gist_id}","starred_url":"https://api.github.com/users/yallop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yallop/subscriptions","organizations_url":"https://api.github.com/users/yallop/orgs","repos_url":"https://api.github.com/users/yallop/repos","events_url":"https://api.github.com/users/yallop/events{/privacy}","received_events_url":"https://api.github.com/users/yallop/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2016-09-12T06:51:48Z","updated_at":"2016-09-12T15:49:16Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/ocaml/ocaml/pulls/805","html_url":"https://github.com/ocaml/ocaml/pull/805","diff_url":"https://github.com/ocaml/ocaml/pull/805.diff","patch_url":"https://github.com/ocaml/ocaml/pull/805.patch"},"body":"[tl;dr: `String.concat` can segfault due to overflow; this PR fixes the bug and makes the function faster.]\r\n\r\n### The Description of the Bug\r\n\r\nThis PR fixes a bug from last century in the `String.concat` function, which catenates a list of strings:\r\n\r\n```ocaml\r\nString.concat \",\" [\"a\"; \"b\"; \"c\"]\r\n~>\r\n\"a,b,c\"\r\n```\r\n\r\nand whose [description][string-concat-mli] includes the following:\r\n\r\n```\r\nRaise [Invalid_argument] if the result is longer than\r\n{!Sys.max_string_length} bytes. *)\r\n```\r\n\r\nUnfortunately, computing the length of the output string may overflow an `int`, in which case the result is not the `Invalid_argument` exception but an out-of-bounds write.  This situation is perhaps unlikely on a modern 64-bit platform, but on what the configure script [calls][thirty-two] \"a regular 32 bit architecture\" the bug can be triggered with a single large string and a list of moderate length.\r\n\r\n### The Example\r\n\r\nHere's an example to illustrate the problem.  The idea is to create a list containing multiple references to a single large string of length `Sys.max_string_length`, or `16777211`.  The number of entries in the list is carefully chosen so that computing their sum wraps around past `max_int` (`1073741823`) and `min_int`, all the way past zero again to give a number between zero and  `Sys.max_string_length` -- i.e. a valid length for a string but significantly less than the combined lengths of the members of the list.\r\n\r\n```ocaml\r\nlet big = String.make Sys.max_string_length 'x'\r\n\r\nlet push x l = l := x :: !l\r\nlet (+=) a b = a := !a + b\r\n\r\nlet sz, l = ref 0, ref []\r\n\r\nlet () = begin\r\n  while !sz >= 0 do push big l; sz += Sys.max_string_length done;\r\n  while !sz <= 0 do push big l; sz += Sys.max_string_length done;\r\nend\r\n\r\nlet _ = String.concat \"\" !l\r\n```\r\n\r\nHere's the unfortunate result of compiling and running the program:\r\n\r\n```\r\nSegmentation fault (core dumped)\r\n```\r\n\r\n### The Proposed Fix\r\n\r\nThe fix is simple, in principle: the [code that computes the size of the result string][output-size-calculation] must be extended with a check that the sum does not overflow an `int`.  In general overflow is only detectable during the computation; by the time the final result is computed it may be too late, as the example above shows.\r\n\r\nHere is the current code for computing the size of the result string:\r\n\r\n```ocaml\r\nlet num = ref 0 and len = ref 0 in\r\nList.iter (fun s -> incr num; len := !len + length s) l;\r\n(!len + length sep * (!num - 1))\r\n```\r\n\r\nNaively adding an overflow check to each iteration (i.e. to the function passed to `List.iter`) slows things down slightly, as we might expect:\r\n\r\n**Effect on performance of adding an overflow check**\r\n\r\n| List length:               |\t1\t|\t2\t|\t4\t|\t8\t|\t16\t|\t32\t|\t64\t|\t128\t|\t256\t|\r\n|----------------------------|----------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|\r\n| Current code (ns):         |\t13.08\t|\t20.44\t|\t23.72\t|\t39.31\t|\t83.46\t|\t141.42\t|\t266.81\t|\t505.84\t|\t994.86\t|\r\n| With overflow check (ns):  |\t13.82\t|\t19.94\t|\t27.07\t|\t43.77\t|\t83.76\t|\t157.16\t|\t300.61\t|\t578.60\t|\t1119.99\t|\r\n\r\nIn mitigation, it seems unlikely that computing the size of the result in `String.concat` is a significant bottleneck in most OCaml programs.\r\n\r\nStill, it's a shame to slow things down unnecessarily.  So this PR takes advantage of some optimization opportunities to make the size computation faster (while adding in the overflow check, of course).  Instead of calling `List.iter` with a closure we might compute the size in a simple loop implemented as a recursive function with an accumulator.  And we can then unroll the loop so as not to perform the overflow check every iteration.  The unrolling uses the following observation: since `Sys.max_string_length` is significantly smaller than `max_int`, if adding `String.length s` to `size` causes an overflow, then we can add quite a few more string lengths to `size` before it becomes positive again.\r\n\r\nHere's a comparison of the performance of the existing size computation and the implementation in this PR:\r\n\r\n**Performance of current implementation vs this PR**\r\n\r\n| List length:               |\t1\t|\t2\t|\t4\t|\t8\t|\t16\t|\t32\t|\t64\t|\t128\t|\t256\t|\r\n|----------------------------|----------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|\r\n| Current code (ns):         |\t13.08\t|\t20.44\t|\t23.72\t|\t39.31\t|\t83.46\t|\t141.42\t|\t266.81\t|\t505.84\t|\t994.86\t|\r\n| New implementation (ns):   |\t3.70\t|\t5.04\t|\t8.51\t|\t14.70\t|\t27.15\t|\t53.66\t|\t112.77\t|\t215.85\t|\t419.42\t|\r\n\r\nWith flambda the gap narrows a bit:\r\n\r\n**Performance of current implementation vs this PR (flambda)**\r\n\r\n| List length:               |\t1\t|\t2\t|\t4\t|\t8\t|\t16\t|\t32\t|\t64\t|\t128\t|\t256\t|\r\n|----------------------------|----------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|---------------|\r\n| Current code (ns):         |\t8.49\t|\t10.79\t|\t15.74\t|\t25.84\t|\t48.46\t|\t93.41\t|\t183.54\t|\t357.02\t|\t711.02\t|\r\n| New implementation (ns):   |\t4.29\t|\t5.25\t|\t8.43\t|\t15.74\t|\t27.38\t|\t52.16\t|\t108.34\t|\t209.81\t|\t419.05\t|\r\n\r\n### A final note\r\n\r\nThis PR fixes a bug in `String.concat` and `Bytes.concat`.  The `Array.concat` function has a similar problem, which I'll address in a separate PR.\r\n\r\n[string-concat-mli]: https://github.com/ocaml/ocaml/blob/bf6261c2b7058a2ac2c471839d48acb1c77c22fd/stdlib/string.mli#L123-L128\r\n[thirty-two]: https://github.com/ocaml/ocaml/blob/bf6261c2b7058a2ac2c471839d48acb1c77c22fd/configure#L562\r\n[output-size-calculation]: https://github.com/ocaml/ocaml/blob/bf6261c2b7058a2ac2c471839d48acb1c77c22fd/stdlib/string.ml#L51-L53\r\n"},"comment":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/comments/246392687","html_url":"https://github.com/ocaml/ocaml/pull/805#issuecomment-246392687","issue_url":"https://api.github.com/repos/ocaml/ocaml/issues/805","id":246392687,"user":{"login":"yallop","id":1736496,"avatar_url":"https://avatars.githubusercontent.com/u/1736496?v=3","gravatar_id":"","url":"https://api.github.com/users/yallop","html_url":"https://github.com/yallop","followers_url":"https://api.github.com/users/yallop/followers","following_url":"https://api.github.com/users/yallop/following{/other_user}","gists_url":"https://api.github.com/users/yallop/gists{/gist_id}","starred_url":"https://api.github.com/users/yallop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yallop/subscriptions","organizations_url":"https://api.github.com/users/yallop/orgs","repos_url":"https://api.github.com/users/yallop/repos","events_url":"https://api.github.com/users/yallop/events{/privacy}","received_events_url":"https://api.github.com/users/yallop/received_events","type":"User","site_admin":false},"created_at":"2016-09-12T15:49:15Z","updated_at":"2016-09-12T15:49:15Z","body":"> @yallop What are you benchmarking here exactly ? The cost of concat, or the cost of computing the final size ?\r\n\r\nThe cost of computing the final size.\r\n\r\n> A naive solution would be to keep the current (wrong) final size computation, but do an overflow check before the unsafe_blit operations ? Is it too inefficient ?\r\n\r\nI haven't measured, but it sounds less efficient.  Wouldn't that involve two checks before each write -- for overflow of `offset+length`, and for out-of-bounds writes?  (Consider the case where the sum of the lengths of the strings is `3+2*max_int`, i.e. `1`.)"}}
{"actor":{"display_login":"yallop"}}