lkml.org 
[lkml]   [2004]   [Mar]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] mask ADT: new mask.h file [2/22]
    On Mon, 2004-03-29 at 04:12, Paul Jackson wrote:
    >>> * 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.

    On Mon, Mar 29, 2004 at 04:30:18PM -0800, Matthew Dobson wrote:
    > bitmap_and() & bitmap_or() *do not* mask off the unused input bits.
    > Unless you add that code in a subsequent patch... This paragraph seems
    > a bit unclear. You're saying that bitmap_and() & bitmap_or() *don't*
    > follow the precondition, but *do* mask off unused bits, which I'm not
    > seeing. Then the 'however' is confusing, because you continue with the
    > same point about *not* following preconditions. Maybe something like:

    They actually don't need to. The cases where "or" gives rise to the need
    to do a fixup pass is only when the second operand is complemented. If
    both the inputs satisfy the trailing zero precondition, it's already
    guaranteed that bitmap_or()'s result will do likewise as a
    postcondition. If _either_ of the inputs to bitmap_and() satisfy the
    trailing zero precondition, its result will also satisfy the trailing
    zero postcondition.

    This is all assuming the trailing zero invariant; the "don't care"
    invariant behaves very differently and incurs its checks only at the
    time of examinations whose underlying implementations operate on whole
    words, like cpus_equal(), cpus_weight(), and cpus_empty().

    For the single-word case, something like this is required for mainline:
    #if NR_CPUS % BITS_PER_LONG
    #define __CPU_VALID_BITS__ (~((1UL << (NR_CPUS % BITS_PER_LONG)) - 1))
    #else
    #define __CPU_VALID_BITS__ (~0UL)
    #endif

    #define cpus_equal(x,y) (!(((x) ^ (y)) & __CPU_VALID_BITS__))
    #define cpus_empty(x) (!((x) & __CPU_VALID_BITS__))
    #define cpus_coerce(x) ((unsigned long)(x) & __CPU_VALID_BITS__)
    #if BITS_PER_LONG == 32
    #define cpus_weight(x) hweight32((x) & __CPU_VALID_BITS__)
    #else
    #define cpus_weight(x) hweight64((x) & __CPU_VALID_BITS__)
    #endif

    ... and all other operations unmodified. In all honesty, the difference
    in overhead and/or implementation complexity between the two invariants
    is miniscule. I don't care who wants what per se; if you want to change
    that invariant, it's not my concern what the invariant is so long as
    it's respected and there's a coherent notion of what people want it to
    be. Given some of your statements, I wonder sometimes if you actually
    understand the "don't care" invariant.

    The patch series is a little clunky though. e.g. the cpus_raw()
    renaming has zero semantic effect, where the cpus_complement() API
    change should probably move people to a renamed function (e.g. dyadic
    cpus_not() or some such) so callers can be incrementally converted, it
    looks like there are points in the series where various things won't
    compile etc. but otherwise innocuous. The really hard questions will
    come when those with real concerns about the operational semantics
    start coming out of the woodwork. Actually, why don't you start
    by asking Ray Bryant, since it was prodding from him about codegen
    results directly contradicting yours that originally instigated the
    apparently reviled cpumask_const_t. A coherent story out of SGI (e.g.
    not so many contradictory statements from different people) would
    probably help and/or would have helped get this right the first time.


    -- wli
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:02    [W:4.721 / U:0.112 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site