bus/policy: use hash tables for checking policysandbox/adrians/send-index

Only for send/receive/own rules in default context.

Change-Id: Iabbbfa5d582f9993b832f49193da93225c645014

2 files changed, 322 insertions, 14 deletions

diff --git a/bus/policy.c b/bus/policy.c
index 45477b95..4ba7d6f3 100644
--- a/bus/policy.c
+++ b/bus/policy.c
@@ -31,6 +31,7 @@
 #include <dbus/dbus-hash.h>
 #include <dbus/dbus-internals.h>
 #include <dbus/dbus-message-internal.h>
+#include <dbus/dbus-connection-internal.h>
 
 struct BusClientPolicy
 {
@@ -152,8 +153,17 @@ struct BusPolicy
   DBusHashTable *rules_by_gid;     /**< per-GID policy rules */
   DBusList *at_console_true_rules; /**< console user policy rules where at_console="true"*/
   DBusList *at_console_false_rules; /**< console user policy rules where at_console="false"*/
+
+  DBusHashTable *default_rules_by_name;
+  unsigned int n_default_rules;
 };
 
+typedef struct BusPolicyRulesWithScore
+{
+  DBusList *rules;
+  int score;
+} BusPolicyRulesWithScore;
+
 static void
 free_rule_func (void *data,
                 void *user_data)
@@ -178,6 +188,21 @@ free_rule_list_func (void *data)
   dbus_free (list);
 }
 
+static void
+free_rule_list_with_score_func (void *data)
+{
+  BusPolicyRulesWithScore *rules = data;
+
+  if (rules == NULL)
+    return;
+
+  _dbus_list_foreach (&rules->rules, free_rule_func, NULL);
+
+  _dbus_list_clear (&rules->rules);
+
+  dbus_free (rules);
+}
+
 BusPolicy*
 bus_policy_new (void)
 {
@@ -201,6 +226,12 @@ bus_policy_new (void)
   if (policy->rules_by_gid == NULL)
     goto failed;
 
+  policy->default_rules_by_name = _dbus_hash_table_new (DBUS_HASH_STRING,
+                                                        NULL,
+                                                        free_rule_list_with_score_func);
+  if (policy->default_rules_by_name == NULL)
+    goto failed;
+
   return policy;
   
  failed:
@@ -251,6 +282,12 @@ bus_policy_unref (BusPolicy *policy)
           policy->rules_by_gid = NULL;
         }
 
+      if (policy->default_rules_by_name)
+        {
+          _dbus_hash_table_unref (policy->default_rules_by_name);
+          policy->default_rules_by_name = NULL;
+        }
+
       dbus_free (policy);
     }
 }
@@ -413,12 +450,74 @@ bus_policy_allow_windows_user (BusPolicy        *policy,
   return _dbus_windows_user_is_process_owner (windows_sid);
 }
 
