Showing posts with label c++. Show all posts
Showing posts with label c++. Show all posts

Thursday, January 11, 2018

C++, the cause and solution to life's pimpl problems


Can a programming language invite programmers to write anti-patterns that makes them write more code that is also harder to follow? Certainly, it can.

PIMPL is a much hyped code pattern in C++ to separate a class's public declaration from the implementation detail by wrapping a pointer to the implementation object in the public class. This is what the user of the public class sees. The pointer is the only member of the public class.
// In xyzzy.h

class Xyzzy {
 public:
  Xyzzy();   // Constructor.
  ~Xyzzy();  // Destructor.

  void Foo();

 private:
  class Impl;  // Incomplete forward declaration to the implementation.
  Impl *pimpl_;  // Pointer to incomplete class is allowed.
};
The implementation would be written like this, hidden away from the user.
// In xyzzy.c

class Xyzzy::Impl {
  ...
  void Foo() {
    // Actual code.
  }
  ...
  // All private members are declared in the Impl class.
};

Xyzzy::Xyzzy()  // Constructor.
  : pimpl_(new Impl) {}

Xyzzy::~Xyzzy() {  // Destructor.
  delete impl_;
}

void Xyzzy::Foo() {
  impl_->Foo();
}
There are some elaborate concerns like constness preservation, use of smart pointers, copying and moving, memory allocation, and generalizing the boilerplate to a template, but I want to take a step back and look at what PIMPL accomplishes, and why it is necessary.

The main reason for using PIMPL is to reduce compilation dependencies, so that changes made to the implementation class would not force the user of the public interface to have to recompile code. Recompilation is necessary when the change breaks binary compatibility. In C++, a change could break binary compatibility for banal reasons like adding a private member to a class.

When class members are added or removed, the size of the class would change. In C++, it is the caller's responsibility to prepare memory storage for the object, regardless whether the object is stack or heap allocated. Without recompilation, the storage might be too small. Bigger storage is not a problem, but the compiler has no way of telling the old size. With PIMPL, the size of the public class is always just a single pointer to the implementation object, so it stays the same. It shifts the responsibility of storage preparation from the user to the implementation.

Another type of change that warrants recompilation is when virtual methods are added or removed, which changes the ordering of function pointers in the vtable. Without recompilation, the old code would end up calling the wrong virtual method since the index changed. PIMPL would not be able to alleviate this type of recompilation; adding or removing non-virtual methods from the public class would still require recompilation under PIMPL.

One might ask, instead of PIMPL, why not use the abstract base class with a static constructor? It would look something like this for the public interface.
// In xyzzy.h
class Xyzzy {
 public:
  static Xyzzy *New();  // Static constructor.
  virtual ~Xyzzy();  // Virtual destructor.
  virtual void Foo();

 protected:
  Xyzzy();  // Not to be constructed directly by user.
};
And the implementation:
// In xyzzy.c
class XyzzyImpl : public Xyzzy {
 public:
  void ~XyzzyImpl() override {
    ...
  }

  void Foo() override {
    ...
  }

  // Other members.
};

Xyzzy *Xyzzy::New() {
  return new XyzzyImpl;
}
The problem is that the abstract base class forces all methods to be virtual, and virtual method calls are more expensive because it's harder to do branch prediction with function pointers. The responsibility to manage storage is shifted to the static constructor, so adding or removing members to the base class shouldn't affected binary compatibility. Even so, it still requires recompilation in practice, so members should be declared in the implementation class only.

The common theme here is that any change to a class in C++ requires recompilation, period. That's because the compiler can't tell what changed, so it can't tell whether the change may or may not affect binary compatibility. Contrast this with C, where user of a struct never has to know its size, without relying on virtual methods.
// In xyzzy.h

struct xyzzy;  // Incomplete type.

struct xyzzy *new_xyzzy();              // Constructor.
void delete_xyzzy(struct xyzzy *this);  // Destructor.
void xyzzy_foo(struct xyzzy *this);     // Method foo().
Although most build systems would still recompile the translation unit that includes xyzzy.h for posterity, it doesn't have to if the changes are binary compatible. This is why an executable compiled with an older header could still be dynamically linked with a newer version of the shared library without recompilation, and it would still work.

In the end, I think any effort to reduce recompilation for C++ code is futile. C++ is inherently designed for whole-program compilation. There are other reasons, like how template instantiation requires the implementation source code to be available. But any class would require the user to know its size, and one has to go through great lengths to hide that from the user in order to ensure binary compatibility.

Clearly, PIMPL is an anti-pattern that is motivated by the way C++ is designed. It's a problem that C never has to worry about.

Tuesday, December 13, 2016

Fermat Numbers and Bit Mask

There is a little known application of Fermat numbers for generating bit masks, that I discovered back in 2010 while implementing "counting the number of one bits" using C++ template meta-programming. In the algorithm, bit masks such as 0x55555555, 0x33333333, 0x0f0f0f0f, etc. are used to mask out bits in specific locations. These bit masks can be generated by dividing the maximum integer 0xffffffff (or simply ~0u) against Fermat numbers 3, 5, 17, 257, 65537, etc.

HexBinaryExpression
0x5555...0101010101010101...~0u / 3
0x3333...0011001100110011...~0u / 5
0x0f0f...0000111100001111...~0u / 17
0x00ff...0000000011111111...~0u / 257
and so on...

