HNHacker News
TopNewBestAskShowJobs

charleslmunger

1,327 karma · joined March 3, 2013

submissionscomments
charleslmunger··on What If OpenDocument Used SQLite?
>and they seem to get annoyed that people run fuzzers against SQLite, even though application file formats should definitely be fuzzed.

I think that's an unfair reading. Sqlite runs fuzzers itself and quickly addresses bugs found by fuzzers externally. There's an entire section in their documentation about their own fuzzers and thanking third party fuzzers, including credit to individual engineers.

https://www.sqlite.org/testing.html

The tone of the CVE docs are because people freak out about CVEs flagged by automated tools when the CVEs are for issues that have no security impact for typical usage of SQLite, or have prerequisites that would already have resulted in some form of compromise.

charleslmunger··on Fil's Unbelievable Garbage Collector
This is really cool! I noticed

>The fast path of a pollcheck is just a load-and-branch.

A neat technique I've seen used to avoid these branches is documented at https://android-developers.googleblog.com/2023/11/the-secret... under "Implicit suspend checks".

charleslmunger··on SQLite (with WAL) doesn't do `fsync` on each commit under default settings
>If you switch to WAL mode, the default behavior is that transactions are durable across application crashes (or SIGKILL or similar) but are not necessarily durable across OS crashes or power failures. Transactions are atomic across OS crashes and power failures. But if you commit a transaction in WAL mode and take a power loss shortly thereafter, the transaction might be rolled back after power is restored.

How is this behavior reconciled with the documentation cited in my comment above? Are the docs just out of date?

charleslmunger··on SQLite (with WAL) doesn't do `fsync` on each commit under default settings
>EXTRA synchronous is like FULL with the addition that the directory containing a rollback journal is synced after that journal is unlinked to commit a transaction in DELETE mode. EXTRA provides additional durability if the commit is followed closely by a power loss.

It depends on your filesystem whether this is necessary. In any case I'm pretty sure it's not relevant for WAL mode.

charleslmunger··on SQLite (with WAL) doesn't do `fsync` on each commit under default settings
The default is FULL

https://sqlite.org/compile.html#default_synchronous

>SQLITE_DEFAULT_SYNCHRONOUS=<0-3> This macro determines the default value of the PRAGMA synchronous setting. If not overridden at compile-time, the default setting is 2 (FULL).

>SQLITE_DEFAULT_WAL_SYNCHRONOUS=<0-3> This macro determines the default value of the PRAGMA synchronous setting for database files that open in WAL mode. If not overridden at compile-time, this value is the same as SQLITE_DEFAULT_SYNCHRONOUS.

Many wrappers for sqlite take this advice and change the default, but the default is FULL.

charleslmunger··on Traps to Developers
I too interpretat those docs as contradictory, and I wonder if, like how Java 5 strengthened volatile semantics, this happened at some point in C# too and the docs weren't updated? Either way the specification, which the docs say is definitive, says it's acquire/release.

https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...

"When a field_declaration includes a volatile modifier, the fields introduced by that declaration are volatile fields. [...] For volatile fields, such reordering optimizations are restricted:

    A read of a volatile field is called a volatile read. A volatile read has “acquire semantics”; that is, it is guaranteed to occur prior to any references to memory that occur after it in the instruction sequence.

    A write of a volatile field is called a volatile write. A volatile write has “release semantics”; that is, it is guaranteed to happen after any memory references prior to the write instruction in the instruction sequence."
charleslmunger··on Traps to Developers
>A volatile write operation prevents earlier memory operations on the thread from being reordered to occur after the volatile write. A volatile read operation prevents later memory operations on the thread from being reordered to occur before the volatile read

Looks like release/acquire to me? A total ordering would be sequential consistency.

charleslmunger··on Writing memory efficient C structs
Avoiding false sharing is a separate problem best solved by explicitly aligning the struct or relevant members to std::hardware_destructive_interference_size.
charleslmunger··on I wasted weeks hand optimizing assembly because I benchmarked on random data
I tried implementing an optimized varint encoder that did something similar, by populating an 8 byte value and then storing it to ram, but unaligned overlapping stores caused big regressions. The approach that worked required a different technique. This one is for encoding backwards:

1. One branch for the one-byte case, always inlined, just store the byte

2. Calculate the size size of the unencoded zero prefix with a branch-free construction: (((uint32_t)clz + 7) * 9) >> 6

3. Hand roll a jump table taking advantage of arm's fixed instruction width to calculate the jump target with a shift.

https://github.com/protocolbuffers/protobuf/commit/b039dfe26...

