Thursday, October 27, 2011

range copy

The range library proposal for the std library included copy_range which required that the dest range have a constructor that took begin and end iterators. This was not applicable to C struct ranges like UNICODE_STRING.

I decided to fix this by following the pattern for the begin and end free-functions. A free-function named copy calls a free-function named range_copy via ADL that can be overloaded for each Range type. The default range_copy has the same behavior that the proposed copy_range provided, but now other range_copy overloads can be written.

UNICODE_STRING usage

This snippet shows some of the operations now enabled.

auto helloRange = as_literal(L"hello");
auto title = copy<std::wstring>(helloRange);

auto unicodeHello = copy<UNICODE_STRING>(helloRange);
auto stringRange = make_range(unicodeHello);
auto unicodeTitle = copy<UNICODE_STRING>(
    make_range_raw(title)
    );
stringRange = make_range(unicodeTitle);
  • line 1 will make a range<const wchar_t*> that points to the static string array.
  • line 2 will make a std::wstring that holds a copy of the static string array.
  • line 4 will make a UNICODE_STRING that points to the static string array.
  • line 5 will make a range<PWSTR> that points to the static string array.
  • line 6 will make a UNICODE_STRING that points to the wstring copy of the static string array.
  • line 9 will make a range<PWSTR> that points to the wstring copy of the static string array.

Implementation

maintained here

template< class RangeTo, class RangeFrom >
auto range_copy(RangeFrom && r, RangeTo*) ->
decltype(
  RangeTo(
      begin(std::forward<RangeFrom>(r)),
      end(std::forward<RangeFrom>(r))
  )
)
{
  return RangeTo(
      begin(std::forward<RangeFrom>(r)),
      end(std::forward<RangeFrom>(r))
      );
}

template< class RangeTo, class RangeFrom >
auto copy(RangeFrom && r) ->
decltype(
  range_copy(
      std::forward<RangeFrom>(r),
      reinterpret_cast<RangeTo*>(nullptr)
  )
)
{
  return range_copy(
      std::forward<RangeFrom>(r),
      reinterpret_cast<RangeTo*>(nullptr)
      );
}

line 27 passes in a nullptr cast to a RangeTo* this dummy parameter is ugly but required to enable Argument-Dependent-Lookup (ADL) when range_copy is implemented in RangeTo's namespace. I considered using the parameter rather than returning a RangeTo by-value, but then RangeTo must be default-constructable since the copy free-function would have to have one on the stack in order to pass a pointer into range_copy. The current definition allows the overload for RangeTo to use any constructor.

UNICODE_STRING implementation

Now enabling UNICODE_STRING for use with the range library requires only this

// enable UNICODE_STRING <-> range

PWSTR range_begin(const UNICODE_STRING& string)
{
  return string.Buffer;
}

PWSTR range_end(const UNICODE_STRING& string)
{
  return string.Buffer + (string.Length / 2);
}

template< class RangeFrom >
UNICODE_STRING range_copy(
  RangeFrom && r,
  UNICODE_STRING*
)
{
  UNICODE_STRING result = {};

  result.Buffer = const_cast<PWSTR>(
      begin(std::forward<RangeFrom>(r))
      );
  result.Length = size_cast<USHORT>(
      size(std::forward<RangeFrom>(r)) * 2
      );
  result.MaximumLength = size_cast<USHORT>(
      size(std::forward<RangeFrom>(r)) * 2
      );

  return result;
}

Tuesday, October 25, 2011

range size_cast

The range library proposal for the std library included size which calculated the distance between begin(r) and end(r). This value usually ends up in a ptrdiff_t. I often need to put the size of a range into much smaller size types when using C APIs and C structs. Just adding a static_cast is no sufficient as I not only want to cast the type, but ensure that the value fits.

I added size_cast. It requires an explicit ReturnType template parameter. Then it can verify that the value will fit and only then do a static_cast to coerce the value into the ResultType.

The next post will demonstrate some usage.

Implementation

maintained here

template< class ResultType, class InputType >
ResultType
size_cast(InputType size)
{
  const static size_t
  bitsOfPositiveRepresentationInResultType =
    (sizeof(ResultType) * 8) -
    static_cast<ResultType>(
        std::is_signed<ResultType>::value);
  const static size_t
  bitsOfPositiveRepresentationInInputType =
    (sizeof(InputType) * 8) -
    static_cast<InputType>(
        std::is_signed<InputType>::value);
  typedef
  std::conditional <
  bitsOfPositiveRepresentationInResultType <
  bitsOfPositiveRepresentationInInputType,
  InputType,
  ResultType
  >::type
  check_type;
  check_type size_check = static_cast<check_type>(size);
  FAIL_FAST_IF(
    (false,
      (std::is_signed<InputType>::value && size < 0)) ||
        (size_check >> (
          bitsOfPositiveRepresentationInResultType - 1)) != 0,
    ERROR_INVALID_PARAMETER
  );
  return static_cast<ResultType>(size);
}

