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.

1 files changed, 239 insertions, 53 deletions

diff --git a/bus/signals.c b/bus/signals.c
index c6f122b64..23bf98aa1 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