class Metasm::Heap

Attributes

allarrays[RW]

{ chunkinarray => { rootptr => [chunks] } }

alllists[RW]

chunk ptr => { dwindex => [list of ptrs] }

arrays[RW]

{ chunkinarray => { rootptr => [chunks] } }

buckets[RW]

{ chunk size => [list of chunk addrs] }

chunk_struct[RW]

hash chunk user pointer -> C::Struct

chunks[RW]

hash chunk userdata pointer -> chunk userdata size

cp[RW]
kernels[RW]

find the kernels of the graph (strongly connected components) must be called after scan_xr also find the graph diameter

linkedlists[RW]

chunk ptr => { dwindex => [list of ptrs] }

maxpath[RW]

find the kernels of the graph (strongly connected components) must be called after scan_xr also find the graph diameter

ptsz[RW]
range[RW]
roots[RW]
vm[RW]
xrchunksfrom[RW]

the chunk graph: chunk pointer -> [array of chunks addrs pointed]

xrchunksto[RW]

the chunk graph: chunk pointer -> [array of chunks addrs pointed]

Public Class Methods

new(dbg) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 18
def initialize(dbg)
        @dbg = dbg
        @dbg.pid_stuff_list << :heap
        @dbg.heap = self
        @range = {}
        @dwcache = {}
        # userdata_ptr => len
        @chunks = {}
        @xrchunksto = {}
        @xrchunksfrom = {}
        @ptsz = dbg.cpu.size/8
        # ptr => C::Struct
        @chunk_struct = {}
end

Public Instance Methods

bucketize() click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 91
def bucketize
        @buckets = {}
        chunklist.each { |a|
                (@buckets[@chunks[a]] ||= []) << a
        }
end
check_linkedlist(ptr, dwoff) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 217
def check_linkedlist(ptr, dwoff)
        psz = @chunks[ptr]
        fwd = ptr
        lst = [fwd]
        base = find_range(fwd)
        loop do
                if not base or base > fwd or base + @range[base] <= fwd
                        base = find_range(fwd)
                end
                break if not base
                fwd = dwcache(base, @range[base])[(fwd-base)/@ptsz + dwoff]
                break if fwd == 0
                return if not cl = @chunks[fwd] # XXX root/tail may be in .data
                return if cl != psz
                break if lst.include? fwd
                lst << fwd
        end
        fwd = ptr
        while pv = @xrchunksfrom[fwd]
                fwd = pv.find { |p|
                        next if @chunks[p] != psz
                        if not base or base > p or base + @range[base] <= p
                                base = find_range(fwd)
                        end
                        dwcache(base, @range[base])[(p-base)/@ptsz + dwoff] == fwd
                }
                break if not fwd
                break if lst.include? fwd
                lst.unshift fwd
        end
        if lst.length > 3
                lst.each { |p| (@linkedlists[p] ||= {})[dwoff] = lst }
                @alllists << lst
        end
end
chunkdw(ptr, len=@chunks[ptr]) click to toggle source

return the array of dwords in the chunk

# File samples/dbg-plugins/heapscan/heapscan.rb, line 42
def chunkdw(ptr, len=@chunks[ptr])
        if base = find_range(ptr)
                dwcache(base, @range[base])[(ptr-base)/@ptsz, len/@ptsz]
        end
end
chunklist() click to toggle source

returns the list of chunks, sorted

# File samples/dbg-plugins/heapscan/heapscan.rb, line 49
def chunklist
        @chunklist ||= @chunks.keys.sort
end
dump_graph(fname='graph.gv', graph=@xrchunksto) click to toggle source

dump the whole graph in a dot file

# File samples/dbg-plugins/heapscan/heapscan.rb, line 186
def dump_graph(fname='graph.gv', graph=@xrchunksto)
        File.open(fname, 'w') { |fd|
                fd.puts "digraph foo {"
                graph.each { |b, l|
                        fd.puts l.map { |e| '"%x" -> "%x";' % [b, e] }
                }
                fd.puts "}"
        }
end
dwcache(base, len) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 37
def dwcache(base, len)
        @dwcache[[base, len]] ||= pagecache(base, len).unpack(@ptsz == 4 ? 'L*' : 'Q*')
end
find_arrays() click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 255
def find_arrays
        @arrays = {}
        @allarrays = []
        @buckets.sort.each { |sz, lst|
                next if sz < @ptsz*6
                lst.each { |ptr|
                        next if not to = @xrchunksto[ptr]
                        # a table must have at least half its storage space filled with ptrs
                        next if to.length <= sz/@ptsz/2
                        # also, ptrs must point to same-size stuff
                        lsz = Hash.new(0)
                        to.each { |t| lsz[@chunks[t]] += 1 }
                        cnt = lsz.values.max
                        next if cnt <= sz/@ptsz/2
                        tgsz = lsz.index(cnt)
                        ar = to.find_all { |t| @chunks[t] == tgsz }.uniq
                        next if ar.length <= sz/@ptsz/2
                        ar.each { |p| (@arrays[p] ||= {})[ptr] = ar }
                        @allarrays << ar
                }
        }
