Custom interleaved allocation
PATCH 1/1 Custom interleaved allocation
Hi,
I'm submitting a patch that I found quite useful in my case. It supports a user-specified custom interleaved allocation scheme. More specifically, apart from the required allocation size, the user specifies an arbitrary set of partitions and the set of nodes, where each partition must lie on. The interleaved allocator will allocate the required region with a single mmap() call and will then bind the different partitions on the specified nodes, taking care of the correct alignment of the partitions and the possible merging of very small ones.
The key motivation behind this patch is the seamless conversion of existing multithreaded shared-memory-based code to NUMA-aware. For example, suppose you have a multithreaded code acting on a large dataset that you split using your own static load balancing scheme. Converting this code to NUMA-aware using only numa_alloc_onnode() calls would require considerable refactoring, since you need to alter your algorithm toward a more distributed logic. The allocation scheme I'm submitting leaves intact the original shared-memory logic by applying only a user-guided interleaving of the memory pages, based on the algorithm's needs.
The key functions are the alloc_interleaved()', which is responsible for the allocation and node binding, and fix_interleaving()', which fixes the user-specified partitions.
I'm also submitting a set of test/check routines. If you think this patch is relevant, I can integrate it to libnuma.
Regards,
V.K.
[PATCH follows]
Makefile 2012-11-21 20:41:39.000000000 +0200 renamed from Makefile 2012-10-11 23:52:24.000000000 +0300 +3 -2
@@ -32,10 +32,11 @@ test/mbind_mig_pages test/migrate_pages \ migratepages migspeed migspeed.o libnuma.a \ test/move_pages test/realloc_test sysfs.o affinity.o \ - test/node-parse rtnetlink.o test/A numastat + test/node-parse rtnetlink.o test/A numastat \ + custom_interleaved.o custom_interleaved SOURCES := bitops.c libnuma.c distance.c memhog.c numactl.c numademo.c \ numamon.c shm.c stream_lib.c stream_main.c syscall.c util.c mt.c \ - clearcache.c test/*.c affinity.c sysfs.c rtnetlink.c + clearcache.c test/*.c affinity.c sysfs.c rtnetlink.c
custom_interleaved.c
ifeq ($(strip $(PREFIX)),)
prefix := /usr
@@ -49,7 +50,7 @@
test/tshared stream test/mynode test/pagesize test/ftok
test/prefered \
test/randmap test/nodemap test/distance test/tbitmap test/move_pages \
test/mbind_mig_pages test/migrate_pages test/realloc_test libnuma.a \- test/node-parse numastat
+ test/node-parse numastat custom_interleaved
numactl: numactl.o util.o shm.o bitops.o libnuma.so
@@ -103,6 +104,8 @@
$(AR) rc $@ $^
$(RANLIB) $@+custom_interleaved: LDLIBS += libnuma.a
+
distance.o : CFLAGS += -fPIC
syscall.o : CFLAGS += -fPIC
diff -urN numactl-2.0.8-orig/custom_interleaved.c numactl-2.0.8/custom_interleaved.c
--- numactl-2.0.8-orig/custom_interleaved.c 1970-01-01
02:00:00.000000000 +0200
+++ numactl-2.0.8/custom_interleaved.c 2012-11-21 19:48:57.000000000
+0200
@@ -0,0 +1,333 @@
+/*
+ * User-defined custom interleaving of memory pages.
+ *
+ * Copyright (C) 2011-2012, Vasileios Karakasis
+ * Copyright (C) 2011-2012, Theodoros Gkountouvas
+ */
+#include <numa.h>
+#include <numaif.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <assert.h>
+
+#define ALIGN_ADDR(addr, bound) (void *)((unsigned long) addr & ~(bound-1)) +
+static int get_best_node(const size_t *node_scores, int nr_nodes) +{
+ int j; + int ret = 0; + size_t max_score = node_scores[0]; + for (j = 1; j < nr_nodes; j++)
+ if (node_scores[j] > max_score) {
+ max_score = node_scores[j];
+ ret = j;
+ }
+
+ return ret;
+}
+
+static void fix_interleaving(size_t nr_parts, size_t *parts, int *nodes) +{
+ int i;
+ int nr_nodes = numa_num_configured_nodes();
+ int pagesize = numa_pagesize();
+ size_t *node_scores = calloc(nr_nodes, sizeof(*node_scores));
+ if (!node_scores) {+ perror("malloc");
+ exit(1);
+ }
+
+ // merge small partitions
+ size_t base_part = 0;
+ node_scores[nodes[0]] = parts[0];
+ for (i = 1; i < nr_parts; i++) {
+ size_t part_score = parts[i];
+ if (parts[base_part] < pagesize) {
+ // merge with base partition
+ parts[base_part] += parts[i];
+ parts[i] = 0;+ } else {
+ // assign partition to the node with the highest score
+ nodes[base_part] = get_best_node(node_scores, nr_nodes);
+
+ // reset the scores + memset(node_scores, 0, nr_nodes*sizeof(*node_scores)); + base_part = i;
+ }
+
+ node_scores[nodes[i]] += part_score;
+ }
+
+ // fix the last merger
+ nodes[base_part] = get_best_node(node_scores, nr_nodes);
+
+ // adjust partition size to multiples of system's page size
+ size_t rem = 0;
+ ssize_t size_adjust = 0; // can be negative
+ for (i = 0; i < nr_parts; i++) {+ if (!parts[i])
+ continue;
+
+ parts[i] += size_adjust; // adjustment from previous partition
+ rem = parts[i] % pagesize;
+
+ // find next valid partition + size_t next_part = i+1; + while (next_part != nr_parts && !parts[next_part]) + next_part++; + + // + // If at last partition, always execute the else path. + // Otherwise, take the remainder of the page, if the largest part is + // in the current partition, assuring, however, that the next + // partition will have at least one page. + // + if (next_part != nr_parts &&
+ ((rem < pagesize / 2) ||
+ (parts[next_part] + rem < 2*pagesize))) {
+ parts[i] -= rem;
+ size_adjust = rem;
+ } else {
+ parts[i] += pagesize - rem;
+ size_adjust = rem - pagesize;
+ }
+ }
+
+ free(node_scores);
+}
+
+void *alloc_interleaved(size_t size, size_t *parts, size_t nr_parts,
+ int *nodes)
+{
+ int i;
+ void *ret = NULL;
+
+ ret = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_ANONYMOUS |MAP_PRIVATE,
+ 0, 0);
+ if (ret == (void *) -1) {
+ ret = NULL;
+ goto exit;
+ }
+
+ struct bitmask *nodemask = numa_allocate_nodemask();
+
+ /*
+ * Fix the interleaving and bind parts to specific nodes
+ */
+ fix_interleaving(nr_parts, parts, nodes);
+
+ void *curr_part = ret;
+ for (i = 0; i < nr_parts; i++) {
+ if (!parts[i])
+ continue;
+
+ printf("node = %d, part = %zd\n", nodes[i], parts[i]);
+ numa_bitmask_setbit(nodemask, nodes[i]);
+ if (mbind(curr_part, parts[i], MPOL_BIND,+ nodemask->maskp, nodemask->size, 0) < 0) {
+ perror("mbind");
+ exit(1);
+ }
+ curr_part += parts[i];
+
+ /* Clear the mask for the next round */
+ numa_bitmask_clearbit(nodemask, nodes[i]);
+ }
+
+ numa_bitmask_free(nodemask);
+exit:
+ return ret;
+}
+
+int check_region(void *addr, size_t size, int node) +{
+ void *misplaced_start;
+ int pagesize;
+ size_t i;
+ int misplaced_node;
+ int err = 0;
+
+ pagesize = numa_pagesize();
+ misplaced_start = NULL;
+ misplaced_node = -1;
+ void *aligned_addr = ALIGN_ADDR(addr, pagesize);
+ for (i = 0; i < size; i += pagesize) {+ int page_node;
+ if (get_mempolicy(&page_node, 0, 0, aligned_addr + i,
+ MPOL_F_ADDR | MPOL_F_NODE) < 0) {
+ perror("get_mempolicy()");
+ exit(1);
+ }
+
+ if (page_node != node) {
+ // Start of a misplaced region
+ if (!misplaced_start)
+ misplaced_start = aligned_addr + i;
+ misplaced_node = page_node;
+ err = 1;
+ } else {
+ if (misplaced_start) {
+ // End of a misplaced region + assert(misplaced_node != -1); + size_t misplaced_size = (aligned_addr + i - misplaced_start); + fprintf(stderr, "Region [%p,%p) (%zd bytes) is misplaced " + "(lies on node %d but it should be on node %d)\n", + misplaced_start, aligned_addr + i, misplaced_size, + misplaced_node, node);
+ misplaced_start = NULL;
+ misplaced_node = -1;
+ }
+ }
+ }
+
+ if (misplaced_start) {
+ // Last misplaced region + assert(misplaced_node != -1); + size_t misplaced_size = (aligned_addr + i - misplaced_start); + fprintf(stderr, "Region [%p,%p) (%zd bytes) is misplaced " + "(lies on node %d but it should be on node %d)\n", + misplaced_start, aligned_addr + i, misplaced_size, + misplaced_node, node);
+ }
+
+ return err;
+}
+
+int check_interleaved(void *addr, const size_t *parts, size_t nr_parts,
+ const int *nodes)
+{
+ assert(addr && "addr is NULL");
+ assert(parts && "parts is NULL");
+
+ size_t i = 0;
+ int err = 0;
+ for (i = 0; i < nr_parts; i++) {+ if (check_region(addr, parts[i], nodes[i]))
+ err = 1;
+
+ addr += parts[i];
+ }
+
+ return err;
+}
+
+void print_alloc_status(const char *data_descr, int err) +{
+ printf("allocation check for %s... %s\n", data_descr,
+ (err) ? "FAILED (see above for more info)" : "DONE");
+}
+
+static size_t test_region_size(const size_t *parts, size_t nr_parts) +{
+ int i;
+ size_t ret;
+
+ ret = 0;
+ for (i = 0; i < nr_parts; i++)
+ ret += parts[i];
+
+ return ret;
+}
+
+static void test_touch_region(void *addr, size_t size)
+{
+ size_t i; + size_t pagesize = numa_pagesize(); + for (i = 0; i < size; i += pagesize)
+ *((char *) (addr + i)) = 1;
+}
+
+static void test_print_parts(const char *descr,
+ const size_t *parts, size_t nr_parts,
+ const int *nodes)
+{
+ size_t i;
+
+ printf("%s", descr);
+ for (i = 0; i < nr_parts; i++) {
+ printf("parts[%zd] = %zd, nodes[%zd] = %d\n",
+ i, parts[i], i, nodes[i]);
+ }
+}
+
+static void test_interleaving(size_t *parts, size_t nr_parts,
+ int *nodes)
+{
+ size_t region_size = test_region_size(parts, nr_parts);
+
+ test_print_parts("Orig. partitions:\n", parts, nr_parts, nodes);
+ void *region = alloc_interleaved(region_size,
+ parts, nr_parts, nodes);
+
+ if (!region) {
+ perror("alloc_interleaved");
+ exit(1);
+ }
+
+ test_print_parts("New partitions:\n", parts, nr_parts, nodes);
+ test_touch_region(region, region_size);
+
+ /* Check interleaving */
+ int err = check_interleaved(region, parts, nr_parts, nodes);
+ print_alloc_status("test data", err);
+ numa_free(region, region_size);+}
+
+#define NR_PARTS ((size_t) 4)
+
+size_t test_parts[NR_PARTS];
+int test_nodes[NR_PARTS];
+
+int main(void)
+{
+ /* All small regions */
+ test_parts[0] = 100;
+ test_parts[1] = 200;
+ test_parts[2] = 300;
+ test_parts[3] = 400;
+ test_nodes[0] = 0;
+ test_nodes[1] = 0;
+ test_nodes[2] = 1;
+ test_nodes[3] = 1;
+ printf("\n*** Testing very small partitions ***\n");
+ test_interleaving(test_parts, NR_PARTS, test_nodes);
+
+ /* Some small regions */
+ test_parts[0] = 1000;
+ test_parts[1] = 2000;
+ test_parts[2] = 3000;
+ test_parts[3] = 4000;
+ test_nodes[0] = 0;
+ test_nodes[1] = 0;
+ test_nodes[2] = 1;
+ test_nodes[3] = 1;
+ printf("\n*** Testing small partitions ***\n");
+ test_interleaving(test_parts, NR_PARTS, test_nodes);
+
+ /* Some large regions */
+ test_parts[0] = 10000;
+ test_parts[1] = 20000;
+ test_parts[2] = 30000;
+ test_parts[3] = 40000;
+ test_nodes[0] = 0;
+ test_nodes[1] = 0;
+ test_nodes[2] = 1;
+ test_nodes[3] = 1;
+ printf("\n*** Testing large partitions ***\n");
+ test_interleaving(test_parts, NR_PARTS, test_nodes);
+
+ /* Mixture of small and large regions */
+ test_parts[0] = 1000;
+ test_parts[1] = 4000;
+ test_parts[2] = 30000;
+ test_parts[3] = 40000;
+ test_nodes[0] = 0;
+ test_nodes[1] = 0;
+ test_nodes[2] = 1;
+ test_nodes[3] = 1;
+ printf("\n*** Testing small/large partitions ***\n");
+ test_interleaving(test_parts, NR_PARTS, test_nodes);+
+ return 0;
+}
Binary files numactl-2.0.8-orig/test/move_pages and numactl-2.0.8/test/move_pages differ
Review
Quoted 8 lines
(quoted diff) +8
-0+{ + int i; + int nr_nodes = numa_num_configured_nodes(); + int pagesize = numa_pagesize(); + size_t *node_scores = calloc(nr_nodes, sizeof(*node_scores)); + if (!node_scores) { + perror("malloc"); + exit(1);
You cannot handle errors like this in the library.
It's not fully clear to me what the interface of your proposed new function is. Can you send a spec of the new user interface in a manpage like format?
Also it would be good to have some more information on the use case.
My first reaction is that you can create any interleaving scheme you want anyways using the low level functions.
-Andi
Hi,
Quoted 9 lines · Andi Kleen
Review
Quoted 8 lines
(quoted diff) +8
-0+{ + int i; + int nr_nodes = numa_num_configured_nodes(); + int pagesize = numa_pagesize(); + size_t *node_scores = calloc(nr_nodes, sizeof(*node_scores)); + if (!node_scores) { + perror("malloc"); + exit(1);You cannot handle errors like this in the library.
Definitely, this was just a proof-of-concept of my patch.
Quoted 2 lines
It's not fully clear to me what the interface of your proposed new function is. Can you send a spec of the new user interface in a manpage like format?
void *numa_alloc_interleaved_custom(size_t size, size_t *parts, size_t nr_parts, int *nodes);
User-specified custom interleaved allocation.
This function allocates a continuous region of size' bytes (rounded up to the system's page size) that are interleaved in nr_parts' partitions across the system's memory nodes according to the interleaving specification passed in the parts' and nodes' arrays. The size of each partition in bytes and the node that it must lie on are passed in the parts' and nodes' arrays, respectively, both of size nr_parts'. For example, the i-th partition of size parts[i]' will be placed on the node nodes[i]'. This function takes care of the correct alignment of each partition to the system's page size and the parts' array is updated accordingly. The page at the boundary of two partitions is assigned to the partition owning the largest part, provided that each partition is left with at least one page. In cases of very small partitions, not exceeding the system's page size, these are merged into larger ones and placed to the node with the largest allocation requirements among the nodes of the merged partitions. The parts' and nodes' arrays are updated accordingly. For example, supposing the following interleaved allocation scheme (in bytes):
parts = {100, 200, 300, 400}
nodes = {0, 0, 1, 1}
the resulting allocation will be
parts = {4096, 0, 0, 0}
nodes = {1, 0, 1, 1}
Note that sizes of the merged partitions set to zero, while their original node specification is not touched.
On success a pointer to the newly allocated area is returned, otherwise NULL is returned. The parts' and nodes' arguments are set to the values of the updated partition sizes and nodes.
Similarly to numa_alloc_onnode(), this function just reserves the requested allocation space and binds the user-specified partitions to the desired memory nodes. The actual (physical page) allocation will take place on first write. In fact, numa_alloc_interleaved_custom(mysize, &mysize, 1, &mynode)' is equivalent to numa_alloc_onnode(mysize, mynode)'.
Quoted 1 line
Also it would be good to have some more information on the use case.
Suppose you have a large data structure (e.g., a sparse matrix) and a set of operations that operate on this, assuming a continuous allocation. However, some operations are quite time-consuming and memory-intensive, so you have decided to use multiple threads for them. Your balancing is based on a static determination of the data structure partitions, while the partition boundaries are determined by `marks' (e.g., starting/ending rows) in the original data structure. The following is a typical (a little abstract) scenario:
void do_sth_memory_intensive(matrix, matrix_parts) {
for (j = matrix_parts.start to matrix_parts.end)
do_sth(matrix[j])
}
matrix = malloc(size)
init(matrix);other_trivial_ops(matrix);matrix_parts = split_balanced(matrix, nr_threads);
for (i = 0; i < nr_threads; i++)
spawn_thread(do_sth_memory_intensive, matrix, matrix_parts[i])
Since your workload is memory-intensive, NUMA capabilities are quite tempting, but you want to achieve this with the minimum effort. Having already your static balancing scheme with the corresponding partition boundaries, all you need is to replace the typical malloc() call with the custom interleaved allocation call proposed, passing it your partition sizes and the desired nodes. The rest of the operations on your data structure will work as is. For example, converting the above code to NUMA-aware would be sth like
matrix = malloc(size)
init(matrix);other_trivial_ops(matrix);matrix_parts = split_balanced(matrix, nr_threads);
+ matrix_interleaved = numa_alloc_interleaved_custom(size, matrix_parts, nr_threads, mynodes);
+ memcpy(matrix_interleaved, matrix);
+ free(matrix);
for (i = 0; i < nr_threads; i++)
spawn_thread(do_sth_memory_intensive, matrix_interleaved,
matrix_parts[i])
Of course, if the splitting info can be obtained independently from matrix' the memcpy() could be omitted and numa_alloc_interleaved_custom()' would replace the first `malloc()'. But, anyway, this was my exact scenario.
Quoted 2 lines
My first reaction is that you can create any interleaving scheme you want anyways using the low level functions.
This is true, but creating your own interleaving has some low-level intricacies, that the proposed function hides effectively. Supposing you have already you own partition scheme, I suppose an out-of-the-box implementation will be quite tempting.
Quoted 6 lines
-Andi
--
To unsubscribe from this list: send the line "unsubscribe linux-numa" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Regards,
Signature · 1 line
V.K.