Messages in this thread | | | Date | Thu, 21 Feb 2019 04:53:56 +0100 | From | Frederic Weisbecker <> | Subject | Re: [PATCH 05/32] locking/lockdep: Prepare valid_state() to handle plain masks |
| |
On Wed, Feb 13, 2019 at 11:47:13AM -0800, Linus Torvalds wrote: > On Wed, Feb 13, 2019 at 7:16 AM Frederic Weisbecker <frederic@kernel.org> wrote: > > > > > > If "vectors" only has the high hit set, you end up with "fs" having > > > the value "64". > > > > > > And then "vectors >>= fs" is undefined and won't actually do anything > > > at all on x86. > > > > Oh! ok didn't know that... > > So in general, shift counts >= width of the type (or negative) are undefined. > > They can sometimes happen to work (that's the "undefined" part ;), but > it's not reliable or portable. > > It's why you occasionally see things like > > drivers/block/sx8.c: > tmp = (blk_rq_pos(rq) >> 16) >> 16; > > to get the upper 32 bits of the value. It is written with that odd > double shift, rather than being written as ">> 32". That way it works > even if the sector type happens to be 32-bit (and the compiler will > just end up turning it into a zero if it's an unsigned 32-bit type > since it's compile-time obvious).
Ok, I see.
> > > I see, perhaps I should use for_each_set_bit() that should take care about those > > details? > > That would _work_, but don't do that. "for_each_set_bit()" works on > bitmaps in memory, and is slow for a simple word case. In addition to > being slow, it uses the Linux tradition of working on bitmaps that are > comprised of "unsigned long". So it has byte order issues too. > > So for_each_set_bit() is useful when you have real arrays of bits and > are using the "set_bit()" etc interfaces.
Yeah I suspected some overhead.
> > When you're actually working on just a single variable, your "__ffs()" > model works fine, you just need to be careful to _not_ do the "+1" and > then use it for shifts. > > Also, it actually turns out that if you want to be really clever, you > can play tricks if you don't care about the exact bit *number*. > > For example, this expression: > > v = a & (a-1); > > will remove the lowest bit set from 'a' very cheaply. So what you can > do is something like this: > > void for_each_bit_in_mask(u64 mask) > { > while (mask) { > u64 newmask = mask & (mask-1); > u64 onebit = mask ^ newmask; > mask = newmask; > do_something_with(onebit); > } > } > > to do some operation on each bit set, and quite efficiently and > without any undefined behavior or expensive shifts. > > But the above trick does require that you are happy to just see the > bit *mask*, not the bit *number*. I'm not sure any of your cases match > that.
Nice, I couldn't resist introducing such a headache in my set ;-) unfortunately I indeed need the bit number itself most of the time.
So following your 1st advice, I should rather do something along the lines of:
nr = 0; while (mask) { fs = __ffs64(mask); mask >>= fs; mask >>= 1; nr += fs + 1; process_bit_nr(nr - 1); }
And define a for_each_lock_usage_bit(usage_mask) on top of it.
Thanks a lot!
| |