RVM
  1. RVM
  2. RVM-157

Space virtual address management (discontiguous spaces)

    Details

    • Type: Improvement Improvement
    • Status: Closed Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: MMTk
    • Labels:
      None
    • Number of attachments :
      3

      Description

      Copied from core list:

      Overview:

      • a "space" is defined as a region (contiguous or not) of memory managed under a single memory management policy
      • mapping between objects and spaces is a (very) performance critical feature of MMTk
      • these mappings may arise in write barriers (most critical) and the GC tracing loop (somewhat critical)
      • the two obvious approaches for such mappings are via a lookup or via an address range check (both currently supported)
      • we believe (though have not verified!) that lookups will be too expensive for really performance critical tasks (such as write barriers)
      • we use space identifiers to encode the mapping (either for use in the table look up or for unpacking and use in address range check)
      • the current implementation leverages some very nice optimizations in our opt compiler to achieve very good performance
      • MMTk is intended to support research, so we're not interested in ditching support for address range checking (contiguous spaces)
      • supporting dynamic address space mapping (ie moving the entire image around) is an important and slightly/somewhat related goal, but the biggest problem at the moment is bootimage relocatability

      Current design

      • two kinds of space supported by the design:
        a. contiguous spaces
      • identified in terms of an address range
      • address range statically defined in terms of size (either fraction or concrete)
      • spaces assigned address ranges at build time via class initializers
      • spaces may identify constraints (must be in high memory etc)
      • address space carved up based on constraints of spaces and ordering of initializers
        b. discontiguous spaces
      • comprised of 4MB chunks
      • identified via a table lookup
      • these two are intended to co-exist.
      • for example, the likely situation would be that a nursery would exist as a contiguous space in high memory and all otehr spaces would share the remaining address space via discontiguous spaces

      Current implementation

      • contiguous spaces are (obviously) fully supported
      • discontinuous spaces are not supported
      • mappings should work correctly already
      • main missing feature is a 4MB-granularity allocator with which to carve up available address space
      • this should not be hard to implement, using an instance of org.mmtk.utility.GenericFreeList managing 4MB address range chunks as its "unit"

      Future design

      • Daniel pointed out that we're currently conflating address range managment with space management
      • he suggests two layers:
        a. an address range manager which allocates "address ranges" which may have "holes" in them due to libraries or whatever
        b. spaces which are generally discontiguous and are associated with just one "address range"
      • spaces are allocated in 4MB chunks, but always from within the address range with which they are always associated
      • if a space was "solitary" (guaranteed to be the only occupant of the address range), then address range checks could be used to do the object - space mapping
      1. discontig.12.patch
        45 kB
        Steve Blackburn
      2. discontig.23.patch
        35 kB
        Steve Blackburn
      3. discontig.8.patch
        31 kB
        Steve Blackburn

        Activity

        Hide
        Peter Donald added a comment -

        I am not sure if I understand the implications of the proposed design (then again it could be my cold befuddled mind!).

        For discontiguous spaces, will it be possible for one space to expand and contract based on usage patterns. Restricting a space to a fixed address range would seem to limit this unless all spaces except the nursery cover the entire memory space (except the nursery address range and any library addresses).

        Another concern is how pinned objects will interact with non-pinned objects (if/when the RVM ever supports the pinning). Will pinned objects be managed by a separate space? Will the series of chunks (is the correct term Segment?) they are allocated in simply be holes that the virtual address manager deals with specially while they are live.

        Show
        Peter Donald added a comment - I am not sure if I understand the implications of the proposed design (then again it could be my cold befuddled mind!). For discontiguous spaces, will it be possible for one space to expand and contract based on usage patterns. Restricting a space to a fixed address range would seem to limit this unless all spaces except the nursery cover the entire memory space (except the nursery address range and any library addresses). Another concern is how pinned objects will interact with non-pinned objects (if/when the RVM ever supports the pinning). Will pinned objects be managed by a separate space? Will the series of chunks (is the correct term Segment?) they are allocated in simply be holes that the virtual address manager deals with specially while they are live.
        Hide
        Steve Blackburn added a comment -

        For discontiguous spaces, will it be possible for one space to expand and contract based on usage patterns.

        Not sure what you mean.

        There are two concepts of "size" w.r.t. spaces. a) the number of pages actually in use at any time, and b) the address space associated with the space.

        In both contiguous spaces and discontiguous spaces, a) is a dynamic property (it can and does expand and contract) and b) is a static property. The difference is that for a discontiguous spaces, b) is shared with other discontiguous spaces sharing the same address range.

        Restricting a space to a fixed address range would seem to limit this unless all spaces except the nursery cover the entire memory space (except the nursery address range and any library addresses).

        Perhaps my previous answer helped. There's nothing necessarily special about the nursery---it was just an example I gave which may have some restrictions (and would for our current generational collectors). In any case, reducing the number of fixed address ranges obviously increases flexibility. So if most discontiguous spaces shared one address range that would give most opportunity for dynamic load balancing of address space use.

        Another concern is how pinned objects will interact with non-pinned objects (if/when the RVM ever supports the pinning). Will pinned objects be managed by a separate space? Will the series of chunks (is the correct term Segment?) they are allocated in simply be holes that the virtual address manager deals with specially while they are live.

        Hmmm... I don't see the connection between pinning and this issue. We want to support pinning (I'm tinkering with it right now). Exactly how you do it depends a great deal on a) the pinning semantics we want to support (and there are many), and b) the GC policies we want to use to support it, but is (as far as I can see) entirely independent of whether the containing space is contiguous or discontiguous.

        Show
        Steve Blackburn added a comment - For discontiguous spaces, will it be possible for one space to expand and contract based on usage patterns. Not sure what you mean. There are two concepts of "size" w.r.t. spaces. a) the number of pages actually in use at any time, and b) the address space associated with the space. In both contiguous spaces and discontiguous spaces, a) is a dynamic property (it can and does expand and contract) and b) is a static property. The difference is that for a discontiguous spaces, b) is shared with other discontiguous spaces sharing the same address range. Restricting a space to a fixed address range would seem to limit this unless all spaces except the nursery cover the entire memory space (except the nursery address range and any library addresses). Perhaps my previous answer helped. There's nothing necessarily special about the nursery---it was just an example I gave which may have some restrictions (and would for our current generational collectors). In any case, reducing the number of fixed address ranges obviously increases flexibility. So if most discontiguous spaces shared one address range that would give most opportunity for dynamic load balancing of address space use. Another concern is how pinned objects will interact with non-pinned objects (if/when the RVM ever supports the pinning). Will pinned objects be managed by a separate space? Will the series of chunks (is the correct term Segment?) they are allocated in simply be holes that the virtual address manager deals with specially while they are live. Hmmm... I don't see the connection between pinning and this issue. We want to support pinning (I'm tinkering with it right now). Exactly how you do it depends a great deal on a) the pinning semantics we want to support (and there are many), and b) the GC policies we want to use to support it, but is (as far as I can see) entirely independent of whether the containing space is contiguous or discontiguous.
        Hide
        Peter Donald added a comment -

        Ignore comment about pinning - I am not sure what I was babbling about.

        The design works for wrt to virtual address management.

        I guess we will need to address the introduction of many more build time configuration parameters as I can easily imagine the scenario where;

        • we want to stay with existing arrangement
        • want most flexibility in managing memory allocation and thus almost all spaces but the nursery become overlapping
        • on 64 bit architectures where virtual address ranges are "cheap" make all spaces non overlapping
        Show
        Peter Donald added a comment - Ignore comment about pinning - I am not sure what I was babbling about. The design works for wrt to virtual address management. I guess we will need to address the introduction of many more build time configuration parameters as I can easily imagine the scenario where; we want to stay with existing arrangement want most flexibility in managing memory allocation and thus almost all spaces but the nursery become overlapping on 64 bit architectures where virtual address ranges are "cheap" make all spaces non overlapping
        Hide
        Steve Blackburn added a comment -

        This patch is a first cut at adding discontiguous spaces.

        Conspicuously missing are changes to FreeListPageResource to allow it to deal with discontiguous spaces. So only CopySpace and ImmortalSpace use discontiguous spaces for the moment. So SemiSpace uses discontiguous spaces, for example.

        To my surprise, initial performance testing showed a consistent small (0.5%) advantage on FastAdaptiveSemiSpace. I don't yet understand this.

        Show
        Steve Blackburn added a comment - This patch is a first cut at adding discontiguous spaces. Conspicuously missing are changes to FreeListPageResource to allow it to deal with discontiguous spaces. So only CopySpace and ImmortalSpace use discontiguous spaces for the moment. So SemiSpace uses discontiguous spaces, for example. To my surprise, initial performance testing showed a consistent small (0.5%) advantage on FastAdaptiveSemiSpace. I don't yet understand this.
        Steve Blackburn made changes -
        Field Original Value New Value
        Attachment discontig.8.patch [ 29124 ]
        Hide
        Steve Blackburn added a comment -

        I have finished a first cut at discontiguous spaces. With this, we now only use contiguous spaces for the nursery---all other myriad spaces are interleaved in virtual memory now (immortal, raw pages, LOS, mature space, etc).

        This patch (against 13397) has a number of obvious shortcomings:

        1. It is not extensively tested
        2. It is very inefficient in generation page allocation maps for each discontiguous FreeListPageResource (it creates a map for each instance which covers the entire possible space, which is grossly redundant).

        I've run some perf regressions on DaCapo and seen that it is robust in that setting and actually performs quite well, with the notable exception of a regression on jython whereby we do 30% extra GCs. This is presumably due to a bug in my approach.

        I discussed 2. above with Robin and Daniel. Daniel has previously proposed injecting another layer of abstraction to the design of spaces etc, whereby virtual memory segmentation is shifted to a high level of abstraction. Virtual memory is carved up into vm regions and then spaces are associated with these, either contiguously or discontiguously, but nonetheless, constrained to a single vm region. This seems like a good approach, adn I think we should attack it in the short to medium term. Therefore I think the inefficiency in 2. above is fine because that whole issue would be treated entirely differently under the new arrangement. I prefer not to invest time polishing up a perfect solution to 2 if we know the premise is bad and that a better approach is in our sights.

        Anyway, I'll try to get back to this soon, but the patch is here so if any one is chaffing at the bit to do this and doesn't want to wait for me, they can at least take a look at a first cut solution....

        Show
        Steve Blackburn added a comment - I have finished a first cut at discontiguous spaces. With this, we now only use contiguous spaces for the nursery---all other myriad spaces are interleaved in virtual memory now (immortal, raw pages, LOS, mature space, etc). This patch (against 13397) has a number of obvious shortcomings: 1. It is not extensively tested 2. It is very inefficient in generation page allocation maps for each discontiguous FreeListPageResource (it creates a map for each instance which covers the entire possible space, which is grossly redundant). I've run some perf regressions on DaCapo and seen that it is robust in that setting and actually performs quite well, with the notable exception of a regression on jython whereby we do 30% extra GCs. This is presumably due to a bug in my approach. I discussed 2. above with Robin and Daniel. Daniel has previously proposed injecting another layer of abstraction to the design of spaces etc, whereby virtual memory segmentation is shifted to a high level of abstraction. Virtual memory is carved up into vm regions and then spaces are associated with these, either contiguously or discontiguously, but nonetheless, constrained to a single vm region. This seems like a good approach, adn I think we should attack it in the short to medium term. Therefore I think the inefficiency in 2. above is fine because that whole issue would be treated entirely differently under the new arrangement. I prefer not to invest time polishing up a perfect solution to 2 if we know the premise is bad and that a better approach is in our sights. Anyway, I'll try to get back to this soon, but the patch is here so if any one is chaffing at the bit to do this and doesn't want to wait for me, they can at least take a look at a first cut solution....
        Steve Blackburn made changes -
        Attachment discontig.12.patch [ 29202 ]
        Hide
        Steve Blackburn added a comment -

        This patch still needs some cleaning up and straightening out, but I think it's fairly close to being ready to commit.

        Unfortunately I've timed out for today.

        Show
        Steve Blackburn added a comment - This patch still needs some cleaning up and straightening out, but I think it's fairly close to being ready to commit. Unfortunately I've timed out for today.
        Steve Blackburn made changes -
        Attachment discontig.23.patch [ 29348 ]
        Hide
        Steve Blackburn added a comment -

        Closed in r13626

        Show
        Steve Blackburn added a comment - Closed in r13626
        Steve Blackburn made changes -
        Status Open [ 1 ] Closed [ 6 ]
        Resolution Fixed [ 1 ]

          People

          • Assignee:
            Daniel Frampton
            Reporter:
            Daniel Frampton
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved: