Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fixing stutters in Papers Please on Linux

blog.jhm.dev

Post reply on HN
Print view View original

171–180 of 202 posts

Re: Fixing stutters in Papers Please on Linux

#171

Post by kennylevinsen »

infogulch wrote: post #130
CyberRabbi wrote: post #72

Earlier quoted context omitted.

While tempting, you can’t generally fix this by simply patching close() with some function that converts it to an unchecked asynchronous operation. If that were the case, you could just do that in the kernel. Close() is expected to complete synchronously. This matters because posix guarantees that open()/pipe() etc. will return the lowest file descriptor not in use[1]. I.e. this should work: close(0); fd = open(“/foo…

I did not know this, and for some reason it really annoys me. Why are our process contexts littered with useless little synchronous properties? How many other tedious and slow bookkeeping tasks does the OS have to do just to meet some outdated spec that was probably just an ossified implementation detail in the first place? I feel compelled to make it so that new fds are explicitly randomized just so you can't do thi…

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value.

Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles.

Go would also be better off without, but they are catering to a different audience and different degree of specification, and apparently need to actively deter developers from ignoring documentation.

Re: Fixing stutters in Papers Please on Linux

#172

Post by cturner »

arghwhat wrote: post #170
cturner wrote: post #169

Earlier quoted context omitted.

"You only need a mitigation if it ends up blocking long enough to be a problem in reasonable setups." That criteria is established here - the OP is about an issue affecting paying end-users! Premature optimisation is not relevant - the software is failing. It is unsafe to make fair-weather assumptions about customer systems. Consider a common software failure: where the user is saving data to a SMB or NFS partition,…

> That criteria is established here - the OP is about an issue affecting paying end-users! Premature optimisation is not relevant - the software is failing. The software is not failing, it is experiencing performance degradation: a 500ms pause whenever excessive and entirely unnecessary work is done. The solution is to not do the work. Moving open/close to a different thread is premature optimization, as no necessary…

"implies non-blocking fds"

I don't think the open and close calls respect non-blocking on linux when operating on files (specifically files, not sockets - for sockets the return is always quick as far as I know). From man open(2), "I/O operations will (briefly) block when device activity is required, regardless of whether O_NONBLOCK is set". And my recollection is that they will non-briefly block if the problem is a hanging NFS mount.

"What are you going to do when they don't return? Accumulate dead threads and inconsistent shared application state?"

Good point. My practice is to use child processes. These can be killed, and so I do not run into this. But subprocesses ratchets up the amount of work to be done, because you then need to do async IPC. So it's now a lot of extra work. It's even worse for multiplatform stuff because now you are exposed to platform differences (e.g. select is suboptimal on Linux, but poll is not available on Windows).

As you say, using threads within same proc would lead to stale threads. In some contexts this would be tolerable but it is not nearly as simple+clean as I presented.

Thinking hard about addressing this on Linux brings me down, every time. I hope io_uring will make pure async practical within a single process. Even if it does, the multiplatform story will remain complex. I am not fond of your disregard for user data in the (tangential) discussion about disappearing filesystems, but you have won me over to embracing the main thread in this context.

Re: Fixing stutters in Papers Please on Linux

#173

Post by arghwhat »

CyberRabbi wrote: post #84
loeg wrote: post #81

Earlier quoted context omitted.

> Logically you should expect it to block indefinitely Frankly, that’s completely insane. It should block if and only if there is actual io in flight which could produce a failure return that an application needs. Syscalls should be fast unless there is a very good reason not to be.

> It should block if and only if there is actual io in flight which could produce a failure return that an application needs. Blocking simply means that the specification does not guarantee an upper bound on the completion time. There is no other meaningful definition. POSIX is not an RTOS therefore nearly all system calls block. The alternative is that the specification guarantees an upper bound on completion time.…

The machine is not running POSIX, it's running Linux which is POSIX-ey, and an RTOS does not guarantee that system calls do not block. The insistence on only referring to POSIX was what caused the O_PONIES debate in the first place.

If one assumes that "there is no upper bound on the completion time", then that also means assuming that a poll/read/write will never return within the lifetime of the machine as it could block for that long (maybe you're using this computer: https://www.youtube.com/watch?v=nm0POwEtiqE), and so it is impossible to implement a functioning, responsive application, much less a game.

In the real-world you need to make slightly more reasonable assumptions. And, again, when interacting with device files you must refer to the kernel documentation rather than POSIX, as POSIX does not describe how these files work in any meaningful way or form.

Re: Fixing stutters in Papers Please on Linux

#174

Post by nisegami »

satnome wrote: post #99
arghwhat wrote: post #7

The issue has been identified before, but seems like it stalled: https://gitlab.freedesktop.org/libinput/libinput/-/issues/50... , https://patchwork.kernel.org/project/linux-input/patch/20201... .

Just curious, how did you nail it down to that specific issue and patch? That seems like a great skill to have.

With git, the command git bisect provides a mechanism for using binary search on a range of commits.

Re: Fixing stutters in Papers Please on Linux

#175

Post by loeg »

kennylevinsen wrote: post #171
infogulch wrote: post #130

Earlier quoted context omitted.

I did not know this, and for some reason it really annoys me. Why are our process contexts littered with useless little synchronous properties? How many other tedious and slow bookkeeping tasks does the OS have to do just to meet some outdated spec that was probably just an ossified implementation detail in the first place? I feel compelled to make it so that new fds are explicitly randomized just so you can't do thi…

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value. Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles. Go would also…

If we ignore POSIX for a moment, the kernel could avoid contending on the one-per-process fd map by sharding the integers into distinct allocation ranges per thread. This would eliminate a source of contention between threads.

In addition to violating POSIX’ lowest hole rule, it would break select(2) (more than it’s already broken).

Re: Fixing stutters in Papers Please on Linux

#176

Post by CyberRabbi »

kennylevinsen wrote: post #167
CyberRabbi wrote: post #56

Earlier quoted context omitted.

What the proposed patch does is delay a specific latent operation to an asynchronous context so that close() doesn’t block on that operation (which is freeing some memory). The proposed patch isn’t a comprehensive fix, it admits there are still other sources of relatively high close() latency. So that got me thinking, there is no way to fix this “bug” because there is no specification on how long close() should take…

Patch author here. It is important to not conflate POSIX requirements with expected behavior, especially for device files which require very specific knowledge of their implementation to use (DRM ioctl's and resources anyone?). You might think that as a well-behaved game should not be opening/closing evdev fds during gameplay at all, this is clearly just an application bug. However, games are not the main user of evd…

> As for putting things in threads, I would consider it a huge hack to move open/close. Threads are not and will never be mandatory to have great responsiveness.

The POSIX interface was invented for batch processing. Long running non-interactive jobs. This is why it lacks timing requirements. All well-designed interactive GUI applications do not interact with the file system on their main thread. This is especially true for game display loops. The fundamental problem here is that they are doing unbounded work on a thread that has specific timing requirements (usually 16.6ms per loop). As I’ve said elsewhere, this bug will still manifest itself no matter how fast you make close(), just depends on how many device files are present on that particular system. It’s a poor design. Well designed games account for every line of code run in their drawing loop.

> This is absolutely a kernel bug.

I don’t think that is proven unless the original author can chime in. It’s your best guess and opinion that the author intended to not block on synchronize_rcu but it’s perfectly possible they did indeed intend the code as written. synchronize_rcu is used in plenty of other critical system call paths in similar ways, not every one of those uses is a bug. I would guess you might be slightly suffering from tunnel vision a bit here given how the behavior was discovered.

If it is indeed the case the synchronize_rcu is taking up to 50ms I would suspect there is a deeper issue at play on this machine. By search/replacing the call with call_rcu or similar you may just be masking the problem. RCU updates should not be taking that long.

Re: Fixing stutters in Papers Please on Linux

#177

Post by CyberRabbi »

arghwhat wrote: post #173
CyberRabbi wrote: post #84

Earlier quoted context omitted.

> It should block if and only if there is actual io in flight which could produce a failure return that an application needs. Blocking simply means that the specification does not guarantee an upper bound on the completion time. There is no other meaningful definition. POSIX is not an RTOS therefore nearly all system calls block. The alternative is that the specification guarantees an upper bound on completion time.…

The machine is not running POSIX, it's running Linux which is POSIX-ey, and an RTOS does not guarantee that system calls do not block. The insistence on only referring to POSIX was what caused the O_PONIES debate in the first place. If one assumes that "there is no upper bound on the completion time", then that also means assuming that a poll/read/write will never return within the lifetime of the machine as it could…

> poll/read/write

The “non-blocking” nature of those calls were invented for network servers, not for video games. Not only is jitter tolerable there but high latency is allowed from the lowest layers of the stack. It’s not uncommon to simply get no response from a network request.

A video game should never ever do arbitrary system calls on its main drawing thread unless those system calls are specifically intended for that use case. Jitter is not tolerable in this use case since the timing requirements are so strict. The code must product a frame every 16.6ms, no exceptions. The interface must never become unresponsive.

> RTOS does not guarantee that system calls do not block

RTOSes do indeed provide upper bounds for all calls.

> And, again, when interacting with device files you must refer to the kernel documentation rather than POSIX

Yes that would be a relevant point if it were the case that the kernel documentation for these devices specified that close() should complete within some time bound.

Re: Fixing stutters in Papers Please on Linux

#178

Post by infogulch »

kennylevinsen wrote: post #171
infogulch wrote: post #130

Earlier quoted context omitted.

I did not know this, and for some reason it really annoys me. Why are our process contexts littered with useless little synchronous properties? How many other tedious and slow bookkeeping tasks does the OS have to do just to meet some outdated spec that was probably just an ossified implementation detail in the first place? I feel compelled to make it so that new fds are explicitly randomized just so you can't do thi…

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value. Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles. Go would also…

The correct term for this is not "developers ignoring documentation" it's "ossification" or Hyrum's Law:

    With a sufficient number of users of an API,
    it does not matter what you promise in the contract:
    all observable behaviors of your system
    will be depended on by somebody.
I guess that we got this "lowest available" rule because that's what the first implementation happened to do (it's the obvious thing to do if you have a single core), then someone 'clever' noticed that they could save 3 cycles by hard coding and reusing the fd in their IO-bound loop, and anyone that tried to implement fd allocation differently was instantly met by "your OS breaks my app", and thus the first implementation was permanently ossified in stone. To be clear I'm not making any historical claims and this is pure speculation.

"Stupid developers should have rtfm humph" is not a useful position because it ignores this behavior ossification.

The Go map example is actually very relevant, it's an "anti-ossification" feature that makes the behavior match the spec. If the spec says iteration order is not guaranteed, but in practice people can rely on it being the same in some specific situation (say, in a unit test on a particular version of Go) then the spec is ignored and it breaks people's programs when the situation changes (e.g. Go version updates). This actually happened. Instead of giving in and ossifying the first implementation's details into the spec, Go chose the only other approach: Make the behavior match the spec: "iteration order is not guaranteed" == "iteration order is explicitly randomized". (They do it pretty efficiently actually.)

Re: Fixing stutters in Papers Please on Linux

#179

Post by touisteur »

infogulch wrote: post #178
kennylevinsen wrote: post #171

Earlier quoted context omitted.

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value. Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles. Go would also…

The correct term for this is not "developers ignoring documentation" it's "ossification" or Hyrum's Law: With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody. I guess that we got this "lowest available" rule because that's what the first implementation happened to do (it's the obvious thing to do if yo…

There you can queue the 'workflow' xkcd https://xkcd.com/1172 and while the joke is funny I wish everyone would stop breaking my workflow.

Maybe I'm getting old, or maybe I find the permanent useless change tiring. I'm looking at GNOME, Android, Windows in particular.

Re: Fixing stutters in Papers Please on Linux

#180

Post by kennylevinsen »

loeg wrote: post #175
kennylevinsen wrote: post #171

Earlier quoted context omitted.

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value. Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles. Go would also…

If we ignore POSIX for a moment, the kernel could avoid contending on the one-per-process fd map by sharding the integers into distinct allocation ranges per thread. This would eliminate a source of contention between threads. In addition to violating POSIX’ lowest hole rule, it would break select(2) (more than it’s already broken).

This sounds like premature optimization. FD availability is tracked in a bitmask, and finding the next available slot is a matter of scanning for the first unset bit under a spinlock. This is going to be extremely fast.

While you could shard the file descriptor tables for CLONE_FILES processes such as threads, you would likely complicate file descriptor table management and harm the much more important read performance (which is currently just a plain array index and pretty hard to beat).

You could also juts create your processes (or threads) without CLONE_FILES so that they get their own file descriptor table. ------

The fdtable can be seen here: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin..., and alloc_fd and __fget can be found here: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin....

Post reply on HN