lkml.org 
[lkml]   [2004]   [Mar]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]
    At some point in the past, I wrote:
    >> No, the existing standard is to treat the unused bits as "don't cares".

    At some point in the past, Paul Jackson wrote:
    > ==> Note of course that the above model(s) are efforts to describe
    > the bitmap/bitop code. The model I provide for my new mask ADT is
    > different - it makes use of the implementation condition above on
    > bitmaps "Zero tails in yield zero tails out", along with an added
    > precondition "Don't pass in masks with nonzero tails" to avoid
    > needing much filtering code.

    I think the difference is maybe one or two lines, but it doesn't matter
    much. If zeroed tails are what you want, by all means, have them. But
    please keep it to one change at a time(e.g. do the standardized
    array-in-struct datatype in a different patch). Also, please document
    the change of invariants. I didn't realize it would become a point of
    confusion and we should avoid repeating this kind of affair.

    I think I failed to convey the entire zeroed tail invariant I described.
    What I wanted to convey did include the precondition of zeroed tails
    for validity and/or satisfying zeroed tail postconditions. I think I
    even meant to go as far as saying not having zeroed tails meant undefined
    behavior, where I suspect you want general validity and zeroed tails
    preserved when present (and actually it would take some effort to barf
    on nonzeroed tails for most of the operations).


    At some point in the past, Paul Jackson wrote:
    > So - would you consent to my bundling the following changes as a single
    > patch - that adds to bitmaps the property that "output tails will be
    > zero if input tails are zero"?
    > 1) Zero unused bits in the *_complement operators.
    > 2) Zero unused bits in CPU_MASK_ALL (multiword).

    I think the change is small enough and transparent enough in general you
    could do the entire invariant conversion for arith and bitmaps as one
    patch. But please document it (possibly with kerneldoc) somewhere
    nearby to where the API's are implemented. I think a couple of lines of
    comments at the top of lib/bitmap.c should be enough if the bitmap
    functions don't rely on zeroed tails for correctness. If some do rely
    on zeroed tails for correctness, that should be in kerneldoc comments
    (e.g. if bitmap_shift_right() needs zeroed tails not to shift in garbage
    from upper bits, that's a gotcha that needs to be documented).

    Part of what led to this confusion in the first place was the assumption
    (likely on my part) that the "don't care" invariant was the most natural
    and not documenting it. Zeroed tails are a stronger condition in general
    and likely make some small optimizations possible if the bitmap functions
    are allowed to produce undefined results for nonzeroed tails (which is an
    okay thing to do, just needs to be a separate change for bisection/testing
    etc. purposes if by some catastrophe something does break).


    -- 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:0.024 / U:1.408 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site