Added the KeySetManager.

Bug: 7554291
Change-Id: Ic693a544f1e2cab20f6540b3fc4ff673e35bd2c6
diff --git a/services/java/com/android/server/pm/KeySetManager.java b/services/java/com/android/server/pm/KeySetManager.java
new file mode 100644
index 0000000..afb7d4b
--- /dev/null
+++ b/services/java/com/android/server/pm/KeySetManager.java
@@ -0,0 +1,540 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.pm;
+
+import android.content.pm.KeySet;
+import android.content.pm.PackageParser;
+import android.os.Binder;
+import android.util.Base64;
+import android.util.Log;
+import android.util.LongSparseArray;
+
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.security.PublicKey;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.xmlpull.v1.XmlPullParser;
+import org.xmlpull.v1.XmlPullParserException;
+import org.xmlpull.v1.XmlSerializer;
+
+/*
+ * Manages system-wide KeySet state.
+ */
+public class KeySetManager {
+
+    static final String TAG = "KeySetManager";
+
+    private static final long KEYSET_NOT_FOUND = -1;
+    private static final long PUBLIC_KEY_NOT_FOUND = -1;
+
+    private final Object mLockObject = new Object();
+
+    private final LongSparseArray<KeySet> mKeySets;
+
+    private final LongSparseArray<PublicKey> mPublicKeys;
+
+    private final LongSparseArray<Set<Long>> mKeySetMapping;
+
+    private final Map<String, PackageSetting> mPackages;
+
+    private static long lastIssuedKeySetId = 0;
+
+    private static long lastIssuedKeyId = 0;
+
+    public KeySetManager(Map<String, PackageSetting> packages) {
+        mKeySets = new LongSparseArray<KeySet>();
+        mPublicKeys = new LongSparseArray<PublicKey>();
+        mKeySetMapping = new LongSparseArray<Set<Long>>();
+        mPackages = packages;
+    }
+
+    /*
+     * Determine if a package is signed by the given KeySet.
+     *
+     * Returns false if the package was not signed by all the
+     * keys in the KeySet.
+     *
+     * Returns true if the package was signed by at least the
+     * keys in the given KeySet.
+     *
+     * Note that this can return true for multiple KeySets.
+     */
+    public boolean packageIsSignedBy(String packageName, KeySet ks) {
+        synchronized (mLockObject) {
+            PackageSetting pkg = mPackages.get(packageName);
+            if (pkg == null) {
+                throw new NullPointerException("Invalid package name");
+            }
+            if (pkg.keySetData == null) {
+                throw new NullPointerException("Package has no KeySet data");
+            }
+            long id = getIdByKeySetLocked(ks);
+            return pkg.keySetData.packageIsSignedBy(id);
+        }
+    }
+
+    /*
+     * This informs the system that the given package has defined a KeySet
+     * in its manifest that a) contains the given keys and b) is named
+     * alias by that package.
+     */
+    public void addDefinedKeySetToPackage(String packageName,
+            Set<PublicKey> keys, String alias) {
+        if ((packageName == null) || (keys == null) || (alias == null)) {
+            Log.e(TAG, "Got null argument for a defined keyset, ignoring!");
+            return;
+        }
+        synchronized (mLockObject) {
+            KeySet ks = addKeySetLocked(keys);
+            PackageSetting pkg = mPackages.get(packageName);
+            if (pkg == null) {
+                throw new NullPointerException("Unknown package");
+            }
+            long id = getIdByKeySetLocked(ks);
+            pkg.keySetData.addDefinedKeySet(id, alias);
+        }
+    }
+
+    /*
+     * Similar to the above, this informs the system that the given package
+     * was signed by the provided KeySet.
+     */
+    public void addSigningKeySetToPackage(String packageName,
+            Set<PublicKey> signingKeys) {
+        if ((packageName == null) || (signingKeys == null)) {
+            Log.e(TAG, "Got null argument for a signing keyset, ignoring!");
+            return;
+        }
+        synchronized (mLockObject) {
+            // add the signing KeySet
+            KeySet ks = addKeySetLocked(signingKeys);
+            long id = getIdByKeySetLocked(ks);
+            Set<Long> publicKeyIds = mKeySetMapping.get(id);
+            if (publicKeyIds == null) {
+                throw new NullPointerException("Got invalid KeySet id");
+            }
+
+            // attach it to the package
+            PackageSetting pkg = mPackages.get(packageName);
+            if (pkg == null) {
+                throw new NullPointerException("No such package!");
+            }
+            pkg.keySetData.addSigningKeySet(id);
+
+            // for each KeySet the package defines which is a subset of
+            // the one above, add the KeySet id to the package's signing KeySets
+            for (Long keySetID : pkg.keySetData.getDefinedKeySets()) {
+                Set<Long> definedKeys = mKeySetMapping.get(keySetID);
+                if (publicKeyIds.contains(definedKeys)) {
+                    pkg.keySetData.addSigningKeySet(keySetID);
+                }
+            }
+        }
+    }
+
+    /*
+     * Fetches the stable identifier associated with the given KeySet.
+     *
+     * Returns KEYSET_NOT_FOUND if the KeySet... wasn't found.
+     */
+    public long getIdByKeySet(KeySet ks) {
+        synchronized (mLockObject) {
+            return getIdByKeySetLocked(ks);
+        }
+    }
+
+    private long getIdByKeySetLocked(KeySet ks) {
+        for (int keySetIndex = 0; keySetIndex < mKeySets.size(); keySetIndex++) {
+            KeySet value = mKeySets.valueAt(keySetIndex);
+            if (ks.equals(value)) {
+                return mKeySets.keyAt(keySetIndex);
+            }
+        }
+        return KEYSET_NOT_FOUND;
+    }
+
+    /*
+     * Fetches the KeySet corresponding to the given stable identifier.
+     *
+     * Returns KEYSET_NOT_FOUND if the identifier doesn't identify a KeySet.
+     */
+    public KeySet getKeySetById(long id) {
+        synchronized (mLockObject) {
+            return mKeySets.get(id);
+        }
+    }
+
+    /*
+     * Fetches the KeySet that a given package refers to by the provided alias.
+     *
+     * If the package isn't known to us, throws an IllegalArgumentException.
+     * Returns null if the alias isn't known to us.
+     */
+    public KeySet getKeySetByAliasAndPackageName(String packageName, String alias) {
+        synchronized (mLockObject) {
+            PackageSetting p = mPackages.get(packageName);
+            if (p == null) {
+                throw new NullPointerException("Unknown package");
+            }
+            if (p.keySetData == null) {
+                throw new IllegalArgumentException("Package has no keySet data");
+            }
+            long keySetId = p.keySetData.getAliases().get(alias);
+            return mKeySets.get(keySetId);
+        }
+    }
+
+    /*
+     * Fetches all the known KeySets that signed the given package.
+     *
+     * If the package is unknown to us, throws an IllegalArgumentException.
+     */
+    public Set<KeySet> getSigningKeySetsByPackageName(String packageName) {
+        synchronized (mLockObject) {
+            Set<KeySet> signingKeySets = new HashSet<KeySet>();
+            PackageSetting p = mPackages.get(packageName);
+            if (p == null) {
+                throw new NullPointerException("Unknown package");
+            }
+            if (p.keySetData == null) {
+                throw new IllegalArgumentException("Package has no keySet data");
+            }
+            for (long l : p.keySetData.getSigningKeySets()) {
+                signingKeySets.add(mKeySets.get(l));
+            }
+            return signingKeySets;
+        }
+    }
+
+    /*
+     * Creates a new KeySet corresponding to the given keys.
+     *
+     * If the PublicKeys aren't known to the system, this adds them. Otherwise,
+     * they're deduped.
+     *
+     * If the KeySet isn't known to the system, this adds that and creates the
+     * mapping to the PublicKeys. If it is known, then it's deduped.
+     *
+     * Throws if the provided set is null.
+     */
+    private KeySet addKeySetLocked(Set<PublicKey> keys) {
+        if (keys == null) {
+            throw new NullPointerException("Provided keys cannot be null");
+        }
+        // add each of the keys in the provided set
+        Set<Long> addedKeyIds = new HashSet<Long>(keys.size());
+        for (PublicKey k : keys) {
+            long id = addPublicKeyLocked(k);
+            addedKeyIds.add(id);
+        }
+
+        // check to see if the resulting keyset is new
+        long existingKeySetId = getIdFromKeyIdsLocked(addedKeyIds);
+        if (existingKeySetId != KEYSET_NOT_FOUND) {
+            return mKeySets.get(existingKeySetId);
+        }
+
+        // create the KeySet object
+        KeySet ks = new KeySet(new Binder());
+        // get the first unoccupied slot in mKeySets
+        long id = getFreeKeySetIDLocked();
+        // add the KeySet object to it
+        mKeySets.put(id, ks);
+        // add the stable key ids to the mapping
+        mKeySetMapping.put(id, addedKeyIds);
+        // go home
+        return ks;
+    }
+
+    /*
+     * Adds the given PublicKey to the system, deduping as it goes.
+     */
+    private long addPublicKeyLocked(PublicKey key) {
+        // check if the public key is new
+        long existingKeyId = getIdForPublicKeyLocked(key);
+        if (existingKeyId != PUBLIC_KEY_NOT_FOUND) {
+            return existingKeyId;
+        }
+        // if it's new find the first unoccupied slot in the public keys
+        long id = getFreePublicKeyIdLocked();
+        // add the public key to it
+        mPublicKeys.put(id, key);
+        // return the stable identifier
+        return id;
+    }
+
+    /*
+     * Finds the stable identifier for a KeySet based on a set of PublicKey stable IDs.
+     *
+     * Returns KEYSET_NOT_FOUND if there isn't one.
+     */
+    private long getIdFromKeyIdsLocked(Set<Long> publicKeyIds) {
+        for (int keyMapIndex = 0; keyMapIndex < mKeySetMapping.size(); keyMapIndex++) {
+            Set<Long> value = mKeySetMapping.valueAt(keyMapIndex);
+            if (value.equals(publicKeyIds)) {
+                return mKeySetMapping.keyAt(keyMapIndex);
+            }
+        }
+        return KEYSET_NOT_FOUND;
+    }
+
+    /*
+     * Finds the stable identifier for a PublicKey or PUBLIC_KEY_NOT_FOUND.
+     */
+    private long getIdForPublicKeyLocked(PublicKey k) {
+        String encodedPublicKey = new String(k.getEncoded());
+        for (int publicKeyIndex = 0; publicKeyIndex < mPublicKeys.size(); publicKeyIndex++) {
+            PublicKey value = mPublicKeys.valueAt(publicKeyIndex);
+            String encodedExistingKey = new String(value.getEncoded());
+            if (encodedPublicKey.equals(encodedExistingKey)) {
+                return mPublicKeys.keyAt(publicKeyIndex);
+            }
+        }
+        return PUBLIC_KEY_NOT_FOUND;
+    }
+
+    /*
+     * Gets an unused stable identifier for a KeySet.
+     */
+    private long getFreeKeySetIDLocked() {
+        lastIssuedKeySetId += 1;
+        return lastIssuedKeySetId;
+    }
+
+    /*
+     * Same as above, but for public keys.
+     */
+    private long getFreePublicKeyIdLocked() {
+        lastIssuedKeyId += 1;
+        return lastIssuedKeyId;
+    }
+
+    public void removeAppKeySetData(String packageName) {
+        Log.e(TAG, "Removing application " + packageName);
+        synchronized (mLockObject) {
+            // Get the package's known keys and KeySets
+            Set<Long> deletableKeySets = getKnownKeySetsByPackageName(packageName);
+            Set<Long> deletableKeys = new HashSet<Long>();
+            for (Long ks : deletableKeySets) {
+                deletableKeys.addAll(mKeySetMapping.get(ks));
+            }
+
+            // Now remove the keys and KeySets known to any other package
+            for (String pkgName : mPackages.keySet()) {
+                if (pkgName.equals(packageName)) {
+                    continue;
+                }
+                Set<Long> knownKeySets = getKnownKeySetsByPackageName(pkgName);
+                deletableKeySets.removeAll(knownKeySets);
+                Set<Long> knownKeys = new HashSet<Long>();
+                for (Long ks : knownKeySets) {
+                    deletableKeys.removeAll(mKeySetMapping.get(ks));
+                }
+            }
+
+            // The remaining keys and KeySets are not known to any other
+            // application and so can be safely deleted.
+            for (Long ks : deletableKeySets) {
+                mKeySets.delete(ks);
+                mKeySetMapping.delete(ks);
+            }
+            for (Long keyId : deletableKeys) {
+                mPublicKeys.delete(keyId);
+            }
+        }
+    }
+
+    private Set<Long> getKnownKeySetsByPackageName(String packageName) {
+        PackageSetting p = mPackages.get(packageName);
+        if (p == null) {
+            throw new NullPointerException("Unknown package");
+        }
+        if (p.keySetData == null) {
+            throw new IllegalArgumentException("Package has no keySet data");
+        }
+        Set<Long> knownKeySets = new HashSet<Long>();
+        for (Long ks : p.keySetData.getSigningKeySets()) {
+            knownKeySets.add(ks);
+        }
+        for (Long ks : p.keySetData.getDefinedKeySets()) {
+            knownKeySets.add(ks);
+        }
+        return knownKeySets;
+    }
+
+    public String encodePublicKey(PublicKey k) throws IOException {
+        return new String(Base64.encode(k.getEncoded(), 0));
+    }
+
+    public void dump(PrintWriter pw) {
+        synchronized (mLockObject) {
+            pw.println("  Dumping KeySetManager");
+            for (Map.Entry<String, PackageSetting> e : mPackages.entrySet()) {
+                String packageName = e.getKey();
+                PackageSetting pkg = e.getValue();
+                pw.print("  ["); pw.print(packageName); pw.println("]");
+                if (pkg.keySetData != null) {
+                    pw.print("      Defined KeySets:");
+                    for (long keySetId : pkg.keySetData.getDefinedKeySets()) {
+                        pw.print(" "); pw.print(Long.toString(keySetId));
+                    }
+                    pw.println("");
+                    pw.print("      Signing KeySets:");
+                    for (long keySetId : pkg.keySetData.getSigningKeySets()) {
+                        pw.print(" "); pw.print(Long.toString(keySetId));
+                    }
+                    pw.println("");
+                }
+            }
+        }
+    }
+
+    void writeKeySetManagerLPr(XmlSerializer serializer) throws IOException {
+        serializer.startTag(null, "keyset-settings");
+        writePublicKeysLPr(serializer);
+        writeKeySetsLPr(serializer);
+        serializer.startTag(null, "lastIssuedKeyId");
+        serializer.attribute(null, "value", Long.toString(lastIssuedKeyId));
+        serializer.endTag(null, "lastIssuedKeyId");
+        serializer.startTag(null, "lastIssuedKeySetId");
+        serializer.attribute(null, "value", Long.toString(lastIssuedKeySetId));
+        serializer.endTag(null, "lastIssuedKeySetId");
+        serializer.endTag(null, "keyset-settings");
+    }
+
+    void writePublicKeysLPr(XmlSerializer serializer) throws IOException {
+        serializer.startTag(null, "keys");
+        for (int pKeyIndex = 0; pKeyIndex < mPublicKeys.size(); pKeyIndex++) {
+            long id = mPublicKeys.keyAt(pKeyIndex);
+            PublicKey key = mPublicKeys.valueAt(pKeyIndex);
+            String encodedKey = encodePublicKey(key);
+            serializer.startTag(null, "public-key");
+            serializer.attribute(null, "identifier", Long.toString(id));
+            serializer.attribute(null, "value", encodedKey);
+            serializer.endTag(null, "public-key");
+        }
+        serializer.endTag(null, "keys");
+    }
+
+    void writeKeySetsLPr(XmlSerializer serializer) throws IOException {
+        serializer.startTag(null, "keysets");
+        for (int keySetIndex = 0; keySetIndex < mKeySetMapping.size(); keySetIndex++) {
+            long id = mKeySetMapping.keyAt(keySetIndex);
+            Set<Long> keys = mKeySetMapping.valueAt(keySetIndex);
+            serializer.startTag(null, "keyset");
+            serializer.attribute(null, "identifier", Long.toString(id));
+            for (long keyId : keys) {
+                serializer.startTag(null, "key-id");
+                serializer.attribute(null, "identifier", Long.toString(keyId));
+                serializer.endTag(null, "key-id");
+            }
+            serializer.endTag(null, "keyset");
+        }
+        serializer.endTag(null, "keysets");
+    }
+
+    void readKeySetsLPw(XmlPullParser parser)
+            throws XmlPullParserException, IOException {
+        int type;
+        long currentKeySetId = 0;
+        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT) {
+            if (type == XmlPullParser.END_TAG || type == XmlPullParser.TEXT) {
+                continue;
+            }
+            final String tagName = parser.getName();
+            if (tagName.equals("keys")) {
+                readKeysLPw(parser);
+            } else if (tagName.equals("keysets")) {
+                readKeySetListLPw(parser);
+            } else {
+                PackageManagerService.reportSettingsProblem(Log.WARN,
+                        "Could not read KeySets for KeySetManager!");
+            }
+        }
+    }
+
+    void readKeysLPw(XmlPullParser parser)
+            throws XmlPullParserException, IOException {
+        int outerDepth = parser.getDepth();
+        int type;
+        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+                && (type != XmlPullParser.END_TAG || parser.getDepth() > outerDepth)) {
+            if (type == XmlPullParser.END_TAG || type == XmlPullParser.TEXT) {
+                continue;
+            }
+            final String tagName = parser.getName();
+            if (tagName.equals("public-key")) {
+                readPublicKeyLPw(parser);
+            } else if (tagName.equals("lastIssuedKeyId")) {
+                lastIssuedKeyId = Long.parseLong(parser.getAttributeValue(null, "value"));
+            } else if (tagName.equals("lastIssuedKeySetId")) {
+                lastIssuedKeySetId = Long.parseLong(parser.getAttributeValue(null, "value"));
+            } else {
+                PackageManagerService.reportSettingsProblem(Log.WARN,
+                        "Could not read keys for KeySetManager!");
+            }
+        }
+    }
+
+    void readKeySetListLPw(XmlPullParser parser)
+            throws XmlPullParserException, IOException {
+        int outerDepth = parser.getDepth();
+        int type;
+        long currentKeySetId = 0;
+        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+                && (type != XmlPullParser.END_TAG || parser.getDepth() > outerDepth)) {
+            if (type == XmlPullParser.END_TAG || type == XmlPullParser.TEXT) {
+                continue;
+            }
+            final String tagName = parser.getName();
+            if (tagName.equals("keyset")) {
+                currentKeySetId = readIdentifierLPw(parser);
+                mKeySets.put(currentKeySetId, new KeySet(new Binder()));
+                mKeySetMapping.put(currentKeySetId, new HashSet<Long>());
+            } else if (tagName.equals("key-id")) {
+                long id = readIdentifierLPw(parser);
+                mKeySetMapping.get(currentKeySetId).add(id);
+            } else {
+                PackageManagerService.reportSettingsProblem(Log.WARN,
+                        "Could not read KeySets for KeySetManager!");
+            }
+        }
+    }
+
+    long readIdentifierLPw(XmlPullParser parser)
+            throws XmlPullParserException {
+        return Long.parseLong(parser.getAttributeValue(null, "identifier"));
+    }
+
+    void readPublicKeyLPw(XmlPullParser parser)
+            throws XmlPullParserException {
+        String encodedID = parser.getAttributeValue(null, "identifier");
+        long identifier = Long.parseLong(encodedID);
+        String encodedPublicKey = parser.getAttributeValue(null, "value");
+        PublicKey pub = PackageParser.parsePublicKey(encodedPublicKey);
+        if (pub == null) {
+            PackageManagerService.reportSettingsProblem(Log.WARN,
+                    "Could not read public key for KeySetManager!");
+        } else {
+            mPublicKeys.put(identifier, pub);
+        }
+    }
+}
\ No newline at end of file
diff --git a/services/java/com/android/server/pm/PackageKeySetData.java b/services/java/com/android/server/pm/PackageKeySetData.java
new file mode 100644
index 0000000..01ba5ba
--- /dev/null
+++ b/services/java/com/android/server/pm/PackageKeySetData.java
@@ -0,0 +1,91 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.pm;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+public class PackageKeySetData {
+
+    private long[] mSigningKeySets;
+
+    private long[] mDefinedKeySets;
+
+    private final Map<String, Long> mKeySetAliases;
+
+    PackageKeySetData() {
+        mSigningKeySets = new long[0];
+        mDefinedKeySets = new long[0];
+        mKeySetAliases =  new HashMap<String, Long>();
+    }
+
+    PackageKeySetData(PackageKeySetData original) {
+        mSigningKeySets = original.getSigningKeySets().clone();
+        mDefinedKeySets = original.getDefinedKeySets().clone();
+        mKeySetAliases = new HashMap<String, Long>();
+        mKeySetAliases.putAll(original.getAliases());
+    }
+
+    public void addSigningKeySet(long ks) {
+        // deduplicate
+        for (long knownKeySet : mSigningKeySets) {
+            if (ks == knownKeySet) {
+                return;
+            }
+        }
+        int end = mSigningKeySets.length;
+        mSigningKeySets = Arrays.copyOf(mSigningKeySets, end + 1);
+        mSigningKeySets[end] = ks;
+    }
+
+    public void addDefinedKeySet(long ks, String alias) {
+        // deduplicate
+        for (long knownKeySet : mDefinedKeySets) {
+            if (ks == knownKeySet) {
+                return;
+            }
+        }
+        int end = mDefinedKeySets.length;
+        mDefinedKeySets = Arrays.copyOf(mDefinedKeySets, end + 1);
+        mDefinedKeySets[end] = ks;
+        mKeySetAliases.put(alias, ks);
+    }
+
+    public boolean packageIsSignedBy(long ks) {
+        for (long signingKeySet : mSigningKeySets) {
+            if (ks == signingKeySet) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public long[] getSigningKeySets() {
+        return mSigningKeySets;
+    }
+
+    public long[] getDefinedKeySets() {
+        return mDefinedKeySets;
+    }
+
+    public Map<String, Long> getAliases() {
+        return mKeySetAliases;
+    }
+}
\ No newline at end of file
diff --git a/services/java/com/android/server/pm/PackageManagerService.java b/services/java/com/android/server/pm/PackageManagerService.java
index 5f44ff4..0c8d9d1 100644
--- a/services/java/com/android/server/pm/PackageManagerService.java
+++ b/services/java/com/android/server/pm/PackageManagerService.java
@@ -70,6 +70,7 @@
 import android.content.pm.IPackageMoveObserver;
 import android.content.pm.IPackageStatsObserver;
 import android.content.pm.InstrumentationInfo;
+import android.content.pm.KeySet;
 import android.content.pm.PackageCleanItem;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageInfoLite;
@@ -113,10 +114,12 @@
 import android.os.UserManager;
 import android.os.Environment.UserEnvironment;
 import android.security.SystemKeyStore;
+import android.util.Base64;
 import android.util.DisplayMetrics;
 import android.util.EventLog;
 import android.util.Log;
 import android.util.LogPrinter;
+import android.util.LongSparseArray;
 import android.util.Slog;
 import android.util.SparseArray;
 import android.util.Xml;
@@ -1022,6 +1025,7 @@
 
             mRestoredSettings = mSettings.readLPw(this, sUserManager.getUsers(false),
                     mSdkVersion, mOnlyCore);
+
             long startTime = SystemClock.uptimeMillis();
 
             EventLog.writeEvent(EventLogTags.BOOT_PROGRESS_PMS_SYSTEM_SCAN_START,
@@ -3262,10 +3266,12 @@
         pp.setOnlyCoreApps(mOnlyCore);
         final PackageParser.Package pkg = pp.parsePackage(scanFile,
                 scanPath, mMetrics, parseFlags);
+
         if (pkg == null) {
             mLastScanError = pp.getParseError();
             return null;
         }
+
         PackageSetting ps = null;
         PackageSetting updatedPkg;
         // reader
@@ -3408,6 +3414,7 @@
         } else {
             resPath = pkg.mScanPath;
         }
+
         codePath = pkg.mScanPath;
         // Set application objects path explicitly.
         setApplicationInfoPaths(pkg, codePath, resPath);
@@ -4230,6 +4237,24 @@
                 }
             }
 
+            // Add the package's KeySets to the global KeySetManager
+            KeySetManager ksm = mSettings.mKeySetManager;
+            try {
+                ksm.addSigningKeySetToPackage(pkg.packageName, pkg.mSigningKeys);
+                if (pkg.mKeySetMapping != null) {
+                    for (Map.Entry<String, Set<PublicKey>> entry : pkg.mKeySetMapping.entrySet()) {
+                        if (entry.getValue() != null) {
+                            ksm.addDefinedKeySetToPackage(pkg.packageName,
+                                entry.getValue(), entry.getKey());
+                        }
+                    }
+                }
+            } catch (NullPointerException e) {
+                Slog.e(TAG, "Could not add KeySet to " + pkg.packageName, e);
+            } catch (IllegalArgumentException e) {
+                Slog.e(TAG, "Could not add KeySet to malformed package" + pkg.packageName, e);
+            }
+
             int N = pkg.providers.size();
             StringBuilder r = null;
             int i;
@@ -8420,7 +8445,9 @@
             removePackageDataLI(ps, outInfo, flags, writeSettings);
             return true;
         }
+
         boolean ret = false;
+        mSettings.mKeySetManager.removeAppKeySetData(packageName);
         if (isSystemApp(ps)) {
             Log.i(TAG, "Removing system package:" + ps.name);
             // When an updated system application is deleted we delete the existing resources as well and
@@ -8433,6 +8460,7 @@
             ret = deleteInstalledPackageLI(ps, deleteCodeAndResources, flags, outInfo,
                     writeSettings);
         }
