Date: Tue, 15 Oct 2013 21:28:52 +0000 (UTC) From: Maksim Yevmenkin <emax@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r256563 - head/sys/net Message-ID: <201310152128.r9FLSqTl011833@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: emax Date: Tue Oct 15 21:28:51 2013 New Revision: 256563 URL: http://svnweb.freebsd.org/changeset/base/256563 Log: 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). Submitted by: scottl Obtained from: Netflix, Inc MFC after: 3 weeks Modified: head/sys/net/flowtable.c Modified: head/sys/net/flowtable.c ============================================================================== --- head/sys/net/flowtable.c Tue Oct 15 21:08:37 2013 (r256562) +++ head/sys/net/flowtable.c Tue Oct 15 21:28:51 2013 (r256563) @@ -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) {
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201310152128.r9FLSqTl011833>