This results in one branch for 1 byte varints, plus one additional branch for any larger size, and the branch predictor does not have to track a varying trip count through a loop. This approach resulted in a 2.64% speedup for overall encoding (which includes a lot more than just varints) on mid sized arm cores.

I think it's very difficult to beat a single comparison and branch for the 1 byte case for actual encoding forwards or backwards, unless you know there's going to be long runs of one-byte values.

charleslmunger··on SQLite async connection pool for high-performance
A connection pool is absolutely a best practice. One of the biggest benefits is managing a cache of prepared statements, the page cache, etc. Maybe you have temp tables or temp triggers too.

Even better is to have separate pools for the writer connection and readers in WAL mode. Then you can cache write relevant statements only once. I am skeptical about a dedicated thread per call because that seems like it would add a bunch of latency.

charleslmunger··on Async Queue – One of my favorite programming interview questions
How did you make it wait free with only compare and swap?
charleslmunger··on Async Queue – One of my favorite programming interview questions
It's too hard because the variations you could add to it (multi threading) that add enough depth to make it hard make it too hard, in my opinion. If you look at the implementation I linked in my previous comment, it's fully lock-free, which is pretty unreasonable to expect from anyone who isn't already familiar with lock free concurrency. On the other hand the version with a lock is basically identical to the single thread version. Asking for the two-lock queue is also a bad interview question because it's not something you'd reasonably expect someone to derive in an interview.

The other examples given for fleshing it out are all pretty similar; if a candidate can do one, chances are they can do the others too. If you want to get a decent signal if candidate skill, you have to ask a question easy enough that any candidate you'd accept can answer it, then incrementally add difficulty until you've given the candidate a chance to show off the limit of their abilities (at least as applied to your question).

Otherwise you ask a too-easy question which everyone nails, then make it way too hard and everyone fails. Or you ask a too-easy question and follow it up with additional enhancements that don't actually add much difficulty, and again all the candidates look similar. That's just my experience; the author seems pleased with the question so maybe they're getting good signal out of it.

charleslmunger··on Async Queue – One of my favorite programming interview questions
I've implemented multiple production versions of this problem (but not in JavaScript)[1], so maybe my view of this problem is miscalibrated...

This feels both too easy and too hard for an interview? I would expect almost any new grad to be able to implement this in the language of their choice. Adding delays makes it less trivial, except that the answer is... Just use the function provided by the language. That's the right answer for real code, but what are you really assessing by asking it?

[1] https://github.com/google/guava/blob/master/guava/src/com/go...

charleslmunger··on Yet Another Zip Trick
Check out CVE-2017-13156 which is a real exploit that leveraged differences in zip parsing to bypass a signature scheme.
charleslmunger··on The provenance memory model for C
This is doable via this trick:

https://github.com/protocolbuffers/protobuf/blob/ae0129fcd01...

charleslmunger··on Libxml2's "no security embargoes" policy
If there was another bug that allowed input data to request a large allocation, this would be?

Normally I'd want a secure parser to allocate memory with a bound, and one way to implement that is to give each parse call an allocator that fails once it reaches a limit. From a very basic scan it seems like libxml2 supports swapping its allocator function, so it could do this; although that's probably not the intended purpose since those APIs are global rather than per parser instance.

I bet what happened here is the reporter ran a fuzzer, found a report, and didn't realize that the fuzzer configuration was injecting faults into malloc so they thought it was more severe than it actually was. Missing a bounds check often results in some massive number being passed to malloc, which then returns null, so this is a common pattern to find. It's not a high severity security bug but it's reasonable to think it could be one if you didn't know about the fault injecting allocator.

charleslmunger··on I was surprised by how simple an allocator is
If you use upb, an allocator is optional - you can provide a presized block to upb_Arena and a NULL upb_alloc. Of course, you'll still fail to parse a message with an in memory representation larger than your region.
charleslmunger··on How fast can the RPython GC allocate?
I simulated yours vs the UPB arena fast path:

https://godbolt.org/z/1oTrv1Y58

Messing with it a bit, it seems like yours has a slightly shorter dependency chain due to loading the two members separately, where UPB loads them as a pair (as it needs both in order to determine how much size is available). Also seems to have less register pressure. I think that's because yours bumps down. UPB's supports in place forward extension, so it needs to bump up.

If you added branch hints to signal to the compiler that your slow path is not often hit, you might see some improvement (although if you have PGO it should already do this). These paths could also be good candidates for the `preserve_most` calling convention.

