lkml.org 
[lkml]   [2023]   [Jul]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: Maple Tree Work
From


在 2023/7/13 23:36, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230713 04:05]:
>>
>>
>> 在 2023/7/12 23:27, Liam R. Howlett 写道:
>>> Dropping Danilo from the Cc..
>>>
>>> I was asked to add linux-mm to the list, so I did that as well.
>>>
>>> If anyone else is interested in seeing the full list, it's on lkml [1] and
>>> the maple-tree list [2].
>>>
>>> Thank you Peng for looking at the list and taking time to think about
>>> the items.
>>>
>>> * Peng Zhang <zhangpeng.00@bytedance.com> [230712 07:49]:
>>>>
>>>>
>>>> 在 2023/7/8 00:38, Liam R. Howlett 写道:
>>>>> - Fork & Dup tree + Delete DONT_COPY
>>>>> This is to optimize dup_mmap() in kernel/fork.c, but other
>>>>> users may want faster duplications of a tree.
>>>>> This should be faster than building a tree in bulk mode. The
>>>>> idea is to just copy each node and replace the pointers in,
>>>>> probably, a BFS order. Once the leaves are reached, the VMAs
>>>>> will be replaced by the copies made in fork, unless DONT_COPY is
>>>>> set, in which case the VMA will be deleted from the copied tree.
>>>>> DONT_COPY is not common and since the tree isn't visible, all
>>>>> nodes should be available for reuse (no RCU worries).
>>>> If DONT_COPY is set, this method will be complicated, because the gaps
>>>> adjacent to it need to be merged, and the gaps of all ancestor nodes need to
>>>> be updated.
>>>
>>> My understanding is that this is a rare event; there aren't many VMAs
>>> marked this way. The store operation already does all the necessary
>>> work for deleting an entry. The gap tracking is also updated, and that
>>> would only happen if the new gap is larger. Are you concerned about the
>>> performance/runtime of handling the DONT_COPY in this way?
>> Yes, if no DONT_COPY is set, copying all nodes and replacing the
>> pointers must be the fastest way. I was just thinking if there is
>> a faster way if DONT_COPY exists. Using the store operation to
>> delete unnecessary entries will cause additional overhead sometimes.
>> To give an example:
>>
>> Suppose a leaf node layout of the maple tree is as follows:
>> [VMA1][VMA2][NULL][VMA3]
>>
>> If VMA2 has DONT_COPY set, we need to change the node layout as
>> follows to delete it:
>> [VMA1'][NULL][VMA3']
>>
>> At least we need to copy this node to replace it to make this
>> delete operation, even need to rebalance. However, this is a
>> rare case. In most cases, there is no gap between VMAs, so it
>> will not cause changes in the node layout.
>
> Remember that at this point, there is no readers so we could edit the
> node without a copy. It would require new code, but it's just moving
> data left.. The bigger worry is a rebalance, as you said, and that can
> get complicated. We know we have (more than) enough room to store the
> data, but editing in place isn't done in this version of the code. We
> do allow for node re-use by pushing back onto the mas->alloc, so the
> data requirements won't be too high. Without any readers, the parent
> pivots could be changed directly between two leaves.
>
>>>
>>>>
>>>> I have another idea to build a tree, if inserted in order, we only
>>>> insert at the leaf node. All leaf nodes are connected using a linked
>>>> list. In the end we get a linked list with only leaf nodes. Then we
>>>> construct non-leaf nodes layer by layer from bottom to top. I think
>>>> this is also faster than bulk mode. Another advantage of this method
>>>> is that we are applicable to more scenarios, do not need the original
>>>> tree, only need to know the ranges inserted in order. I don't know
>>>> how fast this method is, so we can discuss it.
>>>
>>> What is the advantage of a linked list over just building the tree as
>>> you go? Considering the non-leaf nodes are just a list of nodes
>>> already, and you will have to do the same work of setting pivots,
>>> allocating nodes, and filling them after you have the linked list.
>>>
>>> What work do you avoid that would make a linked list faster than bulk
>>> insert or a tree copy/replace VMAs? I was thinking that we could avoid
>>> a lot of the work involved with splitting/pushing and the parent
>>> construction by using memcpy of each node, replace each slot (and
>>> parent) with a new memcpy of the mirrored tree, then have a minimum
>>> amount of modifications to delete the DONT_COPY during the VMA
>>> replacement. BFS copy would ensure we wouldn't modify the source tree
>>> during VMA replacement and deletion (DONT_COPY). So the rebalancing (in
>>> bulk insert), pivot calculations, metadata, and gaps are (mostly) saved
>>> by using memcpy.
>> Your analysis is correct.
>>>
>>> From what I understand from your linked list idea, we would need to
>>> construct the child node by examining each entry and know that a certain
>>> entry is a DONT_COPY (ie: VMA logic would be needed in the maple tree
>>> code or a callback?). We really can't have VMA logic in the maple tree
>>> code, so we could do some sort of loop through the VMAs to add the entry
>>> to the list if desired.
>>>
>>> Once we have a linked list, we still need to figure out each pivot for
>>> the parent (I guess we won't use the last slot so there is a pivot to
>>> check?), and each max gap in each child to construct the upper layers
>>> of the tree. Is this correct?
>>>
>>> I guess we would still need to adjust the last node to ensure sufficient
>>> entries as well, so as we add items we may need to rebalance the last
>>> leaf with the second-last leaf.
>> Yes, the last two leaves need to check to make sure they have enough
>> items.
>>>
>>> The bulk store currently adjusts the split to favour splitting
>>> left, could you get the same result by strictly filling the nodes? This
>>> would have to have special handling to rebalance the last one - which we
>>> have a pretty good idea of when it's going to happen as we have a count
>>> (and the DONT_COPY is rare).
>>>
>>> Are you thinking you could compact the tree at the same time to gain
>>> efficiency?
>>>
>>> What would you consider a sufficient packed tree? It's best to keep
>>> some space around for expansion/contraction. This works out since, I
>>> think, we would need to keep that last slot free so we have a pivot to
>>> check in your linked list plan. Initial development with strict
>>> split/join rules resulted in a 'jittering' of nodes as the number of
>>> entries in a node shifted just above/below the threshold so we relaxed
>>> the merging of nodes to avoid such a scenario.
>> We can control the number of entries of nodes, for example, let this
>> number be (min + max)/2, so as to avoid making a node too 'dense' or
>> too 'loose'.
>
> By the way, in the VMA case, we also know the number of VMAs in the
> tree. Unfortunately, we don't know how many are DONT_COPY VMAs. I
> wonder if it would be worth while to balance each VMA with its neighbour
> during this operation, at least within one tree level? It would reduce
> the possibility of a larger rebalance on a DONT_COPY. It's probably not
> worth it because it would slow down our fast path.
>
>>>
>>> Let me know if you would like me to put your name beside the Fork & Dup
>>> Tree item in the list of work.
>> You can put my name on this one and I'll do it.
>
> Sounds good, thanks!
>
>> I use the method of copying all nodes, so I will implement an interface
>> to get a mirrored tree.
>>
>> But I can't think of a good way to replace old VMAs, it can't be done
>> during the copy tree process, because maybe some VMAs have DONT_COPY
>> flag.
>
> I think it could be done during the copy, instead of a 'replace' it
> would be a 'delete'. I think this is why we need to use a BFS-like
> duplication. So once we reach the leaves, then we can modify the tree
> knowing that the above state has already been copied and so it's going
> to be altering a copy of the data and so we are at a point where it can
> be mutated. You could detect that the lock-step next/insert is out of
> sync and delete the range between the old_mas and the new_mas.
>
>> It seems that we can only scan all VMAs in the source tree again
>> to update the new tree. We have already traversed the source tree once
>> in the process of copying the tree. Is there any way to avoid traversing
>> it again?
>
> Well, we haven't visited the VMAs in the copy, but we have visited the
> leaf nodes with all the pointers to the VMAs. I get what you are
> saying thought, we will have to duplicate the leaves then re-visit the
> leaves to replace the VMAs. I am not sure we can avoid this since a
> rebalance may occur, and it would be very tricky to rebalance with old
> and new data in the tree - it's probably best to just revisit, at least
> to begin with.
>
> Depending on how you implement it, you could make the copying of the
> tree end on the first leaf node by using the height of the tree to
> figure out which way to sweep (left to right or right to left) on the
> first level. Not strictly BFS, but you could end the maple state in the
> correct location to start replacing the VMAs. Would that work?
>
> We also have a reverse iterator, so we could just run through the tree
> from the right-most node to the start.
>
> I was thinking that we would make the first 'duplication store' detect
> an empty tree and duplicate the tree, ending on the left-most leaf and
> then replace the first entry (and possibly delete up to the first
> store). Each subsequent store would do the same. We would need a
> 'duplication complete' that would remove any entries beyond the last
> store and rebalance, if necessary.
>
> Feel free to use some or none of the ideas. I hope some of this helps
> with what you are trying to work out. Let me know if you have any more
> questions.
Thank you for providing so much information, I am doing this feature.

Thanks,
Peng
>
> Thanks,
> Liam
>

\
 
 \ /
  Last update: 2023-07-16 20:50    [W:0.068 / U:0.724 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site