Add memory reporting infrastructure and use it to measure the display list.

This changeset implements the beginnings of fine-grained measurement of
Servo's data structures.

- It adds a new `SizeOf` trait, which is used to measure the memory used
  by heap data structures, and implements it for some std types: Box,
  String, Option, Arc, Vec, and DList.

- It adds a new `MemoryReporter` trait which is used to report memory
  measurements from other threads to the memory profiler. Reporters are
  registered and unregistered with the memory profiler, and the memory
  profiler makes measurement requests of reporters when necessary.

- It plumbs a MemoryProfilerChan through to the layout task so it can
  register a memory reporter.

- It implements the `SizeOf` trait for `DisplayList` and associated
  types, and adds a memory reporter that uses it.

The display list hits 14.77 MiB when viewing
tests/html/perf-rainbow.html, and 2.51 MiB when viewing the Guardians of
the Galaxy Wikipedia page from servo-static-suite. Example output:

  0.29: display-list::http://www.reddit.com/
  0.00: display-list::http://static.adzerk.net/reddit/ads.html?sr=-reddit.com,loggedout&bust2#http://www.reddit.com
  0.00: display-list::http://www.reddit.com/static/createadframe.html

There are a number of FIXME comments indicating sub-optimal things. This
is a big enough change for now that doing them as follow-ups seems best.

1 files changed, 249 insertions, 6 deletions

diff --git a/components/util/memory.rs b/components/util/memory.rs
index 6327a6e01f9..e72873872f8 100644
--- a/components/util/memory.rs
+++ b/components/util/memory.rs
@@ -6,20 +6,175 @@
 
 use libc::{c_char,c_int,c_void,size_t};
 use std::borrow::ToOwned;
+use std::collections::{DList, HashMap};
 use std::ffi::CString;
 #[cfg(target_os = "linux")]
 use std::iter::AdditiveIterator;
 use std::old_io::timer::sleep;
 #[cfg(target_os="linux")]
 use std::old_io::File;
-use std::mem::size_of;
+use std::mem::{size_of, transmute};
 use std::ptr::null_mut;
+use std::sync::Arc;
 use std::sync::mpsc::{Sender, channel, Receiver};
 use std::time::duration::Duration;
 use task::spawn_named;
 #[cfg(target_os="macos")]
 use task_info::task_basic_info::{virtual_size,resident_size};
 
