[sync] Significantly speed up password model association on mac

chrome/browser/password_manager/password_store_mac.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/password_manager/password_store_mac.h"
 #include "chrome/browser/password_manager/password_store_mac_internal.h"
 
 #include <CoreServices/CoreServices.h>
 #include <set>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include "base/callback.h"
 #include "base/debug/crash_logging.h"
 #include "base/debug/stack_trace.h"
 #include "base/logging.h"
 #include "base/mac/mac_logging.h"
 #include "base/mac/mac_util.h"
 #include "base/message_loop/message_loop.h"
 #include "base/stl_util.h"
@@ skipping 208 matching lines @@
   switch (auth_type) {
     case kSecAuthenticationTypeHTMLForm:   return PasswordForm::SCHEME_HTML;
     case kSecAuthenticationTypeHTTPBasic:  return PasswordForm::SCHEME_BASIC;
     case kSecAuthenticationTypeHTTPDigest: return PasswordForm::SCHEME_DIGEST;
     default:                               return PasswordForm::SCHEME_OTHER;
   }
 }
 
 bool FillPasswordFormFromKeychainItem(const AppleKeychain& keychain,
                                       const SecKeychainItemRef& keychain_item,
-                                      PasswordForm* form) {
+                                      PasswordForm* form,
+                                      bool extract_password_data) {
   DCHECK(form);
 
   SecKeychainAttributeInfo attrInfo;
   UInt32 tags[] = { kSecAccountItemAttr,
                     kSecServerItemAttr,
                     kSecPortItemAttr,
                     kSecPathItemAttr,
                     kSecProtocolItemAttr,
                     kSecAuthenticationTypeItemAttr,
                     kSecSecurityDomainItemAttr,
                     kSecCreationDateItemAttr,
                     kSecNegativeItemAttr };
   attrInfo.count = arraysize(tags);
   attrInfo.tag = tags;
   attrInfo.format = NULL;
 
   SecKeychainAttributeList *attrList;
   UInt32 password_length;
-  void* password_data;
+
+  // If |extract_password_data| is false, do not pass in a reference to
+  // |password_data|. ItemCopyAttributesAndData will then extract only the
+  // attributes of |keychain_item| (doesn't require OS authorization), and not
+  // attempt to extract its password data (requires OS authorization).
+  void* password_data = NULL;
+  void** password_data_ref = extract_password_data ? &password_data : NULL;
+
   OSStatus result = keychain.ItemCopyAttributesAndData(keychain_item, &attrInfo,
                                                        NULL, &attrList,
                                                        &password_length,
-                                                       &password_data);
+                                                       password_data_ref);
 
   if (result != noErr) {
     // We don't log errSecAuthFailed because that just means that the user
     // chose not to allow us access to the item.
     if (result != errSecAuthFailed) {
       OSSTATUS_LOG(ERROR, result) << "Keychain data load failed";
     }
     return false;
   }
 
-  UTF8ToUTF16(static_cast<const char *>(password_data), password_length,
-              &(form->password_value));
+  if (extract_password_data) {
+    UTF8ToUTF16(static_cast<const char *>(password_data), password_length,
+                &(form->password_value));
+  }
 
   int port = kAnyPort;
   std::string server;
   std::string security_domain;
   std::string path;
   for (unsigned int i = 0; i < attrList->count; i++) {
     SecKeychainAttribute attr = attrList->attr[i];
     if (!attr.data) {
       continue;
     }
@@ skipping 41 matching lines @@
           form->blacklisted_by_user = true;
         }
         break;
     }
   }
   keychain.ItemFreeAttributesAndData(attrList, password_data);
 
   // kSecNegativeItemAttr doesn't seem to actually be in widespread use. In
   // practice, other browsers seem to use a "" or " " password (and a special
   // user name) to indicated blacklist entries.
