[PATCH 1/7] introduce time managment in xtf

[PATCH 1/7] introduce time managment in xtf

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

this file is introduce to be able to implement an inter domain
communication protocol over xenstore. For synchronization purpose, we do
really want to be able to "control" time

common/time.c: since_boot_time gets the time in nanoseconds from the
moment the VM has booted

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786223
---
 build/files.mk     |  1 +
 common/time.c      | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 include/xtf/time.h | 35 ++++++++++++++++++++++
 3 files changed, 123 insertions(+)
 create mode 100644 common/time.c
 create mode 100644 include/xtf/time.h

diff --git a/build/files.mk b/build/files.mk
index 46b42d6..55ed1ca 100644
--- a/build/files.mk
+++ b/build/files.mk
@@ -16,6 +16,7 @@ obj-perarch += $(ROOT)/common/libc/vsnprintf.o
 obj-perarch += $(ROOT)/common/report.o
 obj-perarch += $(ROOT)/common/setup.o
 obj-perarch += $(ROOT)/common/xenbus.o
+obj-perarch += $(ROOT)/common/time.o
 
 obj-perenv += $(ROOT)/arch/x86/decode.o
 obj-perenv += $(ROOT)/arch/x86/desc.o
diff --git a/common/time.c b/common/time.c
new file mode 100644
index 0000000..11ac168
--- /dev/null
+++ b/common/time.c
@@ -0,0 +1,87 @@
+#include <xtf/types.h>
+#include <xtf/traps.h>
+#include <xtf/time.h>
+
+/* This function was taken from mini-os source code */
+/* It returns ((delta << shift) * mul_frac) >> 32 */
+static inline uint64_t scale_delta(uint64_t delta, uint32_t mul_frac, int shift)
+{
+    uint64_t product;
+#ifdef __i386__
+    uint32_t tmp1, tmp2;
+#endif
+
+    if ( shift < 0 )
+        delta >>= -shift;
+    else
+        delta <<= shift;
+
+#ifdef __i386__
+    __asm__ (
+            "mul  %5       ; "
+            "mov  %4,%%eax ; "
+            "mov  %%edx,%4 ; "
+            "mul  %5       ; "
+            "add  %4,%%eax ; "
+            "xor  %5,%5    ; "
+            "adc  %5,%%edx ; "
+            : "=A" (product), "=r" (tmp1), "=r" (tmp2)
+            : "a" ((uint32_t)delta), "1" ((uint32_t)(delta >> 32)), "2" (mul_frac) );
+#else
+    __asm__ (
+            "mul %%rdx ; shrd $32,%%rdx,%%rax"
+            : "=a" (product) : "0" (delta), "d" ((uint64_t)mul_frac) );
+#endif
+
+    return product;
+}
+
+
+#if defined(__i386__)
+uint32_t since_boot_time(void)
+#else
+uint64_t since_boot_time(void)
+#endif
+{
+    uint64_t tsc;
+    uint32_t version, wc_version;
+#if defined(__i386__)
+    uint32_t system_time;
+#else
+    uint64_t system_time;
+#endif
+    uint64_t old_tsc;
+
+    do
+    {
+        do
+        {
+            wc_version = shared_info.wc_version ;
+            version = shared_info.vcpu_info[0].time.version;
+        } while ( (version & 1) == 1 || (wc_version & 1) == 1);
+
+        system_time = shared_info.vcpu_info[0].time.system_time;
+        old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
+    } while (
+            version != shared_info.vcpu_info[0].time.version ||
+            wc_version != shared_info.wc_version
+            );
+
+    rdtscp(tsc);
+
+    system_time += scale_delta(tsc - old_tsc,
+                               shared_info.vcpu_info[0].time.tsc_to_system_mul,
+                               shared_info.vcpu_info[0].time.tsc_shift);
+
+    return system_time;
+}
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * tab-width: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
diff --git a/include/xtf/time.h b/include/xtf/time.h
new file mode 100644
index 0000000..15cbd48
--- /dev/null
+++ b/include/xtf/time.h
@@ -0,0 +1,35 @@
+/**
+ * @file include/xtf/time.h
+ *
+ * Time management
+ */
+#ifndef XTF_TIME_H
+# define XTF_TIME_H
+
+#include <xtf/types.h>
+
+#define rdtscp(tsc) {\
+    uint32_t lo, hi;\
+    __asm__ volatile("rdtsc": "=a"(lo), "=d"(hi));\
+    tsc = ((uint64_t)hi << 32) | lo;\
+}
+
+
+#if defined(__i386__)
+/* Time from boot in nanoseconds */
+uint32_t since_boot_time(void);
+#else
+uint64_t since_boot_time(void);
+#endif
+
+#endif /* XTF_TIME_H */
+
+/*
+ * Local variables:
+ * mode: C
+ * c-file-style: "BSD"
+ * c-basic-offset: 4
+ * tab-width: 4
+ * indent-tabs-mode: nil
+ * End:
+ */
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 2/7] add current_time function to time manager

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

this function returns the "epoch" time

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786224
---
 common/time.c      | 16 ++++++++++++++++
 include/xtf/time.h |  4 ++++
 2 files changed, 20 insertions(+)