+extern {
+    // Get the size of a heap block.
+    //
+    // Ideally Rust would expose a function like this in std::rt::heap, which would avoid the
+    // jemalloc dependence.
+    //
+    // The C prototype is `je_malloc_usable_size(JEMALLOC_USABLE_SIZE_CONST void *ptr)`. On some
+    // platforms `JEMALLOC_USABLE_SIZE_CONST` is `const` and on some it is empty. But in practice
+    // this function doesn't modify the contents of the block that `ptr` points to, so we use
+    // `*const c_void` here.
+    fn je_malloc_usable_size(ptr: *const c_void) -> size_t;
+}
+
+// A wrapper for je_malloc_usable_size that handles `EMPTY` and returns `usize`.
+pub fn heap_size_of(ptr: *const c_void) -> usize {
+    if ptr == ::std::rt::heap::EMPTY as *const c_void {
+        0
+    } else {
+        unsafe { je_malloc_usable_size(ptr) as usize }
+    }
+}
+
+// The simplest trait for measuring the size of heap data structures. More complex traits that
+// return multiple measurements -- e.g. measure text separately from images -- are also possible,
+// and should be used when appropriate.
+//
+// FIXME(njn): it would be nice to be able to derive this trait automatically, given that
+// implementations are mostly repetitive and mechanical.
+//
+pub trait SizeOf {
+    /// Measure the size of any heap-allocated structures that hang off this value, but not the
+    /// space taken up by the value itself (i.e. what size_of::<T> measures, more or less); that
+    /// space is handled by the implementation of SizeOf for Box<T> below.
+    fn size_of_excluding_self(&self) -> usize;
+}
+
+// There are two possible ways to measure the size of `self` when it's on the heap: compute it
+// (with `::std::rt::heap::usable_size(::std::mem::size_of::<T>(), 0)`) or measure it directly
+// using the heap allocator (with `heap_size_of`). We do the latter, for the following reasons.
+//
+// * The heap allocator is the true authority for the sizes of heap blocks; its measurement is
+//   guaranteed to be correct. In comparison, size computations are error-prone. (For example, the
+//   `rt::heap::usable_size` function used in some of Rust's non-default allocator implementations
+//   underestimate the true usable size of heap blocks, which is safe in general but would cause
+//   under-measurement here.)
+//
+// * If we measure something that isn't a heap block, we'll get a crash. This keeps us honest,
+//   which is important because unsafe code is involved and this can be gotten wrong.
+//
+// However, in the best case, the two approaches should give the same results.
+//
+impl<T: SizeOf> SizeOf for Box<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        // Measure size of `self`.
+        heap_size_of(&**self as *const T as *const c_void) + (**self).size_of_excluding_self()
+    }
+}
+
+impl SizeOf for String {
+    fn size_of_excluding_self(&self) -> usize {
+        heap_size_of(self.as_ptr() as *const c_void)
+    }
+}
+
+impl<T: SizeOf> SizeOf for Option<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        match *self {
+            None => 0,
+            Some(ref x) => x.size_of_excluding_self()
+        }
+    }
+}
+
+impl<T: SizeOf> SizeOf for Arc<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        (**self).size_of_excluding_self()
+    }
+}
+
+impl<T: SizeOf> SizeOf for Vec<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        heap_size_of(self.as_ptr() as *const c_void) +
+            self.iter().fold(0, |n, elem| n + elem.size_of_excluding_self())
+    }
+}
+
+// FIXME(njn): We can't implement SizeOf accurately for DList because it requires access to the
+// private Node type. Eventually we'll want to add SizeOf (or equivalent) to Rust itself. In the
+// meantime, we use the dirty hack of transmuting DList into an identical type (DList2) and
+// measuring that.
+impl<T: SizeOf> SizeOf for DList<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        let list2: &DList2<T> = unsafe { transmute(self) };
+        list2.size_of_excluding_self()
+    }
+}
+
+struct DList2<T> {
+    _length: usize,
+    list_head: Link<T>,
+    _list_tail: Rawlink<Node<T>>,
+}
+
+type Link<T> = Option<Box<Node<T>>>;
+
+struct Rawlink<T> {
+    _p: *mut T,
+}
+
+struct Node<T> {
+    next: Link<T>,
+    _prev: Rawlink<Node<T>>,
+    value: T,
+}
+
+impl<T: SizeOf> SizeOf for Node<T> {
+    // Unlike most size_of_excluding_self() functions, this one does *not* measure descendents.
+    // Instead, DList2<T>::size_of_excluding_self() handles that, so that it can use iteration
+    // instead of recursion, which avoids potentially blowing the stack.
+    fn size_of_excluding_self(&self) -> usize {
+        self.value.size_of_excluding_self()
+    }
+}
+
+impl<T: SizeOf> SizeOf for DList2<T> {
+    fn size_of_excluding_self(&self) -> usize {
+        let mut size = 0;
+        let mut curr: &Link<T> = &self.list_head;
+        while curr.is_some() {
+            size += (*curr).size_of_excluding_self();
+            curr = &curr.as_ref().unwrap().next;
+        }
+        size
+    }
+}
+
+// This is a basic sanity check. If the representation of DList changes such that it becomes a
+// different size to DList2, this will fail at compile-time.
+#[allow(dead_code)]
+unsafe fn dlist2_check() {
+    transmute::<DList<i32>, DList2<i32>>(panic!());
+}
+
+// Currently, types that implement the Drop type are larger than those that don't. Because DList
+// implements Drop, DList2 must also so that dlist2_check() doesn't fail.
+#[unsafe_destructor]
+impl<T> Drop for DList2<T> {
+    fn drop(&mut self) {}
+}
+
+//---------------------------------------------------------------------------
+
+#[derive(Clone)]
 pub struct MemoryProfilerChan(pub Sender<MemoryProfilerMsg>);
 
 impl MemoryProfilerChan {
@@ -29,15 +184,60 @@ impl MemoryProfilerChan {
     }
 }
 
