Re: [PATCH] mark pseudo user as deleted instead of removing them

[Christopher Li <sparse@chrisli.org>]

On Fri, Aug 4, 2017 at 12:54 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>
> I think what might be a good idea is to simply replace the "nr" in
> "ptr_list" with a bitmap of entries instead.

That is one interesting idea.

>
> We already limit each ptr_list[] to 29 entries, so making it an
> "unsigned int" bitmap instead wouldn't be hard. So it would be just a
> single-bit "tag" whether an entry is present or not.

Sure. I think Luc has a patch to make it 13 entries now.

>
> And that allows easy deletion, easy insertion and easy to iterate over too.

I have to think about the insert and ptrlist node split more.

>
> The insertion is admittedly a *bit* awkward, since you have to find a
> free bit, but it's either a fairly simple loop or on newer CPU's you
> can use the "find first bit" instruction.

So for the nested loop insert case, the parent loop iterator will keep
track of __nth_valid_ptr as the slot indicator instead of __nr. If the insert
happen before the __nth_valid_ptr, That still doesn't work, because
the list->list[] will still get shifted.

If the insert only happen after __nth_valid_ptr, that might be
able to work.

For node spiting, We just need to carry over the __nth_valid_ptr to
the next splinted node, still not work if the insert position is
before the carry
over part of the __nth_valid_ptr.

Again I need to think about it more.

Or do you see a way to make insert into any slot position work with
parent holding pointer to the slot number?

Yes, the bit mask seems better than the mark ptr entry as NULL or tag it.

Chris