Skip to contentSkip to conversation

Introduce nodemask_t ADT [0/7]

PATCH Andi Kleen 3 participants 5 messages Mar 19, 2004 – Mar 20, 2004 3 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

Andi Kleen

author
#3 lore raw
Quoted 5 lines · Matthew Dobson
Quoted 3 lines

Chris Hellwig responded to it at the time asking why I didn't provide a single generic mask ADT, and make cpumask and nodemask instances of that.

That is a better idea, if it can be made to work. My goal is to stop

It already exists in linux/bitmap.h. I use that in NUMA API for the node masks.

It's just a bit ugly to write because you have to always pass MAX_NUMNODES. Some wrappers would be prettier.

-Andi

#4 lore raw
Quoted 1 line

Some wrappers would be prettier.

That's roughly what the mask.h is, along with enough other bits and pieces so that it can serve as a complete basis for cpumasks and nodemasks. The bitmap.h stuff is an incomplete subset of what's used.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#5 lore raw
In reply to Andi Kleen
Quoted 6 lines · Andi Kleen
Quoted 4 lines · Matthew Dobson
Quoted 3 lines

Chris Hellwig responded to it at the time asking why I didn't provide a single generic mask ADT, and make cpumask and nodemask instances of that.

Quoted 8 lines
Quoted 1 line

That is a better idea, if it can be made to work. My goal is to stop

It already exists in linux/bitmap.h. I use that in NUMA API for the node masks.

It's just a bit ugly to write because you have to always pass MAX_NUMNODES. Some wrappers would be prettier.

-Andi

For MAX_NUMNODES > BITS_PER_LONG, thats just what these are. There are just built-in optimizations for the single bit (UP for cpumask, non-NUMA for nodemask) case and the single unsigned long case. For the case of a single unsigned long, the bitmap operations aren't as efficient as just doing a

	res = (mask1 & mask2);
vs. 
	bitmask_and(&res, &mask1, &mask2);

Maybe I'm overly concerned about the speed of these ops at the expense of code size. If that's the consensus, I'll gladly look at a simpler implementation. As I said, my only real goal is to stop people open coding these types of operations.

-Matt

#6 lore raw
Quoted 5 lines

For the case of a single unsigned long, the bitmap operations aren't as efficient as just doing a

	res = (mask1 & mask2);
vs.
	bitmask_and(&res, &mask1, &mask2);

This is probably the same as Matt is thinking, but what I imagine has the inline efficiency (a machine instruction or two) of the openly coded first example above, but is always written more in the style of the second example above.

The 'mask_and()' macro can be an inline or define that collapses in the one word case (by far the most common) to the same machine instruction or two as the open code does. We _do_ know, at compile time, the _exact_ size of any given instance of these, so gcc has sufficient information to collapse the inline code, if we present it right, to the legitimate minimum.

For example, mask_and might be:

=========================================================================
#define __mask(bits) struct { unsigned long _m[BITS_TO_LONGS(bits)]; }
typedef __mask(NR_CPUS) cpumask_t;

#define mask_and(d,s1,s2)                               \
do {                                                    \
        if (sizeof(d) == sizeof(unsigned long))         \
                d._m[0] = s1._m[0] & s2._m[0];          \
        else                                            \
                bitmask_and(d._m, s1._m, s2._m);        \

} while(0)
=========================================================================

With this, mask_and() on some cpumask_t's, when NR_CPUS is 64, _does_ collapse to a simple:

        and r32 = r8, r32

on my ia64 with gcc 3.2.3.

The mask.h I appended yesterday uses bitmap calls such as bitmap_and() unconditionally (even in the one word case). This is probably worth fixing, in the manner shown above, at least for such cases such as 'and', 'or', 'empty', 'complement', 'shift_left' and 'shift_right'.

No use of multiple architecturally chosen implementations, such as we do now with cpumask, is required. Just a little bit of special case code for the one-word case, in 6 or 8 of the macros.

I still think, that with just a few lines of compile time logic such as above, we can have a single implementation that is pretty close to ideal, for almost all architectures, using a struct holding an array of unsigned longs.

The one obvious exception, sparc64, should have its own arch specific implementation under include/asm-sparc64 and perhaps arch/sparc64. It should not be embedded in a thicket of pseudo-generic ifdefs and conditional includes as part of the apparently generic implementation.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#7 lore raw
Quoted 1 line
               bitmask_and(d._m, s1._m, s2._m);        \

Oops - need the size argument to bitmask_and:

		bitmask_and(d._m, s1._m, s2._m, sizeof(d)*8);        \

(I only tested the 1 word case earlier ...)

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373