diff --git a/tools/releasetools/ota_from_target_files.py b/tools/releasetools/ota_from_target_files.py
index 3579645..1e2f39e 100755
--- a/tools/releasetools/ota_from_target_files.py
+++ b/tools/releasetools/ota_from_target_files.py
@@ -1024,6 +1024,9 @@
     """
     return self._GetPropertyFilesString(input_zip, reserve_space=True)
 
+  class InsufficientSpaceException(Exception):
+    pass
+
   def Finalize(self, input_zip, reserved_length):
     """Finalizes a property-files string with actual METADATA offset/size info.
 
@@ -1045,13 +1048,15 @@
       "payload.bin:679:343,payload_properties.txt:378:45,metadata:69:379  ".
 
     Raises:
-      AssertionError: If the reserved length is insufficient to hold the final
-          string.
+      InsufficientSpaceException: If the reserved length is insufficient to hold
+          the final string.
     """
     result = self._GetPropertyFilesString(input_zip, reserve_space=False)
-    assert len(result) <= reserved_length, \
-        'Insufficient reserved space: reserved={}, actual={}'.format(
-            reserved_length, len(result))
+    if len(result) > reserved_length:
+      raise self.InsufficientSpaceException(
+          'Insufficient reserved space: reserved={}, actual={}'.format(
+              reserved_length, len(result)))
+
     result += ' ' * (reserved_length - len(result))
     return result
 
@@ -1089,11 +1094,12 @@
 
     # 'META-INF/com/android/metadata' is required. We don't know its actual
     # offset and length (as well as the values for other entries). So we reserve
-    # 10-byte as a placeholder, which is to cover the space for metadata entry
-    # ('xx:xxx', since it's ZIP_STORED which should appear at the beginning of
-    # the zip), as well as the possible value changes in other entries.
+    # 15-byte as a placeholder ('offset:length'), which is sufficient to cover
+    # the space for metadata entry. Because 'offset' allows a max of 10-digit
+    # (i.e. ~9 GiB), with a max of 4-digit for the length. Note that all the
+    # reserved space serves the metadata entry only.
     if reserve_space:
-      tokens.append('metadata:' + ' ' * 10)
+      tokens.append('metadata:' + ' ' * 15)
     else:
       tokens.append(ComputeEntryOffsetSize(METADATA_NAME))
 
@@ -1252,36 +1258,54 @@
     output_file: The final output ZIP filename.
     needed_property_files: The list of PropertyFiles' to be generated.
   """
-  output_zip = zipfile.ZipFile(
-      input_file, 'a', compression=zipfile.ZIP_DEFLATED)
 
-  # Write the current metadata entry with placeholders.
-  for property_files in needed_property_files:
-    metadata[property_files.name] = property_files.Compute(output_zip)
-  WriteMetadata(metadata, output_zip)
-  common.ZipClose(output_zip)
+  def ComputeAllPropertyFiles(input_file, needed_property_files):
+    # Write the current metadata entry with placeholders.
+    with zipfile.ZipFile(input_file) as input_zip:
+      for property_files in needed_property_files:
+        metadata[property_files.name] = property_files.Compute(input_zip)
+      namelist = input_zip.namelist()
 
-  # SignOutput(), which in turn calls signapk.jar, will possibly reorder the
-  # ZIP entries, as well as padding the entry headers. We do a preliminary
-  # signing (with an incomplete metadata entry) to allow that to happen. Then
-  # compute the ZIP entry offsets, write back the final metadata and do the
-  # final signing.
-  if OPTIONS.no_signing:
-    prelim_signing = input_file
-  else:
+    if METADATA_NAME in namelist:
+      common.ZipDelete(input_file, METADATA_NAME)
+    output_zip = zipfile.ZipFile(input_file, 'a')
+    WriteMetadata(metadata, output_zip)
+    common.ZipClose(output_zip)
+
+    if OPTIONS.no_signing:
+      return input_file
+
     prelim_signing = common.MakeTempFile(suffix='.zip')
     SignOutput(input_file, prelim_signing)
+    return prelim_signing
 
