Adds LRU caching of compile units in DWARFContext.

[netforce]

Summary

This adds LRU caching of compile units in DWARFContext to reduce memory consumption of llvm-symbolizer. When llvm-symbolize symbolizes addresses from various compile units, it keeps the internal data structure (e.g. DIE and line table) for all relevant compile units until it finishes running. This leads to memory bloat when symbolizing many addresses. The memory usage can be limited by only keeping a fixed number of compile units in the memory.

This might make it longer to run because sometimes it has to parse the same compile unit as it's kicked out of memory. For better performance, LRU caching is used to keep the recently used compile units in the memory while kicking out the ones not used recently.

Confirmed this reduces the memory usage significantly (1.3GB -> 441MB when symbolizing a clang binary).
$ nm clang | sort -n | gawk '{printf "0x%s\n", $1}' | /usr/bin/time -f "RSS: %M KB\nexecution_time: %E\n" ./llvm-symbolizer-before -a -demangle -obj clang > /dev/null
RSS: 1314996 KB
execution_time: 0:04.11

$ nm clang | sort -n | gawk '{printf "0x%s\n", $1}' | /usr/bin/time -f "RSS: %M KB\nexecution_time: %E\n" ./llvm-symbolizer-after -a -demangle -obj clang > /dev/null
RSS: 441300 KB
execution_time: 0:08.15

Using Valgrind/Massif we could also confirm it limits the memory usage growth while it keeps growing without the change.
$ nm clang | sort -n | gawk '{printf "0x%s\n", $1}' | /usr/bin/valgrind --tool=massif --massif-out-file=massif.out.before ./llvm-symbolizer-before -a -demangle -obj clang > /dev/null
$ ms_print massif.out.before
`--------------------------------------------------------------------------------
Command: ./llvm-symbolizer-before -a -demangle -obj clang
Massif arguments: --massif-out-file=massif.out.before

ms_print arguments: massif.out.before

GB

1.208^ :

  |                                                                  @@@#::
  |                                                               @@@@@@#::
  |                                                            @@@@@@@@@#::
  |                                                        @@@@@@@@@@@@@#::
  |                                                     ::@@ @@@@@@@@@@@#::
  |                                                 ::::::@@ @@@@@@@@@@@#::
  |                                              @@@::: ::@@ @@@@@@@@@@@#::
  |                                           @@@@@@::: ::@@ @@@@@@@@@@@#::
  |                                       @@@@@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                                    @@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                                ::@:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                              ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                         :@:::::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                     @@@::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                   @@@ @::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |                @@:@@@ @::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |           @@@@@@@ @@@ @::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |       ::@@@ @@ @@ @@@ @::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
  |    @@@: @@@ @@ @@ @@@ @::@:: ::: @:@@@@@ @@@ @@@::: ::@@ @@@@@@@@@@@#::
0 +----------------------------------------------------------------------->Gi
  0                                                                   19.40

...`

$ nm clang | sort -n | gawk '{printf "0x%s\n", $1}' | /usr/bin/valgrind --tool=massif --massif-out-file=massif.out.after ./llvm-symbolizer-after -a -demangle -obj clang > /dev/null
$ ms_print massif.out.after
`--------------------------------------------------------------------------------
Command: ./llvm-symbolizer-after -a -demangle -obj clang
Massif arguments: --massif-out-file=massif.out.after

ms_print arguments: massif.out.after

MB

97.32^ #

  |              #                                                         
  |              #                                                         
  |              #          :                        ::                    
  |              #          :                        :                     
  |              #          :                        :                     
  |              #          :                        :                     
  |              #          :           @@:          :             :       
  |              #          :           @ :          : :           :       
  |             :#          :           @ :          : :           :       
  |          :  :#          :        :  @ :        : : :        @  :       
  |          :  :#      @@  :::      :: @ :        ::: :        @:::       
  |          ::::#      @   ::       :: @ :      ::::: :      ::@: :   :   
  |     : :  :: :#@@   :@ :::: : : :::::@ ::  :::: ::: : :    ::@: ::: :  :
  | ::::::::::: :#@ ::::@ : :: ::: : :::@ ::@::: : ::: :::::::::@: :::@::::
  | :: ::::: :: :#@ :: :@ : :: :::@: :::@ ::@::: : ::: :::::: ::@: :::@::::
  | :: ::::: :: :#@ :: :@ : :: :::@: :::@ ::@::: : ::: :::::: ::@: :::@::::
  | :: ::::: :: :#@ :: :@ : :: :::@: :::@ ::@::: : ::: :::::: ::@: :::@::::
  | :: ::::: :: :#@ :: :@ : :: :::@: :::@ ::@::: : ::: :::::: ::@: :::@::::
  | :: ::::: :: :#@ :: :@ : :: :::@: :::@ ::@::: : ::: :::::: ::@: :::@::::
0 +----------------------------------------------------------------------->Gi
  0                                                                   49.33

...`

[aprantl]

Do you think this is always a win, i.e., also for LLDB, or should this be done in a higher layer?

[netforce]

In D78950#2006434, @aprantl wrote:

Do you think this is always a win, i.e., also for LLDB, or should this be done in a higher layer?

In terms of memory usage, this will always make it smaller or equal to the current implementation except the small amount used for the LRU data structure. It could increase execution time or CPU usage, since it is possible that some compile units need to be parsed multiple times due to the cache eviction. How much it is affected depends on the access pattern of the information. In our use case of llvm-symbolizer and our own symbolization library, it could save huge memory with reasonable degradation of CPU usage.

