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] [day] [month] [year] [list]

Message-ID: <c222b26f-4671-85db-497b-7122a596870e@huawei.com>
Date:   Fri, 2 Jun 2023 09:36:00 +0800
From:   "Liao, Chang" <liaochang1@...wei.com>
To:     Thomas Gleixner <tglx@...utronix.de>,
        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



在 2023/5/30 20:19, Thomas Gleixner 写道:
> 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?

Oh, that is the point, your explanation made it all clear, my problem is solved,
Thanks!

> 
> Thanks,
> 
>         tglx

-- 
BR
Liao, Chang