(x | y) - y why can't it simply be x or even `x | 0`

Question

I was reading a kernel code, and in one place I've seen an expression inside if statement like

if (value == (SPINLOCK_SHARED | 1) - 1) {
         ............
}

where SPINLOCK_SHARED = 0x80000000 is a predefined constant.

I wonder why do we need (SPINLOCK_SHARED | 1) - 1 - for type conversion purpose? the result of the expression would be 80000000-- same as 0x80000000, is it not? yet, why ORing 1 and Subtracting 1 matters?

Have a feeling like I am missing to get something..

There's something not clear to me: is `SPINLOCK_SHARED` a variable or a constant set through #define? — Roberto Caboni, Dec 19 '19 at 12:34
I suspect there's no reason. Possibly a copy-paste thing. Could you add where exactly you found this (which version of which kernel, which file, etc.). — Sander De Dycker, Dec 19 '19 at 12:39
Here, https://github.com/DragonFlyBSD/DragonFlyBSD/blob/master/sys/kern/kern_spinlock.c#L177 — RaGa__M, Dec 19 '19 at 12:42
Where is `SPINLOCK_SHARED` defined? Is it inside conditional code, so that it could be defined by different code if different build/compile options are used? — Eric Postpischil, Dec 19 '19 at 12:45
https://github.com/DragonFlyBSD/DragonFlyBSD/blob/master/sys/sys/spinlock.h#L55 — RaGa__M, Dec 19 '19 at 12:46
The [commit](https://github.com/DragonFlyBSD/DragonFlyBSD/commit/cc705b823a33a247956d2a54a4e929a0ca2936d9) doesn't explain it at all. — KamilCuk, Dec 19 '19 at 12:51
The same source code file also contains `if (atomic_cmpset_int(&spin->counta, SPINLOCK_SHARED|0, 1))`. — Eric Postpischil, Dec 19 '19 at 12:58
I copied the git and searched for `grep '|[[:space:]]*1[[:space:]]*)[[:space:]]*-[[:space:]]*1' -r .` (and similar). This is a single instance of `|1)-1` in the code. — KamilCuk, Dec 19 '19 at 12:59
The source code contains various instances of `SPINLOCK_SHARED|0` and `SPINLOCK_SHARED|1`, suggesting the author is thinking of the spinlock “counter” as one bit indicating shared/exclusive and other bits containing a count (in which 0 and 1 are notable counts for various purposes). — Eric Postpischil, Dec 19 '19 at 13:03
The constant could on other platforms have bit 0 set. The only guess for not using SPINLOCK_SHARED & -2 might be signed/unsigned comparison on some processors, spinlock | 1 is checked at some places. — Joop Eggen, Dec 19 '19 at 13:11
IIRC [integer overflow is undefined in C](https://stackoverflow.com/a/3948496/128511) so assigning an 0x80000000 to an int sounds like trouble to me. — gman, Jan 02 '20 at 06:15

score 31 · Answer 1 · answered Dec 19 '19 at 13:11

31

The code is found in _spin_lock_contested, which is called from _spin_lock_quick when someone else is attempting to obtain the lock :

count = atomic_fetchadd_int(&spin->counta, 1);
if (__predict_false(count != 0)) {
    _spin_lock_contested(spin, ident, count);
}

If there's no contest, then count (the previous value) should be 0, but it isn't. This count value is passed as parameter to _spin_lock_contested as the value parameter. This value is then checked with the if from the OP :

/*
 * WARNING! Caller has already incremented the lock.  We must
 *      increment the count value (from the inline's fetch-add)
 *      to match.
 *
 * Handle the degenerate case where the spinlock is flagged SHARED
 * with only our reference.  We can convert it to EXCLUSIVE.
 */
if (value == (SPINLOCK_SHARED | 1) - 1) {
    if (atomic_cmpset_int(&spin->counta, SPINLOCK_SHARED | 1, 1))
        return;
}

Keeping in mind that value is the previous value of spin->counta, and the latter has already been incremented by 1, we expect spin->counta to equal value + 1 (unless something has changed in the meantime).

So, checking if spin->counta == SPINLOCK_SHARED | 1 (the precondition of the atomic_cmpset_int) corresponds to checking if value + 1 == SPINLOCK_SHARED | 1, which can be rewritten as value == (SPINLOCK_SHARED | 1) - 1 (again, if nothing has changed in the meantime).

While value == (SPINLOCK_SHARED | 1) - 1 could be rewritten as value == SPINLOCK_SHARED, it's left as is, to clarify the intent of the comparison (ie. to compare the incremented previous value with the test value).

Or iow. the answer appears to be : for clarity and code consistency.

answered Dec 19 '19 at 13:11

Sander De Dycker

16,053
1
35
40

Thanks for your response, everything except `(SPINLOCK_SHARED | 1) - 1` part is understandable and `value == SPINLOCK_SHARED` is my thought too, because we are checking whether the previous value has shared-flag set.if yes, turn the lock into exclusive......... – RaGa__M Dec 19 '19 at 13:19
1

@RaGa__M : the intent of the `if` check is to check whether `value + 1` (which should be the same value as `spin->counta` if nothing has changed in the meantime) equals `SPINLOCK_SHARED | 1`. If you write the `if` check as `value == SPINLOCK_SHARED`, this intent is not clear, and it would be a lot harder to figure out what the check means. Keeping both `SPINLOCK_SHARED | 1` and `- 1` explicitly in the `if` check is intentional. – Sander De Dycker Dec 19 '19 at 13:26
But it is actually causing confusion. – RaGa__M Dec 20 '19 at 05:30
Why not `if (value + 1 == (SPINLOCK_SHARED | 1) )`? – Pablo H Dec 20 '19 at 20:09
Well....it simply could be `value & SPINLOCK_SHARED` which is more readable. – RaGa__M Dec 21 '19 at 07:09
@PabloH : a different way of looking at the same thing : adjusting the value to fit the current state vs. adjusting the test value to fit the previous state. Both are equally valid, but in the end you're checking `value`, so it makes sense to have that on the left-hand side of the comparison. – Sander De Dycker Dec 23 '19 at 16:27
@RaGa__M : you appear to be missing the point. The goal is not to make the expression simpler and easier to read, but to make it easier to understand its intent. They're two different things. By making the expression simpler (as you suggest), you're losing information about the intent, which in turn makes it harder to understand the *why* of the code. The comment above the test currently nicely fits the code, and clarifies it. But with your suggested change, that would no longer be the case. Further clarification would have to be added to compensate for the information lost in the code. – Sander De Dycker Dec 23 '19 at 16:38
@RaGa__M : or to put it differently : the test is whether the spinlock is currently shared (`SPINLOCK_SHARED`) and owned by just us (`| 1`) by checking the previous value (`value`) adjusted to fit the (expected) current state (`+ 1` or `- 1`). After that test succeeds, we do the same test again, but this time on the *actual* current state (`spin->counta`) to make sure nothing has changed in the meantime. – Sander De Dycker Dec 23 '19 at 16:57
The objective was, is the `spinlock` shared, if it is, check the current thread is the only actor `|1` if yes, acquire it exclusively-- set `1`. @SanderDeDycker – RaGa__M Dec 23 '19 at 17:14
@RaGa__M : indeed. But your proposed alternative doesn't mention the `| 1` part. And that's the reason the expression is written as it is (that and to explain how the expression was adjusted to allow testing against the previous value instead of the current value). – Sander De Dycker Dec 23 '19 at 17:39
If you can simplify expression, why can't you simplify intent? – Atomosk Dec 25 '19 at 01:58

score 10 · Answer 2 · answered Dec 19 '19 at 12:31

10

I think the goal is probably to ignore the lowest significant bit:

If SPINLOCK_SHARED expressed in binary is xxx0 -> result is xxx0
If SPINLOCK_SHARED = xxx1 -> result is also xxx0

would have been perhaps clearer to use a bit mask expression ?

answered Dec 19 '19 at 12:31

Guillaume Petitjean

2,408
1
21
47

8

That's what the code does, but the question is *why* would you do that for a defined constant that doesn't have the least significant bit set ? – Sander De Dycker Dec 19 '19 at 12:37
4

@SanderDeDycker Because Linux kernel? – Lundin Dec 19 '19 at 12:39
9

@Lundin The linux kernel is not exempt from understandable coding practices. Quite the opposite. – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:40
1

@Qix I strongly disagree. Read the Linux kernel coding style document. It's a "garage-hacking" quality document, completely exempt from rationales. – Lundin Dec 19 '19 at 12:41
1

@Lundin I meant, that's not what we should strive for. Especially since the Linux kernel is so vital to.. well, the world. – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:47
@SanderDeDycker I didn't know this is a constant – Guillaume Petitjean Dec 19 '19 at 12:47
@Qix, it isn't because it is useful that everything in it is perfect. I remember one of the coding rules is "do not write any comment". Don't know if it's still true, but it sounds as least questionable – Guillaume Petitjean Dec 19 '19 at 12:48
1

@GuillaumePetitjean there are tons of comments in the linux kernel. Also, OP specifically states that `SPINLOCK_SHARED` is a constant (defined as `0x80000000`). – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:49
1

And the thing is, it isn't from linux kernel. – RaGa__M Dec 19 '19 at 12:50
OK sorry my memory failed me. – Guillaume Petitjean Dec 19 '19 at 12:50
@Qix, still, my answer applies also to a constant doesn't it ? In case there is a reason to ignore the lowest bit, for whatever reason – Guillaume Petitjean Dec 19 '19 at 12:52
2

@Qix If you say so. I was a big fan of Linux until I peeked at the code and read the kernel coding style document. Nowdays I keep a 10 meter safety distance to Linux computers. – Lundin Dec 19 '19 at 12:53
1

@Lundin judging the efficacy and stability of a codebase in such wide use and under such scrutiny based on its style guide is silly and naive. – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:53

score 4 · Answer 3 · answered Dec 19 '19 at 12:43

The effect of

(SPINLOCK_SHARED | 1) - 1

is to ensure that the low-order bit of the result is cleared prior to the comparison with value. I agree that it seems rather pointless but apparently the low-order bit has a particular usage or meaning which is not apparent in this code, and I think we have to assume that the devs had a good reason for doing this. An interesting question would be - is this same pattern (| 1) -1) used throughout the codebase you're looking at?

score 2 · Answer 4 · answered Dec 19 '19 at 12:37

2

It's an obfuscated way of writing a bit mask. Readable version: value == (SPINLOCK_SHARED & ~1u).

answered Dec 19 '19 at 12:37

Lundin

195,001
40
254
396

5

Yes, but _why_. The OP is asking _why_ this would be the case if `SPINLOCK_SHARED` is a known constant. If they're simply testing for `SPINLOCK_SHARED` being present in a mask, why not `if (value & SPINLOCK_SHARED)`? – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:39
True, that's my question. – RaGa__M Dec 19 '19 at 12:40
4

`value == (SPINLOCK_SHARED & ~1u)` is not equivalent because `value == (SPINLOCK_SHARED | 1) - 1` works even if the type of `SPINLOCK_SHARED` is wider than `unsigned`. – Eric Postpischil Dec 19 '19 at 12:42
1

@EricPostpischil But we know that it is `0x80000000` which as it happens is guaranteed to be of type `unsigned`. – Lundin Dec 19 '19 at 12:44
4

Honestly, I'm not sure that `& ~1u` is any clearer. I thought of suggesting `& 0xFFFFFFFE` in my answer but realized that's also not really clear. Your suggestion does have the advantage of brevity, though. :-) – Bob Jarvis - Слава Україні Dec 19 '19 at 12:46
6

