Android nougat ota tool

'''
Usage:  ota_from_target_files [flags] input_target_files output_ota_package

  -k (--package_key) <key>
      指定一个ota包签名的key，否则采用默认的key，来自source-target。

  -i  (--incremental_from)  <file>
      指明从哪里制作差分包

  --full_radio
      包含完整的img，

  --full_bootloader
      差分包时包含完整的bootloader镜像

  -v  (--verify)
      差分包时校验镜像内文件

  -o  (--oem_settings)  <file>
      使用文件指定OEM分区内的OEM properties

  --oem_no_mount
      如果有 -o 选项，则表示OEM properties file没有具体存放的分区

  -w  (--wipe_user_data)
      指定OTA包能清空用户数据

  -n  (--no_prereq)
      忽略升级况timestamp校验，这个校验语句在update script开始的地方。一般用于开发模式，
      开发者期望回退版本。

  --downgrade
      故意制作一个差分包，从一个新版本降到一个旧版本（是通过timestamp判断的）。在metadata file中，
      "ota-downgrade=yes" "ota-wipe=yes"，并默认使用source target中的update-binary，除非 --binary被指定。

  -e  (--extra_script)  <file>
      在update script的尾部追加<file>中的内容

  -a  (--aslr_mode)  <on|off>
      Specify whether to turn on ASLR for the package (on by default).
      空间格局随机化

  -2  (--two_step)
      两个步骤升级：先升级recovery，然后重启，使用新的recovery升级系统。

  --block
      制作block包

  -b  (--binary)  <file>
      指定 update-binary，只用于开发模式。

  -t  (--worker_threads) <int>
      otatools的工作线程，(defaults to 3).

  --stash_threshold <float>
      指定内存使用阈值（threshold）

  --gen_verify
      生成的OTA包会对分区进行校验，具体是哪些分区？

  --log_diff <file>
      当指定选项 -i 时，获得source zip与target zip的差分信息。
'''

WriteABOTAPackageWithBrilloScript(
        target_file=args[0],
        output_file=args[1],
        source_file=OPTIONS.incremental_source) //如果不是差分升级，这个是空

if block_based:
  # Full OTA is done as an "incremental" against an empty source
  # image.  This has the effect of writing new data from the package
  # to the entire partition, but lets us reuse the updater code that
  # writes incrementals to do it.
  system_tgt = GetImage("system", OPTIONS.input_tmp, OPTIONS.info_dict)
  system_tgt.ResetFileMap()
  system_diff = common.BlockDifference("system", system_tgt, src=None)
  system_diff.WriteScript(script, output_zip)

def GetImage(which, tmpdir, info_dict):
  # Return an image object (suitable for passing to BlockImageDiff)
  # for the 'which' partition (most be "system" or "vendor").  If a
  # prebuilt image and file map are found in tmpdir they are used,
  # otherwise they are reconstructed from the individual files.

  # 这个解释很明了，返回一个image object给BlockImageDiff用的，一般是system/vendor两个分区，
  # 在input_zip解压后的temp文件夹中应该包含对应的image和file map两个文件，
  # 否则，脚本会尝试从分离的大量文件中重新制作对应的image和file map文件。

  assert which in ("system", "vendor")

  path = os.path.join(tmpdir, "IMAGES", which + ".img")
  mappath = os.path.join(tmpdir, "IMAGES", which + ".map")
  if os.path.exists(path) and os.path.exists(mappath):
    print "using %s.img from target-files" % (which,)
    # This is a 'new' target-files, which already has the image in it.

  else:
    print "building %s.img from target-files" % (which,)

    # This is an 'old' target-files, which does not contain images
    # already built.  Build them.

    mappath = tempfile.mkstemp()[1]
    OPTIONS.tempfiles.append(mappath)

    import add_img_to_target_files
    if which == "system":
    #我们应当关注一下这里的制作方式，简单的，在make_ext4fs加上-B file.map参数可以获得对应的file map信息
      path = add_img_to_target_files.BuildSystem(
          tmpdir, info_dict, block_list=mappath)
    elif which == "vendor":
      path = add_img_to_target_files.BuildVendor(
          tmpdir, info_dict, block_list=mappath)

  # Bug: http://b/20939131
  # In ext4 filesystems, block 0 might be changed even being mounted
  # R/O. We add it to clobbered_blocks so that it will be written to the
  # target unconditionally. Note that they are still part of care_map.
  clobbered_blocks = "0"
  # 我理解的意思是，ext4文件系统镜像，mount的时候，第一个block总是被修改，所以我们不使用这个block，仅仅当作一个占位空间。
  # 脚本的做法是，对clobbered_blocks指定的block，总是写到target中。见下一节的说明

  return sparse_img.SparseImage(path, mappath, clobbered_blocks)

"""Wraps a sparse image file into an image object.

  Wraps a sparse image file (and optional file map and clobbered_blocks) into
  an image object suitable for passing to BlockImageDiff. file_map contains
  the mapping between files and their blocks. clobbered_blocks contains the set
  of blocks that should be always written to the target regardless of the old
  contents (i.e. copying instead of patching). clobbered_blocks should be in
  the form of a string like "0" or "0 1-5 8".
  """

  def __init__(self, simg_fn, file_map_fn=None, clobbered_blocks=None,
               mode="rb", build_map=True):
    self.simg_f = f = open(simg_fn, mode)

    header_bin = f.read(28)
    header = struct.unpack("<I4H4I", header_bin)
    # 这里是把buffer数据格式化，"<I4H4I"就是格式方式，得到的数据放入一个List中。
    # < : 小端序
    # I ： 1个int 1*4 = 4
    # 4H ： 4个unsigned short 4*2 = 8
    # 4I ： 4个int 1*4 = 4
    # 9个数据，共28个bit。

    # 1个int
    magic = header[0]
    # 4个unsigned short
    major_version = header[1]
    minor_version = header[2]
    file_hdr_sz = header[3]    
    chunk_hdr_sz = header[4]
    # 4个int
    self.blocksize = blk_sz = header[5]
    self.total_blocks = total_blks = header[6]
    self.total_chunks = total_chunks = header[7]
    # 4个中的最后一个int没有使用，预留的。

    if magic != 0xED26FF3A:
      raise ValueError("Magic should be 0xED26FF3A but is 0x%08X" % (magic,))
    if major_version != 1 or minor_version != 0:
      raise ValueError("I know about version 1.0, but this is version %u.%u" %
                       (major_version, minor_version))
    if file_hdr_sz != 28:
      raise ValueError("File header size was expected to be 28, but is %u." %
                       (file_hdr_sz,))
    if chunk_hdr_sz != 12:
      raise ValueError("Chunk header size was expected to be 12, but is %u." %
                       (chunk_hdr_sz,))

    print("Total of %u %u-byte output blocks in %u input chunks."
          % (total_blks, blk_sz, total_chunks))

    if not build_map:
      return

    pos = 0   # in blocks，对于整个system.img而言，pos表示第几个block，从0开始
    care_data = [] # 关心的list
    self.offset_map = offset_map = []
    self.clobbered_blocks = rangelib.RangeSet(data=clobbered_blocks)

    for i in range(total_chunks): #遍历所有的chunk
      header_bin = f.read(12)
      header = struct.unpack("<2H2I", header_bin)
      chunk_type = header[0]
      chunk_sz = header[2] # 表示data中包含block的个数
      total_sz = header[3] #整个chunk的大小
      data_sz = total_sz - 12 #chunk中data区大小

      if chunk_type == 0xCAC1:
        if data_sz != (chunk_sz * blk_sz):
          raise ValueError(
              "Raw chunk input size (%u) does not match output size (%u)" %
              (data_sz, chunk_sz * blk_sz))
        else:
          # 记录一个pos的范围
          care_data.append(pos)
          care_data.append(pos + chunk_sz)
          # 把一个元组加入list中，元组信息(block的位置, block的个数, 文件偏移量, 空)
          offset_map.append((pos, chunk_sz, f.tell(), None))
          pos += chunk_sz # pos位置往后移动
          f.seek(data_sz, os.SEEK_CUR) # 改变文件偏移量，移到下一个chunk

      elif chunk_type == 0xCAC2:
        fill_data = f.read(4)
        care_data.append(pos)
        care_data.append(pos + chunk_sz)
        offset_map.append((pos, chunk_sz, None, fill_data))
        pos += chunk_sz
        #从上面的意思可见：在第pos个block开始的chunk_sz个block填充f.read(4)的内容
        #f通过read函数自动往后移动4个字节

      elif chunk_type == 0xCAC3:
        if data_sz != 0:
          raise ValueError("Don't care chunk input size is non-zero (%u)" %
                           (data_sz))
        else:
          pos += chunk_sz #只是一个简单的chunk头，略过。

      elif chunk_type == 0xCAC4:
        raise ValueError("CRC32 chunks are not supported")

      else:
        raise ValueError("Unknown chunk type 0x%04X not supported" %
                         (chunk_type,))

    #到此，得到两个信息：1. 保存了block范围的care_data； 2.保存了大量元组信息的offset_map。

    #这个功能是明确的，把多个连续的子空间变成一个大空间： 1-2 2-4 4-10 = 1-10
    self.care_map = rangelib.RangeSet(care_data)
    #取出所有的pos，放到一个list中。
    self.offset_index = [i[0] for i in offset_map]

    # Bug: 20881595
    # Introduce extended blocks as a workaround for the bug. dm-verity may
    # touch blocks that are not in the care_map due to block device
    # read-ahead. It will fail if such blocks contain non-zeroes. We zero out
    # the extended blocks explicitly to avoid dm-verity failures. 512 blocks
    # are the maximum read-ahead we configure for dm-verity block devices.
    extended = self.care_map.extend(512) #子空间前后扩展512 blocks
    all_blocks = rangelib.RangeSet(data=(0, self.total_blocks)) # 获得有效范围
    extended = extended.intersect(all_blocks).subtract(self.care_map) # && ||，得到具体需要拓展的blocks
    self.extended = extended
    #上面的代码考虑了一个bug，对于支持dm-verity的设备，在校验system.img的时候，有512个block的预读数据，我们需要将其置0.

    if file_map_fn:
      #如果我们前面给了一个.map文件
      #这样，就区分空和非空block，分别标志为__ZERO和__NONZERO，并把clobbered_blocks标志为__COPY
      self.LoadFileBlockMap(file_map_fn, self.clobbered_blocks)
    else:
      #如果没有，如果我们不做差分包，.map文件不是必须的，后面会看到ResetFileMap函数，否认了LoadFileBlockMap的工作。
      #这样，就把关心的数据标志为"__DATA"
      self.file_map = {"__DATA": self.care_map}

class RangeSet(object):
  """A RangeSet represents a set of nonoverlapping ranges on the
  integers (ie, a set of integers, but efficient when the set contains
  lots of runs."""
  # 代表一个不重叠的数据集合，也就是去重。

  def __init__(self, data=None):
    self.monotonic = False
    if isinstance(data, str): # str的去重
      self._parse_internal(data)
    elif data:
      assert len(data) % 2 == 0
      self.data = tuple(self._remove_pairs(data)) #元组的去重，多个连续的空间拼成一个大空间。yield
      #检查data递增性
      self.monotonic = all(x < y for x, y in zip(self.data, self.data[1:]))
    else:
      self.data = ()

def LoadFileBlockMap(self, fn, clobbered_blocks):
  remaining = self.care_map
  self.file_map = out = {}

  with open(fn) as f:
    for line in f:
      fn, ranges = line.split(None, 1) #得到文件path和它的block范围
      ranges = rangelib.RangeSet.parse(ranges) #返回一个RangeSet对象，包含整理过的block范围信息
      out[fn] = ranges #把两者保存到字典 file_map
      assert ranges.size() == ranges.intersect(remaining).size() #校验空间是否存在care_map中

      # Currently we assume that blocks in clobbered_blocks are not part of
      # any file.
      assert not clobbered_blocks.overlaps(ranges)
      remaining = remaining.subtract(ranges) #计算剩下的空间

  remaining = remaining.subtract(clobbered_blocks) #先把必须填充的空间去掉

  # For all the remaining blocks in the care_map (ie, those that
  # aren't part of the data for any file nor part of the clobbered_blocks),
  # divide them into blocks that are all zero and blocks that aren't.
  # (Zero blocks are handled specially because (1) there are usually
  # a lot of them and (2) bsdiff handles files with long sequences of
  # repeated bytes especially poorly.)
  # 剩下的空间是不包含任何文件的，也不是必须填充的空间。
  # 我们把它们分离成空和非空，空的空间是特殊的，因为：1.它们很多；2.bsdiff在处理文件的时候，会包含很多重复的字节，即使这样做很傻。

  zero_blocks = []
  nonzero_blocks = []
  reference = '\0' * self.blocksize  # 创建blocksize个'\0'，保存成字符串

  # Workaround for bug 23227672. For squashfs, we don't have a system.map. So
  # the whole system image will be treated as a single file. But for some
  # unknown bug, the updater will be killed due to OOM when writing back the
  # patched image to flash (observed on lenok-userdebug MEA49). Prior to
  # getting a real fix, we evenly divide the non-zero blocks into smaller
  # groups (currently 1024 blocks or 4MB per group).
  # Bug: 23227672
  MAX_BLOCKS_PER_GROUP = 1024
  nonzero_groups = []

  f = self.simg_f
  for s, e in remaining: # 遍历block区间，得到开始和结尾
    for b in range(s, e): # 对于每一个block
      idx = bisect.bisect_right(self.offset_index, b) - 1 # 是第一个block？
      chunk_start, _, filepos, fill_data = self.offset_map[idx] # 取出block字典信息
      if filepos is not None: #有数据的
        filepos += (b-chunk_start) * self.blocksize #文件偏移量后移
        f.seek(filepos, os.SEEK_SET) #文件指针后移
        data = f.read(self.blocksize) #读取文件数据(从system.img中)，为什么要读取数据，后面你又不用？？？
      else: #没有数据，或者是填充数据
        if fill_data == reference[:4]:   # fill with all zeros，如果填充数据是'\0'
          data = reference
        else:
          data = None #不理会填充数据是什么

      if data == reference:
        zero_blocks.append(b)
        zero_blocks.append(b+1)
      else:
        nonzero_blocks.append(b)
        nonzero_blocks.append(b+1)

        if len(nonzero_blocks) >= MAX_BLOCKS_PER_GROUP:
          nonzero_groups.append(nonzero_blocks)
          # Clear the list.
          nonzero_blocks = []

  if nonzero_blocks:
    nonzero_groups.append(nonzero_blocks)
    nonzero_blocks = []

  assert zero_blocks or nonzero_groups or clobbered_blocks

  if zero_blocks:
    out["__ZERO"] = rangelib.RangeSet(data=zero_blocks)
  if nonzero_groups:
    for i, blocks in enumerate(nonzero_groups):
      out["__NONZERO-%d" % i] = rangelib.RangeSet(data=blocks)
  if clobbered_blocks:
    out["__COPY"] = clobbered_blocks

class BlockDifference(object):
  def __init__(self, partition, tgt, src=None, check_first_block=False,
               version=None, disable_imgdiff=False):
    self.tgt = tgt
    self.src = src
    self.partition = partition
    self.check_first_block = check_first_block
    self.disable_imgdiff = disable_imgdiff

    if version is None:
      version = 1
      if OPTIONS.info_dict:
        version = max(
            int(i) for i in
            OPTIONS.info_dict.get("blockimgdiff_versions", "1").split(","))
    self.version = version

    # 获得一个BlockImageDiff对象，记住这里传入的参数，后面的Compute函数需要用到
    b = blockimgdiff.BlockImageDiff(tgt, src, threads=OPTIONS.worker_threads,
                                    version=self.version,
                                    disable_imgdiff=self.disable_imgdiff)
    tmpdir = tempfile.mkdtemp()
    OPTIONS.tempfiles.append(tmpdir)
    self.path = os.path.join(tmpdir, partition)

    #调用BlockImageDiff对象的Compute方法，核心方法在这。
    b.Compute(self.path)

    self._required_cache = b.max_stashed_size
    self.touched_src_ranges = b.touched_src_ranges
    self.touched_src_sha1 = b.touched_src_sha1

    if src is None:
      _, self.device = GetTypeAndDevice("/" + partition, OPTIONS.info_dict)
    else:
      _, self.device = GetTypeAndDevice("/" + partition,
                                        OPTIONS.source_info_dict)

def Compute(self, prefix):  # prefix 是一个临时文件，用于存放计算结果
  # When looking for a source file to use as the diff input for a
  # target file, we try:
  #   1) an exact path match if available, otherwise
  #   2) a exact basename match if available, otherwise
  #   3) a basename match after all runs of digits are replaced by
  #      "#" if available, otherwise
  #   4) we have no source for this target.
  self.AbbreviateSourceNames() # 对target_src的file_map提取所有的key，将文件名保存起来
  self.FindTransfers()
  # 对file_map中的标志为filename/__ZERO/__NONZERO/__COPY的信息进行转换
  # 非filename: 直接创建一个Transfer
  # filename：将标志为'diff'，并区分文件有没有数字，然后创建对应的Transfer，如果文件过大，将被分为多个Transfer。具体依照cache分区的大小。
  # 不是标志的target信息，被标志为'new'来创建Transfer对象
  # 将上面创建的Transfer对象保存到transfers列表中。

  # Find the ordering dependencies among transfers (this is O(n^2)
  # in the number of transfers).
  self.GenerateDigraph() # 对生成的transfers列表进行排序，这样的好处是方便数据顺序写入。

  # 搞不懂下面这几个是什么鬼算法，但是至少知道，它是优化transfers列表的。
  # Find a sequence of transfers that satisfies as many ordering
  # dependencies as possible (heuristically).
  self.FindVertexSequence()  
  # Fix up the ordering dependencies that the sequence didn't
  # satisfy.
  if self.version == 1:
    self.RemoveBackwardEdges()
  else:
    self.ReverseBackwardEdges()
    self.ImproveVertexSequence()

  # Ensure the runtime stash size is under the limit.
  if self.version >= 2 and common.OPTIONS.cache_size is not None:
    self.ReviseStashSize()

  # Double-check our work.
  self.AssertSequenceGood()

  # 对transfers进行分类计算和处理
  # 对于zip格式的文件，如apk、jar、zip，采用imgdiff工具，对于其它文件，采用bsdiff工具。
  # 分别给.patch.dat 和 .new.dat写入对应的数据。
  # 对于full非差分升级包，.patch.dat为空。
  self.ComputePatches(prefix)
  self.WriteTransfers(prefix)