kernel - Scale tsleep() performance vs many (thousands) of processes
authorMatthew Dillon <dillon@apollo.backplane.com>
Sun, 13 Aug 2017 06:35:47 +0000 (23:35 -0700)
committerMatthew Dillon <dillon@apollo.backplane.com>
Sun, 13 Aug 2017 07:13:59 +0000 (00:13 -0700)
* In situations where a huge number of processes or threads are present
  and sleeping (that is, more than a few thousand), the global cpumask hash
  table used by tsleep() would saturate and effectively cause any wakeup()
  call to broadcast to all CPUs.

* Refactor the tsleep initialization code to allow the global cpumask
  hash table and the pcpu hash tables to be dynamically allocated.

* Allocate a MUCH larger global cpumask hash table, and significantly
  smaller pcpu hash tables.  The global cpumask hash table is now
  sized to approximate 2 * maxproc, greatly reducing cpumask collisions
  when large numbers of processes exist in the system.

  The pcpu hash tables can be smaller without effecting performance.  This
  will simply result in more entries in each queue which are trivially
  iterated.

  Nominal maxproc ~32,000 -> in the noise (normal desktop system)
  Nominal maxproc ~250,000 -> 16MB worth of hash tables (on a 128G box)
  Maximal maxproc ~2,000,000 -> 122MB worth of hash tables (on a 128G box)

* Remove the unused sched_quantum sysctl and variable.

* Tested with running a pipe() chain through 900,000 processes, the
  end-to-end latency dropped from 25 seconds to 10 seconds and the
  pcpu IPI rate dropped from 60,000 IPIs/cpu to 5000 IPIs/cpu.  This
  is still a bit more than ideal, but much better than before.

* Fix a low-memory panic in zalloc().  A possible infinite recursion
  was not being properly handled.

sys/kern/init_main.c
sys/kern/kern_synch.c
sys/sys/kernel.h
sys/sys/proc.h
sys/vm/vm_zone.c

index 2d89f22..8c754ad 100644 (file)
@@ -756,7 +756,10 @@ mi_gdinit(struct globaldata *gd, int cpuid)
        gd->gd_cpumask_offset = (uintptr_t)CPUMASK_ADDR(*(cpumask_t *)0, cpuid);
        lwkt_gdinit(gd);
        vm_map_entry_reserve_cpu_init(gd);
-       sleep_gdinit(gd);
+       if (gd->gd_cpuid == 0)
+               sleep_early_gdinit(gd);
+       else
+               sleep_gdinit(gd);
        slab_gdinit(gd);
        ATOMIC_CPUMASK_ORBIT(usched_global_cpumask, cpuid);
        gd->gd_vmstats = vmstats;
index 9fe1901..30512df 100644 (file)
@@ -66,10 +66,11 @@ TAILQ_HEAD(tslpque, thread);
 
 static void sched_setup (void *dummy);
 SYSINIT(sched_setup, SI_SUB_KICK_SCHEDULER, SI_ORDER_FIRST, sched_setup, NULL);
+static void sched_dyninit (void *dummy);
+SYSINIT(sched_dyninit, SI_BOOT1_DYNALLOC, SI_ORDER_FIRST, sched_dyninit, NULL);
 
 int    lbolt;
 void   *lbolt_syncer;
-int    sched_quantum;          /* Roundrobin scheduling quantum in ticks. */
 int    ncpus;
 int    ncpus2, ncpus2_shift, ncpus2_mask;      /* note: mask not cpumask_t */
 int    ncpus_fit, ncpus_fit_mask;              /* note: mask not cpumask_t */
@@ -110,28 +111,6 @@ static void        endtsleep (void *);
 static void    loadav (void *arg);
 static void    schedcpu (void *arg);
 