-  if (form->password_value.empty() || EqualsASCII(form->password_value, " ")) {
+  if (extract_password_data && (form->password_value.empty() ||
+                                EqualsASCII(form->password_value, " "))) {
     form->blacklisted_by_user = true;
   }
 
   form->origin = URLFromComponents(form->ssl_valid, server, port, path);
   // TODO(stuartmorgan): Handle proxies, which need a different signon_realm
   // format.
   form->signon_realm = form->origin.GetOrigin().spec();
   if (form->scheme != PasswordForm::SCHEME_HTML) {
     form->signon_realm.append(security_domain);
   }
   return true;
 }
 
 bool FormsMatchForMerge(const PasswordForm& form_a,
                         const PasswordForm& form_b) {
   // We never merge blacklist entries between our store and the keychain.
   if (form_a.blacklisted_by_user || form_b.blacklisted_by_user) {

[stuartmorgan, 2013/09/30 22:39:12]

As far as I can tell, you are pulling a bunch of password forms that always say
they aren't blacklist entries (even if they are), then feeding them into this
method. So it seems like this will never fire, and you'll merge keychain
blacklist entries from other browsers into the list of non-blacklist forms,
breaking the contract of the higher-level methods. Am I missing a filtering step
somewhere?

On a related note, I'm concerned that several versions of this CL have had
important behavioral regressions that apparently weren't covered by tests.
Obviously that means I didn't write tests for enough of the cases, but if you
are going to be changing core functioning of the password system I'd like to see
increased test coverage of the things I've pointed out that earlier iterations
would have broken so that we can be confident that each case we've talked about
will survive the refactoring.

[Raghu Simha, 2013/10/02 02:09:50]

There is a filtering step for blacklisted passwords in MergePasswordForms, which
is called after ExtractPasswordsMergeableWithForm. In addition, the above check
does fire when any one of form_a or form_b are blacklisted. I stepped through a
debugger and was able to confirm that we are hitting this case due to the fact
that the corresponding PasswordForms in database_forms do have the
blacklisted_by_user flag set. I have gone ahead and added a step that checks for
the blacklisted bit *after* the passwords are extracted from the keychain, and
only then adds the form to |matches|.

However, you're right that the documentation for
GetAllKeychainItemAttributesAsPasswordForms should be updated to mention
blacklist entries.
I added a new unit test for blacklisted passwords where the PasswordFormData
entries contain non-empty passwords, but the keychain entries for those forms
are blacklisted, and made sure that the collection of merged forms returned is
empty.

I've also added a new unit test to test FillPasswordFormFromKeychainItem for
both versions of |extract_password_data|.

     return false;
   }
   return form_a.scheme == form_b.scheme &&
          form_a.signon_realm == form_b.signon_realm &&
          form_a.username_value == form_b.username_value;
 }
 
 // Returns an the best match for |form| from |keychain_forms|, or NULL if there
 // is no suitable match.
 PasswordForm* BestKeychainFormForForm(
@@ skipping 75 matching lines @@
 
   // Add in the blacklist entries from the database.
   merged_forms->insert(merged_forms->end(),
                        database_blacklist_forms.begin(),
                        database_blacklist_forms.end());
 
   // Clear out all the Keychain entries we used.
   DeleteVectorElementsInSet(keychain_forms, used_keychain_forms);
 }
 
