diff --git a/binder_bindings/android/os/IUpdateEngine.aidl b/binder_bindings/android/os/IUpdateEngine.aidl
index 1305079..8a5ec71 100644
--- a/binder_bindings/android/os/IUpdateEngine.aidl
+++ b/binder_bindings/android/os/IUpdateEngine.aidl
@@ -45,4 +45,17 @@
   void resetStatus();
   /** @hide */
   boolean verifyPayloadApplicable(in String metadataFilename);
+  /**
+   * Allocate space on userdata partition.
+   *
+   * @return 0 indicates allocation is successful.
+   *   Non-zero indicates space is insufficient. The returned value is the
+   *   total required space (in bytes) on userdata partition.
+   *
+   * @throws ServiceSpecificException for other errors.
+   *
+   * @hide
+   */
+  long allocateSpaceForPayload(in String metadataFilename,
+                               in String[] headerKeyValuePairs);
 }
diff --git a/binder_service_android.cc b/binder_service_android.cc
index 994dcfa..214801b 100644
--- a/binder_service_android.cc
+++ b/binder_service_android.cc
@@ -199,4 +199,23 @@
   return true;
 }
 
+Status BinderUpdateEngineAndroidService::allocateSpaceForPayload(
+    const android::String16& metadata_filename,
+    const vector<android::String16>& header_kv_pairs,
+    int64_t* return_value) {
+  const std::string payload_metadata{
+      android::String8{metadata_filename}.string()};
+  vector<string> str_headers = ToVecString(header_kv_pairs);
+  LOG(INFO) << "Received a request of allocating space for " << payload_metadata
+            << ".";
+  brillo::ErrorPtr error;
+  *return_value =
+      static_cast<int64_t>(service_delegate_->AllocateSpaceForPayload(
+          payload_metadata, str_headers, &error));
+  if (error != nullptr)
+    return ErrorPtrToStatus(error);
+
+  return Status::ok();
+}
+
 }  // namespace chromeos_update_engine
diff --git a/binder_service_android.h b/binder_service_android.h
index 0dda93b..5207075 100644
--- a/binder_service_android.h
+++ b/binder_service_android.h
@@ -70,6 +70,10 @@
   android::binder::Status resetStatus() override;
   android::binder::Status verifyPayloadApplicable(
       const android::String16& metadata_filename, bool* return_value) override;
+  android::binder::Status allocateSpaceForPayload(
+      const android::String16& metadata_filename,
+      const std::vector<android::String16>& header_kv_pairs,
+      int64_t* return_value) override;
 
  private:
   // Remove the passed |callback| from the list of registered callbacks. Called
diff --git a/service_delegate_android_interface.h b/service_delegate_android_interface.h
index 6bd75b6..7f0169e 100644
--- a/service_delegate_android_interface.h
+++ b/service_delegate_android_interface.h
@@ -83,6 +83,19 @@
   virtual bool VerifyPayloadApplicable(const std::string& metadata_filename,
                                        brillo::ErrorPtr* error) = 0;
 
+  // Allocates space for a payload.
+  // Returns 0 if space is successfully preallocated.
+  // Return non-zero if not enough space is not available; returned value is
+  // the total space required (in bytes) to be free on the device for this
+  // update to be applied, and |error| is unset.
+  // In case of error, returns 0, and sets |error| accordingly.
+  //
+  // This function may block for several minutes in the worst case.
+  virtual uint64_t AllocateSpaceForPayload(
+      const std::string& metadata_filename,
+      const std::vector<std::string>& key_value_pair_headers,
+      brillo::ErrorPtr* error) = 0;
+
  protected:
   ServiceDelegateAndroidInterface() = default;
 };
diff --git a/update_attempter_android.cc b/update_attempter_android.cc
index d775679..59cdbb8 100644
--- a/update_attempter_android.cc
+++ b/update_attempter_android.cc
@@ -901,4 +901,13 @@
   return GetCurrentSlot() == 0 ? 1 : 0;
 }
 
+uint64_t UpdateAttempterAndroid::AllocateSpaceForPayload(
+    const std::string& metadata_filename,
+    const vector<string>& key_value_pair_headers,
+    brillo::ErrorPtr* error) {
+  // TODO(elsk): implement b/138808058
+  LogAndSetError(error, FROM_HERE, "Not implemented.");
+  return 0;
+}
+
 }  // namespace chromeos_update_engine
diff --git a/update_attempter_android.h b/update_attempter_android.h
index 44b66d3..309adff 100644
--- a/update_attempter_android.h
+++ b/update_attempter_android.h
@@ -77,6 +77,10 @@
   bool ResetStatus(brillo::ErrorPtr* error) override;
   bool VerifyPayloadApplicable(const std::string& metadata_filename,
                                brillo::ErrorPtr* error) override;
+  uint64_t AllocateSpaceForPayload(
+      const std::string& metadata_filename,
+      const std::vector<std::string>& key_value_pair_headers,
+      brillo::ErrorPtr* error) override;
 
   // ActionProcessorDelegate methods:
   void ProcessingDone(const ActionProcessor* processor,