On Fri, Feb 22, 2019 at 8:36 PM Ben Pfaff <[email protected]> wrote:
>
> On Fri, Feb 22, 2019 at 07:31:59PM -0800, Han Zhou wrote:
> > On Fri, Feb 22, 2019 at 5:27 PM Ben Pfaff <[email protected]> wrote:
> > >
> > > On Fri, Feb 22, 2019 at 05:21:51PM -0800, Han Zhou wrote:
> > > > On Fri, Feb 22, 2019 at 3:04 PM Ben Pfaff <[email protected]> wrote:
> > > > >
> > > > > Using HMAP_FOR_EACH_SAFE_WITH_HASH tends to imply that an hmap can
> > > > > have
> > > > > more than one item with a given key. Nothing prevents that, and it
> > > > > will
> > > > > otherwise work, but it is unusual and it normally makes sense to use
> > > > > an
> > > > > hindex instead of an hmap for efficiency's sake if it is going to
> > > > > happen
> > > > > very often. Does the data structure in question often have
> > > > > duplicates?
> > > > > Should we change it to an hindex?
> > > >
> > > > Hi Ben, I think you are asking if there can be more than one item with
> > > > a given "hash value". Yes it is possible, but it should not be often
> > > > for the data structure in question here - the json cache. The key is
> > > > uuid of the change set combined with monitor version, and the hash is
> > > > the uuid_hash. So conflicts of uuid_hash should be rare. When there
> > > > are different versions (e.g. monitor v1, v2, v3) of clients referring
> > > > same change sets we do get more items with same hash value, but there
> > > > were at most 2 versions and I am adding 1 more in next patches in the
> > > > series, and I guess it is not likely we add too many versions of
> > > > monitors in the future, and even that is possible, it is unlikely that
> > > > many different versions of clients co-exists in same environment. So I
> > > > don't think it has a real impact to performance.
> > > >
> > > > The reason for using HMAP_FOR_EACH_SAFE_WITH_HASH instead of
> > > > HMAP_FOR_EACH_WITH_HASH is just because the node is going to be
> > > > removed and freed in the loop. It needs to be safe regardless of the
> > > > probability of hash conflicts.
> > >
> > > It's important to be clear about the difference between hashes and keys.
> > > The hash is what's stored in the hmap_node (that is, the uuid_hash()
> > > return value in this case), the key in this case is what uuid_equals()
> > > compares. I *think* you are saying there can be a small number of
> > > duplicate keys in the hmap in this case. Is that correct?
> >
> > I thought you were talking about hashes instead of keys (I thought it
> > was a typo), because I assume keys are always unique.
> > Let me clarify a little more. In the json_cache hmap, the key is the
> > combination of <change_set_uuid, version> of the struct
> > ovsdb_monitor_json_cache_node. This key uniquely identifies each
> > element in the hmap. The hash function doesn't take version into the
> > hash calculation, so if there are multiple versions of clients exist
> > at the same time, there will be different elements with same hash.
> > However, since the number of versions should be very small (worse case
> > 3, most cases 1), this is not going to cause any performance problem.
> > There do exist probability of hash conflict even if there is only one
> > version, but the chances are very low (ensured by uuid_hash).
> >
> > Now for the function:
> > +/* Free all versions of json cache for a given change_set.*/
> > +static void
> > +ovsdb_monitor_json_cache_destroy(struct ovsdb_monitor *dbmon,
> > + struct ovsdb_monitor_change_set
> > *change_set)
> >
> > It is different from a general function that destroys an element in a
> > hmap with the unique key. Instead, it destroys *all versions* of the
> > json cache for a given change_set uuid. So it uses only part of the
> > key to do the search, which may have caused some confusion.
>
> Ah. This is an unusual combination of factors. Very unusual in fact.
> If it is something we really want, then I think that it should be
> carefully documented in a comment on the data structure.
I agree. This trick introduces confusion without obvious benefit, and
the HMAP_FOR_EACH_SAFE_WITH_HASH is not really necessary. Instead of
playing tricks with the keys, I can simply use the search function to
find the nodes for all versions and destroy them if exists. Please see
below change on top of the current one. I will submit it as v3 if it
looks better.
------8><-------------------------------------><8--------
diff --git a/include/openvswitch/hmap.h b/include/openvswitch/hmap.h
index e4fc9a4..8aea9c2 100644
--- a/include/openvswitch/hmap.h
+++ b/include/openvswitch/hmap.h
@@ -144,15 +144,6 @@ struct hmap_node *hmap_random_node(const struct hmap *);
(NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) || (NODE = NULL); \
ASSIGN_CONTAINER(NODE, hmap_next_in_bucket(&(NODE)->MEMBER), MEMBER))
-/* Safe when NODE may be freed (not needed when NODE may be removed from the
- * hash map but its members remain accessible and intact). */
-#define HMAP_FOR_EACH_SAFE_WITH_HASH(NODE, NEXT, MEMBER, HASH, HMAP) \
- for (INIT_CONTAINER(NODE, hmap_first_with_hash(HMAP, HASH), MEMBER); \
- ((NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) || (NODE = NULL) \
- ? INIT_CONTAINER(NEXT, hmap_next_with_hash(&(NODE)->MEMBER), \
- MEMBER), 1 : 0); \
- (NODE) = (NEXT))
-
static inline struct hmap_node *hmap_first_with_hash(const struct hmap *,
size_t hash);
static inline struct hmap_node *hmap_next_with_hash(const struct hmap_node *);
diff --git a/ovsdb/monitor.c b/ovsdb/monitor.c
index 9d74770..03be5dc 100644
--- a/ovsdb/monitor.c
+++ b/ovsdb/monitor.c
@@ -205,13 +205,20 @@ static void ovsdb_monitor_change_set_destroy(
struct ovsdb_monitor_change_set *);
static void ovsdb_monitor_track_new_change_set(struct ovsdb_monitor *);
+static uint32_t
+json_cache_hash(enum ovsdb_monitor_version version,
+ struct ovsdb_monitor_change_set *change_set)
+{
+ return hash_uint64_basis(version, uuid_hash(&change_set->uuid));
+}
+
static struct ovsdb_monitor_json_cache_node *
ovsdb_monitor_json_cache_search(const struct ovsdb_monitor *dbmon,
enum ovsdb_monitor_version version,
struct ovsdb_monitor_change_set *change_set)
{
struct ovsdb_monitor_json_cache_node *node;
- uint32_t hash = uuid_hash(&change_set->uuid);
+ uint32_t hash = json_cache_hash(version, change_set);
HMAP_FOR_EACH_WITH_HASH(node, hmap_node, hash, &dbmon->json_cache) {
if (uuid_equals(&node->change_set_uuid, &change_set->uuid) &&
@@ -230,7 +237,7 @@ ovsdb_monitor_json_cache_insert(struct ovsdb_monitor *dbmon,
struct json *json)
{
struct ovsdb_monitor_json_cache_node *node;
- uint32_t hash = uuid_hash(&change_set->uuid);
+ uint32_t hash = json_cache_hash(version, change_set);
node = xmalloc(sizeof *node);
@@ -257,12 +264,11 @@ static void
ovsdb_monitor_json_cache_destroy(struct ovsdb_monitor *dbmon,
struct ovsdb_monitor_change_set *change_set)
{
- struct ovsdb_monitor_json_cache_node *node, *next;
- uint32_t hash = uuid_hash(&change_set->uuid);
-
- HMAP_FOR_EACH_SAFE_WITH_HASH (node, next, hmap_node, hash,
- &dbmon->json_cache) {
- if (uuid_equals(&node->change_set_uuid, &change_set->uuid)) {
+ enum ovsdb_monitor_version v;
+ for (v = OVSDB_MONITOR_V1; v < OVSDB_MONITOR_VERSION_MAX; v++) {
+ struct ovsdb_monitor_json_cache_node *node
+ = ovsdb_monitor_json_cache_search(dbmon, v, change_set);
+ if (node) {
hmap_remove(&dbmon->json_cache, &node->hmap_node);
json_destroy(node->json);
free(node);
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