-/*
- * Adjust the scheduler quantum.  The quantum is specified in microseconds.
- * Note that 'tick' is in microseconds per tick.
- */
-static int
-sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
-{
-       int error, new_val;
-
-       new_val = sched_quantum * ustick;
-       error = sysctl_handle_int(oidp, &new_val, 0, req);
-        if (error != 0 || req->newptr == NULL)
-               return (error);
-       if (new_val < ustick)
-               return (EINVAL);
-       sched_quantum = new_val / ustick;
-       return (0);
-}
-
-SYSCTL_PROC(_kern, OID_AUTO, quantum, CTLTYPE_INT|CTLFLAG_RW,
-       0, sizeof sched_quantum, sysctl_kern_quantum, "I", "");
-
 static int pctcpu_decay = 10;
 SYSCTL_INT(_kern, OID_AUTO, pctcpu_decay, CTLFLAG_RW, &pctcpu_decay, 0, "");
 
@@ -281,27 +260,6 @@ schedcpu_resource(struct proc *p, void *data __unused)
        return(0);
 }
 
-/*
- *
- */
-static void
-schedcpu_setup(void *arg)
-{
-       globaldata_t save_gd = mycpu;
-       globaldata_t gd;
-       int n;
-
-       for (n = 0; n < ncpus; ++n) {
-               gd = globaldata_find(n);
-               lwkt_setcpu_self(gd);
-               callout_init_mp(&gd->gd_loadav_callout);
-               callout_init_mp(&gd->gd_schedcpu_callout);
-               schedcpu(NULL);
-               loadav(NULL);
-       }
-       lwkt_setcpu_self(save_gd);
-}
-
 /*
  * This is only used by ps.  Generate a cpu percentage use over
  * a period of one second.
@@ -323,39 +281,19 @@ updatepcpu(struct lwp *lp, int cpticks, int ttlticks)
 }
 
 /*
- * tsleep/wakeup hash table parameters.  Try to find the sweet spot for
- * like addresses being slept on.  The larger the table, the fewer
- * unnecessary IPIs.  However, larger sizes also have diminishing returns
- * and eat memory.
- */
-#define TABLESIZE      8191            /* 4001, 8191, or 16369 */
-#define LOOKUP(x)      (((u_int)(uintptr_t)(x)) % TABLESIZE)
-
-static cpumask_t slpque_cpumasks[TABLESIZE];
-
-/*
- * General scheduler initialization.  We force a reschedule 25 times
- * a second by default.  Note that cpu0 is initialized in early boot and
- * cannot make any high level calls.
+ * Handy macros to calculate hash indices.  LOOKUP() calculates the
+ * global cpumask hash index, TCHASHSHIFT() converts that into the
+ * pcpu hash index.
  *
- * Each cpu has its own sleep queue.
+ * By making the pcpu hash arrays smaller we save a significant amount
+ * of memory at very low cost.  The real cost is in IPIs, which are handled
+ * by the much larger global cpumask hash table.
  */