+
         return ret;
     }
 
@@ -9234,6 +9262,8 @@
 
         public static final int DUMP_PREFERRED_XML = 1 << 10;
 
+        public static final int DUMP_KEYSETS = 1 << 11;
+
         public static final int OPTION_SHOW_FILTERS = 1 << 0;
 
         private int mTypes;
@@ -9331,6 +9361,7 @@
                 pw.println("    m[essages]: print collected runtime messages");
                 pw.println("    v[erifiers]: print package verifier info");
                 pw.println("    <package.name>: info about given package");
+                pw.println("    k[eysets]: print known keysets");
                 return;
             } else if ("-f".equals(opt)) {
                 dumpState.setOptionEnabled(DumpState.OPTION_SHOW_FILTERS);
@@ -9372,6 +9403,8 @@
                 dumpState.setDump(DumpState.DUMP_MESSAGES);
             } else if ("v".equals(cmd) || "verifiers".equals(cmd)) {
                 dumpState.setDump(DumpState.DUMP_VERIFIERS);
+            } else if ("k".equals(cmd) || "keysets".equals(cmd)) {
+                dumpState.setDump(DumpState.DUMP_KEYSETS);
             }
         }
 
@@ -9507,7 +9540,14 @@
                     }
                 }
             }
-            
+
+            if (dumpState.isDumping(DumpState.DUMP_KEYSETS)) {
+                if (dumpState.onTitlePrinted()) {
+                    pw.println(" ");
+                }
+                mSettings.mKeySetManager.dump(pw);
+            }
+
             if (dumpState.isDumping(DumpState.DUMP_PACKAGES)) {
                 mSettings.dumpPackagesLPr(pw, packageName, dumpState);
             }