@Lundin: We do not know that it will be `0x80000000`. OP has stated it is defined with `#define SPINLOCK_SHARED 0x80000000`, but that could be inside `#if…#endif` and a different definition is used in other circumstances, or the author of this code could have intended it to work even if the definition is edited or the code is compiled with other headers that define it differently. Regardless, the two pieces of code are not equivalent by themselves. – Eric Postpischil Dec 19 '19 at 12:46
2

@BobJarvis-ReinstateMonica It's much clearer to people who work with bitwise operators every day. Mixing bitwise with regular arithmetic is confusing. – Lundin Dec 19 '19 at 12:49
1

@EricPostpischil Regardless, for such scenarios you wouldn't be using magic numbers but rather `SPINLOCK_SHARED & ~FOO_BIT` where each constant has the same type. – Lundin Dec 19 '19 at 12:50
2

Nonetheless, the two pieces of code are not equivalent. – Eric Postpischil Dec 19 '19 at 12:50
1

@EricPostpischil You have a point there. `(SPINLOCK_SHARED | 1) - 1` cleverly avoids the risk of `SPINLOCK_SHARED` being wider than negative literals (i.e. `~1u`), either due to an unanticipated change in the definition of `SPINLOCK_SHARED`, or due to a quirky C compiler. – Ruud Helderman Dec 19 '19 at 13:14
@RuudHelderman The actual define is `0x80000000` though. If the reason for the - 1 trick was cleverness, then the programmer would also surely be aware of all the subtle crap revolving around C's integer constants. That is, `0x80000000` is of type `unsigned int` but `0x40000000` is of type `signed int`. Programmers who don't `u` suffix hex constants are clearly not aware of this though, so the probability of the programmer having some deeper meaning of the - 1 trick is very low. – Lundin Dec 19 '19 at 14:33
1

