From owner-svn-src-stable-10@FreeBSD.ORG Mon Dec 30 05:19:28 2013 Return-Path: Delivered-To: svn-src-stable-10@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 0D92C3F1; Mon, 30 Dec 2013 05:19:28 +0000 (UTC) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id EDB56161A; Mon, 30 Dec 2013 05:19:27 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.7/8.14.7) with ESMTP id rBU5JRec052442; Mon, 30 Dec 2013 05:19:27 GMT (envelope-from scottl@svn.freebsd.org) Received: (from scottl@localhost) by svn.freebsd.org (8.14.7/8.14.7/Submit) id rBU5JRLR052441; Mon, 30 Dec 2013 05:19:27 GMT (envelope-from scottl@svn.freebsd.org) Message-Id: <201312300519.rBU5JRLR052441@svn.freebsd.org> From: Scott Long Date: Mon, 30 Dec 2013 05:19:27 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r260077 - stable/10/sys/net X-SVN-Group: stable-10 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable-10@freebsd.org X-Mailman-Version: 2.1.17 Precedence: list List-Id: SVN commit messages for only the 10-stable src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 30 Dec 2013 05:19:28 -0000 Author: scottl Date: Mon Dec 30 05:19:27 2013 New Revision: 260077 URL: http://svnweb.freebsd.org/changeset/base/260077 Log: Merge r256563: In the flowtable scanner, restart the scan at the last found position, not at position 0. Changes the scanner from O(N^2) to O(N). Reviewed by: emax Obtained from: Netflix Modified: stable/10/sys/net/flowtable.c Modified: stable/10/sys/net/flowtable.c ============================================================================== --- stable/10/sys/net/flowtable.c Mon Dec 30 05:02:57 2013 (r260076) +++ stable/10/sys/net/flowtable.c Mon Dec 30 05:19:27 2013 (r260077) @@ -1401,7 +1401,7 @@ fle_free(struct flentry *fle, struct flo static void flowtable_free_stale(struct flowtable *ft, struct rtentry *rt) { - int curbit = 0, count; + int curbit = 0, count, tmpsize; struct flentry *fle, **flehead, *fleprev; struct flentry *flefreehead, *flefreetail, *fletmp; bitstr_t *mask, *tmpmask; @@ -1410,6 +1410,7 @@ flowtable_free_stale(struct flowtable *f flefreehead = flefreetail = NULL; mask = flowtable_mask(ft); tmpmask = ft->ft_tmpmask; + tmpsize = ft->ft_size; memcpy(tmpmask, mask, ft->ft_size/8); /* * XXX Note to self, bit_ffs operates at the byte level @@ -1479,7 +1480,9 @@ flowtable_free_stale(struct flowtable *f bit_clear(mask, curbit); FL_ENTRY_UNLOCK(ft, curbit); bit_clear(tmpmask, curbit); - bit_ffs(tmpmask, ft->ft_size, &curbit); + tmpmask += (curbit / 8); + tmpsize -= (curbit / 8) * 8; + bit_ffs(tmpmask, tmpsize, &curbit); } count = 0; while ((fle = flefreehead) != NULL) {