df876bac1ff1ffb6bcfddfef2c13b64a83877fb8
[virt-mem.git] / ps / virt_ps.ml
1 (* Memory info for virtual domains.
2    (C) Copyright 2008 Richard W.M. Jones, Red Hat Inc.
3    http://libvirt.org/
4
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2 of the License, or
8    (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18  *)
19
20 open Printf
21
22 open Virt_mem_gettext.Gettext
23 open Virt_mem_utils
24 open Virt_mem_mmap
25
26 (* The implementation of 'ps' has gone through a number of complete
27  * rewrites.  This explains the "leading theories" of how to implement
28  * this.  Probably some sort of hybrid method is the way to go.
29  *
30  * General comments: The init_task ksym points to the initial
31  * task_struct (PID 1, init).  Out from this init task_struct
32  * we find linked lists (struct list_head) which cover all
33  * tasks and subsets of the tasks (eg. parent/children).
34  * So if we have init_task and we know what the task_struct
35  * looks like, then we can follow these chains of pointers
36  * to find all processes in the kernel.
37  *
38  * task_struct varies greatly depending on: word size, kernel
39  * version, CONFIG_* settings, and vendor/additional patches.
40  *
41  * (Theory 1) Precompiled task_struct.  We can easily and reliably
42  * determine the Linux kernel version (see virt-uname).  In
43  * theory we could compile a list of known kernel versions,
44  * check out their sources beforehand, and find the absolute
45  * layout of the task_struct (eg. using CIL).  This method would
46  * only work for known kernel versions, but has the advantage
47  * that all fields in the task_struct would be known.
48  *
49  * (Theory 2) Fuzzy matched task_struct.  The task_struct has
50  * a certain internal structure which is stable even over many
51  * kernel revisions.  For example, groups of pointers always
52  * occur together.  We search through init_task looking for
53  * these characteristic features and where a pointer is found
54  * to another task_struct we search that (recursively) on the
55  * assumption that those contain the same features at the same
56  * location.  This works well for pointers, but not so well for
57  * finding other fields (eg. uids, process name, etc).  We can
58  * defray the cost of searches by caching the results between
59  * runs.
60  *)
61
62 (* This accumulator stores a map of task_struct address to
63  * task_struct content.  It can also store the address of a
64  * task_struct which isn't fully parsed yet.
65  *   key:   address (int64)
66  *   value: task_struct option (None if not parsed yet)
67  *)
68 type task_struct = {
69   ts_addr : int64;
70 }
71
72 module Accum = struct
73   include Map.Make (Int64)
74
75   let contains_addr accum addr = mem addr accum
76   let add_address accum addr = add addr None accum
77   let add_task_struct accum addr ts = add addr (Some ts) accum
78 end
79
80 exception ShapeError of int
81
82 (* Parse (recursively) all task_structs, starting at init_task.
83  *
84  * Either returns an accumulator of task_structs, or raises an
85  * exception.
86  *
87  * On failure, the caller can try again with a different shape.
88  * The exception gives some information back to the caller about
89  * where the match failed, allowing faster, directed searches.
90  *)
91 let get_task_struct debug mem ((ws,e) as wse) ((n1,n2) as shape)
92     addr accum =
93
94   (* The 'struct list_head', the standard double-linked list used
95    * by Linux, contains next and prev pointers.  However these point
96    * not to the beginning of the struct, but to the offset of the
97    * list_head within the struct.  This function adjusts the pointer
98    * to get back to the beginning of the struct.
99    *)
100   let container_of addr bitoffset =
101     if addr <> 0L then (
102       let offset = Int64.of_int (bitoffset lsr 3) in
103       addr -^ offset
104     ) else 0L
105   in
106
107   (* Do get_task_struct as a recursive subfunction so we don't have
108    * to pass around all the fixed arguments on the stack.
109    *)
110   let rec get_task_struct ~i addr accum =
111     if Accum.contains_addr accum addr then accum
112     else (
113       (* NOTE: The order of the following three statements is crucial
114        * to avoid cycles and malicious guests.  Do not change it!
115        *)
116       let bits =
117         try Bitstring.bitstring_of_string (get_bytes mem addr (4096*8))
118         with Invalid_argument "get_bytes" -> raise (ShapeError i) in
119       let accum = Accum.add_address accum addr in
120       let accum = ref accum in
121
122       if debug then
123         eprintf "trying to match task_struct, i=%d %Lx\n%!" i addr;
124
125       bitmatch bits with
126       | { _ : n1*ws : bitstring;    (* Ignore start of task_struct. *)
127
128           (* struct list_head tasks *)
129           tasks_next : ws : endian(e),
130             save_offset_to (offset),
131             bind (let addr = container_of tasks_next offset in
132               eprintf "offset = %d, tasks_next = %Lx, addr = %Lx\n"
133                 offset tasks_next addr;
134                   accum := get_task_struct ~i:1 addr !accum;
135                   addr);
136           tasks_prev : ws : endian(e),
137             bind (let addr = container_of tasks_prev offset in
138               eprintf "offset = %d, tasks_prev = %Lx, addr = %Lx\n"
139                 offset tasks_prev addr;
140                   accum := get_task_struct ~i:1 addr !accum;
141                   addr);
142
143           _ : n2*ws : bitstring;
144
145           (* struct task_struct *parent *)
146           parent : ws : endian(e),
147             bind (let addr = parent in
148                   accum := get_task_struct ~i:2 addr !accum;
149                   addr);
150
151           (* struct list_head children *)
152           children_next : ws : endian(e),
153             save_offset_to (offset),
154             bind (let addr = container_of children_next offset in
155                   accum := get_task_struct ~i:2 addr !accum;
156                   addr);
157
158           children_prev : ws : endian(e),
159             bind (let addr = container_of children_prev offset in
160                   accum := get_task_struct ~i:2 addr !accum;
161                   addr);
162
163           (* struct list_head sibling *)
164           sibling_next : ws : endian(e),
165             save_offset_to (offset),
166             bind (let addr = container_of sibling_next offset in
167                   accum := get_task_struct ~i:2 addr !accum;
168                   addr);
169
170           sibling_prev : ws : endian(e),
171             bind (let addr = container_of sibling_prev offset in
172                   accum := get_task_struct ~i:2 addr !accum;
173                   addr);
174
175           (* struct task_struct *group_leader *)
176           group_leader : ws : endian(e),
177             bind (let addr = group_leader in
178                   accum := get_task_struct ~i:2 addr !accum;
179                   addr)
180         } ->
181           (* Successful match, so return the updated accumulator. *)
182           let accum = !accum in
183           let accum = Accum.add_task_struct accum addr { ts_addr = addr } in
184           accum
185
186       | { _ } ->
187           (* Unsuccessful match, throw an exception. *)
188           raise (ShapeError (-1))
189     )
190   in
191   get_task_struct ~i:0 addr accum
192
193 (* This is the directed search function. *)
194 let search debug mem lookup_ksym =
195   let ws = get_wordsize mem in
196   let ws = match ws with W32 -> 32 | W64 -> 64 in
197   let e = get_endian mem in
198   let wse = ws, e in
199
200   let init_task =
201     try lookup_ksym "init_task"
202     with Not_found ->
203       eprintf "virt-ps: lookup_ksym of init_task failed\n";
204       exit 1 in
205
206   let accum = Accum.empty in
207
208   let rec loop n1 n2 =
209     try
210       if debug then eprintf "search: trying (%d, %d)\n" n1 n2;
211       let ts = get_task_struct debug mem wse (n1, n2) init_task accum in
212       if debug then eprintf "search: success (%d, %d)\n" n1 n2;
213       ts
214     with
215     | ShapeError ((-1|0|1) as i) ->
216         if debug then eprintf "search: ShapeError %d\n" i;
217         loop (n1+1) n2
218     | ShapeError 2 ->
219         if debug then eprintf "search: ShapeError 2\n";
220         loop n1 (n2+1)
221   in
222   let ts = loop 0 0 in
223   ()
224
225 let run debug (_, _, _, mem, lookup_ksym, _) =
226   search debug mem lookup_ksym
227
228 let summary = s_"list processes in virtual machine"
229 let description = s_"\
230 virt-ps prints a process listing for virtual machines running under
231 libvirt."
232
233 let () = Virt_mem.register "ps" summary description ~run