From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752903AbbDDUZ4 (ORCPT ); Sat, 4 Apr 2015 16:25:56 -0400 Received: from mga03.intel.com ([134.134.136.65]:54148 "EHLO mga03.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752528AbbDDUZy (ORCPT ); Sat, 4 Apr 2015 16:25:54 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.11,524,1422950400"; d="scan'208";a="675322203" Message-ID: <1428179149.2610.27.camel@picadillo> Subject: Re: [PATCH v3 5/7] tracing: Add 'hist' event trigger command From: Tom Zanussi To: Alexei Starovoitov Cc: Steven Rostedt , Masami Hiramatsu , Namhyung Kim , Andi Kleen , "linux-kernel@vger.kernel.org" Date: Sat, 04 Apr 2015 15:25:49 -0500 In-Reply-To: References: <9fe50519aa2cac1550b40a0e396dd721eff03574.1428072891.git.tom.zanussi@linux.intel.com> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.10.4 (3.10.4-4.fc20) Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, 2015-04-04 at 08:36 -0700, Alexei Starovoitov wrote: > On Fri, Apr 3, 2015 at 8:51 AM, Tom Zanussi 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