bus/policy: separate prefix rules in default context

To handle prefix rules stored with all other rules in the default context
we need to match each prefix of each name against policy rules.
That's because names are looked up in the hash tables, so we can
miss a prefix rule for a prefix of the name.

However, if prefix rules are separated from non-prefix rules, we
can simply check them all once for each name, and also check hash tables once
for each name.

This is what this commit changes. It separates prefix rules
from non-prefix rules, and handles them in sequence.

This gives a little boost, especially if there are no prefix rules.

Change-Id: Ifade906d35af96a973920ce9c2f6065f5b9b549e

diff --git a/bus/policy.c b/bus/policy.c
index 606d9a8..4bd9868 100644 (file)
--- a/bus/policy.c
+++ b/bus/policy.c
@@ -155,6 +155,7 @@ struct BusPolicy
   DBusList *at_console_false_rules; /**< console user policy rules where at_console="false"*/
 
   DBusHashTable *default_rules_by_name;
+  DBusList *default_prefix_rules;
   unsigned int n_default_rules;
 };
 
@@ -233,7 +234,7 @@ bus_policy_new (void)
     goto failed;
 
   return policy;
-  
+
  failed:
   bus_policy_unref (policy);
   return NULL;
@@ -288,6 +289,9 @@ bus_policy_unref (BusPolicy *policy)
           policy->default_rules_by_name = NULL;
         }
 
+      _dbus_list_foreach (&policy->default_prefix_rules, free_rule_func, NULL);
+      _dbus_list_clear (&policy->default_prefix_rules);
+
       dbus_free (policy);
     }
 }
@@ -490,6 +494,17 @@ get_name_from_rule (BusPolicyRule *rule)
   return name;
 }
 
+static dbus_bool_t
+is_prefix_rule (BusPolicyRule *rule)
+{
+  if (rule->type == BUS_POLICY_RULE_SEND && rule->d.send.destination_prefix)
+    return TRUE;
+  if (rule->type == BUS_POLICY_RULE_OWN && rule->d.own.prefix)
+    return TRUE;
+
+  return FALSE;
+}
+
 dbus_bool_t
 bus_policy_append_default_rule (BusPolicy      *policy,
                                 BusPolicyRule  *rule)
@@ -501,22 +516,31 @@ bus_policy_append_default_rule (BusPolicy      *policy,
     }
   else
     {
-      DBusList **list;
-      BusPolicyRulesWithScore *rules;
+      rule->score = ++policy->n_default_rules;
 
-      rules = get_rules_by_string (policy->default_rules_by_name,
-                                   get_name_from_rule (rule));
+      if (is_prefix_rule (rule))
+        {
+          if (!_dbus_list_append (&policy->default_prefix_rules, rule))
+            return FALSE;
+        }
+      else
+        {
+          DBusList **list;
+          BusPolicyRulesWithScore *rules;
 
-      if (rules == NULL)
-        return FALSE;
+          rules = get_rules_by_string (policy->default_rules_by_name,
+                                       get_name_from_rule (rule));
 
-      list = &rules->rules;
+          if (rules == NULL)
+            return FALSE;
 
-      if (!_dbus_list_prepend (list, rule))
-        return FALSE;
+          list = &rules->rules;
 
-      rule->score = ++policy->n_default_rules;
-      rules->score = rule->score;
+          if (!_dbus_list_prepend (list, rule))
+            return FALSE;
+
+          rules->score = rule->score;
+        }
     }
 
   bus_policy_rule_ref (rule);
@@ -775,6 +799,10 @@ bus_policy_merge (BusPolicy *policy,
                           to_absorb->default_rules_by_name))
     return FALSE;
 
+  if (!append_copy_of_policy_list (&policy->default_prefix_rules,
+                                   &to_absorb->default_prefix_rules))
+    return FALSE;
+
   return TRUE;
 }
 
@@ -1215,34 +1243,28 @@ check_rules_list (const DBusList   *rules,
 }
 
 static int