diff --git a/common/time.c b/common/time.c
index 11ac168..37a9faf 100644
--- a/common/time.c
+++ b/common/time.c
@@ -76,6 +76,22 @@ uint64_t since_boot_time(void)
     return system_time;
 }
 
+/* This function return the epoch time (number of seconds elapsed
+ * since Juanary 1, 1970) */
+#if defined(__i386__)
+uint32_t current_time(void)
+#else
+uint64_t current_time(void)
+#endif
+{
+#if defined(__i386__)
+    uint32_t seconds = shared_info.wc_sec;
+#else
+    uint64_t seconds = ((uint64_t)shared_info.wc_sec_hi << 32) | shared_info.wc_sec;
+#endif
+    return seconds + (since_boot_time() / 1000000000);
+}
+
 /*
  * Local variables:
  * mode: C
diff --git a/include/xtf/time.h b/include/xtf/time.h
index 15cbd48..a8c10eb 100644
--- a/include/xtf/time.h
+++ b/include/xtf/time.h
@@ -18,8 +18,12 @@
 #if defined(__i386__)
 /* Time from boot in nanoseconds */
 uint32_t since_boot_time(void);
+
+uint32_t current_time(void);
 #else
 uint64_t since_boot_time(void);
+
+uint64_t current_time(void);
 #endif
 
 #endif /* XTF_TIME_H */
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 3/7] add gettimeofday function to time managment

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786225
---
 common/time.c      | 14 ++++++++++++++
 include/xtf/time.h | 12 ++++++++++++
 2 files changed, 26 insertions(+)

diff --git a/common/time.c b/common/time.c
index 37a9faf..c80bc11 100644
--- a/common/time.c
+++ b/common/time.c
@@ -92,6 +92,20 @@ uint64_t current_time(void)
     return seconds + (since_boot_time() / 1000000000);
 }
 
+/* The POSIX gettimeofday syscall normally takes a second argument, which is
+ * the timezone (struct timezone). However, it sould be NULL because linux
+ * doesn't use it anymore. So we need for us to add it in this function
+ */
+int gettimeofday(struct timeval *tp)
+{
+    if (!tp)
+        return -1;
+
+    tp->sec = current_time();
+    tp->nsec = shared_info.wc_nsec + (since_boot_time() % 1000000000);
+    return 0;
+}
+
 /*
  * Local variables:
  * mode: C
diff --git a/include/xtf/time.h b/include/xtf/time.h
index a8c10eb..16356eb 100644
--- a/include/xtf/time.h
+++ b/include/xtf/time.h
@@ -8,6 +8,16 @@
 
 #include <xtf/types.h>
 
+struct timeval {
+#if !defined(__i386__)
+    uint64_t sec;
+    uint64_t nsec;
+#else
+    uint32_t sec;
+    uint32_t nsec;
+#endif
+};
+
 #define rdtscp(tsc) {\
     uint32_t lo, hi;\
     __asm__ volatile("rdtsc": "=a"(lo), "=d"(hi));\
@@ -26,6 +36,8 @@ uint64_t since_boot_time(void);
 uint64_t current_time(void);
 #endif
 
+int gettimeofday(struct timeval *tp);
+
 #endif /* XTF_TIME_H */
 
 /*
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 4/7] add nspin_sleep function to time manager

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-836539
---
 common/time.c | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/common/time.c b/common/time.c
index c80bc11..db28d78 100644
--- a/common/time.c
+++ b/common/time.c
@@ -106,6 +106,24 @@ int gettimeofday(struct timeval *tp)
     return 0;
 }
 
+#if defined(__i386__)
+static inline void nspin_sleep(uint32_t t)
+#else
+static inline void nspin_sleep(uint64_t t)
+#endif
+{
+#if defined(__i386__)
+    uint32_t curr = since_boot_time();
+    uint32_t end = curr + t;
+#else
+    uint64_t curr = since_boot_time();
+    uint64_t end = curr + t;
+#endif
+
+    while ( curr < end )
+        curr = since_boot_time();
+}
+
 /*
  * Local variables:
  * mode: C
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 5/7] add spin_sleep function to time manager

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786226
---
 common/time.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/common/time.c b/common/time.c
index db28d78..6aa1648 100644
--- a/common/time.c
+++ b/common/time.c
@@ -124,6 +124,20 @@ static inline void nspin_sleep(uint64_t t)
         curr = since_boot_time();
 }
 
+#if defined(__i386__)
+static inline void spin_sleep(uint32_t t)
+#else
+static inline void spin_sleep(uint64_t t)
+#endif
+{
+#if defined(__i386__)
+    uint32_t nsec = t * 1000000000;
+#else
+    uint64_t nsec = t * 1000000000ul;
+#endif
+    nspin_sleep(nsec);
+}
+
 /*
  * Local variables:
  * mode: C
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 6/7] add mspin_sleep function to time manager

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786227
---
 common/time.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/common/time.c b/common/time.c
index 6aa1648..7577694 100644
--- a/common/time.c
+++ b/common/time.c
@@ -138,6 +138,20 @@ static inline void spin_sleep(uint64_t t)
     nspin_sleep(nsec);
 }
 
+#if defined(__i386__)
+static inline void mspin_sleep(uint32_t t)
+#else
+static inline void mspin_sleep(uint64_t t)
+#endif
+{
+#if defined(__i386__)
+    uint32_t nsec = t * 1000000;
+#else
+    uint64_t nsec = t * 1000000ul;
+#endif
+    nspin_sleep(nsec);
+}
+
 /*
  * Local variables:
  * mode: C
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

[PATCH 7/7] add sleep, msleep and NOW() macros to time manager

[Pawel Wieczorkiewicz]

From: Paul Semel <phentex@amazon.de>

Signed-off-by: Paul Semel <phentex@amazon.de>

cr https://code.amazon.com/reviews/CR-786228
---
 common/time.c      | 18 ++++++++++++++++++
 include/xtf/time.h | 16 ++++++++++++++++
 2 files changed, 34 insertions(+)

diff --git a/common/time.c b/common/time.c
index 7577694..2bd4e7f 100644
--- a/common/time.c
+++ b/common/time.c
@@ -152,6 +152,24 @@ static inline void mspin_sleep(uint64_t t)
     nspin_sleep(nsec);
 }
 
+#if defined(__i386__)
+void sleep(uint32_t t)
+#else
+void sleep(uint64_t t)
+#endif
+{
+    spin_sleep(t);
+}
+
+#if defined(__i386__)
+void msleep(uint32_t t)
+#else
+void msleep(uint64_t t)
+#endif
+{
+    mspin_sleep(t);
+}
+
 /*
  * Local variables:
  * mode: C
diff --git a/include/xtf/time.h b/include/xtf/time.h
index 16356eb..252263a 100644
--- a/include/xtf/time.h
+++ b/include/xtf/time.h
@@ -30,14 +30,30 @@ struct timeval {
 uint32_t since_boot_time(void);
 
 uint32_t current_time(void);
+
+/* This function takes seconds in parameter */
+void sleep(uint32_t f);
+
+/* Be careful, this function takes milliseconds in parameter,
+ * not microseconds !
+ */
+void msleep(uint32_t f);
 #else
 uint64_t since_boot_time(void);
 
 uint64_t current_time(void);
