8 ms·

Is this actually a bug? The default assumption in Java is that types are not thread-safe unless otherwise specified. Attempting to use types in a way that excee

Is this actually a bug? The default assumption in Java is that types are not thread-safe unless otherwise specified. Attempting to use types in a way that exceeds their documented thread safety has always been allowed to leave your program in an inconsistent state.

neandrake 3y ago
My thinking is the same. I doubt this is an oversight. Making the String constructor thread-safe would likely slow things significantly. Great point about things being assumed not thread-safe. The JDK is pretty thorough with documenting thread-safety.
- neandrake 3y ago
  Coming back to this the answer is probably not strictly about concurrency and so there is a possibility something would need addressed about this.
- masklinn 3y ago
  > Making the String constructor thread-safe would likely slow things significantly. By my reckoning it would speed things up, at least going by the Java code.
  - neandrake 3y ago
    By what means? The only ways I would expect are either unconditionally duplicating the array or mutex, and I don’t think the mutex wouldn’t be simple. Adding a sync block on the input could be done but that’s assuming nothing else is locked on it (but probably points to there being a race condition elsewhere if there is..). Unconditionally duplicating the array would use more memory and wouldn’t be faster.
    - masklinn 3y ago
      Inlining `StringUTF16.compress` and `StringUTF16.bytes what the code currently does is essentially this (using python as pseudocode): latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c > 255: latin1 = None break latin1[i] = c if latin1 is not None: return LATIN1, latin1 utf16 = bytearray(len(input)*2) for i in range(0, len(input)): c = input[i] utf16[2*i] = c >> HI_BYTE_SHIFT utf16[2*i+1] = c >> LO_BYTE_SHIFT return UTF16, utf16 The issue occurs because `input` can be mutated between the moment it finds a char that's above 255 in the first loop and the moment it visits that same char in the second loop. The solution is to not do that, but instead something like: latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c <= 255: latin1[i] = c continue utf16 = bytearray(len(input)*2) for j in range(i): utf16[2*j] = latin1[j] latin1 = None utf16[2*i] = c utf16[2*i+1] = c >> 8 for j in range(i+1, len(input)): c = input[j] utf16[2*i] = c utf16[2*i+1] = c >> 8 return UTF16, utf16 return LATIN1, latin1 This means if you find a char that's above 255 you will always append that char to the UTF16 array, there's no possibility that someone will change it under you because you append the exact same char you tested. So you can not get into the situation the essay describes, a utf16 string will always contain at least one non-latin1-code unit. Non-vectorised performances should an improvement as latin1 to utf16 is a trivial operation (just copy every byte of the input to every other byte of the output) Though if you vectorised the char to utf16 conversion you now vectorise two loops on bailout (latin1 -> utf16 up to i, then char -> utf16) which is probably less efficient. I don't know if the JDK has vectorised optimisations, the source has "HotSpotIntrinsicCandidate" annotations but I don't know to what extent the intrinsics go.
cempaka 3y ago
That's true, but in the case of Strings in particular they are generally considered to be thread-safe by virtue of being immutable (and the Javadocs themselves say this in many places). Concurrently modifying the input character array may seem like willful abuse in this case, but I suppose there might be some carelessly written code out there which does it and the post shows how it would create some weird and very hard-to-debug behavior. And I can see the argument going both ways as far as the Javadoc: on the one hand, it only promises to return a String representing what is currently in the input character array, which seems to warn against concurrent/subsequent modification at least obliquely. But on the other hand, it does seem to commit to an up-front defensive copy of the input character array which doesn't quite take place, and without which things go a bit haywire if the encoding of the string changes. I don't think the correct answer is to sacrifice any performance to guard against this weird edge case, though.
- gizmo686 3y ago
  As the article points out, the only thing the Javadoc guarantees is the subsequent modifications of the character array have no effect. It says nothing about concurrent modifications. The type whose thread safety is in question here is not actually String, but char[]. I'm not going to say it is always wrong to share char[] between threads (as a primitive array of something other than double and long, the Java Spec does make some guarentees about char[]), however it is almost always wrong to be sharing char[] between threads. If you want a language that protects you from this type of mistake, you simply need something more advanced than Java. This isn't even the biggest hole in Java's safety. Java has a type system, which is at least a nominal claim to type safety. Yet, you can do things like: Integer[] foo = new Integer[1]; Object[] bar = foo; bar[0] = new Object() And the compiler will let you (although the runtime won't). Its even worse with generics: List<Integer> foo = new ArrayList<>(); List bar = foo; bar.add(new Object()); System.out.println(foo.get(0)); Integer x = foo.get(0); Will compile, and won't even through an exception until the very last line, past the point where you have retrieved and used a non Integer from a List<Integer> In fairness to java on the last one, it is at least a warning, and a deliberate compromise to support backwards compatability when they introduced generics.
hashmash 3y ago
For locally generated strings, it's not a concern. For String.intern, this is actually a very serious bug that should be treated as a security vulnerability.
- gizmo686 3y ago
  At best it is only a security vulnerability if you are running different trust domains within your process. That is something Java supports, but most Java code does not attempt to take advantage of it. Most Java programs have 100% of there code being allowed to use reflection to simply hack the program however they please, including corrupting the intern pool. But still, for the few people who actually trust Java's isolation features and use it, possible bypasses are a concern. Having said that, I don't see how you can turn this into an attack on String.intern. The guarentees about interning are as follows: > When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned. > It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true. If you pollute the pool with a "broken" String, all that would happen is that that String would not be returned in place of a logically equivalent correct String, and vice-versa.
  - hashmash 3y ago
    If a security sensitive operation was (for whatever reason) calling startsWith (as shown in the blog), then it might return an incorrect result. I'm merely speculating that an exploit is possible, and I'm not aware of any code that would be affected. Regardless, the fix is quite simple. The public String.intern method just needs to validate the encoding first. This will have little impact on performance because the String.intern method is rarely called.
    - dundarious 3y ago
      Their point, which I agree with, is that shared memory concurrency requires correct code, and cooperative synchronization between threads, in order to avoid data races; and if your security model is to run untrusted or unverified code with shared memory concurrency, then you cannot ensure correct code or synchronization, and you cannot guarantee against data races. It's perfectly fine to code String.intern() defensively against such dodgy String-s, but in any sizable program with shared memory concurrency and untrusted or unverified code, there will be millions of other potential data races. The only sensible choice would be to not use such a mix.
NotYourLawyer 3y ago
// compareTo does consider them equal (even though its javadoc // specifies that "compareTo returns 0 exactly when the // equals(Object) method would return true") Seems like at least a documentation error.
jillesvangurp 3y ago
Not really. I'm sure there are some edge cases where the ability for someone to do silly things like this is harmful but otherwise this goes in category of things where the general advice is "just don't do that and you're fine". Basically, if you look at why the standard library would not go out of its way to prevent you from doing stuff like this it boils down to the same reason as why they put the string compression optimization in to begin with: doing so would make things slower rather than faster. And that's just not desirable in something as performance critical as string initialization, which is a thing that a lot of Java programs would do a lot. Having string compression helps save some memory but it's a weird low level hack. It's fine as long as you don't actively try to break things in your own program. You'd have to jump through some hoops to do it accidentally. That is not likely to happen just like that. So, not a bug but a known limitation that you should be aware of if you go down the path of doing lots of concurrent modifications to arrays that may or may not be used to create Strings. Java has lots of nice primitives and frameworks to make writing such code less error prone but it's up to you to use those properly and it's entirely possible to write all sorts of code that has lots of concurrency issues.
- brohee 3y ago
  How do you plan to have any assurance that none of your dependencies is doing it? You could well consume a string you didn't build and be affected.
pulse7 3y ago
I remember a bug in Visual/Digitalk Smalltalk: conversion from integer to string (method printString) was not thread safe, because it used global buffer for better performance. Very rarely - when we used a progress indicator in another thread (called Process in Visual Smalltalk) - this global buffer was overriden by another integer to string conversion... It took a year to find out the reason why our code sometimes got wrong results... I submitted the bug to Digitalk and they decided to not fix it (performance reasons). Only in later versions they abandoned the global buffer...
- gene91 3y ago
  I don’t know the terminology for it. But the behavior that you just described isn’t just “not thread safe”. It’s violating basic assumptions. I’d call that hostile or a trap.
  - erik_seaberg 3y ago
    A function that can’t be called while it’s already running is “non-reentrant.” strtok used to work this way (before thread-locals), and some languages predating C that used globals instead of stack frames.
formerly_proven 3y ago
> Attempting to use types in a way that exceeds their documented thread safety has always been allowed to leave your program in an inconsistent state. Wasn't there an attempt for Java to define the range of outcomes even of programs with data races?
- tialaramex 3y ago
  Yes. Java promises (unlike C, C++, Go, etc.) not to have Undefined Behaviour as a result of data races, however you do lose Sequential Consistency, which means humans aren't able to successfully reason about non-trivial programs with data races. More specifically Java says something like, if you race a value of some sort, even a complex value like a hash table, it doesn't get fatally damaged, but its new state is some state it had, or might have during other executions.
  - vacuity 3y ago
    Purely out of curiosity, is that much better? At least the data won't be complete garbage, but there'll still be a logic bug lurking in the details.
    - tialaramex 3y ago
      Sure. In a C++ program all races can cause anything physically possible to happen. So e.g. maybe the program is processing Calendar data, but it's running as the GeneralHR service user on this machine which technically has access to the payroll database. So now Jimmy Smith's insane 4863 meetings which invite himself and a meeting room that hasn't existed for six years causes a data race and the description of a meeting ends up written over part of the stack, which explains why the meeting descriptions were gibberish, because now the machine connects to the payroll DB and sets Jimmy's monthly pay to eighty five thousand six hundred and fourteen bucks... Then it crashes. Oops, bug in the calendar app, well, it worked the next time, so, it's probably fine. Right? It's not Good that the Java code has a bug you don't understand, but it's very unlikely to have completely wild outcomes like giving Jimmy a massive pay rise. When they began this work, as I understand it the Java engineers imagined humans can successfully reason about the resulting bugs, but turns out that's not true. So this work might have been deemed unnecessary if they'd known that but obviously it's hard to know without trying.
coekie 3y ago
Author of the blog here. Yes, this is a bug. While the javadoc doesn't state it explicitly, immutable classes in the core library are expected to be thread safe. Java tries to be and mostly succeeds at being a safe language, where (by default) the guarantees of its internals cannot be broken no matter what user code does. The JVM preserves its own integrity. There are some other deliberate holes in that safety, such as using reflection to access private members, and instrumentation, where it is clear you are stepping outside the safety zone, but even that is getting locked down now with the "Integrity and Strong Encapsulation" effort https://openjdk.org/jeps/8305968 https://openjdk.org/jeps/8305968 . In general, most code we write would not (and should not) try to protect against such abuse, but classes in the core platform play by different rules. Btw, this has been accepted into the bug database now: https://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-8311906 https://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-831190... . I expect this to be fixed in a future release.
- haspok 3y ago
  How would you fix this? Possibly by copying the input array to a local array as the first step? But then you might copy a lot of data, which is in 99% of the cases totally unnecessary. Have a separate threadsafe and a non-threadsafe constructor for char[]? EDIT: another idea is to do a hash of the input array, and compare between start and end. But that also requires an O(n) walk through the input...
  - silon42 3y ago
    /s redesign a language to prevent parallel mutable use of the array
    - pshirshov 3y ago
      This won't happen (unfortunately) for obvious reasons.
  - tpxl 3y ago
    > But that also requires an O(n) walk through the input... Compressing requires an O(n) walk through the input either way.
_old_dude_ 3y ago
It's a TOCTOU bug [1], a well known category of bugs. [1] https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use
- masklinn 3y ago
  Also one more argument for “parse don’t validate”. The code validates a mutable input, and assumes that validation holds thereafter. An incorrect assumption as it turns out.
  - vacuity 3y ago
    While that is good advice, it can't apply to mutable input. Unless a defensive copy is made (at least, under the current system), concurrent modification can still occur. The new type's underlying data is still being accessed.
    - masklinn 3y ago
      There are necessarily copies being made since it's converting a `char[]` to a `byte[]`, the problem is that they're not done correctly. Currently the code tries to encode the chars, and if it fails it completely bails out and restarts with a code unit copy. The bailing and restarting is what offers the opportunity for TOCTOU. But if instead of bailing it converted the data collected so far to code units, then appended the code unit on which it failed, then switched to a UTF16 copy loop, the result would necessarily be correct (at least insofar as a UTF16 string would not contain just latin1) And in fact this would likely be more efficient than the current version, because we already know that everything we've already converted is valid latin-1, which means we can literally just copy that to every other byte. There is no need to re-do that validation and conversion work. Which is currently the case, because StringUTF16.toBytes redoes the entire thing from zero.
      - vacuity 3y ago
        Ah, good points. Thank you for the insight!

neandrake 3y ago

My thinking is the same. I doubt this is an oversight. Making the String constructor thread-safe would likely slow things significantly. Great point about things being assumed not thread-safe. The JDK is pretty thorough with documenting thread-safety.

neandrake 3y ago
Coming back to this the answer is probably not strictly about concurrency and so there is a possibility something would need addressed about this.
masklinn 3y ago
> Making the String constructor thread-safe would likely slow things significantly. By my reckoning it would speed things up, at least going by the Java code.
- neandrake 3y ago
  By what means? The only ways I would expect are either unconditionally duplicating the array or mutex, and I don’t think the mutex wouldn’t be simple. Adding a sync block on the input could be done but that’s assuming nothing else is locked on it (but probably points to there being a race condition elsewhere if there is..). Unconditionally duplicating the array would use more memory and wouldn’t be faster.
  - masklinn 3y ago
    Inlining `StringUTF16.compress` and `StringUTF16.bytes what the code currently does is essentially this (using python as pseudocode): latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c > 255: latin1 = None break latin1[i] = c if latin1 is not None: return LATIN1, latin1 utf16 = bytearray(len(input)*2) for i in range(0, len(input)): c = input[i] utf16[2*i] = c >> HI_BYTE_SHIFT utf16[2*i+1] = c >> LO_BYTE_SHIFT return UTF16, utf16 The issue occurs because `input` can be mutated between the moment it finds a char that's above 255 in the first loop and the moment it visits that same char in the second loop. The solution is to not do that, but instead something like: latin1 = bytearray(len(input)) for i in range(len(input)): c = input[i] if c <= 255: latin1[i] = c continue utf16 = bytearray(len(input)*2) for j in range(i): utf16[2*j] = latin1[j] latin1 = None utf16[2*i] = c utf16[2*i+1] = c >> 8 for j in range(i+1, len(input)): c = input[j] utf16[2*i] = c utf16[2*i+1] = c >> 8 return UTF16, utf16 return LATIN1, latin1 This means if you find a char that's above 255 you will always append that char to the UTF16 array, there's no possibility that someone will change it under you because you append the exact same char you tested. So you can not get into the situation the essay describes, a utf16 string will always contain at least one non-latin1-code unit. Non-vectorised performances should an improvement as latin1 to utf16 is a trivial operation (just copy every byte of the input to every other byte of the output) Though if you vectorised the char to utf16 conversion you now vectorise two loops on bailout (latin1 -> utf16 up to i, then char -> utf16) which is probably less efficient. I don't know if the JDK has vectorised optimisations, the source has "HotSpotIntrinsicCandidate" annotations but I don't know to what extent the intrinsics go.

