evolution of select()
evolution of select()
2015-01-12
Overview
System Calls
select()
Input:
- FD sets for read, write, error.
- Timeout
Output:
- >=0: Active bit on FD set
- -1: set errno global
select in Big O notation*
- FD_SET: O(1)
- FD_ZERO: O(FD_SETSIZE/8)
- select kernel-side: CPU: O(2*FD_SETSIZE)
- select kernel-side: Memory Copy: O(3*FD_SETSIZE/8)
(*) FD_SETSIZE is a constant in a header file, but give me some rope here.
Evolutionary pressure: 1996.
FD_SETSIZE = 1024
squid** was written.
more clients.
multiple FDs per-client. (not just network)
HTTP keepalive.
(**) actually lots of software was written.More than 64 1024 FDs?
Redefine FD_SETSIZE to be bigger!
Introducing poll()
Instead of a fixed size array, let the user allocate it!
Added in Linux 2.1.32, Jan, 1997.
poll()
Input:
- FDs array
- Size of FD array
- Timeout
Output:
- >=1: Updated .revent for each FD.
- -1: set errno global
poll in Big O notation
- Array operations for FD: O(n)
- poll kernel-side: CPU: O(2*n)
- poll kernel-side: Memory Copy: O(n)
(*) Assuming you don't need to realloc as n increases.
(*) Because pollfd is a struct, you can index it in another data structure to get better big O in user-space.
Evolutionary pressure continues
more clients.
global clients.
idle network protocols. (due to TCP handshake)
c10k and HTTP 1.1
- 10,000 clients: any 10ms period, 10 active.
- Userspace poll() needs to do O(10,000) operations
- Kernel needs to copy 10,000 * sizeof(pollfd): 80kb
- Kernel needs to do O(2*10,000) operations.
Evolutionary pressure continues
GUI Event Loops
filesystem watches
non-network objects.
signals
Linux Answer: Everything is an FD.
Introducing epoll()
Added in Linux 2.5.44, Oct, 2002.
epoll()
Multiple functions:
- epoll_create
- epoll_ctl
- epoll_wait
epoll_wait:
- epoll FD
- Output Array
- Timeout
epoll in Big O notation
- epoll_ctl add/remove: O(log N)
- epoll_wait kernel-side: CPU: O(1)
- epoll_wait kernel-side: Memory Copy Out: O(active)
.jpg){kind=link}