On Thu, Nov 06, 2014 at 01:16:39PM -0800, Jarno Rajahalme wrote: > > On Nov 6, 2014, at 12:28 PM, Ben Pfaff <b...@nicira.com> wrote: > > > On Thu, Nov 06, 2014 at 10:50:09AM -0800, Jarno Rajahalme wrote: > >> With notes below: > >> > >> Acked-by: Jarno Rajahalme <jrajaha...@nicira.com> > >> > >> On Nov 6, 2014, at 10:03 AM, Ben Pfaff <b...@nicira.com> wrote: > >> > >>> Inserting or removing a sequence of flows with different wildcard patterns > >>> causes temporary use of O(n**2) memory due to pvector modifications inside > >>> the classifier. This commit fixes the problem in two easy cases. There > >>> is at least one more difficult case inside ovs-vswitchd that this does not > >>> fix. > >> > >> I’m curious about the case inside ovs-vswitchd... > > > > It occurs when you do an "ovs-ofctl del-flows" that deletes all of the > > subtables. Each subtable deletion creates a new copy of the pvector but > > we can't free the old one yet. Bang! > > This could be solved by changing the vector to create holes (NULL > pointers), and make the users deal with those. It seems like updating > the vector iterators would suffice, so the change could be invisible > to the users, actually. Could rate-limit the reallocation or issue a > new version whenever the number of holes gets too big? > > Thoughts?
That would work, yes, and it is simple. I like simple. My favorite idea, so far, is to change pvector from an array to an rculist. pvector_change_priority() is tricky, though, and so it's not a perfect match, and maybe that invalidates the whole idea. Another thought I've had is to define a kind of "transaction" for the classifier. Before a sequence of modifications, you start the transaction; after the sequence, you commit it. In between, the work on the pvector happens on a copy that is not exposed to readers, so that it can be edited (and freed) as much as necessary, and then at commit time the final version is exposed and the former version is postpone-deleted. That kind of approach might be necessary at some point if we add high-quality support for OpenFlow 1.4 "bundles", but it might be premature. _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