+
+void sleep(uint64_t f);
+
+void msleep(uint64_t f);
 #endif
 
 int gettimeofday(struct timeval *tp);
 
+
+/* This returns the current epoch time */
+#define NOW() current_time()
+
 #endif /* XTF_TIME_H */
 
 /*
-- 
2.16.2

Amazon Development Center Germany GmbH
Berlin - Dresden - Aachen
main office: Krausenstr. 38, 10117 Berlin
Geschaeftsfuehrer: Dr. Ralf Herbrich, Christian Schlaeger
Ust-ID: DE289237879
Eingetragen am Amtsgericht Charlottenburg HRB 149173 B


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 1/7] introduce time managment in xtf

[Paul Semel]

On 04/07/2018 10:39 PM, Andrew Cooper wrot>>>>> However, both of your 
patches have (different) barrier issues, and
>>>>> different (mis)uses of the shared memory clocks, which will need to be
>>>>> addressed. One general comment for the full series is to not bother
>>>>> trying to make time 32bits in a 32bit build.  XTF is an entirely
>>>>> self-contained binary, and I don't much care for legacy behaviours for
>>>>> legacy sake.
>>>>>
>>>>
>>
>> Alright, so I took a look at all of this. So, if I understood it well,
>> you want me to drop all the `uint32_t` part to only have 64 bits.
>> But are you sure that it works the same on 32bits architecture ?
> 
> At the end of the day, all you are passing is units of nanoseconds of
> larger.  The parameter passing won't be identical between 32 or 64bit
> builds, but everything else will be fine.
> 
>>
>> Also, I have another question. I don't see any place where I have
>> memory barrier issues, but I am certainely missing something. Can you
>> elaborate on this one ?
> 
> Your code does:
> 
>> +    do
>> +    {
>> +        do
>> +        {
>> +            wc_version = shared_info.wc_version ;
>> +            version = shared_info.vcpu_info[0].time.version;
>> +        } while ( (version & 1) == 1 || (wc_version & 1) == 1);
>> +
>> +        system_time = shared_info.vcpu_info[0].time.system_time;
>> +        old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>> +    } while (
>> +            version != shared_info.vcpu_info[0].time.version ||
>> +            wc_version != shared_info.wc_version
>> +            );
> 
> First of all, I'm not sure why you are looking at wc_version.  You are
> only reading data out of shared_info.vcpu_info[0].time so you should
> only need to check time.version
> 
> That said, it is critical to force two things:
> 1) The first read of version is strictly before
> system_time/tsc_timestamp, and the second read is afterwards.
> 2) That the compiler can't optimise the code by making repeated reads of
> shared memory.
> 
> 1 is a correctness issue and C, whose memory model is that there are no
> unknown updates to memory, sees that it hasn't written to time.version,
> and therefore can optimises the entire outer do loop to a single iteration.
> 
> 2 is a security issue and we've had many XSAs in the past.  The worst
> example IIRC was a compiler which managed to use a jump table, using a
> 32bit integer index read from shared memory.  When using shared memory,
> it is critical to force the compiler to read a value and stash it
> locally (either in a live register, or on the stack), then audit its
> value, then act upon the value.
> 
> This way, no optimisation the compiler can make code which will result
> in a repeated read of memory, where a malicious advisory could change
> the value between reads.
> 
> 1 strictly needs memory barriers to make work, and in this case
> smp_rmb().  Things tend to work on x86 because of the fairly restricted
> memory model, but architectures such as ARM with weaker memory models
> typically tends to explode in funny ways.
> 
> 2 could be fixed with ACCESS_ONCE() to explicitly tell the compiler that
> this is a volatile access and the value in memory may no longer be the same.
> 
> A sample (which I think is correct, but you never quite know for sure
> with barriers!) is:
> 
>>      do {
>>          uint32_t ver1, ver2;
>>
>>          do {
>>              ver1 = shared_info.vcpu_info[0].time.version;
>>              smp_rmb();
>>          } while ( (ver1 & 1) == 1 );
>>
>>          system_time = shared_info.vcpu_info[0].time.system_time;
>>          old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>>          smp_rmb();
>>          ver2 = shared_info.vcpu_info[0].time.version;
>>          smp_rmb();
>>
>>      } while ( ver1 != ver2 );
> 
> The smp_rmb() are full CPU memory barriers (enforcing the ordering of
> reads even from remote cores), and compiler barriers (preventing the
> compiler from reodering memory accesses across the barrier).
> 
> Therefore, ver1 and ver2 are forced to be kept in registers, or spilled
> onto the stack.
> 
> ~Andrew
> 

Thank you very much for replying ! I completely missed this function, I 
do really apologize about it !

Effectively, there is serious issues here. As far as I can remember, I 
inspired myself by another OS code to write this function (as I didn't 
know really much how the time thing was working in Xen).

Thanks for writing this piece of code, I think I will use it and add 
some ACCESS_ONCE on my reads of the different variables in the shared 
memory (version, system_time etc..).

Anyway, I already got rid of the 32 bits part, so that even 32 bits 
architectures are using 64 bits integer (by making sure to use the 
`divmod64` function 🙂) for the division and modulos.

I will change this part of the code this night or maybe tomorrow and 
send you another version of the patch !

-- 
Paul

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 1/7] introduce time managment in xtf

[Paul Semel]

On 04/07/2018 10:58 PM, Paul Semel wrote:
> On 04/07/2018 10:39 PM, Andrew Cooper wrot>>>>> However, both of your patches 
> have (different) barrier issues, and
>>>>>> different (mis)uses of the shared memory clocks, which will need to be
>>>>>> addressed. One general comment for the full series is to not bother
>>>>>> trying to make time 32bits in a 32bit build.  XTF is an entirely
>>>>>> self-contained binary, and I don't much care for legacy behaviours for
>>>>>> legacy sake.
>>>>>>
>>>>>
>>>
>>> Alright, so I took a look at all of this. So, if I understood it well,
>>> you want me to drop all the `uint32_t` part to only have 64 bits.
>>> But are you sure that it works the same on 32bits architecture ?
>>
>> At the end of the day, all you are passing is units of nanoseconds of
>> larger.  The parameter passing won't be identical between 32 or 64bit
>> builds, but everything else will be fine.
>>
>>>
>>> Also, I have another question. I don't see any place where I have
>>> memory barrier issues, but I am certainely missing something. Can you
>>> elaborate on this one ?
>>
>> Your code does:
>>
>>> +    do
>>> +    {
>>> +        do
>>> +        {
>>> +            wc_version = shared_info.wc_version ;
>>> +            version = shared_info.vcpu_info[0].time.version;
>>> +        } while ( (version & 1) == 1 || (wc_version & 1) == 1);
>>> +
>>> +        system_time = shared_info.vcpu_info[0].time.system_time;
>>> +        old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>>> +    } while (
>>> +            version != shared_info.vcpu_info[0].time.version ||
>>> +            wc_version != shared_info.wc_version
>>> +            );
>>
>> First of all, I'm not sure why you are looking at wc_version.  You are
>> only reading data out of shared_info.vcpu_info[0].time so you should
>> only need to check time.version
>>
>> That said, it is critical to force two things:
>> 1) The first read of version is strictly before
>> system_time/tsc_timestamp, and the second read is afterwards.
>> 2) That the compiler can't optimise the code by making repeated reads of
>> shared memory.
>>
>> 1 is a correctness issue and C, whose memory model is that there are no
>> unknown updates to memory, sees that it hasn't written to time.version,
>> and therefore can optimises the entire outer do loop to a single iteration.
>>
>> 2 is a security issue and we've had many XSAs in the past.  The worst
>> example IIRC was a compiler which managed to use a jump table, using a
>> 32bit integer index read from shared memory.  When using shared memory,
>> it is critical to force the compiler to read a value and stash it
>> locally (either in a live register, or on the stack), then audit its
>> value, then act upon the value.
>>
>> This way, no optimisation the compiler can make code which will result
>> in a repeated read of memory, where a malicious advisory could change
>> the value between reads.
>>
>> 1 strictly needs memory barriers to make work, and in this case
>> smp_rmb().  Things tend to work on x86 because of the fairly restricted
>> memory model, but architectures such as ARM with weaker memory models
>> typically tends to explode in funny ways.
>>
>> 2 could be fixed with ACCESS_ONCE() to explicitly tell the compiler that
>> this is a volatile access and the value in memory may no longer be the same.
>>
>> A sample (which I think is correct, but you never quite know for sure
>> with barriers!) is:
>>
>>>      do {
>>>          uint32_t ver1, ver2;
>>>
>>>          do {
>>>              ver1 = shared_info.vcpu_info[0].time.version;
>>>              smp_rmb();
>>>          } while ( (ver1 & 1) == 1 );
>>>
>>>          system_time = shared_info.vcpu_info[0].time.system_time;
>>>          old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>>>          smp_rmb();
>>>          ver2 = shared_info.vcpu_info[0].time.version;
>>>          smp_rmb();
>>>
>>>      } while ( ver1 != ver2 );
>>
>> The smp_rmb() are full CPU memory barriers (enforcing the ordering of
>> reads even from remote cores), and compiler barriers (preventing the
>> compiler from reodering memory accesses across the barrier).
>>
>> Therefore, ver1 and ver2 are forced to be kept in registers, or spilled
>> onto the stack.
>>
>> ~Andrew
>>
> 
> Thank you very much for replying ! I completely missed this function, I do 
> really apologize about it !
> 
> Effectively, there is serious issues here. As far as I can remember, I inspired 
> myself by another OS code to write this function (as I didn't know really much 
> how the time thing was working in Xen).
> 
> Thanks for writing this piece of code, I think I will use it and add some 
> ACCESS_ONCE on my reads of the different variables in the shared memory 
> (version, system_time etc..).
> 
> Anyway, I already got rid of the 32 bits part, so that even 32 bits 
> architectures are using 64 bits integer (by making sure to use the `divmod64` 
> function 🙂) for the division and modulos.
> 
> I will change this part of the code this night or maybe tomorrow and send you 
> another version of the patch !
> 
So, to be completely secure, I guess we would need some locking mechanisms for 
64 bits shared memory accesses on 32 bits arch. Am I right ?

For the moment, I only used the ACCESS_ONCE mechanism, but that's obviously not 
a "once" access on 32 bits. We have something like this actually :

```asm
         system_time = ACCESS_ONCE(shared_info.vcpu_info[0].time.system_time);
   102699:       8b 35 30 c0 10 00       mov    0x10c030,%esi
   10269f:       8b 3d 34 c0 10 00       mov    0x10c034,%edi
```

Do you think this is acceptable, or do you think we should be more secure than 
this by locking the shared memory ? (which would imply implementing a locking 
mechanism to xtf)

Thanks,

-- 
Paul

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 1/7] introduce time managment in xtf

[Andrew Cooper]

On 08/04/2018 15:00, Paul Semel wrote:
> On 04/07/2018 10:58 PM, Paul Semel wrote:
>> On 04/07/2018 10:39 PM, Andrew Cooper wrot>>>>> However, both of your
>> patches have (different) barrier issues, and
>>>>>>> different (mis)uses of the shared memory clocks, which will need
>>>>>>> to be
>>>>>>> addressed. One general comment for the full series is to not bother
>>>>>>> trying to make time 32bits in a 32bit build.  XTF is an entirely
>>>>>>> self-contained binary, and I don't much care for legacy
>>>>>>> behaviours for
>>>>>>> legacy sake.
>>>>>>>
>>>>>>
>>>>
>>>> Alright, so I took a look at all of this. So, if I understood it well,
>>>> you want me to drop all the `uint32_t` part to only have 64 bits.
>>>> But are you sure that it works the same on 32bits architecture ?
>>>
>>> At the end of the day, all you are passing is units of nanoseconds of
>>> larger.  The parameter passing won't be identical between 32 or 64bit
>>> builds, but everything else will be fine.
>>>
>>>>
>>>> Also, I have another question. I don't see any place where I have
>>>> memory barrier issues, but I am certainely missing something. Can you
>>>> elaborate on this one ?
>>>
>>> Your code does:
>>>
>>>> +    do
>>>> +    {
>>>> +        do
>>>> +        {
>>>> +            wc_version = shared_info.wc_version ;
>>>> +            version = shared_info.vcpu_info[0].time.version;
>>>> +        } while ( (version & 1) == 1 || (wc_version & 1) == 1);
>>>> +
>>>> +        system_time = shared_info.vcpu_info[0].time.system_time;
>>>> +        old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>>>> +    } while (
>>>> +            version != shared_info.vcpu_info[0].time.version ||
>>>> +            wc_version != shared_info.wc_version
>>>> +            );
>>>
>>> First of all, I'm not sure why you are looking at wc_version.  You are
>>> only reading data out of shared_info.vcpu_info[0].time so you should
>>> only need to check time.version
>>>
>>> That said, it is critical to force two things:
>>> 1) The first read of version is strictly before
>>> system_time/tsc_timestamp, and the second read is afterwards.
>>> 2) That the compiler can't optimise the code by making repeated
>>> reads of
>>> shared memory.
>>>
>>> 1 is a correctness issue and C, whose memory model is that there are no
>>> unknown updates to memory, sees that it hasn't written to time.version,
>>> and therefore can optimises the entire outer do loop to a single
>>> iteration.
>>>
>>> 2 is a security issue and we've had many XSAs in the past.  The worst
>>> example IIRC was a compiler which managed to use a jump table, using a
>>> 32bit integer index read from shared memory.  When using shared memory,
>>> it is critical to force the compiler to read a value and stash it
>>> locally (either in a live register, or on the stack), then audit its
>>> value, then act upon the value.
>>>
>>> This way, no optimisation the compiler can make code which will result
>>> in a repeated read of memory, where a malicious advisory could change
>>> the value between reads.
>>>
>>> 1 strictly needs memory barriers to make work, and in this case
>>> smp_rmb().  Things tend to work on x86 because of the fairly restricted
>>> memory model, but architectures such as ARM with weaker memory models
>>> typically tends to explode in funny ways.
>>>
>>> 2 could be fixed with ACCESS_ONCE() to explicitly tell the compiler
>>> that
>>> this is a volatile access and the value in memory may no longer be
>>> the same.
>>>
>>> A sample (which I think is correct, but you never quite know for sure
>>> with barriers!) is:
>>>
>>>>      do {
>>>>          uint32_t ver1, ver2;
>>>>
>>>>          do {
>>>>              ver1 = shared_info.vcpu_info[0].time.version;
>>>>              smp_rmb();
>>>>          } while ( (ver1 & 1) == 1 );
>>>>
>>>>          system_time = shared_info.vcpu_info[0].time.system_time;
>>>>          old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
>>>>          smp_rmb();
>>>>          ver2 = shared_info.vcpu_info[0].time.version;
>>>>          smp_rmb();
>>>>
>>>>      } while ( ver1 != ver2 );
>>>
>>> The smp_rmb() are full CPU memory barriers (enforcing the ordering of
>>> reads even from remote cores), and compiler barriers (preventing the
>>> compiler from reodering memory accesses across the barrier).
>>>
>>> Therefore, ver1 and ver2 are forced to be kept in registers, or spilled
>>> onto the stack.
>>>
>>> ~Andrew
>>>
>>
>> Thank you very much for replying ! I completely missed this function,
>> I do really apologize about it !
>>
>> Effectively, there is serious issues here. As far as I can remember,
>> I inspired myself by another OS code to write this function (as I
>> didn't know really much how the time thing was working in Xen).
>>
>> Thanks for writing this piece of code, I think I will use it and add
>> some ACCESS_ONCE on my reads of the different variables in the shared
>> memory (version, system_time etc..).
>>
>> Anyway, I already got rid of the 32 bits part, so that even 32 bits
>> architectures are using 64 bits integer (by making sure to use the
>> `divmod64` function 🙂) for the division and modulos.
>>
>> I will change this part of the code this night or maybe tomorrow and
>> send you another version of the patch !
>>
> So, to be completely secure, I guess we would need some locking
> mechanisms for 64 bits shared memory accesses on 32 bits arch. Am I
> right ?

That depends.

If you have two mutually untrusted entities, then yes, you have to be
very careful. 

In this case, one half is the hypervisor, and you've got to trust that. 
For example, Xen could leave the version field with the bottom bit set,
and cause us to livelock waiting for it to drop, but that defeats the
purpose of Xen running virtual machines.

Here, the check of the two samples of the version field is sufficient to
determine that we read consistent data, irrespective of whether the
64bit fields were broken down into two 32bit accesses or not.

~Andrew

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 1/7] introduce time managment in xtf

[Roger Pau Monné]

On Wed, Apr 04, 2018 at 03:50:48PM +0000, Pawel Wieczorkiewicz wrote:
> From: Paul Semel <phentex@amazon.de>
> 
> this file is introduce to be able to implement an inter domain
> communication protocol over xenstore. For synchronization purpose, we do
> really want to be able to "control" time
> 
> common/time.c: since_boot_time gets the time in nanoseconds from the
> moment the VM has booted
> 
> Signed-off-by: Paul Semel <phentex@amazon.de>
> 
> cr https://code.amazon.com/reviews/CR-786223

This seems like some Amazon internal tracking, which shouldn't be sent
upstream (the webpage is not even accessible from the outside).

> ---
>  build/files.mk     |  1 +
>  common/time.c      | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  include/xtf/time.h | 35 ++++++++++++++++++++++
>  3 files changed, 123 insertions(+)
>  create mode 100644 common/time.c
>  create mode 100644 include/xtf/time.h
> 
> diff --git a/build/files.mk b/build/files.mk
> index 46b42d6..55ed1ca 100644
> --- a/build/files.mk
> +++ b/build/files.mk
> @@ -16,6 +16,7 @@ obj-perarch += $(ROOT)/common/libc/vsnprintf.o
>  obj-perarch += $(ROOT)/common/report.o
>  obj-perarch += $(ROOT)/common/setup.o
>  obj-perarch += $(ROOT)/common/xenbus.o
> +obj-perarch += $(ROOT)/common/time.o
>  
>  obj-perenv += $(ROOT)/arch/x86/decode.o
>  obj-perenv += $(ROOT)/arch/x86/desc.o
> diff --git a/common/time.c b/common/time.c
> new file mode 100644
> index 0000000..11ac168
> --- /dev/null
> +++ b/common/time.c
> @@ -0,0 +1,87 @@
> +#include <xtf/types.h>
> +#include <xtf/traps.h>
> +#include <xtf/time.h>
> +
> +/* This function was taken from mini-os source code */
> +/* It returns ((delta << shift) * mul_frac) >> 32 */
> +static inline uint64_t scale_delta(uint64_t delta, uint32_t mul_frac, int shift)
> +{
> +    uint64_t product;
> +#ifdef __i386__
> +    uint32_t tmp1, tmp2;
> +#endif
> +
> +    if ( shift < 0 )
> +        delta >>= -shift;
> +    else
> +        delta <<= shift;
> +
> +#ifdef __i386__
> +    __asm__ (
> +            "mul  %5       ; "
> +            "mov  %4,%%eax ; "
> +            "mov  %%edx,%4 ; "
> +            "mul  %5       ; "
> +            "add  %4,%%eax ; "
> +            "xor  %5,%5    ; "
> +            "adc  %5,%%edx ; "
> +            : "=A" (product), "=r" (tmp1), "=r" (tmp2)
> +            : "a" ((uint32_t)delta), "1" ((uint32_t)(delta >> 32)), "2" (mul_frac) );
> +#else
> +    __asm__ (
> +            "mul %%rdx ; shrd $32,%%rdx,%%rax"
> +            : "=a" (product) : "0" (delta), "d" ((uint64_t)mul_frac) );
> +#endif
> +
> +    return product;
> +}
> +
> +
> +#if defined(__i386__)
> +uint32_t since_boot_time(void)
> +#else
> +uint64_t since_boot_time(void)
> +#endif

Why is the return type different for 32 vs 64bits?

I see no reason to not return a 64bit value in both cases IMO, and
that would remove the need for all the ifdefery below.

> +{
> +    uint64_t tsc;
> +    uint32_t version, wc_version;
> +#if defined(__i386__)
> +    uint32_t system_time;
> +#else
> +    uint64_t system_time;
> +#endif
> +    uint64_t old_tsc;
> +
> +    do
> +    {
> +        do
> +        {
> +            wc_version = shared_info.wc_version ;
> +            version = shared_info.vcpu_info[0].time.version;
> +        } while ( (version & 1) == 1 || (wc_version & 1) == 1);
> +
> +        system_time = shared_info.vcpu_info[0].time.system_time;
> +        old_tsc = shared_info.vcpu_info[0].time.tsc_timestamp;
> +    } while (
> +            version != shared_info.vcpu_info[0].time.version ||
> +            wc_version != shared_info.wc_version
> +            );
> +
> +    rdtscp(tsc);
> +
> +    system_time += scale_delta(tsc - old_tsc,
> +                               shared_info.vcpu_info[0].time.tsc_to_system_mul,
> +                               shared_info.vcpu_info[0].time.tsc_shift);

This seems way more complicated that what's actually needed. First of
all you don't need to check wc_version at all if you are only fetching
the vcpu_time_info fields (wc_version is for the wallclock).

Then AFAICT you are also missing the barriers (or using something like
Linux's ACCESS_ONCE):

https://github.com/freebsd/freebsd/blob/master/sys/x86/x86/pvclock.c#L141

> +
> +    return system_time;
> +}
> +
> +/*
> + * Local variables:
> + * mode: C
> + * c-file-style: "BSD"
> + * c-basic-offset: 4
> + * tab-width: 4
> + * indent-tabs-mode: nil
> + * End:
> + */
> diff --git a/include/xtf/time.h b/include/xtf/time.h
> new file mode 100644
> index 0000000..15cbd48
> --- /dev/null
> +++ b/include/xtf/time.h
> @@ -0,0 +1,35 @@
> +/**
> + * @file include/xtf/time.h
> + *
> + * Time management
> + */
> +#ifndef XTF_TIME_H
> +# define XTF_TIME_H
> +
> +#include <xtf/types.h>
> +
> +#define rdtscp(tsc) {\

Why is this called rdtscp when you are actually using rdtsc? (and not
rdtscp?)

> +    uint32_t lo, hi;\
> +    __asm__ volatile("rdtsc": "=a"(lo), "=d"(hi));\
> +    tsc = ((uint64_t)hi << 32) | lo;\

rdtsc is not a serializing instruction, see:

https://marc.info/?l=xen-devel&m=151939254729277

Also this should likely belong in arch/x86/include/arch/lib.h.

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 2/7] add current_time function to time manager