+std::vector<MacKeychainPasswordFormAdapter::ItemFormPair>
+    GetAllKeychainItemAttributesAsPasswordForms(
+        std::vector<SecKeychainItemRef>* keychain_items,
+        const AppleKeychain& keychain) {
+  DCHECK(keychain_items);
+  MacKeychainPasswordFormAdapter keychain_adapter(&keychain);
+  *keychain_items = keychain_adapter.GetAllPasswordFormKeychainItems();
+  std::vector<MacKeychainPasswordFormAdapter::ItemFormPair> item_form_pairs;
+  for (std::vector<SecKeychainItemRef>::iterator i = keychain_items->begin();
+       i != keychain_items->end(); ++i) {
+    PasswordForm* form_without_password = new PasswordForm();
+    internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+        keychain,
+        *i,
+        form_without_password,
+        false);  // Load password attributes, but not password data.
+    item_form_pairs.push_back(std::make_pair(&(*i), form_without_password));
+  }
+  return item_form_pairs;
+}
+
 std::vector<PasswordForm*> GetPasswordsForForms(
     const AppleKeychain& keychain,
     std::vector<PasswordForm*>* database_forms) {
+  // First load the attributes of all items in the keychain without loading
+  // their password data, and then match items in |database_forms| against them.
+  // This avoids individually searching through the keychain for passwords
+  // matching each form in |database_forms|, and results in a significant
+  // performance gain, replacing O(N) keychain search operations with a single
+  // operation that loads all keychain items, and then selective reads of only
+  // the relevant passwords. See crbug.com/263685.
+  std::vector<SecKeychainItemRef> keychain_items;
+  std::vector<MacKeychainPasswordFormAdapter::ItemFormPair> item_form_pairs =
+      GetAllKeychainItemAttributesAsPasswordForms(&keychain_items, keychain);
+
+  // Next, compare the attributes of the PasswordForms in |database_forms|
+  // against those in |item_form_pairs|, and extract password data for each
+  // matching PasswordForm using its corresponding SecKeychainItemRef.
   MacKeychainPasswordFormAdapter keychain_adapter(&keychain);
-
   std::vector<PasswordForm*> merged_forms;
   for (std::vector<PasswordForm*>::iterator i = database_forms->begin();
        i != database_forms->end();) {
     std::vector<PasswordForm*> db_form_container(1, *i);
     std::vector<PasswordForm*> keychain_matches =
-        keychain_adapter.PasswordsMergeableWithForm(**i);
+        keychain_adapter.ExtractPasswordsMergeableWithForm(item_form_pairs,
+                                                           **i);
     MergePasswordForms(&keychain_matches, &db_form_container, &merged_forms);
     if (db_form_container.empty()) {
       i = database_forms->erase(i);
     } else {
       ++i;
     }
     STLDeleteElements(&keychain_matches);
   }
+
+  // Clean up temporary PasswordForms and SecKeychainItemRefs.
+  STLDeleteContainerPairSecondPointers(item_form_pairs.begin(),
+                                       item_form_pairs.end());
+  for (std::vector<SecKeychainItemRef>::iterator i = keychain_items.begin();
+       i != keychain_items.end(); ++i) {
+    keychain.Free(*i);
+  }
   return merged_forms;
 }
 
 class Thread : public base::Thread {
  public:
   Thread(const char* name) : base::Thread(name) {}
   virtual ~Thread() {
     base::debug::SetCrashKeyToStackTrace(
         crash_keys::mac::kPasswordThreadDtorTrace, base::debug::StackTrace());
   }
@@ skipping 11 matching lines @@
 std::vector<PasswordForm*>
     MacKeychainPasswordFormAdapter::PasswordsFillingForm(
         const PasswordForm& query_form) {
   std::vector<SecKeychainItemRef> keychain_items =
       MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
                             NULL, NULL);
 
   return ConvertKeychainItemsToForms(&keychain_items);
 }
 
+bool MacKeychainPasswordFormAdapter::FormIsValidAndMatchesOtherForm(
+    const PasswordForm& query_form,
+    const PasswordForm& other_form) {
+  std::string server;
+  std::string security_domain;
+  int port;
+  bool is_secure;
+  if (!ExtractSignonRealmComponents(query_form.signon_realm, &server, &port,
+                                    &is_secure, &security_domain)) {
+    return false;
+  }
+  return internal_keychain_helpers::FormsMatchForMerge(query_form, other_form);
+}
+
 std::vector<PasswordForm*>
-    MacKeychainPasswordFormAdapter::PasswordsMergeableWithForm(
+    MacKeychainPasswordFormAdapter::ExtractPasswordsMergeableWithForm(

[stuartmorgan, 2013/09/30 22:39:12]

AFAICT this no longer operates on the keychain in any way, so it's weird to have
it be part of MacKeychainPasswordFormAdapter. Can it just be a stand-alone
helper?

[Raghu Simha, 2013/10/02 02:09:50]

We reference the keychain in line 580, while calling
FillPasswordFormFromKeychainItem, but this can just as easily be done by passing
a const reference to the keychain. The reason I originally made
ExtractPasswordsMergeableWithForm a member of MacKeychainPasswordFormAdapter was
because it calls FormIsValidAndMatchesOtherForm, which in turn calls
ExtractSignonRealmComponents, both of which are members of
MacKeychainPasswordFormAdapter. Since these methods do not actually operate on
the keychain, I've made them helper functions.

+        const std::vector<ItemFormPair>& item_form_pairs,
         const PasswordForm& query_form) {
-  std::string username = UTF16ToUTF8(query_form.username_value);
-  std::vector<SecKeychainItemRef> keychain_items =
-      MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
-                            NULL, username.c_str());
-
-  return ConvertKeychainItemsToForms(&keychain_items);
+  std::vector<PasswordForm*> matches;
+  for (std::vector<ItemFormPair>::const_iterator i = item_form_pairs.begin();
+       i != item_form_pairs.end(); ++i) {
+    if (FormIsValidAndMatchesOtherForm(query_form, *(i->second))) {
+      // Create a new object, since the caller is responsible for deleting the
+      // returned forms.

[stuartmorgan, 2013/09/30 22:39:12]

Feel free to use ScopedVector anywhere it makes life easier here BTW; this code
predates it, which is the only reason it does everything manually.

[Raghu Simha, 2013/10/02 02:09:50]

I did consider using a ScopedVector here, but ended up not doing so, since the
vector of PasswordForm*s created here is processed in another function, and
therefore, cannot be deleted here.

+      PasswordForm* form_with_password = new PasswordForm();
+      internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+          *keychain_,
+          *(i->first),
+          form_with_password,
+          true);  // Load password attributes and data.
+      matches.push_back(form_with_password);
+    }
+  }
+  return matches;
 }
 
 PasswordForm* MacKeychainPasswordFormAdapter::PasswordExactlyMatchingForm(
     const PasswordForm& query_form) {
   SecKeychainItemRef keychain_item = KeychainItemForForm(query_form);
   if (keychain_item) {
     PasswordForm* form = new PasswordForm();
     internal_keychain_helpers::FillPasswordFormFromKeychainItem(*keychain_,
                                                                 keychain_item,
-                                                                form);
+                                                                form,
+                                                                true);
     keychain_->Free(keychain_item);
     return form;
   }
   return NULL;
 }
 
 bool MacKeychainPasswordFormAdapter::HasPasswordsMergeableWithForm(
     const PasswordForm& query_form) {
   std::string username = UTF16ToUTF8(query_form.username_value);
   std::vector<SecKeychainItemRef> matches =
       MatchingKeychainItems(query_form.signon_realm, query_form.scheme,
                             NULL, username.c_str());
   for (std::vector<SecKeychainItemRef>::iterator i = matches.begin();
        i != matches.end(); ++i) {
     keychain_->Free(*i);
   }
 
   return !matches.empty();
 }
 
