diff --git a/keystore/Android.mk b/keystore/Android.mk
index aa40fd1..8bf2852 100644
--- a/keystore/Android.mk
+++ b/keystore/Android.mk
@@ -21,7 +21,7 @@
 LOCAL_MULTILIB := 32
 endif
 LOCAL_CFLAGS := -Wall -Wextra -Werror -Wunused
-LOCAL_SRC_FILES := keystore.cpp keyblob_utils.cpp
+LOCAL_SRC_FILES := keystore.cpp keyblob_utils.cpp operation.cpp
 LOCAL_SHARED_LIBRARIES := \
 	libbinder \
 	libcutils \
diff --git a/keystore/IKeystoreService.cpp b/keystore/IKeystoreService.cpp
index e3f7602..53e4e31 100644
--- a/keystore/IKeystoreService.cpp
+++ b/keystore/IKeystoreService.cpp
@@ -1125,7 +1125,7 @@
     }
 
     virtual void update(const sp<IBinder>& token, const KeymasterArguments& params,
-                        uint8_t* opData, size_t dataLength, OperationResult* result)
+                        const uint8_t* opData, size_t dataLength, OperationResult* result)
     {
         if (!result) {
             return;
@@ -1154,7 +1154,7 @@
     }
 
     virtual void finish(const sp<IBinder>& token, const KeymasterArguments& params,
-                        uint8_t* signature, size_t signatureLength, OperationResult* result)
+                        const uint8_t* signature, size_t signatureLength, OperationResult* result)
     {
         if (!result) {
             return;
diff --git a/keystore/include/keystore/IKeystoreService.h b/keystore/include/keystore/IKeystoreService.h
index f69b76e..f671077 100644
--- a/keystore/include/keystore/IKeystoreService.h
+++ b/keystore/include/keystore/IKeystoreService.h
@@ -217,10 +217,11 @@
                        OperationResult* result) = 0;
 
     virtual void update(const sp<IBinder>& token, const KeymasterArguments& params,
-                        uint8_t* data, size_t dataLength, OperationResult* result) = 0;
+                        const uint8_t* data, size_t dataLength, OperationResult* result) = 0;
 
     virtual void finish(const sp<IBinder>& token, const KeymasterArguments& params,
-                        uint8_t* signature, size_t signatureLength, OperationResult* result) = 0;
+                        const uint8_t* signature, size_t signatureLength,
+                        OperationResult* result) = 0;
 
     virtual int32_t abort(const sp<IBinder>& handle) = 0;
 
diff --git a/keystore/keystore.cpp b/keystore/keystore.cpp
index ea9556a..46bc174 100644
--- a/keystore/keystore.cpp
+++ b/keystore/keystore.cpp
@@ -63,6 +63,7 @@
 #include <selinux/android.h>
 
 #include "defaults.h"
+#include "operation.h"
 
 /* KeyStore is a secured storage for key-value pairs. In this implementation,
  * each file stores one key-value pair. Keys are encoded in file names, and
@@ -1619,12 +1620,16 @@
 class KeyStoreProxy : public BnKeystoreService, public IBinder::DeathRecipient {
 public:
     KeyStoreProxy(KeyStore* keyStore)
-        : mKeyStore(keyStore)
+        : mKeyStore(keyStore),
+          mOperationMap(this)
     {
     }
 
-    void binderDied(const wp<IBinder>&) {
-        ALOGE("binder death detected");
+    void binderDied(const wp<IBinder>& who) {
+        auto operations = mOperationMap.getOperationsForToken(who.unsafe_get());
+        for (auto token: operations) {
+            abort(token);
+        }
     }
 
     int32_t test() {
@@ -2670,25 +2675,122 @@
         result->resultCode = rc ? rc : ::NO_ERROR;
     }
 
-    void begin(const sp<IBinder>& /*appToken*/, const String16& /*name*/,
-               keymaster_purpose_t /*purpose*/, bool /*pruneable*/,
-               const KeymasterArguments& /*params*/, KeymasterArguments* /*outParams*/,
-               OperationResult* result) {
-        result->resultCode = KM_ERROR_UNIMPLEMENTED;
+    void begin(const sp<IBinder>& appToken, const String16& name, keymaster_purpose_t purpose,
+               bool pruneable, const KeymasterArguments& params,
+               KeymasterArguments* outParams, OperationResult* result) {
+        if (!result || !outParams) {
+            ALOGE("Unexpected null arguments to begin()");
+            return;
+        }
+        uid_t callingUid = IPCThreadState::self()->getCallingUid();
+        if (!pruneable && get_app_id(callingUid) != AID_SYSTEM) {
+            ALOGE("Non-system uid %d trying to start non-pruneable operation", callingUid);
+            result->resultCode = ::PERMISSION_DENIED;
+            return;
+        }
+        Blob keyBlob;
+        String8 name8(name);
+        ResponseCode responseCode = mKeyStore->getKeyForName(&keyBlob, name8, callingUid,
+                TYPE_KEYMASTER_10);
+        if (responseCode != ::NO_ERROR) {
+            result->resultCode = responseCode;
+            return;
+        }
+        keymaster_key_blob_t key;
+        key.key_material_size = keyBlob.getLength();
+        key.key_material = keyBlob.getValue();
+        keymaster_key_param_t* out;
+        size_t outSize;
+        keymaster_operation_handle_t handle;
+        keymaster1_device_t* dev = mKeyStore->getDeviceForBlob(keyBlob);
+        // TODO: Check authorization.
+        keymaster_error_t err = dev->begin(dev, purpose, &key, params.params.data(),
+                                           params.params.size(), &out, &outSize,
+                                           &handle);
+
+        // If there are too many operations abort the oldest operation that was
+        // started as pruneable and try again.
+        while (err == KM_ERROR_TOO_MANY_OPERATIONS && mOperationMap.hasPruneableOperation()) {
+            sp<IBinder> oldest = mOperationMap.getOldestPruneableOperation();
+            ALOGD("Ran out of operation handles, trying to prune %p", oldest.get());
+            if (abort(oldest) != ::NO_ERROR) {
+                break;
+            }
+            err = dev->begin(dev, purpose, &key, params.params.data(),
+                             params.params.size(), &out, &outSize,
+                             &handle);
+        }
+        if (err) {
+            result->resultCode = err;
+            return;
+        }
+        if (out) {
+            outParams->params.assign(out, out + outSize);
+            free(out);
+        }
+
+        sp<IBinder> operationToken = mOperationMap.addOperation(handle, dev, appToken, pruneable);
+        result->resultCode = ::NO_ERROR;
+        result->token = operationToken;
     }
 
-    void update(const sp<IBinder>& /*token*/, const KeymasterArguments& /*params*/,
-                uint8_t* /*data*/, size_t /*dataLength*/, OperationResult* result) {
-        result->resultCode = KM_ERROR_UNIMPLEMENTED;
+    void update(const sp<IBinder>& token, const KeymasterArguments& params, const uint8_t* data,
+                size_t dataLength, OperationResult* result) {
+        const keymaster1_device_t* dev;
+        keymaster_operation_handle_t handle;
+        if (!mOperationMap.getOperation(token, &handle, &dev)) {
+            result->resultCode = KM_ERROR_INVALID_OPERATION_HANDLE;
+            return;
+        }
+        uint8_t* output_buf = NULL;
+        size_t output_length = 0;
+        size_t consumed = 0;
+        // TODO: Check authorization.
+        keymaster_error_t err = dev->update(dev, handle, params.params.data(),
+                                            params.params.size(), data, dataLength,
+                                            &consumed, &output_buf, &output_length);
+        result->data.reset(output_buf);
+        result->dataLength = output_length;
+        result->inputConsumed = consumed;
+        result->resultCode = err ? (int32_t) err : ::NO_ERROR;
     }
 
-    void finish(const sp<IBinder>& /*token*/, const KeymasterArguments& /*args*/,
-                uint8_t* /*signature*/, size_t /*signatureLength*/, OperationResult* result) {
-        result->resultCode = KM_ERROR_UNIMPLEMENTED;
+    void finish(const sp<IBinder>& token, const KeymasterArguments& params,
+                const uint8_t* signature, size_t signatureLength, OperationResult* result) {
+        const keymaster1_device_t* dev;
+        keymaster_operation_handle_t handle;
+        if (!mOperationMap.getOperation(token, &handle, &dev)) {
+            result->resultCode = KM_ERROR_INVALID_OPERATION_HANDLE;
+            return;
+        }
+        uint8_t* output_buf = NULL;
+        size_t output_length = 0;
+        // TODO: Check authorization.
+        keymaster_error_t err = dev->finish(dev, handle, params.params.data(),
+                                            params.params.size(), signature, signatureLength,
+                                            &output_buf, &output_length);
+        // Remove the operation regardless of the result
+        mOperationMap.removeOperation(token);
+        result->data.reset(output_buf);
+        result->dataLength = output_length;
+        result->resultCode = err ? (int32_t) err : ::NO_ERROR;
     }
 
-    int32_t abort(const sp<IBinder>& /*token*/) {
-        return KM_ERROR_UNIMPLEMENTED;
+    int32_t abort(const sp<IBinder>& token) {
+        const keymaster1_device_t* dev;
+        keymaster_operation_handle_t handle;
+        if (!mOperationMap.getOperation(token, &handle, &dev)) {
+            return KM_ERROR_INVALID_OPERATION_HANDLE;
+        }
+        mOperationMap.removeOperation(token);
+        if (!dev->abort) {
+            return KM_ERROR_UNIMPLEMENTED;
+        }
+        int32_t rc = dev->abort(dev, handle);
+        if (rc) {
+            return rc;
+        }
+        return ::NO_ERROR;
     }
 
 private:
@@ -2731,6 +2833,7 @@
     }
 
     ::KeyStore* mKeyStore;
+    OperationMap mOperationMap;
 };
 
 }; // namespace android
diff --git a/keystore/operation.cpp b/keystore/operation.cpp
new file mode 100644
index 0000000..0d5b17b
--- /dev/null
+++ b/keystore/operation.cpp
@@ -0,0 +1,126 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+#define LOG_TAG "KeystoreOperation"
+
+#include "operation.h"
+
+#include <algorithm>
+
+namespace android {
+OperationMap::OperationMap(IBinder::DeathRecipient* deathRecipient)
+        : mDeathRecipient(deathRecipient) {
+}
+
+sp<IBinder> OperationMap::addOperation(keymaster_operation_handle_t handle,
+                                       const keymaster1_device_t* dev,
+                                       sp<IBinder> appToken, bool pruneable) {
+    sp<IBinder> token = new BBinder();
+    mMap[token] = Operation(handle, dev, appToken);
+    if (pruneable) {
+        mLru.push_back(token);
+    }
+    if (mAppTokenMap.find(appToken) == mAppTokenMap.end()) {
+        appToken->linkToDeath(mDeathRecipient);
+    }
+    mAppTokenMap[appToken].push_back(token);
+    return token;
+}
+
+bool OperationMap::getOperation(sp<IBinder> token, keymaster_operation_handle_t* outHandle,
+                                const keymaster1_device_t** outDevice) {
+    if (!outHandle || !outDevice) {
+        return false;
+    }
+    auto entry = mMap.find(token);
+    if (entry == mMap.end()) {
+        return false;
+    }
+    updateLru(token);
+
+    *outHandle = entry->second.handle;
+    *outDevice = entry->second.device;
+    return true;
+}
+
+void OperationMap::updateLru(sp<IBinder> token) {
+    auto lruEntry = std::find(mLru.begin(), mLru.end(), token);
+    if (lruEntry != mLru.end()) {
+        mLru.erase(lruEntry);
+        mLru.push_back(token);
+    }
+}
+
+bool OperationMap::removeOperation(sp<IBinder> token) {
+    auto entry = mMap.find(token);
+    if (entry == mMap.end()) {
+        return false;
+    }
+    sp<IBinder> appToken = entry->second.appToken;
+    mMap.erase(entry);
+    auto lruEntry = std::find(mLru.begin(), mLru.end(), token);
+    if (lruEntry != mLru.end()) {
+        mLru.erase(lruEntry);
+    }
+    removeOperationTracking(token, appToken);
+    return true;
+}
+
+void OperationMap::removeOperationTracking(sp<IBinder> token, sp<IBinder> appToken) {
+    auto appEntry = mAppTokenMap.find(appToken);
+    if (appEntry == mAppTokenMap.end()) {
+        ALOGE("Entry for %p contains unmapped application token %p", token.get(), appToken.get());
+        return;
+    }
+    auto tokenEntry = std::find(appEntry->second.begin(), appEntry->second.end(), token);
+    appEntry->second.erase(tokenEntry);
+    // Stop listening for death if all operations tied to the token have finished.
+    if (appEntry->second.size() == 0) {
+        appToken->unlinkToDeath(mDeathRecipient);
+        mAppTokenMap.erase(appEntry);
+    }
+}
+
+bool OperationMap::hasPruneableOperation() {
+    return mLru.size() != 0;
+}
+
+sp<IBinder> OperationMap::getOldestPruneableOperation() {
+    if (!hasPruneableOperation()) {
+        return sp<IBinder>(NULL);
+    }
+    return mLru[0];
+}
+
+std::vector<sp<IBinder>> OperationMap::getOperationsForToken(sp<IBinder> appToken) {
+    auto appEntry = mAppTokenMap.find(appToken);
+    if (appEntry != mAppTokenMap.end()) {
+        return appEntry->second;
+    } else {
+        return std::vector<sp<IBinder>>();
+    }
+}
+
+OperationMap::Operation::Operation(keymaster_operation_handle_t handle_,
+                                   const keymaster1_device_t* device_,
+                                   sp<IBinder> appToken_)
+    : handle(handle_),
+      device(device_),
+      appToken(appToken_) {
+}
+
+OperationMap::Operation::Operation() : handle(0), device(NULL), appToken(NULL) {
+}
+} // namespace android
diff --git a/keystore/operation.h b/keystore/operation.h
new file mode 100644
index 0000000..f6f3ea7
--- /dev/null
+++ b/keystore/operation.h
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#ifndef KEYSTORE_OPERATION_H_
+#define KEYSTORE_OPERATION_H_
+
+#include <hardware/keymaster1.h>
+#include <binder/Binder.h>
+#include <binder/IBinder.h>
+#include <utils/LruCache.h>
+#include <utils/StrongPointer.h>
+#include <map>
+#include <vector>
+
+namespace android {
+
+/**
+ * OperationMap handles the translation of keymaster_operation_handle_t's and
+ * keymaster1_device_t's to opaque binder tokens that can be used to reference
+ * that operation at a later time by applications. It also does LRU tracking
+ * for operation pruning and keeps a mapping of clients to operations to allow
+ * for graceful handling of application death.
+ */
+class OperationMap {
+public:
+    OperationMap(IBinder::DeathRecipient* deathRecipient);
+    sp<IBinder> addOperation(keymaster_operation_handle_t handle,
+                             const keymaster1_device_t* dev, sp<IBinder> appToken,
+                             bool pruneable);
+    bool getOperation(sp<IBinder> token, keymaster_operation_handle_t* outHandle,
+                      const keymaster1_device_t** outDev);
+    bool removeOperation(sp<IBinder> token);
+    bool hasPruneableOperation();
+    sp<IBinder> getOldestPruneableOperation();
+    std::vector<sp<IBinder>> getOperationsForToken(sp<IBinder> appToken);
+
+private:
+    void updateLru(sp<IBinder> token);
+    void removeOperationTracking(sp<IBinder> token, sp<IBinder> appToken);
+    struct Operation {
+        Operation();
+        Operation(keymaster_operation_handle_t handle, const keymaster1_device_t* device,
+                  sp<IBinder> appToken);
+        keymaster_operation_handle_t handle;
+        const keymaster1_device_t* device;
+        sp<IBinder> appToken;
+    };
+    std::map<sp<IBinder>, struct Operation> mMap;
+    std::vector<sp<IBinder>> mLru;
+    std::map<sp<IBinder>, std::vector<sp<IBinder>>> mAppTokenMap;
+    IBinder::DeathRecipient* mDeathRecipient;
+};
+} // namespace android
+#endif