Subversion Repositories freemyipod

#!/usr/bin/env python

#

#

#    Copyright 2011 TheSeven

#

#

#    This file is part of emCORE.

#

#    emCORE is free software: you can redistribute it and/or

#    modify it under the terms of the GNU General Public License as

#    published by the Free Software Foundation, either version 2 of the

#    License, or (at your option) any later version.

#

#    emCORE is distributed in the hope that it will be useful,

#    but WITHOUT ANY WARRANTY; without even the implied warranty of

#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

#    See the GNU General Public License for more details.

#

#    You should have received a copy of the GNU General Public License

#    along with emCORE.  If not, see <http://www.gnu.org/licenses/>.

#

#

import sys

import struct

from misc import ExtendedCStruct

from ctypes import *

def usage():

  print("Usage: %s <image> [image_base] [tlsf_pool] [SL_INDEX_COUNT_LOG2] [FL_INDEX_MAX]" % (sys.argv[0]))

  exit(2)

image_base = 0x08000000

tlsf_pool = 0x08000000

SL_INDEX_COUNT_LOG2 = 5

FL_INDEX_MAX = 30

if len(sys.argv) < 2: usage()

filename = sys.argv[1]

if len(sys.argv) > 2: image_base = int(sys.argv[2])

if len(sys.argv) > 3: tlsf_pool = int(sys.argv[3])

if len(sys.argv) > 4: SL_INDEX_COUNT_LOG2 = int(sys.argv[4])

if len(sys.argv) > 5: FL_INDEX_MAX = int(sys.argv[5])

if len(sys.argv) > 6: usage()

file = open(filename, "rb")

data = file.read()

file.close()

SL_INDEX_COUNT = 1 << SL_INDEX_COUNT_LOG2

FL_INDEX_SHIFT = SL_INDEX_COUNT_LOG2 + 2

FL_INDEX_COUNT = FL_INDEX_MAX - FL_INDEX_SHIFT + 1

SMALL_BLOCK_SIZE = 1 << FL_INDEX_SHIFT

class block_header_t(ExtendedCStruct):

  _fields_ = [("prev_phys_block", c_uint32),

              ("size", c_uint32),

              ("next_free", c_uint32),

              ("prev_free", c_uint32)]

  def is_last(self):

    return self.get_size() == 0;

  def is_null(self):

    return self._address_ == self.next_free and self.size == 0 and self.prev_phys_block == 0

  def is_free(self):

    return (self.size & block_header_free_bit) != 0;

  def is_prev_free(self):

    return (self.size & block_header_prev_free_bit) != 0;

  def get_address(self):

    return self._address_

  def get_size(self):

    return self.size & 0xfffffffc

  def get_prev_free(self):

    if not self.is_free(): raise Exception("Trying to get previous free block of non-free block")

    return block_header_t(self._data_, self._base_, self.prev_free)

  def get_next_free(self):

    if not self.is_free(): raise Exception("Trying to get next free block of non-free block")

    return block_header_t(self._data_, self._base_, self.next_free)

  def get_prev_phys(self):

    if not self.is_prev_free(): raise Exception("Trying to get non-free previous physical block")

    return block_header_t(self._data_, self._base_, self.prev_phys_block)

  def get_next_phys(self):

    return self.get_next_by_offset(self.get_size() + 4)

  def get_next_by_offset(self, offset):

    return block_header_t(self._data_, self._base_, self._address_ + offset)

class pool_t(ExtendedCStruct):

  _fields_ = [("fl_bitmap", c_uint32),

              ("sl_bitmap", c_uint32 * FL_INDEX_COUNT),

              ("blocks", c_uint32 * SL_INDEX_COUNT * FL_INDEX_COUNT)]

block_header_free_bit = 1

block_header_prev_free_bit = 2

block_size_min = sizeof(block_header_t) - 4;

block_size_max = 1 << FL_INDEX_MAX

pool = pool_t(data, image_base, tlsf_pool)

block = block_header_t(data, image_base, tlsf_pool + sizeof(pool_t) - 4)

prev_free = False

prev_addr = 0

blocks = []

free_blocks = []

bytes_used = 0

bytes_free = 0

while True:

  if block.is_prev_free() != prev_free:

    print("Block %08X previous free indicator is %d, expected %d" % (block.get_address(), block.is_prev_free(), prev_free))

  if prev_free and prev_addr != block.prev_phys_block:

    print("Block %08X previous physical block address is wrong. Got %08X, should be %08X" % (block.get_address(), block.prev_phys_block, prev_addr))

  prev_free = block.is_free()

  prev_addr = block.get_address()

  if block.is_last(): break

  if blocks.count(prev_addr) > 0:

    print("Block loop detected at %08X" % (prev_addr))

    break

  blocks.append(prev_addr)

  if prev_free:

    print("%08X: %08X bytes free" % (prev_addr + 4, block.get_size() + 4))

    free_blocks.append(prev_addr)

    bytes_free = bytes_free + block.get_size() + 4

  else:

    owner_address = prev_addr - image_base + block.get_size() - 4

    owner = struct.unpack("<I", data[owner_address : owner_address + 4])[0]

    print("%08X: %08X+8 bytes owned by %08X" % (prev_addr + 8, block.get_size() - 4, owner))

    bytes_used = bytes_used + block.get_size() + 4

  try: block = block.get_next_phys()

  except:

    print("Block %08X has invalid size: %08X" % (prev_addr, block.get_size()))

    print("Fatal error in block chain, continuing with map check")

    break

handled_blocks = []

for i in range(FL_INDEX_COUNT):

  fl_map = (pool.fl_bitmap >> i) & 1

  sl_list = pool.sl_bitmap[i]

  if fl_map == 0:

    if sl_list != 0:

      print("[%d:%d] Second-level map must be null, but isn't" % (i, j))

  elif sl_list == 0:

    print("[%d:%d] No free blocks in second-level map, but first-level map indicates there are some" % (i, j))

  for j in range(SL_INDEX_COUNT):

    sl_map = (sl_list >> j) & 1

    ba = pool.blocks[i][j]

    block = block_header_t(data, image_base, ba)

    if sl_map == 0:

      if not block.is_null():

        print("[%d:%d:%08X] Block list must be null, but isn't" % (i, j, ba))

      continue

    elif block.is_null():

      print("[%d:%d:%08X] Block list is null, but second-level map indicates there are free blocks" % (i, j, ba))

    blocks = []

    while not block.is_null():

      fatal = False

      addr = block.get_address()

      if blocks.count(addr) > 0:

        print("[%d:%d:%08X] Detected block loop" % (i, j, addr))

        break

      blocks.append(addr)

      if not block.is_free():

        print("[%d:%d:%08X] Non-free block on free list" % (i, j, addr))

        fatal = True

      if block.is_prev_free():

        print("[%d:%d:%08X] Block should have coalesced with previous one" % (i, j, addr))

      try:

        if block.get_next_phys().is_free():

          print("[%d:%d:%08X] Block should have coalesced with next one" % (i, j, addr))

      except:

        print("Block %08X has invalid size: %08X" % (addr, block.get_size()))

        fatal = True

      size = block.get_size()

      if size < block_size_min:

        print("[%d:%d:%08X] Block violates minimum size: %d (should be at least %d)" % (i, j, addr, size, block_size_min))

      if size > block_size_max:

        print("[%d:%d:%08X] Block violates maximum size: %d (should be at most %d)" % (i, j, addr, size, block_size_max))

      if size < SMALL_BLOCK_SIZE:

        fl = 0

        sl = size / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT)

      else:

        fl = 32 - FL_INDEX_SHIFT;

        if (size & 0xffff0000) == 0:

          size = size << 16

          fl = fl - 16

        if (size & 0xff000000) == 0:

          size = size << 8

          fl = fl - 8

        if (size & 0xf0000000) == 0:

          size = size << 4

          fl = fl - 4

        if (size & 0xc0000000) == 0:

          size = size << 2

          fl = fl - 2

        if (size & 0x80000000) == 0:

          size = size << 1

          fl = fl - 1

        sl = (block.get_size() >> (fl - SL_INDEX_COUNT_LOG2 + FL_INDEX_SHIFT - 1)) ^ (1 << SL_INDEX_COUNT_LOG2)

      if fl != i or sl != j:

        print("Block %08X is in wrong free list: [%d:%d] (should be [%d:%d])" % (addr, i, j, fl, sl))

      if free_blocks.count(addr) != 1:

        print("[%d:%d:%08X] Block is in free list, but was not found in pool" % (i, j, addr))

      if handled_blocks.count(addr) > 0:

        print("[%d:%d:%08X] Block appears in multiple free lists" % (i, j, addr))

      else: handled_blocks.append(addr)

      if fatal:

        print("Fatal error in block chain, continuing with next chain")

        break

      block = block.get_next_free()

for addr in free_blocks:

  if handled_blocks.count(addr) != 1:

    print("Free block %08X does not appear in any free list" % (addr))