Talk:epoll

O(1) ?

Clearly not O(1) for add and upd (only wait) and even there, without EPOLLET, I think epoll as to search for socket with available data (unless it maintain a queue internally)?

Why do they use RB-tree instead of hashtbl ? O(1) amortized with O(n) worst case feels better than O(ln(n)) ?

Could someone who have time to look at the code comment? 148.66.126.134 (talk) 22:38, 13 January 2023 (UTC)

Introduction to kernel

In https://en.wikipedia.org/w/index.php?title=Epoll&diff=prev&oldid=1191403982 someone changed "first introduced in version 2.5.44 of the Linux kernel" to "first introduced in version 2.5.45 of the Linux kernel", however, when I checked the reference I see that it does say 2.5.44. Does someone have a different reference that shows 2.5.45? Otherwise I will revert this change. Jrdnch (talk) 17:37, 1 April 2025 (UTC)

The plot thickens. The primary source is always the kernel development mailing lists. From what I can tell, epoll as we know it was first introduced here, as a patch based off of 2.5.44 "for inclusion in the next 2.5 kernel release" (hinting that 2.5.45 is the true first possible candidate):

• https://lore.kernel.org/lkml/53100000.1035832459@w-hlinder/ or https://lwn.net/Articles/13918/

There was some discussion and then another patch was supplied with man pages. This patch contains the (erroneous?) line of "a new API introduced in Linux kernel 2.5.44":

• https://lore.kernel.org/lkml/144220000.1035864069@w-hlinder/

Perhaps it's stylistic grammatical choice in that it was "introduced" against .44 and was released in a later version? Or somehow those original manpages never got their text bumped for the release epoll was included in. Anyway, a few days later Linus announces v2.5.45 and mentions epoll in the notes:

• https://lore.kernel.org/lkml/Pine.LNX.4.44.0210301651120.6719-100000@penguin.transmeta.com/

But later on the standard "[STATUS 2.5]" email sent a week later describes it as merged in 2.5.46 (granted this could mean yet another improvement to the first epoll patch):

• https://lore.kernel.org/lkml/3DC9402F.22787.27763DD6@localhost/

As contrast, the "2.5.43 to 2.5.44" changelog email that precedes this all does not mention epoll:

• https://lwn.net/Articles/13197/

So, from what I can reasonably conclude from these mailing list archives, v2.5.45 is the true introduction of sys_epoll (its own version at v0.15). —f3ndot ^{(TALK) (EMAIL)} 05:52, 15 July 2025 (UTC)

Oh, and a source-worthy link for citing the 2.5.45 change would be: https://lwn.net/Articles/13587/ —f3ndot ^{(TALK) (EMAIL)} 06:02, 15 July 2025 (UTC)