merge in lmp-mr1-release history after reset to f30eef8f554a3241298a686c5e59e618dbc8e177
diff --git a/CleanSpec.mk b/CleanSpec.mk
index 025edb0..f348692 100644
--- a/CleanSpec.mk
+++ b/CleanSpec.mk
@@ -294,6 +294,11 @@
$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/app/*)
$(call add-clean-step, rm -rf $(PRODUCT_OUT)/obj/APPS/*)
+# API 21!
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/build.prop)
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/app/*)
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/obj/APPS/*)
+
# ************************************************
# NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
# ************************************************
diff --git a/core/Makefile b/core/Makefile
index d3fc6cc..a3f3757 100644
--- a/core/Makefile
+++ b/core/Makefile
@@ -1395,6 +1395,7 @@
$(hide) echo "use_set_metadata=1" >> $(zip_root)/META/misc_info.txt
$(hide) echo "multistage_support=1" >> $(zip_root)/META/misc_info.txt
$(hide) echo "update_rename_support=1" >> $(zip_root)/META/misc_info.txt
+ $(hide) echo "blockimgdiff_versions=1,2" >> $(zip_root)/META/misc_info.txt
ifneq ($(PRODUCTS.$(INTERNAL_PRODUCT).PRODUCT_OEM_PROPERTIES),)
# OTA scripts are only interested in fingerprint related properties
ifneq ($(filter ro.product.brand ro.product.name ro.product.device, $(PRODUCTS.$(INTERNAL_PRODUCT).PRODUCT_OEM_PROPERTIES)),)
diff --git a/core/build_id.mk b/core/build_id.mk
index 843e90a..00a691f 100644
--- a/core/build_id.mk
+++ b/core/build_id.mk
@@ -18,4 +18,4 @@
# (like "CRB01"). It must be a single word, and is
# capitalized by convention.
-export BUILD_ID=LMW87
+export BUILD_ID=LMP
diff --git a/core/definitions.mk b/core/definitions.mk
index 3bded9f..d7d8b25 100644
--- a/core/definitions.mk
+++ b/core/definitions.mk
@@ -2187,11 +2187,13 @@
$(if $(call if-build-from-source,$(2),$(3)),$(eval include $(1)))
endef
-## Return the arch for the source file of a prebuilt
+# Return the arch for the source file of a prebuilt
+# Return "none" if no matching arch found, so the result can be passed to
+# LOCAL_MODULE_TARGET_ARCH.
# $(1) the list of archs supported by the prebuilt
define get-prebuilt-src-arch
$(strip $(if $(filter $(TARGET_ARCH),$(1)),$(TARGET_ARCH),\
- $(if $(filter $(TARGET_2ND_ARCH),$(1)),$(TARGET_2ND_ARCH))))
+ $(if $(filter $(TARGET_2ND_ARCH),$(1)),$(TARGET_2ND_ARCH),none)))
endef
###########################################################
diff --git a/core/tasks/cts.mk b/core/tasks/cts.mk
index 82094b9..2638de7 100644
--- a/core/tasks/cts.mk
+++ b/core/tasks/cts.mk
@@ -17,7 +17,6 @@
cts_name := android-cts
-DDMLIB_JAR := $(HOST_OUT_JAVA_LIBRARIES)/ddmlib-prebuilt.jar
JUNIT_HOST_JAR := $(HOST_OUT_JAVA_LIBRARIES)/junit.jar
HOSTTESTLIB_JAR := $(HOST_OUT_JAVA_LIBRARIES)/hosttestlib.jar
TF_JAR := $(HOST_OUT_JAVA_LIBRARIES)/tradefed-prebuilt.jar
@@ -74,7 +73,6 @@
DEFAULT_TEST_PLAN := $(cts_dir)/$(cts_name)/resource/plans
CTS_TEST_CASE_LIST_FILES := $(foreach c, $(CTS_TEST_CASE_LIST), $(call intermediates-dir-for,APPS,$(c))/package.apk)
-$(cts_dir)/all_cts_files_stamp: PRIVATE_JUNIT_HOST_JAR := $(JUNIT_HOST_JAR)
$(cts_dir)/all_cts_files_stamp: $(CTS_CORE_CASES) $(CTS_TEST_CASES) $(CTS_TEST_CASE_LIST_FILES) $(JUNIT_HOST_JAR) $(HOSTTESTLIB_JAR) $(CTS_HOST_LIBRARY_JARS) $(TF_JAR) $(VMTESTSTF_JAR) $(CTS_TF_JAR) $(CTS_TF_EXEC_PATH) $(CTS_TF_README_PATH) $(ACP) $(CTS_TEST_JAR_FILES)
# Make necessary directory for CTS
$(hide) rm -rf $(PRIVATE_CTS_DIR)
@@ -85,7 +83,7 @@
$(hide) mkdir -p $(PRIVATE_DIR)/repository/plans
# Copy executable and JARs to CTS directory
$(hide) $(ACP) -fp $(VMTESTSTF_JAR) $(PRIVATE_DIR)/repository/testcases
- $(hide) $(ACP) -fp $(DDMLIB_JAR) $(PRIVATE_JUNIT_HOST_JAR) $(HOSTTESTLIB_JAR) $(CTS_HOST_LIBRARY_JARS) $(TF_JAR) $(CTS_TF_JAR) $(CTS_TF_EXEC_PATH) $(CTS_TF_README_PATH) $(PRIVATE_DIR)/tools
+ $(hide) $(ACP) -fp $(HOSTTESTLIB_JAR) $(CTS_HOST_LIBRARY_JARS) $(TF_JAR) $(CTS_TF_JAR) $(CTS_TF_EXEC_PATH) $(CTS_TF_README_PATH) $(PRIVATE_DIR)/tools
# Change mode of the executables
$(foreach jar,$(CTS_TEST_JAR_LIST),$(call copy-testcase-jar,$(jar)))
$(foreach apk,$(CTS_CASE_LIST),$(call copy-testcase-apk,$(apk)))
@@ -318,11 +316,11 @@
CORE_INTERMEDIATES :=$(call intermediates-dir-for,JAVA_LIBRARIES,core-libart,,COMMON)
JUNIT_INTERMEDIATES :=$(call intermediates-dir-for,JAVA_LIBRARIES,core-junit,,COMMON)
-GEN_CLASSPATH := $(CORE_INTERMEDIATES)/classes.jar:$(JUNIT_INTERMEDIATES)/classes.jar:$(VMTESTSTF_JAR):$(DDMLIB_JAR):$(TF_JAR)
+GEN_CLASSPATH := $(CORE_INTERMEDIATES)/classes.jar:$(JUNIT_INTERMEDIATES)/classes.jar:$(VMTESTSTF_JAR):$(TF_JAR)
$(CORE_VM_TEST_TF_DESC): PRIVATE_CLASSPATH:=$(GEN_CLASSPATH)
# Please see big comment above on why this line depends on javalib.jar instead of classes.jar
-$(CORE_VM_TEST_TF_DESC): $(HOST_OUT_JAVA_LIBRARIES)/descGen.jar $(JUNIT_HOST_JAR) $(CORE_INTERMEDIATES)/javalib.jar $(JUNIT_INTERMEDIATES)/javalib.jar $(VMTESTSTF_JAR) $(DDMLIB_JAR) | $(ACP)
+$(CORE_VM_TEST_TF_DESC): $(HOST_OUT_JAVA_LIBRARIES)/descGen.jar $(JUNIT_HOST_JAR) $(CORE_INTERMEDIATES)/javalib.jar $(JUNIT_INTERMEDIATES)/javalib.jar $(VMTESTSTF_JAR) | $(ACP)
$(hide) mkdir -p $(CTS_TESTCASES_OUT)
$(call generate-core-test-description,$(CTS_TESTCASES_OUT)/android.core.vm-tests-tf,\
cts/tests/vm-tests-tf/AndroidManifest.xml,\
diff --git a/core/version_defaults.mk b/core/version_defaults.mk
index ea10f2a..8cb8d26 100644
--- a/core/version_defaults.mk
+++ b/core/version_defaults.mk
@@ -41,7 +41,7 @@
# which is the version that we reveal to the end user.
# Update this value when the platform version changes (rather
# than overriding it somewhere else). Can be an arbitrary string.
- PLATFORM_VERSION := L
+ PLATFORM_VERSION := 5.0
endif
ifeq "" "$(PLATFORM_SDK_VERSION)"
@@ -59,7 +59,7 @@
ifeq "" "$(PLATFORM_VERSION_CODENAME)"
# This is the current development code-name, if the build is not a final
# release build. If this is a final release build, it is simply "REL".
- PLATFORM_VERSION_CODENAME := L
+ PLATFORM_VERSION_CODENAME := REL
# This is all of the development codenames that are active. Should be either
# the same as PLATFORM_VERSION_CODENAME or a comma-separated list of additional
diff --git a/tools/droiddoc/templates-sdk/class.cs b/tools/droiddoc/templates-sdk/class.cs
index deffa30..8ffe2f9 100644
--- a/tools/droiddoc/templates-sdk/class.cs
+++ b/tools/droiddoc/templates-sdk/class.cs
@@ -124,7 +124,7 @@
<?cs /if ?>
<?cs set:colspan = colspan-1 ?>
<?cs /each ?>
-<?cs call:show_annotations_list(class, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+<?cs call:show_annotations_list(class) ?>
</div><!-- end header -->
@@ -197,7 +197,7 @@
<?cs if:subcount(method.shortDescr) || subcount(method.deprecated) ?>
<div class="jd-descrdiv">
<?cs call:short_descr(method) ?>
- <?cs call:show_annotations_list(method, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(method) ?>
</div>
<?cs /if ?>
</td></tr>
@@ -217,7 +217,7 @@
<td class="jd-linkcol"><?cs call:cond_link(field.name, toroot, field.href, included) ?></td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(field) ?>
- <?cs call:show_annotations_list(field, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(field) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
@@ -232,7 +232,7 @@
<td class="jd-linkcol"><?cs call:cond_link(field.name, toroot, field.href, included) ?></td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(field) ?>
- <?cs call:show_annotations_list(field, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(field) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
@@ -255,7 +255,7 @@
</td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(attr) ?>
- <?cs call:show_annotations_list(attr, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(attr) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
@@ -275,7 +275,7 @@
<td class="jd-linkcol"><?cs call:type_link(cl.type) ?></td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(cl) ?>
- <?cs call:show_annotations_list(cl, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(cl) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
@@ -354,7 +354,7 @@
<td class="jd-linkcol"><?cs call:cond_link(field.name, toroot, field.href, cl.included) ?> </td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(field) ?>
- <?cs call:show_annotations_list(field, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(field) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
@@ -524,7 +524,7 @@
<?cs call:federated_refs(field) ?>
</div>
<div class="jd-details-descr">
- <?cs call:show_annotations_list(field, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(field) ?>
<?cs call:description(field) ?>
<?cs if:subcount(field.constantValue) ?>
<div class="jd-tagdata">
@@ -567,7 +567,7 @@
<?cs call:federated_refs(method) ?>
</div>
<div class="jd-details-descr">
- <?cs call:show_annotations_list(method, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(method) ?>
<?cs call:description(method) ?>
</div>
</div>
@@ -582,7 +582,7 @@
<h4 class="jd-details-title"><?cs var:attr.name ?>
</h4>
<div class="jd-details-descr">
- <?cs call:show_annotations_list(attr, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(attr) ?>
<?cs call:description(attr) ?>
<div class="jd-tagdata">
diff --git a/tools/droiddoc/templates-sdk/classes.cs b/tools/droiddoc/templates-sdk/classes.cs
index 84cca81..4eab438 100644
--- a/tools/droiddoc/templates-sdk/classes.cs
+++ b/tools/droiddoc/templates-sdk/classes.cs
@@ -33,7 +33,7 @@
<td class="jd-linkcol"><?cs call:type_link(cl.type) ?></td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(cl) ?>
- <?cs call:show_annotations_list(cl, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(cl) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
diff --git a/tools/droiddoc/templates-sdk/docpage.cs b/tools/droiddoc/templates-sdk/docpage.cs
index 4d1404b..7d872bc 100644
--- a/tools/droiddoc/templates-sdk/docpage.cs
+++ b/tools/droiddoc/templates-sdk/docpage.cs
@@ -195,8 +195,8 @@
<?cs include:"trailer.cs" ?>
<script src="https://developer.android.com/ytblogger_lists_unified.js" type="text/javascript"></script>
<script src="<?cs var:toroot ?>jd_lists_unified.js?v=2" type="text/javascript"></script>
- <script src="<?cs var:toroot ?>jd_extras.js?v=2" type="text/javascript"></script>
- <script src="<?cs var:toroot ?>jd_collections.js?v=2" type="text/javascript"></script>
+ <script src="<?cs var:toroot ?>jd_extras.js?v=3" type="text/javascript"></script>
+ <script src="<?cs var:toroot ?>jd_collections.js?v=3" type="text/javascript"></script>
<script src="<?cs var:toroot ?>jd_tag_helpers.js?v=2" type="text/javascript"></script>
</body>
diff --git a/tools/droiddoc/templates-sdk/macros_override.cs b/tools/droiddoc/templates-sdk/macros_override.cs
index 6ff8f58..1525be5 100644
--- a/tools/droiddoc/templates-sdk/macros_override.cs
+++ b/tools/droiddoc/templates-sdk/macros_override.cs
@@ -2,17 +2,18 @@
<?cs # pre is an HTML string to start the list, post is an HTML string to close the list ?>
<?cs # for example call:show_annotations_list(cl, "<td>Annotations: ", "</td>") ?>
<?cs # if obj has nothing on obj.showAnnotations, nothing will be output ?>
-<?cs def:show_annotations_list(obj, pre, post) ?>
+<?cs def:show_annotations_list(obj) ?>
<?cs each:anno = obj.showAnnotations ?>
<?cs if:first(anno) ?>
- <?cs var:pre ?>
+ <span class='annotation-message'>
+ Included in documention by the annotations:
<?cs /if ?>
@<?cs var:anno.type.label ?>
<?cs if:last(anno) == 0 ?>
,
<?cs /if ?>
<?cs if:last(anno)?>
- <?cs var:post ?>
+ </span>
<?cs /if ?>
<?cs /each ?>
<?cs /def ?>
@@ -26,7 +27,7 @@
<td class="jd-linkcol"><?cs call:type_link(cl.type) ?></td>
<td class="jd-descrcol" width="100%">
<?cs call:short_descr(cl) ?>
- <?cs call:show_annotations_list(cl, "<span class='annotation-message'>Included in documentation by the annotations: ", "</span>") ?>
+ <?cs call:show_annotations_list(cl) ?>
</td>
</tr>
<?cs set:count = count + #1 ?>
diff --git a/tools/releasetools/blockimgdiff.py b/tools/releasetools/blockimgdiff.py
index 216486c..8b179d5 100644
--- a/tools/releasetools/blockimgdiff.py
+++ b/tools/releasetools/blockimgdiff.py
@@ -16,6 +16,7 @@
from collections import deque, OrderedDict
from hashlib import sha1
+import heapq
import itertools
import multiprocessing
import os
@@ -142,9 +143,16 @@
self.goes_before = {}
self.goes_after = {}
+ self.stash_before = []
+ self.use_stash = []
+
self.id = len(by_id)
by_id.append(self)
+ def NetStashChange(self):
+ return (sum(sr.size() for (_, sr) in self.stash_before) -
+ sum(sr.size() for (_, sr) in self.use_stash))
+
def __str__(self):
return (str(self.id) + ": <" + str(self.src_ranges) + " " + self.style +
" to " + str(self.tgt_ranges) + ">")
@@ -182,11 +190,14 @@
# original image.
class BlockImageDiff(object):
- def __init__(self, tgt, src=None, threads=None):
+ def __init__(self, tgt, src=None, threads=None, version=2):
if threads is None:
threads = multiprocessing.cpu_count() // 2
if threads == 0: threads = 1
self.threads = threads
+ self.version = version
+
+ assert version in (1, 2)
self.tgt = tgt
if src is None:
@@ -221,7 +232,12 @@
self.FindVertexSequence()
# Fix up the ordering dependencies that the sequence didn't
# satisfy.
- self.RemoveBackwardEdges()
+ if self.version == 1:
+ self.RemoveBackwardEdges()
+ else:
+ self.ReverseBackwardEdges()
+ self.ImproveVertexSequence()
+
# Double-check our work.
self.AssertSequenceGood()
@@ -231,18 +247,87 @@
def WriteTransfers(self, prefix):
out = []
- out.append("1\n") # format version number
total = 0
performs_read = False
+ stashes = {}
+ stashed_blocks = 0
+ max_stashed_blocks = 0
+
+ free_stash_ids = []
+ next_stash_id = 0
+
for xf in self.transfers:
- # zero [rangeset]
- # new [rangeset]
- # bsdiff patchstart patchlen [src rangeset] [tgt rangeset]
- # imgdiff patchstart patchlen [src rangeset] [tgt rangeset]
- # move [src rangeset] [tgt rangeset]
- # erase [rangeset]
+ if self.version < 2:
+ assert not xf.stash_before
+ assert not xf.use_stash
+
+ for s, sr in xf.stash_before:
+ assert s not in stashes
+ if free_stash_ids:
+ sid = heapq.heappop(free_stash_ids)
+ else:
+ sid = next_stash_id
+ next_stash_id += 1
+ stashes[s] = sid
+ stashed_blocks += sr.size()
+ out.append("stash %d %s\n" % (sid, sr.to_string_raw()))
+
+ if stashed_blocks > max_stashed_blocks:
+ max_stashed_blocks = stashed_blocks
+
+ if self.version == 1:
+ src_string = xf.src_ranges.to_string_raw()
+ elif self.version == 2:
+
+ # <# blocks> <src ranges>
+ # OR
+ # <# blocks> <src ranges> <src locs> <stash refs...>
+ # OR
+ # <# blocks> - <stash refs...>
+
+ size = xf.src_ranges.size()
+ src_string = [str(size)]
+
+ unstashed_src_ranges = xf.src_ranges
+ mapped_stashes = []
+ for s, sr in xf.use_stash:
+ sid = stashes.pop(s)
+ stashed_blocks -= sr.size()
+ unstashed_src_ranges = unstashed_src_ranges.subtract(sr)
+ sr = xf.src_ranges.map_within(sr)
+ mapped_stashes.append(sr)
+ src_string.append("%d:%s" % (sid, sr.to_string_raw()))
+ heapq.heappush(free_stash_ids, sid)
+
+ if unstashed_src_ranges:
+ src_string.insert(1, unstashed_src_ranges.to_string_raw())
+ if xf.use_stash:
+ mapped_unstashed = xf.src_ranges.map_within(unstashed_src_ranges)
+ src_string.insert(2, mapped_unstashed.to_string_raw())
+ mapped_stashes.append(mapped_unstashed)
+ self.AssertPartition(RangeSet(data=(0, size)), mapped_stashes)
+ else:
+ src_string.insert(1, "-")
+ self.AssertPartition(RangeSet(data=(0, size)), mapped_stashes)
+
+ src_string = " ".join(src_string)
+
+ # both versions:
+ # zero <rangeset>
+ # new <rangeset>
+ # erase <rangeset>
+ #
+ # version 1:
+ # bsdiff patchstart patchlen <src rangeset> <tgt rangeset>
+ # imgdiff patchstart patchlen <src rangeset> <tgt rangeset>
+ # move <src rangeset> <tgt rangeset>
+ #
+ # version 2:
+ # bsdiff patchstart patchlen <tgt rangeset> <src_string>
+ # imgdiff patchstart patchlen <tgt rangeset> <src_string>
+ # move <tgt rangeset> <src_string>
tgt_size = xf.tgt_ranges.size()
@@ -255,17 +340,27 @@
assert xf.tgt_ranges
assert xf.src_ranges.size() == tgt_size
if xf.src_ranges != xf.tgt_ranges:
- out.append("%s %s %s\n" % (
- xf.style,
- xf.src_ranges.to_string_raw(), xf.tgt_ranges.to_string_raw()))
+ if self.version == 1:
+ out.append("%s %s %s\n" % (
+ xf.style,
+ xf.src_ranges.to_string_raw(), xf.tgt_ranges.to_string_raw()))
+ elif self.version == 2:
+ out.append("%s %s %s\n" % (
+ xf.style,
+ xf.tgt_ranges.to_string_raw(), src_string))
total += tgt_size
elif xf.style in ("bsdiff", "imgdiff"):
performs_read = True
assert xf.tgt_ranges
assert xf.src_ranges
- out.append("%s %d %d %s %s\n" % (
- xf.style, xf.patch_start, xf.patch_len,
- xf.src_ranges.to_string_raw(), xf.tgt_ranges.to_string_raw()))
+ if self.version == 1:
+ out.append("%s %d %d %s %s\n" % (
+ xf.style, xf.patch_start, xf.patch_len,
+ xf.src_ranges.to_string_raw(), xf.tgt_ranges.to_string_raw()))
+ elif self.version == 2:
+ out.append("%s %d %d %s %s\n" % (
+ xf.style, xf.patch_start, xf.patch_len,
+ xf.tgt_ranges.to_string_raw(), src_string))
total += tgt_size
elif xf.style == "zero":
assert xf.tgt_ranges
@@ -276,7 +371,10 @@
else:
raise ValueError, "unknown transfer style '%s'\n" % (xf.style,)
- out.insert(1, str(total) + "\n")
+
+ # sanity check: abort if we're going to need more than 512 MB if
+ # stash space
+ assert max_stashed_blocks * self.tgt.blocksize < (512 << 20)
all_tgt = RangeSet(data=(0, self.tgt.total_blocks))
if performs_read:
@@ -289,12 +387,24 @@
else:
# if nothing is read (ie, this is a full OTA), then we can start
# by erasing the entire partition.
- out.insert(2, "erase %s\n" % (all_tgt.to_string_raw(),))
+ out.insert(0, "erase %s\n" % (all_tgt.to_string_raw(),))
+
+ out.insert(0, "%d\n" % (self.version,)) # format version number
+ out.insert(1, str(total) + "\n")
+ if self.version >= 2:
+ # version 2 only: after the total block count, we give the number
+ # of stash slots needed, and the maximum size needed (in blocks)
+ out.insert(2, str(next_stash_id) + "\n")
+ out.insert(3, str(max_stashed_blocks) + "\n")
with open(prefix + ".transfer.list", "wb") as f:
for i in out:
f.write(i)
+ if self.version >= 2:
+ print("max stashed blocks: %d (%d bytes)\n" % (
+ max_stashed_blocks, max_stashed_blocks * self.tgt.blocksize))
+
def ComputePatches(self, prefix):
print("Reticulating splines...")
diff_q = []
@@ -409,7 +519,13 @@
# Imagine processing the transfers in order.
for xf in self.transfers:
# Check that the input blocks for this transfer haven't yet been touched.
- assert not touched.overlaps(xf.src_ranges)
+
+ x = xf.src_ranges
+ if self.version >= 2:
+ for _, sr in xf.use_stash:
+ x = x.subtract(sr)
+
+ assert not touched.overlaps(x)
# Check that the output blocks for this transfer haven't yet been touched.
assert not touched.overlaps(xf.tgt_ranges)
# Touch all the blocks written by this transfer.
@@ -418,6 +534,47 @@
# Check that we've written every target block.
assert touched == self.tgt.care_map
+ def ImproveVertexSequence(self):
+ print("Improving vertex order...")
+
+ # At this point our digraph is acyclic; we reversed any edges that
+ # were backwards in the heuristically-generated sequence. The
+ # previously-generated order is still acceptable, but we hope to
+ # find a better order that needs less memory for stashed data.
+ # Now we do a topological sort to generate a new vertex order,
+ # using a greedy algorithm to choose which vertex goes next
+ # whenever we have a choice.
+
+ # Make a copy of the edge set; this copy will get destroyed by the
+ # algorithm.
+ for xf in self.transfers:
+ xf.incoming = xf.goes_after.copy()
+ xf.outgoing = xf.goes_before.copy()
+
+ L = [] # the new vertex order
+
+ # S is the set of sources in the remaining graph; we always choose
+ # the one that leaves the least amount of stashed data after it's
+ # executed.
+ S = [(u.NetStashChange(), u.order, u) for u in self.transfers
+ if not u.incoming]
+ heapq.heapify(S)
+
+ while S:
+ _, _, xf = heapq.heappop(S)
+ L.append(xf)
+ for u in xf.outgoing:
+ del u.incoming[xf]
+ if not u.incoming:
+ heapq.heappush(S, (u.NetStashChange(), u.order, u))
+
+ # if this fails then our graph had a cycle.
+ assert len(L) == len(self.transfers)
+
+ self.transfers = L
+ for i, xf in enumerate(L):
+ xf.order = i
+
def RemoveBackwardEdges(self):
print("Removing backward edges...")
in_order = 0
@@ -425,19 +582,17 @@
lost_source = 0
for xf in self.transfers:
- io = 0
- ooo = 0
lost = 0
size = xf.src_ranges.size()
for u in xf.goes_before:
# xf should go before u
if xf.order < u.order:
# it does, hurray!
- io += 1
+ in_order += 1
else:
# it doesn't, boo. trim the blocks that u writes from xf's
# source, so that xf can go after u.
- ooo += 1
+ out_of_order += 1
assert xf.src_ranges.overlaps(u.tgt_ranges)
xf.src_ranges = xf.src_ranges.subtract(u.tgt_ranges)
xf.intact = False
@@ -448,8 +603,6 @@
lost = size - xf.src_ranges.size()
lost_source += lost
- in_order += io
- out_of_order += ooo
print((" %d/%d dependencies (%.2f%%) were violated; "
"%d source blocks removed.") %
@@ -458,6 +611,48 @@
if (in_order + out_of_order) else 0.0,
lost_source))
+ def ReverseBackwardEdges(self):
+ print("Reversing backward edges...")
+ in_order = 0
+ out_of_order = 0
+ stashes = 0
+ stash_size = 0
+
+ for xf in self.transfers:
+ lost = 0
+ size = xf.src_ranges.size()
+ for u in xf.goes_before.copy():
+ # xf should go before u
+ if xf.order < u.order:
+ # it does, hurray!
+ in_order += 1
+ else:
+ # it doesn't, boo. modify u to stash the blocks that it
+ # writes that xf wants to read, and then require u to go
+ # before xf.
+ out_of_order += 1
+
+ overlap = xf.src_ranges.intersect(u.tgt_ranges)
+ assert overlap
+
+ u.stash_before.append((stashes, overlap))
+ xf.use_stash.append((stashes, overlap))
+ stashes += 1
+ stash_size += overlap.size()
+
+ # reverse the edge direction; now xf must go after u
+ del xf.goes_before[u]
+ del u.goes_after[xf]
+ xf.goes_after[u] = None # value doesn't matter
+ u.goes_before[xf] = None
+
+ print((" %d/%d dependencies (%.2f%%) were violated; "
+ "%d source blocks stashed.") %
+ (out_of_order, in_order + out_of_order,
+ (out_of_order * 100.0 / (in_order + out_of_order))
+ if (in_order + out_of_order) else 0.0,
+ stash_size))
+
def FindVertexSequence(self):
print("Finding vertex sequence...")
diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 815c76c..96075a9 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -1030,7 +1030,14 @@
self.partition = partition
self.check_first_block = check_first_block
- b = blockimgdiff.BlockImageDiff(tgt, src, threads=OPTIONS.worker_threads)
+ version = 1
+ if OPTIONS.info_dict:
+ version = max(
+ int(i) for i in
+ OPTIONS.info_dict.get("blockimgdiff_versions", "1").split(","))
+
+ b = blockimgdiff.BlockImageDiff(tgt, src, threads=OPTIONS.worker_threads,
+ version=version)
tmpdir = tempfile.mkdtemp()
OPTIONS.tempfiles.append(tmpdir)
self.path = os.path.join(tmpdir, partition)
diff --git a/tools/releasetools/rangelib.py b/tools/releasetools/rangelib.py
index 8a85d2d..7279c60 100644
--- a/tools/releasetools/rangelib.py
+++ b/tools/releasetools/rangelib.py
@@ -24,7 +24,9 @@
lots of runs."""
def __init__(self, data=None):
- if data:
+ if isinstance(data, str):
+ self._parse_internal(data)
+ elif data:
self.data = tuple(self._remove_pairs(data))
else:
self.data = ()
@@ -46,6 +48,9 @@
else:
return self.to_string()
+ def __repr__(self):
+ return '<RangeSet("' + self.to_string() + '")>'
+
@classmethod
def parse(cls, text):
"""Parse a text string consisting of a space-separated list of
@@ -59,7 +64,9 @@
"15-20 30 10-14" is not, even though they represent the same set
of blocks (and the two RangeSets will compare equal with ==).
"""
+ return cls(text)
+ def _parse_internal(self, text):
data = []
last = -1
monotonic = True
@@ -81,9 +88,8 @@
else:
monotonic = True
data.sort()
- r = RangeSet(cls._remove_pairs(data))
- r.monotonic = monotonic
- return r
+ self.data = tuple(self._remove_pairs(data))
+ self.monotonic = monotonic
@staticmethod
def _remove_pairs(source):
@@ -113,7 +119,13 @@
def union(self, other):
"""Return a new RangeSet representing the union of this RangeSet
- with the argument."""
+ with the argument.
+
+ >>> RangeSet("10-19 30-34").union(RangeSet("18-29"))
+ <RangeSet("10-34")>
+ >>> RangeSet("10-19 30-34").union(RangeSet("22 32"))
+ <RangeSet("10-19 22 30-34")>
+ """
out = []
z = 0
for p, d in heapq.merge(zip(self.data, itertools.cycle((+1, -1))),
@@ -125,7 +137,13 @@
def intersect(self, other):
"""Return a new RangeSet representing the intersection of this
- RangeSet with the argument."""
+ RangeSet with the argument.
+
+ >>> RangeSet("10-19 30-34").intersect(RangeSet("18-32"))
+ <RangeSet("18-19 30-32")>
+ >>> RangeSet("10-19 30-34").intersect(RangeSet("22-28"))
+ <RangeSet("")>
+ """
out = []
z = 0
for p, d in heapq.merge(zip(self.data, itertools.cycle((+1, -1))),
@@ -137,7 +155,13 @@
def subtract(self, other):
"""Return a new RangeSet representing subtracting the argument
- from this RangeSet."""
+ from this RangeSet.
+
+ >>> RangeSet("10-19 30-34").subtract(RangeSet("18-32"))
+ <RangeSet("10-17 33-34")>
+ >>> RangeSet("10-19 30-34").subtract(RangeSet("22-28"))
+ <RangeSet("10-19 30-34")>
+ """
out = []
z = 0
@@ -150,7 +174,13 @@
def overlaps(self, other):
"""Returns true if the argument has a nonempty overlap with this
- RangeSet."""
+ RangeSet.
+
+ >>> RangeSet("10-19 30-34").overlaps(RangeSet("18-32"))
+ True
+ >>> RangeSet("10-19 30-34").overlaps(RangeSet("22-28"))
+ False
+ """
# This is like intersect, but we can stop as soon as we discover the
# output is going to be nonempty.
@@ -164,7 +194,11 @@
def size(self):
"""Returns the total size of the RangeSet (ie, how many integers
- are in the set)."""
+ are in the set).
+
+ >>> RangeSet("10-19 30-34").size()
+ 15
+ """
total = 0
for i, p in enumerate(self.data):
@@ -173,3 +207,37 @@
else:
total -= p
return total
+
+ def map_within(self, other):
+ """'other' should be a subset of 'self'. Returns a RangeSet
+ representing what 'other' would get translated to if the integers
+ of 'self' were translated down to be contiguous starting at zero.
+
+ >>> RangeSet("0-9").map_within(RangeSet("3-4"))
+ <RangeSet("3-4")>
+ >>> RangeSet("10-19").map_within(RangeSet("13-14"))
+ <RangeSet("3-4")>
+ >>> RangeSet("10-19 30-39").map_within(RangeSet("17-19 30-32"))
+ <RangeSet("7-12")>
+ >>> RangeSet("10-19 30-39").map_within(RangeSet("12-13 17-19 30-32"))
+ <RangeSet("2-3 7-12")>
+ """
+
+ out = []
+ offset = 0
+ start = None
+ for p, d in heapq.merge(zip(self.data, itertools.cycle((-5, +5))),
+ zip(other.data, itertools.cycle((-1, +1)))):
+ if d == -5:
+ start = p
+ elif d == +5:
+ offset += p-start
+ start = None
+ else:
+ out.append(offset + p - start)
+ return RangeSet(data=out)
+
+
+if __name__ == "__main__":
+ import doctest
+ doctest.testmod()
