Duktape doesn't appear to respect pointer alignment

[davidchisnall]

I'm trying to use DukTape on a very weird architecture[1] which, among other things, has strict pointer alignment requirements. The DUK_HOBJECT_A_GET_VALUE_PTR macro apparently expands to:

(&((duk_tval *) ( ((((obj)))->props) + ((((obj)))->e_size) * (sizeof(duk_hstring *) + sizeof(duk_propvalue) + sizeof(duk_uint8_t)) + ((4 - (((((obj)))->e_size))) & 0x03) ))[(arr_idx)])

For us (with sizeof(void*) == 32), this evaluates to 196, which is not a multiple of 32. Is there an easy change possible to fix this?

[1] Pointers are 256 bits, containing a 64-bit virtual address, base, bounds and permissions. sizeof(void*) is 32. Similarly, sizeof(intptr_t) is 32 and permits arithmetic on the pointer value. Pointers may only be materialised

[svaarala]

That's indeed an interesting platform :) Duktape assumes currently that align by 8 would be sufficient for pointers too. Because memory areas contain a mix of tagged values and pointers, some alignment assumptions are unfortunately necessary (or at least quite difficult to avoid).

I can look into supporting stronger alignment guarantees, I'll have to give it some thought :)

Is there any way (say an emulator) where I could reproduce this?

[davidchisnall]

We have a QEMU port that is almost ready: https://github.com/CTSRD-CHERI/qemu. Currently it requires a lot of assembly, but we should have pre-packaged images available soon. I found the DUK_USE_ALIGN_8 macro, so I can take a look at the places where it might need to be a bit stronger.

[fatcerberus]

Pointers are 256 bits, containing a 64-bit virtual address, base, bounds and permissions.

Wow, I hope this platform has huge amounts of RAM if programs are passing 32-byte pointers (and integers) around everywhere!

Also, encoding permissions in the pointer sounds exploitable...

[svaarala]

@davidchisnall I guess duk_tval will use the unpacked alternative and be 512 bytes to host a tag and a pointer so it would always be properly aligned.

The default is to use DUK_USE_HOBJECT_LAYOUT_2 which is quite portable even with (normal) alignment restrictions. You could perhaps try layout 3 by editing duk_config.h manually: enable DUK_USE_HOBJECT_LAYOUT_3 and disable DUK_USE_HOBJECT_LAYOUT_2. Layout 3 makes less assumptions and would seem to align properly: https://github.com/svaarala/duktape/blob/master/src/duk_hobject.h#L738-L745.

There may be other alignment issues besides the property table though.

[davidchisnall]

Note that we provide a tag bit in hardware that lets us differentiate pointers and non-pointer values (any store from an integer register clears the tag associated with the 32-byte line, giving us unforgeable pointers). This means that we shouldn't need to use a 512-byte representation, if all of the places that test whether a value is a pointer or not are doing it via some macro (we have a compiler builtin that accesses this bit and expands to a single instruction, as well as cheap instructions for branching on it).

[svaarala]

Right, it'd be possible to extend duk_tval to support 256-bit tagged values (I said 512 bytes above when I meant 512 bits of course). But at the moment duk_tval.h won't be packed and will be 2x32 = 64 bytes. Are there enough spare bits so that different pointer types (such as object, string, or buffer) can be differentiated?

[davidchisnall]

Given the alignment requirements, we can use the low 3 bits to differentiate pointers to different types. We also have a notion of 'sealing' a pointer, which assigns it a type (currently a 24-bit value) and means that you can't use it without unsealing it, but that's probably the wrong mechanism here. We're prototyping a 128-bit version (necessary for real implementations - the 256-bit version is fine for prototypes, but does have noticeable cache overhead), which slightly reduces the number of bits available for the types. Anyway, I'll try making it work before I think too much about optimisation. Thanks for your help.

[svaarala]

Ok, sounds good. It's probably best to first see how to make Duktape work without touching duk_tval (using the somewhat inefficient 2x32-byte duk_tval). Once that's done, optimizing duk_tval representation for the platform is tedious but straightforward.

[davidchisnall]

