Wow, this: "random() was returning values in int range rather than long." is a very nice bug find. Randomness is VERY hard to check for humans. For example, Python's binomial distribution is very bad on some inputs [1], giving widely wrong values, but nobody found it. I bumped into it when I implemented an algorithm to compute the approximate volume of solutions to a DNF, and the results were clearly wrong [2]. The algorithm is explained here by Knuth, in case you are interested [3]
> String to float conversion had a table missing four values. This caused an array access overflow which resulted in imprecise values in some cases.
I've once wrote a function to parse the date format from log files that Go doesn't natively support, and forgot to add November. I quit that job in April, so I never saw any issues. However when 1st of November came my ex-colleagues saw no logs for this day, and when they found out the reason they created a hash tag #nolognovember which you can probably find somewhere to this day :)
This is kind of bug unit tests don't catch. The only way to exhaustively test that you're handling every possible input, is to loop over every possible input (which may tend to infinity).
Therein lies the importance of runtime assertions (so we can sanity check that parsing actually succeeded rather than silently failing) and monitoring (so we can sanity check that, for example, we don't ever go 24 hours without receiving data from the parsing job).
> to loop over every possible input (which may tend to infinity).
This attitude is defeatist. The success of property based testing (see QuichCheck in Haskell or Hypothesis in Python) especially when combined with fuzzing shows that instead of looping over every possible input, looping over thousands of inputs tend to be good enough in practice to catch bugs.
Throwing infinity as a cop out is a lazy opinion held by people who don't understand infinity, or rather, the concept of infinity that's countable. Everything we model on a computer is countably infinite. When we have multiple of such countable infinite sets, the standard dovetail constructions guarantees that their union will be countable. Their Cartesian product will also be countable. You can always obtain an interesting prefix of such an infinite set for testing purposes.
Your tone implies to me that you are under the impression that I'm suggesting one should not test their software. Nothing could be further from the truth.
What I'm saying is that it's foolish not to take any measures at runtime to validate that the system is behaving correctly.
Who's to say that the logs themselves are even formatted correctly? Your software could be perfectly bug-free and you'd still have problems without knowing it, due to bugs in some other person's software. That's the point you're missing - no matter how many edge cases you account for, there's always another edge case.
Oh no not at all. I didn't imply that you are suggesting one shouldn't test their software. Instead, I believe you have an overly narrow view of what tests can accomplish.
I didn't say anything about measures at runtime to validate things. That's complementary to good tests.
Fuzzing does not catch all bugs. And even if it, did your software can still misbehave when all logical bugs are eliminated. Say for example the program parses correctly but uses up a large amount of RAM on certain inputs, causing occasional crashes and restarts in production. Say for example your program behaves perfectly but there's actually an occasional bug in the date formatting in the logs themselves.
So yeah, you need monitoring and assertions. A decent coverage of unit tests is good, but I wouldn't bother trying to invest in some sort of advanced fuzzing or quickcheck system. In my experience the juice isn't worth the squeeze.
IME PBT is complementary to assertions: PBT probes the space of inputs and your assertions find inputs that make your code violate invariants.
When I was writing a nontrivial data structure library I was amazed (and humbled) by how many bugs were caught by PBT (again, combined with copious assertions) but not by my unit tests (which tried to cover all the "obvious" edge cases).
func MonthToString(month int) string {
switch month {
case 1: return "January"
case 2: return "February"
...
case 10: return "October"
case 12: return "December"
default: panic(fmt.Errorf("invalid month number: %d", month))
}
}
are usually written? You take the switch's body, shove it into the test function, and then replace "case/return" with regexp to "assert.Equal" or something:
Well I guess you can have a unit test that checks that there are 12 entries :). Repeating the same list probably wouldn't have found an issue unfortunately
> the vast bulk of sanitizer complaints came from invoking undefined or implementation-defined behavior in harmless ways
This is patently false. Any Undefined Behavior is harmful because it allows the optimizer to insert totally random code, and this is not a purely theoretical behavior, it's been repeatedly demonstrated happening. So even if your UB code isn't called, the simple fact it exists may make some seemingly-unrelated code behave wrongly.
It may theoretically be false, and probably false in some cases, but (at least temporarily) there are cases (not all! but some) where some of the current C compilers currently will never result in bad behavior even if UB actually happens, for now, and those do include some of those mentioned in the article. (not all though; e.g. the actually-used cases of signed overflow could behave badly; of course if one looks at the assembly and makes sure it's what you want, it will be,..as long as the code is always compiled by the specific version of the checked compiler)
For example, in clang/llvm, currently, doing arithmetic UB (signed overflow, out-of-range shifts, offsetting a pointer outside its allocation bounds, offsetting a null pointer, converting an out-of-range float to int, etc) will never result in anything bad, as long as you don't use it (where "using it" includes branching on or using as a load/store address or returning from a function a value derived from it, but doesn't include keeping it in a variable, doing further arithmetic, or even loading/storing it). Of course that's subject to change and not actually guaranteed by any documentation. Not a thing to rely on, but currently you won't ever need to release an emergency fix and get a CVE number for having "void *mem = malloc(10); void *tmp[1]; tmp[0] = mem-((int)two_billion + (int)two_billion); if (two_billion == 0) foo(tmp); free(mem);" in your codebase (..at least if compiling with clang; don't know about other compilers). (yes, that's an immense amount of caveats for an "uhh technically")
> This is patently false. Any Undefined Behavior is harmful because it allows the optimizer to insert totally random code
Undefined to who, though? Specific platforms and toolchains have always attached defined behavior to stuff the standard lists as undefined, and provided ways (e.g. toolchain-specific volatile semantics, memory barriers, intrinsic functions) to exploit that. Even things like inline assembly live in this space of dancing around what the standard allows. And real systems have been written to those tools, successfully. At the bottom of the stack, you basically always have to deal with stuff like this.
Your point is a pedantic proscription, basically. It's (heh) "patently false" to say that "Any Undefined Behavior is harmful".
Yeah, this is especially true if you're writing a libc. E.g., every libc allocator in existence invokes UB with respect to ISO C when it reads metadata placed before a malloc()ed block of memory. Doubly so, since ISO C arguably doesn't even allow a container_of() mechanism at all. At some point, you have to look at what the implementation is actually expecting of your code.
To pick a slightly less obvious example, I doubt (but haven't tried to prove) that it's possible to use the POSIX ancillary data API for Unix domain sockets (i.e., SCM_RIGHTS) without invoking UB.
I think that's technically possible, but you have to use a freshly allocated (and zeroed) buffer every single time, since after it's been written to once, it's 'tainted' with the effective types of the structs stored in it. (Though it looks like the ISO C2y draft finally has language to address this case, with a concept of "byte arrays" that can hold objects of other types, as long as you keep alignments in mind.)
The bigger issue with ISO C and POSIX is everything around 'struct sockaddr': you don't have any way of knowing what types the implementation is internally reading in or writing out. If you give it a casted pointer to a 'struct sockaddr_in' but it reads the sa_family from the 'struct sockaddr *', that's UB; ditto if listen() gives you a 'struct sockaddr_in' and you read the sa_family from a 'struct sockaddr *'. Or if you use 'struct sockaddr_storage' at all, that's also UB. IIRC, the latest POSIX edition just tells implementations to "pretty please allow aliasing between these types in particular!"
Of course, POSIX has nothing on Windows APIs, many of which encourage the caller to cast around pointers with impunity. As far as I'm aware, MSVC doesn't care about strict aliasing at all, and only has a minimal set of optimizations for 'restrict' pointers.
Or use the results of mmap() or futex() system calls, or to model the behavior around barrier/serializing instruction. MMIO is likewise right out. It's just asking too much of the poor language standard to rigorously specify every possible thing you might do with C syntax, even though many of those things can be very valuably implemented in high level languages.
So they punted and left it up to the toolchains, and the toolchains admirably picked up the slack and provided good tools. The problem then becomes the pedants who invent rules like "any UB is harmful" above, not realizing the UB-reliant code is plugging the holes keeping their system afloat.
By contrast, I'd assume any other report by ubsan to be fair game for the optimizer to do its thing and generate whatever code is going to be different from what was likely the developer's intention. If not in the current version, maybe in a future one.
Unless the optimizer has rules around its own intrinsics or whatever, though. Again, this isn't a black/white issue. You need to know what specific toolchains are going to do when writing base level software like C libraries (or RTOS kernels, which is my wheelhouse). The semantics defined by the standard are not sufficient.
Memory barrier builtins, inline assembly and other builtins may not be defined by the standard itself but won't lead in themselves to undefined behavior in my understanding since those are compiler extensions and defined by the implementation. (though invalid use can lead to UB, such as passing 0 to builtin_clz or modifying registers outside of the clobber list in inline assembly)
With that being said, I would definitely expect that the small set of UB that ubsan reports about is actually undefined for the compiler that implements the sanitizer (meaning: either problematic now or problematic in some future update).
I agree. The typical ubsan sanitizers (not all sanitizers though) detect serious issues which should be fixed in all cases and I would definitely consider it best practice to run testing with sanitizers (and I would also would recommend to run many in production).
What are you even saying - what is your definition of "random code". FYI UB is exactly (one of) the places where an optimizer can insert optimized code.
To take an example from the post: in some cases a value was computed that could overflow, but it was not used because of a later overflow check. I think the optimizer would be fully within its rights to delete the code inside the overflow check, because the computation implicitly asserts that it won't overflow (since overflow is undefined). I think this is a more or less useful way of thinking around UB: any operation you put in your program implicitly asserts that the values are such that UB won't happen. For example, dereferencing a pointer implicitly means it cannot be NULL, because derefing NULL is UB, and anything downstream of that deref which checks for NULL can be deleted.
Unfortunately UB is an umbrella term for all sorts of things, and some of those can be very harmful/unexpected, while others are (currently) harmless - but that may change in new compiler versions.
The typical optimization showcase (better code generation for signed integer loop counts) only works when the (undefined behaviour) signed integer overflow doesn't actually happen (e.g. the compiler is free to assume that the loop count won't overflow). But when the signed integer overflow happens all bets are off what will actually happen to the control flow - while that same signed integer overflow in another place may simply wrap around.
Another similar example is to specifically 'inject' UB by putting a `std::unreachable` into the default case of a switch statement. This enables an optimization that the compiler omits a range check before accessing the switch-case jump table. But if the switch-variable isn't handled in a case-branch, the jump table access may be out-of-bounds and there will be a jump to a random location.
In other situations the compiler might even be able to detect at compile time that the UB is triggered and simply generate broken code (usually optimizing away some critical part), or if you're lucky the compiler inserts an ud instruction which crashes the process.
Not OP, but here's an example of "random code" inserted by the compiler[1]: note the assembly instruction "ud2" ("invalid opcode exception" in x86 land) instead of "ret" in not_ok().
You might think this code would be fine if address 0 were mapped to RAM, but both gcc and clang know it's undefined behavior to use the null pointer like that, so they add "random code" that forces a processor exception.
> Passing pointers to the middle of a data structure. For example, free takes a pointer to the start of an allocation. The management structure appears just before that in memory; computing the address of which appears to be undefined behavior to the compiler.
To clarify, the undefined behavior here is that the sanitizer sees `free` trying to access memory outside the bounds of what was returned by `malloc`.
It's perfectly valid to compute the address of a struct just before memory pointed to by a pointer you have, as long as the result points to valid memory:
In the case of `free`, that resulting pointer is technically "invalid" because it's outside what was returned by `malloc`, even though the implementation of `malloc` presumably returned a pointer to memory just past the header.
Yeah; I used to enjoy poking through C code in well written programs. It’s amazing what gems you can find by people who really know their stuff.
I saw a string library once which took advantage of this. The library passed around classic C style char* pointers. They work in printf, and basically all C code that expects a string. But the strings had extra metadata stored before the string content. That metadata contained the string’s current length and the total allocation size. As a result, you could efficiently get a string length without scanning, append to a string, and do all sorts of other useful things that are tricky to do with bare allocations. All while maintaining support for the rest of the C ecosystem. It’s a very cool trick!
The Windows API uses this scheme for one of its 50 string types [1].
I"m not very fond of this design as it's easy to pass a "normal" C string, which compiles because BSTR is just a typedef to it.
You can allocate the exact same data structure, but store a pointer to the size prefix, instead of the first byte - you avoid that issue, and can still pass the data field to anything expecting a zero-terminated string:
That arithmetic shift right implementation is also what I came up with for a video game fantasy architecture that only has logical shift right. (16-bit registers)
; asr rd, rs1, rs2 ; rd = signed(rs1) >> rs2
and rt, rs1, 0x8000 ; isolate sign bit
lsr rt, rt, rs2 ; shift sign bit to final position
neg rt, rt ; sign-extended part of final result
lsr rd, rs1, rs2 ; base part of final result
or rd, rd, rt ; combine both parts
It might be easier to understand broken down this way for anyone who didn't understand the article's one-liner.
Wow, this: "random() was returning values in int range rather than long." is a very nice bug find. Randomness is VERY hard to check for humans. For example, Python's binomial distribution is very bad on some inputs [1], giving widely wrong values, but nobody found it. I bumped into it when I implemented an algorithm to compute the approximate volume of solutions to a DNF, and the results were clearly wrong [2]. The algorithm is explained here by Knuth, in case you are interested [3]
[1] https://www.cs.toronto.edu/~meel/Slides/meel-distform.pdf [2] https://github.com/meelgroup/pepin [3] https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
> String to float conversion had a table missing four values. This caused an array access overflow which resulted in imprecise values in some cases.
I've once wrote a function to parse the date format from log files that Go doesn't natively support, and forgot to add November. I quit that job in April, so I never saw any issues. However when 1st of November came my ex-colleagues saw no logs for this day, and when they found out the reason they created a hash tag #nolognovember which you can probably find somewhere to this day :)
> when 1st of November came my ex-colleagues saw no logs for this day
Faced with this symptom I would bet there was a "No" in a yaml somewhere :-)
Who needs unit tests when you have "squints lgtm"
This is kind of bug unit tests don't catch. The only way to exhaustively test that you're handling every possible input, is to loop over every possible input (which may tend to infinity).
Therein lies the importance of runtime assertions (so we can sanity check that parsing actually succeeded rather than silently failing) and monitoring (so we can sanity check that, for example, we don't ever go 24 hours without receiving data from the parsing job).
> to loop over every possible input (which may tend to infinity).
This attitude is defeatist. The success of property based testing (see QuichCheck in Haskell or Hypothesis in Python) especially when combined with fuzzing shows that instead of looping over every possible input, looping over thousands of inputs tend to be good enough in practice to catch bugs.
Throwing infinity as a cop out is a lazy opinion held by people who don't understand infinity, or rather, the concept of infinity that's countable. Everything we model on a computer is countably infinite. When we have multiple of such countable infinite sets, the standard dovetail constructions guarantees that their union will be countable. Their Cartesian product will also be countable. You can always obtain an interesting prefix of such an infinite set for testing purposes.
Your tone implies to me that you are under the impression that I'm suggesting one should not test their software. Nothing could be further from the truth.
What I'm saying is that it's foolish not to take any measures at runtime to validate that the system is behaving correctly.
Who's to say that the logs themselves are even formatted correctly? Your software could be perfectly bug-free and you'd still have problems without knowing it, due to bugs in some other person's software. That's the point you're missing - no matter how many edge cases you account for, there's always another edge case.
Oh no not at all. I didn't imply that you are suggesting one shouldn't test their software. Instead, I believe you have an overly narrow view of what tests can accomplish.
I didn't say anything about measures at runtime to validate things. That's complementary to good tests.
No there are 12 months you can exhaustively test 12 cases.
It's called fuzzing.
Fuzzing does not catch all bugs. And even if it, did your software can still misbehave when all logical bugs are eliminated. Say for example the program parses correctly but uses up a large amount of RAM on certain inputs, causing occasional crashes and restarts in production. Say for example your program behaves perfectly but there's actually an occasional bug in the date formatting in the logs themselves.
So yeah, you need monitoring and assertions. A decent coverage of unit tests is good, but I wouldn't bother trying to invest in some sort of advanced fuzzing or quickcheck system. In my experience the juice isn't worth the squeeze.
IME PBT is complementary to assertions: PBT probes the space of inputs and your assertions find inputs that make your code violate invariants.
When I was writing a nontrivial data structure library I was amazed (and humbled) by how many bugs were caught by PBT (again, combined with copious assertions) but not by my unit tests (which tried to cover all the "obvious" edge cases).
Pfft, you know how tests for functions like this:
are usually written? You take the switch's body, shove it into the test function, and then replace "case/return" with regexp to "assert.Equal" or something: Look ma, we got that sweet 100% code coverage!The solution is to add integration testing,
the reverse composition is harder to test.Did you mean property testing?
I feel attacked! (:>
Nice nick name. What happened to the first one?
It got dropped.
Again??
Well I guess you can have a unit test that checks that there are 12 entries :). Repeating the same list probably wouldn't have found an issue unfortunately
> the vast bulk of sanitizer complaints came from invoking undefined or implementation-defined behavior in harmless ways
This is patently false. Any Undefined Behavior is harmful because it allows the optimizer to insert totally random code, and this is not a purely theoretical behavior, it's been repeatedly demonstrated happening. So even if your UB code isn't called, the simple fact it exists may make some seemingly-unrelated code behave wrongly.
It may theoretically be false, and probably false in some cases, but (at least temporarily) there are cases (not all! but some) where some of the current C compilers currently will never result in bad behavior even if UB actually happens, for now, and those do include some of those mentioned in the article. (not all though; e.g. the actually-used cases of signed overflow could behave badly; of course if one looks at the assembly and makes sure it's what you want, it will be,..as long as the code is always compiled by the specific version of the checked compiler)
For example, in clang/llvm, currently, doing arithmetic UB (signed overflow, out-of-range shifts, offsetting a pointer outside its allocation bounds, offsetting a null pointer, converting an out-of-range float to int, etc) will never result in anything bad, as long as you don't use it (where "using it" includes branching on or using as a load/store address or returning from a function a value derived from it, but doesn't include keeping it in a variable, doing further arithmetic, or even loading/storing it). Of course that's subject to change and not actually guaranteed by any documentation. Not a thing to rely on, but currently you won't ever need to release an emergency fix and get a CVE number for having "void *mem = malloc(10); void *tmp[1]; tmp[0] = mem-((int)two_billion + (int)two_billion); if (two_billion == 0) foo(tmp); free(mem);" in your codebase (..at least if compiling with clang; don't know about other compilers). (yes, that's an immense amount of caveats for an "uhh technically")
> So even if your UB code isn't called, the simple fact it exists may make some seemingly-unrelated code behave wrongly.
This is fortunately not true. If it were, it would make runtime checks pointless. Consider this code
The second free would be undefined behavior, but since it doesn't run the snippet is fine.> This is patently false. Any Undefined Behavior is harmful because it allows the optimizer to insert totally random code
Undefined to who, though? Specific platforms and toolchains have always attached defined behavior to stuff the standard lists as undefined, and provided ways (e.g. toolchain-specific volatile semantics, memory barriers, intrinsic functions) to exploit that. Even things like inline assembly live in this space of dancing around what the standard allows. And real systems have been written to those tools, successfully. At the bottom of the stack, you basically always have to deal with stuff like this.
Your point is a pedantic proscription, basically. It's (heh) "patently false" to say that "Any Undefined Behavior is harmful".
Yeah, this is especially true if you're writing a libc. E.g., every libc allocator in existence invokes UB with respect to ISO C when it reads metadata placed before a malloc()ed block of memory. Doubly so, since ISO C arguably doesn't even allow a container_of() mechanism at all. At some point, you have to look at what the implementation is actually expecting of your code.
To pick a slightly less obvious example, I doubt (but haven't tried to prove) that it's possible to use the POSIX ancillary data API for Unix domain sockets (i.e., SCM_RIGHTS) without invoking UB.
I think that's technically possible, but you have to use a freshly allocated (and zeroed) buffer every single time, since after it's been written to once, it's 'tainted' with the effective types of the structs stored in it. (Though it looks like the ISO C2y draft finally has language to address this case, with a concept of "byte arrays" that can hold objects of other types, as long as you keep alignments in mind.)
The bigger issue with ISO C and POSIX is everything around 'struct sockaddr': you don't have any way of knowing what types the implementation is internally reading in or writing out. If you give it a casted pointer to a 'struct sockaddr_in' but it reads the sa_family from the 'struct sockaddr *', that's UB; ditto if listen() gives you a 'struct sockaddr_in' and you read the sa_family from a 'struct sockaddr *'. Or if you use 'struct sockaddr_storage' at all, that's also UB. IIRC, the latest POSIX edition just tells implementations to "pretty please allow aliasing between these types in particular!"
Of course, POSIX has nothing on Windows APIs, many of which encourage the caller to cast around pointers with impunity. As far as I'm aware, MSVC doesn't care about strict aliasing at all, and only has a minimal set of optimizations for 'restrict' pointers.
Or use the results of mmap() or futex() system calls, or to model the behavior around barrier/serializing instruction. MMIO is likewise right out. It's just asking too much of the poor language standard to rigorously specify every possible thing you might do with C syntax, even though many of those things can be very valuably implemented in high level languages.
So they punted and left it up to the toolchains, and the toolchains admirably picked up the slack and provided good tools. The problem then becomes the pedants who invent rules like "any UB is harmful" above, not realizing the UB-reliant code is plugging the holes keeping their system afloat.
Ubsan docs do mention one case where UB is defined by the implementation: floating point division by zero: https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
By contrast, I'd assume any other report by ubsan to be fair game for the optimizer to do its thing and generate whatever code is going to be different from what was likely the developer's intention. If not in the current version, maybe in a future one.
Unless the optimizer has rules around its own intrinsics or whatever, though. Again, this isn't a black/white issue. You need to know what specific toolchains are going to do when writing base level software like C libraries (or RTOS kernels, which is my wheelhouse). The semantics defined by the standard are not sufficient.
Memory barrier builtins, inline assembly and other builtins may not be defined by the standard itself but won't lead in themselves to undefined behavior in my understanding since those are compiler extensions and defined by the implementation. (though invalid use can lead to UB, such as passing 0 to builtin_clz or modifying registers outside of the clobber list in inline assembly)
With that being said, I would definitely expect that the small set of UB that ubsan reports about is actually undefined for the compiler that implements the sanitizer (meaning: either problematic now or problematic in some future update).
I agree. The typical ubsan sanitizers (not all sanitizers though) detect serious issues which should be fixed in all cases and I would definitely consider it best practice to run testing with sanitizers (and I would also would recommend to run many in production).
> optimizer to insert totally random code
What are you even saying - what is your definition of "random code". FYI UB is exactly (one of) the places where an optimizer can insert optimized code.
To take an example from the post: in some cases a value was computed that could overflow, but it was not used because of a later overflow check. I think the optimizer would be fully within its rights to delete the code inside the overflow check, because the computation implicitly asserts that it won't overflow (since overflow is undefined). I think this is a more or less useful way of thinking around UB: any operation you put in your program implicitly asserts that the values are such that UB won't happen. For example, dereferencing a pointer implicitly means it cannot be NULL, because derefing NULL is UB, and anything downstream of that deref which checks for NULL can be deleted.
Unfortunately UB is an umbrella term for all sorts of things, and some of those can be very harmful/unexpected, while others are (currently) harmless - but that may change in new compiler versions.
The typical optimization showcase (better code generation for signed integer loop counts) only works when the (undefined behaviour) signed integer overflow doesn't actually happen (e.g. the compiler is free to assume that the loop count won't overflow). But when the signed integer overflow happens all bets are off what will actually happen to the control flow - while that same signed integer overflow in another place may simply wrap around.
Another similar example is to specifically 'inject' UB by putting a `std::unreachable` into the default case of a switch statement. This enables an optimization that the compiler omits a range check before accessing the switch-case jump table. But if the switch-variable isn't handled in a case-branch, the jump table access may be out-of-bounds and there will be a jump to a random location.
In other situations the compiler might even be able to detect at compile time that the UB is triggered and simply generate broken code (usually optimizing away some critical part), or if you're lucky the compiler inserts an ud instruction which crashes the process.
Not OP, but here's an example of "random code" inserted by the compiler[1]: note the assembly instruction "ud2" ("invalid opcode exception" in x86 land) instead of "ret" in not_ok().
You might think this code would be fine if address 0 were mapped to RAM, but both gcc and clang know it's undefined behavior to use the null pointer like that, so they add "random code" that forces a processor exception.
[1] https://godbolt.org/z/sK55YsGz1
That doesn't sound very random to me!
> Passing pointers to the middle of a data structure. For example, free takes a pointer to the start of an allocation. The management structure appears just before that in memory; computing the address of which appears to be undefined behavior to the compiler.
To clarify, the undefined behavior here is that the sanitizer sees `free` trying to access memory outside the bounds of what was returned by `malloc`.
It's perfectly valid to compute the address of a struct just before memory pointed to by a pointer you have, as long as the result points to valid memory:
In the case of `free`, that resulting pointer is technically "invalid" because it's outside what was returned by `malloc`, even though the implementation of `malloc` presumably returned a pointer to memory just past the header.Yeah; I used to enjoy poking through C code in well written programs. It’s amazing what gems you can find by people who really know their stuff.
I saw a string library once which took advantage of this. The library passed around classic C style char* pointers. They work in printf, and basically all C code that expects a string. But the strings had extra metadata stored before the string content. That metadata contained the string’s current length and the total allocation size. As a result, you could efficiently get a string length without scanning, append to a string, and do all sorts of other useful things that are tricky to do with bare allocations. All while maintaining support for the rest of the C ecosystem. It’s a very cool trick!
The Windows API uses this scheme for one of its 50 string types [1].
I"m not very fond of this design as it's easy to pass a "normal" C string, which compiles because BSTR is just a typedef to it.
You can allocate the exact same data structure, but store a pointer to the size prefix, instead of the first byte - you avoid that issue, and can still pass the data field to anything expecting a zero-terminated string:
[1] BSTR - https://learn.microsoft.com/en-us/previous-versions/windows/...And don't forget -fbounds-safety, which is in Apple's clang/llvm and perhaps other versions. https://clang.llvm.org/docs/BoundsSafety.html
> [...] detect places where the program wanders into parts of the C language specification [...]
Small nitpick, the UB sanitizer also has some checks specific for C++ https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
That arithmetic shift right implementation is also what I came up with for a video game fantasy architecture that only has logical shift right. (16-bit registers)
It might be easier to understand broken down this way for anyone who didn't understand the article's one-liner.