kernel - Fix NUMA contention due to assymetric memory
authorMatthew Dillon <dillon@apollo.backplane.com>
Mon, 15 Oct 2018 03:09:47 +0000 (20:09 -0700)
committerMatthew Dillon <dillon@apollo.backplane.com>
Mon, 15 Oct 2018 03:25:37 +0000 (20:25 -0700)
* Fix NUMA contention in situations where memory is associated
  with CPU cores assymetrically.  In particular, with the 2990WX,
  half the cores will have no memory associated with them.

* This was forcing DFly to allocate memory from queues belonging to
  other nearby cores, causing unnecessary SMP contention, as well
  as burn extra time iterating queues.

* Fix by calculating the average number of free pages per-core,
  and then adjust any VM page queue with pages less than the average
  by stealing pages from queues with greater than the average.
  We use a simple iterator to steal pages, so the CPUs with less
  (or zero) direct-attached memory will operate more UMA-like
  (just on 4K boundaries instead of 256-1024 byte boundaries).

* Tested with a 64-thread concurrent compile test.  systat -pv 1
  showed all remaining contention disappear.  Literally, *ZERO*
  contention when we run the test with each thread in its own jail
  with no shared resources.

* NOTE!  This fix is specific to asymetric NUMA configurations
  which are fairly rare in the wild and will not speed up more
  conventional systems.

* Before and after timings on the 2990WX.

  cd /tmp/src
  time make -j 128 nativekernel NO_MODULES=TRUE > /dev/null

  BEFORE
  703.915u 167.605s 0:49.97 1744.0%       9993+749k 22188+8io 216pf+0w
  699.550u 171.148s 0:50.87 1711.5%       9994+749k 21066+8io 150pf+0w

  AFTER
  678.406u 108.857s 0:45.66 1724.1%       10105+757k 22188+8io 216pf+0w
  674.805u 115.256s 0:46.67 1692.8%       10077+755k 21066+8io 150pf+0w

  This is a 4.2 second difference on the second run, an over 8%
  improvement which is nothing to sneeze at.

sys/kern/subr_cpu_topology.c
sys/platform/pc64/acpica/acpi_srat.c
sys/sys/cpu_topology.h
sys/vm/vm_page.c
sys/vm/vm_page.h

index 5ac4d49..2dd67bf 100644 (file)
@@ -53,6 +53,7 @@ struct per_cpu_sysctl_info {
        char cpu_name[32];
        int physical_id;
        int core_id;
+       int ht_id;                              /* thread id within core */
        char physical_siblings[8*MAXCPU];
        char core_siblings[8*MAXCPU];
 };
@@ -68,12 +69,15 @@ static per_cpu_sysctl_info_t *pcpu_sysctl;
 static void sbuf_print_cpuset(struct sbuf *sb, cpumask_t *mask);
 
 int cpu_topology_levels_number = 1;
+int cpu_topology_ht_ids;
 int cpu_topology_core_ids;
 int cpu_topology_phys_ids;
 cpu_node_t *root_cpu_node;
 
 MALLOC_DEFINE(M_PCPUSYS, "pcpusys", "pcpu sysctl topology");
 
