Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753753Ab0ADUFS (ORCPT ); Mon, 4 Jan 2010 15:05:18 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1752767Ab0ADUFQ (ORCPT ); Mon, 4 Jan 2010 15:05:16 -0500 Received: from out02.mta.xmission.com ([166.70.13.232]:60868 "EHLO out02.mta.xmission.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751051Ab0ADUFO (ORCPT ); Mon, 4 Jan 2010 15:05:14 -0500 To: "H. Peter Anvin" Cc: Yinghai Lu , Jesse Brandeburg , Ingo Molnar , Thomas Gleixner , "linux-kernel\@vger.kernel.org" , Andrew Morton , NetDEV list , Jesse Brandeburg Subject: Re: [PATCH 2/2] x86: get more exact nr_irqs References: <4B347AEE.6030705@kernel.org> <20091228094707.GH24690@elte.hu> <4B398ECD.1080506@kernel.org> <4807377b1001031906s6b1ee576jc021da2642bb4147@mail.gmail.com> <4B415E73.1050801@kernel.org> <4B41918D.3000605@kernel.org> <86802c441001041103s5abd6d3ai4e6ccbfc68323f3c@mail.gmail.com> <4B4241E2.1020008@zytor.com> From: ebiederm@xmission.com (Eric W. Biederman) Date: Mon, 04 Jan 2010 12:05:08 -0800 In-Reply-To: <4B4241E2.1020008@zytor.com> (H. Peter Anvin's message of "Mon\, 04 Jan 2010 11\:30\:42 -0800") Message-ID: User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-XM-SPF: eid=;;;mid=;;;hst=in02.mta.xmission.com;;;ip=76.21.114.89;;;frm=ebiederm@xmission.com;;;spf=neutral X-SA-Exim-Connect-IP: 76.21.114.89 X-SA-Exim-Mail-From: ebiederm@xmission.com X-SA-Exim-Scanned: No (on in02.mta.xmission.com); SAEximRunCond expanded to false Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1715 Lines: 41 "H. Peter Anvin" writes: > On 01/04/2010 11:16 AM, Eric W. Biederman wrote: >> >> If we care about memory use efficiency let's replace irq_desc_ptrs >> with a rbtree or a radix_tree. Something that moves the memory use >> penalty onto those machines that have a lot of irqs. >> > > rbtree doesn't make much sense for something that is addressed by index, > and doesn't need to answer questions of the form "give me the highest > member <= X". A hash table or radix tree makes sense, depending on the > expected sparseness of the index. Not counting irqs for msi's I think we are looking 36% to 25% fill. Maybe a little lower. The sparseness is much higher if we count the number of irqs that we might/use allocate as we do today. Short of driver hotplug msis should be allocated densely, unless we start reserving all possible 4K msi-x vectors. For each ioapic we allocate 16 gsis, and only maybe four of them are connected to actual pci slots. This is essentially a slow path operation, so as long as we are not too expensive we can use any data structure we want. In kernel hash tables don't grow well so I don't think a hash table is a good choice, and a hash table is essentially what we have now. The truth is we don't know how many irqs we will have until msi supporting drivers claim all of theirs. I think a radix-tree would likely be the least intrusive choice as it does not imply any changes to the data structure indexed. Eric -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/