Automatic NUMA placement for xl

Hi Everyone again,

New version (v7) of the last bit of the NUMA placement series, addressing all the comments the last round received:

1/4 libxl: kill the need for checking and linking to libm 2/4 libxl: enable automatic placement of guests on NUMA nodes 3/4 libxl: have NUMA placement deal with cpupools 4/4 Some automatic NUMA placement documentation

All the patches but 1/4 one have been acked at least once at this point.

The biggest news about this version is the rework of the placement compaison function (in patch 2/4), as discussed during review of v6. In fact, it now looks both simpler and clearer than before (and does no longer need any floating point arithmetic). For that reason, I'm including 1/4, which is a de-facto rrevert of 7b0dc7f3ddfe ("libxl: explicitly check for libmath in autoconf") as asking for libm to be present and linking with it is no longer necessary.

Thanks and Regards,
Dario

<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://retis.sssup.it/people/faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Which was introduced in 7b0dc7f3ddfe. This is because the NUMA placement heuristic does not need FP arith anymore.

As usual when changing configure.ac, remember to rerun autoconf after applying this change.

@@ -137,7 +137,6 @@ AC_CHECK_LIB([lzo2], [lzo1x_decompress],
 AC_SUBST(zlib)
 AC_CHECK_LIB([aio], [io_setup], [system_aio="y"], [system_aio="n"])
 AC_SUBST(system_aio)
-AC_CHECK_LIB([m], [isnan], [], [AC_MSG_ERROR([Could not find libm])])
 AC_CHECK_LIB([crypto], [MD5], [], [AC_MSG_ERROR([Could not find libcrypto])])
 AC_CHECK_LIB([ext2fs], [ext2fs_open2], [libext2fs="y"], [libext2fs="n"])
 AC_SUBST(libext2fs)

@@ -61,7 +61,7 @@ ifeq ($(BISON),)
 		  scanners, please install it an rerun configure)
 endif
 
-LIBXL_LIBS += -lyajl -lm
+LIBXL_LIBS += -lyajl
 
 LIBXL_OBJS = flexarray.o libxl.o libxl_create.o libxl_dm.o libxl_pci.o \
 			libxl_dom.o libxl_exec.o libxl_xshelp.o libxl_device.o \

Acked and applied, thanks.

If a domain does not have a VCPU affinity, try to pin it automatically to some PCPUs. This is done taking into account the NUMA characteristics of the host. In fact, we look for a combination of host's NUMA nodes with enough free memory and number of PCPUs for the new domain, and pin it to the VCPUs of those nodes.

Deciding which placement is the best happens by means of some heuristics. For instance, smaller candidates are better, both from a domain perspective (less memory spreading among nodes) and from the entire system perspective (smaller memory fragmentation). In case of candidates of equal sizes (i.e., with the same number of nodes), the amount of free memory and the number of domains' vCPUs already pinned to the candidates' nodes are both considered. Very often, candidates with greater amount of memory are the one we wants, as this is good for keeping memory fragmentation under control. However, we do not want to overcommit some node too much, just because it has a lot of memory, and that's why the number of vCPUs must be accounted for.

This all happens internally to libxl, and no API for driving the mechanism is provided for now. This matches what xend already does.

---
Changes from v6:
* Patch for properly triggering placement only if we don't have any vcpu affinity (which was 2/4 in v6) merged into this one.
* Placement candidate comparison function reworked again, as requested during review.
* Improved the error logging, as equested during review.
* Indentation and line wrapping fixes.

Changes from v5:
* macros moved from libxl_numa.c to libxl_internal.h.
* Changed the placement heuristics that now considers how many vCPUs are already pinned to a candidate, instead of how many domains, as suggested during testing/review (thanks a lot Andre!).
* Changed the weights in the placement heuristics so that, now, CPU load counts more than free memory, as suggested during testing/review (thanks a log again Andre! :-D).
* Removed the separation between generating the list of possible candidates and sorting that list. Now the best candidate is selected on-line, without the need of keeping track of more than 2 candidates at a time.
* Thanks to the above, the placement can now end earlier, i.e., as soon as a placement is found and all the other candidates with the same number of nodes have been checked (as bigger candidates would be worse than that anyway).
* Avoid running any placement if the system has more than 8 nodes, as agreed during review.
* Avoid running any placement if the config file has a "cpus='all'" directive, as suggested during review.

Changes from v3:
* fixed a double free on non-NUMA systems (namely, when just 1 node exists).
* Reword an ambiguous sentence in xl's man page, as requested during review.
* Do no special case single node systems in libxl__get_numa_candidates(), to avoid generating a spurious warning on them.

Changes from v2:
* lots of typos.
* Clayfied some comments, as requested during (ijc's) review.
* Added some more information/reference for the combination generation algorithm.
* nodemap_to_nodes_cpus() function renamed to nodemap_to_nr_cpus().
* libxl_bitmap_init() used to make sure we do not try to free random memory on failure paths of functions that allocates a libxl_bitmap.
* Always invoke libxl__sort_numa_candidates(), even if we get there with just 1 candidate, as requested during review.
* Simplified the if-s that check for input parameter consistency in libxl__get_numa_candidates() as requested during (gwd's) review.
* Comparison function for candidates changed so that it now provides total ordering, as requested during review. It is still using FP arithmetic, though. Also I think that just putting the difference between the amount of free memory and between the number of assigned domains of two candidates in a single formula (after normalizing and weighting them) is both clear and effective enough.
* Function definitions moved to a numa specific source file (libxl_numa.c), as suggested during review.

Changes from v1:
* This patches incorporates the changes from both "libxl, xl: enable automatic placement of guests on NUMA nodes" and "libxl, xl: heuristics for reordering NUMA placement candidates" from v1.
* The logic of the algorithm is basically the same as in v1, but the splitting of it in the various functions has been completely redesigned from scratch.
* No public API for placement or candidate generation is now exposed, everything happens within libxl, as agreed during v1 review.
* The relevant documentation have been moved near the actual functions and features. Also, the amount and (hopefully!) the quality of the documentation has been improved a lot, as requested.
* All the comments about using the proper libxl facilities and helpers for allocations, etc., have been considered and applied.
* This patch still bails out from NUMA optimizations if it find out cpupools are being utilized. It is next patch that makes the two things interact properly, as suggested during review.

@@ -111,8 +111,8 @@ created online and the remainder will be
 
 =item B<cpus="CPU-LIST">
 
-List of which cpus the guest is allowed to use. Default behavior is
-`all cpus`. A C<CPU-LIST> may be specified as follows:
+List of which cpus the guest is allowed to use. By default xl will pick
+some cpus on its own (see below). A C<CPU-LIST> may be specified as follows:
 
 =over 4
 

@@ -132,6 +132,12 @@ run on cpu #3 of the host.
 
 =back
 
+If this option is not specified, libxl automatically tries to place the new
+domain on the host's NUMA nodes (provided the host has more than one NUMA
+node) by pinning it to the cpus of those nodes. A heuristic approach is
+utilized with the goals of maximizing performance for the domain and, at
+the same time, achieving efficient utilization of the host's CPUs and RAM.
+
 =item B<cpu_weight=WEIGHT>
 
 A domain with a weight of 512 will get twice as much CPU as a domain

@@ -66,7 +66,7 @@ LIBXL_LIBS += -lyajl
 LIBXL_OBJS = flexarray.o libxl.o libxl_create.o libxl_dm.o libxl_pci.o \
 			libxl_dom.o libxl_exec.o libxl_xshelp.o libxl_device.o \
 			libxl_internal.o libxl_utils.o libxl_uuid.o \
-			libxl_json.o libxl_aoutils.o \
+			libxl_json.o libxl_aoutils.o libxl_numa.o \
 			libxl_save_callout.o _libxl_save_msgs_callout.o \
 			libxl_qmp.o libxl_event.o libxl_fork.o $(LIBXL_OBJS-y)
 LIBXL_OBJS += _libxl_types.o libxl_flask.o _libxl_types_internal.o

@@ -215,6 +215,8 @@ int libxl__domain_build_info_setdefault(
         libxl_bitmap_set_any(&b_info->cpumap);
     }
 
+    libxl_defbool_setdefault(&b_info->numa_placement, true);
+
     if (b_info->max_memkb == LIBXL_MEMKB_DEFAULT)
         b_info->max_memkb = 32 * 1024;
     if (b_info->target_memkb == LIBXL_MEMKB_DEFAULT)

@@ -249,6 +249,7 @@ libxl_domain_build_info = Struct("domain
     ("max_vcpus",       integer),
     ("avail_vcpus",     libxl_bitmap),
     ("cpumap",          libxl_bitmap),
+    ("numa_placement",  libxl_defbool),
     ("tsc_mode",        libxl_tsc_mode),
     ("max_memkb",       MemKB),
     ("target_memkb",    MemKB),

@@ -696,6 +696,9 @@ static void parse_config_data(const char
                 vcpu_to_pcpu[n_cpus] = i;
             n_cpus++;
         }
+
+        /* We have a cpumap, disable automatic placement */
+        libxl_defbool_set(&b_info->numa_placement, false);
     }
     else if (!xlu_cfg_get_string (config, "cpus", &buf, 0)) {
         char *buf2 = strdup(buf);

@@ -709,6 +712,8 @@ static void parse_config_data(const char
         if (vcpupin_parse(buf2, &b_info->cpumap))
             exit(1);
         free(buf2);
+
+        libxl_defbool_set(&b_info->numa_placement, false);
     }
 
     if (!xlu_cfg_get_long (config, "memory", &l, 0)) {

I have tested this version 7 on my box in various configurations:
1. Homogeneous memory distribution: 8 nodes, each 16 GB
2. "Odd" configuration: 8 nodes, 4 have 8 GB, 4 have 16 GB 3 Flat memory (by using cpus="all")

I created up to 32 guests with 2 VCPUs and 2 GB each and observed the distribution after every 8th guest. Another round with 2 VCPU guests, but this time with memory sizes varying from 512MB to 5120MB.

The placement was running well in all cases.
The only thing I saw as a little sub-optimal placement in the odd configuration (2) with the differently sized guests. This is probably a side effect of Dom0 ballooning, which is not really NUMA aware AFAIK. This leads to a situation, where some nodes just by chance have less memory than a certain guest needs and so are not considered candidates. I think we can perfectly tolerate this behavior for now. I didn't see anything strange with config 1.

So this patch gets my:

Please apply to 4.2-unstable!

Regards,
Andre.

Wow, that sounds like a lot of work... Thanks a ton for doing this Andre! :-)

It's hard to describe how much I am pleased to hear this. :-P

Yes, that sounds a more than possible explanation. Honestly, I think that no matter how good we are in finding algorithms and heuristics, there always will be some weird combination of host and guest configurations that will lead to equally weird results.

That being said, I also think the algorithm's structure is flexible enough to allow us trying to do better in at least some of this weird but possible situation. For example, we surely can play with some of the parameters we pass to libxl__get_numa_candidate() and with the comparison function in order to deal better with asymmetrical hosts... In the near _future_ !!

Also, instilling some NUMA-awareness in other components, such as the ballooning machinery, should be on our todo-list, for 4.3 perhaps.

That's the important thing for now. :-)

Thanks again and Regards,
Dario

<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://retis.sssup.it/people/faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

_______________________________________________
Xen-devel mailing list
[email protected]
http://lists.xen.org/xen-devel

Dario Faggioli writes ("[PATCH 2 of 4 v7/leftover] libxl: enable automatic placement of guests on NUMA nodes"):

Nice! Thank you (and IanC, and all the others involved in the process) a lot for the thorough reviews and all the hard work this took! :-)

Dario

<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://retis.sssup.it/people/faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

_______________________________________________
Xen-devel mailing list
[email protected]
http://lists.xen.org/xen-devel

In such a way that only the cpus belonging to the cpupool of the domain being placed are considered for the placement itself.

This happens by filtering out all the nodes in which the cpupool has not any cpu from the placement candidates. After that ---as cpu pooling not necessarily happens at NUMA nodes boundaries--- we also make sure only the actual cpus that are part of the pool are considered when counting how much processors a placement candidate provides.

---
Changes from v4:
* fixed a bug in the cpupool filtering logic (also the number of nodes should be affected by that)

Changes from v3:
* fixed a double free on non-NUMA systems (namely, when just 1 node exists).
* Changed the filtering logic: now only the meaningful combinations and nodemap are being considered.

Changes from v2:
* fixed typos in comments.

@@ -128,26 +128,30 @@ static int numa_cmpf(const libxl__numa_c
 }
 
 /* The actual automatic NUMA placement routine */
-static int numa_place_domain(libxl__gc *gc, libxl_domain_build_info *info)
+static int numa_place_domain(libxl__gc *gc, uint32_t domid,
+                             libxl_domain_build_info *info)
 {
     int found;
     libxl__numa_candidate candidate;
     libxl_bitmap candidate_nodemap;
-    libxl_cpupoolinfo *pinfo;
-    int nr_pools, rc = 0;
+    libxl_cpupoolinfo cpupool_info;
+    int i, cpupool, rc = 0;
     uint32_t memkb;
 
     libxl__numa_candidate_init(&candidate);
     libxl_bitmap_init(&candidate_nodemap);
 
-    /* First of all, if cpupools are in use, better not to mess with them */
-    pinfo = libxl_list_cpupool(CTX, &nr_pools);
-    if (!pinfo)
-        return ERROR_FAIL;
-    if (nr_pools > 1) {
-        LOG(NOTICE, "Skipping NUMA placement as cpupools are in use");
-        goto out;
-    }
+    /*
+     * Extract the cpumap from the cpupool the domain belong to. In fact,
+     * it only makes sense to consider the cpus/nodes that are in there
+     * for placement.
+     */
+    rc = cpupool = libxl__domain_cpupool(gc, domid);
+    if (rc < 0)
+        return rc;
+    rc = libxl_cpupool_info(CTX, &cpupool_info, cpupool);
+    if (rc)
+        return rc;
 
     rc = libxl_domain_need_memory(CTX, info, &memkb);
     if (rc)

@@ -159,7 +163,8 @@ static int numa_place_domain(libxl__gc *
 
     /* Find the best candidate with enough free memory and at least
      * as much pcpus as the domain has vcpus.  */
-    rc = libxl__get_numa_candidate(gc, memkb, info->max_vcpus, 0, 0,
+    rc = libxl__get_numa_candidate(gc, memkb, info->max_vcpus,
+                                   0, 0, &cpupool_info.cpumap,
                                    numa_cmpf, &candidate, &found);
     if (rc)
         goto out;

@@ -175,6 +180,13 @@ static int numa_place_domain(libxl__gc *
     if (rc)
         goto out;
 
+    /* Avoid trying to set the affinity to cpus that might be in the
+     * nodemap but not in our cpupool. */
+    libxl_for_each_set_bit(i, info->cpumap) {
+        if (!libxl_bitmap_test(&cpupool_info.cpumap, i))
+            libxl_bitmap_reset(&info->cpumap, i);
+    }
+
     LOG(DETAIL, "NUMA placement candidate with %d nodes, %d cpus and "
                 "%"PRIu32" KB free selected", candidate.nr_nodes,
                 candidate.nr_cpus, candidate.free_memkb / 1024);

@@ -182,7 +194,7 @@ static int numa_place_domain(libxl__gc *
  out:
     libxl__numa_candidate_dispose(&candidate);
     libxl_bitmap_dispose(&candidate_nodemap);
-    libxl_cpupoolinfo_list_free(pinfo, nr_pools);
+    libxl_cpupoolinfo_dispose(&cpupool_info);
     return rc;
 }
 

@@ -214,7 +226,7 @@ int libxl__build_pre(libxl__gc *gc, uint
             return ERROR_INVAL;
         }
 
-        rc = numa_place_domain(gc, info);
+        rc = numa_place_domain(gc, domid, info);
         if (rc)
             return rc;
     }

@@ -2531,6 +2531,10 @@ typedef int (*libxl__numa_candidate_cmpf
  * other hand, if not even one single candidate can be found, the function
  * still returns successfully but cndt_found will be zero.
  *
+ * Finally, suitable_cpumap is useful for telling that only the cpus in that
+ * mask should be considered when generating placement candidates (for
+ * example because of cpupools).
+ *
  * It is up to the function to properly allocate cndt_out (by calling
  * libxl__numa_candidate_alloc()), while it is the caller that should init
  * (libxl__numa_candidate_init()) and free (libxl__numa_candidate_dispose())

@@ -2539,6 +2543,7 @@ typedef int (*libxl__numa_candidate_cmpf
 _hidden int libxl__get_numa_candidate(libxl__gc *gc,
                                       uint32_t min_free_memkb, int min_cpus,
                                       int min_nodes, int max_nodes,
+                                      const libxl_bitmap *suitable_cpumap,
                                       libxl__numa_candidate_cmpf numa_cmpf,
                                       libxl__numa_candidate *cndt_out,
                                       int *cndt_found);

Dario Faggioli writes ("[PATCH 3 of 4 v7/leftover] libxl: have NUMA placement deal with cpupools"):

About rationale, usage and (some small bits of) API.

---
Changes from v6:
* text updated to reflect the modified behaviour.
* Lines wrapped to a smaller column number.

Changes from v5:
* text updated to reflect the modified behaviour.

Changes from v3:
* typos and rewording of some sentences, as suggested during review.

Changes from v1:
* API documentation moved close to the actual functions.

new file mode 100644
@@ -0,0 +1,97 @@
+# Guest Automatic NUMA Placement in libxl and xl #
+
+## Rationale ##
+
+NUMA (which stands for Non-Uniform Memory Access) means that the memory
+accessing times of a program running on a CPU depends on the relative
+distance between that CPU and that memory. In fact, most of the NUMA
+systems are built in such a way that each processor has its local memory,
+on which it can operate very fast. On the other hand, getting and storing
+data from and on remote memory (that is, memory local to some other processor)
+is quite more complex and slow. On these machines, a NUMA node is usually
+defined as a set of processor cores (typically a physical CPU package) and
+the memory directly attached to the set of cores.
+
+The Xen hypervisor deals with NUMA machines by assigning to each domain
+a "node affinity", i.e., a set of NUMA nodes of the host from which they
+get their memory allocated.
+
+NUMA awareness becomes very important as soon as many domains start
+running memory-intensive workloads on a shared host. In fact, the cost
+of accessing non node-local memory locations is very high, and the
+performance degradation is likely to be noticeable.
+
+## Guest Placement in xl ##
+
+If using xl for creating and managing guests, it is very easy to ask for
+both manual or automatic placement of them across the host's NUMA nodes.
+
+Note that xm/xend does the very same thing, the only differences residing
+in the details of the heuristics adopted for the placement (see below).
+
+### Manual Guest Placement with xl ###
+
+Thanks to the "cpus=" option, it is possible to specify where a domain
+should be created and scheduled on, directly in its config file. This
+affects NUMA placement and memory accesses as the hypervisor constructs
+the node affinity of a VM basing right on its CPU affinity when it is
+created.
+
+This is very simple and effective, but requires the user/system
+administrator to explicitly specify affinities for each and every domain,
+or Xen won't be able to guarantee the locality for their memory accesses.
+
+It is also possible to deal with NUMA by partitioning the system using
+cpupools (available in the upcoming release of Xen, 4.2). Again, this
+could be "The Right Answer" for many needs and occasions, but has to
+be carefully considered and setup by hand.
+
+### Automatic Guest Placement with xl ###
+
+If no "cpus=" option is specified in the config file, libxl tries
+to figure out on its own on which node(s) the domain could fit best.
+It is worthwhile noting that optimally fitting a set of VMs on the NUMA
+nodes of an host is an incarnation of the Bin Packing Problem. In fact,
+the various VMs with different memory sizes are the items to be packed,
+and the host nodes are the bins. As such problem is known to be NP-hard,
+we will be using some heuristics.
+
+The first thing to do is find the nodes or the sets of nodes (from now
+on referred to as 'candidates') that have enough free memory and enough
+physical CPUs for accommodating the new domain. The idea is to find a
+spot for the domain with at least as much free memory as it has configured
+to have, and as much pCPUs as it has vCPUs.  After that, the actual
+decision on which candidate to pick happens accordingly to the following
+heuristics:
+
+  *  candidates involving fewer nodes are considered better. In case
+     two (or more) candidates span the same number of nodes,
+  *  candidates with a smaller number of vCPUs runnable on them (due
+     to previous placement and/or plain vCPU pinning) are considered
+     better. In case the same number of vCPUs can run on two (or more)
+     candidates,
+  *  the candidate with with the greatest amount of free memory is
+     considered to be the best one.
+
+Giving preference to candidates with fewer nodes ensures better
+performance for the guest, as it avoid spreading its memory among
+different nodes. Favoring candidates with fewer vCPUs already runnable
+there ensures a good balance of the overall host load. Finally, if more
+candidates fulfil these criteria, prioritizing the nodes that have the
+largest amounts of free memory helps keeping the memory fragmentation
+small, and maximizes the probability of being able to put more domains
+there.
+
+## Guest Placement within libxl ##
+
+xl achieves automatic NUMA just because libxl does it internally. No
+API is provided (yet) for interacting with this feature and modify the
+library behaviour regarding automatic placement, it just happens by
+default if no affinity is specified (as it is with xm/xend).
+
+For actually looking and maybe tweaking the mechanism and the algorithms
+it uses, all is implemented as a set of libxl internal interfaces and
+facilities. Look for the comment "Automatic NUMA placement"
+in libxl\_internal.h.
+
+Note this may change in future versions of Xen/libxl.

Dario Faggioli writes ("[PATCH 4 of 4 v7/leftover] Some automatic NUMA placement documentation"):

...

I applied this one already

I've just applied these two.

There were some comments on this one so I'll wait for a respin.

Ian.

Just hit 'Send'.

Thanks and Regards,
Dario

<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://retis.sssup.it/people/faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

_______________________________________________
Xen-devel mailing list
[email protected]
http://lists.xen.org/xen-devel