Since DWARFContext is used as entry point of the API, I thought it makes sense to place the caching functionality there. Although I'm not very familiar with LLDB, if this hurts the performance of it, it can opt out of using the caching by giving negative LRUSize when creating DWARFContext.

In case reviewers agree that it makes more sense to put it in a higher layer, I believe that's possible too after making a couple private member functions public.

[ikudrin]

Is it possible to add some tests for the LRU logic?

llvm/include/llvm/DebugInfo/DWARF/DWARFContext.h

117–124

Can this be a separate utility class? No need to overburden DWARFContext.

321

Does this method need to be in the public interface of the class? Right now, it looks like an implementation detail that should be hidden from users.

402

It looks like this should also be private, no?

[labath]

In D78950#2006434, @aprantl wrote:

Do you think this is always a win, i.e., also for LLDB, or should this be done in a higher layer?

Whether this is a win or not will definitely depend on the usage patterns, and it's very hard to know that for sure before trying it out on a specific use case. My gut feeling would be that this wouldn't help lldb's memory usage much because lldb already stores so much other state, but it may have a big (negative) impact on cpu usage. However, given that this functionality can be turned off (thought that could be better documented) I don't think we need to burden ourselves with that too much with what would happen with lldb in particular.

That said, I'm not really sure what to make of this patch. What was they criterion for choosing where to place the referCompileUnit calls ? Right, now they seem to be present on a couple of high-level APIs, but those functions are definitely not the only way to access dwarf units. Indeed, once you start thinking about the lower level APIs, things start to get a lot more fuzzier. And dangerous -- for instance, this makes it very easy to turn a perfectly valid DWARFDie object into a landmine if some operation happens to "garbage-collect" the DWARFDebugInfoEntry object that it refers to.

I think that example would definitely speak for a separate layer with a high level api, which offers only a limited (and more controlled) way of accessing the information in the dwarf file. How feasible is that in the current situation -- I don't know.

In D78950#2006767, @netforce wrote:

Although I'm not very familiar with LLDB, if this hurts the performance of it, it can opt out of using the caching by giving negative LRUSize when creating DWARFContext.

I think it's important to note here that lldb does not use (most of) llvm dwarf parsing code right now -- it has it's own semi-forked versions of a lot of stuff. However, we are looking into making it reuse more (all?) of llvm dwarf parsing code, which is why it is important to ensure the interface stays flexible enough.

[netforce]

In D78950#2007001, @ikudrin wrote:

Is it possible to add some tests for the LRU logic?

When we decide where to put caching, I'll see if I can add some unit tests.

llvm/include/llvm/DebugInfo/DWARF/DWARFContext.h

117–124

Once we determine which layer we place this LRU caching first, I'll revisit this and see if it would be cleaner to use a separate utility class.

321

I'll revisit this too when we decide which layer to put the caching. For the current implementation, it seems it doesn't need to be public.

402

Again, I'll revisit this when we decide which layer to put the caching. For the current implementation, we need this to be public as we have our symbolization tool directly accessing the compile units.

[netforce]

In D78950#2007530, @labath wrote:

In D78950#2006434, @aprantl wrote:

Do you think this is always a win, i.e., also for LLDB, or should this be done in a higher layer?

Whether this is a win or not will definitely depend on the usage patterns, and it's very hard to know that for sure before trying it out on a specific use case. My gut feeling would be that this wouldn't help lldb's memory usage much because lldb already stores so much other state, but it may have a big (negative) impact on cpu usage. However, given that this functionality can be turned off (thought that could be better documented) I don't think we need to burden ourselves with that too much with what would happen with lldb in particular.

That said, I'm not really sure what to make of this patch. What was they criterion for choosing where to place the referCompileUnit calls ? Right, now they seem to be present on a couple of high-level APIs, but those functions are definitely not the only way to access dwarf units. Indeed, once you start thinking about the lower level APIs, things start to get a lot more fuzzier. And dangerous -- for instance, this makes it very easy to turn a perfectly valid DWARFDie object into a landmine if some operation happens to "garbage-collect" the DWARFDebugInfoEntry object that it refers to.

I think that example would definitely speak for a separate layer with a high level api, which offers only a limited (and more controlled) way of accessing the information in the dwarf file. How feasible is that in the current situation -- I don't know.

In D78950#2006767, @netforce wrote:

Although I'm not very familiar with LLDB, if this hurts the performance of it, it can opt out of using the caching by giving negative LRUSize when creating DWARFContext.

I think it's important to note here that lldb does not use (most of) llvm dwarf parsing code right now -- it has it's own semi-forked versions of a lot of stuff. However, we are looking into making it reuse more (all?) of llvm dwarf parsing code, which is why it is important to ensure the interface stays flexible enough.

I agree that it's better to keep the interface flexible enough. As I mentioned in previous comment, I'm open to moving this to a different layer. Since I'm new to LLVM, please advise me where would be the best place for this.

Here's my thought process of placing this in DWARFContext. I only looked at two users of this DWARF API (llvm-symbolizer and our own symbolization tool). llvm-symbolizer access it mainly through DIContext interface from which DWARFContext inherits. Our symbolization tool access it via both DWARFContext and DWARFUnit. So, I thought DWARFContext would be a good place to put this in order for both of them to use it. I'm sorry I didn't take a look at LLDB.

With that being said, I'm OK with moving the caching to the symbolizer layer. Since they access the API through DWARFContext, it needs to expose a couple more member functions to make it possible:

1. getCompileUnitForAddress
2. clearLineTableForUnit

Do you think this is better in terms of keeping the API flexible enough? Or do you suggest another way? Please let me know. Thanks.

[labath]

(adding more debug info folks)

In D78950#2008973, @netforce wrote:

Do you think this is better in terms of keeping the API flexible enough?

Umm... probably?

I don't have a comprehensive overview of the users of the DWARF parser either, but I'm sure there are users that want to access it through the lower level APIs. Lldb will most likely be one of those users -- even after it starts using llvm parsers completely I think it's fairly unlikely it would use APIs like getLocalsForAddress, but rather do something custom. However, all of that is vapourware, so its hard to reason about that.

It may be more interesting to look at other (real) users. One such user which comes to mind is (llvm-)dsymutil, as it accesses dwarf in a fairly complex way. Jonas, what do you think?

[netforce]

In D78950#2009668, @labath wrote:

(adding more debug info folks)

In D78950#2008973, @netforce wrote:

Do you think this is better in terms of keeping the API flexible enough?

Umm... probably?

I don't have a comprehensive overview of the users of the DWARF parser either, but I'm sure there are users that want to access it through the lower level APIs. Lldb will most likely be one of those users -- even after it starts using llvm parsers completely I think it's fairly unlikely it would use APIs like getLocalsForAddress, but rather do something custom. However, all of that is vapourware, so its hard to reason about that.

It may be more interesting to look at other (real) users. One such user which comes to mind is (llvm-)dsymutil, as it accesses dwarf in a fairly complex way. Jonas, what do you think?

I took a look at llvm-symbolizer code considering how to fit the caching there, and I also took a brief look at dsymutil to see how it uses the DWARF library.

llvm-symbolizer (more specifically code in lib/DebugInfo/Symbolize) mostly access the library through DIContext interface, and it can be either DWARFContext or PDBContext, while the caching is quite DWARFContext-specific.

dsymutil creates DWARFContext and give it to DWARFLinker library, then it seems it uses lower level API (DWARFUnit) to access the information. Here's an example.

So, both high level API (DIContext) and low level API (DWARFUnit) are being used depending on the the users, and it makes it difficult to decide where the best place to put the caching in is. Here are a few options I could think of.

1. Place caching in DWARFContext (as the revision currently is) but turn it off by default.

In this way, llvm-symbolizer could benefit from the revision without making its client code too complicated. At the same time, it'll be noop for other users that access the library with lower level API. If they need caching later, they can choose between implementing it using the lower level API or using the one in DWARFContext.

2. Move caching to llvm-symbolizer

This minimizes the disruption in the API (both DWARFContext and DWARFUnit). However, I expect that it needs pretty messy changes in llvm-symbolizer because it uses DIContext interface: we need to make it distinguish the implementation of DIContext and apply caching only when it's DWARFContext.

3. Just expose the necessary member functions without implementing caching anywhere in LLVM source tree

This also needs minimum disruption in the API (as is in 2), and it's good enough for our own use case (our own symbolization tool that access the library via both DWARFContext and DWARFUnit). However, none of LLVM tool will benefit from caching until they implement it.

I'm good with all three options, but I'm personally leaning toward option 1. Which one should we follow for the sake of the API? Or is there any other way? Please let me know. Thank you!

[netforce]

This is a friendly ping. Could you please let me know which direction we should go? Thank you.

[labath]

First off, let me say that I don't feel qualified to set the direction here, nor I am fully familiar with all of these interfaces. However, since I am already involved in here, I am going to say something anyway. :)

The way I would imagine this working ideally is that there would be two layers. The lower layer would provide more explicit access to the debug info, and it would provide it's users with the ability to manually manage the memory usage. It would be the responsibility of the users to not shoot themselves in the foot if they use it.

The second layer would offer a higher level view of the debug info and it would manage the memory (semi)automatically. Being high level it would/could/should also abstract away the difference between the different debug info formats.

The first layer would roughly correspond to the current DWARFUnit, DWARFContext, etc. classes, with one important difference DWARFContext would not implement DIContext -- it would be a standalone class. The second layer would correspond to the DIContext class, and any of the (new) helper classes it needs to manage the memory and perform the abstractions.

