class Metasm::Heap
Attributes
{ chunkinarray => { rootptr => [chunks] } }
chunk ptr => { dwindex => [list of ptrs] }
{ chunkinarray => { rootptr => [chunks] } }
{ chunk size => [list of chunk addrs] }
hash chunk user pointer -> C::Struct
hash chunk userdata pointer -> chunk userdata size
find the kernels of the graph (strongly connected components) must be called after scan_xr also find the graph diameter
chunk ptr => { dwindex => [list of ptrs] }
find the kernels of the graph (strongly connected components) must be called after scan_xr also find the graph diameter
the chunk graph: chunk pointer -> [array of chunks addrs pointed]
the chunk graph: chunk pointer -> [array of chunks addrs pointed]
Public Class Methods
# 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
# File samples/dbg-plugins/heapscan/heapscan.rb, line 91 def bucketize @buckets = {} chunklist.each { |a| (@buckets[@chunks[a]] ||= []) << a } end
# 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
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
returns the list of chunks, sorted
# File samples/dbg-plugins/heapscan/heapscan.rb, line 49 def chunklist @chunklist ||= @chunks.keys.sort end
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
# 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
# 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 the chunk encompassing ptr
# File samples/dbg-plugins/heapscan/heapscan.rb, line 80 def find_chunk(ptr) find_elem(ptr, @chunks, chunklist) end
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
# 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
# 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
# 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 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
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
# File samples/dbg-plugins/heapscan/heapscan.rb, line 33 def pagecache(base, len) @dbg.read_mapped_range(base, len) end
# 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