cempaka 3y ago

That's true, but in the case of Strings in particular they are generally considered to be thread-safe by virtue of being immutable (and the Javadocs themselves say this in many places). Concurrently modifying the input character array may seem like willful abuse in this case, but I suppose there might be some carelessly written code out there which does it and the post shows how it would create some weird and very hard-to-debug behavior. And I can see the argument going both ways as far as the Javadoc: on the one hand, it only promises to return a String representing what is currently in the input character array, which seems to warn against concurrent/subsequent modification at least obliquely. But on the other hand, it does seem to commit to an up-front defensive copy of the input character array which doesn't quite take place, and without which things go a bit haywire if the encoding of the string changes. I don't think the correct answer is to sacrifice any performance to guard against this weird edge case, though.

gizmo686 3y ago
As the article points out, the only thing the Javadoc guarantees is the subsequent modifications of the character array have no effect. It says nothing about concurrent modifications. The type whose thread safety is in question here is not actually String, but char[]. I'm not going to say it is always wrong to share char[] between threads (as a primitive array of something other than double and long, the Java Spec does make some guarentees about char[]), however it is almost always wrong to be sharing char[] between threads. If you want a language that protects you from this type of mistake, you simply need something more advanced than Java. This isn't even the biggest hole in Java's safety. Java has a type system, which is at least a nominal claim to type safety. Yet, you can do things like: Integer[] foo = new Integer[1]; Object[] bar = foo; bar[0] = new Object() And the compiler will let you (although the runtime won't). Its even worse with generics: List<Integer> foo = new ArrayList<>(); List bar = foo; bar.add(new Object()); System.out.println(foo.get(0)); Integer x = foo.get(0); Will compile, and won't even through an exception until the very last line, past the point where you have retrieved and used a non Integer from a List<Integer> In fairness to java on the last one, it is at least a warning, and a deliberate compromise to support backwards compatability when they introduced generics.

