From db06903b8464dde6952e2099f6625f6df1760fe9 Mon Sep 17 00:00:00 2001 From: scottl Date: Mon, 30 Dec 2013 05:19:27 +0000 Subject: 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 --- sys/net/flowtable.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'sys/net') diff --git a/sys/net/flowtable.c b/sys/net/flowtable.c index 6995798..32b953c 100644 --- a/sys/net/flowtable.c +++ b/sys/net/flowtable.c @@ -1401,7 +1401,7 @@ fle_free(struct flentry *fle, struct flowtable *ft) 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 *ft, struct rtentry *rt) 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 *ft, struct rtentry *rt) 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) { -- cgit v1.1