extract/codegen/struct_classify.mli

   1 (** Structure classification. *)
   2 (* Memory info command for virtual domains.
   3    (C) Copyright 2008 Richard W.M. Jones, Red Hat Inc.
   4    http://libvirt.org/
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19  *)
  20
  21 (**
  22    {2 How it works}
  23
  24    There's no getting around it, this is complicated.
  25
  26    {!Pahole_parser} has parsed in a limited set of structures from
  27    each available kernel.  We now aim to take a holistic view of
  28    a structure as it changed over time, though different kernel
  29    versions and also on different architectures.
  30
  31    {3 Shape fields and content fields}
  32
  33    A structure is a list of fields.
  34
  35    Fields fall into two classifications, as far as we are interested:
  36
  37    (i) 'Shape' fields define the relationship between different
  38    structures.  Shape fields are all pointers to other structures
  39    that we care about.   They have type {!Pahole_parser.FStructPointer}
  40    and {!Pahole_parser.FListHeadPointer}.
  41
  42    (ii) 'Content' fields are fields in a structure that contain
  43    some data, like ints and strings.  (In the current implementation,
  44    it's anything left which isn't a shape field).
  45
  46    So we can easily take a structure and place its fields into two
  47    buckets.  For example, with [task_struct] it might be:
  48
  49    [task_struct] shape fields:
  50    - [tasks'next]  (the linked list of tasks)
  51    - [tasks'prev]
  52    - [parent]      (points to the parent task)
  53
  54    [task_struct] content fields:
  55    - [pid]  (process ID)
  56    - [comm] (task name)
  57    - etc. etc.
  58
  59    {3 Shape fields and iterator functions}
  60
  61    For each kernel/structure we can build a list of shape fields, but
  62    in fact in many kernels they will be the same, so we also
  63    performing a {i sharing} operation to minimize the number of
  64    variations.
  65
  66    We also write (by hand) iterator functions.  These iterator
  67    functions are matched to the corresponding shape field structure,
  68    by setting up some prerequisites that the function needs, then
  69    matching on those prerequisites with the available shape
  70    field structures.
  71
  72    {3 Content fields and printing functions}
  73
  74    The same (minimization & matching) applies to hand-written printing
  75    functions over content field structures.
  76
  77    {3 Generated parsing functions}
  78
  79    A third form of minimization is required to find kernel
  80    structures which happen to be similar - ie. all the fields
  81    happen to be in the same place, with the same wordsize and
  82    endianness.
  83
  84    We can then generate a minimal set of parsing functions which
  85    map the binary data from the kernel image into shape and
  86    content field structures.
  87
  88    {3 Generated loading code}
  89
  90    Finally, we generate recursive loading code which recurses over
  91    structures into order to load the kernel memory and invoke the
  92    correct parsers on it, ensuring that when the program runs, all
  93    known kernel structures are recursively reached and loaded in.
  94 *)
  95
  96 (** {2 Field classification} *)
  97
  98 type f_class = ShapeField | ContentField
  99
 100 val classify_field : string list -> Pahole_parser.f_type -> f_class
 101   (** [classify_field names field] classifies a field as either
 102       a shape field or a content field.  [names] is a list of
 103       all kernel structures that we care about. *)
 104
 105 (** {2 Minimization of shape field structures and content field structures} *)
 106
 107 type shape_field_struct = {
 108   sf_i : int;                           (** Unique number. *)
 109   sf_name : string;                     (** Structure name in output. *)
 110   sf_fields : Pahole_parser.field list; (** Shape fields. *)
 111 }
 112     (** The type of a shape field structure. *)
 113
 114 and content_field_struct = {
 115   cf_i : int;                           (** Unique number. *)
 116   cf_name : string;                     (** Structure name in output. *)
 117   cf_fields : Pahole_parser.field list; (** Content fields. *)
 118 }
 119     (** The type of a content field structure. *)
 120
 121 type sfhash = (string, shape_field_struct) Hashtbl.t
 122     (** Hash of kernel version to the shape field structure. *)
 123
 124 val minimize_shape_field_structs :
 125   string -> string list ->
 126   (Pahole_parser.info * Pahole_parser.structure) list ->
 127   shape_field_struct list * sfhash
 128     (** [minimize_shape_field_structs struct_name names kernels] returns
 129         a minimized list of shape field structures
 130         (a hash table of kernel version to {!shape_field_struct}).
 131
 132         [struct_name] is the name of the structure.
 133
 134         [names] is the list of interesting kernel structures. *)
 135
 136 type cfhash = (string, content_field_struct) Hashtbl.t
 137     (** Hash of kernel version to the content field structure. *)
 138
 139 val minimize_content_field_structs :
 140   string -> string list ->
 141   (Pahole_parser.info * Pahole_parser.structure) list ->
 142   content_field_struct list * cfhash
 143     (** [minimize_content_field_structs struct_name names kernels] returns
 144         a minimized list of content field structures
 145         (a hash table of kernel version to {!content_field_struct}).
 146
 147         [struct_name] is the name of the structure.
 148
 149         [names] is the list of interesting kernel structures. *)
 150
 151 (** {2 Minimization of parsers} *)
 152
 153 type parser_ (* parser is a reserved word *) = {
 154   pa_i : int;                           (** Unique number. *)
 155   pa_name : string;                     (** Parser function name in output. *)
 156   (* The input to the parser: *)
 157   pa_endian : Bitstring.endian;         (** Default field endianness. *)
 158   pa_structure : Pahole_parser.structure; (** Original structure. *)
 159   (* The output of the parser: *)
 160   pa_shape_field_struct : shape_field_struct;
 161   pa_content_field_struct : content_field_struct;
 162 }
 163     (** The type of a parser. *)
 164
 165 type pahash = (string, parser_) Hashtbl.t
 166     (** Hash of the kernel version to the parser. *)
 167
 168 val minimize_parsers :
 169   string ->
 170   (Pahole_parser.info * Pahole_parser.structure) list ->
 171   sfhash -> cfhash ->
 172   parser_ list * pahash
 173     (** [minimize_parsers struct_name kernels sfhash cfhash] returns
 174         a minimized list of parsers (a hash table of kernel version
 175         to {!parser_}).
 176
 177         [sfhash] and [cfhash] are the kernel version -> shape/content
 178         field struct hashes returned by a previous call to
 179         {!minimize_shape_field_structs} and {!minimize_content_field_structs}
 180         respectively. *)