-check_rules_for_name (DBusHashTable  *rules,
-                      const char     *name,
-                      int             score,
-                      CheckRuleFunc   check_func,
-                      const void     *params,
-                      dbus_int32_t   *toggles,
-                      dbus_bool_t    *log,
-                      BusResult      *result,
-                      const char    **privilege,
-                      BusPolicyRule **matched_rule)
+check_rules_list_with_score (DBusList         *rules,
+                             int               score,
+                             CheckRuleFunc     check_func,
+                             const RuleParams *params,
+                             dbus_int32_t     *toggles,
+                             dbus_bool_t      *log,
+                             BusResult        *result,
+                             const char      **privilege,
+                             BusPolicyRule   **matched_rule,
+                             dbus_bool_t       break_on_first_match)
 {
   dbus_int32_t local_toggles;
   dbus_bool_t local_log;
   BusResult local_result;
   const char *local_privilege;
   BusPolicyRule *local_matched_rule;
-  const BusPolicyRulesWithScore *rules_list;
-
-  rules_list = _dbus_hash_table_lookup_string (rules, name);
-
-  if (rules_list == NULL || rules_list->score <= score)
-    return score;
 
   local_toggles = 0;
 
-  check_rules_list (rules_list->rules, check_func, params,
+  check_rules_list (rules, check_func, params,
                     &local_toggles, &local_log, &local_result, &local_privilege,
-                    &local_matched_rule, TRUE);
+                    &local_matched_rule, break_on_first_match);
 
   if (local_toggles > 0)
     {
@@ -1266,7 +1288,30 @@ check_rules_for_name (DBusHashTable  *rules,
 }
 
 static int
+check_rules_for_name (DBusHashTable  *rules,
+                      const char     *name,
+                      int             score,
+                      CheckRuleFunc   check_func,
+                      const void     *params,
+                      dbus_int32_t   *toggles,
+                      dbus_bool_t    *log,
+                      BusResult      *result,
+                      const char    **privilege,
+                      BusPolicyRule **matched_rule)
+{
+  const BusPolicyRulesWithScore *rules_list;
+
+  rules_list = _dbus_hash_table_lookup_string (rules, name);
+
+  if (rules_list == NULL || rules_list->score <= score)
+    return score;
+
+  return check_rules_list_with_score (rules_list->rules, score, check_func, params, toggles, log, result, privilege, matched_rule, TRUE);
+}
+
+static int
 find_and_check_rules_for_name (DBusHashTable  *rules,
+                               DBusList       *prefix_rules,
                                const char     *c_str,
                                int             score,
                                CheckRuleFunc   check_func,
@@ -1277,34 +1322,25 @@ find_and_check_rules_for_name (DBusHashTable  *rules,
                                const char    **privilege,
                                BusPolicyRule **matched_rule)
 {
-  char name[DBUS_MAXIMUM_NAME_LENGTH+1];
-  int pos = strlen(c_str);
-
-  _dbus_assert (pos <= DBUS_MAXIMUM_NAME_LENGTH);
-
-  strncpy (name, c_str, pos);
-  name[pos] = 0;
-
-  while (pos > 0)
-    {
-      score = check_rules_for_name (rules, name,
-                                    score, check_func, params,
-                                    toggles, log,
-                                    result, privilege,
-                                    matched_rule);
-
-      while (pos > 0 && name[pos] != '.')
-        pos--;
-
-      name[pos] = 0;
-    }
+  score = check_rules_for_name (rules, c_str,
+                                score, check_func, params,
+                                toggles, log,
+                                result, privilege,
+                                matched_rule);
+
+  score = check_rules_list_with_score (prefix_rules,
+                                       score, check_func, params,
+                                       toggles, log,
+                                       result, privilege,
+                                       matched_rule, FALSE);
 
   return score;
 }
 
 static void
-find_and_check_rules (DBusHashTable *rules,
-                      CheckRuleFunc  check_func,
+find_and_check_rules (DBusHashTable  *rules,
+                      DBusList       *prefix_rules,
+                      CheckRuleFunc   check_func,
                       const void     *params,
                       dbus_int32_t   *toggles,
                       dbus_bool_t    *log,
@@ -1335,7 +1371,7 @@ find_and_check_rules (DBusHashTable *rules,
               if (name[0] == ':')
                 continue;
 
-              score = find_and_check_rules_for_name (rules, name, score,
+              score = find_and_check_rules_for_name (rules, prefix_rules, name, score,
                                                      check_func, params,
                                                      toggles, log, result,
                                                      privilege, matched_rule);
@@ -1343,14 +1379,14 @@ find_and_check_rules (DBusHashTable *rules,
         }
       else if (p->u.sr.name != NULL)
         {
-          score = find_and_check_rules_for_name (rules, p->u.sr.name, score,
+          score = find_and_check_rules_for_name (rules, prefix_rules, p->u.sr.name, score,
                                                  check_func, params,
                                                  toggles, log, result,
                                                  privilege, matched_rule);
         }
     }
   else
-    score = find_and_check_rules_for_name (rules, _dbus_string_get_const_data(p->u.name),
+    score = find_and_check_rules_for_name (rules, prefix_rules, _dbus_string_get_const_data(p->u.name),
                                            score, check_func, params,
                                            toggles, log, result,
                                            privilege, matched_rule);
@@ -1374,7 +1410,9 @@ check_policy (BusClientPolicy *policy,
   if (toggles)
     *toggles = 0;
 
-  find_and_check_rules (policy->policy->default_rules_by_name, check_func, params,
+  find_and_check_rules (policy->policy->default_rules_by_name,
+                        policy->policy->default_prefix_rules,
+                        check_func, params,
                         toggles, log, &result, privilege, matched_rule);
 
   /* we avoid the overhead of looking up user's groups