(* virt-dmesg
 * (C) Copyright 2008-2011 Red Hat Inc.
 *
 * This program 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.
 *
 * This program 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 this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *)

open Printf

open Utils

(* Look for ordinary symbol table.
 *
 * The ordinary symbol table is defined as:
 * struct kernel_symbol {
 *   unsigned long value;
 *   const char *name;  -------> points to string somewhere else
 * } symbols[];
 *
 * What we do is look for some likely symbols (ie. the strings,
 * common_ksyms).  Then (since we know the address of those strings)
 * we look for something which is plausibly a symbol table, searching
 * forwards and backwards to find the ends of it.  This gives us, for
 * each likely symbol found, a corresponding potential symbol table.
 * Then we take a vote for the most frequently occurring symbol table
 * and use that.
 *)

(* Look for some common entries in the exported symbol table and
 * from that find the symbol table itself.  These are just
 * supposed to be symbols which are very likely to be present
 * in any Linux kernel, although we only need one of them to be
 * present to find the symbol table.
 *
 * NB. Must not be __initdata, must be in EXPORT_SYMBOL.
 *)
let common_ksyms = [
  "init_task";                          (* first task_struct *)
  "root_mountflags";                    (* flags for mounting root fs *)
  "init_uts_ns";                        (* uname strings *)
  "nr_cpu_ids";
  "speedstep_get_freqs";
  "hpet_register_irq_handler";
  "tty_put_char";
  "driver_find";
  "scsi_register_driver";
  "phy_register_fixup";
  "input_register_handler";
  "save_processor_state";
]

let search_ksyms k =
  let sym_addrs : (string * int64) list =
    List.concat (
      List.map (
        fun symbol ->
          let addrs = Kernel.find_all k (sprintf "\000%s\000" symbol) in
          (* Need to +1 because the string we matched started with \0
           * character.
           *)
          let addrs = List.map ((+^) 1L) addrs in
          List.map (fun addr -> (symbol, addr)) addrs
      ) common_ksyms
    ) in

  let sym_tables : (int64 * int64) list =
    List.concat (
      List.map (
        fun (source_symbol, addr) ->
          let addrs = Kernel.find_all_pointers k addr in

          (* struct kernel_symbol {
           *   unsigned long value;
           *   const char *name; <--- each of addrs (could) point here
           * } symbols[];
           *)

          (* Look at 'value' field and see if it's likely to be a
           * value.  Filter out if not.
           *)
          let addrs = List.filter (
            fun a ->
              let a2 = Kernel.pred_word k a in
              let a2p = Kernel.follow_pointer k a2 in
              (* We wouldn't expect the value to point somewhere near
               * to the name.
               *)
              Int64.abs (addr -^ a2p) > 32L
          ) addrs in

          (* Search back and forward for beginning and end of symbol table. *)
          let symtab_start_addrs = List.map (
            fun addr ->
              let rec loop addr =
                (* '*addr' should point to a C identifier.  If it
                 * does, step backwards to the previous symbol table
                 * entry.
                 *)
                let addrp = Kernel.follow_pointer k addr in
                if Kernel.is_C_identifier k addrp then
                  loop (Kernel.pred_word k (Kernel.pred_word k addr))
                else
                  Kernel.succ_word k addr
              in
              loop addr
          ) addrs in

          List.iter (
            fun start_addr ->
              debug "start_addr %Lx from %s" start_addr source_symbol
          ) symtab_start_addrs;

          List.map (
            fun start_addr ->
              let rec loop addr =
                let addr2 = Kernel.succ_word k addr in (* &name *)
                let addr2p = Kernel.follow_pointer k addr2 in (* name itself *)
                if Kernel.is_C_identifier k addr2p then
                  loop (Kernel.succ_word k addr2)
                else
                  addr
              in
              let end_addr = loop start_addr in
              start_addr, end_addr -^ start_addr
          ) symtab_start_addrs
      ) sym_addrs
    ) in

  debug "candidate symbol tables:";
  List.iter (
    fun (start, size) ->
      debug "\tstart %Lx size %Ld" start size
  ) sym_tables;

  (* Simply ignore any symbol table candidates which are too small. *)
  let sym_tables = List.filter (fun (_, size) -> size > 64L) sym_tables in

  (* Vote for the most popular symbol table. *)
  let freqs = frequency sym_tables in
  match freqs with
  | [] ->
      (* No symbol table, so this is likely not a kernel that we
       * know how to parse.
       *)
      raise Not_found

  | (_, (start_addr, size)) :: _ ->
      (* Take the most popular symbol table candidate and discard
       * the others.  Parse this into a list of symbols.
       *)
      let rec loop addr acc =
        if addr < start_addr +^ size then
          let value = Kernel.follow_pointer k addr in (* value *)
          let addr2 = Kernel.succ_word k addr in (* &name *)
          let addr2p = Kernel.follow_pointer k addr2 in (* name itself *)
          let symbol = Kernel.get_string k addr2p in
          let acc = (symbol, value) :: acc in
          loop (Kernel.succ_word k addr2) acc
        else
          List.rev acc
      in
      loop start_addr []