With that, and a few patches I've managed to get it working. I'm working with the big single-file duktape.c from the latest release, because I haven't yet persuaded the Duktape build system to work on FreeBSD. This is my patch:

--- duktape.c.orig      2016-01-13 16:17:14.988053950 +0000
+++ duktape.c   2016-01-13 16:18:45.031047860 +0000
@@ -8097,14 +8097,10 @@
        } while (0)
 #elif defined(DUK_USE_HOBJECT_LAYOUT_2)
 /* LAYOUT 2 */
-#if (DUK_USE_ALIGN_BY == 4)
-#define DUK_HOBJECT_E_FLAG_PADDING(e_sz) ((4 - (e_sz)) & 0x03)
-#elif (DUK_USE_ALIGN_BY == 8)
-#define DUK_HOBJECT_E_FLAG_PADDING(e_sz) ((8 - (e_sz)) & 0x07)
-#elif (DUK_USE_ALIGN_BY == 1)
+#if (DUK_USE_ALIGN_BY == 1)
 #define DUK_HOBJECT_E_FLAG_PADDING(e_sz) 0
 #else
-#error invalid DUK_USE_ALIGN_BY
+#define DUK_HOBJECT_E_FLAG_PADDING(e_sz) ((DUK_USE_ALIGN_BY - (e_sz)) & (DUK_USE_ALIGN_BY-1))
 #endif
 #define DUK_HOBJECT_E_GET_KEY_BASE(heap,h) \
        ((duk_hstring **) (void *) ( \
@@ -8385,15 +8381,7 @@
 #define DUK_HOBJECT_A_ABANDON_LIMIT      2  /* 25%, i.e. less than 25% used -> abandon */

 /* internal align target for props allocation, must be 2*n for some n */
-#if (DUK_USE_ALIGN_BY == 4)
-#define DUK_HOBJECT_ALIGN_TARGET         4
-#elif (DUK_USE_ALIGN_BY == 8)
-#define DUK_HOBJECT_ALIGN_TARGET         8
-#elif (DUK_USE_ALIGN_BY == 1)
-#define DUK_HOBJECT_ALIGN_TARGET         1
-#else
-#error invalid DUK_USE_ALIGN_BY
-#endif
+#define DUK_HOBJECT_ALIGN_TARGET         DUK_USE_ALIGN_BY

 /* controls for minimum entry part growth */
 #define DUK_HOBJECT_E_MIN_GROW_ADD       16
@@ -9644,8 +9632,8 @@
 /* Fixed buffer; data follows struct, with proper alignment guaranteed by
  * struct size.
  */
-#if (DUK_USE_ALIGN_BY == 8) && defined(DUK_USE_PACK_MSVC_PRAGMA)
-#pragma pack(push, 8)
+#if (DUK_USE_ALIGN_BY > 1) && defined(DUK_USE_PACK_MSVC_PRAGMA)
+#pragma pack(push, DUK_USE_ALIGN_BY)
 #endif
 struct duk_hbuffer_fixed {
        /* A union is used here as a portable struct size / alignment trick:
@@ -9663,14 +9651,8 @@
                        duk_size_t size;
 #endif
                } s;
-#if (DUK_USE_ALIGN_BY == 4)
-               duk_uint32_t dummy_for_align4;
-#elif (DUK_USE_ALIGN_BY == 8)
-               duk_double_t dummy_for_align8;
-#elif (DUK_USE_ALIGN_BY == 1)
-               /* no extra padding */
-#else
-#error invalid DUK_USE_ALIGN_BY
+#if (DUK_USE_ALIGN_BY > 1)
+               duk_uint8_t padding[DUK_USE_ALIGN_BY];
 #endif
        } u;

@@ -9687,13 +9669,13 @@
         *  dynamic buffer).
         */
 }
-#if (DUK_USE_ALIGN_BY == 8) && defined(DUK_USE_PACK_GCC_ATTR)
-__attribute__ ((aligned (8)))
-#elif (DUK_USE_ALIGN_BY == 8) && defined(DUK_USE_PACK_CLANG_ATTR)
-__attribute__ ((aligned (8)))
+#if (DUK_USE_ALIGN_BY > 1) && defined(DUK_USE_PACK_GCC_ATTR)
+__attribute__ ((aligned (DUK_USE_ALIGN_BY)))
+#elif (DUK_USE_ALIGN_BY > 8) && defined(DUK_USE_PACK_CLANG_ATTR)
+__attribute__ ((aligned (DUK_USE_ALIGN_BY)))
 #endif
 ;
