On Sat, 2015-04-04 at 08:36 -0700, Alexei Starovoitov wrote: > On Fri, Apr 3, 2015 at 8:51 AM, Tom Zanussi <tom.zanu...@linux.intel.com> > wrote: > > +static struct hist_trigger_entry * > > +tracing_map_insert(struct tracing_map *map, void *key) > > +{ > > + u32 idx, key_hash, test_key; > > + > > + key_hash = jhash(key, map->key_size, 0); > > + idx = key_hash >> (32 - (map->map_bits + 1)); > > + > > + while (1) { > > + idx &= (map->map_size - 1); > > + test_key = map->map[idx].key; > > + > > + if (test_key && test_key == key_hash && > > + keys_match(key, map->map[idx].val->key, map->key_size)) > > + return map->map[idx].val; > > + > > + if (!test_key && !cmpxchg(&map->map[idx].key, 0, key_hash)) > > { > > + struct hist_trigger_entry *entry; > > + > > + entry = hist_trigger_entry_create(map); > > + if (!entry) > > + break; > > + memcpy(entry->key, key, map->key_size); > > + map->map[idx].val = entry; > > + > > + return map->map[idx].val; > > + } > > There is obvious race here, since algorithm is not implemented correctly. > Partially inserted key/value is not handled.
You're right, thanks for pointing it out. I guess adding '&& map->map[idx].val && keys_match(...' would fix the problem, but would result in duplicate entries for the same key, which I wanted to avoid. My original code didn't even have that keys_match() check, which is only there for the rare possibility of a key collision - I originally just set a flag in that case, which was printed out with the run results. In all my testing I only ever saw it once, so I know it happens very rarely, but it does happen, and the flag lets the user know and to maybe try again (my second run of the same test didn't show a collision). I thought of actually tracking the collisions as well, since they're so rare, but didn't see that it was worth the bother. Using a 64-bit hash would make it even more remote, but again, is it necessary in practice? So I think there are several solutions - I'll probably just keep things simple and go back to a collision flag.. Tom -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/