[lkml]   [2017]   [Sep]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
    Patch in this message
    Subject[PATCH v2 02/40] tracing: Add support to detect and avoid duplicates
    From: Vedang Patel <>

    A duplicate in the tracing_map hash table is when 2 different entries
    have the same key and, as a result, the key_hash. This is possible due
    to a race condition in the algorithm. This race condition is inherent to
    the algorithm and not a bug. This was fine because, until now, we were
    only interested in the sum of all the values related to a particular
    key (the duplicates are dealt with in tracing_map_sort_entries()). But,
    with the inclusion of variables[1], we are interested in individual
    values. So, it will not be clear what value to choose when
    there are duplicates. So, the duplicates need to be removed.

    The duplicates can occur in the code in the following scenarios:

    - A thread is in the process of adding a new element. It has
    successfully executed cmpxchg() and inserted the key. But, it is still
    not done acquiring the trace_map_elt struct, populating it and storing
    the pointer to the struct in the value field of tracing_map hash table.
    If another thread comes in at this time and wants to add an element with
    the same key, it will not see the current element and add a new one.

    - There are multiple threads trying to execute cmpxchg at the same time,
    one of the threads will succeed and the others will fail. The ones which
    fail will go ahead increment 'idx' and add a new element there creating
    a duplicate.

    This patch detects and avoids the first condition by asking the thread
    which detects the duplicate to loop one more time. There is also a
    possibility of infinite loop if the thread which is trying to insert
    goes to sleep indefinitely and the one which is trying to insert a new
    element detects a duplicate. Which is why, the thread loops for
    map_size iterations before returning NULL.

    The second scenario is avoided by preventing the threads which failed
    cmpxchg() from incrementing idx. This way, they will loop
    around and check if the thread which succeeded in executing cmpxchg()
    had the same key.

    [1] -

    Signed-off-by: Vedang Patel <>
    kernel/trace/tracing_map.c | 37 +++++++++++++++++++++++++++++++++----
    1 file changed, 33 insertions(+), 4 deletions(-)

    diff --git a/kernel/trace/tracing_map.c b/kernel/trace/tracing_map.c
    index 305039b..437b490 100644
    --- a/kernel/trace/tracing_map.c
    +++ b/kernel/trace/tracing_map.c
    @@ -414,6 +414,7 @@ static inline bool keys_match(void *key, void *test_key, unsigned key_size)
    __tracing_map_insert(struct tracing_map *map, void *key, bool lookup_only)
    u32 idx, key_hash, test_key;
    + int dup_try = 0;
    struct tracing_map_entry *entry;

    key_hash = jhash(key, map->key_size, 0);
    @@ -426,10 +427,31 @@ static inline bool keys_match(void *key, void *test_key, unsigned key_size)
    entry = TRACING_MAP_ENTRY(map->map, idx);
    test_key = entry->key;

    - if (test_key && test_key == key_hash && entry->val &&
    - keys_match(key, entry->val->key, map->key_size)) {
    - atomic64_inc(&map->hits);
    - return entry->val;
    + if (test_key && test_key == key_hash) {
    + if (entry->val &&
    + keys_match(key, entry->val->key, map->key_size)) {
    + atomic64_inc(&map->hits);
    + return entry->val;
    + } else if (unlikely(!entry->val)) {
    + /*
    + * The key is present. But, val (pointer to elt
    + * struct) is still NULL. which means some other
    + * thread is in the process of inserting an
    + * element.
    + *
    + * On top of that, it's key_hash is same as the
    + * one being inserted right now. So, it's
    + * possible that the element has the same
    + * key as well.
    + */
    + dup_try++;
    + if (dup_try > map->map_size) {
    + atomic64_inc(&map->drops);
    + break;
    + }
    + continue;
    + }

    if (!test_key) {
    @@ -451,6 +473,13 @@ static inline bool keys_match(void *key, void *test_key, unsigned key_size)

    return entry->val;
    + } else {
    + /*
    + * cmpxchg() failed. Loop around once
    + * more to check what key was inserted.
    + */
    + dup_try++;
    + continue;

     \ /
      Last update: 2017-09-06 00:09    [W:21.735 / U:0.004 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site