Implement __emutls_get_address

[chh]

Summary

Implement __emutls_get_address for targets like Android that depends on libgcc's emulated thread local storage.

clang/llvm can generate calls to __emutls_get_address since
http://reviews.llvm.org/D10522 and http://reviews.llvm.org/D10524

[danalbert]

compiler-rt/lib/builtins/emutls.c

18

Just checked with cferris. I don't think this is a default we even want on Android. Sounds like this would maybe be a win for dlmalloc with us, but for jemalloc posix_memalign should be fine. Older devices + N9 are dlmalloc, but he still thinks it's unlikely this is necessary.

34

Only one space between void* and address (I believe, I'm not very familiar with style practices here)

36

Or null

41

Should probably find (or create) a common header for this.

68

No space between the cast and the value

86

text alignment again

91

emutls_address_array* instead of void*? This is C, so there's no mangling concern.

94

A non-trivial loop body should have braces.

108

abort() (no space)

129

Inconsistent pointer positioning. Most of the file has type* var, here is type *var. Not sure what the style is here, but stick to it (or stick to one for this particular file if there isn't consistent style across the whole tree).

134

No space after the cast

143

Probably better to be aligning this multiples of 16 or something instead of just adding 16 since index can be any integer here.

150

This doesn't actually guarantee that we've made enough space, right? If I'm reading this correctly, we need the check on the line above because some other thread may have used many TLS variables that our thread hasn't encountered yet, so our array needs to expand to accommodate them, but if the index is significantly larger than our current array then we won't have made enough space.

compiler-rt/test/builtins/Unit/emutls_test.c

15

sort

51

include file and line number?

75

If this isn't true we have a much bigger problem.

78

The above three don't offer anything that the static asserts don't.

79

Make it a static assert.

[chh]

compiler-rt/lib/builtins/emutls.c

18

If posix_memalign is used, current Android linker won't link because it wants to redefine malloc and free, but not posix_memalign. We can change Android linker, but I think making this module not depending on only basic malloc/free will be more portable. It's not going to be fast accessing emutls variables anyway.

41

Still looking for a place to put this.

91

It should be void* for pthread_key_create's argument type.

143

This calloc or realloc does not need 16-byte or 16-slot aligned address.
It's just some extra slots to avoid too many calloc or realloc.
libgcc uses increment of 32 slots, which seems too big.
Most apps have only a few TLS variables.

150

Other threads can use more than index + 16 variables, but the current thread only need to allocate space for index number of slots, for this call. When other TLS variables are used by this thread later, this thread can allocate more slots if necessary.

compiler-rt/test/builtins/Unit/emutls_test.c

51

I would usually do that, but all other tests use this simple style without file/line number.
Guess it's the style preferred here.

75

Yes, I hope the compile time check is useful to catch configuration errors in cross compilers.

78

Yes, removing them.

[joerg]

compiler-rt/lib/builtins/emutls.c

19

IMO it would still be cleaner to provide two inline functions at the start and
#undef posix_memalign / free and redefine them to map to those two functions. It leaves the complications of the Android issue out of the rest of the file.

144

Just round up to next multiple of 16. No need to allocate some strange number depending on which TLS variable was access first.

151

I still think it would make sense to try to remember the current maximum index. It doesn't have to be thread-safe, just a global variable. Essentially, use something like roundup16(max(index, max_index)) here.

[chh]

compiler-rt/lib/builtins/emutls.c

19

Please take a look of the new diff.
I am not sure that is what what you want.
It has the posix_memalign/malloc/free functions factored out into two inline functions. Maybe it is easier to read.

151

I think emutls_num_object is what you want as a max_index here.
It's shared by all threads and thread safe.
For every newly used TLS variable, its index will be ++emutls_num_object.

[chh]

ping.

[danalbert]

compiler-rt/lib/builtins/emutls.c

42

Wow. Phab makes it hard to track comments across versions. This was about COMPILE_TIME_ASSERT. Feel free to make your own header in lib/builtins for this. We don't have one for this kind of thing yet.

compiler-rt/test/builtins/Unit/emutls_test.c

52

No sense in continuing a bad thing. This should probably all come out to a shared header at some point.

[chh]

Added FILE and LINE output in error messages.
Added comp_assert.h.

compiler-rt/lib/builtins/emutls.c

42

Done. Added new header comp_assert.h.

compiler-rt/test/builtins/Unit/emutls_test.c

52

Done. Added FILE and LINE to printf output.

[compnerd]

compiler-rt/lib/builtins/comp_assert.h

20 ↗

(On Diff #33016)

Why not just put this in int_lib.h?

[chh]

compiler-rt/lib/builtins/comp_assert.h

20 ↗

(On Diff #33016)

Maybe you mean int_util.h?
int_lib.h defines target dependent configuration macros and functions.
int_util.h defines aborting macros and declares aborting functions.
COMPILE_TIME_ASSERT is target independent compile-time checking and does not generate any code.

Now comp_assert.h is only included by one file.
If it is included by multiple files in the future, I think it would be better to separate different functionality into multiple header files.

[compnerd]

compiler-rt/lib/builtins/comp_assert.h

20 ↗

(On Diff #33016)

Er, yes, int_util.h. That was just a slip up on my part. The *use* of the macro in your case is target dependent, nothing about the macro is target dependent though. There is a set of macros that we use pervasively though out the builtins, which are currently consolidated, and this would be the odd one out.

[chh]

Move the macro COMPILE_TIME_ASSERT to int_util.h and change it to a typedef.

[chh]

I think all suggested changes were made.
Please let me know if there is any other required change or is it ready to submit.
Thanks.

compiler-rt/lib/builtins/comp_assert.h

20 ↗

(On Diff #33016)

Okay, I am moving the macro to int_util.h and also making it a typedef as suggested by Joerge.

[joerg]

compiler-rt/lib/builtins/int_util.h

31

More like:

#define COMPILE_TIME_ASSERT0(pred,cnt) typedef char dummy#cnt[(pred) ? 1 : -1]
#define COMPILE_TIME_ASSERT(pred) COMPILE_TIME_ASSERT0(pred,LINE)

or so.

[chh]

compiler-rt/lib/builtins/int_util.h

31

I think what you want is dummy##cnt to add line number to each dummy typedef.
However, above macros were expanded to dummy__LINE__, and I got multiple definition errors.

A trick to get cpp do the right thing is:

#define COMPILE_TIME_ASSERT(expr)    typedef char UNIQUE_NAME[(expr) ? 1 : -1] __attribute__((unused))
#define UNIQUE_NAME                     MAKE_NAME(__LINE__)
#define MAKE_NAME(line)                 MAKE_NAME2(line)
#define MAKE_NAME2(line)               constraint_ ## line

The __attribute__((unused)) is still necessary to avoid unused typedef warnings.

Would you rather to have that complicated macros?

My current definition should give line number on error and also avoid multiple definition errors.

[joerg]

That's why I said "or so" :) The attribute unused is fine, but your version doesn't work in file scope, which is where I normally would place compile time asserts.

[chh]

Make COMPILER_ASSERT work at also the file scope.
Use COUNTER instead of LINE to be unique in a compilation unit.

[compnerd]

compiler-rt/lib/builtins/CMakeLists.txt

44

Please don't add this to GENERIC_SOURCES. This is really not applicable to all targets. It uses pthread, so it can't be used on say Windows.

This makes me wonder if this actually belongs in the compiler builtins in the first place.

compiler-rt/lib/builtins/emutls.c

47

Can you also pull out the alignment math into a macro or an inline function please?

80

Cant this be written more simply as

(align & (align - 1) == 0)

109

Remove the unnecessary braces here.

[danalbert]

compiler-rt/lib/builtins/CMakeLists.txt

44

GCC keeps it in libgcc, and it's a function that's only ever emitted by the compiler as a replacement for __thread. Seems like this is the right place to me. A windows equivalent could be implemented as well, but perhaps it's best to just wrap all this in an #if !defined(_WIN32) for now.

[danalbert]

compiler-rt/lib/builtins/emutls.c

109

Bodies that aren't a one-liner should have braces.

[chh]

Changes with compnerd's and danalbert's suggestions.

[chh]

PTAL new diff 7. Thanks.

compiler-rt/lib/builtins/CMakeLists.txt

44

I will exclude it from WIN32 as danalbert suggested.

compiler-rt/lib/builtins/emutls.c

80

Done, use if ((align & (align - 1)) != 0) abort();

109

I think you meant that line 106 does not need brace and line 105 needs brace. Fixed it.

[compnerd]

LG with the one comment about the growth function.

compiler-rt/lib/builtins/emutls.c

152

If you are trying to round up to 16, shouldn't this be more like:

(index + 16 - 1) & ~(16 - 1)

Which would be ideal as an inline function:

inline size_t align_up(size_t value, unsigned alignment) {
  return (value + alignment - 1) & ~(size_t)(alignment - 1);
}

[chh]

compiler-rt/lib/builtins/emutls.c

152

It's trickier than that as we try to be compatible with gcc's structure of emutls_address_arrary. It has a 'data' array plus an extra pointer. So, here we want to round up (index + 1) to 16, but returns the new size of 'data' array.

compiler-rt/lib/builtins/CMakeLists.txt

   divti3.c
   divtf3.c
   divxc3.c
+  emutls.c
   enable_execute_stack.c
   eprintf.c
   extendsfdf2.c

compiler-rt/lib/builtins/README.txt

 // for use with some implementations of assert() in <assert.h>
 void __eprintf(const char* format, const char* assertion_expression,
         const char* line, const char* file);
-        
 
+// for systems with emulated thread local storage
+void* __emutls_get_address(struct __emutls_control*);
 
+
 //   Power PC specific functions
 
 // There is no C interface to the saveFP/restFP functions.  They are helper

compiler-rt/lib/builtins/emutls.c

+/* ===---------- emutls.c - Implements __emutls_get_address ---------------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+#include <pthread.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "int_util.h"
+
+/* Default is not to use posix_memalign, so systems like Android
+ * can use thread local data without heavier POSIX memory allocators.
+ */
+#ifndef EMUTLS_USE_POSIX_MEMALIGN
+#define EMUTLS_USE_POSIX_MEMALIGN 0
+#endif
+
+/* For every TLS variable xyz,
+ * there is one __emutls_control variable named __emutls_v.xyz.
+ * If xyz has non-zero initial value, __emutls_v.xyz's "value"
+ * will point to __emutls_t.xyz, which has the initial value.
+ */
+typedef struct __emutls_control {
+    size_t size;  /* size of the object in bytes */
+    size_t align;  /* alignment of the object in bytes */
+    union {
+        uintptr_t index;  /* data[index-1] is the object address */
+        void* address;  /* object address, when in single thread env */
+    } object;
+    void* value;  /* null or non-zero initial value for the object */
+} __emutls_control;
+
+static inline void* emutls_memalign_alloc(size_t align, size_t size) {
+    void *base;
+#if EMUTLS_USE_POSIX_MEMALIGN
+    if (posix_memalign(&base, align, size) != 0)
+        abort();
+#else
+    /* Allocate (align - 1 + sizeof(void*) + size) bytes. */
+    char* object;
+    if ((object = malloc(align - 1 + sizeof(void*) + size)) == NULL)
+        abort();
+    base = (void*)(((uintptr_t)(object + sizeof(void*) + align - 1))
+                    & ~(uintptr_t)(align - 1));
+
+    ((void**)base)[-1] = object;
+#endif
+    return base;
+}
+
+static inline void emutls_memalign_free(void* base) {
+#if EMUTLS_USE_POSIX_MEMALIGN
+    free(base);
+#else
+    /* The mallocated address is in ((void**)base)[-1] */
+    free(((void**)base)[-1]);
+#endif
+}
+
+/* Emulated TLS objects are always allocated at run-time. */
+static inline void* emutls_allocate_object(__emutls_control* control) {
+    /* Use standard C types, check with gcc's emutls.o. */
+    typedef unsigned int gcc_word __attribute__((mode(word)));
+    typedef unsigned int gcc_pointer __attribute__((mode(pointer)));
+    COMPILE_TIME_ASSERT(sizeof(size_t) == sizeof(gcc_word));
+    COMPILE_TIME_ASSERT(sizeof(uintptr_t) == sizeof(gcc_pointer));
+    COMPILE_TIME_ASSERT(sizeof(uintptr_t) == sizeof(void*));
+
+    size_t size = control->size;
+    size_t align = control->align;
+    if (align < sizeof(void*))
+        align = sizeof(void*);
+    /* Make sure that align is power of 2. */
+    if ((((align - 1) | align) + 1) != (align << 1))
+        abort();
+
+    void* base = emutls_memalign_alloc(align, size);
+    if (control->value)
+        memcpy(base, control->value, size);
+    else
+        memset(base, 0, size);
+    return base;
+}
+
+static pthread_mutex_t emutls_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+static size_t emutls_num_object = 0;  /* number of allocated TLS objects */
+
+typedef struct emutls_address_array {
+    uintptr_t size;  /* number of elements in the 'data' array */
+    void* data[];
+} emutls_address_array;
+
+static pthread_key_t emutls_pthread_key;
+
+static void emutls_key_destructor(void* ptr) {
+    emutls_address_array* array = (emutls_address_array*)ptr;
+    uintptr_t i;
+    for (i = 0; i < array->size; ++i) {
+        if (array->data[i]) {
+            emutls_memalign_free(array->data[i]);
+        }
+    }
+    free(ptr);
+}
+
+static void emutls_init(void) {
+    if (pthread_key_create(&emutls_pthread_key, emutls_key_destructor) != 0)
+        abort();
+}
+
+/* Returns control->object.index; set index if not allocated yet. */
+static inline uintptr_t emutls_get_index(__emutls_control* control) {
+    uintptr_t index = __atomic_load_n(&control->object.index, __ATOMIC_ACQUIRE);
+    if (!index) {
+        static pthread_once_t once = PTHREAD_ONCE_INIT;
+        pthread_once(&once, emutls_init);
+        pthread_mutex_lock(&emutls_mutex);
+        index = control->object.index;
+        if (!index) {
+            index = ++emutls_num_object;
+            __atomic_store_n(&control->object.index, index, __ATOMIC_RELEASE);
+        }
+        pthread_mutex_unlock(&emutls_mutex);
+    }
+    return index;
+}
+
+/* Updates newly allocated thread local emutls_address_array. */
+static inline void emutls_check_array_set_size(emutls_address_array* array,
+                                               uintptr_t size) {
+    if (array == NULL)
+        abort();
+    array->size = size;
+    pthread_setspecific(emutls_pthread_key, (void*)array);
+}
+
+/* Returns the new 'data' array size, number of elements,
+ * which must be no smaller than the given index.
+ */
+static inline uintptr_t emutls_new_data_array_size(uintptr_t index) {
+   /* Need to allocate emutls_address_array with one extra slot
+    * to store the data array size.
+    * Round up the emutls_address_array size to multiple of 16.
+    */
+    return ((index + 1 + 15) & ~((uintptr_t)15)) - 1;
+}
+
+/* Returns the thread local emutls_address_array.
+ * Extends its size if necessary to hold address at index.
+ */
+static inline emutls_address_array* emutls_get_address_array(uintptr_t index) {
+    emutls_address_array* array = pthread_getspecific(emutls_pthread_key);
+    if (array == NULL) {
+        uintptr_t new_size = emutls_new_data_array_size(index);
+        array = calloc(new_size + 1, sizeof(void*));
+        emutls_check_array_set_size(array, new_size);
+    } else if (index > array->size) {
+        uintptr_t orig_size = array->size;
+        uintptr_t new_size = emutls_new_data_array_size(index);
+        array = realloc(array, (new_size + 1) * sizeof(void*));
+        if (array)
+            memset(array->data + orig_size, 0,
+                   (new_size - orig_size) * sizeof(void*));
+        emutls_check_array_set_size(array, new_size);
+    }
+    return array;
+}
+
+void* __emutls_get_address(__emutls_control* control) {
+    uintptr_t index = emutls_get_index(control);
+    emutls_address_array* array = emutls_get_address_array(index);
+    if (array->data[index - 1] == NULL)
+        array->data[index - 1] = emutls_allocate_object(control);
+    return array->data[index - 1];
+}

compiler-rt/lib/builtins/int_util.h

 void compilerrt_abort_impl(const char *file, int line,
                            const char *function) __attribute__((noreturn));
 
+#define COMPILE_TIME_ASSERT(expr) COMPILE_TIME_ASSERT1(expr, __COUNTER__)
+#define COMPILE_TIME_ASSERT1(expr, cnt) COMPILE_TIME_ASSERT2(expr, cnt)
+#define COMPILE_TIME_ASSERT2(expr, cnt) \
+    typedef char ct_assert_##cnt[(expr) ? 1 : -1] __attribute__((unused))
+
 #endif /* INT_UTIL_H */

compiler-rt/test/builtins/Unit/emutls_test.c

+//===-- emutls_test.c - Test __emutls_get_address ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file tests __emutls_get_address for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef unsigned int gcc_word __attribute__((mode(word)));
+typedef unsigned int gcc_pointer __attribute__((mode(pointer)));
+
+struct gcc_emutls_object {  // for libgcc
+    gcc_word size;
+    gcc_word align;
+    union {
+        gcc_pointer offset;
+        void *ptr;
+    } loc;
+    void *templ;
+};
+
+typedef struct __emutls_control {  // for clang/llvm
+    size_t size;
+    size_t align;
+    union {
+        uintptr_t index;
+        void* address;
+    } object;
+    void* value;
+} __emutls_control;
+
+void* __emutls_get_address(__emutls_control*);
+
+#define COMPILE_TIME_ASSERT(pred) { \
+    char dummy[(pred) ? 0 : -1] __attribute__((unused)); \
+}
+
+#define ASSERT_TRUE(v) { \
+    if (!(v)) { \
+        printf("%s:%d: error in emutls expect true: (%s)\n", \
+               __FILE__, __LINE__, #v); \
+        return 1; \
+    } \
+}
+
+#define ASSERT_EQ(v1, v2) { \
+    if ((v1) != (v2)) { \
+        printf("%s:%d: error in emutls test: (%s) != (%s)\n", \
+               __FILE__, __LINE__, #v1, #v2); \
+        return 1; \
+    } \
+}
+
+#define ASSERT_STREQ(v1, v2) { \
+    if (strcmp((v1), (v2))) { \
+        printf("%s:%d: error in emutls test: " \
+               "string %s (\"%s\") != %s (\"%s\")\n", \
+               __FILE__, __LINE__, #v1, (v1), #v2, (v2)); \
+        return 1; \
+    } \
+}
+
+int test__type_size ()
+{
+    COMPILE_TIME_ASSERT(sizeof(size_t) == sizeof(gcc_word));
+    COMPILE_TIME_ASSERT(sizeof(uintptr_t) == sizeof(gcc_pointer));
+    COMPILE_TIME_ASSERT(sizeof(uintptr_t) == sizeof(void*));
+    COMPILE_TIME_ASSERT(
+        sizeof(__emutls_control) == sizeof(struct gcc_emutls_object));
+    return 0;
+}
+
+int test__init_align()
+{
+    const char* tls_value1 = "123456789";
+    const char* tls_value2 = "abcdefghi";
+    const int num_saved_values = 10;
+    __emutls_control tls_var[num_saved_values];
+    void* saved_gap[num_saved_values];
+    void* saved_p[num_saved_values];
+    size_t prev_index = 0;
+    int n = 0;
+
+    ASSERT_TRUE(strlen(tls_value2) <= strlen(tls_value1));
+
+    __emutls_control c = {strlen(tls_value1) + 1, 1, {0}, (void*)tls_value1};
+    for (n = 0; n < num_saved_values; n++) {
+        memcpy(&tls_var[n], &c, sizeof(c));
+        tls_var[n].align = (1 << n);
+    }
+
+    for (n = 0; n < num_saved_values; n++) {
+        saved_gap[n] = malloc(1);
+        void* p = __emutls_get_address(&tls_var[n]);
+        saved_p[n] = p;
+        ASSERT_TRUE(p != NULL);
+        ASSERT_TRUE(tls_var[n].object.index != 0);
+        // check if p is a new object.
+        if (n > 0) {
+            // In single-thread environment, object.address == p.
+            // In multi-threads environment, object.index is increased.
+            ASSERT_TRUE(prev_index + 1 == tls_var[n].object.index ||
+                        p == tls_var[n].object.address);
+        }
+        prev_index = tls_var[n].object.index;
+        // check if p is aligned
+        uintptr_t align = (1 << n);
+        ASSERT_EQ(((uintptr_t)p & ~(align - 1)), (uintptr_t)p);
+        // check if *p is initialized
+        ASSERT_STREQ(tls_value1, (char*)p);
+        memcpy(p, (void*)tls_value2, strlen(tls_value2) + 1);
+    }
+
+    for (n = 0; n < num_saved_values; n++) {
+        free(saved_gap[n]);
+    }
+    for (n = 0; n < num_saved_values; n++) {
+        void* p = __emutls_get_address(&tls_var[n]);
+        ASSERT_EQ(p, saved_p[n]);
+        // check if *p has the new value
+        ASSERT_STREQ(tls_value2, (char*)p);
+    }
+}
+
+int main()
+{
+    if (test__type_size())
+        return 1;
+    if (test__init_align())
+        return 1;
+    return 0;
+}