NSBlog

Friday Q&A 2013-05-17: Let's Build stringWithFormat:

Mike Ash — Fri, 17 May 2013 14:40:00 GMT

Friday Q&A 2013-05-17: Let's Build stringWithFormat:

Our long effort to rebuild Cocoa piece by piece continues. For today, reader Nate Heagy has suggested building NSString's stringWithFormat: method.

String Formatting
It's hard to get very far in Cocoa without knowing about format strings, but just in case, here's a recap.

stringWithFormat:, as well as other calls like NSLog, take strings that can use special format specifiers of the form %x. The % indicates that it's a format specifier, which reads an additional argument and adds it to the string. The character after it specifies what kind of data to display. For example:

    [NSString stringWithFormat: @"Hello, %@: %d %f", @"world", 42, 1.0]

This produces the string:

    Hello, world: 42 1.0

This is useful for all sorts of things, from creating user-visible text, to making dictionary keys, to printing debug logs.

Variable Arguments
This method takes variable arguments, which is an odd corner of C. For more extensive coverage of how to write such methods, see my article on vararg macros and functions. Here's a quick recap.

You declare the function or method to take variable arguments by putting ... at the end of the parameter list. For a method, this ends up being slightly odd syntax:

    + (id)stringWithFormat: (NSString *)format, ...;

That , ... thing at the end is actually legal Objective-C.

Once in the method, declare a variable of type va_list to represent the variable argument list. The va_start and va_args macros initialize and clean it up. The va_arg macro will extract one argument from the list and return it.

Code
As usual, I have posted the code on GitHub. You can view the repository here:

https://github.com/mikeash/StringWithFormat

This code supports an extremely limited subset of the full NSString formatting functionality. NSString supports a huge number of specifiers, as well as options such as field width, precision, and out-of-order arguments. My reimplementation sticks to a basic set that's enough to illustrate what's going on. In particular, it supports:

%d - int
%ld - long
%lld - long long
%u, %lu, and %llu, for the unsigned variants of the above.
%f - float
%s - C strings
%@ - Objective-C objects
%% - Output a single % character.

Furthermore, no options are supported.

Interface
For my reimplementation, I wrote a function called MAStringWithFormat that does the same thing as [NSString stringWithFormat:]. However, I wrapped the meat of the implementation in a class to organize the various bits of state needed. That function just makes a va_list for the arguments, instantiates a formatter, and asks it to do the work:

    NSString *MAStringWithFormat(NSString *format, ...)
    {
        va_list arguments;
        va_start(arguments, format);

        MAStringFormatter *formatter = [[MAStringFormatter alloc] init];
        NSString *result = [formatter format: format arguments: arguments];

        va_end(arguments);

        return result;
    }

The MAStringFormatter class essentially carries out two tasks in parallel. First, it reads through the format string character-by-character, and secondly, it writes the resulting string. Accordingly, it has two groups of instance variables. The first group deals with reading through the format string:

    CFStringInlineBuffer _formatBuffer;
    NSUInteger _formatLength;
    NSUInteger _cursor;

CFStringInlineBuffer is a little-known API in CFString that allows for efficiently iterating through the individual characters of a string. Making a function or method call for each character is slow, so CFStringInlineBuffer allows fetching them in bulk for greater efficiency. The length of the format string is stored to avoid running off the end, and the current position within the format string is stored in _cursor.

The second group deals with collecting the output of the formatting operation. It consists of a buffer of characters, the current location within that buffer, and its total size:

    unichar *_outputBuffer;
    NSUInteger _outputBufferCursor;
    NSUInteger _outputBufferLength;

This could be implemented using an NSMutableData or NSMutableString, but this is much more efficient. While this code isn't intended to be particularly fast in general, I just couldn't stand the thought of making each character run through a call to a string object.

Reading
MAStringFormatter has a read method which fetches the next character from _formatBuffer, and returns -1 once it reaches the end of the string. There isn't a whle lot to this, just an if check and a call to CFStringGetCharacterFromInlineBuffer:

    - (int)read
    {
        if(_cursor < _formatLength)
            return CFStringGetCharacterFromInlineBuffer(&_formatBuffer, _cursor++);
        else
            return -1;
    }

Writing
Writing is a little more complex, because the size of the output string isn't known ahead of time. First, there's a doubleOutputBuffer method that increases the size of the output buffer. If the buffer is completely empty, it allocates it to hold 64 characters. If it's already allocated, it doubles the size:

    - (void)doubleOutputBuffer
    {
        if(_outputBufferLength == 0)
            _outputBufferLength = 64;
        else
            _outputBufferLength *= 2;

Once the new buffer length is computed, a simple call to realloc allocates or reallocates the buffer:

        _outputBuffer = realloc(_outputBuffer, _outputBufferLength * sizeof(*_outputBuffer));
    }

Next, there's a write: method, which takes a single unichar and appends it to the buffer. If the write cursor is already at the end of the buffer, it first increases the size of the buffer:

    - (void)write: (unichar)c
    {
        if(_outputBufferCursor >= _outputBufferLength)
            [self doubleOutputBuffer];

Once sufficient storage is assured, it places c at the current cursor position, and advances the cursor:

        _outputBuffer[_outputBufferCursor] = c;
        _outputBufferCursor++;
    }

Formatting
The format:arguments: method is the entry point to where the real work gets done. The first thing it does is fill out the format string instance variables using the format argument:

    - (NSString *)format: (NSString *)format arguments: (va_list)arguments
    {
        _formatLength = [format length];
        CFStringInitInlineBuffer((__bridge CFStringRef)format, &_formatBuffer, CFRangeMake(0, _formatLength));
        _cursor = 0;

It also initializes the output variables. This isn't necessary, strictly speaking, but leaves open the possibility of reusing a single formatter object:

        _outputBuffer = NULL;
        _outputBufferCursor = 0;
        _outputBufferLength = 0;

After that, it loops through the format string until it runs off the end:

        int c;
        while((c = [self read]) >= 0)
        {

All format specifiers begin with the '%' character. If c is not a '%', then just write the character directly to the output:

            if(c != '%')
            {
                [self write: c];
            }

This comparison uses the character literal '%' despite the fact that read deals in unichar. This works because the first 128 Unicode code points map directly to the 128 ASCII characters. When a unichar contains a %, it contains the same value as the ASCII '%', and the same is true for any other ASCII character. This is terribly convenient when working with ASCII data in NSStrings.

If c is a '%' character, then there's a format specifier to come. What happens at this point depends on what the next character is:

            else
            {
                int next = [self read];

If the format specifier is a 'd', then it reads an int from the arguments and passes it to the writeLongLong: method, which handles the actual work of formatting the value into the output. All signed integers pass through that method. Since long long is the largest signed data type handled, a single method that prints those will work for all signed types:

                if(next == 'd')
                {
                    int value = va_arg(arguments, int);
                    [self writeLongLong: value];
                }

If the format specifier is 'u', then it does the same thing as above, but with unsigned, and calling through to the writeUnsignedLongLong: method:

                else if(next == 'u')
                {
                    unsigned value = va_arg(arguments, unsigned);
                    [self writeUnsignedLongLong: value];
                }

Note that int and unsigned are the smallest integer types handled here. There is no code to handle char or short. This is because of C promotion rules for functions that take variable arguments. When passed as a variable arguments, values of type char or short are promoted to int, and likewise the unsigned variants are promoted to unsigned int. This means that the code for int handles the smaller data types as well, without any additional work.

If the next character is 'l', then we need to keep reading to figure out what to do:

                else if(next == 'l')
                {
                    next = [self read];

If the character following the 'l' is 'd', then the argument is a long. Follow the same basic procedure as before:

                    if(next == 'd')
                    {
                        long value = va_arg(arguments, long);
                        [self writeLongLong: value];
                    }

Likewise, if the next character is 'u', it's an unsigned long:

                    else if(next == 'u')
                    {
                        unsigned long value = va_arg(arguments, unsigned long);
                        [self writeUnsignedLongLong: value];
                    }

If the next character is 'l' again, then we need to read one character further

                    else if(next == 'l')
                    {
                        next = [self read];

Here, 'd' indicates a long long, and 'u' indicates an unsigned long long. These are handle in the same fashion as before:

                        if(next == 'd')
                        {
                            long long value = va_arg(arguments, long long);
                            [self writeLongLong: value];
                        }
                        else if(next == 'u')
                        {
                            unsigned long long value = va_arg(arguments, unsigned long long);
                            [self writeUnsignedLongLong: value];
                        }
                    }
                }

That's it for the deep sequence of 'l' variants. Next comes a check for 'f'. In that case, the argument is a `double', and gets passed off to a method built to handle that:

                else if(next == 'f')
                {
                    double value = va_arg(arguments, double);
                    [self writeDouble: value];
                }

Once again, promotion rules simplify things a bit. When a float is passed as a variable argument, it's promoted to a double, so no extra code is needed to handle float.

If the format specifier is an 's', then the argument is a C string:

                else if(next == 's')
                {
                    const char *value = va_arg(arguments, const char *);

This is simple enough not to need a helper method. It iterates through the string until it reaches the terminating 0, writing each character as it goes. This assumes the string contains only ASCII:

                    while(*value)
                        [self write: *value++];
                }

If the format specifier is a '@', then the argument is an Objective-C object:

                else if(next == '@')
                {
                    id value = va_arg(arguments, id);

To find out what to output, ask the value for its description:

                    NSString *description = [value description];

The length of the description is also handy:

                    NSUInteger length = [description length];

Now, copy the contents of description into the output buffer. I decided to get a bit fancy here. A simple loop could suffice, perhaps using CFStringInlineBuffer for speed, but I wanted something nicer. An NSString can put its contents into an arbitrary buffer, so why not ask description to put its contents directly into the output buffer? To do that, the output buffer must first be made large enough to contain length characters:

                    while(length > _outputBufferLength - _outputBufferCursor)
                        [self doubleOutputBuffer];

Doing this in a while loop is mildly inefficient if description is larger than the buffer is already. However, that's an uncommon case, and the code is nicer by being able to share doubleOutputBuffer, so I decided to use this approach.

Now that the output buffer is sufficiently large, use getCharacters:range: to dump the contents of description into it, putting it at the location of the output cursor:

                    [description getCharacters: _outputBuffer + _outputBufferCursor range: NSMakeRange(0, length)];

Finally, move the cursor past the newly written data:

                    _outputBufferCursor += length;
                }

We're nearly to the end. If the character following the '%' is another '%', that's the siganl to write a literal '%' character:

                else if(next == '%')
                {
                    [self write: '%'];
                }
            }
        }

That's the last case handled by this miniature implementation. Once the loop terminates, the resulting unichars are located in _outputBuffer, with _outputBufferCursor indicating the number of unichars in the buffer. Create an NSString from it and return the new string:

        NSString *output = [[NSString alloc] initWithCharactersNoCopy: _outputBuffer length: _outputBufferCursor freeWhenDone: YES];
        return output;
    }

Using the NoCopy variant makes this potentially more efficient, and removes the need to manually free the buffer.

That's the basic shell of the formatting code. To complete it, we need the code to print signed and unsigned long longs, and code to print doubles.

unsigned long long
Let's start with the most fundamental helper method, writeUnsignedLongLong:. The others ultimately rely on this one for much of their work.

The algorithm is simple: divide by successive powers of ten, produing a single digit each time. Convert the digit to a unichar and write it.

We'll store the power of ten in a variable called cursor and start it at 1:

    - (void)writeUnsignedLongLong: (unsigned long long)value
    {
        unsigned long long cursor = 1;

However, what we really want is the power of ten with as many digits as the input number. For example, for 42, we want 10. For 123456, we want 100000. To obtain this, we just keep multiplying cursor by ten until it has the same number of digits as value, which is easily tested by seeing if value is less than ten times larger than cursor:

        while(value / cursor >= 10)
            cursor *= 10;

Now we just loop, dividing cursor by ten each time, until we run out of cursor:

        while(cursor > 0)
        {

The current digit is obtained by dividing value by cursor:

            int digit = value / cursor;

To compute the unichar that corresponds with digit, just add the literal '0' character. ASCII (and therefore Unicode) lays out digits sequentially starting with '0', making this easy:

            [self write: '0' + digit];

With the digit written, we remove it from value, then move cursor down:

            value -= digit * cursor;
            cursor /= 10;
        }
    }

And just like that, the value flows into the output. This code even correctly handles zero, due to ensuring that cursor is always at least 1.

long long
The writeLongLong: method is simple. If the number is less than zero, write a '-' and negate the number. For positive numbers, do nothing special. Pass the final non-negative number to writeUnsignedLongLong:.

    - (void)writeLongLong: (long long)value
    {
        unsigned long long unsignedValue = value;
        if(value < 0)
        {
            [self write: '-'];
            unsignedValue = -unsignedValue;
        }
        [self writeUnsignedLongLong: unsignedValue];
    }

There's an odd corner case in here. Due to the nature of the two's complement representation of signed integers, the magnitude of the smallest representable long long is one greater than the magnitude of the largest representable long long on systems we're likely to encounter.

A long long on a typical system can hold numbers all the way down to -9223372036854775808, but only up to 9223372036854775807. This means you can't negate the smallest possible negative number and get a positive number, because the data type can't hold the appropriate positive number. If you try to negate -9223372036854775808, you get an overflow and undefined behavior, although the result is usually just -9223372036854775808 again.

However, negation is well defined on all unsigned values, and it has the same bitwise result as negation on the bitwise-equivalent signed values. In other words, -signedLongLong produces the same bits as -(unsigned long long)signedLongLong. It also works on the bits that make up -9223372036854775808, and produces 9223372036854775808. By moving value into unsignedValue and then negating that, the above code works around the problem of undefined behavior when negating the smallest representable long long.

double
Now it's time for the really fun one. Due to the nature of floating-point arithmetic, figuring out how to properly and accurately print the value of a double was pretty tough. I did some research, even dove into an open-source implementation of printf to see how they did it, but it was so crazy and incomprehensible that I didn't get too far. I finally settled on a technique which works fairly well, and I think is as accurate as the data type allows, although the output tends to have more digits than it strictly needs.

The first step in solving the problem is to break it into two pieces. I split the double into the integer part and the fractional part, then deal with each one separately. Print each part in base 10, separate the two with a dot, and done.

The trick, then, is how to print the integer and fractional parts in base 10. I didn't want to use the same technique of successive division that I used for unsigned long long, because I was concerned that it would lose accuracy. There are integers that can be represented in a double, but where the result of dividing the integer by ten can't be exactly represented in a double. Similarly, I was afraid that the equivalent successive multiplication by ten for the fractional part would lose precision.

However, dividing or multiplying a double by two to move is always safe, unless it pushes it beyond the limits of what can be represented. If you only do this to push it closer to 1.0, then it will never lose precision. Furthermore, it's possible to chop off the fractional part of a double without losing precision in the integer part, and vice versa. Put together, these operations allow extracting information from a double bit by bit, which is enough to compute an integer representation of its integer and fractional parts. With those in hand, the existing writeUnsignedLongLong: method can be used to print the digits.

With this in mind, I set off. The first step is to check for infinity and NaN, and short circuit the whole attempt for them:

    - (void)writeDouble: (double)value
    {
        if(isinf(value) || isnan(value))
        {
            const char *str = isinf(value) ? "INFINITY" : "NaN";
            while(*str)
                [self write: *str++];
            return;
        }

Otherwise, check for negative values. If value is negative, write a '-', and negate it:

        if(value < 0.0)
        {
            [self write: '-'];
            value = -value;
        }

Unlike the long long case, there are no double values that can't be safely and correctly negated, so no shenanigans are needed here.

Next, extract the integer and fractional parts.

        double intpart = trunc(value);
        double fracpart = value - intpart;

With those in hand, call out to helper methods to write those two parts, separated by a dot:

        [self writeDoubleIntPart: intpart];
        [self write: '.'];
        [self writeDoubleFracPart: fracpart];
    }

Integer Part
Writing the integer part is the simpler of the two, conceptually. The strategy is to shift the double value one bit to the right until the value becomes zero. Each bit that's extracted is added to an unsigned long long accumulator. Once the double becomes zero, the accumulator contains its integer value.

The one tricky part is how to handle the case where the double contains a value that's larger than an unsigned long long can contain. To handle this, whenever the value of the current bit extracted from the double threatens to overflow, the accumulator is divided by ten to shift it rightwards and allow more room. The total number of shifts is recorded, and the appropriate number of extra zeroes are printed at the end of the number. Dividing the accumulator by ten loses precision, but the 64 bits of an unsigned long long exceeds the 53 bits of precision in a double, so the lost precision should not actually result in incorrect output. At the least, while the output may not precisely match the integer value stored in the double, it will be closer to that value than to any other representable double value, which I'm calling close enough.

In order to know when the accumulator threatens to overflow, the code needs to know the largest power of ten that can be represented in an unsigned long long. This method computes it by just computing successive powers of ten until it gets close to ULLONG_MAX:

    - (unsigned long long)ullongMaxPowerOf10
    {
        unsigned long long result = 1;
        while(ULLONG_MAX / result >= 10)
            result *= 10;
        return result;
    }

The writeDoubleIntPart: method starts off by initializing a total variable to zero:

    - (void)writeDoubleIntPart: (double)intpart
    {
        unsigned long long total = 0;

This is the accumulator that will hold the total computed value so far. It also keeps track of the value of the current bit:

        unsigned long long currentBit = 1;

This is multiplied by two each time a bit is extracted from the double, and represents the value of that bit.

The maximum value that can be stored in total before overflow threatens is cached:

        unsigned long long maxValue = [self ullongMaxPowerOf10] / 10;

This is one digit less than the maximum representable power of ten, in order to make sure that it can never overflow the accumulator. There is a surplus of 11 bits of precision in the accumulator, so losing one digit doesn't hurt too much.

The number of times that total and currentBit have been shifted to the right is recorded so that the appropriate number of trailing zeroes can be output later:

        unsigned surplusZeroes = 0;

Setup is complete, now it's time to loop until intpart is exhausted:

        while(intpart)
        {

A bit is extracted from intpart by dividing it by two:

            intpart /= 2;

Because intpart contains an integer, dividing it by two produces a number with a fractional part that is either .0 or .5. The .5 case represents a one bit that needs to be added to total. The presence of .5 is checked by using the fmod function, which computes the remainder when dividing by a number. Using fmod with 1.0 as the second argument just produces the fractional part of the number:

            if(fmod(intpart, 1.0))
            {

If the bit is set, then currentBit is added to total, and the .5 is sliced off of intpart using the trunc function:

                total += currentBit;
                intpart = trunc(intpart);
            }

Next, currentBit is multiplied by two so that it holds the right value for the next bit to be extracted:

            currentBit *= 2;

If currentBit exceeds maxValue, then both currentBit and total get divided by ten, and surplusZeroes is incremented. Both are rounded when dividing by adding 5 to them first, to aid in preserving as much precision as possible:

            if(currentBit > maxValue)
            {
                total = (total + 5) / 10;
                currentBit = (currentBit + 5) / 10;
                surplusZeroes++;
            }
        }

Once intpart is exhausted, total contains an approximation of its original value, and surplusZeroes indicates how many times it got shifted over. First, it prints total:

        [self writeUnsignedLongLong: total];

Finally, it prints the appropriate number of trailing zeroes:

        for(unsigned i = 0; i < surplusZeroes; i++)
            [self write: '0'];
    }

Fractional Part
The basic idea for printing the fractional part is similar to printing the integer part. The difference is that the accumulator can't directly represent the fractional value, because unsigned long long doesn't do fractions. Instead, it holds the fractional value, scaled up by some large power of ten. For example, 100 might represent 1.0, in which case the value of the first bit in the fractional part of a double is 50, the second bit is 25, and so forth. The actual numbers used contain a lot more zeroes at the end.

The accumulator for the integer part can overflow, while the accumulator for the fractional part can underflow. If the double contains an extremely small value, the accumulator will end up containing zero, which is no good. A similar strategy is used to deal with this problem, but in the opposite direction: whenever the accumulator and current bit become too small, they are multiplied by ten, and an extra leading zero is output.

The method starts off with its accumulator initialized to zero:

    - (void)writeDoubleFracPart: (double)fracpart
    {
        unsigned long long total = 0;

The value of the current bit is started at the largest power of ten that will fit into an unsigned long long. This represents 1.0, and will be divided by 2 right away to properly represent 0.5 for the first bit extracted from the double:

        unsigned long long currentBit = [self ullongMaxPowerOf10];

The threshold for when the numbers become too small is the maximum representable power of ten, divided by ten. When this value is reached, there's a conceptual leading zero, and it's time to shift everything over:

        unsigned long long shiftThreshold = [self ullongMaxPowerOf10] / 10;

Now it's time for the loop. Keep extracting bits from fracpart until there's nothing left:

        while(fracpart)
        {

fracpart is shifted to the left by one bit, while currentBit is simultaneously shifted to the right:

            currentBit /= 2;
            fracpart *= 2;

The integer part of the resulting number will be either 1 or 0. If it's 1, the corresponding bit is 1, so add currentBit to total, and chop the 1 off fracpart:

            if(fracpart >= 1.0)
            {
                total += currentBit;
                fracpart -= 1.0;
            }

If both the accumulator and currentBit are below shiftThreshold, it's time to shift everything over, and write a leading zero. Note that the number of shifts doesn't need to be tracked like it did in the previous method, because the leading zeroes can be written out immediately:

            if(currentBit <= shiftThreshold && total <= shiftThreshold)
            {
                [self write: '0'];
                currentBit *= 10;
                total *= 10;
            }
        }

Once the loop exits, there's one more task to be done. total now contains an integer representation of the decimal representation of the fractional part that was passed into the method (whew!), but with potentially a large number of redundant trailing zeroes. For example, if fracpart contained 0.5, then total now contains 5000000000000000000, but those trailing zeroes shouldn't be printed in the output. They're removed by just dividing total by ten repeatedly to get rid of trailing zeroes:

        while(total != 0 && total % 10 == 0)
            total /= 10;

Once that's done, total is ready to print, so it's passed to writeUnsignedLongLong:

        [self writeUnsignedLongLong: total];
    }

That's the end of the adventure of printing a double.

Conclusion
stringWithFormat: is an extremely useful method that is, at its heart, a straightforward function that takes variable arguments. There are a ton of subtleties in how to output all of the various data formats, such as the adventure in printing a double above. There are further complications in supporting all of the various options available in format strings, which the above code doesn't even address. However, it's ultimately a big loop that looks for '%' format specifiers, and uses va_arg to extract the arguments passed in by the caller. Although stringWithFormat: is considerably more complex, you now have a basic idea of how it's put together.

That's it for today. Come back next time for more bitwise adventures. Friday Q&A is driven by reader suggesions, so until the next time, please keep sending in your ideas for topics.

Friday Q&A 2013-05-03: Proper Use of Asserts

Mike Ash — Fri, 03 May 2013 13:03:00 GMT

Friday Q&A 2013-05-03: Proper Use of Asserts

Asserts are a powerful tool for building quality code, but they're often poorly understood. Today, I want to discuss the various options for writing asserts in Cocoa apps and the best ways to use them, a topic suggested by reader Ed Wynne.

APIs
Fundamentally, an assert is just a call that takes an expression and indicates failure in some way if the expression isn't true. The basic idea is to check for conditions that should always be true so that you fail early and obviously, rather than failing later and confusingly. For example, an array dereference will fail in various weird ways if you give it a bad index:

    x = array[index]; // sure hope index is in range

Using an assert can help make it obvious what went wrong:

    assert(index >= 0 && index < arrayLength);
    x = array[index];

This actually demonstrates an API for asserts. C provides the assert function if you #include <assert.h>. It takes a single expression. If the expression is true, it does nothing. If it's false, it prints the expression, the file name and line number where the assert is located, and then calls abort, terminating the program.

Cocoa provides several assert functions as well. The most basic is NSAssert. It takes an expression and a string description, which can be a format string:

    NSAssert(x != y, @"x and y were equal, this shouldn't happen");
    NSAssert(z > 3, @"z should be greater than 3, but was actually %d", z);
    NSAssert(str != nil, @"nil string while processing %@ of type %@", name, type);

Like the assert function, this logs the assertion failure if the expression is false. It then throws an NSInternalInconsistencyException, and what happens then depends on what exception handlers are present. In a typical Cocoa app, it will either be caught and logged by the runloop, or it will terminate the application.

Unfortunately, the logging from NSAssert is weak. It logs the fact that the assertion failed, as well as the method it was in and the filename and line number, but it doesn't actually log the expression that failed, nor does it log the reason string provided to the macro. The exception it throws does include the reason string, at least, so as long as the exception gets printed at some point, that will show up.

There are a few variants of this call available in Cocoa. The NSAssert call only works within an Objective-C method, so there's an equivalent NSCAssert call that works in a C function. There's also NSParameterAssert, which doesn't take a description string and is intended for quickly checking a parameter value, and an equivalent NSCParameterAssert for C functions.

Build Your Own
The built-in options aren't great. The C assert is decent, but doesn't allow for a customizable message. The Cocoa calls have bad logging, and their behavior in the event of a failed assertion depends too much on runtime context, and may not actually terminate the app.

These things aren't hard to build, though, so let's build one that does things right! We'll want a call that takes an expression and optionally a description format string:

    MAAssert(x > 0);
    MAAssert(y > 3, @"Bad value for y");
    MAAssert(z > 12, @"Bad value for z: %d", z);

It should log the expression, the format string if it exists, and the filename, line number, and function name where the problem occurred. Additionally, it should only evaluate the format string parameters if the assertion fails, to make things more efficient. All of this calls for a macro.