@Lundin Some day, someone may have conceived `(x | 1) - 1` as an alternative for `x & ~1` when faced with a buggy C compiler that did not properly implement _common real type_. Somebody else may have adopted the pattern without properly understanding the rationale. As for the defines, those may have been written by a different programmer. Or maybe there was this sudden urge to support ancient C compilers that do not support the `U` suffix. Without an explanation from the original author(s), we can only guess. – Ruud Helderman Dec 19 '19 at 15:38

score 1 · Accepted Answer · answered Jan 29 '20 at 18:44

It was just done that way for clarity, that's all. It's because atomic_fetchadd_int() (in e.g. sys/spinlock2.h) returns the value PRIOR to the addition/subtraction, and that value is passed to _spin_lock_contested()

Note that the C compiler completely pre-calculates all constant expressions. In fact, the compiler can even optimize-out inlined code based on conditionals that use passed-in procedure arguments when the procedures are passed constants in those arguments. This is why the lockmgr() inline in sys/lock.h has a case statement.... because that entire case statement will be optimized out and devolve into a direct call to the appropriate function.

Also, in all of these locking functions the overhead of the atomic ops dwarf all other calculations by two or three orders of magnitude.

-Matt

This answer is from the author. – RaGa__M Sep 02 '20 at 11:01 — RaGa__M, Sep 02 '20 at 11:01