It's not a coincidence that integers with all one bits set can be divided cleanly by a Fermat number, and this works with 8-bit, 16-bit, 32-bit, 64-bit, and beyond. To understand why, a \(k\)-bit all-one integer is \(2^k - 1\). In particular, \(k = 2^n\) in our case. We can factor \(2^{2^n} - 1\) using the formula \(a^2 - b^2 = (a + b)(a - b)\) we learned in grade school, here using the special case \(b = 1\), so \(a^2 - 1 = (a + 1)(a - 1)\).
\begin{align}
2^{2^n} - 1 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 1}} - 1) \\
 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 2}} + 1)(2^{2^{n - 2}} - 1) \\
 & = (2^{2^{n - 1}} + 1)(2^{2^{n - 2}} + 1)(2^{2^{n - 3}} + 1)(2^{2^{n - 3}} - 1) \\
 & = \dots
\end{align}
Conveniently, the last term \(2^{2^0} - 1\) is just \(1\), so we can write the product in terms of \(F_i = 2^{2^i} + 1\) for the \(i\)-th Fermat number,
\[ 2^{2^n} - 1 = \prod_{i=0\dots n-1}{2^{2^i} + 1} = \prod_{i=0\dots n-1}{F_i} \]
For example,
\(k\)\(2^k - 1\)Expression
23\(3 \)
415\(3 \times 5 \)
8255\(3 \times 5 \times 17 \)
1665535\(3 \times 5 \times 17 \times 257\)
324294967295\(3 \times 5 \times 17 \times 257 \times 65537\)
and so on...

So how are Fermat numbers related to bit mask construction? It turns out that if you write 3, 5, 17, 257, 65537 in binary, you get 11, 101, 1 0001, 1 0000 0001, and 1 0000 0000 0000 0000 0000 0000 0000 0001 respectively. If you multiply 101 (5) and 1 0001 (17), you get alternating patterns of 0101 0101 (85). If you multiply this by 11 (3), you get an 8-bit all-one integer 1111 1111 (255). Conversely, you can take a pattern "out of circulation" by dividing the all-one integer by a Fermat number which is one of its factors.

Appendix: Counting the number of one bits using C++ template meta-programming

We start with the straightforward bit vector algorithm:
x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
// etc.
which can be represented by the following for-loop:
for (int n = 1; n < sizeof(Tp) * 8; n *= 2)
  Tp mask = ~0 / ((1 << n) + 1));
  x = ((x >> n) & mask) + (x & mask);
}
In the template meta-programming version, the template __unroll_shift_mask_add essentially unrolls into the for-loop above, but in a manner that is agnostic to the actual integer type.
template<unsigned int n, typename Tp>
struct __unroll_shift_mask_add {
  static Tp compute(Tp x) {
    Tp y = __unroll_shift_mask_add<n / 2, Tp>::compute(x);
    Tp mask = ~Tp(0) / ((Tp(1) << n) + 1);
    return ((y >> n) & mask) + (y & mask);
  }
};

template<typename Tp>
struct __unroll_shift_mask_add<0u, Tp> {
  static Tp compute(Tp x) { return x; }
};

template<typename Tp>
Tp one_bits(Tp x) {
  return __unroll_shift_mask_add<sizeof(Tp) * 8 / 2, Tp>::compute(x);
}

Sunday, July 10, 2016

C preprocessor hygienic macros

A hygienic macro is a macro that defines variables for its own use without accidentally confusing them with the variables defined by the user of the macro. By design, C/C++ preprocessor macro performs only simple string substitution which is not hygienic. That means those using a macro has to be mindful of the macro's definition and avoid using variables of already used names. This also means that such macro cannot be arbitrarily nested in scope, since nesting will cause variable conflict.

But hygienic macro is really useful for defining language extensions in the form of syntactic sugars. My motivation example is a foreach loop that was not added to the C++ language until C++11. Although C++ now has a ranged-for syntax, it is still useful for a plain C library that implements containers. There may be other use cases for macro hygiene, so I want to explain the technique I have been using for a number of years.

The "ranged-for" syntax in C++11 iterates over all items in a container sequentially:
std::vector<int> xs;
for (int& x : xs) {
  // User code.
}
I defined a macro to accomplish something similar:
std::vector<int> xs;
foreach(int& x, xs) {
  // User code.
}
The idea is that this macro is a synthetic sugar that expands to a for-loop using an iterator:
std::vector<int> xs;
for (std::vector<int>::iterator it = xs.begin(); it != xs.end(); ++it) {
  int& x = *it;
  // User code.
}
But this synthetic sugar does not quite work: we need to define the variable int& x on the user's behalf. The user shouldn't be expected to add int& x = *it; to his block statement. For that, I used another for loop to introduce the variable but only run it once.
std::vector<int> xs;
for (std::vector<int>::iterator it = xs.begin(); it != xs.end(); ++it)
  for (int& x = *it; true; break) {
    // User code.
  }
What if the user code also contains a break statement? It will only break the inner for loop that introduces the variable binding but the outer for loop will continue. Unfortunately C/C++ has no labeled break. One solution is to use a variable to keep track of how the break happened.
std::vector<int> xs;
for (bool next = true; next; (next = false))
  for (std::vector<int>::iterator it = xs.begin(); next && it != xs.end(); ++it)
    for (int& x = *it; !(next = false); ({ next = true; break; })) {
      // User code.
    }
We wrap the user code around a sentinel variable initially set to false before executing the user code, and reset it to true after. If the user code breaks, the sentinel variable remains false, so the next iteration will not run. This works, but now the code introduces two implicit variables, it and next.