+SYSCTL_INT(_hw, OID_AUTO, cpu_topology_ht_ids, CTLFLAG_RW,
+          &cpu_topology_ht_ids, 0, "# of logical cores per real core");
 SYSCTL_INT(_hw, OID_AUTO, cpu_topology_core_ids, CTLFLAG_RW,
           &cpu_topology_core_ids, 0, "# of real cores per package");
 SYSCTL_INT(_hw, OID_AUTO, cpu_topology_phys_ids, CTLFLAG_RW,
@@ -594,9 +598,12 @@ init_pcpu_topology_sysctl(int assumed_ncpus)
                sbuf_finish(&sb);
 
                pcpu_sysctl[i].core_id = get_core_number_within_chip(i);
-               if (cpu_topology_core_ids < pcpu_sysctl[i].core_id)
+               if (cpu_topology_core_ids < pcpu_sysctl[i].core_id + 1)
                        cpu_topology_core_ids = pcpu_sysctl[i].core_id + 1;
 
+               pcpu_sysctl[i].ht_id = get_logical_CPU_number_within_core(i);
+               if (cpu_topology_ht_ids < pcpu_sysctl[i].ht_id + 1)
+                       cpu_topology_ht_ids = pcpu_sysctl[i].ht_id + 1;
        }
 
        /*
@@ -747,6 +754,14 @@ sbuf_print_cpuset(struct sbuf *sb, cpumask_t *mask)
        sbuf_printf(sb, ") ");
 }
 
+int
+get_cpu_ht_id(int cpuid)
+{
+       if (pcpu_sysctl)
+               return(pcpu_sysctl[cpuid].ht_id);
+       return(0);
+}
+
 int
 get_cpu_core_id(int cpuid)
 {
index fc77f7b..12d4ec5 100644 (file)
@@ -140,6 +140,7 @@ srat_probe(void)
                        kprintf("(not found)\n");
                }
        }
+       vm_numa_organize_finalize();
 
 done:
        sdt_sdth_unmap(&srat->Header);
index 2de510a..3db45c0 100644 (file)
@@ -37,6 +37,7 @@ typedef struct cpu_node cpu_node_t;
 #if defined(_KERNEL)
 
 extern int cpu_topology_levels_number;
+extern int cpu_topology_ht_ids;
 extern int cpu_topology_core_ids;
 extern int cpu_topology_phys_ids;
 extern cpu_node_t *root_cpu_node;
@@ -45,6 +46,7 @@ cpumask_t get_cpumask_from_level(int cpuid, uint8_t level_type);
 cpu_node_t *get_cpu_node_by_cpuid(int cpuid);
 const cpu_node_t *get_cpu_node_by_chipid(int chip_id);
 long get_highest_node_memory(void);
+int get_cpu_ht_id(int cpuid);
 int get_cpu_core_id(int cpuid);
 int get_cpu_phys_id(int cpuid);
 
index 14ea145..21348b2 100644 (file)
@@ -449,6 +449,8 @@ vm_page_startup(void)
 }
 
 /*
+ * (called from early boot only)
+ *
  * Reorganize VM pages based on numa data.  May be called as many times as
  * necessary.  Will reorganize the vm_page_t page color and related queue(s)
  * to allow vm_page_alloc() to choose pages based on socket affinity.
@@ -466,9 +468,9 @@ vm_numa_organize(vm_paddr_t ran_beg, vm_paddr_t bytes, int physid)
        struct vpgqueues *vpq;
        vm_page_t m;
        vm_page_t mend;
-       int i;
        int socket_mod;
        int socket_value;
+       int i;
 
        /*
         * Check if no physical information, or there was only one socket
@@ -543,6 +545,101 @@ vm_numa_organize(vm_paddr_t ran_beg, vm_paddr_t bytes, int physid)
                        ++m;
                }
        }
+
+       crit_exit();
+}
+
+/*
+ * (called from early boot only)
+ *
+ * Don't allow the NUMA organization to leave vm_page_queues[] nodes
+ * completely empty for a logical cpu.  Doing so would force allocations
+ * on that cpu to always borrow from a nearby cpu, create unnecessary
+ * contention, and cause vm_page_alloc() to iterate more queues and run more
+ * slowly.
+ *
+ * This situation can occur when memory sticks are not entirely populated,
+ * populated at different densities, or in naturally assymetric systems
+ * such as the 2990WX.  There could very well be many vm_page_queues[]
+ * entries with *NO* pages assigned to them.
+ *
+ * Fixing this up ensures that each logical CPU has roughly the same
+ * sized memory pool, and more importantly ensures that logical CPUs
+ * do not wind up with an empty memory pool.
+ *
+ * At them moment we just iterate the other queues and borrow pages,
+ * moving them into the queues for cpus with severe deficits even though
+ * the memory might not be local to those cpus.  I am not doing this in
+ * a 'smart' way, its effectively UMA style (sorta, since its page-by-page
+ * whereas real UMA typically exchanges address bits 8-10 with high address
+ * bits).  But it works extremely well and gives us fairly good deterministic
+ * results on the cpu cores associated with these secondary nodes.
+ */
+void
+vm_numa_organize_finalize(void)
+{
+       struct vpgqueues *vpq;
+       vm_page_t m;
+       long lcnt_lo;
+       long lcnt_hi;
+       int iter;
+       int i;
+       int scale_lim;
+
+       crit_enter();
+
+       /*
+        * Machines might not use an exact power of 2 for phys_ids,
+        * core_ids, ht_ids, etc.  This can slightly reduce the actual
+        * range of indices in vm_page_queues[] that are nominally used.
+        */
+       if (cpu_topology_ht_ids) {
+               scale_lim = PQ_L2_SIZE / cpu_topology_phys_ids;
+               scale_lim = scale_lim / cpu_topology_core_ids;
+               scale_lim = scale_lim / cpu_topology_ht_ids;
+               scale_lim = scale_lim * cpu_topology_ht_ids;
+               scale_lim = scale_lim * cpu_topology_core_ids;
+               scale_lim = scale_lim * cpu_topology_phys_ids;
+       } else {
+               scale_lim = PQ_L2_SIZE;
+       }
+
+       /*
+        * Calculate an average, set hysteresis for balancing from
+        * 10% below the average to the average.
+        */
+       lcnt_hi = 0;
+       for (i = 0; i < scale_lim; ++i) {
+               lcnt_hi += vm_page_queues[i].lcnt;
+       }
+       lcnt_hi /= scale_lim;
+       lcnt_lo = lcnt_hi - lcnt_hi / 10;
+
+       kprintf("vm_page: avg %ld pages per queue, %d queues\n",
+               lcnt_hi, scale_lim);
+
+       iter = 0;
+       for (i = 0; i < scale_lim; ++i) {
+               vpq = &vm_page_queues[PQ_FREE + i];
+               while (vpq->lcnt < lcnt_lo) {
+                       struct vpgqueues *vptmp;
+
+                       iter = (iter + 1) & PQ_L2_MASK;
+                       vptmp = &vm_page_queues[PQ_FREE + iter];
+                       if (vptmp->lcnt < lcnt_hi)
+                               continue;
+                       m = TAILQ_FIRST(&vptmp->pl);
+                       KKASSERT(m->queue == PQ_FREE + iter);
+                       TAILQ_REMOVE(&vptmp->pl, m, pageq);
+                       --vptmp->lcnt;
+                       /* queue doesn't change, no need to adj cnt */
+                       m->queue -= m->pc;
+                       m->pc = i;
+                       m->queue += m->pc;
+                       TAILQ_INSERT_HEAD(&vpq->pl, m, pageq);
+                       ++vpq->lcnt;
+               }
+       }
        crit_exit();
 }
 