end
find_chunk(ptr) click to toggle source

find the chunk encompassing ptr

# File samples/dbg-plugins/heapscan/heapscan.rb, line 80
def find_chunk(ptr)
        find_elem(ptr, @chunks, chunklist)
end
find_elem(ptr, len, list=nil) click to toggle source

dichotomic search of the chunk containing ptr len = hash ptr => length list = list of hash keys sorted

# File samples/dbg-plugins/heapscan/heapscan.rb, line 56
def find_elem(ptr, len, list=nil)
        return ptr if len[ptr]

        list ||= len.keys.sort

        if list.length < 16
                return list.find { |p| p <= ptr and p + len[p] > ptr }
        end 

        window = list
        while window and not window.empty?
                i = window.length/2
                wi = window[i]
                if ptr < wi
                        window = window[0, i]
                elsif ptr < wi + len[wi]
                        return wi
                else
                        window = window[i+1, i]
                end
        end
end
find_kernels(adj = @xrchunksto) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 102
def find_kernels(adj = @xrchunksto)
        @maxpath = []
        kernels = {}
        adj.keys.sort.each { |ptr|
                next if kernels[ptr]
                paths = [[ptr]]
                while path = paths.pop
                        next if not l = @xrchunksfrom[path.first]
                        l.each { |pl|
                                next if kernels[pl]
                                next if not adj[pl]
                                if path.include?(pl)
                                        kernels[pl] = true
                                else
                                        paths << [pl, *path]
                                end
                        }
                        @maxpath = paths.last if paths.last and paths.last.length > @maxpath.length
                end
        }
        if @maxpath.first and np = (adj[@maxpath.last] - @maxpath).first
                @maxpath << np
        end
        @kernels = []
        while k = kernels.index(true)
                curk = reachfrom(k, adj).find_all { |ok|
                        true == reachfrom(ok, adj) { |tk|
                                break true if tk == k
                        }
                }
                @kernels << curk
                curk.each { |ka| kernels.delete ka }
        end
end
find_linkedlists() click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 198
def find_linkedlists
        @linkedlists = {}
        @alllists = []
        @buckets.sort.each { |sz, lst|
                #puts "sz #{sz} #{lst.length}"
                lst.each { |ptr|
                        next if not l = @xrchunksto[ptr]
                        next if not l.find { |tg| @chunks[tg] == sz }
                        dw = chunkdw(ptr)
                        dw.length.times { |dwoff|
                                next if @linkedlists[ptr] and @linkedlists[ptr][dwoff]
                                tg = dw[dwoff]
                                next if @chunks[tg] != sz
                                check_linkedlist(ptr, dwoff)
                        }
                }
        }
end
find_range(ptr) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 84
def find_range(ptr)
        @range_keys ||= @range.keys.sort
        find_elem(ptr, @range, @range_keys)
end
find_roots(adj=@xrchunksto) click to toggle source

find the root nodes that allow acces to most other nodes { root => [reachable nodes] } does not include single nodes (@chunks.keys - @xrchunksfrom.keys)

# File samples/dbg-plugins/heapscan/heapscan.rb, line 141
def find_roots(adj=@xrchunksto)
        @roots = {}
        adj.keys.sort.each { |r|
                if not @roots[r]
                        l = reachfrom(r, adj, @roots)
                        l.each { |t| @roots[t] = true if adj[t] }   # may include r !, also dont mark leaves
                        @roots[r] = l
                end
        }
        @roots.delete_if { |k, v| v == true }
end
graph_from(p, adj = @xrchunksto) click to toggle source

create a subset of xrchunksto from one point

# File samples/dbg-plugins/heapscan/heapscan.rb, line 172
def graph_from(p, adj = @xrchunksto)
        hash = {}
        todo = [p]
        while p = todo.pop
                next if hash[p]
                if adj[p]
                        hash[p] = adj[p]
                        todo.concat hash[p]
                end
        end
        hash
end
pagecache(base, len) click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 33
def pagecache(base, len)
        @dbg.read_mapped_range(base, len)
end
reachfrom(p, adj = @xrchunksto, roots={}) { |tk| ... } click to toggle source
# File samples/dbg-plugins/heapscan/heapscan.rb, line 153
def reachfrom(p, adj = @xrchunksto, roots={})
        return roots[p] if roots[p].kind_of? Array
        hash = {}
        todo = [p]
        while p = todo.pop
                if to = roots[p] || adj[p] and to.kind_of? Array
                        to.each { |tk|
                                if not hash[tk]
                                        hash[tk] = true
                                        todo << tk
                                        yield tk if block_given?
                                end
                        }
                end
        end
        hash.keys
end