The simplest way to construct a hygienic macro is by giving it explicit variable names, so we can define the foreach macro like this:
#define FOR_EACH_NAMED(decl_var, container, it, next)                   \
  for (bool next = true; next; (next = false))                          \
    for (autovar(it, container.begin()); next && it != container.end(); ++it) \
      for (decl_var = *it; !(next = false); ({ next = true; break; }))
Instead of writing the explicit iterator type std::vector<int>::iterator, we use another macro autovar() here to declare a variable with a type that is inferred from an expression, using a GCC extension __typeof__(). C++11 now has decltype which should be used for C++ code.
#define autovar(var, exp) __typeof__(exp) var = (exp)
Now, the hygienic macro simply generates unique variable names and invokes the explicit macro.
#define foreach FOR_EACH

#define FOR_EACH(decl_var, container) \
  FOR_EACH_NAMED(decl_var, container, VAR(__it_), VAR(__next_))
Now the interesting part is the VAR() macro that creates a unique variable name using a given prefix. Using a human readable prefix makes the generated code somewhat easier to debug. We define a UNIQUE() macro to generate a unique token, and this needs to be concatenated with the prefix only after evaluating the unique token, not before. For this to work, we use a JOIN() macro that does double concatenation.
// Creates a hygienic identifier with a given prefix name.
#define VAR(name) JOIN(name, UNIQUE())

// Concatenates expanded macro.
#define JOIN(a, b) JOIN_2(a, b)
#define JOIN_2(a, b) a ## b
As to the implementation of UNIQUE(), we use __COUNTER__, which is a GCC extension, if present. Otherwise the current line number __LINE__ would suffice.
#ifdef __COUNTER__
#  define UNIQUE() __COUNTER__
#else
#  define UNIQUE() __LINE__
#endif
In summary, a good way to construct hygienic C preprocessor macro is by first defining an explicit version, then an implicit hygienic version using a unique variable generator.
#define FOO_NAMED(arg0, arg1, /* ... */, var0, var1, /* ... */) /* ... */
#define FOO(arg0, arg1, /* ... */) \
  FOO_NAMED(arg0, arg1, /* ... */, VAR(__var0_), VAR(__var1_), /* ... */)

Saturday, February 6, 2016

Generic setuid/setgid wrapper for scripts

The setuid or setgid bit on a binary executable allows the binary to run with the effective uid or gid set to the owner of the executable, rather than the user that runs it. It is a rudimentary way for anyone to impersonate as the executable owner, so the owner can provide limited services using the owner's identity, including using files only accessible by the owner.

Historically, system binaries such as /sbin/ping are setuid root since ping requires privileged network access, but capabilities have reduced those needs. Binaries that manipulate privileged files still need to be setuid root, such as /bin/passwd. To setuid non-root user is less common but is still useful to control filesystem access.

Sometimes it is useful to write a shell script and making it setuid or setgid for the sake of controlling filesystem access. Many experts generally warn against setuid shell scripts. Here are the common security issues specific to scripts.
  • Anyone could create a symlink that resembles shell options and obtain an interactive shell with elevated privileges.
  • Anyone could create a symlink to a genuine setuid script, then after the OS executes the interpreter, perform a symlink switcheroo to a malicious script.
  • Command line interpretation can be changed by PATH or IFS.
Some people advocate (warning: bad advice) creating a binary specifically for executing the shell, but it can render other safety guards ineffective. The dynamic loader is more careful with the LD_PRELOAD and LD_LIBRARY_PATH directives with a setuid executable. But in this case, only the wrapper binary is setuid, but the shell run under is not, so it will pull in the whole slew of dynamic loading hooks unless we sanitize the environment.

One technique that an OS overcomes the switcheroo problem is to open the script file and pass /dev/fd/N to the interpreter, which ensures the same file is seen by the OS and the interpreter. This must be explicitly enabled on the OS and is still ignored by Linux. At least on Mac OS X, the interpreter's own setuid bit is also ignored.

When it comes to my own need, it basically boils down to:
  1. Don't bother with setuid/setgid, but use sudo which sanitizes environments. My use case is most similar to the line "ALL ALL = (script-owner) NOPASSWD: /path/to/script" in /etc/sudoers, to be run as "sudo -u script-owner /path/to/script". But sudoers manual begins with a "Quick guide to EBNF" which scares me.
  2. Rewrite my shell script as a full blown C program. I'm not feeling overly excited about that.
  3. Write a setuid/setgid wrapper binary in C, and the rest as shell script.
Needless to say, I took the last approach.

ps. In doing this, I found out about the shortest open source license called "Fair License" which is appropriate for such a short program.

Monday, September 3, 2012

Mistake in my RC4 implementation

Jim Wilcoxson approached me two days ago regarding the skewed distribution I observed in RC4. He sent me a snippet from SQLite's implementation of RC4 and showed that it did not suffer the non-uniform result I saw.

After digging out my old code, I found two mistakes I made. One in the key scheduling algorithm:
  void initialize(const char *begin, const char *end) throw() {
    for (size_t i = 0; i < 256; ++i)
      s_[i] = i;

    const char *key = begin;
    uint8_t j = 0;

    for (size_t i = 0; i < 256; ++i, ++key) {
      if (key == end) key = begin;
      j = j + s_[i] + *key;
      std::swap(s_[i], s_[j]);
    }
  }
In the original code, I had forgotten to ++key, so the key scheduling is always done on the first byte of the key only. The addition for the fix is highlighted in yellow.

Another mistake is an index out of bounds error in the generation of bytes.
  uint8_t next() throw() {
    i_ = i_ + 1;
    j_ = j_ + s_[i_];
    std::swap(s_[i_], s_[j_]);
    return s_[s_[i_] + s_[j_]];
  }
