Re: [PATCH v3 1/4] IPC: Added two new system call mq_recvmmsg() and mq_sendmmsg()

Hi, Pavel
so yeah I have some thought over optimization approach,
By saving last visited node to avoid complete traversal, we can not
hold lock till finish entire batch to save eviction of our stored node
so i thought why not version tree and monotonically increase during
any operation that modify tree like insert and deletion, and use
version to invalidate stale saved last visited node node but this
seems it not give us any fruitful benefits as it may cause lot of
invalidation that again fallback to complete traversal.
So the only long run average optimal way seems to be to augment tree
and achieve logarithmic complexity on tree traversal and linear for
list in the same multiple priorities by some extra memory cost per
node probably 4-8 byte with utilizing current padded struct node
layout.
overall augmentation seems great efficiency with slight memory cost
which is tiny in high throughput message exchange.
So, What do you think of it ??

Thanks,
Mathura

On Fri, 12 Jun 2026 at 19:22, Pavel Tikhomirov
<[email protected]> wrote:
>
>
>
> On 6/12/26 14:35, Mathura wrote:
> > Hi,
> >
> > I am resending this due to a mail server error.
>
> Sorry, I accidentally replied with html and broke the formating.
>
> >
> > I never tested in compat mode. I will do and look at all the points
> > mentioned above.
> > I will insist you to please do a complete review and kindly tell me if
> > any more such or any architecture specific issue exists.
> >
> > Regarding optimization on target retrieval from tree, can you provide
> > any suggestion how we can minimize complete traversal required for
> > each time. if we maintain state how we know the current cache or
> > stored efficient node belongs to which system calls from userspace if
> > we assume many concurrent processes calling it.
>
> My idea was to basically just have `struct rb_node **last = NULL;`
> in do_mq_recvmmsg() and pass it down to mq_peek_index(), so that we can
> start the walk from last instead of rb_last, just doing `node = rb_prev(last)`
> instead of full tree walk. You should set node back to last after that.
> Only thing we should be careful about is that info->msg_tree
> should be sufficiently locked to avoid removal of last from the tree.
>
> >
> > Thanks,
> > Mathura
>
> --
> Best regards, Pavel Tikhomirov
> Senior Software Developer, Virtuozzo.
>