hashmash 3y ago

For locally generated strings, it's not a concern. For String.intern, this is actually a very serious bug that should be treated as a security vulnerability.

gizmo686 3y ago
At best it is only a security vulnerability if you are running different trust domains within your process. That is something Java supports, but most Java code does not attempt to take advantage of it. Most Java programs have 100% of there code being allowed to use reflection to simply hack the program however they please, including corrupting the intern pool. But still, for the few people who actually trust Java's isolation features and use it, possible bypasses are a concern. Having said that, I don't see how you can turn this into an attack on String.intern. The guarentees about interning are as follows: > When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned. > It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true. If you pollute the pool with a "broken" String, all that would happen is that that String would not be returned in place of a logically equivalent correct String, and vice-versa.
- hashmash 3y ago
  If a security sensitive operation was (for whatever reason) calling startsWith (as shown in the blog), then it might return an incorrect result. I'm merely speculating that an exploit is possible, and I'm not aware of any code that would be affected. Regardless, the fix is quite simple. The public String.intern method just needs to validate the encoding first. This will have little impact on performance because the String.intern method is rarely called.
  - dundarious 3y ago
    Their point, which I agree with, is that shared memory concurrency requires correct code, and cooperative synchronization between threads, in order to avoid data races; and if your security model is to run untrusted or unverified code with shared memory concurrency, then you cannot ensure correct code or synchronization, and you cannot guarantee against data races. It's perfectly fine to code String.intern() defensively against such dodgy String-s, but in any sizable program with shared memory concurrency and untrusted or unverified code, there will be millions of other potential data races. The only sensible choice would be to not use such a mix.