There is an array index out of bounds error in the return line. The reason is that in C/C++ compiler, the intermediate result of an expression, if it's an int, does not inherit the int size of the sub-expressions, but instead is word sized. Since both s_[i_] and s_[j_] are (0...255), half of the times the result is in (256...511) which accesses some memory beyond s_[]. This explains why I get a skew where most byte value tallies are halved.

The fix is to replace the return line as follows:
    return s_[(uint8_t) (s_[i_] + s_[j_])];
Where an explicit cast to uint8_t solves the index out of bounds problem.

The suggestion I gave, to add ^ j, only obscures the problem.

Fortunately my code has never been used in a production system. It was written quickly to give me a PRNG for a memory usage simulator I wrote last year for testing a memory allocator where the PRNG (1) must not use memory allocation itself, (2) must not use locking, (3) is reasonably fast and easy to implement. The implementation satisfied all my original requirements but was not RC4.

Wednesday, July 18, 2012

Contiki protothreads

I just want to make a note for myself about Protothreads in Contiki operating system, which is an operating system for devices that are extremely memory constrained. Here are some examples of protothreads.

The protothreads implementation can be found in core/sys/pt.h. A protothread is a function that returns a char indicating its state. The states are PT_WAITING, PT_YIELDED, PT_EXITED, and PT_ENDED. Each operation that causes the thread to block actually makes the function return, so the values of local variables are not preserved.

The resume execution of a protothread is based on “local continuation” which has two implementations. One uses the switch statement to create a Duff's device (see core/sys/lc-switch.h), and another one based on a GCC __label__ extension (see core/sys/lc-addrlabels.h).

Despite the simplicity of the implementation, here are limitations of protothreads:

  • Local variables are in undefined state after context switching, so they must be used extremely carefully. Most examples will let the thread take an external “context” struct argument and store state there.
  • Context switching can only happen inside the main protothread routine but not in sub-function calls. This limitation is very similar to Cilk (not surprising because Cilk is a compiler that generates code very similar to that of protothread).
I think that continuation passing style is the answer. And it looks like someone else agrees.

Friday, February 11, 2011

How many aligned address space can I allocate via mmap?

Suppose I want to allocate a naturally aligned piece of memory through mmap(), say I want to allocate a 16KB block of memory aligned to 16KB, what is the greatest amount of memory inside the address space I could allocate in that way? What if I want to allocate 4MB aligned to 4MB? Or 16MB aligned to 16MB? The table is the result in number of that sized chunks and the total amount in GB.

OS4KB16KB4MB16MB64MB
Mac OS X 10.5.8900227 (3.43GB)225056 (3.43GB)877 (3.43GB)217 (3.39GB)52 (3.25GB)
Linux 2.6.18 (32-bit)1048173 (4.00GB)262040 (4.00GB)1020 (3.98GB)252 (3.94GB)59 (3.69GB)
Linux 2.6.18 (64-bit)6168666 (23.53GB)1540236 (23.50GB)6016 (23.5GB)1504 (23.5GB)376 (23.5GB)

The machine that ran the 64-bit test is an AMD Opteron 8220 SE with 40 bit physical address lines (1024 GB) and 48 bit virtual address lines (262144 GB). However, I can't seem to actually allocate that much memory at all.

The source of the program can be found here (alignedmmap.c). Note that since the address is never touched, this does not allocate any actual memory, and the program is so tiny that it hasn't loaded very many shared objects besides standard C library.

Thursday, November 11, 2010

Continuation passing style calling convention for a C-like language

There have been two strong indications where continuation passing style calling convention is necessary for a C-like language.
  • Although user-space thread library exists, it still could not truly implement lightweight processes. The problem is not about kernel-level context switching versus user-level context switching anymore, since both could be equally efficient. The problem is the stack requirement of any thread. Even user-level threads must reserve a large amount of space space (2MB), making it impossible to start thousands of threads unless you use 64-bit address space. The problem with 64-bit address space is that it doubles the storage requirement for pointers.
  • Parallel processing framework such as Cilk goes through great lengths trying to imitate continuation passing style, using Duff's device in generated C code so that execution could "resume" in the middle of a function. This complicates debugging as well as the scheduler of the runtime system.
