From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758571Ab1I3Mm4 (ORCPT ); Fri, 30 Sep 2011 08:42:56 -0400 Received: from mail-wy0-f174.google.com ([74.125.82.174]:61622 "EHLO mail-wy0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752523Ab1I3Mmz (ORCPT ); Fri, 30 Sep 2011 08:42:55 -0400 Date: Fri, 30 Sep 2011 14:42:48 +0200 From: Frederic Weisbecker To: "Kirill A. Shutemov" Cc: Andrew Morton , LKML , Containers , Li Zefan , Johannes Weiner , Aditya Kali , Oleg Nesterov , Kay Sievers , Tim Hockin , Tejun Heo Subject: Re: [PATCH 06/11] cgroups: Add res counter common ancestor searching Message-ID: <20110930124243.GA19053@somewhere> References: <1315869091-18933-1-git-send-email-fweisbec@gmail.com> <1315869091-18933-7-git-send-email-fweisbec@gmail.com> <20110918195932.GD28057@shutemov.name> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20110918195932.GD28057@shutemov.name> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sun, Sep 18, 2011 at 10:59:32PM +0300, Kirill A. Shutemov wrote: > On Tue, Sep 13, 2011 at 01:11:26AM +0200, Frederic Weisbecker wrote: > > Add a new API to find the common ancestor between two resource > > counters. This includes the passed resource counter themselves. > > > > Signed-off-by: Frederic Weisbecker > > Acked-by: Paul Menage > > Cc: Li Zefan > > Cc: Johannes Weiner > > Cc: Aditya Kali > > Cc: Oleg Nesterov > > Cc: Andrew Morton > > Cc: Kay Sievers > > Cc: Tim Hockin > > Cc: Tejun Heo > > --- > > include/linux/res_counter.h | 3 +++ > > kernel/res_counter.c | 22 ++++++++++++++++++++++ > > 2 files changed, 25 insertions(+), 0 deletions(-) > > > > diff --git a/include/linux/res_counter.h b/include/linux/res_counter.h > > index de4ba29..558f39b 100644 > > --- a/include/linux/res_counter.h > > +++ b/include/linux/res_counter.h > > @@ -147,6 +147,9 @@ static inline void res_counter_uncharge(struct res_counter *counter, > > res_counter_uncharge_until(counter, NULL, val); > > } > > > > +struct res_counter *res_counter_common_ancestor(struct res_counter *l, > > + struct res_counter *r); > > + > > /** > > * res_counter_margin - calculate chargeable space of a counter > > * @cnt: the counter > > diff --git a/kernel/res_counter.c b/kernel/res_counter.c > > index 0cc9c7e..22f07cc 100644 > > --- a/kernel/res_counter.c > > +++ b/kernel/res_counter.c > > @@ -91,6 +91,28 @@ void res_counter_uncharge_until(struct res_counter *counter, > > local_irq_restore(flags); > > } > > > > +/* > > + * Walk through r1 and r2 parents and try to find the closest common one > > + * between both. If none is found, it returns NULL. > > + */ > > +struct res_counter * > > +res_counter_common_ancestor(struct res_counter *r1, struct res_counter *r2) > > +{ > > + struct res_counter *iter; > > + > > + while (r1) { > > + iter = r2; > > + while (iter) { > > + if (iter == r1) > > + return iter; > > + iter = iter->parent; > > + } > > + > > + r1 = r1->parent; > > + } > > + > > + return NULL; > > +} > > Your implementation is O(n*m). Paul Menage said that shouldn't harm because in practice cgroups hierarchies are not very deep. But I can take your implementation below, it won't harm further and might behave better on some corner cases. > > What about: > > struct res_counter * > res_counter_common_ancestor(struct res_counter *r1, struct res_counter *r2) > { > struct res_counter *iter; > int r1_depth = 0, r2_depth = 0; > > for (iter = r1; iter; iter = iter->parent) > r1_depth++; > for (iter = r2; iter; iter = iter->parent) > r2_depth++; > > while (r1_depth > r2_depth) { > r1 = r1->parent; > r1_depth--; > } > while (r2_depth > r1_depth) { > r2 = r2->parent; > r2_depth--; > } > > while (r1 != r2) { > r1 = r1->parent; > r2 = r2->parent; > } > > return r1; > } > > Untested. It's O(n+m). > > -- > Kirill A. Shutemov