NotYourLawyer 3y ago

// compareTo does consider them equal (even though its javadoc // specifies that "compareTo returns 0 exactly when the // equals(Object) method would return true") Seems like at least a documentation error.

jillesvangurp 3y ago

Not really. I'm sure there are some edge cases where the ability for someone to do silly things like this is harmful but otherwise this goes in category of things where the general advice is "just don't do that and you're fine". Basically, if you look at why the standard library would not go out of its way to prevent you from doing stuff like this it boils down to the same reason as why they put the string compression optimization in to begin with: doing so would make things slower rather than faster. And that's just not desirable in something as performance critical as string initialization, which is a thing that a lot of Java programs would do a lot. Having string compression helps save some memory but it's a weird low level hack. It's fine as long as you don't actively try to break things in your own program. You'd have to jump through some hoops to do it accidentally. That is not likely to happen just like that. So, not a bug but a known limitation that you should be aware of if you go down the path of doing lots of concurrent modifications to arrays that may or may not be used to create Strings. Java has lots of nice primitives and frameworks to make writing such code less error prone but it's up to you to use those properly and it's entirely possible to write all sorts of code that has lots of concurrency issues.

brohee 3y ago
How do you plan to have any assurance that none of your dependencies is doing it? You could well consume a string you didn't build and be affected.

pulse7 3y ago

I remember a bug in Visual/Digitalk Smalltalk: conversion from integer to string (method printString) was not thread safe, because it used global buffer for better performance. Very rarely - when we used a progress indicator in another thread (called Process in Visual Smalltalk) - this global buffer was overriden by another integer to string conversion... It took a year to find out the reason why our code sometimes got wrong results... I submitted the bug to Digitalk and they decided to not fix it (performance reasons). Only in later versions they abandoned the global buffer...

gene91 3y ago
I don’t know the terminology for it. But the behavior that you just described isn’t just “not thread safe”. It’s violating basic assumptions. I’d call that hostile or a trap.
- erik_seaberg 3y ago
  A function that can’t be called while it’s already running is “non-reentrant.” strtok used to work this way (before thread-locals), and some languages predating C that used globals instead of stack frames.

formerly_proven 3y ago

> Attempting to use types in a way that exceeds their documented thread safety has always been allowed to leave your program in an inconsistent state. Wasn't there an attempt for Java to define the range of outcomes even of programs with data races?

tialaramex 3y ago
Yes. Java promises (unlike C, C++, Go, etc.) not to have Undefined Behaviour as a result of data races, however you do lose Sequential Consistency, which means humans aren't able to successfully reason about non-trivial programs with data races. More specifically Java says something like, if you race a value of some sort, even a complex value like a hash table, it doesn't get fatally damaged, but its new state is some state it had, or might have during other executions.
- vacuity 3y ago
  Purely out of curiosity, is that much better? At least the data won't be complete garbage, but there'll still be a logic bug lurking in the details.
  - tialaramex 3y ago
    Sure. In a C++ program all races can cause anything physically possible to happen. So e.g. maybe the program is processing Calendar data, but it's running as the GeneralHR service user on this machine which technically has access to the payroll database. So now Jimmy Smith's insane 4863 meetings which invite himself and a meeting room that hasn't existed for six years causes a data race and the description of a meeting ends up written over part of the stack, which explains why the meeting descriptions were gibberish, because now the machine connects to the payroll DB and sets Jimmy's monthly pay to eighty five thousand six hundred and fourteen bucks... Then it crashes. Oops, bug in the calendar app, well, it worked the next time, so, it's probably fine. Right? It's not Good that the Java code has a bug you don't understand, but it's very unlikely to have completely wild outcomes like giving Jimmy a massive pay rise. When they began this work, as I understand it the Java engineers imagined humans can successfully reason about the resulting bugs, but turns out that's not true. So this work might have been deemed unnecessary if they'd known that but obviously it's hard to know without trying.