-  # Open the signed zip. Compute the final metadata that's needed for streaming.
-  with zipfile.ZipFile(prelim_signing, 'r') as prelim_signing_zip:
-    for property_files in needed_property_files:
-      metadata[property_files.name] = property_files.Finalize(
-          prelim_signing_zip, len(metadata[property_files.name]))
+  def FinalizeAllPropertyFiles(prelim_signing, needed_property_files):
+    with zipfile.ZipFile(prelim_signing) as prelim_signing_zip:
+      for property_files in needed_property_files:
+        metadata[property_files.name] = property_files.Finalize(
+            prelim_signing_zip, len(metadata[property_files.name]))
+
+  # SignOutput(), which in turn calls signapk.jar, will possibly reorder the ZIP
+  # entries, as well as padding the entry headers. We do a preliminary signing
+  # (with an incomplete metadata entry) to allow that to happen. Then compute
+  # the ZIP entry offsets, write back the final metadata and do the final
+  # signing.
+  prelim_signing = ComputeAllPropertyFiles(input_file, needed_property_files)
+  try:
+    FinalizeAllPropertyFiles(prelim_signing, needed_property_files)
+  except PropertyFiles.InsufficientSpaceException:
+    # Even with the preliminary signing, the entry orders may change
+    # dramatically, which leads to insufficiently reserved space during the
+    # first call to ComputeAllPropertyFiles(). In that case, we redo all the
+    # preliminary signing works, based on the already ordered ZIP entries, to
+    # address the issue.
+    prelim_signing = ComputeAllPropertyFiles(
+        prelim_signing, needed_property_files)
+    FinalizeAllPropertyFiles(prelim_signing, needed_property_files)
 
   # Replace the METADATA entry.
   common.ZipDelete(prelim_signing, METADATA_NAME)
-  output_zip = zipfile.ZipFile(
-      prelim_signing, 'a', compression=zipfile.ZIP_DEFLATED)
+  output_zip = zipfile.ZipFile(prelim_signing, 'a')
   WriteMetadata(metadata, output_zip)
   common.ZipClose(output_zip)
 
@@ -1292,7 +1316,7 @@
     SignOutput(prelim_signing, output_file)
 
   # Reopen the final signed zip to double check the streaming metadata.
-  with zipfile.ZipFile(output_file, 'r') as output_zip:
+  with zipfile.ZipFile(output_file) as output_zip:
     for property_files in needed_property_files:
       property_files.Verify(output_zip, metadata[property_files.name].strip())
 
diff --git a/tools/releasetools/test_ota_from_target_files.py b/tools/releasetools/test_ota_from_target_files.py
index 97687e7..d7cace8 100644
--- a/tools/releasetools/test_ota_from_target_files.py
+++ b/tools/releasetools/test_ota_from_target_files.py
@@ -24,8 +24,8 @@
 import common
 import test_utils
 from ota_from_target_files import (
-    _LoadOemDicts, AbOtaPropertyFiles, BuildInfo, GetPackageMetadata,
-    GetTargetFilesZipForSecondaryImages,
+    _LoadOemDicts, AbOtaPropertyFiles, BuildInfo, FinalizeMetadata,
+    GetPackageMetadata, GetTargetFilesZipForSecondaryImages,
     GetTargetFilesZipWithoutPostinstallConfig, NonAbOtaPropertyFiles,
     Payload, PayloadSigner, POSTINSTALL_CONFIG, PropertyFiles,
     StreamingPropertyFiles, WriteFingerprintAssertion)
@@ -373,11 +373,22 @@
   }
 
   def setUp(self):
+    self.testdata_dir = test_utils.get_testdata_dir()
+    self.assertTrue(os.path.exists(self.testdata_dir))
+
     # Reset the global options as in ota_from_target_files.py.
     common.OPTIONS.incremental_source = None
     common.OPTIONS.downgrade = False
     common.OPTIONS.timestamp = False
     common.OPTIONS.wipe_user_data = False
+    common.OPTIONS.no_signing = False
+    common.OPTIONS.package_key = os.path.join(self.testdata_dir, 'testkey')
+    common.OPTIONS.key_passwords = {
+        common.OPTIONS.package_key : None,
+    }
+
+    common.OPTIONS.search_path = test_utils.get_search_path()
+    self.assertIsNotNone(common.OPTIONS.search_path)
 
   def tearDown(self):
     common.Cleanup()