However, there is an unfortunate compiler behavior here for both implementations - it doesn't track whether the slow path (which is not inlined, and clobbers the pointers) was actually hit, so it reloads on the hot path, for both approaches. Unfortunately this means that a sequence of allocations will store and load the arena pointers repeatedly, when ideally they'd keep the current position in a register on the hot path and refill that register after clobbering in the cold path.

charleslmunger··on Machine Code Isn't Scary
You can use __builtin_expect_with_probability with 0.5 to tell the compiler to be consistent in using a select rather than a branch.
charleslmunger··on Atomics and Concurrency
You can't precisely convert it to c++, because there's no c++ construct that precisely matches Java behavior - namely atomic with relaxed memory order but permitting aliasing and load/store optimizations. The spiritually closest thing would just be a regular variable, which would be a data race that tsan would catch.

You can go the other way, porting that c++ to Java using varhandle and opaque memory order.

charleslmunger··on Atomics and Concurrency
Also the programs are not direct translations of each other - a direct translation to Java would use varhandle and opaque (equivalent to relaxed), and then would not contain a data race.
charleslmunger··on Atomics and Concurrency
No, because it's atomic. If that was a data race, and data races are UB, there would be no point in having relaxed atomics.

It's not my criterion, it's defined in the language standard. You can't have a data race on an atomic except for std::atomic_init. The reads on the string contents themselves are ordered because the args string is initialized before the thread is launched and the other one is static. If the launched thread allocated a new string and then populated the atomic, that would be a data race, unless stronger memory order was used by both the writer and the reader.

charleslmunger··on Atomics and Concurrency
Actually I don't think your c++ program contains a data race, because the writes that populated the argument string happened before the atomic read. If you copied the string on the other thread before writing the pointer or you used a non atomic variable, I bet tsan would catch it.
charleslmunger··on Atomics and Concurrency
>When a program contains two conflicting accesses (§17.4.1) that are not ordered by a happens-before relationship, it is said to contain a data race.

Yes, your program contains a data race, by the definition used in the JLS. The set of outcomes you may observe from a data race are specified. I'm not sure if this choice was intentional or not, but there is a guarantee that you will either print the argument or "uninitialized" and no other behavior, because String relies on final field semantics. This is would not be true in c/c++ where the equivalent code is undefined behavior and you could see any result.

In Java you can have a data race and use it productively for certain niche cases, like String.hashcode - I've also contributed some to the Guava concurrency library. This is not true in c/c++ where data races (by their definition) are undefined behavior. If you want to do the tricks you can in racy Java without UB, you have to declare your variables atomic and use relaxed memory order and possibly fences.

charleslmunger··on An appeal to companies doing AI
>Oh, in US, for US citizens, intelligence agencies can't do dragnet surveillance.

They can, and do? What else would you call https://www.theguardian.com/world/2013/jun/06/nsa-phone-reco...

That's just one example, Snowden published tons of this stuff.

charleslmunger··on Four Years of Jai (2024)
>My point is that memory is usually the least of one’s problem, even on average machines.

The average machine a person directly interacts with is a phone or TV at this point, both of which have major BoM restrictions and high pixel density displays. Memory is the primary determination of performance in such environments.

On desktops and servers, CPU performance is bottlenecked on memory - garbage collection isn't necessarily a problem there, but the nature of separate allocations and pointer chasing is.

On battery, garbage collection costs significant power and so it gets deferred (at least for full collections) until it's unavoidable. In practice this means that a large amount of heap space is "dead", which costs memory.

Your language sounds interesting - I've always thought that it would be cool to have a language where generational GC was exposed to the programmer. If you have a server, you can have one new generation arena per request with a write barrier for incoming references from the old generation to the new. Then you could perform young GC after every request, only paying for traversal+move of objects that survived.

charleslmunger··on Not OK Cupid – A story of poor email address validation
There's other good reasons not to use a random string! Try calling up customer service, they'll ask you the question, and you can say "oh it's just a bunch of random letters and numbers".

Unlike a code or password, these security questions are fuzzy matches generally based on the judgment of human on the other end.

charleslmunger··on New USPTO Memo Makes Fighting Patent Trolls Even Harder
https://patents.google.com/patent/US20080270152

https://patents.google.com/patent/US20070244837

charleslmunger··on HTTP/3 is everywhere but nowhere
A dropped packet requires a retransmit which is effectively a round trip. Introducing shared fate by bundling many requests into a single TCP connection results in more requests being delayed by round trips per dropped packet.
charleslmunger··on HTTP/3 is everywhere but nowhere
At the cost of head-of-line blocking - one dropped TCP packet delays all HTTP/2 streams.
← PreviousPage 3 of 16Next →