diff --git a/services/java/com/android/server/pm/PackageSettingBase.java b/services/java/com/android/server/pm/PackageSettingBase.java
index ae1b213..2a723b4 100644
--- a/services/java/com/android/server/pm/PackageSettingBase.java
+++ b/services/java/com/android/server/pm/PackageSettingBase.java
@@ -65,6 +65,8 @@
     boolean permissionsFixed;
     boolean haveGids;
 
+    PackageKeySetData keySetData = new PackageKeySetData();
+
     private static final PackageUserState DEFAULT_USER_STATE = new PackageUserState();
 
     // Whether this package is currently stopped, thus can not be
@@ -120,6 +122,9 @@
         origPackage = base.origPackage;
 
         installerPackageName = base.installerPackageName;
+
+        keySetData = new PackageKeySetData(base.keySetData);
+
     }
 
     void init(File codePath, File resourcePath, String nativeLibraryPathString,
@@ -170,6 +175,7 @@
             userState.put(base.userState.keyAt(i), base.userState.valueAt(i));
         }
         installStatus = base.installStatus;
+        keySetData = base.keySetData;
     }
 
     private PackageUserState modifyUserState(int userId) {
diff --git a/services/java/com/android/server/pm/Settings.java b/services/java/com/android/server/pm/Settings.java
index 13f514b..b3f87ff 100644
--- a/services/java/com/android/server/pm/Settings.java
+++ b/services/java/com/android/server/pm/Settings.java
@@ -44,6 +44,7 @@
 import android.content.Intent;
 import android.content.pm.ApplicationInfo;
 import android.content.pm.ComponentInfo;
+import android.content.pm.KeySet;
 import android.content.pm.PackageCleanItem;
 import android.content.pm.PackageManager;
 import android.content.pm.PackageParser;
@@ -58,6 +59,7 @@
 import android.os.Process;
 import android.os.UserHandle;
 import android.util.Log;
+import android.util.LongSparseArray;
 import android.util.Slog;
 import android.util.SparseArray;
 import android.util.Xml;
@@ -68,6 +70,7 @@
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.PrintWriter;
+import java.security.PublicKey;
 import java.text.SimpleDateFormat;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -177,6 +180,9 @@
     private final Context mContext;
 
     private final File mSystemDir;
+
+    public final KeySetManager mKeySetManager = new KeySetManager(mPackages);
+
     Settings(Context context) {
         this(context, Environment.getDataDirectory());
     }
@@ -1325,6 +1331,8 @@
                 }
             }
             
+            mKeySetManager.writeKeySetManagerLPr(serializer);
+
             serializer.endTag(null, "packages");
 
             serializer.endDocument();
@@ -1512,9 +1520,31 @@
             serializer.endTag(null, "perms");
         }
 
+        writeSigningKeySetsLPr(serializer, pkg.keySetData);
+        writeKeySetAliasesLPr(serializer, pkg.keySetData);
+
         serializer.endTag(null, "package");
     }
 
+    void writeSigningKeySetsLPr(XmlSerializer serializer,
+            PackageKeySetData data) throws IOException {
+        for (long id : data.getSigningKeySets()) {
+            serializer.startTag(null, "signing-keyset");
+            serializer.attribute(null, "identifier", Long.toString(id));
+            serializer.endTag(null, "signing-keyset");
+        }
+    }
+
+    void writeKeySetAliasesLPr(XmlSerializer serializer,
+            PackageKeySetData data) throws IOException {
+        for (Map.Entry<String, Long> e: data.getAliases().entrySet()) {
+            serializer.startTag(null, "defined-keyset");
+            serializer.attribute(null, "alias", e.getKey());
+            serializer.attribute(null, "identifier", Long.toString(e.getValue()));
+            serializer.endTag(null, "defined-keyset");
+        }
+    }
+
     void writePermissionLPr(XmlSerializer serializer, BasePermission bp)
             throws XmlPullParserException, java.io.IOException {
         if (bp.type != BasePermission.TYPE_BUILTIN && bp.sourcePackage != null) {
@@ -1692,6 +1722,8 @@
                 } else if (TAG_READ_EXTERNAL_STORAGE.equals(tagName)) {
                     final String enforcement = parser.getAttributeValue(null, ATTR_ENFORCEMENT);
                     mReadExternalStorageEnforced = "1".equals(enforcement);
+                } else if (tagName.equals("keyset-settings")) {
+                    mKeySetManager.readKeySetsLPw(parser);
                 } else {
                     Slog.w(PackageManagerService.TAG, "Unknown element under <packages>: "
                             + parser.getName());
@@ -2287,12 +2319,22 @@
                 } else if (tagName.equals("perms")) {
                     readGrantedPermissionsLPw(parser, packageSetting.grantedPermissions);
                     packageSetting.permissionsFixed = true;
+                } else if (tagName.equals("signing-keyset")) {
+                    long id = Long.parseLong(parser.getAttributeValue(null, "identifier"));
+                    packageSetting.keySetData.addSigningKeySet(id);
+                    Slog.e(TAG, "Adding signing keyset " + Long.toString(id) + " to " + name);
+                } else if (tagName.equals("defined-keyset")) {
+                    long id = Long.parseLong(parser.getAttributeValue(null, "identifier"));
+                    String alias = parser.getAttributeValue(null, "alias");
+                    packageSetting.keySetData.addDefinedKeySet(id, alias);
                 } else {
                     PackageManagerService.reportSettingsProblem(Log.WARN,
                             "Unknown element under <package>: " + parser.getName());
                     XmlUtils.skipCurrentTag(parser);
                 }
             }
+
+
         } else {
             XmlUtils.skipCurrentTag(parser);
         }