]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - sys/kern/subr_epoch.c
epoch(9): Guarantee forward progress on busy sections
[FreeBSD/FreeBSD.git] / sys / kern / subr_epoch.c
1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3  *
4  * Copyright (c) 2018, Matthew Macy <mmacy@freebsd.org>
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25  * SUCH DAMAGE.
26  *
27  */
28
29 #include <sys/cdefs.h>
30 __FBSDID("$FreeBSD$");
31
32 #include <sys/param.h>
33 #include <sys/types.h>
34 #include <sys/systm.h>
35 #include <sys/counter.h>
36 #include <sys/epoch.h>
37 #include <sys/gtaskqueue.h>
38 #include <sys/kernel.h>
39 #include <sys/limits.h>
40 #include <sys/lock.h>
41 #include <sys/malloc.h>
42 #include <sys/mutex.h>
43 #include <sys/proc.h>
44 #include <sys/sched.h>
45 #include <sys/smp.h>
46 #include <sys/sysctl.h>
47 #include <sys/turnstile.h>
48 #include <vm/vm.h>
49 #include <vm/vm_extern.h>
50 #include <vm/vm_kern.h>
51
52 #include <ck_epoch.h>
53
54 static MALLOC_DEFINE(M_EPOCH, "epoch", "epoch based reclamation");
55
56 /* arbitrary --- needs benchmarking */
57 #define MAX_ADAPTIVE_SPIN 1000
58
59 #define EPOCH_EXITING 0x1
60 #ifdef __amd64__
61 #define EPOCH_ALIGN CACHE_LINE_SIZE*2
62 #else
63 #define EPOCH_ALIGN CACHE_LINE_SIZE
64 #endif
65
66 CTASSERT(sizeof(epoch_section_t) == sizeof(ck_epoch_section_t));
67 SYSCTL_NODE(_kern, OID_AUTO, epoch, CTLFLAG_RW, 0, "epoch information");
68 SYSCTL_NODE(_kern_epoch, OID_AUTO, stats, CTLFLAG_RW, 0, "epoch stats");
69
70 static int poll_intvl;
71 SYSCTL_INT(_kern_epoch, OID_AUTO, poll_intvl, CTLFLAG_RWTUN,
72                    &poll_intvl, 0, "# of ticks to wait between garbage collecting deferred frees");
73 /* Stats. */
74 static counter_u64_t block_count;
75 SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, nblocked, CTLFLAG_RW,
76                                    &block_count, "# of times a thread was in an epoch when epoch_wait was called");
77 static counter_u64_t migrate_count;
78 SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, migrations, CTLFLAG_RW,
79                                    &migrate_count, "# of times thread was migrated to another CPU in epoch_wait");
80 static counter_u64_t turnstile_count;
81 SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, ncontended, CTLFLAG_RW,
82                                    &turnstile_count, "# of times a thread was blocked on a lock in an epoch during an epoch_wait");
83 static counter_u64_t switch_count;
84 SYSCTL_COUNTER_U64(_kern_epoch_stats, OID_AUTO, switches, CTLFLAG_RW,
85                                    &switch_count, "# of times a thread voluntarily context switched in epoch_wait");
86
87 typedef struct epoch_cb {
88         void (*ec_callback)(epoch_context_t);
89         STAILQ_ENTRY(epoch_cb) ec_link;
90 } *epoch_cb_t;
91
92 TAILQ_HEAD(threadlist, thread);
93
94 typedef struct epoch_record {
95         ck_epoch_record_t er_record;
96         volatile struct threadlist er_tdlist;
97         volatile uint32_t er_gen;
98         uint32_t er_cpuid;
99 } *epoch_record_t;
100
101 struct epoch_pcpu_state {
102         struct epoch_record eps_record;
103         STAILQ_HEAD(, epoch_cb) eps_cblist;
104 } __aligned(EPOCH_ALIGN);
105
106 struct epoch {
107         struct ck_epoch e_epoch __aligned(EPOCH_ALIGN);
108         struct grouptask e_gtask;
109         struct callout e_timer;
110         struct mtx e_lock;
111         int e_flags;
112         /* make sure that immutable data doesn't overlap with the gtask, callout, and mutex*/
113         struct epoch_pcpu_state *e_pcpu_dom[MAXMEMDOM] __aligned(EPOCH_ALIGN);
114         counter_u64_t e_frees;
115         uint64_t e_free_last;
116         struct epoch_pcpu_state *e_pcpu[0];
117 };
118
119 static __read_mostly int domcount[MAXMEMDOM];
120 static __read_mostly int domoffsets[MAXMEMDOM];
121 static __read_mostly int inited;
122 __read_mostly epoch_t global_epoch;
123
124 static void epoch_call_task(void *context);
125
126 #if defined(__powerpc64__) || defined(__powerpc__) || !defined(NUMA)
127 static bool usedomains = false;
128 #else
129 static bool usedomains = true;
130 #endif
131 static void
132 epoch_init(void *arg __unused)
133 {
134         int domain, count;
135
136         if (poll_intvl == 0)
137                 poll_intvl = hz;
138
139         block_count = counter_u64_alloc(M_WAITOK);
140         migrate_count = counter_u64_alloc(M_WAITOK);
141         turnstile_count = counter_u64_alloc(M_WAITOK);
142         switch_count = counter_u64_alloc(M_WAITOK);
143         if (usedomains == false)
144                 goto done;
145         count = domain = 0;
146         domoffsets[0] = 0;
147         for (domain = 0; domain < vm_ndomains; domain++) {
148                 domcount[domain] = CPU_COUNT(&cpuset_domain[domain]);
149                 if (bootverbose)
150                         printf("domcount[%d] %d\n", domain, domcount[domain]);
151         }
152         for (domain = 1; domain < vm_ndomains; domain++)
153                 domoffsets[domain] = domoffsets[domain-1] + domcount[domain-1];
154
155         for (domain = 0; domain < vm_ndomains; domain++) {
156                 if (domcount[domain] == 0) {
157                         usedomains = false;
158                         break;
159                 }
160         }
161  done:
162         inited = 1;
163         global_epoch = epoch_alloc();
164 }
165 SYSINIT(epoch, SI_SUB_TASKQ + 1, SI_ORDER_FIRST, epoch_init, NULL);
166
167 static void
168 epoch_init_numa(epoch_t epoch)
169 {
170         int domain, cpu_offset;
171         struct epoch_pcpu_state *eps;
172         epoch_record_t er;
173
174         for (domain = 0; domain < vm_ndomains; domain++) {
175                 eps = malloc_domain(sizeof(*eps)*domcount[domain], M_EPOCH,
176                                                         domain, M_ZERO|M_WAITOK);
177                 epoch->e_pcpu_dom[domain] = eps;
178                 cpu_offset = domoffsets[domain];
179                 for (int i = 0; i < domcount[domain]; i++, eps++) {
180                         epoch->e_pcpu[cpu_offset + i] = eps;
181                         er = &eps->eps_record;
182                         STAILQ_INIT(&eps->eps_cblist);
183                         ck_epoch_register(&epoch->e_epoch, &er->er_record, NULL);
184                         TAILQ_INIT((struct threadlist *)(uintptr_t)&er->er_tdlist);
185                         er->er_cpuid = cpu_offset + i;
186                 }
187         }
188 }
189
190 static void
191 epoch_init_legacy(epoch_t epoch)
192 {
193         struct epoch_pcpu_state *eps;
194         epoch_record_t er;
195
196         eps = malloc(sizeof(*eps)*mp_ncpus, M_EPOCH, M_ZERO|M_WAITOK);
197         epoch->e_pcpu_dom[0] = eps;
198         for (int i = 0; i < mp_ncpus; i++, eps++) {
199                 epoch->e_pcpu[i] = eps;
200                 er = &eps->eps_record;
201                 ck_epoch_register(&epoch->e_epoch, &er->er_record, NULL);
202                 TAILQ_INIT((struct threadlist *)(uintptr_t)&er->er_tdlist);
203                 STAILQ_INIT(&eps->eps_cblist);
204                 er->er_cpuid = i;
205         }
206 }
207
208 static void
209 epoch_callout(void *arg)
210 {
211         epoch_t epoch;
212         uint64_t frees;
213
214         epoch = arg;
215         frees = counter_u64_fetch(epoch->e_frees);
216         /* pick some better value */
217         if (frees - epoch->e_free_last > 10) {
218                 GROUPTASK_ENQUEUE(&epoch->e_gtask);
219                 epoch->e_free_last = frees;
220         }
221         if ((epoch->e_flags & EPOCH_EXITING) == 0)
222                 callout_reset(&epoch->e_timer, poll_intvl, epoch_callout, epoch);
223 }
224
225 epoch_t
226 epoch_alloc(void)
227 {
228         epoch_t epoch;
229
230         if (__predict_false(!inited))
231                 panic("%s called too early in boot", __func__);
232         epoch = malloc(sizeof(struct epoch) + mp_ncpus*sizeof(void*),
233                                    M_EPOCH, M_ZERO|M_WAITOK);
234         ck_epoch_init(&epoch->e_epoch);
235         epoch->e_frees = counter_u64_alloc(M_WAITOK);
236         mtx_init(&epoch->e_lock, "epoch callout", NULL, MTX_DEF);
237         callout_init_mtx(&epoch->e_timer, &epoch->e_lock, 0);
238         taskqgroup_config_gtask_init(epoch, &epoch->e_gtask, epoch_call_task, "epoch call task");
239         if (usedomains)
240                 epoch_init_numa(epoch);
241         else
242                 epoch_init_legacy(epoch);
243         callout_reset(&epoch->e_timer, poll_intvl, epoch_callout, epoch);
244         return (epoch);
245 }
246
247 void
248 epoch_free(epoch_t epoch)
249 {
250         int domain;
251 #ifdef INVARIANTS
252         struct epoch_pcpu_state *eps;
253         int cpu;
254
255         CPU_FOREACH(cpu) {
256                 eps = epoch->e_pcpu[cpu];
257                 MPASS(TAILQ_EMPTY(&eps->eps_record.er_tdlist));
258         }
259 #endif
260         mtx_lock(&epoch->e_lock);
261         epoch->e_flags |= EPOCH_EXITING;
262         mtx_unlock(&epoch->e_lock);
263         /*
264          * Execute any lingering callbacks
265          */
266         GROUPTASK_ENQUEUE(&epoch->e_gtask);
267         gtaskqueue_drain(epoch->e_gtask.gt_taskqueue, &epoch->e_gtask.gt_task);
268         callout_drain(&epoch->e_timer);
269         mtx_destroy(&epoch->e_lock);
270         counter_u64_free(epoch->e_frees);
271         taskqgroup_config_gtask_deinit(&epoch->e_gtask);
272         if (usedomains)
273                 for (domain = 0; domain < vm_ndomains; domain++)
274                         free_domain(epoch->e_pcpu_dom[domain], M_EPOCH);
275         else
276                 free(epoch->e_pcpu_dom[0], M_EPOCH);
277         free(epoch, M_EPOCH);
278 }
279
280 #define INIT_CHECK(epoch)                                                               \
281         do {                                                                                    \
282                 if (__predict_false((epoch) == NULL))           \
283                         return;                                                                 \
284         } while (0)
285
286 void
287 epoch_enter(epoch_t epoch)
288 {
289         struct epoch_pcpu_state *eps;
290         struct thread *td;
291
292         INIT_CHECK(epoch);
293
294         td = curthread;
295         critical_enter();
296         eps = epoch->e_pcpu[curcpu];
297         td->td_epochnest++;
298         MPASS(td->td_epochnest < UCHAR_MAX - 2);
299         if (td->td_epochnest == 1)
300                 TAILQ_INSERT_TAIL(&eps->eps_record.er_tdlist, td, td_epochq);
301 #ifdef INVARIANTS
302         if (td->td_epochnest > 1) {
303                 struct thread *curtd;
304                 int found = 0;
305
306                 TAILQ_FOREACH(curtd, &eps->eps_record.er_tdlist, td_epochq)
307                         if (curtd == td)
308                                 found = 1;
309                 KASSERT(found, ("recursing on a second epoch"));
310         }
311 #endif
312         if (td->td_epochnest > 1) {
313                 critical_exit();
314                 return;
315         }
316         sched_pin();
317         ck_epoch_begin(&eps->eps_record.er_record, (ck_epoch_section_t*)&td->td_epoch_section);
318         critical_exit();
319 }
320
321 void
322 epoch_exit(epoch_t epoch)
323 {
324         struct epoch_pcpu_state *eps;
325         struct thread *td;
326
327         td = curthread;
328         INIT_CHECK(epoch);
329         MPASS(td->td_epochnest);
330         critical_enter();
331         eps = epoch->e_pcpu[curcpu];
332         td->td_epochnest--;
333         if (td->td_epochnest == 0)
334                 TAILQ_REMOVE(&eps->eps_record.er_tdlist, td, td_epochq);
335         else {
336                 critical_exit();
337                 return;
338         }
339         sched_unpin();
340         ck_epoch_end(&eps->eps_record.er_record, (ck_epoch_section_t*)&td->td_epoch_section);
341         eps->eps_record.er_gen++;
342         critical_exit();
343 }
344
345 /*
346  * epoch_block_handler is a callback from the ck code when another thread is
347  * currently in an epoch section.
348  */
349 static void
350 epoch_block_handler(struct ck_epoch *global __unused, ck_epoch_record_t *cr,
351                                         void *arg __unused)
352 {
353         epoch_record_t record;
354         struct epoch_pcpu_state *eps;
355         struct thread *td, *tdwait, *owner;
356         struct turnstile *ts;
357         struct lock_object *lock;
358         int spincount, gen;
359
360         eps = arg;
361         record = __containerof(cr, struct epoch_record, er_record);
362         td = curthread;
363         spincount = 0;
364         counter_u64_add(block_count, 1);
365         if (record->er_cpuid != curcpu) {
366                 /*
367                  * If the head of the list is running, we can wait for it
368                  * to remove itself from the list and thus save us the
369                  * overhead of a migration
370                  */
371                 if ((tdwait = TAILQ_FIRST(&record->er_tdlist)) != NULL &&
372                         TD_IS_RUNNING(tdwait)) {
373                         gen = record->er_gen;
374                         thread_unlock(td);
375                         do {
376                                 cpu_spinwait();
377                         } while (tdwait == TAILQ_FIRST(&record->er_tdlist) &&
378                                          gen == record->er_gen && TD_IS_RUNNING(tdwait) &&
379                                          spincount++ < MAX_ADAPTIVE_SPIN);
380                         thread_lock(td);
381                         return;
382                 }
383
384                 /*
385                  * Being on the same CPU as that of the record on which
386                  * we need to wait allows us access to the thread
387                  * list associated with that CPU. We can then examine the
388                  * oldest thread in the queue and wait on its turnstile
389                  * until it resumes and so on until a grace period
390                  * elapses.
391                  *
392                  */
393                 counter_u64_add(migrate_count, 1);
394                 sched_bind(td, record->er_cpuid);
395                 /*
396                  * At this point we need to return to the ck code
397                  * to scan to see if a grace period has elapsed.
398                  * We can't move on to check the thread list, because
399                  * in the meantime new threads may have arrived that
400                  * in fact belong to a different epoch.
401                  */
402                 return;
403         }
404         /*
405          * Try to find a thread in an epoch section on this CPU 
406          * waiting on a turnstile. Otherwise find the lowest
407          * priority thread (highest prio value) and drop our priority
408          * to match to allow it to run.
409          */
410         TAILQ_FOREACH(tdwait, &record->er_tdlist, td_epochq) {
411                 /*
412                  * Propagate our priority to any other waiters to prevent us
413                  * from starving them. They will have their original priority
414                  * restore on exit from epoch_wait().
415                  */
416                 if (!TD_IS_INHIBITED(tdwait) && tdwait->td_priority > td->td_priority) {
417                         thread_lock(tdwait);
418                         sched_prio(tdwait, td->td_priority);
419                         thread_unlock(tdwait);
420                 }
421                 if (TD_IS_INHIBITED(tdwait) && TD_ON_LOCK(tdwait) &&
422                         ((ts = tdwait->td_blocked) != NULL)) {
423                         /*
424                          * We unlock td to allow turnstile_wait to reacquire the
425                          * the thread lock. Before unlocking it we enter a critical
426                          * section to prevent preemption after we reenable interrupts
427                          * by dropping the thread lock in order to prevent tdwait
428                          * from getting to run.
429                          */
430                         critical_enter();
431                         thread_unlock(td);
432                         owner = turnstile_lock(ts, &lock);
433                         /*
434                          * The owner pointer indicates that the lock succeeded. Only
435                          * in case we hold the lock and the turnstile we locked is still
436                          * the one that tdwait is blocked on can we continue. Otherwise
437                          * The turnstile pointer has been changed out from underneath
438                          * us, as in the case where the lock holder has signalled tdwait,
439                          * and we need to continue.
440                          */
441                         if (owner != NULL && ts == tdwait->td_blocked) {
442                                 MPASS(TD_IS_INHIBITED(tdwait) && TD_ON_LOCK(tdwait));
443                                 critical_exit();
444                                 turnstile_wait(ts, owner, tdwait->td_tsqueue);
445                                 counter_u64_add(turnstile_count, 1);
446                                 thread_lock(td);
447                                 return;
448                         } else if (owner != NULL)
449                                 turnstile_unlock(ts, lock);
450                         thread_lock(td);
451                         critical_exit();
452                         KASSERT(td->td_locks == 0,
453                                         ("%d locks held", td->td_locks));
454                 }
455         }
456         /*
457          * We didn't find any threads actually blocked on a lock
458          * so we have nothing to do except context switch away.
459          */
460         counter_u64_add(switch_count, 1);
461         mi_switch(SW_VOL | SWT_RELINQUISH, NULL);
462
463         /*
464          * Release the thread lock while yielding to
465          * allow other threads to acquire the lock
466          * pointed to by TDQ_LOCKPTR(td). Else a
467          * deadlock like situation might happen. (HPS)
468          */
469         thread_unlock(td);
470         thread_lock(td);
471 }
472
473 void
474 epoch_wait(epoch_t epoch)
475 {
476         struct thread *td;
477         int was_bound;
478         int old_cpu;
479         int old_pinned;
480         u_char old_prio;
481 #ifdef INVARIANTS
482         int locks;
483
484         locks = curthread->td_locks;
485 #endif
486         INIT_CHECK(epoch);
487
488         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL,
489             "epoch_wait() can sleep");
490
491         td = curthread;
492         KASSERT(td->td_epochnest == 0, ("epoch_wait() in the middle of an epoch section"));
493         thread_lock(td);
494
495         DROP_GIANT();
496
497         old_cpu = PCPU_GET(cpuid);
498         old_pinned = td->td_pinned;
499         old_prio = td->td_priority;
500         was_bound = sched_is_bound(td);
501         sched_unbind(td);
502         td->td_pinned = 0;
503         sched_bind(td, old_cpu);
504
505         ck_epoch_synchronize_wait(&epoch->e_epoch, epoch_block_handler, NULL);
506
507         /* restore CPU binding, if any */
508         if (was_bound != 0) {
509                 sched_bind(td, old_cpu);
510         } else {
511                 /* get thread back to initial CPU, if any */
512                 if (old_pinned != 0)
513                         sched_bind(td, old_cpu);
514                 sched_unbind(td);
515         }
516         /* restore pinned after bind */
517         td->td_pinned = old_pinned;
518
519         /* restore thread priority */
520         sched_prio(td, old_prio);
521         thread_unlock(td);
522         PICKUP_GIANT();
523         KASSERT(td->td_locks == locks,
524                         ("%d residual locks held", td->td_locks - locks));
525 }
526
527 void
528 epoch_call(epoch_t epoch, epoch_context_t ctx, void (*callback) (epoch_context_t))
529 {
530         struct epoch_pcpu_state *eps;
531         epoch_cb_t cb;
532
533         cb = (void *)ctx;
534
535         MPASS(callback);
536         /* too early in boot to have epoch set up */
537         if (__predict_false(epoch == NULL)) {
538                 callback(ctx);
539                 return;
540         }
541         MPASS(cb->ec_callback == NULL);
542         MPASS(cb->ec_link.stqe_next == NULL);
543         cb->ec_callback = callback;
544         counter_u64_add(epoch->e_frees, 1);
545
546         critical_enter();
547         eps = epoch->e_pcpu[curcpu];
548         STAILQ_INSERT_HEAD(&eps->eps_cblist, cb, ec_link);
549         critical_exit();
550 }
551
552 static void
553 epoch_call_task(void *context)
554 {
555         struct epoch_pcpu_state *eps;
556         epoch_t epoch;
557         epoch_cb_t cb;
558         struct thread *td;
559         int cpu;
560         STAILQ_HEAD(, epoch_cb) tmp_head;
561
562         epoch = context;
563         STAILQ_INIT(&tmp_head);
564         td = curthread;
565         thread_lock(td);
566         CPU_FOREACH(cpu) {
567                 sched_bind(td, cpu);
568                 eps = epoch->e_pcpu[cpu];
569                 if (!STAILQ_EMPTY(&eps->eps_cblist))
570                         STAILQ_CONCAT(&tmp_head, &eps->eps_cblist);
571         }
572         sched_unbind(td);
573         thread_unlock(td);
574         epoch_wait(epoch);
575
576         while ((cb = STAILQ_FIRST(&tmp_head)) != NULL) {
577                 STAILQ_REMOVE_HEAD(&tmp_head, ec_link);
578                 cb->ec_callback((void*)cb);
579         }
580 }
581
582 int
583 in_epoch(void)
584 {
585         return (curthread->td_epochnest != 0);
586 }