Add PUBLIC support to SourceLineResolver (resolve function names in Windows

system libraries) (#53)
StackFrame::function_base is not populated (#49)
r=bryner

http://groups.google.com/group/airbag-dev/browse_thread/thread/a17d35348e7027bb


git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@43 4c0a9323-5329-0410-9bdc-e9ce6186880e

15 files changed, 637 insertions, 31 deletions

diff --git a/Makefile.am b/Makefile.am
index faab0a14..2674f02c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -56,6 +56,8 @@ src_libairbag_la_SOURCES = \
 	src/google/stack_frame.h \
 	src/google/stack_frame_cpu.h \
 	src/google/symbol_supplier.h \
+	src/processor/address_map.h \
+	src/processor/address_map-inl.h \
 	src/processor/call_stack.cc \
 	src/processor/contained_range_map.h \
 	src/processor/contained_range_map-inl.h \
@@ -88,6 +90,7 @@ bin_PROGRAMS = \
 
 ## Tests
 check_PROGRAMS = \
+	src/processor/address_map_unittest \
 	src/processor/contained_range_map_unittest \
 	src/processor/minidump_processor_unittest \
 	src/processor/postfix_evaluator_unittest \
@@ -106,6 +109,9 @@ check_SCRIPTS = \
 TESTS = $(check_PROGRAMS) $(check_SCRIPTS)
 TESTS_ENVIRONMENT =
 
+src_processor_address_map_unittest_SOURCES = \
+	src/processor/address_map_unittest.cc
+
 src_processor_contained_range_map_unittest_SOURCES = \
 	src/processor/contained_range_map_unittest.cc
 
diff --git a/Makefile.in b/Makefile.in
index fd15374d..88bfdad9 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -70,7 +70,8 @@ build_triplet = @build@
 host_triplet = @host@
 bin_PROGRAMS = src/processor/minidump_dump$(EXEEXT) \
 	src/processor/minidump_stackwalk$(EXEEXT)
-check_PROGRAMS = src/processor/contained_range_map_unittest$(EXEEXT) \
+check_PROGRAMS = src/processor/address_map_unittest$(EXEEXT) \
+	src/processor/contained_range_map_unittest$(EXEEXT) \
 	src/processor/minidump_processor_unittest$(EXEEXT) \
 	src/processor/postfix_evaluator_unittest$(EXEEXT) \
 	src/processor/range_map_unittest$(EXEEXT) \
@@ -118,6 +119,11 @@ binPROGRAMS_INSTALL = $(INSTALL_PROGRAM)
 @SELFTEST_TRUE@am__EXEEXT_1 =  \
 @SELFTEST_TRUE@	src/processor/stackwalker_selftest$(EXEEXT)
 PROGRAMS = $(bin_PROGRAMS) $(noinst_PROGRAMS)
+am_src_processor_address_map_unittest_OBJECTS =  \
+	src/processor/address_map_unittest.$(OBJEXT)
+src_processor_address_map_unittest_OBJECTS =  \
+	$(am_src_processor_address_map_unittest_OBJECTS)
+src_processor_address_map_unittest_LDADD = $(LDADD)
 am_src_processor_contained_range_map_unittest_OBJECTS =  \
 	src/processor/contained_range_map_unittest.$(OBJEXT)
 src_processor_contained_range_map_unittest_OBJECTS =  \
@@ -193,6 +199,7 @@ CCLD = $(CC)
 LINK = $(LIBTOOL) --tag=CC --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \
 	$(AM_LDFLAGS) $(LDFLAGS) -o $@
 SOURCES = $(src_libairbag_la_SOURCES) \
+	$(src_processor_address_map_unittest_SOURCES) \
 	$(src_processor_contained_range_map_unittest_SOURCES) \
 	$(src_processor_minidump_dump_SOURCES) \
 	$(src_processor_minidump_processor_unittest_SOURCES) \
@@ -202,6 +209,7 @@ SOURCES = $(src_libairbag_la_SOURCES) \
 	$(src_processor_source_line_resolver_unittest_SOURCES) \
 	$(src_processor_stackwalker_selftest_SOURCES)
 DIST_SOURCES = $(src_libairbag_la_SOURCES) \
+	$(src_processor_address_map_unittest_SOURCES) \
 	$(src_processor_contained_range_map_unittest_SOURCES) \
 	$(src_processor_minidump_dump_SOURCES) \
 	$(src_processor_minidump_processor_unittest_SOURCES) \
@@ -348,6 +356,8 @@ src_libairbag_la_SOURCES = \
 	src/google/stack_frame.h \
 	src/google/stack_frame_cpu.h \
 	src/google/symbol_supplier.h \
+	src/processor/address_map.h \
+	src/processor/address_map-inl.h \
 	src/processor/call_stack.cc \
 	src/processor/contained_range_map.h \
 	src/processor/contained_range_map-inl.h \
@@ -377,6 +387,9 @@ check_SCRIPTS = \
 
 TESTS = $(check_PROGRAMS) $(check_SCRIPTS)
 TESTS_ENVIRONMENT = 
+src_processor_address_map_unittest_SOURCES = \
+	src/processor/address_map_unittest.cc
+
 src_processor_contained_range_map_unittest_SOURCES = \
 	src/processor/contained_range_map_unittest.cc
 
@@ -592,6 +605,12 @@ clean-noinstPROGRAMS:
 	  echo " rm -f $$p $$f"; \
 	  rm -f $$p $$f ; \
 	done
+src/processor/address_map_unittest.$(OBJEXT):  \
+	src/processor/$(am__dirstamp) \
+	src/processor/$(DEPDIR)/$(am__dirstamp)
+src/processor/address_map_unittest$(EXEEXT): $(src_processor_address_map_unittest_OBJECTS) $(src_processor_address_map_unittest_DEPENDENCIES) src/processor/$(am__dirstamp)
+	@rm -f src/processor/address_map_unittest$(EXEEXT)
+	$(CXXLINK) $(src_processor_address_map_unittest_LDFLAGS) $(src_processor_address_map_unittest_OBJECTS) $(src_processor_address_map_unittest_LDADD) $(LIBS)
 src/processor/contained_range_map_unittest.$(OBJEXT):  \
 	src/processor/$(am__dirstamp) \
 	src/processor/$(DEPDIR)/$(am__dirstamp)
@@ -642,6 +661,7 @@ src/processor/stackwalker_selftest$(EXEEXT): $(src_processor_stackwalker_selftes
 
 mostlyclean-compile:
 	-rm -f *.$(OBJEXT)
+	-rm -f src/processor/address_map_unittest.$(OBJEXT)
 	-rm -f src/processor/call_stack.$(OBJEXT)
 	-rm -f src/processor/call_stack.lo
 	-rm -f src/processor/contained_range_map_unittest.$(OBJEXT)
@@ -668,6 +688,7 @@ mostlyclean-compile:
 distclean-compile:
 	-rm -f *.tab.c
 
+@AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/address_map_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/call_stack.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/contained_range_map_unittest.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@src/processor/$(DEPDIR)/minidump.Plo@am__quote@
diff --git a/src/common/windows/pdb_source_line_writer.cc b/src/common/windows/pdb_source_line_writer.cc
index 5e0c4a2e..91c95922 100644
--- a/src/common/windows/pdb_source_line_writer.cc
+++ b/src/common/windows/pdb_source_line_writer.cc
@@ -483,7 +483,7 @@ bool PDBSourceLineWriter::GetSymbolFunctionName(IDiaSymbol *function,
       } else if (*name[0] == '_') {
         // This symbol's name is encoded according to the cdecl rules.  The
         // name doesn't end in a '@' character followed by a decimal positive
-        // nteger, so it's not a stdcall name.  Strip off the leading
+        // integer, so it's not a stdcall name.  Strip off the leading
         // underscore.
         wcsncpy_s(*name, length, *name + 1, length - 1);
       }
diff --git a/src/google/stack_frame.h b/src/google/stack_frame.h
index 43b52dd0..563106e4 100644
--- a/src/google/stack_frame.h
+++ b/src/google/stack_frame.h
@@ -45,7 +45,8 @@ struct StackFrame {
         function_base(),
         function_name(),
         source_file_name(),
-        source_line() {}
+        source_line(),
+        source_line_base() {}
   virtual ~StackFrame() {}
 
   // The program counter location as an absolute virtual address.  For the
@@ -74,6 +75,10 @@ struct StackFrame {
   // The (1-based) source line number, may be omitted if debug symbols are
   // not available.
   int source_line;
+
+  // The start address of the source line, may be omitted if debug symbols
+  // are not available.
+  u_int64_t source_line_base;
 };
 
 }  // namespace google_airbag
diff --git a/src/processor/address_map-inl.h b/src/processor/address_map-inl.h
new file mode 100644
index 00000000..5cff4562
--- /dev/null
+++ b/src/processor/address_map-inl.h
@@ -0,0 +1,86 @@
+// Copyright (c) 2006, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// address_map-inl.h: Address map implementation.
+//
+// See address_map.h for documentation.
+//
+// Author: Mark Mentovai
+
+#ifndef PROCESSOR_ADDRESS_MAP_INL_H__
+#define PROCESSOR_ADDRESS_MAP_INL_H__
+
+#include "processor/address_map.h"
+
+namespace google_airbag {
+
+template<typename AddressType, typename EntryType>
+bool AddressMap<AddressType, EntryType>::Store(const AddressType &address,
+                                               const EntryType &entry) {
+  // Ensure that the specified address doesn't conflict with something already
+  // in the map.
+  if (map_.find(address) != map_.end())
+    return false;
+
+  map_.insert(MapValue(address, entry));
+  return true;
+}
+
+template<typename AddressType, typename EntryType>
+bool AddressMap<AddressType, EntryType>::Retrieve(
+    const AddressType &address,
+    EntryType *entry, AddressType *entry_address) const {
+  if (!entry)
+    return false;
+
+  // upper_bound gives the first element whose key is greater than address,
+  // but we want the first element whose key is less than or equal to address.
+  // Decrement the iterator to get there, but not if the upper_bound already
+  // points to the beginning of the map - in that case, address is lower than
+  // the lowest stored key, so return false.
+  MapConstIterator iterator = map_.upper_bound(address);
+  if (iterator == map_.begin())
+    return false;
+  --iterator;
+
+  *entry = iterator->second;
+  if (entry_address)
+    *entry_address = iterator->first;
+
+  return true;
+}
+
+template<typename AddressType, typename EntryType>
+void AddressMap<AddressType, EntryType>::Clear() {
+  map_.clear();
+}
+
+}  // namespace google_airbag
+
+#endif  // PROCESSOR_ADDRESS_MAP_INL_H__
diff --git a/src/processor/address_map.h b/src/processor/address_map.h
new file mode 100644
index 00000000..b38da24b
--- /dev/null
+++ b/src/processor/address_map.h
@@ -0,0 +1,80 @@
+// Copyright (c) 2006, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// address_map.h: Address maps.
+//
+// An address map contains a set of objects keyed by address.  Objects are
+// retrieved from the map by returning the object with the highest key less
+// than or equal to the lookup key.
+//
+// Author: Mark Mentovai
+
+#ifndef PROCESSOR_ADDRESS_MAP_H__
+#define PROCESSOR_ADDRESS_MAP_H__
+
+#include <map>
+
+namespace google_airbag {
+
+template<typename AddressType, typename EntryType>
+class AddressMap {
+ public:
+  AddressMap() : map_() {}
+
+  // Inserts an entry into the map.  Returns false without storing the entry
+  // if an entry is already stored in the map at the same address as specified
+  // by the address argument.
+  bool Store(const AddressType &address, const EntryType &entry);
+
+  // Locates the entry stored at the highest address less than or equal to
+  // the address argument.  If there is no such range, or if there is a
+  // parameter error, returns false.  The entry is returned in entry.  If
+  // entry_address is not NULL, it will be set to the address that the entry
+  // was stored at.
+  bool Retrieve(const AddressType &address,
+                EntryType *entry, AddressType *entry_address) const;
+
+  // Empties the address map, restoring it to the same state as when it was
+  // initially created.
+  void Clear();
+
+ private:
+  // Convenience types.
+  typedef std::map<AddressType, EntryType> AddressToEntryMap;
+  typedef typename AddressToEntryMap::const_iterator MapConstIterator;
+  typedef typename AddressToEntryMap::value_type MapValue;
+
+  // Maps the address of each entry to an EntryType.
+  AddressToEntryMap map_;
+};
+
+}  // namespace google_airbag
+
+#endif  // PROCESSOR_ADDRESS_MAP_H__
+
diff --git a/src/processor/address_map_unittest.cc b/src/processor/address_map_unittest.cc
new file mode 100644
index 00000000..01d52166
--- /dev/null
+++ b/src/processor/address_map_unittest.cc
@@ -0,0 +1,190 @@
+// Copyright (c) 2006, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// address_map_unittest.cc: Unit tests for AddressMap.
+//
+// Author: Mark Mentovai
+
+#include <climits>
+#include <cstdio>
+
+#include "processor/address_map-inl.h"
+#include "processor/linked_ptr.h"
+
+#define ASSERT_TRUE(condition) \
+  if (!(condition)) { \
+    fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
+    return false; \
+  }
+
+#define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))
+
+#define ASSERT_EQ(e1, e2) ASSERT_TRUE((e1) == (e2))
+
+using google_airbag::AddressMap;
+using google_airbag::linked_ptr;
+
+// A CountedObject holds an int.  A global (not thread safe!) count of
+// allocated CountedObjects is maintained to help test memory management.
+class CountedObject {
+ public:
+  explicit CountedObject(int id) : id_(id) { ++count_; }
+  ~CountedObject() { --count_; }
+
+  static int count() { return count_; }
+  int id() const { return id_; }
+
+ private:
+  static int count_;
+  int id_;
+};
+
+int CountedObject::count_;
+
+typedef int AddressType;
+typedef AddressMap< AddressType, linked_ptr<CountedObject> > TestMap;
+
+static bool DoAddressMapTest() {
+  ASSERT_EQ(CountedObject::count(), 0);
+
+  TestMap test_map;
+  linked_ptr<CountedObject> entry;
+  AddressType address;
+
+  // Check that a new map is truly empty.
+  ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
+  ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
+  ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
+
+  // Check that Clear clears the map without leaking.
+  ASSERT_EQ(CountedObject::count(), 0);
+  ASSERT_TRUE(test_map.Store(1,
+      linked_ptr<CountedObject>(new CountedObject(0))));
+  ASSERT_TRUE(test_map.Retrieve(1, &entry, &address));
+  ASSERT_EQ(CountedObject::count(), 1);
+  test_map.Clear();
+  ASSERT_EQ(CountedObject::count(), 1);  // still holding entry in this scope
+
+  // Check that a cleared map is truly empty.
+  ASSERT_FALSE(test_map.Retrieve(0, &entry, &address));
+  ASSERT_FALSE(test_map.Retrieve(INT_MIN, &entry, &address));
+  ASSERT_FALSE(test_map.Retrieve(INT_MAX, &entry, &address));
+
+  // Check a single-element map.
+  ASSERT_TRUE(test_map.Store(10,
+      linked_ptr<CountedObject>(new CountedObject(1))));
+  ASSERT_FALSE(test_map.Retrieve(9, &entry, &address));
+  ASSERT_TRUE(test_map.Retrieve(10, &entry, &address));
+  ASSERT_EQ(CountedObject::count(), 1);
+  ASSERT_EQ(entry->id(), 1);
+  ASSERT_EQ(address, 10);
+  ASSERT_TRUE(test_map.Retrieve(11, &entry, &address));
+  ASSERT_FALSE(test_map.Retrieve(11, NULL, &address));  // parameter error
+  ASSERT_TRUE(test_map.Retrieve(11, &entry, NULL));     // NULL ok here
+
+  // Add some more elements.
+  ASSERT_TRUE(test_map.Store(5,
+      linked_ptr<CountedObject>(new CountedObject(2))));
+  ASSERT_EQ(CountedObject::count(), 2);
+  ASSERT_TRUE(test_map.Store(20,
+      linked_ptr<CountedObject>(new CountedObject(3))));
+  ASSERT_TRUE(test_map.Store(15,
+      linked_ptr<CountedObject>(new CountedObject(4))));
+  ASSERT_FALSE(test_map.Store(10,
+      linked_ptr<CountedObject>(new CountedObject(5))));  // already in map
+  ASSERT_TRUE(test_map.Store(16,
+      linked_ptr<CountedObject>(new CountedObject(6))));
+  ASSERT_TRUE(test_map.Store(14,
+      linked_ptr<CountedObject>(new CountedObject(7))));
+
+  // Nothing was stored with a key under 5.  Don't use ASSERT inside loops
+  // because it won't show exactly which key/entry/address failed.
+  for (AddressType key = 0; key < 5; ++key) {
+    if (test_map.Retrieve(key, &entry, &address)) {
+      fprintf(stderr,
+              "FAIL: retrieve %d expected false observed true @ %s:%d\n",
+              key, __FILE__, __LINE__);
+      return false;
+    }
+  }
+
+  // Check everything that was stored.
+  const int id_verify[] = { 0, 0, 0, 0, 0,    // unused
+                            2, 2, 2, 2, 2,    // 5 - 9
+                            1, 1, 1, 1, 7,    // 10 - 14
+                            4, 6, 6, 6, 6,    // 15 - 19
+                            3, 3, 3, 3, 3,    // 20 - 24
+                            3, 3, 3, 3, 3 };  // 25 - 29
+  const AddressType address_verify[] = {  0,  0,  0,  0,  0,    // unused
+                                          5,  5,  5,  5,  5,    // 5 - 9
+                                         10, 10, 10, 10, 14,    // 10 - 14
+                                         15, 16, 16, 16, 16,    // 15 - 19
+                                         20, 20, 20, 20, 20,    // 20 - 24
+                                         20, 20, 20, 20, 20 };  // 25 - 29
+
+  for (AddressType key = 5; key < 30; ++key) {
+    if (!test_map.Retrieve(key, &entry, &address)) {
+      fprintf(stderr,
+              "FAIL: retrieve %d expected true observed false @ %s:%d\n",
+              key, __FILE__, __LINE__);
+      return false;
+    }
+    if (entry->id() != id_verify[key]) {
+      fprintf(stderr,
+              "FAIL: retrieve %d expected entry %d observed %d @ %s:%d\n",
+              key, id_verify[key], entry->id(), __FILE__, __LINE__);
+      return false;
+    }
+    if (address != address_verify[key]) {
+      fprintf(stderr,
+              "FAIL: retrieve %d expected address %d observed %d @ %s:%d\n",
+              key, address_verify[key], address, __FILE__, __LINE__);
+      return false;
+    }
+  }
+
+  // The stored objects should still be in the map.
+  ASSERT_EQ(CountedObject::count(), 6);
+
+  return true;
+}
+
+static bool RunTests() {
+  if (!DoAddressMapTest())
+    return false;
+
+  // Leak check.
+  ASSERT_EQ(CountedObject::count(), 0);
+
+  return true;
+}
+
+int main(int argc, char **argv) {
+  return RunTests() ? 0 : 1;
+}
diff --git a/src/processor/minidump.cc b/src/processor/minidump.cc
index 6b33aeed..2d3dce81 100644
--- a/src/processor/minidump.cc
+++ b/src/processor/minidump.cc
@@ -1486,7 +1486,7 @@ MinidumpModule* MinidumpModuleList::GetModuleForAddress(u_int64_t address) {
     return NULL;
 
   unsigned int module_index;
-  if (!range_map_.RetrieveRange(address, &module_index))
+  if (!range_map_.RetrieveRange(address, &module_index, NULL, NULL))
     return NULL;
 
   return GetModuleAtIndex(module_index);
@@ -1616,7 +1616,7 @@ MinidumpMemoryRegion* MinidumpMemoryList::GetMemoryRegionForAddress(
     return NULL;
 
   unsigned int region_index;
-  if (!range_map_.RetrieveRange(address, &region_index))
+  if (!range_map_.RetrieveRange(address, &region_index, NULL, NULL))
     return NULL;
 
   return GetMemoryRegionAtIndex(region_index);
diff --git a/src/processor/range_map-inl.h b/src/processor/range_map-inl.h
index 5073a1fc..74ce8513 100644
--- a/src/processor/range_map-inl.h
+++ b/src/processor/range_map-inl.h
@@ -83,7 +83,8 @@ bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base,
 
 template<typename AddressType, typename EntryType>
 bool RangeMap<AddressType, EntryType>::RetrieveRange(
-    const AddressType &address, EntryType *entry) const {
+    const AddressType &address, EntryType *entry,
+    AddressType *entry_base, AddressType *entry_size) const {
   if (!entry)
     return false;
 
@@ -100,6 +101,42 @@ bool RangeMap<AddressType, EntryType>::RetrieveRange(
     return false;
 
   *entry = iterator->second.entry();
+  if (entry_base)
+    *entry_base = iterator->second.base();
+  if (entry_size)
+    *entry_size = iterator->first - iterator->second.base() + 1;
+
+  return true;
+}
+
+
+template<typename AddressType, typename EntryType>
+bool RangeMap<AddressType, EntryType>::RetrieveNearestRange(
+    const AddressType &address, EntryType *entry,
+    AddressType *entry_base, AddressType *entry_size) const {
+  if (!entry)
+    return false;
+
+  // If address is within a range, RetrieveRange can handle it.
+  if (RetrieveRange(address, entry, entry_base, entry_size))
+    return true;
+
+  // upper_bound gives the first element whose key is greater than address,
+  // but we want the first element whose key is less than or equal to address.
+  // Decrement the iterator to get there, but not if the upper_bound already
+  // points to the beginning of the map - in that case, address is lower than
+  // the lowest stored key, so return false.
+  MapConstIterator iterator = map_.upper_bound(address);
+  if (iterator == map_.begin())
+    return false;
+  --iterator;
+
+  *entry = iterator->second.entry();
+  if (entry_base)
+    *entry_base = iterator->first;
+  if (entry_size)
+    *entry_size = iterator->first - iterator->second.base() + 1;
+
   return true;
 }
 
diff --git a/src/processor/range_map.h b/src/processor/range_map.h
index d03d76fd..301b82e5 100644
--- a/src/processor/range_map.h
+++ b/src/processor/range_map.h
@@ -61,7 +61,19 @@ class RangeMap {
 
   // Locates the range encompassing the supplied address.  If there is
   // no such range, or if there is a parameter error, returns false.
-  bool RetrieveRange(const AddressType &address, EntryType *entry) const;
+  // entry_base and entry_size, if non-NULL, are set to the base and size
+  // of the entry's range.
+  bool RetrieveRange(const AddressType &address, EntryType *entry,
+                     AddressType *entry_base, AddressType *entry_size) const;
+
+  // Locates the range encompassing the supplied address, if one exists.
+  // If no range encompasses the supplied address, locates the nearest range
+  // to the supplied address that is lower than the address.  Returns false
+  // if no range meets these criteria.  entry_base and entry_size, if
+  // non-NULL, are set to the base and size of the entry's range.
+  bool RetrieveNearestRange(const AddressType &address, EntryType *entry,
+                            AddressType *entry_base, AddressType *entry_size)
+                            const;
 
   // Empties the range map, restoring it to the state it was when it was
   // initially created.
diff --git a/src/processor/range_map_unittest.cc b/src/processor/range_map_unittest.cc
index 4fd3c3be..39fac6d0 100644
--- a/src/processor/range_map_unittest.cc
+++ b/src/processor/range_map_unittest.cc
@@ -36,10 +36,12 @@
 #include <cstdio>
 #include <memory>
 
+#include "processor/linked_ptr.h"
 #include "processor/range_map-inl.h"
 
 
 using std::auto_ptr;
+using google_airbag::linked_ptr;
 using google_airbag::RangeMap;
 
 
@@ -48,7 +50,6 @@ using google_airbag::RangeMap;
 class CountedObject {
  public:
   explicit CountedObject(int id) : id_(id) { ++count_; }
-  CountedObject(const CountedObject &that) : id_(that.id_) { ++count_; }
   ~CountedObject() { --count_; }
 
   static int count() { return count_; }
@@ -63,7 +64,7 @@ int CountedObject::count_;
 
 
 typedef int AddressType;
-typedef RangeMap<AddressType, CountedObject> TestMap;
+typedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap;
 
 
 // RangeTest contains data to use for store and retrieve tests.  See
@@ -98,7 +99,7 @@ struct RangeTestSet {
 // test RangeMap.  It returns true if the expected result occurred, and
 // false if something else happened.
 bool StoreTest(TestMap *range_map, const RangeTest *range_test) {
-  CountedObject object(range_test->id);
+  linked_ptr<CountedObject> object(new CountedObject(range_test->id));
   bool stored = range_map->StoreRange(range_test->address,
                                       range_test->size,
                                       object);
@@ -158,10 +159,14 @@ bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) {
           expected_result = !side;   // should succeed low and fail high.
       }
 
-      CountedObject object(-1);
-      bool retrieved = range_map->RetrieveRange(address, &object);
+      linked_ptr<CountedObject> object;
+      AddressType retrieved_base;
+      AddressType retrieved_size;
+      bool retrieved = range_map->RetrieveRange(address, &object,
+                                                &retrieved_base,
+                                                &retrieved_size);
 
-      bool observed_result = retrieved && object.id() == range_test->id;
+      bool observed_result = retrieved && object->id() == range_test->id;
 
       if (observed_result != expected_result) {
         fprintf(stderr, "FAILED: "
@@ -174,6 +179,59 @@ bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) {
                         observed_result ? "true" : "false");
         return false;
       }
+
+      // If a range was successfully retrieved, check that the returned
+      // bounds match the range as stored.
+      if (observed_result == true &&
+          (retrieved_base != range_test->address ||
+           retrieved_size != range_test->size)) {
+        fprintf(stderr, "FAILED: "
+                        "RetrieveRange id %d, side %d, offset %d, "
+                        "expected base/size %d/%d, observed %d/%d\n",
+                        range_test->id,
+                        side,
+                        offset,
+                        range_test->address, range_test->size,
+                        retrieved_base, retrieved_size);
+        return false;
+      }
+
+      // Now, check RetrieveNearestRange.  The nearest range is always
+      // expected to be different from the test range when checking one
+      // less than the low side.
+      bool expected_nearest = range_test->expect_storable;
+      if (!side && offset < 0)
+        expected_nearest = false;
+
+      linked_ptr<CountedObject> nearest_object;
+      AddressType nearest_base;
+      bool retrieved_nearest = range_map->RetrieveNearestRange(address,
+                                                               &nearest_object,
+                                                               &nearest_base,
+                                                               NULL);
+
+      // When checking one greater than the high side, RetrieveNearestRange
+      // should usually return the test range.  When a different range begins
+      // at that address, though, then RetrieveNearestRange should return the
+      // range at the address instead of the test range.
+      if (side && offset > 0 && nearest_base == address) {
+        expected_nearest = false;
+      }
+
+      bool observed_nearest = retrieved_nearest &&
+                              nearest_object->id() == range_test->id;
+
+      if (observed_nearest != expected_nearest) {
+        fprintf(stderr, "FAILED: "
+                        "RetrieveNearestRange id %d, side %d, offset %d, "
+                        "expected %s, observed %s\n",
+                        range_test->id,
+                        side,
+                        offset,
+                        expected_nearest ? "true" : "false",
+                        observed_nearest ? "true" : "false");
+        return false;
+      }
     }
   }
 
diff --git a/src/processor/source_line_resolver.cc b/src/processor/source_line_resolver.cc
index 3c612c75..e2e884ce 100644
--- a/src/processor/source_line_resolver.cc
+++ b/src/processor/source_line_resolver.cc
@@ -34,6 +34,7 @@
 #include <utility>
 #include "processor/source_line_resolver.h"
 #include "google/stack_frame.h"
+#include "processor/address_map-inl.h"
 #include "processor/contained_range_map-inl.h"
 #include "processor/linked_ptr.h"
 #include "processor/range_map-inl.h"
@@ -77,6 +78,23 @@ struct SourceLineResolver::Function {
   RangeMap< MemAddr, linked_ptr<Line> > lines;
 };
 
+struct SourceLineResolver::PublicSymbol {
+  PublicSymbol(const string& set_name,
+               MemAddr set_address,
+               int set_parameter_size)
+      : name(set_name),
+        address(set_address),
+        parameter_size(set_parameter_size) {}
+
+  string name;
+  MemAddr address;
+
+  // If the public symbol is used as a function entry point, parameter_size
+  // is set to the size of the parameters passed to the funciton on the
+  // stack, if known.
+  int parameter_size;
+};
+
 class SourceLineResolver::Module {
  public:
   Module(const string &name) : name_(name) { }
@@ -129,12 +147,17 @@ class SourceLineResolver::Module {
   // Parses a line declaration, returning a new Line object.
   Line* ParseLine(char *line_line);
 
+  // Parses a PUBLIC symbol declaration, storing it in public_symbols_.
+  // Returns false if an error occurs.
+  bool ParsePublicSymbol(char *public_line);
+
   // Parses a stack frame info declaration, storing it in stack_info_.
   bool ParseStackInfo(char *stack_info_line);
 
   string name_;
   FileMap files_;
   RangeMap< MemAddr, linked_ptr<Function> > functions_;
+  AddressMap< MemAddr, linked_ptr<PublicSymbol> > public_symbols_;
 
   // Each element in the array is a ContainedRangeMap for a type listed in
   // StackInfoTypes.  These are split by type because there may be overlaps
@@ -208,10 +231,17 @@ bool SourceLineResolver::Module::LoadMap(const string &map_file) {
       if (!cur_func) {
         return false;
       }
-      functions_.StoreRange(cur_func->address, cur_func->size,
-                            linked_ptr<Function>(cur_func));
+      if (!functions_.StoreRange(cur_func->address, cur_func->size,
+                                 linked_ptr<Function>(cur_func))) {
+        return false;
+      }
     } else if (strncmp(buffer, "PUBLIC ", 7) == 0) {
-      // TODO(mmentovai): add a public map
+      // Clear cur_func: public symbols don't contain line number information.
+      cur_func = NULL;
+
+      if (!ParsePublicSymbol(buffer)) {
+        return false;
+      }
     } else {
       if (!cur_func) {
         return false;
@@ -248,30 +278,62 @@ void SourceLineResolver::Module::LookupAddress(
     }
   }
 
+  // First, look for a matching FUNC range.  Use RetrieveNearestRange instead
+  // of RetrieveRange so that the nearest function can be compared to the
+  // nearest PUBLIC symbol if the address does not lie within the function.
+  // Having access to the highest function below address, even when address
+  // is outside of the function, is useful: if the function is higher than
+  // the nearest PUBLIC symbol, then it means that the PUBLIC symbols is not
+  // valid for the address, and no function information should be filled in.
+  // Using RetrieveNearestRange instead of RetrieveRange means that we need
+  // to verify that address is within the range before using a FUNC.
+  //
+  // If no FUNC containing the address is found, look for the nearest PUBLIC
+  // symbol, being careful not to use a public symbol at a lower address than
+  // the nearest FUNC.
+  int parameter_size = 0;
   linked_ptr<Function> func;
-  if (!functions_.RetrieveRange(address, &func)) {
-    return;
-  }
+  linked_ptr<PublicSymbol> public_symbol;
+  MemAddr function_base;
+  MemAddr function_size;
+  MemAddr public_address;
+  if (functions_.RetrieveNearestRange(address, &func,
+                                      &function_base, &function_size) &&
+      address >= function_base && address < function_base + function_size) {
+    parameter_size = func->parameter_size;
+
+    frame->function_name = func->name;
+    frame->function_base = frame->module_base + function_base;
+
+    linked_ptr<Line> line;
+    MemAddr line_base;
+    if (func->lines.RetrieveRange(address, &line, &line_base, NULL)) {
+      FileMap::const_iterator it = files_.find(line->source_file_id);
+      if (it != files_.end()) {
+        frame->source_file_name = files_.find(line->source_file_id)->second;
+      }
+      frame->source_line = line->line;
+      frame->source_line_base = frame->module_base + line_base;
+    }
+  } else if (public_symbols_.Retrieve(address,
+                                      &public_symbol, &public_address) &&
+             (!func.get() || public_address > function_base + function_size)) {
+    parameter_size = public_symbol->parameter_size;
 
-  frame->function_name = func->name;
-  linked_ptr<Line> line;
-  if (!func->lines.RetrieveRange(address, &line)) {
+    frame->function_name = public_symbol->name;
+    frame->function_base = frame->module_base + public_address;
+  } else {
+    // No FUNC or PUBLIC data available.
     return;
   }
 
-  FileMap::const_iterator it = files_.find(line->source_file_id);
-  if (it != files_.end()) {
-    frame->source_file_name = files_.find(line->source_file_id)->second;
-  }
-  frame->source_line = line->line;
-
   if (frame_info &&
       !(frame_info->valid & StackFrameInfo::VALID_PARAMETER_SIZE)) {
     // Even without a relevant STACK line, many functions contain information
     // about how much space their parameters consume on the stack.  Prefer
     // the STACK stuff (above), but if it's not present, take the
-    // information from the FUNC line.
-    frame_info->parameter_size = func->parameter_size;
+    // information from the FUNC or PUBLIC line.
+    frame_info->parameter_size = parameter_size;
     frame_info->valid |= StackFrameInfo::VALID_PARAMETER_SIZE;
   }
 }
@@ -325,7 +387,7 @@ void SourceLineResolver::Module::ParseFile(char *file_line) {
 
 SourceLineResolver::Function* SourceLineResolver::Module::ParseFunction(
     char *function_line) {
-  // FUNC <address> <stack_param_size> <name>
+  // FUNC <address> <size> <stack_param_size> <name>
   function_line += 5;  // skip prefix
 
   vector<char*> tokens;
@@ -360,6 +422,36 @@ SourceLineResolver::Line* SourceLineResolver::Module::ParseLine(
   return new Line(address, size, source_file, line_number);
 }
 
+bool SourceLineResolver::Module::ParsePublicSymbol(char *public_line) {
+  // PUBLIC <address> <stack_param_size> <name>
+
+  // Skip "PUBLIC " prefix.
+  public_line += 7;
+
+  vector<char*> tokens;
+  if (!Tokenize(public_line, 3, &tokens)) {
+    return false;
+  }
+
+  u_int64_t address    = strtoull(tokens[0], NULL, 16);
+  int stack_param_size = strtoull(tokens[1], NULL, 16);
+  char *name           = tokens[2];
+
+  // A few public symbols show up with an address of 0.  This has been seen
+  // in the dumped output of ntdll.pdb for symbols such as _CIlog, _CIpow,
+  // RtlDescribeChunkLZNT1, and RtlReserveChunkLZNT1.  They would conflict
+  // with one another if they were allowed into the public_symbols_ map,
+  // but since the address is obviously invalid, gracefully accept them
+  // as input without putting them into the map.
+  if (address == 0) {
+    return true;
+  }
+
+  linked_ptr<PublicSymbol> symbol(new PublicSymbol(name, address,
+                                                   stack_param_size));
+  return public_symbols_.Store(address, symbol);
+}
+
 bool SourceLineResolver::Module::ParseStackInfo(char *stack_info_line) {
   // STACK WIN <type> <rva> <code_size> <prolog_size> <epliog_size>
   // <parameter_size> <saved_register_size> <local_size> <max_stack_size>
diff --git a/src/processor/source_line_resolver.h b/src/processor/source_line_resolver.h
index 1490f715..f0d1e54b 100644
--- a/src/processor/source_line_resolver.h
+++ b/src/processor/source_line_resolver.h
@@ -73,6 +73,7 @@ class SourceLineResolver {
   template<class T> class MemAddrMap;
   struct Line;
   struct Function;
+  struct PublicSymbol;
   struct File;
   struct HashString {
     size_t operator()(const string &s) const;
diff --git a/src/processor/source_line_resolver_unittest.cc b/src/processor/source_line_resolver_unittest.cc
index 5cdfb85b..6cc9afd3 100644
--- a/src/processor/source_line_resolver_unittest.cc
+++ b/src/processor/source_line_resolver_unittest.cc
@@ -116,6 +116,22 @@ static bool RunTests() {
   ASSERT_EQ(frame.source_line, 21);
   ASSERT_EQ(frame_info.prolog_size, 1);
 
+  frame.instruction = 0x216f;
+  frame.module_name = "module2";
+  resolver.FillSourceLineInfo(&frame, &frame_info);
+  ASSERT_EQ(frame.function_name, "Public2_1");
+
+  ClearSourceLineInfo(&frame, &frame_info);
+  frame.instruction = 0x219f;
+  frame.module_name = "module2";
+  resolver.FillSourceLineInfo(&frame, &frame_info);
+  ASSERT_TRUE(frame.function_name.empty());
+
+  frame.instruction = 0x21a0;
+  frame.module_name = "module2";
+  resolver.FillSourceLineInfo(&frame, &frame_info);
+  ASSERT_EQ(frame.function_name, "Public2_2");
+
   ASSERT_FALSE(resolver.LoadModule("module3",
                                    testdata_dir + "/module3_bad.out"));
   ASSERT_FALSE(resolver.HasModule("module3"));
diff --git a/src/processor/testdata/module2.out b/src/processor/testdata/module2.out
index f25740b7..6c1cb378 100644
--- a/src/processor/testdata/module2.out
+++ b/src/processor/testdata/module2.out
@@ -5,10 +5,12 @@ FUNC 2000 c 4 Function2_1
 1000 4 54 1
 1004 4 55 1
 1008 4 56 1
+PUBLIC 2160 0 Public2_1
 FUNC 2170 14 4 Function2_2
 2170 6 10 2
 2176 4 12 2
 217a 6 13 2
 2180 4 21 2
+PUBLIC 21a0 0 Public2_2
 STACK WIN 4 2000 c 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
 STACK WIN 4 2170 14 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =