Ensure completion_cx::as_promise(p) works even when p is destroyed prior to fulfillment

[Dan Bonachea]

Consider the following program:

#include <upcxx/upcxx.hpp>
#include <iostream>
#include <algorithm>

using namespace upcxx;
using namespace std;

future<> fetch_vals(global_ptr<int> gp, int *dst, int cnt) {
#if STATIC_PROMISE
  static 
#endif
  promise<> p;

  for (int i=0;i<cnt;i++) {
    upcxx::rget(gp+i, dst+i, 1, operation_cx::as_promise(p));
  }
  return p.finalize();
}

double stack_writer(double v) {
  if (v < 3) return 1;
  else return stack_writer(v-2) * stack_writer(v-1) * v;
}

int main() {
  upcxx::init();
  int cnt = 100;
  int *vals = new int[cnt]();
  global_ptr<int> gp;

  if (!rank_me()) {
    gp = new_array<int>(cnt);
    int *src = gp.local();
    std::fill(src, src+cnt, 42);
  }
  gp = broadcast(gp, 0).wait();
  future<> f = fetch_vals(gp, vals, cnt);
  cout << stack_writer(10.1) << endl;
  f.wait();

  for (int i=0;i<cnt;i++)
    assert(vals[i] == 42);

  barrier();
  if (!rank_me()) cout << "SUCCESS" << endl;

  upcxx::finalize();
}

This proxy does not compute anything interesting, but the pattern in fetch_vals() is an idiom we'd like to encourage for functions that launch many operations and return a future - specifically, registering all the operations on a single promise costs less overhead than creating and conjoining a bunch of futures, and it's also more convenient in a case like this where the operations are being generated in a localized block of code.

Sadly, this code does not currently work as written, due to a lifetime problem. Running this code on distributed memory generates a crash, eg a SEGV with the following stack:

[1] #22 0x0000000100788f52 in upcxx::detail::persona_tls::fulfill_during_user_of_active<>(upcxx::persona&, upcxx::promise<>&, long) (this=0x60003ac88, per=..., pro=..., anon=1) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/persona.hpp:659
[1] #23 0x000000010078bc3d in upcxx::backend::fulfill_during_<upcxx::promise<>&>(std::integral_constant<upcxx::progress_level, (upcxx::progress_level)1>, upcxx::promise<>&, long, upcxx::persona&) (pro=..., anon=1, active_per=...) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/backend.hpp:152
[1] #24 0x000000010078bafe in upcxx::backend::fulfill_during<(upcxx::progress_level)1>(upcxx::promise<>&, long, upcxx::persona&) (pro=..., anon=1, active_per=...) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/backend.hpp:172
[1] #25 0x000000010078b6db in upcxx::detail::cx_state<upcxx::promise_cx<upcxx::operation_cx_event>, std::tuple<> >::operator()() (this=0x6000d50e8) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/completion.hpp:383
[1] #26 0x000000010078acfb in upcxx::detail::completions_state_head<true, upcxx::detail::rget_byref_event_values, upcxx::promise_cx<upcxx::operation_cx_event> >::operator_case<>(std::integral_constant<bool, true>) (this=0x6000d50e8) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/completion.hpp:525
[1] #27 0x000000010078ad67 in upcxx::detail::completions_state_head<true, upcxx::detail::rget_byref_event_values, upcxx::promise_cx<upcxx::operation_cx_event> >::operator()<upcxx::operation_cx_event> (this=0x6000d50e8) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/completion.hpp:535
[1] #28 0x0000000100789aa8 in upcxx::detail::completions_state<upcxx::detail::event_is_here, upcxx::detail::rget_byref_event_values, upcxx::completions<upcxx::promise_cx<upcxx::operation_cx_event> > >::operator()<upcxx::operation_cx_event> (this=0x6000d50e8) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/completion.hpp:605
[1] #29 0x000000010078978d in upcxx::detail::rget_cb_byref<upcxx::detail::completions_state<upcxx::detail::event_is_here, upcxx::detail::rget_byref_event_values, upcxx::completions<upcxx::promise_cx<upcxx::operation_cx_event> > >, upcxx::detail::completions_state<upcxx::detail::event_is_remote, upcxx::detail::rget_byref_event_values, upcxx::completions<upcxx::promise_cx<upcxx::operation_cx_event> > > >::execute_and_delete (this=0x6000d50d0) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/rget.hpp:121
[1] #30 0x000000010078cbe8 in upcxx::backend::gasnet::handle_cb_queue::burst (this=0x100870110 <upcxx::backend::gasnet::master_hcbs>, burst_n=3) at /home/bonachea/UPC/rel/upcxx-2019.9.0/src/backend/gasnet/runtime.cpp:2151
[1] #31 0x000000010041bcfe in upcxx::<lambda(upcxx::persona&)>::operator()(upcxx::persona &) const (__closure=0xffffc930, p=...) at /home/bonachea/UPC/rel/upcxx-2019.9.0/src/backend/gasnet/runtime.cpp:1665
[1] #32 0x000000010041d635 in upcxx::detail::persona_tls::foreach_active_as_top<upcxx::progress(upcxx::progress_level)::<lambda(upcxx::persona&)> >(upcxx::<lambda(upcxx::persona&)> &&) (this=0x60003ac88, fn=...) at /home/bonachea/UPC/rel/upcxx-2019.9.0/src/persona.hpp:768
[1] #33 0x000000010041be82 in upcxx::progress (level=upcxx::progress_level::user) at /home/bonachea/UPC/rel/upcxx-2019.9.0/src/backend/gasnet/runtime.cpp:1660
[1] #34 0x000000010078feaa in upcxx::detail::future_wait_upcxx_progress_user::operator() (this=0xffffcbf7) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/future/future1.hpp:60
[1] #35 0x000000010078e85f in upcxx::future1<upcxx::detail::future_kind_shref<upcxx::detail::future_header_ops_general>>::wait<-1, upcxx::detail::future_wait_upcxx_progress_user>(upcxx::detail::future_wait_upcxx_progress_user&&) (this=0xffffcbc8, progress=...) at /usr/local/upcxx-2019.9.0/upcxx.debug.gasnet_seq.udp/include/upcxx/future/future1.hpp:218
[1] #36 0x00000001004013e7 in main () at promise-nuke2.cc:39

The problem is that when the promise<> p used to register the operations is a local variable (often the most convenient and elegant choice) it goes out of scope before fulfillment leading to a later crash when the RMA completes and the runtime tries to fulfill.

The simplest workaround is to extend the promise lifetime by promoting it to a static variable (e.g. -DSTATIC_PROMISE in the above code), however this is inelegant and doesn't handle multiple calls. The more localized solution that doesn't suffer the latter deficiency is to inject explicitly managed dynamic allocation to provide the required lifetime, something like this:

future<> fetch_vals(global_ptr<int> gp, int *dst, int cnt) {
  promise<> *p = new promise<>;

  for (int i=0;i<cnt;i++) {
    upcxx::rget(gp+i, dst+i, 1, operation_cx::as_promise(*p));
  }
  return p->finalize().then([p](){ delete p; });
}

However this is non-intuitive (for novices), non-RAII and inserts a dynamic allocation overhead into the critical path. This requirement to explicitly manage the promise lifetime imposes additional complexity into highly asynchronous user code.

As an aside, I don't think this lifetime requirement for operation_cx::as_promise() is adequately addressed by the current spec - it's only by assumption and implication that readers can infer a potential problem here (probably motivates a spec issue to fix that). It's also a departure from the behavior of future, which always behave as a handle to a reference-counted object and have no associated lifetime concerns. Finally, it's worth noting this lifetime problem only applies to the interval until promise fulfillment - once fulfilled, the promise can safely be destroyed and readied futures linked to it will continue to work, EVEN for non-empty promises. This means there is already a level of indirection (at least for non-empty promises) to an internal object containing the result value - which makes it particularly unfortunate that the user is forced to insert a redundant and potentially costly level of indirection.