-void
-sleep_gdinit(globaldata_t gd)
-{
-       static struct tslpque slpque_cpu0[TABLESIZE];
-       int i;
+#define LOOKUP(x)      (((u_int)(uintptr_t)(x)) % slpque_tablesize)
+#define TCHASHSHIFT(x) ((x) >> 4)
 
-       if (gd->gd_cpuid == 0) {
-               sched_quantum = (hz + 24) / 25;
-               gd->gd_tsleep_hash = slpque_cpu0;
-       } else {
-               gd->gd_tsleep_hash = kmalloc(sizeof(slpque_cpu0), 
-                                           M_TSLEEP, M_WAITOK | M_ZERO);
-       }
-       for (i = 0; i < TABLESIZE; ++i)
-               TAILQ_INIT(&gd->gd_tsleep_hash[i]);
-}
+static uint32_t        slpque_tablesize;
+static cpumask_t *slpque_cpumasks;
 
 /*
  * This is a dandy function that allows us to interlock tsleep/wakeup
@@ -378,22 +316,25 @@ static __inline void
 _tsleep_interlock(globaldata_t gd, const volatile void *ident, int flags)
 {
        thread_t td = gd->gd_curthread;
-       int id;
+       uint32_t cid;
+       uint32_t gid;
 
        crit_enter_quick(td);
        if (td->td_flags & TDF_TSLEEPQ) {
-               id = LOOKUP(td->td_wchan);
-               TAILQ_REMOVE(&gd->gd_tsleep_hash[id], td, td_sleepq);
-               if (TAILQ_FIRST(&gd->gd_tsleep_hash[id]) == NULL) {
-                       ATOMIC_CPUMASK_NANDBIT(slpque_cpumasks[id],
+               cid = LOOKUP(td->td_wchan);
+               gid = TCHASHSHIFT(cid);
+               TAILQ_REMOVE(&gd->gd_tsleep_hash[gid], td, td_sleepq);
+               if (TAILQ_FIRST(&gd->gd_tsleep_hash[gid]) == NULL) {
+                       ATOMIC_CPUMASK_NANDBIT(slpque_cpumasks[cid],
                                               gd->gd_cpuid);
                }
        } else {
                td->td_flags |= TDF_TSLEEPQ;
        }
-       id = LOOKUP(ident);
-       TAILQ_INSERT_TAIL(&gd->gd_tsleep_hash[id], td, td_sleepq);
-       ATOMIC_CPUMASK_ORBIT(slpque_cpumasks[id], gd->gd_cpuid);
+       cid = LOOKUP(ident);
+       gid = TCHASHSHIFT(cid);
+       TAILQ_INSERT_TAIL(&gd->gd_tsleep_hash[gid], td, td_sleepq);
+       ATOMIC_CPUMASK_ORBIT(slpque_cpumasks[cid], gd->gd_cpuid);
        td->td_wchan = ident;
        td->td_wdomain = flags & PDOMAIN_MASK;
        crit_exit_quick(td);
@@ -413,16 +354,18 @@ static __inline void
 _tsleep_remove(thread_t td)
 {
        globaldata_t gd = mycpu;
-       int id;
+       uint32_t cid;
+       uint32_t gid;
 
        KKASSERT(td->td_gd == gd && IN_CRITICAL_SECT(td));
        KKASSERT((td->td_flags & TDF_MIGRATING) == 0);
        if (td->td_flags & TDF_TSLEEPQ) {
                td->td_flags &= ~TDF_TSLEEPQ;
-               id = LOOKUP(td->td_wchan);
-               TAILQ_REMOVE(&gd->gd_tsleep_hash[id], td, td_sleepq);
-               if (TAILQ_FIRST(&gd->gd_tsleep_hash[id]) == NULL) {
-                       ATOMIC_CPUMASK_NANDBIT(slpque_cpumasks[id],
+               cid = LOOKUP(td->td_wchan);
+               gid = TCHASHSHIFT(cid);
+               TAILQ_REMOVE(&gd->gd_tsleep_hash[gid], td, td_sleepq);
+               if (TAILQ_FIRST(&gd->gd_tsleep_hash[gid]) == NULL) {
+                       ATOMIC_CPUMASK_NANDBIT(slpque_cpumasks[cid],
                                               gd->gd_cpuid);
                }
                td->td_wchan = NULL;
@@ -937,13 +880,15 @@ _wakeup(void *ident, int domain)
        struct thread *ntd;
        globaldata_t gd;
        cpumask_t mask;
-       int id;
+       uint32_t cid;
+       uint32_t gid;
 
        crit_enter();
        logtsleep2(wakeup_beg, ident);
        gd = mycpu;
-       id = LOOKUP(ident);
-       qp = &gd->gd_tsleep_hash[id];
+       cid = LOOKUP(ident);
+       gid = TCHASHSHIFT(cid);
+       qp = &gd->gd_tsleep_hash[gid];
 restart:
        for (td = TAILQ_FIRST(qp); td != NULL; td = ntd) {
                ntd = TAILQ_NEXT(td, td_sleepq);
@@ -980,7 +925,7 @@ restart:
         * thread pointers.
         */
        if ((domain & PWAKEUP_MYCPU) == 0) {
-               mask = slpque_cpumasks[id];
+               mask = slpque_cpumasks[cid];
                CPUMASK_ANDMASK(mask, gd->gd_other_cpus);
                if (CPUMASK_TESTNZERO(mask)) {
                        lwkt_send_ipiq2_mask(mask, _wakeup, ident,
@@ -1315,12 +1260,134 @@ collect_load_callback(int n)
        return ((averunnable.ldavg[0] * 100 + (fscale >> 1)) / fscale);
 }
 
-/* ARGSUSED */
 static void
-sched_setup(void *dummy)
+sched_setup(void *dummy __unused)
 {
+       globaldata_t save_gd = mycpu;
+       globaldata_t gd;
+       int n;
+
        kcollect_register(KCOLLECT_LOAD, "load", collect_load_callback,
                          KCOLLECT_SCALE(KCOLLECT_LOAD_FORMAT, 0));
-       /* Kick off timeout driven events by calling first time. */
-       schedcpu_setup(NULL);
+
+       /*
+        * Kick off timeout driven events by calling first time.  We
+        * split the work across available cpus to help scale it,
+        * it can eat a lot of cpu when there are a lot of processes
+        * on the system.
+        */
+       for (n = 0; n < ncpus; ++n) {
+               gd = globaldata_find(n);
+               lwkt_setcpu_self(gd);
+               callout_init_mp(&gd->gd_loadav_callout);
+               callout_init_mp(&gd->gd_schedcpu_callout);
+               schedcpu(NULL);
+               loadav(NULL);
+       }
+       lwkt_setcpu_self(save_gd);
+}
+
+/*
+ * Extremely early initialization, dummy-up the tables so we don't have
+ * to conditionalize for NULL in _wakeup() and tsleep_interlock().  Even
+ * though the system isn't blocking this early, these functions still
+ * try to access the hash table.
+ *
+ * This setup will be overridden once sched_dyninit() -> sleep_gdinit()
+ * is called.
+ */
+void
+sleep_early_gdinit(globaldata_t gd)
+{
+       static struct tslpque   dummy_slpque;
+       static cpumask_t dummy_cpumasks;
+
+       slpque_tablesize = 1;
+       gd->gd_tsleep_hash = &dummy_slpque;
+       slpque_cpumasks = &dummy_cpumasks;
+       TAILQ_INIT(&dummy_slpque);
+}
+
+/*
+ * PCPU initialization.  Called after KMALLOC is operational, by
+ * sched_dyninit() for cpu 0, and by mi_gdinit() for other cpus later.
+ *
+ * WARNING! The pcpu hash table is smaller than the global cpumask
+ *         hash table, which can save us a lot of memory when maxproc
+ *         is set high.
+ */
+void
+sleep_gdinit(globaldata_t gd)
+{
+       struct thread *td;
+       uint32_t n;
+       uint32_t i;
+
+       /*
+        * This shouldn't happen, that is there shouldn't be any threads
+        * waiting on the dummy tsleep queue this early in the boot.
+        */
+       if (gd->gd_cpuid == 0) {
+               TAILQ_FOREACH(td, &gd->gd_tsleep_hash[0], td_sleepq) {
+                       kprintf("SLEEP_GDINIT SWITCH %s\n", td->td_comm);
+               }
+       }
+
+       /*
+        * Note that we have to allocate one extra slot because we are
+        * shifting a modulo value.  TCHASHSHIFT(slpque_tablesize - 1) can
+        * return the same value as TCHASHSHIFT(slpque_tablesize).
+        */
+       n = TCHASHSHIFT(slpque_tablesize) + 1;
+
+       gd->gd_tsleep_hash = kmalloc(sizeof(struct tslpque) * n,
+                                    M_TSLEEP, M_WAITOK | M_ZERO);
+       for (i = 0; i < n; ++i)
+               TAILQ_INIT(&gd->gd_tsleep_hash[i]);
+}
+
+/*
+ * Dynamic initialization after the memory system is operational.
+ */
+static void
+sched_dyninit(void *dummy __unused)
+{
+       int tblsize;
+       int tblsize2;
+       int n;
+
+       /*
+        * Calculate table size for slpque hash.  We want a prime number
+        * large enough to avoid overloading slpque_cpumasks when the
+        * system has a large number of sleeping processes, which will
+        * spam IPIs on wakeup().
+        *
+        * While it is true this is really a per-lwp factor, generally
+        * speaking the maxproc limit is a good metric to go by.
+        */
+       for (tblsize = maxproc | 1; ; tblsize += 2) {
+               if (tblsize % 3 == 0)
+                       continue;
+               if (tblsize % 5 == 0)
+                       continue;
+               tblsize2 = (tblsize / 2) | 1;
+               for (n = 7; n < tblsize2; n += 2) {
+                       if (tblsize % n == 0)
+                               break;
+               }
+               if (n == tblsize2)
+                       break;
+       }
+
+       /*
+        * PIDs are currently limited to 6 digits.  Cap the table size
+        * at double this.
+        */
+       if (tblsize > 2000003)
+               tblsize = 2000003;
+
+       slpque_tablesize = tblsize;
+       slpque_cpumasks = kmalloc(sizeof(*slpque_cpumasks) * slpque_tablesize,
+                                 M_TSLEEP, M_WAITOK | M_ZERO);
+       sleep_gdinit(mycpu);
 }
index a99b48c..4d37095 100644 (file)
@@ -135,6 +135,7 @@ enum sysinit_sub_id {
        SI_BOOT1_VM             = 0x1000000,    /* virtual memory system init*/
        SI_BOOT1_ALLOCATOR      = 0x1400000,    /* slab allocator */
        SI_BOOT1_KMALLOC        = 0x1600000,    /* kmalloc inits */
+       SI_BOOT1_DYNALLOC       = 0x1700000,    /* permanent kernel allocs */
        SI_BOOT1_POST           = 0x1800000,    /* post boot1 inits */
 
        /*
index 0100050..8a1bed8 100644 (file)
@@ -510,7 +510,6 @@ extern struct lwp lwp0;                     /* LWP slot for swapper. */
 extern struct thread thread0;          /* Thread slot for swapper. */
 extern int nprocs, maxproc;            /* Current and max number of procs. */
 extern int maxprocperuid;              /* Max procs per uid. */
-extern int sched_quantum;              /* Scheduling quantum in ticks */
 
 extern struct proc *initproc;          /* Process slot for init */
 extern struct thread *pagethread, *updatethread;
@@ -560,6 +559,7 @@ int p_trespass (struct ucred *cr1, struct ucred *cr2);
 void   setrunnable (struct lwp *);
 void   proc_stop (struct proc *, int);
 void   proc_unstop (struct proc *, int);
+void   sleep_early_gdinit (struct globaldata *);
 void   sleep_gdinit (struct globaldata *);
 thread_t cpu_heavy_switch (struct thread *);
 thread_t cpu_lwkt_switch (struct thread *);
index 2cbc285..f495082 100644 (file)
@@ -610,6 +610,34 @@ zget(vm_zone_t z)
        spin_lock(&z->zspin);
        z->ztotal += nitems;
 
+       /*
+        * The zone code may need to allocate kernel memory, which can
+        * recurse zget() infinitely if we do not handle it properly.
+        * We deal with this by directly repopulating the pcpu vm_map_entry
+        * cache.
+        */
+       if (nitems > 1 && (z->zflags & ZONE_SPECIAL)) {
+               struct globaldata *gd = mycpu;
+               vm_map_entry_t entry;
+
+               /*
+                * Make sure we have enough structures in gd_vme_base to handle
+                * the reservation request.
+                *
+                * The critical section protects access to the per-cpu gd.
+                */
+               crit_enter();
+               while (gd->gd_vme_avail < 2 && nitems > 1) {
+                       entry = item;
+                       entry->next = gd->gd_vme_base;
+                       gd->gd_vme_base = entry;
+                       ++gd->gd_vme_avail;
+                       item = (uint8_t *)item + z->zsize;
+                       --nitems;
+               }
+               crit_exit();
+       }
+
        if (nitems != 0) {
                /*
                 * Enter pages into the pool saving one for immediate
@@ -647,14 +675,6 @@ zget(vm_zone_t z)
        }
        spin_unlock(&z->zspin);
 
-       /*
-        * A special zone may have used a kernel-reserved vm_map_entry.  If
-        * so we have to be sure to recover our reserve so we don't run out.
-        * We will panic if we run out.
-        */
-       if (z->zflags & ZONE_SPECIAL)
-               vm_map_entry_reserve(0);
-
        return item;
 }