coekie 3y ago

Author of the blog here. Yes, this is a bug. While the javadoc doesn't state it explicitly, immutable classes in the core library are expected to be thread safe. Java tries to be and mostly succeeds at being a safe language, where (by default) the guarantees of its internals cannot be broken no matter what user code does. The JVM preserves its own integrity. There are some other deliberate holes in that safety, such as using reflection to access private members, and instrumentation, where it is clear you are stepping outside the safety zone, but even that is getting locked down now with the "Integrity and Strong Encapsulation" effort https://openjdk.org/jeps/8305968 https://openjdk.org/jeps/8305968 . In general, most code we write would not (and should not) try to protect against such abuse, but classes in the core platform play by different rules. Btw, this has been accepted into the bug database now: https://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-8311906 https://bugs.java.com/bugdatabase/view_bug?bug_id=JDK-831190... . I expect this to be fixed in a future release.

haspok 3y ago
How would you fix this? Possibly by copying the input array to a local array as the first step? But then you might copy a lot of data, which is in 99% of the cases totally unnecessary. Have a separate threadsafe and a non-threadsafe constructor for char[]? EDIT: another idea is to do a hash of the input array, and compare between start and end. But that also requires an O(n) walk through the input...
- silon42 3y ago
  /s redesign a language to prevent parallel mutable use of the array
  - pshirshov 3y ago
    This won't happen (unfortunately) for obvious reasons.
- tpxl 3y ago
  > But that also requires an O(n) walk through the input... Compressing requires an O(n) walk through the input either way.

_old_dude_ 3y ago

It's a TOCTOU bug [1], a well known category of bugs. [1] https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use https://en.wikipedia.org/wiki/Time-of-check_to_time-of-use

masklinn 3y ago
Also one more argument for “parse don’t validate”. The code validates a mutable input, and assumes that validation holds thereafter. An incorrect assumption as it turns out.
- vacuity 3y ago
  While that is good advice, it can't apply to mutable input. Unless a defensive copy is made (at least, under the current system), concurrent modification can still occur. The new type's underlying data is still being accessed.
  - masklinn 3y ago
    There are necessarily copies being made since it's converting a `char[]` to a `byte[]`, the problem is that they're not done correctly. Currently the code tries to encode the chars, and if it fails it completely bails out and restarts with a code unit copy. The bailing and restarting is what offers the opportunity for TOCTOU. But if instead of bailing it converted the data collected so far to code units, then appended the code unit on which it failed, then switched to a UTF16 copy loop, the result would necessarily be correct (at least insofar as a UTF16 string would not contain just latin1) And in fact this would likely be more efficient than the current version, because we already know that everything we've already converted is valid latin-1, which means we can literally just copy that to every other byte. There is no need to re-do that validation and conversion work. Which is currently the case, because StringUTF16.toBytes redoes the entire thing from zero.
    - vacuity 3y ago
      Ah, good points. Thank you for the insight!