bulk_move in ttm_resource manager

bulk_move in ttm_resource manager

[Zeng, Oak]

[-- Attachment #1: Type: text/plain, Size: 1397 bytes --]

Hi Christian,

As a follow up to this thread: https://www.spinics.net/lists/dri-devel/msg410740.html, I started the work of moving the lru out of ttm_resource_manager and make it a common library for both ttm and svm. While look into the details of the bulk_move in ttm resource manager, I found a potential problem:

For simplicity, let's say we only have one memory type and one priority, so ttm resource manager only maintains one global lru list. Let's say this list has 10 nodes, node1 to node10.

But the lru_bulk_move is per vm. Let's say vm1 has a bulk_move covering node range [node4, node7] and vm2 has a bulk_move covering node range [node6, node9]. Notice those two range has an overlap. Since two vm can simultaneously add nodes to lru, I think this scenario can happen.

Now if we perform a bulk move for vm1, moving [node4, node7] to the tail of the lru list. The lru after this bulk move will be: node1, node2, node3,node8, node9, node10, node4, node5, node6, node7. Now notice that for vm2's bulk_move, the first pointer  (pointing to node6) is actually after the last pointer (pointing to node9), which doesn't make sense.

Is this a real problem? As I understand it, with this issue, we only mess up the lru list order, but there won't be any functional problem. If it is a real problem, should we make the bulk_move global instead of per vm based?

Thanks,
Oak


[-- Attachment #2: Type: text/html, Size: 3842 bytes --]

Re: bulk_move in ttm_resource manager

[Thomas Hellström]

On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
> Hi Christian,
>  
> As a follow up to this thread:
> https://www.spinics.net/lists/dri-devel/msg410740.html, I started the
> work of moving the lru out of ttm_resource_manager and make it a
> common library for both ttm and svm. While look into the details of
> the bulk_move in ttm resource manager, I found a potential problem:
>  
> For simplicity, let’s say we only have one memory type and one
> priority, so ttm resource manager only maintains one global lru list.
> Let’s say this list has 10 nodes, node1 to node10.
>  
> But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
> covering node range [node4, node7] and vm2 has a bulk_move covering
> node range [node6, node9]. Notice those two range has an overlap.
> Since two vm can simultaneously add nodes to lru, I think this
> scenario can happen.
>  
> Now if we perform a bulk move for vm1, moving [node4, node7] to the
> tail of the lru list. The lru after this bulk move will be: node1,
> node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
> notice that for vm2’s bulk_move, the first pointer  (pointing to
> node6) is actually after the last pointer (pointing to node9), which
> doesn’t make sense.
>  
> Is this a real problem? As I understand it, with this issue, we only
> mess up the lru list order, but there won’t be any functional
> problem. If it is a real problem, should we make the bulk_move global
> instead of per vm based?
>  
> Thanks,
> Oak
>  

FWIW I have a patch set that converts the TTM bulk move code to using
sublists; a list item is either a resource or a sublist, and when
performing a bulk move essentially the sublist is moved. Bumping
resource LRU within a VM would touch only the sublist.

Currently functionality and TTM API is essentially the same but when
experimenting with LRU traversal for exhaustive WW-locking eviction
this concept was easier to use. Also hopefully this would reduce
fragility and improve understanding since a scenario like the above
could really never happen...

Let me know if I should send it out as an RFC.

Code is here:
https://gitlab.freedesktop.org/drm/xe/kernel/-/merge_requests/351/commits

/Thomas

Re: bulk_move in ttm_resource manager

[Christian König]

Am 04.10.23 um 09:17 schrieb Thomas Hellström:
> On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
>> Hi Christian,
>>   
>> As a follow up to this thread:
>> https://www.spinics.net/lists/dri-devel/msg410740.html, I started the
>> work of moving the lru out of ttm_resource_manager and make it a
>> common library for both ttm and svm. While look into the details of
>> the bulk_move in ttm resource manager, I found a potential problem:
>>   
>> For simplicity, let’s say we only have one memory type and one
>> priority, so ttm resource manager only maintains one global lru list.
>> Let’s say this list has 10 nodes, node1 to node10.
>>   
>> But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
>> covering node range [node4, node7] and vm2 has a bulk_move covering
>> node range [node6, node9]. Notice those two range has an overlap.
>> Since two vm can simultaneously add nodes to lru, I think this
>> scenario can happen.

That can't happen. See what ttm_resource_move_to_lru_tail() does when 
the BO has a bulk move associated with it.

>>   
>> Now if we perform a bulk move for vm1, moving [node4, node7] to the
>> tail of the lru list. The lru after this bulk move will be: node1,
>> node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
>> notice that for vm2’s bulk_move, the first pointer  (pointing to
>> node6) is actually after the last pointer (pointing to node9), which
>> doesn’t make sense.
>>   
>> Is this a real problem? As I understand it, with this issue, we only
>> mess up the lru list order, but there won’t be any functional
>> problem. If it is a real problem, should we make the bulk_move global
>> instead of per vm based?
>>   
>> Thanks,
>> Oak
>>   
> FWIW I have a patch set that converts the TTM bulk move code to using
> sublists; a list item is either a resource or a sublist, and when
> performing a bulk move essentially the sublist is moved. Bumping
> resource LRU within a VM would touch only the sublist.

That sounds like my very first attempt at bulk moves which we abandoned 
for various reasons.

That's easily >5years ago, but the history of that should still be on 
the mailing list if I'm not completely mistaken.

Regards,
Christian.

>
> Currently functionality and TTM API is essentially the same but when
> experimenting with LRU traversal for exhaustive WW-locking eviction
> this concept was easier to use. Also hopefully this would reduce
> fragility and improve understanding since a scenario like the above
> could really never happen...
>
> Let me know if I should send it out as an RFC.
>
> Code is here:
> https://gitlab.freedesktop.org/drm/xe/kernel/-/merge_requests/351/commits
>
> /Thomas
>
>
>
>
>

RE: bulk_move in ttm_resource manager

[Zeng, Oak]

> -----Original Message-----
> From: Christian König <christian.koenig@amd.com>
> Sent: Wednesday, October 4, 2023 8:45 AM
> To: Thomas Hellström <thomas.hellstrom@linux.intel.com>; Zeng, Oak
> <oak.zeng@intel.com>
> Cc: intel-xe@lists.freedesktop.org; dri-devel@lists.freedesktop.org
> Subject: Re: bulk_move in ttm_resource manager
> 
> Am 04.10.23 um 09:17 schrieb Thomas Hellström:
> > On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
> >> Hi Christian,
> >>
> >> As a follow up to this thread:
> >> https://www.spinics.net/lists/dri-devel/msg410740.html, I started the
> >> work of moving the lru out of ttm_resource_manager and make it a
> >> common library for both ttm and svm. While look into the details of
> >> the bulk_move in ttm resource manager, I found a potential problem:
> >>
> >> For simplicity, let’s say we only have one memory type and one
> >> priority, so ttm resource manager only maintains one global lru list.
> >> Let’s say this list has 10 nodes, node1 to node10.
> >>
> >> But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
> >> covering node range [node4, node7] and vm2 has a bulk_move covering
> >> node range [node6, node9]. Notice those two range has an overlap.
> >> Since two vm can simultaneously add nodes to lru, I think this
> >> scenario can happen.
> 
> That can't happen. See what ttm_resource_move_to_lru_tail() does when
> the BO has a bulk move associated with it.

I spent more time reading the codes and I am convinced the codes guarantee all nodes in a bulk move range are all belongs to one vm. Yes each time when we add a node to bulk move range, ttm_resource_move_to_lru_tail (and other helpers such as ttm_resource_add_bulk_move) moves the newly added node to the tail of bulk move. When the first node is added to the bulk move, the first and last pointer of the bulk move both point to the same first node - this is the initial condition that nodes in a bulk move are not separated. Eventually when new nodes are added, we always move them to the tail of the bulk move. So after the move, all nodes in a bulk move are still not separated (by nodes from other vm). 

I doubt whether this implementation of bulk move can actually cut LRU maintenance overhead. Even though we can move bulk nodes at once at the end, but when *each* node are added to LRU or moved in LRU, we moved them to the tail of bulk move range due to above bulk move restriction(when bulk move is enabled) - this is already link list operation. Why not just add node to the tail of LRU, or just move node to LRU tail when node is touched by GPU?
 
> 
> >>
> >> Now if we perform a bulk move for vm1, moving [node4, node7] to the
> >> tail of the lru list. The lru after this bulk move will be: node1,
> >> node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
> >> notice that for vm2’s bulk_move, the first pointer  (pointing to
> >> node6) is actually after the last pointer (pointing to node9), which
> >> doesn’t make sense.
> >>
> >> Is this a real problem? As I understand it, with this issue, we only
> >> mess up the lru list order, but there won’t be any functional
> >> problem. If it is a real problem, should we make the bulk_move global
> >> instead of per vm based?
> >>
> >> Thanks,
> >> Oak
> >>
> > FWIW I have a patch set that converts the TTM bulk move code to using
> > sublists; a list item is either a resource or a sublist, and when
> > performing a bulk move essentially the sublist is moved. Bumping
> > resource LRU within a VM would touch only the sublist.
> 
> That sounds like my very first attempt at bulk moves which we abandoned
> for various reasons.
> 
> That's easily >5years ago, but the history of that should still be on
> the mailing list if I'm not completely mistaken.

So for my refactor work, I plan to do it based on the current upstream implementation. I will revisit if we end up using the sublists.

Regards,
Oak

> 
> Regards,
> Christian.
> 
> >
> > Currently functionality and TTM API is essentially the same but when
> > experimenting with LRU traversal for exhaustive WW-locking eviction
> > this concept was easier to use. Also hopefully this would reduce
> > fragility and improve understanding since a scenario like the above
> > could really never happen...
> >
> > Let me know if I should send it out as an RFC.
> >
> > Code is here:
> > https://gitlab.freedesktop.org/drm/xe/kernel/-
> /merge_requests/351/commits
> >
> > /Thomas
> >
> >
> >
> >
> >

Re: bulk_move in ttm_resource manager

[Thomas Hellström]

On Wed, 2023-10-04 at 14:44 +0200, Christian König wrote:
> Am 04.10.23 um 09:17 schrieb Thomas Hellström:
> > On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
> > > Hi Christian,
> > >   
> > > As a follow up to this thread:
> > > https://www.spinics.net/lists/dri-devel/msg410740.html, I started
> > > the
> > > work of moving the lru out of ttm_resource_manager and make it a
> > > common library for both ttm and svm. While look into the details
> > > of
> > > the bulk_move in ttm resource manager, I found a potential
> > > problem:
> > >   
> > > For simplicity, let’s say we only have one memory type and one
> > > priority, so ttm resource manager only maintains one global lru
> > > list.
> > > Let’s say this list has 10 nodes, node1 to node10.
> > >   
> > > But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
> > > covering node range [node4, node7] and vm2 has a bulk_move
> > > covering
> > > node range [node6, node9]. Notice those two range has an overlap.
> > > Since two vm can simultaneously add nodes to lru, I think this
> > > scenario can happen.
> 
> That can't happen. See what ttm_resource_move_to_lru_tail() does when
> the BO has a bulk move associated with it.
> 
> > >   
> > > Now if we perform a bulk move for vm1, moving [node4, node7] to
> > > the
> > > tail of the lru list. The lru after this bulk move will be:
> > > node1,
> > > node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
> > > notice that for vm2’s bulk_move, the first pointer  (pointing to
> > > node6) is actually after the last pointer (pointing to node9),
> > > which
> > > doesn’t make sense.
> > >   
> > > Is this a real problem? As I understand it, with this issue, we
> > > only
> > > mess up the lru list order, but there won’t be any functional
> > > problem. If it is a real problem, should we make the bulk_move
> > > global
> > > instead of per vm based?
> > >   
> > > Thanks,
> > > Oak
> > >   
> > FWIW I have a patch set that converts the TTM bulk move code to
> > using
> > sublists; a list item is either a resource or a sublist, and when
> > performing a bulk move essentially the sublist is moved. Bumping
> > resource LRU within a VM would touch only the sublist.
> 
> That sounds like my very first attempt at bulk moves which we
> abandoned 
> for various reasons.
> 
> That's easily >5years ago, but the history of that should still be on
> the mailing list if I'm not completely mistaken.

This here?

https://lists.freedesktop.org/archives/amd-gfx/2018-August/025016.html

No, in that case it's very different. Or is it an even earlier version?

/Thomas


> 
> Regards,
> Christian.
> 
> > 
> > Currently functionality and TTM API is essentially the same but
> > when
> > experimenting with LRU traversal for exhaustive WW-locking eviction
> > this concept was easier to use. Also hopefully this would reduce
> > fragility and improve understanding since a scenario like the above
> > could really never happen...
> > 
> > Let me know if I should send it out as an RFC.
> > 
> > Code is here:
> > https://gitlab.freedesktop.org/drm/xe/kernel/-/merge_requests/351/commits
> > 
> > /Thomas
> > 
> > 
> > 
> > 
> > 
> 

Re: bulk_move in ttm_resource manager

[Christian König]

Am 05.10.23 um 10:36 schrieb Thomas Hellström:
> On Wed, 2023-10-04 at 14:44 +0200, Christian König wrote:
>> Am 04.10.23 um 09:17 schrieb Thomas Hellström:
>>> On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
>>>> Hi Christian,
>>>>    
>>>> As a follow up to this thread:
>>>> https://www.spinics.net/lists/dri-devel/msg410740.html, I started
>>>> the
>>>> work of moving the lru out of ttm_resource_manager and make it a
>>>> common library for both ttm and svm. While look into the details
>>>> of
>>>> the bulk_move in ttm resource manager, I found a potential
>>>> problem:
>>>>    
>>>> For simplicity, let’s say we only have one memory type and one
>>>> priority, so ttm resource manager only maintains one global lru
>>>> list.
>>>> Let’s say this list has 10 nodes, node1 to node10.
>>>>    
>>>> But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
>>>> covering node range [node4, node7] and vm2 has a bulk_move
>>>> covering
>>>> node range [node6, node9]. Notice those two range has an overlap.
>>>> Since two vm can simultaneously add nodes to lru, I think this
>>>> scenario can happen.
>> That can't happen. See what ttm_resource_move_to_lru_tail() does when
>> the BO has a bulk move associated with it.
>>
>>>>    
>>>> Now if we perform a bulk move for vm1, moving [node4, node7] to
>>>> the
>>>> tail of the lru list. The lru after this bulk move will be:
>>>> node1,
>>>> node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
>>>> notice that for vm2’s bulk_move, the first pointer  (pointing to
>>>> node6) is actually after the last pointer (pointing to node9),
>>>> which
>>>> doesn’t make sense.
>>>>    
>>>> Is this a real problem? As I understand it, with this issue, we
>>>> only
>>>> mess up the lru list order, but there won’t be any functional
>>>> problem. If it is a real problem, should we make the bulk_move
>>>> global
>>>> instead of per vm based?
>>>>    
>>>> Thanks,
>>>> Oak
>>>>    
>>> FWIW I have a patch set that converts the TTM bulk move code to
>>> using
>>> sublists; a list item is either a resource or a sublist, and when
>>> performing a bulk move essentially the sublist is moved. Bumping
>>> resource LRU within a VM would touch only the sublist.
>> That sounds like my very first attempt at bulk moves which we
>> abandoned
>> for various reasons.
>>
>> That's easily >5years ago, but the history of that should still be on
>> the mailing list if I'm not completely mistaken.
> This here?
>
> https://lists.freedesktop.org/archives/amd-gfx/2018-August/025016.html
>
> No, in that case it's very different. Or is it an even earlier version?

No, that was even earlier. Basically the first version I discussed with 
Chunming.

The issue was simple that when you have a hierarchically LRU you also 
need a multi layer cursor and make sure that you have a single lock for 
everything.

This is multi layer cursor is complicated to implement and contradicts 
the idea that we want to walk the LRU with anchors and dropping locks in 
between (not that we ever implemented that, but it would still be nice 
to have).

In general when you use some hierarchical LRU you just move the 
complexity from the insert function to the walk function. And I don't 
think we would win much with that.

Regards,
Christian.

>
> /Thomas
>
>
>> Regards,
>> Christian.
>>
>>> Currently functionality and TTM API is essentially the same but
>>> when
>>> experimenting with LRU traversal for exhaustive WW-locking eviction
>>> this concept was easier to use. Also hopefully this would reduce
>>> fragility and improve understanding since a scenario like the above
>>> could really never happen...
>>>
>>> Let me know if I should send it out as an RFC.
>>>
>>> Code is here:
>>> https://gitlab.freedesktop.org/drm/xe/kernel/-/merge_requests/351/commits
>>>
>>> /Thomas
>>>
>>>
>>>
>>>
>>>

Re: bulk_move in ttm_resource manager

[Thomas Hellström]

On 10/5/23 12:44, Christian König wrote:
> Am 05.10.23 um 10:36 schrieb Thomas Hellström:
>> On Wed, 2023-10-04 at 14:44 +0200, Christian König wrote:
>>> Am 04.10.23 um 09:17 schrieb Thomas Hellström:
>>>> On Wed, 2023-10-04 at 03:52 +0000, Zeng, Oak wrote:
>>>>> Hi Christian,
>>>>>    As a follow up to this thread:
>>>>> https://www.spinics.net/lists/dri-devel/msg410740.html, I started
>>>>> the
>>>>> work of moving the lru out of ttm_resource_manager and make it a
>>>>> common library for both ttm and svm. While look into the details
>>>>> of
>>>>> the bulk_move in ttm resource manager, I found a potential
>>>>> problem:
>>>>>    For simplicity, let’s say we only have one memory type and one
>>>>> priority, so ttm resource manager only maintains one global lru
>>>>> list.
>>>>> Let’s say this list has 10 nodes, node1 to node10.
>>>>>    But the lru_bulk_move is per vm. Let’s say vm1 has a bulk_move
>>>>> covering node range [node4, node7] and vm2 has a bulk_move
>>>>> covering
>>>>> node range [node6, node9]. Notice those two range has an overlap.
>>>>> Since two vm can simultaneously add nodes to lru, I think this
>>>>> scenario can happen.
>>> That can't happen. See what ttm_resource_move_to_lru_tail() does when
>>> the BO has a bulk move associated with it.
>>>
>>>>>    Now if we perform a bulk move for vm1, moving [node4, node7] to
>>>>> the
>>>>> tail of the lru list. The lru after this bulk move will be:
>>>>> node1,
>>>>> node2, node3,node8,node9, node10, node4, node5, node6, node7. Now
>>>>> notice that for vm2’s bulk_move, the first pointer  (pointing to
>>>>> node6) is actually after the last pointer (pointing to node9),
>>>>> which
>>>>> doesn’t make sense.
>>>>>    Is this a real problem? As I understand it, with this issue, we
>>>>> only
>>>>> mess up the lru list order, but there won’t be any functional
>>>>> problem. If it is a real problem, should we make the bulk_move
>>>>> global
>>>>> instead of per vm based?
>>>>>    Thanks,
>>>>> Oak
>>>> FWIW I have a patch set that converts the TTM bulk move code to
>>>> using
>>>> sublists; a list item is either a resource or a sublist, and when
>>>> performing a bulk move essentially the sublist is moved. Bumping
>>>> resource LRU within a VM would touch only the sublist.
>>> That sounds like my very first attempt at bulk moves which we
>>> abandoned
>>> for various reasons.
>>>
>>> That's easily >5years ago, but the history of that should still be on
>>> the mailing list if I'm not completely mistaken.
>> This here?
>>
>> https://lists.freedesktop.org/archives/amd-gfx/2018-August/025016.html
>>
>> No, in that case it's very different. Or is it an even earlier version?
>
> No, that was even earlier. Basically the first version I discussed 
> with Chunming.
>
> The issue was simple that when you have a hierarchically LRU you also 
> need a multi layer cursor and make sure that you have a single lock 
> for everything.
>
> This is multi layer cursor is complicated to implement and contradicts 
> the idea that we want to walk the LRU with anchors and dropping locks 
> in between (not that we ever implemented that, but it would still be 
> nice to have).
>
Yes, that's sort of what I was trying to implement, although rather list 
permutating so that list items already iterated over end up last in some 
sense. And indeed the iterator gets slightly more complicated, but not 
much really.

> In general when you use some hierarchical LRU you just move the 
> complexity from the insert function to the walk function. And I don't 
> think we would win much with that.

There's also a gain in list_move() simplicity and maintainability, since 
the bulk pos last-and-first become self-adjusting..

But anyway, this is currently on lower priority, so if / when I come up 
with something I'll send anything that changes bulk lru structures last 
so it can be left out if needed.

Thanks,

Thomas


>
> Regards,
> Christian.
>
>>
>> /Thomas
>>
>>
>>> Regards,
>>> Christian.
>>>
>>>> Currently functionality and TTM API is essentially the same but
>>>> when
>>>> experimenting with LRU traversal for exhaustive WW-locking eviction
>>>> this concept was easier to use. Also hopefully this would reduce
>>>> fragility and improve understanding since a scenario like the above
>>>> could really never happen...
>>>>
>>>> Let me know if I should send it out as an RFC.
>>>>
>>>> Code is here:
>>>> https://gitlab.freedesktop.org/drm/xe/kernel/-/merge_requests/351/commits 
>>>>
>>>>
>>>> /Thomas
>>>>
>>>>
>>>>
>>>>
>>>>
>