[PATCH] mask ADT: new mask.h file [2/22]

Paul Jackson
2004-03-29T12:14:18Z

Patch_2_of_22 - New mask ADT
Adds new include/linux/mask.h header file

==> See this mask.h header for more extensive mask documentation <==

diffstat Patch_2_of_22:
mask.h | 372 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 372 insertions(+)

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
# ChangeSet 1.1707 -> 1.1708
# (new) -> 1.1 include/linux/mask.h
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/03/28 pj@sgi.com 1.1708
# New mask ADT to be used as common basis for cpumask and nodemask types.
# --------------------------------------------
#
diff -Nru a/include/linux/mask.h b/include/linux/mask.h
--- /dev/null Wed Dec 31 16:00:00 1969
+++ b/include/linux/mask.h Mon Mar 29 01:03:28 2004
@@ -0,0 +1,372 @@
+#ifndef _ASM_GENERIC_MASK_H
+#define _ASM_GENERIC_MASK_H
+
+/*
+ * include/linux/mask.h
+ *
+ * Copyright (c) 2004 Silicon Graphics, Inc. All rights reserved.
+ *
+ * Paul Jackson <pj@sgi.com>
+ *
+ * This file is distributed under the GNU GENERAL PUBLIC LICENSE (GPL)
+ * Version 2 (June 1991). See the "COPYING" file distributed with this
+ * software for more info.
+ */
+
+/*
+ * Mask is an abstract data type for multi-word bit masks. Masks
+ * are bitmaps (arrays of unsigned longs) wrapped in a struct.
+ * The struct wrapper enables them to be assigned and passed as
+ * arguments. Masks are useful for representing sets of small
+ * numbers, such as the CPU numbers on a multi-processor system.
+ *
+ * How mask.h fits with bitops.h, bitmap.h, cpumask.h and nodemask.h:
+ *
+ * 1) bitmap.h and lib/bitmap.c provide several operations
+ * for manipulating bitmaps, as arrays of unsigned long.
+ * There are operations that and, or, set, clear, shift,
+ * print, parse, and test these bitmaps. The routines
+ * typically require a pointer to an array of unsigned longs,
+ * and a count of the number of valid bits therein.
+ *
+ * The byte ordering of bitmaps is more natural on little
+ * endian architectures. See the big-endian headers
+ * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
+ * for the best explanations of this ordering.
+ *
+ * 2) bitops.h provides a few specific inline routines for
+ * finding the first set bit and the Hamming weight of
+ * these same bitmaps. Several architectures provide
+ * include/asm-<arch>/bitops.h variants, optimized for
+ * specific processor instruction sets.
+ *
+ * 3) mask.h makes use of bitmap.h, bitops.h and a few other
+ * kernel utilities to provide a mask abstract data type
+ * (ADT) as a structure of an array of unsigned longs.
+ * mask.h attempts to provide a fairly complete set of
+ * operations, to make it easy for users to write clear
+ * concise and correct mask manipulation code.
+ *
+ * The mask macros use the fairly rich compile time
+ * optimizations of gcc in order to generate optimum code
+ * for each architecture. Some of these macros require the
+ * current mask type or number of bits - the cpumask.h and
+ * nodemask.h macros serve to hide such details.
+ *
+ * 4) cpumask.h and nodemask.h are both based on mask.h.
+ * They provide cpu and node specific macros that hide
+ * such details as NR_CPUS that might be needed by the
+ * lower level mask macros defined below.
+ *
+ * Summary:
+ * Don't use mask.h directly - use cpumask.h and nodemask.h.
+ *
+ * The available mask operations and their rough meaning in the
+ * case that "nbits == 8 * sizeof(single unsigned long)" are:
+ *
+ * __mask(nbits) Use to define new *mask types
+ * mask_setbit(bit, mask) mask |= bit
+ * mask_clearbit(bit, mask) mask &= ~bit
+ * mask_setall(mask, nbits) mask = ~0UL
+ * mask_clearall(mask) mask = 0UL
+ * mask_isset(bit, mask) Is bit set in mask?
+ * mask_test_and_set(bit, mask) mask | bit ? 0 : mask |= bit
+ * mask_and(dst, src1, src2) dst = src1 & src2
+ * mask_or(dst, src1, src2) dst = src1 | src2
+ * mask_xor(dst, src1, src2) dst = src1 ^ src2
+ * mask_andnot(dst, src1, src2) dst = src1 & ~src2
+ * mask_complement(dst, src, nbits) dst = ~src
+ * mask_equal(mask1, mask2) Are mask1 and mask2 equal?
+ * mask_intersects(mask1, mask2) Do mask1 and mask2 overlap?
+ * mask_subset(mask1, mask2) Is mask1 a subset of mask2?
+ * mask_empty(mask) Is mask empty?
+ * mask_full(mask, nbits) Are all bits set in mask?
+ * mask_weight(mask, nbits) Hamming Weight: number set bits
+ * mask_shift_right(dst, src, n, nbits) dst = src >> n
+ * mask_shift_left(dst, src, n, nbits) dst = src << n
+ * mask_first(mask, nbits) find_first_bit(mask, nbits)
+ * mask_next(bit, mask, nbits) find_next_bit(mask, size, bit, nbits)
+ * mask_of_bit(bit, T) returns mask with a single bit set
+ * MASK_ALL(nbits) returns mask with all bits set
+ * MASK_NONE(nbits) returns mask with no bits set
+ * mask_raw(mask) Array of unsigned long's in mask
+ * mask_scnprintf(buf, len, mask, nbits) scnprintf(buf, len, "%lx", mask, nbits)
+ * mask_parse(ubuf, ulen, mask, nbits) parse comma sep 32 bit words to mask
+ *
+ * Various Implementation Details
+ * ==============================
+ *
+ * The parameter 'T' above must be a variable of the appropriate
+ * mask type (cpumask_t or nodemask_t, for instance). This
+ * variable is only used for its typeof() information.
+ *
+ * For details of mask_scnprintf() and mask_parse(), see
+ * bitmap_scnprintf() and bitmap_parse() in lib/bitmap.c
+ *
+ * A new *mask type should be defined, such as cpumask_t or
+ * nodemask_t, for each possibly different sized (number of
+ * bits) bitmask based on this mask ADT. The definition
+ * for example of cpumask_t is:
+ * typedef __mask(NR_CPUS) cpumask_t;
+ *
+ * The previous definitions of CPU_MASK_ALL were inconsistent.
+ * For cpumasks of one word size or less, they set exactly
+ * NR_CPUS bits, leaving any remaining high order bits zero.
+ * For cpumasks of multiple words, all bits were set, which
+ * might result in a cpumask of weight > NR_CPUS, if NR_CPUS is
+ * not an exact multiple of the number of bits in an unsigned
+ * long. The MASK_ALL(nbits) macro fixes this inconsistency
+ * by refining the static initializor to set only valid bits
+ * in the last word.
+ *
+ * These macros presume that all masks passed in a given call
+ * are the same nbits long, and that only bits in positions
+ * b where 0 <= b < nbits might be set in input masks.
+ * They ensure that no additional bits outside this range
+ * become set (however don't protect against improperly set
+ * bits that are outside this range but still inside the array
+ * of unsigned longs representing the mask.) In other words,
+ * any implementation of these ops may assume as a precondition
+ * that any unused bits (bits in the array of unsigned
+ * longs, outside the range 0 to nbits-1) are zero. And any
+ * implementation of these ops must ensure as a postcondition
+ * on all output masks that this same precondition (unused
+ * bits are zero) holds. If you manage to create, by some
+ * other means, a mask with some unused bits non-zero, and
+ * then pass that mask to one of these mask operations, that
+ * operation may malfunction.
+ *
+ * The abstract bit model supported by these masks is that of
+ * an infinite set of bits, in positions numbered 0 and up,
+ * where all but the first 'nbits' bits are always zero.
+ * Calls that implicitly attempt to set any bit outside of
+ * the first 'nbits' bits successfully and quietly leave such
+ * bits as zero. Calls that query or modify specifically
+ * numbered bit positions require as a precondition that the
+ * specified bit position 'n' is the range 0 <= n < nbits, and
+ * may malfunction if handed a bit position outside this range.
+ *
+ * The mask_raw() op enables violating this model. It returns
+ * the address of the start of the array of unsigned
+ * longs, enabling the caller to directly manipulate them.
+ * This can be used to intermix mask ops with classic 'C' bit
+ * operations, usually only done on systems whose cpumask_t
+ * fits in a single unsigned long word.
+ *
+ * The underlying bitmap.c operations such as bitmap_and() and
+ * bitmap_or() don't follow this model. They don't assume
+ * the precondition that unused bits are zero, and they do
+ * mask off any unused portion of input masks in most cases.
+ * However the underlying bitop.h operations, such as set_bit()
+ * and clear_bit(), do no sanitizing of their inputs, depending
+ * heavily on preconditions.
+ *
+ * The declaration of the array _m[] of unsigned longs in the
+ * definition of __mask() below intentionally does not use
+ * the DECLARE_BITMAP() macro. It would be gratuitously opaque
+ * in this case - as the macro implementations below depend on
+ * the internal details of this declaration.
+ *
+ * The MASK_LAST_WORD() macro defines the value of the last (high
+ * order) word of a bitmask. In particular, for the case of a
+ * mask of a size that is an exact multiple of the word size,
+ * with all bits set, it ensures that this value is all one's,
+ * not all zero's.
+ *
+ * The file include/mask.h applies to all architectures.
+ * Architectures requiring custom details should provide
+ * them in their include/asm-<arch>/bitops.h file, and
+ * if necessary modify the common include/linux/mask.h
+ * file to conditionally generate the necessary code,
+ * depending on compile time settings. No need to write
+ * ugly #ifdef's to do this - gcc provides a rich set
+ * of compile time extensions. See further for example:
+ * http://gcc.gnu.org/onlinedocs/gcc-3.3.3/gcc/C-Extensions.html
+ *
+ * Some architectures (I'm told sparc32) do not pass structures
+ * efficiently as arguments to subroutine calls, even if the
+ * structure is just one word long. If you need to pass
+ * a cpumask or nodemask to a subroutine in a performance
+ * critical path on such an architecture, then as an
+ * alternative, pass the first unsigned long of the mask
+ * directly, using cpus_raw() or nodes_raw(). Of course,
+ * if your masks are more than one word long, this won't
+ * be adequate.
+ */
+
+#include "linux/bitops.h"
+#include "linux/string.h"
+#include "linux/types.h"
+#include "linux/kernel.h"
+#include "linux/bitmap.h"
+
+#define __mask(bits) struct { unsigned long _m[BITS_TO_LONGS(bits)]; }
+
+#define MASK_LAST_WORD(nbits) \
+( \
+ ((nbits) % BITS_PER_LONG) ? \
+ (1<<((nbits) % BITS_PER_LONG))-1 : ~0UL \
+)
+
+#define mask_setbit(bit, mask) \
+ set_bit((bit), (mask)._m)
+
+#define mask_clearbit(bit, mask) \
+ clear_bit((bit), (mask)._m)
+
+#define mask_setall(mask, nbits) \
+do { \
+ size_t sz_all_but_last = sizeof(mask) - sizeof(unsigned long); \
+ if (sz_all_but_last > 0) \
+ memset((mask)._m, 0xff, sz_all_but_last); \
+ (mask)._m[BITS_TO_LONGS(nbits)-1] = MASK_LAST_WORD(nbits); \
+} while(0)
+
+#define mask_clearall(mask) \
+do { \
+ if (sizeof(mask) == sizeof(unsigned long)) \
+ (mask)._m[0] = 0UL; \
+ else \
+ memset((mask)._m, 0, sizeof(mask)); \
+} while(0)
+
+#define mask_isset(bit, mask) \
+ test_bit((bit), (mask)._m)
+
+#define mask_test_and_set(bit, mask) \
+ test_and_set_bit(bit, (mask)._m)
+
+#define mask_and(dst, src1, src2) \
+do { \
+ if (sizeof(dst) == sizeof(unsigned long)) \
+ (dst)._m[0] = (src1)._m[0] & (src2)._m[0]; \
+ else \
+ bitmap_and((dst)._m, (src1)._m, (src2)._m, \
+ sizeof(dst) * 8); \
+} while(0)
+
+#define mask_or(dst, src1, src2) \
+do { \
+ if (sizeof(dst) == sizeof(unsigned long)) \
+ (dst)._m[0] = (src1)._m[0] | (src2)._m[0]; \
+ else \
+ bitmap_or((dst)._m, (src1)._m, (src2)._m, \
+ sizeof(dst) * 8); \
+} while(0)
+
+#define mask_xor(dst, src1, src2) \
+do { \
+ if (sizeof(dst) == sizeof(unsigned long)) \
+ (dst)._m[0] = (src1)._m[0] ^ (src2)._m[0]; \
+ else \
+ bitmap_xor((dst)._m, (src1)._m, (src2)._m, \
+ sizeof(dst) * 8); \
+} while(0)
+
+#define mask_andnot(dst, src1, src2) \
+do { \
+ if (sizeof(dst) == sizeof(unsigned long)) \
+ (dst)._m[0] = (src1)._m[0] & ~(src2)._m[0]; \
+ else \
+ bitmap_andnot((dst)._m, (src1)._m, (src2)._m, \
+ sizeof(dst) * 8); \
+} while(0)
+
+#define mask_complement(dst, src, nbits) \
+ bitmap_complement((dst)._m, (src)._m, nbits)
+
+#define mask_equal(mask1, mask2) \
+({ \
+ int r; \
+ if (sizeof(mask1) == sizeof(unsigned long)) \
+ r = ((mask1)._m[0] == (mask2)._m[0]); \
+ else { \
+ int nbits = sizeof(mask1) * 8; \
+ r = bitmap_equal((mask1)._m, (mask2)._m, (nbits)); \
+ } \
+ r; \
+})
+
+#define mask_intersects(mask1, mask2) \
+({ \
+ int r; \
+ if (sizeof(mask1) == sizeof(unsigned long)) \
+ r = (((mask1)._m[0] & (mask2)._m[0]) != 0); \
+ else { \
+ int nbits = sizeof(mask1) * 8; \
+ r = bitmap_intersects((mask1)._m, (mask2)._m, (nbits)); \
+ } \
+ r; \
+})
+
+#define mask_subset(mask1, mask2) \
+({ \
+ int r; \
+ if (sizeof(mask1) == sizeof(unsigned long)) \
+ r = (((mask1)._m[0] & ~(mask2)._m[0]) == 0); \
+ else { \
+ int nbits = sizeof(mask1) * 8; \
+ r = bitmap_subset((mask1)._m, (mask2)._m, (nbits)); \
+ } \
+ r; \
+})
+
+#define mask_empty(mask) \
+({ \
+ int r; \
+ if (sizeof(mask) == sizeof(unsigned long)) \
+ r = ((mask)._m[0] == 0UL); \
+ else { \
+ int nbits = sizeof(mask) * 8; \
+ r = bitmap_empty((mask)._m, nbits); \
+ } \
+ r; \
+})
+
+#define mask_full(mask, nbits) \
+ bitmap_full((mask)._m, (nbits))
+
+#define mask_weight(mask, nbits) \
+ bitmap_weight((mask)._m, (nbits))
+
+#define mask_shift_right(dst, src, n, nbits) \
+ bitmap_shift_right((dst)._m, (src)._m, (n), (nbits))
+
+#define mask_shift_left(dst, src, n, nbits) \
+ bitmap_shift_left((dst)._m, (src)._m, (n), (nbits))
+
+#define mask_first(mask, nbits) \
+ find_first_bit((mask)._m, (nbits))
+
+#define mask_next(bit, mask, nbits) \
+ find_next_bit((mask)._m, (nbits), (bit)+1)
+
+#define mask_of_bit(bit, T) \
+({ \
+ typeof(T) m; \
+ mask_clearall(m); \
+ mask_setbit((bit), m); \
+ m; \
+})
+
+#define MASK_ALL(nbits) \
+{{ \
+ [0 ... BITS_TO_LONGS(nbits)-1] = ~0UL, \
+ [BITS_TO_LONGS(nbits)-1] = MASK_LAST_WORD(nbits) \
+}}
+
+#define MASK_NONE(nbits) \
+{{ \
+ [0 ... BITS_TO_LONGS(nbits)-1] = 0UL \
+}}
+
+#define mask_raw(mask) \
+ ((mask)._m)
+
+#define mask_scnprintf(buf, len, mask, nbits) \
+ bitmap_scnprintf((buf), (len), ((mask)._m), (nbits))
+
+#define mask_parse(ubuf, ulen, mask, nbits) \
+ bitmap_parse((ubuf), (ulen), ((mask)._m), (nbits))
+
+#endif /* _ASM_GENERIC_MASK_H */