From patchwork Tue May 22 22:37:19 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Pravin B Shelar X-Patchwork-Id: 160758 X-Patchwork-Delegate: shemminger@vyatta.com Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 6E170B6FAA for ; Wed, 23 May 2012 08:37:48 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932438Ab2EVWh3 (ORCPT ); Tue, 22 May 2012 18:37:29 -0400 Received: from na3sys009aog122.obsmtp.com ([74.125.149.147]:37242 "HELO na3sys009aog122.obsmtp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1757076Ab2EVWh0 (ORCPT ); Tue, 22 May 2012 18:37:26 -0400 Received: from mail-pz0-f53.google.com ([209.85.210.53]) (using TLSv1) by na3sys009aob122.postini.com ([74.125.148.12]) with SMTP ID DSNKT7wVJSpatWgDR2weWdpOU0sATCysv+WG@postini.com; Tue, 22 May 2012 15:37:26 PDT Received: by dadg9 with SMTP id g9so10457097dad.26 for ; Tue, 22 May 2012 15:37:24 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=from:to:cc:subject:date:message-id:x-mailer:x-gm-message-state; bh=tGhRpsVZDSlsgJHuuRiFz0DKgRvT25+1hOIGDyp3pnM=; b=QeypN7flHXfnMHtHrwbJwiqD0gnMVNWlYgDCPGJUSNQYlLBHIgSLb4j6M6yevp6u7D Ur55uZBvyyDrwHjKmFiZKLdKgg9aIUYoozSGqOJWU8IExeuIgbzItDk6x7v99/0j17jn 0PngUlk5Zr1gW+Ld3FoCx/V8C+0IzdIw7moU26w5Vdb0L27qxzuZCTuMWOiMxbBSj3Ig 6pPF2pTGxkoVp2t0ABPpmINTSoLd7wcpL/FmfIaAPGMp7olxsq11GxCbikutu9PtEgPW /AXOpHWKxbWAQIWOnpLWdbh/hESrU8LEylFYfJXPOw93w3oHqumEuexPE7gHcm2DKypP 7BfA== Received: by 10.68.226.73 with SMTP id rq9mr2940945pbc.145.1337726244614; Tue, 22 May 2012 15:37:24 -0700 (PDT) Received: from localhost (107-0-204-137-ip-static.hfc.comcastbusiness.net. [107.0.204.137]) by mx.google.com with ESMTPS id ph1sm28038291pbb.45.2012.05.22.15.37.22 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 22 May 2012 15:37:23 -0700 (PDT) From: Pravin B Shelar To: shemminger@vyatta.com, netdev@vger.kernel.org Cc: jpettit@nicira.com, jesse@nicira.com, Pravin B Shelar Subject: [PATCH 1/2] iproute2: Improve list add. Date: Tue, 22 May 2012 15:37:19 -0700 Message-Id: <1337726239-9925-1-git-send-email-pshelar@nicira.com> X-Mailer: git-send-email 1.7.10 X-Gm-Message-State: ALoCoQmxUsOovbY7fyYm0eY6aLg9OP5YARkxsYAx8Bpm8Z7gtS+tKruXC9SKEqzM4kwr8IJ2Ml/m Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org ip command reads entire list of devices on every flush command. While adding device record to list is does list traversal O(n). This is time consuming for large batch commands. Following patch improves list add operation to O(1). Reported-by: Justin Pettit Signed-off-by: Pravin B Shelar --- ip/ipaddress.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) diff --git a/ip/ipaddress.c b/ip/ipaddress.c index 9ab65ec..7080c41 100644 --- a/ip/ipaddress.c +++ b/ip/ipaddress.c @@ -714,6 +714,7 @@ int print_addrinfo_secondary(const struct sockaddr_nl *who, struct nlmsghdr *n, struct nlmsg_list { struct nlmsg_list *next; + struct nlmsg_list *last; struct nlmsghdr h; }; @@ -744,17 +745,24 @@ static int store_nlmsg(const struct sockaddr_nl *who, struct nlmsghdr *n, { struct nlmsg_list **linfo = (struct nlmsg_list**)arg; struct nlmsg_list *h; - struct nlmsg_list **lp; - h = malloc(n->nlmsg_len+sizeof(void*)); + h = malloc(n->nlmsg_len+sizeof(void*)+sizeof(void*)); if (h == NULL) return -1; memcpy(&h->h, n, n->nlmsg_len); h->next = NULL; - for (lp = linfo; *lp; lp = &(*lp)->next) /* NOTHING */; - *lp = h; + if (!*linfo) { + /* First element. */ + h->last = h; + *linfo = h; + } else { + struct nlmsg_list *last = (*linfo)->last; + + last->next = h; + (*linfo)->last = h; + } ll_remember_index(who, n, NULL); return 0;