Like all good multi-line macros, this macro is wrapped in a do/while construct:

    #define MAAssert(expression, ...) \
        do { \

The first thing it does is check whether the expression is actually false:

            if(!(expression)) { \

If it is, it uses NSLog to log the details of the failure:

                NSLog(@"Assertion failure: %s in %s on line %s:%d. %@", #expression, __func__, __FILE__, __LINE__, [NSString stringWithFormat: @"" __VA_ARGS__]); \

The #expression construct produces a string literal containing the text of the expression. For example, it will produce "x > 0" for the first assert call above. The __func__ identifier produces the name of the current function. __FILE__ and __LINE__ should be self-explanatory. The dummy @"" in the stringWithFormat: call ensures that the syntax is legal even when no reason string is provided.

After logging the assertion failure, it then terminates the app by calling abort, and the macro ends:

                abort(); \
            } \
        } while(0)

This works perfectly. It allows an additional explanatory string, but doesn't require it for cases where the expression is enough to make it clear what's going wrong. It always calls abort on failure, rather than throwing an exception that could potentially be caught. It logs all available details at the point of failure.

Application Specific Information
It would be great if we could get the failure message to show up in crash logs as well. Turns out, we can! Wil Shipley demonstrated how to put custom data into the "Application Specific Information" section of a crash log. Put this somewhere in the source code:

    const char *__crashreporter_info__ = NULL;
    asm(".desc _crashreporter_info, 0x10");

Any string written into this magic global variable will show up in that section of the crash log. This doesn't work everywhere (word is that it doesn't work on iOS), but it can be handy, and does no harm when it doesn't work. If you want to take advantage of this, a small modification to the assert macro will put the message into this variable as well as logging it:

    #define MAAssert(expression, ...) \
        do { \
            if(!(expression)) { \
                NSString *__MAAssert_temp_string = [NSString stringWithFormat: @"Assertion failure: %s in %s on line %s:%d. %@", #expression, __func__, __FILE__, __LINE__, [NSString stringWithFormat: @"" __VA_ARGS__]]; \
                NSLog(@"%@", __MAAssert_temp_string); \
                __crashreporter_info__ = [__MAAssert_temp_string UTF8String]; \
                abort(); \
            } \
        } while(0)

And, as if by magic, the message appears in the crash log.

Philosophy
Now that you know how to write an assert in many different ways, just what kind of asserts should you write?

Asserts should be written for conditions that, according to your understanding of the program, should never occur. Asserts should not be used to check for errors that are actually expected to happen in some cases. For example, asserting that a filename is not nil is good technique:

    assert(filename != nil);

However, asserting that data could be read from that file is bad practice:

    NSData *data = [NSData dataWithContentsOfFile: filename];
    assert(data != nil);

That call can legitimately fail due to real-world conditions, such as the file not existing on disk, or not having permissions to read it. Because of that, this code needs some actual error handling, not just an assert. Failing to read the file should result in taking an alternate approach or alerting the user that something went wrong, not just logging and terminating the app.

Typically, the most useful place for asserts is at the top of a function or method, to check constraints on the parameters that can't be expressed in the language directly. These asserts correspond directly to constraints expressed in the documentation. For example:

    // Flange an array of sprockets. The sprockets array must contain
    // at least two entries, and the index must lie within the array.
    - (void)flangeSprockets: (NSArray *)array fromIndex: (NSUInteger)index
    {
        assert([array count] >= 2);
        assert(index < [array count]);

        ...method body...

The gap between a caller and a callee makes it easy to lose track of these constraints, making this an excellent place to double-check that everything is as it should be. Special attention should be paid to parameters that are easy to screw up, and to parameters where bad values will cause strange failures. For example, this assert checking for NULL, while still useful, doesn't add much, since the resulting crash without it would still be fairly clear:

    assert(ptr != NULL);
    x = *ptr;

It's not bad, but your time may be better spent elsewhere. This assert checking for nil is really handy, as a nil value here will just result in a strangely built string, which could show up far away and much later:

    assert(name != nil);
    str = [NSString stringWithFormat@"Hello, %@!", name];

It can also be handy to add asserts in the middle of complex code which has clear pre or post-conditions. For example, in the middle of modifying a data structure, you might check to make sure all of your variables have consistent values between themselves:

    assert(done + remaining == total);

This will let you catch logic errors quickly.

Avoid asserts for obvious conditions that have little room for error. For example, these are pointless:

    int x = 1;
    assert(x == 1);

    for(int i = 0; i < 10; i++)
    {
        assert(i >= 0);
        ...

There's no way these asserts will fire unless the computer is seriously malfunctioning, so they're basically a waste of time. Concentrate on things that "can't happen" if parts of your program work together as they should, but that you could conceivably miss.

Finally, make sure that the conditions you're asserting are reasonably fast to evaluate. You don't want them bogging down your program. Don't loop through your million-element array asserting a complex condition on every entry just out of paranoia.

In short, assert essential preconditions of your code, with an eye toward things that will cause you pain if not caught early. The goal is to get a leg up on debugging when things start to go wrong.

Disabling Asserts
If you search the web for information about asserts, you'll invariably turn up discussions of how to disable asserts in your release builds. Most assert systems have a way to disable asserts program-wide. For the C assert call, setting the NDEBUG macro disables it. For the Cocoa assert calls, setting the NS_BLOCK_ASSERTIONS macro disables them. There are generally two reasons given for disabling asserts in release builds:

Asserts impose a runtime cost that you shouldn't make every user pay. In theory, if you've tested thoroughly, you shouldn't encounter any assertion failures in your release builds anyway.
An assertion failure immediately terminates the app, which users don't like. By removing asserts, you give the program a chance to continue functioning in the face of a bug.

However, I am firmly of the opinion that disabling asserts in release builds is a terrible idea. The runtime cost should be negligible, and if it's not, then you should redo your asserts to fix that. As for avoiding app termination, asserts should be written such that a failure always means that something has gone terribly wrong. It is possible that the app will continue functioning in the face of that. It's more likely that it'll crash. It's also possible that it'll keep running, but corrupt your user's data. A clean crash is vastly preferable. No code is free of bugs, and crashing early and obviously when a bug is encountered is much better, even in a release build running on a user's machine. Generating a cleaner crash log will help you debug the failures more quickly.

The example MAAssert macro above doesn't have any built-in way to disable it for this reason. If you use a different assert facility, I strongly recommend that you avoid ever turning them off.

Conclusion
Asserts are a valuable tool for producing better code and making bugs easier to find and fix. Asserts should be used anywhere there's a constraint on a value that isn't enforced by the language. My general guideline is that if you document a restriction for callers, you should also assert it in the code. If you ever find yourself writing some code that gets you thinking a lot, and has variables whose values should relate to each other in a certain way not enforced by the language, assert that in the code.

That's it for today. Friday Q&A is driven by reader suggestions as always, so if there's a topic that you'd like to see covered here, please send it in. Come back soon for another exciting article.

Friday Q&A Is On Vacation

Mike Ash — Fri, 19 Apr 2013 14:24:00 GMT

Friday Q&A Is On Vacation

Friday Q&A is on vacation at the moment, so there will be no article today. Never fear: although he's busy relaxing today, Friday Q&A will return, and soon. To keep my loyal readers from being too upset, here is a collection of links to interesting articles to keep you occupied.

How did real-mode Windows implement its LRU algorithm without hardware assistance? - A fascinating look at how a really old system pulled off a good chunk of virtual memory with no hardware assistance.
Data in crash dumps are not a matter of opinion - A case study in challenging your assumptions and believing the evidence over your preconceptions when debugging code. This is another Old New Thing link, and I could easily give dozens of links to great articles just on that blog. Don't mind the Windows-centric topics, it's well worth your time.
Things That Turbo Pascal is Smaller Than - Pretty self-explanatory. Old software is small.
Synchronization on the local variables - A construct that makes absolutely no sense in general ends up providing an important speed gain through the magic of JIT compilation and lock elision.
Errors detected in Open Source projects by the PVS-Studio developers through static analysis - Makers of a static code analyzer run their code on a lot of open source projects and summarize the results. Great list of common errors to watch out for in your own code.
Weird Machines - Breaks down the process of exploiting security bugs, and describes "weird machines" that result: accidental general-purpose computers formed by manipulating programs in ways they weren't intended to be used.
The world's longest cells? Speculations on the nervous systems of sauropods - Without clicking the link, take a guess as to how long the longest cell that ever existed was. I won't spoil it, but if you're like me, your guess is off by many orders of magnitude.

Friday Q&A 2013-04-05: Windows and Window Controllers

Mike Ash — Fri, 05 Apr 2013 13:36:00 GMT

Friday Q&A 2013-04-05: Windows and Window Controllers

It's time to take a turn to some lighter fare, but to a subject that's near and dear to my heart. The fundamental UI component of a Cocoa app is the NSWindow, and there are many different ways to instantiate and manage them, but there is only one correct way: for each type of window, there should be a separate nib file, and a specialized NSWindowController subclass. I'll walk through what this means and how to do it, a topic suggested by reader Mike Shields.

Variants
It's common to see different ways of instantiating and managing windows. Xcode's templates, for example, put an NSWindow instance in MainMenu.xib, and treat the application delegate as the window's controller. It's common to pack multiple related windows into a single nib. People sometimes instantiate windows in code wherever they need them. Some will subclass NSWindow and put the controlling code in the subclass.

The central thesis of this article is that all of the approaches listed above are wrong. Yes, even the Xcode template, the first thing people see when they check out this whole Cocoa thing, is wrong. This is the fundamental correct design:

    one window = one nib + one NSWindowController subclass

Why
Fundamental separation of concerns makes this the best approach, and it ultimately costs no more time or effort than lesser approaches.

Most windows need a lot of controller functionality. Even extremely basic windows can eventually grow to take on a lot of tasks. As the largest unit of Cocoa UI, each kind of window needs and deserves its own controller class. It's possible to cram the logic for multiple windows into a single controller, but this ultimately makes no more sense than cramming the logic for a string and an array into the same class, just because you happen to be using them at the same time.

Most windows also function as independent units. It's rare to have a window that always appears with another window. Even if it does now, it may not later as you evolve your UI. Because of this, each window should be in its own nib file, separate from any others. The only objects in a nib, other than MainMenu.xib, should be File's Owner, which is an instance of your NSWindowController subclass, the window itself, and any non-window objects related to the window, such as auxiliary views and controller objects. MainMenu.xib is a special case: it should contain File's Owner, which is the NSApplication instance, the menu bar, the application delegate, any other objects related to these, but no NSWindow instances.

How
Start off by creating an NSWindowController subclass. Give it a name like MAImportantThingWindowController to make it obvious what it is.

Next, create the nib. Give this one a name like MAImportantThingWindow.xib. The Xcode template for a nib with a window it in will set things up well, so you can use that. If you prefer to build it yourself, create a new empty nib file, then add a new window to it from the library.

Set up the nib with the NSWindowController subclass. Set the class of File's owner to the controller class. Once that's done, connect the controller's window outlet to the window, and connect the window's delegate outlet to the controller.

That's it for nib setup, beyond whatever specific UI you want to build yourself. It's time to make the controller aware of the nib.

Xcode will pre-populate some methods in the subclass for you, but these aren't important. The windowDidLoad implementation it provides is useful, but doesn't contain anything interesting. The initWithWindow: method it provides is pointless and can be deleted.

NSWindowController provides a initWithWindowNibName: method. However, your subclass is built to work with only a single nib, so it's pointless to make clients specify that nib name. Instead, we'll provide a plain init method that does the right thing internally. Simply override it to call super and provide the nib name:

    - (id)init
    {
        return [super initWithWindowNibName: @"MAImportantThingWindow"];
    }

If your window controller needs parameters to set itself up, for example a model object that it's going to display and edit, then those parameters can be added to this init method.

Optionally, depending on your level of paranoia, you may override initWithWindowNibName: to guard against accidentally calling it from elsewhere:

    - (id)initWithWindowNibName: (NSString *)name
    {
        NSLog(@"External clients are not allowed to call -[%@ initWithWindowNibName:] directly!", [self class]);
        [self doesNotRecognizeSelector: _cmd];
    }

I don't personally bother with this sort of guard most of the time, but it can be comforting or potentially useful to have depending on your habits and those of the people you work with.

If you have instance-specific initialization to perform, that can be done in the init method just like any other class. Note, however, that outlets are not connected at this point, so you can't do anything that involves those. UI initialization comes later.

After the nib loads, NSWindowController calls windowDidLoad, which is the perfect override point for UI initialization:

    - (void)windowDidLoad
    {
        [_myView setColor: ...];
        [_myButton setImage: ...];
    }

The implementation in NSWindowController is documented to do nothing, so it's not necessary to call super.

NSWindowController loads its nib lazily. When initialized, it just remembers which nib it's supposed to use. Only when you ask for its window does it actually proceed to load the nib. Because of this, you need to be careful when accessing outlets in code that may run before the nib loads. For example, this method will silently fail if it's called before the window is loaded:

    - (void)setName: (NSString *)name
    {
        [_nameField setStringValue: name];
    }

There are two ways to work around this. One is to simply force the window to load before using an outlet:

    - (void)setName: (NSString *)name
    {
        [self window];
        [_nameField setStringValue: name];
    }

This has some unnecessary overhead if the window wouldn't otherwise be loaded at this point, but works well enough. Most of the time, a window controller is being used because it's going to display the window.

The other way is to keep an instance variable for the data as well as setting it in the UI. The setter will both set the instance variable and manipulate the outlet:

    - (void)setName: (NSString *)name
    {
        _name = name;
        [_nameField setStringValue: _name];
    }

This also needs a line of code in windowDidLoad to sync up the UI when it does finally load:

    - (void)windowDidLoad
    {
        if(_name)
            [_nameField setStringValue: _name];
        // more setup code here
    }

Everything else in the nib and the window controller is up to you. It all depends on what you want the window to do. At this point you can create outlets and views and controls as you normally would.

Using the Controller
With this stuff in place, using the controller is simple. First, allocate and initialize it:

    MAImportantThingWindowController *controller = [[MAImportantThingWindowController alloc] init];

Perform any necessary setup:

    [controller setName: _name];

Then show the window:

    [controller showWindow: nil];

If there are multiple windows of this kind floating around, you usually want to add this controller to an array that holds all of the controllers of this type:

    [_importantThingControllers addObject: controller];

If there's only one, then you'll probably want an instance variable to hold it:

    _importantThingController = controller;

That's it! As you use it, you may find that you need to pass more data through from whatever is instantiating and manipulating the controller. To do this, just add setters to the controller class that manipulate the UI as needed, and call those setters as appropriate.

Conclusion
There are a lot of ways to manage windows in Cocoa, but most of those ways are wrong. Sadly, there are a lot of different, incorrect techniques floating around out there, up to and including Apple's own Xcode templates. Now you know the proper way to do it. Just remember the principle:

    one window = one nib + one NSWindowController subclass

That's it for today. Check back next time for more wacky shenanigans. Friday Q&A is driven by reader ideas, so if you have a topic you'd like to see here, please send it to me.

Objective-C Literals in Serbo-Croatian

Mike Ash — Tue, 26 Mar 2013 23:48:00 GMT

Objective-C Literals in Serbo-Croatian

Reader Anja Skrba from Webhostinggeeks.com has translated my Objective-C Literals article into Serbo-Croatian. It's always fun to see translations of my writing, even when I can't understand them at all. If you do understand Serbo-Croatian, or know someone who does, check it out. The Serbo-Croatian version of Objective-C Literals is available on Webhostinggeeks.com.

Friday Q&A 2013-03-22: Let's Build NSInvocation, Part II

Mike Ash — Fri, 22 Mar 2013 14:57:00 GMT

Friday Q&A 2013-03-22: Let's Build NSInvocation, Part II

Last time on Friday Q&A, I began the reimplementation of parts of NSInvocation as MAInvocation. In that article, I discussed the basic theory, the architecture calling conventions, and presented the assembly language glue code needed for the implementation. Today, I present the Objective-C part of MAInvocation.

Recap
MAInvocation is my reimplementation of a large chunk of NSInvocation. For simplicity, it doesn't support floating point arguments or return values, and it also doesn't support struct arguments. It only supports the x86-64 architecture. The code is on GitHub here:

https://github.com/mikeash/MAInvocation

The first six parameters to a function are passed in six registers: rdi, rsi, rdx, rcx, r8, and r9. Subsequent parameters, if any, are passed on the stack. Return values are returned in rax. For the special case of a two-element struct, the second element is returned in rdx. Larger structs are returned by having the caller allocate memory, and then a pointer to that memory is implicitly passed in as the first parameter in rdi, with all explicit parameters bumped down. These are called stret calls in the Objective-C world.

Assembly language glue is used to translate between values held in a struct and actual function calls. The struct holds all of the registers in question, plus a pointer to stack arguments, plus some additional data:

    struct RawArguments
    {
        void *fptr;

        uint64_t rdi;
        uint64_t rsi;
        uint64_t rdx;
        uint64_t rcx;
        uint64_t r8;
        uint64_t r9;

        uint64_t stackArgsCount;
        uint64_t *stackArgs;

        uint64_t rax_ret;
        uint64_t rdx_ret;

        uint64_t isStretCall;
    };

The MAInvocationCall function is written in assembly, and was explored in the previous article. It has this prototype:

    void MAInvocationCall(struct RawArguments *);

Objective-C code can fill out a struct RawArguments with a function pointer and the appropriate register values, then call this function. It will make the function call, and on return, the two return value register fields in the struct will be filled out with whatever the function returned.

There are also two forwarding handlers:

    void MAInvocationForward(void);
    void MAInvocationForwardStret(void);

These are designed to be invoked by an arbitrary Objective-C method call. They both create a new struct RawArguments, fill out the argument registers and stack arguments pointer, and then invoke a C function called MAInvocationForwardC. When that returns, the handlers pass the rax_ret and rdx_ret values back to the caller. The only difference between these two handlers is whether they set the isStretCall to 0 or 1.

The stage is now set for the Objective-C implementation of MAInvocation.

Interface
The interface to MAInvocation is the same as NSInvocation:

    @interface MAInvocation : NSObject

    + (MAInvocation *)invocationWithMethodSignature:(NSMethodSignature *)sig;

    - (NSMethodSignature *)methodSignature;

    - (void)retainArguments;
    - (BOOL)argumentsRetained;

    - (id)target;
    - (void)setTarget:(id)target;

    - (SEL)selector;
    - (void)setSelector:(SEL)selector;

    - (void)getReturnValue:(void *)retLoc;
    - (void)setReturnValue:(void *)retLoc;

    - (void)getArgument:(void *)argumentLocation atIndex:(NSInteger)idx;
    - (void)setArgument:(void *)argumentLocation atIndex:(NSInteger)idx;

    - (void)invoke;
    - (void)invokeWithTarget:(id)target;

    @end

Instance Variables
The method signature is central to an invocation object. The method signature describes how many parameters the method takes, as well as what the types are. This is critical information to be able to figure out how to deal with method parameters and return types. This is why the only way to create an MAInvocation is with an NSMethodSignature, and that signature is stored in an instance variable:

    @implementation MAInvocation {
        NSMethodSignature *_sig;

The invocation keeps a local struct RawArguments. This struct is manipulated directly when setting or getting arguments and return values. When the invocation is invoked, a pointer to the instance variable can be passed directly to the assembly language glue:

        struct RawArguments _raw;

Invocations can retain their arguments. This sends retain to all object arguments, and it also copies C string arguments. Whether arguments are currently retained needs to be tracked, so that they can be properly freed, and so that newly-set arguments can be retained, so there's a flag for that:

        BOOL _argumentsRetained;

Finally, there needs to be a buffer to store the return value for stret calls:

        void *_stretBuffer;
    }

Initialization
The factory method just calls an init method:

    + (NSInvocation *)invocationWithMethodSignature: (NSMethodSignature *)sig
    {
        return [[[self alloc] initWithMethodSignature: sig] autorelease];
    }

The init method saves the method signature:

    - (id)initWithMethodSignature: (NSMethodSignature *)sig
    {
        if((self = [super init]))
        {
            _sig = [sig retain];

It then populates the isStretCall of the struct RawArguments by examining the method signature to determine whether it fits the requirements for a stret call. This is done by calling another method. The code for that method is rather involved, and will come later:

            _raw.isStretCall = [self isStretReturn];

Next, the stack arguments are set up. The first thing to do here is to get the total number of arguments from the method signature:

            NSUInteger argsCount = [sig numberOfArguments];

Note that this count includes the two implicit arguments, self and _cmd, so this number is exactly equal to the number of function arguments being passed.

If it's a stret call, then there's effectively one more argument, because of the implicit pointer for the return value passed in rdi:

            if(_raw.isStretCall)
                argsCount++;

If there are more than six arguments (potentially including the implicit stret parameter), then there are stack arguments. stackArgsCount is set to the number of remaining arguments, and memory is allocated so that stackArgs can hold them:

            if(argsCount > 6)
            {
                _raw.stackArgsCount = argsCount - 6;
                _raw.stackArgs = calloc(argsCount - 6, sizeof(*_raw.stackArgs));
            }
        }
        return self;
    }

Wrapper Methods
There are a few methods in the API that are simply small wrappers around other methods. I'll cover them here before we get to the real meat.

The target method just gets the value of the first argument in a slightly more convenient way. The method is just a small wrapper around the getArgument:atIndex: method:

    - (id)target
    {
        id target;
        [self getArgument: &target atIndex: 0];
        return target;
    }

The setTarget: method is an even simpler wrapper around the setArgument:atIndex: method:

    - (void)setTarget: (id)target
    {
        [self setArgument: &target atIndex: 0];
    }

The selector and setSelector: methods are virtually identical, but manipulate the second argument:

    - (SEL)selector
    {
        SEL sel;
        [self getArgument: &sel atIndex: 1];
        return sel;
    }

    - (void)setSelector: (SEL)selector
    {
        [self setArgument: &selector atIndex: 1];
    }

Finally, the invoke method calls invokeWithTarget:, passing [self target]:

    - (void)invoke
    {
        [self invokeWithTarget: [self target]];
    }

Getting Arguments
In order to get an argument out of the invocation, the code first needs to know where an argument is stored. This small wrapper method handles that:

    - (uint64_t *)argumentPointerAtIndex: (NSInteger)idx
    {
        uint64_t *ptr = NULL;
        if(idx == 0)
            ptr = &_raw.rdi;
        if(idx == 1)
            ptr = &_raw.rsi;
        if(idx == 2)
            ptr = &_raw.rdx;
        if(idx == 3)
            ptr = &_raw.rcx;
        if(idx == 4)
            ptr = &_raw.r8;
        if(idx == 5)
            ptr = &_raw.r9;
        if(idx >= 6)
            ptr = _raw.stackArgs + idx - 6;
        return ptr;
    }

This method takes a raw argument index, which is to say that it's already been adjusted to take into account whether or not this is a stret call. It then maps that index onto the appropriate register or stack slot.

It's also handy to be able to get the size of a particular argument, so it can copy the right number of bytes for arguments that are smaller than 8 bytes. This method wraps the Foundation function NSGetSizeAndAlignment, which takes an Objective-C type string and returns the size (and alignment!) of the type in question:

    - (NSUInteger)sizeOfType: (const char *)type
    {
        NSUInteger size;
        NSGetSizeAndAlignment(type, &size, NULL);
        return size;
    }

Another small wrapper around this method provides the size of a given argument:

    - (NSUInteger)sizeAtIndex: (NSInteger)idx
    {
        return [self sizeOfType: [_sig getArgumentTypeAtIndex: idx]];
    }

To actually fetch an argument, the method first adjusts the requested index to take into account the possible stret return:

    - (void)getArgument: (void *)argumentLocation atIndex: (NSInteger)idx
    {
        NSInteger rawArgumentIndex = idx;
        if(_raw.isStretCall)
            rawArgumentIndex++;

Next, it grabs the pointer from the above method, and checks it for sanity:

        uint64_t *src = [self argumentPointerAtIndex: rawArgumentIndex];
        assert(src);

Then it grabs the argument size and copies the appropriate number of bytes out of the argument location:

        NSUInteger size = [self sizeAtIndex: idx];
        memcpy(argumentLocation, src, size);
    }

Getting and Setting Return Values
To get and set the return value, the value's size is needed. This is easy to obtain by just getting the size of the return type obtained from the method signature:

    - (NSUInteger)returnValueSize
    {
        return [self sizeOfType: [_sig methodReturnType]];
    }

It's also necessary to get a pointer to the location where the return value is stored. If the invocation is for a stret call, then it returns _stretBuffer. If the buffer isn't allocated yet, it allocates it:

    - (void *)returnValuePtr
    {
        if(_raw.isStretCall)
        {
            if(_stretBuffer == NULL)
                _stretBuffer = calloc(1, [self returnValueSize]);
            return _stretBuffer;
        }

For regular calls, it just returns the address of the rax_ret field in the raw arguments struct:

        else
        {
            return &_raw.rax_ret;
        }
    }

This takes care of the case where the return value uses both return registers. Since they're contiguous in the struct, copying a sufficiently large value into this address will write to both register fields in the struct.

With these methods available, writing the methods to get and set the return value is easy. All they have to do is call memcpy with the computed size and pointer:

    - (void)getReturnValue: (void *)retLoc
    {
        NSUInteger size = [self returnValueSize];
        memcpy(retLoc, [self returnValuePtr], size);
    }

    - (void)setReturnValue: (void *)retLoc
    {
        NSUInteger size = [self returnValueSize];
        memcpy([self returnValuePtr], retLoc, size);
    }

Type Classification
Determining whether a method's return type requires a stret call requires classifying that type according to the x86-64 calling conventions. The NSInvocation API allows for retaining the arguments to the invocation, which also requires classifying the argument types, so that all of the object types can be found.

The different classifications get put into an enum which combines the relevant parts of the x86-64 ABI with the distinctions necessary for retaining arguments. This boils down to objects, blocks, C strings, other integer types (including non-object pointers), a struct containing two integers, an empty struct, any other struct, and any other type not already covered:

    enum TypeClassification
    {
        TypeObject,
        TypeBlock,
        TypeCString,
        TypeInteger,
        TypeTwoIntegers,
        TypeEmptyStruct,
        TypeStruct,
        TypeOther
    };

The classification process itself consists of two mutually-recursive methods: one that classifies arbitrary types, and one specialized to classify struct types.

The general method starts by creating the type strings for 'id', blocks, and C strings by using the @encode directive:

    - (enum TypeClassification)classifyType: (const char *)type
    {
        const char *idType = @encode(id);
        const char *blockType = @encode(void (^)(void));
        const char *charPtrType = @encode(char *);

Note that all blocks have the same type string when it comes to @encode, so the choice of block type here is completely arbitrary.

With these in hand, it compares type against them, and returns the appropriate enum value if there's a match:

        if(strcmp(type, idType) == 0)
            return TypeObject;
        if(strcmp(type, blockType) == 0)
            return TypeBlock;
        if(strcmp(type, charPtrType) == 0)
            return TypeCString;

Next, it checks integer types. This crazy bit of code constructs a C string that contains every the character for every integer type, plus function pointers (which is just ?), plus any other pointer (which all start with ^):

        char intTypes[] = { @encode(signed char)[0], @encode(unsigned char)[0], @encode(short)[0], @encode(unsigned short)[0], @encode(int)[0], @encode(unsigned int)[0], @encode(long)[0], @encode(unsigned long)[0], @encode(long long)[0], @encode(unsigned long long)[0], '?', '^', 0 };

With that C string in hand, the strchr function can be used to check the first character in type aganist all of these characters. If there's a match, then the type is an integer type:

        if(strchr(intTypes, type[0]))
            return TypeInteger;

struct types begin with the { character. If the type string starts with that character, then call into the struct classifier:

        if(type[0] == '{')
            return [self classifyStructType: type];

If nothing matches, then return the "other" type:

        return TypeOther;
    }

The struct classifier uses a helper method that takes the type string for the struct and enumerates over all of its contents. It tracks the struct's classification at each point, and updates it with each new element in the struct. It starts out with an empty struct:

    - (enum TypeClassification)classifyStructType: (const char *)type
    {
        __block enum TypeClassification structClassification = TypeEmptyStruct;

Then it enumerates and classifies each type within:

        [self enumerateStructElementTypes: type block: ^(const char *type) {
            enum TypeClassification elementClassification = [self classifyType: type];

If the current classification is an empty struct, then the new classification is the same as the element classification. A struct with one element is classified the same as the element it contains:

            if(structClassification == TypeEmptyStruct)
                structClassification = elementClassification;

If the current classification is an integer type and the element classification is also an integer type, then the struct gets the special classification of a struct containing two integers:

            else if([self isIntegerClass: structClassification] && [self isIntegerClass: elementClassification])
                structClassification = TypeTwoIntegers;

In any other circumstance (struct contains more than two elements, struct contains floating-point elements, etc.) the classification is just a generic struct:

            else
                structClassification = TypeStruct;
        }];
        return structClassification;
    }

The method to enumerate over a struct type string's elements is short. A struct type string consists of the struct's name, the = symbol, and then each element's type concatenated together, all contained within a pair of {}. For example, NSRange would look like:

    {NSRange=LL}

The first thing the method does is find the = and start scanning just beyond it:

    - (void)enumerateStructElementTypes: (const char *)type block: (void (^)(const char *type))block
    {
        const char *equals = strchr(type, '=');
        const char *cursor = equals + 1;

Then it enumerates over each type contained within, taking advantage of NSGetSizeAndAlignment to move the cursor to the end of each type encountered, even if the type contains more than one character. It does this until it encounters a closing brace:

        while(*cursor != '}')
        {
            block(cursor);
            cursor = NSGetSizeAndAlignment(cursor, NULL, NULL);
        }
    }

There's also a short helper method that determines whether a particular type classification is considered an integer. This just checks to see if the classification is an object, block, C string, or an actual integer or other pointer:

    - (BOOL)isIntegerClass: (enum TypeClassification)classification
    {
        return classification == TypeObject || classification == TypeBlock || classification == TypeCString || classification == TypeInteger;
    }

This finishes the type classification system. This is somewhat rudimentary compared to the full complexity of the x86-64 spec, but it's enough for MAInvocation's needs. With type classification available, we can finally implement the isStretReturn method used in the initializer:

    - (BOOL)isStretReturn
    {
        return [self classifyType: [_sig methodReturnType]] == TypeStruct;
    }

Setting Arguments
With type classification in place, it's finally time to implement setting arguments. The basic form of setArgument:atIndex: is nearly identical to getArgument:atIndex:, but the need to support retained arguments makes everything far more complicated.

It's possible to create an NSInvocation, set it up, and then keep it around for a while. In order for the NSInvocation to remain valid, it needs to be able to do proper memory management on the arguments it contains. In a nod to flexibility, this is optional. A freshly-made NSInvocation doesn't do any memory management on its arguments, but it can be enabled by sending it a retainArguments message.

MAInvocation mimics this functionality. When it receives retainArguments it performs the following operations on its arguments:

    1. Block arguments are copied.
    2. Non-block object arguments are retained.
    3. C string arguments are copied.
    4. All others are left alone.

In addition to doing this for retainArguments, the setArgument:atIndex: method needs to do this for each newly set argument as well. This is what makes it so much more complex than getArgument:atIndex:.

The method starts off by computing the raw argument index:

    - (void)setArgument: (void *)argumentLocation atIndex: (NSInteger)idx
    {
        NSInteger rawArgumentIndex = idx;
        if(_raw.isStretCall)
            rawArgumentIndex++;

Next, it gets the argument pointer at that index:

        uint64_t *dest = [self argumentPointerAtIndex: rawArgumentIndex];
        assert(dest);

Then it classifies the argument at this index:

        enum TypeClassification c = [self classifyArgumentAtIndex: idx];

If arguments are retained, it will then check the classification of the arguments to see if it's a block, a non-block object, or a C string. If it is, then it directly sets dest to the value found at argumentLocation using the appropriate retain or copy semantics. If argument is of a different type, or if arguments aren't retained, it does a simple memcpy.

The first case is for plain objects. This just does a fairly standard retain/release combination, with a bunch of casting to treat both pointers as object pointers. The release is done at the end using the old variable to avoid problems where releasing the old value invalidates the new one:

        if(_argumentsRetained && c == TypeObject)
        {
            id old = *(id *)dest;
            *(id *)dest = [*(id *)argumentLocation retain];
            [old release];
        }

Blocks get the same treatment, except they get a copy rather than a retain:

        else if(_argumentsRetained && c == TypeBlock)
        {
            id old = *(id *)dest;
            *(id *)dest = [*(id *)argumentLocation copy];
            [old release];
        }

C strings are similar, but use strdup and free:

        else if(_argumentsRetained && c == TypeCString)
        {
            char *old = *(char **)dest;

            char *cstr = *(char **)argumentLocation;
            if(cstr != NULL)
                cstr = strdup(cstr);
            *(char **)dest = cstr;

            free(old);
        }

In all other cases, the appropriate number of bytes is copied over using memcpy:

        else
        {
            NSUInteger size = [self sizeAtIndex: idx];
            memcpy(dest, argumentLocation, size);
        }
    }

The classifyArgumentAtIndex: is a small wrapper around classifyType: that retrieves the argument type from the method signature and classifies it:

    - (enum TypeClassification)classifyArgumentAtIndex: (NSUInteger)idx
    {
        return [self classifyType: [_sig getArgumentTypeAtIndex: idx]];
    }

Retaining Arguments
In addition to retaining each argument as it arrives in setArgument:atIndex:, MAInvocation also needs to retain all existing arguments in the retainArguments method. Only the first call does anything, so the first thing that method does is check to see if arguments are already retained, and bail out if so:

    - (void)retainArguments
    {
        if(_argumentsRetained)
            return;

Next, it iterates over all retainable arguments, using a helper method. This method invokes a block for each retainable argument that passes in the argument index as well as the argument's value. There are three value arguments in the block, and only one is set for any given call.

        [self iterateRetainableArguments: ^(NSUInteger idx, id obj, id block, char *cstr) {

If it's an object argument, then that argument is retained:

            if(obj)
            {
                [obj retain];
            }

If it's a block argument, the block is copied, and the new value set as the argument value. Note that _argumentsRetained has not yet been set to YES, so setArgument:atIndex: won't try to do its own memory management, avoiding any conflict between the two:

            else if(block)
            {
                block = [block copy];
                [self setArgument: &block atIndex: idx];
            }

If it's a C string argument, it uses strdup:

            else if(cstr)
            {
                if(cstr != NULL)
                    cstr = strdup(cstr);
                [self setArgument: &cstr atIndex: idx];
            }
        }];

Finally, it sets _argumentsRetained:

        _argumentsRetained = YES;
    }

The iterateRetainableArguments: method uses the type classification system to figure out what each argument is, then calls getArgument:atIndex: to fetch the value. It first iterates over each argument and classifies it:

    - (void)iterateRetainableArguments: (void (^)(NSUInteger idx, id obj, id block, char *cstr))block
    {
        for(NSUInteger i = 0; i < [_sig numberOfArguments]; i++)
        {
            enum TypeClassification c = [self classifyArgumentAtIndex: i];

Objects and blocks are both handled by the same branch. It first retrieves the argument into a local id variable:

            if(c == TypeObject || c == TypeBlock)
            {
                id arg;
                [self getArgument: &arg atIndex: i];

It then moves arg into one of two other local variables depending on whether the type is a block or a plain object:

                id o = c == TypeObject ? arg : nil;
                id b = c == TypeBlock ? arg : nil;

At this point, o contains the argument value if it's a plain argument, and b contains the argument value if it's a block. The iteration block can then be called with these values:

                block(i, o, b, NULL);
            }

C strings are similar, but less complex, because there's only one possible type here:

            else if(c == TypeCString)
            {
                char *arg;
                [self getArgument: &arg atIndex: i];

                block(i, nil, nil, arg);
            }
        }
    }

While we're at it, here's a quick getter method for argumentsRetained:

    - (BOOL)argumentsRetained
    {
        return _argumentsRetained;
    }

Dealloc
The hardest part of dealloc is freeing the retained arguments. The iterateRetainableArguments: method takes care of most of the work:

    - (void)dealloc
    {
        if(_argumentsRetained)
        {
            [self iterateRetainableArguments: ^(NSUInteger idx, id obj, id block, char *cstr) {
                [obj release];
                [block release];
                free(cstr);
            }];
        }

With that taken care of, all that remains is freeing the method signature, the stackArgs pointer, and calling super:

        [_sig release];
        free(_raw.stackArgs);

        [super dealloc];
    }

Invocation
The code so far has kept the struct RawArguments almost completely up to date. Implementing invokeWithTarget: is simply a matter of filling out the last details, then making a call to the MAInvocationCall assembly glue function. The method starts out by setting the target value:

    - (void)invokeWithTarget: (id)target
    {
        [self setTarget: target];

It then uses methodForSelector: to get the function pointer for the invocation's selector and places that into the fptr field. This is what the glue code will call:

        _raw.fptr = [target methodForSelector: [self selector]];

If this is a stret call, then rdi needs to be set up to point to space that can hold the return value:

        if(_raw.isStretCall)
            _raw.rdi = (uint64_t)[self returnValuePtr];

Finally, call the assembly glue:

        MAInvocationCall(&_raw);
    }

With all of the register fields and the stack arguments pointer set up, and the function pointer field set to the target IMP, the assembly glue is able to make the call. Upon return, the assembly glue copies rax and rdx into the return value fields of the struct RawArguments. This means that the return value is already set when the assembly glue returns, and will be available from getReturnValue: without any additional action in the Objective-C code.

Forwarding
The last major piece of MAInvocation is the MAInvocationForwardC function. The assembly language forwarding glue intercepts unknown message calls. It then constructs a struct RawArguments on the stack from the function call, and then calls through to MAInvocationForwardC, passing it a pointer to the struct RawArguments. The remainder of the logic is implemented in Objective-C:

    void MAInvocationForwardC(struct RawArguments *r)
    {

The first order of business is to get the object that the message was sent to, and the selector being sent. For a stret call, the object is in rsi and the selector is in rdx. For a normal call, the object is in rdi and the selector is in rsi:

        id obj;
        SEL sel;

        if(r->isStretCall)
        {
            obj = (id)r->rsi;
            sel = (SEL)r->rdx;
        }
        else
        {
            obj = (id)r->rdi;
            sel = (SEL)r->rsi;
        }

A method signature is critical to creating an invocation object. With the object and selector available, a simple call to methodSignatureForSelector: obtains that:

        NSMethodSignature *sig = [obj methodSignatureForSelector: sel];

With the method signature in hand, the forwarding function can now create an MAInvocation:

        MAInvocation *inv = [[MAInvocation alloc] initWithMethodSignature: sig];

The next order of business is to copy all of the pertinent information from r into the invocation's_raw` instance variable. First come the registers:

        inv->_raw.rdi = r->rdi;
        inv->_raw.rsi = r->rsi;
        inv->_raw.rdx = r->rdx;
        inv->_raw.rcx = r->rcx;
        inv->_raw.r8 = r->r8;
        inv->_raw.r9 = r->r9;

After that, stack arguments are copied. Although r always contains 0 for stackArgsCount, the invocation has now computed the number of actual stack arguments, so its _raw variable can be consulted to get the count:

        memcpy(inv->_raw.stackArgs, r->stackArgs, inv->_raw.stackArgsCount * sizeof(uint64_t));

The invocation is now fully constructed and filled out. The object is sent forwardInvocation: with the newly constructed invocation.

        [obj forwardInvocation: (id)inv];

After that call returns, the return value from the invocation needs to be copied back into r. The assembly glue will then pass the value back to the caller. It first copies the two return value registers over:

        r->rax_ret = inv->_raw.rax_ret;
        r->rdx_ret = inv->_raw.rdx_ret;

If it's a stret call and the invocation actually has a buffer to hold the return value, the value in the invocation's return value buffer is copied into the memory pointed to by r->rdi, which is where the caller specified that it wanted the return value placed:

        if(r->isStretCall && inv->_stretBuffer)
        {
            memcpy((void *)r->rdi, inv->_stretBuffer, [inv returnValueSize]);
        }

Everything is now complete, so the invocation is released, and control is returned to the assembly language glue:

        [inv release];
    }

The glue code will now copy the rax and rdx fields back into the respective CPU registers, then return control to the original method caller, which will see the return value either in those registers or in the stret buffer that it passed in rdi.

Conclusion
That wraps up the implementation of MAInvocation. It's enormously complicated and involved, despite only supporting x86-64 and ignoring struct parameters and floating point of all kinds, which are a large part of the x86-64 calling conventions. NSInvocation not only supports all types of parameters and return values (aside from a few corner cases like union parameters), it also supports them on at least three different architectures: i386, x86-64, and ARM.

However, despite the complication, it's all very much doable. Covering all of the cases requires a lot of time and effort, but there's nothing mysterious or magical. It would require equivalents of the assembly glue functions for the other architectures, expanding the glue functions to cover the floating-point registers, and implementing all of the logic for which arguments go where in the MAInvocation Objective-C code.

MAInvocation was a lot of fun to build and gives great insight on just what NSInvocation is doing. It should be obvious, but don't use MAInvocation for any real work. NSInvocation does all the same stuff and more, and no doubt does it better.

That's it for today. Come back next time for another breathtaking adventure. Friday Q&A is driven by reader ideas, so until then, please keep sending in your ideas for topics to cover.

Friday Q&A 2013-03-08: Let's Build NSInvocation, Part I

Mike Ash — Fri, 08 Mar 2013 14:33:00 GMT

Friday Q&A 2013-03-08: Let's Build NSInvocation, Part I

It's time for another trip into the nether regions of the soul. Reader Robby Walker suggested an article about NSInvocation, and I have obliged, implementing it from scratch for your amusement. Today I'll start on a guided tour down the hall of horrors that is MAInvocation, my reimplementation of the NSInvocation API. It's a big project, so today I'm going to focus on the basic principles and the assembly language glue code, with the rest of the implementation to follow.

Code
The code for MAInvocation is available on GitHub here:

https://github.com/mikeash/MAInvocation

Overview
An NSInvocation object represents a single method invocation. A method invocation has a target, a selector, a set of arguments, and a return value.

Just holding these values would be pretty boring. You can whip up a model class pretty easily to do that. Have a variable for the return value, an array for the arguments, and you're done. (The target and selector are just the first and second arguments.) Where NSInvocation gets interesting is in its ability to actually capture and send the invocations that it represents.

An NSInvocation can be invoked on a particular object. This does the equivalent of code like [target message: argument], except that the target, the message, and the arguments are all determined entirely at runtime. The NSInvocation can be constructed in code using runtime introspection without knowing anything about the method ahead of time.

Furthermore, an NSInvocation can be constructed from an attempted message send. If you write [target message: argument], and target doesn't actually implement message:, then it gets a forwardInvocation: call, which is given an NSInvocation * representing the invocation. It can then do whatever it wishes with that invocation, such as invoking it on another object, fiddling with the parameters, or setting an arbitrary return value which is passed back to the caller.

NSInvocation therefore has two complementary pieces of tricky business:

Code that's able to take a set of arguments, use them to make a method call, and collect the return value.
Code that's able to receive a method call, collect the arguments, then return an arbitrary return value to the caller.

Both pieces require extensive knowlede of the CPU architecture's calling conventions encoded in the implementation, as well as assembly language glue code.

Calling Conventions
Because so much architecture-specific code is needed, I decided to focus on a single architecture. x86-64 is the most convenient one to use for us Mac types. To further simplify things, I decided not to support floating-point arguments or return values, and also gave up on struct arguments, although I did implement support for struct return values. The following discussion ignores those parts that I didn't implement.

In order to implement even this limited MAInvocation, it's necessary to understand the relevant parts of the x86-64 function calling conventions, and in order to understand that, you must first understand at least a bit of the x86-64 architecture in general.

The x86-64 architecture is a 64-bit extension of Intel's 32-bit x86 architecture introduced with the 386 CPU. That is in turn an extension of the Intel 8086's 16-bit architecture which is in turn heavily based on the 8-bit architecture of the Intel 8080, generally considered to be the first microprocessor worth building a computer around. It could address a whopping 64kB of RAM, just enough to hold one medium-sized app icon these days.

There are sixteen general-purpose registers: rax, rbx, rcx, rdx, rbp, rsp, rsi, rdi, r8, r9, r10, r11, r12, r13, r14, and r15. The first half are all inherited from Intel's 32-bit architecture, while the second half are new additions for x86-64. Each register holds 64 bits.

Pointers and integers are treated identically when it comes to these calling conventions. Both are simply 64-bit quantities. Smaller integers are extended to 64 bits in size.

When calling a function, the first six parameters are passed by filling these registers in order: rdi, rsi, rdx, rcx, r8, and r9. Additional arguments, if any, are passed on the stack as 64-bit quantities, so subsequent parameters can be found in memory at rsp, rsp + 8, rsp + 16, etc.

If the function returns a value, that value is returned by storing it in rax. If the function returns two values, such as when returning a struct like NSRange that contains two values, rdx is used for the second one. If the function returns a larger struct, this is handled by having the caller allocate enough memory to hold it, and then a pointer to that memory is passed as an implicit first argument to the function in rdi, with all of the explicit parameters moved down by one.

Note that, for Objective-C methods, the first two parameters are self and _cmd, which are therefore passed in rdi and rsi (or, if the method returns a larger struct, in rsi and rdx). The explicit parameters, if any, come after those two.

As far as I know, there's no particular fundamental reason for the number of registers used to pass parameters, or which ones are used. Calling conventions are a tradeoff between placing a burden on the caller, placing a burden on the callee, making parameter passing more efficient, and making surrounding code more efficient. These conventions presumably sit near some reasonable compromise between all of the competing desires.

In order to make a function call, MAInvocation needs to take the parameters to the function, place the first six in the appropriate registers, place any additional ones on the stack, then needs to actually jump to the function's address. Upon return, it needs to record the values in the two return-value registers.

In order to receive a function call, MAInvocation needs to record the values of the six parameter-passing registers, as well as the location of the stack pointer, and use these to extract the argument values. Upon returning, it needs to place the desired return values into the two return-value registers. The logic of which values go into registers and the stack can be written in Objective-C, but the code that actually manipulates the registers and the stack needs to be written in assembly.

Data Structure
In order to cleanly communicate between the Objective-C and assembly code, I defined a struct that contains all of the relevant code. When making a call, MAInvocation will fill out the struct as appropriate, then invoke the assembly language glue code. When receiving a call, the assembly language glue code will construct the struct from the current state, then pass it over to the Objective-C code. Not all fields will be useful in both situations, but it's easier to use the same struct for everything rather than try to specialize.

The first thing this struct contains is the address of the function to call:

    struct RawArguments
    {
        void *fptr;

Next, it stores the values of the six 64-bit parameter-passing registers:

        uint64_t rdi;
        uint64_t rsi;
        uint64_t rdx;
        uint64_t rcx;
        uint64_t r8;
        uint64_t r9;

It then stores the address of the arguments passed on the stack, as well as how many stack arguments there are:

        uint64_t stackArgsCount;
        uint64_t *stackArgs;

After that, it stores the two return-value registers:

        uint64_t rax_ret;
        uint64_t rdx_ret;

rdx already exists in the parameter-passing section, but it's easier to make a separate entry for return values than to reuse that field.

Finally, it keeps a flag that records whether or not the call uses struct return conventions, i.e. whether the rdi is used to store a pointer to space allocated for the return value. In Objective-C runtime terminology, such calls are called stret, short for "struct return":

        uint64_t isStretCall;
    };

"Struct return" is something of a misnomer, since small structs are returned in registers, but that's how it is. When you see "struct return" or "stret", think "sufficiently large struct return".

Function Call Glue
The function call glue is a function with this C signature:

    void MAInvocationCall(struct RawArguments *);

It is implemented in assembly, but with the above prototype, the Objective-C code can call it as if it were a C function. It will pass a filled-out struct RawArguments and the assembly glue will make the call.

The assembly code first declares the symbol. It's marked as global so it's accessible from other parts of the program. The leading underscore is due to ancient history involving Fortran, and every C symbol implicitly gets one. A non-C symbol that expects to be accessible from C code needs to have it as well:

    .globl _MAInvocationCall
    _MAInvocationCall:

The first thing any well-behaved x86-64 function is save the old frame pointer (stored in rbp) and set up a new one by copying the stack pointer over:

    pushq %rbp
    movq %rsp, %rbp

I'll use r12 through r15 in the following code. These registers are designated as callee-saved by the platform calling conventions, meaning that we're not allowed to just obliterate their contents. Instead, we save their values onto the stack so they can be restored later:

    pushq %r12
    pushq %r13
    pushq %r14
    pushq %r15

The struct RawArguments * parameter is stored in rdi. It's the first parameter to the function, and the calling conventions state that the first parameter is passed it rdi. We need to use rdi for the first parameter to the function being called, so we save the current value into r12. The various elements of the struct RawArguments parameter can be accessed by loading various offsets from r12:

    mov %rdi, %r12

Now it's ready to start copying arguments where they need to go. Because this requires manipulating the stack pointer, it copies the stack pointer into r15 so it's easy to restore later:

    mov %rsp, %r15

Stack arguments get copied first, for no particular reason. It does make the code to copy them slightly easier to write, as it can use the argument-passing registers as scratch space, since they don't contain anything important. The first thing it does is load the number of stack arguments, which is located at offset 56 in the struct Rawarguments:

    movq 56(%r12), %r10

If you're wondering where 56 comes from, each member in this struct is 8 bytes, and the number of stack arguments is the 8th element in the struct, meaning that it comes after space for 7 other elements. 7 * 8 = 56. All the offsets in this code are computed in the same way.

r10 now contains the number of stack arguments that need to be copied. Next, it computes the amount of stack space needed for these arguments. This is equal to the number of arguments multiplied by 8 (each argument is 64 bits, or 8 bytes). It does this by copying the number of arguments into r11, then shifting it left by three bits, which is equivalent to multiplying by 8:

    movq %r10, %r11
    shlq $3, %r11

Next, it loads the stack argument pointer from offset 64 in the struct RawArguments into r13:

    movq 64(%r12), %r13

Let's take a moment to recap what the temporary registers contain at the moment:

r10: the number of stack arguments to copy.
r11: the number of bytes needed for stack arguments.
r13: the stack argument pointer.

We don't get to give things convenient names in assembly, so it's essential to keep careful track of what contains what at any given moment.

The next step is to move the stack pointer down to make room for the arguments, which is done by subtracting r11 from the stack pointer:

    subq %r11, %rsp

The stack is also required to be 16-byte aligned before making a function call, and this is done by just doing a logical AND with a value that has the bottom four bits cleared:

    andq $-0x10, %rsp

The stage is now set. At this point, we just execute a simple memory copy loop. The equivalent C code would be:

    for(int i = 0; i != r10; i++)
        rsp[i] = r13[i];

r14 will serve as the loop counter. The first step is to initialize it to zero:

    movq $0, %r14

The top of the loop needs a label so that later code can easily jump back to it:

    stackargs_loop:

Next comes the check for r14 != r10:

    cmpq %r14, %r10
    je done

The cmp instruction compares the two registers and sets the contents of the FLAGS register accordingly. The je instruction then jumps to the done label if the FLAGS register indicats that the two are equal. This two-stage construct is a bit odd, but it's how x86-64 works.

If the two aren't equal, the loop continues. The next step is to copy the current argument. This is done in two stages. First, the argument is copied from the memory pointed to by r13 into a temporary register, in this case rdi. Next, the argument is copied from rdi into the memory pointed to by rsp:

    movq 0(%r13, %r14, 8), %rdi
    movq %rdi, 0(%rsp, %r14, 8)

The parenthetical expressions are a little scary. x86-64 allows memory references with a bunch of different components, which makes it easier to do computed array dereferences like this. The general form of the expression looks like:

    offset(%r1, %r2, elementSize)

This refers to this address:

    r1 + r2 * elementSize + offset

This can be thought of as an array dereference. r1 is the array pointer, r2 is the index, elementSize is the size of each element in the array, and offset is just a final fixup to apply to the whole result. In short, 0(%r13, %r14, 8) is equivalent to ((uint64_t *)r13)[r14].

After that comes the i++, which has a simple assembly equivalent:

    inc %r14

Finally, a jump back to stackargs_loop completes the loop, with the done label following it so that execution resumes below once the loop exits:

    jmp stackargs_loop

    done:

The stack arguments are now ready to go. All that remains is to copy the register arguments into their actual registers. This is done by writing a sequence of move instructions:

    movq 8(%r12), %rdi
    movq 16(%r12), %rsi
    movq 24(%r12), %rdx
    movq 32(%r12), %rcx
    movq 40(%r12), %r8
    movq 48(%r12), %r9

With everything ready, it's time to call the target function. The function pointer is conveniently located right at the location pointed to by r12, since it's the first element in the struct RawArguments. This instruction makes the call:

    callq *(%r12)

Once the call returns, the return value (if any) is found in rax and rdx. The code immediately copies the contents of these registers into the struct RawArguments:

    movq %rax, 72(%r12)
    movq %rdx, 80(%r12)

It's just about done. The only thing that needs to be done, aside from returning, is to restore the values stored in r12-r15 to whatever the caller had in them. First, the stack pointer needs to be restored to what it was after those registers were pushed onto the stack:

    mov %r15, %rsp

Then they're popped off in the opposite order from which they were pushed:

    popq %r15
    popq %r14
    popq %r13
    popq %r12

Finally, control is returned to the caller, using a magic combination of instructions which readjust the stack and frame pointer before jumping to the caller's address:

    leave
    ret

That takes care of the glue code for function calls. The Objective-C code can now fill out a struct RawArguments to suit the call being made, then call MAInvocationCall and pass the pointer to the struct to make the call.

Forwarding Glue
Capturing a method invocation is called "forwarding" in Objective-C. The runtime has a special forwarding handler, which is called any time an implementation can't be found for a particular selector. In fact, there are two different forwarding handlers: one for normal calls, and one for stret calls. The forwarding handler needs to know where to find the self and _cmd parameters, and the locations of those parameters change for a stret call, so a bit of specialization is required.

The strategy here is to have two entry points that call through to a common implementation after making a note of whether or not it's a stret call. The common implementation then fills out a new struct RawArguments accordingly and calls into an Objective-C function. Once that function returns, it copies the return value back out into the return value registers, then returns.

The r10 register doesn't contain anything in particular when a function is called, but neither is it required to save the value. This makes it a good spot to store the stret flag temporarily. The normal forwarding handler will set it to 0 before jumping to the common implementation, and the stret handler will set it to 1. Here's the normal handler in its entirety:

    .globl _MAInvocationForward
    _MAInvocationForward:
    movq $0, %r10
    jmp _MAInvocationForwardCommon

The stret handler is nearly identical:

    .globl _MAInvocationForwardStret
    _MAInvocationForwardStret:
    movq $1, %r10
    jmp _MAInvocationForwardCommon

All the interesting stuff happens in the common handler:

    .globl _MAInvocationForwardCommon
    _MAInvocationForwardCommon:

The first thing it does is calculate the location of the stack arguments passed in to the function. The stack arguments start at rsp + 8 from the callee's point of view. The call instruction issued by the caller pushes the return address onto the stack, which is why stack arguments start right at rsp from that side of things, but not here. r11 is another convenient register that neither contains anything useful nor needs to be saved, so the code computes the address in that register:

    movq %rsp, %r11
    addq $8, %r11

Then the function performs the standard prologue of setting up the frame pointer:

    pushq %rbp
    movq %rsp, %rbp

Now it's finally time to construct the struct RawArguments. This is done by pushing values onto the stack. First, a quick recap of what the various register contain right now:

r10: the isStretCall flag.
r11: the pointer to the stack arguments.
rdi-r9: register arguments.

The handler uses the pushq instruction to construct the struct on the stack. Because it's pushing onto the stack, it needs to push everything in reverse order. Because isStretCall is the last thing in the struct, it's the first thing to be pushed:

    pushq %r10

The return value registers don't need to contain anything in particular, so it makes space for them by pushing zero twice:

    pushq $0
    pushq $0

Next comes the stackArgs pointer, whose value is currently in r11:

    pushq %r11

After that comes the number of stack arguments. This is not currently known, so the handle just pushes a zero to make room for it. That field will be filled out by the Objective-C code:

    pushq $0

Next come the argument registers, which are pushed in reverse order:

    pushq %r9
    pushq %r8
    pushq %rcx
    pushq %rdx
    pushq %rsi
    pushq %rdi

The very first field of the struct is the function pointer. That's not used here, so another zero is pushed to make room for it:

    pushq $0

At this point, rsp now contains a pointer to the newly-built struct RawArguments. The goal is to call a C function with this prototype:

    void MAInvocationForwardC(struct RawArguments *r);

The pointer to the struct is its only parameter, so that address needs to be moved to rdi, where the first parameter is passed:

    movq %rsp, %rdi

The handler needs to consult the struct afterwards to extract the return value registers. Since rdi isn't saved across the function call, and rsp may be changed when aligning the stack for the call, the handler also copies the address into r12 so it can be used afterwards:

    movq %rdi, %r12

It's now time to align the stack and call into Objective-C:

    andq $-0x10, %rsp
    callq _MAInvocationForwardC

The Objective-C code will now construct an MAInvocation instance and invoke the object's forwardInvocation: method.

Once control returns, the return value, if any, is found in the struct. To make them visible to the caller, that value is copied out of the struct and into the appropriate registers:

    movq 72(%r12), %rax
    movq 80(%r12), %rdx

That's it! Return to the caller:

    leave
    ret

The Objective-C runtime's forward handlers are, amazingly, configurable. To set them to this code, all you have to do is call this somewhere convenient:

    objc_setForwardHandler(MAInvocationForward, MAInvocationForwardStret);

The runtime will then use these forward handlers for all unimplemented selectors.

Conclusion
That wraps up the assembly language glue code and the basic knowledge of calling conventions. Much work remains, but the two glue functions here provide the necessary foundation that the Objective-C parts of MAInvocation can be built on. MAInvocation needs to manage a struct RawArguments and translate between the contents of that struct and the arguments and return values provided and requested by the clients of the API. To make a method call, it needs to arrange the struct properly, then call into the above glue code. To receive a method call, it needs to construct a new MAInvocation from the struct contents.

All this shall be covered next time. Until then, please send in your ideas for topics to cover on Friday Q&A. The next article may be spoken for, but your suggestions for the future are always welcome.

Friday Q&A 2013-02-22: Let's Build UITableView

Matthew Elton — Fri, 22 Feb 2013 15:35:00 GMT

Friday Q&A 2013-02-22: Let's Build UITableView

Friday Q&A is driven by the readers, and that's especially true today. Reader Matthew Elton thought that "Let's Build UITableView" would make a good topic for Friday Q&A, but he decided he'd rather implement it himself and write it up rather than wait for me to do it (good move, Matthew). Without further ado, here is Matthew's article an building UITableView.

Let's Build UITableView
UITableView is a powerful and full featured class, but its internal workings can seem mysterious. Most of the time use of the class is straightforward: in return for following the prescribed practice in the documentation, the developer gets a responsive scrolling table that is frugal with memory even when the row count is high. But when pushing the class hard, for example with large tables where each row may have a different and varying height, it helps to have a deeper understanding of how the class works.

In this article, I am going to implement a basic version of a table view class. This will show how the class works its magic and also show just why UITableView asks what it does - and when - of its data source and delegate.

Implementation Strategy
UITableView is a subclass of UIScrollView and, with the power of that class in place, it takes only a little work to implement a basic version of a table view. Before diving into code, consider two key tasks needed to keep performance high and memory usage low.

The table view is going to need a pool of reusable views for displaying the rows in the table. Why is this?
- Consider a table with, say, a 1000 rows. To the user, it looks as if there are a 1000 views all neatly stacked one upon the other. Although building views is fast and modern devices do have a lot of memory, if the table view has to build and store a 1000 views, there is serious risk of a performance hit. It might mean, for example, that there's a nasty lag before the table first appears. Not good.
- Fortunately, the table view does not need to take this approach. It only needs to behave as if it has a 1000 neatly stacked views. In fact, the table view only needs actual views for the rows in the table that are visible at any given time. Typically this is a fairly small number. And, in any case, it's reliably much smaller than a 1000. To make the illusion work, the table view just needs to move a few views around, so they appear in the part of the scroll view that is visible to the user. Then it has to make sure their contents are updated according to the row they are currently representing. Recycling views from a pool, rather than making new views each time they are needed, ensures things happen fast enough for smooth scrolling even on older iOS devices.
The table view is also going to need to know the starting position and height of each row in the table. And, critically, it will need this information before it attempts any layout at all. Why is this?
- First, it needs to know how tall the table is so it can tell the scroll view the size of its contents and, thus, ensure that the scroll bars are the right size, that when the user gets to the bottom of the table they experience the pleasing elastic band effect, and so on.
- Second, whenever the scroll view moves, the table view needs to figure out how to reposition its reusable views and whether it needs to refresh their contents.

It turns out that the reusable pool is very simple to implement, so we'll do that first. The mechanism for coordinating rows, their offsets and their contents, is only a little trickier. We'll do that second and build it up by stages.

A Reusable Pool of Views
UITableView keeps a pool of reusable views, Apple calls it a queue, with each view representing a single row of the table. Often every row of the table is similar but sometimes tables have different types of rows. So UITableView asks its data source to specify a reuse identifier when working with the pool of reusable views. A reuse identifier is an NSString that is passed to the UITableView method dequeueReusableCellWithIdentifier:.

The dequeueReusableCellWithIdentifier: method asks the UITableView to return a view. With a fresh UITableView the pool will be empty and the method will return nil. But once a UITableView is up and running, it may well have views in its pool. If it does and if their reuse identifier matches that specified in the dequeueReusableCellWithIdentifier: call, then this view is returned.

If you've used UITableView at all, you'll be familiar with the standard pattern for using dequeueReusableCellWithIdentifier:. In your data source, you implement the tableView:cellForRowAtIndexPath: method to return a view to represent a given row of your table. At the start of the method, you either grab a view from the pool or make a new one. Either way you populate the view with data for the row. Typical codes looks like this:

    - (UITableViewCell*) tableView:(UITableView*) tableView cellForRowAtIndexPath:(NSIndexPath*) indexPath
    {
        UITableViewCell* cell = [tableView dequeueReusableCellWithIdentifier: @"standardRow"];
        if (!cell)
        {
            cell = [[UITableViewCell alloc] initWithStyle: UITableViewCellStyleDefault reuseIdentifier: @"standardRow"];
            [cell autorelease];
        }

        [self populateCell: cell forIndexPath: indexPath];
        return cell;
    }

OK, so let's implement dequeueReusableCellWithIdentifier:.

    - (PGTableViewCell*) dequeueReusableCellWithIdentifier: (NSString*) reuseIdentifier
    {
        PGTableViewCell* poolCell = nil;

        for (PGTableViewCell* tableViewCell in [self reusePool])
        {
            if ([[tableViewCell reuseIdentifier] isEqualToString: reuseIdentifier])
            {
                poolCell = tableViewCell;
                break;
            }
        }

        if (poolCell)
        {
            [poolCell retain];
            [[self reusePool] removeObject: poolCell];
            [poolCell autorelease];
        }

        return poolCell;
    }

In this implementation the reusePool property is an NSMutableArray. And a PGTableViewCell is simply a subclass of UIView that has one additional property, an NSString called reuseIdentifier. The real UITableViewCell has lots of extra functionality, but this property is all that's needed for our basic implementation.

The method assumes that any view in reusePool is available, i.e it is not currently being used to display a visible row. Of course, for the method to do its job, the table view will need to make sure that relevant views are added to it. That is, it'll need to work out when a row is moved off screen and, at that point, add it to the reuse pool.

Gathering Height and Vertical Offset Data
UITableView cheerfully copes with fixed and variable row heights and our basic implementation will be no different. If the delegate responds to the tableView:heightForRowAtIndexPath: method, then a UITableView will ask the delegate for the height of every row. It gets to know about the number of rows in the table by asking the data source using the tableView:numberOfRowsInSection: method (which is required) and the optional numberOfSectionsInTableView: method. (If this method isn't implemented, the table view assumes you have just one section.)

For our implementation, we will simplify a little. Our table will not have any sections, so we just need to learn about the number of rows. We'll require our data source to implement numberOfRowsInPgTableView. And, following Apple, we'll offer an optional pgTableView:heightForRow: method as part of the delegate protocol.

    - (void) generateHeightAndOffsetData
    {
        CGFloat currentOffsetY = 0.0;

        BOOL checkHeightForEachRow = [[self delegate] respondsToSelector: @selector(pgTableView:heightForRow:)];

        NSMutableArray* newRowRecords = [NSMutableArray array];

        NSInteger numberOfRows = [[self dataSource] numberOfRowsInPgTableView: self];

        for (NSInteger row = 0; row < numberOfRows; row++)
        {
            PGRowRecord* rowRecord = [[PGRowRecord alloc] init];

            CGFloat rowHeight = checkHeightForEachRow ? [[self delegate] pgTableView: self heightForRow: row] : [self rowHeight];

            [rowRecord setHeight: rowHeight + _pgRowMargin];
            [rowRecord setStartPositionY: currentOffsetY + _pgRowMargin];

            [newRowRecords insertObject: rowRecord atIndex: row];
            [rowRecord release];

            currentOffsetY = currentOffsetY + rowHeight + _pgRowMargin;
        }

        [self setRowRecords: newRowRecords];

        [self setContentSize: CGSizeMake([self bounds].size.width,  currentOffsetY)];
    }

The code builds an array of PGRowRecord instances that capture what we will need to perform our layout work. A PGRowRecord records the starting position of a row, its height and - as we'll see later - a pointer to the view that represents the row if the row is visible. The generateHeightAndOffsetData method has no idea what is visible or not, so it doesn't set the pointer to the view.

As the code shows, we need to check to see if the delegate is up for providing height information. If it is then we ask it once for each row in the table.

Arguably, there is room for greater efficiency here. The height of a given row could be derived by subtracting the current starting position from the next starting position (and having some record of the very last starting position, i.e. the start of the row after the last row). And, in addition, for the case of fixed height rows, we could pass on storing start positions and heights altogether, but simply calculate them when needed. But it looks as if we might need the array anyway, because we need to keep track of whether a given row is currently visible. So we'll leave this method as is for now.

Laying Out the Rows
Having gathered start positions and heights, the work of laying out the views is straightforward. The table view fetches its contentOffset, a property of the UIScrollView that indicates the start of the visible section of the view. It then figures out the first row that needs to be shown, stepping forward one row at a time until the visible section of the view is filled up.

The only complexity here is keeping careful track of which rows are displayed so the table view can then check to see if any that were previously visible have now gone. In that case, it will want to put them back in the pool for reuse. The returnNonVisibleRowsToThePool: method will do this work if required.

    - (void) layoutTableRows
    {
        CGFloat currentStartY = [self contentOffset].y;
        CGFloat currentEndY = currentStartY + [self frame].size.height;

        NSInteger rowToDisplay = [self findRowForOffsetY: currentStartY inRange: NSMakeRange(0, [[self rowRecords] count])];

        NSMutableIndexSet* newVisibleRows = [[NSMutableIndexSet alloc] init];

        CGFloat yOrigin;
        CGFloat rowHeight;
        do
        {
            [newVisibleRows addIndex: rowToDisplay];

            yOrigin = [self startPositionYForRow: rowToDisplay];
            rowHeight = [self heightForRow: rowToDisplay];

            PGTableViewCell* cell = [self cachedCellForRow: rowToDisplay];

            if (!cell)
            {
                cell = [[self dataSource] pgTableView: self cellForRow: rowToDisplay];
                [self setCachedCell: cell forRow: rowToDisplay];

                [cell setFrame: CGRectMake(0.0, yOrigin, [self bounds].size.width, rowHeight - _pgRowMargin)];
                [self addSubview: cell];
            }

            rowToDisplay++;
        }
        while (yOrigin + rowHeight < currentEndY && rowToDisplay < [[self rowRecords] count]);

        [self returnNonVisibleRowsToThePool: newVisibleRows];

        [newVisibleRows release];
    }

This method is going to get called a lot. Every time you scroll the table or, indeed, every time the system does, this method will need to be called. Ensuring that it is is achieved by overriding the superclass setContentOffset: method as follows.

    - (void) setContentOffset:(CGPoint)contentOffset
    {
        [super setContentOffset: contentOffset];
        [self layoutTableRows];
    }

If you are playing with this code, you can put an NSLog in here to get a feel for the frequency of calls, not least because this drives home the importance of ensuring the layoutTableRows is fast.

One thing that could really slow down layoutTableRows would be inefficiency in the findRowForOffsetY:inRange method. So it seemed worth putting a little effort into this. Because the array of rowRecords is already sorted, we can take advantage of the NSArray method indexOfObject:inSortedRange:options:usingComparator:. This performs a binary search to home in on the first row that is needed for the current vertical offset of the UIScrollView. For a table of 6000 rows or so, this method can be 100 times faster than just cranking through the list of rows from the start. That said, after doing some measuring it became clear that even unoptimised iteration is fast enough most of the time. By 'fast enough' here I mean that doing it inefficiently has no discernible impact on the user experience, at least for tables up to 10,000 rows.

    - (NSInteger) findRowForOffsetY: (CGFloat) yPosition inRange: (NSRange) range
    {
        if ([[self rowRecords] count] == 0) return 0;

        PGRowRecord* rowRecord = [[PGRowRecord alloc] init];
        [rowRecord setStartPositionY: yPosition];

        NSInteger returnValue = [[self rowRecords] indexOfObject: rowRecord
                                                   inSortedRange: NSMakeRange(0, [[self rowRecords] count])
                                                         options: NSBinarySearchingInsertionIndex
                                                 usingComparator: ^NSComparisonResult(PGRowRecord* rowRecord1, PGRowRecord* rowRecord2){
                if ([rowRecord1 startPositionY] < [rowRecord2 startPositionY])
                    return NSOrderedAscending;
                return NSOrderedDescending;
        }];
        [rowRecord release];
        if (returnValue == 0) return 0;
        return returnValue - 1;
    }

The final method used by layoutTableRows is returnNonVisibleRowsToThePool: This makes use of some handy methods provided by the NSMutableIndexSet class to figure out which, if any rows, are now no longer visible. For all that are, it clears the pointer to the view in the row's PGRowRecord instance, removes the view from its superview and then adds it into the pool.

    - (void) returnNonVisibleRowsToThePool: (NSMutableIndexSet*) currentVisibleRows
    {
        [[self visibleRows] removeIndexes: currentVisibleRows];
        [[self visibleRows] enumerateIndexesUsingBlock:^(NSUInteger row, BOOL *stop)
         {
             PGTableViewCell* tableViewCell = [self cachedCellForRow: row];
             if (tableViewCell)
             {
                 [[self reusePool] addObject: tableViewCell];
                 [tableViewCell removeFromSuperview];
                 [self setCachedCell: nil forRow: row];
             }
         }];
        [self setVisibleRows: currentVisibleRows];
    }

Nearly Done
That's all the hard work. The reloadData method just uses code we've already written. Because the generateHeightAndOffsetData method is going to discard the current record of visible cells, the reloadData method takes care to remove all the currently visible views first.

    - (void) reloadData
    {
        [self returnNonVisibleRowsToThePool: nil];
        [self generateHeightAndOffsetData];
        [self layoutTableRows];
    }

The rest is just housekeeping, such as setting up data source and delegate protocols and providing some convenience methods for accessing our array of PGRowRecords. The details are in the full source, along with a bonus row:changedHeight: method which allows for a row to change height without forcing the delegate to provide new height information for every other row.

The source includes a small test app so you can see PGTableView working, showing the text of this article with three different row types: code, headings, and text. The test app lets you turn off the reuse pool so you can see the difference in performance and also lets you run measurements for two variants of findRowForOffset:inRange.

See https://github.com/Obliquely/Let-s-Build-UITableView for the source, including the test app. The code here is for learning purposes and is not production tested. If you want to make use of any of the code, please feel free.

Conclusion
One of the things this exercise reveals is just why UITableView has to ask for the height of every row when you call the reloadData method. When tables have many rows and when the cost of calculating the height of a row is high, this requirement can be a burden. In such cases, it can make sense to cache row heights so that they don't all have to be recalculated when you or the table view calls reloadData, e.g. to add an extra row or because the height of one row has changed. And, in addition, if your table needs to cope with a change orientation that then calls for row height adjustments, you can do work in the background calculating the heights in the orientation you're not in, so that if or when the change comes, the work is already done.

Given that we know the UITableView must be keeping its own cache of row heights, it is perhaps mildly annoying that this caching work may need to be done twice. After all, given what we have seen here it seems likely that any implementation would have scope to implement insert, delete, and move methods in such a way that they didn't need to trigger a call tableView:heightForRowAtIndexPath: on every row. And it seems likely that it would be easy easy for Apple to implement a rowAtIndexPath:changedHeight: method top cope with growing or shrinking rows. Still, the fully featued UITableView is a mighty class. So perhaps it's not seemly to carp about such a minor detail.

Friday Q&A 2013-02-08: Let's Build Key-Value Coding

Mike Ash — Fri, 08 Feb 2013 14:17:00 GMT

Friday Q&A 2013-02-08: Let's Build Key-Value Coding

Last time, I showed how to build the basic functionality of NSObject. I left out key-value coding, because the implementation of valueForKey: and setValue:forKey: is complex enough to need its own article. This is that article.

Basics
Key-value coding (KVC) is an API that allows string-based access to object properties. NSObject implements the methods to look up accessor methods or instance variables based on the key name, and fetch or set the value using those.

There are two basic methods that form the basis of KVC.

The valueForKey: method searches for a getter method with the same name as the key. If found, it calls the method and returns its return value. If none is found, it searches for an instance variable with the same name as the key. Failing those, it looks for an instance variable with the same name as the key, but prefixed with an underscore. If an instance variable is found, it returns the value it currently holds.

The setValue:forKey: method performs the same search, except that it searches for a setter method rather than a getter. It then either calls the setter or sets the instance variable directly.

An interesting feature of both of these methods is that they work with primitive values by automatically boxing and unboxing them into instances of NSNumber or NSValue. You can use valueForKey: to invoke a method that returns int, and the result will be an NSNumber object containing the return value. Likewise, you can use setValue:forKey: to invoke a method that takes int, pass it an NSNumber, and it will automatically extract the integer value.

KVC also has the concept of key paths, which are sequences of keys put together with periods, like:

    foo.bar.baz

There are corresponding methods to work with key paths: valueForKeyPath: and setValue:forKeyPath:. These simply call the more primitive methods recursively.

There are a bunch of other KVC features for managing collections, but these are less interesting and I'm going to skip over them here.

Code
Today's code is available on GitHub as part of the MAObject project:

https://github.com/mikeash/MAObject

Let's get to it.

valueForKey:
The first thing that valueForKey: does is check for a getter method with the same name as the key.

    - (id)valueForKey: (NSString *)key
    {
        SEL getterSEL = NSSelectorFromString(key);
        if([self respondsToSelector: getterSEL])
        {

If the object responds to that selector, it will use the accessor to get the value. Exactly how that's done will depend on the accessor's return type. To get ready, it fetches the return type and IMP for the method:

            NSMethodSignature *sig = [self methodSignatureForSelector: getterSEL];
            char type = [sig methodReturnType][0];
            IMP imp = [self methodForSelector: getterSEL];

If the return type is an object or a class, then the code is simple: cast the IMP to the right function pointer type, call it, and return what it returns:

            if(type == @encode(id)[0] || type == @encode(Class)[0])
            {
                return ((id (*)(id, SEL))imp)(self, getterSEL);
            }

Otherwise, the method returns a primitive, which is where things get interesting.

There is no convenient way to take a function pointer with an arbitrary type, call it, and box up the result. We have to do things the brute-force way, by enumerating all of the possibilities one by one and writing code to handle each possible type. I created a small macro to help with this:

            else
            {
                #define CASE(ctype, selectorpart) \
                    if(type == @encode(ctype)[0]) \
                        return [NSNumber numberWith ## selectorpart: ((ctype (*)(id, SEL))imp)(self, getterSEL)];

The idea is that each type gets a single line. You pass the type name as one parameter, and a selector part that fits in with [NSNumber numberWithType:] as the other parameter. The macro uses these to construct code that checks for the type and calls the IMP with the right function pointer type if it matches. With this macro, it's just a matter of writing out every supported primitive type:

                CASE(char, Char);
                CASE(unsigned char, UnsignedChar);
                CASE(short, Short);
                CASE(unsigned short, UnsignedShort);
                CASE(int, Int);
                CASE(unsigned int, UnsignedInt);
                CASE(long, Long);
                CASE(unsigned long, UnsignedLong);
                CASE(long long, LongLong);
                CASE(unsigned long long, UnsignedLongLong);
                CASE(float, Float);
                CASE(double, Double);

Let's not forget to undefine the CASE macro so we can reuse the name later:

                #undef CASE

If a matching case was found, then the method returned immediately. If the method is still running at this point, then the type isn't known. Rather than try to handle this gracefully somehow, the method just throws an exception to complain:

                [NSException raise: NSInternalInconsistencyException format: @"Class %@ key %@ don't know how to interpret method return type from getter, signature is %@", [isa description], key, sig];
            }
        }

That was the code to handle the case where a getter method exists. If no getter exists, then KVC falls back to instance variables. First, it tries to get an instance variable with the same name as the key:

        Ivar ivar = class_getInstanceVariable(isa, [key UTF8String]);

If that fails, it tries again with a leading underscore:

        if(!ivar)
            ivar = class_getInstanceVariable(isa, [[@"_" stringByAppendingString: key] UTF8String]);

If either of those found an instance variable, it proceeds to actually fetching its value. In order to fetch the contents of the variable, we need to know where it's stored. This is done by getting the variable's offset, and adding it to the value of self:

        if(ivar)
        {
            ptrdiff_t offset = ivar_getOffset(ivar);
            char *ptr = (char *)self;
            ptr += offset;

self is cast to char * first, because the offset is in bytes, and operating on a char * ensures that the += operation does what we need.

We also need to know the type of the variable:

            const char *type = ivar_getTypeEncoding(ivar);

If the type is an object or class, then it just extracts the value directly and returns it:

            const char *type = ivar_getTypeEncoding(ivar);
            if(type[0] == @encode(id)[0] || type[0] == @encode(Class)[0])
            {
                return *(id *)ptr;
            }

Otherwise, it falls back to special cases again. This code uses a slightly different CASE macro. This one checks the type and then extracts the value from ptr if there's a match:

            else
            {
                #define CASE(ctype, selectorpart) \
                    if(strcmp(type, @encode(ctype)) == 0) \
                        return [NSNumber numberWith ## selectorpart: *(ctype *)ptr];

Once again, there's a long list of supported types:

                CASE(char, Char);
                CASE(unsigned char, UnsignedChar);
                CASE(short, Short);
                CASE(unsigned short, UnsignedShort);
                CASE(int, Int);
                CASE(unsigned int, UnsignedInt);
                CASE(long, Long);
                CASE(unsigned long, UnsignedLong);
                CASE(long long, LongLong);
                CASE(unsigned long long, UnsignedLongLong);
                CASE(float, Float);
                CASE(double, Double);

Followed by macro cleanup:

                #undef CASE

This code falls back to creating a generic NSValue with the contents of ptr if there's no match. Because the data is already laid out in memory, it's trivial to have a fallback here, rather than just throwing an exception like the getter code above does:

                return [NSValue valueWithBytes: ptr objCType: type];
            }
        }

Finally, if no getter or instance variable was found, the method throws an exception. The dummy return statement at the end is just to ensure that the compiler doesn't complain about not returning a value:

        [NSException raise: NSInternalInconsistencyException format: @"Class %@ is not key-value compliant for key %@", [isa description], key];
        return nil;
    }

That takes care of valueForKey:.

setValue:forKey:
The setValue:forKey: method works similarly, but there are some differences due to the fact that it has to set values rather than retrieve them.

The first thing it does is construct the name of the setter method to search for. valueForKey: can simply translate the key directly to a selector, but this method needs to do a bit of work. The setter method is generated by capitalizing the first letter of the key, then adding "set" to the beginning, and a colon at the end:

    - (void)setValue: (id)value forKey: (NSString *)key
    {
        NSString *setterName = [NSString stringWithFormat: @"set%@:", [key capitalizedString]];

It then turns that into a selector and checks to see if the object responds:

        SEL setterSEL = NSSelectorFromString(setterName);
        if([self respondsToSelector: setterSEL])
        {

If it does, it fetches the method's argument type and IMP much like the getter code above:

            NSMethodSignature *sig = [self methodSignatureForSelector: setterSEL];
            char type = [sig getArgumentTypeAtIndex: 2][0];
            IMP imp = [self methodForSelector: setterSEL];

If the type is an object or class, it simply calls the setter, passing value, and returns:

            if(type == @encode(id)[0] || type == @encode(Class)[0])
            {
                ((void (*)(id, SEL, id))imp)(self, setterSEL, value);
                return;
            }

Otherwise, it's once again time for a CASE macro. This one calls the IMP, passing [value typeValue] as the parameter, when a match is found:

            else
            {
                #define CASE(ctype, selectorpart) \
                    if(type == @encode(ctype)[0]) { \
                        ((void (*)(id, SEL, ctype))imp)(self, setterSEL, [value selectorpart ## Value]); \
                        return; \
                    }

Here is the big list of cases:

                CASE(char, char);
                CASE(unsigned char, unsignedChar);
                CASE(short, short);
                CASE(unsigned short, unsignedShort);
                CASE(int, int);
                CASE(unsigned int, unsignedInt);
                CASE(long, long);
                CASE(unsigned long, unsignedLong);
                CASE(long long, longLong);
                CASE(unsigned long long, unsignedLongLong);
                CASE(float, float);
                CASE(double, double);

Followed by macro cleanup:

                #undef CASE

Last, if the type is unknown, it throws an exception:

                [NSException raise: NSInternalInconsistencyException format: @"Class %@ key %@ set from incompatible object %@", [isa description], key, value];
            }
        }

If no setter method is found, then it searches for instance variables. No string manipulation is needed, since the instance variable's name doesn't change the way the setter's name does. This code does the same check for instance variables with a leading underscore:

        Ivar ivar = class_getInstanceVariable(isa, [key UTF8String]);
        if(!ivar)
            ivar = class_getInstanceVariable(isa, [[@"_" stringByAppendingString: key] UTF8String]);

If the instance variable exists, it creates a pointer to it and gets its type just like valueForKey: does:

        if(ivar)
        {
            ptrdiff_t offset = ivar_getOffset(ivar);
            char *ptr = (char *)self;
            ptr += offset;

            const char *type = ivar_getTypeEncoding(ivar);

If the variable is an object or class pointer, the code can set it directly. Well, nearly directly. There's a minor retain release dance to be done in order to ensure that memory management is correct:

            if(type[0] == @encode(id)[0] || type[0] == @encode(Class)[0])
            {
                value = [value retain];
                [*(id *)ptr release];
                *(id *)ptr = value;
                return;
            }

Otherwise, value is boxed, and the primitive value needs to be extracted. If value is an NSValue with the exact same type as the instance variable, the getValue: method can be used to simply copy the value over directly:

            else if(strcmp([value objCType], type) == 0)
            {
                [value getValue: ptr];
                return;
            }

If that doesn't work, it's time to fall back to the last long list of cases. This version of the CASE macro sets the value at ptr, appropriately cast, to [value typeValue]:

            else
            {
                #define CASE(ctype, selectorpart) \
                    if(strcmp(type, @encode(ctype)) == 0) { \
                        *(ctype *)ptr = [value selectorpart ## Value]; \
                        return; \
                    }

The traditional exhaustive enumeration of primitive types follows:

                CASE(char, char);
                CASE(unsigned char, unsignedChar);
                CASE(short, short);
                CASE(unsigned short, unsignedShort);
                CASE(int, int);
                CASE(unsigned int, unsignedInt);
                CASE(long, long);
                CASE(unsigned long, unsignedLong);
                CASE(long long, longLong);
                CASE(unsigned long long, unsignedLongLong);
                CASE(float, float);
                CASE(double, double);

Macro cleanup:

                #undef CASE

Finally, if none of the cases were hit, throw an exception:

                [NSException raise: NSInternalInconsistencyException format: @"Class %@ key %@ set from incompatible object %@", [isa description], key, value];
            }
        }

If neither setter method nor instance variable was found, throw an exception to complain:

        [NSException raise: NSInternalInconsistencyException format: @"Class %@ is not key-value compliant for key %@", [isa description], key];
    }

Key Paths
To round out the implementation of KVC, I'll implement valueForKeyPath: and setValue:forKeyPath: as well.

The first thing that valueForKeyPath: does is look for a . in the key path. If it doesn't exist, then it's treated as a plain key and passed to valueForKey:

    - (id)valueForKeyPath: (NSString *)keyPath
    {
        NSRange range = [keyPath rangeOfString: @"."];
        if(range.location == NSNotFound)
            return [self valueForKey: keyPath];

Otherwise, the key is split into two pieces. The piece up to the . is the local key, and the following piece is the remainder of the key path:

        NSString *key = [keyPath substringToIndex: range.location];
        NSString *rest = [keyPath substringFromIndex: NSMaxRange(range)];

The key is passed to valueForKey:

        id next = [self valueForKey: key];

Then valueForKeyPath: is sent recursively to the next object:

        return [next valueForKeyPath: rest];
    }

Its implementation will decompose rest further until every . is consumed. The result is a chain of valueForKey: calls, returning the result of the very last call.

setValue:forKeyPath: works similarly. If there's no . in the key path, call setValue:forKey: and return:

    - (void)setValue: (id)value forKeyPath: (NSString *)keyPath
    {
        NSRange range = [keyPath rangeOfString: @"."];
        if(range.location == NSNotFound)
        {
            [self setValue: value forKey: keyPath];
            return;
        }

Otherwise, extract the key and remainder:

        NSString *key = [keyPath substringToIndex: range.location];
        NSString *rest = [keyPath substringFromIndex: NSMaxRange(range)];

Grab the next object using valueForKey:

        id next = [self valueForKey: key];

Then recursively send setValue:forKeyPath: to next, passing rest as the key path:

        [next setValue: value forKeyPath: rest];
    }

The result is a chain of valueForKey: calls, culminating in a call to setValue:forKey: on the last object in the chain.

Conclusion
You can now see how key-value coding works on the inside. There isn't anything particularly complicated. It's largely just a long list of different things to try. Cocoa's implementation is a bit smarter, and can leverage things like NSInvocation for more comprehensive coverage, but that's the basic idea. A large part of NSInvocation is simply baked-in knowledge of all the different cases that need to be handled as well.

That's it for today. May you code your keys and values in peace. Until next time, since Friday Q&A is driven by reader suggestions, please send in your ideas for topics!

Friday Q&A 2013-01-25: Let's Build NSObject

Mike Ash — Fri, 25 Jan 2013 15:32:00 GMT

Friday Q&A 2013-01-25: Let's Build NSObject

The NSObject class lies at the root of (almost) all classes we build and use as part of Cocoa programming. What does it actually do, though, and how does it do it? Today, I'm going to rebuild NSObject from scratch, as suggested by friend of the blog and occasional guest author Gwynne Raskind.

Components of a Root Class
What exactly does a root class do? In terms of Objective-C itself, there is precisely one requirement: the root class's first instance variable must be isa, which is a pointer to the object's class. The isa is used to figure out what class an object is when dispatching messages. That's all there has to be, from a strict language standpoint.

A root class that only provides that wouldn't be very useful, of course. NSObject provides a lot more. The functionality it provides can be broken down into three categories:

Memory management: standard memory management methods like retain and release are implemented in NSObject. The alloc method is also implemented there.
Introspection: NSObject provides a bunch of methods that are essentially wrappers around Objective-C runtime functionality, such as class, respondsToSelector:, and isKindOfClass:.
Default implementations of miscellaneous methods: there are a bunch of methods that we count on every object implementing, such as isEqual: and description. In order to ensure that every object has an implementation, NSObject provides a default implementation that every subclass gets if it doesn't bring its own.

Code
I'll be reimplementing NSObject functionality as MAObject. I've posted the full code for this article on GitHub:

https://github.com/mikeash/MAObject

Note that this code is built without ARC. Although ARC is great and should be used whenever possible, it really gets in the way when implementing a root class, because a root class needs to implement memory management and ARC prefers that you leave memory management up to the compiler.

Instance Variables
MAObject has two instance variables. The first is the isa pointer. The second is the object's reference count:

    @implementation MAObject {
        Class isa;
        volatile int32_t retainCount;
    }

The reference count will be managed using functions from OSAtomic.h to ensure thread safety, which is why it has a somewhat unusual definition rather than just using NSUInteger or similar.

NSObject actually holds reference counts externally. There's a global table which maps an object's address to its reference count. This saves memory, because the table represents the common reference count of 1 by not having an entry in the table at all. However, this technique is complex and a bit slow, so I opted not to follow it for my own version.

Memory Management
The first thing that MAObject needs to be able to do is to create instances. This is done by implementing the +alloc method. (I'm skipping the deprecated and rarely used +allocWithZone:, which these days does the same thing and ignores its parameter anyway.)

Subclasses rarely override +alloc, and rely on the root class to allocate memory for them. That means that MAObject needs to be able to allocate instances not only of MAObject, but of any subclass. This is done by taking advantage of the fact that the value of self in a class method is the class the message was actually sent to. If code does [SomeSubclass alloc], then self holds a pointer to SomeSubclass. That class can then be used to query the runtime to figure out how much memory to allocate, and to set the isa pointer correctly. The retain count is also initialized to 1, as suits a newly allocated object:

    + (id)alloc
    {
        MAObject *obj = calloc(1, class_getInstanceSize(self));
        obj->isa = self;
        obj->retainCount = 1;
        return obj;
    }

The retain method simply uses OSAtomicIncrement32 to bump up the retain count, and returns self:

    - (id)retain
    {
        OSAtomicIncrement32(&retainCount);
        return self;
    }

The release method does a bit more. It first decrements the retain count. If the retain count was decremented to 0, then the object needs to be destroyed, so the code calls dealloc:

    - (oneway void)release
    {
        uint32_t newCount = OSAtomicDecrement32(&retainCount);
        if(newCount == 0)
            [self dealloc];
    }

The implementation of autorelease calls NSAutoreleasePool to add self to the current autorelease pool. Autorelease pools are part of the runtime these days, so this is a somewhat indirect route, but the autorelease APIs in the runtime are private, so this is the best we can do for now:

    - (id)autorelease
    {
        [NSAutoreleasePool addObject: self];
        return self;
    }

The retainCount method simply returns the value held in the ivar:

    - (NSUInteger)retainCount
    {
        return retainCount;
    }

Finally, there's the dealloc method. In normal classes, dealloc needs to clean up any instance variables and then call super. The root class has to actually dispose of the memory occupied by the object itself. In this case, it's just a simple call to free:

    - (void)dealloc
    {
        free(self);
    }

There are a couple of helper methods as well. NSObject provides a do-nothing init method for consistency, so that subclasses can always call [super init]:

    - (id)init
    {
        return self;
    }

There's also a new method, which is just a wrapper around alloc and init:

    + (id)new
    {
        return [[self alloc] init];
    }

There's also an empty finalize method. NSObject implements this as part of its garbage collection support. MAObject doesn't support garbage collection in the first place, but I included this just because NSObject has it:

    - (void)finalize
    {
    }

Introspection
Many of the introspection methods are just wrappers around runtime functions. Since that's not too interesting, I'll give a brief discussion of what the runtime function is doing behind the scenes as well.

The simplest introspection method is class, which just returns the value of isa:

    - (Class)class
    {
        return isa;
    }

Technically, this method will fail on tagged pointers. A proper implementation should call object_getClass, which behaves correctly for tagged pointers, and extracts the isa from a normal pointer.

The superclass instance method is equivalent to just invoking the superclass class method on the object's class, so that's exactly what the method does:

    - (Class)superclass
    {
        return [[self class] superclass];
    }

There are also class methods for these. The +class method just returns self, which is the class object. This is a little weird, but it's how NSObject does things. [obj class] returns the object's class, but [MyClass class] just returns a pointer to MyClass itself. It's not consistent, as MyClass also has a class, which is the MyClass metaclass, but it's how things are done:

    + (Class)class
    {
        return self;
    }

The +superclass method does what it says. This is implemented by calling class_getSuperclass, which just grovels around inside the class structure maintained by the runtime and pulls out the pointer to the superclass.

    + (Class)superclass
    {
        return class_getSuperclass(self);
    }

There are also methods for querying whether an object's class matches a particular class. The simple one is isMemberOfClass:, which does a strict check, ignoring subclasses. Its implementation is simple:

    - (BOOL)isMemberOfClass: (Class)aClass
    {
        return isa == aClass;
    }

The isKindOfClass: method checks subclasses too, so that [subclassInstance isKindOfClass: [Superclass class]] returns YES. The output of this method is essentially the same as that of the class method isSubclassOfClass:, so it just calls through:

    - (BOOL)isKindOfClass: (Class)aClass
    {
        return [isa isSubclassOfClass: aClass];
    }

That method gets a bit more interesting. Starting from self, it walks up the class hierarchy, comparing with the target class at each level. If it finds a match, it returns YES. If it runs off the top of the class hierarchy without ever finding a match, it returns NO:

    + (BOOL)isSubclassOfClass: (Class)aClass
    {
        for(Class candidate = self; candidate != nil; candidate = [candidate superclass])
            if (candidate == aClass)
                return YES;

        return NO;
    }

It's interesting to note that this check is not particularly efficient. If you call this method on a class that's deep in the class hierarchy, it can take a lot of loop iterations before it returns NO. Because of that, isKindOfClass: checks can be quite a lot slower than message sends, and can actually be substantial bottlenecks in certain cases. Just one more reason to avoid them when possible.

The respondsToSelector: method just calls through to the runtime function class_respondsToSelector. That, in turn, looks up the selector in the class's method table to see if it has an entry:

    - (BOOL)respondsToSelector: (SEL)aSelector
    {
        return class_respondsToSelector(isa, aSelector);
    }

There's a class method, instancesRespondToSelector:, which is nearly identical. The only difference is passing self, which is the class in this context, rather than isa, which would be the metaclass here:

    + (BOOL)instancesRespondToSelector: (SEL)aSelector
    {
        return class_respondsToSelector(self, aSelector);
    }

There are also two conformsToProtocol: methods, one for instances and one for classes. These also just wrap a runtime function, which in this case just consults a table of every protocol that the class conforms to in order to see if the given protocol is present:

    - (BOOL)conformsToProtocol: (Protocol *)aProtocol
    {
        return class_conformsToProtocol(isa, aProtocol);
    }

    + (BOOL)conformsToProtocol: (Protocol *)protocol
    {
        return class_conformsToProtocol(self, protocol);
    }

Next is methodForSelector:, and its classy cousin instanceMethodForSelector:. These both call through to class_getMethodImplementation, which looks up the selector in the class's method table and returns the corresponding IMP:

    - (IMP)methodForSelector: (SEL)aSelector
    {
        return class_getMethodImplementation(isa, aSelector);
    }

    + (IMP)instanceMethodForSelector: (SEL)aSelector
    {
        return class_getMethodImplementation(self, aSelector);
    }

An interesting aspect of these methods is that class_getMethodImplementation always returns an IMP, even for unknown selectors. When the class doesn't actually implement a method, it returns a special forwarding IMP which wraps up the message arguments starts down the path to invoking forwardInvocation:.

The methodSignatureForSelector: method just wraps the equivalent class method:

    - (NSMethodSignature *)methodSignatureForSelector: (SEL)aSelector
    {
        return [isa instanceMethodSignatureForSelector: aSelector];
    }

The class method in turn wraps some runtime calls. It first fetches the Method for the given selector. If it can't be found, then the class doesn't implement that method, and this code returns nil. Otherwise, it extracts the C string representing the method's types, and wraps the in an NSMethodSignature object:

    + (NSMethodSignature *)instanceMethodSignatureForSelector: (SEL)aSelector
    {
        Method method = class_getInstanceMethod(self, aSelector);
        if(!method)
            return nil;

        const char *types = method_getTypeEncoding(method);
        return [NSMethodSignature signatureWithObjCTypes: types];
    }

Finally, there's performSelector:, and the two withObject: variants that take arguments. These aren't strictly introspection, but they fall in the same general category of wrapping lower-level runtime functionality. They simply retrieve the IMP for the given selector, cast it to the appropriate function pointer type, and call it:

    - (id)performSelector: (SEL)aSelector
    {
        IMP imp = [self methodForSelector: aSelector];
        return ((id (*)(id, SEL))imp)(self, aSelector);
    }

    - (id)performSelector: (SEL)aSelector withObject: (id)object
    {
        IMP imp = [self methodForSelector: aSelector];
        return ((id (*)(id, SEL, id))imp)(self, aSelector, object);
    }

    - (id)performSelector: (SEL)aSelector withObject: (id)object1 withObject: (id)object2
    {
        IMP imp = [self methodForSelector: aSelector];
        return ((id (*)(id, SEL, id, id))imp)(self, aSelector, object1, object2);
    }

Default Implementations
MAObject provides default implementations of a bunch of methods. We'll start off with default implementations of isEqual: and hash, which just use the object's pointer for identity purposes:

    - (BOOL)isEqual: (id)object
    {
        return self == object;
    }

    - (NSUInteger)hash
    {
        return (NSUInteger)self;
    }

Any subclasses with a more expansive notion of equality will have to override these methods, but any subclass where an object is only ever equal to itself can just use these implementations.

The description method is another handy one to have a default implementation. This implementation just generates a string of the form <MAObject: 0xdeadbeef>, containing the object's class and pointer value.

    - (NSString *)description
    {
        return [NSString stringWithFormat: @"<%@: %p>", [self class], self];
    }

The standard for classes is to just return the class name from their own description, so there's a class method as well that fetches that name from the runtime and returns it:

    + (NSString *)description
    {
        return [NSString stringWithUTF8String: class_getName(self)];
    }

doesNotRecognizeSelector: is a lesser-known utility method. It throws an exception to make it look like the object doesn't actually respond to the given selector. This is useful for things like creating override points where subclasses have to implement a particular method:

    - (void)subclassesMustOverride
    {
        // pretend we don't actually implement this here
        [self doesNotRecognizeSelector: _cmd];
    }

The code is fairly simple. The only really tricky bit is formatting the method name. We want to display something like -[Class method], but class methods need a + at the front, as in +[Class classMethod]. To figure out which context it's in, the code checks to see whether isa is a metaclass. If it is, then self is a class, and the + variant should be used. Otherwise, self is an instance, and the - variant is used. The rest of the code just raises the appropriate NSException:

    - (void)doesNotRecognizeSelector: (SEL)aSelector
    {
        char *methodTypeString = class_isMetaClass(isa) ? "+" : "-";
        [NSException raise: NSInvalidArgumentException format: @"%s[%@ %@]: unrecognized selector sent to instance %p", methodTypeString, [[self class] description], NSStringFromSelector(aSelector), self];
    }

Finally, there are a bunch of little methods that either provide obvious answers to obvious questions (e.g. the self method), exist to let subclasses always safely call super (e.g. the empty +initialize method), or exist as override points (e.g. the copy implementation that throws an exception). None of these are particularly interesting, but I include them for completeness:

    - (id)self
    {
        return self;
    }

    - (BOOL)isProxy
    {
        return NO;
    }

    + (void)load
    {
    }

    + (void)initialize
    {
    }

    - (id)copy
    {
        [self doesNotRecognizeSelector: _cmd];
        return nil;
    }

    - (id)mutableCopy
    {
        [self doesNotRecognizeSelector: _cmd];
        return nil;
    }

    - (id)forwardingTargetForSelector: (SEL)aSelector
    {
        return nil;
    }

    - (void)forwardInvocation: (NSInvocation *)anInvocation
    {
        [self doesNotRecognizeSelector: [anInvocation selector]];
    }

    + (BOOL)resolveClassMethod:(SEL)sel
    {
        return NO;
    }

    + (BOOL)resolveInstanceMethod:(SEL)sel
    {
        return NO;
    }

Conclusion
NSObject is a big bundle of different functionality, but nothing too strange. Its main function is to handle memory allocation and management so that you can actually create objects. It also provides a bunch of handy override points for methods that every object is expected to support, and wraps a bunch of runtime functions in a nicer API.

I've skipped over a big piece of functionality provided by NSObject: key-value coding. This is complex enough that it deserves its own article, so I will come back to that another time.

That's it for today. Friday Q&A is driven by reader ideas, in case you somehow didn't already know, so please send in your topic suggestions. Until next time, don't code anything I wouldn't code.

Friday Q&A 2013-01-11: Mach Exception Handlers

Landon Fuller — Fri, 11 Jan 2013 14:44:00 GMT

Friday Q&A 2013-01-11: Mach Exception Handlers

This is my first guest Friday Q&A article, dear readers, and I hope it will withstand your scrutiny. Today's topic is on Mach exception handlers, something I've recently spent some time exploring on Mac OS X and iOS for the purpose of crash reporting. While there is surprisingly little documentation available about Mach exception handlers, and they're considered by some to be a mystical source of mystery and power, the fact is that they're actually pretty simple to understand at a high level - something I hope to elucidate here. Unfortunately, they're also partially private API on iOS, despite being used in a number of new crash reporting solutions - something I'll touch on in the conclusion.

Signals vs. Exceptions
On most UNIX systems, the only mechanism available for handling crashes (such as dereferencing NULL, or writing to an unwritable page) are the standard UNIX signal handlers. When a fatal machine exception is generated, it is caught by the kernel, which then executes a user-space trampoline within the failing process, executing any function previously registered by that process via sigaction(3) or signal(3).

On OS X, however, a much more versatile API exists: Mach exceptions. Dating back to Avie Tevanian's work on the Mach OS (yes, that Avie Tevanian), Mach exceptions build on Mach IPC/RPC to provide an alternative to the UNIX signal handler API. The original design of the Mach exception handling facility was first described, as far as I'm aware, in a 1988 paper authored by Avie Tevanian, among others. It remains fairly accurate to this day, and I'd recommend reading it for more details (after finishing this post, of course).

Mach exceptions differ from UNIX signals in three significant ways:

Exception information is delivered as a Mach message via a Mach IPC port, rather than by the kernel calling into a userspace trampoline.
Exception handlers may be registered by any process that has the appropriate mach port rights for the target process.
Exception handlers may be registered for a specific thread, a specific task (process), or for the entire host. The kernel will search for handlers in that order.

These differences introduce a number of properties that can be useful when implementing debuggers and crash reporters, and are what make the Mach API interesting as an alternative to BSD signals.

Exceptions are Messages
The Mach exception API is based on Mach RPC (which is, in itself, based on Mach IPC). There's a lot of confusion around Mach IPC, but at a high-level, it's not too dissimilar to UNIX sockets or other well-known IPC mechanisms that allow one to read/write messages between processes. Mach IPC communication occurs over mach ports, rather than via socket or other traditional UNIX mechanism; mach ports have unique names, and can be shared with other processes. They can be used to send and receive messages containing arbitrary data. There's a bit more complexity involved in their actual use, but conceptually, that's about all you need to know.

To write a Mach exception handler using raw Mach IPC, you would need to wait for a new exception message by calling mach_msg() on a Mach port previously registered as an exception handler (how to do this is covered below). The call to mach_msg() will block until an exception message is received, or the thread is interrupted. Once a message is received, you are free to introspect it for the state of the thread that generated the exception. You can even correct the cause of the crash and restart the failing thread, if you feel like hacking register state at runtime.

Since exceptions are provided as messages, rather than by calling a local function, exception messages can be forwarded to the previously registered Mach exception handler, even if that existing handler is completely out-of-process. This means that you can insert an exception handler without disturbing an existing one, whether it's the debugger or Apple's crash reporter. To forward the message to an existing handler, you also use mach_msg() to send the original message to a previously registered handler's mach port, using the MACH_SEND_MSG flag.

However, if you wish to respond the Mach RPC request yourself, rather than forwarding it, you would need to reply to the message, informing the sender whether or not you handled the exception. Mach considers an exception handled if the crashing thread's state has been corrected such that its execution can be resumed. In this case, the kernel does not attempt to find any other exception handler, and considers the matter settled. However, if you reply to the RPC request informing the sender (usually the kernel) that the exception has not been handled, the sender will then try to find the next applicable Mach exception handler. Remember that the kernel attempts to send exceptions to thread-specific, task-specific, and host-global exception handlers, in that order.

The fact that a reply is expected from the exception request can be used for interesting purposes. For example, if a debugger has its exception handler called when a breakpoint is hit, it can simply wait to reply to the Mach exception message until (and only if) you request that the debugger continue execution.

Mach RPC, not IPC
While above I described how one might implement mach exception handling with raw Mach IPC, the fact is that this is not how the interfaces are defined in Mach. Instead, Mach RPC uses an interface description language (called matchmaker in the original 1989 paper), to describe the format of Mach RPC requests (and their replies), and automatically generate code to handle received messages and generate a reply.

On OS X, the Mach RPC interface descriptions for exception handling - mach_exc.defs and exc.defs - are available via /usr/include/mach. If you include these files in your Xcode project, it will automatically run the mig(1) tool (Mach Interface Generator), generating headers and C source files necessary to receive and handle Mach exception messages. The exc.defs file provides an API for working with 32-bit exceptions, whereas the mach_exc.defs file provides an API for working with 64-bit exceptions. Unfortunately, the Mach RPC defs are not provided on iOS, and only a subset of the necessary generated headers are provided. As a result, it's not possible to implement a fully correct Mach exception handler on iOS without relying on undocumented functionality.

The code generated by MIG handles two things:

Interpreting incoming RPC messages and calling out to an existing handler function with the decoded data.
Initialize a response to the RPC messages using the return values from the handler function.

The generated code does not handle registering a Mach exception handler, receiving the Mach message, or actually sending the reply. That is the implementor's responsibility. In addition, there are multiple supported exception "behaviors" that provide different sets of information about an exception; it is the implementor's responsibility to provide callback functions for all of them.

This is best illustrated in the following 64-bit safe code, intended to work with RPC code generated by mach_exc.defs (I've left out error handling for simplicity):

    // Handle EXCEPTION_DEFAULT behavior
    kern_return_t catch_mach_exception_raise (mach_port_t exception_port,
                                               mach_port_t thread,
                                               mach_port_t task, 
                                               exception_type_t exception,
                                               mach_exception_data_t code,
                                               mach_msg_type_number_t codeCnt)
    {
        // Do smart stuff here.
        fprintf(stderr, "My exception handler was called by exception_raise()\n");

        // Inform the kernel that we haven't handled the exception, and the
        // next handler should be called.
        return KERN_FAILURE;
    }

    extern boolean_t mach_exc_server (mach_msg_header_t *msg, mach_msg_header_t *reply);
    static void exception_server (mach_port_t exceptionPort) {
        mach_msg_return_t rt;
        mach_msg_header_t *msg;
        mach_msg_header_t *reply;

        msg = malloc(sizeof(union __RequestUnion__mach_exc_subsystem));
        reply = malloc(sizeof(union __ReplyUnion__mach_exc_subsystem));

        while (1) {
             rt = mach_msg(msg, MACH_RCV_MSG, 0, sizeof(union __RequestUnion__mach_exc_subsystem), exceptionPort, 0, MACH_PORT_NULL);
             assert(rt == MACH_MSG_SUCCESS);

             // Call out to the mach_exc_server generated by mig and mach_exc.defs.
             // This will in turn invoke one of:
             // mach_catch_exception_raise()
             // mach_catch_exception_raise_state()
             // mach_catch_exception_raise_state_identity()
             // .. depending on the behavior specified when registering the Mach exception port.
             mach_exc_server(msg, reply);

             // Send the now-initialized reply
             rt = mach_msg(reply, MACH_SEND_MSG, reply->msgh_size, 0, MACH_PORT_NULL, 0, MACH_PORT_NULL);
             assert(rt == MACH_MSG_SUCCESS);
        }
    }

You'll note from the example code that our exception handler is called a server. In Mach RPC parlance, the kernel would be the client: it issues RPC requests to our exception server, and waits for our reply.

Exception Behaviors
As described above, exception messages come in multiple formats, containing varying types of data. It's the implementor's responsibility to register for the correct behavior; the mig-generated RPC code will interpret the messages and hand it off to a user-defined function for the specific type. There are three basic behaviors defined by the Mach Exception API:

EXCEPTION_DEFAULT: Exception messages will contain a reference thread that triggered it. Handled by catch_exception_raise().
EXCEPTION_STATE: Exception messages will contain the register state of the triggering thread, but not a reference to the thread itself. Handled by catch_exception_raise_state().
EXCEPTION_STATE_IDENTITY: Exception messages will contain the register state of the triggering thread, as well as a reference to the triggering thread. Handled by catch_exception_raise_state_identity().

In addition to the above behaviors, an additional variant was added in later OS X releases to support 64-bit safety. The MACH_EXCEPTION_CODES flag may be set by AND'ing it with any of the listed behaviors, in which case 64-bit safe exception messages will be provided. This flag is used by LLDB/GDB even when targeting 32-bit processes. When using the MACH_EXCEPTION_CODES flag, one must also use the RPC functions generated by mach_exc.defs; these use the mach_ prefix for all functions and types.

Generally speaking, EXCEPTION_DEFAULT or EXCEPTION_STATE_IDENTITY are sufficient for most purposes. Since EXCEPTION_DEFAULT behavior provides a reference to the triggering thread, you can also fetch the thread state that would normally be provided via EXCEPTION_STATE_IDENTITY via the Mach thread_state() API.

When registering your exception handler, you are responsible for requesting the MACH_EXCEPTION_CODES behavior that matches the RPC implementation (exc.defs or mach_exc.defs) that you intend to use.

Putting it Together
It's time to get down to brass tacks: actually registering an mach port to receive exception messages. As noted above, handlers can be registered for threads, tasks, and the host, and there are different sets of identical APIs for each:

(thread|task|host)_get_exception_ports: Returns the currently registered set of exception ports.
(thread|task|host)_set_exception_ports: Sets the exception port that will be used for all future exceptions.
(thread|task|host)_swap_exception_ports: Atomically set a new exception port, and return the current ports. This can be used to avoid race conditions that could otherwise occur if multiple handlers are registered concurrently.

To register your handler, you'll need to first allocate a mach port to receive the messages, insert a "send right" to permit sending responses, and then call one of the exception port set() or swap() functions to register it as a receiver of exception messages.

For example (error handling again elided for conciseness):

    mach_port_t server_port;
    kern_return_t kr = mach_port_allocate(mach_task_self(), MACH_PORT_RIGHT_RECEIVE, &server_port);
    assert(kr == KERN_SUCCESS);

    kr = mach_port_insert_right(mach_task_self(), &server_port, &server_port, MACH_MSG_TYPE_MAKE_SEND);
    assert(kr == KERN_SUCCESS);

    kr = task_set_exception_ports(task, EXC_MASK_BAD_ACCESS, server_port, EXCEPTION_DEFAULT|MACH_EXCEPTION_CODES, THREAD_STATE_NONE);

If you wish to preserve the previous exception handlers, task_swap_exception_ports() should be used in place of task_set_exception_ports().

Conclusion
Mach exception handlers are a very useful tool, and using them requires a fair bit of moving pieces, but hopefully they don't seem dauntingly complex. At the end of the day, mach exceptions are just a simple exception message, coupled with a reply, sent over Mach ports.

There are some signficiant advantages of the Mach API over signal handlers, including the ability to forward exceptions out-of-process, and handle all exceptions on a completely different stack - something that can be useful when handling an exception triggered by a stack overflow on the target thread.

If you plan on implementing your own mach exception handler, there are certainly more details worth further investigation:

When forwarding mach exceptions, you need to send an exception message that matches the previous registered handler's exception flavor. This may mean populating a new Mach exception message with additional thread state.
It's not strictly necessary to use the MIG-generated exc_server() or mach_exc_server() functions for interpreting Mach messages (though it is probably a good idea). Since mig(1) generates structures that may be used to directly interpret the Mach exception messages, you can do so directly.
If you forward exception messages for exceptions that occur in your own process, you need to be sure that the target for the reply is not also your own process. Single-stepping debuggers will only resume the thread they wish to step; that means that they won't resume your exception handler's thread, you'll never receive the reply, and the interrupted thread will never resume.

Lastly, I should highlight that the headers and mach interfaces required to implement a correct mach exception handler on iOS are not available (though they are available and public on Mac OS X). I filed a radar requesting their addition (rdar://12939497), as well as an Apple DTS support incident to clarify the situation. The radar is still open, but DTS provided the following guidance:

Our engineers have reviewed your request and have determined that this would be best handled as a bug report, which you have already filed. There is no documented way of accomplishing this, nor is there a workaround possible.

In the meantime, as far as I can determine through my own work, and as per DTS's feedback, it's not possible to implement Mach exception handling on iOS using only public API. Hopefully this will be resolved in a future release of iOS, such that we can safely adopt Mach exceptions.

Thus concludes my first contribution to Friday Q&A. If you have any questions, feel free to drop me an e-mail. If I got anything terrible wrong, feel free to roast me in the comments.

Friday Q&A 2012-12-28: What Happens When You Load a Byte of Memory

Mike Ash — Fri, 28 Dec 2012 14:45:00 GMT

Friday Q&A 2012-12-28: What Happens When You Load a Byte of Memory

The hardware and software that our apps run on is almost frighteningly complicated, and there's no better place to see that than in the contortions that the system goes through when we load data from memory. What exactly happens when we load a byte of memory? Reader and friend of the blog Guy English suggested I dedicate an article to answering that question.

Code
Let's start with the code that loads the byte of memory. In C, it would look something like this:

    char *addr = ...;
    char value = *addr;

On x86-64, this compiles to something like:

    movsbl (%rdi),%eax

This instructs the CPU to load the byte located at the address stored in %rdi into the %eax register. On ARM, the compiler produces:

    ldrsb.w r0, [r0]

Although the instruction name is different, the effect is basically the same. It loads the byte located at the address stored in r0, and puts the value into r0. (The compiler is reusing r0 here, since the address isn't needed anymore.)

Now that the CPU has its instruction, the software is done. Well, maybe.

Instruction Decoding and Execution
I don't want to go too in depth with how the CPU actually executes code in general. In short, the CPU loads the above instruction from memory and decodes it to figure out the opcode and operands. Once it sees that it's a load instruction, it issues the memory load at the appropriate address.

Virtual Memory
On most hardware you're likely to program for today, and on any Apple platform from the past couple of decades, the system uses virtual memory. In short, virtual memory disconnects the memory addresses seen by your program from the physical memory addresses of the actual RAM in your computer. In other words, when your program accesses address 42, that might actually access the physical RAM address 977305.

This mapping is done by page. Each page is a 4kB chunk of memory. The overhead of tracking virtual address mappings for every byte in memory would be far too great, so pages are mapped instead. They're small enough to provide decent granularity, but large enough to not incur too much overhead in maintaining the mapping.

Modern virtual memory systems also have the ability to set permissions on a page. A page may be readable, writeable, or executable, or some combination thereof. If the program tries to do something with a page that it isn't allowed, or tries to access a page that has no mapping at all, the program is suspended and a fault is raised with the operating system. The OS can then take further action, such as killing the program and generating a crash report, which is what happens when you experience the common EXC_BAD_ACCESS error.

The hardware that handles this work is called the Memory Management Unit, or MMU. The MMU intercepts all memory accesses and remaps the address according to the current page mappings.

The first thing that happens when the CPU loads a byte of memory is to hand the address to the MMU for translation. (This is not always true. On some CPUs, there is a layer of cache that comes before the MMU. However, the overall principle remains.)

The first thing the MMU does with the address is slice off the bottom 12 bits, leaving a plain page address. 2¹² equals 4096, so the bottom 12 bits describe the address's location within its page. Once the rest of the address is remapped, the bottom 12 bits can be added on to generate the full physical address.

With the page address in hand, the MMU consults the Translation Lookaside Buffer, or TLB. The TLB is a cache for page mappings. If the page in question has been accessed recently, the TLB will remember the mapping, and quickly return the physical page address, at which point the MMU's work is done.

When the TLB does not contain an entry for the given page, this is called a TLB miss, and the entry must be found by searching the entire page table. The page table is a chunk of memory that describes every page mapping in the current process. Most commonly, the page table is laid out in memory by the OS in a special format that the MMU can understand directly. Following a TLB miss, the MMU searches the page table for the appropriate entry. If it finds one, it loads it into the TLB and performs the remapping.

On some architectures, the page table mapping is left entirely up to the OS. When a TLB miss occurs, the CPU passes control to the OS, which is then responsible for looking up the mapping and filling the TLB with it. This is more flexible but much slower, and isn't found much in modern hardware.

If no entry is found in the page table, that means the given address doesn't exist in RAM at all. The CPU informs the OS, which then decides how to handle the situation. If the OS doesn't think that address is valid, it terminates the program and you get an EXC_BAD_ACCESS. In some cases, the OS does think the address is valid, but just doesn't have the data in RAM. This can happen if the data has been swapped out to disk, is part of a memory mapped file, or is freshly allocated with backing memory being provided on demand. In these cases, the OS loads the appropriate data into RAM, adds an entry to the page table, and then lets the MMU translate the virtual address into a physical address now that the backing data is available.

Cache
With the address in hand, the CPU consults its memory cache. In days of yore, the CPU would talk directly to RAM. However, CPU speeds have increased faster than memory speeds, and that's no longer practical. If a modern CPU had to talk directly to modern RAM for every memory access, our computers would slow to a relative crawl.

The cache is a hardware map from a set of memory addresses to memory contents. Caches are organized into cache lines, which are typically in the region of 32-128 bytes each. Each entry in the cache holds an address and a single cache line corresponding to that address. When loading data from the cache, it checks to see if the requested address exists in the cache, and if so, returns the appropriate data from that address's cache line.

There are typically several levels of cache. Due to hardware design constraints, larger caches are necessarily slower. By having multiple levels, a small, fast cache can be checked first, with slower, larger caches used later to avoid the cost of fetching from RAM. The CPU first checks with the L1 cache, which is the first level. This cache is small, typically around 16-64kB. If it contains the data in question, then the memory load is complete! Since that's boring, we'll assume the caches don't contain the data being loaded here.

Next up is the L2 cache. This is bigger, generally anywhere from 256kB to several megabytes. In some CPUs, the L2 cache is the last level, and these typically have larger L2 caches. Other CPUs have an L3 cache as well, in which case the L2 is usually smaller, and it's supplemented by a large L3 cache, usually several megabytes, with some high performance chips having up to 20MB of L3 cache.

Once all levels of cache have been tried, if none of them contain the necessary data, it's time to try main memory. Because caches work with entire cache lines, the entire cache line is loaded from main memory at once, even though we're only loading a single byte. This greatly increases efficiency in the common case of accessing other nearby memory, since subsequent nearby loads can come from cache, at the cost of wasting time when memory use is scattered.

Memory
It's finally time to start querying RAM. The CPU has been waiting quite a while by this point, and will have to wait a long time more before it gets the data it wants.

The load is handed off to the memory controller, which is the bit of hardware that actually knows how to talk to RAM. On a lot of modern hardware, the memory controller is integrated directly into the CPU, while on some systems it's part of a separate chip called the "northbridge".

The memory controller then starts loading data from RAM. Modern SDRAM transfers 64 bits of data at a time, so several transfers have to be done to fill the entire cache line being requested.

The memory controller places the load address on the address pins of the RAM and waits for the data to be returned. Internally, the RAM uses the values on the address pins to activate a row of memory cells, whose contents are then exposed on the RAM's output pins.

RAM is not instantaneous, and there's an appreciable delay between when the memory controller requests an address and when the data is available, on the order of 10 nanoseconds in current hardware. It takes more time to perform the subsequent loads needed for the cache line, but the loads can be pipelined, so total transfer time is maybe 50% more.

As the memory controller obtains data from RAM, it hands that data back to the caches, which store it in case other data from the same cache line is needed soon. Finally, the requested byte is handed to the CPU, which places the data into the register requested by the instruction. At last, after all of this work, the CPU can get on with running the code that needed that byte of data.

Consequences
There are a lot of practical consequences that result from how all of this stuff works. In particular, memory acccess is slow, relatively speaking. It's amazing that your computer can do all of the above work literally tens of millions of times per second, but it can do other things literally billions of times per second. Everything is relative.

The total time required for all of this, assuming a TLB hit (the fast case for the MMU) is a couple of dozen nanoseconds. On a 2GHz CPU, that could mean something like 50 clock cycles with the potential to execute perhaps 150 instructions in that time. That's a lot. A TLB miss may double or triple this latency number.

Modern CPUs are pipelined and parallelized. This means that they will likely see the need for the memory read ahead of time and initiate the load at that point, softening the blow. Parallel execution means that the CPU will probably be able to continue executing some code after the load instruction while waiting for the load, especially code that doesn't depend on the loaded value. However, this stuff has limits, and finding 150 instructions that can be executed while waiting for RAM is a tall order. You're almost certain to hit a point where program execution has to stop and wait for the memory load to complete.

Incidentally, this is where hyperthreading gains its advantage. Instead of having an entire CPU core just idle while waiting for RAM, hyperthreading lets it switch over to a completely different thread of execution and run code from that instead, so that it can still get useful work done while it waits.

Access patterns are key to performance. Discussions about micro-optimization tend to center on using some instructions rather than others, avoiding divisions, etc. Relatively few talk about memory access patterns. However, it doesn't matter how optimized your individual instructions are if they're operating on memory that's loaded in a way that isn't kind to the memory system. Saving a few cycles here and there is meaningless if you're waiting dozens of cycles for every new piece of data to load. For example, this is why, although it's the more natural way to express it, you should never write loops to access image data like this:

    for(int x = 0; x < width; x++)
        for(int y = 0; y < height; y++)
            // use the pixel at x, y

Images are typically laid out in contiguous rows, and this loop does not take advantage of that fact. It accesses columns, only coming back to the next pixel in the first row after loading the entire first column. This causes cache and TLB misses. This loop will be vastly slower than if you iterate over rows first, then columns:

    for(int y = 0; y < height; y++)
        for(int x = 0; x < width; x++)
            // use the pixel at x, y

In many cases, the top loop with fast code in the loop body will be massively outperformed by the bottom loop with slow code in the loop body, simply because memory access delays can be so punishing.

To make things even worse, profilers, such as Apple's Time Profiler in Instruments, aren't good at showing these delays. They'll tell you what instructions took time, but because of the pipelined, parallel nature of modern CPUs, the instruction that takes the hit of the memory load may not be the actual load instruction. The CPU will hit the load instruction, mark its destination register as not having its data yet, and move on. When the CPU hits an instruction that actually needs that register's value, then it will stop and wait. The clue here is when the first instruction in a sequence of manipulations on the same value takes far longer than the rest, and far longer than it should. For example, if you have code that does load, add, mul, add, and the profiler says that the first add takes the vast majority of the time, this is likely to be a memory delay, not actually a slow add.

Conclusion
Modern computers operate on time scales that are difficult to envision. To a human, the time required for a single CPU cycle and the time required to perform a hard disk seek are both indistingusihably instantaneous, yet they vary by many orders of magnitude. The computer is an incredibly complicated system that requires a huge number of things to happen in order to load a single chunk of data from memory. Knowing what goes on in the hardware when this happens is fascinating and can even help write better code. It's even more incredible once you think that this complicated set of operations happens literally millions of times every second in the computer you're using to read this.

That's it for today. Check back next time for another exploration of the trans-mundane. If you somehow didn't already know, Friday Q&A is driven by reader submissions. By "reader" I mean you, so if you have a topic that you'd like to see covered, please send it in.

Friday Q&A 2012-12-14: Objective-C Pitfalls

Mike Ash — Fri, 14 Dec 2012 14:38:00 GMT

Friday Q&A 2012-12-14: Objective-C Pitfalls

Objective-C is a powerful and extremely useful language, but it's also a bit dangerous. For today's article, my colleague Chris Denter suggested that I talk about pitfalls in Objective-C and Cocoa, inspired by Cay S. Horstmann's article on C++ pitfalls.

Introduction
I'll use the same definition as Horstmann: a pitfall is code that compiles, links, runs, but doesn't do what you might expect it to. He provides this example, which is just as problematic in Objective-C as it is in C++:

    if (-0.5 <= x <= 0.5) return 0;

A naive reading of this code would be that it checks to see whether x is in the range [-0.5, 0.5]. However, that's not the case. Instead, the comparison gets evaluated like this:

    if ((-0.5 <= x) <= 0.5)

In C, the value of a comparison expression is an int, either 0 or 1, a legacy from when C had no built-in boolean type. It is that 0 or 1, not the value of x, that is compared with 0.5. In effect, the second comparison works as an extremely weirdly phrased negation operator, such that the if statement's body will execute if and only if x is less than -0.5.

Nil Comparison
Objective-C is highly unusual in that sending messages to nil does nothing and simply returns 0. In nearly every other language you're likely to encounter, the equivalent is either prohibited by the type system or produces a runtime error. This can be both good and bad. Given the subject of the article, we'll concentrate on the bad.

First, let's look at equality testing:

    [nil isEqual: @"string"]

Messaging nil returns 0, which in this case is equivalent to NO. That happens to be the correct answer here, so we're off to a good start! However, consider this:

    [nil isEqual: nil]

This also returns NO. It doesn't matter that the argument is the exact same value. The argument's value doesn't matter at all, because messages to nil always return 0 no matter what. So going by isEqual:, nil never equals anything, including itself. Mostly right, but not always.

Finally, consider one more permutation with nil:

    [@"string" isEqual: nil]

What does this do? Well, we can't be sure. It may return NO. It may throw an exception. It may simply crash. Passing nil to a method that doesn't explicitly say it's allowed is a bad idea, and isEqual: doesn't say that it accepts nil.

Many Cocoa classes also include a compare: method. This takes another object of the same class and returns either NSOrderedAscending, NSOrderedSame, or NSOrderedDescending, to indicate less than, equal, or greater than.

What happens if we compare with nil?

    [nil compare: nil]

This returns 0, which happens to be equal to NSOrderedSame. Unlike isEqual:, compare: thinks nil equals nil. Handy! However:

    [nil compare: @"string"]

This also returns NSOrderedSame, which is definitely the wrong answer. compare: will consider nil to be equal to anything and everything.

Finally, just like isEqual:, passing nil as the parameter is a bad idea:

    [@"string" compare: nil]

In short, be careful with nil and comparisons. It really just doesn't work right. If there's any chance your code will encounter nil, you must check for and handle it separately before you start doing isEqual: or compare:.

Hashing
You write a little class to contain some data. You have multiple equivalent instances of this class, so you implement isEqual: so that those instances will be treated as equal. Then you start adding your objects to an NSSet and things start behaving strangely. The set claims to hold multiple objects after you just added one. It can't find stuff you just added. It may even crash or corrupt memory.

This can happen if you implement isEqual: but don't implement hash. A lot of Cocoa code requires that if two objects compare as equal, they will also have the same hash. If you only override isEqual:, you violate that requirement. Any time you override isEqual:, always override hash at the same time. For more information, see my article on Implementing Equality and Hashing.

Macros
Imagine you're writing some unit tests. You have a method that's supposed to return an array containing a single object, so you write a test to verify that:

    STAssertEqualObjects([obj method], @[ @"expected" ], @"Didn't get the expected array");

This uses the new literals syntax to keep things short. Nice, right?

Now we have another method that returns two objects, so we write a test for that:

    STAssertEqualObjects([obj methodTwo], @[ @"expected1", @"expected2" ], @"Didn't get the expected array");

Suddenly, the code fails to compile and produces completely bizarre errors. What's going on?

What's going on is that STAssertEqualObjects is a macro. Macros are expanded by the preprocessor, and the preprocessor is an ancient and fairly dumb program that doesn't know anything about modern Objective-C syntax, or for that matter modern C syntax. The preprocessor splits macro arguments on commas. It's smart enough to know that parentheses can nest, so this is seen as three arguments:

    Macro(a, (b, c), d)

Where the first argument is a, the second is (b, c), and the third is d. However, the preprocessor has no idea that it should do the same thing for [] and {}. With the above macro, the preprocessor sees four arguments:

[obj methodTwo]
@[ @"expected1"
@"expected2 ]
@"Didn't get the expected array"

This results in completely mangled code that not only doesn't compile, but confuses the compiler beyond the ability to provide understandable diagnostics. The solution is easy, once you know what the problem is. Just parenthesize the literal so the preprocessor treats it as one argument:

    STAssertEqualObjects([obj methodTwo], (@[ @"expected1", @"expected2" ]), @"Didn't get the expected array");

Unit tests are where I've run into this most frequently, but it can pop up any time there's a macro. Objective-C literals will fall victim, as will C compound literals. Blocks can also be problematic if you use the comma operator within them, which is rare but legal. You can see that Apple thought about this problem with their Block_copy and Block_release macros in /usr/include/Block.h:

    #define Block_copy(...) ((__typeof(__VA_ARGS__))_Block_copy((const void *)(__VA_ARGS__)))
    #define Block_release(...) _Block_release((const void *)(__VA_ARGS__))

These macros conceptually take a single argument, but they're declared to take variable arguments to avoid this problem. By taking ... and using __VA_ARGS__ to refer to "the argument", multiple "arguments" with commas are reproduced in the macro's output. You can take the same approach to make your own macros safe from this problem, although it only works on the last argument of a multi-argument macro.

Property Synthesis
Take the following class:

    @interface MyClass : NSObject {
        NSString *_myIvar;
    }

    @property (copy) NSString *myIvar;

    @end

    @implementation MyClass

    @synthesize myIvar;

    @end

Nothing wrong with this, right? The ivar declaration and @synthesize are a little redundant in this modern age, but do no harm.

Unfortunately, this code will silently ignore _myIvar and synthesize a new variable called myIvar, without the leading underscore. If you have code that uses the ivar directly, it will see a different value from code that uses the property. Confusion!

The rules for @synthesize variable names are a little weird. If you specify a variable name with @synthesize myIvar = _myIvar;, then of course it uses whatever you specify. If you leave out the variable name, then it synthesizes a variable with the same name as the property. If you leave out @synthesize altogether, then it synthesizes a variable with the same name as the property, but with a leading underscore.

Unless you need to support 32-bit Mac, your best bet these days is to just avoid explicitly declaring backing ivars for properties. Let @synthesize create the variable, and if you get the name wrong, you'll get a nice compiler error instead of mysterious behavior.

Interrupted System Calls
Cocoa code usually sticks to higher level constructs, but sometimes it's useful to drop down a bit and do some POSIX. For example, this code will write some data to a file descriptor:

    int fd;
    NSData *data = ...;

    const char *cursor = [data bytes];
    NSUInteger remaining = [data length];

    while(remaining > 0) {
        ssize_t result = write(fd, cursor, remaining);
        if(result < 0)
        {
            NSLog(@"Failed to write data: %s (%d)", strerror(errno), errno);
            return;
        }
        remaining -= result;
        cursor += result;
    }

However, this can fail, and it will fail strangely and intermittently. POSIX calls like this can be interrupted by signals. Even harmless signals handled elsewhere in the app like SIGCHLD or SIGINFO can cause this. SIGCHLD can occur if you're using NSTask or are otherwise working with subprocesses. When write is interrupted by a signal, it returns -1 and sets errno to EINTR to indicate that the call was interrupted. The above code treats all errors as fatal and will bail out, even though the call just needs to be tried again. The correct code checks for that separately and just retries the call:

    while(remaining > 0) {
        ssize_t result = write(fd, cursor, remaining);
        if(result < 0 && errno == EINTR)
        {
            continue;
        }
        else if(result < 0)
        {
            NSLog(@"Failed to write data: %s (%d)", strerror(errno), errno);
            return;
        }
        remaining -= result;
        cursor += result;
    }

String Lengths
The same string, represented differently, can have different lengths. This is a relatively common but incorrect pattern:

    write(fd, [string UTF8String], [string length]);

The problem is that NSString computes length in terms of UTF-16 code units, while write wants a count of bytes. While the two numbers are equal when the string only contains ASCII (which is why people so frequently get away with writing this incorrect code), they're no longer equal once the string contains non-ASCII characters such as accented characters. Always compute the length of the same representation you're manipulating:

    const char *cStr = [string UTF8String];
    write(fd, cStr, strlen(cStr));

Casting to BOOL
Take this bit of code that just checks to see whether an object pointer is nil:

    - (BOOL)hasObject
    {
        return (BOOL)_object;
    }

This works... usually. However, roughly 6% of the time, it will return NO even though _object is not nil. What gives?

The BOOL type is, unfortunately, not a boolean. Here's how it's defined:

    typedef signed char BOOL;

This is another bit of unfortunate legacy from the days when C had no boolean type. Cocoa predates C99's _Bool, so it defines its "boolean" type as a signed char, which is just an 8-bit integer. When you cast a pointer to an integer, you just get the numeric value of that pointer. When you cast a pointer to a small integer, you just get the numeric value of the lower bits of that pointer. When the pointer looks like this:

    ....110011001110000

The BOOL gets this:

01110000

This is not 0, meaning that it evaluates as true, so what's the problem? The problem is when the pointer looks like this:

    ....110011000000000

Then the BOOL gets this:

00000000

This is 0, also known as NO, even though the pointer wasn't nil. Oops!

How often does this happen? There are 256 possible values in the BOOL, only one of which is NO, so we'd naively expect it to happen about 1/256 of the time. However, Objective-C objects are allocated aligned, normally to 16 bytes. This means that the bottom four bits of the pointer are always zero (something that tagged pointers takes advantage of) and there are only four bits of freedom in the resulting BOOL. The odds of getting all zeroes there are about 1/16, or about 6%.

To safely implement this method, perform an explicit comparison against nil:

    - (BOOL)hasObject
    {
        return _object != nil;
    }

If you want to get clever and unreadable, you can also use the ! operator twice. This !! construct is sometimes referred to as C's "convert to boolean" operator, although it's just built from parts:

    - (BOOL)hasObject
    {
        return !!_object;
    }

The first ! produces 1 or 0 depending on whether _object is nil, but backwards. The second ! then puts it right, resulting in 1 if _object is not nil, and 0 if it is.

You should probably stick to the != nil version.

Missing Method Argument
Let's say you're implementing a table view data source. You add this to your class's methods:

    - (id)tableView:(NSTableView *) objectValueForTableColumn:(NSTableColumn *)aTableColumn row:(NSInteger)rowIndex
    {
        return [dataArray objectAtIndex: rowIndex];
    }

Then you run your app and NSTableView complains that you haven't implemented this method. But it's right there!

As usual, the computer is correct. The computer is your friend.

Look closer. The first parameter is missing. Why does this even compile?

It turns out that Objective-C allows empty selector segments. The above does not declare a method named tableView:objectValueForTableColumn:row: with a missing argument name. It declares a method named tableView::row:, and the first argument is named objectValueForTableColumn. This is a particularly nasty way to typo the name of a method, and if you do it in a context where the compiler can't warn you about the missing method, you may be trying to debug it for a long time.

Conclusion
Objective-C and Cocoa have plenty of pitfalls ready to trap the unwary programmer. The above is just a sampling. However, it's a good list of things to be careful of.

That's it for today! Check back next time for more wacky advice. Friday Q&A is driven by user ideas, in case you didn't already know, so until next time, please send in your ideas for articles!

Friday Q&A 2012-11-30: Let's Build A Mach-O Executable

Gwynne Raskind — Fri, 30 Nov 2012 17:59:00 GMT

Friday Q&A 2012-11-30: Let's Build A Mach-O Executable

This is something of a followup to my last article, dyld: Dynamic Linking On OS X, in which I explored how the dynamic linker dyld does its job. This week, I'm going to recreate the function of both the compiler and the static linker, building a Mach-O binary completely from scratch with only the help of the assembler.

The Right Tool For the Right Job
The best tool on OS X for producing binary files from assembly-language inputs is, of course, the assembler, as. But, if you try to build a raw binary from this, you'll find that as also functions as a static linker in its own right. This isn't what we're after.

A more flexible tool, in this particular respect, is nasm, the Netwide Assembler. nasm is installed by the Xcode commandline tools, but unfortunately, Apple ships a horrifyingly outdated version, 0.98.40, which dates back to 2007 in terms of bug fixes, and to 1999 for features. The most recent version at the time of this writing is 2.10.05, which can be installed with port install nasm, brew install nasm, or whatever other package manager of your choice. If you don't use a package manager, you can download and compile the source yourself.

nasm 2.x includes a number of useful things, like 64-bit support, and Mach-O output. We won't be using nasm's Mach-O support, since the point of all this is to do it by hand, but it'd be kind of nice to build a 64-bit binary using 64-bit instructions instead of split 32-bit words!

Reinserting the Prime Program
Here's the C source code for which we'll build our Mach-O binary. To keep the resulting binary relatively simple, I've written it to avoid importing more than the bare minimum of information:

    #define NULL ((void *)0L)
    extern int printf(const char * restrict format, ...);
    typedef long time_t;
    extern time_t time(time_t *sloc);

    int main(void)
    {
        printf("Hello, world #%ld!\n", time(NULL));
        return 0;
    }

Some things to notice:

Rather than #include <stdio.h> and #include <time.h>, I've manually declared printf() and time(), defined the time_t type, and macroed NULL. This avoids emitting extra debug information for the various stuff defined in the standard headers.
I've defined main() as taking no parameters. This is extremely poor practice in general, but because of C's calling conventions, it works correctly.
I've used a format string that actually does a format replacement so that the compiler with which I produced my test files doesn't get all efficient and replace it with a puts() call instead.

This generates the following assembly (built with Clang 3.3svn at -Os):

            .section        __TEXT,__text,regular,pure_instructions
            .globl  _main
    _main:                                  ## @main
            .cfi_startproc
    ## BB#0:                                ## %entry
            pushq   %rbp
    Ltmp2:
            .cfi_def_cfa_offset 16
    Ltmp3:
            .cfi_offset %rbp, -16
            movq    %rsp, %rbp
    Ltmp4:
            .cfi_def_cfa_register %rbp
            xorl    %edi, %edi
            callq   _time
            leaq    L_.str(%rip), %rdi
            movq    %rax, %rsi
            xorb    %al, %al
            callq   _printf
            xorl    %eax, %eax
            popq    %rbp
            ret
            .cfi_endproc

            .section        __TEXT,__cstring,cstring_literals
    L_.str:                                 ## @.str
            .asciz   "Hello, world #%ld!\n"

    .subsections_via_symbols

The code itself is very straightforward: Inside the __TEXT,__text section, set up a stack frame, call time(), load the L_.str string, set al to zero, call printf, zero eax, tear down the stack frame, and return. Then, in the __TEXT,__cstring section, define the L_.str label to point to a zero-terminated ASCII string. Finally, declare that no symbols in this file occur inside basic blocks, which the linker uses during dead code stripping.

The rest of the directives are related to Call Frame Information, which is used for unwinding data ('.unwind_info' and .eh_frame, exception handling support) and debug information (.debug_frame). We'll be building the first two by hand.

For sanity's sake, I'll be omitting the full DWARF debugging information. Even for this very simple program it would represent a considerable addition to this already overlong article.

The Start of a Mach-O Executable
Our nasm input file will be used to generate a Mach-O file, so we need to start it with a Mach-O header. We'll use the 64-bit Mach-O little-endian format, whose header looks like this:

    struct mach_header_64 {
        uint32_t    magic;      /* mach magic number identifier */
        cpu_type_t  cputype;    /* cpu specifier */
        cpu_subtype_t   cpusubtype; /* machine specifier */
        uint32_t    filetype;   /* type of file */
        uint32_t    ncmds;      /* number of load commands */
        uint32_t    sizeofcmds; /* the size of all the load commands */
        uint32_t    flags;      /* flags */
        uint32_t    reserved;   /* reserved */
    };

    /* Constant for the magic field of the mach_header_64 (64-bit architectures) */
    #define MH_MAGIC_64 0xfeedfacf /* the 64-bit mach magic number */
    #define MH_CIGAM_64 0xcffaedfe /* NXSwapInt(MH_MAGIC_64) */

Here's the nasm input for our Mach-O header:

    bits 64
    cpu x64

    __mh_execute_header:
        dd 0xfeedfacf   ; MH_MAGIC_64
        dd 16777223     ; CPU_TYPE_X86 | CPU_ARCH_ABI64
        dd 0x80000003   ; CPU_SUBTYPE_I386_ALL | CPU_SUBTYPE_LIB64
        dd 2            ; MH_EXECUTE
        dd 16           ; number of load commands
        dd ___loadcmdsend - ___loadcmdsstart    ; size of load commands
        dd 0x00200085   ; MH_NOUNDEFS | MH_DYLDLINK | MH_TWOLEVEL | MH_PIE
        dd 0            ; reserved
    ___loadcmdsstart:

The bits and cpu directives just tell nasm to run in 64-bit mode.

Immediately after the Mach-O header comes the load commands. There's a whole list of commands which are required for an executable, and a huge pile more which might be in one. Clang produces 16 load commands for this executable. A load command looks like this:

    struct load_command {
        uint32_t cmd;       /* type of load command */
        uint32_t cmdsize;   /* total size of command in bytes */
    };

Each load command is actually larger than this; the cmd field tells the loader how to interpret the following data. Load commands must be aligned to an 8-byte boundary for 64-bit Mach-O files.

Segments and Sections
Segments are the blocks of data and code which dyld actually maps into memory at runtime. Sections are subdivisions of segments. Segments and sections both have names, and quite a few are standard and predefined.

Here's our first segment command:

    ___pagezerostart:
        dd 0x19         ; LC_SEGMENT_64
        dd ___pagezeroend - ___pagezerostart    ; command size
        db '__PAGEZERO',0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0            ; VM address
        dq 0x100000000  ; VM size
        dq 0            ; file offset
        dq 0            ; file size
        dd 0x0          ; VM_PROT_NONE (maximum protection)
        dd 0x0          ; VM_PROT_NONE (inital protection)
        dd 0            ; number of sections
        dd 0x0          ; flags
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___pagezeroend:

This is the __PAGEZERO segment, which predefines the entire lower 4GB of the 64-bit virtual memory space as inaccessible. Because of this segment, which is marked unreadable, unwriteable, and nonexecutable, dereferencing NULL pointers causes an immediate segmentation fault.

The next segment command is more complicated:

    ___TEXTstart:
        dd 0x19         ; LC_SEGMENT_64
        dd ___TEXTend - ___TEXTstart    ; command size
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000  ; VM address
        dq 0x1000       ; VM size
        dq 0            ; file offset
        dq 0x1000       ; file size
        dd 0x7          ; VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE
        dd 0x5          ; VM_PROT_READ | VM_PROT_EXECUTE
        dd 6            ; number of sections
        dd 0x0          ; flags
    ___TEXTtextstart:
        db '__text',0,0,0,0,0,0,0,0,0,0 ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___codestart - ___TEXTload ; address
        dq ___codeend - ___codestart    ; size
        dd ___codestart ; offset
        dd 0            ; alignment as power of 2 (1)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x80000400   ; S_REGULAR | S_ATTR_PURE_INSTRUCTIONS | S_ATTR_SOME_INSTRUCTIONS
        dd 0            ; reserved1
        dd 0            ; reserved2
        dd 0            ; reserved3
    ___TEXTstubsstart:
        db '__stubs',0,0,0,0,0,0,0,0,0  ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___stubstart - ___TEXTload ; address
        dq ___stubend - ___stubstart    ; size
        dd ___stubstart ; offset
        dd 1            ; alignment as power of 2 (2)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x80000408   ; S_SYMBOL_STUBS | S_ATTR_PURE_INSTRUCTIONS | S_ATTR_SOME_INSTRUCTIONS
        dd 0            ; reserved1 (index into indirect symbol table)
        dd 6            ; reserved2 (size per stub)
        dd 0            ; reserved3
    ___TEXTstubhelperstart:
        db '__stub_helper',0,0,0    ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___stubhelpstart - ___TEXTload ; address
        dq ___stubhelpend - ___stubhelpstart    ; size
        dd ___stubhelpstart ; offset
        dd 2            ; alignment as power of 2 (4)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x80000400   ; S_REGULAR | S_ATTR_PURE_INSTRUCTIONS | S_ATTR_SOME_INSTRUCTIONS
        dd 0            ; reserved1
        dd 0            ; reserved2
        dd 0            ; reserved3
    ___TEXTcstringstart:
        db '__cstring',0,0,0,0,0,0,0    ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___strsstart - ___TEXTload ; address
        dq ___strsend - ___strsstart    ; size
        dd ___strsstart ; offset
        dd 0            ; alignment as power of 2 (1)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x00000002   ; S_CSTRING_LITERALS
        dd 0            ; reserved1
        dd 6            ; reserved2
        dd 0            ; reserved3
    ___TEXTunwindinfostart:
        db '__unwind_info',0,0,0    ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___uwstart - ___TEXTload   ; address
        dq ___uwend - ___uwstart    ; size
        dd ___uwstart   ; offset
        dd 0            ; alignment as power of 2 (1)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x00000000   ; no flags
        dd 0            ; reserved1
        dd 0            ; reserved2
        dd 0            ; reserved3
    ___TEXTehframestart:
        db '__eh_frame',0,0,0,0,0,0 ; section name (pad to 16 bytes)
        db '__TEXT',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100000000 + ___ehstart - ___TEXTload   ; address
        dq ___ehend - ___ehstart    ; size
        dd ___ehstart   ; offset
        dd 3            ; alignment as power of 2 (8)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x00000000   ; no flags
        dd 0            ; reserved1
        dd 0            ; reserved2
        dd 0            ; reserved3
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___TEXTend:

So, this is the __TEXT segment, which covers all the executable code and a good bit of other data. It contains six sections. Each section is aligned according to its section information, and all the sections are shoved together at the end of the segment, such that the first quite-a-few bytes of __TEXT are zeroed. However, because of how the linker maps segments, __TEXT actually includes all the Mach-O headers. As we'll see later, the symbol table even has its own entry for __mh_execute_header. Here are the sections:

__text - The actual code code of the executable, where all the functions are. In this case, just one function - main(). It's marked as S_REGULAR, which means "it's a plain old section", and flagged as containing both "some instructions" (at least some executable code) and "pure instructions" (only executable code).
__stubs - The jump table which redirects into the lazy and non-lazy symbol sections. See my previous article for an explanation of the contents of this section. It's marked as S_SYMBOL_STUBS, the meaning of which is fairly obvious.
__stub_helper - The helper function for lazy dynamically bound symbols.
__cstring - A section containing the read-only C string literals used within the code.
__unwind_info - The compact unwind information for the executable's code. Generated for exception handling on OS X.
__eh_frame - The DWARF2 unwind information for the executable's code. Generated for exception handling and debugging.

Next comes the __DATA segment:

    ___DATAstart:
        dd 0x19         ; LC_SEGMENT_64
        dd ___DATAend - ___DATAstart    ; command size
        db '__DATA',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100001000  ; VM address
        dq 0x1000       ; VM size
        dq 0x1000       ; file offset
        dq 0x1000       ; file size
        dd 0x7          ; VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE
        dd 0x3          ; VM_PROT_READ | VM_PROT_WRITE
        dd 2            ; number of sections
        dd 0x0          ; flags
    ___DATAnlsymptrstart:
        db '__nl_symbol_ptr',0  ; section name (pad to 16 bytes)
        db '__DATA',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100001000 + ___nlsymptrstart - ___DATAload ; address
        dq ___nlsymptrend - ___nlsymptrstart    ; size
        dd ___nlsymptrstart ; offset
        dd 3            ; alignment as power of 2 (8)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x00000006   ; S_NON_LAZY_SYMBOL_POINTERS
        dd 2            ; reserved1 (index into indirect symbol table)
        dd 0            ; reserved2
        dd 0            ; reserved3
    ___DATAlasymptrstart:
        db '__la_symbol_ptr',0  ; section name (pad to 16 bytes)
        db '__DATA',0,0,0,0,0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100001000 + ___lasymptrstart - ___DATAload ; address
        dq ___lasymptrend - ___lasymptrstart    ; size
        dd ___lasymptrstart ; offset
        dd 3            ; alignment as power of 2 (8)
        dd 0            ; relocations data offset
        dd 0            ; number of relocations
        dd 0x00000007   ; S_LAZY_SYMBOL_POINTERS
        dd 4            ; reserved1 (index into indirect symbol table)
        dd 0            ; reserved2
        dd 0            ; reserved3
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___DATAend:

There's only two sections here, since this program doesn't have any global or static data: the non-lazy and lazy symbol stubs.

And then the last segment, __LINKEDIT:

    ___LINKEDITstart:
        dd 0x19         ; LC_SEGMENT_64
        dd ___LINKEDITend - ___LINKEDITstart    ; command size
        db '__LINKEDIT',0,0,0,0,0,0 ; segment name (pad to 16 bytes)
        dq 0x100002000  ; VM address
        dq 0x1000       ; VM size
        dq 0x2000       ; file offset
        dq ___LINKEDITdataend - ___LINKEDITdatastart    ; file size
        dd 0x7          ; VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE
        dd 0x1          ; VM_PROT_READ
        dd 0            ; number of sections
        dd 0x0          ; flags
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___LINKEDITend:

The __LINKEDIT segment contains a variety of data used by dyld, such as the symbol table, the indirect symbol table, the rebase opcodes, the binding opcodes, the exports table, the function starts information, the data-in-code table, and some codesigning data.

Lots and Lots of Linker Data
The next several load commands deal with static and dynamic linking information:

    ___dyldinfostart:
        dd 0x80000022   ; LC_DYLD_INFO | LC_REQ_DYLD
        dd ___dyldinfoend - ___dyldinfostart    ; command size
        dd ___rebasestart   ; rebase info offset
        dd ___rebaseend - ___rebasestart    ; rebase info size
        dd ___bindstart ; binding info offset
        dd ___bindend - ___bindstart    ; binding info size
        dd 0            ; weak binding info offset
        dd 0            ; weak binding info size
        dd ___lazystart ; lazy binding info offset
        dd ___lazyend - ___lazystart    ; lazy binding info size
        dd ___exportstart   ; export info offset
        dd ___exportend - ___exportstart    ; export info size
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___dyldinfoend:
    ___symtabinfostart:
        dd 0x2          ; LC_SYMTAB
        dd ___symtabinfoend - ___symtabinfostart    ; command size
        dd ___symtabstart   ; symbol table offset
        dd (___symtabend - ___symtabstart) >> 4 ; number of symbols
        dd ___strtabstart   ; string table offset
        dd ___strtabend - ___strtabstart    ; string table size
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___symtabinfoend:
    ___dysymtabinfostart:
        dd 0xb          ; LC_DYSYMTAB
        dd ___dysymtabinfoend - ___dysymtabinfostart    ; command size
        dd 0            ; local symbols index
        dd 8            ; number of local symbols
        dd 8            ; external symbols index
        dd 2            ; number of external symbols
        dd 10           ; undefined symbols index
        dd 3            ; number of undefined symbols
        dd 0            ; table of contents offset
        dd 0            ; table of contents entries
        dd 0            ; module table offset
        dd 0            ; module table entries
        dd 0            ; external references table offset
        dd 0            ; external references table entries
        dd ___indirsymstart ; indirect symbol table offset
        dd (___indirsymend - ___indirsymstart) >> 2 ; indirect symbol table entries
        dd 0            ; local relocation table offset
        dd 0            ; local relocation table entries
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___dysymtabinfoend:
    ___loaddylinkerstart:
        dd 0xe          ; LC_LOAD_DYLINKER
        dd ___loaddylinkerend - ___loaddylinkerstart    ; command size
        dd ___loaddylinkername - ___loaddylinkerstart   ; offset to name
    ___loaddylinkername:
        db '/usr/lib/dyld',0    ; name
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___loaddylinkerend:
    ___maincmdstart:
        dd 0x80000028   ; LC_MAIN | LC_REQ_DYLD
        dd ___maincmdend - ___maincmdstart  ; command size
        dq _main        ; offset of main from start of __TEXT
        dq 0            ; stack size
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___maincmdend:
    ___loadlibsystemstart:
        dd 0xc          ; LC_LOAD_DYLIB
        dd ___loadlibsystemend - ___loadlibsystemstart  ; command size
        dd ___loadlibsystemname - ___loadlibsystemstart ; offset to path
        dd 2            ; UNIX time stamp Wed Dec 31 19:00:02 1960
        dd 0x00a90300   ; current version (0.169.3.0)
        dd 0x00010000   ; compatibility version (0.1.0.0)
    ___loadlibsystemname:
        db '/usr/lib/libSystem.B.dylib' ; path
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___loadlibsystemend:
    ___fstartscmdstart:
        dd 0x26         ; LC_FUNCTION_STARTS
        dd ___fstartscmdend - ___fstartscmdstart    ; command size
        dd ___functionstartsstart   ; offset to function starts data (fun label name, isn't it?)
        dd ___functionstartsend - ___functionstartsstart    ; size of function starts data (even more fun name!)
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___fstartscmdend:
    ___datacodecmdstart:
        dd 0x29         ; LC_DATA_IN_CODE
        dd ___datacodecmdend - ___datacodecmdstart  ; command size
        dd ___datacodestart ; offset to data-in-code information
        dd ___datacodeend - ___datacodestart ; size of data-in-code information
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___datacodecmdend:
    ___dycodesigncmdstart:
        dd 0x2b         ; LC_DYLIB_CODE_SIGN_DRS
        dd ___dycodesigncmdend - ___dycodesigncmdstart  ; command size
        dd ___dylibcodesignaturesstart  ; offset to code signatures from dylibs
        dd ___dylibcodesignaturesend - ___dylibcodesignaturesstart  ; you get the idea, right?
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___dycodesigncmdend:

To summarize, this long blather of data consists of:

A list of dynamic linking info for the binary. This command, along with some others, is marked with LC_REQ_DYLD, meaning that if the version of dyld loading the binary doesn't understand the command, it must give up right then rather than continue without the information.
The location of the symbol and strings tables. These are given as offsets from the beginning of the file, but it is understood that the data is contained within the __LINKEDIT segment. At runtime, dyld will perform the calculation symtable_base_address = linkedit_base_address + (symtab_offset - linkedit_offset) to get the actual location in memory of the symbol table. This is repeated similarly for the strings table, as well as the offsets given in the LC_DYLD_INFO and LC_DYSYMTAB commands.
A set of dynamic symbol data for the binary, giving the offsets and counts within the symbol table for various types of symbols.
The LC_LOAD_DYLINKER command which gives the hardcoded path for the dynamic linker to load the executable with. This is used by the kernel rather than the dynamic linker, which will run the specified program when the process is spawned. Don't get the idea that you can use this to subvert the loading process, however; the kernel won't let you pick just any dynamic linker.
LC_MAIN, a replacement for the older LC_UNIXTHREAD command. It used to be that executables were initialized with a thread state specified within the binary itself, but recently, someone realized this was a waste of time and space with dyld running early and the state being exactly the same in practically every executable. Instead, LC_MAIN gives the address of the entry point (main()) and dyld jumps right to that instead, also replacing the old crt1.o object which contained glue code to set up main().
LC_LOAD_DYLIB is the "I link to this dynamic library for some of my undefined symbols" command. This binary only links to libSystem.B.dylib, the OS X equivalent of libc.
LC_FUNCTION_STARTS is a table of data in the __LINKEDIT segment which gives the address of every function entry point in the executable. Among other things, this allows for functions to exist that have no entries in the symbol table.
LC_DATA_IN_CODE is similarly a table giving the locations of data bytes which are embedded within executable code. This is useful for any number of purposes, not the least of which is accurate disassembly.
LC_DYLIB_CODE_SIGN_DRS, finally, gives a list of designated requirements for each dynamic library linked with the executable. This allows the code signing machinery to determine the suitability of the executable without having to load every dynamic library it links to.

A Few More!
Just when you thought we were done, there're three more load commands we haven't covered yet:

    ___uuidstart:
        dd 0x1b         ; LC_UUID
        dd ___uuidend - ___uuidstart    ; command size
        db 0xd3,0xec,0x58,0x28,0x02,0x26,0x36,0x29,0xab,0xc3,0x7d,0x6d,0xc9,0xf9,0x2d,0xda  ; D3EC5828-0226-3629-ABC3-7D6DC9F92DDA
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___uuidend:
    ___osverstart:
        dd 0x24         ; LC_VERSION_MIN_MACOSX
        dd ___osverend - ___osverstart  ; command size
        dd 0x000a0800   ; OS min version: 10.8
        dd 0x000a0800   ; Build SDK version: 10.8
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___osverend:
    ___sourceverstart:
        dd 0x2a         ; LC_SOURCE_VERSION
        dd ___sourceverend - ___sourceverstart  ; command size
        dq 0            ; Source version: 0.0.0.0.0
        align 8, db 0   ; pad with zero to 8-byte boundary
    ___sourceverend:
    ___loadcmdsend:

These are the binary's UUID, the version of OS X it's meant for, the version of the SDK it was linked against, and the "source version". I can't find any clue what the "source version" actually is, and it's just a bunch of zeroes in the binaries I've looked at, so your guess is as good as mine.

Finally, Something Else!
The first thing we do now is pad out the file to the start of main():

    ___TEXTload:
        times (0xf14-($-$$)) db 0   ; pad the __TEXT segment

You might ask why I didn't write _main-($-$$) there, and hardcoded the start address. It certainly looks fragile. Well, it is. The problem is that nasm doesn't provide a simple means to align data to the "end" of a segment, especially since we're not using its built-in sectioning support. It doesn't know where _main is until the padding has been added! In this case, I just hardcode the offset where main() starts (which is the exact value of the __TEXT,__text section's addr field) and let it stand as a hack, rather than trying to figure out an elegant-but-complicated solution.

Now we take the data in order; we don't even really have to do it in any particular order, since the labels we used in the load commands will relocate everything according to where we place it in the file, but there's no reason not to. The first thing is __TEXT,__text, the executable code. Notice that we have to rewrite the original assembly code to nasm's syntax - nasm uses the Intel syntax, rather than the GNU syntax. The major difference is that all the operands are backwards, and there's no qualifier on the register names. All the various directives are also stripped out, since we're doing their jobs by hand.

    ___codestart:
    _main:
        push    rbp
        mov     rbp, rsp
        xor     edi, edi
        call    _time
        lea     rdi, [rel L_str]
        mov     rsi, rax
        xor     al, al
        call    _printf
        xor     eax, eax
        pop     rbp
        ret
    ___codeend:

We also don't have any size suffixes on the instructions, since nasm can infer them from the operands. The rel qualifier for the string load just tells nasm to generate a rip-relative access instead of an absolute position, which is necessary since we marked the executable as position-independent.

Next we have the symbol stubs for time() and printf(), and the stub helper:

    ___stubstart:
    _printf:
        jmp     [rel _lazy_printf]
    _time:
        jmp     [rel _lazy_time]
    ___stubend:

    ___stubhelpstart:
    _stub_helper:
        lea     r11, [rel _nonlazy_dyld_stub_binder]
        push    r11
        jmp     [rel _nonlazy_dyld_stub_binder]
        nop
        push    strict qword (_lazy_printf - ___lasymptrstart)
        jmp     _stub_helper
        push    strict qword (_lazy_time - ___lasymptrstart)
        jmp     _stub_helper
    ___stubhelpend:

The stubs themselves jump to the lazy symbol bindings in the __DATA segment. These initially jump right back into the bottom of _stub_helper, which loads the offset into the lazy symbol section of the symbol and calls into dyld itself through a nonlazy symbol (which will be bound by dyld when the executable is loaded). dyld will bind the symbol and rewrite the lazy symbol section so that future calls to that stub go directly to the function. Notice, these are all direct, non-conditional jumps, not subroutine calls. Also notice the use of the strict qword directives to force nasm to emit the full 64-bit values for the stack pushes.

Next comes the C strings section, very short and simple since we only have one string:

    ___strsstart:
    L_str:
        db      "Hello, world #%ld!\n",0
    ___strsend:

And now the unwinding table. This is encoded with the "compact unwind encoding" defined by Apple (as far as I know).

    ___uwstart:
        dd 1            ; unwind info version
        dd _commonEncodings - ___uwstart    ; common encodings array offset
        dd 0            ; count of common encodings
        dd _personalities - ___uwstart  ; personality array offset
        dd 0            ; count of personalities
        dd _index - ___uwstart  ; first-level index offset
        dd 2            ; count of entries in first-level index
    _commonEncodings:
    _personalities:
    _index:
    __entry1_0:
        dd _main        ; function offset
        dd __entry2_0 - ___uwstart  ; offset to second-level entry
        dd _lsda - ___uwstart   ; offset to language-specific data array entry
    __entry1_1:
        dd ___codeend+1 ; function offset (end of table)
        dd 0            ; offset to second-level entry - zero means end of table
        dd _lsda - ___uwstart   ; offset to LSDA
    _lsda:
    _pages:
    __entry2_0:
        dd 3            ; UNWIND_SECOND_LEVEL_COMPRESSED
        dw ___entrypage0 - __entry2_0   ; offset to entry page
        dw 1            ; number of entries in entry page
        dw ___enc0 - __entry2_0 ; offset to encoding page
        dw 1            ; number of entries in encoding page
    ___entrypage0:
    ____entrypage0_0:
        dd (0 << 24) | (0)  ; encoding index and function offset relative to first-level index offset
    ___enc0:
    ____enc0_0:
        dd 0x01000000   ; UNWIND_X86_64_MODE_RBP_FRAME | UNWIND_X86_64_REG_NONE
    ___uwend:

And then the DWARF-encoded version of the same information. To save everyone some time, I'm not going to write this part out with all the comments, because it's complex and it just duplicates the unwinding info above in a much more verbose fashion.

    ___ehstart:
        db 0x14,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x7a,0x52,0x00,0x01,0x78,0x10,0x01
        db 0x10,0x0c,0x07,0x08,0x90,0x01,0x00,0x00,0x24,0x00,0x00,0x00,0x1c,0x00,0x00,0x00
        db 0x34,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x20,0x00,0x00,0x00,0x00,0x00,0x00,0x00
        db 0x00,0x41,0x0e,0x10,0x86,0x02,0x43,0x0d,0x06,0x00,0x00,0x00,0x00,0x00,0x00,0x00
    ___ehend:

Data, data, data... well, sort of
That ends off the __TEXT segment. Now we have the __DATA segment, which contains the lazy and non-lazy symbol pointers:

    ___DATAload:

    ___nlsymptrstart:
    _nonlazy_dyld_stub_binder:
        dq 0x0000000000000000
    _nonlazy_table_start:
        dq 0x0000000000000000
    ___nlsymptrend:

    ___lasymptrstart:
    _lazy_printf:
        dq 0x100000000 + _stub_helper_printf
    _lazy_time:
        dq 0x100000000 + _stub_helper_time
    ___lasymptrend:

In a real executable, __DATA would usually also contain static data, space for globals, and some other stuff.

The link editor
__LINKEDIT is a real pain, because it's arbitrarily structured and the data within it isn't always all that documented. I've done my best to represent what's in it comprehensibly, but I can't guarantee I've succeeded.

We start with the rebasing opcodes, which dyld uses when applying ASLR:

    ___rebasestart:
        db 0x10 | 0x01  ; REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER
        db 0x20 | 0x02  ; REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | indexOfSegment(__DATA) (2)
        db 0x10         ; uleb128_encode(_lazy_printf - ___DATAload)
        db 0x50 | 0x02  ; REBASE_OPCODE_DO_REBASE_IMM_TIMES | 2
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___rebaseend:

This says, "using pointers, in the __DATA segment at offset 0x10, rebase 2 pointers based on the load address of that segment".

Next come the binding opcodes and lazy binding opcodes:

    ___bindstart:
        db 0x11         ; BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | 1
        db 0x40         ; BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | 0
        db 'dyld_stub_binder',0 ; immediate operand
        db 0x51         ; BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER
        db 0x72         ; BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | indexOfSegment(__DATA) (2)
        db 0x00         ; uleb128_encode(0)
        db 0x90         ; BIND_OPCODE_DO_BIND
        db 0x00         ; BIND_OPCODE_DONE
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___bindend:
    ___lazystart:
        db 0x72,0x10    ; BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | indexOfSegment(__DATA) (2), uleb128_encode(0x10)
        db 0x11         ; BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | 1
        db 0x40,'_printf',0 ; BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | 0, '_printf'
        db 0x90,0x00    ; BIND_OPCODE_DO_BIND, BIND_OPCODE_DONE
        db 0x72,0x18    ; BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | indexOfSegment(__DATA) (2), uleb128_encode(0x18)
        db 0x11         ; BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | 1
        db 0x40,'_time',0   ; BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM | 0, '_time'
        db 0x90,0x00    ; BIND_OPCODE_DO_BIND, BIND_OPCODE_DONE
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___lazyend:

These opcodes bind a non-lazy symbol named dyld_stub_binder to offset 0 in the __DATA segment as a pointer. For lazy symbols, they bind a symbol named _printf to offset 0x10 in the __DATA segment and _time to offset 0x18.

And here's the export trie:

    ___exportstart:
    _exnode0:
        db 0x00         ; terminal size
        db 0x01         ; child count
        db '_',0        ; name
        db _exnode1 - ___exportstart    ; child node offset
    _exnode1:
        db 0x00         ; terminal size
        db 0x02         ; child count
        db '_mh_execute_header',0   ; name
        db _exnode3 - ___exportstart    ; child node offset
    _exnode2:
        db 'main',0     ; name
        db _exnode4 - ___exportstart    ; child node offset
    _exnode3:
        db 0x02         ; terminal size
        db 0x00         ; flags
        db 0x00         ; address - uleb128_encode(0)
        db 0x00         ; child count
    _exnode4:
        db 0x03         ; terminal size
        db 0x00         ; flags
        db 0x94,0x1e    ; address - uleb128_encode(0xf14)
        db 0x00         ; child count
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___exportend:

This forms a trie, or prefix tree, for the two symbols exported by the executable, __mh_execute_header and _main.

Have the compressed function starts table, represented as a set of deltas to be added to the base code address:

    ___functionstartsstart:
        db 0x94         ; delta = 0x14, address  = ___codestart
        db 0x1e         ; delta = 0x1e, end 
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___functionstartsend:

Here's the data-in-code table. Whoops, there isn't any in this executable, the load command's just added anyway:

    ___datacodestart:
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___datacodeend:

How about some designated requirements for dylibs? I have no real idea what format this is in, I just interpreted it as best I could:

    ___dylibcodesignaturesstart:
        dd 1            ; count of code signatures (maybe?)
        dd 0            ; unknown
        dd 0x14         ; unknown
        db 0xfa,0xde,0x0c,0x00,0x00,0x00,0x00,0x28
        db 0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x06
        db 0x00,0x00,0x00,0x02,0x00,0x00,0x00,0x0b
        db 0x6c,0x69,0x62,0x53,0x79,0x73,0x74,0x65
        db 0x6d,0x2e,0x42,0x00,0x00,0x00,0x00,0x03  ; code signature for libSystem.B.dylib
        dd 0            ; unknown
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___dylibcodesignaturesend:

A symbol table
The symbol table is where most the interesting stuff that's left happens:

    ___symtabstart:
        dd L_srcdir - ___strtabstart    ; string table offset
        db 0x64         ; N_SO
        db 0x00         ; section 0
        dw 0x00         ; no desc
        dq 0            ; address 0
        dd L_srcfile - ___strtabstart   ; string table offset
        db 0x64         ; N_SO
        db 0x00         ; section 0
        dw 0x00         ; no desc
        dq 0            ; address 0
        dd L_objfile - ___strtabstart   ; string table offset
        db 0x66         ; N_OSO
        db 0x03         ; section 3
        dw 0x01         ; desc(?)
        dq 0x50b8c91f   ; st_mtime
        dd L_empty - ___strtabstart ; no string
        db 0x2e         ; N_BNSYM
        db 0x01         ; section 1
        dw 0x00         ; desc
        dq 0x100000000 + _main      ; start address
        dd L_main1 - ___strtabstart ; string table offset
        db 0x24         ; N_FUN
        db 0x01         ; section 1
        dw 0x00         ; desc
        dq 0x100000f14  ; start address
        dd L_empty - ___strtabstart ; no string
        db 0x24         ; N_FUN
        db 0x00         ; section 0
        dw 0x00         ; desc
        dq 0x20         ; address
        dd L_empty - ___strtabstart ; no string
        db 0x4e         ; N_ENSYM
        db 0x01         ; section 1
        dw 0x00         ; desc
        dw 0x20         ; address
    _sym_mh_execute_header:
        dd L_mhexechead - ___strtabstart    ; string table offset
        db 0x0f         ; N_SECT | N_EXT
        db 0x01         ; section 1
        dw 0x0010       ; REFERENCED_DYNAMICALLY
        dq 0x100000000 + __mh_execute_header    ; start address
    _sym_main:
        dd L_main2 - ___strtabstart ; string table offset
        db 0x0f         ; N_SECT | N_EXT
        dw 0x0000       ; no extra flags
        dq 0x100000000 + _main  ; start address
    _sym_printf:
        dd L_printf - ___strtabstart    ; string table offset
        db 0x01         ; N_UNDF | N_EXT
        dw 0x0100       ; dynamic library 1
        dq 0            ; address
    _sym_time:
        dd L_time - ___strtabstart  ; string table offset
        db 0x01         ; N_UNDF | N_EXT
        dw 0x0100       ; dynamic library 1
        dq 0            ; address
    _sym_dyld_stub_binder:
        dd L_binder - ___strtabstart    ; string table offset
        db 0x01         ; N_UNDF | N_EXT
        dw 0x0100       ; dynamic library 1
        dq 0            ; address
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___symtabend:

    ___indirsymstart:
        dd (_sym_printf - ___symtabstart) >> 4  ; index into symbol table
        dd (_sym_time - ___symtabstart) >> 4    ; index into symbol table
        dd (_sym_dyld_stub_binder - ___symtabstart) >> 4    ; index into symbol table
        dd 0x40000000   ; INDIRECT_SYMBOL_ABS
        dd (_sym_printf - ___symtabstart) >> 4  ; index into symbol table
        dd (_sym_time - ___symtabstart) >> 4    ; index into symbol table
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___indirsymend:

    ___strtabstart:
    L_spc:
        db ' '
    L_empty:
        db 0
    L_srcdir:
        db '/Users/gwynne/',0
    L_srcfile:
        db 'test.c',0
    L_objfile:
        db '/var/folders/b8/qgjb841d71d55cf8jh1myb540000gn/T/test-KyuIba.o',0
    L_main1:
        db '_main',0
    L_mhexechead:
        db '__mh_execute_header',0
    L_main2:
        db '_main',0
    L_printf:
        db '_printf',0
    L_time:
        db '_time',0
    L_binder:
        db 'dyld_stub_binder',0
        align 8, db 0   ; pad with 0 to 8-byte boundary
    ___strtabend:

    ___LINKEDITdataend:

Here you have the symbol table (including STABS entries), the indirect symbol table (which is nothing but a set of indexes into the symbol table which tell dyld how to use the symbol stubs in the event that the binding opcodes aren't good enough - basically, legacy data), and the string table, which holds all the user-readable strings for the symbol table.

Conclusion
That is one long mess of mostly raw hexadecimal bytes. And here's the punch line: As written here, it still doesn't produce a working Mach-O binary!

Why not? Because I didn't account for alignment requirements properly, and I ran out of time to fix the problem before the article had to go up. All the tables and structures here are correct, though, so hopefully, it's still instructional as to just how much goes into even the simplest binary, and how much work you should be very glad ld and dyld are doing for you!

Thanks for reading, as always. I hope you enjoyed it!

Friday Q&A 2012-11-16: Let's Build objc_msgSend

Mike Ash — Fri, 16 Nov 2012 14:27:00 GMT

Friday Q&A 2012-11-16: Let's Build objc_msgSend

The objc_msgSend function underlies everything we do in Objective-C. Gwynne Raskind, reader and occasional Friday Q&A guest contributor, suggested that I talk about how objc_msgSend works on the inside. What better way to understand how something works than to build it from scratch? Let's build objc_msgSend.

Tramapoline! Trampopoline!
Whenever you write an Objective-C message send:

    [obj message]

The compiler generates a call to objc_msgSend:

    objc_msgSend(obj, @selector(message));

objc_msgSend then takes care of dispatching the message.

How does it do that? It looks up the appropriate function pointer, or IMP, to invoke, then jumps to it. Any arguments passed to objc_msgSend end up being arguments to the IMP after the jump. The return value from the IMP ends up as the return value seen by the caller.

Because objc_msgSend only takes control long enough to obtain the right function pointer and directly jump to it, it's sometimes referred to as a trampoline. In general, any small piece of code that serves to redirect code somewhere else can be called a trampoline.

It is this trampolining behavior that makes objc_msgSend special. Because it simply looks up the right code and then jumps directly to it, it's relatively generic. It works with any combination of parameters passed to it, because it just leaves them alone for the method IMP to read. Return values are a bit trickier, but it turns out that every possible return type can be accounted for with just a couple of variants of objc_msgSend.

Unfortunately, this trampoline behavior cannot be written in pure C. There is no way to write a C function that passes through generic parameters to another function. You can come close by using variable arguments, but variable arguments are passed differently from normal arguments and in a way that's slower, so it's not compatible with regular C parameters.

If you could write objc_msgSend in C, the basic idea would look something like this:

    id objc_msgSend(id self, SEL _cmd, ...)
    {
        Class c = object_getClass(self);
        IMP imp = class_getMethodImplementation(c, _cmd);
        return imp(self, _cmd, ...);
    }

This is actually a bit over-simplified. There's a method cache to make the whole lookup faster, so it's more like this:

    id objc_msgSend(id self, SEL _cmd, ...)
    {
        Class c = object_getClass(self);
        IMP imp = cache_lookup(c, _cmd);
        if(!imp)
            imp = class_getMethodImplementation(c, _cmd);
        return imp(self, _cmd, ...);
    }

Except that, for speed, cache_lookup is implemented inline.

Assembly
In Apple's runtime, the whole function is implemented in assembly for maximum speed. objc_msgSend runs for every single Objective-C message send, and the simplest action in app can result in thousands or millions of messages.

To simplify things a bit, my own implementation will do the bare minimum in assembly, with all of the smarts in a separate C function. The assembly itself will do the equivalent of:

    id objc_msgSend(id self, SEL _cmd, ...)
    {
        IMP imp = GetImplementation(self, _cmd);
        imp(self, _cmd, ...);
    }

Then GetImplementation can do all of the work in a more understandable fashion.

The assembly code needs to:

Save all potential parameters somewhere safe, so that GetImplementation won't overwrite them.
Call GetImplementation.
Save the return value somewhere.
Restore all of the parameter values.
Jump to the IMP returned from GetImplementation.

So let's get started!

I'm going to use x86-64 assembly here, as it's the most convenient to work with on a Mac. The same principles would apply for i386 or ARM.

This function goes into its own file, which I called msgsend-asm.s. This file can be passed to the compiler as just another source file, and it will assemble it and link it into the rest of the program.

The first thing to do is to actually declare the global symbol. For boring historical reasons, C functions get an extra leading underscore in their global symbol name:

    .globl _objc_msgSend
    _objc_msgSend:

The compiler will happily link against the nearest available objc_msgSend. Simply linking this into a test app is enough to get [obj message] expressions going to our own code rather than Apple's runtime, which is terribly convenient when it comes to testing this code to make sure it actually works.

Integer and pointer parameters are passed in registers %rsi, %rdi, %rdx, %rcx, %r8, and %r9. Any additional parameters beyond what would fit in there get passed on the stack. The first thing this function does is save those six registers onto the stack as well, so they can be restored later:

    pushq %rsi
    pushq %rdi
    pushq %rdx
    pushq %rcx
    pushq %r8
    pushq %r9

In addition to these registers, the %rax register acts as something of a hidden parameter. It's used for variable-argument calls, and in that case it stores the number of vector registers passed in, which is used by the called function to properly prepare the variable argument list. In case the target method is a variable-argument method, I save this register as well:

    pushq %rax

For completeness, the %xmm registers used to pass floating-point arguments really ought to be saved as well. However, if I can safely assume that GetImplementation doesn't use any floating point, then I can ignore them, which I do simply to keep the code shorter.

Next, I align the stack. Mac OS X requires that the stack be aligned to a 16-byte boundary when making function calls. The above code leaves us with an aligned stack anyway, but it's nice to have code to explicitly handle it so that you don't have to worry about making sure everything is lined up, or wondering why your app is crashing in dyld functions. To align the stack, I save the existing stack pointer into %r12 after saving the original value of %r12 onto the stack. The choice of %r12 is somewhat arbitrary, and any caller-saved register would do. The important thing is that the value is guaranteed to survive across the call to GetImplementation. Then I and the stack pointer with -0x10, which just clears the bottom four bits:

    pushq %r12
    mov %rsp, %r12
    andq $-0x10, %rsp

Now the stack pointer is aligned. It's also safely past any of the saved registers from above, since the stack grows down, and this alignment procedure will only move it further down.

It's finally time to call into GetImplementation. It takes two parameters, self and _cmd. Calling conventions are for those two parameters to go into %rsi and %rdi, respectively. However, they were passed into objc_msgSend like that, and haven't been moved, so nothing has to be done to get them into place. All that has to be done is actually make the call to GetImplementation, which also gets a leading underscore:

    callq _GetImplementation

Integer and pointer return values are returned in %rax, so that's where the returned IMP is found. Since %rax has to be restored to its original state, the returned IMP needs to be moved elsewhere. I arbitrarily chose to store it into %r11:

    mov %rax, %r11

Now it's time to start putting things back the way they were. The first item is to restore the stack pointer, which was stashed in %r12, and restore the old value of %r12:

    mov %r12, %rsp
    popq %r12

Then pop all of the argument registers off the stack in the opposite order from when they were pushed:

    popq %rax
    popq %r9
    popq %r8
    popq %rcx
    popq %rdx
    popq %rdi
    popq %rsi

Everything is now ready. The argument registers are restored to how they were before. All parameters intended for the target method are in the place where the target method will expect to find them. The IMP itself is in %r11, so all that has to be done is to jump there:

    jmp *%r11

And that's it! There's nothing more to be done in the assembly code. The jump passes control to the method implementation. From the perspective of that code, it looks exactly as if the message sender directly invoked the method. All of the indirection above just disappears. When the method returns, it will return directly to the caller of objc_msgSend without any further intervention. Any return value from the method will be found in the correct place.

There's a bit of subtlety when it comes to unusual return values. Large structs (anything too large to be returned in a register) are the most common example of this. On x86-64, large structs are returned by using a hidden first parameter. When you make a call like this:

    NSRect r = SomeFunc(a, b, c);

The call gets translated to something more like this:

    NSRect r;
    SomeFunc(&r, a, b, c);

The address of memory to use for the return value gets passed in %rdi. Since objc_msgSend expects %rdi and %rsi to contain self and _cmd, it won't work for messages that return large structs. This same basic problem exists on many different platforms. The runtime solves this problem by providing a separate objc_msgSend_stret function used for struct returns, which works like objc_msgSend, but knows to find self in %rsi and _cmd in %rdx.

A similar problem arises on some platforms with messages that return floating point values. On those platforms, the runtime provides objc_msgSend_fpret (and on x86-64, objc_msgSend_fpret2 for extremely special cases).

Method Lookup
Let's move on to the implementation of GetImplementation. The above assembly trampoline means that this code can be written in C. Remember that in the real runtime, this code is all straight assembly, in order to get the best speed possible. Not only does this allow for fine control over the code, but it also eliminates the need to save and restore all of those registers like the code above does.

GetImplementation could simply call class_getMethodImplementation and be done with it, foisting all of the work onto the Objective-C runtime. This is a bit boring, though. The real objc_msgSend looks in the class's method cache first, for maximum speed. Since GetImplementation is intended to mimic objc_msgSend, it will do the same. Only if the cache doesn't contain an entry for the given selector will it fall back to querying the runtime.

The first thing we need is some struct definitions. The method cache is a private set of structures accessed through the class structure, so to get to it we need our own definitions. Note that, while private, these definitions are all available as part of Apple's open source release of the Objective-C runtime.

First comes the definition for a single cache entry:

    typedef struct {
        SEL name;
        void *unused;
        IMP imp;
    } cache_entry;

Pretty easy. Don't ask me about the unused field, I don't know why that's there. Here's the definition for the cache as a whole:

    struct objc_cache {
        uintptr_t mask;
        uintptr_t occupied;        
        cache_entry *buckets[1];
    };

The cache is implemented as a hash table. This table is built for speed and simplicity over all else, so it's a bit unusual. The table size is always a power of two. The table is indexed by selector, and the bucket index is computed by simply taking the selector's value, possibly shifting it to get rid of irrelevant low bits, and performing a logical and with the appropriate mask. While we're at it, here are macros used to compute the bucket index for a particular selector and mask:

    #ifndef __LP64__
    # define CACHE_HASH(sel, mask) (((uintptr_t)(sel)>>2) & (mask))
    #else
    # define CACHE_HASH(sel, mask) (((unsigned int)((uintptr_t)(sel)>>0)) & (mask))
    #endif

Finally, there's the structure for the class itself. This is what a Class actually points to:

    struct class_t {
        struct class_t *isa;
        struct class_t *superclass;
        struct objc_cache *cache;
        IMP *vtable;
    };

Let's get started with GetImplementation now that the necessary structs are there:

    IMP GetImplementation(id self, SEL _cmd)
    {

The first thing it does is get the object's class. The real objc_msgSend does this with the equivalent of self->isa, but I'll be gentle and use the official API for that part:

        Class c = object_getClass(self);

Since I want access to the guts, I'll immediately cast to a pointer to the class_t struct:

        struct class_t *classInternals = (struct class_t *)c;

Now it's time to look up the IMP. We'll start off with it set to NULL. If we find an entry in the cache, we'll set it. If it's still NULL after checking the cache, we'll fall back to the slow path:

        IMP imp = NULL;

Next, grab a pointer to the cache:

        struct objc_cache *cache = classInternals->cache;

Compute the bucket index, and grab a pointer to the array of buckets:

        uintptr_t index = CACHE_HASH(_cmd, cache->mask);
        cache_entry **buckets = cache->buckets;

Next, we search for a cache entry with the appropriate selector. The runtime uses linear chaining, so it's just a matter of searching subsequent buckets until either we find a match or find a NULL entry:

        for(; buckets[index] != NULL; index = (index + 1) & cache->mask)
        {
            if(buckets[index]->name == _cmd)
            {
                imp = buckets[index]->imp;
                break;
            }
        }

If no entry was found, we fall back to the slow path and call into the runtime. In the real objc_msgSend, all of the above code is written in assembly, and this is the point where it would drop out of assembly and call into the runtime itself. Once the cache has been tried and no entry was found, any hope for a fast message send is gone. The need to go fast becomes much less important at this point, partly because it's already doomed to be slow, and partly because this path should be taken extremely rarely. Because of that, it's acceptable to drop out of the assembly code and call into more maintainable C:

        if(imp == NULL)
            imp = class_getMethodImplementation(c, _cmd);

The IMP has now been obtained, one way or another. If it was in the cache, it was retrieved from there, and otherwise it was populated by the runtime. The class_getMethodImplementation call will also populate the cache, so subsequent calls will go faster. All that's left is to return it the IMP:

        return imp;
    }

Testing
To make sure this stuff actually works, I whipped up a quick test program:

    @interface Test : NSObject
    - (void)none;
    - (void)param: (int)x;
    - (void)params: (int)a : (int)b : (int)c : (int)d : (int)e : (int)f : (int)g;
    - (int)retval;
    @end

    @implementation Test

    - (id)init
    {
        fprintf(stderr, "in init method, self is %p\n", self);
        return self;
    }

    - (void)none
    {
        fprintf(stderr, "in none method\n");
    }

    - (void)param: (int)x
    {
        fprintf(stderr, "got parameter %d\n", x);
    }

    - (void)params: (int)a : (int)b : (int)c : (int)d : (int)e : (int)f : (int)g
    {
        fprintf(stderr, "got params %d %d %d %d %d %d %d\n", a, b, c, d, e, f, g);
    }

    - (int)retval
    {
        fprintf(stderr, "in retval method\n");
        return 42;
    }

    @end


    int main(int argc, char **argv)
    {
        for(int i = 0; i < 20; i++)
        {
            Test *t = [[Test alloc] init];
            [t none];
            [t param: 9999];
            [t params: 1 : 2 : 3 : 4 : 5 : 6 : 7];
            fprintf(stderr, "retval gave us %d\n", [t retval]);

            NSMutableArray *a = [[NSMutableArray alloc] init];
            [a addObject: @1];
            [a addObject: @{ @"foo" : @"bar" }];
            [a addObject: @("blah")];
            a[0] = @2;
            NSLog(@"%@", a);
        }
    }

I also added some debug logs to GetImplementation to make sure it actually got called, in case I screwed up the build and ended up calling the runtime's implementation by mistake. Everything worked, and even the literals and subscripting called the replacement implementation.

Conclusion
At its core, objc_msgSend is relatively simple. The way that it's used requires the use of assembly code, however, which makes it more difficult to understand than it really needs to be. Additionally, the extreme performance demands and requisite optimizations mean that it's pretty dense and tricky assembly. However, by building a simple assembly trampoline and then reimplementing the logic in C, we can see just how it works, and there really isn't all that much to it.

This should be obvious, but never ship your own objc_msgSend in your own app. You'll break stuff and you'll be sorry. Do this for educational purposes only.

That's it for today's hallucinatory, assembly-soaked article. Come back next time for more fun, games, and hacking. As I've said roughly one thousand times by now, but can't help but reminding you, Friday Q&A is driven by reader suggestions. If you have a topic that you'd like to see me write about, please send it in!

Friday Q&A 2012-11-09: dyld: Dynamic Linking On OS X

Gwynne Raskind — Fri, 09 Nov 2012 15:51:00 GMT

Friday Q&A 2012-11-09: dyld: Dynamic Linking On OS X

In the course of a recent job interview, I had an opportunity to study some of the internals of dyld, the OS X dynamic linker. I found this particular corner of the system interesting, and I see a lot of people having trouble with linking issues, so I decided to do an article about the basics of dynamic linking. Some of the deeper logic is new to me, so sorry in advance for any inaccuracies.

WARNING
Because the precise details of how dyld works are quite complicated and change frequently, and because I don't yet know all of those details myself, most of my examination of it in this article is simplified, and in some places purely conceptual. If you're curious about the particulars, I strongly recommend dyld's source code, which is publicly available at http://opensource.apple.com.

Static linking
So, let's start by talking about static linking, generally referred to simply as 'linking'. This is the step that typically happens after compiling, where the machine language the compiler churned out from your source code, the object files, are 'linked' together into a single binary file.

Why does static linking matter to dynamic linking? Because the static linker, ld (and ld64) is responsible for transforming symbol references in your source code into indirect symbol lookups for dyld to use later. Here's a very simple example:

    // This is the actual full declaration of main() on OS X. The "apple"
    //  parameter is the path to the executable, i.e. _NSGetProgname().
    int main(int argc, char **argv, char **envp, char **apple)
    {
        puts("Hello, world!\n");
        return 0;
    }

The (optimized) assembly for this, as generated by clang -S test.c -o test.s -Os and stripped of a bit of debug info, is:

            .section        __TEXT,__text,regular,pure_instructions
            .globl  _main
    _main:                                  ## @main
            pushq   %rbp
            movq    %rsp, %rbp
            leaq    L_str(%rip), %rdi
            callq   _puts
            xorl    %eax, %eax
            popq    %rbp
            ret
            .section        __TEXT,__cstring,cstring_literals
    L_str:                                  ## @str
            .asciz  "Hello, world!"

Seems straightforward enough. Let's compile it into an object file and dump the fully compiled version (clang -c test.c -o test.o -Os, otool -tv test.o):

    _main:
    0000000000000000        pushq   %rbp
    0000000000000001        movq    %rsp,%rbp
    0000000000000004        leaq    0x00000000(%rip),%rdi
    000000000000000b        callq   0x00000010
    0000000000000010        xorl    %eax,%eax
    0000000000000012        popq    %rbp
    0000000000000013        ret

Whoops, our symbol names are gone! The compiler has replaced them with sets of zero bytes. For the leaq instruction, the result is a load from the current value of rip. The callq instruction is a "signed offset" jump, which means that the offset of 0 calls the very next instruction in the code (address 0x10 in this case). Never fear, the compiler has generated relocation entries which tell the linker where to update all these zeroes (otool -r test.o):

    Relocation information (__TEXT,__text) 2 entries
    address  pcrel length extern type    scattered symbolnum/value
    0000000c 1     2      1      2       0         4
    00000007 1     2      1      1       0         0

The first entry says, "At offset 0xc in the __TEXT,__text section, there is an unscattered, external, PC-relative X86_64_RELOC_BRANCH reference of length 'long word' to the symbol at index 4 in the symbol table." A peek at the symbol table (nm -ap) gives us:

    0000000000000014 s L_str
    0000000000000048 s EH_frame0
    0000000000000000 T _main
    0000000000000060 S _main.eh
                     U _puts

The symbol at index 4 (the fifth entry) is _puts. Similarly, the symbol at index 0 is L_str, which will be relocated at offset 0x7 of the object file (three bytes into the leaq instruction). Finally, let's look at the result of linking this object into an executable (clang test.c -o test -Os, otool -tv test):

    _main:
    0000000100000f36        pushq   %rbp
    0000000100000f37        movq    %rsp,%rbp
    0000000100000f3a        leaq    0x00000029(%rip),%rdi
    0000000100000f41        callq   0x100000f4a
    0000000100000f46        xorl    %eax,%eax
    0000000100000f48        popq    %rbp
    0000000100000f49        ret

ld has:

Located the __TEXT segment at the standard executable load address for x86_64, 0x0000000100000000, and the __TEXT,__text section at 0xf36 after that. The first 0xf35 (actually, 0xa0f, since the larger offset doesn't account for the file's Mach-O header) bytes of __TEXT are zeroed out. This aligns the __TEXT segment flush up against the __DATA segment. I don't know exactly why this is done, though I assume it has something to do with cache efficiency.
Replaced 0 with the actual offset from the leaq instruction to the L_str symbol, which in this case is 0x29. The resulting address is 0x100000f61, which a peek at the load commands (otool -l test) tells us is the exact beginning of the __TEXT,__cstring section.
Replaced 0 with the address of the symbol stub for puts(), which comes immediately after main. Another peek at the load commands puts this in the __TEXT,__stubs section, which we'll look at in detail later.

Static linking, then, combines object files, resolves symbol references to external libraries, applies the relocations for those symbols, and builds a complete executable. Obviously, this is a huge simplification and applies only to executables. The process of linking dynamic libraries is similar, but not identical, and for brevity's sake I won't go into it here.

What does dyld do, anyway?
dyld is actually responsible for quite a bit of work, all told. It (in roughly this order):

Bootstraps itself based on the very simple raw stack set up for the process by the kernel.
Recursively and cachingly loads all dependent dynamic libraries the executable links to into the process' memory space, including any necessary perusal of search paths from both the environment and the executable's "runpaths".
Links those libraries into the executable by immediately binding non-lazy symbols and setting up the necessary tables for lazy binding.
Runs static initializers for the executable.
Sets up the parameters to the executable's main function and calls it.
During the process' execution, handles calls to lazily-bound symbol stubs by binding the symbols, provides runtime dynamic loading services (via the dl*() API), and provides hooks for gdb and other debuggers to get critical information.
Runs static terminator routines after main returns.
In some scenarios, makes the required call to libSystem's _exit routine once main returns.

I'll examine each step roughly in order.

Bootstrap
dyld is the very first code run in a new process. In particular, a symbol by the very descriptive name of __dyld_start is called. This happens due to a bit of magic in the kernel which notices the LC_LOAD_DYLINKER load command in the main executable and uses the given dynamic linker's entry symbol as the process' initial instruction pointer. __dyld_start performs the following pseudocode (the actual implementation is a compact bit of assembly code):

    noreturn __dyld_start(stack mach_header *exec_mh, stack int argc, stack char **argv, stack char **envp, stack char **apple, stack char **STRINGS)
    {
        stack push 0 // debugger end of frames marker
        stack align 16 // SSE align stack
        uint64_t slide = __dyld_start - __dyld_start_static;
        void *glue = NULL;
        void *entry = dyldbootstrap::start(exec_mh, argc, argv, slide, ___dso_handle, &glue);
        if (glue)
            push glue // pretend the return address is a glue routine in dyld
        else
            stack restore // undo stack stuff we did before
        goto *entry(argc, argv, envp, apple); // never returns
    }

In retrospect, I'm not sure that pseudocode is any more sensible than the assembly would have been, but let's walk through it quickly:

Push a 0 onto the stack, and align the stack to SSE requirements.
Calculate the slide of dyld itself by subtracting the address of a symbol whose address is always the same from the current address of __dyld_start.
Run dyld's actual bootstrap routine, which sets up some minimal state for dyld itself (such as pulling in certain functions from libSystem without actually linking to it and setting up Mach messaging) and then runs dyld's real main routine, which does loading, linking, and initializers.
If dyld detected that the main executable uses the LC_MAIN load command to set up its entry point, it returns the address of a glue routine which is responsible for calling _exit when the process is done. That address is pushed onto the stack, fooling the entry point into thinking it's the routine's return address; the ret instruction at the end of that function will jump to that glue code.
If, on the other hand, dyld detected the executable using the older LC_UNIXTHREAD load command, it simply restores the stack to its original state and jumps to that entry point, which will be the start routine from crt1.o, the C runtime. The C runtime basically redoes all the work that __dyld_start just did, minus the actual dyld startup, which is one of the reasons it was replaced with the LC_MAIN command.
Jump to the entry point.

Loading
Each time dyld has to load a dynamic library, whether at application startup or due to a request at runtime, it must locate the correct binary on disk, map the file into memory, parse the Mach-O headers, and record all the data it just generated for use in linking (which in this context means symbol binding). (Boy, "linking" sure has a lot of different uses, doesn't it?)

Locating the correct binary on disk is usually fairly simple. The LC_LOAD_DYLIB command will give an absolute path, and the binary is loaded from that path. Of course, sometimes that path contains a special marker that tells dyld to look somewhere else:

@executable_path - Up to OS X 10.3, this was the only marker dyld supported, and it had rather limited utility. dyld will replace this marker with the full path to the main executable.
@loader_path - Added in 10.4, this marker is replaced with the full path to the binary which loaded the binary that is currently being loaded. This is not always the main executable, and primarily enabled frameworks to themselves embed frameworks without resorting to the "umbrella framework" mechanism, which Apple never made entirely public and actively discouraged the use of.
@rpath - When this marker was added in 10.5, there was much rejoicing. This marker is replaced in sequence with each "run path" embedded in the binary's loading binaries (recursively), enabling frameworks and dynamic libraries to finally be built only once and be used for both system-wide installation and embedding without changes to their install names, and allowing applications to provide alternate locations for a given library, or even override the location specified for a deeply embedded library.

There are also default search paths, and in some circumstances, further paths can be specified in the environment and load commands.

Linking
Once a dynamic library is loaded into a process (ignoring for now some manipulations related to address space randomization, and also setting aside code signing issues), its non-lazy symbols must be bound.

At this point, I should take a moment out to explain the different between lazy and non-lazy symbols. It's not complicated; a lazy symbol's binding is deferred until the symbol is called the first time by the executable, while a non-lazy symbol is bound immediately when its containing library is loaded. The actual binding process is identical; the only difference is in how that process is triggered.

Conceptually, binding a symbol is simple. In practice, it's rather interesting:

Look up, in the binding information of the __LINKEDIT segment of the executable, the address of the symbol stub for the symbol. Taking our example from above, the stub for _puts was at 0xf4a (plus some, I'm shortening for simplicity's sake!). If we were to disassemble the machine code at that address, we would get:
```
    Contents of (__TEXT,__stubs) section
    0000000100000f4a        jmp     *0x000000c0(%rip)
    Contents of (__TEXT,__stub_helper) section
    0000000100000f50        leaq    0x000000b1(%rip),%r11
    0000000100000f57        pushq   %r11
    0000000100000f59        jmp     *0x000000a1(%rip)
    0000000100000f5f        nop
    0000000100000f60        pushq   $0x00000000
    0000000100000f65        jmp     0x100000f50
```
Wow, a nice simple jump instruction! Unfortunately, it's not quite as simple as replacing the target of the jump with the address of the symbol, since the jump can only be a signed 32-bit offset and the symbol could (and should!) be anywhere in the 64-bit address space. So, the next step is...
Look up, also in the binding information, the address of the symbol pointer for puts in the __DATA,__nl_symbol_ptr section. If this is a lazy symbol, look it up in the __DATA,__la_symbol_ptr section instead. In our example executable, these sections look simply like this (using a hybrid of otool's output):
```
    Contents of (__DATA,__nl_symbol_ptr) section
    0000000100001000        dq      0x0000000000000000
    0000000100001008        dq      0x0000000000000000
    Contents of (__DATA,__la_symbol_ptr) section
    0000000100001010        dq      0x0000000100000f60
```
In short, the non-lazy symbol pointers are just zero bytes, and the lazy symbol pointer points right back to the stub helper section!
Update the address of the symbol pointer in the appropriate __DATA section to the real address of the symbol in the loaded library. You're done!

So what, you may be asking, are all this crazy indirection and all these extra sections all about?

Well, for non-lazy symbols, the indirection is necessary for two reasons. First, you can't put writable data in the __TEXT section, which is executable code. This means you can't update the jump instruction directly at runtime, even if you had a jump instruction that took an absolute 64-bit address. Secondly, you can't put executable code in the __DATA section, which is writable data! So you can't just put a 64-bit jump instruction there either. As a result, the jump instruction is encoded to take an extra level of indirection, as with dereferencing a pointer in C.

All this is true of lazily-bound symbols as well, but with a few caveats. dyld does not immediately bind such a symbol, but just leaves it be. The address saved in the lazy symbol pointer by the static linker isn't a simple 0, but rather points to the "stub helper". The stub helper is a bit of code embedded in the __TEXT,__stub_helper section (really? who'd've guessed?) which pushes the offset into the lazy symbol pointer table to update onto the stack and jumps to the (not lazily bound!) symbol for dyld's internal symbol binder. It doesn't show up in this very simple example, but the stub helper grows by two instructions for each lazy symbol so that the correct offset is passed to dyld. When the lazy binding is finished, the symbol pointer is updated as usual, and the stub helper is never called again for that symbol.

Static initializers, static terminators, and runtime services
Most of the interesting stuff has already happened at this point. dyld will run any static initializers in the executable (most often constructors for global C++ objects and +load methods for Objective-C classes, though there are also __attribute__((constructor)) functions for plain C). A list of initializers is stored in a separate __DATA,__mod_init_func section in the binary, and is simply a set of addresses into the __TEXT,__text section which dyld calls in order of appearance. Initializer functions are passed the same arguments as main.

When the process exits, dyld will also run static terminators, which mostly means static destructors for C++ objects and __attribute__((destructor)) functions. These are handled just like static initializers, except that they're stored in __DATA,__mod_term_func and take no parameters. Static terminators run in the same context as an atexit() function.

Finally, dyld provides runtime services to binaries it has loaded. The dl*() APIs are the preferred interface to dyld's services (and as of 10.5, the only sanctioned interface; the old functions have been deprecated):

dlopen - Performs the load stage of loading a dynamic library, can optionally partially or completely perform the bind stage.
dlsym - Look up a symbol in a dynamic library (or the entire process). At its simplest, this is no more than a "name to address" lookup.
dladdr - The inverse of dlsym, transforming an address into a set of symbol information.
dlclose - Unloads a dynamic library from the process, if no other handles to it are in use. Unloading invalidates all the symbols provided by the dynamic library and can be something of a touchy operation, particularly in an Objective-C environment.

What's missing
While I've gone over quite a bit, I've also left out a lot of information in this article:

Two-level namespaces, which prevent trivial symbol collisions in dynamic libraries
The dyld shared cache, which maintains a systemwide map of already-loaded dynamic libraries for fast binding
Rebasing
Code signing
Dynamic library linking
dyld's expansive set of environment variables
"Restricted" binaries (particularly setuid binaries)
Most of the kernel's interaction with dyld
Compression and encryption in Mach-O binaries
How dyld itself is built
Symbol interposing
dyld's operation on i386 and ARM, which is conceptually the same, but both architectures differ significantly in the details
Details of the Mach-O binary format
How "fat" binaries are handled

I've left these out for two reasons: One, I was a bit behind when writing this article and just didn't have time to put it all in, and two, there really isn't space in one article for all that. However, all of these concepts are at least somewhat documented by Apple, and both the kernel and dyld are open-source. Here are what I hope are some useful links (warning, some of these are pretty outdated, as Apple doesn't seem too interested in updating the documentation):

Apple's Mach-O documentation
Apple's Mach-O reference
The Mach-O "loader" header, a very good reference (also look at other files in the mach-o/ directory) Apple's dyld Reference
The dlopen(3) manpage
dyld's Release Notes
dyld's source code as of 10.8.2
Kernel source code as of 10.8.2 (look at bsd/kern/kern_exec.c and bsd/kern/mach_loader.c in particular)

Conclusion
dyld is one of the most essential parts of OS X; without it, nothing but the kernel would run. With that responsibility inevitably comes significant complexity, and dyld has it aplenty. Some of that complexity comes from the massive backwards-compatibility requirements of dyld, and some simply from the sheer scope of the tasks it must handle. Most developers will have no need to understand linking in such detail, but maybe the next time you get a strange error message in Xcode from the linker, you'll have a better idea of where to look for the problem. Then again, maybe not; ld can be pretty obstructive.

That's all I have for you this week. Come back next week for a special treat from Mike; his next article is particularly awesome!

Friday Q&A 2012-11-02: Building the FFT

Chris Liscio — Fri, 02 Nov 2012 14:29:00 GMT

Friday Q&A 2012-11-02: Building the FFT

In the last post in this mini-series, Mike gave an overview of the Fourier Transform and then showed you how to use Apple's implementation of the Fast Fourier Transform (FFT).

In this installment, I'll show you how we get from point A to point B. Specifically, I'll talk a bit about the magic behind the Fast Fourier Transform.

A bit of math (British localization: Some maths)
Fourier Transforms have some interesting mathematical properties. Most importantly, Fourier Transforms are a linear operation. That is, if we use $\mathcal{F}(h(t))$ to denote the Fourier Transform of $h(t)$ :

$\begin{align} \mathcal{F}(h_a(t) + h_b(t)) &= \mathcal{F}(h_a(t)) + \mathcal{F}(h_b(t)) \text{; and} \\ \mathcal{F}(K \cdot h(t)) &= K \cdot \mathcal{F}(h(t)) \end{align}$

So whether you scale or add two signals in the time or frequency domain is up to you. That's pretty handy when you're working on signal processing code. But I digress.

In addition to the above, there are some more interesting properties relating the time and frequency domain representations of a function. We'll use $h(t) \Leftrightarrow H(f)$ to relate the time and frequency domain representations.

$\begin{align} h(C \cdot t) &\Leftrightarrow \frac{1}{|C|} \cdot H(\frac{f}{C}) && \text{scaling time}\\ \frac{1}{C} \cdot h(\frac{t}{C}) &\Leftrightarrow H(C \cdot f) && \text{scaling frequency}\\ h(t-t_0) &\Leftrightarrow H(f) \cdot e^{2 \pi i f \cdot t_0} && \text{shifting time} \\ h(t) \cdot e^{-2 \pi i t \cdot f_0} &\Leftrightarrow H(f - f_0) && \text{shifting frequency} \\ \end{align}$

Don't focus too much on the individual relations themselves. The main point that I'm trying to get across is that we can manipulate the Fourier Transform and the signal in meaningful ways, and relate those changes between domains.

The Discrete Fourier Transform
Before we continue, I'd like to make a clarification of sorts. The mathematical properties above are using terminology specific to Fourier Transforms of continuous functions defined over infinite time and frequency.

$\begin{align} H(f) = \int_{t=-\infty}^{\infty} h(t) e^{2\pi ift} dt \end{align}$

Obviously we're working in a digital world, and we don't have the luxury of continuous signals to work with. In software, we're dealing with sampled data, which is where the Discrete Fourier Transform comes in.

$\begin{align} H_k = \sum_{j=0}^{N-1} h_j e^{2\pi ijk/N} \end{align}$

This is basically what Mike already gave you in code form in his last post on the topic, and I encourage you to take another look at his code to understand how it relates to this equation.

What's important is that you understand the Discrete Fourier Transform and Continuous Fourier Transforms are closely related, and have almost exactly the same mathematical properties as described above. For what we're discussing, you can safely ignore the "almost" part, and look to Wikipedia's definition for more discussion.

The Danielson-Lanczos lemma
Using a combination of the mathematical properties of the Fourier Transform above, Danielson and Lanczos discovered that you can rewrite a Discrete Fourier Transform of length N as a sum of two Discrete Fourier Transforms of length N/2: one from the even-numbered and one from the odd-numbered points of input.

This is their proof:

$\begin{align} H_k &= \sum_{j=0}^{N-1} e^{2\pi ijk/N} h_j \\ &= \sum_{j=0}^{N/2-1} e^{2\pi ik(2j)/N} h_{2j} + \sum_{j=1}^{N/2-1} e^{2\pi ik(2j+1)/N} h_{2j+1} \\ &= \sum_{j=0}^{N/2-1} e^{2\pi ikj/(N/2)} h_{2j} + W^k \sum_{j=0}^{N/2-1} e^{2\pi ikj/(N/2)} h_{2j+1} \\ &= H_k^e + W^k H_k^o \end{align}$

Here, $W^k = e^{2\pi i k/N}$ , and $H_k^{e}$ and $H_k^o$ are the even and odd terms of $H_k$ , respectively.

Again, it's not important to totally understand the above, or how they got from A to B. This is where I wave my hands and defer to the fact that the mathematical properties of the Discrete Fourier Transform have been used in the derivation.

The Fast Fourier Transform
The discovery by Danielson and Lanczos, combined with the fact that it can be applied recursively, is the basis of the Fast Fourier Transform. Breaking the problem down one more step, we will end up with a combination of $H_k^{ee}$ , $H_k^{eo}$ , $H_k^{oe}$ , and $H_k^{oo}$ .

If we stick with power-of-two inputs to the Fourier Transform, we will guarantee that the problem continues to decompose until we reach a fourier transform on one element. And, guess what? That's just a copy of the input value:

$\begin{align} H_k^{eeoeoe \dots eoe} = f_n && \text{for some value of } n \end{align}$

There is a way to derive the value of $n$ , but I'm choosing to wave my hands again.

Instead, I'm going to let recursion do the work for us. I vote for this option, to keep this post from exploding out of control. Also, get your hands on a copy of Numerical Recipes to really go deep.

(Fairly) Straightforward Implementation
I put together a compact implementation that demonstrates how this all works. It is based on the first optimization, because I think it's a good balance of readability with just a hint of cleverness. (I started out based on this resource, but massaged the implementation for clarity, and to closely match my math above.)

    static complex double *FFT_recurse( complex double *x, int N, int skip ) {
        complex double *X = (complex double*)malloc( sizeof(complex double) * N );
        complex double *O, *E;

        // We've hit the scalar case, and copy the input to the output.
        if ( N == 1 ) {
            X[0] = x[0];
            return X;
        }

        E = FFT_recurse( x, N/2, skip * 2 );
        O = FFT_recurse( x + skip, N/2, skip * 2 );

        for ( int k = 0; k < N / 2; k++ ) {
            O[k] = ( cexp( 2.0 * I * M_PI * k / N ) * O[k] );
        }

        // While E[k] and O[k] are of length N/2, and X[k] is of length N, E[k] and
        // O[k] are periodic in k with length N/2. See p.609 of Numerical Recipes
        // in C (3rd Ed, 2007). [CL]
        for ( int k = 0; k < N / 2; k++ ) {
            X[k] = E[k] + O[k];
            X[k + N/2] = E[k] + O[k];
        }

        free( O );
        free( E );

        return X;
    }

    complex double *FFT( complex double *x, int N ) {
        return FFT_recurse( x, N, 1 );
    }

It's really not that complicated, but the improvement in performance is immense. I put together some driver code and tossed it all up on my github account. Some simple timings revealed that a straightforward "math definition" of the algorithm took approximately 12.1s, and the FFT implementation above took a mere 0.1s. More than a 100x speed increase, and that's with a whole bunch of malloc()s and free()s strewn about!

In closing
I hope that this explanation was somewhat helpful in demystifying the Fast Fourier Transform and how it works. It's one of many examples of algorithms that exploit mathematics in order to gain an order-of-magnitude speedup.

Oh, and in case Mike didn't make it clear, you should never implement this yourself. Use the vDSP routines in Accelerate.framework!

Apple's performance team continues to push the limits of their FFT implementation year after year on all platforms. A combination of mathematicians, physicists, engineers, scientists, and assembly language wizards are working hard to ensure that Accelerate.framework is always running as fast, and power-efficient as possible.

I'm of the opinion that Apple's performance team is largely responsible for what makes the "cool stuff" on the iPhone possible. Think about live audio effects in Garage Band, video effects in iMovie, the processing in iPhoto, and so forth. All of that stuff is depending on Accelerate.framework in some capacity.

The next time you visit WWDC, make some time to stop by their lab with any performance questions you may have that relate to Accelerate.framework. They're really nice folks, and astoundingly smart, too!

Friday Q&A 2012-10-26: Fourier Transforms and FFTs

Mike Ash — Fri, 26 Oct 2012 13:25:00 GMT

Friday Q&A 2012-10-26: Fourier Transforms and FFTs

Last time around I discussed the basics of audio data, how to get it, and how to understand it. Today, I'm going to go into some detail about one of the fundamental tools for more complex audio analysis, the fourier transform, and the FFT algorithm that makes it practical to use on computers.

Theory
Humans largely experience audio in the frequency domain. If you plot the waveform of a guitar chord, it's a messy thing, yet we experience it as a combination of individual notes, or frequencies. Analyzing audio by frequencies is tremendously useful, not in the least because it matches up much better with how we experience sound. Computers generally consider audio to be a collection of individual samples, while people consider it to be a collection of individual frequencies. Going from individual samples to frequencies is, essentially, the Fourier transform.

Imagine that you have an audio waveform that you think has a 200Hz frequency component in it. However, you're not sure, and you don't know how loud it is. How can you check?

First, let's slow the audio down by a factor of 1000 so this 200Hz frequency is on a more human timescale. With that factor of 1000 slowdown, a 200Hz frequency is a waveform that goes up, down, and back to the starting point every five seconds. The frequency is now far too low to hear, but easy to see, and convenient to analyze. This is a bit like how computers deal with audio, since they're fast and can devote a lot of attention to every individual audio sample.

The mystery audio has a complex waveform which goes up and down in what seems like a nearly random fashion. But you suspect this 200Hz pattern, or a consistent up and down every five seconds, embedded in the rest of the action.

You could check for this by just tapping out a beat once every five seconds, and checking where the waveform is at each beat. If it's consistently up, even after you've done this for a couple of minutes, then there's clearly some consistent once-every-five-seconds signal in there.

There's a problem with this, though. The 200Hz frequency crosses zero on its way between the hills and valleys of the wave. What if your beat happens to line up with those zero crossings? You'll get nothing, even though the signal is present. You'd have to repeat this simple analysis several times to make sure you didn't end up out of phase with the signal.

It would be better to have a single analysis that works with any phase, and has no chance of consistently hitting zero crossings. You want something that lines up with this once-every-five-seconds period, but still operates constantly. In short, you want a circle.

Get the waveform going so you can see it. It's moving up, down, back up, etc. Now, imagine you stand up and start turning in place. Make one complete turn once every five seconds.

Now start walking. Adjust your speed to match the waveform at any particular moment. If the wave is high, walk forward quickly. If it's near zero, walk slowly. If it's at zero, stop. When it's below zero, walk backwards. And keep turning at a rate of one complete turn every five seconds.

If you keep this up for a couple of minutes, you'll end up with a solid analysis of the 200Hz signal, or lack thereof, in the audio you're analyzing. Because you're turning at a rate that exactly matches the frequency you're looking for, any audio at that frequency will consistently move you in a single direction. As you turn, the 200Hz wave will crest at exactly the same point around the turn each time, and you'll begin to wander away from where you started.

All the parts of the sound that aren't at 200Hz will move you around too, of course. But because they don't match the speed at which you turn, they end up getting spread out all along the circle, and the net result is to bring you back to the center. Only the 200Hz component will consistently move you away. How far away you get tells you how strong that component is. The direction you move in tells you where the wave started, or its phase.

Do this over and over again, and you can characterize the whole sound. For example, you might do this at 20Hz, 40Hz, 60Hz, 80Hz, 100Hz, etc., all the way up to 20,000Hz or so. At the end, you'll have completely mapped out the strength and phase of all of the frequency components of the sound. A sound can be thought of as a sum of various sine waves, or pure tones. Any sound, or indeed any signal at all, can be represented as a collection of sine waves with the right frequency and phase. By mapping out the frequencies in the sound, you build up the fundamental component sine waves it contains.

This map is the Fourier transform of the sound. You spin the sound around in a circle at different frequences and come up with all of its components, and get the Fourier transform. You've now gone from a collection of individual samples, which tell you very little, to a comprehensive map of the fundamental components of the audio, which tell you a lot. The Fourier transform is, essentially, what your ear does with incoming sound, and we fundamentally hear sound by frequencies, not samples, so it's a much better match for human perception.

You can also take the Fourier transform and reverse it to obtain the original audio. If you modify the transformed frequency components, that modification shows up in the original audio. This can be used to reduce or increase the volume of certain frequency components, or perform other interesting changes on the original audio.

The Fast Fourier Transform, or FFT, is pretty much what it implies. It's an algorithm for quickly computing the Fourier transform of a sequence of values. While FFT just refers to the algorithm, and Fourier transform is the actual result that it produces, FFT is often used pretty much interchangeably for both.

Basic Implementation
Let's build a basic Fourier transform. The fundamental operation is the rotation procedure I described above, so let's build a function to perform that:

    COMPLEX Rotate(float *buf, int samples, float hz, float rate)
    {

COMPLEX is a data type defined in Apple's vDSP library that simply has two components, real and imag. The output of a Fourier transform is actually a sequence of complex numbers, which correspond to the two-dimensional result of the rotation procedure. The Fourier transform is actually defined in terms of complex number exponents, which conceptually maps to rotation in two dimensions.

The goal is to add all of the various impulses together, so we want COMPLEX variable to serve as an accumulator:

        COMPLEX result = { 0, 0 };

Then loop over all of the samples:

        for(int i = 0; i < samples; i++)
        {

We want to rotate to make a complete circle once every rate / hz samples. The following line computes the appropriate angle (in radians) for the current sample:

            float angle = i * hz * 2 * M_PI / rate;

Now we use that angle to compute the step to take. This is simply the value of buf[i], rotated by angle, which is a simple bit of trigonometry:

            float real = buf[i] * cos(angle);
            float imag = buf[i] * sin(angle);

We then add that step into the accumulator, and continue with the loop:

            result.real += real;
            result.imag += imag;
        }

Once the loop is done, just return the accumulated result:

        return result;
    }

Note that, for reasons I don't fully understand, the results of this function are off by a factor of two and sometimes with inverted components compared to a reference FFT function's output. However, this still does fine in illustrating the principle and getting usable data out.

To perform a Fourier transform, we then just call Rotate repeatedly with different frequencies. Which frequencies? The lowest frequency the Fourier transform can extract (aside from zero) is equal to the sample rate divided by the number of samples, which is the frequency where one complete waveform can fit within the samples given. The transform produces samples / 2 bins of output, where each bin is a complex number. (Technically, it produces samples bins of output, but with real-valued input, the output is symmetric and half of it can be neglected.) The first bin (bin 0) corresponds to a frequency of 0Hz, also called the DC offset. The second bin corresponds to rate / samplesHz. The third bin corresponds to 2 * rate / samplesHz, and so on like that, with each bin's frequency equal to i * rate / samples.

Given that, here is a quick routine to compute the Fourier transform of a collection of samples:

    int samples = ...;
    float *buf = ...;

    COMPLEX result[samples / 2];
    for(int i = 0; i < samples / 2; i++)
        result[i] = Rotate(buf, samples, i * rate / samples, rate);

This is great code to play with and makes it a lot easier to understand what's happening when you generate a Fourier transform. However, it's impractical for any real use, as it's far too slow. For speed, we want an FFT implementation, and Apple has a good one.

vDSP FFT
Apple's vDSP provides optimized digital signal processing routines, including a full suite of FFT functions. For those wondering, "DSP" stands for digital signal processing, and the "v" stands for vector, indicating that it will use your CPU's vector unit whenever possible for best speed.

The FFT functions need some initial setup done which can be reused across multiple calls. To reduce overhead, you perform the setup separately, then use the resulting data as many times as you want before destroying it. The vDSP_create_fftsetup function handles this. It takes the maximum amount of data you want to work with, and a radix. The data is specified as a power of two, so to specify that you want to work with 1024 samples at a time, pass in 10. For the radix, pass kFFTRadix2. vDSP supports radix values of 3 and 5, which allows it to work with data whose length is a multiple of 3 or 5, but this is not generally useful. Powers of two are convenient in programming, so we'll stick with that. Here is the code to set up the vDSP FFT for 1024 samples:

    int bufferFrames = 1024;
    int bufferlog2 = round(log2(bufferFrames));
    FFTSetup fftSetup = vDSP_create_fftsetup(bufferlog2, kFFTRadix2);

Next, the input data has to be transformed into the arrangement that vDSP expects. The output is provided as two distinct arrays, one for the real parts and one for the imaginary parts. To keep things simple (for vDSP, not for us), the input is also split into two arrays, and the FFT performed in place. Here are the two arrays, plus a little structure to hold them:

    float outReal[bufferFrames / 2];
    float outImaginary[bufferFrames / 2];
    COMPLEX_SPLIT out = { .realp = outReal, .imagp = outImaginary };

The input buffer needs to be transformed so that all of the even-numbered elements go into outReal, and all of the odd-numbered elements go into outImaginary. vDSP provides a convenient function to do this for us:

    vDSP_ctoz((COMPLEX *)data, 2, &out, 1, bufferFrames / 2);

This function is intended to take an array of complex numbers as the input (thus the cast to COMPLEX *) and produce a split array of the output. By squinting and pretending that the input data is actually complex numbers, this accomplishes the even/odd split that we wanted.

Performing the FFT itself is actually pretty simple. Just call vDSP_fft_zrip, give it the fftSetup object, the array to work on, the stride (how many elements to move forward for each iteration, usually 1) the data length (as a power of two), and specify that you want a forward FFT:

    vDSP_fft_zrip(fftSetup, &out, 1, bufferlog2, FFT_FORWARD);

The same function can do both forward (from standard PCM audio to frequencies) and inverse (from frequencies back to raw audio) transforms, which is why this call has to specify FFT_FORWARD.

At this point, outReal and outImaginary contain the real and imaginary components of the FFT output. Their magnitude (sqrt(real * real + imag * imag)) tells you how much energy is in a particular frequency bin. Note that the magnitude can be quite high even when the input is restricted to a range of [-1, 1], since very pure tones will deposit all of their energy into a single bin.

Analyzing the magnitudes can produce for interesting visualizations. Since human hearing works similar to the FFT, the result corresponds much more with how we hear audio than a simple waveform generated from the PCM data.

The output has one odd feature. Index 0 in the output would normally contain the DC offset, which is always a pure real value with a zero imaginary component. Index bufferFrames / 2 contains the Nyquist frequency, which also is a pure real value with zero imaginary component. To save a bit of space, vDSP squashes these two together at index 0. outReal[0] contains the DC offset, and outImaginary[0] contains the Nyquist component.

The FFT output can be altered to, for example, reduce or increase the strength of certain frequencies. You can then transform the result back into raw audio data, which will reflect the alterations. The alterations are just a matter of twiddling around with outReal and outImaginary. For example, if you go through and set the first 1/4th of each array to0, you'll remove all of the low frequency components from the sound.

To reverse the transform, just call vDSP_fft_zrip again with FFT_INVERSE:

    vDSP_fft_zrip(fftSetup, &out, 1, bufferlog2, FFT_INVERSE);

Then de-interleave the data, using vDSP_ztoc which just does the opposite of the vDSP_ctoz call useb previously:

    float outData[bufferFrames];
    vDSP_ztoc(&out, 1, (COMPLEX *)outData, 2, bufferFrames / 2);

The result of this inverse transformation, for reasons I don't fully understand, comes out multiplied by a factor of bufferFrames * 2. This needs to be removed before treating the result as audio data, unless you like frightening everybody in the restaurant with the sudden blast of sound from your MacBook (ask me how I know this).

A simple for loop would do for this, but the cblas_sscal function will do it faster and nearly as easily. This function is found in Accelerate.framework, the umbrella framework which also contains vDSP and a bunch of other nifty functionality that I highly recommend you check out. This code simply multiplies every element in the output data by 1 / (bufferFrames * 2) to renormalize it:

    cblas_sscal(bufferFrames, 1.0 / (bufferFrames * 2), outData, 1);

At this point, outData now contains the audio that was originally in data, except with whatever modifications made to the FFT data in between.

Conclusion
Fourier transforms are a deep and complicated subject, and this article barely scratches the surface. The interpretation and modification of the resulting data can get about as complex as you care to go. Just performing and understanding the basics of an FFT can be tough, though, and I hope I've jumped you over that initial hurdle today.

It's time for everybody to go home now. But before you go, please don't forget to visit the suggestion box. Friday Q&A is driven by reader suggestions, in case you haven't already picked that up, so please let me know if you have an idea for a topic that you'd like to see covered in a future article.

Friday Q&A 2012-10-12: Obtaining and Interpreting Audio Data

Mike Ash — Fri, 12 Oct 2012 13:20:00 GMT

Friday Q&A 2012-10-12: Obtaining and Interpreting Audio Data

Continuing the multimedia data processing trend, today I'm switching over to audio. A reader known as Derek suggested a discussion on how to obtain and interpret audio data, which is what I'll cover today.

Theory
Before we even get to the question of how computers represent sound, we first need to have an idea of just what sound is, physically. Ultimately, sound is variation in pressure in a medium, usually air, over time.

That variation can be represented as a function of pressure over time. However, the variations are small. If the function represents absolute pressure, then the variations made by the sound are nearly indistinguishable. If you graphed the function, you'd just see a flat line.

Better, then, to represent the sound as a function of pressure over time relative to the normal, undisturbed pressure. The range of the function will vary a lot depending on many different factors, so while we're at it, let's just normalize it to be between -1 and 1. Do this, and you get a nice waveform, as can be seen in just about any audio editor.

Computers can't represent arbitrary continuous functions, so it has to be discretized somehow. Rather than try to represent every point on the function, the computer simply samples it occasionally. How frequently it gathers those samples is called the sample rate. The Nyquist sampling theorem says that a signal sampled at a given rate can represent frequencies up to one half that rate. For example, sampling sound at a rate of 44100 samples/second, or 44.1kHz, allows representing sounds with frequencies up to 22.05kHz, near the top end of the range of human hearing. Because of this, the 44.1kHz sample rate is probably the most common audio sample rate out there.

The value of each sample also has to be discretized, since computers can't represent arbitrary real numbers with infinite precision. Typically, each sample is stored as a signed, 16-bit integer, where the 16-bit integer range of [-32768, 32767] is mapped onto the conceptual sample range of [-1, 1]. For more fidelity, 24-bit values can be used, or for more compact storage, 8-bit values can be used.

Floating point is also a common format. This allows direct use of the normalized [1, -1] range, and good precision. Modern CPUs are fast with floating point, so performance is good, and the data is convenient to work with in code.

This system of representing audio using a series of samples taken at intervals is called pulse-code modulation, or PCM. "PCM" is often used to refer to this representation of "raw" audio, in contrast to various encodings like MP3 or AAC.

Probably the most common digital audio representation out there is 44.1kHz, 16-bit audio. This is what CDs hold, and most digital music files. 44.1kHz is enough to represent sounds up to the maximum frequency most people can hear, and 16 bits is generally granular enough to not produce audible noise or distortion, at least for most situations.

On Apple devices, 32-bit floats are the most common in-memory format for audio, since they can faithfully represent the full range of 24-bit integers, and are convenient to work with.

A Quick Note on Floating Point
Using a floating-point number to represent only values between -1 and 1 may sound wasteful. After all, a 32-bit float can represent values between -3.4×10³⁸ and 3.4×10³⁸. Audio uses only a tiny fraction of that range.

It turns out, however, that restricting the range to [-1, 1] only wastes one bit out of the 32 available. In effect, it's being used as a 31-bit number stored in 32 bits of memory, which doesn't sound so bad at all. This is because of how floating point numbers are stored.

The short version is that floats are represented in the form m×2^e, where m and e are stored in the number, along with one bit to indicate the sign. For a 32-bit float, the exponent (e) can range from -128 to 127. Values with exponents in the range [-128, -1] represent the range between -1 and 1. That range restriction simply cuts the exponent's range in half, which equates to restricting only a single bit from its value.

For more details on the floating-point representation, see my previous article on floating point arithmetic.

Stereo
You may have noticed that most people have two ears. Because of this, sound recorded as two separate streams sounds nicer to most people than a single stream. Conceptually, this audio can be thought of as two separate functions of pressure over time.

To represent stereo sound in data, those two functions have to be represented simultaneously. The most common way is to simply interleave the two channels, so that the first value in a buffer would be the left channel, the second value the right channel, then left again, etc. In memory, it would look like:

    LRLRLRLRLRLRLRLRLR

It's also possible to simply use two completely different buffers, which just looks like:

    buffer 1: LLLLLLLLLL
    buffer 2: RRRRRRRRRR

Deinterleaved data like this can be more convenient to work with, but the interleaved representation is more commonly used simply because it keeps everything in one place.

Obtaining Audio Data
There is no audio equivalent to Cocoa's NSImage class. The NSSound class may seem promising, but it's extremely limited and provides no way to extract the underlying audio data.

Instead, I'll drop down to Core Audio, which excels at this kind of thing. It's not the nicest API in the world, but it's entirely capable. I believe the newer AV Foundation APIs are also capable of extracting raw audio data, but for a basic task like this, Core Audio does just fine.

The Extended Audio File Services API does exactly this. Given a file, it produces the raw audio data contained within.

The first thing to do is to create an ExtAudioFileRef pointing at the file we're interested in. The ExtAudioFileOpenURL function takes a CFURLRef and creates an audio file object for it. It returns an error value, with the audio file object returned by reference in one of the parameters:

    NSURL *urlToFile = ...;
    ExtAudioFileRef af = NULL;
    OSStatus err = ExtAudioFileOpenURL((__bridge CFURLRef)urlToFile, &af);
    if(err != noErr)
        // Handle the error here

It's important to check errors! Code like this is really easy to mess up, and if you write code that ignores errors, it can add hours to your debugging for no good reason. Always check the error from any function that returns them.

The next step is to tell the audio file object what kind of in-memory format we want for the audio. This is done using an AudioStreamBasicDescription, or ASBD. This is a structure which contains fields for the sample rate, number of channels, etc. Here is an ASBD that asks for 44.1kHz, mono, PCM audio using float to store the samples:

    AudioStreamBasicDescription clientASBD = {
        .mSampleRate = 44100,
        .mFormatID = kAudioFormatLinearPCM,
        .mFormatFlags = kAudioFormatFlagsNativeFloatPacked,
        .mBitsPerChannel = sizeof(float) * CHAR_BIT,
        .mChannelsPerFrame = 1,
        .mFramesPerPacket = 1,
        .mBytesPerFrame = sizeof(float),
        .mBytesPerPacket = sizeof(float)
    };

This structure contains what appears to be redundant information, in the form of the channels and bytes per frame/packet. These fields exist for the benefit of non-PCM formats, and because the ASBD struct is used in many different situations. To understand the meaning of these fields, here are some quick definitions:

Sample: a single number representing the value of one audio channel at one point in time.
Frame: a group of one or more samples, with one sample for each channel, representing the audio on all channels at a single point on time.
Packet: a group of one or more frames, representing the audio format's smallest encoding unit, and the audio for all channels across a short amount of time.

Many audio formats use packets that are considerably longer than a single frame. MP3, for example, uses packets of 1152 frames, which are the basic atomic unit of an MP3 stream. PCM audio is just a series of samples, so it can be divided down to the individual frame, and it really has no packet size at all. For the ASBD's purpose, the packet size is equal to the frame size.

Note that the above definitions are a bit loose, and people often use these terms in different ways. However, these definitions are how Core Audio uses the words, which is what counts when we're writing code for that API!

With the structure filled out, the code uses it to tell the audio file object what kind of data we want:

    err = ExtAudioFileSetProperty(af, kExtAudioFileProperty_ClientDataFormat, sizeof(clientASBD), &clientASBD);
    if(err != noErr)
        // Handle the error

Once again, error handling is important. It's easy to build an ASBD that Core Audio doesn't like, and catching that error early will save a lot of pain.

You won't always want to specify every detail of the audio format like this. For many purposes, you'll want to use the sample rate of the data in the file rather than specifying one and having Core Audio resample the audio if necessary. Likewise, you'll often want to use the number of channels present in the file rather than simply requesting or forcing a certain number of channels. This can be done simply by calling ExtAudioFileGetProperty and getting the kExtAudioFileProperty_FileDataFormat property. This will return an ASBD describing the file's format, and the file's sample rate and number of channels can easily be extracted from that.

Reading
With the audio file object set up, it's time to start reading data from it.

Since audio data is a stream, and audio files can be huge, it's common to read from them only a piece at a time and move on, rather than trying to read the entire thing into memory at once. Audio data can be pretty big, especially once decoded into memory. A typical 1MB MP3 will decode to about 10MB in memory using the audio format specified in this code, and twice that for stereo.

To that end, we'll define a fixed-size buffer to read audio data into:

    int bufferFrames = 4096;
    float data[bufferFrames];

For multi-channel audio, the array size needs to be multiplied by the number of channels. We're just reading mono, though, so the array size is equal to the number of frames.

The function to actually read an audio file takes an AudioBufferList, which is just a structure of AudioBuffer structures. This code constructs an AudioBuffer for the above array, and an AudioBufferList containing a single entry for that buffer:

    AudioBuffer buffer = {
        .mNumberChannels = 1,
        .mDataByteSize = sizeof(data),
        .mData = data
    };

    AudioBufferList bufferList;
    bufferList.mNumberBuffers = 1;
    bufferList.mBuffers[0] = buffer;

With that in place, it's time to actually read the data. The read function takes an odd shortcut, where it takes a pointer to a number of frames to read, and then sets that variable to the number of frames actually read. It returns an error just like the rest of these functions:

    UInt32 ioFrames = bufferFrames; /* Request reading 4096 frames. */
    err = ExtAudioFileRead(af, &ioFrames, &bufferList);
    if(err != noErr)
        // Handle the error here

At this point, ioFrames contains the number of frames actually read. The data itself can be found in data[0], data[1], ..., data[ioFrames - 1].

To read the entire file, simply run the above in a loop until ioFrames comes out 0, signaling the end of the file.

Once you're done, don't forget to clean up the audio file object:

    if(af)
    {
        err = ExtAudioFileDispose(af);
        if(err != noErr)
            // How do you handle an error from a dispose function?
    }

Interpreting the Data
With the audio data in a buffer, the program can read elements out of the buffer to get audio samples. However, interpreting that data can get tricky. Unlike images, where a single pixel has meaning, a single audio sample has essentially no meaning on its own. Audio is fundamentally a result of change over time, so looking at a single sample of, say, 0.5 doesn't tell us anything. Contrast this with an image, where a single pixel with an RGB value of (255, 0, 0) tells us that this pixel is red, even if it doesn't tell us anything about the rest of the image.

Interpreting audio data can get extremely difficult, but we can at least cover some basics here.

The sample values are simply deviations from the center. If you wanted to render a visual representation of the waveform, for example, you could simply transform the sample values to vertical offsets from the centerline of your waveform view. There can be a lot more to it, but for the basic idea, you can simply generate (x, y) values like so:

    x = sampleNumber;
    y = data[sampleNumber] * viewHeight / 2 + viewHeight / 2;

It can be interesting and useful to figure out how loud a particular piece of audio is. Loudness is typically measured in decibels, which is a logarithmic scale. It's calculated using the base 10 logarithm of a ratio of the audio's power with a reference power level. The pure logarithm produces a value in bels, and to obtain decibels, simply multiply that number by 10. The power level of a piece of audio is proportional to the square of the amplitude, and the amplitude is exactly what the individual audio samples describe.

To compute the total power level of a piece of audio, simply average the squares of all the samples:

    float accumulator = 0;
    for(int i = 0; i < frames; i++)
        accumulator += data[i] * data[i];
    float power = accumulator / frames;

For computer audio, the reference power level is typically 1.0, which is the loudest possible. To compute decibels, take the base-10 logarithm of the computed power divided by the reference power then multiply the result by 10. Dividing by 1.0 does nothing, so it's ommitted from the calculation:

    float decibels = 10 * log10f(power);

Mathematically astute readers will notice that squaring the amplitude when calculating the power is equivalent so simply calculating 20 * log10f(averageAmplitude), which can simply things slightly. However, don't forget to take the absolute value of the amplitudes when calculating the averages, because otherwise the samples are likely to cancel each other out.

The resulting decibel value is negative, which may be confusing if you're used to seeing decibels written as a positive value. It's important to understand that decibels are a relative measure, and need some sort of reference power or amplitude to be meaningful. When audible sound levels are expressed in decibels, the reference level is a standard number which is roughly the quietest sound that a normal human can hear. If a sound is described as 10dB, that means that it's 10 times more powerful than the quietest perceptible sound. 20dB means that it's 100 times more powerful, etc.

For computer audio, the maximum possible output power is typically used as the reference level, because there is no meaningful minimum level to compare with. An audio file filled with zeros has zero output power, and attempting to compute a ratio with that would divide by zero. The result is that, when talking about computer audio, 0dB is the maximum level possible, and negative values are quieter. If audio is described as being at a level of -30dB, that means that it's 1000 times less powerful than this reference maximum value.

To adjust the volume of audio, simply multiply each sample by a fixed gain. The gain can be calculated from a desired change in decibels by reversing the formula above. For example, to achieve a volume increase of 30dB, multiply the power by 1000, which is equivalent to a gain of sqrt(1000):

    float decibelsAdjust = ...;
    float gain = pow(10, decibelsAdjust / 20);
    for(int i = 0; i < frames; i++)
        data[i] *= gain;

Note that this works equally well for negative values, which cause a decrease in volume by the specified number of decibels.

Writing Audio Out
You've done a volume adjustment or maybe some other manipulation to the audio data, and you want to get audio back out of your program. The ExtAudioFile APIs make this easy.

The first thing to do is to create a new audio file and a new audio file object all at once. This is done by calling ExtAudioFileCreateWithURL:

        ExtAudioFileRef outAF = NULL;
        err = ExtAudioFileCreateWithURL((__bridge CFURLRef)outURL, kAudioFileCAFType, &clientASBD, NULL, kAudioFileFlags_EraseFile, &outAF);
        if(err != noErr)
            // You should know what to do here by now

This function takes several more parameters than ExtAudioFileOpenURL. The first parameter is a URL to the file to create. The second one is the file type to create. ExtAudioFile supports many different formats. I chose CAF, as it's a simple format that stores raw PCM samples with a minimum of fuss, and was designed specifically to be nice to use with Core Audio.

The third parameter is the format that will be used for audio within the file. By default, it's also used as the in-memory audio format. For convenience, I'm using the same format as the in-memory format specified earlier. In more realistic situations, you'd likely want to specify an in-file format that's more compact or useful (e.g. 16-bit integer), then use the kExtAudioFileProperty_ClientDataFormat property to specify the in-memory format, just as we did when reading.

The fourth parameter is an audio channel layout struct, which is optional and only needed for more advanced uses. For this, I leave it NULl.

The fifth parameter tells the system what to do if the file already exists. I want it to erase any existing file and make a new one, so I pass kAudioFileFlags_EraseFile. The last parameter is a pointer to where the newly created audio file object will be stored.

Writing audio to this file is almost exactly the same as reading it. You need a buffer of data, an AudioBuffer struct, and an AudioBufferList. Then simply call ExtAudioFileWrite:

    err = ExtAudioFileWrite(outAF, ioFrames, &bufferList);
    if(err != noErr)
        // Guess what

If you stick this into the same loop as the audio reading code from above, you'll get a program that creates a new CAF audio file using the contents from an existing audio file. If you modify the contents of the data buffer before writing, the new audio file will contain your modified contents.

Conclusion
The world of audio can be strange and mysterious, but the basics are pretty simple. The ExtAudioFile APIs make it easy, relatively speaking, to get at the audio data of a file. That audio data is represented as a series of samples in memory between -1 and 1. If you want to make changes and build a new file, ExtAudioFile makes it easy to write the new audio back out to disk.

That's it for today. You probably know by now that Friday Q&A is driven by reader submissions, so as always, please send in your ideas for topics if you have a subject you'd like to see covered here.

Friday Q&A 2012-09-28: Optimizing Flood Fill

Mike Ash — Fri, 28 Sep 2012 13:17:00 GMT

Friday Q&A 2012-09-28: Optimizing Flood Fill

Last time, I presented the implementation of a basic flood fill. That implementation works fine, but is not terribly fast. Today, I'm going to walk through various optimizations that can be done to make it faster, using techniques which I hope will be useful in many different situations. Ultimately, starting from the original code, I was able to achieve over an order of magnitude speedup while still keeping the code relatively straightforward and clear.

Measurement
A prerequisite for any optimization work is the ability to measure the code in question. In this case, we're optimizing for speed, so we have to measure how fast the code is. If you can't measure it, it's nearly impossible to make it faster, because you have only a vague idea how much difference any given change makes, or whether it's even an improvement at all. Lots of seemingly-obvious optimizations can end up making code slower, so it's important to have real data.

If at all possible, it's best to have a consistent scenario that you can run in an automated fashion. If you can simply push a button and get a number out that says how fast the code is, that's ideal. Anything that requires manual setup will add a lot of work. Anything that requires manual inputs to the process is begging for trouble: if your inputs vary from one run to the next, you can't tell what changes are due to your code and what changes are due to your changing inputs! This can be important for UI-heavy code where the user's specific actions can heavily influence how much code runs and when it runs. Whenever possible, isolate the code in question away from the user and pass it pre-baked input.

For the flood fill, we need an image to fill. I wrote a quick method that creates a NSBitmapImageRep using NSGraphicsContext to draw into it, building a square covering most of the image, with some diagonal lines to ensure that the flood fill has something interesting to work on. Here's the code for that:

    NSBitmapImageRep *TestImageRep(int width, int height)
    {
        NSBitmapImageRep *rep = [[NSBitmapImageRep alloc]
                                 initWithBitmapDataPlanes: NULL
                                 pixelsWide: width
                                 pixelsHigh: height
                                 bitsPerSample: 8
                                 samplesPerPixel: 4
                                 hasAlpha: YES
                                 isPlanar: NO
                                 colorSpaceName: NSCalibratedRGBColorSpace
                                 bytesPerRow: width * 4
                                 bitsPerPixel: 32];

        NSGraphicsContext *ctx = [NSGraphicsContext graphicsContextWithBitmapImageRep: rep];

        [NSGraphicsContext saveGraphicsState];
        [NSGraphicsContext setCurrentContext: ctx];

        NSRect r;

        [[NSColor whiteColor] setFill];
        r = NSMakeRect(0, 0, width, height);
        NSRectFill(r);

        [[NSColor blackColor] setFill];
        r = NSMakeRect(width / 8, height / 8, width * 3 / 4, height * 3 / 4);
        NSRectFill(r);

        [[NSColor greenColor] setStroke];
        for(int i = 0; i < 4; i++)
        {
            NSPoint p1 = NSMakePoint(width * (i + 1) / 5, height / 5);
            NSPoint p2 = NSMakePoint(width / 5, height * (i + 1) / 5);
            [NSBezierPath strokeLineFromPoint: p1 toPoint: p2];
        }

        [ctx flushGraphics];
        [NSGraphicsContext restoreGraphicsState];

        return rep;
    }

This function can then be used to create the image that each flood fill test will operate on, to make each test totally consistent. The dimensions are left up to the caller here, and I decided to test on images of 10000 pixels square, which is hefty enough for the operation to take a substantial amount of time, but still fast enough to make for a decent testing cycle.

For the measurement itself, I wrote a function that takes a block, runs it several times, and measures how fast it runs. It's not generally a good idea to only run the code once, because transient events can strongly influence how long a particular run takes. For example, a background process might suddenly allocate a bunch of memory, causing your process's memory to be swapped out to disk, then back in again, making it run much slower than usual. Running several times helps even out these transients.

The next question is, how do you distill the results from all of the runs into a single number you can compare? The most obvious way is to simply take an average, but this isn't necessarily appropriate. For computation-heavy code like this, there are a lot of random events that could pop up to make it run slower than usual, but essentially nothing could happen to make it run faster than usual.

Given that, the obvious choice is to use the fastest run out of all the trials. However, having an ingrained distrust of outliers, I opeted for the second-fastest run instead. It should provide essentially the same result.

Here's the function I wrote to do the test. It takes a name and a block and runs the block ten times. It measures each invocation's running time, and tracks all of the running times. Once all of the runs are complete, it grabs the second-best time out of the array and returns it to the caller:

    NSArray *Time(NSString *name, void (^block)(void))
    {
        NSMutableArray *times = [NSMutableArray array];
        int trials = 10;
        for(int i = 0; i < trials; i++)
        {
            @autoreleasepool
            {
                NSLog(@"Running trial %d of %d", i + 1, trials);
                NSTimeInterval start = [[NSProcessInfo processInfo] systemUptime];
                block();
                NSTimeInterval end = [[NSProcessInfo processInfo] systemUptime];
                NSLog(@"Done, total elapsed time is %f seconds", end - start);
                [times addObject: @(end - start)];
            }
        }
        NSArray *sortedTimes = [times sortedArrayUsingSelector: @selector(compare:)];
        NSTimeInterval secondBest = [sortedTimes[1] doubleValue];
        NSLog(@"%@: Second best time is %f, times are %@", name, secondBest, sortedTimes);

        return @[name, @(secondBest)];
    }

It also returns the name to the caller, purely to make it easier on the caller when aggregating the results.

With the testing infrastructure in place, we can measure the performance of the original FloodFill function. The result on my computer is roughly 26.2 seconds. Tolerable, for such a gigantic image, but not great.

Setting a Lower Bound
I decided to write a simple fill routine to set a bound on the speed of the flood fill function. It simply scans every pixel of the image and fills the pixel if it's within the threshold from the starting pixel. It will fill areas that are not contiguous with the starting pixel, so it's not useful as a flood fill. However, it's fast, and since it touches every pixel in the image, it gives a pretty decent lower bound. Since the flood fill area in the test image covers most of it, it's unlikely that any flood fill could ever surpass the speed of this dumb whole-image scan:

    void CheckAll(struct Pixel *image, int width, int height, int startx, int starty, struct Pixel fillValue, int threshold)
    {
        struct Pixel startPixel = PIXEL(startx, starty);

        for(int i = 0; i < width * height; i++)
        {
            int diff = PixelDiff(startPixel, image[i]);
            if(diff <= threshold)
                image[i] = fillValue;
        }
    }

Running this through the tester gives a run time of 0.5 seconds. Clearly, there's substantial room for improvement over the 26.2 second running time of the original flood fill.

Profiling
Measuring the running time of the function is important to optimization, but to actually perform useful optimizations we need more specific data. We need to profile the code to see where the time is being spent. Although the much-beloved Shark is dead, Instruments is a decent substitute. In particular, the Time Profiler instrument provides far and away the best view of just where code is spending its time.

The Time Profiler instrument produces a call tree. Expanding it out, it shows each function under the "Symbol Name" column, and the amount and percentage of time spent in that function under the "Running Time" column.

To get more detail, you can double-click any function, and it will display that function's code and a percentage of time spent on each line. This is extremely useful when you have a slow function that's complex enough that you don't know exactly which part is slow.

Pixels Visited Bitmap
Profiling the original flood fill function, the main source of slowness is immediately obvious. A huge amount of time is spent checking for membership in NSIndexSet and adding new indexes to the set. There are two NSIndexSets in play here, but it seems fairly clear that the worst offender is the pixelsSeen set, which tracks the pixels that have already been seen and shouldn't be checked again. Over a quarter of the function's running time is spent in containsIndex:, which is only sent to pixelsSeen. The first order of business is to replace pixelsSeen with something faster.

This variable basically stores a single bit of information per pixel, namely whether that pixel has been visited or not. A natural way to store this information is with a bitmap. Essentially, make a new image with one bit per pixel that corresponds exactly to the image being filled. To mark a pixel as visited, set the bit to 1. To test a pixel, just grab the corresponding bit.

C doesn't offerd bit-addressed arrays, but no matter. We can use an array of bytes, and do some bit twiddling to get at the individual bits. For a given index, the byte to access is just index / 8, and the bit is just index % 8. I used the CHAR_BIT macro to be clean, even though the odds of running this code on a system where CHAR_BIT != 8 are only marginally better than the odds of winning the lottery while being simultaneously struck by lightning and being eaten by a shark.

With the byte and bit index, a bit of bitshifting and a bitwise or allows setting a bit within the bitmap:

    static inline void AddToBitmap(int x, int y, uint8_t *bitmap, int width)
    {
        int index = x + y * width;
        int bytes = index / CHAR_BIT;
        int bits = index % CHAR_BIT;
        uint8_t bit = 1 << bits;
        bitmap[bytes] |= bit;
    }

Similarly, a bitwise and allows checking whether the bit is set:

    static inline BOOL CheckBitmap(int x, int y, uint8_t *bitmap, int width)
    {
        int index = x + y * width;
        int bytes = index / CHAR_BIT;
        int bits = index % CHAR_BIT;
        uint8_t bit = 1 << bits;
        return bitmap[bytes] & bit ? YES : NO;
    }

The flood fill function must then allocate the bitmap when it starts up. It has to allocate a chunk of memory whose size is equal to the number of pixels in the image divided by eight, rounded up. This bit of code handles that:

    int length = width * height;
    int bytes = (length + CHAR_BIT - 1) / CHAR_BIT;
    uint8_t *pixelsSeen = calloc(1, bytes);

The uses of pixelsSeen then get replaced with calls to AddToBitmap and CheckBitmap. Finally, we free the bitmap at the end of the function:

    free(pixelsSeen);

Running the new version, the running time for the flood fill is down to 12.6 seconds. This one change made things over twice as fast!

Pixel Queue
Profiling the new code shows that NSIndexSet is once again taking up most of the time. The pixelsToExamine variable is the only NSIndexSet remaining, so it clearly must be the culprit. NSIndexSet is fast enough to be acceptable here, but it's clearly not optimized for this particular use. This is only to be expected, since this is definitely not the use it was built for.

I'll replace the NSIndexSet with a simple stack of coordinates. This will be a big array and an index indicating the top of the array. Adding a coordinate will mean simply setting the element at the top of the array and incrementing the index. Retrieving the next coordinate to examine is simply a matter of decrementing the index and grabbing the value at the top of the array. Allocating enough memory to hold a coordinate for every pixel is impractical, so instead I'll dynamically increase the size of the array when required.

First, I make a variable to hold the current array length. This lets the code know when it hits the end of the array and needs to reallocate:

    int pixelsToExamineLength = 128;

I chose 128 simply because it's a decent middle size, and the number sounded nice. The exact number is probably not too important, as long as it's not 0 and not so large that it consumes an excessive amount of memory for no reason.

Next, I make a simple Coordinate structure, a variable to point to the array of coordinates, and allocate memory for it:

    struct Coordinate { int x, y; };
    struct Coordinate *pixelsToExamine = malloc(sizeof(*pixelsToExamine) * pixelsToExamineLength);

Then, there's a variable to hold the index of the current top of the stack:

    int pixelsToExamineIndex = 0;

Finally, the starting pixel is added to the stack:

    pixelsToExamine[pixelsToExamineIndex++] = (struct Coordinate){ startx, starty };

The top of the loop now examines and pulls from the array:

    while(pixelsToExamineIndex > 0)
    {
        struct Coordinate coordinate = pixelsToExamine[--pixelsToExamineIndex];

        int x = coordinate.x;
        int y = coordinate.y;

When adding a new coordinate to the array, it first checks the index to see if the array is full and needs to be reallocated. If it's full, it just doubles the length and calls realloc to allocate more memory:

    if(pixelsToExamineIndex >= pixelsToExamineLength)
    {
        pixelsToExamineLength *= 2;
        pixelsToExamine = realloc(pixelsToExamine, sizeof(*pixelsToExamine) * pixelsToExamineLength);
    }

Once enough memory is available, it simply stores the desired coordinate into the top of the array and increments the index:

    pixelsToExamine[pixelsToExamineIndex++] = (struct Coordinate){ nextX, nextY };

Don't forget to deallocate the memory at the end of the function:

    free(pixelsToExamine);

How did we do? Running this new flood fill function takes about 4.8 seconds, once again more than doubling the performance of the code. We're doing very well compared to the original time of 26.2 seconds, but more performance can be extracted.

Linear Memory Access
Profiling this latest version now shows basically all of the run time is spent within the flood fill function itself. This is only to be expected, as it hardly makes any external calls at this point. Aside from very occasionally allocating or deallocating memory, it spends all of its time working internally. At this point, it's time to take advantage of Time Profiler's ability to examine the code within a function and see what the remaining bottlenecks are.

Double-clicking on the flood fill function in Instruments pulls up the source code and shows the time spent on each line. The line taking up the most time by far is the body of ComponentDiff, which is just:

    return MAX(a, b) - MIN(a, b);

Clearly there isn't much that can be done to speed this up. This is already as fast as it can get. The only other way to speed this up would be to simply call it less, but ComponentDiff has to run at least three times on every pixel examined (once per component), and the current code only runs it three times per pixel. This code is now as fast as it can possibly go, right?

Right?

Obviously the answer is "no", otherwise you'd be at the end of the article now. However, the way forward from here is deeply non-obvious and took me a long time to figure out.

I had some false starts trying to make the ComponentDiff function faster. Was there a way to make MIN and MAX faster? Could the subtraction be vectorized, so that all three components run at once?

It turned out that this was all completely wrong-headed, and the answer lies in a completely different direction.

RAM, despite being officially "random access", isn't truly random access these days. Modern computer memory is a complex hierarchical system which is optimized for common access patterns. Truly random access is quite slow compared to linearly reading or writing a long, contiguous chunk of memory.

When it comes to manipulating an image, this means that you always want to write code that iterates over x in the inner loop, like so:

    for(int y = 0; y < height; y++)
        for(int x = 0; x < width; x++)
            // Do something with pixel (x, y)

Since images are normally laid out in memory by rows, this code iterates over memory in a completely linear fashion, which is really fast. Writing the loops in a more conventional order ends up being substantially slower:

    for(int x = 0; x < width; x++)
        for(int y = 0; y < height; y++)
            // Do something with pixel (x, y)

This code jumps around a lot. For a 32-bit image that's 1024 pixels wide, this code will read the first pixel, then read a second pixel that's 4kB away in memory. The third pixel will be another 4kB down, etc. This scattered memory access is really slow.

Flood fill is not quite the simple systematic iteration of the above for loops, but it's ultimately similar. It iterates over a potentially large number of contiguous pixels, and the order in which it iterates will affect just how quickly the computer's memory is able to return pixels.

The massive amount of time spent in ComponentDiff is suspicious. It's a pretty simple operation, and there's a lot of other code running, so why is this one operation taking up half of the total run time? With the performance characteristics of modern RAM in mind, maybe the calculations themselves aren't taking up all of this time. Instead, it might just be that the calculations are spending a lot of time waiting for the data to be loaded from RAM.

Let's look at the access patterns of the flood fill function to see if this is really it, and whether it can be improved. The latest flood fill function uses a stack to store which pixels to examine. A stack operates in a last-in, first-out manner, where things come off the stack in the opposite order that they were put in. The last thing placed on the stack is the first thing to be retrieved. When a pixel adds adjacent pixels to the stack, those adjacent pixels will be the next ones to be examined. This contiguous access is what we want.

The big question is then: does it access rows before columns, or columns before rows? Here's the code that enqueues the new pixels to examine:

    int nextXs[4] = { x + 1, x - 1, x, x };
    int nextYs[4] = { y, y, y + 1, y - 1 };
    for(int i = 0; i < 4; i++)
    {
        int nextX = nextXs[i];
        int nextY = nextYs[i];
        // enqueue...

Remember, these pixels are popped off the stack in last-in, first-out order. The first pixel examined will be (x, y - 1), which is the pixel above the current pixel. That pixel will do its own thing and enqueue the one above it, and so on until the entire column is filled above. After the flood fill runs in that direction, it'll run downward, then finally go left and lastly right. This is pretty much the opposite of what we need for good performance.

This is really easy to fix, though: just reverse the arrays!

    int nextXs[4] = { x, x, x - 1, x + 1 };
    int nextYs[4] = { y - 1, y + 1, y, y };

With only this change, the flood fill function drops from 4.8 seconds to 2.9 seconds. This really shows the value of good memory access patterns!

Linear Memory Access, Part Two
Although the last optimization almost looked impossible, it's still worth running the profiler again to see if the change exposed any new bottlenecks. ComponentDiff is under 10% in the new profile, showing just how much of a difference the memory access pattern makes to memory-intensive code like this.

There are two noticeable hotspots with the latest flood fill function. One is the pixelsSeen bitmap, which manifests in a lot of time spent in AddToBitmap and CheckBitmap.

The access pattern for pixelsSeen is different from the access pattern for the image's pixels itself. Because it gets checked and set when enqueueing rather than when dequeueing, all four of a pixel's neighbors get checked, and potentially set, immediately. The pixels on the same row are fine, but the pixels above and below are far away in memory. It's exactly the sort of non-local memory access that the previous optimization tries to avoid in the image, although on a much smaller scale, since the pixels in pixelsSeen are only one bit instead of 32 bits.

Still, it appears to be worth attacking. My strategy is to change the Coordinate struct into a Command struct which will hold not only an (x, y) pair, but also a command to execute on that pair. There will be two commands. The EXAMINE command will do the same thing that the flood fill algorithm currently does: test the pixel's color and fill it and enqueue new pixels if it matches. The ENQUEUE_VERTICALS will point at the original pixel, and will enqueue the pixels above and below as part of a second pass.

This accesses the pixelsSeen bitmap much more nicely. It will simply scan left and right of the current pixel. After the stack gets popped back down to this pixel, only then will it scan above and below. By this time, those are likely to be filled, so it will just be a quick check and then done. The next command will likely be the command to scan above and below a horizontally adjacent pixel, making for nice linear accesses once again.

To actually implement this, we first need to define the commands, which I simply wrote as enums:

    enum {
        EXAMINE,
        ENQUEUE_VERTICALS
    };

Next, Coordinate and pixelsToExamine need to change to incorporate a new field to hold the command:

    struct Command { int command; int x, y; };
    struct Command *pixelsToExamine = malloc(sizeof(*pixelsToExamine) * pixelsToExamineLength);

I'm now going to be enqueueing pixels in three places, and enqueueing two different commands. To cut back on duplicated code, I wrote a macro to handle enqueueing a command:

    #define ENQUEUE(...) do { \
            if(pixelsToExamineIndex >= pixelsToExamineLength) \
            { \
                pixelsToExamineLength *= 2; \
                pixelsToExamine = realloc(pixelsToExamine, sizeof(*pixelsToExamine) * pixelsToExamineLength); \
            } \
            pixelsToExamine[pixelsToExamineIndex++] = (__VA_ARGS__); \
        } while(0)

Note the use of ..., which allows the macro to accept a C99 compound literal, like:

    ENQUEUE((struct Command){ command, x, y });

The C preprocessor isn't wise to the ways of compound literals, so it sees that as three separate parameters, separated by the commas.

The most common scenario will be enqueueing a pixel to examine, so I wrote a macro for that as well. This macro checks the pixel's coordinates to make sure they're within the image's bounds, and also checks the pixelsSeen bitmap, then uses ENQUEUE to add a new EXAMINE command if everything is good:

    #define ENQUEUE_PIXEL(x, y) do { \
            if((x) >= 0 && (y) >= 0 && (x) < width && (y) < height) \
                if(!CheckBitmap(x, y, pixelsSeen, width)) \
                    ENQUEUE((struct Command){ EXAMINE, (x), (y) }); \
        } while(0)

Now we have to change the rest of the function to use these commands.

The first change is when enqueueing the starting pixel. This now becomes:

    ENQUEUE((struct Command){ EXAMINE, startx, starty });

I'm not using ENQUEUE_PIXEL because I don't want all of the extra checking it does for this one, although it wouldn't really hurt.

The loop starts off pretty much the same, popping the command off the top of the stack:

    while(pixelsToExamineIndex > 0)
    {
        struct Command command = pixelsToExamine[--pixelsToExamineIndex];
        int x = command.x;
        int y = command.y;

At this point, it examines the actual command and branches. If it's EXAMINE, then the code is much like before. It adds the pixel to pixelsSeen, checks PixelDiff against threshold, and fills:

        if(command.command == EXAMINE)
        {
            AddToBitmap(x, y, pixelsSeen, width);

            int diff = PixelDiff(startPixel, PIXEL(x, y));
            if(diff <= threshold)
            {
                PIXEL(x, y) = fillValue;

At this point, the old code would enqueue the four adjacent pixels. Instead, we'll enqueue the two horizontally adjacent pixels, and one ENQUEUE_VERTICALS command for the current pixel. We do them backwards, since the stack is last-in, first-out:

                ENQUEUE((struct Command){ ENQUEUE_VERTICALS, x, y });
                ENQUEUE_PIXEL(x - 1, y);
                ENQUEUE_PIXEL(x + 1, y);
            }
        }

The code for an ENQUEUE_VERTICALS command is simple: just enqueue the pixels above and below:

        else if(command.command == ENQUEUE_VERTICALS)
        {
            ENQUEUE_PIXEL(x, y - 1);
            ENQUEUE_PIXEL(x, y + 1);
        }
    }

How does this optimization do? The previous version took 2.9 seconds, and this version takes only 1.9 seconds. Not too bad for the second revision after what appeared to be an impasse.

At this point, we've started to hit diminishing returns. The final flood fill function is about 14 times faster than the original, plenty to brag about.

For those having trouble keeping track of all the changes made to the function throughout this article, here's a full listing of the final version of it:

    void FloodFill(struct Pixel *image, int width, int height, int startx, int starty, struct Pixel fillValue, int threshold)
    {
    #define PIXEL_TO_INDEX(x, y) ((x) + (y) * width)
    #define PIXEL(x, y) image[PIXEL_TO_INDEX(x, y)]

        enum {
            EXAMINE,
            ENQUEUE_VERTICALS
        };

        int length = width * height;
        int bytes = (length + CHAR_BIT - 1) / CHAR_BIT;
        uint8_t *pixelsSeen = calloc(1, bytes);

        int pixelsToExamineLength = 128;
        struct Command { int command; int x, y; };
        struct Command *pixelsToExamine = malloc(sizeof(*pixelsToExamine) * pixelsToExamineLength);
        int pixelsToExamineIndex = 0;
    #define ENQUEUE(...) do { \
            if(pixelsToExamineIndex >= pixelsToExamineLength) \
            { \
                pixelsToExamineLength *= 2; \
                pixelsToExamine = realloc(pixelsToExamine, sizeof(*pixelsToExamine) * pixelsToExamineLength); \
            } \
            pixelsToExamine[pixelsToExamineIndex++] = (__VA_ARGS__); \
        } while(0)

    #define ENQUEUE_PIXEL(x, y) do { \
            if((x) >= 0 && (y) >= 0 && (x) < width && (y) < height) \
                if(!CheckBitmap(x, y, pixelsSeen, width)) \
                    ENQUEUE((struct Command){ EXAMINE, (x), (y) }); \
        } while(0)

        ENQUEUE((struct Command){ EXAMINE, startx, starty });
        struct Pixel startPixel = PIXEL(startx, starty);

        while(pixelsToExamineIndex > 0)
        {
            struct Command command = pixelsToExamine[--pixelsToExamineIndex];
            int x = command.x;
            int y = command.y;

            if(command.command == EXAMINE)
            {
                AddToBitmap(x, y, pixelsSeen, width);

                int diff = PixelDiff(startPixel, PIXEL(x, y));
                if(diff <= threshold)
                {
                    PIXEL(x, y) = fillValue;

                    ENQUEUE((struct Command){ ENQUEUE_VERTICALS, x, y });
                    ENQUEUE_PIXEL(x - 1, y);
                    ENQUEUE_PIXEL(x + 1, y);
                }
            }
            else if(command.command == ENQUEUE_VERTICALS)
            {
                ENQUEUE_PIXEL(x, y - 1);
                ENQUEUE_PIXEL(x, y + 1);
            }
        }

        free(pixelsSeen);
        free(pixelsToExamine);
    #undef ENQUEUE
    #undef ENQUEUE_PIXEL
    }

Conclusion
Effective optimization requires good measurements and careful thoughts. Appropriate data structures and algorithms are key, and should always be the first place you look when you need to optimize a routine. In this case, NSIndexSet ended up being a pretty slow choice for pixel membership tests and queueing, and more appropriate, specialized solutions were much faster. When operating on large amounts of data, pay close attention to your memory access patterns. Linear memory access will be far faster than scattered access.

Micro-optimizations should always be the choice of last resort. We could have spent ages trying to apply micro-optimizations to ComponentDiff and never made any sort of measurable difference, while simply rearranging the order in which pixels were visited sped up the function by over 60%.

Finally, be sure to only optimize when necessary, and what's necessary. Don't waste time optimizing code that doesn't take up a significant amount of time in the first place. Measure first, identify bottlenecks, and only then see if they might be worth improving.

This flood fill function can probably be optimized further, although the easiest speed improvements are long gone by now. Profiling reveals the various ENQUEUE operations to be the bottleneck in the latest version. It should be possible to improve the speed of the queue by packing values more efficiently, being smarter about the checks that are performed, etc. An algorithmic overhaul to work in terms of scanline segments rather than individual pixels is probably the best hope for gaining more speed. Most flood fill operations will have rows of many contiguous pixels, and representing the entire row as a (startx, endx, y) tuple could make for a major speed win. This is known as a scanline flood fill.

One thing that stood out at me when looking at this last version of the flood fill was that AddToBitmap is only called after a pixel is dequeued. This seems wasteful, as the same pixel could accumulate multiple entries in the command queue, which will then be wasted. This can be avoided by calling AddToBitmap when enqueueing a new pixel instead of when dequeueing. However, in practice, this resulted in no measurable change in performance. I didn't look to hard to figure out why, but this is a good lesson in why measurement is essential for this kind of work.

That's it for today. Come back next time for the next wacky adventure. Friday Q&A is driven by reader suggestions as always, so if you have any suggestions for topics you'd like to see, please send them in!