[Roger Pau Monné]

On Wed, Apr 04, 2018 at 03:50:49PM +0000, Pawel Wieczorkiewicz wrote:
> From: Paul Semel <phentex@amazon.de>
> 
> this function returns the "epoch" time
> 
> Signed-off-by: Paul Semel <phentex@amazon.de>
> 
> cr https://code.amazon.com/reviews/CR-786224
> ---
>  common/time.c      | 16 ++++++++++++++++
>  include/xtf/time.h |  4 ++++
>  2 files changed, 20 insertions(+)
> 
> diff --git a/common/time.c b/common/time.c
> index 11ac168..37a9faf 100644
> --- a/common/time.c
> +++ b/common/time.c
> @@ -76,6 +76,22 @@ uint64_t since_boot_time(void)
>      return system_time;
>  }
>  
> +/* This function return the epoch time (number of seconds elapsed
> + * since Juanary 1, 1970) */
> +#if defined(__i386__)
> +uint32_t current_time(void)
> +#else
> +uint64_t current_time(void)
> +#endif
> +{
> +#if defined(__i386__)
> +    uint32_t seconds = shared_info.wc_sec;
> +#else
> +    uint64_t seconds = ((uint64_t)shared_info.wc_sec_hi << 32) | shared_info.wc_sec;
> +#endif
> +    return seconds + (since_boot_time() / 1000000000);

You need barriers and checking wc_version, see:

https://github.com/freebsd/freebsd/blob/master/sys/x86/x86/pvclock.c#L156

And as commented in patch 1, I think you should return a 64bit value
regardless of the bitness of the binary.

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 3/7] add gettimeofday function to time managment