@@ -960,29 +1057,61 @@ u_short
 vm_get_pg_color(int cpuid, vm_object_t object, vm_pindex_t pindex)
 {
        u_short pg_color;
-       int phys_id;
-       int core_id;
        int object_pg_color;
 
-       phys_id = get_cpu_phys_id(cpuid);
-       core_id = get_cpu_core_id(cpuid);
+       /*
+        * WARNING! cpu_topology_core_ids might not be a power of two.
+        *          We also shouldn't make assumptions about
+        *          cpu_topology_phys_ids either.
+        *
+        * WARNING! ncpus might not be known at this time (during early
+        *          boot), and might be set to 1.
+        *
+        * General format: [phys_id][core_id][cpuid][set-associativity]
+        * (but uses modulo, so not necessarily precise bit masks)
+        */
        object_pg_color = object ? object->pg_color : 0;
 
-       if (cpu_topology_phys_ids && cpu_topology_core_ids) {
-               int grpsize;
+       if (cpu_topology_ht_ids) {
+               int phys_id;
+               int core_id;
+               int ht_id;
+               int physcale;
+               int grpscale;
+               int cpuscale;
 
                /*
-                * Break us down by socket and cpu
+                * Translate cpuid to socket, core, and hyperthread id.
                 */
-               pg_color = phys_id * PQ_L2_SIZE / cpu_topology_phys_ids;
-               pg_color += core_id * PQ_L2_SIZE /
-                           (cpu_topology_core_ids * cpu_topology_phys_ids);
+               phys_id = get_cpu_phys_id(cpuid);
+               core_id = get_cpu_core_id(cpuid);
+               ht_id = get_cpu_ht_id(cpuid);
 
                /*
-                * Calculate remaining component for object/queue color
+                * Calculate pg_color for our array index.
+                *
+                * physcale - socket multiplier.
+                * grpscale - core multiplier (cores per socket)
+                * cpu*     - cpus per core
+                *
+                * WARNING! In early boot, ncpus has not yet been
+                *          initialized and may be set to (1).
+                *
+                * WARNING! physcale must match the organization that
+                *          vm_numa_organize() creates to ensure that
+                *          we properly localize allocations to the
+                *          requested cpuid.
                 */
-               grpsize = PQ_L2_SIZE / (cpu_topology_core_ids *
-                                       cpu_topology_phys_ids);
+               physcale = PQ_L2_SIZE / cpu_topology_phys_ids;
+               grpscale = physcale / cpu_topology_core_ids;
+               cpuscale = grpscale / cpu_topology_ht_ids;
+
+               pg_color = phys_id * physcale;
+               pg_color += core_id * grpscale;
+               pg_color += ht_id * cpuscale;
+               pg_color += (pindex + object_pg_color) % cpuscale;
+
+#if 0
                if (grpsize >= 8) {
                        pg_color += (pindex + object_pg_color) % grpsize;
                } else {
@@ -996,12 +1125,20 @@ vm_get_pg_color(int cpuid, vm_object_t object, vm_pindex_t pindex)
                        }
                        pg_color += (pindex + object_pg_color) % grpsize;
                }
+#endif
        } else {
                /*
                 * Unknown topology, distribute things evenly.
+                *
+                * WARNING! In early boot, ncpus has not yet been
+                *          initialized and may be set to (1).
                 */
-               pg_color = cpuid * PQ_L2_SIZE / ncpus;
-               pg_color += pindex + object_pg_color;
+               int cpuscale;
+
+               cpuscale = PQ_L2_SIZE / ncpus;
+
+               pg_color = cpuid * cpuscale;
+               pg_color += (pindex + object_pg_color) % cpuscale;
        }
        return (pg_color & PQ_L2_MASK);
 }