The point of this issue is that I don't see any fundamental reason why promise needs to continue behaving as it currently does. If promise instead always behaved as a smart-pointer to a reference-counted (hidden) object, even before fulfillment, then the lifetime could be automatically managed and collection would also happen naturally after fulfillment and the destruction of the last reference (which might be held by the runtime itself). I'd like us to discuss/consider the costs and benefits of deploying such a feature upgrade. I think it would be a nice productivity improvement for highly asynchronous codes, enabling a more natural idiom for use of promises. Also, as a semantic relaxation it should be backwards-compatible with existing code.

[john bachan]

Refcounted promises was considered when drafting the API and was excluded intentionally for these reasons:

1. Unlike futures, promises are mutable by the user. Implicit sharing becomes awkward unless the type semantics are always reference-like, but in our case they aren't. For instance, the default promise() constructor allocates a new promise (value-like) yet the copy constructor would just copy the reference (reference-like). No other type in the C++ std lib works like this, either its all value-like or all reference-like (to the best of my knowledge). If we were to change promise to be all-reference-like, we would add a make_promise<T>() factory function and either delete the default constructor or have the default constructed promise refer to a NULL promise. I can't find a reason why the mixed semantics would be unsound, so I'm not against them, I just want other people to acknowledge the oddness of them and if we then all conclude that the semantics are the most convenient and intuitive we can green light them.

2. It just so happens that as implemented now promises keep their state (dependency counter) in the same hunk of memory that is later referenced as the future. For this reason, extending promises to be shared incurs no extra cost and would be a trivial change. But when drafting the spec, the working implementation I had put promise state directly in the promise object adjacent to the future's thunk pointer. This extension definitely eliminates that specific implementation.

