Documentation/pwqr.adoc

   1 Pthread WorkQueue Regulator
   2 ===========================
   3
   4 The Pthread Workqueue Regulator is meant to help userland regulate thread
   5 pools based on the actual amount of threads that are running, the capacity of
   6 the machines, the amount of blocked threads ...
   7
   8 kernel-land design
   9 ------------------
  10
  11 In the kernel, threads registered in the pwq regulator can be in 4 states:
  12
  13 blocked::
  14         This is the state of threads that are curently blocked in a syscall.
  15
  16 running::
  17         This is the state of threads that are either really running, or have
  18         been preempted out by the kernel. In other words it's the number of
  19         schedulable threads.
  20
  21 waiting::
  22         This is the state of threads that are currently in a `PWQR_WAIT` call
  23         from userspace (see `pwqr_ctl`) but that would not overcommit if
  24         released by a `PWQR_WAKE` call.
  25
  26 quarantined::
  27         This is the state of threads that are currently in a `PWQR_WAIT` call
  28         from userspace (see `pwqr_ctl`) but that would overcommit if released
  29         by a `PWQR_WAKE` call.
  30 +
  31 This state avoids waking a thread to force userland to "park" the thread, this
  32 is racy, make the scheduler work for nothing useful.  Though if `PWQR_WAKE` is
  33 called, quarantined threads are woken but with a `EDQUOT` errno set, and only
  34 one by one, no matter how wakes have been asked.
  35 +
  36 This state actually has only one impact: when `PWQR_WAKE` is called for more
  37 than one threads, for example 4, and that userland knows that there is 5
  38 threads in WAIT state, but that actually 3 of them are in the quarantine, only
  39 2 will be woken up, and the `PWQR_WAKE` call will return 2. Any subsequent
  40 `PWQR_WAKE` call will wake up one quarantined thread to let it be parked, but
  41 returning 0 each time to hide that from userland.
  42
  43 parked::
  44         This is the state of threads currently in a `PWQR_PARK` call from
  45         userspace (see `pwqr_ctl`).
  46
  47
  48 The regulator tries to maintain the following invariant:
  49
  50         running + waiting == target_concurrency
  51     ||  (running + waiting < target_concurrency && waiting > 0)
  52
  53 When `running + waiting` overcommits::
  54         The kernel puts waiting threads into the quarantine, which doesn't
  55         require anything from userland. It's something userland discovers only
  56         when it needs a waiting thread, which may never happen.
  57 +
  58 If there are no waiting threads, then well, the workqueue overcommits, and
  59 that's one of the TODO items at the moment (see Notes)
  60
  61 When `running + waiting` undercommits::
  62         If waiting is non-zero then well, we don't care, it's that userland
  63         actually doesn't need work to be performed.
  64 +
  65 If waiting is zero, then a parked thread (if such a thread) is woken up so
  66 that userland has a chance to consume jobs.
  67 +
  68 Unparking threads only when waiting becomes zero avoid flip-flops when the job
  69 flow is small, and that some of the running threads sometimes blocks (IOW
  70 running sometimes decreases, making `running + waiting` be below target
  71 concurrency for very small amount of time).
  72 +
  73 NOTE: unparking only happens after a delay (0.1s in the current
  74 implementation) during which `waiting` must have been remained zero and the
  75 overal load to be under commiting resources for the whole period.
  76
  77 The regulation between running and waiting threads is left to userspace that
  78 is a way better judge than kernel land that has absolutely no knowledge about
  79 the current workload. Also, doing so means that when there are lots of jobs to
  80 process and that the pool has a size that doesn't require more regulation,
  81 kernel isn't called for mediation/regulation AT ALL.
  82
  83
  84 Todos
  85 ~~~~~
  86 When we're overcommiting for a "long" time, userspace should be notified in
  87 some way it should try to reduce its amount of running threads. Note that the
  88 Apple implementation (before Lion at least) has the same issue. Though if you
  89 imagine someone that spawns a zillion jobs that call very slow `msync()s` or
  90 blocking `read()s` over the network, then that all those go back to running
  91 state, the overcommit is huge.
  92
  93 There are several ways to "fix" this:
  94
  95 in kernel (poll solution)::
  96         Let the file descriptor be pollable, and let it be readable (returning
  97         something like the amount of overcommit at read() time for example) so
  98         that userland is notified that it should try to reduce the amount of
  99         runnable threads.
 100 +
 101 It sounds very easy, but it has one major drawback: it meaks the pwqfd must be
 102 somehow registered into the eventloop, and it's not very suitable for a
 103 pthread_workqueue implementation.
 104
 105 in kernel (hack-ish solution)::
 106         The kernel could voluntarily unpark/unblock a thread with another
 107         errno that would signal overcommiting. Unlike the pollable proposal,
 108         this doesn't require hooking in the event loop. Though it requires
 109         having one such thread, which may not be the case when userland has
 110         reached the peak number of threads it would ever want to use.
 111 +
 112 Is this really a problem? I'm not sure. Especially since when that happens
 113 userland could pick a victim thread that would call `PWQR_PARK` after each
 114 processed job, which would allow some kind of poor man's poll.
 115 +
 116 The drawback I see in that solution is that we wake up YET ANOTHER thread at a
 117 moment when we're already overcommiting, which sounds counter productive.
 118 That's why I didn't implement that.
 119
 120 in userspace::
 121         Userspace knows how many "running" threads there are, it's easy to
 122         track the amount of registered threads, and parked/waiting threads are
 123         already accounted for. When "waiting" is zero, if "registerd - parked"
 124         is "High" userspace could choose to randomly try to park one thread.
 125 +
 126 I think `PWQR_PARK` could use `val` to have some "probing" mode, that would
 127 return `0` if it wouldn't block and `-1/EWOULDBLOCK` if it would in the non
 128 probing mode. Userspace could maintain some global probing_mode flag, that
 129 would be a tristate: NONE, SLOW, AGGRESSVE.
 130 +
 131 It's in NONE when userspace belives it's not necessary to probe (e.g. when the
 132 amount of running + waiting threads isn't that large, say less than 110% of
 133 the concurrency or any kind of similar rule).
 134 +
 135 It's in SLOW mode else. In slow mode each thread does a probe every 32 or 64
 136 jobs to mitigate the cost of the syscall. If the probe returns EWOULDBLOCK
 137 then the thread goes to PARK mode, and the probing_mode goes to AGGRESSVE.
 138 +
 139 When AGGRESSVE threads check if they must park more often and in a more
 140 controlled fashion (every 32 or 64 jobs isn't nice because jobs can be very
 141 long), for example based on some poor man's timer (clock_gettime(MONOTONIC)
 142 sounds fine). As soon as a probe returns 0 or we're in the NONE conditions,
 143 then the probing_mode goes back to NONE/SLOW.
 144 +
 145 The issue I have with this is that it sounds to add quite some code in the
 146 fastpath code, hence I dislike it a lot.
 147
 148 my dream::
 149         To be able to define a new signal we could asynchronously send to the
 150         process. The signal handler would just put some global flag to '1',
 151         the threads in turn would check for this flag in their job consuming
 152         loop, and the first thread that sees it to '1', xchg()s 0 for it, and
 153         goes to PARK mode if it got the '1'. It's fast, inexpensive.
 154 +
 155 Sadly AFAICT defining new signals() isn't such a good idea. Another
 156 possibility is to give an address for the flag at pwqr_create() time and let
 157 the kernel directly write into userland. The problem is, I feel like it's a
 158 very wrong interface somehow. I should ask some kernel hacker to know if that
 159 would be really frowned upon. If not, then that's the leanest solution of all.
 160
 161 pwqr_create
 162 -----------
 163 SYNOPSIS
 164 ~~~~~~~~
 165
 166         int pwqr_create(int flags);
 167
 168 DESCRIPTION
 169 ~~~~~~~~~~~
 170 This call returns a new PWQR file-descriptor. The regulator is initialized
 171 with a concurrency corresponding to the number of online CPUs at the time of
 172 the call, as would be returned by `sysconf(_SC_NPROCESSORS_ONLN)`.
 173
 174 `flags`::
 175         a mask of flags, currently only O_CLOEXEC.
 176
 177 RETURN VALUE
 178 ~~~~~~~~~~~~
 179 On success, this call return a nonnegative file descriptor.
 180 On error, -1 is returned, and errno is set to indicate the error.
 181
 182 ERRORS
 183 ~~~~~~
 184 [EINVAL]::
 185         Invalid value specified in flags
 186 [ENFILE]::
 187         The system limit on the total number of open files has been reached.
 188 [ENOMEM]::
 189         There was insufficient memory to create the kernel object.
 190
 191
 192 pwqr_ctl
 193 --------
 194 SYNOPSIS
 195 ~~~~~~~~
 196
 197         int pwqr_ctl(int pwqrfd, int op, int val, void *addr);
 198
 199
 200 DESCRIPTION
 201 ~~~~~~~~~~~
 202
 203 This system call performs control operations on the pwqr instance referred to
 204 by the file descriptor `pwqrfd`.
 205
 206 Valid values for the `op` argument are:
 207
 208 `PWQR_GET_CONC`::
 209         Requests the current concurrency level for this regulator.
 210
 211 `PWQR_SET_CONC`::
 212         Modifies the current concurrency level for this regulator. The new
 213         value is passed as the `val` argument. The requests returns the old
 214         concurrency level on success.
 215 +
 216 A zero or negative value for `val` means 'automatic' and is recomputed as the
 217 current number of online CPUs as `sysconf(_SC_NPROCESSORS_ONLN)` would return.
 218
 219 `PWQR_REGISTER`::
 220         Registers the calling thread to be taken into account by the pool
 221         regulator. If the thread is already registered into another regulator,
 222         then it's automatically unregistered from it.
 223
 224 `PWQR_UNREGISTER`::
 225         Deregisters the calling thread from the pool regulator.
 226
 227 `PWQR_WAKE`::
 228         Tries to wake `val` threads from the pool. This is done according to
 229         the current concurrency level not to overcommit. On success, a hint of
 230         the number of woken threads is returned, it can be 0.
 231 +
 232 This is only a hint of the number of threads woken up for two reasons. First,
 233 the kernel could really have woken up a thread, but when it becomes scheduled,
 234 it could *then* decide that it would overcommit (because some other thread
 235 unblocked inbetween for example), and block it again.
 236 +
 237 But it can also lie in the other direction: userland is supposed to account
 238 for waiting threads. So when we're overcommiting and userland want a waiting
 239 thread to be unblocked, we actually say we woke none, but still unblock one
 240 (the famous quarantined threads we talk about above). This allow the userland
 241 counter of waiting threads to decrease, but we know the thread won't be usable
 242 so we return 0.
 243
 244 `PWQR_WAKE_OC`::
 245         Tries to wake `val` threads from the pool. This is done bypassing the
 246         current concurrency level (`OC` stands for `OVERCOMMIT`). On success,
 247         the number of woken threads is returned, it can be 0, but it's the
 248         real count that has been (or will soon be) woken up. If it's less than
 249         required, it's because there aren't enough parked threads.
 250
 251 `PWQR_WAIT`::
 252         Puts the thread to wait for a future `PWQR_WAKE` command. If this
 253         thread must be parked to maintain concurrency below the target, then
 254         the call blocks with no further ado.
 255 +
 256 If the concurrency level is below the target, then the kernel checks if the
 257 address `addr` still contains the value `val` (in the fashion of `futex(2)`).
 258 If it doesn't then the call doesn't block. Else the calling thread is blocked
 259 until a `PWQR_WAKE` command is received.
 260 +
 261 `addr` must of course be a pointer to an aligned integer which stores the
 262 reference ticket in userland.
 263
 264 `PWQR_PARK`::
 265         Puts the thread in park mode. Those are spare threads to avoid
 266         cloning/exiting threads when the pool is regulated. Those threads are
 267         released by the regulator only, and can only be woken from userland
 268         with the `PWQR_WAKE_OC` command, and once all waiting threads have
 269         been woken.
 270 +
 271 The call blocks until an overcommiting wake requires the thread, or the kernel
 272 regulator needs to grow the pool with new running threads.
 273
 274 RETURN VALUE
 275 ~~~~~~~~~~~~
 276 When successful `pwqr_ctl` returns a nonnegative value.
 277 On error, -1 is returned, and errno is set to indicate the error.
 278
 279 ERRORS
 280 ~~~~~~
 281 [EBADF]::
 282         `pwqfd` is not a valid file descriptor.
 283
 284 [EBADFD]::
 285         `pwqfd` is a valid pwqr file descriptor but is in a broken state: it
 286         has been closed while other threads were in a pwqr_ctl call.
 287 +
 288 NOTE: this is due to the current implementation and would probably not be here
 289 with a real syscall.
 290
 291 [EFAULT]::
 292          Error in reading value from `addr` from userspace.
 293
 294 [EINVAL]::
 295         TODO
 296
 297 Errors specific to `PWQR_REGISTER`:
 298
 299 [ENOMEM]::
 300         There was insufficient memory to perform the operation.
 301
 302 Errors specific to `PWQR_WAIT`:
 303
 304 [EWOULDBLOCK]::
 305         When the kernel evaluated if `addr` still contained `val` it didn't.
 306         This works like `futex(2)`.
 307
 308 Errors specific to `PWQR_WAIT` and `PWQR_PARK`:
 309
 310 [EINTR]::
 311         The call was interrupted by a syscall (note that sometimes the kernel
 312         masks this fact when it has more important "errors" to report like
 313         `EDQUOT`).
 314 [EDQUOT]::
 315         The thread has been woken by a `PWQR_WAKE` or `PWQR_WAKE_OC` call, but
 316         is overcommiting.
 317