Inspired by LLVM calling conventions and suggestions for continuation passing style and tail-call optimization, I propose a continuation passing style (CPS) calling convention for a C-like language, where:
  • A code block may be expressed like a function that returns void *.
  • All arguments are passed by register. Additional arguments must be spilled on a memory location, and the last register will be a pointer to the spilled location. The number of registers is machine-dependent, but at least two arguments are allowed.
  • Variadic argument must be spilled in memory as a variable length array.
  • One register is reserved for stack pointer, which must be restored to its original value when the control flow leaves the code block.
  • The stack is useful for calling a conventional C function, or for spilling block-local variables. Scope-local variables that span multiple blocks must be spilled to a heap-allocated location.
  • A code block transitions into another code block using a tail-call with a return statement.
  • It is possible to return from a continuation passing style code block. Stack pointer is restored, a void * value is prepared as the return value, and the function returns like a conventional C function (e.g. pops return address from stack, or branches to return address stored in a register, depending on the machine's native calling convention).
  • Only the stack register (and on some architecture, also the return address register) is callee saved. The caller must save all other registers.
Here is a matrix of caller-callee interaction. There are three types of caller: CPS tail-call, CPS non tail-call, and C. There are two types of callee: CPS and C.
  • Caller is CPS tail-call, callee is CPS: arguments are passed in registers, then branches to callee.
  • Caller is CPS tail-call, callee is C: behaves like a regular tail call from a C caller.
  • Caller is C, callee is CPS: all caller registers are saved, arguments are passed in registers, and a call is made as if the CPS callee is a C callee taking no arguments (i.e. return address may be stored on the stack or in a register, depending on the machine architecture).
  • Caller is CPS non tail-call, callee is CPS: a warning may be issued, but otherwise behaves as if the caller is C and callee is CPS.
  • Caller is CPS non tail-call, callee is C; or caller is C, and callee is C: behaves like regular C function call.
LLVM requires both caller and callee use the same calling convention. But unlike LLVM, we anticipate that C function will want to call CPS, and vice versa. It is intentional that CPS calling convention must be a subset of C calling convention.

The language will be used as an intermediate language for compiling higher level language such as ML, Cilk, etc. A typical function in the higher level source language will be broken down to more than one CPS code blocks.

For a source language that wants to use CPS for lightweight processes, it could be necessary for the lightweight processes to reuse the stack of the worker thread, and that context switching must require the stack to be pristine. The lightweight process may only yield to the scheduler when the stack is empty. This condition may be checked in the run-time, or enforced statically at compile time by having a "pristine" attribute (stack is pristine). A pristine CPS callee may only be called by a pristine CPS tail-call caller.

Thursday, June 17, 2010

Lack of Lexical Context Closure Impediment to Abstraction

Lexical context (also called the environment) describes what identifiers need to be present as well as their types in order for a fragment of a program to run. Closure allows a first-class function to refer to its lexical context while being called in the lexical context elsewhere. This is useful for writing algorithms as a higher-order function whose behavior can be customized by a function argument. This is widely understood by functional programming community (LISP/Scheme, ML, Haskell) to be a very powerful abstraction tool.

It is only starting to be noticed by the C++ community. In C++, the std::for_each algorithm can be used to apply a function to elements in a container between two iterators. But only in C++0x can you use it without too much notational overhead.
// From Wikipedia: C++0x
std::vector<int> someList;
int total = 0;
std::for_each(someList.begin(), someList.end(), 
  [&total](int x) { total += x; }
);
std::cout << total;
The idea is that std::for_each would describe a specific kind of for-loop, and its usage makes the intent of the program more obvious. Note that the function argument (in bold) would be called inside std::for_each, which is in a different lexical scope than where the function argument is defined.

When compiling to machine code, a typical way to implement closure is to enclose the environment in a struct, let each function take a pointer to the environment as an implicit argument, and make the function pointer a pair of pointer to the code as well as pointer to the argument. In plain C, it would look like this:
typedef struct env {
  int total;
} env_t;

void anonymous_func(void *ctx, int x) {
  env_t *envp = (env_t *) ctx;
  envp->total += x;
}

typedef struct for_each_int_arg {
  void (*code)(void *, int);
  void *ctx;
} for_each_int_arg_t;

void for_each_int(int *first, int *last, for_each_int_arg_t f) {
  for ( ; first != last; first++)
    f.code(f.ctx, *first);
}

void sum(int *numbers, size_t n) {
  env_t env = { .total = 0 };
  for_each_int_arg func = {
    .code = anonymous_func,
    .ctx = (void *) &env,
  };

  for_each_int(numbers, numbers + n, func);
}
In fact, this technique is prevalent in C programs that take a callback in the form of a function pointer plus a context pointer. A profound implication for callbacks that do not take a context pointer is that the function argument to these higher-order functions can only refer to the global or static variable scope as its lexical context. Unless these functions do not effect external state (i.e. pure, effectless), this limitation makes it hard to encapsulate the state of the program into small reusable discrete units, and therefore a violation of abstraction.

Let's take a look at several C library calls and see what the implication means.
  • qsort(), bsearch(): the compar argument does not take context. It may be fine because compar is supposed to be pure, i.e. causing no side effects. However, neither qsort() nor bsearch() are very generic either; they assume the data to be laid out entirely in a C array. A more general version may require the compar function to take a context, for example when operating on the content of a huge file without reading the content entirely into memory.
  • atexit(): the function argument does not take context. If the exit routine is supposed to synchronize files, databases or remote processes, all the states would have to be global.
  • signal() and sigaction(): the signal handler does not take context, therefore they cannot be modularized. There are legitimate needs for modular signals, such as alarm and broken pipe detection. These will need to seek alternative workarounds.
  • pthread_key_create(): the destructor of a thread-specific key takes the thread-specific value as the context.
  • pthread_cleanup_push(): the cleanup routine takes a context.
  • pthread_create(): the start routine takes a context.
We can see that those library calls that don't take context in the callback can restrict the utility of these library calls.

In C++, the implicit this object pointer with a type parameter can be used together to compensate for the lack of context pointer, using a function object. The type parameter would specify a class that implements operator(), the function call operator. It will be given an implicit this pointer when called. This is how std::for_each worked when C++ did not support lexical context closure. You would have to rewrite the one line of anonymous function in C++0x into several lines of function object, incurring notational overhead that does not justify the axiomatization of a simple for loop construct.

Even so, there are cases where the lack of lexical context closure in C++ can impede abstraction and code reuse.

A while ago, I implemented a Splay tree where the pointer as well as the nodes are abstracted out.
template<class Ptr /* implements pointer<? implements binary_tree_node> */>
struct splay_tree /* implements binary_search_tree */ {
  template<class Compare /* implements unary_compare<Ptr> */>
  static ptr_type&
  find(Compare& cmp, ptr_type& root) throw() {
    ...
  }

  // More functions that operate on splay trees...
}
The idea is that whoever wants to use the Splay tree algorithm will write a node class that implements the binary_tree_node interface (provides accessor and mutator to left and right subtree pointers). The template argument Ptr is the pointer type to the node. The find() function takes a comparable object, which can either be a key or another node, which will be used to find a node in the tree that compares equal to the comparable object. The template argument Compare is the type of the comparable object.

Generalizing the pointer allows an alternative memory model to be used. In my case, I used the splay tree with linear_ptr<> which performs ownership tracking, so I know the algorithm preserves resource ownership. It has been used successfully this way. Another usage of alternative memory model is where a pointer is subscript into a particular array. This allows binary tree nodes allocated from a small array (say < 256 entries) to use just one byte for the pointer.

However, it doesn't work. We could try it like this:
template<typename Index, typename Tp, Tp *array>
class small_pointer {
 public:
  small_pointer(Index i = 0) throw() : i_(i) {}
  Tp& operator*() const throw() { return array[i_]; }
  Tp* operator->() const throw() { return &array[i_]; }
 private:
  Index i_;
};
A seasoned C++ programmer will correctly spot that array—a value of type Tp *— has to be a constant. It turns out that C++'s idea of constant means that the pointer must come from the memory location of a global or static variable. For example, you can't use small_pointer in a function like this.
void foo() {
  int numbers[10];
  for (int i = 0; i < 10; i++) {
    small_pointer<char, int, numbers> p(i);  // error!
    *p = i;
  }
}
C++ compiler will tell you that numbers cannot appear in a constant expression. However, if you think about it, after the code for operator*() is inlined, the statement *p = i would become numbers[i] = i, and it makes perfect sense. However, in the case that the C++ compiler decides to place opeartor*() into its own function, it would not have access to the int array because numbers is in another lexical scope. If C++ correctly supports lexical context closure, it would actually be able to accept any identifier as a pointer to a non-type argument of a template. You would be able to instantiate the small_pointer template class with a function scope identifier as well as a class scope identifier.

Without this abstraction, I would have to re-implement the Splay tree for tree nodes that want to use a compact pointer model because the nodes are stored in an array. This need might be more common than you think, given that embedded devices like Arduino is getting more popular these days. The difference between O(n) and O(lg n) operation can mean a lot to battery life, but O(n) algorithm is often being chosen due to the prohibitive complexity involved to get O(lg n) data structure working in a compact memory layout. I certainly do not look forward to re-implementing Splay tree for each possible compact node layout. This is something that the compiler should do for me.

Tuesday, June 8, 2010

Bridging the high level concept with low level detail

I was fascinated with this blog post written by an undergrad, exclaiming with excitement his teaching fellow's announcement saying that "binary search tree and merge sort are broken." From the detail that he cited (posted at Google Research blog, written by Joshua Bloch, the author of Effective Java book), I think he meant binary search, and not binary search tree. The problem has to do with overflow in this line:
int mid = (low + high) / 2;
The assumption is that low, mid and high are both indices to some array, with low <= mid <= high. When you add low and high, the result could overflow and become negative, and mid becomes negative. This causes array index out of bounds. In Java, the code will crash right away due to the run-time array bounds check. In C/C++, it might access bad memory location and cause undefined behavior, including non-termination. The problem will be a different one if you change int to unsigned int, in which case mid will be smaller than both low and high. Although mid will fall inside array bounds, it's still a violation of loop invariant, which could make the code non-terminating in C (Java doesn't have unsigned int type). The fix that Joshua suggested was to write:
int mid = low + (high - low) / 2;
Another fix, if you know that you're using a binary computer (which is most computer nowadays), is this aggregate magic hack to average two integers using bitwise operators.