+pub struct MemoryReport {
+    /// The identifying name for this report.
+    pub name: String,
+
+    /// The size, in bytes.
+    pub size: u64,
+}
+
+/// A channel through which memory reports can be sent.
+#[derive(Clone)]
+pub struct MemoryReportsChan(pub Sender<Vec<MemoryReport>>);
+
+impl MemoryReportsChan {
+    pub fn send(&self, report: Vec<MemoryReport>) {
+        let MemoryReportsChan(ref c) = *self;
+        c.send(report).unwrap();
+    }
+}
+
+/// A memory reporter is capable of measuring some data structure of interest. Because it needs
+/// to be passed to and registered with the MemoryProfiler, it's typically a "small" (i.e. easily
+/// cloneable) value that provides access to a "large" data structure, e.g. a channel that can
+/// inject a request for measurements into the event queue associated with the "large" data
+/// structure.
+pub trait MemoryReporter {
+    /// Collect one or more memory reports. Returns true on success, and false on failure.
+    fn collect_reports(&self, reports_chan: MemoryReportsChan) -> bool;
+}
+
+/// Messages that can be sent to the memory profiler thread.
 pub enum MemoryProfilerMsg {
-    /// Message used to force print the memory profiling metrics.
+    /// Register a MemoryReporter with the memory profiler. The String is only used to identify the
+    /// reporter so it can be unregistered later. The String must be distinct from that used by any
+    /// other registered reporter otherwise a panic will occur.
+    RegisterMemoryReporter(String, Box<MemoryReporter + Send>),
+
+    /// Unregister a MemoryReporter with the memory profiler. The String must match the name given
+    /// when the reporter was registered. If the String does not match the name of a registered
+    /// reporter a panic will occur.
+    UnregisterMemoryReporter(String),
+
+    /// Triggers printing of the memory profiling metrics.
     Print,
+
     /// Tells the memory profiler to shut down.
     Exit,
 }
 
 pub struct MemoryProfiler {
+    /// The port through which messages are received.
     pub port: Receiver<MemoryProfilerMsg>,
+
+    /// Registered memory reporters.
+    reporters: HashMap<String, Box<MemoryReporter + Send>>,
 }
 
 impl MemoryProfiler {
@@ -57,7 +257,7 @@ impl MemoryProfiler {
                 });
                 // Spawn the memory profiler.
                 spawn_named("Memory profiler".to_owned(), move || {
-                    let memory_profiler = MemoryProfiler::new(port);
+                    let mut memory_profiler = MemoryProfiler::new(port);
                     memory_profiler.start();
                 });
             }
@@ -80,11 +280,12 @@ impl MemoryProfiler {
 
     pub fn new(port: Receiver<MemoryProfilerMsg>) -> MemoryProfiler {
         MemoryProfiler {
-            port: port
+            port: port,
+            reporters: HashMap::new(),
         }
     }
 
-    pub fn start(&self) {
+    pub fn start(&mut self) {
         loop {
             match self.port.recv() {
                Ok(msg) => {
@@ -97,12 +298,33 @@ impl MemoryProfiler {
         }
     }
 
-    fn handle_msg(&self, msg: MemoryProfilerMsg) -> bool {
+    fn handle_msg(&mut self, msg: MemoryProfilerMsg) -> bool {
         match msg {
+            MemoryProfilerMsg::RegisterMemoryReporter(name, reporter) => {
+                // Panic if it has already been registered.
+                let name_clone = name.clone();
+                match self.reporters.insert(name, reporter) {
+                    None => true,
+                    Some(_) =>
+                        panic!(format!("RegisterMemoryReporter: '{}' name is already in use",
+                                       name_clone)),
+                }
+            },
+
+            MemoryProfilerMsg::UnregisterMemoryReporter(name) => {
+                // Panic if it hasn't previously been registered.
+                match self.reporters.remove(&name) {
+                    Some(_) => true,
+                    None =>
+                        panic!(format!("UnregisterMemoryReporter: '{}' name is unknown", &name)),
+                }
+            },
+
             MemoryProfilerMsg::Print => {
                 self.handle_print_msg();
                 true
             },
+
             MemoryProfilerMsg::Exit => false
         }
     }
@@ -120,8 +342,11 @@ impl MemoryProfiler {
     }
 
     fn handle_print_msg(&self) {
+
         println!("{:12}: {}", "_size (MiB)_", "_category_");
 
+        // Collect global measurements from the OS and heap allocators.
+
         // Virtual and physical memory usage, as reported by the OS.
         MemoryProfiler::print_measurement("vsize", get_vsize());
         MemoryProfiler::print_measurement("resident", get_resident());
@@ -154,6 +379,24 @@ impl MemoryProfiler {
         MemoryProfiler::print_measurement("jemalloc-heap-mapped",
                                           get_jemalloc_stat("stats.mapped"));
 
+        // Collect reports from memory reporters.
+
+        // This serializes the report-gathering. It might be worth creating a new scoped thread for
+        // each reporter once we have enough of them.
+        //
+        // If anything goes wrong with a reporter, we just skip it.
+        for reporter in self.reporters.values() {
+            let (chan, port) = channel();
+            if reporter.collect_reports(MemoryReportsChan(chan)) {
+                if let Ok(reports) = port.recv() {
+                    for report in reports {
+                        MemoryProfiler::print_measurement(report.name.as_slice(),
+                                                          Some(report.size));
+                    }
+                }
+            }
+        }
+
         println!("");
     }
 }