src/kallsyms.ml

   1 (* virt-dmesg
   2  * (C) Copyright 2008-2011 Red Hat Inc.
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *)
  18
  19 open Printf
  20
  21 open Utils
  22
  23 (* This code tries to find the /proc/kallsyms table.  This is in an
  24  * odd compressed format (but not a very successful compression
  25  * format).  However if it exists we know that it will contain
  26  * addresses of the ordinary ksyms, and it has some characteristics
  27  * which make it easy to detect in the memory.
  28  *
  29  * kallsyms contains a complete list of symbols so is much more useful
  30  * than the basic list of exports.
  31  *)
  32
  33 let min_kallsyms_tabsize = 1_000L
  34 let max_kallsyms_tabsize = 1_000_000L (* 433056 kallsyms in 64 bit F14 kernel *)
  35
  36 type kallsyms_compr =
  37   | Compressed of (string * int64) list * int64
  38   | Uncompressed of (string * int64) list
  39
  40 let search_kallsyms k map =
  41   let ksym_addrs = filter_map (
  42     fun ksym -> try Some (StringMap.find ksym map) with Not_found -> None
  43   ) Ksyms.common_ksyms in
  44
  45   (* Search for those kernel addresses in the image.  We're looking
  46    * for the table kallsyms_addresses followed by kallsyms_num_syms
  47    * (number of symbols in the table).
  48    *)
  49   let ksym_addrs =
  50     List.concat (List.map (Kernel.find_all_pointers k) ksym_addrs) in
  51
  52   (* Test each one to see if it's a candidate list of kernel
  53    * addresses followed by length of list.
  54    *)
  55   let kallsymtabs = filter_map (
  56     fun addr ->
  57       (* Search upwards from address until we find the length field.
  58        * If found, jump backwards by length and check all addresses.
  59        *)
  60       debug "testing candidate kallsyms at %Lx" addr;
  61
  62       (* Addresses which can appear in kallsyms can be validly not
  63        * mapped.  This appears to only happen for 64 bit kernels.
  64        *)
  65       let is_kallsyms_valid_address =
  66         match k.Kernel.wordsize with
  67         | Kernel.Word32 -> Kernel.is_mapped k
  68         | Kernel.Word64 ->
  69             fun addr ->
  70               Kernel.is_mapped k addr
  71               || Kernel.addr_compare addr 0xffffffff_80000000_L >= 0
  72               || Kernel.addr_compare addr 0x00000000_00200000_L <= 0
  73       in
  74
  75       let rec loop prev_addrp addr =
  76         let addrp = Kernel.follow_pointer k addr in
  77
  78         (* kallsyms are sorted, so this gives us an additional heuristic *)
  79         let increasing =
  80           match prev_addrp with
  81           | None -> true
  82           | Some prev_addrp -> Kernel.addr_compare prev_addrp addrp <= 0 in
  83
  84         if increasing && is_kallsyms_valid_address addrp then
  85           (* continue up the table *)
  86           loop (Some addrp) (Kernel.succ_word k addr)
  87         else
  88           if addrp >= min_kallsyms_tabsize &&
  89             addrp <= max_kallsyms_tabsize then (
  90               (* addrp might be the symbol count.  Count backwards and
  91                * check the full table.
  92                *)
  93               debug "addrp (num_entries) = %Lx" addrp;
  94
  95               let num_entries = Int64.to_int addrp in
  96               let entry_size = Kernel.bytes_of_wordsize k in
  97               let start_addr =
  98                 addr -^ Int64.of_int (entry_size * num_entries) in
  99               let end_addr = addr in
 100               let rec loop2 addr =
 101                 if Kernel.addr_compare addr end_addr < 0 then (
 102                   let addrp = Kernel.follow_pointer k addr in
 103                   if is_kallsyms_valid_address addrp then
 104                     loop2 (Kernel.succ_word k addr)
 105                   else (
 106                     debug "rejected on second pass because addrp = %Lx" addrp;
 107                     None
 108                   )
 109                 ) else
 110                   (* ok! *)
 111                   let names_addr = Kernel.succ_word k end_addr in
 112                   debug "candidate kallsyms found at %Lx (names_addr at %Lx, num_entries %d)"
 113                     start_addr names_addr num_entries;
 114                   Some (start_addr, num_entries, names_addr)
 115               in
 116               loop2 start_addr
 117             )
 118           else (
 119             debug "rejected on first pass because addrp = %Lx" addrp;
 120             None
 121           )
 122       in
 123       match loop None addr with
 124       | None -> None
 125       | Some (start_addr, num_entries, names_addr) ->
 126           (* As an additional verification, check the list of
 127            * kallsyms_names.
 128            *)
 129           try
 130             (* If the first byte is '\000' and is followed by a
 131              * C identifier, then this is old-school list of
 132              * symbols with prefix compression as in 2.6.9.
 133              * Otherwise Huffman-compressed kallsyms as in
 134              * 2.6.25.
 135              *)
 136             if Kernel.get_byte k names_addr = 0 &&
 137               Kernel.is_C_identifier k (names_addr+^1L) then (
 138                 let names = ref [] in
 139                 let prev = ref "" in
 140                 let rec loop names_addr start_addr num =
 141                   if num > 0 then (
 142                     let prefix = Kernel.get_byte k names_addr in
 143                     let prefix = String.sub !prev 0 prefix in
 144                     let name =
 145                       Kernel.get_string k (names_addr+^1L) in
 146                     let len = String.length name in
 147                     let name = prefix ^ name in
 148                     prev := name;
 149                     let names_addr = names_addr +^ Int64.of_int len +^ 2L in
 150                     let sym_value = Kernel.follow_pointer k start_addr in
 151                     let start_addr = Kernel.succ_word k start_addr in
 152                     (*eprintf "%S -> %Lx\n" name sym_value;*)
 153                     names := (name, sym_value) :: !names;
 154                     loop names_addr start_addr (num-1)
 155                   )
 156                 in
 157                 loop names_addr start_addr num_entries;
 158                 let names = List.rev !names in
 159
 160                 Some (start_addr, num_entries, names_addr,
 161                       Uncompressed names)
 162               )
 163             else ( (* new-style "compressed" names. *)
 164               let compressed_names = ref [] in
 165               let rec loop names_addr start_addr num =
 166                 if num > 0 then (
 167                   let len = Kernel.get_byte k names_addr in
 168                   let name = Kernel.get_memory k (names_addr+^1L) len in
 169                   let names_addr = names_addr +^ Int64.of_int len +^ 1L in
 170                   let sym_value = Kernel.follow_pointer k start_addr in
 171                   let start_addr = Kernel.succ_word k start_addr in
 172                   compressed_names :=
 173                     (name, sym_value) :: !compressed_names;
 174                   loop names_addr start_addr (num-1)
 175                 ) else
 176                   names_addr
 177               in
 178               let markers_addr = loop names_addr start_addr num_entries in
 179               let markers_addr = Kernel.succ_align k markers_addr in
 180               let compressed_names = List.rev !compressed_names in
 181
 182               Some (start_addr, num_entries, names_addr,
 183                     Compressed (compressed_names, markers_addr))
 184             )
 185           with
 186             Invalid_argument _ -> None (* bad names list *)
 187   ) ksym_addrs in
 188
 189   debug "candidate kallsyms at:";
 190   List.iter (
 191     function
 192     | (start_addr, num_entries, names_addr, Uncompressed _) ->
 193         debug "\t%Lx %d entries names_addr=%Lx old-style"
 194           start_addr num_entries names_addr
 195     | (start_addr, num_entries, names_addr,
 196        Compressed (_, markers_addr)) ->
 197         debug "\t%Lx %d entries names_addr=%Lx markers_addr=%Lx"
 198           start_addr num_entries names_addr markers_addr
 199   ) kallsymtabs;
 200
 201   (* Vote for the most popular symbol table candidate and
 202    * return the list of kallsyms.
 203    *)
 204   let freqs = frequency kallsymtabs in
 205   match freqs with
 206   | [] ->
 207       (* Can't find any kallsymtabs. *)
 208       raise Not_found
 209
 210   | (_, (_, _, _, Uncompressed names)) :: _ ->
 211       names
 212
 213   | (_, (start_addr, num_entries, names_addr,
 214          Compressed (compressed_names, markers_addr))) :: _ ->
 215       (* Skip the markers and look for the token table. *)
 216       let num_markers = Int64.of_int ((num_entries + 255) / 256) in
 217       let marker_size = Int64.of_int (Kernel.bytes_of_wordsize k) in
 218       let tokens_addr = markers_addr +^ marker_size *^ num_markers in
 219
 220       (* Now read out the compression tokens, which are just
 221        * 256 ASCIIZ strings that map bytes in the compression
 222        * names to substrings.
 223        *)
 224       let tokens = Array.make 256 "" in
 225       let rec loop i addr =
 226         if i < 256 then (
 227           let str = Kernel.get_string k addr in
 228           let len = String.length str in
 229           let addr = addr +^ Int64.of_int (len+1) in
 230           tokens.(i) <- str;
 231           loop (i+1) addr
 232         )
 233       in
 234       loop 0 tokens_addr;
 235
 236       (* Expand the compressed names using the tokens. *)
 237       filter_map (
 238         fun (name, sym_value) ->
 239           let f c = tokens.(Char.code c) in
 240           let name = replace_chars f name in
 241           (* First character in uncompressed output is the symbol
 242            * type, eg. 'T'/'t' for text etc.
 243            *)
 244           (* NOTE: Symbol names are NOT unique
 245            * (eg. 'con_start' is both a function and data in
 246            * some kernels).  XXX We need to handle this situation
 247            * better.
 248            *)
 249           (*let typ = name.[0] in*)
 250           let name = String.sub name 1 (String.length name - 1) in
 251           (*eprintf "%S -> %Lx\n" name sym_value;*)
 252           Some (name, sym_value)
 253       ) compressed_names