+static BusPolicyRulesWithScore *
+get_rules_by_string (DBusHashTable *hash,
+                    const char    *key)
+{
+  BusPolicyRulesWithScore *rules;
+
+  rules = _dbus_hash_table_lookup_string (hash, key);
+  if (rules == NULL)
+    {
+      rules = dbus_new0 (BusPolicyRulesWithScore, 1);
+      if (rules == NULL)
+        return NULL;
+
+      if (!_dbus_hash_table_insert_string (hash, (char *)key, rules))
+        {
+          dbus_free (rules);
+          return NULL;
+        }
+    }
+
+  return rules;
+}
+
+static const char *
+get_name_from_rule (BusPolicyRule *rule)
+{
+  const char *name = NULL;
+  if (rule->type == BUS_POLICY_RULE_SEND)
+    name = rule->d.send.destination;
+  else if (rule->type == BUS_POLICY_RULE_RECEIVE)
+    name = rule->d.receive.origin;
+  else if (rule->type == BUS_POLICY_RULE_OWN)
+    name = rule->d.own.service_name;
+
+  if (name == NULL)
+    name = "";
+
+  return name;
+}
+
 dbus_bool_t
 bus_policy_append_default_rule (BusPolicy      *policy,
                                 BusPolicyRule  *rule)
 {
-  if (!_dbus_list_append (&policy->default_rules, rule))
-    return FALSE;
+  if (rule->type == BUS_POLICY_RULE_USER || rule->type == BUS_POLICY_RULE_GROUP)
+    {
+      if (!_dbus_list_append (&policy->default_rules, rule))
+        return FALSE;
+    }
+  else
+    {
+      DBusList **list;
+      BusPolicyRulesWithScore *rules;
+
+      rules = get_rules_by_string (policy->default_rules_by_name,
+                                   get_name_from_rule (rule));
+
+      if (rules == NULL)
+        return FALSE;
+
+      list = &rules->rules;
+
+      if (!_dbus_list_prepend (list, rule))
+        return FALSE;
+
+      rule->score = ++policy->n_default_rules;
+      rules->score = rule->score;
+    }
 
   bus_policy_rule_ref (rule);
 
@@ -580,6 +679,64 @@ merge_id_hash (DBusHashTable *dest,
   return TRUE;
 }
 
+static dbus_bool_t
+merge_string_hash (unsigned int *n_rules,
+                   unsigned int n_rules_to_absorb,
+                   DBusHashTable *dest,
+                   DBusHashTable *to_absorb)
+{
+  DBusHashIter iter;
+#ifndef DBUS_DISABLE_ASSERT
+  int cnt_rules = 0;
+#endif
+
+  _dbus_hash_iter_init (to_absorb, &iter);
+  while (_dbus_hash_iter_next (&iter))
+    {
+      const char *id = _dbus_hash_iter_get_string_key (&iter);
+      BusPolicyRulesWithScore *to_absorb_rules =_dbus_hash_iter_get_value (&iter);
+      DBusList **list = &to_absorb_rules->rules;
+      BusPolicyRulesWithScore *target_rules = get_rules_by_string (dest, id);
+      DBusList **target;
+      DBusList *list_iter;
+      DBusList *target_first_link;
+
+      if (target_rules == NULL)
+        return FALSE;
+
+      target = &target_rules->rules;
+      target_first_link = _dbus_list_get_first_link (target);
+
+      list_iter = _dbus_list_get_first_link (list);
+      while (list_iter != NULL)
+        {
+          DBusList *new_link;
+          BusPolicyRule *rule = list_iter->data;
+
+          rule->score += *n_rules;
+          list_iter = _dbus_list_get_next_link (list, list_iter);
+#ifndef DBUS_DISABLE_ASSERT
+          cnt_rules++;
+#endif
+          new_link = _dbus_list_alloc_link (rule);
+          if (new_link == NULL)
+            return FALSE;
+
+          bus_policy_rule_ref (rule);
+
+          _dbus_list_insert_before_link (target, target_first_link, new_link);
+        }
+
+      target_rules->score = to_absorb_rules->score + *n_rules;
+    }
+
+  _dbus_assert (n_rules_to_absorb == cnt_rules);
+
+  *n_rules += n_rules_to_absorb;
+
+  return TRUE;
+}
+
 dbus_bool_t
 bus_policy_merge (BusPolicy *policy,
                   BusPolicy *to_absorb)
@@ -612,6 +769,12 @@ bus_policy_merge (BusPolicy *policy,
                       to_absorb->rules_by_gid))
     return FALSE;
 
+  if (!merge_string_hash (&policy->n_default_rules,
+                          to_absorb->n_default_rules,
+                          policy->default_rules_by_name,
+                          to_absorb->default_rules_by_name))
+    return FALSE;
+
   return TRUE;
 }
 
