Attachment 28321 Details for Bug 23117 – [PATCH 6/6] Group match rules by their interface.

[patch] [PATCH 6/6] Group match rules by their interface.

0006-Group-match-rules-by-their-interface.patch (text/plain), 13.84 KB, created by Will Thompson on 2009-08-03 11:56:50 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Will Thompson

Created: 2009-08-03 11:56:50 UTC

Size: 13.84 KB

patch

obsolete

>From 023bb6fdc82304866353a28cd503863e80c3ea0d Mon Sep 17 00:00:00 2001
>From: Will Thompson <will.thompson@collabora.co.uk>
>Date: Thu, 30 Jul 2009 10:49:33 +0100
>Subject: [PATCH 6/6] Group match rules by their interface.
>
>In my informal studies of "normal" sets of match rules, only checking
>match rules with the appropriate interface for the message reduces the
>number that need to be checked by almost 100x on average (ranging from
>halving for messages from the bus daemon, to a >200x reduction in many
>cases). This reduces the overhead added to dispatching each message by
>having lots of irrelevant match rules.
>---
> bus/signals.c |  292 ++++++++++++++++++++++++++++++++++++++++++++++-----------
> 1 files changed, 239 insertions(+), 53 deletions(-)
>
>diff --git a/bus/signals.c b/bus/signals.c
>index c6f122b..23bf98a 100644
>--- a/bus/signals.c
>+++ b/bus/signals.c
>@@ -1018,15 +1018,25 @@ bus_match_rule_parse (DBusConnection   *matches_go_to,
>   return rule;
> }
> 
>+typedef struct RulePool RulePool;
>+struct RulePool
>+{
>+  /* Maps non-NULL interface names to non-NULL (DBusList **)s */
>+  DBusHashTable *rules_by_iface;
>+
>+  /* List of BusMatchRules which don't specify an interface */
>+  DBusList *rules_without_iface;
>+};
>+
> struct BusMatchmaker
> {
>   int refcount;
> 
>-  /* lists of rules, grouped by the type of message they match. 0
>+  /* Pools of rules, grouped by the type of message they match. 0
>    * (DBUS_MESSAGE_TYPE_INVALID) represents rules that do not specify a message
>    * type.
>    */
>-  DBusList *rules_by_type[DBUS_NUM_MESSAGE_TYPES];
>+  RulePool rules_by_type[DBUS_NUM_MESSAGE_TYPES];
> };
> 
> static void
>@@ -1042,28 +1052,139 @@ rule_list_free (DBusList **rules)
>     }
> }
> 
>+static void
>+rule_list_ptr_free (DBusList **list)
>+{
>+  /* We have to cope with NULL because the hash table frees the "existing"
>+   * value (which is NULL) when creating a new table entry...
>+   */
>+  if (list != NULL)
>+    {
>+      rule_list_free (list);
>+      dbus_free (list);
>+    }
>+}
>+
> BusMatchmaker*
> bus_matchmaker_new (void)
> {
>   BusMatchmaker *matchmaker;
>+  int i;
> 
>   matchmaker = dbus_new0 (BusMatchmaker, 1);
>   if (matchmaker == NULL)
>     return NULL;
> 
>   matchmaker->refcount = 1;
>-  
>+
>+  for (i = DBUS_MESSAGE_TYPE_INVALID; i < DBUS_NUM_MESSAGE_TYPES; i++)
>+    {
>+      RulePool *p = matchmaker->rules_by_type + i;
>+
>+      p->rules_by_iface = _dbus_hash_table_new (DBUS_HASH_STRING,
>+          dbus_free, (DBusFreeFunction) rule_list_ptr_free);
>+
>+      if (p->rules_by_iface == NULL)
>+        goto nomem;
>+    }
>+
>   return matchmaker;
>+
>+ nomem:
>+  for (i = DBUS_MESSAGE_TYPE_INVALID; i < DBUS_NUM_MESSAGE_TYPES; i++)
>+    {
>+      RulePool *p = matchmaker->rules_by_type + i;
>+
>+      if (p->rules_by_iface == NULL)
>+        break;
>+      else
>+        _dbus_hash_table_unref (p->rules_by_iface);
>+    }
>+
>+  return NULL;
> }
> 
> static DBusList **
> bus_matchmaker_get_rules (BusMatchmaker *matchmaker,
>-                          int            message_type)
>+                          int            message_type,
>+                          const char    *interface,
>+                          dbus_bool_t    create)
> {
>+  RulePool *p;
>+
>   _dbus_assert (message_type >= 0);
>   _dbus_assert (message_type < DBUS_NUM_MESSAGE_TYPES);
> 
>-  return matchmaker->rules_by_type + message_type;
>+  _dbus_verbose ("Looking up rules for message_type %d, interface %s\n",
>+                 message_type,
>+                 interface != NULL ? interface : "<null>");
>+
>+  p = matchmaker->rules_by_type + message_type;
>+
>+  if (interface == NULL)
>+    {
>+      return &p->rules_without_iface;
>+    }
>+  else
>+    {
>+      DBusList **list;
>+
>+      list = _dbus_hash_table_lookup_string (p->rules_by_iface, interface);
>+
>+      if (list == NULL && create)
>+        {
>+          char *dupped_interface;
>+
>+          list = dbus_new0 (DBusList *, 1);
>+          if (list == NULL)
>+            return NULL;
>+
>+          dupped_interface = _dbus_strdup (interface);
>+          if (dupped_interface == NULL)
>+            {
>+              dbus_free (list);
>+              return NULL;
>+            }
>+
>+          _dbus_verbose ("Adding list for type %d, iface %s\n", message_type,
>+                         interface);
>+
>+          if (!_dbus_hash_table_insert_string (p->rules_by_iface,
>+                                               dupped_interface, list))
>+            {
>+              dbus_free (list);
>+              dbus_free (dupped_interface);
>+              return NULL;
>+            }
>+        }
>+
>+      return list;
>+    }
>+}
>+
>+static void
>+bus_matchmaker_gc_rules (BusMatchmaker *matchmaker,
>+                         int            message_type,
>+                         const char    *interface,
>+                         DBusList     **rules)
>+{
>+  RulePool *p;
>+
>+  if (interface == NULL)
>+    return;
>+
>+  if (*rules != NULL)
>+    return;
>+
>+  _dbus_verbose ("GCing HT entry for message_type %u, interface %s\n",
>+                 message_type, interface);
>+
>+  p = matchmaker->rules_by_type + message_type;
>+
>+  _dbus_assert (_dbus_hash_table_lookup_string (p->rules_by_iface, interface)
>+      == rules);
>+
>+  _dbus_hash_table_remove_string (p->rules_by_iface, interface);
> }
> 
> BusMatchmaker *
>@@ -1087,7 +1208,12 @@ bus_matchmaker_unref (BusMatchmaker *matchmaker)
>       int i;
> 
>       for (i = DBUS_MESSAGE_TYPE_INVALID; i < DBUS_NUM_MESSAGE_TYPES; i++)
>-        rule_list_free (bus_matchmaker_get_rules (matchmaker, i));
>+        {
>+          RulePool *p = matchmaker->rules_by_type + i;
>+
>+          _dbus_hash_table_unref (p->rules_by_iface);
>+          rule_list_free (&p->rules_without_iface);
>+        }
> 
>       dbus_free (matchmaker);
>     }
>@@ -1102,7 +1228,15 @@ bus_matchmaker_add_rule (BusMatchmaker   *matchmaker,
> 
>   _dbus_assert (bus_connection_is_active (rule->matches_go_to));
> 
>-  rules = bus_matchmaker_get_rules (matchmaker, rule->message_type);
>+  _dbus_verbose ("Adding rule with message_type %d, interface %s\n",
>+                 rule->message_type,
>+                 rule->interface != NULL ? rule->interface : "<null>");
>+
>+  rules = bus_matchmaker_get_rules (matchmaker, rule->message_type,
>+                                    rule->interface, TRUE);
>+
>+  if (rules == NULL)
>+    return FALSE;
> 
>   if (!_dbus_list_append (rules, rule))
>     return FALSE;
>@@ -1110,9 +1244,11 @@ bus_matchmaker_add_rule (BusMatchmaker   *matchmaker,
>   if (!bus_connection_add_match_rule (rule->matches_go_to, rule))
>     {
>       _dbus_list_remove_last (rules, rule);
>+      bus_matchmaker_gc_rules (matchmaker, rule->message_type,
>+                               rule->interface, rules);
>       return FALSE;
>     }
>-  
>+
>   bus_match_rule_ref (rule);
> 
> #ifdef DBUS_ENABLE_VERBOSE_MODE
>@@ -1224,10 +1360,23 @@ bus_matchmaker_remove_rule (BusMatchmaker   *matchmaker,
> {
>   DBusList **rules;
> 
>+  _dbus_verbose ("Removing rule with message_type %d, interface %s\n",
>+                 rule->message_type,
>+                 rule->interface != NULL ? rule->interface : "<null>");
>+
>   bus_connection_remove_match_rule (rule->matches_go_to, rule);
> 
>-  rules = bus_matchmaker_get_rules (matchmaker, rule->message_type);
>+  rules = bus_matchmaker_get_rules (matchmaker, rule->message_type,
>+                                    rule->interface, FALSE);
>+
>+  /* We should only be asked to remove a rule by identity right after it was
>+   * added, so there should be a list for it.
>+   */
>+  _dbus_assert (rules != NULL);
>+
>   _dbus_list_remove (rules, rule);
>+  bus_matchmaker_gc_rules (matchmaker, rule->message_type, rule->interface,
>+      rules);
> 
> #ifdef DBUS_ENABLE_VERBOSE_MODE
>   {
>@@ -1248,31 +1397,38 @@ bus_matchmaker_remove_rule_by_value (BusMatchmaker   *matchmaker,
>                                      BusMatchRule    *value,
>                                      DBusError       *error)
> {
>-  /* FIXME this is an unoptimized linear scan */
>   DBusList **rules;
>-  DBusList *link;
>+  DBusList *link = NULL;
> 
>-  rules = bus_matchmaker_get_rules (matchmaker, value->message_type);
>+  _dbus_verbose ("Removing rule by value with message_type %d, interface %s\n",
>+                 value->message_type,
>+                 value->interface != NULL ? value->interface : "<null>");
> 
>-  /* we traverse backward because bus_connection_remove_match_rule()
>-   * removes the most-recently-added rule
>-   */
>-  link = _dbus_list_get_last_link (rules);
>-  while (link != NULL)
>+  rules = bus_matchmaker_get_rules (matchmaker, value->message_type,
>+      value->interface, FALSE);
>+
>+  if (rules != NULL)
>     {
>-      BusMatchRule *rule;
>-      DBusList *prev;
>+      /* we traverse backward because bus_connection_remove_match_rule()
>+       * removes the most-recently-added rule
>+       */
>+      link = _dbus_list_get_last_link (rules);
>+      while (link != NULL)
>+        {
>+          BusMatchRule *rule;
>+          DBusList *prev;
> 
>-      rule = link->data;
>-      prev = _dbus_list_get_prev_link (rules, link);
>+          rule = link->data;
>+          prev = _dbus_list_get_prev_link (rules, link);
> 
>-      if (match_rule_equal (rule, value))
>-        {
>-          bus_matchmaker_remove_rule_link (rules, link);
>-          break;
>-        }
>+          if (match_rule_equal (rule, value))
>+            {
>+              bus_matchmaker_remove_rule_link (rules, link);
>+              break;
>+            }
> 
>-      link = prev;
>+          link = prev;
>+        }
>     }
> 
>   if (link == NULL)
>@@ -1282,6 +1438,9 @@ bus_matchmaker_remove_rule_by_value (BusMatchmaker   *matchmaker,
>       return FALSE;
>     }
> 
>+  bus_matchmaker_gc_rules (matchmaker, value->message_type, value->interface,
>+      rules);
>+
>   return TRUE;
> }
> 
>@@ -1341,16 +1500,29 @@ bus_matchmaker_disconnected (BusMatchmaker   *matchmaker,
>    * for the rules belonging to the connection, since we keep
>    * a list of those; but for the rules that just refer to
>    * the connection we'd need to do something more elaborate.
>-   * 
>    */
>-  
>+
>   _dbus_assert (bus_connection_is_active (disconnected));
> 
>+  _dbus_verbose ("Removing all rules for connection %p\n", disconnected);
>+
>   for (i = DBUS_MESSAGE_TYPE_INVALID; i < DBUS_NUM_MESSAGE_TYPES; i++)
>     {
>-      DBusList **rules = bus_matchmaker_get_rules (matchmaker, i);
>+      RulePool *p = matchmaker->rules_by_type + i;
>+      DBusHashIter iter;
>+
>+      rule_list_remove_by_connection (&p->rules_without_iface, disconnected);
>+
>+      _dbus_hash_iter_init (p->rules_by_iface, &iter);
>+      while (_dbus_hash_iter_next (&iter))
>+        {
>+          DBusList **items = _dbus_hash_iter_get_value (&iter);
> 
>-      rule_list_remove_by_connection (rules, disconnected);
>+          rule_list_remove_by_connection (items, disconnected);
>+
>+          if (*items == NULL)
>+            _dbus_hash_iter_remove_entry (&iter);
>+        }
>     }
> }
> 
>@@ -1565,6 +1737,9 @@ get_recipients_from_list (DBusList       **rules,
> {
>   DBusList *link;
> 
>+  if (rules == NULL)
>+    return TRUE;
>+
>   link = _dbus_list_get_first_link (rules);
>   while (link != NULL)
>     {
>@@ -1581,10 +1756,10 @@ get_recipients_from_list (DBusList       **rules,
>         dbus_free (s);
>       }
> #endif
>-      
>+
>       if (match_rule_matches (rule,
>                               sender, addressed_recipient, message,
>-                              BUS_MATCH_MESSAGE_TYPE))
>+                              BUS_MATCH_MESSAGE_TYPE | BUS_MATCH_INTERFACE))
>         {
>           _dbus_verbose ("Rule matched\n");
> 
>@@ -1616,12 +1791,9 @@ bus_matchmaker_get_recipients (BusMatchmaker   *matchmaker,
>                                DBusMessage     *message,
>                                DBusList       **recipients_p)
> {
>-  /* FIXME for now this is a wholly unoptimized linear search */
>-  /* Guessing the important optimization is to skip the signal-related
>-   * match lists when processing method call and exception messages.
>-   * So separate match rule lists for signals?
>-   */
>   int type;
>+  const char *interface;
>+  DBusList **neither, **just_type, **just_iface, **both;
> 
>   _dbus_assert (*recipients_p == NULL);
> 
>@@ -1638,25 +1810,39 @@ bus_matchmaker_get_recipients (BusMatchmaker   *matchmaker,
>   if (addressed_recipient != NULL)
>     bus_connection_mark_stamp (addressed_recipient);
> 
>-  /* We always need to try the rules that don't specify a message type */
>-  if (!get_recipients_from_list (
>-          bus_matchmaker_get_rules (matchmaker, DBUS_MESSAGE_TYPE_INVALID),
>-          sender, addressed_recipient, message, recipients_p))
>-    goto nomem;
>-
>-  /* Also try rules that match the type of this message */
>   type = dbus_message_get_type (message);
>+  interface = dbus_message_get_interface (message);
>+
>+  neither = bus_matchmaker_get_rules (matchmaker, DBUS_MESSAGE_TYPE_INVALID,
>+      NULL, FALSE);
>+  just_type = just_iface = both = NULL;
>+
>+  if (interface != NULL)
>+    just_iface = bus_matchmaker_get_rules (matchmaker,
>+        DBUS_MESSAGE_TYPE_INVALID, interface, FALSE);
>+
>   if (type > DBUS_MESSAGE_TYPE_INVALID && type < DBUS_NUM_MESSAGE_TYPES)
>-    if (!get_recipients_from_list (
>-            bus_matchmaker_get_rules (matchmaker, type),
>-            sender, addressed_recipient, message, recipients_p))
>-      goto nomem;
>+    {
>+      just_type = bus_matchmaker_get_rules (matchmaker, type, NULL, FALSE);
> 
>-  return TRUE;
>+      if (interface != NULL)
>+        both = bus_matchmaker_get_rules (matchmaker, type, interface, FALSE);
>+    }
> 
>- nomem:
>-  _dbus_list_clear (recipients_p);
>-  return FALSE;
>+  if (!(get_recipients_from_list (neither, sender, addressed_recipient,
>+                                  message, recipients_p) &&
>+        get_recipients_from_list (just_iface, sender, addressed_recipient,
>+                                  message, recipients_p) &&
>+        get_recipients_from_list (just_type, sender, addressed_recipient,
>+                                  message, recipients_p) &&
>+        get_recipients_from_list (both, sender, addressed_recipient,
>+                                  message, recipients_p)))
>+    {
>+      _dbus_list_clear (recipients_p);
>+      return FALSE;
>+    }
>+
>+  return TRUE;
> }
> 
> #ifdef DBUS_BUILD_TESTS
>-- 
>1.6.3.3
>

Actions: View | Splinter Review

Attachments on bug 23117: 28316 | 28317 | 28318 | 28319 | 28320 | 28321 | 28377 | 29176

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.