funnydman · Answer 6 · 2019-12-19T12:39:50.133

0

Most like this is done to handle several additional cases. For example, in this case, we say that SPINLOCK_SHARED can not be 1:

int SPINLOCK_SHARED = 0x01

int res = (SPINLOCK_SHARED | 1) - 1 // 0

edited Dec 19 '19 at 12:39

answered Dec 19 '19 at 12:28

funnydman

9,083
4
40
55

2

It would make sense but, though it is not actually clear from the question, it sounds like `SPINLOCK_SHARED` is a defined constant and the tested variable is `value`. In this case the mistery remains. – Roberto Caboni Dec 19 '19 at 12:33
Thanks for your reply, But I think in original case SPINLOCK_SHARED is not 0x01, you kept the `| 1) - 1` part tho, when SPINLOCK_SHARED holding `0x80000000` what would be the impact of `| 1) - 1`? – RaGa__M Dec 19 '19 at 12:34
The only reason I could think of is that they wanted to guard against `SPINLOCK_SHARED` being changed in the future. But it's not at all clear. I would write in to the kernel devs and ask for a clarification comment to be made or for the expression to be rearranged so that it self-documents. – Qix - MONICA WAS MISTREATED Dec 19 '19 at 12:38

(x | y) - y why can't it simply be x or even `x | 0`

6 Answers6