Implement mechanism to wait on any of several futexes
lkml.org
lkml.org
This legit isnt really like anything in Windows, the closest thing I can think of is you'd be able to do something like this with XOK wake predicates.
Its also telling Linux has gone through the whole select/poll/epoll madness while WaitForMultipleObjects has worked well in windows NT since the 90s. Its a proven design.
And this better too, you don't need to register futexes with the kernel, the futex wait call is just "I want to sleep until the data at this memory address changes", and now you can say "I want to sleep until _these addresses_ change". NT doesn't give you any equivalent, you need to build in kernel objects to do the same thing.
And if you want to wait for both, you just wrap it into an eventfd and epoll on that.
(P.S. there is a really ugly way to get around this on Windows if for some bizarre reason you really need to, which is to have 1 thread per 64 handles, then wait on the thread handle instead. I've never found a need do even get close to doing such a thing though.)
Which brings me back to my main point against the GPs
> They should just bite the bullet and implement WaitForMultipleObjects instead of having all these disjoint APIs
Is this your way of saying "I can't think of any legitimate response, but I insist the Windows API must suck because that's just how I feel about it"?
I literally told you there is a proper solution that turns out to be different than what you're expecting coming from Linux, and instead of either realizing it's a good solution or telling me why it isn't, you just trashed the OS and told me it sucks.
And staying on the topic of mutexes, that "just spawn another thread for every 64 items you want to wait on" (which I already knew about) is about the hackiest shit ever.
(And FWIW, I started off as a Win32 developer, have code in ReactOS, and have written NT and WinCE drivers. You're not talking to some Linux fanboy)
Is this surprising to you? I already told you it would be a hack because I told you there is a better and proper solution for the actual problem you were encountering. You're stubbornly insisting for no reason on actively doing something bizarre, and you're frustrated you need an obtuse hack to make it happen?
If you're trying so hard to "stay on the topic of mutexes" why do you trash WFMO for the "silly 64 item cap" and then repeatedly refuse to provide a single situation in which waiting on 64 mutexes would actually come up as a legitimate problem? Somehow you find the inability to use a wrong method to solve a problem whose existence you can't even show evidence of to be "silly"?
I admire what Linux accomplishes functionally. But it is just as ugly as win32 in my opinion. The two are really more alike in their pragmatism than they would care to admit - but mutual hatred prevents learning from each others mistakes.
What are you talking about by "wait for both"?
But jesus, the windows API in this area is hot garbage. A hard 64 limit and O(N)? It's a terrible design.
fds are equivalent to Windows HANDLEs, and WaitForMultipleObjects() is equivalent to poll().
But, Linux also has epoll() which scales better for non-trivial numbers of things, and Windows has IOCP. So WaitForMultipleObjects isn't particularly special.
Both Windows and Linux have things that don't work with these interfaces. Nonetheless, Linux has been trending towards "waiting on all sorts of things" by makng more and more things into fds that can be waited on with pol;/epoll. Examples: timerfd, signalfd, eventfd. It's quite a unixy approach.
In fact, Wine already uses eventfd to implement WaitForMultipleObjects. This kernel change is just an optimisation, to speed up Wine, and a workaround for some distros setting Wine's max fd limit too low for Windows apps.
Futexes used to support waiting on multiple futexes, using FUTEX_FD. That was arguably better than the new patch FUTEX_WAIT_MULTIPLE, because in old Linux you could wait for futexes and other fds at the same time - it did work with "all sorts of things".
But FUTEX_FD was removed after searches online found no code using it, and kernel devs didn't like keeping it. (To my mind, this was a suprising, unusual breakage of system call binary compatibility) The new FUTEX_WAIT_MULTIPLE allows programs like Wine to wait for multiple futexes faster than before, but it's more limited than the old FUTEX_FD because you can't mix them with other things.
The VMS and NT philosophies of everything being an object are a bit more general and easier to follow in practice.
Futex is a special case because futexes themselves are quite special. There is no userspace equivalent to them in Windows anyway as has been mentioned. Windows Events are similar to what is provided by eventfd, but not as featureful.
It's also not something that works on all Unices (e.g. afaik macos has no timerfd). But in all fairness, that problem only exists because OS speciation, as it's biological counterpart, is not as clear cut a concept as one would desire.
In fact windows actually reserves a block of user address space that will never be allocated to disambiguate memory vs non memory handles.
Its really a pitty these two great systems refuse to learn from each other.
I'm calling your bluff too. Which one of the supported waitable handles in Windows are just addresses with no other state? I'm more surprised because they all need an access mask at a minimum, and I thought they all involve an ObCreateObject, even a Mutant... these dusty corners of the kernel are visible through the DDK. Anyway, I would be glad to be shown wrong.
It would be possible to provide an orthogonal handle based API even if windows doesn’t always live up to that ideal.
Ultimately it seems these systems are just too big to maintain a cohesive design - but it is still an ideal to aspire to.
EDIT: And since you dirty edited, can you point to an example of HMODULE or any other dataless HANDLE being used on the syscall interface?
You will find that windows never makes guarantees of what handles actually are - in case it wants to change them.
In windows NT most GDI handles are user mode and not kernel objects. Other objects may or may not be kernel based depending on the version and whims of the implementor.
And can you WFMO on user space only HANDLEs?
Can you use HMODULEs orthogonally to common APIs that use Handles? That's what really matters. Just because something is 4 or 8 bytes wide and you call it the same thing isn't interesting. Like can you pass HMODULE to WaitForSingleObject? Oh Ok, I guess that's mean because to be fair, what does "waiting" on a DLL mean.
Ok, well surely you can pass that HMODULE to CloseHandle, at least closing should be orthogonal.. Why don't you try that? I'll wait.
So what point are you trying to make here? It sound like you're just jerking everyone around, tbh.
Edit: Moreover, it's a bit ridiculous to say that an HMODULE is just an address with no kernel state. It uniquely identifies the loaded DLL, so it a key to a tremendous amount of kernel bookkeeping about the loaded module.
"File descriptor" is just a weird spelling of "handle", for historical reasons.
FDs are pretty much HANDLEs of the nix world.
We are going to soon: "The 5.3 kernel also adds the ability to pass a pidfd to poll(), which will provide a notification when the process represented by that pidfd exits." (https://lwn.net/SubscriberLink/794707/905eb6b5b7287e77/)
[1] https://stackoverflow.com/questions/8057892/epoll-on-regular...
* limited to 64 handles.
* passes the entire handle buffer to the kernel on every call. That is also a key reason poll is worse than epoll/kqueue. A better way is to let the kernel retain the list of handles across calls.
* when two handles are signalled, the one earlier in the array is always the one returned. So handle with a lower array index being frequently signalled can starve out your opportunity to process the later ones.
* since everything happens by returning an index, when multiple handles are signalled, you can only process one at a time, needing a new syscall for each.
I am not sure if this is just my experience but when using libinput on Fedora for example - the cursor movement is not exactly precise. This is not obvious when working but while gaming this is a deal breaker.
To use a metaphor, it's like someone made a replacement edge for a puzzle, which interlocks with a subset of existing pieces for another puzzle rather than someone making a table-sandbox within which to use the the entire initial puzzle.
Touchpad flat profile was flat up to a certain velocity, but when you exceeded that it accelerated a lot.
Flat profile on a physical mouse worked correctly. Even if I yanked the device, it wouldn't accelerate.
This is one of the reasons why I'm sticking to Ubuntu 16.04: "xset m 1 0" disables all acceleration on xinput.
It is a security issue and an X-Window design issue.
The only reason I switched back to a Windows Desktop was that there were just one or two games I specifically wanted to try, but couldn't install to Linux. And once I had switched back (and paid the price for Windows) there were no games that needed Linux, so no motivation to go back.
Alright, it's a headless VM, but it's pared down with 'unfuck' and other telemetry- and uselessness- neutering projects into something safer. Lookingglass peers into one of my GPU's framebuffers, so it lives inside a window on my Linux host.
It's also been at least a year since I've needed it, though, since Steam and wine cover everything else I'd want to play or run, so it might be time to cut it loose for good.
That will never happen. You game in Linux because you need Linux first and games second.
Isn’t a mutex timing out an indication that:
a) a lock wasn’t needed in the first place or
b) the program is incorrect?
It feels more like they just want the api to match win32 better but most of the multithreaded programming I’ve done lately has just used go’s channels so I totally could be missing something.
Ever seen a texture pop in instead of a stutter? If a lock would be taken on that load without timeout (very short) it'd either not load on time or load when it's no longer needed.
Maybe a lazy GUI framework could use a mutex timout, though.
It could also be (c) -- it's correct but there's contention or: the mutex is too coarse / there's "too much" work being protected by the mutex.
But I think your point about matching windows is likely the case (this is how wine implements WaitForMultipleObjects maybe?). The fd exhaustion with FUTEX_FD means they need another way.
Essentially you're putting a lower bound on Availability in favor of Consistency. Lease expiry happens when the lessor isn't around to retire the lease in an orderly fashion. It's detecting a Partition. In theory a network partition, but we all know how CPU boundedness creeps into the system as the feature set or the data set grows... and that can show up even on a solitary machine.
- program with fine grained locks
- you have an algorithm that needs to acquire N of those locks, one at a time, and can do it in any order
In that case, you really want to:
- first attempt fast path locking on all of them in any order
- if that fails tell the kernel about all of the locks you are waiting on at once.
This means that you will become unblocked as soon as any lock becomes available.
That will make your program run faster. Therefore, it’s a good improvement for futexes in my opinion.
Use of WaitForMultipleObjects is more usually for completion of tasks, in the way that win32 "overlapped" works.
Remember, the algorithm in my example is one where you hold locks one at a time. You can acquire locks in any order if you hold them one at a time.
Also my example is intentionally not about wine or win32. I’m articulating why this interface is independently valuable.
1. Each CPU first attempts to take an allocated object from its own pool, using a 1ms timeout to acquire the mutex on the pool.
2. If that fails, the CPU attempts to steal from the other CPU pools, using a zero timeout (immediately return if the mutex can't be taken).
3. If that fails, acquire the mutex on its own pool with an infinite timeout.
This is definitely correct and is much faster than any of the lock-free approaches I could come up with. I guess the general class of problems where mutex timeouts help is when you have "many valid options, some of which are being used by others."
> We think that if this feature (or an equivalent) was adopted upstream, we would achieve efficiency gains by adopting it in native massively-threaded applications such as Steam and the Source 2 engine.
Depending on what they mean by "massively-threaded", that might cover some other popular network applications that thread to handle requests, but I'm not sure how much work they would put into a linux specific solution if it complicated their codebase.
Indeed. See Dota 2.
Wine stands for "Wine Is Not an Emulator".
Citation with detailed history: https://news.ycombinator.com/item?id=13476390
Say you have one worker thread per CPU core. On Windows, each thread would get an Event object and you would WaitOnMultiple to be able to act on the first unit of work that was complete. On Linux you would have to roll your own solution using lower-level primitives and it will not be correct. Being able to wait on multiple events on Linux will be awesome.
In Linux each thread can get an eventfd and you can POLLIN all of them.
In fact I would argue that using futexes is the “roll your own solution” using lower level primitives (and easier to fuckup) much more so than eventfd and epoll.
As mentioned somewhat poorly in the post, using futexes gives a performance boost which is not surprising since they are fast user mutexes. FWIW I didnt think windows events had a fast user space path but I may be mistaken.
For most worker pool scenarios you’re describing, the overhead of eventfd is probably in the noise.
Again.. eventfd and epoll covers the same use case as WFMO and EVENTs.
Though it can emulate a win32 api for waiting on multiple “objects”, it’s strictly more powerful than WaitForMultiple if you are dealing with user objects since futexes impose very few constraints on how your user synchronization object is shaped and how it works.
So, the new interface is totally different from things like epoll. In one case the kernel is helping you wait for multiple user objects and in the other case it’s helping you wait for multiple kernel objects. The distinction is intentional because the whole point is that the user object that has the futex can be shaped however user likes, and can implement whatever synchro protocol the use likes.
Finally, it’s worth remembering that futex interfaces are all about letting you avoid going into kernel unless there is actually something to wait for. The best part of the api is that it helps you to avoid calling it. So for typical operations, if the resource being waited on can have its wait state represented as a 32-bit int in user memory, the futex based apis will be a lot faster.
1. You'll likely get it wrong and have subtle bugs.
2. This is significantly different than the Windows model where you wait on events. Now you have two classes of events - regular ones, and ones that can be waited on in multiple. The second class also comes with its own event manager class that needs to manage the eventfd for this group of events.
You end up with a specialised class of event that needs to be used whenever you need to wait in several of them at once. Then you realise you used a normal POSIX event somewhere else and now you want to wait on that as well, so you have to rewrite parts of your program to use your special multi-waitable event.
It's mostly trivial to write a event wrapper on top of POSIX events that behaves the same as Windows Events, except for the part where you might want to wait on multiple of them. I would expect that once this kernel interface is implemented we'll get GNU extensions in glibc allowing for waiting on multiple POSIX events. I absolutely do not want to roll my own thread synchronisation primitives except for very thin wrappers over the platform-specific primitives. Rolling your own synchronisation primitives is about as fraught with peril as rolling your own crypto.
To be honest, WaitForMultipleObjects will probably become not very useful in the near future. We're getting 32-core workstation CPUs today, it's quite likely there will be CPUs with more than 64 cores in near future workstations making it impossible to use this classic Windows primitive, but I suspect Microsoft will provide WaitForMultipleObjectsEx2.
WebKit has its own implementation (see the ParkingLot in https://webkit.org/blog/6161/locking-in-webkit/) which inspired an implementation in folly (https://github.com/facebook/folly/blob/master/folly/synchron...).
Surprisingly, implementing futexes in userland can have performance benefits wrt kernel futexes (because of better control over the fast path, possibly avoiding syscalls) and a richer interface (for example the value doesn't need to be 32 bit, just any atomic).
Thanks for pointing out the obvious for those of us who missed it!
In any case, you're not alone.
11 is higher than 2.
/grumpy
edit: nope, it's fine as is. my experience in frame numbers, dates, and so forth do not scale to releases
Note that the futex address itself is also a pointer, but it's validated with access_ok in get_futex_key.
https://elixir.bootlin.com/linux/latest/source/kernel/futex....
I'm an idiot
This may be someone’s first submission and they may consequently not be aware of style guides, tools which can help lint, etc?
Also, given the amount of patches I have to read, uniform style really does matter. Unconventional style breaks the flow and detracts from the important bits.
Also, I'm not aware of a lint like tool that works on diffs. Many of the patches never get further than my MUA.
Personally I prefer to be less strict about style whenever possible, but then I prefer to work in safer languages, and I don't have the same firehose to deal with.
I didn't see any discussion about tradeoffs, alternative approaches, or a survey of what other systems do for this kind of functionality, or detailed benchmark results.
The tone was roughly what I'd want people to give me in a code review -- the only problem is that it was trivial, and could have been summarized as "Fix the style, check it with $tool"
That review also had a comment about an implicit limit on the number of objects, which is caused by a limit on the amount of physically contiguous memory the kernel memory allocator can obtain at once, and a comment that the code being reviewed would allow for a large increase of the reference count of a couple of important structures. Both appear to be very technical comments to me.
[0] https://www.kernel.org/doc/html/v4.17/process/submitting-pat...
It is hard enough to get people to review code as it is. I think everyone would be better off with a little humility and be thankful that other people review their code, even in the cases where the review itself isn't very helpful.
To me, it serves as a type of virtue signalling. It's kind of interesting to view the issue from a social perspective:
1. It gives a feedback to the committer, shows that your patch has caught the attention of a kernel maintainer, not lost or ignored (Example: last time, I sent a bunch of patches to a subsystem, no reply at all, it turned out that the maintainer was on a vacation. On the other hand, if I received a review on non-conforming code style, I know the maintainer is at least available, and I'm not rejected because I did something seriously wrong).
2. It gives kernel maintainers a chance to immediately expresses objections to your patch, thus affirming the social status and authority of a kernel maintainer (Example: After submitting a few patches, you'll quickly know who's in charge and who has a saying on the development).
3. By doing (2), it also creates a personal connection from the maintainer to the committer, the committer now knows all the sequentially modifications can be CC-ed to maintainer J. Random Hacker for review (although scripts/get_maintainer.pl should always be used, but at least you know who's the most active one).
4. It exerts peer pressure to the submitter to follow the cultural norms, "the system" of the kernel development process, including obeying the Linux kernel coding standard.
5. It creates a system of bureaucracy that could accelerate and mechanize the workflow of a patch-reviewing maintainer (Other examples include pull requests written in a formal, respectful language, often semi-automatically generated, can be compared to the bureaucracy paperwork, e.g. https://lore.kernel.org/lkml/20190731062622.GA4414@archbox/).
6. A lot of the older kernel code has many strange nonstandard coding styles and technical tricks from the early days, which is now discouraged. A strict coding style review prevents any nonstandard practice continues to enter the kernel as new code.
The act of expressing role and power through virtue signalling exists in all organizations. If "the system" itself serves its intended useful proposes without objectionable, serious harms [0], there is no reason to abolish it.
The only problem seems to be frustration over lengthy E-mail exchanges without progress. However, the workflow of Kernel is large, loose, highly asynchronous across different timezones, with a lot of reviewers, some are not even dedicated to the kernel project. Organizing itself already implies a relatively slow pace, so it's not seen as a major problem.
I believe most traditional FOSS project works more or less in the same way. In fact, I think Linux Kernel is actually a lot more open that other similar low-level projects, at least for the "non-core" (not linux-mm) parts, like device drivers.
Finally, I think there are valid criticisms to the traditional model of a FOSS project driven by mails, and many people have attempted to innovate towards a more accessible system of development. GitHub's "Pull Request" proved to lower the barrier-of-entry and boost productivity considerably for small-to-medium projects. And I welcome other innovations if you are starting a new project. On the other hand, the Linux Kernel is now a canonical representation of the "old system" which is very unlikely to change in the next 20 years. My recommendation is: Don't waste your energy to attack the old systems, instead, learn from all major projects and study their workflow and governance, and see if you can invent something new, we need a lot of innovation).
[0] Verbal abuses are criticized as a problem of this system, but by itself, it's not a part of the workflow, using what words is more closer that a matter of personal choice (so yes, one could say harsh criticisms is a greater problem in hacker culture, not only a workflow problem, it can be seen on mailing list, on online forums, IRC, or even offline). Also, Linus Torvalds recently changed his behavior under external pressure.
If the developer of the patch couldn't get the easy minor details right before submitting, I wouldn't have much confidence that they spent a lot of effort thinking about the hard, major details either.
The kernel team came up with rules about how code is formatted. If you don't follow the rules, they are under no obligation to allow your code to be merged in to the main repo, and in fact, are within their rights to reject it. I take the initial response more as a "I'm going to let you off with a warning" versus "Here's your ticket, see you in court"