-std::vector<PasswordForm*>
-    MacKeychainPasswordFormAdapter::GetAllPasswordFormPasswords() {
+std::vector<SecKeychainItemRef>
+    MacKeychainPasswordFormAdapter::GetAllPasswordFormKeychainItems() {
   SecAuthenticationType supported_auth_types[] = {
     kSecAuthenticationTypeHTMLForm,
     kSecAuthenticationTypeHTTPBasic,
     kSecAuthenticationTypeHTTPDigest,
   };
 
   std::vector<SecKeychainItemRef> matches;
   for (unsigned int i = 0; i < arraysize(supported_auth_types); ++i) {
     KeychainSearch keychain_search(*keychain_);
     keychain_search.Init(NULL, 0, kSecProtocolTypeAny, supported_auth_types[i],
                          NULL, NULL, NULL, CreatorCodeForSearch());
     keychain_search.FindMatchingItems(&matches);
   }
+  return matches;
+}
 
-  return ConvertKeychainItemsToForms(&matches);
+std::vector<PasswordForm*>
+    MacKeychainPasswordFormAdapter::GetAllPasswordFormPasswords() {
+  std::vector<SecKeychainItemRef> items = GetAllPasswordFormKeychainItems();
+  return ConvertKeychainItemsToForms(&items);
 }
 
 bool MacKeychainPasswordFormAdapter::AddPassword(const PasswordForm& form) {
   // We should never be trying to store a blacklist in the keychain.
   DCHECK(!form.blacklisted_by_user);
 
   std::string server;
   std::string security_domain;
   int port;
   bool is_secure;
@@ skipping 47 matching lines @@
   finds_only_owned_ = finds_only_owned;
 }
 
 std::vector<PasswordForm*>
     MacKeychainPasswordFormAdapter::ConvertKeychainItemsToForms(
         std::vector<SecKeychainItemRef>* items) {
   std::vector<PasswordForm*> keychain_forms;
   for (std::vector<SecKeychainItemRef>::const_iterator i = items->begin();
        i != items->end(); ++i) {
     PasswordForm* form = new PasswordForm();
-    if (internal_keychain_helpers::FillPasswordFormFromKeychainItem(*keychain_,
-                                                                    *i, form)) {
+    if (internal_keychain_helpers::FillPasswordFormFromKeychainItem(
+            *keychain_, *i, form, true)) {
       keychain_forms.push_back(form);
     }
     keychain_->Free(*i);
   }
   items->clear();
   return keychain_forms;
 }
 
 SecKeychainItemRef MacKeychainPasswordFormAdapter::KeychainItemForForm(
     const PasswordForm& form) {
@@ skipping 397 matching lines @@
   owned_keychain_adapter.SetFindsOnlyOwnedItems(true);
   for (std::vector<PasswordForm*>::const_iterator i = forms.begin();
        i != forms.end(); ++i) {
     owned_keychain_adapter.RemovePassword(**i);
   }
 }
 
 void PasswordStoreMac::CreateNotificationService() {
   notification_service_.reset(content::NotificationService::Create());
 }