On Nov 6, 2014, at 1:40 PM, Ben Pfaff <b...@nicira.com> wrote: > 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. >
Also, the whole reason for introducing pvector was to be able to prefetch the subtables. This because getting to the next subtable in a priority ordered list popped up in perf reports as a frequent cache miss. > 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. I like this. First I thought that this would require support from ovs-ofctl to mark the beginning and end of a transaction, but we could start with by marking each OF request as a transaction, which would catch the case of single request deleting all the flows. Jarno _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
