mikeash.com pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html comments

robert engels - 2024-09-10 22:02:38

Tue, 10 Sep 2024 22:02:38 GMT

awesome post. really great reverse engineering work and write-up.

Sam - 2020-09-06 22:00:34

Sun, 06 Sep 2020 22:00:34 GMT

As of macOS 10.15 (WWDC2019 #210), NSColor is now a tagged value, too!

mikeash - 2020-06-20 20:22:22

Sat, 20 Jun 2020 20:22:22 GMT

There isn't a whole lot to say about that, it's just a random value XORed into every tagged pointer to make it harder for an attacker with a memory write primitive to forge specific tagged values.

Kentzo - 2020-06-09 15:21:13

Tue, 09 Jun 2020 15:21:13 GMT

Would love to see an update to this article that would explain objc_debug_taggedpointer_obfuscator

Rob Mayoff - 2018-10-11 17:41:33

Thu, 11 Oct 2018 17:41:33 GMT

I just discovered that lldb also implements tagged pointer string decoding in its lldb_private::formatters::NSTaggedString_SummaryProvider function.

https://github.com/llvm-mirror/lldb/blob/master/source/Plugins/Language/ObjC/NSString.cpp#L338

mikeash - 2017-11-06 19:13:06

Mon, 06 Nov 2017 19:13:06 GMT

Ben H.: Interesting problem. I think I would favor what you say at the end, that you were always doing it wrong and it's just finally manifesting. Even in the absence of tagged pointers, nothing says Apple couldn't intern string objects behind the scenes.

Object equality is still perfectly safe, but I think the problem boils down to it meaning something a bit different from what you (and probably many other people) think it does. Pointer equality just checks: "Are these literally the exact same object in memory?" It sounds like you're using it to answer the question: "Were these created in different places?" There questions always had the same answer for a long time, but nothing says they have to.

I should say, I don't blame you for thinking this way and it seems like an easy mistake to make! Sometimes we just get it wrong.

It sounds like maybe you shouldn't be using string objects at all, but rather create your own custom class and pass those around. Your class could then contain a string, and since it's your own class, you'd have full control over how objects get allocated.

If it's not possible to have a completely separate class, you may be able to achieve the same effect by subclassing NSString.

Ben H. - 2017-11-05 06:16:04

Sun, 05 Nov 2017 06:16:04 GMT

A followup on my previous comment. It turns out that -mutableCopy does not work; I'm putting these strings into an NSDictionary as keys, and it seems NSDictionary makes immutable copies of its keys, which turns them right back into NSTaggedPointerStrings. However, I have discovered that using +[NSString stringWithString:] does seem to work; you get back a copy of the string that is not an NSTaggedPointerString. This is surprising, really – I see no reason for them to do that – and it could probably break at any time. For now, though, it works. I wish I had a better solution. This tagged-pointer business is an interesting, cool idea, but I really don't like that it can change the behavior of existing code in unexpected ways like this. Maybe I should never have been assuming that two separately-created strings would necessarily be two different objects; but does Apple warn against making that assumption anywhere in their docs?

Ben H. - 2017-11-05 03:01:31

Sun, 05 Nov 2017 03:01:31 GMT

Hi Mike. Amazing post, very informative. I have just run into an interesting problem in my app that results from NSTaggedPointerString, and I wonder whether you have any advice. For reasons not worth going into, I'm reading a bunch of strings from a file and keeping them, and later on I need those strings to be distinct objects – i.e. no two strings should be pointer-identical. That used to be the case; each separately-created string would be a separate object. Now, however, as a side effect of Apple's use of NSTaggedPointerString, the short strings are effectively getting uniqued, and pointer equality between strings sometimes results, breaking my code. So one question is: can you see a safe way to guarantee that the system does not do this for my strings? I am contemplating using -mutableCopy and keeping mutable strings instead, but of course Apple could choose to tag-ify those as well if they wanted to, so that's not really safe. Another question is: in this world of tagged points, is the whole idea of using pointer equality now unsafe? Should (a==b) or (a!=b) where a and b are pointers now be verboten, because it has become essentially meaningless and dependent upon internal implementation?

Chris C. - 2015-08-06 16:17:28

Thu, 06 Aug 2015 16:17:28 GMT

My first thought was perhaps a benefit of tagged pointer strings was to improve runtime type encoding performance, but the six-bit encoding table doesn't seem to bear that out.

Jean-Daniel - 2015-08-05 16:04:10

Wed, 05 Aug 2015 16:04:10 GMT

@Shane: There is no guarantee that passing a NSNumber to - [NSString compare:] raises an exception. If you pass anything else than a string to -[NSString compare:], the behavior is undefined, so the implementation is free to returns an invalid value, or raise an exception, or do anything else.

mikeash - 2015-08-04 02:58:03

Tue, 04 Aug 2015 02:58:03 GMT

Björne: On modern systems, computation is fast and memory accesses are slow. If you can avoid accessing memory by burning some extra CPU cycles, the result is likely to be a net gain. Memory allocation and deallocation is also costly, which tagged pointers avoid. Reducing memory usage also increases speed for the program overall, because cache is a limited resource, and spending less cache on strings means more cache available for other uses.

David: Nice find. Makes sense that the debugger would want to know about the internal details like this.

Shane: NSTaggedPointer's compare: implementation assumes that any tagged pointer passed in to the method is also an NSTaggedPointer and does a direct comparison between the contents of the two. This is a valid optimization because the parameter to compare: is NSString * and by passing an NSNumber in, you're violating that static type. So instead of blowing up trying to treat the tagged NSNumber as a string by sending it string messages, it performs a bogus comparison on the tagged NSNumber's internal data.

Shane - 2015-08-04 00:08:35

Tue, 04 Aug 2015 00:08:35 GMT

@Rob: I understand that I'm mixing classes. The point is that no exception is being raised when the tagged pointer string is being passed to NSNumber's compare: method.

Rob Mayoff - 2015-08-03 18:59:22

Mon, 03 Aug 2015 18:59:22 GMT

@Shane: Your error has nothing to do with tagged pointers. The problem is that -[NSNumber compare:] requires an NSNumber* argument, and -[NSString compare:] requires an NSString* argument. You are (indirectly) passing an NSNumber* argument to -[NSString compare:] by mixing the objects in your array.

David - 2015-08-03 04:22:35

Mon, 03 Aug 2015 04:22:35 GMT

Great writeup.

I googled that hardcoded "eilotrm..." string lookup, and got this:

https://llvm.org/svn/llvm-project/lldb/trunk/source/DataFormatters/CXXFormatterFunctions.cpp

The method in question is NSTaggedString_SummaryProvider

Björne - 2015-08-02 13:49:28

Sun, 02 Aug 2015 13:49:28 GMT

But what is the speedup? The benefit with tagged integers is that they work as normal numbers. The assembly instructions ADD, SUB and IDIV all do the right thing automagically. But to append two tagged strings, you first need to unpack them, do the append and then see if they still fit in the packed format.

Operations also get slower, like taking the hashcode of a packed string. You want both the packed and unpacked version of the string "foo" to have the same hashcode, and since you can't store it on the tagged pointer string itself, you have to recompute it each time.

Shane - 2015-08-02 07:47:58

Sun, 02 Aug 2015 07:47:58 GMT

"The next three bits indicate the tagged class." But not everything seems to understand them:

    NSString *seven = @"7";

    NSString *taggedSeven = [[seven mutableCopy] copy];

    NSLog(@"taggedSeven: %p, class: %@", taggedSeven, [taggedSeven class]); //taggedSeven: 0x3715, class: NSTaggedPointerString

    NSLog(@"seven: %p,  class: %@", seven, [seven class]); //seven: 0x100002078,  class: __NSCFConstantString

    

    NSArray *array = @[@4, @2.0, taggedSeven, @6, @10];

    NSArray *result = [array sortedArrayUsingSelector:@selector(compare:)];

    NSLog(@"result: %@", result); // 2, 4, 6, 10, 7

    

    array = @[@4, @2.0, seven, @6, @10];

    result = [array sortedArrayUsingSelector:@selector(compare:)]; //-[__NSCFNumber length]: unrecognized selector sent to instance 0x627

mikeash - 2015-08-01 19:36:51

Sat, 01 Aug 2015 19:36:51 GMT

Daniel: Interesting thought. However, it looks like either the buffer is large enough, or there's nothing important after it, because logging 0xf5 just prints eeeeeeeeeeeeeee and continues normally.

Note that if you experiment with this, you have to make sure that your code does something else with NSString first, like a dummy call to [NSString class], in order to get it properly registered with the runtime. Otherwise you crash in objc_msgSend trying to mess with a tagged pointer it doesn't understand.

Pete - 2015-08-01 15:59:08

Sat, 01 Aug 2015 15:59:08 GMT

Uwe: It's always possible that you can come up with pathological cases where an optimization makes existing code run slower, but that's probably not one of them.

The vast majority of strings stored by almost any program (even in other languages) are ASCII. This optimization only works at all for really short strings. So the only case where this would matter at all to a "Chinese app" would be if it dealt with a huge number of tiny user-entered strings ... without doing any I/O, perhaps, since I/O tends to dwarf even memory dereferencing.

Remember, the short form of the encoding also doesn't work for 10-character ASCII strings that contain the letter "b" or the number "2". Does that mean apps that use "b" and "2" a lot will be 'slower'? Probably not enough for anybody to ever notice.

Daniel - 2015-08-01 09:18:38

Sat, 01 Aug 2015 09:18:38 GMT

There might be a second amendment to be made regarding the __stack_chk_guard:
In a malformed tagged pointer, this would still overflow buffer by up to four bytes, (probably garbling up the stored index parameter on stack?) overwriting them with the ASCII code for “e”.
If it's really writing into the memory of index, that would then enter the exception branch for any original index parameter reporting a ridiculously large out-of-range index—even if the caller passed 0.

Uwe - 2015-08-01 05:40:27

Sat, 01 Aug 2015 05:40:27 GMT

Does that mean that eg Chinese apps have a chance to run a bit slower?

mikeash - 2015-08-01 02:47:19

Sat, 01 Aug 2015 02:47:19 GMT

An even more fun approach to mixing fast numerics and pointers is to embed your pointer value in the payload of an IEEE754 double NaN. A double NaN is represented by setting the 11 bits of the exponent to 1, and by having at least one 1 bit in the 52-bit fraction area. This gives you 52 bits of storage, or 53 bits if you can guarantee you'll never have all zeroes in the fraction area. If you can squeeze your pointers into that extra space (for example, since x86-64 only uses 48 bits of each pointer value then this is trivial) then you can represent each numeric value as a double, and each object value as a NaN.

NaNs propagate through a calculation. Any calculation that involves a NaN will produce a NaN. That means that you can run through your calculation without checking the inputs, and just fall back to the slow path if the result is NaN.

I don't think Cocoa cares since, as you say, you don't use NSNumber for speed. The Objective-C tagged pointer implementation appears to be all about reducing memory allocations, which will also improve performance but as a sort of side effect. NSNumber gets the tagged pointer treatment not because apps are adding them together a lot, but because they're using a lot of NSNumbers to store in arrays and dictionaries and such.

Ken - 2015-08-01 02:39:01

Sat, 01 Aug 2015 02:39:01 GMT

Interesting. I wonder: were they constrained by platform/historical decisions, to use all 0's as the pointer tag value?

The way it's implemented here, arithmetic (with NSNumber) has to mask off the low bits before doing anything. I guess that must be a big gain over the old way, since masking a couple bits is still a lot faster than dereferencing a pointer. Also (IME), NSNumber is really only used for storage, not arithmetic, so people don't really expect it to be fast. When you want fast integer math in Cocoa, you use "int".

In contrast, SBCL, for example, uses all 0's as the fixint tag value, so when they want to add 3 plus 4, they can just call x86 ADD. But this tagged pointer is the default way to do arithmetic, in SBCL, so making this case fast is important to them.

https://github.com/sbcl/sbcl/blob/master/src/compiler/generic/early-objdef.lisp

In fact, for fast integer math, they only need to test (and potentially branch) once. Just bitwise-OR the arguments together, and if the low bits are all still 0 (which in practice they almost always are), you know it's safe to ADD them together!

mikeash - 2015-08-01 01:28:29

Sat, 01 Aug 2015 01:28:29 GMT

Rob Mayoff: Good eye. There's a reason I said "typically a multiple of 16" in the article. If you allocate objects, they are 16-byte aligned, but not all objects are allocated. String constants just get packed into your data section, so they get looser alignment. Fortunately 8 bytes is the worst you'll see on 64-bit, since everything still wants pointer alignment. 32-bit will be 4-byte aligned.

Using the high bits works well as long as you know a chunk of the address space is unused. That's true on x86-64 for now, where only 48 bits are used. It's not the case on 32-bit, so a hypothetical tagged pointer implementation there wouldn't be able to use the high bits. If x86-64 expands to the full 64-bit address space then that would stop working, too.

And yes, you could use any of the bottom three bits as a signal for taggedness. This would expand the number of tagged classes you can discriminate between. I suspect it's less efficient to check for, though. Or maybe they just don't need that many (last I checked, the tagged class table wasn't fully used yet) and went for simplicity.

Bob Peterson: I know six-bit encodings had some history, and five-bit codings substantially pre-date the computer (e.g. Baudot code), but I never heard about the link between 18-bit words, six-bit encodings, and the standard three-character file extension. Interesting tidbit.

Matt: Using the high bits wouldn't break ASLR. You'd only use the high bits if there were portions of the address space that were always unmapped. This is the case in the current implementations of x86-64, for example, where the top 16 bits of a pointer must always be set to the same value, and on the Mac the high values are reserved for the kernel. That means that everything above 2^48 is unmapped from the perspective of userspace, and you can count on those top bits always being zero in a real pointer. ASLR will work within the 48-bit address space, but can't go beyond it.

People always bring up stuff like "32-bit clean" when I post articles about these things, but it simply doesn't apply. The problem with the 24->32-bit transition on the Mac was that third-party apps were pulling tricks like this. Apple could update their code, but third-party apps would break until they were fixed. When these tricks are only being done in the OS, it's not a problem. The OS gets updated whenever fundamental things like the process memory map is updated (for the x86-64 48-bit address space limitation, it would require new CPU hardware) and Apple can update their tagged pointer implementation accordingly. If it's burdensome, they can turn it off. It's a single #define in the Objective-C runtime to toggle it, and I believe you can even toggle it on a process-by-process basis using an environment variable.

As for why Apple doesn't use the high bits, I imagine they just don't need to, and using the low bit as the tagged pointer indicator keeps things simple.

Joseph Gentle: Good question! The exact same loops can be found in the implementation in other methods, like -[NSTaggedPointerString getCharacters:range:] and -[NSTaggedPointerString UTF8String]. My guess is that the code that converts the tagged string storage to a sequence of ASCII bytes lives in a single location in the source code, and then gets inlined into these different methods. characterAtIndex: would use this rather than reading the character directly to keep the implementation in a single location. The overhead is probably not important, as performance-sensitive code won't typically use characterAtIndex: in the first place.

Joseph Gentle - 2015-08-01 01:09:30

Sat, 01 Aug 2015 01:09:30 GMT

I'm confused - Why did they loop through to make the buffer instead of simply reading the character off directly?

For the 6 bit case:



if (length < 0xa) {

  tableIndex = stringData >> (index * 6 * 2) & 0x3f;

  return table[tableIndex];

}

Matt - 2015-08-01 00:04:20

Sat, 01 Aug 2015 00:04:20 GMT

@Rob Mayoff - using the high bits breaks more things; for instance, security approaches like ASLR use the vastness of 64-bit virtual memory to make attacks harder so the high bits aren't guaranteed to be zero.

Also, there are probably still people at Apple that remember the whole "32-bit clean" debacle, where early MacOS programs used the top 8 of 32 bits of addresses for flags. Worked great when the machines it ran on had 512k of RAM - not so hot when they started to get 16M+. :)

Bob Peterson - 2015-07-31 23:54:55

Fri, 31 Jul 2015 23:54:55 GMT

SIXBIT was used back on the early DEC/Digital machines. There were bit string pointers that made it easy to fetch an arbitrary string of bits, so encoding characters in 6 bits did not need masking and shifting. This compaction was invaluable when memory and long term storage were excruciatingly limited and slow. The three character file name suffix came directly out of this encoding: the 18 bit word could store three characters. #geezerhistory

Rob Mayoff - 2015-07-31 21:52:11

Fri, 31 Jul 2015 21:52:11 GMT

Great analysis. A few comments:

1. Did you notice that your original constant string pointer 0x10ba41038 is 8-aligned, not 16-aligned?

2. You could use a tagged pointer scheme even if you allowed byte-aligned objects. Just use the high bits instead of the low bits.

3. Given 8-aligned pointers, you don't need to dedicate a whole bit for a tag flag. The pointer must be fake if any of the low three bits are non-zero.

mikeash - 2015-07-31 17:28:36

Fri, 31 Jul 2015 17:28:36 GMT

Heh, nice catch. I was thinking too much about 8-byte words. Fixed it to 11 now.

Jean-Daniel - 2015-07-31 15:44:19

Fri, 31 Jul 2015 15:44:19 GMT

Maybe you shouldn't have removed the ___stack_chk_guard. It may help you to catch the buffer overflow that will arise if you try to decode a string longer than 8 characters ;-) (int8_t buffer[8];)

That said, this is yet an other very interesting Friday Q&A. Thanks for the hard work.