From owner-freebsd-arch@FreeBSD.ORG Sun Feb 15 08:14:07 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5920716A4CE; Sun, 15 Feb 2004 08:14:07 -0800 (PST) Received: from milla.ask33.net (milla.ask33.net [217.197.166.60]) by mx1.FreeBSD.org (Postfix) with ESMTP id 9B82B43D1D; Sun, 15 Feb 2004 08:14:04 -0800 (PST) (envelope-from nick@milla.ask33.net) Received: by milla.ask33.net (Postfix, from userid 1001) id 298753ABB85; Sun, 15 Feb 2004 17:17:05 +0100 (CET) Date: Sun, 15 Feb 2004 17:17:04 +0100 From: Pawel Jakub Dawidek To: Robert Watson Message-ID: <20040215161704.GY14639@garage.freebsd.pl> References: <200402141831.i1EIVCwL079081@repoman.freebsd.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="SwLo357mIESq0V3a" Content-Disposition: inline In-Reply-To: <200402141831.i1EIVCwL079081@repoman.freebsd.org> X-PGP-Key-URL: http://people.freebsd.org/~pjd/pjd.asc X-OS: FreeBSD 4.8-RELEASE-p13 i386 X-URL: http://garage.freebsd.pl User-Agent: Mutt/1.5.1i cc: freebsd-arch@FreeBSD.org Subject: Re: cvs commit: src/sys/sys jail.h src/sys/kern kern_jail.c vfs_syscalls.c X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 15 Feb 2004 16:14:07 -0000 --SwLo357mIESq0V3a Content-Type: text/plain; charset=iso-8859-2 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Feb 14, 2004 at 10:31:12AM -0800, Robert Watson wrote: +> Commiter: Robert Watson +> Branch: HEAD +>=20 +> Files: +> 1.36 src/sys/kern/kern_jail.c =20 +> 1.337 src/sys/kern/vfs_syscalls.c =20 +> 1.20 src/sys/sys/jail.h =20 +>=20 +> Log: +> By default, when a process in jail calls getfsstat(), only return the +> data for the file system on which the jail's root vnode is located. +> Previous behavior (show data for all mountpoints) can be restored +> by setting security.jail.getfsstatroot_only to 0. Note: this also +> has the effect of hiding other mounts inside a jail, such as /dev, +> /tmp, and /proc, but errs on the side of leaking less information. I don't like this fix... There are many problems related to the fact, that we store path where file system is mounted as a string. This fix is one of them. I've wrote kld module some time ago that shows file systems with cutted path in front (jail chroot directory was removed). This wasn't a nice, clean way, but... In your fix we still leak of where-the-real-root-is information, of course it is much better than we had before, but still not complete. Another problem (changing as PR somewhere) is that when you mount file system in chroot environment, wrong path is stored (path releated to chroot= ). This problem was really important in the past, because such file system was totally unmountable, with FSID it is, but wrong path still exists. I think the complete way is to store vnode related to the directory where file system is mounted, instead of directory as a string. We have some ideas to explore in future, for example allowing file systems mounts inside of jail if vfs.usermount is 1 and then your fix will not be enough. With such fix (vnode instead of string), we will be able to always return file system names related to chroot directory. I'm still not sure if we're able to implement this with our current vn_fullpath() implementation, but we can try, or more - we can try to add a flag to this function DONT_USE_CACHE_JUST_ASK_FILE_SYSTEM_DIRECTLY (as was discussed on #thatchannel). Sooner or later we must do this (before AUDIT will be merged?). I can prepare a patch to change this string to a vnode and we'll see. What you say? [ Let's continue on arch@ ] --=20 Pawel Jakub Dawidek http://www.FreeBSD.org pjd@FreeBSD.org http://garage.freebsd.pl FreeBSD committer Am I Evil? Yes, I Am! --SwLo357mIESq0V3a Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (FreeBSD) iD8DBQFAL5uAForvXbEpPzQRAv5vAKDz+N7OtuoGA9M6Gvk3sZFDygj4LQCgpVKI JKiKECKlUMxfLT/hrb9h+gw= =4W4X -----END PGP SIGNATURE----- --SwLo357mIESq0V3a-- From owner-freebsd-arch@FreeBSD.ORG Sun Feb 15 09:02:23 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 06C4F16A4CE; Sun, 15 Feb 2004 09:02:23 -0800 (PST) Received: from fledge.watson.org (fledge.watson.org [204.156.12.50]) by mx1.FreeBSD.org (Postfix) with ESMTP id 9890343D1F; Sun, 15 Feb 2004 09:02:22 -0800 (PST) (envelope-from robert@fledge.watson.org) Received: from fledge.watson.org (localhost [127.0.0.1]) by fledge.watson.org (8.12.10/8.12.10) with ESMTP id i1FH1uDL056808; Sun, 15 Feb 2004 12:01:56 -0500 (EST) (envelope-from robert@fledge.watson.org) Received: from localhost (robert@localhost)i1FH1ucL056805; Sun, 15 Feb 2004 12:01:56 -0500 (EST) (envelope-from robert@fledge.watson.org) Date: Sun, 15 Feb 2004 12:01:56 -0500 (EST) From: Robert Watson X-Sender: robert@fledge.watson.org To: Pawel Jakub Dawidek In-Reply-To: <20040215161704.GY14639@garage.freebsd.pl> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: freebsd-arch@FreeBSD.org Subject: Re: cvs commit: src/sys/sys jail.h src/sys/kern kern_jail.c vfs_syscalls.c X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 15 Feb 2004 17:02:23 -0000 On Sun, 15 Feb 2004, Pawel Jakub Dawidek wrote: > On Sat, Feb 14, 2004 at 10:31:12AM -0800, Robert Watson wrote: > +> Commiter: Robert Watson > +> Branch: HEAD > +> > +> Files: > +> 1.36 src/sys/kern/kern_jail.c > +> 1.337 src/sys/kern/vfs_syscalls.c > +> 1.20 src/sys/sys/jail.h > +> > +> Log: > +> By default, when a process in jail calls getfsstat(), only return the > +> data for the file system on which the jail's root vnode is located. > +> Previous behavior (show data for all mountpoints) can be restored > +> by setting security.jail.getfsstatroot_only to 0. Note: this also > +> has the effect of hiding other mounts inside a jail, such as /dev, > +> /tmp, and /proc, but errs on the side of leaking less information. > > I don't like this fix... > > There are many problems related to the fact, that we store path where > file system is mounted as a string. > > This fix is one of them. I've wrote kld module some time ago that shows > file systems with cutted path in front (jail chroot directory was > removed). This wasn't a nice, clean way, but... > > In your fix we still leak of where-the-real-root-is information, of > course it is much better than we had before, but still not complete. > > Another problem (changing as PR somewhere) is that when you mount file > system in chroot environment, wrong path is stored (path releated to > chroot). This problem was really important in the past, because such > file system was totally unmountable, with FSID it is, but wrong path > still exists. > > I think the complete way is to store vnode related to the directory > where file system is mounted, instead of directory as a string. We have > some ideas to explore in future, for example allowing file systems > mounts inside of jail if vfs.usermount is 1 and then your fix will not > be enough. With such fix (vnode instead of string), we will be able to > always return file system names related to chroot directory. I'm still > not sure if we're able to implement this with our current vn_fullpath() > implementation, but we can try, or more - we can try to add a flag to > this function DONT_USE_CACHE_JUST_ASK_FILE_SYSTEM_DIRECTLY (as was > discussed on #thatchannel). Sooner or later we must do this (before > AUDIT will be merged?). > > I can prepare a patch to change this string to a vnode and we'll see. > What you say? Everything involving pathnames and VFS is evil and/or difficult. This problem smacks every UNIX system I've seen with regular frequency, and it's complicated by the following: - Vnodes may have no name (deleted but referenced files). - Vnodes may have more than one name (hard links) -- not only that, but new names can be created for most objects by unprivileged users. - Names may have more than one vnode (mountpoint covering, synthetic file systems). - Cached names become stale easily and cannot be easily updated. - Names are relative to a process context due to notions of current process root and current working directory. This is further complicated by the fact that UFS and NFS both encourage a philosophy of names simply being a "path" to reach an object, not a property of the object. Trying to change these assumptions will both be extremely difficult, and may also be un-UNIXy. However, there are some very strong motivations to find at least a partial solution: (1) Make mount strings returned by fsstat() and getfsstat() make sense regardless of context. (2) Make name pointers in procfs reliable and safe. (3) Provide accurate path information for security audit logs. Complications in solving this problem also include locking issues: it's generally safe to access the name cache if you have a strong vnode reference to look up "possible" names for an object. However, asking the file system for the name of an object reliably in UFS is probably both a disk-intensive and locking-complex operation (even pre-SMPng). The cache is, of course, unreliable for the above-identified reasons, and also that we can push intermediate vnodes in the path out of memory, meaning that it's a very expensive operation to pull them back in. If we lived in a world of HFS+ and volfs as on Darwin, we could cheat by returning the volfs path to the object, but that's not very useful from a user perspective, and so is basically useless despite being functionally correct (mostly). Finally, you might want to take a look at the implementation of vn_getpath() on Darwin, which relies on the stronger namespace semantics of HFS+, where all objects really do have parents, they maintain vnode back-pointers to parents, and can rely on the catalog entries for the directory tree being in memory (something we sacrifice for UFS directories for scalability reasons). So, I guess to conclude after railing: I went with the change I committed for the reason that it was the simplest change to give the desired result without increasing the strength of assumptions regarding the existence, correctness, and usefulness of pathnames. I agree we need a better solution, but juggling the traditional UNIX conventions for names and objects with the requirements of usability and security is hard. In earlier revisions of the patch, I did actually update the string for the root directory before exporting to userspace when masking other file system entries so that if you typed "df" in the jail, you saw the right "/" entry. However, I ommitted this in the committed version because it required the getfsstat() code to know more about how Jails work, whereas currently there's a simple jail decision function that is invoked by getfsstat(). I'm willing to explore many different alternative approaches, but I think we should avoid complexity, and also try to avoid hurting ourselves too badly on the sharp edges of UNIX namespaces. Robert N M Watson FreeBSD Core Team, TrustedBSD Projects robert@fledge.watson.org Senior Research Scientist, McAfee Research From owner-freebsd-arch@FreeBSD.ORG Wed Feb 18 12:56:58 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id D274916A4CE for ; Wed, 18 Feb 2004 12:56:58 -0800 (PST) Received: from herring.nlsystems.com (mailgate.nlsystems.com [80.177.232.242]) by mx1.FreeBSD.org (Postfix) with ESMTP id 6EADE43D2D for ; Wed, 18 Feb 2004 12:56:58 -0800 (PST) (envelope-from dfr@nlsystems.com) Received: from [10.0.0.2] (herring.nlsystems.com [10.0.0.2]) by herring.nlsystems.com (8.12.10/8.12.8) with ESMTP id i1IKukF1028228 for ; Wed, 18 Feb 2004 20:56:46 GMT (envelope-from dfr@nlsystems.com) From: Doug Rabson To: freebsd-arch@freebsd.org Content-Type: text/plain Message-Id: <1077137806.28133.10.camel@herring.nlsystems.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.5 Date: Wed, 18 Feb 2004 20:56:46 +0000 Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on herring.nlsystems.com Subject: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 18 Feb 2004 20:56:59 -0000 So, I was reading the latest installment of the SCO soap on slashdot today (bizarre - they seem to be claiming that they own all code that was ever linked to a System V kernel) and I ended up trying to figure out exactly what this RCU thing is that they claim is infringing their right to obtain money with menaces. I read one of the original papers at http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a surprisingly simple idea. Basically for certain data structures which are read-mostly, you can make the entire read path lock-free at the expense of making updates quite a bit more expensive. They claim that its much faster than reader-writer locks both for light contention and for heavy contention. I imagine that a FreeBSD implementation of RCU wouldn't actually be too hard and it might be well worth it as an alternative way of managing concurrency, e.g. for the routing cache and the name cache (and probably lots of other things). From owner-freebsd-arch@FreeBSD.ORG Wed Feb 18 15:26:09 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 0805016A4CE for ; Wed, 18 Feb 2004 15:26:09 -0800 (PST) Received: from mail.chesapeake.net (chesapeake.net [208.142.252.6]) by mx1.FreeBSD.org (Postfix) with ESMTP id A6A7643D1D for ; Wed, 18 Feb 2004 15:26:08 -0800 (PST) (envelope-from jroberson@mail.chesapeake.net) Received: from mail.chesapeake.net (localhost [127.0.0.1]) by mail.chesapeake.net (8.12.10/8.12.10) with ESMTP id i1INQ7XJ074540; Wed, 18 Feb 2004 18:26:07 -0500 (EST) (envelope-from jroberson@mail.chesapeake.net) Received: from localhost (jroberson@localhost)i1INQ6xe074521; Wed, 18 Feb 2004 18:26:07 -0500 (EST) (envelope-from jroberson@mail.chesapeake.net) Date: Wed, 18 Feb 2004 18:26:05 -0500 (EST) From: Jeff Roberson To: Doug Rabson In-Reply-To: <1077137806.28133.10.camel@herring.nlsystems.com> Message-ID: <20040218182136.S5430@mail.chesapeake.net> References: <1077137806.28133.10.camel@herring.nlsystems.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 18 Feb 2004 23:26:09 -0000 On Wed, 18 Feb 2004, Doug Rabson wrote: > So, I was reading the latest installment of the SCO soap on slashdot > today (bizarre - they seem to be claiming that they own all code that > was ever linked to a System V kernel) and I ended up trying to figure > out exactly what this RCU thing is that they claim is infringing their > right to obtain money with menaces. > > I read one of the original papers at > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a > surprisingly simple idea. Basically for certain data structures which > are read-mostly, you can make the entire read path lock-free at the > expense of making updates quite a bit more expensive. They claim that > its much faster than reader-writer locks both for light contention and > for heavy contention. > > I imagine that a FreeBSD implementation of RCU wouldn't actually be too > hard and it might be well worth it as an alternative way of managing > concurrency, e.g. for the routing cache and the name cache (and probably > lots of other things). > I've looked into this a bit myself. My general feeling is that it would not be terribly difficult to do, but I would prefer to start with stronger primitives and work our way into more efficient mechanisms. I say this for two reasons. First, as a general rule of optimizations, you only optimize the things that need it. I think we should wait and measure contention and then optimize things. Secondly, we need to get more confidence in the correctness of simpler mechanisms in most subsystems before we go to something more complex. It will be easier to move to RCU once a subsystem is already protected by mutexes. I think that this is a good path to go down, but I really don't think we're ready yet. I'd rather see energy spent protecting code than building more infrastructure. Cheers, Jeff From owner-freebsd-arch@FreeBSD.ORG Thu Feb 19 01:02:48 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 1E4BF16A4CE for ; Thu, 19 Feb 2004 01:02:48 -0800 (PST) Received: from herring.nlsystems.com (mailgate.nlsystems.com [80.177.232.242]) by mx1.FreeBSD.org (Postfix) with ESMTP id A33FB43D1D for ; Thu, 19 Feb 2004 01:02:47 -0800 (PST) (envelope-from dfr@nlsystems.com) Received: from [10.0.0.2] (herring.nlsystems.com [10.0.0.2]) i1J92ZF1038512; Thu, 19 Feb 2004 09:02:36 GMT (envelope-from dfr@nlsystems.com) From: Doug Rabson To: Jeff Roberson In-Reply-To: <20040218182136.S5430@mail.chesapeake.net> References: <1077137806.28133.10.camel@herring.nlsystems.com> <20040218182136.S5430@mail.chesapeake.net> Content-Type: text/plain Message-Id: <1077181355.28133.13.camel@herring.nlsystems.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.5 Date: Thu, 19 Feb 2004 09:02:35 +0000 Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on herring.nlsystems.com cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Feb 2004 09:02:48 -0000 On Wed, 2004-02-18 at 23:26, Jeff Roberson wrote: > On Wed, 18 Feb 2004, Doug Rabson wrote: > > > So, I was reading the latest installment of the SCO soap on slashdot > > today (bizarre - they seem to be claiming that they own all code that > > was ever linked to a System V kernel) and I ended up trying to figure > > out exactly what this RCU thing is that they claim is infringing their > > right to obtain money with menaces. > > > > I read one of the original papers at > > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a > > surprisingly simple idea. Basically for certain data structures which > > are read-mostly, you can make the entire read path lock-free at the > > expense of making updates quite a bit more expensive. They claim that > > its much faster than reader-writer locks both for light contention and > > for heavy contention. > > > > I imagine that a FreeBSD implementation of RCU wouldn't actually be too > > hard and it might be well worth it as an alternative way of managing > > concurrency, e.g. for the routing cache and the name cache (and probably > > lots of other things). > > > > I've looked into this a bit myself. My general feeling is that it would > not be terribly difficult to do, but I would prefer to start with stronger > primitives and work our way into more efficient mechanisms. I say this > for two reasons. First, as a general rule of optimizations, you only > optimize the things that need it. I think we should wait and measure > contention and then optimize things. Secondly, we need to get more > confidence in the correctness of simpler mechanisms in most subsystems > before we go to something more complex. It will be easier to move to RCU > once a subsystem is already protected by mutexes. > > I think that this is a good path to go down, but I really don't think > we're ready yet. I'd rather see energy spent protecting code than > building more infrastructure. I completely agree. I was just musing about this as a future addition to the locking toolbox. Its certainly not worth trying before enough of the kernel is outside the giant lock to make it worthwhile. From owner-freebsd-arch@FreeBSD.ORG Thu Feb 19 02:08:54 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 37C7A16A4CE for ; Thu, 19 Feb 2004 02:08:54 -0800 (PST) Received: from smtp3.Stanford.EDU (smtp3.Stanford.EDU [171.67.16.117]) by mx1.FreeBSD.org (Postfix) with ESMTP id 2FCD743D1D for ; Thu, 19 Feb 2004 02:08:54 -0800 (PST) (envelope-from tedu@stanford.edu) Received: from elaine39.Stanford.EDU (elaine39.Stanford.EDU [171.64.15.114]) by smtp3.Stanford.EDU (8.12.10/8.12.10) with ESMTP id i1JA8rdI031031; Thu, 19 Feb 2004 02:08:53 -0800 Date: Thu, 19 Feb 2004 02:08:53 -0800 (PST) From: Ted Unangst To: Doug Rabson In-Reply-To: <1077137806.28133.10.camel@herring.nlsystems.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Feb 2004 10:08:54 -0000 On Wed, 18 Feb 2004, Doug Rabson wrote: > I read one of the original papers at > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a > surprisingly simple idea. Basically for certain data structures which > are read-mostly, you can make the entire read path lock-free at the > expense of making updates quite a bit more expensive. They claim that > its much faster than reader-writer locks both for light contention and > for heavy contention. consider the following for the linked list example given. A -> B -> C thread 0 was changing B. creates B', links A -> B' -> C. waits for quiet time, free(B). thread 1 is walking list. when it's done, signals quiet time. what if both threads want to change B? thread 0 walks list to B. thread 1 walks list to B. thread 0 creates B'. thread 1 creates B''. thread 0 links list A -> B' -> C thread 1 links list A -> B'' -> C thread 0 creates callback. thread 1 creates callback. thread 0 callback runs, free(B). thread 1 callback runs, free(B). *boom* excuse me if i missed it, but i didn't see this addressed in the paper. -- From owner-freebsd-arch@FreeBSD.ORG Thu Feb 19 02:14:49 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 290DF16A4CE for ; Thu, 19 Feb 2004 02:14:49 -0800 (PST) Received: from herring.nlsystems.com (mailgate.nlsystems.com [80.177.232.242]) by mx1.FreeBSD.org (Postfix) with ESMTP id AD43F43D1F for ; Thu, 19 Feb 2004 02:14:48 -0800 (PST) (envelope-from dfr@nlsystems.com) Received: from [10.0.0.2] (herring.nlsystems.com [10.0.0.2]) i1JAEbF1041838; Thu, 19 Feb 2004 10:14:37 GMT (envelope-from dfr@nlsystems.com) From: Doug Rabson To: Ted Unangst In-Reply-To: References: Content-Type: text/plain Message-Id: <1077185677.28133.29.camel@herring.nlsystems.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.5 Date: Thu, 19 Feb 2004 10:14:37 +0000 Content-Transfer-Encoding: 7bit X-Spam-Status: No, hits=0.0 required=5.0 tests=none autolearn=no version=2.60 X-Spam-Checker-Version: SpamAssassin 2.60 (1.212-2003-09-23-exp) on herring.nlsystems.com cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Feb 2004 10:14:49 -0000 On Thu, 2004-02-19 at 10:08, Ted Unangst wrote: > On Wed, 18 Feb 2004, Doug Rabson wrote: > > > I read one of the original papers at > > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a > > surprisingly simple idea. Basically for certain data structures which > > are read-mostly, you can make the entire read path lock-free at the > > expense of making updates quite a bit more expensive. They claim that > > its much faster than reader-writer locks both for light contention and > > for heavy contention. > > consider the following for the linked list example given. A -> B -> C > > thread 0 was changing B. creates B', links A -> B' -> C. waits for > quiet time, free(B). > > thread 1 is walking list. when it's done, signals quiet time. > > what if both threads want to change B? > > thread 0 walks list to B. > thread 1 walks list to B. > thread 0 creates B'. > thread 1 creates B''. > thread 0 links list A -> B' -> C > thread 1 links list A -> B'' -> C > thread 0 creates callback. > thread 1 creates callback. > thread 0 callback runs, free(B). > thread 1 callback runs, free(B). *boom* > > excuse me if i missed it, but i didn't see this addressed in the paper. This is mentioned in the paper where they say that 'Thread 0 must use some sort of update discipline to handle concurrent updates'. Effectively, updates to the list must be serialised using e.g. a mutex but simple list traversals don't need to take the mutex. From owner-freebsd-arch@FreeBSD.ORG Thu Feb 19 08:26:26 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id F06E416A4CF for ; Thu, 19 Feb 2004 08:26:26 -0800 (PST) Received: from mother.ludd.ltu.se (mother.ludd.ltu.se [130.240.16.3]) by mx1.FreeBSD.org (Postfix) with ESMTP id 583DF43D1F for ; Thu, 19 Feb 2004 08:26:26 -0800 (PST) (envelope-from pj@ludd.ltu.se) Received: from dexter.ludd.ltu.se (pj@dexter.ludd.ltu.se [130.240.16.80]) i1JGQNAr026227; Thu, 19 Feb 2004 17:26:24 +0100 (MET) To: Doug Rabson References: <1077137806.28133.10.camel@herring.nlsystems.com> From: Peter A Jonsson Date: 19 Feb 2004 17:26:23 +0100 In-Reply-To: <1077137806.28133.10.camel@herring.nlsystems.com> Message-ID: Lines: 17 User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Feb 2004 16:26:27 -0000 > I imagine that a FreeBSD implementation of RCU wouldn't actually be too > hard and it might be well worth it as an alternative way of managing > concurrency, e.g. for the routing cache and the name cache (and probably > lots of other things). Alan Cox pointed out[1] that there was a patent problem (US Patent #05442758 [2]) with RCU which prevented inclusion in the Linux kernel. This was solved[3] by granting the right to use it in GPL software according to my understanding. Isn't this a problem for FreeBSD? [1] http://www.cs.helsinki.fi/linux/linux-kernel/2001-36/0385.html [2] http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5442758.WKU.&OS=PN/5442758&RS=PN/5442758 [3] http://www.cs.helsinki.fi/linux/linux-kernel/2001-36/0505.html / Peter From owner-freebsd-arch@FreeBSD.ORG Thu Feb 19 08:32:22 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 392A916A4CE for ; Thu, 19 Feb 2004 08:32:22 -0800 (PST) Received: from mail.qubesoft.com (gate.qubesoft.com [217.169.36.34]) by mx1.FreeBSD.org (Postfix) with ESMTP id B5B9343D1D for ; Thu, 19 Feb 2004 08:32:21 -0800 (PST) (envelope-from dfr@nlsystems.com) Received: from bluebottle.qubesoft.com (bluebottle.qubesoft.com [192.168.1.2]) by mail.qubesoft.com (8.12.9/8.12.9) with ESMTP id i1JGWJ8g073058; Thu, 19 Feb 2004 16:32:20 GMT (envelope-from dfr@nlsystems.com) Received: from builder02.qubesoft.com (builder02.qubesoft.com [192.168.1.8]) i1JGWIsD088287; Thu, 19 Feb 2004 16:32:19 GMT (envelope-from dfr@nlsystems.com) From: Doug Rabson To: Peter A Jonsson In-Reply-To: References: <1077137806.28133.10.camel@herring.nlsystems.com> Content-Type: text/plain Message-Id: <1077208338.9856.1.camel@builder02.qubesoft.com> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.4.0 Date: 19 Feb 2004 16:32:18 +0000 Content-Transfer-Encoding: 7bit cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 19 Feb 2004 16:32:22 -0000 On Thu, 2004-02-19 at 16:26, Peter A Jonsson wrote: > > I imagine that a FreeBSD implementation of RCU wouldn't actually be too > > hard and it might be well worth it as an alternative way of managing > > concurrency, e.g. for the routing cache and the name cache (and probably > > lots of other things). > > Alan Cox pointed out[1] that there was a patent problem (US Patent > #05442758 [2]) with RCU which prevented inclusion in the Linux > kernel. This was solved[3] by granting the right to use it in GPL > software according to my understanding. Isn't this a problem for > FreeBSD? That would be a problem unless the patent owner (Sequent, i.e. IBM) could be encouraged to grant a similar license for BSD software. From owner-freebsd-arch@FreeBSD.ORG Fri Feb 20 09:46:03 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 66C8916A4CE for ; Fri, 20 Feb 2004 09:46:03 -0800 (PST) Received: from carver.gumbysoft.com (carver.gumbysoft.com [66.220.23.50]) by mx1.FreeBSD.org (Postfix) with ESMTP id 60A2C43D1F for ; Fri, 20 Feb 2004 09:46:03 -0800 (PST) (envelope-from dwhite@gumbysoft.com) Received: by carver.gumbysoft.com (Postfix, from userid 1000) id 5654472DBF; Fri, 20 Feb 2004 09:46:03 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by carver.gumbysoft.com (Postfix) with ESMTP id 5191572DB5; Fri, 20 Feb 2004 09:46:03 -0800 (PST) Date: Fri, 20 Feb 2004 09:46:03 -0800 (PST) From: Doug White To: Doug Rabson In-Reply-To: <1077208338.9856.1.camel@builder02.qubesoft.com> Message-ID: <20040220094342.W60703@carver.gumbysoft.com> References: <1077137806.28133.10.camel@herring.nlsystems.com> <1077208338.9856.1.camel@builder02.qubesoft.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: Peter A Jonsson cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 20 Feb 2004 17:46:03 -0000 On Thu, 19 Feb 2004, Doug Rabson wrote: > On Thu, 2004-02-19 at 16:26, Peter A Jonsson wrote: > > > I imagine that a FreeBSD implementation of RCU wouldn't actually be too > > > hard and it might be well worth it as an alternative way of managing > > > concurrency, e.g. for the routing cache and the name cache (and probably > > > lots of other things). > > > > Alan Cox pointed out[1] that there was a patent problem (US Patent > > #05442758 [2]) with RCU which prevented inclusion in the Linux > > kernel. This was solved[3] by granting the right to use it in GPL > > software according to my understanding. Isn't this a problem for > > FreeBSD? > > That would be a problem unless the patent owner (Sequent, i.e. IBM) > could be encouraged to grant a similar license for BSD software. Note that SCO is trying to claim that RCU is derviative of SysV, so it might be a good idea to steer clear of this until that issue is resolved... which might be a while. :) -- Doug White | FreeBSD: The Power to Serve dwhite@gumbysoft.com | www.FreeBSD.org From owner-freebsd-arch@FreeBSD.ORG Fri Feb 20 09:54:31 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id EA22916A4CE for ; Fri, 20 Feb 2004 09:54:31 -0800 (PST) Received: from smtp814.mail.sc5.yahoo.com (smtp814.mail.sc5.yahoo.com [66.163.170.84]) by mx1.FreeBSD.org (Postfix) with SMTP id CB8A143D1D for ; Fri, 20 Feb 2004 09:54:31 -0800 (PST) (envelope-from rsharpe@richardsharpe.com) Received: from unknown (HELO ns.aus.com) (ngsharpe1@sbcglobal.net@67.122.205.184 with plain) by smtp814.mail.sc5.yahoo.com with SMTP; 20 Feb 2004 17:54:31 -0000 Received: from ns.aus.com (durable [127.0.0.1]) by ns.aus.com (8.12.8/8.12.8) with ESMTP id i1KHuH6R006296; Fri, 20 Feb 2004 09:56:17 -0800 Received: from localhost (rsharpe@localhost) by ns.aus.com (8.12.8/8.12.8/Submit) with ESMTP id i1KHuG9Y006292; Fri, 20 Feb 2004 09:56:16 -0800 X-Authentication-Warning: ns.aus.com: rsharpe owned process doing -bs Date: Fri, 20 Feb 2004 09:56:16 -0800 (PST) From: Richard Sharpe X-X-Sender: rsharpe@durable To: Doug White In-Reply-To: <20040220094342.W60703@carver.gumbysoft.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: Peter A Jonsson cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 20 Feb 2004 17:54:32 -0000 On Fri, 20 Feb 2004, Doug White wrote: > > That would be a problem unless the patent owner (Sequent, i.e. IBM) > > could be encouraged to grant a similar license for BSD software. > > Note that SCO is trying to claim that RCU is derviative of SysV, so it > might be a good idea to steer clear of this until that issue is > resolved... which might be a while. :) Hmmm, I don't think that is the case at all. They are, ISTM, claiming that the RCU code contributed to Linux is derived from SysV. That is, they are making a contractual and copyright cliam, I think. It would not be hard to write a non-derived implementation. The more important issue is the Patent issue, but I think there are ways to get IBM to grant royalty free access, after all, they have done it for Linux. Regards ----- Richard Sharpe, rsharpe[at]richardsharpe.com, rsharpe[at]samba.org, sharpe[at]ethereal.com, http://www.richardsharpe.com