-#if (DUK_USE_ALIGN_BY == 8) && defined(DUK_USE_PACK_MSVC_PRAGMA)
+#if (DUK_USE_ALIGN_BY > 1) && defined(DUK_USE_PACK_MSVC_PRAGMA)
 #pragma pack(pop)
 #endif

@@ -13665,6 +13647,7 @@
        if (blen < 16) {
                goto skip_fastpath;
        }
+               goto skip_fastpath;

        /* Align 'p' to 4; the input data may have arbitrary alignment.
         * End of string check not needed because blen >= 16.
@@ -56033,15 +56016,10 @@
 #endif
                        " "
                        /* Alignment guarantee */
-#if (DUK_USE_ALIGN_BY == 4)
-                       "a4"
-#elif (DUK_USE_ALIGN_BY == 8)
-                       "a8"
-#elif (DUK_USE_ALIGN_BY == 1)
-                       "a1"
-#else
-#error invalid DUK_USE_ALIGN_BY
-#endif
+#define DUK_XSTRINGIFY(x) #x
+#define DUK_STRINGIFY(x) DUK_XSTRINGIFY(x)
+                       "a"
+                       DUK_STRINGIFY(DUK_USE_ALIGN_BY)
                        " "
                        /* Architecture, OS, and compiler strings */
                        DUK_USE_ARCH_STRING

And this to duk_config.h

--- duk_config.h.orig   2016-01-13 16:20:31.572040487 +0000
+++ duk_config.h        2016-01-13 16:21:04.562038208 +0000
@@ -2329,13 +2329,7 @@
 /* User forced alignment to 4 or 8. */
 #if defined(DUK_OPT_FORCE_ALIGN)
 #undef DUK_USE_ALIGN_BY
-#if (DUK_OPT_FORCE_ALIGN == 4)
-#define DUK_USE_ALIGN_BY 4
-#elif (DUK_OPT_FORCE_ALIGN == 8)
-#define DUK_USE_ALIGN_BY 8
-#else
-#error invalid DUK_OPT_FORCE_ALIGN value
-#endif
+#define DUK_USE_ALIGN_BY DUK_OPT_FORCE_ALIGN
 #endif

 /* Compiler specific hackery needed to force struct size to match aligment,

Most of the changes just allow arbitrary values for forcing alignment. You should be able to apply these without affecting anything else.

The only other change that I made is in the UTF-8 logic, to always skip the fast path because it reads past the end of the string and in a memory-safe environment this causes a trap. You probably don't want this anywhere else. Assuming that the alignment checks are correct and the out-of-bounds read is always within a cache line, this should not be problematic anywhere else (it might be in some managed VMs, but they probably aren't trying to run Duktape).

I plan now to spend a little bit of time on a CHERI-specific duk_tval layout (pointer sized, tag bit to identify pointer vs non-pointer, low bits in pointer to differentiate pointer types). Any hints about what to modify for that would be welcome.

[svaarala]

@davidchisnall Nice to hear, let's see how to get these into master.

Re: the utf-8 logic, there shouldn't be a read past the end of the string - if so, it's a bug which I'd like to fix. Could you point to the line where this happens?

[davidchisnall]

In the loop with the comment Full, aligned 4-byte reads., it reads four bytes at a time, but the string is not guaranteed to be a multiple of four bytes, so it will read 0-3 bytes past the end. The rounding in the calculation of p32_end ensures this.

Looking at this code a bit more carefully, it's actually worse than I'd thought because you're not ensuring the alignment on the start, so if you have a string with a non-multiple-of-four length that ends on a page boundary then you can get a segmentation fault on other architectures. On a system with byte-granularity protection, you hit it quite a lot earlier (unfortunately, we don't yet have enough of a debugger working to get stack traces, but somewhere in the startup code it's called with an on-stack buffer of non-multiple-of-four length and crashes for us).

[svaarala]

Hmm, the loop is trying to first align the pointer to 4. It then tries to read 4 bytes at a time, rounding p32_end down to ensure all the reads are safe.

The initial alignment loop doesn't need a bounds check because the fast path is skipped unless the input is >= 16 bytes: https://github.com/svaarala/duktape/blob/master/src/duk_unicode_support.c#L307-L309.

After that, p32_end is computed by adding the safe multiples of 4 to p (where p is already aligned to 4):

• p_end - p: number of bytes left (after p has been aligned to 4)
• Clearing two low bits of that gives number of bytes, rounded down to multiple of 4

The loop then reads only when p32 != p32_end; because p32 steps always by 4 it should never read on p32_end (which is <= p_end due to the rounding down) or beyond. But maybe I'm not seeing something obvious?

[davidchisnall]

Having now read it more carefully, your code looks correct. This might be a bug in our compiler.

[svaarala]

Those are always fun :)

By the way, Duktape currently assumes here and there that it's valid to compare pointers using e.g. p < q in loops. I know this is not strictly portable (and is indeed incorrect in some concrete environments I know of) and intend to do away with them. But just in case your pointers are not considered unsigned, this might cause some odd issues.

[davidchisnall]

That should be portable (and valid standard C) as long as p and q are both pointers to the same object, or q is a pointer to one past the end of the object. We compare pointers by virtual address, ignoring the bounds, for this kind of comparison because it turns out that a lot of code does things like create trees indexed by pointer value.

[svaarala]

Right, I've worked with a compiler where the pointer comparison emits signed integer comparison instructions which fail if p is below 0x80000000 and q is >= 0x80000000. Not sure if that's a spec violation or not - but caused practical issues with some code I was working on.

[davidchisnall]

The issue turns out to be quite subtle. This patch fixes it:

-       while (((duk_uintptr_t) (const void *) p) & 0x03) {
+       while (0x03 & ((duk_uintptr_t) (const void *) p)) {

In the C specification, any arithmetic on uintptr_t is implementation defined. In our model, we adopt the bounds information from the left-hand side and set the offset to the result. This means that your code here always gives a pointer at some offset from p , which is always non-null. Eventually, you run off the end of the string. With the alternate formulation, you get a pointer with base and length 0 and offset 0-3.

The following would also work:

-       while (((duk_uintptr_t) (const void *) p) & 0x03) {
-       while (((size_t) (const void *) p) & 0x03) {

This will do the arithmetic on a type that is definitely a plain integer type, with no guarantees that it can be converted back to a pointer type.

[svaarala]

I must admit I'm a bit out of my depth here, but my understanding has been that (u)intptr_t types are guaranteed to be plain integer types large enough to host a pointer and allow conversion back and forth, and being integer types they'd obey normal arithmetic rules? For example, http://pubs.opengroup.org/onlinepubs/000095399/basedefs/stdint.h.html:

The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to a pointer to void, and the result will compare equal to the original pointer: uintptr_t

I can apply one of the fixes above, but I'd like to add a code comment (and perhaps add the issue to doc/code-issues.rst as it's quite subtle). Could you provide a link to a relevant specification where arithmetic on uintptr_t is implementation defined? Or if you can suggest a comment that should precede the arithmetic for future readers, that'd be good too :)

[fatcerberus]

This is what I found re: pointer comparison in C (6.5.8.5):

When two pointers are compared, the result depends on the relative locations in the
address space of the objects pointed to. If two pointers to object or incomplete types both
point to the same object, or both point one past the last element of the same array object,
they compare equal. If the objects pointed to are members of the same aggregate object,
pointers to structure members declared later compare greater than pointers to members
declared earlier in the structure, and pointers to array elements with larger subscript
values compare greater than pointers to elements of the same array with lower subscript
values. All pointers to members of the same union object compare equal. If the
expression P points to an element of an array object and the expression Q points to the
last element of the same array object, the pointer expression Q+1 compares greater than
P. In all other cases, the behavior is undefined.

So yes, that signed pointer comparison mentioned earlier is a spec violation.

[svaarala]

ISO/IEC 9899 seems to have the same text re: (u)intptr_t as I quoted above:

7.18.1.4 Integer types capable of holding object pointers

The following type designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:

intptr_t

The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:

uintptr_t

These types are optional.

Given that the types are optional it'd be best if Duktape didn't rely on these types at all, and there's actually very few places they're now needed.

One case in particular is a bit of a blocker: in some cases Duktape needs to do a const-to-non-const cast without causing compiler warnings. The only way to do that reliably seems to be to cast through an integer type (casting through void * is not enough) and that means an integer type large enough to hold a pointer is needed: (void *) (intptr_t) my_const_void_ptr).

[svaarala]

This is going a bit off topic, but perhaps I could lose the const by casting through a union, this seems to work at least with -Wcast-qual:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef union {
        void *x;
        const void *y;
} lose_const;

int main(int argc, char *argv[]) {
        void *p1;
        const void *p2;
        lose_const lc;

        (void) argc; (void) argv;

        /* Warning */
        p2 = (const void *) 0xdeadbeef;
        p1 = (void *) p2;
        printf("p1=%p\n", p1);

        /* No warning, but (u)intptr_t types are optional */
        p2 = (const void *) 0xdeadbeef;
        p1 = (void *) (uintptr_t) p2;
        printf("p1=%p\n", p1);

        /* No warning, doesn't rely on optional types */
        p2 = (const void *) 0xdeadbeef;
        lc.y = p2;
        p1 = lc.x;
        printf("p1=%p\n", p1);
}

[fatcerberus]

That's a bit hacky, are there any interesting platforms that have the normal (u)intX_t types but not (u)intptr_t?

[svaarala]

Let's discussing the const casting in #538 so I'll respond there.

[svaarala]

@davidchisnall The C standard apparently just guarantees that you can cast from pointer to (u)intpr_t and back to pointer without losing information, and that the result is an integer type (from which I'd assume it then behaves like any other integer). There are apparently no guarantees what e.g. the lowest bits represent, so perhaps it'd be entirely legal for the lowest 16 bits of a (u)intptr_t to represent a segment selector instead of offset within segment, etc, so arithmetic on the result may not be meaningful.

But even so I don't understand why the argument order for bitwise AND should matter: once the pointer has been converted to (u)intptr_t it should behave like other integer types? And since the cast happens before the AND operator is involved at all, the argument order shouldn't matter (?)

[davidchisnall]

The answer is complicated and has to do with pointer provenance. In the C abstract machine, each pointer either:

1. Points somewhere inside a valid object
2. Points to one past the end of a valid object
3. Is null (which does not necessarily mean that it is zero, but means that comparing it to an integer constant zero must return true. Interestingly, it is not required that casting an integer variable that happens to contain 0 will give a null pointer)
4. It has an undefined value (in which case, all bets are off and it doesn't even need to compare equal to itself).

Any arithmetic on a pointer in one of the first two categories may move it to the fourth, or may move it between the first two states, but must result in a pointer to the same object. Compilers use this fact in optimisation: If they can prove that a and b point to different objects then they assume that a+x != b, for any value of x.

For this to be a property of the abstract machine, this means that pointers must carry provenance information around with them (i.e. they must in some way understand what object they are related to). In formal specifications of C, there are various models. If you want to support xor linked lists, then you must have a multi-provenance semantics, where values inherit the provenance of all values that are operands to operations that give rise to the value.

In a concrete implementation with bounds checking, this is not possible because the set of objects that a pointer could inherit a valid provenance for is unbounded. Instead, each pointer has a single provenance. We do not (at least, not in all compilation modes, and not in the one where I'm now running Duktape) support casting from an arbitrary integer to a pointer, because that would make it trivial to bypass memory safety. Instead, our [u]intptr_t is a value that is actually represented as a memory capability (you can think of this as an unforgeable fat pointer, with base, length, offset, and permissions, and a tag bit indicating that it's valid). When you cast from an integer to an intptr_t, you get a value that has its tag bit cleared, its base and length set to zero, and its offset set to whatever you cast from. When you cast from a pointer to a [u]intptr_t, you get exactly the same in-memory (or in-register) representation as in the original pointer.

This means that when you do arithmetic on n [u]intptr_t value you must inherit the base/length/permissions and so on from one side or the other. We, somewhat arbitrarily, pick the left side. We then hit another set of requirements: We want to be able to support accurate copying garbage collection in code that doesn't explicitly do things that wouldn't work with garbage collection (and to be able to statically verify whether code does violate these assumptions). This means that we don't want to expose arithmetic directly on the virtual address and instead support uintptr_t arithmetic on the offset. This allows a copying garbage collector to interrupt the program at arbitrary points, move objects around, rewrite their pointers, and continue. Because of this decision, the value of foo & 3, where foo is a uintptr_t is the base and bounds of foo, with the offset of foo anded with the value 3. This normally does what you'd want (for example foo &= ~3ULL will give you the value rounded down to give the alignment that you want.

Motivated by this issue, I've added a compiler warning whenever you do a bitwise operation where one side is a uintptr_t and the other is not. This triggered two places in Duktape:

duk_unicode_support.c:316:14: warning: binary expression on capability and non-capability types: 'int' and 'duk_uintptr_t' (aka '__uintcap_t'). Provenance will be inherited from left-hand side
      [-Wcapabilities]
        while (((duk_uintptr_t) (const void *) p) & 0x03) {
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~
duk_bi_json.c:1463:50: warning: binary expression on capability and non-capability types: 'duk_uintptr_t' (aka '__uintcap_t') and 'unsigned int'. Provenance will be inherited from left-hand side
      [-Wcapabilities]
        shift_dst = (duk_bool_t) (((duk_uintptr_t) dst) & 0x01U);
                                  ~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~

Changing both of these to use duk_size_t instead of duk_uintptr_t indicates that you just want a numerical value of the pointer and do not intend to cast it back to a pointer and fixes the issue. I completely understand if you don't want to apply this change (keeping around code to support an experimental CPU is not currently valuable to anyone other than me). Maintaining a two-line patch isn't a huge hardship for me.

[fatcerberus]

So just to clarify (because this platform's pointer semantics intrigue me :) ):

void* ptr1 = &obj;
uintptr_t ip = (uintptr_t)ptr1;
void* ptr2 = (void*)ip;

Is it necessarily true that ptr2 == ptr1? Because the specification requires that to be the case.

[davidchisnall]

Yes, round trips through uintptr_t work. The following will also work:

char *x = &obj;
uintptr_t ip = (uintptr_t)x;
ip++;
char *y = (char*)ip;
assert(y == x+1);

We've tried very hard to make [u]intptr_t do what people expect them to do, but bitwise operations are tricky in anything where the hardware actually does preserve provenance information.

[svaarala]

@davidchisnall Thanks for the detailed description, the issue is indeed not trivial :)

Out of curiosity, what would happen if one used sprintf() to format a (u)intptr_t, parse it back from the string, and then coerce back to a pointer? What about if one parses an arbitrary string so that the (u)intptr_t value may be arbitrary; is it checked somehow during parsing and/or casting?

In any case, I'll be happy to apply any compatible fixes, fixing those two warnings should be trivial using size_t (or if I understand correctly, any "normal" integer type). I'll add a note to code-issues.rst about this issue. Unfortunately I can't think of an automatic regression test for future issues.

[davidchisnall]

Out of curiosity, what would happen if one used sprintf() to format a (u)intptr_t, parse it back from the string, and then coerce back to a pointer? What about if one parses an arbitrary string so that the (u)intptr_t value may be arbitrary; is it checked somehow during parsing and/or casting?

In both of these cases, you're attempting to materialise a pointer without any provenance, and so you would get something that looks much like a pointer, but actually isn't. The tag bit would be unset. There is one exception to this: there are two global memory capabilities, one for code (read and execute permissions) and one for data (load and store permissions). You are allowed to materialise pointers inside these regions from arbitrary data. It's up to the run-time environment how restricted these are - the goal is to have nothing in the global data capability.

In any case, I'll be happy to apply any compatible fixes, fixing those two warnings should be trivial using size_t (or if I understand correctly, any "normal" integer type). I'll add a note to code-issues.rst about this issue. Unfortunately I can't think of an automatic regression test for future issues.

That's great, thank you!