mikeash.com pyblog/deadlocks-and-lock-ordering-a-vignette.html comments

Language Defense Attorney - 2013-11-04 04:21:14

Mon, 04 Nov 2013 04:21:14 GMT

Objection!

This is a very clever hack, and I like it, but LL is right. It's undefined. If you want to make this work, then just cast your pointers to intptr_t first, and back to a pointer when you're done:

@synchronized((void*) MIN((intptr_t) a, (intptr_t) b)) { ...

It's a little uglier, but it's totally valid and well-defined C! Now your clever multiprocessing code will run even on your 286 in protected-mode segments, if you want.

OK, I joke, but there does appear to be an actual problem with this code as originally written.

Interestingly, Xcode/Clang generates different object code for this, depending on whether you cast it properly or not. In fact, the version without the casts is longer, and seems to include 4 extra objc_retain calls, which are unmatched by any apparent objc_release calls.

Looking through the code for __NSMIN_IMPL__ (and ...MAX...), I can perhaps see why. Xcode's MIN() isn't the trivial #define they show you on the first day of C preprocessor class. It makes a little block, creates local variables of the same type as the arguments, and then compares those (so it doesn't have to evaluate the parameters twice). I would totally believe that ARC would get a little confused by that, and throw in -retain calls to each object used by the preprocessor blocks. (MIN(a,b) + MAX(a,b) = 4 objects passed = 4 retain calls.)

That suggests to me that calling MIN() or MAX() on NSObject pointers when using ARC can result in a memory leak. If you actually have two arbitrary id's you need to compare, cast to intptr_t and compare those, because that's what it's there for.

me - 2012-07-16 09:01:39

Mon, 16 Jul 2012 09:01:39 GMT

For a comparison to be undefined doesn't mean you will get back an illogical value, it means your program may crash, hang, initiate global thermonuclear war, start a game of Nethack or whatever the compiler wants.

languageLawyer - 2012-06-03 08:17:35

Sun, 03 Jun 2012 08:17:35 GMT

Kyle Sluders reading and interpretation of the standard is correct- for the type of comparison being discussed, the standard says that the behavior is undefined. The standard explicitly enumerates when such pointer relational comparisons are defined and valid (i.e., different members of a struct and elements of the same array).

Everything else is explicitly undefined. No where in the standard is there anything that remotely supports Mikes "consistent total ordering of all pointers" interpretation.

From Derek Jones "The New C Standard", on §6.5.8:

Commentary

The C relational operator model enables pointers to objects to be treated in the same way as indexes into array objects. Relational comparisons between indexes into two different array objects (that are not both subobjects of a larger object) rarely have any meaning and the standard does not define such support for pointers. Some applications do need to make use of information on the relative locations of different objects in storage. However, this usage was not considered to be of sufficient general utility for the Committee to specify a model defining the behavior.

[...]

Common Implementations

Most implementations perform no checks prior to any operation on values having pointer type. Most processors use the same instructions for performing relational comparisons involving pointer types as they use for arithmetic types. For processors that use a segmented memory architecture, a pointer value is often represented using two components, a segment number and an offset within that segment. A consequence of this representation is that there are many benefits in allocating storage for objects such that it fits within a single segment (i.e., storage for an object does not span a segment boundary). One benefit is an optimization involving the generated machine code for some of the relational operators, which only needs to check the segment offset component. This can lead to the situation where p >= q is false but p > q is true, when p and q point to different objects.

The above not withstanding, the pointer comparison in question is pretty safe for the set of compilers and architectures the code is meant for, and almost certainly true for any future architecture.

This is one of those undefined behaviors where if it's going to be a problem, you're very much aware that it's a problem- you're writing C code for a PIC microcontroller that's got 4096 bytes of memory accessed in 256 byte chunks via a segment register. :)

mikeash - 2012-03-06 16:51:09

Tue, 06 Mar 2012 16:51:09 GMT

I figure a summary of the subsequent discussion on Twitter might be interesting to anyone who finds this page.

My reading of the quoted paragraph is that, since the result of pointer comparison depends on the relative locations in the address space, the result is a consistent total ordering of all pointers and the comparison is safe. I reconcile this with "the behavior is undefined" by interpreting it as saying that, while the ordering will be consistent, it will not be predictable in advance. In other words, a < b will always produce the same result for the same inputs, but you can't rely on e.g. local variables' pointers being in a particular order, or heap allocations being in a particular order, or local variables being ordered before/after heap allocations.

I think this satisfies every condition listed in that paragraph, but reading standards is hard (let's go shopping!), this paragraph is definitely not very clear, and I could be wrong. However, I'm happy enough with it to rely on it working for any compiler/architecture combo Cocoa code will ever run on.

Kyle Sluder - 2012-03-05 23:57:48

Mon, 05 Mar 2012 23:57:48 GMT

I don't believe that your pointer comparison is valid here.

§6.5.8 of the C99 standard defines the valid comparisons between pointer objects:

5. When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

In your example, a and b can point to arbitrary locations in memory. Thus the comparison between them results in undefined behavior.

Granted, all that matters is that the behavior is consistent, but that's not guaranteed.

Chris Suter - 2012-02-13 09:20:19

Mon, 13 Feb 2012 09:20:19 GMT

Nice. I just posted an article on my blog (http://sutes.co.uk/2012/02/deadlocks.html) about a pattern that I use when you have two locks. It’s for the case where you usually want the child lock but depending on some condition you want the parent lock as well.