Re: vmpage race and deadlock

2010-11-28 Thread Mindaugas Rasiukevicius
Juergen Hannken-Illjes hann...@eis.cs.tu-bs.de wrote: Some weeks ago I started my fs stress test (5 x fsstress+fsx+dbench) on a log enabled ffs1 file system backed by md(4). Usually within hours I get a deadlock where a thread is waiting on genput but the page in question is neither BUSY nor

radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
Hello, our FFS quota system is pretty outdated and is less and less suitable for modern storage (quotacheck is long and can't be avoided). I'm thinking about coding a new quota system with would be more closely integrated with the filesystem, where quotas would be integrated with filesystem

Re: radix tree implementation for quota ?

2010-11-28 Thread Ted Lemon
On Nov 28, 2010, at 10:53 AM, Manuel Bouyer wrote: Do we have a generic enough radix implementation somewhere wich could be used for this ? We already use it for network routing table, but it didn't look generic to me. It seems like overkill for a project like this, although I'm sure it would

Re: radix tree implementation for quota ?

2010-11-28 Thread Ted Lemon
On Nov 28, 2010, at 11:08 AM, Ignatios Souvatzis wrote: Why? It's a sparse file unless you copy it using cp. True enough, but using sparse files this way tends to violate the principle of least surprise, so I think Manuel's right to be thinking about not doing it this way.

Re: radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
On Sun, Nov 28, 2010 at 11:10:32AM -0600, Ted Lemon wrote: On Nov 28, 2010, at 11:07 AM, Manuel Bouyer wrote: You're suggesting I should include Berkeley DB in the kernel, right ? No, wouldn't the kernel just deliver UIDs and usages? Yes, but this needs to be stored somewhere on a stable

Re: radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
On Sun, Nov 28, 2010 at 05:21:52PM +, Sad Clouds wrote: On Sun, 28 Nov 2010 17:53:59 +0100 Manuel Bouyer bou...@antioche.eu.org wrote: One open question is how to store quota informations on disk. At this time we use one big array indexed by uid or gid. This can be very

Re: radix tree implementation for quota ?

2010-11-28 Thread Matt Thomas
On Nov 28, 2010, at 9:27 AM, Manuel Bouyer wrote: On Sun, Nov 28, 2010 at 05:21:52PM +, Sad Clouds wrote: On Sun, 28 Nov 2010 17:53:59 +0100 Manuel Bouyer bou...@antioche.eu.org wrote: One open question is how to store quota informations on disk. At this time we use one big array

Re: radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
On Sun, Nov 28, 2010 at 09:31:47AM -0800, Matt Thomas wrote: [...] This does assume you are going to cache the entire quota file while the file system is mounted. which assumes you have enough RAM (which is likely true for today's usage and hardware). another issue is that you can't

Re: radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
On Sun, Nov 28, 2010 at 05:40:15PM +, Sad Clouds wrote: On Sun, 28 Nov 2010 18:27:07 +0100 Manuel Bouyer bou...@antioche.eu.org wrote: Wouldn't a hash table work? I think it's too dependant on uid distribution, or even how much uid you have. a tree scales and adapts better.

Re: radix tree implementation for quota ?

2010-11-28 Thread Ted Lemon
On Nov 28, 2010, at 11:25 AM, Manuel Bouyer wrote: (but then the kernel has to know about limits too). You could hang it off the user structure... :)

Re: radix tree implementation for quota ?

2010-11-28 Thread Robert Elz
Date:Sun, 28 Nov 2010 19:46:46 +0100 From:Manuel Bouyer bou...@antioche.eu.org Message-ID: 20101128184645.gd17...@antioche.eu.org | one issue (which isn't really one) is that you'd then need to have | 2 distinct block allocation for new uid. Not really, or not

Re: radix tree implementation for quota ?

2010-11-28 Thread David Laight
On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote: Wouldn't a hash table work? I think it's too dependant on uid distribution, or even how much uid you have. a tree scales and adapts better. I agree, hash tables often degenerate into a linear search. This means that it is still

Re: radix tree implementation for quota ?

2010-11-28 Thread Manuel Bouyer
On Sun, Nov 28, 2010 at 09:34:29PM +, David Laight wrote: On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote: Wouldn't a hash table work? I think it's too dependant on uid distribution, or even how much uid you have. a tree scales and adapts better. I agree, hash

Re: New apple keymap variant or keymap in /usr/share/wscons/keymaps?

2010-11-28 Thread Matthew Mondor
On Sun, 28 Nov 2010 21:04:54 +0100 Frank Wille fr...@phoenix.owl.de wrote: I came to the conclusion that it might be easier and less intrusive to create a new keymap file (e.g. called ukbd.apple.powerbook) for those function keys. So they can easily be added to any national keyboard layout.

Re: vmpage race and deadlock

2010-11-28 Thread Matthew Mondor
On Sun, 28 Nov 2010 09:30:44 +0100 Juergen Hannken-Illjes hann...@eis.cs.tu-bs.de wrote: Usually within hours I get a deadlock where a thread is waiting on genput but the page in question is neither BUSY nor WANTED. I suppose I tracked (*1) it down to three places, where we change page flags

Re: radix tree implementation for quota ?

2010-11-28 Thread David Laight
On Sun, Nov 28, 2010 at 10:35:21PM +0100, Manuel Bouyer wrote: On disk, I'm not sure. Once you've read a disk block, you might as well do a linear search! except the quota data may well need several disk blocks. But there will be a moderate number of users per block? So you need some

Re: radix tree implementation for quota ?

2010-11-28 Thread David Laight
On Sun, Nov 28, 2010 at 10:35:21PM +0100, Manuel Bouyer wrote: I don't think this would work well for NFS servers, where users have no process running on the system doing the limit checks, while there may be lots of different UIDs active at the same time. This is exactly my use case :) Keep a

Re: radix tree implementation for quota ?

2010-11-28 Thread David Laight
On Sun, Nov 28, 2010 at 09:47:02PM +, David Holland wrote: (Also, why a radix tree? Radix trees are generally not very efficient. If you're going to, though, you might want to reuse the direct, indirect, double indirect, etc. method FFS uses for block mapping.) One lookup scheme I've

Re: radix tree implementation for quota ?

2010-11-28 Thread David Holland
On Sun, Nov 28, 2010 at 09:47:02PM +, David Holland wrote: (Also, why a radix tree? Radix trees are generally not very efficient. If you're going to, though, you might want to reuse the direct, indirect, double indirect, etc. method FFS uses for block mapping.) ...and the easiest way to

Re: radix tree implementation for quota ?

2010-11-28 Thread Dennis Ferguson
On 28 Nov 2010, at 13:47 , David Holland wrote: (Also, why a radix tree? Radix trees are generally not very efficient. If you're going to, though, you might want to reuse the direct, indirect, double indirect, etc. method FFS uses for block mapping.) I think generalizations are generally

Re: radix tree implementation for quota ?

2010-11-28 Thread Joerg Sonnenberger
On Sun, Nov 28, 2010 at 05:53:59PM +0100, Manuel Bouyer wrote: One open question is how to store quota informations on disk. At this time we use one big array indexed by uid or gid. This can be very space-consuming if you have a very sparse uid/gid allocation, this is why I don't think this

Re: radix tree implementation for quota ?

2010-11-28 Thread Sad Clouds
On Sun, 28 Nov 2010 21:34:29 + David Laight da...@l8s.co.uk wrote: On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote: Wouldn't a hash table work? I think it's too dependant on uid distribution, or even how much uid you have. a tree scales and adapts better. I agree,

Re: radix tree implementation for quota ?

2010-11-28 Thread David Holland
On Sun, Nov 28, 2010 at 11:43:48PM +0100, Joerg Sonnenberger wrote: A radix tree is kind of a bad choice for this purpose. The easiest approach is most likely to have [a btree] I would go with an expanding hash table of some kind, e.g. size is 2^n pages, hash (2^n - 1) tells you the page to