From 17e612c5383f9421d12faaaefe6b5e81c9265e6c Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 15 Nov 2018 23:41:59 +0100 Subject: memalloc/arrayalloc: add L1-cache optimisation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- libsimple.c | 142 +++++++++++++++++++++++++++------------------ libsimple/memalloc.h | 6 ++ man3/libsimple_vmemalloc.3 | 18 ++++++ vmemalloc.c | 77 +++++++++++++++++++++--- 4 files changed, 179 insertions(+), 64 deletions(-) diff --git a/libsimple.c b/libsimple.c index 3026160..a5015c3 100644 --- a/libsimple.c +++ b/libsimple.c @@ -6,6 +6,27 @@ #else #include "test.h" +static size_t +gcd(size_t u, size_t v) +{ + size_t t; + int shift = 0; + /* Not needed because u>0, v>0: if (!(u | v)) return u + v; */ + while (!((u | v) & 1)) u >>= 1, v >>= 1, shift++; + while (!(u & 1)) u >>= 1; + do { + while (!(v & 1)) v >>= 1; + if (u > v) t = u, u = v, v = t; + } while (v -= u); + return u << shift; +} + +static size_t +lcm(size_t u, size_t v) +{ + return u / gcd(u, v) * v; +} + static int test_timespec(double d, time_t sec, long int nsec, double rd, const char *s, const char *ss) { @@ -95,9 +116,10 @@ main(void) char buf[1024], *s; int intarray[10]; size_t i, j, n; - size_t pagesize; + size_t pagesize, cacheline; pagesize = (size_t)sysconf(_SC_PAGESIZE); + cacheline = (size_t)sysconf(_SC_LEVEL1_DCACHE_LINESIZE); assert(libsimple_default_failure_exit == 1); @@ -1022,6 +1044,14 @@ main(void) tv2.tv_sec = 1, tv2.tv_usec = 0L; assert(libsimple_cmptimeval(&tv1, &tv2) == -1); +#define ASSERT_ALIGNMENT(INFO, ALIGN)\ + do {\ + assert((INFO)->alignment <= lcm(cacheline, ALIGN));\ + assert(!((INFO)->alignment % (ALIGN)));\ + if ((cacheline - (ALIGN) % cacheline) % cacheline + (INFO)->size % (ALIGN) > cacheline)\ + assert(!((INFO)->alignment % cacheline));\ + } while (0) + assert((ptr = libsimple_mallocz(0, 11))); if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); @@ -1080,7 +1110,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8); - assert(info->alignment == 8); + ASSERT_ALIGNMENT(info, 8); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1090,7 +1120,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 16); - assert(info->alignment == 8); + ASSERT_ALIGNMENT(info, 8); assert(info->zeroed == 16); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1102,7 +1132,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8); - assert(info->alignment == 8 * sizeof(void *)); + ASSERT_ALIGNMENT(info, 8 * sizeof(void *)); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1114,7 +1144,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 16); - assert(info->alignment == 4 * sizeof(void *)); + ASSERT_ALIGNMENT(info, 4 * sizeof(void *)); assert(info->zeroed == 16); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1125,7 +1155,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 9 || info->size == 12); - assert(info->alignment == 4); + ASSERT_ALIGNMENT(info, 4); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1136,7 +1166,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 7 || info->size == 8); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(info->zeroed == 7 || info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1147,7 +1177,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 || info->size == 6); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1200,7 +1230,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 81); - assert(info->alignment == 1); + ASSERT_ALIGNMENT(info, 1); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1210,7 +1240,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 162); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(info->zeroed == 162); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1220,7 +1250,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 243 || info->size == 244); - assert(info->alignment == 4); + ASSERT_ALIGNMENT(info, 4); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1230,7 +1260,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 9 || info->size == 10); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(info->zeroed == 9 || info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1241,7 +1271,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 7 || info->size == 8); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(info->zeroed == 7 || info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1252,7 +1282,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8); - assert(info->alignment == 2); + ASSERT_ALIGNMENT(info, 2); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1263,7 +1293,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 4); - assert(info->alignment == 4); + ASSERT_ALIGNMENT(info, 4); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1274,7 +1304,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8); - assert(info->alignment == 4); + ASSERT_ALIGNMENT(info, 4); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1285,7 +1315,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 || info->size == 8); - assert(info->alignment == 8); + ASSERT_ALIGNMENT(info, 8); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1296,7 +1326,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 9 || info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1307,7 +1337,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 7 || info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 7 || info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1318,7 +1348,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 || info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1329,7 +1359,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 3 * pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1340,7 +1370,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 4 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1351,7 +1381,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1362,7 +1392,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 6 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 6 * pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1373,7 +1403,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1384,7 +1414,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 10 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1409,7 +1439,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1420,7 +1450,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1431,7 +1461,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 || info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1442,7 +1472,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1453,7 +1483,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1464,7 +1494,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 2 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 2 * pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1475,7 +1505,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 3 * pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1486,7 +1516,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 4 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1497,7 +1527,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1508,7 +1538,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 6 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == 6 * pagesize); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1519,7 +1549,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 8 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1530,7 +1560,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 10 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)info->alignment)); } @@ -1555,7 +1585,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 81 * (pagesize - 1)); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1565,7 +1595,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 72 * (pagesize - 2)); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1575,7 +1605,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 9 * (pagesize - 1)); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1585,7 +1615,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 * pagesize - 1); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1596,7 +1626,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 * pagesize + 1); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1607,7 +1637,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize - 1); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1618,7 +1648,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize + 1); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1629,7 +1659,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 127); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1640,7 +1670,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 * pagesize - 1); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1651,7 +1681,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 81 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1661,7 +1691,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 72 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1671,7 +1701,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 9 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1681,7 +1711,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 5 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1692,7 +1722,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 4 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(info->zeroed == info->size); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1703,7 +1733,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1714,7 +1744,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 2 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1725,7 +1755,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } @@ -1736,7 +1766,7 @@ main(void) if (have_custom_malloc()) { assert((info = get_allocinfo(ptr))); assert(info->size == 3 * pagesize); - assert(info->alignment == pagesize); + ASSERT_ALIGNMENT(info, pagesize); assert(!info->zeroed); assert(!((uintptr_t)ptr % (uintptr_t)(info->alignment))); } diff --git a/libsimple/memalloc.h b/libsimple/memalloc.h index 977221b..5b91a64 100644 --- a/libsimple/memalloc.h +++ b/libsimple/memalloc.h @@ -8,6 +8,8 @@ enum libsimple_memalloc_option { LIBSIMPLE_MEMALLOC_NULL_IF_ZERO, LIBSIMPLE_MEMALLOC_ALIGNMENT, LIBSIMPLE_MEMALLOC_PAGE_ALIGNMENT, + LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE, + LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING, LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT, LIBSIMPLE_MEMALLOC_ELEMENT_SIZE, LIBSIMPLE_MEMALLOC_PRODUCT_SIZE, @@ -24,6 +26,8 @@ enum libsimple_memalloc_option { #define LIBSIMPLE_MEMALLOC_NULL_IF_ZERO LIBSIMPLE_MEMALLOC_NULL_IF_ZERO #define LIBSIMPLE_MEMALLOC_ALIGNMENT LIBSIMPLE_MEMALLOC_ALIGNMENT #define LIBSIMPLE_MEMALLOC_PAGE_ALIGNMENT LIBSIMPLE_MEMALLOC_PAGE_ALIGNMENT +#define LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE +#define LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING #define LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT #define LIBSIMPLE_MEMALLOC_ELEMENT_SIZE LIBSIMPLE_MEMALLOC_ELEMENT_SIZE #define LIBSIMPLE_MEMALLOC_PRODUCT_SIZE LIBSIMPLE_MEMALLOC_PRODUCT_SIZE @@ -36,6 +40,8 @@ enum libsimple_memalloc_option { #define LIBSIMPLE_ARRAYALLOC_CONDITIONAL_ZERO_INIT LIBSIMPLE_MEMALLOC_CONDITIONAL_ZERO_INIT #define LIBSIMPLE_ARRAYALLOC_UNIQUE_IF_ZERO LIBSIMPLE_MEMALLOC_UNIQUE_IF_ZERO #define LIBSIMPLE_ARRAYALLOC_NULL_IF_ZERO LIBSIMPLE_MEMALLOC_NULL_IF_ZERO +#define LIBSIMPLE_ARRAYALLOC_ALIGNMENT_TO_CACHE_LINE LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE +#define LIBSIMPLE_ARRAYALLOC_ALLOW_CACHE_LINE_SPLITTING LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING #define LIBSIMPLE_ARRAYALLOC_ROUND_UP_SIZE_TO_ALIGNMENT LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT #define LIBSIMPLE_ARRAYALLOC_PRODUCT_SIZE LIBSIMPLE_MEMALLOC_PRODUCT_SIZE #define LIBSIMPLE_ARRAYALLOC_VA_PRODUCT_SIZE LIBSIMPLE_MEMALLOC_VA_PRODUCT_SIZE diff --git a/man3/libsimple_vmemalloc.3 b/man3/libsimple_vmemalloc.3 index b661f29..e088af2 100644 --- a/man3/libsimple_vmemalloc.3 +++ b/man3/libsimple_vmemalloc.3 @@ -73,6 +73,24 @@ The alignment of the returned pointer should be the page size. By default the alignment is .IR "alignof(max_align_t)" . .TP +.B LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE +Align the pointer to the cache line (usuallly 64 bytes), +in addition other specific or default alignment. +.TP +.B LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING +Allow the allocated memory to misaligned to the +cache line such that the memory is stored over +one more cache line than necessary. For example, +if the cache line is 64 bytes and the requested +alignment is 8 bytes, pointer can be aligned to +the cache line or off by 8, 16, 24, 32, 40, 48, +or 56 bytes. If 32 is allocated, an misalignment +to the cache line by 0, 8, 16, 24, or 32 is +normally used, by if +.B LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING +is used, the alignment can be of with 0, 8, 16, +24, 32, 40, 48, or 56 bytes. +.TP .B LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT The number of bytes to allocated should be rounded up to the next multiple of the alignment, unless it already is diff --git a/vmemalloc.c b/vmemalloc.c index 855d078..0f26cbc 100644 --- a/vmemalloc.c +++ b/vmemalloc.c @@ -1,16 +1,20 @@ /* See LICENSE file for copyright and license details. */ #include "libsimple.h" +#include #ifndef TEST struct memalloc_state { - int zero_init; - int if_zero; - int round_up_size; - int have_size; size_t alignment; size_t elem_size; size_t size_prod; + char zero_init; + char if_zero; + char round_up_size; + char have_size; + char cache_align; + char cache_split; + char pad__[(4 * sizeof(size_t) - 6) % sizeof(size_t)]; }; static int @@ -102,6 +106,16 @@ vmemalloc_parse_args(struct memalloc_state *state, size_t n, va_list ap) state->alignment = (size_t)page_size; break; + case LIBSIMPLE_MEMALLOC_ALIGNMENT_TO_CACHE_LINE: + if (state->cache_align++) + goto inval; + break; + + case LIBSIMPLE_MEMALLOC_ALLOW_CACHE_LINE_SPLITTING: + if (state->cache_split++) + goto inval; + break; + case LIBSIMPLE_MEMALLOC_ROUND_UP_SIZE_TO_ALIGNMENT: if (state->round_up_size++) goto inval; @@ -152,21 +166,39 @@ inval: return -1; } +static size_t +gcd(size_t u, size_t v) +{ + size_t t; + int shift = 0; + /* Not needed because u>0, v>0: if (!(u | v)) return u + v; */ + while (!((u | v) & 1)) u >>= 1, v >>= 1, shift++; + while (!(u & 1)) u >>= 1; + do { + while (!(v & 1)) v >>= 1; + if (u > v) t = u, u = v, v = t; + } while (v -= u); + return u << shift; +} + void * libsimple_vmemalloc(size_t n, va_list ap) /* TODO test ([v]{mem,array}alloc) */ { struct memalloc_state state; - size_t misalignment, size; + size_t misalignment, size, cacheline, min, max; void *ptr = NULL; int saved_errno; + long int tmp; + state.alignment = 0; + state.elem_size = 0; + state.size_prod = 1; state.zero_init = -1; state.if_zero = -1; state.round_up_size = 0; state.have_size = 0; - state.alignment = 0; - state.elem_size = 0; - state.size_prod = 1; + state.cache_align = 0; + state.cache_split = 0; if (vmemalloc_parse_args(&state, n, ap)) return NULL; @@ -193,6 +225,35 @@ libsimple_vmemalloc(size_t n, va_list ap) /* TODO test ([v]{mem,array}alloc) */ return NULL; n = n ? n : (state.if_zero > 0); + if (state.cache_align || !state.cache_split) { + tmp = sysconf(_SC_LEVEL1_DCACHE_LINESIZE); + cacheline = (size_t)(tmp < 1 ? 64L : tmp); + } + + if (state.cache_align) { + if (!state.alignment) + state.alignment = alignof(max_align_t); + align_to_cacheline: + if (!(cacheline % state.alignment)) { + state.alignment = cacheline; + } else if (state.alignment % cacheline) { + min = MIN(state.alignment, cacheline); + max = MAX(state.alignment, cacheline); + size = max / gcd(state.alignment, cacheline); + if (size > SIZE_MAX / min) { + errno = ENOMEM; + return NULL; + } + state.alignment = size = min; + } + } else if (!state.cache_split) { + if (!state.alignment) + state.alignment = alignof(max_align_t); + misalignment = cacheline - state.alignment % cacheline; + if (n % cacheline + misalignment % cacheline > cacheline) + goto align_to_cacheline; + } + saved_errno = errno; errno = 0; if (state.alignment) { -- cgit v1.2.3-70-g09d2