Thursday, October 20, 2011

make_range_raw

I wrote a range library some years ago and then found a proposal to include a range library in the std library.

I adopted the proposed library and over time I have added additional features to ease usage of C APIs. One feature I added is make_range_raw.

make_range works by requiring that the Range passed in has support for the begin and end free-functions. This produces range<Iterator> where Iterator is a raw pointer for built-in arrays but uses the iterator type defined by the Range when it is a collection like vector or wstring. This is the desired behavior for make_range but when trying to interface between collections and C APIs it would be better to access the raw pointer for contiguous array collections like vector and wstring.

make_raw_range requires that the collection support raw access via operator []. Using &r[0] for begin and &r[0] + size(r) for end produces range<Iterator> where Iterator is always a raw pointer. (for well behaved collections this is true. vector<bool> is not well behaved)

Implementation

maintained here

template< class Range >
auto
make_range_raw(Range && r) ->
decltype(
  make_range(
      &r[0],
      &r[0] + size(r)
  )
)
{
  if (size(r) == 0) {
    decltype(
      make_range(
          &r[0],
          &r[0] + size(r)
      )
    ) result;
    return result;
  }
  return make_range(
      &r[0],
      &r[0] + size(r)
      );
}

template< class Range >
auto
make_range_raw(
  Range && r,
  typename
  range_difference<Range>::type advance_begin,
  typename
  range_difference<Range>::type advance_end
) ->
decltype(
  make_range(
      &r[0],
      &r[0] + size(r)
  )
)
{
  decltype(
    make_range(
        &r[0],
        &r[0] + size(r)
    )
  ) result;
  if (size(r) != 0) {
    result = make_range(
        &r[0],
        &r[0] + size(r)
        );
  }
  result.advance_begin(advance_begin);
  result.advance_end(advance_end);
  return result;
}

Tuesday, October 18, 2011

catch(…) is harmful and should be avoided

A common use of catch(...), even in the STD library implementation, is to free objects or to return to a known state on failure.

catch(...) has no information about the exception and therefore there is no way to reason about whether the code in the catch block will corrupt the process. Thus any code in a catch(...) is a potential danger to the process and the data it manages.

Whenever an exception is thrown and the search for a catch encounters a catch(...) block it must run all the destructors for the code inside the matching try to get the stack back to the correct state to run the catch block. At best this modifies the state, when it doesn't corrupt it. Then the catch block is likely to immediately rethrow the exception with the state at the most relevant part of the stack (where the throw occurred) erased.

This erasure is particularly unwanted when the exception is ultimately not handled and a Windows Error Report is generated with a dump of the state after the unhelpful catch(...) erased the part that would be most important to determine how to fix the bug.

Windows Error Reporting (WER) has changed the way I write code. I try to exit the process quickly (FAIL_FAST) whenever I reach an unexpected state. When there are no catch(...) blocks in the way I get great bugs generated directly from the WER with no repro necessary and I quickly issue a fix.

The good thing is that none of the catch(...) blocks are needed and that the replacements do not corrupt the state when the exception type is not known to the call stack. The common case where you might use catch(...) to free an allocation or restore state can be replaced by an unwinder. In the case where catch(...) is used to suppress an exception it should be replaced with a FAIL_FAST_ON_THROW([]{});. This will not suppress the exception (which as described earlier invites data corruption), instead when an exception that is not expected and handled reaches this barrier a WER will be generated and the process will exit without any corruption.

These boundaries can be enforced using error contract functions:

template<typename Function>
HRESULT HResultErrorContract(Function && function)
{
  HRESULT result = S_OK;
  FAIL_FAST_ON_THROW(
  [&] {
    // any C++ exception that is uncaught or any SEH
    // will cause the process to exit
    try
    {
      unique_hresult hresult = (
        std::forward<Function>(function)());
      result = hresult.get();
    } catch (const std::bad_alloc&) {
      result = E_OUTOFMEMORY;
    } catch (const unique_winerror::exception& e) {
      result = HRESULT_FROM_WIN32(e.get());
    } catch (const unique_hresult::exception& e) {
      result = e.get();
    }
  }
  );
  return result;
}