I'd like to point out that the algorithm is not broken. An algorithm is a high-level concept of how to do the work. The algorithm is correct, and it's provably correct. What is broken is the program, whose capability is restricted by the finite machine they're run on. However, when you translate from high-level to low-level, the loss in computing power (from infinite state to finite state) causes program error. The problem with the kind of computer science education I'm familiar with is that we often teach computer science in the high-level concept, with the (flawed) mentality that mapping it to low-level program will be straightforward. Only someone who actually writes the program will know that the devil is in the details.

Some programming languages are better at bridging the gap than others; one that came to mind is Scheme, which uses arbitrary precision integer, as well as built-in rational number. It is a very useful language for describing algorithms because many of the machine-specific aspects are hidden by the language and its run-time system. However, programs written in Scheme will run slower because of the arbitrary precision integer arithmetic. ML programs using the IntInf package also share the same benefit and shortcoming.

What I think would be very useful is to write the algorithm as a template program that can be instantiated with different integer sizes, but let the compiler deduce its limits. For example, the binary search bug could be avoided if overflow does not happen. The compiler will generate a precondition requiring that the caller of that function must check that low + high <= INT_MAX. If int is 32-bit, then INT_MAX is 2147483647; if int is 16-bit, then INT_MAX is 32767. Furthermore, since 0 <= low <= high < array_length, it suffices to show that if array_length <= INT_MAX / 2, then the function will be safe. The last step is perhaps not deducible by the compiler, but a programmer can use that fact to convince the compiler that the limits are satisfied.

You can almost write such code in the programming language ATS because the compiler statically checks for integer constraints. You will just have to use #include template technique: prepare the algorithm in a separate include file, while each instantiation will define the concrete type int and the value INT_MAX before including the algorithm. However, the language default + operator does not check for overflow, so you will have to write a new declaration of the + operator function type with the appropriate integer constraint. Maybe I'll write a tutorial in another post.

Thursday, June 3, 2010

strxcpy—More Consistent, Safer String Copying and Concatenation

This is now published as a Google Project under the name strxcpy. The full motivation article that was previously found in this blog post has been relocated here.

The C language makes it easy to write programs with buffer overflow problems, but there is still something the library can do to help the programmer make fewer mistakes. For this reason, we propose strxcpy(), a variant of strcpy() and strcat(), which combines both string copying and concatenation.
char *strxcpy(char *dest, const char *dest_end, const char *src, size_t n);

The function takes two parameters to define the buffer, dest and dest_end. It guarantees that it will not overwrite the memory location past dest_end, and the string at dest is always NUL terminated. Furthermore, it does not require dest to be a NUL terminated string. The return value is a character pointer to the NUL terminator of the dest string, so that we can easily append another string to it by calling strxcpy() again.

We also propose the sprintf() variants using the same idiom.
char *vsxprintf(char *dest, const char *dest_end, const char *fmt, va_list ap);
char *sxprintf(char *dest, const char *dest_end, const char *fmt, ...);

See the motivation for buffer overflow problems.

Friday, March 12, 2010

Use try-finally to prevent resource leak

This is not a tutorial, but a critique of a programming language feature known as try-finally.

Mom always tells you to clean up after yourself, or to put things back to where it was when you're done with it. If you don't do that, your room becomes a mess, and your stuff gets lost. A good programmer also follow a similar rule: if you acquired the ownership of an object, you have to release it. A program that doesn't follow the rule leaks resource every here and there, and it consumes more and more resource without being able to reuse them. Sharing might be a virtue in human etiquette, but it makes resource tracking difficult, and poor tracking will eventually lead to resource leak, both in the real world and inside the computer.

The most prominent kind of resource leak is memory leak, and it is the kind of leak most visible to the user thanks to how Task Manager (or top/ps in Unix) shows you the amount of memory used per program. The symptom is that the program uses more and more memory over time, until the operating system can no longer supply its insatiable gluttony, at which point the program crashes in a nasty way. (Greedy humans will eventually crash in a similar way—a forewarning to people who wanted to work for Google in order to indulge in its unlimited supply of gourmet food).

But even if a programmer is in good faith to clean up after himself, some programming languages make it harder than others to do it. For example, the following construct arises often in a non-trivial program:

thing_t *obj = acquire_thing(...);
...
if (...) {
  ...
  release_thing(obj);
  return ...;
} else {
  ...
  release_thing(obj);
}

The reason we could not factor release_thing(obj) out of the two branches of if-then-else is because the then-clause has a control flow that escapes current scope—the return statement, which could also be a continue or break statement, and our discussion still applies. Fortunately, in this case, the code is manageable because:
  • The clean up only requires releasing one object.
  • There are only two conditional branches, then and else.
Anything more than that, the code starts to become unmanageable.

Some languages make the code easier to write by providing the try-finally construct, so we could rewrite our code like this:

thing_t *obj = acquire_thing(...);
...
try {
  if (...) {
    ...
    return ...;
  } else {
    ...
  }
} finally {
  release_thing(obj);
}

The finally block is executed whenever the control flow escapes the try block. This allows us to write the clean up code only once. You're not required to use exceptions in order to use try-finally.

If your language provides this syntax, the finally statement is the only safe place you put any clean-up code. This is a very useful facility to combat any type of resource leak, especially memory leak. However, taking a look at languages that feature exception handling, many of the languages with finally support are garbage collected, such as C#, Java, JavaScript, Python, Ruby. In particular, C# and Java programs tend to put clean-up code in the object destructor, but garbage collection prevents you from explicitly destroy an object at a precise moment of time. The clean-up code is delayed for an unspecified duration, until the collection cycle kicks in. Rather than using try-finally, you might as well leak the garbage and wait for its collection. This renders try-finally useless for C# and Java—they have no business implementing try-finally in their language.

The only manual memory managed languages with try-finally support are Delphi (Object Pascal) and Objective-C. Try-finally is absent from the C language that is in dire need of the feature.

An interesting exception is C++, which implicitly calls an object's destructor when the control flow leaves the scope the object is declared in, known as resource acquisition is initialization. If we have a pointer to an object allocated in heap using operator new, we could use scoped_ptr<> to delete the pointer when the object leaves the scope. Apparently auto_ptr<> in STL also works, where the copy and assignment semantics moves object ownership from one pointer to another. Some people prefer to outright disallow copying and assignment, so they use scoped_ptr<> instead.

Although scoped_ptr<> and auto_ptr<> facilitates memory resource clean-up, they are not usable with other kinds of resources such as file descriptors and locks, which need other types of clean-up code. Also, any C library managed resource such as graphics context need their own clean-up code. This is why, in C++, it is fashionable to wrap C system or library calls as C++ objects. This requires a humongous start-up effort to want to use C++ along with a C library!

Finally (finally!), I conclude with two recommendations for the language design committee:
  • The C language needs try-finally, even if it does not need to support exception handling.
  • The C++ language also needs try-finally even if it does have exception handling syntax. This makes interoperability with resources managed in the C language easier.

Thursday, June 4, 2009

Multiple definition of... extern inline

When I tried to compile gnutls-2.6.6, I got a lot of these:
.libs/gnutls_compress.o: In function `__strcspn_c1':
/usr/include/bits/string2.h:972: multiple definition of `__strcspn_c1'
.libs/gnutls_record.o:/usr/include/bits/string2.h:972: first defined here
.libs/gnutls_compress.o: In function `__strcspn_c2':
/usr/include/bits/string2.h:983: multiple definition of `__strcspn_c2'
.libs/gnutls_record.o:/usr/include/bits/string2.h:983: first defined here
It turns out that gnutls decides to enforce ISO C99 standard on all its source files, but a lot of the glibc header files use extern inline, which causes GCC to emit a symbol for each extern inline functions. GCC made a change to the extern inline semantics in GCC 4.3 in order to be ISO C99 compliant.
The fix I chose is to add -fgnu89-inline option to GCC throughout. It can be accomplished by invoking configure script like this:
./configure [config_flags...] CFLAGS=-fgnu89-inline
And this solves the problem.

Wednesday, March 4, 2009

stdio.h discard a line from input

There are a few different ways to phrase this question, all relating to stdio.h input handling:
  • What is a better way to discard input other than using fgetc() to read it character by character?
  • How do I discard a line without using fgets() to store it first? It may not clear the line completely due to limited buffer size.
Through creative uses of scanf() this can be done. The format string of scanf() looks like printf(). Rather than passing the value to be printed, you pass a pointer to some memory location to store the value that is parsed. In addition, you can use an astrisk '*' modifier to tell scanf() to discard input.

The first try, scanf("%*s\n"), doesn't really quite do what we wanted. The format "%s" matches only non-white characters (space, tab, newline, etc), so we only discard up to the nearest white space. The "\n" eats another white space (not a newline, contrary to intuition).

The Glibc version* of scanf can match a sequence of characters of any length given character ranges in brackets, sort of like POSIX regular expression character classes. The matching does not care about white spaces, so scanf("%*[^\n]") discards all non-newline characters from the input. But that doesn't quite do the trick yet. The input buffer still has a newline character.

Finally, scanf("%*[^\n]\n") does the trick. It first discards all characters leading to a newline, then discards a white character which must be a new line.

*Update: appears to be ANSI C3.159-1989, so this feature should be portable to any conforming implementations. AIX has it. BSD has it. Glibc is the only one I tried.

Friday, March 30, 2007

Unsafe String Concatenation in C

Many remote exploit vulnerability can be classified into two kinds: memory management problems and confusion of language domains. Memory issues are characteristic of programs written in a low-level language like C. Confusion of language domain is more characteristic of programs written in a high-level scripting language like Perl, PHP and Python. For networked applications that require performance, programmers tend to use a low-level language like C, so memory issues like buffer overrun has been a primary concern in this case.

Because buffer overrun has been Numero Uno cause of security issues, courses and programming books teaching C nowadays have (hopefully) delivered good practices of memory management. One example is to use string functions that limit buffer size. For example, use snprintf() instead of sprintf(), fgets() instead of gets(), strncpy() instead of strcpy(). These functions provide an argument to impose buffer usage limit in order to avoid overrun.

One may be inclined to also recommend strncat() in place of strncat() for string concatenation. However, this deserves closer scrutiny. This function has the following prototype:
char *
strncat(char * restrict s, const char * restrict append, size_t count);
It copies at most count characters from append to the end of s. However, if s is nearly filling up its buffer size, a count that is too large would still overflow the buffer that holds s. We can illustrate this using the following example:
char buf[16];
strcpy(buf, "hello world!");
strncat(buf, " adam!", sizeof(buf)); // wrong!
This code instructs strncat() to append at most 16 bytes, which is sizeof(buf), from " adam!" string. Obviously, strncat() ends up appending the whole string, and this overflows buffer by 3 characters because the string "hello world! adam!" is 18 characters in length plus the terminating NUL.

This is apparently a real problem that once plagued CUPS (printing system for Linux and Mac OS X) and Solaris ufsrestore (incremental file system restore).

Another easy to make mistake is the fact that strncpy() may not properly zero-terminate a string. For example:
char buf[4];
strncpy(buf, "love", sizeof(buf));
printf("buffer contains the string '%s'", buf);
The code would end up printing "buffer contains the string 'love...'" with some garbage. The reason for the garbage is that buffer is no longer properly NUL terminated. You're lucky if the garbage is relatively short. Trying to pass buf to a string processing function that expects NUL terminated string may cause that function to run forever, even for benign functions like strlen().

On the other hand, fgets() reads a string into buffer up to size - 1 characters and properly NUL terminates the string.

All in all, I think these C functions are examples of bad interface design. If someone is reworking the string functions in C, he should focus on making the interface consistent, namely:
  1. That strncat function, like everyone else, should accept destination buffer size limit, rather than limiting number of characters to append; and
  2. All string functions should result in valid, properly NUL terminated strings.
Furthermore, I actually encourage one to use strcat() and strcpy(), despite them being allegedly "unsafe." The rationale is that this forces you into the habit of always checking string length with strlen() and make sure you have enough buffer size to hold the resulting string before performing the operation.

There are additional gripes about strtok()/strsep()—they destroy the original string, which is a problem if the string is shared with another data structure or function. You should use strchr() or strcspn() to find the next occurrence of delimiter, and use strncat() to copy the delimited portion to an empty—but NUL terminated—string. The reason why you shouldn't use strncpy() is precisely that it does not NUL terminate your string.

You should consider strncat() as a safer substitute for strncpy() because strncat() at least guarantees NUL terminating the resulting string (string copying is a special case for concatenation). This also brings up an issue about how to initialize a string buffer. Instead of zeroing out every bytes in the buffer, you only need to zero the first byte.

We discussed a number of string processing functions and their interface irregularities, and we showed some workarounds for better security practice. This illustrates the amount of detailed attention one has to pay when writing C programs. I hope that students who first learn C would just pick up the good practice from the beginning.