[Question] The necessity of transaction ID in SLUB.

[Question] The necessity of transaction ID in SLUB.

[Wonhyuk Yang]

Hi all,

I have a question about the necessity of slub's transaction id.
I found that it was Introduced by quite old commit 8a5ec0ba42c4
("Lockless (and preemptless) fastpaths for slub"). And this
concept is still being used.

By using the transaction ID, we can verify that there is no
update and it isn't running on other cpu. But it seems like
that we can do these things by comparing c->cpu_slab->freelist.

Let's assume we don't use transaction id.

If other slub events occurred, c->cpu_slab->freelist will be
different generally. But even if other slub events occurred,
c->cpu_slab->freelist can be the same.

There is 2 cases,

1) c->cpu_slab->page is unfrozen and frozen by another cpu. (is it possible?)
2) c->cpu_slab->freelist == NULL

In the first case, cpu_slab structure can be different. But updating
freelist isn't a problem.

In the second case, slab alloc's fast-path doesn't have to care
about it. Because it will call __slab_alloc instead of cmpxchg
In the slab free's fast-path, c->cpu_slab->freelist can be NULL.
So we have to check whether slab page is changed by other
events. We can do this by checking the cpu_slab's page
like below.

this_cpu_cmpxchg_double(
s->cpu_slab->freelist, s->cpu_slab->page,
object, page, next_object,
s->cpu_slab->page)

I feel that I missed something important. Please let me know if
I missed something.

Thanks.

Re: [Question] The necessity of transaction ID in SLUB.

[Christoph Lameter]

On Sun, 21 Nov 2021, Wonhyuk Yang wrote:

> 1) c->cpu_slab->page is unfrozen and frozen by another cpu. (is it possible?)

Yes.

> In the first case, cpu_slab structure can be different. But updating
> freelist isn't a problem.

It is a problem because the update can occur on a different processor
without the TID which can race with another update on another processor.

Re: [Question] The necessity of transaction ID in SLUB.

[Wonhyuk Yang]

On Mon, Nov 22, 2021 at 6:25 PM Christoph Lameter <cl@gentwo.org> wrote:
>
> > 1) c->cpu_slab->page is unfrozen and frozen by another cpu. (is it possible?)
>
> Yes.
>
> > In the first case, cpu_slab structure can be different. But updating
> > freelist isn't a problem.
>
> It is a problem because the update can occur on a different processor
> without the TID which can race with another update on another processor.
>

Do you mean that without TID, multiple cpu can race on one
cpu_slab->freelist?

How is it possible? As you know, cpu_slab is per-cpu variable and
cpu_slab->freelist is accessed via "this_cpu_cmpxchg" in the area
where preemption is enabled.

I can't imagine what kind of situation will make that race happen.

Re: [Question] The necessity of transaction ID in SLUB.

[Christoph Lameter]

On Tue, 23 Nov 2021, Wonhyuk Yang wrote:

> Do you mean that without TID, multiple cpu can race on one
> cpu_slab->freelist?
>
> How is it possible? As you know, cpu_slab is per-cpu variable and
> cpu_slab->freelist is accessed via "this_cpu_cmpxchg" in the area
> where preemption is enabled.

That is the problem. Preemption is enabled. This means that slab_alloc can
be preempted at any time and continue to run on an arbitrary other
processor and also continue at an arbitrary time. It may also be
rescheduled on the processor it ran before after executing just one
instruction or so on another processor.

Yes another thread may therefore also start to execute slab_alloc() on the
same cpu, get the same per cpu pointer and perform some ops. Somewhere in
the middle of this another processor may continue the first thread that
was preempted earlier.

Re: [Question] The necessity of transaction ID in SLUB.

[Wonhyuk Yang]

On Tue, Nov 23, 2021 at 6:38 PM Christoph Lameter <cl@gentwo.org> wrote:

>
> > Do you mean that without TID, multiple cpu can race on one
> > cpu_slab->freelist?
> >
> > How is it possible? As you know, cpu_slab is per-cpu variable and
> > cpu_slab->freelist is accessed via "this_cpu_cmpxchg" in the area
> > where preemption is enabled.
>
> That is the problem. Preemption is enabled. This means that slab_alloc can
> be preempted at any time and continue to run on an arbitrary other
> processor and also continue at an arbitrary time. It may also be
> rescheduled on the processor it ran before after executing just one
> instruction or so on another processor.

Yes, that's why transaction id is made up of two part CPU id and event id
(To guarantee there are no other events and migrations).
And the guarantee is ultimately to protect cpu_slab->freelist.

My point is, we can protect cpu_slab->freelist using only cpu_slab->freelist
with less overhead. That's why I'm asking if there's any other reason for TID.

Re: [Question] The necessity of transaction ID in SLUB.

[Wonhyuk Yang]

I think submitting my patch will be more helpful for communication.

Sorry for bothering you.

Re: [Question] The necessity of transaction ID in SLUB.

[Christoph Lameter]

On Tue, 23 Nov 2021, Wonhyuk Yang wrote:

> Yes, that's why transaction id is made up of two part CPU id and event id
> (To guarantee there are no other events and migrations).
> And the guarantee is ultimately to protect cpu_slab->freelist.

Well that is the way it was initially because I thought along the same
way. You can simply revert the patches that introduced the TID to get that
version back (and the races too.....) if you want to try.

Re: [Question] The necessity of transaction ID in SLUB.

[Wonhyuk Yang]

Now I know what I missed!

I missed that the freepointer may no more be valid because any other
preemptions. Also, It is possible that cpu_slab->freelist is unchanged
but it's freepointer may be changed. This is why we guarantee that
there is no update before, right?

Thanks to the answer, I was able to solve my question.