HRESULT MyDllExport()
{
  // no exception can get past
  // HResultErrorContract
  return HResultErrorContract(
  [&]() -> unique_hresult {
    // It is safe to throw C++ exceptions
    unique_hresult hresult;
    // RestoreState is only called on failure
    ON_UNWIND(unwindWork, []{ RestoreState(); });
    hresult = Work();
    if (hresult.ok()) {
      unwindWork.Dismiss();
    }
    return hresult;
  }
}

Thursday, October 13, 2011

error contract functions

In code for Windows there are many places that are boundaries across which C++ exceptions cannot safely travel.

The most accurate way to describe the boundaries is to say that C++ exceptions cannot be sent across modules (exe and all and sys are all examples of modules). It may not be completely clear from that statement when a module boundary is crossed. Here are some examples that should help reason about when a module boundary is being crossed. The most straight forward situation is when a function is exported from a dll so that it can be called from a different module. but it can get considerably more abstract when you think of dll methods that return COM interfaces or structs containing function pointers. Then add all the PROC's used in Windows programming. WNDPROC, DLGPROC and so many other PROC's are all functions in one module called from a different module.

Any C++ exceptions that occur in these boundary functions must be stopped before the calling module try's to process them. The problem is that exception types are not always the same in each module. if the calling module try's to process an exception from a different module it could be that the type has different members or that the size of the members is different and the constructors, destructors and other methods compiled into the calling module are the wrong methods for an instance of the type that was constructed in the called module. Crashes or data corruption will ensue.

When building all these boundary functions it becomes important to centralize the catch blocks used to convert exceptions to errors and the FAIL_FAST for uncaught exceptions. Without centralization there is a lot of duplicated code.

With lambdas and perfect-forwarding using r-value references we can build error contract functions that will centralize the boundary contract for errors in one function and apply that contract to many functions. Here is an implementation of a error contract function for use with boundary functions that return HRESULT.

template<typename Function>
HRESULT HResultErrorContract(Function && function)
{
  HRESULT result = S_OK;
  FAIL_FAST_ON_THROW(
  [&] {
    // any C++ exception that is uncaught or any SEH
    // will cause the process to exit
    try
    {
      unique_hresult hresult = (
        std::forward<Function>(function)());
      result = hresult.get();
    } catch (const std::bad_alloc&) {
      result = E_OUTOFMEMORY;
    } catch (const unique_winerror::exception& e) {
      result = HRESULT_FROM_WIN32(e.get());
    } catch (const unique_hresult::exception& e) {
      result = e.get();
    }
  }
  );
  return result;
}

HRESULT MyDllExport()
{
  // no exception can get past
  // HResultErrorContract
  return HResultErrorContract(
  [&]() -> unique_hresult {
    // It is safe to throw C++ exceptions
    unique_hresult hresult;
    hresult = Work();
    return hresult;
  }
}

error contract functions are specific to the module they are used in, they are not candidates for a general shared template library. This is because each module uses different libraries and therefore has different exceptions that must be caught and translated.

Tuesday, October 11, 2011

C++ exception implementation on Windows

On windows c++ exceptions are implemented using an exception facility provided by the OS. The OS exception system (Structured Exception Handling or SEH) does not have the same semantics as C++ exception handling.

Windows SEH works in C or assembly code as well as C++. the C++ compiler and the OS are both involved. SEH is used to report many runtime errors and logic errors in code. Often they are unrecoverable. Access Violation, Stack Overflow, RPC errors, are all reported using SEH exceptions. Here is some code that uses SEH

LONG WINAPI MyExceptionFilter(
  __in  struct _EXCEPTION_POINTERS *ExceptionInfo,
  __in DWORD ExceptionCode
)
{
    // code in an exception filter must be 
    // very robust, careful and have minimal 
    // dependencies. often t\filters are run 
    // at times of extreme duress or with 
    // malicious intent

    //
    // must return one of these three values:

    // EXCEPTION_CONTINUE_EXECUTION
    //   re execute the instruction that 
    //   triggered the exception. if it
    //   fails again the new exception 
    //   will be marked
    //   EXCEPTION_NONCONTINUABLE_EXCEPTION

    // EXCEPTION_CONTINUE_SEARCH
    //   call the next registered 
    //   exception filter

    // EXCEPTION_EXECUTE_HANDLER
    //   run all the finally blocks for
    //   nested try's and then runs the 
    //   __except block and then runs 
    //   the finally block and then 
    //   continues after the __try/
    //   __except/__finally

    return EXCEPTION_CONTINUE_SEARCH;
}

void* ptr = nullptr;
__try
{
  ptr = malloc(1);
  if (!ptr) {
    __leave;
  }
  Work(ptr); // might AV or overflow stack, etc..
  // or explicitly call RaiseException() to 
  // raise an SEH
} __except (
    // registers MyExceptionFilter for any SEH
    // that occurs in the __try
    MyExceptionFilter(
      GetExceptionInformation(),
      GetExceptionCode()))
{
  // MyExceptionFilter returned 
  // EXCEPTION_EXECUTE_HANDLER
}
__finally()
{
  // the stack is unwinding due to a return
  // or an exception that is handled here or
  // up the stack from here
  if (ptr) {
    free(ptr);
  }
}

Hopefully it is obvious that an SEH exception will not cause C++ destructors to be called without some more work. The C++ compiler supports __try/__except/__finally and also supports try/catch, but not in the same function. Also, the C++ compiler will not allow __try/__except/__finally to be used in a function that has a local variable with a destructor.

Disclaimer - this is inaccurate yet provides a mental picture suitable for reasoning about the intersection of SEH and C++. - When the C++ compiler sees a try it inserts a __try, and an __except with a filter that is passed information about the catch clauses and catch blocks and destructors in scope. The C++ compiler replaces each throw with a RaiseException() that stores the exception object in the SEH ExceptionInformation. Then the SEH mechanism calls the registered filter and the filter tries to match the catch block type to the exception object type. If a catch block matches the filter calls the appropriate destructors and the appropriate catch block and then returns EXCEPTION_EXECUTE_HANDLER to continue after the catch block.

The C++ compiler also does not implement throw() semantics. Using what we know we can implement those semantics:

#define FAIL_FAST_FILTER() \
  __except(FailFastFilter(GetExceptionInformation())) \
  { \
  } do {} while(0,0)

inline
LONG WINAPI FailFastFilter(
  __in  struct _EXCEPTION_POINTERS* exceptionInfo)
{
  RaiseFailFastException(
    exceptionInfo - > ExceptionRecord,
    exceptionInfo - > ContextRecord,
    0);
  return EXCEPTION_CONTINUE_SEARCH;
}

template<typename Function>
auto FailFastOnThrow(
  Function && function) -> decltype(
      std::forward<Function>(function)())
{
  //
  // __ try must be isolated in its own
  // function in order for the compiler
  // to reason about C++ unwind in the
  // calling and called functions.
  //
  __try {
    return std::forward <Function >(function)();
  }
  FAIL_FAST_FILTER();
}

#define FAIL_FAST_ON_THROW(Function) \
  FailFastOnThrow((Function))

HRESULT MyDllExport()
{
  HRESULT result = S_OK;
  FAIL_FAST_ON_THROW(
  [&] {
    // any C++ exception that is uncaught or any SEH
    // will cause the process to exit
    try
    {
      unique_hresult hresult;
      hresult = Work();
      result = hresult.get();
    } catch (const std::bad_alloc&) {
      result = E_OUTOFMEMORY;
    } catch (const unique_winerror::exception& e) {
      result = HRESULT_FROM_WIN32(e.get());
    } catch (const unique_hresult::exception& e) {
      result = e.get();
    }
  }
  );
  return result;
}

Next time we will build error contract functions to reduce the amount of code in each export.

Thursday, October 6, 2011

all smart ptr's should have a replace method

A lot of C++ code ends up interfacing with C functions. std::vector and std::basic_string have been constructed to make it possible to use them with c functions (basic_string::c_str vector::data and vector::operator[])

Smart pointers, however do not interface well with c code. I believe that c function interfacing is unsupported due to concern that address() is too dangerous to expose. While interfacing with c code does require the same return value that address would return, it does not require the same semantics.

The implementation of replace() would call reset() and then return address(). This would mean that the user could not accidentally leak a pointer by using replace()

Here is some code that shows how std::unique_ptr interacts with a c function now and how it would work if it had replace().

struct CoTask_deleter {
  void operator()(void* expired) {
    CoTaskMemFree(expired);
  }
};

unique_hresult hresult;

{
  //
  // without replace
  //
  LPOLESTR rawString = nullptr;
  std::unique_ptr<OLECHAR, CoTask_deleter> string;
  hresult.reset(StringFromCLSID(GUID_NULL, &rawString));
  // memory allocation is not 'owned'
  // any mistake from here through the
  // unique_ptr reset will result in a
  // leak
  if (hresult.ok()) {
    string.reset(raw_string);
    raw_string = nullptr;
    // now the memory is safely owned
  }
}

{
  //
  // with replace
  //
  std::unique_ptr<OLECHAR, CoTask_deleter> string;
  hresult.reset(
    StringFromCLSID(
        GUID_NULL,
        string.replace()));
  // there is no point when the memory is not owned
}

if (!hresult)
{
  return;
}

Tuesday, October 4, 2011

template policies via ADL

I wrote a range library some years ago and then found a proposal to include a range library in the std library.

I liked the design and decided to implement the proposal. One of the coolest features of the proposal is how ADL and decltype are used to implement traits or policies.

Since that time I have continued to refine the use of ADL and decltype to produce policies with vastly improved flexibility, stability and usability then anything I have seen before.

For example (Note: for space reasons this code is incomplete and won't compile. A working version of unique_t called unique_resource is available here) if we start with an existing smart-pointer that has a policy trait for the type and the way to close the type:

// policy based type
template<typename T, typename Close>
class unique_t_classic;

// user code using that type
template<typename T, typename Close>
void function(unique_t_classic<T, Close>& t);

Then at some future time we wish to add an index trait to enable operator[] usage:

// new policy
template<
  typename T, 
  typename Close, 
  typename Index=DefaultIndex<T>>
class unique_t_classic;

Now all the code that was dependent on the original policy set will fail to compile.
Here is the way I would express this functionality today:

template<typename TypeTag>
class unique_t;

template<typename Tag>
void function(unique_t<Tag>& t);

Now we can explore three different implementations of this with different policies without changing any of the above. The initial implementation might look like this.

template<typename TypeTag>
class unique_t
{
public:
  // these functions are looked up via ADL
  // thus this will pick up the definition
  // of unique_t_invalid_value from whatever
  // namespace TypeTag is in, and since TypeTag
  // is not the actual type (in database terms
  // it is a dataless key to the traits) the
  // user controls which namespace the
  // traits are in
  typedef decltype(unique_t_invalid_value(TypeTag()))
  type;
  //...
  void reset() {
    if (t != unique_t_invalid_value(TypeTag())) {
      unique_t_reset(t, TypeTag());
      t = unique_t_invalid_value(TypeTag());
    }
  }
private:
  type t;
};

A user might write code like this:

// Usability is provided by allowing simple
// and static definitions of specific 
// template instantiations
namespace detail
{
namespace file
{
struct tag {};
HANDLE unique_t_invalid_value(tag &&)
{
  return INVALID_HANDLE_VALUE;
}
void unique_t_reset(HANDLE value, tag &&)
{
  make_winerror_if(!CloseHandle(value)).suppress();
}
}
}
typedef unique_t<detail::file::tag>
unique_file;

Now it is time to make some changes to unique.
This will add optional indexing capability:

template<typename TypeTag>
class unique_t
{
public:
  ...
  auto operator[](
    size_t at) -> decltype(
        unique_t_index(at, TypeTag())) {
    return unique_t_index(at, TypeTag());
  }
private:
  type t;
};

unique_file still works as before. It does not support operator[] because it does not define unique_t_index.
More dramatic changes can be made without breaking existing code. This will make the type trait optionally independent of the return value of unique_t_invalid_value:

//
// This is a completely optional type
// it merely provides a succinct way 
// to create a type with a typedef 
// of the correct name 
//
template<typename T>
struct unique_t_traits_builder {
  typedef T
  type;
};

namespace detail
{
//
// this implements the optional part.
//
// notice that neither of these functions
// are implemented, they are only used in 
// declspec so no implementation is referenced
//
// the users definition of unique_t_traits
// needs no implementation either.
//

// this is used if the user supplied a 
// unique_t_traits for the TypeTag
template<typename TypeTag>
auto resolve_unique_t_traits(
  size_t) -> decltype(unique_t_traits(TypeTag()));

// the is used if the user only supplied 
// unique_t_invalid_value for the TypeTag
template<typename TypeTag>
unique_t_traits_builder<unique_t_invalid_value(TypeTag())>
resolve_unique_t_traits(...);
}

template<typename TypeTag>
class unique_t
{
public:
  typedef decltype(
    detail::resolve_unique_t_traits(TypeTag()))
  traits;

  typedef typename traits::type
  type;
  // ...
  void reset() {
    if (t != unique_t_invalid_value(TypeTag())) {
      unique_t_reset(t, TypeTag());
      t = unique_t_invalid_value(TypeTag());
    }
  }
private:
  type t;
};

Viola! no change to user code was required even though the implementation changed dramatically and the traits are different. This provides stability and flexibility that previous policy patterns lacked.