Format function SegFaulting at Runtime when negative width string is specified

[tj800x]

While attempting to use the Format package on a U128, I managed to create a run-time segfault, by accidentally passing in a negative width value. I was using position-based arguments when this occurred, but it also occurs with named arguments, as shown below.

use "format"

actor Main
  new create(env:Env) =>
  let n: U128 = 42

  env.out.print("Regular output. n="+n.string())
  env.out.print(Format.int[U128](where x=n, fmt=FormatBinaryBare, prefix=PrefixDefault, 
    prec=1, width=20, align=AlignRight,fill='0'))

  env.out.print("Before runtime fault.  Segment fault 11 on Mac OS X.")
  env.out.print(Format.int[U128](where x=n, fmt=FormatBinaryBare, prefix=PrefixDefault, 
    prec=1, width=-1, align=AlignRight,fill='0'))
  env.out.print("This is never executed because the above line crashes at runtime.")

Building builtin -> /usr/local/Cellar/ponyc/0.14.0/packages/builtin
Building . -> /Users/thomasjohnson/Projects/pony/FormatStringSizeCrash
Building format -> /usr/local/Cellar/ponyc/0.14.0/packages/format
Building collections -> /usr/local/Cellar/ponyc/0.14.0/packages/collections
Building ponytest -> /usr/local/Cellar/ponyc/0.14.0/packages/ponytest
Building time -> /usr/local/Cellar/ponyc/0.14.0/packages/time
Generating
Reachability
Selector painting
Data prototypes
Data types
Function prototypes
Functions
Descriptors
Optimising
Writing ./FormatStringSizeCrash.o
Linking ./FormatStringSizeCrash
Regular output. n=42
00000000000000101010
Before runtime fault. Segment fault 11 on Mac OS X.
/bin/bash: line 1: 31076 Segmentation fault: 11 ./FormatStringSizeCrash
[Finished in 4.0s with exit code 139]
[shell_cmd: ponyc && ./FormatStringSizeCrash]

I've confirmed this issue on both Mac OSX and on the Pony Playground.

0.14.0 [release]
compiled with: llvm 3.9.1 -- Apple LLVM version 8.1.0 (clang-802.0.42)

0.14.0 [release]
compiled with: llvm 3.9.1 -- cc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609

[tj800x]

Possibly relevant comments from the 2017-JULY-07 IRC follow:

[15:20] <@jemc> the cause is that USize(-1) == USize.max_value()
[15:39] <@jemc> no worries - I was trying to think if there's something that could be done as a sanity check in Format against very large values of width, but it seems that width is used for padding, and I'm not sure where to draw a "sane" limit for padding a string
[15:42] <@Praetonus> jemc: There's a bug in String.reserve too. If the reserved size is USize.max_value, the function will add 1 for the null terminator and overflow, resulting in a String that thinks it has lots of memory available but actually didn't allocate anything
[15:42] <@Praetonus> That's the reason of the crash here
[15:44] <@jemc> that darn null terminator

[tj800x]

I've confirmed this on 0.14.0-8781b65.

$ ponyc --version
0.14.0-8781b654 [release]
compiled with: llvm 3.9.1 -- Apple LLVM version 8.1.0 (clang-802.0.42)

[jemc]

This is the key part for addressing the segault.

[15:42] <@Praetonus> jemc: There's a bug in String.reserve too. If the reserved size is USize.max_value, the function will add 1 for the null terminator and overflow, resulting in a String that thinks it has lots of memory available but actually didn't allocate anything

[charlesetc]

The segfault is happening within the while loop here

What's happening is that the pre variable has overflown from 0 to the max usize and is being slowly decremented.

Changing the code to this:

while pre > 0 do
  Debug.out(pre)
  s.append(fills)
  pre = pre - 1
end

...results in this:

18446744073709528348
18446744073709528347
18446744073709528346
18446744073709528345
18446744073709528344
18446744073709528343
18446744073709528342
18446744073709528341
18446744073709528340
18446744073709528339
18446744073709528338
18446744073709528337
...

I'm not sure what the proper response to a negative width should be though 🛩 🍐

[jemc]

@charlesetc - as you've noted USize(-1) is equivalent to USize.max_value(), which is not really a bug, but a reasonable shorthand.

I think the only consistent thing we can do is to assume that they really did mean USize.max_value(), and make a string of the maximum length.

[charlesetc]

Interesting - so is the segfault here from allocating too much memory?

[jemc]

@charlesetc According to @Praetonus' comment above, the issue is that the string is allocating an extra byte for the null terminator, leading it to allocate not USize.max_value() bytes, but USize.max_value() + 1, which comes out to zero bytes.

The allocation logic needs to be special-cased to not add + 1 for the null terminator if the size is USize.max_value().

[charlesetc]

Gotcha - does the segfault in the while loop that I'm seeing go along with that?

[Praetonus]

The allocation logic needs to be special-cased to not add + 1 for the null terminator if the size is USize.max_value().

This certainly is a good solution for this particular edge case, but I think we need to discuss on a way to handle the general issue of "overflowing" collections, i.e. what should happen when one tries to add more elements to a collection than logically possible.

Since these are very uncommon edge cases, one possible way to handle the issue could be to take the "performance over safety" route and not handle it at all, similar to how we're currently not handling memory exhaustion. This would also raise the issue of whether USize(-1) really is a "reasonable shorthand" for a really big number, since it can easily lead to an overflowing collection as demonstrated in this issue.

@charlesetc Yes. It's segfaulting because the String is writing to memory that it thinks it owns, but actually doesn't since it didn't allocate any memory.

[Theodus]

Minimal reproduction:

actor Main
  new create(env:Env) =>
    let s = recover String end
    s.reserve(-1)
    // s.reserve(1_000_000_000) also works fine

    var n: USize = 129 // 128 is fine, 129 results in SEGFAULT

    while n > 0 do
      s.append(" ")
      n = n - 1
    end

    DoNotOptimise[String tag](s)
    DoNotOptimise.observe()

Output:

src/libponyrt/mem/pool.c:868: void ponyint_pool_free(size_t, void *): Assertion `index < (20 - 5 + 1)' failed.
signal SIGABRT (Abort)

[malthe]

The issue is not in String.reserve but rather in the pool size adjustment logic.

However, the fix shown below reveals a bigger issue here which is that pool_alloc_size(size) then fails to allocate a pointer (this time of the correct size) since there is no block which is large enough.

On my system pool_block_header.largest_size is 134167552. This is obvious larger than USize.max_value() - 1.

--- a/src/libponyrt/mem/heap.c
+++ b/src/libponyrt/mem/heap.c
@@ -416,6 +416,8 @@ void* ponyint_heap_alloc_small_final(pony_actor_t* actor, heap_t* heap,
 void* ponyint_heap_alloc_large(pony_actor_t* actor, heap_t* heap, size_t size)
 {
   size = ponyint_pool_adjust_size(size);
+  if(size == 0)
+      size = (size_t) - 1;
 
   chunk_t* chunk = (chunk_t*) POOL_ALLOC(chunk_t);
   chunk->actor = actor;
diff --git a/src/libponyrt/mem/pool.c b/src/libponyrt/mem/pool.c
index c89b743a5..2f2436782 100644
--- a/src/libponyrt/mem/pool.c
+++ b/src/libponyrt/mem/pool.c
@@ -914,6 +914,8 @@ void* ponyint_pool_alloc_size(size_t size)
     return ponyint_pool_alloc(index);
 
   size = ponyint_pool_adjust_size(size);
+  if(size == 0)
+      size = (size_t) - 1;
   void* p = pool_alloc_size(size);
 
   return p;