src/kernel.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 (* C functions, see [c_utils.c] file. *)
  24 external str_mapping : int64 -> int64 -> int -> int
  25   = "virt_dmesg_str_mapping" "noalloc"
  26 external strstr_from : string -> string -> int -> int = "virt_dmesg_strstr_from"
  27 external strstr_from_aligned : string -> string -> int -> int
  28   = "virt_dmesg_strstr_from_aligned"
  29 external str_get_le32 : string -> int -> int64 = "virt_dmesg_str_get_le32"
  30 external str_get_be32 : string -> int -> int64 = "virt_dmesg_str_get_be32"
  31 external str_get_le64 : string -> int -> int64 = "virt_dmesg_str_get_le64"
  32 external str_get_be64 : string -> int -> int64 = "virt_dmesg_str_get_be64"
  33 external str_of_le32 : int64 -> string = "virt_dmesg_str_of_le32"
  34 external str_of_be32 : int64 -> string = "virt_dmesg_str_of_be32"
  35 external str_of_le64 : int64 -> string = "virt_dmesg_str_of_le64"
  36 external str_of_be64 : int64 -> string = "virt_dmesg_str_of_be64"
  37 external get_asciiz : string -> int -> string = "virt_dmesg_get_asciiz"
  38 external is_C_ident : string -> int -> bool = "virt_dmesg_is_C_ident"
  39 external crc32_of_string : string -> int32 = "virt_dmesg_crc32_of_string"
  40 external addr_compare : int64 -> int64 -> int
  41   = "virt_dmesg_addr_compare" "noalloc"
  42
  43 type t = {
  44   (* Note that 'base_addr' is the guest virtual address of the first
  45    * byte in the 'data' string.
  46    *)
  47   data : string;
  48   base_addr : int64;
  49
  50   endian : endian;
  51   wordsize : wordsize;
  52 }
  53
  54 and endian = BigEndian | LittleEndian
  55
  56 and wordsize = Word32 | Word64
  57
  58 let string_of_endian = function
  59   | BigEndian -> "big endian"
  60   | LittleEndian -> "little endian"
  61
  62 let string_of_wordsize = function
  63   | Word32 -> "32 bit"
  64   | Word64 -> "64 bit"
  65
  66 let succ_word { wordsize = wordsize } addr =
  67   match wordsize with Word32 -> addr +^ 4L | Word64 -> addr +^ 8L
  68
  69 let pred_word { wordsize = wordsize } addr =
  70   match wordsize with Word32 -> addr -^ 4L | Word64 -> addr -^ 8L
  71
  72 let succ_align { wordsize = wordsize } addr =
  73   let mask = match wordsize with Word32 -> 3L | Word64 -> 7L in
  74   (addr +^ mask) &^ (Int64.lognot mask)
  75
  76 let bytes_of_wordsize = function
  77   | { wordsize = Word32 } -> 4
  78   | { wordsize = Word64 } -> 8
  79
  80 let create base_addr f =
  81   (* XXX Make kernel size configurable. *)
  82   let len = 16 * 1024 * 1024 - 65536 in
  83   let top_addr = base_addr +^ Int64.of_int len in
  84
  85   (* As we're loading the kernel, keep running stats on the number of
  86    * valid (or "probably valid") pointers found that are:
  87    *  - 32 bit, aligned, little endian
  88    *  - 32 bit, aligned, big endian
  89    *  - 64 bit, aligned, little endian
  90    *  - 64 bit, aligned, big endian
  91    * and the total amount of data read.  Use these stats to heuristically
  92    * determine endianness and word size, and also reject the kernel
  93    * early by raising [Not_found] if it doesn't look like a kernel.
  94    *
  95    * Also a characteristic of qemu is that if you ask for an invalid
  96    * virtual address, it returns the same set of blocks of random data
  97    * over and over.  Detect this by keeping a count of the checksum
  98    * of each block.
  99    *)
 100   let update_stats, get_endian_wordsize =
 101     let blocks = ref 0 in
 102     let size = ref 0 in
 103     let le32 = ref 0 and be32 = ref 0 and le64 = ref 0 and be64 = ref 0 in
 104     let max_le32_pc = ref 0. and max_be32_pc = ref 0.
 105     and max_le64_pc = ref 0. and max_be64_pc = ref 0. in
 106     let checksums = Counter.create () in
 107
 108     let update_stats data =
 109       incr blocks;
 110
 111       let n = String.length data in
 112       assert (n mod 8 = 0);
 113       size := !size + n;
 114
 115       for i = 0 to n/4 do
 116         let p = str_get_le32 data (i*4) in
 117         if p >= base_addr && p < top_addr then
 118           incr le32;
 119         let p = str_get_be32 data (i*4) in
 120         if p >= base_addr && p < top_addr then
 121           incr be32;
 122       done;
 123       for i = 0 to n/8 do
 124         let p = str_get_le64 data (i*8) in
 125         if p >= base_addr && p < top_addr then
 126           incr le64;
 127         let p = str_get_be64 data (i*8) in
 128         if p >= base_addr && p < top_addr then
 129           incr be64;
 130       done;
 131
 132       (* Because the kernel is likely to be smaller than the memory we
 133        * are reading, keep track of the running maximum of the
 134        * percentage of memory which contains pointers.  The percentages
 135        * will decline once we run off the end of the kernel.
 136        *)
 137       if !size > 1_000_000 then (
 138         let percent v w = float v *. 100. /. (float (!size / w)) in
 139         max_le32_pc := max !max_le32_pc (percent !le32 4);
 140         max_be32_pc := max !max_be32_pc (percent !be32 4);
 141         max_le64_pc := max !max_le64_pc (percent !le64 8);
 142         max_be64_pc := max !max_be64_pc (percent !be64 8);
 143
 144         (* If these are all < 0.1% even after a millions of bytes have
 145          * been read, then we should bail.  It's not a kernel.
 146          *)
 147         if !size > 8_000_000 &&
 148           !max_le32_pc < 0.1 && !max_be32_pc < 0.1 &&
 149           !max_le64_pc < 0.1 && !max_be64_pc < 0.1 then (
 150             debug "doesn't look like a kernel: le32 %g%% be32 %g%% le64 %g%% be64 %g%%"
 151               !max_le32_pc !max_be32_pc !max_le64_pc !max_be64_pc;
 152             raise Not_found
 153           )
 154       );
 155
 156       (* Update block CRC.  Bail if qemu is just giving us the same
 157        * block of data over and over again.  However note that most
 158        * kernels are only about 10 MB in size, and because we read a
 159        * fixed amount (usually 16 MB) at the end of this read we'll be
 160        * reading unmapped memory which can trip this heuristic.
 161        * Therefore only run this heuristic for the first 4 MB of
 162        * memory.
 163        *)
 164       if !size > 2 * 1024 * 1024 && !size <= 4 * 1024 * 1024 then (
 165         let crc = crc32_of_string data in
 166         Counter.incr checksums crc;
 167
 168         if Counter.get checksums crc > !blocks/4 then (
 169           debug "looks like unmapped memory";
 170           raise Not_found
 171         )
 172       )
 173
 174     and get_endian_wordsize () =
 175       if !max_le32_pc > !max_be32_pc && !max_le32_pc > !max_le64_pc &&
 176         !max_le32_pc > !max_be64_pc then
 177           LittleEndian, Word32
 178       else if !max_be32_pc > !max_le64_pc && !max_be32_pc > !max_be64_pc then
 179         BigEndian, Word32
 180       else if !max_le64_pc > !max_be64_pc then
 181         LittleEndian, Word64
 182       else
 183         BigEndian, Word64
 184     in
 185
 186     update_stats, get_endian_wordsize
 187   in
 188
 189   (* Loop loading the kernel. *)
 190   let rec loop i acc =
 191     if i < len then (
 192       let str = f (base_addr +^ Int64.of_int i) in
 193       update_stats str;
 194       loop (i + String.length str) (str :: acc)
 195     ) else
 196       List.rev acc
 197   in
 198   let strs = loop 0 [] in
 199   let data = String.concat "" strs in
 200   assert (String.length data = len);
 201
 202   let endian, wordsize = get_endian_wordsize () in
 203
 204   { data = data; base_addr = base_addr; endian = endian; wordsize = wordsize }
 205
 206 let rec find_first k str =
 207   find_from k k.base_addr str
 208
 209 and find_all k str =
 210   let rec loop addr acc =
 211     try
 212       let a = find_from k addr str in
 213       loop (a +^ 1L) (a :: acc)
 214     with Not_found -> List.rev acc
 215   in
 216   loop k.base_addr []
 217
 218 and find_from { data = data; base_addr = base_addr } addr str =
 219   let off = str_mapping base_addr addr (String.length data) in
 220   assert (off >= 0);
 221   let found_off = strstr_from data str off in
 222   base_addr +^ Int64.of_int found_off
 223
 224 let find_all_pointers ({ endian = endian; wordsize = wordsize } as k) ptr =
 225   let str =
 226     match endian, wordsize with
 227     | LittleEndian, Word32 -> str_of_le32 ptr
 228     | BigEndian, Word32 -> str_of_be32 ptr
 229     | LittleEndian, Word64 -> str_of_le64 ptr
 230     | BigEndian, Word64 -> str_of_be64 ptr in
 231
 232   let find_from_aligned addr =
 233     let off = str_mapping k.base_addr addr (String.length k.data) in
 234     assert (off >= 0);
 235     let found_off = strstr_from_aligned k.data str off in
 236     k.base_addr +^ Int64.of_int found_off
 237   in
 238
 239   let rec loop addr acc =
 240     try
 241       let a = find_from_aligned addr in
 242       loop (succ_word k a) (a :: acc)
 243     with Not_found -> List.rev acc
 244   in
 245   loop k.base_addr []
 246
 247 let follow_pointer k addr =
 248   let off = str_mapping k.base_addr addr (String.length k.data) in
 249   assert (off >= 0);
 250   match k.endian, k.wordsize with
 251   | LittleEndian, Word32 -> str_get_le32 k.data off
 252   | BigEndian, Word32 -> str_get_be32 k.data off
 253   | LittleEndian, Word64 -> str_get_le64 k.data off
 254   | BigEndian, Word64 -> str_get_be64 k.data off
 255
 256 let is_mapped k addr =
 257   let off = str_mapping k.base_addr addr (String.length k.data) in
 258   off >= 0
 259
 260 let get_memory k addr len =
 261   let off = str_mapping k.base_addr addr (String.length k.data) in
 262   assert (off >= 0);
 263   assert (len >= 0);
 264   assert (len + off <= String.length k.data);
 265   String.sub k.data off len
 266
 267 let get_byte k addr =
 268   let off = str_mapping k.base_addr addr (String.length k.data) in
 269   assert (off >= 0);
 270   Char.code (String.unsafe_get k.data off)
 271
 272 let get_int32 k addr =
 273   let off = str_mapping k.base_addr addr (String.length k.data - 4) in
 274   assert (off >= 0);
 275   match k.endian with
 276   | LittleEndian -> str_get_le32 k.data off
 277   | BigEndian -> str_get_be32 k.data off
 278
 279 let get_int64 k addr =
 280   let off = str_mapping k.base_addr addr (String.length k.data - 8) in
 281   assert (off >= 0);
 282   match k.endian with
 283   | LittleEndian -> str_get_le64 k.data off
 284   | BigEndian -> str_get_be64 k.data off
 285
 286 let get_string k addr =
 287   let off = str_mapping k.base_addr addr (String.length k.data) in
 288   assert (off >= 0);
 289   get_asciiz k.data off
 290
 291 let is_C_identifier k addr =
 292   let off = str_mapping k.base_addr addr (String.length k.data) in
 293   if off >= 0 then
 294     is_C_ident k.data off
 295   else
 296     false