Re: [PATCH v3 2/3] cgroup/rstat: Optimize cgroup_rstat_updated_list()

[Yosry Ahmed]

> >>>>     *
> >>>>     * The only ordering guarantee is that, for a parent and a child pair
> >>>> - * covered by a given traversal, if a child is visited, its parent is
> >>>> - * guaranteed to be visited afterwards.
> >>>> + * covered by a given traversal, the child is before its parent in
> >>>> + * the list.
> >>>> + *
> >>>> + * Note that updated_children is self terminated while updated_next is
> >>>> + * parent cgroup terminated except the cgroup root which can be self
> >>>> + * terminated.
> >>> IIUC updated_children and updated_next is the same list.
> >>> updated_children is the head, and updated_next is how the list items
> >>> are linked. This comment makes it seem like they are two different
> >>> lists.
> >> Thanks for the comment. I will rework the comment to clarify that a bit
> >> more.
> >>> I am actually wondering if it's worth using the singly linked list
> >>> here. We are saving 8 bytes percpu, but the semantics are fairly
> >>> confusing. Wouldn't this be easier to reason about if you just use
> >>> list_head?
> >>>
> >>> updated_children would be replaced with LIST_HEAD (or similar), and
> >>> the list would be NULL terminated instead of terminated by self/parent
> >>> cgroup. IIUC the reason it's not NULL-terminated now is because we use
> >>> cgroup->updated_next to check quickly if a cgroup is on the list or
> >>> not. If we use list_heads, we can just use list_emtpy() IIUC.
> >>>
> >>> We can also simplify the semantics of unlinking @root from the updated
> >>> tree below, it would just be list_del() IIUC, which is actually more
> >>> performant as well. It seems like overall we would simplify a lot of
> >>> things. When forming the updated_list, we can just walk the tree and
> >>> splice the lists in the correct order.
> >>>
> >>> It seems to me that saving 8 bytes percpu is not worth the complexity
> >>> of the custom list semantics here. Am I missing something here?
> >> It will cost an additional 16 bytes of percpu memory if converted to
> >> list_heads. Like other lists, there will be sibling and children
> >> list_heads. There are also 2 pointers to update instead of one. Anyway,
> >> I don't have an objection to convert them to list_heads if agreed by Tejun.
> > Yes you are right. It's definitely not free, but it's also not super
> > costly. It's just that every time I look at the rstat code I need to
> > remind myself of how updated_next and updated_children work. I will
> > let Tejun decide.
>
> After further thought, changing it to list_head may not be possible with
> the current design since the actual linkage is like:
>
> update_next -> cgroup + cpu --> update_next --> ...
>
> So unless we change the design to link cgroup_rstat_cpu directly to each
> other for a given CPU, not via a cgroup intermediary, we will not be
> able to use list_head and the associated list_add() & list_del() macros.
> Direct linkage, however, requires a cgroup back pointer. So the real
> cost will be 24 bytes instead.

Yes you are right. Perhaps it's not worth it and it may not be as
simple as I thought. Please dismiss this suggestion, we'll have to
rely on comments for now to keep things clear.