releasetools: Make BBOTA incremental generation repeatable.
set() doesn't keep elements according to the order of insertion. So
Transfers managed with set() in intermediate steps may not appear in the
same order across runs. This leads to slightly different output packages
when generating the same incremental OTA.
This CL fixes the issue by replacing set() with OrderedDict() in
blockimgdiff.GenerateDigraph() and blockimgdiff.FindVertexSequence().
It also adds a testcase that ensures blockimgdiff.GenerateDigraph()
preserves the insertion order for Transfer.goes_after set.
Bug: 32220816
Test: ota_from_target_files.py gives identical package when running
multiple times.
Change-Id: I56d551e5ca926993ab46896e33c80e0ce42e506a
diff --git a/tools/releasetools/blockimgdiff.py b/tools/releasetools/blockimgdiff.py
index 70bb4eb..662b4ec 100644
--- a/tools/releasetools/blockimgdiff.py
+++ b/tools/releasetools/blockimgdiff.py
@@ -999,8 +999,11 @@
heap.append(xf.heap_item)
heapq.heapify(heap)
- sinks = set(u for u in G if not u.outgoing)
- sources = set(u for u in G if not u.incoming)
+ # Use OrderedDict() instead of set() to preserve the insertion order. Need
+ # to use 'sinks[key] = None' to add key into the set. sinks will look like
+ # { key1: None, key2: None, ... }.
+ sinks = OrderedDict.fromkeys(u for u in G if not u.outgoing)
+ sources = OrderedDict.fromkeys(u for u in G if not u.incoming)
def adjust_score(iu, delta):
iu.score += delta
@@ -1011,26 +1014,28 @@
while G:
# Put all sinks at the end of the sequence.
while sinks:
- new_sinks = set()
+ new_sinks = OrderedDict()
for u in sinks:
if u not in G: continue
s2.appendleft(u)
del G[u]
for iu in u.incoming:
adjust_score(iu, -iu.outgoing.pop(u))
- if not iu.outgoing: new_sinks.add(iu)
+ if not iu.outgoing:
+ new_sinks[iu] = None
sinks = new_sinks
# Put all the sources at the beginning of the sequence.
while sources:
- new_sources = set()
+ new_sources = OrderedDict()
for u in sources:
if u not in G: continue
s1.append(u)
del G[u]
for iu in u.outgoing:
adjust_score(iu, +iu.incoming.pop(u))
- if not iu.incoming: new_sources.add(iu)
+ if not iu.incoming:
+ new_sources[iu] = None
sources = new_sources
if not G: break
@@ -1049,11 +1054,13 @@
del G[u]
for iu in u.outgoing:
adjust_score(iu, +iu.incoming.pop(u))
- if not iu.incoming: sources.add(iu)
+ if not iu.incoming:
+ sources[iu] = None
for iu in u.incoming:
adjust_score(iu, -iu.outgoing.pop(u))
- if not iu.outgoing: sinks.add(iu)
+ if not iu.outgoing:
+ sinks[iu] = None
# Now record the sequence in the 'order' field of each transfer,
# and by rearranging self.transfers to be in the chosen sequence.
@@ -1072,8 +1079,7 @@
# Each item of source_ranges will be:
# - None, if that block is not used as a source,
- # - a transfer, if one transfer uses it as a source, or
- # - a set of transfers.
+ # - an ordered set of transfers.
source_ranges = []
for b in self.transfers:
for s, e in b.src_ranges:
@@ -1081,23 +1087,19 @@
source_ranges.extend([None] * (e-len(source_ranges)))
for i in range(s, e):
if source_ranges[i] is None:
- source_ranges[i] = b
+ source_ranges[i] = OrderedDict.fromkeys([b])
else:
- if not isinstance(source_ranges[i], set):
- source_ranges[i] = set([source_ranges[i]])
- source_ranges[i].add(b)
+ source_ranges[i][b] = None
for a in self.transfers:
- intersections = set()
+ intersections = OrderedDict()
for s, e in a.tgt_ranges:
for i in range(s, e):
if i >= len(source_ranges): break
- b = source_ranges[i]
- if b is not None:
- if isinstance(b, set):
- intersections.update(b)
- else:
- intersections.add(b)
+ # Add all the Transfers in source_ranges[i] to the (ordered) set.
+ if source_ranges[i] is not None:
+ for j in source_ranges[i]:
+ intersections[j] = None
for b in intersections:
if a is b: continue