As stated in point 1, I could be persuaded in favor of this extension if everyone (or just @Dan Bonachea & @Amir Kamil concede that its a little weird.

[Edit] Also, I am not in favor of changing promise to be all-reference like since that breaks code. But I wouldn't be against a new reference-like class of promises like promise_ref or something.

[Amir Kamil]

I think the problem we’re trying to solve is that dropping a promise leads to undefined behavior, which is actually unspecified and not the desired behavior. I think this is solvable without making promises copyable; the underlying state should be maintained as long as there are outstanding dependencies and/or futures associated with the promise.

[john bachan]

@Amir Kamil 's suggestion sounds good to me. It requires that we support refcounting promises, but only expose that power to the upcxx internals. The biggest nontrivial change would be operations with completion_cx::as_promise(promise&) would have to stash the underlying thunk address instead of the promise address.

[Dan Bonachea]

@john bachan said:

The biggest nontrivial change would be operations with completion_cx::as_promise(promise&) would have to stash the underlying thunk address instead of the promise address.

I agree this is the key change - I believe this is the root cause of the breakage shown in the OP. In fact I suspect this implementation change alone may be enough to resolve the current difficulties. Can @john bachan or @Amir Kamil provide an example of why anything more is required semantically?

It's worth noting that if promises remain non-copyable value-like objects, then fulfillment from user code still needs to maintain the (exactly one) promise lifetime until fulfillment (because user code has no other way to invoke fulfillment). Fulfillment from runtime code (via completion_cx::as_promise(promise&)) just needs to ensure it holds a reference to the underlying thunk and prevents its collection before completion, even in cases where the user-held promise is destructed prior to fulfillment (I think this is what John meant by "requires that we support refcounting promises, but only expose that power to the upcxx internals").

So assuming we are in agreement, how do we explain this change in the spec? It's currently underspecified and somehow we'll need to clarify this strengthened guarantee...

[Amir Kamil]

Do we want to provide user code with the ability to work with the underlying state even if the promise is destructed? Something like the promise_ref that John proposed, that would allow user code to fulfill the underlying object?

[Dan Bonachea]

@Amir Kamil : For monolithic codes, I don't think we'd be providing any strongly motivated new capability, because monolithic code that both constructs and fulfills a promise can presumably arrange to ensure it remains live until fulfillment.

HOWEVER, if the client code is implementing an interface that takes a promise reference/pointer from its own caller (who constructed the promise), then it could probably benefit from this capability for exactly the same reasons as completion_cx::as_promise - in other words, I think it's the division of responsibility between promise construction/destruction and fulfillment that motivates the use of a reference-counted thunk.

Pseudocode example:

// this function represents an abstraction boundary
void producer(upcxx::promise<int> &p) {
   do_some_async_stuff(...).then([&p](int result) {
      p.fulfill_result(result);
   });
}
// the user code below is a layer above the abstraction boundary
void user() {
  upcxx::promise<int> p;
  rput(..., operation_cx::as_promise(p));
  producer(p);
  return p.get_future();
}

Here the producer function really wants the ability to ensure it can safely fulfill_result, even if the caller supplied a promise that is immediately destroyed after dispatch. Of course this could be solved by changing the interface design to return futures instead of accepting promise references, but the current UPC++ design rules out the latter design. I'm not sure if there's any good motivating use case for that latter design, aside from potentially reducing future churn.

I think what such code would need is the ability to fetch the ref-counted thunk pointer (promise_ref) from a promise, where the only methods on the new handle type are probably fulfill_result and fulfill_anonymous (and possibly get_future?).

[Amir Kamil]

I think we should hold off on providing the promise_ref capability until someone asks for it.

[Dan Bonachea]

@Rob Egan - You previously mentioned HipMer is creating promises and keeping them around until fulfillment. Is that code dynamically allocating the promise to accomplish that lifetime guarantee?

If so, would the semantic loosening requested in this issue (and being developed in pull request #141) help to simplify code or remove overhead for HipMer? Is all the fulfillment coming from the runtime or do you directly call promise::fulfill_*? If the latter, do you have a motivating use case for the additional promise_ref extension to be available in user code?

[Rob Egan]

So the way we use promises is within the aggr_store code… There is a fixed amount of memory with blocks of it cycling in and out of use through “void push(block_t)” and “future<block_t> pop()”, so pop() will populate and record a promise on a list if it there are no blocks immediately available on the stack and push() will fulfill a promise, if any exist on that list of promises, or put it on the stack of available blocks. To make this work with an arbitrary number of requests to pop(), I use a std::list to store the promises. I found that I needed to create a shared_ptr< promise<block_t> > and put that on a list, because of the restricted copy/move constructors on promise itself.

Being able to use the STL containers for tracking promises is my driving use case, and I do explicitly call promise::fulfill_*. It is not immediately obvious to me if promise_ref could be stored in a STL without a shared_ptr wrapping. But I agree with this thread that the undefined behavior of fulfilling a promise that did drop out of scope is problematic and confusing.

So for my use case eliminating the extra overhead of a shared_ptr is worth it, especially if internally the promise is already is reference counting the underlying object that will eventually be fulfilled.

‌

[Dan Bonachea]

@Rob Egan said:

I use a std::list to store the promises. I found that I needed to create a shared_ptr< promise<block_t> > and put that on a list, because of the restricted copy/move constructors on promise itself.

Rob - promises do support move construction and move assignment, just not copies (they behave as unboxed mutable objects, not handles). std::smart_ptr gives you a copyable handle to the promise (as would the proposed promise_ref), but do you know if you actually need a copyable handle? I think it should be possible to store non-copyable promises in a std::list, but it probably depends on how you intend to use the list.

Here's a simple working example I just wrote as a sanity check:

#include <upcxx/upcxx.hpp>
#include <iostream>
#include <list>
#include <cassert>

std::list<upcxx::promise<int>> mylist;

upcxx::future<int> create_promise() {
  upcxx::promise<int> p;
  upcxx::future<int> f = p.get_future();
  mylist.push_back(std::move(p));
  return f;
}

void fulfill_list() {
  int i=1;
  for (auto &p : mylist) {
    p.fulfill_result(i++);
    mylist.pop_front(); // optional
  }
}

int main() {
  upcxx::init();

  int sum = 0;
  for (int i=0; i < 10; i++) {
    create_promise().then([&sum](int v) {
      sum += v;
      if (!upcxx::rank_me()) std::cout << v << std::endl;
    });
  } 

  fulfill_list();
  assert(sum == 55);

  upcxx::barrier();
  if (!upcxx::rank_me()) std::cout << "SUCCESS" << std::endl;
  upcxx::finalize();
}

Note that promise was missing a move assignment operator until version 2018.9.0 (issue #141), so perhaps you were trying against an outdated version of the library? The example code above works in the current 2019.9.0 release.

[Rob Egan]

Thanks Dan, I might have been developing with an older installation which led to my usage of shared_ptrs. I was also trying to attach a timer to the elements within the list of promises so I could track the lifetimes and may have confused the compiling problems associated with that. I can confirm that promises work just fine within STL containers in my code and makes it simpler too.

So I can’t provide a compelling need for promise_ref, unless the incremental memory overhead for storing a promise is much larger than that for a promise_ref… For the aggregated query that I plan to develop, I am planning to store millions of promises in a container while waiting for aggregated responses to complete which would be used to fulfill them.

[Dan Bonachea]

@Rob Egan wrote:

I can’t provide a compelling need for promise_ref, unless the incremental memory overhead for storing a promise is much larger than that for a promise_ref

This is a question for @john bachan, but if I understand his plan in pull request #141 correctly, the promise exposed to the user will just be a restricted form of the promise_ref-like-class used internally by the runtime - in both cases just a lightweight reference-counted pointer to the unique internal heap-allocated object that backs the promise and all associated futures.

[Dan Bonachea]

@Amir Kamil + @john bachan : I thought up a simpler and more compelling example to motivate promise_ref.

This is just a minor tweak to the fetch_vals function in the original post that needs to perform some post-processing on fetched values before signalling completion to the caller:

future<> fetch_vals(global_ptr<int> gp, int *dst, int cnt) {
  promise<> p(cnt);

  for (int i=0;i<cnt;i++) {
    upcxx::rget(gp+i, dst+i, 1).then([dst,i,&p]() {
      dst[i] *= 2;  // some post-processing
      p.fulfill_anonymous(1);
    });     
  }
  return p.finalize();
}

This code is erroneous because the reference capture of the promise becomes a dangling reference when fetch_vals returns, and the execution of the callback within later progress explodes (even on the pull request #141 branch). This is essentially the same problem as the original code (except here fulfillment is invoked in user code), and the fixes are equally nasty - in general, requiring the user to add a dynamically allocated level of indirection to his promise (or ditch the promise entirely and pay the overheads to conjoin a bunch of additional futures).

However if the user had access to promise_ref functionality, he could instead write something simple like this:

future<> fetch_vals(global_ptr<int> gp, int *dst, int cnt) {
  promise<> p(cnt);
  promise_ref<> pr = p.get_ref(); // syntax TBD

  for (int i=0;i<cnt;i++) {
    upcxx::rget(gp+i, dst+i, 1).then([dst,i,pr]() {
      dst[i] *= 2;  // some post-processing
      pr.fulfill_anonymous(1);
    });     
  }
  return p.finalize();
}

Using the existing internal level of indirection to avoid extraneous allocation.

As a side note, specifying promise_ref also makes it somewhat easier to specify the new behavior of completion_cx::as_promise(promise <T...> &pro) - we can specify this method schedules a completion for pro.get_ref(), or (better yet?) change the argument type to promise_ref and specify an implicit conversion. The latter would allow the lambda above to schedule additional RMA completions on the same underlying promise, which also seems a useful capability.

Thoughts?

[john bachan]

@Dan Bonachea , yes this seems like a valid motivator. The fact that multiple "then" callbacks can reference the promise at the same time makes it impossible to std::move the promise into the callback where it is to be fulfilled (this is possible with a single callback).

My preference would be to enhance promise to have the gc-ref semantics, granted the weirdness of an allocating default constructor.

[Dan Bonachea]

@john bachan said:

If we were to change promise to be all-reference-like, we would add a make_promise<T>() factory function and either delete the default constructor or have the default constructed promise refer to a NULL promise.
[...]
I am not in favor of changing promise to be all-reference like since that breaks code. But I wouldn't be against a new reference-like class of promises like promise_ref or something.
[...]
My preference would be to enhance promise to have the gc-ref semantics, granted the weirdness of an allocating default constructor.

John - please clarify exactly what you are proposing here. I'm pretty strongly against a promise change that breaks current code (such as deleting or castrating the constructor), since we know the current constructor is already used extensively in at least two external applications, some of which may be relying on default constructor. Forcing a factory function on users may entail non-trivial changes to existing app code.

We seem to agree promise should grow some ref-like capabilities, but in order to expose that relaxation to users I think we need to decide at least:

1. Do we want to leave promise unchanged and provide a promise_ref helper class with reference-like semantics? Or add new ref-like semantics onto the existing promise class. Assuming the latter:
2. How the promise constructor works
3. Are we adding any ref-like C++ concepts to promise (eg CopyAssignable)

[Paul Hargrove]

Revamped how promises are handled internally. We now take advantage of the fact that a promise is just a pointer to a shared object which is also aliased by its future('s). We enable the same refcounting garbage collection that governs futures, but hide it from the end-user. The goal of this work is to allow the user to drop promises which are the completion targets of outstanding comm operations, yet still have the futures obtained from that promise function correctly. See issue 277.

There is a new detail::promise_shref<T...> class that implements all of promise<T...> plus implements all constructors with aliasing refcounting semantics (the default ctor allocates a new promise). This class also allows easy access to the underlying detail::future_header_promise<T...>*. promise<T...> simply inherits this class privately and then explicitly whitelists all the base members except the aliasing constructors. Use detail::promise_as_shref() to cast from promise& to detail::promise_shref&.

The backend API pertaining to promises has been changed to take naked detail::future_header_promise<T...> pointers. If a function accepting a header pointer is commented as "takes ref", then that function is going to assume ownership of your reference, so unless you incref() the header first you've effectively lost the header to move semantics.

Added test/regression/issue277.cpp

→ <<cset 00b7b1524c94>>

[Paul Hargrove]

Merged in promise-lifetime-gc (pull request #141)

Promise lifetime GC

Revamped how promises are handled internally. We now take advantage of the fact that a promise is just a pointer to a shared object which is also aliased by its future('s). We enable the same refcounting garbage collection that governs futures, but hide it from the end-user. The goal of this work is to allow the user to drop promises which are the completion targets of outstanding comm operations, yet still have the futures obtained from that promise function correctly. See issue 277.

There is a new detail::promise_shref<T...> class that implements all of promise<T...> plus implements all constructors with aliasing refcounting semantics (the default ctor allocates a new promise). This class also allows easy access to the underlying detail::future_header_promise<T...>*. promise<T...> simply inherits this class privately and then explicitly whitelists all the base members except the aliasing constructors. Use detail::promise_as_shref() to cast from promise& to detail::promise_shref&.

The backend API pertaining to promises has been changed to take naked detail::future_header_promise<T...> pointers. If a function accepting a header pointer is commented as "takes ref", then that function is going to assume ownership of your reference, so unless you incref() the header first you've effectively lost the header to move semantics.

Added test/regression/issue277.cpp

Approved-by: Paul Hargrove Approved-by: Dan Bonachea

→ <<cset fd35b34216e7>>

[Dan Bonachea]

The implementation side of this was resolved in pull request #141

Specifying these improvements are a task in spec issue 156