From owner-freebsd-net@FreeBSD.ORG  Sat Apr  5 17:44:26 2008
Return-Path: <owner-freebsd-net@FreeBSD.ORG>
Delivered-To: freebsd-net@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id B43981065670
	for <freebsd-net@freebsd.org>; Sat,  5 Apr 2008 17:44:26 +0000 (UTC)
	(envelope-from Jinmei_Tatuya@isc.org)
Received: from mon.jinmei.org (mon.jinmei.org [IPv6:2001:4f8:3:36::162])
	by mx1.freebsd.org (Postfix) with ESMTP id 873BF8FC0C
	for <freebsd-net@freebsd.org>; Sat,  5 Apr 2008 17:44:26 +0000 (UTC)
	(envelope-from Jinmei_Tatuya@isc.org)
Received: from dhcp-191.sql1.isc.org (unknown
	[IPv6:2001:4f8:3:bb:5177:2da0:2a07:637])
	by mon.jinmei.org (Postfix) with ESMTP id 39F9133C2E;
	Sat,  5 Apr 2008 10:44:26 -0700 (PDT)
Date: Sat, 05 Apr 2008 10:44:24 -0700
Message-ID: <m2lk3si4cn.wl%Jinmei_Tatuya@isc.org>
From: Jinmei_Tatuya@isc.org
To: Max Laier <max@love2party.net>
In-Reply-To: <200804051850.34371.max@love2party.net>
References: <47F78E90.1000706@incunabulum.net>
	<200804051850.34371.max@love2party.net>
User-Agent: Wanderlust/2.14.0 (Africa) Emacs/22.1 Mule/5.0 (SAKAKI)
MIME-Version: 1.0 (generated by SEMI 1.14.6 - "Maruoka")
Content-Type: text/plain; charset=US-ASCII
Cc: freebsd-net@freebsd.org, Bruce M Simpson <bms@incunabulum.net>
Subject: Re: getifaddrs() scalability
X-BeenThere: freebsd-net@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Networking and TCP/IP with FreeBSD <freebsd-net.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-net>,
	<mailto:freebsd-net-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-net>
List-Post: <mailto:freebsd-net@freebsd.org>
List-Help: <mailto:freebsd-net-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-net>,
	<mailto:freebsd-net-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sat, 05 Apr 2008 17:44:26 -0000

At Sat, 5 Apr 2008 18:50:34 +0200,
Max Laier <max@love2party.net> wrote:

> > As such the getifaddrs() call is likely to get slow in that scenario,
> > as it uses a linked list.
> 
> I'm not sure what you are trying to achieve.  getifaddrs is the API to get 
> a complete and consistent snapshot of all currently configured addresses 
> and I don't think there is a better way to represent that then a linked 
> list.  If you need to do lookups in userland you should build your own 
> data structure off of that list.  You can use a PF_ROUTE socket to watch 
> for changes and modify your view accordingly.

If getifaddrs() is used to search for something, the linear aspect
can be a serious overhead that could be actually avoided.  For
example, the current implementation of if_indextoname() calls
getaddrinfo() and search the returned list of ifaddrs for the
interface name that matches the given index.  It requires a linear
order regarding the number of interfaces (and addresses), but it could
in theory be done in O(1).

---
JINMEI, Tatuya
Internet Systems Consortium, Inc.