index 91f58a6..1ff10ee 100644 (file)
@@ -157,10 +157,15 @@ typedef struct vm_page *vm_page_t;
  * lock contention between cpus.
  *
  * Page coloring cannot be disabled.
+ *
+ * In today's world of many-core systems, we must be able to provide enough VM
+ * page queues for each logical cpu thread to cover the L1/L2/L3 cache set
+ * associativity.  If we don't, the cpu caches will not be properly utilized.
+ * Using 2048 allows 8-way set-assoc with 256 logical cpus.
  */
 #define PQ_PRIME1 31   /* Prime number somewhat less than PQ_HASH_SIZE */
 #define PQ_PRIME2 23   /* Prime number somewhat less than PQ_HASH_SIZE */
-#define PQ_L2_SIZE 512 /* A number of colors opt for 1M cache */
+#define PQ_L2_SIZE 2048        /* Must be enough for maximal ncpus x hw set-assoc */
 #define PQ_L2_MASK     (PQ_L2_SIZE - 1)
 
 #define PQ_NONE                0
@@ -386,6 +391,7 @@ void vm_page_remove (vm_page_t);
 void vm_page_rename (vm_page_t, struct vm_object *, vm_pindex_t);
 void vm_page_startup (void);
 void vm_numa_organize(vm_paddr_t ran_beg, vm_paddr_t bytes, int physid);
+void vm_numa_organize_finalize(void);
 void vm_page_unmanage (vm_page_t);
 void vm_page_unwire (vm_page_t, int);
 void vm_page_wire (vm_page_t);