@@ -590,6 +601,68 @@
     with zipfile.ZipFile(target_file) as verify_zip:
       self.assertNotIn(POSTINSTALL_CONFIG, verify_zip.namelist())
 
+  def _test_FinalizeMetadata(self, large_entry=False):
+    entries = [
+        'required-entry1',
+        'required-entry2',
+    ]
+    zip_file = PropertyFilesTest.construct_zip_package(entries)
+    # Add a large entry of 1 GiB if requested.
+    if large_entry:
+      with zipfile.ZipFile(zip_file, 'a') as zip_fp:
+        zip_fp.writestr(
+            # Using 'zoo' so that the entry stays behind others after signing.
+            'zoo',
+            'A' * 1024 * 1024 * 1024,
+            zipfile.ZIP_STORED)
+
+    metadata = {}
+    output_file = common.MakeTempFile(suffix='.zip')
+    needed_property_files = (
+        TestPropertyFiles(),
+    )
+    FinalizeMetadata(metadata, zip_file, output_file, needed_property_files)
+    self.assertIn('ota-test-property-files', metadata)
+
+  def test_FinalizeMetadata(self):
+    self._test_FinalizeMetadata()
+
+  def test_FinalizeMetadata_withNoSigning(self):
+    common.OPTIONS.no_signing = True
+    self._test_FinalizeMetadata()
+
+  def test_FinalizeMetadata_largeEntry(self):
+    self._test_FinalizeMetadata(large_entry=True)
+
+  def test_FinalizeMetadata_largeEntry_withNoSigning(self):
+    common.OPTIONS.no_signing = True
+    self._test_FinalizeMetadata(large_entry=True)
+
+  def test_FinalizeMetadata_insufficientSpace(self):
+    entries = [
+        'required-entry1',
+        'required-entry2',
+        'optional-entry1',
+        'optional-entry2',
+    ]
+    zip_file = PropertyFilesTest.construct_zip_package(entries)
+    with zipfile.ZipFile(zip_file, 'a') as zip_fp:
+      zip_fp.writestr(
+          # 'foo-entry1' will appear ahead of all other entries (in alphabetical
+          # order) after the signing, which will in turn trigger the
+          # InsufficientSpaceException and an automatic retry.
+          'foo-entry1',
+          'A' * 1024 * 1024,
+          zipfile.ZIP_STORED)
+
+    metadata = {}
+    needed_property_files = (
+        TestPropertyFiles(),
+    )
+    output_file = common.MakeTempFile(suffix='.zip')
+    FinalizeMetadata(metadata, zip_file, output_file, needed_property_files)
+    self.assertIn('ota-test-property-files', metadata)
+
 
 class TestPropertyFiles(PropertyFiles):
   """A class that extends PropertyFiles for testing purpose."""
@@ -609,11 +682,14 @@
 
 class PropertyFilesTest(unittest.TestCase):
 
+  def setUp(self):
+    common.OPTIONS.no_signing = False
+
   def tearDown(self):
     common.Cleanup()
 
   @staticmethod
-  def _construct_zip_package(entries):
+  def construct_zip_package(entries):
     zip_file = common.MakeTempFile(suffix='.zip')
     with zipfile.ZipFile(zip_file, 'w') as zip_fp:
       for entry in entries:
@@ -647,7 +723,7 @@
         'required-entry1',
         'required-entry2',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       property_files_string = property_files.Compute(zip_fp)
@@ -663,7 +739,7 @@
         'optional-entry1',
         'optional-entry2',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       property_files_string = property_files.Compute(zip_fp)
@@ -676,7 +752,7 @@
     entries = (
         'required-entry2',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       self.assertRaises(KeyError, property_files.Compute, zip_fp)
@@ -687,7 +763,7 @@
         'required-entry2',
         'META-INF/com/android/metadata',
     ]
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # pylint: disable=protected-access
@@ -710,7 +786,7 @@
         'optional-entry2',
         'META-INF/com/android/metadata',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # First get the raw metadata string (i.e. without padding space).
@@ -725,7 +801,7 @@
 
       # Or pass in insufficient length.
       self.assertRaises(
-          AssertionError,
+          PropertyFiles.InsufficientSpaceException,
           property_files.Finalize,
           zip_fp,
           raw_length - 1)
@@ -745,7 +821,7 @@
         'optional-entry2',
         'META-INF/com/android/metadata',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = TestPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # First get the raw metadata string (i.e. without padding space).
@@ -787,7 +863,7 @@
         'care_map.txt',
         'compatibility.zip',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = StreamingPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       property_files_string = property_files.Compute(zip_fp)
@@ -804,7 +880,7 @@
         'compatibility.zip',
         'META-INF/com/android/metadata',
     ]
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = StreamingPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # pylint: disable=protected-access
@@ -827,7 +903,7 @@
         'compatibility.zip',
         'META-INF/com/android/metadata',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = StreamingPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # First get the raw metadata string (i.e. without padding space).
@@ -923,8 +999,8 @@
       self.assertEqual(verify_fp.read(), metadata_signature)
 
   @staticmethod
-  def _construct_zip_package_withValidPayload(with_metadata=False):
-    # Cannot use _construct_zip_package() since we need a "valid" payload.bin.
+  def construct_zip_package_withValidPayload(with_metadata=False):
+    # Cannot use construct_zip_package() since we need a "valid" payload.bin.
     target_file = construct_target_files()
     payload = Payload()
     payload.Generate(target_file)
@@ -951,7 +1027,7 @@
     return zip_file
 
   def test_Compute(self):
-    zip_file = self._construct_zip_package_withValidPayload()
+    zip_file = self.construct_zip_package_withValidPayload()
     property_files = AbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       property_files_string = property_files.Compute(zip_fp)
@@ -964,7 +1040,7 @@
         zip_file, tokens, ('care_map.txt', 'compatibility.zip'))
 
   def test_Finalize(self):
-    zip_file = self._construct_zip_package_withValidPayload(with_metadata=True)
+    zip_file = self.construct_zip_package_withValidPayload(with_metadata=True)
     property_files = AbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # pylint: disable=protected-access
@@ -980,7 +1056,7 @@
         zip_file, tokens, ('care_map.txt', 'compatibility.zip'))
 
   def test_Verify(self):
-    zip_file = self._construct_zip_package_withValidPayload(with_metadata=True)
+    zip_file = self.construct_zip_package_withValidPayload(with_metadata=True)
     property_files = AbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file, 'r') as zip_fp:
       # pylint: disable=protected-access
@@ -1001,7 +1077,7 @@
 
   def test_Compute(self):
     entries = ()
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = NonAbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file) as zip_fp:
       property_files_string = property_files.Compute(zip_fp)
@@ -1014,7 +1090,7 @@
     entries = [
         'META-INF/com/android/metadata',
     ]
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = NonAbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file) as zip_fp:
       # pylint: disable=protected-access
@@ -1032,7 +1108,7 @@
     entries = (
         'META-INF/com/android/metadata',
     )
-    zip_file = self._construct_zip_package(entries)
+    zip_file = self.construct_zip_package(entries)
     property_files = NonAbOtaPropertyFiles()
     with zipfile.ZipFile(zip_file) as zip_fp:
       # pylint: disable=protected-access
diff --git a/tools/releasetools/test_utils.py b/tools/releasetools/test_utils.py
index e64355b..a15ff5b 100644
--- a/tools/releasetools/test_utils.py
+++ b/tools/releasetools/test_utils.py
@@ -32,6 +32,22 @@
   return os.path.join(current_dir, 'testdata')
 
 
+def get_search_path():
+  """Returns the search path that has 'framework/signapk.jar' under."""
+  current_dir = os.path.dirname(os.path.realpath(__file__))
+  for path in (
+      # In relative to 'build/make/tools/releasetools' in the Android source.
+      ['..'] * 4 + ['out', 'host', 'linux-x86'],
+      # Or running the script unpacked from otatools.zip.
+      ['..']):
+    full_path = os.path.realpath(os.path.join(current_dir, *path))
+    signapk_path = os.path.realpath(
+        os.path.join(full_path, 'framework', 'signapk.jar'))
+    if os.path.exists(signapk_path):
+      return full_path
+  return None
+
+
 def construct_sparse_image(chunks):
   """Returns a sparse image file constructed from the given chunks.