@@ -1020,7 +1183,8 @@ check_rules_list (const DBusList   *rules,
                   dbus_bool_t      *log,
                   BusResult        *result,
                   const char      **privilege,
-                  BusPolicyRule   **matched_rule)
+                  BusPolicyRule   **matched_rule,
+                  dbus_bool_t       break_on_first_match)
 {
   const DBusList *link;
 
@@ -1042,8 +1206,155 @@ check_rules_list (const DBusList   *rules,
 
           _dbus_verbose ("  (policy) used rule, result now = %d\n",
                          result);
+
+          if (break_on_first_match)
+            break;
+        }
+    }
+}
+
+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)
+{
+  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,
+                    &local_toggles, &local_log, &local_result, &local_privilege,
+                    &local_matched_rule, TRUE);
+
+  if (local_toggles > 0)
+    {
+      _dbus_assert (local_matched_rule != NULL);
+
+      if (local_matched_rule->score > score)
+        {
+          if (toggles)
+            *toggles += local_toggles;
+          if (log)
+            *log = local_log;
+          *result = local_result;
+          *privilege = local_privilege;
+          if (matched_rule)
+            *matched_rule = local_matched_rule;
+          return local_matched_rule->score;
+        }
+    }
+
+  return score;
+}
+
+static int
+find_and_check_rules_for_name (DBusHashTable  *rules,
+                               const char     *c_str,
+                               int             score,
+                               CheckRuleFunc   check_func,
+                               const void     *params,
+                               dbus_int32_t   *toggles,
+                               dbus_bool_t    *log,
+                               BusResult      *result,
+                               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;
+    }
+
+  return score;
+}
+
+static void
+find_and_check_rules (DBusHashTable *rules,
+                      CheckRuleFunc  check_func,
+                      const void     *params,
+                      dbus_int32_t   *toggles,
+                      dbus_bool_t    *log,
+                      BusResult      *result,
+                      const char    **privilege,
+                      BusPolicyRule **matched_rule)
+{
+  const RuleParams *p = params;
+  const DBusList *services = NULL;
+  int score = 0;
+
+  if (p->type == PARAM_SR)
+    {
+      if (p->u.sr.peer != NULL)
+        {
+          DBusList *link;
+
+          services = bus_connection_get_owned_services_list (p->u.sr.peer);
+
+          link = _dbus_list_get_first_link ((DBusList **)&services);
+          while (link != NULL)
+            {
+              const char *name = bus_service_get_name (link->data);
+
+              link = _dbus_list_get_next_link ((DBusList **)&services, link);
+
+              /* skip unique id names */
+              if (name[0] == ':')
+                continue;
+
+              score = find_and_check_rules_for_name (rules, name, score,
+                                                     check_func, params,
+                                                     toggles, log, result,
+                                                     privilege, matched_rule);
+            }
         }
+      else
+        score = find_and_check_rules_for_name (rules, DBUS_SERVICE_DBUS, score,
+                                               check_func, params,
+                                               toggles, log, result,
+                                               privilege, matched_rule);
     }
+  else
+    score = find_and_check_rules_for_name (rules, _dbus_string_get_data(p->u.name),
+                                           score, check_func, params,
+                                           toggles, log, result,
+                                           privilege, matched_rule);
+
+  /* check also wildcard rules */
+  score = check_rules_for_name (rules, "", score, check_func, params,
+                                toggles, log, result, privilege, matched_rule);
 }
 
 static BusResult
@@ -1060,12 +1371,8 @@ check_policy (BusClientPolicy *policy,
   if (toggles)
     *toggles = 0;
 
-  /* checking is in the order the rules appeared
-   * in the config file, i.e. last rule that applies wins
-   */
-
-  check_rules_list (policy->policy->default_rules, check_func, params,
-                    toggles, log, &result, privilege, matched_rule);
+  find_and_check_rules (policy->policy->default_rules_by_name, check_func, params,
+                        toggles, log, &result, privilege, matched_rule);
 
   /* we avoid the overhead of looking up user's groups
    * if we don't have any group rules anyway
@@ -1083,7 +1390,7 @@ check_policy (BusClientPolicy *policy,
 
           if (list != NULL)
             check_rules_list (*list, check_func, params,
-                              toggles, log, &result, privilege, matched_rule);
+                              toggles, log, &result, privilege, matched_rule, FALSE);
         }
     }
 
@@ -1098,19 +1405,19 @@ check_policy (BusClientPolicy *policy,
 
           if (list != NULL)
             check_rules_list (*list, check_func, params,
-                              toggles, log, &result, privilege, matched_rule);
+                              toggles, log, &result, privilege, matched_rule, FALSE);
 
           if (policy->at_console)
             check_rules_list (policy->policy->at_console_true_rules, check_func,
-                              params, toggles, log, &result, privilege, matched_rule);
+                              params, toggles, log, &result, privilege, matched_rule, FALSE);
           else
             check_rules_list (policy->policy->at_console_false_rules, check_func,
-                              params, toggles, log, &result, privilege, matched_rule);
+                              params, toggles, log, &result, privilege, matched_rule, FALSE);
         }
     }
 
   check_rules_list (policy->policy->mandatory_rules, check_func, params,
-                    toggles, log, &result, privilege, matched_rule);
+                    toggles, log, &result, privilege, matched_rule, FALSE);
 
   return result;
 }
diff --git a/bus/policy.h b/bus/policy.h
index 6d86909f..080f7975 100644
--- a/bus/policy.h
+++ b/bus/policy.h
@@ -65,6 +65,7 @@ struct BusPolicyRule
   BusPolicyRuleType type;
 
   unsigned int access : 2; /**< BusPolicyRuleAccess */
+  unsigned int score : 30; /**< for keeping the importance of the rule */
   char *privilege; /**< for BUS_POLICY_RULE_ACCESS_CHECK */
 
   union