From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S937454AbdEWPM7 (ORCPT ); Tue, 23 May 2017 11:12:59 -0400 Received: from mx0b-001b2d01.pphosted.com ([148.163.158.5]:51134 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1764383AbdEWPMy (ORCPT ); Tue, 23 May 2017 11:12:54 -0400 From: Laurent Dufour Subject: Re: [PATCH 2/6] locking: Introduce range reader/writer lock To: Davidlohr Bueso , mingo@kernel.org, peterz@infradead.org, akpm@linux-foundation.org Cc: jack@suse.cz, kirill.shutemov@linux.intel.com, mhocko@suse.com, mgorman@techsingularity.net, linux-kernel@vger.kernel.org, Davidlohr Bueso References: <20170515090725.27055-1-dave@stgolabs.net> <20170515090725.27055-3-dave@stgolabs.net> Date: Tue, 23 May 2017 17:12:45 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.1 MIME-Version: 1.0 In-Reply-To: <20170515090725.27055-3-dave@stgolabs.net> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-TM-AS-GCONF: 00 x-cbid: 17052315-0040-0000-0000-000003B4688D X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17052315-0041-0000-0000-0000203EA343 Message-Id: <7f35e628-1331-84df-5e1d-8c46233dbc6c@linux.vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:,, definitions=2017-05-23_04:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1703280000 definitions=main-1705230079 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 15/05/2017 11:07, Davidlohr Bueso wrote: > --- /dev/null > +++ b/include/linux/range_lock.h > @@ -0,0 +1,181 @@ > +/* > + * Range/interval rw-locking > + * ------------------------- > + * > + * Interval-tree based range locking is about controlling tasks' forward > + * progress when adding an arbitrary interval (node) to the tree, depending > + * on any overlapping ranges. A task can only continue (wakeup) if there are > + * no intersecting ranges, thus achieving mutual exclusion. To this end, a > + * reference counter is kept for each intersecting range in the tree > + * (_before_ adding itself to it). To enable shared locking semantics, > + * the reader to-be-locked will not take reference if an intersecting node > + * is also a reader, therefore ignoring the node altogether. > + * > + * Fairness and freedom of starvation are guaranteed by the lack of lock > + * stealing, thus range locks depend directly on interval tree semantics. > + * This is particularly for iterations, where the key for the rbtree is > + * given by the interval's low endpoint, and duplicates are walked as it > + * would an inorder traversal of the tree. > + * > + * The cost of lock and unlock of a range is O((1+R_int)log(R_all)) where > + * R_all is total number of ranges and R_int is the number of ranges > + * intersecting the operated range. > + */ > +#ifndef _LINUX_RANGE_LOCK_H > +#define _LINUX_RANGE_LOCK_H > + > +#include > +#include > +#include > +#include > + > +/* > + * The largest range will span [0,RANGE_LOCK_FULL]. > + */ > +#define RANGE_LOCK_FULL ~0UL > + > +struct range_lock { > + struct interval_tree_node node; > + struct task_struct *tsk; > + /* Number of ranges which are blocking acquisition of the lock */ > + unsigned int blocking_ranges; > + u64 seqnum; > +}; > + > +struct range_lock_tree { > + struct rb_root root; > + spinlock_t lock; > + struct interval_tree_node *leftmost; /* compute smallest 'start' */ > + u64 seqnum; /* track order of incoming ranges, avoid overflows */ > +#ifdef CONFIG_DEBUG_LOCK_ALLOC > + struct lockdep_map dep_map; > +#endif > +}; > + > +#ifdef CONFIG_DEBUG_LOCK_ALLOC > +# define __RANGE_LOCK_DEP_MAP_INIT(lockname) , .dep_map = { .name = #lockname } > +#else > +# define __RANGE_LOCK_DEP_MAP_INIT(lockname) > +#endif > + > +#define __RANGE_LOCK_TREE_INITIALIZER(name) \ > + { .leftmost = NULL \ > + , .root = RB_ROOT \ > + , .seqnum = 0 \ > + , .lock = __SPIN_LOCK_UNLOCKED(name.lock) \ > + __RANGE_LOCK_DEP_MAP_INIT(name) } \ > + > +#define DEFINE_RANGE_LOCK_TREE(name) \ > + struct range_lock_tree name = __RANGE_LOCK_TREE_INITIALIZER(name) > + > +#define __RANGE_LOCK_INITIALIZER(__start, __last) { \ > + .node = { \ > + .start = (__start) \ > + ,.last = (__last) \ > + } \ > + , .task = NULL \ ^tsk > + , .blocking_ranges = 0 \ > + , .reader = false \ ^ this field doesn't exist anymore Cheers, Laurent.