From mboxrd@z Thu Jan  1 00:00:00 1970
From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Subject: Re: [RFC] RCU Judy array with distributed locking for FS extents
Date: Mon, 3 Jun 2013 09:50:47 -0400
Message-ID: <20130603135047.GB3288@Krystal>
References: <20130603052758.GA4278@Krystal> <20130603124011.4088.84338@localhost.localdomain> <20130603124601.GA2922@Krystal> <20130603130706.4088.90651@localhost.localdomain>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Cc: Linux FS Devel <linux-fsdevel@vger.kernel.org>,
	David Woodhouse <David.Woodhouse@intel.com>,
	"dchinner@redhat.com" <dchinner@redhat.com>,
	"bo.li.liu@oracle.com" <bo.li.liu@oracle.com>,
	"rp@svcs.cs.pdx.edu" <rp@svcs.cs.pdx.edu>,
	"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>,
	Lai Jiangshan <laijs@cn.fujitsu.com>,
	Stephen Hemminger <shemminger@vyatta.com>,
	Alan Stern <stern@rowland.harvard.edu>
To: Chris Mason <clmason@fusionio.com>
Return-path: <linux-fsdevel-owner@vger.kernel.org>
Received: from mail.openrapids.net ([64.15.138.104]:37748 "EHLO
	blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL)
	by vger.kernel.org with ESMTP id S1757995Ab3FCNuw (ORCPT
	<rfc822;linux-fsdevel@vger.kernel.org>);
	Mon, 3 Jun 2013 09:50:52 -0400
Content-Disposition: inline
In-Reply-To: <20130603130706.4088.90651@localhost.localdomain>
Sender: linux-fsdevel-owner@vger.kernel.org
List-ID: <linux-fsdevel.vger.kernel.org>

* Chris Mason (clmason@fusionio.com) wrote:
> Quoting Mathieu Desnoyers (2013-06-03 08:46:01)
> > > Hi Mathieu,
> > > 
> > > One problem here is that XFS wants to allow duplicate keys in the tree.
> > > This is possible with some modifications to the skiplist code, but I'm
> > > not sure if it fits into your description above.
> > 
> > Are those segments that completely overlap, or partially overlap ?
> 
> I believe completely overlap.  On the skiplist side I'll make it
> possible for either one.

A complete segment overlap is conceptually the same as having duplicate
segments, which makes it easy to handle in my Judy implementation: the
nodes returned by a key lookup are a linked RCU hlist. So when a segment
match is found for a key, iterating on the linked list of duplicate
segments should achieve the intended goal.

Partial overlap can be trickier. There might be extra overhead and
complexity required to support those, so I'll wait until this becomes
really needed before trying to figure out how to support them in Judy.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com