The main advantage I see in that is the breaking of the is-a relationship between DWARFContext and DIContext. Without it the interfaces seems rather shoot-footy because one can happily play around with the lower-level DWARFContext apis (which don't manage memory), and then accidentally call some higher level method which comes from DIContext , which does the management and will then cause the debug info to disappear from under you.

As I said, I don't know how easy would be to reach this state, nor whether it would be an acceptable state for other stakeholders...

[netforce]

In D78950#2022293, @labath wrote:

First off, let me say that I don't feel qualified to set the direction here, nor I am fully familiar with all of these interfaces. However, since I am already involved in here, I am going to say something anyway. :)

The way I would imagine this working ideally is that there would be two layers. The lower layer would provide more explicit access to the debug info, and it would provide it's users with the ability to manually manage the memory usage. It would be the responsibility of the users to not shoot themselves in the foot if they use it.

The second layer would offer a higher level view of the debug info and it would manage the memory (semi)automatically. Being high level it would/could/should also abstract away the difference between the different debug info formats.

The first layer would roughly correspond to the current DWARFUnit, DWARFContext, etc. classes, with one important difference DWARFContext would not implement DIContext -- it would be a standalone class. The second layer would correspond to the DIContext class, and any of the (new) helper classes it needs to manage the memory and perform the abstractions.

The main advantage I see in that is the breaking of the is-a relationship between DWARFContext and DIContext. Without it the interfaces seems rather shoot-footy because one can happily play around with the lower-level DWARFContext apis (which don't manage memory), and then accidentally call some higher level method which comes from DIContext , which does the management and will then cause the debug info to disappear from under you.

As I said, I don't know how easy would be to reach this state, nor whether it would be an acceptable state for other stakeholders...

Hi Pavel,

I like your two layers idea, since it could give better control to the lower level API users and enable the new feature for the higher level API users without complicating the higher level API.

However, I don't think I have enough understanding of the wholesome picture of the DWARF API to make it in a better shape by refactoring it, which I believe is needed to decouple DWARFContext from DIContext. Furthermore, that seems quite out of the scope of this revision.

So, here's my suggestion that could make this revision align better with the direction you suggested, but leaving the refactoring for a later revision from someone who has better knowledge of the API.

1. I'll expose primitive member functions in DWARFUnit and DWARFContext so that lower level API users can control memory management themselves.
2. I'll introduce a new wrapper class (say CachedDWARFContext?) that implements DIContext with the LRU caching and having an instance of DWARFContext.
3. I'll let llvm-symbolizer uses the new wrapper class where it currently uses DWARFContext as DIContext.

I think this is one step closer to what you suggest without letting an unqualified person (= me) substantially modify the API (= DWARFContext) that's used by several different clients. It'll also make it easier to decouple DWARFContext from DIContext in a later revision.

WDYT? If you think this is reasonable, I'll prepare the changes. We can talk more about the details there and ask the other stakeholders if this is OK too.

Thank you,
HK

[netforce]

Hi Pavel,

This is a friendly ping. Could you please see if my previous comment sounds OK?

Thanks,
HK

[labath]

(sorry about the delay... the usual blurb about being busy, not being qualified etc.)

Yes, that sounds like a reasonable design to me. I think it's definitely worth creating a patch to see how it looks like in practice.

[netforce]

Hi Pavel,

Thank you for the confirmation. I'll shortly prepare a patch in that direction.

Thanks,
HK

[netforce]

Reflected the discussion we've had so far. Made minimum change to the lower level API (DWARFContext, DWARFDebugLine, and DWARFUnit) to make it possible for the high level API and symbolization tool to implement caching. Added a higher level API (DWARFCachedDIContext) that implements DIContext with LRU caching so that llvm-symbolizer could benefit from the caching without code change. It is also a step toward decoupling DWARFContext from DIContext in the future which would be desirable for other use of DWARFContext (e.g. LLDB). Finally, added a unit test for the LRU logic.

[netforce]

In D78950#2007001, @ikudrin wrote:

Is it possible to add some tests for the LRU logic?

Added a unit test for the LRU logic. Thank you.

llvm/include/llvm/DebugInfo/DWARF/DWARFContext.h

117–124

Added DWARFCachedDIContext to implement DIContext with LRU caching without modifying DWARFContext much. Also added a utility class (DWARFUnitLRUCache) there.

321

To expose memory management feature to higher level API or tools, this needs to be public now. Please refer to the previous discussion for more context.

402

To implement caching in a separate class, this needs to be public. Actually, it seems it has already become public in another (previous) revision.

[netforce]

In D78950#2033767, @labath wrote:

(sorry about the delay... the usual blurb about being busy, not being qualified etc.)

Yes, that sounds like a reasonable design to me. I think it's definitely worth creating a patch to see how it looks like in practice.

Hi Pavel,

Created the patch as we discussed. PTAL.

Thank you,
HK

[netforce]

Sorry I mistakenly dropped the CMakeLists.txt files in the previous patch. Added them.

[labath]

I think this is definitely cleaner than the previous patch. However, I still see some potential problems here. The way that this patch implements the reference counting means not all "usages" of DWARFUnits will be recorded. For example, during a call to GetLocalsForAddress, we end up calling Die.getAttributeValueAsReferencedDie(DW_AT_type)) here. The type DIE may end up being in a different compile unit (DW_FORM_ref_addr, DW_FORM_ref_sig8, DW_FORM_GNU_ref_alt, only the first one seems to be implemented correctly), which can cause additional units to be parsed "behind your back". Now, the question is what to do about it...

If we don't do anything about that, then the code will still be "correct", but it may end up using more memory than you expect. And if we try to do something about it, then we're back to the problem of DIEs disappearing from under you -- that function continues to use the Die object after it gets the type, but getting the type can cause the memory that Die points to to "disappear"...

I don't know whether you're ok with this quirk of the implementation. I also don't know whether we are ok with it. At this point it would really be nice to get someone else's opinion on all of this...

[netforce]

FYI, I haven't abandoned this patch. I have been waiting for more opinions including dblaikie@'s.

I'll be on leave from work for the next 6 weeks. So, once I get back from it, I'll revisit the comments then and try to figure out how to move forward.

Thank you!

[dblaikie]

In D78950#2086146, @netforce wrote:

FYI, I haven't abandoned this patch. I have been waiting for more opinions including dblaikie@'s.

I'll be on leave from work for the next 6 weeks. So, once I get back from it, I'll revisit the comments then and try to figure out how to move forward.

Thank you!

Yep, it's on my list of things to review! Sorry for the delay.

[netforce]

In D78950#2086166, @dblaikie wrote:

In D78950#2086146, @netforce wrote:

FYI, I haven't abandoned this patch. I have been waiting for more opinions including dblaikie@'s.

I'll be on leave from work for the next 6 weeks. So, once I get back from it, I'll revisit the comments then and try to figure out how to move forward.

Thank you!

Yep, it's on my list of things to review! Sorry for the delay.

No problem at all. Please take your time as I'll have to get back in 6 weeks. Thank you!

[netforce]

We are still waiting for discussion on where to put this cache eviction / memory management functionality to better serve existing user via different API layers. While we try to make progress on that, it'll be great if we expose the minimum interface change so that we could reduce the our memory footprint by implementing cache eviction out of LLVM source tree. So, I extracted the minimum changes and sent out https://reviews.llvm.org/D90006 for review. PTAL. Thank you.

llvm/include/llvm/DebugInfo/DIContext.h

 //===- DIContext.h ----------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines DIContext, an abstract data structure that holds
struct DIDumpOptions {
 
   std::function<void(Error)> RecoverableErrorHandler =
       WithColor::defaultErrorHandler;
   std::function<void(Error)> WarningHandler = WithColor::defaultWarningHandler;
 };
 
 class DIContext {
 public:
-  enum DIContextKind {
-    CK_DWARF,
-    CK_PDB
-  };
+  enum DIContextKind { CK_DWARF, CK_CACHED_DWARF, CK_PDB };
 
   DIContext(DIContextKind K) : Kind(K) {}
   virtual ~DIContext() = default;
 
   DIContextKind getKind() const { return Kind; }
 
   virtual void dump(raw_ostream &OS, DIDumpOptions DumpOpts) = 0;
 

llvm/include/llvm/DebugInfo/DWARF/DWARFCachedDIContext.h

+//===- DWARFCachedDIContext.h ----------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===/
+
+#ifndef LLVM_DEBUGINFO_DWARF_DWARFCACHEDDICONTEXT_H
+#define LLVM_DEBUGINFO_DWARF_DWARFCACHEDDICONTEXT_H
+
+#include "llvm/DebugInfo/DIContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Error.h"
+#include <list>
+#include <memory>
+#include <string>
+#include <unordered_map>
+
+namespace llvm {
+
+class raw_ostream;
+
+/// DWARFUnitLRUCache
+/// This class provides data structure for LRU caching DWARFUnit.
+class DWARFUnitLRUCache {
+public:
+  DWARFUnitLRUCache(int LRUSize) : UnitLRUSize(LRUSize) {}
+
+  // Add a DWARFUnit to the cache if it doesn't already exists and evicts a
+  // least recently used (LRU) DWARFUnit in the cache if there's no more free
+  // space. Returns the pointer to the evicted DWARFUnit or nullptr if nothing's
+  // evicted.
+  DWARFUnit *addUnitAndEvictLRU(DWARFUnit *Unit);
+
+private:
+  using unit_queue_type = std::list<DWARFUnit *>;
+  using unit_queue_iterator = unit_queue_type::iterator;
+  using unit_map_type = std::unordered_map<DWARFUnit *, unit_queue_iterator>;
+  unit_queue_type UnitQueue;
+  unit_map_type UnitMap;
+  const int UnitLRUSize;
+};
+
+/// DWARFCachedDIContext
+/// This class implements DIContext interface using DWARFContext with caching
+/// internal data structure in order to keep memory usage from growing
+/// without a bound.
+class DWARFCachedDIContext : public DIContext {
+public:
+  DWARFCachedDIContext(std::unique_ptr<DWARFContext> DCtx,
+                       int LRUSize = DefaultLRUSize);
+  ~DWARFCachedDIContext();
+
+  DWARFCachedDIContext(DWARFCachedDIContext &) = delete;
+  DWARFCachedDIContext &operator=(DWARFCachedDIContext &) = delete;
+
+  static bool classof(const DIContext *DICtx) {
+    return DICtx->getKind() == CK_CACHED_DWARF;
+  }
+
+  void dump(raw_ostream &OS, DIDumpOptions DumpOpts) override;
+
+  bool verify(raw_ostream &OS, DIDumpOptions DumpOpts = {}) override;
+
+  DILineInfo getLineInfoForAddress(
+      object::SectionedAddress Address,
+      DILineInfoSpecifier Specifier = DILineInfoSpecifier()) override;
+  DILineInfoTable getLineInfoForAddressRange(
+      object::SectionedAddress Address, uint64_t Size,
+      DILineInfoSpecifier Specifier = DILineInfoSpecifier()) override;
+  DIInliningInfo getInliningInfoForAddress(
+      object::SectionedAddress Address,
+      DILineInfoSpecifier Specifier = DILineInfoSpecifier()) override;
+
+  std::vector<DILocal>
+  getLocalsForAddress(object::SectionedAddress Address) override;
+
+  static std::unique_ptr<DWARFCachedDIContext>
+  create(const object::ObjectFile &Obj, const LoadedObjectInfo *L = nullptr,
+         std::string DWPName = "",
+         std::function<void(Error)> RecoverableErrorHandler =
+             WithColor::defaultErrorHandler,
+         std::function<void(Error)> WarningHandler =
+             WithColor::defaultWarningHandler,
+         int LRUSize = DefaultLRUSize);
+
+private:
+  std::unique_ptr<DWARFContext> Context;
+
+  // LRU mechanism of compile units to manage memory usage.
+  DWARFUnitLRUCache Cache;
+  static constexpr int DefaultLRUSize = 10;
+
+  // Refer a compile unit so that it's pushed back in LRU.
+  void referCompileUnitForAddress(object::SectionedAddress Address);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_DEBUGINFO_DWARF_DWARFCACHEDDICONTEXT_H

llvm/include/llvm/DebugInfo/DWARF/DWARFContext.h

class DWARFContext : public DIContext {
   /// section.
   enum MacroSecType {
     MacinfoSection,
     MacinfoDwoSection,
     MacroSection
     // FIXME: Add support for.debug_macro.dwo section.
   };
 
 public:
   DWARFContext(std::unique_ptr<const DWARFObject> DObj,
                std::string DWPName = "",
                std::function<void(Error)> RecoverableErrorHandler =
                    WithColor::defaultErrorHandler,
                std::function<void(Error)> WarningHandler =
                    WithColor::defaultWarningHandler);
   ~DWARFContext();
 
   DWARFContext(DWARFContext &) = delete;
   DWARFContext &operator=(DWARFContext &) = delete;
 
   const DWARFObject &getDWARFObj() const { return *DObj; }
 
   static bool classof(const DIContext *DICtx) {
     return DICtx->getKind() == CK_DWARF;
public:
   const DWARFDebugLine::LineTable *getLineTableForUnit(DWARFUnit *U);
 
   /// Get a pointer to a parsed line table corresponding to a compile unit.
   /// Report any recoverable parsing problems using the handler.
   Expected<const DWARFDebugLine::LineTable *>
   getLineTableForUnit(DWARFUnit *U,
                       function_ref<void(Error)> RecoverableErrorHandler);
 
+  // Clear the line table object corresponding to a compile unit for memory
+  // management purpose. When it's referred to again, it'll be re-populated.
+  void clearLineTableForUnit(DWARFUnit *U);
+
   DataExtractor getStringExtractor() const {
     return DataExtractor(DObj->getStrSection(), false, 0);
   }
   DataExtractor getLineStringExtractor() const {
     return DataExtractor(DObj->getLineStrSection(), false, 0);
   }
 
   /// Wraps the returned DIEs for a given address.
public:
   /// TODO: refactor compile_units() to make this const.
   uint8_t getCUAddrSize();
 
   Triple::ArchType getArch() const {
     return getDWARFObj().getFile()->getArch();
   }
 
   /// Return the compile unit which contains instruction with provided
   /// address.
   /// TODO: change input parameter from "uint64_t Address"
   ///       into "SectionedAddress Address"
   DWARFCompileUnit *getCompileUnitForAddress(uint64_t Address);
 
 private:
   /// Parse a macro[.dwo] or macinfo[.dwo] section.
   std::unique_ptr<DWARFDebugMacro>
   parseMacroOrMacinfo(MacroSecType SectionType);
 
   void addLocalsForDie(DWARFCompileUnit *CU, DWARFDie Subprogram, DWARFDie Die,
                        std::vector<DILocal> &Result);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h

bool lookupAddressRangeImpl(object::SectionedAddress Address, uint64_t Size,
                                 std::vector<uint32_t> &Result) const;
   };
 
   const LineTable *getLineTable(uint64_t Offset) const;
   Expected<const LineTable *>
   getOrParseLineTable(DWARFDataExtractor &DebugLineData, uint64_t Offset,
                       const DWARFContext &Ctx, const DWARFUnit *U,
                       function_ref<void(Error)> RecoverableErrorHandler);
+  void clearLineTable(uint64_t Offset);
 
   /// Helper to allow for parsing of an entire .debug_line section in sequence.
   class SectionParser {
   public:
     using cu_range = DWARFUnitVector::iterator_range;
     using tu_range = DWARFUnitVector::iterator_range;
     using LineToUnitMap = std::map<uint64_t, DWARFUnit *>;
 

llvm/lib/DebugInfo/DWARF/DWARFCachedDIContext.cpp

+//===- DWARFCachedDIContext.cpp -------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/DWARF/DWARFCachedDIContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
+#include <utility>
+
+using namespace llvm;
+using namespace object;
+
+DWARFCachedDIContext::DWARFCachedDIContext(std::unique_ptr<DWARFContext> DCtx,
+                                           int LRUSize)
+    : DIContext(CK_CACHED_DWARF), Context(std::move(DCtx)), Cache(LRUSize) {}
+
+DWARFCachedDIContext::~DWARFCachedDIContext() = default;
+
+void DWARFCachedDIContext::dump(raw_ostream &OS, DIDumpOptions DumpOpts) {
+  Context->dump(OS, DumpOpts);
+}
+
+bool DWARFCachedDIContext::verify(raw_ostream &OS, DIDumpOptions DumpOpts) {
+  return Context->verify(OS, DumpOpts);
+}
+
+DILineInfo
+DWARFCachedDIContext::getLineInfoForAddress(object::SectionedAddress Address,
+                                            DILineInfoSpecifier Spec) {
+  referCompileUnitForAddress(Address);
+  return Context->getLineInfoForAddress(Address, Spec);
+}
+
+DILineInfoTable DWARFCachedDIContext::getLineInfoForAddressRange(
+    object::SectionedAddress Address, uint64_t Size, DILineInfoSpecifier Spec) {
+  referCompileUnitForAddress(Address);
+  return Context->getLineInfoForAddressRange(Address, Size, Spec);
+}
+
+DIInliningInfo DWARFCachedDIContext::getInliningInfoForAddress(
+    object::SectionedAddress Address, DILineInfoSpecifier Spec) {
+  referCompileUnitForAddress(Address);
+  return Context->getInliningInfoForAddress(Address, Spec);
+}
+
+std::vector<DILocal>
+DWARFCachedDIContext::getLocalsForAddress(object::SectionedAddress Address) {
+  referCompileUnitForAddress(Address);
+  return Context->getLocalsForAddress(Address);
+}
+
+void DWARFCachedDIContext::referCompileUnitForAddress(
+    object::SectionedAddress Address) {
+  DWARFUnit *CU = Context->getCompileUnitForAddress(Address.Address);
+  DWARFUnit *LRU = Cache.addUnitAndEvictLRU(CU);
+  if (LRU != nullptr) {
+    Context->clearLineTableForUnit(LRU);
+    LRU->clear();
+  }
+}
+
+std::unique_ptr<DWARFCachedDIContext> DWARFCachedDIContext::create(
+    const object::ObjectFile &Obj, const LoadedObjectInfo *L,
+    std::string DWPName, std::function<void(Error)> RecoverableErrorHandler,
+    std::function<void(Error)> WarningHandler, int LRUSize) {
+  auto DCtx = DWARFContext::create(Obj, L, DWPName, RecoverableErrorHandler,
+                                   WarningHandler);
+  return std::make_unique<DWARFCachedDIContext>(std::move(DCtx), LRUSize);
+}
+
+DWARFUnit *DWARFUnitLRUCache::addUnitAndEvictLRU(DWARFUnit *Unit) {
+  if (UnitLRUSize <= 0)
+    return nullptr;
+  if (Unit == nullptr)
+    return nullptr;
+  DWARFUnit *LRU = nullptr;
+  auto I = UnitMap.find(Unit);
+  if (I == UnitMap.end()) {
+    if (UnitQueue.size() == UnitLRUSize) {
+      LRU = UnitQueue.back();
+      UnitQueue.pop_back();
+      UnitMap.erase(LRU);
+    }
+  } else {
+    UnitQueue.erase(I->second);
+  }
+  UnitQueue.push_front(Unit);
+  UnitMap[Unit] = UnitQueue.begin();
+  return LRU;
+}

llvm/lib/DebugInfo/DWARF/DWARFContext.cpp

Expected<const DWARFDebugLine::LineTable *> DWARFContext::getLineTableForUnit(
 
   // We have to parse it first.
   DWARFDataExtractor lineData(*DObj, U->getLineSection(), isLittleEndian(),
                               U->getAddressByteSize());
   return Line->getOrParseLineTable(lineData, stmtOffset, *this, U,
                                    RecoverableErrorHandler);
 }
 
+void DWARFContext::clearLineTableForUnit(DWARFUnit *U) {
+  if (!Line)
+    return;
+
+  auto UnitDIE = U->getUnitDIE();
+  if (!UnitDIE)
+    return;
+
+  auto Offset = toSectionOffset(UnitDIE.find(DW_AT_stmt_list));
+  if (!Offset)
+    return;
+
+  uint64_t stmtOffset = *Offset + U->getLineTableOffset();
+  Line->clearLineTable(stmtOffset);
+}
+
 void DWARFContext::parseNormalUnits() {
   if (!NormalUnits.empty())
     return;
   DObj->forEachInfoSections([&](const DWARFSection &S) {
     NormalUnits.addUnitsForSection(*this, S, DW_SECT_INFO);
   });
   NormalUnits.finishedInfoUnits();
   DObj->forEachTypesSections([&](const DWARFSection &S) {

llvm/lib/DebugInfo/DWARF/DWARFDebugLine.cpp

if (Pos.second) {
     if (Error Err =
             LT->parse(DebugLineData, &Offset, Ctx, U, RecoverableErrorHandler))
       return std::move(Err);
     return LT;
   }
   return LT;
 }
 
+void DWARFDebugLine::clearLineTable(uint64_t Offset) {
+  LineTableMap.erase(Offset);
+}
+
 static StringRef getOpcodeName(uint8_t Opcode, uint8_t OpcodeBase) {
   assert(Opcode != 0);
   if (Opcode < OpcodeBase)
     return LNStandardString(Opcode);
   return "special";
 }
 
 uint64_t DWARFDebugLine::ParsingState::advanceAddr(uint64_t OperationAdvance,

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

 
 void DWARFUnit::clear() {
   Abbrevs = nullptr;
   BaseAddr.reset();
   RangeSectionBase = 0;
   LocSectionBase = 0;
   AddrOffsetSectionBase = None;
   clearDIEs(false);
+  AddrDieMap.clear();
+  if (DWO)
+    DWO->clear();
   DWO.reset();
 }
 
 const char *DWARFUnit::getCompilationDir() {
   return dwarf::toString(getUnitDIE().find(DW_AT_comp_dir), nullptr);
 }
 
 void DWARFUnit::extractDIEsToVector(

llvm/lib/DebugInfo/Symbolize/SymbolizableObjectFile.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolizableObjectFile.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/BinaryFormat/COFF.h"
-#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFCachedDIContext.h"
 #include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/SymbolSize.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Error.h"
 #include <algorithm>

 
 bool SymbolizableObjectFile::shouldOverrideWithSymbolTable(
     FunctionNameKind FNKind, bool UseSymbolTable) const {
   // When DWARF is used with -gline-tables-only / -gmlt, the symbol table gives
   // better answers for linkage names than the DIContext. Otherwise, we are
   // probably using PEs and PDBs, and we shouldn't do the override. PE files
   // generally only contain the names of exported symbols.
   return FNKind == FunctionNameKind::LinkageName && UseSymbolTable &&
-         isa<DWARFContext>(DebugInfoContext.get());
+         isa<DWARFCachedDIContext>(DebugInfoContext.get());
 }
 
 DILineInfo
 SymbolizableObjectFile::symbolizeCode(object::SectionedAddress ModuleOffset,
                                       DILineInfoSpecifier LineInfoSpecifier,
                                       bool UseSymbolTable) const {
   if (ModuleOffset.SectionIndex == object::SectionedAddress::UndefSection)
     ModuleOffset.SectionIndex =

llvm/lib/DebugInfo/Symbolize/Symbolize.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
 
 #include "SymbolizableObjectFile.h"
 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/BinaryFormat/COFF.h"
-#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFCachedDIContext.h"
 #include "llvm/DebugInfo/PDB/PDB.h"
 #include "llvm/DebugInfo/PDB/PDBContext.h"
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/Object/COFF.h"
 #include "llvm/Object/MachO.h"
 #include "llvm/Object/MachOUniversal.h"
 #include "llvm/Support/CRC.h"
 #include "llvm/Support/Casting.h"

 Expected<DILineInfo>
 LLVMSymbolizer::symbolizeCode(const ObjectFile &Obj,
                               object::SectionedAddress ModuleOffset) {
   StringRef ModuleName = Obj.getFileName();
   auto I = Modules.find(ModuleName);
   if (I != Modules.end())
     return symbolizeCodeCommon(I->second.get(), ModuleOffset);
 
-  std::unique_ptr<DIContext> Context = DWARFContext::create(Obj);
+  std::unique_ptr<DIContext> Context = DWARFCachedDIContext::create(Obj);
   Expected<SymbolizableModule *> InfoOrErr =
                      createModuleInfo(&Obj, std::move(Context), ModuleName);
   if (!InfoOrErr)
     return InfoOrErr.takeError();
   return symbolizeCodeCommon(*InfoOrErr, ModuleOffset);
 }
 
 Expected<DILineInfo>
if (!EC && DebugInfo != nullptr && !PDBFileName.empty()) {
         Modules.emplace(ModuleName, std::unique_ptr<SymbolizableModule>());
         // Return along the PDB filename to provide more context
         return createFileError(PDBFileName, std::move(Err));
       }
       Context.reset(new PDBContext(*CoffObject, std::move(Session)));
     }
   }
   if (!Context)
-    Context = DWARFContext::create(*Objects.second, nullptr, Opts.DWPName);
+    Context =
+        DWARFCachedDIContext::create(*Objects.second, nullptr, Opts.DWPName);
   return createModuleInfo(Objects.first, std::move(Context), ModuleName);
 }
 
 namespace {
 
 // Undo these various manglings for Win32 extern "C" functions:
 // cdecl       - _foo
 // stdcall     - _foo@12

llvm/unittests/DebugInfo/DWARF/DWARFCachedDIContextTest.cpp

+//===- DWARFCachedDIContextTest.cpp ---------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/DebugInfo/DWARF/DWARFCachedDIContext.h"
+#include "DwarfGenerator.h"
+#include "DwarfUtils.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+#include <memory>
+#include <vector>
+
+using namespace llvm;
+using namespace dwarf;
+using namespace utils;
+
+namespace {
+
+TEST(DWARFUnitLRUCache, LRUSelection) {
+  Triple Triple = getNormalizedDefaultTargetTriple();
+  if (!isConfigurationSupported(Triple))
+    return;
+
+  // Create 5 compile units.
+  auto ExpectedDG = dwarfgen::Generator::create(Triple, 4);
+  ASSERT_THAT_EXPECTED(ExpectedDG, Succeeded());
+  dwarfgen::Generator *DG = ExpectedDG.get().get();
+  for (int i = 0; i < 5; i++) {
+    DG->addCompileUnit();
+  }
+  StringRef FileBytes = DG->generate();
+  MemoryBufferRef FileBuffer(FileBytes, "dwarf");
+  auto Obj = object::ObjectFile::createObjectFile(FileBuffer);
+  ASSERT_TRUE((bool)Obj);
+  std::unique_ptr<DWARFContext> Context = DWARFContext::create(**Obj);
+  std::vector<DWARFUnit *> CUs;
+  for (auto &CUPtr : Context->compile_units()) {
+    CUs.push_back(CUPtr.get());
+  }
+  ASSERT_EQ(CUs.size(), 5);
+
+  // Create a LRU cache of size 3.
+  DWARFUnitLRUCache Cache(3);
+  DWARFUnit *LRU;
+
+  // Add 0.
+  // Before: []
+  // After: [0]
+  LRU = Cache.addUnitAndEvictLRU(CUs[0]);
+  ASSERT_EQ(LRU, nullptr);
+
+  // Add 1.
+  // Before: [0]
+  // After: [1, 0]
+  LRU = Cache.addUnitAndEvictLRU(CUs[1]);
+  ASSERT_EQ(LRU, nullptr);
+
+  // Add 2.
+  // Before: [1, 0]
+  // After: [2, 1, 0]
+  LRU = Cache.addUnitAndEvictLRU(CUs[2]);
+  ASSERT_EQ(LRU, nullptr);
+
+  // Add 3.
+  // Before: [2, 1, 0]
+  // After: [3, 2, 1]
+  LRU = Cache.addUnitAndEvictLRU(CUs[3]);
+  ASSERT_EQ(LRU, CUs[0]);
+
+  // Refer to 1.
+  // Before: [3, 2, 1]
+  // After: [1, 3, 2]
+  LRU = Cache.addUnitAndEvictLRU(CUs[1]);
+  ASSERT_EQ(LRU, nullptr);
+
+  // Add 4.
+  // Before: [1, 3, 2]
+  // After: [4, 1, 3]
+  LRU = Cache.addUnitAndEvictLRU(CUs[4]);
+  ASSERT_EQ(LRU, CUs[2]);
+
+  // Refer to 3.
+  // Before: [4, 1, 3]
+  // After: [3, 4, 1]
+  LRU = Cache.addUnitAndEvictLRU(CUs[3]);
+  ASSERT_EQ(LRU, nullptr);
+
+  // Add 0.
+  // Before: [3, 4, 1]
+  // After: [0, 3, 4]
+  LRU = Cache.addUnitAndEvictLRU(CUs[0]);
+  ASSERT_EQ(LRU, CUs[1]);
+
+  // Add 1.
+  // Before: [0, 3, 4]
+  // After: [1, 0, 3]
+  LRU = Cache.addUnitAndEvictLRU(CUs[1]);
+  ASSERT_EQ(LRU, CUs[4]);
+}
+
+} // end anonymous namespace