lkml.org 
[lkml]   [2009]   [Jun]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[patch 025/108] dma-debug: change hash_bucket_find from first-fit to best-fit
    2.6.30-stable review patch.  If anyone has any objections, please let us know.

    ------------------

    From: Joerg Roedel <joerg.roedel@amd.com>

    commit 7caf6a49bb17d0377210693af5737563b31aa5ee upstream.

    Some device drivers map the same physical address multiple times to a
    dma address. Without an IOMMU this results in the same dma address being
    put into the dma-debug hash multiple times. With a first-fit match in
    hash_bucket_find() this function may return the wrong dma_debug_entry.

    This can result in false positive warnings. This patch fixes it by
    changing the first-fit behavior of hash_bucket_find() into a best-fit
    algorithm.

    Reported-by: Torsten Kaiser <just.for.lkml@googlemail.com>
    Reported-by: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
    Signed-off-by: Joerg Roedel <joerg.roedel@amd.com>
    Cc: lethal@linux-sh.org
    Cc: just.for.lkml@googlemail.com
    Cc: hancockrwd@gmail.com
    Cc: jens.axboe@oracle.com
    Cc: bharrosh@panasas.com
    Cc: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    LKML-Reference: <20090605104132.GE24836@amd.com>
    Signed-off-by: Ingo Molnar <mingo@elte.hu>
    Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>

    ---
    lib/dma-debug.c | 43 +++++++++++++++++++++++++++++++++++++++----
    1 file changed, 39 insertions(+), 4 deletions(-)

    --- a/lib/dma-debug.c
    +++ b/lib/dma-debug.c
    @@ -185,15 +185,50 @@ static void put_hash_bucket(struct hash_
    static struct dma_debug_entry *hash_bucket_find(struct hash_bucket *bucket,
    struct dma_debug_entry *ref)
    {
    - struct dma_debug_entry *entry;
    + struct dma_debug_entry *entry, *ret = NULL;
    + int matches = 0, match_lvl, last_lvl = 0;

    list_for_each_entry(entry, &bucket->list, list) {
    - if ((entry->dev_addr == ref->dev_addr) &&
    - (entry->dev == ref->dev))
    + if ((entry->dev_addr != ref->dev_addr) ||
    + (entry->dev != ref->dev))
    + continue;
    +
    + /*
    + * Some drivers map the same physical address multiple
    + * times. Without a hardware IOMMU this results in the
    + * same device addresses being put into the dma-debug
    + * hash multiple times too. This can result in false
    + * positives being reported. Therfore we implement a
    + * best-fit algorithm here which returns the entry from
    + * the hash which fits best to the reference value
    + * instead of the first-fit.
    + */
    + matches += 1;
    + match_lvl = 0;
    + entry->size == ref->size ? ++match_lvl : match_lvl;
    + entry->type == ref->type ? ++match_lvl : match_lvl;
    + entry->direction == ref->direction ? ++match_lvl : match_lvl;
    +
    + if (match_lvl == 3) {
    + /* perfect-fit - return the result */
    return entry;
    + } else if (match_lvl > last_lvl) {
    + /*
    + * We found an entry that fits better then the
    + * previous one
    + */
    + last_lvl = match_lvl;
    + ret = entry;
    + }
    }

    - return NULL;
    + /*
    + * If we have multiple matches but no perfect-fit, just return
    + * NULL.
    + */
    + ret = (matches == 1) ? ret : NULL;
    +
    + return ret;
    }

    /*



    \
     
     \ /
      Last update: 2009-07-01 03:09    [W:0.027 / U:31.016 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site