Re: reiser4 plugins
On Sun, 10 Jul 2005 02:00:49 +0200, Stefan Smietanowski <[EMAIL PROTECTED]> said: > So basically if I write a program that works in both Gnome and KDE I > should (according to your description) implement my own VFS that will > use the Gnome or KDE VFS that will then use the OS VFS. Either that, or use a whole lot of #ifdefs, or hope that GNOME and KDE agree on a common VFS, or don't use their VFS and just use the basic OS calls and lose the functionality (and portability) of the VFSes, or pick one VFS and hope that the other users can adapt. GNOME and KDE already have their own VFS. I am not asking for anything new. If you don't like the idea of a VFS at that level, take it up with the GNOME and KDE people. > Is it only me finding that a little silly? > I mean, if I am to have the same functionality under neither Gnome nor > VFS and they don't support something I need I _NEED_ a vfs so that my > program is so totally independent on anything at all. > My program calling My VFS which calls KDE/Gnome's VFS which calls the > OS VFS will be slowe than just calling the VFS immidiately - I do hope > you can see that. Of course. It's probably slower than arranging the bits on the hard drive directly, and hand-coding everything in assembly. But there's always a performance price to pay for maintaining the programmer's sanity. There's always a price to pay when writing cross-platform stuff. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Thu, 30 Jun 2005 15:52:25 -0400, Horst von Brand <[EMAIL PROTECTED]> said: >> This doesn't even invalidate the userland VFSs of the other guys, >> they're still needed for systems whose kernels don't have a metadata >> facility. > So the metadata facility in kernel won't be used, for portability's > sake. Oh gee. Every operating system does threads differently. Mozilla has an abstraction layer called nspr that allows them to handle threads portably. glib/gtk has their own threads abstraction. On Windows, nspr will use the Windows method for handling threads. On Linux, it will use the Linux way. On systems that don't support threads, it can usually emulate it using timers. It's the exact same thing with the userspace VFS. If GNOME needs to handle extended attributes, it can use one mechanism under one operating system, or emulate it using some ugly hack on operating systems that don't support extended attributes. Isn't that the whole point of having a VFS? -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Fri, 01 Jul 2005 03:41:00 -0400, Chet Hosey <[EMAIL PROTECTED]> said: > Horst von Brand wrote: >> And who says that a normal user isn't allowed to annotate each and >> every file with its purpose or something else? Explain how you currently allow users to annotate arbitrary files. >> I can very well imagine a system in which users (say students in a >> Linux class) want to do so... on a shared machine. Or users having a >> shared MP3 or photograph or ... collection, with individual notes on >> each. Or even developers wanting to annotate source code files with >> their comments, but leave them read-only (or have them under SCM). > This same argument could be used to attack the idea of group > permissions -- that groups of users might have conflicting > goals. Implementing metadata in userspace via bundled files has the > same drawback. The situation is even better with file-as-dir. If the administrator wants to allow users to edit the description metadata for the file foo, the administrator can set the appropriate permissions for foo/.../description, and keep foo read-only. >>Kevin Bowen <[EMAIL PROTECTED]> wrote: >>> If you're sysadmining a multiuser reiser4 box, and your users are >>> able to modify the metadata of files they don't own, then you go to >>> sysadmin purgatory. Actually, you could use something like unionfs to allow users to keep their own annotations without affecting everyone else's. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Fri, 01 Jul 2005 03:06:19 -0500, David Masover <[EMAIL PROTECTED]> said: > Hubert Chan wrote: >> The main thing blocking file-as-dir is that there are some >> locking(IIRC?) issues. And, of course, some people wouldn't want it >> to be merged into the mainline kernel. (Of course, the latter >> doesn't prevent Namesys from maintaining their own patches for people >> to play around with.) > What's the locking issue? I think that was more about transactions... It was whatever was Al Viro's (technical) complaint about file-as-dir. I don't remember exactly what it was. The technical people know what it is (and the Namesys guys are probably working on it), and the exact issue doesn't concern us non-technical people that much, so I don't feel like looking it up. But if you want to, just look for Al Viro's message in this thread. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Tue, 05 Jul 2005 20:50:08 -0400 EDT, "Alexander G. M. Smith" <[EMAIL PROTECTED]> said: > That sounds equivalent to no hard links (other than the usual parent > directory one). If there's any directory with two links to it, then > there will be a cycle somewhere! What we want is no directed cycles. That is A is the parent of B is the parent of C is the parent of A. We don't care about A is the parent of B is the parent of C; A is the parent of B is the parent of C. OK, here's a random idea that just popped into my head, and to which I've given little thought (read: none whatsoever), and may be the stupidest idea ever proposed on LKML, but thought I would just toss it out to see if it could stimulate someone to come up with something better (read: sane): Conceptually, foo/ is just a symlink to /meta/[filesystem]/[inode of foo]. And a question: is it feasible to store, for each inode, its parent(s), instead of just the hard link count? -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Tue, 05 Jul 2005 22:51:07 -0400, Horst von Brand <[EMAIL PROTECTED]> said: > Hubert Chan <[EMAIL PROTECTED]> wrote: >> On Fri, 01 Jul 2005 03:41:00 -0400, Chet Hosey <[EMAIL PROTECTED]> >> said: >> > Horst von Brand wrote: >> >> And who says that a normal user isn't allowed to annotate each and >> >> every file with its purpose or something else? >> Explain how you currently allow users to annotate arbitrary files. > By keeping annotations /outside/ the files. So if I want to share annotations, I have to look in 20 different places? > [...] >> The situation is even better with file-as-dir. If the administrator >> wants to allow users to edit the description metadata for the file >> foo, the administrator can set the appropriate permissions for >> foo/.../description, and keep foo read-only. > So now root is responsible in exquisite detail for random other users > being able to keep info about my files? I can grant people permissions to write random info into my own files. Or they can use unionfs if I don't grant them permissions. Remember: the above argument was citing an advantage of file-as-dir over packed files (storing metadata as a tar or zip file, similar to what OpenOffice.org does, or even something like exif or id3). In a packed file, I can't allow people to edit the description attribute without allowing them to edit the entire file. With file-as-dir, I get much finer grained permissions. > [...] >> Actually, you could use something like unionfs to allow users to keep >> their own annotations without affecting everyone else's. > Again, root has to mount that stuff for each and every user? suid program that allows union mount into a directory within my own tree (or just into any directory that I have write permissions should be sufficiently secure). -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Wed, 06 Jul 2005 12:52:23 -0600, Jonathan Briggs <[EMAIL PROTECTED]> said: > On Tue, 2005-07-05 at 23:44 -0700, Hans Reiser wrote: >> Hubert Chan wrote: >>> And a question: is it feasible to store, for each >>> inode, its parent(s), instead of just the hard link count? >> Ooh, now that is an interesting old idea I haven't considered in 20 >> years makes fsck more robust too If you can store the parents, then finding cycles (relatively) quickly is pretty easy: before you try to make A the parent of B, walk up the parent pointers starting from A. If you ever reach B, you have a cycle. If not, you don't have a cycle. (Hmmm. Do I need a proof of correctness for this? It's just depth-first-search, which everybody learned in their first algorithms course.) Running time is (at most) just the sum of all (directed) path lengths from A to the root. Assuming people don't have too deep of a hierarchy, or too much branching with hard links (i.e. nodes with too many parents), which I think is a reasonable assumption, running time should be fairly quick. (People may have millions of files in a single directory, which is why doing the DFS in the forward direction is a bad idea. But people probably don't have millions of hard links to the same file, or hierarchies that are millions of levels deep.) And it only happens when a hard link is created -- probably not a very performance-dependent event (i.e. it's not the scheduling algorithm). I would imagine that some creative caching could be done to speed up the situation where you try to make a whole batch of hard links. (When you walk up the parent pointers starting from A, cache the inode numbers that you encounter. If you then try to make A the parent of C, check if C is one of the inode numbers in the cache. If yes, we have a cycle; if no, we don't have a cycle.) Extra disk storage is just about one extra word for most nodes (that only have one parent -- basically, one extra word per parent), if you can pack the data efficiently. (i.e. we don't want to waste a extra whole block per node.) Of course, since this requires extra storage on the part of the filesystem, the (kernel) VFS change would have to be something where the VFS asks the filesystem whether making A the parent of B will create a cycle; it's not something the VFS can do transparently for everybody. Filesystems that don't store this extra stuff just return "yes" if B is a directory (thus disallowing the link), and "no" if B is a file, and we get the same situation we have right now. It would require a disk format change (sort of) in Reiser4, but (as Hans mentioned) since we have plugins, shouldn't require a reformat (as I understand it). Just run a tool that builds the parent-pointer data; until you run that tool, the filesystem can just disallow hard links. After you run the tool, updating parent pointers is handled automatically by the filesystem. > Hey, sounds like the idea I proposed a couple months ago of storing > the path names in each file, instead of in directories. Only better, > since each path component isn't text but a link instead. > It still has the performance and locking problem of having to update > every child file when moving a directory tree to a new parent. On the > other hand, maybe the benefit is worth the cost. Every node should store the inode number(s) for its parent(s). Not the path name. So you don't need to do any updates, since when you move a tree, inode numbers don't change. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Wed, 06 Jul 2005 14:33:18 -0600, Jonathan Briggs <[EMAIL PROTECTED]> said: > On Wed, 2005-07-06 at 15:51 -0400, Hubert Chan wrote: >> On Wed, 06 Jul 2005 12:52:23 -0600, Jonathan Briggs >> <[EMAIL PROTECTED]> said: > [snip] >>> It still has the performance and locking problem of having to >>> update every child file when moving a directory tree to a new >>> parent. On the other hand, maybe the benefit is worth the cost. >> Every node should store the inode number(s) for its parent(s). Not >> the path name. So you don't need to do any updates, since when you >> move a tree, inode numbers don't change. > You do need the updates if you change what inode is the parent. > /a/b/c, /a/b/d, /a/b/e, /b > mv /a/b /b > Now you have to change the stored grand-parent inodes for /a/b/c, > /a/b/d and /a/b/e so that they reference /b/b instead of /a/b. Don't store (great)*grand-parent pointers; only parent pointers. c points to b, b points to a, a points to root. c doesn't need to know about /a or root directly. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Wed, 06 Jul 2005 16:33:23 -0400, Horst von Brand <[EMAIL PROTECTED]> said: > Hubert Chan <[EMAIL PROTECTED]> wrote: >> If you can store the parents, then finding cycles (relatively) >> quickly is pretty easy: before you try to make A the parent of B, >> walk up the parent pointers starting from A. If you ever reach B, >> you have a cycle. If not, you don't have a cycle. (Hmmm. Do I need >> a proof of correctness for this? It's just depth-first-search, which >> everybody learned in their first algorithms course.) > Correct. And you need space for potentially a huge lot of up pointers > for each file. People (that I know of) don't normally have a huge lot of hardlinks to a single file. > And then there is the (very minor) problem is that meanwhile /nothing/ > can touch the filesystem to do any change... If the DFS is quick, it shouldn't make much difference. Lock nodes as you walk up the tree, and people can change unlocked nodes without harming anything. All you need to do is make sure that no up pointers get added to nodes that you've already looked at. People can also still edit files without changing the tree (and hence not screwing up the DFS). > How do you delete such an object? You will have to delete from each > child down to the first object that has a pointer to it from the > outside, if you don't want garbage left behind. And that means walking > down to /each/ reachable object, then walking up from there to see if > all its parents are in the DAG rooted at what you are going to > delete. This means potentially walking through the whole filesystem > (if you want to delete the root, or something near). You will run out > of memory, and again, meanwhile no changes can be allowed. What does deleting have to do with up pointers? If you delete a directory that has refcount greater than 1, you decrease the refcount, remove the appropriate up pointer, and remove the inode entry from its parent. If you delete a directory that has refcount equal to 1, well, we're in the same situation we're in right now when you delete a directory; you need to "rm -r", which doesn't lock up the whole filesystem. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
On Wed, 06 Jul 2005 23:42:50 -0700, Hans Reiser <[EMAIL PROTECTED]> said: > Oh no, don't store the whole path, store just the parent list. This > will make fsck more robust in the event that the directory gets > clobbered by hardware error. > I don't think it affects the cost of detecting cycles though, I think > it only makes fsck more robust. It doesn't affect the worst-case cost of detecting cycles; by necessity, any (static [1]) directed cycle detection algorithm must take O(n) time, n being the size of the tree (nodes + links). However, under "reasonable assumptions" (where the reasonableness of those assumptions may be questioned, but I think they're reasonable), I think that doing a depth-first-search through the parent links makes the algorithm not-too-terrible. Namely, the "reasonable assumptions" are that a node doesn't have "too many" parents, and the filesystem hierarchy is not "too deep". [1] BTW, I had also previously looked at online/dynamic algorithms, for those who are familiar with that area. The best known so far is still O(n) worst case, but much, much smaller in "most cases". -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: reiser4 plugins
Did you mean to reply to the list? I'm taking the liberty of sending my reply to the list. On 2005-07-06 17:50:07 -0400 Horst von Brand <[EMAIL PROTECTED]> wrote: Hubert Chan <[EMAIL PROTECTED]> wrote: On Wed, 06 Jul 2005 16:33:23 -0400, Horst von Brand <[EMAIL PROTECTED]> said: Hubert Chan <[EMAIL PROTECTED]> wrote: If you can store the parents, then finding cycles (relatively) quickly is pretty easy: before you try to make A the parent of B, walk up the parent pointers starting from A. If you ever reach B, you have a cycle. If not, you don't have a cycle. (Hmmm. Do I need a proof of correctness for this? It's just depth-first-search, which everybody learned in their first algorithms course.) Correct. And you need space for potentially a huge lot of up pointers for each file. Which space are you talking about? Disk space, or memory space? Anyways, for disk space, you're basically just doubling the size of the tree -- two pointers per link instead of one. As for memory space, the DFS only takes a couple of words times the depth of the tree. People (that I know of) don't normally have a huge lot of hardlinks to a single file. Can't rely on that... And then there is the (very minor) problem is that meanwhile /nothing/ can touch the filesystem to do any change... If the DFS is quick, it shouldn't make much difference. Lock nodes as you walk up the tree, and people can change unlocked nodes without harming anything. All you need to do is make sure that no up pointers get added to nodes that you've already looked at. If somebody meanwhile tries to link an ancestor of (one of) your node(s) to a descendent, you've got two DFSes going at once through the same paths... a single lock won't help. Good point. You would need to use a counter instead of just a flag for the lock. There's another problem with my proposal though (finding it is left as an exercise for the reader ;-) ). I think it can be avoided, but I don't have the time right now to properly write it up. (No time to properly write out what the problem is either. I'm already behind on my work as it is!) Maybe next week... (Out of town this weekend.) Anyways, you only really need to prevent creating other hard links while doing the DFS. Unliking won't cause a problem -- worst that can happen is that the DFS gives you a false positive. (OK, you need to make sure that the new parent that you're linking the child node to doesn't disappear from under you.) Creating new files/directories won't case a problem -- they're new files/directories; they can't cause cycles. Besides, you lost the nice property of top-down lock ordering that makes the traversal of Unix filesystems naturally deadlock-free. Yes, I don't know much about what locks the filesystem/VFS does already. I'll need to look into that. -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
