linux-kernel - Re: [PATCH v5 1/3] genirq: Use hlist for managing resend handlers

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <87a5xmj9km.ffs@tglx>
Date:   Tue, 30 May 2023 14:19:21 +0200
From:   Thomas Gleixner <tglx@...utronix.de>
To:     "Liao, Chang" <liaochang1@...wei.com>,
        Shanker Donthineni <sdonthineni@...dia.com>,
        Marc Zyngier <maz@...nel.org>
Cc:     Sebastian Andrzej Siewior <bigeasy@...utronix.de>,
        Michael Walle <michael@...le.cc>, linux-kernel@...r.kernel.org,
        Vikram Sethi <vsethi@...dia.com>,
        Jason Sequeira <jsequeira@...dia.com>
Subject: Re: [PATCH v5 1/3] genirq: Use hlist for managing resend handlers

On Tue, May 30 2023 at 09:59, Chang Liao wrote:
> 在 2023/5/30 5:51, Thomas Gleixner 写道:
>>> What is the benefit of using hlist here? If you want to enjoy the
>>> low latency of querying elements by key, you must define a hlist table
>>> with a reasonable number of buckets. Otherwise, I don't think the time
>>> complexity of hlist is better than a regular double-linked list,
>>> right?
>> 
>> What's complex about hlist in this case? Please explain.
>
> Honestly, it is not about the complexity. Perhaps I do not understand the
> usage of hlist very deeply. I have searched some codes in the kernel and
> found that hlist is always used to speed up arbitrary querying, such as
> searching a registered kprobe by address. Back to this patch, these resend
> IRQs are organized in a sequence list actually, and traveled one by one to
> handle. Further, by comparing the difference between hlist_empty, hlist_add_head,
> hlist_del_init, and their counterparts in list, it looks like a regular linked
> list is also good enough.

Sure that works too.

The main difference between regular linked lists and hlist is that the
list head of hlist is half the size of a regular double linked list.

The only downside of hlist is that there is no back link in the list
head to the tail. Searching for the tail is O(N) while on a double
linked list it's O(1).

Nothing in this use case needs to access the tail. So what's your
problem?

Thanks,

        tglx