[Roger Pau Monné]

On Wed, Apr 04, 2018 at 03:50:50PM +0000, Pawel Wieczorkiewicz wrote:
> From: Paul Semel <phentex@amazon.de>
> 
> Signed-off-by: Paul Semel <phentex@amazon.de>
> 
> cr https://code.amazon.com/reviews/CR-786225
> ---
>  common/time.c      | 14 ++++++++++++++
>  include/xtf/time.h | 12 ++++++++++++
>  2 files changed, 26 insertions(+)
> 
> diff --git a/common/time.c b/common/time.c
> index 37a9faf..c80bc11 100644
> --- a/common/time.c
> +++ b/common/time.c
> @@ -92,6 +92,20 @@ uint64_t current_time(void)
>      return seconds + (since_boot_time() / 1000000000);
>  }
>  
> +/* The POSIX gettimeofday syscall normally takes a second argument, which is
> + * the timezone (struct timezone). However, it sould be NULL because linux
> + * doesn't use it anymore. So we need for us to add it in this function

IMO it's better to use the POSIX prototype.

I would instead panic if tz != NULL, or return EOPNOTSUPP.

> + */
> +int gettimeofday(struct timeval *tp)
> +{
> +    if (!tp)
> +        return -1;
> +
> +    tp->sec = current_time();
> +    tp->nsec = shared_info.wc_nsec + (since_boot_time() % 1000000000);

Please add a define for 1000000000.

Also, I'm not sure this is accurate.

current_time already calls since_boot_time, so you end up using data
from two different since_boot_time calls in order to fill the timeval
struct, which is wrong (ie: those calls will return different values
which you are mixing).

> +    return 0;
> +}
> +
>  /*
>   * Local variables:
>   * mode: C
> diff --git a/include/xtf/time.h b/include/xtf/time.h
> index a8c10eb..16356eb 100644
> --- a/include/xtf/time.h
> +++ b/include/xtf/time.h
> @@ -8,6 +8,16 @@
>  
>  #include <xtf/types.h>
>  
> +struct timeval {
> +#if !defined(__i386__)
> +    uint64_t sec;
> +    uint64_t nsec;
> +#else
> +    uint32_t sec;
> +    uint32_t nsec;
> +#endif
> +};

Let's have a sane interface from the start and always use 64bit
fields.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 4/7] add nspin_sleep function to time manager

[Roger Pau Monné]

On Wed, Apr 04, 2018 at 03:50:51PM +0000, Pawel Wieczorkiewicz wrote:
> From: Paul Semel <phentex@amazon.de>

Missing commit log?

> Signed-off-by: Paul Semel <phentex@amazon.de>
> 
> cr https://code.amazon.com/reviews/CR-836539
> ---
>  common/time.c | 18 ++++++++++++++++++
>  1 file changed, 18 insertions(+)
> 
> diff --git a/common/time.c b/common/time.c
> index c80bc11..db28d78 100644
> --- a/common/time.c
> +++ b/common/time.c
> @@ -106,6 +106,24 @@ int gettimeofday(struct timeval *tp)
>      return 0;
>  }
>  
> +#if defined(__i386__)
> +static inline void nspin_sleep(uint32_t t)
> +#else
> +static inline void nspin_sleep(uint64_t t)
> +#endif
> +{
> +#if defined(__i386__)
> +    uint32_t curr = since_boot_time();
> +    uint32_t end = curr + t;
> +#else
> +    uint64_t curr = since_boot_time();
> +    uint64_t end = curr + t;
> +#endif

Again same comment as before regarding the 32 vs 64bit types.

You would probably want something like:

if ( end < curr )
    panic("end value overflows counter\n");

> +
> +    while ( curr < end )
> +        curr = since_boot_time();

And you likely want this to be:

while ( end < since_boot_time() )
    asm volatile ("pause");

I'm actually trying to add a "pause" instruction helper in:

https://marc.info/?l=xen-devel&m=152241364510840

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH 5/7] add spin_sleep function to time manager

[Roger Pau Monné]

On Wed, Apr 04, 2018 at 03:50:52PM +0000, Pawel Wieczorkiewicz wrote:
> From: Paul Semel <phentex@amazon.de>

Missing commit log.

> Signed-off-by: Paul Semel <phentex@amazon.de>
> 
> cr https://code.amazon.com/reviews/CR-786226
> ---
>  common/time.c | 14 ++++++++++++++
>  1 file changed, 14 insertions(+)
> 
> diff --git a/common/time.c b/common/time.c
> index db28d78..6aa1648 100644
> --- a/common/time.c
> +++ b/common/time.c
> @@ -124,6 +124,20 @@ static inline void nspin_sleep(uint64_t t)
>          curr = since_boot_time();
>  }
>  
> +#if defined(__i386__)
> +static inline void spin_sleep(uint32_t t)
> +#else
> +static inline void spin_sleep(uint64_t t)
> +#endif
> +{
> +#if defined(__i386__)
> +    uint32_t nsec = t * 1000000000;
> +#else
> +    uint64_t nsec = t * 1000000000ul;

This value should be in a define with a proper name.

Thanks, Roger.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel